International Association
for Cryptologic Research

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.

The Mixed Integer Linear Programming (MILP) technique has been widely applied in the realm of symmetric-key cryptanalysis. In this paper, we propose a new bitwise breakdown MILP modeling strategy for describing the linear propagation rules of modular addition-based operations. We apply such new techniques to cryptanalysis of the SNOW stream cipher family and find new linear masks: we use the MILP model to find many linear mask candidates among which the best ones are identified with particular algebraic bias evaluation techniques. For SNOW 3G, the correlation of the linear mask we found is the highest on record: such results are highly likely to be optimal according to our analysis. For SNOW 2.0, we find new masks matching the correlation record and many new sub-optimal masks applicable to improving correlation attacks. For SNOW-V/Vi, by investigating both bitwise and truncated linear masks, we find all linear masks having the highest correlation, and prove the optimum of the corresponding truncated patterns under the ``fewest active S-box preferred'' strategy. By using the newly found linear masks, we give correlation attacks on the SNOW family with improved complexities. We emphasize that the newly proposed uniform MILP-aided framework can be potentially applied to analyze LFSR-FSM structures composed of modular addition and S-box as non-linear components.

Non-fungible tokens (NFTs) are unique non-interchangeable digital assets verified and stored using blockchain technology. Quite recently, there has been a surging interest and adoption of NFTs, with sales exceeding \$10 billion in the third quarter of 2021. Given the public state of Blockchain, NFTs owners face a privacy problem. More precisely, an observer can trivially learn the whole NFT collections owned by an address. For some categories of NFTs like arts and game collectibles, owners can sell them for a profit. However, popular marketplaces trade NFTs using public auctions and direct offers. Hence, an observer can learn about the new owner and the NFT purchase price. To tackle those problems, we propose Aegis, a protocol that allows users to add privacy to their NFTs ownership. In Aegis, users can swap NFTs for payment amounts in fungible tokens while hiding the details (i.e., involved parties, the NFTs, and the payment amounts). One of the main properties of Aegis is its complete compatibility with existing NFT standards. We design Aegis by leveraging a zk-SNARK proof system and smart contracts. We build an open-source prototype and perform experiments to evaluate Aegis's performance.

The pair encodings framework is an important result in the simplified design of complex attribute-based encryption schemes. In particular, it reduces the effort of proving security of a scheme to proving security of the associated pair encoding, which can then be transformed into a provably secure pairing-based encryption scheme with a compiler. Especially the symbolic property, as introduced by Agrawal and Chase (EUROCRYPT '17), has proven to be a valuable security notion that is both simple to verify and applies to many schemes. Nevertheless, several practical extensions using full-domain hashes or employing multiple authorities cannot be instantiated with this compiler, and therefore still require complicated proof techniques.

In this work, we present the first compiler for attribute-based encryption schemes that supports such extensions. To this end, we generalize the definitions of pair encodings and the symbolic property. With our compiler, we flexibly instantiate any pair encodings that satisfy this new notion of the symbolic property in any pairing-friendly groups, and generically prove the resulting scheme to be selectively secure. To illustrate the effectiveness of our new compiler, we give several new multi-authority and hash-based constructions.

We present a single-trace attack against lattice-based KEMs using the cumulative distribution table for Gaussian sampling and execute it in a real-world environment. Our analysis takes a single power trace of the decapsulation algorithm as input and exploits leakage of the Gaussian sampling subroutine to reveal the session key. We investigated the feasibility of the attack on different boards and proved that the power consumption traces become less informative with higher clock frequencies. Therefore, we introduce a machine-learning denoising technique, which enhances the accuracy of our attack and leverages its success rate to 100%.

We accomplish the attack on FrodoKEM, a lattice-based KEM and third-round alternate candidate. We execute it on a Cortex-M4 board equipped with an STM32F4 micro-controller clocked at different frequencies.

Aggregate statistics derived from time-series data collected by individual users are extremely beneficial in diverse fields, such as e-health applications, IoT-based smart metering networks, and federated learning systems. Since user data are privacy-sensitive in many cases, the untrusted aggregator may only infer the aggregation without breaching individual privacy. To this aim, secure aggregation techniques have been extensively researched over the past years. However, most existing schemes suffer either from high communication overhead when users join and leave, or cannot tolerate node dropouts. In this paper, we propose a dropout-resistant bandwidth-efficient time-series data aggregation. The proposed scheme does not incur any interaction among users, involving a solo round of user→aggregator communication exclusively. Additionally, it does not trigger a re-generation of private keys when users join and leave. Moreover, the aggregator is able to output the aggregate value by employing the re-encrypt capability acquired during a one-time setup phase, notwithstanding the number of nodes in the ecosystem that partake in the data collection of a certain epoch. Dropout-resistancy, trust-less key management, low-bandwidth and non-interactive nature of our construction make it ideal for many rapid-changing distributed real-world networks. Other than bandwidth efficiency, our scheme has also demonstrated efficiency in terms of computation overhead

The best lattice reduction algorithm known in theory for approximating the Shortest Vector Problem (SVP) over lattices is the slide reduction algorithm (STOC '08 & CRYPTO '20). In this paper, we first improve the running time analysis of computing slide-reduced bases based on potential functions. This analysis applies to a generic slide reduction algorithm that includes (natural variants of) slide reduction and block-Rankin reduction (ANTS '14). We then present a rigorous dynamic analysis of generic slide reduction using techniques originally applied to a variant of BKZ (CRYPTO '11). This provides guarantees on the quality of the current lattice basis during execution. This dynamic analysis not only implies sharper convergence for these algorithms to find a short nonzero vector (rather than a fully reduced basis), but also allows to heuristically model/trace the practical behaviour of slide reduction. Interestingly, this dynamic analysis inspires us to introduce a new slide reduction variant with better time/quality trade-offs. This is confirmed by both our experiments and simulation, which also show that our variant is competitive with state-of-the-art reduction algorithms. To the best of our knowledge, this work is the first attempt of improving the practical performance of slide reduction beyond speeding up the SVP oracle.

In post-quantum cryptography (PQC), Learning With Errors (LWE) is the dominant underlying mathematical problem. For example, in NIST's PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to revise the complexity of the dual attack on the LWE-based protocols Kyber, Saber and TFHE. For all these schemes we improve upon the total bit-complexity in both the classical and the quantum setting. As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas.