IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Beyond the Circuit How to minimize foreign arithmetic in ZKP circuits
Full text link A fundamental challenge in zero-knowledge proof systems is implementing operations that are “foreign” to the underlying constraint system, in that they are arithmetic operations with a different modulus than the one used by the proof system. The modulus of the constraint system is a large prime, and common examples of foreign operations are Boolean operations, field arithmetic, or public-key cryptography operations. We present novel techniques for efficiently embedding such foreign arithmetic in zero-knowledge, including (i) equality of discrete logarithms across different groups; (ii) scalar multiplication without requiring elliptic curve operations; (iii) proving knowledge of an AES encryption. Our approach combines rejection sampling, sigma protocols, and lookup protocols. We implement and provide concrete benchmarks for our protocols. </p
Don\u27t Use It Twice: Reloaded! On the Lattice Isomorphism Group Action
No full textGroup actions have emerged as a powerful framework in post-quantum cryptography, serving as the foundation for various cryptographic primitives. The Lattice Isomorphism Problem (LIP) has recently gained attention as a promising hardness assumption for designing quantum-resistant protocols. Its formulation as a group action has opened the door to new cryptographic applications, including a commitment scheme and a linkable ring signature.In this work, we analyze the security properties of the LIP group action and present new findings. Specifically, we demonstrate that it fails to satisfy the weak unpredictability and weak pseudorandomness properties when the adversary has access to as few as three and two instances with the same secret, respectively. This significantly improves upon prior analysis by Budroni et al. (PQCrypto 2024).As a direct consequence of our findings, we reveal a vulnerability in the linkable ring signature scheme proposed by Khuc et al. (SPACE 2024), demonstrating that the hardness assumption underlying the linkable anonymity property does not hold.</p
On TRP-RF Switch in the Quantum Query Model
Full text link The tweakable random permutation (TRP) to random function (RF) switch in the quantum query model (Hosoyamada and Iwata, IACR ASIACRYPT 2019) is tightened. This immediately improves the security bounds for TNT and LRWQ against quantum chosen-plaintext attacks. We further demonstrate the utility of this tightened switch by establishing birthday-bound security for two additional TRP-based modes, including the cascade function. </p
On Circuit Private, Multikey and Threshold Approximate Homomorphic Encryption
Full text linkHomomorphic encryption for approximate arithmetic allows one to encrypt discretized real/complex numbers and evaluate arithmetic circuits over them. The first scheme, called CKKS, was introduced by Cheon et al. (Asiacrypt 2017) and gained tremendous attention. The enthusiasm for CKKS-type encryption stems from its potential to be used in inference or multiparty computation tasks that do not require an exact output.A desirable property for homomorphic encryption is circuit privacy, which requires that a ciphertext leaks no information on the computation performed to obtain it. Despite numerous improvements directed toward improving efficiency, the question of circuit privacy for approximate homomorphic encryption remains open.In this paper, we give the first formal study of circuit privacy for homomorphic encryption over approximate arithmetic. We introduce formal models that allow us to reason about circuit privacy. Then, we show that approximate homomorphic encryption can be made circuit private using tools from differential privacy with appropriately chosen parameters. In particular, we show that by applying an exponential (in the security parameter) Gaussian noise on the evaluated ciphertext, we remove useful information on the circuit from the ciphertext. Crucially, we show that the noise parameter is tight, and taking a lower one leads to an efficient adversary against such a system.We expand our definitions and analysis to the case of multikey and threshold homomorphic encryption for approximate arithmetic. Such schemes allow users to evaluate a function on their combined inputs and learn the output without leaking anything on the inputs. A special case of multikey and threshold encryption schemes defines a so-called partial decryption algorithm where each user publishes a “masked” version of its secret key, allowing all users to decrypt a ciphertext. Similarly, in this case, we show that applying a proper differentially private mechanism gives us IND-CPA-style security where the adversary additionally gets as input the partial decryptions. This is the first security analysis of approximate homomorphic encryption schemes that consider the knowledge of partial decryptions. We show lower bounds on the differential privacy noise that needs to be applied to retain security. Analogously, in the case of circuit privacy, the noise must be exponential in the security parameter. We conclude by showing the impact of the noise on the precision of CKKS-type schemes. </p
SoK: A Methodology to Achieve Provable Side-Channel Security in Real-World Implementations
Full text linkA wide range of countermeasures have been proposed to defend against side-channel attacks, with masking being one of the most effective and commonly used techniques. While theoretical models provide formal security proofs, these often rely on assumptions—sometimes implicit—that can be difficult to assess in practice. As a result, the design of secure masked implementations frequently combines proven theoretical arguments with heuristic and empirical validation.Despite the significant body of work, the literature still lacks a cohesive and well-defined framework for translating theoretical security guarantees into practical implementations on physical devices. Specifically, there remains a gap in connecting provable results from abstract models to quantitative security guarantees at the implementation level.In this Systematization of Knowledge (SoK), we aim to provide a comprehensive methodology to transform abstract cryptographic algorithms into physically secure implementations against side-channel attacks on microcontrollers. We introduce new tools to adapt the ideal noisy leakage model to practical, real-world scenarios, and we integrate state-of-the-art techniques to build secure implementations based on this model.Our work systematizes the design objectives necessary for achieving high security levels in embedded devices and identifies the remaining challenges in concretely applying security reductions. By bridging the gap between theory and practice, we seek to provide a foundation for future research that can develop implementations with proven security against side-channel attacks, based on well-understood leakage assumptions. </p
The Round Complexity of Proofs in the Bounded Quantum Storage Model
Full text link The round complexity of interactive proof systems is a key question of practical and theoretical relevance in complexity theory and cryptography. Moreover, results such as QIP = QIP(3) (STOC\u2700) show that quantum resources significantly help in such a task. In this work, we initiate the study of round compression of protocols in the bounded quantum storage model (BQSM). In this model, the malicious parties have a bounded quantum memory and they cannot store the all the qubits that are transmitted in the protocol. Our main results in this setting are the following: There is a non-interactive (statistical) witness indistinguishable proof for any language in NP (and even QMA) in BQSM in the plain model. We notice that in this protocol, only the memory of the verifier is bounded. Any classical proof system can be compressed in a two-message quantum proof system in BQSM. Moreover, if the original proof system is zero-knowledge, the quantum protocol is zero-knowledge too. In this result, we assume that the prover has bounded memory. Finally, we give evidence towards the “tightness” of our results. First, we show that NIZK in the plain model against BQS adversaries is unlikely with standard techniques. Second, we prove that without the BQS model there is no 2–message zero-knowledge quantum interactive proof, even under computational assumptions. </p
Towards a Generalization of the Algebraic Attack on Stream Ciphers: A Study of the Case with Only Extremal-Degree Monomials
Full text link When designing filter functions in Linear Feedback Shift Registers (LFSR) based stream ciphers, algebraic criteria of Boolean functions such as the Algebraic Immunity (AI) become key characteristics because they guarantee the security of ciphers against the powerful algebraic attacks. In this article, we abstract the algebraic attacks proposed by Courtois and Meier on filtered LFSR twenty years ago, considering how the standard algebraic attack can be generalized beyond filtered LFSR to stream ciphers that employ a Boolean filter function to an updated state. Depending on the updating process, we use different sets of annihilators than those used in the standard algebraic attack; it leads to a generalization of the concept of algebraic immunity, and in some particular cases, potentially more efficient attacks. Motivated by the filter permutator paradigm, we focus on the case where the update function is a bit-permutation, since it maintains the degree of the monomials. For example the degree of the monomials of degree up to and from to remains invariant, which leads us to consider annihilators having only monomials of these degrees. If this number of monomials is sufficiently low, linearization is feasible, allowing the linear system to be solved and revealing the key, as in the standard algebraic attack. This particular characteristic is restricted by the standard algebraic attacks and to analyze it we introduce a new notion called Extremal Algebraic Immunity (EAI). We perform a theoretic study of the EAI criterion and explore its relation to other algebraic criteria. We prove the upper bound of the EAI of an -variable Boolean function and further show that the EAI can be lower bounded by the AI restricted to a subset, as defined by Carlet, Méaux and Rotella at FSE 2017. We also exhibit functions with EAI guaranteed to be lower than the AI, in particular we highlight a pathological case of functions with optimal algebraic immunity and EAI only . As applications, we determine the EAI of filter functions of some existing stream ciphers and discuss how extremal algebraic attacks using EAI could apply to variations of known ciphers. The extremal algebraic attack does not give a better complexity than Courtois and Meier\u27s result on the existing stream ciphers. However, we see this work as a study to avoid weaknesses in the construction of future stream ciphers. </p
A Greedy Global Framework for Lattice Reduction Using Deep Insertions
Full text linkLLL-style lattice reduction algorithms iteratively employ size reduction and reordering on ordered basis vectors to find progressively shorter, more orthogonal vectors. DeepLLL reorders the basis through deep insertions, yielding much shorter vectors than LLL. DeepLLL was introduced alongside BKZ, however, the latter has received greater attention and has emerged as the state-of-the-art. We first show that LLL-style algorithms work with a designated measure of basis quality and iteratively improves it; specifically, DeepLLL improves a sublattice measure based on the generalised Lovász condition. We then introduce a new generic framework X-GG for lattice reduction algorithms that work with a measure X of basis quality. X-GG globally searches for deep insertions that minimise X in each iteration. We instantiate the framework with two quality measures – basis potential (Pot) and squared sum (SS) – both of which have corresponding DeepLLL algorithms. We prove polynomial runtimes for our X-GG algorithms and also prove their output to be X-DeepLLL reduced. Our experiments on non-preprocessed bases show that X-GG produces better quality outputs whilst being much faster than the corresponding DeepLLL algorithms. We also compare SS-GG and the FPLLL implementation of BKZ with LLL-preprocessed bases. In small dimensions (40 to 210), SS-GG is significantly faster than BKZ with block sizes 8 to 12, while simultaneously also providing better output quality in most cases. In higher dimensions (250 and beyond), by varying the threshold for deep insertion, SS-GG offers new trade-offs between the output quality and runtime. On the one hand, it provides significantly better runtime than BKZ-5 with worse output quality; on the other hand, it is significantly faster than BKZ-21 while providing increasingly better output quality after around dimension 350. </p
HOP-1 and HOP-2: New Re-keying Schemes for Symmetric Ciphers
Full text link Re-keying is one of the most effective techniques to protect symmetric ciphers against side-channel attacks. Since its introduction, numerous re-keying schemes have been developed. This paper proposes two new index-based re-keying schemes, HOP-1 and HOP-2, which are variants of Kocher\u27s re-keying scheme. Specifically, through tree-based analysis of Kocher\u27s re-keying scheme, we identify strategies to minimize key repetition in Kocher\u27s approach. We compare HOP-1 and HOP-2 with existing re-keying schemes and evaluate their application to two leakage-resilient authenticated encryption schemes, highlighting their effectiveness relative to these other re-keying schemes. </p
Strengthening the KLEIN Cipher
Full text linkIn 2011, Gong, Nikova, and Law introduced the lightweight block cipher KLEIN, designed for efficient encryption both in hardware and software implementations. Since then, several attacks on KLEIN have been published, most notably truncated differential cryptanalysis that exploits the weak mixing of higher and lower nibbles in the cipher\u27s diffusion layer. The weakness stems from the combination of the byte-oriented AES MixColumns operation together with 4-bit S-boxes. The branch number of the AES MixColumns is 5, which is optimal for byte-oriented designs, but insufficient in a nibble-oriented setting, where the upper bound is 9. To address this vulnerability, we evaluate the implementation cost of four MDS and near-MDS matrices over GF(2^4), which improve diffusion due to having branch numbers 9 and 8, respectively. We select an involutory near-MDS matrix for which we present an implementation with s-XOR count of 135, the lowest reported for an involutory near-MDS matrix of order 8 over GF(2^4). By pairing the new mixing step with a modified key schedule, we obtain a variant of KLEIN that is secure against previously published attacks and offers comparable efficiency. </p