International Association
for Cryptologic Research

Zero-knowledge codes, introduced by Decatur, Goldreich, and Ron (ePrint 1997), are error-correcting codes in which few codeword symbols reveal no information about the encoded message, and have been extensively used in cryptographic constructions. Quantum CSS codes, introduced by Calderbank and Shor (Phys. Rev. A 1996) and Steane (Royal Society A 1996), are error-correcting codes that allow for quantum error correction, and are also useful for applications in quantum complexity theory. In this short note, we show that (linear, perfect) zero-knowledge codes and quantum CSS codes are equivalent. We demonstrate the potential of this equivalence by using it to obtain explicit asymptotically-good zero-knowledge locally-testable codes.

The algebraic group model (AGM), formalized by Fuchsbauer, Kiltz, and Loss (Crypto 2018), has recently garnered significant attention. Notably, Katz, Zhang, and Zhou (Asiacrypt 2022) challenged a widely held belief: that hardness results proven in the AGM imply corresponding results in the generic group model (GGM). They showed that this implication fails under Shoup's GGM framework. In response, Jaeger and Mohan (Crypto 2024) proposed an alternative interpretation based on Maurer's GGM and proved that, under this interpretation, the implication indeed holds.

Many cryptographic applications analyzed in the AGM also rely on the random oracle model (ROM), which is largely absent from Jaeger and Mohan's framework. Because Maurer’s GGM and the ROM are inherently incomparable, Jaeger and Mohan's framework may not capture all AGM-based proofs. To bridge this gap and faithfully translate all known AGM-based proofs into the GGM setting, we make the following contributions:

- Limitations of JM's framework: Jaeger and Mohan’s framework captures only those primitives that can be instantiated within Maurer’s GGM. We identify a primitive—specifically, a public-key encryption scheme with short ciphertexts—whose security has been analyzed in the AGM, and establish a black-box separation between this primitive and Maurer’s GGM, even when combined with the ROM. This result provides concrete evidence that JM’s framework cannot encompass all known AGM-based proofs.

- Augmented framework: We propose an augmented framework that integrates Maurer’s GGM with a carefully constructed ROM, enabling inputs and outputs to incorporate group elements defined within Maurer’s model. - Transferring all known AGM-based proofs to GGM setting: Building on our augmented framework, we prove the lifting lemma from the AGM to our model, demonstrating that hardness results in the AGM+ROM directly carry over to our setting, thereby justifying all known AGM-based proofs.

We show how to translate some of the more advanced techniques used in LWE-based cryptography to the setting of lattice-isomorphism-based cryptography, which was recently introduced by Ducas and van Woerden [Eurocrypt, 2022]. In particular, we show constructions of two powerful cryptographic primitives, identity-based encryption (IBE) and fully homomorphic encryption (FHE). We then prove their security under the assumption that a suitable version of the Lattice Isomorphism Problem is hard.

Our constructions use quite general and modular techniques, and we expect them to have other applications. Specifically, we show that the now-ubiquitous techniques introduced by Gentry, Peikert, and Vaikuntanathan [STOC, 2008] to build IBE and Gentry, Sahai, and Waters [Crypto, 2013] to build FHE can be made to work in our setting using any sufficiently "nice" lattice.

Model extraction attacks aim to recover the internal parameters of neural networks through black-box queries. While significant progress has been achieved for fully connected ReLU networks, far less is known about structured architectures such as Convolutional Neural Networks (CNNs), which are widely used in practice. In particular, convolutional layers introduce locality and weight sharing, while max-pooling operations leak only relative activation information, both of which require rethinking and extending existing extraction techniques. In this work, we study the extraction of CNNs combining ReLU activations and max-pooling layers in the soft-label setting. We first demonstrate that max-pooling can be understood as a natural extension of the ReLU non-linear operation and classify the different types of critical points observed in this setting. We show that max-pooling critical points capture the difference between two convolutional neurons and that the local structure of convolution allows us to determine the shift between them and reconstruct the underlying convolutional kernel. We also introduce optimizations that take advantage of the specific structure of CNNs: by using receptive-field analysis, we design efficient methods to filter noise and localize critical points. These improvements significantly reduce the computational cost compared to a naive reduction to a large sparse fully connected network. Finally, we validate our approach experimentally on a compact VGG-style convolutional neural network trained on CIFAR-10. The results show that our methods permit accurate weight extraction in CNNs in practice, while correctly localizing critical points in convolutional layers.

Individual genomic data is a uniquely sensitive type of user data. While many papers have considered using Multi-Party Computation (MPC) or Fully Homomorphic Encryption (FHE) to allow collaborators to study combined genomic datasets they cannot share, few have considered verifying the results of genomic computations, either in research studies or in the emerging area of personalized genetic therapies.

In this paper, we initiate the first systematic study of zero-knowledge proofs for verifiable genomics, providing both building blocks for verifying common operations in computational genomics, such as sequence alignment, and exploring two end-to-end applications:

Verifiable Genome-Wide Association Studies: A Genome-Wide Association Study (GWAS) study operates over a repository of genomic data, identifying statistical correlations between genetic variations and observed traits or medical conditions. Our system enables third parties to verify that research was honestly computed over an authenticated, untampered database, ensuring both the integrity of the underlying data set and the correctness of the resulting science. We achieve practical performance (<20 minutes proving time) for studies of sizes equal to those in the existing genomics literature.

Verifiable CRISPR Eligibility: We propose using zk-SNARKs in the context of gene engineering (e.g. CRISPR). To our knowledge, this is a new use case for zk-SNARKs. We implement and optimize models for detecting “on-target” and “off-target” sites for a CRISPR probe in zk-SNARKs, so users can, for example, demonstrate eligibility for a therapy or trial without having to reveal their own DNA sequence.

In support of these applications, we develop new building blocks, like zero-knowledge proofs of sequence alignment that are 30x faster than the prior state of the art, and storage-efficient indexes for Merkle trees for large scale genomic data that asymptotically reduce storage costs.

This survey article provides an overview of the Semigroup Action Problem (SAP) as a pivotal generalization of the Discrete Logarithm Problem (DLP), tracing its theoretical evolution from foundational algebraic cryptography in the early 2000s to its application in the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization process. We examine the mathematical framework of semigroup actions, contrasting them with classical group-theoretic assumptions, and detail the generalizations of Diffie-Hellman and ElGamal protocols within this broader context. Finally, the paper investigates the renaissance of group and semigroup actions in the design of next-generation digital signatures, providing a detailed algebraic analysis of candidates in the current NIST competition.

Hamming Quasi-Cyclic (HQC) is a leading code-based key-encapsulation mechanism (KEM), recently selected by NIST for standardization, whose bandwidth and efficiency are balanced with the concrete cost of information-set decoding (ISD) attacks. However, the current balance relies on (1) the decryption-failure-rate (DFR) is directly configured to be less than $2^{-\lambda}$ ($\lambda$ is the security parameter), rather than carefully determined by choosing conservative parameters to resist known attacks as the Kyber team did in the design of NIST FIPS 203; (2) the error distribution in the underlying quasi-cyclic syndrome decoding problem is restricted to be balanced.

In this paper, we show how to quantitatively and conservatively evaluate the impact of removing the aforementioned two restrictions on the complexities of known attacks, and thus find a new balance among bandwidth, efficiency, and security for HQC. In detail, we first formalize the best-known decryption-failure attack against HQC, and derive an upper bound on the probability that an adversary triggers a decryption-failure event under realistic query and time limits, enabling an attack-aware upper bound on the secure DFR. Second, we quantify how the weight distribution of $(\mathbf{r}_1, \mathbf{r}_2, \mathbf{e})$ (the random low-weight polynomials used in encryption) affects the concrete cost of ISD attacks and DFR. This yields an \emph{unbalanced} weight strategy that strictly lowers the DFR without sacrificing the targeted bit security, leading to a new variant called \emph{Unbalanced HQC (UHQC)}. By combining these analyses, we provide optimized parameters for UHQC. Across all NIST security levels, UHQC reduces bandwidth by 10-12% and improves runtime by 6-8%.

Large-size Number Theoretic Transforms (NTTs) are key operations in modern Zero-Knowledge Proofs (ZKPs), where the NTT size often reaches millions of points and the arithmetic is over wide prime fields. To handle such NTTs on hardware, prior designs commonly rely on the decomposition algorithm, which makes large-size NTTs feasible by streaming sub-NTTs through limited on-chip buffers. However, in practical implementations, decomposition alone is insufficient to ensure high efficiency. Since coefficients and twiddle factors remain off-chip, performance tends to depend on data movement across the memory hierarchy and delivery to the processing elements (PEs). To address these remaining issues, we present RENTT, a resource-efficient accelerator for large-size NTTs with decomposition-oriented data movement schemes and memory hierarchy design.

First, we design a precomputation-based twiddle factor management scheme that feeds multiple PEs without conflicts, both reducing on-chip twiddle factor storage and avoiding on-the-fly twiddle factor generation. Second, we develop a burst-optimized transpose method that fuses coefficient reordering into the element-wise twiddle-multiplication pass, reducing the latency of off-chip accesses for the subsequent NTTs. Third, we design a decoupled, multi-banked on-chip memory hierarchy that sustains high PE utilization under off-chip streaming, while remaining configurable across PE counts and maximum supported NTT sizes. We implement RENTT on an FPGA and experimentally verify that RENTT supports NTT sizes up to $N=2^{28}$ over 256-bit fields and completes a $2^{28}$-point NTT in 1.52 seconds with 16 processing elements. Compared with the state-of-the-art FPGA baseline SAM, RENTT provides $2.64\times$ speedup (1.52s vs. 4.02s), reduces 46.4% DSP usage (3629 vs. 6776 DSPs), and achieves a $3.58\times$ lower area-time product.

In this work, we propose novel security notions for encryption schemes that simulate an adversary in the black-box model equipped with additional side-channel power. More concretely, the adversary is allowed to probe values of the secret-key sensitive algorithms, i.e. key generation and decryption. We then prove a generalization of the well-known Naor-Yung (NY) transform, generically lifting IND-CPA secure encryption schemes to IND-CCA ones in this new probing context. Moreover, we instantiate the resulting framework from lattices, constructing Rutile, a masking-friendly IND-CPA encryption scheme inspired by Kyber, and then Topaz its IND-CCA secure extension. In our proposal, the masking-unfriendly parts of Kyber, namely the central binomial distributions and the FO-transform, are replaced by masking-friendly counterparts (sum of uniforms and the aforementioned NY-transform).

A useful linearization technique (or a trick) was introduced in the Marlin and Plonk SNARKs, which significantly reduces the number of KZG polynomial commitment openings a SNARK prover has to send. Subsequently, many other KZG-based protocols have taken advantage of it.

We revisit and formalize this technique: – We define a Linearization Polynomial Commitment Scheme (LPCS) that abstracts their linearization technique. – We formalize LinKZG, a LPCS version of the KZG commitment scheme, and show that it achieves a weak form of extractability under a target group version of the ARSDH assumption. We show that Plonk is secure under the same assumption in the ROM. – We show how to construct LPCSs from any homomorphic polynomial commitment scheme. Thus, enabling the linearization technique also for those polynomial commitment schemes, and potentially improving the efficiency of many other SNARKs.

Distributed key generation (DKG) protocols enable a set of parties to distributively generate a threshold-shared key pair \((\mathsf{pk}, \mathsf{sk})\), such that at least \(t\) parties must participate to reconstruct the secret. We introduce the first DKG protocol for discrete-logarithm based keys that are both universally composable and adaptively secure without erasure, inconsistent players, interactive assumptions, or oracle-aided simulation.

Our contributions are as follows: (1) an adaptively secure and universally composable DKG that achieves guaranteed output delivery in three rounds assuming an honest majority, (2) an adaptively secure and universally composable committed DKG that realizes our novel committed DKG functionality, tolerates a full corruption threshold, and achieves identifiable abort in two rounds, (3) an adaptively secure and universally composable committed DKG that achieves guaranteed output in three rounds assuming an honest majority, (4) as an application, an incredibly simple threshold Schnorr protocol in the committed DKG-hybrid model--implying an adaptively secure and universally composable threshold Schnorr protocol tolerating a full corruption threshold with identifiable abort in three rounds, and an adaptively secure and universally composable threshold Schnorr protocol for an honest majority with guaranteed output in four rounds.

Most importantly, our DKG constructions are secure in the random oracle model under the DDH assumption. Our output guarantees are proven under the assumption of synchrony. All existing synchronous DKG protocols for discrete-logarithm based keys satisfy weaker security notions or require stronger assumptions.

We propose Libra, a compiler framework that automates efficient code generation for cross-scheme fully homomorphic encryption (FHE) on highly parallel computing architectures. While it is known that leveraging multiple FHE schemes in a single application can improve the overall efficiency, the exact mapping of cross-scheme FHE operators onto high-performance architectures, such as general-purpose graphic processing units (GPGPUs), remains challenging. To address such challenge, Libra integrates both the FHE computational patterns and hardware-aware scheduling strategies to establish an algorithm-hardware co-optimization framework. Specifically, Libra defines a novel cross-scheme representation for FHE that abstracts common program patterns for each of the FHE schemes. Then, we dynamically optimize the output FHE program based on the combined execution costs of FHE primitives derived from multiple scheme switching patterns. Next, to accelerate inter-operator execution on GPUs, Libra introduces a computational scheduling strategy that bridges high-level computation characteristics with low-level execution plans. Through the proposed pattern-scheduling co-optimization process, Libra generates efficient codes for cross-scheme high-precision FHE computations on GPGPUs. Experiment results show that Libra achieves up to 270$\times$ speedup on microbenchmarks and 19$\times$ on the applications compared to state-of-the-art cross-scheme, while improving compute unit and memory bandwidth utilization by $44\%$ and $36.1\%$.

Most prior works on secure Multi-Party Computation (MPC) in asynchronous networks study Guaranteed Output Delivery (GOD), meaning that all parties learn the function output. Asynchronous MPC protocols with GOD necessarily tolerate only t < n/3 corruptions, and they necessarily allow the adversary to exclude the inputs of up to t honest parties from the computation, a phenomenon referred to as input loss. Seeking improvements to threshold/input loss, we consider weakening GOD to security with abort, a standard notion studied in the context of synchronous networks. Unfortunately we show that, when these standard notions are applied in asynchrony, it is not possible to improve the corruption threshold or the input loss.

We therefore study relaxations of these standard notions under which protocols can be improved. In particular, we propose a relaxation of the standard notion of correctness for asynchronous MPC protocols. Our relaxed notion requires only that parties obtain the correct output when all parties are honest and when at most a threshold A of the parties are asynchronous. We present several impossibility and feasibility results that completely characterize what is possible in the context of our relaxed correctness. For instance, it is possible to achieve selective abort even when t < n parties are corrupt if (and only if) A < (n-t)/2, but it is impossible to achieve unanimous abort unless t < n/3, even when A=0. We additionally propose a new notion of identifiable abort for asynchronous networks (aIA), and we show that we can achieve fair MPC with aIA and min(A,t) input loss.

We describe a Las Vegas algorithm for the principal ideal problem in matrix rings $M_g(O)$ for $g \geq 2$, over maximal orders $O$ in the rational quaternion algebra $B_{p, \infty}$ ramified at $\infty$ and a prime number $p$. Under plausible heuristic assumptions, the method has expected polynomial runtime. An implementation in SageMath shows that it runs very efficiently in practice, with compact output. Our main auxiliary result is a method for finding endomorphisms of superspecial abelian varieties (i.e., powers of supersingular elliptic curves) with a prescribed kernel.

Instant messaging services are an integral part of today's communication and their privacy has wide societal implications. Major messengers deploy end-to-end encryption, hiding message contents from the service provider. Group messaging, however, creates the challenge of also keeping the group membership list private.

The Signal messenger currently implements private group management using techniques inspired by Chase, Perrin, and Zaverucha (CCS 2020). Transitioning this system to quantum-safe turns out to be challenging: While one-to-one messaging can often adopt the newly standardized KEMs and signatures in a relatively direct way, private group management is more complex. Signal’s existing design heavily relies on the discrete-log structure to combine anonymous credentials, verifiable encryption, and oblivious PRFs for privacy and functionality. Quantum-safe versions of these components are unfortunately, typically far less efficient, requiring heavy zero-knowledge proofs and large communication per group operation. As a result, simply "swapping in" quantum-safe primitives is unlikely to yield an optimal protocol.

This paper reconsiders the design of the entire group system from the ground-up. Our result is a scheme that possesses the same strong privacy guarantees, but is built in a more modular way using simpler underlying cryptographic building blocks that permit a more efficient quantum-safe instantiation. The modularity of our protocol further allows for gradual migration to quantum-safe: we can immediately transition components vulnerable to harvest-now-decrypt-later attacks (such as classical public-key encryption, computationally hiding commitments, etc.) while deferring the transition of other building blocks, such as authentication. We prove our design secure in an extended security model that more comprehensively captures the rich feature set of Signal's group messaging system.

In a seminal paper at Eurocrypt'25, B. Libert solved the long-standing open question of the CCA1 security of the Damgard-ElGamal scheme under standard assumptions. That paper also further showed that several other schemes, including a variant of Paillier-ElGamal with plaintext zero-padding, are CCA1 secure under falsifiable assumptions. However, all these schemes are only somewhat linearly homomorphic. In this paper, we first tackle the fundamental question of designing efficient "truly" linearly homomorphic encryption schemes achieving CCA1 security under standard and falsifiable assumptions. We generalize Libert's approach to a large class of group-based PKE, that covers the aforementioned schemes, the Cramer-Shoup Lite scheme as well as new ones. In particular, we use our framework to show that a new variant of Paillier-ElGamal, which we call Damgard-Paillier-ElGamal (DPEG) as its design follows a Knowledge-of-Exponent pattern, achieves CCA1 security solely under the standard DCR assumption. To the best of our knowledge, DPEG is the first "truly" linearly homomorphic encryption scheme that is proven CCA1 secure under a standard assumption. Furthermore, DPEG can be extended to support one level of multiplication while still preserving its CCA1 security under the same assumption. Second, we show that DPEG also achieves Manulis&Nguyen's stronger notion of vCCA security under a non-falsifiable linear-only homomorphism assumption. We then connect vCCA security to a no-go Theorem of Gentry&Wichs and show that, under mild assumptions, vCCA security cannot be established from any falsifiable assumption. This explains why all currently known vCCA secure constructions, including ours, rely on non-falsifiable assumptions.

Oblivious algorithms allow a space-constrained client program to securely outsource storage to an untrusted server. Any program can be compiled to an oblivious form via Oblivious RAM (ORAM), but this is asymptotically and concretely expensive. Recent work (Appan et al., CCS’24) proposed a weakening of ORAM called the Oblivious Single Access Machine (OSAM) model, which offers asymptotically-improved oblivious compilation for many programs, including those that manipulate graph data structures. While of theoretical interest, OSAM graph algorithms were worse than generic ORAM, even for large graphs (tested on graphs of size up to $2^{24}$).

This work improves the concrete costs of OSAM-based oblivious algorithms. In short, the original work on OSAM proposed algorithms for manipulating objects with pointers to other objects. Pointers and objects can be naturally used to instantiate arbitrary graphs, but the OSAM’s underlying management of pointers involves non-trivial and concretely-expensive algorithms. Our work greatly simplifies and improves the efficiency of OSAM-based pointer handling by co-designing (1) pointer-friendly modifications to the underlying Path ORAM algorithm (Stefanov et al., CCS’13) and (2) new algorithms for managing pointers.

We implemented the original OSAM algorithms and our approach. Naturally-written graph algorithms can now be automatically compiled to an oblivious form while enjoying up to a $4$× improvement in performance as compared to when using generic Path ORAM (and at least $8$× as compared to the original OSAM). In sum, our work provides generic and easy-to-use oblivious tools while concretely improving over prior generic state-of-the-art tools.

A new paradigm, called \emph{discrete}-CKKS, proposes to restrict the plaintext space of the homomorphic encryption CKKS scheme from $\mathbb{C}$ to a discrete subset of it (e.g., $\{0, 1\}$). While sacrificing approximate computations, this allows one to express an arithmetic similar to that available in exact schemes, but with significantly larger parallelism and flexibility due to SIMD computations and the underlying complex arithmetic, which remains available internally. A significant example is the recent work by Boneh and Kim (Crypto '25), where they present a method to operate on extremely large encrypted integers.

In this work, we build a simple computational device that handles integers, decomposed as binary vectors, by evaluating standard mod 2 arithmetic operations using polynomials only. Since we do not resort to the modular reductions based on the functional bootstrapping proposed by Kim and Noh (CIC '25), this yields a more flexible parameterization, consistent with standard CKKS configurations, e.g., leveled supporting roughly 13 multiplicative levels before bootstrapping. This means that one can use CKKS in $\mathbb{R}$ and then switch to $\mathbb{Z}$ with the same set of parameters -- we will refer to this as \emph{domain-switching}. Experiments show that our solution has lower latency on all operations (i.e., additions, multiplications, comparisons and logical shifts) by roughly three times, with respect to the current state of the art, although we have smaller throughput due to how data is represented.

We present two constructions of short signature schemes based on the polynomial hardness decisional Diffie Hellman. Our simplest scheme guarantees selective security (i.e. the adversary has to commit to the forged message ahead of time) while the second one realizes full fledged existential unforgeability. Remarkably, our schemes can be implemented over standard prime order groups (no pairings needed) and can be proven secure without resorting to the random oracle heuristic.

Polynomials are a fundamental mathematical object underlying virtually all of theoretical computer science. In proof systems, a common task for the verifier is to evaluate a polynomial of degree $d$ at $m$ distinct points. The best known algorithm for this problem performs $O((m + d) \cdot \log^2(m + d))$ field operations.

We present a concretely efficient $\mathsf{MA}$ protocol for this problem in which the verifier runs in \emph{linear time}: the prover sends a single message consisting of $d - 1$ field elements, and the verifier performs only $O(m + d)$ field operations. We further extend our protocol to handle the more general setting of evaluating multiple polynomials at multiple points, and for this problem, we construct an $\mathsf{AMA}$ protocol.

Our protocols improve the verifier time in several interactive proofs. Most notably are the sumcheck protocol over a large summation domain and protocols that rely on polynomial quotienting. In particular, by a straightforward application of our results, we reduce the verifier's runtime in the STIR protocol (CRYPTO 2024) to match that of WHIR (EUROCRYPT 2025), despite WHIR being highly optimized for verification time.

As an additional application, we show that any univariate polynomial commitment schemes (PCS) can be transformed, in a black-box manner, into a new scheme that efficiently supports batch openings at multiple points. In particular, opening $m$ points incurs only a constant overhead compared to opening a single point.