IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Hash-Based Multi-Signatures for Post-Quantum Ethereum
Get PDFWith the threat posed by quantum computers on the horizon, systems like Ethereum must transition to cryptographic primitives resistant to quantum attacks. One of the most critical of these primitives is the non-interactive multi-signature scheme used in Ethereum\u27s proof-of-stake consensus, currently implemented with BLS signatures. This primitive enables validators to independently sign blocks, with their signatures then publicly aggregated into a compact aggregate signature.In this work, we introduce a family of hash-based signature schemes as post-quantum alternatives to BLS. We consider the folklore method of aggregating signatures via (hash-based) succinct arguments, and our work is focused on instantiating the underlying signature scheme. The proposed schemes are variants of the XMSS signature scheme, analyzed within a novel and unified framework. While being generic, this framework is designed to minimize security loss, facilitating efficient parameter selection. A key feature of our work is the avoidance of random oracles in the security proof. Instead, we define explicit standard model requirements for the underlying hash functions. This eliminates the paradox of simultaneously treating hash functions as random oracles and as explicit circuits for aggregation. Furthermore, this provides cryptanalysts with clearly defined targets for evaluating the security of hash functions. Finally, we provide recommendations for practical instantiations of hash functions and concrete parameter settings, supported by known and novel heuristic bounds on the standard model properties. </p
Goldreich-Krawczyk Revisited: A Note on the Zero Knowledge of Proofs of Knowledge
Get PDFThe seminal work of Goldreich and Krawczyk (SIAM Journal on Computing) shows that any constant-round public-coin interactive proof for languages not in cannot be black-box zero knowledge. Their result says nothing, however, about proofs (or arguments) of knowledge for languages in . As a special case, their work leaves open the question of whether Schnorr\u27s protocol for proving knowledge of discrete logarithms in cyclic groups is black-box zero knowledge.In this work we focus on the zero knowledge of proofs of knowledge, centering on Schnorr\u27s protocol as a prominent example. We prove two lower bounds, ruling out two different classes of simulators through which Schnorr\u27s protocol can be proven zero knowledge: We prove that if a relation has a public-coin interactive proof of knowledge that is black-box zero knowledge and this protocol is compatible with the Fiat-Shamir transform in the random oracle model, then must be efficiently searchable. As an immediate corollary, we deduce that Schnorr\u27s protocol cannot be black-box zero knowledge in groups in which discrete log is hard. We define a new class of simulators for Schnorr\u27s protocol, which we call generic simulators. A generic simulator is one that works in any cyclic group, and does not use the representation of the specific group in which Schnorr\u27s protocol is instantiated. We prove that Schnorr\u27s protocol cannot have generic simulators. As an additional contribution, we generalize the original lower bound of Goldreich and Krawczyk, to prove that a language not in cannot have an interactive proof (not necessarily of knowledge) that is both black-box zero knowledge and compatible with the Fiat-Shamir transform in the random oracle model. In conjunction with recent works, this extends the Goldreich-Krawczyk lower bound to public-coin protocols that are not constant-round but have round-by-round soundness, including the parallel repetition of any public-coin interactive proof. </p
Accurate and Composable Noise Estimates for CKKS with Application to Exact HE Computation
Get PDFAll RLWE-based FHE schemes are inherently noisy. The CKKS scheme (Cheon, Kim, Kim, Song, Asiacrypt 2017) considers the noise as a part of the message, yielding approximate computations but also considerable performance gains. Since it grows with each homomorphic operation and incurs a precision loss, it is paramount for users to be able to estimate the noise level throughout a given circuit in order to appropriately estimate parameters and control the precision loss in the message. In this work, we develop a noise model that allows for tight estimates of the precision loss, and propose a tool prototype for computing these estimates on any given circuit. Our noise model relies on a novel definition, the component-wise noise, which makes the average-case noise estimates tighter and more composable. As a result, our model and tool can derive accurate estimates of complex circuits such as bootstrapping. We experimentally demonstrate the tightness of our noise estimates by showing that our theoretical estimates never deviate by more than 0.01 bits from experimental estimates, even for large circuits, and hold with high probability. Furthermore, we demonstrate how to apply our techniques to obtain an exact version of the CKKS scheme in which the decryption removes all the noise (with high probability). Such a scheme has many applications, as it allows to take advantage of the efficiency of CKKS, while preserving an exact message space, hence further strengthening CKKS against IND-CPA-D attacks. </p
Optimizing Key Recovery in Classic McEliece: Advanced Error Correction for Noisy Side-Channel Measurements
Get PDFClassic McEliece was one of the code-based Key Encapsulation Mechanism finalists in the NIST post-quantum cryptography standardization process. Several key-recovery side-channel attacks on the decapsulation algorithm have already been published. However none of them discusses the feasibility and/or efficiency of the attack in the case of noisy side-channel acquisitions. In this paper, we address this issue by proposing two improvements on the recent key-recovery attack published by Drăgoi et al.. First, we introduce an error correction algorithm for the lists of Hamming weights obtained by side-channel measurements, based on the assumption, validated experimentally, that the error on a recovered Hamming weight is bounded to . We then offer a comparison between two decoding efficiency metrics, the theoretical minimal error correction capability and an empirical average correction probability. We show that the minimal error correction capability, widely used for linear codes, is not suitable for the (non-linear) code formed by the lists of Hamming weights. Conversely, experimental results show that out of 1 million random erroneous lists of Hamming weights, only 2 could not be corrected by the proposed algorithm. This shows that the probability of successfully decoding a list of erroneous Hamming weights is very high, regardless of the error weight. In addition to this algorithm, we describe how the secret Goppa polynomial , recovered during the first step of the attack, can be exploited to reduce both the time and space complexity of recovering the secret permuted support . </p
Cracking the Mask: SASCA Against Local-Masked NTT for CRYSTALS-Kyber
Get PDF Soft-Analytical Side-Channel Attacks (SASCAs) on lattice-based cryptography implementations have become a prominent vector of attack in the recent years, specially against the Number-Theoretic Transform (NTT). To address this issue, local masking with twiddle factors has been proposed as a countermeasure to protect the NTT against such attacks. In this paper we propose an adaptation of SASCA to local-masked NTT implementations, by modifying the factor graph representation to include the masking nodes. We evaluate the success rate of the attack with respect to the level of noise of simulated traces and the number of masks per layer. We show that the attack proves very successful in the lower values of , by even outperforming the attack on the unmasked case. When is increased there is a gradual augmentation of security, which comes with an important overhead on performance. Thus, we question the practicality of this countermeasure when compared to other analyzed countermeasures in the state of the art, such as shuffling. </p
On Round-Optimal Computational VSS
Get PDF In ASIACRYPT 2011, Backes, Kate, and Patra (BKP) introduced two computationally secure round-optimal (2-round) Verifiable Secret Sharing (VSS) schemes in the honest-majority setting, one based on non-homomorphic commitments and the other on homomorphic ones. Their scheme based on non-homomorphic commitments has computational complexity and necessitates public and private communication for the dealer, where denotes the number of parties and is the security parameter. They showed that these costs are times higher compared to their round-optimal VSS scheme employing homomorphic commitments and posed a research question regarding the inevitability of this gap. In this paper, we fill this gap by introducing a new variant of the recently proposed unified framework by Baghery at PKC 2025, designed to enable the construction of more efficient round-optimal VSS schemes in the honest-majority setting. Compared to the original framework, our variant reduces the required rounds by one while maintaining compatibility with any commitments and achieving comparable efficiency. Leveraging this new general construction, we develop several round-optimal VSS schemes that surpass state-of-the-art alternatives. Particularly noteworthy is the new round-optimal VSS scheme based on non-homomorphic commitments, which improves the BKP scheme by a factor of across all efficiency metrics. Compared to their schemes based on homomorphic commitments, our schemes demonstrate significantly expedited verification and reconstruction. Implementation results further validate the practicality of these new VSS schemes. For example, for , where represents the threshold, compared to the hash-based BKP VSS scheme, our proposed scheme showcases speed-ups exceeding (and ) for the dealer (and parties, respectively), while also requiring (and ) less communication. </p
Exponent-Inversion P-Signatures and Accountable Identity-Based Encryption from SXDH
Get PDFSalient in many cryptosystems, the exponent-inversion technique began without randomization in the random oracle model (SCIS \u2703, PKC \u2704), evolved into the Boneh-Boyen short signature scheme (JoC \u2708) and exerted a wide influence. Seen as a notable case, Gentry\u27s (EuroCrypt \u2706) identity-based encryption (IBE) applies exponent inversion on a randomized base in its identity-based trapdoors. Making use of the non-static q-strong Diffie-Hellman assumption, Boneh-Boyen signatures are shown to be unforgeable against q-chosen-message attacks, while a variant q-type decisional assumption is used to establish the security of Gentry-IBE. Challenges remain in proving their security under weaker static assumptions.Supported by the dual form/system framework (Crypto \u2709, AsiaCrypt \u2712), we propose dual form exponent-inversion Boneh-Boyen signatures and Gentry-IBE, with security proven under the symmetric external Diffie-Hellman (SXDH) assumption. Starting from our signature scheme, we extend it into P-signatures (TCC \u2708), resulting in the first anonymous credential scheme from the SXDH assumption, serving as a competitive alternative to the static-assumption construction of Abe et al. (JoC \u2716). Moreover, from our Gentry-IBE variant, we propose an accountable-authority IBE scheme also from SXDH, surpassing the fully secure Sahai-Seyalioglu scheme (PKC \u2711) in efficiency and the generic Kiayias-Tang transform (ESORICS \u2715) in security. Collectively, we present a suite of results under static assumptions. </p
Discrete Logarithm Factory
Get PDFThe Number Field Sieve and its variants are the best algorithms to solve the discrete logarithm problem in finite fields (except for the weak small characteristic case). The Factory variant accelerates the computation when several prime fields are targeted. This article adapts the Factory variant to non-prime finite fields of medium and large characteristic. A precomputation, solely dependent on an approximate finite field size and an extension degree, allows to efficiently compute discrete logarithms in a constant proportion of the finite fields of the given approximate size and extension degree. We combine this idea with two other variants of NFS, namely the tower and special variant. This combination improves the asymptotic complexity. We also notice that combining our approach with the MNFS variant would be an unnecessary complication as all the potential gain of MNFS is subsumed by our Factory variant anyway. Furthermore, we demonstrate how Chebotarev\u27s density theorem allows to compute the density of finite fields that can be solved with a given precomputation. Finally, we provide experimental data in order to assess the practical reach of our approach. </p
The Perils of Limited Key Reuse: Adaptive and Parallel Mismatch Attacks with Post-processing Against Kyber
Get PDF The Module Learning With Errors (MLWE)-based Key Encapsulation Mechanism (KEM) Kyber is NIST\u27s new standard scheme for post-quantum encryption. As a building block, Kyber uses a Chosen Plaintext Attack (CPA)-secure Public Key Encryption (PKE) scheme, referred to as Kyber.CPAPKE. In this paper we study the robustness of Kyber.CPAPKE against key mismatch attacks. We demonstrate that Kyber\u27s security levels can be compromised if having access to a few mismatch queries of Kyber.CPAPKE, by striking a balance between the parallelization level and the cost of lattice reduction for post-processing. This highlights the imperative need to strictly prohibit key reuse in Kyber.CPAPKE.We further propose an adaptive method to enhance parallel mismatch attacks, initially proposed by Shao et al. at AsiaCCS 2024, thereby significantly reducing query complexity. This method combines the adaptive attack with post-processing via lattice reduction to retrieve the final secret key entries. Our method proves its efficacy by reducing query complexity by 14.6 % for Kyber512 and 7.5 % for Kyber768/Kyber1024.Furthermore, this approach has the potential to improve multi-value Plaintext-Checking (PC) oracle-based side-channel attacks and fault-injection attacks against Kyber itself.</p
Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?
Get PDFThe adversary model of white-box cryptography includes an extreme case where the adversary, sitting at the endpoint, has full access to a cryptographic scheme. Motivating by the fact that most existing white-box implementations focus on symmetric encryption, we present implementations for hash-based signatures so that the security against white-box attackers (who have read-only access to data with a size bounded by a space-hardness parameter M) depends on the availability of a white-box secure cipher (in addition to a general one-way function). We also introduce parameters and key-generation complexity results for white-box secure instantiation of stateless hash-based signature scheme SPHINCS+, one of the NIST selections for quantum-resistant digital signature algorithms, and its older version SPHINCS. We also present a hash tree-based solution for one-time passwords secure in a white-box attacker context. We implement the proposed solutions and share our performance results. </p