International Association
for Cryptologic Research

We propose a new fuzzy private set intersection (FPSI) protocol, a two-party functionality that securely identifies similar items across private sets. Our design departs from the prevailing separation-based paradigm in existing constructions. Rather than enforcing common separation-based assumptions, e.g., ``apart by $2\delta$'' or disjoint projection assumptions, we adopt a fundamentally different perspective: we explicitly allow collisions within $\delta$-balls, but require that their multiplicity be bounded per axis. We formalize this by introducing a new structural assumption called \textit{$k$-max collision}, which upper-bounds the number of items intersecting any $\delta$-ball along each axis by a parameter $k$. This new assumption intrinsically reflects the axis-wise distinctness of the data through density, rather than pairwise separability. Following prior analyses of disjoint projection assumptions, we show the plausibility of $k$-max collision by proving that uniformly distributed data satisfies this property. Under the $k$-max collision assumption, we propose an FPSI protocol with computation/communication complexities scaling linearly with both parties' set sizes and the data dimension for a fixed $k$. Our results demonstrate that separation assumptions are not necessary for efficient FPSI. Notably, our construction accommodates the intermediate-dimension regime ($1\ll d \ll \kappa$ for the data dimension $d$ and the statistical security parameter $\kappa$), which has remained neither efficiently supported nor well-justified under existing separation-based FPSI paradigms.

We give the first $\mathsf{NC}^1$-computable Pseudorandom Function (PRF) constructions from well-founded (non-ad-hoc) code-based assumptions. Specifically, we give two constructions based on two different classical variants of the learning parity with noise (LPN) assumption: (1) An $\mathsf{NC}^1$-computable PRF from hardness of Sparse-LPN [Alekhnovich, FOCS~'03] (with respect to a sublinear-depth explicit expander graph family). This PRF is also key-homomorphic. (2) An $\mathsf{NC}^1$-computable PRF from hardness of Ring-LPN [Heyse et al., FSE~'12].

Both of these assumptions have been used and studied for many years. Notably, within the range of parameters that we need, none of these assumptions is known to imply collision-resistant hashing, and the first is not known to imply public-key encryption. Prior constructions of code-based PRFs (let alone key-homomorphic) are either super-logarithmic depth, or rely on ad-hoc and new assumptions. As a bonus, we give a similar result relying on the \emph{classical} LPN assumption, albeit with quasi-polynomial hardness: -A key-homomorphic $\mathsf{NC}^1$-computable PRF from quasi-polynomial hardness of classical LPN [Blum et al., CRYPTO~'93].

Technically, all of our results are obtained via a refinement and substantial extension of the recent ideas of [Ding, Jain, and Komargodski, STOC~'25].

This paper investigates the algebraic structure of SNOVA, a NIST PQC Round 2 candidate, with a specific focus on the kernel dimension of the wedge map. We employ lifting techniques to transform the public key from the matrix ring $\mathbb{F}_q^{l \times l}$ to an equivalent representation over the extension field $\mathbb{F}_{q^l}$, establishing that the rank of the wedge map is a structural invariant. A key contribution of this work is the derivation of a generating function that explicitly characterizes the wedge map's kernel dimension. This algebraic analysis provides a rigorous understanding of SNOVA's geometry, verifying the safety of specific parameter sets and enabling future refined adjustments to guarantee structural security.

As crypto-assets become increasingly integrated into global financial systems, they are now employed to demonstrate solvency, establish creditworthiness, and satisfy wealth verification requirements for various financial and regulatory purposes. A fundamental challenge in these applications is proving that a given wallet address is controlled exclusively by a single legal entity, as fraudulent multiple claims can undermine the integrity of asset-based verification systems.

In this paper, we propose a binding of wallet address to legal identity that makes conflicting claims cryptographically inconsistent. In the main design, claimants post to a public, privacy-preserving bulletin board a zkSNARK that proves knowledge of both the private key and the address–identity binding without revealing either; proofs are structured so that duplicate claims for the same address are publicly detectable. When a shared bulletin board is not available, we introduce a self-deterrence proof: a zero-knowledge protocol in which producing two valid proofs for the same address under different legal identities would enable efficient extraction of the private key, creating a strong economic disincentive against double claiming. These cryptographic primitives provide effective countermeasures against blockchain stacking fraud attacks and enhance the reliability of crypto-assets in traditional financial applications, contributing to the broader integration of digital assets into established economic systems.

Polynomial commitment schemes (PCS) are a fundamental building block of modern zkSNARKs. In this paper, we propose Lightning, a new coding-based PCS that achieves state-of-the-art prover efficiency. Our main technical contribution is a new linear code family, the Lightning code, which can be instantiated from any base code with constant relative distance. Compared to the base code, Lightning code significantly reduces encoding cost by trading off relative distance. We integrate Lightning code into the standard coding-based PCS framework of Ligero and Brakedown. Experimental results show that Lightning PCS reduces prover commitment time by up to $2.7\times$ compared to the fastest prover configuration of Brakedown, at the cost of a $2.4\times$ increase in proof size. Overall, Lightning provides a practical mechanism for trading proof size for prover efficiency in coding-based PCS constructions.

We revisit the question of minimizing the overhead of security against malicious parties in dishonest-majority secure computation.

A leading approach, pioneered by the SPDZ line of protocols, uses homomorphic MACs to authenticate computation: Parties effectively compute a MAC on the computation output using authenticated multiplication triples (AMT). However, securely generating these AMTs presently sits as the cost bottleneck.

In this work, we introduce a new technique for enabling SPDZ-style verification via homomorphic MACs, while bypassing the need for AMT. We instead rely on the specific structure of state-of-the-art fast pseudorandom correlation generators (PCG) for generating standard (unauthenticated) multiplication triples (MT). Parties authenticate the computation result via an authenticated variant of private information retrieval (PIR), relying on the sparse representation of MT produced by these PCGs.

This opens the door to a wide range of PIR optimizations and tradeoffs from the literature, resulting in asymptotic and concrete improvements over the traditional AMT-based approach. For example, in the Boolean 2-party case with \(\sigma=40\), we get a \(3\times\) to \(8\times\) computation improvement (and comparable communication) over best approaches using PCG to generate AMT, where the latter exploits variants of the Stationary Syndrome Decoding assumption of Kolesnikov et al. (Crypto 2025). With \(m\ge 3\) parties we obtain even larger improvements while reducing the asymptotic dependence on \(m\) from cubic to quadratic.

Quantum computing threatens widely deployed public-key cryptosystems, driving the urgent adoption of post-quantum cryptography (PQC) in cloud and hardware-accelerated security infrastructures. This paper presents Adams Bridge, an industry-grade hardware accelerator for lattice-based PQC that integrates ML-KEM and ML-DSA within a unified architecture to maximize hardware reuse and silicon efficiency. The design features a staged, pipelined datapath that exploits multi-level parallelism to accelerate polynomial operations shared by both schemes. An optimized NTT/INTT and point-wise multiplication engine is tightly coupled with a high-throughput Keccak core and efficient hardware sampling, reducing memory overhead and eliminating pipeline stalls.

Synthesized in 5 nm technology and operating at 600 MHz, Adams Bridge achieves the best reported normalized Area-Time (AT) efficiency among unified designs, offering a 27% AT improvement for ML-DSA compared to state-of-the-art architectures. The three phases of ML-DSA complete in 26, 61, and 31 $\mu$s, respectively, while ML-KEM takes 11, 14, and 20 $\mu$s for its corresponding stages.

To address physical attack vectors, the accelerator embeds hardware-level side-channel countermeasures, including masking, shuffling, and constant-time control and arithmetic, mitigating information leakage without compromising performance. Empirical TVLA evaluation up to one million traces confirms the elimination of first-order leakage in critical datapaths. Targeted for deployment within the open-source Caliptra Root of Trust (RoT), Adams Bridge represents the first open-source PQC accelerator under the Apache 2.0 license designed for real-world hardware security systems.

Compressing correlated randomness is a key component of secure computation protocols in the silent preprocessing model and has received significant attention in recent years. However, to date, all known constructions are restricted to generating additive correlations, where the parties receive additive shares of a relation. The only known exceptions are constructions from indistinguishability obfuscation.

In this work, we initiate the study of compressing useful forms of correlated randomness for non-additive correlations, without resorting to indistinguishability obfuscation (iO). We provide several constructions for pseudorandom correlation generators and functions, overcoming the long-standing "iO-barrier" in the field. Concretely, we focus on two types of non-additive correlations in this work.

First, we introduce pseudorandom permutation functions, where each party obtains a portion of a pseudorandom permutation $\pi$ over the set $\set{1,\dots, n}$, such that no subset of $n-2$ colluding parties learn the full permutation $\pi$. We give a three-party construction of a pseudorandom correlation function (PCF) for permutations from homomorphic secret sharing satisfying a special share programmability property. This construction can be instantiated from a variety of standard assumptions and can even be concretely efficient (generating pseudorandom permutations in a fraction of a second). We describe two applications of pseudorandom permutation functions: one in anonymous broadcast and the other in single secret leader election.

Second, we introduce pseudorandom correlation generators for classical correlations (such as Beaver triples) where additive secret sharing is replaced with threshold} secret sharing. We obtain a pseudorandom correlation function for constant-degree Shamir shares of low-degree correlations from a variety of standard assumptions. We also introduce two new $t$-out-of-$n$ PCG constructions where either $t$ or $n-t$ is a constant and $t$ denotes the threshold. These constructions rely on the conjunction of the LPN and MQ assumptions.

This paper presents improved attacks and proofs for the key committing security of EtE-HCTR2, a robust authenticated encryption scheme constructed from HCTR2 and the Encode-then-Encipher (EtE) framework, in light of the ongoing standardization effort of cryptographic accordions by NIST. We improve attacks on the instantiations with two common encodings, where zeros are either appended or prepended to the message, namely EtE_A-HCTR2 and EtE_P-HCTR2. Compared with the state-of-the-art attack by Chen et al. in ToSC 2023(4), our EtE_A-HCTR2 attack reduces the complexity from $O(2^{\tau/2})$ to $O(2^{\max\{\tau/3, \tau-n\}})$ for an $n$-bit block cipher and $\tau$-bit zero padding, which degrades EtE_A-HCTR2's security below the birthday bound. Meanwhile, our EtE_P-HCTR2 attack reduces the complexity from $O(2^{\min \{n/2, \tau\}})$ to $O(2^{\tau/2})$, which is tight with our new security proof. We verify these computationally-bounded attacks by experimentally generating concrete vectors for both EtE_A-HCTR2 with $\tau=96$ and EtE_P-HCTR2 with $\tau=64$, each instantiated with $n=128$, in less than 15 minutes. We consider yet another padding scheme that appends zeros to the first message block, namely EtE_S-HCTR2, and prove that it has a tight committing security bound of $O(2^{\tau/2})$ by avoiding the issue in EtE_A-HCTR2.

Deep neural networks (DNNs) are today’s central machine learning engines, yet their parameters represent valuable intellectual prop- erty exposed to extraction through black-box queries. While existing cryptanalytic attacks have primarily targeted ReLU-based architectures, this work extends model-stealing techniques to a broad class of non-linear activation functions, including GELU, SiLU, SELU, Sigmoid, and oth- ers. We present the first universal black-box attack capable of recovering both weights and biases from networks whose activations converge to lin- ear behavior outside narrow non-linear regions. Our method generalizes prior geometric approaches by leveraging higher-order derivatives and ad- jacent linear zone analysis, bypassing the need for non-differentiability. We show that, for several activations, neuron signatures can be recov- ered more easily than in the ReLU case, and we further demonstrate that activation functions themselves can be identified when not publicly known. Our results broaden the scope of cryptanalytic model extraction, revealing that the secrecy of activation functions or smoothness of nonlin- earities does not provide effective protection against black-box recovery attacks.

We start from the observation in prior work that cryptography broadly intuits security goals – as modelled in games or ideal functionalities – while claiming realism. This stands in contrast to cryptography’s attentive approach towards examining assumptions and constructions through cryptanalysis and reductions. To close this gap, we introduce a technique for determining security goals. Given that games and ideal functionalities model specific social relations between various honest and adversarial parties, our methodology is ethnography: a careful social science methodology for studying social relations in their contexts. As a first application of this technique, i.e. ethnography in cryptography, we study security at-compromise (neither pre- nor post-) and introduce the security goal of alert blindness. Specifically, in our 2024/2025 six-and-a-half-month ethnographic fieldwork with protesters in Kenya, we observed that alert blindness captures a security goal of abducted persons who were taken by Kenyan security forces for their presumed activism. We show this notion is achievable under standard assumptions by providing a construction secure in our model. We discussed both the notion and the construction with some interlocutors in Kenya.

Digital identity systems require mechanisms for verifiable, privacy-preserving presentations of user attestations. The trivial approach of utilizing selective disclosure by presenting individually signed attestations introduces persistent linkability that compromises user anonymity. Existing anonymous credential systems come with practical drawbacks. Some depend on trusted setups, others require substantial modifications to an issuer’s established issuance flow.

We propose an open, transparent, and lightweight anonymous credential design that addresses these limitations with the use of zero-knowledge proofs. Our construction is modular, requires no trusted setup and integrates with existing workflows without the need for substantial changes to existing cryptographic mechanisms, procedure overhauls, or hardware devices. It delivers unlinkability while maintaining broad applicability across heterogeneous digital-identity ecosystems and current verifiable credential standards.

To demonstrate practicality, we provide a proof-of-concept implementation and benchmarks on mobile devices. Our results show best-in-class proving times, with a focus on efficient client-side proving, an essential requirement for usability in digital identity wallets.

OpenAC was purposely constructed to be compatible with the European Digital Identity Architecture and Reference Framework (EUDI ARF). In the appendix, we map EUDI ARF’s functional, privacy, and interoperability requirements, illustrating how OpenAC satisfies regulatory constraints while preserving strong user privacy.

LWR has been introduced by Banerjee et al. in 2012 as a deterministic variant of LWE. Since then, it has found many applications in the design of symmetric primitives and post-quantum schemes. Despite its deterministic nature, LWR is usually analyzed as LWE, under the (implicit) assumption that no improved attack can take advantage of the additional structure it provides. In this paper, we tackle this assumption in the context of power-of-two moduli and investigate the security of LWR against algebraic attacks in depth. For this purpose, we model its samples as the outputs of a vectorial Boolean function. We first observe that there are corner cases where the state-of-the-art linearisation attack of Arora & Ge does not apply. In contrast, we propose the first LWR-specific attack, which applies in any parameter regime as long as the modulus is a power of two. We combine analyses of standard criteria such as the algebraic degree and the number of monomials in the secret with an analysis of the algebraic normal form, that we are able to express exactly in a compact representation by leveraging group action theory. Our results exhibit specificities in the structure of LWR that we are able to exploit. They allow refining and strengthening the understanding of this important problem, and systematically improve over the attack of Arora & Ge. They also put forward new tools for (symmetric) cryptanalysis, which we believe can be of independent interest.

We report on a novel authenticated key-exchange (AKE) protocol where the authentication is achieved entirely by key-encapsulation mechanisms (KEMs). Techniques to achieve AKE with KEMs have been known for some time, but have received renewed attention in a post-quantum world; in contrast to classical cryptography, the data corresponding to the NIST post-quantum KEM standard is a significant save on bandwidth compared to the signature standard. Previous KEM-authenticated AKE protocols are not known to be composable; our protocol offers similar security guarantees, plus composability, while being more efficient in terms of bandwidth compared to non-composable KEM-based AKE protocols, and composable signature-based AKE protocols. Our protocol features a modular design, and a full security proof in the Constructive Cryptography (CC) framework, one of the major composable security frameworks. We also prove the forward secrecy of our protocol, and introduce generic techniques to prove forward secrecy in CC, which may be of independent interest.

Most PQC schemes remain too resource-intensive for ultra-constrained 8-bit AVR wireless sensor nodes. In this work, we present a comprehensive approach to practical lightweight PQC for such devices, covering scheme design, implementation optimization, and protocol integration. Our contributions are threefold: (i) We propose CTRU-Light, a lattice-based KEM specifically tailored for IoT sensor nodes. It combines small moduli, low-degree polynomials, and NTT-friendly arithmetic for high efficiency, with ASCON used for lightweight symmetric operations. (ii) We explore NTT-friendly moduli for the first time to accelerate modular multiplication on 8-bit AVR platforms and design optimized variants of Montgomery and Barrett multiplication. We show that K-RED2X multiplication exhibits approximate equivalence to Montgomery multiplication under small NTT-friendly moduli. We apply these optimizations to the latest implementations of Kyber (ASIACCS 2025) and Saber (CHES 2025), achieving significant improvements in both speed and code size. Furthermore, we present a highly optimized AVR assembly implementation of CTRU-Light that delivers high efficiency and low stack usage. (iii) We design a Hybrid KEM–MQTT protocol that integrates classical ECDH with post-quantum KEMs. We present the first implementation of this protocol and provide a detailed empirical analysis of its performance. Experiments show that CTRU-Light is the only scheme capable of supporting both pure PQ and hybrid KEM–MQTT on 8-bit WSNs, achieving lower handshake latency than Kyber-512 and LightSaber.

Non-interactive Batch arguments (BARGs) for NP relations enable a prover to generate a single succinct proof for multiple NP instances, significantly amortizing verification costs. While recent pairing-based BARGs achieve impressive results, their practical efficiency remains limited by proof sizes and verifier pairing operations that scale linearly with the size of the Boolean circuit computing the NP relation. In this work, we present a novel pairing-based BARG construction that achieves constant proof size and a constant number of pairing operations, independent of both the number of instances and the circuit size. Our approach leverages a bivariate polynomial commitment to compactly encode all wire values across instances, and introduces a new efficient bi-to-uni variate sumcheck protocol, called BuLosum. BuLosum improves upon prior techniques by reducing proving costs to a single multi-scalar multiplication and verification to only three pairings. Using BuLosum, we further design an optimized matrix multiplication protocol that minimizes both proof size and verification overhead. By integrating these components, we obtain the first pairing-based BARG achieving constant-size proofs and constant number of pairing operations.

An asymmetric Password-Authenticated Key Exchange (aPAKE) protocol allows a client, who holds a raw password, and a server, who holds a one-way mapping of the password, to jointly establish a cryptographically strong session key, without an authenticated channel. The standard security definition for aPAKE is in the Universal Composability (UC) framework. Despite its great potential of being used in practice, existing aPAKE protocols are either not round-optimal, computationally inefficient, or not proven secure.

In this work, we present two aPAKE protocols that are 1 simultaneous round, UC-secure, have reasonable computational costs, and rely on mild cryptographic assumptions. Our first protocol is in the Random Oracle Model and the Algebraic Group Model (ROM+AGM), secure under the CDH assumption, and has computational cost comparable to the most efficient aPAKE protocols in the literature (1 simultaneous round or not). Our second protocol is in the ROM only and secure under the DDH assumption, and also has significantly lower computational cost than the only other UC-secure 1 simultaneous round aPAKE protocol. Interestingly, even our second protocol does not rely on the gap Diffie-Hellman assumption, which requires creative application of the forking lemma.

In this note, we consider a perspective on adversary running times that fixes the adversary's running time to be $2^\kappa$, and then asks: to achieve security against such an adversary, what running time in terms of $\kappa$ do honest parties need? This perspective gives rise to a new natural class of adversary running times that we call \emph{quasi-exponential} time adversaries.

We study lattice constructions arising from Coppersmith’s method combined with the Unravelled Linearization technique introduced by Herrmann and May (ASIACRYPT~2009) for solving structured polynomial equations, which can yield improved asymptotic bounds. This work contributes in two aspects, theoretical and practical.

Theoretical contribution: While Unravelled Linearization, introduced can lead to improved asymptotic bounds, computing these bounds is technically delicate. Previous works typically assume that the lattice dimension is a polynomial function of the scaling parameter $m$ and therefore rely on Lagrange interpolation to derive asymptotic bounds. We show that this assumption does not hold in general. In particular, the interpolation approach used in Herrmann and May (ASIACRYPT~2009) and in \texttt{cuso} (EUROCRYPT~2025) may yield incorrect results: in the former case, the exponant in the determinate may be a quasi-polynomial instead of polynomial, while in the latter it becomes polynomial only beyond a certain threshold. To address this issue, we present a rigorous analysis based on Ehrhart theory for computing asymptotic bounds. As applications, we improve five cryptanalytic results, including attacks on linear congruential generators, quadratic generators, the subset-sum pseudorandom generator, and a recent partial-key attack on isogenies in the P\`oke setting. In the latter case, we reduce the required leakage of most significant bits from $85.29\%$ to $79.81\%$, and further to $79.08\%$ in certain special cases.

Practical contribution: Asymptotic bounds alone are insufficient for practical attacks, since one must also determine an appropriate lattice dimension. To avoid trivial guessing of the lattice dimension from small to large, we introduce an estimator, $\mathsf{DimOracle}$, based on Ehrhart theory. Our approach simultaneously estimates the lattice dimension and determinant via the associated Ehrhart (quasi-)polynomials. Due to Barvinok’s algorithm, any fixed number of leading coefficients of these (quasi-)polynomial can be computed in polynomial time by reducing the problem to volume computations of faces of the Newton polytope. Using these coefficients, $\mathsf{DimOracle}$ provides accurate predictions of the required lattice size in practice. We implement $\mathsf{DimOracle}$ and demonstrate its effectiveness through experimental results.

Doubly-efficient private information retrieval (DEPIR) enables sublinear per-query work (in the database size $N$) for both client and server, while requiring no client state. Despite its theoretical promise, single-server DEPIR exhibits a prohibitive concrete efficiency gap: for $N=2^{23}$, the state-of-the-art construction (Eurocrypt '25) requires a 733TB server state and over $2^{37}$ online RAM/Disk reads, rending it infeasible to execute. This paper advances single-server DEPIR towards practicality through a series of algorithmic innovations. Compared with the state-of-the-art, we achieve a 4 orders of magnitude reduction in server state and a 6 orders of magnitude reduction in query time. In particular, for the same level database ($N=2^{23}$), querying $5461$ elements in a single batch requires only 171GB of server state and $2^{24}$ online RAM/disk reads, yielding a 112s total query time and a 21ms amortized query time.