Falcon and the forthcoming FN-DSA standard based on it generate signatures via discrete Gaussian sampling, during which power consumption leaks information about secret-dependent intermediate values. While prior attacks exploit sampler leakages individually or in pairs, we present a unified key-recovery framework that fuses three observations from each SamplerZ call: the signed-exponent class e(k) of the integer center, the random-sign bit b, and a multi-class proposal magnitude z0. These fused observations define magnitude-preserving intervals or rays for accepted sampler outputs. Leveraging an exact public linear relation that holds in the absence of modular wraparound, we map these candidate sets directly into slab and halfspace constraints on the secret key. The resulting system is solved via smooth softplus interval regression and bounded integer reconstruction with public-key validation, entirely bypassing computationally intensive lattice reductions such as LLL or BKZ. For PQClean Falcon-512 running at-O3 on an ARM Cortex-M4, our 17-class center classifier achieves 99.34% call-level accuracy on held-out test signatures from the profiling keys. The resulting attack recovers all 50 disjoint evaluation keys using at most 34 signatures (median 11), with a median post-classification key-recovery runtime of 17.54s per key. Furthermore, on c-fn-dsa, where center conversion relies on a single constant-time CLZ instruction, a reduced-resolution 7-class classifier combined with proposal leakage still recovers 38 of 50 keys within 200 signatures. These findings demonstrate that instruction-level normalization alone cannot prevent key recovery, underscoring that side-channel countermeasures for FN-DSA must protect all sampler leakage channels jointly.

Recent MPC-in-the-Head (MPCitH) signatures increasingly rely on aggressive GGM-tree optimizations to reduce signature size and computational cost, culminating in __secret-key-root correlated GGM trees__ as used in SBC (Huth and Joux, CRYPTO 2024), MQOM (NIST PQC Standardization for Additional Signature Round-2, 2024), and rBN++ (Kim, Lee, and Son, EUROCRYPT 2025). While this technique yields substantial compression, it introduces a dependency loop in the proof (Kosuge and Xagawa, CiC 2026(3)). We analyze MQOM and resolve this circularity by providing EUF-CMA security proofs for a slightly modified variant. The modifications consist of incorporating a salt into the input of a hash function and modifying the evaluation domain to ensure that all evaluation points are nonzero. For the resulting variant of MQOM, we prove EUF-CMA security for the GF(2) parameter sets in the random-oracle plus ideal-cipher model, assuming EUF-NMA security, standard one-wayness, and a heuristic conjecture on matrices. Our proof combines the H-coefficient technique with one-wayness, which may be of independent interest. We also prove EUF-CMA security in the (quantum) random-oracle model, where block-cipher-based hash functions are modeled as random oracles. The proof relies on EUF-NMA security and partial-guessing one-wayness (Feneuil and Rivain, ASIACRYPT 2026), which can be reduced classically to partial-domain one-wayness.

The rapid deployment of Graph Neural Networks (GNNs) within Machine Learning as a Service (MLaaS) has opened up new privacy concerns. Both sensitive graph data and proprietary GNN models are submitted to and processed in third-party MLaaS platform for training and inference. To alleviate those concerns, recent efforts have been made to design tailored secure computation protocols for GNNs. Unfortunately, existing designs cannot accomplish security, functionality, and scalability simultaneously. They leak a certain degree of graph information, offer limited support on secure training of GNNs, and can hardly scale to large graphs. In this paper, we design and implement OblivDGL, an oblivious deep graph learning framework for secure GNN inference and training. Our design is inspired by Deep Graph Library (DGL), an industrial practice for graph learning. At its core, we distill the secure computational patterns of GNNs into a generalized form, and empower both secure GNN training and inference through a novel oblivious message passing paradigm. To realize such a paradigm, we design a new oblivious graph representation, and realize it by function secret sharing (FSS), a lightweight secure computation technique with low latency. Compared to prior secure GNN systems, OblivDGL achieves the most stringent privacy guarantees, i.e., revealing no private information except for the total number of edges and nodes. One standout feature of OblivDGL is the scalability of processing encrypted graphs by carefully tailored parallelization designs. Extensive evaluations on four benchmark graph datasets demonstrate that, compared to state-of-the-art secure GNN frameworks, OblivDGL reduces communication cost by up to 1024x and achieves up to 14.3x speedup in runtime during secure training. For secure inference, OblivDGL achieves up to 754x lower communication and a 4.19x speedup.

The hint framework of Dachman-Soled, Ducas, Gong, and Rossi (CRYPTO 2020), together with the later too-many-hints analyses from May and Nowakowski (ASIACRYPT 2023) and Cao, Jiang, and Cheng (CRYPTO 2025), gives a classification of secret-dependent hints and LLL-breaking hint thresholds for LWE schemes. These values are now frequently adopted as the default benchmark for side-channel security evaluation. We show that applying them as a security metric is problematic. DDGR categorizes hints based only on their local algebraic form, while the threshold analyses assume uniformly sampled hint vectors. Neither captures how the specific algebraic form of a hint governs the geometry of the resulting sparsified lattice. A hint’s class label and the corresponding uniform threshold therefore cannot, on their own, capture its real cryptanalytic power. We illustrate this mismatch with two forms of structured leakage that naturally appear in ring and module lattice implementations, validated via synthetic experiments on Kyber-512. NTT-domain residues qualify formally as mod-$q$ hints, yet they recover the full Kyber-512 secret with roughly half as many hints as the uniform mod-$q$ bound predicts. Finite-precision FFT samples fall into the weaker approximate-hint class, and still only need $25\%$--$55\%$ of the hint budget required for uniform perfect hints. The gap stems from algebraic structure: these hint families carry additional ring structure that enables tailored lattice recovery strategies, a distinction invisible under the uniform-sampling model. We do not propose new attack optimizations. Our findings indicate that DDGR hint classes and too-many-hints thresholds are syntactic descriptions, not standalone security metrics for real leakage traces. Evaluating a side-channel leak requires considering the algebraic structure of the hint vectors, not just their category and quantity.

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, which be named Eagle, whose encryption and decryption can be completed in linear time. The key consists of 10 variables, for the attacker, in the case when only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations about ten unknown variables $(w_{1}, w_{2}, ..., w_{9}, w_{10})$ together with some implicit variables which are generated by the encryption process. In this paper, we will prove that there is no universal algorithm without brute-force searching at least one variable during the process of verifying four variables $(w_{1}, w_{2}, w_{3}, w_{4})$ whose computational complexity is not greater than solving the ten variables. After performing elimination the implicit variables, the problem of verifying the four variables will be equivalently transformed into a series of general quintic equations about one variable $w_{9} \oplus w_{10}$ with coefficient given by other four variables $(w_{5}, w_{6}, w_{7}, w_{8})$, according to the conclusion that ``there is no algebraic solution to quintic equations", we can't establish a system of algebraic equations only containing the other four variables $(w_{5}, w_{6}, w_{7}, w_{8})$. Without solving the other four variables, the problem of verifying the four variables $(w_{1}, w_{2}, w_{3}, w_{4})$ is equivalent to solve the slope and intercept of a line given the x-coordinates or y-coordinates of several points on it (points with x-coordinates known cannot have their y-coordinates known, and vice versa), this implies that there is no universal algorithm without brute-force searching at least one variable to verify the four variables $(w_{1}, w_{2}, w_{3}, w_{4})$. Since the computational complexity of brute-force searching any single variable is exponential, thus the complexity of cracking the key is exponential. Thus decryption is a one-way function, and according to ``the existence of one-way function means P$\neq$NP", solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm, which be named $Eagle^{*}$. The key of $Eagle^{*}$ is composed of three independent variables. Given any plaintext ciphertext correspondences, the problem of verifying any two variables in the key is equivalent to solving a system of quintic equations. Based on the conclusion that there is no algebraic solution to quintic equations, we assert that there is no fast algorithm to verify any two variables, and thus the computational complexity of cracking the key is equal to the computational complexity of completely exhausting the three variables. In addition, we conducted an in-depth analysis that without cracking the key, it is not possible to directly decrypt new ciphertext by simply collecting a large number of ciphertext plaintext correspondences. Due to the fact that ciphertext consists of two parts, one part is completely random, while the other small part is calculated using plaintexts, keys, and random numbers, and their distribution is also completely random, thus $Eagle^{*}$ is resistant to all forms of linear and differential attacks.

In e-voting, a mix-net is a widely used system for shuffling votes in order to guarantee voter privacy. The core principle is as follows: (1) N voters cast their votes; (2) a sequence of mix-servers shuffles the N encrypted ballots, thereby randomly permuting the underlying votes; and (3) trustees jointly decrypt the shuffled ballots to compute the tally. This approach, however, relies heavily on trusted parties after the voting phase and raises serious robustness issues. For example, what happens if the mix-servers disrupt the protocol, or if trustees lose the decryption key during the tallying phase? A recent incident in the IACR board election illustrates this problem: one of the three trustees involuntarily lost their key, requiring the entire community to restart the vote. We introduce OMIX, an offline-mixing architecture for self-tallying elections: trustees prepare public functional decryption keys embedding a hidden random permutation before voting, voters then cast encrypted ballots, and anyone can compute the shuffled tally without further trustee participation. Function-hiding inner-product functional encryption supplies the key mechanism, and a voter-assisted correction phase accommodates dropouts. The main technical component is a verifiable offline shuffle of a matrix of encrypted functional keys. We extend linearly homomorphic signatures with tag-binding and two-dimensional tags: row tags support hidden row permutations, while column tags bind entries to their respective voters. In the certified-input model, these properties allow trustees to certify matrix transformations, with final proof size and verification cost independent of the number of mix-servers. Together, these components enable distributed preparation and public certification of permutation keys within a client-lightweight voting architecture. Each voter registers and casts a ballot with computation and communication independent of N, while preprocessing per trustee, public helper-key size, and tallying work are quadratic. This establishes a foundation for self-tallying elections with offline mixing and opens the way to further improvements in system-wide efficiency.

The contribution vector (convec) of a secret-sharing scheme is the vector of its normalized share sizes. The average and maximum coordinates of a convec give, respectively, the average and maximum information ratios of the scheme. Obtaining superlinear lower bounds on these quantities for unrestricted perfect secret sharing has remained a challenging open problem for about four decades. In this paper, we study substitution, a natural way to build complicated access structures from simpler ones: one participant of an outer access structure is replaced by an inner access structure. Given secret-sharing schemes for the two factors, the standard forward construction composes them into a scheme for the composite access structure. We study the converse question. Given an arbitrary scheme for the composite access structure, we ask to what extent its convec admits a reverse factorization into convecs for the outer and inner factors, up to a common multiplicative loss. Exact reversal is false: we give a counterexample whose optimal reverse factor is \(8/9\), with a composite scheme that is scalar-linear over every finite field. On the positive side, we prove that a factor \(1/2\) is always attainable, and that every fixed instance admits a strictly larger factor. For a recursive family built from Csirmaz’s classical access structure \(\mathcal C_k\), whose distinguished set has size \(k\), we identify a critical reverse factor that determines when the resulting lower bound becomes superlinear. This critical factor exceeds one half by only an amount of order \((\log k)/k\). Crossing it yields superlinear lower bounds, while any fixed positive excess above one half gives a route to superpolynomial lower bounds. Using only Shannon inequalities, the corresponding recursive factor cannot cross the critical value. Thus any improvement sufficient to pass this threshold must exploit constraints beyond the Shannon inequalities.

Robust combiners are a standard way to hedge cryptographic assumptions: given several candidate constructions, they produce one construction that remains secure as long as one candidate is secure. In favorable cases, such combiners also yield universal constructions. We ask whether this paradigm applies to cryptographic primitives whose public outputs must be both pseudorandom and sparse. Our first result gives a negative answer for pseudorandom codes (PRCs), i.e., error-correcting codes whose codewords are computationally indistinguishable from uniform strings. We prove that secret-key PRCs admit no black-box robust combiner. The impossibility holds even for the weakest meaningful guarantee, where the combined scheme is required to be secure when all but one candidate PRC are secure. We then show that the obstruction is not specific to error correction. In the sparse ciphertext regime, public-key encryption with pseudorandom ciphertexts also admits no black-box robust combiner. This stands in contrast to ordinary IND-CPA encryption, for which robust combiners are easy to obtain. Thus the requirement that public outputs look uniformly random introduces a genuine barrier to black-box assumption hedging, and rules out the standard combiner route to universal constructions for these primitives.

We present a security analysis of the messaging service known as LINE, a popular platform used daily by millions of users in East and Southeast Asia – most notably Japan, Taiwan, Thailand, and Indonesia. More specifically, we focus on its underlying custom end-to-end encryption (E2EE) protocol, known as Letter Sealing v2. Our findings show that Letter Sealing allows a TLS Machine-in-the- Middle attacker or malicious server to violate integrity, authenticity, and confidentiality of communications. The stateless design of the protocol allows message replay, reordering, and blocking attacks without the user being notified. The lack of origin authentication facilitates impersonation attacks, in which the authorship of mes- sages in one-to-one or group chats can be forged by malicious users colluding with the adversary. Lastly, stickers and URL previews present a notable leakage of plaintext, which leads to a violation of confidentiality. To verify the correctness of our findings, we mounted a Machine-in-the-Middle attack on an iOS device, yielding the device’s outgoing traffic and the corresponding server responses. Utilizing this setup, we experimentally verified our attacks against the authentic LINE application and an independent implementation. We discuss our findings in comparison to the state-of-the-art E2EE protocols, and conclude that Letter Sealing does not satisfy the requirements expected from a modern E2EE messaging protocol.

Digital identity systems are being deployed worldwide to enable secure, privacy-preserving authentication. In this regards, Europe's EUDI Wallet mandates selective attribute disclosure and unlinkable authentication, effectively requiring anonymous credentials. Yet current proposed solutions omit them because they lack device binding: tying a credential to a secure hardware element on the user's device to prevent cloning or sharing. Device binding encodes a device public key in the credential and, at presentation time, produces a fresh signature under the hardware-protected secret key -- a proof-of-possession (PoP). While academic solutions for device binding exist, they require pairing-friendly curves, whereas consumer phones are restricted to ECDSA over P-256. In this work, we bridge this gap by enabling device binding of pairing-based credentials using the device's standard ECDSA signature as the PoP. To explore the efficiency–complexity trade-off of such solution, we present three constructions. Our most efficient solution generates unlinkable binding proofs of size ~1.5kB in under ~400ms using a simple arithmetic circuit, whereas the most conservative circuit-free approach matches this proving time at ~122kB. All solutions follow a common blueprint expressed in the reductions of knowledge framework (Crypto 2023), which enables modular composition of zero-knowledge proofs and eases both security analysis and implementation. This framework has previously been mainly used in a theoretical context, and our work demonstrates that it is a powerful tool to design, analyze and implement advanced real-world systems.

We review the Bulletproofs++ construction which replaces the bit-decomposition inner-product argument of Bulletproofs with a reciprocal set-membership argument over base-$16$ digits. We present a self-contained specification of the $64$-bit range proof as well as a general batched variant parametric in the batch size $M$ and bit width $b$ and prove honest-verifier zero-knowledge and exact-form knowledge soundness. We describe the evaluation and optimizations of our Rust implementation over Ristretto255, which proves up to $7.8\times$ and verifies up to $4.5\times$ faster than regular Bulletproofs. Finally, we correct two formulas of the original paper: the affine $T^3$ term of the scalar polynomial $p_s(T)$ carries a factor of $2$, and the slot-$0$ component of the blinding vector $r_S$ carries the opposite sign.

ZMAC+ is a tweakable-block-cipher-based MAC proposed by List and Nandi in ToSC 2017 with claimed beyond-birthday-bound security. We show that a tag-swap mechanism previously observed for a hypothetical two-output extension of DoveMAC also applies to the published ZMAC+ construction. For two-block tags, we give a distinguisher with constant advantage and a fresh-message forgery with constant success probability using $O(2^{n/2})$ queries in the ideal-TBC model, where $n$ is the block length. An internal collision between two message families exchanges their tag blocks; a common extension preserves this relation and leads to a forgery with one additional authentication query. We identify a counting error in the published Lemma~4 and prove a corrected aggregate differential bound. The resulting PRF and MAC upper bounds match the birthday query threshold for bounded message lengths and two-block tags, under explicit field-order conditions. The distinguisher extends to every legal fixed output length $d\ge2$, and the forgery to every legal even $d$. We also retain ZHash and separate the output domains. Under stated field-order, length, and domain-capacity conditions, this modification admits an adaptive PRF bound of order $q^2/2^{n+\min(n,t)}$ for bounded lengths. Finally, a one-query counterexample shows that the ZAE security theorem must retain the per-message length restriction required by its counter-in-tweak encryption component.

Provers for succinct non-interactive arguments of knowledge (SNARKs) perform arithmetic over a large field for soundness, even when the witness entries are a few bits wide, which inflates both prover time and memory usage. Recent work makes individual SNARK components bitwidth-aware, so that a lower witness bitwidth means faster proving and lower memory usage, but these techniques cover only part of the prover and exploit the structure of specific fields, typically binary ones. We introduce Mikros, a framework for end-to-end bitwidth-aware SNARK construction based on algebraic vector packing. We pack vectors of length \(N=m\kappa\) over a base field \(\mathbb{F}\) into length-\(m\) vectors over a degree-\(\kappa\) extension field \(\mathbb{E}\), which turns length-\(N\) relations over \(\mathbb{F}\) into length-\(m\) relations over \(\mathbb{E}\) and makes existing linear-time extension-field protocols bitwidth-aware. This technique thus unifies bitwidth-aware inner-product proofs, Hadamard-product proofs, and polynomial commitment schemes, previously obtained by separate constructions, and yields the first bitwidth-aware grand-product proof, hence the first bitwidth-aware permutation argument. Composing them gives bitwidth-aware SNARKs for circuit satisfiability over extensions of arbitrary small fields. For a single instance of circuit satisfiability, the prover cost is proportional to the effective bitwidth, the combined bitwidth of the witness entries and the wiring-position encodings; across instances of the same circuit, the position encoding is amortized and the per-instance cost is proportional to the witness bitwidth. Although Mikros does not rely on binary-field structure, its prover is \(2.19\times\), \(2.55\times\), and \(1.85\times\) faster on batches of \(256\) SHA-256 compressions, Keccak permutations, and BLAKE3 compressions than Flock (B\"unz \etal, IACR ePrint 2026), the state-of-the-art bitwidth-aware SNARK over binary-extension fields.

Under-constrained arithmetic circuits are a recurring source of soundness failures in zero-knowledge applications: after fixing the public statement, a malicious prover may be able to assign a security-relevant wire in more than one way while still satisfying the circuit. Existing tools attack this uniqueness question with solver-based checking, direct polynomial solving, abstract interpretation, or fuzzing. We study a complementary algebraic diagnostic based on exact Jacobian linear algebra. The method separates three notions that are often conflated: first-order rigidity at a sampled witness, finite algebraic dependence on an irreducible component, and uniqueness over the circuit field. At a satisfying assignment, the kernel of the constraint Jacobian augmented with rows fixing the statement coordinates is the Zariski tangent space of the corresponding fibre scheme, so motion of a target coordinate in this kernel certifies infinitesimal freedom at that witness. Under suitable separability hypotheses, the associated differential representation also recovers component-wise algebraic dependence, while a certified triangular degree calculus provides multiplicity bounds for locally rigid targets. An exact sparse implementation classifies public benchmarks (chain, tree, Merkle-path, and EdDSA topologies, up to 66,000 constraints) in at most a second per instance on commodity hardware, has been exercised on industrial gnark circuits in the 6k-60k-constraint range, and carries over to PLONKish standard-gate systems in a measured end-to-end check (lookup arguments remain future work); a checkable degree budget (m < log2 p quadratic constraints) discharges the separability hypothesis at gadget scale. Conversely, when the rank computation itself certifies a smooth witness (full row rank, or full rank after vacuous guard rows are discharged by explicit local-redundancy identities), effective Lang-Weil bounds convert infinitesimal freedom into at least p/(2·deg C) distinct finite-field values of the target among genuine satisfying assignments, so in that regime the local diagnostic becomes a sound non-uniqueness certificate. For quadratic constraints, an additional affine-line certificate converts a tangent vector into p explicit satisfying assignments whenever every quadratic directional coefficient vanishes; its checker uses sparse field evaluations and needs no smoothness assumption. A second-order parabola variant extends the construction to curved families through one further linear solve together with a quadratic condition on its solution space, certifying targets that first order cannot move. Projected tangent dimension distinguishes the number of free target wires from their independent degrees of freedom. Where witnesses come from is treated as part of the method. In the studied gadgets, the circuit's own generator computes advice by division and refuses at exactly the compatible exceptional inputs that expose the defects. Three separate experiments measure construction from the constraint system instead. On five defective circuits, propagation, one-input symbolic solving, and rational-function propagation with resultant elimination supply compatible exceptional inputs for all five with no solver in the loop, including a Pedersen point distinct from the solver's own counterexample. On the fifty-one circuits the solver reports safe, an algebraic and symbolic construction sweep finds no output-moving certificate under stated budgets, with 86 of 102 circuit-method combinations producing a witness. A bounded 108-trial pilot compares honest generation, uniform and structural mutation, and the relational solver under identical queries and a shared eight-second end-to-end wall cap, showing complementary coverage on the tested instances. The principal limitation is witness locality, and we state it as a theorem rather than an observation: an explicit 20-constraint instance admits two satisfying assignments agreeing on the statement such that every target is first-order rigid at one while all five targets are infinitesimally free, indeed p-fold free, at the other. The same separation occurs in deployed code: in a measured 2,396-constraint gnark 0.14.0 scalar-multiplication gadget, an honest witness exposes no free target wires, a degenerate adversarial witness exposes five, and an explicit second satisfying witness confirms the freedom. We therefore position Jacobian analysis as a scalable candidate detector and localisation tool, paired with witness construction and solver- or certificate-based confirmation, with the witness-construction stage itself measured rather than assumed.

Despite ensuring both consistency and liveness, state machine replication (SMR) protocols remain vulnerable to adversaries that manipulate transaction order, causing, e.g., MEV attacks. To mitigate this, researchers have proposed new variants augmented with order-fairness. However, existing protocols that employ dependency graphs, such as Aequitas (Crypto 2020), Themis (CCS 2023), and SpeedyFair (NDSS 2024), often suffer from suboptimal performance, limited resilience, or weakened security guarantees. Pompē (OSDI 2020) introduced a novel ordering notion called ordering linearizability (OL) that may circumvent those drawbacks. However, its guarantee holds only under favorable network conditions, making the protocol vulnerable to order fairness violations during network delays and susceptible to performance degradation in the presence of Byzantine faults. Also, implementing SMR under OL remains an open challenge in asynchronous settings, as no known protocol achieves this without sacrificing liveness of SMR. In this paper, we present $\mathsf{Isotaxis}$, a state machine replication with ordering linearizability; moreover, our protocol has communication complexity $\mathcal{O}(n\ell+\lambda n^2)$, where $n$ is the number of processes, $\ell$ is the input (transaction) size, and $\lambda$ is the security parameter. This is optimal when $\ell\geq \lambda n$, while previous works have cubic communication. To the best of our knowledge, $\mathsf{Isotaxis}$ is the first protocol to achieve ordering linearizability in the asynchronous setting, especially one with optimal communication complexity and optimal Byzantine resilience. We implemented $\mathsf{Isotaxis}$ and conducted extensive experiments using up to 100 EC2 c6a.2xlarge instances. The experimental results show that our protocol robustly outperforms Pompē across all system scales, ranging from 4 to 100 nodes.

NAT is widely assumed to conceal the private IP addresses of internal clients from both off-path attackers within the same LAN and external observers. We show that this assumption does not hold. We present a novel off-path private IP address inference attack against NATed clients engaged in active TCP connections with a remote server. Our attack exploits known NAT behaviors in real-world routers, such as port preservation, insufficient reverse-path validation, and the absence of TCP window tracking, previously shown to enable off-path TCP hijacking. By inferring a NATed client’s private IP address, our attack defeats the address-hiding property commonly attributed to NAT, creating a privacy leak that can lead to deanonymization and user profiling. We validate the attack on 6 NAT routers and 2 real-world Wi-Fi networks on SSH and HTTP/HTTPS traffic, finding that 5 of the 6 routers and both networks are vulnerable.

It is well known that Byzantine agreement requires $\Omega(t^2)$ messages against a strongly adaptive adversary that may corrupt $t=\Theta(n)$ parties and suppress a party's undelivered messages upon corruption. We circumvent this lower bound by relaxing termination: for any constant $0<\nu<1$, at least a $(1-\nu)$ fraction of the honest parties terminate, while agreement and validity hold for every honest decision. For every constant corruption gap $\delta>0$ and every $t\leq(1-\delta)n/3$, we construct binary agreement with this guarantee in authenticated asynchronous networks against strongly adaptive corruptions with message takebacks. Except with negligible probability, these guarantees hold and every honest decision carries a transferable justifier. The protocol achieves almost-everywhere termination in expected $O(1)$ rounds, expected total communication $O(n\kappa^2)$ bits, and expected maximum communication $\widetilde O(\kappa^2)$ bits over honest parties before corruption, where $\kappa$ is the computational security parameter. Our construction combines a recursively shared BLS signing key with certificate dissemination over a sparse graph. The recursive sharing is used to implement threshold signing with distinct safety and liveness thresholds. Dissemination propagates existing certificates to almost all honest parties. The construction uses a trusted setup and is secure in the random oracle model under the algebraic one-more computational Diffie--Hellman assumption. We further obtain full binary agreement with the same asymptotic communication and round complexity against adaptive corruptions without message takebacks. The extension requires neither atomic multi-send nor private communication channels.

Public certificates of semiprimality could support cryptographic modulus generation by proving that an integer has exactly two prime factors without revealing them. Their usefulness in this setting depends on whether the certificate preserves the difficulty of factoring. Motivated by the examples of Reble and Broadhurst, we formalize semiprimality certificates by adapting the Goldwasser-Kilian primality criterion. For certificates with a prime point order, our semiprimality theorem uses public data $(N,S,E,P)$ comprising a composite nonsquare integer $N$, an elliptic curve $E$ over $\mathbb{Z}/N\mathbb{Z}$, a certified prime $S>(N^{1/6}+1)^2$, and a point $P\in E(\mathbb{Z}/N\mathbb{Z})$ of order $S$ modulo every prime divisor of $N$. Hasse's bound forces each prime divisor above $N^{1/3}$, proving that $N$ has exactly two prime factors. For such semiprimality certificates constructed using complex multiplication (CM), we show that a norm-lattice reconstruction factors $N$ from $(N,S,D)$ alone in expected polynomial time when the Frobenius at every prime divisor lies in a known imaginary quadratic field of fundamental discriminant $D$ or has trace zero, and $\gcd(S,2DN)=1$. Applying this reconstruction and complementary public-point and quadratic-twist attacks, we factor Reble's 1084-digit and Broadhurst's 5061-digit moduli. These attacks also defeat proposed repairs based on hidden cofactors, withheld CM maps, or private isogeny descent within a known field under the stated hypotheses. We leave open whether one can efficiently produce a public Goldwasser-Kilian-based certificate for a fixed modulus, using its privately known factors, while preserving its factoring difficulty relative to the General Number Field Sieve.

We study amortization of prover work in the multi-verifier setting, motivated by proof-as-a-service deployments in which a shared prover serves $K$ independent clients holding distinct statements. Each verifier checks only its own statement and proof, with no inter-verifier communication. The challenge is therefore to amortize prover work across many proofs while preserving local verification. We consider polynomial relations arising naturally in IOP-based proof systems, where verification reduces to polynomial identities and polynomial openings at verifier-chosen random points. Existing amortization techniques rely on shared verifier randomness, for example, to batch openings at a common evaluation point. However, under the standard Fiat--Shamir transform, independently verifiable proofs derive challenges from separate transcripts, preventing such amortization. We address this obstacle through a multi-verifier Fiat--Shamir transform that correlates verifier challenges across independently verifiable proofs while preserving locality. We further introduce promise local folding schemes, which defer polynomial-constraint checks generated during folding and amortize them later. Together, these techniques provide a generic framework for amortization under local verification. We apply this framework to the witness-independent component arising in R1CS- and CCS-based SNARK provers, which reduces to bivariate polynomial evaluation claims over the public constraint matrices. This component accounts for a substantial portion of the concrete proving cost. Applying our techniques to these claims reduces the server's cryptographic cost for this component from $O(K\cdot s)$ to $O(K\log K+s)$ group operations, where $s$ denotes the sparsity of the public constraint matrices, with each verifier performing only $O(\log K)$ cryptographic work and requiring no inter-verifier communication. Because the amortized component depends only on the public circuit description, our framework composes cleanly with collaborative zk-SNARK protocols, which target the complementary witness-dependent component.

Evolving secret sharing allows participants to join indefinitely without modifying previously distributed shares. We study the share size of perfectly secure evolving threshold secret sharing schemes and obtain two improvements. For general thresholds, we introduce a polynomial sharing method that shares two secrets with adjacent reconstruction thresholds using one polynomial. Combining this method with the evolving scheme of Cheng et al.\ (ASIACRYPT 2025), we obtain an evolving $k$-threshold scheme whose $t$-th share has size \[ \left\lfloor \frac{k}{2} \right\rfloor \log_2 t + O_k\!\left(\ell+\log_2\log_2 t\right) \] bits for an $\ell$-bit secret. This reduces the leading coefficient of their general construction from $k-1$ to $\lfloor k/2\rfloor$. For threshold three, we give a separate construction that reduces the lower-order terms of the scheme of Cheng et al. We mask the short shares in all generations with the same random $\ell$-bit value $R$, which is shared through an evolving $2$-threshold scheme, we obtain \[ \log_2 t+(2+o(1))\log_2\log_2 t \] bits per share for fixed $\ell$. Both constructions satisfy correctness and perfect information-theoretic security.

With the rapid advances in quantum computer architectures and the emerging prospect of large-scale quantum memory, it is becoming essential to classically verify that remote devices genuinely allocate the promised quantum memory with a specified number of qubits. In this paper, we introduce a new concept, proofs of quantum memory (PoQM). A PoQM is an interactive protocol between a classical probabilistic polynomial-time (PPT) verifier and a quantum polynomial-time (QPT) prover over a classical channel where the verifier can verify that the prover has possessed a quantum memory with a specified number of qubits for a specified period of time. PoQM generalize the well-studied notion of proofs of quantumness (PoQ) [Brakerski, Christiano, Mahadev, Vazirani, and Vidick, JACM 2021] where a classical verifier can verify that the prover is not classical. Our contributions are summarized as follows: We introduce a formal definition of PoQM. We also introduce a variant of PoQM, which we call inefficient-verifier PoQM (IV-PoQM), where the verifier's final computation to make the decision is not necessarily efficient. Clearly, PoQM imply IV-PoQM. We construct PoQM based on the hardness of LWE. Specifically, we give two constructions of PoQM. The first one is of two-round (i.e., four-message) and has negligible soundness error under the subexponential-hardness of LWE. The second one is of polynomial-round and has inverse-polynomial soundness error under the polynomial-hardness of LWE. As a lowerbound of IV-PoQM (and therefore PoQM), we show that IV-PoQM imply one-way puzzles. Moreover, we show that a certain restricted version of PoQM implies quantum computation classical communication (QCCC) key exchange, which suggests the difficulty of black-box constructing PoQM from one-way functions. We show that constant-round PoQ imply PoQM or single-round PoQ (with a quantum verifier). Single-round PoQ are ``trivial'' PoQ in the sense that the verifier asks the prover to solve a classical problem which is quantumly easy but classically hard. The result therefore demonstrates that PoQM capture ``genuinely-interactive'' PoQ. We show that if constant-round IV-PoQ that are black-box constructed from quantumly-secure falsifiable assumptions exist then IV-PoQM exist. This result implies that IV-PoQM can be constructed from quantumly-secure constant-round statistically-hiding commitments (and therefore from quantumly-secure collision-resistant hash functions).

One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which—in Satoshi Nakamoto's own words—rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet. Unfortunately, the real-world implementations of peer-to-peer gossip-style networks used by blockchain protocols rely on a number of ad-hoc attack mitigation strategies that leave a glaring gap between the idealized communication layer assumed in formal security arguments for blockchains and the real world, where a wide array of attacks have been showcased. In this work we bridge this gap by presenting a Byzantine-resilient network layer for blockchain protocols. For the first time we quantify the problem of network-layer attacks in the context of blockchain security models, and we develop a design that thwarts resource restricted adversaries. Importantly, we focus on the proof-of-stake setting due to its vulnerability to Denial-of-Service (DoS) attacks stemming from the well-known deficiency (compared to the proof-of-work setting) known as nothing at stake. We present a Byzantine-resilient gossip protocol, and we analyze it in the Universal Composition framework. In order to prove security, we show novel results on expander properties of random graphs. Importantly, our gossip protocol can be based on any given bilateral functionality that determines a desired interaction between two "adjacent" peers in the networking layer and demonstrates how it is possible to use application-layer information to make the networking-layer resilient to attacks. Despite the seeming circularity, we demonstrate how to prove the security of a Nakamoto-style longest-chain protocol given our gossip networking functionality, and hence, we demonstrate constructively how it is possible to obtain provable security across protocol layers, given only bare-bone point-to-point networking, majority of honest stake, and a verifiable random function.

Ring switching provides a natural way to reduce bootstrapping cost in ring-based fully homomorphic encryption by moving computation to smaller rings. For SIMD-packed ciphertexts, however, ring switching changes the slot layout, so conventional approaches apply slot recovery to ensure correct computation on the original slot values, consuming capacity and requiring synchronization across ciphertexts. In this paper, we show that slot recovery is not indispensable: CKKS and BGV/BFV bootstrapping can proceed directly after ring switching. We further prove that a continuous slotwise function admits independent leaf evaluation for unrestricted real CKKS inputs exactly when it is affine. Our construction provides an extra layer of parallelism, enables cheaper arithmetic in smaller rings, and can further simplify bootstrapping by exploiting the leaf structure. For CKKS with \(N=2^{17}\) and \(n=2^{16}\), we achieve a \(1.13\times\) serial speedup; evaluating two leaves in parallel yields a \(2.03\times\)--\(2.18\times\) speedup and \(2.00\times\)--\(2.14\times\) the throughput of direct bootstrapping. For BGV with \(p=65537\), \(N=2^{16}\), and \(n=2^{15}\), we achieve a \(1.30\times\) serial speedup and \(1.63\times\) the throughput of direct general bootstrapping under matched transform settings, while reducing key-generation time by \(50.6\%\) and server-key size by \(48.6\%\).

The question of obtaining a constant-additive approximation for bin packing was highlighted in the third of ten open problems in Williamson and Shmoys' The Design of Approximation Algorithms [SW11, Chapter~17, Problem~3]. We prove that there is an absolute constant $c>0$ such that, unless $\mathrm P=\mathrm{NP}$, no deterministic polynomial-time packing using at most $\mathrm{OPT}+c\log^*\mathrm{OPT}$ bins, where $\mathrm{OPT}$ is the minimum number of bins. In particular, no such algorithm has additive error $o(\log^*\mathrm{OPT})$. The best known upper bound, due to Hoberg and Rothvoss [HR17], is $\mathrm{OPT}+O(\log\mathrm{OPT})$, achieved by a randomized algorithm with expected polynomial running time. OpenAI [Ope26] previously showed that, unless $\mathrm P=\mathrm{NP}$, no deterministic polynomial-time algorithm guarantees a packing using at most $\mathrm{OPT}+O(1)$ bins. We conjecture that the optimal additive approximation error for bin packing is $\Theta(\log \mathrm{OPT})$.

During the last decade, single-trace side-channel attacks on cryptographic implementations have largely focused on profiled methods, which typically assume that the attacker has a clone device and implementation knowledge to build a leakage model for the target before launching the attack. In this paper, we demonstrate that a much weaker adversary, without the ability to profile, can also mount powerful single-trace attacks. The presented method compares the observed sample distribution with the expected Hamming weight leakage distribution using a Gaussian mixture model as a distinguisher. The horizontal nature of the attack allows us to obtain multiple observations per execution by partitioning and stacking the trace. We show how to select optimal parameters for trace preprocessing and configure the measurement setup so that the noise floor is lowered, enabling the exploitation of weak leakage. We also prove that imperfect classifications can be efficiently corrected using information-set decoding algorithms. The new method is evaluated on an optimized implementation of ML-DSA-65 on ARM Cortex-M4 using the secret key unpacking procedure as an attack point. With an enumeration budget of $2^{70}$ operations in $\mathbb Z_q$, the full secret key is recovered from a single trace in 99% of attacks.

Verifpal is a symbolic protocol analyzer introduced in 2019 to make formal analysis accessible during protocol design. It provides a small modeling language, built-in cryptographic primitives, and attack reports that use the model's names. This paper describes the analysis engine of Verifpal 1.6.7. A backward solver proposes attacker actions, which an executor checks by running all sessions and peer configurations together. An injected value is delivered only when the attacker can derive it from information already available in that execution. A separate query evaluator, or judge, records the result. We define the model, its five query predicates, and a reference semantics, and prove that every judged execution is a history of that semantics. Executions terminate; search termination is conditional on the solver calls terminating. Evaluation covers 885 secrecy queries across 189 configurations of the fifteen fundamental Noise patterns, varying static-key compromise and protocol checks. At one and two sessions, a separate executor reproduces every reported disclosure, and ProVerif proves all 290 passing counterparts for unbounded sessions. The protocol computations also match 90 external cryptographic test-vector messages. These results support the implementation on the tested models; a Verifpal pass remains the outcome of bounded, incomplete search.

We present a plaintext-recovery attack on both the DBDH-based construction and the CBDH-based variant of Datta, Komargodski, and Waters (Journal of Cryptology, 2023). The attack succeeds with probability one in the claimed static security model using one corrupt authority and two users, each unauthorized even when granted the corrupt authority's attribute. The flaw is an invalid extension of the LSSS matrix-normalization lemma originating with Rouselakis and Waters (FC,~2015): preserving complete-share distributions does not preserve coordinate-wise ciphertext masks, which a corrupt authority can expose to remove identity binding from other users' shares. For both variants, replacing these masks with independent full linear sharings of zero preserves correctness and restores ciphertext-distribution invariance. We prove static security of both repaired variants in the random oracle model under their respective BDH assumptions, using the original hardcore-bit convention for the CBDH variant. Both proofs allow adaptive identity-hash queries. The modification retains the original matrix-width and row-labeling restrictions, keys, decryption, and ciphertext size, requiring only additional encryption randomness and finite-field arithmetic. We also attack both multi-authority attribute-based inner-product functional encryption constructions of Datta and Pal (PKC, 2023) and establish correctness and matrix-substitution invariance of the same repair. We prove static security of the repaired small-universe construction under asymmetric DBDH. For the large-universe construction, we identify a missing source-group encoding in the original reduction and give a complete static security proof under an augmented $L$-DBDH assumption, whose generic bilinear group hardness we establish.

The signature schemes MQOM, SNOVA, MAYO, and UOV are third-round candidates in the NIST standardization process for additional post-quantum signatures, and their security relies on the hardness of the multivariate quadratic (MQ) problem. XL with block Wiedemann (BW) is one of the most efficient MQ solvers in practice, but its memory demand has led to a debate about its memory access cost: generating the rows of the Macaulay matrix on the fly is widely believed to save memory at a non-negligible computational cost. In this work, we evaluate the memory--time trade-off in practice. We provide the first efficient on-the-fly implementation of XL with BW. We build on the state-of-the-art implementation by Cheng, Chou, Niederhagen, and Yang (CCNY), which uses SSE instructions and supports the fields $\mathbb{F}_2$, $\mathbb{F}_{16}$ and $\mathbb{F}_{31}$; we remove its column-index tables and generate the rows on the fly in the first phase of BW (BW1). We amortize the cost of on-the-fly generation with a new algorithm that computes column indices with $O(n^2)$ instead of $O(n^3)$ table look-ups, where $n$ is the number of variables. In our experiments we observe that our on-the-fly implementation achieves running times comparable to CCNY's with up to five times less memory. We also port both implementations to AVX2 over $\mathbb{F}_{256}$, the main field of UOV, and observe a similar behavior: comparable BW1 running times with less memory for the on-the-fly variant.

Miner extractable value (MEV) in automated market makers allows block builders to profit from transaction ordering and injected trades, imposing costs on users and contributing to builder centralization. We introduce Otter (Optimal Truthful Trading with Excess Redistribution), a two-asset batch AMM that achieves provable MEV resilience when the consensus layer provides censorship resilience and block space is uncongested. In particular, Otter makes truthful behavior a dominant strategy for both users and builders. Consequently, a builder cannot profit from strategic deviations, including reordering bids or injecting sybil bids. These guarantees continue to hold even when the builder is itself a trader with intrinsic value. Moreover, we show that our mechanism maximizes social welfare, in a strong sense, within a natural class of mechanisms satisfying the desired game-theoretic properties. To achieve these guarantees, we introduce a new paradigm called surplus redistribution, which provably prevents residual surplus from being captured as MEV by redirecting it to the broader community. Specifically, the pool's output tokens need not be distributed entirely among the users in the current batch. Instead, any residual surplus may be transferred, for example, to a smart contract governed by the decentralized community. The accumulated surplus can subsequently be used to benefit community members in ways that preserve the mechanism's game-theoretic guarantees --- for example, by subsidizing traders' transaction fees, rewarding liquidity providers, or returning assets to the pool to reduce price impact and slippage for future traders. Our approach relies on the underlying consensus layer to provide censorship resilience. We motivate the necessity of this assumption through an impossibility result showing that the desired game-theoretic guarantees become unattainable when the builder is additionally allowed to censor transactions. Thus, our results also provide a mathematically formal demonstration of how consensus-level security guarantees can fundamentally expand what is achievable at the application (i.e., smart-contract) layer. Finally, we establish additional results characterizing the builder fee structures compatible with our desired incentive guarantees.

Recent superlattice algorithms have improved the provable complexity of lattice problems. Ducas, Engelberts, and Loyer used this framework to obtain a subexponential algorithm for infinity-norm short integer solution, while also identifying a key obstacle to extending it to learning with errors (LWE). A similar difficulty arose in the analysis of Kirchner and Fouque, whose claimed subexponential running time with only linearly many LWE samples was not rigorously established. Building on the framework of Ducas, Engelberts, and Loyer, we develop two refinements based on rejection sampling that solve this open problem. First, we use rejection sampling to cancel the shift-dependent normalization factor that arises when sampling from a shifted, scaled integer lattice. This factor is a product of one-dimensional Gaussian masses and can be evaluated efficiently. This yields a provably subexponential classical search-LWE algorithm for prime $q\in[n^2,2n^2]$ and constant Gaussian error width. It uses only $m=4n$ independent samples and runs in time and space $\exp(O(n/\ln\ln n))$. Second, we use random auxiliary superlattices and apply rejection sampling to the difference of two Gaussian lattice samples, ensuring that the accepted output follows the desired discrete Gaussian distribution up to a small statistical error. For $q=n^{\kappa+o(1)}$, $m=n+h=O(n)$, and $R=h\ln q/[m\ln(2+\sigma)]\to\infty$, the resulting algorithm uses time and space $2^{(1/2+o(1))n/\ln R}$, where $\sigma$ is the Gaussian error width. In particular, for $\sigma=n^{o(1)}$ and any fixed $m/n>1$, our algorithm achieves provable subexponential classical running time, whereas the primal and dual baselines have exponential-time bounds and earlier provable subexponential BKW analyses require $\Omega(n\ln n)$ samples.

We present GordieHowe, a system comprising a language, a certifying compiler, and a zero-knowledge proof protocol. GordieHowe is especially suitable for building anonymous credentials on top of standardized signature schemes like ECDSA, RSA, and ML-DSA. GordieHowe is the first system to achieve the following three properties simultaneously: provable security against quantum attackers, efficiency for statements spanning multiple fields—including proving and verifying in parallel—and automatic batching of structured computations. GordieHowe is high-assurance by design. The language is designed to enable static checking of bounds safety, preventing integer overflows. Its compiler emits a Lean certificate that its optimization decisions are semantics-preserving for the input program. The proof system's security theorems are machine-checked in Lean. GordieHowe is faster and has smaller proofs than comparable prior work. It proves, in parallel on four cores, an ECDSA-signed mobile driving license presentation in 64.8 ms with a 276 KiB proof, 10.1× faster and 22% smaller than Google's Longfellow. With at least 101 bits of knowledge soundness in the random oracle model, GordieHowe proves knowledge of a 1 KiB SHA3-256 preimage in 5.0 ms with a 60 KiB proof, and of an RSA-2048 signature on a private 2 KiB message in 25.9 ms with a 210 KiB proof. With at least 116 bits against quantum adversaries, GordieHowe proves knowledge of an ML-DSA-44 signature on a private message in 87.3 ms with a 549 KiB proof, 70.2× faster and 29% smaller than an optimized Longfellow circuit. In building GordieHowe we make a number of contributions of independent interest. We define a new notion of an interactive oracle proof (IOP) whose messages are partially ordered, which we call a series-parallel IOP. We extend the BCS transformation to series-parallel IOPs, and give knowledge soundness and ZK proofs in the QROM. We also show our BCS extension satisfies a form of simulation extractability in the QROM; we believe this is the first simulation extractability result of any kind for BCS in the QROM.

Du et al. (Security and Communication Networks, 2022) proposed a public-key authenticated searchable encryption scheme that employs Bloom filters and blockchain. In their scheme, Bloom filters are used to search encrypted keywords, while blockchain is used to guarantee the correctness of search results. In this paper, we demonstrate that Du et al.'s scheme leaks keyword information from ciphertexts. Our analysis focuses on the fact that the Bloom filter embedded in a ciphertext is uniquely determined by the Diffie-Hallman key and the keyword to be encrypted and is directly included in the ciphertext. We show that the success probability of the proposed attack is lower bounded by the probability that no false positives occur in the Bloom filter, and we evaluate this probability to confirm that the attack achieves a sufficiently high success rate. Furthermore, we examine Du et al.'s security model and their assumed usage scenarios, and discuss the validity of our attack under those conditions. We also consider a simple modification intended to prevent our attack and demonstrate that a slightly adapted version of the attack remains effective against the modified scheme. In addition, we show that previously generated ciphertexts can still pass verification even when the search results differ, indicating that the blockchain-based integrity verification mechanism is insufficient.

In EUROCRYPT 1999, Gennaro, Jarecki, Krawczyk, and Rabin (GJKR) showed that in the well-known Pedersen robust Distributed Key Generation (DKG) protocol for the Discrete Logarithm (DL), an adversary can bias the distribution of the resulting public key. To address this issue, they proposed a fully secure, statistically unbiased variant of the Pedersen DKG protocol. The GJKR protocol achieves robustness and guarantees a statistically uniform final public key, at the cost of $O(n^2)$ exponentiations per party, where $n$ denotes the number of parties. In this paper, we revisit fully secure robust DKG protocols for the DL setting and propose three more efficient alternatives, each using $O(n)$ exponentiations per party in the happy path while offering different trade-offs in security, efficiency, and round complexity. Our first protocol, like the GJKR scheme, guarantees that the final public key is indistinguishable from a uniformly random group element even to a computationally unbounded distinguisher. The second protocol is concretely more efficient and ensures that the public key distribution is computationally indistinguishable from uniform. In our third construction, we focus on minimizing the worst-case number of rounds in the second protocol and present a variant using three rounds in the happy path and one additional reconstruction round in the unhappy path. Our third scheme can be viewed as a fully secure and round-reduced variant of the biased construction by Atapoor et al. (ASIACRYPT 2023). In comparison with the most recent low-round fully secure DKG protocols by Katz (CRYPTO 2024), Cascudo-David (EUROCRYPT 2024), Kate et al. (CCS 2024), and Boneh et al. (EUROCRYPT 2025)--all of which achieve three rounds via two online rounds and one preprocessing round (or vice versa)--our third DKG protocol requires only $O(n)$ exponentiations per party in the happy path, as opposed to at least $O(n^2)$.

Known-Covariance Ring-LWE (KCov-RLWE) was introduced by Micciancio and Suhl to support simulation-secure threshold encryption. It strengthens ordinary Ring-LWE by revealing an exact quadratic summary of the hidden secret and errors, and its decisional hardness was left open. We give explicit polynomial-time decision attacks for broad families of prime moduli at ring rank one. Our key observation is that the public sample and the covariance hint together determine a bordered Gram matrix whose determinant exposes a hidden residual with a different distribution for genuine and uniform samples. After reducing the ring into finite-field components, this residual has one of two forms: a product across reciprocal components, or a Hermitian norm when a component is preserved by conjugation. The latter case yields a particularly strong distinguishing signal. Moreover, reduction modulo any divisor preserves the KCov real and random experiments exactly, so every attackable odd prime divisor of a composite modulus transfers the corresponding distinguisher with no loss of advantage. The attack covers the one-sample setting globally in the self-reciprocal regime and, under the coefficient-product Gaussian specialization, locally in the completely split regime. More generally, we obtain a complete classification of how this residual-based attack behaves for odd prime moduli when $m\ge2$, and extend these guarantees to arbitrary moduli possessing a suitable odd prime divisor. The classification does not imply insecurity for every parameter family: when the relevant residue fields are sufficiently large, the guaranteed distinguishing advantage in the reciprocal case can become negligible, and pure power-of-two moduli remain outside the divisor-reduction extension. Accordingly, our results invalidate the KCov pseudorandomness assumption in the quantified families; they do not show that every parameter choice permitted by the motivating Ring-PKE sketch is insecure, nor do they give a direct IND-CPA break of the complete threshold-encryption construction.

In classical cryptography, one-way functions are necessary for most of cryptography. In the quantum world, however, Kretschmer at TQC'21 and subsequent works have demonstrated that quantum versions of various primitives in minicrypt, such as signatures and private-key encryption, do not require quantum-computable one-way functions (qOWFs). However, the question of the necessity of qOWFs for primitives in Cryptomania like public-key encryption with classical public-keys and ciphertexts (qPKE) has remained open. We provide a comprehensive picture of the relationship between qPKE and qOWF. First, our main result is a black-box separation between qOWFs and qPKE. In particular, we show that relative to a unitary, real, and self-inverse oracle, there exists a qPKE scheme (with classical keys and ciphertexts), but qOWFs do not exist. Further, our oracles admit a point-function obfuscation construction, thus ruling out black-box construction of qOWF from point function obfuscations. On the positive side, we construct qPKE from quantum indistinguishability obfuscation for quantum circuits with classical obfuscated descriptions and efficiently verifiable one-way puzzles, which is known to be a potentially weaker assumption than qOWFs, due to an existing black-box separation. Our construction is the quantum analog of the classical construction of PKE from one-way functions and indistinguishability obfuscation in the quantum computation with classical communication (QCCC) setting.

Fix a prime power q . We prove that deciding whether a received word y ∈ F^n_qm lies at rank distance at most n − 2 from the one-dimensional Gabidulin code {λg : λ in Fqm } is NP-complete. Thus maximum-likelihood decoding of Gabidulin codes is NP-hard even for k = 1, an analogue of the Guruswami-Vardy theorem for Reed-Solomon codes. In the Hamming metric, by contrast, hardness at this radius requires the dimension to grow with the length, as in the Guruswami Vardy theorem. The reduction is deterministic; consequently Rank Syndrome Decoding (RSD) and Rank Minimum Distance (RMD) for Fqm -linear codes are NP-complete under deterministic polynomial reductions, whereas the previously known reduction was randomized. The proof goes through a pivot problem that we introduce, Twisted Square Membership (TSM): given Fq -subspaces U, W in FqN , decide whether some non-zero a ∈ U satisfies a^(q+1) in W . Quadratic systems in d unknowns are encoded into TSM, then TSM into Gabidulin decoding. The last step views the received word as an Fq -linear map and decoding at radius n − 2 as the search for an Fq -plane on which it acts as a scalar. With support U + τ W in a cubic extension and map a + τ b → a^(q^2) + τ b^q , two Frobenius twists force solution planes to encode the relation a^(q+1) ∈ W . All constructions are explicit and polynomial, with N = O(qd^2 ), n ≤ N + d, and m = 3N .

We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state. The verifier has access to a reflection oracle about the target. For a Haar-random $n$-qubit target, we prove that achieving constant average fidelity with the target requires $(q+1)^2(B+1)=\Omega(2^n)$, where $q$ is the number of verifier queries and $B$ is the total prover-to-verifier communication. The bound allows arbitrary classical interaction and unrestricted computation between queries. Our proof extends the lower bound of Aaronson and Kuperberg (ToC'07) from a single classical proof to an arbitrary classical interaction. As a result, we obtain a quantum-oracle separation of QMA from QCIP. In particular, we give a unitary oracle $\mathcal{U}$ such that there exists a language $L\in\mathrm{QMA}^{\mathcal{U}}$ but $L\notin\mathrm{QCIP}^{\mathcal{U}}$. Our separation holds even for UniqueQMA, the restriction of QMA to verification with a unique quantum witness, which is known to be strictly weaker than QMA in the quantum black-box setting. We further give an oracle construction for a notion known as QMA--QCIP[2] gap problem. This gives average case hardness for a QMA language under classical access to a QCIP[2] decision oracle and is used in establishing negative results on witness encryption and quantum indistinguishability obfuscation.

Secure multiparty computation (MPC) allows distrusted parties to jointly evaluate a common function while keeping their inputs private. In this work, we focus on improving the communication complexity of information-theoretic asynchronous MPC with optimal resilience ($t < n/3$). The current state-of-the-art work in this setting by Goyal, Liu-Zhang, and Song [Crypto’24] achieves amortized linear communication per gate with $\Omega(n^{14})$ elements additive overhead. In comparison, the best-known result in the synchronous setting by Goyal, Song, and Zhu [Crypto’20] achieves the amortized linear communication per gate with only $\mathcal{O}(n^{6})$ elements additive overhead, revealing a significant gap that we aim to close. This work closes this gap and goes further. We present the first statistically secure asynchronous MPC protocol achieving amortized linear communication per gate with only $\mathcal{O}(n^{5})$ elements additive overhead assuming a functionality for Agreement on Common Set (ACS). With the best-known instantiation for ACS, we obtain an asynchronous MPC protocol in the plain model with additive overhead $\mathcal{O}((\kappa+n)n^4\log\kappa)$ elements in expectation, where $\kappa$ is the security parameter. In the setting of statistical security with optimal resilience, this even surpasses the best synchronous result when $n\geq\sqrt{\kappa\log\kappa}$. Technically, our contributions include (i) a new protocol for generating Beaver triples with linear communication per triple and $\mathcal{O}(n^3)$ elements additive overhead assuming functionalities for generating random degree-$t$ Shamir sharings and ACS, and (ii) a new protocol for generating random degree-$t$ Shamir sharings with linear communication per sharing and $\mathcal{O}(n^{5})$ elements additive overhead assuming a functionality for ACS.

Fully homomorphic encryption schemes enable arbitrary computation on encrypted data. Although the first candidate were considered too computationally inefficient, modern cryptosystems are now featured in practical deployments. Yet, despite a plethora of advances, many non-polynomial operations remain computationally challenging. In this work, we investigate radix decomposition, i.e., the homomorphic conversion of an LWE ciphertext with a large plaintext message into encryptions of its digits. Such decompositions are a core building block for large-precision computation in FHEW/TFHE-like schemes, for instance for sign evaluation, comparisons, and large lookup tables. To this end, we introduce phase decomposition: decomposing the coefficients of an LWE ciphertext itself in a radix $\alpha$ yields small pseudo-LWE samples whose phases recombine linearly to the phase of the original ciphertext. For keys of bounded Hamming weight, these phases are small and can be made non-negative, and the base-$\alpha$ digits of the original phase follow from them through a simple carry recurrence. We evaluate this recurrence entirely in the exponent of an RLWE accumulator, using a new exact homomorphic truncation in the exponent based on automorphisms. The resulting digit decomposition requires a single blind rotation per digit, asymptotically half as many as the state of the art, introduces no modulus-switching error between iterations, and supports input moduli larger than the ring modulus. The same tools yield functional bootstrapping over the full ring $\mathbb{Z}_{2N}$, the evaluation of arbitrary, not necessarily negacyclic, functions on small plaintext spaces, and a scheme-independent digit decomposition for SIMD schemes based on parallel-prefix addition.

NIST is revising SP~800-38F, which specifies the AES Key Wrap modes KW and KWP. This paper is an updated and expanded version of our technical comments to NIST. We show that the forgery probabilities stated in SP~800-38F do not account for adaptive attacks, give the resulting forgery probabilities for KW, KWP, and TKW, and show that checking the expected plaintext length can raise the security level of KWP considerably. Revisiting Kelsey's long-message observation, we correct the collision conditions, show that a successful forgery leaks a plaintext prefix, derive an encryption-only distinguisher, and conclude that KW does not have beyond-birthday-bound security. We explain the role of the step counter, analyse the single-semiblock path of KWP and the trade-off between the number of passes and the length limit, and give recommendations for the revision, for implementations, and for future key-wrap designs.

We present a multi-target second-preimage attack on the message hashing of the stateful hash-based signature schemes HSS/LMS and XMSS with SHA-256 and with the truncated SHA-256/192. The attack builds on the herding technique of Kelsey and Kohno: the attacker takes the chaining states that follow the per-signature prefixes of many collected signatures and merges them, level by level through state collisions, into a single chaining state. From that state one search serves all collected signatures at once, which defeats the commitment to the key and to the one-time-signature leaf index at the start of the hash input that is meant to rule out multi-target attacks. The search can match the final digests, which is the better choice against SHA-256/192, or, after appending a Kelsey-Schneier expandable message, the internal chaining states of long signed messages, which is effective for full SHA-256. For SHA-256 with NIST's bound of $2^{64}$ signatures, which may be spread over any number of keys, the cost in compression-function calls falls from the nominal $2^{256}$ to about $2^{166}$ for messages of up to 4 GiB and to about $2^{156}$ in the formal limit of maximal message length, a loss of 100 bits. For SHA-256/192, digest matching costs about $2^{153}$ for $2^{64}$ signatures of any length, a loss of 39 bits. Because the attack pools signatures across keys, even the first signature of an individual key contributes to a potential overall exposure of an ecosystem. The attacks exploit the chaining state of SHA-256, which is narrower than twice the targeted security level; the SHAKE256 parameter sets are not affected.

With Q-day approaching, the transition to post-quantum cryptography (PQC) has begun, with governments across the US, UK and EU mandating migration to quantum-resistant standards. This paper benchmarks the three NIST-standardised PQC algorithms—FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA)—across key generation, signing and verification operations, measuring both computational performance and energy consumption on a range of constrained IoT-class devices, from the 32-bit Raspberry Pi 1 and Zero to the 64-bit Raspberry Pi 4, as well as commodity laptop hardware. Using the FNIRSI FNB58 USB power meter and OpenSSL 3.5, results show that ML-KEM and ML-DSA achieve energy and speed efficiency comparable to classical elliptic-curve cryptography across all tested architectures. However, SLH-DSA signing is inadvisable on constrained hardware: energy costs for SLH-DSA signing on 32-bit devices were up to 243% higher than on equivalent 64-bit hardware, making it impractical for resource-limited IoT deployments. These findings have direct implications for IoT security practitioners planning PQC migration.

The closest vector problem(CVP)and the nearest codeword problem (NCP) are fundamental computational problems with connections to learning, coding theory, and cryptography. We study hardness of approximation in the preprocessing model: an algorithm receives the lattice or code in advance, may perform unrestricted computation to produce polynomial-size advice, and must then solve the problem on any target in polynomial time. Unless $\mathsf{NP} \subseteq \mathsf{P/poly}$, no such algorithm achieves an approximation factor of $\bullet$ $M^{1−\varepsilon}$ for NCP over any fixed finite field, or $\bullet$ $M^{1/\min\{p,2\}−\varepsilon}$ for CVP in any $\ell_p$ norm, for every fixed $\varepsilon > 0$, where $M$ denotes the code block length or lattice dimension, respectively. We improve the subpolynomial factors of Khot, Popat, and Vishnoi [KPV14]to polynomial ones, matching the exponents that Song [Son26] proved without preprocessing for binary codes and the $\ell_2$ norm. We further extend Song’s evaluation tables to every fixed prime characteristic and the lattice reduction to $\ell_p$ with $p > 2$. Our main technical contribution is an extension of the moment method, introduced in an OpenAI report [Ope26] and improved by Song [Son26], to the preprocessing setting. In addition, we give a direct reduction from probabilistically checkable proofs (PCPs) whose query locations and families of possible predicates do not depend on the formula. The resulting factor of $M^{\Omega(1/(\log \log M)^2)}$ is already larger than that of [KPV14], and the reduction may be of independent interest.

Integral cryptanalysis analyzes block ciphers using input structures for which the sum of a chosen function of the output bits becomes key-independent. However, most methods still test one output expression at a time, so they can miss distinguishers that emerge when several outputs are combined, either linearly or nonlinearly. They are also not designed to capture key-dependent integral combinations, which may hold deterministically on part of the key space. In this work, we develop Split-and-Cancel, a method that combines exact expansion in a short final part with an oracle on the preceding rounds to determine which suffix monomials can survive from the chosen structure and records them in a binary matrix. Key-independent combinations are then extracted from the left kernel of this matrix. We first apply the method in a reduced model with omitted boundary key additions, where linear dependencies in this matrix yield certified sum combinations independent of keys among output bits and higher-degree output products. When the omitted round key in the combination is restored, the same combinations yield deterministic weak-key distinguishers. In connection with the weak-key distinguishers, we further investigate their probabilistic behaviour and show that the probability-estimation formula used in Zhang et al.’s EUROCRYPT 2026 work is invalid. The found flaw is supported by our experiments. We apply the method to SIMON, SIMECK, SPECK, PRESENT, and GIFT. Our strongest deterministic results improve the best integral distinguishers for SIMON, SIMECK, and SPECK by one round at every standard block size. For PRESENT and GIFT, we improve deterministic weak-key integral distinguishers by one round. In each case, the exact weak-key class covers at least a quarter of the key space: $2^{78}$ of $2^{80}$ keys for PRESENT-80, $2^{126}$ of $2^{128}$ keys for PRESENT-128, GIFT-64 and GIFT-128. These results show that exact modeling of a short final part can reveal key-independent and weak-key integral behavior missed by analysis using single observables.

HAETAE has shorter public keys and signatures than ML-DSA, but the signing stack of its reference implementation reaches $158\, \mathrm{KiB}$ on Cortex-M4. The Low-Stack HAETAE implementation presented at CHES'26 brings the signing stack down to $5.7$-$5.9\,\mathrm{KiB}$; yet even HAETAE-2 still needs $8,718\,\mathrm{B}$ in a realistic IoT scenario, where the secret key and the signature buffer share the same SRAM. Gaussian regeneration further increases signing time by up to a factor 2.6 relative to the C reference. Although HAETAE's modulus $q = 64\,513$ fits in 16 bits, signing and verification also need values modulo $2q$, so existing implementations keep 32-bit working polynomials. We store them in 16 bits and lift each coefficient to modulo $2q$ in a register only when it is consumed, and let objects with disjoint lifetimes share buffers, which lowers peak stack usage without any additional Gaussian regeneration. Exact Gaussian replay and caching method then record the acceptance decisions and partial CDT ranks of the first generation in the unused space of the signature buffer, so that the original samples are restored from the same random stream with less recomputation. For Cortex-M4, Cortex-M3, MSP430, and AVR, we further design NTT modular multiplication and butterflies that preserve 16-bit storage, and optimize the arithmetic of the FFT and the Gaussian sampler. We validate our implementation on $8\,\mathrm{KiB}$ hardware: a single C firmware image on the ATmega2560 runs HAETAE-2 key generation, signing with the generated key, and verification, and uses a total of $8,070\,\mathrm{B}$ of SRAM, including the secret key, the signature buffer, static data, and the stack. To the best of our knowledge, this is the first standardization-track PQC-DSA implementation that signs within $8\,\mathrm{KiB}$ of total SRAM on physical hardware. Compared with Low-Stack HAETAE on Cortex-M4, Cortex-M3, MSP430, and AVR, our implementation reduces stack usage by up to 34% and runs key generation and signing 1.18-2.51$\times$ faster wherever Low-Stack can run them.

As a privacy-preserving distributed learning paradigm, federated learning faces severe security threats, especially data poisoning, gradient tampering, distributed attacks, and adaptive attacks. Existing gradient-based detection methods encounter three major bottlenecks in practical applications. First, they cannot distinguish between benign and malicious gradients under distributed attacks in non-IID scenarios. Second, defenders lack prior knowledge of trigger patterns. Third, attackers can launch adaptive attacks against these defense mechanisms. To address these challenges, we propose a novel defense paradigm. This paradigm shifts away from gradient detection, instead leveraging zero-knowledge proofs to conduct sample-level inspections on the local datasets of clients, eliminating the defense degradation caused by distributed attacks under non-IID settings. Then, through a staking mechanism, attackers are forced to train on discovered malicious samples with flipped labels, generating counter-gradients to neutralize hidden malicious samples, achieving targeted backdoor removal without requiring any prior knowledge of backdoor features. Furthermore, through zero-knowledge proof commitments, training gradients must be generated based on the same locked data. This prevents dynamic adaptive attacks based on reference model parameters and precludes gradient tampering. Experimental results demonstrate that under the highly non-IID setting of $\text{Dir}(0.1)$, our proposed scheme successfully defends against distributed backdoor attacks and edge-case attacks on CIFAR-10, suppressing the attack success rate to below $6\%$. To the best of our knowledge, this is the first framework to achieve such defense results.

Authenticated garbling (Wang et al., CCS'17) is the leading framework for achieving constant-round maliciously secure 2PC, achieving total communication comparable to protocols in the semi-honest setting. In the semi-honest setting, the one-hot garbling scheme of Heath and Kolesnikov (CCS'21) supports tensor gates $\vec x \otimes \vec y$, for $\vec x \in \{0,1\}^n$ and $\vec y \in \{0,1\}^m$, in $O(n+m)\kappa$ bits, versus $O(nm)\kappa$ for an AND-gate-based garbling. Extending this improvement to the malicious setting has remained open. We present two authenticated garbling protocols that efficiently handle tensor gates. Our first protocol minimizes garbled circuit size, matching the size of semi-honest one-hot garbling; all additional overhead is confined to preprocessing. We also design a custom preprocessing protocol for efficiently generating random authenticated tensor triples, proved secure assuming only a circular correlation robust hash function and base OTs. Our second protocol minimizes total communication via compressed (PCG-style) preprocessing. We construct an authenticated variant of one-hot garbling where the additional overhead in garbled-circuit size as compared to the semi-honest garbling scales with tensor-gate input length rather than output length. As in the semi-honest case, tensor gates are restricted to inputs of length $O(\log \kappa)$ and arbitrary-length tensor products are handled by tiling multiple short input gates. This yields an $O(\log \kappa)$ factor reduction in communication for general tensor products compared to previous state-of-the-art authenticated garbling protocols, with concrete improvements in communication and runtime for practical workloads such as integer and matrix multiplication within an authenticated garbled circuit.

Garbling schemes are powerful primitives that enable secure computation between a mutually untrusting garbler and evaluator. A projective garbling scheme is one that encodes the evaluator's input in a simple bit-by-bit manner. Projective schemes, such as the seminal scheme of Yao, are versatile, as they are naturally compatible with other simple tools, such as $1$-out-of-$2$ oblivious transfer (OT). There exist garbling schemes that naturally operate over large finite fields, some of which require only efficient information-theoretic (IT) techniques. However, here the evaluator's input is encoded via an affine function over a large field, so these schemes are not naturally projective, reducing their versatility. We provide a transformation that efficiently projectivizes such schemes. Consider an arithmetic garbling scheme where the evaluator's input consists of elements from a large prime field. Our symmetric-key-based garbling techniques give a mechanism to translate from Yao-style garbled labels to IT-style garbled labels at cost proportional to the input and output labels: crossing the border is duty-free! We apply our technique to two problems. (1) Recent works show that projective garbling schemes solve a problem central to trust-minimized bridges for the Bitcoin blockchain. BABE (Garg et al., 2026) and Argo MAC (Eagen and Lai, 2026) give two different approaches. Both works implicitly construct an efficient IT garbling scheme, then use naive bit-decomposition to achieve projectivity. We construct and implement drop-in replacements for both; we improve BABE's encoding size by $51\times$, and Argo MAC's by $23\times$. (2) Our technique implies a non-interactive reduction from vector oblivious linear evaluations (VOLEs) over $\mathbb{F}_p$ to $1$-out-of-$2$ OTs. To our knowledge, ours is the state-of-the-art Minicrypt (plus base OTs) protocol for large field VOLE secure against a malicious receiver. It costs only $O((\lambda + n) \lg p)$ bits.

Crites and Stewart reduce an adaptive forgery attack on threshold Schnorr signatures with $N$ parties and threshold $\tau$ to one call to a sparse linear search oracle, which they show to be bounded distance decoding of a diagonally scaled Reed–Solomon code and whose sparse answer, a witness, names the parties to corrupt. Their analysis samples the coefficient vector behind the adversary's commitment uniformly at random and leaves open whether a chosen vector does better. We bound the success of an adversary that follows their template with a chosen vector and recovers witnesses only inside regions built from the radii that seven decoding theorems, three for Reed–Solomon and four for folded Reed–Solomon codes, certify under their own setup hypotheses. When the commitment is fixed through a known coefficient vector before a fresh hash challenge, the attack target is, conditional on the history that fixed the vector, a uniform point of a line. For distinct nonzero Shamir points, our main theorem shows that every such line contains at most $M$ targets with a witness in a finite collection of coordinate and block weight regions fixed before the targets, each permitting fewer than $\tau$ nonzero coordinates, for an explicit integer $M$ depending only on $N$, $\tau$ and the collection. We call the adversary the wrapper when it makes at most $Q$ fresh challenges and no signing query, chooses each coefficient vector from its history before the challenge and keeps it afterwards, and lets its solvers make no further signature hash queries. It accepts only a witness of the same target and representation that lies in the regions of the collection within its corruption cap, corrupts parties only once it holds such a witness, and then forges from that witness and stops. Hence the wrapper succeeds with probability at most $QM/p$, with $p$ the group order, even if its solvers recover every witness in the regions at no cost. On the six pairs $(N,\tau)$ of the original attack, fixed collections built from partitions into consecutive blocks contain all seven certified regions and have $M$ below $2^{24}$, so at the field size proxy $p = 2^{252}$ the bound stays below $2^{-100}$ after $2^{128}$ challenges. For uniform targets we prove much smaller bounds on the witness probability in these regions. For the folded Guruswami–Wang and Ashvinkumar–Habib–Srivastava block regions on partitions into consecutive blocks fixed before the target, this probability is negligible for polynomially many parties, exponentially large fields and $\tau/N$ bounded away from zero. These results also classify the studied decoder theorems. The hardness of the oracle, the success of other strategies and the adaptive security of threshold Schnorr schemes are open.

All traditional encryption schemes share a fundamental operational vulnerability: encrypted data must be decrypted before it can be used. Fully homomorphic encryption eliminates this vulnerability by enabling computation directly on encrypted data, but existing FHE schemes impose substantial practical constraints that limit deployment. This paper presents a formal security analysis of the Gribov-Kahrobaei-Shpilrain (GKS) private-key FHE scheme. GKS requires no bootstrapping or de-linearization, produces bit-exact decryption, supports native encrypted search, and scales to unbounded depth.

We investigate non-malleable Incrementally Verifiable Computation (IVC), a subject that has received limited attention. We focus on whether and how simulation-sound IVC can be obtained from falsifiable assumptions. We provide additional evidence of the unique aspects of non-malleable incremental proofs, identifying definitional challenges in formalizing simulation-sound IVC, and showing how existing IVC designs from falsifiable assumptions cannot exhibit simulation-soundness "for free" (without modifications). In addition to a new family of definitions of simulation-sound IVC, our main results are the following. - A general negative result: common Valiant-style proofs are malleable. We isolate and formalize a feature shared by the dominant Valiant-style IVC designs (Valiant, TCC 2008) related to the ability to merge proofs together. We show that, assuming one-way functions, natural zero-knowledge versions of Valiant's design are malleable. As an implication of our framework of attacks, we show that the only IVC for NP from falsifiable assumptions (Datta et al., CRYPTO 2025) cannot satisfy any form of simulation-soundness; this is the case even when instantiating this scheme from non-malleable building blocks. - A positive result: first IVC from falsifiable assumptions with non-malleability features. We construct an IVC satisfying a non-trivial form of simulation-soundness under subexponential iO and either subexponential LWE or subexponential bilinear-map assumptions.

DNS was designed around UDP, and most DNS traffic today still follows that design: one query, one response, and no handshake. This makes DNS fast and scalable, but exposes client queries in cleartext. DoT, DoH, and DoQ provide privacy by encrypting DNS messages with TLS. This works once TLS/TCP or QUIC handshakes complete, but cold sessions spend extra round trips and CPU before the first private query can be sent—a cost that grows with post-quantum cryptography. We present VeilDNS, a DNS-native protocol that uses a post-quantum KEM and AEAD to encrypt DNS questions and answers and authenticate the resolver in a single UDP exchange. Given an authenticated resolver KEM key, clients have query privacy from their first UDP packet. VeilDNS supports stateless and stateful modes—the latter reducing recurring computation and bandwidth. An optional mode provides forward secrecy from the second query onward. By preserving the DNS wire format, VeilDNS runs on the standard UDP port 53. Compared with ML-DSA-authenticated Do(T/H/Q) on the well-provisioned network profile, VeilDNS's stateless and stateful modes achieve up to $3.5\times$ higher cold-session throughput, $4.8\times$ lower average latency, $4.7\times$ lower CPU time, $13.7\times$ fewer bytes, and $15.8\times$ fewer packets. On the constrained profile, the throughput gain reaches $12.4\times$. Tamarin establishes query confidentiality, response authentication, and forward secrecy.

We study fully connected neural-network reconstruction by combining cryptanalytic weight-direction extraction with learning from predicted labels. We adapt a ReLU extraction implementation to Leaky ReLU, compare sign-search methods, and estimate biases and output layers. We prove conditional bounds for direction recovery with approximate prefixes, preservation of local distance votes, prediction changes from aligned parameter errors, and sign selection with independent scoring data. We also specify exact row restoration and distinguish its guarantee from that of gradient masking. The experiments evaluate assisted extraction, with privileged access to gradients, hidden activations, and victim parameters, followed by label-based reconstruction. Across eight search seeds on the largest synthetic architecture, Leaky ReLU recovers 51--57 neurons in the deepest hidden layer, while ReLU recovers none. This advantage does not hold uniformly across architectures and layers. Removing victim-weight access from the sign walk gives less accurate signs, despite high final prediction agreement. Across 40 seeded runs on the two smallest synthetic victims, agreement on 5,000 inputs excluded from fitting and selection ranges from $0.9890$ to $0.9992$. On two CIFAR-10 victims, the reconstructed models achieve $56.40\%$ and $58.29\%$ agreement and exceed the distillation baseline on three functional metrics. We report label requests separately from privileged access and explain why prediction agreement does not identify network parameters.

In this work, we analyze the security of hash-based signatures in Lean4. We examine how different ways of accounting for an adversary’s work yield different notions of bit security. As our working example, we study two instances of XMSS with $128$ bit digests. Under most of the accounting modes we consider, we get $127$ bit security for strong unforgeability. However, under the most conservative convention that counts only the adversary’s direct random oracle queries, we only get $122$ bits of security. We prove these bounds in the random oracle model without computational hardness assumptions and give matching attacks. We also prove a tight bound of $127$ bits of strong unforgeability for SLH-DSA-128s. Our work is primarily motivated by recent autoresearch competitions, and it demonstrates the concrete impact of resource accounting. We hope that it helps designers of future challenges make an informed decision when choosing a notion of bit security that reflects their needs.

In the algebraic model, where one counts operations in $\mathbb{F}_q$ uniformly in the characteristic, the best published algorithm for factoring a polynomial of degree $n$ over $\mathbb{F}_q$, due to Kaltofen and Shoup with the rectangular products of Huang and Pan, uses $n^{1.80535+o(1)}\log q$ operations, and its bottleneck is the modular compositions of the giant steps. A new algorithm is presented for these compositions. Like the algorithm of Neiger, Salvy, Schost and Villard, the new method is based on the relation matrices of the argument. Since all compositions at one level of the giant steps share one argument, the relation matrices and a table of remainders are computed only once, and the remaining work consists of rectangular matrix products. For the two-matrix evaluation, we prove that a random change of basis puts every Frobenius image in good position. This reduces the cost of factorization in this model $$\text{from}\quad n^{1.80535+o(1)}\log q\quad\text{to}\quad n^{1.5532+o(1)}\log q,$$ and to $n^{3/2+o(1)}\log q$ if $\omega=2$; with the compositions of Neiger, Salvy, Schost and Villard performed one at a time, the exponent would be $1.7147$. In the bit model, and algebraically in small characteristic, Kedlaya and Umans obtained the exponent $3/2$. For a single composition with an arbitrary argument modulo a separable polynomial, the content of one short relation separates large value fibers, which gives a Las Vegas algorithm for every input at the exponent $(\omega+3)/4<1.3429$, previously known only for generic inputs, and a fourth evaluation level, with truncated powers obtained by transposition, lowers it to $1.3309$. As applications, we obtain faster algorithms for normal bases, minimal polynomials and irreducibility testing, and, for large $q$, factorization in $O(n^{1.5983})+n^{1+o(1)}\log q$ operations.

The hash-based Leighton-Micali Signature (LMS) has been standardized by IETF, NIST and ISO. State-of-the-art non-quantum security proofs for LMS have been given by Katz (SSR 2016) and Fluhrer (Eprint 2017/553). However, the actual structure of SHA-256(/192) is the (chopped) Merkle-Damg{\aa}rd construction using a blockcipher-based Davies-Meyer function, and precise security bounds of SHA-256-based LMS\_SHA256\_M32 and SHA-256/192-based LMS\_SHA256\_M24 should be derived in the {\it ideal-cipher model (ICM)}. This was {\it not} considered in Katz and Fluhrer's proofs. In fact, by leveraging structural properties of (chopped) Merkle-Damg{\aa}rd, we exhibit forgery attacks against LMS\_SHA256\_M32 and LMS\_SHA256\_M24 that expose the inapplicability of Katz's and Fluhrer's random-oracle bounds to the concrete SHA-256 constructions. The precise security guarantees of LMS\_SHA256\_M32 and LMS\_SHA256\_M24 thus remain unknown (and are also missing in the standards). To bridge the structural gap, we provide ICM-based security proofs for the additive-Davies-Meyer abstractions of LMS\_SHA256\_M32 and LMS\_SHA256\_M24. The security level of LMS\_SHA256\_M32 is roughly $256-\log_2 \widehat{B}$ bits, where $\widehat{B}$ is the number of blocks in SHA-256 calls internally made by LMS\_SHA256\_M32 and $\widehat{B}\ll2^{128}$. The security level of LMS\_SHA256\_M24 is roughly $\min \{ 192 - \log_2 \widehat{\Gamma} , 256-\log_2 \widehat{B} \}$ bits, where $\widehat{\Gamma}$ is the number of SHA-256/192 calls internally made by LMS\_SHA256\_M24 and $\widehat{B}$ is the number of blocks in them, and $\widehat{B}\ll2^{128}$ and $\widehat{B} \widehat{\Gamma} \ll 2^{192}$. In conclusion, LMS\_SHA256\_M32 and LMS\_SHA256\_M24 ensure a moderate (yet not ``full'') level of security.

Let $\operatorname{RM}(r,n)$ be the $r$th order Reed--Muller code of length $2^n$, and let $\rho(r,n)$ denote its covering radius. The values $\rho(2,6)=18$ and $\rho(2,7)=40$ are known, whereas the exact value of $\rho(2,8)$ remains open. Starting from the current state of the art bound $88\leq\rho(2,8)\leq96$, we give a computer-assisted reduction of the upper bound $\rho(2,8)\leq91$. We first show that every even-weight Boolean function on eight variables is within distance $90$ of a quadratic function. Changing one value then gives the bound $91$ for odd-weight functions. Our main lemma addresses rank-four seven-variable quintics: when their second-order distance is $36$ and their maximum quadratic-shift first-order distance is $56$, they have at least $60$ minimizing quadratic cosets and at most $12$ cosets of cost $56$. The complete proof covers all $68443$ quartic classes. For every rank-four quintic, the distance-$56$ cosets are enumerated outright, and the $5199$ words are examined individually. Profile counts, hyperplane contractions, and support moments then give the even-weight bound. We describe the calculations and enumerations, together with the classification upon which the proof depends. Instructions to verify the computer search portion may be found at $\texttt{https://github.com/EvelynSabo/RM28}$.

Let $\omega$ denote the matrix multiplication exponent. Very recently, OpenAI showed that $\omega\le9/4$. We demonstrate that, for any fixed $\eta>0$, if $\omega\le9/4-\eta$, then there is a constant $\delta=\delta(\eta)>0$ such that heuristic lattice sieving can be improved to $(3/2-\delta)^{n/2+o(n)}$ time under the spherical heuristic used in the BDGL analysis. With known matrix multiplication algorithms, our method already yields subquadratic search within BDGL buckets.

We revisit a classical result of Coppersmith and Shparlinski [CS00] showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $\deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = \mathsf{dlog}(x) \}| \leq \sqrt{2 D p}.$$ We show two improvements: (1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas. (2) For $D = 1$, where both the above bounds are $\mathcal{O}(\sqrt{p})$, we give an asymptotically improved upper bound of $\mathcal{O}(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics. We also improve the [CS00] bounds on the number of points of the form $(x, \mathsf{dlog}(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $\deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.

Due to their widespread applications in decentralized and privacy preserving technologies, commitment schemes have become increasingly important cryptographic primitives. With a wide variety of applications, many new constructions have been proposed, each enjoying different features and security guarantees. In this paper, we systematize the designs, features, properties, and applications of vector commitments (VCs). We define vector, polynomial, and functional commitments and we discuss the relationships shared between these types of commitment schemes. We first provide an overview of the definitions of the commitment schemes we will consider, as well as their security notions and various properties they can have. We proceed to compare popular constructions, taking into account the properties each one enjoys, their proof/update information sizes, and their proof/commitment complexities. We also consider their effectiveness in various decentralized and privacy preserving applications. Finally, we conclude by discussing some potential directions for future work.

Bitcoin bridges, protocols that lock BTC on Bitcoin and represent it on a secondary system, underpin much of Bitcoin's application layer, yet remain poorly secured. Deployed bridges rely on federated custody with honest-majority assumptions, while BitVM2, the state of the art in trust-minimized bridging, incurs worst-case dispute costs of approximately \$16,000, requiring large operator bonds and deposits that restrict participation to well-capitalized parties. We present BitVM3-BRIDGE, a trust-minimized bridge architecture from Bitcoin to (i) chains with finality certificates, such as Ethereum, and (ii) Bitcoin rollups. Our main contribution is an end-to-end bridge construction that makes trust-minimized Bitcoin bridging practical at scale. The bridge is powered by BitVM3-CORE, a modular abstraction for permissionless off-chain computation on Bitcoin using garbled circuits. In BitVM3-CORE, a challenger evaluates a garbled circuit entirely off-chain and obtains a fraud-proof witness if and only if the operator's claim is incorrect. This paradigm reduces total on-chain costs to approximately \$9, with the challenge transaction itself costing just \$0.20. This nearly 1000× cost reduction enables smaller bonds, broader operator participation, and smaller deposit sizes. Beyond the bridge itself, we make two additional contributions. First, we formalize BitVM3-CORE as a sound and complete on-chain proof system under standard cryptographic assumptions. Prior GC-based proposals typically provide either informal security arguments or construction-specific formalizations. By contrast, our framework captures existing constructions within a uniform model and gives a generic treatment based on axiomatized security and functional assumptions. Second, we introduce an on-chain Bitcoin light client secure in the variable-difficulty setting, enabling permissionless chain introspection on Bitcoin and thereby the rollup variant of BitVM3-BRIDGE.

Although recent surveys on privacy-enhancing technologies concluded that FHE cannot feasibly evaluate non-linear activation functions in modern ML architectures, 21 CKKS-based frameworks have since demonstrated end-to-end private inference of LLMs with up to 8B parameters. However, as the field grows rapidly, the literature has become fragmented. Frameworks differ in ciphertext packing layouts, model fidelity, software and hardware stacks, and reported metrics, that hinder direct comparison and reproducibility. This paper presents the first systematization of knowledge for non-interactive, CKKS-based private LLM inference. We categorize the design space across two axes: a model-level axis (packing layout for linear blocks and model preservation for non-linear blocks) and a system-level axis (covering hardware, compilers, bootstrapping management, and hybrid execution). To standardize reporting framework configurations and results among researchers, we propose a Private LLM Card System (PLCS). Furthermore, we introduce POLARIS, a model-preserving reference framework for CKKS-based private LLM inference and provide it as an open-source proof-of-concept. POLARIS evaluates encrypted inference for the entire BERT family, from BERT-Tiny to BERT-Base, on CPU and GPU backends, the first framework to demonstrate this. Our analysis shows that only 5 out of the 21 surveyed frameworks are model-preserving, that is, they evaluate standard, unmodified LLMs without retraining or architectural substitutions while keeping the entire prompt encrypted. We also show that model-preserving CKKS approximations maintain high downstream task accuracy from BERT-Tiny up to Llama-3-8B. We identify a runtime gap of roughly four orders of magnitude between the best encrypted and plaintext inference as the primary barrier to practical use. While our analysis confirms that CKKS-based inference is now algorithmically feasible for non-linear functions and large models, we conclude that it remains operationally impractical for many human-facing applications until the efficiency gap is narrowed. We outline promising research directions to close this gap.

Threshold encrypted mempools protect the privacy of transactions up until the point their inclusion on chain is confirmed. They are a promising approach to protection against front-running attacks on decentralized blockchains. Recent works have introduced two key properties that an encryption scheme must satisfy to operate efficiently on large-scale decentralized blockchains such as Ethereum: Silent Setup, as introduced by Garg et al. (CRYPTO'24), demands that a threshold encryption scheme does not require any interaction during the setup phase and only relies on the existence of Public Key Infrastructure. Batched Decryption, as introduced by Choudhuri et al. (USENIX'24), demands that an entire block containing $B$ encrypted transactions can be decrypted using communication that is independent of (or sublinear in) $B$, without compromising the privacy of transactions that have not yet been confirmed. While existing constructions achieve either Silent Setup or Batched Decryption independently, a truly decentralized and scalable encrypted mempool requires both properties to be satisfied simultaneously. In this work, we present the first "Batched Threshold Encryption scheme with Silent Setup" built using bilinear pairings. We provide formal definitions for the primitive and prove security in the Generic Group Model. We provide several optimizations and implement our scheme to evaluate its performance. Our experiments demonstrate its efficiency for deployment in blockchain systems.

At a high level our contribution is threefold: we improve the quantitative MCA error bound for polynomial generators, we prove a refinement of the implication from list-decodability to MCA, and we clarify that in general, these two notions are distinct. We show that, for every finite field $\mathbb{F}$, every nonempty seed set $S\subseteq\mathbb{F}$, every linear code $\mathcal{C} \subseteq \mathbb{F}^{n}$ of relative minimum distance $\delta_{\mathcal{C}}$ and every degree $d \geq 1$, the univariate powers generator $G_{d}(x) := (1,x,\dots,x^{d})$ has mutual correlated agreement for $\mathcal{C}$ at relative proximity parameter $\gamma$ with error $O(d\max\{1,n\gamma\}/|S|)$ below the smaller of the unique decoding radius and the generalized Johnson radius $J_{d+2}(\delta_{\mathcal{C}}) := 1-(1-\delta_{\mathcal{C}})^{1/(d+2)}$, with a one-coordinate margin below the latter when it is smaller. Then, we show that list-decodability at radius $p$ with list size $L$ implies MCA slightly above $1-\sqrt{1-p}$ (the improvement on the radius is dependent on the list size). The previous state-of-the-art result of Gao, Cai, Xu and Kan showed that list-decodability at radius $p<\delta_{\mathcal{C}}$ with list size $L$ implies mutual correlated agreement at every proximity parameter strictly below $1-\sqrt{1-p}$. Finally we construct two families of codes that show obstructions to any improvement of the $1-\sqrt{1-p}$ bound, or to strong converse statements. Informally, a bound of the form $\epsilon_{\mathsf{MCA}}(1-(1-p)^\alpha)\leq Q(n, L)/|\mathbb{F}|$ for some polynomial $Q$ and $\alpha > 1/2$ cannot hold for all linear codes $\mathcal{C}$ under the sole hypothesis that $\mathcal{C}$ is $(p,L)$-list-decodable. Similarly, for any distance $0<\delta<1$ and any $1-\sqrt{1-\delta}<p<\gamma<1$, there exists a family of linear codes with fixed positive rate and relative distance tending to $\delta$ such that $|\mathbb{F}|\epsilon_{\mathsf{MCA}}(\gamma)\leq \mathrm{poly}(n)$ but the list size at radius $p$ is $n^{\omega(1)}$. Both counterexample families exist over fields of any characteristic. Both MCA errors are for the line generator.

In lattice sieving, the sphere model assumes that sieving elements are distributed close to or on a sphere with uniformly distributed direction. It is extensively used to predict how lattice sieving behaves. In the sphere model the probability that a random pair of vectors reduces is asymptotically $p_n={(3/4)}^{n/2}/\sqrt{3\pi n/8}$. In practice sieving algorithms have been observed to perform better than predicted by the sphere model. It is an open question how this gap behaves asymptotically: does the gap vanish or grow as the dimension grows? Our work answers this question by showing that it is asymptotically constant. We generalise the sphere model to uniform ball and non-uniform ball models and analyse reduction probability distributions. The reduction probability advantages of our models over the sphere model range from $\times 1.5$ up to $\times 8$. Moreover, we examine scaled depth distributions (defined for dimension $n$ as $w=-n \ln \|x\|$) in the asymptotic setting. Under global reductions the output scaled depth distribution converges to $\text{Exp}(2/3)$ for any converging family of scaled depth distributions that is dominated by a suitable integrable function. The input scaled depth distribution only affects the total reduction probability. Compared to (the scaled depth distribution $\text{Exp}(1)$ induced by) the uniform ball as input distribution, using this stable limit distribution as input distribution results in an increased reduction probability ($\times 4.5$ versus $\times 8$).

Programmable bootstrapping (PBS) in FHEW/TFHE evaluates a lookup table (LUT) while refreshing a ciphertext, but a t-entry negacyclic table must fit, with redundancy, into the 2N signed rotation positions of a ring accumulator. Module bootstrappings, namely extended bootstrapping (PKC'23), monomial-matrix bootstrapping (TCC'25) and their successors, rotate a redundant table once in a module of rank tau, at a cost linear in both the rank and the redundancy. Meta-PBS (CCS'26) removes the redundancy by iterating the rotation in the ring, but supports plaintext moduli only up to 2N, and running it inside the module pays the rank in every rotation. We present Descent-PBS, which pays the module rank of a large table only in its first rotation. We prove that for a module secret embedded from the subring, truncation commutes with the secret, so one public functional key switch with merged columns repacks all tau_0 components of a module accumulator into the ring and removes the per-component factor tau_0 of repacking. The bootstrapping then continues with Meta-PBS refinements in the ring, at tau_0 + K instead of (K'+1) tau_0 external products per key. For block one-hot secrets, the first-rotation exponents are multiples of tau_0, so every combined key is a scalar matrix: the tau_0 components share one key per block, and since all exponents are public in advance, one pass over the bootstrapping key builds the keys of all rotations of a negacyclic table. Ties-to-even gadget rounding removes a refinement bias that we trace to half-up rounding on the FFT grid. In a TFHE-rs-based engine, Descent-PBS evaluates a 16-bit negacyclic LUT in 196 ms on one thread at 128-bit security and a model-predicted failure probability below 2^-64. With the same keys and failure budget, the descent alone makes it 1.44-2.40x faster than Meta-PBS run inside the module for dense secrets; for block one-hot secrets, the descent and the shared keys together make it 1.51-3.32x faster, and 1.37-3.57x against the same baseline re-planned for more conservative 131-bit parameters. General 13-16-bit LUTs take 179-368 ms, 3.8-6.6x faster than WoP-PBS in its authors' configuration on the same single-ciphertext interface, at about twice its memory. The failure probabilities are predictions of a model that we validate where failures are observable, and the 16-bit keys take 1,208 MB.

SQIsign is a compact isogeny-based signature scheme. We present a low-latency AVX-512 implementation of complete SQIsign 3.0 verification at security levels I, III, and V. Our implementation provides vectorized curve-side verification, including the Superglue transition, and introduces dynamic-programming strategies for the degree-$2^\ell$ and theta-model $(2,2)$-isogeny chains. The strategies account for batched point evaluation and the preparation of SIMD data. On an Intel Core i7-11800H running native Ubuntu 24.04, the complete verifiers achieve $2.14\times$, $2.08\times$, and $2.34\times$ speedups, respectively, over the SQIsign 3.0 Broadwell reference verifiers (the optimized 64-bit assembly implementation).

Motivated by the accordion mode approach, we propose a length preserving tweakable wide block mode based on the hash-encrypt-hash paradigm. The construction uses AES and HMAC-SHA3-256 with five purpose separated working keys derived from a single master key, replacing algebraic universal hashing with a cryptographic keyed hash. An encrypted internal seed couples two separately keyed head branches and determines the counter mode keystream. The head layers permit parallel evaluation, while inter-branch dependence is retained even when the tail is empty. The mode supports every bit length within its specified range, starting from $2n$ bits without padding, where $n$ is the block size. Variable length external information is incorporated into a fixed length core tweak through application specific preprocessing. We establish birthday bound tweakable variable-input-length strong pseudorandom permutation security under the stated block cipher, keyed hash, and key derivation assumptions. The analysis covers adaptive encryption and decryption queries, varying message lengths, repeated tweaks, and reused internal values. We also describe derived interfaces for authenticated encryption with associated data, tweakable encryption, and deterministic authenticated encryption, distinguishing their additional security requirements from the core guarantee.

The 2007 algorithm of Joux, Naccache, and Thomé (JNT) shows that, with subexponential access to an $e$-th root oracle, one can forge RSA signatures for odd $e$ in time close to the special number field sieve, without factoring the modulus; a recent JNT implementation by Shea et al. [2] carried that attack to $1024$-bit RSA. We revisit the JNT construction at $e=2$, the Rabin case, where an $e$-th root oracle is a square-root oracle. A raw square-root oracle factors $n=pq$ in one query, so it is of no interest; the interesting object is a redundancy-constrained (affine-padded) Rabin oracle that returns a single canonical root and thereby resists the one-query attack. We show that a one-sided number field sieve against such an oracle produces a congruence of squares $X^2\equiv Y^2\pmod n$ with $X\not\equiv\pm Y$ with probability $\tfrac12$ per dependency, and hence factors $n$ in special-number-field-sieve time \[ L_n \left(\frac{1}{3},{\sqrt[3]{\frac{32}{9}}}\right)\simeq L_n(1/3,{1.526\ldots}), \] strictly below the general number field sieve's \[ L_n \left(\frac{1}{3},{\sqrt[3]{\frac{64}{9}}}\right)\simeq L_n(1/3,{1.923\ldots}). \] The mechanism is a pleasant inversion: the sign ambiguity that the odd-$e$ algorithm must suppress becomes, at $e=2$, the very quantity that leaks the factorization. We give the algorithm in full --- LLL polynomial selection for a quadratic field, a line sieve producing prime-ideal relations, quadratic characters, $\mathbb F_2$ linear algebra, and an exact number-field square root --- prove the half-rate splitting, and analyse the complexity, including the precise reason the attack collapses when the padding is a hash rather than an affine function of an attacker-chosen message. An open-source implementation realises every step. A small toy example run of it, from the padded modulus to the recovered factors, is given in Appendix A. Our implementation confirms a clear performance improvement in factoring speed.

The FX construction (FX) is one of the simplest key-length extension schemes for block ciphers, introduced by Kilian and Rogaway as a generalization of DESX. By extending the key length without modifying the underlying block cipher, FX can improve security against adversaries that perform quantum computation but are restricted to classical queries to the keyed construction. Recently, Shiba and Iwata showed in their ToSC 2026 paper that FX with an $n$-bit block and a $\kappa$-bit internal key is secure up to approximately $2^{(n+\kappa-\log_2\mu)/3}$ total classical and quantum oracle queries in the quantum ideal cipher model, where $\mu\leq2^\kappa$ is the number of independently keyed instances. In this paper, we improve this bound to approximately $2^{(n+\kappa)/3}$ total oracle queries in the same model against fully adaptive adversaries, for every $\mu\geq1$ and $1\leq\kappa\leq2n$. The known attack based on the offline Simon's algorithm can target a single keyed instance and matches our bound in the exponent. Thus, the exponent of the total query complexity required to break FX is independent of the number of keyed instances in this parameter regime.

Motivated by the MAMBA proposals, we study the worst case hardness of learning with quantization (LWQ) with public dither. We allow any efficiently computable dither function and efficiently samplable seed distribution; the matrix is uniform and independent of the secret and the seed. Using the randomized polar lattice quantizer of Lyu et al., we construct explicit families with polynomial power of two moduli. For the search family, polynomial time recovery of the uniformly chosen secret with inverse polynomial probability yields quantum polynomial time algorithms for the gap shortest vector problem (GapSVP) and the shortest independent vectors problem (SIVP) on arbitrary \(n\) dimensional lattices, with approximation factors \(O(n\log n)\) and \(O(n(\log n)^2)\), respectively. Under stronger parameter conditions, a second family admits a decision reduction: a polynomial time algorithm with inverse polynomial distinguishing advantage yields quantum polynomial time algorithms for the same lattice problems with factors \(O(n(\log n)^3)\) and \(O(n(\log n)^4)\), respectively. Conditional on the public seed, the comparison output is uniform in the prescribed dither coset and independent of the matrix. We also examine extensions to learning with errors (LWE) with interval uniform errors, as arising in MAMBA Frost. We identify obstacles caused by deterministic quantization boundaries and give a local perturbation bound with explicit dependence on the number of observations. This analysis does not establish a complete worst case reduction for these errors or hardness at the concrete MAMBA parameters.

Bitcoin Script lacks native pairing operations for efficient direct verification of Groth16 proofs. Conventional federated bridges instead authorize withdrawals through a signing quorum, whose collusion can release funds without valid evidence. We present the Tritone protocol, which lets Bitcoin enforce the outcome of verifying a Groth16 proof for an NP relation fixed in a one-time trusted setup, with the locked funds secure as long as one of a fixed set of $N$ operators is honest. Verification is optimistic and off-chain, and every transaction is standard under current relay policy, so Tritone runs on Bitcoin today without consensus changes. Tritone generalizes the two-party BABE protocol to a fixed committee of $N$ operators, with one dispute instance per ordered pair. Cut-and-choose protects against malicious garblers, while Feldman verifiable secret sharing correlates input keys across candidates. Our new Lamport-adaptor gadget forces a challenging verifier to disclose the shares selected by the prover's committed proof element, providing the transaction-level binding left unspecified by BABE. A single set of disclosed shares then unlocks all retained candidates. We formalize the multi-party primitive, prove the protocol secure against up to $N-1$ statically corrupted operators, and specify its complete pre-signed transaction graph. We implement Tritone in Rust. On Bitcoin mainnet, when one verifier disputes a claim at every stage, the prover-candidate posts 9,607 vB and the verifier 18,160 vB of protocol transactions. In local benchmarks at 40-bit statistical security, the prover-candidate of each dispute instance retains as little as 112.83 MiB. Tritone thus replaces trust in a signing quorum with a single-honest-operator assumption wherever locked bitcoin is released to an operator against a Groth16 proof, with Bitcoin bridges as our showcase.

Hardware accelerators for lattice-based post-quantum cryptography (PQC) have largely converged on the radix-2 number-theoretic transform (NTT). The spectrum of standards that crypto-agility must accommodate, however, extends beyond NIST. In response to advances in cryptanalysis and to reduce the attack surface, national authorities are standardizing or recommending lattice-based algorithms with alternative algebraic structures, as well as schemes built on entirely different primitives. For instance, NTRU+, selected in the Korean PQC competition and currently undergoing standardization, is defined over a trinomial ring whose degree is divisible by three and thus requires a mixed-radix NTT comprising both radix-2 and radix-3 layers, whereas SMAUG-T employs an NTT-unfriendly modulus. Support for heterogeneous algebraic structures is therefore no longer optional but a prerequisite for crypto-agile design; existing radix-2-centric accelerators, however, fail to meet this requirement. In this paper, we present a crypto-agile mixed-radix NTT accelerator that performs transforms over both negacyclic and trinomial rings on a single datapath. Our contributions are threefold. First, we design a unified butterfly unit that integrates two parallel radix-2 butterflies, one radix-3 butterfly, and the trinomial transform on shared arithmetic resources, in which a generic 17-bit Montgomery path and an ML-DSA-specific 23-bit reduction path share the same two DSPs. Second, we propose a conflict-free memory mapping that guarantees in-place parallel access across all mixed-radix layers with a single 1-bit bank-selection function, namely address parity for radix-2 and a fixed address bit for radix-3, and requires neither mapping tables, nor coefficient reordering, nor additional BRAMs. Third, we introduce a generalized modular constant division that combines the multiple alignment of Montgomery reduction with the quotient estimation of Barrett reduction to perform the $3^{-1}$ scaling of the radix-3 inverse NTT without any DSP. Implemented on an Artix-7 FPGA, the proposed core supports all security levels of ML-KEM, ML-DSA, HAETAE, SMAUG-T, and NTRU+ using 5,279 LUTs, 4 DSPs, and 9 BRAMs at 141.5~MHz. For NTRU+, it achieves a $4.1$--$13.0\times$ improvement in area-time product (ATP) over approaches that resort to radix-2-only cores via degree lifting, and new moduli of up to 17 bits can be integrated at the cost of fewer than 20 LUTs.

Evaluating the hardness of the Shortest Vector Problem (SVP) is essential for selecting secure parameters in lattice-based cryptography. The fastest current SVP solvers are based on variants of G6K, but their large memory consumption remains a major bottleneck, making high-dimensional executions difficult. A common strategy for alleviating this memory bottleneck is strong basis reduction preprocessing before a sieve-based algorithm. This strategy can solve SVP instances in higher dimensions than standalone G6K under the same memory constraints, but the time required for basis reduction becomes a major issue. ProPnjBKZ, a fast basis reduction algorithm optimized by Wang et al., is currently used as a promising preprocessing method for solving high-dimensional SVP instances. In this paper, we identify that, in the ProPnjBKZ-based SVP-solving pipeline, memory resources can remain underutilized during the preprocessing phase, since ProPnjBKZ requires less memory than the subsequent high-dimensional sieving process. Based on this observation, we propose AH-BKZ, which exploits such unused computational resources by asynchronously running multiple SVP oracles, thereby accelerating basis reduction. Our experiments show that, compared with ProPnjBKZ-based preprocessing, AH-BKZ reduces the overall runtime by up to 23.1% and by 18.6% on average among successful runs for dimensions 124-148 under comparable peak memory constraints. Moreover, in a supplementary experiment conducted in a larger computational environment, AH-BKZ set new solving records for dimension 163 in the TU Darmstadt SVP Challenge and for dimension 164 in the Ideal Lattice Challenge.

Blockchain technology allows parties to use a consensus protocol to add transactions and data to a decentralized ledger that are immutable. However, the amount of transactions that can be processed within a consensus protocol and thus added to the ledger within a given time frame is limited. This is a scalability issue. Layer-2 protocols are a class of approaches that process transactions off-chain, i.e. without involvement of the consensus protocol, but allow usage of the consensus protocol as a backup for security. This potentially reduces the processing of $n\in\mathbb{N}$ transactions to only $\mathcal{O}(1)$ transactions being committed to the ledger. The basic building blocks of Layer 2 protocols are Payment Channels, whereas newer protocols as Hydra (FC'21) allow for multi-party channels that are not limited to payments but can execute smart contracts, i.e. program code. There has been substantial research proposing tools and improvements to Layer 2 protocols, but most assume the original two party Payment Channel design. This makes it unclear to what degree existing techniques can be utilized with Hydra style multi-party channels. This work (1) presents a survey of such such existing two party channel protocols and tools built on top of them. We use a didactic approach with a focus on explaining their core ideas. (2) This work identifies uses cases for which novel protocols for Hydra should be developed. (3) This work analyzes open problems for Hydra, lists relevant related work and proposes which existing tools can be used to address them or serve as a starting point for further research.

We prove that ten rounds of \AES{} with independent and uniform random round keys are $\varepsilon_{10}$-close to pairwise independent, with \[ \varepsilon_{10}\leq\frac{3017}{2^{141}}<2^{-129}. \] For every two distinct plaintexts, the joint ciphertext distribution is therefore within this statistical distance of the uniform distribution on ordered pairs of distinct ciphertexts. The same sampled key tuple is used for both encryptions. The construction retains the \AES{} round transformations, including the omission of MixColumns in the final round, with input and output whitening. Let $E_{10}$ denote this random permutation and $\Omega$ the set of nonzero differences. We establish the result through the induced one-norm bound $\norm{\Dten-U}_1\leq3017/2^{140}$ on its averaged difference-distribution matrix restricted to $\Omega$, where $U$ projects onto the uniform distribution on $\Omega$. The proof groups the ten rounds into five superbox layers and decomposes the deviation from uniformity into fourteen orthogonal subspaces according to the number of active words and residual factors. Local Gram moments and MDS code constraints control the dependencies between word differences. Bounds for the distributions produced by the first rounds preserve their common source variables, while joint estimates for the last four rounds retain the constraints across two linear layers. The final conversion to statistical distance uses the support size of each component. Exact rational evaluation of the resulting finite recurrence establishes the stated bound.

CMoSS facilitates modular specifications, design and analysis of cryptographic protocols. Modular design and analysis is achieved by supporting provably-secure compositions of protocols; typically, a protocol uses a blackbox subprotocol, and is proven secure when composed with any subprotocol meeting the blackbox specifications. For modularity of specifications, CMoSS extends the approach of the MoSS framework: protocol specifications are defined modularly, by a set of independent predicates (games) for each model (assumption) and requirement (goal). CMoSS makes it feasible to rigorously specify, develop and analyze realistic applied cryptographic protocols, supporting real-time concurrency and involving different attacker capabilities, delays, faults and synchronization challenges. CMoSS specifications provide a precise formalization of the informal specifications used by practitioners, facilitating provable security for practical protocols.

Error-correcting codes are a useful tool in cryptography, being used both to design schemes whose hardness relies on coding theory problems (the area typically known as code-based cryptography) and as a building block in other contexts, such as proof systems and associated cryptographic argument systems. Among all codes used in cryptography, Goppa codes stand out, notably in the well-known McEliece encryption scheme, where they have withstood the test of time as one of very few classes of codes to be considered secure for over 40 years. Therefore, a natural question is whether Goppa codes can also be used in the construction of proof systems or cryptographic argument systems. In the context of probabilistically checkable proofs (PCPs), codes are used to transform proofs into a format that requires only a constant number of queries for verification. This efficiency is often achieved using low-degree polynomial codes, which enable the verifier to check consistency through interpolation, ensuring correctness with minimal effort. This application underscores the importance of good codes in enhancing the robustness and verifiability of proof systems. Given their critical role, we take a closer look at how error-correcting codes are used in proof systems to find a new way of obtaining an interactive oracle proof system of proximity (IOPP) from Goppa codes.

Private search engines allow a user to retrieve documents from a public database that are similar to a text query. Our cryptographic protocol Mímir employs state-of-the-art homomorphic ciphertext switching techniques to realize the first stateless semantic private search engine for highly dynamic databases. The security of Mímir relies on (Ring) Learning with Errors. Mímir requires no offline communication, and it trades higher but highly parallelizable server computation for low per-query communication. When the database may change between queries, Mímir matches Tiptoe's search quality with 84$\times$ less per-query communication (0.24 MiB). At Tiptoe's per-query communication, it reaches 64$\%$ instead of 36$\%$ of non-private search quality and is 4.2$\times$ faster (0.87s on a single multithreaded machine). Against PACMANN, Mímir improves search quality from 76$\%$ to 81$\%$ of non-private with 72$\%$ of its per-query communication and a 9.54 MiB instead of 2.68 GiB one-time cost, but is 2.1$\times$ slower. Mímir can achieve 59$\%$ of the non-private search quality with 8.13 MiB of per-query communication and 0.77s of total latency. This matches PACMANN's latency at a 7.6$\times$ smaller per-query communication, and outperforms Tiptoe in all three metrics.

Universal thresholdizers offer one-round threshold signatures, but require evaluating an entire signer under fully homomorphic encryption (FHE). We present Balsamic, a complete homomorphic Unbalanced Oil and Vinegar (UOV) signer and its application to one-round threshold UOV signature. UOV's short salted target hash shifts the encrypted workload to finite-field linear solving, which we integrate with coin derivation and hashing in a packed discrete-CKKS circuit. Our paired-pivot solver selects both pivots before first-pivot normalization, then applies their coupled update with one inversion stage per pair and cubic field work. Pivot-success certificates enable encrypted retry selection without residual evaluation. In 2-out-of-3 semihonest threshold UOV signing, each partial signing (online) takes $10.7$ seconds on NVIDIA RTX 6000 Ada and $7.77$ seconds on NVIDIA GB300, with $5.25$ MB per response. These measurements demonstrate that complete homomorphic signing can provide the computational core of one-round threshold signatures without intermediate openings or per-signature interactive preprocessing.

Understanding the hardness of the complexity class PPAD is an important question in complexity theory given that it contains problems such as computing a Nash equilibrium. Evidence of hardness, however, has come primarily from cryptography, through a long line of work. Most recently, Chen, Freitag, Jin and Wichs (STOC 2025) based the hardness of PPAD on the polynomial hardness of the Learning with Errors (LWE) problem, together with a fine-grained average-case hardness assumption. In this work, we base the hardness of PPAD on a different lattice problem, the Short Integer Solution (SIS) problem, which, unlike the assumptions underlying prior work, is not known to imply public-key encryption. Specifically, we show that PPAD is hard on average assuming either: (i) polynomially hard SIS with a quasi-polynomial norm bound and a fine-grained average-case hardness assumption; or (ii) subexponentially hard SIS alone. Our main technical contribution is a succinct, incrementally updatable proof system for a class of exponentially large circuits with short descriptions. Building on the work of Wee (CRYPTO 2025) for succinct proof systems for circuits from SIS, we show how to make such proof systems satisfy these properties while preserving the unambiguity guarantee of the underlying scheme: it is hard to find two distinct accepted states for the same computation and time. Together, these are crucial for our PPAD hardness reductions.

Classical integral cryptanalysis relies on zero-sum properties that, for every key, hold with probability one. Existing arguments against such deterministic integrals, based on the division property and its algebraic variants, only exclude this extreme case: once the zero-sum probability falls below one, they say nothing about its actual value, nor about a probabilistic bias that could still be exploited. We develop a tool combining MILP-based trail search with a recursive evaluation of assignments to the constant inputs. It estimates the probability that no valid trail remains and uses an additional heuristic to predict the zero-sum probability. Applying this tool to PRESENT and GIFT, we obtain probabilistic integral distinguishers for 6 to 9 rounds, including 6- and 7-round PRESENT distinguishers using $2^4$ and $2^{12}$ plaintexts per structure, respectively. For the ASCON permutation, we obtain 4- and 5-round distinguishers using as few as $2$ and $2^{12}$ inputs per structure. We further explain algebraically the large bias of the 6-round PRESENT distinguisher, showing how the S-box and bit permutation restrict the way active variables combine. Finally, we show how these distinguishers can be used for key recovery, reducing both the data and time complexities compared to their deterministic variants for PRESENT and GIFT-64.

At CT-RSA 2026, Ng and Lau introduced $(t,n)$-integer coordinate families for threshold RSA signatures with $e=3$, and found some families by heuristic search for $2\le t \le n \le 9$. They asked whether such families always exist and, if so, can they be constructed efficiently. We answer both of these questions positively. We prove that a $(t,n)$-integer coordinate family is also a $(t+1,n)$-integer coordinate family. We construct such families for $t=2$, and $2\le n < 19$, using a polynomial time algorithm in $n$ and its output bit length. Answering another question raised in the Ng-Lau work, we prove super-polynomial lower bounds on coordinates of pairwise families. We also find the minimum families for $n \le 9$. Ng and Lau proposed a threshold signature scheme based on integer coordinate families. We show that the Ng-Lau scheme admits trivial forgeries, and has a flawed proof. We give a repaired scheme $\mathrm{PiIC}$ which does not suffer from these issues. Finally, we propose an integer secret-sharing scheme $\mathrm{PiZ}$ that works for every prime $e$ and every $(t,n)$, without relying on any special coordinate family. We prove that both the schemes $\mathrm{PiIC}$ and $\mathrm{PiZ}$ are TS-UF-CMA secure under the standard RSA assumption.

Generalized CKKS (GCKKS) trades slot count for reduced modulus consumption in high-precision approximate arithmetic. However, designing a GCKKS bootstrapping algorithm with reduced modulus consumption throughout its computation remains a challenging problem. We construct high-precision bootstrapping for GCKKS using low-precision overflow extraction followed by iterative precision enhancement. Our main ingredient is a ciphertext-conversion framework for changing the decryption factor and slot count without requiring the factors to be units. A slot-aware analysis bounds unused-slot magnitudes proportionally to the corresponding evaluations of the decryption factor, which is essential to ensure the unused-slot values remain well-bounded after conversion. We combine precision doubling with ciphertext splitting and develop a joint evaluation procedure that produces two error-cleaned outputs at the cost of only one evaluation of the cleaning polynomial. We also give a useful-slot-preserving conversion from CKKS to GCKKS that simultaneously resets unused slots through component-wise re-encoding. Underlying these constructions, we also improve the construction of the decryption factors by searching directly in the canonical embedding and obtain depth-free conjugation with non-unit factors. For target encoding precision $p$ and $2N/k$ useful slots in a ring of dimension $N$, the precision-dependent stages of the bootstrapping use $O(k)$ homomorphic operations and consume $O((p/k)\log k)$ modulus bits.

In the average key setting, a linear attack of Bak et al. on the TFHE-friendly stream cipher FRAST let wrong guesses pass, which they left as an open problem. The S-boxes of FRAST are public and random for every keystream block. For the mask on the least significant bit, we show that key differences fall into five indistinguishable classes per round. The filter of Bak et al. gives some wrong classes of the right parity a nonzero expected score. We compute the trail correlation exactly through the real cipher and bound the success of our statistic for every fixed master key. We bound its false alarms for a fixed master key with the last round kept and no filter, and for every attack against an ideal keystream. With known XOF inputs, our algorithm Contract recovered the classes of a branch pair of 15 rounds and the master key of ten rounds. A cost model gives class recovery for every sampled key at 26 rounds with known inputs and for a third at 38 rounds with chosen inputs. In the accounting of Bak et al., it reaches full FRAST on weak master keys of density $2^{-11.8}$ to $2^{-5.4}$ within the claimed security. A distinguisher of full FRAST has a proved advantage on these keys, and its time over the advantage stays below the claimed security as well. Independent branch S-boxes remove the cheap classes at a cost in TFHE.

Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data without decryption, providing strong privacy guarantees for secure cloud computing, encrypted analytics, and privacy-preserving machine learning. However, practical deployment of FHE remains limited by the high computational cost of polynomial arithmetic over large modular rings. In particular, Number Theoretic Transform (NTT)–based polynomial multiplication dominates the execution time of modern lattice-based FHE schemes. In this work, we present TP-NTT, a scalable, throughput-optimized NTT architecture supporting a wide range of ring dimensions used in FHE, from $2^{10}$ to $2^{16}$. Our design applies optimizations at multiple levels, from modular arithmetic to the NTT algorithm itself, including multi-dimensional decomposition without requiring additional multiplication blocks. The decomposition dimensionality is configurable at design time, supporting 2-D, 3-D, and 4-D decompositions, each advantageous in specific scenarios. Furthermore, TP-NTT provides design-time-configurable throughput. Combined with its scalable architecture, this enables significant advantages for batch NTT operations compared to other works in the literature. At $n=2^{16}$, it outperforms the best-performing prior design by $1.33\times$ in average latency while achieving $1.24\times$ better area–time-product (ATP). To demonstrate its efficiency, we present a case study on FHE relinearization, focusing on the BFV scheme. We propose a relinearization accelerator that leverages the fast batch NTT capability of TP-NTT, achieving $67.34\times$ speedup over state-of-the-art software implementations and highlighting TP-NTT’s effectiveness in real-world FHE applications.

In this paper, we present RISQrypt, the first unified architecture in the literature that implements ML-KEM (f.k.a. CRYSTALS-Kyber) and ML-DSA (f.k.a. CRYSTALS-Dilithium), two standardized lattice-based post-quantum cryptography (PQC) algorithms, with masking. RISQrypt is a hardware–software co-design framework that integrates dedicated cryptographic accelerators to speed up polynomial arithmetic, hashing, and mask-conversion operations, the latter being one of the primary bottlenecks in masked implementations of lattice-based PQC. Our design achieves low latency while providing both theoretical and practical side-channel security through formal proofs in the $t$-probing model and practical experiments. Specifically, the masked decapsulation of ML-KEM-768 requires $\mathbf{109K}$ clock cycles, while masked signing of ML-DSA-65 requires $\mathbf{1230K}$ clock cycles on average. These results demonstrate $\mathbf{11.3\times}$ time-performance improvement over existing masked implementations. Our time performance results for unprotected functions also outperform the existing work; achieving speed-ups of $\mathbf{10.64\times}$ and $\mathbf{8.94\times}$ for ML-KEM's encapsulation and decapsulation algorithms, respectively, and $\mathbf{1.14\times}$ and $\mathbf{2.23\times}$ for ML-DSA’s signature generation and verification algorithms, respectively, when compared to existing designs with similar resource usage. In addition, prior designs are more limited in scope, generally supporting only a single scheme and lacking either the side-channel protection or the unified, crypto-agile framework that enables support for both ML-KEM and ML-DSA as in our architecture. Leveraging the HW/SW co-design approach, the proposed architecture can be reprogrammed through firmware to support other (and future) PQC standards and algorithms sharing similar computational building blocks. As proof of concept, we demonstrate this capability by implementing FN-DSA (f.k.a. Falcon) and SLH-DSA (f.k.a. SPHINCS+).

Confidential sources are vital for investigative journalism and thus for holding those in power to account. However, sources often face great risks to their privacy and safety. SecureDrop is a system that enables sources to anonymously contact journalists, including at major news organisations around the world. Despite its widespread use, the current design requires physical servers hosted on premises. While cloud-based deployment would alleviate this burdensome requirement and improve SecureDrop's usability and accessibility, it would also introduce new threats to security that are not addressed by the current design. In particular, a lack of end-to-end encryption presents serious risks in the event that a cloud service provider is coerced into revealing information. In this work, we present and formally analyse a new protocol for SecureDrop which addresses the challenges of off-premises deployment. Our protocol composes an encryption scheme with hybrid post-quantum guarantees and an identity-hiding message-fetching mechanism to provide strong anonymity guarantees. In contrast to existing systems, we minimise incriminating evidence against whistleblowers by providing message-level deniability and by having sources remain stateless. Our formal security analysis combines the Tamarin prover for symbolic analysis and game-based proofs for computational analysis. Finally, our benchmarks demonstrate that the protocol achieves practical levels of performance in a browser context. The Freedom of the Press Foundation plans to deploy the new protocol, with integration efforts beginning in 2026.

Almost pairwise independence asks how closely a block cipher reproduces the joint output distribution of a random permutation on two distinct plaintexts. Existing analyses of AES with independent round keys combine bounds on the distribution after the first few rounds with contraction over later rounds. Diffusion makes local output differences dependent, and estimating local responses or successive transitions separately can lose useful information. We preserve these dependencies in two ways. First, Gram-moment estimates sum the squared overlaps between local responses whose inputs are linked by diffusion. Second, we estimate two consecutive transitions together. The compatible intermediate differences form affine fibers; summing over these fibers inside the composed operator retains the constraints shared by the two diffusion layers. We prove $\varepsilon_{8+2k}<2^{-92.19-41k}$ for every integer $k\ge0$, where $\varepsilon_r$ is the largest total variation distance, over distinct plaintext pairs, between the ciphertext-pair law and the corresponding random-permutation law. The round keys are independent and uniform, sampled once and reused across evaluations. Consequently, 10, 14, and 16 rounds suffice for statistical accuracy $2^{-128}$, $2^{-192}$, and $2^{-256}$. The same bound controls the complete view of an algorithm making at most two adaptive classical forward queries with an independent finite private seed. The resulting family gives 41 additional bits of pairwise accuracy for every two additional rounds, starting at eight rounds.

Building an Asynchronous Byzantine Fault Tolerant (BFT) protocol requires establishing payload availability with total order despite Byzantine faults and arbitrarily delayed messages. Although many BFT systems separate payload dissemination from agreement, they often couple their composition to protocol-specific selection or scheduling mechanisms. We present the Distributed Producer-Consumer Model (DPCM), an event-driven abstraction that separates payload-specific certified availability from payload-oblivious binary finalization. We prove that DPCM compiles any producer–consumer pair satisfying interfaces specified herein into an asynchronous BFT object log. DPCM batch-finalizes certified heights, deterministically refining failed batches until each height yields a normal or evidence-backed dummy entry. We instantiate DPCM as Octopus, which combines parallel consistent broadcast producers with batched asynchronous binary agreement (ABA). To achieve performance advantages, Octopus lets producers certify blocks without waiting for consumer decisions and keeps payload recovery off the agreement path. One ABA optimistically finalizes multiple consecutive producer columns, while failures trigger parallel row-wise refinement with logarithmic bisection depth. Across an eight-region WAN with $n\in\{8,16,32\}$ and 2200-transaction blocks, Octopus remains within 6.5% of Dumbo-NG's (ACM CCS'22) fault-free throughput. With the maximum tested number of silent faulty parties, it outperforms Dumbo-NG by 25.9% and 18.7% at $n=8$ and $n=16$, respectively, and remains within 1% at $n=32$. At $n=16$ and $n=32$, Dumbo-NG's latency is 1.9--2.5$\times$ that of Octopus. Across all evaluated settings, Octopus achieves 2.9--16.8$\times$ the throughput of Alea-BFT (USENIX NSDI'24), whose latency is 2.4--15.2$\times$ that of Octopus.

As AI increasingly automates cryptanalytic programming, transparent and reproducible frameworks are essential for making generated results human-verifiable. We present CLAASP-MP, a monomial-prediction tool integrated into CLAASP and based on the three-subset division property without unknown subset (3SDP-woU). CLAASP-MP generates a Mixed Integer Linear Programming (MILP) model directly from the CLAASP component graph, supporting S-boxes, linear layers, Boolean operations, modular addition and multiplication, and linear and nonlinear feedback shift registers. For selected output bits, CLAASP-MP computes the algebraic normal form (ANF) for small numbers of rounds, derives superpolies for a chosen cube, and bounds the algebraic degree with respect to plaintext, key, or IV variables. It detects absent monomials through vanishing ANF coefficients, zero superpolies, or degree bounds, thereby identifying balanced outputs and integral distinguishers. We evaluate CLAASP-MP on block ciphers, permutations, and stream-cipher update functions. For block ciphers, we reproduce known distinguishers, find new cubes, and report the first integral distinguishers for SAECHAM. For Splight, we reach rounds 10 and 11, despite a previous two-subset division-property search reporting no 10-round distinguisher. On MSX-128, a $96$-dimensional cube leaves $64$ of $128$ output bits balanced after 7 rounds. For permutations, we extend the best-known division-property distinguishers for ChaCha and Salsa from 6 and 5 rounds, respectively, to 6.75 rounds; give the first such distinguishers for Forr\'o; and reduce the data complexity for Chaskey-Pi from $2^{64}$ to $2^{23}$ at round 3 and from $2^{127}$ to $2^{122}$ at round 4. For stream ciphers, we find new 36-dimensional cubes for Bivium, extend the tight degree bounds for Trivium to later initialization clocks, and reproduce published superpolies. These results establish CLAASP-MP as a unified, practical, and human-verifiable framework for monomial prediction across symmetric primitives.

Hiding countermeasures, alongside masking, play an important role in modern hardware security for protecting against side-channel attacks. Additive noise generators are one such hiding countermeasure. They increase the noise, thereby lowering the signal-to-noise ratio and, simultaneously, amplifying the effectiveness of masking countermeasures. Among the different design options for additive noise generators, ring-oscillator-based designs feature regularly in scientific publications. These existing works not only differ in their designs, but also in their evaluation methods; therefore, they do not permit fair comparisons or enable systematic evaluations. Thus, it is currently not possible to design ring-oscillators for noise generation in an informed and tailored way. In this paper, we address this lack of systematic comparisons of existing designs, and discuss the possibility of filtering out the generated noise and further limitations of ring-oscillator-based noise generators. We find that many existing designs do not consider the need to amplify the output signal or the risk of filtering. As a consequence, the existing designs do not sufficiently lower the signal-to-noise ratio in our experiments. However, using these results, we provide a guideline for tailoring and configuring ring-oscillators so that they efficiently add noise in the desired frequency spectrum. This includes deciding on the inverter chain length, the amplification of the output, and the randomization of the output frequency. Finally, we apply this methodology to build a tailored ring-oscillator-based noise generator for an exemplary AES implementation and find that it significantly outperforms existing ring-oscillator-based designs.

ANNULAR is a shielded pool built on isogeny-based primitives. Notes are committed in a Merkle tree and spent by nullifier with hidden amounts, following the structure of Zcash's Sapling, but every primitive is post-quantum: spends are authorised by the prime-degree PRISM signature of Basso et al., note ciphertexts are keyed by the MIKE non-interactive key exchange, and each transaction carries a STARK proved natively over the isogeny field. The transaction proofs of a block are then folded into a single recursive proof. A ledger need record and verify only this one proof, 426 KB in 15 ms, whatever the batch holds, and check each transaction's two signatures alongside it. A transaction's body is the size of Sapling's at the same memo length (2,685 bytes against 2,756 with a 512-byte memo); its share of the batch proof adds under 500 bytes. A move to post-quantum primitives is generally expected to raise a pool's operating cost. We argue that the post-quantum change and the scaling change are complementary: with a STARK as the proof system, proofs fold, and with isogeny keys, the per-transaction data remains small. The cost moves to the sender, whose proof takes 1.4 s on sixteen cores, and to one aggregator per batch, which we measure: 1,248 transactions in 99 s on one GPU. Each proof in the tree carries 100 bits of round-by-round soundness and the batch about 90 under a union bound; under Fiat–Shamir that is the work an adversary needs. The constraints of the leaf circuit are proven in Lean 4 to encode the spend statement, while the soundness of the STARK itself rests on a paper argument. The scheme's claims rest on the signature's existential unforgeability; its strong unforgeability, argued by the construction's authors and not yet proved, is not relied on.

In this work, we look at collision-based attacks both for elliptic curve and isogeny problems. Our main focus is on attacks in the multi-user setting, i.e., where one tries to recover all secret keys of a large set of $L$ public keys simultaneously, in a faster way than the total time required to attack each key individually. We consider three different problems: (1) the discrete logarithm problem on elliptic curves, (2) the isogeny pathfinding problem on supersingular $\mathbb{F}_{p^2}$-curves, (3) the isogeny pathfinding problem on supersingular $\mathbb{F}_p$-curves. We first survey the existing van Oorschot and Wiener style attacks on these three problems. Then we propose versions of the pseudorandom walks that are better suited for isogeny pathfinding problems without additional restrictions. We then apply these new walks to the multi-user setting and analyse which properties we can achieve compared to the discrete logarithm case where we show that we can extract all $L$ public keys with $L$ useful collisions and without an infiltrator (a user for which we know the secret key). Specifically, for (2) we can extract $L$ public keys with approximately $L + \log(L)$ useful collisions and no infiltrator needed. Our analysis shows however that heuristic and infiltrator-aided strategies are more efficient while enjoying practically similar gains. For (3) we can extract approximately $0.75L$ public keys with $L$ useful collisions, but with an infiltrator.

Threshold cryptographic primitives have not been widely adopted in real-world distributed systems (i.e., beyond the closed committee model) presumably due to state-synchronization overhead and complex certification processes for the shareholders. These are both aspects of their overreliance on infrastructure, an assumption that is usually glossed over in their design. In this work, we propose OSST, a real-time threshold identification protocol that achieves non-interactivity and non-reliance on public shares by means of direct proof interpolation. Given a Shamir $(n, t)$-shared secret $x$, the proposed scheme allows any $t^* \ge t$ (but no less) shareholders to prove over designated communication channels that their key shares interpolate to $x$ without revealing any information beyond that. Provers do not engage in distributed computations, sending their packets to the verifier asynchronously; conversely, verifiers need only know the combined public key $y \equiv g ^ x$, without need to pre-validate and register the individual member identities. The protocol is intended for use in permissionless or unmanaged meshes that lack both overlay networks and trust infrastructure or governance, a use case space that has been tacitly neglected as ''niche'' by the current mainstream. No publicly verifiable setup is required beyond distributing $x$ according to Shamir's secret sharing (or equivalent distributed key generation scheme) and advertising its public counterpart; in particular, the protocol is intended to be secure against impersonation without relying on the auditability of any advertised public shares. We provide evidence that this has good chances to hold true by giving a reasonably restricted security proof in the random oracle model under the one-more discrete-logarithm (OMDL) hardness assumption.

Rotational-XOR (RX) cryptanalysis extends rotational cryptanalysis by combining rotational relations with XOR translations, enabling the analysis of symmetric-key primitives even in the presence of symmetry-breaking constants. Existing analyses of RX characteristics, however, typically rely on independence assumptions when estimating characteristic probabilities, which may lead to inaccurate probability evaluations and even incompatible characteristics. In this paper, we introduce the first application of the geometric approach to RX cryptanalysis. Inspired by the quasidifferential framework of Beyne and Rijmen, we define rotational-quasidifferential trails and derive exact expressions for fixed-key RX characteristic probabilities without relying on round-independence assumptions. We also derive explicit rotational-quasidifferential transition matrices for bitwise AND and modular addition. By incorporating the key schedule into the state space, we further obtain an exact expression for the Expected Rotational-XOR Probability (ERXP), the RX analogue of the Expected Differential Probability (EDP). We apply the framework to the ARX cipher SPECK, the ARX permutation Alzette, and the AND-RX ciphers SIMON and SIMECK. For SPECK, we repair an incompatible 12-round characteristic and show that the longest published RX characteristics for SPECK64/128, SPECK96/144, and SPECK128/256 are incompatible. For Alzette, we show that signed nonzero-mask contributions explain the discrepancy between independent-ADD estimates and experimentally observed full-data-path probabilities. For SIMECK, we experimentally verify a fixed-key probability distribution, explain incompatible characteristics, and correct the weak-key class estimates of rotational-XOR differential rectangle attacks. These results extend the geometric approach to both ARX and AND-RX designs and demonstrate its usefulness for exact characteristic-level analysis.

Blockchain-aided decentralized storage networks (DSNs) use public audits to verify outsourced storage and smart contracts to govern payments and collateral. Published audit evidence, however, remains available to servers and may let them reduce local storage while continuing to pass audits. Retrieval must also remain fair across adaptively selected sessions. We formalize DSN protocols across delegation, preservation, and retrieval, accounting for evolving server state and externally available proofs. To support adaptive replication soundness, we reformulate rational replication for proofs of replication (PoRep) as an extractor-based notion. We then give a generic construction combining PoRep, verifiable delay functions, and simulation-extractable zkSNARKs, with encrypted delivery and conditional authorization for retrieval. Our analysis identifies roles for succinctness and simulation-extractability beyond privacy and efficiency. Under the knowledge of strong compression assumption and the stated primitive and timing assumptions, we establish adaptive replication soundness subject to bounds on extraction resources and the cumulative public transcript. We also establish contract unforgeability and retrieval fairness. Controlled experiments illustrate storage offloading through public audit evidence, while a separate Merkle-PLONK prototype measures proving and verification costs through Cardano's Plutus interface.

Class group actions on supersingular elliptic curves over $\mathbb F_p$ as in CSIDH are typically evaluated as long chains of isogenies of small prime degree. Radical isogeny formulae compute such chains using a single $N$th root per step, without sampling torsion points. Compact formulae of linear size had been conjectured for all odd $N$. We prove a corrected version of these formulae for every $N\ge4$, odd and even, over every field of characteristic coprime to $2N$. In our formulation, every building block is a twisted sum of a discrete Kronecker function over $\mathbb Z/N\mathbb Z$, and the formulae follow from a distribution relation for the Kronecker theta function. For even $N$, the $N$th root is only determined up to sign over $\mathbb F_p$, and the sign decides whether the walk stays on the surface of the $2$-isogeny volcano. We show that the radical times a $2$-torsion coordinate of the next curve is a square, which yields the horizontal choice for all even $N$; previously this was only known for $N\le14$. Algorithmically, one radical step costs about $12.5N$ multiplications and one exponentiation, without inversions. For horizontal $2$-isogeny walks, radical $2^m$-isogenies with $m\in\{5,6,7\}$ are optimal for primes of $512$ to $4096$ bits. Finally, we show how to evaluate radical isogenies on points. As a consequence, a class group action can be computed from two given points, one on the curve and one on its quadratic twist, without ever sampling torsion points.

Registered Functional Encryption (Reg-FE) eliminates the key escrow issue in traditional functional encryption by allowing users to generate their own public/secret keys without the help of a central authority. The public key is then registered to the system along with a function, and all the registered public keys will be aggregated to a compact master public key by a transparent key curator. Messages are encrypted under the master public key, and users can learn functions of encrypted data from the ciphertext using their own secret keys. Prior constructions of Reg-FE either become insecure when more than one malicious users collude or require the heavy machinery of indistinguishability obfuscation. In this work, we construct the first collusion-resistant Reg-FE without obfuscations. The schemes are secure if the number of colluded users is bounded, and the collusion bound can be either a global parameter or specified by the encryption algorithm dynamically. In both settings, we provide generic constructions of Reg-FE from registered attribute-based encryption and instantiate them from either the standard $k$-Lin assumption or the succinct LWE assumption.

Laconic Oblivious Transfer (OT) enables a receiver to compress a large database into a short digest, allowing a sender to generate a succinct ciphertext that reveals only a single indexed message. While prior works achieve efficient constructions in the semi-honest model, known solutions for malicious security rely on inherently heavy non-black-box techniques, such as garbled circuits or succinct arguments, resulting in impractical schemes. In this work, we present the first construction of maliciously secure laconic OT that makes fully black-box use of its underlying primitives. Our construction is based on a simple and widely used paradigm combining vector commitments with witness encryption, previously known to yield efficient semi-honest protocols. We show that this approach can in fact achieve malicious security by introducing two minimal yet powerful enhancements: equivocal vector commitments and maliciously secure witness encryption. We prove that these properties suffice to obtain laconic OT with security against malicious senders in the universal composability model and against malicious receivers in the context model. We instantiate our framework from standard assumptions, including LWE and bilinear Diffie-Hellman variants, obtaining schemes in the standard model. Notably, our constructions avoid heavy non-black-box tools mentioned before, and therefore achieve efficiency comparable to the state-of-the-art black-box constructions with merely semi-honest security. In particular, in certain settings, we obtain malicious security at essentially no additional asymptotic cost. Our results resolve a central question on the feasibility of practical, maliciously secure laconic OT, and provide a unifying pathway for efficiently achieving malicious security in laconic cryptography.