Lattice-based cryptography uses SHAKE to expand seeds into byte strings for matrix generation and sampling. SIMD Keccak implementations process multiple hash streams in parallel. Differences in stream lengths and input dependencies can prevent full SIMD utilization. We present a cost-aware method for scheduling Keccak permutations across hash streams during a single execution of a cryptographic algorithm. The method groups ready streams and divides long streams into segments for regrouping. A model of permutation calls, state movement, initialization, and input preparation guides the selection of stream groups, segment lengths, and state placements. We evaluate ML-KEM and HAETAE on an Apple M5, a Cortex-A72, and an Intel Core i5-11500, using Keccak kernels that process two, four, or eight streams per call. ML-KEM achieves speedups of up to $1.31\times$ for encapsulation and $1.44\times$ for decapsulation, while HAETAE achieves up to $1.28\times$ for signing and $1.26\times$ for verification.

The approximate Closest Vector Problem $\mathsf{CVP}$ with large approximation factors, such as a polynomial approximation, arises in the concrete cryptanalysis of lattice-based signatures, yet it is commonly estimated indirectly through $\mathsf{SVP}$ after Kannan's embedding (Wang et al, PQC2025). Such reductions may return short vectors that do not encode valid $\mathsf{CVP}$ solutions and are less suited to reusable preprocessing, batched targets, and list output. We give, to our knowledge, the first practical instantiation of the Nearest-Colattice framework (Espitau et al, ANTS2020). Our $\texttt{RandNColattice}$ algorithm realizes quotient-lattice $\mathsf{CVP}$ calls on explicitly projected basis blocks using randomized slicer oracles (Ducas et al, PKC2020), and therefore naturally propagates multiple candidate branches for batches of targets. We further extend the randomized slicer with dimensions for free for both $\mathsf{BDD}$ and approximate $\mathsf{CVP}$/$\mathsf{ListCVP}$, and introduce $\texttt{HybridRandNColattice}$, which replaces the oracle on the final block with Klein's sampler to generate diverse randomized residual targets efficiently. The final candidate-filtering interface is norm-generic, while our concrete analysis focuses on the Euclidean and infinity norms. We derive blockwise distance and runtime models and construct an estimator over 4 strategy models: $\mathsf{D4f}\text{-}{CVP}$, $\mathsf{Prob}\text{-}\mathsf{BDD}$, $\mathsf{CVP}_{\gamma_2}$, and $\mathsf{Flexd4f}\text{-}\mathsf{CVP}_{\gamma_2}$ with $1\leq \gamma_2\leq \sqrt{4/3}$. The estimator instantiates costs under a theoretical model and the AGPS20 and MATZOV22 gate-count models, and we apply it to non-amortized forgery estimates for Dilithium, HuFu, and one-more-ISIS. Finally, we implement $\texttt{HybridRandNColattice}$ by extending the G6K-CPU based randomized slicer (Alexander et al, AsiaCrypt 2025). Our experiments support the Euclidean distancemodel, while showing that the spherical approximation used for infinity-norm filtering is optimistic because the actual blockwise error distribution is anisotropic. These results provide a concrete foundation for direct approximate-$\mathsf{CVP}$ cryptanalysis and identify tighter infinity-norm modeling as an important open problem.

Identity-based encryption (IBE) is required to support a superpolynomial-size identity space using only polynomial-size public parameters. This compression requirement underlies known barriers to IBE in the generic (pairing-free) group model. Cryptographic group actions, motivated prominently by isogeny-based cryptography, support many advanced primitives beyond public-key encryption. However, no generic construction of IBE from the basic group-action interface is known. Existing generic-group barriers do not resolve this question as they do not translate to generic group-action models. We establish the first tight barriers to IBE in two variants of the generic group-action model. In the type-safe generic group-action model, we prove that an IBE scheme with negligible correctness error and $n$ non-origin action-set element-handles in its public parameters can support at most $n$ identities, even for a weak notion of fully selective security. We show that this bound holds irrespective of the number of action-set element-handles in identity secret keys. We further establish that this bound is tight by demonstrating a matching construction. We then extend this tight characterization to a natural class of IBE schemes in the random-representation generic group-action model (including against representation-sensitive adversaries) under conditions ensuring that identity keys retain no hidden action-set encodings and discarded private encodings leave no residual information. We give a natural syntactic condition for the latter property. For actions additionally equipped with an inversion-like twist, we obtain a more general upper bound (including the same tight bound for odd-order actions). Our results provide the first formal evidence that IBE is likely to require additional algebraic structure or non-black-box techniques beyond the generic group-action interface. More broadly, we provide a new framework for proving lower bounds in generic group-action models.

Enhanced Privacy Identification (EPID) is one of the anonymous authentication mechanisms that found their way into the industry, being deployed in billions of chips and standardized at ISO. The linchpin of EPID lies in its decentralized revocation procedure that allows to revoke a signer by simply placing one of its signatures on a signature revocation list SRL. Each new signature must then include a proof that it has been generated with a key different from those used to produce the signatures on the SRL. This proof of non-revocation in current post-quantum schemes either relies on general-purpose NIZKs or on regular zero-knowledge proofs (ZKP) but with a witness dimension linear in the size of the SRL, which leads to large size and/or computational complexity. In this paper, we rethink the standard approach of non-revocation so as to avoid its heavy reliance on ZKP. Our construction indeed combines features from different tools (such as Falcon signatures) that are unusual in this context to pull most elements out of the ZKP, leading to significant performance improvements. Providing all these elements unconcealed creates many security challenges for our construction but we yet manage to address all of them and prove security under well-understood lattice assumptions, and in the strong model of Sanders-Traoré (CT-RSA'21) allowing malicious SRLs.

We present an end-to-end resource estimation of Shor's algorithm on superconducting cat qubits, from its mathematical description to the allocation and scheduling of physical qubits on a chip layout. After proposing a comprehensive view of the modern versions of Shor's algorithm for RSA, ECDLP and FFDLP, we make explicit their logical circuits and the trade-offs they enable. We compile the dominant subroutines down to physical-qubit operations on two architectures: one based on repetition cat codes and one based on LDPC cat codes. We design a parity-Cnot gate for cat qubits, extend a multi-target Cnot gate to the LDPC-cat architecture, and adapt an active injection procedure to cat-qubit architectures. Building on these primitives, we adapt to cat-qubit architectures the adder from Gidney’s 2025 resource estimate for factoring RSA-2048. We combine our adder compilation and a coarser resource estimate for the phaseup with the factory designs and lookup compilation from the FeMoco resource estimation of Kroell et al. Together, these compilations lead to chip layouts and schedules for factoring RSA-2048. Assuming a 1$\mu$s error-correction cycle time, a 10$\mu$s reaction time, circuit-level phase-flip noise with probability $p_Z = 5 \times 10^{-4}$ and no bit-flips, factoring RSA-2048, the configuration we compile in full, requires about 23 000 cat qubits and 3.14 days. Reusing the operations compiled for RSA-2048, solving ECDLP on secp256k1 requires at most 30 000 cat qubits and 1 hour, and FFDLP-512, which we propose as an intermediate benchmark, about 6\,700 cat qubits and 21~minutes. Trading space for time, RSA-2048 runs in 1.25 hours on about 611 000 cat qubits. The requirement on no bit-flips (which corresponds to a bit-flip time of about 100 years) can be relaxed to a bit-flip time of about one hour by using an additional concatenation layer into a distance-3 bit-flip error-correcting code. In that case, we estimate that the cost of RSA-2048 increases to about 45 000 cat qubits.

The Lattice Isomorphism Problem (LIP) is a computational problem that has recently been introduced into cryptography and is believed to be hard. Its search version, Search Lattice Isomorphism Problem (SLIP), is considered even harder than the Shortest Vector Problem (SVP), yet its complexity is still not well understood. Haviv and Regev (SODA 2014) showed that the decisional version (DLIP) lies in a statistical zero-knowledge class and is therefore unlikely to be NP-hard. This result does not apply to the search version, which motivates the question of whether NP can reduce to SLIP. Our main result answers this question negatively. We show that every language reducible to SLIP lies in AM and coAM, by analyzing the direct-sum structure of irreducible lattices. Consequently, NP cannot reduce to SLIP unless the polynomial hierarchy collapses, and there is no reduction from SVP to SLIP unless the polynomial hierarchy collapses. We also study several problems closely related to LIP and establish reductions between its search, counting, and decisional variants. These connections mirror known relationships for graph isomorphism. Finally, we propose a new algorithm that uses a KZ basis to compute an orthogonal decomposition of a lattice.

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings to any efficient adversary. We study public-key multi-bit PRCs over the stochastic memoryless binary substitution-insertion-deletion channel and its $q$-ary generalization. Here $P_i,P_d$ are the insertion and deletion probabilities, and $P_s$ is the substitution probability conditional on transmission. We first show that the majority-based construction of Christ and Gunn yields a binary PRC with vanishing rate that recovers the transmitted message with overwhelming probability whenever $P_i+P_d<1$ and $P_s<1/2$. We then use this binary PRC to protect control information in a high-rate, uniquely decodable PRC over an unbounded family of constant-size alphabets. For fixed channel parameters satisfying $P_i+P_d<1$ and $P_s<1$, its decoder recovers the transmitted message with overwhelming probability. The alphabet size may depend on the channel parameters and desired rate gap, but not on the security parameter. As the gap tends to zero and the alphabet grows through the supported sizes, the rate approaches the capacity upper bound obtained by revealing insertion and deletion locations to the receiver. The constructions use the assumptions underlying the Christ--Gunn public-key PRC and secure pseudorandom generators.

We investigate an algebraic approach to the Syndrome Decoding Problem, based on a reformulation of the Hamming weight constraint and its integration with the Information Set Decoding paradigm. We begin with a systematic analysis of the Hamming variety, deriving its defining equations in terms of elementary symmetric functions. Since these equations may have high degree, we exploit convolution identities for elementary symmetric functions, together with factorizations based on Lucas' identity, to derive an equivalent formulation with auxiliary variables and equations of bounded degree. Building on this modeling, we generalize the ISD paradigm through an ISD-like decoding strategy, implemented by the GBDecode algorithm, in which only a subset of an information set is fixed. This approach reduces the size of the combinatorial search space at the cost of solving the associated multivariate nonlinear systems. To handle this algebraic component, we employ the MultiSolve algorithm, which replaces a single Grobner basis computation with a collection of computations on simpler systems, obtained by exhaustively assigning a varying number of indeterminates over the finite field. This provides a tunable balance between combinatorial search and algebraic solving. We evaluate the resulting approach experimentally on instances of the Syndrome Decoding Problem for random binary linear codes, using parameters corresponding to the NIST Security Category 1 parameter set of the Classic McEliece cryptosystem. The experiments assess the feasibility of this combinatorial-algebraic approach and provide insights into the practical behavior of Grobner basis techniques within an ISD-like decoding framework.

The EasyCrypt proof assistant has been used to successfully formalize security proofs for a wide variety of cryptographic primitives. However, attempts at formalizing objects with interactivity, such as protocols, have fared much worse. In this paper, we investigate (some of) the reasons for this difficulty. To identify which proof features contribute most to the complexity of formalization in a tool based on probabilistic relational Hoare logic (pRHL) such as EasyCrypt, we formalize a simple interactive key agreement protocol in three different ways. From these proof efforts, we then extract our insights. In particular, we argue that difficulties in formalizing the security of interactive protocols in the computational model arise from the fact that such proofs rely on both state and temporal invariants—the former to support cryptographic reasoning, and the latter to support reasoning about the protocol’s structure. At the same time, EasyCrypt and similar pRHL-based approaches offer no native notion of events, traces or timestamps, forcing a user to find their own encoding of temporal properties. We discuss two possible encodings, state-first and trace-first, and their impact on the proof effort. More generally, we believe that this observation can help build new reasoning tools that can bridge the gap that currently exists between primitive-focused tools and protocol-focused tools.

Rerandomizable garbling schemes (RGS) are a fundamental primitive enabling advanced cryptographic constructions such as multi-hop homomorphic encryption (Gentry, Halevi, Vaikuntanathan, CRYPTO 2010), iO-combiners (Ananth, Jain, Naor, Sahai, Yogev, CRYPTO 2016), and YOSO-style MPC (Acharya, Hazay, Kolesnikov, Prabhakaran, TCC 2022 and CRYPTO 2024). All known RGS instantiations rely on discrete-logarithm-type assumptions, concretely via the BHHO scheme (Boneh, Halevi, Hamburg, Ostrovsky, CRYPTO 2008) and its recent pairing-based variant (Heitjohann, von der Heyden, Jager, CRYPTO 2025). This reliance stems from the use of key-and-message homomorphic encryption (KMHE) that supports rerandomization and strong "key-privacy under leakage", which hides the applied homomorphic transformations and is currently only achievable using BHHO-style bitwise encryption in combination with permutation-based homomorphisms. Our first main contribution is a new garbling technique that shifts the burden of hiding homomorphic transformations from the encryption scheme to the garbling itself. This allows us to construct RGS from KMHE schemes with substantially weaker properties, avoiding the need for bitwise encryption and permutation-based homomorphisms, and enabling the construction of RGS from KMHE with other homomorphisms, such as additively-homomorphic ones. As a second contribution, we give a concrete lattice-based instantiation of the required KMHE primitive, based on LWE. This construction is a variant of the GSW FHE scheme (Gentry, Sahai, Waters, CRYPTO 2013), which uses new techniques for rerandomization and is tailored to the requirements of our new garbling scheme by supporting a "homomorphic"/"lossy" mode. This yields the first RGS construction that does not rely on discrete-logarithm assumptions and may provide post-quantum security.

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

We study quantum collision finding for functions of prescribed exact type. For fixed constants $k\ge r\ge2$ and $N=kn$, consider functions $f:[N]\to\mathbb Z_q$ of type $(k^n)$, with exactly $n$ distinct output values and $k$ preimages for each value. We prove that the worst-case bounded-error quantum query complexity of finding $r$-collisions in $\ell$ distinct equality classes is \[ \Theta_{k,r}\!\left( \ell^{\,2^{r-1}/(2^r-1)} N^{(2^{r-1}-1)/(2^r-1)} \right) \] for $1\le\ell\le N^{2^{-r}}$. The result is uniform over all feasible alphabet sizes $q\ge n$. Our proof uses the compressed permutation oracle (CPO). We establish a recurrence for intermediate collision counts and control its accumulated error to obtain database tails exponentially small in $\ell$. The improved CPO soundness estimate then converts these database bounds into function-query lower bounds. Moreover, we extend the analysis to arbitrary exact types with bounded class sizes, without requiring any particular class size to occur linearly often. The resulting lower bounds are tight when forward permutation access is additionally available, although they need not be tight for the original function-query problem. Finally, a sampling reduction relates our collision bounds to sparse $k$-distinctness instances. A separate analysis using Belovs's transfer framework recovers the same lower-bound exponent, establishing a concrete connection between the two approaches.

Fully homomorphic encryption (FHE) enables computation over encrypted data subject to the prescribed security and precision requirements (allowable deviations from ideal results). Among all FHE schemes, CKKS is a representative scheme for approximate arithmetic, allowing the same operation on multiple values packed into a single RLWE ciphertext. Reducing ciphertext modulus \(Q\) for given output precision requirements under RLWE security constraints is a central challenge in homomorphic computation. However, despite advances in plaintext and ciphertext representations, algorithmic optimizations, and modulus management, the budget in most existing approaches remains dependent on the highest required precision and cannot reduce the baseline modulus cost to overcome encryption noise. In this work, we make average rather than maximum precision requirements govern the modulus budget and achieve savings in the baseline cost. Under decryption correctness constraints, we make these possible by allocating arbitrary output precision among independent values and quantify the modulus savings arising from differences in their precision requirements. As a bonus, our construction preserves the standard CKKS ciphertext format, which helps maintain compatibility with existing optimizations. And the construction inherits the IND-CPA security of CKKS without additional cryptographic assumptions. In a repeated squaring experiment, we use 67% fewer initial modulus bits and one quarter of the ring dimension of standard CKKS, while meeting the same precision and security requirements.

To enhance the security of stealth addresses and protect user privacy, Liu et al. (EuroS&P 2019) proposed a Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Keys (PDPKS). In this scheme, the payee generates a master public/secret key pair, and the payer derives a public key from the payee's master public key and binds the cryptocurrency asset to the resulting derived public key. The payee then verifies, using the master secret key, whether the derived public key has been correctly generated from the master public key. In this paper, we show that a public-key encryption (PKE) scheme secure against chosen-ciphertext attacks (CCA) can be generically constructed from PDPKS. Specifically, we utilize unlinkability, which hides the master public key from which a derived public key originates, to conceal plaintext information from ciphertexts. We also simulate the decryption oracle by leveraging the derived public key checking algorithm. In addition, to guarantee the correctness of the proposed PKE scheme, we rely on the consistency of PDPKS introduced by Emura (IACR CiC 2025). Given the motivation behind PDPKS, namely the construction of stealth addresses in a provably secure manner, unlinkability is regarded as the core security property of PDPKS. Our result shows that achieving this core security property essentially requires CCA-secure PKE, or cryptographic primitives of equivalent strength, and that such primitives are indispensable for constructing PDPKS.

Prior research on ensuring trust in delegated computation through lattice-based zero-knowledge proofs mostly rely on Learning-With-Errors (LWE) assumption. In this work, we propose a zero-knowledge proof of knowledge using the Ring Learning with Rounding (RLWR) assumption for an interesting and useful class of statements: linear relations on polynomials. We begin by proposing, to the best of our knowledge, the first efficient commitment scheme in literature based on the hardness of RLWR assumption. We establish two properties on RLWR that aid in the construction of our commitments: (i) closure under addition with double rounding, and (ii) closure under multiplication with a short polynomial. Building upon our RLWR commitment scheme, we consequently design a RLWR based $\Sigma_2$ protocol for proving knowledge of a single committed message under linear relations with public polynomials. As an use-case of our proposed $\Sigma_2$ protocol, we showcase a construction of a quantum-safe Searchable Symmetric Encryption (SSE) scheme by plugging a prior LWR based SSE scheme from (EuroS&P 2023) with our $\Sigma_2$ protocol. Concretely, using our $\Sigma_2$ protocol for linear relations, we prove the correctness of an encrypted search result in a zero-knowledge manner. We implement our verifiable SSE framework and show that the overhead of an extra verification round is negligible ($0.0023$ seconds) and retains the asymptotic query execution time complexity of the original SSE scheme. Our work establishes results on zero-knowledge proof systems that can be of independent interest. By shifting the setting from RLWE to RLWR, we gain significant (i) efficiency improvements in terms of communication complexity by $O(M)$ (since some prior works on RLWE require rejection sampling by a factor of $M$), as well as (ii) very short proof size ($8.4$ KB) and tighter parameters (since RLWR does not explicitly manipulate error polynomials like RLWE).

Oscillator-based true random number generators derive randomness from timing fluctuations driven by thermal and flicker noise, and flicker gains weight as technology advances and transistors shrink. Its long memory leaks information about past, which existing models either discard or truncate, overstating security. We introduce a rigorous and tractable framework for colored noise, including the white and flicker noise of oscillators. We model the oscillator phase by fractional Brownian motion and prove a quasi-renewal property: the phase uncertainty left after conditioning on the entire past depends only on the elapsed time. This yields closed-form worst-case min-entropy and sampling requirements. We also extend spectral and Allan-variance analysis to finite samples, so the noise parameters are estimated consistently from a single timing trace. The pipeline from measurement to sampling requirement is closed-form and needs no simulation. Experiments across FPGA and ASIC platforms show that flicker dominates: its variance meets white noise within about 100 cycles and accounts for more than 99% of uncertainty behind the targeted 0.99 min-entropy rate. Methods relying exclusively on thermal noise require adjustment or redesign: incorporating flicker noise enables a two-to-three orders of magnitude increase in bitrate.

An important class of plausibly post-quantum zkSNARKs uses univariate-polynomial interactive oracle proofs (IOPs) over binary extension fields $\mathbb{F}_{2^k}$, relying on the Fast Reed--Solomon (RS) Interactive Oracle Proof of Proximity (FRI) for low-degree testing. Their provers fold RS codewords in FRI and perform polynomial arithmetic, notably division and multiplication by subspace vanishing polynomials. Constraint polynomials and RS codewords are in evaluation form, but existing implementations perform this arithmetic in the monomial basis, requiring inverse additive fast Fourier transforms (FFTs) for coefficient recovery and forward FFTs for evaluation. On a general basis, Gao--Mateer and Lin--Chung--Han (LCH) additive FFTs incur $O(n(\log n)^2)$ field additions and $O(n\log n)$ field multiplications for basis conversion per $n$-point transform, and Lagrange-based FRI folding performs a field inversion per coset. We carry out this arithmetic directly in the LCH polynomial basis for arbitrary $\mathbb{F}_2$-bases. We introduce a divide-and-conquer algorithm for division by subspace vanishing polynomials directly in the LCH basis. For $n$ input coefficients, it requires $O(n)$ field operations, and on a Cantor basis it requires no field multiplications. We also show that the multiples of vanishing polynomials used for zero-knowledge blinding can be sampled directly through their LCH coefficients. Together, these remove the basis-conversion stage of the LCH additive FFT, leaving only its butterfly. We further express the FRI fold in the LCH basis: on each coset, it is an LCH inverse butterfly followed by an evaluation at the verifier challenge, and for higher-arity folds, the challenge of each stage is the value of a normalized subspace vanishing polynomial at the verifier challenge. Given constants that depend only on the domain, this yields a fold without field inversions whose folding loop performs $n(1-1/\kappa)$ field multiplications for a length-$n$ codeword and arity $\kappa$; for every input word, it outputs the same next codeword as the classical fold. We integrate these algorithms into the Aurora prover without changing the proof or the verifier. At $2^{19}$ constraints over $\mathbb{F}_{2^{256}}$, when all configurations use our FRI fold, the LCH-basis arithmetic speeds up the prover by $2.80\times$ over \texttt{libiop} on a general basis and by $1.24\times$ over a Cantor-basis prover that uses the LCH additive FFT. Against these baselines with their Lagrange-based FRI fold, the speedups are $3.63\times$ and $2.05\times$.

Radical isogeny formulae compute a cyclic chain of $N$-isogenies with one $N$th root per step and without sampling torsion points, but for general $N$ they were only known in Tate normal form. We give radical steps of every odd degree $N$ directly on short Weierstrass, Montgomery, twisted Edwards, Huff, extended Jacobi quartic, twisted Hessian, Legendre and Jacobi intersection curves, on Kummer lines, and on all curves with a rational point of order~$2$. Our approach is model-independent. The Tate normal form data is obtained from the $x$-coordinate of the kernel generator by a shifted recursion, and the codomain is recovered in the original model by locating the image of a distinguished torsion point, without square roots. In Tate normal form we lower the cost of a step from $12.5N$ to $10N$ multiplications plus one exponentiation, and short Weierstrass curves come close at $10N+35$. Montgomery and twisted Edwards curves cost $10.5N+O(1)$. However, pushing a point through their steps costs only $2N$ multiplications without precomputation, against $2N+16$ plus a shared $2N-7$ in Tate normal form, which makes them the cheapest models for chains that transport torsion points, e.g.\ for all $N\ge19$ when two points are pushed. The other models cost between $11.5N+O(\log N)$ and $15.5N+O(\log N)$ per step. All algorithms are inversion-free, with exact operation counts.

Programmable bootstrapping (PBS) in TFHE is a powerful primitive for homomorphic lookup-table (LUT) evaluation, but its practical precision is limited to $O(\sqrt{N})$ for RLWE dimension $N$. Existing solutions either enlarge the RLWE dimension or digit-decompose plaintexts before encryption, thus degrading either bootstrapping efficiency or the efficiency of downstream linear combinations. We propose Meta-PBS, a single-ciphertext high-precision PBS framework that supports plaintext modulus up to $2N$ without increasing the RLWE dimension. The key idea is to view PBS through a redundancy-perturbation perspective: Meta-PBS starts from an under-redundant LUT and iteratively increases its redundancy by combining blind rotations with LWE-to-RLWE packing. Under this view, classical TFHE PBS becomes the zero-iteration special case of Meta-PBS. Asymptotically, Meta-PBS supports PBS with a plaintext modulus $2N$ with only $O(1)$ blind rotations, leading to an $O(\sqrt{N})$ speedup compared with PBS. Another key advantage of Meta-PBS is its additive noise growth, which enables more efficient parameters and stronger support for post-bootstrap homomorphic linear combinations. In practice, Meta-PBS evaluates a 12-bit negacyclic LUT in 166 ms, achieving an $81.0\times$ speedup over EBS. For an arbitrary 8-bit LUT, a high-capacity Meta-WoP-PBS configuration is $2.04\times$ faster than Refined LHE while supporting post-bootstrap linear combinations of size up to 25,000; a lower-capacity configuration reaches a $2.61\times$ speedup.

In 2009, Galindo and Garcia (Africacrypt) proposed the use of concatenated Schnorr signatures for hierarchical public key delegation, creating an efficient identity-based signature scheme (IBS). Essentially, the scheme builds upon the Schnorr signature scheme to generate a primary signature, part of which is then used as a secret key to produce signatures on subsequent messages. The resulting IBS is proven secure against existential forgery under adaptive chosen-message attacks in the identity-based setting using variants of the Forking Lemma. In this paper, our goal is to answer the following question: would it be feasible to build upon the widely used elliptic curve digital signature algorithm (ECDSA) scheme to obtain a similarly secure and efficient IBS? We answer this affirmatively, opening interesting possibilities not only for identity-based signatures with ECDSA but also for solutions such as secure credential delegation. This latter application is of particular interest considering the wide support for ECDSA in web- and cloud-oriented authentication systems (e.g., those based on JSON Web Tokens). We prove the security of the resulting scheme by combining the Bijective Random Oracle model and the existential unforgeability game in an identity-based setup. Our results also show that, despite its non-linear nature and more convoluted verification process than Schnorr signatures, ECDSA allows one to obtain signatures of roughly the same size as those of Galindo-Garcia's scheme while maintaining efficient performance.

Side-Channel Analysis is an established field of research to assess implementation vulnerabilities of cryptographic algorithms. One typically exploited side-channel is the electromagnetic (EM) near-field, which is proportional to the data-dependent currents flowing through an Integrated Circuit (IC). The field of Quantum Sensing (QS) based on Nitrogen-Vacancy (NV) centers has shown promising approaches for different measurement configurations like scanning or spatially resolved wide-field imaging. Already today, QS has been used in the analysis of (quasi-)static magnetic fields on ICs in spatially-resolved wide-field magnetometers. In this work, we study the applicability of QS for the analysis of dynamic EM fields of ICs. For the first time, we demonstrate spectral-temporal analysis of the EM-side-channel using an NV-center-based Radio-Frequency spectrometer. Our sensor has a real-time bandwidth of 1.1 GHz with adjustable center frequency and directly probes the frequency spectrum via NV center interactions in the time domain. The approach circumvents any computations like Fourier transforms or performing frequency sweeps, enabling GHz-realtime bandwidths. We use this spectrometer to analyze the EM emanations of an RSA decryption and perform leakage detection of a software implementation of the Number Theoretic Transform - a building block of all current lattice based post-quantum algorithms - running on a Cortex M4 commercial off-the-shelf microcontroller.

In CKKS, the sign is commonly evaluated by polynomial approximation, and nonlinear functions such as comparison, ReLU, and max are computed through the sign. However, the discontinuity of the sign makes it harder to approximate with a polynomial as the required input bit precision $p$ grows. Alternatively, the sign can be computed by first decomposing the input into radix-$B$ digits. Existing methods extract the $u \approx p/\log B$ digits one at a time, taking $u$ sequential bootstrappings. Instead, we approximately round $u$ copies of the input to each digit's grid and obtain all $u$ digits in parallel, up to carries, with a single bootstrapping. The carries are then corrected in $O(\log u)$ depth. For the sign, a scan of the same form returns the sign directly, without recovering the exact digits. We show that our method distinguishes inputs separated by about $2^{-p}$ with $\Theta(p)$ modulus bits, at the cost of $\Theta(u)$ slots per input. Neither the digits nor the carries need to be computed to high precision, so our circuit, including its bootstrapping, runs at low precision. We also analyze polynomial approximation under an explicit noise and scale model, and show that, in contrast, its modulus consumption grows to $\Omega(p^2)$ bits. Benchmarks show a 2.04$\times$ speedup over [AKP25] for coefficient-encoded integer digit decomposition at ten radix-64 digits and speedups of 5.37$\times$ over [LLNK22] and 7.83$\times$ over [CKK20] for sign evaluation on real input pairs at $2^{-60}$ separation. In the tested settings, the method of [AKP25] is faster for $u \leq 4$ and that of [LLNK22] for $p \leq 36$, while our method is faster at the larger tested settings.

The HM-QCT protocol, presented by Mazzoncini et al. in 2025, uses a unique feature of quantum information to achieve quantum key distribution (QKD) with secret-key rates beyond standard constructions. The protocol has been designed in the hybrid quantum–computational time-lock (QCT) security model which imposes two independent (but related) restrictions on the attacker: (1) a computationally secure encryption scheme which a successful attacker must break within a narrow timeframe and (2) an assumption that the attacker can only store quantum information with low fidelity. We first review the protocol and its two-assumption model by presenting, in explicit form, the two natural “harvest now, decrypt later” strategies against it, one using quantum memory and one using classical memory. We show how each is excluded by exactly one of the two assumptions, so that harvesting resistance rests on their conjunction and on the presumed existence of a technological gap: the adversary's quantum memory must decohere much faster than the time it takes to break the short-term encryption. Finally, we introduce HM-PRF, a variant that replaces the short-term encryption with a pseudorandom function (PRF), evaluated locally. By eliminating the transmission of enciphered classical information, the adversary does not need to race an impending expiry event. We compare the security of our construction against the original and argue that our PRF-based assumption yields a more realistic adversary. It simply requires the existence of one-way functions rather than a predicted lasting limitation of quantum computation and memory technology.

Hair and Sahai (arXiv:2609.18275v1) have recently proposed a construction of witness encryption for NP satisfying semantic security. In this note we observe that this recent witness-encryption construction is unconditionally extractable in the generic group model. This yields a construction of extractable witness encryption without assuming subexponential soundness of SNARGs, in contrast to the recent work of Jin (ePrint 2026/2063), which requires this assumption. The result in this note, moreover, complements the concurrent work of Chen and Vaikuntanathan (ePrint 2026/2346), who show the same construction to be public-coin extractable under a knowledge-style assumption; our argument is unconditional in the GGM.

Multiparty fully homomorphic encryption (MPFHE) is a generalization of (multi-key) fully homomorphic encryption ((MK)FHE) that lives on the cusp between multiparty computation (MPC) and FHE, enabling a computation over encrypted data using multiple keys. However, contrary to MKFHE, it seeks to reduce the noise inflation based on the number of parties by allowing the parties to first compute shared data in MPC before executing the computation in FHE. However, many works use specific constructions, e.g. Chang-Li, Koirala et. al., and Ma et. al., reliant on the behaviour of a particular scheme and do not consider security against colluding servers and parties, e.g. Passelègue-Stehlé, Okada-Takagi, and Mouchet et. al. In this work we present a new framework that is secure against collusion between servers and parties and allows the use of a broad spectrum of MPC and FHE protocols, while eliminating the noise inflation based on the participating number of parties. We then show a case study of this using the FINAL scheme and show that we reduce the required key material by 60­–99.9% compared to the MKFHE FINAL scheme, FINALLY, and 65–70% compared to the Park-Rovira scheme in all cases, and by up to 71% compared to the AKÖ scheme when there are 4 or more parties. Moreover, we reduce the bootstrapping time for the AKÖ, Park-Rovira, and KMS schemes by 75–99.7%.

NIST standardised ML-KEM and ML-DSA in 2024 for post-quantum key establishment and digital signatures. Both compute forward number-theoretic transforms on secret polynomials. Their fixed multipliers, called twiddles, are a documented fault-attack target. Published attacks zero every twiddle during Kyber key generation with a single fault, or individual twiddles in one Dilithium signing variant. Nonzero replacements preserve transform invertibility, raising the question of what the difference between correct and faulted outputs reveals without transform collapse. This paper characterises the linear map from a secret polynomial to that transform difference under static twiddle replacements. Each selected twiddle takes a fixed changed field value at every use during one call; zero and nonzero replacements, including qualifying bit flips, are covered. For one replacement, rank equals the number of butterflies sharing its twiddle, halving by layer from 128 to 2 for ML-KEM and to 1 for ML-DSA. Known positions and replacement values specify the linear equations, while a known transform difference supplies their values. With one replacement per layer, these equations determine every coefficient except the constant and linear coefficients for ML-KEM, or the constant for ML-DSA. Lean 4 certifies this result for both 256-coefficient network shapes over fields of characteristic other than two, with nonzero original twiddles. Those coefficients cancel from the difference for every allowed fault set and choice of replacement values. NIST permits seed storage, motivating comparison of a known correct public key with a released faulty key from the same seed. If replacements affect only one ML-KEM secret-polynomial transform and all other computations are unchanged, the decoded key difference is a known matrix column times the transform difference. An invertible column entry reconstructs the latter. For ML-DSA, neither reconstruction nor the number of secret-polynomial candidates from the paired compressed keys is established.

Nowadays, the Matrix Code Equivalence Problem shows potential applicability in constructing efficient and secure advanced digital signatures, focusing on linkable ring signatures, threshold signatures, and blind signatures. Current constructions of these advanced signatures rely on relaxed instantiations of the Matrix Code Equivalence Problem (namely, the 2-MCE problem): given two pairs of equivalent matrix codes, find (if it exists) the secret isometry connecting the pairs. For example, the linkable ring signature construction by Chou et al. (AFRICACRYPT, 2023) builds on top of the Inverse Matrix Code Equivalence Problem: given three equivalent matrix codes, where one pair of the codes is connected by the secret isometry and another by the inverse of that isometry, find the secret isometry. This paper studies the 2-MCE problem, focusing on the family of instances where the secret isometry is (skew) symmetric. Our main contribution is a polynomial-time algorithm for these instances of the 2-MCE problem. We prove that the algorithm returns a valid solution whenever an explicit invertibility condition and two kernel-dimension conditions hold. Our results have a crucial security impact on the recent blind signature construction proposed by Kuchta, LeGrow, and Persichetti (Cryptography and Communications, 2026), whose security relies on the hardness of solving these kinds of instance of the Inverse Matrix Code Equivalence Problem: we show that this problem reduces to the instances we solve. More precisely, we show that we can recover the secret key of the blind signature construction by Kuchta, LeGrow, and Persichetti (Cryptography and Communications, 2026), with an estimated security of 128 bits, in less than a minute.

Blind signatures are a fundamental cryptographic primitive with numerous practical applications. While there exist many practical blind signatures from number-theoretic assumptions, the situation is far less satisfactory from post-quantum assumptions. In this work, we provide the first overall practical, lattice-based blind signature, supporting an unbounded number of signature queries and additionally enjoying optimal round complexity. We provide a detailed estimate of parameters achieved -- we obtain a signature of size slightly above 45KB, for a core-SVP hardness of 109 bits. The run-times of the signer, user and verifier are also very small. Our scheme relies on the Gentry, Peikert and Vaikuntanathan signature [STOC'08] and non-interactive zero-knowledge proofs for linear relations with small unknowns, which are significantly more efficient than their general purpose counterparts. Its security stems from a new and arguably natural assumption which we introduce, called the one-more-ISIS assumption. This assumption can be seen as a lattice analogue of the one-more-RSA assumption by Bellare et al. [JoC'03]. To gain confidence in our assumption, we provide a detailed analysis of diverse attack strategies.

Transport Layer Security (TLS) is the backbone of the web, allowing clients to establish secure and private channels with servers. DECO (CCS'20) and follow-up works proposed protocols that enable proving the provenance of a TLS response, i.e., that a payload came from a particular server, without needing server-side modifications. Unfortunately, these works are limited to proving Boolean statements over the payload (e.g., age $\ge$ 18) and cannot combine payloads from multiple clients. We introduce TLShare, a framework that extracts authenticated data from a TLS connection and imports it into secure multiparty computation (MPC) or fully homomorphic encryption (FHE), without requiring server-side changes or exposing client credentials. Unlike prior work, TLShare allows the payload itself, not just a predicate about it, to serve as private input to secure downstream computation. TLShare supports combining verifiable inputs across multiple clients and servers, enabling new applications such as privacy-preserving financial risk assessment and collaborative analytics. We design three protocols for TLShare: one for MPC using verifiable secret sharing, and two for FHE using interactive and non-interactive zero-knowledge proofs, each ensuring input authenticity, integrity, and end-to-end privacy. We evaluate all three protocols of TLShare over both LAN and WAN settings, comparing their trade-offs and demonstrating their practicality.

The CKKS fully homomorphic encryption scheme enables efficient encrypted computation over complex-valued data. In many real-world cases, however, the computation only involves real data, and storing them inside complex slots wastes the encoding ability. This motivated the design of conjugate-invariant CKKS (CI-CKKS) instantiated over the conjugate-invariant ring (CIR), which provides the same number of real slots while halving the RLWE dimension. Despite its better efficiency in handling real data, CI-CKKS cannot be bootstrapped directly in CIR, since the CoeffToSlot and SlotToCoeff linear transformations used in bootstrapping require storing complex values in both plaintexts and ciphertexts. Existing methods bootstrap CI-CKKS ciphertexts via conversion to standard CKKS, perform bootstrapping there, and convert back. For example, Lattigo bootstraps two CI-CKKS ciphertexts by combining them into a CKKS ciphertext with doubled ring dimension, while Bae et al. convert a single CI-CKKS ciphertext to a CKKS ciphertext in the same dimension. The former is efficient only for batched inputs and suffers from limited flexibility, while the latter consumes additional layers in packing. Another issue with CI-CKKS is that many existing functional bootstrapping methods encode intermediate values using complex roots of unity, whereas CI-CKKS provides only real-valued slots. Our first contribution is a real FFT algorithm over the conjugate-invariant ring, thereby enabling native bootstrapping in CI-CKKS. Our second contribution investigates functional bootstrapping over CI-CKKS. We adapt the real-valued AKP interpolant with radial correction and develop a single-cosine Hermite interpolation method using a single real ciphertext. We show existing complex-valued interpolation methods can be implemented using two real ciphertexts to simulate complex arithmetic. We also study the numerical behavior of real-valued interpolation and evaluate the tradeoffs between computational efficiency and precision. We implement our methods in Lattigo. Our native CI-CKKS bootstrapping achieves a $1.14$--$12.86\times$ speedup in single-ciphertext bootstrapping across different baseline methods and total linear transformation depths. Compared with state-of-the-art functional bootstrapping methods over standard CKKS, our methods achieve $1.16$--$1.68\times$ higher throughput.

Secure aggregation lets clients reveal only an aggregate of their private contributions, supporting a variety of applications, including privacy-preserving sensing, collaborative analytics, and federated learning. Building on the single-server, committee-aided model for one-shot clients used by OPA and Willow~(CRYPTO~'25), we present Ossa, a generic construction with a modular security analysis. Ossa realizes the standard secure aggregation functionality with non-selective abort against a malicious server, but leaves role selection unspecified and provides no delivery guarantee. We therefore present AlgOssa, which integrates Ossa into an Algorand-style consensus backbone in which cryptographic sortition selects fresh potential leaders and verifier committees in each round and refreshes the decryptor committee from finalized chain state at key epochs. AlgOssa further selects the server from among the potential leaders, and we establish an explicit lower bound on the probability that the selected server is honest. Consequently, the probability that a round delivers a non-empty aggregate is bounded below by a positive constant, yielding an eventual delivery guarantee across repeated rounds. This variable delivery cadence fits delay-tolerant statistical sensing and, with persistent buffering and staleness control, buffered asynchronous federated learning. Our generic core supports classical and post-quantum instantiation routes; we evaluate complete local classical rounds and demonstrate the feasibility of the post-quantum route.

We present hardware implementations of the recently proposed isochronous fixed-weight sampling algorithm by Décio Luiz Gazzoni Filho, Tomás S. R. Silva, Julio López (CiC vol. 1, 2024) and apply them to the post-quantum cryptographic algorithms NTRU-HPS, Streamlined NTRU Prime and Classic McEliece. We offer multiple implementations, optimized for different targets: A high-area high-performance implementation, a lightweight low-area implementation, as well as a side-channel secure implementation using gadget-based masking. We verify the security of our masked implementation using the PROLEAD leakage detection tool. We show that the sampling algorithm results in highly efficient and effective implementations for the NTRU-like schemes, outperforming existing hardware implementations for fixed-weight sampling.

The Algebraic Group Model (AGM) is widely used to prove the security of cryptographic schemes involving groups and pairings. It requires adversaries to explain how their output group elements are obtained from the elements they have received. The AGM with Oblivious Sampling (AGMOS), introduced by Lipmaa, Parisella, and Siim (TCC 2023), additionally allows adversaries to sample group elements without learning their discrete logarithms. This models capabilities such as hashing to a group, but complicates security proofs: security in the AGM does not always imply security in the AGMOS. We give a framework for transferring AGM security proofs to the AGMOS for a broad class of pairing-based security games. Our results separate the existing AGM argument from the additional reasoning needed to handle obliviously sampled elements. Under the Find Polynomial Representation (FPR) and Tensor Oracle Find Representation (TOFR) assumptions, this additional reasoning can be handled by general reductions. Games with further requirements, such as extractability, also require a lifting condition that ensures these requirements are preserved. We first establish a lifting theorem for non-interactive games and apply it to KZG extractability, the multivariate Adaptive Rational Strong Diffie-Hellman assumption, and the special-soundness of the Polymath SNARK. We then extend the framework to interactive games that use random oracles and other oracles that depend on the trapdoor. In the interactive setting, we apply the theorem to the existential unforgeability of BLS signatures and strong unforgeability of BBS signatures under FPR/PDL and TOFR assumptions. For BLS, we also provide an AGM security proof for Type-3 pairings, adapting the original Type-1 analysis. Our framework allows existing AGM proofs to be reused in the AGMOS. To apply the framework, it is enough to check its requirements, including oracle simulation and, where needed, the lifting condition, without repeating the full security proof.

Shuffling is a standard hiding countermeasure against (single-trace) side-channel attacks on the number-theoretic transform (NTT) of lattice-based post-quantum schemes, such as ML-DSA. The Fisher-Yates algorithm can be used to generate the underlying random permutation. Recovering this permutation itself from a single trace has so far only been studied for short sequences. We present a practical attack on a software implementation of Fisher-Yates for sequences of length 128, the number of butterfly operations in one layer of ML-DSA’s NTT. We identify the exploitable leakage of the algorithm, detect and remove the timing variations caused by rejection sampling and extract Hamming weight and identity leakage from a single trace per shuffle. We encode these hints as a constraint-programming problem with a soft objective function and enumerate the most likely permutations in order of descending likelihood. Applied to a shuffled ML-DSA-44 NTT, the recovered permutations are used to re-order the butterfly leakage, and recover the secret polynomial s1 either directly or up to a few coefficients that are enumerated directly. Protecting ML-DSA’s NTT with Fisher-Yates-based shuffling does, therefore, not, by itself, prevent side-channel-assisted key recovery.

We present Poly2MsgLeaks, a profiled chosen-ciphertext power-analysis attack that recovers the complete 512-coefficient public-key encryption (PKE) secret of SMAUG-T in its TiMER parameter set. Each polynomial-to-message (P2M) decision depends on four ternary secret coefficients and therefore on one of 81 local states. We characterize all admissible P2M predicates and show that our six-query schedule maps the 81 states to 57 binary transcripts; even with both exact polynomial weights, noiseless transcripts leave a mean residual ambiguity of 27.2 bits. Poly2MsgLeaks retains waveform scores for all 81 states, couples the 128 local blocks through the exact weights, and enumerates a calibrated cost region against the public-key relation. Under a uniform-matrix model, we prove that an incorrect key is released with probability at most $2^{-2095.6}$; for exchangeable calibration and evaluation keys, the probability that the true key lies outside the searched region is bounded without a channel model. Using six physical P2M traces recorded on an STM32F415, Poly2MsgLeaks recovers 999 of 1,000 previously unseen secrets, and a verifier-driven policy recovers all 1,000 secrets of a second cohort at a mean cost of 7.021 traces, without false acceptances. With the same decoder and limits, equalizing the scores within each transcript class reduces recovery from 998 to 112 keys. Against single-write message assembly and a two-share masked P2M, the evaluated six-execution attack recovers no complete secret.

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.

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.

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.

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.

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.