IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Lattice Reduction via Dense Sublattices: A Cryptanalytic No-Go
Full text link Most concrete analyses of lattice reduction focus on the BKZ algorithm or its variants relying on Shortest Vector Problem (SVP) oracles. However, a variant by Li and Nguyen (Cambridge U. Press 2014) exploits more powerful oracles, namely for the Densest rank- Sublattice Problem (DSP) for . We first observe that, for random lattices, DSP –and possibly even DSP– seems heuristically not much more expensive than solving SVP with the current best algorithm. We indeed argue that a densest sublattice can be found among pairs or triples of vectors produced by lattice sieving, at a negligible additional cost. This gives hope that this approach could be competitive. We therefore proceed to a heuristic and average-case analysis of the slope of DSP-BKZ output, inspired by a theorem of Kim (Journal of Number Theory 2022) which suggest a prediction for the volume of the densest rank- sublattice of a random lattice. Under this heuristic, the slope for or appears tenuously better than that of BKZ, making this approach less effective than regular BKZ using the “Dimensions for Free” of Ducas (EUROCRYPT 2018). Furthermore, our experiments show that this heuristic is overly optimistic. Despite the hope raised by our first observation, we therefore conclude that this approach appears to be a No-Go for cryptanalysis of generic lattice problems. </p
Shared OT and Its Applications
Full text linkWe present unconditionally perfectly secure protocols in the semi-honest setting for several functionalities: (1) private elementwise equality; (2) private bitwise integer comparison; and (3) bit-decomposition. These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo M and allowing additive secret-sharing of all inputs and outputs. These extensions can be implemented by simple local computations without incurring additional OT invocations. We believe our Shared OT may be of independent interest.Our protocols demonstrate the best round, communication, and computational complexities compared to all other protocols secure in a similar setting. Moreover, all of our protocols involve either 2 or 3 rounds. </p
Revisiting Module Lattice-based Homomorphic Encryption and Application to Secure-MPC
Full text linkHomomorphic encryption (HE) schemes have gained significant popularity in modern privacy-preserving applications across various domains. While research on HE constructions based on learning with errors (LWE) and ring-LWE has received major attention from both cryptographers and software-hardware designers alike, their module-LWE-based counterpart has remained comparatively under-explored in the literature. A recent work provides a module-LWE-based instantiation (MLWE-HE) of the Cheon-Kim-Kim-Song (CKKS) scheme and showcases several of its advantages such as parameter flexibility and improved parallelism. However, a primary limitation of this construction is the quadratic growth in the size of the relinearization keys. Our contribution is two-pronged: first, we present a new relinearization key-generation technique that addresses the issue of quadratic key size expansion by reducing it to linear growth. Second, we extend the application of MLWE-HE in a multi-group homomorphic encryption (MGHE) framework, thereby generalizing the favorable properties of the single-keyed HE to a multi-keyed setting as well as investigating additional flexibility attributes of the MGHE framework. </p
Simpler and Faster Pairings from the Montgomery Ladder
Full text link We show that Montgomery ladders compute pairings as a by-product, and explain how a small adjustment to the ladder results in simple and efficient algorithms for the Weil and Tate pairing on elliptic curves using cubical arithmetic. We demonstrate the efficiency of the resulting cubical pairings in several applications from isogeny-based cryptography. Cubical pairings are simpler and more performant than pairings computed using Miller\u27s algorithm: we get a speed-up of over 40 per cent for use-cases in SQIsign, and a speed-up of about 7 per cent for use-cases in CSIDH. While these results arise from a deep connection to biextensions and cubical arithmetic, in this article we keep things as concrete (and digestible) as possible. We provide a concise and complete introduction to cubical arithmetic as an appendix. </p
Turning Hash-Based Signatures into Distributed Signatures and Threshold Signatures Delegate Your Signing Capability, and Distribute it Among Trustees
Full text linkWe introduce techniques to transform existing stateful hash based signature (HBS) schemes, such as LMS or XMSS, into efficient threshold and distributed signature schemes. Our approach requires a trusted dealer for setup, and uses a large (up to a few GiB, typically) common reference value for each new public key. The dealer generates the keypair and distributes shares of the signing key to the trustees, while creating the CRV. Signing involves an untrusted aggregator communicating point-to-point with a set of trustees. Only the aggregator needs access to the CRV; the trustees need only a PRF key and enough space to remember which one-time keys they have helped to sign with so far. Signing requires two round trips between the aggregator and each participating trustee, and only a little more computation from the trustees and aggregator than is done when signing with the underlying HBS scheme. We reduce the security of our scheme to that of the underlying HBS scheme, assuming the availability of a secure PRF. A dishonest aggregator or tampered CRV can prevent valid signatures from being constructed, but does not allow forgeries. Our techniques offer a powerful practical defense against accidental reuse of a one-time key in stateful HBS schemes by requiring multiple trustees to fail in the same way in order for key reuse to occur. </p
A Holistic Framework for Impossible Boomerang Attacks
Full text linkIn 2011, Lu introduced the impossible boomerang attack at DCC. This powerful cryptanalysis technique combines the strengths of the impossible differential and boomerang attacks, thereby inheriting the advantages of both cryptographic techniques. In this paper, we propose a holistic framework comprising two generic and effective algorithms and a MILP-based model to search for the optimal impossible boomerang attack systematically. The first algorithm incorporates any key guessing strategy, while the second integrates the meet-in-the-middle (MITM) attack into the key recovery process. The MILP-based model combines the generic key recovery algorithms and supports the arbitrary location of the contradiction. Our highly flexible framework treats the distinguisher and the extended part as a whole, returning the optimal attack parameters and complexity. When applying our framework to Deoxys-BC-256, Deoxys-BC-384, Joltik-BC-128, Joltik-BC-192, and SKINNYe v2, we achieve several significant improvements. We achieve the first 11-round impossible boomerang attacks on Deoxys-BC-256 and Joltik-BC-128. For SKINNYe v2, we achieve the first 33-round impossible boomerang attack, then using the MITM approach in the key recovery attack, the time complexity is significantly reduced. Additionally, for the 14-round Deoxys-BC-384 and Joltik-BC-192, the time complexity of the impossible boomerang attack is reduced by factors exceeding and , respectively. </p
Post-Quantum Access Control with Application to Secure Data Retrieval
Full text link Servan-Schreiber et al. [IEEE S& P, 2023] presented a new notion called private access control lists (PACL) for function secret sharing (FSS), where the FSS evaluators can ensure that the FSS dealer is authorized to share the given function. Their construction relies on costly non-interactive secret-shared proofs and is not secure in the post-quantum setting. We give a construction of PACL from publicly verifiable secret sharing (PVSS) under the short integer solution (SIS) problem. Our construction adapts the Gentry et al.\u27s scheme [EUROCRYPT, 2022] for the post-quantum setting based on the learning with error (LWE) assumption aimed at ensuring that database access control policies are enforced by FSS evaluators, who verify that the FSS dealer is authorized to share the specified database query function. The benchmarks of our PACL show a trade-off between proving and verification efficiency, making the optimal choice dependent on application requirements. This construction has many applications for access control by applying FSS. We also present a secure data retrieval scheme using DPF-PACL for access control, which complements the PACL framework while providing independent utility. </p
Fly Away: Lifting Fault Security through Canaries and the Uniform Random Fault Model
Full text linkCryptographic implementations are vulnerable to active physical attacks where adversaries inject faults to extract sensitive information. Existing fault models, such as the threshold and random fault models, assume limitations on the amount or probability of injecting faults. Such models, however, insufficiently address the case of practical fault injection methods capable of faulting a large proportion of the wires in a circuit with high probability. Prior works have shown that this insufficiency can lead to concrete key recovery attacks against implementations proven secure in these models. We address this blind spot by introducing the uniform random fault model, which relaxes assumptions on the amount/probability of faults and instead assumes a uniform probabilistic faulting of all wires in a circuit or region. We then show that security in this new model can be reduced to security in the random fault model by inserting canaries in the circuit to ensure secret-independent fault detection. We prove that combining canaries with a more classical fault countermeasure such as redundancy can lead to exponential fault security in the uniform random fault model at a polynomial cost in circuit size in the security parameter. Finally, we discuss the interactions between our work and the practical engineering challenges of fault security, shedding light on how the combination of state-of-the-art countermeasures may protect against injections of many high probability faults, while opening a path to methodologies that formally analyze the guarantees provided by such countermeasures. </p
Tightly Secure Threshold Signatures over Pairing-Free Groups
Full text link Threshold signatures have been drawing lots of attention in recent years. Of particular interest are threshold signatures that are proven secure under adaptive corruptions (NIST Call 2023). Sadly, existing constructions with provable adaptive security suffer from at least one of the following drawbacks: (i) strong idealizations such as the algebraic group model (AGM), (ii) an unnatural restriction on the corruption threshold being t/2 where t is the signing threshold, or (iii) prohibitively large security loss under established assumptions. Notably, point (iii) has received little to no attention in the literature on this subject. In this work, we introduce Twinkle-T, a new threshold signature scheme which overcomes these limitations. Twinkle-T is the first scheme to have a fully tight security proof under up to t adaptive corruptions without relying on the AGM. It also has a signing protocol consisting of only three rounds and thus matches the currently best threshold signature with full adaptive security Twinkle (Eurocrypt 2024) in the pairing-free discrete logarithm setting. We prove security from a standard non-interactive assumption, namely, the Decisional Diffie-Hellman (DDH) assumption, in the random oracle model. </p
AKE Protocol Combining PQC and QKD
Full text linkWith the advent of quantum computing, which threatens the very foundations of classical cryptography, several authenticated key exchange (AKE) protocols have been proposed, combining classical and post-quantum cryptographic algorithms, and a quantum key distribution (QKD) sub-protocol. The goal being to associate the claimed information theoretic security of QKD, and the security based upon computational assumptions of classical and post-quantum cryptography. To our knowledge, in existing security proofs of such hybrid AKE protocols, the QKD phase is treated as a black box and the impact of establishing the output quantum key appears similar as setting a symmetric key beforehand at the two communicating parties. In this paper, we describe an hybrid AKE protocol and a security model that captures multiple security properties. Our security analysis integrates the security loss induced by the QKD phase as well as that of implied by the classical and post-quantum cryptographic algorithms involved in the protocol. </p