International Association
for Cryptologic Research

We provide a new way of performing an algebraic attack on the McEliece cryptosystem based on binary Goppa codes. It also applies in general to the case where the field over which the Goppa code is defined is of even characteristic. It is based on a new algebraic modeling for finding as in [CMT23,M25,BLT26] matrices of rank $2$ in the code of quadratic relations related to the Goppa code that is attacked. Such matrices are then used to recover the secret algebraic structure of the code. This breaks the scheme. A byproduct of our approach is a new distinguisher for Goppa codes in even characteristic which is as the syzygy distinguisher of [R25] subexponential in the security parameter of the scheme. We demonstrate the effectiveness of our attack on McEliece TII challenges, some of which having been studied in [BLT26], and aimed at having $83$,$89$,$119$,$166$, $210$ and even $248$ bit security respectively and CFS keys with parameters $r=9$ and $m=16$, corresponding to a security of $74.9$ bits according to [LS12]. This CFS key was not attacked in practice in [BLT26] and took us 14 hours of computation and 24GB of RAM. We make the conjecture that this attack has a complexity which is of the same nature as the distinguisher, namely subexponential in the security parameter.

Post-Quantum Cryptography (PQC) and Quantum Key Distribution (QKD) are both contenders for securing communication against quantum adversaries, but are at different stages of maturity. For hedging security risks, hybridization is the default approach. Unlike previous research on classical–post-quantum hybrids, we propose a QKD-PQC hybrid for Authenticated Key Exchange (AKE).

To minimize the attack surface, we completely remove the requirement for digital signature schemes and propose a Hybrid Authenticated Key Exchange (HAKE) that combines Post-Quantum (PQ) AKE and QKD key agreement, leveraging Key Encapsulation Mechanisms (KEMs) for both key exchange and authentication. Our fully modular security analysis, based on the recent multi-input Key Derivation Function (KDF) framework by Backendal et al. (Eurocrypt 2025), establishes AKE security in the CK01 model and yields a conditional information-theoretic security guarantee when the QKD component is uncompromised; a property not achieved by prior hybrid protocols. We demonstrate the protocol’s practical feasibility with benchmarks using ML-KEM, FrodoKEM, and Classic McEliece.

Hybrid post-quantum migration is entering deployed handshake designs, but hybrid KEM security protects only one shared-secret input. It does not by itself say whether handshake, application, exporter, or resumption material remains pseudorandom after branch reveals, stage-key reveals, selective corruptions, or late corruptions. We characterize these staged claims through branch-formula freshness: each stage receives a monotone formula over branch exposure, authentication freshness, transcript binding, KDF ancestry, and explicit non-reveal atoms. Secrecy follows by replacing a surviving branch contribution and then using a labelled HKDF/PRF-style target-hiding argument along a fresh KDF cut; agreement follows separately from authentication binding and injective transcript representation. We also give selector-local accounting, where a fixed admissible witness selector determines which surviving branches and KDF cuts are charged. For scoped TLS 1.3 ECDHE--ML-KEM 1-RTT, we identify the branch-replacement, HKDF-path, and binding assumptions that imply concrete preservation bounds for handshake, application, exporter, and resumption targets.

All EU member states are required to roll out a digital identity system - the European Digital Identity (EUDI) wallet - by the end of 2026. Strong privacy is at the core of the underlying regulation, which mandates the EUDI wallet to support selective disclosure and unlinkability. The wallet currently being developed relies on the batch issuance of one-time ECDSA credentials that sign attributes through individually salted hashes for selective disclosure. This solution is known to achieve only a weak form of unlinkability, where the credential issuer must be honest: a malicious issuer could trace users through the salted hashes it signs and the signature value itself. But such a tracing attack requires the issuer to store all signed data and communicate with the verifying parties for tracing, which can be argued to be too cumbersome or obvious to happen in reality. In this work, we therefore initiate the study of a more subtle type of subversion attacks. Therein, the issuer can deviate from the issuance protocol, with two goals: (i) enabling verifiers in possession of a short tracing key to de-anonymize users and (ii) keeping this deviation undetectable from users. We formalize unlinkability against such subversion attacks, and show that batch-issued credentials with salted hashes do not achieve that form of privacy. We present several undetectable subversion attacks against batch-issued ECDSA credentials and suggest lightweight mechanisms to provably mediate them.

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniform random strings, a primitive motivated by the need to robustly watermark generative AI models. While recent breakthroughs have established the feasibility of PRCs, critical challenges remain regarding the diversity of their underlying cryptographic assumptions and their security against active adversaries. This work advances the study of PRCs on two complementary fronts: structural diversity and advanced security.

On the structural side, we propose a novel PRC template that departs from the prior one based on sparse parity-check trapdoors. We introduce a new LPN-type assumption, formalized as Dense-Planted LPN, which postulates $(\mathbf{M}\mathbf{T}, \ \mathbf{M}\mathbf{T}\mathbf{s}+\mathbf{e})\ \approx_c\ (\mathbf{M}\mathbf{T}, \ \mathbf{u})$, where $\mathbf{T}$ is a random dense matrix and $\mathbf{M}$ is sampled from a distribution containing a planted structure. This hidden structure enables a completely new decoding mechanism based on a local-window search rather than global parity checks. Notably, this template provides a viable path toward constructing PRCs from assumptions beyond code-based ones, including Learning with Errors (LWE) assumptions.

On the security side, we construct the first public-key PRC secure against pre-challenge chosen-codeword attacks (CCA1) in the standard model. In realistic watermarking deployments where detectors are exposed as public services, CCA security is essential. However, prior CCA-secure PRCs were only achievable in the random oracle model. By formally introducing and instantiating a robust tag-based equivocal bit commitment scheme combined with robust hinting PRGs, we demonstrate that CCA1 security can be achieved in the standard model without sacrificing decoding robustness.

Pseudorandom codes (PRCs), recently proposed by Christ and Gunn (CRYPTO'24), are encryption schemes that have pseudorandom ciphertexts and a decryption algorithm which is resilient against a bounded number of Hamming errors. This notion provides a significant strengthening over standard PKE and has exciting applications in, e.g., watermarking LLMs. The recent work of Alrabiah et al. (STOC'25) initiated the study of CCA-secure public-key PRCs, where the adversary is additionally given access to a decoding oracle. In terms of realizations, they provide one that can be proven secure in the random oracle model. Constructing CCA-secure public-key PRCs in the standard model remained an open problem.

In this work, we resolve this problem and provide the first construction of CCA-secure public-key PRCs in the standard model. Our construction achieves a constant rate and can decode from a constant fraction of adversarial errors. In fact, our construction is a general blueprint that can be instantiated from a broad range of standard cryptographic assumptions.

As an additional contribution, we construct a strong adaptively robust public-key pseudorandom code with conjectured sub-exponential security based on a new family of assumptions we call Noisy McEliece. In a nutshell, these assumptions mask a scrambled generator matrix from an efficiently decodable inner-code family with sparse Bernoulli noise; this additional error is meant to obscure the algebraic structure targeted by known attacks and thereby permits candidate instantiations from broader classes of codes.

Masking stands as one of the most effective countermeasures against side-channel attacks. While a number of recent works have investigated first-order masking schemes that eliminate the need for fresh randomness, most existing solutions trade off this randomness reduction against increased latency or area overhead. This paper targets the simultaneous achievement of low latency and zero fresh randomness. To this end, we make the following contributions. First, we identify a security flaw in the round-based design proposed by Askeland et al.\ at CARDIS 2022, which builds upon the Changing of the Guards (COTG) technique. Second, we propose a revised construction that rectifies this vulnerability without incurring any additional randomness or latency penalty. Finally, by integrating the Time Sharing Masking (TSM) S-box introduced at CHES 2025, we present a first-order masked AES implementation with a latency of 20 clock cycles that requires no fresh randomness.

The eSIM specification enables remote SIM provisioning without the need to hand out a physical SIM card. Instead of a physical SIM card, the subscriber downloads a SIM profile, which contains a subscriber's identity and authentication key material, to their embedded UICC, a discrete, embedded chip in the user's phone. This provisioning process is specified in the remote SIM provisioning (RSP) protocol and is secured through contemporary public-key cryptography. However, the potential advent of general-purpose quantum computers threatens the security of RSP.

This paper provides a quantum threat analysis of the RSP protocol, considering both Harvest Now, Decrypt Later attacks and active quantum attacks. To alleviate this threat, this paper introduces PQC-RSP, a post quantum secure version of the RSP protocol. The main challenge we address is the introduction of key encapsulation mechanisms (KEMs) into the RSP protocol, both in a PQC-only and hybrid version, and the security implications of this modification. We prove the security of PQC-RSP and review the performance overhead introduced through the usage of post quantum cryptography.

We initiate the study of \emph{arithmetic} private information retrieval (APIR) schemes, in which the database is a vector of field elements and the scheme makes a black-box use of the field. We obtain the following results.

\begin{itemize} \item Our main result is a negative one: We show that no single-server APIR scheme can achieve non-trivial download cost smaller than $n$ field elements. We observe that recent proposals for code-based PIR (Holzbaur et al., ISIT'20; Verma and Hollanti, ISIT'24) are arithmetic, and show how to break them within a few minutes on a standard workstation for all suggested parameters.

\item We complement the above by positive results in alternative models. Concretely, we show that with either two servers or a single server with secret-key preprocessing, it is possible to construct computationally secure APIR schemes based on well-studied coding assumptions. This is achieved by arithmetizing the distributed-point-function-based PIR of Boyle et al.~(CCS'16), and by observing that the recent construction of secret-key single-server PIR by Chen et al.~(STOC'26) also arithmetizes.

\item Finally, we characterize the existence of information-theoretic two-server APIR schemes in linear-algebraic terms, and show that communication of $O(n^{1/3})$ can be achieved in this setting based on the original approach of Chor et al.~(FOCS'95). The optimality of this result remains an interesting open question. \end{itemize}

This document provides a machine-checked Isabelle/HOL formalisation of the modular-arithmetic core of the Neon NTT paper of Becker, Hwang, Kannwischer, Yang, and Yang. We develop parametric theories of Barrett and Montgomery reduction and multiplication; the equivalence of Barrett and Montgomery arithmetic; the doubling- and rounding-Montgomery variants; and correctness and bounds theorems for Neon assembly kernels, against a hand-written model of the word arithmetic underlying the relevant Neon instructions. The development is a directed auto-formalisation: definitions, theorem statements, and proofs were produced by Claude Opus 4.7 and 4.8 using AutoCorrode's LLM-Isabelle integration layers. The human author set the architecture, chose abstractions and proof strategies, often nudged the model toward shorter or cleaner proofs, and controlled which output entered the development. This document is auto-generated from the Isabelle sources through Isabelle’s document preparation system, eliminating drift between prose and formal artifact.

Emerging attacks and applications have motivated the development of transforms that turn a given AE scheme into a committing AE (cAE) one. We give a new transform called UCX with the following attributes: It does not require the starting scheme to be tag based, works for schemes in the broad AE5 framework rather than the limited AE1 one, and preserves both UNAE (Unique Nonce AE) and MRAE (Misuse Resistant AE) security. No prior transform is ``universal'' in the sense of having the combination of all these properties. The use of UCX in place of prior, limited transforms reduces the risk of error and failure in the real world, where choices may be made by application developers and hidden in software libraries. The committing security of UCX is shown in the ideal-cipher model, and its AE5-security in the standard model. To design UCX, we introduce and build a new primitive, that we call a Tweakable Committing Concealer, and that may be of independent interest.

We study error correction in a computationally bounded world, where errors are introduced by an arbitrary polynomial-time adversarial channel. Recent works construct seeded codes in this model, where the encoding and decoding procedure share a public random seed. They achieve significantly better tradeoffs between rate and error tolerance than what is possible information theoretically for unique decoding, essentially matching the parameters of the best known efficiently list-decodable codes. Over the binary alphabet, however, this is still well short of the optimal Shannon capacity with rate $R \approx 1 - H_2(p)$ for a $p < 1/4$ fraction of errors. Even heuristic constructions meeting this target were not previously known. We make progress towards this goal.

- $\textbf{Secret-Key Codes.}$ We first study secret-key codes, where the encoder and decoder share a secret key hidden from the adversarial channel. Lipton (STACS '94) constructed one-time secure secret-key codes achieving Shannon capacity in this setting, but it was unknown whether one can get CPA (resp. CCA) security where the adversary may query an encoding oracle (resp. also a decoding oracle). We construct CCA-secure secret-key codes achieving Shannon capacity via pseudorandom codes (PRCs). - $\textbf{Seeded Codes (Heuristic).}$ We can heuristically upgrade the resulting secret-key codes to seeded codes by publishing an obfuscation of the encoding/decoding procedures with a hard-coded secret key as a seed. Security holds in the ideal obfuscation model. - $\textbf{Public-key Codes.}$ We also consider public-key codes, where the decoder has a secret key and the encoder has the corresponding public key. We construct such CPA-secure public-key codes achieving Shannon capacity with unique decoding for $p < 1/4$ errors, and list decoding all the way to $p < 1/2$ errors, assuming PRCs and the subexponential security of standard crypto assumptions (e.g., LWE or DDH or QR or DCR). We also show how to get CCA security in the random oracle model. - $\textbf{List-Decodable Codes.}$ Finally, we consider list-decodable codes that can achieve Shannon capacity for even larger fractions of errors, all the way to $p < 1/2$. We construct such public-key CPA-secure codes in the plain model using PRCs, as well as CCA-secure ones in the random oracle model.

Our secret-key and public-key codes meeting Shannon capacity are also simultaneously pseudorandom codes.

Depth-robust directed acyclic graphs (DAGs) are an important combinatorial primitive in cryptography, with applications to memory-hard functions, proofs of space, and proofs of sequential work. These applications require node depth-robustness, yet constructing sparse graphs with strong concrete guarantees remains a longstanding challenge. By contrast, edge depth-robust graphs are easier to construct explicitly and achieve better parameters, motivating the problem of efficiently transforming edge-depth-robust graphs into node-depth-robust graphs. We give a new and substantially more efficient transformation from edge-depth-robust graphs to node-depth-robust graphs. We give a new and substantially more efficient transformation from edge-depth-robust graphs to node-depth-robust graphs. Prior work of Blocki and Cinkoske (ITCS 2021) gave a general transformation by replacing each node with an ST-robust graph, resulting in extraordinarily large overhead and relying on non-explicit components. In contrast, our transformation replaces each node with a single superconcentrator rather than an ST-robust graph, yielding an explicit construction whenever the input graph is explicit, with dramatically improved concrete efficiency.

Formally, given an $(e,d)$-edge-depth-robust graph $G$ with $N$ nodes and $m$ edges, our transformation generates a graph $G'=Transform(G_N)$ with $N' = O(m)$ nodes, constant indegree, and $(e/3,\, 2d-1)$-node depth-robustness. We also show that the transformation preserves fractional depth-robustness. Moreover, when $m=\omega(N)$, we show that our transformation can amplify depth --- overcoming a key limitation of prior work. In particular, for any parameter $d'$, we can obtain a constant-indegree graph $G'$ with $N' = O(m+d'N)$ nodes and $(e/3,\, (d-e)d')$-node depth-robustness, yielding asymptotically tighter results in the important setting where $m = \omega(N)$ and $e \geq d$ by setting $d' \sim m/N$. As an application, We provide a novel analysis of Schnitger's edge-depth-robust graph construction (FOCS 1983). We show that the graph $G_n$, which has $N=2^{n+1}-1$ nodes and $m \leq n2^{n}$ edges, is $(e,2d-1)$-edge-depth robust for all $e + d \leq 2^n$. Applying our transformation yields an explicit DAG on $N'$ nodes with maximum indegree $2$ and depth-robustness parameters $e = \Omega(N'/\log N')$ and $d = \Omega(N')$, matching the best known asymptotic trade-offs—even compared with non-explicit constructions—while improving the best previously known concrete ed-product lower bound by a multiplicative factor of 6.6.

We introduce WayFinder, a framework for generalizing the Delfs-Galbraith and SuperSolver algorithms for the supersingular isogeny problem. Our framework extends the search for elliptic curves with an orientation by an order containing $\mathbb{Z}[\ell \sqrt{-p}]$ to more general orders, and we derive a cost model for such generalisations. Our cost model not only works in a more general context, but also provides more accurate predictions when applied to SuperSolver. We instantiate WayFinder for orders containing $\mathbb{Z}[\ell_1\sqrt{-\ell_2p}]$ where $\ell_i$ are $1$ or primes such that the modular curve $X_0(\ell_2)$ has genus $0$. We then introduce a low-storage algorithm for computing an isogeny between two oriented supersingular elliptic curves, even when the curves are oriented by distinct orders. Together, these provide an algorithm that improves on the state of the art for solving the isogeny problem, and a cost model with potential applications to parameter selection in isogeny-based cryptography.

We study frequency estimation in the shuffle model of differential privacy under poisoning attacks, where corrupted users may deviate from the local randomizer to inject crafted in-domain messages. Existing shuffle-model protocols face a core tension: achieving low estimation error relies on flexible multi-message noise generation, which can amplify poisoning influence once messages are anonymized by shuffling.

To address this tension, we propose a symmetric binomial-sum noise distribution (i.e., $\mathrm{Bin}(n/2,p) + \mathrm{Bin}(n/2,1-p)$), which preserves high accuracy while limiting the impact of crafted in-domain messages. We realize this distribution via preprocessing-guided noise generation, which routes a balanced collection of mode flags through the shuffler so that each user receives a randomly assigned mode flag that fixes their noise-sampling behavior prior to shuffling. For binary estimation, our protocol requires a single Bernoulli trial per user and at most $2$ messages per user ($1.5$ on average), while bounding the worst-case poisoning influence of a single corrupted user by $O(1/n)$. We extend the protocol to histograms, including large domains via hashing, and provide formal privacy, accuracy, and robustness guarantees. Experiments on real datasets show that our protocols remain resilient under poisoning and reduce MAE by up to nearly $2\times$ over the strongest baseline at comparable per-user communication on small-domain workloads, and stay on par with it on large domains.

In this work, we construct (stateful) leakage-resilient circuits (LRCs) secure against bounded-output-length leakage functions computable by \(\mathsf{NC}^1\) circuits under the mild worst-case assumption \(\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}\), without relying on any leak-free hardware components, thereby resolving the open problem left by Bogdanov, Ishai, and Srinivasan (Journal of Cryptology, 2021) and Wang (CRYPTO 2025).

Concretely, we first construct a leakage-tolerant circuit with succinct setup (sAI-LTC) secure against 2-adaptive \(\mathsf{NC}^1\) leakage, and then generically combine it with a 2-adaptive leakage-resilient composable encoding scheme to obtain the desired LRC.

We further give a direct non-black-box instantiation that optimizes the compiled circuit size at the cost of a slightly larger setup, matching the circuit size of Wang's construction that relies on leak-free hardware while using a more compact setup.

Finally, we show that our sAI-LTC generically implies a fine-grained multi-theorem non-interactive proof system for all \(\mathsf{NP}\), with compact common reference strings, perfect soundness, and multi-theorem zero-knowledge with offline simulation against \(\mathsf{NC}^1\) adversaries.

Shor demonstrated that the discrete logarithm problem in the multiplicative roup $\mathbb{Z}_{p}^{*}$, where $p$ is an odd prime, can be solved fficiently using a period-finding algorithm based on the quantum Fourier transform. In this paper, we propose a quantum-classical algorithm based on algebraic properties that do not rely on periodicity. Specifically, we show that the hardcore predicate for the discrete logarithm problem, which was introduced by Blum and Micali, can be reduced, using the swap test, to the problem of distinguishing between two Bernoulli distributions. In our algorithm, although the swap test is used as a quantum subroutine, most of the computation is performed classically. Moreover, the algorithm does not require the quantum Fourier transform.

Classically testing for the presence of anti-commuting operators on a quantum device is a critical tool underpinning recent progress in classical verification of quantum computation. While such tests can be based on cryptographic assumptions, known constructions rely on highly structured assumptions, e.g. trapdoor claw-free functions.

In this work, we seek to explain this state of affairs by constructing strong cryptography from (certain forms of) classical tests of anti-commutation. In particular, we formulate the notion of a test of non-commutation (ToNC), an interactive protocol between a quantum prover and classical verifier in which the prover's final-round response is obtained by measuring one of two binary observables ?₀, ?₁ depending on the verifier's challenge bit ?. We prove that, for a broad range of parameters, ToNC implies classical-communication key agreement (KA), and ToNC combined with one-way functions implies oblivious transfer (OT).

Along the way, we develop tools for and provide the first known results on hardness amplification for post-quantum KA and OT, where communication is classical but adversaries may be quantum. In particular, we prove the following results of independent interest. - Post-quantum hard-core measure theorem: For any efficiently sampleable high-min-entropy distribution ? over pairs (?,?) such that quantum circuits have advantage at most ? in predicting ? from ?, there exists a sub-distribution ?≼? of density 1-? on which ? is nearly optimally quantum-hard to predict. - Post-quantum interactive XOR lemma: Given any classically-interactive protocol, if quantum adversaries have advantage at most ? in guessing a private challenger bit ?, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits ?₁⊕?₂ to at most ?² + negl(?).

Blockchain consensus protocols, also known as BFT state-machine replication, enable a system of $n$ players to decide an ever-growing chain of blocks. We consider partial synchrony: after an unknown time GST, messages sent by honest players are delivered within an unknown actual delay $\delta$, and a known bound $\Delta$ satisfies $\delta \leq \Delta$. This setting imposes $t
The main technical novelty is a certificate of exclusivity for a block $B$. It is shown by the next leader as evidence that players can safely vote for a child of $B$. A certificate of exclusivity is an interpolation between a quorum certificate and a timeout certificate, in that it is formed from a mix of votes for a unique block $B$ and complaint votes, proving that $B$ is the only non-dummy block that can still obtain a decision certificate for that iteration.

The other novelty of Hamster is the use of {overlapping iterations: after a process has supported a newer proposal, the protocol may still allow it to support a safe proposal of an earlier iteration}. This overlap is what allows old honest proposals to be decided in time despite players advancing iterations faster.

We also analyze another metric, called the {pessimistic block proposal time}, which is the time during which a bad leader can delay the proposal of a transaction in a block which will be decided. Hamster achieves a pessimistic block proposal time of $2\Delta+2\delta$, refined to $2\Delta+\delta$ for leaders not caught equivocating, down from $3\Delta+\delta$ for Simplex.

In addition to anonymity and traceability, which are the primary security properties of group signatures, non‑frameability is also defined (Bellare-Shi-Zhang, CT-RSA 2005). This property guarantees that even an adversary colluding with all authorities (the opener and the issuer) cannot produce a signature that frames an honest user, and it is regarded as a security notion that protects users. In this short note, we introduce a new perspective on non-frameability, namely that it can also protect the authorities, and we examine its significance in the context of anonymous auctions, a well‑known application of group signatures. We show that non-frameability serves as an effective countermeasure against situations in which a winning bidder falsely claims not to have placed a bid and accuses the organizer of forgery.