International Association
for Cryptologic Research

Blind signatures play a central role in cryptographic protocols for privacy-preserving authentication and have attracted substantial attention in both theory and practice. A major line of research, dating back to the 1990s, has focused on constructing blind signatures from pairing-free groups. However, all known constructions in this setting require at least three moves of interaction between the signer and the user. These schemes treat the underlying group as a black box and rely on the random oracle in their security proofs. While computationally efficient, they suffer from the drawback that the signer must maintain state during a signing session. In contrast, round-optimal solutions are known under other assumptions and structures (e.g., RSA, lattices, and pairings), or via generic transformations such as Fischlin’s method (CRYPTO~'06), which employ non-black-box techniques.

This paper investigates whether the three-round barrier for pairing-free groups is inherent. We provide the first negative evidence by proving that, in a model combining the Random Oracle Model (ROM) with Maurer’s Generic Group Model, no blind signature scheme can be secure if it signs sufficiently long messages while making at most a logarithmic number of random oracle queries. Our lower-bound techniques are novel in that they address the interaction of both models (generic groups and random oracles) simultaneously.

The Plonky3 Merkle tree implementation has become one of the most widely deployed Merkle tree constructions due to its high efficiency, and—through its integration into numerous succinct-argument systems—it currently helps secure an estimated \$4 billion in assets. Somewhat paradoxically, however, the underlying 2-to-1 compression function is not collision-resistant, nor even one-way, which at first glance appears to undermine the security of the entire Merkle tree. The prevailing ad-hoc countermeasure is to pre-hash data before using them as leaves in this otherwise insecure Merkle tree.

In this work, we provide the first rigorous security analysis of this Merkle tree design and show that the Plonky3 approach is, in fact, sound. Concretely, we show (strong) position-binding and extractability.

This paper introduces BLISK, a framework that compiles a monotone Boolean authorization policy into a single signature verification key, enabling only the authorized signer subset to produce the standard constant-size aggregated signatures. BLISK combines (1) $n$-of-$n$ multisignatures to realize conjunctions, (2) key agreement protocols to realize disjunctions, and (3) verifiable group operations (for instance, based on the 0-ART framework). BLISK avoids distributed key generation (allowing users to reuse their long-term keys), supports publicly verifiable policy compilation, and enables non-interactive key rotation.

Anonymous credential schemes such as BBS face a significant deployment barrier: currently available secure hardware such as HSMs required for eIDAS Level of Assurance High does not yet support BBS signatures or pairing-friendly curves. We address this challenge by augmenting BBS credentials with a conventional signature (such as ECDSA), where the issuer additionally signs part of the BBS signature using a conventional signature private key that can be secured in widely available HSMs. While disclosing the extra signature breaks unlinkability, we argue this is acceptable for high-assurance use cases where disclosed attributes already uniquely identify the user. For use cases not requiring this additional security, the conventional signature can be omitted to preserve BBS unlinkability. We prove that augmented BBS credentials are existentially unforgeable under chosen message attacks, with security depending solely on the conventional signature private key rather than the BBS private key. This approach provides a practical migration path to full BBS deployment while (apart from unlinkability) maintaining several key BBS advantages.

General-purpose secure multiparty computation (MPC) remains bottlenecked in large part by a lack of efficient techniques for handling memory access. We demonstrate a remarkably simple and efficient 2PC instantiation of random access memory (RAM), based on distributed point functions (DPFs, Gilboa and Ishai, Eurocrypt'14). Our semi-honest 2PC protocol can be achieved from oblivious transfer (OT) and a black-box pseudorandom generator (PRG).

For a memory that stores large enough data words, our 2PC RAM incurs constant communication overhead per access. Like prior works that leverage DPFs to achieve memory access, our work incurs linear computation per access, but our per-access communication is lean.

Our 2PC RAM is built on top of an obliviousness-friendly model of computation called the single access machine model (SAM, Appan et al., CCS'24). In the SAM model, each memory slot can be read at most once. We present a simple 2PC SAM protocol, where each single-access memory operation incurs at most $2w + O(\lambda \lg n)$ bits of communication, where $w$ is the word size, $n$ is the number of memory words, and $\lambda$ is a security parameter. Of this cost, only $2w + 2\lg n$ bits are incurred in the online phase.

Our RAM operations are (non-cryptographically) compiled to SAM operations. At most a logarithmic number of SAM operations are needed per RAM operation; if word size is large, even fewer SAM operations are required. Alternatively, there are now many oblivious algorithms that compile directly to SAM more efficiently than via a compilation to RAM, and our 2PC SAM can instantiate these algorithms. As one example, we can use our 2PC SAM to implement privacy-preserving graph traversal (DFS or BFS) over a secret-shared size-$n$ graph while revealing nothing beyond the runtime of the SAM program. Our construction achieves online communication $O(n \lg n)$ bits, asymptotically matching the number of bits touched in a corresponding cleartext graph traversal.

The block cipher (BC) mode for realizing a variable-input-length strong tweakable pseudorandom permutation (VIL-STPRP), also known as the accordion mode, is a rapidly growing research field driven by NIST's standardization project, which considers AES as a primitive. Widely used VIL-STPRP modes, such as HCTR2, have birthday-bound security and provide only 64-bit security with AES. To provide higher security, NIST is considering two directions: to develop new modes with beyond-birthday-bound (BBB) security and to use Rijndael-256-256 with HCTR2. This paper pursues the first direction while maintaining compatibility with HCTR2. In particular, we provide two solutions to achieve BBB security for two different approaches: (i) general cases without any conditions on the tweak and (ii) under the condition that the same tweak is not repeated too often as adopted in bbb-ddd-AES recently presented at Eurocrypt 2025. For the first approach, we propose a new mode, CHCTR, that iterates HCTR2 with two independent keys, which achieves $2n/3$-bit security in the multi-user (mu) setting and satisfies NIST's requirements. For the second approach, we prove mu security of HCTR2, which allows us to apply the tweak-based key derivation (TwKD) to HCTR2 in a provable manner. When the number of BC calls processed by a single tweak is upper-bounded by $2^{n/3}$, HCTR2-TwKD achieves $2n/3$-bit mu security. By benchmarking optimized software implementations, we show that CHCTR with AES-256 outperforms HCTR2 with Rijndael-256-256, in all the twelve processor models examined. Similarly, HCTR2-TwKD outperforms bbb-ddd-AES in general cases, and it is even comparable to bbb-ddd-AES rigorously optimized for tweak-repeating use cases using precomputation.

Cryptographic hardware implementations are vulnerable to combined physical implementation attacks, integrating Side-Channel Analysis and Fault-Injection Analysis to compromise their security. Although theoretically sound countermeasures exist, their practical application is often complicated and error-prone, making automated security verification a necessity. Various tools have been developed to address this need, using different approaches to formally verify security, but they are limited in their ability to analyze complex hardware circuits in the context of Combined Analysis and advanced probabilistic adversary models.

In this work, we introduce a novel verification method that assesses the security of complex hardware circuits in the context of random probing with random faults, a scenario that more closely reflects real-world combined attack scenarios. Our approach centers around symbolic fault simulation and the derivation of a fault-enhanced leakage function using the Fourier-Hadamard Transform, enabling the computation of tight leakage probabilities for arbitrary circuits and providing a more accurate and comprehensive security analysis. By integrating our method into the INDIANA security verification framework, we extended its capabilities to analyze the leakage behavior of circuits in the presence of random faults, demonstrating the practicality of our approach.

The results of our evaluation highlight the versatility and scalability of our approach, which can efficiently compute leakage probabilities under various fault scenarios for large-scale attacks, e.g., for a masked round of the PRESENT cipher. Notably, our method can complete most experiments in less than an hour, demonstrating a significant improvement over existing estimation-based tools. This achievement confirms the potential of our approach to provide a more comprehensive and practically useful security assessment of hardware circuits, and marks an important step forward for the development of secure hardware systems.

The NIST lattice-based cryptographic standards are set to be widely adopted, offering solutions to the most common cryptographic needs, namely key establishment and authentication (signature). This shifted the attention to more advanced primitives such as threshold cryptography as well as privacy-enhanced technologies, where the transition is expected to be more complex. This is particularly true in the context of post-quantum anonymous authentication where the existing mechanisms may not match the performance requirements of industrial applications. An important avenue for improvement of said performances is the lattice sampler, which is at the center of these mechanisms. Despite recent progress, prior samplers neglected one component: the tag. The latter is not only necessary for security, but it also impacts the efficiency of the subsequent constructions if not handled properly. In this paper, we introduce a new sampler with an enhanced tag management that yet retain the main features of current samplers, and can thus be used as a plug-in replacement. It offers a sampling quality independent of the tag, allowing for producing preimages that are both smaller and faster to generate than those from the very recent sampler of Jeudy and Sanders (Asiacrypt'25). Far from being anecdotal, plugging it into several advanced authentication mechanisms results in size improvements of up to 30%, while being 35% faster.

The Rank Syndrome Decoding (RSD) problem forms the foundation of many post-quantum cryptographic schemes. Its inherent hardness, with best known algorithms for common parameter regimes running in time exponential in $n^2$ (for $n$ being the code length), enables compact parameter choices and efficient constructions. Several RSD-based submissions to the first NIST PQC process in 2017 were, however, invalidated by algebraic attacks, raising fundamental concerns about the security of RSD-based designs.

In this work, we revisit the parameters of prominent rank-based constructions and analyze the rationales that guided their selection, as well as their security against modern attacks. We provide a unified complexity analysis of all major RSD algorithms, including combinatorial, algebraic, and hybrid approaches, under a common cost model. All estimates are made publicly available through a dedicated open source module.

Furthermore, we present the first asymptotic analysis of these algorithms, yielding deep insights into the relations between different procedures. We show that all studied algorithms converge to one of three distinct asymptotic runtime exponents. We then provide an asymptotic baseline in terms of the worst-case decoding exponent. In particular, we find that for an extension degree equal to the code length, the best known algorithms achieve a complexity of $2^{0.1481n^2 + o(n^2)}$, attained simultaneously by algebraic and combinatorial approaches. Overall, our results reinforce confidence in the RSD assumption and the design rationales of modern RSD-based schemes such as RYDE.

Post-quantum secure digital signatures based on the MPC-in-the-Head (MPCitH) paradigm, a zero-knowledge (ZK) proof-based construction, are becoming increasingly popular due to their small public key size. However, the development of techniques for protecting MPCitH-based schemes against side-channel attacks remains slow, despite them being critical for real-world deployment. In this work, we adapt the Hypercube-MPCitH framework exploiting its native use of additive secret sharing to enable inherent protection against first- and high-order differential power analysis (DPA). We first perform a sensitivity analysis of the Hypercube Syndrome Decoding in the Head (SDitH) digital signature scheme with respect to both simple and differential power analysis. Based on the insight into its side-channel sensitivity, we then propose a tweak to the signature scheme to increase its inherent resistance against DPAs by design, eliminating the need to explicitly mask large parts of the signing procedure. More specifically, this is achieved through the novel (k+1)-Hypercube ZK Protocol: the proposed tweak increases the number of hidden shares an adversary must probe to recover the secret key from one to k+1, thus achieving inherent masking order k. Typically, increasing the amount of hidden shares results in a degradation of soundness in the zero-knowledge proof and as a result increases the signature size to a point where the scheme becomes of limited practical interest. To address this, we propose a technique to select the hidden shares in a more structured and optimal fashion, by exploiting the GGM tree structure in the Hypercube-MPCitH framework. As a result, the amount of revealed seeds is reduced, thus resulting in a smaller signature size even compared to the original hypercube protocol. Finally, we implement and benchmark the proposed Hypercube-SDitH signature scheme, comparing it against the cost of traditional masking. We propose different parameter sets that explore a trade-off between computational overhead and signature size. For 3rd-order protection, our tweaked signature scheme only incurs a 35-50% overhead in computational cost, compared to an estimated overhead of 300% for a fully masked implementation, while the overhead in signature size stays relatively low (52%). Overall, we demonstrate that the proposed (k+1)-Hypercube ZK Protocol can be used to construct efficient, DPA-resistant MPCitH-based digital signatures.

Private set intersection (PSI) protocols are an essential privacy-enhancing technology for many real-world use cases, ranging from mobile contact discovery to fraud detection. However, PSI executed directly between input parties can result in unreasonable performance overhead. This motivates the study of outsourced PSI, where clients delegate the heavy PSI operations to an untrusted (cloud) server.

In this SoK, we introduce a framework of 12 distinct properties that characterize outsourced PSI protocols based on security, functionality, and efficiency. By analyzing 20 protocols through this framework, we provide a valuable resource and an interactive tool for researchers and practitioners to select the most suitable protocols for their specific requirements. Finally, we discuss research gaps between trends in regular PSI and the current state of outsourced PSI, identifying promising avenues for future work.

In the field of hardware masking, threshold implementations are a well-known technique that provides glitch-resistant power analysis security. While they guarantee probing security, finding a uniform sharing without additional randomness is difficult, making it challenging to apply to certain functions and, consequently, making it impossible to develop a tool that can straightforwardly generate the masked circuit. Additionally, this approach forces designers to use at least three shares in the underlying masking, which can make the design more costly. Other schemes, like DOM, which can work with two shares, often require fresh randomness. To address these issues, Shahmirzadi and Moradi introduced the NullFresh masking technique at CHES 2021. This method allows for uniform sharing with no additional randomness, using the minimal number of shares. However, similar to original threshold implementations, it is not always straightforward to find a NullFresh masking for arbitrary functions.

In this work, we introduce an automated technique to provide masking for arbitrary functions, ensuring first-order security. This technique is applicable to functions where the number of output bits does not exceed the number of input bits. While this technique introduces additional register stages (resulting in higher latency and area) compared to existing methods, it addresses the automation challenges of threshold implementations, which have remained an open problem since their inception. We present the masking technique, along with proofs of glitch-extended probing security, and demonstrate its application to several ciphers, including PRINCE, MIDORI, SKINNY, KECCAK, and AES. The masked designs were verified using SILVER and PROLEAD, and tested on an FPGA through TVLA.

Signature schemes based on the MPC-in-the-Head (MPCitH) paradigm play an important role in enabling cryptosystems founded on a wide diversity of hardness assumptions. While the design of such schemes is currently stabilizing, providing efficient implementations on embedded devices remains a critical challenge, as MPCitH frameworks are known to manipulate large data structures and to rely heavily on symmetric primitives.

In this work, we present a highly optimized implementation of the NIST candidate MQOM (version 2) targeting embedded microcontrollers. Our implementation significantly outperforms existing MPCitH implementations on such platforms, both in terms of memory footprint and execution time. In particular, for the L1 parameter set, we can achieve an SRAM usage below 10 KB, including the key and signature buffers, while preserving practical signing and verification performance.

We also provide the first memory-friendly implementation of the one-tree technique, which is used to reduce signature sizes in several MPCitH-based schemes. This enables a comparative analysis of the implementation costs of correlated trees versus the one-tree technique. We then demonstrate how streaming and precomputation techniques can further mitigate the impact of the running time and the signature size.

This paper presents a formal framework for enhancing privacy in decentralized identity (DID) systems, resolving the inherent conflict between blockchain verifiability and the principle of minimal data disclosure. At its core, we introduce a provably secure cryptographic protocol that leverages attribute commitments on-chain and zero-knowledge proofs for off-chain validation. This approach allows users to demonstrably prove the validity of predicates about their attributes without revealing the underlying sensitive values. We formally define the security and privacy requirements for such a system—including consistency, attribute-based indistinguishability, and predicate-based indistinguishability—within a semi-honest adversarial model. We then construct a concrete scheme that realizes these properties under standard cryptographic assumptions. The proposed architecture is designed for full backward compatibility with W3C DID standards, ensuring practical deployability. Security analysis provides rigorous, provable guarantees, while performance evaluation confirms the efficiency of the core cryptographic operations, supporting its use in resource-constrained environments. This work establishes a foundational and analyzable basis for building decentralized identity systems where both accountability and user privacy are essential.

We introduce Lether, the first practical account-based private block-chain payment protocol based on post-quantum lattice assumptions, following the paradigm of Anonymous Zether (FC '19, IEEE S&P '21). The main challenge in building such a protocol from lattices lies in the absence of core building blocks: unbounded-level additively-homomorphic multi-message multi-recipient public key encryption (mmPKE), and event-oriented linkable ring signatures with support for multiple tags (events). To address these issues, we propose a verifiable refreshable additively-homomorphic mmPKE scheme and a plug-and-play event-oriented linkable tag scheme from lattices. We believe both to be of independent interest.

To achieve unbounded-level homomorphic evaluation in the lattice-based setting without relying on heavy techniques such as bootstrapping or large moduli (e.g., over 60 bits) in fully homomorphic encryption (FHE), we introduce a lightweight and blockchain-friendly mechanism called refresh. Namely, each user is required to verifiably refresh their account after a certain number of transactions. With our tailored parameter settings, the amortized per-refresh costs of communication and computation are only about 1.3% and 1.5%, respectively, of the cost of a transaction.

We also optimize the implementations of LNP22 lattice-based zero-knowledge proof system (Crypto '22) in the LaZer library (CCS ’24), to support efficient batching of various proof components. Overall, for a typical transaction, the total communication cost becomes about 68 KB, with the associated zero-knowledge proof accounting for about 51 KB of this total. Each of proof generation and verification take a fraction of a second on a standard PC.

As an additional contribution, we formalize new definitions for Anonymous Zether-like protocols that more accurately capture real-world blockchain settings. These definitions are generic and are expected to benefit the broader development of account-based private blockchain payment protocols, beyond just lattice settings.

Threshold signature schemes play a vital role in securing digital assets within blockchain and distributed systems. $\textsf{FROST2}$ stands out as a practical threshold Schnorr signature scheme, noted for its efficiency and compatibility with standard verification processes. However, under the one-more discrete logarithm assumption, with static corruption and centralized key generation settings, $\textsf{FROST2}$ has been shown by Bellare et al. (in CRYPTO 2022) to achieve only $\textsf{TS-SUF-2}$ security, which is a consequence of its vulnerability to $\textsf{TS-UF-3}$ attacks.

In this paper, we address this security limitation by presenting two enhanced variants of $\textsf{FROST2}$: $\textsf{FROST2}\texttt{+}$ and $\textsf{FROST2}\texttt{#}$, both achieving the $\textsf{TS-SUF-4}$ security level under the same computational assumptions as the original $\textsf{FROST2}$. The first variant, $\textsf{FROST2}\texttt{+}$, strengthens $\textsf{FROST2}$ by integrating additional pre-processing token verifications that help mitigate $\textsf{TS-UF-3}$ and $\textsf{TS-UF-4}$ vulnerabilities while maintaining practical efficiency. We show that $\textsf{FROST2}\texttt{+}$ can achieve $\textsf{TS-SUF-4}$ security not only under the same conditions as the original $\textsf{FROST2}$ analysis, but also when initialized with a distributed key generation protocol such as $\textsf{PedPoP}$. Building on these improvements, we identify optimization opportunities that lead to our second variant, $\textsf{FROST2}\texttt{#}$, which achieves $\textsf{TS-SUF-4}$ security with enhanced computational efficiency by eliminating redundant calculations. Our benchmark shows that the performance of $\textsf{FROST2}\texttt{+}$ is comparable to $\textsf{FROST2}$ while $\textsf{FROST2}\texttt{#}$ is at least 3 times faster than $\textsf{FROST2}$.

Differential privacy (DP) has emerged as a rigorous framework for privacy-preserving data analysis, with widespread deployment in industry and government. Yet existing implementations typically assume that the party applying the mechanism can be trusted to sample noise correctly. This trust assumption is overly optimistic: a malicious party may deviate from the protocol to gain accuracy or avoid scrutiny, thereby undermining users’ privacy guarantees.

In this paper, we introduce Noisette, a family of efficient protocols for certifying DP noise sampling across both discrete and continuous settings. We design a protocol that supports any discrete distribution through certifiable lookup table evaluation, and introduce a staircase-based optimization that greatly improves efficiency without compromising privacy or utility. We further extend this framework to continuous mechanisms, providing the first efficient protocol for certifiable continuous noise sampling. We demonstrate the practicality of our protocols through concrete DP applications, including mean estimation and federated learning. Our protocols outperform the prior state-of-the-art by up to $64\times$ in runtime and $24\times$ in communication, while preserving the same accuracy as uncertified DP mechanisms. These results establish Noisette as the first efficient, scalable, and general-purpose solution for certifiable DP noise sampling, making certified privacy guarantees practical in high-stakes applications.

Neural networks have achieved remarkable success across a wide range of domains, including applications involving sequential data such as natural language processing and time-series prediction. However, in many real-world deployments, it is essential to ensure the integrity of the inference process–namely, that the output of a model is correctly computed–without revealing the model’s data. While prior work has introduced zero-knowledge proof (ZKP) schemes for convolutional and feedforward neural networks, these do not extend naturally to recurrent architectures due to the challenges introduced by temporal dependencies and weight sharing.

In this paper, we propose zkRNN, a novel ZKP system for recurrent neural networks (RNNs), enabling the prover to demonstrate that a model’s output is correctly computed over a sequential input without revealing any information about the model parameters. Our approach builds upon the GKR protocol, and a recursive sum-check framework introduced in prior work and adapts them to handle the recurrent structure of RNNs. We design a circuit representation that encodes hidden-state transitions, unrolls computation across time steps, and shares weights in a manner compatible with sum-check-based verification. Our protocol achieves polylogarithmic verifier time and proof size in the size of the final iteration circuit and remains independent of the sequence length. The evaluation results demonstrate practical proof generation and succinct, sequence-length-independent verification, with second-scale proving and millisecond-scale verification.

Distributed key generation (DKG) is a foundational building block for designing efficient threshold cryptosystems, which are crucial components of blockchain ecosystems. Existing DKG protocols address the problem in a standalone setting, focusing on establishing the final DKG public key and individual secret keys among the participating parties. This work focuses on DKG primitives for use over blockchain, where the final DKG public key must be available on-chain, enabling on-chain smart contracts to seamlessly execute threshold cryptographic verifications. We observe that existing standalone DKG designs do {\em not} sufficiently exploit the presence of blockchain, leaving substantial scope for improvement in performance.

In this work, we design the first discrete-log-based DKG protocol tailored for use over blockchain, leveraging the blockchain's built-in consensus mechanism to realize DKG efficiently. Interestingly, the use of blockchains enables us to solve DKG while tolerating up to one-half Byzantine faults even in non-synchronous settings. Our protocol is asynchronous, allowing it to operate independently of the network's timing assumptions, with the exact network model depending on the destination blockchain.

Our solution further utilizes an associated random beacon to select smaller committees and achieves a DKG protocol with sub-cubic communication complexity, sub-quadratic computation complexity, and minimal on-chain storage. Notably, our protocol employs a single invocation of consensus and can terminate in just eleven communication rounds in the good case when deployed on an optimal latency partially synchronous blockchain. Our experiments show that our protocol terminates faster than state-of-the-art standalone protocols, with similar bandwidth overhead for committee members and significantly reduced bandwidth for other parties. Additionally, our protocol benefits from higher CPU resources—when deployed on machines with $32$ vCPUs, it completes in approximately $6.5$ seconds in the optimistic case, even for larger systems with $256$ nodes.

HQC is a code-based key-encapsulation mechanism standardized by NIST, whose decapsulation follows a Fujisaki--Okamoto (FO) transform and therefore re-executes encryption-side encoding during deterministic re-encryption. In this paper, we show that this design choice exposes a critical leakage point in the \emph{Reed--Muller (RM) encoding} routine: across the NIST-submitted implementations, the HQC team's official codebase, and the PQClean implementations.

We demonstrate the practical impact of this leakage on a ChipWhisperer CW308 UFO board with an STM32F303 (Cortex-M4) target. Using a total of 5{,}000 power traces for profiling and evaluation, we recover the full 128-bit encapsulation message from a \emph{single} decapsulation trace with up to 96.9\% success. In comparison, the current state of the art for single-trace HQC message recovery based on \emph{soft-analytical side-channel attacks} (SASCA) reports profiling on the order of 500{,}000 traces; our approach therefore reduces the required profiling budget by two orders of magnitude while achieving comparable single-trace capability.

Beyond session-key compromise, we show that direct recovery of the decrypted message can serve as an oracle primitive that substantially lowers the cost of oracle instantiation in prior HQC secret-key recovery frameworks. While prior oracle instantiations typically map leakage to a discrete set of task-specific labels, our approach recovers the decrypted message itself, and thus applies uniformly over the full message space (i.e., arbitrary $m'$ values). Concretely, we reduce the profiling cost required to instantiate a \emph{decryption success/failure} oracle, multi-value plaintext-checking, and full-decryption oracles by approximately 90.3\%, 84.83\%, and 26.7\%, respectively.