GeezerVison

γ₁₁: Unequal Triangles and Adapted References — the macadamia 0050

Foundations

Show abstract

Foundations

This paper settles the ninth of the ten macadamias of the series on the Hermite constant in dimension 11: the perfect form $P$ = 0050:024468269 of rank 9, of determinant 8192/9 at minimum 4. The root paper reduces $\gamma_{11}$ to chains $L\supset M\supset N$ of lattices of ranks 11, 10, 9, each with minimum at least 4; we prove that every admissible chain whose rank-9 member is admissibly marked by $P$ has $\det L\ge 972$. No argument at rank 10 can do this, because an actual lattice of rank 10 with determinant $3328/3<4\cdot 972^{9/11}$ lies over $P$. The proof is computer-assisted, with explicit finite checks. Its decisive step is elementary: the three additive dual vectors of a section covector and the first normal usually have different lengths, and keeping the three lengths in the circle obstruction, instead of their maximum, gives a determinant cap that sharpens every subsequent contact and spectral bound. Adapted reference forms turn the contact conditions into exact rational tests, a common slack is retained throughout, and four computational results reduce the problem to a five-parameter root, exhausted by a finite cover of 6 993 terminal regions replayed in exact arithmetic.

TUTTI: Parallel CKKS Bootstrapping in under 3 ms on CPU

Public-key cryptography

Show abstract

Public-key cryptography

This paper introduces TUTTI, a new CKKS bootstrapping procedure that outperforms previous low-latency solutions in multi-threaded latency for any number of messages and, most notably, has a lower latency than TFHE when bootstrapping a single one. Our bootstrapping builds upon SPRU (CK, TCHES 2027), improving it with new methods for exploiting parallelism and increasing the number of messages, as well as with a refined security analysis, of independent interest, of the block-binary secret keys of LMSS (AsiaCCS 2023). \tutti bootstraps $4096$ real-number messages in $46$ to $83.4$ ms on $192$ threads to restore $1$ to $9$ multiplicative levels, outperforming SHIP (CHKS, Eurocrypt 2025) by a factor of up to $3$ on the same machine. Unlike SHIP, TUTTI gains immediately from bootstrapping fewer messages, with a $256$-message bootstrapping taking just $15$ to $34$ ms on $32$ threads. For a single message, TUTTI takes $4.6$ ms on $32$ threads, whereas TFHE-rs needs $7.3$ ms for a $4$-bit bootstrapping on the same machine and thread count. We show that this advantage persists across different architectures: on an Apple M5 Pro laptop (ARM), TUTTI takes $2.4$ ms on $14$ threads, against $4.5$ ms for TFHE-rs. Differences between CKKS and lightweight schemes such as TFHE remain on several fronts, from functionality to key sizes and security assumptions, but our work shows that multi-threaded latency is no longer one of them, closing a long-standing gap in the practical FHE literature.

Access Cost Tradeoffs in Mixed-Mode Oblivious RAM

Cryptographic protocols

Show abstract

Cryptographic protocols

A mixed-mode oblivious RAM (ORAM) lets each memory request be marked public or private: public requests disclose their addresses, private requests hide them. We ask how much work such a scheme must do, and which requests must do it, in the cell-probe model—with a passive server that only reads and overwrites addressed words. We examine the expected amortized per-request cost on randomized workloads with independent modes and uniformly random addresses. For array size $n$ and client memory $m\le n^{1-\varepsilon}$ words, let $H=\log_2(2+n/(m+1))$. Our main result is a tight tradeoff between the cost of public reads and private writes. We show that if a request is private with probability $0<p\le1/2$ and private requests cost at most $Q$ probes on average, then every scheme with $m\le n^{1-\varepsilon}$ has expected public-read cost\[ \Omega\!\left(\max\left\{1, \frac{H}{\log_2(2+1/p+Q/H)}\right\}\right), \]even when the server learns the kind (read/write) of each private request. For polynomial $m$, we provide constructions that match this bound whenever $Q$ exceeds a threshold that we identify for both $Q$ treated as an expectation over the workload and as the average cost for the worst-case workload. In particular, at constant private frequency $p$ a logarithmic private budget forces logarithmic public-read cost, and constant public-read cost requires private cost $(n/(m+1))^{\Omega(1)}$. This answers, for passive servers, the question posed by Zhang, Wang, and Weng, whose PIR-based scheme achieves constant public and logarithmic private bandwidth with server computation. Our lower bound proof fixes the public query and changes its private history; crucially, we charge them separately. Our constructions combine a public cache with linear merges of hash tables. Two further groups of results concern public writes and total work. Firstly, we give a cost tradeoff between public writes and private reads. Secondly, for workloads mixing private operations, public reads, and public writes with probabilities $p,r,a$, we show that every scheme with $m\le n^{1-\varepsilon}$ has total cost per request $\Omega(\max\{1,H/\log_2(2+1/p)\})$ when private request kinds are hidden, and a construction with polynomial client memory matches this bound with a constant independent of $p,r,a$. We also separately bound the costs of reads and writes in this workload. Lastly, public requests can in some cases be made cheaper by offloading their cost to preparation in earlier requests or cleanup in later ones. For both public reads and writes, we show localized tradeoffs constrained to a subset of requests, which demonstrate some of the limitations of such offloading.

The isodual constant of the LLL potential: exact values and structure

Foundations

Show abstract

Foundations

The LLL potential $\Psi^2(B)=\prod_k\det\mathrm{Gram}(b_1,\dots,b_k)$, minimized over the bases of a lattice $L$ and normalized by its determinant, defines an isodual lattice invariant $\eta(L)$. Its supremum $\eta_n$ over $n$-dimensional lattices, introduced in ePrint 2007/105, is the staircase case of the generalized Hermite constants of Watanabe and Meyer, for which explicit values were known only for $n\le4$. We prove that $\eta_5=6$, attained only by $D_5$ and its dual: the flag analogue of Korkine and Zolotarev's value of $\gamma_5$. The natural reduction to four-dimensional lattices, through a function $\Phi_5$, does not suffice: the global maximum of $\Phi_5$ is $2^{16}/(3^4\cdot5^3)\approx6.4727$, attained not at $D_4$ but at an even $135$-modular lattice $M_*$, which we have not found in the literature. A second stage, over the lifts of the remaining region, completes the proof; both stages are computer-assisted, with about $9\times10^9$ leaves, each re-proved in interval arithmetic by a separately written checker; code and data are public. We also prove $\eta_8=2304$, attained by $E_8$, and show that $E_6$, $E_7$, $E_8$ and their duals are strict local maxima of $\eta$ (for $n=6,7$ these are the conjectured extremal lattices). Asymptotically, $\log\eta_n=(\frac14+o(1))\,n^2\log n$. For lattice reduction we introduce the $\Psi$-Hermite constant $\mu_m$, the largest first Gram–Schmidt norm in a potential-minimal basis of an $m$-dimensional lattice, and bound it through $\eta_m$. This gives $\mu_m=\gamma_m$, Hermite's constant, for $m\le5$, and $\mu_m\le\exp(O(\log^2 m))$ in general.

On Composing Oracle Separations

Foundations

Show abstract

Foundations

Black-box separations constitute very powerful technical barriers against constructing primitives from specific building blocks. However, they give surprisingly little indication on the usefulness of \emph{combining} several such building blocks in a single construction. We propose a set of technical conditions, under which (fully) black-box separations compose with each other. That is, if two black-box separations $P_1 \stackrel{BB}{\nRightarrow} Q$ and $P_2 \stackrel{BB}{\nRightarrow} Q$ satisfy our conditions, then $Q$ is also separated from black-box combinations of $P_1$ and $P_2$. When applicable, these conditions can be established without unpacking the full technical details of the base separations. As our main application, we show that combining indistinguishability obfuscation (iO) with collision resistant hash functions is unlikely to yield hard problems in the complexity class $SZK$, and thus unlikely to suffice for primitives such as lossy functions or fully homomorphic encryption. Previous lower bounds on iO only applied to combinations of iO with one-way permutations (Asharov-Segev, FOCS '15 and Bitansky-Degwekar-Vaikuntanathan, SIAM Journal on Computing '21).

Antipodal necessity for rotation symmetric bent functions of degree at most three

Foundations

Show abstract

Foundations

The conjecture that every homogeneous rotation symmetric bent Boolean function has degree two remains open in general. We prove a necessary condition that settles the degree-three case of this conjecture. Let $n>0$ be even. If a rotation symmetric Boolean function of degree at most three in $n$ variables is bent, then its algebraic normal form contains the antipodal quadratic orbit $\sum_{i<n/2} x_i x_{i+n/2}$. A homogeneous cubic has no quadratic terms, so no homogeneous rotation symmetric cubic Boolean function is bent, in any even number of variables. The condition also applies to nonhomogeneous functions with arbitrary lower-degree terms compatible with rotation symmetry; it neither classifies these functions nor addresses degree four and higher. The proof uses only finite Fourier analysis and linear algebra over the binary field. Restriction to the fixed space of a rotation of odd order reduces the problem to a power-of-two number of variables. There, Parseval's identity and a rigidity property of rotation symmetric quadratic forms impose incompatible conditions on a single fiber of the function. A second proof replaces the final fiber argument by descent through a single unipotent Jordan block. Examples illustrate the hypotheses. A Lean formalization of the original proof is provided as supplementary material; the Jordan proof has not been formalized.

Adaptively Secure (Threshold) Batched IBE from Static Assumptions

Public-key cryptography

Show abstract

Public-key cryptography

Batched identity-based encryption (batched IBE) lets a key authority release one short decryption key for a set of identities and a batch label/epoch. It has been used to mitigate maximal extractable value (MEV) attacks on public blockchains. Existing constructions either use the generic-group and/or random-oracle models, or rely on $q$-type assumptions whose size grows with the batch-size bound. In this paper, we present the first adaptively secure batched IBE scheme from static assumptions. Our scheme supports an exponential identity space and an exponential epoch space, and its ciphertexts, digests, and batch keys consist of a constant number of group elements independent of the batch size. Our scheme relies on composite-order bilinear groups, and we prove its adaptive security assuming hardness of static subgroup decision assumptions and a static pairing assumption, with a security loss polynomial in the security parameter $\lambda$ and the number of key queries. Our proof does not rely on $q$-type assumptions, random oracles, generic-group arguments, or complexity leveraging. We also present a threshold version with adaptive challenge security under static corruption, and translate our scheme to prime-order bilinear groups under the static MDDH assumption.

Enabling Memory Encryption Using Ascon Derivatives

Secret-key cryptography

Show abstract

Secret-key cryptography

Keeping data stored in memory confidential is a tough challenge when assuming an adversary with physical access to it. First, we have fine-grained access to typically 256 to 512 bits at once, so nonces or tags of the typical sizes used for authenticated encryption would lead to a sizeable overhead. Second, we have stringent performance requirements, including low latency that directly impacts CPU performance and, more generally, strict area and energy constraints, especially for the high bandwidth of memory interfaces. Currently, memory encryption solutions typically rely on the AES block cipher. In this paper, we explore ways of using Ascon as a building block for memory encryption. Our analysis shows that Ascon-based constructions achieve better performance than AES-based HCTR2 and can also compete with XTS-AES while providing larger block sizes.

SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders

Cryptographic protocols

Show abstract

Cryptographic protocols

We introduce \(\mathsf{SEC}\), an expander-code-based ramp secret sharing scheme over \(\mathbb{Z}\)-modules, particularly suitable for lattice-based distributed cryptography. It is everywhere-short: bounded secret coefficients yield bounded share coefficients, and the integer reconstruction vectors have bounded entries. Moreover, each participant receives exactly one share, regardless of the number of parties and the privacy and reconstruction thresholds. This improves on prior schemes with bounded share coefficients and bounded entries in the integer reconstruction vectors, in which the number of sub-shares or shares per participant grows either with the number of parties and the threshold or with the security parameter. The construction rests on a coding-theoretic observation: in the bi-adjacency matrix of a lossless bipartite expander, unique-neighbor peeling completes every sufficiently small set of columns to a square unimodular submatrix. We prove correctness, everywhere-shortness, and linearity, and give a publicly computable entrywise bound on the reconstruction vector our algorithm returns for each authorized set. For privacy, we introduce hard-core local leakage resilience, which strengthens the leakage-resilience notion of Nielsen and Simkin (EUROCRYPT 2020) to protect a hard-core function of the secret, and we prove that \(\mathsf{SEC}\) satisfies it against correlated multi-query local leakage under the \(\mathsf{MatrixHint\text{-}MLWE}\) problem, which admits a reduction from the standard \(\mathsf{MLWE}\) problem. For \(n=60\) participants and security parameter \(\kappa = 128\), \(\mathsf{SEC}\) achieves privacy threshold \(6\) against \(2^{64}\) leakage queries and empirical reconstruction threshold \(46\). The ideal entropy-coded secret and share sizes are about \(3.5\) KiB and \(6.4\) KiB, respectively.

MPCTM: MPC-Based Trajectory Matching on Unmanned Autonomous Systems

Applications

Show abstract

Applications

Emerging technologies such as Unmanned Autonomous Systems (UASs) are increasingly being deployed across several application domains. Their deployment, however, introduces safety risks, especially when unmanned vehicles operate in shared operational spaces (e.g., air, land, or maritime) and may follow collision-prone paths. This creates the need for solutions that can detect possible collisions among pre-planned trajectories, thereby improving operational safety and reducing risk. At the same time, revealing trajectories in plaintext leaks sensitive information, such as traversal patterns, deployment and infrastructure locations, and potentially private user data. In this paper, we present a privacy-preserving trajectory matching protocol based on Multi-Party Computation (MPC). We introduce an end-to-end secure scheme for collision detection that reveals no information beyond the prescribed output. Our solution models the behaviour of UASs along their paths, accurately capturing collisions that may occur between discretely sampled points. We further propose a lightweight, MPC-friendly model and discuss the trade-off between accuracy and efficiency for the two approaches. We provide a proof-of-concept implementation of our scheme and compare it to the closest state-of-the-art solution. Our evaluation shows that our work MPCTM, in the dealer mode, improves the online latency upon previous work by over 2x in our modelled protocol and by 8x in our lightweight protocol. In autonomous mode, our protocol results in a slow-down of 2.5-3x, while providing a more expressive model with no false negatives and fully preserving privacy of the trajectory data.

Practical Confidential Clustering for Federated Learning using Efficient Secret-Sharing

Applications

Show abstract

Applications

Federated Learning (FL) often suffers from statistical heterogeneity, where diverging data distributions prevent a single global model from achieving high utility for all participants. Clustered Federated Learning (CFL) addresses this problem by grouping similar clients to train personalized sub-models, yet performing such clustering while ensuring strict confidentially with minimal communication overhead remains a significant challenge. This paper introduces CCFL, a framework for Confidential Clustering that executes clustering logic, including distance computations and centroid updates, entirely within the encrypted domain using Replicated Secret Sharing (RSS). CCFL orchestrates a unified pipeline that integrates client-side feature extraction, an anonymization server for oblivious shuffling, and Multi-Party Computation (MPC)-based clustering to ensure both input privacy and participant unlinkability. By employing a ring-based Euclidean distance optimization, CCFL significantly reduces interactive rounds, achieving up to $46.7\times$ computational speedup under realistic LAN and WAN constraints. Our one-shot clustering approach decouples heavy cryptographic computation from the training loop, allowing the system to scale seamlessly to thousands of clients with negligible edge overhead. Finally, downstream evaluations confirm that CCFL achieves a superior privacy-utility trade-off, matching or outperforming state-of-the-art personalized FL paradigms without exposing sensitive feature geometries.

DKG: A Dual-Layer Knowledge Graph and LLM Co-Driven Framework for Fully Automated Side-Channel Analysis of Cryptosystems

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

Cryptographic algorithms underpin billions of devices, from payment smartcards to smartphone secure enclaves and industrial controllers. Yet their physical implementations risk leaking secret keys. Non-profiled side-channel analysis (SCA) evaluates whether such leakage enables key recovery, but executing it end-to-end remains expert-intensive. Large language model (LLM) agents now automate complex workflows across many domains, yet reliable key recovery requires specialized SCA knowledge that must be extracted and organized from scattered technical literature. In this paper, we propose DKG, a dual-layer knowledge graph and LLM co-driven key-recovery agent framework. We introduce the first graph schema designed specifically for SCA: an upper layer of configuration components and a lower layer of diagnostic strategies, joined by cross-layer relationships. An LLM-driven three-step extraction pipeline (Locate & Rewrite, Triple Extraction, and Knowledge Fusion) builds the graph from raw technical documents without manual annotation, and at runtime the retrieved knowledge drives a closed-loop autonomous attack workflow. Built from a corpus of 166 technical documents, the graph contains 1,334 entities and 1,813 relationships. On eight datasets covering AES, DES, and SM4 across smartcards, FPGAs, and MCUs, DKG with DeepSeek-V3.2 achieves a 97.5% end-to-end key-recovery success rate. By comparison, ReAct-RAG, a text-retrieval-augmented agent, achieves only 68.8%. Across the open-weights backbones DeepSeek-V3.2, GLM-5, and Qwen3.5, DKG achieves an average success rate of 93.3%. To the best of our knowledge, DKG is the first framework to achieve consistent end-to-end automated key recovery across diverse implementations. Its automated pipeline lets the graph grow with new literature, and its dual-layer organization provides a basis for extending DKG to additional SCA techniques.

Adaptive Leaky LWE and Its Security

Foundations

Show abstract

Foundations

The Leaky LWE problem, proposed by Lai, Swarnakar, and Woo (CiC '25), studies whether LWE samples remain pseudorandom in the presence of noisy linear information about their secrets and errors. In Leaky LWE, the leakage matrix may depend on the public matrix, but must be chosen before the LWE challenge is revealed. We study $t$-round adaptive Leaky LWE, where each leakage matrix may depend on the challenge and all preceding leakage answers. Under explicit norm, smoothing, and sampling conditions, we reduce Gaussian-secret LWE to this problem at the corresponding source parameters for polynomially many rounds. The reduction preserves the public-matrix distribution and access to its correlated oracle, and supports rectangular leakage matrices and non-spherical discrete Gaussians over arbitrary orders in number fields.

Doubly-Efficient Private Information Retrieval from Modular Forms

Cryptographic protocols

Show abstract

Cryptographic protocols

We present new information-theoretic protocols for $s$-server, doubly-efficient private information retrieval (PIR) in sublinear server time and one extra bit of space on the servers, for every constant $s \geq 2$. On an $n$-bit database, each of the $s$ PIR servers first builds and stores a preprocessing data structure consisting of $n+1$ bits (which is unique to each server, and after which the server may discard the original database). Then, each server answers a PIR query in time $T_s(n)$, by reading at most $T_s$ bits of its data structure and sending them to the user. In the two server setting ($s=2$), our PIR protocols achieve $T_2 = n^{0.82}$, matching the server time of the state-of-the-art schemes of Henzinger and Ragavan (EUROCRYPT 2026) while shrinking their storage from $O(n\sqrt{\log n})$ to $n+1$ bits. With $s \geq 3$ servers, our PIR protocols retain the $n+1$ bits of storage and additionally improve on the server time of all prior information-theoretic $s$-server schemes with $n^{1+o(1)}$ storage: for example, achieving $T_3 = n^{0.74}$ and $T_{10} = n^{0.61}$ (previously $n^{0.79}$ and $n^{0.75}$). Asymptotically, as the server count $s$ grows, we shrink the number of servers required to achieve a given server-work exponent from $s^{3.9}$ to $s$. Our results draw inspiration from matching-vector techniques (Efremenko, STOC 2009), which we generalize to handle degree-two computations in the exponent. Using this generalization, we build doubly-efficient PIR from the new intermediate abstraction of Fourier-sparse cone-delta functions. Then, we construct such Fourier-sparse cone-delta functions via a connection to modular forms and complex analysis: if a Fourier-sparse cone-delta function does not exist, then there exists a modular form which has too many roots, contradicting the valence formula.

Multi-Hop Functional Encryption

Public-key cryptography

Show abstract

Public-key cryptography

In this paper, we initiate the study of multi-hop functional encryption ($\mathsf{MHFE}$), a new primitive for computing over encrypted data in recursive and multi-stage workflows while enabling controlled release of intermediate outputs. $\mathsf{MHFE}$ supports dynamic directed-acyclic computation graphs in which each node is labeled by a function and is equipped with a restricted secret key that reveals only that node's output, yet the computation can continue downstream on a forwardable encrypted state. In doing so, $\mathsf{MHFE}$ simultaneously overcomes (i) multi-hop fully homomorphic encryption's need for a globally trusted, always-online decryption key to reveal intermediate values, (ii) standard FE's lack of a native mechanism for forwarding reusable encrypted state across stages and handling evolving datasets without a fresh recomputation, and (iii) Multi Party Computation's deployment friction stemming from interaction and liveness/coordination requirements (at the cost of a central key-issuing authority). We formalize $\mathsf{MHFE}$ security via the simulation paradigm extending standard FE collusion resistance to the multi-hop setting; this simulation-based notion captures the intended information flow in recursive computations most accurately by characterizing an adversary's entire view as simulatable given only the authorized intermediate outputs. Our security games impose a natural topological-order on queries: a hop key for a node may be requested only after the ciphertexts/keys on all incoming edges to that node have been fixed. We then give the first generic simulation-secure construction of public-key $\mathsf{MHFE}$ for all polynomial-size circuits from any IND-secure standard FE for circuits.

Undine: Distributed Extendable Merkle Tree Storage with Private Retrieval and Efficient Reconfiguration

Cryptographic protocols

Show abstract

Cryptographic protocols

Clients of transparency logs, public-key directories, and shielded blockchain pools require authenticated access to an ever-changing Merkle tree, without storing it in full or revealing which entry they open. We seek to distribute storage and query work across independent servers as the data grows and participants join, leave, change their shares, or misbehave. We present Undine, which combines a distributed Merkle tree encoding with private retrieval from independently-maintained fragments. Maintainers can choose and efficiently adjust the size of their stored fragments, to offer a flexible tradeoff against the number of maintainer replies needed for authenticated data reconstruction by clients. Maintainers can also perform authenticated updates and appends, at a write cost of just twice the number of modified Merkle nodes. Undine uses a linear encoding of the Merkle tree nodes to divide evenly the storage and retrieval load across maintainers. This is combined with a private information retrieval (PIR) protocol that operates directly over the linearly-encoded fragments. Undine avoids repeated storage and computation for nodes shared by Merkle paths across records, producing the same PIR replies with work over tree values linear in the filled prefix. Record sizes adapt as the prefix grows to balance query and reply sizes. Clients verify against the Merkle root, without commitments to individual PIR databases. Computational query privacy holds against any coalition. Undine is also secure against selective-failure leakage (i.e., deductions from acceptance), up to the PIR backend's correctness error, given enough timely honest replies, fixed public timing, and no reply-dependent follow-up. We evaluate UndineLog, our append-only implementation of Undine combined with YPIR. On a height-50 sparse Merkle tree with a 4GiB prefix of nonempty 32-byte leaves and a reconstruction threshold of 64, a maintainer replies in 100ms (single-core); a client can process 192 replies from maintainers and reconstruct a verified opening in 380ms, even with 64 corrupted replies. Scaled up to 1TiB and 256 threshold , a maintainer answers in 1.13s. Existing shielded pools can use this service without consensus changes.

The Closest Vector Problem on Gadget Lattices: Efficient Algorithms and Voronoi Geometry

Public-key cryptography

Show abstract

Public-key cryptography

Gadget lattices are a prominent family of lattices widely used in lattice-based cryptography, error-correcting codes, and computational complexity. We present efficient algorithms for the Closest Vector Problem (CVP) on power and CRT gadget lattices and their duals, handling arbitrary real-valued target vectors. For the parity-check power gadget lattice, we give a practical, deterministic O(n) linear-time exact CVP solver based on a new, specialized "deferred greedy" graph-cut technique. Through an explicit characterization of the Voronoi cell, we provide a comprehensive analysis of existing decoders: we prove that the standard BDD algorithm of Micciancio and Peikert (2012) unexpectedly solves CVP exactly for odd base b and integer targets, but degrades to a worst-case approximation factor of n^0.5 for binary base b=2 and continuous targets. Furthermore, we prove that standard pruned sphere decoding requires exponential time exp(Omega(n)) even when using a geometrically optimal basis. For the dual (generator) power gadget lattice, we construct an obtuse superbasis---proving for the first time that it is a lattice of "Voronoi's first kind"---which yields a polynomial-time O(n^3) exact CVP algorithm via graph min-cut reductions. Geometrically, we determine all successive minima and enumerate the facets of their Voronoi cells. In particular, we show that while the parity-check lattice has a sparse Voronoi cell with n^2+n facets, the generator lattice reaches the theoretical upper bound of 2(2^n-1) facets. Finally, we observe that CRT gadget lattices and their duals admit an orthogonal basis, yielding trivial linear-time CVP algorithms.

An Agile Homomorphic Encryption and ML-KEM Scheme for Privacy-Preserving Health Data Processing

Implementation

Show abstract

Implementation

The storage and processing of health data raise serious privacy con- cerns; therefore, the data must be encrypted. Fully Homomorphic Encryption (FHE) allows computations on encrypted data, which makes it a very promising technology in this context. However, although the efficiency of FHE algorithms has improved in recent years, they remain very complex. The security of several prominent FHE schemes is based on variants of the Learning With Errors (LWE) problem, which is also the basis of Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM), the new post-quantum standard for asymmetric encryption. In this paper, we propose an agile cryptographic scheme – combining ML-KEM and BGV – that allows efficient implementations in an embedded use case. We describe the parameter selection for the proposed scheme and show its feasibility with a proof-of-concept implementation.

Twisted Towers: A Faster and Fully Costed SexTNFS Attack

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

We study the Special exTNFS attack on discrete logarithms in the target group $\mathbb{G}_T$ of BLS12-381. We give a (6,2) design in which every step is priced in one instruction-level model: relation collection, cofactorisation, filtering, linear algebra, the Block Wiedemann generator and both individual logarithms, at success probability at least 0.39. The design rests on an explicit twisted tower. The sextic base field has an involution $\sigma$ and a unit $c$ with $c\,\sigma(c)=-1$, so $\tau:(y,x)\mapsto(\sigma y,cx)$ has order 4 and acts on $\mathbb{F}_{p^{12}}$ as $\mathrm{Frob}^3$. Relations and ideals then come in orbits of four. The quotient linear system has Gaussian-integer entries read modulo $r$, and ten Schirokauer maps suffice. A norm-2 element of the base field enables a coset sieve. We also observe that yield estimates over TNFS coefficient cubes count unit multiples $(\varepsilon a,\varepsilon b)$ as distinct relations. For the valid polynomial pair closest to the published BLS12-381 design, only $2^{-2.81}$ of the smoothness-weighted cube points give distinct relations. Under stated heuristics the ledger is $2^{115.72}$ dense $\mathbb{F}_{p^{12}}$-multiplication equivalents, about $2^{130}$ AArch64 instructions. Under our instruction model and transferred pricing assumptions, the design is estimated to cost 0.74 to 1.08 bit less (about 0.8) than a fundamental-domain version of the published design. Under the published cost models the difference ranges from 0.57 bit in our favour to 0.19 bit against. Nothing was run at full size, and the practical security of BLS12-381 is unchanged.

γ₁₁: One Selected Contact, Two Linked Blocks — the macadamia 0030

Foundations

Show abstract

Foundations

This paper is one of five companion papers completing the proof of $\gamma_{11}=4/\sqrt[11]{972}$ announced in the root paper and assembled in “A Focus on Hermite Constant 11”. The root paper reduces a lattice of rank 11 with minimum 4 and determinant below 972 to a chain of sections of ranks 11, 10 and 9 whose rank-9 member is admissibly marked by one of 4 487 813 perfect forms; ten of them, the macadamias, lie under an actual lattice of rank 10 and need proofs of their own. We settle the first, the form 0030:030301719 of $\Lambda_9$ under $\Lambda_{10}$, where the bound has little margin. The argument selects one contact of the reference lattice from the actual metric, keeps the off-diagonal column shared by two eight-dimensional blocks of the section metric, applies one determinant–trace theorem to both blocks, and closes with a rational cover of three scalar parameters. The proof is computer-assisted: its finite inputs are three outer-range covers, two middle-range covers with 10 498 and 1 140 leaves, an annulus tree with 3 567 leaves and four smaller trees, every leaf checked in exact rational arithmetic.

γ₁₁: Reduction by Sections — the macadamias 0019 and 0017

Foundations

Show abstract

Foundations

The root paper of this series reduces the value $\gamma_{11}=4/\sqrt[11]{972}$ of the Hermite constant in dimension 11 to a statement about chains $L\supset M\supset N$ of lattices of ranks 11, 10 and 9 whose rank-9 member lies over one of 4 487 813 perfect forms of rank 9; the $\gamma_{11}$ paper settles all of them but ten, the macadamias. This paper settles two of the ten: 0019:030884313 (the form $P_S$ of the root paper, an extension of $E_8$ by a simplex vector) and 0017:001746552 (the form $P_K$, KAPPA9.2). We prove that every admissible chain whose rank-9 member is admissibly marked by the form has $\det L\ge 972$. The method is a reduction by sections: for 0019 the nine simplex contacts turn the problem into one about an eight-dimensional covariance matrix, and a tree of 17 347 nodes with 7 743 scalar determinant witnesses covers the remaining box; for 0017 a two-vector flag bound and the decomposition of the section metric along a short-dual plane and its rank-seven kernel reduce the problem to five parameters, covered by a tree of 3 010 595 nodes. The proof is computer-assisted: every finite check is stated as a Computational result, and the verification records in the certificate archive are named.

γ₁₁: A Finite Spectral Relaxation — the macadamia 0008

Foundations

Show abstract

Foundations

The root paper of this series reduces $\gamma_{11}=4/\sqrt[11]{972}$ to a statement about chains of lattices $L\supset M\supset N$ of ranks 11, 10 and 9, cut along shortest dual vectors, whose rank-9 member lies over one of 4 487 813 perfect forms. Ten of these forms, the macadamias, lie under an actual lattice of rank 10 of small determinant and need a proof at rank 11, where the bound 972 is attained. This paper settles the form 0008:022143116, which lies under a section of $K_{11}$ with 276 minimal vectors: every admissible chain whose rank-9 member is admissibly marked by this form has $\det L\ge 972$. In coordinates aligned with the form, the section metric is $S=I+E$ with three blocks of size three. Two sufficient flag tests come from short dual covectors and integral triangles; local reductions, proved from rational comparisons and Bernstein or Sturm certificates, remove explicit regions of the parameters; every remaining real spectrum is mapped, with explicit allowances, into a finite relaxation on 81 grid nodes, which a tree of 400 nodes with 1 091 rational certificates, replayed in two exact arithmetic implementations, excludes. The proof is computer-assisted, with explicit finite checks stated as one Computational result.

γ₁₁: Contact Geometry — the macadamias 0001, 0014, 0059 and 0015

Foundations

Show abstract

Foundations

The root paper of this series reduces the value $\gamma_{11}=4/\sqrt[11]{972}$ of the Hermite constant to a statement about chains of lattices $L\supset M\supset N$ of ranks 11, 10 and 9 whose rank-9 member lies, in the sense of Voronoi, over one of 4 487 813 perfect forms; the $\gamma_{11}$ paper excludes all of them but ten, the macadamias. This paper settles four macadamias, the forms 0001:010488327, 0014:001749549, 0059:016902802 and 0015:030291998, by one method: the geometry of the contacts of the form. A section frame of short dual vectors forces the first gluing of $M$ over $N$ to lie near one of finitely many coherent centres; at such a centre the rank-10 metric is compared with an explicit reference lattice, whose Delaunay cells and contact identities give a uniform bound on its covering radius; and a primitive-extension inequality turns that bound into $\det L\ge 972$. The proof is computer-assisted: every finite check it uses is stated as a Computational result with the records of the certificate archive that certify it, and all comparisons are between explicit rational numbers.

A Focus on Hermite Constant 11

Foundations

Show abstract

Foundations

This paper assembles the dimension-eleven argument in a series on the Hermite constants in dimensions ten, eleven and twelve. The root paper reduces a hypothetical lattice of minimum 4 and determinant below 972 to a chain of sections of ranks eleven, ten and nine. Its rank-nine section is marked by a perfect form below an explicit determinant cutoff. The global finite computation leaves 4 487 813 candidate forms and excludes all but ten by certificates. We state the mathematical content of these certificates, describe their data and checking rules, and prove why every valid certificate excludes the corresponding form. The four formats are trace, domain, glue and tree certificates; each tree must cover its entire stated domain. One of the ten remaining cases, 0052:005247066, is treated here by a complete gluing cover. Five companion papers settle the other nine. We also prove the common inequalities used by those local arguments. The resulting bound is $\gamma_{11}=4/\sqrt[11]{972}$, conditional on the attributed rank-nine classification, the rank-ten census and the stated global and local finite checks.

The Hermite Constants in Dimensions 10, 11 and 12

Foundations

Show abstract

Foundations

This paper introduces a series of seven papers establishing $\gamma_{10}^{10}=4^{10}/768$, $\gamma_{11}^{11}=4^{11}/972$ and $\gamma_{12}=4/\sqrt{3}$, under the attributed classification of perfect forms of rank nine and the explicitly stated computational inputs. The argument treats the dimensions in order. In dimension ten, a section orthogonal to a shortest dual vector is compared with a perfect form. A completed exact census leaves three possible reference forms, and matrix inequalities exclude a determinant below 768 in each case. In dimension eleven, two successive sections give a chain of ranks eleven, ten and nine. The dimension-ten bound controls the determinant of the last section. The verified global census and preliminary certificates reduce the problem to ten local cases: nine are treated in five companion papers, and one in “A Focus on Hermite Constant 11”. The local arguments combine contact geometry, section bounds and finite rational covers. Mordell’s inequality then gives the dimension-twelve upper bound, matched by the Coxeter–Todd lattice. We prove the common reduction, explain the dependency between the papers, and state exactly which finite assertions must be checked. The accompanying Lean development verifies the complete analytic deduction from those inputs; external exact checkers verify the large certificate data.

Incrementally Verifiable Oracle Aided Computation

Cryptographic protocols

Show abstract

Cryptographic protocols

Incrementally verifiable computation ($\IVC$) allows a prover to maintain a short proof that can be efficiently updated after each computation step, without retaining or recomputing the preceding execution. In the context of AI safety, the need for incremental verification is particularly important, as AI systems interact with users over time and perform further computation after each interaction. However, standard $\IVC$ schemes do not directly address a crucial feature of AI tasks: their dependence on external information and expertise. Indeed, the UK AISI Alignment Team~\cite{IrvingM25} emphasizes that verification methods for AI safety should accommodate access to external information and human judgment. This is the topic of this paper. We construct $\IVC$ schemes for {\em oracle-aided} computations under the Learning with Errors ($\LWE$) assumption by first constructing succinct non-interactive arguments ($\SNARG$s), and then extending them to the incremental setting. We consider the following two settings, where below, $\lambda$ is the security parameter, $n$ is the input length, and $T$, $S$, and $Q$ are the time, space, and oracle-query bounds. \begin{itemize} \item \textbf{Robust computations.} For bounded-space computations, including non-deterministic computations, in which every accepting purported execution on a false input contains at least an $\varepsilon$-fraction of incorrect oracle answers, we construct {\em privately verifiable} $\SNARG$s and $\IVC$. For $\IVC$, the corresponding robustness condition is imposed on the claimed configuration. Public parameters, private verification keys, and proofs have length $\poly(\lambda,S,\log T,1/\varepsilon)$, and verification uses $O(\lambda/\varepsilon)$ oracle calls. We complement this result with a lower bound ruling out (deterministic) publicly verifiable $\SNARG$s and $\IVC$s with public parameters of length $o(n)$, and $o(Q)$ verifier oracle queries. \item \textbf{Signed oracles.} For oracles that digitally sign their query-answer pairs, we construct publicly verifiable $\SNARG$s and $\IVC$ without a robustness assumption, and with oracle-free setup and verification. Public parameters and proofs have length $\poly(\lambda,S,\log T)$. For deterministic computations with oracle query and answer lengths $\poly(\lambda,\log T)$, we remove the dependence on $S$, obtaining public parameter and proof lengths $\poly(\lambda,\log T)$. \end{itemize} All our constructions have adaptive completeness and soundness. Sub-exponential hardness of $\LWE$ suffices for all constructions; polynomial hardness suffices in the deterministic signed-oracle setting when $T$ is polynomially bounded in $\lambda$. All cryptographic assumptions are required to hold even given access to the underlying oracle.

Revisiting the Security of OleF, t-OleF, and OlÆF

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

We revisit the security of OleF, t-OleF, and \olaef\ and identify two independent security flaws. First, we establish a mask-compensation relation between continuation and termination processing in OleF and t-OleF. Exploiting this relation, we construct a two-encryption-query distinguisher against OleF with advantage $1-2^{-2n}$. We further give two concrete AXU hash families for which the same attack applies to t-OleF, revealing flaws in the original DOSPRP and SPRTOP security proofs. We extend these attacks to \olaef\ through valid encodings, breaking its privacy and integrity. In particular, the integrity forgery succeeds with probability $1$ under full-domain verification when the target expansion length is $1$ and extends to larger expansion lengths under suffix-only verification. Second, we refute the claimed ideal RUP integrity bound for variable-expansion online authenticated encryption. Even with an ideal tweakable online permutation, prior unverified decryption queries at smaller expansion lengths can reveal part of the target authentication suffix. We construct counterexamples showing that two such decryption queries and one forgery attempt achieve a success probability of $3/8$, exceeding the claimed bound of $1/4$. We also derive a general expression for the forgery success probability. Finally, we discuss the corresponding repairing

Threshold Batched Attribute-Based Encryption from Succinct LWE

Public-key cryptography

Show abstract

Public-key cryptography

Batched identity-based encryption (BIBE) enables a single compact key to decrypt ciphertexts associated with a designated batch of identities. Batched attribute-based encryption (B-ABE) extends this functionality to attribute-based access control, while threshold batched attribute-based encryption (TB-ABE) further distributes the decryption capability among multiple parties. Existing constructions of TB-ABE rely on bilinear pairings, motivating post-quantum alternatives. In this work, we give, to the best of our knowledge, the first lattice-based candidate construction of TB-ABE. Our construction combines the succinct polynomial-digest mechanism underlying lattice-based BIBE with key-homomorphic evaluation for arithmetic-circuit policies and linear secret sharing. We prove security under the ℓ-succinct LWE assumption, assuming the required share-uniformity property of the underlying ramp threshold sharing scheme.

Designing Quantum-Safe Network Architectures via Certified Randomness Distribution

Applications

Show abstract

Applications

We propose an alternative design for quantum-safe network architectures, based on distributing certified randomness generated by different trust-level QRNGs. Our modular methodology aggregates high-trust entropy from upper network layers with local contributions, enhancing the security guarantees of locally available random sequences. Leveraging the physical guarantees of QRNGs and symmetric-key cryptographic algorithms for node authentication, our approach enables immediately deployable, quantum-safe infrastructures. Such a paradigm bypasses the practical security limitations of current QKD-based solutions, while avoiding massive key sizes and latency inherent to asymmetric PQC implementations.

The Minimum Bucket Capacity for Reliable Path ORAM

Cryptographic protocols

Show abstract

Cryptographic protocols

Path ORAM hides memory access patterns by storing $N$ data blocks in a binary tree whose buckets have capacity $Z$, using a client-side stash for blocks that cannot be placed in the tree. Smaller buckets reduce storage and communication costs but increase the risk of stash overflow. The revised Path ORAM analysis in 2014 established an exponentially decreasing stash overflow probability for $Z \geq 5$. Experiments suggest small stashes at $Z=4$ and substantially larger ones at $Z=3$. However, it remained unknown whether $Z=4$ admits a uniform exponential stash bound or whether such a bound is impossible at $Z=3$. We establish a sharp threshold at $Z=4$ for binary Path ORAM with tree depth $L=\lceil \log_2 N \rceil$. For $Z=4$, we prove that, uniformly over all database sizes and fixed access sequences, the stash size $S$ after the final refill satisfies \[ \Pr[S>R] \leq \frac{23}{28}\left(\frac{5}{7}\right)^R \] for every integer $R \geq 0$. For $Z=3$, we exhibit a family of instances on which a single sequential scan of all $N$ blocks produces a stash of size $\Omega(N)$ with probability bounded away from zero. Thus, four is the minimum bucket capacity admitting a uniform exponential stash bound: a logarithmic stash suffices for polynomial-length executions with inverse-polynomial failure probability at $Z=4$, whereas at $Z=3$ no sublinear stash can make the overflow probability vanish uniformly. Our proofs connect the actual Path ORAM process with dependent node loads to an auxiliary model with independent geometric node loads. This independence enables a recursive analysis of overflow that avoids the union bound over rooted subtrees used in the previous $Z=5$ proof. The main challenge is to transfer bounds from the auxiliary model to the actual process, which requires different techniques for the upper and lower bounds. For $Z=4$, we develop a two-stage randomization argument that bounds the actual process's exponential overflow moment by that of the auxiliary model. For $Z=3$, we develop a local continuous-time approximation with controlled errors that transfers an overflow surplus from the auxiliary model to the actual process, yielding the linear stash lower bound. Together, these arguments establish the sharp threshold at bucket capacity four.

How to Revoke Users in Encryption Schemes?

Public-key cryptography

Show abstract

Public-key cryptography

Revocation is essential for keeping encryption secure as keys leak, devices are compromised or users leave the system. We revisit the problem of revocation for encryption schemes and give, to our knowledge, the first approach combining anonymous, collusion-resistant revocation with unchanged keys and access rules, succinct ciphertext overhead and a trustless revocation authority, i.e. that cannot decrypt. Revoking a user publishes one random-looking pseudonym, without telling encryptors whose key was revoked. A party can decrypt future ciphertexts only if it is unrevoked and satisfies the original access decryption rule. Our core observation is that revocation is, at heart, witness encryption for the statement that one satisfies the access rule and that the pseudonym bound to one's key has not been revoked. Although general-purpose witness encryption remains far from practical, we observe that the statements arising from revocation are simple and algebraic, and we show that they fall within the special-purpose framework of Garg et al. (CRYPTO 2025), which compiles short arguments of knowledge (called ``gadgets'') into efficient witness encryption using bilinear groups. Our technical contribution is a pair of succinct non-membership gadgets for this framework, one for a single hidden pseudonym and one that certifies non-revocation jointly for all users selected by an access rule. Both gadgets are generic and modular, as they compose with the gadgets expressing a wide range of access rules, and thus provide a single revocation mechanism that is designed once and reused across different encryption schemes, without redesigning either the scheme or the revocation. These gadgets yield the following applications. First, we give a black-box transformation adding revocation to arbitrary independently instantiated public-key encryption, with constant-size cryptographic ciphertext overhead. For unrevoked users, confidentiality continues to rely only on the security of the underlying scheme. Then, we demonstrate applications to advanced encryption scheme, constructing revocable schemes for distributed broadcast, registered attribute-based, and registered threshold encryption, with succinct cryptographic ciphertext components and threshold decryption shares. We prove adaptive security of our schemes in the generic bilinear-group and random-oracle models.

Round-Optimal Statistical Verifiable Secret Sharing with Polynomial Complexity

Cryptographic protocols

Show abstract

Cryptographic protocols

Verifiable secret sharing (Chor, Goldwasser, Micali, and Awerbuch; FOCS'85) is a central primitive in secure computation, and its round complexity has been studied extensively. Rabin and Ben-Or [STOC'89] established the feasibility of statistical security up to $t<n/2$ corruptions, and Patra, Choudhary, Rabin, and Rangan [Crypto'09] showed that three sharing rounds are necessary. The work of Applebaum, Kachlon and Patra [STOC'23] introduced the first round-optimal VSS with three rounds of sharing and one round for reconstruction, albeit with exponential communication in the number of parties. We give the first round-optimal statistical VSS that has polynomial communication and computation for $t<n/2$. This resolves the efficiency question left open by Applebaum, Kachlon and Patra. The protocol is obtained from a new notion of weak secret sharing, in which the reconstruction-time freedom of a corrupt dealer is limited to choosing verification keys, which is of independent interest.

From Degree Three to Degree Two: Statistical Randomized Encodings for All Functions

Foundations

Show abstract

Foundations

A randomized encoding represents a function by a simpler randomized map whose output allows recovery of the function value while revealing essentially no further information about the input. Perfectly correct and perfectly private encodings of degree three over $\F_2$ are known for every Boolean function, but degree two cannot provide these guarantees for all functions (Ishai and Kushilevitz, FOCS 2000 and ICALP 2002). Whether degree two suffices when small statistical errors are allowed in both correctness and privacy has remained open. We construct quadratic randomized encodings of every Boolean function with exponentially small correctness and statistical privacy errors. The degree bound holds jointly in the input bits and independent uniform random bits, and the construction, encoder, decoder and simulator have complexity polynomial in the total size of mod-2 branching programs computing the function's output bits and in the security parameter. Our encodings also achieve decomposability and output locality three, meaning that each encoded bit depends on at most three input and random bits. These results resolve the degree-two and locality-three questions for statistical randomized encodings (Ishai, 2013). As an application, we obtain one-way functions of optimal output locality three from one-way functions in polynomial-time uniform $\mathrm{NC}^1$, improving the previous locality-four result under the same assumption (Applebaum, Ishai and Kushilevitz, FOCS 2004). We also obtain quadratic multiparty randomized encodings with negligible correctness and statistical privacy errors against semi-honest corruption of any coalition of parties. Previous general constructions for $k\ge4$ parties provided perfect correctness and privacy against at most $\lfloor 2k/3\rfloor$ corruptions (Applebaum, Ishai, Karni and Patra, CRYPTO 2022). Through known reductions, our encodings yield non-interactive reductions of every functionality to a fixed three-party functionality and three-round protocols in the two-round OT-hybrid model, with negligible correctness and statistical privacy errors against every coalition. They also yield non-interactive client--server protocols for every function whenever a majority of the servers is honest, even when corrupted servers collude with any set of clients. This server threshold is optimal in this model when privacy is required against arbitrary client coalitions.

SoK: Understanding Virtual Machines over Fully Homomorphic Encryption

Applications

Show abstract

Applications

We survey the current literature on fully homomorphic encryption (FHE) from a virtual machine (VM) perspective. We observe that programs behave in an intrinsically different way over FHE than on plaintext, forming a new paradigm of computation that is fundamentally constrained by the obliviousness of data. To better understand the computational properties, we compile more than 125 works to formulate a cross-layer systematic view of FHE VMs, with a special focus on understanding the concrete programming models over encrypted data. In particular, we identify three distinct forms of VMs over FHE, namely, the SISD VM, the SIMD VM, and the hybrid VM. To aid the cross-layer systematization, we also discuss how current FHE compilers and hardware accelerators can be applied to enhance the usability and performance of the respective VMs. In the experiment, we test eight VM instructions with varying precision as well as two end-to-end application programs to quantitatively assess the concrete design trade-offs for each of the VM paradigms. We conclude that FHE VMs of different types exhibit distinct utility and performance characteristics, necessitating new design methodologies to be developed in a cross-layer manner.

Jazzline: Composable CryptoLine Functional Correctness Proofs for Jasmin Programs

Implementation

Show abstract

Implementation

Jasmin is a programming language for high-speed and high-assurance cryptography. Correctness proofs of Jasmin programs are typically carried out deductively in EasyCrypt. This allows generality, modularity and composable reasoning, but does not scale well for low-level architecture-specific routines. CryptoLine offers a semi-automatic approach to formally verify algebraically-rich low-level cryptographic routines. CryptoLine proofs are self-contained: they are not integrated into higher-level formal verification developments. This paper shows how to soundly use CryptoLine to discharge subgoals in functional correctness proofs for complex Jasmin programs. We extend Jasmin with annotations and provide an automatic translation into a CryptoLine model, where most complex transformations are certified. We also formalize and implement the automatic extraction of the semantics of a CryptoLine proof

Registration-based Encryption with Logarithmic Registration

Public-key cryptography

Show abstract

Public-key cryptography

Registration-based encryption (RBE) preserves IBE's identity-only encryption interface while eliminating key escrow: users generate their own keys, and a Key Curator manages only registered public keys. However, this design introduces a new challenge: user registration, since every joining user rrequires KC to update the registry. Although theoretical RBE constructions achieve polylogarithmic registration, they rely on costly cryptographic techniques and remain impractical. In existing deployable black-box RBE, registration takes $O(\sqrt{N})$ time ($N$ denotes the maximum user capacity). This gap between theoretical registration efficiency and deployability makes registration a key performance bottleneck for large-scale deployments of pairing-based RBE. This work presents a black-box pairing-based RBE construction under the decisional $(R,S,T,f)$-Diffie-Hellman assumption. Build on the multilinear tree, when registering a user's public key, KC updates only the corresponding root-to-leaf path associated with the user. Therefore, registration in our construction takes $O(\log \sqrt{N})$ time for the maximum user capacity $N$. Moreover, we provides membership and non-membership verification, and their batch verification supports to check registration status of multiple users. Experiments show registration and key generation complete in milliseconds when $N=10^7$. Compared with Glaeser et al. (CCS'23), our scheme accelerates registration by up to \(158\times\) and key generation by up to \(230\times\) with practical overheads.

Overcoming Padding in Cryptography via Hardness of Certifying Random Strings

Foundations

Show abstract

Foundations

Modern cryptography relies on a provable security paradigm where the security of a primitive is established from the intractability of one or more computational problems. Hybrid arguments are central to this approach. Somewhat unexpectedly, many security proofs in the literature that use this methodology require hybrids with description-size larger than the real scheme. To argue security, the real scheme is artificially padded to match this size. This so-called “superfluous padding” phenomenon is surprisingly commonplace and poses a barrier to achieving succinct cryptographic primitives where the size of the scheme parameters does not grow with the input length. We present a framework to eliminate padding in cryptography. We demonstrate several applications, including rate-1 iO, succinct (and extractable) witness encryption and succinct non-interactive arguments with short CRS for subclasses of NP, and multi-input functional encryption for functions with unbounded arity. To obtain our results, we establish a new connection between cryptography and proof complexity. Central to our approach is the notion of proof-complexity generators (PCGs) [Krajíček'01, Alekhnovich, Ben-Sasson, Razborov, Wigderson'04], which, informally speaking, formalizes the hardness of certifying random (incompressible) strings with propositional proof systems. Our applications are derived from a master theorem that lifts cryptographic security on “compressible instances” to security on any instance under the existence of PCGs. Due to its broad scope, this theorem might find future application

Constructions of Boolean Correctors with Optimal Nonlinearity and Vectorial Correctors Beyond Optimal Linear Correction Order

Foundations

Show abstract

Foundations

Correctors are postprocessing functions that reduce or eliminate statistical bias in raw bitstreams produced by physical noise sources in true random number generators. In this paper, we develop a framework based on binary Krawtchouk polynomials for analyzing and constructing Boolean and vectorial correctors. This framework reformulates the Walsh-layer criterion into finite moment constraints on support-layer counts and preimage-layer counts. We also establish universal upper bounds on the nonlinearity of correctors, and necessary conditions on the achievable correction order. For Boolean functions, we prove that $(n-1)$-correctors are either the parity function or its complement. Then we characterize the support-layer profiles of $(n-2)$- and $(n-3)$-correctors and establish upper bounds on nonlinearity. For $n=2^k\ge 8$, a self-addressing construction yields $(n-2)$-correctors achieving the optimal nonlinearity $2^{n-1}-2^{n-1}/n$ with resiliency $n/2-2$ and algebraic degree $k+1$. Notably, this provides the first known infinite family of nonlinear correctors achieving both optimal correction order and optimal nonlinearity for that order, while having a resiliency strictly lower than the correction order. Furthermore, using constant-weight addressing, we construct $(n-d-1)$-correctors that asymptotically meet the nonlinearity upper bounds for every fixed $d\ge 1$. Our profile characterization also reveals inherent limitations of injective Maiorana--McFarland constructions at correction order $n-3$. For vectorial functions, we construct nonlinear $(s(2^m-1),m,s2^{m-1}+\ell-1)$-correctors for every $m\ge 2$ under certain conditions on $s$ and $\ell$, with resiliency at most $s2^{m-1}-2$. To the best of our knowledge, this is the first infinite family of nonlinear correctors whose correction order simultaneously exceeds that of optimal linear corrector and its own resiliency. Finally, we introduce a secondary construction that lifts these vectorial correctors to larger input dimensions while preserving their correction-order advantage. This approach yields a nonlinearity of $2^{n-1}-2^{n-n_0-1}$, where $n_0$ is the input dimension of the base corrector, along with explicit resiliency and a flexible algebraic degree.

More Keys, Less Commitment: Key-Committing Attacks on BBB Accordions via Encode-then-Encipher and a Key-Committing Transform

Secret-key cryptography

Show abstract

Secret-key cryptography

Cryptographic accordions with beyond-birthday-bound (BBB) security are being actively studied in connection with NIST’s ongoing standardization effort. We show that BBB security of an accordion does not necessarily strengthen key commitment of AE built from it: in many BBB accordions, additional keys introduced for BBB security give an adversary extra degrees of freedom. Exploiting this observation, we present $O(1)$ key-committing attacks on a broad range of AE schemes built from BBB accordions, mostly via the Encode-then-Encipher (EtE) paradigm, including CHCTR2, eCTR-based accordions, THCTR, HCTR+, TCT2, and bbb-ddd-AES under a natural polynomial-hash instantiation. To address this issue, we propose CACH, a black-box transform from BBB-secure accordions to robust AE (RAE) with key-committing security. CACH achieves BBB multi-user RAE security and achieves $t/2$-bit key-committing security with a $t$-bit tag for $n \le t \le 2n$ in the ideal-cipher model. CACH uses only AES-based components and supports all AES key sizes, making it compatible with NIST’s design goals. We instantiate CACH with CHCTR2. CACH-CHCTR2 with AES-256 outperforms EtE-HCTR2 with Rijndael-256 and EtE-CHCTR2 for short messages.

QUASI: Post-Quantum Quorum Attestation of Pre-Validated Statements

Cryptographic protocols

Show abstract

Cryptographic protocols

We present QUASI, a newly conceived class of protocols that enable a group of parties to produce a publicly verifiable attestation about a pre-validated statement. Designed for quorum-based systems, QUASI enables parties to attest to external entities that the statement is valid. Surprisingly, each party need not sign the entire statement: authenticating only a small subset of symbols suffices for the quorum to attest to the whole. A simple deterministic construction illustrates this possibility. Built purely from hashing and error correction, QUASI achieves small per-party contributions and low attestation generation and verification costs, without relying on SNARKs for aggregation. Our main contribution is a randomized construction achieving reductions of more than $10\times$ in per-party contribution size and hash computations for generation and verification, compared with full hash-based signatures. QUASI is a generic primitive supporting diverse applications. Two principal use cases are external attestation for signature-free consensus, enabling clients to verify statements about committed state; and preprocessing for SNARK-based aggregation, compounding QUASI's savings with succinct-proof compression.

Pastel: Single Secret Leader Election with Private Weights

Cryptographic protocols

Show abstract

Cryptographic protocols

A single secret leader election (SSLE) protocol allows an election of exactly one leader among $n$ parties in a secrecy-preserving manner, where only the elected leader knows it has won until it publicly announces and claims leadership. Motivated by proof-of-stake blockchains where stakes are stored in an encrypted or committed form for the sake of privacy, we design and implement the first SSLE protocol with private weights. Each party's probability of winning an election in our protocol is weighted by stake, and these weights are private. Prior schemes in the literature only allow probabilistic (i.e. expectation of one but can be zero or many leaders) elections in the same setting. Preserving privacy also means public verification is paramount in order for a protocol to be practically reliable. In this respect, our protocol achieves security against malicious adversaries with a concrete implementation. In particular, we concretely implement the needed zero-knowledge proofs and thus do not rely on slashing (financial penalties) to achieve end-to-end malicious security, though slashing can still serve as a performance optimization. Along the way, we observe that previous SSLE protocols in a setting without private weights (either unweighted or with public weights) are either maliciously secure with implementation or post-quantum secure but not both, while our protocol achieves both.

An improved algorithm to solve the isogeny problem in dimension 2 with precomputation

Public-key cryptography

Show abstract

Public-key cryptography

We give a new algorithm for the superspecial isogeny problem in dimension $2$. After a one-time precomputation depending only on $p$ (which succeeds with overwhelming probability), each instance is solved in expected time and memory $p^{3/4+o(1)}$. This result is unconditional, relying on no heuristics. Including the precomputation, a single instance is solved in time $p^{19/23+o(1)}$, improving on the $p^{1+o(1)}$ of the Costello-Smith algorithm. The improvement holds even with the same memory as (the rigorous version of) their algorithm. The key ingredient is an algorithm that computes the equations of the Humbert surfaces $\mathcal{H}_{N^2}$ modulo $p$ for all $N$ up to a bound $D$ growing with $p$. These equations give a membership test for optimally $(N,N)$-split surfaces, which we evaluate in batches using fast multipoint evaluation. This speeds up the bottleneck of the Costello-Smith algorithm: finding an isogeny from a superspecial principally polarised abelian surface to a product of supersingular elliptic curves.

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

Cryptographic protocols

Show abstract

Cryptographic protocols

Decentralized exchanges typically give traders no execution guarantee until a block is finalized. In the meantime, external prices move, traders strategically delay submission, and block producers can influence inclusion and ordering. We introduce FirstSwap, a DEX built on a constant-function market maker pricing curve that gives traders an early pre-approval before consensus, guaranteeing inclusion and execution within their submitted price limit, with final ordering determined by limit prices rather than by a block producer. We demonstrate the benefits of trade pre-approvals in an economic model combining auction theory with CEX-DEX arbitrage. When the CEX price changes gradually, FirstSwap rewards earlier traders with better prices, discouraging strategic delay and yielding higher social welfare and gains to AMM liquidity providers than a batch auction. When the CEX price jumps abruptly, FirstSwap yields higher welfare and smaller AMM losses than fair ordering. The central challenge is delivering fast trade pre-approvals without consensus. We introduce a decentralized, scaled admissibility protocol under which each validator reserves only a fraction of the available liquidity at every price. A trader obtains approval in a single round of messages with a quorum of validators. Somewhat surprisingly, despite Byzantine validators who may approve trades arbitrarily, we show that all quorum-certified trades are jointly admissible and execute within their limits. Our protocol extends naturally to a setting where buy and sell orders can be pre-approved against each other before a block is finalized.

On Proximity Gaps for Expander Codes

Foundations

Show abstract

Foundations

Proximity gaps describe a phenomenon concerning random linear combinations of words and their distance from a linear error-correcting code. Informally, they address the following question: if a collection of words is jointly far from the code, is a random linear combination of those words likely to also remain far from the code? Motivated by applications to concretely efficient proof systems, in this note we study this question for expander codes, a class of low-density parity-check (LDPC) codes. Recent works of Goyal and Guruswami (STOC 2026) and Goyal, Guruswami, Sun, and Wootters (RANDOM 2026; arXiv 2026) establish proximity gaps approaching capacity for random LDPC ensembles, but only asymptotically and for very large degrees and field sizes, well beyond what is used in practical proof systems. We focus on general expander codes (not necessarily random) with small degree. Building on the smoothness property of expander codes due to Dinur, Sudan, and Wigderson (RANDOM 2006), we show that such codes have proximity gaps up to nearly half of the distance guaranteed by their expansion.

SNARKs from LWE via Non-black-box Reductions

Foundations

Show abstract

Foundations

We construct the first succinct non-interactive arguments of knowledge (SNARKs) from the polynomial-hardness of Learning with Errors (LWE) for a subclass of UP languages whose witness unambiguity has a polynomial-size Extended Frege ($\mathcal{EF}$) proof. Our construction achieves the following soundness guarantee: For any fixed sequence of false instances $\{x_\lambda\}_{\lambda\in\mathbb{N}}$, there exists a (non-constructive) constant $c>0$ such that, whenever the uniform random CRS length exceeds $\lambda^c$, the construction achieves infinitely-often soundness for this sequence $\{x_\lambda\}_{\lambda\in\mathbb{N}}$: for any polynomial-time cheating prover $\{\mathcal{A}_\lambda\}_{\lambda\in\mathbb{N}}$, the probability that $\mathcal{A}_\lambda$ outputs an accepting proof for $x_\lambda$ is negligible for infinitely many $\lambda$. As intermediate results, we also obtain: - SNARGs for any NP language that has polynomial-size $\mathcal{EF}$ proofs of witness unambiguity for all instances outside of the language, based on polynomial-hard LWE, achieving the same style of soundness guarantee. - SNARKs for all true instances in any language $L \in \mathsf{UP}$ where every instance has a polynomial-size $\mathcal{EF}$ proof of witness unambiguity, under polynomial hardness of LWE, without soundness guarantees for false instances. To achieve our main result, we employ a non-black-box soundness reduction. Along the way, we introduce a new logical proof system, the \emph{Cryptographic Extended Frege} ($\mathcal{CEF}$) system, which extends $\mathcal{EF}$ with rules for formalizing the indistinguishability in cryptographic security proofs. Building on the Encrypt-hash-and-BARG framework of [Jin–Kalai–Lombardi–Vaikuntanathan, STOC’24], we further obtain SNARGs for NP languages that have $\mathcal{CEF}$ proofs of non-membership, which may be of independent interest.

Actively Secure PIR from Verifiable Linear Relations over Rings

Cryptographic protocols

Show abstract

Cryptographic protocols

Privately retrieving data from a database without revealing which element is being retrieved is a fundamental problem in cryptography with many diverse applications. State-of-the-art solutions to this problem are generally based on homomorphic encryption, which offers security only against passive adversaries. In this work, we contribute to the recently introduced notion of Verifiable Private Information Retrieval (vPIR), which leverages verifiable computation to achieve security against active adversaries. We present a new sum-check based interactive oracle proof for linear relations over power-of-two cyclotomic rings, and show how to instantiate it into a vPIR protocol using Ring-LWE. Our solution is concretely efficient, offers the best possible security guarantees and is plausibly post-quantum secure. We additionally provide an open-source Rust implementation. Our server time improves on prior work's IOP by more than an order of magnitude, leading to a factor two end-to-end performance improvement. Compared to vPIR prior work, on a 4 GiB database, our offline communication and client storage are of 128 MiB, against 3.29 GiB. Preprocessing is run once per database and amortized over an unbounded number of queries.

The GGM PRF Construction is Optimal

Foundations

Show abstract

Foundations

We study the complexity of fully black-box constructions of pseudorandom functions (PRFs) from pseudorandom generators (PRGs). The seminal work of Goldreich, Goldwasser, and Micali (JACM 1986), combined with Levin’s domain-extension technique, yields PRFs that make a superlogarithmic number of adaptive calls to a length-doubling PRG. A long-standing open problem is whether fewer calls suffice for fully black-box constructions. Despite progress for restricted classes of constructions and reductions, previous results have not been able to rule out even a single-call construction in full generality. A related question asks how many calls are needed to amplify a PRG’s stretch from \(r\) bits to \(\rho>r\) bits. Our main result establishes the asymptotic optimality of the GGM construction with domain compression, both in the number of calls and in adaptivity, for length-doubling PRGs. More generally, for a PRG with seed length \(n\) and stretch \(r(n)\), we rule out fully black-box PRF constructions with \(d(n)\) adaptive rounds whenever \(d(n)\log(2+r(n)/n)=O(\log n)\), even allowing polynomially many calls per round. Our bounds hold for one-bit weak PRFs on domains of superpolynomial size. In particular, they exclude all polynomial-query nonadaptive constructions from PRGs of arbitrary polynomial stretch and require superlogarithmically many rounds when the underlying PRG doubles its input length. We further show impossibility results for fully black-box non-adaptive PRG stretch amplification. First, we show that a non-adaptive construction of a $\rho$-bit stretch PRG from an $r$-bit stretch PRG requires $\Omega(\tfrac{\rho}{r+\log n})$ calls. Second, we show that it is impossible to construct a length-doubling PRG from an $o(n)$-bit stretch PRG with non-adaptive calls. Our techniques combine and extend two prior lines of work. First, we develop a sensitivity framework that measures the effect of changing a uniformly chosen oracle entry and transfers this stability through black-box reductions, extending the sensitivity arguments of Bitansky et al. (CRYPTO 2017) and Bitansky and Degwekar (TCC 2019). Second, we extend the scoring mechanism of Alon et al. (CRYPTO 2026) and integrate it with our framework. Finally, we show that the sensitivity framework applies to constructions from one-way permutations. Specifically, we show another proof of Simon's impossibility of basing collision-resistant hash functions on one-way permutations. Our new proof can be viewed as an abstraction of the argument by Bitansky and Degwekar.

Filtered merges make deeper representation trees pay: Subset Sum and Meet-LWE

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

Dubiner's bucketing codes, used as type-class filters on representation coordinates, let a merge avoid generating matched pairs with the wrong split pattern. We show that in representation trees their main effect is to make depth pay. For random density-one Subset Sum they improve the exponent of Bonnetain, Bricout, Schrottenloher and Shen from 0.2831 (our recomputation) to 0.2690, at depth 5; no better point was found up to depth 9. For May's Meet-LWE on ternary keys they improve the asymptotic exponent by 0.013–0.023 for key weights ω ≥ 0.375. Filters can pay only at merges where most matched pairs have the wrong split pattern, and do pay where such merges bind; we show both where this holds and where it fails. A survival recursion justifies the accounting, a symmetry lemma shows that the filters cannot bias the planted solution, and simulations support the remaining heuristics.

Parallelizable modes for duplex-based authenticated encryption

Secret-key cryptography

Show abstract

Secret-key cryptography

This note enriches the SHAKE and TurboSHAKE-based authenticated encryption schemes defined by Daemen et al. at EuroS&P 2025 with parallelizable ones, while keeping their security properties. The main contribution is a new deck cipher mode, called FlightDeck, that has the ability of processing input strings similarly to KangarooTwelve and producing output strings as in counter mode, so both parallelizable. We then instantiate FlightDeck on top of the overwrite duplex (OD) construction, in turn on top of a Keccak-p permutation. Combined with a deck cipher-based mode like Deck-BO, the security of the resulting authenticated encryption schemes reduces to the PRF security of keyed (Turbo)SHAKE and to the collision resistance of (Turbo)SHAKE. Compared to the schemes defined at EuroS&P 2025, replacing UpperDeck with FlightDeck greatly improves their software efficiency as one can implement them with Keccak-p permutations evaluated in parallel.

Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions

Foundations

Show abstract

Foundations

Whether almost perfect nonlinear (APN) permutations exist in even dimension $n\ge 8$ is a long-standing open question, the big APN problem. The only example known in even dimension, on six bits, was found from a quadratic APN function that is not itself a permutation, by Carlet--Charpin--Zinoviev (CCZ) equivalence. It is therefore natural to test APN functions for CCZ-equivalence to a permutation. This amounts to finding two complementary $n$-dimensional subspaces among the zeros of the Walsh transform, which lie in $\mathbb{F}_2^{2n}$. A known necessary condition only uses their projections to $\mathbb{F}_2^n$ and cannot decide every case. We give an exact test for functions whose Walsh supports are affine, including all quadratic functions. It reconstructs the subspaces from their projections, through searches for subspaces of $\mathbb{F}_2^n$ and for constrained bilinear maps. On the benchmarked functions in dimension twelve, it lists them $39$ to $55$ times faster than the generic search of the commonly used sboxU library. We then study the functions $x^3+a^{-1}\mathrm{Tr}(a^3x^9)$, which Göloğlu and Pavlů proved not to be CCZ-equivalent to permutations when $4$ divides $n$. With their result, our computations show that this holds for every even $n\le 24$. In dimension $18$ the necessary condition is satisfied, and the new test decides the case. We conjecture this for every even dimension. We also compile $25$ classes of quadratic APN functions in dimension ten from published instances, with equivalence certificates. No function in these classes or in their switching closure is CCZ-equivalent to a permutation. All code and data are public.

Exploring the Set of APN Functions

Secret-key cryptography

Show abstract

Secret-key cryptography

An Almost Perfect Nonlinear (APN) function $F : \mathbb{F}_2^n \to \mathbb{F}_2^n$ provides optimal protection against differential attacks, meaning that the equation $F(x+a)=F(x)+b$ has at most 2 solutions~$x$ when $a \neq 0$. Setting aside some sporadic examples, such functions are hard to find in practice, and whether there exists APN bijections of $ \mathbb{F}_2^n$ when $n > 6$ is even (the Big APN Problem) is still unknown. In this paper, we provide the tools needed to explore the complete set of known APN functions. Indeed, for a given APN function $F$, we in fact know many: all functions CCZ-equivalent to $F$ are also APN, and so are its switching neighbours. These notions have been in the literature for many years, but several unknowns remain that complicate the exploration of the corresponding functions in practice: a given function has too many switching neighbours, and the algorithms that are known to iterate through a CCZ-equivalence class return multiple representatives per extended-affine (EA) equivalence class. We solve both problems. First, we show how to partition precisely the CCZ-equivalence class of a quadratic APN function in practice, and thus obtain exactly one representative per EA-equivalence class. To achieve this, we carefully investigate the set of the automorphisms of the graph of a quadratic APN function, and show how to generate them very efficiently using the ortho-derivative. Second, we provide the first detailed investigation of the set of the switching neighbours of a function, show in particular how an overwhelming majority of them are trivial, and explain how to get rid of those. Incidentally, we build a new extended-affine equivalence class invariant using the resulting set of non-trivial switching neighbours. For both theoretical contributions, we pushed highly-efficient and easy to re-use implementations of the corresponding algorithms to the sboxU library. It allowed us to generate databases containing all known APN functions for $n=6$ and $n=7$. For $n=8$, our algorithms are efficient-enough that we can investigate the properties of the millions of quadratic APN function recently exhibited. In the process, we generate a few thousands of new CCZ-equivalence classes. In the light of our work, the successes of the exploration strategies for $n=6$ (i.e. finding an APN function inequivalent to any monomial and quadratic mapping, and finding an APN bijection in even dimension) seems to be an artifact due to the small dimension that we show not to work for dimension 8 and which we do not expect to work either when the dimension is greater.

More Salt, Please: A Simple Compiler for Post-Quantum Strong aPAKE

Cryptographic protocols

Show abstract

Cryptographic protocols

Resistance to precomputation attacks is a central security goal in password-based cryptography, as it drastically increases the runtime of brute-force attacks on breached password hashes. Strong asymmetric password-authenticated key exchange (saPAKE), which enforces such precomputation resistance, is standardized by the IRTF and deployed today at large scale. Unfortunately, no practical and easy-to-deploy saPAKE exists yet that withstands quantum attackers. Current constructions use rate-limiting tools such as oblivious pseudo-random functions (OPRFs), of which post-quantum versions are significantly more costly and complex than their discrete-log based counterparts. In this paper, we take a new approach to precomputation resistance. Starting from the compilers from PAKE to aPAKE by Gentry-MacKenzie-Ramzan (Crypto 2006) and Liu-Lyu-Han (Asiacrypt 2024), we propose a password file ratchet that adds precomputation resistance to these compilers through continuously updating the password file. The update is a simple salted hash. With a variety of practical post-quantum PAKEs at hand, this yields a ready-to-deploy post-quantum saPAKE at the trade-off of a changing server state.

The Maximum Possible Nonlinearity for a Balanced Boolean Function in 10 Variables is 492

Foundations

Show abstract

Foundations

Determining the maximum nonlinearity of 10-variable balanced Boolean functions has been a long-standing open problem. In this paper, we resolve it by proving that the maximum nonlinearity is exactly 492, thereby confirming Dobbertin’s conjecture in dimension 10. To exclude nonlinearity 494, we derive a quadratic residue for the Walsh spectrum and refine a local energy table from four-block concatenation by retaining the signs of the Walsh coefficients. The resulting bounds exclude all but the largest polar rank; a product inequality and a parity argument eliminate the remaining case.

Applying Combinatorial Techniques To Find Minimal Non-Complete Set Coverings

Foundations

Show abstract

Foundations

One of the most prominent hardware countermeasures against side-channel attacks are threshold implementations (TIs). The technique uses masking to split the operations in a cryptographic algorithm into several ones operating on shares. The coverage and non-completeness requirements of TIs are mathematically described by the notion of non-complete set coverings (NCSCs). Importantly, the number of members inside an NCSC determines the number of output shares and therefore directly impacts the complexity of the resulting TI. In this work, we derive new lower bounds on the minimal number of members of NCSCs and obtain new upper bounds by explicit constructions. We present a group-theoretic construction of balanced NCSCs, in which the numbers of input and output shares coincide, together with a search algorithm based on intersections of group translates. Our methods determine the smallest balanced coverings in two previously unresolved cases and yield exact minima and classifications of optimal coverings for an infinite family of parameters. These results resolve all four explicit open problems posed by Farr\`as, Fidalgo and Lara-Nino.

Exploiting Matrix-Vector Multiplication in AIMer: Single-Trace Attacks on Key Generation and Signing

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

This paper presents two side-channel attacks against AIMer v3.0, one of the two signature schemes selected in the Korean Post-Quantum Cryptography (KpqC) competition. Both are single-trace attacks that recover the full secret key without a profiling phase, one against key generation and one against signing. Both target the same routine: the matrix-vector multiplication invoked by either phase expands each bit of its secret operand into an all-zero or an all-one mask, which then gates the accumulation of the corresponding public matrix row. A single execution therefore leaks one distinguishable segment per secret bit. What makes the attacks non-profiled is that each attacked trace carries its own labelled training set. During key generation, creating the dense invertible public matrices invokes the matrix-vector multiplication routine hundreds of times, on operands that are public. In signing the same derivation takes place, and in addition the signature itself opens all but one of the $N$ parties of every repetition, so the bits of nearly every multiplication in the trace are public. In both attacks we use a supervised classifier to recover the unknown value. In key generation that value is the private key itself, whereas in signing there are three distinct routes to it: the key itself, a party's share of the key, and a party's share of an S-box output. Recovering any one of them is enough to recover the private key. We validate both attacks on an ARM Cortex-M4: one trace recovers the exact secret key from every capture we took, $100$ key generations for each of AES-128, AES-192 and AES-256, and $100$ signatures for each of AES-128f, AES-192f and AES-256f. We also discuss possible countermeasures.

BeaverDam: A Post-Quantum Threshold Key Recovery Protocol from a One-Time Threshold Oblivious Random Function

Cryptographic protocols

Show abstract

Cryptographic protocols

Secure backups are a practical necessity of E2EE messaging apps, typically relying on password-protected key-recovery (PPKR) protocols. These allow users to turn a human-memorable password into a cryptographic key with the help of a server. Recently, Signal and Juicebox proposed threshold PPKR (tPPKR) protocols, removing the trust on a centralized server. Unfortunately, known solutions are only classically secure, lagging behind the shift toward post-quantum (PQ), or to be more precise, hybrid secure E2EE. We present BeaverDam, a novel tPPKR protocol that is PQ secure with efficiency close to existing classical protocols. It also easily extends to hybrid security, standing as the first concretely efficient hybrid-secure tPPKR protocol. BeaverDam relies on a new primitive we introduce --- one-time threshold oblivious random functions (tORF). Unlike full-fledged OPRFs, which are notoriously difficult to construct in a PQ-secure manner, one-time tORF offers weaker but sufficient security guarantees tailored to the tPPKR setting. We then construct an efficient one-time tORF called Beaver, inspired by multi-party computation (MPC) techniques. Owing to the one-time feature, we only need to securely compute a 2-wise independent hash function, making our protocol very efficient. We conclude by presenting a practical instantiation of BeaverDam and comparing its performance to state-of-the-art classical tPPKR protocols, namely Signal's SVR3 and Juicebox.

Weights Come Almost for Free in Ramp Threshold Cryptography

Foundations

Show abstract

Foundations

A weighted threshold access structure assigns a weight to each party and authorizes a subset of parties whenever their total weight exceeds a prescribed threshold. Most existing approaches to designing multiparty cryptographic protocols in the weighted threshold setting, however, either incur complexity that grows with the total weight assigned to the parties or remain far from concretely efficient. Toward \emph{concretely efficient} weighted threshold primitives, we take a different route and relax to the \emph{ramp} setting, in which two thresholds are prescribed: a subset whose total weight falls below an $\alpha$ fraction of the total is unauthorized, while a subset whose total weight exceeds a $\beta$ fraction is authorized. Exploiting the gap between these two thresholds, we obtain the following results. 1. Given any weighted ramp threshold access structure with privacy threshold $\alpha$ and reconstruction threshold $\beta$, where $0\!<\!\alpha\!<\!\beta\!<\!1$, we present a weight compression technique that reduces the total weight to $\approx n/(2(\beta-\alpha))$ while preserving the authorized and unauthorized sets. Combined with the standard player-virtualization paradigm, this yields concretely efficient weighted threshold cryptographic protocols with only a multiplicative overhead of $\approx 1/(2(\beta-\alpha))$ over their unweighted counterparts. Previously, the best known compression technique in this setting, due to Benhamouda et al.~[ITC'23], achieved total weight $\approx 5n/(\beta-\alpha)$. 2. Player virtualization has an inherent drawback: a party's share size and workload grow in proportion to its (compressed) weight, so the parties in which the most trust is placed also bear the largest computational and communication costs. Thus, although the \emph{overall} overhead is $O(1)$, the cost borne by a single party can still be $O(n)$ times that in the unweighted setting. Our second result removes this imbalance. Building on our compression technique, we construct a linear secret-sharing scheme in which every party receives a share of size $\widetilde{O}(1)$, independent of its weight, for a total share size of $\widetilde{O}(n)$, nearly matching the $O(n)$ complexity of standard unweighted threshold secret sharing.

Independent Leakage Does Not Save Evasive LWE: Refuting Folklore Fixes in the Private-Coin Setting

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

The evasive learning with errors (evasive LWE) assumption has enabled a wide range of advanced cryptographic constructions from lattices in the past few years. The simple intuition that LWE remains secure even when additional ``non-zeroizing'' short preimages are given has proved highly versatile in applications. Unfortunately, recent counterexamples have refuted its general private-coin formulations, showing that having the short preimages along with arbitrary auxiliary leakage about the secret and target matrices can invalidate this intuition. To preserve important applications, particularly witness encryption, the community has sought to repair the assumption by restricting the allowed leakage. One folklore proposal requires the secret and target matrices, together with their respective leakage, to be generated independently. This restriction appears to preserve the application to witness encryption while ruling out all previously known counterexamples. In this work, we refute this proposal. Assuming LWE and indistinguishability obfuscation, we show that both the binding and hiding variants of private-coin evasive LWE are false even with the independent sampler restriction. Our counterexamples exploit only auxiliary leakage about the target matrix. We sample the secret honestly from a standard uniform or Gaussian distribution, independently of the target and its leakage, and we use no auxiliary information about the secret.

New Results in Adaptively-Secure Broadcast Encryption and Succinct Computational Secret Sharing from Standard Lattices

Public-key cryptography

Show abstract

Public-key cryptography

Projective pseudorandom generators (PPRGs), introduced by [Applebaum et al.; STOC'23], expand a short seed into a long pseudorandom string, with a special feature that one can generate a short $\textit{projected}$ key, for any set $S$, such that it reveals the output bits in $S$ while preserving pseudorandomness of the remaining bits. They demonstrated that PPRGs can bypass the 'representation size barrier' in computational secret sharing schemes, and designed PPRGs assuming hardness of a variety of standard cryptographic assumptions. Later, [Hsieh, Waters, and Wu; EUROCRYPT'25] showed that PPRGs can also be used to design adaptively-secure broadcast encryption in the standard model, without relying on unprovable heuristics. In this work, we design succinct computational secret sharing schemes for graph access structures and adaptively-secure flexible broadcast encryption in the standard model, both with optimal parameters. The main driver for both our results is a new construction of a compact programmable pseudorandom set sampler (PPS), introduced by [Goyal and Yadugiri; CRYPTO'26], from standard Learning with Errors (LWE) assumption [Regev; STOC'05]. We show that PPS generically imply PPRGs with many useful properties and, moreover, by replacing PPRGs with PPS we can achieve full succinctness in the underlying applications to secret sharing and adaptive security compilers for broadcast encryption. This yields the $\textit{first}$ flexible broadcast encryption scheme in the standard model from $\textit{any}$ falsifiable assumption with fully compact ciphertext size, and a succinct computational secret sharing for evolving graph access structures with optimal share size from standard LWE.

Vector Commit-and-Reduce Schemes

Cryptographic protocols

Show abstract

Cryptographic protocols

Hash-based argument systems are seeing increasing adoption in practice, owing to their ease of deployment, fast provers, and plausible post-quantum security. However, they still lag behind elliptic-curve counterparts due to their large proof sizes and (comparatively more) expensive verifiers. Attempts to optimize these metrics have focused on one of the two ingredients underlying these arguments, namely Interactive Oracle Reductions, leaving the other ingredient, Vector Commitments (VC) schemes largely ignored. This is in part because Merkle trees are the best known hash-based VC scheme to date. To make progress on this front, we introduce Vector Commit-and-Reduce (VCR) schemes. These generalize VC schemes by allowing both the commitment and opening algorithms to be interactive protocols, and moreover by allowing the opening algorithm to be a reduction instead of an argument. By requiring VCR schemes to satisfy strong round-by-round knowledge soundness notions, we show how they can be used to construct hash-based reductions from IORs. Our transformation extends prior work which used (non-interactive) VC schemes. We also provide a construction of a VCR scheme, Canopy, that greatly reduces proof size and verifier time by reducing the vector opening claims to proximity claims about certain (committed) codewords. This latter feature enables us to use a wide variety of techniques for proving, batching, and accumulating these claims, and indeed we use these to obtain both concrete and asymptotic improvements for hash-based arguments and reductions. For SNARKs based on the Bolt code [CRYPTO 2026], we reduce proof sizes by 50\% and verifier hashes by $3\times$ with only a 5-15$\%$ prover overhead. For SNARKs based on the Reed-Solomon code, we reduce proof sizes by 20$\%$, and verifier hashes by $1.5\times$ with only a 20$\%$ prover overhead. We also construct hash-based Proof-Carrying Data where the recursion overhead is $O(\lambda \sqrt{\log N})$ hashes; in comparison, the state-of-the-art requires $\Omega(\lambda {\log N})$ hashes.

SETH: Subcode Equivalence in the Head

Cryptographic protocols

Show abstract

Cryptographic protocols

The Multi-Party Computation in the Head (MPCitH) paradigm has proven to be a versatile tool to design post-quantum digital signature schemes. Recently, MPCitH was improved with Threshold Computation in the Head (TCitH) and Vector Oblivious Linear Evaluation in the Head (VOLEitH). In this paper, we propose two polynomial models for the Subcode Equivalence Problem (SEP) and derive TCitH and VOLEitH signatures from them. The resulting scheme has better performance when compared to other SEP-based signature schemes and also features shorter signatures when compared to other schemes based on similar assumptions.

Differentially Private Distance-Sensitive Representations for General Metrics

Foundations

Show abstract

Foundations

A distance-sensitive set representation stores a set $S$ from a metric space $(U,d)$ and answers queries of the form "is some element of $S$ within distance $r$ of $q$?''. Existing differentially private constructions are confined to Hamming space, because they route the query through a signature map built for that metric. We give a framework that removes this restriction. The released object records only the occupancy of a fixed public partition of $U$, so privacy transfers unchanged from an off-the-shelf private membership structure, and the entire metric dependence collapses into one packing quantity, the straddle number $\kappa$: the largest number of cells a ball of radius $r$ can meet. Any metric admitting a partition of width at most $(c-1)r$ and straddlenumber $\kappa$ then has an $\varepsilon$-differentially private $(c,r)$-representation with $\varepsilon =\ln(2\kappa/\alpha)$ in $O(k\log(\kappa/\alpha))$ bits. Instantiating $\kappa$ gives matching upper and lower bounds in $\ell_\infty$ for partition-based constructions ($\varepsilon=O(\log d)$ at $c=\Theta(d)$, against $\varepsilon=\Omega(d)$ at constant $c$), and a randomized, dimension-free construction for every $\ell_p$ (one probe and $\varepsilon=\ln(2/\alpha)$ regardless of $d$) at the cost of a weaker, non-oblivious guarantee whose price is exactly this $\log d$ gap. For metrics available only through a distance oracle, we build the partition from a public net and a public navigable graph, and show that greedy search on that graph both locates and enumerates the cells a query must probe; on a $\lambda$-doubling metric this gives $\varepsilon\le 5\ln\lambda+\ln(2/\alpha)$. We further show that the per-query form of the guarantee is forced rather than chosen: any representation correct on all queries simultaneously requires $\varepsilon\ge\ln M+\ln(1/\alpha)-O(1)$ for $M$ the packing number of the whole space, and on doubling metrics this is achievable up to an additive $O(dim_D\log\frac{c}{c-1})$. Finally, the space bound is optimal in $k$ and $\alpha$.

Symbolic forward secrecy analysis of ML-KEM

Cryptographic protocols

Show abstract

Cryptographic protocols

Post-quantum Key Encapsulation Mechanisms (KEMs) rely on generic transformations to achieve active security. Specifically, ML-KEM (FIPS 203) applies the Fujisaki--Okamoto (FO) transform to a lattice-based public-key encryption scheme, Kyber.CPAPKE, to construct an IND-CCA2 secure key exchange protocol, ML-KEM. While NIST standards and associated special publications discuss guidelines for establishing larger shared keying material using ML-KEM, formal symbolic proofs to evaluate these operational setups remain sparse. This work addresses this gap by conducting a formal symbolic analysis of ML-KEM using \textsf{ProVerif}. First, we verify the core primitive, establishing symbolic proofs for session key confidentiality, key agreement soundness, and Fujisaki--Okamoto implicit rejection fallback secrecy. Second, we examine the temporal security guarantees of ML-KEM under long-term static key leakage. Using \textsf{ProVerif}'s global phase constructs, we demonstrate that standalone static ML-KEM does not preserve Perfect Forward Secrecy (PFS), rendering repeated static encapsulation for additional key share establishment vulnerable to retroactive decapsulation. Lastly, we formally model and verify that deploying ML-KEM with ephemeral key rotation or ratcheting mechanisms mitigates this vulnerability, providing robust forward secrecy and complete session domain separation.

Quantum Key Exchange from Public Quantum Money

Foundations

Show abstract

Foundations

Two-message quantum key exchange (2QKE) cannot be realized in a statistically secure way, and therefore some computational assumptions are required [Malavolta and Walter 2024]. So far, the known weakest assumption for 2QKE is the existence of one-way functions (OWFs): Malavolta and Walter constructed (even everlasting-secure) 2QKE from OWFs [Malavolta and Walter 2024], and Kitagawa, Morimae, Nishimaki, and Yamakawa constructed quantum public-key encryption (QPKE) with quantum public keys, which implies 2QKE, from OWFs [Kitagawa, Morimae, Nishimaki and Yamakawa 2024]. Can we construct 2QKE from a weaker assumption than OWFs? In this paper, we give the first complete characterization of 2QKE. We show that the following four primitives are (existentially) equivalent: everlasting-secure 2QKE, standard 2QKE, efficiently-verifiable state puzzles (EV-StatePuzzs), and one-time secure digital signatures with quantum signatures and signing keys. Because EV-StatePuzzs are potentially weaker than OWFs [Kretschmer, Qian and Tal 2025], the equivalence implies that 2QKE are potentially weaker than OWFs. Moreover, our result shows the equivalence between standard 2QKE and everlasting-secure 2QKE, which means that everlasting security comes for free. Finally, one-shot signatures, quantum lightning, and public-key quantum money mini-schemes imply EV-StatePuzzs, and therefore, our result also gives a new lowerbound, namely everlasting-secure 2QKE, of these public-key unclonable primitives. We also show that one-shot signatures imply QPKE with quantum public keys [Kitagawa, Morimae, Nishimaki and Yamakawa, 2024] constructed QPKE with quantum public keys from OWFs, and it was open whether QPKE with quantum public keys can be constructed from an assumption weaker than or incomparable to OWFs. Our result gives a potential answer to this question since one-shot signatures seem to be incomparable with OWFs. Moreover, QPKE constructed from one-shot signatures has an additional functionality, which we call certified freeze, that allows the receiver to publish a publicly verifiable classical certificate that computationally binds the receiver to an upper bound on the total number of distinct valid ciphertexts under its verification key.

Optimal Early-Stopping Broadcast via Exponential Information Gathering

Foundations

Show abstract

Foundations

Early-stopping broadcast protocols guarantee termination based on the actual number of malicious parties, $f \leq t$, encountered during execution, rather than the worst-case scenario of $t < n$ corruptions. The seminal work of Dolev, Reischuk, and Strong~[JACM'90] established that $\min\{f+2,\, t+1\}$ rounds are necessary. The influential works of Berman, Garay, and Perry~[WDAG'92] and Abraham and Dolev~[STOC'15] introduced the first protocols achieving this optimal bound in the $t < n/3$ (unconditional, no setup) regime, while Perry and Toueg~[Tech.\ Report'84] gave the first protocol for the $t < n/2$ setting (with plain PKI), achieving $2 \cdot \min\{f+2,\, t+1\}$ rounds. Despite this early progress, closing the gap to the optimal bound in the computational setting has remained a longstanding open problem, and only recently has progress been made. The best known result in the $t < n/2$ regime is due to Elsheimy, Loss, and Papamanthou~[Eprint'25], achieving $f + O(\sqrt{f})$ rounds. In the dishonest-majority regime, the best known result is due to Deligios, Klasovita, and Liu-Zhang~[Eurocrypt'25], who obtain the first asymptotically optimal protocol, with $O(f)$ round complexity, for $t = (1-\epsilon)n$, where $\epsilon > 0$ is a constant. In this work, we advance the state of the art in two directions. First, in the $t < n/2$ setting with plain PKI, we present a broadcast protocol in which all parties output within optimal $\min\{f+2,\, t+1\}$ rounds. Second, we complete the picture by introducing the first protocol that is optimally resilient ($t < n$) and asymptotically matches the lower bound for any number of corruptions $t < n$. By leveraging exponential information gathering (EIG) graphs, our constructions establish that these round bounds are achievable, providing the first feasibility result for optimal-round protocols, albeit at the cost of exponential communication complexity.

Privacy-Preserving Multi-Institutional Clinical Prediction via Multiparty Encrypted Newton-CG Logistic Regression

Applications

Show abstract

Applications

Multi-institutional clinical prediction can benefit from larger and more diverse patient populations, but privacy and data-governance constraints often prevent pooling patient-level records. This study aims to enable collaborative logistic-regression training while keeping such records local. We developed a framework combining multiparty Cheon–Kim–Kim–Song (CKKS) homomorphic encryption with Newton–conjugate gradient optimization. Each institution computes local gradient and damped Hessian contributions, while only encrypted fixed-dimensional statistics are aggregated. The global Newton system is solved by encrypted preconditioned conjugate gradient with diagonal preconditioning and delayed division, making the dominant homomorphic cost depend mainly on model dimension. We evaluated the framework on nine clinical-prediction tasks from NHANES 2017–2018 and on the PIMA Diabetes and Breast Cancer Wisconsin datasets. Across the nine NHANES tasks, mean absolute deviations from pooled-data plaintext Newton training were below 0.002 for area under the receiver operating characteristic curve, area under the precision–recall curve, and average precision. Five-fold cross-validation accuracy was (77.21 ± 1.28)% on PIMA Diabetes and (96.42 ± 1.44)% on Breast Cancer Wisconsin. Under a common 20-iteration budget, the proposed method achieved approximately 3.85× faster training and nearly 90% lower peak memory use than a reproduced multiparty encrypted first-order baseline, while attaining a lower final relative gradient and closer agreement with plaintext Newton. These results show that exploiting locally computed Newton statistics can preserve predictive utility while substantially reducing encrypted training cost, supporting privacy-preserving multi-institutional clinical prediction without pooling patient-level data.

Bridging Correlation Measures and Unpredictability: Sharp Bounds and Insights for TRNG Validation

Foundations

Show abstract

Foundations

Do small correlations certify high unpredictability? We answer this for the high-order correlation measures (Mauduit and Sárközy) and finite-memory sources. We develop minimax sharp bounds on next-bit prediction from high-order correlations and show that the min-entropy-rate deficit is linear in the largest correlation, with optimal first-order constants. We also bridge population and sample correlations through ergodic limits and finite-sample guarantees. As an application, we show that the validation method for true random number generators recently proposed at WAIFI 2026 over-rejects: shrinking (sub-constant) thresholds strongly reject sources of nearly full entropy.

Memory-Efficient HQC Implementations on Cortex-M3 and Cortex-M7

Implementation

Show abstract

Implementation

In the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism (KEM), eliminating the polynomial product buffer still leaves serialized inputs, operands, and candidate ciphertexts that may coexist during decapsulation. We organize storage around the last use of each value. Comparing each candidate component before producing the next allows both to share one workspace, while deterministic regeneration shortens the lifetimes of ephemeral supports. Our lifetime analysis relates the measured footprint to the values that coexist during reencryption in our compact design. We read dense operands directly from serialized inputs and reuse output storage as workspace before final serialization during key generation and encapsulation. These choices reduce overlapping storage across the complete KEM and complement established support-form and Zero-Buffer multiplication. We evaluate this organization for all three HQC parameter sets on ARM Cortex-M3 and Cortex-M7 under the August 2025 specification. In a cumulative Cortex-M3 HQC-256 comparison, combined representation and lifetime changes reduced the stack by 38.9% relative to a Zero-Buffer configuration that already uses component-wise ciphertext comparison. Using a separate configuration, we measured decapsulation footprints of 36,858 bytes on Cortex-M3 and 36,850 bytes on Cortex-M7, including peak operation stack and serialized input/output storage. The common object layout accounts for most of these footprints. In the evaluated configurations, the relative increase in decapsulation cycles from the direct to the compact implementation is larger on Cortex-M7 than on Cortex-M3. Retaining supports reduces cycles when memory permits. The kernels retain support-dependent control flow and memory accesses; we did not establish complete-KEM constant-time execution or physical side-channel resistance.

Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space

Foundations

Show abstract

Foundations

We give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$. For rational inputs of bit length $\ell$ on full-rank lattices $L\subset\mathbb R^N$, the reduction uses $(Cp)^N\poly(p,\ell)$ oracle calls and additional bit operations, where $C$ is an absolute constant. It uses $\poly(p,\ell)$ working space outside the oracle, and all oracle queries have rank $N$ and $\poly(p,\ell)$ bit complexity. For $p=2$, the reduction transfers polynomial-space exact SVP algorithms to exact CVP with $2^{O(N)}\poly(\ell)$ time overhead. Instantiating it with the SVP algorithms of Kannan and of Feng, Gao and Liu yields randomized polynomial-space CVP algorithms running in time $N^{N/(2e)+o(N)}$ and $N^{N/(4e)+o(N)}$, respectively. For every fixed integer $p\ge3$, the same reduction yields exact $\ell_p$-CVP algorithms for arbitrary rational targets either in randomized time and space $2^{O(N)}$, or in randomized time $N^{N/(4e)+o(N)}$ and polynomial space. These algorithmic bounds are up to polynomial factors in $\ell$. The reduction performs local search sequentially over the cosets of \(2L\), where \(L\) is the input lattice, while tracking the excess of the current objective value over the optimum. Within a coset containing a closest vector, midpoint inequalities bound the unknown correction in terms of this excess, which in turn allows us to construct many short corrections that reduce the excess bound by a factor of four. A counting argument shows that these improving corrections form a sufficiently large fraction of the lattice points in a known search region, and a sparsification-based sampler assigns sufficiently large probability to every nonzero vector in that region, using at most one SVP call per sample. Repeating this improvement over polynomially many stages yields exact recovery. For \(p\ge3\), the same framework is extended using a diagonal weighted norm computed from the current point.

Structured Quantum Hardness from Unstructured Assumptions

Foundations

Show abstract

Foundations

Whether useful structured hardness can arise from unstructured assumptions is a fundamental question in complexity and cryptography. The longstanding Bennett–Gill question asks whether $\mathsf{NP}\cap\mathsf{coNP}$ remains hard relative to a random oracle; [GIKKLS, STOC 2023] recently gave a conditional affirmative answer in the classical setting. We establish the quantum analogue: if $\mathsf{UP}\not\subseteq\mathsf{BQP}$, then $\mathsf{NP}^{O}\cap\mathsf{coNP}^{O}\not\subseteq\mathsf{BQP}^{O}$ with probability $1$ over a random oracle $O$. Beyond extending the classical result, this separation has a distinctly quantum significance: Shor’s algorithms defeat canonical number-theoretic hardness candidates, while lattice assumptions and other leading post-quantum cryptographic assumptions do not directly supply hard languages with two-sided classical certification on every input. Our conditional oracle separation provides evidence that such structured quantum hardness can nevertheless arise from unstructured sources. Complementing this result, we rule out fully black-box quantum reductions of worst-case quantum hardness in $\mathsf{NP}\cap\mathsf{coNP}$ to post-quantum injective one-way functions and indistinguishability obfuscation. This barrier excludes a broad class of black-box approaches to deriving structured quantum hardness from generic cryptographic primitives, providing partial evidence that the non-black-box techniques in our first result are essential.

Optimizations and First-Order Masking of AIMer on Cortex-M4

Implementation

Show abstract

Implementation

We optimize AIMer-128f on Cortex-M4 and propose first-order masking of its signing. Since squaring is a Frobenius map about $\times 16$ cheaper than multiplication, we restructure AIM2's inverse-Mersenne S-box into a Frobenius-shifted addition chain, cutting multiplications per S-box from 24/23 to 9/10. Since one multiplication-check operand is constant across $N = 16$ parties, we build the partial-product table once and reuse it. Both are orthogonal to single-multiplication acceleration, and with a Radix-16 multiplier on NUCLEO-L4R5ZI, keygen/sign/verify drop 18.55%/3.94%/7.30%. 1-PINI gadgets on every sensitive operation give first-order probing security. TVLA finds no first-order leakage in 100,000 traces. Masking costs $\times 10.5$, itself improved 5.20%.

Breaking $\mathsf{TraintoDefend}$ via Adaptive Neuron Clustering in Cryptanalytic Model Extraction

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

Cryptanalytic model extraction poses a fundamental threat to deep learning model confidentiality by enabling precise parameter recovery with theoretical guarantees of functional equivalence. To counter this growing threat, $\mathsf{Train to Defend}$ (NeurIPS 2025) was proposed as the first dedicated defense against cryptanalytic extraction and remains the only defense believed to be effective to date. It encourages neurons to learn similar weights so that they switch activation states together, making their individual contributions harder to distinguish. However, we notice that neurons with similar weights need not switch activation states together under small perturbations. Instead, weight similarity can cause the original clustering rule to merge signatures from distinct neurons when only a subset of their normalized weight coordinates agree. Motivated by this observation, we introduce $\mathsf{SimBreak}$, an adaptive clustering rule that breaks the weight-similarity defense of $\mathsf{Train to Defend}$. $\mathsf{SimBreak}$ estimates a relative scale from all jointly observed weight coordinates and uses the same scale to test both weight direction and bias consistency. Across six protected fully connected networks trained on MNIST, $\mathsf{SimBreak}$ raises target layer signature recovery from $0\%$ to $100\%$, with a maximum relative recovery error of $2^{-22.27}$. Our work challenges the use of neuron weight similarity as a sufficient basis for protection and establishes adaptive evaluation as essential to assessing cryptanalytic extraction defenses.

Tamper-Resilient Quantum Key Encapsulation with Coherent Ciphertexts from qOWFs in the QROM

Public-key cryptography

Show abstract

Public-key cryptography

Kitagawa et al. (CRYPTO 2024) constructed the first tamper-resilient, chosen-ciphertext-secure public-key encryption from quantum-secure one-way functions (qOWFs). However, their construction assumes authenticated classical channels and measures intermediate signed-phase states to produce classical ciphertexts. Therefore we ask whether coherent quantum ciphertexts can support active security and certified deletion over unauthenticated classical and quantum channels. We construct the first tamper-resilient quantum key-encapsulation mechanism (QKEM) from qOWFs with coherent quantum ciphertexts and genuine validity-feedback confidentiality in the quantum random-oracle model. Our scheme, designated Signed-Fourier QKEM, retains signed coherence through honest encapsulation to form a state-consuming quantum ciphertext. Aside from an authentic root verification key, all transmitted classical metadata and quantum registers are subject to arbitrary adversarial tampering and entanglement. With one quantum public key per independent signing domain and a challenge serial unused in pre-challenge decapsulation queries, we prove session-key confidentiality under genuine different-header decapsulation, including queries sharing the challenge serial, and genuine same-header validity feedback. We also establish fixed-header key robustness against adaptive decapsulation attacks, bounding wrong-key acceptance by a negligible probability. Furthermore, our scheme provides publicly verifiable computational certified deletion, protecting session-key privacy against subsequent, complete exposure of the receiver's secret state. Finally, composing our QKEM with a classical one-time private data encapsulation mechanism yields header-restricted chosen-ciphertext confidentiality for arbitrary polynomial-length messages.

One-Way Functions and Local Descriptions of Random Data

Foundations

Show abstract

Foundations

Sample compression describes a labeled sample by retained examples and extra information from which a decoder recovers the labels. We show that estimating the length of the shortest such description of random data is hard on average if and only if one-way functions exist. As in Hirahara and Nanashima's (FOCS 2023) consistent pointwise programs, the decoder labels each sample point separately, as a hypothesis does, but in our main result the labels are random rather than given by a concept. To label a point, it sees only that point, the retained examples with one extra bit each, a program, and a public random string revealed before the description is chosen. The length counts the choice of retained examples, their extra bits and the program, not the examples themselves. The task is to output a number between the $1/2$ and $3/4$ quantiles of the shortest length over the public string, up to an additive $a\lceil\log_2m\rceil$ for $m$ points and a fixed integer $a\ge0$. The main result takes polynomially many, at least $8n$, uniform $n$-bit points with independent uniform labels and any large enough polynomial time bound per query. If one-way functions exist, every efficient randomized algorithm fails to output such a number for all large $n$ with probability above an inverse polynomial that is the same for all algorithms and time bounds. Otherwise, for every inverse polynomial, some such algorithm fails with at most that probability for infinitely many $n$. For hardness, labels derived from one-way functions look random yet have short local descriptions, which random labels rarely have. The converse inverts a function that generates descriptions. One-way functions also exist if and only if estimating between the quantiles is hard, at some suitable time bound, for some PAC-style samplable data of the same sizes, labeled by a concept independent of the points.

Quadratic Extractors

Foundations

Show abstract

Foundations

A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.

Separating Pseudorandom Codes from Quantum Random Oracles

Foundations

Show abstract

Foundations

Pseudorandom codes (PRCs) combine two seemingly conflicting goals: robustness to noise and computational indistinguishability from random strings. Recent work has shown that classical symmetric-key PRCs over binary alphabets cannot be constructed from minimal cryptographic assumptions, such as one-way functions, via black-box reductions. In this work, we revisit this question in the presence of quantum computation and quantum information. We first consider pseudorandom codes with classical codewords but quantum algorithms. We prove that symmetric-key pseudorandom codes robust to Bernoulli noise admit no black-box construction from quantum random oracles, and hence from quantum-secure one-way functions. This establishes that the classical black-box barrier for PRCs persists even in the quantum computational setting. Motivated by this separation, we investigate the notion of quantum pseudorandom codes (QPRCs), in which codewords are quantum states and security is defined via computational indistinguishability from Haar-random states. We then present several positive results. Assuming quantum-secure one-way functions, we construct QPRCs that are secure against a single encoding query, allow multiple copies of the challenge state, and tolerate an error rate matching that of any classical uniquely decodable binary error-correcting code against a dephasing or bit-flip channel. We also show that the PRFS with proof of destruction due to Behera et al. (TCC 2023) can be extended to a 0-bit QPRC that is secure against multiple encoding queries and tolerates unbounded phase errors but only a constant number of bit-flip errors. Finally, assuming the existence of quantum-secure single-query pseudorandom states (1PRS), we construct single-query single-copy QPRC that tolerate arbitrary Pauli noise up to the decoding radius of a quantum error-correcting code with unique decoding.

Vectorized (2, 2)-Isogenies in the Theta Model Using AVX-512 and Applications to SQIsign

Implementation

Show abstract

Implementation

Higher-dimensional isogenies have emerged as a powerful building block for isogeny-based cryptography, with recent protocols such as SQIsign relying on the efficient evaluation of $(2^n, 2^n)$-isogenies. Despite their attractive security and compactness properties, these schemes remain computationally expensive and improving their performance is an important step for their real-world use. In this work, we present a high-performance AVX-512 implementation of two-dimensional isogenies that effectively exploits their data-level parallelism. We develop a code generator that produces efficient AVX-512 implementations of arithmetic over $\mathbb{F}_p$ and $\mathbb{F}_{p^2}$ for Montgomery-friendly primes of the form $p=c\cdot 2^e-1$ with $e\approx \log_2(p)$, covering the family of primes used by several protocols based on two-dimensional isogenies, including SQIsign. Building on this arithmetic, we vectorize the $(2^n, 2^n)$-isogeny formulas by Dartois et al. (ASIACRYPT 2024), achieving significant speedups over the corresponding, highly-optimized scalar implementation that uses x86-64 assembly. As an application, we accelerate the Round 2 version of SQIsign verification and obtain speedups of $2.5\times$ at NIST security level I and $3.2\times$ and $3.3\times$ at levels III and V, respectively. Our code generator also readily supports the larger primes of Round 3 SQIsign, for which we obtain verification speedups between $3.1\times$ and $3.4\times$.

STIR/SHAKEN: A Cocktail of Cryptographic Clumsiness

Applications

Show abstract

Applications

Scams and fraudulent robocalls are rampant in the telephone system. Fraudsters often employ call spoofing to impersonate a known caller to the victim, making it difficult to detect and block the fraudster’s calls. In an effort to combat call spoofing, the U.S. government in 2019 mandated the use of a new suite of protocols called STIR/SHAKEN. In STIR/SHAKEN, providers include a cryptographically-signed assertion about the caller’s identity and other metadata in call headers. This serves both to authentically convey this metadata between providers during call routing and to provide reportable, verifiable evidence of bad behavior by providers that originate fraudulent calls. This paper asks whether STIR/SHAKEN achieves its security goals, and at what cost to the telephone system. On security we find serious structural weaknesses: a year of STIR/SHAKEN certificates observed in production call traffic shows a PKI riddled with noncompliance—nearly half of valid certificates violate the specifications—a provider can prevent later verification of a STIR/SHAKEN assertion by taking its certificate offline, and a header-malleability flaw, which we verified in test calls placed with the help of a real telephone provider, causes a spoofed caller ID to be displayed as verified on some phones. The cost, meanwhile, has been steep: STIR/SHAKEN deployment has created systemic new harms to the privacy of all phone users. These new privacy harms take two forms. First, signing call metadata renders it cryptographically non-repudiable: for the first time in the phone system’s 150-year history, there is publicly verifiable proof that a call took place. Second, STIR/SHAKEN’s complexity pushes providers to outsource signing and verification—roughly half of the 29 providers we surveyed do so, most to a handful of dominant vendors—causing widespread new leakage of sensitive call metadata to off-path third parties. (One such off-path third party, Neustar, was acquired in 2021 by TransUnion, one of the three nationwide U.S. credit bureaus. Neustar authenticates over 30 billion calls per month—and TransUnion sells a “Phone Behavior Intelligence” product advertising “insight into billions of call transactions” obtained through its “deep carrier relationships.”) These structural harms sit atop implementation failures: our tests also found implementations that completely break the federally-mandated *67 caller-privacy mechanism. Finally, we propose solutions to the problems we identify. To fix the PKI, STIR/SHAKEN should adopt certificate transparency; a public certificate log also stops providers from taking certificates offline to defeat later verification. Our remaining solutions are cryptographic, and share a prerequisite STIR/SHAKEN cannot currently meet: the origin provider must learn the destination provider’s public key. We thus design a backwards-compatible key discovery mechanism that uses SIP error messages. We then attack the privacy harms directly: replacing STIR/SHAKEN’s signatures with asymmetric message franking (AMF) makes call metadata deniable again, and issuing AMFs blindly keeps it hidden from outsourced signers. We design the first blind signing protocol for the AMF construction of Tyagi et al., along with new security definitions capturing requirements novel to the setting, such as verifier-hiding blindness. To our knowledge, we thereby initiate the formal study of blind signing for designated-verifier signatures; we believe this is of independent interest.

Can Fully Homomorphic Encryption on Public Blockchains Protect Sensitive Medical Consultations? A Security and Privacy Assessment

Secret-key cryptography

Show abstract

Secret-key cryptography

%===================================================================== \begin{abstract} People seeking care for stigmatised conditions often delay treatment because they fear exposure, yet digital health services routinely expose user data and metadata. Fully homomorphic encryption (FHE) now allows smart contracts on public blockchains to hold encrypted data whose decryption is governed by contract rules. This paper assesses whether this approach can protect sensitive medical consultations. We present ConfidentialCare, a prototype built on Zama's fhEVM and the Ethereum Sepolia testnet, in which patients' symptoms are encrypted in the browser and only an authorised doctor may decrypt them. We evaluated three versions of the system through metadata inspection, access-control tests and attack experiments, asking what FHE protects and whether access to patient data can be controlled. Consultation content remained confidential in all tested cases, and the design collects no names, emails or accounts. However, public on-chain metadata revealed which wallet consulted which doctor, the doctor's specialty, when, and the approximate length of each message, and this history would be exposed permanently if the wallet were ever linked to the patient. We also found that a doctor granted access could re-share a patient's encrypted data, both through a confused-deputy flaw in the application contract, which we fixed, and directly through fhEVM's access control list, and that neither withdrawing access nor closing a consultation removed it. A redesign based on time-limited, revocable delegation prevented re-sharing, and Zama's live service enforced its revocation and expiry immediately. On Sepolia, Zama's key-management service refused decryption without a valid delegation, and revocation took effect within the same block in all six trials. We conclude that FHE protects what patients disclose, but not the fact or context of seeking care, and that in fhEVM a permission to decrypt is also a permission to share. \end{abstract}

Sumcheck bit packing

Cryptographic protocols

Show abstract

Cryptographic protocols

Circuit-based zero-knowledge proofs over large fields waste most of a field element when they commit to a single bit. We study the problem of committing to packed witnesses, in which $m$ bits are stored in one element of $GF(2^m)$, while still allowing the proof system to verify linear claims about the individual bits. Prior approaches to this problem either (a) scale to packing only 4 bits[Fs24], (b) require tensor-structured claims and additional sumcheck rounds that incur larger soundness error [DP23,DP25], or (c) rely on Frobenius automorphisms [Koc26]. In contrast, we present a simpler reduction that exploits only the $GF(2)$-linearity of the field trace and achieves soundness error $2^{-m}$ for arbitrary bit-linear claims. We then use a characterization of trace-zero field elements to make the reduction zero-knowledge over any hiding linear commitment scheme: whereas previous constructions verify $O(m^2)$ or $O(m)$quadratic constraints in the commitment scheme, our protocol requires only linear constraints.

Projective Jet Geometry and Hold-Out Rank of Binary Goppa Codes

Foundations

Show abstract

Foundations

We develop a projective-geometric and algebraic framework for the higher-order polynomial relations among the public generator-matrix columns of a binary Goppa code, the relations exploited by the recent structural distinguishers and key-recovery methods for Classic McEliece. The alternant representation realizes the public columns as rational points on a hidden curve parametrized over $\F_{2^m}$; higher-order vanishing conditions become fat-point conditions, pulled back along the hidden parametrization. Our first contribution is an exact characterization of a codimension-$t$ ambient space containing all products of $d$ code polynomials: the products satisfy $(\pi^dh)'\equiv0\pmod{g^2}$ for the support polynomial $\pi$ and the Goppa polynomial $g$, and the space of degree-$\le dD$ polynomials with this property has dimension $dD+1-t$ once $dD\ge2t-1$. Equality with the actual product space is proved in a local regime, verified computationally on every instance tested, and stated as a conjecture. Our second contribution is a Frobenius-descent theorem: a binary form vanishes on the hidden curve if and only if it vanishes on the union of its $m$ Frobenius conjugates, with the $\F_2$-dimension of such forms equal to the $K$-dimension of the ideal of the union; from it we derive Hilbert-function bounds, including a multilinear version attained on all but one of the twenty-seven keys with $t\ge5$ tested (and missed by one on that key), and the local structure of the pulled-back forms at the roots of $g$. We then analyze the universal dependencies among Hasse-jet conditions in the multilinear setting of the attacks: a closed formula for the rank at a single column, and an explicit family of $\binom{k}{2s-d-2}$ relations between the conditions at any two columns. At a held-out column we prove an exact codimension formula for the Goppa subcode generated by the gradients of the vanishing forms. Finally, running our experimental pipeline (the jet system of the attacks, without the key-recovery steps) on six independently generated keys of a Classic-McEliece-shaped code shows that the kernel dimension is comparable to that of a random control, while every kernel form exhibits the predicted hidden-curve vanishing, the gradients span the predicted subcode, and the first-order normal data of the kernel is nearly independent of the key. Together these results explain the main components of the nuisance space of the recent attacks and isolate the conjectures that remain for an exact description of the kernel.

Cryptanalysis of Pairing-Based Additive Masking with Prime-Field Secrets

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

We analyze the public values generated by a pairing-based multi-secret sharing construction in which each secret is added to a power of a common pairing value. The secrets lie in the prime subfield of the extension field containing the public values. We show that the first two public values determine the common mask whenever an explicit nonzero condition holds. We also show that the exceptional case is resolved for the parameter set considered in the numerical example. Consequently, the complete public transcript determines every secret, without requiring a participant share or an initially compromised secret. We further describe two related forms of leakage: recovery of all secrets after disclosure of one suitable secret, and a reduction in the possible values of a secret from a single public value. Our conclusions concern the field-valued, common-base masking construction analyzed here; they do not imply that pairing-based secret sharing in general is insecure.

HqcLethe: Streaming HQC Encapsulation for Tiny Stateless Servers

Cryptographic protocols

Show abstract

Cryptographic protocols

Stateless post-quantum authenticated key exchanges such as post-quantum WireGuard hedge against unexpected cryptanalytic advances by combining a lattice KEM with code-based Classic McEliece. However, recent attacks have led Germany's BSI to advise against McEliece, which leaves these protocols with lattices alone. HQC, the code-based KEM that NIST selected, could restore diversity, but its keys do not fit in a single packet, so a server would have to buffer multi-packet handshakes. This would leave an attack surface for memory exhaustion, which is what WireGuard's stateless handshake was designed to avoid in the first place. McTiny demonstrated that stateless key encapsulation for Classic McEliece is possible by streaming key blocks one-at-a-time. However, HQC's encapsulation does not split as easily into individual packets, as cyclic polynomial multiplication, unlike matrix-vector multiplication, is inherently non-local. We present HqcLethe, a stateless key exchange that streams an HQC encapsulation in packet-sized pieces. It uses the Chinese remainder theorem to split the polynomial multiplication into independent remainders, one per packet, and masks them so that they reveal no more than an ordinary HQC ciphertext, which we prove in Rocq with SSProve; we also verify session secrecy, server authentication and forward secrecy in ProVerif. Client puzzles bound CPU exhaustion, and HqcLethe removes memory exhaustion: on a Raspberry Pi 3B+, each worker runs in a fixed 1.2-1.6 MiB. At category 5 it sends 27x fewer bytes and uses 9.0x less server CPU than McTiny, the earlier stateless code-based design.

Keyber: Recovering the Signal by Amplifying the Noise in ML-KEM

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

ML-KEM (FIPS 203) is now being deployed in real-world applications to provide security against adversaries with quantum computers. Therefore, the resistance of ML-KEM’s implementations to physical attacks requires thorough evaluation. So far, fault attacks on ML-KEM have targeted the decapsulation operation. The key generation operation has received little attention from a fault-attack perspective. In this work, we present Keyber, the first statistical ineffective fault attack (SIFA) on the key generation of ML-KEM. Keyber is a key-recovery attack that needs only a single fault in key generation. The fault adds a known value to the error vector. Thus, the public key becomes faulty, while the seed of the public matrix remains intact. Every subsequent decapsulation, therefore, carries a known induced error. The adversary encapsulates locally and keeps only ciphertexts whose induced error peaks at exactly one coefficient. A decapsulation failure can then be attributed to that coefficient. Each query yields one linear inequality on the secret key, with no further faults. We observe that approximately 0.2-27% of encapsulations are usable for different parameter sets of ML-KEM. The full secret key is recovered using up to 30,000 inequalities across all security levels. We also realise the attack for ML-KEM-512 on an ARM Cortex-M4 device using a single over-clock fault. We then recover the entire secret key end-to-end. A single fault in this one-time operation thus compromises the key for its entire lifetime. Protecting ML-KEM, therefore, demands hardening not only decapsulation, but also key generation.

BASTION: Lock-Step, Staggered and Sequential Share Schedules for a First-Order Masked ML-KEM NTT on FPGA

Implementation

Show abstract

Implementation

The Number Theoretic Transform (NTT) is the arithmetic core of ML-KEM (FIPS 203) and a prominent side-channel target in hardware. Because the transform is linear, first-order arithmetic masking applies share-wise without fresh randomness, which leaves one design decision open: when each share is processed. Published designs process the shares in sequence on one datapath, or on one datapath per share started a configurable delay apart and in random order; running both datapaths in lock-step is the third option. We implement the three schedules on one first-order masked NTT core for ML-KEM on Artix-7 and measure their cost and pre-silicon leakage under one synthesis flow. An iso-architectural unmasked control separates the cost of masking from that of parallelisation: the delivered lock-step core costs 1.56x the LUTs, 2.33x the slices and twice the DSPs of the control at an unchanged cycle count and 196.1 instead of 227.3 MHz, while the sequential core needs 9 LUTs more than the control at twice the cycles. We state when a set of samples combines both shares of a secret, measure the criterion on the RTL and use it as a cycle-accurate oracle. On a whole-design toggle model that sums both share domains, calibrated with injected flaws detected within 750 traces, no schedule leaks at first order in five pairs of runs of 10^5 traces. At second order the schedules form a scale: the lock-step core leaks in single samples, the sequential core only at the pair of samples that its public offset relates, and the staggered core in both ways at every delay we tested short of one transform. Every detected sample lies in the support view of the oracle, which flags up to 80% of the samples of a window for the univariate test, and some lie outside its form view, so lazy reduction matters. A check on the routed netlist finds no cell shared by the domains of the lock-step and staggered cores, and finds the cells that synthesis shares once the preservation attributes are removed. Silicon validation is left to future work.

Trapdoors Beyond Inversion: Recoverable Information in Public-Key Cryptography

Foundations

Show abstract

Foundations

Classical trapdoor functions recover complete preimages, whereas public-key decryption needs only designated information about an encryption input. We study this distinction through trapdoor hardcore functions (TDHFs), whose trapdoor recovers a prescribed value $h(x)$ from a public evaluation $f (x)$, while $h(x)$ remains pseudorandom given the public key and evaluation. For perfectly correct primitives, we show that adaptive TDHFs characterize IND-CCA2-secure public-key encryption. The constructive direction requires only a single recoverable bit and allows noninjective public evaluations. Extending the rejection-sampling approach, we show that adaptive pseudorandomness itself controls queries to unselected candidate evaluations, without requiring full inversion. We also prove that lossy TDHFs characterize lossy public-key encryption, identifying statistical hiding of the designated recovered value as the relevant lossiness requirement. Fiber samplability together with fiber hiding yields a parameter-preserving correspondence with lossy encryption and, through the known long-message transformation, almost-always lossy trapdoor functions when the recovered-value length exceeds the fiber-sampling randomness length. Ordinary TDHFs provide the corresponding characterization of IND-CPA encryption. Together, these results make explicit the roles of adaptive recovery, conditional sampling, and randomness costs in transformations between public-key encryption and full-inversion primitives.

On Key Recovery from Exposed Neural XOR Activations in DES and TDES

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

We study the security of natural ReLU realizations of the Data Encryption Standard (DES) and two-key Triple DES (TDES) when an adversary can submit non-binary inputs and observe selected intermediate neural values. The attack exploits the piecewise-linear extension of XOR: paired inputs that differ in one expanded right-half bit reveal the corresponding round-key bit from the change in a natural XOR node. For DES, the resulting 48-bit first-round subkey leaves only the eight key-schedule bits omitted by PC-2; enumerating these bits and checking an intermediate value recovers the 56-bit effective master key. For two-key EDE TDES, the same technique recovers the first encryption subkey of K_1 and the last DES subkey used by the middle decryption under K_2; two independent 2^8 completions then recover the full 112-bit key pair. The exposed round subkey is recovered with a constant number of leakage observations per bit, giving query complexity linear in the targeted subkey length; the remaining searches are fixed-size for DES. Python experiments report exact recovery for 1,000 random DES keys and 1,000 random two-key TDES key pairs. These results concern a synthetic intermediate-oracle model for natural neural implementations and do not claim a physical attack on conventional DES/TDES hardware or software.

AirBB: Lightweight Threshold Anonymous Credentials without Random Oracles from BB Signatures

Cryptographic protocols

Show abstract

Cryptographic protocols

Anonymous credentials are a well-studied cryptographic primitive enabling users to prove statements about their identity and selectively present personal information in an unlinkable manner. The issuer, however, is often a single point of failure. Threshold issuance addresses this by distributing the issuer across several parties such that a quorum of them must cooperate to issue credentials. Numerous constructions of single-issuer and threshold issuance anonymous credentials have been proposed. However, existing schemes each have at least one of the following weaknesses: (1) their presentations depend on the number of attributes, (2) they are not concretely efficient, or (3) they rely on the random oracle model (ROM) for non-interactive presentations. In this work, we present a new construction of threshold anonymous credentials that has a constant presentation size of 240 bytes, rivals the efficiency of BBS, and does not rely on the random oracle model. We achieve this by combining techniques from set commitments with Boneh-Boyen (BB) signatures (Eurocrypt'04) and prove our scheme's security in the algebraic group model. This is on par with the tight security proofs of existing schemes, which typically rely on the AGM or GGM, or on assumptions justified in those models. Since signing uses linear operations, the scheme is easily thresholdizable, without requiring interaction between the issuers or preprocessing.

Superlattice methods for the shortest vector problem and discrete Gaussian sampling

Foundations

Show abstract

Foundations

We give worst-case algorithms for the shortest vector problem (SVP) and discrete Gaussian sampling (DGS) at arbitrary widths. Both algorithms generate lists on a dense superlattice and combine vectors along a chain down to the input lattice. Random shifts let us control the expected number of representations of a vector regardless of the lattice. For SVP we balance these counts with a novel midpoint-shell test to ensure output distributions are sufficiently uniform. For DGS we use Gaussian weights and correct the probabilities of selecting entries from the final list. For SVP, our optimized algorithm runs in time $2^{0.409 n+o(n)}$ and space $2^{0.259 n+o(n)}$, improving the best $2^{n/2 + o(n)}$ worst-case SVP complexities of Hhan [ePrint, 2026]. For Haar-random lattices, or assuming a natural upper bound on the kissing constant, the costs of the algorithm match the $2^{0.292 n+o(n)}$ time and $2^{0.208 n+o(n)}$ space of Becker-Ducas-Gama-Laarhoven [SODA 2016]. For quantum SVP, through a series of refinements and generalizations we obtain worst-case time and space $2^{0.247n+o(n)}$. This improves the best known heuristic quantum SVP time complexity of $2^{0.256n+o(n)}$ due to Bonnetain-Chailloux-Schrottenloher-Shen [Eurocrypt 2023], without requiring any heuristic assumptions. For discrete Gaussian sampling, we provide a sampling algorithm at any width with distribution error $2^{-\kappa}$, running in worst-case time $2^{0.292 n+o(n)} \operatorname{poly}(\kappa)$ and space $2^{0.208 n+o(n)} \operatorname{poly}(\kappa)$, improving upon the previous best $2^{n + o(n)}$ cost for sampling at arbitrary widths of Aggarwal-Dadush-Regev-Stephens-Davidowitz [STOC 2015]. As further applications, we obtain fast algorithms for approximate-SVP/CVP, bounded distance decoding, and estimating the Gaussian mass and smoothing parameter of any lattice.

Syndrome Decoding out of the Head: Structure-Aided Side-Channel Witness Recovery on SDitH

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

Regular syndrome decoding (RSD) underlies several code-based signature schemes, including SD-in-the-Head (SDitH). Its secret witness has exactly one nonzero coordinate per block, and the selected positions must satisfy a public syndrome equation. In this work, we show how these structural constraints can be exploited to recover the complete witness from imperfect side-channel information. We present a profiled power analysis of the witness-embedding operation in the SDitH Round-3 reference implementation. We train convolutional neural networks (CNNs) to classify the mux digits encoding each regular block and use their outputs to rank candidate positions. To correct errors in these predictions, we combine the resulting rankings with the public syndrome and the regularity constraints. We formulate this recovery problem as an affine correction system with block-validity constraints and analyze its rank, consistency, and uniqueness for the systematic parity-check matrix used in SDitH. Based on this analysis, we develop a quotient-syndrome decoder that identifies blocks whose true positions fall outside the initial candidate lists, avoiding exhaustive enumeration of block subsets. We evaluate our attack on an ARM Cortex-M4 using measured power traces. With a single target trace per key, our approach recovers all 100 test witnesses under -Os using 4,000 profiling traces, and 91 out of 100 under -O3 using 16,000 profiling traces. Each successful recovery matches all 616 serialized witness bits. These results demonstrate how the regular structure of RSD and the public syndrome can compensate for imperfect side-channel predictions, thereby enabling full-witness recovery.

Differentially Oblivious Graph Ball Queries

Foundations

Show abstract

Foundations

A graph ball query returns all vertices within distance $r$ of a source vertex. On $N$-vertex graphs with maximum degree at most $\Delta$, ordinary breadth-first search answers such queries with $O_{\Delta,r}(1)$ record accesses. These accesses depend on private edges and can reveal graph structure. Full obliviousness hides this dependence, but incurs substantial overhead. Differential obliviousness (DO) [Chan et al., SODA'2019] trades off between privacy and efficiency by relaxing full obliviousness to $(\varepsilon, \delta)$-differential privacy on the access traces of neighboring graphs. We study DO graph ball queries under three widely-adopted edge-level neighboring relations: add/delete, replacement, and $2$-switch. Starting from padded adjacency records, we charge all observable accesses, including preprocessing. For fixed $\Delta,r\ge2$, error probability $0<\beta<1/2$, and $0\le\delta\le(1-2\beta)/2$, we prove an $\Omega_{\Delta,r,\beta}(1+Ne^{-\varepsilon})$ expected lower bound at every sufficiently large connected graph and every public source. For every fixed $r\ge2$, we give $(\varepsilon,0)$-DO sampling algorithms with expected cost $O_{\Delta,r,\beta}(1+Ne^{-\varepsilon/C})$ using constant size of hidden workspace, where $C$ depends only on $\Delta,r$ and the neighboring relation. Especially, for $r=2$, we have $C=1$, which indicates that the algorithm achieves the tight bound under all three relations. Finally, we consider repeated queries on the same graph, where the cost of protected preprocessing can be amortized across queries. For fixed $\Delta,r,\beta$, we construct a linear-size reusable index with $(\varepsilon,0)$-DO preprocessing and constant query cost. The expected preprocessing cost is linear in $N$ when $\varepsilon$ exceeds a sufficiently large constant multiple of $\log N$.

Fine-Grained Proof Complexity for Elementary Arithmetic in Extended Frege

Foundations

Show abstract

Foundations

Proof complexity has historically focused on qualitative results, such as whether natural mathematical statements (e.g. the Pigeonhole Principle) admit polynomial-size proofs in certain proof systems (e.g. Resolution or Frege). In contrast to the rich theory of algorithm design, there is little understanding of how to design quantitatively efficient proofs. We initiate the study of fine-grained propositional proof complexity. Our motivation comes from an emerging line of cryptographic constructions such as the elegant work of Jain and Jin (2022), in which the efficiency of the resulting scheme is governed by the size of the underlying Extended Frege proofs. Our main result is that the basic laws of integer arithmetic —commutativity and associativity of addition and of multiplication, together with distributivity — admit Extended Frege proofs of quasi-linear size, when addition is implemented by the schoolbook algorithm and multiplication by an FFT-based algorithm. This seemingly elementary result turns out to be surprisingly non-trivial: the natural paper-and- pencil arguments for distributivity and for associativity of multiplication translate into Extended Frege proofs of quadratic size. To reach quasi-linear size, we develop a technique we call index generalization, which we believe will find wide application in the design of efficient propositional proofs.

Affine Advantage in Guess-type Attacks on Goldreich’s PRGs: Generalization, Characterization and Countermeasures

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

The recent guess-type attack (Eurocrypt'26) on Goldreich's pseudorandom generators exploits the strong bias toward constants that can arise when some inputs of majority-based predicates are fixed. This attack has demonstrated substantial effectiveness against several concrete parameter instances (Eurocrypt'24\&'25, Asiacrypt'24). In this paper, we generalize this attack paradigm to arbitrary affine approximations, characterize its capabilities, and develop a new predicate as a countermeasure. We introduce a guess-and-affine-approximation (GAA) attack framework that generalizes existing guess-type attacks from constant approximations to arbitrary affine approximations of residual nonlinear predicates. To characterize the capacity of GAA attack, we introduce the bit-fixing affine advantage $\operatorname{adv}_{b'}(M_b)$, defined as the maximum affine advantage of a $b$-ary nonlinear predicate $M_b$ over all residuals with $b'$ unfixed inputs. For polynomial stretch $m=n^s$ and logarithmic nonlinear arity $b=\gamma\log_2 n$, we obtain the optimal attack complexities $C^\star$ linking bit-fixing affine advantages: (1) $C^\star>2^{cn}$ for every $c<2^{-(s-1)/\gamma}$ iff $\operatorname{adv}_{\theta b}(M_b)\to 0$ for every constant $\theta\in(0,1]$; (2) $C^\star=2^{o(n)}$ iff fixing only $o(b)$ predicate inputs can yield a residual with affine advantage $\frac{1}{2}-o(1)$, and the sufficient direction also holds for $b=\Omega(\log n)$. In particular, if $\operatorname{adv}_{b-r}(M_b) =\frac12- O\left(\frac{\log n}{n}\right)$ for $r\le s-1$, then $C^\star$ can further decrease to $n^{O(1)}$. These results complement prior analyses for arities $O(1)$, $\omega(1)\cap O(\log n)$, and $\Omega(n^{1/s})$. Guided by the results above, we introduce the $\XOR_a$--$\MODtwelve_b$ family as a predicate candidate. We prove that every $b'$-input residual of its nonlinear component retains algebraic degree and algebraic immunity $\Theta(b')$, matching the asymptotic orders of $\MAJ$ (STOC'16). Moreover, its bit-fixing affine advantage is at most $2^{-\Omega(b')}$, whereas $\operatorname{adv}_{\theta b}(\MAJ_b)\approx \frac12$ for every fixed $\theta\in(0,1)$. Analysis shows that, for $n=1024$, $m=n^2$, and $b=54$, $\XOR$--$\MODtwelve$ can achieve $\log C^\star \approx 737$, while $\XOR$--$\MAJ$ and $\XOR$--$\MODthree$ have cost exponents of only $182$ and $599$, respectively, under the specified attack. Furthermore, our experiments show that $\MODtwelve$ offers stronger resistance to belief-propagation-based attacks.

Refined Bounds for the Smoothing Parameter of Lattices

Foundations

Show abstract

Foundations

The smoothing parameter $\eta_\varepsilon(\Lambda)$ is a fundamental invariant in lattice-based cryptography. Zheng, Zhao, and Xu (AAECC 2021) proved $\eta_\varepsilon(\mathbb{Z}) \le \sqrt{\ln(\frac{2}{\varepsilon} + \frac{\varepsilon}{44})/\pi}$ and $\eta_\varepsilon(\Lambda) \le \sqrt{\ln(n - 1 + \frac{2n}{\varepsilon})/\pi}\,\mathrm{bl}(\Lambda)$. Guo, Liu, Wang, and Tian (PLOS One 2025) proposed $\eta_\varepsilon(\mathbb{Z}) \le \sqrt{\ln(\frac{2}{\varepsilon} + \frac{\varepsilon}{m})/\pi}$ for $0 < \varepsilon \le \frac{4}{m} - \frac{172}{m^6}$ ($m \ge 3$) and $\eta_\varepsilon(\Lambda) \le \sqrt{\ln((n - 1)(1 + \frac{2}{\varepsilon}))/\pi}\,\mathrm{bl}(\Lambda)$ under $\sqrt{\frac{24n+1}{n^2-1}} \le \varepsilon \le \sqrt{2}-1$. We establish three strictly sharper bounds that uniformly dominate both while removing the artificial lower bound on $\varepsilon$. First, for $0 < \varepsilon \le \rho(\mathbb{Z})-1 \approx 0.086435$, \[ \sqrt{\frac{\ln\!\left(\frac{2}{\varepsilon} + \frac{\varepsilon^2}{4} - \frac{3\varepsilon^5}{32}\right)}{\pi}} < \eta_\varepsilon(\mathbb{Z}) \le \sqrt{\frac{\ln\!\left(\frac{2}{\varepsilon} + \frac{\varepsilon^2}{4}\right)}{\pi}}; \] since Guo et al.'s condition forces $\frac{\varepsilon}{m} > \frac{\varepsilon^2}{4}$, our bound is strictly tighter for all admissible $(\varepsilon, m)$, improving the worst-case gap from $O(\varepsilon^2)$ to $O(\varepsilon^6)$. Second, for all $n \ge 2$ and $0 < \varepsilon < \min\{1, (\rho(\mathbb{Z})-1)n\}$, \[ \eta_\varepsilon(\Lambda) \le \sqrt{\frac{\ln\!\left(\frac{2}{\delta_n} + \frac{\delta_n^2}{4}\right)}{\pi}}\,\mathrm{bl}(\Lambda) < \sqrt{\frac{\ln\!\left(\frac{2n}{\varepsilon} + (n - 1) - \frac{(n^2 - 1)\varepsilon}{6n(1 + \varepsilon)}\right)}{\pi}}\,\mathrm{bl}(\Lambda), \] where $\delta_n = (1+\varepsilon)^{1/n} - 1$; the rational bound is strictly tighter than Guo et al.'s across $100\%$ of their validity window, while remaining valid as $\varepsilon \to 0^+$. Third, for any basis $\mathbf{B}$ with Gram--Schmidt vectors $\mathbf{b}_i^*$ and $M = \max_i \|\mathbf{b}_i^*\|$, define $N_\varepsilon(\mathbf{B}) = \sum_{i=1}^n (\varepsilon/2)^{M^2/\|\mathbf{b}_i^*\|^2 - 1} \in [1, n]$; then \[ \eta_\varepsilon(\Lambda) \le \sqrt{\ln\!\left(\frac{2}{\delta_{\mathrm{eff}}} + \frac{\delta_{\mathrm{eff}}^2}{4}\right)/\pi}\,M, \] where $\delta_{\mathrm{eff}} = \frac{n}{N_\varepsilon(\mathbf{B})}((1+\varepsilon)^{1/n}-1)$. For reduced bases with geometrically decaying Gram--Schmidt lengths, $N_\varepsilon(\mathbf{B}) = O(1)$ is independent of $n$, eliminating the $O(n)$ factor inside the logarithm.

Blockchain-Anchored Proactive Refresh for Dynamic Threshold Services

Cryptographic protocols

Show abstract

Cryptographic protocols

A long-lived threshold service must issue shares to participants that join after deployment, refresh them against a mobile adversary, and allow participants offline during a refresh to recover missed updates. We show that charging exposure solely to committed epochs is fundamentally insufficient: an aborted refresh attempt that publishes candidate update tokens can reveal the secret even if no committed epoch exceeds its corruption budget. To eliminate this exposure leakage, we index security by fine-grained states covering both committed epochs and aborted attempts. Each state's budget bounds all participants whose local material or public update records originate from that state, enforced via an append-only, durable release ledger that is never rolled back upon abort. A fixed dealer committee anchors encrypted update records in blockchain blob storage, enabling non-interactive recovery for offline participants without contacting dealers, while an interactive bisection dispute protocol deterministically attributes faulty records on chain. Our core cryptographic result is an explicit distribution-preserving shift of the actual generation transcript, establishing proactive secrecy and past-share unforgeability after dealer-state disclosure without idealizing the underlying subprotocols. An end-to-end Rust implementation benchmarks complete lifecycles across up to 1,280 participants on an EVM chain, demonstrating sub-second group recovery and practical gas costs.

A note on zero-knowledge ring switching

Cryptographic protocols

Show abstract

Cryptographic protocols

We make the ring-switching technique of Diamond and Posen zero knowledge, resolving a problem left open in the literature. Over $\mathbb{F}_{2^n}$, our technique uses $n-1$ auxiliary masks and $n-1$ quadratic constraints, checked in zero knowledge by the underlying commitment scheme.

Correlation Power Analysis on SHA-2-Based SLH-DSA

Attacks and cryptanalysis

Show abstract

Attacks and cryptanalysis

The stateless hash-based digital signature algorithm (SLH-DSA) repeatedly processes a fixed secret seed with varying public addresses. This paper presents non-profiled correlation power analysis of the address-based pseudorandom function for all six SHA-2 parameter sets, using separate recovery paths through SHA-256 compression rounds and message-schedule expansion. The procedures account for the input layout in which a 22-byte compressed address precedes the secret seed. For the 256-bit sets, a two-stage joint procedure recovers two 16-bit secret portions. We evaluate an STM32F303 ARM Cortex-M4 implementation using 30 secret seeds and 5,000 measured power traces per seed for each evaluated condition. Each recovery stage is evaluated with the required preceding secret values supplied correctly; the reported rates are therefore conditional stage-wise results, not end-to-end seed recovery rates. Compression-round stages achieve 100% success under both forest-of-random-subsets and Winternitz one-time-signature-plus address conditions. Under forest-of-random-subsets addresses, all message-schedule stages achieve 100% success for the 128- and 192-bit sets. For both 256-bit variants, joint recovery achieves 100%, whereas recovery of message word $W_{12}$ achieves 66.7%; recovery of $W_7$ achieves 70.0% and 80.0% for the fast and small variants, respectively. An alternative first stage is also provided for 128-bit Winternitz one-time-signature-plus addresses. These results show that side-channel protection must cover both compression rounds and message-schedule expansion.

Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices

Foundations

Show abstract

Foundations

Pseudorandomness plays a central role in algorithms, complexity theory, and cryptography. We ask whether deterministic information loss alone can yield post-quantum pseudorandomness with $\mathrm{TC}^0$ evaluation. Learning with errors (LWE) hides linear measurements with random noise. Learning with rounding (LWR) replaces noise with deterministic rounding, but a standard polynomial-modulus hardness reduction requires parameters tailored to a predetermined sample bound. Decisional Diffie–Hellman offers a noiseless algebraic route to pseudorandomness, but its standard instantiations are vulnerable to quantum algorithms. We show that deterministic rounding achieves this under quantum worst-case lattice hardness, with fixed polynomial parameters and no predetermined sample bound. We introduce the learning with algebraic rounding (LAR) assumption, which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For one fixed family with polynomially bounded modulus and dimensions, its deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. Our classical reduction from Gaussian LWE, combined with the quantum worst-case reduction to LWE, bases LAR on GapSVP and SIVP over general lattices at approximation factor $\widetilde{O}(q)$, where $q$ is the modulus. To prove this, we develop a source-independent affine transport framework that may be of independent interest. Using public affine maps sampled independently of the hidden errors, it transports the Gaussian error law close to uniform on the rounding map’s zero-label fiber while preserving exactly uniform public matrices. For every fixed inverse-polynomial accuracy, we give a polynomial-time sampler for the same public parameter family. This yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in $\mathrm{TC}^0$, secure against uniform quantum polynomial-time distinguishers given any polynomial number of classical uniform random examples. We also establish the hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners.

An efficient Failure Probability Estimator for LWE-based encryption, and application to IBE

Public-key cryptography

Show abstract

Public-key cryptography

In recent years, lattice-based cryptography has proven to be a source of post-quantum cryptosystems. In particular, the blueprint of Learning With Errors (LWE) encryption enabled the creation of Kyber, chosen by NIST to be standardized as ML-KEM. Because of the structure of LWE encryption, the decryption of a ciphertext can give an incorrect plaintext. This event (a decryption failure) happens randomly with some probability. Since this is a problem for both functionality and security, we must ensure that this failure probability is cryptographically negligible. Usually, this is assessed with theoretical approximations and upper-bounds. The authors of Kyber used a Python program to compute that probability more precisely, enabling to fine-tune the compression of the ciphertext, hence reducing its size. However, because of its performances, this program has been limited to Kyber, and all the other schemes are still studied theoretically. In this paper, we design a more efficient Failure Probability Estimator, that we implement in low-level languages (C and CUDA C++), to reach higher parameters used in real schemes based on structured LWE. We illustrate some benefits of our tool with two Identity-Based Encryption schemes. For the first scheme, our tool allows to reduce the size of the ciphertext by about 20%. For the second one, we reduce the failure probability (thus improving security) without impacting the scheme (key size, ciphertext size, etc.).

Practical Optimal Bucket Sets with Power-of-Two Radices for LFG-Based MSM Algorithms

Applications

Show abstract

Applications

Fixed point multi-scalar multiplication (MSM) is a major computational component of pairing-based SNARK proof generation. The Luo--Fu--Gong (LFG) framework is a variant of Pippenger's bucket method that uses a multiplier set $M$ and precomputed point multiples to reduce the number of buckets and online point additions. For radix $q$ and a positive multiplier set $M$, covering all digit residues requires a bucket set of size at least $q/(2|M|)$. Previous constructions approaching this bound based on primitive roots or power-residue classes impose radix restrictions that exclude $q=2^c$, thereby requiring additional binary-to-radix conversion in software implementations. We present two main bucket set constructions for power-of-two radices $q=2^c$, using the multiplier sets $M=\{1,2,3\}$ and $M=\{1,3\}$, respectively. Their cardinalities are $q/6+O(\log q)$ and $q/4+2$, respectively, so both asymptotically attain the counting bound $q/(2|M|)$ while allowing efficient radix-digit extraction through shifts and masks. We further give two generalizations. Using consecutive powers of $3$ as multipliers yields bucket sets of size $q/(2\ell)+O(\log q)$ for every fixed positive integer $\ell$. For $\ell=2^d$ and $c\ge d+2$, consecutive odd multipliers yield bucket sets of size $q/(2\ell)+d+1$. We also present scalar conversion and two strategies for handling the leading digit, allowing the bucket set constructions to be used within the LFG framework.