International Association
for Cryptologic Research

Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson (JACM'91), zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments. In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action (Eurocrypt’22). We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We consider three representations: arithmetic circuits, rank-1 constraint systems and branching programs. This work gives the first attempt at constructing a post-quantum generic proof system from isogeny assumptions (the group action DDH problem). Though the resulting proof systems are linear in the circuit size, they possess interesting features such as non-interactivity, statistical zero-knowledge, and online-extractability.

In 2012, Ding, Xie and Lin designed a key exchange protocol based on Ring-LWE problem, called the DXL key exchange protocol, which can be seen as an extended version of the Diffie-Hellman key exchange. In this protocol, Ding et al. achieved key exchange between the communicating parties according to the associativity of matrix multiplications, that is, $(x^T\cdot A)\cdot y = x^T\cdot (A\cdot y)$, where $x,y$ are column vectors and $A$ is a square matrix. However, the DXL key exchange protocol cannot resist key reuse attacks. At ESORICS 2022, Qin et al. proposed a method that an adversary can recover the reused private key after forging the public keys for several times. Nevertheless, Qin et al.'s method leads to a lot of redundant operations. In this paper, we improve Qin et al.'s method to a more general case and propose an effective approach to combine signal leakage attacks with depth first search. Compared with state-of-the-art result appeared at ESORICS 2022, the number of reused private key have been decreased from 29 to 10. In other words, if the number of reuses exceeds 10, the private key will be restored. Moreover, we validate the effectiveness of the results through experiments.

The Boolean map $\chi_n \colon \mathbb{F}_2^n \to \mathbb{F}_2^n,\ x \mapsto y$ defined by $y_i = x_i + (x_{i+1}+1)x_{i+2}$ (where $i\in \mathbb{Z}/n\mathbb{Z}$) is used in various permutations that are part of cryptographic schemes, e.g., Keccak-f (the SHA-3-permutation), ASCON (the winner of the NIST Lightweight competition), Xoodoo, Rasta and Subterranean (2.0). In this paper, we study various algebraic properties of this map. We consider $\chi_n$ (through vectorial isomorphism) as a univariate polynomial. We show that it is a power function if and only if $n=1,3$. We furthermore compute bounds on the sparsity and degree of these univariate polynomials, and the number of different univariate representations. Secondly, we compute the number of monomials of given degree in the inverse of $\chi_n$ (if it exists). This number coincides with binomial coefficients. Lastly, we consider $\chi_n$ as a polynomial map, to study whether the same rule ($y_i = x_i + (x_{i+1}+1)x_{i+2}$) gives a bijection on field extensions of $\mathbb{F}_2$. We show that this is not the case for extensions whose degree is divisible by two or three. Based on these results, we conjecture that this rule does not give a bijection on any extension field of $\mathbb{F}_2$.

Several key exchange protocols based on tropical circulant matrices were proposed in the last two years. In this paper, we show that protocols offered by M. Durcheva [M. I. Durcheva. TrES: Tropical Encryption Scheme Based on Double Key Exchange. In: Eur. J. Inf. Tech. Comp. Sci. 2.4 (2022), pp. 11–17], by B. Amutha and R. Perumal [B. Amutha and R. Perumal. Public key exchange protocols based on tropical lower circulant and anti-circulant matrices. In: AIMS Math. 8.7 (2023), pp. 17307–17334.], and by H. Huang, C. Li, and L. Deng [H. Huang, C. Li, and L. Deng. Public-Key Cryptography Based on Tropical Circular Matrices. In: Appl. Sci. 12.15 (2022), p. 7401] are insecure.

Private Set Intersection Cardinality(PSI-CA) is a type of secure two-party computation. It enables two parties, each holding a private set, to jointly compute the cardinality of their intersection without revealing any other private information about their respective sets.

In this paper, we manage to break two PSI-CA protocols by recovering the specific intersection items in polynomial time. Among them, the PSI-CA protocol proposed by De Cristofaro et al. in 2012 is the most popular PSI-CA protocol based on the Google Scholar search results and it is still deemed one of the most efficient PSI-CA protocols.

In this paper, we also propose several solutions to these protocols' security problems.

Interactive Oracle Proof of Proximity (IOPPs) are a powerful tool for constructing succinct non-interactive arguments of knowledge (SNARKs) in the random oracle model, which are fast and plausibly post-quantum secure. The Fast Reed Solomon IOPP (FRI) is the most widely used in practice, while tensor-code IOPPs (such as Brakedown) achieve significantly faster prover times at the cost of much larger proofs. IOPPs are used to construct polynomial commitment schemes (PCS), which are not only an important building block for SNARKs but also have a wide range of independent applications.

This work introduces Basefold, a generalization of the FRI IOPP to a broad class of linear codes beyond Reed-Solomon, which we call $\textit{foldable linear codes}$. We construct a new family of foldable linear codes, which are a special type of randomly punctured Reed-Muller code, and prove tight bounds on their minimum distance. Finally, we introduce a new construction of a multilinear PCS from any foldable linear code, which is based on interleaving Basefold with the classical sumcheck protocol for multilinear polynomial evaluation. As a special case, this gives a new multilinear PCS from FRI.

In addition to these theoretical contributions, the Basefold PCS instantiated with our new foldable linear codes offers a more reasonable tradeoff between prover time, proof size, and verifier time than prior constructions. For instance, for polynomials over a $64$-bit field with $12$ variables, the Basefold prover is faster than both Brakedown and FRI-PCS ($2$ times faster than Brakedown and $3$ times faster than FRI-PCS), and its proof is $4$ times smaller than Brakedown's. On the other hand, for polynomials with $25$ variables, Basefold's prover is $6.5$ times faster than FRI-PCS, it's proof is $2.5$ times smaller than Brakedown's and its verifier is $7.5$ times faster. Using Basefold to compile the Hyperplonk PIOP [CBBZ23] results in an extremely fast implementation of Hyperplonk, which in addition to having competitive performance on general circuits, is particularly fast for circuits with high-degree custom gates (e.g., signature verification and table lookups). Hyperplonk with Basefold is approximately equivalent to the speed of Hyperplonk with Brakedown, but with a proof size that is more than $5$ times smaller. Finally, Basefold maintains performance across a wider variety of field choices than FRI, which requires FFT-friendly fields. Thus, Basefold can have an extremely fast prover compared to SNARKs from FRI for special applications. Benchmarking a circom ECDSA verification circuit with curve secp256k1, Hyperplonk with Basefold has a prover time that is more than $200\times$ faster than with FRI and its proof size is $5.8$ times smaller than Hyperplonk with Brakedown.

Security proofs of symmetric-key primitives typically consider an idealized world with access to a (uniformly) random function. The starting point of our work is the observation that such an ideal world leads to underestimating the actual security of certain primitives. As a demonstrating example, $\mathsf{XoP2}$, which relies on two independent random permutations, is proven to exhibit far superior concrete security compared to $\mathsf{XoP}$, which employs a single permutation with domain separation. But the main reason for this is an artifact of the idealized model used in the proof, in particular, that (in the random-function-ideal world) $\mathsf{XoP}$ might hit a trivially bad event (outputting 0) which does not occur in the real/domain-separated world. Motivated by this, we put forth the analysis of such primitives in an updated ideal world, which we call the {\em fine-tuned} setting, where the above artifact is eliminated. We provide fine-tuned (and enhanced) security analyses for $\mathsf{XoP}$ and $\mathsf{XoP}$-based MACs: $\mathsf{nEHtM}$ and $\mathsf{DbHtS}$. Our analyses demonstrate that the security of $\mathsf{XoP}$-based and $\mathsf{XoP2}$-based constructions are, in fact, far more similar than what was previously proven. Concretely, for the number of users $u$ and the maximum number of queries per user $q_m$, we show that the multi-user ``fine-tuned'' security bound of $\mathsf{XoP}$ can be proven as $O\left({u^{0.5}{q_m}^{2}}/{2^{2n}}\right)$ via the Squared-ratio method proposed by Chen et al. [CRYPTO'23], resulted to the same security bound of $\mathsf{XoP2}$ proven there. We also show the compatibility of the fine-tuned model with the Chi-squared method proposed by Dai et al. [CRYPTO'17], and show that $\mathsf{XoP}$ and $\mathsf{XoP2}$ enjoy the same security bound in the fine-tuned setting regardless of proving tools. Finally, we turn to the security analysis of MACs in the multi-user setting, where the effect of transitioning the proofs to the fine-tuned setting is even higher. Concretely, we are able to prove unexpected improvements in the security bounds for both $\mathsf{nEHtM}$ and $\mathsf{DbHtS}$. Our security proofs rely on a fine-tuned and extended version of Mirror theory for both lower and upper bounds, which yields more versatile and improved security proofs. Of independent interest, this extension allows us to prove the multi-user MAC security of $\mathsf{nEHtM}$ in the nonce-misuse model, while the previous analysis only applied to the multi-user PRF security in the nonce-respecting model. As a side note, we also point out (and fix) a flaw in the original analysis of Chen et al..

When outsourcing a database to an untrusted remote server, one might want to verify the integrity of contents while accessing it. To solve this, Blum et al. [FOCS `91] propose the notion of memory checking. Memory checking allows a user to run a RAM program on a remote server, with the ability to verify integrity of the storage with small local storage. In this work, we define and initiate the formal study of memory checking for Parallel RAMs (PRAMs). The parallel RAM model is very expressive and captures many modern architectures such as multi-core architectures and cloud clusters. When multiple clients run a PRAM algorithm on a shared remote server, it is possible that there are concurrency issues that cause inconsistencies. Therefore, integrity verification is even more desirable property in this setting. Assuming only the existence of one-way functions, we construct an online memory checker (one that reports faults as soon as they occur) for PRAMs with $O(\log N)$ simulation overhead in both work and depth. In addition, we construct an offline memory checker (one that reports faults only after a long sequence of operations) with amortized $O(1)$ simulation overhead in both work and depth. Our constructions match the best known simulation overhead of the memory checkers in the standard single-user RAM setting. As an application of our parallel memory checking constructions, we additionally construct the first maliciously secure oblivious parallel RAM (OPRAM) with polylogarithmic overhead.

Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness (SS-NIZK), that allows the adversary to access the simulator in superposition. We show a separation between post-quantum and quantum security of SS-NIZK, and prove that both Sahai’s construction for SS-NIZK (in the CRS model) and the Fiat-Shamir transformation (in the QROM) can be made quantumly-simulation-sound. As an immediate application of our new notion, we prove the security of the Naor-Yung paradigm in the quantum settings, with respect to a strong quantum IND-CCA security notion. This provides the quantum analogue of the classical dual key approach to prove the security of encryption schemes. Along the way, we introduce a new notion of quantum-query advantage functions, which may be used as a general framework to show classical/quantum separation for other cryptographic primitives, and it may be of independent interest.

Integral, zero-correlation (ZC), and impossible-differential (ID) attacks are three of the most important attacks on block ciphers. However, manually finding these attacks can be a daunting task, which is why automated methods are becoming increasingly important. Most of the automatic tools regarding integral, ZC and ID attacks have been focused only on finding distinguishers rather than complete attacks. At EUROCRYPT 2023, Hadipour et al. proposed a generic and efficient constraint programming (CP) model based on satisfiability for finding ID, ZC, and integral distinguishers. This new model can be extended to a unified CP model for finding full key recovery attacks. However, their method has some limitations, including the fact that the location of contradiction should be determined in advance, and the model is a cell-wise model unsuitable for weakly aligned ciphers, e.g., Ascon and PRESENT. In addition, they left developing a CP model for the partial-sum technique in key recovery as a future work.

In this paper, we improve the method by Hadipour et al. in several ways. First, we remove the limitation of determining the contradiction location in advance. Second, we show how to extend the distinguisher model to a bit-wise model, considering the internal structure of S-boxes and keeping the model based on satisfiability. Third, we introduce a CP model for the partial-sum technique for the first time. To show the usefulness and versatility of our approach, we applied it to different designs, from strongly aligned designs such as ForkSKINNY and QARMAv2 to weakly aligned designs such as Ascon and PRESENT, obtaining significantly improved results. To mention a few of our results, we improve the integral distinguisher of QARMAv2-128 (resp. QARMAv2-64) by 7 (resp. 5) rounds, and the integral distinguisher of ForkSKINNY by 1 round, only thanks to our cell-wise distinguisher modelings. By using our new bit-wise modeling, our tool can find a group of $2^{155}$ 5-round ID and ZC distinguishers for Ascon in only one run, taking a few minutes on a regular laptop. Thanks to the new CP model for the partial-sum technique, we could improve the integral attacks on all variants of SKINNY. Particularly, we improved the best attack on SKINNY-$n$-$n$ in the single-key setting by 1 round. We also improved the ID attacks on ForkSKINNY and analyzed this cipher in the limited reduced-round setting for the first time. Our methods are generic and applicable to other block ciphers.

Protocols for secure multi-party computation (MPC) supporting mixed-mode computation have found a lot of applications in recent years due to their flexibility in representing the function to be evaluated. However, existing mixed-mode MPC protocols are only practical for a small number of parties: they are either tailored to the case of two/three parties, or scale poorly for a large number of parties. In this paper, we design and implement a new system for highly efficient and scalable mixed-mode MPC tolerating an arbitrary number of semi-honest corruptions. Our protocols allow secret data to be represented in Encrypted, Boolean, Arithmetic, or Yao form, and support efficient conversions between these representations. 1. We design a multi-party table-lookup protocol, where both the index and the table can be kept private. The protocol is scalable even with hundreds of parties. 2. Using the above protocol, we design efficient conversions between additive arithmetic secret sharings and Boolean secret sharings for a large number of parties. For 32 parties, our conversion protocols require 1184× to 8141× less communication compared to the state- of-the-art protocols MOTION and MP-SPDZ; this leads to up to 1275× improvement in running time under 1 Gbps network. The improvements are even larger with more parties. 3. We also use new protocols to design an efficient multi-party distributed garbling protocol. The protocol could achieve asymptotically constant communication per party.

Our implementation will be made public.

In this paper, we introduce Oblivious Homomorphic Encryption (OHE) which provably separates the computation spaces of multiple clients of a fully homomorphic encryption (FHE) service while keeping the evaluator blind about whom a result belongs. We justify the importance of this strict isolation property of OHE by showing an attack on a recently proposed key-private cryptocurrency scheme. Our two OHE constructions are based on a puncturing function where the evaluator can effectively mask ciphertexts from rogue and potentially colluding clients. We show that this can be implemented via a FHE scheme plus an anonymous commitment scheme. OHE can be used to provide provable anonymity to cloud applications, to single server implementations of anonymous messaging as well as to account-based cryptocurrencies.

The idea of balancing the side-channel leakage in software was proposed more than a decade ago. Just like with other hiding-based countermeasures, the goal is not to hide the leakage completely but to significantly increase the effort required for the attack. Previous approaches focused on two directions: either balancing the Hamming weight of the processed data or deriving the code by using stochastic leakage profiling.

In this brief, we build upon these results by proposing a novel approach that combines the two directions. We provide the theory behind our encoding scheme backed by experimental results on a 32-bit ARM Cortex-M4 microcontroller. Our results show that such a combination gives better side-channel resistance properties than each of the two methods separately.

This paper presents full round distinguishing and key recovery attacks on lightweight block cipher SAND-2 with 64-bit block size and 128-bit key size, which appears to be a mixture of the AND-Rotation-XOR (AND-RX) based ciphers SAND and ANT. However, the security arguments against linear and some other attacks are not fully provided. In this paper, we find that the combination of a SAND-like nibble-based round function and ANT-like bit-based permutations will cause dependencies and lead to iterative linear and differential trails with high probabilities. By exploiting these, full round distinguishing attacks on SAND-2 work with $2^{46}$ queries for linear and $2^{58.60}$ queries for differential in the single-key setting. Then, full round key recovery attacks are also mounted, which work with the time complexity $2^{48.23}$ for linear and $2^{64.10}$ for differential. It should be noted that the dependency observed in this paper only works for SAND-2 and will not threaten SAND and ANT. From the point of designers, our attacks show the risk of mixing the parts of different designs, even though each of them is well-studied to be secure.

We show that the Yang et al.'s key agreement scheme [Future Gener. Comput. Syst., 145, 415-428 (2023)] is flawed. (1) There are some inconsistent computations, which should be corrected. (2) The planned route of a target vehicle is almost exposed. The scheme neglects the basic requirement for bit-wise XOR, and tries to encrypt the route by the operator. The negligence results in some trivial equalities. (3) The scheme is insecure against impersonation attack launched by the next roadside unit.

Many secure computation schemes and protocols (such as numerous variants of secure multi-party computation and homomorphic encryption) have favorable performance characteristics when they are used to evaluate addition and scalar multiplication operations on private values that can be represented as ring elements. A purely algebraic argument (with no references to any specific protocol or scheme) can be used to show that the ability to perform these operations is sufficient to implement any univariate map that operates on private values when that map's domain is finite. Such implementations of univariate maps can be composed in sequence any number of times. Other forms of composition for such implementations can be realized by using multiplication operations involving ring elements, but it is possible that these can be substituted with scalar multiplication operations within certain secure computation workflows.

Motivated by applications in anonymous reputation systems and blockchain governance, we initiate the study of predicate aggregate signatures (PAS), which is a new primitive that enables users to sign multiple messages, and these individual signatures can be aggregated by a combiner, preserving the anonymity of the signers. The resulting PAS discloses only a brief description of signers for each message and provides assurance that both the signers and their description satisfy the specified public predicate. We formally define PAS and give a construction framework to yield a logarithmic size signature, and further reduce the verification time also to logarithmic. We also give several instantiations for several concrete predicates that may be of independent interest. To showcase its power, we also demonstrate its applications to multiple settings including multi-signatures, aggregate signatures, threshold sig- natures, (threshold) ring signatures, attribute-based signatures, etc, and advance the state of the art in all of them.

In the design of an identity-based encryption (IBE) scheme, the primary security assumptions center around quadratic residues, bilinear mappings, and lattices. Among these approaches, one of the most intriguing is introduced by Clifford Cocks and is based on quadratic residues. However, this scheme has a significant drawback: a large ciphertext to plaintext ratio. A different approach is taken by Zhao et al., who design an IBE still based on quadratic residues, but with an encryption process reminiscent of the Goldwasser-Micali cryptosystem. In the following pages, we will introduce an elementary method to accelerate Cocks' encryption process and adapt a space-efficient encryption technique for both Cocks' and Zhao et al.'s cryptosystems.

In Crypto 94, Chor, Fiat, and Naor first introduced the traitor tracing (TT) systems, which aim at helping content distributors identify pirates. Since its introduction, many traitor tracing schemes have been proposed. However, we observe until now almost all the traitor tracing systems using probabilistic public key (and secret key) encryption as the the content distribution algorithm, they do not consider this basic fact: the malicious encrypter can plant some trapdoor in the randomness of the ciphertexts and later he can use this trapdoor or the delegation of the trapdoor to construct decoding pirates, He can sell them to the black market and get his own benefits. At first sight, this new attack model is too strong to capture the real attack scenarios. But we think it is valuable at least for the following two reasons: (1) Note in many modern content distribution systems, there are at least existing three different roles: { the content provider, the content distributer and the content consumer. In this framework, the encrypter is not necessarily the content provider (or content owner). It can be a malicious employee in the content provider corporation, it can also be the malicious content distributer or its malicious employee}. In all these cases, the encrypter has its own benefits and has the potential intention to plant some trapdoor in the randomness for generating ciphertexts. (2) Also note in the related work, there is a conclusion that traitor tracing and differential privacy can have directly influence on each other, while differential privacy (DP) is at the heart of constructing modern privacy preserving systems. But if we consider this new insider attacker (the encrypter), at least some part arguments on the relationship between traitor tracing and differential privacy need more consideration. Therefore in this paper we carefully describe this new insider attacker and investigate thoroughly on its effect. Our main research results are the following: (1) We show that many existing public key traitor tracing systems with probabilistic encryption algorithm are failing to work correctly when facing this malicious encrypter.They are including the BSW, BW, GKSW, LCZ and BZ traitor tracing systems. Furthermore, we conclude that most of the existing traitor tracing systems using probabilistic encryption algorithm can not resist this attack. (2) When considering the insider attacker (the encrypter), if the traitor tracing schemes using probabilistic encryption algorithms, the conclusion on tight relationship between traitor tracing and differential privacy may need more consideration. (3) By employing the technique of hash function, we show how to design TT+ system which can resist this type of attack based on the existing traitor tracing system. Compared with the old traitor tracing system, our new proposal does not add much overhead and thus is practical too.

In this paper, we analyze the Espresso cipher from a related key chosen IV perspective. More precisely, we explain how one can obtain Key-IV pairs such that Espresso's keystreams either have certain identical bits or are shifted versions of each other. For the first case, we show how to obtain such pairs after $2^{32}$ iterations, while for the second case, we present an algorithm that produces such pairs in $2^{28}$ iterations. Moreover, we show that by making a minor change in the padding used during the initialization phase, it can lead to a more secure version of the cipher. Specifically, changing the padding increases the complexity of our second attack from $2^{28}$ to $2^{34}$. Finally, we show how related IVs can accelerate brute force attacks, resulting in a faster key recovery. Although our work does not have any immediate implications for breaking the Espresso cipher, these observations are relevant in the related-key chosen IV scenario.