International Association
for Cryptologic Research

Abstract Homomorphic encryption () protects data in-use, but can be computationally expensive. To avoid the costly bootstrapping procedure that refreshes ciphertexts, some works have explored client-aided outsourcing protocols, where the client intermittently refreshes ciphertexts for a server that is performing homomorphic computations. But is this approach secure against malicious servers? We present a -secure encryption scheme that is completely insecure in this setting. We define a new notion of security, called , that we prove is sufficient. Additionally, we show: Homomorphic encryption schemes that have a certain type of circuit privacy—for example, schemes in which ciphertexts can be “sanitized"—are -secure. In particular, assuming certain existing schemes are -secure, they are also -secure. For certain encryption schemes, like Brakerski-Vaikuntanathan, that have a property that we call oblivious secret key extraction, -security implies circular security—i.e., that it is secure to provide an encryption of the secret key in a form usable for bootstrapping (to construct fully homomorphic encryption).

Abstract Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we make significant progress in closing this gap by proposing two new actively secure constant-round 2PC protocols, one with one-way communication of $$2\kappa +5$$ 2 κ + 5 bits per AND gate (for $$\kappa $$ κ -bit computational security and any statistical security) and one with total communication of $$2\kappa +\rho +5$$ 2 κ + ρ + 5 bits per AND gate (for $$\rho $$ ρ -bit statistical security). In particular, our first protocol essentially matches the one-way communication of semi-honest half-gates protocol. Our optimization is achieved by three new techniques: The recent compression technique by Dittmer et al. (Crypto 13510:57–87, 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from $$5\rho +1$$ 5 ρ + 1 bits to 2 bits per AND gate for $$\rho $$ ρ -bit statistical security. Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $$2\kappa +3\rho $$ 2 κ + 3 ρ bits per AND gate. We designed a new authenticated garbling that does not use information-theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size $$2\kappa +1$$ 2 κ + 1 bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of $$2\kappa +5$$ 2 κ + 5 bits per AND gate. In terms of total communication, we notice that the communication overhead of the consistency checking method by Dittmer et al. (Crypto 13510:57–87, 2022) can be optimized by adding one-round of interaction and utilizing the Free-XOR property. This reduces the online communication from $$2\kappa +3\rho $$ 2 κ + 3 ρ bits down to $$2\kappa +\rho +1$$ 2 κ + ρ + 1 bits per AND gate. Combined with our first contribution, this yields total amortized communication of $$2\kappa +\rho +5$$ 2 κ + ρ + 5 bits.

Abstract We propose a generic compiler that can convert any zero-knowledge (ZK) proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art. By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for general circuits from $$\mathcal {O}(C^{3/4})$$ O ( C 3 / 4 ) to $$\mathcal {O}(C^{1/2})$$ O ( C 1 / 2 ) . Our implementation shows that for a circuit of size $$2^{27}$$ 2 27 , it achieves up to $$83.6\times $$ 83.6 × improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least $$70\%$$ 70 % faster in a 10Mbps network. Using the recent results on compressed $$\varSigma $$ Σ -protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with $$\mathcal {O}(C^{1/2})$$ O ( C 1 / 2 ) communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation. We improve the communication of a designated n-verifier zero-knowledge proof from $$\mathcal {O}(nC/B+n^2B^2)$$ O ( n C / B + n 2 B 2 ) to $$\mathcal {O}(nC/B+n^2)$$ O ( n C / B + n 2 ) . To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology.

The present article provides a novel hash function $${\mathcal {H}}$$ H to any elliptic curve of j -invariant $$\ne 0, 1728$$ ≠ 0 , 1728 over a finite field $${\mathbb {F}}_{\!q}$$ F q of large characteristic. The unique bottleneck of $${\mathcal {H}}$$ H consists of extracting a square root in $${\mathbb {F}}_{\!q}$$ F q as well as for most hash functions. However, $${\mathcal {H}}$$ H is designed in such a way that the root can be found by (Cipolla–Lehmer–)Müller’s algorithm in constant time. Violation of this security condition is known to be the only obstacle to applying the given algorithm in the cryptographic context. When the field $${\mathbb {F}}_{\!q}$$ F q is highly 2-adic and $$q \equiv 1 \ (\textrm{mod} \ 3)$$ q ≡ 1 ( mod 3 ) , the new batching technique is the state-of-the-art hashing solution except for some sporadic curves. Indeed, Müller’s algorithm costs $$\approx 2\log _2(q)$$ ≈ 2 log 2 ( q ) multiplications in $${\mathbb {F}}_{\!q}$$ F q . In turn, original Tonelli–Shanks’s square root algorithm and all of its subsequent modifications have the algebraic complexity $$\varTheta (\log (q) + g(\nu ))$$ Θ ( log ( q ) + g ( ν ) ) , where $$\nu $$ ν is the 2-adicity of $${\mathbb {F}}_{\!q}$$ F q and a function $$g(\nu ) \ne O(\nu )$$ g ( ν ) ≠ O ( ν ) . As an example, it is shown that Müller’s algorithm actually needs several times fewer multiplications in the field $${\mathbb {F}}_{\!q}$$ F q (whose $$\nu = 96$$ ν = 96 ) of the standardized curve NIST P-224.

Abstract This paper studies several building blocks needed for electronic voting in order to prepare for the post-quantum era. In particular, we present lattice-based constructions for a generic zero-knowledge (ZK) proof of ballot correctness, a ZK proof of ballot correctness applicable for the homomorphic tallying scenario, and a ZK proof to achieve cast-as-intended verification during the vote casting period. We implement and benchmark our ballot correctness proofs, giving concrete estimations comparing the performance of homomorphic tallying and mix-net based e-voting systems in case of our lattice-based constructions.

Abstract Constructing one-way functions from average-case hardness is a long-standing open problem. A positive result would exclude Pessiland (Impagliazzo ’95) and establish a highly desirable win–win situation: either (symmetric) cryptography exists unconditionally, or all $$\textsf{NP} $$ NP problems can be solved efficiently on the average. Motivated by the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win–win results of the following type: either there are fine-grained one-way functions (FGOWF), or non-trivial speedups can be obtained for all $$\textsf{NP} $$ NP problems on the average. FGOWFs only require a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter. We obtain three main results: Construction. We show that if there is an $$\textsf{NP} $$ NP language having a very strong form of average-case hardness, which we call block finding hardness, then FGOWF exist. We provide heuristic support for this very strong average-case hardness notion by showing that it holds for a random language. Then, we study whether weaker (and more natural) forms of average-case hardness could already suffice to obtain FGOWF and obtain two negative results: Separation I. We provide a strong oracle separation for the implication ( $$\exists $$ ∃ exponentially average-case hard $$\textsf{NP} $$ NP language $$\implies $$ ⇒ $$\exists $$ ∃ FGOWF). Separation II. We provide a second strong negative result for an even weaker candidate win–win result. Namely, we rule out a relativizing proof for the implication ( $$\exists $$ ∃ exponentially average-case $$\textsf{NP} $$ NP hard language whose hardness amplifies optimally through parallel repetitions $$\implies $$ ⇒ $$\exists $$ ∃ FGOWF). This separation forms the core technical contribution of our work.

Abstract Leakage-resilient cryptography aims to protect cryptographic primitives from so-called “side channel attacks” that exploit their physical implementation to learn their input or secret state. Starting from the works of Ishai, Sahai and Wagner (CRYPTO‘03) and Micali and Reyzin (TCC‘04), most works on leakage-resilient cryptography either focus on protecting general computations, such as circuits or multiparty computation protocols, or on specific non-interactive primitives such as storage, encryption, and signatures. This work focuses on leakage resilience for the middle ground, namely for distributed and interactive cryptographic primitives. Our main technical contribution is designing the first secret sharing scheme that is equivocal, resists adaptive probing of a constant fraction of bits from each share, while incurs only a constant blowup in share size. Equivocation is a strong leakage-resilience guarantee, recently introduced by Hazay et al. (ITC, 2021). Our construction is obtained via a general compiler which we introduce, that transforms any secret sharing scheme into an equivocal scheme against adaptive leakage. An attractive feature of our compiler is that it respects additive reconstruction; namely, if the original scheme has additive reconstruction, then the transformed scheme has linear reconstruction. We extend our compiler to a general paradigm for protecting distributed primitives against leakage and show its applicability to various primitives, including secret sharing, verifiable secret sharing, function secret sharing, distributed encryption and signatures, and distributed zero-knowledge proofs. For each of these primitives, our paradigm transforms any construction of the primitive into a scheme that resists adaptive party corruptions, as well as adaptive probing leakage of a constant fraction of bits in each share when the share is stored in memory (but not when it is used in computations). Moreover, the transformation incurs only a constant blowup in the share size and respects additive reconstruction—an important feature for several of these primitives, such as function secret sharing and distributed encryption.

The common approach in secure communication channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example, is the case with TLS or SSH. However, protocols like QUIC or DTLS which run over a non-reliable transport such as UDP, do not—and in fact cannot—close the connection if packets are lost or arrive in a different order. Those protocols instead have to carefully catch effects arising naturally in unreliable networks, usually by using a sliding-window technique where ciphertexts can be decrypted correctly as long as they are not misplaced too far. In order to be able to capture QUIC and the newest DTLS version 1.3, we introduce a generalized notion of robustness of cryptographic channels. This property can capture unreliable network behavior and guarantees that adversarial tampering cannot hinder ciphertexts that can be decrypted correctly from being accepted. We show that robustness is orthogonal to the common notion of integrity for channels, but together with integrity and chosen-plaintext security it provides a robust analog of chosen-ciphertext security of channels. In contrast to prior work, robustness allows us to study packet encryption in the record layer protocols of QUIC and of DTLS 1.3 and the novel sliding-window techniques both protocols employ. We show that both protocols achieve robust chosen-ciphertext security based on certain properties of their sliding-window techniques and the underlying AEAD schemes. Notably, the robustness needed in handling unreliable network messages requires both record layer protocols to tolerate repeated adversarial forgery attempts. This means we can only establish non-tight security bounds (in terms of AEAD integrity), a security degradation that was missed in earlier protocol drafts. Our bounds led the responsible IETF working groups to introduce concrete forgery limits for both protocols and the IRTF CFRG to consider AEAD usage limits more broadly.

We revisit the problem of finding B -block-long collisions in Merkle–Damgård Hash Functions in the auxiliary-input random oracle model, in which an attacker gets a piece of S -bit advice about the random oracle and makes T oracle queries. Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis, Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for $$2\le B\le T$$ 2 ≤ B ≤ T (with respect to a random salt). The attack achieves advantage $$\widetilde{\Omega }(STB/2^n+T^2/2^n)$$ Ω ~ ( S T B / 2 n + T 2 / 2 n ) where n is the output length of the random oracle. They conjectured that this attack is optimal. However, this so-called STB conjecture was only proved for $$B\approx T$$ B ≈ T and $$B=2$$ B = 2 . Very recently, Ghoshal and Komargodski (CRYPTO 2022) confirmed the STB conjecture for all constant values of B and provided an $$\widetilde{O}(S^4TB^2/2^n+T^2/2^n)$$ O ~ ( S 4 T B 2 / 2 n + T 2 / 2 n ) bound for all choices of B . In this work, we prove an $$\widetilde{O}((STB/2^n)\cdot \max \{1,ST^2/2^n\}+ T^2/2^n)$$ O ~ ( ( S T B / 2 n ) · max { 1 , S T 2 / 2 n } + T 2 / 2 n ) bound for every $$2< B < T$$ 2 < B < T . Our bound confirms the STB conjecture for $$ST^2\le 2^n$$ S T 2 ≤ 2 n and is optimal up to a factor of S for $$ST^2>2^n$$ S T 2 > 2 n (note as $$T^2$$ T 2 is always at most $$2^n$$ 2 n , otherwise finding a collision is trivial by the birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters except for $$B=\widetilde{O}(1)$$ B = O ~ ( 1 ) and $$ST^2>2^n$$ S T 2 > 2 n . We obtain our results by adopting and refining the technique of Chung, Guo, Liu and Qian (FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the limitations of prior techniques. Along the way, we obtain a considerably simpler and illuminating proof for $$B=2$$ B = 2 , recovering the main result of Akshima, Cash, Drucker and Wee.

Abstract Almost perfect nonlinear (in brief, APN) functions are vectorial functions $$F:{\mathbb {F}}_2^n\rightarrow {\mathbb {F}}_2^n$$ F : F 2 n → F 2 n playing roles in several domains of information protection, at the intersection of computer science and mathematics. Their definition comes from cryptography and is also related to coding theory. When they are used as substitution boxes (S-boxes, which are the only nonlinear components in block ciphers), APN functions contribute optimally to the resistance against differential attacks. This makes of course a strong cryptographic motivation for their study, which has been very active since the 90’s, and has posed interesting and difficult mathematical questions, some of which are still unanswered. Since the introduction of differential attacks, more recent types of cryptanalyses have been designed, such as integral attacks. No notion about S-boxes has been identified which would play a similar role with respect to integral attacks. In this paper, we study two generalizations of APNness that are natural from a mathematical point of view, since they directly extend classical characterizations of APN functions. We call these two notions strong non-normality and sum-freedom. The former existed already for Boolean functions (it had been introduced by Dobbertin), and the latter is new. We study how these two notions are related to cryptanalyses (the relation is weaker for strong non-normality). The two notions behave differently from each other, while they have similar definitions. They behave differently from differential uniformity, which is a well-known generalization of APNness. We study the different ways to define them. We prove their satisfiability, their monotonicity, and their invariance under classical equivalence relations, and we characterize them by the Walsh transform. We finally begin a study of the multiplicative inverse function (used as a substitution box in the Advanced Encryption Standard and other block ciphers) from the viewpoint of these two notions. In particular, we find a simple expression of the sum of the values taken by this function over affine subspaces of $$\mathbb F_{2^n}$$ F 2 n that are not vector subspaces. This formula shows that the sum never vanishes on such affine spaces. We also give a formula for the case of a vector space defined by one of its bases.