The traditional definition of fully homomorphic encryption (FHE) is not composable, i.e., it does not guarantee that evaluating two (or more) homomorphic computations in a sequence produces correct results. We formally define and investigate a stronger notion of homomorphic encryption which we call "fully composable homomorphic encryption", or "composable FHE". The definition is both simple and powerful: it does not directly involve the evaluation of multiple functions, and yet it supports the arbitrary composition of homomorphic evaluations. On the technical side, we compare the new definition with other definitions proposed in the past, proving both implications and separations, and show how the "bootstrapping" technique of (Gentry, STOC 2009) can be formalized as a method to transform a (non-composable, circular secure) homomorphic encryption scheme into a fully composable one. We use this formalization of bootstrapping to formulate a number of conjectures and open problems.

LLL-style lattice reduction algorithms iteratively employ size reduction and reordering on ordered basis vectors to find progressively shorter, more orthogonal vectors. DeepLLL reorders the basis through deep insertions, yielding much shorter vectors than LLL. DeepLLL was introduced alongside BKZ, however, the latter has received greater attention and has emerged as the state-of-the-art. We first show that LLL-style algorithms work with a designated measure of basis quality and iteratively improves it; specifically, DeepLLL improves a sublattice measure based on the generalised Lovász condition. We then introduce a new generic framework X-GG for lattice reduction algorithms that work with a measure X of basis quality. X-GG globally searches for deep insertions that minimise X in each iteration. We instantiate the framework with two quality measures – basis potential (Pot) and squared sum (SS) – both of which have corresponding DeepLLL algorithms. We prove polynomial runtimes for our X-GG algorithms and also prove their output to be X-DeepLLL reduced. Our experiments on non-preprocessed bases show that X-GG produces better quality outputs whilst being much faster than the corresponding DeepLLL algorithms. We also compare SS-GG and the FPLLL implementation of BKZ with LLL-preprocessed bases. In small dimensions (40 to 210), SS-GG is significantly faster than BKZ with block sizes 8 to 12, while simultaneously also providing better output quality in most cases. In higher dimensions (250 and beyond), by varying the threshold $\delta$ for deep insertion, SS-GG offers new trade-offs between the output quality and runtime. On the one hand, it provides significantly better runtime than BKZ-5 with worse output quality; on the other hand, it is significantly faster than BKZ-21 while providing increasingly better output quality after around dimension 350.

The round complexity of interactive proof systems is a key question of practical and theoretical relevance in complexity theory and cryptography. Moreover, results such as QIP = QIP(3) (STOC'00) show that quantum resources significantly help in such a task.

In this work, we initiate the study of round compression of protocols in the bounded quantum storage model (BQSM). In this model, the malicious parties have a bounded quantum memory and they cannot store the all the qubits that are transmitted in the protocol.

Our main results in this setting are the following:

1. There is a non-interactive (statistical) witness indistinguishable proof for any language in NP (and even QMA) in BQSM in the plain model. We notice that in this protocol, only the memory of the verifier is bounded.
2. Any classical proof system can be compressed in a two-message quantum proof system in BQSM. Moreover, if the original proof system is zero-knowledge, the quantum protocol is zero-knowledge too. In this result, we assume that the prover has bounded memory.

Finally, we give evidence towards the “tightness” of our results. First, we show that NIZK in the plain model against BQS adversaries is unlikely with standard techniques. Second, we prove that without the BQS model there is no 2–message zero-knowledge quantum interactive proof, even under computational assumptions.

A wide range of countermeasures have been proposed to defend against side-channel attacks, with masking being one of the most effective and commonly used techniques. While theoretical models provide formal security proofs, these often rely on assumptions—sometimes implicit—that can be difficult to assess in practice. As a result, the design of secure masked implementations frequently combines proven theoretical arguments with heuristic and empirical validation.

Despite the significant body of work, the literature still lacks a cohesive and well-defined framework for translating theoretical security guarantees into practical implementations on physical devices. Specifically, there remains a gap in connecting provable results from abstract models to quantitative security guarantees at the implementation level.

In this Systematization of Knowledge (SoK), we aim to provide a comprehensive methodology to transform abstract cryptographic algorithms into physically secure implementations against side-channel attacks on microcontrollers. We introduce new tools to adapt the ideal noisy leakage model to practical, real-world scenarios, and we integrate state-of-the-art techniques to build secure implementations based on this model.

Our work systematizes the design objectives necessary for achieving high security levels in embedded devices and identifies the remaining challenges in concretely applying security reductions. By bridging the gap between theory and practice, we seek to provide a foundation for future research that can develop implementations with proven security against side-channel attacks, based on well-understood leakage assumptions.

We construct the following cryptographic primitives with unconditional security in a bounded-key model:

• One-time public-key encryption, where the public keys are pure quantum states
• One-time signatures, where the verification keys are pure quantum states.

In our model, the adversary is given a bounded number of copies of the public key. We present efficient constructions and nearly-tight lower bounds for the size of the secret keys.

Our security proofs are based on the quantum coupon collector problem, which was originally studied in the context of learning theory. The quantum coupon collector seeks to learn a set of strings (coupons) when given several copies of a superposition over the coupons. We make novel connections between this problem and cryptography.

Our main technical ingredient is a family of coupon states, with randomized phases, that come with strong hardness properties. Our analysis improves on prior work by (i) showing that the number of quantum states needed to learn the entire set of coupons is identical to the number of random coupons needed in the classical coupon collector problem. (ii) Furthermore we prove that this result holds for a randomly chosen set of coupons, whereas prior work only lower-bounded the number of coupon states required to learn the worst-case set of coupons.

Given a supersingular elliptic curve E and a non-scalar endomorphism α of E, we prove that the endomorphism ring of E can be computed in classical time about disc(Z[α])^1/4, and in quantum subexponential time, assuming the generalised Riemann hypothesis. Previous results either had higher complexities, or relied on heuristic assumptions.

Along the way, we describe and analyse a general algorithm to divide isogenies in polynomial time, and to solve the Primitivisation problem in polynomial time. Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results.

We present Boomy, a multivariate polynomial commitment scheme enabling the proof of the evaluation of multiple points, i.e., batch opening. Boomy is the natural extension of two popular protocols: the univariate polynomial commitment scheme of Kate, Zaverucha and Goldberg[KZG10] and its multivariate counterpart from Papamanthou, Shi and Tamassia[PST13]. Our construction is proven secure under the selective security model. In this paper, we present Boomy's complexity and the applications on which it can have a significant impact. In fact, Boomy is perfectly suited to tackling blockchain problems by greatly improving data availability sampling and shrinking existing challenges. We also present special lower-complexity cases that occur frequently in practical situations.

Several protocols have been proposed recently for threshold ECDSA signatures, mostly in the dishonest-majority setting. Yet in so-called key-management networks, where a fixed set of servers share a large number of keys on behalf of multiple users, it may be reasonable to assume that a majority of the servers remain uncompromised, and in that case there may be several advantages to using an honest-majority protocol.

With this in mind, we describe an efficient protocol for actively secure, honest-majority threshold ECDSA supporting batch generation of key-independent presignatures that allow for “non-interactive” online signing; these properties are not available in existing dishonest-majority protocols. Our protocol offers low latency and high throughput, and runs at an amortized rate of roughly 1.3 ms per presignature (after which signatures can be generated in less than 100 microseconds).

Homomorphic encryption for approximate arithmetic allows one to encrypt discretized real/complex numbers and evaluate arithmetic circuits over them. The first scheme, called CKKS, was introduced by Cheon et al. (Asiacrypt 2017) and gained tremendous attention. The enthusiasm for CKKS-type encryption stems from its potential to be used in inference or multiparty computation tasks that do not require an exact output.

A desirable property for homomorphic encryption is circuit privacy, which requires that a ciphertext leaks no information on the computation performed to obtain it. Despite numerous improvements directed toward improving efficiency, the question of circuit privacy for approximate homomorphic encryption remains open.

In this paper, we give the first formal study of circuit privacy for homomorphic encryption over approximate arithmetic. We introduce formal models that allow us to reason about circuit privacy. Then, we show that approximate homomorphic encryption can be made circuit private using tools from differential privacy with appropriately chosen parameters. In particular, we show that by applying an exponential (in the security parameter) Gaussian noise on the evaluated ciphertext, we remove useful information on the circuit from the ciphertext. Crucially, we show that the noise parameter is tight, and taking a lower one leads to an efficient adversary against such a system.

We expand our definitions and analysis to the case of multikey and threshold homomorphic encryption for approximate arithmetic. Such schemes allow users to evaluate a function on their combined inputs and learn the output without leaking anything on the inputs. A special case of multikey and threshold encryption schemes defines a so-called partial decryption algorithm where each user publishes a “masked” version of its secret key, allowing all users to decrypt a ciphertext. Similarly, in this case, we show that applying a proper differentially private mechanism gives us IND-CPA-style security where the adversary additionally gets as input the partial decryptions. This is the first security analysis of approximate homomorphic encryption schemes that consider the knowledge of partial decryptions. We show lower bounds on the differential privacy noise that needs to be applied to retain security. Analogously, in the case of circuit privacy, the noise must be exponential in the security parameter. We conclude by showing the impact of the noise on the precision of CKKS-type schemes.

Modern security systems depend fundamentally on the ability of users to authenticate their communications to other parties in a network. Unfortunately, cryptographic authentication can substantially undermine the privacy of users. One possible solution to this problem is to use privacy-preserving cryptographic authentication. These protocols allow users to authenticate their communications without revealing their identity to the verifier. In the non-interactive setting, the most common protocols include blind, ring, and group signatures, each of which has been the subject of enormous research in the security and cryptography literature. These primitives are now being deployed at scale in major applications, including Intel's SGX software attestation framework. The depth of the research literature and the prospect of large-scale deployment motivate us to systematize our understanding of the research in this area. This work provides an overview of these techniques, focusing on applications and efficiency.

The Chou-Orlandi batch oblivious transfer (OT) protocol is a particularly attractive OT protocol that bridges the gap between practical efficiency and strong security guarantees and is especially notable due to its simplicity. The security analysis provided by Chou and Orlandi bases the security of their protocol on the hardness of the computational Diffie-Hellman (CDH) problem in prime-order groups. Concretely, in groups in which no better-than-generic algorithms are known for the CDH problem, their security analysis yields that an attacker running in time $t$ and issuing $q$ random-oracle queries breaks the security of their protocol with probability at most $\epsilon \leq q^2 \cdot t / 2^{\kappa/2}$, where $\kappa$ is the bit-length of the group's order. This concrete bound, however, is somewhat insufficient for 256-bit groups (e.g., for $\kappa = 256$, it does not provide any guarantee already for $t = 2^{48}$ and $q = 2^{40}$).

In this work, we establish a tighter concrete security bound for the Chou-Orlandi protocol. First, we introduce the list square Diffie-Hellman problem and present a tight reduction from the security of the protocol to the hardness of solving the list square Diffie-Hellman problem. That is, we completely shift the task of analyzing the concrete security of the protocol to that of analyzing the concrete hardness of the list square Diffie-Hellman problem. Second, we reduce the hardness of the list square Diffie-Hellman problem to that of the decisional Diffie-Hellman (DDH) problem without incurring a multiplicative loss. Our key observation is that although CDH and DDH have the same assumed concrete hardness, relying on the hardness of DDH enables our reduction to efficiently test the correctness of the solutions it produces.

Concretely, in groups in which no better-than-generic algorithms are known for the DDH problem, our analysis yields that an attacker running in time $t$ and issuing $q \leq t$ random-oracle queries breaks the security of the Chou-Orlandi protocol with probability at most $\epsilon \leq t / 2^{\kappa/2}$ (i.e., we eliminate the above multiplicative $q^2$ term). We prove our results within the standard real-vs-ideal framework considering static corruptions by malicious adversaries, and provide a concrete security treatment by accounting for the statistical distance between a real-model execution and an ideal-model execution.

The Structured Encryption (StE) framework can be used to capture the encryption and querying of complex data structures on an honest-but-curious server. In this work, we introduce a new type of StE called indirectly addressed multimap encryption (IA-MME). We propose two IA-MME schemes: the layered multimaps approach" which extends and generalizes the existing "multimap chaining" approach, and a novel technique called the single multimap approach which has comparable efficiency and strictly better security. We demonstrate that our formalisms simplify and modularize StE solutions for real-world use cases in searchable encryption and SQL databases, and provide simulations demonstrating that our IA-MME constructions lead to tangible efficiency and security gains on realistic data. As a part of our techniques, we identify and correct a technical error in prior constructions — providing greater insight into issues that can arise when composing StE schemes.

With the threat posed by quantum computers on the horizon, systems like Ethereum must transition to cryptographic primitives resistant to quantum attacks. One of the most critical of these primitives is the non-interactive multi-signature scheme used in Ethereum's proof-of-stake consensus, currently implemented with BLS signatures. This primitive enables validators to independently sign blocks, with their signatures then publicly aggregated into a compact aggregate signature.

In this work, we introduce a family of hash-based signature schemes as post-quantum alternatives to BLS. We consider the folklore method of aggregating signatures via (hash-based) succinct arguments, and our work is focused on instantiating the underlying signature scheme. The proposed schemes are variants of the XMSS signature scheme, analyzed within a novel and unified framework. While being generic, this framework is designed to minimize security loss, facilitating efficient parameter selection. A key feature of our work is the avoidance of random oracles in the security proof. Instead, we define explicit standard model requirements for the underlying hash functions. This eliminates the paradox of simultaneously treating hash functions as random oracles and as explicit circuits for aggregation. Furthermore, this provides cryptanalysts with clearly defined targets for evaluating the security of hash functions. Finally, we provide recommendations for practical instantiations of hash functions and concrete parameter settings, supported by known and novel heuristic bounds on the standard model properties.

The seminal work of Goldreich and Krawczyk (SIAM Journal on Computing) shows that any constant-round public-coin interactive proof for languages not in ${\sf BPP}$ cannot be black-box zero knowledge. Their result says nothing, however, about proofs (or arguments) of knowledge for languages in ${\sf BPP}$. As a special case, their work leaves open the question of whether Schnorr's protocol for proving knowledge of discrete logarithms in cyclic groups is black-box zero knowledge.

In this work we focus on the zero knowledge of proofs of knowledge, centering on Schnorr's protocol as a prominent example. We prove two lower bounds, ruling out two different classes of simulators through which Schnorr's protocol can be proven zero knowledge:

1. We prove that if a relation $\mathcal{R}$ has a public-coin interactive proof of knowledge that is black-box zero knowledge and this protocol is compatible with the Fiat-Shamir transform in the random oracle model, then $\mathcal{R}$ must be efficiently searchable. As an immediate corollary, we deduce that Schnorr's protocol cannot be black-box zero knowledge in groups in which discrete log is hard.
2. We define a new class of simulators for Schnorr's protocol, which we call generic simulators. A generic simulator is one that works in any cyclic group, and does not use the representation of the specific group in which Schnorr's protocol is instantiated. We prove that Schnorr's protocol cannot have generic simulators.

As an additional contribution, we generalize the original lower bound of Goldreich and Krawczyk, to prove that a language not in ${\sf BPP}$ cannot have an interactive proof (not necessarily of knowledge) that is both black-box zero knowledge and compatible with the Fiat-Shamir transform in the random oracle model. In conjunction with recent works, this extends the Goldreich-Krawczyk lower bound to public-coin protocols that are not constant-round but have round-by-round soundness, including the parallel repetition of any public-coin interactive proof.

We present a new sumcheck protocol called Fold-DCS (Fold-Divide-and-Conquer-Sumcheck) for multivariate polynomials based on a divide-and-conquer strategy. Its round complexity and soundness error are logarithmic in the number of variables, whereas they are linear in the classical sumcheck protocol. This drastic improvement in number of rounds and soundness comes at the expense of exchanging multivariate polynomials, which can be alleviated using polynomial commitment schemes. We first present Fold-DCS in the PIOP model, where the prover provides oracle access to a multivariate polynomial at each round. We then replace this oracle access in practice with a multivariate polynomial commitment scheme; we illustrate this with an adapted version of the recent commitment scheme Zeromorph, which allows us to replace most of the queries made by the verifier with a single batched evaluation check.

Bulletproofs, introduced by Bünz, Bootle, Boneh, Poelstra, Wuille and Maxwell (IEEE S& P, 2018), is a highly efficient non-interactive argument system that does not require a trusted setup. Recently, Bünz (PhD Thesis, 2023) extended Bulletproofs to support arguments for rank-1 constraint satisfaction (R1CS) systems, a widely-used representation for arithmetic satisfiability problems. Although the argument system constructed by Bünz preserves the attractive properties of Bulletproofs, it presents a gap between its completeness and soundness guarantees: The system is complete for a restricted set of instances, but sound only for a significantly broader set. Although argument systems for such gap relations nevertheless provide clear and concrete guarantees, the gaps they introduce may lead to various inconsistencies or undesirable gaps within proofs of security, especially when used as building blocks within larger systems.

In this work we show that the argument system presented by Bünz can be extended to bridge the gap between its completeness and soundness, and to additionally provide honest-verifier zero-knowledge. For the extended argument system, we introduce a refined R1CS relation that captures the precise set of instances for which both completeness and soundness hold without resorting to a gap formulation. The extended argument system preserves the performance guarantees of the argument system presented by Bünz, and yields a non-interactive argument system using the Fiat-Shamir transform.

We study quantum algorithms for multivariate quadratic Boolean equation systems by focusing on their precise gate count. While better asymptotic algorithms are known, currently gate counts were only computed for exhaustive search (Schwabe and Westerbaan, SPACE 2016) and a variant of Grover's search using preprocessing (Pring, WAIFI 2018). This limits the applicability of Boolean equation solving to cryptanalysis, which considers relatively small numbers of variables (from 40 to 200) and is concerned with the exact complexity of the solver.

In this paper, we introduce two new quantum algorithms. The first algorithm is an optimized quantum exhaustive search which amortizes the cost of polynomial evaluation at each quantum search iterate. The second algorithm adapts a method of Bouillaguet et al. (SOSA 2022) which proceeds by linearization of the system. In both cases, we implement the quantum circuits, study their complexity, and obtain significant improvements over previous results.

Next, we apply these new algorithms to the cryptanalysis of the block ciphers LowMC and RAIN in the single-data setting. By adapting attacks from Liu et al. (ToSC 2022) and Liu et al. (ToSC 2023) we obtain the first quantum cryptanalysis results on these ciphers.

Recently, a number of highly optimized threshold signing protocols for Schnorr signatures have been proposed. While these proposals contain important new techniques, some of them present and analyze these techniques in very specific contexts, making it less than obvious how these techniques can be adapted to other contexts, or combined with one another. The main goal of this paper is to abstract out and extend in various ways some of these techniques, building a toolbox of techniques that can be easily combined in different ways and in different contexts. To this end, we present security results for various “enhanced” modes of attack on the Schnorr signature scheme in the non-distributed setting, and we demonstrate how to reduce the security in the distributed threshold setting to these enhanced modes of attack in the non-distributed setting. This results in a very modular approach to protocol design and analysis, which can be used to easily design new threshold Schnorr protocols that enjoy better security and/or performance properties than existing ones.

This work describes vulnerabilities in the specification of AEAD modes and Key Wrap in two cryptographic message formats. Firstly, this applies to AEAD packets as introduced in the novel LibrePGP specification that is implemented by the widely used GnuPG application. Secondly, we describe vulnerabilities in the AES-based AEAD schemes as well as the Key Wrap Algorithm specified in the Cryptographic Message Syntax (CMS). These new attacks exploit the possibility to downgrade AEAD or AES Key Wrap ciphertexts to valid legacy CFB- or CBC-encrypted related ciphertexts and require that the attacker learns the content of the legacy decryption result. This can happen in two principal ways: either due to the human recipient returning the decryption output to the attacker as a quote or due to a programmatic decryption oracle in the receiving system that reveals information about the plaintext. The attacks effect the decryption of low-entropy plaintext blocks in AEAD ciphertexts and, in the case of LibrePGP, also the manipulation of existing AEAD ciphertexts. For AES Key Wrap in CMS, full key decryption is possible. Some of the attacks require multiple successful oracle queries. The attacks thus demonstrate that CCA2 security is not achieved by the LibrePGP and CMS AEAD or Key Wrap encryption in the presence of a legacy cipher mode decryption oracle. The proper countermeasure to thwart the attacks is a key derivation that ensures the use of unrelated block cipher keys for the different encryption modes.

In a recent Eurocrypt'24 paper, Manulis and Nguyen have proposed a new CCA security notion, vCCA, and associated construction blueprints to leverage both CPA-secure and correct FHE beyond the CCA1 security barrier. However, because their approach is only valid under the correctness assumption, it leaves a large part of the FHE spectrum uncovered, as many FHE schemes used in practice turn out to be approximate and, as such, do not satisfy the correctness assumption. In this paper, we improve their work by defining and investigating a variant of their security notion which is suitable for a more general case where approximate FHE are included. As the passive security of approximate FHE schemes is more appropriately captured by CPAD rather than CPA security, we start from the former notion to define our vCCAD new security notion. Although we show that vCCA and vCCAD are equivalent when the correctness assumption holds, we establish that vCCAD security is strictly stronger than vCCA security in the general case. In doing so, we interestingly establish several new separation results between variants of CPAD security of increasing strength. This allows us to clarify the relationship between vCCA security and CPAD security, and to reveal that the security notions landscape is much simpler for correct FHE than when approximate ones are included — in which case, for example, we establish that multiple challenges security notions are strictly stronger than single-challenge ones for both CPAD and vCCAD security. Lastly, we also give concrete construction blueprints, showing how to leverage some of the blueprints proposed by Manulis and Nguyen to achieve vCCAD security. As a result, vCCAD security is the strongest CCA security notion known so far to be achievable by both correct and approximate FHE schemes.

The Learning with Errors problem (LWE) and its variants are among the most popular assumptions underlying lattice-based cryptography. The Learning with Rounding problem (LWR) can be thought of as a deterministic variant of LWE. In this work, we present a thorough study of Somewhat Homomorphic Encryption schemes based on Ring-LWR that are the analogue of the Ring-LWE-based BFV scheme. Our main contribution is to present two new schemes, in the LPR and Regev paradigms, and give a thorough analysis of their security (provable and concrete). The technical tools we developed in the process may be of independent interest to the community. Our schemes inherit the many benefits of being based on LWR, including avoiding the need for expensive Gaussian sampling and improved ciphertext size. Indeed, we give a detailed comparison showing that our schemes marginally outperform the BFV scheme in terms of ciphertext size. Moreover, we show that both our schemes support RNS variants. Our Regev-type scheme can be seen as an improved generalisation of the only prior work in this direction (Costache-Smart, 2017). In particular, our scheme resolves the tangled modulus issue in the Costache-Smart proposal that led to unmanageable noise growth, and achieves a factor n improvement in the size of the public key.

We construct an efficient proxy re-encryption (PRE) scheme secure against honest re-encryption attacks (HRA-secure) with precise concrete security estimates. To get these precise concrete security estimates, we introduce the tight, fine-grained noise-flooding techniques of Li et al. (CRYPTO'22) to RLWE-based (homomorphic) PRE schemes, as well as a mixed statistical-computational security definition to HRA security analysis. Our solution also supports homomorphic operations on the ciphertexts. Such homomorphism allows for advanced applications, e.g., encrypted computation of network statistics across networks, and unlimited hops in the case of full homomorphism, i.e., when bootstrapping is available.

We implement our PRE scheme in the OpenFHE software library and apply it to a problem of secure multi-hop data distribution in the context of 5G virtual network slices. We also experimentally evaluate the performance of our scheme, demonstrating that the implementation is practical.

Moreover, we compare our PRE method with other lattice-based PRE schemes and approaches targeting HRA security. These achieve HRA security, but not in a tight, practical scheme such as our work. Further, we present an attack on the PRE scheme proposed in Davidson et al.'s (ACISP'19), which was claimed to achieve HRA security without noise flooding, i.e., without adding large noise.

A fundamental challenge in zero-knowledge proof systems is implementing operations that are “foreign” to the underlying constraint system, in that they are arithmetic operations with a different modulus than the one used by the proof system. The modulus of the constraint system is a large prime, and common examples of foreign operations are Boolean operations, field arithmetic, or public-key cryptography operations. We present novel techniques for efficiently embedding such foreign arithmetic in zero-knowledge, including (i) equality of discrete logarithms across different groups; (ii) scalar multiplication without requiring elliptic curve operations; (iii) proving knowledge of an AES encryption. Our approach combines rejection sampling, sigma protocols, and lookup protocols. We implement and provide concrete benchmarks for our protocols.

A Bloom filter is a probabilistic data structure designed to provide a compact representation of a set S of elements from a large universe U. The trade-off for this succinctness is allowing some errors. The Bloom filter efficiently answers membership queries: given any query x, if x is in S, it must answer ’Yes’; if x is not in S, it should answer ’Yes’ only with a small probability (at most ε).

Traditionally, the error probability of the Bloom filter is analyzed under the assumption that the query is independent of its internal randomness. However, Naor and Yogev (Crypto 2015) focused on the behavior of this data structure in adversarial settings; where the adversary may choose the queries adaptively. One particular challenge in this direction is to define rigorously the robustness of Bloom filters in this model.

In this work, we continue investigating the definitions of success of the adaptive adversary. Specifically, we focus on two notions proposed by Naor and Oved (TCC 2022) and examine the relationships between them. In particular, we highlight the notion of Bet-or-Pass as being stronger than others, such as Monotone-Test Resilience.

Our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256). In total, we develop a pool of 26 implementations per AES variant (totaling 78), by taking the state-of-the-art advancements in the relevant fields into account.

We present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.'s Asiacrypt'20 paper by more than 97 percent for each variant of AES. We show that the qubit count - Toffoli depth product is reduced from theirs by more than 87 percent. Furthermore, we analyze the Jaques et al.'s Eurocrypt'20 implementations in detail, fix the bugs (arising from some problem of the quantum computing tool used), and report corrected benchmarks (which seem to improve from the authors' own bug-fixing, thanks to our architecture consideration). To the best of our finding, our work improves from all the previous works (including the Asiacrypt'22 paper by Huang and Sun, the Asiacrypt'23 paper by Liu et al. and the Asiacrypt'24 paper by Shi and Feng) in terms of various quantum circuit complexity metrics. To be more precise, we estimate the currently best-known quantum attack complexities for AES-128 ($2^{156.2630}$), AES-192 ($2^{221.5801}$) and AES-256 ($2^{286.0731}$). Additionally, we achieve the least Toffoli depth - qubit count product for AES-128 ($121920$, improving from $130720$ by Shi and Feng in Asiacrypt'24), AES-192 ($161664$, improving from $188880$ by Liu et al. in Asiacrypt'23) and AES-256 ($206528$, improving from $248024$ by Liu et al. in Asiacrypt'23) so far.

We further investigate the prospect of the Grover's search. We propose four new implementations of the S-box, one new implementation of the MixColumn; as well as five new architecture (one is motivated by the architecture by Jaques et al. in Eurocrypt'20, and the rest four are entirely our innovation). Under the MAXDEPTH constraint (specified by NIST), the circuit depth metrics (Toffoli depth, $T$-depth and full depth) become crucial factors and parallelization for often becomes necessary. We provide the least depth implementation in this respect that offers the best performance in terms of metrics like depth-squared - qubit count product, depth - gate count product.

Plaintext-ciphertext matrix multiplication (PC-MM) is an indispensable tool in privacy-preserving computations such as secure machine learning and encrypted signal processing. While there are many established algorithms for plaintext-plaintext matrix multiplication, efficiently computing plaintext-ciphertext (and ciphertext-ciphertext) matrix multiplication is an active area of research which has received a lot of attention. Recent literature have explored various techniques for privacy-preserving matrix multiplication using fully homomorphic encryption (FHE) schemes with ciphertext packing and Single Instruction Multiple Data (SIMD) processing. On the other hand, there hasn't been any attempt to speed up PC-MM using unpacked additively homomorphic encryption (AHE) schemes beyond the schoolbook method and Strassen's algorithm for matrix multiplication. In this work, we propose an efficient PC-MM from unpacked AHE, which applies Cussen's compression-reconstruction algorithm for plaintext-plaintext matrix multiplication in the encrypted setting. We experimentally validate our proposed technique using a concrete instantiation with the additively homomorphic elliptic curve ElGamal encryption scheme and its software implementation on a Raspberry Pi 5 edge computing platform. Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths. Extensive measurement results demonstrate that our fast PC-MM is an excellent candidate for efficient privacy-preserving computation even in resource-constrained environments.

Private set intersection (PSI) enables two parties to jointly compute the intersection of their private sets without revealing any extra information to each other. In this work, we focus on the unbalanced setting where one party (a powerful server) holds a significantly larger set than the other party (a resource-limited client). We present a new protocol for this setting that achieves a better balance between low client-side storage and efficient online processing.

We first formalize a general framework to transform Private Information Retrieval (PIR) into PSI with techniques used in prior works. Building upon recent advancements in Private Information Retrieval (PIR), specifically the SimplePIR construction (Henzinger et al., USENIX Security'23), combined with our tailored techniques, our construction shows a great improvement in online efficiency. Concretely, when the client holds a single element, our protocol achieves more than $100\times$ faster computation and over $4\times$ lower communication compared to the state-of-the-art unbalanced PSI based on leveled fully homomorphic encryption (Chen et al., CCS'21). The client-side storage is only in the order of tens of megabytes, even for a gigabyte-sized set on the server. Moreover, since the framework is generic, any future improvement in PIR can further improve our construction.

We present the first fully collusion resistant traceable functional encryption (TFE) scheme for identity-based inner product FE (IBIPFE) that directly traces user identities through an efficient tracing procedure. We name such a scheme as embedded identity TIBIPFE (EI-TIBIPFE) where secret keys and ciphertexts are computed for vectors, and decryption recovers the inner product between the vectors given the key and ciphertext are associated with the same group identity. Additionally, a secret key corresponds to a user identity for the purpose of tracing. Suppose some of the users linked to a particular group team up and create a pirate decoder that is capable of decrypting the content of the group, then the tracing algorithm extracts the identities of the dishonest users' given black-box access to the decoder. Previously, such schemes were designed for usual public key encryptions. In this work, we construct a fully collusion resistant EI-TIBIPFE scheme from pairings in the standard model. The ciphertext size of our scheme grows sub-linearly with the number of users in the system. We achieve many-target security of tracing, namely the adversary is allowed to ask for multiple secret keys corresponding to many functions, which notably solves an open problem raised by Do, Phan, and Pointcheval [CT-RSA'2020].

When designing filter functions in Linear Feedback Shift Registers (LFSR) based stream ciphers, algebraic criteria of Boolean functions such as the Algebraic Immunity (AI) become key characteristics because they guarantee the security of ciphers against the powerful algebraic attacks. In this article, we abstract the algebraic attacks proposed by Courtois and Meier on filtered LFSR twenty years ago, considering how the standard algebraic attack can be generalized beyond filtered LFSR to stream ciphers that employ a Boolean filter function to an updated state. Depending on the updating process, we use different sets of annihilators than those used in the standard algebraic attack; it leads to a generalization of the concept of algebraic immunity, and in some particular cases, potentially more efficient attacks. Motivated by the filter permutator paradigm, we focus on the case where the update function is a bit-permutation, since it maintains the degree of the monomials. For example the degree of the monomials of degree up to $d$ and from $n-d$ to $n$ remains invariant, which leads us to consider annihilators having only monomials of these degrees. If this number of monomials is sufficiently low, linearization is feasible, allowing the linear system to be solved and revealing the key, as in the standard algebraic attack. This particular characteristic is restricted by the standard algebraic attacks and to analyze it we introduce a new notion called Extremal Algebraic Immunity (EAI). We perform a theoretic study of the EAI criterion and explore its relation to other algebraic criteria. We prove the upper bound of the EAI of an $n$-variable Boolean function and further show that the EAI can be lower bounded by the AI restricted to a subset, as defined by Carlet, Méaux and Rotella at FSE 2017. We also exhibit functions with EAI guaranteed to be lower than the AI, in particular we highlight a pathological case of functions with optimal algebraic immunity and EAI only $n/4$. As applications, we determine the EAI of filter functions of some existing stream ciphers and discuss how extremal algebraic attacks using EAI could apply to variations of known ciphers. The extremal algebraic attack does not give a better complexity than Courtois and Meier's result on the existing stream ciphers. However, we see this work as a study to avoid weaknesses in the construction of future stream ciphers.

VDFs are characterized by sequential function evaluation but an immediate output verification. In order to ensure secure use of VDFs in real-world applications, it is important to determine the fastest implementation. Considering the point of view of an attacker (say with unbounded resources), this paper aims to accelerate the isogeny-based VDF proposed by De Feo-Mason-Petit-Sanso in 2019. It is the first work that implements a hardware accelerator for the evaluation step of an isogeny VDF. To meet our goal, we use redundant representations of integers and introduce a new lookup table-based algorithm for modular reduction. We also provide both a survey of elliptic curve arithmetic to arrive at the most cost-effective curve computations and an in-depth cost analysis of the different base degree isogeny and method for the isogeny evaluation. The evaluation step of a VDF is defined to be sequential, which means that there is limited scope for parallelism. Nevertheless, taking this constraint into account our proposed design targets the highest levels of parallelism possible on an architectural level of an isogeny VDF implementation. We provide a technology-independent metric to model the delay of isogeny evaluation, which a VDF developer can use to derive secure parameters. ASIC synthesis results in 28nm are used as a baseline to estimate VDF parameters.

In 2015, May and Ozerov proposed a new method to solve the Nearest Neighbor Problem. They also observed that it could be used as a subroutine in various Information Set Decoding (ISD) algorithms for arbitrary linear codes. This led to an asymptotic improvement in their complexity. However, the proposed improvement has been widely perceived as impractical because of the huge hidden factors in its asymptotic complexity. The main contribution of this article is to provide a sound foundation for this claim. We show that it is indeed “galactic”, namely that it only improves upon much simpler methods when instances are so large that they fill the whole universe.

More precisely, we argue that for the May-Ozerov ISD algorithm to require less operations than a technique based on the Stern ISD algorithm, the length of the code has to be greater than 1,874,400 with a number of operation beyond 2 to the power 63489, making it practically useless.

In order to protect against side-channel attacks, masking countermeasure is widely considered. Its application on asymmetric cryptographic algorithms, such as RSA implementations, rendered multiple traces aggregation inefficient and led to the development of single trace horizontal attacks. Among these horizontal attacks proposed in the literature, many are based on the use of clustering techniques or statistical distinguishers to identify operand collisions. These attacks can be difficult to implement in practice, as they often require advanced trace pre-processing, including the selection of points of interest, a step that is particularly complex to perform in a non-profiling context. In recent years, numerous studies have shown the effectiveness of deep learning in security evaluation for conducting side-channel attacks. However, few attentions have been given to its application in asymmetric cryptography and horizontal attack scenarios. Additionally, the majority of deep learning attacks tend to focus on profiling attacks, which involve a supervised learning phase. In this paper, we propose a new non-profiling horizontal attack using an unsupervised deep learning method called Deep Canonical Correlation Analysis. In this approach, we propose to use a siamese neural network to maximize the correlation between pairs of modular operation traces through canonical correlation analysis, projecting them into a highly correlated latent space that is more suitable for identifying operand collisions. Several experimental results, on simulated traces and a protected RSA implementation with up-to-date countermeasures, show how our proposal outperformed state-of-the-art attacks despite being simpler to implement. This suggests that the use of deep learning can be impactful for security evaluators, even in a non-profiling context and in a fully unsupervised way.

We provide a high-level cost comparison between Regev's quantum algorithm with Ekerå–Gärtner's extensions on the one hand, and existing state-of-the-art quantum algorithms for factoring and computing discrete logarithms on the other. This when targeting cryptographically relevant problem instances, and when accounting for the space-saving optimizations of Ragavan and Vaikuntanathan that apply to Regev's algorithm, and optimizations such as windowing that apply to the existing algorithms.

Our conclusion is that Regev's algorithm without the space-saving optimizations may achieve a per-run advantage, but not an overall advantage, if non-computational quantum memory is cheap. Regev's algorithm with the space-saving optimizations does not achieve an advantage, since it uses more computational memory, whilst also performing more work, per run and overall, compared to the existing state-of-the-art algorithms. As such, further optimizations are required for it to achieve an advantage for cryptographically relevant problem instances.

We investigate the side-channel security of ISAP against Algebraic Side-Channel Attacks (ASCA) in a simulated setting where the Hamming weight leakages of its intermediate computations can be recovered. For this purpose, we first describe how these attacks, so far only used to target 8-bit implementations, can be applied to 16-bit or 32-bit implementations. We then use ASCA to discuss the side-channel security claims of ISAP's re-keying, where a single bit of nonce is absorbed per permutation call. Theoretically, this re-keying aims to ensure that attacking more than one permutation call jointly does not improve over attacking the same number of permutation calls independently. Yet, while this expectation is expected to be met for ISAP's conservative parameters (where permutation calls are made of 12 Ascon rounds), the extent to which it does (not) hold for ISAP's aggressive parameters (where permutation calls are made of a single Ascon round) remains an open question. We contribute to this question by showing that for 16-bit implementations, combining the leakages of multiple permutation calls can improve over attacking the same number of permutation calls independently, which contradicts ISAP's (theoretical) leakage-resistance claims. By contrast, for 32-bit leakages, we only show similar weaknesses by guessing a large part of the target state (i.e., more than 128 bits), which only impacts the initialization of ISAP's re-keying and does not contradict its security reduction. These results confirm that for hardware implementations with a sufficient level of parallelism, ISAP's aggressive parameters are probably sufficient, but that for more serial (e.g., software) implementations, slightly more conservative parameters, or the addition of implementation-level countermeasures, are needed.

We provide several attacks on the BASS signature scheme introduced by Grigoriev, Ilmer, Ovchinnikov and Shpilrain in 2023. We lay out a trivial forgery attack which generates signatures passing the scheme's probabilistic signature verification with high probability. Generating these forgeries is faster than generating signatures honestly. Moreover, we describe a key-only attack which allows us to recover an equivalent private key from a signer's public key. The time complexity of this recovery is asymptotically the same as that of signing messages.

Efficient implementation of some privacy-preserving algorithms and applications rely on efficient implementation of homomorphic inversion. For example, a recently proposed homomorphic image filtering algorithm and the privacy-preserving body mass index (BMI) calculations repetitively use homomorphic inversion. In this paper, inspired by Montgomery's trick to perform simultaneous plaintext inversion, we tackle the simultaneous homomorphic inversion problem to compute s inverses simultaneously over ciphertexts. The advantage of Montgomery's trick for plaintext arithmetic is well-known. We first observe that the advantage can quickly vanish when homomorphic encryption is employed because of the increased depth of the circuits. Therefore, we propose three algorithms (Montgomery's trick and two other variants) that reduce the number of homomorphic inversions from s to 1 and that offer different levels of trade-offs between the number of multiplications and the circuit depth. We provide a theoretical complexity analysis of our algorithms and implement them using the CKKS scheme in the OpenFHE library. Our experiments show that, for some cases, the run time of homomorphic s-inversion can be improved up to 35 percent while in some other cases, regular inversion seems to outperform Montgomery-based inversion algorithms.

In this paper, we study MDS matrices that are specifically designed to prevent the occurrence of related differentials. We investigate MDS matrices with a Hadamard structure and demonstrate that it is possible to construct 4 X 4 Hadamard matrices that effectively eliminate related differentials. Incorporating these matrices into the linear layer of AES-like block-ciphers/hash functions significantly mitigates the attacks that exploit the related differentials property. The central contribution of this paper is to identify crucial underlying relations that determine whether a given 4 X 4 Hadamard matrix exhibits related differentials. By satisfying these relations, the matrix ensures the presence of related differentials, whereas failing to meet them leads to the absence of such differentials. This offers effective mitigation of recently reported attacks on reduced-round AES. Furthermore, we propose a faster search technique to exhaustively verify the presence or absence of related differentials in 8 X 8 Hadamard matrices over finite field of characteristic 2 which requires checking only a subset of involutory matrices in the set. Although most existing studies on constructing MDS matrices primarily focus on lightweight hardware/software implementations, our research additionally introduces a novel perspective by emphasizing the importance of MDS matrix construction in relation to their resistance against differential cryptanalysis.

We introduce a framework based on Bayesian statistical inference for analyzing leakage in cryptography and its vulnerability to inference attacks. Our framework naturally integrates auxiliary information, defines a notion of adversarial advantage, and provides information-theoretic measures that capture the security of leakage patterns against both full and functional recovery attacks.

We present two main theorems that bound the advantage of powerful inference techniques: the maximum a posteriori (MAP), the maximum likelihood estimate (MLE) and the MAP test. Specifically, we show that the advantage of these methods is exponentially bounded by new entropy measures that capture the susceptibility of leakage patterns to inference.

To demonstrate the applicability of our framework, we design and implement an automated leakage attack engine, Bayle, which leverages a novel inference algorithm that efficiently computes MAP estimates for a large class of i.i.d. leakage models. These models include query equality leakage, the combination of query equality and volume leakage, and leakage patterns arising from naive conjunctions.

Making the most of TFHE advanced capabilities such as programmable or circuit bootstrapping and their generalizations for manipulating data larger than the native plaintext domain of the scheme is a very active line of research. In this context, AES is a particularly interesting benchmark, as an example of a nontrivial algorithm which has eluded “practical” FHE execution performances for years, as well as the fact that it will most likely be selected by NIST as a flagship reference in its upcoming call on threshold (homomorphic) cryptography. Since 2023, the algorithm has thus been the subject of a renewed attention from the FHE community and has served as a playground to test advanced operators following the LUT-based, p-encodings or several variants of circuit bootstrapping, each time leading to further timing improvements. Still, AES is also interesting as a benchmark because of the tension between boolean- and byte-oriented operations within the algorithm. In this paper, we resolve this tension by proposing a new approach, coined “Hippogryph”, which consistently combines the (byte-oriented) LUT-based approach with a generalization of the (boolean-oriented) $p$-encodings one to get the best of both worlds. In doing so, we obtain the best timings so far, getting a single-core execution of the algorithm over TFHE from 46 down to 32 seconds and approaching the $1$ second barrier with only a mild amount of parallelism. We should also stress that all the timings reported in this paper are consistently obtained on the same machine which is often not the case in previous studies. Lastly, we emphasize that the techniques we develop are applicable beyond just AES since the boolean-byte tension is a recurrent issue when running algorithms over TFHE.

Persistent Fault Attacks (PFA) have emerged as an active research area in embedded cryptography. This attack exploits faults in one or multiple constants stored in memory, typically targeting S-box elements. In the literature, such persistent faults primarily induced by bit flips in storage, often achieved through laser fault injection techniques. In this paper, we demonstrate that persistent faults can also be induced through instruction skips, which can easily be achieved with almost any fault injection methods (e.g., voltage/clock glitching, electromagnetism). Specifically, we target AES implementations that dynamically generate the S-box table at runtime, during the initialization phase, before executing the first AES operation. We illustrate this with an attack on the AES implementation in the MbedTLS library, where a clock glitch is inserted during the S-box generation. Secondly, we introduce, to our knowledge, the first PFA that targets a constant other than the S-box elements. We show that faulting a round constant involved in the AES key schedule is sufficient to recover the key by a differential analysis. Compared to previous PFAs that rely on statistical analysis requiring hundreds to thousands of ciphertexts, our approach needs only three correct-faulty ciphertexts pairs. We showcase this attack with an experiment on the MbedTLS AES implementation, using a clock glitch in the round constant generation.