Central Bank Digital Currencies (CBDCs) aim to replicate the utility of physical cash in the digital era by balancing privacy with regulatory auditability. Despite recent advancements, existing CBDC schemes suffer from limited concurrency and the lack of offline payment confirmation, forcing users to process concurrent payments one by one and requiring counterparts to remain online. These constraints severely limit CBDC's applicability in high-frequency, real-world payment scenarios. This paper proposes PulpoPay, the first CBDC scheme to provide high concurrency and offline confirmation, while maintaining auditable privacy. To achieve high concurrency and offline confirmation, PulpoPay, at its core, introduces a coin-based payment protocol that facilitates users to concurrently withdraw, transfer, and deposit coins without synchronization or online requirements for counterparts. For auditable privacy, we leverage signatures on randomizable ciphertexts to enable fine-grained auditing without compromising privacy. Furthermore, we design a coin identifier with offline-checkable uniqueness to resist double-spending attacks even in disconnected (offline) environments. We formally prove PulpoPay's security within the Universal Composability (UC) framework. We implement a prototype of PulpoPay. Experimental results demonstrate that (1) a payment with an offline receiver can be finished within 0.3~s using a mobile phone; (2) PulpoPay outperforms the state-of-the-art PEReDi [CCS'22] in the scenarios of concurrent payments. For a typical setting of 200 concurrent payments, PulpoPay reduces processing time by at least 66.89% and communication overhead by at least 76.45%. This advantage becomes even more significant as the number of concurrent payments grows.

The module lattice isomorphism problem (module-LIP), introduced with HAWK, has attracted growing interest. Its most studied case is ${\mathcal O_{\mathbb{L}}}^2$-LIP, underlying HAWK key recovery, where $\mathbb{L}$ is a power-of-two cyclotomic field and ${\mathcal O_{\mathbb{L}}}$ its ring of integers. Three recent independent algorithms reduce this $2n$-dimensional problem to polynomially many exact-SVP calls: the Claude-derived algorithm uses dimensions at most $n/2+1$, and the ChatGPT-derived and Mureau--Pellet-Mary algorithms use $3n/4+1$. These improve Ducas's generic $\mathbb Z$LIP bound $n+1$ (DCC 2024). Although known SVP methods still give exponential running times, the impact on parameter selection led the HAWK team to withdraw the scheme. All three approaches rely substantially on rank-two structure. Higher-rank module-LIP is a possible direction for alternatives, calling for further study of its hardness. We first use the symmetric square to obtain a rank-two reduction, matching the bound $3n/4+1$ above. Its auxiliary objects correspond geometrically and algebraically to those of the ChatGPT-derived algorithm, so this does not constitute a substantively new reduction; the differences lie in the interpretation and post-processing. This viewpoint nevertheless motivates our dimension reduction in rank four. In rank four, the conjugate Hodge star on the exterior square yields a publicly computable fixed lattice isometric to $\mathbb Z^{3n}$, from whose orthonormal basis we reconstruct a module isomorphism. For ${\mathcal O_{\mathbb{L}}}^4$-LIP with the standard free module as reference, we reduce the $4n$-dimensional problem to polynomially many SVP calls in dimensions at most $3n/2+1$, improving the generic bound $2n+1$. All computation outside the oracle runs in deterministic polynomial time.

The complexity of fast correlation attack is fundamentally determined by the correlations of the linear approximations used. Conventional fast correlation attacks either rely on a single dominant linear approximation or use the lower bound to evaluate the resulting correlation of multiple linear approximations, which have the same output mask and distinct input masks. How to exploit multiple linear approximations with distinct output masks remains an open problem. In this paper, we propose a framework of fast correlation attack exploiting multiple linear approximations called \texttt{MultLA} to solve this problem. \texttt{MultLA} utilizes the arithmetic mean of the absolute correlations of linear approximations, rather than the lower bound of that. For SNOW 5G, our attack has time/memory/data complexities of ${{2}^{279.25}}/{{2}^{265.03}}/{{2}^{263.62}}$, which are all better than those of the existing work. When the time and memory complexities are slightly better than those of the existing work, the data complexity is significantly reduced from ${{2}^{265.4}}$ to ${{2}^{261.21}}$. To the best of our knowledge, our attacks achieve the best known cryptanalytic results of SNOW 5G up to now.

Fuzzy Password-Authenticated Key Exchange (fuzzy PAKE) was introduced at Eurocrypt'18, enabling two parties to securely establish a shared cryptographic key using passwords that are close and potentially low-entropy. This is a generalization of standard PAKE and is particularly useful for handling mistyped passwords or inherently “noisy” samples such as biometrics. While this primitive sounds promising, existing definitions and protocols face several challenges: they may suffer from gapped leakage (namely, leakage of a small amount of information from failed authentications), or they may be restricted to Hamming distance. We review the functionality and describe our contributions below: 1. Leakage under Reuse. We show that, when a password may be reused across multiple sessions, any leakage from the functionality has the same eventual compromise consequence under repeated use. Concretely, we construct an efficient ideal-world adversary that recovers an n-character password within O(n) active sessions, assuming it starts from a password not too far from the target. Our attack applies to both Hamming distance and Minkowski (L_p) distance under reasonable parameter choices. This implies that, for common distance metrics in practical settings, several notions of leakage are effectively unified when passwords are reused, thereby resolving an open question from Eurocrypt'18. 2. Supporting L_p Distances. We propose substantially more efficient protocols for generalized Minkowski (L_p) and Hamming distances in the random oracle model. As a key technical step, we show how to achieve malicious security using only a semi-honestly secure oblivious key-value store, while addressing several subtleties in the proof. Concretely, compared with existing approaches for L_2 distance, our protocol reduces runtime by about 86% and bandwidth by about 99%.

Multi-key fully homomorphic encryption (MKFHE) supports homomorphic computation over ciphertexts encrypted under independently generated keys. Known constructions accommodate independent keys by expanding every ciphertext under the concatenation of the participating secret keys, and then evaluating the circuit in that expanded dimension. A concatenated key is $N$ times longer than an individual key, so the ciphertext on each wire and the running time of each gate grow with $N$, the number of users. L\'opez-Alt, Tromer, and Vaikuntanathan, who introduced MKFHE, asked for a scheme in which all algorithms are independent of $N$. More than a decade later, no MKFHE scheme has a homomorphic evaluation whose cost is even sublinear in $N$. We construct the first MKFHE whose homomorphic evaluation asymptotically matches that of single-key FHE, while users still generate their keys and encrypt independently and the participating set is chosen only after encryption. We insert a public, deterministic, and non-interactive preprocessing phase between encryption and evaluation: key aggregation combines the selected public keys, and ciphertext preparation converts each independently encrypted input into a short single-key ciphertext under a \emph{virtual key}, namely the sum of the participating secret keys. Evaluation then runs on ordinary single-key ciphertexts, so every wire ciphertext, every gate, and the decryptable output are independent of $N$. We give two instantiations, a leveled GSW-based scheme over $\mathbb{Z}_q$ from standard LWE and a leveled BFV-based scheme over cyclotomic rings from circular Ring-LWE. Both retain single-round distributed decryption with statistically simulatable partial decryptions, where the published key material grows with $N$. As a proof of concept, we implement our ring-based construction in Go. For 32 users, its multiplication is $275.13\times$ and $45.50\times$ faster than CDKS and KKLSS, and its ciphertexts are $16.5\times$ smaller than both.

Hash-based signature schemes present an appealing proposition: they are broadly regarded as the most conservative in terms of assumptions, and their efficiency profiles suit many applications. However, little is known about their compatibility with threshold signing, which is common practice today in domains like digital asset security. Especially in the context of an impending migration to post-quantum cryptography, this gap in the literature leaves uncertain what hash-based standards would imply for applications that rely on threshold signing. In this work, we develop a new framework by which to analyze such hash-based schemes, and prove inherent barriers to designing an entire class of efficient (fully distributed) threshold signing protocols. Our framework is simple, and yet powerful. Our results encompass standard schemes such as XMSS and SLH-DSA. Our approach is to connect hash-based signatures to the literature on straight-line extraction in the random oracle model. We then apply and build upon techniques from the recent work of Doerner et al. (Crypto '24) to show that threshold signing protocols for hash based schemes must—beyond a certain number of signers—use the circuit representation of the hash function, i.e. it can not use the hash function as a black box. We then give a more fine-grained analysis for the specific case of the Winternitz signature scheme—a building block of both NIST standards—and show that it can not permit even two-party signing with blackbox use of the hash function.

We study the matrix signing problem for positive semidefinite matrices, assigning one sign to each original matrix regardless of its rank. This includes the higher-rank Kadison--Singer partition problem [KS59] when the matrices sum to the identity. For arbitrary positive semidefinite matrices $A_1,\ldots,A_m\in\mathbb C^{n\times n}$, we prove that there are signs $\sigma_i\in\{-1,1\}$ such that $\|\sum_i \sigma_i A_i\|\le 3.34963\|\sum_i \operatorname{tr}[A_i]A_i\|^{1/2}$. We give a deterministic algorithm achieving this bound in $\widetilde O(mn^2+n^{4.75})$ real arithmetic operations. Inspired by the Lee--Sidford barrier, we use a potential function built from Schatten norms to obtain a square-root logarithmic dependence on the rank. Under the additional assumptions $\sum_iA_i=I$, $\|A_i\|\le\alpha$, and $\operatorname{rank}(A_i)\le r$, we obtain a discrepancy of at most $\min\{1,3.48745\sqrt{\alpha\log(2r)}\}$. We also give a deterministic algorithm achieving a discrepancy of at most $\min\{1,4.171\sqrt{\alpha\log(2r)}\}$ in $\widetilde O(mn^2+n^{6.38})$ real arithmetic operations. This dependence on $\alpha$ and $r$ is optimal up to an absolute constant when $0<\alpha\le1/256$ and $r\ge256\alpha^{-6}$: even diagonal matrices can force every signing to have a discrepancy of at least $\min\{1,\sqrt{\alpha\log(2r)}\}$. For a zero-one incidence matrix with at most $d$ ones in each row and each column, our deterministic algorithm achieves a discrepancy of $O(\sqrt{d\log(d)})$, recovering Harvey's bound [Har15] by a different method. We give a deterministic construction of a single spanning tree that is simultaneously spectrally thin with respect to any given collection of $k\ge1$ positive edge weightings of the same graph, assuming small edge leverage in every weighting. The tree retains the original edge weights, and its thinness bound grows only logarithmically with $k$.

Distribution-aware encryption seeks guarantees tailored to the probability law of the protected data and the secret key. We study simultaneous message-recovery, key-recovery, and target-distribution semantic security for arbitrary finite joint distributions, without assuming that messages and keys are independent. We represent encryption by a decomposition of the joint probability matrix and construct this decomposition through capacity-controlled randomized rounding. A stepwise conditional sampler turns the rounding process into a correct encryption algorithm without enumerating its output distribution or rejecting complete samples. Let $p_\star$ and $q_\star$ be the largest message and key probabilities. Our construction attains the exact message-recovery optimum $\max\{p_\star,q_\star\}$, has key-recovery success below $2q_\star$, and provides $O(\sqrt{q_\star})$ advantage against prediction of every fixed Boolean message predicate. The semantic guarantee follows from negative correlation of the binary row-rounding remainders. We prove that the key-recovery factor cannot be uniformly improved while preserving exact message-recovery optimality, and that the semantic bound has the optimal worst-case order. We also establish additive robustness under distribution error and short-ciphertext existence by preserving only the moments needed for the security proof. The general sampler runs in expected polynomial time in the explicit rational input size; short ciphertexts do not by themselves imply efficient preprocessing or compact public descriptions. Structured sources admit additional efficient implementations.

In order to estimate accurately the impact of large-scale computing devices, one requires a precise resource estimate of quantum algorithms for cryptographic problems. As a start, these algorithms can be described as quantum circuits. One then estimates the number of gates, qubits, and circuit depth that they require, as a first step towards physical resource estimates. In order to simplify this task, different quantum programming languages have been used, targeting different circuit sizes and abstraction levels. Quantum cryptanalysis is indeed a domain in which one may consider both medium-scale circuits with fine-grained optimizations (such as optimizations of Shor's algorithm) and very large-scale circuits with well-defined building blocks (such as exhaustive key search on block ciphers using Grover's algorithm). This paper presents Qarton, a python library to represent logical quantum circuits, focused on quantum cryptanalysis. It allows to study very large-scale circuits like Grover searches, to simulate classical or ``almost'' classical circuits such as the arithmetic building blocks of Shor's algorithm, and to analyze trade-offs between qubit and gate count when switching between different implementations of arithmetic operations. Qarton is equipped with a library of around 300 circuits and examples from different areas of quantum symmetric and asymmetric cryptanalysis.

Recent CKKS-based constructions support homomorphic arithmetic modulo powers of two and more general moduli. We explore a complementary tradeoff: using polynomial rings native to CKKS simplifies arithmetic and refreshing but restricts the message spaces. Building on Kim's interpretation of GBFV ciphertexts as CKKS ciphertexts, we use the decomposition $\mathbb{R}[X]/\langle X^N+1\rangle \cong(\mathbb{R}[X]/\langle X^n+1\rangle)^{N/n}$ into $N/n$ polynomial lanes, where $2\leq n\leq N$ is a power of two dividing the RLWE dimension $N$. Following GBFV, each lane represents a message in $\mathbb{Z}[X]/\langle X^n+1,t\rangle$, where $t$ is coprime to $X^n+1$ over $\mathbb{Q}$. These message spaces include $\mathbb{Z}_{\beta^n+1}$ for $t=X-\beta$, products of modular integer rings, specific 128-, 256-, 512-, and 1024-bit prime fields, and extension fields such as $\mathbb{F}_{5^{16}}$, $\mathbb{F}_{17^4}$, and $\mathbb{F}_{37^{32}}$. Unlike the triangle encoding of Gao and Zheng's construction (GZ), our lanes occur at intermediate stages of conventional CoeffToSlot and SlotToCoeff transformations, avoiding additional encoding-specific linear maps. We thus "stay in our lane" by performing arithmetic and refreshing within CKKS-native polynomial rings. Our arithmetic bootstrapping restores ciphertext levels, bounds polynomial representatives, and reduces approximation error. At $N=2^{16}$, it takes less than 4.5 seconds in every tested configuration, with little variation across $t$ and $n$. Comparing our arithmetic modulo $2^n+1$ with GZ's arithmetic modulo $2^n$, same-machine, same-library experiments show a $2.2\times$–$3.8\times$ speedup for $2^3\leq n\leq 2^6$. Our bootstrapping time remains nearly constant as $n$ grows, whereas GZ's dense encoding-specific transformations increase its cost and, at larger $n$, exceed available memory, preventing direct comparisons. At $n=2^{14}$, extrapolating GZ's published timings suggests a $26\times$ speedup.

To address the scalability and flexibility limitations of dedicated point-to-point cabling in broadcast production, the broadcasting community created a suite of standards for carrying media over IP multicast. This shift removes the inherent physical protection that dedicated cabling provides, exposing streams to tampering and eavesdropping. Such threats have been widely reported and pose major risks to broadcasters and their audiences. Despite almost a decade of deployment, the security of IP-based broadcast has received little academic attention. We collaborate with the European Broadcasting Union (EBU) to establish the security and deployment requirements of this environment. We introduce SafeCast, a system to secure the transmission of ultra-high-bitrate multicast media. SafeCast builds on established and standardized protocols (the MLS group key agreement protocol and the SRTP media-protection protocol), while extending and adapting them to the demanding setting of broadcast media. SafeCast provides strong confidentiality and integrity guarantees, and exploits the precise clock synchronization of broadcast networks to achieve cheap per-sender authentication. We evaluate SafeCast against the stringent deployment requirements of production facilities (throughput, latency, large dynamic groups) and find that it can sustain the most common media formats with ample headroom.

Multiparty private set union (MPSU) enables a group of mutually distrusting parties, each holding a private set, to learn the union of their sets without revealing additional information. MPSU is a fundamental primitive with applications to privacy-preserving tasks such as cyber-risk assessment and private record matching. State-of-the-art MPSU protocols require parties to sequentially shuffle encrypted values in order to hide which party contributed which inputs to the final result. We introduce a new paradigm for semi-honest MPSU that eliminates the need for such shuffling. This allows the protocol to run in constant rounds regardless of how many parties are involved. The resulting protocol also benefits from improved parallelism, an information-theoretic online phase, and native support for unbalanced input sizes, a situation most prior works must handle by padding inputs to hide individual input sizes. We implement and evaluate our protocol across a range of party counts, input sizes, and network conditions. In the unbalanced setting, where parties hold unequal-sized inputs, our protocol significantly outperforms the state-of-the-art schemes PULSE (CCS ’25) and DZBC25 (USENIX Security ’25). In the balanced setting, it achieves an order-of-magnitude improvement over PULSE in most settings and outperforms DZBC25 in WAN deployments with 100ms latency.

In a zkTLS protocol, a user proves to a third party a property of data obtained from an online service over TLS, revealing nothing beyond the statement proven. Each existing scheme, however, comes with its own security model, written for that scheme alone, so the schemes are not proven secure against a common definition. The root cause is a mismatch of levels: existing models are stated at the level of TLS and therefore reflect how each construction handles it. Yet TLS is only the transport, and a zkTLS proof is about the application-layer protocol executed over it. We therefore introduce the first transport-agnostic security model for zkTLS, stated at the application layer and mentioning neither TLS nor any particular construction. The resulting notion, Zero-Knowledge Proof of Protocol Execution (zkPoPE), defines what it means for a party that has executed an arbitrary two-party protocol with a counterparty to prove, in zero knowledge, that its private input and the reply it received satisfy a chosen property, and, crucially, that the reply comes from a real execution with that counterparty rather than being fabricated. This proof-of-execution requirement separates zkPoPE from a NIZK over the input--reply pair: knowing a satisfying pair does not by itself show that an execution occurred. We formalize zkPoPE as a UC ideal functionality F_{zkpope}. We then introduce the Reclaim Protocol, a zkTLS scheme that UC-realizes F_{zkpope} under a deployment-aligned trust model and underlies a production system. Reclaim builds on Distributed-AEAD, a new three-party authenticated-encryption primitive of independent interest. On a lower-mid-range phone, Reclaim attests to a 1200kB response in 7.28s, two orders of magnitude beyond any size previously benchmarked for zkTLS.

The dual attack is a central tool for evaluating the security of the Learning with Errors (LWE) problem, which is the foundation of the lattice-based cryptosystems such as ML-KEM. Since the introduction of FFT acceleration by Guo and Johansson (ASIACRYPT 2021) and subsequent optimizations in the MATZOV report, FFT-based dual attacks have achieved concrete security estimates for ML-KEM. However, these results rely on one specific independence heuristic that is known to fail in certain parameter regimes (CRYPTO 2023). Recent work by Pouly and Shen (EUROCRYPT 2024) initiated the study of provable dual attacks through explicit geometric analysis, but restricted the analysis to the orthogonal lattice, requiring approximately \(m\approx2n\) LWE samples. Qu and Xu (ASIACRYPT 2025) subsequently introduced modulus switching into the provable dual-attack setting, enabling evaluation over a smaller modulus, with a revised analysis given in their later version. More recently, a closely related ePrint revisited the concrete complexity estimates of these provable attacks after correcting the norm-bound formula used in the earlier analysis. In this work, we provide a provable correctness analysis of the Guo--Johansson-style FFT-based dual attack over the general dual lattice. By extending the analysis from the orthogonal lattice to $L_q(\mathbf{A}^{T})$, where $\mathbf{y}$ is not restricted to $\mathbf{0}$, we reduce the required number of LWE samples from $m\approx2n$ to $m\approx n$ while retaining the computational efficiency of FFT-based score evaluation. We further derive an explicit upper bound on the false-positive probability via an integral estimate for a geometric distinguishing event. For concrete complexity estimation, we follow the abstractions and cost models used in prior provable analyses while refining the probability-dependent treatment of the norm bounds. We obtain attack costs of $216$, $317$, and $426$ bits for ML-KEM-512, ML-KEM-768, and ML-KEM-1024, respectively. Compared with the recomputed estimates of the previous best published provable dual attack, these represent reductions of $22$, $30$, and $52$ bits, respectively.

Recent work has introduced the Hamiltonian phase state (HPS) assumptions, which postulate that Hamiltonian phase states can be used to instantiate pseudorandom and one-way state generators. Additionally, it has been conjectured that these assumptions can be true, even if one-way functions do not exist. This is exciting, because if true, then the HPS assumptions provide a route to the instantiation of Microcrypt. In this work we falsify this conjecture, by proving that if the HPS assumptions are true, then one-way functions exist. While this removes the possibility of instantiating genuine Microcrypt cryptography with Hamiltonian phase states, it shows that the HPS assumptions provide novel inherently quantum assumptions for the construction of classical cryptography. Technically we achieve this via a method for the construction of one-way puzzles from one-way state generators and tailored "measure first, ask later" state certification protocols. This generalizes prior constructions of one-way puzzles from one-way state generators via classical shadows and allows us to relate properties of the one-way puzzle to properties of the state certification protocol used in the construction. Specifically, if the state certification protocol admits efficient classical post-processing then one obtains an efficiently verifiable one-way puzzle, and if the state certification protocol can be efficiently classically simulated in a certain sense, then one obtains a classical one-way puzzle, which implies one-way functions. The latter observation allows us to prove that the HPS assumptions imply one-way functions, by exploiting properties of state certification protocols for phase states. The former observation provides a new toolbox for the construction of efficiently verifiable one-way puzzles by exploiting tailored state certification protocols for pseudorandom and one-way state generators.

Signatures with Post-Compromise Accountability (SPCA), introduced by Dayanikli et al. at SCN'26, are signature schemes that enable signatures generated before the compromise of a signing key to be distinguished from those produced after the compromise. In this paper, we extend this notion to static group signatures and introduce Group Signatures with Post-Compromise Accountability (GSPCA). GSPCA preserves the anonymity and traceability guarantees of group signatures while enabling pre-compromise signatures to be revalidated after key compromise. The coexistence of opening and revalidation algorithms gives rise to a new consistency requirement, which we formalize as opening--revalidation consistency. We present a generic construction of GSPCA from public key encryption schemes, signature schemes, and simulation-sound non-interactive zero-knowledge proof systems. A central technical difficulty is that the encryption randomness in our construction is derived from a randomized signature component and may therefore have high min-entropy without being uniformly distributed. To address this issue, we introduce adaptive hedged security against adaptive chosen-ciphertext attacks (AH-CCA), which extends indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) to adaptively chosen high-min-entropy message--randomness distributions, and show how to realize the required randomness-recovering encryption in the random oracle model. We also give a generic signature-based mechanism that provides the required min-entropy and key-binding properties. Finally, we show that ordinary IND-CCA2 security alone is insufficient as a general assumption for our construction by exhibiting an IND-CCA2 secure encryption scheme for which the resulting GSPCA scheme fails to satisfy anonymity.

Secure aggregation with input validation enables a server to securely compute the summation of private data from multiple clients while verifying that the inputs satisfy specific constraints. However, the practical deployment of this paradigm at scale is hindered by two primary limitations. First, existing schemes suffer from severe efficiency bottlenecks due to their reliance on generic, computationally expensive zero-knowledge proofs (ZKPs). Second, the scope of input validation is currently restricted to norm checks (e.g., $L_2$ and $L_\infty$) against public bounds. This paper presents \textsf{Vespa}, a single-server secure aggregation scheme that simultaneously achieves practical efficiency and expands validation capabilities to support both \textit{norm checks against public bounds} and \textit{similarity checks against private server inputs}. Specifically, we design a novel validity-weighted secure aggregation protocol over committed inputs, built upon highly efficient vector oblivious linear evaluation (VOLE). To efficiently realize input validation, we introduce customized $L_2$ and $L_\infty$ norm checks based on VOLE-based ZKPs, centered around optimized range proofs with reduced range sizes. Furthermore, we extend our framework to support advanced similarity-based checks against private server inputs, instantiated with widely used Euclidean and cosine similarities. This allows \textsf{Vespa} to first filter out invalid inputs using norm checks, followed by performing fine-grained validation via similarity metrics. We compare our scheme with the state-of-the-art secure aggregation works, including RoFL (S\&P 2023), ACORN (USENIX Security 2023), and Armadillo (CCS 2025), and extensive evaluation shows that our $L_2$ and $L_\infty$ norm checks achieve runtime improvements of up to $2\sim 3$ and $1\sim 3$ orders of magnitude, respectively. Our similarity checks also achieve practical performance, consuming only around $94$ seconds for an $818$k-entry vector.

Lexical search retrieves documents containing query keywords that require exact matches, such as rare terms, entity names or codewords. Search is increasingly hosted in the cloud, which places both the corpus and every query on infrastructure the data owner does not control. Encrypted lexical search addresses this concern by ensuring no third party, including the cloud provider, learns which queries are issued or which documents are retrieved. The key binding constraints are all on the client — accuracy, memory, computation, and communication — since cloud capacity is elastic. Existing approaches that guarantee full privacy without caveats require prohibitively high client-side persistent storage or communication. We present Lexicure, a protocol for encrypted lexical search that reduces the search to arithmetic operations favorable to cryptographic primitives, such as encrypted matrix–vector products (EMVP). Across sixteen diverse datasets, Lexicure retains over $95\%$ of plaintext BM25 accuracy on average. Lexicure sets a new baseline for leakage-free lexical search, requiring 2.6-9.9$\times$ less communication than alternative approaches and less than 1KB of client-side storage. A major challenge is that secure lexical search is inherently bandwidth-bound. We additionally describe an approach for compressing the communication further in exchange for a larger server. To do so, we introduce a new cryptographic primitive that modifies EMVP to securely compute quadratic and higher-degree functions, more efficiently than a direct reduction. Lexicure demonstrates that leakage-free encrypted search with practical performance is achievable and opens new avenues for secure information retrieval systems.

Unbalanced Oil and Vinegar (UOV) and its variants are among the candidates in the NIST call for additional post-quantum signatures. Their security rests on the hardness of recovering a hidden subspace on which a public system of quadratic forms vanishes. In characteristic $2$ the polar forms of such a system are alternating, which a recent attack exploits by working in the exterior algebra rather than the polynomial ring. Unlike its polynomial-ring counterparts, it either applies at a threshold fixed by the parameters or not at all, and for most proposed parameter sets it does not. We remove this threshold and improve complexity in two independent ways. First, over the integers the square of an alternating polar form is $\omega \wedge \omega = 2\,\omega^{(2)}$, so in characteristic $2$ it vanishes only because the factor $2$ does. Dividing that factor out before reducing leaves the divided square $\omega^{(2)}$, which still vanishes on the oil space but is in general not a consequence of the original equations. Iterating gives a whole tower $\omega^{(2^j)}$ of new equations. Second, the symmetric powers $\textrm{Sym}^d\mathbb{F}_q^n$ and the exterior powers $\bigwedge^a\mathbb{F}_q^n$ are the two extreme shapes of the Schur modules $L_\lambda\mathbb{F}_q^n$. We introduce an extension of Macaulay matrices to an arbitrary shape $\lambda$ which we call Schur--Macaulay matrices. For both constructions we conjecture a Hilbert series and verify it experimentally. We also extend the approach to odd characteristic. The attack then applies to every Round-2 parameter set of UOV, MAYO, SNOVA, and QR-UOV but one. Four of the alternate Round-2 parameter sets of MAYO fall below their claimed security level while being out of reach of all previous attacks. After disclosing preliminary results to the MAYO team, a parameter set designated for Round-3 was discarded and parameters increased. For SNOVA, the divided powers remove the spurious kernel elements that obstructed the exterior algebra attack, and seven of the eleven Round-2 parameter sets fall below their claimed security level, and the complexity estimates drop further compared to previous attacks.

A Gaussian leftover hash lemma (LHL) states that, for a matrix $\mathbf{X}$ with discrete Gaussian columns and a sufficiently wide Gaussian vector $\mathbf{v}$, the product $\mathbf{X}\mathbf{v}$ is close to a discrete Gaussian. Over the integers this is a classical tool, and Albrecht-Felderhoff-Lai-Lapiha-Woo (EUROCRYPT'26) recently extended it to modules over a number field $K$ of degree $d$. In every version, the lemma rests on two facts about the kernel lattice of $\mathbf{X}$: that $\mathbf{X}$ is surjective, and that the smoothing parameter of the kernel is small. We prove both facts with a single analytic estimate. An exact identity expresses the Gaussian mass of the dual kernel, multiplied by the index of the image of $\mathbf{X}$, as an integral of one-dimensional periodic Gaussian sums over a torus. Bounding this integral below two forces the index to be one, which is surjectivity, and bounds the smoothing parameter at the same time. No separate surjectivity argument and no GRH are needed. For smoothing error $2^{-\lambda}$ the smoothing parameter is $O_K(\sqrt\lambda)$ with explicit constants, once $\mathbf{X}$ has $m\gtrsim dr\ln(srm)$ columns, and a deterministic lower bound shows that this order is optimal. The width $s$ of the matrix enters only through the number of columns. Over power-of-two cyclotomic fields the theorem even applies to matrices whose integer coefficients follow a discrete Gaussian of width one. In the SIS-to-$k$-SIS reduction of Albrecht et al. (EUROCRYPT'26), the new bound lowers the hint width from $d^{39/2}\lambda^{9/2}$ to $d^{3/2}\lambda^{3/2}$ and the norm loss from $d^{41/2}\lambda^{5}$ to $d^{3/2}\lambda^{2}$, up to logarithmic factors. Additionally, we also formalized the main results of the paper in Lean.

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings to any efficient adversary. Most prior PRC work focuses on Hamming error channels; nevertheless, the few proposed constructions on edit channels are not optimized for a stochastic channel with both Hamming and synchronization errors. We study PRC over a stochastic memoryless Binary Substitution-Insertion-Deletion (BSID) channel and its generalized $q$-ary version. At each current input symbol, the channel inserts a uniformly random symbol without advancing with probability $P_i$, deletes and advances with probability $P_d$, or transmits and advances otherwise; a transmitted symbol is then replaced uniformly by another alphabet symbol with probability $P_s$. We first prove that the majority based PRC construction of Christ and Gunn remains robust over the BSID channel whenever $1-P_i-P_d>0$ and $P_s<1/2$, by proving its majority decoding after the BSID channel recovers more than half of the original coordinates by a constant margin with overwhelming probability. Then we propose a unique-decodable public-key multi-bit PRC on a constant alphabet constructed by letting the Christ--Gunn majority component protect control information and the Haeupler--Shahrasbi synchronization/list-recovery construction encodes the high-rate payload. For every sufficiently large admissible constant alphabet q depending on the channel parameters, the PRC is robust against a q-ary SID channel bounded by $P_i+P_d<1$, $P_s<$1, and its rate approaches the genie-aided capacity upper bound of the channel when q approaches infinity.

VDOO is a Rainbow-like multivariate signature scheme with additional ``diagonal” structure intended to resist structural attacks. We show that its security is governed primarily by the first two oil layers, while the diagonal structure has negligible impact, and that all proposed parameters fail to meet their claimed NIST security levels. We provide a corrected complexity analysis of the Simple and Rectangular MinRank attacks, introduce a hybrid Simple–Padded MinRank attack, and compare their effectiveness. Open-source code is provided for independent validation, clarifying VDOO’s true security and informing future Rainbow-type post-quantum designs.

Wide-block block ciphers have attracted significant interest due to emerging high-throughput encryption requirements and NIST's Accordion Mode Process. The primary choice for such ciphers is Rijndael-256, also known as WAES. At the same time, independent efforts continue to explore more efficient designs and implementations. In this paper, we present LEANY, a 256-bit block cipher with a 256-bit key. LEANY is a nibble-oriented SPN whose state is an 8×8 matrix of 4-bit nibbles. Each round consists of four layers: key addition, a 4-bit S-box layer, row-wise nibble shifts, and multiplication by an 8×8 MDS matrix over $\mathrm{GF}(2^4)$. This structure follows the same shift-then-mix principle as AES, but with a wider state and a smaller cell size. LEANY consists of only 12 rounds. Since the linear diffusion layer has branch number 9, the wide-trail strategy guarantees that every four consecutive rounds activate at least $9^2=81$ S-boxes in any differential or linear characteristic. Consequently, upper bounds on the best differential and linear trail probabilities fall below $2^{-256}$ after seven rounds. We further analyze LEANY against impossible differential, invariant subspace, integral, meet-in-the-middle, boomerang, and several algebraic attacks. Finally, FPGA implementations demonstrate both compact and high-performance hardware realizations: the iterative architecture occupies only about 1.4K LUTs, whereas the fully pipelined architecture achieves a steady-state throughput exceeding 50 Gbps. Compared with existing 256-bit wide-block block ciphers, including WAES, LEANY provides substantially better area efficiency and competitive throughput (TP) and throughput-to-area ratio (TAR) results.

Spending limits are the workhorse of custody policy, yet in every deployed threshold-signing stack they live outside the signing protocol—in centralized policy engines, on-chain covenants, or hardware co-signers—where they leak budget state, bind to a single chain, or add a trusted bypass surface. The workload is compounding: agent payments passed one hundred million transfers on a single chain in under a year. We initiate the study of protocol-native spending limits: per-epoch budgets secret-shared among the signers and enforced inside the signing session, with unchanged on-chain verification. We first show that the natural approach fails: gating a threshold signature with a passively secure MPC comparison admits a deterministic bypass. For the class of linear gatein-combination protocols we prove that every member signs over-budget transactions with probability one, disguised against any transcript auditor up to the statistical masking bound. We then construct BTS, a budgeted threshold Schnorr scheme with a formal budget-soundness definition for honest-majority configurations. The gap is closed with an authenticated gate: in implementation, every attack attempt is caught before a signature is produced, at a measured cost of 3.4–3.7× multiplications and five extra rounds. Batched over k=20 payments, enforcement amortizes to about one network round trip per payment in our WANmodeled prototype.

Succinct proofs for arithmetic modulo powers of two are crucial for verifying machine-word computations in practice. However, designing SNARKs over such rings is challenging, since they lack the algebraic properties that common SNARKs over fields rely on to achieve negligible soundness error. Existing approaches either work over Galois rings, whose arithmetic is expensive, or lift the statement to the integers and prove it over a large random prime field, which is also several times slower than the structured primes used in practice. We present $\mathsf{Rotor}$, an efficient SNARK for circuits over $\mathbb Z_{2^k}$. Unlike prior work, $\mathsf{Rotor}$ operates natively over power-of-two rings and derives its soundness from three levels of ring precision. To prove statements over $\mathbb Z_{2^k}$, we first construct a sumcheck-style interactive oracle proof with tensor queries over a larger ring $\mathbb Z_{2^m}$. We then establish a weakened proximity gap for linear codes, in which proximity testing over a still larger ring $\mathbb Z_{2^\ell}$ ensures that the underlying vectors are close to the code after reduction to $\mathbb Z_{2^m}$. This yields a Brakedown-style commitment with tensor evaluation proofs over $\mathbb Z_{2^m}$. In both cases, a sufficiently large gap between the precisions guarantees negligible soundness error. Finally, we introduce compatible commitments, which link ring witnesses to their binary-field representations and enable permutation checks over fields to verify permutations over $\mathbb Z_{2^k}$, completing the construction of $\mathsf{Rotor}$.

Cashu, the dominant deployed Chaumian ecash system, has grown to 31 specification documents, 58 indexed mints, and seven interoperable wallets, while the cryptographic literature has studied only its blind-signature core. Every incident in the system’s short audited history, including a cross-mint theft disclosed in early 2026, is compositional: it emerges from keyset rotation, wallet recovery, and multi-mint identity. We give the first system-level security analysis of a deployed ecash system, built on a five-layer model, a nine-property family (three properties new), and a stateful one-more-unforgeability theorem whose proof separates forgery from theft; the deployed attacks commit theft without forging anything. We reproduce the disclosed theft end-to-end, exhibit a strictly stronger public-key-claim variant, and measure all 58 indexed mints: every reachable mint declares support for DLEQ proofs, the sole remaining defense, yet declarations are unauthenticated the guardrail sits with the issuer, not the wallet. A theft theorem gives necessary and sufficient conditions for prevention, and replaying three fixes shows the cheapest one costs honest issuers nothing. A defect taxonomy and a three-system comparison suggest a broader lesson: recoverability is not free. All artifacts are pure standard-library Python and pass the 49 o cial test vectors.

Upgrading cryptocurrencies to post-quantum security is inherently difficult, because their on-chain state associates users' holdings with public keys: users who fail to transfer their funds to (yet to be added) post-quantum signature schemes remain exposed to theft. In networks with Confidential Transactions (CT) such as Liquid, Monero, and Grin, which hide monetary amounts inside homomorphic Pedersen commitments, the situation is worse still: an adversary who computes a single discrete logarithm can inflate the currency as a whole, rather than merely steal individual funds. The contentious remedy is to expire all funds not transferred by a deadline, destroying the funds of everyone who fails to act. Switch commitments (Ruffing and Malavolta 2017) were proposed to avoid exactly this expiration, but only Grin has deployed them deliberately—and the security theorem later stated for its scheme does not hold, as we show. In this paper, we show that Liquid and Monero already deploy a switch commitment scheme by coincidence: the ciphertext a sender stores on-chain to convey the hidden amount to the recipient can be re-interpreted, together with the Pedersen commitment, as a switch commitment. We conceptualize this construction as coincidental switch commitments and prove it secure in the quantum random oracle model. Additionally, we save the construction that Grin deploys: it is computationally switch binding, with practical bounds in the algebraic group model. The real-world implication of our results is that these networks can be upgraded to post-quantum CT schemes without expiring any user funds.

SQIsign samples a random ideal of odd prime norm at every key generation and every signature through $\mathbf{PrimeNormIdealInertSampling}$. We revisit this step from a new perspective: the inert ideals of a given norm form a circle modulo the norm, and drawing lines through a fixed point of this circle turns a single random parameter into an ideal, hitting each ideal exactly once. Compared with the reference implementation, the new algorithm requires one modular inversion and a handful of additions and multiplications. It achieves $13.76\times$ speed-up at NIST security level I in SQIsign while producing an uniform output.

Quantum linear key-recovery attacks using QFT-based correlation state preparation can achieve superquadratic speedups, but their complexity grows rapidly with the active subkey dimension, potentially erasing the advantage over Grover's search. WSP (EUROCRYPT 2024) provides a natural mechanism for alleviating this bottleneck by replacing the key-recovery map with a spectrally punctured approximation of smaller active dimension. In this work, we establish a puncture-aware framework for QFT-based quantum key recovery, extending quantum linear cryptanalysis to key-recovery problems whose active-subkey dimension can be reduced through spectral puncturing. We further propose Q-Puncture, an automated optimization method tailored to quantum key-recovery complexity. Applied to Serpent, RECTANGLE-128, and PIPO-128, Q-Puncture yields a new family of punctured quantum linear key-recovery attacks whose modeled quantum complexities improve upon generic Grover search. The resulting attacks improve upon comparable QFT-based results, extend them to new settings, and provide further examples in which structured quantum cryptanalysis surpasses the generic quadratic speedup of Grover's search.

Falcon is one of the three post-quantum signature schemes selected by NIST for standardization so far. It is efficient and has particularly short signatures, but has the drawback of being difficult to implement correctly and securely, owing to its use of floating point arithmetic and secret-dependent lattice Gaussian sampling. In particular, obtaining implementations of Falcon that are protected against side-channel attacks seems to be a tremendous challenge that has no satisfactory solution so far. While it is theoretically possible to rely on generic countermeasures like masking, they are likely so costly as to be effectively inapplicable. And yet, side-channels are an actual threat to Falcon: a number of them have been demonstrated against various parts of the signing algorithm, including floating point operations and Gaussian sampling. Multiple power analysis attacks in fact achieve full key recovery from very realistic numbers of traces. This is especially the case for a series of side-channel attacks that can be broadly categorized as based on “sign leakage” within a specific part of the one-dimensional Gaussian sampler. In this paper, we take a closer look at this class of side-channel attacks, and obtain yet another one of a somewhat different flavor: while it also targets the sign of a variable in the one-dimensional Gaussian sampler, that variable is the input center, and in particular does not depend on the sampling randomness, making previously proposed mitigations modifying the base sampler ineffective. Furthermore, we propose, analyze and experimentally validate a novel, inexpensive countermeasure to protect Falcon against this class of side channel attacks. The idea, taking inspiration from shuffling, is to twist the target vector by random roots of unity in every recursive call of the fast Fourier sampling algorithm: this averages away the sign leakage efficiently. While this mitigation technique is heuristic and does not offer the provable guarantees of masking, it significantly enhances the physical security of Falcon fairly cheaply. In particular, it provides a more robust and more widely applicable protection than the countermeasure of Lin et al. (PKC 2025) at a much lower cost (incurring a 1.4-fold overhead in signing in dynamic mode and 2-fold in tree mode, compared to 3.5-fold and 6.8-fold for Lin et al. respectively). To the best of our knowledge, this is the first shuffling countermeasure proposed for Falcon.

AIMer v3 replaces AIM2 with AIM3. We test whether SIMD methods developed for AIM2 can accelerate AIM3 while preserving its results. We port the field-arithmetic, affine, party-parallel, and SHAKE methods of the earlier AVX-512 implementation to AIMer v3 and implement the same operations for AVX2. For Cortex-M55 MVE, we use 16-bit polynomial partial products for field multiplication, group corresponding 32-bit words from four parties, and vectorize both affine layers, including the input layer introduced in AIM3. The implementations preserve AIMer v3’s mathematical structure and proof procedures. For all six parameter sets, their outputs match the official known-answer tests and the reference results in differential tests. Relative to the reference on each platform, AVX2 and AVX-512 accelerate signing and verification by 3.14–4.41× and 4.59–6.55×, respectively. Cortex-M55 MVE accelerates the same operations by 1.28–1.91×.

Efficient execution of Post-Quantum Cryptography (PQC) in resource-constrained embedded environments requires the joint optimization of not only algorithm vectorization but also dataflow and instruction execution order. This paper implements the HAETAE-2/3/5 and SMAUG-T1/3/5 parameter sets of two Korean Post-Quantum Cryptography Competition (KpqC) winners using the M-profile Vector Extension (MVE) of the Arm Cortex-M55 and analyzes the contribution of each optimization stage to performance improvement. We first establish an MVE-intrinsic implementation as the baseline and then present Manually Optimized MVE Assembly that redesigns the data layout, register reuse, and memory access patterns of the principal kernels. Slothy is subsequently applied to this assembly to optimize instruction order and register allocation for the Cortex-M55 pipeline. This process is applied to the Keccak/SHAKE operations shared by the two schemes; the Number-Theoretic Transform (NTT), fixed-point Fast Fourier Transform (FFT), and Gaussian sampling of HAETAE; and the Toom-Cook/Karatsuba polynomial multiplication of SMAUG-T. Measurements on the STM32N657 show that the implementation with Slothy achieves speedups of 2.349–2.424× for the HAETAE forward NTT, 1.701–1.732× for the FFT including squared-value accumulation, and 1.322–1.350× for the SMAUG-T matrix–vector multiplication over the intrinsic implementation. At the complete-scheme level, HAETAE and SMAUG-T achieve speedups of 1.050–1.212× and 1.108–1.212×, respectively. These results demonstrate that direct dataflow redesign and automated instruction scheduling eliminate different bottlenecks and that combining the two stages can effectively improve the performance of Cortex-M55-based PQC implementations.

We present new constructions of the following primitives featuring succinct communication: - Batch threshold encryption: Assuming RSA and DCR, we construct a threshold encryption scheme in which a batch of ciphertexts can be decrypted via short hints from a quorum of decryptors. Previously, this was known only from bilinear maps. - Aggregate signatures: Assuming RSA, we construct a signature scheme where signatures on different messages from an arbitrary number of signers can be aggregated into one signature. Our construction achieves bounded-query security. In contrast to prior (fully secure) schemes in the standard model, ours makes black-box use of cryptography. - Broadcast encryption: Assuming RSA, we construct a secret-key encryption scheme where a sender can encrypt a message to multiple recipients via a short ciphertext. Our construction achieves bounded-query security. Previously, (fully secure) broadcast encryption was known from bilinear maps or obfustopia or nonstandard lattice assumptions. Our constructions are simple and achieve optimal succinctness in the key parameter (decryption batch size or number of signers or recipient set size). In this metric, they outperform or match known constructions. Our results are obtained by applying the lens of projective pseudorandom generators (PPRGs) to these problems. Towards this, we identify new enhanced properties for PPRGs and instantiate them from the RSA assumption.

The dual attack is a central tool for evaluating the concrete security of the Learning with Errors (LWE) problem, which underlies lattice-based cryptosystems such as ML-KEM. The MATZOV-style FFT dual attack combines dual distinguishing with an FFT-accelerated guessing phase and provides one of the main frameworks for concrete attack estimates against ML-KEM. However, its correctness analysis has traditionally relied on heuristic independence assumptions, leaving a gap between practical attack estimates and provable guarantees. In this work, we give a rigorous correctness analysis of a MATZOV-style FFT-based dual attack for the ML-KEM parameter sets. The analysis treats the correct and incorrect candidates separately and applies different conditioning arguments on the two sides, because the former requires a provable lower bound on the score of the true candidate, while the latter requires a uniform upper bound for all wrong recovered guesses. Combining these two parts, we obtain an explicit success criterion and a provable threshold separation for the FFT score. For concrete cost estimation, we follow the same cost-estimation convention as previous provable dual-attack analyses whenever the same subroutine is involved, using Pouly and Shen's estimates (EUROCRYPT 2024) as our main baseline. We obtain attack costs of 210, 300, and 410 bits for ML-KEM-512, ML-KEM-768, and ML-KEM-1024, respectively. Relative to this baseline, our estimates reduce the attack costs by 28, 47, and 68 bits for ML-KEM-512, ML-KEM-768, and ML-KEM-1024, respectively.

We present Argo, a randomized encoding scheme for the invalidity of pairing-based SNARKs like Groth16. Argo allows an encoder to encode a proof such that a decoder can derive a secret if the proof is invalid. We prove the selective security of invalidity Argo, as well as the adaptive security of validity Argo, under DDH in one source group of a bilinear pairing in the standard model, a standard assumption that holds in the generic group model used to analyze Groth16. We show how to couple invalidity Argo with a projective garbling scheme like Argo MAC or Duty-Free Bits to construct a garbled circuit for Groth16 invalidity as a function of the proof bits, and how to use it with BitVM to construct a permissionless, optimistic Groth16 verifier for Bitcoin: a decoder proves a proof invalid by publishing a secret, and the decoder can be anyone, not necessarily known in advance. When instantiated with BN254, Argo has an offline encoding size of about 21 kB, a thousand times smaller than the projective garbling scheme, and an end-to-end protocol size more than three orders of magnitude smaller than existing Yao-based approaches. Generating an Argo + Argo MAC garbled circuit takes tens of milliseconds on a laptop, compared to minutes for a Yao GC. Argo is the first protocol that makes permissionless, optimistic SNARK verification on Bitcoin practical.

Updatable Public-Key Encryption (UPKE) enables forward secrecy in asynchronous settings like secure group messaging. At EC'25, Albrecht, Benčina and Lai proposed the first plausibly post-quantum UPKE scheme supporting unlimited updates, based on permutation code equivalence (PCE) over finite fields and hollow lattice problems. However, it has impractically large public keys (4.8MiB) and ciphertexts (1.5MiB). In this work, we first replace the information-theoretic Hollow LHL with a computational assumption secure under binary-secret binary-error LWE, reducing key sizes by an order of magnitude. Second, we show that generalising to Module-LWE is not beneficial: PCE instances over $\mathbb{F}_{q^d}$ admit a linearisation attack via the $q$-Frobenius structure, enabling recovery of secret isometries unless code rates are inflated by $d$, negating any size benefit from module lattices. Third, we establish IND-CCA security in the model of Alwen, Fuchsbauer and Mularczyk (EC'24), but do not achieve `joiner security' like other post-quantum candidates. Finally, we introduce a heuristic multi-key variant using matrix-valued secret keys, enabling efficient encryption of $\ell$ bits per ciphertext. We define the Hinted SPCE assumption to capture the main cryptanalytic challenge and show that the performance gain is likely too small to justify adoption, unless the new assumption can be avoided. Overall, our `unlimited' scheme has update sizes 3.5 to 10 times larger than lattice-based schemes limited to $2^{20}$ updates, depending on the aggressiveness of parameter choices.

Oblivious RAM (ORAM) protocols enable a resource-constrained client to outsource data to an untrusted server, and access this data without revealing what is being accessed. While ORAM protocols are almost optimal, concretely efficient ORAM protocols incur sub-optimal bandwidth overhead and require multiple roundtrips of communication between the client and the server. In this work, we introduce write-public ORAM: a relaxed variant of ORAM that hides what data is being read, but not what data is being updated on the server. We present wpORAM, a write-public ORAM that modifies Path ORAM to achieve a log N-factor improvement in bandwidth and roundtrips over Path ORAM during writes. The asymptotic cost of reads in wpORAM remains the same as Path ORAM, with a slight slowdown in practice. wpORAM, when used with a Trusted Execution Environment (TEE), can implement a dynamic Private Information Retrieval scheme that efficiently updates data stored in a public database. We use wpORAM to implement a private blockchain RPC server that enables blockchain clients to query RPC nodes without revealing their queries to the server operator. Our evaluation shows that, while syncing with the latest blockchain state, our RPC node achieves a 3-4x speedup over Path ORAM. Our RPC node can serve reads with a slowdown of approximately 23% compared to Path ORAM.

A pseudorandom code (PRC) is a cryptographic primitive combining pseudorandom encryption and error-correcting codes (Christ and Gunn, CRYPTO 2024). That is, any polynomial number of codewords are pseudorandom, and decryption tolerates a constant rate of bit-flips. Although this might seem like a natural combination of standard properties, it is a fundamentally new object: PRCs are black-box separated from many primitives, including one-way functions, public-key encryption, and even virtual black-box obfuscation (Döttling et al., Garg et al., TCC 2025). Pseudorandom codes were introduced to build watermarks for AI-generated content. In particular, they imply watermarks that preserve the model's quality in a strong sense and withstand modification of the content. This relationship makes pseudorandom codes an inviting area for researchers: improvements to this simple theoretical object yield better watermarks. Beyond watermarks, PRCs have been used to construct error-correcting codes against computationally bounded channels (Lu et al., CRYPTO 2026), and techniques underlying them have led to new public-key encryption schemes (Döttling et al., CRYPTO 2026, Dyseryn et al. ASIACRYPT 2026). This survey aims to equip the interested researcher with tools to make progress in the area. We detail the current landscape of definitions, techniques, and applications. A main contribution is introducing new tricks and assembling existing tricks to generically strengthen PRCs (e.g., from substitution-robustness to random-deletion-robustness). We also show natural weakenings of PRCs that can be constructed from OWFs or even unconditionally. We conclude with a number of concrete open questions.

This paper studies the cryptanalytic extraction of convolutional neural networks (CNNs). Existing cryptanalytic extraction attacks on CNNs assume that the network architecture is known, and try to recover model parameters. In this paper, we prove for the first time that the architecture assumption can be removed for CNNs with both max and average pooling. Our core finding is that the spatial geometry of the weight vectors recovered by existing parameter-recovery attacks naturally leaks the architecture. We formalize this geometry and establish its correspondence with the architectural knowledge of a convolutional layer: (1) The sparsity consistency with the convolution receptive field reveals the layer type, the kernel size, and the stride; (2) The numerical consistency with the kernel parameters reveals the padding mode and the output-channel number; (3) The structural consistency with the pooling operation reveals the pooling type, the window size, and the stride. Although the recovered vectors are obtained using different methods in the raw-output and hard-label settings, their spatial geometry remains the same. Therefore, our architecture recovery is feedback-agnostic: combined with a parameter-recovery attack, it yields a complete cryptanalytic extraction framework that recovers both the architecture and the parameters in the black-box setting. Extensive experiments, including both layer-wise and end-to-end ones, on a wide range of CNNs demonstrate that simultaneously recovering the network architecture and the model parameters is practical.

We present $\mathsf{Accordion}$, a new proof system that works in two steps: - $\textit{Accumulate}$: The first building block is a multi-folding scheme that efficiently accumulates $k$ different instances of a degree-$d$ polynomial relation into a single accumulated instance, without using recursion. Our scheme builds on the Protostar [Bünz & Chen, ASIACRYPT '23] and Protogalaxy [Eagen & Gabizon, ePrint 2023/1106] line of work, improving further the verifier efficiency. It supports the same expressive class of relations, arbitrary-degree polynomial constraints, enabling efficient folding for CCS, Plonkish constraints, and even custom gates. - $\textit{Decide}$: The second block is a SNARK decider for the folding scheme, which efficiently proves the validity of the resulting accumulated instance using off-the-shelf optimized building blocks. We give a concrete instantiation consisting of a Plonk-based proof plus an additional KZG polynomial commitment opening. This design is especially attractive in batch-aggregation settings where a prover collects many independent witnesses, folds them into a single accumulator, and then runs one succinct decider to certify the entire batch. Our scheme avoids costly recursion overheads. We implement $\mathsf{Accordion}$ and evaluate it against a highly optimized Plonk proving pipeline ($\texttt{midnight-zk}$). For $k=64$ instances, $\mathsf{Accordion}$ is up to $2.5\times$ faster than computing $k$ Plonk proofs for SHA-256 preimages, with a $3\times$ faster verifier and $4\times$ smaller proofs. Its prover is also an order of magnitude faster than using IVC to aggregate the $k$ proofs.

Many cryptographic protocols rely on affine message authentication tags of the form \({\boldsymbol\sigma}=\Delta{\boldsymbol x}+{\boldsymbol k}\), the batch version of information-theoretic MAC. Generating the tags for a long message vector typically requires communication linear in its length. Recent chosen-input VOLE protocols achieve succinct communication, but do not allow the authenticator’s key $k$ to be fixed in advance. We introduce $\mathit{batch\text{-}MAC}$, a primitive that authenticates a chosen message vector in two messages while allowing the authenticator’s key vector to be generated beforehand from a short seed. For a vector of length \(m\), we construct batch-MACs with \(O(m^{2/3}\lambda)\) communication under the decisional composite residuosity (DCR) assumption and \(\operatorname{poly}(\log m,\lambda)\) communication under the learning with errors assumption. Both constructions require a common reference string (CRS). We find applications in constrained pseudorandom functions, 2-message 2PC, and succinct zero-knowledge arguments.

The Terrapin attack against SSH channel integrity (USENIX Security 2024) used a novel attack vector: attacks on the channel state. Surprisingly, not all AEAD modes of SSH were equally affected by this attack, and it remained an open question if "unaffected" meant "secure". Existing formal models for secure channels are based on stateful encryption. However, these models do not define what the channel state is and how it is used as input to the different AEAD modes. In this paper, we propose a formal model for channel integrity under partially chosen state. Applied to the Terrapin attack, the chosen state is the SSH sequence number. It uses an abstract stateful encryption interface, for which we provide pseudocode descriptions for the eight most prominent AEAD modes used in SSH. By varying the SND oracle, we can model ciphertext-only (CO; the Terrapin attack), known-plaintext (KPA), and chosen-plaintext (CPA) attacks. This allows us to establish concrete bounds on the security of the AEAD modes. We find that all three Encrypt-then-MAC (EtM) modes and ChaCha20-Poly1305 in SSH are insecure in the CO model. AES-GCM is the only cipher secure in all three model variants. Going beyond Terrapin, we show that Encrypt-and-MAC (EaM) with a CBC cipher is secure, even in the KPA model. In particular, we describe a novel BEAST-like chosen-plaintext attack on the channel integrity of EaM-CBC, which separates the KPA and CPA models for this scheme.

In this work, we verify, using the Lean 4 proof assistant, that the Jolt zk-VM's expanded programs faithfully emulate a RISC-V CPU. Prior work translated the official Sail specification of RISC-V into Lean. We extend this model to define the Jolt ISA in Lean. We build a generator that runs Jolt's Rust bytecode expander and renders its output as Lean programs. Finally, for 51 out of 58 such programs, we prove these expansions are equivalent to their corresponding RISC-V instructions. This lays the groundwork for proving completeness and soundness of further stages of Jolt's proving pipeline.

Goldreich's pseudorandom generators (PRGs) expand a secret seed by evaluating a fixed low-locality predicate on random subsets of its bits. We study the concrete and asymptotic security of constructions whose local predicate combines majority with XOR. We introduce Deterministic Pooled Recovery (DPR), which guesses a set of seed positions and pools the outputs whose majority inputs are forced by the guess. The selected outputs yield noiseless sparse linear equations. For the proposed \(\operatorname{MAJ}_7\oplus\operatorname{XOR}_4\) challenge published in ToSC 2025, with seed length \(n=1024\) and output length \(m=n^2\), DPR has an estimated recovery cost of \(2^{109.71}\) operations using \(\omega=2.38\) for the linear-algebra exponent. This is below the claimed 128-bit security level. We also refine the common-bias analysis by evaluating its advantage at each fixed seed weight. This viewpoint motivates Bias-Amplified Pooled Recovery (BAPR), which uses partial majority bias to construct pooled noisy linear systems. For \(m=n^s\) with fixed \(s>1\), odd majority locality \(a\in\omega(1)\cap O(\log n)\), and fixed XOR locality \(b\ge3\), we prove that BAPR admits a worst-case \(2^{o(n)}\)-time implementation that recovers any fixed seed with high probability. This rules out exponential security in this intermediate-locality regime. In addition, we identify exploitable affine structure and residue constraints in proposed alternative predicates.

Adaptor signatures enable conditional payments on blockchain networks: a pre-signature is bound to a public instance $Y$ and can be completed into a valid signature by any party knowing a witness $y$ with $\mathcal{R}(Y,y)=1$, while the pre-signature and full signature together allow the signer to extract $y$. Existing constructions only support specific algebraically-structured relations, lose witness privacy, or have significant overhead both in signature size and computation. We present a practical adaptor signature framework for arbitrary NP relations, built from a new primitive we call Online/Offline NIZK whose proof is separated into online and offline parts. The key property is that the witness can be extracted from the online part knowing the randomness used in the offline part. We give two generic constructions: a basic scheme achieving witness hiding, and an instance-hiding scheme achieving a new, stronger forward-secure privacy notion we introduce. We instantiate our framework for the AES-128 relation using the VOLE-in-the-Head paradigm and the FAEST post-quantum signature scheme. The resulting complete signature is $11.6$ kB, roughly $60\%$ smaller than the state-of-the-art adaptor signature for NP (Ciampi et al., CT-RSA '25), and our implementation is an order of magnitude faster in overall signature generation, verification, and extraction.

The Round-3 SNOVA signer samples vinegar variables, which are elements of $\mathbb{F}_q$, by reducing uniform byte strings modulo a power of $q$. We show that the resulting bias leaks secret-key information for the six odd-characteristic alternative parameter sets. Even though the leakage is small (the most leaky variables leak at most $0.086$ bits of information), this still leads to efficient key-recovery attacks which we demonstrate in practice. Key recovery becomes a $q$-ary LPN problem of dimension $o\ell$ with a known, full-support error distribution. A naive algorithm needs some ten thousand signatures and $2^{90}$ to $2^{130}$ operations, which is already far below the $170$ to $331$ bits claimed for the six affected sets. Using more signatures makes the attack practical: using standard LPN machinery - BKW reduction with Fourier hypothesis testing - we recover the secret key for four parameter sets in practice using between $9$ and $180$ million signatures, and at most 16 minutes of wall clock time. Fixing SNOVA to sample the vinegar variables uniformly would prevent the attack completely.

Many isogeny-based schemes rely on the Deuring correspondance and thus require computations with quaternion ideals. In this paper, we generalize the recent results of Leroux on the inert representation of quaternion ideals, yielding a normalized representation together with a set of simple and efficient algorithms for quaternion ideals in the context of the Deuring correspondence when the prime characteristic $p$ is equal to $3 \bmod 4$. One of the main benefit of our new algorithms is that the size of the integers involved in the computations is both easy to bound, and smaller than previous work. In particular, when applied to the latest version of SQIsign, our algorithms yield a concrete integer bound of $O(p^4)$ in the worst case, proven under an experimentally verified assumption on the size of the integers required to perform the lattice reduction part of the response sampling. This bound improves upon all known previous bound by a factor at least $O(p^2)$. Our new algorithms are used in the latest update of SQIsign's implementation submitted to the third round of the NIST call for additional post-quantum signatures. In particular, their low integer bounds facilitated the removal of a dependency on the GMP library in favor of a custom library of fixed-size integers without performance overhead. We stress that our algorithms are not limited to SQIsign, but apply to any isogeny-based cryptographic protocol that relies on the Deuring correspondence such as the PRISM signature scheme for instance.

The Institute of Commercial Cryptography Standards (ICCS) launched the Next-generation Commercial Cryptographic Algorithms Program (NGCC) and invited worldwide comments on draft submission requirements and evaluation criteria for cryptographic hash algorithms. Our analysis of seven submitted hash functions gives the following results: - Message differences that cancel in every key injection give explicit collisions for all four fixed-output variants of \textbf{MoFang} and both XOF variants at every finite output length. - Two distinct states of \textbf{Neulaser} become equal after one update, giving collisions for all three variants with the initialization used by the v2 reference and optimized implementations. - An invariant subspace of \textbf{CHIME-512} permits collision search using at most \(2^{64}\) hash evaluations when shifts act separately on 64-bit words, as in both submitted implementations. - \textbf{CHAMP}'s determinant constraint gives collision searches using at most \(2^{192}\) and \(2^{384}\) hash evaluations for its 512- and 1024-bit variants, respectively. - We exhibit explicit free-start collisions for all three \textbf{QSH} variants. In the semi-free-start setting, both messages and every tree node share one chosen complete reset. We prove upper bounds of \(2^{64},2^{128},2^{128}\) compression evaluations for finding collisions with 512-, 768-, and 1024-bit digests, respectively, plus constant preparation and finalization costs. - In both versions of \textbf{WChain}, the message expansion preserves invariant sets and admits sequences of expanded blocks with periods one, three, and six over all prescribed steps. - On a set of 256 message blocks, \textbf{Cuishen}'s message expansion acts as a cyclic shift of eight binary coordinates throughout all 64 rounds. With the same initial chaining register and counter, these blocks give XOR differences between round keys with periods dividing eight. The stated evaluation budgets for \textbf{CHIME-512} and \textbf{CHAMP} give success probabilities greater than \(0.39\).

Middle-Product LWE (MP-LWE) can inherit hardness from Ring-LWE over many number fields. Peikert and Pepin developed a direct reduction using field traces. Njah Nchiwo and Pellet-Mary (NP26) proved polynomial loss for the route through Polynomial-LWE under an additional condition on the defining polynomial. Recently, Pellet-Mary and Xia (PX26) unified both routes and proved polynomial loss for defining polynomials with polynomially bounded coefficients under suitable modulus conditions. We analyze Peikert and Pepin's trace reduction for monic irreducible integer polynomials $f$ of degree $n\ge2$ with coefficients of absolute value at most a fixed $B\ge1$. First, when the prime modulus satisfies $q\nmid[\mathcal O_{\mathbb{Q}(\theta)}:\mathbb{Z}[\theta]]$, where $\theta$ is a root of $f$, we prove the existence of multipliers with primal loss $O_B(n\sqrt{\log n/\log\log n})$ and dual loss $O_B(n^2)$. The multipliers have polynomial-size descriptions and serve as advice. Second, whenever the polynomial class is nonempty, every $Q\ge21$ admits a prime $q\in[Q,2Q]$ for which the index condition holds for at least a $1-O_B(n\log n/Q)$ fraction of the polynomials. At the same prime, we prove the same lower bound when counting the distinct number fields defined by these polynomials. Both coverage bounds tend to one as $n\to\infty$ if $Q/(n\log n)\to\infty$. Third, we prove that the trace reduction can match the linear noise bounds achieved by NP26's reduction through Polynomial-LWE. For the same defining polynomial, Ring-LWE variant, and MP-LWE parameters, a suitable trace multiplier exists whose linear noise amplification is no larger than that achieved by NP26's multipliers.

Recent works have studied Byzantine agreement (BA) in the mixed-fault model with resilience threshold $n>2t+r+s$, where $n$ is the number of parties, $t$ is the number of Byzantine parties, $r$ is the number of receive-faulty parties, and $s$ is the number of send-faulty parties. In particular, Feng et al.~(ASIACRYPT~2025) proposed a BA protocol with optimal resilience, expected asymptotically quadratic communication complexity, and expected constant round complexity. However, existing BA protocols guarantee a meaningful output $v$ only when all parties hold the same input $v$. Such a guarantee is insufficient for efficient construction of atomic broadcast protocols, leaving efficient atomic broadcast in the mixed-fault setting as an open problem. In this paper, we present the first atomic broadcast protocol (UABC) with optimal resilience in the mixed-fault model. In addition, our protocol achieves communication complexity $\mathcal{O}(n\ell+n^2\lambda^2)$ when $t=\Theta(n)$, where $\ell$ is the input size and $\lambda$ is the security parameter. This complexity is asymptotically optimal for moderately large $\ell$, namely when $\ell\ge n\lambda^2$. At the core of our design is an undead verifiable information dispersal (UVID) protocol, which allows an input to be efficiently dispersed and later reconstructed in the mixed-fault setting. Leveraging UVID together with the undead multi-valued consensus (ASIACRYPT~2025), we further construct a new primitive called weak undead multi-valued validated Byzantine agreement (wUMVBA) and its optimized variant (Opt-wUMVBA). Unlike standard multi-valued validated Byzantine agreement, wUMVBA and Opt-wUMVBA guarantee that the output is either a meaningful value satisfying the validity predicate or $\bot$. Moreover, the probability of outputting $\bot$ is at most $(t+s)/n$. Finally, by leveraging Opt-wUMVBA, we obtain our optimal atomic broadcast protocol for the mixed-fault setting.

The rapid expansion of quantum computing threatens the security foundations of classical public-key cryptography, including RSA and ECC, both vulnerable to Shor's algorithm. For the automotive industry, where secure communication underpins critical functions such as over-the-air (OTA) updates, secure boot, firmware signing, PKI validation, and vehicle-to-everything (V2X) connectivity, this threat demands early and informed migration planning. This paper presents a cross-platform performance evaluation of NIST-selected and candidate Post-Quantum Cryptography (PQC) algorithms integrated into the Transport Layer Security (TLS) protocol, in both standalone and hybrid (classical + PQC) configurations. Signature schemes CROSS, MAYO, SPHINCS+ (SHA and SHAKE variants), ML-DSA, and FALCON are evaluated alongside key encapsulation mechanisms including FrodoKEM, BIKE, and ML-KEM. Testing spans two representative platforms: a resource-constrained Raspberry Pi 4B (Broadcom BCM2711, 4GB RAM) representing embedded automotive ECUs, and an Ubuntu-based Intel Core i5 system representing backend or gateway infrastructure. Execution time, memory consumption, and CPU core utilization are measured across algorithm-KEM combinations to characterize real-world feasibility. Results indicate lattice-based schemes offer a strong balance of performance, interoperability, and long-term assurance suited to V2X and PKI-heavy communication, while compact signature schemes such as MAYO and FALCON better serve resource-constrained operations like secure boot and firmware signing, where verification speed and low memory footprint are prioritized over frequent key exchange. The study further identifies a critical dependency of PQC feasibility on 64-bit architecture, highlighting the limitations of legacy 32-bit automotive chipsets that lack dedicated cryptographic accelerators. These findings offer practical, use-case-specific guidance for automotive OEMs and suppliers navigating the transition from classical to quantum-resistant cryptography, supporting risk-informed decisions across onboard and offboard vehicle communication architectures.

We construct the first non-trivial weighted threshold encryption scheme with silent setup. The CRS and each public key consists of O(W) group elements, where W is the maximum committee weight. Both the weight assignments and the threshold for decryption can be dynamically chosen at encryption time. Each partial decryption is a single G1 element computed non-interactively with one scalar multiplication, independent of the party's weight. The CPA ciphertext is two G_1 elements, improving upon the shortest known unweighted scheme, and CCA security costs two additional field elements. We prove security in the generic bilinear group model.

Polynomial commitment schemes (PCSs) allow a prover to commit to a polynomial and later prove its evaluations succinctly. Among hash-based constructions, FRI (Ben-Sasson et al., ICALP 2018) and its follow-up works achieve polylogarithmic proofs by recursively ``folding'' Reed-Solomon (RS) codes. However, their concrete evaluation costs remain relatively high, as the first few folding rounds operate on the largest codewords and dominate the prover work. We present \emph{ReedWeave}, a Reed-Solomon PCS that successfully incorporates interleaving with folding, achieving the best of the two worlds. ReedWeave decomposes a degree-$d$ polynomial into $m$ smaller components and commits to their RS encodings over a common domain. Under our novel decomposition, a random linear combination of these codewords is exactly an $m$-ary folding. At a high level, ReedWeave starts with an $m$-ary folding, followed by standard binary folding as in FRI. The prover costs are substantially reduced in the sense that at the very beginning it suffices to do interleaved-RS encoding rather than standard RS encoding. That is, we reduce prover costs from $\mathcal{O}(d \log d)$ to $\mathcal{O}(d\log(d/m))$ for constant code rate while maintaining efficient polylogarithmic verification. Moreover, our approach essentially works for arbitrary $m$, relaxing the smoothness requirements of the underlying fields by a multiplicative factor of $m$. We benchmark our Rust implementation over Goldilocks using 32 threads and targeting 100-bit security. At $d=2^{24}$, $\rho=1/4$, and $m=64$, the DEEP variant commits in $475.0$ ms, opens in $111.6$ ms, verifies in $2.07$ ms, and produces a $594.7$ KiB proof. Compared with FRI (ICALP 2018), commitment, opening, and verification are $6.9\times$, $51.5\times$, and $4.2\times$ faster, respectively. Against STIR (CRYPTO 2024), the corresponding speedups are $2.9\times$, $68.5\times$, and $2.1\times$. Its proof is only $0.69\times$ the size of FRI's and $2.31\times$ that of STIR's.

Range proofs are a fundamental building block of lattice-based proof systems. Existing approaches relying on standard Johnson-Lindenstrauss (JL) struggle to provide succinctness: unstructured JL incurs linear verifier complexity, while structured JL introduced in RoK and Roll [ASIACRYPT'25] produce large projection vectors that need to be sent in costly committed form. For a witness of dimension $m$ and a security parameter $\lambda$, the JL projection vector is $O(\lambda),$ but the projection matrix is $O(\lambda m)$. Structured JL can be represented in $\widetilde O(\rho \lambda^2)$, but the resulting projection length grows to $\widetilde O(m / \rho)$ for any trade-off parameter $\rho > 1$. \hspace{5mm} In this paper, we introduce Tensor Train Random Projection (TTRP) to lattice-based cryptography, offering a ``best of both world" structured JL variant. The Tensor Train (TT) matrix representation drops to $\widetilde O(\lambda)$, while maintaining the projection vector at $O(\lambda)$. \hspace{5mm} We show that TTRP can be seamlessly integrated into proof systems by linearizing the well-formedness of the projection with the sum-check protocol. Concretely, using TTRP + sum-check as a drop-in replacement for existing range proof techniques yields an approximate shortness check with $O(\lambda \log m (\log\log m)^2)$ verifier complexity and proof size around $4$ KB for relevant parameter settings.

Fully anonymous secret-sharing schemes ensure two properties at once: for any fixed secret, the combined shares of every unauthorized set of participants are uniformly random, and every authorized set can reconstruct the secret exactly using only the share values, without needing to know which participant holds which share or in what order the shares appear. It was previously open whether such schemes exist for nontrivial exact-threshold parameters 2 < t < n. For the smallest previously open threshold, t= 3, we give, for every n≥4, an explicit fully anonymous scheme for one-bit secrets, with 2⌈log n⌉-bit shares and a perfect reconstruction algorithm running in poly(log n) time. The next result, found by ChatGPT, shows that for every 1 ≤t ≤n there exists a fully anonymous perfect (t,n) threshold secret-sharing scheme for one-bit secrets, in which each share has length O(tlog n) bits. The proof is purely existential and does not provide an efficient construction. Moreover, ChatGPT identified a simple construction of a fully anonymous perfect scheme for every access structure A; if A contains ℓ authorized sets, then each share consists of ℓ2 bits. The authors subsequently verified and streamlined the proofs on their own and take full responsibility for their correctness.

We study affine and linear equivalence of functions $F,G:\mathbb{F}_q^n\to\mathbb{F}_q^m$. We present practical equivalence algorithms that handle arbitrary functions (any algebraic degree, permutations and non-permutations) and are particularly effective on structured instances with nontrivial self-equivalences, covering most cryptographically relevant cases. We also give a dedicated algorithm for computing generators for the group of self-equivalences $(A_1,A_2)$ satisfying $A_2\circ F = F\circ A_1$, for which no comparably efficient general method was previously available.

We formalize and construct $sparse$ arguments of knowledge, where given a length $N$ witness that contains $n$ non-zero values the prover time is $O(n) \circ o(N)$. In particular, we achieve a sparse argument of knowledge for the customizable constraint system relation, which generalizes circuit-satisfiability. We achieve this by first utilizing $sublinear$ lookup arguments to provably select only the subset of the constraint system that touches the non-zero entries of the variable assignment, and then running a standard argument of knowledge with mild qualifications. Our resulting sparse argument of knowledge is publicly verifiable and supports a universal and updatable setup. It features an $O(N \log N)$ preprocessing phase, an $O(n \log n)$ prover time, and an $O(1)$ verifier time, improving on the prior $O(n \log^2 n)$ and $O(n \log N)$ prover time.

We propose an efficient threshold mechanism that is well suited for certain hash-based signatures. Our proposal has a number of compelling features: • The final signature assembled from a quorum of signature shares has the same format as a non-threshold hash-based signature. In particular, the verifier is unaware that the signer is thresholdized. Moreover, we can add and remove parties and change the threshold without changing the public key. • Our framework can be used to thresholdize one-time signature schemes, such as Winternitz, and a few-time schemes, such as XMSS, HORS, FORS, and PORS+FP. • The public key and the signatures reveal nothing about the number of parties $n$ or the threshold $t$. • An instantiation of our framework scales well to a large number of parties $n$ and a large threshold $t$. One limitation of the framework is that it does not support an efficient distributed key generation protocol (DKG). Another limitation is that the framework does not directly apply to SLH-DSA. It is primarily designed for the Winternitz, XMSS, and FORS schemes.

We introduce BitZ, a hash-based Polynomial Commitment Scheme (PCS) for committing to multilinear polynomials $\mathbf{f}$ with coefficients in an arbitrary finitely generated ring $S$, e.g.\ a finite field $\mathbb{F}$, the integers $\mathbb{Z}$, a cyclotomic ring, etc. Moreover, given another arbitrary ring $R$ and a ring homomorphism $\psi:S\to R$, BitZ then proves evaluation claims over $R$ for the polynomial $\psi(\mathbf{f})$. BitZ's costs depend almost exclusively on the number of bits in the coefficients of $\mathbf{f}$, and not on $S$, $R$ or $\psi$. Moreover, BitZ provides range checks (or more generally, bit-size checks) essentially for free. BitZ can thus be used as a PCS in essentially any proof system. We do so to build a SNARK, called BitZ-SNARK, for integer polynomial constraints, following the fingerprinting technique of Campanelli and Hall-Andersen, where one commits over $\mathbb{Z}$ and proves the constraints over a random prime field $\mathbb{F}_q$, i.e. BitZ is deployed with $S=\mathbb{Z}$, $R=\mathbb{F}_q$, and $\psi$ reduction modulo $q$. BitZ applies equally to other ring-based proof systems, or field-based ones. To commit to $\mathbf{f}$, BitZ first decomposes $\mathbf{f}$ into a string of bits, and then commits to it over a binary field $\mathbb{F}_{2^{\nu}}$, in packed form. The scheme then proves the linear claim on $\psi(\mathbf{f})$ over the arbitrary ring $R$, even though it committed to the bits forming $\mathbf{f}$ over a binary field. We implement BitZ-SNARK and use it to prove, among others, SHA-256 hashing followed by ECDSA signature verification; RSA modular exponentiation and Poseidon hashing; integer multiplication; and SHA-256 hashing followed by multiplication modulo $2^{32}$, consistently obtaining better performance than prior approaches on most tasks. As an example, we achieve a throughput of $9$ million proved 32-bit integer multiplications per second on a MacBook Air M5 24 GB (10 threads, CPU-only) with proof sizes under $200$ kB. We prove a SHA-256 hash of a $2$ kB ($2^5$ compressions) message followed by a P-256 ECDSA signature verification with $32$ ms and $3.1$ ms prover and verifier time, respectively, and with a proof of $65$ kB, single-threaded. With $10$ threads the times are $17$ ms and $3.7$ ms.

Adaptive reprogramming is a central tool for proving security in the quantum random oracle model (QROM). Recently, it has been extended to the setting when an oracle-dependent advice is in presence. However, the existing result is restricted to classical advice, and addresses only a single reprogramming. Extending it to n reprogrammings through naive hybridization yields a loss that is linear in the number of reprogrammings. In this paper, we establish an adaptive reprogramming theorem that accommodates quantum advice, and has a tighter overall security loss that only scales in the cubic-root of n, with an attack that matches the number of queries required in order to reach constant advantage. Using our reprogramming theorem, we provide improved time-space tradeoff bounds for PRG security of random oracles, and an IND-CPA security proof of salted pseudo one-time pad, in the quantum advice setting. Along the way, we also identify and prove a folklore lemma about indistinguishability of two oracles, which may be of independent interest. As another application, we provide a generic security analysis of Fiat-Shamir and hash-and-sign signature schemes, in QROM with quantum advice. We do so via a two-step modular analysis, where in the first step we perform a generic UF-CMA to UF-NMA reduction using our reprogramming theorem, and in the second step we provide a characterization of when such a scheme satisfies UF-NMA security, which we then use to discuss security of several signature schemes in this model.

The NIST SP 800-208 eXtended Merkle Signature Scheme (XMSS) profile XMSS-SHAKE256_10_256 repeatedly invokes SHAKE256 primitives, making field-programmable gate array (FPGA) accelerator latency sensitive to Keccak permutation time and absorb/finalization-control overhead. Established round unrolling reduces permutation-side latency but leaves residual controller work. We propose SAFE Final-Block Construction (SAFE FBC), combining guarded SHAKE256-rate-aware eligibility, direct eligible final-block construction, and sequential-finalization bypass without modifying Keccak. A controlled 12-configuration study crosses four controller/finalization organizations with one-, two-, and three-round-per-cycle datapaths over nine XMSS-oriented cases: 96-byte F and pseudorandom-function (PRF) inputs, 128-byte H and PRFkeygen inputs, and selected message-hash cases around the SHAKE256 rate boundary. At every fixed depth, SAFE FBC reduces aggregate L2-final latency by 13 cycles versus the Structural Controller Decoupling (SCD) baseline; L2-final spans the first accepted AXI input beat to the final accepted AXI output beat. At three rounds per cycle, aggregate latency falls from 305 to 292 cycles, with no case regressing. F and ordinary PRF show the largest per-call gain, from 30 to 25 cycles (16.67%). Component measurements localize the saving to absorb/finalization control; Keccak permutation latency, squeeze latency, and input-transfer span remain unchanged. SAFE FBC complements unrolling, trading latency for substantial lookup-table/slice growth with very small flip-flop overhead.

Robust asynchronous threshold Schnorr signatures enable honest parties to complete signing despite malicious behavior and network delays. To reduce online latency, these schemes typically follow an offline–online paradigm. The parties prepare batches of shared nonces in the offline phase and consume them to generate signatures online. In high-throughput constructions such as SPRINT (Benhamouda et al.~Eurocrypt 2024), super-invertible matrices are used to extract multiple nonces and their corresponding commitments from a single execution of the nonce-generation protocol. However, the associated group operations incur substantial computational overhead. We identify several computational bottlenecks in SPRINT and present $\mathsf{DASH}$, a suite of robust asynchronous threshold Schnorr signature protocols that substantially improve computational efficiency while retaining SPRINT’s amortized linear communication cost. Our contributions are threefold. First, we propose distributing the group computations involved in nonce extraction among the parties. This reduces the amortized computational cost from $\mathcal{O}(\log n)$ to $\mathcal{O}(1)$ group operations per signature per party. To enable this distributed computation, we employ a batching technique that allows each dealer to distribute $L$ nonce polynomials simultaneously. Second, we introduce an efficient batched share-verification procedure that jointly checks shares of all $L$ polynomials. For concrete parameters, this can accelerate share verification by a factor of $40-60$. We also introduce a simple agreement protocol via player elimination, which could be of independent interest. Finally, under a stronger honest-majority assumption, we develop a packed two-stage online reconstruction protocol that enables parties to reconstruct signatures through error correction. This eliminates the need for signature-share verification, and consequently, avoids the expensive group operations performed by the aggregator in SPRINT. Surprisingly, even in the worst case, our $\mathsf{DASH}$ protocols preserve the same asymptotic amortized computation and communication costs, provided that $L \gg n\log n$. %We prove the security of all $\mathsf{DASH}$ variants in the random oracle model under the standard discrete logarithm assumption.

Key generation in ML-KEM (CRYSTALS-Kyber) samples a short secret from a centered binomial distribution (CBD) and immediately transforms it with the number-theoretic transform (NTT). Each execution draws fresh randomness, so an attacker obtains a single trace and cannot average. We show that one power trace of the optimized pqm4 implementation on an Arm Cortex-M4 suffices, and that the two operations leak complementary information. The CBD sampler stores each coefficient as a signed $16$-bit two's-complement word, which reveals its sign almost without error but too little about its magnitude to yield long error-free hint sets. The missing magnitude leaks in the subsequent NTT, where coefficients are multiplied by public twiddle factors. Used as hints in a primal lattice attack, the combined leakage reduces the estimated BKZ block size for ML-KEM-768 from $624$ to $129$, corresponding to $2^{182.2}$ and $2^{37.7}$ in the core-SVP model. A control experiment shows that the same NTT code leaks the Hamming weight of a near-uniform operand as strongly as that of the secret, yet reveals almost nothing about its value. What makes a coefficient vulnerable is how few values it can take, not how small it is. That points to a countermeasure inside the CBD sampler. Each sample $v$ is stored as a random representative $\widetilde v = v + rq$ of its residue class, with $r$ nonzero, so the NTT and all later code run unchanged. This $q$-randomization drives the sign leakage to the noise floor, reduces the NTT magnitude leakage by $4.5\times$, and raises the block size from $129$ back to $611$, about four bits of estimated security lost instead of more than $140$. The sampler grows by $937$ bytes of firmware.

The Learning With Errors (LWE) problem provides a conservative and well-established security foundation for lattice-based cryptography, while Learning With Rounding (LWR) improves bandwidth efficiency through deterministic rounding. However, the rounding noise in LWR is inherently correlated with the hidden linear term, preventing tight and sample-preserving reductions to standard LWE for polynomial moduli. Prior work on the Learning With Quantization (LWQ) problem established a tight security reduction from LWE, where standard additive noise is intrinsically replaced by quantization error. We specialize this framework by explicitly instantiating the quantization lattice as a scaled integer lattice. Under this geometric choice, specifically utilizing aligned power-of-two moduli, we derive the exact finite-support error distribution and construct an explicit bijection between transmitted split samples and normal-form LWE samples. These ingredients yield \(\mathsf{MAMBA\text{-}Frost}\), a plain LWQ-based key encapsulation mechanism that seamlessly pairs unstructured LWE security with quantization-based compression. Because its effective error stems entirely from public dithered quantization, \(\mathsf{MAMBA\text{-}Frost}\) operates strictly with hardware-friendly power-of-two arithmetic. Furthermore, the construction employs an \(E_8\)-coded message embedding to optimize the correctness margin without altering the underlying LWQ hardness argument. We instantiate \(\mathsf{Frost}\) at NIST security levels 1, 3, and 5 and provide a complete software implementation. Its power-of-two design realizes the core arithmetic with shifts and masks, keeping the implementation simple and amenable to constant-time engineering. At level 1, \(\mathsf{Frost\text{-}128}\) reduces the combined public-key and ciphertext size by about \(40\%\) compared with \(\mathsf{FrodoKEM\text{-}640}\) and by about \(8\%\) compared with \(\mathsf{SCloud}^{+}\text{-}128\). On an AVX2 platform, \(\mathsf{Frost\text{-}128}\) achieves speedups of \(2.3\times\), \(1.8\times\), and \(1.5\times\) for key generation, encapsulation, and decapsulation over \(\mathsf{FrodoKEM\text{-}640}\), and \(2.1\times\), \(1.5\times\), and \(1.3\times\) over \(\mathsf{SCloud}^{+}\text{-}128\).

We give a sharper bound on the error introduced by replacing a random permutation oracle with Carolan’s compressed permutation oracle. Building on Rosmanis’s representation-theoretic approach, we represent exact permutation states in the compressed oracle’s database space, allowing a direct comparison of the two query operations. For a uniform permutation on N points, this comparison bounds the soundness error by 4q/√N after q ≤ N/4 queries. As the main application, we obtain tight query complexity for constant success probability in sponge preimage and collision search by substituting this bound into Carolan’s search reductions. The same analysis improves bounds for the one-more problem and cycle finding, and gives tight query complexity for constant success probability in keyless Davies–Meyer collision search

We give a lattice identity-based signature scheme from annular NTRU trapdoors and Fiat--Shamir with aborts (FSwA). Countered hashing maps each identity to its first invertible DLP/NTRU syndrome $a$. Extraction returns a short witness to $s_0+s_1h=a\bmod q$, and signing normalizes this relation to a fixed-target two-response equation with public commitment recovery. Gärtner's iterative rejection method fits naturally into this signing layer: processing the challenge monomials separately reduces the Gaussian mask width and expected signing attempts, yielding shorter signatures. We report three parameter sets whose signing layer is calibrated against NIST security categories 2, 3, and 5, with fixed signature sizes of $8486$, $11309$, and $12727$ bytes, respectively.

Folding is a core technique in building efficient code-based polynomial commitment schemes with polylogarithmic proof size and verification. To date, there are two families of linear error-correcting codes that have been known to allow folding, i.e., Reed-Solomon (RS) codes and foldable codes. However, neither admits optimal proximity gaps, which constitutes a fundamental bottleneck in the resulting proof sizes. In this work, we give the first folding scheme that enjoys optimal proximity gaps. Specifically, we construct IOPPs (interactive oracle proofs of proximity) for both folded RS (FRS) codes and univariate multiplicity (UM) codes, which achieve optimal proximity gaps $1-R-\varepsilon$ as shown in a recent work of Goyal and Guruswami (STOC 2026), where $R$ is the code rate and $0<\varepsilon<1-R$. Our key observation is that the typical even/odd folding commutes with polynomial reduction for suitably paired moduli, enabling consistency checks via the Chinese remainder theorem. This implies a new generic folding framework that recovers the FRI folding for RS codes and enables efficient folding for FRS and UM codes. We further refine the optimal proximity gap analysis for FRS and UM codes, yielding tighter concrete soundness bounds. Our IOPPs have $O(N)$ prover time and oracle proof size, together with $O(\lambda\log{N})$ query complexity and verification time, where $N$ is the block length and $\lambda$ is the security parameter. These bounds match the asymptotic complexity of FRI while attaining optimal proximity gaps and allowing smaller underlying fields at the same security level. E.g., a $128$-bit field suffices for $100$-bit security.

Multiparty Private Set Union (MPSU) allows multiple parties to compute the union of their private sets while revealing no additional information beyond the prescribed output. Existing practical MPSU protocols typically manipulate individual elements and rely on a distributed shuffle to hide element ownership, introducing an $O(n)$ round-complexity bottleneck. We present United, a shuffle-free MPSU framework based on a new data-structure abstraction, Oblivious Insert-Only Invertible Sketches (OIIS). Rather than anonymizing an element-wise intermediate representation, the parties directly construct a protected symmetric sketch of the union. Conditional oblivious insertion ensures that each distinct union element is inserted exactly once while hiding the insertion condition and modified locations. We provide two realizations of OIIS. Our HE-based construction instantiates OIIS with a standard Invertible Bloom Lookup Table protected by multi-key partially homomorphic encryption, while our MPC-based construction uses additive secret sharing and introduces a new row-local power-sum OIIS technique for efficient conditional insertion. We implement and evaluate both constructions. Across the evaluated configurations, our MPC-based construction achieves up to $3.10\times$ lower runtime in LAN settings, while our HE-based construction achieves up to $2.73\times$ lower runtime in WAN settings compared with prior MPSU protocols.

The security of RSA is generally understood to be based on the complexity of factoring, and key size parameters are extrapolated from the general number field sieve (GNFS). However, this may not accurately represent RSA security in practical scenarios. An under-appreciated 2007 algorithm of Joux, Naccache, and Thomé allows an attacker to forge RSA signatures after temporary access to a raw RSA signing/decryption oracle in time close to the *special* number field sieve (SNFS) without factoring the key. We implement and run this algorithm for 1024-bit RSA. In total, the attack took 1380 CPU core-years over five calendar months, and made $2^{32}$ oracle queries. Most of this time is precomputation; after the precomputation the attacker can forge any signature of choice, offline, in 180 core-years. We carried out our attack using a hardware security module (HSM) as the signing oracle, thus demonstrating the ability to impersonate the HSM through black-box API interactions, without exfiltrating the key. Blind RSA schemes also provide such a signing oracle. Extrapolating our empirical running times to larger key sizes, we conclude that the concrete security of RSA with a signing oracle should be 15 to 30 bits lower than the factoring-based security estimates for the 1024-bit to 4096-bit RSA parameters that are common in practice. Even 4096-bit RSA does not appear to meet a 128-bit security level in this attack model. This highlights a gap in current RSA-type security assumptions, and gives classical cryptanalytic evidence in favor of moving away from RSA entirely during the current post-quantum transition.

Covert communication can be achieved without anamorphic encryption.

We analyze a recently published construction of redactable blockchains based on multivariate polynomial equations. We show that its public integrity conditions reveal sufficient algebraic structure to recover the relevant private evaluation points efficiently. As a consequence, the blockchain unauthorized redaction problem reduces to univariate root finding over a finite field followed by solving a linear system. We also discuss an alternative attack based on linearization.

Modern cryptocurrency wallets use Schnorr signatures together with public, deterministic key derivation: by repeatedly rerandomizing a single master public key, an unlimited number of public keys for incoming payments can be derived without access to secret data. Moreover, some wallets support multi-signature schemes such as MuSig2 for optionally aggregating derived public keys from $n$ distinct parties into "$n$-of-$n$" public keys, so that funds received on such aggregated keys can be spent only when authorized by all $n$ parties. However, these advanced key-management techniques stretch the underlying cryptographic schemes beyond the guarantees provided by existing security proofs. Although deterministic Schnorr wallets and MuSig2 have each been proven secure in isolation, the provable security of their composition---despite its deployment in wallets---has not been established thus far. The goal of this work is to narrow this gap between theory and practice. We provide the first formal security analysis of the joint use of single-signer Schnorr signatures and MuSig2, both under rerandomization and in deterministic wallets. First, we introduce the notion of a (rerandomizable) joint-signature scheme, in which an honest signer uses the same secret key for single-signer signatures and multi-signatures. Within this model, we prove tight security of Schnorr signatures plus MuSig2 under the algebraic one-more discrete logarithm (AOMDL) assumption in the combination of the algebraic group model (AGM) and the random oracle model (ROM). Finally, we provide a formal model of deterministic wallets with joint-signature schemes and show that Schnorr plus MuSig2 remains secure under public, deterministic key derivation.

We present the first polynomial-time attacks against certain parameter choices of the low-dimensional vector representation (LDVR) problem, introduced by Crites, Katz, Komlo, Tessaro, and Zhu (CRYPTO '25) to prove the adaptive security of FROST in the Algebraic Group Model. Building on work by Crites and Stewart (CRYPTO '25), they also show that every attack against LDVR directly yields an adaptive attack—i.e., one leveraging adaptive corruptions—against any threshold Schnorr signature that exposes to the attacker the values $g^{\mathrm{sk}_i}$ for the secret-key shares $\mathrm{sk}_i$ held by the signers, where $g$ is a generator of the underlying group. This class of protocols includes FROST (Komlo and Goldberg, SAC '20), Sparkle (Crites, Komlo, and Maller, CRYPTO '23), Lindell's three-round protocol (CiC '24), along with other masking-free protocols. Consequently, our results give the first polynomial-time adaptive attacks against a class of practical threshold signatures. Our attacks require a large, but still polynomial, number of signers: asymptotically, we require $n = \Theta(\log^2 p)$ signers and corrupt $t_c = \Theta(\log p)$ of them. For the prime-order subgroup of Curve25519, concrete and optimized instantiations of our attack require $n=5020$ signers and corrupt $204$ of them. This exceeds the signer counts commonly encountered in practice, but falls within the scenarios considered by NIST's call for threshold signatures. At the theoretical level, our results also yield a non-artificial separation between static and adaptive security based on a real-world multi-party protocol. Our results arise from a new reduction from LDVR to structured subset-sum problems determined by the evaluation points of the polynomial used to secret-share the signing key. We further show that allowing these evaluation points to be chosen adversarially can lead to substantially more efficient attacks.

Over the last fifteen years, side-channel analysis (SCA) against implementations of both classical and post quantum cryptography has undergone a quiet but fundamental change of paradigm: from treating leakage as evidence to be combined with an algorithm’s structure into a system of exact equations to be solved, to treating it as evidence to be combined into a joint probability distribution to be queried. This survey gives a systematic account of that evolution through four paradigms: Algebraic SCA (ASCA), which encodes leakage as hard Boolean or algebraic constraints and solves the resulting system with SAT or Gröbner-basis solvers; Tolerant/weighted Algebraic SCA (TASCA), which relaxes hard constraints into pseudo-Boolean costs and recovers a maximum-a-posteriori key via combinatorial optimization; Soft Analytical SCA (SASCA), which retains leakage as full likelihood functions attached to a factor graph and approximates the posterior with loopy belief propagation; and Exact SASCA (ExSASCA), which replaces the uncertified approximation of loopy belief propagation with exact inference on a knowledge-compiled tractable probabilistic circuit. Our central contribution is a single Bayesian factor-graph formulation under which all four paradigms are shown to be different representations of the same leakage-augmented joint distribution combined with different inference queries and solvers: we prove, in a precise but lightweight sense, that ASCA is the zero-temperature limit of TASCA, that TASCA is a maximum-a-posteriori restriction of SASCA’s model, and that ExSASCA is SASCA with its approximate solver replaced by an exact one on the identical graphical model. Building on this formulation, we develop a taxonomy that organizes the literature along a representation axis (hard, weighted, probabilistic) and a solver axis (satisfiability, combinatorial optimization, approximate message passing, exact tractable inference), survey the concrete attack literature in each paradigm on both AES and NTT-based post-quantum schemes (Kyber, Dilithium, Falcon/FN-DSA), and analyze the computational and security trade-offs of each approach, including its implications for what a security evaluator may soundly conclude from a failed attack. We close with open problems at the current frontier of tractable probabilistic inference for cryptographic implementation security.

Falcon offers compact signatures and well-studied mathematical security, but its side-channel security remains a critical challenge. In particular, its floating-point Gaussian sampler constitutes a major source of side-channel leakage, while protecting it efficiently is difficult because of its reliance on floating-point arithmetic. However, existing attacks targeting the sampler under realistic noisy-leakage conditions typically require thousands of traces and are evaluated on unoptimized implementations. In this paper, we present a new attack on Falcon's sampler, which reduces the number of required traces by more than two orders of magnitude compared with prior attacks under realistic noisy-leakage conditions and works on both unoptimized (\texttt{-O0}) and highly optimized (\texttt{-O3}) builds. Our attack targets the floating-point Gaussian centers $\mu$ used by the sampler at the recursion leaves of the \texttt{ffSampling} procedure. Specifically, it exploits signed-exponent leakage arising when $\lfloor\mu\rfloor$ is converted from an integer back to floating-point representation, as well as the weaker sign-only leakage. Signed-exponent leakage places the integer part $\lfloor\mu\rfloor$ of each center in one of $17$ signed power-of-two intervals, whereas sign-only leakage divides it into two intervals according to its sign. We propose CB-MLE, which uses gradient descent to obtain an estimate $f^\star$ whose computed Gaussian-center classifications are consistent with the observed classifications under the profiled confusion matrix. An ISD-style search tests subsets of the more reliable coefficients in $f^\star$ with LLL/BKZ on the corresponding reduced NTRU lattices to recover the full key. We collect power traces from the Falcon implementation in the PQClean library running on an ARM Cortex-M4 microprocessor. Our Gaussian-center classifier achieves single-trace classification accuracies of $0.9997$ and $0.884$ at the \texttt{-O0} and \texttt{-O3} optimization levels, respectively, confirming exploitable signed-exponent leakage from the Gaussian centers. Using these classification results, the full attack recovers Falcon-$512$ keys with success rates of $100\%$ from $20$ signatures at \texttt{-O0} and $100\%$ from $56$ signatures at \texttt{-O3}. For Falcon-$1024$, it reaches $100\%$ from $21$ signatures at \texttt{-O0} and $100\%$ from $100$ signatures at \texttt{-O3}.

Let $C_0$ be the least constant such that, for every finite family of vectors $u_1,\ldots,u_n\in\mathbb C^d$ and independent finitely supported real random variables $\xi_i$, there are values $\varepsilon_i\in\operatorname{supp}(\xi_i)$ satisfying $\|\sum_{i=1}^n(\varepsilon_i-\mathbb{E}[\xi_i])u_i u_i^*\| \leq C_0\|\sum_{i=1}^n\mathrm{Var}[\xi_i](u_i u_i^*)^2\|^{1/2},$ where $\|\cdot\|$ denotes the operator norm. This rank-one matrix discrepancy formulation generalizes the signing formulation of the Kadison--Singer problem [KS59], resolved by Marcus, Spielman, and Srivastava [MSS15b]. Let $C_1$ be the least constant such that, for every $\epsilon>0$ and every finite family in $\mathbb C^d$, in every dimension $d$, satisfying $\sum_{i=1}^n u_i u_i^*=I$ and $\max_{i\in[n]}\|u_i\|^2\leq\epsilon$, there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i u_i u_i^*\|\leq C_1\sqrt\epsilon.$ Taking the $\xi_i$ to be independent symmetric signs gives $C_1\leq C_0$, since $\|\sum_{i=1}^n(u_i u_i^*)^2\|\leq\epsilon$ under these hypotheses. The general formulation allows arbitrary finite real supports and does not require $\sum_{i=1}^n u_i u_i^*=I$. Kyng, Luh, and Song [KLS20] proved $C_0\leq4$. We prove $2\leq C_1\leq C_0\leq2.176$. This improves the bounds $\sqrt2\leq C_0\leq3$ of Xie, Xu, and Zhu [XXZ21]. We conjecture that the optimal constant is $C_0=2$.

Traditional secure multiparty computation (MPC) protocols assume a fixed set of participants throughout the computation. Dynamic MPC (DMPC) relaxes this assumption by permitting parties to join or leave during the process. However, practical deployment of DMPC in Internet settings favors tolerating asynchrony and achieving guaranteed output delivery (GOD). Recently, AD-MPC [CCS 2025] introduced an asynchronous DMPC (ADMPC) achieving this goal, but its reliance on per-epoch preprocessing and masking randomness incurs substantial concrete overhead. In this paper, we present Continuum, a concretely efficient ADMPC protocol with GOD. We introduce an aggregated hand-off protocol that ensures transfer consistency across epochs while eliminating per-epoch masking randomness, and a batch multiplication protocol based on the BGW paradigm that defers degree reduction to the hand-off phase and aggregates verification for all multiplications into succinct proofs. Together, these protocols enable a non-interactive computation phase with interaction concentrated in an efficient hand-off phase, overcoming the primary concrete inefficiencies of prior ADMPC designs. We implement Continuum and evaluate its performance on up to 128 geographically distributed servers. In experiments on 22 servers with circuits of depth 6 and width 100, Continuum reduces linear-gate transfer latency from 76.60s to 15.13s (80% reduction) and multiplication-gate evaluation time from 476.62s to 35.67s (93% reduction), compared with AD-MPC, while preserving strong security guarantees.

Aggregate signatures play an important role in proof-of-stake systems, where many validators sign a block. There is a strong desire to aggregate all these signatures into one short signature that is fast to verify. Since all validators know the block number they are signing, this setting is well suited for synchronous (a.k.a stateful) signatures. Boneh and Kim (2019) showed that lattice-based one-time signatures (OTS) can be aggregated very efficiently. The Chipmunk and Lemur signature schemes extend this to an $\ell$-time synchronous scheme using a (homomorphic) Merkle tree of $\ell$ one-time public keys. Each leaf of the tree is used to sign one message, and these one-time signatures can be aggregated across many signers. Due to the Merkle tree, every aggregate signature includes a Merkle authentication path of length $O_\lambda(\log \ell)$. We present a different lattice-based approach to constructing a synchronous aggregate signature scheme. The length of an aggregate signature in our scheme is independent of $\ell$. The resulting signatures are asymptotically shorter than existing schemes, and concretely shorter for some parameter choices. The resulting signature verification algorithm is algebraic, which makes it amendable to efficient threshold signing. Moreover, we are able to prove security in an adaptive corruption model. We thus obtain an efficient lattice-based synchronous threshold signature scheme, where signatures from many signers can be aggregated into a single short signature. The scheme relies on a one time trusted setup to generate the public parameters.

Multi-Key Fully Homomorphic Encryption (MKFHE) is a variant of fully homomorphic encryption (FHE) that allows computations over data encrypted under different keys. Its support for non-interactive, dynamic participation and on-the-fly computation makes it an attractive primitive for multi-party applications. However, MKFHE has been largely overlooked in practice as its performance scales poorly, since the ciphertext size grows linearly with the number of participants in all existing constructions. Resolving this issue was a major open problem for almost a decade. In this work, we close this gap by providing the first construction of an MKFHE scheme with compact ciphertexts: the size of ciphertexts remains constant throughout the entire homomorphic evaluation, even when the number of participating parties changes during computation. As a result, our construction retains all the advantages of MKFHE while simultaneously offering fast evaluation performance similar to that of a single-key scheme. Our methodology is generic and applies to a broad class of RLWE-based FHE schemes. Concretely, we construct efficient multi-key variants of RGSW and FV-like schemes, and further develop a compiler that transforms a wide range of RLWE-based FHE schemes into their multi-key counterparts. We implement our multi-key FV scheme in Go. Empirical results show that our scheme achieves $30.6 \times$ faster multiplication and $60.6 \times$ faster automorphism for 16 parties compared to the state-of-the art construction by Kwak et al. (CCS '23), demonstrating the concrete efficiency of our construction.

Bootstrapping enables deep homomorphic computation in CKKS by replenishing multiplicative levels. It remains one of the scheme's most expensive operations. HEAAN reports a bootstrapping latency of 6.97ms, substantially faster than other publicly documented alternatives. However, the algorithmic and implementation techniques underlying this result have not been disclosed, leaving it unclear how such performance is achieved. In this work, we present a fully specified CKKS bootstrapping construction that achieves performance comparable to that reported by HEAAN. Building on SHIP (presented in Eurocrypt 2025), we introduce several algorithmic innovations that reduce communication and computational overhead while enabling efficient parallel execution. Our implementation bootstraps a single complex-valued ciphertext in 8.2ms and achieves an amortized latency of 4.6ms per ciphertext for a batch of 64. These results demonstrate practical sub-10ms CKKS bootstrapping.

Secure multiparty computation (MPC) enables mutually distrustful parties to compute on private digital inputs. We initiate the study of $\mathbf{spatiotemporal}$ $\mathbf{MPC}$, extending this paradigm to functionalities whose inputs additionally depend on physical facts such as the parties' locations, times, or trajectories. Such protocols must simultaneously hide spatiotemporal information and ensure its physical consistency: a malicious party should not be able to make the functionality operate on a spatiotemporal input inconsistent with its actual physical state. The main conceptual challenge is to formulate extraction of spatiotemporal information within the simulation-based security framework. We introduce $\mathbf{arguments}$ $\mathbf{of}$ $\mathbf{spatiotemporal}$ $\mathbf{knowledge}$, following the principle "I prove, therefore I am:" rather than defining physical presence directly through a mathematical relation, we define it operationally through the ability to complete a sound spatiotemporal verification protocol. Accordingly, an extractor recovers a spatiotemporal point from a successful prover and certifies its physical validity by using the extracted prover to succeed in an auxiliary spatiotemporal verification protocol. Building on this notion, we define universally composable (UC) security for spatiotemporal MPC, capturing privacy, physical consistency, and composability. We provide constructions achieving this new MPC notion. We first construct UC-secure commit-and-prove protocols for spatiotemporal knowledge: in the CRS model under LWE against quantum provers without pre-shared entanglement, and in the QROM against quantum provers with unbounded pre-shared entanglement. Using these protocols, we obtain general-purpose UC-secure spatiotemporal MPC from semi-honest post-quantum MPC. We also extend our framework to UC-secure spatiotemporal multiparty quantum computation over private quantum inputs and classical spatiotemporal information.

The Learning with Errors (LWE) problem is a cornerstone of post-quantum cryptography, and the dual attack is a central tool for evaluating its concrete hardness. In provable dual attacks, a major bottleneck is the large number of discrete Gaussian samples required over the dual lattice. While recent works have focused on accelerating the guessing step via modulus switching, the sampling bottleneck has remained largely unoptimized. In this paper, we address this issue from a new perspective. First, we observe that Banaszczyk's inequality can be significantly improved when the first minimum of the lattice is suitably large. This yields a refined distinguishing inequality, which provides sharper conditions for attack success. Second, we propose a new provable dual attack framework based on lattice projection. Instead of sampling over the entire dual lattice, we sample over a carefully chosen sublattice, whose dual is the projection of the primal lattice onto a lower-dimensional subspace. This reduces the lattice dimension and thus substantially accelerates discrete Gaussian sampling. We rigorously analyze the parameter conditions for the success of our framework, and by enumerating all feasible parameters we achieve an improvement of $26.1$--$43.7$ bits over the original provable dual attack framework.

In this note we find large primes $p$ such that $\Phi_k(p)$ is $B$-smooth for the cyclotomic polynomials $\Phi_k$, with $k = 3,4$ and $6$, and a sufficiently small smoothness bound $B$. These primes hence provide the first instantiation of integer factoring challenges that, a priori would be difficult to factor but, are actually easy to factor with traditional algorithms not typically used in practice.

Optimizing quantum circuits is critical: circuits must fit within the resource limits of a quantum computer, and every unnecessary operation increases their cost and probability of failure.We present a simple optimization algorithm for quantum circuits that (1) is very fast, (2) scales to millions of operations, and (3) matches or outperforms the optimization quality of the best existing optimizers and superoptimizers. Our key insight is that we can compactly represent circuit equivalence classes as a map which associates a projective unitary with a smallest representative circuit implementing it. We give a sound algorithm for synthesizing such maps, which we call minimal unitary representative maps (MURMs). Armed with a MURM, our optimizer inspects every bounded subcircuit in a linear pass and replaces it with a minimal variant. Incremental computation and symbolic arithmetic make every replacement fast and sound. Our evaluation shows that our approach achieves significantly greater circuit reductions than leading optimizers, runs orders of magnitude faster, and scales to circuits with millions of operations.

We propose a new variant of the Fiat–Shamir transformation where the Fiat-Shamir hash is instantiated by an external verifiable random function (VRF) service. We prove that soundness holds as long as the VRF secret key remains hidden from the prover, i.e., assuming no collusion between the prover and the VRF evaluator. Crucially, due to the public verifiability of VRF outputs, the VRF computation itself need not be trusted beyond the key-generation phase. This yields the first NIZK compiler in a non-idealized model that is both practical and provably sound. Our transformation can be instantiated using extensively deployed blockchain-based VRF services. Moreover, it naturally supports distributed VRF services, allowing the no-collusion assumption to be relaxed: soundness holds even if the prover colludes with up to a threshold number of evaluators. In this setting, distributed key generation for the VRF further eliminates trust in the setup. A distinctive feature of our approach is that the verification step is local and does not require accessing the VRF. This is particularly advantageous for recursive proof systems such as incrementally verifiable computation, where the verification circuit must be embedded within the circuit for which a proof needs to be generated. This enables construction of the first provable and practical recursive proof -- bypassing well-known impossibilities in the random oracle model. We demonstrate the real-world utility of our framework with an implementation for the GKR protocol.

Noisy linear algebraic assumptions (NLAs), such as $\mathsf{LWE}$ and Alekhnovich’s $\mathsf{LPN}$, have long served as the most reliable sources of post-quantum hardness. However, a series of recent classical attacks on assumptions once believed to be quantum-secure, coupled with the rapid progress in quantum technology, underscores the urgent need for assumptions that are plausibly hard even if both $\mathsf{LWE}$ and $\mathsf{LPN}$ turn out to be broken. A fascinating recent work of Ghosal et al. (Eurocrypt 2025) takes an important first step in this direction, constructing a PKE scheme by combining two NLAs that remain plausibly secure even if $\mathsf{LWE}$ and Alekhnovich’s parameter regime for $\mathsf{LPN}$ were to be polynomially broken. A critical weakness of their work, however, is that it is still $\mathsf{LPN}$-broken: namely, an oracle that breaks $\mathsf{LPN}$ with $n^{-\delta}$ noise rate can break their NLA, for some $\delta>0$. We ask: can this barrier be overcome? We answer this question positively, by introducing an NLA that is plausibly hard given an oracle that breaks even constant noise rate $\mathsf{LPN}$, while still being plausibly hard given an oracle that breaks $\mathsf{LWE}$. Along the way, we improve upon the work of Ghosal et al. significantly in several dimensions. Specifically, we introduce a single new natural NLA and provide constructions of (i) public-key encryption and (ii) two-round maliciously secure oblivious transfer protocol from this single assumption. We also construct a one-time circular-secure secret-key encryption from a binary variant of this assumption. Our assumption takes the form $(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e})$, where $\mathbf{A}$ is a random unstructured square matrix, the secret $\mathbf{s}$ has short and sparse entries, and the error $\mathbf{e}$ is a mixture of two components: a small-but-dense error combined with a large-but-sparse error. We provide a comprehensive initial cryptanalysis, ruling out (1) efficient combinatorial attacks that exploit sparsity such as information set decoding, (2) dimension reduction attacks, and (3) dual lattice attacks. We also prove, via a reduction, that our assumption, and its binary variant, is at-least as hard as $\mathsf{LWE}$. Additionally, we show that for a broad range of parameters including those used by our constructions, our assumption does not appear to fall within the class of “lattice” assumptions, that is, there seems to be no reduction to approximate shortest vector problem solvers, and, crucially, it is plausibly hard even given an oracle that breaks $\mathsf{LPN}$ for any noise density parameter.

We construct the first polynomial commitment in groups of unknown order that simultaneously requires no trusted setup, has quasilinear prover time, and has constant-size opening proofs. Our main technical contribution is a transparent class group realization of the subset-product accumulator relation introduced by Morphic accumulators (CRYPTO ’26). It supports accumulating a fixed family of class group elements and proving prescribed algebraic relations among the accumulated elements, yielding constant-size range arguments with quasilinear prover time. Combining these range proofs with the DewTwo framework (CRYPTO ’25) gives the first transparent polynomial commitment with quasilinear prover time and constant-size openings. Concretely, our construction also gives the shortest known opening proofs (1.3 KB) among transparent polynomial commitments. We prove security under falsifiable class group assumptions and also develop new extraction techniques over dyadic rationals, which may be of independent interest.

Binomial coefficients modulo an integer, $\binom{N}{R} \pmod m$, are a primitive of combinatorial counting, yet the two textbook methods collapse at scale: the Pascal recurrence costs $\Theta(NR)$ time, and the factorial-table method costs $\Theta(N)$ memory, requires a prime modulus, and requires $N < m$. Composite moduli are harder still, because factorials are not invertible modulo prime powers and the exact power of $p$ dividing the coefficient must be tracked. We present a complete, provably correct engine for arbitrary $m < 2^{62}$ and $N < 2^{64}$. Methodology. The modulus is factored as $m = \prod p_i^{k_i}$ by trial division, deterministic Miller-Rabin, and Pollard-Brent rho. For each prime power we prove and implement the decomposition $\binom{N}{R} \equiv p^e F_p(N) F_p(R)^{-1} F_p(N-R)^{-1} \pmod{p^k}$, where $F_p$ is the $p$-free part of the factorial and $e$ is Kummer's carry count; the same count yields an $O(\log_p N)$ short-circuit that decides $p^k \mid \binom{N}{R}$ before any multiplication. A periodicity lemma derived from Gauss's generalization of Wilson's theorem compresses the state of Pascal's triangle modulo $p^k$ to $p^k$ prefix products, giving two regimes with proven bounds: a table regime answering queries in $O(\log_p N)$ multiplications after $O(\min(p^k, N_{\max}))$ preprocessing, and a direct regime costing $O(R + \log_p N)$ multiplications for $R < p^k$ with $O(1)$ memory. Residues are recombined by the Chinese Remainder Theorem. The hot loops are division-free: Montgomery arithmetic exploits an incremental-form identity so that every unit costs one multiply and one add, and moduli $2^k$ reduce by a bit-mask. Four modular-inverse strategies are compared, including Fermat-Hensel lifting and an inverse-prefix table built with a single inversion. Validation. 3,139,684 oracle checks against Pascal's triangle, Lucas' theorem, Gauss's theorem, and literature constants, plus 3,004 exact big-integer comparisons, passed with zero failures; all 101 benchmark checksums are bit-identical across a Windows GCC 16 12th-gen Intel laptop and a Linux GCC 11 Xeon server. Results. At $N \approx 10^{18}$ a query costs 1.4 to 6.9 microseconds for composite moduli and scales linearly in $\log N$ at 15 to 36 ns per base-$p$ digit. For prime moduli the table regime answers queries in 0.09 to 0.27 microseconds independently of $p$, and building the table costs 0.36 to 0.85 of a single worst-case direct query, so it pays for itself immediately. Montgomery arithmetic is 2.0 to 3.1 times faster than 128-bit modulo and bit-masking up to 6.7 times; Fermat-Hensel inversion is 16 to 20 times faster than the extended Euclidean algorithm at $2^{40}$ and 1.4 to 2.0 times faster for large odd prime powers. Against the Pascal recurrence the engine is already 7,100 to 12,800 times faster at $N = 4 \times 10^4$; at $N = 10^9$ the recurrence would need 4.6 to 5.8 CPU-years and a 4 GB row, whereas the engine answers in about 2 microseconds from a 244-byte table. With uniformly random $R$, the Kummer short-circuit resolves 95% to 99.998% of prime-power solves in $O(\log N)$ time, a rate predicted exactly by Fine's theorem. We also report the honest wall: for a prime $p \approx 10^9$ with $R \approx N/2$ no table fits in memory and a query costs 3.4 to 4.5 seconds—the intrinsic $\Theta(p^k)$ bound that only sub-linear factorial algorithms could remove.

Context-committing security binds an authenticated encryption (AE) ciphertext uniquely to its encryption context. Many conventional AE schemes lack this guarantee, while most generic committing transforms rely on idealized primitives. We develop committing AE from explicit forkcipher collision-resistance properties: $\mathsf{fCR}$ and zero-message collision resistance ($\mathsf{zmCR}$). For an $n$-to-$2n$-bit forkcipher, we establish matching query complexities of order $2^{n/2}$ and $2^n$, respectively. MILP- and SAT-based differential and reduced-round collision analyses of $\textsf{ForkSkinny-128-384}$ support the corresponding generic security levels for the full-round primitive. We also analyze collisions in ButterKnife and ZIP-AES. We lift $\mathsf{fCR}$ and $\mathsf{zmCR}$ through FCPRF and FixM to fixed-length collision-resistant PRFs. We introduce nonce-based PRF security to capture the nonce-respecting pseudorandomness needed by our constructions, and construct FHashN, proving its variable-input-length collision resistance, pseudorandomness, and nonce-based pseudorandomness. We present AEaH-2K, a two-key variant of AEaH combining secure AE with a variable-input-length collision-resistant PRF. Including the AE key in the commitment input gives confidentiality, authenticity, and CMT-4 security in the standard model. We also construct $\textsf{FCTR-CMT}$, an AEAD mode using a single forkcipher, and prove nonce-respecting privacy, authenticity, and CMT-4 security. With FHashN based on FCPRF, $\textsf{FCTR-CMT}$ achieves $n$-bit confidentiality and $n/2$-bit authenticity and CMT-4 security; with FixM, all 3 reach $n$ bits. All construction proofs reduce to explicit pseudorandomness and collision-resistance assumptions.

We develop a new Coppersmith lattice attack on balanced CRT-RSA with small CRT exponents $d_p, d_q$ using unravelled linearization. The new attack matches the practical effectiveness of the Takayasu–Lu–Peng attack (JoC 2019) while using lattices of roughly half the dimension. In contrast to their attack, for which there is a noticeable gap between the theoretical predictions and experimental results, our theoretical estimates closely match the experimental results for all tested parameter sets. Our analysis further shows that the asymptotic bound remains $d_p,d_q<N^{0.122}$, so the new attack does not achieve the asymptotic improvement anticipated by Takayasu, Lu, and Peng. Nevertheless, performing LLL reduction on lower-dimensional lattices substantially reduces the running time, allowing us to attack much larger $d_p,d_q$ in practice. Furthermore, through elegant variable substitutions, we extend our attack to two most significant bit (MSB) leakage models, obtaining the first attack exploiting MSB leakage of $p+q$ and an improved attack exploiting MSB leakage of $d_p,d_q$. In both models, the asymptotic bounds improve as the amount of leakage increases and recover the Takayasu–Lu–Peng bound in the absence of leakage.

Computing smooth-degree isogenies between supersingular elliptic curves with known endomorphism rings is a fundamental task in isogeny-based cryptography. Via the Deuring correspondence, this task is equivalent to finding a connecting ideal of smooth norm between the corresponding quaternion maximal orders. KLPT-type algorithms address this problem by transforming a known connecting ideal into an equivalent ideal of smooth norm. Although connecting ideals of norm approximately $p$ are expected to exist, the best known such algorithms for general input only achieve norm $\widetilde{O}(p^{4.5})$. In this paper, we propose $\Delta$-KLPT$^+$, a new KLPT-type algorithm that lowers this bound to $\widetilde{O}(p^4)$. Our construction builds on $\Delta$-KLPT, which attains a smaller norm bound but requires two input ideals of the same prime norm. To extend $\Delta$-KLPT to arbitrary inputs, we introduce a new subroutine IdealNormReduce, which reduces the common norm of an ideal pair. By iterating IdealNormReduce, we obtain two ideals with a common norm below $p$. Then we apply $\Delta$-KLPT to the resulting ideal pair to obtain a desired connecting ideal of smooth norm. As an application, we construct Delfar, a fully anonymous isogeny-based ring signature scheme. Compared to Erebor-full, Delfar achieves shorter signatures and lower signing and verification costs for large rings.

The Keccak hash function, designed by Bertoni et al., was selected as the new generation of Secure Hash Algorithm (SHA-3) in 2012. For NIST-standardized SHA-3 instances (SHA3-224/256/384/512, SHAKE128, SHAKE256), practical collision attacks have reached five rounds; six-round SHAKE128 was known only as a theoretical attack with cost $2^{123.5}$ six-round evaluations~\cite{tuyi2022sha3}. In this paper, we present the first classical practical collision attack on six-round SHAKE128 with $d{=}160$ and total complexity about $2^{47.82}$. Building on the Dinur-framework Dinur et al.~\cite{dinur2012new} and the SAT tooling of Guo et al.~\cite{tuyi2022sha3}, we introduce a parameterized colliding-trail SAT model--- collision length in digest and weight bounds are chosen at setup together with leaner differential encodings. Specifically, we introduce an enhanced heuristic strategy to identify suitable differential trails and employ multiple techniques to optimize the connectors: for the connector phase, we minimize weighted propagation cost of second round and third round, and penalize costly $\mathrm{DDT}{=}2$ transitions; candidate $\chi$-compatible equations are chosen by a bit-granular greedy routine that maximizes connector degrees of freedom. In addition to SHAKE128, we report six-round \textbf{near}-collisions on SHA3-224 and SHA3-256 (four and six differing digest bits, respectively), and practical collisions on four- and five-round SHAKE256 with the full $512$-bit digest.

We present Couplet, a new pairing-based multivariate polynomial commitment scheme (PCS). Couplet is the first multivariate PCS whose opening proofs are solely two group elements. In addition, for the case of multilinear polynomials, Couplet is the first constant-proof PCS with a prover that requires only a sublinear number of group operations. We achieve those properties simultaneously at the expense of a quasilinear, polynomial-specific, one-time preprocessing phase, whose cost can be amortized over multiple subsequent openings. On BN254, our implementation opens multilinear polynomials with $20$ variables about $20\times$ faster than Mercury after preprocessing, breaking even in total prover time after roughly 100 openings. Our approach generalizes to batched evaluation proofs, yielding a constant-size proof for multiple evaluation points without using random oracles. Applications include verifying repeated inferences of a committed model as well as more efficient auditable authenticated dictionaries. Our main technique involves compressing Papamanthou--Shi--Tamassia (PST) evaluation proofs, giving a single commitment which encodes all $\log n$ quotient polynomials which are normally given out separately in a PST proof. In doing this, we reduce the verification to a univariate sumcheck problem, which we solve with techniques from Groth16 using a single additional group element. We prove extractability in the algebraic group model under a parameterized discrete-logarithm assumption. We give hiding variants and prove perfect zero-knowledge of the opening protocols. All opening protocols are noninteractive and require no random oracle.

MPC-based privacy-preserving machine learning (PPML) typically operates over finite rings rather than floating-point arithmetic, making arithmetic overflow an inherent risk. Existing overflow-detection techniques generally require the evaluation of nonlinear functions, resulting in substantial computation and communication overhead. We propose Soft Boundary Detection, which reduces boundary verification to probabilistic functions over partitioned intervals, with a cost comparable to that of linear computation. Building on this abstraction, we develop an efficient mechanism for detecting arithmetic overflow in PPML workloads. Moreover, we show that Soft Boundary Detection naturally extends to the malicious-adversary setting. In ring-based computation, it further avoids the need to choose a ring space substantially larger than the actual data range to ensure soundness against malicious behavior. Our framework provides two key benefits: (1) highly efficient arithmetic overflow detection, and (2) active security without requiring ring extension or enlarging the underlying ring space. Experimental results demonstrate that our approach substantially strengthens security while retaining high efficiency, providing a practical solution for robust and actively secure PPML.

Multiplicative zero-knowledge ($\mathsf{MZK}$) replaces the negligible statistical distance required by statistical zero-knowledge ($\mathsf{SZK}$) with symmetric $(\varepsilon,\delta)$ approximate max-divergence between real and simulated verifier views. Prior work established efficiency gains from this relaxation; we study its computational power. With negligible completeness, soundness, and additive simulation errors, \[ \mathsf{HVMZK}[\varepsilon]=\mathsf{MZK}[\varepsilon]=\mathsf{SZK} \qquad\text{for }\varepsilon(n)=O(\log n), \] where $n$ is the input length. Taking the union over polynomial leakage bounds gives \[ \mathsf{MZK}[\mathrm{poly}]=\mathsf{HVMZK}[\mathrm{poly}]=\mathsf{PSPACE}, \] even with zero additive simulation error. For every fixed $c>0$, a polynomially padded $\operatorname{TQBF}$ language remains $\mathsf{PSPACE}$-complete and belongs to $\mathsf{MZK}[O(n^c)]$. A linear-leakage protocol for $\operatorname{SAT}$ separates $\mathsf{MZK}$ from $\mathsf{SZK}$ unless the polynomial hierarchy collapses to its second level. Padding yields $\mathsf{NP}$-complete separators at every fixed positive polynomial exponent. Under a subexponential weakening of the nonuniform nondeterministic Strong Exponential Time Hypothesis, every polylogarithmic level $\mathsf{MZK}[O((\log n)^j)]$ with fixed $j\geq2$ strictly contains $\mathsf{SZK}$. The logarithmic threshold is tight relative to oracles: every polynomial-time computable, polynomially bounded superlogarithmic leakage budget admits an oracle separating classical $\mathsf{MZK}$ from quantum statistical zero-knowledge. Finally, fraction statistical knowledge complexity exactly characterizes one-sided real-to-simulator multiplicative simulation, with the sharp knowledge parameter and negligible statistical error.

Lattice-based proof systems are one of the leading routes to quantum-safe succinct proofs. Existing lattice-based schemes come with inherent limitations arising from the coupling between the commitment and constraint domains. First, commitment efficiency is restricted by the need for invertible challenge differences, which precludes the use of fully splitting moduli that enable the fastest lattice arithmetic. Second, the characteristic of the constraint field must equal the commitment modulus. This limits the efficiency of proving binary computations, including standard hash function evaluations. We present $\mathsf{LaBinius}$, a lattice-based polynomial commitment scheme, in which the evaluation arithmetic is separated from that of the commitment. The commitment runs over a composite modulus, and all of its prime factors are NTT-friendly. The evaluation claim lives in a binary extension field, without bitness checks or overhead over a binary arithmetisation. We implement the scheme with AVX-512 kernels and connect it to the $\mathsf{Binius}$ and $\mathsf{Flock}$ front ends in an almost black-box way, which lets us use their arithmetisations tailored to binary fields. As a result, we obtain a SNARK for standard hashes. Proving $\mathsf{Keccak}$-$\mathsf{256}$, $\mathsf{SHA}$-$\mathsf{256}$ and $\mathsf{BLAKE3}$ on one core, our prover takes at most $1.2$ times as long as the hash-based prover supplied with each system, and we obtain a single-core throughput of over $67{,}000$ $\mathsf{BLAKE3}$ compressions per second with verification in under $40$ milliseconds. With $\mathsf{LaBRADOR}$ as a recursive compressor, the prover takes less than twice as long as the hash-based provers at the largest sizes we consider, while the proof size is below $100$ KiB. This is about five times smaller than the proofs of $\mathsf{Binius}$ and $\mathsf{Flock}$ at those sizes and constitutes the smallest quantum-safe proof of a standard hash evaluation to date.

Decryption in EC-ElGamal and Twisted ElGamal based Additively Homomorphic Encryption (AHE) requires solving a small exponential Elliptic Curve Discrete Logarithm Problem (ECDLP) that recovers a bounded plaintext scalar $m$ from $m \cdot G$. This recovery step is the performance-critical path in various applications, such as electronic voting systems (e-Voting), private federated learning, and privacy-preserving blockchain confidential payment systems including Zether (EC-ElGamal), Solana Token-2022 Confidential Transfers (Twisted ElGamal), and the forthcoming XRPL XLS-96 standard (EC-ElGamal). The state-of-the-art FastECDLP (Tang et al., 2023) employs the baby-step giant-step algorithm (BSGS) to solve ECDLP in $\ell$-bit range by utilizing a baby-step table $T_1'$ of $2^{\ell_1 - 1}$ affine points and achieves fast decryption by precomputing a giant-step table $T_2'$ of all $2^{\ell_2 - 1}$ affine points where $\ell_1 + \ell_2 = \ell$. Even with the signed-range halving of Tang et al., the giant-step table for secp256k1 requires 5.91 GB for a 58-bit search space and exponentially increases to 378 GB for a 64-bit search space. Thus, as noted by Tang et al., a 64-bit range remains impractical on a typical workstation due to the memory requirements. We present three algorithmic contributions that together eliminate $T_2'$ and enable practical 64-bit decryption. (i) A Jacobian coordinate loop advances the giant-step point iteratively in Jacobian coordinates, removing the need to precompute the giant steps in affine coordinates. (ii) Windowed batch inversion batch-inverts a window of a small $W$ accumulated $Z$-coordinates at once, reducing the per-thread working memory required for the giant-step computation from $O(2^{\ell_2})$ (the size of $T_2'$ in FastECDLP) to $O(W)$ regardless of bit size. (iii) Co-Z arithmetic computes two giant steps simultaneously by maintaining a shared $Z$-coordinate, reducing the field multiplication cost per step. We validate our solver on two machines, a laptop-class Apple M1 Pro and a desktop-class Intel Core Ultra 9 285K, with consistent results across both. On the Intel machine, our complete solver outperforms a faithful re-implementation of FastECDLP at 54-bit and 58-bit ($\ell_1 = 31$, up to $2.3\times$ faster) without storing the giant-step table $T_2'$. At 63-bit and 64-bit, Tang et al.'s giant-step table $T_2'$ requires 189 GB and 378 GB respectively, making their approach infeasible on typical desktop or laptop computers. So far, our solver is the only feasible approach, completing full 63-bit and 64-bit decryption in 53 sec and 105 sec, directly overcoming the memory limitation identified by Tang et al. We also discuss two additional arithmetic optimizations, an inversion-chaining scheme and a co-Z Jacobian addition, that reduce the per-step arithmetic cost.

Private information retrieval (PIR) inherently requires public-key cryptography. A recent line of work suggests that this barrier can be avoided in secret-key PIR, where the client first preprocesses an N-bit database and retains only a short secret key. This line of work has yielded communication O(N^\epsilon) for any constant \epsilon under the Learning Parity with Noise (LPN) assumption in a high-noise regime not known to imply public-key cryptography, and communication O(N^{1/2}) under one-way functions. Whether compression beyond N^{1/2} can be achieved without relying on structured assumptions such as LPN has remained open. We show that interaction enables polylogarithmic communication in the random oracle model. We construct a secret-key PIR protocol with O(log N ) rounds and polylogarithmic total communication. Alternatively, for any constant \epsilon, we obtain a constant-round protocol with communication O(N^\epsilon). We also obtain protocols with similar communication in the plain model under the weakest version of LPN, with maximal noise rate 1/2 − o(1). Our main idea, inspired by the free-XOR technique for circuit garbling, is to make secret-key preprocessing homomorphic under XOR, while relying on security against related-key attacks.

The Groth16 verification equation has a compact algebraic description, yet garbling its Boolean implementation can require tens of gigabytes. We show how to garble this computation using native elliptic-curve group operations. Motivated by proof verification in trust-minimized Bitcoin bridges, we construct a projective partial garbling scheme for conditional disclosure on invalid Groth16 proofs. For a fixed verification key and public statement, evaluation reveals a garbler-held secret when the supplied proof is invalid and hides the secret when it is valid. The proof itself remains public. The main technical challenge is handling a pairing whose two arguments are supplied by the evaluator. We introduce a rekeying gadget that resolves this using a single private scalar multiplication. Building on Argo MAC (Eagen and Lai, 2026), BABE (Garg et al., 2026), and Duty-Free Bits (Khambhati et al., 2026), we prove a composition theorem for partial garbling across input representations and apply it to transform group encodings into bitwise projective encodings. This requires extending the projectivization technique of Duty-Free Bits to quadratic extension fields. The resulting garbled program has size $O(\lambda^2)$ bits, where $\lambda$ is the computational security parameter. We prove privacy under the decisional Diffie-Hellman assumption, in the random oracle model. Our BN254 implementation produces a 2.4 MiB garbled program, including projectivization, compared with the 48 GB reported for Boolean garbling of Groth16. Thus, we improve over prior state of the art in Groth16 garbling by over four orders of magnitude.

Succinct arguments are a fundamental cryptographic primitive for verifying computational claims with small communication. In the classical setting, succinct arguments for NP can be constructed from unstructured hardness alone (e.g., hash functions) by compiling probabilistically checkable proofs (PCPs) or interactive oracle proofs (IOPs) for NP via the commit-and-open paradigm. In contrast, known succinct arguments for QMA rely on ``structured'' cryptographic primitives, or on the quantum PCP conjecture. We construct the first succinct argument for QMA in the quantum random oracle model (QROM) without relying on additional cryptographic assumptions or unproven conjectures. This yields succinct arguments for QMA from unstructured hardness alone, showing that ideal hash functions not only suffice for succinct arguments for NP but also for QMA. Underlying our result is an efficiency-preserving transformation that compiles quantum interactive oracle proofs (QIOPs), a recently introduced interactive generalization of quantum PCPs, into quantum arguments for the same language, via a natural quantum commit-and-open paradigm. Our transformation applies to every QIOP with public-query soundness, a notion that we formalize to capture a natural requirement of the commit-and-open paradigm and is satisfied by a known QIOP for QMA. As a key ingredient in our transformation, we formalize and construct extractable vector commitments for quantum states with local openings in the QROM, which may be of independent interest.