International Association
for Cryptologic Research

This paper explores the challenges and potential solutions of implementing the recommended upcoming post-quantum cryptography standards (the CRYSTALS-Dilithium and CRYSTALS-Kyber algorithms) on resource constrained devices. The high computational cost of polynomial operations, fundamental to cryptography based on ideal lattices, presents significant challenges in an efficient implementation. This paper proposes a hardware/software co-design strategy using RISC-V extensions to optimize resource utilization and speed up the number-theoretic transformations (NTTs). The primary contributions include a lightweight custom arithmetic logic unit (ALU), integrated into a 4-stage pipeline 32-bit RISC-V processor. This ALU is tailored towards the NTT computations and supports modular arithmetic as well as NTT butterfly operations. Furthermore, an extension to the RISC-V instruction set is introduced, with ten new instructions accessing the custom ALU to perform the necessary operations. The new instructions reduce the cycle count of the Kyber and Dilithium NTTs by more than 80% compared to optimized assembly, while being more lightweight than other works that exist in the literature.

In the algebraic group model (AGM), an adversary has to return with each group element a linear representation with respect to input group elements. In many groups, it is easy to sample group elements obliviously without knowing such linear representations. Since the AGM does not model this, it can be used to prove the security of spurious knowledge assumptions. We show several well-known zk-SNARKs use such assumptions. We propose AGM with oblivious sampling (AGMOS), an AGM variant where the adversary can access an oracle that allows sampling group elements obliviously from some distribution. We show that AGM and AGMOS are different by studying the family of ``total knowledge-of-exponent'' assumptions, showing that they are all secure in the AGM, but most are not secure in the AGMOS if the DL holds. We show an important separation in the case of the KZG commitment scheme. We show that many known AGM reductions go through also in the AGMOS, assuming a novel falsifiable assumption TOFR. We prove that TOFR is secure in a version of GGM with oblivious sampling.

Zero-Knowledge Proofs (ZKPs), especially Succinct Non-interactive ARguments of Knowledge (SNARKs), have garnered significant attention in modern cryptographic applications. Given the multitude of emerging tools and libraries, assessing their strengths and weaknesses is nuanced and time-consuming. Often, claimed results are generated in isolation, and omissions in details render them irreproducible. The lack of comprehensive benchmarks, guidelines, and support frameworks to navigate the ZKP landscape effectively is a major barrier in the development of ZKP applications.

In response to this need, we introduce zk-Bench, the first benchmarking framework and estimator tool designed for performance evaluation of public-key cryptography, with a specific focus on practical assessment of general-purpose ZKP systems. To simplify navigating the complex set of metrics and qualitative properties, we offer a comprehensive open-source evaluation platform, which enables the rigorous dissection and analysis of tools for ZKP development to uncover their trade-offs throughout the entire development stack; from low-level arithmetic libraries, to high-level tools for SNARK development.

Using zk-Bench, we (i) collect data across $13$ different elliptic curves implemented across $9$ libraries, (ii) evaluate $5$ tools for ZKP development and (iii) provide a tool for estimating cryptographic protocols, instantiated for the $\mathcal{P}\mathfrak{lon}\mathcal{K}$ proof system, achieving an accuracy of 6 − 32% for ZKP circuits with up to millions of gates. By evaluating zk-Bench for various hardware configurations, we find that certain tools for ZKP development favor compute-optimized hardware, while others benefit from memory-optimized hardware. We observed performance enhancements of up to $40$ % for memory-optimized configurations and $50$ % for compute-optimized configurations, contingent on the specific ZKP development tool utilized.

The security level of a cipher is a key parameter. While general-purpose quantum computers significantly threaten modern symmetric ciphers, other quantum approaches like quantum annealing have been less concerning. However, this paper argues that a quantum annealer specifically designed to attack Grain 128 and Grain 128a ciphers could soon be technologically feasible. Such an annealer would require 5,751 (6,751) qubits and 77,496 (94,708) couplers, with a qubit connectivity of 225 (249). Notably, the forthcoming D-Wave Advantage 2 with Zephyr topology will feature over 7,000 qubits and 60,000 couplers and a qubit connectivity 20. This work also shows that modern stream ciphers like Grain 128 and Grain 128a could be vulnerable to quantum annealing attacks. Although the exact complexity of quantum annealing is unknown, heuristic estimates suggest a \(\sqrt{N}\) exponential advantage over simulated annealing for problems with \(N\) variables. We detail how to transform algebraic attacks on Grain ciphers into the QUBO problem, making our attack potentially more efficient than classical brute-force methods. We also show that applying our attack to rescaled versions of the Grain cipher, namely Grain \( l \) and Grain \( la \) versions, where \( l \) represents the key size, leads to our attack overtaking both brute-force and Grover's attacks for sufficiently large \( l \). This is true, provided that quantum annealing has an exponential advantage over simulated annealing. Specifically, it is sufficient for the time complexity of quantum annealing for problems with \( N \) variables to be $e^{N^{\beta}}$ for any \( \beta < 1 \). Finally, given the general nature of our attack method, all new ciphers should be scrutinized for vulnerability to quantum annealing attacks and at least match the AES cipher in terms of security level.

We improve the space efficiency of Regev's quantum factoring algorithm [Reg23] while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. In contrast, Regev's circuit requires $O(n^{3/2})$ qubits, while Shor's circuit requires $O(n^2)$ gates. As with Regev, to factor an $n$-bit integer $N$, one runs this circuit independently $\approx \sqrt{n}$ times and apply Regev's classical post-processing procedure.

Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2.

A succinct non-interactive argument (SNARG) is called holographic if the verifier runs in time sub-linear in the input length when given oracle access to an encoding of the input. We present holographic SNARGs for P and Batch-NP under the learning with errors (LWE) assumption. Our holographic SNARG for P has a verifier that runs in time $\mathsf{poly}(\lambda, \log T, \log n)$ for $T$-time computations and $n$-bit inputs ($\lambda$ is the security parameter), while our holographic SNARG for Batch-NP has a verifier that runs in time $\mathsf{poly}(\lambda, T, \log k)$ for $k$ instances of $T$-time computations. Before this work, constructions with the same asymptotic efficiency were known in the designated-verifier setting or under the sub-exponential hardness of the LWE assumption. We obtain our holographic SNARGs (in the public-verification setting under the polynomial hardness of the LWE assumption) by constructing holographic SNARGs for certain hash computations and then applying known/trivial transformations.

As an application, we use our holographic SNARGs to weaken the assumption needed for a recent public-coin 3-round zero-knowledge (ZK) argument [Kiyoshima, CRYPTO 2022]. Specifically, we use our holographic SNARGs to show that a public-coin 3-round ZK argument exists under the same assumptions as the state-of-the-art private-coin 3-round ZK argument [Bitansky et al., STOC 2018].

Electronic voting is one of the most interesting application of modern cryptography, as it involves many innovative tools (such as homomorphic public-key encryption, non-interactive zero-knowledge proofs, and distributed cryptography) to guarantee several a priori contradictory security properties: the integrity of the tally and the privacy of the individual votes. While many efficient solutions exist for honest-but-curious voters, that follow the official procedure but try to learn more than just the public result, preventing attacks from malicious voters is much more complex: when voters may have incentive to send biased ballots, the privacy of the ballots is much harder to satisfy, whereas this is the crucial security property for electronic voting. We present a new technique to prove that an ElGamal ciphertext contains a message from a specific subset (quasi-adaptive NIZK of subset membership), using linearly-homomorphic signatures. The proofs are both quite efficient to generate, allowing the use of low-power devices to vote, and randomizable, which is important for the strong receipt-freeness property. They are well-suited to prevent vote-selling and replay attacks, which are the main threats against the privacy in electronic voting, with security proofs in the generic group model and the random oracle model.

The learning with errors problem (LWE) is one of the most important building blocks for post-quantum cryptography. To better understand the quantum hardness of LWE, it is crucial to explore quantum variants of LWE, show quantum algorithms for those variants, or prove they are as hard as standard LWE.

To this end, Chen, Liu, and Zhandry [Eurocrypt 2022] define the $\sf{S|LWE\rangle}$ problem, which encodes the error of LWE samples into quantum amplitudes. They then show efficient quantum algorithms for $\sf{S|LWE\rangle}$ with a few interesting amplitudes. However, the hardness of the most interesting amplitude, Gaussian, was not addressed by Chen et al., or only known for some restricted settings (for example, when the number of $\sf{S|LWE\rangle}$ samples is very small, it is well known that $\sf{S|LWE\rangle}$ is as hard as standard LWE).

In this paper, we show new hardness and algorithms for $\sf{S|LWE\rangle}$ with Gaussian and other amplitudes. Our main results are

1. There exist quantum reductions from standard LWE or worst-case GapSVP to $\sf{S|LWE\rangle}$ with Gaussian amplitude with unknown phase, and arbitrarily many $\sf{S|LWE\rangle}$ samples.

2. There is a $2^{\widetilde{O}(\sqrt{n})}$-time algorithm for $\sf{S|LWE\rangle}$ with Gaussian amplitude with known phase, given $2^{\widetilde{O}(\sqrt{n})}$ many quantum samples. The algorithm is modified from Kuperberg's sieve, and in fact works for more general amplitudes as long as the amplitudes and phases are completely known.

One way of interpreting our result is: to show a sub-exponential time quantum algorithm for standard LWE, all we need is to handle phases in $\sf{S|LWE\rangle}$ amplitudes better, either in the algorithm or the reduction.

We show that the key agreement scheme [J. Supercomput., 78:12093-12113, 2022] is flawed. (1) It neglects the representation of a point over an elliptic curve and the basic requirement for bit-wise XOR, which results in a trivial equality. By the equality, an adversary can recover a target device's identity, which means the scheme fails to keep anonymity. (2) It falsely requires that the central server should share its master secret key with each dew server. (3) The specified certificate is almost nonsensical.

Central banks around the world are actively exploring the issuance of retail central bank digital currency (rCBDC), which is widely seen as a key upgrade of the monetary system in the 21st century. However, privacy concerns are the main impediment to rCBDC’s development and roll-out. A central bank as the issuer of rCBDC would typically need to keep a digital ledger to record all the balances and transactions of citizens. These data, when combined with other data, could possibly disclose the spending habits of all citizens. On the one hand, the eligible rights of people to keep their transactions private should be protected, including against central bank surveillance. On the other hand, the central bank needs to ensure that no over-issuance of money or other frauds occur, necessarily demanding a certain form of knowledge of rCBDC transactions to safeguard against malicious users who create counterfeit money or spend duplicated money. This work investigates cryptographic tools and privacy-enhancing technology with the aim to craft a scalable solution to strike a balance between user privacy and transaction verifiability. Different from the current mainstream thought among central banks, it assumes that the central bank maintains a ledger to record all balances and transactions of citizens, but in a concealed form. Specifically, this work focuses on rCBDC architectures based on the unspent transaction output (UTXO) data model and tackles the research problem of preserving a sufficient degree of privacy for UTXO transaction records while allowing the central bank to verify their correctness. While UTXO-based rCBDC architectures were widely tested among major central banks, user privacy is not adequately addressed. The adoption of evolving public keys as pseudonyms to hide the real identities of users is the most advanced privacy design for UTXO-based rCBDC, but it only solves the privacy issue partially. Some information could still be leaked out. This work investigates techniques to address the shortcomings of the pseudonym approach. First, a Pedersen commitment scheme is applied to hide the transaction values of a UTXO transaction while allowing the central bank to verify that no over-issuance of rCBDC has occurred in the transaction. Contrary to the conventional approach, which applies a zero knowledge proof to prove no over-issuance, this work uses a Schnorr signature. This not only reduces the overheads but also enables a non-interactive proof. Then, Coinjoin is applied to aggregate UTXO transactions from different users into one larger UTXO transaction to obfuscate the payer-payee relationship while preserving the correctness of the amount of money flow. This work applies a well-developed notion in database research, namely, k-anonymity, to analyse the privacy guarantee of Coinjoin. Through modelling the transaction traffic by a Poisson process, the trade-off between anonymity and transaction confirmation time of Coinjoin is analysed.

Recently, there has been a surge of interest in the security of authenticated encryption with associated data (AEAD) within the context of key commitment frameworks. Security within this framework ensures that a ciphertext chosen by an adversary does not decrypt to two different sets of key, nonce, and associated data. Despite this increasing interest, the security of several widely deployed AEAD schemes has not been thoroughly examined within this framework. In this work, we assess the key committing security of AEGIS, which emerged as a winner in the Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR). A recent assertion has been made suggesting that there are no known attacks on AEGIS in the key committing settings and AEGIS qualifies as a fully committing AEAD scheme in IETF document. However, contrary to this claim, we propose a novel O(1) attack applicable to all variants of AEGIS. This demonstrates the ability to execute a key committing attack within the FROB game setting, which is known to be one of the most stringent key committing frameworks. This implies that our attacks also hold validity in other, more relaxed frameworks, such as CMT-1, CMT-4, and so forth.

Authenticated encryption is a cryptographic mechanism that allows communicating parties to protect the confidentiality and integrity of message exchanged over a public channel, provided they share a secret key. Some applications require committing authenticated encryption schemes, a security notion that is not covered by the classical requirements of confidentiality and integrity given a secret key. An authenticated encryption (AE) scheme is committing in the strongest sense when it is impossible to generate the same ciphertext for different $(K, [N, ]A, P)$ tuples, with $K$ the key, $N$ the nonce, $A$ the associated data and $P$ the plaintext.

In this work, we present authenticated encryption schemes for which we provably reduce their confidentiality, integrity and commitment security to the security of an underlying sponge function. In particular, we instantiate them with SHAKE128 and SHAKE256, offering 128 and 256 bits of security strength and based on the security claim in the SHA-3 standard FIPS 202. Cryptanalysis of reduced-round versions of SHA-3 and SHAKE functions suggests that the number of rounds can be divided by two without noticeable security degeneration, and this had lead to the definition of TurboSHAKE128 and TurboSHAKE256; hence we also instantiate our scheme with these functions, offering the same security strength at twice the speed. The AE schemes we propose therefore have the unique advantages that 1) their security is based on a security claim that has received a large amount of public scrutiny and that 2) it makes use of the standard Keccak-p permutation that has dedicated hardware support on more and more CPUs.

In more details, we build two online AE modes on top of a sponge function, in multiple layers. At the bottom layer, we use a variant of the duplex construction, referred to as overwrite duplex or OD for short, that uses an overwrite operation leading to a smaller state footprint. Our first AE mode is nonce-based and built using a variant of the SpongeWrap mode on top of OD, and security-equivalent to it. Our second AE mode makes use of the Deck-BO mode published at Asiacrypt 2022, an online version of a Synthetic Initial Value (SIV) authenticated encryption scheme. It requires a deck function that we build on top of the OD, again security-equivalent to it.

Ethereum is undergoing significant changes to its architecture as it evolves. These changes include its switch to PoS consensus and the introduction of significant infrastructural changes that do not require a change to the core protocol, but that fundamentally affect the way users interact with the network. These changes represent an evolution toward a more modular architecture, in which there exists new exogenous vectors for centralization. This paper builds on previous studies of decentralization of Ethereum to reflect these recent significant changes, and Ethereum’s new modular paradigm.

How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we consider the following problem, which we call succinct RSPV for classical functions (sRCF). Suppose $f$ is a function described by a polynomial time classical Turing machine, which is public; the client would like to sample a random $x$ as the function input and use a protocol to send $f(x)$ to the server. What's more, (1) when the server is malicious, what it knows in the passing space should be no more than $f(x)$; (2) the communication should be succinct (that is, independent to the running time of evaluating $f$). Solving this problem in classical cryptography seems to require strong cryptographic primitives. We show that, perhaps surprisingly, it's possible to solve this problem with quantum techniques under much weaker assumptions. By allowing for quantum communication and computations, we give a protocol for this problem assuming only collapsing hash functions [Unr16]. Our work conveys an interesting message that quantum cryptography could outperform classical cryptography in a new type of problems, that is, to reduce communications in meaningful primitives without using heavy classical cryptographic primitives.

In the aftermath of the Snowden revelations in 2013, concerns about the integrity and security of cryptographic systems have grown significantly. As adversaries with substantial resources might attempt to subvert cryptographic algorithms and undermine their intended security guarantees, the need for subversion-resilient cryptography has become paramount. Security properties are preserved in subversion-resilient schemes, even if the adversary implements the scheme used in the security experiment. This paper addresses this pressing concern by introducing novel constructions of subversion-resilient signatures and hash functions while proving the subversion-resilience of existing cryptographic primitives. Our main contribution is the first construction of subversion-resilient signatures under complete subversion in the offline watchdog model (with trusted amalgamation) without relying on random oracles. We demonstrate that one-way permutations naturally yield subversion-resilient one-way functions, thereby enabling us to establish the subversion-resilience of Lamport signatures, assuming a trusted comparison is available. Additionally, we develop subversion-resilient target-collision-resistant hash functions using a trusted XOR. By leveraging this approach, we expand the arsenal of cryptographic tools that can withstand potential subversion attacks. Our research builds upon previous work in the offline watchdog model with trusted amalgamation (Russell et al. ASIACRYPT'16) and subversion-resilient pseudo-random functions (Bemmann et al. ACNS'23), culminating in the formal proof of subversion-resilience for the classical Naor-Yung signature construction.

In remote state preparation with verifiability (RSPV), a client would like to prepare a quantum state (sampled from a state family) on the server side, such that ideally the client knows its full description, while the server holds and only holds the state itself. A closely related notion called self-testing, which is recently generalized to the single-server computationally-secure setting [MV21, aims at certifying the server's operation. These notions have been widely studied in various different settings and have become fundamental building blocks in many quantum protocols [GV19,GMP22,Zha22,FWZ22]. However, there are many variants of definitions in existing works, and many of these variants do not have some desirable properties like sequential composability. What's more, existing works mainly focus on simple state families like simple product states, and treatments for these types of states are already technically complicated; in this background, a new framework that could potentially support more general solutions is desirable. In this paper, we choose notions or basic ideas from existing works [RSP01,GV19,Zha22,RY21] and introduce new notions, with the goal of developing a more general, well-behaved framework for these problems. We choose RSPV with simulation-based soundness [RSP01,GV19,Zha22] (instead of rigidity-based soundness [GMP22]), and study its basic properties like composability. Furthermore, for controlling the server's operation in a verifiable way, we introduce a new notion named remote operator application with verifiability (ROAV) as a replacement of self-testing. In this notion the server is provided with an unknown input state, and is supposed to perform a specific operator (sampled from an operator family) to the state; the client knows the operator description, but what server knows in the end is limited to the output state of the operation applied on the input state. Finally, we show several basic constructions of protocols under our set of notions, and discuss why these notions could potentially lead to quantum cryptographic protocols with new functionalities.

Resource efficiency in blockchain systems remains a pivotal concern in their design. While Ethereum often experiences network congestion, leading to rewarding opportunities for miners through transaction inclusions, a significant amount of block space remains underutilized. Remarkably, instances of entirely unutilized blocks contribute to resource wastage within the Ethereum ecosystem. This study delves into the incentives driving miners to produce empty blocks. We ascertain that the immediate rewards of mining empty blocks often lead miners to forego potential benefits from transaction inclusions. Moreover, our investigation reveals a marked reduction in empty blocks after the Ethereum's Merge, highlighting that the Proof-of-Stake (PoS) consensus mechanism enhances block space efficiency in the blockchain sphere.

We present SCALLOP-HD, a novel group action that builds upon the recent SCALLOP group action introduced by De Feo, Fouotsa, Kutas, Leroux, Merz, Panny and Wesolowski in 2023. While our group action uses the same action of the class group $\textnormal{Cl}(\mathfrak{O})$ on $\mathfrak{O}$-oriented curves where $\mathfrak{O} = \mathbb{Z}[f\sqrt{-1}]$ for a large prime $f$ as SCALLOP, we introduce a different orientation representation: The new representation embeds an endomorphism generating $\mathfrak{O}$ in a $2^e$-isogeny between abelian varieties of dimension $2$ with Kani's Lemma, and this representation comes with a simple algorithm to compute the class group action. Our new approach considerably simplifies the SCALLOP framework, potentially surpassing it in efficiency — a claim to be confirmed by implementation results. Additionally, our approach streamlines parameter selection. The new representation allows us to select efficiently a class group $\textnormal{Cl}(\mathfrak{O})$ of smooth order, enabling polynomial-time generation of the lattice of relation, hence enhancing scalability in contrast to SCALLOP.

To instantiate our SCALLOP-HD group action, we introduce a new technique to apply Kani's Lemma in dimension 2 with an isogeny diamond obtained from commuting endomorphisms. This method allows one to represent arbitrary endomorphisms with isogenies in dimension 2, and may be of independent interest.

Exclusive OR (XOR), a common Boolean logical operation, is an operation on two factors where the result is true if and only if one operand is true and the other is false. A simple way to state this is ``one or the other, but not both''. Using this logical operation, a text string can be encrypted by applying the XOR operator to every character using a ``key''. If you want to decrypt the output, simply reapply the key and the resulting output will be the original message.

In this paper we present an improved version of the classical RC4 stream cipher. The improvements allow to build lightweight high-performance cryptographically strong random number generator suitable for use in IoT and as a corresponding component of operating systems. The criterion for high performance is both a high speed of generating a stream of random numbers and low overhead costs for adding entropy from physical events to the state of the generator.