International Association
for Cryptologic Research

Private Information Retrieval (PIR), a set of techniques from the literature on cryptography, enables the retrieval of data from a public database while concealing the intent of those querying it, even when the database itself is untrusted. While the scalability of PIR has improved in recent years, its applicability remains limited due to the assumption that databases cooperate with users. PIR schemes usually require the database or website administrators to perform costly operations beyond servicing requests, which they have little incentive to do. In this paper, we introduce a new direction of PIR research that eliminates requirement of any special cooperation from the database and assumes the presence of a strong adversary that controls not only the database but also any third parties involved in the system. We present Zeal, the first `non-cooperative' PIR scheme that defends against a strong adversary. We also implement Zeal on AWS and evaluate its performance. Zeal has roughly three to four minutes of latency for a database with one million records, improving upon the latency of a naive solution by a factor of 50. We also prove and quantify Zeal's security using a differential privacy guarantee.

As efficient proof systems mature rapidly, more practical use cases that require zero-knowledge (ZK) guarantees are arising. Adding ZK typically requires either composing the non-zk base system with an expensive zk one that proves correctness of the cryptographic hashes performed by the base verifier, or alternatively making tightly coupled modifications to every component of the base protocol. We introduce VEIL, a lightweight and non-intrusive compiler for hash-based multilinear proof systems. VEIL achieves ZK without these drawbacks. Our approach decouples the protocol's algebraic interactions from the cryptographic hashing and applies a ZK wrapper solely to the algebraic components. This results in a simple, plausibly post-quantum, protocol that achieves a minimal prover overhead of $(1+o(1))$, while maintaining the architectural integrity of the base proof system. Our proof-of-concept implementation demonstrates that, over a $31$-bit base prime field, for a trace of $2^{29}$ field elements, compared to the non-zk proof system, VEIL has a prover overhead of about $3\%$, verifier overhead of $22\%$ and proof-size overhead of $12\%$.

In this paper we study the cryptographic complexity of non-trivial witness-indistinguishable (WI) arguments of knowledge. We establish that:

- Assuming that $NP\not\subseteq P/poly$, the existence of a constant-round computational WI argument of knowledge for $NP$ implies that (infinitely-often) auxiliary-input one-way functions exist.

- Assuming that $ NP\nsubseteq P^{Sam}/poly$, there is no black-box construction of a constant-round (unbounded-verifier) statistical WI argument of knowledge from one-way permutations. Here, $Sam$ is the collision finder oracle of Haitner, Hoch, Reingold, and Segev [FOCS '07].

Moreover, we identify a natural class of knowledge extractors for which stronger versions of the above implications hold (e.g., even if the protocols have many rounds).

In a previous paper [Shoup 2023], we presented a modular toolkit for analyzing threshold Schnorr signature schemes, built around "enhanced attack modes" in the non-distributed setting. In this note, we revisit the random oracle analysis of the combination of batch randomness extraction with re-randomized presignatures. We make the simulation argument fully explicit --- in particular, giving a careful analysis of what is leaked through the presignatures, the programmed hash values, and the signature values --- and fill in a gap in the treatment of batch re-randomization. We also give a simpler path to tight security bounds in the combined random oracle plus generic group model (ROM+GGM): rather than reducing to somewhat convoluted (if concrete) assumptions about the hash function within the GGM, we reduce in the ROM to an attack on the Schnorr interactive identification scheme, and then observe that the identification scheme is easily seen to be hard in the GGM.

The Ethereum Foundation recently announced the Proximity Prize which aims to resolve some open problems that play an important role in the design of succinct proof systems. This paper reviews the open problems relevant to the Proximity Prize. We focus on some grand challenges relating to list decoding bounds, proximity gaps, correlated agreement, and mutual correlated agreement,as they relate to proof systems and Reed--Solomon codes. Along the way we survey the known results on these topics.

CSIDH (Commutative Supersingular Isogeny Diffie--Hellman) is a class-group-based key-exchange protocol operated on supersingular elliptic curves, which, at the time of its proposal, exhibited several attractive selling points such as non-interactivity. Unfortunately, CSIDH is vulnerable to the sub-exponentiation attack--Kuperberg's algorithm, thereby requiring large parameters to ensure security. A recent work based on oriented elliptic curves with large discriminants, proposed by Houben, allows for a significantly small base field (around 255 bits). We name this protocol CSIDH-LDO. However, the practicality of CSIDH-LDO is currently hindered by the necessity of performing multiple group actions and its huge public-key size.

In this paper, we address these bottlenecks by presenting highly optimized constant-time implementations alongside an effective public-key compression framework for CSIDH-LDO. We combine algorithmic improvements, specifically scalar multiplication by differential addition chains and isogeny computation on the twisted Edwards model, with \textit{limb-slicing} to exploit parallelism via Intel's AVX-512 instructions. To resolve the architectural mismatch when mapping $r \in \{7, 13\}$ group actions to 8-lane SIMD registers, we evaluate two parallel scheduling strategies. While a dummy-based approach allows us to leverage efficient $\mathbb{F}_{p^2}$-arithmetic, our dummy-free strategy systematically exploits internal parallelism to fully saturate the 512-bit vectors without redundant computations. Benchmarks on an Intel Tiger Lake processor demonstrate our parallel implementations achieve speedups of up to 3.40$\times$ (AVX-512F) and 7.30$\times$ (AVX-512IFMA) over an optimized x64 assembly baseline. Furthermore, we establish a formal framework for public-key compression tailored for CSIDH-LDO. Specifically, we propose two efficient techniques that achieve a compact public key representation of approximately $(r+2)\log_2(p)$ bits, thereby significantly reducing communication bandwidth. To the best of our knowledge, this work is the first to demonstrate the efficacy of SIMD parallelization combined with optimized compression for isogeny-based protocols derived from orientations of large discriminants.

We present a new method for merging short computationally sound proofs (SNARGs). Intuitively, this means going from short proofs of two statements to a short proof of a statement that is a ``logical consequence'' of the two.

Our work is the first to handle an unbounded polynomial number of recursive merges with arbitrary topology. Unlike prior works, the running time of our security reduction grows only with the depth of the merging process, and not with the associated ``tree size", which could be exponentially larger.

Our method is only applicable to so-called ``trapdoor languages'', where the validity of a statement can be decided in polynomial time given a trapdoor. Importantly, this trapdoor needs not be known for generating or verifying proofs, and is only used in the security reduction. We present constructions from sub-exponential iO and from LWE, where the former yields fully compact proofs, while in the latter the proof size scales with the depth of the merging process.

We show the usefulness of our method by presenting the first CCA1-secure multi-hop fully homomorphic encryption, from either iO or LWE. We also present the first adaptive multi-hop aggregate signature scheme from LWE.

Modern processors are largely fixed at the time of fabrication, rendering post-silicon security updates infeasible. This lack of flexibility is especially problematic for speculative execution attacks, which exploit microarchitectural optimizations to leak sensitive information through transient execution. However, existing defenses are typically hardwired, narrowly scoped, and non-adaptive. Once deployed, these defenses lack the flexibility to respond to new attack variants, creating a critical security gap.

This paper presents SPLASH, a novel and adaptive framework for comprehensively mitigating speculative execution vulnerabilities across processor components. SPLASH introduces two primary contributions: (i) we introduce Speculative Information Flow Tracking (SIFT), which enables fine-grained tracking of speculative data propagation throughout the microarchitecture; (ii) the reconfigurable speculative table provides, for the first time, enforceable and fully configurable control over speculative behavior across the processor pipeline. SPLASH is runtime-configurable, allowing dynamic security policy adjustments post-fabrication, such as tuning the speculative window size or selectively protecting specific microarchitectural structures, without requiring hardware redesign.

We implement SPLASH on both the small and medium BOOM processors and evaluate its effectiveness in mitigating speculative leakage vulnerabilities. SPLASH successfully mitigates all types of speculative execution attacks. In terms of computation overhead, SPLASH incurs only 0.05% overhead on small BOOM and 1.23% on medium BOOM on average compared with the baseline. Compared to the best performing state-of-the-art defenses, SPLASH reduces overhead by 129.2X and 1.2X, respectively, with negligible hardware cost.

Blind signatures are a fundamental cryptographic primitive enabling privacy-preserving protocols such as e-cash, e-voting, and anonymous authentication. However, achieving both formal security and compatibility with existing national cryptographic standards remains an open challenge. In this paper, we propose an efficient identity-based blind signature (IBBS) scheme constructed directly upon the SM9 Chinese national cryptographic standard (GM/T 0044-2016 / ISO/IEC 14888-3:2018). Our scheme is standard-compatible in the sense that the output signature \((h, S)\) passes the unmodified SM9 verification algorithm without any additional post-processing. We provide a rigorous formal security model encompassing one-more unforgeability and perfect blindness under the random oracle model. One-more unforgeability is reduced to the \(q\)-Strong Bilinear Diffie-Hellman (\(q\)-SBDH) assumption, while perfect blindness holds information-theoretically (i.e., without any computational assumption). We compare our construction against five representative SM9-related and identity-based blind signature schemes, demonstrating a reduction of at least 60\% in pairing operations and approximately 73\% in total signing latency relative to the state-of-the-art multifactor SM9 blind signature of Zhang et al.~\cite{Zhang2025}. Furthermore, we show how our scheme can be naturally extended to support partial blindness, thereby broadening its applicability to auditable e-voting and conditional anonymous credentials.

Decentralized Finance (DeFi) lending protocols implement programmable credit markets without intermediaries. This paper systematizes the DeFi lending ecosystem, spanning collateralized lending (including over- and under- collateralized designs, and zero-liquidation loans), uncollateralized primitives (e.g., flashloans), and yield aggregation protocols which allocate capital across underlying lending platforms. Beyond a taxonomy of mechanisms and comparing protocols, we provide empirical on-chain measurements of lending activity and user behavior, using Compound V2 and AAVE V2 as case studies, and connect empirical observations to protocol design choices (e.g., interest-rate models and liquidation incentives). We then characterize vulnerabilities that arise due to notable designs, focusing on interest-rate setting mechanisms and time-measurement approaches. Finally, we outline open questions at the intersection of mechanism design, empirical measurement and security for future research.

Batch encryption enables a holder of the secret key to publish a succinct pre-decryption key for a set of ciphertexts, such that exactly that set can be decrypted while other ciphertexts remain secret. Existing constructions either rely on epochs or, when epochless, suffer from large public parameters (quadratic in the batch size) and are vulnerable to censorship. In this work, we present an epochless, censorship-resistant batch encryption scheme with linear-sized public parameters, constant-sized pre-decryption keys and ciphertexts, and efficient batch decryption. Our construction extends the partial fraction techniques of Jutla, Nema, and Roy's threshold encryption scheme: we exploit partial fraction decomposition such that publishing a single group element as the pre-decryption key lets the decryptor decrypt all ciphertexts in the batch. We prove CCA security of our scheme, and show how to thresholdize it. Our results directly benefit applications such as encrypted mempools for MEV mitigation and time-lock encrypted storage.

A consistent accumulator computes a digest for a dynamically-growing set of elements, with a proof of consistency of the new digest with the previous digests. Consistent accumulators are in wide use, in particular, by Certificate Transparency (CT), which is part of the Web PKI, and in blockchains.

We present a significantly more efficient design for a consistent accumulator. Our design is compatible with the CT specifications; similarly to the widely-used, open-source CT implementation, it uses a Merkle tree, but much more efficiently. We provide open source implementation, security analysis and experimental evaluation showing the performance improvements.

Randomly permuting secret data vectors is a core building block in many privacy-preserving protocols, including those for analytics, advertising, and communication. Existing approaches either rely on computation-heavy public key cryptography and zero-knowledge proofs or scale poorly for large vectors due to use of a quasilinear-sized permutation network. This work presents a preprocessing approach to enable fast linear-time online shuffles in the malicious-secure two-party computation (2PC) setting. We propose FLOSS, a 2PC protocol for securely computing any interactive arithmetic permutation circuit, a notion we introduce to capture how higher level protocols are built on secret-shared field arithmetic and permutations. We show how secret-shared sorting (a subprotocol in data analytics) can be described as an arithmetic permutation circuit, and can thus be compiled to an efficient online 2PC protocol using FLOSS. Our implementation and evaluation confirm FLOSS performs online shuffles fast: shuffling $2^{20}$ elements in under 500ms, greater than $800\times$ faster than state-of-the-art alternatives.

In this work, we study the proposal for a linkable ring signature (LRS) in [KTS+24]. It is instantiated from the group action based framework described in [BKP20], using the Lattice Isomorphism Group Action (LIGA), meaning that the security of the signature rests on the famous Lattice Isomorphism Problem (LIP).

We will show that this signature does not in fact fit the requirements to be a linkable ring signature, despite the guarantees of the [BKP20] framework, due to it straying from that framework by using a non-commutative group for the group actions. More specifically, we will show that the signature from [KTS+24] satisfies neither the property of correctness nor linkability, which are required of a LRS.

This further damages the signature, as it was already shown in [BCF25] that the linkable anonymity property of [KTS24+] isn't satisfied.

The group used in LIGA is the group of invertible integer matrices: $\mathrm{GL}_n(\mathbb{Z})$. As the main obstacle in successfully applying the framework mentioned above to construct a LRS based on LIP is the fact that this group is non-commutative, we try fixing the signature by restricting the secret key space to a commutative subgroup of $\mathrm{GL}_n(\mathbb{Z})$. However, we will see that finding a commutative subgroup of $\mathrm{GL}_n(\mathbb{Z})$ that maintains the hardness of the underlying LIP, and that at the same time is realistic to use is not as easy as it may seem.

Hax is a verification pipeline that translates a subset of Rust into F*, enabling machine-checked proofs of panic freedom and functional correctness for cryptographic implementations being developed in partnership with Google and tested in Signal's post-quantum protocol.

We study whether hax's translation preserves the security properties it claims to verify. Through a structural analysis of its 35-phase transformation engine, F* proof libraries, and specification API, we identify three classes of semantic gap between the Rust source and the F* verification target: translation infidelity, where pipeline transformations distort security-relevant semantics; unverifiable trust boundaries, where operations are axiomatized without postconditions; and specification gaming, where escape hatches inject unproven facts into the verification context.

We demonstrate each class through five proof-of-concept exploits against ML-DSA (FIPS 204), ML-KEM (FIPS 203), Ed25519 (FIPS 186-5), and ChaCha20 (RFC 8439). Every exploit meets a strict criterion: the Rust code compiles, passes functional tests, and extracts to F* without warnings, while harboring a security gap invisible to testing.

We distinguish three gradations: facade gaps where the F* model actively diverges from Rust semantics, a conditional gap dependent on the compilation mode, and a scope gap where the model is faithful but cannot cover a critical property. We call the resulting phenomenon a verification facade: verification that is performed but covers less than it appears to cover.

Payment channel networks (PCNs) are a leading method to deal with the scalability limitations of blockchain networks. PCNs allow users to execute transactions without committing them to the blockchain by relying on predefined payment channels. Transactions between pairs of users without a connecting channel are also supported through a path of multiple channels. Serving such transactions involves fees paid to intermediate users. In this paper, we uncover the potential existence of the Braess paradox in payment networks: Sometimes, establishing a new payment channel can increase the fees paid for serving some fixed transactions. We study conditions for the paradox to appear under two different models of fees: Liquidity-based fees as a function of the transaction value jointly with the channel liquidity values and proportional fees which are based only on the transaction value. We also provide indications for the appearance of the paradox based on real data from Lightning, a popular payment channel network of Bitcoin. Last, we discuss methods to mitigate the paradox upon establishing a new payment channel.

We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem—$Gap_pMK^tP[s_1,s_2]$—where the goal is to determine whether for a given string x, $K^t(x) ≤s_1(n)$ or $K^{p(t)}(x) > s_2(n)$, where $K^t(x)$ denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if $Gap_pMK^tP[s_1,s_2] \notin prBPP$ for every polynomial p, then (under appropriate derandomization assumption) $Gap_pMK^tP$ is errorless average-case hard with respect to BPP heuristics. The notion of errorless average-case hardness, however, is seemingly insufficient for cryptographic applications where one needs to consider average-case hardness against attacks that simply may err with some probability (i.e., two-sided error hardness).

In this work, we present several new consequences of the assumption that $Gap_pMK^tP[s_1,s_2]\notin P/poly$ for all polynomials p, for appropriate choices of $s_1$,$s_2$, and under appropriate (worst-case) derandomization assumptions. In particular, we show that this assumption implies:

- The existence of an (inefficient-prover) zero-knowledge proof system for NP with a non-uniform simulator w.r.t. adversaries with a-priori bounded-length auxiliary-input. - The existence of a hard disjoint NP pair, defined as a promise problem $(Y,N)$ where both $Y,N\in NP$; this provides a barrier towards showing that $Gap_pMK^tP$ is NP-complete.

The above results are proven via first showing that the above assumption implies the existence of a so-called conditional PRG—roughly speaking, a cryptographic PRG where indistinguishability only needs to hold for some (potentially not efficiently sampleable) distribution over the seed to the PRG. (In fact, this notion of a PRG also almost directly implies average-case hardness of $Gap_pMK^tP$, and as such, this provides a modular explanation to Hirahara’s results.) Finally, we show that for the results on conditional PRGs and Zero-knowledge Proofs, unconditional results can be obtained (that is, without making any derandomization assumptions), if considering an appropriate version of $Gap_pMK^tP$ concerning randomized $K^t$.

In recent years, the shuffle model has emerged as a prevalent paradigm in privacy-preserving data analysis, centered on the principle of \textit{privacy amplification via shuffling}: an individual user's report is obscured by the ``background noise'' of other users' messages, a phenomenon intuitively known as the \textit{privacy blanket}. This paper initiates a foundational and systematic study of this mechanism from an information-theoretic perspective. We investigate the following optimal noise-design problem: given that a target user's message $Y_1$ follows a distribution $P$, what is the optimal blanket noise distribution $Q$ that maximizes privacy? Specifically, when $Y_1 \sim P$ and the remaining messages $Y_2, \dots, Y_n \stackrel{\text{i.i.d.}}{\sim} Q$ are shuffled to produce an output $\boldsymbol{Z} = (Y_{\sigma(i)})_{i=1}^n$, we seek the $Q$ that affords the strongest protection for $Y_1$ under various metrics, including mutual information $I(Y_1; \mathbf{Z})$, total-variation-information $I_{\mathrm{TV}}(Y_1; \mathbf{Z})$, message recovery advantage, and expected posterior variance.

Our analysis reveals a series of non-intuitive results that challenge the conventional heuristic of setting $Q=P$. First, we prove that the optimal noise distribution $Q$ generally \textit{deviates} from the target distribution $P$. For binary alphabets, we show that the (near-)uniform distribution is optimal in a strong sense. For general finite alphabets, we derive an explicit analytical form $Q \propto \sqrt{P(1-P)}$ that achieves asymptotic optimality for mutual information. Furthermore, we demonstrate that our analytical framework transcends the shuffle model, yielding new security insights into broader cryptographic primitives such as the \textit{ideal cipher model} and \textit{honey encryption}.

Finally, we extend our results to the shuffle-DP paradigm, where messages $Y_i = \mathcal{R}(X_i)$ are outputs of $\varepsilon_0$-locally differentially private mechanisms. We establish a new, tight information-theoretic upper bound $I(X_1; \mathbf{Z} \mid (X_i)_{i=2}^n) \le \frac{(e^{\varepsilon_0/2}-1)^2}{2n} + \mathcal{O}(n^{-3/2})$. This result provides a sharp characterization that matches the optimal privacy-amplification parameters known in the literature, while offering a novel interpretation of the shuffling gain.

Post-quantum migration in TLS 1.3 should not be understood as a flat substitution problem in which one signature algorithm is replaced by another and the resulting deployment cost is read directly from primitive-level benchmarks. In certificate-based authentication, the practical effect of a signature family depends on where it appears in the certification hierarchy, how much of that hierarchy is exposed during the handshake, and how the resulting cryptographic burden is distributed across client and server roles. This makes post-quantum TLS migration a problem of cryptographic design in authenticated key establishment, rather than merely a matter of algorithm selection.

This paper presents a local experimental study of TLS 1.3 authentication strategies built on OpenSSL 3 and oqsprovider. Using a reproducible laboratory, it compares ML-DSA and SLH-DSA across multiple certificate placements, hierarchy depths, and key-exchange modes, including classical, hybrid, and pure post-quantum configurations. The analysis is organized around four complementary campaigns: a leaf-only comparison, a full hierarchy strategy matrix, a depth comparison, and a key-exchange exploration.

Across the experimental matrix, the clearest discontinuity appears when SLH-DSA is placed in the server leaf certificate. In that configuration, handshake latency and server-side compute cost increase by orders of magnitude, while strategies that confine SLH-DSA to upper trust layers and preserve ML-DSA in the interactive leaf remain within a substantially more plausible operational range. The results further show that transport size alone does not explain the heavy regime: outside leaf-SLH scenarios, transferred bytes and observed chain size track latency closely, but once SLH-DSA reaches the leaf, server-side cryptographic cost becomes dominant.

The paper therefore argues that post-quantum TLS migration is best evaluated as a problem of certificate-hierarchy design, chain exposure, and cryptographic cost concentration during live authentication. In practical terms, signature placement matters at least as much as signature-family choice.

We introduce metric-aware code-based cryptography by moving beyond the Hamming metric to the Niederreiter-Rosenbloom-Tsfasman (NRT) and sum-rank metrics and by exploiting their linear isometry groups via Bruhat-Chevalley-Renner decompositions. On the structural side, we give isometry-invariant distance tests: a parity-check prefix-rank test for single-chain NRT, its multi-prefix extension for block-NRT, and a block rank-profile test for sum-rank. We also analyze orbit structure under the relevant isometry subgroups and prove NP-hardness of a block-NRT canonicalization problem via a reduction from Exact-3-Cover, pinning down the difficulty of public ``structure recovery.'' On the design side, we propose an inner-outer Niederreiter cryptosystem that couples a short rowwise single-chain NRT inner code with $k_V$ outer binary Goppa codes across columns. For the resulting matrix code we prove a distance guarantee $d_{\mathrm{NRT}}\!\ge\!\delta_V\cdot \min_t d^{(t)}$ and give a simple two-stage decoder (outer Goppa per coordinate, then inner per column). Public keys are dense, obfuscated parity-checks $M=S H_{\mathrm{sys}} (PD)$ drawn from a metric-preserving subgroup, preserving decodability while hiding structure. Finally, we reduce NRT and sum-rank syndrome decoding to classical Hamming/Rank decoding, yielding one-wayness of the public syndrome map at standard regimes.