Papers updated in last 183 days (Page 5 of 2708 results)
Bootstrapping via Ring Switching without Slot Recovery: Independent Leaf Evaluation for SIMD-Packed Ciphertexts
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\%\).
Iterated-Logarithmic Additive Hardness for Bin Packing
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})$.
Non-profiled Single-Trace ML-DSA Secret Key Recovery by Horizontal Distribution Analysis
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.
From Toy to Instrument: Seven Years of Verifpal
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.
Cryptanalysis and Repair of "Decentralized Multi-authority ABE for NC$^1$ from BDH"
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.
A Memory-efficient Implementation of Wiedemann XL
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.
Subexponential Algorithms for LWE via Rejection Sampling on Superlattices
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.
Faster and Smaller Anonymous Credentials from Standardized Signatures
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.
Security Analysis on a Blockchain-based Public-Key Authenticated Searchable Encryption Scheme
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.
Fully Secure DKG Protocols for Discrete Logarithm Revisited
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)$.
Decision Attacks on Known-Covariance Ring-LWE via Public Gram Determinants
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.
Quantum Cryptomania with Classical Communication without One-Way Functions
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.
Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One
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 .
Quantum State Search with Classical Interactive Advice
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.
On Phase Decompositions with Applications to Digit Decomposition
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.
Revisiting AES Key Wrap: Forgery Bounds, Structural Observations, and Recommendations for the Revision of NIST SP 800-38F
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.
A Kelsey–Kohno Attack Variant against SHA-2 Message Digests in HSS/LMS and XMSS
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.
Energy Consumption of Post-Quantum Cryptography on Constrained and General-Purpose Architectures
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.
Nearly Optimal Hardness for CVP and NCP with Preprocessing
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.
On Extending Integral Distinguishers
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 on a Diet: Less Stack, Less Time on Low-End Microcontrollers
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.
For Thirty Pieces of Silver: Overcoming Non-IID via ZKP Sample-Level Auditing and Forcing Attackers into Traitors in Federated Learning
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 with Tensor Gates
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.
Duty-Free Bits: Projectivizing Garbling Schemes
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.
Chosen Commitments and Certified Decoding Regions in the Adaptive Threshold Schnorr Attack
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.
GKS Fully Homomorphic Encryption: Security Analysis
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.
On the Subtleties of Non-Malleability in IVC: Notions, Attacks and Constructions from Falsifiable Assumptions
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.
VeilDNS: Post-Quantum DNS Privacy from the First UDP Packet
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.
Extraction meets Distillation - cryptanalytic techniques to recover parameters from a Deep Neural Network
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.
The Exact Bit Security of Hash-Based Signatures
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.
Faster Polynomial Factorization over Finite Fields via Batched Modular Composition
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.
Provable Security of SHA-256-Based LMS Revisited in the Ideal-Cipher Model
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.
The Covering Radius of $\operatorname{RM}(2,8)$ is Between $88$ and $91$
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}$.
Faster Matrix Multiplication Leads to Faster Lattice Sieving
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.
Bounds on polynomial approximations of the discrete logarithm function
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.
Vector Commitment Design, Analysis, and Applications: A Survey
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.
BitVM3: Efficient Bitcoin Bridges via Garbled Circuits
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.
SoK: Private LLM Inference using Approximate Homomorphic Encryption
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.
BEAST-MEV: Batched Threshold Encryption with Silent Setup for MEV prevention
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.
On Reduction Probability Models in Lattice Sieving
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$).
Descent-PBS: Programmable Bootstrapping beyond the Ring Dimension
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.
AVX-512 Acceleration of SQIsign 3.0 Verification
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).
ANIMAGUS: A Provably Secure Tweakable Wide-Block Mode
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.
Affine-Padding Rabin-Oracle Factoring in $L_n\left(\frac{1}{3},\sqrt[3]{\frac{32}{9}}\right)$
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.
Tight Post-Quantum Multi-Key Security of the FX Construction
The FX construction (FX) is one of the simplest key-length extension schemes for block ciphers, introduced by Kilian and Rogaway as a generalization of DESX. By extending the key length without modifying the underlying block cipher, FX can improve security against adversaries that perform quantum computation but are restricted to classical queries to the keyed construction. Recently, Shiba and Iwata showed in their ToSC 2026 paper that FX with an $n$-bit block and a $\kappa$-bit internal key is secure up to approximately $2^{(n+\kappa-\log_2\mu)/3}$ total classical and quantum oracle queries in the quantum ideal cipher model, where $\mu\leq2^\kappa$ is the number of independently keyed instances. In this paper, we improve this bound to approximately $2^{(n+\kappa)/3}$ total oracle queries in the same model against fully adaptive adversaries, for every $\mu\geq1$ and $1\leq\kappa\leq2n$. The known attack based on the offline Simon's algorithm can target a single keyed instance and matches our bound in the exponent. Thus, the exponent of the total query complexity required to break FX is independent of the number of keyed instances in this parameter regime.
Learning with Quantization and Worst Case Lattice Problems
Motivated by the MAMBA proposals, we study the worst case hardness of
learning with quantization (LWQ) with public dither. We allow any
efficiently computable dither function and efficiently samplable seed
distribution; the matrix is uniform and independent of the secret and
the seed.
Using the randomized polar lattice quantizer of Lyu et al., we construct
explicit families with polynomial power of two moduli. For the search
family, polynomial time recovery of the uniformly chosen secret with
inverse polynomial probability yields quantum polynomial time algorithms
for the gap shortest vector problem (GapSVP) and the shortest independent
vectors problem (SIVP) on arbitrary \(n\) dimensional lattices, with
approximation factors \(O(n\log n)\) and \(O(n(\log n)^2)\), respectively.
Under stronger parameter conditions, a second family admits a decision
reduction: a polynomial time algorithm with inverse polynomial
distinguishing advantage yields quantum polynomial time algorithms for
the same lattice problems with factors \(O(n(\log n)^3)\) and
\(O(n(\log n)^4)\), respectively. Conditional on the public seed, the
comparison output is uniform in the prescribed dither coset and
independent of the matrix.
We also examine extensions to learning with errors (LWE) with interval uniform errors, as
arising in MAMBA Frost. We identify obstacles caused by deterministic
quantization boundaries and give a local perturbation bound with
explicit dependence on the number of observations. This analysis does
not establish a complete worst case reduction for these errors or
hardness at the concrete MAMBA parameters.
Tritone: Pairwise Garbled Disputes for Multi-Party Proof Verification on Bitcoin
Bitcoin Script lacks native pairing operations for efficient direct verification of Groth16 proofs. Conventional federated bridges instead authorize withdrawals through a signing quorum, whose collusion can release funds without valid evidence. We present the Tritone protocol, which lets Bitcoin enforce the outcome of verifying a Groth16 proof for an NP relation fixed in a one-time trusted setup, with the locked funds secure as long as one of a fixed set of $N$ operators is honest. Verification is optimistic and off-chain, and every transaction is standard under current relay policy, so Tritone runs on Bitcoin today without consensus changes.
Tritone generalizes the two-party BABE protocol to a fixed committee of $N$ operators, with one dispute instance per ordered pair. Cut-and-choose protects against malicious garblers, while Feldman verifiable secret sharing correlates input keys across candidates. Our new Lamport-adaptor gadget forces a challenging verifier to disclose the shares selected by the prover's committed proof element, providing the transaction-level binding left unspecified by BABE. A single set of disclosed shares then unlocks all retained candidates. We formalize the multi-party primitive, prove the protocol secure against up to $N-1$ statically corrupted operators, and specify its complete pre-signed transaction graph. We implement Tritone in Rust. On Bitcoin mainnet, when one verifier disputes a claim at every stage, the prover-candidate posts 9,607 vB and the verifier 18,160 vB of protocol transactions. In local benchmarks at 40-bit statistical security, the prover-candidate of each dispute instance retains as little as 112.83 MiB. Tritone thus replaces trust in a signing quorum with a single-honest-operator assumption wherever locked bitcoin is released to an operator against a Groth16 proof, with Bitcoin bridges as our showcase.
A Crypto-Agile Mixed-Radix NTT Accelerator for Negacyclic and Trinomial Rings
Hardware accelerators for lattice-based post-quantum cryptography (PQC) have largely converged on the radix-2 number-theoretic transform (NTT). The spectrum of standards that crypto-agility must accommodate, however, extends beyond NIST. In response to advances in cryptanalysis and to reduce the attack surface, national authorities are standardizing or recommending lattice-based algorithms with alternative algebraic structures, as well as schemes built on entirely different primitives. For instance, NTRU+, selected in the Korean PQC competition and currently undergoing standardization, is defined over a trinomial ring whose degree is divisible by three and thus requires a mixed-radix NTT comprising both radix-2 and radix-3 layers, whereas SMAUG-T employs an NTT-unfriendly modulus. Support for heterogeneous algebraic structures is therefore no longer optional but a prerequisite for crypto-agile design; existing radix-2-centric accelerators, however, fail to meet this requirement. In this paper, we present a crypto-agile mixed-radix NTT accelerator that performs transforms over both negacyclic and trinomial rings on a single datapath. Our contributions are threefold. First, we design a unified butterfly unit that integrates two parallel radix-2 butterflies, one radix-3 butterfly, and the trinomial transform on shared arithmetic resources, in which a generic 17-bit Montgomery path and an ML-DSA-specific 23-bit reduction path share the same two DSPs. Second, we propose a conflict-free memory mapping that guarantees in-place parallel access across all mixed-radix layers with a single 1-bit bank-selection function, namely address parity for radix-2 and a fixed address bit for radix-3, and requires neither mapping tables, nor coefficient reordering, nor additional BRAMs. Third, we introduce a generalized modular constant division that combines the multiple alignment of Montgomery reduction with the quotient estimation of Barrett reduction to perform the $3^{-1}$ scaling of the radix-3 inverse NTT without any DSP. Implemented on an Artix-7 FPGA, the proposed core supports all security levels of ML-KEM, ML-DSA, HAETAE, SMAUG-T, and NTRU+ using 5,279 LUTs, 4 DSPs, and 9 BRAMs at 141.5~MHz. For NTRU+, it achieves a $4.1$--$13.0\times$ improvement in area-time product (ATP) over approaches that resort to radix-2-only cores via degree lifting, and new moduli of up to 17 bits can be integrated at the cost of fewer than 20 LUTs.
AH-BKZ: A Lattice Reduction Algorithm with Asynchronous Hybrid Processing
Evaluating the hardness of the Shortest Vector Problem (SVP) is essential for selecting secure parameters in lattice-based cryptography. The fastest current SVP solvers are based on variants of G6K, but their large memory consumption remains a major bottleneck, making high-dimensional executions difficult. A common strategy for alleviating this memory bottleneck is strong basis reduction preprocessing before a sieve-based algorithm. This strategy can solve SVP instances in higher dimensions than standalone G6K under the same memory constraints, but the time required for basis reduction becomes a major issue. ProPnjBKZ, a fast basis reduction algorithm optimized by Wang et al., is currently used as a promising preprocessing method for solving high-dimensional SVP instances. In this paper, we identify that, in the ProPnjBKZ-based SVP-solving pipeline, memory resources can remain underutilized during the preprocessing phase, since ProPnjBKZ requires less memory than the subsequent high-dimensional sieving process. Based on this observation, we propose AH-BKZ, which exploits such unused computational resources by asynchronously running multiple SVP oracles, thereby accelerating basis reduction. Our experiments show that, compared with ProPnjBKZ-based preprocessing, AH-BKZ reduces the overall runtime by up to 23.1% and by 18.6% on average among successful runs for dimensions 124-148 under comparable peak memory constraints. Moreover, in a supplementary experiment conducted in a larger computational environment, AH-BKZ set new solving records for dimension 163 in the TU Darmstadt SVP Challenge and for dimension 164 in the Ideal Lattice Challenge.
SoK: Optimization Tools for the Hydra Multiplayer Channel
Blockchain technology allows parties to use a consensus protocol to add transactions and data to a decentralized ledger that are immutable. However, the amount of transactions that can be processed within a consensus protocol and thus added to the ledger within a given time frame is limited. This is a scalability issue. Layer-2 protocols are a class of approaches that process transactions off-chain, i.e. without involvement of the consensus protocol, but allow usage of the consensus protocol as a backup for security. This potentially reduces the processing of $n\in\mathbb{N}$ transactions to only $\mathcal{O}(1)$ transactions being committed to the ledger. The basic building blocks of Layer 2 protocols are Payment Channels, whereas newer protocols as Hydra (FC'21) allow for multi-party channels that are not limited to payments but can execute smart contracts, i.e. program code. There has been substantial research proposing tools and improvements to Layer 2 protocols, but most assume the original two party Payment Channel design. This makes it unclear to what degree existing techniques can be utilized with Hydra style multi-party channels. This work (1) presents a survey of such such existing two party channel protocols and tools built on top of them. We use a didactic approach with a focus on explaining their core ideas. (2) This work identifies uses cases for which novel protocols for Hydra should be developed. (3) This work analyzes open problems for Hydra, lists relevant related work and proposes which existing tools can be used to address them or serve as a starting point for further research.
Pairwise Independence of Ten-Round AES
We prove that ten rounds of \AES{} with independent and uniform random round keys are $\varepsilon_{10}$-close to pairwise independent, with
\[
\varepsilon_{10}\leq\frac{3017}{2^{141}}<2^{-129}.
\]
For every two distinct plaintexts, the joint ciphertext distribution is therefore within this statistical distance of the uniform distribution on ordered pairs of distinct ciphertexts. The same sampled key tuple is used for both encryptions. The construction retains the \AES{} round transformations, including the omission of MixColumns in the final round, with input and output whitening. Let $E_{10}$ denote this random permutation and $\Omega$ the set of nonzero differences. We establish the result through the induced one-norm bound $\norm{\Dten-U}_1\leq3017/2^{140}$ on its averaged difference-distribution matrix restricted to $\Omega$, where $U$ projects onto the uniform distribution on $\Omega$. The proof groups the ten rounds into five superbox layers and decomposes the deviation from uniformity into fourteen orthogonal subspaces according to the number of active words and residual factors. Local Gram moments and MDS code constraints control the dependencies between word differences. Bounds for the distributions produced by the first rounds preserve their common source variables, while joint estimates for the last four rounds retain the constraints across two linear layers. The final conversion to statistical distance uses the support size of each component. Exact rational evaluation of the resulting finite recurrence establishes the stated bound.
CMoSS: Composable Modular Security Specifications Framework
CMoSS facilitates modular specifications, design and analysis of cryptographic protocols. Modular design and analysis is achieved by supporting provably-secure compositions of protocols; typically, a protocol uses a blackbox subprotocol, and is proven secure when composed with any subprotocol meeting the blackbox specifications. For modularity of specifications, CMoSS extends the approach of the MoSS framework: protocol specifications are defined modularly, by a set of independent predicates (games) for each model (assumption) and requirement (goal). CMoSS makes it feasible to rigorously specify, develop and analyze realistic applied cryptographic protocols, supporting real-time concurrency and involving different attacker capabilities, delays, faults and synchronization challenges. CMoSS specifications provide a precise formalization of the informal specifications used by practitioners, facilitating provable security for practical protocols.
On the $s$-projected Goppa Codes and their Application to the Interactive Oracle Proofs of Proximity
Error-correcting codes are a useful tool in cryptography, being used both to design schemes whose hardness relies on coding theory problems (the area typically known as code-based cryptography) and as a building block in other contexts, such as proof systems and associated cryptographic argument systems. Among all codes used in cryptography, Goppa codes stand out, notably in the well-known McEliece encryption scheme, where they have withstood the test of time as one of very few classes of codes to be considered secure for over 40 years.
Therefore, a natural question is whether Goppa codes can also be used in the construction of proof systems or cryptographic argument systems.
In the context of probabilistically checkable proofs (PCPs), codes are used to transform proofs into a format that requires only a constant number of queries for verification. This efficiency is often achieved using low-degree polynomial codes, which enable the verifier to check consistency through interpolation, ensuring correctness with minimal effort. This application underscores the importance of good codes in enhancing the robustness and verifiability of proof systems.
Given their critical role, we take a closer look at how error-correcting codes are used in proof systems to find a new way of obtaining an interactive oracle proof system of proximity (IOPP) from Goppa codes.
Mímir: A Stateless Private Search Engine
Private search engines allow a user to retrieve documents from a public database that are similar to a text query.
Our cryptographic protocol Mímir employs state-of-the-art homomorphic ciphertext switching techniques to realize the first stateless semantic private search engine for highly dynamic databases.
The security of Mímir relies on (Ring) Learning with Errors.
Mímir requires no offline communication, and it trades higher but highly parallelizable server computation for low per-query communication.
When the database may change between queries, Mímir matches Tiptoe's search quality with 84$\times$ less per-query communication (0.24 MiB).
At Tiptoe's per-query communication, it reaches 64$\%$ instead of 36$\%$ of non-private search quality and is 4.2$\times$ faster (0.87s on a single multithreaded machine).
Against PACMANN, Mímir improves search quality from 76$\%$ to 81$\%$ of non-private with 72$\%$ of its per-query communication and a 9.54 MiB instead of 2.68 GiB one-time cost, but is 2.1$\times$ slower.
Mímir can achieve 59$\%$ of the non-private search quality with 8.13 MiB of per-query communication and 0.77s of total latency. This matches PACMANN's latency at a 7.6$\times$ smaller per-query communication, and outperforms Tiptoe in all three metrics.
Balsamic: One-round Threshold UOV from GPU-Accelerated FHE
Universal thresholdizers offer one-round threshold signatures, but require evaluating an entire signer under fully homomorphic encryption (FHE). We present Balsamic, a complete homomorphic Unbalanced Oil and Vinegar (UOV) signer and its application to one-round threshold UOV signature. UOV's short salted target hash shifts the encrypted workload to finite-field linear solving, which we integrate with coin derivation and hashing in a packed discrete-CKKS circuit. Our paired-pivot solver selects both pivots before first-pivot normalization, then applies their coupled update with one inversion stage per pair and cubic field work. Pivot-success certificates enable encrypted retry selection without residual evaluation. In 2-out-of-3 semihonest threshold UOV signing, each partial signing (online) takes $10.7$ seconds on NVIDIA RTX 6000 Ada and $7.77$ seconds on NVIDIA GB300, with $5.25$ MB per response. These measurements demonstrate that complete homomorphic signing can provide the computational core of one-round threshold signatures without intermediate openings or per-signature interactive preprocessing.
PPAD Hardness from SIS
Understanding the hardness of the complexity class PPAD is an important question in complexity theory given that it contains problems such as computing a Nash equilibrium. Evidence of hardness, however, has come primarily from cryptography, through a long line of work. Most recently, Chen, Freitag, Jin and Wichs (STOC 2025) based the hardness of PPAD on the polynomial hardness of the Learning with Errors (LWE) problem, together with a fine-grained average-case hardness assumption.
In this work, we base the hardness of PPAD on a different lattice problem, the Short Integer Solution (SIS) problem, which, unlike the assumptions underlying prior work, is not known to imply public-key encryption. Specifically, we show that PPAD is hard on average assuming either:
(i) polynomially hard SIS with a quasi-polynomial norm bound and a fine-grained average-case hardness assumption; or
(ii) subexponentially hard SIS alone.
Our main technical contribution is a succinct, incrementally updatable proof system for a class of exponentially large circuits with short descriptions. Building on the work of Wee (CRYPTO 2025) for succinct proof systems for circuits from SIS, we show how to make such proof systems satisfy these properties while preserving the unambiguity guarantee of the underlying scheme: it is hard to find two distinct accepted states for the same computation and time. Together, these are crucial for our PPAD hardness reductions.
A Probabilistic Extension of the Division Property: Integral Distinguishers with Key-Independent Bounds
Classical integral cryptanalysis relies on zero-sum properties that, for every key, hold with probability one. Existing arguments against such deterministic integrals, based on the division property and its algebraic variants, only exclude this extreme case: once the zero-sum probability falls below one, they say nothing about its actual value, nor about a probabilistic bias that could still be exploited. We develop a tool combining MILP-based trail search with a recursive evaluation of assignments to the constant inputs. It estimates the probability that no valid trail remains and uses an additional heuristic to predict the zero-sum probability. Applying this tool to PRESENT and GIFT, we obtain probabilistic integral distinguishers for 6 to 9 rounds, including 6- and 7-round PRESENT distinguishers using $2^4$ and $2^{12}$ plaintexts per structure, respectively. For the ASCON permutation, we obtain 4- and 5-round distinguishers using as few as $2$ and $2^{12}$ inputs per structure. We further explain algebraically the large bias of the 6-round PRESENT distinguisher, showing how the S-box and bit permutation restrict the way active variables combine. Finally, we show how these distinguishers can be used for key recovery, reducing both the data and time complexities compared to their deterministic variants for PRESENT and GIFT-64.
Integer Coordinate Families and Threshold RSA Signatures for Any Prime Exponent
At CT-RSA 2026, Ng and Lau introduced $(t,n)$-integer coordinate families for threshold RSA signatures with $e=3$, and found some families by heuristic search for $2\le t \le n \le 9$. They asked whether such families always exist and, if so, can they be constructed efficiently. We answer both of these questions positively. We prove that a $(t,n)$-integer coordinate family is also a $(t+1,n)$-integer coordinate family. We construct such families for $t=2$, and $2\le n < 19$, using a polynomial time algorithm in $n$ and its output bit length. Answering another question raised in the Ng-Lau work, we prove super-polynomial lower bounds on coordinates of pairwise families. We also find the minimum families for $n \le 9$.
Ng and Lau proposed a threshold signature scheme based on integer coordinate families. We show that the Ng-Lau scheme admits trivial forgeries, and has a flawed proof. We give a repaired scheme $\mathrm{PiIC}$ which does not suffer from these issues. Finally, we propose an integer secret-sharing scheme $\mathrm{PiZ}$ that works for every prime $e$ and every $(t,n)$, without relying on any special coordinate family. We prove that both the schemes $\mathrm{PiIC}$ and $\mathrm{PiZ}$ are TS-UF-CMA secure under the standard RSA assumption.
High-Precision Bootstrapping for GCKKS
Generalized CKKS (GCKKS) trades slot count for reduced modulus consumption in high-precision approximate arithmetic.
However, designing a GCKKS bootstrapping algorithm with reduced modulus consumption throughout its computation remains a challenging problem.
We construct high-precision bootstrapping for GCKKS using low-precision overflow extraction followed by iterative precision enhancement.
Our main ingredient is a ciphertext-conversion framework for changing the decryption factor and slot count without requiring the factors to be units.
A slot-aware analysis bounds unused-slot magnitudes proportionally to the corresponding evaluations of the decryption factor, which is essential to ensure the unused-slot values remain well-bounded after conversion.
We combine precision doubling with ciphertext splitting and develop a joint evaluation procedure that produces two error-cleaned outputs at the cost of only one evaluation of the cleaning polynomial.
We also give a useful-slot-preserving conversion from CKKS to GCKKS that simultaneously resets unused slots through component-wise re-encoding.
Underlying these constructions, we also improve the construction of the decryption factors by searching directly in the canonical embedding and obtain depth-free conjugation with non-unit factors. For target encoding precision $p$ and $2N/k$ useful slots in a ring of dimension $N$, the precision-dependent stages of the bootstrapping use $O(k)$ homomorphic operations and consume $O((p/k)\log k)$ modulus bits.
Linear Cryptanalysis of TFHE-Friendly Cipher FRAST in the Average Key Setting
In the average key setting, a linear attack of Bak et al. on the TFHE-friendly stream cipher FRAST let wrong guesses pass, which they left as an open problem. The S-boxes of FRAST are public and random for every keystream block. For the mask on the least significant bit, we show that key differences fall into five indistinguishable classes per round. The filter of Bak et al. gives some wrong classes of the right parity a nonzero expected score. We compute the trail correlation exactly through the real cipher and bound the success of our statistic for every fixed master key. We bound its false alarms for a fixed master key with the last round kept and no filter, and for every attack against an ideal keystream.
With known XOF inputs, our algorithm Contract recovered the classes of a branch pair of 15 rounds and the master key of ten rounds. A cost model gives class recovery for every sampled key at 26 rounds with known inputs and for a third at 38 rounds with chosen inputs. In the accounting of Bak et al., it reaches full FRAST on weak master keys of density $2^{-11.8}$ to $2^{-5.4}$ within the claimed security. A distinguisher of full FRAST has a proved advantage on these keys, and its time over the advantage stays below the claimed security as well. Independent branch S-boxes remove the cheap classes at a cost in TFHE.
TP-NTT: Batch NTT Hardware with Application to Relinearization
Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data without decryption, providing strong privacy guarantees for secure cloud computing, encrypted analytics, and privacy-preserving machine learning. However, practical deployment of FHE remains limited by the high computational cost of polynomial arithmetic over large modular rings. In particular, Number Theoretic Transform (NTT)–based polynomial multiplication dominates the execution time of modern lattice-based FHE schemes. In this work, we present TP-NTT, a scalable, throughput-optimized NTT architecture supporting a wide range of ring dimensions used in FHE, from $2^{10}$ to $2^{16}$. Our design applies optimizations at multiple levels, from modular arithmetic to the NTT algorithm itself, including multi-dimensional decomposition without requiring additional multiplication blocks. The decomposition dimensionality is configurable at design time, supporting 2-D, 3-D, and 4-D decompositions, each advantageous in specific scenarios. Furthermore, TP-NTT provides design-time-configurable throughput. Combined with its scalable architecture, this enables significant advantages for batch NTT operations compared to other works in the literature. At $n=2^{16}$, it outperforms the best-performing prior design by $1.33\times$ in average latency while achieving $1.24\times$ better area–time-product (ATP). To demonstrate its efficiency, we present a case study on FHE relinearization, focusing on the BFV scheme. We propose a relinearization accelerator that leverages the fast batch NTT capability of TP-NTT, achieving $67.34\times$ speedup over state-of-the-art software implementations and highlighting TP-NTT’s effectiveness in real-world FHE applications.
RISQrypt: Fast, Secure and Agile Hardware-Software Co-Design for Post-Quantum Cryptography
In this paper, we present RISQrypt, the first unified architecture in the literature that implements ML-KEM (f.k.a. CRYSTALS-Kyber) and ML-DSA (f.k.a. CRYSTALS-Dilithium), two standardized lattice-based post-quantum cryptography (PQC) algorithms, with masking. RISQrypt is a hardware–software co-design framework that integrates dedicated cryptographic accelerators to speed up polynomial arithmetic, hashing, and mask-conversion operations, the latter being one of the primary bottlenecks in masked implementations of lattice-based PQC. Our design achieves low latency while providing both theoretical and practical side-channel security through formal proofs in the $t$-probing model and practical experiments. Specifically, the masked decapsulation of ML-KEM-768 requires $\mathbf{109K}$ clock cycles, while masked signing of ML-DSA-65 requires $\mathbf{1230K}$ clock cycles on average. These results demonstrate $\mathbf{11.3\times}$ time-performance improvement over existing masked implementations. Our time performance results for unprotected functions also outperform the existing work; achieving speed-ups of $\mathbf{10.64\times}$ and $\mathbf{8.94\times}$ for ML-KEM's encapsulation and decapsulation algorithms, respectively, and $\mathbf{1.14\times}$ and $\mathbf{2.23\times}$ for ML-DSA’s signature generation and verification algorithms, respectively, when compared to existing designs with similar resource usage. In addition, prior designs are more limited in scope, generally supporting only a single scheme and lacking either the side-channel protection or the unified, crypto-agile framework that enables support for both ML-KEM and ML-DSA as in our architecture. Leveraging the HW/SW co-design approach, the proposed architecture can be reprogrammed through firmware to support other (and future) PQC standards and algorithms sharing similar computational building blocks. As proof of concept, we demonstrate this capability by implementing FN-DSA (f.k.a. Falcon) and SLH-DSA (f.k.a. SPHINCS+).
The SecureDrop Protocol: End-to-End Encrypted Whistleblowing for All
Confidential sources are vital for investigative journalism and thus for holding those in power to account. However, sources often face great risks to their privacy and safety. SecureDrop is a system that enables sources to anonymously contact journalists, including at major news organisations around the world. Despite its widespread use, the current design requires physical servers hosted on premises. While cloud-based deployment would alleviate this burdensome requirement and improve SecureDrop's usability and accessibility, it would also introduce new threats to security that are not addressed by the current design. In particular, a lack of end-to-end encryption presents serious risks in the event that a cloud service provider is coerced into revealing information.
In this work, we present and formally analyse a new protocol for SecureDrop which addresses the challenges of off-premises deployment. Our protocol composes an encryption scheme with hybrid post-quantum guarantees and an identity-hiding message-fetching mechanism to provide strong anonymity guarantees. In contrast to existing systems, we minimise incriminating evidence against whistleblowers by providing message-level deniability and by having sources remain stateless. Our formal security analysis combines the Tamarin prover for symbolic analysis and game-based proofs for computational analysis. Finally, our benchmarks demonstrate that the protocol achieves practical levels of performance in a browser context. The Freedom of the Press Foundation plans to deploy the new protocol, with integration efforts beginning in 2026.
Gram Moments and Pairwise Mixing of AES
Almost pairwise independence asks how closely a block cipher reproduces the joint output distribution of a random permutation on two distinct plaintexts. Existing analyses of AES with independent round keys combine bounds on the distribution after the first few rounds with contraction over later rounds. Diffusion makes local output differences dependent, and estimating local responses or successive transitions separately can lose useful information. We preserve these dependencies in two ways. First, Gram-moment estimates sum the squared overlaps between local responses whose inputs are linked by diffusion. Second, we estimate two consecutive transitions together. The compatible intermediate differences form affine fibers; summing over these fibers inside the composed operator retains the constraints shared by the two diffusion layers.
We prove $\varepsilon_{8+2k}<2^{-92.19-41k}$ for every integer $k\ge0$, where $\varepsilon_r$ is the largest total variation distance, over distinct plaintext pairs, between the ciphertext-pair law and the corresponding random-permutation law. The round keys are independent and uniform, sampled once and reused across evaluations. Consequently, 10, 14, and 16 rounds suffice for statistical accuracy $2^{-128}$, $2^{-192}$, and $2^{-256}$. The same bound controls the complete view of an algorithm making at most two adaptive classical forward queries with an independent finite private seed. The resulting family gives 41 additional bits of pairwise accuracy for every two additional rounds, starting at eight rounds.
The Distributed Producer-Consumer Model Is All You Need: A Compiler for Asynchronous BFT
Building an Asynchronous Byzantine Fault Tolerant (BFT) protocol requires establishing payload availability with total order despite Byzantine faults and arbitrarily delayed messages. Although many BFT systems separate payload dissemination from agreement, they often couple their composition to protocol-specific selection or scheduling mechanisms. We present the Distributed Producer-Consumer Model (DPCM), an event-driven abstraction that separates payload-specific certified availability from payload-oblivious binary finalization. We prove that DPCM compiles any producer–consumer pair satisfying interfaces specified herein into an asynchronous BFT object log. DPCM batch-finalizes certified heights, deterministically refining failed batches until each height yields a normal or evidence-backed dummy entry. We instantiate DPCM as Octopus, which combines parallel consistent broadcast producers with batched asynchronous binary agreement (ABA). To achieve performance advantages, Octopus lets producers certify blocks without waiting for consumer decisions and keeps payload recovery off the agreement path. One ABA optimistically finalizes multiple consecutive producer columns, while failures trigger parallel row-wise refinement with logarithmic bisection depth. Across an eight-region WAN with $n\in\{8,16,32\}$ and 2200-transaction blocks, Octopus remains within 6.5% of Dumbo-NG's (ACM CCS'22) fault-free throughput. With the maximum tested number of silent faulty parties, it outperforms Dumbo-NG by 25.9% and 18.7% at $n=8$ and $n=16$, respectively, and remains within 1% at $n=32$. At $n=16$ and $n=32$, Dumbo-NG's latency is 1.9--2.5$\times$ that of Octopus. Across all evaluated settings, Octopus achieves 2.9--16.8$\times$ the throughput of Alea-BFT (USENIX NSDI'24), whose latency is 2.4--15.2$\times$ that of Octopus.
CLAASP-MP: An Automated MILP Framework for Monomial Prediction
As AI increasingly automates cryptanalytic programming, transparent and reproducible frameworks are essential for making generated results human-verifiable. We present CLAASP-MP, a monomial-prediction tool integrated into CLAASP and based on the three-subset division property without unknown subset (3SDP-woU). CLAASP-MP generates a Mixed Integer Linear Programming (MILP) model directly from the CLAASP component graph, supporting S-boxes, linear layers, Boolean operations, modular addition and multiplication, and linear and nonlinear feedback shift registers.
For selected output bits, CLAASP-MP computes the algebraic normal form (ANF) for small numbers of rounds, derives superpolies for a chosen cube, and bounds the algebraic degree with respect to plaintext, key, or IV variables. It detects absent monomials through vanishing ANF coefficients, zero superpolies, or degree bounds, thereby identifying balanced outputs and integral distinguishers.
We evaluate CLAASP-MP on block ciphers, permutations, and stream-cipher update functions. For block ciphers, we reproduce known distinguishers, find new cubes, and report the first integral distinguishers for SAECHAM. For Splight, we reach rounds 10 and 11, despite a previous two-subset division-property search reporting no 10-round distinguisher. On MSX-128, a $96$-dimensional cube leaves $64$ of $128$ output bits balanced after 7 rounds. For permutations, we extend the best-known division-property distinguishers for ChaCha and Salsa from 6 and 5 rounds, respectively, to 6.75 rounds; give the first such distinguishers for Forr\'o; and reduce the data complexity for Chaskey-Pi from $2^{64}$ to $2^{23}$ at round 3 and from $2^{127}$ to $2^{122}$ at round 4. For stream ciphers, we find new 36-dimensional cubes for Bivium, extend the tight degree bounds for Trivium to later initialization clocks, and reproduce published superpolies.
These results establish CLAASP-MP as a unified, practical, and human-verifiable framework for monomial prediction across symmetric primitives.
The Good, the Bad, and the Noisy: A Systematic Analysis of Ring-Oscillator-Based Noise Generators
Hiding countermeasures, alongside masking, play an important role in modern hardware security for protecting against side-channel attacks. Additive noise generators are one such hiding countermeasure. They increase the noise, thereby lowering the signal-to-noise ratio and, simultaneously, amplifying the effectiveness of masking countermeasures. Among the different design options for additive noise generators, ring-oscillator-based designs feature regularly in scientific publications. These existing works not only differ in their designs, but also in their evaluation methods; therefore, they do not permit fair comparisons or enable systematic evaluations. Thus, it is currently not possible to design ring-oscillators for noise generation in an informed and tailored way.
In this paper, we address this lack of systematic comparisons of existing designs, and discuss the possibility of filtering out the generated noise and further limitations of ring-oscillator-based noise generators. We find that many existing designs do not consider the need to amplify the output signal or the risk of filtering. As a consequence, the existing designs do not sufficiently lower the signal-to-noise ratio in our experiments. However, using these results, we provide a guideline for tailoring and configuring ring-oscillators so that they efficiently add noise in the desired frequency spectrum. This includes deciding on the inverter chain length, the amplification of the output, and the randomization of the output frequency. Finally, we apply this methodology to build a tailored ring-oscillator-based noise generator for an exemplary AES implementation and find that it significantly outperforms existing ring-oscillator-based designs.
ANNULAR: Post-Quantum Private Transactions from Isogenies with Recursive Batch Verification
ANNULAR is a shielded pool built on isogeny-based primitives. Notes are committed in a Merkle tree and spent by nullifier with hidden amounts, following the structure of Zcash's Sapling, but every primitive is post-quantum: spends are authorised by the prime-degree PRISM signature of Basso et al., note ciphertexts are keyed by the MIKE non-interactive key exchange, and each transaction carries a STARK proved natively over the isogeny field. The transaction proofs of a block are then folded into a single recursive proof. A ledger need record and verify only this one proof, 426 KB in 15 ms, whatever the batch holds, and check each transaction's two signatures alongside it. A transaction's body is the size of Sapling's at the same memo length (2,685 bytes against 2,756 with a 512-byte memo); its share of the batch proof adds under 500 bytes.
A move to post-quantum primitives is generally expected to raise a pool's operating cost. We argue that the post-quantum change and the scaling change are complementary: with a STARK as the proof system, proofs fold, and with isogeny keys, the per-transaction data remains small. The cost moves to the sender, whose proof takes 1.4 s on sixteen cores, and to one aggregator per batch, which we measure: 1,248 transactions in 99 s on one GPU. Each proof in the tree carries 100 bits of round-by-round soundness and the batch about 90 under a union bound; under Fiat–Shamir that is the work an adversary needs. The constraints of the leaf circuit are proven in Lean 4 to encode the spend statement, while the soundness of the STARK itself rests on a paper argument. The scheme's claims rest on the signature's existential unforgeability; its strong unforgeability, argued by the construction's authors and not yet proved, is not relied on.
Graphs and cycles in curve-based collision walks
In this work, we look at collision-based attacks both for elliptic curve and isogeny problems. Our main focus is on attacks in the multi-user setting, i.e., where one tries to recover all secret keys of a large set of $L$ public keys simultaneously, in a faster way than the total time required to attack each key individually. We consider three different problems: (1) the discrete logarithm problem on elliptic curves, (2) the isogeny pathfinding problem on supersingular $\mathbb{F}_{p^2}$-curves, (3) the isogeny pathfinding problem on supersingular $\mathbb{F}_p$-curves. We first survey the existing van Oorschot and Wiener style attacks on these three problems. Then we propose versions of the pseudorandom walks that are better suited for isogeny pathfinding problems without additional restrictions. We then apply these new walks to the multi-user setting and analyse which properties we can achieve compared to the discrete logarithm case where we show that we can extract all $L$ public keys with $L$ useful collisions and without an infiltrator (a user for which we know the secret key). Specifically, for (2) we can extract $L$ public keys with approximately $L + \log(L)$ useful collisions and no infiltrator needed. Our analysis shows however that heuristic and infiltrator-aided strategies are more efficient while enjoying practically similar gains. For (3) we can extract approximately $0.75L$ public keys with $L$ useful collisions, but with an infiltrator.
One-Step Schnorr Threshold Identification
Threshold cryptographic primitives have not been widely adopted in real-world distributed systems (i.e., beyond the closed committee model) presumably due to state-synchronization overhead and complex certification processes for the shareholders. These are both aspects of their overreliance on infrastructure, an assumption that is usually glossed over in their design. In this work, we propose OSST, a real-time threshold identification protocol that achieves non-interactivity and non-reliance on public shares by means of direct proof interpolation. Given a Shamir $(n, t)$-shared secret $x$, the proposed scheme allows any $t^* \ge t$ (but no less) shareholders to prove over designated communication channels that their key shares interpolate to $x$ without revealing any information beyond that. Provers do not engage in distributed computations, sending their packets to the verifier asynchronously; conversely, verifiers need only know the combined public key $y \equiv g ^ x$, without need to pre-validate and register the individual member identities. The protocol is intended for use in permissionless or unmanaged meshes that lack both overlay networks and trust infrastructure or governance, a use case space that has been tacitly neglected as ''niche'' by the current mainstream. No publicly verifiable setup is required beyond distributing $x$ according to Shamir's secret sharing (or equivalent distributed key generation scheme) and advertising its public counterpart; in particular, the protocol is intended to be secure against impersonation without relying on the auditability of any advertised public shares. We provide evidence that this has good chances to hold true by giving a reasonably restricted security proof in the random oracle model under the one-more discrete-logarithm (OMDL) hardness assumption.
Rotational-Quasidifferential Framework - A Geometric Approach to Rotational-XOR Cryptanalysis
Rotational-XOR (RX) cryptanalysis extends rotational cryptanalysis by combining rotational relations with XOR translations, enabling the analysis of symmetric-key primitives even in the presence of symmetry-breaking constants.
Existing analyses of RX characteristics, however, typically rely on independence assumptions when estimating characteristic probabilities, which may lead to inaccurate probability evaluations and even incompatible characteristics.
In this paper, we introduce the first application of the geometric approach to RX cryptanalysis.
Inspired by the quasidifferential framework of Beyne and Rijmen, we define rotational-quasidifferential trails and derive exact expressions for fixed-key RX characteristic probabilities without relying on round-independence assumptions.
We also derive explicit rotational-quasidifferential transition matrices for bitwise AND and modular addition.
By incorporating the key schedule into the state space, we further obtain an exact expression for the Expected Rotational-XOR Probability (ERXP), the RX analogue of the Expected Differential Probability (EDP).
We apply the framework to the ARX cipher SPECK, the ARX permutation Alzette, and the AND-RX ciphers SIMON and SIMECK.
For SPECK, we repair an incompatible 12-round characteristic and show that the longest published RX characteristics for SPECK64/128, SPECK96/144, and SPECK128/256 are incompatible.
For Alzette, we show that signed nonzero-mask contributions explain the discrepancy between independent-ADD estimates and experimentally observed full-data-path probabilities.
For SIMECK, we experimentally verify a fixed-key probability distribution, explain incompatible characteristics, and correct the weak-key class estimates of rotational-XOR differential rectangle attacks.
These results extend the geometric approach to both ARX and AND-RX designs and demonstrate its usefulness for exact characteristic-level analysis.
Adaptively Secure Blockchain-Aided Decentralized Storage Networks: Formalization and Generic Construction
Blockchain-aided decentralized storage networks (DSNs) use public audits to verify outsourced storage and smart contracts to govern payments and collateral.
Published audit evidence, however, remains available to servers and may let them reduce local storage while continuing to pass audits.
Retrieval must also remain fair across adaptively selected sessions.
We formalize DSN protocols across delegation, preservation, and retrieval, accounting for evolving server state and externally available proofs.
To support adaptive replication soundness, we reformulate rational replication for proofs of replication (PoRep) as an extractor-based notion.
We then give a generic construction combining PoRep, verifiable delay functions, and simulation-extractable zkSNARKs, with encrypted delivery and conditional authorization for retrieval.
Our analysis identifies roles for succinctness and simulation-extractability beyond privacy and efficiency.
Under the knowledge of strong compression assumption and the stated primitive and timing assumptions, we establish adaptive replication soundness subject to bounds on extraction resources and the cumulative public transcript.
We also establish contract unforgeability and retrieval fairness.
Controlled experiments illustrate storage offloading through public audit evidence, while a separate Merkle-PLONK prototype measures proving and verification costs through Cardano's Plutus interface.
Getting to the right root: radical isogenies of every degree
Class group actions on supersingular elliptic curves over $\mathbb F_p$ as in CSIDH are typically evaluated as long chains of isogenies of small prime degree. Radical isogeny formulae compute such chains using a single $N$th root per step, without sampling torsion points. Compact formulae of linear size had been conjectured for all odd $N$. We prove a corrected version of these formulae for every $N\ge4$, odd and even, over every field of characteristic coprime to $2N$. In our formulation, every building block is a twisted sum of a discrete Kronecker function over $\mathbb Z/N\mathbb Z$, and the formulae follow from a distribution relation for the Kronecker theta function.
For even $N$, the $N$th root is only determined up to sign over $\mathbb F_p$, and the sign decides whether the walk stays on the surface of the $2$-isogeny volcano. We show that the radical times a $2$-torsion coordinate of the next curve is a square, which yields the horizontal choice for all even $N$; previously this was only known for $N\le14$. Algorithmically, one radical step costs about $12.5N$ multiplications and one exponentiation, without inversions. For horizontal $2$-isogeny walks, radical $2^m$-isogenies with $m\in\{5,6,7\}$ are optimal for primes of $512$ to $4096$ bits. Finally, we show how to evaluate radical isogenies on points. As a consequence, a class group action can be computed from two given points, one on the curve and one on its quadratic twist, without ever sampling torsion points.
Registered Functional Encryption for Circuits with Dynamic Bounded Collusion
Registered Functional Encryption (Reg-FE) eliminates the key escrow issue in traditional functional encryption by allowing users to generate their own public/secret keys without the help of a central authority. The public key is then registered to the system along with a function, and all the registered public keys will be aggregated to a compact master public key by a transparent key curator. Messages are encrypted under the master public key, and users can learn functions of encrypted data from the ciphertext using their own secret keys.
Prior constructions of Reg-FE either become insecure when more than one malicious users collude or require the heavy machinery of indistinguishability obfuscation. In this work, we construct the first collusion-resistant Reg-FE without obfuscations. The schemes are secure if the number of colluded users is bounded, and the collusion bound can be either a global parameter or specified by the encryption algorithm dynamically. In both settings, we provide generic constructions of Reg-FE from registered attribute-based encryption and instantiate them from either the standard $k$-Lin assumption or the succinct LWE assumption.
Efficient Laconic Oblivious Transfer with Malicious Security
Laconic Oblivious Transfer (OT) enables a receiver to compress a large database into a short digest, allowing a sender to generate a succinct ciphertext that reveals only a single indexed message. While prior works achieve efficient constructions in the semi-honest model, known solutions for malicious security rely on inherently heavy non-black-box techniques, such as garbled circuits or succinct arguments, resulting in impractical schemes.
In this work, we present the first construction of maliciously secure laconic OT that makes fully black-box use of its underlying primitives. Our construction is based on a simple and widely used paradigm combining vector commitments with witness encryption, previously known to yield efficient semi-honest protocols. We show that this approach can in fact achieve malicious security by introducing two minimal yet powerful enhancements: equivocal vector commitments and maliciously secure witness encryption. We prove that these properties suffice to obtain laconic OT with security against malicious senders in the universal composability model and against malicious receivers in the context model.
We instantiate our framework from standard assumptions, including LWE and bilinear Diffie-Hellman variants, obtaining schemes in the standard model. Notably, our constructions avoid heavy non-black-box tools mentioned before, and therefore achieve efficiency comparable to the state-of-the-art black-box constructions with merely semi-honest security. In particular, in certain settings, we obtain malicious security at essentially no additional asymptotic cost.
Our results resolve a central question on the feasibility of practical, maliciously secure laconic OT, and provide a unifying pathway for efficiently achieving malicious security in laconic cryptography.
Laminate: Succinct SIMD-Friendly Verifiable FHE
In outsourcing computation to untrusted servers, one can cryptographically ensure privacy using Fully Homomorphic Encryption (FHE) or integrity using Verifiable Computation (VC) such as SNARK proofs. While each is practical for some applications in isolation, efficiently composing FHE and VC into Verifiable Computation over Encrypted Data (VCoED) with verification faster than local computation remains a challenge.
We introduce $\mathsf{Laminate}$, a family of VCoED protocols for adding integrity to computations delegated using BGV/BFV-style FHE. Our approach combines the blind interactive proof framework with the GKR proof system, which avoids computing commitments to intermediate computation states under FHE. Our client-efficient variant employs novel transcript packing and folding techniques that reduce proof size to $O(\log^2 n + N)$ words (suppressing security parameters) for bounded-depth size-$n$ circuits, where $N$ is the BGV/BFV ring dimension. Unlike prior FHE-over-SNARK schemes, $\mathsf{Laminate}$ preserves the SIMD parallelism of FHE for both payload circuit evaluation and proof generation; eliminates the need for witness reductions; is field-agnostic; and adds only constant multiplicative depth on top of payload evaluation while performing $\widetilde{O}(n_{\mathsf{FHE}})$ FHE operations, where $n_{\mathsf{FHE}}$ is the number of payload FHE operations.
We give an end-to-end concrete integrity analysis, implement the complete protocol, and provide a reproducible methodology for measuring server overhead and per-request client computation. We benchmark $\mathsf{Laminate}$ on payload circuits with $n=2^{34}$ scalar gates. One scheme variant has an overhead of $21$--$33\times$ compared to FHE evaluation without integrity, with proofs of $52$--$54\,\mathrm{MB}$. Another variant reduces overhead to $10$--$14\times$, with larger proofs. For both, per-request client computation is much faster than local evaluation, demonstrating concrete outsourced computation with privacy and integrity, a key distinction from prior VCoED work.
A Post Quantum Vector Commitment Scheme with Efficient Insertions and Deletions
Vector Commitments (VCs) are a cryptographic primitive that allows users to commit to a tuple and later provide proofs about entries of the committed tuple. Literature on VCs provides many secure constructions with properties attractive for decentralized applications. These include fast commitment/proof update algorithms after a value in the committed vector changes, algorithms to aggregate position proofs, generating proofs for subvectors, commitment hiding, and many more. However, these works assume a static setting, where only vector values change and the length of the committed vector never changes. We initiate the study of designing VCs which support efficient updates to commitments and proofs after a change in vector length occurs (i.e. an insertion or a deletion of a vector value at an \textit{arbitrary} position). In order to construct such a primitive, we formalize a VC framework implicitly considered in VC based verifiable decentralized storage constructions. Parties control a subset of positions in the committed vector. A proof for an inserted vector value at a given position may only be generated via participation from enough honest parties. We call such primitives \textit{Multiparty Dynamic Vector Commitments}. Our work provides formal definitions for multiparty dynamic VC functionality and security. In particular, standard VC binding does not extend to our dynamic setting. This motivates us to define the \textit{dynamic multiparty binding} security notion. We also comment on how multiparty dynamic VCs can be applied to extend existing VC based instantiations of verifiable storage. Finally, we provide a vector commitment construction and show that it possesses multiparty dynamic binding under standard lattice assumptions.
Consensus in One Shot: Fast Agreement Beyond Classical Limits
Good-case latency, studied in early fast-consensus protocols (Martin and Alvisi, DSN 2005) and formalized by Abraham, Nayak, Ren, and Xiang (DISC 2020), captures a natural efficiency goal: when the sender is honest, agreement should be reached quickly for the honest parties. In the standard classical model, however, there exists a barrier for any $f\geq n/3$ corrupted parties. Specifically, synchronous broadcast requires good-case latency at least $\Delta+\delta$ for $f\geq n/3$, where $\delta$ is the actual, unknown message-delay bound and $\Delta \gg \delta$ is its known, conservative upper bound. Under partial synchrony, consistency and liveness cannot even both hold for $f \geq n/3$ (Dwork, Lynch, and Stockmeyer, JACM 1988).
In this work we study the use of quantum information to get past these classical barriers, specifically using one-shot signatures (OSS) (Amos et al., STOC 2020, Shmueli and Zhandry, CRYPTO 2025). OSS prevents even a corrupt signer from issuing signatures on different messages under the same verification key, which provides cryptographic non-equivocation without trusted hardware assumptions.
Assuming OSS and a public-key infrastructure, we obtain two main results against quantum polynomial-time static corruptions. First, under synchrony, we construct a state-machine replication (SMR) protocol without clients, with optimal $\delta$ good-case latency, tolerating any $f<n$ corruptions among $n$ parties. Second, under partial synchrony, we obtain SMR with $2\cdot \delta$ good-case latency which is consistent under any number of corruptions and live assuming $f<\frac{n}{2}$. Specifically, a corrupt majority may cause progress to stop, but cannot create conflicting histories. Such an always consistent protocol is impossible classically (without assumptions like trusted hardware) even if liveness is only required to hold against a single corrupt party. In both our SMR protocols, communication is entirely classical, with only local quantum computation.
Time-Space Tradeoffs For Probabilistic Proofs
Many recent constructions of probabilistic proofs achieve fast proving times but have high space complexity (much higher than that of the computation being proved). Empirically this arises due to the fact that error-correcting codes, a key ingredient of such constructions, suffer from limiting time-space tradeoffs. It remained open, however, whether such time-space tradeoffs exist for proofs themselves.
We establish time-space tradeoffs for probabilistically checkable proofs (PCPs) as well as for their multi-round extension, interactive oracle proofs (IOPs), with straightline knowledge soundness. Our results hold for machine computations that have sequential input access, the same model for which similar tradeoffs hold for error-correcting codes. We complement this result by describing an IOP for R1CS that avoids the tradeoff but requires random access to the R1CS witness.
Our techniques build on and extend results for codes of Cook and Moshkovitz (CCC~2024). A key difficulty that we encounter in establishing our tradeoff is that distance of the code plays a key role in prior results, while for probabilistic proofs there is no natural notion of distance. Nevertheless, we show that, assuming the existence of collision-resistant hash functions, we can establish time-space tradeoffs by carefully relating a small-space machine's information flow to the proof system's properties.
Sotto Maschera: Masking the Sota-Voce Fixed-Weight Vector Sampling
Sparse fixed-weight vector sampling is a highly critical primitive in several post-quantum cryptography schemes. It has also been the target of multiple side-channel attacks, demonstrating the need for robust implementations. While such implementations do exist, they are not necessarily practical in terms of runtime, and some have already been shown to be insecure. At CHES 2026, Filho et al. presented a runtime-optimized, but not side-channel protected, sparse fixed-weight vector sampling algorithm named Sota Voce. It consists of the Sota support sampler and MWSupport support-to-vector conversion, where the latter is planned to be included in the next HQC implementation. This work explores how both parts of Sota Voce can be transformed into a power side-channel protected implementation using masking gadgets for embedded devices. At the same time, we aim to preserve its competitive performance advantage over other masked implementations. By bitslicing core components of the algorithm, including sorting, merging, and compaction, we achieve high parallelism of the computation, improving the overall runtime. Moreover, we avoid slow masking conversions by masking exclusively in the Boolean domain. Thereby, our masked implementation is orders of magnitude faster than the state-of-the-art, while showing no power side-channel leakage in TVLA evaluations. For instance, for HQC, we achieve a speedup of up to 45x in comparison to previous work.
AuthOr: Lower Cost Privacy-Free Garbling of Arbitrary Boolean Circuits
Privacy-free garbling schemes of Frederiksen et al. (Eurocrypt
’15) are designed to satisfy only the authenticity criterion of Bellare
et al. (ACM CCS ’12) and to be more efficient than full-fledged garbling
schemes. In this work, we improve the state-of-the-art privacy-free version
of half-gates (HG) garbling of Zahur et al. (Crypto ’15) by allowing
an AND gate to be garbled with zero ciphertexts whenever at least one
of its input wires is freely settable by the garbler. Our full solution, AuthOr,
then combines the ideas from the information-theoretic garbling
of Kondi and Patra (Crypto ’17) with the improved HG-based scheme
we obtain. AuthOr has a lower communication cost (i.e., garbled-circuit
size) than HG garbling without any additional security assumptions.
Theoretically, AuthOr’s garbled-circuit size reduction over HG garbling
ranges from 0% to 100%, with the exact improvement depending on the
circuit structure. We have implemented our scheme and evaluated it on
various circuits constructed by independent researchers. Our experimental
results show that, in practice, the garbled-circuit size reduction can
reach roughly 98%.
Rerandomizable Garbling for Arithmetic Circuits
Rerandomizable garbling is a powerful extension of Yao’s garbled circuits that allows a garbled circuit to be refreshed without changing its functionality, while preserving privacy as long as at least one rerandomization step is honest. Existing constructions, however, are limited to Boolean circuits and incur significant communication overhead.
In this work, we initiate the study of rerandomizable garbling for arithmetic circuits. We present the first rerandomizable arithmetic garbling scheme, based on techniques inspired by recent advances in garbling from homomorphic secret sharing. Our construction departs fundamentally from previous approaches and achieves communication complexity $O(|\mathbf{C}|\log B)$ for circuits $\mathbf{C}$ with $B$-bounded computation. Concretely, our scheme requires 17 group elements per multiplication gate, while addition gates are free. Our scheme can be instantiated under standard subgroup-indistinguishability assumptions, including the Decisional Composite Residuosity (DCR) assumption and assumptions over class groups.
Hint-Free Multi-Signatures
In a (non-interactive) multi-signature scheme, parties independently generate keys and produce signatures on a common message, which can be aggregated into a single signature verifiable with respect to the set of public keys. Existing multi-signature constructions, however, suffer from at least one of two limitations: either (1) aggregate signatures cannot be further aggregated, or (2) verification requires auxiliary information beyond the set of public keys, such as the aggregation topology.
We argue that these limitations significantly restrict the applicability of multi-signatures in large-scale distributed systems, such as proof-of-stake blockchains. To address this gap, we initiate the formal study of hint-free multi-signatures, which support multi-hop aggregation while allowing verification using only the set of public keys.
To the best of our knowledge, the only previously known (folklore) construction that is fully hint-free relies on recursive SNARKs, which introduces unclear heuristics for security (e.g., proving statements about random oracle relations) or inherently limits the depth of the aggregation topology.
We show that hint-free multi-signatures can be realized without proof recursion, in the standard model. At a high level, we show how to publicly normalize BLS multi-signatures so that verification depends only on the set of public keys rather than a multi-set. While our scheme is not practical (it uses indistinguishability obfuscation), it establishes the feasibility of the primitive provides a foundation for future work on practical constructions.
Page-efficient Encrypted Multi-Maps: New Techniques for Optimal Search Bandwidth
Encrypted multi-maps (EMMs) allow a client to outsource a multi-map to an untrusted server and then later retrieve the values corresponding to a queried label. They are a core building block for various applications such as encrypted cloud storage and searchable encryption. One important metric of EMMs is memory-efficiency: most schemes incur many random memory accesses per search query, leading to larger overhead compared to plaintext queries. Memory-efficient EMMs reduce random accesses but, in most known solutions, this comes at the cost of higher query bandwidth.
This work focuses on EMMs run on SSDs and we construct two page-efficient schemes, one static and one dynamic, both with optimal search bandwidth. Our static scheme achieves $\tilde{O}(\log N/p)$ page-efficiency and $O(1)$ client storage, where $N$ denotes the size of the EMM and $p$ the SSD's page size. Our dynamic scheme achieves forward and backward privacy with $\tilde{O}(\log N/p)$ page-efficiency and $O(M)$ client storage, where $M$ denotes the number of labels. Among schemes with optimal server storage, these are the first to combine optimal bandwidth with good page-efficiency, saving up to $O(p)$ and $\tilde{O}(p\log\log (N/p))$ bandwidth over the state-of-the-art static and dynamic schemes, respectively. Our implementation on real-world data shows strong practical performance.
Forensic categories: a framework for SQIsign-like primitives
Using the language of categories, we introduce a novel framework abstracting the key algorithmic features of the Deuring correspondence between supersingular elliptic curves and quaternion orders and of the post-quantum signature scheme SQIsign based on it. We then show how to construct an interactive identification scheme and digital signature within this framework, and also instantiate more advanced primitives, such as a chameleon hash function. We present two distinct instantiations of the framework based on isogenies of supersingular elliptic curves: the first recovers (one-dimensional) SQIsign, while the second leads to the recently published SQInstructor.
Cyclic isogeny walks on genus-zero modular curves
Isogeny-based cryptography implementations have to navigate a large space of options for representing elliptic curves and isogenies and for the corresponding arithmetic. This work collects, completes, and organizes the set of algebraic maps and relations available when working with genus-zero modular curves $X_0(N)$, which parametrize cyclic $N$-isogenies of elliptic curves and can be represented by a single field element. This abstract notion covers many single-parameter curve models, such as Montgomery, Edwards, Jacobi quartic, Hessian curve, Deuring normal form. Such single-parameter models for the same modular curve are related by degree-1 rational maps, which limits the remaining options for improving the expressions. This representation is universal in the sense that it can be obtained from any other algebraic parametrization of such isogenies, or simply from the $j$-invariants through which the isogeny passes, away from singularities. We propose a method to derive rational maps for computing such lifting from the $j$-line to $X_0(N)$.
Our main technical contribution is the definition, analysis, and computation of non-backtracking modular polynomials over these curves obtained using an extended method of Elkies. In addition to characterizing cyclic extensions of isogenies, they have many other useful properties, such as having lower degree and being sparser than other typical modular polynomials, smoother walk models (being better at distinguishing different isogenies), carrying additional isogeny of different degree along the walk. We also propose radical representations of the same relation, which sheds new light on a few existing radical isogeny formulas.
We illustrate the use of the framework by achieving more compact R1CS encodings for isogeny proofs of knowledge.
Eras MPC: Granular Preprocessing and Abort Recovery with Dynamic Committees
MPC with dynamic committees achieves scalability by having small committees execute each round of the computation, instead of involving all parties in the entire execution. However, achieving Guaranteed Output Delivery in efficient information theoretical protocols requires larger honest majority committees, limiting scalability. Moreover, using preprocessed correlated randomness to speed up the computation is prohibitively expensive due to the cost of transferring such randomness to parties that have not yet joined the execution.
We propose Eras MPC, a model where small dishonest majority computation committees execute one or more rounds of the computation with the help of honest majority preprocessing and checkpointing committees. The computation is carried out in "Eras", which are sets of shorter epochs. In the beginning of each Era's first epoch, a preprocessing committee generates correlated randomness for the computation epochs to be executed by different computation committees. In the end of an Era, checkpoint committees verify the current state of the computation, save this state if it is valid and provide the latest valid state to the next Era.
We show an Eras MPC protocol where the preprocessing is carried out using an honest majority MPC protocol to generate authenticated Beaver triples, requiring only enough rounds of interaction to perform two subsequent batches of multiplications. The computation is done via the SPDZ online phase executed in each epoch by a small dishonest majority committee. Finally, intermediate state is checkpointed by verifying the validity of wire shares and saving wire values in $4$ rounds, each executed by a different honest majority checkpoint committee.
RingTrace: Model-Free Spatio-Temporal Detection and Core Attribution for Cache Side-Channels
The widespread adoption of shared last-level caches in modern multi-core processors improves memory efficiency but introduces timing channels between untrusted programs. In particular, Flush+Reload serves as a high-resolution cache side channel and a fundamental data leakage mechanism in transient-execution attacks. Existing detection approaches predominantly rely on aggregate hardware performance counters, which discard spatial context, fail to locate the malicious core, and often confuse stealthy attacks with benign cache-intensive workloads. This paper addresses these gaps by proposing RingTrace, a system-level monitoring framework that synergizes core-local and uncore telemetry. We capture and normalize per-core cache misses alongside distributed slice activity across uncore CBoxes. Through Joint Spatio-Temporal Attribution (JSTA), we formulate an interpretable joint-activity matrix that captures spatial concentration and co-activity without requiring model training. In the hierarchical response, the largest entry of this matrix serves as the initial screening score, while its row sums identify a candidate core. Our approach reliably identifies victim-independent flush activity prior to secret leakage, effectively suppresses false alarms under severe concurrent memory pressure, and achieves rapid process confirmation with negligible application runtime overhead on commodity processors. This work introduces an interpretable and tamper-resilient hardware-assisted defense model, bridging local CPU execution with physical uncore traffic to provide robust protection against cache side channels.
Modeling Modular Multiplication for Monomial Prediction and Impossible Differentials, with Application to MSX
MSX is a recent family of lightweight block ciphers for microcontrollers, and its round function draws nonlinearity from modular addition and modular multiplication on $32$-bit words. The multiplication is the distinctive part of the design because it turns the round function into a strongly universal hash function, and from this, the designers prove ideal strong differential and linear properties. The same operation also kept MSX out of reach of automated cryptanalysis, since no exact bit-level model of a modular multiplication was available.
We give two such models for $z=(x\cdot y)\bmod 2^n$. Both work at the bit level and, to the best of our knowledge, both are new. The first is for monomial prediction under the three-subset division property without an unknown subset (3SDP-woU), and it assigns an exact parity to every monomial without using a truth table. The second is a deterministic truncated model for impossible differential search, and we prove that it is not merely sound but exact for two independent operands, so every incompatibility a miss-in-the-middle search reports through a multiplication is genuine.
Both properties are deterministic, so our results are exact, whereas the designers' own analysis provides bounds and estimates, with no explicit trail. Using the two models, we analyze MSX. As far as we know, this is its first independent cryptanalysis. For MSX-128 we obtain a $7$-round deterministic integral distinguisher of data complexity $2^{96}$, where a $96$-bit cube leaves $64$ of the $128$ output bits balanced, and we extend it to key recoveries on $8$ and $9$ of the $18$ rounds that recover the $256$-bit master key in about $2^{228}$ operations, improving over the MSX designers' generic yoyo key recovery attack on seven rounds.
Searching all $16,384$ single-bit pairs at each round count, we also find $1,984$ impossible differentials at seven rounds and none at eight. Both models are implemented in the CLAASP library, so they can be used on any included primitive that uses modular multiplication.
Verifiable Post-Quantum TLS Handshake: Recognizing Implementation Errors of Cryptographic Verification Steps
The migration to post-quantum cryptography is becoming unavoidable for security protocols. Yet as the historical "goto fail" incident illustrates, deploying new primitives is not sufficient: subtle implementation bugs, especially in verification logic, can yield systems that remain fully interoperable while compromising security silently. Existing confirmation code techniques make certain errors observable, but they do not cover post-quantum signatures and provide limited protection in multi-stage handshakes.
Therefore, we present a migration-oriented solution that spans both the algorithm and protocol layers. At the algorithm layer, we develop two generic confirmation-code construction frameworks for Fiat–Shamir signatures and GPV-style Hash-and-Sign signatures, instantiated with ML-DSA and Falcon. For KEMs, we further propose a protocol-friendly, KEM-level confirmation-code method, instantiated with ML-KEM, HQC, and DAWN (NTRU-based KEM). We then prove confirmation-code unpredictability for each instantiation. At the protocol layer, we design PQCD-TLS, a post-quantum TLS handshake that binds confirmation codes into chained key derivation, ensuring that any verification fault induces key mismatch and causes handshake failure. We then extend a multi-stage authenticated key-exchange model with error-injection capabilities to formalize matching correctness with implementation errors, and prove that PQCD-TLS exposes such internal errors without compromising protocol security. Our implementation evaluates 48 configurations combining confirmation code-enhanced PQC algorithms and authentication modes. Results show that handshake latency overhead remains below 1% across all tests, while turning silent verification bugs into observable handshake failures.
SHAKEing SLH-DSA with Non-profiled SCAs
SLH-DSA is a hash-based digital signature algorithm, standardised by NIST as a post-quantum signature scheme. While prior work has analysed the vulnerability of its pseudorandom function (PRF) to differential side-channel analysis (SCA), no prior work has thoroughly examined this vulnerability under SHAKE as the PRF, nor recovered a full secret seed in practice. In this work, we address this gap by first analysing the differential SCA vulnerability of SLH-DSA-SHAKE, examining the inputs to the PRF and the possible selection functions for an attack. Then, based on this analysis, we propose a methodology to efficiently apply correlation power analysis (CPA) on every parameter set of SLH-DSA-SHAKE with three main steps: a strategy of averaging subtraces of the same signature to increase the signal-to-noise ratio; a partial-then-total CPA approach to reduce the complexity; and an efficient algorithm for the remaining exhaustive search to recover a full secret seed, which enables universal forgery. We then provide experimental results in simulation and on a 32-bit microcontroller. Our attack requires on average from $280$ to $559$ signatures, and in our experiments the exhaustive search completes within $45$ minutes on $72$ cores.
Rounded Gaussians are Discrete Gaussians
Many lattice-based cryptographic schemes still require sampling integers following a Gaussian-like distribution. Depending on the application, this sampling should be generic to tackle variable (and possibly large) standard deviations and centers, with a low memory footprint, easily implementable in constant-time, and with the highest throughput. Combining all these features is very challenging, as shown by the numerous works on optimizing discrete Gaussian samplers. In contrast, the rounded Gaussian (and associated samplers), formalized by Hülsing, Lange and Smeets (PKC'18), seems to satisfy these criteria, but its formal definition makes security analyses of the schemes using it more complex, thus explaining why they are rarely used in practice.
In this paper, we show that a small correction on the parameter $\sigma$ of the rounded Gaussian yields a distribution that is close to a discrete Gaussian of parameter $s$. More formally, defining $\sigma = s - 1/(24s)$ yields a Rényi divergence between the two distributions evolving as $1 + O(1/s^8)$. As a result, for mild to large parameters $s$, one can use the corrected rounded Gaussian sampler, while still analyzing security with an ideal discrete Gaussian at a very mild loss. It then readily gives a discrete Gaussian sampler that benefits from all the features of rounded Gaussian samplers.
SoK: Design-Level Backdoors in Block Ciphers Constructions, Detection, and Key Recovery
A block cipher is trusted once it resists every published attack and its
S-boxes pass the standard tests. A design-level backdoor turns this trust
against its users. Its designer hides a structure that only they can
exploit, and that the usual tests miss.
Four such backdoors have been published, by Rijmen and Preneel, Paterson,
Bannier and Filiol, and Peyrin and Wang. Each paper shows what the hidden
structure gives its designer. Everyone else needs answers to two other
questions. Does the structure also weaken the cipher against ordinary
cryptanalysis? Can an evaluator who holds only the specification find it?
Neither has been answered for all four designs, so an S-box that passes
the usual tests is trusted by default.
In this paper we answer both questions. We place the four designs in one
taxonomy and in Beyne's correlation-matrix framework. We give an algorithm
that recovers a partition trapdoor from the S-box tables, and prove that it
never reports a false one and, below an explicit cap, never misses one. We
show that inversion and affine equivalence preserve a trapdoor, while
extended affine and CCZ equivalence can erase it. We then attack KG-DES
(Paterson's S-boxes in DES), BEA-1 and LowMC-M.
The answer to the first question depends on the rest of the cipher. In
KG-DES the trapdoor makes ordinary attacks far stronger. The best
$16$-round differential characteristic has probability $2^{-21.23}$,
against $2^{-61.97}$ for DES, and a two-stage attack recovers the $56$-bit
key in minutes. In BEA-1 the trapdoor opens no useful trail. However, for
every key both ciphers act as an exact smaller cipher on the cosets, and
fall to known-plaintext distinguishers from about $2^{16.5}$ and
$2^{20.5}$ texts. An independent MILP model confirms every optimum it can
prove, and shows that single characteristics put the KG-DES boomerang at
$2^{-36.79}$ when it returns with probability $1$.
The answer to the second question depends on where the backdoor sits. Our
algorithm finds Paterson's trapdoor and BEA-1's four in the S-boxes that
carry them. Rijmen and Preneel's trapdoor needs unbalanced S-boxes, which
linear algebra exposes. LowMC-M's MALICIOUS backdoor sits in the linear
layers instead. With an ideal XOF a backdoored instance is distributed as
an honest one, so no test of the primitive finds it. Its holder recovered
the key from $35$ to $409$ queries in seven full-size measurements.
A deterministic trapdoor in the S-boxes therefore leaves a trace that a
sound algorithm finds. A trapdoor in unexplained linear layers leaves none,
and only constants derived verifiably from a public seed rule it out. We
recommend both as routine checks. Probabilistic trapdoors and trapdoors in
only some S-boxes remain open.
Fully Homomorphic Encryption for Small Batches of Complex Numbers
We propose a new approximate homomorphic encryption scheme to process small batches of complex numbers. Leveled operations are based on a new shaped rounding, whose error is a multiple of a fixed public ring element $g$, small on the data slots and larger on the others. The unused slots form a guard band that is computed on but never decoded, and the polynomial scaling factor $g^{-1}\Delta$ generalizes the CKKS scaling factor, with $g=1$ recovering CKKS. Guard-domain bounds determine the scaling factor needed for stability, while a norm bound limits the precision gain for a given guard amplification. A replicated layout uses a unit from a small cyclotomic subring to preserve shaping under admissible rotations and traces. We give a native bootstrapping algorithm whose forward transform reads only data slots, and conversions to and from CKKS with shared keys. Security reduces to Ring-LWE with the same parameters as CKKS. In poulpy, at ring degree $2^{15}$ and parameters targeting 128-bit security, bootstrapping a ciphertext holding 16 or 64 values restores 21 levels and retains at least 22.6 bits of minimum precision after 21 sequential products by fresh operands, while sparse CKKS supports only four levels at that degree and comparable precision. For these batch sizes, bootstrapping to restore 16 levels is about 5 times faster on one thread than sparse CKKS, which requires ring degree $2^{16}$.
Post-Quantum Sublinear Lookup Arguments from Polynomial Preprocessing
Lookup arguments with sublinear prover time typically rely on bilinear pairings. The only exception is the recent work of Campanelli, Carrillo, Cascudo, Fiore, Francati, and Gennaro (ePrint 2025/238); however, they rely on general-purpose SNARKs to certify expensive preprocessing, which requires non-black-box usage of cryptographic primitives. Thus practical realizations of sublinear lookups with post-quantum security remain challenging. We develop the first plausibly post-quantum sublinear lookup arguments that avoid general-purpose SNARKs via polynomial preprocessing and a novel adaptation of proximity testing for Reed-Muller codes into the Interactive Oracle Proof (IOP) framework.
Our starting point is a knowledge-sound polynomial commitment scheme (PCS) with prover-side preprocessing based on the Kedlaya-Umans framework. Rather than proving the expensive preprocessing computation inside a general-purpose SNARK, we directly certify its output using Reed-Muller proximity testing and an associated evaluation protocol. For polynomials of size $N$, our approach yields multivariate and univariate PCS with $N^{1+\epsilon}\mathsf{polylog}(N)$ preprocessing and only $\mathsf{polylog}(N)$ online prover time, while retaining $\mathsf{polylog}(N)$ proof size and verification.
We leverage this PCS to obtain a lookup argument for \textit{static} tables of size $N$ and $k\ll N$ lookups with $k\cdot\mathsf{polylog}(N)$ online prover time and $\mathsf{polylog}(N)$ verification and proof size. We further extend the approach to \textit{updatable} tables, obtaining $O(k(N^\epsilon+\mathsf{polylog}(N)))$ amortized prover time for a $k$-sized batch of reads and writes, where $\epsilon \in (0,1)$. We retain $\mathsf{polylog}(N)$ proof size and verification. The IOPs underlying our lookup arguments satisfy round-by-round (knowledge) soundness, which can be compiled into plausibly post-quantum arguments in the (quantum) random oracle model with transparent setup.
Table-Free Constant-Work BCH Decoding by Algebraic Index Elimination
Algebraic error-correcting codes such as BCH let lattice-based key encapsulation mechanisms (KEMs) reduce bandwidth and the decryption-failure rate. The decoder’s input is determined jointly by the long-term secret and a ciphertext that an adversary may choose. Variable work or table accesses that reveal error positions can enable key recovery even when the KEM uses implicit rejection. Walters and Sinha Roy (WSR) gave a constant-work BCH decoder whose fixed-address realization scans the entire field per protected lookup.
We introduce algebraic index elimination, a table-free realization of WSR’s paired Berlekamp–Massey schedule in which received-word-dependent selections become fixed circuits over public addresses. We prove bounded-distance correctness through radius t and source-level trace regularity for the parameterized decoder. We instantiate the construction with length-511 subcodes of dimension k , using ( k,t ) = (384 , 14) and (320 , 22). Their implementations eliminate, respectively, 5.2 and 7.2 KiB of received-word-selected field and encoder tables required by matched fixed-address WSR baselines. On WSR’s published parameter sets, an Intel i7-13700 runs the deterministic cores 35.7–82.4 × faster than the fixed-address WSR baselines. In the identity-based lattice KEMs ANSA-IBKEM1 and ANSA-IBKEM2, decapsulation is 25.5 × and 10.9 × faster than with fixed-address WSR baselines for the same 384-dimensional subcode. Index elimination does not equalize operands. Ordinary C masks compiled to received-word-dependent branches under Apple Clang 21; a compiler-opaque primitive prevented this transformation in the audited builds. At the measured radii, scalar binaries of both codes pass the x86-64, Cortex-A76 and Cortex-M4 mean-timing screens, and the Apple M5 screens with Data Independent Timing (DIT) enabled.
Active and Passive Attacks against TPM 2.0-based Full Disk Encryption
Trusted Platform Module (TPM) 2.0-based full-disk encryption (FDE) has gained renewed importance with the rise of bring-your-own-device environments. Aside from Windows Bitlocker, which uses the TPM since the days of Windows Vista, FDE has also been recently adopted by several Linux distributions. We revisit tamper attacks against TPM 2.0-based FDE systems and analyze the security of current Windows and Linux implementations. We examine TPM 2.0 sealing mechanisms and demonstrate passive and active attacks against systems using discrete TPMs (dTPMs) connected via SPI, using a mini PC and a notebook platform as case studies. While dTPMs are highly tamper-resistant, they remain vulnerable to attacks on the communication bus. We further show that active attacks are not limited to dTPM bus interception but can also affect firmware TPMs (fTPMs). Specifically, we present a prototype attack in a virtualized QEMU environment targeting UEFI firmware rather than bus communication, impacting both Windows and modern Linux systems. These attacks enable us to break not only BitLocker-based full-disk encryption on Windows, but also all current Linux implementations, including those that utilize parameter encryption to secure the bus communication. Our findings expose weaknesses in current TPM 2.0 FDE implementations and motivate stronger specification-level protections.
Back to the Bits: Revisiting MAYO’s Data Representation for GPU and Tensor-Core Acceleration
MAYO, a multivariate quadratic signature scheme with small public keys and signatures, is a third-round candidate in the additional signature standardization process of the National Institute of Standards and Technology. Cloud and application servers receiving many independent signing requests need to batch them on Graphics Processing Units (GPUs). MAYO's nibble-sliced representation suits CPU shuffle instructions or multiplication tables, but on GPUs it costs a memory access or several instructions per $\mathbb{F}_{16}$ multiplication. The existing GPU implementation cuMAYO (CHES 2026) uses the second-round nibble-sliced representation and looks up a shared-memory table per $\mathbb{F}_{16}$ multiplication. Our GPU implementation keeps all keys and intermediate values in the bitsliced representation yet matches the official Known Answer Test vectors. Its bitsliced multiply-accumulate circuit computes matrix products $32$ coefficients at a time with only word-wide AND and XOR. One thread block handles one instance; KeyGen, Sign, and Verify each run as a single kernel from the expansion of the compact key to the output; and representation conversion is confined to reading and writing specification-defined byte strings. For same-key batches, an additional tensor path decomposes $\mathbb{F}_{16}$ matrix products into binary ones and computes the large Sign and Verify matrix products on Tensor Cores. To our knowledge, the tensor path is the first use of Tensor Cores for MAYO, and ours is the first GPU implementation of the third-round specification. On an RTX 4090, the bitsliced implementation achieves $2.75\times$ to $6.73\times$ higher throughput and $6.99\times$ to $34.35\times$ lower single-shot latency than cuMAYO for all three operations of the four parameter sets. In same-key batches, the tensor path, including key preparation, reaches $13.75\times$ to $30.62\times$ the throughput of cuMAYO on distinct-key batches.
Reverse Engineering IVXV: A Specification and Security Analysis of Estonia’s Internet Voting System
Estonia’s IVXV system is one of the world’s longest-running and largest-scale deployments of internet voting, yet it lacks a precise public specification of the protocol as implemented or security claims, which has left it difficult to audit independently. We address this as follows:
First, we reverse engineer a detailed specification of IVXV as implemented—covering the setup, voting, tallying, and audit phases—comprising protocol-flow diagrams, pseudocode algorithms, and the core data structures, reconstructed from the public source code, official documentation, and configuration examples.
Second, we complement the specification with an executable TLA+ model of the setup, voting, and tally phases, which we check with TLC for basic executability and correctness and
which serves as an extensible basis for modelling concrete attack scenarios.
Third, using the reconstructed specification, we carry out a systematic security analysis under a broad range of threat models spanning individual verifiability, universal verifiability,
privacy, coercion resistance, and eligibility verifiability, and we reassess previously known attacks against the current protocol.
Fourth, we compare IVXV against two of the most extensively studied deployed systems, Belenios and Swiss Post, across these properties in order to situate its guarantees.
Fifth, we discover numerous previously unknown, vulnerabilities—spanning ballot privacy, individual verifiability, and universal verifiability, many of them arising from inconsistent validation logic across components, encoding discrepancies, and unchecked cryptographic parameters—and validate selected findings with proof-of-concept tests that exercise the real implementation.
Finally, we propose concrete mitigations for the attacks we identify.
Broadcast and Trace from Lattices: Collusion-Resistant and Publicly Traceable
A broadcast and trace scheme combines broadcast encryption with accountability. Specifically, broadcast encryption is augmented with an algorithm for tracing traitors within a specified set, even if the given pirate decoder is created by an arbitrary collusion of users. As in broadcast encryption, the size of the ciphertext should be sublinear in the total number of users $N$.
In this work, we generically construct collusion-resistant broadcast and trace that supports public tracing from attribute-based encryption with succinct ciphertexts and lockable obfuscation, both of which are known from the decomposed LWE assumption. Our scheme has ciphertext size $\sqrt{N}\cdot\mathsf{poly}(\lambda, \log N)$, while the master public key and secret keys have size $\mathsf{poly}(\lambda, \log N)$. Previously, collusion-resistant broadcast and trace with public tracing required pairing-based assumptions, positional witness encryption, or indistinguishability obfuscation. In particular, we provide the first construction that relies on a simple and instance-independent lattice assumption.
At the heart of our construction is a novel way to use nested lockable obfuscations, taking inspiration from the recent work of Nassar, Waters, and Wu that constructs positional witness encryption from indistinguishability obfuscation for null programs.