International Association
for Cryptologic Research

In the Web2 world, users control their accounts using credentials such as usernames and passwords, which can be reset or recovered by centralized servers if the user loses them. In the decentralized Web3 world however, users control their accounts through cryptographic private-public key pairs which are much more complex to manage securely. In addition, the decentralized nature of Web3 makes account recovery impossible in the absence of predetermined recovery mechanisms. With the proliferation of blockchains and cryptocurrencies over the last years, it is crucial to provide users secure, usable and reliable ways to recover their accounts and assets. However, up to this day, no Web3 recovery method has adequately achieved all three of the above required properties. For instance, conventional ``mnemonic" backups which can deterministically reconstruct a private key require verbatim recall of a fixed word list, creating an unpleasant usability/security trade-off.

In this work, we present a fully-offline protocol called LifeXP$^{+}$, that allows a user to reconstruct a cryptographically-secure private key from a natural-language story, which a user always remembers, such an memorable life event. To ensure usability of our protocol, key reconstruction can work even when the story is later retold with different wording or grammar, only requiring to preserve the semantics. The protocol combines pre-trained sentence embeddings to capture semantics, locality-sensitive hashing to quantize embeddings into stable bit strings, a cryptographic fuzzy extractor that corrects bit errors caused by paraphrasing, and a biometric factor that is fused with the linguistic factor to boost entropy and enhance security. In our paper we describe the design, show that the protocol achieves the required properties, and provide an evaluation based on publicly-available datasets which runs completely offline on commodity hardware, showcasing its feasibility.

This paper introduces an ML-guided scoring heuristic for differential trail beam search in substitution--permutation network (SPN) ciphers. Instead of replacing classical search procedures or relying on heavy learning architectures, we take a residual-learning approach: a gradient boosting regressor is trained to predict the error of a simple nibble-count lower bound on the remaining trail cost. At search time, the predicted residual is fused multiplicatively into the beam scoring function, using per-layer robust normalization and a conservative floor to preserve safety. This design keeps the underlying search structure such as beam width, pruning rules, and lower-bound guarantees unchanged, while aiming to improve the ranking of partial trails. We instantiate the method on the 64-bit block cipher GIFT-64 under the classical Markov differential model. Our implementation reproduces state of the art differential trails with identical weights and round by round differences, and achieves 10--40\% reductions in the number of expanded nodes in moderate-depth searches, with runtime trade-offs analyzed across different model horizons. The results suggest a practical, non-invasive paradigm for enhancing classical cryptanalytic search with learned corrections, without redesigning existing algorithms or probability models, and are in principle applicable to a range of SPN designs.

Zero-knowledge virtual machines (zkVMs) rely on tabular constraint systems whose verification semantics include gate, lookup, and permutation relations, making correctness auditing substantially more challenging than in arithmetic-circuit DSLs such as Circom. In practice, ensuring that witness-generation code is consistent with these constraints has become a major source of subtle and hard-to-detect bugs. To address this problem, we introduce a high-level semantic model for tabular constraint systems that provides a uniform, circuit-irrelevant interpretation of row-wise constraints and their logical interactions. This abstraction enables an inductive, row-indexed reasoning principle that checks consistency without expanding the full circuit, significantly improving scalability. We implement this methodology in ZIVER and show that it faithfully captures real zkVM designs and automatically validates the consistency of diverse SP1 chip components.

Hash-based signature schemes offer a promising post-quantum alternative for Bitcoin, as their security relies solely on hash function assumptions similar to those already underpinning Bitcoin's design. We provide a comprehensive overview of these schemes, from basic primitives to SPHINCS+ and its variants, and investigate parameter selection tailored to Bitcoin's specific requirements. By applying recent optimizations such as SPHINCS+C, TL-WOTS-TW, and PORS+FP, and by reducing the allowed number of signatures per public key, we achieve significant size improvements over the standardized SPHINCS+ (SLH-DSA).We provide public scripts for reproducibility and discuss limitations regarding key derivation, multi-signatures, and threshold signatures.

In this work, we analyze the mathematical aspect of the MAYO signature scheme. Following the specification of MAYO, we generate the keys where the secret key is a matrix and the public key is a system of quadratic polynomial of multiple variables; then use them to sign. During the signing procedure, we disprove the claim that the polynomial only has a constant part and a linear part after sampling values for the vinegar variables. Technically, we provide the mathematical expression of an arbitrarily polynomial of the system after substitution and discover that in addition of having a constant part and a linear part, the polynomial also has a quadratic part. The quadratic state of the polynomials after substitution allows us to conclude that signing fails with the third attempt of MAYO.

We study a new variant of the $k$-sum problem. In the classical formulation, one is given $k$ lists of binary vectors and must find one vector from each list such that their sum is the zero vector. In our variant, vectors are instead chosen from the set $\{-1,1\}^m$. First, we analyse how the complexity of the original problem changes when one use $\pm 1$ vectors. We show that this variant achieves better than square-root complexity when using more than two lists, although its overall complexity for $k \geq 4$ is worse than that for the binary case. As an application of our algorithms, we present a combinatorial attack strategy for a recently proposed variant of the Inhomogeneous Short Integer Solution (ISIS) problem known as the randomised one-more ISIS assumption. Our combinatorial attack is more effective than previous combinatorial attacks on this problem.

We further consider a generalised setting of the $k$-sum problem in which the target sum is not the zero vector, but a given integer vector $Y \in \mathbb{Z}_p^m$ that is known to be a sum of $\pm 1$ vectors. We study the complexity of reconstructing such a decomposition of $Y$ using $k$ lists of candidate vectors. Our analysis shows that, as the number of lists increases, the problem becomes solvable in approximately cube-root time.

Device identifiers like the International Mobile Equipment Identity (IMEI) are crucial for ensuring device integrity and meeting regulations in 4G and 5G networks. However, sharing these identifiers with Mobile Network Operators (MNOs) brings significant privacy risks by enabling long-term tracking and linking of user activities across sessions. In this work, we propose a privacy-preserving identifier checking method in 5G. This paper introduces a protocol for verifying device identifiers without exposing them to the network while maintaining the same functions as the 3GPP-defined Equipment Identity Register (EIR) process. The proposed solution modifies the PEPSI protocol [USENIX, 2024] for a Private Set Membership (PSM) setting using the BFV homomorphic encryption scheme. This lets User Equipment (UE) prove that its identifier is not on an operator’s blacklist or greylist while ensuring that the MNO only learns the outcome of the verification. The protocol allows controlled deanonymization through an authorized Law Enforcement (LE) hook, striking a balance between privacy and accountability. Implementation results show that the system can perform online verification within five seconds and requires about 15 to 16 MB of communication per session. This confirms its practical use under post-quantum security standards. The findings highlight the promise of homomorphic encryption for managing identifiers while preserving privacy in 5G, laying the groundwork for scalable and compliant verification systems in future 6G networks.

This paper provides an upper bound on the success rate (SR) of side-channel attacks (SCAs) on masked implementations. We present a formal security proof of additive masking—including both Boolean and arithmetic—through new reductions from relaxed noisy leakage (RNL) to the probing model. Unlike existing proofs relying on random probing (RP), our proof introduces a novel security notion named leakage energy (LE), which enables a tighter bound. In addition, our proof reveals the necessary and sufficient condition for asymptotic security of additive masking in both the noisy leakage and mutual information frameworks, which includes a resolution to an open problem in TCC 2016. Our claims are validated through numerical evaluations. As an application of our theorems, we propose a binary block-cipher based leakage-resilient primitive based on a variant of $\mathsf{XEX}$, which claims $d$-th order SCA security of arithmetic masking by design, enabling efficient $\mathsf{OCB}$-style authenticated encryption with an implementation cost of $O(d)$.

Multi-signatures enable multiple parties to create a joint signature on the same message. Such schemes aggregate several individual signatures and public keys into a short signature and aggregated public key, and verification is performed on these combined values. Interestingly, all existing notions of unforgeability for multi-signatures are designed with a single honest user in mind, overlooking the multi-user setting that multi-signatures are built for. While multi-user security can be bootstrapped from any single-user secure scheme, the straightforward adoption implies a security loss that is linear in the number of signers n. In this work we therefore start the investigation of multi-signatures with tight multi-user security. We show that none of the existing multi-signatures with tight single-user security seems amendable to the multi-user setting, as all their proofs and design choices exploit the fact that there is only a single honest user. Based on this insight, we then propose two new constructions built from scratch with multi-user security in mind: Skewer-NI, a non-interactive and pairing-based scheme, and Skewer-PF, a pairing-free and two-round construction. We prove both schemes tightly secure under the DDH assumption in the ROM. Both schemes also improve the state-of-the-art in another aspect: they support the feature of key aggregation. Skewer-NI is the first non-interactive tightly secure multi-signature with this feature. In the pairing-free two-round setting, Skewer-PF is the first to combine tight multi-user security with key aggregation where the only prior result, due to Bacho and Wagner (CRYPTO’25), achieved aggregation but only in the single-user case.

Hash-based succinct non-interactive arguments (SNARGs) are a widely studied and deployed class of proof systems. The security of practical hash-based SNARGs relies on two combinatorial parameters of its underlying linear code $\mathcal{C}$: a distance-preservation error $\varepsilon(\mathcal{C},\delta)$ and the list size $|\Lambda(\mathcal{C}, \delta)|$ (both parametrized by a proximity parameter $\delta$). Optimistically, one might hope that these parameters are bounded all the way to the capacity regime: when the proximity parameter $\delta$ approaches the minimum distance of the code $\delta(\mathcal{C})$. Perhaps too optimistically, several deployed hash-based SNARGs indeed operate in this regime, and initiatives such as the Ethereum Proximity Prize investigate to which extent soundness is preserved in this setting.

We present a minimal toy protocol whose analysis captures most of the complexity of state-of-the-art hash-based SNARGs, and present a generic attack whose success probability depends on the list size $|\Lambda(\mathcal{C}, \delta)|$. Further, we investigate the common settings when the code $\mathcal{C}$ is an extension code over a field $\mathbb{F}$ of a base code $\mathcal{C}_\mathbb{B}$ over a small base field $\mathbb{B}$. In this setting, we show that classical combinatorial lower bounds on the list-size of the code yields strong attacks that affect the regimes in which hash-based SNARGs operate in practice.

Cross-chain bridges have emerged as key components of blockchain infrastructure, enabling digital assets to flow across chains and benefit from non-native features. While early bridge designs were fraught with brittle trust assumptions, more recent designs, even within Bitcoin's script limits, can operate in a trust-minimized setting. Given this ever-increasing expansion of blockchain bridge systems, a critical question regarding custody arises: When a user's coins cross a bridge back and forth, is there a possibility that they are substituted with other coins upon return? Naturally, if cryptocurrencies were truly fungible, this would not be a consequential event. Nevertheless, chain analytics algorithms as applied to Bitcoin, Ethereum, and other popular chains can trace coins' provenance up to their minting event, thereby highlighting the possibility that users may end up with "tainted" coins upon receiving their coins from a peg-out bridge operation. Similarly, this also highlights the possibility that bridges could become an attraction for money laundering.

To address these considerations, we put forward the concept of ownership preservation for blockchain bridges and we observe that existing multi-sig and BitVM bridges fail to satisfy it. We then present a novel BitVM-based bridge that enables Bitcoin to connect bidirectionally with another DeFi supporting chain in an ownership-preserving and trust-minimized manner. We also observe that our ownership-preserving design is the first Bitcoin bridge to facilitate the transfer of Bitcoin NFTs, Ordinals, across chains, extending in this way their potential value and use cases.

The primal attack reduces Learning with Errors (LWE) to the unique Shortest Vector Problem (uSVP), and then applies lattice reduction such as BKZ to solve the latter. Estimating the cost of the attack is required to evaluate the security of constructions based on LWE.

Existing fine-grained estimators for the cost of the primal attack, due to Dachman-Soled--Ducas--Gong--Rossi (CRYPTO 2020) and Postlethwaite--Virdia (PKC 2021), differ from experimental data as they implicitly assume the unique shortest vector is resampled several times during the attack, changing its length. Furthermore, these estimators consider only the first two moments of the LWE secret and error, and therefore do not differentiate between distinct centred distributions with equal variances. We remedy both issues by initially fixing the short vector's length, and later integrating over its distribution. We provide extensive experimental evidence that our estimators are more accurate and faithfully capture the behaviour of different LWE distributions.

In the case of Module-LWE, lattice reduction utilising the module structure could lead to cheaper attacks. We build upon the analysis of module lattice reduction by Ducas--Engelberts--Perthuis (Asiacrypt 2025), providing a simulator for Module-BKZ generalising the BKZ simulator of Chen--Nguyen (Asiacrypt 2011). We design estimators for a module variant of the primal attack, supporting our analysis with experimental evidence. Asymptotically, we show the module primal attack over a degree $d$ number field $K$ has a reduced cost, resulting in a subexponential gain, whenever the discriminant $\Delta_K$ satisfies $\vert \Delta_K \vert < d^d$, one such case being non-power-two cyclotomics.

Simulation is a fundamental technique in cryptography, central to security proofs, probably most well-known is its use for showing zero-knowledge. In this paper, we consider simulations no longer being merely a proof technique, but to constructively use simulators of non-interactive zero-knowledge proofs (NIZKs) as an integral component of cryptographic designs. We have occasionally seen such a use, e.g., in designated verifier signatures (DVS), deniable encryption, or the recent concept of anamorphic encryption. However, it was never explicity explored as a stand-alone concept, which is the goal of this paper.

By embedding simulated proofs directly into concrete systems, we unlock cryptographic functionalities that were previously out of reach under standard assumptions or required prohibitively complex techniques. In other words, by incorporating simulated proofs into the ``real'' world, rather than the simulated one, we achieve conceptually more elegant primitives. As a primer, we construct a secure signature scheme whose security hinges on a simulated proof of a false statement, i.e., the ludicrous statement $1 = 2$.

To illustrate the broader potential of this approach, we present new and simple constructions of chameleon hash functions with strong privacy guarantees (e.g., full indistinguishability), that do not require a trusted setup. Additionally, we present a very simple DVS with tight security proofs and a strengthened notion of non-transferability.

Based on the zero-knowledge guarantees of the underlying NIZKs, the resulting constructions achieve privacy even if the adversary is allowed to choose the random coins to set up the cryptographic material. To model this, we introduce the notion of trapdoor-detectable zero-knowledge, which may be of independent interest.

Secure multiparty computation (MPC) is perhaps the most popularparadigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case ofunconditional (information-theoretic) security, protocols are known which tolerate a dishonest minorityof players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model).

A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked.

1. We construct an MPC protocol which uses the broadcast channel only three times in a preprocessing phase, after which it is never required again. Ours is the first unconditionally secure MPC protocol for $t < n/2$ to achieve such a low number of broadcast rounds. In contrast, combining the best previous techniques yields a protocol with twenty four broadcast rounds.

2. In the negative direction, we show a lower bound of two broadcast rounds for the specific functionality of Weak Secret Sharing (a.k.a. Distributed Commitment), also a very natural functionality and central building block of many MPC protocols.

The broadcast-efficient MPC protocol relies on new constructions of Pseudosignatures and Verifiable Secret Sharing, both of which might be of independent interest.

Verifying the security of masked hardware and software implementations, under advanced leakage models, remains a significant challenge, especially when accounting for glitches, transitions and CPU micro-architectural specifics. Existing verification approaches are either restricted to small hardware gadgets, small programs on CPUs such as Sboxes, limited leakage models, or require hardware-specific prior knowledge. In this work, we present aLEAKator, an open-source framework for the automated formal verification of masked cryptographic accelerators and software running on CPUs from their HDL descriptions. Our method introduces mixed-domain simulation, enabling precise modeling and verification under various (including robust and relaxed) 1-probing leakage models, and supports variable signal granularity without being restricted to 1-bit wires. aLEAKator also supports verification in the presence of lookup tables, and does not require prior knowledge of the target CPU architecture. Our approach is validated against existing tools and real-world measurements while providing innovative results such as the verification of a full, first-order masked AES on various CPUs.

SQIsign, the only isogeny-based signature competing in the ongoing NIST call for additional signatures, offers the most compact key and signature sizes among all other candidates. It combines isogenies with quaternion arithmetic for its signing procedure. In this work, we address a gap in the current implementation of SQIsign: the absence of constant-time algorithms for quaternion arithmetic. We propose constant-time algorithmic formulations for three fundamental routines in SQIsign's quaternion layer.

First, we discuss a constant-time Hermite Normal Form (HNF) algorithm. We then present a new constant-time approach for computing a generator of a quaternion ideal, replacing the exhaustive search-based approach used in SQIsign. Our approach eliminates the need for coefficient scanning, coprimality tests, and norm evaluation loops, yielding a data-independent and deterministic procedure.

Finally, we design a constant-time version of the GeneralizedRepresentInteger algorithm for solving norm equations in special extremal orders. We circumvent timing dependencies arising from primality checks, modular square root calculations, and Euclidean division steps by introducing a regularized control flow with fixed-iteration sampling and branch-free arithmetic. We also show that the tools developed along the way enable a constant-time version of the recently introduced Qlapoti algorithm.

In our constant-time algorithms, the cost of large operand operations remains a bottleneck for the constant-time HNF and GeneralizedRepresentInteger. We believe our work will facilitate secure and efficient implementations and inspire further works on deployment-level optimizations.

Single Secret Leader Election (SSLE) protocol facilitates the election of a single leader per round among a group of registered nodes while ensuring unpredictability. Ethereum has identified SSLE as an essential component in its development roadmap and has adopted it as a potential solution to counteract potential attacks. However, we identify a new form of attack termed the state uniqueness attack that is caused by malicious leaders proposing multiple publicly verifiable states. This attack undermines the property of uniqueness in subsequent leader elections and, with high probability, leads to violations of fundamental security properties of the over-layer protocol such as liveness. The vulnerability stems inherently from the designs reducing the uniqueness guarantee to a unique state per election, and can be generalized to the existing SSLE constructions. We further quantify the severity of this attack based on theoretical analysis and real-world executions on Ethereum, highlighting the critical challenges in designing provably secure SSLE protocols. To address the state uniqueness attack while ensuring both security and practical performance, we present a universal SSLE protocol called Mobius that does not rely on extra trust assumptions. Specifically, Mobius prevents the generation of multiple verifiable states for each election and achieves a unique state across consecutive executions through an innovative approximately-unique randomization mechanism. In addition to providing a comprehensive security analysis in the Universal Composability framework, we develop a proof-of-concept implementation of Mobius, and conduct extensive experiments to evaluate the security and overhead. The experimental results show that Mobius exhibits enhanced security while significantly reducing communication complexity throughout the protocol execution, achieving over 80% reduction in the registration phase.

Secure coin-tossing is typically modeled as an input-less functionality, where parties with no private inputs jointly generate a fair coin. In the dishonest majority setting, however, a strongly fair coin-tossing protocol is impossible. To circumvent this barrier, recent work has adopted the weaker notion of game-theoretic fairness, where adversaries are rational parties with preferences for specific outcomes, seeking to bias the coin in their favor. Yet these preferences may encode secret information, making prior protocols that assume preferences are public, fundamentally incompatible with privacy.

We initiate a comprehensive study of privacy-preserving game-theoretically fair coin-tossing, where the preferences of honest parties remain private. We propose a simulation-based security framework and a new ideal functionality that reconciles both preference-privacy and game-theoretic fairness. A key ingredient is a certifying authority that authenticates each party’s preference and publishes only aggregate statistics, preventing misreporting while hiding parties' preferences. The functionality guarantees that every honest party receives an output: either a uniform coin; or, if an adversary deviates, a coin that strictly decreases the adversarial coalition's expected utility.

Within this framework, we construct a protocol realizing our ideal functionality under standard cryptographic assumptions that works for both binary and general $m$-sided coin-tossing. Our schemes tolerate the same optimal (or nearly optimal) corruption thresholds as the best known protocols with public preferences (Wu-Asharov-Shi, EUROCRYPT '22; Thyagarajan-Wu-Soni, CRYPTO '24). Technically, our protocols combine authenticated preferences with an anonymous communication layer that decouples identities from preference-dependent actions, together with a deviation-penalty mechanism that enforces game-theoretic fairness.

Our work is the first to reconcile game-theoretic fairness with preference privacy, offering new definitional tools and efficient protocols for rational multi-party computation in dishonest majority settings.

The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these ''sieving steps'' sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098 d}$ to $2^{0.2846 d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby ''center points'' to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.

Secure two-party computation (2PC)-based privacy-preserving machine learning (ML) has made remarkable progress in recent years. However, most existing works overlook the privacy challenges that arise during the data preprocessing stage. Although some recent studies have introduced efficient techniques for privacy-preserving feature selection and data alignment on well-structured datasets, they still fail to address the privacy risks involved in transforming raw data features into ML-effective numerical representations.

In this work, we present ALIOTH, an efficient 2PC framework that securely transforms raw categorical and numerical features into Weight-of-Evidence (WoE)-based numerical representations under both vertical and horizontal data partitions. By incorporating our proposed partition-aware 2PC protocols and vectorization optimizations, ALIOTH efficiently generates WoE-transformed datasets in secret. To demonstrate scalability, we conduct experiments on diverse datasets. Notably, ALIOTH can transform 3 million data samples with 100 features securely within half an hour over a wide-area network. Furthermore, ALIOTH can be seamlessly integrated with existing 2PC-based ML frameworks. Empirical evaluations on real-world financial datasets show ALIOTH improves both the predictive performance of logistic regression and 2PC training efficiency.