International Association
for Cryptologic Research

Arithmetic correlation is a critical performance measure for pseudorandom sequences generated by feedback with carry shift registers (FCSRs), extending classical correlation by accounting for carry propagation. Chen et al. proved that for binary sequences with coprime periods, the arithmetic crosscorrelation is constant, and established bounds for Legendre sequences and $m$-sequences. In this paper, we further investigate the arithmetic crosscorrelation of sequences with coprime periods. We derive upper bounds for sequences constructed from the Legendre symbol, which generalize classical Legendre sequences, and for sequences generated by trace functions. In addition, we show that the constant property of arithmetic crosscorrelation extends to non-binary sequences with coprime periods.

Recent MPC-in-the-Head techniques enable the construction of signature schemes with compact signature sizes from various hardness assumptions. These techniques rely on commitments based on GGM trees, which have been optimized to further reduce the signature size with the so-called one-tree or correlated tree optimizations. While the one-tree technique has no incidence on the security of the scheme, this is not obvious for the correlated tree technique, and a formal security analysis of this technique has been missing in the literature.

In this work, we fill this gap and provide the first formal security analysis of MPC-in-the-Head signature schemes based on correlated trees. We first exhibit a potential security flaw of this technique which rules out any hope for a security reduction to the underlying hardness assumption. In particular, we show that recovering the first $\lambda$ bits of the secret witness is sufficient to achieve a full key recovery (where $\lambda$ is the security level). The underlying assumption should hence be such that recovering these $\lambda$ bits is as hard as recovering the full witness. Some state-of-the-art schemes do not satisfy this condition, which prevents a direct application of the correlated tree technique.

We then provide a formal security proof for signature schemes based on the correlated tree technique under this degraded hardness assumption. Our proof comes in several variants, in the random oracle mode or in the ideal cipher model, depending on the specific correlated tree construction. We also introduce a tweak for the instantiation of the leaf seed expansion in the ideal cipher model, which allows us to achieve a tighter security reduction. Our result shows that MPC-in-the-Head signatures based on correlated trees can achieve strong security guarantees and provides the first formal security proof for the MQOM v2 signature scheme, the on-going candidate in the NIST post-quantum standardization process with the shortest signature size in the MPC-in-the-Head family.

This paper extends the Kikuchi method to give algorithms for decisional $k$-sparse Learning With Errors (LWE) and $k$-sparse Learning Parity with Noise (LPN) problems for higher moduli $q$. We create a Kikuchi graph for a sparse LWE/LPN instance and use it to give two attacks for these problems. The first attack decides by computing the spectral norm of the adjacency matrix of the Kikuchi graph, which is a generalization of the attack for $q=2$ given by Wein et. al. (Journal of the ACM 2019). The second approach computes non-trivial closed walks of the graph, and then decides by computing a certain polynomial of edge labels in the walks. This is a generalization of the attack for $q=2$ given by Gupta et. al. (SODA 2026). Both the attacks yield new tradeoffs between sample complexity and time complexity of sparse LWE/LPN.

For decades, verifiable election systems have typically relied on encrypting ballots to maintain voter privacy. Encryption re- quires keys, and the management of these keys is usually one of the most cumbersome and error-prone components of the system. But in-person elections—where one or more devices are used to each collect many votes—can use cryptographic commitments rather than encryption and completely obvi- ate the need for cryptographic keys, leading to solutions that are much simpler and more robust than the encryption-based approaches. Currently deployed E2E-verifiable voting systems also pro- duce large election records, which can sometimes become an obstacle to election verification, by increasing the cost of hosting, distributing, and verifying election data. Using modern techniques for compact ZK proofs, Haechi improves on past commitment-based and encryption-based solutions by drastically reducing the size of the election records, leading to improvements of over an order of magnitude compared to several real-world deployments.

The Learning with Errors (LWE) problem is a hard math problem in lattice-based cryptography. In the simplest case of binary secrets, it is the subset sum problem, with error. Effective ML attacks on LWE were demonstrated in the case of binary, ternary, and small secrets, succeeding on fairly sparse secrets. The ML attacks recover secrets with up to 3 active bits in the "cruel region" (Nolte et al. 2024) on samples pre-processed with BKZ. We show that using larger training sets and repeated examples enables recovery of denser secrets. Empirically, we observe a power-law relationship between model-based attempts to recover the secrets, dataset size, and repeated examples. We introduce a stepwise regression technique to recover the "cool bits" of the secret.

DATA [22] and Microwalk [23] are two advanced dynamic binary instrumentation (DBI) tools for detecting constant-time (CT) violations in software implementations. This paper presents a comparative evaluation of these tools' findings using a common test setup and several cryptographic implementations that are included in the libraries LibTomCrypt, OpenSSL, and liboqs. Our experiments yield reliable results for symmetric ciphers. For asymmetric cryptographic schemes, however, internal random numbers cause a high number of reported findings that also differ among the tools. In order to make the tools' results more comparable our test setup is adapted to externally inject random numbers that are otherwise generated internally by the cryptographic libraries. We discuss the differences of the tools' design and their impact on practical results of cryptographic implementations as well as their resource consumption in terms of memory and runtime.

By construction, Fully Homomorphic Encryption schemes have probabilistic correctness due to their underlying cryptographic assumptions. The family of Learning With Errors (LWE) problems assumes that a random error term is added during encryption. Statistically, this error grows as homomorphic computation proceeds. While predicting the noise evolution was initially only a correctness issue, recent works have shown a direct link with the security of FHE schemes in the IND-CPA-D model. Here, we present a framework that provides practical guarantees that the probabilities extrapolated from theoretical models satisfy bounds as small as $2^{-128}$. We show how to obtain strong experimental guarantees that the usual Gaussian model for noise is conservative and that a refined model based on Irwin-Hall distribution is valid. This is realized through an algorithm called importance splitting, which we adapt here to the cryptographic setting. We provide a detailed study in the context of TFHE bootstrapping and its variants. We believe our framework can serve as a baseline to be extended to other schemes, thereby ensuring both correctness and security across all FHE schemes.

Blockchains intend to provide long-term integrity guarantees through cryptographic primitives that may become vulnerable over time due to algorithmic advances or paradigm shifts such as quantum computation. While cryptographic agility, the ability to transition between algorithms without disrupting operation, is recognized as essential, existing blockchain systems lack comprehensive support for such transitions. We address this gap by designing an Ethereum virtual machine (EVM) compatible blockchain that introduces support for cryptographic agility from genesis. We first propose a flexibility framework that characterizes how algorithm choice can be distributed across blockchain components. We then present two technical contributions aligned with this framework: (1) cryptographically agile transactions (CATX), a new transaction format that decouples body and signature to enable user-selected signature schemes; and (2) a consensus-layer key registration mechanism that allows validators to migrate between signature schemes as operational upgrades without hard forks. We exemplify the agility of our design with ECDSA, Falcon-512, and ML-DSA signatures by conducting experimental evaluations over 30,000 blocks and 11 million transactions, showing that the CATX format introduces no measurable overhead.

The bottleneck complexity of a (secure) multiparty computation protocol is one measure of its communication-efficiency. It captures how well the communication load is balanced, and is defined as the maximum communication complexity required by any one party within the protocol execution.

Prior works on this topic restricted attention to protocols with fixed communication graphs, i.e. whether or not a given party communicates to another only depends on the round number.

We demonstrate the power of adaptively choosing communication graphs by developing various bottleneck-efficient protocols, both with and without security. Done naÏvely, protocols with adaptive communication graphs can exploit unnatural tricks, such as "communicating with silence." To ensure our protocols are meaningful, we additionally stipulate that they should run correctly even in asynchronous networks (where we make no assumption on the adversarial message-delays other than being finite).

[Bottleneck complexity of arbitrary functions.] With fixed communication graphs, Boyle, Jain, Prabhakaran, and Yu (ICALP'18) established the existence of a function $f\colon\{0,1\}^n\to\{0,1\}$ requiring $\Omega(n)$-bit bottleneck complexity, which is matched by the trivial protocol of having all parties send their inputs to one party. By adaptively choosing communication graphs, we show that any function $f\colon\{0,1\}^n\to\{0,1\}$ can be computed (securely) with bottleneck $O(n/\log n)$ (which we prove is essentially optimal), even in \emph{asynchronous} networks.

[Bottleneck complexity of symmetric functions.] Prior works have demonstrated that special classes of symmetric functions, such as additive [Eriguchi, Asiacrypt'23] or abelian [Keller, Orlandi, Paskin-Cherniavsky, Ravi, ITC'23] functions can be computed bottleneck-efficiently with fixed communication graphs. We both expand the class of symmetric functions achievable with low bottleneck complexity, as well as show how input-adaptive communication graphs can be leveraged to further reduce the bottleneck complexity of some of our protocols.

The security of lattice-based cryptography relies critically on the concrete hardness of the approximate shortest vector problem (Approx-SVP). For cryptographic-sized instances, existing Approx-SVP rank reduction conditions may be overly aggressive, as they implicitly assume access to a large number of extremely short lattice vectors. In this work, we systematize and refine Approx-SVP rank reduction conditions from a feasibility perspective. We identify that, in the context of dimension-for-free (D4f) technique, the existence of a single sufficiently short vector is the essential requirement, and we derive two refined and compact rank reduction conditions accordingly. The first condition is based on geometric properties of lattice sieving, while the second incorporates a basis-quality-dependent probabilistic bound. These results are validated through extensive experiments on high-dimensional lattices, where the compact condition outperforms prior methods by up to a factor of $60$ in dimensions $850$ and $925$. To reliably realize these conditions in high dimensions, we present APBKZ, an adaptive Pump-based lattice reduction strategy that dynamically selects the blocksize and dimension-for-free parameters according to the evolving Gram-Schmidt profile. We further introduce HeadAPBKZ, a head-focused execution mode that restricts reduction to a critical prefix once the rank reduction condition is satisfied. Combining these advances, we develop an improved concrete security estimation framework for the MSIS problem. Applied to Dilithium, our analysis indicates that when integrating compact rank reduction behavior with the D4f technique, the estimated concrete security margin of Dilithium drops by 9.50-16.63 bits compared to the conservative Core-SVP baseline, offering more accurate security benchmarks for cryptographic standardization.

Heterogeneous cross-device side-channel attacks remain a critical yet underexplored challenge, as models trained on one device often fail to generalize across architectures. This paper presents PD-Net, a domain generalization framework that learns device-invariant features by disentangling algorithmic content from device-specific style and aligning feature distributions using prototypical and Maximum Mean Discrepancy (MMD) losses. PD-Net is trained on nine heterogeneous source domains spanning ARM/AVR/FPGA and power/electromagnetic leakage modalities, including 32-bit ARM Cortex-M0/M1/M3/M4, 8-bit AVR ATmega (three series), and 128-bit Xilinx Virtex-5 FPGA, and evaluated in a zero-shot setting without target-specific adaptation. Experimental results demonstrate robust zero-shot cross-architecture transfers between 8-bit and 32-bit devices, with consistent gains over existing generalization and transfer-learning approaches. In particular, PD-Net delivers 29 successful attacks with only 10 divergences across 70 settings, markedly outperforming the state of the art, which succeeds in only 4 cases and diverges 19 times. To the best of our knowledge, this is the first domain generalization (DG)-based deep learning framework to systematically demonstrate practical zero-shot heterogeneous cross-device side-channel attacks.

(Bi-Directional) Proxy Re-Encryption ($\mathsf{PRE}$) is a public-key encryption scheme that allows a proxy, holding a re-encryption key from $i$ to $j$, to transform a ciphertext intended for $i$ into one intended for $j$. $\mathsf{PRE}$ has numerous applications, including secure data sharing and cloud computing. However, most existing $\mathsf{PRE}$ schemes experience significant security degradation when adversaries are allowed to adaptively corrupt re-encryption or secret keys. Prior to this work, only a few $\mathsf{PRE}$ schemes achieved quasi-polynomial security loss in the adaptive setting, and even those were limited to restricted re-encryption strategies.

In this paper, we propose four distinct $\mathsf{PRE}$ schemes with tight security guarantees in the adaptive setting, based on the $\mathsf{MDDH}$ assumption: - $\mathsf{PRE}_0$, $\mathsf{PRE}_1$: Single- and multi-challenge $\mathsf{aHRA}$-secure $\mathsf{PRE}$ schemes with tight security focusing on efficient constructions. - $\mathsf{PRE}_2$, $\mathsf{PRE}_3$: Single- and multi-challenge $\mathsf{aCCA}$-secure $\mathsf{PRE}$ schemes with (almost) tight security focusing on $\mathsf{CCA}$-type security.

To achieve tightly $\mathsf{CCA}$-secure $\mathsf{PRE}$ schemes, we introduce a novel concept called tag-based language-malleable $\mathsf{NIZK}$ with special simulation soundness. This primitive provides simulation-sound $\mathsf{NIZK}$ while preserving a restricted form of malleability. We construct both one-time and unbounded versions of this primitive under the $\mathsf{MDDH}$(Matrix Decisional Diffie-Hellman) assumption.

We describe the methodology and scope of CatCrypt, a library for machine-checked cryptographic security proofs in Lean. CatCrypt provides an end-to-end pipeline from Rust reference implementations to security proofs in the computational model in Lean. The translation from Rust to Lean is done using the Hax tool.

CatCrypt covers 172 cryptographic protocols and constructions with machine-checked security theorems in the computational model. Of these, 110 have the full Rust-to-Lean pipeline. All bounds have been systematically cross-referenced against their published sources (IETF RFCs, NIST standards, and academic papers). Some proofs were ported from SSProve (Rocq), EasyCrypt, ProVerif, CryptoVerif and Squirrel; most are independent formalisations with no prior machine-checked treatment. CatCrypt also includes a verified Lean implementation of a substantial part of the hax transpiler pipeline.

This work is an experiment of what can be done by a researcher working with GenAI. Until recently, the formalization of one protocol required months of expert effort. In contrast, the whole of CatCrypt was developed in a period of two months. Because it was developed with AI, we develop a new methodology to increase confidence that the specifications are correct. Moreover, we will continue to audit the code in the coming months to gain even more confidence in the specification of the results.

We hope this work will facilitate the adoption of formal methods in the development of security-critical software. This is especially urgent due to AI's increased hacking capabilities, the explosion of AI generated software and the ongoing post-quantum transition, which requires the development of new cryptographic protocols and their secure implementation.

Heavy-hitter detection is a fundamental primitive in stream analytics, with applications in network monitoring, telemetry, and large-scale data systems. In many practical deployments, this computation must be maintained continuously on remote infrastructure that offers higher availability and centralized operational control, even when the underlying streams contain sensitive identifiers or proprietary activity patterns. Existing privacy-preserving approaches either incur substantial statistical noise or rely on multi-server trust assumptions. Fully Homomorphic Encryption (FHE) offers an attractive alternative by enabling exact computation over encrypted data on a single untrusted server, but the high cost of encrypted comparisons has historically made stateful stream processing impractical.

We present Oblivious SpaceSaving, a privacy-preserving reformulation of the classical Space-Saving algorithm for fully encrypted execution. Our central idea is the Moving Floor abstraction, which exploits a monotonicity invariant in the summary state to replace repeated magnitude comparisons with equality-based selection against a tracked encrypted floor. We further combine this with parallel victim selection and a hierarchical asynchronous ingestion pipeline, yielding an end-to-end encrypted heavy-hitter architecture that preserves the deterministic accuracy guarantees of the original algorithm.

Our design reduces the cost of encrypted updates by up to $2.74\times$ over a naive oblivious baseline and sustains end-to-end encrypted ingestion throughputs of up to 4.30 items/s with sub-second amortized latency. These results show that, with the right algorithmic reformulation, classical streaming summaries can be made practically viable under fully encrypted execution, bringing privacy-preserving stream analytics significantly closer to deployment.

We introduce Confidential Transfers for Multi-Purpose Tokens (Confidential MPTs) on the XRP Ledger, a cryptographic extension of the XLS-33 token standard that enables confidential balances and hidden transfer amounts while preserving public supply verifiability. The protocol replaces plaintext per-account balances with EC–ElGamal ciphertexts and employs non-interactive zero-knowledge proofs to enforce transfer correctness, balance sufficiency, and the invariant OutstandingAmount ≤ MaxAmount without requiring decryption by validators. Confidentiality is scoped to transaction amounts and account balances; sender and receiver identities remain public, preserving XRPL’s account-based execution model. Our design maintains full compatibility with existing MPT semantics: public and confidential balances coexist, issuance rules remain unchanged, and theissuer’s designated second account is treated identically to other holders. The protocol further supports issuer-controlled operations, including freeze and clawback, without weakening supply soundness. To accommodate regulatory and institutional requirements, Confidential MPTs provide cryptographic auditability through an on-chain selective-disclosure model based on multi-ciphertext balance representations and equality proofs, while remaining compatible with simpler issuer-mediated audit models. We present a complete protocol specification, a security analysis under standard discrete-logarithm assumptions, and an open-source reference implementation (mpt-crypto) that realizes the required cryptographic primitives. Experimental evaluation demonstrates that confidential transfers can be verified within XRPL validator performance constraints, with proof sizes and verification costs suitable for production deployment.

This paper presents a security evaluation of the RRSC lightweight stream cipher in its 64-bit and 128-bit variants. The analysis examines the key update process, internal component interactions, and diffusion behavior during initialization, supported by an avalanche study. Based on these observations, several cryptanalytic scenarios are explored, including time-memory-data trade-off attacks, full key-recovery attacks in the known-plaintext setting, and partial key-recovery attacks targeting the linear feedback shift register and nonlinear feedback shift register components. It is shown that the effective key space is reduced from \(2^{128}\) to \(2^{96}\) for the 128-bit variant and from \(2^{64}\) to \(2^{48}\) for the 64-bit variant.

We explore distributed training in a setting where features are held by one party and labels are held by another. In this context, we focus on label Differential Privacy (DP), where the labels require privacy protection from the other party who learns the trained model. Previous approaches struggle to train accurate models in high-privacy settings (i.e. when $\epsilon \leq 1$), or typically require a trusted third party. To eliminate this trusted party while preserving model utility, we present PostScale, a novel Homomorphic Encryption (HE)-based protocol suited for high-privacy regimes with ciphertext multiplicative depth of two. Our protocol is suitable for a wide variety of models in the semi-honest setting and avoids leaking the model architecture as well as costly ciphertext operations like bootstrapping and rotations. We also present a multi-party sampling protocol for generating DP noise, and Hadal, a general-purpose dataflow-based framework for encrypted computation implementing our protocols. Hadal repurposes existing tools for use with HE, including comprehensive performance profiling capabilities, dual execution modes (eager and deferred), graph compiler-based optimization, and hyperparameter tuning. Our techniques achieve model utility similar to centralized DP while reducing communication by over 90% (from 1 TB to 8 GB per batch) and training time by 99% (from 54 minutes to 33 seconds) compared to related work that protects both features and labels. These improvements unlock larger models; we train Bert-tiny of Devlin et al. (2019), with 6.5 MB of parameters, in 20 ms per example in a LAN setting.

In code-based cryptography, dual attacks for solving the decoding problem have recently been improved. They are now competitive and beat information set decoders for a significant regime. These recent dual attacks, starting from Carrier et al. (Asiacrypt 2022), work by reducing decoding to an LPN problem where the secret and the noise involve parts of the error vector coming from the decoding problem. However, currently, the analysis of all these dual attacks is heuristic. In the original Asiacrypt 2022 work, a simple LPN modeling was used to carry out the analysis but Meyer-Hilfiger and Tillich (TCC 2023) showed that this assumption could not be used. Consequently, they proposed an alternative analysis based on Fourier theory and on heuristically modeling the weight enumerator of a random linear code as a Poisson variable. The analysis of the newest and most efficient dual attack, doubleRLPN, introduced by Carrier et al. (Eurocrypt 2024) also relies on this technique and on this model.

Our main contribution is to devise a variant of doubleRLPN that we can fully prove without using any model. We show that our variant has the same performance, up to polynomial factors, as the original doubleRLPN algorithm. The final algorithm and its analysis are also simpler. Our technique involves flipping the coordinates of the noisy codeword and observing the fine changes in the amount of noise in the related LPN problem to reconstruct the entire error. The analysis is based on the second-order behavior of the bias of the noise which was already used in the original analysis.

Secondly, the performance of our algorithm, as it was the case for doubleRLPN, heavily depends on having access to a good code along with an efficient decoder. We instantiate this code by choosing a Cartesian product of a constant (instead of sublinear in the original proposal by Carrier et al.) number of random linear codes. We use a decoder based on blockwise error enumeration that was already used by Guo et al. (Asiacrypt 2014). We show that our approach is optimal up to polynomial (instead of superpolynomial) factors.

To penetrate more rounds with Meet-in-the-Middle (MitM) attack, the neutral words are usually subject to some linear constraints, e.g., Sasaki and Aoki's initial structure technique. At CRYPTO 2021, Dong et al. found the neutral words can be nonlinearly constrained. They introduced a table-based method to precompute and store the solution space of the neutral words, which led to a huge memory complexity. In this paper, we find some nonlinearly constrained neutral words can be solved efficiently by Khovratovich et al.'s triangulation algorithm (TA). Furthermore, motivated by the structured Gaussian elimination paradigm developed by LaMacchia et al. and Bender et al., we improve the TA to deal with the case when there are still many unprocessed equations, but no variable exists in only one equation (the original TA will terminate). Then, we introduce the new MitM attack based on our improved TA, called triangulating MitM attack. As applications, the memory complexities of the single-plaintext key-recovery attacks on 4-/5-round AES-128 are significantly reduced from $2^{80}$ to the practical $2^{24}$ or from $2^{96}$ to $2^{40}$. Besides, a series of new one/two-plaintext attacks are proposed for reduced AES-192/-256 and Rijndael-EM, which are the basic primitives of NIST PQC candidate FAEST. A partial key-recovery experiment is conducted on 4-round AES-128 to verify the correctness of our technique. For AES-256-DM, the memory complexity of the 10-round preimage attack is reduced from $2^{56}$ to $2^{8}$, thus an experiment is also implemented. Without our technique, the impractical memories $2^{80}$ or $2^{56}$ of previous attacks in the precomputation phase will always prevent any kind of (partial) experimental simulations. In the full version, we extend our techniques to sponge functions.

Fully homomorphic encryption (FHE) is a cryptographic scheme that can take ciphertexts as inputs and compute a new ciphertext of a function of the underlying messages without decryption. FHE has been attracting attention along with the growing interest in privacy-preserving technologies. In terms of privacy-preserving technology, deniable encryption is also important. Deniable encryption enables a user, who may be forced to reveal the messages corresponding to the user's public ciphertexts, to lie about which messages the user encrypted. Agrawal et al. (CRYPTO 2021) introduced deniable FHE (DFHE) that combines FHE with deniable encryption, and proposed a transformation from an FHE scheme that satisfies specific special requirements, called special FHE, to a DFHE scheme. They also showed a construction of a special FHE scheme based on the BGV (Brakerski--Gentry--Vaikuntanathan) scheme. However, in the construction by Agrawal et al., one must store all the extensive randomness used for encryption in order to lie, and a bootstrapping operation, which takes a long time to execute, is a bottleneck in execution speed. In this paper, we show that by providing a tighter upper bound on deniability, we can reduce the size of the stored randomness and the required number of bootstrapping in the construction by Agrawal et al. In addition, we show that TFHE (Chillotti et al., J. Cryptol., 2020; Joye, CT-RSA 2024), which is known as a FHE scheme with fast bootstrapping, satisfies the requirements of special FHE, and thus can realize a faster DFHE scheme than the BGV-based construction.