International Association
for Cryptologic Research

Many post-quantum cryptosystems require generating an $n$-bit binary vector with a prescribed Hamming weight $\omega$, a process known as \emph{fixed-weight sampling}. When $\omega = O(n)$, we call this \emph{dense} fixed-weight sampling, which commonly appears in lattice-based cryptosystems, like those in the NTRU family. In contrast, code-based cryptosystems typically use \emph{sparse} fixed-weight sampling with $\omega = O(\sqrt{n})$. Sparse fixed-weight sampling generally involves three constant-time steps to keep the sampled vector secret: 1. sample $\omega$ nearly uniform random integers from a series of decreasing intervals; 2. map these integers into a set of $\omega$ distinct indices in $[0, n)$, called the \emph{support}; 3. generate a binary $n$-bit vector with bits set only at the support indices. Remarkably, some of the core algorithms employed in fixed-weight sampling date back to nearly a century, yet developing efficient and secure techniques remains essential for modern post-quantum cryptographic applications. In this paper, we present novel algorithms for steps two and three of the fixed-weight sampling process. We demonstrate their practical applicability by replacing the current fixed-weight sampling routine in the HQC post-quantum key exchange mechanism, recently selected for NIST standardization. We rigorously prove that our procedures are sound, secure, and introduce little to no bias. Our implementation of the proposed algorithms accelerates step 2 by up to $2.63\times$ and step 3 by up to $5.20\times$ compared to an optimized version of the fixed-weight sampler currently used in HQC. Since fixed-weight sampling constitutes a significant portion of HQC’s execution time, these speedups translate into protocol-level improvements of up to $1.36\times$, $1.23\times$ and $1.17\times$ for key generation, encapsulation and decapsulation, respectively.

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is widely adopted for securely evaluating circuits over real numbers, such as those arising in privacy-preserving machine learning (PPML), because it efficiently supports approximate floating-point arithmetic of messages. A CKKS ciphertext has a finite level, which corresponds to the budget for how many multiplicative operations can be applied. Once these levels are consumed, the ciphertext must be refreshed through a bootstrapping procedure to restore its capacity for further computation. However, bootstrapping itself also consumes a significant number of levels, leaving fewer levels after each bootstrapping.

In this work, we propose three techniques—OverModRaise1, OverModRaise2, and Tuple-C2S/S2C—that target reductions in the modulus consumption of C2S/S2C among the CKKS bootstrapping procedures, without introducing substantial overhead or compromising security. By combining these techniques, our implementation demonstrates a 27–61% throughput improvement compared to the state-of-the-art bootstrapping.

Ateniese et al. (CRYPTO 2019/JoC 2021) introduced a cryptographic primitive which they call matchmaking encryption (ME), and Identity-based ME (IB-ME) is its identity-based variant. IB-ME supports an equality matching where a sender (encryptor) indicates a receiver's (decryptor's) identity (rcv) in addition to their own ID ($\sigma$), and a receiver indicates a sender's identity (snd) in addition to the own identity ($\rho$). A ciphertext is decrypted if $(\sigma,\rho)=$(snd,rcv). In this paper, we pay attention to the search condition of public key authenticated encryption with keyword search (PAEKS) (Huang-Li, Information Sciences 2017) is reminiscent of the equality matching. We introduce a public key variant of ME which we call PK-ME, and propose a generic construction of PK-ME from PAEKS. As a conceptual contribution, our work lies in revealing a connection between ME and public key searchable encryption, which were independently researched so far. Due to the generic construction of PAEKS (Li-Boyen, IACR CiC 2024), we can instantiate the proposed generic construction from pairings or lattices. We also introduce a weaker version of authenticity and show that it can be instantiated from several complexity assumptions. Finally, we discuss the advantage/disadvantage of PK-ME compared to IB-ME.

A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. '94] shows that zero-knowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs --- namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message).

Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that **every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness.** This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is "game-based" instead of "simulation-based."

Our construction builds on the work of Kuykendall and Zhandry [TCC '20] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is Krajícek and Pudlák's 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbert's second problem (and, hence, also Gödel's incompleteness theorem). Our high-level idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC.

In this paper, we discuss refined Humbert invariants, introduced by Kani in 1994. We show that in the contexts of SQISign and CSIDH, under GRH, the computational isogeny problem is polynomially equivalent to the computational refined Humbert invariant problem. This includes an algorithm to compute the basis of a maximal order of a quaternion algebra given its norm form. Finally, we also review what is known in the literature about computing refined Humbert invariants.

In this work, we present Interstellar, a novel folding and IVC framework built on a technique we call circuit interpolation, designed specifically for circuit satisfiability. By incorporating the GKR protocol, our approach avoids commitments to full computation traces and cross-term vectors, requiring instead only commitments to the actual circuit witness and optionally a small subset of intermediate gate values. This design significantly reduces the size of the vectors to be committed to in each folding step, which is an important advantage over existing schemes, as vector commitments typically incur costly group multi-scalar multiplications. Moreover, Interstellar is highly flexible. It can be extended naturally to handle high-degree and lookup gates, enable multi-instance folding, and support non-uniform IVC efficiently, making it well-suited for practical applications ranging from zkML to proving program execution for zkVMs. We instantiate our protocol with various vector/polynomial commitment schemes and provide detailed cost analyses, demonstrating substantial reductions in prover overhead compared to existing approaches.

Developers implementing elliptic curve cryptography (ECC) face a wide range of implementation choices created by decades of research into elliptic curves. The literature on elliptic curves offers a plethora of curve models, scalar multipliers, and addition formulas, but this comes with the price of enabling attacks to also use the rich structure of these techniques. Navigating through this area is not an easy task and developers often obscure their choices, especially in black-box hardware implementations. Since side-channel attackers rely on the knowledge of the implementation details, reverse engineering becomes a crucial part of attacks.

This work presents ECTester -- a tool for testing black-box ECC implementations. Through various test suites, ECTester observes the behavior of the target implementation against known attacks but also non-standard inputs and elliptic curve parameters. We analyze popular ECC libraries and smartcards and show that some libraries and most smartcards do not check the order of the input points and improperly handle the infinity point. Based on these observations, we design new techniques for reverse engineering scalar randomization countermeasures that are able to distinguish between group scalar randomization, additive, multiplicative or Euclidean splitting. Our techniques do not require side-channel measurements; they only require the ability to set custom domain parameters, and are able to extract not only the size but also the exact value of the random mask used. Using the techniques, we successfully reverse-engineered the countermeasures on 13 cryptographic smartcards from 5 major manufacturers -- all but one we tested on. Finally, we discuss what mitigations can be applied to prevent such reverse engineering, and whether it is possible at all.

We introduce a new key recovery attack on the public-key encryption scheme using matrix codes proposed by Aragon et al. in Asiacrypt 2024. The secret key is a matrix code obtained by expanding an $\mathbb{F}_{q^m}$-linear Gabidulin code over an $\mathbb{F}_{q}$-basis of $\mathbb{F}_{q^m}$. This code is hidden by appending random rows and columns to a basis and then left- and right-multiplying by scrambling matrices. We show how to recover the secret code with an exponential complexity that is generally better than the current best distinguisher. This also breaks a few of their proposed parameters. Our attack does not rely on the Gabidulin structure and thus applies to most $\mathbb{F}_{q^m}$-linear codes hidden by their transform.

We provide minimal counterexamples for the security of the BitVM3 garbling scheme: our attack allows the evaluator to forge input and output wires. Then we use the same idea to exhibit an attack on the forward label propagation garbling scheme proposed in a more recent paper. In both cases, the authenticity property of the garbling scheme is broken.

Remote power analysis is a novel threat to information systems. Under this attack model, the adversary does not require direct physical access to the platform or specialized sensing equipment. Most of the literature in this field deals with advanced acquisition methods and adversarial models. In contrast, side-channel analysis techniques for remote attacks have not been sufficiently explored. We bridge this gap by taking a look at the characteristics of the data recovered from remote power analysis. We use these insights to propose a novel selection rule for correlation-based attacks that boosts success confidence. This improvement comes from the observation that the samples in a power trace are not independent. We show that adjacent samples can also provide useful information by proposing a post-processing step that capitalizes on these additional leakages. In contrast to previous work, the proposed technique does not rely on the selection of points of interest within the power traces. We further investigate the characteristics of "remote" power traces and their effect on the proposed selection rule through experiments with real (TDC, ChipWhisperer) and synthetic data sets. To assess the advantage of the proposed improvement, we also introduce novel performance metrics that divert from known-key evaluation techniques.

Federated learning (FL) proposes to train a global machine learning model across distributed datasets. However, the aggregation protocol as the core component in FL is vulnerable to well-studied attacks, such as inference attacks, poisoning attacks [71] and malicious participants who try to deviate from the protocol [24]. Therefore, it is crucial to achieve both malicious security and poisoning resilience from cryptographic and FL perspectives, respectively. Prior works either achieve incomplete malicious security [76], address issues by using expensive cryptographic tools [22, 59] or assume the availability of a clean dataset on the server side [32]. In this work, we propose AlphaFL, a two-server secure aggregation protocol achieving both malicious security in the universal composability (UC) framework [19] and poisoning resilience in FL (thus malicious$^2$) against a dishonest majority. We design maliciously secure multi-party computation (MPC) protocols [24, 26, 48] and introduce an efficient input commitment protocol tolerating server-client collusion (dishonest majority). We also propose an efficient input commitment protocol for the non-collusion case (honest majority), which triples the efficiency in time and quadruples that in communication, compared to the state-of-the-art solution in MP-SPDZ [46]. To achieve poisoning resilience, we carry out $L_\infty$ and $L_2$-Norm checks with a dynamic $L_2$-Norm bound by introducing a novel silent select protocol, which improves the runtime by at least two times compared to the classic select protocol. Combining these, AlphaFL achieves malicious$^2$ security at a cost of 25% − 79% more runtime overhead than the state-of-the-art semi-malicious counterpart Elsa [76], with even less communication cost.

During NIST's post-quantum cryptography standardization process, two generic transforms, Fujisaki-Okamoto (FO) and OAEP, are widely used to achieve the IND-CCA security. For instance, the final winner Kyber has utilized FO, and a variant of the 3rd-round finalist NTRU has utilized OAEP. The FO and OAEP are both constructed in the random oracle model (ROM), so to evaluate their post-quantum security, a security proof in the quantum random oracle model (QROM) is required. So far, the QROM security proof of FO has been given and improved by a sequence of works, however, the QROM security proof of OAEP has not been fully explored: current proofs either introduced an extra plaintext-confirming hash to the ciphertext (TCC 2016), or required parameter restrictions and a quantum collision-resistant term (PKC 2022). In this paper, by reorganizing the proof route, we give a new QROM security proof of plain OAEP. The key techniques used in our proof are the compressed oracle technique proposed by Zhandry (CRYPTO 2019) and the Fixed Permutation One-Way to Hiding recently proposed by Jaeger (Eprint 2024/797), and our proof has the following three advantages: \begin{itemize} \item Similar to Ebrahimi’s proof (PKC 2022), our proof also achieves the stronger IND-qCCA security, where the decryption oracle can be accessed in superposition. \item The parameter restrictions "$n+k_1\geq k_0$" and "$k_0-n=\mathcal{O}(n)$" introduced in Ebrahimi’s proof (PKC 2022) are removed. \item The reliance on the collision resistance of quantum random oracles required in Ebrahimi’s proof (PKC 2022) is avoided, and hence our security bound does not introduce the quantum collision-resistant term "$\mathcal{O}(q^3/2^{n+k_1})$". \end{itemize}

A critical aspect of securing cryptographic hardware is their resistance to FI attacks, which involve the successful injection of faults into the system in operation. Specifically, a hardware design must be resilient to well-established fault injection techniques, including voltage or clock glitching, laser fault injections, and the more recently introduced EMFI. Ideally, the protection level must be verified before the chip is fabricated. Although initial efforts to verify the resistance of hardware designs against fault injection have been made, analyzing the security of practical designs with realistic gate counts under fault injections that affect multiple gates or the entire circuit state remains a significant challenge. This scenario, however, is considered more realistic than assessing resistance to a fixed, relatively small number of faults.

In this work, we introduce FIESTA, a versatile automated framework for analyzing the resistance of hardware circuits under the general random fault model. By leveraging a non-exhaustive approach, FIESTA is capable of evaluating larger designs compared to state-of-the-art tools, while maintaining a reasonable level of confidence. FIESTA supports various adversary models, allowing customized resistance analysis against specific adversaries. In particular, we present a concrete procedure for evaluating more realistic precise adversaries, based on practical observations. Using FIESTA, we assessed the resistance of several (protected) AES cores.

Classical Shadow Tomography (Huang, Kueng and Preskill, Nature Physics 2020) is a method for creating a classical snapshot of an unknown quantum state, which can later be used to predict the value of an a-priori unknown observable on that state. In the short time since their introduction, classical shadows received a lot of attention from the physics, quantum information, and quantum computing (including cryptography) communities. In particular there has been a major effort focused on improving the efficiency, and in particular depth, of generating the classical snapshot.

Existing constructions rely on a distribution of unitaries as a central building block, and research is devoted to simplifying this family as much as possible. We diverge from this paradigm and show that suitable distributions over \emph{states} can be used as the building block instead. Concretely, we create the snapshot by entangling the unknown input state with an independently prepared auxiliary state, and measuring the resulting entangled state. This state-based approach allows us to consider a building block with arguably weaker properties that has not been studied so far in the context of classical shadows. Notably, our cryptographically-inspired analysis shows that for \emph{efficiently computable} observables, it suffices to use \emph{pseudorandom} families of states. To the best of our knowledge, \emph{computational} classical shadow tomography was not considered in the literature prior to our work.

Finally, in terms of efficiency, the online part of our method (i.e.\ the part that depends on the input) is simply performing a measurement in the Bell basis, which can be done in constant depth using elementary gates.

We present the first horizontally scalable SNARK for general circuits that is both transparent and plausibly post-quantum (PQ) secure. This system adapts the distributed proof generation technique introduced in Pianist (IEEE S&P 2024), which achieves linear scalability by encoding witnesses using bivariate polynomials and committing to them using the KZG polynomial commitment scheme. While Pianist and other scalable SNARK systems offer strong performance profiles, they rely on trusted setup ceremonies and cryptographic assumptions that are not PQ secure, e.g., pairing-based primitives. In contrast, we present a bivariate polynomial commitment scheme based on FRI, achieving a transparent and plausibly PQ alternative. Distributed FRI has a high communication cost. Therefore, we introduce Fold-and-Batch, a customizable technique that applies partial folding locally before performing batched FRI centrally. We formally prove the security of our constructions and provide an implementation for three variants of distributed FRI with thorough performance evaluations. Our results show that Fold-and-Batch reduces communication overhead compared to existing distributed FRI approaches while preserving scalability and keeping proof sizes moderate. To our knowledge, this is the first horizontally scalable SNARK for general circuits that at the same time achieves transparency, plausible PQ security, with a tunable tradeoff between efficiency, verifier cost and communication.

Regular Syndrome Decoding (RSD) is a variant of the traditional Syndrome Decoding (SD) problem, where the error vector is divided into consecutive, equal-length blocks, each containing exactly one nonzero element. Recently, RSD has gained significant attention due to its extensive applications in cryptographic constructions, including MPC, ZK protocols, and more. The computational complexity of RSD has primarily been analyzed using two methods: Information Set Decoding (ISD) approach and algebraic approach.

In this paper, we introduce a new hybrid algorithm for solving the RSD problem. This algorithm can be viewed as replacing the meet-in-the-middle enumeration in ISD with a process that solves quadratic equations. Our new algorithm demonstrates superior performance across a wide range of concrete parameters compared to previous methods, including both ISD and algebraic approaches, for parameter sets over both large fields (q = 2^128) and binary fields (q = 2). For parameter sets used in prior works, our algorithm reduces the concrete security of RSD by up to 20 bits compared to the state-of-the-art algorithms. We also provide an asymptotic analysis, identifying a broader parameter region where RSD is solvable in polynomial time compared to ISD and algebraic methods over binary fields. Additionally, we apply our algorithm to evaluate the security of the ZK protocol Wolverine (IEEE S&P 2021) and the OT protocol Ferret (ACM CCS 2020). Our results reduce the security level of Wolverine, which targets a 128-bit security level, to about 111 bits, and also marginally lowers the security of Ferret below the targeted 128-bit level for the first time.

Non-degenerate bilinear maps on elliptic curves, commonly referred to as pairings, have many applications including short signature schemes, zero-knowledge proofs and remote attestation protocols. Computing a state-of-the-art pairing at the $128$-bit security level, such as the optimal ate pairing over the curve BLS12-381, is very costly due to the high complexity of some of its sub-operations: most notable are the Miller loop and final exponentiation. In the past ten years, a few optimized pairing implementations have been introduced in the literature, but none of those took advantage of the vector (resp., SIMD) extensions of modern Intel and AMD CPUs, especially AVX-512; this is surprising, because doing so offers the potential to reach significant speed-ups. Consequently, the questions of 1) how computation of the optimal ate pairing can be effectively vectorized, and 2) what execution time such a vectorized implementation can achieve are still open. This paper addresses said questions by introducing a carefully-optimized AVX-512 implementation of the optimal ate pairing on BLS12-381. A central feature of the implementation is the use of $8$-way Integer Fused Multiply-Add (IFMA) instructions, which are capable to execute eight $52 \times 52$-bit multiplications in a SIMD-parallel fashion. We introduce new vectorization strategies and describe optimizations of existing ones to speed up arithmetic operations in the extension fields $\mathbb{F}_{p^4}$, $\mathbb{F}_{p^6}$, and $\mathbb{F}_{p^{12}}$ as well as certain higher-level functions. Furthermore, we discuss some parallelization bottlenecks and how they impact execution time. We benchmarked our pairing software, which we call avxbls, on an Intel Core i3-1005G1 ("Ice Lake") CPU and found that it needs $1,265,314$ clock cycles (resp., $1,195,236$ clock cycles) for the full pairing, with the Granger-Scott cyclotomic squaring (resp., compressed cyclotomic squaring) being used in the final exponentiation. For comparison, the non-vectorized (i.e., scalar) x64 assembly implementation from the widely-used blst library has an execution time of $2,351,615$ cycles, which is $1.86$ times (resp., $1.97$ times) slower. avxbls also outperforms Longa's implementation (CHES 2023) by almost the same factor. The practical importance of these results is amplified by Intel's recent announcement to support AVX10, which includes IFMA instructions, in all future CPUs.

We propose a novel partial key exposure attack on common prime RSA by leveraging lattice-based techniques. In common prime RSA, the primes $p$ and $q$ are defined as $p=2ga+1$ and $q=2gb+1$ for a common prime $g$. Recently, Zheng introduced the first partial key exposure attack on this scheme; however, it is limited to instances where $g > N^{1/4}$. In contrast, our work investigates deeper into partial key exposure attacks by presenting a unified generic case that targets one consecutive unknown block of the private key. By employing a lattice-based solving strategy for trivariate integer polynomials, we can effectively identify additional weak private keys that are vulnerable to partial exposure. Extensive numerical experiments validate the correctness and practicality of our proposed attack on common prime RSA.

In this paper, we present a new small private exponent attack on RSA by combining continued fractions and Coppersmith's techniques. Our results improve upon previous bounds, including Herrmann-May's attack, by leveraging a crucial relation derived from continued fraction. Additionally, we extend the range of vulnerable small private exponents by considering the partial leakage of prime factors or their sum. Our main result establishes an improved attack bound $ d < N^{1-\alpha/3-\gamma/2} $, where $ \alpha := \log_{N} e $ and $ \gamma := \log_{N} |p+q-S| $, with $ S $ being an approximation of the prime sum $ p+q $. Furthermore, we explore more applications of our main attack in scenarios where the primes share some most or least significant bits. The validity of our proposed main attack is confirmed through numerical experiments, demonstrating its improved performance over existing attacks.

Patient monitoring in hospitals, nursing centers, and home care can be largely automated using cameras and machine-learning-based video analytics, thus considerably increasing the efficiency of patient care. In particular, Facial-expression-based Pain Assessment Systems (FePAS) can automatically detect pain and notify medical personnel. However, current FePAS solutions using cloud-based video analytics offer very limited security and privacy protection. This is problematic, as video feeds of patients constitute highly sensitive information. To address this problem, we introduce SecFePAS, the first FePAS solution with strong security and privacy guarantees. SecFePAS uses advanced cryptographic protocols to perform neural network inference in a privacy-preserving way. To counteract the significant overhead of the used cryptographic protocols, SecFePAS uses multiple optimizations. First, instead of a cloud-based setup, we use edge computing with a 5G connection to benefit from lower network latency. Second, we use a combination of transfer learning and quantization to devise neural networks with high accuracy and optimized inference time. Third, SecFePAS quickly filters out unessential frames of the video to focus the in-depth analysis on key frames. We tested SecFePAS with the SqueezeNet and ResNet50 neural networks on a real pain estimation benchmark. SecFePAS outperforms state-of-the-art FePAS systems in accuracy and optimizes secure processing time.