International Association
for Cryptologic Research

A pair of differences $(x,y)$ is a \emph{related differential} for a linear layer $M$ if, for every coordinate at both the input and the output, at least one of the two values vanishes or the two values coincide. Related differentials underlie the zero-difference attack on AES of Bardeh and Rijmen, and the question of which maximum distance separable (MDS) matrices admit them was raised by Daemen and Rijmen, who showed that every $4\times4$ circulant MDS matrix does while some Hadamard ones do not. In earlier work we characterized the $3\times3$ MDS matrices over $\mathbb{F}_{2^r}$ admitting related differentials by fifteen explicit equations. In this paper we settle the $4\times4$ case completely: an MDS matrix $M=DNE$ over $\mathbb{F}_{2^r}$ admits a related differential if and only if at least one of $280$ explicit polynomial equations in the nine free entries of its reduced form $N$ holds. The equations, $70$ quadratic and $210$ cubic, are pairwise distinct, irreducible and pairwise coprime, and fall into $27$ orbits under the natural symmetries. We further determine the structure of the equation set: the fifteen equations of the $3\times3$ case are exactly the points of $\mathrm{PG}(3,2)$, while the $280$ equations span a $14$-dimensional $\mathbb{F}_2$-space, satisfy exactly $560$ additive relations, and contain exactly $840$ pairs that can never hold simultaneously on an MDS matrix. The discarded zero patterns split into $525$ whose determinant condition is equivalent to the failure of MDS-ness and $289$ vacuous cases. Over $\mathbb{F}_8$, the smallest field carrying $4\times4$ MDS matrices, exhaustive enumeration shows that there are exactly $720$ reduced MDS matrices; each satisfying exactly $28$ of the equations and each equation being satisfied by exactly $72$ matrices; in particular every $4\times4$ MDS matrix over $\mathbb{F}_8$ admits a related differential. Over $\mathbb{F}_{2^{10}}$ we exhibit an explicit MDS matrix admitting none. All results are verified by exact computation against an independent exhaustive search.

GPU Tensor Cores, specialized hardware units designed to accelerate matrix multiplication, have served as the primary engine behind the AI revolution. Given the exponential performance gains they have delivered, aligning cryptographic implementations with this hardware evolution is critical. This is particularly acute for zero-knowledge proofs (ZKPs), a cryptographic primitive that currently grapples with high proof generation costs. Existing GPU implementations for ZKPs rely exclusively on general-purpose SIMT cores, leaving the massive computational power of Tensor Cores untapped.

In this paper, we introduce TensorZKP, the first GPU framework to harness Tensor Cores for ZKP acceleration. Since Tensor Cores are designed for low-precision matrix multiplication, mapping ZKP's arithmetic to this hardware is non-trivial. To bridge this gap, we develop Tensor-Core-compatible finite field arithmetic and reformulate ZKP modules, specifically sum-check protocols and Spielman code, into matrix multiplication tasks. Furthermore, we design an asynchronous warp-specialized framework that pipelines memory access, Tensor Core matrix operations, and SIMT-based modular reductions. We instantiate these optimizations with HyperPlonk as the Polynomial Interactive Oracle Proof (PIOP) and Brakedown as the Polynomial Commitment Scheme (PCS) to enable end-to-end proof generation.

The evaluation results show that TensorZKP exhibits remarkable efficiency. At a $2^{25}$ scale, the underlying building blocks complete in $0.85$ ms for inner product, $0.91$ ms for scalar-vector multiplication, $4.04$ ms for degree-2 sum-check, and $11.58$ ms for the encoder. For a circuit with $2^{25}$ multiplication gates, TensorZKP achieves a proof generation time of only $215.28$ milliseconds, representing a $955\times$ speedup over the CPU baseline and a $36.2\times$ improvement over state-of-the-art SIMT-based GPU implementations.

Shift-invariant maps have been employed to design nonlinear layers in many symmetric cryptographic schemes, such as the $\chi$-map used in Keccak. In this paper, we study the shift-invariant maps on $\mathbb{F}_2^n$, whose defining functions come from a family of $n$-variable Boolean functions induced by a bifix-free sequence $\underline{a}=(a_1,a_2,\ldots,a_m)\in \mathbb{F}_2^m$ with $2\leq m

Anonymous tokens with private metadata bit (ATPM) allow an issuer to embed a hidden trust flag, as a single bit, within issued tokens. The bit remains hidden from the clients, but verifiers can read the bit and rate-limit or discard tokens marked suspect. A series of ATPM constructions exist in the literature, however all current constructions rely on classical hardness assumptions such as RSA groups, pairings, or elliptic-curve VRFs and do not provide any post-quantum security guarantees.

In this work we present, the first ATPM scheme based on lattice assumptions. Tokens generated with our scheme are publicly verifiable, and privately bit-extractable given partial knowledge of the issuing authority's secret. Our design follows the Fischlin blind-signature paradigm and enriches it with lattice-based linearly-homomorphic encryption to carry the hidden bit.

We also instantiate our scheme from Falcon-512 and the efficient LNP22 lattice NIZK proof system (Lyubashevsky et. al, Crypto '22). The resulting protocol, which we call $\textsf{Atlantis}$, requires 70 KB of client-issuer communication and yields 129 KB tokens.

Session is a widely deployed decentralized messenger application that emphasizes user anonymity and privacy through end-to-end encryption. Session currently employs its own uniquely designed messaging protocol, Session Protocol V1, having migrated from the extensively studied Signal Protocol. In this paper, we conduct a comprehensive, implementation-driven security analysis of the Session Protocol V1, focusing on its 1-to-1 and closed-group communication mechanisms. Our analysis reveals two fundamental design vulnerabilities: the absence of mutual public key authentication and the lack of cryptographic bindings to monotonic sequence counters. Exploiting these weaknesses within the context of actual application environments, we demonstrate three practical attacks: an impersonation attack, a message timestamp forgery attack, and message dropping and replay attacks. These attacks allow malicious server nodes or unprivileged malicious insiders to substitute public keys, silently suppress or duplicate messages, and manipulate the perceived chronological order of conversations. The findings highlight that these exploits severely undermine the fundamental security guarantees of the messenger. Finally, we propose immediate, actionable mitigation strategies to address the identified flaws and secure the protocol against these threats.

Leakage-resilient rekeying schemes aim to maintain cryptographic security in the presence of side-channel leakage by periodically refreshing ephemeral keys before sufficient information can be accumulated by an adversary. Fallen Sanctuary (LR4) is a recent higher-order leakage-resilient rekeying construction that achieves exponential security amplification with respect to the number of primitive encryption invocations and the number of traces required to compromise the physical security of the implementation. Its security, however, relies on the correct maintenance of internal counters and cached intermediate keys that enforce the prescribed trace bounds. In this work, we investigate the security of LR4 under a combined fault and side- channel attack model. We show that transient faults targeting the counter-update and counter-validation mechanism can prevent the advancement of the rekeying state, causing repeated reuse of temporal keys that are intended to be short-lived. As a consequence, the bounded-trace assumptions underlying the LR4 security proof no longer hold. We demonstrate that an adversary can accumulate an arbitrary number of leakage traces corresponding to the same secret state, effectively reducing the security of the protected primitive to that of a conventional implementation without rekeying. We evaluate the attack on a fault simulated implementation and analyze its impact on the leakage-resilience guarantees claimed by LR4. Our findings emphasize that leakage-resilient rekeying schemes must consider fault- induced violations of state evolution assumptions in addition to conventional side- channel leakage.

In non-synchronous networks, classic partition arguments imply that any $t\text{-resilient}$ protocol among $n$ parties cannot ensure safety for many meaningful functionalities once the number of corruptions reaches $f \geq n - 2t$. This motivates building in accountability to detect (and deter) safety violations.

We present the first accountable asynchronous MPC (AAMPC) protocol that securely evaluates any arithmetic circuit $\mathcal{C}$ (asynchronously computable by a trusted third party). Our protocol:

(1) Ensures all target hyperproperties (correctness, privacy, input-independence, and guaranteed output delivery) whenever $f \leq t < n/3$.

(2) Provides strong accountability for $f \in (t,\,t_{\mathrm{acc}}]$ with $t_{\mathrm{acc}} < n - t$: either (i) all hypersafety properties continue to hold (without guaranteed output delivery), or (ii) every honest party obtains publicly verifiable evidence implicating at least $n - 2t$ faulty processes. The construction follows the standard offline/online paradigm and assumes only a transparent setup: a bulletin-board public key infrastructure (PKI) and a common random string (CRS).

Our main technical contribution is an accountable additively homomorphic high-threshold asynchronous complete (verifiable) secret sharing functionality with amortized linear communication for both sharing and reconstruction. This yields an efficient online phase with $O\big(\mathsf{Depth}(\mathcal{C})\big)$ latency and amortized $O(|\mathcal{C}|n)$ communication.

We additionally provide a constant-round offline phase with cubic communication per generated Beaver triple.

Our results are formalized and proven in the Accountable Universal Composability (AUC) framework (S&P 2023), an extension of UC designed to support modular analysis of accountability guarantees.

Evaluating the quantum security of elliptic-curve cryptosystems requires precise resource estimations for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) on fault-tolerant quantum hardware. In monolithic implementations of Shor's algorithm, the required number of logical qubits remains a formidable constraint, primarily dictated by the modular inversion subroutine during point addition. To overcome this architectural limitation, we adapt a recently proposed distributed quantum discrete logarithm framework to the elliptic curve setting and conduct a comprehensive resource estimation. The algorithm decomposes the global scalar search space into compact candidate subsets, verifying whether the secret scalar is contained within a given window via a classical dichotomy-driven coordinator. Remarkably, this distributed approach requires no quantum communication between nodes, operating entirely with minimal classical communication overhead, while reducing the necessary control register width. By incorporating the state-of-the-art, space-efficient reversible modular inversion circuits of Luo et al. (2026), we achieve a dual compression of the quantum memory footprint. Our analytical and concrete resource benchmarks demonstrate that the single-node logical qubit requirement for breaking a cryptographically relevant 256-bit curve drops to between 1080 and 1140 qubits. This represents a substantial reduction below existing monolithic baselines and establishes the lowest logical qubit threshold per processing node for distributed quantum cryptanalysis reported to date.

Digital library lending is a critical resource for access to information. Currently prevalent models of digital lending, however, involve opaque licensing schemes that entail serious drawbacks to reader privacy and freedom of expression. In popular modern library apps, publishers and hidden intermediaries control a wealth of informa- tion about readers and reading habits, at a scale and level of detail that would be essentially impossible in physical library lending.

To understand digital lending needs in practice, our work begins with a series of interviews with library professionals (?= 11). We present thematic findings on their concerns with existing systems, including privacy, surveillance, preservation, and lack of library control over resources. Many of the concerns raised are inherently unproblematic in the context of physical library lending—leading us to our central technical question: Can digital lending achieve privacy and transparency at least as strong as physical library lending?

Based on our qualitative findings, we provide the first rigorous modeling of security, privacy, and transparency requirements in digital library lending. As existing systems fall short of the strong guarantees we model, we propose a new system design, LendLocked, based on cryptography and trusted hardware, and prove it achieves these guarantees in the random oracle model. We micro-benchmark our design’s key cryptographic functionalities, s

Constant time programming patterns is the primary defense against timing attacks on cryptographic implementations, yet what "constant time" means varies across academia and industry. This work systematizes constant time models and their evolution, identifies a recurring gap between what models protect and what specifications assume, and distills an offensive methodology for discovering timing vulnerabilities that originate outside the cryptographic primitive boundary. Applying this methodology, we locate a specification-level vulnerability related to private key loading, and confirm the leak in both OpenSSL and BoringSSL. Counterintuitively, BoringSSL's per-observation signal is several orders of magnitude stronger than OpenSSL's, despite an explicitly stricter threat model.

We argue that if the message expansion code of SHA-1 is replaced by a linear code with a better minimum distance, then the resulting hash function is collision resistant. To support this argument, we characterize the disturbance vectors which are used to build local collision attacks as a linear code. This linear code is the xor-sum of two codes, the message expansion code and a linear code representing the underlying block cipher in SHA-1.

We also show that the following constraint satisfaction problem is NP-hard. The constraints are restricted to being XOR constraints, or Majority constraints on at most three variables each. The instances are further restricted by requiring that the constraints can be listed in a sequence C_1, C_2,...,C_m, such that for every constraint C_i, two of the variables in it occur only in constraints C_j, with |j-i|< 48. This problem is similar to the problem modeling the one-way function property of SHA-1.

Following the cryptographic security analyses of proof-of-work (PoW) blockchain protocols, a line of research has focused on their economic robustness. The two core questions asked are: How resilient is the system to rational attacks, and how profitable it is for miners to execute it. However, to our knowledge, no work to date has attempted to address them considering the full complexity of the blockchain protocol, including difficulty readjustment, which is needed to handle dynamic participation, price fluctuations, and the impact of risk.

In this work, we provide a fine-grained game-theoretic analysis for Nakamoto-style PoW blockchains, which takes into account both incentives of parties to deviate and complications introduced by difficulty readjustment. Our results employ the Rational Protocol Design framework of Garay et al. [FOCS’13] and extend recent works on the economic robustness of the Bitcoin backbone protocol to the variable difficulty setting.

Notably, our fine-grained specification of miners’ utility incorporates variable difficulty adjustment alongside factors like the average cost of mining and the depreciation factor, which, despite being common in economics, are typically either abstracted as exogenous parameters or ignored in the blockchain literature. We showcase the expressivity and usefulness of our formulation of utilities by using it to provide estimates and trends for such factors across several real-world cryptocurrencies.

FESTA is an isogeny-based trapdoor function proposed as a high-performance alternative in isogeny-based cryptography. Its core design principles have inspired a number of related constructions, collectively referred to as FESTA variants.

The MOXZ attack is an adaptive attack that exploits malicious ciphertexts together with access to a checking oracle, aiming to compromise FESTA and its variants. This attack applies to FESTA variants whose secret keys are derived from isogenies of known degree; however, it does not extend to variants employing masked-degree isogenies.

In this work, we present a novel adaptive attack that generalizes the MOXZ attack. Our attack successfully targets several FESTA variants even when their secret keys are isogenies of masked degree. We also identify POKE-4D as an exception for which our attack does not appear to be applicable.

Shuffle differential privacy (shuffle DP) offers an attractive distributed alternative to standard differential privacy. It uses a secure shuffler to permute users' randomized encodings, providing individual data privacy without a central trusted entity. A key challenge, however, is to achieve both generality and client efficiency. Under information-theoretic shuffle-DP guarantees, protocols that nearly match central-model utility are restricted to statistical tasks such as summation and histograms. In contrast, in the computational setting, additive randomized encodings (ARE), introduced by Halevi et al. (CRYPTO 2023), yield a generic compiler that achieves central-model utility for arbitrary mechanisms. However, their construction incurs prohibitive worst-case computation and communication costs for clients, making it impractical for resource-constrained devices such as mobile phones, IoT sensors, and web browsers.

In this work, we present a client-efficient one-round compiler from central DP to non-robust computational shuffle DP. To achieve this, we first construct a new balanced ARE scheme, where all the clients almost equally share the computational burden in the protocol. For a mechanism $M$ over $n$ clients, this reduces the worst-case per-client computation from $O(|M|)$ in prior work to $O(|M|/n)$, where $|M|$ denotes the circuit complexity of the mechanism. The key technical ingredient is a new permute-XOR ARE primitive that enables wire splicing across independently generated garbled subcircuits. Secondly we design a more efficient ARE-to-shuffle compiler, whose client bandwidth scales with the sparsity and cross-partition structure parameter of the ARE encoding - a quantity that is always sublinear in $n$. This is an improvement over Halevi et al. (CRYPTO 2023) where each client bandwidth is $\Omega(n)$. At a high level, the first contribution improves client computation while the second improves client bandwidth.

We provide an implementation of our generic compiler for differentially private tasks including selection, distinct elements, and linear contextual bandits. We obtain shuffle protocols that match the utility of their central-model counterparts with reasonable client overhead. We evaluate our method across a range of practical settings, and observe substantial gains over the compiler of Halevi et al., with per-client computational and bandwidth speedups increasing linearly in the number of clients.

We revisit the problem of mitigating information leakage in the widely used but insecure compress-then-encrypt paradigm. While encryption hides message contents, the ciphertext length is directly related to the length of the compressed message, which may, in turn, leak information about the {\em content} of the message itself. Recent work of Blocki et al. (TCC 2025) proposed an $(\varepsilon,\delta)$-differentially private approach that adds randomized padding calibrated to the global sensitivity of the compression algorithm, and showed that the global sensitivity of LZ77 is $O(W^{2/3}\log n)$, where $n$ is the input length and $W$ is the sliding window size.

However, prior analysis focused only on sensitivity with respect to single-character edits, which leads to limited privacy guarantees when protecting longer substrings such as passwords, passphrases, cookies, or confidential user records. A natural attempt to handle longer secrets is to appeal to group privacy, but for approximate differential privacy, this leads to very poor parameter degradation: in particular, the effective value of $\delta$ can grow exponentially with the group size $g$. In this work, we introduce and study the sensitivity of compression schemes under block edits. Specifically, we define two strings to be $g$-neighbors if they differ only within a contiguous interval of length $g$.

Our main technical contribution is a nearly tight characterization of the $g$-consecutive sensitivity of LZ77. We show that the $g$-consecutive sensitivity of both LZ77 variants (with and without self-referencing) is at most $O((W^{2/3}+g+\sqrt{Wg})\log n)$. In particular, when $g \leq W^{1/3}$, the bound simplifies to $O(W^{2/3}\log n)$, matching the known bound for single-character edits. Thus, calibrating noise to the single-character sensitivity of LZ77 already suffices to protect much longer contiguous substrings. We provide matching lower bounds to demonstrate that our upper bound is tight, e.g., when $n=W=O(g^2)$, the $g$-consecutive sensitivity of LZ77 is at least $\tilde{\Omega}(g^{1.5})$, matching the $\sqrt{Wg}=O(g^{1.5})$ term from our upper bound up to a logarithmic factor.

Secure Multi-Party Computation (MPC) enables private computation, but has significantly higher overhead than plaintext execution. Hybrid MPC compilers improve concrete efficiency by mapping distinct computation parts to contextually optimal MPC protocols. However, state-of-the-art systems like Silph (Chen et al., S&P’23) depend on deployment-specific cost models that are cumbersome to retune, and compute mappings via brittle heuristics or costly Integer Linear Programming (ILP), limiting scalability and portability across protocols and deployment settings.

We present SING, the first machine-learning-based framework for hybrid MPC share assignment. SING leverages Graph Neural Networks (GNNs) for: (1) imitation of Silph’s assignments, accelerating share assignment by up to $76,697\times$ with comparable quality; and (2) cost-driven learning, where we train a GNN cost predictor on synthetic or empirical costs (e.g., runtime or communication), freeze it, and train the share-assigning GNN to minimize predicted costs. The latter supports expressive non-linear cost models, avoiding ILP's linearity constraints, and enables retargeting to new protocol suites and deployment settings by re-fitting the predictor. Finally, we release our synthetic benchmark resources, including a dataset of 704 MPC circuits with wide-ranging hybrid assignments.

In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then independently send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. The PSM setting was introduced as a minimal model for secure multiparty computation. In the quantum setting, PSM has been related to non-local quantum computation (NLQC), and has several connections to the complexity of Boolean functions. The communication and correlation cost of implementing private simultaneous message passing may be much larger than the cost without privacy, and the cost of privacy in this setting remains poorly understood. Here, we give new upper and lower bounds on the PSM model, in both the quantum and classical settings. Concretely, we prove two lower bounds:

1) Nečiporuk's measure lower bounds the entanglement required for $k$-player quantum PSM with perfect correctness. This can be evaluated to give quadratic lower bounds for some explicit functions. 2) The rank of the communication matrix of $f(x_1,x_2)$ lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness.

When allowing both quantum communication and shared entanglement, these two bounds are the first lower bounds on quantum PSM that make use of the privacy condition. Regarding upper bounds, we show:

1) Letting $s$ be the size of a quantum circuit computing $f$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $\epsilon$ the correctness parameter of the PSM protocol, we obtain the upper bound $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O( d_f)}(s/\epsilon)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$.

In proving the first upper bound, we also generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones. These generalizations may be of independent interest.

We introduce the Huffman-Merkle Tree (HMT), an authenticated data structure (ADS) optimized for dynamic workloads where some items may be more frequently accessed than others, and access frequencies change over time. An ADS allows proving item membership against a short commitment to a large mutable state, with applications including verifiable storage, Internet transparency services, and blockchains. Optimizing ADS performance under continuously changing access frequencies has not been fully addressed before, neither in theory nor in practice. HMT tackles access skew via tiering: "hot" items are stored according to a Huffman coding layout where frequently accessed items are closer to the root and thus contribute less to overall costs, while a binary Merkle Tree (MT) is used for cold and new elements to lower their update overhead. To efficiently handle dynamic workloads, we incrementally apply and batch layout changes, track access frequencies via count-min sketch, use a tier promotion cache, and consider various tier migration policies. We implement HMT and compare it on real-world data against Ethereum's Merkle Patricia Trie (MPT) ADS and its proposed replacement, the Unified Binary Tree (UBT). Our evaluation considers two metrics: the amount of hashing per ADS update and access-weighted membership-proof size. The latter metric captures both the cost of accessing each item and its access frequency. We find that the best HMT policy uses about 2.4x and 0.34x less average hash operations than MPT and UBT respectively, while featuring proofs shorter by 0.18x than MPT and 0.55x than UBT.

Modern consensus protocols often aspire to be responsive---that is, to confirm transactions in time proportional to the actual network delays as opposed to a (typically much larger) worst-case bound on network delays. Responsiveness can yield substantial practical improvements in both protocol latency and throughput.

In blockchain settings, however, block proposers commonly have economic incentives (most notably MEV) to delay their blocks, a phenomenon repeatedly observed in practice, e.g., in the block production supply chains for Ethereum and Solana. Such incentives clash with responsiveness in existing protocol designs.

This paper develops a rigorous framework for designing incentive-compatible responsive consensus protocols. We first consider the canonical case of single-leader protocols and establish feasibility results characterizing the conditions on the distribution of network latency under which responsiveness can be incentivized through a suitable reward function. We further quantify the amount of stake required from the leader to deter dishonest delays.

We then show strong positive results for protocols with multiple leaders, demonstrating that the multi-leader approach is fundamentally superior to single-leader designs for resolving the tension between responsiveness and incentive-compatibility: by forcing leaders to compete for rewards, much of the burden otherwise placed on the incentive mechanism is alleviated. Notably, this results in simpler reward mechanisms with no stake requirements that also remain feasible in parameter regimes which are provably impossible under a single leader.

In this paper, we demonstrate a way to generalize learning with errors (LWE) to the family of so-called modular-maximal cyclic groups which are non-commuting. Since the group $\mathbb{M}_{2^t}$ has two cycles of maximal multiplicative order, we use this fact to construct an accurate criterion for restoring the message bit with overwhelming probability. Furthermore, we implement the original idea by O. Regev in the considered group to gain benefits from the non-commutativity of $\mathbb{M}_{2^t}$. Also we prove that using this approach we can achieve a level of security comparable to the original idea.