In their CRYPTO 2023 paper, Fuchs, Rotella, and Daemen reduced the universality of key-then-hash (KTH) functions built from public permutations to differential properties of the underlying permutation. Subsequent work analyzed KTH Parallel with fixed-length public functions and related variable-length universality bounds [12,13]. We develop a corresponding framework for key-recovery attacks on KTH-based MACs. We first revisit the weak-key classes identified by Handschuh and Preneel for NH, NMH*, WH, and Square Hash. For the KTH attacks considered here, these classes are solution sets of controlled differentials. These translated sets may still satisfy HP08's broad operational weak-key criterion. Our claim is different: KTH offset invariance translates every such solution set through every absolute key with unchanged probability and oracle-query cost, so the attacks do not identify intrinsically exceptional absolute keys. For these controlled attacks, this gives a strong KTH form of the UHF "regularity" sought by Handschuh and Preneel: the complete attack profile is homogeneous over absolute key space. We then show that, for every fixed-length KTH map with no probability-one nonzero differential, any two distinct key-prefix candidates can be distinguished by a generalized differential test. If its generalized derivatives are affine, one retained successful fixed-output equal-length differential leaves an affine coset and at most \(\lceil \log_2 \#S_0 \rceil\) further suitably chosen successful events determine the prefix, under the stated computational and interface assumptions. Finally, we apply the framework to NH and Xoodoo[3]. Under reusable-reference WC(S), unequal-length NH image tests simultaneously test one candidate for each word of a multiplication pair and recover both \(w\)-bit words with one generation query and at most \(2^w+1\) verification queries, approximately half the verification-query cost of the Handschuh-Preneel recovery. For Serial[Xoodoo[3]], published three-round trails yield recovery of a reusable 384-bit KTH key block in \(2^{42}\) expected differential trials, or \(2^{43}\) MAC-oracle calls.

A folding scheme reduces the task of checking multiple NP instances into checking a single instance, providing an efficient route to incrementally verifiable computation (IVC). We identify five desirable properties of a practical folding scheme: constant recursion overheads, multi-folding, linear scaling with the number of instances, no extraneous commitments, and modularity. No existing scheme achieves all five simultaneously. We introduce NeutronNova, the first folding scheme to achieve all five. The prover's work is dominated by the cost to commit to its witness -- with no extraneous commitments -- and the recursive verifier performs only three group scalar multiplications and a constant number of hash computations. We construct NeutronNova modularly using the reductions of knowledge (RoK) framework around a core relation called zero-check, and build folding schemes for circuit satisfiability (CCS), grand products, and lookups by reducing each to zero-check. In experiments, NeutronNova folds a SHA-256 circuit with $2^{20}$ constraints in 91 ms, a ${\approx}10\times$ improvement over Nova. Several subsequent works have used NeutronNova to achieve new results, including space-efficient SNARKs with optimal prover time, packed sum-check protocols over small fields, and client-side zero-knowledge proofs with low end-to-end latency.

Spartan is a SNARK for R1CS that can be instantiated with any multilinear polynomial commitment scheme. We instantiate Spartan over a binary field, using Ligerito as the commitment scheme along with the ring-switching technique of Diamond and Posen; we refer to the instantiation as BinarySpartan. It is transparent, so it requires no trusted setup, and it provides polylogarithmic-sized proofs. Its security rests on a hash function, so it is plausibly post-quantum. We apply well-known optimizations to Spartan and sum-check: the SIMD R1CS of Phalanx; the next multilinear extension of SuperSpartan; sum-check optimizations from Gruen, from Dao and Thaler, and from Bagad, Dao, Domb, and Thaler; and Binius64’s byte lookup tables, which speed up the prover’s early rounds of Spartan’s outer sum-check. All but the last optimization were developed in the context of prime fields and in fact over large prime fields in the elliptic curve group setting. Furthermore, they are widely used in modern Spartan implementations. Thus, BinarySpartan is a natural instantiation of Spartan over binary fields. We implement and evaluate BinarySpartan end to end. On a MacBook Pro M4 Max (using only its 12 performance cores, and without GPU/Metal acceleration), BinarySpartan proves BLAKE3 at 547,000 hashes/second and SHA-256 at 255,000 hashes/second, including witness generation. These clear the 200,000 hashes/second rate proposed as sufficient for a post-quantum Ethereum transition, as well as the roughly 30,000–180,000 hashes/second a possible post-quantum Bitcoin transition would require. We also evaluate BinarySpartan on the Ethereum Foundation’s client-side proving benchmark, where it proves a single SHA-256 of a 2 KiB message in 6.2 ms, making it the fastest scheme in the benchmark suite.

Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn at CRYPTO’24, combine pseudorandomness with error correction, providing a natural abstraction for robust watermarking and steganography on generative AI models. Subsequent standalone notions, which are ideal security for secret-key PRCs and CCA-style security for public-key PRCs, are oracle-based and do not capture composable use with explicit parties, sessions, and corruption. We give a UC treatment of PRCs via corruption-aware ideal functionalities for both settings. Under non-adaptive corruption, the UC notions recover the standalone ones. Under adaptive corruption, we identify a common obstruction: dummy codewords sampled before corruption, together with their neighborhoods, must later be opened as valid PRC codewords. We formalize this as a decoder-non-committing code (NC-PRC), which any adaptively UC-secure realization must induce. We then capture failures of such openings via targeted low opening capacity, show it rules out robust NC-PRCs, and prove that LDPC-based PRCs have this property hence do not admit a NC-PRC. On the positive side, we sketch two compilers to lift error-correcting codes to admit NC-PRCs: a secret-key one from a puncturable PRF and indistinguishability obfuscation (iO), and a public-key one from a smooth projective hash function (SPHF), both evading the barrier via programmable acceptance. Finally, we identify a fresh-codeword explanation barrier for public-key PRCs: accepted unseen codewords cannot be explained from public information without violating pseudorandomness, hence public-key UC realizations require a trapdoor or an idealized setup, and PRC-based watermark detection is inherently designated-verifier.

The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.

In many secure multiparty computation (MPC) applications, the semantic domains of some operands are much smaller than the underlying arithmetic field or ring. The arithmetic domain is typically chosen to meet computation and security requirements (e.g., a 128-bit prime field), whereas the actual data may consist of only a few bits, such as 4-bit values in a 16-category classification task. This mismatch can lead to substantial communication and computation overhead in existing MPC protocols, which typically treat data of different ranges uniformly. We introduce UFO$_\mathrm{s}$, an ultra-fast toolkit for MPC on small elements, with optimized protocols for one-hot encoding, comparison, and digit decomposition. For $t=2^k$, our random one-hot vector generator attains, in the fan-in-two arithmetic-circuit model, the lower bounds of $t-\log t-1$ multiplication gates and $\lceil\log\log t\rceil$ multiplication depth. Our comparison protocol applies to any public small domain, while DigitDecomp avoids binary expansion and supports any public base $t>1$. Using these primitives, we construct a higher-radix sorting protocol for large field elements. Experiments confirm the resulting gains in random one-hot vector generation, digit decomposition, and sorting. In particular, our sorting protocol achieves a $3.4\times$ online and $1.4\times$ offline speedup over Hamada et al.'s radix-sort baseline when sorting $2^{16}$ elements among five parties.

Secure three-party computation with an honest majority is among the most efficient secure computation settings and is widely used in practice. However, achieving malicious security incurs significant overhead, often an order of magnitude higher than semi-honest protocols. Covert security provides a security–efficiency trade-off by detecting malicious behavior with a certain probability (e.g., $50\%$), deterring rational adversaries. Existing covert protocols mainly target two-party or dishonest-majority settings, with little work on efficient honest-majority three-party solutions. We present $\mathsf{ECHO}$, a family of concretely efficient protocols for covertly secure honest-majority three-party computation. We explore the design space of cheating detection and identification, and develop optimized protocols for both arithmetic and Boolean circuits, targeting different performance goals such as low latency and reduced communication. For arithmetic circuits over rings, our asymmetric-MAC-based protocol achieves an online phase only $1.26\times$ slower than the semi-honest baseline and over $5.59\times$ faster than malicious security. For Boolean circuits, our method improves over the best malicious protocol by $5\times$. We also applied $\mathsf{ECHO}$ on practical PPML tasks. $\mathsf{ECHO}$ approaches semi-honest performance while providing up to $8\times$ speedup over malicious security.

Large-state ARX-based S-boxes have become a key component of modern lightweight cryptographic designs, yet deriving tight security bounds for their differential and linear properties remains challenging. In this paper, we study the security of Alzette, the 64-bit ARX-based S-box used in the SPARKLE permutation, and present a general framework for the analysis and design of large-state ARX S-boxes. We introduce SMCS, a hybrid search strategy that combines MILP-based optimization with SMT-based model checking, enabling the computation of tight bounds on maximum expected differential probabilities and linear correlations. Using SMCS, we refine existing bounds for Alzette and, for the first time, establish tight linear bounds (resp. differential bounds) for up to 15 rounds (resp. 14 rounds). Building on these results, we propose S-box configurational encoding, an automated design method for ARX-based S-boxes, and introduce a new family of S-boxes called AFS (ARX-Feistel Structure) with 32-bit and 64-bit instances. We show that selected AFS instances achieve strictly better resistance to single-trail differential and linear cryptanalysis than SPECKEY and Alzette, respectively, while preserving comparable hardware and software costs. Finally, we present the first bit-based SMT model for optimal long-trail decomposition and apply it to derive more accurate bounds for SPARX-128 and SPARKLE. Our results show that replacing the S-boxes with AFS instances yields substantial improvements in cryptanalytic security margins.

This paper studies the post-quantum multi-key security of Galois/Counter Mode (GCM) in the Quantum Ideal Cipher Model (QICM). GCM is one of the most widely deployed AEAD schemes. In practice, widely deployed cryptosystems are often instantiated under many independent keys, making the multi-key setting practically relevant. A trivial extension of a single-key security bound to the multi-key setting incurs a security loss proportional to the number of keys. In particular, in the post-quantum setting, the term corresponding to exhaustive key search becomes $up^2/2^k$, where $u$ is the number of keys and $k$ is the key length. Here, $u$ is the number of keys, $k$ is the key length, and $p$ is the number of quantum queries to the underlying block cipher $E$ and its inverse, which serves as a coarse measure of the amount of offline (quantum) computation performed by the adversary. For example, when $u=2^{32}$, the trivial bound does not guarantee security for $p \geq 2^{48}$ when $k=128$, and even for $k=192$, it ceases to guarantee security for $p \geq 2^{80}$. We show that, at the cost of some additional loss terms, the term $up^2/2^k$ can be replaced by a term of order $\sqrt{dp^2/2^k}$, where $d$ denotes the maximum number of keys under which the same nonce appears in encryption queries. Thus, when $d$ is much smaller than $u$ (and the additional loss terms remain small), our bound improves upon the trivial multi-key bound. This can be viewed as a post-quantum counterpart of the classical result of Hoang et al. (CCS 2018). As in their work, we further show that, for randomized nonce-generation mechanisms that abstract patterns used in protocols such as TLS, the parameter $d$ remains small even when $u$ is large. Although our bounds are not tight and leave room for improvement, they yield a notable improvement over the trivial multi-key bound for several concrete parameter settings. To the best of our knowledge, this is the first non-trivial post-quantum multi-key security bound for an AEAD mode in the QICM. Our proof combines the reprogramming-and-resampling approach of Alagic et al. (EUROCRYPT 2022) with counting arguments used in the classical multi-user analysis of GCM by Hoang et al.

For each positive integer $c^*$, we construct an infinite sequence of Reed–Solomon codes $C \subset \mathbb{F}_q^n$, together with ball radii $z$, for which the proportion of $\mathbb{F}_q^n$ collectively covered by the radius-$z$ Hamming balls decays asymptotically more slowly than $\frac{n^{c^*}}{q}$ does. To pinpoint this decay rate, we develop various new, sharp combinatorial estimates, pertaining to the volumes of balls and their intersections. Our result proves that the capacity conjecture of Ben-Sasson, Carmon, Ishai, Kopparty and Saraf (J. ACM '23) is false. Our code families' relative rates converge to 0 and their relative radii converge to 1. We suggest avenues by the means of which the capacity conjecture might be resuscitated; roughly, we suggest that that conjecture be restricted to the case of families whose relative rates are bounded from below by a positive constant. Our work shows that many deployed SNARKs may be less secure than they were formerly—optimistically—assumed to be.

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.

AI image generation has made image misinformation a serious concern. To address this issue, the Coalition for Content Provenance and Authenticity (C2PA) standard adopts digital signatures to attest that an image originates from an authorized source, such as an attested camera or authorized AI provider. In practice, however, raw images are rarely published directly: photos are typically compressed before publication, which invalidates any C2PA signature. Recent works have proposed the use of zero-knowledge proofs (zk-SNARKs) to prove that only allowed edits were applied to a C2PA-signed original image. Unfortunately, prior works only support simple edits (e.g. cropping, blurring, and resizing) and do not support lossy image compression like JPEG, which is ubiquitous. The purpose of compression is to save communication. Therefore, unlike other edits, it cannot be verified directly, requires small proof sizes, and is unsuitable to outsourcing. To address these limitations, we present SPEG, the first practical proof system that supports the full image-transmission pipeline on personal devices. We present two protocols that support JPEG compression, while proving validity of the C2PA signature on the original image. The two modes are incomparable: the first is compatible with an arbitrary hashing algorithm (we use Poseidon for efficiency), whereas the second is significantly faster but requires the C2PA to use a polynomial commitment (e.g., KZH) instead of a conventional hash. Our key optimizations are handling the non-algebraic JPEG Encoding outside the proving circuit, and avoiding range checks in our floating-point arithmetic. We can prove the JPEG compression of an FHD(1080p) image in 47s in the Poseidon mode and in 2s in the fast mode. The fastest prior work (VerITAS) which only handles simple resizing, requires 227s on the same consumer hardware. Additionally, we identify a security gap in VIMz (PETS 25) that enables forgery of proofs for unauthorized images and provide a fix. We also prove that we can securely use the popular powers-of-tau SRS with the polynomial commitment scheme KZH.

Silent threshold encryption is a generalization of threshold encryption where the public encryption key associated with a group of users is a deterministic function of their individual public keys. The main efficiency requirement is that the ciphertext size should be sublinear in (and ideally, independent of) the size of the decryption quorum $N$. Existing constructions of silent threshold encryption for arbitrary threshold policies have either relied on bilinear maps or on heavyweight tools such as witness encryption and indistinguishability obfuscation. Recently, several works have shown how to support constant thresholds from the decomposed learning with errors (LWE) problem. In this work, we show how to construct a silent threshold encryption scheme from the decomposed LWE assumption where the ciphertext size for encrypting a single bit is $\tilde{O}(T) + \mathsf{poly}(\lambda, \log N)$. Here, $N$ is the total number of users, $T$ is the threshold, and $\lambda$ is the security parameter. Our scheme achieves non-trivial succinctness for all thresholds $T = N^\varepsilon$ for any constant $\varepsilon < 1$. More generally, our scheme extends beyond threshold policies to any monotone policy family that has a succinct (computational) secret sharing scheme; the ciphertext in this case scales with the maximum number of corrupted shares. The core building block in our work is a new bounded-collusion registered functional encryption (FE) scheme with succinct ciphertexts. Specifically, for $N$ users and a collusion bound $Q$, we obtain a registered FE scheme that supports depth-$d$ Boolean circuits on $\ell$-bit inputs and single-bit output with ciphertext size $Q \cdot \tilde{O}(d) + \ell \cdot \mathsf{poly}(\lambda, d, \log N)$. Security relies on the decomposed LWE assumption in the random oracle model. Previously, bounded-collusion registered FE for general circuits was known only from bilinear maps, evasive LWE, or indistinguishability obfuscation.

We introduce the notion of canonical lifting for group actions. This generalises existing techniques for reducing the size of group-action-based signatures, such as the canonical forms used in the LESS signature scheme. Building on this framework, we construct Sigma protocols and a linkable ring signature scheme. Notably, our approach avoids the key-reuse mechanism for linkability used in the framework of Beullens et al. (ASIACRYPT'20), which was shown to be insecure for group actions arising from linear code equivalence (ASIACRYPT'24) and lattice isomorphism (CiC'25). The resulting signatures have size logarithmic in the ring size. We provide security proofs at the level of the abstract canonical-lifting framework, which are then inherited by concrete instantiations satisfying the required assumptions. Finally, we instantiate our approach using the linear code equivalence group action and obtain a linkable ring signature scheme CELeReS, achieving signature sizes that compare favourably with the state of the art, and our AVX2-optimised C implementation demonstrates its practical applicability.

NTRU is one of the longest-tested lattice-based public-key encryption families and is often viewed as a compact alternative to (R/M)-LWE. Yet, after three decades of research, its potential for compactness remains an open area for further exploration: recent designs such as NEV (Asiacrypt 2023) and DAWN (Asiacrypt 2025) suggest that there is still room for improvement. This raises a natural question: Has NTRU reached its compactness limit? If not, how compact can it be while still remaining secure and efficient? Motivated by this question, we aim to formalize a unified relationship between compactness and efficiency under the required security level. We present a common two-stage view of NTRU decryption. In the first stage, the decoder constructs a small set of candidate wrap-around errors. In the second stage, it verifies these candidates using either algebraic redundancy or trapdoor-derived distributional information. We introduce Free Candidate Localization (FCL), a generic first-stage method that ranks coordinates by their proximity to the centered boundary. FCL could be used in most lattice-based encryptions; we instantiate it in ML-KEM to achieve a $10\%$ smaller ciphertext at the cost of a $5\%$ slower overall runtime in the reference C implementation under NIST-I. We organize modern NTRU encryptions into two frameworks. NTRU with Encoding leverages algebraic structure via auxiliary quotient rings. NTRU with Trapdoor exploits geometric structure through the NTRU trapdoor, then verifies candidate corrections using distributional tests. These frameworks give a common language for existing NTRU designs and for the compactness searches in this paper. Within an explicit search model, we derive heuristic compactness frontiers for both frameworks. At NIST-I, the encoding frontier yields a total public-key plus ciphertext size of 812 bytes, and the trapdoor frontier yields a size of 754 bytes, $15\%$/$21\%$ smaller than the previous lowest size of 964 bytes in DAWN. Furthermore, we propose END, an instantiation of NTRU with Trapdoor plus FCL. At NIST-I, \textsf{END} has a 384-byte ciphertext, which is exactly half the size of the 768-byte ciphertext of ML-KEM-512, and is $12-19\%$ smaller than the shortest prior NTRU-style ciphertexts in BAT (TCHES 2022) and DAWN. In our reference C implementation, the combined encapsulation and decapsulation cost of END-512 is about $3\%$ higher than that of ML-KEM-512.

In a recent preprint, Simon proposed a polynomial-time quantum algorithm for the Dihedral Coset Problem and rested the analysis on four lemmas. Three of them carry only proof sketches, and this paper gives each of those three a statement that admits a single reading together with a complete proof. Lemma 1 follows from an exact second-moment computation for the subset-sum counts, and it holds with probability tending to one in place of the constant originally claimed. The amplitude bound of Lemma 3 follows from an exact Parseval identity on the cube of measurement outcomes and holds at every threshold with no well-behavedness hypothesis, so that predicate leaves the argument entirely. For Lemma 4, we compute both balls-in-bins covariances exactly and find that the second carries a term a fixed ball count leaves out. The assumption that the distinguished group contains no faulty samples can also be dropped. The two branch amplitudes share a signed prefactor, so the counting estimates control their difference and not the ratio the lemma states. We prove the additive form and show that the closing argument consumes nothing more than that. A single hypothesis survives all of this. It asks that the partition into the two sides be fixed independently of the measured string, and the rule the algorithm gives for choosing that partition does not supply it. Establishing these four lemmas therefore does not by itself establish the correctness of the algorithm.

A universal, dynamic accumulator is a verifiable data structure that compresses a set of elements (e.g., unspent coins, issued public key certificates, etc.) into a succinct digest while supporting addition and deletion of elements alongside efficient proving of (non-)membership in that set. In many applications, valid (non-)membership proofs are a prerequisite to accessing a service (e.g., sending a private payment transaction, establishing a TLS connection, etc.). Typically, newly added or deleted elements necessitate updating all existing (non-)membership proofs per update. Thus, intermittently connected clients will possess invalid (non-)membership proofs whenever they reconnect. In this work, we design, implement, and evaluate algorithms for the RSA and bilinear accumulators that allow a resource-constrained client to privately delegate the updates of its (non-)membership proofs to an untrusted server. We define and prove security in a game-based framework under standard assumptions. We also study proof delegation in the batch setting. The online client algorithms are constant-time, i.e., independent of the updated set size $k$, compared to prior $\mathcal{O}(k),\mathcal{O}(\sqrt{k})$ works. The private delegation algorithms for membership proofs incur an asymptotically constant computational overhead for the server (e.g., $6.12\times$ overhead when $2^{10}$ elements were added in the offline phase to the RSA accumulator) compared to the non-private membership proof creation algorithms.

Modern isogeny-based cryptosystems spend much of their running time in finite-field, elliptic-curve, and higher-dimensional isogeny arithmetic. Exploiting SIMD parallelism in these computations is nevertheless nontrivial: central routines such as Montgomery ladders contain loop-carried dependencies, while point, pairing, and theta-coordinate formulas expose only irregular fine-grained parallelism. We show that substantial SIMD parallelism can be recovered by reorganizing the arithmetic dependency graphs of these higher-level primitives rather than vectorizing field multiplication in isolation. We develop an end-to-end AVX-512IFMA implementation of SQIsign in which data remain in a radix-$2^{51}$ vector representation across most of the curve-side computation. Our redesign includes projective xDBLADD schedules for Montgomery ladders, batched point doubling in several coordinate systems, a vectorized biscalar ladder, fused cubical-arithmetic pairing steps, and batched one- and two-dimensional isogeny evaluation. Relative to the reference C implementation, our implementation achieves end-to-end speedups of $1.76\times$, $1.71\times$, and $3.18\times$ for key generation, signing, and verification, respectively, at NIST security level~I; combining the same implementation with Qlapoti increases the key-generation and signing speedups to $2.90\times$ and $2.69\times$. To test whether these techniques are specific to SQIsign, we further apply the same AVX-512IFMA backend and higher-dimensional vectorization methodology to CORAL, a recent isogeny group action for post-quantum non-interactive key exchange based on two-dimensional $2$-isogenies. Across the five parameter sets in our experiments, this yields $1.28$--$1.40\times$ speedups for key generation and $1.92$--$2.46\times$ speedups for shared-key computation over the reference C implementation. These results provide cross-scheme evidence that algorithm-level SIMD scheduling is a reusable optimization dimension for higher-dimensional isogeny cryptography.

Motivated by the 2026 COLDCARD incident, this paper studies cryptographic asset recovery after self-custodial seed-generation failures. Self-custodial hardware wallets depend on secure entropy sources for seed generation. If an RNG implementation or design failure reduces seed entropy, an adversary may reconstruct wallet signing keys through offline search. Such weaknesses may also be discovered long after wallet creation, placing existing self-custodial assets at risk. To prevent large-scale exploitation after such a failure is identified, a hardware manufacturer or security response team may perform a protective sweep of affected assets into a protected recovery treasury. Asset redistribution then creates a fundamental authentication problem: once the signing key can be reconstructed by both the legitimate owner and an adversary, possession of that key no longer uniquely identifies the legitimate controller. We propose Z-SCAPE, a zero-knowledge recovery-credential protocol for privacy-preserving asset recovery after seed-generation failures and protective sweeps. Before compromise, the user commits to a recovery credential consisting of a 256-bit recovery secret $r$ generated from an entropy source intended to be independent of the transaction-signing seed, and an RNG-independent personal record $P$. After an incident, the prover proves knowledge of $(P,r)$ in zero knowledge for the pre-bound wallet identifier $W$, while binding the proof to the incident-specific protected-asset reference, a fresh verifier nonce, an expiry value, and a fresh recovery destination. The verifier derives the protected-asset reference from authenticated protective-transfer records rather than accepting an arbitrary asset set from the claimant. The protocol enables recovery claims without revealing $P$, $r$, or the compromised wallet private keys, while preventing replay, destination substitution, and cross-wallet protected-asset substitution. Z-SCAPE provides concrete integration mechanisms for Bitcoin and Ethereum and enables only assets recorded as protectively transferred from the proved wallet to be returned to the fresh destination bound to an accepted recovery proof.

Given a fixed security order, the randomness and latency of masked hardware present a trade-off. This trade-off has not been structurally examined well enough to enable an efficient search for a user-optimal (randomness/latency-efficient) masked design. Gadget-based masking simplifies masking by replacing each unmasked primitive circuit with a corresponding masked circuit, called a \textit{gadget}, to realize a larger masked design. These gadgets, in turn, have masking-order-dependent latency-randomness costs, lending a structure to the randomness and latency of gadget-based masked hardware. This structure enables automated Design-Space Exploration (DSE) of gadget-based masked hardware that takes in a user's constraints on randomness (or latency) to arrive at the latency (or randomness) optimal assignment of gadgets with less area and vice versa. This article introduces a software-level DSE approach, the basis of which is the two DSE algorithms - Minimize Latency under Randomness Constraints (MLRC) and Minimize Randomness under Latency Constraints (MRLC), which are duals of each other. While prior work optimizes masked hardware by formulating a global optimization based on the Boolean Satisfiability Problem (SAT), our results show that gadget-based masked hardware using Probe-Isolating Non-Interference (PINI) gadgets embodies a structured trade-off, enabling efficient heuristic-based solutions rather than relying on heavy global optimizations. This gives our tool comparable or superior area results in under a millisecond - a speedup of up to several orders of magnitude to the State-of-the-Art tools.

ML-DSA is a NIST post-quantum signature standard whose security argument rests on rejection sampling making released signatures independent of the secret key. Liu et al. and Damm et al. showed that a single leaked bit of the masking randomness per signature breaks this guarantee, making ML-DSA subkeys recoverable from a number of so-called informative relations, and the resulting attacks were sharpened by Schubert et al. and Bashiri et al.. All of them treat every leaked bit as equally trustworthy. We show that they need not. After the $j$-independence transformation introduced by al., the values extracted from a clean and from a flipped bit are exact complements in absolute value, so the observable relation $|\tilde z|$ follows a two-component mixture whose components we determine in closed form for all leakage regimes. This yields, first, a method-of-moments estimator for the bit-error rate $p$ that requires only the informative relations an attack already collects and that, unlike the estimator of Schubert et al., also works in the low-leakage regime, down to leakage index $4$ for ML-DSA-44 and ML-DSA-87 and $5$ for ML-DSA-65, the same indices at which the attack itself remains feasible. However lower leakage indices come with a lower accuracy, at $25{,}000$ informative relations the mean absolute error for the lowest cases is about $0.022$ to $0.040$ compared to values below $0.002$ in the high-leakage regime. The noise estimator is also adjustable to estimate asymmetric noise rates. Second, it yields a posterior probability, for each individual relation, that its leaked bit is correct. Thresholding this posterior gives an $O(\alpha)$ preprocessing step that corrects relations classified as noisy and that any downstream attack can use unchanged, where $\alpha$ is the amount of informative relations. Applied to the attack of Schubert et al., the preprocessing reduces the number of informative relations required for key recovery by about $20\%$ to $44\%$ across all three parameter sets, leakage indices $6$ to $9$, and error rates $20\%$ and $40\%$. Applied to the attack of Bashiri et al. for ML-DSA-44 at leakage index $8$, it improves key recovery across the noise range we tested: at $p = 0.45$ from $1{,}900{,}000$ informative relations, at $p = 0.40$ from $450{,}000$ informative relations, at $p = 0.20$ from $40{,}000$ informative relations, a single fixed threshold chosen in hindsight succeeds for $20$, $22$, and $23$ of $30$ seeds against $16$, $18$, and $19$ of $30$ without the preprocessing, and a parallel search over ten thresholds succeeds for $23$, $25$, and $29$ of $30$.

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, 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 incoming viewing key disclosure, while, at the same time, exposing problems with Monero. Finally, the paper shows that malicious parties may happily surrender all viewing keys in each of Zcash, Monero, and Firo and still find very efficient ways of evading financial monitoring.

We propose NAIBI-Full, a lattice-based key encapsulation mechanism (KEM) together with its forward-secure ephemeral key-agreement protocols, built on the regular representation $\rho$ of the non-split commutative algebra $\mathcal{A}_\alpha = R_q[y]/(y^k - \alpha)$ over $R_q = \mathbb{Z}_q[x]/(x^n + 1)$, with $k \in \{2,3\}$ and $\alpha$ a non-$k$-th power. Each party publishes the full matrix $\mathbf{t} = A\rho(\mathbf{s}) + \mathbf{e} \in R_q^{k \times k}$; because $\rho(\mathcal{A}_\alpha)$ is commutative, the cross-product collapses to small noise and a Peikert hint closes the gap to exact agreement, even though the public matrix $A$ is fully generic in $M_k(R_q)$. Hardness rests on a single, well-localised assumption: structured-secret Module-LWE $\mathrm{MLWE}_\rho$, which we identify exactly with a $\rho(y)$-linked $k$-sample MLWE problem via column decomposition, placing it inside the well-cryptanalysed MLWE landscape of ML-KEM. NAIBI-Full is the conservative member of the family: a clean account in terms of a standard lattice assumption, at the cost of $k^2$-element public keys and ciphertexts. Three primitives follow from this single core: an IND-CCA2 KEM (the $\mathrm{FO}^{\not\bot}$ transform, i.e. with implicit rejection, in the ROM and QROM) and two forward-secure ephemeral protocols, ephemeral-static and ephemeral-ephemeral. For the KEM we prove in addition a statistical, decapsulation-level binding correctness guarantee, with collision probability at most $(2/3 + 1/(3q))^{\lceil n/2 \rceil} + (8/q)^{n/2} + 2^{-256}$, below $2^{-148}$ at every parameter set. That binding survives in the malicious-key model on the public-key axis (MAL-BIND-K-PK, with a $q_H$ factor on the mechanism term), with no distributional assumption on the adversarial keys: the property ML-KEM is known to lack, and which the seed key format of FIPS 203 (which does restore the ciphertext axis) still leaves unattained. The statistical modality attaches to the accept branch; on the rejection branch, where no KEM admits a statistical guarantee, the rejection key hashes the public key, without which the notion falls to a one-line attack reusing a single $z$ across two malicious keys. We deliberately offer no static-static mode, since it would inherit the active key-mismatch attacks of the Ding/Peikert/NewHope family; NAIBI-Full is confined to its key-mismatch-resistant deployments. Parameter sets cover NIST security Categories 1, 3 and 5, all with $\delta \le 2^{-128}$.

The Updatable Signature (US) allows valid signatures to be updated by an update token without accessing the newly generated signing key. Cini et al. (PKC’21) formally defined this signature and gave several constructions. However, their security model requires the secrecy of the update token, which is not applicable in many common application scenarios where existing signatures have been distributed to many parties. In addition, one can use the same token to update both the signing key and signatures, and all signatures can be updated by a single token, whereas the adversarial signature generated by an adversary might also be updated. This work explores the (im)possibility of constructing an Updatable Signature with public tokens (USpt). Specifically, we first define the updatable signature with public tokens and present its security model. Then, from considering existing US schemes, we found that a secure USpt must properly handle a transform function from signature-update token to key-update token. We further formally proved the impossibility of constructing a secure USpt if (1) there is no transform function between key pairs and signatures, or (2) the signature-update token can be derived from the public keys of adjacent epochs. Finally, we present a concrete USpt scheme based on the BLS signature.

Proxy re-encryption (PRE) enables a semi-trusted proxy to transform ciphertexts between users without learning their plaintexts. In lattice-based PRE, honest re-encryption attack (HRA) security has become a common security goal. However, the relation between HRA and chosen-ciphertext (CCA) security, and the mechanisms needed to achieve HRA security, remain poorly understood. We first clarify the relation between the security notions. We formulate derivative-closure chosen-ciphertext security (DCL-CCA) and show that it implies HRA security at any fixed constant hop depth, including single-hop. We then introduce recorded-provenance chosen-ciphertext security (REC-CCA). For correct PRE schemes, REC-CCA preserves recorded provenance and implies both DCL-CCA and HRA security without a fixed depth bound. We next identify two attacks on linear re-encryption schemes that fail to hide correlations across honest transcripts. The first reconstructs the re-encryption functionality from distinct honest input--output pairs. The second uses repeated re-encryptions to average away fresh noise before reconstruction. Under the reusable-key convention, we obtain an HRA attack on the construction of Susilo et al. (ESORICS'21). For the construction of Fan and Liu (ACNS'19), we obtain a conditional attack under the noise-bearing interpretation of their re-encryption specification and the stated polynomial-noise and modulus-to-noise regime. Finally, building on stateful source-bound masking, we give a feasibility result for standard public-key PRE in the idealised continuous-Gaussian arithmetic model of Micciancio and Suhl (CiC'25). Our stateful, unidirectional, single-hop PRE scheme combines gadget key switching with Reused-\(A\) LWE. It achieves HRA security against static corruption for a public H2H delegation DAG fixed after registration. The resulting instantiation uses a polynomial modulus and a source pad only a constant factor wider than the decisional-LWE error width. Thus, in this setting, HRA security does not require superpolynomial statistical noise flooding.

We study HFE-based multivariate signatures with an \(LL'\) perturbation. The resulting scheme \(HFE_{LL'}\) gives short signatures, and its Dragon variant \(D\text{-}HFE_{LL'}\) gives ultra-short signatures by separating the hash length from the number of signature variables. We discuss the relation with \(\mathrm{HFE}^{\widehat{+}}\), the applicability of known attacks, and propose explicit parameter sets.

The Permutation Code Equivalence Problem (PEP) and Permuted Kernel Problem (PKP) are two notorious computational problems over linear codes used for building post-quantum digital signature schemes. Although traditionally analyzed over prime fields, recent proposals, such as the signature schemes PERK and SETH, have considered extension fields to improve efficiency and compactness. In this work, we analyze the hardness of solving PKP and PEP when instantiated over field extensions. %the latter between self-orthogonal codes. For binary field extensions, by exploiting a reduction to a structured variant of the Regular Syndrome Decoding Problem (RSD), we uncover new polynomial-time parameter regimes for both PKP and PEP, including families of self-orthogonal PEP instances and all self-dual instances over extensions of degree $\nu>4$. We also adapt the permutation-based Regular-ISD algorithm of Esser and Santini for RSD (CRYPTO '24) to PKP-derived instances, and uncover regimes of parameters for which it improves upon the state-of-the-art. Moreover, we present a reduction from a broad family of PEP instances over extension fields with odd characteristic to the Graph Isomorphism Problem, yielding a polynomial-time algorithm to solve those instances. Overall, our results invalidate the use of PEP over extension fields for most of the scenarios, and provide novel insights into the security of PKP over extension fields.

Continuous group key agreement (CGKA), the cryptographic core of Messaging Layer Security (MLS, RFC 9420), provides key management for large end-to-end encrypted group chats. It refreshes the group's keys as members join and leave, but offers no way for a designated auditor to recover past epoch keys, and no way to check that such recovery remains possible. Regulated deployments in finance, healthcare, and government therefore resort to plaintext server logging, abandoning end-to-end encryption entirely. Simply adding a key escrow admits a silent escrow failure: the group accepts an epoch whose escrow holds unrecoverable material, with no visible anomaly until a later audit. Addressing this, we introduce auditable CGKA (Au-CGKA), an MLS-shaped protocol in which every admitted epoch carries a proof. The proof binds that epoch's key material to a well-defined secret recoverable by a threshold auditor committee. Every member checks that binding against the epoch secret it derives and refuses the commit if the two disagree, so auditability guarantees that the secret of every epoch an honest member accepts is threshold-recoverable. We give a post-quantum protocol, Π_A, realizing this property with STARK proofs. The committer escrows the epoch secret to an auditor committee, and the escrow ciphertext is a STARK-friendly encryption of Shamir shares. Its well-formedness is proven in-circuit at MLS commit time. We prototype Au-CGKA in Rust with the proofs on a zero-knowledge, post-quantum custom multi-stage STARK. On an Apple M5 Pro, an auditability proof takes 1.38 s with proof-size 15.31 MB and verifies in 0.17 s, at every group size; the relation it proves is independent of the group size. The proof is checked at admission and then discarded, so it costs bandwidth on the commit and nothing in storage; the only persistent overhead is the fixed-size escrow. Adaptive post-quantum security holds in the secure-erasure model with straight-line reductions in the quantum random-oracle model, and carries to the implemented backend under a stated assumption; privacy and escrow soundness follow as game-based guarantees.

Ring signatures have long struggled to balance absolute anonymity with traceability. While various extensions, such as traceable and accountable ring signatures, have been proposed, they typically apply a uniform anonymity or traceability rule to all potential signers. This paper introduces personalized-anonymity ring signatures (PARS), a novel primitive in which users are certified with different anonymity rights according to their roles or authority. Unlike ordinary ring signatures, PARS involves a group manager at key issuance; however, the group manager does not determine a fixed signing group. Instead, signers retain the ring-signature feature of choosing the ring at signing time, while the manager certifies whether each user's key permits fully anonymous signing or only traceable signing. This model is particularly suited for organizational governance, where ordinary members may require strong anonymity for internal reporting or expressing dissenting opinions, while users with institutional authority must remain accountable for official approvals or authorizations. We provide a formal syntax and rigorous security definitions for PARS, capturing both standard ring-signature requirements and traceability-related guarantees. We then present a generic construction from standard cryptographic primitives, including digital signatures, one-time signatures, public-key encryption, and non-interactive zero-knowledge proofs of knowledge.

SPHINCS+ provides stateless signing and self-contained verification, but its signatures are large: every message carries a FORS signature and a complete WOTS+/Merkle authentication chain to the long-term root. This cost is repeated even when messages arrive in a bounded episode whose maximum size is known in advance. We introduce prepared-episode signatures and instantiate them as SPHINCS-PE. The construction splits a globally addressed hypertree at an episode boundary into upper and lower trees. Preparation authenticates the boundary root through the upper tree, while each online signature traverses the lower tree back to that root. Because the upper tree is computed before messages arrive, it can use fewer, taller layers. This removes WOTS+ blocks from full signatures at the cost of more preparation work. Full signatures remain self-contained, while recurring verifiers may cache the upper certificate. Our fixed-count exposure analysis pools colliding preparations and bounds post-selection of the target episode. The end-to-end theorem reduces unforgeability to PE-ITSR and explicit PRF and hash-component games. Compared with the matched FIPS 205 SLH-DSA profiles, SPHINCS-PE reduces full-signature sizes by 3% to 12% for the short profiles and by 25% to 40% for the fast profiles. With the upper certificate cached, online signatures are 24% to 48% smaller for short profiles and 56% to 70% smaller for fast profiles. These results show that prepared episodes can shorten hash-based signatures without giving up self-contained verification.

The quantum resource analysis of CSIDH has remained an active research topic. At Eurocrypt 2020, Peikert raised three open problems concerning the optimization of the corresponding quantum resources. In this work, we primarily focus on the first two: optimizing quantum resources for ideal class groups and choosing the collimation arity. Specifically, we reduce the T-gate complexity of class group actions for CSIDH-512 from $2^{52.6}$ to $2^{51.7}$. Furthermore, within our four-way permutation construction model and under a specified classical memory budget, we provide a detailed analysis of the classical and quantum resources associated with different collimation arities $r$. Among the evaluated configurations, $r = 4$ emerges as the optimal choice. By incorporating the hidden-shift quantum algorithms proposed by Peikert, we achieve a T-gate reduction of at least 85\% for solving CSIDH-512.

This paper presents several optimizations to Qlapoti (Asiacrypt'25), an ideal-finding procedure at the heart of modern isogeny-based signature schemes. We apply these optimizations to the Qlapoti-based NIST Round-2 SQIsign implementation from Asiacrypt'25. Together, they accelerate the Qlapoti procedure by approximately \(1.6\times\) to \(5.3\times\), depending on the parameter set and implementation. Under the Broadwell benchmark, compared with the baseline implementation in Asiacrypt'25, our optimizations achieve key-generation speedups of \(1.29\times\), \(2.23\times\), and \(1.54\times\), and signing speedups of \(1.23\times\), \(1.79\times\), and \(1.43\times\), at NIST security levels~1, 3, and~5, respectively. Our techniques also apply to the Qlapoti-optimized PRISM implementation (PKC'25, Journal of Cryptology), for which we introduce an additional tailored optimizations. Under the Broadwell benchmark, compared with the baseline implementation in JoC using Qlapoti, our improvements translate into key-generation speedups of \(1.22\times\), \(1.87\times\), and \(1.46\times\), and signing speedups of \(1.47\times\), \(1.90\times\), and \(1.60\times\), at NIST security levels~1, 3, and~5, respectively.

We present fault injection attacks against MAYO in which a single faulty execution reveals structural information about the secret. We consider two closely related single-block fault models. In the first one, a controlled perturbation affects one oil coordinate of a signature block and induces an error $e \in \mathcal{O}$. In the second one, the perturbation may affect several oil coordinates of the same block. In both cases, we show that the observable verification mismatch can be written as the image of the induced error under a publicly derivable linear operator. This yields two recovery strategies. In the linear route, when the relevant oil part of the error can be identified, recovery reduces to solving a linear system over $\mathbb{F}_q$. In the reduced-quadratic route, the same linear relation is combined with the constraint $P(e)=0$, which leaves, in the generic full-rank case, a reduced system of $m$ quadratic equations in $n-m$ variables. For the MAYO parameter sets, $n-m=o$ is small, and the resulting reduced quadratic systems can be solved over the base field. Recovering $e$ yields a nonzero vector of the secret subspace and provides a starting point for key-recovery techniques against the oil space. We also discuss the practical cost of both approaches and explain why the attack applies to randomized MAYO.

Updatable Public-Key Encryption (UPKE) augments the security of PKE with Forward Secrecy properties. While requiring more coordination between parties, UPKE enables much more efficient constructions than full-fledged Forward-Secret PKE. Alwen, Fuchsbauer and Mularczyk (AFM, Eurocrypt’24) presented the strongest security notion to date. It is the first to meet the needs of UPKE’s most important applications: Secure Group Messaging and Continuous Group Key Agreement. The authors provide a very efficient construction of an Updatable Key Encapsulation Mechanism (UKEM), implying UPKE, that satisfies their notion with classic security based on the Computational Diffie-Hellman (CDH) assumption in the Random Oracle Model (ROM). No existing post-quantum UPKE/UKEM construction is known to meet the AFM definition. We present and implement practical secret-key recovery attacks in the AFM adversarial model for all proposed parameter sets of two PQ schemes including the most efficient one to date, due to Abou Haidar, Passelègue and Stehlé (APS, Asiacrypt’23). If the UKEM schemes were used in a real-world group messaging application, the attacks would correspond to realistic execution scenarios, even when targeting a 100% success probability. Next, we present the first post-quantum UKEM construction meeting (a slight relaxation of) the AFM security notion. When based on the Module-LWE assumption, our construction is more efficient than prior PQ constructions, while achieving stronger security. More concretely, public key sizes are about 1/2 that of APS and ciphertext sizes are about 14% smaller. As the AFM security proof relies on random self-reducibility of CDH, which has no analogue for lattices, we develop a new proof technique for strong UKEM, identifying the core properties required from the underlying (lattice-based) encryption scheme.

We present four quantum-safe schemes: the Kyber (ML-KEM) and FrodoKEM key encapsulation mechanisms, and the Dilithium (ML-DSA) and Falcon (FN-DSA) signature schemes. We also develop the mathematical background on lattices needed to understand why Kyber, FrodoKEM, Dilithium and Falcon are regarded as lattice-based cryptosystems, and we provide insight into the computational hardness of the underlying lattice problems. The exposition is intended to be accessible to senior undergraduate students and beginning graduate students.

We introduce CRISP (\underline{C}hannel-\underline{R}andomised Single-\underline{I}mage\\ \underline{S}teganography with \underline{P}ermutations), a homomorphic steganography scheme for outsourced computation. In the setting we consider, a client (Alice) hides Boolean inputs in the least-significant bits of cover images and asks an honest-but-curious cloud (Carol) to evaluate a logic circuit, gate by gate, directly on those images so that a receiver (Bob) can later extract the result. The setting is natural for outsourcing but non-standard for steganography: Carol knows that steganographic embedding is used, knows the scheme, and knows the public channel-assignment permutations; the only secret is the per-execution pixel position $(\mathit{row}, \mathit{col})$ in the image at which the bits live. The security goal is therefore positional hiding under known presence, not Cachin-style undetectability. CRISP embeds all three inputs of a Fredkin gate (a universal reversible three-bit logic gate) into the three RGB channels of a single cover image at a secret pixel position, and writes all three outputs into a single output cover at the same position. Two independently sampled permutations $(\pi_{\mathrm{in}}, \pi_{\mathrm{out}}) \in S_3 \times S_3$ assign channels to logical roles at the input and output of each gate, and both travel with the public circuit specification. Two results about the limits of this design follow, and we regard them as the more useful contribution. First, per-gate resampling of $\pi_{\mathrm{out}}$ does not give circuit privacy. We prove that a server holding the circuit specification reads the channel-to-role map at every gate directly, and that a weaker adversary holding only the images recovers the same map and the wiring graph with nine channel-pair comparisons per gate. Second, a $1/(h{\times}w)$ positional bound proved on a single image does not survive a full multi-image transcript when ancillary wires carry publicly known constants. We restate the security game over the whole transcript and prove a bound $2^{\lambda}/(2^{\lambda}+n-1)$ with $n = h{\times}w$ and $\lambda$ the gap between the number of secret input bits and the collision entropy of the server's prior on them. Constants embedded only at the secret pixel push $\lambda$ up by one bit each, and enough of them pin the pixel down exactly. Two cheap repairs drive $\lambda$ back to zero and restore the exact $1/(h{\times}w)$ bound. The decay is polynomial, not super-polynomial, so the bound is statistically small but not cryptographically negligible in the standard sense.

Fully Homomorphic Encryption (FHE) enables computations on encrypted data, ensuring privacy for outsourced computation. However, verifying the integrity of FHE computations remains a significant challenge, especially for bootstrapping, the most computationally intensive operation in FHE. Prior approaches, including zkVM-based solutions and general-purpose SNARKs, suffer from inefficiencies, with proof generation time ranging from several hours to days. In this work, we propose HasteBoots, a succinct argument tailored for TFHE with programmable bootstrapping. By designing efficient protocols for arithmetic operations over quotient rings, HasteBoots achieves proof generation in a few seconds for TFHE evaluation with programmable bootstrapping, significantly outperforming the state-of-the-art, Zama (CCS'25). Moreover, HasteBoots supports batching multiple TFHE evaluations and bootstrappings, a feature that prior work cannot practically support due to prohibitive proving cost. HasteBoots can prove a batch of 16 operations within one minute, while maintaining succinct verification, requiring only 126 ms and a proof size of 0.28 MB. Our approach demonstrates the potential for scalable and efficient verifiable FHE, paving the way for practical, privacy-preserving computations.

Liu et al. (2022 Phys. Scr. 97 045102) propose a quantum public key encryption scheme in which a qubit message is encrypted by a controlled-NOT gate driven by a four-state public key, followed by measurement of the message register, and claim information-theoretic security. I show that the encryption map reduces exactly to \( |M\rangle \mapsto R_{\theta}X^{m}|M\rangle \), where the outcome \(m\) is published. \(R_{\theta}\) is diagonal and the ciphertext reproduces the computational-basis distribution \((|\alpha|^2,|\beta|^2)\) of the plaintext, while the plaintexts \(|0\rangle\) and \(|1\rangle\) are perfectly distinguishable. The claim of information-theoretic security is therefore invalid.

Beam search is practical for differential-trail exploration, but its cost grows quickly with the number of reachable intermediate differences. We test whether a lightweight tail-cost estimate can reduce deterministic bounded beam-search work without taking control of the search. At each horizon, a regressor predicts a residual tail cost from an active-nibble heuristic using the current difference and target endpoint. The learned signal is applied after classical selection. With four or two rounds remaining, the frozen policy protects the best $25\%$ of the classical frontier, removes at most $30\%$ of accepted states, and abstains when fewer than five states can be pruned. We develop the method on a state-grouped GIFT-64 corpus and evaluate it on $D=8$ and $D=12$ holdouts and a $D=16$ stress test. It preserves target recovery and the best classical cost on all $48$ holdout cases and all $18$ stress cases. Aggregate node reductions are $6.832\%$, $0.099\%$, and $0.040\%$ at $D=8$, $D=12$, and $D=16$, respectively. In a frozen-policy replication on PRESENT-64, retraining only the model weights preserves all $18$ $D=12$ cases with a $3.881\%$ aggregate node reduction, but one of the $18$ $D=8$ targets is missed. Learned guidance can therefore serve as a limited auxiliary signal, but its benefit is depth dependent and empirical preservation does not automatically transfer across ciphers. All comparisons are relative to the bounded classical baseline; no claim is made about globally optimal trails.

In 2017, Aggarwal, Joux, Prakash, and Santha proposed an integer analogue of the NTRU cryptosystem, known as the AJPS cryptosystem. This scheme is based on Mersenne numbers, and is believed to be resistant to quantum attacks. This paper revisits the security of AJPS by reexamining its inherent hard problems. We propose novel attacks that apply the continued fraction-based method and the lattice-based solving strategy for modular polynomial equations, rather than directly using lattice reduction algorithms. Our methods significantly relax the size constraints on the unknown private key. Specifically, we either eliminate the need to estimate upper bounds on the unknowns or extend the attack range of vulnerable weak keys, while enhancing the success probability under unbalanced parameter settings. To validate our theoretical findings, we conduct extensive numerical experiments with parameters of various sizes. The experiments confirm both the practicality and the effectiveness of our proposed attacks.

The MQOM signature scheme is currently a third-round candidate in the NIST competition for additional signatures. It is based on the ``MPC-in-the-Head'' paradigm and relies on the hardness of the MQ problem. Some of its parameter sets expose a Boolean quadratic system in the public key. While the situation for MQ over larger fields has been relatively quiescent over the last decade, Boolean MQ has seen active progress, culminating with Dinur's algorithms at SODA 2021 and Eurocrypt 2021. We propose yet another algorithm for Boolean MQ. It is a hybrid between the ``polynomial-method'' of Lokshtanov, Paturi, Tamaki, Williams and Yu from SODA 2017 and Dinur's ``second algorithm'' from Eurocrypt 2021. We remove some machinery from the latter to obtain a modest improvement of 1--4 bits in performance for MQOM parameters (``decremental improvement''). MQOM optionally uses the ``correlated GGM trees'' technique to shorten signatures; in that case, its security also relies on the hardness of the ``Partial-Guessing One-Wayness'' problem for MQ (PGOW-MQ): given an MQ system supposed to offer $\lambda$ bits of security, the adversary has to find the first $\lambda$ bits of a solution, and they have access to an oracle that enables them to check candidate prefixes. The designers of MQOM implicitly assumed that PGOW-MQ is as hard as MQ itself. Our algorithm can exploit the availability of the solution-testing oracle to solve PGOW-MQ 2 to 4 times faster than it solves MQ, thus showing that the two problems are marginally different. This yields attacks against MQOM that are 3--4 bits below the expected security level, but that suffer from huge memory complexities. Lastly, we survey old and new techniques to find an invertible linear change of variables that puts a few arbitrary polynomials in UOV shape. This leads to a small acceleration of our algorithm, and also incidentally improves upon the Thomae-Wolf and Furue-Nakamura-Takagi algorithms to solve underdetermined Boolean systems. A new idea based on matrix pencils was used to solve the largest underdetermined Boolean Fukuoka MQ challenges and may be of independent interest.

Post-quantum migration of Transport Layer Security (TLS) is often described as replacing a classical key-exchange algorithm with a post-quantum alternative. This framing is incomplete: TLS distributes security across key establishment, authentication, resumption and pre-shared keys (PSKs), traffic-secret evolution, and the X.509/PKIX ecosystem. These functions have different security objectives, failure modes, lifecycle dependencies, and deployment constraints. This Systematization of Knowledge (SoK) develops a functional framework for analyzing post-quantum TLS migration as an architectural problem rather than a single algorithm transition. We systematize classical, pure post-quantum, and hybrid key establishment; TLS 1.3 PSK modes and resumption; KeyUpdate; ML-KEM; ML-DSA and SLH-DSA; hybrid and composite authentication; X.509/PKIX and trust-anchor migration; HSM dependencies; interoperability; performance; deployment environments; cryptographic inventory; and crypto-agility. We classify evidence by mechanism, security objective, source of keying material, forward-secrecy behavior, quantum threat, post-compromise behavior, communication and computational cost, interoperability dependency, standardization status, deployment evidence, and migration complexity. We explicitly separate finalized standards from evolving Internet-Drafts and implementation-specific evidence. The systematization produces four analytical conclusions. First, confidentiality migration and authentication migration are coupled operationally but distinct security programs. Second, hybrid ECDHE-ML-KEM is a strong transitional architecture for confidentiality migration when the relevant TLS integration and implementation support are available, because its security objective can tolerate failure of one component; the exact security claim nevertheless depends on the standardized construction and its assumptions. Third, PSKs, resumption, and KeyUpdate are not interchangeable forms of rekeying: their security depends on the provenance and role of the secret, while KeyUpdate remains within an existing traffic-secret lineage and does not create an independent post-quantum secret. Fourth, deployment readiness is constrained as much by certificates, trust stores, HSMs, middleboxes, inventory, and interoperability as by primitive availability. We therefore derive a migration decision framework that prioritizes HNDL-sensitive data, controlled hybrid deployment, interoperability testing, staged authentication and PKI migration, and observable retirement of classical-only mechanisms.

We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies \[ \omega^*(G^{\otimes n}) \le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n)) \] for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen to three and matches the cubic gap dependence in Holenstein's general classical bound [Hol09]: \[ \omega(G^{\otimes n})\le\exp(-\Omega( \frac{ (1-\omega(G))^3}{1+\ell} n)). \] The proof replaces the randomly shifted logarithmic grid used in quantum correlated sampling by smooth soft labels. This makes the relevant label infidelity quadratic in the distance between state descriptions and avoids a Jensen loss when averaging over questions. Together with the postselection argument, these improvements yield the cubic gap dependence stated above.

Secure function evaluation (SFE) and private function evaluation (PFE) are fundamental primitives in multiparty computation. In SFE, multiple parties jointly compute a \textit{public} function over private inputs while revealing nothing beyond the output, whereas in PFE the function itself is \textit{private} and known only to a designated party. In this work, we focus on the semi-honest setting and present more efficient information-theoretic constructions for both SFE and PFE. For SFE, the classical BGW protocol incurs $O(n^2)$ communication per multiplication gate. The DN protocol (Damg\aa rd and Nielsen, Crypto 2007) reduces the amortized communication to linear but still require an additional $O(n^2)$ term, yielding $O(m^* n + n^2)$ communication for $m^*$ multiplication gates. This becomes suboptimal in the regime $m^*= o(n)$. We introduce a simple technique that removes this quadratic overhead, achieving strictly linear $O(m^* n)$ communication. For PFE, the only existing information-theoretic approach relies on universal circuits, which results in $O(m^5n+n^2)$ complexity for arithmetic circuits. We develop new techniques that avoid universal circuits entirely. Combined with our SFE improvements, this yields an honest-majority PFE protocol achieving $O(m^2n)$ communication for circuit size $m$. We further obtain improved efficiency in special cases, including a three-party protocol with $O(m^{4/3})$ communication, and an $n$-party protocol tolerating one corruption with $O(m^{(2n-2)/(2n-3)}n)$ communication.

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographic session key, in the "password-only" setting where the only information shared in advance is a low-entropy password. In recent years, the One-encryption EKE with 2-round Feistel cipher (OEKE-2F) protocol, a compiler from Key Encapsulation Mechanism (KEM) to PAKE, has received much attention, for the following reasons: (1) When instantiated with the Diffie–Hellman KEM, it is the most computationally efficient PAKE protocol to date that is secure in the Universal Composability (UC) framework; and (2) When instantiated with a post-quantum KEM, it provides a generic way to construct efficient PAKE protocols based on post-quantum assumptions. Unfortunately, the community cannot agree upon what the OEKE-2F protocol exactly is: part of the second protocol message is an RO hash of the KEM key, together with any number of the following: - The password, - The KEM public key, - The first protocol message, and - The KEM ciphertext. This yields 16 potential variants of OEKE-2F; only two of them have been studied in the literature, and their pros and cons are poorly understood. In this work, we present a comprehensive analysis of *all 16 variants* of OEKE-2F, proving the UC-security of each of them. The general takeaway is that the "hash everything" version requires the fewest security properties of the underlying KEM scheme, and the more items we remove from the hash, the more security requirements the KEM scheme has to satisfy — although all of the additional KEM properties are still mild. We pinpoint the exact KEM properties each version of OEKE-2F needs, and thoroughly explain the rationales. The significance of this work lies in that it helps the community converge upon the "right" version of OEKE-2F, and perhaps also in that this is the first paper by the author that is over 100 pages.

We develop (mostly) the radix-2 number-theoretic transform (NTT) and its butterflies, the twisting trick and why it never changes the transform, the freedom to use Cooley--Tukey butterflies in both directions, incomplete NTTs, Good's trick, and the ways all of these combine---closing with the coefficient-bound bookkeeping that motivates the whole toolkit. This note is intended to help implementers of postquantum cryptography, and is compressed from the author's lecture notes and slides in his Postquantum Cryptography class at National Taiwan University (2020--2025). It may be otherwise trivial for FFT experts who know the DIT--DIF equivalence inside out---except that they tend not to encounter incomplete NTTs (a term which, to the best of his knowledge, he originated in 2020) and negacyclic.

Responding to China's 2025 call for commercial cryptographic standards mandating 128-bit, 256-bit, and 512-bit security (optional 384-bit), we propose DTRU, a versatile, compact, simple, and robust NTRU-based key encapsulation mechanism (KEM). Our principal design contribution is double $E_8$ encoding, which constructs 16-dimensional lattice codes from $E_8$ with low decoding complexity. We further provide a detailed analysis of decryption-failure probability under this encoding mechanism. DTRU's design achieves a careful balance among versatility, compactness, simplicity, and robustness. To accommodate diverse application requirements, it supports multiple ring structures, including power-of-two cyclotomic rings, tricyclotomic rings, and large-Galois-group prime-degree prime-ideal number fields (LPPNF). The double $E_8$ encoding enables DTRU to achieve enhanced error correction with compact bandwidth. The design prioritizes simplicity to facilitate deployment on low-power devices, achieved by eschewing additional coefficient compression techniques and redundant invertibility checks during key generation, while enabling circuit/code reuse. Security robustness is guaranteed through parameter selections that offer adequate security redundancy, mitigating potential cyclotomic ring risks via LPPNF, and precluding sparse noise distributions in the recommended parameter sets. Complementing our theoretical advances, we present comprehensive implementations of all the parameter sets with dedicated support for C, AVX2, and ARM platforms, leveraging architecture-specific optimizations. For example, compared to NTRU-HRSS and Kyber at the same security levels, our KEM is 49%-52% more compact and 3.84–15.69$\times$ faster than NTRU-HRSS in the round-trip time of ephemeral key exchange, and is 7%-27% more compact and 1.05–1.32$\times$ faster than Kyber.

The quaternionic ideal-to-isogeny translation is a central building block of SQIsign. While the Qlapoti algorithm by Borin, Invernizzi, Corte-Real Santos, Eriksen, Mula, Schaeffler and Vercauteren significantly simplified and accelerated this step, it does not treat several technical details in sufficient depth, resulting in a flawed analysis of its failure probability. Additionally, several discrepancies between the implementation of Qlapoti and the paper's pseudocode were never analyzed explicitly. We address these shortcomings and add further improvements, resulting in a new norm equation solving algorithm with negligible failure probability. Our C implementations shows 6x to 9x speedups compared to Qlapoti's norm equation solver, and 1.3x-2.1x speedups for a SQIsign NIST2 signature (depending on NIST levels).

Adaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations. Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message. Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme. Since adaptor signatures are commonly used as building blocks in larger systems, in particular blockchain protocols, it is natural to seek a security definition in the Universal Composability (UC) framework. Tairi et al. (CCS'23) recently took a first step in this direction by proposing a UC functionality for adaptor signatures. This paper investigates UC-secure adaptor signatures as a primitive, making both negative and positive contributions. On the negative side, we show that the functionality proposed by Tairi et al. suffers from critical limitations: - The functionality fails to guarantee extractability and adaptability, which are core security properties of adaptor signatures, to higher-level protocols. - No adaptor signature scheme can realize the functionality. On the positive side, we propose a new UC functionality that faithfully captures the latest security guarantees of adaptor signatures as formalized via game-based notions by Gerhart et al. (EUROCRYPT'24). - Our functionality guarantees extractability and pre-signature adaptability in a way that is composable and meaningful for higher-level protocols. - We show that it is realizable by an enhanced Schnorr-based adaptor signature scheme that we construct. Our construction maintains compatibility with existing infrastructure and is efficient enough for practical deployment, particularly in Bitcoin-like environments.

We present a practical framework $\mathsf{DumboMix}$ for asynchronous anonymous broadcasts with guaranteed output delivery (G.O.D., a.k.a. robustness), enabling a set of $n$ servers to privately solicit $N$ messages from distinct clients, such that these messages remain secret until they are simultaneously revealed in a uniformly random order. Here, asynchronous G.O.D. ensures that all solicited messages will eventually be randomly mixed despite (i) arbitrary malicious behaviors by up to $n/3$ Byzantine servers and (ii) unpredictable network delays and jitters. At the core of $\mathsf{DumboMix}$, we first propose a couple of practical arithmetic circuits $\mathsf{DumboMix1}$ and $\mathsf{DumboMix2}$ for mixing in Shamir-secret-shared multi-party computation (MPC) over $\mathbb{Z}_p$, along with their server-optimized variants. When randomly mixing $N$ messages, their online phases require only $\mathcal{O}(1)$ multiplicative depth, expected $\mathcal{O}(N^2)$ scalar multiplications (between public and shared values), and up to $\mathcal{O}(N)$ MPC multiplications (between shared values). Moreover, assuming a robust underlying MPC framework, they guarantee that all revealed inputs are uniformly shuffled. In contrast, existing techniques fail to achieve all these performance and functionality features: The DC-net variant $\mathsf{Blinder}$ (CCS’20) may reveal a non-negligible fraction of inputs without shuffling them; Butterfly switching networks in secret-shared MPC (CCS’19) incur $\mathcal{O}(\log^2 N)$ multiplicative depth; RabbitMix (Security’24) requires $\mathcal{O}(N^2)$ MPC multiplications; and PowerMix (CCS’19) incurs $N^{3}/2$ scalar multiplications. We also implement our mixing methods within $\mathsf{DumboMPC\text{++}}$, our computation-optimized implementation of the state-of-the-art robust AMPC framework $\mathsf{DumboMPC}$ (Security’25), which provides more concretely efficient offline preprocessing while preserving asynchronous G.O.D. and optimal resilience. We then conduct extensive evaluations with $n=4$ to $31$ servers under varying network settings, revealing that our new mixing circuits achieve 44.8--65.9× (resp. 37.1--52.7×), 4.8--7.1× (resp. 3.9--5.5×), and 2.7--4.0× (resp. 5.1--7.2×) speedups over RabbitMix, PowerMix, and the butterfly switching network, respectively, when shuffling 1024 messages in LAN (resp. WAN).

The Vandermonde Knapsack problem comprises a family of algebraic variants of the Knapsack problem. This includes the Partial Vandermonde $(\mathsf{PV})$ Knapsack problem (DCC’15, ACNS’14, ACISP’18, DCC’20, Indocrypt'25), the Vanishing $\mathsf{SIS}$ $(\mathsf{vSIS})$-based commitment problem (Crypto’23, PKC'25), and related assumptions. These problems have played an important role in enabling efficient lattice-based cryptographic constructions. Recently, two independent works by Boudgoust, Gachon, and Pellet-Mary (Crypto’22), and by Das and Joux (Eurocrypt’24), proposed attacks demonstrating that certain instances of the $\mathsf{PV}$ Knapsack problem are weak. In this paper, we present new attacks on the $\mathsf{PV}$ Knapsack problem for power-of-two cyclotomic rings. By combining our techniques with the attack of Das and Joux, we show that a substantially larger fraction of keys are weak in this setting than was previously known. We then extend our attack to the integer variant of the $\mathsf{vSIS}$ commitment problem, demonstrating that certain instances are also weak for specific parameter regimes.

Traditional deniable encryption denies the \emph{content} of secret communications by allowing plausible alternative plaintexts under coercion. But the recognizable use of a deniable-encryption tool can itself defeat the purpose: a revealed plaintext becomes suspicious once a coercer detects that a non-standard tool was used, and fully encrypted, format-anomalous traffic is already detected and acted upon by deployed censorship systems. This motivates a second axis of deniability, the deniability of the mechanism's \emph{use}, which we call \emph{second-order deniability} (2OD) and treat as a design goal rather than a single achievable primitive. We decompose 2OD into two formally separate properties: \emph{content deniability} (CD), that a coercer holding all disclosed keys cannot identify the true message among decoys, and \emph{existence deniability} (ED), that the transmitted ciphertext is indistinguishable from the output of a fixed, standard reference protocol. We give game-based definitions of CD and ED, prove that the two are logically independent, and present PhantomCrypt, a construction that composes False-Bottom Encryption (CD) with Invisible Encryption (ED) under a post-quantum hybrid KEM/AEAD envelope. We are deliberate about what each guarantee buys. ED, as we define and prove it, is the indistinguishability of the transmitted ciphertext \emph{object} from a single, explicitly specified reference distribution (a standard hybrid KEM/AEAD wrapper over an unmodified cover string); it reduces to KEM and AEAD security. It is \emph{not} a claim of traffic-analysis resistance, and it is conditional on an assumption we make explicit rather than prove: that the chosen cover string is itself unremarkable to the observer. CD we prove negligible in the random-oracle model, conditioned on the secrecy of a pre-shared seed, with the residual advantage controlled by two explicit quantities: the seed's entropy relative to the field size, and a cover-concentration term that we introduce here and bound by a min-entropy admissibility condition validated on real text. Post-quantum security enters through the envelope only: ED reduces to ML-KEM and AEAD security against a quantum distinguisher, whereas the CD argument is statistical and stated in the classical random-oracle model, so we claim a post-quantum \emph{envelope} rather than post-quantum deniability wholesale and leave a QROM treatment of composed CD open. We further show that this coupling is sharp: a feasibility threshold separates a regime where strong deniability holds from one where it is information-theoretically impossible, governed by the seed-entropy margin relative to the plausible-message entropy. We are explicit about the boundary throughout: ED is object-level indistinguishability, not a defense against traffic analysis or device-side software forensics, and we state where full 2OD does and does not hold. A proof-of-concept implementation encrypts a 32-byte message with three decoys in under 10\,ms on commodity hardware, with scaling measured across cover-text length and decoy count.

A secret-sharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. Secret-sharing schemes are an important tool in cryptography and they are used as a building block in many secure protocols, e.g., secure multiparty computation protocols for arbitrary functionalities, Byzantine agreement, threshold cryptography, access control, attribute-based encryption, and weighted cryptography (e.g., stake-based blockchains). The collection of authorized sets that should be able to reconstruct the secret is called an access structure. The main goal in secret sharing is to minimize the share size in a scheme realizing an access structure. In most of this monograph, we will consider secret-sharing schemes with information-theoretic security, i.e., schemes in which unauthorized sets cannot deduce any information on the secret even when the set has unbounded computational power. Although research on secret-sharing schemes has been conducted for nearly 40 years, we still do not know what the optimal share size required to realize an arbitrary 𝑛-party access structure is; there is an exponential gap between the best known upper bounds and the best known lower bounds on the share size. In this monograph, we review the most important topics on secret sharing. We start by discussing threshold secret-sharing schemes in which the authorized sets are all sets whose size is at least some threshold 𝑡; these are the most useful secret-sharing schemes. We then describe efficient constructions of secret-sharing schemes for general access structures; in particular, we describe constructions of linear secret-sharing schemes from monotone formulas and monotone span programs and provide a simple construction for arbitrary 𝑛-party access structures with share size 2^0.5𝑛. To demonstrate the importance of secret-sharing schemes, we show how they are used to construct secure multi-party computation protocols for arbitrary functions. We next discuss the main problem with known secret-sharing schemes – the large share size, which is exponential in the number of parties. We present the known lower bounds on the share size. These lower bounds are fairly weak, and there is a big gap between the lower and upper bounds. For linear secret-sharing schemes, which are a class of schemes based on linear algebra that contains most known schemes, exponential lower bounds on the share size are known. We then turn to study ideal secret-sharing schemes in which the share size of each party is the same as the size of the secret; these schemes are the most efficient secret-sharing schemes. We describe a characterization of the access structures that have ideal schemes via matroids. Finally, we discuss computational secret-sharing schemes, i.e., secret-sharing schemes that are secure only against polynomial-time adversaries. We show computational schemes for monotone and non-monotone circuits; these constructions are more efficient than the best known schemes with information-theoretic security.

Key transparency enables a centralized encrypted messaging provider to publicly commit to the public keys it distributes, allowing clients to detect potentially malicious keys. Recent deployments by WhatsApp and iMessage demonstrate the promise of this approach, but they rely on third-party global auditors to detect misbehavior by the key server. No existing system supports auditing efficiently enough to be done by lightweight end users while also providing scalability to billions of users and short epoch latency. We present $\mathsf{Aegon}$, a key transparency scheme designed for global-scale encrypted messaging. Building on ideas from $\mathsf{IronDict}$, $\mathsf{Aegon}$ avoids per-epoch work that scales with the full dictionary size: its server computation depends only on the number of updates in the current epoch, eliminating global invariance proofs and enabling epoch latency of under a minute ($500\times$ reduction compared to $\mathsf{IronDict}$). $\mathsf{Aegon}$ further introduces a sharded dictionary design that reduces global parameters to shard-dependent sizes and enables horizontal scaling. To control long-term storage, $\mathsf{Aegon}$ uses proof caching to safely discard historical dictionary snapshots, so storage grows only with retained history. We provide a production-grade Rust implementation of $\mathsf{Aegon}$ and demonstrate practical scalability to a dictionary with $4$ billion entries, comparing it against the public codebase of WhatsApp Key Transparency ($\mathsf{AKD}$). At the throughput of $1{,}250$ updates per second, $\mathsf{Aegon}$ produces constant-size auditor proofs of under $30$ KB, verifiable in under $65$ ms and independent of the number of updates per epoch or of the directory fill. At a fully-populated $2^{32}$-entry directory, this is roughly an $80{,}000\times$ reduction in audit proof size and a $370\times$ reduction in verify time relative to $\mathsf{AKD}$. All other server and client operations remain highly efficient and comparable to $\mathsf{AKD}$, while $\mathsf{Aegon}$ achieves stronger privacy guarantees.

Sum-check and Fast Fourier Transforms (FFTs) dominate the computational cost of modern zero-knowledge proving systems, such as HyperPlonk (Eurocrypt 2023) and FRI-based schemes like DeepFold (USENIX Security 2025). Despite numerous optimizations, existing efforts remain fragmented across algorithmic, protocol, and implementation layers, leaving significant CPU performance potential untapped. We present MamaBearZKP, a co-designed framework that bridges these layers to enable high-throughput ZK proving on modern CPUs. At its core, MamaBearZKP leverages MamaBear, a 49-bit prime field ($p = 2^{49} - 2^{34} + 1$), and introduces a systematic vectorization framework specifically tailored for the AVX-512IFMA execution model. By treating field arithmetic, protocol structure, and low-level hardware primitives as a unified optimization target, MamaBearZKP achieves unprecedented efficiency. We instantiate our framework in a HyperPlonk-DeepFold prover and obtain single-thread speedups of up to $42\times$, $33\times$, $15\times$, $21\times$, and $21\times$ for ZeroCheck, ProductCheck, DeepFold Commit, DeepFold Open, and end-to-end proof generation, respectively, compared to a Goldilocks-based baseline on the same platform. With 8-thread execution, the corresponding speedups increase to as much as $64\times$, $47\times$, $81\times$, $45\times$, and $45\times$. Across our end-to-end evaluations, MamaBearZKP also achieves up to $18\times$ single-thread speedup over Plonky3, which already uses an AVX-512 BabyBear backend. Rather than resulting from isolated improvements, these gains arise from a synergistic cascading effect: the 49-bit field’s headroom enables efficient lazy reduction, which paves the way for high-performance fused fold-and-evaluate kernels. The efficiency of these kernels facilitates a unified stay-packed dataflow throughout the HyperPlonk and DeepFold stacks; it is precisely this end-to-end dataflow that materializes the hardware throughput of AVX-512IFMA into realized performance gains.

Function secret sharing (FSS) gives two parties succinct keys whose local evaluations add up to a hidden function value. Removing the dealer is the natural next step for preprocessing-based secure computation, but malicious security then requires more than checking a finished key: the generation transcript, the function the key actually computes, and every released evaluation share must all be bound to one execution. We call this the cross-phase binding problem, and we solve it. We present VeriFSS, a dealer-free two-party FSS scheme with active security, proved in the standard simulation-based framework against one static malicious corruption. The construction rests on a two-plane key: the distributed generator produces a key for the paired function $x\mapsto(f_\theta(x),\Lambda f_\theta(x))$, where $\Lambda$ is a secret global authentication scalar. The second plane makes every local evaluation an authenticated sharing for free, which yields online report binding without vector commitments, extractable hashing, or per-point interaction. It also supplies the ingredient the audit was missing: we prove a moment-fidelity lemma showing that a corrupted party cannot misreport the full-domain moments of its own sealed key except with probability $3/|E|$ over the challenge set $E$, and a shape-identification lemma showing that three moment equations pin a point function down exactly, with error $2n/|E|$ over any field. The proof isolates the coefficient of the square monomial in the support polynomial and is therefore characteristic-free; in characteristic two an odd-size equal-weight support defeats the support equation on its own, and we show the position equation takes over. A discrete-derivative reduction carries both lemmas to comparison functions, and a Galois-ring variant covers fixed-point payloads over $\mathbb{Z}_{2^k}$ by a $2$-adic valuation argument, so no non-additive lift into a binary field is ever needed. Generation costs two rounds and five field elements per party per level; certification adds $O(n)$ elements with no dependence on the domain size, and a dynamic cross-domain aggregation certifies arbitrarily many heterogeneous instances under one challenge and a constant number of rounds. We then lift the general-purpose FSS gates of Boyle et al. (EUROCRYPT 2021): every gate that is a public affine post-processing of a constant number of DPF/DCF evaluations---interval containment, splines, ReLU, arithmetic shift, bit decomposition, zero test, table lookup---inherits active security at no additional online cost. We evaluate our construction using a C++ implementation that certifies keys over $\mathbb{F}_{p^2}$ ($p=2^{61}-1$) and $\mathrm{GF}(2^{128})$, realises the gate layer, and agrees bit‑for‑bit on every exported test vector. A certified DPF key at $n=16$ takes $5.7$ ms to generate and $3.3$ ms to certify. Certified DPF keys are $5.4\%$ larger than the semi-honest dealer-free baseline at $n=16$, and aggregated certification traffic converges to $1{,}282$ bytes per instance while the round count stays constant. Replaying the certified execution between two processes over TCP shows what that constancy is worth: at a $50$ ms round trip a session takes $1.15$ s, and the figure is unchanged whether one key or sixty-four are certified together, so wide-area certification of a whole preprocessing session is latency-bound by a single key. A campaign of $1{,}400$ injected generation deviations plus shape, moment and release forgeries is rejected without exception in six of seven deviation classes; the seventh is rejected in exactly the $105$ of $200$ trials in which the attacked index bit is one, which is a quantitatively exact confirmation of the single-bit selective-failure predicate that we model explicitly in the ideal functionality, matching the leakage profile of the best known actively secure distributed DPF.

Since the seminal work of Carlini et al. at CRYPTO 2020, cryptanalytic model extraction has shown neural-networks parameters can be recovered from black-box queries. Existing attacks are largely built around piecewise-linear phenomena. Softmax attention, as the key component of the transformer architecture, presents a different extraction landscape: its nonlinearity is smooth and sequence-dependent, which renders the existing piecewise-linear-based method inapplicable. Recent work has investigated the learnability of a single-head attention model, while in the multi-head case, the parameters of the multi-head attention layer cannot be uniquely identified from value queries alone. In this paper, we propose the first attack against multi-head attention models. We formalize the extractable representative of multi-head attention and give a polynomial-time algorithm for extracting the parameters of the canonical representative model. We also test our algorithm end to end under finite precision, and successfully extract the parameters of a softmax attention model with token dimension 8 and 6 heads to accuracy $2^{-51}$. Moreover, we overcome the limitation that existing parameter extraction algorithms for one-layer single-head Transformers fail when the ReLU feedforward networks (FFNs) include bias terms. The effectiveness of our approach is demonstrated through model extraction attacks in finite-precision experiments. These results show that softmax normalization itself exposes exploitable algebraic structure, extending cryptanalytic extraction beyond ReLU-centric techniques.

Category theory is a mathematical theory of composition, widely used in logic, computing, and physics. Here we apply it to give a theory of secure composition. In particular, we provide a categorical treatment of Canetti's Universal Composability (UC) framework for systems with a static number of parties and sessions, often termed UC for static systems, yielding four benefits. First, we present our results graphically yet retain rigor by applying a standard categorical technique known as string diagrams. In particular, our formulation of the composition theorem can be graphically verified with a short sequence of diagrams, while remaining translatable to equations and amenable to formal verification. Second, categories let us generalize so that our results extend beyond interactive Turing machines to other forms of computation, such as quantum computation or domain-specific languages. Third, categories help us drop some unnecessary restrictions of UC (e.g., our adversary can be a computational network rather than a single Turing machine); we prove equivalence between our variant and the usual UC, showing no expressiveness is lost. Finally, the categorical perspective leads us to identify and correct some minor technical oversights in the standard formulation of simple UC.

Nowadays, governments are world-wide pushing towards building infrastructures to intercept, decrypt and prevent communications among citizens with the goal of catching criminals. The recent notion of anamorphic encryption proposed by Persiano et al. [Eurocrypt 2022] faces the risks of abuses derived from such infrastructures that could be maliciously leveraged to realize the phantom menace of large-scale mass-surveillance programs. Several recent papers showed positive results on the existence of anamorphic encryption schemes, mostly confined to basic settings. In this work we consider extreme scenarios where in addition to obtaining secret keys, the authority actively tries to sanitize ciphertexts removing covert communication. Despite anamorphic encryption might look impossible to achieve in the above settings, we give new definitions and somewhat surprising positive results in two scenarios: Rerandtopia and Interceptopia. Our main construction consists of two layers of encryption. Interestingly, when carefully instantiated, our scheme achieves a notion of re-randomizable CCA encryption that outperforms the state of the art in terms of assumptions and efficiency.

Multivariate signature schemes are among the few post-quantum candidates capable of providing very short signatures, but designing secure constructions has proven challenging. HFE-based schemes such as G$e$MSS were compromised by algebraic MinRank attacks. This motivates the HFE$_\text{IP}^-$ framework, which combines IP and minus modifiers to address these attacks. We introduce James and D-James, the latter achieving signatures of only 156 bits at the 128-bit classical security level and 348 bits at the 256-bit classical security level, among the shortest signatures reported for practical post-quantum public-key signature schemes, with estimated signing and verification costs comparable to those of G$e$MSS. The main technical contribution is the introduction of Dragon terms, which decouple the number of public equations from the hash output length, allowing the signature size to be reduced independently of the security parameter. We characterize the algebraic structure introduced by Dragon terms and show that it does not enable known MinRank attacks when combined with the HFE$_\text{IP}^-$ countermeasures. We also show that the known differential attack does not appear to extend to the minus variant. We further present parameter sets over both binary and small non-binary finite fields. For small values of $q>2$, the public-key size decreases by up to a factor of 10, while signature size and computational cost remain close to the binary case.

Masking is a well-established software countermeasure against side-channel attacks, yet even algorithmically correct masked implementations can leak on real hardware once the compiler has performed instruction selection, register allocation, and stack allocation. Existing approaches either rely on leakage simulation, which is tied to a specific power model and computationally expensive, or on formal verification of the source program, which does not capture the effects introduced by the subsequent compilation stages. We address this gap from within the compiler and propose a leakage detection pass for the Jasmin language, integrated into its formally verified pipeline and operating on the intermediate representation before register and stack allocation. Rather than simulating power traces, the pass implements a configurable, microarchitecture-oriented leakage model that tracks the contact between shares, secrets, random values, and public values, making the root causes of the detected leakage explicit and enabling the detection of masking-order reductions. We validate the pass on 60 dedicated Jasmin test snippets covering all considered leakage sources and category combinations, and intend it as the foundation for a subsequent compiler stage that automatically removes the detected leakage, thus constituting a first step toward secure compilation.

A $(k,n)$-robust combiner for a primitive $\mathcal{P}$ combines $n$ candidate instantiations of $\mathcal{P}$ into a single scheme that remains secure as long as at least $k$ of them remain secure. Robust combiners have been extensively studied for primitives such as hash functions, public-key encryption, and oblivious transfer, but much less is known in the setting of cryptographic groups. In this work, we initiate the study of robust combiners for cryptographic groups in Maurer's generic group model (GGM), where algorithms access group elements only through abstract algebraic operations. We ask whether one can combine $n$ candidate groups into a single group that remains secure provided that at least $k$ of the underlying groups remain secure. A natural baseline is the direct-product construction, which preserves search hardness but fails for decisional assumptions and incurs substantial representation overhead. We show that these limitations are in fact inherent. Our first result is a complete impossibility for the decisional Diffie--Hellman assumption: for every polynomially bounded $n$ and $k$ with $k<n$, there is no generic $(k,n)$-robust combiner for cryptographic groups that preserves DDH security. Our second result gives a tight threshold for search assumptions in the regime where $n$ and $k$ are fixed constants. For the discrete logarithm problem, robust generic combination is possible when the combined group order is large enough to encode the secrets of $n-k+1$ components; concretely, if $\log N \ge (n-k+1)\lambda$, where the component groups have distinct $\lambda$-bit prime order, then a robust combiner exists. Conversely, if $\log N \le (n-k)\lambda$, then no generic $(k,n)$-robust DLog-secure combiner exists. These results identify a fundamental limitation of robust hedging at the group level. Decisional assumptions such as DDH cannot be robustly combined in the GGM, while search assumptions admit robustness only at essentially optimal representation cost. Consequently, robustness for group-based cryptography must in general be achieved at higher layers, such as protocol design or key derivation.

The uniform multivariate quadratic (UMQ) assumption states that it is hard to find a zero of a uniformly generated MQ function. It is the average-case hardness assumption about the MQ problem. In this paper, we investigate the relations among the UMQ assumption, the MQ one-wayness (MQOW) assumption, and the MQ second-preimage resistance (MQSPR) assumption. We show that UMQ and MQSPR tightly imply each other, and MQOW tightly implies UMQ. Then, we show that UMQ implies MQOW when $m\leq n+O(\log\lambda)$, where $n$ is the number of variables, $m$ is the number of MQ equations, and $\lambda$ is the security parameter. In particular, when $m\leq n+O(1)$, this implication is tight. As a corollary, we show that MQSPR implies MQOW under the same condition $m\leq n+O(\log\lambda)$, which is weaker than the compression condition $n=m+\omega(\log\lambda)$ required for the implication from SPR to OW for general function families. In particular, our result covers the square case $m=n$ as well as mildly overdetermined MQ systems satisfying $m=n+O(\log\lambda)$.

In this note, we formally show that the recent algorithm by Simon (ePrint:2026/1591, August 11 2026) does not extract the least-significant bit of the dihedral coset problem (DCP) secret with non-negligible guessing advantage, and therefore does not solve DCP. We emphasize that our result is not merely about Simon's analysis of his algorithm; we are showing directly that the algorithm cannot possibly work. Our no-go encompasses a much broader class of algorithms than the specific algorithm by Simon. The main message of our no-go is that an algorithm for DCP following the template of the reduction by Regev (SIAM Journal on Computing, 2004) will probably have to make extensive use of the classical Fourier labels in the uncomputation stage. On the other hand, the algorithm by Simon can be implemented, up to error $\mathsf{poly}(n)2^{-n/3}$, using only the most-significant third of the classical Fourier labels, and therefore cannot succeed. To help with verifiability, we release Lean 4 code for our results, available at https://github.com/sragavan99/lean-ePrint-2026-1591-refutation.

Poseidon [Grassi, Khovratovich, Rechberger, Roy, and Schofnegger; USENIX'21] is an arithmetization-oriented (AO) hash function designed to be efficient in real-world zero-knowledge (ZK) applications. We present GSR, a generalized S-box skipping gadget that absorbs a single initial full round and $t-2k$ partial rounds without increasing the polynomial degree of the Poseidon polynomial system with state size $t$ and input-output constraints $2k$. By restricting the subspace of the total constraints satisfying solutions, independent of the rounds constants and MDS matrix selection, the distinguisher expends input degrees of freedom to linearize the internal state transitions where the dense algebraic mixing usually occurs. This maps a computationally infeasible polynomial system into a bounded, low-degree ideal parameterized by $k$ free variables. We show how to use the gadget to construct a probability 1 distinguisher over $t-2k+1$ rounds of Poseidon. We then show how this distinguisher can be used as a basis for interpolation-based attacks. We go on to present experimental solutions to the CICO-1 problem over 28 out of 31 rounds and CICO-2 problem over 25 out of 31 rounds in the setting set by the Ethereum Poseidon initiative (i.e., using the KoalaBear field with $t=24$ and $\alpha=3$). Crucially, since the subspace restriction approach is tuned only by $t$ and $k$, our results apply to the Poseidon structure regardless of the choice of round constants, MDS matrix, S-box exponent $\alpha$, or field size $p$.

Proof-of-work allows Bitcoin to boast security amidst arbitrary fluctuations in participation of miners throughout time, so long as, at any point in time, a majority of hash power is honest. In recent years, however, the pendulum has shifted in favor of proof-of-stake-based consensus protocols. There, the sleepy model is the most prominent model for handling fluctuating participation of nodes. However, to date, no protocol in the sleepy model rivals Bitcoin in its robustness to drastic fluctuations in participation levels, with state-of-the-art protocols making various restrictive assumptions. In this work, we present a new adversary model, called external adversary. Intuitively, in our model, corrupt nodes do not divulge information about their secret keys. In this model, we show that protocols in the sleepy model can meaningfully claim to remain secure against fully fluctuating participation, without compromising efficiency or corruption resilience. Our adversary model is quite natural, and arguably naturally captures the process via which malicious behavior arises in protocols, as opposed to traditional worst-case modeling. On top of which, the model is also theoretically appealing, circumventing a barrier established in a recent work of Malkhi, Momose, and Ren.

Many important applications of fully homomorphic encryption (FHE) require arithmetic on *high-precision* plaintexts, e.g., from the ring $\mathbb{Z}_p$ for a huge prime or power-of-two modulus $p$. The classic FHE schemes are poorly suited to this, because the inverse error rate of fresh ciphertexts, and the error growth under homomorphic multiplication, are both larger than $p$, which results in large and inefficient parameters. While there are now several works addressing this problem, the landscape for *exact* (as opposed to approximate) FHE is highly fragmented: known solutions either work only for certain rare plaintext moduli having very special forms (sometimes using non-standard ciphertext rings that lack other important features for FHE), or have quite complicated and high-latency constructions. This work gives a very simple, general, and efficient technique for high-precision exact FHE, in which the error rates and growth match those of classic schemes for *exponentially smaller* precision. The runtimes can scale only *quasi-linearly* (versus quadratically for classic schemes) with the plaintext precision $\log p$, and are fast in practice. Also in contrast to all prior works, our technique works for *any integer modulus* and over *any underlying (number) ring*---or even with no structured ring at all, making it the first solution that can be based on plain LWE. Moreover, it is *fully compatible with prior FHE techniques* for fast ring arithmetic, plaintext packing and SIMD operations, bootstrapping, etc. For typical parameters and security levels, our (preliminary, unoptimized, single-threaded) implementation does homomorphic $\mathbb{Z}_{2^{64}}$-multiplication in just tens of milliseconds, and obtains a four- to five-fold increase in multiplicative depth versus classic FHE schemes.

In this work, we present a new framework for signature-free, post-quantum secure authenticated key exchange (AKE) that simultaneously satisfies: (1) exchanging at most two standard ciphertexts of a key encapsulation mechanism (KEM); (2) computational symmetry; (3) perfect forward secrecy (PFS); (4) strong resilience to secret-state exposure; (5) strong resistance to decryption-error attacks; (6) admitting instantiations based on the native structure of \textsf{ML-KEM} under the \textsf{MLWE} assumption; and (7) provable security in both the random oracle model (ROM) and the quantum-accessible random oracle model (QROM) under the post-id $\mathsf{eCK}\mbox{-}\mathsf{PFS}$ framework. This resolves several fundamental open questions in the literature. The core technical building block is a new cryptographic primitive, called an \emph{authenticated forward-secure} KEM (AFS-KEM), which unifies authentication and forward secrecy within a single KEM abstraction and may be of independent interest.

The relationship between cryptography and learning theory has long been a central theme in the foundations of theoretical computer science: cryptographic primitives can imply hardness of learning, while hardness of learning can in turn be used to construct cryptographic schemes. Recent works have begun exploring analogous connections in the quantum setting, relating the average-case hardness of learning quantum states (AHL) to cryptographic primitives such as one-way state generators (OWSG). Despite recent progress exploring this for pure states, the relationship for mixed states has remained an open question. In this work, we prove that the existence of AHL for mixed quantum states is equivalent to the existence of inefficiently verifiable one-way state generators (IV-OWSGs). As a consequence, this relates mixed-state AHL to EFI pairs. Moreover, as a corollary of existing results, we obtain a separation between IV-OWSGs and OWSGs relative to the SWAP oracle.

A blind signature scheme allows a user to interact with a signer to obtain a valid signature on a message, while ensuring that the signer cannot learn any information on the message being signed, nor link a given couple message-signature to the specific interaction that produced it (blindness). In round-optimal (i.e., two-move) blind signature schemes, a user sends a request (typically a commitment) for a message, and the signer responds with a signature. To achieve blindness, the resulting blind signature usually consists of a zero-knowledge proof of knowledge of a valid signature from the signer on a request. This reliance on zero-knowledge proofs has become the main bottleneck in reducing the blind signature size. In particular, state-of-the-art lattice-based blind signature schemes are instantiated based on the zero-knowledge proof system from [Lyubashevsky et al., EUROCRYPT, 2022], which results in blind signatures of at least 22 KB. In this work, we carefully design a blind signature protocol following the classical lattice-based Σ-protocol as in [Ducas et al., CRYPTO, 2013], so that the last component naturally forms a short preimage of the hash of the message, as a classical GPV signature. As a result, this removes the need for zero-knowledge proofs in the blind signature. Eventually, this design allows us to obtain a significantly more compact blind signature of size 4.7 KB, with concurrent security under the Module-SIS assumption. As a trade-off, our protocol may require more than one round with small probability, due to the rejection sampling in lattice-based Σ-protocols. Under our proposed parameters, however, the expected number of rounds for honest users can be as small as 1.1, which is very close to optimal. To minimize the number of rounds, we require users to prove that they failed to derive a blind signature in the previous round, before starting a new one. This technique yields a moderately looser bound on the expected number of rounds for malicious users, who will be forced to terminate in at most 2.6 rounds.

Harvesting ciphertext from cloud storage needs no quantum computer; decrypting it later does. That gap is the harvest-now-decrypt-later exposure: anything protected by RSA or ECDH today that must stay secret for decades is already compromised. Small and medium-sized enterprises are least able to respond: they neither run the infrastructure on which their data sits on nor employ a cryptographer. Bespoke migration suits firms with security budgets; a managed key service relocates trust rather than removing it. The obstacle is architectural, not cryptographic. We present Quantum Cloud Guard (QCG), a software-only three-layer architecture. No prior SME-oriented system combines its three elements: client-side hybrid post-quantum encryption, self-hosted key custody with client-verifiable ML-DSA-87 signatures on served keys, and an integrated application-layer abuse-prevention gateway. Files never leave the client: each is sealed under AES-256-GCM, its key wrapped to an ML-KEM-1024 public key from the enterprise’s key service. The enterprise alone administers it; it signs every key with ML-DSA-87, so a client that pinned it detects substitution. Separating key custody from data custody is the point: a provider holding both can read the data. On a 24 MHz STM32F407, ML-KEM-1024 key generation takes 40.8 ms and decapsulation 44.0 ms; on the server every post-quantum operation stays sub-millisecond, signing adding 0.24 ms per request. The service runs on a 4.49 EUR/month virtual server. Under sustained flooding, the in-process gateway Sentinel Gate rejected 98.8% of attack traffic while a legitimate client’s median latency moved from 621 to 625 ms. Being single-source, this shows filtering effectiveness, not DDoS resilience.

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.

We introduce Noisy Torus Conjugation (NTC), a lattice assumption in which a short secret is confined to a non-split maximal torus of $GL_k(R_q)$ and acts by conjugation on a uniform matrix, the result being masked by a short additive error. NTRU is the $k=1$ member of the family. Passing to $k \ge 2$ changes the geometry of the underlying lattice in two specific ways. The planted module occupies a fraction $1/(2k)$ of the published lattice's dimension, against NTRU's $1/2$; and the norm-map shortcut that governs the overstretched regime is blocked once the conjugated matrix is required to be uniform over the full matrix algebra instead of the torus. We develop the structure theory of the assumption: marginal uniformity of each component, invariance along the torus orbit, a rigidity theorem identifying the full set of short solutions, and a reduction from search to decision. On it we build an IND-CCA key encapsulation mechanism whose passive security reduces tightly to NTC together with one isolated decisional assumption. At NIST categories 1, 3 and 5 it reaches public keys within 1.08 to 1.16 times Kyber's and ciphertexts 2.0 to 2.1 times Kyber's. The new assumption is not load-bearing but purchasable. Widening the key distribution to the smoothing parameter of the key lattice would make the public key statistically uniform and remove it altogether, leaving IND-CPA on module-LWE and hence on a worst-case problem. We price that variant at a factor 3.4 on the public key and 4.0 on the ciphertext. It rests, however, on a regularity statement not established for the completely split rings our transform uses; we isolate that statement as a conjecture and give a modulus class for which it is not needed. Concrete parameters are selected with an estimator calibrated against the published core-SVP figures of Kyber, and validated against a hybrid meet-in-the-middle model whose single free constant is fitted on Kyber. The fatigue predictions underlying the modulus window are tested further by lattice reduction. We reduce small instances of the published lattice against NTRU controls of identical dimension, determinant and planted-vector norm, and at every modulus the NTRU plant is discovered as a dense sublattice while the sparser NTC plant is not. A companion paper builds a Fiat-Shamir-with-aborts signature from the same assumption. The assumption is new and has no worst-case reduction; we state throughout what is proved, what is heuristic, what is measured, and what remains open.

We prove an algebraic analogue of Pataki-Tural lemma (Pataki-Tural, arXiv:0804.4014, 2008) -- the main tool in analysing the so-called overstretched regime of NTRU. Our result generalizes this lemma from Euclidean lattices to modules over any number field enabling us to look at NTRU as rank-2 module over cyclotomic number fields with a rank-1 dense submodule generated by the NTRU secret key. For Euclidean lattices, this overstretched regime occurs for large moduli $q$ and enables to detect a dense sublattice in NTRU lattices leading to faster NTRU key recovery. We formulate an algebraic version of this event, the so-called Dense Submodule Discovery (DSD) event, and heuristically predict under which conditions this event happens. For that, we formulate an algebraic version of the Geometric Series Assumption -- an heuristic tool that describes the behaviour of algebraic lattice reduction algorithms. We verify this assumption by implementing an algebraic LLL -- an analog of classical LLL lattice reduction that operates on the module level. Our experiments verify the introduced heuristic, enabling us to predict the algebraic DSD event. UPD: minor notation fixes.

We present the Pilot--Sailor Framework, an LLM-guided system for studying theoretical open problems in symmetric cryptography. Pilot proposes intermediate statements and proof plans. Sailor attempts formal proofs, and the proof assistant admits only checked declarations to the verified context. We apply this methodology to Boolean-function theory and symmetric cryptanalysis through fourteen mathematical case studies, comprising complete resolutions, corrected formulations, counterexamples, and scoped quantitative advances. In particular, we prove the original pointwise Tu--Deng conjecture for all word lengths and admissible residues. We further characterize equality in this bound: if \(t\) has \(z\) zero bits, equality holds exactly when every cyclic gap between consecutive zeros is at least \(z\). This criterion also gives a closed formula for the number of equality cases for each \(z\). We also prove that, for \(n=2k\geq6\) and \(k<m<2k\), every mapping \(F:\mathbb F_2^n\to\mathbb F_2^m\) satisfies \(\operatorname{NL}(F)\leq2^{n-1}-2^{n/2-1}-2\). This improves both the covering-radius estimate and the bound obtained from Nyberg's obstruction and integrality. Using an exact computer-assisted spectral classification, we also prove that the maximum nonlinearity of a balanced Boolean function in eight variables is 116, resolving whether the value 118 can occur. Beyond the well-known long-standing problems highlighted above, we also establish new results for ten further research questions in symmetric cryptography.

The main message of this paper is that several seemingly different circular-style primitives are existentially equivalent. In particular, somewhat surprisingly, we show that hinting PRGs (Koppula and Waters, CRYPTO 2019) are equivalent to secret-key encryption (SKE) schemes satisfying key-dependent-message (KDM) security. As a conceptual centerpiece, we introduce key-dependent-shift (KDS) security for weak pseudorandom functions (PRFs), and show that they serve as a convenient hub connecting these primitives. We also show that KDS secure weak PRFs imply other cryptographic primitives with circular-style security, such as linear-resistant PRGs (Hajiabadi et al., ITC 2023) and hinting weak PRFs (Alamati and Patranabis, ASIACRYPT 2022), all of which are thus existentially equivalent to KDM secure SKE and hinting PRGs as well. Hence, KDS secure weak PRFs can be thought of as a unifying umbrella for circular-secure cryptographic primitives. As another application of our new notion, we show that KDS security enables new constructions of public-key encryption (PKE) satisfying randomness-dependent-message (RDM) security and correlated-product secure trapdoor functions (TDFs). Our key technical contribution is a generic construction of KDS secure weak PRFs from any KDM secure SKE.

We construct the first folding scheme that simultaneously achieves six desirable properties: plausible post-quantum security, pay-per-bit commitment costs, field-native arithmetic (the sum-check and norm checks run purely over a small field), support for general (non-SIMD) constraint systems, small-field support (e.g., Goldilocks), and low recursion overheads. No existing scheme satisfies all six: group-based schemes (e.g., HyperNova) lack post-quantum security and are tied to large elliptic-curve fields; lattice-based schemes (e.g., LatticeFold) require expensive ring arithmetic, lose pay-per-bit costs, and impose SIMD constraints; and hash-based schemes (e.g., Arc) incur large verifier circuits. We present two lattice-based folding schemes for CCS, an NP-complete relation generalizing R1CS, Plonkish, and AIR, called Neo and SuperNeo. Neo satisfies five of the six properties but requires SIMD constraint systems; SuperNeo removes this restriction and satisfies all six. SuperNeo also natively supports CCS relations over arbitrary extension fields of the field underlying the Ajtai commitment, without relying on an NTT embedding. Both run a single invocation of the sum-check protocol over a small field extension and achieve pay-per-bit costs via new folding-friendly instantiations of Ajtai commitments under the Module-SIS assumption. At the core of our constructions are two new norm-preserving embeddings of field vectors into ring vectors that respect an evaluation homomorphism required for folding. We also introduce interactive reductions, a framework that generalizes reductions of knowledge and enables modular security proofs for composed lattice-based protocols.

Authenticated data structures are widely used to compute compact digests of evolving collections of elements and to support efficient verification of element inclusion. However, the authenticated collection often should not grow forever: older elements may expire and no longer require verification. Many implemented append-only approaches, for example used in Certificate Transparency (CT), do not directly support this setting, since previously accumulated elements remain part of the authenticated state indefinitely. In this work, we introduce a pruning accumulator, a stateful accumulator that supports both incremental addition of new elements and pruning of an old prefix of previously accumulated elements. The resulting digest represents the unpruned sequence, while pruned elements are removed from the authenticated state. Unpruned elements continue to support proof-of-inclusion verification, proof updates, update verification, and consistency checks. This captures applications that require authenticated, incrementally maintained state over a moving window of elements. We present two constructions of Merkle-tree-based pruning accumulators, both with efficient accumulation, prefix pruning, proof generation, proof updating, and verification. The constructions preserve the standard Merkle-tree style of verification for active elements while reducing long-term storage requirements. We provide formal definitions, correctness and security analysis, an open-source implementation, and experimental evaluation demonstrating the performance benefits of pruning.

BitVM2 brought arbitrary program execution to Bitcoin, yielding the first light-client-based bridge to its second layers and reducing the trust required at setup to a single honest participant. Its successors, BitVM3 and BABE, move the disputed computation off-chain into Garbled Circuits (GCs), cutting worst-case on-chain dispute costs by roughly three orders of magnitude and so opening participation beyond well-capitalized operators; BABE in turn cuts the off-chain storage and setup costs of BitVM3's garbled circuits by a comparable factor. What still reaches the chain, however, is bulkier than it need be. BitVM2 commits its data with compact Winternitz one-time signatures (WOTS), whereas BitVM3 and BABE must reveal GC input labels on-chain and so fall back on far bulkier Lamport signatures, which play two roles at once: GC input labels and Bitcoin-verifiable commitments. WOTS cannot simply be substituted, because its hash chains are monotonic---an evaluator holding one state's preimage can hash forward and obtain several active labels on a single input wire, destroying the circuit's privacy. Recovering BitVM2's compactness therefore calls for a practical GC whose input labels are WOTS signatures---a construction that has remained out of reach. We close this gap with a non-interactive \emph{WOTS-to-Lamport translation gadget}: the garbler commits on-chain using compact WOTS chains, and the evaluator expands them off-chain into exactly the orthogonal Lamport labels the GC consumes, learning nothing about the mutually exclusive ones. A naive translation table that enumerated messages would be exponentially large. Two symmetries bring it down to quadratic: reconstruction from a Shamir sharing depends only on \emph{how many} shares are held and not on \emph{which}, which collapses the exponentially many messages onto the single checksum weight WOTS already computes; and monotonicity, the very property that made WOTS unusable, orders an evaluator's access by inclusion. We model the gadget as a garbling scheme and prove it adaptively private. Applied to BABE, it restores WOTS-scale commitments to a GC-based protocol, cutting total on-chain script size by more than $3\times$ and bringing dispute transactions within Bitcoin's standardness limit.

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.

ML-KEM is IND-CCA2 secure only because of one check inside decapsulation: the receiver re-encrypts the message it recovered and returns the true shared secret only if the result matches the received ciphertext exactly. This is the Fujisaki–Okamoto (FO) check. wolfSSL implemented it in hand-written SIMD assembly, and on two backends it compared fewer than all of the ciphertext bytes. The x86-64 AVX2 path compared 1536 of 1568 bytes; the ARM64 NEON path compared roughly half. These bugs were documented as a weakening of IND-CCA2 security, in that a tampered ciphertext can slip past the check. We show they are worse than that. The bytes the check skips carry the tail of the decryption noise, and that noise is an exact linear function of the secret key. An attacker who varies those unchecked bytes and watches the decapsulation output reads the noise off one coordinate at a time. Stacking the measurements gives an overdetermined linear system in the secret, which we solve by ordinary least squares with no lattice reduction. The measurement is a plaintext-checking oracle, the same primitive that key-mismatch attacks use. What is new is where it comes from. Reading it off the unchecked v-tail, rather than from chosen sparse-u ciphertexts, means it survives even when u is fully validated, as on AVX2, so the standard "validate all of u" hardening does not close it. The price is queries, 10⁵ to 10⁶ against a few thousand for key-mismatch, so the contribution is reach rather than efficiency. We recover most of the ML-KEM-1024 private key end-to-end against the shipped binaries on both backends: 98.0% of the 2048 secret coefficients at 400 ciphertexts on AVX2, and 98.5% at 600 on NEON, reaching the full key with more ciphertexts (the verified reference model recovers all 2048 at about 1300 ciphertexts). The cost appears to track the geometry of which bytes go unchecked more than their number: NEON leaves about 2.5× more coordinates unchecked than AVX2 yet needs more ciphertexts. We conclude that an incomplete FO comparison is a key-recovery vulnerability, and should be triaged as one.

Nonlinear feedback shift registers (NFSRs) are fundamental building blocks for modern stream-cipher constructions. An $n$-stage NFSR $f$ is classified as irreducible when the output sequence set of $f$ does not contain the output family of any NFSR of order less than $n$. Existing research has established upper and lower bounds for the density of irreducible NFSRs, confining this value within the range of 0.4461 to 0.4834. This study tightens these bounding intervals with high accuracy, reducing the original 0.04 gap down to only $8\times10^{-6}$.

In this work, we revisit multi-round public-coin proof systems by enabling the use of their simulators and extractors within other cryptographic protocols. Although research on multi-round public-coin proofs has rapidly progressed, their simulators and extractors typically differ from the 3-move (e.g., Sigma protocols) setting in interface and behavior, and are rarely studied from this viewpoint. Prior work [Abe et al., Eurocrypt ’26] introduced the notion of critical-round zero-knowledge, showing that, for some classes of protocols, multi-round ZK simulators can be as useful in protocol constructions as the 3-move ones. In this paper, we focus on soundness and introduce critical-round special soundness, a property that enables multi-round witness extractors to be used in protocol design in a manner analogous to 3-move special soundness. We show that several existing multi-round public-coin proof systems satisfy this property and present three applications: - A witness sharing scheme that verifiably secret-shares an NP witness without interaction among recipients. It can be realized in a hash-based way by combining MPC-in-the-Head with secret sharing. - An offline trapdoor-extractable trapdoor commitment scheme where a trapdoor is extracted immediately upon a double opening. Offline trapdoor extractability was previously known from 3-move public-coin proofs, but no general construction from multi-round proofs was known; our approach closes this gap. - A parameter improvement for the multi-round Fischlin transform [Rotem–Tessaro, Crypto’25]. The improved parameter extends the design space of the multi-round Fischlin transform and reduces the prover’s complexity in practice. Overall, our results clarify how multi-round public-coin proofs can support protocol design beyond their traditional role as stand-alone proof systems.

Secure group messaging protocols, now standardized by the IETF as Messaging Layer Security (MLS), provide end-to-end encryption for billions of users. The cryptographic core of these protocols is continuous group key agreement (CGKA), a primitive designed to maintain a shared secret among a dynamic group while providing security guarantees like forward secrecy and post-compromise security. A critical challenge for CGKA is achieving efficiency, particularly sublinear complexity (in the size of the group), for group operations. While practical tree-based protocols like TreeKEM offer logarithmic complexity in ideal (so-called "fair-weather") scenarios, their performance degrades to linear in the worst-case, and even realistic average-case, scenarios. This performance collapse raises the fundamental question of whether any CGKA protocol can achieve provably sublinear worst-case complexity. Prior work has established significant barriers to this goal, including black-box impossibility results ruling out efficient constructions from standard public-key encryption. Theoretical solutions circumvent these barriers using powerful tools like indistinguishability obfuscation ($i\mathcal{O}$), but these constructions are astronomically inefficient and often provide weaker security guarantees, such as lacking forward secrecy. This leaves a wide gap between practical protocols with poor worst-case guarantees and theoretical solutions that are entirely impractical. In this paper, we narrow this gap by presenting the first CGKA protocol that achieves provably logarithmic worst-case complexity for both computation and communication. Our first construction is based on a falsifiable and plausibly post-quantum assumption called decomposed learning with errors (decomposed LWE), and achieves basic CGKA security (only group members know the key) and post-compromise security, but not forward secrecy. We then show how to extend our scheme in the random oracle model to achieve optimal security (including forward secrecy) while retaining worst-case sublinear communication. However, the forward-secure refresh operation takes linear time in the group size, while still producing compact ciphertexts. Our work is the first to establish that worst-case efficient CGKA is theoretically possible from simple falsifiable assumptions. Moreover, it offers a plausible roadmap towards concretely efficient constructions.

Secure key leasing (SKL) is a quantum cryptographic primitive that enables the leasing of decryption keys to delegated users with the guarantee that, once revoked, the lessees irreversibly lose decryption capability. A key feature that makes SKL practically relevant is classical revocation: the ability to revoke keys at any time and from anywhere, without relying on a quantum channel. In this work, we revisit SKL schemes for public-key encryption (PKE) and identity-based encryption (IBE), and present a new approach for concrete efficiency under the standard Learning With Errors (LWE) assumption. First, we refine the security analysis of the Dual-Regev SKL-PKE scheme with classical revocation from [Ananth, Poremba, and Vaikuntanathan, TCC 2023; Ananth, Hu, and Huang, TCC 2024], establishing security under the polynomial hardness of LWE with polynomial modulus. Together with the resource efficiency of the Dual-Regev-based construction, our analysis shows that this approach yields the most quantum-efficient known SKL-PKE scheme. Second, we present a simple and efficient construction of selectively secure SKL-IBE with classical revocation from standard LWE. Our approach directly extends the Dual-Regev SKL-PKE within the IBE framework of [Agrawal, Boneh, and Boyen, Eurocrypt 2010], avoiding garbled circuits and obfuscation-based assumptions and achieving improved concrete efficiency over prior generic approaches.

Multi-party computation (MPC) enables multiple parties to jointly process sensitive data without revealing their inputs. However, existing MPC protocols remain inefficient for high-dimensional sparse data. In plaintext, sparse linear algebra algorithms address this problem using two fundamental primitives, Scatter and Gather. We propose SparseMPC, an outsourced MPC protocol that securely implements Scatter and Gather and uses them to perform sparse matrix multiplication. Our protocol supports an arbitrary number of data owners and provides a low memory footprint, constant round complexity, and low communication cost. Beyond sparse matrix multiplication, SparseMPC provides a foundation for efficiently realizing a broader class of sparse computations in outsourced MPC.

Autonomous agents are increasingly used to plan and execute paid workflows on behalf of users. Existing agentic-payment frameworks support this delegation through merchant-admission authorization credentials but require the user to specify merchants before execution. However, complex paid workflows often span multiple services and merchants, and agents may choose among them based on intermediate results. This creates two limitations: (1) requiring the user to choose each merchant in advance either limits the agent's adaptability or forces the user back into the loop; and (2) reusing a stable identifier across merchants lets observers link separate paid calls and infer the user's broader intent. To address these limitations, we introduce MinMandate, which grants adaptive merchant selection within user-approved task bounds and derives fresh per-call payment views without introducing a stable cross-merchant identifier. Extensive experiments on AgentDojo tasks demonstrate that, when 50% of merchants are unavailable, MinMandate improves task success by 32.7 percentage points on average across four tested planners compared with an AP2 baseline that preauthorizes one merchant per service class. Reintroducing a reusable public payment-layer handle in the Stable Handle ablation raises attacker task-recovery success by 27.4 percentage points on average, isolating the privacy cost of a stable join handle. The code is available at https://github.com/Zora-G/minmandate.

This paper provides upper bounds on the success rate (SR) of side-channel attacks (SCAs) on masked implementations. We present a formal security proof of additive masking over any finite abelian group—including Boolean and arithmetic maskings—through new reductions from strong noisy leakage (SNL) to the probing model. Unlike existing proofs relying on noisy leakage (NL) and random probing (RP), our proof introduces a novel security notion named leakage energy (LE), which enables a stronger bound. Our proof reveals the necessary and sufficient condition for asymptotic security of additive masking in both the NL and mutual information frameworks, which includes a resolution to an open problem in TCC 2016. Our claims are validated through numerical evaluations. As an application of our theorems, we propose a binary block-cipher based leakage-resilient primitive based on a variant of XEX, which claims $d$-th order SCA security of arithmetic masking by design under some assumptions, enabling efficient OCB-style authenticated encryption with implementation cost of $O(d)$.

Certified deletion enables a party to prove that it has erased the sensitive information contained in a quantum state. Bartusek and Raizes (CRYPTO 2024) gave the first secret-sharing scheme with privately verifiable deletion. Subsequently, Katz and Sela (EUROCRYPT 2025) constructed secret-sharing schemes with publicly verifiable deletion under computational assumptions. Constructing such a publicly verifiable scheme without cryptographic assumptions remains open. In this work, we introduce an intermediate notion called unanimously verifiable deletion, where deletion certificates are verified jointly by the parties in the protocol. While private verification relies on the dealer and public verification allows any third party to verify deletion, unanimous verification assigns the verification responsibility to the parties in the secret-sharing scheme themselves. We construct an information-theoretically secure linearly homomorphic threshold secret-sharing batch scheme with adaptive unanimously verifiable deletion. In particular, to obtain its linear-homomorphic property, we exploit a linearly homomorphic structure of BB84-type states that enables linear operations on encoded values while preserving certified deletion. More generally, this structure can be used to upgrade certain primitives with certified deletion to their linearly homomorphic counterparts. As another major contribution, we demonstrate an application of this batch scheme by constructing outsourced multi-party computation (MPC) protocols for arbitrary arithmetic circuits. Our outsourced MPC has honest classical clients and quantum servers, and achieves adaptive unanimously verifiable deletion security in the trusted-preprocessing and security-with-abort setting, supports public output reconstruction, and is secure against malicious, rushing quantum server adversaries for any $t<n/2$, provided that throughout the online execution, at most $t$ corrupted servers remain undeleted and at least $t+1$ honest servers remain undeleted. Moreover, after successful finalization, all servers may be corrupted without revealing any information about the clients' inputs beyond the public output.

Noise flooding is a standard defense against decryption attacks on approximate homomorphic encryption, but its security proof is unusually sensitive to composition. Replacing each of \(q\) adaptive decryption answers with a statistically close simulation and applying an ordinary hybrid argument loses linearly in \(q\). The cryptographic proof instead accumulates conditional Kullback-Leibler (KL) costs and converts to statistical distance once, giving the parameter-critical square-root loss. We machine-check this argument using Rocq and SSProve. Given any fully homomorphic encryption scheme that is approximately correct and IND-CPA secure, we formalize a reduction for every \(q\)-query IND-CPAD adversary and prove \[ \Pr[\mathsf{IND\text{-}CPAD}_{\mathsf{NF}}^{\mathcal A}=1] \leq \beta_{\mathsf{CPA}}(\mathcal B_{\mathcal A,q}) + \frac{\sqrt{qn}}{2\gamma}. \] where \(n\) is the plaintext dimension and \(\gamma\) is the flooding-width multiplier. Our proof constructs a new relational program logic over SSProve semantics. Its Pythagorean judgment composes conditional KL budgets without converting them to statistical distance, and a verified trace compiler lifts a local oracle rule to arbitrary adaptive programs with a single final conversion.

Since the invention of Bitcoin in 2008, blockchain technology has evolved from a simple decentralized ledger into a complex, multi-functional financial system spanning multiple layers. Despite this evolution, the cryptographic primitives foundational to this trustless system are now threatened by the emergence of quantum computers. While the necessity of Post-Quantum Cryptography (PQC) migration is widely acknowledged, blockchain remains an extremely challenging domain for cryptographic migration due to its decentralized architecture and long-term security requirements. Today, the evolving complexity has rendered simple cryptographic migration models insufficient at system scale. Furthermore, human factors rooted in economic rationality and intertwined incentives, such as investors’ pursuit of short-term profits and miners’ mining profitability, have emerged as critical obstacles to migration. This paper provides a comprehensive analysis of the challenges and current status of blockchain PQC migration as of December 2025. Specifically, we analyze the components requiring migration and their technical challenges, while systematically organizing operational barriers, including trade-offs found within migration strategies and stakeholder interests. Furthermore, we propose guidelines for future research initiatives that academia and the blockchain community should collaboratively address. By synthesizing ongoing community discussions and existing literature, this work aims to establish a foundation for navigating the path toward achieving quantum-resistant blockchains.

Anamorphic cryptography targets the scenario in which a dictator does not forbid the use of cryptography but requires all users to reveal their secret keys to them. Thus, the dictator can decrypt all honestly generated ciphertexts. The approach for bypassing this is to identify spots, such as random nonces, in existing cryptographic protocols in which secret messages can be hidden using an additional secret double key. So far, the literature mostly focused on identifying such spots in simple primitives like public-key encryption or signatures; only recently, an initial work identified limited spots in Signal's Double Ratchet Algorithm. We are the first to leverage the statefulness of cryptographic communication protocols to employ continuously updated double states and, thereby, achieve Forward Security: Even if the adversary (i) observes all traffic, (ii) knows all users' regular secret key material at any stage of the protocol execution, and (iii) at some point learns the secret double state, the entire protocol execution looks benign although covert messages were previously hidden in the traffic anamorphically. We formalize this notion and also cover robustness and authenticity, which appear to be particularly relevant in the messaging context. In this new model, we study four of the most relevant messaging protocols and identify hiding spots therein: Signal's Double Ratchet, Signal's Triple Ratchet, Apple's PQ3, and the two-party core of the Messaging Layer Security Standard. We focus on the cryptographic parts of these protocols and, despite their complexity, identify surprisingly few anamorphic hiding spots. We prove that all these protocols offer forward secure, authenticated anamorphic channels and we evaluate their bandwidths: While 16 bits can be embedded in every epoch of the Double Ratchet, Triple Ratchet and PQ3 provide 176 bits, respectively 256 bits, of bandwidth per post-quantum epoch, and MLS provides 688 bits per epoch.

Threshold signatures reduce the risk of single-key compromise by distributing signing authority, but each key share remains exposed to compromise of the software and infrastructure that execute the protocol. We present RSS, a threshold signing service that runs share generation and signing inside Trusted Execution Environments (TEEs). We integrate GG20 threshold ECDSA, FROST, and threshold BLS into the EnGINE experimentation framework and evaluate local and Google Cloud deployments using AMD SEV-SNP and Intel TDX. Our experiments separate distributed key generation (DKG), preprocessing, and online signing, and cover up to 40 logical protocol participants distributed across four physical hosts or confidential VMs (CVMs). In matched-platform comparisons, confidential execution adds limited overhead relative to protocol and deployment effects. DKG is the main scaling bottleneck: for 40 participants, it completes within seconds in the evaluated configurations, whereas signing completes in tens of milliseconds. Threshold BLS is approximately twice as slow as FROST for comparable values of $n$ and $t$. These results establish the performance feasibility of executing threshold-signature workloads inside CVMs under benign-operation assumptions. The evaluation does not cover a complete attestation-bound provisioning lifecycle, persistent-state rollback protection, or Byzantine fault behavior.

Zero Knowledge Encryption is a term widely used by vendors of cloud-based password managers. Although it has no strict technical meaning, the term conveys the idea that the server, who stores encrypted password vaults on behalf of users, is unable to learn anything about the contents of those vaults. The security claims made by vendors imply that this should hold even if the server is fully malicious. This threat model is justified in practice by the high sensitivity of vault data, which makes password manager servers an attractive target for breaches (as evidenced by a history of attacks). We examine the extent to which security against a fully malicious server holds true for four leading vendors who make the Zero Knowledge Encryption claim: Bitwarden, LastPass, Dashlane and 1Password. Collectively, they have more than 60 million users and 23% market share. We present 12 distinct attacks against Bitwarden, 7 against LastPass, 6 against Dashlane and 6 against 1Password. The attacks range in severity, from integrity violations of targeted user vaults to the complete compromise of all the vaults associated with an organisation. The majority of the attacks allow recovery of passwords. We have disclosed our findings to the vendors and remediation is underway. Our attacks showcase the importance of considering the malicious server threat model for cloud-based password managers. Despite vendors’ attempts to achieve security in this setting, we uncover several common design anti-patterns and cryptographic misconceptions that resulted in vulnerabilities. We discuss possible mitigations and also reflect more broadly on what can be learned from our analysis by developers of end-to-end encrypted systems.

We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $\Omega(\sqrt{n})$ error under pure differential privacy and $\Omega(\sqrt{n}/\log n)$ error under strong approximate differential privacy, whereas computational security permits $O(1)$ error. In Klauck's honest, nonpreemptive, message-preserving model, we give an $O(n)$-communication quantum protocol with pure $\varepsilon$ quantum differential privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+\gamma,$ for every $\gamma>0$. For approximate $(\varepsilon, \delta)$ QDP, an exact finite-cycle hockey-stick calculation yields strictly smaller error, while preserving the $O(1)$-versus-$\Omega(\sqrt{n}/\log n)$ separation for $\delta=o(1/n)$. Thus, quantum communication achieves $O(1)$ information-theoretic error, matching the accuracy available classically only under computational assumptions. The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We also separate this model from weaker prescribed-channel privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal quantum messages as a resource for privacy, but leave open whether a separation exists in the malicious setting.

A key challenge in digital credential systems is revocation, that is, the ability to revoke credentials post-issuance and verify their status upon presentation. While anonymous credentials enhance privacy over classical credentials (e.g., by providing unlinkability), they complicate revocation. Existing revocation schemes for anonymous credentials often suffer from high client or verifier computation, long delays before revocation takes effect (e.g., epoch-based settings), or require updates to all users with each revocation. We present an efficient, real-time revocation system for anonymous credentials with decentralized revocation authorities based on a novel primitive called Private Record Certification (PRC). PRC enables users to obtain a certificate for a record stored in a server-managed database without the servers learning which record was requested. This primitive is of independent interest, and we construct it by combining techniques from private information retrieval and secure multi-party computation. Our revocation scheme outsources its costs to the revocation authorities and has minimal overhead for clients and verifiers, while ensuring the communication costs are sublinear in the number of credentials for the revocation authorities. We build a prototype and demonstrate that our system achieves sub-second real-time latency at a scale of over 1 billion credentials, with an online operational cost of 2.5$ per server for processing 1 million PRC queries.

We give a two-transcript key-recovery attack on TALUS-MPC in TALUS v4. TALUS was presented in the second round of the NIST Threshold Call Preview Talks. In Algorithm 3 of TALUS v4, the committee's nonce polynomials are evaluated at all $N$ points so that any $T$ parties can sign. An adversary controlling the coordinator and $T-1$ parties can reuse the same pooled nonce with two quorums whose only common members are corrupt. Each participating honest party uses its signing share once, yet the coordinator obtains $\mathbf{z}_0=\mathbf{y}+c_0\mathbf{s}_1$, $\mathbf{z}_1=\mathbf{y}+c_1\mathbf{s}_1$. The nonce cancels on subtraction. Moreover, no invertibility assumption in $R_q$ is needed: the response equations lift to $\mathbb{Z}[X]/(X^{256}+1)$, and every nonzero $c_0-c_1$ is invertible in the cyclotomic field $\mathbb{Q}[X]/(X^{256}+1)$. Thus two distinct challenges recover $\mathbf{s}_1$ exactly; since the TALUS v4 public key includes the full $\mathbf{t}=\mathbf{A}\mathbf{s}_1+\mathbf{s}_2$, the adversary also recovers $\mathbf{s}_2$ and forges signatures.

Oblivious Key-Value Stores (OKVS) (Garimella et al., CRYPTO 2021), once encoded, provide indistinguishability over keys and random values. This is an important property in many secure computation applications, such as private set intersection and multi-key searchable encryption. We introduce an Updatable Oblivious Key-Value Store with access control (UOKVS), a dynamic extension of OKVS that supports insertions over time. We provide meaningful security in the presence of updates by equipping UOKVS with fine-grained access control. As a building block in UOKVS, we provide the first analysis of oblivious insertions for Cuckoo hashing, which may be of independent interest. We show the application of UOKVS to multi-key searchable encryption where a data owner wishes to share parts of a multimap with multiple clients. We construct an oblivious multimap with insertions from UOKVS and private information retrieval (PIR). Unlike prior multi-key searchable encryption schemes, our construction supports sharing without replicating data across authorized users, substantially reducing storage costs in addition to stronger privacy guarantees. We implement our multi-key searchable encryption construction on a dataset containing up to 24 million entries using the Enron email dataset. For keywords matching 100 documents on a WAN, query processing completes in $0.6$ seconds using FrodoPIR as the underlying PIR protocol. By comparison, the scheme of Wang and Papadopoulos (Cloud Computing 2023) achieves a query time of $0.6$ seconds and also incurs data replication and leaks access patterns. Our construction reduces leakage, maintains performance, and only requires a $3.1$x storage overhead.

We show new constructions for pseudorandom quantum states (PRS) and pseudorandom function-like quantum state (PRFS) generators satisfying scalability, which means the security parameter can be much larger than the number of qubits, quantum accessibility, which means the adversary can provide quantum input, and adaptivity, which means the adversary can query it adaptively. We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). This naturally gives the first construction for scalable, quantum-accessible, and adaptive PRFS assuming quantum-secure one-way functions. Compared to prior PRFS works, we use a stronger definition of quantum accessibility in which the adversary can be ancilla-assisted, i.e., the input state may not be pure and could be entangled with other quantum registers. Thus, our result also gives the first (fully) quantum-accessible PRFS. Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS. This new construction may be helpful in simplifying the microcrypt zoo.

Secure aggregation is a core primitive for privacy-preserving federated learning, enabling a server to compute aggregates of client updates without learning individual inputs. Recent protocols have explored committee-based designs to reduce client overhead and tolerate weakly connected participants. However, existing approaches still incur communication and computation costs that scale with the number of clients and/or the size of model updates. This becomes a serious bottleneck in interaction between the server and the committee, given that model updates are high-dimensional and the committee is a small set of clients. We present Lighthouse, a new secure aggregation protocol that supports one-shot client communication and achieves constant committee computation and communication overhead with the server, independent of both the number of clients and the size of the input vector. Our protocol attains the best-known round complexity of two rounds, matching OPA (CRYPTO 2025) and TACITA (ePrint 2025) and improving upon Flamingo (IEEE S&P 2023) and Willow (CRYPTO 2025). Our core technical contribution is a novel application of recent advances in batched threshold encryption, which enables succinct server–committee interaction while preserving security and correctness. Beyond asymptotic improvements over prior works, Lighthouse yields substantial concrete efficiency gains: For an aggregation with 1024 clients, we reduce server-to-committee communication by over 100× and committee-to-server communication by over 300× compared to Flamingo and Willow. Also, we present an extension that supports dynamic client participation, a critical requirement for practical deployments at scale, while preserving the asymptotic and concrete efficiency of the static protocol for clients.