International Association
for Cryptologic Research

Private information retrieval (PIR) protocols allow clients to access database entries without revealing the queried indices. They have many real-world applications, including privately querying patent-, compromised credential-, and contact databases. While existing PIR protocols that have been implemented perform reasonably well in practice, they all have suboptimal asymptotic complexities.

A line of work has explored so-called doubly-efficient PIR (DEPIR), which refers to single-server PIR protocols with optimal asymptotic complexities. Recently, Lin, Mook, and Wichs (STOC 2023) presented the first protocol that completely satisfies the DEPIR constraints and can be rigorously proven secure. Unfortunately, their proposal is purely theoretical in nature. It is even speculated that such protocols are completely impractical, and hence no implementation of any DEPIR protocol exists.

In this work, we challenge this assumption. We propose several optimizations for the protocol of Lin, Mook, and Wichs that improve both asymptotic and concrete running times, as well as storage requirements, by orders of magnitude. Furthermore, we implement the resulting protocol and show that for batch queries it outperforms state-of-the-art protocols.

In [1], Sarier presents a practical biometric-based non-transferable credential scheme that maintains the efficiency of the underlying Brands credential. In this paper, we design a new Blockchain-Based E-Voting (BBEV) scheme that combines the system of [1] with encrypted Attribute Based Credentials for a non-transferable code-voting approach to achieve efficient, usable, anonymous, transparent, auditable, verifiable, receipt-free and coercion-resistant remote voting system for small/medium scale elections. To the best of our knowledge, the system is the first user-centric BBEV scheme that depends on the one-show Brands' Credential both for biometric authentication and pre-encrypted ballot generation leading to a natural prevention against double voting. Even though the system is instantiated with Bitcoin Blockchain due to its prevalence and various coin mixers available for anonymity, the system is designed to be generic, i.e. independent of the cryptocurrency. Thus, the new BBEV scheme can be extended to large-scale elections for public Blockchains with higher throughput/cheaper transaction fees. Finally, a cost analysis based on the last USA presidential election data shows that, the new BBEV is advantageous over the traditional one if implemented for three consecutive elections.

Learning with Errors (LWE) is an important problem for post-quantum cryptography (PQC) that underlines the security of several NIST PQC selected algorithms. Several recent papers have claimed improvements on the complexity of so-called dual attacks on LWE. These improvements make dual attacks comparable to or even better than primal attacks in certain parameter regimes. Unfortunately, those improvements rely on a number of untested and hard-to-test statistical assumptions. Furthermore, a recent paper claims that the whole premise of those improvements might be incorrect.

The goal of this paper is to improve the situation by proving the correctness of a dual attack without relying on any statistical assumption. Although our attack is greatly simplified compared to the recent ones, it shares all the important statistical elements with those attacks and can serve as a basis for the analysis of more advanced attacks.

Our main contribution is to clearly identify a set of parameters under which our attack (and presumably other recent dual attacks) can work. Furthermore, our analysis completely departs from the existing statistics-based analysis and is instead rooted in geometry. We also compare the regime in which our algorithm works to the ``contradictory regime'' of Ducas and Pulles. We observe that those two regimes are essentially complementary but also that their statistical model does not seem to match what happens in our attack.

Byzantine agreement (BA) asks for a set of parties to reach agreement in an adversarial setting. A central question is how to construct efficient BA protocols that scale well with the number of parties. In particular, the communication complexity is a critical barrier for large-scale implementations.

State-of-the-art, scalable BA protocols typically work by sampling a small, unpredictable committee of parties that will send messages in each round. These messages must reach all honest parties, to allow the next round's committee to function. In practice, this is usually accomplished by propagating messages over a gossip network, implemented over a partial communication graph. Most formulations of gossip networks have an ideal guarantee that every message delivered to any honest party will be delivered to every other honest party. Unfortunately, realizing this guarantee necessarily makes the protocol vulnerable to denial-of-service attacks, since an adversary can flood the network with many messages that the protocol must deliver to all parties.

In this paper, we make several contributions towards realizing the goal of efficient, scalable byzantine agreement over a gossip network:

1. We define ``gossip with abort,'' a relaxed gossip model that can be efficiently realized with minor modifications to existing gossip protocols, yet allows for significant savings in communication compared to the full point-to-point model.

2. Our protocols work in a graded PKI model, in which honest parties only have partial agreement about the set of participants in the protocol. This model arises naturally in settings without trusted setup, such as the ``permissionless'' setting underlying many blockchain protocols.

3. We construct a new, player-replaceable BA protocol in the graded PKI model. The concrete communication complexity of our protocol, for typical parameter values, is more than 25 times better than the current state-of-the-art BA protocols in the honest-majority setting.

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. One of the benefits of using isogeny-based cryptography is its compactness. In particular, a key exchange scheme SIDH forgave us to use a $4\lambda$-bit prime for the security parameter $\lambda$.

Unfortunately, SIDH was broken in 2022 by some studies. After that, some isogeny-based key exchange and public key encryption schemes have been proposed; however, most of these schemes use primes whose sizes are not guaranteed as linearly related to the security parameter $\lambda$. As far as we know, the rest schemes have not been implemented due to the computation of isogenies of high dimensional abelian varieties, or they need to use a ``weak" curve (\textit{i.e.}, a curve whose endomorphism ring is known) as the starting curve.

In this study, we propose a novel compact isogeny-based key encapsulation mechanism named IS-CUBE via Kani's theorem and a $3$-dimensional SIDH diagram. A prime used in IS-CUBE is of the size of about $8\lambda$ bits, and its starting curve is a random supersingular elliptic curve. The core idea of IS-CUBE comes from the hardness of some already known computational problems and the novel computational problem (the Computational Long Isogeny with Torsion (CLIT) problem), which is the problem to compute a hidden isogeny from given two supersingular elliptic curves and information of torsion points of a relatively small order. From our PoC implementation of IS-CUBE via \textsf{sagemath}, it takes about $4.34$ sec for the public key generation, $0.61$ sec for the encapsulation, and $17.13$ sec for the decapsulation if $\lambda = 128$.

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.