International Association
for Cryptologic Research

State-machine replication (SMR) allows a state machine to be replicated across a set of replicas and handle clients' requests as a single machine. Most existing SMR protocols are leader-based, i.e., requiring a leader to order requests and coordinate the protocol. This design places a disproportionately high load on the leader, inevitably impairing the scalability. If the leader fails, a complex and bug-prone fail-over protocol is needed to switch to a new leader. An adversary can also exploit the fail-over protocol to slow down the protocol. In this paper, we propose a crash-fault tolerant SMR named Cascade, with the following properties: • Leaderless: it does not require a leader, hence completely get rid of the fail-over protocol. • Scalable: it can scale to a large number of replicas. %its throughput increases with the number of replicas. • Robust: it behaves well even under a poor network connection. We provide a full-fledged implementation of Cascade and systematically evaluate its performance. Our benchmark results show that Cascade achieves a peak throughput of around two million TPS, up to 8.7$\times$ higher than the state-of-the-art leaderless SMR.

A prevalent issue in the residue number system (RNS) variant of the Cheon-Kim-Kim-Song (CKKS) homomorphic encryption (HE) scheme is the challenge of efficiently achieving high precision on hardware architectures with a fixed, yet smaller, word-size of bit-length $W$, especially when the scaling factor satisfies $\log\Delta > W$. In this work, we introduce an efficient solution termed composite scaling. In this approach, we group multiple RNS primes as $q_\ell:= \prod_{j=0}^{t-1} q_{\ell,j}$ such that $\log q_{\ell,j} < W$ for $0\le j < t$, and use each composite $q_\ell$ in the rescaling procedure as $\mathsf{ct}\mapsto \lfloor \mathsf{ct} / q_\ell\rceil$. Here, the number of primes, denoted by $t$, is termed the composition degree. This strategy contrasts the traditional rescaling method in RNS-CKKS, where each $q_\ell$ is chosen as a single $\log\Delta$-bit prime, a method we designate as single scaling. To achieve higher precision in single scaling, where $\log\Delta > W$, one would either need a novel hardware architecture with word size $W' > \log\Delta$ or would have to resort to relatively inefficient solutions rooted in multi-precision arithmetic. This problem, however, doesn't arise in composite scaling. In the composite scaling approach, the larger the composition degree $t$, the greater the precision attainable with RNS-CKKS across an extensive range of secure parameters tailored for workload deployment. We have integrated composite scaling RNS-CKKS into both OpenFHE and Lattigo libraries. This integration was achieved via a concrete implementation of the method and its application to the most up-to-date workloads, specifically, logistic regression training and convolutional neural network inference. Our experiments demonstrate that single and composite scaling approaches are functionally equivalent, both theoretically and practically.

Blockchain users who submit transactions through private pools are guaranteed pre-trade privacy but face execution risk. We argue that private pools serve the intended purpose of eliminating frontrunning risk, only if such risk is high. Otherwise, some validators may decide to avoid monitoring private pools to preserve rents extracted from frontrunning bots. Private pools intensify the execution arms race for bots, thus decreasing their payoffs {and increasing validators' rents}. The private pool option reduces blockspace allocative inefficiencies and raises aggregate welfare.

Dual attacks aiming at decoding generic linear codes have been found recently to outperform for certain parameters information set decoding techniques which have been for $60$ years the dominant tool for solving this problem and choosing the parameters of code-based cryptosystems. However, the analysis of the complexity of these dual attacks relies on some unproven assumptions that are not even fully backed up with experimental evidence.

These dual attacks can actually be viewed as the code-based analogue of dual attacks in lattice based cryptography. Here too, dual attacks have been found out those past years to be strong competitors to primal attacks and a controversy has emerged whether similar heuristics made for instance on the independence of certain random variables really hold.

We will show that the dual attacks in coding theory can be studied by providing in a first step a simple alternative expression of the fundamental quantity used in these dual attacks. We then show that this expression can be studied without relying on independence assumptions whatsoever.

This study leads us to discover that there is indeed a problem with the latest and most powerful dual attack introduced in the recent Asiacrypt 2022 paper "Statistical decoding 2.0: Reducing Decoding to LPN" (RLPN) and that for the parameters chosen in this algorithm there are indeed false candidates which are produced and which are not predicted by the analysis provided there which relies on independence assumptions.

We then suggest a slight modification of this algorithm consisting in a further verification step, analyze it thoroughly, provide experimental evidence that our analysis is accurate and show that the complexity claims made in RLPN are indeed valid for this modified algorithm. This approach provides a simple methodology for studying rigorously dual attacks which could turn out to be useful for further developing the subject.

The identity-based signature, initially introduced by Shamir [Sha84], plays a fundamental role in the domain of identity-based cryptography. It offers the capability to generate a signature on a message, allowing any user to verify the authenticity of the signature using the signer's identifier information (e.g., an email address), instead of relying on a public key stored in a digital certificate. Another significant concept in practical applications is the threshold signature, which serves as a valuable tool for distributing the signing authority. The notion of an identity-based threshold signature scheme pertains to the distribution of a secret key associated with a specific identity among multiple entities, rather than depending on a master secret key generated by a public key generator. This approach enables a qualified group of participants to jointly engage in the signing process. In this paper, we present two identity-based threshold signature schemes based on isogenies, each of which addresses a different aspect of security. The first scheme prioritizes efficiency but offers security with abort, while the second scheme focuses on robustness. Both schemes ensure active security in the quantum random oracle model. To build these identity-based threshold signatures, we begin by modifying the identity-based signature scheme proposed by Shaw and Dutta [SD21], to accommodate the CSI-SharK signature scheme. Subsequently, we leverage the resulting identity-based signature and build two threshold schemes within the CSIDH (Commutative Supersingular Isogeny Diffie-Hellman) framework. Our proposed identity-based threshold signatures are designed based on CSI-SharK and can be easily adapted with minimal adjustments to function with CSI-FiSh.

Vectorial dual-bent functions have recently attracted some researchers' interest as they play a significant role in constructing partial difference sets, association schemes, bent partitions and linear codes. In this paper, we further study vectorial dual-bent functions $F: V_{n}^{(p)}\rightarrow V_{m}^{(p)}$, where $2\leq m \leq \frac{n}{2}$, $V_{n}^{(p)}$ denotes an $n$-dimensional vector space over the prime field $\mathbb{F}_{p}$. We give new characterizations of certain vectorial dual-bent functions (called vectorial dual-bent functions with Condition A) in terms of amorphic association schemes, linear codes and generalized Hadamard matrices, respectively. When $p=2$, we characterize vectorial dual-bent functions with Condition A in terms of bent partitions. Furthermore, we characterize certain bent partitions in terms of amorphic association schemes, linear codes and generalized Hadamard matrices, respectively. For general vectorial dual-bent functions $F: V_{n}^{(p)}\rightarrow V_{m}^{(p)}$ with $F(0)=0, F(x)=F(-x)$ and $2\leq m \leq \frac{n}{2}$, we give a necessary and sufficient condition on constructing association schemes. Based on such a result, more association schemes are constructed from vectorial dual-bent functions.

This paper analyses the Secure Remote Password Protocol (SRP) in the context of provable security. SRP is an asymmetric Password-Authenticated Key Exchange (aPAKE) protocol introduced in 1998. It allows a client to establish a shared cryptographic key with a server based on a password of potentially low entropy. Although the protocol was part of several standardization efforts, and is deployed in numerous commercial applications such as Apple Homekit, 1Password or Telegram, it still lacks a formal proof of security. This is mainly due to some of the protocol's design choices which were implemented to circumvent patent issues. Our paper gives the first security analysis of SRP in the universal composability (UC) framework. We show that SRP is UC-secure against passive eavesdropping attacks under the standard CDH assumption in the random oracle model. We then highlight a major protocol change designed to thwart active attacks and propose a new assumption -- the additive Simultaneous Diffie Hellman (aSDH) assumption -- under which we can guarantee security in the presence of an active attacker. Using this new assumption as well as the Gap CDH assumption, we prove security of the SRP protocol against active attacks. Our proof is in the "Angel-based UC framework", a relaxation of the UC framework which gives all parties access to an oracle with super-polynomial power. In our proof, we assume that all parties have access to a DDH oracle (limited to finite fields). We further discuss the plausibility of this assumption and which level of security can be shown without it.

The support minors method has become indispensable to cryptanalysts in attacking various post-quantum cryptosystems in the areas of multivariate cryptography and rank-based cryptography. The complexity analysis for support minors minrank calculations is a bit messy, with no closed form for the Hilbert series of the ideal generated by the support minors equations (or, more correctly, for the quotient of the polynomial ring by this ideal).

In this article, we provide a generating series whose coefficients are the Hilbert Series of related MinRank ideals. This simple series therefore reflects and relates the structure of all support minors ideals. Its simplicity also makes it practically useful in computing the complexity of support minors instances.

Distributing the Elliptic Curve Digital Signature Algorithm (ECDSA) has received increased attention in past years due to the wide range of applications that can benefit from this, particularly after the popularity that the blockchain technology has gained. Many schemes have been proposed in the literature to improve the efficiency of multi- party ECDSA. Most of these schemes either require heavy homomorphic encryption computation or multiple executions of a functionality that transforms Multiplicative shares to Additive shares (MtA). Xue et al. (CCS 2021) proposed a 2-party ECDSA protocol secure against mali- cious adversaries and only requires one execution of MtA, with an online phase that consists of only one party sending one field element to the other party with a computational overhead dominated by the verifica- tion step of the signature scheme. We propose a novel protocol, based on the assumption that the Computational Diffie-Hellman problem is hard, that offers the same online phase performance as the protocol of Xue et al., but improves the offline phase by reducing the computational cost by one elliptic curve multiplication and the communication cost by two field elements. To the best of our knowledge, our protocol offers the most efficient offline phase for a two-party ECDSA protocol with such an efficient online phase.

Blockchain auction plays an important role in the price discovery of digital assets (e.g. NFTs). However, despite their importance, implementing auctions directly on blockchains such as Ethereum incurs scalability issues. In particular, the on-chain transactions scale poorly with the number of bidders, leading to network congestion, increased transaction fees, and slower transaction confirmation time. This lack of scalability significantly hampers the ability of the system to handle large-scale, high-speed auctions that are common in today's economy. In this work, we build a protocol where an auctioneer can conduct sealed bid auctions that run entirely off-chain when parties behave honestly, and in the event that $k$ bidders deviate (e.g., do not open their sealed bid) from an $n$-party auction protocol, then the on-chain complexity is only $O(k \log n)$. This improves over existing solutions that require $O(n)$ on-chain complexity, even if a single bidder deviates from the protocol. In the event of a malicious auctioneer, our protocol still guarantees that the auction will successfully terminate. We implement our protocol and show that it offers significant efficiency improvements compared to existing on-chain solutions. Our use of zkSnark to achieve scalability also ensures that the on-chain contract and other participants do not acquire any information about the bidders' identities and their respective bids, except for the winner and the winning bid amount.

Ascon, a family of algorithms that supports hashing and authenticated encryption, is the winner of the NIST Lightweight Cryptography Project. In this paper, we propose an improved preimage attack against 2-round Ascon-XOF-64 with a complexity of $2^{32}$ via a better guessing strategy. Furthermore, in order to find a good guessing strategy efficiently, we build a MILP model and successfully extend the attack to 3 rounds. The time complexity is $2^{53}$ when $IV=0$, while for the real $IV$, the attack still works and the time complexity is $2^{51}$. Additionally, we also investigate the resistance of Ascon-HASH against collision attacks. We introduce the linearization of the inverse of S-boxes and then propose a practical free-start collision attack on 3-round Ascon-HASH using a differential trail searched dedicatedly. Furthermore, We construct different 2-round connectors using the linearization of the inverse of S-boxes and successfully extend the collision attack to 4 rounds and 5 rounds of Ascon-HASH with complexities of $2^{21}$ and $2^{41}$ respectively. Although our attacks do not compromise the security of the full 12-round Ascon-XOF and Ascon-HASH, they provide some insights into Ascon's security.

We present a cryptographic string commitment scheme that is computationally hiding and binding based on (modular) subset sum problems. It is believed that these NP-complete problems provide post-quantum security contrary to the number theory assumptions currently used in cryptography. Using techniques recently introduced by Feneuil, Maire, Rivain and Vergnaud, this simple commitment scheme enables an efficient zero-knowledge proof of knowledge for committed values as well as proofs showing Boolean relations amongst the committed bits. In particular, one can prove that committed bits $m_0, m_1, ..., m_\ell$ satisfy $m_0 = C(m_1, ..., m_\ell)$ for any Boolean circuit $C$ (without revealing any information on those bits). The proof system achieves good communication and computational complexity since for a security parameter $\lambda$, the protocol's communication complexity is $\tilde{O}(|C| \lambda + \lambda^2)$ (compared to $\tilde{O}(|C| \lambda^2)$ for the best code-based protocol due to Jain, Krenn, Pietrzak and Tentes).

A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both conceptually and technically).

Our goal is to provide a construction of a PRG from OWFs with a simple proof of security; we thus focus on the setting of non-uniform security (i.e., we start off with a OWF secure against non-uniform PPT, and we aim to get a PRG secure against non-uniform PPT).

Our main result is a construction of a PRG from OWFs with a self-contained, simple, proof of security, relying only on the Goldreich-Levin Theorem (and the Chernoff bound). Although our main goal is simplicity, the construction, and a variant there-of, also improves the efficiency—in terms of invocations and seed lengths—of the state-of-the-art constructions due to [Haitner-Reingold-Vadhan, STOC’10] and [Vadhan-Zheng, STOC’12], by a factor $O(\log^2 n)$.

The key novelty in our analysis is a generalization of the Blum-Micali [FOCS’82] notion of unpredictabilty—rather than requiring that every bit in the output of a function is unpredictable, we count how many unpredictable bits a function has, and we show that any OWF on $n$ input bits (after hashing the input and the output) has $n + O(\log n)$ unpredictable output bits. Such unpredictable bits can next be “extracted” into a pseudorandom string using standard techniques.

Gentry's groundbreaking work showed that a fully homomorphic, provably secure scheme is possible via bootstrapping a somewhat homomorphic scheme. However, a major drawback of bootstrapping is its high computational cost. One alternative is to use a different metric for noise so that homomorphic operations do not accumulate noise, eliminating the need for boostrapping altogether. Leonardi and Ruiz-Lopez present a group-theoretic framework for such a ``noise non-accumulating'' multiplicative homomorphic scheme, but Agathocleous et al. expose weaknesses in this framework when working over finite abelian groups. Tangentially, Li and Wang present a ``noise non-accumulating'' fully homomorphic scheme by performing Ostrovsky and Skeith's transform on a multiplicative homomorphic scheme of non-abelian group rings. Unfortunately, the security of Li and Wang's scheme relies on the Factoring Large Numbers assumption, which is false given an adversary with a quantum computer. In this work, we seek to modify Li and Wang's scheme to be post-quantum secure by fitting it into the Leonardi and Ruiz-Lopez framework for non-abelian rings. We discuss improved security assumptions for Li and Wang encryption and assess the shortcomings of working in a non-abelian setting. Finally, we show that a large class of semisimple rings is incompatible with the Leonardi and Ruiz-Lopez framework.

Truncated differential attacks were introduced by Knudsen in 1994 [1]. They are a well-known family that has arguably received less attention than some other variants of differential attacks. This paper gives some new insight on truncated differential attacks and provides the best-known attacks on both variants of the lightweight cipher QARMA, in the single tweak model, reaching for the first time 10 rounds while contradicting the security claims of this reduced version. These attacks use some new truncated distinguishers as well as some evolved key-recovery techniques.

Given a supersingular elliptic curve $E$ and a non-scalar endomorphism $\alpha$ of $E$, we prove that the endomorphism ring of $E$ can be computed in classical time about $\text{disc}(\mathbb{Z}[\alpha])^{1/4}$ , and in quantum subexponential time, assuming the generalised Riemann hypothesis. Previous results either had higher complexities, or relied on heuristic assumptions.

Along the way, we prove that the Primitivisation problem can be solved in polynomial time (a problem previously believed to be hard), and we prove that the action of smooth ideals on oriented elliptic curves can be computed in polynomial time (previous results of this form required the ideal to be powersmooth, i.e., not divisible by any large prime power). Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results.

Blind signatures serve as a foundational tool for privacy-preserving applications and have recently seen renewed interest due to new applications in blockchains and privacy-authentication tokens. With this, constructing practical round-optimal (i.e., signing consists of the minimum two rounds) blind signatures in the random oracle model (ROM) has been an active area of research, where several impossibility results indicate that either the ROM or a trusted setup is inherent.

In this work, we present two round-optimal blind signatures under standard assumptions in the ROM with different approaches: one achieves the smallest sum of the signature and communication sizes, while the other achieves the smallest signature size. Both of our instantiations are based on standard assumptions over asymmetric pairing groups, i.e., CDH, DDH, and/or SXDH. Our first construction is a highly optimized variant of the generic blind signature construction by Fischlin (CRYPTO'06) and has signature and communication sizes 447 B and 303 B, respectively. We progressively weaken the building blocks required by Fischlin and we result in the first blind signature where the sum of the signature and communication sizes fit below 1 KB based on standard assumptions. Our second construction is a semi-generic construction from a specific class of randomizable signature schemes that admits an all-but-one reduction. The signature size is only 96 B while the communication size is 2.2 KB. This matches the previously known smallest signature size while improving the communication size by several orders of magnitude. Finally, both of our constructions rely on a (non-black box) fine-grained analysis of the forking lemma that may be of independent interest.

As concerns are increasingly raised about data privacy, encrypted database management system (DBMS) based on fully homomorphic encryption (FHE) attracts increasing research attention, as FHE permits DBMS to be directly outsourced to cloud servers without revealing any plaintext data. However, the real-world deployment of FHE-based DBMS faces two main challenges: i) high computational latency, and ii) lack of elastic query processing capability, both of which stem from the inherent limitations of the underlying FHE operators. Here, we introduce HE$^3$DB, a fully homomorphically encrypted, efficient and elastic DBMS framework based on a new FHE infrastructure. By proposing and integrating new arithmetic and logic homomorphic operators, we devise fast and high-precision homomorphic comparison and aggregation algorithms that enable a variety of SQL queries to be applied over FHE ciphertexts, e.g., compound filter-aggregation, sorting, grouping, and joining. In addition, in contrast to existing encrypted DBMS that only support aggregated information retrieval, our framework permits further server-side analytical processing over the queried FHE ciphertexts, such as private decision tree evaluation. In the experiment, we rigorously study the efficiency and flexibility of HE$^3$DB. We show that, compared to the state-of-the-art techniques,HE$^3$DB can homomorphically evaluate end-to-end SQL queries as much as $41\times$ -$299\times$ faster than the state-of-the-art solution, completing a TPC-H query over a 16-bit 10K-row database within 241 seconds.

We propose a new compiler framework that automates code generation over multiple fully homomorphic encryption (FHE) schemes. While it was recently shown that algorithms combining multiple FHE schemes (e.g., CKKS and TFHE) achieve high execution efficiency and task utility at the same time, developing fast cross-scheme FHE algorithms for real-world applications generally require heavy hand-tuned optimizations by cryptographic experts, resulting in either high usability costs or low computational efficiency. To solve the usability and efficiency dilemma, we design and implement HEIR, a compiler framework based on multi-level intermediate representation (IR). To achieve cross-scheme compilation of efficient FHE circuits, we develop a two-stage code-lowering structure based on our custom IR dialects. First, the plaintext program along with the associated data types are converted into FHE-friendly dialects in the transformation stage. Then, in the optimization stage, we apply FHE-specific optimizations to lower the transformed dialect into our bottom-level FHE library operators. In the experiment, we implement the entire software stack for HEIR, and demonstrate that complex end-to-end programs, such as homomorphic K-Means clustering and homomorphic data aggregation in databases, can easily be compiled to run $72$--$179\times$ faster than the program generated by the state-of-the-art FHE compilers.

Sponge paradigm, used in the design of SHA-3, is an alternative hashing technique to the popular Merkle-Damgård paradigm. We revisit the problem of finding $B$-block-long collisions in sponge hash functions in the auxiliary-input random permutation model, in which an attacker gets a piece of $S$-bit advice about the random permutation and makes $T$ (forward or inverse) oracle queries to the random permutation.

Recently, significant progress has been made in the Merkle-Damgård setting and optimal bounds are known for a large range of parameters, including all constant values of $B$. However, the sponge setting is widely open: there exist significant gaps between known attacks and security bounds even for $B=1$.

Freitag, Ghoshal and Komargodski (CRYPTO 2022) showed a novel attack for $B=1$ that takes advantage of the inverse queries and achieves advantage $\tilde{\Omega}(\min(S^2T^2/2^{2c}$, $ (S^2T/2^{2c})^{2/3})+T^2/2^r)$, where $r$ is bit-rate and $c$ is the capacity of the random permutation. However, they only showed an $\tilde{O}(ST/2^c+T^2/2^r)$ security bound, leaving open an intriguing quadratic gap. For $B=2$, they beat the general security bound by Coretti, Dodis, Guo (CRYPTO 2018) for arbitrary values of $B$. However, their highly non-trivial argument is quite laborious, and no better (than the general) bounds are known for $B\geq 3$.

In this work, we study the possibility of proving better security bounds in the sponge setting. To this end, - For $B=1$, we prove an improved $\tilde{O}(S^2T^2/2^{2c}+S/2^c+T/2^c+T^2/2^r)$ bound. Our bound strictly improves the bound by Freitag et al., and is optimal for $ST^2\leq 2^c$. - For $B=2$, we give a considerably simpler and more modular proof, recovering the bound obtained by Freitag et al. - We obtain our bounds by adapting the recent multi-instance technique of Akshima, Guo and Liu (CRYPTO 2022) which bypasses the limitations of prior techniques in the Merkle-Damgård setting. To complement our results, we provably show that the recent multi-instance technique cannot further improve our bounds for $B=1,2$, and the general bound by Correti et al., for $B\geq 3$.

Overall, our results yield state-of-the-art security bounds for finding short collisions and fully characterize the power of the multi-instance technique in the sponge setting.