International Association
for Cryptologic Research

We show a general compiler that transforms a large class of erroneous cryptographic schemes (such as public-key encryption, indistinguishability obfuscation, and secure multiparty computation schemes) into perfectly correct ones. The transformation works for schemes that are correct on all inputs with probability noticeably larger than half , and are secure under parallel repetition. We assume the existence of one-way functions and of functions with deterministic (uniform) time complexity $$2^{O(n)}$$ 2 O ( n ) and non-deterministic circuit complexity $$2^{\Omega (n)}$$ 2 Ω ( n ) . Our transformation complements previous results that showed how public-key encryption and indistinguishability obfuscation that err on a noticeable fraction of inputs can be turned into ones that for all inputs are often correct, showing that they can be made perfectly correct. The technique relies on the idea of “reverse randomization” [Naor, Crypto 1989] and on Nisan–Wigderson style derandomization, previously used in cryptography to remove interaction from witness-indistinguishable proofs and commitment schemes [Barak, Ong and Vadhan, Crypto 2003].

The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt’19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited. In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior works on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol based on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong (or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to progressively strengthen it using ring signatures and/or non-interactive zero-knowledge proof systems. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available.

In this paper, we use genus theory to analyze the hardness of the decisional Diffie–Hellman problem for ideal class groups of imaginary quadratic orders acting on sets of elliptic curves through isogenies (DDH–CGA). Such actions are used in the Couveignes–Rostovtsev–Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order $$\mathcal {O}$$ O with a set of assigned characters $$\chi : {\text {cl}}(\mathcal {O}) \rightarrow \{ \pm 1\}$$ χ : cl ( O ) → { ± 1 } , and for each such character and every secret ideal class $$[\mathfrak {a}]$$ [ a ] connecting two public elliptic curves E and $$E' = [\mathfrak {a}] \star E$$ E ′ = [ a ] ⋆ E , we show how to compute $$\chi ([\mathfrak {a}])$$ χ ( [ a ] ) given only E and $$E'$$ E ′ , i.e., without knowledge of $$[\mathfrak {a}]$$ [ a ] . In practice, this breaks DDH–CGA as soon as the class number is even, which is true for a density 1 subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over $$\mathbb {F}_p$$ F p with $$p \equiv 1 \bmod 4$$ p ≡ 1 mod 4 . Our method relies on computing Tate pairings and walking down isogeny volcanoes. We also show that these ideas carry over, at least partly, to abelian varieties of arbitrary dimension. This is an extended version of the paper that was presented at Crypto 2020.

We study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, we aim at finding a unified approach and some additional requirement to realize IND-CCA secure PKE and TDF based on IND-CPA secure PKE, and show the following two main results. As the first main result, we show how to achieve IND-CCA security via a weak form of key-dependent-message (KDM) security. More specifically, we construct an IND-CCA secure PKE scheme based on an IND-CPA secure PKE scheme and a secret-key encryption (SKE) scheme satisfying one-time KDM security with respect to projection functions (projection-KDM security). Projection functions are elementary functions with respect to which KDM security has been widely studied. Since the existence of projection-KDM secure PKE implies that of the above two building blocks, as a corollary of this result, we see that the existence of IND-CCA secure PKE is implied by that of projection-KDM secure PKE. As the second main result, we extend the above construction of IND-CCA secure PKE into that of TDF by additionally requiring a mild requirement for each building block. Our TDF satisfies adaptive one-wayness. We can instantiate our TDF based on a wide variety of computational assumptions. Especially, we obtain the first TDF (with adaptive one-wayness) based on the sub-exponential hardness of the constant-noise learning-parity-with-noise (LPN) problem. In addition, we show that by extending the above constructions, we can obtain PKE schemes satisfying advanced security notions under CCA, that is, optimal rate leakage-resilience under CCA and selective-opening security under CCA. As a result, we obtain the first PKE schemes satisfying these security notions based on the computational Diffie–Hellman (CDH) assumption or the low-noise LPN assumption.

In this paper, we present a constant-round leakage-resilient zero-knowledge argument system for $$\mathcal {NP}$$ NP under the assumption of the existence of collision-resistant hash function families. That is, using a collision-resistant hash function, we construct a constant-round zero-knowledge argument system that has the following zero-knowledge property: even against any cheating verifier that obtains an arbitrary amount of leakage on the prover’s internal secret state, a simulator can simulate the verifier’s view by obtaining the same amount of leakage on the witness. Previously, leakage-resilient zero-knowledge proofs/arguments for $$\mathcal {NP}$$ NP were constructed only under a relaxed security definition (Garg et al., in: CRYPTO’11, pp 297–315, 2011) or under the DDH assumption (Pandey, in: TCC’14, pp 146–166, 2014). Our leakage-resilient zero-knowledge argument system satisfies an additional property that it is simultaneously leakage-resilient zero-knowledge, meaning that both zero-knowledge and soundness hold in the presence of leakage.

We consider the problem of constructing leakage-resilient circuit compilers that are secure against global leakage functions with bounded output length. By global, we mean that the leakage can depend on all circuit wires and output a low-complexity function (represented as a multi-output Boolean circuit) applied on these wires. In this work, we design compilers both in the stateless (a.k.a. single-shot leakage) setting and the stateful (a.k.a. continuous leakage) setting that are unconditionally secure against $$\mathsf {AC}^0$$ AC 0 leakage and similar low-complexity classes. In the stateless case, we show that the original private circuits construction of Ishai, Sahai, and Wagner (Crypto 2003) is actually secure against $${\mathsf {AC}}^{0}$$ AC 0 leakage. In the stateful case, we modify the construction of Rothblum (Crypto 2012), obtaining a simple construction with unconditional security. Prior works that designed leakage-resilient circuit compilers against $$\mathsf {AC}^0$$ AC 0 leakage had to rely either on secure hardware components (Faust et al., Eurocrypt 2010, Miles-Viola, STOC 2013) or on (unproven) complexity-theoretic assumptions (Rothblum, Crypto 2012).

Secure computation enables n mutually distrustful parties to compute a function over their private inputs jointly. In 1988, Ben-Or, Goldwasser, and Wigderson (BGW) proved that any function can be computed with perfect security in the presence of a malicious adversary corrupting at most $$t< n/3$$ t < n / 3 parties. After more than 30 years, protocols with perfect malicious security, and round complexity proportional to the circuit’s depth, still require (verifiably) sharing a total of $$O(n^2)$$ O ( n 2 ) values per multiplication. In contrast, only O ( n ) values need to be shared per multiplication to achieve semi-honest security. Sharing $$\Omega (n)$$ Ω ( n ) values for a single multiplication seems to be the natural barrier for polynomial secret-sharing-based multiplication. In this paper, we construct a new secure computation protocol with perfect, optimal resilience and malicious security that incurs (verifiably) sharing O ( n ) values per multiplication. Our protocol requires a constant number of rounds per multiplication. Like BGW, it has an overall round complexity that is proportional only to the multiplicative depth of the circuit. Our improvement is obtained by a novel construction for weak VSS for polynomials of degree 2t , which incurs the same communication and round complexities as the state-of-the-art constructions for VSS for polynomials of degree t . Our second contribution is a method for reducing the communication complexity for any depth 1 sub-circuit to be proportional only to the size of the input and output (rather than the size of the circuit). This implies protocols with sub-linear communication complexity (in the size of the circuit) for perfectly secure computation for important functions like matrix multiplication.

Everlasting security models the setting where hardness assumptions hold during the execution of a protocol but may get broken in the future. Due to the strength of this adversarial model, achieving any meaningful security guarantees for composable protocols is impossible without relying on hardware assumptions (Müller-Quade and Unruh, JoC’10). For this reason, a rich line of research has tried to leverage physical assumptions to construct well-known everlasting cryptographic primitives, such as commitment schemes. The only known everlastingly UC secure commitment scheme, due to Müller-Quade and Unruh (JoC’10), assumes honestly generated hardware tokens. The authors leave the possibility of constructing everlastingly UC secure commitments from malicious hardware tokens as an open problem. Goyal et al. (Crypto’10) constructs unconditionally UC-secure commitments and secure computation from malicious hardware tokens, with the caveat that the honest tokens must encapsulate other tokens. This extra restriction rules out interesting classes of hardware tokens, such as physically uncloneable functions (PUFs). In this work, we present the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token model without requiring honest token encapsulation. Our scheme assumes the existence of PUFs and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-secure computation from non-erasable tokens (such as PUFs), even with trusted setup.

We present several improvements to the framework of differential-linear attacks with a special focus on ARX ciphers. As a demonstration of their impact, we apply them to Chaskey and ChaCha and we are able to significantly improve upon the best attacks published so far.

Oblivious RAMs, introduced by Goldreich and Ostrovsky [JACM’96], compile any RAM program into one that is “memory oblivious,” i.e., the access pattern to the memory is independent of the input. All previous ORAM schemes, however, completely break the locality of data accesses (for instance, by shuffling the data to pseudorandom positions in memory). In this work, we initiate the study of locality-preserving ORAMs —ORAMs that preserve locality of the accessed memory regions, while leaking only the lengths of contiguous memory regions accessed. Our main results demonstrate the existence of a locality-preserving ORAM with polylogarithmic overhead both in terms of bandwidth and locality. We also study the trade-off between locality, bandwidth and leakage, and show that any scheme that preserves locality and does not leak the lengths of the contiguous memory regions accessed, suffers from prohibitive bandwidth. To further improve the parameters, we also consider a weaker notion of a File ORAM, which supports accesses to predefined non-overlapping regions. Assuming one-way functions, we present a computationally secure File ORAM that has a work overhead and locality of roughly $$O(\log ^2 N)$$ O ( log 2 N ) , while ignoring $$\log \log N$$ log log N factors. To the best of our knowledge, before our work, the only works combining locality and obliviousness were for symmetric searchable encryption [e.g., Cash and Tessaro (EUROCRYPT’14), Asharov et al. (STOC’16)]. Symmetric search encryption ensures obliviousness if each keyword is searched only once, whereas ORAM provides obliviousness to any input program. Thus, our work generalizes that line of work to the much more challenging task of preserving locality in ORAMs.

Algebraic structure lies at the heart of much of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives: One-Way Function (OWF) Weak Unpredictable Function (wUF) Weak Pseudorandom Function (wPRF) The algebraic structure that we consider is group homomorphism over the input/output spaces of these primitives. We also consider a “bounded” notion of homomorphism where the primitive only supports an a priori bounded number of homomorphic operations in order to capture lattice-based and other “noisy” assumptions. We show that these structured primitives can be used to construct many cryptographic protocols. In particular, we prove that: (Bounded) Homomorphic OWFs  (HOWFs) imply collision-resistant hash functions, Schnorr-style signatures and chameleon hash functions. (Bounded) Input-Homomorphic weak UFs  (IHwUFs) imply CPA-secure PKE, non-interactive key exchange, trapdoor functions, blind batch encryption (which implies anonymous IBE, KDM-secure and leakage-resilient PKE), CCA2 deterministic PKE, and hinting PRGs (which in turn imply transformation of CPA to CCA security for ABE/1-sided PE). (Bounded) Input-Homomorphic weak PRFs  (IHwPRFs) imply PIR, lossy trapdoor functions, OT and MPC (in the plain model). In addition, we show how to realize any CDH/DDH-based protocol with certain properties in a generic manner using IHwUFs/IHwPRFs, and how to instantiate such a protocol from many concrete assumptions. We also consider primitives with substantially richer structure, namely Ring IHwPRFs and L-composable IHwPRFs . In particular, we show the following: Ring IHwPRFs with certain properties imply FHE. 2-composable IHwPRFs imply (black-box) IBE, and L -composable IHwPRFs imply non-interactive $$(L+1)$$ ( L + 1 ) -party key exchange. Our framework allows us to categorize many cryptographic protocols based on which structured Minicrypt primitive implies them. In addition, it potentially makes showing the existence of many cryptosystems from novel assumptions substantially easier in the future.

We present a new multiparty protocol for the distributed generation of biprime RSA moduli, with security against any subset of maliciously colluding parties assuming oblivious transfer and the hardness of factoring. Our protocol is highly modular, and its uppermost layer can be viewed as a template that generalizes the structure of prior works and leads to a simpler security proof. We introduce a combined sampling-and-sieving technique that eliminates both the inherent leakage in the approach of Frederiksen et al. (Crypto’18) and the dependence upon additively homomorphic encryption in the approach of Hazay et al. (JCrypt’19). We combine this technique with an efficient, privacy-free check to detect malicious behavior retroactively when a sampled candidate is not a biprime and thereby overcome covert rejection-sampling attacks and achieve both asymptotic and concrete efficiency improvements over the previous state of the art.

The Learning with Errors (LWE) problem is the fundamental backbone of modern lattice-based cryptography, allowing one to establish cryptography on the hardness of well-studied computational problems. However, schemes based on LWE are often impractical, so Ring LWE was introduced as a form of ‘structured’ LWE, trading off a hard to quantify loss of security for an increase in efficiency by working over a well-chosen ring. Another popular variant, Module LWE, generalizes this exchange by implementing a module structure over a ring. In this work, we introduce a novel variant of LWE over cyclic algebras (CLWE) to replicate the addition of the ring structure taking LWE to Ring LWE by adding cyclic structure to Module LWE. We show that the security reductions expected for an LWE problem hold, namely a reduction from certain structured lattice problems to the hardness of the decision variant of the CLWE problem (under the condition of constant rank d ). As a contribution of theoretic interest, we view CLWE as the first variant of Ring LWE which supports non-commutative multiplication operations. This ring structure compares favorably with Module LWE, and naturally allows a larger message space for error correction coding.

We formally study “non-malleable functions” (NMFs), a general cryptographic primitive which simplifies and relaxes “non-malleable one-way/hash functions” (NMOWHFs) introduced by Boldyreva et al. (in: Advances in cryptology—ASIACRYPT 2009, pp 524–541, 2009) and refined by Baecher et al. (in: CT-RSA 2011, pp 268–283, 2011). NMFs focus on basic functions, rather than one-way/hash functions considered in the literature of NMOWHFs. We formalize a game-based definition for NMFs. Roughly, a function f is non-malleable if given an image $$y^* \leftarrow f(x^*)$$ y ∗ ← f ( x ∗ ) for a randomly chosen $$x^*$$ x ∗ , it is hard to output a value y together with a transformation $$\phi $$ ϕ from some prefixed transformation class such that y is an image of $$\phi (x^*)$$ ϕ ( x ∗ ) under f . Our non-malleable notion is strong in the sense that only trivial copy solution $$(\mathsf {id}, y^*)$$ ( id , y ∗ ) is forbidden, where $$\mathsf {id}$$ id is the identity transformation. We also consider the adaptive notion, which stipulates that non-malleability holds even when an inversion oracle is available. We investigate the relations between non-malleability and one-wayness in depth. In the non-adaptive setting, we show that non-malleability generally implies one-wayness for poly-to-one functions but not vice versa. In the adaptive setting, we show that for most algebra-induced transformation classes, adaptive non-malleability (ANM) is equivalent to adaptive one-wayness (AOW) for injective functions. These results establish theoretical connections between non-malleability and one-wayness for functions and extend to trapdoor functions as well, resolving the open problems left by Kiltz et al. (in: Advances in cryptology—EUROCRYPT 2010, pp 673–692, 2010). We also study the relations between standard OW/NM and hinting OW/NM, where the latter notions are typically more useful in practice. Toward efficient realizations of NMFs, we give a deterministic construction from adaptive trapdoor functions as well as a randomized construction from all-but-one lossy functions and one-time signature. This partially solves an open problem posed by Boldyreva et al. (in: Advances in cryptology—ASIACRYPT 2009, pp 524–541, 2009). Finally, we explore applications of NMFs in security against related-key attacks (RKA). We first show that, somewhat surprisingly, the implication AOW $$\Rightarrow $$ ⇒ ANM sheds light on addressing non-trivial copy attacks in RKA security. We then show that NMFs give rise to a generic construction of RKA-secure authenticated key derivation functions, which have proven to be very useful in achieving RKA security for numerous cryptographic primitives. Particularly, our construction simplifies and unifies the result due to Qin et al. (in: Public-key cryptography—PKC 2015, volume 9020 of LNCS. Springer, Berlin, pp 557–578, 2015).

We show that indistinguishability obfuscation (IO) for all circuits can be constructed solely from secret-key functional encryption (SKFE). In the construction, SKFE needs to be secure against an unbounded number of functional key queries, that is, collusion-resistant. Our strategy is to replace public-key functional encryption (PKFE) in the construction of IO proposed by Bitansky and Vaikuntanathan (FOCS 2015) with puncturable SKFE . Bitansky and Vaikuntanathan introduced the notion of puncturable SKFE and observed that the strategy works. However, it has not been clear whether we can construct puncturable SKFE without assuming PKFE. In particular, it has not been known whether puncturable SKFE can be constructed from standard SKFE. In this work, we show that a relaxed variant of puncturable SKFE can be constructed from collusion-resistant SKFE. Moreover, we show that the relaxed variant of puncturable SKFE is sufficient for constructing IO. Ananth and Jain (CRYPTO 2015) also proposed an IO construction from PKFE. However, their strategy is different from that of Biransky and Vaikuntanathan. In addition, we also study the relation of collusion-resistance and succinctness for SKFE. Functional encryption is said to be weakly succinct if the size of its encryption circuit is sub-linear in the size of functions. We show that collusion-resistant SKFE can be constructed from weakly succinct SKFE supporting only one functional key. By combining the above two results, we show that IO for all circuits can be constructed from weakly succinct SKFE supporting only one functional key.

We present an algorithm solving the ROS ( R andom inhomogeneities in a O verdetermined S olvable system of linear equations) problem mod p in polynomial time for $$\ell > \log p$$ ℓ > log p dimensions. Our algorithm can be combined with Wagner’s attack, and leads to a sub-exponential solution for any dimension $$\ell $$ ℓ with the best complexity known so far. When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto–Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe–Okamoto, and conditional blind signatures such as ZGP17. Schemes for e-cash (such as Brands’ signature) and anonymous credentials (such as Anonymous Credentials Light) inspired from the above are also affected.

Indistinguishability obfuscation has become one of the most exciting cryptographic primitives due to its far-reaching applications in cryptography and other fields. However, to date, obtaining a plausibly secure construction has been an illusive task, thus motivating the study of seemingly weaker primitives that imply it, with the possibility that they will be easier to construct. In this work, we provide a systematic study of compressing obfuscation, one of the most natural and simple to describe primitives that is known to imply indistinguishability obfuscation when combined with other standard assumptions. A compressing obfuscator is roughly an indistinguishability obfuscator that outputs just a slightly compressed encoding of the truth table. This generalizes notions introduced by Lin et al. (Functional signatures and pseudorandom functions, PKC, 2016) and Bitansky et al. (From Cryptomania to Obfustopia through secret-key functional encryption, TCC, 2016) by allowing for a broader regime of parameters. We view compressing obfuscation as an independent cryptographic primitive and show various positive and negative results concerning its power and plausibility of existence, demonstrating significant differences from full-fledged indistinguishability obfuscation. First, we show that as a cryptographic building block, compressing obfuscation is weak. In particular, when combined with one-way functions, it cannot be used (in a black-box way) to achieve public-key encryption, even under (sub-)exponential security assumptions. This is in sharp contrast to indistinguishability obfuscation, which together with one-way functions implies almost all cryptographic primitives. Second, we show that to construct compressing obfuscation with perfect correctness, one only needs to assume its existence with a very weak correctness guarantee and polynomial hardness. Namely, we show a correctness amplification transformation with optimal parameters that relies only on polynomial hardness assumptions. This implies a universal construction assuming only polynomially secure compressing obfuscation with approximate correctness. In the context of indistinguishability obfuscation, we know how to achieve such a result only under sub-exponential security assumptions together with derandomization assumptions. Lastly, we characterize the existence of compressing obfuscation with statistical security. We show that in some range of parameters and for some classes of circuits such an obfuscator exists , whereas it is unlikely to exist with better parameters or for larger classes of circuits. These positive and negative results reveal a deep connection between compressing obfuscation and various concepts in complexity theory and learning theory.

The Module Learning With Errors  ( $$\text {M-LWE}$$ M-LWE ) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of  $$\text {M-LWE}$$ M-LWE , i.e., uniform secret modulo  q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that  $$\text {M-LWE}$$ M-LWE with uniform  $$\eta $$ η -bounded secret for any  $$1 \le \eta \ll q$$ 1 ≤ η ≪ q and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of  $$\text {M-LWE}$$ M-LWE , provided that the module rank  d is at least logarithmic in the ring degree  n . We also prove that the search version of  $$\text {M-LWE}$$ M-LWE with large uniform secret and uniform  $$\eta $$ η -bounded error is at least as hard as the standard  $$\text {M-LWE}$$ M-LWE problem, if the number of samples  m is close to the module rank  d and with further restrictions on  $$\eta $$ η . The latter result can be extended to provide the hardness of search  $$\text {M-LWE}$$ M-LWE with uniform  $$\eta $$ η -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.

We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that: 1. BA protocols resilient against n /3 [resp., n /4] corruptions terminate (under attack) at the end of the first round with probability at most o (1) [resp., $$1/2+ o(1)$$ 1 / 2 + o ( 1 ) ]. 2. BA protocols resilient against a fraction of corruptions greater than 1/4 terminate at the end of the second round with probability at most $$1-\Theta (1)$$ 1 - Θ ( 1 ) . 3. For a large class of protocols (including all BA protocols used in practice) and under a plausible combinatorial conjecture, BA protocols resilient against a fraction of corruptions greater than 1/3 [resp., 1/4] terminate at the end of the second round with probability at most o (1) [resp., $$1/2 + o(1)$$ 1 / 2 + o ( 1 ) ]. The above bounds hold even when the parties use a trusted setup phase, e.g., a public-key infrastructure (PKI). The third bound essentially matches the recent protocol of Micali (ITCS’17) that tolerates up to n /3 corruptions and terminates at the end of the third round with constant probability.

The differential-linear attack, combining the power of the two most effective techniques for symmetric-key cryptanalysis, was proposed by Langford and Hellman at CRYPTO 1994. From the exact formula for evaluating the bias of a differential-linear distinguisher (JoC 2017), to the differential-linear connectivity table technique for dealing with the dependencies in the switch between the differential and linear parts (EUROCRYPT 2019), and to the improvements in the context of cryptanalysis of ARX primitives (CRYPTO 2020, EUROCRYPT 2021), we have seen significant development of the differential-linear attack during the last four years. In this work, we further extend this framework by replacing the differential part of the attack by rotational-XOR differentials. Along the way, we establish the theoretical link between the rotational-XOR differential and linear approximations and derive the closed formula for the bias of rotational differential-linear distinguishers, completely generalizing the results on ordinary differential-linear distinguishers due to Blondeau, Leander, and Nyberg (JoC 2017) to the case of rotational differential-linear cryptanalysis. We then revisit the rotational cryptanalysis from the perspective of differential-linear cryptanalysis and generalize Morawiecki et al.’s technique for analyzing Keccak , which leads to a practical method for estimating the bias of a (rotational) differential-linear distinguisher in the special case where the output linear mask is a unit vector. Finally, we apply the rotational differential-linear technique to the cryptographic permutations involved in FRIET , Xoodoo , Alzette , and SipHash . This gives significant improvements over existing cryptanalytic results, or offers explanations for previous experimental distinguishers without a theoretical foundation. To confirm the validity of our analysis, all distinguishers with practical complexities are verified experimentally. Moreover, we discuss the possibility of applying the rotational differential-linear technique to S-box-based designs or keyed primitives, and propose some open problems for future research.

Quantum money allows a bank to mint quantum money states that can later be verified and cannot be forged. Usually, this requires a quantum communication infrastructure to perform transactions. Gavinsky (CCC 2012) introduced the notion of classically verifiable quantum money, which allows verification through classical communication. In this work, we introduce the notion of classical minting and combine it with classical verification to introduce semi-quantum money. Semi-quantum money is the first type of quantum money to allow transactions with completely classical communication and an entirely classical bank. This work features constructions for both a public memory-dependent semi-quantum money scheme and a private memoryless semi-quantum money scheme. The public construction is based on the works of Zhandry  and Coladangelo, and the private construction is based on the notion of noisy trapdoor claw-free functions (NTCF) introduced by Brakerski et al. (FOCS 2018). In terms of technique, our main contribution is a perfect parallel repetition theorem for NTCF.

We propose the first tight security proof for the ordinary two-message signed Diffie–Hellman key exchange protocol in the random oracle model. Our proof is based on the strong computational Diffie–Hellman assumption and the multiuser security of a digital signature scheme. With our security proof, the signed DH protocol can be deployed with optimal parameters, independent of the number of users or sessions, without the need to compensate any security loss. We abstract our approach with a new notion called verifiable key exchange. In contrast to a known tight three-message variant of the signed Diffie–Hellman protocol (Gjøsteen and Jager, in: Shacham, Boldyreva (eds) CRYPTO 2018, Part II. LNCS, Springer, Heidelberg, 2018), we do not require any modification to the original protocol, and our tightness result is proven in the “Single-Bit-Guess” model which we know can be tightly composed with symmetric cryptographic primitives to establish a secure channel. Finally, we extend our approach to the group setting and construct the first tightly secure group authenticated key exchange protocol.

Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O (1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have “escaped the hegemony” of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing $$\text{ SNARG } $$ SNARG s, as well as resulting new efficiency features. Our contribution is threefold: (1) We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded “adversaries” in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional “unstructured” PCPs. (2) We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques. (3) Following this methodology, we exhibit several constructions achieving new efficiency features, such as “single-ciphertext preprocessing SNARGs.” We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.

Rasta and Dasta are two fully homomorphic encryption friendly symmetric-key primitives proposed at CRYPTO 2018 and ToSC 2020, respectively. It can be found from the designers’ analysis that the security of the two ciphers highly relies on the high algebraic degree of the inverse of the n -bit $$\chi $$ χ operation denoted by $$\chi _n^{-1}$$ χ n - 1 , while surprisingly the explicit formula of $$\chi _n^{-1}$$ χ n - 1 has never been given in the literature. As the first contribution, for the first time, we give a very simple formula of $$\chi _n^{-1}$$ χ n - 1 that can be written down in only one line and we prove its correctness in a rigorous way. Based on this formula of $$\chi _n^{-1}$$ χ n - 1 , an obvious yet important weakness of the two ciphers can be identified, which shows that their security against the algebraic attack cannot be solely based on the high degree of $$\chi _n^{-1}$$ χ n - 1 . Specifically, this weakness enables us to theoretically break two out of three instances of full Agrasta, which is the aggressive version of Rasta with the block size only slightly larger than the security level in bits. We further reveal that Dasta is more vulnerable against our attacks than Rasta because of its usage of a linear layer composed of an ever-changing bit permutation and a deterministic linear transform. Based on our cryptanalysis, the security margins of Dasta and Rasta parameterized with $$(n,\kappa ,r)\in \{(327,80,4),(1877,128,4),(3545,256,5)\}$$ ( n , κ , r ) ∈ { ( 327 , 80 , 4 ) , ( 1877 , 128 , 4 ) , ( 3545 , 256 , 5 ) } are reduced to only 1 round, where n , $$\kappa $$ κ and r denote the block size, the claimed security level and the number of rounds, respectively. These parameters are of particular interest as the corresponding ANDdepth is the lowest among those that can be implemented in reasonable time and target the same claimed security level.

We present a new approach to designing concretely efficient MPC protocols with semi-honest security in the dishonest majority setting. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols does not depend on the number of honest parties , we investigate how to construct protocols which improve in efficiency as the number of honest parties increases. Our central idea is to take a protocol which is secure for $$n-1$$ n - 1 corruptions and modify it to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties’ keys. This results in a more efficient protocol tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption. We first apply this technique to a modified version of the semi-honest GMW protocol, using OT extension with short keys, to improve the efficiency of standard GMW with fewer corruptions. We also obtain more efficient constant-round MPC, using BMR-style garbled circuits with short keys, and present an implementation of the online phase of this protocol. Our techniques start to improve upon existing protocols when there are around $$n=10$$ n = 10 parties with $$h=4$$ h = 4 honest parties, and as these increase we obtain up to a 13 times reduction (for $$n=400,h=120$$ n = 400 , h = 120 ) in communication complexity for our GMW variant, compared with the best-known GMW-based protocol modified to use the same threshold.

Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures; however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signature schemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs. In this paper, we construct several lattice-based distributed signing protocols with low round complexity following the Fiat–Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message—which can inevitably happen in the Fiat–Shamir with Aborts setting. We manage to do so using homomorphic commitments. Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.’s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round n -out-of- n distributed signing and multi-signature in the plain public key model , by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.

Zero-Knowledge PCPs (ZK-PCPs; Kilian, Petrank, and Tardos, STOC ‘97) are PCPs with the additional zero-knowledge guarantee that the view of any (possibly malicious) verifier making a bounded number of queries to the proof can be efficiently simulated up to a small statistical distance. Similarly, ZK-PCPs of Proximity (ZK-PCPPs; Ishai and Weiss, TCC ‘14) are PCPPs in which the view of an adversarial verifier can be efficiently simulated with few queries to the input. Previous ZK-PCP constructions obtained an exponential gap between the query complexity q of the honest verifier, and the bound $$q^*$$ q ∗ on the queries of a malicious verifier (i.e., $$q={\mathsf {poly}}\log \left( q^*\right) $$ q = poly log q ∗ ), but required either exponential-time simulation, or adaptive honest verification. This should be contrasted with standard PCPs, that can be verified non-adaptively (i.e., with a single round of queries to the proof). The problem of constructing such ZK-PCPs, even when $$q^*=q$$ q ∗ = q , has remained open since they were first introduced more than 2 decades ago. This question is also open for ZK-PCPPs, for which no construction with non-adaptive honest verification is known (not even with exponential-time simulation). We resolve this question by constructing the first ZK-PCPs and ZK-PCPPs which simultaneously achieve efficient zero-knowledge simulation and non-adaptive honest verification. Our schemes have a square-root query gap, namely $$q^*/q=O\left( \sqrt{n}\right) $$ q ∗ / q = O n , where n is the input length. Our constructions combine the “MPC-in-the-head” technique (Ishai et al., STOC ‘07) with leakage-resilient secret sharing. Specifically, we use the MPC-in-the-head technique to construct a ZK-PCP variant over a large alphabet, then employ leakage-resilient secret sharing to design a new alphabet reduction for ZK-PCPs which preserves zero-knowledge.