Papers updated in last 183 days (Page 7 of 2708 results)
Designated-Verifier Dynamic zk-SNARKs with Applications to Dynamic Proofs of Index
Recently, the notion of dynamic zk-SNARKs was introduced. A dynamic zk-SNARK augments a standard zk-SNARK with an efficient update algorithm. Given a valid source statement-witness pair $(x,w)$ together with a verifying proof $p$, and a valid target statement-witness pair $(x',w')$, the update algorithm outputs a verifying proof $p'$ for $(x',w')$. Crucially, $p'$ is not recomputed from scratch; instead, the update algorithm takes time roughly proportional to the Hamming distance between $(x,w)$ and $(x',w')$, analogous to how dynamic data structures update the result of a computation after a small change.
In this paper, we initiate the study of designated-verifier dynamic zk-SNARKs: dynamic zk-SNARKs in which only a designated verifier, holding secret verification state, can be convinced by a proof. Following recent advances in designated-verifier zk-SNARKs---such as efficient post-quantum designated verifier SNARKs (CCS 2021) and designated verifier SNARKs with very small proofs (CRYPTO 2025)---we construct a designated-verifier dynamic zk-SNARK with $O(\log n)$ update time, constant proof size, and concrete efficiency. Our construction significantly outperforms Dynalog (both asymptotically and concretely), the only publicly verifiable dynamic zk-SNARK with polylogarithmic update time (Wang et al., 2024).
The concrete efficiency of our construction enables, for the first time, an efficient implementation of a dynamic proof of index: Given a digest $d$ of an arbitrary set and a digest $d'$ of its sorted index (e.g., binary search tree), we produce a SNARK proof certifying the consistency of $d$ and $d'$. More importantly, this proof can be updated in sublinear time when the underlying set changes---for example, when an element is modified or inserted, potentially altering the sorted order. We demonstrate applications of designated-verifier dynamic proofs of index to verifiable dynamic database outsourcing, where a client outsources a database and later maintains verifiable indices for efficient query answering, even under arbitrary database updates.
Efficient Two-Dimensional Representation Evaluation via Dual Isogenies with Applications to Isogeny-Based Cryptography
The evaluation of two-dimensional isogeny representations is a fundamental operation in many isogeny-based cryptographic schemes, notably the public-key encryption schemes POK\'{E} (Eurocrypt 2025) and PIKE (PKC 2026), as well as the digital signature schemes SQIsign2D-West (Asiacrypt 2024) and SQIsign2DPush (Eurocrypt 2026). However, existing two-dimensional evaluation algorithms rely on time-consuming discrete logarithm computations and torsion-basis generation, creating a severe performance bottleneck for the entire protocol.
In this paper, we propose a novel algorithm for evaluating two-dimensional representations by leveraging the properties of dual isogenies, thereby eliminating the need for costly discrete logarithms. We apply this methodology to significantly accelerate some isogeny-based protocols, including POK\'{E}, SQIsign2D, and their variants.
We provide optimized C implementations for the speed-optimized variants of POK\'{E} and SQIsign2D using our proposed method. Experimental benchmarks demonstrate that the fast variants of POK\'{E} combined with our new techniques achieve computational speedups of up to $3.47\times$ in terms of CPU clock cycles compared to POK\'{E} at the NIST-I security level.
Additionally, our explicit analysis and implementation results confirm that the signing phase of SQIsign2DPush (resp. the NIST post-quantum cryptography standardization candidate SQIsign-v3.0), when using our method, achieves a performance improvement of up to $11.24\%$ (resp. $5.02$\%) across the three NIST security levels.
When Can We Incrementally Prove Computations of Arbitrary Depth?
Incrementally Verifiable Computation (IVC) allows one to prove the correctness of a computation of potentially unbounded length (or, depth) in an incremental way, while a computationally weak client can efficiently check its correctness in time sublinear in the computation's length. IVC are of practical relevance; yet, most existing IVC schemes are only provably secure for constant-depth computations. Arguing their security for computations of polynomial depth relies on heuristic assumptions, raising both theoretical and practical concerns. More generally, it remains unclear whether these schemes are genuinely insecure at superconstant depths or whether our current proof techniques are simply insufficient.
In this work, we delve into the security foundations of incremental proof systems, while at the same time looking for new approaches to prove security at superconstant depths. To this end, we study the relation between the depth of the target computation and IVC security as a question in its own right. Specifically, we ask:
- Can we prove an IVC secure at depth $d =\omega(1)$ if it satisfies a "weak" security property at some "larger" depth $D$?
We uncover a surprising connection between infinitely-often soundness (guaranteed to hold only for some infinite set of parameters) and standard soundness in IVC: a scheme that is infinitely-often sound at $D$ depth achieves standard soundness at some "smaller" depth $d=o(D)$.
- How does a proof system's security degrade with depth?
More precisely, if a scheme loses negligible soundness beyond (e.g.) $O(1)$ depth—the current provable frontier of most practical schemes—can we at least achieve noticeable (but arbitrarily low) soundness for some superconstant depth? We show the answer is negative.
- Depth boosting: If there exists an IVC scheme secure at depth $d$, does there exist one secure at a "greater" depth?
We show a simple and black-box boosting technique: given an IVC secure at depth $d$, we can construct one secure at depth $D = d^\rho$ for any function $\rho$ such that $d^\rho$ is polynomially bounded ($\rho$ can even be superconstant). This allows us to systematically amplify security from modest depths to much greater ones (e.g., constant to polynomial depth, with only a logarithmic overhead).
Our results uncover a nuanced landscape of depth, efficiency, and security in IVC, and new strategies to prove security beyond $O(1)$ depth. They also apply to non-deterministic computations and other soundness notions, including incremental functional commitments (IFC), a streaming variant of functional commitments that we introduce.
Cryptanalysis of ‘Quantum public key encryption scheme with four states key’
Liu et al. (2022 Phys. Scr. 97 045102) propose a quantum public key encryption scheme in which a qubit message is encrypted by a controlled-NOT gate driven by a four-state public key, followed by measurement of the message register, and claim information-theoretic security. I show that the encryption map reduces exactly to \( |M\rangle \mapsto R_{\theta}X^{m}|M\rangle \), where the outcome \(m\) is published. \(R_{\theta}\) is diagonal and the ciphertext reproduces the computational-basis distribution \((|\alpha|^2,|\beta|^2)\) of the plaintext, while the plaintexts \(|0\rangle\) and \(|1\rangle\) are perfectly distinguishable. The claim of information-theoretic security is therefore invalid.
ZKPoSP: Post-Quantum Zero-Knowledge Proofs for Hierarchical Deterministic Wallets
In the blockchain setting, where key derivation standards such as BIP32, BIP44, and SLIP-10 are the dominant infrastructure for wallet management, a quantum computer running Shor's algorithm can recover any elliptic-curve private key from the corresponding public key, threatening every wallet in production today. Migrating to post-quantum signature schemes requires changing the public key format and forcing address migration across all participating networks. We present an orthogonal approach: keep the existing address format unchanged and replace the classical signing step with a NIZK proof of knowledge of the seed underlying the address (or of the private data of a hardened ancestor), where no step of the security argument relies on the discrete logarithm problem. We prove security against quantum adversaries in the quantum random oracle model, under an explicit assumption on the zero-knowledge and simulation extractability of the NIZK.
We build on the observation of Baldimtsi et al.\ that EdDSA's deterministic seed-to-key mapping makes the seed a valid zero-knowledge witness for the public key, and extend their result to hierarchical deterministic wallets. Our main contribution is ZKPoSP (Zero-Knowledge Proof of Seed Provenance), a signature scheme that splits the proof into a derivation proof generated once per key pair and a signing proof generated once per message, so that the per-message proving cost does not depend on the derivation depth. We also introduce QBIP32, a key derivation scheme based on a keyed function HASH768 (instantiated with KMAC256) that produces the signing scalar, an explicit witness, and the chain code in a single call at hardened steps, for any elliptic curve group of prime order. As last contributioun we notice that after Q-day, once networks reject all non-post-quantum signatures, the signing scalars can be moved to the public statement reducing derivation proving time.
On Module Lattices with Galois-Symmetries: What You See Is Not What You Get
This paper deals with the hardness of finding short vectors in module lattices. Let $K$ be a number field of degree $d$ and $\mathcal{O}_K$ its ring of integers. We show that if a module lattice $M$ of rank $n$ in $\mathcal{O}_K^n$ has some Galois-symmetries, namely if it is fixed coordinate-wise (as a set) by a group $G$ of automorphisms of $K$, then $M$ can actually be seen as a module of rank~$n$ over a subfield~$K'$ of $K$ ($K'$ is the fixed-field of $G$), whose degree is $|G|$ times smaller than the degree of $K$. When one wants to find short vectors in $M$, this translates into the observation that the module lattice $M$, which is a priori a lattice of rank $n d$ can in fact be seen as a lattice of rank only $n d / |G|$. Hence, finding short vectors in $M$ is easier than what one could have expected by forgetting about the algebraic structure of $M$. This result is a generalization of a similar result by Boudgoust, Gachon and Pellet-Mary (Crypto'22), which was restricted to ideal lattices (i.e., modules of rank $1$).
Byzantine Broadcast in $\widetilde{O}(n^2)$ Communication
We present a deterministic $n$-party Byzantine broadcast protocol secure against $t<n$ faults, with communication complexity $O(n^2\log^4(n)\lambda)$ and $O(t)$ rounds (where $\lambda$ is a security parameter), improving upon the seminal Dolev--Strong protocol from 1983.
Shorter Hash-Based Signatures via Guarded Sharing in a DAG Model
Stateless hash-based signatures are among the most important post-quantum signature schemes. Although they have been standardized by NIST, they still have large signatures. Within these constructions, the few-time signature component is receiving increasing attention. Recent work has introduced new techniques, including rejection sampling, forced pruning, bucket thinning, and hash chains.
In this work, we continue to improve few-time signatures with a new technique, guarded sharing. Our construction moves beyond the previous tree-based model to a DAG-based signature. By combining guarded sharing with bucket thinning, hash chains, and rejection sampling, we obtain a new signature scheme called BGS-CC.
Our construction further improves on the state-of-the-art few-time signature BPORS-C+BFP. Most notably, for 128-bit security and a small use quota of $Q=2^{24}$, it yields complete signatures of 2,228 bytes. To our knowledge, this is the first SPHINCS-based stateless signature to be shorter than the 2,420-byte signatures of the standardized module-lattice scheme ML-DSA-44.
Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials
We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. This achieves a superpolynomial improvement in communication when $s \geq 4$; previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, namely the generalized repunit conjecture and Schinzel's hypothesis H (either one of these conjectures would suffice alone).
Our result builds on the "matching vector family + $S$-decoding polynomials" framework pioneered by Efremenko (STOC 2009) and recently refined by Ghasemi, Kopparty, and Sudan (STOC 2025). The main ingredient is a framework for constructing $S$-decoding polynomials with only $k+1$ nonzero coefficients modulo special products of $k$ primes, resolving an open problem posed by Ghasemi and Kopparty (ITCS 2026). By the lower bound shown by Ghasemi and Kopparty, this is the minimum achievable sparsity. We also empirically validate our construction and make our result unconditional for all $s \leq 15$.
We also apply our techniques to regimes where $s$ grows with $n$, showing under a stronger variant of our number-theoretic conjecture that the communication complexity of $s$-server matching-vector PIR can be superpolynomially reduced from the previous state of the art for any $s \leq \exp(o(\sqrt{\log \log n/\log \log \log n}))$.
The main result for $s = O(1)$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.
Aerie: Efficient Aggregation of Falcon Signatures
The post-quantum signatures selected by NIST are ten to over a hundred times larger than the elliptic-curve signatures they replace. Moreover, unlike the BLS signatures that blockchains use to aggregate validator votes, they do not aggregate natively. Both problems can be addressed with a SNARK: a short proof that a batch of signatures is valid, replacing the signatures themselves.
The prevailing approach, central to Ethereum's roadmap, pairs hash-based signatures with hash-based SNARKs. This is slow because the prover must prove many hash evaluations per signature. We instead aggregate lattice-based signatures with a lattice-based SNARK.
We present Aerie, a proof system for aggregating Falcon-512 and Falcon-1024 signatures. By retaining each signature's short random salt in the aggregate, Aerie lets the verifier compute the hashes directly. The proof then covers only algebraic and norm checks. Aerie combines protocols tailored to these checks with the Akita polynomial commitment scheme. Unlike prior Falcon aggregation schemes, it also proves that the signatures satisfy Falcon's byte-format requirements.
On an Apple M4 Max laptop without GPU acceleration, Aerie aggregates 32,768 Falcon-512 signatures, roughly the number of validator votes in one Ethereum slot, in 0.65 seconds. A single proof covers the whole batch, with no recursion. The aggregate is 42.1 bytes per signature including the salts, or about 66 KiB in total if the signatures share one salt. It verifies in 54 milliseconds on one core, 10× faster than checking the signatures individually. On one core, proving takes only about 8× as long as individual verification. We prove knowledge soundness of Aerie in the classical random-oracle model and derive aggregate unforgeability from Falcon's security.
Fuzzy Private Set Intersection under Density-Bounded Assumptions
This paper presents a new fuzzy private set intersection (FPSI) protocol, a two-party protocol to securely identify similar items across private sets. Our design departs from the prevailing separation-based paradigm---e.g., ``apart by $2\delta$'' or the disjoint projection assumption---which either incurs exponential overhead in dimensionality or requires high dimensionality to justify the assumption. Instead, we address this tension by explicitly allowing collisions within $\delta$-balls, but requiring that their multiplicity be bounded per axis. We formalize this new structural property as $C$-max collision. We theoretically analyze its plausibility on several common distributions, e.g., the uniform distribution, and real datasets, and provide an efficient algorithm to verify this assumption.
Under the $C$-max collision property, we propose an efficient FPSI protocol for $\ell_{\infty}$ distance that supports both low- and high-dimensional regimes. Our construction is based on a novel abstraction that views FPSI as an oblivious intersection of membership tags, which natively handles axis-wise matching multiplicity. We capture its requirements through a new functionality called oblivious selected set intersection, along with its instantiation based on symmetric key techniques. Assuming the $C$-max collision property on the receiver's set, our protocol achieves computation/communication complexities scaling linearly with both parties' set sizes for a fixed $C$. We implement our protocol and conduct extensive evaluation. While a direct comparison is infeasible, ours achieves online efficiency comparable to state-of-the-art separation-based FPSI protocols in both low- and high-dimensional regimes.
Akita: A High-Performance Lattice-Based Polynomial Commitment Scheme
Lattice-based polynomial commitment schemes (PCSs) promise post-quantum SNARKs with two properties that elliptic curves provide and hash-based schemes, today's deployed post-quantum default, do not: concretely small proofs and commitment time proportional to the number of nonzero entries in the committed polynomial rather than its length. The second property is essential to Twist and Shout (CRYPTO 2026), the fastest known memory-checking arguments and a core component of the Jolt zero-knowledge virtual machine (zkVM): their prover commits to enormous polynomials that are almost entirely zero. Yet despite a wave of recent work, existing lattice-based PCSs achieve at most two of the three properties that deployment demands: small proof size, fast verification, and soundness from standard assumptions such as Module-SIS.
We present Akita, a lattice-based PCS that achieves all three. We improve on the square-root-time verifier of Hachi (ePrint 2026), our direct predecessor, through a new setup offloading technique: the public setup matrices are committed ahead of time, and the verifier's work in processing them is deferred and proved against these commitments. For any fixed $K\ge2$, this reduces verification time to $\widetilde O_{K,\lambda}(N^{1/K})$ while preserving $\widetilde O_{K,\lambda}(\log N)$ proof size, $\widetilde O_{K,\lambda}(N)$ prover time, and security from standard Module-SIS. We also optimize every fold from root to tail and iterate the fold to completion. This includes an optimized digit range check, relation-specific ring dimensions and subring challenges, complementary methods for embedding field evaluations and checking ring relations, commitments compressed to $128$ bytes each, and exact Euclidean norm checks for tighter Module-SIS parameters.
Beyond the core protocol, Akita provides the capabilities needed for deployment in a zkVM: batched openings of separately committed polynomials, low-communication distributed proving, and an offline planner for selecting secure parameters under configurable cost objectives. We implement Akita in Rust and benchmark it against existing lattice-based and hash-based PCSs. Across these benchmarks, Akita produces proofs of only $58$–$68$ KB, matching Greyhound's when both schemes are calibrated to the same lattice-security target, while verifying $22.1\times$ to $108.7\times$ faster. Akita's prover uses the least memory: beyond storing the polynomial itself, its memory overhead grows sublinearly in the polynomial size. We also integrate Akita into Jolt. For every program size we evaluate, Jolt-with-Akita achieves a $2.2\times$ to $4.2\times$ prover speedup and $2.8\times$ to $8.5\times$ verifier speedup over Jolt-with-Dory, while producing comparable proof sizes, with every proof below $100$ KB.
GhostFaceMPC: Privacy-Preserving Face Recognition with Multi-Party Computation
Facial recognition has become central to modern authentication systems, security frameworks, and personalized services. However, its widespread adoption is hindered by severe privacy risks, particularly surrounding unauthorized access to sensitive biometric data. To address these challenges, this paper presents GhostFaceMPC, the first end-to-end, privacy-preserving face recognition system to evaluate a deep convolutional neural network extractor and matching under secure multi-party computation. GhostFaceMPC enables secure processing of facial data across all stages of a face recognition process, from feature extraction and storage to matching, without exposing raw images or biometric embeddings at any stage.
We introduce a multi-party computation-friendly quantization of the GhostFaceNet model and circuit optimizations that make face recognition under multi-party computation practical. The code is available at https://github.com/crypto-unict/GhostFaceMPC.
Noise-Tolerant Quantum One-Time Programs Using Stateless Trusted Hardware, Revisited
A quantum one-time program scheme is a functionality-preserving compiler that transforms a program into a quantum state that can be used to obtain only one output of the program. Our goal is to design quantum one-time programs that can be realized on existing quantum technologies. Our contributions are two-fold:
1. We design a BB84 state-based quantum one-time program scheme in the stateless trusted hardware model that is resilient to single-qubit corruption errors and detectable erasure errors. To illustrate, under independent noise with a 90% detectable erasure rate and a 3% Pauli Y-error rate on surviving qubits, a signature token of 39,801 BB84 qubits achieves forging probability at most $\small 2^{-128}$ against at most $\small 2^{32}$ classical verification queries, with honest failure probability below $\small 10^{-6}$. Prior to our work, [Behera, Sattath, and Shinar TQC'22] studied a BB84 state-based quantum one-time program scheme resilient to independent single-qubit corruption errors; our construction treats detectable erasures separately.
2. We give two extensions to our scheme. First, we study the setting wherein the same trusted hardware can be reused across different independently generated quantum one-time programs. Second, we study the setting wherein multiple trusted hardware devices are used and the security holds as long as at least one of them is not compromised.
Knuth–Yao masked (Gaussian) sampling
Discrete Gaussian sampling remains one of the most delicate operations to protect against side-channel attacks in lattice-based cryptography. In this work, we present the first masked evaluation of the Knuth-Yao sampler, a generic building block for lattice-based schemes. Its random-walk formulation might seem fundamentally at odds with masking, since the walk's control flow depends precisely on the secret sample being produced. We show instead that its underlying tree structure is remarkably suited to it. Evaluated as a bitsliced Boolean circuit, the public tree prescribes an evaluation order requiring exactly L - 2 masked AND gadgets, where L is the total Hamming weight of the probability expansions of the target distribution. This makes the approach particularly effective for the narrow distributions used in lattice-based schemes. We provide a generic framework that compiles any finite-precision distribution into a masked C implementation with optimized linear-gate count. We use FrodoKEM and HAWK as case studies, and also compile the base samplers of Falcon and HAETAE. On ARM Cortex-M4, our sampler outperforms the state-of-the-art masked CDT approach for every distribution at masking orders 1 to 5, running up to 2.3 times as fast at order 1, even for distributions where it evaluates more non-linear gates. Finally, since the Fujisaki-Okamoto transform ties FrodoKEM to the exact randomness consumption of its specified sampler, we discuss the consequences of this constraint. We benchmarked an unmasked implementation and argue that the Knuth-Yao approach is competitive even without masking, while using identical input randomness.
SecAgg++: A Post-Quantum Privacy Preserving Federated Learning Protocol
Secure aggregation is a fundamental building block for privacy-preserving federated learning, yet most existing masking-based secure aggregation protocols do not provide post-quantum security. In this work, we present SecAgg++, a masking-based post-quantum secure aggregation protocol for the single-server setting. SecAgg++ integrates post-quantum cryptographic primitives while preserving the communication and computational efficiency of classical frameworks such as SecAgg and SecAgg+, and supports client dropout handling through an efficient recovery procedure.
Magnetar: High-speed post-quantum RV64 zkVM from standard hashes
We describe the design, implementation, and experimental evaluation of Magnetar, a transparent proof system for RV64I program executions (i.e., a zkVM). Magnetar is the first zkVM to simultaneously satisfy the following three properties:
1. General-purpose proving. Magnetar proves programs compiled to the general-purpose RV64I ISA. An implementation of the Ethereum Virtual Machine (EVM) written in Rust or Go can therefore run inside Magnetar, yielding a zkEVM for proving executions of existing EVM smart contracts.
2. Hash-based, post-quantum security. Magnetar’s cryptographic security is rooted in standard hash functions (e.g., SHA-256 or SHA-3).
3. Efficient recursion. Magnetar’s verification work is dominated by evaluating standard hash functions. Magnetar’s proof engine, BinarySpartan, is well-suited for such bit-oriented computations, so verifying a proof is itself an efficient proving workload.
Unlike prior general-purpose zkVMs, Magnetar does not rely on circuit-friendly algebraic hash functions such as Poseidon or Poseidon2, elliptic-curve or lattice assumptions, or a conjectured Reed–Solomon proximity gap. Even prior zkVMs commonly described as hash-based rely on elliptic-curve or lattice assumptions in their core proving machinery, provide only about 100 bits of security, or rest on conjectured soundness; some do more than one of these.
Finally, we implement Magnetar in Rust and experimentally evaluate it. We find that, at 120 bits of provable security and with 12 performance cores on an M4 Max MacBook Pro, Magnetar proves 2^{22}-cycle executions at 7.2–8.7 million cycles per second, with proofs of about 600 KiB that verify in 11–13 ms. Across 15 application workloads, Magnetar’s proving throughput is 24–66× that of SP1 Hypercube, a hash-and-more-based zkVM; 12–37× that of Jolt-Dory, a curve-based zkVM; and 6–20× that of Jolt-Akita, a lattice-based zkVM, with geometric-mean speedups of about 39×, 18×, and 9.6×, respectively. An optimized Magnetar proves 222-cycle executions at 9.5–12.8 million cycles per second, which increases each geometric-mean speedup by about 1.3×. Magnetar’s proofs are about 4.6× smaller than SP1 Hypercube’s; Jolt’s proofs are under 100 KiB, but they rely on elliptic-curve or lattice assumptions.
Cryptanalysis of Full BEANIE
Beanie is a tweakable block cipher recently published at ToSC aiming for memory encryption of microcontroller units. In line with this goal, it handles small plaintexts of only 32 bits and has a low latency.
In this paper, we propose the first third-party analysis of the two variants of Beanie. By carefully leveraging structural properties of the cipher and taking advantage of its distinctive attack model, we manage to mount several key-recovery attacks against both the 5+5-round version and the 7+7-round version.
New infinite families of APN functions from the switching construction in even dimension
We present the first new infinite family of APN functions obtained by applying the switching construction to a known family since the introduction of the Budaghyan-Carlet-Leander family in 2009. Our construction is also the first example of an infinite APN family obtained via the switching construction from an infinite family of non-power functions. More generally, we study families of APN functions that can be obtained from the Budaghyan-Helleseth-Kaleyski family by the addition of carefully selected perturbation terms. We perturb the known family by combinations of Frobenius conjugates of the relative norm and obtain four constructions, naturally arranged into two switching pairs. One of these families is EA-equivalent to the Li-Zhou-Li-Qu family, for which our construction yields a new univariate representation. Switching it by a norm-derived Boolean term produces a second family that we prove to be APN in every dimension where the base family is defined, and we show that this family is CCZ-inequivalent to all previously known constructions. Furthermore, we investigate two other infinite families that can be switched to one another, conjecture that they are APN for infinitely many dimensions, and obtain conditions that can be used to characterize their APN-ness. The new infinite APN family and the two conjectured APN families generalize previously known sporadic APN instances in dimension 10.
A zk-SNARK Programming Framework for Verifiable Data Analytics
zk-SNARKs enable succinct, efficiently verifiable proofs of correct computation
over private data, but require the computation to be compiled into a
\emph{statically defined and bounded} arithmetic circuit. This requirement
creates a multidimensional mismatch with data-analytic programming, which
consists largely of array programs: (a)~array operations and resulting shapes
are dynamic; (b)~arrays are accessed at data-dependent positions; (c)~control
flows are data-dependent. Existing zk-SNARK DSLs enforce this requirement using
conservative syntactic restrictions that reject many bounded programs, or leave
the programmer to bound and encode these by hand, while zkVMs recover
expressiveness at substantially higher proving cost.
We present \textsc{Zinnia}, a zk-SNARK programming framework for analytics in
which programs are written in a subset of Python with NumPy. Zinnia's compiler
uses SMT-backed symbolic execution over array types with bounds to derive
properties of the program's values that hold on every input, which we call
\emph{facts}. The facts bound every data-dependent shape and loop, which gives
each array its capacity in the circuit. Built atop this compiler,
\textsc{Zinnia} provides bounded-dynamic array and arithmetic operations for
analytics. The same facts guide how these operators are lowered: for each
operator, \textsc{Zinnia} considers known circuit constructions, whose cost
depends on what the facts guarantee. Unlike a program, a circuit has no order in
which a check protects later uses, so if a construction needs a fact, another
constraint in the circuit must enforce it. A construction chosen for one
operator may enforce a fact that another relies on. \textsc{Zinnia} therefore
chooses the constructions of all operators together, seeking to minimize
estimated circuit cost. Our evaluation on unmodified programs from three NumPy
corpora shows that the circuits \textsc{Zinnia} compiles are never larger than
optimized hand-written ones in existing DSLs, and that \textsc{Zinnia} achieves
over $30\times$ faster proving than zkVM-based approaches by geometric mean.
LaMS: A p-adic Layered Modulus Switching for Provable Dual Attacks on LWE
The Learning with Errors (LWE) problem is a central foundation for post-quantum schemes such as Kyber and Dilithium. Dual attacks are among the main tools for assessing the concrete hardness of LWE instances. At EUROCRYPT 2024, Pouly and Shen introduced the first provable dual attack against LWE. Subsequently, at ASIACRYPT 2025, Qu and Xu incorporated modulus switching into this framework by recovering the guessed secret mod several small primes and recombining the resulting residues via the Chinese Remainder Theorem (CRT). Although this CRT-based strategy substantially reduces the search space, it reconstructs the full guessed secret through several distinct primes whose product must exceed \(q\). Consequently, the total guessing cost is dominated by the largest CRT prime \(p_k\). This raises a natural question: can the same recovery effect be achieved by repeatedly applying the subroutine with a fixed small prime, while further reducing the overall complexity?
We answer this question affirmatively by proposing layered modulus switching (LaMS), a provable modulus switching dual attack based on a \(p\)-adic view of the guessed secret. Instead of recovering residues mod several distinct primes, LaMS fixes a single small prime \(p\) and recovers the guessed secret digit by digit in its \(p\)-adic expansion. After each digit is recovered, its contribution is subtracted from the LWE samples, producing a new target LWE instance in which the next digit becomes the new secret mod \(p\). As a result, the guessing cost is reduced from \(O(\mathrm{poly}(m,n)(N+\sum_{j=1}^{k}p_j^{n_{\mathrm{guess}}}))\) in the CRT-based attack to \(O(\mathrm{poly}(m,n)\lceil\log_p q\rceil(N+p^{n_{\mathrm{guess}}}))\), where \(p \ll p_k\).
We also correct a parameter issue in two previous works (EUROCRYPT 2024 and ASIACRYPT 2025) on Kyber estimates. After this correction, LaMS lowers the estimated attack cost by up to 1 bit for Kyber compared with the corrected CRT-based attack of Qu and Xu.
Structural Cryptanalysis of the Eevee AEAD Family
Eevee is a family of three AEAD modes, Umbreon, Jolteon, and Espeon, proposed at CCS 2023 for IoT-to-cloud secure computation. We analyze structural flaws in the algorithms of the supplied full-version specification and the proof steps underlying their online authenticated-encryption claims. An AD-free, two-encryption prefix distinguisher has advantage $1-2^{-n}$ in the ideal-forkcipher model, contradicting the specified online ideal object. Independently, the separable associated-data transform yields a four-encryption nonce-misuse distinguisher with advantage $1-2^{-n}$, a deterministic AD-only forgery, and nonempty-message forgeries obtained from cross-domain state differences. These attacks contradict the advertised nonce-misuse bounds of Umbreon and Espeon. With nonce-respecting encryption queries, one two-block Jolteon encryption permits a fresh one-block forgery with the same tag, while Espeon's short-message path permits arbitrary AD substitution. We trace these counterexamples to failures of online-prefix consistency, conditional transcript distributions, domain separation, and checksum freshness in the original proof. The authenticity attacks follow from deterministic identities, and the privacy counterexamples persist with an ideal forkcipher. We derive corresponding requirements for AD processing and message finalization, and briefly summarize supporting checks of the published C routines. The central failures concern the mode design and cannot be resolved solely by correcting implementation encodings.
Issuer-Independent Decentralized Exchange for E-Cash
Despite decades of cryptographic advances, electronic cash (e-cash) remains largely confined to payments and lacks the broader decentralized financial applications built around cryptocurrencies. As a step toward broadening its application layer, we present an issuer-independent e-cash exchange in which a liquidity provider holds inventories of two independently issued e-cash currencies and users trade between them without requiring either issuer to participate in individual swaps.
Our design combines a blockchain settlement layer, which automates the exchange and makes its execution publicly verifiable, with an exchange-compatible e-cash protocol. Classical e-cash must be adapted to this setting in two respects: payments must become publicly verifiable by the exchange, and the additional privacy risks created by public execution must be addressed. We formalize these new privacy requirements and construct a compact e-cash realization with publicly verifiable payments and aggregate anonymous reissue. We prove the security and privacy properties of the resulting exchange protocol under the stated cryptographic and issuer-functionality assumptions.
Speeding up Sumcheck using Algebraic Geometry
The sumcheck protocol, a ubiquitous component of modern proof-systems, enables proving the sum of evaluations of a low-degree multivariate polynomial. In theory, sumcheck has been generalized from polynomials to (tensors of) any multiplication code, a code whose pointwise products of codewords lie in a related product code. All practical systems nonetheless specifically use polynomials. For proof-systems over binary fields that target Boolean circuits, this choice has a real cost: the product of two binary messages under Reed--Solomon is no longer binary. As a result, the prover's work in the first, and most expensive, round of sumcheck (the so-called univariate skip) grows by a logarithmic factor.
We present a new concrete multiplication code based on algebraic geometry that is binary-preserving: the product of two encoded binary messages is again a binary message. Specifically, we construct an explicit multiplication code over $\mathbb{F}_{2^{128}}$ that carries $64$-bit messages to binary product messages of length $222$, and whose product code has relative distance greater than $1-2^{-119}$. The part of the product message that the prover actually sends in sumcheck is more than $3 \times$ smaller than with Reed--Solomon, as used in practice. The code comes from a genus-$95$ curve over $\mathbb{F}_2$ with $64$ rational points, built as a $(\mathbb{Z}/2)^3$ Artin--Schreier cover of a genus-$4$ curve.
We implemented the resulting protocol, which we call the AG skip, inside the Flock proof-system. For $2^{32}$ constraints, it speeds up the skip round by $2.36\times$ and the whole zerocheck, which was the prover's most expensive component, by $1.65\times$.
Robust ECDSA Threshold Signing at Scale
Uncategorized
Uncategorized
This work presents an efficient, scalable, and robust threshold ECDSA signing protocol for the $t\leq (n-1)/3$ scenario, making it suitable for e.g., bridging consensus from one Blockchain to another. Our construction allows to batch-compute pre-processing material for efficient online signing. While our protocol is based on established ideas for (Verifiable) Secret Sharing, we optimize it to scale efficiently both in terms of computation and communication with a large number of signers. We therefore combine efficient batching techniques for sharing (Fitzi & Hirt, PODC 2006), randomness extraction (Beerliova-Trubiniova & Hirt, TCC 2008) and share opening (Damgård & Nielsen, CRYPTO 2007) with recent advances in efficient Zero-Knowledge proofs (Attema & Cramer, CRYPTO 2020). We implement and evaluate the protocol experimentally and show that it is practical for large number of parties $n$.
Enhancing Capital Efficiency in DeFi Lending and Liquidity Provision
Decentralized Finance (DeFi) continues to experience rapid growth, yet a significant portion of capital remains inefficiently utilized in overprovisioned lending reserves or inactive liquidity positions. This paper presents two extension-based improvement proposals aimed at increasing capital efficiency in DeFi protocols. The first addresses idle capital in pool-based lending by adding an allocation layer that can deploy otherwise unused liquidity into external yield-generating strategies. The second targets inactive concentrated-liquidity positions through a position-management layer that automates range migration. Both proposals are examined in terms of motivation, mechanism design, expected effects, implementation approach, and practical limitations. Evaluation results are proposal-specific: the lending analysis indicates meaningful supplier-yield uplift under selected external-yield assumptions, while the range-migration analysis focuses on active-time sensitivity and execution cost. Prototype benchmarks suggest that both mechanisms can be implemented as modular extensions, but also expose additional gas overhead and proposal-specific risks, including external-strategy dependence, recall and loss-allocation concerns, and range-policy misconfiguration.
Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure
Shift-invariant permutations of \(\mathbb F_2^n\) are particularly attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of \(\mathbb F_2^n\) constructed from a recursively defined sequence of mappings \(\{\gamma_j\}_{j\ge 0}\) associated with landscapes. First, we prove that, under an explicit dimension condition relating \(n\) to the support of the landscape, the sequence \(\{\gamma_j\}_{j\ge 0}\) has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on \(\mathbb F_2^n\) with a nonzero special index. Then, we determine the eventual zero or periodic behavior of \(\{\gamma_j\}_{j\ge0}\), including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring \(\mathbb F_2[z]/\langle p(z)\rangle\), where \(p(z)\) is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.
Reaction Attack on CKKS Deployments with Asymptotically Optimal Query Complexity
We study a protocol-level reaction leakage in CKKS deployments where public coefficient-to-slot (C2S) evaluation keys are combined with a client's 1-bit validity response. Under this deployment surface, a malicious evaluator can recover a ternary secret key using asymptotically optimal $O(\mathcal{H})$ reaction queries, where $\mathcal{H}$ is the entropy of the secret key.
The attack does not break RLWE or CKKS IND-CPA security. Instead, it exploits the interaction between client-side validity reactions and public homomorphic linear transformations. A shift of a public encryption key yields a ciphertext whose plaintext is a function of the secret key; the public ${\sf C2S}$ layer then repacks this information to construct a ciphertext whose validity depends strictly on whether a targeted secret coefficient matches a guessed value. Furthermore, each submitted query is independently randomized with a fresh encryption of zero, so that each resulting malicious ciphertext appears entirely distinct, thereby allowing the attack to simply evade trivial detection mechanisms on the client side.
We implemented the full end-to-end attack in Lattigo v6.2.0 and recovered the full secret key across four parameter sets drawn from standard CKKS presets.
For uniform ternary secrets, the attack uses
$O(N)$ queries and is within a factor $2/\log_2 3 < 2$ of the oracle-only entropy lower bound. For sparse ternary secrets, a tailored variant further reduces the number of queries in practice. Our results show that observable validity reactions form a practical key-recovery channel in CKKS deployments exposing this surface, even when the underlying cryptographic assumptions remain intact.
Multi-key Fully Homomorphic Encryption with Non-Interactive Setup in the Plain Model
Multi-key fully homomorphic encryption (MKFHE) enables computation over encrypted data under multiple different keys. Constructing MKFHE without any trusted or interactive setup remains an open problem. In the context of MKFHE, a trusted setup is often assumed to mean the use of a common random string (CRS).
In this paper, we present the first MKFHE scheme in the plain model (i.e., without any trusted or interactive setup) based on the RLWE assumption. Specifically, we construct a multi-key somewhat homomorphic encryption based on the RLWE assumption and extend it to a multi-key variant of the Gentry-Sahai-Waters (GSW) scheme with a circular security assumption.
Our design yields a 2-round multi-party computation (MPC) in the plain model against semi-honest adversaries. Moreover, it can be applied to transform existing FHE schemes that rely on RGSW in their construction into a multi-key variant. We also provide concrete conversions for widely-used FHE schemes, including BGV, BFV, CKKS, FHEW, TFHE, and Carousel.
Finally, we implement our scheme and present experimental results for the expansion algorithm from a single-key ciphertext to a multi-key ciphertext and the multi-key homomorphic multiplication algorithm.
Trustless Bitcoin Vaults
Bitcoin (BTC) is the largest crypto asset, yet the Bitcoin blockchain offers few applications in which BTC can be used. A standard approach to make BTC useful is bridging: BTC is deposited on the Bitcoin chain and a wrapped asset is minted on a chain such as Ethereum, where it can be used in smart contract applications. Unfortunately, all Bitcoin bridges to date require trust assumptions on a centralized party or a committee running the bridge to enable withdrawals of the deposited BTC, including state-of-the-art BitVM bridges.
In this paper, we observe that while bridges are application-agnostic, most BTC holders are interested in collateral-based applications, where BTC is deposited as collateral, and only the depositor or a set of known counterparties can withdraw the asset. For this class of applications, we propose a primitive, Trustless Bitcoin Vaults, that guarantees that the BTC depositor or the counterparties can withdraw the deposited BTC following only the logic of the application smart contract without trusting any third party. We present a protocol that achieves the security guarantees of this primitive and instantiate it for a lending application where the deposited BTC is used as collateral to borrow against a set of liquidators on the Aave v4 smart contracts on Ethereum. Our mainnet experiments show that at the current Bitcoin price and fee rate, a deposit costs about \$0.7 in fees while a withdrawal costs at most \$7.7. Our construction is built on recent advances in efficient proof verification for Bitcoin.
Relect: Single Secret Leader Election via FHE with Reduced Computation and Communication and Transparent Setup
In a single secret leader election (SSLE) protocol, all parties collectively and obliviously elect one leader. Parties other than the selected leader should not be able to learn the identity of the leader unless it is revealed by the leader itself. The problem is first formalized by Boneh et al. (AFT 2020), and the first concretely feasible lattice-based SSLE with proof-of-concept implementations, $\mathsf{Qelect}$, was recently introduced by Wang and Zhang (USENIX 2025).
In this work, we present $\mathsf{Relect}$, an efficient SSLE protocol, based on the Ring Learning with Error assumption. We build it by leveraging the algebraic structure of the underlying threshold Fully Homomorphic Encryption (FHE) and by designing tailored homomorphic circuits. Compared to prior works, $\mathsf{Relect}$ (1) achieves substantially higher efficiency and (2) removes the strong environment assumption in $\mathsf{Qelect}$ (a trusted setup), while allowing dynamic leader selection for each round.
Concretely, for $32$ -- $2048$ parties, our local FHE computation runtime (a major efficiency bottleneck for SSLE) achieves $7.15$ -- $42.4\times$ faster than $\mathsf{Qelect}$ for a single thread and $7.10$ -- $48\times$ faster for 16 threads. Furthermore, we show that for the same parameters, our communication cost is also $1.14$ -- $2\times$ smaller. As mentioned, this is achieved while removing the trusted setup.
In terms of end-to-end runtime, following $\mathsf{Qelect}$, we tested $2$ -- $128$ parties. We show that under the LAN setting, $\mathsf{Relect}$ is $2.77$ -- $345\times$ faster than $\mathsf{Qelect}$ per round. Under the WAN setting, $\mathsf{Relect}$ is $1.94$ to $17.2\times$ faster than $\mathsf{Qelect}$. Note that these performance gains are all achieved while removing the trusted assumption and achieving dynamic leader selection for each round.
FAEST on GPUs: Addressing Field Multiplication as a Bottleneck
FAEST is a post-quantum signature scheme that combines VOLE-in-the-Head with QuickSilver to prove knowledge of a secret key. It relies on well-established symmetric primitives and offers small public keys, but signing and verification are computationally expensive. We present an NVIDIA GPU implementation of the key-generation core and the QuickSilver procedures OWFProve and OWFVerify for the standard and EM constructions in both s and f variants. Profiling shows that once AES is accelerated by hardware, field multiplication in QuickSilver becomes the largest cost throughout this parameter grid. In FAEST-128f, field multiplication takes about 82% of signing time. To address this bottleneck in our GPU implementation of FAEST, we use PTX clmad for native carry-less arithmetic and Karatsuba to reduce the number of limb products. The clmad build improves throughput across all twelve OWFProve and OWFVerify paths, and its advantage grows with the field width. On an RTX A5000, PTX clmad raises standard OWFProve throughput to 1.99x, 2.45x, and 2.82x that of the software-multiplication build at 128, 192, and 256 bits, respectively. Together, PTX clmad and Karatsuba deliver 26.6x the throughput of the software-multiplication build in the field-multiplication-heavy kernel of standard 256-bit OWFProve. When all OWFProve stages are included, the combined build reaches 2.9x and 3.1x the software throughput for standard and EM at 256 bits, respectively. These results establish native carry-less arithmetic as a key design choice for GPU implementations of FAEST, with Karatsuba providing an additional improvement for 256-bit proving.
Fault Injection Attacks Against zkSTARKs
Fault injection attacks on zero-knowledge (ZK) constructions have received little attention in the wider literature. Recent work has demonstrated single-fault key recovery attacks against a ZK signature scheme. In this paper, we detail candidate fault injection attacks against zero-knowledge scalable transparent argument of knowledge (zkSTARK) provers, designed to violate ZK capabilities. zkSTARK proving systems are complex, and implementations differ substantially in their implementation specifics. We propose a corresponding variety of fault injection attacks against different popular algorithmic primitives. To the best of our knowledge, this marks the first exploration of the fault injection surface of zkSTARKs, and of the wider class of general-purpose ZK proving systems.
Skyhook: Trustless Cross-Chain Value Transfer with a Fully Scriptless Pool
Facilitating value transfers with a scriptless chain is a longstanding problem in cryptography. We present a cross-chain messaging and value transfer protocol that maintains game-theoretic atomicity even when one party is operating on a chain which is fully scriptless, such as shielded Zcash, which has no scripting capabilities at all and requires transactions to be virtually identical. The observation is that consensus protocols which utilise segregated witness schemes to ensure transaction ID unmalleability (such as ZIP 244 in Zcash, SegWit in Bitcoin) segregate
transaction data from the transaction witness component (which is the part that is actually signed). The transaction identifier is, therefore, a virtually collision-resistant commitment to the effects intended by the transaction, computable before signing, and in many chains, even without the knowledge of the signer. A contract on another chain can therefore recompute a future transaction ID from the few fields it needs to see, such as the recipient, the value and the expiry, while every other part of the transaction arrives as an opaque digest. It learns that any transaction with this ID has the agreed effect, without learning anything about the sender and without the recipient signing anything. An optional zero-knowledge layer hides the recipient and value as well. Combined with a light client for the settlement chain on the Turing-complete chain, this yields fully trustless verification that a shielded payment occurred, with no validator consortium or multisig that can be hacked or stalled.
Context-Blind Device-Bound Anonymous Credentials from Signatures and Proofs
Anonymous credentials enable privacy preserving authentication, but their transferability motivates binding each credential to a key protected by a secure element (SE). Such binding should preserve privacy even when the SE is remote or corrupted: every presentation must require fresh SE participation without revealing its context to the SE (Friedrichs et al., EC'26). Existing context-blind device-bound constructions rely on classical assumptions, whereas existing plausibly post-quantum anonymous credentials do not provide this functionality.
We give a modular construction of context-blind device-bound anonymous credentials from a position-binding vector commitment, a signature scheme, a round-optimal blind signature, and a non-interactive zero-knowledge argument. We prove correctness, one-more unforgeability, unlinkability against a colluding issuer, verifier, and fully corrupted SE, and SE-obliviousness. We instantiate the construction with the CAPSS framework (Feneuil and Rivain, TCHES'26), Griffin/Jive Merkle commitments, and proofs of the complete presentation relation. For 16 attributes and four disclosures, using the Ligero-based proof backend from Longfellow (Frigo and shelat, CiC'26) yields a presentation taking 2.60 s on the user side and 0.29 s to verify, with a 506.11 KB proof. We also evaluate an Aurora backend for the same relation.
We complement these measurements with published results to explore the proof-size/proving-time trade-offs offered by alternative transparent, plausibly post-quantum proof systems for relations of comparable size. To the best of our knowledge, this is the first concrete construction and evaluation of context-blind device-bound anonymous credentials assembled entirely from plausibly post-quantum components.
Extended biprojective APN functions
Almost perfect nonlinear (APN) functions provide optimal resistance to differential cryptanalysis in characteristic two, and constructing new infinite families inequivalent to the known ones remains an important problem in the study of cryptographic functions. We introduce extended biprojective functions, obtained by augmenting biprojective polynomials with truncated trace terms, and establish a new infinite family of quadratic APN functions. To investigate these constructions, we develop an efficient APN test based on the ranks of binary matrices and employ it in exhaustive searches in dimensions up to 28. Using ortho-derivative differential spectra to distinguish CCZ-equivalence classes, we identify APN functions inequivalent to known families and uncover a systematic pattern across dimensions, leading to conjectures on further infinite families of quadratic APN functions.
A Hybrid BP-SAT Attack on MILENAGE: Combining the Complementary Strengths of Algebraic and Soft-Analytical Side-Channel Attacks
Profiled side-channel attacks combine noisy leakage predictions with the mathematical relations imposed by the target algorithm to recover secrets from a small number of observations. Two established approaches are algebraic side-channel analysis (ASCA), which encodes leakage predictions and algorithmic relations as a Boolean satisfiability (SAT) problem, and soft-analytical side-channel analysis (SASCA), which performs probabilistic inference over a factor graph using belief propagation (BP). We evaluate both on the AES-based MILENAGE authentication algorithm deployed on USIM cards, targeting the first AES-128 invocation on $\mathit{RAND}\oplus\mathit{OPc}$ under the subscriber key $K$, where $\mathit{OPc}$ is an operator-specific secret unknown to the attacker. Neural networks predict posterior probability distributions over the AES S-box output byte values across multiple rounds and these predictions are supplied to ASCA and SASCA to recover $K$ and $\mathit{OPc}$ from a single trace. SASCA recovers both secrets in 87.7% of attacks, but converges to an incorrect $\mathit{OPc}$ in 6.1% of cases despite recovering $K$ correctly. ASCA enforces global consistency and resolves this ambiguity, but it succeeds in only 34% of attacks under a 1-hour timeout and our constraint-selection strategy. Motivated by these complementary failure modes, we combine the two into a hybrid attack in which BP refines the neural network predictions before they are supplied to the SAT solver. The hybrid approach recovers both secrets in 93.8% of single-trace attacks, resolving all cases where SASCA recovers $K$ correctly but $\mathit{OPc}$ incorrectly. It has a higher success rate and a lower average runtime than either method alone, despite performing more work per attack. Finally, we suggest a countermeasure, based on masking each AES round key with an independent, per-device secret, that reduces an attacker's advantage over guessing $K$ and $\mathit{OPc}$ to zero bits, and confirm empirically that it defeats the hybrid attack in all evaluated cases.
Tulva: Practical Asynchronous Threshold FHE
Fully homomorphic encryption (FHE) allows arbitrary computation over encrypted data, but its secret key presents a single point of failure which limits its applications. Threshold FHE patches this gap by distributing the secret key to $K$ parties, requiring a threshold $t \leq K$ of them to cooperate for decryption. We focus on the asynchronous setting where a ciphertext can be decrypted by collecting decryption shares from any $t$ parties who do not need to coordinate or even be online simultaneously. Asynchronous schemes are sought in applications such as privacy-preserving Ethereum Virtual Machines (EVM), processing of long-lived private data with quorum-based decryption and the thresholdisation of any cryptographic primitive in general.
We present Tulva, a practical threshold FHE scheme which equips a base FHE scheme with an asynchronous threshold decryption mechanism in a modular way. Our scheme simultaneously (1) is compatible with virtually any base FHE scheme and leaves its ciphertexts unchanged apart from an appended random tag, (2) supports a wide range of threshold profiles $(t,K)$ and ring degrees $\geq 256$ with 6--25 bits partial decryption per plaintext bit, and (3) achieves security in the presence of partial decryption queries on challenge ciphertexts based on the standard LWE assumption.
We provide an open-source implementation, benchmark its threshold decryption performance and evaluate the end-to-end costs for typical privacy-preserving EVM use cases. For 16-out-of-512 threshold and a publicly preprocessed ciphertext, computing secret-dependent partial decryption and public share combination requires only 3.7ms and 0.5ms, respectively, on commodity hardware. Compared with the state-of-the-art synchronous scheme [Zyskind et al., CCS'25], we replace their ciphertext-independent yet interactive preparation of secret-correlated randomness with a public, ciphertext-dependent 0.5s preprocessing step, eliminate interaction in the online phase while maintaining similar decryption time on the same machine, and support 32$\times$ more total users.
Unveiling the Cost: Gas-Efficient Output-Private Distributed VRFs on Ethereum
Unbiased and publicly verifiable randomness is a fundamen-
tal component of Web3 security, and output-private distributed verifiable
random functions (DVRFs) extend this guarantee by keeping the gener-
ated randomness hidden from chain observers until the requester chooses
to reveal it. Two constructions currently realize output privacy under dif-
ferent algebraic regimes: FlexiRand, whose on-chain verification rests on
bilinear pairings, and IcyVeil, a pairing-free design whose verification re-
duces to a constant number of group operations. While it is folklore that
pairing-free verification should be cheaper on the Ethereum Virtual Ma-
chine (EVM), the actual on-chain cost of output-private randomness has
never been measured for either scheme. In this paper, we present the first
EVM implementations of both constructions. Both verifiers are served by
a single coordinator contract realizing the common blind–evaluate–pre-
verify lifecycle, so that every measured difference is attributable solely
to the verification arithmetic. The isolated verification is 57% cheaper in
execution gas for the pairing-free scheme (51,561 against 118,541 gas);
over the full request lifecycle, whose remaining stages are shared, the ad-
vantage is about 11%. This on-chain saving comes with a cost off chain:
the pairing-free scheme’s distributed evaluation requires roughly 2.5 to
8.2 times more aggregate committee compute across committee configu-
rations (n, t), a gap absorbed comfortably by Ethereum’s block time and
one that narrows further once the committee executes concurrently. We
report both axes, separating one-time distributed key generation (DKG)
cost from IcyVeil’s consumable preprocessing, and reconcile the on-chain
and off-chain ratios, which point in opposite directions. All contracts,
harnesses, and raw measurements are publicly available.
A methodology to derive security specifications for complex electronic systems
Uncategorized
Uncategorized
Modern electronic systems are becoming increas-
ingly complex and must satisfy demanding performance, power,
and area (PPA) constraints. Consider for instance artificial
intelligence chips, aiming at datacenters running LLMs or at
automotive perception, which manipulate massive data streams.
Beyond performance considerations, these systems must also
provide increasingly strong security and dependability guaran-
tees. Indeed, when electronic systems are based on chiplets, for
instance, the supply chain gets longer and therefore brings a
larger number of threats. Also, those systems are very versatile,
in that they can run varied multi-tenant applications. Therefore,
defining what security features are required in this context with
numerous stakes is not trivial.
Existing scholarly research is very relevant when the security
problem is well defined. The resulting scientific papers accord-
ingly dig very deep: this modus operandi has proved productive in
exploring new problems, and actually allowed to come up with
innovative solutions. For instance, in the field of side-channel
attacks, varied mitigations alongside with metrics to evaluate
them have been devised. Increasing sophistication resulted from
this research, as external considerations have been injected into
the problem (typically, aspects such as attack order, impact
of combinatorial glitches, etc.). Therefore, we face today the
question of selecting the most suitable technology amongst the
proliferation of state-of-the-art techniques.
In addition, in complex systems, we encounter another prob-
lem, namely that of defining the security problem(s). A fruitful
approach in this respect is a risk based approach. Specifically,
the application of a risk-oriented methodology allows to reason
on the security rationale. It proceeds as follows. First, the
system missions are listed. Then for each of them, the necessary
assets are deduced. A threat analysis allows to identify how
assets are threatened, and eventually, security requirements can
be enunciated. At this stage, the task of matching relevant
countermeasures becomes straightforward.
This paper illustrates the methodology by deriving security
specifications for datacenter and automotive chiplets. The considered missions are (secure) provisioning, trimming, debugging,
booting, and remote attestation.
Decomposed LWE is Equivalent to Succinct LWE
We prove that the Succinct Learning with Errors assumption, introduced by Wee (CRYPTO '24), and the Decomposed Learning with Errors assumption, introduced by Abram, Malavolta, and Roy (CRYPTO '25), are equivalent under appropriate parameter settings. Abram, Malavolta, and Roy proved that Succinct LWE implies Decomposed LWE. We establish the converse implication, showing that Decomposed LWE implies Succinct LWE.
Hardware-Level Mitigation of Micro-Architectural Leakages in Embedded Processors
Cryptographic software, with its inherent flexibility and adaptability, has become essential for meeting today’s rapidly evolving security requirements, despite offering lower performance than dedicated hardware accelerators. However, Side-Channel Analysis (SCA) complicates its secure execution on physical hardware, making robust protection a central challenge. While the masking countermeasure offers provable security guarantees in theory, its effectiveness is often undermined by the processor’s micro-architecture. In response, formal adversary models have been adapted to account for micro-architectural leakage under generic (but over-conservative) assumptions on the hardware. Consequently, achieving security under such a generic model requires compilers to produce less performant software. To bridge this gap, secure hardware-software co-design assumes a precisely specified hardware leakage behavior, enabling the specification of constraints for secure compilation. While this approach reduces the overhead required to counteract these effects, it does not entirely remove it.
This work follows a more fundamental paradigm: instead of managing leakage in software, we aim at eliminating it at its source. Conceptually, we propose architectural changes to general-purpose processors at the Register-Transfer Level (RTL) that remove the root causes of micro-architectural leakages. The application of these changes enables the secure execution of masked software without introducing micro-architectural leakage under the Robust but Relaxed (RR) d-probing model, thereby removing the need for complex, security-aware compilers and hardware-specific workarounds in the software. While our countermeasures can be applied to many micro-architectures, we formally prove the security of each countermeasure individually and integrate them into the Ibex processor, whose security we evaluate as a whole through tool-assisted leakage assessment of the full netlist and physical experiments on a Field Programmable Gate Array (FPGA).
Uniform Sharing in Multiple Stages: Towards Second-Order Security
Mitigating Side‑Channel Analysis (SCA) of cryptographic implementations relies heavily on masking schemes; however, achieving efficient and straightforward hardware realizations remains challenging. While Threshold Implementation (TI) provides provable security against glitches in hardware, it incurs significant area overhead due to the large number of shares required to protect non‑linear functions. Successor schemes achieve the same security order with a minimal number of shares, but often rely on a high amount of per‑cycle randomness, especially at higher orders. Recent optimizations such as NullFresh and MultiStage attain minimal share counts without additional randomness; however, they lack a generalized methodology for higher‑order security. In particular, although MultiStage enables automated generation of low‑randomness masked designs, it is currently limited to first‑order protection.
In this work, we bridge this gap by introducing an automated masking technique for arbitrary functions that guarantees second‑order security in the glitch‑extended probing model. Building upon the MultiStage approach, our method preserves the efficiency of NullFresh by minimizing requirements for fresh masks, while overcoming structural limitations of previous schemes. We demonstrate the feasibility of the approach on the lightweight block ciphers PRINCE, Midori, and SKINNY. The resulting designs are formally verified using SILVER and PROLEAD, and experimentally evaluated on FPGA using TVLA.
Edabits Generation with Quasi-Linear Communication Complexity
The work of (Escudero et al., CRYPTO 2020) introduces the so-called edabits, which are defined as a secret sharing of an integer over an arithmetic domain, together with its bit decomposition secret shared over a binary domain. In the same work, it is shown how edabits can be used to securely evaluate advanced primitives such as comparison, bit decomposition, and truncation, which are essential building blocks in more complex applications such as privacy-preserving machine learning and beyond. Edabits are general and can be defined over any secret-sharing scheme or corruption model. Such flexibility, coupled with their wide range of applications, makes edabits a powerful target correlation.
Escudero et al.~introduced a protocol to generate edabits that works in the arithmetic black-box (ABB) model, that is, it is agnostic to the concrete secret-sharing scheme and even works both for fields $\mathbb{F}_p$ and rings $\mathbb{Z}_{2^\ell}$, as well as both for honest majority $t<n/2$ and dishonest majority $t<n$. Unfortunately, the communication complexity of their approach grows as $\Omega(n^2\ell)$ bits with $\ell$ being the bit-length of an element in the arithmetic domain. This becomes a bottleneck in larger protocols since most MPC primitives such as multiplications or openings can be done with linear communication of $O(n\ell)$ bits.
In this work we present a novel approach for generating edabits in the ABB model that achieves \emph{quasi-linear} communication complexity of $O(n\ell\log n)$ bits, for the setting where $t<n(1-\epsilon)$ for a constant $\epsilon>0$. This includes the honest majority case $t<n/2$, but also dishonest majority with an (arbitrarily small) constant fraction of honest parties. Our result is achieved via novel applications of randomness extraction methods, as well as better edabit aggregation for the binary components. Along the way and of independent interest, we improve the communication complexity of dabit generation (dabits are bits shared in both binary and arithmetic domains) from $\Omega(n^2\ell)$ bits achieved in (Rotaru and Wood, INDOCRYPT 2019), to linear $O(n\ell)$ bits.
Polygero: Proximity Testing From Polynomial Challenges
We present a new proximity test for Reed--Solomon codes that admits a higher-agreement regime with soundness approaching the field's bit length.
All prior work in this area [AHIV2017,BCIKS2020,BCHKS2025] uses the idea of *scalar* batching in which the verifier provides a scalar challenge for each codeword, and the prover must supply a codeword equivalent to the combination, and the verifier tests it at randomly opened columns.
Our main insight is to instead use a low-degree polynomial challenge for each codeword. We prove that the low-dimensional spaces generated by polynomial challenges become maximum distance separable (MDS) after deleting a few coordinates, and this phenomenon leads to a new kind of proximity gap that we can exploit.
This insight enables a simpler, in fact elementary counting proof for soundness of the proximity tests. We do not need the Polishchuk--Spielman lemma or Guruswami--Sudan decoding.
The same technique proves soundness of Polygero, a Ligero-inspired
IOP~[AHIV17], beyond the unique-decoding regime. Through recursion, Polygero produces proofs with a number of field elements logarithmic in the witness size, independently of the number of linear constraints. It does not require roots of unity in the finite field or out-of-domain sampling.
The soundness analysis, including the extractor and the recursive composition, and every reported parameter schedule are machine-checked in Lean.
DDYF: Differential Dolev-Yao Fuzzing of Cryptographic Protocols
Symbolic formal verification of cryptographic protocols based on the Dolev-Yao (DY) attacker model—an active attacker with full network control and perfect cryptography—is well-established for finding design-level logical flaws in cryptographic protocols. Building on this, Dolev-Yao Fuzzing (DYF) enriches fuzzing with this attacker model to uncover logical bugs at the implementation level. In contrast to bit-level fuzzers
(e.g., AFL), DYF leverages a formal model of messages and cryptography to generate structured, adversarial executions, such as replaying and re-signing a modified payload.
However, a significant limitation of DYF is the requirement to precisely model properties to check at runtime (e.g., session parameter agreement). Defining these properties is labor-intensive and inherently non-exhaustive, often necessitating complex instrumentation of the Programs Under Test. Consequently, typically only a subset of logical attacks is detected.
We address this limitation by introducing Differential Dolev-Yao Fuzzing (DDYF) based on a differential oracle to compare executions across different protocol implementations. By interpreting discrepancies through the DY model, it identifies semantic differences indicative of bugs or vulnerabilities, effectively minimizing false positives.
We propose a generic design for DDYF, implement it within the PUFFIN DY fuzzer, and evaluate it on four major TLS implementations and two SSH implementations. Our results demonstrate that DDYF can detect vulnerabilities that evade state-of-the-art fuzzers, specifically those requiring DY attacker capabilities (missed by bit-level differential fuzzers) or complex objective oracles (missed by DYF). DDYF also uncovered numerous new RFC violations in OpenSSL, BoringSSL, wolfSSL, LibreSSL, libssh, and wolfSSH, which are by-design hardly detectable with non-differential oracles.
Post-Quantum Certificate-Based PSK Provisioning for WireGuard via Mutual TLS, DTLS, and QUIC: Design and Performance Study
We present an architecture that provides WireGuard’s resistance against future quantum adversaries. By preserving the core protocol, our approach minimizes deployment effort and adds certificate-based identities to WireGuard peers. To achieve Post-Quantum (PQ) resistance, we establish an external mutually authenticated control channel built on the TLS 1.3 handshake and layered on top of TCP, UDP, or QUIC. Its key establishment includes Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM). An auxiliary shared secret is derived from the exported keying material of the resulting session and injected into WireGuard’s native Pre-Shared Key (PSK) interface; this derivation is identical for all three transports. To support scalable deployment, the control channel is authenticated with X.509 certificates issued by a Public Key Infrastructure (PKI), using the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) for PQ certificate signing. We develop a Tamarin model of the composition layer and symbolically analyze the secrecy, binding, and provisioning-order properties of the interface between TLS 1.3 handshake and WireGuard, identifying the critical conditions necessary for secure deployment. Finally, we evaluate the design to quantify handshake latency and CPU time for classical, pure PQ and hybrid key establishment, classical and ML-DSA certificates, and the three transports, comparing it against an existing PQ WireGuard baseline achieving state-of-the-art results.
Committing Security of Forkcipher-based AEAD
Authenticated Encryption with Associated Data (AEAD) provides confidentiality and integrity, but traditional security notions do not prevent ciphertexts from decrypting correctly under multiple keys. This motivates committing security, which requires ciphertexts to bind to their encryption inputs uniquely. Recent analyses revealed commitment failures in several forkcipher-based AEAD schemes, leaving open the question of whether these failures are inherent to forkciphers or design specific. We provide a comprehensive committing security analysis of existing forkcipher-based AEAD constructions, filling this gap by establishing both negative and positive results. Our analysis shows that while some designs inherently fail to achieve strong commitment, others achieve meaningful commitment guarantees, demonstrating that forkciphers can serve as a foundation for committing-secure AEAD schemes. We derive tight bounds for commitment notions for existing constructions. As a key technical contribution, we formalize a forkcipher-based hash construction and prove its collision resistance, which serves as a foundation for our security analysis.
Tree-BTE: Batched Threshold Encryption using Additive Homomorphism
Batched threshold encryption (BTE) enables a committee of servers to jointly decrypt any chosen subset of ciphertexts from a large pool, while all remaining ciphertexts stay private. BTE is a key building block for encrypted mempools, where transactions are encrypted until block inclusion to mitigate maximal extractable value (MEV). We give a new tree-based BTE construction from two simple building blocks which support additive homomorphism: a symmetric-key encryption scheme that is homomorphic over key and message space, and a thresholdizable public-key encryption scheme that is homomorphic over message space. These building blocks can be instantiated under a wide variety of assumptions including DDH, DCR, LWR and even LWE for post-quantum security.
In our scheme, each ciphertext is associated with an index from an appropriate index space. We implement the DDH-based instantiation. Given an aggregated batch of 1,000 messages over a small 1024 sized index space, each server performs about 41~ms of single-thread computation, including a 100-of-300 threshold decryption.
We also partially implement an RLWE-based post-quantum instantiation over a \(2^{128}\) sized index space for negligible collision probability among indices. A batch of 1024 messages uses approximately 0.89 MB per ciphertext and 20 seconds of single-thread decryption per server.
On the Hardness of Finding Permutation Automorphisms of Linear Codes
We study the hardness of finding permutation automorphisms of linear codes. We look into three main problems: $\mathsf{AUT}$, $\mathsf{AUT}$-$\mathsf{Gen}$ and $\mathsf{AUT}$-$\mathsf{Count}$ which, respectively, ask to find a non-trivial automorphism, a generating set and the order of the automorphism group.
We give polynomial time reductions from $\mathsf{AUT}$ to $\mathsf{ISO}$ (the problem of finding a permutation isomorphism between two linear codes), and from $\mathsf{ISO}$ to $\mathsf{AUT}$-$\mathsf{Gen}$ and $\mathsf{AUT}$-$\mathsf{Count}$. This shows that $\mathsf{AUT}$-$\mathsf{Gen}$ and $\mathsf{AUT}$-$\mathsf{Count}$ are unlikely to be easy in the worst case, since all known solvers for $\mathsf{ISO}$ take exponential time if the hull dimension (the subspace given by the intersection between the code and its dual) is large enough.
Furthermore, we give a reduction from $\mathsf{AUT}$-$\mathsf{Gen}$ to the problem of finding generators for the automorphism group of a graph, which we refer to as $\mathsf{GraphAUT}$-$\mathsf{Gen}$.
Up to some polynomial factors, the reduction runs in time $O(n^{h})$, with $n$ being the code length and $h$ the hull dimension: for $h = O\big(\log(n)\big)$, this implies that $\mathsf{AUT}$-$\mathsf{Gen}$ can be solved in worst case quasi-polynomial time.
We also give a simpler version of the reduction, running in time which is exponential in the worst case (arguably, only for rather contrived codes), even for small $h$. However, heuristically, the algorithm is on average extremely efficient for small $h$. We use it as a concrete solver and show that a proof-of-concept implementation is significantly faster than the built-in implementations of Leon's and Feulner's algorithms provided by $\texttt{Magma}$ and $\texttt{Sagemath}$.
What’s the Matter? An In-Depth Security Analysis of the Matter Protocol
The Matter protocol has emerged as the leading standard for secure IoT interoperability, backed by major vendors such as Apple, Google, Amazon, Samsung, and others. With millions of Matter devices already deployed, its security guarantees are critical to the safety of modern IoT ecosystems. This paper presents the first in-depth analysis of Matter's key establishment protocols: Passcode-Authenticated Session Establishment (PASE) and Certificate-Authenticated Session Establishment (CASE), which are based on the well-studied SPAKE2+ and SIGMA, respectively. We first perform a specification-level security analysis of PASE and CASE, comparing Matter's design choices against the original SPAKE2+ and SIGMA protocols. This reveals weaknesses such as low-entropy setup passcodes, static per-device salts, and weak PBKDF2 parameters. Next, to assess how such weaknesses manifest in practice, we analyse a certified Matter codebase and find that critical safeguards such as limiting failed pairing attempts are not enforced. All identified vulnerabilities were responsibly disclosed and have been patched. We then complement our analysis by formally verifying PASE, CASE, CASE Resumption, and the original SPAKE2+ and SIGMA protocols. In particular, we show in the symbolic model that the security of Matter's lightweight session re-establishment mechanism (CASE Resumption), used for the vast majority of Matter sessions, rests entirely on the secrecy of an ephemeral key generated by an IoT device. Building on all three stages, we construct proof-of-concept attacks and evaluate their feasibility under Matter's own threat model. Our results invalidate several countermeasures specified in Matter's threat model, including protections for threats classified as ``High Risk''. Overall, our work shows that strong cryptographic building blocks alone are insufficient unless the surrounding protocol and deployment rules are equally rigorously specified and tested at the standard level.
It's Not Just a Phase: Understanding Function Dependence in MPC Preprocessing (Extended Version)
Secure multiparty computation (MPC) is a key enabling technology for privacy-preserving applications. To achieve low latency after inputs are provided, many efficient protocols utilize preprocessing, and the landscape of preprocessing approaches is growing and diverse. Some recent works use variants of function-dependent preprocessing, leveraging additional knowledge on the function to be computed for even better performance. While the existing literature primarily focuses on performance, it is mostly overlooked that there exist different kinds of function dependence and what practical implications they have. We systematize the different flavors of function dependence, relating them to practical requirements beyond efficiency.
SubLogarithmic Linear Time SNARKs from Improved Sumcheck
We present $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$ -- the first SNARKs that simultaneously achieve linear-time prover, sublogarithmic proof size, logarithmic verifier, and also feature updatable setups. Our constructions are provably secure in the Random Oracle Model (ROM) and the Algebraic Group Model (AGM). As a core technical contribution (possibly of independent interest), we reduce the communication complexity of the classical sumcheck protocol for multivariate polynomials from logarithmic to sublogarithmic, while retaining linear prover complexity. For degree $d$ multivariate polynomials in $\mu$ variables which can be decomposed into $\ell$ multilinear polynomials, our protocol achieves $O(\ell + d\log\log n)$ communication and $O(n)$ prover cost for $n = 2^\mu$. Our protocol leverages recently proposed multilinear polynomial commitment schemes (PCS) with linear-time prover and constant proof size.
Multivariate sumcheck is a key ingredient in the design of several prover-efficient SNARKs, such as Spartan (Crypto '20), HyperPlonk (Eurocrypt '23), MicroSpartan (S&P '25), Hyrax (S&P '18), Libra (Crypto '19), Gemini (Eurocrypt '22), Virgo (S&P '20) etc. All of these SNARKs incur $\Omega(\log n)$ proof size, with the smallest concrete proof sizes ranging from 5KB-10KB for circuit sizes in the range of $2^{20}$-$2^{30}$.
We compile variants of the Spartan and HyperPlonk multilinear PIOPs with our improved sumcheck to realize two new SNARKs, namely $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$, that support R1CS and Plonkish constraints, respectively. Both of them achieve $O(n)$ prover, $O(\log\log n)$ proof size, and $O(\log n)$ verifier, while avoiding proof recursion and non-black-box use of cryptographic primitives. We implement $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$, and compare their performances with several state-of-the-art prover-efficient SNARKs. For circuits of size $2^{30}$, $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$ achieve proof sizes of 1.9 KB and 2.4 KB, respectively, which are 2.4-3.6x smaller than the most compact prover-efficient SNARKs, while achieving comparable prover costs.
Tamper Sensing Meshes in Payment Terminals and Beyond
Card Payment Terminals commonly use tamper sensing meshes to deter physical attacks on devices handling sensitive data such as cryptographic keys. Although their use of such meshes is frequently referenced in research literature, the public record contains little research on their construction. Addressing this gap, in this paper we present the first comprehensive analysis of the practical implementation of tamper sensing meshes across a wide range of payment terminals, and some other devices such as ATM key pads and a data center HSM. We provide detailed photos of critical features. Based on our observations, we construct a taxonomy of mesh construction techniques. Our analysis reveals that most commercial devices use surprisingly simple construction techniques, and their structure size rarely approaches manufacturing limits.
Based on our analysis, we identify a concise set of design patterns for the construction of secure tamper sensing meshes. We conclude that designing tamper sensing meshes that exceed the industrial state of the art is viable even using inexpensive and easily available manufacturing processes. Our set of design recommendations creates a foundation for both the practical tamper sensing mesh implementations and for future research into their design. Our results enable researchers to base test specimens on concrete evidence of industrial practice.
Software-Pipelining The Number Theoretic Transform on Neural Processing Units: A Loop-Fission Methodology
Lattice-based post-quantum cryptography (PQC) and fully homomorphic encryption (FHE) rely heavily on the number theoretic transform (NTT) for efficient polynomial multiplication. While GPUs and FPGAs have been widely explored for NTT acceleration, neural processing units (NPUs), a rapidly growing class of AI accelerators, remain largely unexplored for cryptographic workloads. In this work, we develop a methodology for accelerating the NTT on NPUs, using AMD’s AI Engine (AIE) architecture as a representative NPU to develop and benchmark it. At its core is manual loop fission, in which large and complex loops are split into smaller primitives, enabling highly efficient software pipelining and avoiding memory stalls or register spilling. Applying it, we develop efficient Barrett reduction primitives and use these to construct three high-throughput, low-latency NTT implementations (radix-2, radix-4, and radix-8), achieving significant performance gains over the AIE compiler and prior literature. On AMD’s first-generation AIE specifically, we achieve speedups of $8.27\times$ to $13.2\times$ in throughput and $2.44\times$ to $10.3\times$ in latency per AIE tile in comparison with prior work. Our implementations support arbitrary NTT-friendly moduli and polynomial sizes up to degree 4096 for 14-bit moduli and 2048 for 30-bit moduli. Finally, we discuss the portability of our techniques to other NPU architectures, and identify which architectural features are most beneficial for NTT acceleration.
Weak keys in QC-MDPC-based cryptosystems via the extended Euclidean algorithm
In this work we analyze a problem strictly linked with the Rational Reconstruction, which forms the foundation of some post-quantum Quasi-Cyclic Moderate-Density Parity-Check and Quasi-Cyclic Low-Density Parity-Check code-based schemes such as LEDAkem and BIKE.
Given a polynomial in a cyclic ring as input, our aim is to recover two polynomials, with specific properties, whose ratio is the input one.
The starting point of this work is the paper of Bardet, Dragoi, Luque, and Otmani, which describes some approaches, based on the Extended Euclidean Algorithm, that solves this problem in some specific cases.
In comparison to previous work, we define an additional setting in which the problem can be solved. We also provide an alternative approach to estimate the probability of success, by taking into account a requirement that was not considered in the original paper, thus getting a more precise estimation. Finally, we present a key-recovery attack on BIKE, evaluate its computational cost, and compare it with that of the most efficient known attacks. Although this last step is performed specifically on BIKE, the methodology can be extended to other schemes as well.
edaBits in the Exponent (edaBitE) and Issuer-Hiding Blind Signatures from ML-DSA and VOLE-in-the-Head
Blind signatures let a user obtain a signature by interacting with an issuer that controls the signing key, while the issuer never sees the message. They form the basis of anonymous credentials, which are the centerpiece of privacy-preserving digital identification to be deployed widely in the coming years. Existing plausibly quantum-secure blind signatures rely on bespoke cryptographic constructions, instead of standardized ones. This is dissatisfying from a cryptographic perspective, and also leads to practical issues: secret signing keys are often stored in secure elements, in which case only signature algorithms supported by certified secure elements can be the basis for deployed protocols.
We give the first blind signature whose issuer runs a NIST-standardized post-quantum signature scheme unmodified. Issuance is just an ML-DSA signature on a commitment, and the blind signature is a zero-knowledge proof of knowledge, using the VOLE-in-the-head zero-knowledge proof system, of the ML-DSA signature. Security reduces to the EUF-CMA security of ML-DSA and to the proof system, with no new assumptions.
A blind signature is about $1$ MB and takes under a second to produce and half a second to verify. Issuer-hiding and selective disclosure of signed attributes can easily be added on top for a few tens of kilobytes, at a proof size essentially independent of how many issuers the list names.
Underlying the construction is edaBitE, a novel batch consistency check between binary and prime-field commitments. In a non-interactive proof, the existing edaBits checks it replaces would be the single largest item in the blind signature. We believe that edaBitE is of independent interest.
Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs
Traditional notions of secure multiparty computation (MPC) allow mutually distrusting parties to jointly compute a function over their private inputs, but typically do not specify how these inputs are chosen. Motivated by real-world applications where corrupt inputs could adversely impact privacy and operational legitimacy, we consider a notion of authenticated MPC where the inputs are authenticated, e.g., signed using a digital signature by some certification authority. We propose a generic and efficient compiler that transforms any linear secret sharing based honest-majority MPC protocol into one with input authentication.
Our compiler incurs significantly lower computational costs and competitive communication overheads when compared to the best existing solutions, while entirely avoiding the (potentially expensive) protocol-specific techniques and pre-processing requirements that are inherent to these solutions. For $n$-party honest majority MPC protocols with abort security where each party has $\ell$ inputs, our compiler incurs $O(n\log \ell)$ communication overall and a computational overhead of $O(\ell)$ group exponentiations per party (the corresponding overheads for the most efficient existing solution are $O(n^2)$ and $O(\ell n)$). Finally, for a corruption threshold $t<n/3$, our compiler preserves the stronger identifiable abort security of the underlying MPC protocol. No existing solution for authenticated MPC achieves this regardless of the corruption threshold.
Along the way, we make several technical contributions that are of independent interest. This includes the notion of distributed proofs of knowledge and concrete realizations of the same for several relations of interest, such as proving knowledge of many popularly used digital signature schemes, and proving knowledge of opening of a Pedersen commitment.
Nowhere Man: Device Binding for Post-Quantum Anonymous Credentials
Anonymous credentials are seeing widespread deployment. Notably, the European Commission plans to roll out age-verification solutions based on anonymous credentials by the end of 2026. Similarly, Google open-sourced Longfellow, a zero-knowledge proof system that lifts the standardized mobile Driver License framework into a full-fledged anonymous credentials, and is currently being integrated with Google Wallet.
Any secure deployment of anonymous credentials must address two major challenges: 1) provide guarantees against credential sharing, and 2) support proof-of-personhood. The standard approach adopted by the industry to address both is device binding, which is mandatory for mDL and was only recently formalized for anonymous credentials by Friedrichs et al. (Eurocrypt '26). Simply put, the idea is to have the user's phone Secure Element sign a fresh challenge from the verifier, and to prove knowledge of this signature in zero-knowledge at each credential presentation.
To date, all existing approaches, including Vega (S&P '26), have only
considered non-post-quantum solutions based on legacy signature schemes. Crucial for near-term deployments and adoption is to work with standardized post-quantum signature schemes, such as ML-DSA,
which were not designed for privacy. Because of this, solutions based on general non-interactive zero-knowledge proof systems (e.g., Longfellow) appear to be needed. This genericity, however, requires proving complex statements, significantly impacting proving time.
In this work, we present a modular device binding protocol tailored to work with ML-DSA. We avoid the pitfalls of the generic approach by leveraging the structure of ML-DSA resulting in an efficient solution, but retaining the security underlying the post-quantum standard. Our most efficient variants additionally rely on a weak-MLWR assumption for unlinkability, which can be removed at the cost of lower efficiency. While tailored for ML-DSA and requiring no modification to the FIPS~204 signing interface, our solution is modular enough to be integrated with different anonymous credential schemes, allowing real-world solutions to pick the most efficient building blocks. To demonstrate the feasibility of our solution, we provide a proof-of-concept implementation.
ECHO: Efficient Covertly-Secure Three-party Computation with Applications to Private Machine Learning
Secure three-party computation with an honest majority is among the most efficient secure computation settings and is widely used in practice. However, achieving malicious security incurs significant overhead, often an order of magnitude higher than semi-honest protocols. Covert security provides a security–efficiency trade-off by detecting malicious behavior with a certain probability (e.g., $50\%$), deterring rational adversaries. Existing covert protocols mainly target two-party or dishonest-majority settings, with little work on efficient honest-majority three-party solutions.
We present $\mathsf{ECHO}$, a family of concretely efficient protocols for covertly secure honest-majority three-party computation. We explore the design space of cheating detection and identification, and develop optimized protocols for both arithmetic and Boolean circuits, targeting different performance goals such as low latency and reduced communication.
For arithmetic circuits over rings, our asymmetric-MAC-based protocol achieves an online phase only $1.26\times$ slower than the semi-honest baseline and over $5.59\times$ faster than malicious security. For Boolean circuits, our method improves over the best malicious protocol by $5\times$. We also applied $\mathsf{ECHO}$ on practical PPML tasks. $\mathsf{ECHO}$ approaches semi-honest performance while providing up to $8\times$ speedup over malicious security.
Refined Application of the XL Algorithm within the Algebraic Approach to the Regular Syndrome Decoding Problem
The Syndrome Decoding Problem (SDP) is a fundamental mathematical problem underlying code-based cryptography, which is considered a promising candidate for post-quantum cryptography. The Regular Syndrome Decoding Problem (RSDP) is a variant of the SDP in which the error vector follows a specific block-wise structure. Recent developments in RSDP-based cryptographic schemes have led to a wider variety of parameter settings, making it increasingly important to evaluate the complexity of solving the RSDP over a broad range of parameters. One of the main approaches to solving the RSDP is the algebraic approach, which transforms a given RSDP instance into a polynomial system and solves it using algebraic techniques such as the XL algorithm. In this work, we construct and analyze algebraic algorithms for the RSDP by combining and extending techniques used in existing algebraic approaches. Our algorithms mainly follow the framework of the hybrid algorithm proposed by Wang et al., while allowing an arbitrary solving degree $d$ in the application of the XL algorithm. We further consider two variants: an XFL-based method that combines partial Gaussian elimination with variable guessing, and a WXL-based method that exploits the sparsity of the Macaulay matrix. Our complexity analysis for various parameter settings shows that, for some fixed values of $n$ and $k$, the WXL-based variant using a larger solving degree $d>2$ is particularly efficient when the block size $\beta$ is sufficiently small, while the original hybrid algorithm becomes more efficient as $\beta$ increases.
Complete Characterization of Randomness Extraction from DAG-Correlated Sources
We introduce the SHEDAG (Somewhere Honest Entropic sources over Directed Acyclic Graphs) source model, a general framework for multi-block randomness sources with causal correlations. A SHEDAG source is defined over a directed acyclic graph (DAG) $G$, whose nodes output $n$-bit blocks. Honest nodes output mutually independent blocks, which are uniformly random by default and, more generally, may have high min-entropy. Corrupted nodes output arbitrary functions of their causal views (all predecessors in $G$). We tightly characterize the conditions under which zero-error and negligible-error randomness extraction from SHEDAG sources is possible.
\begin{description}
\item[Zero-error extraction:] We show that perfect extraction from SHEDAG sources with $t$ corruptions is possible if and only if $G$ contains an \emph{unrelated set} (an antichain under reachability) of size at least $t+1$. In particular, if every unrelated set has size at most $t$, no function can extract a perfectly uniform bit. We also give a polynomial-time algorithm for finding a maximum unrelated set, thereby efficiently determining the largest corruption threshold $t$ for which perfect extraction is possible.
\item[Negligible-error extraction:]
We introduce a graph parameter, called the \emph{resilience} of a DAG $G$, that characterizes the feasibility of randomness extraction with \emph{negligible} error in the block length. We define two variants of this parameter, $\res_\uni(G)$ and $\res_\ent(G)$, corresponding to uniform and entropic honest nodes, respectively. We show that when honest nodes are uniform, negligible-error extraction is impossible when the number of corrupted nodes $t>\res_\uni(G)$.
When honest nodes are entropic, we show that negligible-error extraction is impossible when $t>\res_\ent(G)$. Complementing these impossibility results, we establish the following:
\begin{itemize}
\item[(i)] There exists an explicit extractor for SHEDAG sources with $t\leq \res_\uni(G)$ corrupted nodes and honest blocks that are uniform over $\bits^n$, achieving output length $\Omega_N(n)$ and error $2^{-\Omega_N(n)}$. Here $N$ is number of vertices of the DAG $G$.
\item[(ii)] There exists a non-explicit extractor for SHEDAG sources with $t\leq \res_\ent(G)$ corrupted nodes and honest blocks of min-entropy $k\geq \poly\log n$, achieving output length $k^{\Omega(1)}$ and error $2^{-k^{\Omega(1)}}$.
\end{itemize}
Collusion-Safe Proxy Re-Encryption
Proxy re-encryption is a cryptographic scheme enabling a delegator (user $i$) to delegate its decryption right to a valid delegatee (user $j$) through a proxy, who cannot extract any information about the message during the procedure. An important security notion is the security against collusion between the proxy and the delegatee. In this case, the adversary has the secret key of the delegatee, $\mathsf{sk}_j$, and the re-encryption key, $\mathsf{rk}_{i\to j}$. The master secret security is first formalised by Ateniese et al. (NDSS'05) to capture the secrecy of $i$'s secret key during collusion. This notion was further formalised by Zhou et al. (ASIACRYPT'23) as the indistinguishability of re-encrypted ciphertext against chosen-message attacks, called collusion safety, which implies the master secret security. In this paper, we find that a PRE scheme is not master secret secure as they claimed, and many other schemes were not master secret secure. Then, we propose a generic construction to achieve collusion safety at the cost of doubling the key size from the IND-CPA secure PRE, enjoying a much better generality and efficiency than the existing technique by secret sharing.
A Unified Analysis of Refresh Gadgets in the Random Probing Model
Masking is a standard countermeasure against side-channel attacks on embedded cryptographic implementations. Its security is commonly analyzed in the random probing model, which offers a useful trade-off between realistic leakage assumptions and tractable security proofs. Recent years have seen the emergence of several masking compilers based on compositional security frameworks such as general/cardinal random probing composability (RPC). Most of these approaches rely on dedicated refresh gadgets whose structure is often tightly coupled to the targeted security analysis.
In this work, we investigate the impact of refresh gadgets on the random probing security of masking compilers within the recent general/cardinal RPC frameworks. We formalize two broad families of refresh gadgets, namely direct and zero encoding-based refreshes, define ideal constructions for both families under explicit randomness and uniformity conditions, and extend the compositional analysis of zero encoding-based refreshes.
We then introduce an atomic refresh function capturing the core operation underlying most refresh gadgets from the literature. This abstraction allows us to express and analyze existing constructions within a unified framework, derive their cardinal/general RPC envelopes, and obtain analytical formulas for several of them. Finally, we compare ideal and concrete refresh gadgets on masked implementations of AES and Raccoon. Our results provide a systematic comparison of the security-complexity trade-offs achieved by current refresh strategies.
Accelerating Pollard Rho with GPU Field Arithmetic on NVIDIA Blackwell
We show how far Pollard rho can be accelerated on current NVIDIA GPUs by rebuilding its field arithmetic around the hardware, with the Certicom challenge ECC2K-130, the Koblitz curve $y^2+xy=x^3+1$ over $\mathbb{F}_{2^{131}}$ with an expected cost of $2^{60.9}$ iterations, as the benchmark. None of the speedup comes from changing the algorithm. It comes from a packed normal-basis representation in which every Frobenius power is a permutation network instead of a chain of squarings; from the carry-less multiply that CUDA 13.3 exposes in PTX (clmad), which forms a 131-bit product in six instructions; from three-input logic instructions for everything around it; and from a batch size, launch geometry and compact tiled state chosen by measurement against the pipes they load. Across sixteen paired steps, each held to a rule written down before it ran, these take one RTX PRO 6000 Blackwell from a $0.85$ billion iterations per second bitsliced control to $14.64$ in the audited campaign build, a $17.2\times$ gain (representation and arithmetic $6.3\times$, geometry $1.5\times$, memory layout $1.3\times$, clmad $1.2\times$), and a later build reaches $15.88$. That is about $230$ times the best published 2010 GPU kernel per card and puts the whole challenge under five GPU-years: five cards expect a solution within a year, a thousand in about three days. The gains depend on the die. clmad issues ten to eighteen times faster per SM-clock on the data-centre parts than on the workstation part, so the same change can win on one Blackwell part and lose on another; we report twelve GPUs from Turing to Blackwell per card, per SM and per dollar, and the CPU instruction sets that play the same role. Upper bounds derived from measured pipe rates leave about $1.5\times$ of headroom on one RTX PRO 6000, at $24$–$26$ billion iterations per second for any walk with one addition per step. The same levers applied to Pollard rho on NIST P-256 and P-384 on the same card give $1.52\times$ and $2.61\times$, to $1.632$ and $0.548$ billion iterations per second, which still leaves P-256 about $6\cdot10^{21}$ card-years away. We also separate the $\sigma$-walk from a table walk whose $20.08$ was measured under a cycle rule later found unsound (the exact rule runs at $8.24$), measure the walk constant at $2^{60.91}$–$2^{60.92}$ iterations, and report an FPGA engine at $8.25$ billion iterations per second on one AWS F2 and a campaign that walked $2^{56.68}$ iterations, $5.4\%$ of the expected work. Every number cites an evidence record; the code, data, evidence and a Dockerfile whose image starts the ECC2K-130 walk are at https://github.com/aburan28/rho-blackwell. None of this improves on the generic-group bound, and we do not claim that it does.
Going Faster: Privacy-Preserving Shortest paths from Start to End (Extended Version)
Finding shortest paths in graphs is a fundamental combinatorial optimization problem with numerous applications, e.g., in graph centrality measures, computational biology, and business process analysis. To address privacy constraints in such applications, Secure Multi-Party Computation (SMPC) protocols can compute the lengths of shortest paths on secret-shared graphs. Many such protocols have been proposed in the past, but they only compute the lengths of the shortest paths and not the paths themselves.
In this paper, we close this gap by proposing two SMPC protocols that output secret-shared shortest paths. The first composes sub-protocols to calculate predecessors, to follow them, and to reorder wrongly positioned padding. Our second protocol optimizes the predecessor-following by decomposing it into sub-functionalities and proposing new sub-protocols for each. Further, the padding-reorder is replaced by a graph transformation.
We evaluate our protocols across multiple network and security settings. Our optimized predecessor-following is up to 23 times faster than prior art, and our graph transformation is orders of magnitude faster than the padding-reorder. Overall, our second protocol is 5% to 49% faster than the first protocol due to the predecessor-calculation dominating the runtime on large graphs.
Finally, we introduce a novel demultiplex protocol that, in fast networks, outperforms prior protocols on vector sizes up to 500, and on all evaluated vector sizes in slow networks. Due to the ubiquity of demultiplexes, this protocol is of independent interest.
FlatMerkle: Logarithmic-Space Inclusion Proofs over a Single Linear Hash Stream
Merkle trees are the standard way to obtain logarithmic-size, logarithmic-time
inclusion proofs over a large dataset, but they require a tree-shaped hash
structure distinct from the ordinary, linear (Merkle--Damg\aa rd) hashing that
most deployed systems -- including Bitcoin's own transaction and witness
hashing -- actually perform. We present FlatMerkle, a construction that
achieves the same asymptotic guarantees, $O(\log N)$ proof size and
$O(\log N)$ verification time, over a single ordinary linear hash stream, by
periodically re-injecting the hash function's own past internal states
(``checkpoints'') back into the stream as ordinary message content. The
result is a flat byte sequence whose digest is a single, unmodified
invocation of the underlying hash function -- syntactically an ordinary
digest of an ordinary byte string, not a distinguishable commitment format
-- while still supporting compact inclusion proofs for any element, and
compact proofs that a published file is malformed, so that an honest party
can always answer a malicious committer in logarithmic space. We give the recursive
construction, a closed-form formula locating any element in the structured
stream, worked examples with illustrations, a security reduction to free-start
collision resistance of the hash function's compression step, an optimal
element-size analysis for both a flexible toy primitive and real SHA-256,
a batched multi-element proof construction, a measured construction-speed
comparison against Merkle trees, a concrete application to committing data
inside a Bitcoin transaction annex (BIP-341), a design sketch using that
application as a data-availability layer for an optimistic Bitcoin rollup,
a from-scratch gas-cost comparison, on Ethereum, Rootstock, and Arbitrum,
of an in-contract FlatMerkle commitment against an in-contract Merkle
tree, tracing the three chains' differing verdicts to specific protocol
design choices rather than to anything intrinsic to either construction,
and a comparison against the closest prior art we are aware of,
authenticated append-only skip lists.
Ziren: Succinct Arguments for MIPS32 Execution
Proving MIPS32 execution requires preserving branch-delay semantics while controlling the cost of heterogeneous instruction constraints. We present Ziren, a production zkVM for MIPS32r2 that supports 77 user-mode integer instructions and has proved Ethereum mainnet blocks end to end. Its arithmetisation embeds the program-counter pair in per-opcode instruction frames, eliminating the central CPU table. Each shard is proved with a single lookup argument, a zerocheck and a jagged commitment opened
through batched WHIR; recursive aggregation uses an enumerated verifying-key allowlist.
We mechanically extract 104 determinism theorems from the prover’s constraint description and discharge them in Lean 4. The kernel-checked proofs cover 57 of the core machine’s 62 chips, including precompiles, and establish unique outputs for fixed inputs under the declared lookup-table assumptions. The exclusions are three preprocessed tables and two SHA-256 control chips. We also formulate a cost model that separates trace cells and bus interactions per guest instruction from hardware-dependent proving throughput, accounting for instruction frames, shard-boundary memory rows and precompile expansion.
On the evaluated Ethereum blocks, warm proving throughput reaches 12.0 MHz on one NVIDIA RTX 5090 GPU and 75.8 MHz on eight. Each proof stage has more than 100 bits of interactive soundness; a union bound for a tree with 149 core-schedule proofs and one root gives 93.5 bits of interactive composite security. End-to-end knowledge soundness remains conditional on five stated hypotheses, including enforcement of the recursion relation and computational binding of the cross-shard digest. No numerical security bound is established for that digest; the interactive estimates therefore do not quantify the full security of the deployed non-interactive proof.
Unified Dual Attack Analyses: Covariance-Based Score Distribution Prediction for LWE
The Learning with Errors (LWE) problem underpins many post-quantum cryptosystems, including the NIST-selected CRYSTALS-KYBER and CRYSTALS-DILITHIUM. Recent dual attacks have demonstrated remarkable effectiveness against concrete LWE-based schemes, with some claims suggesting that the security of CRYSTALS-KYBER may be reduced below the NIST threshold. However, the analysis of the score distribution for the correct guess in dual attacks has consistently relied on a flawed independence assumption, leading to variance estimates that are far smaller than the true score variance. This issue has been highlighted in several studies. For instance, Bashiri and Wiemers (JMC 2025) proposed an estimate of the variance, yet our experiments reveal that their approach performs poorly in medium-to-high dimensions. On the other hand, many works have characterized the success probability of dual attacks, but these are either based on the BDD problem or limited to specific attack types, lacking a unified analytical framework for dual attacks on LWE. These theoretical gaps motivate us to develop a unified estimation of the expectation and variance of the score in dual attacks.
In this paper, we propose a unified predictive model for the expectation and variance of the score, covering three types of dual attacks: the original dual attack, the dual attack with modulus switching, and the dual attack with decoding (Crypto 2025). Our key observation is that the cosine of the angle between different short vectors follows a normal distribution, which we use to estimate the covariance between individual scores. By decomposing the score expression into a combination of simple distributions, we obtain estimates for the expectation and variance of individual scores, and combine these with the covariance to derive closed-form estimates for the total variance. Experiments show that our estimates achieve high accuracy and outperform previous work in medium-to-high dimensions. We also extend the prediction method of Ducas and Pulles (JOC 2026) for the score of incorrect guesses to a more general setting and, together with our predictive model, provide an extended characterization of the tail behavior.
DPF-SGD: Byzantine-Robust Differentially Private Federated SGD with Exact Optimality Guarantees
Federated optimization enables collaborative learning over decentralized data but is accompanied by significant privacy risks due to the exchange of model updates. While differential privacy (DP) provides formal protection, optimization accuracy is often degraded, and robustness becomes particularly limited in the presence of Byzantine agents. A Byzantine-robust, differentially private federated SGD algorithm, DPF-SGD, is proposed, in which private step sizes are integrated with a DP noise–decay schedule to regulate gradient updates. To further enhance robustness, a privacy-preserving comparative elimination (PPCE) filter is developed to suppress Byzantine contributions during aggregation while preserving privacy guarantees. Almost sure convergence to the global optimum under ϵ-differential privacy is established, despite persistent noise and adversarial behavior. Experiments on synthetic and MNIST datasets demonstrate oneto two-order-of-magnitude reductions in final optimization error relative to DP baselines.
A Graph-Based Analysis of Comparability, Scale, and Attribution in Private Transformer Inference
Rising privacy concerns around large language models have accelerated research in private Transformer inference (PTI). Synthesizing the empirical claims in this line of research, however, is hindered by multi-dimensional cryptographic progress and inconsistent evaluation contracts. In this work, we systematize the field by constructing an empirical graph of 62 PTI systems, mapping system attributes to node features and evaluation compatibility to edges. A three-tiered analysis of this graph illuminates the state of private inference. Node-level attribution shows that cryptographic progress drives performance gains across most systems, yet always co-occurs with other factors (model fidelity, hardware, cost accounting). Edge-level auditing shows that only 1 of 1891 candidate system pairs is directly comparable under shared assumptions. Finally, graph-level analysis shows that the scaling frontier of private inference has plateaued at 13B parameters and projects the cost of deploying current PTI techniques on production-scale Transformers. Overall, this graph-based framework equips the community to evaluate PTI claims transparently and channel technical speedups into deployment-scale private inference.
Fair and Efficient Helper-Aided MPC with Cheater Identification
Secure multi-party computation (MPC) enables privacy-preserving tasks such as auctions and voting. In practice, more than half of the parties may collude, making security against a dishonest majority desirable. Unfortunately, dishonest-majority MPC suffers from high communication and can achieve only abort security. For instance, in an auction, an adversary may abort after learning the outcome and rerun the protocol with a higher bid.
Helper-aided MPC mitigates these limitations by introducing a semi-honest, non-colluding helper, a model that naturally fits settings with a central governing or coordinating entity and provides strong guarantees even when up to $n-1$ parties are malicious. The model assumes that the adversary can either semi-honestly corrupt the helper or maliciously corrupt up to $n-1$ parties (excluding the helper). While existing helper-aided protocols are fair i.e. either all parties receive the output or none do; they still allow the adversary to abort without any penalty and deny output to all parties. This behavior is undesirable in practice, as parties may incur the cost of computation without receiving the output.
In this work, we design efficient helper-aided MPC protocols that achieve identifiable fairness: either all parties obtain the output, or—if an abort occurs—no party receives the output, and the honest parties identify at least one common cheater.
We propose two protocols, $\mathsf{Alhena}$ for synchronous networks and $\mathsf{Wasat}$ for asynchronous networks which provide the stronger guarantee of identifiable fairness compared to the state-of-the-art fair protocols $\mathsf{Asterisk}$ (Kamarkar et al. IEEE S&P 2024) and $\mathsf{Castor}$ (Kamarkar et al. IEEE S&P 2026) in the respective network settings. Our experiments show that, in the online phase, $\mathsf{Alhena}$ and $\mathsf{Wasat}$ achieves speedups of $4-12.5\times$ and $2.5-5\times$ over $\mathsf{Asterisk}$ and $\mathsf{Castor}$ respectively. Furthermore, in the preprocessing phase, $\mathsf{Wasat}$ exhibits speedup of $\approx 3\times$ over $\mathsf{Castor}$. Notably, our protocols are designed in such a way that the online performance remains unaffected by active misbehaviour.
Efficient Single-Server Online-Offline PIR without Periodic Preprocessing
Private Information Retrieval (PIR) allows a client to retrieve an entry from a public database without revealing the entry of interest. Standard PIR, however, requires the server to perform expensive computation that is linear in the database size per client query. To reduce this online cost, Online-Offline PIR (OO-PIR) was proposed, allowing the client to precompute a query-independent hint table that enables sublinear online
query complexity. Unfortunately, existing OO-PIR protocols require either a non-colluding two-server setting or a single-server setting with expensive periodic preprocessing, where the entire hint table must be rebuilt after a limited number of online queries. This results in extremely high bandwidth or computation overhead.
We present ESCAPE, a novel OO-PIR protocol for the single-server setting that completely eliminates the expensive periodic preprocessing, supporting unlimited online queries in sublinear time with low constant response bandwidth. The core innovation in ESCAPE lies in reconciling a new hint sampling strategy with Linearly Homomorphic Encryption (LHE) to conceal the correlation between any hint and any online query, while allowing the consumed hint to be refreshed on the fly in sublinear time. We design a random sampling structure that aligns with deterministic, precomputable linear functions, enabling the protocol to exploit the streamlined preprocessing of efficient LHE instantiations. We fully implement ESCAPE, evaluate it on large-scale databases, and release our implementation as open source. Experimental results show that ESCAPE radically reduces end-to-end latency to under a second for 1-8 TiB database sizes and 8-16 KiB entries, achieving up to two orders of magnitude lower bandwidth and up to three orders of magnitude lower computation than state-of-the-art PIR.
Leakage-Resilient Incompressible Cryptography: Constructions and Barriers
We introduce Leakage-Resilient Incompressible cryptography, which
simultaneously addresses two variants of side-channel attacks that have been tackled in theoretical cryptography. Leakage-resilience seeks to provide
security against an adversary who learns a part of the secret-key and the
entire ciphertext or signature; conversely, incompressible cryptography
provides security against an adversary who learns the entire secret-key, but
only a part of the ciphertext or signature. However, constructions in either
of these security models can fail against an attack in the other model. In
this work, we define a new model of security that subsumes both
leakage-resilient cryptography and incompressible cryptography, and we
present several non-trivial positive and negative results.
On the positive side, first we present a transformation from incompressible
symmetric-key encryption (SKE) to leakage-resilient incompressible SKE in
the information-theoretic setting. Next, as one of our main results, we
construct a leakage-resilient incompressible public-key encryption (PKE),
combining an incompressible SKE and a new primitive that we call
leakage-resilient non-committing key encapsulation mechanism (LR-NC-KEM).
While an information-theoretic incompressible SKE suitable for use in both these constructions already exists in the literature (Dziembowski, CRYPTO 2006), we present a new construction achieving ciphertext-rate $\frac{1}{2}$ and compression-rate $\frac{1}{2}$, using an appropriate notion of invertible extractors; this leads to corresponding improvements in the final parameters we obtain in these constructions. We also construct a leakage-resilient incompressible signature scheme in the classical random oracle model, assuming $(\mathsf{DCR}\text{ or }\mathsf{LWE})$ and the Decisional Linear assumption, with signature-rate and compression-rate $1-o(1)$ and leakage-rate $1$.
On the negative side, we show barriers to significantly improving the
parameters we obtain, by showing impossibility of basing the security
of such improved schemes on blackbox reductions.
Apart from the general framework and the specific results we obtain, some of
the intermediate tools that we define and instantiate, like LR-NC-KEM and
invertible extractors, may be of independent interest.
Invisible Traces: Subversion Attacks on Batch-Issued Credentials
All EU member states are required to roll out a digital identity system - the European Digital Identity (EUDI) wallet - by the end of 2026. Strong privacy is at the core of the underlying regulation, which mandates the EUDI wallet to support selective disclosure and unlinkability. The wallet currently being developed relies on the batch issuance of one-time ECDSA credentials that sign attributes through individually salted hashes for selective disclosure. This solution is known to achieve only a weak form of unlinkability, where the credential issuer must be honest: a malicious issuer could trace users through the salted hashes it signs and the signature value itself. But such a tracing attack requires the issuer to store all signed data and communicate with the verifying parties for tracing, which can be argued to be too cumbersome or obvious to happen in reality. In this work, we therefore initiate the study of a more subtle type of subversion attacks. Therein, the issuer can deviate from the issuance protocol, with two goals:
(i) enabling verifiers in possession of a short tracing key to de-anonymize users and
(ii) keeping this deviation undetectable from users.
We formalize unlinkability against such subversion attacks, and show that batch-issued credentials with salted hashes do not achieve that form of privacy. We present several undetectable subversion attacks against batch-issued ECDSA credentials and suggest lightweight mechanisms to provably mediate them.
Cube Attacks with Elimination Strategy: Key Recovery Attacks on Trivium
In this paper, we present a novel framework for cube attacks named cube attacks with elimination strategy. The core idea is to find specific key conditions and cubes such that their superpolies under these key conditions can be efficiently computed. By recovering these conditional superpolies, we can solve the corresponding equation system and thereby retrieve key information. If a sufficient number of such key conditions can be found, the attack can be extended to a larger key space. To apply this framework in practical attacks, we propose the following techniques.
First, we propose a nested coefficient solver that combines variable substitution and symbolic computation to efficiently recover superpolies, and present the conditional monomial prediction technique to rapidly recover conditional superpolies. Second, by combining numeric mapping with monomial prediction techniques, we propose an automated cube search algorithm that is capable of generating a large number of good cubes for attacks. Finally, we develop two kinds of testing methods, which are used to efficiently extract substantial key information from large-scale equation systems.
To illustrate the power of our techniques, we apply them to Trivium. As a result, for 840 rounds of Trivium, a practical key recovery attack is mounted with complexity below $2^{55}$ and a success rate 77.8\%. For 845 rounds, we present a practical key recovery attack with complexity below $2^{56}$ and a success rate 98.1\% for $2^{80} \times 59.1\%$ keys. For 855 rounds, we present a theoretical weak-key recovery attack for $2^{74}$ keys. To the best of our knowledge, these are the best practical and theoretical attacks on Trivium. The improvements in the number of rounds reached are 13 for practical attacks and 4 for theoretical attacks, respectively.
What Happens When Integrating Modulus Switching and Lossy Source Coding: A New Dual Attack Variant on LWE
The threat of large-scale quantum computers to classical public-key cryptograp-hy has motivated the development of post-quantum cryptographic schemes. Among these, lattice-based constructions have become the mainstream choice in the ongoing NIST standardization process. The security of these schemes typical-ly relies on the hardness of the LWE problem, and the dual-sieve-FFT attack is widely recognized as one of the most effective approaches against it. Recent improvements by MATZOV and Carrier et al. have significantly advanced its efficiency. In this paper, we propose a new variant of the dual-sieve-FFT attack that integrates modulus switching and lossy source coding. We provide a theoretical analysis of the integrated approach and show that the enumeration size in the FFT step can be reduced from 𝑞^𝑛_fft to 𝑝^𝑘_fft (with 𝑝 < 𝑞, 𝑘_fft < 𝑛_fft), leading to lower FFT cost and decoding cost. When applied to KYBER, our variant achieves better total complexity than the attack using only lossy source coding, although the improvement is modest. More importantly, the decoding and FFT costs are reduced by 1–6 bits and 2–7 bits, respectively, in most parame-ter settings. These reductions are practically meaningful, especially in multi-target attack scenarios where the FFT and decoding steps are amortized over multiple targets.
Proving Threshold Regev PKE from Adaptive Hint-MLWE: Efficient, Non-interactive, and CCA Secure
Threshold public-key encryption (tPKE) has recently attracted renewed
interest, largely due to NIST's call for Multi-Party Threshold Cryptography. While classical tPKE has approached a high state of maturity, its post-quantum counterpart has not. Indeed, thresholdizing the celebrated lattice-based Regev PKE, which forms the basis of ML-KEM, remains unsatisfactory. Interestingly, how to thresholdize Regev PKE has not fundamentally changed in over a decade --- the only thing that has gradually progressed is its security analysis. To this day, it remains open whether threshold Regev can be proven secure while simultaneously satisfying a polynomial modulus, non-interactive decryption, and CCA-compatibility, each of which is essential for practical deployment.
We answer this affirmatively, providing the first proof that threshold Regev is secure under the MLWE assumption while satisfying all three requirements. In fact, we prove that it satisfies a very strong form of simulation-based security --- even stronger than what was known under a super-polynomial modulus --- allowing the adversary to obtain partial decryptions even of the challenge ciphertext. At the technical heart of our result is the adaptive hint-MLWE (AHMLWE) problem, an adaptive variant of hint-MLWE where the adversary obtains hints on the MLWE secret with adaptively chosen coefficients. We show that AHMLWE reduces tightly to standard MLWE, which may be of independent interest.
Witness-Succinct UC-Secure SNARKs with Weaker Trust Assumptions
Zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs) are foundational cryptographic primitives enabling privacy-preserving and verifiable computation. However, most existing zkSNARK constructions rely on strong trust assumptions—typically a fully trusted setup—which undermines their applicability in adversarial or decentralized environments. Although transparent zkSNARKs remove this assumption, they typically do not satisfy strong composability guarantees such as Universal Composability (UC).
In this work, we present the first framework for constructing UC-secure zkSNARKs under weaker trust assumptions, based on a new primitive called Key-Updatable Polynomial Commitments (KU-pCom). This primitive enables publicly verifiable commitment-key updates, requiring only one honest update rather than a fully trusted setup. Our compiler transforms any Simulation-Extractable zkSNARK into a UC-secure variant by composing it with a KU-pCom scheme. We instantiate our framework in two settings: (1) using the structured, trusted setup of the KZG commitment scheme, and (2) an instantiation based on the lattice-based commitment scheme of Hwang et al. (Crypto 2024). We implement both instantiations and provide an end-to-end benchmark of UC-secure zkSNARKs with succinctness. Compared to prior UC-secure NIZKs that sacrifice succinctness (e.g., Abdolmaleki et al., CSF 2024), our work demonstrates that UC security, succinctness, and practical efficiency can be simultaneously achieved, establishing a new foundation for succinct, composable proof systems under weaker trust assumptions.
HOVER: Higher-Order Vanishing Endomorphism Recovery
Higher-Order Vanishing (HOV), introduced by Hemmert and Wiemers at CRYPTO 2026, distinguishes Goppa codes and was recently extended to McEliece key recovery. We introduce a new variant of HOV, HOVER (Higher-Order Vanishing Endomorphism Recovery), that replaces the costly low-rank direction-search phase of HOV with a much faster linear algebra step. Our attack is based on the observation that the first catalecticants (the coefficient matrices of first partial derivatives) of the public HOV kernel define a contraction tensor; HOVER computes the coefficient endomorphisms that preserve all relations of this tensor. In the clean case, in which the scalar-extended HOV kernel is spanned by exactly the $m$ hidden Frobenius directions, this public algebra is $\mathbb{F}_{2^m}$, and the eigenspaces of a field generator are exactly those directions, already ordered by Frobenius. We give a basis-invariant construction, a structural classification of its possible matrix-algebra outputs, and explicit acceptance conditions that return $\bot$ rather than an uncertified output. During our end-to-end public-only experiments, we recovered keys for five Technology Innovation Institute (TII) McEliece challenges, including TII-252, whose label originally represented a $2^{252}$ brute-force enumeration model. However, our analysis does not indicate that HOVER would threaten Classic McEliece parameters in its present form. Lastly, we note that HOVER's main cryptanalytic shortcut was discovered with a large language model, underscoring the strong potential of AI cryptanalysis.
Causal Awareness in End-to-End Encrypted Group Messaging
Chats do not always unfold in a single clear order. Two users may send messages before information about either message reaches the other sender. Such messages are concurrent, but most instant messengers provide no way for users to recognize this relationship. Chen and Fischlin (Eurocrypt 2024) studied this limitation in the two-user setting, showing that Signal does not expose enough information to recover the context in which a message was sent; they proposed a fix. We study group chats, where a user may need to reason about ordering and concurrency among other users' messages. This can become a security problem when network delays or adversarial interference cause an authentic message to be shown in a misleading context.
Event ordering is a classical problem; Lamport clocks and vector clocks are standard starting points. Secure messaging needs a different treatment because communication is asynchronous, bandwidth is limited, and added latency is undesirable. To address the problem under these constraints, we introduce causal awareness: the ability of a receiver to reconstruct a specified part of the causal context in which an accepted message was sent. Senders transmit records of what they have sent and received. Receivers verify these records and compare them with their own.
We develop a framework of correctness and security notions for causal awareness in group chats. Our definitions are parameterized by how much causal information receivers must recover. We give baseline constructions and prove their properties. We also introduce checkpoint-aided and server-aided variants of the framework and prove that, in each, our notions of correctness and integrity imply causal awareness. We discuss how causal information could be surfaced in a messenger's user interface.
Succinct Homomorphic MACs from Groups and Applications
Homomorphic message authentication codes (HMACs) allow users to authenticate data using a shared secret key, while supporting computation over authenticated data. Given data $(m_1, \ldots, m_n)$ and their tags $(\sigma_1, \ldots, \sigma_n)$, anyone can evaluate a circuit $C$ on the data and tags to produce a succinct tag authenticating the output $C(m_1, \ldots, m_n)$. Importantly, tags remain succinc -- of size polynomial in the security parameter $\lambda$ -- regardless of the size of $C$. This work introduces an enhanced variant of HMACs called algebraic HMAC (aHMAC), in which all tags (input and output) take the form $\Delta \cdot m + K$, as in standard information-theoretic MACs.
We construct an aHMAC from group-based assumptions, including variants of the DDH and DCR assumptions, and use it to obtain group-based constructions of several cryptographic primitives:
- Succinct CDS for circuits. For any $P: [N]^k \to [N]$ represented by circuit, we obtain a Conditional Disclosure of Secrets protocol with poly$(\lambda, k, \log N )$ communication.
- Succinct PSM for simple programs. For any $P:[N]^k \to [N]$ represented by a truth-table or shallow branching program, we obtain a Private Simultaneous Messages protocol or a garbling scheme with poly$(\lambda, k, \log N )$ communication.
- Constrained PRFs for circuits. We obtain the first group-based constrained pseudorandom functions for general circuits, improving over a previous construction for NC1 circuits.
Prior to our work, these applications could only be obtained from lattice assumptions or indistinguishability obfuscation.
Master-Key Recovery from Internal Activation Leakage in ReLU Realizations of Camellia
This paper investigates functional correctness and masterkey reconstruction in explicitly constructed rectified linear unit (ReLU) implementations of Camellia-128, Camellia-192, and Camellia-256. Exact neural realizations of Boolean gates, S-box selectors, and bit permutations provide a framework for reproducing Camellia on binary inputs. We present a component-wise correctness argument and report known-answer-test agreement for Camellia-128. We then analyze how selected whitening and round-key quantities determine the external master key through public key-schedule identities. Inverse rotations of suitable subkey pairs recover the required key components, whereas prewhitening-key recovery alone is insufficient for complete reconstruction of the longer keys. Under explicitly constructed synthetic internal-oracle access, symmetric real-valued perturbations identify target subkey bits, requiring 128 and 256 query pairs for the coordinate-wise Camellia-128 and Camellia-256 procedures, respectively. A separate Camellia-192 experiment validates deterministic key-schedule inversion under direct access to DNN-generated round keys. Across 1,000 independently sampled master keys per variant, all three procedures achieved exact recovery in every trial, yielding 3,000 successful recoveries out of 3,000 trials, with zero recovery failures and no Camellia-192 complement-consistency failures. These results validate conditional master-key reconstruction under the specified internal-access models and highlight the distinction between binary functional correctness and security under stronger access assumptions. They do not establish plaintext/ciphertext-only attacks against standard Camellia.
On Secure Sorting and Its Application to Privacy-Preserving Graph Pattern Matching
Sorting in secure computation has been studied almost as long as there have been implementations of multi-party computation (Wang et al., AsiaCCS'10). More recent advances include completely secure implementations (revealing nothing other than the list size) that have used Quicksort (Araki et al., CCS'21) and radix sort (Asharov et al., CCS'22). For the first time, we extensively compare the two variants across a range of parameters and for both honest- and dishonest-majority computation. We then apply secure sorting to improve sparse matrix multiplication without oblivious RAM based on recent work by Damie et al. (CODASPY'26). Our main contribution here is to produce an output in the same format as the inputs to the multiplication. This is needed for repeated multiplication of graph adjacency matrices, which we use to find cycles in graphs. Such cycles have been associated with money laundering, and this also applies to another graph pattern dubbed scatter-gather, which we can detect with the same approach. Our work therefore can be applied to privacy-preserving anti-money laundering detection.
Quick Draw Queries: Lightweight Searchable Public-key Ciphertexts with Hidden Structures via Non-Interactive Key Exchange
Basically, public-key searchable encryption schemes require a linear search time with respect to the total number of ciphertexts. Xu, Wu, Wang, Susilo, Domingo-Ferrer, and Jin (IEEE Transactions on Information Forensics and Security, 2015) introduced Searchable Public-Key Ciphertexts with Hidden Structure (SPCHS). In SPCHS, ciphertexts associated with the same keyword are linked through a hidden structure that can be revealed using a trapdoor. This enables efficient extraction of matching ciphertexts and achieves optimal asymptotic search efficiency by traversing only the result set. However, a drawback of the SPCHS scheme and its subsequent works is that they are all pairing-based or rely on identity-based encryption (IBE) as a foundational component. To improve efficiency, this paper proposes a generic construction of SPCHS. Our core building block is Non-Interactive Key Exchange (NIKE), and the remaining components are symmetric-key primitives, namely secret-key encryption and a pseudorandom function (PRF). In particular, our search algorithm depends solely on these symmetric-key primitives and is independent of any public-key primitives. We implement the most efficient instantiation of the generic construction using Diffie-Hellman NIKE, an HMAC-based PRF, and AES. Our evaluation demonstrates that the search time of the DH-based instantiation is over 250 times faster than that of the asymmetric pairing-based scheme by Wang et al. (IEEE Transactions on Industrial Informatics, 2020). Moreover, we reduce the ciphertext size by a factor of approximately 10. In addition to this practical contribution of significantly improving efficiency, the proposed generic construction also makes a theoretical contribution by enabling the realization of the first set of post-quantum SPCHS schemes based on lattices, isogenies, and codes.
Game-Theoretically Fair Coin Toss from Random Walk Against $n-1$ Corruptions
Coin-tossing protocols allow mutually distrustful parties to generate trusted randomness. While strong fairness is impossible against a corrupted majority, Chung et al. (2018) introduced cooperative-strategy-proof (CSP) fairness for multi-party coin tossing, under the assumption that each party gets utility only when the outcome matches its public preference. CSP-fairness ensures that no PPT adversary can increase the expected joint utility of the corrupted parties through deviation. Since then, a line of work (Wu et al., 2022; Thyagarajan et al., 2024; Zhang and Wu, 2025) has explored the landscape of CSP-fair coin tossing and shown that CSP-fairness can be achieved even against a corrupted majority.
In this work, we study CSP-fair multi-sided coin tossing against up to $n-1$ corruptions when parties may have arbitrary utilities over the possible outcomes. Perhaps surprisingly, we show that CSP-fairness against any semi-malicious adversary corrupting up to $n-1$ parties is achievable for every full-row-rank utility matrix. Our construction can also be upgraded to fully malicious security. More generally, we introduce an abort-safe opening order condition on the utility matrix that suffices for resilience against $n-1$ corruptions.
Our construction uses a public random walk whose state dynamically determines the distribution of the eventual outcome. The parties jointly generate randomness deciding each walk step using commit-and-reveal. When a party aborts, the protocol adjusts the transition distribution of the walk based on the parties' utilities. These adjustments, together with a carefully chosen opening order, prevent profitable deviations.
We also identify conditions on the utility matrix under which CSP-fair coin tossing is impossible. For three parties, our positive and negative results together give a complete characterization of the utility matrices for which CSP-fairness against two corruptions is achievable.
Accountable Verifiable Secret Sharing and Applications
Verifiable Secret Sharing (VSS) ensures consistent sharing and correct reconstruction, but does not identify the shareholders involved. Traceable Secret Sharing (TSS) expands secret sharing with two guarantees: $\textit{traceability}$, which identifies the makers of a reconstruction box through black-box queries; and $\textit{non-imputability}$, which prevents false accusations against honest shareholders. However, full traceability is practically expensive: existing Shamir-based schemes require multiple carefully chosen queries to a $\textit{stateless}$ reconstruction box. Moreover, Goyal et al. (ePrint 2025/1980) show that the strongest form of black-box tracing is incompatible with simultaneously achieving non-imputability and tracer secrecy. We introduce $\textit{Accountable VSS}$ (Acc-VSS), a practical extension of VSS that achieves the next-best goal: $\textit{accountability}$, a strict relaxation of traceability requiring that (i) the contributors to every accepted reconstruction be publicly identifiable from its transcript with a $\textit{single}$ query, and (ii) no honest shareholder be falsely accused, even by an adversary holding all other shares. Accountability thus replaces black-box, multi-query tracing with a transcript check executable by any external verifier or smart-contract judge. In this paper, (i) we give a generic transformation from any computationally secure Shamir-based VSS to Acc-VSS, adding only one field element per share; it uses a long-term identity secret to each share and a conjunctive NIZK to bind partial reconstructions to the shareholder and the dealer's commitments; (ii) we instantiate it with Feldman and Pedersen VSS and prove the security of both schemes; (iii) we prove a self-contained $\textit{single-query}$ impossibility lemma motivating our relaxation; and (iv) we show how Acc-VSS uniformly yields accountable threshold ElGamal decryption, Schnorr/FROST signing, and distributed key generation. For the benchmarked VSS-based threshold-decryption protocol, accountability adds at most $20.3\%$ end-to-end overhead for $n=20$ and less than $6\%$ for $n=100$. Encrypted mempools, end-to-end-verifiable e-voting tallies, and validator-slashing in proof-of-stake systems all reduce to this framework.
On the Expected Number of Iterations in ML-DSA Signing: A Complete Accounting of the Rejection Conditions
FIPS 204 Table 1 gives the expected number of iterations of the ML-DSA signing loop (ML-DSA.Sign_internal, Algorithm 7), citing CRYSTALS-Dilithium Equation (5). That equation covers only the validity checks on line 23 ($\lVert z \rVert_\infty$ and $\lVert r_0 \rVert_\infty$) and omits the two encoding-correctness checks on line 28 ($\lVert c \cdot t_0 \rVert_\infty$ and the hint weight), a scoping distinction the Dilithium specification states explicitly and FIPS 204 does not reproduce. We give a complete accounting of all four conditions. The $z$ check on line 23 is computed exactly by counting; the $c \cdot t_0$ term follows a closed-form Irwin-Hall tail, restating a peer-reviewed result by Yan, Luo and Wang; the hint-weight term's per-coefficient probability, conditioned on line 23 having passed, does have a closed form, but the tail of the sum over $256k$ such coefficients does not, since their probabilities are unequal, random, and correlated with each other, so we give the conditioned per-coefficient probability in closed form and estimate its tail by Monte Carlo. The corrected expected iteration counts are 4.36, 5.14 and 3.91 for ML-DSA-44, -65 and -87, matching a real end-to-end measurement to within 0.14% and already reflected in NIST's own errata to FIPS 204.
Critical-Round Special Soundness for Multi-Round Proofs
Multi-round public-coin proof systems have progressed rapidly, yet their simulators and extractors are rarely used as building blocks in other protocols, unlike those of 3-move $\Sigma$-protocols. Prior work [Abe et al., Eurocrypt~'26] addressed the simulator side with critical-round zero-knowledge.
In this paper, we address the extractor side and introduce critical-round special soundness (CRSS): a witness is extractable from a small critical subtree of transcripts that branches only from one round, while the full tree of transcripts serves only as a fall-back that outputs a solution to a hardness assumption. We first establish an extract-or-extend theorem that bounds the failure probability of the critical extractor even when the critical-round challenges are chosen by the adversary, and then show that KKW-style MPC-in-the-head proofs, KZG-compiled polynomial IOPs including Plonk, and Protogalaxy satisfy CRSS. We also give a corresponding tree-extraction result for the sumcheck sub-protocol of Spartan.
We present three applications: a hash-based witness sharing scheme that verifiably secret-shares an NP witness without interaction among recipients, the first offline trapdoor-extractable trapdoor commitment from a multi-round proof, where a trapdoor is extracted immediately upon a double opening, and a parameter improvement for the multi-round Fischlin transform [Rotem-Tessaro, Crypto~'25] that reduces the prover's complexity in practice.
DTRU: A Versatile, Compact, Simple, and Robust NTRU KEM with Double $E_8$ Encoding
Responding to China's 2025 call for commercial cryptographic standards mandating 128-bit, 256-bit, and 512-bit security (optional 384-bit), we propose DTRU, a versatile, compact, simple, and robust NTRU-based key encapsulation mechanism (KEM). Our principal design contribution is double $E_8$ encoding, which constructs 16-dimensional lattice codes from $E_8$ with low decoding complexity. We further provide a detailed analysis of decryption-failure probability under this encoding mechanism.
DTRU's design achieves a careful balance among versatility, compactness, simplicity, and robustness. To accommodate diverse application requirements, it supports multiple ring structures, including power-of-two cyclotomic rings, tricyclotomic rings, and large-Galois-group prime-degree prime-ideal number fields (LPPNF). The double $E_8$ encoding enables DTRU to achieve enhanced error correction with compact bandwidth. The design prioritizes simplicity to facilitate deployment on low-power devices, achieved by eschewing additional coefficient compression techniques and redundant invertibility checks during key generation, while enabling circuit/code reuse. Security robustness is guaranteed through parameter selections that offer adequate security redundancy, mitigating potential cyclotomic ring risks via LPPNF, and precluding sparse noise distributions in the recommended parameter sets.
Complementing our theoretical advances, we present comprehensive implementations of all the parameter sets with dedicated support for C, AVX2, and ARM platforms, leveraging architecture-specific optimizations. For example, compared to NTRU-HRSS and Kyber at the same security levels, our KEM is 49%-52% more compact and 3.84–15.69$\times$ faster than NTRU-HRSS in the round-trip time of ephemeral key exchange, and is 7%-27% more compact and 1.05–1.32$\times$ faster than Kyber.
CUTS: Chained Uniform-sum Tree Signatures
Stateful hash-based signatures fail badly when a one-time key signs twice,
as happens when the signer's state is lost or rolled back. We study what a
second signature reveals in a broad class of hash-based schemes whose key is
a tree of hash chains. In this class, a message selects a set of tree nodes
that covers every leaf exactly once, together with a position on the chain
of each selected node, and the signature reveals the chain values at those
positions. For the whole class, we prove that the values derivable from
several signatures are exactly the union of those derivable from each
signature alone, and we bound forgery after $b$ signatures in the classical
random-oracle model by a combinatorial coverage exponent $\lambda_b$, also
when the signer grinds a counter. We then present CUTS
(Chained Uniform-sum Tree Signatures), a member of the class built on one
binary tree, in which both the selected nodes and their chain positions
depend on the message, with the positions summing to a fixed value $S$.
Signature length and verification cost are fixed by the parameters and do
not depend on the tree height. For CUTS, we compute the two-use coverage
exactly as one coefficient of a polynomial and derive deterministic lower
bounds on $\lambda_2$; one parameter set with 1 424-byte signatures has
$\lambda_2\ge128.6$. A counter variant, CUTS+C, trades a short counter and
extra signing work for a proven grinding gain of $g$ bits in the coverage
term.
Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold Rate
We study the local leakage resilience of Shamir secret sharing, where an adversary leaks a bounded number of bits from every share. For $n$ parties and reconstruction threshold $k$ over a prime field $\mathbb{F}_p$ with $p>n$, we prove the following.
(1) There is an absolute constant $c_{\mathrm{bh}}<1/2$ such that, for $k\ge c_{\mathrm{bh}}n$, Shamir sharing is resilient to arbitrary one-bit leakage from every share. The best previous threshold was $0.668n$.
(2) For every fixed $0<\delta<1/2$ and $k\ge(1/2+\delta)n$, Shamir sharing is resilient to $\left\lfloor\frac{\delta}{24}\log_2 n\right\rfloor$ bits of arbitrary local leakage per share. By a recent attack, this number of bits is optimal up to a constant factor depending on $\delta$.
(3) For every fixed threshold rate $c>0$ and $k\ge cn$, Shamir sharing is resilient to quadratic-residue leakage and to almost all local leakage functions of up to $\eta_c\log_2 p$ bits, for a constant $\eta_c>0$.
All three results follow from one analytic framework, which we develop for generalized Reed--Solomon codes: local leakage from a uniform codeword is statistically close to the same leakage from independent uniform field elements. The framework expresses the leakage distance as the norm of a function on the leakage outputs. The Efron--Stein decomposition splits this function into orthogonal components indexed by supports of dual codewords. Two tools bound the components: list recovery of the dual code, which is ordinary list decoding for one-bit leakage, and a generalized von Neumann inequality for MDS systems of linear forms that retains linearly many Gowers norms. The first tool gives the result above half, the second gives the constant-rate result, and applying both to different ranges of supports in the same decomposition gives the result below half.
ANSA-IBS: Identity-Based Signatures from Annular NTRU Trapdoors and Bimodal Fiat-Shamir with Aborts
We give a lattice identity-based signature scheme from annular NTRU trapdoors and Fiat--Shamir with aborts (FSwA). Countered hashing maps each identity to its first invertible DLP/NTRU syndrome $a$. Extraction returns a short witness to $s_0+s_1h=a\bmod q$, and signing normalizes this relation to a fixed-target two-response equation with public commitment recovery. Gärtner's iterative rejection method fits naturally into this signing layer: processing the challenge monomials separately reduces the Gaussian mask width and expected signing attempts, yielding shorter signatures. We report three parameter sets whose signing layer is calibrated against NIST security categories 2, 3, and 5, with fixed signature sizes of $8486$, $11309$, and $12727$ bytes, respectively.
Genericity in multivariate cryptography
The results in this paper establish the genericity of some
properties of the ideals and varieties generated by UOV public keys, in
particular the equidimensionality of the UOV varieties and the radicality
of public key ideals. These genericity results justify the various regularity
assumptions that are made on polynomial systems of equations arising
in the cryptanalysis of UOV and its variants. We also provide examples
in the recent literature showing how genericity questions arise in crypt-
analysis and why genericity should be taken into consideration when de-
signing cryptographic schemes. Lastly, we perform a retrospective study
of various cryptographic schemes through the viewangle of genericity.
We identify several cases in which non-genericity led to the cryptanaly-
sis of the scheme, but also provide a counter-example of a scheme whose
non-genericity does not seem easy to exploit.
Cross-Signature Signing-Key Recovery and Domain-Separation Repair for SDitH v2
SDitH is a code-based signature scheme built from the regular syndrome decoding (RSD) problem. Each v2 signature masks the long-term witness with pseudorandom leaf-seed shares. In each repetition, cancelling the shares reconstructed by the verifier leaves the witness XORed with the hidden seed's PRG output. The VOLEitH PRG runs AES or Rijndael in counter mode from zero, so every signature and leaf uses the same input. One encryption therefore tests a candidate seed against every exposed value. RSD elementary-vector constraints discard false candidates before the seed commitment confirms a match. A matching hidden seed reveals the long-term witness and yields a signing key.
With $q=2^{12}$ chosen-message signatures, the attack costs 11.23-11.67 bits less than AES-128/192/256 exhaustive key search across all six parameter sets. Both use the same Boolean-circuit model, and the attack cost extends through fresh forgery. Reduced-keyspace executions against the official C implementation recover witnesses of 616, 876, and 1,144 bits and produce accepted fresh signatures for every parameter set. Using the signature salt as the IV leaves one signature's repetitions under one input and retains 1.95-3.29 bits of separation. Combining salt, BAVC leaf index, and block position assigns a separate counter range to each PRG call without changing signature size or the number of block-cipher calls.
Signing-Key Recovery from Unsalted Root Expansion and Salt-Binding Repair for MQOM v2
We give the first passive signing-key recovery attack on MQOM v2 in the classical EUF-CMA setting by exploiting the generation of the correlated GGM trees used in each signature. MQOM v2 expands a fresh $\lambda$-bit signature master seed, denoted $\mathsf{mseed}$ in the specification, with a PRG call whose salt input is always zero. A repeated $\mathsf{mseed}$ therefore produces the same GGM root seeds $\mathsf{rseed}[e]$, even when the signatures have different salts. For each execution, the BLC opening contains a sibling path whose top seed is either $\mathsf{rseed}[e]$ or its XOR with the first $\lambda$ bits of the secret MQ solution. When two signatures repeat $\mathsf{mseed}$ and the most significant bits of their hidden-leaf indexes differ, XORing the two top seeds cancels $\mathsf{rseed}[e]$ and reveals this secret prefix. The attacker can then recover a GGM root seed, reconstruct the corresponding tree and the secret MQ solution, and sign a fresh message.
The value $\mathsf{mseed}$ is hidden, but the BLC openings provide enough information to detect its repetition. Storing the top sibling-path seeds from the first two executions together with their XOR finds every collision that can reveal the secret prefix. At the Category-I limit of $2^{64}$ signing queries, the attack succeeds with probability about $0.39$. The same zero-salt derivation also allows computations to be reused across public keys, parameter variants, and v2 releases, which yields the cross-key, exhaustive search, and precomputation extensions studied after the single-key attack. Executable tests against the official implementation recover signing keys and verify fresh-message forgeries. MQOM v3.0 binds root-seed derivation to the signature salt and execution index, removing the relation used by these attacks.
Modulus Operandi: Round-Optimal Modulus Conversion for MPC and Threshold FHE
In secure multiparty computation (MPC), modulus conversion turns a sharing of a value $x$ modulo $q$ into a sharing of the same value modulo $t$, without leaking anything about $x$. One important application of modulus conversion is in threshold decryption for lattice-based cryptosystems, where a sharing modulo the ciphertext modulus has to be moved to the plaintext modulus before it can be opened. The most efficient protocols so far (Damgård et al., Asiacrypt 2026) are in the preprocessing model, assume $x$ is bounded away from $q$ by a constant factor and take two rounds for a prime target modulus, three rounds for arbitrary moduli, and one round when all moduli are 2-powers. We improve upon this by constructing three new modulus conversion protocols in the preprocessing model:
- Our first conversion protocol takes a single round for arbitrary moduli, consisting of just one opening.
- Our second conversion protocol is a variant of the first protocol, where in the preprocessing most of the secure multiplications are replaced by private inputs, which are checked in a batch using fully linear interactive oracle proofs (FLIOPs). This makes the preprocessing cheaper (amortized over a batch of conversions) when the number $N$ of parties is small. This comes at the cost of making the bound on $x$ a factor $N$ stronger.
- Our third conversion protocol avoids the bound on $x$ altogether but takes two rounds.
All our protocols are stated in the arithmetic black box (ABB) model, so they can run on top of a wide variety of MPC protocols, inheriting their corruption threshold and security model.
To allow the third conversion protocol to run in two rounds, we construct the first one-round comparison protocol in the ABB model for comparing a bitwise shared $n$-bit value against a public threshold with polynomial-size preprocessing. Concretely, the preprocessing size is $\mathcal O(n^2)$ in general, and $\mathcal O(n^2 / \log n)$ in our case where the secret value is fixed in preprocessing.
We also construct constant-round ABB protocols without preprocessing for computing symmetric functions and comparisons of values shared bitwise modulo powers of arbitrary primes (e.g., $2^k$), at communication quasi-linear in the number of input bits. Previously, this required either a sufficiently large prime or polynomially larger communication.
Finally, we give an impossibility result for non-interactive modulus conversion, demonstrating that a single round is optimal: unless $t$ divides $q$, every non-interactive conversion for inputs $x < q/\beta$ is incorrect with probability at least $\approx 1/(4\beta)$.
Breaking First-Order Masked Kyber with Belief Propagation Alone
We recover the long-term key of a first-order masked Kyber768 implementation on an ARM Cortex-M4 from about 2200 decapsulation power traces, using only authentic ciphertexts that pass ciphertext-validity checks. The secret is freshly shared before every decapsulation, and the attack combines weak second-order leakage from both shares. Under the evaluated leakage model, even exact Hamming weights of both shares provide about 97% less mutual information about a decryption-noise coefficient than the exact Hamming weight of the unmasked coefficient.
A profiled neural network estimates Hamming-weight distributions for the two arithmetic shares of each noisy message coefficient. We combine these distributions into likelihoods on the decryption noise, which is a known affine function of the secret and the public-key error. A belief-propagation (BP) solver accumulates these likelihoods across traces, preserving their non-Gaussian shapes while approximating the aggregate interference from other key coordinates by a Gaussian. An Onsager correction from approximate message passing corrects for feedback between each factor and the current beliefs. The solver recovers all 1536 secret and error coefficients without lattice reduction.
At the evaluated trace budgets, least squares performs no better than the all-zero estimate, and a greedy inequality solver fails even with exact Hamming weights. The evaluated primal-lattice cascade does not reduce the trace requirement: below BP's recovery threshold, its output remains too diffuse to enable practical lattice recovery. At 2000 traces, BP-derived hints lower the estimated BKZ block size from 624 to 505, leaving the lattice attack impractical.
A Note on Splittings and Endomorphisms
Finding a nontrivial endomorphism of a given supersingular elliptic curve is a hardness assumption of isogeny-based cryptography. We prove the reduction from it to the problem of finding a splitting of a given principally polarized abelian surface. By using this new reduction, we also prove the heuristic equivalence of the splitting problem with a degree restriction and the endomorphism ring problem in dimension two.
Static Group Signature with Post-Compromise Accountability
Uncategorized
Uncategorized
Signatures with Post-Compromise Accountability (SPCA), introduced by Dayanikli et al. at SCN'26, are signature schemes that enable signatures generated before the compromise of a signing key to be distinguished from those produced after the compromise. In this paper, we extend this notion to static group signatures and introduce Group Signatures with Post-Compromise Accountability (GSPCA).
GSPCA preserves the anonymity and traceability guarantees of group signatures while enabling pre-compromise signatures to be revalidated after key compromise. The coexistence of opening and revalidation algorithms gives rise to a new consistency requirement, which we formalize as opening--revalidation consistency. We present a generic construction of GSPCA from public key encryption schemes, signature schemes, and simulation-sound non-interactive zero-knowledge proof systems. A central technical difficulty is that the encryption randomness in our construction is derived from a randomized signature component and may therefore have high min-entropy without being uniformly distributed. To address this issue, we introduce adaptive hedged security against adaptive chosen-ciphertext attacks (AH-CCA), which extends indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) to adaptively chosen high-min-entropy message--randomness distributions, and show how to realize the required randomness-recovering encryption in the random oracle model. We also give a generic signature-based mechanism that provides the required min-entropy and key-binding properties. Finally, we show that ordinary IND-CCA2 security alone is insufficient as a general assumption for our construction by exhibiting an IND-CCA2 secure encryption scheme for which the resulting GSPCA scheme fails to satisfy anonymity.