International Association
for Cryptologic Research

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.

Despite improvements to authentication mechanisms, account compromise remains frequent and users need a trustworthy way to determine what devices have accessed their accounts. Doing so, however, is in tension with privacy goals on the modern web, which mandate that web services not learn static device identifiers. Recent work aims to address this tension via client-side encrypted access logging (CSAL), but their approach does not allow retrieving all log entries and users may miss information about adversarial accesses.

We present Trace, a new CSAL system that achieves complete logging while preserving privacy. Trace records verifiable evidence of each authentication in an encrypted log stored by an independent logging service, ensuring that only the user can inspect it. The web service remains unaware of the logging, preserving backward compatibility with existing authentication infrastructures. Unlike prior approaches, Trace simultaneously achieves verifiable device attribution, backward compatibility, and formally-analyzed security against malicious adversaries. Our prototype implementation reaches over 10 K authentications per second on a single core, suggesting it can scale efficiently for large services.

In 2022, Castryck and Decru introduced an attack that broke several isogeny-based schemes, including SIKE, which had advanced to the final round of the NIST Post-Quantum Cryptography Standardization Competition. Despite this attack, research on isogeny-based cryptography has continued, primarily due to the compact key sizes offered by these schemes compared to other post-quantum approaches. There are now many isogeny-based schemes that are resistant to the Castryck-Decru attack. These schemes typically involve advanced mathematical structures that may require significant time and effort to study.

In this paper, we provide a structured survey of isogeny-based signature schemes that are resistant to the Castryck-Decru attack, aiming to facilitate an understanding of the current landscape and the most practically relevant schemes in this area. We categorize these signature schemes into two main classes: those based on the CSIDH group action and the SQIsign family. For each class, we discuss their fundamental design principles, security assumptions, and specific constructions. We also compare their performance and compactness. Additionally, we describe one representative scheme from each class that is particularly relevant in practice due to its efficiency or compactness. In conclusion, we compare the performance of the schemes discussed in this work with other post-quantum signature schemes.

Post-quantum cryptography focuses on research of cryptographic primitives, including public key encryption and signatures, that can resist the attacks mounted by an adversary with an access to a quantum computer. An alternative is to employ quantum cryptography to protect communication links by employing principles of quantum physics to protect security of the key exchange. Recently, a group key establishment protocol that combines these approaches in a secure way was presented by Steinwandt and Gonzales Vasco. We have successfully imple- mented and employed this protocol in a prototype application. In this article we describe the overall architecture and specific details of the implementation that can be of interest for scientific community. We conclude with a discussion of specific challenges, options and open problems that can accompany similar imple- mentation task.

Security evaluation of masking in low-noise regimes remains poorly understood: increasing the masking order does not automatically translate into higher concrete resistance once many correlated intermediates are processed by a full implementation. A common approach is to reduce noisy side-channel leakage to the random probing model (RPM), but existing reductions can be too loose to yield meaningful leakage rates in practice, and current RPM analyses often rely on costly simulations or numerically propagated bounds.

This work develops analytic and algorithmic tools for estimating and upper-bounding RPM security of masked gadgets and their compositions. First, for noisy Hamming-weight leakage over $\mathbb{F}_{2^u}$ we compute concrete RPM leakage-rate parameters for a tighter $\mathbb{F}_2$-linear reduction based on binary inner products, providing a tangible link between SNR and probing rate. Second, for $\mathbb{F}_q$-linear circuits we leverage a vector-space representation to characterize RPM leakage as an erasure event, yielding a direct connection to local metrics such as advantage and implying global simulability for refreshed, block-separated executions. Third, we improve Monte Carlo estimation of rare leakage events using importance sampling, enabling evaluation in low-rate/high-order regimes that are infeasible with naive sampling. Finally, we revisit the leakage-diagram technique and derive explicit bounds for refresh gadgets, and we apply the same viewpoint to composition through \emph{bridges}, showing that SNI—while sufficient for threshold probing model (TPM)—does not capture the RPM phenomenon governing refresh boundaries.

We implement our methods in \textsf{LAPSE}, a tool that compiles gadget descriptions into linear-algebraic representations and supports exact computation as well as Monte Carlo/importance-sampling estimation of RPM security parameters.

The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. In this work, we first build a two-round identification protocol whose security reduces to this problem. The challenge consists of a random large prime $q$ and the prover simply replies with an efficient representation of an isogeny of degree $q$ from its public key. Using the hash-and-sign paradigm, we then derive a signature scheme with a very simple and flexible signing procedure and prove its security in the standard model. The most efficient variant of our signature schemes features a signing which is $1.4\times$ to $1.6\times$ faster than the most recent implementaion of SQIsign, whereas verification ranges from $1.2\times$ slower to $1.01\times$ faster depending on the security level. The sizes of public key and signature are comparable to existing schemes.

SMAUG-T and HAETAE, designated as target algorithms for national standardization via the Korean Post-Quantum Cryptography (KpqC) competition, run efficiently on general-purpose platforms. On ARM Cortex-M4 class microcontrollers, however, peak stack usage becomes a key constraint: while SMAUG-T can be executed on typical Cortex-M4 boards, the baseline HAETAE implementation exceeds the available SRAM (e.g., 91{,}176\,B stack for signing), motivating dedicated memory optimization. To address this problem, we propose a suite of memory optimization techniques for SMAUG-T and HAETAE that enable their practical operation within the strict memory budget of the Cortex-M4. Experimental results demonstrate that, compared to the KpqClean\_ver2 baseline, peak stack usage was reduced by 73--83~\% for SMAUG-T5 (e.g., 24{,}300\,B$\rightarrow$4{,}240\,B in decapsulation) and by about 90~\% for HAETAE5 (e.g., 91{,}176\,B$\rightarrow$8{,}092\,B in signing). Furthermore, a branchless constant-time design was applied throughout to ensure that the optimized implementations remain robust against side-channel threats such as timing attacks. This work provides a practical methodology for deploying KpqC lattice-based cryptography in memory-constrained embedded environments.

Private Set Intersection (PSI) allows two mutually distrusting parties to compute the intersection of their private sets without revealing any additional information. Fuzzy PSI, an approximate variant of PSI, allows the receiver to learn points of the sender that are ``close" to its points. More formally, the receiver learns all $y$ in the sender's set that satisfy $dist(x,y)< \delta$ for some element $x$ in the receiver's set and threshold parameter $\delta$. Recently, there has been significant progress on Fuzzy PSI, as it allows us to realize several important applications such as password matching, facial recognition, and contact tracing in a privacy-preserving manner. However, existing Fuzzy PSI constructions make strong assumptions on the input sets, such as receiver set disjointedness or projected disjointedness. In this work, we analyze those strong assumptions from a practical viewpoint and observe a gap between theory and practice, i.e., real-world data sets do not abide to those assumptions. To bridge the gap, we first define a new relaxed and weaker assumption based on the low density of sets, demonstrate the assumption to be practical, and build a compiler that converts constructions under the strong assumption to those under the new, practical assumption. At the core of our transformation is a novel idea involving higher-dimensional lifting and coloring. Combining our transformation with current Fuzzy PSI protocols under the strong assumption yields efficient and practical Fuzzy PSI protocols. We also concretely analyze the run-time and overhead of our transformed protocols for parameters for illustrative applications, such as password matching.