International Association
for Cryptologic Research

Synthesis and optimization of quantum circuits are important and fundamental research topics in quantum computation, due to the fact that qubits are very precious and decoherence time which determines the computation time available is very limited. Specifically in cryptography, identifying the minimum quantum resources for implementing an encryption process is crucial in evaluating the quantum security of symmetric-key ciphers. In this work, we investigate the problem of optimizing the depth of quantum circuits for linear layers while utilizing a small number of qubits and quantum gates. To this end, we present a framework for the implementation and optimization of linear Boolean functions, by which we significantly reduce the depth of quantum circuits for many linear layers used in symmetric-key ciphers without increasing the gate count.

We introduce an efficient transparent interactive zero knowledge argument system with practical succinctness. Our system converts circuit inputs in Pedersen commitment form to linear polynomials so that the verifier can use standard integer operations to compute and verify the circuit output. The verifier runtime of our protocol is linear to the number of multiplication gates in the path that contains the most multiplications in a circuit (we use symbol $d_m$ to denote its value). However, its practical performance still compares favorably against state-of-the-art transparent zero-knowledge protocols with sub-linear verifier work.

The asymptotic cost of our protocol is $O (d_m \text{ log } d_m)$ for prover work, $O (d_m)$ for verifier work, and $ O({d_m}^{1/2})$ for communication cost, where $d_m$ stands for the total number of multiplication gates in the path that contains the most multiplications in a circuit (e.g. for a circuit with $n=2^{20}$ sequential multiplications, $d_m = n$). Specifically, when running a circuit with $2^{20}$ multiplication gates on a single thread CPU, the prover runtime of our protocol is $1.9$ seconds, the verifier runtime is $32$ ms and the communication cost is $56$ kbs.

In this paper, we will first introduce a base version of our protocol in which the prover work is dominated by $O ({d_m}^2)$ field operations. Although field operations are significantly faster than group operations, they become increasingly expensive as $d_m$ value gets large. So in the follow up sections, we will introduce a mechanism to apply number theoretic transformation (NTT) to bring down the prover time to $O (d_m \text{ log } d_m)$.

Another added benefit of our protocol is that it does not require a front end encoder to translate NP relation $R$ to some zero-knowledge friendly representation $\hat{R}$ (such as R1CS constraint system) before the relation can be converted to a proof system, making our protocol relatively easy to implement and also easier to use compared to constraint system based protocols.

Physical side-channel attacks are a major threat to stealing confidential data from devices. There has been a recent surge in such attacks on edge machine learning (ML) hardware to extract the model parameters. Consequently, there has also been some work, although limited, on building corresponding side-channel defenses against such attacks. All the current solutions either take the fully software or fully hardware-centric approaches, which are limited either in performance or flexibility.

In this paper, we propose the first hardware-software co-design solution for building side-channel-protected ML hardware. Our solution targets edge devices and addresses both performance and flexibility needs. To that end, we develop a secure RISC-V-based coprocessor design that can execute a neural network implemented in C/C++. The coprocessor uses masking to execute various neural network operations like weighted summations, activation functions, and output layer computation in a side-channel secure fashion. We extend the original RV32I instruction set with custom instructions to control the masking gadgets inside the secure coprocessor. We further use the custom instructions to implement easy-to-use APIs that are exposed to the end-user as a shared library. Finally, we demonstrate the empirical side-channel security of the design with 1M traces.

Secure inference of deep convolutional neural networks (CNNs) was recently demonstrated under RNS-CKKS. The state-of-the-art solution uses a high-order composite polynomial to approximate all ReLUs. However, it results in prohibitively high latency because bootstrapping is required to refresh zero-level ciphertext after every Conv-BN layer. To accelerate inference of CNNs over FHE and automatically design homomorphic evaluation architectures of CNNs, we propose AutoFHE: a bi-level multi-objective optimization framework to automatically adapt standard CNNs to polynomial CNNs. AutoFHE can maximize validation accuracy and minimize the number of bootstrapping operations by assigning layerwise polynomial activations and searching for the placement of bootstrapping operations. As a result, AutoFHE can generate diverse solutions spanning the trade-off front between accuracy and inference time. Experimental results of ResNets on encrypted CIFAR-10 under RNS-CKKS indicate that in comparison to the state-of-the-art solution, AutoFHE can reduce inference time (50 images on 50 threads) by up to 3,297 seconds (43%) while preserving accuracy (92.68%). AutoFHE also improves the accuracy of ResNet-32 by 0.48% while accelerating inference by 382 seconds (7%).

Showing quantum advantage based on weaker and standard classical complexity assumptions is one of the most important goals in quantum information science. In this paper, we demonstrate quantum advantage with several basic assumptions, specifically based on only the existence of classically-secure one-way functions. We introduce inefficient-verifier proofs of quantumness (IV-PoQ), and construct it from statistically-hiding and computationally-binding classical bit commitments. IV-PoQ is an interactive protocol between a verifier and a quantum polynomial-time prover consisting of two phases. In the first phase, the verifier is classical probabilistic polynomial-time, and it interacts with the quantum polynomial-time prover over a classical channel. In the second phase, the verifier becomes inefficient, and makes its decision based on the transcript of the first phase. If the quantum prover is honest, the inefficient verifier accepts with high probability, but any classical probabilistic polynomial-time malicious prover only has a small probability of being accepted by the inefficient verifier. In our construction, the inefficient verifier can be a classical deterministic polynomial-time algorithm that queries an $\mathbf{NP}$ oracle. Our construction demonstrates the following results based on the known constructions of statistically-hiding and computationally-binding commitments from one-way functions or distributional collision-resistant hash functions: (1) If one-way functions exist, then IV-PoQ exist. (2) If distributional collision-resistant hash functions exist (which exist if hard-on-average problems in $\mathbf{SZK}$ exist), then constant-round IV-PoQ exist. We also demonstrate quantum advantage based on worst-case-hard assumptions. We define auxiliary-input IV-PoQ (AI-IV-PoQ) that only require that for any malicious prover, there exist infinitely many auxiliary inputs under which the prover cannot cheat. We construct AI-IV-PoQ from an auxiliary-input version of commitments in a similar way, showing that (1) If auxiliary-input one-way functions exist (which exist if $\mathbf{CZK}\not\subseteq\mathbf{BPP}$), then AI-IV-PoQ exist. (2) If auxiliary-input collision-resistant hash functions exist (which is equivalent to $\mathbf{PWPP}\nsubseteq \mathbf{FBPP}$) or $\mathbf{SZK}\nsubseteq \mathbf{BPP}$, then constant-round AI-IV-PoQ exist. Finally, we also show that some variants of PoQ can be constructed from quantum-evaluation one-way functions (QE-OWFs), which are similar to classically-secure classical one-way functions except that the evaluation algorithm is not classical but quantum. QE-OWFs appear to be weaker than classically-secure classical one-way functions.

The discrete logarithm problem forms the basis of security of many practical schemes. When the number of bases is more than one, the problem of finding out the exponents is known as the multi- dimensional discrete logarithm problem. It arises in several circumstances both in groups modulo some integer or elliptic curve groups. Gaudry and Schost proposed a low-memory algorithm for this problem which performs a pseudo-random walk in the group. Tag tracing is a technique to practi- cally speed-up a pseudo-random walk. We have incorporated this technique into the Gaudry-Schost algorithm to observe the results of practical differences in time. We implemented the new algorithm in subgroups of $\mathbb{Z}^{*}_{p}$. Such subgroups are cryptographically relevant in the context of electronic voting and cash schemes. Our algorithm showed a substantial decrease in run-time with a gain in time by some integral multiple. For example, on a single core of Intel Xeon E7-8890 @ 2.50 GHz we showed our algorithm required 12 times less time than the Gaudry-Schost algorithm. This leads to better practical behaviour of the algorithm over such groups. We also point out a few more optimizations that can be adopted along with future applications for other scenarios.

With Dilithium and Falcon, NIST selected two lattice-based signature schemes during their post-quantum standardization project. Whereas Dilithium follows the Fiat-Shamir with Aborts (Lyubashevsky, Asiacrypt'09) blueprint, Falcon can be seen as an optimized version of the GPV-paradigm (Gentry et al., STOC'06). An important question now is whether those signatures allow additional features such as the aggregation of distinct signatures. One example are sequential aggregate signature (SAS) schemes (Boneh et al., Eurocrypt'04) which allow a group of signers to sequentially combine signatures on distinct messages in a compressed manner. The present work first reviews the state of the art of (sequentially) aggregating lattice-based signatures, points out the insecurity of one of the existing Falcon-based SAS (Wang and Wu, PROVSEC'19), and proposes a fix for it. We then construct the first Fiat-Shamir with Aborts based SAS by generalizing existing techniques from the discrete-log setting (Chen and Zhao, ESORICS'22) to the lattice framework. Going from the pre-quantum to the post-quantum world, however, does most often come with efficiency penalties. In our work, we also meet obstacles that seem inherent to lattice-based signatures, making the resulting scheme less efficient than what one would hope for. As a result, we only achieve quite small compression rates. We compare our construction with existing lattice-based SAS which all follow the GPV-paradigm. The bottom line is that none of the schemes achieves a good compression rate so far.

FrodoKEM is a lattice-based Key Encapsulation Mechanism (KEM) based on unstructured lattices. From a security point of view this makes it a conservative option to achieve post-quantum security, hence why it is favored over the NIST winners by several European authorities (e.g., German BSI and French ANSSI). Relying on unstructured instead of structured lattices (e.g., CRYSTALS-Kyber) comes at the cost of additional memory usage, which is particularly critical for embedded security applications such as smart cards. For example, prior FrodoKEM-640 implementations (using AES) on Cortex-M4 require more than 80 kB of stack making it impossible to run on embedded systems. In this work, we explore several stack reduction strategies and the resulting time versus memory trade-offs. Concretely, we reduce the stack consumption of FrodoKEM by a factor 2-3x compared to the smallestknown implementations with almost no impact on performance. We also present various time-memory trade-offs going as low as 8 kB for all AES parameter sets, andbelow 4 kB for FrodoKEM-640. By introducing a minor tweak to the FrodoKEM specifications, we additionally reduce the stack consumption down to 8 kB for all the SHAKE versions. As a result, this work enables FrodoKEM on embedded systems.

Mitaka is a lattice-based signature proposed at Eurocrypt 2022. A key advertised feature of Mitaka is that it can be masked at high orders efficiently, making it attractive in scenarios where side-channel attacks are a concern. Mitaka comes with a claimed security proof in the t-probing model. We uncover a flaw in the security proof of Mitaka, and subsequently show that it is not secure in the t-probing model. For any number of shares d ≥ 4, probing t < d variables per execution allows an attacker to recover the private key efficiently with approximately 221 executions. Our analysis shows that even a constant number of probes suffices (t = 3), as long as the attacker has access to a number of executions that is linear in d/t.

Zero-knowledge elementary databases (ZK-EDBs) enable a prover to commit a database ${D}$ of key-value pairs and later prove that ``${x}$ belongs to the support of ${D}$ and ${D}(x)=v$'' or that ``${x}$ does not belong to the support of ${D}$,'' without revealing any extra knowledge (including the size of ${D}$). Recently, Libert et al. (PKC 2019) introduced zero-knowledge expressive elementary databases (ZK-EEDBs) that support richer queries, e.g., range queries over the keys and values.

In this paper, we introduce a new notion called function queriable ZK-EDBs, where the ZK-EDB prover can convincingly answer the query that ``Send all records ${(x,v)}$ in ${{D}}$ satisfying $f(x,v)=1$ for any Boolean circuit $f$,'' without revealing any extra knowledge (including the size of ${D}$).

To construct function queriable ZK-EDBs, we introduce a new variation of zero-knowledge sets (ZKS) which supports verifiable set operations, and present a construction based on groups of unknown order. By transforming the Boolean circuit over databases into the set operation circuit/formula over sets, we present a construction of function queriable ZK-EDBs from standard ZK-EDBs and ZKS supporting verifiable set operations.

In this paper, we propose the first two-round multi-signature scheme that can guarantee 128-bit security under a standardized EC in concrete security without using the Algebraic Group Model (AGM). To construct our scheme, we introduce a new technique to tailor a certain special homomorphic commitment scheme for the use with the Katz-Wang DDH-based signature scheme. We prove that an EC with at least a 321-bit order is sufficient for our scheme to have the standard 128-bit security. This means that it is easy for our scheme to implement in practice because we can use the NIST-standardized EC P-384 for 128-bit security. The signature size of our proposed scheme under P-384 is 1152 bits, which is the smallest size among the existing schemes without using the AGM. Our experiment on an ordinary machine shows that for signing and verification, each can be completed in about 65 ms under 100 signers. This shows that our scheme has sufficiently reasonable running time in practice.

Asynchronous common subset (ACS) is a powerful paradigm enabling applications such as Byzantine fault-tolerance (BFT) and multi-party computation (MPC). The most efficient ACS framework in the information-theoretic (IT) setting is due to Ben-Or, Kelmer, and Rabin (BKR, 1994). The BKR ACS protocol has been both theoretically and practically impactful. However, the BKR protocol has an $O(\log n)$ running time (where $n$ is the number of replicas) due to the usage of $n$ parallel asynchronous binary agreement (ABA) instances, impacting both performance and scalability. Indeed, for a network of 16-64 replicas, the parallel ABA phase occupies about 95%-97% of the total runtime in BKR. A long-standing open problem is whether we can build an ACS framework with $O(1)$ time while not increasing the message or communication complexity of the BKR protocol.

In this paper, we resolve the open problem, presenting the first constant-time ACS protocol with $O(n^3)$ messages in the IT (and signature-free) settings. Moreover, as a key ingredient of our new ACS framework and an interesting primitive in its own right, we provide the first IT-secure multivalued validated Byzantine agreement (MVBA) protocol with $O(1)$ time and $O(n^3)$ messages. Both results can improve---asymptotically and concretely---various applications using ACS and MVBA in the IT, quantum-safe, or signature-free settings. As an example, we implement FIN, a BFT protocol instantiated using our framework. Via a 121-server deployment on Amazon EC2, we show FIN is significantly more efficient than PACE (CCS 2022), the state-of-the-art asynchronous BFT protocol of the same type. In particular, FIN reduces the overhead of the ABA phase to as low as 1.23% of the total runtime, and FIN achieves up to 3.41x the throughput of PACE.

In this paper, we consider tight multi-user security under adaptive corruptions, where the adversary can adaptively corrupt some users and obtain their secret keys. We propose generic constructions for a bunch of primitives, and the instantiations from the matrix decision Diffie-Hellman (MDDH) assumptions yield the following schemes: (1) the first digital signature (SIG) scheme achieving almost tight strong EUF-CMA security in the multi-user setting with adaptive corruptions in the standard model; (2) the first public-key encryption (PKE) scheme achieving almost tight IND-CCA security in the multi-user multi-challenge setting with adaptive corruptions in the standard model; (3) the first signcryption (SC) scheme achieving almost tight privacy and authenticity under CCA attacks in the multi-user multi-challenge setting with adaptive corruptions in the standard model. As byproducts, our SIG and SC naturally derive the first strongly secure message authentication code (MAC) and the first authenticated encryption (AE) schemes achieving almost tight multi-user security under adaptive corruptions in the standard model. We further optimize constructions of SC, MAC and AE to admit better efficiency.

Furthermore, we consider key leakages besides corruptions, as a natural strengthening of tight multi-user security under adaptive corruptions. This security considers a more natural and more complete "all-or-part-or-nothing" setting, where secret keys of users are either fully exposed to adversary ("all"), or completely hidden to adversary ("nothing"), or partially leaked to adversary ("part"), and it protects the uncorrupted users even with bounded key leakages. All our schemes additionally support bounded key leakages and enjoy full compactness. This yields the first SIG, PKE, SC, MAC, AE schemes achieving almost tight multi-user security under both adaptive corruptions and leakages.

Re-randomizable Replayable CCA-secure public key encryption (Rand-RCCA PKE) schemes guarantee security against chosen-ciphertext attacks while ensuring the useful property of re-randomizable ciphertexts. We introduce the notion of multi-user and multi-ciphertext Rand-RCCA PKE and we give the first construction of such a PKE scheme with an almost tight security reduction to a standard assumption. Our construction is structure preserving and can be instantiated over Type-1 pairing groups. Technically, our work borrows ideas from the state of the art Rand-RCCA PKE scheme of Faonio et al. (ASIACRYPT’19) and the adaptive partitioning technique of Hofheinz (EUROCRYPT’17). Additionally, we show (1) how to turn our scheme into a publicly-verifiable (pv) Rand-RCCA scheme and (2) that plugging our pv-Rand-RCCA PKE scheme into the MixNet protocol of Faonio et al. we can obtain the first almost tightly-secure MixNet protocol.

In this paper, we examine the algebraic XSL attack on the Advanced Encryption Standard (AES). We begin with a brief introduction and we present an overview of AES, then, in Section 3, we present the algebraic attack on ciphers like AES, following with the XL and XSL algorithms in Section 4 and Section 5. Then, we present the XSL first and second attacks, also their aplicability on BES. We see how and if the algorithm has been improved since it firstly appeared. We conclude with Section 10.

A recent line of works on zero knowledge (ZK) protocols with a {\em vector oblivious linear function evaluation (VOLE)}-based offline phase provides a new paradigm for scalable ZK protocols with prover memory footprint almost the same as verifying the circuit in the clear. Most of these protocols can be made to have a {\em non-interactive} online phase, yielding a {\em preprocessing NIZK}. In particular, when the preprocessing is realized by a two-round protocol, one obtains a {\em malicious designated verifier-NIZK (MDV-NIZK)}, which is a recent closely scrutinized variant of DV-NIZK that allows the verifier to generate a public key (first message of two-round protocol) for the prover and a secret key to verify proofs. Though many practically efficient protocols for proving circuit satisfiability over any field are implemented, protocols over the ring $\mathbb{Z}_{2^k}$ are significantly lagging behind, with only a proof-of-concept pioneering work called {\em Appenzeller to Brie} and a first proposal called {\em Moz$\mathbb{Z}_{2^k}$arella}. The ring $\mathbb{Z}_{2^{32}}$ or $\mathbb{Z}_{2^{64}}$, though highly important (it captures computation in real-life programming and the computer architectures such as CPU words), presents non-trivial difficulties because, unlike Galois fields $\mathbb{F}_{2^{k}}$, the fraction of units in rings $\mathbb{Z}_{2^{k}}$ is $1/2$. In this work, we first construct protocols over a large Galois ring extension of $\mathbb{Z}_{2^{k}}$ (fraction of units close to $1$) and then convert to $\mathbb{Z}_{2^k}$ efficiently using amortization techniques. Our results greatly change the landscape of ZK protocols over $\mathbb{Z}_{2^k}$. (1) We propose a competing basic protocol that has many advantages over the state-of-the-art Moz$\mathbb{Z}_{2^k}$arella: our efficiency is independent of the security parameter (so overwhelming superiority in high security region); for frequently used $40,80$ bits soundness on $32,64$-bit CPUs we all offer savings (up to $3\times$ at best). (2) Through adapting a recently proposed {\em interactive} authentication code to work over Galois rings, we obtain constant round VOLE-based ZK protocols over $\mathbb{Z}_{2^k}$ with sublinear (in the circuit size) communication complexity, which was previously achieved only over fields. (3) In order to circumvent the impossibility result of OT-based reusable VOLE, we propose a novel construction of two-round {\em reusable} VOLE over Galois rings using Galois fields counterpart and powerful tools developed for non-interactive secure computation. We also show that the pseudorandom correlation generator (PCG) approach to extending VOLE without increasing rounds can be generalized to Galois rings. Instantiating a non-interactive version of our basic protocol with a two-round reusable VOLE preprocessing, we obtain MDV-NIZK over $\mathbb{Z}_{2^k}$ with unique features. Such protocols are not only never achieved over rings but also new over small fields.

Bootstrapping is a term used very often in the context of Fully Homomorphic Encryption (FHE). Anyone who is familiar with FHE knows that bootstrapping is the most sophisticated and compute-intensive component of an FHE scheme. However, very few non-FHE-experts understand what the bootstrapping operation really is and that there are various bootstrapping methods, each with its own tradeoffs. The goal of this paper is to provide a high-level introduction to common bootstrapping methods and evaluate their performance using the existing implementations in OpenFHE and HElib open-source libraries.

Our performance evaluation suggests that the bootstrapping in the Cheon-Kim-Kim-Song (CKKS) scheme provides highest throughput and efficiently achieves large precision for vectors of real numbers, which are often used in machine learning applications. The Ducas-Micciancio (DM) and Chillotti-Gama-Georgieva-Izabachene (CGGI) schemes achieve the smallest latency (typically for small integers or small-precision fixed-point numbers) and provide a general capability for evaluating arbitrary functions (programmable bootstrapping) via lookup tables. The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV) schemes provide higher bootstrapping throughput than DM/CGGI for vectors of small integers or finite-field elements but do not support programmable bootstrapping.

The target audience is anyone interested in FHE. We intend to keep this paper up-to-date to include new bootstrapping results as they become available.

In this paper, we present a client-side password hashing method, called PassPro. PassPro uses two secrets and a domain word to shuffle the strings. The shuffled strings are converted into hash values and sent to the identity manager for authentication or identity creation. The shuffling is based on a pseudo-random algorithm. The legitimate user can reproduce the shuffled string again. The hash values are encrypted in the password database with a different key for each user. Therefore, PassPro features- a) client-side password metering, b) client-side password hashing, c) prevention of the domino effect, d) protection of the password database from stealing, e) memory hardness, f) encryption of the hash values using a mutually reproducible secret key, and g) prevention of dictionary and guessing attacks. Also, PassPro guarantees that identity managers, including adversaries, cannot retrieve the original password and user ID of the user. Alternatively, the original user ID and password cannot be retrieved even if the password database is given to the adversary. Furthermore, the user ID and password of a password database are invalid in other domains, even if the same user ID and password are used in multiple domains.

Bulletproofs (Bünz et al. IEEE S&P 2018) are a celebrated ZK proof system that allows for short and efficient proofs, and have been implemented and deployed in several real-world systems. In practice, they are most often implemented in their non-interactive version obtained using the Fiat-Shamir transform. A security proof for this setting is necessary for ruling out malleability attacks. These attacks can lead to very severe vulnerabilities, as they allow an adversary to forge proofs re-using or modifying parts of the proofs provided by the honest parties. An earlier version of this work (Ganesh et al. EUROCRYPT 2022) provided evidence for non-malleability of Fiat-Shamir Bulletproofs. This was done by proving simulation-extractability, which implies non-malleability, in the algebraic group model.

In this work, we generalize the former result and prove simulation extractability in the programmable random oracle model, removing the need for the algebraic group model. Along the way, we establish a generic chain of reductions for Fiat-Shamir-transformed multi-round public-coin proofs to be simulation-extractable in the (programmable) random oracle model, which may be of independent interest.

In this paper, we research the implementation of the AES family with Pauli-X gates, CNOT gates and Toffoli gates as the underlying quantum logic gate set. First, we investigate the properties of quantum circuits and the influence of Pauli-X gates, CNOT gates and Toffoli gates on the performance of the circuits constructed with those gates. Based on the properties of quantum circuits as well as our observations on the classical ones built by Boyar \emph{et al.} and Zou \emph{et al.}, we research the construction of reversible circuits for AES's Substitution-box (S-box) and its inverse (S-box$^{-1}$) by rearranging the classical implementation to three parts. Since the second part is treated as a 4-bit S-box in this paper and can be dealt with by existing tools, we propose a heuristic to search optimized reversible circuits for the first part and the third part. The application of our method reveals that the reversible circuits constructed for AES S-box and its inverse consume fewer qubits with optimized CNOT gate consumption and Toffoli depth. In addition, we study the construction of reversible circuits for the key schedule and the round function of AES by applying various number of S-boxes in parallel. As a result, we report quantum circuits of AES-128, AES-192 and AES-256 with 269, 333 and 397 qubits, respectively. If more qubits are allowed, quantum circuits that outperform state-of-the-art schemes in the metric of $T\cdot M$ value for the AES family can be reported, and it needs only 474, 538 and 602 qubits for AES-128, AES-192 and AES-256, respectively.