IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
31 May 2023
Paderborn University, Institute of Computer Science/Codes and Cryptography Group; Paderborn, Germany
Paderborn University is a high-performance and internationally oriented campus university with around 20,000 students. In interdisciplinary teams, we shape future-oriented research, innovative teaching and the active transfer of knowledge to society. As an important research and cooperation partner, the university also shapes regional development strategies.
The Faculty of Electrical Engineering, Computer Science and Mathematics - Institute of Computer Science / Codes and Cryptography Group - has a vacancy (100% of the regular working time) at the earliest opportunity:
Research Assistant (f/m/d) (salary is according to 13 TV-L)
This is a qualification position within the meaning of the Wissenschaftszeitvertragsgesetz (WissZeitVG - German Act on Scientific Temporary Contracts), which serves to promote a doctoral procedure or an early postdoc phase in the field of "Codes and Cryptography". The position is to be filled for a limited period, depending on the qualification achieved to date, but generally for a period of 3 years. An extension is possible within the time limits of the WissZeitVG if applicable.
Your duties and responsibilities
Research in one of the following areas:
- Cryptography and quantum cryptography
- Algorithmic number theory and complexity theory
- Quantum algorithms and quantum complexity
- Teaching on the order of 4 teaching hours (SWS) per week
Hiring requirement: Scientific Master degree in computer science, mathematics of physics
Since Paderborn University seeks to increase the number of female scientists, applications of women are especially welcome. In case of equal qualification and scientific achievements, they will receive preferential treatment according to the North Rhine-Westphalian Equal Opportunities Policy (LGG), unless there are cogent reasons to give preference to another applicant. Part-time employment is possible. Likewise, applications of disabled people with appropriate qualification are explicitly requested. This also applies to people with equal status according to the German social law SGB IX.
The Faculty of Electrical Engineering, Computer Science and Mathematics - Institute of Computer Science / Codes and Cryptography Group - has a vacancy (100% of the regular working time) at the earliest opportunity:
Research Assistant (f/m/d) (salary is according to 13 TV-L)
This is a qualification position within the meaning of the Wissenschaftszeitvertragsgesetz (WissZeitVG - German Act on Scientific Temporary Contracts), which serves to promote a doctoral procedure or an early postdoc phase in the field of "Codes and Cryptography". The position is to be filled for a limited period, depending on the qualification achieved to date, but generally for a period of 3 years. An extension is possible within the time limits of the WissZeitVG if applicable.
Your duties and responsibilities
Research in one of the following areas:
- Cryptography and quantum cryptography
- Algorithmic number theory and complexity theory
- Quantum algorithms and quantum complexity
- Teaching on the order of 4 teaching hours (SWS) per week
Hiring requirement: Scientific Master degree in computer science, mathematics of physics
Since Paderborn University seeks to increase the number of female scientists, applications of women are especially welcome. In case of equal qualification and scientific achievements, they will receive preferential treatment according to the North Rhine-Westphalian Equal Opportunities Policy (LGG), unless there are cogent reasons to give preference to another applicant. Part-time employment is possible. Likewise, applications of disabled people with appropriate qualification are explicitly requested. This also applies to people with equal status according to the German social law SGB IX.
Closing date for applications:
Contact: Please send your application including a CV (preferably in a single pdf file) using the Ref. No. 5963 by 30 June 2023 to: bloemer@upb.de.
Prof. Dr. Johannes Blömer
Faculty of Computer Science, Electrical Engineering and Mathematics
Paderborn University
Warburger Str. 100
33098 Paderborn
More information: https://cs.uni-paderborn.de/en/cuk/research
Abu Dhabi, United Arab Emirates, 5 March - 8 March 2024
Event date: 5 March to 8 March 2024
Submission deadline: 20 July 2023
Notification: 12 September 2023
Submission deadline: 20 July 2023
Notification: 12 September 2023
Darmstadt, Germany, 3 June - 6 June 2024
Event date: 3 June to 6 June 2024
30 May 2023
Steve Thakur
We describe a pairing-based SNARK with a universal updateable CRS that can be instantiated with any pairing-friendly curve endowed with a sufficiently large prime scalar field. We use the monomial basis, thus sidestepping the need for large smooth order subgroups in the scalar field. In particular, the scheme can be instantiated with outer curves to widely used curves such as Ed25519, secp256k1 and BN254. This allows us to largely circumvent the overhead of non-native field arithmetic for succinct proofs of statements in these base fields. These include proofs of valid signatures in Ed25519 and secp256k1 and one layer recursion with BN254.
The proof size is constant \( (10\; \mathbb{G}_1\), \(20\;\mathbb{F}_p)\), as is the verification runtime, which is dominated by a single pairing check (i.e. two pairings). The Prover time is dominated by the \(10\) multi-scalar multiplications in \(\mathbb{G}_1\) - with a combined MSM length of $22\cdot |\mathrm{Circuit}|$ - and, to a lesser extent, the computation of a single sum of polynomial products over the scalar field.
The scheme supports succinct lookup arguments for subsets as well as subsequences. Our construction relies on homomorphic table commitments, which makes them amenable to vector lookups. The Prover algorithm runs in runtime $O(M\cdot \log(M))$, where $M = \max \{|\text{Circuit}| , \;|\text{Table}|\}.$
When the scalar field has low $2$-adicity - as is inevitably the case with any outer curve to Ed25519, secp256k1 or BN254 - we use the Schonhage-Strassen algorithm or the multimodular FFT algorithm to compute the sum of polynomial products that occurs in one of the steps of the proof generation. Despite the small (but discernible) slowdown compared to polynomial products in FFT-friendly fields, we empirically found that the MSMs dominate the proof generation time. To that end, we have included some benchmarks for polynomial products in FFT-unfriendly fields.
Furthermore, the scheme supports custom gates, albeit at the cost of a larger proof size. As an application of the techniques in this paper, we describe a protocol that supports multiple \( \mathbf{univariate}\) custom gates $\mathcal{G}_i$ of high degree that are sparsely distributed, in the sense that \[ \sum_{i} \deg(\mathcal{G}_i)\cdot \#(\mathcal{G}_i\;\text{gates}) \; = \; O(|\text{Circuit}|). \] This comes at the cost of three additional $\mathbb{G}_1$ elements and does not blow up the proof generation time, i.e. it does not entail MSMs or FFTs of length larger than the circuit size.
At the moment, Panther Protocol's Rust implementation in a 576-bit pairing-friendly outer curve to Ed25519 has a (not yet optimized) Prover time of 45 seconds for a million gate circuit on a 64 vCPU AWS machine.
The proof size is constant \( (10\; \mathbb{G}_1\), \(20\;\mathbb{F}_p)\), as is the verification runtime, which is dominated by a single pairing check (i.e. two pairings). The Prover time is dominated by the \(10\) multi-scalar multiplications in \(\mathbb{G}_1\) - with a combined MSM length of $22\cdot |\mathrm{Circuit}|$ - and, to a lesser extent, the computation of a single sum of polynomial products over the scalar field.
The scheme supports succinct lookup arguments for subsets as well as subsequences. Our construction relies on homomorphic table commitments, which makes them amenable to vector lookups. The Prover algorithm runs in runtime $O(M\cdot \log(M))$, where $M = \max \{|\text{Circuit}| , \;|\text{Table}|\}.$
When the scalar field has low $2$-adicity - as is inevitably the case with any outer curve to Ed25519, secp256k1 or BN254 - we use the Schonhage-Strassen algorithm or the multimodular FFT algorithm to compute the sum of polynomial products that occurs in one of the steps of the proof generation. Despite the small (but discernible) slowdown compared to polynomial products in FFT-friendly fields, we empirically found that the MSMs dominate the proof generation time. To that end, we have included some benchmarks for polynomial products in FFT-unfriendly fields.
Furthermore, the scheme supports custom gates, albeit at the cost of a larger proof size. As an application of the techniques in this paper, we describe a protocol that supports multiple \( \mathbf{univariate}\) custom gates $\mathcal{G}_i$ of high degree that are sparsely distributed, in the sense that \[ \sum_{i} \deg(\mathcal{G}_i)\cdot \#(\mathcal{G}_i\;\text{gates}) \; = \; O(|\text{Circuit}|). \] This comes at the cost of three additional $\mathbb{G}_1$ elements and does not blow up the proof generation time, i.e. it does not entail MSMs or FFTs of length larger than the circuit size.
At the moment, Panther Protocol's Rust implementation in a 576-bit pairing-friendly outer curve to Ed25519 has a (not yet optimized) Prover time of 45 seconds for a million gate circuit on a 64 vCPU AWS machine.
Chenghong Wang, David Pujo, Kartik Nayak, Ashwin Machanavajjhala
Safety, liveness, and privacy are three critical properties for any private proof-of-stake (PoS) blockchain. However, prior work (SP'21) has shown that to obtain safety and liveness, a PoS blockchain must in theory forgo privacy. Specifically, to ensure safety and liveness, PoS blockchains elect parties based on stake proportion, potentially exposing a party's stake even with private transaction processing. In this work, we make two key contributions. First, we present the first stake inference attack applicable to both deterministic and randomized PoS with exponentially less running time in comparison with SOTA designs. Second, we use differentially private stake distortion to achieve privacy in PoS blockchains and design two stake distortion mechanisms that any PoS protocol can use. We further evaluate our proposed methods using Ethereum 2.0, a widely-recognized PoS blockchain in operation. Results demonstrate effective stake inference risk mitigation, reasonable privacy, and preservation of essential safety and liveness properties.
Zhipeng Wang, Xihan Xiong, William J. Knottenbelt
The ecosystem around blockchain and Decentralized Finance (DeFi) is seeing more and more interest from centralized regulators. For instance, recently, the US government placed sanctions on the largest DeFi mixer, Tornado.Cash (TC). To our knowledge, this is the first time that centralized regulators sanction a decentralized and open-source blockchain application. It has led various blockchain participants, e.g., miners/validators and DeFi platforms, to censor TC-related transactions. The blockchain community has extensively discussed that censoring transactions could affect users’ privacy.
In this work, we analyze the efficiency and possible security implications of censorship on the different steps during the life cycle of a blockchain transaction, i.e., generation, propagation, and validation. We reveal that fine-grained censorship will reduce the security of block validators and centralized transaction propagation services, and can potentially cause Denial of Service (DoS) attacks. We also find that DeFi platforms adopt centralized third-party services to censor user addresses at the frontend level, which blockchain users could easily bypass. Moreover, we present a tainting attack whereby an adversary can prevent users from interacting normally with DeFi platforms by sending TC-related transactions.
In this work, we analyze the efficiency and possible security implications of censorship on the different steps during the life cycle of a blockchain transaction, i.e., generation, propagation, and validation. We reveal that fine-grained censorship will reduce the security of block validators and centralized transaction propagation services, and can potentially cause Denial of Service (DoS) attacks. We also find that DeFi platforms adopt centralized third-party services to censor user addresses at the frontend level, which blockchain users could easily bypass. Moreover, we present a tainting attack whereby an adversary can prevent users from interacting normally with DeFi platforms by sending TC-related transactions.
Dmitrii Koshelev
This article is dedicated to a new generation method of two ``independent'' $\mathbb{F}_{\!q}$-points $P_0$, $P_1$ on almost any ordinary elliptic curve $E$ over a finite field $\mathbb{F}_{\!q}$ of large characteristic. In particular, the method is relevant for all standardized and real-world elliptic curves of $j$-invariants different from $0$, $1728$. The points $P_0$, $P_1$ are characterized by the fact that nobody (even a generator) knows the discrete logarithm $\log_{P_0}(P_1)$ in the group $E(\mathbb{F}_{\!q})$. Moreover, only one square root extraction in $\mathbb{F}_{\!q}$ (instead of two ones) is required in comparison with all previous generation methods.
Alessio Meneghetti, Edoardo Signorini
A sequential aggregate signature (SAS) scheme allows multiple users to sequentially combine their respective signatures in order to reduce communication costs. Historically, early proposals required the use of trapdoor permutation (e.g., RSA).
In recent years, a number of attempts have been made to extend SAS schemes to post-quantum assumptions. Many post-quantum signatures have been proposed in the hash-and-sign paradigm, which requires the use of trapdoor functions and appears to be an ideal candidate for sequential aggregation attempts. However, the hardness in achieving post-quantum one-way permutations makes it difficult to obtain similarly general constructions. Direct attempts at generalizing permutation-based schemes have been proposed, but they either lack formal security or require additional properties on the trapdoor function, which are typically not available for multivariate or code-based functions.
In this paper, we propose a history-free sequential aggregate signature based on generic trapdoor functions, generalizing existing techniques. We prove the security of our scheme in the random oracle model by adopting the probabilistic hash-and-sign with retry paradigm, and we instantiate our construction with three post-quantum schemes, comparing their compression capabilities. Finally, we discuss how direct extensions of permutation-based SAS schemes are not possible without additional properties, showing the insecurity of two existing multivariate schemes when instantiated with Unbalanced Oil and Vinegar.
Andrea Di Giusto, Chiara Marcolla
The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is a Fully Homomorphic Encryption (FHE) cryptosystem based on the Ring Learning With Error (RLWE) problem.
Ciphertexts in this scheme contain an error term that grows with operations and causes decryption failure when it surpasses a certain threshold.
For this reason, the parameters of BGV need to be estimated carefully, with a trade-off between security and error margin.
The ciphertext space of BGV is the ring $\mathcal R_q=\mathbb Z_q[x]/(\Phi_m(x))$, where usually the degree $n$ of the cyclotomic polynomial $\Phi_m(x)$ is chosen as a power of two for efficiency reasons. However, the jump between two consecutive powers-of-two polynomials can sometimes also cause a jump of the security, resulting in parameters that are much bigger than what is needed.
In this work, we explore the non-power-of-two instantiations of BGV. Although our theoretical research encompasses results applicable to any cyclotomic ring, our main investigation is focused on the case of $m=2^s 3^t$, i.e., cyclotomic polynomials with degree $n=2^s 3^{t-1}$. We provide a thorough analysis of the noise growth in this new setting using the canonical norm and compare our results with the power-of-two case considering practical aspects like NTT algorithms. We find that in many instances, the parameter estimation process yields better results for the non-power-of-two setting.
In this work, we explore the non-power-of-two instantiations of BGV. Although our theoretical research encompasses results applicable to any cyclotomic ring, our main investigation is focused on the case of $m=2^s 3^t$, i.e., cyclotomic polynomials with degree $n=2^s 3^{t-1}$. We provide a thorough analysis of the noise growth in this new setting using the canonical norm and compare our results with the power-of-two case considering practical aspects like NTT algorithms. We find that in many instances, the parameter estimation process yields better results for the non-power-of-two setting.
Fukang Liu, Lorenzo Grassi, Clémence Bouvier, Willi Meier, Takanori Isobe
Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known $\chi$ function over $\mathbb{F}_2^n$ and the power map over a large finite field $\mathbb{F}_{p^n}$. In this work, we study the growth of the algebraic degree for an SPN cipher over $\mathbb{F}_{2^n}^{m}$, whose S-box is defined as the combination of a power map $x\mapsto x^{2^d+1}$ and an $\mathbb{F}_2$-linearized affine polynomial $x\mapsto c_0+\sum_{i=1}^{w}c_ix^{2^{h_i}}$ where $c_1,\ldots,c_w\neq0$. Specifically, motivated by the fact that the original coefficient grouping technique published at EUROCRYPT 2023 becomes less efficient for $w>1$, we develop a variant technique that can efficiently work for arbitrary $w$. With this new technique to study the upper bound of the algebraic degree, we answer the following questions from a theoretic perspective:
1. can the algebraic degree increase exponentially when $w=1$?
2. what is the influence of $w$, $d$ and $(h_1,\ldots,h_w)$ on the growth of the algebraic degree?
Based on this, we show (i) how to efficiently find $(h_1,\ldots,h_w)$ to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary $(h_1,\ldots,h_w)$. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.
1. can the algebraic degree increase exponentially when $w=1$?
2. what is the influence of $w$, $d$ and $(h_1,\ldots,h_w)$ on the growth of the algebraic degree?
Based on this, we show (i) how to efficiently find $(h_1,\ldots,h_w)$ to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary $(h_1,\ldots,h_w)$. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.
Amit Singh Bhati, Antonin Dufka, Elena Andreeva, Arnab Roy, Bart Preneel
A Key Derivation Function KDF generates a uniform and highly random key-stream from weakly random key material. KDFs are broadly used in various security protocols such as digital signatures and key exchange protocols. HKDF is the most deployed KDF in practice. It is based on the $\textit{extract-then-expand}$ paradigm and is presently used, among others, in the Signal Protocol for end-to-end encrypted messaging.
HKDF was proposed as a generic KDF for general input sources and thus is not optimized for source-specific use cases such as key derivation from Diffie-Hellman (DH) sources (i.e. DH shared secrets as key material). Furthermore, the sequential HKDF design is unnecessarily slower on some general-purpose platforms that benefit from parallelization.
In this work, we propose a novel, efficient and secure KDF called $\mathsf{Skye}$. $\mathsf{Skye}$ follows the $\textit{extract-then-expand}$ paradigm and consists of two algorithms: efficient deterministic $\textit{randomness extractor}$ and $\textit{expansion}$ functions. Instantiating our extractor for dedicated source-specific (e.g. DH sources) inputs allows us to achieve a significant efficiency speed-up over HKDF at the same security level. We provide concrete security analysis of $\mathsf{Skye}$ and both its algorithms in the standard model.
We provide a software performance comparison of $\mathsf{Skye}$ with the AES-based expanding PRF $\mathsf{ButterKnife}$ and HKDF with SHA-256 (as used in Signal). Our results show that in isolation $\mathsf{Skye}$ performs from 4x to 47x faster than HKDF, depending on the platform instruction support. We further demonstrate that with such a performance gain, when $\mathsf{Skye}$ is integrated within the current Signal implementation, we can achieve significant overall improvements ranging from $38\%$ to $64\%$ relative speedup in unidirectional messaging. Even in bidirectional messaging, that includes DH computation with dominating computational cost, $\mathsf{Skye}$ still contributes to $12-36\%$ relative speedup when just 10 messages are sent and received at once.
Alia Umrani, Apurva K Vangujar, Paolo Palmieri
Confidentiality, authentication, and anonymity are the fundamental security requirements in broadcast communication that can be achieved by Digital Signature (DS), encryption, and pseudo-anonymous identity techniques. Signcryption offer both DS and encryption in a single logical step with high efficiency. Similarly, anonymous multireceiver signcryption ensure receiver privacy by generating identical ciphertext for multiple receivers while keeping their identities private. While signcryption is a significant improvement over “sign then encrypt”, it still incurs higher computational and communication cost and does not provide the required level of security.
In this paper, we propose a multiple-recipient Key Encapsulation Mechanism (mKEM) - Data Encapsulation Mechanism (DEM) based Anonymous Multireceiver Certificateless Hybrid Signcryption (AMCLHS). The AMCLHS uses a combination of symmetric key and asymmetric key cryptography to signcrypt an arbitrary length message in broadcast communication and has two unique settings as follows:
Pseudo-Identity PID Settings: We introduce a new algorithmic step in AMCLHS construction where each user (sender and receiver) is assigned a PID to enable the sender to signcrypt identical messages for multiple receivers while keeping the identities of other receivers anonymous.
The receiver anonymity is achieved by choosing random Real-Identity (ID_R) to generate PID of the users in key generation algorithm of AMCLHS scheme. Our approach relies on the Elliptic Curve Discrete Logarithm (ECDL) hardness assumptions, the hash function, and verification-based secret key of the Register Authority (RA), using time Delta T.
mKEM-DEM Settings: We introduce the first construction that achieves optimal ciphertext from the Diffie-Hellman (DH) assumption using mKEM-DEM for Signcryption. Our scheme uses mKEM to generate a symmetric key for multiple-receivers and DEM to signcrypt message using the previously generated symmetric key and the sender's private key. mKEM for key setup and Signcryption for confidentiality and forward security, and DEM for key generation and unsigncryption for indistinguishability under Indistinguishability against Chosen Ciphertext Attack (IND-CCA2).
Our scheme relies on DH and Bilinear Pairing (BP) assumption and uses a single key for all messages, which minimizes ciphertext length and ultimately reduces complexity overhead.
The scheme operates in a multireceiver certificateless environment, preventing the key escrow problem, and demonstrates cryptographic notions for Indistinguishability under Chosen-Ciphertext Attack (IND-CCA2) and Existential Unforgeability against Chosen Message Attack (EUF-CMA) for Type-I and Type-II adversaries under q-Decisional Bilinear Diffie-Hellman Inversion (q-DBDHI) and ECDL hard assumptions. We compare the proposed scheme with existing multireceiver hybrid signcryption schemes in terms of computation cost, communication cost, and security requirements. We show that, compared to existing multireceiver schemes which has overall cost of O(n^2), our scheme is computationally more efficient and has optimal communication cost, with signcryption cost linear O(n) to the number of designated receivers while the unsigncryption cost remains constant O(1). Our scheme achieves confidentiality, authentication, anonymity, and simultaneously achieves unlinkability, non-repudiation, and forward security.
Mingjie Chen, Muhammad Imran, Gábor Ivanyos, Péter Kutas, Antonin Leroux, Christophe Petit
The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic $p$ given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of
pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime.
In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(\log\log p)$ many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer $N$ with $O(\log\log p)$ many prime factors to powersmooth elements.
As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.
In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(\log\log p)$ many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer $N$ with $O(\log\log p)$ many prime factors to powersmooth elements.
As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.
Alex Ozdemir, Riad S. Wahby, Fraser Brown, Clark Barrett
Zero Knowledge Proofs (ZKPs) are cryptographic protocols
by which a prover convinces a verifier of the truth of a statement with-
out revealing any other information. Typically, statements are expressed
in a high-level language and then compiled to a low-level representation
on which the ZKP operates. Thus, a bug in a ZKP compiler can com-
promise the statement that the ZK proof is supposed to establish. This
paper takes a step towards ZKP compiler correctness by partially veri-
fying a field-blasting compiler pass, a pass that translates Boolean and
bit-vector logic into equivalent operations in a finite field. First, we define
correctness for field-blasters and ZKP compilers more generally. Next, we
describe the specific field-blaster using a set of encoding rules and de-
fine verification conditions for individual rules. Finally, we connect the
rules and the correctness definition by showing that if our verification
conditions hold, the field-blaster is correct. We have implemented our
approach in the CirC ZKP compiler and have proved bounded versions
of the corresponding verification conditions. We show that our partially
verified field-blaster does not hurt the performance of the compiler or its
output; we also report on four bugs uncovered during verification.
Alexander May, Julian Nowakowski
All modern lattice-based schemes build on variants of the LWE problem. Information leakage of the LWE secret $\mathbf s \in \mathbb{Z}_q^n$ is usually modeled via so-called hints, i.e., inner products of $\mathbf s$ with some (random, but known) vector.
At Crypto`20, Dachman-Soled, Ducas, Gong and Rossi (DDGR) defined among other so-called perfect hints and modular hints. The trailblazing DDGR framework allows to integrate and combine hints successively into lattices, and estimates the resulting LWE security loss.
We introduce a new methodology to integrate and combine an arbitrary number of perfect and modular in a single stroke. As opposed to DDGR, our methodology is significantly more efficient in constructing lattice bases, and thus easily allows for a large number of hints up to cryptographic dimensions, a regime that is impractical in DDGR. The efficiency of our method defines a large LWE parameter regime, in which we can fully carry out attacks faster than DDGR can solely estimate them. A key component of our new method is dimension reduction of $\mathbf s$, which significantly reduces LWE security.
The benefits of our approach allow us to practically determine which number of hints is sufficient to efficiently break LWE-based lattice schemes in practice. For mod-$q$ hints, i.e., modular hints defined over $\mathbb{Z}_q$, we reconstruct Kyber-512 secret keys via LLL reduction (only!) with an amount of $449$ hints. For Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we need $452$, $622$, $702$ and $876$ modular hints, respectively. Our results for perfect hints significantly improve over these numbers, requiring for LWE dimension $n$ roughly $n/2$ perfect hints. Namely, we reconstruct via LLL reduction Kyber-512 keys with merely $234$ perfect hints. For secret keys of Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we require $233$, $332$, $390$ and $463$ perfect hints, respectively. We find such a small amount of perfect hints quite remarkable. If we resort to stronger lattice reduction techniques like BKZ, we need even fewer hints.
For mod-$q$ hints our method is extremely efficient, taking total time for constructing our lattice bases and secret key recovery via LLL of around 20 mins for dimension 512, 40 mins for dimensions 701 and 768, and less than 10 hours for dimension 1024. For perfect hints we require around 3 hours (dim 512), 11 hours (dim 701), 1 day (dim 768), and one week (dim 1024).
Our results demonstrate that especially perfect hints are powerful in practice, and stress the necessity to properly protect lattice schemes against leakage.
At Crypto`20, Dachman-Soled, Ducas, Gong and Rossi (DDGR) defined among other so-called perfect hints and modular hints. The trailblazing DDGR framework allows to integrate and combine hints successively into lattices, and estimates the resulting LWE security loss.
We introduce a new methodology to integrate and combine an arbitrary number of perfect and modular in a single stroke. As opposed to DDGR, our methodology is significantly more efficient in constructing lattice bases, and thus easily allows for a large number of hints up to cryptographic dimensions, a regime that is impractical in DDGR. The efficiency of our method defines a large LWE parameter regime, in which we can fully carry out attacks faster than DDGR can solely estimate them. A key component of our new method is dimension reduction of $\mathbf s$, which significantly reduces LWE security.
The benefits of our approach allow us to practically determine which number of hints is sufficient to efficiently break LWE-based lattice schemes in practice. For mod-$q$ hints, i.e., modular hints defined over $\mathbb{Z}_q$, we reconstruct Kyber-512 secret keys via LLL reduction (only!) with an amount of $449$ hints. For Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we need $452$, $622$, $702$ and $876$ modular hints, respectively. Our results for perfect hints significantly improve over these numbers, requiring for LWE dimension $n$ roughly $n/2$ perfect hints. Namely, we reconstruct via LLL reduction Kyber-512 keys with merely $234$ perfect hints. For secret keys of Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we require $233$, $332$, $390$ and $463$ perfect hints, respectively. We find such a small amount of perfect hints quite remarkable. If we resort to stronger lattice reduction techniques like BKZ, we need even fewer hints.
For mod-$q$ hints our method is extremely efficient, taking total time for constructing our lattice bases and secret key recovery via LLL of around 20 mins for dimension 512, 40 mins for dimensions 701 and 768, and less than 10 hours for dimension 1024. For perfect hints we require around 3 hours (dim 512), 11 hours (dim 701), 1 day (dim 768), and one week (dim 1024).
Our results demonstrate that especially perfect hints are powerful in practice, and stress the necessity to properly protect lattice schemes against leakage.
Hong-Wei Sun, Bin-Bin Cai, Su-Juan Qin, Qiao-Yan Wen, Fei Gao
Generalized Feistel schemes (GFSs) are extremely important and extensively researched cryptographic schemes. In this paper, we investigate the security of Type-1 GFS in quantum circumstances. On the one hand, in the qCCA setting, we give a new quantum polynomial time distinguisher on (d^2 -1)-round Type-1 GFS with branches d >3, which extends the previous results by d-2 rounds. This leads to a more efficient analysis of type-1 GFS, that is, the complexity of some previous key-recovery attacks is reduced by a factor of 2^(((d-2)k)/2), where k is the key length of the internal round function. On the other hand, for CAST-256, which is a certain block cipher based on Type-1 GFS, we give a 17-round quantum distinguisher in the qCPA setting. As a result, we construct an r(r > 17) round quantum key-recovery attack with complexity O(2^(37(r-17))/2 ).
Bishwajit Chakraborty, Chandranan Dhar, Mridul Nandi
The Ascon cipher suite, offering both authenticated encryption with associated data (AEAD) and hashing functionality, has recently emerged as the winner of the NIST Lightweight Cryptography (LwC) standardization process. The AEAD schemes within Ascon, namely Ascon-128 and Ascon-128a, have also been previously selected as the preferred lightweight authenticated encryption solutions in the CAESAR competition. In this paper, we present a tight and comprehensive security analysis of the Ascon AEAD schemes within the random permutation model. Existing integrity analyses of Ascon (and any Duplex AEAD scheme in general) commonly include the term $DT/2^c$, where $D$ and $T$ represent data and time complexities respectively, and $c$ denotes the capacity of the underlying sponge. In this paper, we demonstrate that Ascon achieves AE security when $T$ is bounded by $\min\{2^{\kappa}, 2^c\}$ (where $\kappa$ is the key size), and $DT$ is limited to $2^b$ (with $b$ being the size of the underlying permutation, which is 320 for Ascon). Our findings indicate that in accordance with NIST requirements, Ascon allows for a tag size as low as 64 bits while enabling a higher rate of 192 bits, surpassing the recommended rate.
Yiming Li, Shengli Liu
Chameleon hash (CH) is a trapdoor hash function. Generally it is hard to find collisions, but with the help of trapdoor, finding collisions becomes easy. CH plays an important role in converting a conventional blockchain to a redactable one. However, most of the existing CH schemes are too weak to support redactable blockchain. The currently known CH schemes serving for redactable blockchain have the best security of so-called “full collision resistance (f-CR)”, but they are built either on random oracle model or rely on heavy tools like the simulation-sound extractable non-interactive zero-knowledge (SSE-NIZK) proof system. Moreover, up to now there is no CH scheme with post-quantum f-CR security in the standard model. Therefore, no CH can support redactable blockchain in a post-quantum way without relying on random oracles.
In this paper, we introduce a variant of CH, namely tagged chameleon hash (tCH). Tagged chameleon hash takes a tag into hash evaluations and collision finding algorithms. We define two security notions for tCH, collision resistance (CR) and full collision resistance (f-CR), and prove the equivalence between CR and f-CR when tCH works in the one-time tag mode. We propose a tCH scheme from lattice without using any NIZK proof, and prove that its collision resistance is (almost) tightly reduced to the Short Integer Solution (SIS) assumption in the standard model. We also show how to apply tCH to a blockchain in one-time tag mode so that the blockchain can be compiled to a redactable one. Our tCH scheme provides the first post-quantum solution for redactable blockchains, without resorting to random oracles or NIZK proofs. Besides, we also construct a more efficient tCH scheme with CR tightly reduced to SIS in the random oracle model, which may be of independent interest.
In this paper, we introduce a variant of CH, namely tagged chameleon hash (tCH). Tagged chameleon hash takes a tag into hash evaluations and collision finding algorithms. We define two security notions for tCH, collision resistance (CR) and full collision resistance (f-CR), and prove the equivalence between CR and f-CR when tCH works in the one-time tag mode. We propose a tCH scheme from lattice without using any NIZK proof, and prove that its collision resistance is (almost) tightly reduced to the Short Integer Solution (SIS) assumption in the standard model. We also show how to apply tCH to a blockchain in one-time tag mode so that the blockchain can be compiled to a redactable one. Our tCH scheme provides the first post-quantum solution for redactable blockchains, without resorting to random oracles or NIZK proofs. Besides, we also construct a more efficient tCH scheme with CR tightly reduced to SIS in the random oracle model, which may be of independent interest.
Alexandre Adomnicai
This note provides an update on Keccak performance on the ARMv7-M processors. Starting from the XKCP implementation, we have applied architecture-specific optimizations that have yielded a performance gain of up to 21% for the largest permutation instance.
Zhiyu Zhang, Siwei Sun, Caibing Wang, Lei Hu
At EUROCRYPT 2006, Kelsey and Kohno proposed the so-called chosen target forced-prefix (CTFP) preimage attack, where for any challenge prefix $P$, the attacker can generate a suffix $S$ such that $H(P\|S) = y$ for some hash value $y$ published in advance by the attacker. Consequently, the attacker can pretend to predict some event represented by $P$ she did not know before, and thus this type of attack is also known as the Nostradamus attack. At ASIACRYPT 2022, Benedikt et al. convert Kelsey et al.'s attack to a quantum one, reducing the time complexity from $\mathcal{O}(\sqrt{n}\cdot 2^{2n/3})$ to $\mathcal{O}(\sqrt[3]{n} \cdot 2^{3n/7})$. CTFP preimage attack is less investigated in the literature than (second-)preimage and collision attacks and lacks dedicated methods. In this paper, we propose the first dedicated Nostradamus attack based on the meet-in-the-middle (MITM) attack, and the MITM Nostradamus attack could be up to quadratically accelerated in the quantum setting. According to the recent works on MITM preimage attacks on AES-like hashing, we build an automatic tool to search for optimal MITM Nostradamus attacks and model the tradeoff between the offline and online phases. We apply our method to AES-MMO and Whirlpool, and obtain the first dedicated attack on round-reduced version of these hash functions. Our method and automatic tool are applicable to other AES-like hashings.