Many hash-based proof systems check that committed words are close to Reed–Solomon codewords by testing one random combination of them. Their soundness analysis uses a proximity gap: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few exceptional challenges. Such gaps are known above the Johnson threshold, about $\sqrt\rho$ for rate $\rho$, and extending them below it would shrink proofs. Recent work does so in large characteristic, but not over binary fields, where some of the fastest proof systems run. We show that beyond-Johnson proximity gaps fail over binary fields. Our first construction applies to any additive domain (a binary linear subspace) filling a constant fraction of a containing binary field. Over a suitable extension challenge field and at rate $1/4$, it gives two words that can simultaneously match codewords on at most $25\%$ of the positions, while their combinations approach the $50\%$ Johnson threshold for superpolynomially many challenges. This rules out any $\mathrm{poly}(N)/|\mathbb F|$ bound on the exceptional probability below Johnson. On Binius64's domain (length $2^{27}$, $128$-bit challenges), the combination reaches $49.4\%$ agreement with probability above $2^{-30}$. The construction also rules out polynomial-size decoding lists below Johnson: one word agrees with superpolynomially many codewords at agreement approaching $50\%$, whereas earlier superpolynomial lists needed the rate, or the agreement–rate gap, to vanish. Our second and third constructions cover every additive domain, including the sparse domains used by LeanVM and Flock. At rate $1/16$, the second gives $(N-1)(N-2)/6$ exceptional challenges at the Johnson threshold itself, when the domain lies in a proper subfield of the challenge field. For domains larger than $2^{20}$, this rules out even $90$ bits of soundness from a single beyond-Johnson proximity-gap check over a $128$-bit challenge field. The third construction trades agreement for larger exception counts: at rate $1/2$ and length $2^{22}$, its combinations reach $53.125\%$ agreement from common agreement $50\%$, with probability at least $2^{-20}$ over a $192$-bit challenge field. Finally, at every fixed rate, some constant agreement above the rate makes every challenge exceptional, over $\mathrm{poly}(N)$-size challenge fields. All of our results are formally verified in Lean.

Encrypted key exchange (EKE), introduced by Bellovin and Merritt (IEEE S\&P 1992), and Masny-Rindal OT, introduced by Masny and Rindal (ACM CCS 2019), are highly-efficient methods for compiling essentially any KEM into advanced cryptographic protocols, namely password-authenticated key exchange (PAKE) and oblivious transfer (OT), by relying only on idealized symmetric-key primitives. They have become leading candidates for practically-implementable PAKE and OT due to (1) their simplicity, (2) their plug-and-play nature, allowing for flexibility in the choice of KEM, and (3) existing proofs of UC-security (in the classical adversarial model). Due to point (2) above, these compilers yield attractive candidates for efficient post-quantum PAKE and OT, especially given the recent post-quantum KEM standardization efforts. This motivates the question of whether the (UC-)security of these compilers translates to the quantum adversarial model. In this work, we show that it does not. In particular, we prove that a general family of (O)EKE protocols, as well as Masny-Rindal OT, are not UC-secure against quantum polynomial-time adversaries, even when instantiated with a post-quantum KEM. To establish UC-insecurity, we devise an adversarial strategy that provably thwarts any attempt by the simulator to extract its input (the password in the case of PAKE, and the receiver's choice bit in the case of OT). These are the first naturally-occurring/non-contrived cryptographic protocols that are known to be secure in the (classical) ROM but provably insecure in the QROM. To complement these negative results, we establish that both compilers yield certain notions of game-based security. In the PAKE setting, we consider OEKE instantiated with the ``2-Feistel'' cipher, and prove its stand-alone game-based security in the quantum random oracle model. We view these results as a proof of concept that security of (O)EKE and Masny-Rindal OT can yet be redeemed in the quantum setting, though we caution that the situation will be more subtle than in the classical setting due to the breakdown of simulation-based security. Along the way, we establish a novel ``advantage-tight'' one-way to hiding lemma that may be of independent interest.

Verifiable Computation on Encrypted Data (vCOED) enables clients to outsource computation while providing both privacy and integrity. A promising vCOED paradigm is blind proofs, which use homomorphic encryption (HE) to evaluate verifiable computation (VC) proofs on encrypted data. Despite their efficiency, blind proofs do not provide strong client privacy: a malicious server can exploit reaction attacks to learn information about the client's inputs, intermediate values or final outputs. Our work addresses this limitation by introducing Homomorphic Encryption over Random Encodings (HERE). We formalize a new security notion, indistinguishability under chosen-plaintext attacks in the presence of an equality oracle over encodings (IND-CPA-E). We prove that combining IND-CPA-E-secure HERE schemes with blind proofs that verify computation over the encodings yields vCOED protocols with strong client privacy. We then instantiate a HERE scheme for functions of bounded degree $d$, using Shamir secret sharing at $(d+1)$ evaluation points under $(d+1)$ distinct HE keys. Finally, we demonstrate the concrete efficiency of our approach through an application to matrix-vector multiplication (MVM), a linear computation corresponding to $d=1$. The proof overhead (i.e. the ratio of the vCOED prover runtime to the homomorphic MVM runtime) in our combined vCOED protocol is as low as $2\times$, as demonstrated in our prototype implementation.

We present conceptually simple and practically efficient constructions of a verifiable random function (VRF) that fulfills strong notions of unbiasability recently introduced by Giunta and Stewart (Eurocrypt 2024). Unbiasability is a crucial property for many applications of VRFs such as leader election in proof-of-stake blockchains. The only previous constructions provide heuristic security in the random oracle model or rely on the decisional Diffie–Hellman assumption with preprocessing which incurs significant overhead. In contrast, our compiler turns any VRF into an unbiasable VRF in the standard model (without any setup) using only symmetric-key primitives; and thus only with negligible computational overhead. Underlying our approach, we provide a generic black-box reduction for unbiasability of VRFs that incurs subexponential loss. Additionally, under a mild (verifiable) requirement on the underlying VRF we also show a novel non-black-box reduction that incurs only polynomial loss. This non-black-box technique allows us to replace the folklore "VUF-then-Hash" heuristic with a provably secure "Hash-then-VRF" construction at virtually no cost. In particular, if the underlying VRF hashes its input, our transformation requires only a single evaluation of a hardcore function, e.g. parity of the input (plus a PRF evaluation for full security).

Ducas, Engelberts and Loyer (CRYPTO 2025) turned Wagner's generalized birthday algorithm into a provable subexponential-time Gaussian sampler for unstructured short integer solutions. Recent preprints of Han, Gao and Hu, and of Chen, Jiang, Wang and Zhang, obtain low-sample decision learning-with-errors algorithms from this framework. We extend it to module matrices over power-of-two cyclotomic rings, for every residue degree of the prime modulus. For fixed module ranks $k,\ell\ge1$, let $n=kd$, $m=(k+\ell)d$, and suppose $\ln(q/\sqrt n)=(\ln n)^{b+o(1)}$. For every fixed $b,c,\xi>0$, we solve Module-SIS with coefficient infinity-norm bound $q/(\ln n)^c$ in worst-case time and space $2^{(1/(2b)+\xi)n/\ln\ln n}$. For matrix-independent errors satisfying $\|e\|\le\sigma\sqrt m$ with probability $1-o(1)$ and $\ln(2+\sigma)=(\ln n)^{a+o(1)}$, $0\le a<b$, decision and search Module-LWE take $2^{(1/(2(b-a))+\xi)n/\ln\ln n}$. Success is $1-o(1)$ using only the given $k+\ell$ ring samples; error coordinates need not be independent. The structural ingredient is a Chinese-remainder-support uncertainty bound: the loss of randomness of sparse dual labels is compensated by an arithmetic lower bound on their length. Scalar row perturbations give search over the base field, and small integer shears remove a singular-block loss. Projection, the Han--Gao--Hu martingale analysis, and a finite enumeration sampler give a common algorithmic framework. We also prove sample-preserving scalar search-LWE and narrow Module-LWE algorithms. In particular, for polynomial prime $q=n^{\kappa+o(1)}$, $\kappa>1/2$, one ring sample and growing rank suffice for decision and search in time and space $2^{(1/2+\xi)n/\ln\ln n}$ when the sample supplies $(1+o(1))n/\ln\ln n$ scalar responses. Here ``narrow'' restricts both secret and error. Separate heuristic estimates in the model of Ducas, Engelberts and Loyer suggest that Wagner-style attacks do not reach the NIST security targets of ML-KEM and ML-DSA.

Oblivious RAM (ORAM) allows a trusted client to access (encrypted) data stored in untrusted memory, such that the access patterns reveal nothing about the data or the queries. It is well-known that any ORAM scheme must suffer from a logarithmic overhead. More precisely stated, each request must incur $\Omega(\log_B N)$ block transfers on average, where $N$ is the size of the logical memory and $B$ is the block size of the oblivious implementation. Moreover, the same lower bound extends to oblivious Search Trees (ST). For upper bounds, however, we have been long stuck with a $(\log_B N)^2$ curse on two fronts: (1) Log-squared curse for statistically secure ORAMs: although optimality is known for computationally secure ORAMs for $B = \Theta(1)$ or $B \geq \log^{1+\epsilon} N$ (where $\epsilon > 0$ is an arbitrarily small constant), progress has been stagnant when it comes to statistical security. (2) Log-squared curse for oblivious search trees: for search trees, we do not know how to overcome the log-squared curse even when allowing computational assumptions. In this paper, we break this long-standing log-squared curse for both oblivious search trees and statistically secure ORAM on broad parameter regimes: (1) Our first result gives an optimal, statistically secure ORAM with $O(\log_B N)$ cost as long as $B \geq \log^{1+\epsilon} N$. (2) Our second result gives an optimal, statistically secure oblivious search tree with $O(\log_B N)$ cost when $B \geq \log^{2+\epsilon} N$, matching the performance of the best known non-oblivious search trees in this parameter region. Notably, this means that for search trees, we can get obliviousness for free! The assumptions on $B$ required to achieve optimality are standard and mild. They not only coincide with the standard wide cache-line assumption prevalent in the classical algorithms literature, but also align well with the hardware-enclave architectures that employ oblivious algorithms in practice, such as the implementations of Signal and Meta.

We construct the first multi-key fully homomorphic encryption (MKFHE) scheme where the ciphertext size, public key size, and secret key size remain independent of the number of users, $N$. Our construction is leveled and relies on the standard Learning with Errors (LWE) assumption. All prior MKFHE schemes incur at least linear growth in ciphertext size with the number of users ($|\mathsf{ct}| \propto N$), a limitation that has persisted across more than a decade of research. Our results provide the first evidence that MKFHE with constant ciphertext size is achievable under standard assumptions and paves the way for many interesting applications. We also describe a single-round distributed decryption protocol for multi-key ciphertexts in our fully-succinct MKFHE scheme. More remarkably, we show that our MKFHE scheme simultaneously satisfies the following properties: (1) the size of each user's partial decryption share is identically equal to the plaintext length (i.e., partial decryption shares are truly rate-1), and (2) an honest user's partial decryption can be simulated. To the best of our knowledge prior to this work, we did not have any MKFHE with one-round distributed decryption from standard assumptions that simultaneously satisfied both these properties. We show that our MKFHE is significantly useful in designing various forms of multi-party computation (MPC) protocols with asymptotically optimal communication complexity.

Individual cryptography (Dziembowski et al. Crypto'23) and complete knowledge (Kelkar et al. CCS'24) aim at constructing protocols that ensure that some individual party must know a secret value in the clear, and so the computation cannot have been “outsourced” to an MPC computation. Two central primitives are proofs of complete (or individual) knowledge, which enforce that some party actually knows the secret witness, and secret sharing with snitching, which enforces that whenever the secret is reconstructed, some party must learn a certificate of this fact. The instantiations proposed by both papers (Crypto'23 and CCS'24) ensure that to compute a proof or reconstruct the shared secret, a large number of hash function evaluations is necessary. Thus, at least one party must compute many of these “in the clear” (and not via MPC) and from the hash function inputs one can extract the secret (in the random oracle model). In practice, they suggest using Bitcoin mining hardware. Sequential proofs of complete knowledge have recently been proposed, which use proofs of sequential work to enforce that the hashes are performed sequentially. As a consequence, it suffices to require a much smaller number of hashes, and thus such primitives can be implemented on standard hardware. Unfortunately, this approach does not work for primitives like secret sharing, as one would need to efficiently sample the challenge for the sequential computation together with its solution. In this work, we leverage ideas from time-lock puzzles to overcome this issue. We construct secret sharing with snitching and encryption with self-incriminating proofs where reconstruction/decryption is sequential. The security of our scheme relies on a new knowledge assumption, which informally states that whenever parties that hold secret shares of an RSA modulus N=pq jointly compute 2^2^T N for some large T (too large to perform a sequential computation of length T in MPC), then at least one of them must have learned a multiple of N.

We give provable classical subexponential algorithms for secret recovery in growing parameter families associated with NIST third-round lattice candidates. For the Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, and Dilithium/ML-DSA families studied here, polynomial moduli and polylogarithmic coefficient scales yield recovery of the short secret component in expected time and space $2^{(1/2+o(1))n/\ln\ln n}$. For noisy or rounded linear relations, we exploit an exact gap in the squared Euclidean norm of a comparison vector defined by each coordinate guess. One Gaussian list suffices to identify every secret coordinate by binary search, without enumerating the others. We establish the required sampling guarantees through new geometric bounds for structured public operators over prime and power of two moduli. The construction builds on the Wagner-style Gaussian sampling framework of Ducas, Engelberts, and Loyer (CRYPTO 2025) and the low-error decision-LWE algorithm of Han, Gao, and Hu (2026). For quotient relations of NTRU type, we develop an affine slice search: fixing coordinates restricts candidate pairs to slices of the public lattice, and their estimated Gaussian masses guide the choice of each next coordinate. In the stated modulus window, Falcon's key generation quality condition supplies the required mass bound. The algorithm then recovers an equivalent signing key with high probability in time and space $2^{O(n/\ln\ln n)}$. The same search recovers the short key core for cyclic NTRU-HPS/HRSS. Together, these results give subexponential algorithms for problem families associated with all seven NIST third-round lattice candidates. Despite the subexponential complexity, our results do not establish a reduction in the concrete security of the currently specified parameter sets.

Motivated by recent constructions and barriers in secret sharing, we study multislice functions. These functions, parametrized by a width parameter $w$, take the value 0 on inputs of Hamming weight below a base value $k$, 1 on inputs of weight above $k+w$, and are monotone in between. We first investigate formulas over multislice gates, which generalize the formulas over slices model (Applebaum et al., TOCT 2026). We prove that, although multislices compute complicated functions, they do not help in computing the worst-case function when $w\ll n$; that is, there is an explicit monotone function such that for every $w$, every formula over multislice gates of width $w$ that computes it, regardless of its depth and gate fan-in, has size $2^{\Omega\left(n/((w+1)\log^2 n)\right)}$. Our lower bound is based on a randomized Karchmer-Wigderson protocol for multislices that can be amortized across the formula. As a complementary result, we show how to realize multislices using slice gates, i.e., multislice gates of width 0; the construction uses a simple peeling recursion. Consequently, every width-$w$ multislice on $n$ variables has a formula over slice gates of size at most $2n^{w+1}$ and depth $(w+1)$. The same construction allows to compute multislices with small monotone real formulas and circuits, two models introduced by Pudl\'ak (J. Symb. Log., 1997) in the context of proof complexity. This result also has an application to secret sharing: it yields, for sufficiently long secrets, multilinear secret-sharing schemes for width-$w$ multislices with maximal information ratio $n^{O(w+1)}$, which is polynomial for every fixed $w$. In addition, we prove that an explicit access structure requires shares of size $2^{\Omega(n)}$ in every secret-sharing scheme from a family of schemes that captures all currently known constructions for general access structures with share size $2^{cn+o(n)}$, for $c<1$. Our proof goes through an exponential lower bound on the size of formulas over so-called CDS gates and ideal linear gates.

Bleichenbacher's 1998 padding oracle attack against RSA PKCS#1 v1.5 has resurfaced repeatedly over the past decades, especially in TLS. Although modern browsers prefer TLS 1.3, many servers and clients still permit RSA key exchange for backward compatibility, enabling active network attackers to decrypt recorded sessions. Still, practical man-in-the-middle attacks remain challenging. The classical attack narrows the plaintext interval from the top down, spending many queries on secret-independent padding bytes before reaching the PreMasterSecret in the low-order 46 bytes of the RSA plaintext. As a result, prior attacks required multiple vulnerable servers in parallel to avoid connection timeouts. In this paper, we present Reverse-Bleichenbacher, a novel variant of the Bleichenbacher algorithm. In contrast to all previous Bleichenbacher-style algorithms, our algorithm recovers the least significant bytes first and terminates the search as soon as the target secret is recovered. When the secret occupies only a fraction of the plaintext, as with the TLS PreMasterSecret, this significantly reduces the number of required queries. Together with improved trimmers and a coverage-optimized search, this reduces the median number of oracle queries from 11.428 to 1801 against a standards-conforming PKCS#1 v1.5 oracle with 2048-bit keys, with an overall success rate of 84.8 %. Crucially, under realistic single-server conditions (a 2.6 ms median round-trip time we observe to vulnerable hosts and 2 round trips per query) 68.3% of all runs finish within a 30s timeout, compared with none of the prior algorithms. To remain feasible at higher latency, we parallelize independent queries: at 20 ms round-trip time, batching reduces the median end-to-end runtime from 59.3s to 8.3s, at the cost of additional queries. We identify 640 vulnerable domains in the Tranco Top 1 Million, many behind Alibaba Cloud load balancers. We demonstrate end-to-end impact on real software distribution channels: a man-in-the-middle attacker can inject malicious updates and achieve remote code execution on a victim device.

Research on cryptographic algorithms implemented in hardware and protected against side-channel attacks has advanced rapidly in recent years. Generalized masking schemes, such as Threshold Implementations (TI) and Domain-Oriented Masking (DOM), currently provide a solid theoretical security foundation. Security models, including the probing model and its various extensions, enable formal verification of these guarantees. In addition, established guidelines for designing securely composable gadgets, along with tools for the automatic generation of masked designs, have further advanced the field. Experimental security assessment approaches, such as the Test Vector Leakage Assessment (TVLA) complement these efforts. Consequently, the primary focus of the research community has shifted toward optimizing existing techniques and bridging the gap between theoretical and practical security models. In this work, we demonstrate a case in which side-channel leakage, caused by glitches, can be concealed during experimental assessment in a setup that is theoretically not robustly secure. This effect arises due to specific patterns of glitch propagation. We investigate whether a particular layout of the complete logic chain can further contribute to a design’s resistance to side-channel attacks, potentially reducing latency and area by relaxing glitch-mitigation requirements, such as reducing the number of pipeline registers. To this end, we introduce new adversarial model which further relaxes the model of Müller and Moradi, introduced at CHES 2024. To illustrate the practical relevance of our proposal, we provide experimental evidence by modifying a well-known, provably secure AES S-box design by De Cnudde, rendering it insecure under the robust probing model. We conduct TVLA of power consumption for both FPGA-based (physical) and ASIC-like (simulation) implementations of our netlists, demonstrating the absence of detectable leakage, similar to the originally robustly secure version of the algorithm.

Large-size Number Theoretic Transforms (NTTs) are key operations in modern Zero-Knowledge Proofs (ZKPs), where the NTT size often reaches millions of points and the arithmetic is over wide prime fields. To handle such NTTs on hardware, prior designs commonly rely on the decomposition algorithm, which makes large-size NTTs feasible by streaming sub-NTTs through limited on-chip buffers. However, in practical implementations, decomposition alone is insufficient to ensure high efficiency. Since coefficients and twiddle factors remain off-chip, performance tends to depend on data movement across the memory hierarchy and delivery to the processing elements (PEs). To address these remaining issues, we present RENTT, a resource-efficient accelerator for large-size NTTs with decomposition-oriented data movement schemes and memory hierarchy design. First, we design a precomputation-based twiddle factor management scheme that feeds multiple PEs without conflicts, both reducing on-chip twiddle factor storage and avoiding on-the-fly twiddle factor generation. Second, we develop a burst-optimized transpose method that fuses coefficient reordering into the element-wise twiddle-multiplication pass, reducing the latency of off-chip accesses for the subsequent NTTs. Third, we design a decoupled, multi-banked on-chip memory hierarchy that sustains high PE utilization under off-chip streaming, while remaining configurable across PE counts and maximum supported NTT sizes. We implement RENTT on an FPGA and experimentally verify that RENTT supports NTT sizes up to $N=2^{28}$ over 256-bit fields and completes a $2^{28}$-point NTT in 1.52 seconds with 16 processing elements. Compared with the state-of-the-art FPGA baseline SAM, RENTT provides $2.64\times$ speedup (1.52s vs. 4.02s), reduces 46.4% DSP usage (3629 vs. 6776 DSPs), and achieves a $3.58\times$ lower area-time product.

In cryptographic algorithms based on groups in which the discrete logarithm is supposed to be hard, it is frequent to perform polynomial arithmetic in the exponent of group elements. This old technique has become a critical operation in many recent advanced protocols, mostly related to commitments and zero-knowledge proofs, where polynomials of high degrees are involved. Number Theoretic Transform (NTT) techniques in the exponent are often implemented to gain speed. However, they require roots of unity to exist in the field GF(q) where q is the order of the group. In this work, we propose algorithms that preserve the quasi-linear complexity of the Fourier Transforms, even when no root of unity are available. For this, we develop a formalism for the algebraic structure of polynomials with coefficients in a group, that allows us to adapt asymptotically fast polynomial multiplication algorithms to the case of arithmetic in the exponent. In particular, we design an algorithm inspired by the Schönhage-Strassen algorithm, which runs about twice slower than NTT but does not require any arithmetic property on the order of the group. We explain how this can be adapted to batched KZG commitment proofs and the Bayer-Groth verifiable mixnet used in e-voting.

The 2019 edition of ITU-T X.509 adds three certificate extensions, colloquially called the Catalyst extensions, that let a single certificate carry a second, alternative public key and issuer signature beside the native ones, as a backwards-compatible path for migrating a public-key infrastructure to post-quantum cryptography (PQC). This paper collects the known problems of this multiple cryptographic algorithms (MCA) mechanism and adds several findings of its own. The central and previously known weakness is that a quantum attacker who recovers a single traditional certification-authority key can replace any certificate in a chain by a traditional-only one that a relying party still accepts. We give a precise attack model with a sub-CA and an end-entity-forgery variant to emphasize the inherent problem and propose three mitigating policies for relying parties which offer different degrees of protection and interoperability. As an example, we verify empirically that the susceptibility to this downgrade attack is present in the wolfSSL cryptographic library as a natural consequence. Our further findings concern the construction itself and details of the specification. For one, we analyze the formal violations of EUF-CMA that arise due to the possibility of re-purposing the extension signature to the established signed data format in X.509, which is formally manifest as soon as the alternative key in the extension is also certified as a native key. We show that several further aspects in the ITU-T mechanism remain undefined, which potentially leads to divergent behaviour of clients, and point out that a certificate accepted on its alternative signature alone, as allowed per ITU-T specification, can be invalid under RFC~5280 and potentially exposes an application to arbitrary injected data and even modified signatures chaining it to a certificate chosen by a non-quantum attacker in the positively validated certificate chain.

Fully Homomorphic Encryption for RAM programs (RAM-FHE), introduced by Hamlin, Holmgren, Weiss, and Wichs (Crypto 2019), allows a server to evaluate a RAM program on encrypted data at a per-step cost sublinear in the memory size $N$, whereas standard FHE must read the entire memory for every memory access. In a celebrated work, Lin, Mook, and Wichs (STOC 2023) gave the first, and to date the only, construction from a concrete assumption, namely Ring-LWE. In this work, we construct a RAM-FHE scheme from plain LWE that evaluates each step of a RAM program in $o(N/\log N)$ time. While the scheme is barely sublinear, even such a slight saving over the linear cost of standard FHE was not known to be achievable from unstructured, plain LWE. As Lin, Mook, and Wichs did, we build RAM-FHE by extending a Doubly-Efficient Private Information Retrieval (DEPIR) scheme. Since the only DEPIR from plain LWE, due to Lee (Crypto 2026), relies on a Common Reference String (CRS) that is incompatible with the extension, we show how to remove the CRS and obtain a DEPIR from plain LWE in the standard model, which may be of independent interest.

In a widely publicized recent announcement, Google established a formal 2029 deadline for completing its post-quantum cryptography (PQC) migration---one that deliberately preempts the 2035 deadline set by NIST and the US federal government to complete the deprecation of classical public-key algorithms. Google cited faster-than-expected progress across three fronts: quantum computing hardware development; quantum error correction; and revised estimates of the resources required for quantum computers to break current cryptographic schemes; as motivation for setting an ambitious internal target ahead of the regulatory horizon. This tightened deadline places particular pressure on existing cryptographic protocols that rely on classical key exchange primitives for secure communication. Our work aims to ease this transition by constructing a unified, formally analyzed security framework for migrating classical key exchange constructions to their post-quantum counterparts.

The distinguishing variant $\Delta$LIP of the Lattice Isomorphism Problem underlies the security proofs of a growing family of lattice-based schemes. As the special genus is the strongest efficiently computable invariant of a lattice, such a proof may replace the lattice used by the scheme with a random lattice of the same genus. This raises the question of how hard lattice problems actually are on such random lattices. We answer it, under GRH, with a worst-case to average-case reduction inside any special genus $\mathcal{G}$ of Hermitian lattices of fixed rank $r \geq 2$ over a cyclotomic field $K$ of degree $d$: for each of $\mathrm{(H)SVP}$, $\mathrm{HCVP}$, $(\Delta)\mathrm{BDD}$, $\mathrm{DSP}$ and $\mathrm{DGS}$, solving the problem on a random class of $\mathcal{G}$, drawn from its natural distribution, is as hard as solving it on the worst-case lattice of $\mathcal{G}$, at the cost of a factor $p = \mathrm{poly}(d) \cdot {\det}_{\mathbb{Q}}(\Lambda)^{O_r(1)/d}$ in the approximation factor. The reduction is a random walk on the Kneser $\mathfrak{p}$-neighbour graph of $\mathcal{G}$: neighbours stay close enough to transfer problem instances, while the walk equidistributes quickly, a fact we deduce from spectral bounds for the associated Hecke operators. As an application we give a direct and tight security proof for a minimal LIP-based KEM, resting on two independent assumptions: that the lattice it uses is indistinguishable from a random lattice of its genus, and that $\Delta$BDD is hard on that genus. Unlike existing LIP-based proofs, this requires neither an ad-hoc lattice of the form $q\Lambda \oplus (q+1)\Lambda$, nor the tightness loss caused by the dense sublattice such proofs rely on.

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}$.

Secure multiparty computation (MPC) allows a set of parties to jointly compute a function while keeping their inputs private. Classical MPC protocols assume either a synchronous or an asynchronous network. Synchronous protocols tolerate more corrupted parties but rely on a timing bound, while asynchronous protocols make no timing assumptions but handle fewer corruptions. The network-agnostic model aims to combine the advantages of both. It requires security without knowing in advance whether the network is synchronous or asynchronous, guaranteeing resilience against up to $t_s$ corruptions in the synchronous case and $t_a$ corruptions in the asynchronous case. The optimal corruption threshold for perfect security has been established as $n = 2\max(t_s, t_a) + \max(2t_a, t_s) + 1$, but prior work either falls short of this threshold or requires exponential local computation. In this work, we present the first perfectly secure network-agnostic MPC protocol with polynomial communication and computation complexity under the optimal threshold. Our protocol achieves expected communication complexity $\mathcal{O}((|C|n + (D+C_I)n^2 + n^6)\log n)$ bits for a circuit of size $|C|$ over a finite field $\mathbb{F}$ of size $\mathcal{O}(n)$, depth $D$, and input size $C_I$. Our main technical contribution is a compiler that generates Beaver triples in the network-agnostic setting using synchronous and asynchronous triple-generation protocols in a black-box way. Beyond the cost of the underlying protocols, it only requires $\mathcal{O}(n^2)$ instances of network-agnostic Byzantine agreement.

We present KIFA (Kernel-based Integral Fault Analysis), an integral fault attack framework that mines its balanced properties with the kernel-based miner of Hwang et al. in place of Mixed Integer Linear Programming (MILP). The miner handles only small input structures fixed in advance, and a fault model provides exactly such structures. For DEFAULT, we present attacks at fault penetration (FP) $9$ under a random-position nibble fault and FP $10$ under a random-position byte fault, beyond the prior best integral fault attack at FP $8$. They leave a single master-key candidate under the simple key schedule and reduce the key space to $2^{64}$ under the rotating key schedule. For GIFT-128, we present the first integral fault attacks, at FP $7$ and $8$, against the prior best of $5$. For GIFT-64, we extend the prior best FP $6$ to $7$ with a byte fault, leaving $2^{32}$ master-key candidates. For BAKSHEESH, we extend the prior best FP $7$ to $8$, also when the fault position is uncontrolled.

In reaction to the emerging quantum threat, the National Institute of Standards and Technology (NIST) seeks post-quantum secure digital signature schemes. NIST's ongoing competition recently advanced to the third round, in which the Unbalanced Oil and Vinegar scheme (UOV) is a promising candidate due to UOV's conservative design, small signatures, and performant signing and verification. While these benefits make UOV attractive, the implementation aspects for compact hardware acceleration of UOV remain underexplored. Existing hardware accelerators optimize for performance and have large memory footprints. Yet, constrained devices require compact and low-memory hardware support. At the same time, lowering the memory consumption of UOV without sacrificing performance is challenging due to UOV's large public keys and intermediate results. In addition, low-end devices are prone to power side-channel attacks and benefit from lightweight countermeasures. In this work, we focus on the open challenges of compact UOV hardware acceleration. We design a low-memory UOV architecture with runtime-flexible support of NIST security levels 1 to 5. Our architecture uses a load-balanced 16-lane datapath supporting the critical matrix operations of UOV. In addition, we lower UOV's peak memory consumption using a slicing technique and enable on-the-fly data generation via streamlined data realignment. We also include a pipelined Gaussian Elimination unit and a streaming approach for the large public keys needed for signature verification. In addition to compact hardware acceleration, we defend against differential power analysis attacks through a lightweight blinding countermeasure relying on UOV's equivalent keys. Our blinding requires random non-singular matrices, which are not trivial to sample efficiently in hardware. We therefore assess existing sampling approaches and propose a novel technique based on the lower-upper decomposition of matrices. The resulting blinding solely re-uses existing datapath components and limits the runtime overhead to less than 30%. Compared to existing UOV accelerators, our efficient FPGA design reaches up to 5.1x lower signing and 3.2x lower verification latency, while reducing the memory consumption between 2.2x and 16x.

ECLIPSE is the prime-degree signature construction the PRISM authors describe beside their salted scheme, with that salt, implemented. It exists because a two-dimensional isogeny signature carries an auxiliary isogeny the hash does not bind: the SQIsign round-3 specification says SQIsign cannot be strongly unforgeable for that reason, and PRISM's prime-degree variant has no auxiliary isogeny but was published without parameters, code or a running verifier. This paper is the first implementation, on the SQIsign round-3 primes: a verifier that evaluates the paper's criterion through one isogeny chain and a pull-back, a canonical wire format whose strict decoder recovers one coefficient from two Weil pairings, randomisable keys, two independent implementations that accept each other's signatures, and one key in both roles: a MIKE key pair at the level I prime is an ECLIPSE key pair, the public curve re-encoded and the signing key derived from the MIKE secret alone, with MIKE's code untouched. The only post-quantum precedent is CSIDH with CSI-FiSh, a group action; this is the first shared key in the SQIsign family. Signatures are 206 bytes at NIST level I, within 15 bytes of SQIsign at every matched state. In one session against the SQIsign reference's assembly build, signing is 2.6 times faster and verification costs twice as much, 1.6 times with the public key prepared once. A formal strong-unforgeability (SUF-CMA) argument is left to future work.

Private Set Intersection (PSI) allows two mutually distrusting parties to compute the intersection of their sets without revealing any additional information and has found numerous applications. The approximate matching required by various applications has led to the development of Fuzzy PSI (FPSI), a variant of PSI that identifies approximate intersection elements under a public distance threshold \(\delta\). Reducing computation and communication costs remains an important challenge for FPSI. In this paper, we present a new FPSI protocol, called Mercury, which achieves logarithmic computation and communication complexity with respect to threshold \(\delta\). Our protocol exploits the correlation of the intersection and the point pairs held by the parties, and efficiently identifies the neighboring point pairs by a mixed protocol from homomorphic encryption and secure two-party computation using a "mask-then-compare" technique. We implemented Mercury and evaluated both its sender-private and standard FPSI variants. For balanced two-dimensional inputs, Mercury-SP achieves \(9.0\sim63.9\times\) runtime speedups and reduces communication by a factor of \(8.7\sim26.1\) across the evaluated thresholds and set sizes in the LAN setting, compared to the FPSI protocol by Dang et al. (CCS'25). In the completed unbalanced experiments, Mercury-SP achieves \(55.7\sim132.4\times\) WAN runtime speedups compared to the FPSI protocol by Piske et al. (CCS'25).

The Universal Composability (UC) framework provides a paradigm for security definitions that allows for arbitrary composition, but has been criticized for being unamicable to the concrete security approach, as the meaning of a concrete UC-security statement is hard to interpret in practice. This work aims at alleviating this concern in the context of Password-Authenticated Key Exchange (PAKE): we show that any concrete UC-security statement for PAKE can be easily converted to a concrete game-based security statement, whose real-life meaning is clearer. We also briefly discuss potential generalizations of our result to other cryptographic primitives.

Timed cryptography captures computations that inherently require a prescribed amount of time, even in the presence of parallelism, and has emerged as a central notion due to its broad applications in both practice and theory. A natural question is how timed cryptographic primitives relate to traditional cryptography, in particular to primitives in Minicrypt. Guan and Montgomery (CRYPTO 2024) show that sequential functions do not imply one-way functions (OWFs) via black-box reductions. Their result, however, leaves open whether adding public verifiability (a substantially stronger requirement) suffices to imply OWFs. We study this question via verifiable delay functions (VDFs), which require substantial sequential time to evaluate, yet produce a unique output that is efficiently and publicly verifiable. We show that VDFs do not imply OWFs via fully black-box, relativizing reductions. Combined with prior results showing that VDFs cannot be constructed in the random oracle model, this establishes that there is no black-box implication in either direction between VDFs and OWFs. Our proof develops a new oracle separation technique that combines the random oracle with a carefully designed complexity-theoretic oracle inspired by Kolmogorov complexity.

As zero-knowledge proofs are used in real-world systems, they face threats such as resetting attacks, where an attacker manipulates the prover's randomness. While resettable security has been studied for interactive protocols, whether modern non-interactive systems such as zkSNARKs remain secure under resets is still unclear. This work provides the first systematic study of resettable security for NIZK arguments with three main contributions: - New Definition: We define strong resettable NIZK (srNIZK), which captures adversaries that can selectively reset the prover's randomness, so that some parts are reused while others are generated afresh. This goes beyond the whole-tape resets considered in standard rZK and is motivated by fault injection on secure hardware and incomplete state restoration in virtualized environments. - Concrete Attacks: We demonstrate that widely used NIZK constructions are vulnerable to resetting attacks. We show witness-recovery attacks against (i) Fiat-Shamir-compiled $\Sigma$-protocols (e.g., Schnorr), (ii) succinct proof systems using independently sampled masks (e.g., PLONK and Bulletproofs), and (iii) salted Fiat-Shamir compilations of a broad class of interactive arguments. - Generic Defense: Our simple compiler transforms any NIZK into an srNIZK by modifying only randomness generation, using a pseudorandom function (PRF) secure under partial key resets. This prevents resetting attacks without changing proof size or verification. Our results demonstrate that resetting attacks must be considered in NIZK systems, and provide a simple defense with minor prover overhead.

Vector search on untrusted infrastructure exposes the \emph{query embedding}, a faithful summary of the user's intent. Fully homomorphic encryption can hide the query, but existing approaches still require a full scan followed by ranking of encrypted scores. Scalable private systems avoid encrypted ranking by either sending scores from a single cluster to the client or moving the search to the client, which must first stream the entire vector index for preprocessing. We present Carousel, which instead scores the full corpus under encryption and compresses the results for client-side ranking. The server scores every vector under encryption, raises the scores to a power that preserves their order by magnitude while suppressing all but a handful, and compresses the resulting sparse vector into a logarithmic number of ciphertexts using homomorphic additions alone. Because every vector is scored, Carousel incurs no recall loss from discarding candidates. Since clients hold no database-dependent state, insertions and deletions take effect immediately at the cost of a single vector write. Carousel searches $1$ billion vectors of BIGANN SIFT1B across multiple GPUs and achieves recall@100 of $0.9715$. At $100$ million SIFT vectors, it achieves recall@100 of $0.9845$ with a query latency of $3.735$ seconds on a single GPU.

A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information efficiently intuitively reflects capacities associated with intelligence and learning. Indeed, recent experimental works verify this intuition by showing connections between the capabilities of large language models (LLMs) and their ability as compressors: for instance, Deletang et al. (ICLR'24) demonstrate that LLMs can be used as powerful compressors, and Huang et al. (COLM'24) show that the compression ability of LLMs is highly correlated with their performance on benchmarks for knowledge and reasoning. In this work, we initiate a theoretical study of this connection. Our main result is that LLMs (formally modeled as next-token predictors) are equivalent to monotone (a.k.a. order-preserving) compression algorithms---namely, compression algorithms where the encoding process preserves the ordering of the inputs---in the sense that the one can be constructed from the other while preserving the same error up to an additive gap of 2. We next show that the monotonicity is required for this equivalence to hold if and only if cryptographic (infinitely-often) one-way functions exist. As a direct corollary, we get a cryptographic result of independent interest: the notion of next-bit pseudoentropy (a computational analogue of entropy) of a distribution is equivalent to monotone incompressibility of the distribution. (Previously, it was only known (Haitner et al., ITCS'23) that incompressibility implies next-bit pseudoentropy.)

We present a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP). The algorithm is based on Regev's polynomial-time reduction of the Dihedral Subgroup Problem (DSP) to the modular subset sum problem, but uses a different technique to erase sample bits without use of a subset sum oracle. The algorithm can thus combine with Regev's reduction of lattice problems to DCP, improved by Brakerski, Kirshanova, Stehl{\'e} and Wen, to yield polynomial-time quantum algorithms for various lattice problems, such as finding a polynomial-factor approximation to the shortest vector in an $n$-dimensional lattice (SVP), and the ``learning with errors'' problem (LWE). The algorithm can tolerate a faulty sample rate as high as $1/O(\log{n})$, allowing the algorithm-reduction combination to efficiently solve, for example, SVP with a $\sqrt{n}$ polylog($n$) approximation factor, or LWE instances with $\alpha=\sqrt{n}$ polylog($n$). Note: The proof of Lemma 3 in the first draft incorrectly conflated pairwise independence over the uniform vs. actual distribution on D. The proof has been substantially updated, and now distinguishes clearly between them. Additional note: A new preprint, https://eprint.iacr.org/2026/1693, has been posted claiming to prove that the algorithm in this paper can't possibly work. We're in the process of evaluating it. Additional note October 7/26: The preprint has been updated with a note addressing the claims in https://eprint.iacr.org/2026/1693, as well as clarifications to the proof of Lemma 3 in response to comments by Sam Jaques.

We present two key-recovery attacks against subcodes of generalized Reed–Solomon codes, including alternant and Goppa codes, extending the distinguisher recently introduced by Ghoshal, Ishai, Jain, and Sun. Both attacks recover the full secret key from a single run of the distinguisher. Because the public columns are evaluations of secret polynomials, they lie (up to scaling) on a hidden algebraic curve. The distinguisher holds out one column and finds polynomials vanishing with high multiplicity at the remaining columns, which forces them to vanish identically along the entire curve. From these polynomials, we recover the local geometry of the curve at the held-out column. Two finishing routes then turn the local geometry into the key. In the first route, a bootstrapping step uses this local geometry to recover the tangent planes of the curve at all public columns. From these planes, we construct a minor code, which heuristically turns out to be a full GRS code with the same hidden support, allowing the standard Sidelnikov–Shestakov attack to recover it. Based on a similar idea, the second route uses the local geometry to find two quadratic forms whose ratio at the public columns directly gives an equivalent support. After recovering the support, both routes end by reconstructing the full key, including the support elements removed by any preliminary shortening. We implemented both routes and recovered the secret keys of the TII McEliece challenges TII-173, TII-249, and TII-253, the first two of which had not been solved before, to our knowledge. We also succesfully tested the attacks on randomly generated binary Goppa codes, wild Goppa codes, alternant codes, and GRS subcodes. Under the stated rank and solver assumptions, the whole key recovery costs essentially one run of the distinguisher. In particulat, for Classic McEliece parameters, we estimate this cost at $2^{89.9}$ to $2^{98.6}$ bit operations.

We design a novel robust secret-sharing scheme in the honest-majority setting for $n$ parties that allows constant communication per opening per party when amortized over $\Theta(n)$ simultaneous openings. We attain this scheme by a novel application of list decoding of folded Reed-Solomon codes. This was stated as an open problem by Escudero and Fehr (2023), who could obtain this amortized complexity only for $\Theta(n^2)$ simultaneous openings. Additionally, the dealing of such shares for a random value in a finite field $\mathbb{F}$ can itself be done using an honest-majority MPC protocol using only $O(n^2)$ multiplications between Shamir-shared values. This allows us to build an offline-online fully-secure (GOD) honest-majority MPC protocol, which has a fast online stage with amortized communication cost only $O(n)$ per multiplication gate (assuming the circuit has width $\Omega(n)$) and with no additional overhead, and an offline preprocessing stage with incremental communication cost only $O(n^3)$ per multiplication gate. This improves the previous best protocol in this setting by Escudero and Fehr (2023), which required the circuit to have width $\Omega(n^2)$. Further, the earlier scheme had an incremental preprocessing cost of $O(n^4)$ per multiplication gate. Due to requiring non-responsive rounds, the online stage of these protocols may still be concretely far less efficient than the online stage of the offline-online BGW protocol. Since the BGW protocol only provides security against fewer than $n/3$ malicious parties, we also devise a novel MPC protocol that boosts the BGW protocol's correctness threshold to $n/2$, while maintaining privacy and robustness thresholds at $n/3$, and with minimal online overhead. This is useful in applications, such as elections and auctions, where certification of a correct result is paramount. To achieve this correctness against fewer than $n/2$ malicious parties and to keep the pre-processing cost low, we use our novel robust honest-majority secret-sharing scheme, but only once during a final SPDZ-style attestation.

Dynamic group signatures are commonly formalized in the model of Bellare, Shi, and Zhang (BSZ, CT-RSA 2005), whose security notions are defined relative to specific trust assumptions and registration state. We revisit these assumptions and systematically study which guarantees continue to hold when the trust assumptions on the issuer and opener are considered independently and no trusted registration structure is shared between them. In particular, we show that the meaning of traceability changes substantially in such settings. With a malicious issuer and an honest opener, the natural analogue of traceability only ensures that every valid signature admits an accepted opening; it does not ensure that the resulting identity obtained its membership through a valid join. With a malicious opener, classical accountability guarantees likewise fail to enforce this connection to group membership. We demonstrate this by constructing a scheme satisfying the BSZ-style security notions in which a malicious opener can produce valid signatures that are not associated with any membership established through the join algorithm, even though the issuer is honest. To capture the missing relations between joining, signing, and opening, we introduce three unforgeability-type properties. Certificate-unforgeability binds valid signatures to issued membership certificates. Key-unforgeability requires signature generation to rely on a corresponding member signing key. Opening-unforgeability prevents accepted openings to identities for which no membership was issued. We prove that these properties are logically independent and give a construction satisfying the classical and additional guarantees under mild assumptions. Our results identify precisely which aspects of accountability follow from trusted issuers, trusted openers, or shared registration state, and which must be required explicitly once these assumptions are removed.

Inner-product functional encryption (IPFE) allows the holder of a functional key for a vector $y$ to learn $\langle x,y\rangle$ from an encryption of $x$, and nothing more. Keys, however, accumulate: a coalition holding sufficiently many independent keys recovers the plaintext. We model each institution by the span $W_i\leq\F_q^n$ of its authorized key vectors and show that a coalition $I$ determines the plaintext exactly modulo $(\sum_{i\in I}W_i)^\perp$; for a uniform plaintext it learns exactly $\dim\sum_{i\in I}W_i$ field symbols. The resulting leakage function is a representable and entropic polymatroid. We then study authorization spaces of dimension $r$ whose pairwise intersections have dimension at most $h$. We prove that some coalition of size $c\geq2$ always learns at least $\min\{n,2r-h+c-2\}$ dimensions, and we give a Vandermonde-type construction in which every coalition of size $c$ learns exactly this amount, for all $c$ simultaneously. Hence the largest achievable reconstruction threshold is $n-2r+h+2$, which gives an exact tradeoff between functional diversity and collusion resistance. The optimal configuration is a sunflower, an equidistant subspace code and a generalized arc; its orthogonal complements form a generalized dual arc, and for $r=1$ it reduces to Reed--Solomon secret sharing.

While decentralized identity management systems strive for autonomy, most still rely on centralized mechanisms (e.g., phone numbers or government-issued IDs) to achieve Sybil resistance and prevent fake identity attacks. This article proposes a novel approach for decentralized identity management that ensures robust Sybil resistance, unlike the systems currently in widespread use. Our approach is based on a social graph of connected users. The main novelty resides in pairwise mutual facial biometric verification for connected users and anti-Sybil social graph analysis. By leveraging blockchain technology, zero-knowledge proofs, and privacy-preserving smart contract platforms, the system ensures the uniqueness, anonymity, and privacy of registered users without relying on centralized authorities. We implemented a proof-of-concept prototype of our approach using fast Plonky2 zero-knowledge proofs and evaluated its functionality through simulations on heterogeneous social graph models with 1000 entities. To the best of our knowledge, this is the first work to propose a Sybil-resistant identity system that neither sacrifices decentralization nor privacy and does not rely on any centralized credential issuers.

Modern cryptographic protocols rely on a relatively small collection of standardized hash functions and groups, raising the possibility of preprocessing attacks in which a computationally unbounded offline attacker generates a bounded-size hint that accelerates a later online attack. Blocki and Lee (EUROCRYPT~2022) analyzed the preprocessing security of key-prefixed short Schnorr signatures, where the public key is included in the random-oracle input. Their analysis imposed an a priori restriction on the number of oracle queries made during preprocessing and did not extend to standardized implementations of Schnorr, such as ISO/IEC 14888-3, which do not use key-prefixing but instead reject signatures whose hash challenge is zero. The preprocessing security of these nonzero Schnorr signatures was left as an open question. We resolve this question affirmatively in the ROM+GGM. Moreover, our analysis holds in a stronger model that permits unrestricted offline computation and oracle access, subject only to the size of the resulting hint, as well as adaptive corruption queries during the online phase. Suppressing lower-order terms, an online attacker making \(q\) total oracle queries, including \(q_\mathsf{H}\) random-oracle queries, forges a nonzero Schnorr signature for one of \(N\) users with probability at most $O(\sqrt{Sq^2/p} + q_\mathsf{H} N/2^{\lambda_\mathsf{H}})$, where \(p\) is the group order and \(\lambda_\mathsf{H}\) is the hash-output length. We show that the factor-\(N\) loss is inherent by giving a matching \emph{target-switching attack} with success probability \(\Omega(q_\mathsf{H} N/2^{\lambda_\mathsf{H}})\). By contrast, key-prefixing prevents this attack and the corresponding term in the security bound is just $q_\mathsf{H}/2^{\lambda_\mathsf{H}}$. Consequently, at the same \(\lambda\)-bit security level, key-prefixing enables signatures that are approximately \(\log N\) bits shorter than that of nonzero Schnorr. To support these results, we extend the Bit-Fixing-to-Auxiliary-Input framework of Coretti et al. (CRYPTO/EUROCRYPT 2018) to applications involving multiple idealized primitives. We also address a subtle technical challenge introduced by rejection sampling in the standardized nonzero Schnorr signing algorithm: although long rejection sequences are exceptionally unlikely, a signing query has no deterministic worst-case bound on the number of random-oracle and generic-group queries made by the challenger.

Fully Homomorphic Encryption (FHE) enables one to implement low-round and low-communication complexity Multi-Party Computation (MPC) which is secure in the static malicious corruption model. By expanding on an idea presented in the full version of the FHE-based MPC protocol of Smart (IMA, 2023), we show how to completely remove the need for Zero-Knowledge Proofs-of-Knowledge in that protocol. This simplification makes the final security proof of the MPC protocol much simpler, and more modular. The new protocol makes use of an FHE scheme with an encrypted PRF functionality, and in addition to our main result we formalize the security of such encrypted PRFs and prove the construction of Deo et al. (CCS 2025) secure in this model.

We show an attack on a lattice-based blind signature proposed in Crypto'20. Formally it is a linear hash function based framework with a lattice-based instantiation. We first notice a bug in their security proof of blindness, which is overlooked these years. Then, we develop an attack under the honest key and the honest-but-curious signer setting against the blindness notion of the schemes by exploiting the coorelations between the leaves of the tree. We also discuss how to repair the scheme.

Lattice agreement is a relaxed version of the standard consensus problem: correct processes need not decide the same value, but their decisions must be ``comparable''. Namely, every process proposes a value from a join semi-lattice, and correct processes decide values that (1) lie on a single chain, (2) include their own proposals, and (3) include nothing beyond what was proposed. Lattice agreement has important practical applications, as it underpins atomic snapshot objects and replicated state machines with commutative operations. Yet, the best known protocols decide in $O(\log f)$ rounds, where $f$ is an upper bound on the number of faulty processes. In this paper, we break the logarithmic barrier. Namely, we present Join-IT, a synchronous Byzantine lattice agreement protocol that tolerates $f < n/3$ Byzantine processes and decides in $O\big( \frac{\log f}{\log \log f} \big)$ rounds. Join-IT uses no cryptography whatsoever, and its guarantees thus hold against a computationally unbounded adversary. Perhaps surprisingly, Join-IT is also remarkably simple. It sequentially composes two classical primitives: gradecast, which takes three rounds, and approximate agreement, which, at the precision Join-IT requires, takes $O\big( \frac{\log f}{\log \log f} \big)$ rounds. A single local step finally turns the output of approximate agreement into comparable decisions, at no additional cost in rounds.

We study the Batch Learning Parity with Noise (LPN) variant, where the oracle returns $k$ samples in a batch and draws the noise vector from a joint noise distribution $\mathcal{D}$ over $\mathbb{F}_2^k$ instead of from an i.i.d. product distribution. This model captures a broad range of correlated or structured noise patterns studied in cryptography and learning theory. Consequently, understanding which dependent-noise distributions preserve the hardness of LPN has become an important question. On the hardness side, we design several reductions from standard LPN to Batch LPN. Our reductions identify broader classes of noise distributions $\mathcal{D}$ that preserve LPN hardness, extending the prior hardness results of Golowich, Moitra, and Rohatgi (FOCS 2024). We show hardness in three regimes: 1. If $\mathcal{D}$ satisfies a mild Fourier-analytic condition $\sum_{\mathbf{s}\neq \mathbf0}|\widehat{P}_{\mathcal{D}}(\mathbf{s})|\le 2\varepsilon$, then Batch LPN is as hard as standard LPN with noise rate $1/2-\varepsilon$; 2. If $\mathcal{D}$ is $\Omega(\eta \cdot k 2^{-k})$-dense (i.e., every error pattern occurs with probability at least $\Omega(\eta \cdot k 2^{-k})$) for $\eta < 1/k$, then Batch LPN is as hard as standard LPN with noise rate $\eta$; 3. If $\mathcal{D}$ is a $\delta$-Santha--Vazirani source, then Batch LPN is as hard as standard LPN with noise rate $1/2-\varepsilon$ whenever $\delta\le O(2^{-k/2}\varepsilon)$, improving the previous $O(2^{-k}\varepsilon)$ dependence (in Golowich et al.). On the algorithmic side, we extend Arora and Ge's (ICALP 2011) linearization attack to show that Batch LPN can be solved when the noise distribution assigns sufficiently small probability to at least one point, complementing our second hardness result. We also observe that a nontrivial Fourier coefficient with magnitude close to one yields a simple reduction to low-noise LPN, giving an algorithmic counterpart to our first hardness result. Our reductions are based on random affine transformations and are analyzed through the lens of Fourier analysis, providing a general framework for studying dependent-noise LPN variants.

A recent work by Belohorec et al. (Crypto, 2025) shows that the well-known PST multivariate polynomial commitment scheme is black-box extractable under falsifiable assumptions. They show that a minimally modified (extended) PST is extractable under an assumption ARSDH($n$), and that the canonical PST is extractable under an assumption GARSDH($n$). Both of these assumptions are new and more specialized than the original ARSDH assumption proposed by Lipmaa et al. (Eurocrypt, 2024) to prove black-box extractability of the univariate KZG polynomial commitment. A natural question is whether these assumptions are actually stronger than the original ARSDH assumption. We answer this negatively: we show that both ARSDH($n$) and GARSDH($n$) are equivalent to the original ARSDH assumption. Secondly, we point out a gap in the proof that canonical PST is extractable under GARSDH($n$) assumption.

Anonymity guarantees of privacy-oriented cryptocurrencies are garnering negative attention from lawmakers who view them as antinomic to accountability. Having recognized their potential for innovation, however, regulators may not want to outright ban privacy coins but instead seek a middle ground where financial oversight is effective, and still some privacy is maintained. Mature designs, such as Zcash, Monero, or Firo, are expected to facilitate this through so-called viewing keys that can be disclosed to third parties for the purpose of supervision. This paper studies which privacy guarantees continue to hold once they have been. In doing so, it fills the gap in provable anonymity guarantees for Zcash and Firo under the compromise of the incoming viewing key, but nevertheless shows that malicious parties may happily surrender all their viewing keys and still find very efficient ways of evading financial monitoring. Of independent interest are several shortcomings identified in the prevailing security arguments for Monero.

Deniable secret sharing (DSS; Canetti et al, TCC 2025) is designed for a scenario where an adversary is able to bribe or coerce all shareholders to divulge their shares of a secret. A deniable secret sharing scheme is equipped with a faking function that enables shareholders to produce fake shares that look like real shares, but do not actually reveal any additional information about the secret. Existing DSS constructions require the fakers to jointly compute on their shares, without considering how this computation might be realized. In this paper, we investigate two crucial properties of such computations: the extent to which the fakers themselves learn information about the secret (privacy against fakers), and the number of messages they need to exchange (message complexity). Message complexity can be seen as a measure of faking conspicuousness, if the adversary is able to observe network traffic. We prove that to obtain the strongest notion of DSS, any information-theoretic construction requires the fakers to exchange a non-zero number of messages, which could be large (depending on the access structure). We describe a general construction that matches this lower bound in many cases, e.g. for threshold access structures. Furthermore, for linear secret sharing schemes, we prove that certain unqualified sets must learn the secret as a result of faking. Moving to the computational setting, we describe two constructions which require no interaction beyond the knowledge of who the fakers are. This implies that both inconspicuousness and privacy against fakers are achieved. The first construction requires the share size to be exponential in the number of shareholders, but assumes only a PRG. The second construction has small shares, but assumes virtual black-box obfuscation. We see the latter construction as a stepping stone for a future iO-based instantiation. All of our lower bounds and constructions consider general access structures.

Oblivious RAM (ORAM) is a powerful cryptographic primitive that hides both the contents of outsourced data and the access pattern to the data. However, it offers only a restrictive array-based interface. A principal obstacle to its deployment is building an efficient oblivious dictionary upon it. To build such a dictionary, the state-of-the-art layers an oblivious AVL tree over ORAM, avoids an expensive local position map, but forces every operation to traverse a full root-to-leaf path, costing $\Theta(\log n)$ ORAM accesses. We show this trade-off to be suboptimal, particularly when deployed in a common setup within a trusted execution environment like SGX. There, a small amount of client memory can reduce the position map recursion depth to three levels or less, rendering its overhead relatively small. With low position map cost, probabilistic hash tables prevail as dictionary data structures due to their small, constant number of accesses compared to $\Theta(\log n)$ path traversal of a tree. We implement and analyze oblivious, probabilistic hash tables over Path ORAM, including several different strategies: chaining, power-of-two-choices, stash-less cuckoo, and de-amortized cuckoo hashing. Execution of these algorithms within a secure enclave requires "double obliviousness", which in turn needs strict concrete maximum cost limits for each access that current literature does not provide. We derive these concrete padding parameters bounding the hash table rebuild probability to $\le 2^{-40}$ via large-scale simulation. In an SGX deployment, our constructions outperform oblivious trees by up to $20\times$ for $\mathsf{lookup}$s and $12\times$ for $\mathsf{insert}$s.

Attribute-based credentials (ABCs) enable privacy-preserving authentication by allowing users to prove statements about certified attributes without revealing unnecessary information. However, while ABCs hide undisclosed attributes, the credential verification process inherently reveals the issuer's identity, which can leak contextual information such as a user's nationality or residency. Issuer-hiding ABCs address this by concealing the issuer during verification, but introduce a critical accountability problem: if an issuer is compromised or acts maliciously, previously accepted presentations originating from that issuer cannot be singled out without significant privacy violation and high burden on the central authority performing the inspection. We propose an issuer-inspection mechanism that enables retrospective attribution while preserving privacy. An inspection authority can release keys allowing verifiers to locally identify presentations originating from a specific compromised issuer and a defined time period, without affecting other issuers or earlier time periods. Concretely, we formalize the syntax and security requirements of issuer inspection and provide a generic construction from standard cryptographic building blocks; we further present a concrete pairing-based instantiation using Groth's randomizable structure-preserving signatures, Schnorr-style proofs and an adaptation of Gentry's anonymous identity-based encryption. Our analysis of computational and communication costs indicates that the proposed functionality remains practical for realistic parameter choices.

The complexity of many algebraic algorithms for solving non-linear polynomial systems of equations over finite fields, such as the XL (eXtended Linearization) algorithm or variants of the F4/F5 algorithms, is directly determined by the so called degree of regularity. In essence, we can form the Macaulay matrix at this degree, which can be thought of as the linearization of monomial multiples of the polynomials from the problem instance, and then solve the obtained linear system. The degree of regularity guarantees we can solve the system, however, it is a rather coarse parameter. This means that, sometimes, in order to provably show that we achieve overdeterminess, we end up with a heavily overdetermined Macaulay matrix which unnecessarily increases the computational cost. To reduce this coarseness, and thus avoid the unnecessary computational cost, we propose a technique for ``smoothing'' the degree of regularity that can be seen as operating at a degree in-between two integer values. Instead of the full Macaulay matrix, we consider specific submatrices that we show are sufficient to solve the given system. Under a mild assumption that generalizes the notion of semi-regularity, which we experimentally verify for a range of parameters, we show that our approach smooths the complexity of XL for the MQ (Multivariate Quadratic) problem. Finally, we apply our results to a recent UOV attack and demonstrate improvement of a few bits.

Falcon, a lattice-based signature scheme selected for NIST post-quantum standardization, is notable for its compact signature size alongside a complex signing procedure involving extensive floating-point arithmetic. Prior side-channel attacks on Falcon signing, while demonstrating vulnerabilities, have consistently required a large number of power traces for successful key recovery, which limits their real-world practicality. This paper presents a new single-trace attack on the Falcon signing procedure. We exploit side-channel leakage in the FP conversion and identify additional leakage in the FP multiplication at the first layer of the Fast Fourier Transform (FFT) during secret key expansion. By combining these leakages, we progressively partition the secret-key coefficients and establish a linear system to recover the entire key. Our attack is particularly devastating for the \texttt{sign\_dyn} design---the memory-efficient implementation widely adopted in cryptographic libraries---which executes key expansion during every signature operation. We validate our attack on an ARM Cortex-M4 microcontroller, achieving a 100\% key recovery success rate with just one power trace for Falcon-512 across the baseline \texttt{-O0}, size-optimized \texttt{-Os}, and highest \texttt{-O3} compilation levels of the PQClean implementation. Crucially, we also evaluate the Falcon team's highly optimized embedded assembly (ASM) implementation. Despite its reduced leakage, our adapted multi-trace attack successfully recovers 53 out of 100 test keys with only 10 traces. This marks the first successful single-trace attack at the \texttt{-O3} level and the first practical attack against the embedded ASM Falcon. Furthermore, our in-depth assembly analysis of these vulnerabilities provides critical guidelines for designing more secure, hardened embedded assembly implementations.

Proof-of-useful-work (PoUW) certifies computational hardness, not utility. We separate three properties of a work receipt: work soundness ($\mathsf{W}$), job binding ($\mathsf{B}$), and demand exogeneity ($\mathsf{E}$), the last defined relative to an attacking coalition. Job binding is cryptographically achievable; demand exogeneity is not derivable from endogenous receipts. Payments between coalition-controlled requesters and workers are recoverable transfers, so no attack-cost lower bound may count their nominal value (Lemma 1). Under free pseudonyms and endogenous observation, receipts cannot certify $\mathsf{E}$ (Theorem 1); against a stated class of provenance estimators, evasion costs the equivalent of an implicit tax on simulated volume, below one percent at the parameters we consider. A mechanism that must stay safe and live on the zero-demand path needs an election path independent of demand-derived receipt weight (Proposition 4). The quantitative consequence is a sizing rule. A receipt boost that a coalition can realize by paying itself must be capped against the demand-independent floor (Corollary 4), and pricing the boost with a burn changes its cost but not this cap (Corollary 5): a burn-priced boost capped at $\kappa$ times a participant's own stake lowers the floor share an attacker needs from $\tau$ to $\tau/(1+\kappa(1-\tau))$ once honest demand vanishes. In a stylized free-entry model, fork-independent salvage value of useful outputs leaves security neutral, lower, or higher depending on salvage asymmetry and demand. An irrecoverable tax on every settled payment makes the burn the security resource. We know of no production chain that weights leader election by endogenously attested demand, so the results constrain a design space; the deployed systems closest to it, Filecoin and Gridcoin, keep a demand-independent floor. Receipts suit payment, collateral, loss allocation, and a bounded, priced election boost. They cannot carry the leader-election floor.

Secure multi-party computation (MPC) enables $N$ parties to jointly evaluate any function over their private inputs while preserving confidentiality. While decades of research have produced concretely efficient protocols for small to moderate numbers of participants, scaling MPC to thousands of parties remains a central challenge. Most of the existing approaches either incur per-party costs linear in $N$, due to pairwise computations, or rely on heavy cryptographic tools such as homomorphic encryption, which introduces prohibitive overheads when evaluating Boolean circuits. In this work, we introduce a new lightweight approach to designing semi-honest MPC protocols with per-party, per-gate computation and communication costs that are independent of $N$. Our construction leverages the Sparse Learning Parity with Noise (Sparse LPN) assumption in the random oracle model to achieve per-gate costs of $O(k^2 \cdot c(\lambda))$ computation and $O(c(\lambda))$ communication, where $k$ is the sparsity parameter for the Sparse LPN assumption and $c(\lambda)$ is an arbitrarily small super-constant in the security parameter $\lambda$. Assuming Sparse LPN remains hard for any super-constant sparsity, this yields the first semi-honest MPC protocol in the dishonest-majority setting with per-party, per-gate costs bounded by an arbitrarily small super-constant overhead in $\lambda$. Structurally, our MPC instantiates a Beaver-style MPC with the required correlations generated efficiently. Departing from prior approaches that generate Beaver triples either silently (Boyle et al., 2019; 2020; 2022) or through homomorphic computation (Damgård et al., 2012), our focus is on efficiently generating a weaker correlation. In particular, using Sparse LPN we show that if we relax the correctness requirement in generating random Beaver triples to permit a tunably small inverse-polynomial error probability, such triples can be silently generated with arbitrarily small super-constant per-party computation. We then show that such correlations can be used in an efficient online phase similar to Beaver's protocol (with a tiny super-constant factor blow-up in communication).

We study the randomness required to share possibly correlated secret bits among parties connected by a graph. A dealer places shares on the edges so that each party can recover its own secret from its incident shares and learn nothing about the others beyond what its own secret reveals. Anilkumar et al. completely determined the minimum randomness required for three binary secrets. We extend this study to four secrets and obtain results for arbitrary numbers of secrets on general graphs. For four parties on a complete graph, we determine the minimum number of random states for every set of permitted secret combinations: the possible values are one, two, three and four. We also characterize when one random bit suffices on an arbitrary graph.

Secure weighted aggregation is essential for privacy preserving federated learning, yet existing schemes do not simultaneously provide post-quantum security, resilience to client dropouts, verifiability against malicious servers, and resistance to bounded collusion between the server and clients. This paper presents PQ-DVSA, a verifiable secure aggregation scheme that provides post-quantum security and resilience to client dropouts. PQ-DVSA protects both clients’ updated local models and aggregation weights, enables reconstruction of the aggregate mask for the active set after client dropouts, and allows clients to verify the server’s aggregation result under bounded collusion. Experimental results show that PQ-DVSA achieves learning performance comparable to exact weighted aggregation and reduces the runtime for encrypted submission at each client by up to 96% compared with SWAS, the closest existing scheme to PQ-DVSA.

We advance the study of best-possible security guarantees of two-round secure multiparty computation in the plain model. While Goel et al. (TCC '21) showed the infeasibility of Identifiable Abort in two rounds in the plain model with a standard honest majority (i.e. $t < n/2$), the effect of relaxing the setting to an honest supermajority has not been established. In this work, we close this gap. When $t < n/3$, we show that two rounds are sufficient to achieve identifiable abort. Notably, ours is the first two-round general-purpose MPC construction in the plain model tolerating more than one corruption that achieves a guarantee stronger than unanimous abort. We obtain our construction via a new compiler that lifts any protocol with unanimous abort to one that achieves identifiable abort. A core building block for our compiler is Oblivious Public Transfer with Intermediaries (OPTI), a new primitive that we introduce which may be of independent interest.

Secure multiparty computation with provable identifiable selective abort (PISA), introduced by Kondi and Ravi (CCS 2025), guarantees that every honest party either obtains the computation output or a certificate that convinces any external auditor that a specific party cheated. Crucially, honest parties need not agree: some may get output while others receive evidence of cheating. In contrast, secure computation with identifiable abort (IA) requires just such unanimity; however, in the event that an honest party doesn't get output, it need merely be able to point to a cheater - not to prove their guilt. Secure computation with IA classically requires broadcast. Kondi and Ravi demonstrated that secure computation with PISA, on the other hand, can be built over point-to-point channels alone. While PISA is feasible exactly when guaranteed output delivery is, i.e. for $t < n / 2$, the best known construction over point-to-point channels requires six rounds. We settle the round complexity of PISA for all but a narrow band of thresholds. We prove that two rounds are impossible for $t \geq n /3$, even with arbitrary setup and computational assumptions; we give a three-round protocol for any $t < n/2$, which is therefore round-optimal for $n / 3 \leq t < n/2$; and we give a two-round protocol for $t < n/4$. The two-round protocol introduces a new primitive called one-or-nothing secret sharing with omissions.

DAG-based Byzantine fault-tolerant (BFT) consensus lets all validators propose concurrently, and uncertified designs such as Mysticeti skip per-block certification to achieve low latency. In existing partially synchronous round-based DAGs that use only hashing and standard signatures, however, every block references a quorum of previous-round blocks, so block metadata grows linearly with the committee size and, even in the happy case, the metadata communicated per round grows cubically. We present Bluestreak, a partially synchronous uncertified DAG BFT protocol that sparsifies block metadata using only hashing and standard signatures. A non-leader block carries at most two references, to its author's previous block and, optionally, to the previous leader; the leader reference is a vote. It may also name the leader of two rounds earlier as certified, a claim that its author has seen $2f+1$ votes for it. Only the single leader block per round references the latest block it knows from each validator, so committing it orders their chains. Because a sparse ancestry cannot justify the claims it carries, a node references a block only after verifying every claim in the block's history, and a pull-based pacemaker fetches the blocks and votes it is missing. We prove safety and liveness under partial synchrony and show that, in the happy case, block metadata amortized over a round is constant, per-round metadata communication is quadratic in the committee size, and, under idealized timing, the average end-to-end latency equals Mysticeti's: 4.5 message delays. In experiments with emulated ten-region wide-area delays, Bluestreak cuts average block metadata from Mysticeti's 13 KB to about 320 bytes at 400 validators, and matches or beats its median end-to-end latency at every committee size from 10 to 400.

Retaining intermediate values can shorten a quantum cipher oracle but increase the logical qubits required by each parallel search worker. We propose a joint selection procedure for 80-round and revised 112-round CHAM-128/128 under a fixed global logical-qubit budget. It selects retained round addends, feasible integer allocations of search workers, and execution plans to minimize maximum scheduled logical depth subject to a target probability of recovering and accepting the original key. We evaluate libraries of 83 and 99 retention sets against a baseline whose retention choices are restricted to no retention and full retention. Both comparison groups use the same implementation and execution rules. Across 654 budget, success-target, and Toffoli-decomposition conditions per round count, the mean depth reductions are 11.12% and 8.39%, with strict improvements in 606 and 588 conditions, respectively. The selected retention count need not increase with the budget, and a fixed-circuit capacity discontinuity can disappear after reselection. The findings concern the measured libraries under an ideal-cipher success model and logical-layer costs.

Origami is a multivariate signature scheme submitted to the NGCC round-1 public-key call. We show that the submitted bilinear construction is a Rainbow-type scheme whose central map is exposed. The verification map is the layered signing map in a public coordinate order. The public key therefore gives an equivalent secret key, allowing signature forgery at about the cost of one verification (about $0.01$s at Origami-128). Our attack exploits this public layered structure and succeeds against the unmodified reference implementation on all four parameter sets and the official test vectors. We also refute the security proof's inversion assumption in a bilinear independent-coefficient model. The hidden local algebras introduced by Origami do not prevent the attack. They raise a separate problem: the specification treats constrained matrix coordinates as independent, and honest signatures lie in a proper subspace.

Secret-shared SQL-style join is a fundamental building block in secure collaborative data analysis. In practice, join operations frequently involve duplicate keys, giving rise to one-to-many (Join-OM) and many-to-many (Join-MM) relationships. Supporting such joins requires obliviously materializing all matching row pairs. Existing protocols achieve this in two costly ways: they either perform oblivious sorting over a larger expanded input or rely on multiple aggregation trees that incur additional logarithmic rounds. In this work, we present highly efficient protocols for Join-OM and Join-MM over secret-shared databases in the standard semi-honest setting. Our core contribution is Oblivious Sort Expansion (OSE), a novel constant-round protocol that may be of independent interest. Rather than obliviously sorting the expanded input from scratch, we sort only the original input and use OSE to derive the sorted order after expansion. For Join-OM, OSE eliminates the redundant sorting overhead introduced by input expansion in the state-of-the-art protocol by Asharov et al. (CCS 2023). For Join-MM, we combine OSE with local linear operations to obtain an aggregation-tree-free Join-MM protocol. Experimental results show that our protocols consistently outperform prior protocols, reducing both runtime and communication costs by approximately $27\%$ and $65\%$ for Join-OM and Join-MM, respectively.

Post-Quantum Cryptography is now in its deployment phase. Amongst the threats encountered in real-world applications is Side Channel Analysis, a cryptanalysis branch relying on the study of physical leakages from unsecured implementations. However, the FALCON post-quantum signature includes non-linear functions on real numbers, and applying the generic masking countermeasure to these functions has only been recently studied. In this work, we use convergent sequences to approximate the function and a minimax polynomial to compute the first term of the sequence. The method is applied to the computation of the inverse square root and the square root in FALCON, two operators for which masking has not been investigated before. A theoretical analysis of the security in the t-probing model using the NI criterion and its variants is proposed. Compared to the existing state-of-the-art using the same approach which covers the masked inversion for emulated floating-point implementation, this paper is generic and works with any representation and precision for real numbers.

Notions like identity-based encryption (IBE) and attribute-based encryption (ABE) augment public-key encryption to provide fine-grained access control to encrypted data. In these settings, there is a single master public key that anyone can encrypt to. Users in turn possess different secret keys that determine which ciphertexts they can decrypt. The standard, or full, security notion for these schemes stipulates that a ciphertext computationally hides the message if the adversary does not possess a key that is allowed to decrypt. A relaxed notion of security that is often much easier to achieve is bounded-collusion security, where we only require security against adversaries that have an a priori bounded number of keys (and the scheme parameters can grow with this bound). For instance, it is known that vanilla public-key encryption implies bounded-collusion IBE (and ABE) whereas there is a black-box separation between public-key encryption and fully secure IBE. In this work, we develop a general methodology to upgrade a pairing-based encryption scheme with bounded-collusion security into one that is fully secure. We illustrate our methodology by applying it to two main applications: batched IBE and multi-authority ABE. First, in the case of batched IBE, we obtain the first pairing-based construction of batched IBE where there are no tag restrictions (in the generic bilinear group model). All previous pairing-based batched IBE schemes require attaching a tag to ciphertexts and secret keys, and moreover, restrict the adversary to an a priori bounded number of secret keys for each tag. Second, we use our techniques to obtain a multi-authority ABE scheme that supports conjunction policies in the generic bilinear group model. This is the first pairing-based scheme that makes fully black-box use of the group. Previous pairing-based multi-authority ABE schemes require a random oracle whose output is a group element (which implicitly assumes the underlying group supports a procedure for explainable oblivious sampling).

We study the computational problem $\mu$-SVP, in which the goal is to find a $\mu$-approximate shortest non-zero vector in a lattice $\mathcal{L}$, for constant approximation factors $\mu > 1$. Prior to this work, there was a large gap between the fastest algorithms for this problem whose correctness had been proven and the fastest heuristic algorithms, whose correctness has not been proven (but which seem to work well in practice). We construct a novel sieving algorithm that combines the key tool used in the fastest heuristic sieving algorithms (faster nearest neighbor subroutines) together with the perturbation argument used in sieving algorithms with proven correctness. The result is an algorithm whose correctness we prove and whose running time depends on a simple geometric quantity: the maximal size of certain spherical codes. Under a reasonable assumption about the maximal size of spherical codes, our algorithm's running time is roughly $2^{0.3066n}$ for large constants $\mu$, which is quite close to the best heuristic running time of roughly $(3/2)^{n/2} \approx 2^{0.2925n}$ and much faster than both the previous best known algorithm with proven correctness, which runs in time roughly $2^{0.802n}$ [Liu, Wang, Xu, and Zheng, 2011] and the very recent concurrent and independent work showing a $2^{n/2}$-time algorithm [Hhan, 2026]. (However, the algorithm of Hhan also solves $\mu$-SVP for $\mu =1$, while our algorithm only works for large constant $\mu$.) Using the best proven upper bound on the size of such spherical codes (which is almost certainly quite loose), we obtain a running time of roughly $2^{0.6078n}$, which is much better than the previous best work but notably slower than the concurrent work of Hhan.

Classical deep learning for differential cryptanalysis requires millions of ciphertext pairs, rendering attacks infeasible or easily detectable. This work overcomes this data limitation by introducing quantum differential distinguishers, enabling a practical attacker model where executing few queries is feasible. We design these distinguishers via quantum machine learning based on variational quantum circuits. To address circuit design challenges, we propose QuantumScouter, a reinforcement learning method that discovers compact quantum circuits. Unlike prior work, QuantumScouter explicitly targets metrics like gate count and circuit depth, producing circuits suitable for noisy intermediate-scale quantum hardware. We apply QuantumScouter to the SPECK32/64 and SIMON32/64 ciphers. The models are trained to distinguish ciphertext pairs possessing a meaningful differential from completely random pairs. For SPECK, our approach achieves $0.80$ accuracy, outperforming the $0.53$ of prior work while reducing required qubits from $16$ to $6$. For SIMON, we establish a novel quantum baseline with $0.75$ accuracy. Notably, under a restricted regime of merely $400$ training samples, classical deep learning models struggle. A simple MLP with $361$ parameters fails to capture differential characteristics, resulting in an accuracy of $0.51$, while a deep ResNet with $64{,}737$ parameters overfits to yield an accuracy of $0.55$. In stark contrast, our data-efficient quantum distinguisher extracts meaningful features using only $49$ gates, maintaining $0.80$ accuracy.

Threshold signatures are widely deployed in decentralized asset custody and blockchain infrastructure to eliminate single points of failure. In these systems, an attacker can adaptively corrupt committee members based on public membership and protocol transcripts. Recent cryptanalysis shows this threat is concrete: schemes exposing per-party key commitments enable practical forgeries for committees of roughly 200 signers at the cost of just one minute of the global Bitcoin hashrate. While a new generation of signing schemes defeats this attack by hiding individual key shares, every distributed key generation (DKG) protocol used in practice exposes this information, voiding the adaptive security of any scheme built on top. Trusted dealers avoid the leakage but reintroduce the single point of failure that threshold cryptography exists to eliminate. True adaptive security must therefore span both key generation and signing. We present Janus, the first DKG suite to achieve this end-to-end guarantee. Janus serves as a drop-in replacement for a trusted dealer in threshold schemes, hiding all key shares while outputting a standard DLog public key compatible with existing verifiers, wallets, and smart contracts. Assuming secure erasures, we prove security against an adaptive adversary that corrupts members mid-protocol and controls a dishonest majority. We also show that Janus directly supports a variety of DLog-based primitives, including threshold Schnorr signatures and oblivious pseudorandom functions. Our suite includes Janus2R, which achieves an unbiased key in two rounds, and Janus1R, which completes within a single round by tolerating an additive key shift. When a node misbehaves, both variants generate a 259-byte universally verifiable proof for automated on-chain slashing, and both naturally allow committees to proactively refresh their shares without changing the public key. Our open-source Rust implementation completes key generation for a 16-node intercontinental committee in 310 ms and scales to 512 nodes.

Candidates for post-quantum migration carry additional costs compared to their pre-quantum counterparts, especially for signatures, and they lose attractive properties of schemes such as BLS: homomorphism, and hence direct signature aggregation. We propose a methodology through which a pre-quantum primitive may still be securely used past Q-day (the advent of quantum computers) in settings where forgery of signatures or cryptographic proofs need only be prevented for a bounded lifespan (transient quantum security). The idea is to bind a fresh, ephemeral, ordinary pre-quantum key to a long-term post-quantum identity once per lifespan window, so a forgery under the fresh key is useful only for that window, and to derive the fresh key so that its exposure never leaks the long-term secret. Our main case study is an application to Ethereum consensus, conditional on stated registration, inclusion, and slashing-evidence rules. The construction keeps ordinary BLS aggregation and needs no SNARK prover. Each same-message aggregate is a single 96-byte signature, and each validator publishes 592-688 bytes of reveal data per epoch. Each epoch key is bound to a seed derived from a checkpoint finalized before that epoch, so a committed key is opened under exactly one seed. We reduce unforgeability in the public-tag game to co-CDH' in the ROM and QROM, with explicit probability and resource costs. Transient quantum security requires hardness at the resulting budget; later checkpoint-derived seeds also require the stated public-environment condition. Transient security requires forgery resistance for the whole interval in which an exposed key can affect the chain. Under Ethereum's attestation inclusion rules, that interval is nominally two epochs plus the reveal lead time under prompt processing. Historical slashing and delayed-fork acceptance need additional rules, which we state as preconditions. Published quantum attack costs inform the resource discussion. They do not establish a security lower bound for this construction. We also provide a formal model and security analysis for the construction, and, of independent interest, a new analysis of BLS where the secret key is sampled similarly to the Dodis-Yampolskiy VRF (IACR PKC 2005) and the adversary is given a related group element as leakage.

Based on techniques discovered in the better.codes autoresearch project, we show that Reed-Solomon codes of rate $\rho$ and block length $n$ over a field of sufficiently large characteristic, have $C\cdot n$ list size bound when requiring fractional agreement $\alpha$ with a received word; where $C,\alpha$ are constants depending only on $\rho$ and $\alpha<\sqrt{\rho}$. This complements the recent breakthrough results [BCPZZ26,Jeronimo26] achieving $n^c$ list size bounds with agreement $\rho+\epsilon$ for any constant $\epsilon>0$ with an unspecified constant exponent $c$.

We present Quintus, information-theoretic BFT protocols for tolerating $f < n/5$ Byzantine faults among $n$ parties. We present two protocols: The first protocol, Quintus-Fixed, is in a fixed view regime where views advance at a cadence $3\Delta$ time. This protocol incurs a good-case latency of $2\delta$ time where $\delta$ indicates actual network delay and message complexity of $O(n^2)$ in a view. The second protocol, Quintus-Responsive, is an optimistically responsive protocol with good-case latency of $2\delta$ time, $O(n^2)$ message complexity, and $2\Delta + 2\delta$ worst-case view latency where $\Delta$ denotes a pessimistic network delay parameter under synchrony.

A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model. To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most $T$ oracle rounds, and security against polynomial-width quantum adversaries of depth $o(T)$ for every polynomially bounded delay $T$, resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).

Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes -- a quantum analog of the well-studied LPN problem -- is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practical: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE, and our OT is round-optimal. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suit of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.

Batch Private Information Retrieval (Batch PIR) allows a client to privately retrieve multiple entries from a public database while amortizing query costs. However, concretely efficient schemes typically rely on per-client server state, such as client-specific evaluation keys, which makes queries linkable across sessions and complicates deployment. In this work, we initiate the study of doubly-stateless Batch PIR, where the server stores no per-client state and the client maintains no database-dependent hint. For this model, we construct a communication-efficient scheme that substantially reduces communication compared with the natural baseline of adapting off-the-shelf Batch PIR schemes by sending fresh evaluation keys with each batch query. The core technical ingredient is a single-key RLWE unpacking procedure that replaces the traditional tree-based approach, which requires logarithmically many Galois keys, with a linear walk over a cyclic Galois subgroup requiring only a single Galois key.

Proposer-Builder Separation (PBS) in Ethereum aims to improve decentralization and scalability by offloading block construction to specialized builders, but its current MEV-Boost implementation relies on trusted relays, introducing centralization as well as security and performance concerns. We propose Decentralized Proposer-as-a-Service (DPaaS) to eliminate relays while preserving compatibility with Ethereum’s consensus layer by distributing the combined proposer and relay roles across Proposer Entities (PEs) running in independent Trusted Execution Environments (TEEs). DPaaS presents itself to Ethereum as a single validator using threshold BLS signatures, while a new Byzantine broadcast protocol decentralizes the auctioneer role with censorship-resistance and availability-backed guarantees. Our evaluation, deployed across four independent cloud hosts and driven by real-world traces, shows that DPaaS achieves $\leq 6$ ms bid processing latency, $68.7$ ms latency from the end of auction to block proposal, and $3.3\%$ more MEV earnings – demonstrating that DPaaS can offer security, decentralization, and trustworthiness benefits while providing strong performance.

Deploying memory-heavy post-quantum cryptography (PQC) at the smart grid edge threatens real-time substation determinism, directly conflicting with the strict $\le 3 ms$ GOOSE tripping window of the IEC 61850 standard. To resolve this architectural tension, we propose a security-aware, hardware-in-the-loop benchmarking framework on the dual-core Xtensa LX7 (ESP32-S3) SoC running FreeRTOS. To prevent inter-core resource contention, the framework employs an asymmetric task-isolation design, pinning cryptographic operations to Core 1 while leaving Core 0 responsive to line-rate grid interrupts. Additionally, we define a programmatic heap-auditing methodology to model how heap_4.c maps key-state allocations across physical DRAM fragments while preserving the primary 128 KB contiguous system heap. Finally, we formulate an analytical latency model of the external Octal-SPI PSRAM interface, mathematically characterizing the CPU stall overhead ($C_{\text{stall}}$) induced when side-channel masking forces secret polynomial shares to spill over the external bus during non-sequential Cooley-Tukey NTT strides. This framework provides a rigorous methodology to characterize micro-architectural trade-offs, enabling utility engineers to plan post-quantum migration pathways without violating real-time grid constraints.

Recent Bitcoin bridge designs rely on verification of succinct proofs to process withdrawals. This requires off-chain garbled circuit evaluation of a succinct proof, the input labels for which must be encoded on chain in a manner compatible with malicious security. We assess the post-quantum vulnerability of these cryptographic components, and examine the costs of secure alternatives. Circuit sizes for post-quantum proving systems can be made smaller than the current pairing-based baseline, but at the cost of significantly higher proof sizes that incur greater cost and require multiple Bitcoin blocks to encode. We suggest avenues of future research to improve efficiency of proofs, circuit representations, and input encodings.

The paper presents the first-ever differential neural cryptanalysis of the Latin Dances family of Salsa, ChaCha, and Forró. First, we provide a systematic differential-neural study of the ARX stream cipher ChaCha. We train and compare six neural architectures, viz.: Gohr's residual network, DBitNet, an Inception network, an MLP-ResNet, an SE-ResNet, and a self-attention network on a 3-round reduced version of ChaCha. We train in both the classical single-pair setting and a multi-pair setting that combines up to sixteen ciphertext pairs through a log-odds rule. We extend the study for breadth to other ARX ciphers, Salsa, *ChaCha, and Forró. We provide the first-ever distinguisher for 4.5 rounds of Salsa with accuracy of 0.53 for one pair and 0.60 for 16 pairs. Also, for Forró the first-ever distinguisher for 1.25 rounds of Salsa with accuracy of 1 for single and multiple pairs. We also introduce a family of experimental round-1-XOR variants (\emph{XOR-1}) that isolate the contribution of the first round's diffusion to distinguishability. Finally, we investigate the trained 3-round ChaCha distinguisher with four explainability experiments and show that, although the output difference is its dominant feature, it is not a pure differential distinguisher: its decision is interpretable as a learned mixture of round-1 truncated differentials, five of which already account for $99\%$ of the high-confidence ciphertext pairs.

The Lattice Isomorphism Problem (LIP) is a relatively new problem that has gained increasing attention in the field of lattice-based cryptography. It is the underlying hard problem of the Hawk signature scheme, which has been submitted to the second NIST call for post-quantum signatures. In this paper, we propose to study the security of LIP in the presence of partial information on the secret solution, which can be obtained through side-channel attacks or by design. We propose a new cryptanalysis approach for LIP that embeds it into a shortest vector problem (SVP) based on a different lattice than the one considered in the specifications of Hawk, allowing to integrate hints. We also introduce conversion techniques that transform hints expressed on arbitrary linear combinations of the secret key coefficients into hints on the target lattice, enabling the integration of a broader class of linear leakages on sensitive values. We implement our attack and predictions using the LeakyLWEEstimator tool (Crypto 2020) and obtain concrete security estimates for Hawk in the key-recovery setting. We also observe that Hawk signatures carry intrinsic information about the secret key and show that this can be exploited as a source of hints, yielding a refined key-recovery complexity, thereby eroding the original security estimates. For example, we estimate a security loss of around 11 bits for Hawk-1024. Finally, we apply our framework to side-channel analysis results on Hawk, solving an open problem raised in a recent analysis (TCHES 2024) and discuss further attack paths enabled by fault-injection techniques. We believe that this new cryptanalysis approach for LIP and the integration of hints provide new insights towards a better understanding of its security.

Post-quantum (PQ) migration is usually tracked per asset, with Mosca’s inequality and a share of “migrated” systems. For a flow of sensitive data, the relevant questions are different: is every session that carries it keyed by a quantum-safe secret, what evidence supports that claim, and what can an assessor establish from outside? We propose an assessment method whose unit is the data path and whose verdicts are tied to evidence. Key lineage is an algebra on break dates: a derived key falls when all its inputs fall, and a key falls when any of its copies falls. This covers TLS 1.3 resumption, key transport and keys wrapped several times. A verdict is a pair of strong-Kleene evaluations, one taking claims at face value and one admitting only claims that meet an evidence policy; the reachable pairs form four ordered labels. We characterize what an external probe can establish. A probe of the server decides a hop only if the server enforces PQ or cannot negotiate it; enforcement must be shown by a negative test paired with a positive control; a server that resumes sessions without a fresh key exchange leaves the layer undecided; and behind a load balancer the confidence of a negative test follows a sampling bound only under an independence assumption that a default balancer violates. We implement the probe and validate its inference rules on 22 configurations of five server stacks built on three TLS libraries, including confounders and a heterogeneous load balancer. The same nominal configuration yields different states across implementations, so declared configuration cannot replace runtime evidence. A protocol for an internet-scale enforcement study accompanies the paper

We give a new framework for constructing post-quantum protocols based on graded monoidal actions. An essential difference between the graded monoidal action framework and the cryptographic group action framework is that our higher-rank problems give rise to infinite structures, where elements do not admit inverses, while cryptographic group actions are finite by definition. Nevertheless, we show that the hard problems for cryptographic group actions reduces to the corresponding family of hard problems for graded monoidal actions. However, the main motivation is that for general graded monoidal actions, the relevant problems admit no known subexponential quantum attacks, while still having enough structure to formulate some protocols based on cryptographic group actions, such as the Diffie-Hellman key-exchange. Our framework can, to the extent we make clear in the paper, be instantiated with the module-action on oriented principally polarized abelian varieties (PPAV's), generalizing the class group action on oriented elliptic curves. Although the theory involving the module-action is quite involved, the formulation of a graded monoidal action is strikingly simple, making it a suitable abstraction for constructing protocols in, which can then be instantiated with the module-action.

Belkheyar et al. introduced ChiChi as the even-dimensional, low-latency nonlinear core of ChiLow (Eurocrypt 2025), and Andreoli et al. generalized it into the SWAP and 4-cycle families (ToSC 2025/3), conjecturing five bounds on the linear height and component linear nullity of their inverses, supported by experiments in small dimensions. We settle all five conjectures: Conjectures 1–4 hold for every admissible branch length, and Conjecture 5 is false. In addition, we derive consequences for ChiLow's design and correct one value in the data of Andreoli et al.

We define an asynchronous ledger service ($\mathsf{AsyncLS}$) in the IITM-based universal composability (iUC) framework. The wallet-based service exposes a general state machine for a decentralized ledger-based application through registration, reads of committed application state, authenticated submission, and status queries with immutable final results. Each logical request binds the user's authorization to a finalized checkpoint and the applicable execution context. A confirmed outcome identifies the first eligible transaction and records application success or rejection. Strict expiry requires complete processing beyond the eligible height window with no recorded outcome, and certifies that the request has no application effect. We construct a protocol $\mathbf{\Pi}_{\mathsf{AsyncLS}}$ that realizes the ideal service using four components: Wallet, Relay, Adapter, and Replay. The proof separates the service construction from the implementations of Relay and Adapter while preserving ledger, clock, authentication, and setup interactions. We prove realization for the trusted and local implementations under their respective execution and trust assumptions. We use the service to construct an ORDI interactive payment and a parameterized execution layer above transaction ordering. These examples distinguish the ledger interaction protocol from the application state and effects exposed by the service. Each use requires the stated authorization, setup, ledger, clock, authentication, and ledger-effect assumptions.

We introduce MIKE (Module Isogeny Key Exchange), a post-quantum NIKE (Non Interactive Key Exchange) whose security relies on the CDH problem for the rank-$2$ Hermitian module action on supersingular elliptic curves. For NIST level~$1$, MIKE has very compact public keys of 80B, and using our constant time C implementation, the key generation takes 0.65ms and the shared secret takes 4.9ms (including key validation) on a AMD CPU at 3.3GHz.

Deploying Secure Multiparty Computation (MPC) to operate on data from real world sources requires many connective elements that have not received much attention in the literature. One prominent example is that MPC protocols typically assume conveniently structured data, whereas data in the real world comes in formats that are meant to be handled by string parsing engines. In this work, we give a new constant round protocol for securely parsing secret shared strings into an MPC-friendly format, built upon secure shuffle as a key primitive. Secure shuffle applies a permutation to a list while keeping both the permutation and the underlying data secret-shared at all times. While highly efficient protocols exist in the semi-honest setting, achieving malicious security has incurred significant overhead in both rounds and communication. We present Truffle, a new three-party shuffle protocol that is secure against one active corruption to bridge this gap. Truffle achieves an amortised round complexity that for the first time matches the state-of-the-art semi-honest protocol, while incurring only sublinear communication overhead. The core technique that underlies Truffle is a novel distributed verifier zero-knowledge proof that checks the correctness of a putative shuffle. We implement Truffle and show via benchmarks that it is performant enough to handle real application data. Beyond parsing secret shared data, secure shuffle finds applications in graph analytics, anonymous communication, Distributed Oblivious RAM, aggregate statistics, and secure sorting, each of which stand to benefit from the improvement that Truffle provides.

Post-quantum assumptions may not rely on the difficulty of finding secret subgroups as many classical schemes did. Instead, several assumptions make use of more general group actions, with the hope that quantum algorithms are not helpful in this less structured setting. Group action-based constructions were first presented in the context of isogenies in which an ideal class group acts on elliptic curves, but equivalence problems in error-correcting codes and lattices also exhibit such structures. Previous works presented anonymity-preserving constructions in a generic group action framework; however, they were not general enough to encompass the group action underlying the Lattice Isomorphism Problem (LIP), for which the acting group is countably infinite and non-commutative. We bridge this gap by, from zero-knowledge proofs of OR statements, building generic blind signatures and strong designated-verifier signatures with non-delegability from standard assumptions corresponding to a generalised group action inverse problem.

We present a neural network-based pipeline for efficiently generating fast matrix multiplication (FMM) algorithms of small but arbitrary dimensions $(n,m,k)$. Our neural network is general and tunable to output FMM schemes with specific properties, and in this paper we specifically target aspects that are useful and important in practical implementation, such as ternarity (coefficients in $\{-1, 0, 1\}$), sparseness and a low number of additions after optimization (addition reduction carried out separately). We generate and optimize thousands of FMM algorithms and show that our generation method is beneficial in terms of performance across the entire FMM pipeline (both the FMM generation itself and optimization of additions). We discuss performance metrics and utilize heatmaps to visualize and understand this performance. We achieve record-low arithmetic (additive) complexity for various combinations of dimensions. For $(n,m,k) = (2,2,k)$, our method performs particularly well. Our improvement compared to previous results increases with $k$. We show that the (addition) optimization process can behave very differently depending on the dimensions considered, indicating how further improvements (beyond our results) can be targeted. In particular, in the $(n,m,k) = (2,2,k)$ setting, we show evidence of structural FMM properties coming into play, concretely showing that FMM generation with a minimal number of additions is sometimes suboptimal with respect to the entire FMM pipeline. Finally, we make our neural network implementation, our generated FMM schemes, heatmap utilities and datasets publicly available.

The shift to Post-Quantum Cryptography (PQC, a.k.a. quantum-resistant cryptography) is considered the immediate solution to the threat posed to public key cryptography/PKI by quantum computers. Due to the variety of PQC algorithms (and their characteristics), researchers have proposed different PQC migration strategies. For example, KEMTLS (Schwabe, Stebila, and Wiggers, CCS '20) replaces TLS handshake signing operations by Key Encapsulation Mechanisms (KEMs). However, KEMTLS requires KEM-based certificates (i.e., a certificate with a KEM public key), and the question of issuing KEM certificates on a large scale has received limited attention from the community. We address this research gap by comparing the performance of different Proof of Possession (PoP) approaches for KEMs and assessing their viability for practical adoption. To this end, we first propose and implement a non-interactive PoP for Hamming Quasi-Cyclic (HQC), a code-based post-quantum KEM selected by NIST for standardization. Our PoP is instantiated via the VOLE-in-the-Head (VOLEitH) paradigm. %VOLEitH is based on Vector Oblivious Linear Evaluation (VOLE). Setting, reproducibility, and practicality as design goals, we integrate and benchmark our approach against PoPs for Kyber and FrodoKEM (from Güneysu et al., CCS '22) in the ACME protocol for automatic certificate issuance. Our results show that, in general, Kyber allows faster issuance of KEM certificates but at a cost of losing either compatibility with the protocol (necessitating significant alterations to proposed internet standards) or breaking compatibility/compliance with NIST standards. Notably, our PoP for HQC holds compliance, compatibility, \emph{and} achieves smaller proof sizes. We also report integration choices and considerations, as well as network traffic analysis stemming from larger (KEM-based) Certificate Signing Requests (CSRs). Our testbed demonstrates the impact of large CSRs by simulating an unstable network. It shows that HQC-PoP's performance is competitive with the fastest options, thanks to its smaller proof sizes.

SLH-DSA is a standardized stateless hash-based signature scheme based on SPHINCS$^+$, but its signatures remain large. PORS+FP uses forced pruning to reduce the size of the bottom few-time signature (FTS) component, while BPORS+FP distributes repeated uses among independent PORS child keys. In BPORS+FP, each selected leaf reveals a fixed secret value, and a single pruning budget limits the total number of authentication nodes across all coordinates. We introduce BPORS-C+BFP, which replaces each secret at a child leaf with a short hash chain and assigns a separate authentication budget to each block of coordinates. The child Merkle tree authenticates each chain endpoint. Each selected chain still contributes one hash value to the signature, while its opening depth provides an additional encoding choice. For a fixed set of selected chains, a constant-sum constraint prevents forward hashing alone from converting one valid depth tuple into another. Under repeated use, signatures may disclose different positions on the same chain. We derive a generating-function upper bound on coverage and an exact counting method for individual pruning blocks that accounts for these disclosures and target acceptance. Separate block budgets confine pruning-induced dependencies, reducing the number of coordinates counted jointly and making exact calculation practical for small blocks. Replacing FORS in SPHINCS+ while keeping the hypertree and one-time signature parameters fixed, BPORS-C+BFP reduces complete-signature sizes by $8.3\%$--$18.1\%$ across six standard settings, compared with $3.7\%$--$13.4\%$ for BPORS+FP. Across three limited-use settings, the reductions relative to FORS are $32.5\%$--$36.5\%$ for BPORS-C+BFP and $22.0\%$--$26.0\%$ for BPORS+FP.

Matrix-native fully homomorphic encryption, introduced by Gentry and Lee, multiplies encrypted matrices with a Trace product and returns its four-component output to an ordinary ciphertext with a BigSwitch, whose keys over an extended ring dominate the key material of the scheme. Existing BigSwitches follow two routes: they either store one key per source, as in the original construction, or factor the secret through the trace and relinearize at run time, as in the Trace-Factored BigSwitch (TFB) of Park et al., which halves the keys at the price of $50\%$ more key switches and a whole switching error multiplied by the secret. Meanwhile, the Galois splitting of Park (Eurocrypt'25) decomposes such switches into base-ring diagonals, but it has not been used to reduce their keys. However, whether a BigSwitch can publish only the keys of TFB and still run at the speed of the original one has remained open. In this work, we first propose the pair-merge BigSwitch, which observes that the diagonals of a split BigSwitch are indexed by an inversion-closed coset $\kappa H$ and rewrites the target of a diagonal as $x\,g(s)+y\,s\,g(s)=g\big(g^{-1}(x)\,s+g^{-1}(y)\,s\,g^{-1}(s)\big)$, so that it borrows the product key of its inverse at the cost of one Galois step; it makes the $2n$ key switches of the original BigSwitch with $n/2+1$ instead of $n$ product keys, and we prove that no per-diagonal BigSwitch with $2n$ key switches holds fewer than $3n/2+1$ keys. Building on it, we propose public key rebasing, which turns Galois keys into product keys with one relinearization key placed one small modulus layer above the chain, so that the client publishes only the keys of TFB and a 10.6 MiB layer key, at the price of $1.5\times$ the resident keys of TFB on the server. Consequently, together with a Hermitian hop that finishes a partner diagonal of a Gram product with one Galois step, PairSwitch makes $2n$ key switches on general inputs and $3n/2+1$ on Gram products. On the parameters of Park et al. ($n=256$, $p=17$, $\log_2 PQ=200$), our implementation runs a BigSwitch $1.89$--$1.99\times$ faster than TFB and $1.28$--$1.38\times$ faster than the original BigSwitch, with $2.4$ bits less noise than TFB and $4.3$ bits more than the original, at a $128.3$-bit layer key; it is $2.45\times$ faster than TFB on Gram inputs. Our implementation and the raw logs are available at https://github.com/acprk/pairswitch-gl.

Traditional Proof-of-Work protocols face structural limits in transaction throughput, as scaling block capacity within a serial verification model introduces severe propagation delays and elevates orphan block rates. To address this classical constraint, this paper proposes an asynchronous pipeline consensus architecture that decouples mining initiation from full transaction verification. By embedding a 6-byte compressed UTXO identifier list within an agile Compact Block, nodes can initiate mining on subsequent blocks with reduced delay. This mechanism shifts data latency from a rigid physical bottleneck to a configurable declaration status, introducing a flexible validation framework. Network designers can thereby adjust the dissemination window—defined by the pipeline depth k and mining interval—to adapt to varying block sizes under the Nakamoto security model. Furthermore, we introduce a Dual-Coinbase mechanism that removes mandatory inter-block freezing, thereby unlocking the full potential of the pipeline parameter k and demonstrating applicability to alternative consensus architectures such as PoS, BFT, and DAG. This study establishes a backward-compatible upgrade path for high-performance decentralized ledgers by demonstrating that blockchain scalability can be optimized through the strategic configuration of its minimal consensus payload.

Hash-based signatures are the most conservative post- quantum signature family, and the stateful schemes XMSS and LMS are both standardized by NIST. Prior work has instantiated XMSS and SPHINCS+ with Korean cryptographic primitives, but no comparable Korean-primitive study exists for LMS. We fill that gap with K-LMS, an experimental variant that preserves the full LMS structure and domain separation and replaces only the hash. The substituted hashes are the Korean hash function LSH-256, in both its reference and its vectorized implementation, and a Tandem-DM double-block-length construction over the Korean block ciphers CHAM, LEA, and ARIA. A non-invasive bridge over the reference LMS implementation realizes eight interchange- able backends without editing a line of it. We evaluate key generation, signing, and verification latency, key and signature sizes, peak memory, a sweep over tree height and the Winternitz parameter, and implemen- tation complexity. Hash substitution leaves key and signature sizes, and the memory requirement of the LMS data structures, unchanged. We also isolate two measurement pitfalls that can distort such comparisons: a vector dispatch wrapper that re-runs its capability check on every digest, which costs an order of magnitude on our virtualized host, and the choice of software or hardware-accelerated SHA-256 as the baseline, which shifts any LSH vs. SHA-2 conclusion by a factor of about six. Profiling shows that LMS is dominated by 55-byte one-shot hashes (about 94 % of all calls), so scheme-level ranking cannot be extrapolated from long-message hash benchmarks. Against a fair software baseline, LSH-256 K-LMS signing is on par with SHA-256 LMS (0.84×), while hardware acceleration retains a ∼3.6× advantage where it is available. On the same host and with identical LSH-256 code, K-LMS runs 3.3– 3.9× faster than the published K-XMSS implementation, because LMS needs one hash call per Winternitz chain step where XMSS needs three.

Efficient multiplication over $\mathbb{F}_2[x]$ is a core primitive in classical and post-quantum cryptographic software. As ARM and RISC-V become increasingly relevant for open-source cryptographic libraries such as OpenSSL and liboqs, arithmetic kernels must be retuned across a wider range of Instruction Set Architectures (ISAs). High-performance arithmetic libraries recursively apply Karatsuba- and Toom-style decomposition rules, each splitting the operands into smaller subproblems and recombining the resulting products. The resulting decomposition schedule is the recursive tree of rule choices from the top-level multiplication down to the base kernels. However, hand-tuned schedules can miss better decompositions at large operand sizes, while ISA-specific primitive costs complicate cross-platform retuning. In this paper, we formulate recursive $\mathbb{F}_2[x]$ multiplication as a schedule-selection problem. The recursive rule space has optimal substructure, allowing dynamic programming (DP) over a compact ISA profile that accounts for base multiplication, XORs, memory traffic, and recursive overhead. The resulting schedules are materialized as dispatch tables or fixed-size kernels. Across x86-64, ARM64, RISC-V64, and RP2040, DP costs track runtime trends across input sizes, and the full rule set achieves $1.04$–$1.18\times$ geomean speedup over gf2x. HQC and BIKE integrations on the three 64-bit platforms yield $1.06$–$1.21\times$ and $1.01$–$1.70\times$ end-to-end speedups, respectively, against their platform baselines. We also evaluate Classic McEliece on these platforms. With prepared profiles, HQC/BIKE schedule selection takes 0.075–0.762 seconds, avoiding candidate compilation and benchmarking during search. The scheme provides a systematic alternative to hand tuning and measurement-driven per-size empirical search, reducing the effort required to port and retune carry-less multiplication kernels.

The One-Way-to-Hiding (O2H) theorem is a useful tool for analyzing reprogramming in the quantum random oracle model (QROM). It bounds the distinguishing advantage by the probability $\epsilon$ that a one-wayness attacker finds the reprogrammed point. A sequence of works has improved the tightness of this theorem. Currently, the Measure-Rewind-Extract O2H (MRE-O2H) theorem proved by Ge et al. (ASIACRYPT 2024) achieves the tightest known upper bound of $O(\sqrt{q}\cdot\epsilon)$, where $q$ is the number of quantum queries. This theorem follows the Double-Sided idea introduced by Bindel et al. (TCC 2019), which requires the one-wayness attacker to access both the original and reprogrammed random oracles, thereby imposing stronger requirements on the reduction. Moreover, it incurs a $q$-dependent loss of $O(\sqrt{q})$. In this paper, we address these limitations by proving two Extract-Amplify-Measure (EAM) O2H theorems. First, we prove a Single-Sided EAM-O2H (SSEAM-O2H) theorem, which achieves the same $O(\sqrt{q}\cdot\epsilon)$ upper bound as the MRE-O2H theorem, while the resulting attacker only needs access to either the original or the reprogrammed random oracle, reducing the requirements on the underlying reduction. Second, we prove a Double-Sided EAM-O2H (DSEAM-O2H) theorem, which retains the Double-Sided idea used in the MRE-O2H theorem but removes the $q$-dependent loss, yielding a tight $O(\epsilon)$ upper bound. As applications, we revisit the security of several Fujisaki--Okamoto variants proposed by Hofheinz et al. (TCC 2017) in the QROM, namely $\textsf{U}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$, and obtain the following results: The \textsf{IND-CCA} security of $\textsf{U}^{\slashed{\bot}}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Bindel et al. (TCC 2019) and Kuchta et al. (EUROCRYPT 2020), we avoid both the square-root loss and the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage. The \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{IND-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we reduce the $q$-dependent loss from $O(q^{1.5})$ to $O(q^{0.5})$. Assuming unique randomness recoverability, the \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we avoid the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage.

Classic McEliece is a post-quantum encryption scheme. Its public key is a generator matrix of a secret binary Goppa code. Its security levels are set by generic decoding attacks, which cost $2^{151}$ to $2^{287}$ bit operations for the five parameter sets. Ghoshal, Ishai, Jain and Sun (GIJS26) recently gave the first test that tells a public key from a random matrix at a lower cost, an estimated $2^{114}$ to $2^{124}$ bit operations. They have since extended it to recover the secret key. The test is one large sparse linear-algebra computation, which we call a run. We improve this attack in two ways. First, we lower the cost of a run to $2^{89}$ to $2^{98}$ bit operations. If every operation is charged for the memory that it addresses, at square-root cost, a run costs $2^{107}$ to $2^{117}$. This is our best estimate, and it is below the cost of generic decoding with free memory. The Classic McEliece security guide charges every operation for the whole memory. Under that rule a run costs $2^{117}$ to $2^{128}$, against $2^{159}$ to $2^{316}$ for generic decoding. Second, we give two ways to recover the secret key. One rests on a theorem that we prove and needs $100$ to $1400$ runs. The other builds on the key recovery of GIJS26 and needs a single run. None of this is close to practical, and a run at full size cannot be tested. The costs rest on four heuristic assumptions, which we state and test on small keys. There the first attack recovered the secret key with polynomials of degree $5$, and the second with degrees $5$, $6$ and $7$. Degree $7$ is the degree of the attack on Classic McEliece. Small keys deviated from the assumptions in a few ways. We identify the cause of each deviation and argue that it does not occur at full size. As a demonstration we recovered the secret key of instance~253 of the TII McEliece key-recovery challenges ($m=8$, $t=9$, $n=214$), a toy-sized code that had not been solved.

Oblivious Message Retrieval (OMR) enables recipients to retrieve messages from an untrusted server without revealing which messages correspond to them. OMR is useful for privacy-preserving systems such as anonymous messaging and blockchains. Existing constructions are inherently built in the public-key setting and use Fully Homomorphic Encryption (FHE) to allow a detector to scan a public bulletin board and produce a compact encrypted digest containing only relevant messages. However, this design incurs a major practical limitation: sender-published signals are large (hundreds of kilobytes), leading to significant bandwidth, storage, and on-chain costs. In this work, we explore the efficiency gains achievable by moving to a private, stateful setting, and introduce stateful OMR, a new model in which senders and receivers maintain lightweight private state to enable more efficient anonymous communication. Based on this model, we design StOMR, a protocol that significantly reduces the size of sender signals compared to prior approaches. To support the required shared state, we further introduce an OMR Key Encapsulation Mechanism (OMR-KEM), which allows users to privately establish shared state and instantiate stateful OMR without out-of-band channels. We implement StOMR in C++ and evaluate it against the state-of-the-art systems PerfOMR (USENIX Security '24), SophOMR (USENIX Security '26), and InstantOMR (USENIX Security '26). Our results show that StOMR preserves detector performance while achieving a signal size approximately 550×, 650×, and 178× smaller than PerfOMR, SophOMR, and InstantOMR, respectively.

We introduce a cryptographic framework for fingerprinting machine learning models, enabling model providers to train models that can later be attributed to them. Our framework captures an honest setting in which providers distribute base models that users may subsequently modify to adapt them to their own applications (e.g., through finetuning). We formalize three properties for fingerprinting schemes: (1) quality preservation or undetectability: fingerprinted models must remain computationally indistinguishable from models produced by an underlying training algorithm, (2) robustness: the fingerprint must remain detectable even after the model weights are subject to permitted modification, and (3) unforgeability: no computationally bounded trainer can forge the fingerprint except by applying a permitted modification to an existing fingerprinted model. Under the continuous learning with errors assumption (Bruna et al, 2021), we construct a robust and unforgeable fingerprinting scheme for modifications in $\ell_2$. The scheme achieves undetectability with respect to any given noisy training algorithm, meaning any algorithm whose output weights can be decomposed into independent Gaussian and non-Gaussian components. Along the way, we introduce two new technical tools. The first is a form of steganography; we develop a method for undetectably modifying a noisy training algorithm so that its output weights secretly encode a message. The embedded message remains decodable even after bounded $\ell_2$ perturbations to the weights. Second, we introduce the pancake alignment problem, a "semi-search" variant of homogeneous continuous learning with errors (hCLWE). Given hCLWE samples generated from a random secret, the goal is to recover a direction that is sufficiently aligned with the secret. We provide evidence for the hardness of pancake alignment in certain parameter regimes via reductions from continuous learning with errors.

SQIsign encodes its response isogeny via a two-dimensional representation on a product of elliptic curves, using the Kani construction. We analyze the algebraic structure of this encoding in detail, with a focus on the role of the auxiliary isogeny and its implications for strong unforgeability. We show that the anti-isometry $\psi$ determining the Kani kernel is publicly computable from the torsion-point images of the component and auxiliary isogenies alone, that the automorphism orbit $\{\psi, -\psi\}$ is the only torsion-level source of encoding non-uniqueness on a fixed product surface, and that every auxiliary of the correct degree is commitment-compatible by Kani's theorem. The sole barrier to producing an alternative encoding is the construction of a new auxiliary isogeny of the required (generically non-smooth) degree from the challenge curve. We demonstrate that this barrier falls whenever a single small prime divides the auxiliary degree $2^f - q$: the adversary reroutes the terminal $\ell$-isogeny step at the codomain of the honest auxiliary, preserving the total degree exactly. Since generic odd integers possess small prime factors with overwhelming probability, this establishes that canonicalization of the basis change matrix does not suffice for strong unforgeability. We analyze the signing algorithm's dependency structure to show that the auxiliary cannot be bound into the Fiat-Shamir hash without a protocol redesign, and conclude with a structural comparison of ECDSA (where canonicalization suffices), SQIsign (where it does not), and salt-PRISM (which achieves strong unforgeability via a salted hash-to-prime mechanism that eliminates the auxiliary freedom entirely).

Endowing Bitcoin with the ability to verify succinct proofs has been a longstanding problem with important applications such as scaling Bitcoin and allowing the Bitcoin asset to be used in other blockchains trustlessly. It is a challenging problem due to the lack of expressiveness in the Bitcoin scripting language and the small Bitcoin block space. BitVM2 is the state-of-the-art verification protocol for Bitcoin used in several mainnets and testnets, but it suffers from very high on-chain Bitcoin transaction fees in the unhappy path (over $14,000 in a recent experiment). Recent research BitVM3 dramatically reduces this on-chain cost by using a garbled SNARK verifier circuit to shift most of the verification off-chain, but each garbled circuit is 42 Gibytes in size, so the off-chain storage and setup costs are huge. This paper introduces BABE, a new proof verification protocol on Bitcoin, which preserves BitVM3's savings of on-chain costs but reduces its off-chain storage and setup costs by three orders of magnitude. BABE uses a witness encryption scheme for linear pairing relations to verify Groth16 proofs. Since Groth16 verification involves non-linear pairings, this witness encryption scheme is augmented with a secure two-party computation protocol implemented using a very efficient garbled circuit for scalar multiplication on elliptic curves. The design of this garbled circuit builds on a recent work, Argo MAC, which gives an efficient garbling scheme to compute homomorphic MACs on such curves.

Extremely Lossy Functions (ELFs) are a standard model primitive that captures many useful properties of random oracles (Zhandry, Crypto 2016). While there are many variations of ELFs with additional properties, every construction (excluding obfuscation) has followed essentially the same template of bootstrapping from a sequence of ELFs secure only against fixed-size adversaries, and every construction was based on only the exponential hardness of DDH (or $k$-Lin), an assumption that is only reasonable over elliptic curves. We introduce and construct Extremely Lossy Trapdoor Hashing (ELTDH), a stronger notion that implies all known variations of ELFs. Our construction achieves ELTDH in one go, without bootstrapping from schemes secure for only fixed-size adversaries, which makes it simpler and more efficient than existing ELFs. We assume exponential security of the small-exponent discrete logarithm, together with polynomial security of decisional composite residuosity (DCR). Exponential security is only required in the size of the secret exponent, not the size of the group, so the assumption plausibly holds for multiplication modulo $N^2$ (and for many other cryptographic groups), despite the subexponential-time discrete logarithm attacks from index calculus. Our results diversify the assumptions underlying ELFs, while also giving a simpler construction.

Anonymous authentication schemes allow a user to prove they have been authorized by some issuer, without revealing any additional information about the user's identity. Two variants are currently seeing strong real-world interest. Anonymous tokens (ATs) allow one-time proofs of authorization, e.g., for privacy-preserving rate limiting as currently being pursued in the MoLE effort at the IETF. Anonymous credentials (ACs) incorporate attributes that can be selectively disclosed in an unbounded number of proofs; these underpin digital-identity systems such as the European Digital Identity (EUDI) wallet. Both anonymous tokens and credentials are envisioned as being deployed in systems with multiple issuers. In standard schemes, proofs reveal which issuer authorized a user, leaking more information than necessary and shrinking a user's anonymity set. To address this, there has been significant recent interest in issuer-hiding schemes that only reveal that the authorizing issuer lies in a specified policy set. We present generic constructions of issuer-hiding ATs/ACs based on key-randomizable signatures that give rise to several efficient instantiations. Specifically, we show efficient issuer-hiding ATs based on the Tessaro–Zhu blind-signature scheme, and efficient issuer-hiding ACs (without policy keys) compatible with existing BBS-based schemes.

We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$. Concretely, we want an $F$ and an $A = A(m,n)>0$ as small as possible, so that for every affine map $L: \mathbb{F}_2^n \to \mathbb{F}_2^m$ (of the form $L(x) = Mx + b$) we have: $$ \operatorname{agree}(F,L) := |\{x \in \mathbb{F}_2^n \mid F(x) = L(x)\}| \leq A. $$ Such questions have been studied by Nyberg [1991, 1993], Carlet and Ding [2004, 2007], Liu, Mesnager and Chen [2017], Nagy [2025], and Biryukov, Turecek, and Udovenko [2026]. There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is: $$ A(m,n) = \Theta(2^{n-m} + 2^{n/2}), $$ and in particular, is never smaller than $2^{n/2}$. In this work, we show how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we show how to construct for every $\gamma>0$, a function $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ with $m = \mathcal{O}_{\gamma}(n)$, achieving $$ A(m,n) \leq (1+\gamma)^n. $$ Surprisingly, we even achieve the same quantitative behavior for the much harder question of having low agreement with $m$-tuples of degree $d$ polynomials $Q: \mathbb{F}_2^n \to \mathbb{F}_2^m$, with $m = \mathcal{O}_{\gamma,d}(n)$. Here the previously best bounds were of the form $A(m,n) = \mathcal{O}(2^{-\frac{n}{2^{d+1}}} \cdot 2^n)$ of Ben-Sasson and Kopparty [Kopparty's thesis, 2010], based on Gowers-norm-type arguments. All our results generalize to all finite fields $\mathbb{F}_q$ in place of $\mathbb{F}_2$. Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets.

Established multiple-precision software generally reserves Fast-Fourier Transform (FFT) multiplication for very large operands; for example, GMP reports full-product FFT thresholds of roughly 3000--10000 limbs. Becker et al. showed that Number-Theoretic Transform (NTT) multiplication can become advantageous much earlier on Cortex-M microcontrollers. It thus becomes an interesting engineering question to check where the crossover actually takes place on a big modern CPU. Our first-generation implementation on Cortex-A76 and Neoverse-N1 shows that the crossover point is around 10k bits when using ARMv8+ with Neon, using optimized and verified code. Motivated by the tighter Barrett bound of Becker, we developed the Second implementation, which eliminates additional reductions and pushes the crossover below 5.6k bits. We integrate our multipliers into OpenSSL RSA, resulting in end-to-end speedup for the public-key operations.

We construct the first (conjectured) post-quantum Time Lock Puzzle (TLP) from isogenies. Our construction avoids setup/preprocessing and achieves non-trivial efficiency, where puzzle generation runs in time $\sqrt{T}$ . We prove security in the quantum random oracle model (QROM) under a new conjecture about the sequentiality of isogeny pushforward computations, for which we provide a thorough justification. The only other (conjectured) post-quantum TLP constructions rely on heavy cryptographic machinery from lattice-based assumptions. We also provide, to the best of our knowledge, the first proof-of-concept implementation of a candidate post-quantum TLP. On an Apple M3 CPU, for a one-hour target delay, total puzzle generation, including setup, takes 2.9 minutes serially and 100.5 seconds with four generation workers. Our experiments demonstrate the practicality of the complete design and show that the quadratic gap between puzzle generation and solving in theory also translates into a meaningful concrete separation. As a stepping stone towards our main result, we provide a new TLP from isogenies in the preprocessing model from a combination of the sequentiality of isogeny walks in the $F_{p^2}$ graph and the hardness of computational Diffie-Hellman (CDH) over cyclic prime-order groups. This improves the assumptions underlying the only known TLP from isogenies in the preprocessing model, which required pairing based assumptions instead of just discrete log. We further adapt this construction to achieve non-trivial efficiency of $\sqrt{T}$ in puzzle generation without setup/preprocessing.

We introduce MULTISS, a distributed storage protocol over multiple remote Quantum Key Distribution (QKD) networks that ensures long-term data confidentiality. MULTISS is designed to combine several QKD networks, as QKD links are inherently limited in range, and to connect these networks through classical cryptographic channels. It relies on a hierarchical secret sharing scheme that makes certain shares mandatory for the reconstruction of the original secret. Hence, MULTISS offers a secure distributed storage solution in a scenario that is compatible with the current deployment of quantum networks. We prove that MULTISS preserves the confidentiality of stored data even if an adversary (i) gains full access to all nodes of a subset of the QKD networks, or (ii) records all classical communications between distant QKD networks and compromises them at a later stage. We show that it provides strictly stronger security guarantees than existing QKD-storage protocols. Our protocol also includes a procedure to update the shares without reconstructing the original data. In addition, we provide a recovery mechanism that tolerates the complete compromise of some QKD networks. We further introduce a variant of the protocol, called the local-mode, that minimizes the communication overhead of the recovery procedure when deployed over specific network topologies.

The Fujisaki--Okamoto (FO) transform (Journal of Cryptology, 2013) is the standard route from weakly secure public-key encryption to chosen-ciphertext security, and it underlies many practical post-quantum key-encapsulation schemes, including ML-KEM. Security proofs for FO are set in the (quantum) random oracle models. FO uses two hash functions: the derandomization hash~$H$, which turns the base scheme into a deterministic trapdoor function (TDF) by Encrypt-with-Hash, and the key-derivation hash~$G$. We ask whether it is possible to instantiate the hash functions in the FO transform while retaining its security guarantees. While prior work mainly focused on the $H$ step, our focus is the $G$ step, and we take an underlying injective TDF as given. We first show that the message-only implicit-rejection variant \smash{$\UmIR$}, a key-encapsulation mechanism formulation of FO that follows ML-KEM's choices of rejection and key derivation, is \emph{uninstantiable} in general. Namely, assuming standard LWE and subexponentially secure indistinguishability obfuscation and puncturable PRFs, for every efficient hash function family~$G$ with superlogarithmic output length there is a one-way, perfectly correct injective trapdoor function for which the resulting KEM is not IND-CCA2 secure. We next give sufficient conditions on~$G$ to instantiate the TDF-based \emph{hybrid-encryption} formulation of FO, rather than the KEM version. To this end, we introduce \emph{distributional injective extractability} (\DINJEXT{}), a new hash function property defined relative to a partially injective ``wrapping function.'' Under this assumption relative to the FO-derived wrapping function, combined with an achievable form of universal computational extractor security (Bellare, Hoang, and Keelveedhi, CRYPTO 2013) on $G$ and suitable assumptions on the base schemes, we obtain standard-model IND-CCA2 security. As evidence that \DINJEXT{} is achievable, we show that a random oracle satisfies it for every partially injective wrapping function, and that a quantum random oracle satisfies a formulation of it for the FO wrapping function, in both cases even relative to an oblivious sampling oracle. We leave a standard-model construction open.