IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Circular Insecure Encryption: from Long Cycles to Short Cycles
Full text linkA length encryption cycle consists of a sequence of keys, each encrypting the next, forming a cycle, and an encryption scheme is -circular secure if a length encryption cycle is computationally indistinguishable from encryptions of zeros. An interesting problem is whether CPA security implies circular security. This is shown to be not true. Using standard cryptographic assumptions and LWE, it was shown that within the class of CPA secure encryption schemes, for any , there exists an -circular insecure encryption scheme. Furthermore, there exists a particular encryption scheme that is -circular insecure for all . Following these results, it is natural to ask whether a circular insecurity of a particular length implies circular insecurity of different lengths and of multiple lengths. We answer this problem with an affirmative in this paper. We constructively prove that a CPA secure encryption scheme that is insecure in the presence of encryption cycles of length implies the existence of such a scheme for encryption cycles of any length less than . The constructed -circular insecure construction may have the same message space as the -circular insecure encryption scheme, and our results apply to both public key and symmetric key settings. </p
Construction of Maiorana-McFarland type cryptographically significant Boolean functions with good implementation properties
Full text linkWe present a new construction of cryptographically significant Boolean functions defined over a large number of variables, with an emphasis on efficient circuit realizability. Our method is based on a variant of the well-known Maiorana-McFarland (MM) construction, adapted to enable circuit structures with less than gates on the number of input bits . We evaluate the circuit efficiency in terms of the total number of logic gates (for example AND, OR, NOT, and XOR – each with a maximum fan-in of two) required to implement a given function. While prior studies have explored cryptographic parameters of such functions in theory, they often overlooked circuit-level efficiency, especially in high-dimensional settings. In this work, we construct a class of balanced functions with high nonlinearity, low absolute autocorrelation and high algebraic degree, yet realizable using a small number of logic gates. Towards application, this work provides additional design directions for cryptographic primitives in domains such as fault-resistant cryptography and homomorphic encryption, where both security and circuit efficiency at scale are critical. Further investigations are required towards actual hardware implementation of our proposed functions as well as to exploit them in concrete cipher designs. </p
Unconditional Quantum Cryptography with a Bounded Number of Keys
Full text link We construct the following cryptographic primitives with unconditional security in a bounded-key model: One-time public-key encryption, where the public keys are pure quantum states One-time signatures, where the verification keys are pure quantum states. In our model, the adversary is given a bounded number of copies of the public key. We present efficient constructions and nearly-tight lower bounds for the size of the secret keys. Our security proofs are based on the quantum coupon collector problem, which was originally studied in the context of learning theory. The quantum coupon collector seeks to learn a set of strings (coupons) when given several copies of a superposition over the coupons. We make novel connections between this problem and cryptography. Our main technical ingredient is a family of coupon states, with randomized phases, that come with strong hardness properties. Our analysis improves on prior work by (i) showing that the number of quantum states needed to learn the entire set of coupons is identical to the number of random coupons needed in the classical coupon collector problem. (ii) Furthermore we prove that this result holds for a randomly chosen set of coupons, whereas prior work only lower-bounded the number of coupon states required to learn the worst-case set of coupons. </p
Quantum Analysis of AES
Full text linkOur work explores the key recovery attack using the Grover\u27s search on the three variants of AES (-128, -192, -256). In total, we develop a pool of 26 implementations per AES variant (totaling 78), by taking the state-of-the-art advancements in the relevant fields into account.We present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.\u27s Asiacrypt\u2720 paper by more than 97 percent for each variant of AES. We show that the qubit count - Toffoli depth product is reduced from theirs by more than 87 percent. Furthermore, we analyze the Jaques et al.\u27s Eurocrypt\u2720 implementations in detail, fix the bugs (arising from some problem of the quantum computing tool used), and report corrected benchmarks (which seem to improve from the authors\u27 own bug-fixing, thanks to our architecture consideration). To the best of our finding, our work improves from all the previous works (including the Asiacrypt\u2722 paper by Huang and Sun, the Asiacrypt\u2723 paper by Liu et al. and the Asiacrypt\u2724 paper by Shi and Feng) in terms of various quantum circuit complexity metrics. To be more precise, we estimate the currently best-known quantum attack complexities for AES-128 (), AES-192 () and AES-256 (). Additionally, we achieve the least Toffoli depth - qubit count product for AES-128 (, improving from by Shi and Feng in Asiacrypt\u2724), AES-192 (, improving from by Liu et al. in Asiacrypt\u2723) and AES-256 (, improving from by Liu et al. in Asiacrypt\u2723) so far.We further investigate the prospect of the Grover\u27s search. We propose four new implementations of the S-box, one new implementation of the MixColumn; as well as five new architecture (one is motivated by the architecture by Jaques et al. in Eurocrypt\u2720, and the rest four are entirely our innovation). Under the MAXDEPTH constraint (specified by NIST), the circuit depth metrics (Toffoli depth, -depth and full depth) become crucial factors and parallelization for often becomes necessary. We provide the least depth implementation in this respect that offers the best performance in terms of metrics like depth-squared - qubit count product, depth - gate count product. </p
Faster Quantum Algorithms for MQ2 and Applications
Full text linkWe study quantum algorithms for multivariate quadratic Boolean equation systems by focusing on their precise gate count. While better asymptotic algorithms are known, currently gate counts were only computed for exhaustive search (Schwabe and Westerbaan, SPACE 2016) and a variant of Grover\u27s search using preprocessing (Pring, WAIFI 2018). This limits the applicability of Boolean equation solving to cryptanalysis, which considers relatively small numbers of variables (from 40 to 200) and is concerned with the exact complexity of the solver.In this paper, we introduce two new quantum algorithms. The first algorithm is an optimized quantum exhaustive search which amortizes the cost of polynomial evaluation at each quantum search iterate. The second algorithm adapts a method of Bouillaguet et al. (SOSA 2022) which proceeds by linearization of the system. In both cases, we implement the quantum circuits, study their complexity, and obtain significant improvements over previous results.Next, we apply these new algorithms to the cryptanalysis of the block ciphers LowMC and RAIN in the single-data setting. By adapting attacks from Liu et al. (ToSC 2022) and Liu et al. (ToSC 2023) we obtain the first quantum cryptanalysis results on these ciphers. </p
Bulletproofs for R1CS: Bridging the Completeness-Soundness Gap and a ZK Extension
Full text linkBulletproofs, introduced by Bünz, Bootle, Boneh, Poelstra, Wuille and Maxwell (IEEE S& P, 2018), is a highly efficient non-interactive argument system that does not require a trusted setup. Recently, Bünz (PhD Thesis, 2023) extended Bulletproofs to support arguments for rank-1 constraint satisfaction (R1CS) systems, a widely-used representation for arithmetic satisfiability problems. Although the argument system constructed by Bünz preserves the attractive properties of Bulletproofs, it presents a gap between its completeness and soundness guarantees: The system is complete for a restricted set of instances, but sound only for a significantly broader set. Although argument systems for such gap relations nevertheless provide clear and concrete guarantees, the gaps they introduce may lead to various inconsistencies or undesirable gaps within proofs of security, especially when used as building blocks within larger systems.In this work we show that the argument system presented by Bünz can be extended to bridge the gap between its completeness and soundness, and to additionally provide honest-verifier zero-knowledge. For the extended argument system, we introduce a refined R1CS relation that captures the precise set of instances for which both completeness and soundness hold without resorting to a gap formulation. The extended argument system preserves the performance guarantees of the argument system presented by Bünz, and yields a non-interactive argument system using the Fiat-Shamir transform. </p
HRA-Secure Homomorphic Lattice-Based Proxy Re-Encryption with Tight Security
Full text linkWe construct an efficient proxy re-encryption (PRE) scheme secure against honest re-encryption attacks (HRA-secure) with precise concrete security estimates. To get these precise concrete security estimates, we introduce the tight, fine-grained noise-flooding techniques of Li et al. (CRYPTO\u2722) to RLWE-based (homomorphic) PRE schemes, as well as a mixed statistical-computational security definition to HRA security analysis. Our solution also supports homomorphic operations on the ciphertexts. Such homomorphism allows for advanced applications, e.g., encrypted computation of network statistics across networks, and unlimited hops in the case of full homomorphism, i.e., when bootstrapping is available.We implement our PRE scheme in the OpenFHE software library and apply it to a problem of secure multi-hop data distribution in the context of 5G virtual network slices. We also experimentally evaluate the performance of our scheme, demonstrating that the implementation is practical.Moreover, we compare our PRE method with other lattice-based PRE schemes and approaches targeting HRA security. These achieve HRA security, but not in a tight, practical scheme such as our work. Further, we present an attack on the PRE scheme proposed in Davidson et al.\u27s (ACISP\u2719), which was claimed to achieve HRA security without noise flooding, i.e., without adding large noise. </p
New Records for Practical-data Chosen-plaintext Attacks on Round-reduced AES
Full text linkAs probably the most widespread block cipher, the AES has attracted tremendous cryptanalytical efforts since its standardization. In the single secret-key setting, Demirci-Selcuk Meet-in-the-Middle (DS-MitM) attacks have remained the state of the art on most rounds and have the lowest time complexities on all AES versions. However, after the research intensity had peaked with Derbez et al.\u27s seminal works from Eurocrypt\u2713 and FSE\u2713 and Li et al.\u27s improvements on the AES-192 at FSE\u2714, the generic technical evolution on DS-MitM attacks stagnated. Subsequent works automated the technique or concentrated on ciphers other than the AES. But it took one decade until Dong et al. (DCC\u2724) advanced the progress on DS-MitM attacks. Their approach uses constraints in both the offline and online phases, which produced improved attacks on AES-192 and -256 in the chosen-plaintext setting and on all versions in the practical-data setting.In this work, we demonstrate that Dong et al.\u27s use of constraints could be further improved, leading to better attacks on all versions of the AES with practical data complexity. We emphasize that our attacks do not threaten the security of the full AES versions but refine our understanding of their security margins under practical data settings. </p
Does the UC-Security Notion for PAKE Imply Game-Based Security?
Full text linkA Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographically strong key, in the setting where the only information shared in advance is a low-entropy “password”. The two standard security definitions for PAKE are the game-based one by Bellare, Pointcheval and Rogaway (BPR-security, EUROCRYPT 2000) and the Universally Composable (UC) one by Canetti et al. (EUROCRYPT 2005). It is well-known that UC-security implies BPR-security; however, there are a large number of variants of both definitions, and the relation between them is not entirely clear.In this work, we thoroughly study a variant of BPR-security by Katz, Ostrovsky and Yung (KOY-security, JACM 2009): We show, via a counterexample, that UC-security does not imply KOY-security; We then prove that a variant of UC-security, called implicit-only UC-security (Dupont et al., EUROCRYPT 2018), implies KOY-security. Interestingly, we make the observation that KOY- and implicit-only UC-security essentially strengthen their standard counterparts in the same manner. We also present detailed explanations of all four security notions. </p
Who Verifies the Verifiers? Lessons Learned From Formally Verified Line-Point Zero-Knowledge
Full text link Computer-aided cryptography, with particular emphasis on formal verification, promises an interesting avenue to establish strong guarantees about cryptographic primitives. The appeal of formal verification is to replace the error-prone pen-and-paper proofs with a proof that was checked by a computer and, therefore, does not need to be checked by a human. In this paper, we ask the question of how reliable are these machine-checked proofs by analyzing a formally verified implementation of the Line-Point Zero-Knowledge (LPZK) protocol (Dittmer, Eldefrawy, Graham-Lengrand, Lu, Ostrovsky and Pereira, CCS 2023). The implementation was developed in EasyCrypt and compiled into OCaml code that was claimed to be high-assurance, i.e., that offers the formal guarantees of guarantees of completeness, soundness, and zero knowledge. We show that despite these formal claims, the EasyCrypt model was flawed, and the implementation (supposed to be high-assurance) had critical security vulnerabilities. Concretely, we demonstrate that: 1) the EasyCrypt soundness proof was incorrectly done, allowing an attack on the scheme that leads honest verifiers into accepting false statements; and 2) the EasyCrypt formalization inherited a deficient model of zero knowledge for a class of non-interactive zero knowledge protocols that also allows the verifier to recover the witness. In addition, we demonstrate 3) a gap in the proof of the perfect zero knowledge property of the LPZK variant of Dittmer, Ishai, Lu and Ostrovsky (CCS 2022) that the EasyCrypt proof is based, which, depending on the interpretation of the protocol and security claim, could allow a malicious verifier to learn the witness. Our findings highlight the importance of scrutinizing machine-checked proofs, including their models and assumptions. We offer lessons learned for both users and reviewers of tools like EasyCrypt, aimed at improving the transparency, rigor, and accessibility of machine-checked proofs. By sharing our methodology and challenges, we hope to foster a culture of deeper engagement with formal verification in the cryptographic community. </p