International Association
for Cryptologic Research

We present a simple range-proof mechanism for Pedersen commitments that avoids per- transaction heavy ZK verification and pairings. The idea is to commit once to a Merkleized range table of points {(U, aX·G)}X∈{1,...,2n} for a secret a ∈ Zq and a public anchor U = a·B. At transaction time, a prover shows set membership of the leaf (U, ax · G), proves via a Chaum–Pedersen DLEQ that logB U = logC C′ where C′ = a · C and C is the Pedersen commitment, and finally proves (Schnorr) that C′ − (ax·G) lies in the H-direction. These three checks enforce x to be the in-range value indexed by the Merkle leaf while preserving privacy. Verification costs a single Merkle proof plus a DLEQ and a Schnorr discrete-log proof over an elliptic curve group.

Garbled circuits with one-bit-per-gate communication were recently introduced by Liu et al. (BitGC, Eurocrypt 2025), Meyer et al. (Crypto 2025), and Ishai et al. (Crypto 2025). However, these works focus primarily on the theoretical communication complexity, leaving open questions about practical computational efficiency. In this paper, we present a set of optimizations that substantially improve its practical efficiency. First, we eliminate key barriers to enable SIMD support to BitGC, leading to a substantial speedup in its homomorphic operations. Second, we demonstrate that XOR gates can be garbled without any communication, improving both efficiency and simplicity. Finally, we present a computationally efficient garbling scheme that requires zero communication for XOR gates and only 5 bits per AND gate. When applied to an AES-128 circuit, our fastest garbling scheme generates a garbled circuit of just 4 KB in 3 minutes on a single CPU core.

Secret sharing is a foundational cryptographic primitive for sharing keys in distributed systems. In a classical $(n,t)$-threshold setting, it involves a dealer who has a secret, a set of $n$ users to whom shares of the secret are sent, and a threshold $t$ which is the minimum number of shares required to recover the secret. These schemes offer an \textit{all-or-nothing} security approach where less than $t$ shares reveal no information about the secret. But these guarantees are threatened by side-channel attacks which can leak partial information from each share. Initiated by Benhamouda et. al. (Crypto'18), the security of linear secret sharing schemes has been studied for bounded leakage models, which assume that the adversary can leak bounded functions of each share. However, this model does not translate into real-world attacks, as physical side-channels are inherently noisy. The $\delta$-noisy channel model, proposed by Prouff and Rivain (Eurocrypt’13), is a general leakage framework which captures the noisy behaviour of side-channels. But the security for this model has proven difficult to analyze even for $(n,n)$-threshold schemes. The best known guarantees due to Duc et. al. (Eurocrypt'14), show that the adversary has at most $(\delta \cdot\mathcal{O}(n) \cdot q)^{n}$ advantage compared to guessing blindly, where $\mathbb{F}_q$ is the underlying field. In this work, we study the security of linear secret sharing schemes with $\delta$-noisy leakage, and show bounds on the mutual information (MI) and statistical bias ($\Delta^{\mathrm{TV}}$) security metrics. Our results are based on the Fourier analytical framework, first used by Benhamouda et. al. (Crypto'18), adapted to the $\delta$-noisy model. Informally, for some security parameter $\eta\le \min{\{1,2\delta\}}$, the Poisson's summation formula enables us to bound the ratio between the observed leakage for some given secret, and leakage under independence as $(1\pm \eta^t)$. This is then used to show a) $(n,t \ge \tau (n+1))$-threshold schemes over $\mathbb{F}_q$ have at most $\mathcal{O}(q^{-t(\gamma+1-1/\tau)})$ leakage, given $\eta \le q^{-\gamma}$; and consequently b) for $(n,n)$-threshold schemes the guessing advantage is at most $(q-1) \cdot \eta^n = \mathcal{O}(q^{1/n} \cdot \delta)^n$. Our results for the first time remove the field-size loss in security guarantees for $(n,n)$-threshold schemes. Furthermore, for $(n,t)$-threshold schemes, our results imply that the known security barrier of $t \ge 0.5n$ is an artifact of the bounded leakage model. This work can be viewed as a next step towards closing the gap between theory and practice in leakage resilient cryptography.

Multivariate quadratic problem over a finite field, a NP-hard problem, is also considered as one of the hard problems for cryptanalytic-relevant quantum computers. It is the foundation of multivariate quadratic-based cryptography and several post-quantum digital signature schemes initially proposed in 1990s. Patarin’s unbalanced Oil-and-Vinegar (UOV) scheme is the oldest MQ signature algorithm that remain secure against large-scale cryptanalytic-relevant quantum computers. UOV has compact signature size and succinct verification time. However, it suffers from a very large public key size. Subsequently, UOV-based variants have focused on minimizing the size of central map. MAYO, a candidate advanced to NIST’s round 2 additional post-quantum digital signatures, is based off the UOV algorithm with whipped structure to reduce public key size. In this paper, we present a theoretical framework of the proposed cryptanalysis. It targets the construction of valid signatures during the signing phase. This attack allows efficient extraction of secret oil vectors from the public signatures, facilitating the complete recovery of the entire secret oil space O. Finally, we show that this attack is applicable to parameter sets of all three security level of all versions of MAYO.

Traceable Ring Signatures (TRS) were introduced by Fujisaki and Suzuki~[PKC'07], where a trace algorithm can publicly check if two signatures with the same event label were generated by the same signer (linkability). In addition, if the two signatures correspond to different messages, then the signer's identity is revealed (traceability). Following [PKC'07], most subsequent works adopt the same definitions and consider three security properties, anonymity, linkability, and exculpability. [PKC'07] proved that the latter two properties together imply unforgeability, a fundamental requirement for all signature-like primitives.

~~~~In this work, we identify a gap in the aforementioned proof, which arises from the insufficient consideration of linkability and exculpability in [PKC'07]. To address this, we revisit the syntax and security notions of TRS, and close this gap by defining extended linkability and extended exculpability. Building on these, we design a new framework of TRS from PseudoRandom Functions (PRF) and Zero-Knowledge Proofs of Knowledge (ZKPoK) that supports $O(1)$ tracing, provided that both two signatures are valid. This constitutes a substantial improvement over existing approaches---all of which require $O(n)$ tracing with $n$ the size of the ring---and elevates TRS to a level of practicality and efficiency comparable to Linkable Ring Signatures (LRS), which have already achieved widespread deployment in practice. Finally, we instantiate our generic framework from the DDH assumption and leverage the Bulletproofs [S\&P'18] to construct a TRS scheme with log-size signatures. The proposed scheme achieves highly optimized signature sizes in practice and remains compatible with most existing DLog-based systems. On Curve25519, the signature size is $(128 \cdot \log n + 736)$ bytes, which to our best knowledge is the shortest LRS scheme for a ring $n \ge 19$.

The protection of executable code in embedded systems requires efficient mechanisms that ensure confidentiality and integrity. Belkheyar et al. recently proposed the Authenticated Code Encryption (ACE) framework, with ChiLow-(32 + $\tau$) as the first instantiation of ACE2 at EUROCRYPT 2025. The design of ChiLow-(32 + $\tau$) is based on a 32-bit tweakable block cipher with a quadratic nonlinear layer, known as ChiChi (denoted by $\chi\!\!\chi$), and a nested tweak key schedule optimized for secure code execution under strict query limits.

In this work, we study the resistance of ChiLow to integral cryptanalysis. We identify new integral distinguishers in both the single-tweak and related-tweak models. Using these results and a nested strategy to recover all round tweaks, we present a key-recovery attack on 7 out of 8 rounds of ChiLow. The central contribution of our work is that it resolves the challenge of deriving the master key from the recovered round tweaks, an open problem highlighted by the designers and in a recent cryptanalysis by Peng et al. The attack on 7 rounds requires $2^{6.32}$ chosen ciphertexts, has a time complexity of about $2^{121.75}$ encryptions, and requires negligible memory.

Function Secret Sharing (FSS) schemes enable sharing efficiently secret functions. Schemes dedicated to point functions, referred to as Distributed Point Functions (DPFs), are the center of FSS literature thanks to their numerous applications including private information retrieval, anonymous communications, and machine learning. While two-party DPFs benefit from schemes with logarithmic key sizes, multi-party DPFs have seen limited advancements: $O(\sqrt{N})$ key sizes (with $N$, the function domain size) and/or exponential factors in the key size.

We propose a DDH-based technique reducing the key size of existing multi-party schemes. In particular, we build an honest-majority DPF with $O(\sqrt[3]{N})$ key size. Our benchmark highlights key sizes up to $10\times$ smaller (on realistic problem sizes) than state-of-the-art schemes. Finally, we extend our technique to schemes supporting comparison functions.

Multi-key fully homomorphic encryption (MK-FHE) enables secure computation over ciphertexts under different keys, but its practicality is hindered by inefficient bootstrapping.In this work, we propose HELIOS, a new MK-FHE scheme with highly efficient bootstrapping. Our bootstrapping framework improves upon the best-known complexity, reducing it from ${O}(dkn)$ to ${O}(kn)$, and further to ${O}(\sqrt{kn})$ under parallelization, where $d$ is the gadget length (typically scaling with the number of parties $k$) and $n$ is the LWE dimension.The framework consists of two main components: (i) a ciphertext conversion algorithm that transforms a multi-key LWE ciphertext into $k$ vectorized RLWE ciphertexts via $k$ optimized blind rotations and $dk$ key-switching operations, and (ii) a hybrid accumulator that aggregates these into a single multi-key RLWE ciphertext. We implemented HELIOS on both CPU and GPU platforms to demonstrate its practicality. For $k=16$, we achieve $3.3\times$ and $7.2\times$ improvements on CPU, compared to the state-of-the-art schemes by Kwak et al. (PKC 2024) and by Xiang et al. (ASIACRYPT 2024), respectively. We further achieve a $195\times$ GPU acceleration, compared to our CPU runtime. As a byproduct, we design a new distributed-decryption protocol, which allows us to obtain a ciphertext with a small noise bound, and thus does not blow up the parameters.

Homomorphic secret sharing (HSS) is a powerful cryptographic primitive that enables efficient, low-communication secure computation without the use of fully homomorphic encryption. Public-key HSS is a well-known variant that supports inputs from multiple parties, but all parties must agree on a joint public key before any party can encode their inputs, requiring extra rounds of communication in applications. Recently, Couteau et al. (EUROCRYPT 2025) constructed multi-key HSS (MKHSS)—a new primitive which allows parties to encode their inputs under independent keys—under the DCR assumption. MKHSS assumes only a reusable common reference string, without the need for prior interactions between parties or a public-key infrastructure.

In this paper, we construct and implement the first concretely-efficient MKHSS scheme under the same assumptions used by Couteau et al. Using an algorithmic insight that reduces the largest modulus in Couteau et al. from $N^4$ to $N^2$, our optimized implementation can homomorphically multiply inputs in 5.0 milliseconds—while an implementation of Couteau et al. requires 224.6 milliseconds—thereby achieving a $45\times$ speedup.

A powerful application of MKHSS is to realize attribute-based non-interactive key exchange (ANIKE), which generalizes password-authenticated key exchange (PAKE) to arbitrary attribute policies. ANIKE is currently only known from MKHSS and in this paper we show the first practical instantiation of ANIKE for two concrete predicate types with applications to geolocation-based key exchange and fuzzy PAKE.

We use our implementation to evaluate the first concretely-efficient ANIKE schemes for a range of practically useful policies. Using our implementation, two parties can perform a geolocation-based key exchange in under one second and a fuzzy PAKE on an 8-word passphrase in a few seconds for realistic parameters, on a single core, achieving a roughly $30 \times$ speedup over Couteau et al. for both applications.

We present Zyga, a pairing-based zero-knowledge proof system optimized for privacy-preserving DeFi applications. Our main contribution is an enhancement of existing zkSNARK constructions that enables dynamic public input substitution during verification while maintaining privacy of witness components through one-sided encoding. The one-sided encoding aspect favors practical deployment constraints on Solana where G2 scalar multiplications are computationally expensive. Zyga separates private values (blinded through trusted setup) from public values (instantiated on-chain), enabling applications like private trading against current market rates without reproofing. We provide rigorous security analysis under discrete logarithm and q-Strong Diffie-Hellman assumptions, demonstrating computational soundness, zero-knowledge, and completeness. Performance analysis shows verification requires only 3 pairings with constant proof size, making it practical for blockchain deployment where transaction costs are critical.

In this paper, we propose a quantum circuit implementation of AIM2. We apply optimization to reduce the circuit depth and introduce a method to reuse qubits by performing inverse operations in parallel. For all AIM2 variants (AIM2-I, AIM2-III, AIM2-V), we design quantum circuits for $\mathsf{Mer}^{-1}$, the linear layer, $\mathsf{Mer}$, and feed-forward. We confirm that the $\mathsf{Mer}^{-1}$ operation dominates the overall cost. Compared to the previous version of AIM, AIM2 requires significantly more quantum resources since it introduces $\mathsf{Mer}^{-1}$ before the linear layer. Based on the proposed circuits, we estimate the cost of Grover's algorithm for key search and compare it with the NIST estimates for AES. As a result, AIM2-I, AIM2-III, and AIM2-V achieve the post-quantum security levels of Level-1, Level-3, and Level-5, respectively.

We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity. In concrete terms, the following result holds for each of the function families that we propose. Given integers $m_0\geq 0$, $x_0\geq 1$, and $a_0\geq 1$, it is possible to construct an $n$-variable function which has resiliency at least $m_0$, linear bias (which is an equivalent method of expressing nonlinearity) at most $2^{-x_0}$ and algebraic immunity at least $a_0$; further, $n$ is linear in $m_0$, $x_0$ and $a_0$, and the function can be implemented using $O(n)$ gates.

Secure storage of private keys is a challenge. Seed phrases were introduced in 2013 to allow wallet owners to remember a secret without storing it electronically or writing it down. Still, very few people can remember even 12 random words. This paper proposes an alternative recovery option that utilizes lower-than-standard entropy secrets (such as passwords, biometrics, and object extractors). It can be used on its own (in combination with strong key derivation functions) or provide an additional backup option for the existing mnemonics. In this work, we investigate several aspects of secure key derivation: (1) how much entropy different sources can provide; (2) what is the preferred construction of the fuzzy extractor; (3) our key contributions in the selected approach; (4) the main security assumptions and properties of Unforgettable Fuzzy Extractor; (5) economic rationale for parameters (e.g., fuzzy vault size, additional PoW difficulty, secret length, cost of the attack) achieving the optimal solution from both security and time perspectives.

Blind signatures are a versatile cryptographic primitive with many applications, especially in privacy-preserving technologies. Threshold blind signature schemes (TBS) enhance blind signatures with a signing procedure distributed among up to n signers to reduce the risk attached to the compromise of the secret key.

Blind signatures and TBS in pairing-free groups often rely on strong assumptions, e.g., the algebraic group model (AGM) or interactive assumptions. A recent line of work initiated by Chairattana-apirom, Tessaro and Zhu (Crypto'24), hereafter CTZ, manages to construct blind signatures in pairing-free groups in the random oracle model (ROM) without resorting to the AGM. While CTZ gives a construction from CDH, the scheme suffers from large signatures. Recent works have improved the efficiency, however at the cost of relying on a decisional assumption, namely DDH. In this work, we close this gap by giving an efficient blind signature in pairing-free groups proven secure under CDH in the ROM. Our signatures are of size 320 Byte which is an 32× improvement over CTZ’s CDH-based construction. Further, we give the first TBS in pairing-free groups that does not rely on the AGM by thresholdizing our blind signature. Likewise, our TBS is proven secure under CDH in the ROM.

To achieve this, our starting point is the efficient scheme introduced by Klooß, Reichle and Wagner (Asiacrypt'24). We manage to avoid the DDH assumption in the security argument by carefully hiding critical information from the user during the signing phase. At the cost of only 3 additional Zp elements in signature size, this allows us to prove security under CDH.

In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the $S$-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, $S$-class groups, relative class group and unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.

Fuzzy PSI is a variant of PSI, which on input a set of points from the receiver and sender respectively, allows the receiver to learn which of the sender's points lie within a threshold distance $\delta$ under a specific distance metric.

Baarsen and Pu (EUROCRYPT'24) first proposed efficient fuzzy PSI protocols for general $L_{p}$ distances (where $p \in [1, \infty]$) in $d$-dimensional space, achieving communication complexity linear in the input size, $\delta$, and $2^d d$. However, they leave open the question of whether the prefix technique of Chakraborti et al. (USENIX Security'23) can further reduce the communication complexity of their fuzzy PSI protocols in both low and high dimensions.

In this work, we thoroughly explore using the prefix technique to reduce the complexity of fuzzy PSI. First, we propose fuzzy matching protocols for $L_{\infty}$ and $L_p$ distances, where the communication complexity is improved from $O(\delta d)$ to $O(\log\delta\, d)$ for $L_\infty$, and from $O(\delta^p)$ to $O((\log \delta)^d p)$ for $L_p$ distance. By applying our fuzzy matching protocol in conjunction with spatial hashing, we propose fuzzy PSI protocols for low-dimensional space. For high-dimensional space, we present the first fuzzy PSI protocols achieving communication and computation complexity that scales logarithmically in $\delta$ and linearly in dimension $d$ and input set sizes.

We implement our fuzzy PSI protocols and compare them with state-of-the-art protocols. Experimental results demonstrate that our protocols achieve superior performance for large $\delta$: for input size $N=2^8$, $d=5$, and $\delta=256$, our protocol requires $10$--$36\times$ less running time and $3$--$4.5\times$ lower communication than existing protocols.

In anonymous token protocols, clients obtain access tokens by proving eligibility for the usage of a resource and later get access to the resource by redeeming the token. The server verifying eligibility and providing the resource cannot link the token issuance to its redemption. To prevent ineligible clients from accessing resources, it is crucial to prevent the transfer or sale of tokens. Durak et al. (CCS'24) propose binding tokens to valuable insurance secrets, which must be known to redeem the tokens. The value of the insurance secret deters the vendor from transferring the secret to the token buyer, who cannot redeem the token without the secret. However, the authors do not consider scenarios, where the token vendor assists the buyer during token redemption. Their construction, therefore, falls short to guarantee non-transferability when facing a vendor-aided token redemption.

We address this gap by introducing the concept of anonymous tokens with betrayability. Our notion ensures that a token buyer, that is able to redeem a bought token, either knows the insurance secret or is able to betray the vendor in a vendor-aided redemption. The betrayal allows the buyer to steal the insurance secret without being detected. This way, we make the support in the token redemption equivalent to a transfer of the insurance secret and, hence, inherit the transfer deterrence of the insurance secret even when considering a vendor-aided token redemption. We formalize our new security notion, present a protocol for anonymous tokens with betrayability, prove its security, and provide an implementation and experimental evaluation.

Finding shortest paths in graphs is one of the fundamental combinatorial optimization problems with numerous applications. Privacy constraints in these applications have lead to an extensive line of research on the so-called privacy-preserving (length of) shortest path problem. A Secure Multi-Party Computation (SMPC) protocol that solves this problem computes the lengths of shortest paths on a secret graph in a distributed fashion while ensuring that the graph remains secret. While many such protocols have been proposed in the past, they only compute the length of the shortest paths and not the paths themselves.

In this paper, we address this shortcoming but also propose a novel adaptable protocol design that chooses between different sub-protocols for the building blocks it uses depending on input size, the network delay and bandwidth, and the security model the protocol operates in. Our protocol thus finds the run-time optimal combination of sub-protocols for a given environment. We compare the resulting adaptive protocol to a less flexible baseline protocol in an extensive evaluation using the MP-SPDZ framework, spanning multiple network and security settings. Compared to the baseline protocol, the adaptivity of our optimized path construction leads to speedups from 4% to 32% in the overall time to find the shortest path.

Further, we find and fix a small leakage in two prior (length of) shortest path protocols, and report multiple observations that can be used to improve the practical runtime of other SMPC protocols.

We give a formal analysis of the optimized variant of the $\mathsf{gemini}$ polynomial commitment scheme [BCHO22] used by the $\href{https://github.com/AztecProtocol/aztec-packages}{\text{Aztec Network}}$. Our work is motivated by an attack on a previous implementation [GL25].

The rapid advancement of quantum computing threatens the security of widely deployed public-key cryptosystems, creating an urgent need for practical migration to post-quantum cryptographic (PQC) standards. Although the U.S. National Institute of Standards and Technology (NIST) and Korea’s KpqC initiative have recently standardized PQC algorithms, integrating them into Transport Layer Security (TLS)~1.3 remains operationally challenging. Larger certificates, higher handshake costs, and incompatibility with legacy clients make naive deployment impractical in production environments. While hot reload has long been supported in classical TLS deployments (e.g., Nginx, HAProxy), these mechanisms were designed for RSA/ECC contexts with small keys and certificates, and they do not address PQC-specific challenges.

This work presents a systematic demonstration of \emph{hot reload and rollback in a PQC-enabled TLS context}, incorporating a policy-driven state machine for staged migration and rollback under realistic constraints such as increased handshake latency and legacy-client compatibility. We propose a bridge-server-based framework that operates at the TLS library level, enabling zero-downtime migration across classical, hybrid, and PQC deployments. Experimental evaluation shows that PQC handshakes incur a $\approx$5.8--6.4$\times$ increase in latency in compute-bound settings relative to ECC baselines, while the relative overhead is significantly smaller in network-bound scenarios, highlighting the importance of deployment context. These findings provide a feasible path toward secure and incremental PQC integration in TLS infrastructures, contributing to broader strategies for achieving crypto-agility under evolving cryptographic standards.