Papers updated in last 183 days (Page 16 of 2708 results)

Last updated:  2026-09-05
Key-Space Complexity of Information-Theoretic Target-Distribution Semantic Security
Pengcheng Su, Haibo Cheng, and Ping Wang
We study the uniform key-space complexity of information-theoretic target-distribution semantic security (TDSS) for symmetric encryption. Given a message distribution \(P\), we ask for the minimum size of a uniform key space such that observing the ciphertext improves the optimal prediction probability of any Boolean predicate of the message by at most \(\varepsilon\). Our main construction is a sample-based encryption scheme with \(\kappa\) keys: for a secret key $k\in[\kappa]$, the message is placed in the $k$-th position, and each of the remaining $\kappa-1$ positions is filled with an independent sample from a dummy distribution $P_{D}$. When \(P_D=P\), the posterior distribution of the message conditional on the ciphertext is exactly the empirical distribution of \(\kappa\) independent samples from \(P\). This gives a universal semantic-security bound of \(1/(2\sqrt \kappa)\), so \(\kappa=O(\varepsilon^{-2})\) keys suffice for every message distribution, independently of the message-space size. We prove a complementary lower bound in terms of \(\|P\|_2\), matching this rate up to constants for sufficiently flat distributions. In particular, for the uniform distribution on \(|\mathcal{M}|\) messages, the optimal key-space size is $\Theta\!\left(\min\{|\mathcal{M}|,\varepsilon^{-2}\}\right).$ The same framework recovers and generalizes the classical key-length scaling of entropic security: taking \(P_D\) uniform on \(\{0,1\}^n\), a mixture-and-cloning argument protects every source of min-entropy at least \(h\) using $n-h+2\log(1/\varepsilon)+O(1)$ secret-key bits. It also yields a broader source-family view of information-theoretic semantic security, showing that short-key TDSS is possible for any family of sources with bounded second-order R\'enyi divergence from a common reference distribution. We further study zero-advantage TDSS (i.e., $\varepsilon=0$) for restricted predicate classes \(\mathcal F\). We show that a perfectly correct cipher achieving zero-advantage TDSS for $\mathcal F$ with a uniform $\kappa$-element key space exists if and only if $P$ admits a decomposition into $\kappa$-sparse posteriors that preserve the prior Bayes-optimal prediction for every $f\in\mathcal F$. This sparse-convex characterization implies that \(|\mathcal F|+1\) keys always suffice. Surprisingly, point, threshold, and interval predicates can all be protected exactly with only two keys for every message distribution. Our results connect information-theoretic encryption with sparse convex decompositions and the shuffle model, and provide a systematic view of zero-advantage and approximate TDSS with short secret keys.
Last updated:  2026-09-05
TreeCast: Multi-Party Key Establishment Protocol for IoT Devices
Supriyo Banerjee and Sayon Duttagupta
Secure communication in the Internet of Things (IoT) requires lightweight protocols that scale across unicast, multicast, and broadcast settings. Existing solutions typically depend on centralized gateways, which introduce single points of failure and scalability limitations. We propose TreeCast, a distributed group key establishment protocol that organizes devices into a binary tree of hashed Diffie–Hellman secrets, which naturally unifies unicast, multicast, and broadcast in a single scalable hierarchical structure. This design yields logarithmic rekey costs, efficient subtree derivation with efficient device addition and revocation in large and dynamic IoT environments and strong security properties including authentication, partial forward secrecy, and post-compromise recovery. We present a detailed security analysis and to demonstrate practical viability, implement TreeCast on an Arm Cortex-M33 using only software cryptography, without any hardware accelerators. Our measurements show that TreeCast performs key establishment and rekeying within realistic IoT timing and energy budgets, achieving sub-millisecond tree updates and low memory footprint. These results establish TreeCast as a lightweight, scalable, and deployable solution for secure communication in next-generation IoT networks.
Last updated:  2026-09-05
Vega: Low-Latency Zero-Knowledge Proofs over Existing Credentials
Darya Kaviani and Srinath Setty
As digital identity verification becomes increasingly pervasive, existing privacy-preserving approaches are still limited by complex circuit designs, large proof sizes, trusted setups, or high latency. We present Vega, a practical zero-knowledge proof system that proves statements about existing credentials without revealing anything else. Vega is simple, does not require a trusted setup, and is more efficient than the prior state-of-the-art: for a 1920-byte credential, Vega achieves 92 ms proving time, 23 ms verification time, 108 kB proofs, and a 464 kB proving key. For smaller credentials (896 bytes), these drop to 62 ms proving, 17 ms verification, and 83 kB proofs. At the heart of Vega are two principles that together enable a lightweight proof system that pays only for what it needs. First, fold-and-reuse proving exploits repetition and folding opportunities (i) across presentations, by pushing repeated work to a rerandomizable precomputation; (ii) across uniform hashing steps, by folding many steps into a single step; and (iii) for zero-knowledge, by folding the public-coin transcript with a random one. Second, lookup-centric arithmetization extracts relevant values from credential bytes, both for extracting relevant fields without full in-circuit parsing, and to enable length-hiding hashing.
Last updated:  2026-09-05
Cryptanalysis of a knot-based key exchange
Simon-Philipp Merz
We present an efficient attack on a knot-based Diffie--Hellman key exchange proposed by Sconza and Wildi. In the proposal, the two parties exchange oriented knots, combine them under connected sum to obtain a common knot, and derive the shared secret by evaluating a finite type invariant of degree $m$ on it. We show the scheme is insecure for every choice of finite type invariant. The shared secret can be computed from the public transcript at roughly three times the cost of running the scheme honestly. The attack maps knots into a truncated Polyak space $\mathcal{P}_m$, in which connected sum becomes multiplication and every element of the image is invertible, so the public knot can simply be divided out. This bypasses all countermeasures put in place by the proposed protocol. Independently of the attack, we show that the key space is too small for the parameters proposed. A degree-$m$ invariant takes $O(c^{m})$ values on knots represented with diagrams consisting of $c$ crossings. For the suggested crossing number, reaching the $128$ bits claimed would require $m\ge 10$, at which point a single evaluation of the invariant costs in the order of $2^{50}$ operations.
Last updated:  2026-09-05
WaterSQI and PRISMO: Quaternion Signatures for Supersingular Isogeny Group Actions
Tako Boris Fouotsa
Isogeny group action based signatures are obtained from a sigma protocol with high soundness error, say $\frac{1}{2}$ for its most basic variant. One needs to independently repeat the sigma protocol $O(\lambda)$ times to reduce the soundness error to negligible (with $\lambda$ being the security parameter). These repetitions come with a considerable efficiency and size overhead. On the other hand, quaternion isogeny-based signatures such as SQIsign and PRISM are directly obtained from a sigma protocol with a negligible soundness error. The secret key in SQIsign and PRISM is a random supersingular isogeny, and both schemes are insecure when the secret isogeny arises from the supersingular isogeny group action setting. In this paper, we propose WaterSQI and PRISMO, variants of SQIsign and PRISM respectively, suited for secret isogenies that arise from the supersingular isogeny group action setting. They use a sigma protocol whose soundness error is negligible without requiring parallel repetitions. They are hence more compact and $O(\lambda)$ times more efficient compared to Generalised CSI-FiSh (the generalisation of CSI-FiSh to large parameters using generic isogeny group action evaluation algorithms such as Clapotis/KLaPoTi/PEGASIS). For example, for our proof of concept implementation with a 2000 bits prime in Sagemath, PRISMO, when compared to Generalised CSI-FiSh with the same public key size, is about 80x faster for signing and 1457x faster for verification, while also being 29x more compact (signature size). Moreover, we prove that WaterSQI is a quantum proof of knowledge of the full endomorphism ring.
Last updated:  2026-09-05
Determining those Boolean functions whose restrictions to affine spaces are plateaued
Claude Carlet and Darrion Thornburgh
Quadratic Boolean functions (that is, Boolean functions of algebraic degree at most 2), bent Boolean functions (i.e. maximally nonlinear Boolean functions in even numbers of variables) and, as we observe in this paper, partially-bent Boolean functions (i.e. affine extensions of bent functions to linear super-spaces), share a strong property: all their restrictions to affine hyperplanes are plateaued (i.e. have a Walsh transform valued in a set of the form $\{0,\pm \lambda\}$, where $\lambda$ is a positive integer called the amplitude). In this paper we determine for any $n$ and $k<n$ the class $C^n_k$ of those $n$-variable Boolean functions whose restrictions to all $k$-dimensional affine subspaces of $\F_2^n$ are plateaued (of any amplitude). We show that, for any $n\geq 4$, $C^n_{n-1}$ equals the class of partially-bent functions, and for $3 \leq k \leq n-2$, $C^n_k$ equals the class of quadratic functions (while for $0\leq k\leq 2$, it equals of course the class of all Boolean functions). This provides a new characterization (after almost 20 years) of partially-bent functions and a hierarchy among $n$-variable Boolean functions by six nested classes, each of which happens to be, for any $n\geq 5$, strictly included in the next one: quadratic functions, partially-bent functions, the restrictions of $(n+1)$-variable partially-bent functions to $\F_2^n$, plateaued functions, the restrictions of $(n+1)$-variable plateaued functions to $\F_2^n$, and all Boolean functions. We leave open the two problems of determining exactly what are the third and fifth of these classes, but we begin the study of the first of these two classes by characterizing the situation where a plateaued function $g$ has a restriction $f$ to an affine hyperplane $H$ that is plateaued. We also characterize when $g$ is partially-bent. Our characterization of partially-bent (resp., quadratic) functions extends to strongly plateaued vectorial functions. We state an open question on vectorial functions that happens to be related to an important one on crooked functions.
Last updated:  2026-09-05
A size/fan-in trade-off for circuits
Pierre Meyer
We consider (boolean or arithmetic) circuits in which every gate may compute an arbitrary function of its input gates. We show a novel tradeoff between a circuit's size and its fan-in: \begin{quote} Any function which may be computed using $s$ fan-in $2$ gates can alternatively be computed using $s/3\ (1+O(1/\sqrt{k}))$ fan-in $k$ gates. \end{quote} This asymptotically improves the previous bound of $2s/5\ (1+O(1/k))$ by Charbit, Couteau, Meyer, and Naserasr [TCC'24]. Among other applications, this improves the communication complexity of secure multiparty computation in the correlated randomness model. \emph{Any} $n$-input $m$-output circuit with $s$ internal gates (over arbitrary binary gates) can be securely computed in the correlated randomness model with per party communication $s/3 + n + m$ and computation $\widetilde{O}(s)$. Our paper stands at the intersection of cryptography, complexity theory, and graph theory, but our main technical contribution is one to extremal combinatorics: we establish that every order-$n$ $2$-degenerate graph admits a planarising set of size at most $\lfloor n/3 \rfloor$. Our main conceptual contribution is to relate the existence of sublinear-size (directed) $k$-path transversals to well-studied graph parameters. Along the way, we uncover a recurringly overstated lemma throughout the literature on sublinear-size vertex-separators and hyperfinite graphs. According to this lemma, any monotone graph class admitting sublinear-size balanced vertex separators should be weakly hyperfinite. However, this is contradicted by a graph class put forward by [Moshkovitz and Shapira, Random Structures \& Algorithms'15]. Unfortunately, the lemma appears in highly influencial works such as [Henzinger, Klein, Rao, and Subramanian, STOC'94 \& JCSS'97], or the textbook of Nešetřil and Ossona de Mendez [\emph{Sparsity}, Springer'12], and in turn it is used in a significant number of papers. Thankfully a slightly weaker version of this lemma is true, with a caveat on how sublinear the vertex separators needs to be, and we provide the correction as a service to the community.
Last updated:  2026-09-04
The One-and-a-Half Johnson Bound Is Tight for Proximity Gaps of General Linear Codes
Scott Duke Kominers, Justin Thaler, and Kai Zhe Zheng
For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the proximity-gaps property up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction—typically at most $\operatorname{poly}(n)/q$—of exceptional coefficients $z\in\mathbb{F}_q$ for which $f+zg$ is $\delta_1$-close to $C$. The work [BGKS20] shows that every linear code of relative distance $\delta$ satisfies proximity gaps up to the one-and-a-half Johnson radius \[ J_{3/2}(\delta)=1-(1-\delta)^{1/3}. \]We prove that this threshold is tight for general linear codes at every distance $0<\delta<1$. Specifically, for every $0<\delta<1$, we construct a linear code of relative distance arbitrarily close to $\delta$ and words $f,g\in\mathbb{F}_q^n$ that are both \[ 1-(1-\delta)^{4/9} \]far from the code, but for which a constant fraction of coefficients $z\in\mathbb{F}_q$ make $f+zg$ nearly $J_{3/2}(\delta)$-close to the code. Our counterexamples continue to hold even when a fixed amount of distance-dependent slack is allowed.
Last updated:  2026-09-04
Bounded Gaps Between Primes: An Upper Bound of 236
Zhao Song and Song Yue
Let $H_1:=\liminf_{n\to\infty}(p_{n+1}-p_n)$, where $p_n$ is the $n$-th prime. The twin-prime conjecture asserts that $H_1=2$. Zhang [Zha14] proved the first finite bound, $H_1<7\times10^7$. Maynard [May15] improved this bound to $H_1\le600$. Polymath [D. 14b] subsequently established $H_1\le246$. Stadlmann [Sta26] further improved the bound to $H_1\le240$. In this paper, we prove $H_1\leq236$.
Last updated:  2026-09-04
Dynasaurs: Efficient Universal Dynamic zkSNARKs from Sparse Linear Arguments
Martí Batista, Álvaro Montes, Nikitas Paslis, and Carla Ràfols
Dynamic zkSNARKs were recently introduced by Wang et al. [Eurocrypt, 2026]. This primitive extends standard zkSNARKs with an update algorithm that adapts a proof to a new statement in time sublinear in the circuit size, provided the witness changes in few positions. However, existing constructions either need a circuit-specific setup or, in the universal case, send over $130$ group elements and require over $180$ pairings. As is the case for universal zkSNARKs, dynamic ones can be built from dynamic arguments for Hadamard products and linear relations. Wang et al. handle the latter in the particular case of a permutation matrix, via a sparse argument---a protocol whose prover runs in time proportional to the Hamming weight of the witness. Nevertheless, their techniques do not directly extend to the arbitrary matrices arising in constraint systems such as R1CS or CCS. Furthermore, the standard approach for proving general linear relations is unsuitable for the sparse setting because of a witness-independent step: the prover commits to an auxiliary polynomial determined by the matrices alone, and is hence dense regardless of how sparse the witness might be. Our first contribution is a sparse zkSNARK for linear relations, which we build from a fully witness-dependent argument together with what we call a rational encoding of the matrices. As our second contribution, we develop a compiler that turns any sparse argument for a linear relation into a dynamic one, while preserving the zero-knowledge property of the underlying scheme. Instantiated for Plonk and R1CS-lite, our techniques yield universal dynamic zkSNARKs with at most $20$ group elements per proof and $23$ verifier pairings---over $6.5\times$ and $7.8\times$ fewer than the state of the art---as well as asymptotically faster updates. We also show how both of our constructions can be de-amortized.
Last updated:  2026-09-04
LWE is as Hard as Continuous LWE \& a Search-to-Decision Reduction
Prince Kirpa
In 2021, Bruna, Regev, Song and Tang introduced the continuous analogue of LWE, CLWE. Shortly after, Gupte, Vafa, and Vaikuntanathan showed a classical reduction from LWE to CLWE and from discrete-CLWE (secret from a discrete set) to LWE. In this paper, we show two results. The first result is a search-to-decision reduction for CLWE. The search-to-decision reduction works similarly to the standard reduction for LWE. The main difference between the reductions is the continuous nature of the CLWE secret. As a consequence, our reduction can find the secret up to a polynomial error $n^{-k}$ for some constant $k$. The second and our main result is the reduction from CLWE to discrete-CLWE. The reduction is an identity reduction, i.e. samples are passed as-is to the distinguisher. To prove the distinguisher can accept the samples we employ tools from analytic number theory. These tools allow us to show that the set $\frac{1}{r} \cdot \mathbb{Z}^n$ with fixed $\ell_2$ norm $r$, i.e. integer vectors projected onto the unit sphere, can mimic the unit sphere $S^{n-1}$ for some $r > r'$. By completing this missing link, we can show that LWE is equivalent to CLWE i.e. $\text{LWE} \equiv \text{CLWE}$ and existing or new results on each problem apply to the other.
Last updated:  2026-09-04
Improved Related-Key Boomerang Distinguisher for Full-Round FUTURE
Guoqiang Liu, Suping Liu, and Wuyou Zhang
FUTURE is a lightweight block cipher with a 64-bit block, a 128-bit key and $10$ rounds, proposed at AFRICACRYPT 2022 for low-latency hardware. This study analyzes FUTURE in the related-key setting with a bit-level constraint model that carries the exact weights of the differential distribution table and the exact entries of the boomerang connectivity table, and whose objective function $2w_0 + 2w_1 + w_{\mathrm{bct}} = -\log_2(p^2q^2r)$ optimizes both sub-ciphers and the middle layer of the sandwich framework together. The model returns a full-round distinguisher whose objective function value $36$ is optimal over all switching rounds and whose probability is $P = \hat{p}^2\,\bar{r}\,\hat{q}^2 = 11\cdot 2^{-39} \approx 2^{-35.54}$, at a cost of $2^{37.54}$ queries under four related keys and $2^{37.54}$ XOR operations. Running it on the full cipher over $2^{44.34}$ quartets returns $341$ right quartets and an experimental probability of $2^{-35.92}$, in $63.9$ hours on an ordinary personal computer; at the previous full-round probability $2^{-45.8}$ the same computer would take about $6.8$ years. The distinguisher is therefore a practical one, and improves the best previously known full-round related-key boomerang distinguisher of FUTURE by a factor of $2^{10.26}$ in probability, in data and in time. An $8$-round distinguisher placed into the unified key recovery framework further gives a full-round attack with $2^{51.05}$ data, $2^{64}$ time and $2^{64}$ memory, whose time complexity attains the optimum of the framework at any memory within the codebook and improves the best previously known attack by a factor of $2^{6}$.
Last updated:  2026-09-04
Rogue: Updatable Matrix Lookup Arguments and Applications to Verifiable Databases
Christodoulos Pappas, Zhuo Cai, and Dimitrios Papadopoulos
Proving the correctness of computations over a large dataset via succinct non-interactive arguments of knowledge (SNARKs) entails the large overhead of ``loading'' the dataset in the SNARK. However, certain computations may only need to access a small fraction of the dataset (e.g., a database query that only accesses a subset of table rows and then computes an aggregation function). The standard way of \emph{efficiently} proving such computations is to use \emph{lookup arguments with sublinear prover complexity} to load only necessary data to the SNARK. Unfortunately, all prior schemes are \emph{static}: even a single change to the dataset forces the prover to re-run an expensive pre-processing step, linear to the dataset size. The only exemption is the recent work of Dutta et al., (CCS'24) that proposed a lookup argument with \emph{amortized} sublinear updates---based on re-running the pre-processing phase periodically, when too many changes have been accumulated. In this work, we present Rogue, the first lookup argument with sublinear prover time and updates that \emph{always} take time proportional only to the number of incurred changes. Indeed, Rogue is actually a \emph{matrix lookup argument}, supporting entire row lookups in time proportional to the number of rows (and independent of their size)! It has very good practical performance, e.g., for a $2^{20}\times 2^7$ matrix and $2^{10}$ row accesses, Rogue achieves $\times 21$-$942$ and $\times 76$-$30000$ faster lookups and updates, respectively, compared to prior works. We then use Rogue to build RogueDB, the first verifiable database system for arbitrary SQL queries that supports authenticated indexes, hence achieves prover time sublinear to the database. Compared with prior schemes with succinct proofs, vSQL (Zhang et al., IEEE S\&P'17) and PoneglyphDB (Gu et al., SIGMOD'25), we get $\times 42.8$-$\times 8624.1$ and $\times 149.6$-$\times 11362.4$ faster prover times, for various SQL queries from the TPC-H benchmark.
Last updated:  2026-09-04
A General Approach to Adaptor Signatures
Nico Döttling, Sri AravindaKrishnan Thyagarajan, Pratik Soni, Jay Taylor, Hendrik Waldner, and Riccardo Zanotto
Adaptor signatures have emerged as a powerful contract-minimal mechanism for fair exchange on blockchains, enabling efficient and privacy-preserving atomic swaps and conditional payments. However, existing adaptor schemes are limited to narrow classes of NP relations (e.g., discrete logarithm secrets) and specific signature schemes, limiting their scope both in terms of constructions and applications. This work addresses this gap by presenting a new framework that supports arbitrary NP relations and a broad range of signature schemes, significantly extending the reach of adaptor signatures beyond prior works and broadening the design space for adaptor signature constructions. Our framework also yields adaptor signatures that are compatible with today's blockchain systems. More specifically, we devise two general compilers for adaptor signatures. First, we show how to efficiently lift adaptor signatures from structured languages (such as discrete log relations) to general NP languages with the help of degree-$2$ homomorphic encryption, resulting in adaptors for standard signature schemes and general NP languages. Secondly, we develop a compiler that transforms any signature scheme with a subliminal channel into an adaptor signature scheme for general NP languages using circuit-private fully homomorphic encryption. Signatures with subliminal channels enable the encoding of witnesses in the signing randomness, and include randomness-recoverable schemes like Schnorr, ECDSA, CL, BBS, as well as salted versions of deterministic signatures schemes like BLS and RSA. Both constructions achieve a novel property called statement truth privacy, which guarantees that a buyer learns nothing about the underlying statement, not even its truth, unless the protocol successfully completes.
Last updated:  2026-09-04
Achieving Guaranteed Output Delivery MPC with Constant Rounds and Linear Communication in Minicrypt
Junru Li and Yifan Song
In this work, we study the communication complexity of constant-round MPC with guaranteed output delivery (GOD) in Minicrypt. We construct the first MPC protocol in this setting with linear communication complexity of $O(|C|n\kappa+Dn^3\kappa^3+W_I{\sf poly}(n,\kappa))$ bits under the assumption of a random oracle, where $|C|$ is the circuit size, $D$ is the circuit depth, $W_I$ is the number of input wires, and $\kappa$ is the security parameter. In comparison, the previously best-known construction with linear communication ($O(|C|n)$), presented by Goyal et al. (CRYPTO 2020), requires $O(D+n^2)$ round complexity. When targeting $O(D)$ round complexity, the best-known result by Agarwal et al. (ASIACRYPT 2024) still requires $O(|C|n^3)$ communication complexity. More communication is needed to achieve constant round complexity, even with non-black-box use of the underlying cryptographic primitives.
Last updated:  2026-09-04
BMuSig2: Schnorr-Compatible Blind Multi-Signatures
Kanchan Bisht, Keerthi Aiswarya Varshini, Shivam Sethi, Maria Francis, and R. Kabaleeshwaran
Blind signatures and multi‑signatures are well‑known primitives, but blind multi‑signatures (BMS), which combine both these primitives, were only recently formalized by Karantaidou et al (CCS'24). A BMS scheme allows a user to obtain a compact signature on a common hidden message from a group of signers such that even if the signers collude, they cannot learn the message or link the final signature to any particular interaction. In this paper, we introduce BMuSig2, a 2-round concurrently secure blind multi-signature scheme whose signatures and verification match standard Schnorr signatures. This design enables systems using Schnorr signatures to adopt BMuSig2 as a drop-in replacement, requiring changes only to the issuance phase, while leaving verification unchanged. BMuSig2 builds on MuSig2 multi-signatures (CRYPTO’21) and integrates techniques from a recent blind signature scheme (CRYPTO’24) that leverages non-interactive zero-knowledge (NIZK) arguments and public-key encryption (PKE) to achieve concurrent security. We formally prove the security of BMuSig2 by relying on the unforgeability of MuSig2 and the security of the underlying NIZK and PKE components. We also provide a proof-of-concept implementation to demonstrate its practical efficiency.
Last updated:  2026-09-04
VERA: VERifiable Microarchitectural Monitoring for Adversarially Robust Edge AI
Soumi Chatterjee, Debadrita Talapatra, Nimish Mishra, and Debdeep Mukhopadhyay
As machine learning increasingly moves to edge devices, model owners must trust predictions produced on devices and inputs outside their direct control. This trust is challenged by adversarial inputs, where carefully crafted perturbations can induce incorrect predictions. Existing black-box defenses can detect such inputs using microarchitectural signals, but provide no privacy-preserving mechanism for a remote model owner to verify the detection outcome. In this work, we introduce VERA, a framework for verifiable and privacy-preserving adversarial detection at the edge. VERA combines lightweight Hardware Performance Counter (HPC) monitoring with Zero-Knowledge Range Proofs (ZKRPs). Adversarial perturbations can alter internal activation patterns and consequently the microarchitectural behavior of inference, which can be captured through HPC measurements. Rather than revealing these potentially sensitive measurements, VERA allows an edge device to prove that a committed HPC value lies within a calibrated benign range without disclosing the value itself. This avoids the overhead of general-purpose zk-SNARKs and enables lightweight verification on resource-constrained devices. We formalize VERA as a black-box framework that can combine an HPC-based adversarial detector with an interactive ZKRP, which can also be made non-interactive using the Fiat--Shamir transform. We evaluate VERA against multiple adversarial attacks on MNIST and CIFAR-10. Our results show millisecond-scale verification overhead, with proof-generation costs amortizable across batches of inferences. To the best of our knowledge, VERA is the first framework to provide privacy-preserving cryptographic evidence that an edge inference exhibits microarchitectural behavior within a calibrated benign regime.
Last updated:  2026-09-04
Quadratic-like balanced functions and permutations
Claude Carlet and Irene Villa
We study those $(n,n)$-permutations, and more generally those balanced $(n,m)$-functions, whose component functions all admit a derivative equal to constant function 1 (this property itself implies balancedness). We call these functions quadratic-like permutations (resp. quadratic-like balanced functions) since all quadratic balanced functions have this property. We show that all Feistel permutations, all crooked permutations and (more generally) all balanced strongly plateaued functions have this same property and we observe that the notion is affine invariant. We also study in each of these classes and in the class of quadratic-like APN permutations the "reversed" property that every derivative in a nonzero direction has a component function equal to constant function 1, and we show that this property can be satisfied only if $m\geq n$. We also show that all the quadratic-like power permutations $F(x)=x^d$, $x\in \mathbb F_{2^n}$ must be quadratic, which generalizes a well-known similar result on power crooked functions. We give several constructions of quadratic-like permutations and balanced functions outside the three classes of quadratic balanced functions, permutations affine equivalent to Feistel permutations and crooked permutations. We characterize the property by the Walsh transform.
Last updated:  2026-09-04
Neo: Lattice-based folding scheme for CCS over small fields and pay-per-bit commitments
Wilson Nguyen and Srinath Setty
This paper introduces Neo, a new lattice-based folding scheme for CCS, an NP-complete relation that generalizes R1CS, Plonkish, and AIR. Neo's folding scheme can be viewed as adapting the folding scheme in HyperNova (CRYPTO'24), which assumes elliptic-curve based linearly homomorphic commitments, to the lattice setting. Unlike HyperNova, Neo can use “small” prime fields (e.g., over the Goldilocks prime). Additionally, Neo provides plausible post-quantum security. Prior to Neo, folding schemes in the lattice setting, notably LatticeFold (ePrint 2024/257), worked with constraint systems defined over a cyclotomic polynomial ring. This structure allows packing a fixed batch of constraint systems over a small prime field into a single constraint system over a polynomial ring. However, it introduces significant overheads, both for committing to witnesses (e.g., the commitment scheme cannot take advantage of bit-width of values), and within the folding protocol itself (e.g., the sum-check protocol is run over cyclotomic polynomial rings). Additionally, the required ring structure places restrictions on the choice of primes (e.g., LatticeFold is not compatible with the Goldilocks field). Neo addresses these problems, by drawing inspiration from both HyperNova and LatticeFold. A key contribution is a folding-friendly instantiation of Ajtai's commitments, with "pay-per-bit" commitment costs i.e., the commitment costs scale with the bit-width of the scalars (e.g., committing to a vector of bits is $32\times$ cheaper than committing to a vector of $32$-bit values). This scheme commits to vectors over a small prime field. It does so by transforming the provided vector into a matrix and committing to that matrix. We prove that this commitment scheme provides the desired linear homomorphism for building a folding scheme. Additionally, like HyperNova, Neo runs a single invocation of the sum-check protocol, where in HyperNova it is over the scalar field of an elliptic curve and in Neo it is over an extension of a small prime field.
Last updated:  2026-09-04
Neo and SuperNeo: Post-quantum folding with pay-per-bit costs over small fields
Wilson Nguyen and Srinath Setty
We construct the first folding scheme that simultaneously achieves six desirable properties: plausible post-quantum security, pay-per-bit commitment costs, field-native arithmetic (the sum-check and norm checks run purely over a small field), support for general (non-SIMD) constraint systems, small-field support (e.g., Goldilocks), and low recursion overheads. No existing scheme satisfies all six: group-based schemes (e.g., HyperNova) lack post-quantum security and are tied to large elliptic-curve fields; lattice-based schemes (e.g., LatticeFold) require expensive ring arithmetic, lose pay-per-bit costs, and impose SIMD constraints; and hash-based schemes (e.g., Arc) incur large verifier circuits. We present two lattice-based folding schemes for CCS, an NP-complete relation generalizing R1CS, Plonkish, and AIR, called Neo and SuperNeo. Neo satisfies five of the six properties but requires SIMD constraint systems; SuperNeo removes this restriction and satisfies all six. SuperNeo also natively supports CCS relations over arbitrary extension fields of the field underlying the Ajtai commitment, without relying on an NTT embedding. Both run a single invocation of the sum-check protocol over a small field extension and achieve pay-per-bit costs via new folding-friendly instantiations of Ajtai commitments under the Module-SIS assumption. At the core of our constructions are two new norm-preserving embeddings of field vectors into ring vectors that respect an evaluation homomorphism required for folding. We also introduce interactive reductions, a framework that generalizes reductions of knowledge and enables modular security proofs for composed lattice-based protocols.
Last updated:  2026-09-04
Symplex: Improved Pairing-Based zkSNARK using Partial Fraction Techniques
Charanjit S. Jutla and Arnab Roy
We present Symplex, a pairing-based zkSNARK for R1CS that preserves the syntax of Groth16: a $2G_1{+}1G_2$ proof, and a verifier with three pairings and one public-input multi-scalar multiplication (MSM), while {\it strictly reducing prover cost}. For constraint count $n$, wire count $m$, public-input count $\ell$, and $\kappa=\min\{n,m+1\}$, Symplex's prover uses four FFTs of size $n$ rather than the six of our coset-Lagrange Groth16 comparator, and its larger $G_1$-MSM has width $m+n-\ell+4$ rather than the adaptively based Groth16 width $2\kappa+m+n-\ell+3$. The matched Groth16 prover derives three length-$n$ vectors from the R1CS instance, converts each between coefficient and evaluation form, and commits the quotient with a size-$n$ coset-Lagrange column, resulting in six FFTs in total. Its usual monomial quotient column has one fewer CRS element but requires a final inverse FFT. Symplex instead uses the partial-fraction techniques of Jutla, Nema, Roy (EuroCrypt 2026) allowing the output-wire selector polynomials to be precomputed into the per-wire CRS bundles during setup. So, only the left- and right-wire vectors require FFT-based processing at proving time. The verifier is unchanged (three pairings, one public-input MSM). On a BLS12-381 prototype of Symplex that shares sparse R1CS, FFT, and pairing code with Groth16, a Circom circuit chaining SHA-256 ten times gives a $1.84\times$ prover speedup with online verification at $\approx 2.6\,\mathrm{ms}$ for both schemes. The uniform algebraic extraction argument, perfect completeness, and perfect zero-knowledge are machine-checked in Lean~4. Polymath (Lipmaa, CRYPTO 2024) and PARI (Dellepere, Mishra, and Shirzad, USENIX Security 2026) shrink the proof using a squared R1CS arithmetization. Polymath proves soundness in the AGMOS model, and PARI does not provide zero-knowledge in the stated construction. Symplex keeps Groth16's proof shape and standard R1CS arithmetization, and is proved knowledge-sound in the standard Generic Group Model.
Last updated:  2026-09-03
Compact Lattice-Based NIZK Arguments for Set Membership and Ring Signatures without RO
Nam Tran, Khoa Nguyen, Dongxi Liu, Josef Pieprzyk, and Willy Susilo
Zero-knowledge proofs of set membership underpin privacy-preserving constructions such as ring signatures and anonymous credentials. Existing succinct constructions rely mainly on the Fiat--Shamir transform in the Random Oracle Model (ROM), while standard-model non-interactive proofs from post-quantum assumptions remain either generic and inefficient or asymptotically compact yet concretely impractical. A key obstacle is that existing lattice-based zero-knowledge systems operate over a single ambient modulus, forcing heterogeneous components to be homogenized, inflating parameters and weakening reductions. We introduce the first \emph{compact lattice-based NIZK arguments for set membership in the standard model} with proof size logarithmic in the set cardinality. Our construction matches the logarithmic proof size of accumulator-based ROM constructions while achieving post-quantum security without random oracles. The main technical ingredient is a new trapdoor $\Sigma$-protocol supporting linear relations modulo multiple heterogeneous moduli, allowing such relations to be handled at their native moduli without homogenization. This yields a modular approach to compact proofs compatible with lattice accumulators. As an application, we construct lattice-based ring signatures of size $O(\log R)\cdot \widetilde{O}(\lambda^{2})$ bits, improving the dependence on the security parameter $\lambda$ quadratically over the plain-model construction of Chatterjee et al. (CRYPTO~2021) while retaining optimal logarithmic dependence on the ring size $R$. Our construction is in the CRS model, which partly enables this improvement. The scheme achieves statistical anonymity and unforgeability under standard Module-LWE and Module-SIS assumptions. We also develop two additional tools of independent interest: (i) a generalized Merkle-tree accumulator over module lattices with base-$B$ decomposition, enabling finer efficiency--assumption trade-offs; and (ii) a message-binding technique that removes the need for costly lattice one-time signatures in standard-model ring signatures.
Last updated:  2026-09-03
BinarySpartan: Spartan over binary fields
Srinath Setty
Spartan is a SNARK for R1CS that can be instantiated with any multilinear polynomial commitment scheme. We instantiate Spartan over a binary field, using Ligerito as the commitment scheme along with the ring-switching technique of Diamond and Posen; we refer to the instantiation as BinarySpartan. It is transparent, so it requires no trusted setup, and it provides polylogarithmic-sized proofs. Its security rests on a hash function, so it is plausibly post-quantum secure. We apply well-known optimizations to Spartan and sum-check. We implement and evaluate BinarySpartan end to end. On a MacBook Pro M4 Max (using only its 12 performance cores, and without GPU/Metal acceleration), BinarySpartan proves BLAKE3 at 872,000 hashes/second, SHA-256 at 401,000 hashes/second, and Keccak-f at 287,000 permutations/second, including witness generation. All three clear the 200,000 hashes/second rate proposed as sufficient for a post-quantum Ethereum transition, as well as the roughly 37,000–180,000 hashes/second a possible post-quantum Bitcoin transition would require. At comparable security, BinarySpartan is 16.3–37.8× faster than Plonky3, 6.3–15.7× faster than Binius64, and 4.0× faster than Hashcaster, which only supports Keccak. On all three hash functions, BinarySpartan’s peak throughput matches or exceeds that of Flock, the prior state-of-the-art system. On BLAKE3 and Keccak, BinarySpartan also reaches those rates on far less memory: Flock needs 1.9× and 5.3× more to reach its own best rates. We also evaluate BinarySpartan on the Ethereum Foundation’s client-side proving benchmark, where it proves a single SHA-256 of a 2 KiB message in 6.2 ms, the fastest in the suite and 4.2× faster than Flock.
Last updated:  2026-09-03
Efficient Batch Threshold Encryption Using Partial Fraction Techniques
Dan Boneh, Rohit Nema, Arnab Roy, and Ertem Nusret Tas
Batch encryption enables a holder of the secret key to publish a succinct pre-decryption key for a set of ciphertexts, such that exactly that set can be decrypted while other ciphertexts remain secret. Existing constructions either rely on epochs or, when epochless, suffer from large public parameters (quadratic in the batch size) and are vulnerable to censorship. In this work, we present an epochless, censorship-resistant batch encryption scheme with linear-sized public parameters, constant-sized pre-decryption keys and ciphertexts, and efficient batch decryption. Our construction extends the partial fraction techniques of Jutla, Nema, and Roy's threshold encryption scheme: we exploit partial fraction decomposition such that publishing a single group element as the pre-decryption key lets the decryptor decrypt all ciphertexts in the batch. We prove CCA security of our scheme, and show how to thresholdize it. Our results directly benefit applications such as encrypted mempools for MEV mitigation and time-lock encrypted storage.
Last updated:  2026-09-03
Linear Secret-shared Shuffle with Malicious Security
Samuel Dittmer, Rohit Nema, and Rafail Ostrovsky
Securely shuffling a secret-shared list is a vital sub-protocol in numerous applications, including secure sorting, secure list merging, secure graph processing, oblivious RAM, and anonymous broadcast. We demonstrate how to convert the folklore constant-round protocol for secure shuffling, which employs a delegated Fisher-Yates shuffle using rerandomizable encryption, into a maliciously secure constant-round protocol. This gives the first ever protocol that has linear end-to-end time and communication for a two-party secret-shared shuffle with malicious security. We prove the security of our protocol under the ``linear targeted malleability'' assumption on the homomorphic encryption system, as well as the natural assumptions of efficient ciphertext validity checks and rerandomizability. We also introduce a novel assumption, which we call weak predicability, and show that it is sufficient for security.
Last updated:  2026-09-03
Partial Fraction Techniques for Cryptography
Charanjit S. Jutla, Rohit Nema, and Arnab Roy
Partial fraction decomposition is a fundamental technique in mathematics where products of rational functions can be expressed as sums of fractions. While rational functions have been used in various cryptographic constructions, their rich algebraic structure has not been systematically explored as a direct foundation for building cryptographic primitives. In this work, we describe and exploit two key properties of partial fraction decomposition: (1) the decomposition property itself, which enables efficient set membership testing, and (2) a novel linear independence property arising from the non-singularity of Cauchy matrices, which enables threshold cryptography. We present two main applications. First, we construct a key-value commitment scheme where a dictionary is represented as a linear combination of partial fractions. Our scheme achieves constant-size commitments (a single group element) and proofs, supports homomorphic updates enabling stateless operation, and provides efficient membership and non-membership proofs through simple pairing equations. We also introduce Credential-based Key-Value Commitments, where keys are registered via Boneh-Boyen signatures, enabling applications in permissioned settings. Second, we construct a dynamic threshold encryption scheme leveraging the linear independence of partial fraction products. Our scheme achieves compact ciphertexts, supports public preprocessing of public keys to a succinct encryption key, enables dynamic threshold selection at encryption time, and provides robustness through share verification without random oracles. In particular, we achieve the shortest CPA-secure ciphertext size of 3 group elements, given logarithmic size preprocessed encryption key. We prove security of our constructions in the standard model under new $q$-type assumptions and establish their generic hardness in the generic bilinear group model. Our work demonstrates that working directly with the algebraic structure of rational fractions, rather than converting to polynomial representations, yields elegant and efficient cryptographic constructions with concrete advantages over prior work.
Last updated:  2026-09-03
More Efficient (Hintless) Keyword Private Information Retrieval
Minzhang Li, Feng-Hao Liu, and Guangbei Yi
Keyword private information retrieval (Keyword PIR) enables a client to retrieve the value associated with a keyword from a database while keeping the queried keyword private, thereby generalizing traditional private information retrieval, known as index PIR. The state-of-the-art by Hao et al. (USENIX 2025) has several limitations. First, their generic construction requires three invocations of an underlying index-PIR protocol. Second, to reduce this overhead, they propose a specialized design combining SimplePIR with hash tables. However, this approach inherits SimplePIR's large client-side hint, resulting in substantial per-database storage costs on the client side. Moreover, it allows clients to retrieve information beyond the value associated with the queried keyword. In this work, we present a novel and practical Keyword PIR framework that addresses these limitations. Our construction extends the hintless KsPIR scheme of Luo et al. (CCS 2024) to the keyword setting, ensuring that a semi-honest client retrieves only the value corresponding to the queried keyword. The construction leverages the linear homomorphic technique of Peikert and Pepin (TCC 2025). To accelerate homomorphic evaluation, we design a baby-step giant-step (BSGS) implementation and an offline/online decomposition based on a Galois-theoretic formulation. Experimental results show a mean online speedup of $2.65\times$ over the generic framework when instantiated with the same index-PIR scheme, for databases containing up to $2^{22}$ entries.
Last updated:  2026-09-03
On the hardness of the NTRU problem
Uncategorized
Alice Pellet-Mary and Damien Stehlé
Show abstract
Uncategorized
The 25 year-old NTRU problem is an important computational assumption in public-key cryptography. However, from a reduction perspective, its relative hardness compared to other problems on Euclidean lattices is not well-understood. Its decision version reduces to the search Ring-LWE problem, but this only provides a hardness upper bound. We provide two answers to the long-standing open problem of providing reduction-based evidence of the hardness of the NTRU problem. First, we reduce the worst-case approximate Shortest Vector Problem over ideal lattices to an average-case search variant of the NTRU problem. Second, we reduce another average-case search variant of the NTRU problem to the decision NTRU problem.
Last updated:  2026-09-03
Verifiable SelfMix
Doron Zarchy
Anonymous communication systems aim to hide which user sent which message, but existing designs sit at two extremes: efficient, centralized mixnets that rely on at least one honest mix server, and fully decentralized protocols such as DC-nets and MPC-based shuffles that avoid trusted mixers at the cost of high communication and fragility under disruption. This paper introduces \emph{verifiable self-mix} (VSM), a new anonymity architecture for privately shuffling messages posted on a public bulletin board. In VSM, users \emph{self-mix} their encrypted messages by writing them to secret locations in a public table. A preprocessing protocol, \emph{Unique Number Selection} (UNS), assigns every user a distinct hidden mix location; an anonymization protocol, \emph{Secure Mapping of Private Permutation} (SMPP), ensures that each such location contains exactly that user's ciphertext, without revealing the mapping from users to locations. Because each user learns their own final location, VSM provides \emph{unconditional individual verifiability}: after an optional decryption step, users can check that their message appears at the correct slot without running any cryptographic checks. We formally define VSM and prove anonymity, integrity, and self-verifiability in the malicious model. We then present several concrete instantiations. Our UNS protocols rely on either trusted hardware or multiple servers running plaintext-equivalence tests and require only constant private memory, making them suitable for constrained trusted execution environments. Our SMPP constructions allow trade-offs between trust and bandwidth, achieving $O(n)$ ciphertext uploads per user (or $O(\log n)$ in theory under FHE, at substantial setup cost), while avoiding the pairwise shared-pad state and interactive disruption-resolution typical of classic DC-net designs.
Last updated:  2026-09-03
A Reproducible Security–Performance Benchmark Protocol for Lightweight AEAD on Resource-Constrained IoT Nodes
Atul, Vivek Shukla, Mehul Kumar Das, Varun Shukla, and Divya Mishra
—Internet-of-Things (IoT) nodes must protect sensed data while operating with limited processing capability, memory, and battery capacity. In August 2025, the National Institute of Standards and Technology (NIST) finalized SP 800-232, which standardizes the Ascon family for constrained devices. This paper presents ASCON-Edge, a reproducible protocol for evaluating the security, performance, memory cost, and directly measured energy cost of standardized Ascon-AEAD128 on resource-constrained IoT nodes. The protocol compares Ascon-AEAD128 with AES 128-GCM and ChaCha20-Poly1305 using identical message sizes, associated data, timing boundaries, build conditions, and security tests. It defines a deterministic workload, a nonce uniqueness and replay policy, a hardware-freeze record, raw-data fields, statistical summaries, direct-energy rules, and functional acceptance criteria. It also separates AEAD guarantees from application-layer responsibilities for replay prevention and key handling. A targeted literature synthesis motivates a final-standard, workload-aware comparison protocol. This is a methodology and reproducibility paper: it reports deterministic packet-format overhead, but deliberately does not claim hardware benchmark measurements before a frozen platform and raw data are available.
Last updated:  2026-09-03
UdMAC: Efficiently Updatable Message Authentication Codes
Debrup Chakraborty and Avishek Majumder
Message authentication codes (MAC) are ubiquitous and are considered to be the most important tool employed to ensure authenticity of messages in the symmetric key setting. In this work, we aim to empower MACs with a newly added functionality of updatablility, i.e., the goal is to construct a MAC scheme where the authentication tag for a message can be updated with every update to the message without recomputing the tag for the entire message. Such a functionality can be useful in several scenarios, primarily where the storage of a frequently changing large message is delegated to an un-trusted server. In such a scenario it may be infeasible for an user to download the entire message and recompute the tag for every update. Bellare et al. [CRYPTO'94, STOC'95] introduced a new class of history-free updatable MACs, which can update a message tag without requiring any previous information. However, their update algorithm takes the entire document as an input, which can be impractical in many real-world scenarios. We introduce a new class of MACs called updatable message authentication codes (UdMACs). An UdMAC allows an existing message tag to be updated using only the previous tag, the message update, and a small state, without accessing the previous message. We systematically develop UdMACs, provide syntax for UdMAC, propose formal security notion. We then present two constructions: $\concatu$ and $\xoru$, which support two distinct message updates, namely, concatenation and xor difference. We analyze both the constructions in details and prove security of the construction in the newly proposed security model.
Last updated:  2026-09-03
Private Quantised Neural Network Inference
Hendrik Eerikson, Sven Laur, and Pille Pullonen-Raudvere
Neural networks based machine learning models are used in many classification problems yet privacy issues in model usage are mostly unresolved. When a model owner provides their model to other parties for inference, either the model owner has to share the parameters of the model or the model user must share their query and result with the model owner. Depending on the usage scenario, the user’s query or query result could contain sensitive information that the model provider should not see. And on the other hand, the model parameters themselves could be a valuable business secret or leak private training data. In such cases, neural network inference must be performed in a privacy preserving manner, for example, using secure multi-party computation (MPC). We propose protocols for the private inference of neural networks and evaluate them within the Sharemind MPC secure computation framework. Our protocols are based on the per-tensor quantisation scheme in PyTorch which maps floating point model parameters to 8-bit integer values. Quantisation improves the efficiency of our protocols and our protocols are interoperable with models trained using PyTorch. We extend constant round integer convolution and matrix multiplication protocols for quantised model weights, propose constant round protocols for re-quantising values and analyse the optimal secret share bit width for efficient re-quantisation. The resulting protocols are used to evaluate the VGG16 image classification network with an amortised throughput of 24.3 s per image classification in a LAN setting.
Last updated:  2026-09-03
Peel and Vote: A Paper Ballot Design for Publicly Verifiable Risk-Limiting Audits
Jack Nolan, Yasmine Vazirinejad, Siamak Shahandashti, and Feng Hao
Post-election Risk-Limiting Audits (RLAs) provide statistical guarantees of election outcomes by hand-counting randomly selected paper ballots. However, standard RLAs assume that ballots remain unaltered in storage between election day and the audit, but voters cannot verify this assumption. Prior frameworks, such as VAULT (E-VOTE-ID 2019), attempt to make the audit process verifiable, but they require the public to trust the Election Authority (EA) to honestly sample ballots at random and correctly interpret the voters' choices into cryptographic commitments. Furthermore, they are typically ballot-level, requiring a 1-to-1 mapping between individual paper ballots and digital records. The EA also needs to interactively open commitments during the audit. To address these limitations, we propose the first verifiable batch-level RLA scheme, which shifts the trust anchor from the EA directly to the voter and operates on groups of ballots (batches) to eliminate individual tracking hurdles. Our scheme introduces a peel-and-vote paper ballot design with removable flaps containing pre-printed cryptograms. A voter selects a candidate by removing the corresponding flap, and retains the flap as a receipt, while the same cryptogram printed on the receipt is also published on a bulletin board. In our scheme, a batch contains a group of cryptographically related ballots that are randomly distributed across the precincts before the election. Once all cryptograms in a batch are published, anyone can independently compute the tally for that batch, achieving a self-tallying property. Intuitively, our scheme transforms a national-scale election into many smaller self-tallying elections: one for each batch. Based on historical US election data, we show that when the ballot loss rates remain below 0.5%, the scheme enables tally verification for 61% of randomly selected ballots with a batch size of 100, or 37% with a batch size of 200. These figures are substantially higher than the 0.01-0.3% sampling coverage typically achieved in RLAs. This improvement stems from the fact that auditing is built directly into the paper ballot design in our scheme as an always-on feature, rather than being treated as an optional manual post-election process.
Last updated:  2026-09-03
ANARKey: A New Approach to (Socially) Recover Keys
Aniket Kate, Pratyay Mukherjee, Hamza Saleem, Pratik Sarkar, and Bhaskar Roberts
In a social key recovery scheme, users back up their secret keys (typically using Shamir's secret sharing) with their social connections, known as a set of guardians. This places a heavy burden on the guardians, as they must manage their shares both securely and reliably. Finding and managing such a set of guardians may not be easy, especially when the consequences of losing a key are significant. We take an alternative approach of social recovery within a community, where each member already holds a secret key (with possibly an associated public key) and uses other community members as their guardians forming a mutual dependency among themselves. Potentially, each member acts as a guardian for upto $(n-1)$ other community members. Therefore, in this setting, using standard Shamir's sharing leads to a linear ($O(n)$) blow-up in the internal secret storage of the guardian for each key recovery. Our solution avoids this linear blowup in internal secret storage by relying on a novel secret-sharing scheme, leveraging the fact that each member already manages a secret key. In fact, our scheme does not require guardians to store anything beyond their own secret keys. We propose the first formal definition of a social key recovery scheme for general access structures in the community setting. We prove that our scheme is secure against any malicious and adaptive adversary that may corrupt up to $t$ parties. As a main technical tool, we use a new notion of secret sharing, that enables $(t+1)$ out of $n$ sharing of a secret even when the shares are generated independently -- we formalize this as bottom-up secret sharing (BUSS), which may be of independent interest. Finally, we provide an implementation benchmarking varying the number of guardians both in a regional, and geo-distributed setting. For instance, for 8 guardians, our backup protocol takes around 146-149 ms in a geo-distributed WAN setting, and 4.9-5.9 ms in the LAN setting; for recovery protocol, the timings are approximately the same for the WAN setting (as network latency dominates), and 1.2-1.4 ms for the LAN setting.
Last updated:  2026-09-03
On the Round Complexity of Early Stopping
Wonseok Choi, Wookjin Choi, Xiangyu Liu, and Vassilis Zikas
A common pipeline of cryptographic research is: a theory paper asks an interesting question which triggers a line of works; then the problem remains dormant until technology catches up and makes the problem potentially relevant for practice; this triggers a renewed interest which at times pushes the originally theoretical ideas to practice. Several highly influential ideas have followed this pipeline: e.g., the original work on Oblivious RAMs by Goldreich and Ostrovsky [STOC'87\&90], polynomial commitments by Kate, Zaverucha, and Goldberg [ASIACRYPT'10], and many others. A problem that shows early signs of this pattern is early-stopping Byzantine Agreement (esBA): esBA protocols whose round complexity depends on the number $f$ of {\em actually} faulty parties rather than on (an upper bound on) the number $t$ of {\em potentially} faulty parties. Although it is fair to say that esBA protocols are not (yet) within the practical realm, their potential to improve large scale distributed systems like blockchain ledgers has fueled a number of recent novel results pushing the envelope in esBA feasibility (e.g., Loss and Nielsen [EUROCRYPT'24] and Elsheimy, Loss, and Papamanthou [ASIACRYPT'24]). The original starting point of this work has been to advance on the above feasibility questions. But as is common for problems following this trajectory, renewed interest often comes with observations about issues in the assumed definitions and models. Interestingly, our investigation revealed an issue with how the existing literature has been computing the round complexity of such protocols, which yields (previously unobserved) inconsistencies in the literature of esBA and more generally of synchronous protocols. In a nutshell, the inconsistencies stem from the fact that the last round of several esBA protocols has parties terminating as soon as they send a message to other parties, i.e., they don't need to wait to receive messages sent to them in that round. So, should we count this as an extra round or not? As we observe, different works give different answers to this question, and the answer one adopts affects the claimed tightness of the corresponding bounds. Building on the above observation, our work proposes a fine-grained manner of counting synchronous rounds that is both intuitive and resolves these inconsistencies. In a nutshell, our counting distinguishes between rounds in which parties might both send and receive messages, and rounds in which parties only need to send messages. Examining the existing literature through the lens of this round-counting methodology exposes gaps and new open questions in the relevant literature. We resolve these gaps and extend the landscape by several new results.
Last updated:  2026-09-03
Pairing-Based BARG for NP with Constant-Size Proofs and Applications
Zhe Jiang, Kai Zhang, Junqing Gong, and Haifeng Qian
This paper presents a pairing-based non-interactive batch argument (BARG) for NP in the common reference string (CRS) model with constant-size proofs and constant-cost verification. Our construction is fully black-box in its use of the underlying group and achieves a weak form of somewhere extractability under a new $q$-type assumption in composite-order pairing groups. We further show that this extractability guarantee implies somewhere soundness. Prior pairing-based BARGs in this setting suffer from proof size and verification cost proportional to the size of the Boolean circuit computing the NP relation, and our work removes this dependence. Technically, our starting point is the Waters--Wu framework [Asiacrypt'25] and the main idea is to replace the univariate polynomial commitment with a bivariate polynomial commitment together with univariate sumcheck arguments. This allows us to compress both wire and gate checks into a constant number of algebraic identities, leading to constant-size proofs and constant-cost verification. As a demonstration of the resulting somewhere-sound BARG, we show that it simplifies and improves existing generic constructions of NIZKs and rate-1 BARGs. In particular, we obtain: -a generic construction of NIZKs for NP from our somewhere-sound BARG, together with a one-time dual-mode commitment scheme with extraction and a leakage-resilient weak pseudorandom function. The resulting proof size is independent of the circuit size, whereas prior work incurs circuit-size-dependent proof overhead and either requires a local PRG or commits to all internal wires; -a generic construction of rate-1 BARGs from pairing-based assumptions by combining the somewhere sound BARG obtained from our construction with existing rate-1 fully local somewhere-extractable hashing. The resulting proof size is $h+\mathsf{poly}(\lambda,\log\ell)$, whereas prior work either requires proof size $h+o(h)\mathsf{poly}(\lambda,\log\ell)$ or relies on a RAM SNARG with partial-input soundness. Both generic constructions rely on weaker or fewer cryptographic primitives than prior work and the construction of NIZK also avoids the complicated parameter selection in prior work.
Last updated:  2026-09-03
Equivalence Classes of BOGI-Based Ciphers for Differential and Linear Cryptanalysis
Uncategorized
Insung Kim, Seonggyeom Kim, Sunyeop Kim, Donggeun Kwon, Byoungjin Seok, Deukjo Hong, Jaechul Sung, Seokhie Hong, Sangjin Lee, and Dongjae Lee
Show abstract
Uncategorized
BOGI-based ciphers extend the design space of GIFT by combining 4-bit S-boxes with bit permutations satisfying the ``Bad Output must go to Good Input'' principle. Prior work reduced this space to 41,472 parameter representatives, but did not determine whether their complete differential and linear trail spaces were distinct. We define DC/LC-equivalence in terms of weight-preserving bijections between the differential and linear trail sets of two ciphers for an arbitrary number of rounds, and give sufficient conditions based on permutation characteristics and trail reversal. For each pair of mixing permutations and each 4-bit permutation, we decide exactly whether the required initial word permutation exists. The relations generated by these transformations and trail reversal partition the 41,472 ciphers into 864 classes of size 48 for BOGI-64 and 5,184 classes of size 8 for BOGI-128. Using the BOGI-128 classification, we perform differential and linear best-trail searches through round 20, completing both searches for 5,081 classes. These results and additional threshold decisions show that the earliest round at which both best-trail weights reach 128 bits is round 19, attained by at least 59 classes. The class containing GIFT-128 reaches both thresholds at round 22. Thus, at least 59 classes reach both thresholds three rounds earlier than the GIFT-128 class. We also compare selected BOGI-64 and BOGI-128 instances with GIFT in hardware and software. The resulting security and implementation data can support component selection in future GIFT-based primitives.
Last updated:  2026-09-03
Efficient Soft Analytical Side-Channel Attacks on Large-Scale Cryptographic Computations
Yiteng Sun, Zhuo Huang, Yan Zhuang, Shuo Sun, Xinyu Li, Yu Yu, and Weijia Wang
Soft Analytical Side-Channel Attacks (SASCA) combine leakage-derived priors from multiple intermediate variables with their functional dependencies through belief propagation (BP).However, when applying SASCA to large-scale cryptographic computations where algorithms are abstracted into extensive factor graphs with large candidate sets per variable node, the memory and computational complexity of SASCA become prohibitive. A natural first choice for large-domain variables is to fragment them into smaller-domain variables when the underlying computation decomposes accordingly. For modular addition and multiplication, however, preserving cross-fragment dependencies can introduce short cycles and coupled factor updates, motivating alternative inference strategies. We consider the Number Theoretic Transform (NTT) in ML-DSA as a representative large-scale cryptographic computation, where standard SASCA (with FFT optimization) requires approximately 122~GB of memory for message propagation in an unprotected single-trace setting, even for a 6-layer sub-NTT component, while masking further amplifies the graph size and inference cost. To address this limitation, we propose Greedy Region-Wise Pruning SASCA (GRWP-SASCA), a practical and efficient framework that enables scalable inference by dividing the global factor graph into manageable regions. The core idea is to replace global BP with a sequence of localized inference steps, where regions are incrementally merged, and the search space is reduced via greedy pruning of redundant structures and low-confidence candidates, thereby significantly reducing the memory and computational complexity of the BP algorithm. This design provides a flexible attack strategy for large-domain arithmetic factor graphs. Our results show that GRWP-SASCA transforms previously infeasible SASCA attacks on large-scale cryptographic computations into practical ones. Theoretical analysis of single-trace attacks on unprotected ML-DSA shows that GRWP-SASCA reduces the memory overhead associated with message propagation by a factor of up to $151$ compared to the standard SASCA, while achieving an estimated speedup by a factor of $68$. For $d$-order masked ML-DSA with multiple (say, $t$) traces, GRWP-SASCA achieves an estimated reduction in memory overhead associated with message propagation by a factor of up to $388.13t(d+1.14)/(d+2.44)$, while achieving a speedup by a factor of approximately $2d + 4$. Real-device experiments on an ARM Cortex-M4 platform demonstrate that the secret can be recovered from an unprotected implementation within approximately $15$ minutes with a single trace, with a peak message memory usage of approximately 0.9 GB. For first-order masked ML-DSA, the secret can be recovered within 3.2 hours using 8 traces, with a peak message memory usage of approximately 8.1 GB.
Last updated:  2026-09-02
Collusion-Resistant Constrained PRFs for Compute-&-Compare Predicates from LWE
Jiaqi Cheng and Rishab Goyal
We design the first collusion-resistant constrained PRFs (CPRFs) for a non-trivial and expressive class of constraints from standard LWE. The two predicate classes for which we design CPRFs are: compute-&-compare and predicated range constraints. We improve our CPRF for compute-&-compare predicates to also satisfy collusion-resistant constraint privacy. An additional feature of our CPRFs is that they also satisfy (almost-)key-homomorphic property. Prior to this work, we did not have any post-quantum collusion-resistant CPRF beyond prefixfixing constraints, and collusion-resistant CPRFs for expressive predicates relied on either code obfuscation or multilinear maps. As an immediate application, we obtain a two-sided predicate encryption (PE) and functional encryption (FE) for the compute-&-compare class in the symmetric-key setting. Prior to this work, we did not have any post-quantum construction for 2-sided PE/FE beyond inner product predicates. An important contribution of this work is to introduce a new framework of purifying functionality. The main motivation behind our new framework is to systematically eliminate zeroizing attacks, which have been a highly successful cryptanalysis paradigm for breaking various candidates for advanced cryptographic objects.
Last updated:  2026-09-02
Xiezhi: Toward Succinct Proofs of Solvency
Youwei Deng, Majid Khabbazian, and Jeremy Clark
A proof of solvency (or proof of reserves) is a zero-knowledge proof produced by a centralized cryptocurrency exchange to demonstrate that it holds enough cryptocurrency to cover all customer balances, while revealing nothing beyond solvency itself. A key challenge in building practical end-to-end proofs of solvency is the cryptographic mismatch between asset keys and modern succinct non-interactive arguments of knowledge (SNARKs): many deployed account-based cryptocurrency systems use secp256k1, whereas efficient SNARKs are built over pairing-friendly curves such as bls12-381. Bridging these two settings is therefore necessary for any private end-to-end construction. We introduce Xiezhi, an end-to-end proof of solvency protocol that avoids directly translating keys across curves (which is expensive) and instead transfers asset-ownership claims into the SNARK-friendly setting with much lower proving overhead. A Rust prototype over bls12-381 shows that the reusable key-ownership phase remains practical for real-world exchanges, while the recurring asset proof has constant-size proofs and constant-time verification. For liabilities, the column-wise range proof scales linearly in proving time but keeps proof size and auditor verification independent of the number of users for fixed precision; with 32-bit balances, proofs are below 10 KB and verify in under 8 ms. These results indicate that Xiezhi offers practical end-to-end private proofs of solvency with substantially lower proving overhead than prior circuit-based end-to-end approaches.
Last updated:  2026-09-02
Fully Fluctuating Sleepy Consensus from Minimal Assumptions
Javier Nieto, Yuval Efron, Joachim Neu, and Ling Ren
Bitcoin's proof-of-work (PoW)-based protocol is remarkable for how little it asks of its participants. Not only can miners take breaks from work whenever they please, but it is almost unique in offering a path of contrition: corrupt miners can reclaim honest status simply by resuming mining on the longest chain. The protocol only requires that honest miners hold the majority of computational power at any given time. Analogous proof-of-stake (PoS) protocols, usually formalized via the sleepy model of Pass and Shi (2017), have fallen short of matching this robustness. In fact, sleepy consensus protocols in the plain PKI model must heavily restrict fluctuations in adversarial participation over time. The recent work of Efron, Neu, Pitassi (2025) enables fully fluctuating participation in the sleepy model by introducing the external adversary model. Their protocol, however, relies on verifiable delay functions (VDFs), a strong cryptographic primitive that somewhat resembles PoW, by assuming that the adversary cannot compute sequential work significantly faster than honest nodes. In this work, we design a sleepy consensus protocol for fully fluctuating participation with an external adversary under an honest majority, from minimal assumptions: a public key infrastructure (PKI) and a verifiable random function (VRF). In particular, we make no VDF or hardware assumptions. Our key technique is graded wakeness, a novel primitive that allows nodes to form consistent opinions on which other nodes are awake. We further extend our protocol to handle uncorruption, where corrupt nodes return to honesty. This extension requires only a mild additional assumption on the unpredictability of VRF outputs for liveness.
Last updated:  2026-09-02
DNSPIR: Private Information Retrieval Optimized for Privacy-Preserving DNS Lookups
Lea Nürnberger, Simon Pohmann, Mattia Veroni, and Christian Weinert
The Domain Name System (DNS) was conceived with reliability, speed, and scalability in mind, with limited consideration for privacy. Different solutions have been proposed to make DNS more privacy preserving, mostly focusing on confidentiality in transit and networking approaches to achieve unlinkability. However, DNS queries are still observable in plaintext during processing. In this work, we investigate how to achieve privacy against all involved servers through private DNS lookups via single-server private information retrieval (PIR). For this, we design a new PIR protocol that is optimized for the DNS setting. In addition to using ideas from NTTlessPIR (Li et al., CRYPTO 2024), we design a new algorithm to efficiently perform RLWE-based matrix-vector multiplication. As opposed to previous methods, it does not require NTT-friendly plaintext moduli, uses only a single key-switching key, and causes significantly lower noise growth. For a single database of 2 billion entries (the estimated number of domains in the world), our protocol allows clients to perform PIR queries with about 80KB of communication, and less than 5 seconds of server computation time. This outperforms all previous PIR schemes in terms of communication cost, at only slightly increased runtime. Additionally, our end-to-end evaluation of iterative DNS resolution across three nameservers shows sub-second lookups in smaller settings and under 5 seconds with 264KB communication for querying .com domains, which can be practical when used selectively for privacy-sensitive web browsing activities.
Last updated:  2026-09-02
PEEV: Parse Encrypt Execute Verify - A Verifiable FHE Framework
Omar Ahmed, Charles Gouert, and Nektarios Georgios Tsoutsos
Cloud computing has been a prominent technology that allows users to store their data and outsource intensive computations. However, users of cloud services are also concerned about protecting the confidentiality of their data against attacks that can leak sensitive information. Although traditional cryptography can be used to protect static data or data being transmitted over a network, it does not support processing of encrypted data. Homomorphic encryption can be used to allow processing directly on encrypted data, but a dishonest cloud provider can alter the computations performed, thus violating the integrity of the results. To overcome these issues, we propose PEEV (Parse, Encrypt, Execute, Verify), a framework that allows a developer with no background in cryptography to write programs operating on encrypted data, outsource computations to a remote server, and verify the correctness of the computations. The proposed framework relies on homomorphic encryption techniques as well as zero-knowledge proofs to achieve verifiable privacy-preserving computation. It supports practical deployments with low performance overheads and allows developers to express their encrypted programs in a high-level language, abstracting away the complexities of encryption and verification.
Last updated:  2026-09-02
Terrazzo: Memory-Aware GPU Framework for Private Transformer Inference
Rostin Shokri and Nektarios Georgios Tsoutsos
Fully homomorphic encryption (FHE) allows a server to run inference directly on encrypted data, making it a promising foundation for private transformer inference. Its dominant scheme, CKKS, has no native matrix multiplication, so the encrypted matrix multiplications at the heart of transformers dominate inference cost. The recent GL scheme supports matrix multiplication natively, but its ciphertexts, plaintexts, and evaluation keys are so large that a direct GPU implementation would require terabytes of VRAM for even small language models. We present Terrazzo, a GPU framework for the GL scheme, co-designed across cryptography, algorithms, and kernels to fit private inference on a commodity GPU. Terrazzo bootstraps into a compact Y-decoded representation, so nonlinear layers never hold full ciphertexts live; tiles all work over GL's independently schedulable ciphertext slices, sizing each tile per level against an L2 and occupancy model; confines grafting-based modulus management to application levels around a sprout-free bootstrap; and keeps every model weight at its cleartext footprint with an expansion-free plaintext pipeline. On BERT-base at full 256-input occupancy, Terrazzo achieves a 7.04 s amortized time per input on a consumer 32 GB RTX 5090. Its A100 time is 29.98 s amortized, a 2.20-20.09x speedup over prior single-A100 systems. Per-slice bootstrap speedup is 1.12–2.03x on the RTX 5090 and 1.08-1.36x on the A100.
Last updated:  2026-09-02
High-Precision Homomorphic ALU over Arbitrary Moduli with $O(1)$ Bootstrapping
Jiaming Liu, Shihe Ma, Anyu Wang, and Xiaoyun Wang
Homomorphic computation on large integers requires both arithmetic and non-arithmetic (e.g., Boolean) operations. The radix-based method by Cha et al. (EUROCRYPT'26) supports both operation types over arbitrary $n$-bit integers with a complexity of \(O(\log n)\) and \(O(1)\) bootstrapping, respectively. Meanwhile, the triangle encoding method by Gao and Zheng (CRYPTO'26) has a complexity of \(O(1)\) bootstrapping in arithmetic mode, but is restricted to power-of-two integers. Its arithmetic-to-Boolean (A2B) conversions also needs \(O(n)\) bootstrapping and is only \(O(1)\) in the amortized sense. This work improves both methods by supporting computation over arbitrary moduli with \(O(1)\) bootstrapping for both operation types, and is a generalization of Gao and Zheng's approach. Our first contribution is a framework for efficient homomorphic arithmetic over arbitrary plaintext moduli. It supports flexible radix representations and uses a CVP-based method to find defining polynomials with well-conditioned canonical embeddings and small norm growth under ring operations. When the method fails to find suitable defining polynomials, we use homomorphic Montgomery multiplication over radix-friendly plaintext rings, where each Montgomery reduction requires only $O(1)$ bootstrapping calls. Our second contribution is an efficient arithmetic-to-digit (A2D) conversion using $O(1)$ bootstrapping calls, independent of the radix used by the arithmetic representation. We implemented our method in OpenFHE. For P-384 and Curve25519, our arithmetic multiplication achieves $8.67\sim10.26\times$ and $12.57\sim13.41\times$ lower latency than CPL26's LazyMult and ExactMult, respectively. The speedups increase to $17.47\sim27.24\times$ and $25.35\sim35.63\times$ in the amortized setting. For RSA-1024 and RSA-2048, our arbitrary-modulus multiplication achieves $4.25\times$ and $7.58\times$ lower latency and $16.74\times$ and $29.85\times$ lower amortized time than CPL26's ExactMult, respectively. For 64-, 128-, and 256-bit messages, our A2B conversion is $3.75\times$, $6.40\times$, and $14.17\times$ faster than GZ26, respectively.
Last updated:  2026-09-02
Finer-Grained Fixed-Key Differential Probability Distributions via Quasidifferential Decoupling
Kai Hu, Thomas Peyrin, Quan Quan Tan, Hongyi Zhang, and Chunning Zhou
The recent study of fixed-key differential probabilities mainly follows two complementary approaches. The first derives key-dependent constraints from the internal structure of the primitive. This approach is intuitive, but a complete theory is difficult to build. The second approach is based on quasidifferentials. It is complete in theory when all quasidifferentials are considered, but exhaustive enumeration is usually infeasible in practice. In this paper, we relate quasidifferentials to concrete key-dependent constraints. This gives new insights into quasidifferentials. Each quasidifferential with a nonzero mask carries one relation, equating a linear parity of the involved key bits to a generally nonlinear Boolean function of the intermediate-state bits, and the relations that share these bits together constrain the key. Under the common threshold-based treatment, where only quasidifferential trails with sufficiently large absolute correlation are kept, some constraints on intermediate-state bits may be lost. This can produce an incomplete quasidifferential trail set with respect to the induced intermediate-state constraints. This, for example, can cause the fixed-key differential probabilities computed by quasidifferential aggregation to become negative on some key subspaces. To obtain a more precise distribution of fixed-key differential probabilities over the key space, we decouple quasidifferential trails according to their induced constraints. After decoupling, each resulting quasidifferential trail set is locally complete, hence satisfies the vector-space condition of Beyne and Rijmen as a coordinate subspace, so the derived probability distribution for the particular subspace is always valid. The decoupling also reduces the number of trails in each set, improving the efficiency of the quasidifferential method. As a result, our method yields a finer-grained key-space partition that could allow us to better approximate the true distribution under the quasidifferential framework. We instantiate this decoupling strategy in the threshold-based setting and apply it to differential trails of GIFT-64, GIFT-128, SKINNY-64, SKINNY-128, and RECTANGLE. The resulting locally complete trail sets always give valid fixed-key differential probability distributions and are no coarser than direct threshold-based quasidifferential aggregation. They coincide with direct aggregation when the retained trails are already locally complete. In our experiments, using our decoupling method is actually better for many evaluated trails and refines the key-space restrictions reported by prior constraint-detection frameworks. As each quasidifferential is a constraint, the same insight also lets us write the induced linear and nonlinear key constraints explicitly for the bit-wise ciphers GIFT-64, GIFT-128, and RECTANGLE, addressing a limitation of the Trail-Estimator constraint detector.
Last updated:  2026-09-02
A Simple Compiler for CCA2-Secure Pseudorandom Codes in the Standard Model
Nico Döttling, Antoine Joux, Venkata Koppula, Mahesh Sreekumar Rajasree, and Hendrik Waldner
Public-key pseudorandom codes (PRCs) combine two seemingly conflicting properties: their codewords are computationally indistinguishable from uniformly random strings, yet a secret-key decoder can recover the encoded message even after a bounded Hamming corruption. Security against chosen-plaintext (CPA) attacks asks that an encoding of a chosen message appears uniform. Security against adaptive chosen-ciphertext (CCA2) attacks additionally gives the adversary adaptive access to a decoding oracle for codewords outside the Hamming ball around the challenge encoding. Döttling et al. (CRYPTO 2026) showed how to realize CCA2-secure PRCs in the standard model through a generic compiler based on the Koppula-Waters hinting pseudorandom generator framework. We give a substantially simpler black-box compiler. Starting from any adaptively $\alpha$-robust, CPA-pseudorandom PRC and using only a secure PRG and an almost perfectly correct IND-CCA2-secure PKE scheme, our compiler constructs an adaptively $\alpha/2$-robust, $\alpha/2$-CCA2-pseudorandom PRC. The compiled PRC has twice the codeword length of the underlying PRC and therefore loses only a factor of two in its relative decoding radius; in particular, it preserves a constant relative decoding radius.
Last updated:  2026-09-02
Peeling Nonlinear Layers: Algebraic Cryptanalysis of Full-Round Iasta
Chandan Dey, Abul Kalam, and Santanu Sarkar
Iasta is a stream cipher designed for hybrid homomorphic encryption (HHE), with claimed $128$-bit security for its Iasta-3 and Iasta-4 instances. In this work, we present the first third-party cryptanalysis of the full-round Iasta-3 and Iasta-4 instances and further extend our approach to Iasta-5. Our cryptanalysis exploits the restricted randomness and structured construction of the nonce-dependent affine-layer matrices. We show that the matrix space contains only $2^{31.30}$ and $2^{19.62}$ distinct matrices for Iasta-3 and Iasta-4/5, respectively, compared with the $2^{29}$ and $2^{22}$ matrix randomness claimed by the designers. This restricted matrix space enables us to construct weak nonces that induce an identical matrix in the final affine layer. For such nonces, we peel off the final Cube transformation, yielding polynomial equations of degree at most $2^{d-1}$ in the secret-key coefficients, which we solve using linearization. We further consider the more restrictive class of nonces that induce identical matrices in both the initial and final affine layers. This allows us to additionally peel off the first non-linear layer, reducing the degree of the resulting equations to at most $2^{d-2}$ at the cost of introducing additional linearization variables. This extended attack substantially improves the attack complexity for Iasta-4 and Iasta-5. For Iasta-3 and Iasta-4, our best estimated attack complexities are $2^{59}$ and $2^{67}$ operations, respectively, under $\omega=2$, reducing the claimed $128$-bit security level to an almost square-root security level. Even under the conservative setting $\omega=3$, the attack requires approximately $2^{80}$ and $2^{82}$ operations against Iasta-3 and Iasta-4, respectively, both below $2^{128}$. For Iasta-5, the extended attack achieves an estimated complexity of $2^{99}$ operations under $\omega=2$. Although no overall security level is explicitly specified for Iasta-5, this result demonstrates that our attack can also reach a complexity below $2^{128}$ for this instance. In all three instances, our attacks reveal a structural weakness in Iasta arising from the restricted space of nonce-dependent affine-layer matrices.
Last updated:  2026-09-02
SING: Improving the Efficiency of MPC Protocol Assignment using Graph Neural Networks
Jannis Blüml, Moritz Huppert, Nora Khayata, Joachim Schmidt, and Thomas Schneider
Secure Multi-Party Computation (MPC) enables private computation, but has significantly higher overhead than plaintext execution. Hybrid MPC compilers improve concrete efficiency by mapping distinct computation parts to contextually optimal MPC protocols. However, state-of-the-art systems like Silph (Chen et al., S&P’23) depend on deployment-specific cost models that are cumbersome to retune, and compute mappings via brittle heuristics or costly Integer Linear Programming (ILP), limiting scalability and portability across protocols and deployment settings. We present SING, the first machine-learning-based framework for hybrid MPC share assignment. SING leverages Graph Neural Networks (GNNs) for: (1) imitation of Silph’s assignments, accelerating share assignment by up to $76,697\times$ with comparable quality; and (2) cost-driven learning, where we train a GNN cost predictor on synthetic or empirical costs (e.g., runtime or communication), freeze it, and train the share-assigning GNN to minimize predicted costs. The latter supports expressive non-linear cost models, avoiding ILP's linearity constraints, and enables retargeting to new protocol suites and deployment settings by re-fitting the predictor. Finally, we release our synthetic benchmark resources, including a dataset of 704 MPC circuits with wide-ranging hybrid assignments.
Last updated:  2026-09-02
Polytopic Sieving: Practical Low-Data Key-Recovery Attacks on Reduced-Round AES
Stefan Kölbl
Minimizing the data complexity required to recover the secret key of reduced-round block ciphers is a fundamental problem in symmetric cryptanalysis. Here, we introduce Polytopic Sieving, a data-efficient key-recovery framework and apply it to reduced-round AES. By characterizing the algebraic dependencies of anchor bytes (the reference state values that govern differential transitions across S-boxes), we show that cross-column and cross-row geometric consistency substantially restricts the realizable subkey space. We apply this framework to 4-round AES to achieve a practical key recovery using only 3 chosen plaintexts in $2^{40}$ time complexity or 4 chosen plaintexts in less than $2^{34}$ time complexity. This sets a new benchmark for data efficiency of polytopic attacks, and outperforms other recent techniques such as Subspace Trail Cryptanalysis and Mixture-Integral attacks on very low data targets. Furthermore, we extend our framework to a 5-round attack which requires only 10 plaintexts. By pairing our sieving with a dissected meet-in-the-middle approach, we can reduce both the data and time complexity over the previously best known polytopic attacks. These results establish the lowest data requirements known to date for practical key recovery on 4-round AES.
Last updated:  2026-09-02
Subring VOLE over Galois Rings with Applications to ZK over $\mathbb{Z}_{p^k}$
Ignacio Cascudo and Xiang Liu
Vector oblivious linear evaluation (VOLE) is a type of correlation that is widely used in multiparty computation (MPC) and zero-knowledge (ZK) proofs. Recently, the generation of VOLE correlation has become very efficient due to the pseudorandom correlation generator (PCGs) paradigm (Boyle et al. CCS 2018) and SoftSpokenOT (Roy Crypto 2022). This has driven a line of research on VOLE-based ZK, which enjoys linear prover time, low memory cost and post-quantum security. However, most existing works build VOLE and VOLE-based ZK over finite fields, whereas the constructions over integer rings are less satisfactory, especially in terms of communication and public verifiability. In this work, we address some of these problems using a newly introduced primitive called subring VOLE (srVOLE), which is a generalization of subfield VOLE to Galois rings. Specifically, (1) We propose two maliciously secure srVOLE protocols. One is a PCG-like protocol that achieves extremely low amortized communication. The other is a SoftSpoken-like protocol, which is compatible with the VOLE-in-the-head (VOLEitH) technique and thus can be used to construct publicly verifiable VOLE-based ZK. (2) We find that the VOLE correlation over $\mathbb{Z}_{2^k}$ used in Moz$\mathbb{Z}_{2^k}$arella (Baum et al. Crypto 2022) is a special case of our srVOLE. Therefore, based on our construction, their designated-verifier ZK protocol can be made publicly verifiable. (3) We adapt the QuickSilver (Yang et al. CCS 2021) protocols to any Galois ring and compare with existing VOLE-based ZK protocols over rings. For circuit satisfiability, our protocol only communicates 1 subring element per multiplication gate, reducing the communication by more than half. For polynomial satisfiability, our protocol supports arbitrary low-degree relations, overcoming the restrictions of existing work on degree-2 relations.
Last updated:  2026-09-02
Adaptively Secure Partially Non-Interactive Threshold Schnorr Signatures in the AGM
Renas Bacho, Yanbo Chen, Julian Loss, Stefano Tessaro, and Chenzhi Zhu
Very recently, Crites et al. (CRYPTO 2025) gave a proof for the full adaptive security of FROST (Komlo and Goldberg, SAC 2020), the state-of-the-art two-round threshold Schnorr signature scheme, which is currently used in real-world applications and is covered by an RFC standard. Their security proof, however, relies on the computational hardness of a new search problem they call “low-dimensional vector representation” (LDVR). In fact, the authors show that hardness of LDVR is necessary for adaptive security of a large class of threshold Schnorr signatures to hold, including FROST and its two-round variants. Given that LDVR is a new assumption and its hardness has not been seriously scrutinized, it remains an open problem whether a two-round threshold Schnorr signature with full adaptive security can be constructed based on more well-established assumptions. In this paper, we resolve this open problem by presenting ms-FROST. Our scheme is partially non-interactive and supports any t - 1 < n adaptive corruptions, where n is the number of signers and t is the signing threshold. Its security relies on the algebraic one-more discrete logarithm (AOMDL) assumption, the algebraic group model (AGM), and the random oracle model (ROM). Further, it achieves the strongest security notion (TS-UF-4) in the security hierarchy of Bellare et al. (CRYPTO 2022). To justify our use of the algebraic group model, we show an impossibility result: We rule out any black-box algebraic security reduction in the ROM from AOMDL to the adaptive TS-UF-0 security of ms-FROST.
Last updated:  2026-09-02
Character Block Encodings for Discrete CKKS: Single-Level LUTs and Low-Depth Arithmetic
Jules Dumezy and Elias Suvanto
Functional bootstrapping has made discrete computation practical in the Cheon--Kim--Kim--Song (CKKS) scheme, but it fuses four distinct tasks -- lookup table (LUT) evaluation, modular reduction, noise cleaning, and ciphertext refreshing -- into a single rigid pipeline. As a consequence, a generic LUT over an alphabet of size $t$ costs multiplicative depth proportional to $\log_2 t$ and consumes a large share of the modulus budget during a fixed bootstrapping procedure, invoked each time a LUT evaluation or modular reduction is needed. We show that this pipeline can be unbundled by changing the representation, rather than optimizing the bootstrapping, through block encodings. A finite-alphabet value is carried across several CKKS slots whose coordinates form a basis of functions on the alphabet, typically the characters of a finite abelian group. In such a basis, every LUT is an affine plaintext map evaluated in a single multiplicative level, with depth independent of $t$. Modular reduction comes for free: a block encoding cannot represent anything but a residue, so arithmetic modulo $t$ is native. Because every encoded coordinate has magnitude at most one, noise growth is independent of the alphabet size $t$. In the worst case, it matches the noise growth of standard discrete CKKS on the smallest alphabet $\mathbb Z_2$, and in more typical workloads it is linear in the number of operations, exponentially better than discrete CKKS at every $t > 2$. Noise cleaning becomes a constant-depth procedure of at most four levels, because the alphabet-dependent part is an LUT and only a fixed-degree-3 smoothstep is nonlinear. Finally, since LUTs are no longer part of the bootstrapping, refreshing reverts to its classical role as a maintenance operation invoked only to regain multiplicative depth. Any CKKS bootstrapping can be used, rather than a constrained and expensive pipeline. We instantiate the framework with several block encodings that make modular addition, modular multiplication, xor or min/max possible with a single CKKS multiplication. We use them to build CRT arithmetic over large composite moduli, and finite-state prefix scans for radix addition and subtraction in depth $4 + \lceil\log_2 d\rceil$ and for equality and comparison in depth $3 + \lceil\log_2 d\rceil$ for $d$ radix digits. For example, a 256-bit CRT modular addition or multiplication consumes a single multiplicative level and has a latency of 4.7 ms on a single thread.
Last updated:  2026-09-02
SoK: The Engineer’s Guide to Post-Quantum Cryptography for Embedded Devices
Nikolai Puch, Maximilian Pursche, Sebastian N. Peters, and Michael P. Heinl
Embedded systems are flexible and cost-effective, and thus ubiquitous, making them attractive targets for cyberattacks. Yet deploying advanced cybersecurity on embedded devices is challenging due to their limited computational power and memory. An emerging risk is quantum computing, which, despite being in its early stages, threatens classical asymmetric cryptography. Given the long lifespan of embedded devices, engineers must urgently address post-quantum security. Post-quantum cryptography (PQC) gained prominence with NIST’s standardization initiative for suitable algorithms. During this process, the applicability of PQC to embedded devices became a key research topic. In this work, we survey recent research on PQC for embedded systems, emphasizing applicability to specific use cases rather than focusing solely on PQC algorithms. We provide an overview of the state of the art in PQC and analyze, systematize, and contrast prior work for the three critical embedded use cases: secure communication, secure boot, and secure updates. Overall, PQC already performs competitively with classical cryptography algorithms. However, when performance and memory constraints are an issue, use case-specific considerations should be taken into account when selecting an algorithm for embedded devices. With our findings, we help developers understand the current state of research and its impact from an integration perspective.
Last updated:  2026-09-02
Degree bounds and synchronization in Gröbner basis computations for affine semi-regular systems
Momonari Kudo and Kazuhiro Yokoyama
Determining the complexity of computing Gröbner bases is an important problem in both theory and practice, and solving degrees provide a central measure of this complexity. We study solving degrees and Gröbner basis computations for affine polynomial systems, with particular emphasis on semi-regular sequences. We first derive two upper bounds for the maximum Gröbner basis degree of the homogenized system. One is based on a regular initial subsequence of the highest-degree homogeneous parts. When these parts form a semi-regular sequence in nondecreasing degree order, the bound involves the $n$ smallest input degrees together with the largest one. The other bound is expressed in terms of the saturation exponent with respect to the homogenizing variable. Both are obtained by bounding the degree from which the Hilbert function of the quotient ring associated with the homogenized system is constant. We then compare the Buchberger-like Gröbner basis computations for an affine system, its homogenization, and its highest-degree homogeneous parts. The first degree fall is characterized by failure of injectivity of multiplication by the homogenizing variable. Before that point, choices of S-pairs and reducers in any computation can be matched in the others, and reduction sequences, remainders, intermediate bases, and leading monomials correspond under specialization. Cryptographic semi-regularity guarantees this correspondence until the step degree first reaches the degree of regularity. At that degree, affine reduction steps that preserve the sugar degree lift to homogeneous ones, yielding upper bounds on the algorithmic solving degree for a computation starting directly from the affine input.
Last updated:  2026-09-02
(Im)possibility of Asynchronous MPC with Honest Majority over Blockchains
Ashish Choudhury, Sannidhi V Hebbar, Aniket Kate, Pabitra Mandal, and Arpita Patra
This work studies asynchronous verifiable secret sharing (AVSS) and asynchronous multi-party computation (AMPC) in the blockchain-hybrid model, where parties have black-box access to an ideal (asynchronous) blockchain functionality providing only persistence and eventual liveness. Motivated by the practical deployment of MPC in blockchain applications such as privacy-preserving payments and threshold wallets, we investigate whether blockchain access can improve the classical resilience bound of $n > 3t$, where $n$ is the total number of parties, and $t$ is the number of parties that can be compromised by an adversary. In particular, in the blockchain-hybrid model, we provide a comprehensive set of lower and upper bounds across three cryptographic settings: (i) no trusted setup, (ii) trusted setup with Minicrypt assumptions, (iii) trusted setup with public-key assumptions. 1. We show that without a trusted setup, or under Minicrypt assumptions, even with a setup, the classical resilience bound for AMPC is inherent: AMPC is impossible for $n \leq 3t$, even against weaker fail-stop or omission adversaries. 2. We establish separations between AVSS and AMPC in the intermediate regime $2t < n \leq 3t$: against a fail-stop adversary, unlike AMPC, AVSS is possible for $n>2t$ without any setup. Moreover, against a Byzantine adversary, again unlike AMPC, AVSS is possible for $n>2t$ under Minicrypt assumptions with a setup. 3. In contrast, under public-key assumptions with trusted setup, we construct an AMPC protocol tolerating Byzantine adversaries whenever $n>2t$. Our protocol leverages threshold homomorphic encryption, threshold signatures, commitments, and zero-knowledge proofs to minimize on-chain communication, achieving blockchain communication complexity independent of the circuit size. In the process, we define an efficient agreement on a common subset primitive for large messages in the blockchain-hybrid model, which can be of independent interest for secure distributed computing systems.
Last updated:  2026-09-02
Lemur: Scalable Post-Quantum Synchronized Multi-Signatures
Yini Lin, Muhammed F. Esgin, Amin Sakzad, Ron Steinfeld, and Markku-Juhani O. Saarinen
Synchronized multi-signatures allow for non-interactive aggregation of signatures generated within the same time step. This primitive is particularly well-suited for high-throughput blockchain protocols like Ethereum, where many distributed signers must validate the same block within a synchronized slot. In this work, we present Lemur, a post-quantum synchronized multi-signature from (module) lattices that improves upon the state-of-the-art in efficiency, scalability, and flexibility. Lemur follows the blueprint of Squirrel/Chipmunk (CCS 2022/2023) but introduces a fundamental redesign of the foundations of the overall framework. Our revisit of the framework is also motivated by the fact that our evaluation of Chipmunk's parameter sets, using the state-of-the-art lattice security estimation methods, suggests a substantially lower concrete security level (approximately 30 bits rather than the claimed 112 bits). First, we revisit the underlying building block of key-homomorphic one-time signature (KOTS) and introduce a novel security reduction based on a new lattice problem: the Dual Hint-MLWE assumption, which may be of independent interest. We then provide a formal reduction from the standard Module-LWE problem to Dual Hint-MLWE, which overall enables us to base the security of Lemur on the standard Module-LWE and Module-SIS assumptions. By shifting from a statistical security argument to a computational one, our KOTS design enjoys much better compactness and scalability. Second, we optimize the underlying homomorphic vector commitment (HVC) by transitioning from Ring-SIS to the Module-SIS setting and extending the commitment domain from vectors to matrices. This generalization reduces opening size and improves aggregation efficiency. After rectifying the parameters of Chipmunk for a fair comparison, our results show that Lemur's KOTS size achieves up to an order of magnitude improvement over Chipmunk's KOTS. In particular, aggregating 1 million one-time signatures requires under 8 KB. For the total multi-signature size, Lemur demonstrates around $2\times$ improvement over Chipmunk. To showcase our design, we provide a full-fledged Rust implementation. Our benchmarks demonstrate an aggregate signature size of 380 KB for $2^{20}$ signers. Stateful signing takes roughly 4.2 ms for a Merkle tree of height 20, while batch verification for an aggregate of 1024 signers completes in 15.0 ms ($\approx$ 14.6 $\mu$s per signer).
Last updated:  2026-09-02
Finding a Shortest Vector and More in $2^{n/2+o(n)}$ Time using $q$-ary Coset Difference Tree
Minki Hhan
This paper presents a new randomized algorithm for solving the exact shortest vector problem. For the $n$-dimensional lattice $\mathcal L$, our algorithm runs in time and space $2^{n/2+o(n)}$. Our algorithm can be viewed as a $q$-ary analogue of the midpoint Hessian for an odd prime $q$; more precisely, we use the fact that, for a shortest vector $v$, the gradient (rather than Hessian) of the periodic Gaussian function at $v/q$ is nearly proportional to $v$ (up to sign), even after aggregation over a relatively large random affine coset. We compute the relevant coset gradient along a chain of intermediate lattices using a combinatorial procedure inspired by Wagner's generalized birthday algorithm, yielding the $2^{n/2+o(n)}$ time and space complexity. A variant of the algorithm solves the exact closest vector problem on every input $(y,\mathcal L)$ with a distance guarantee $\operatorname{dist}(y,\mathcal L)\le 1.039\lambda_1(\mathcal L)$ within the same time and space complexity. This guarantee holds for a random target and a random lattice drawn according to the Haar-Siegel measure. Thus, this algorithm solves a closest vector problem on such random instances in time and space $2^{n/2+o(n)}$.
Last updated:  2026-09-01
Post-Quantum Migration for Bitcoin and Ethereum: Hidden-Key Proofs, Finalization, and Enforcement
Mehmet Sabir Kiraz and Suleyman Kardas
Quantum computers threaten the elliptic-curve signatures used by Bitcoin and Ethereum once a public key appears on-chain. Hidden-key credentials, including those controlling Bitcoin P2PKH/P2WPKH outputs and unused Ethereum EOAs, have a different risk profile: their public keys are hidden behind hash-derived addresses, but classical spending reveals them. We propose a migration design that separates revealed-key and hidden-key credentials. Revealed-key credentials may use hybrid classical/post-quantum authorization only while the legacy signing secret remains uncompromised; after quantum recovery of that secret, an independent rescue policy or pre-committed recovery credential is required to distinguish the owner from an attacker. Hidden-key credentials use STARK-verifiable ownership relations that bind a legacy identifier to a commitment to a post-quantum public key without explicitly publishing the legacy elliptic-curve public key as a public value. Complete enrollment opens the commitment and verifies post-quantum key possession. The design adds one-way migration-registry semantics, quantum hash-security analysis, scenario-based network-capacity evaluation, and an SP1-based prototype. We distinguish Groth16/PLONK wrapping, which is only a current-EVM compatibility path, from an intended quantum-era transparent verification path; the exact post-quantum security of a concrete SP1 deployment depends on the pinned SP1 version, proof mode, and all cryptographic subarguments used by that configuration.
Last updated:  2026-09-01
LatticeBlindFold: A Lattice-Based Analogue of NovaBlindFold
Luca Dall'Ava
Folding schemes compress many instances of a relation into a single accumulated one and, via composition with the Fiat-Shamir heuristic, yield SNARKs for arbitrarily large computations. However, essentially every folding scheme beyond Nova itself (including the lattice-based SuperNeo [NS26], LatticeFold(+) [BC24,BC25], and Cyclo [GLLO26]) is only randomizing, not blinding (i.e. honest-verifier zero-knowledge): its folding transcript leaks information about the witnesses being folded. We present LatticeBlindFold, a first lattice-based, plausibly post-quantum-secure analogue of the NovaBlindFold protocol [KS23,KS25], obtained by making SuperNeo blinding. This is a first step, intended to establish feasibility; for simplicity we restrict to the interactive setting. We also hope the note serves as a record of the difficulties one encounters in achieving zero-knowledge for lattice-based folding schemes. Our central technical device is the ABDLOP commitment scheme [BDL+16,LNP22], used as a commit-and-prove backbone. We mask SuperNeo's Sum-Check transcript via Libra-style polynomial masking, replace its plaintext evaluation hints with ABDLOP commitments checked homomorphically, and employ rejection sampling so that the randomized folded instance-witness pair, salts included, is simulatable. Since ABDLOP is only known to be secure over the base ring R_F and not over the extension ring R_K that SuperNeo's Sum-Check runs over, we give a component-wise instantiation of ABDLOP over R_K, translating every relation into a pair of R_F-relations once, at the level of public parameters. The resulting protocol is complete, knowledge-sound, and blinding (when a single fresh R1CS instance is folded), with security reducing to Module-SIS/Module-LWE assumptions over cyclotomic rings (together with the Extended-MLWE variant of [LNS20]). Completeness moves from perfect completeness to a statistical one, due to the introduction of rejection sampling. The price of blinding is paid through the parameters rather than the asymptotics. Rejection sampling forces a norm-decomposition depth k = Θ(log n_F), whereas SuperNeo needs only k = Θ(1). We record as a corollary an accumulator-free variant, dropping the prover-sampled blinding pairs that the main protocol carries for interface compatibility with SuperNeo's folding step, which saves a few decomposition digits (k = 26 rather than 31 at our parameters) at no cost in blinding. At a matched k the two schemes agree in prover time, verifier time, and communication up to constant factors, but measured against SuperNeo at its native parameters LatticeBlindFold carries a Θ(log n_F) multiplicative overhead in all three. Once again, all security figures we quote are interactive; a Fiat-Shamir transform instantiation would require a higher degree fields while here we focus on degree 2 for simplicity of exposition. LatticeBlindFold inherits SuperNeo's compatibility with small-field arithmetic and offers a modular, plausibly post-quantum-safe route to introducing zero-knowledge on top of a SNARK. We stress the shape of what we prove here: the LatticeBlindFold step is a single interactive step, taking its input uncommitted and outputting k committed evaluation claims together with the ABDLOP openings certifying them. Turning it into a deployable wrapper requires a decider for those claims, whether by having a downstream verifier consume them directly or by arithmetizing the ABDLOP verification; we do not construct one here, and neither recursive composition nor the instance-in/instance-out folding interface is claimed. This work is directly motivated by the Jolt Atlas zkML framework [BCDG26].
Last updated:  2026-09-01
Delegatable Anonymous Credentials from Legacy Credentials using Recursive zk-SNARKs
Leandro Rometsch, Philipp-Florens Lehwalder, Sebastian Faust, and Stefan Schulte
Digital identity systems are becoming increasingly prevalent, driven by regulatory efforts such as the European Digital Identity (EUDI) Wallet. Yet these systems usually do not achieve strong privacy guarantees as offered by anonymous credentials, since they rely on standardized curves and widespread signature schemes like ECDSA that are incompatible with pairing-based primitives underpinning most anonymous credential constructions. Recent work bridges this gap by retrofitting such legacy credentials with anonymous-credential properties via zero-knowledge proofs, requiring no issuer-side modifications. However, none of these constructions supports delegation: the ability for users to pass on a restricted credential derived from their own to another party, while all parties along the delegation chain maintain full anonymity. Delegatable anonymous credentials (DACs) provide exactly these guarantees, but are likewise incompatible with existing deployments. We present the first DAC scheme built directly on top of legacy credentials. Our construction requires no issuance infrastructure changes, and yields constant-size credentials independent of delegation depth, with full unlinkability along the chain and selective attribute disclosure at every level. We instantiate it for credentials based on JSON Web Tokens (JWTs) signed with ECDSA using Plonky2 as the recursive proving backend, contributing a secure in-circuit JWT parser that closes vulnerabilities in prior work and a Plonky2 extension for cyclic recursion with per-step zero-knowledge. At 64 attributes, delegation takes 1.2 s and verification only 3.3 ms, with a constant proof size across all delegation levels
Last updated:  2026-09-01
The Cokernel Pairing
Krijn Reijnders
We study a new pairing, beyond the Weil and Tate pairing. The Weil pairing is a non-degenerate pairing $E[m] \times E[m] \to \mu_{m}$, which operates on the kernel of $[m]$. Similarly, when $\mu_{m} \subseteq \mathbb{F}_q^*$, the Tate pairing is a non-degenerate pairing $E[m](\mathbb{F}_q) \times E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \to \mu_{m}$, which connects the kernel and the rational cokernel of $[m]$. We define a pairing \[ \langle{\quad}\rangle_m : E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \times E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \to \mu_{m}\] on the rational cokernels of $[m]$, filling the gap left by the Weil and Tate pairing. When $E[m] \subseteq E(\mathbb{F}_q)$, this pairing is non-degenerate, and can be computed using three Tate pairings, and two discrete logarithms in $\mu_{m}$, assuming a basis for $E[m]$. For $m = \ell$ prime, this pairing allows us to study $E(\mathbb{F}_q) / [\ell]E(\mathbb{F}_q)$ directly and to simplify the computation for a basis of $E[\ell^k]$, and more generally the Sylow $\ell$-torsion. This finds natural applications in isogeny-based cryptography when computing $\ell^k$-isogenies.
Last updated:  2026-09-01
Correcting the modulus switch error in TFHE bootstrapping for real-valued computation
Thomas Crasson and Florian Méhats
Torus Fully Homomorphic Encryption (TFHE) enables the homomorphic evaluation of arbitrary functions via Programmable Bootstrapping (PBS). However, the modulus switching step inherent to bootstrapping introduces a rounding error that forces the discretization of the input space, limiting the achievable precision on real-valued inputs. We propose a correction algorithm based on a first-order Taylor expansion, applied after bootstrapping, that directly mitigates this rounding error. Our method leverages the many-LUT technique to simultaneously recover encryptions of the function and its derivative within a single PBS, making the correction essentially free in terms of bootstrapping latency. We support our construction with a heuristic average-case noise analysis, validated by empirical measurements, and demonstrate a tenfold reduction in bootstrapping noise standard deviation. As a proof of concept, we apply our method to the numerical integration of ordinary differential equations under encryption.
Last updated:  2026-09-01
Reusable Fuzzy Extractors for Low-Entropy Distributions
Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, and Adam Smith
Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person's biometric is enrolled with multiple unrelated organizations). We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated (the only prior construction assumed a very specific, unrealistic class of correlations). The extractor works for binary strings with Hamming noise; it achieves computational security under assumptions on the security of hash functions or in the random oracle model. It is simple and efficient and tolerates near-linear error rates. Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates--lower than those supported by prior (nonreusable) constructions--assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. We show that such structural assumptions are necessary to support low entropy rates. We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, providing a computationally secure and an information-theoretically secure construction for large-alphabet sources.
Last updated:  2026-09-01
Distributed Key Generation for NTRU
Patrick Hough, Jérôme Nguyen, Caroline Sandsbråten, and Tjerand Silde
NTRU-based encryption enjoys compact keys and ciphertexts and admits non-interactive distributed decryption, making it an attractive basis for threshold encryption with applications to threshold FHE, threshold signatures, and electronic voting. All known protocols, however, assume a secret key shared by a trusted dealer. The public NTRU key $h = f^{-1}g$ is a nonlinear function of the secret, so distributed key generation (DKG) techniques for LWE-based schemes do not apply, and generic MPC is prohibitively expensive. We present the first dedicated DKG protocol for NTRU. Each party publishes an NTRU sample, defining a joint public key whose secret key is shared multiplicatively, and a multiplicative-to-additive (MtA) conversion yields the additive sharing required for non-interactive decryption. The protocol runs in few rounds and is actively secure with abort. At the heart of our DKG lies the MtA conversion, for which we give two efficient lattice-based certified constructions; one from additively homomorphic NTRU encryption and one from homomorphic secret sharing, both of which may be of independent interest. We demonstrate the protocol by building a threshold variant of NTRU-Encrypt, which we prove secure and instantiate with concrete parameters.
Last updated:  2026-09-01
Automated Reasoning for Indistinguishability in the CCSA
Simon Jeanteur, Laura Kovács, Matteo Maffei, and Michael Rawson
Cryptographic protocols are the foundation of secure digital communication, yet their design remains error-prone, as evidenced by the vulnerabilities that have plagued even the most widely adopted protocols throughout history. Security properties are typically formalized using either trace properties or indistinguishability, each addressing distinct security guarantees, such as agreement and authenticity for the former and anonymity and strong secrecy for the latter. Formal verification of cryptographic protocols spans both symbolic and computational models. While symbolic techniques enable automation and scalability, they do not provide computational security guarantees. Computational models, though robust, are harder to formalize and automate. Recent advances, such as the Computationally Complete Symbolic Attacker (CCSA) model and its logic, the Bana-Comon Logic (BC Logic), bridge this gap by supporting both trace properties and indistinguishability. However, despite significant progress in proof assistants, automating indistinguishability remains a challenge due to its combination of unstructured equality theories, complex non-classical calculus, and partially inductive reasoning—all requiring expert knowledge in both cryptography and logic. This paper introduces a novel approach to automate indistinguishability proofs in the CCSA model, implemented in the automated prover CryptoVampire2. We extend CryptoVampire to support indistinguishability by designing golgge, a Prolog-inspired backtracking engine over equality graphs (e-graphs), which provides strong, rewrite-driven equational reasoning capabilities. We adapt the BC Logic rules to this new framework, yielding semantically compatible statements. The effectiveness of our approach is demonstrated by automating all indistinguishability goals in the Squirrel repository.
Last updated:  2026-09-01
A Machine-Checked EUF-CMA Proof for the Hybrid Fiat-Shamir Signature Scheme
Sara Zain
Hybrid signatures are a practical approach to post-quantum migration, but their security analysis becomes subtle when two Fiat-Shamir (FS) components are binded through a single shared challenge. This paper presents the first machine-checked proof of EUF-CMA security for the FS-FS hybrid construction of Bindel and Hale (2023) formalised in EasyCrypt in the Random Oracle Model (ROM). The proof is parametrised over abstract component interfaces and establishes the intended either-component security guarantee: for either choice of component, a hybrid forgery can be reduced to an EUF-CMA forgery against that component, together with the collision resistance of the message digest and a random-oracle guessing term. In this ROM formulation, the proof does not require an independent second-preimage-resistance assumption for the challenge hash. The mechanisation makes explicit two proof obligations arising from the hybrid structure and the abstract digest: an invariant linking the lazy-oracle state to an explicit query log at the verification point, and a module-restriction framing argument for the digest-collision reduction. We further machine-check honest-signing correctness for a concrete Schnorr-Schnorr instantiation and instantiate the abstract security proof with a Schnorr-Okamoto component pair without changing the core game-hopping argument. The formalisation thereby makes explicit the assumptions, invariants, and composition structure underlying the security argument for the FS-FS hybrid.
Last updated:  2026-09-01
Open EM Side-Channel Dataset for ML-KEM (Kyber) Implementations
Alain Alyosha Magazin and Karim M. Abdellatif
We present an open dataset of electromagnetic (EM) traces captured during the decapsulation operation of ML-KEM (Kyber), the key encapsulation mechanism standardised by NIST in FIPS 203. Each trace is windowed on a single pair-pointwise polynomial multiplication, in which the decapsulation key is one of the operands, making it a recurring target of published side-channel key-recovery attacks. The dataset covers three widely used implementations: the CRYSTALS reference implementation, the Cortex-M4 optimised pqm4 implementation, and the first-order masked mkm4 implementation, with 200k traces per implementation. For the masked implementation we release the traces of both shares, enabling first-order leakage assessment and share-wise analysis rather than attacks on unprotected code alone. All measurements were taken on an STM32F407 Cortex-M4 microcontroller using a near-field EM probe. Compared to previously published datasets targeting the same operation, which provide power measurements of the unprotected reference implementation only, this dataset contributes an EM modality and covers optimised and masked code. The traces and the associated sensitive variables are distributed as chunked NumPy arrays, so that researchers without access to measurement equipment can reproduce and extend side-channel analyses of ML-KEM.
Last updated:  2026-09-01
TEE-Assisted Authenticated MPC for Resource Constrained Edge_Intelligence
Puyu Wang, Ruidan Su, Zhenshen Liu, Ruiqi Yang, Kai Fan, and Hui Li
Supporting privacy-preserving analytics across large Internet of Things (IoT) populations remains difficult. Resource-constrained devices may be unable to execute expensive multi-party computation (MPC) preprocessing or remain in a sustained many-party online protocol. We present a remotely attested, trusted execution environment (TEE)-assisted authenticated MPC multiplication scheme for large-scale edge intelligence. The TEE is deliberately restricted to the offline phase: before task-time compute committees are selected according to current edge availability and resource conditions, an Intel Software Guard Extensions (SGX) enclave provisions fine-grained authenticated material to authorized edge devices and then leaves the computation path. When a task arrives, a smaller set of $m<n$ compute committees aggregates the delegated device shares, the input owners inject their private data and model parameters through preprocessed masks, and the committees perform authenticated online multiplication without re-entering the TEE. We establish the correctness and authentication invariants of the committee-level computation and analyze the remotely attested deployment under an explicit TEE trust assumption. A hardware-SGX prototype implements the integrated scheme. The prototype generates batches of 10 million triples; at $l=1$ million in the evaluated three-recipient configuration, it achieves a $12.17\times$ preprocessing speedup over the evaluated MP-SPDZ MASCOT baseline. A separate stress test packages one preprocessing row for 100,000 recipients, and integrated tests reject ciphertext and online message-authentication-code (MAC) tampering. These results show that our scheme substantially improves preprocessing performance over the evaluated software-only protocol and is well suited to resource-constrained edge-intelligence deployments, underscoring its strong practical utility.
Last updated:  2026-09-01
A Practical Optimization for Wiedemann XL
Tung Chou and Ruben Niederhagen
Wiedemann XL is a variant of the XL algorithm that has been widely used in algebraic attacks. Usually, the cost of applying Widemann XL is estimated as 3N^2 ω, where N is the width of the Macaulay matrix, and ω is the average row weight of the Macaulay matrix. Among 3N^2 ω, 2N^2 ω is from the 1st phase of the algorithm, while N^2 ω is from the 3rd phase of the algorithm. This paper shows a practical optimization that reduces the cost of the 3rd phase by a huge factor so that its cost becomes essentially negligible compared to that of the 1st phase. Our optimization makes use of the fact that, to obtain a solution of the multivariate system, only a few coordinates of the kernel vectors are needed.
Last updated:  2026-09-01
The ePrint:2026/1591 Quantum Algorithm Does Not Solve DCP
Aparna Gupte, Seyoon Ragavan, and Mark Zhandry
In this note, we formally show that the recent algorithm by Simon (ePrint:2026/1591, August 11 2026) does not extract the least-significant bit of the dihedral coset problem (DCP) secret with non-negligible guessing advantage, and therefore does not solve DCP. We emphasize that our result is not merely about Simon's analysis of his algorithm; we are showing directly that the algorithm cannot possibly work. Our no-go encompasses a much broader class of algorithms than the specific algorithm by Simon. The main message of our no-go is that an algorithm for DCP following the template of the reduction by Regev (SIAM Journal on Computing, 2004) will probably have to make extensive use of the classical Fourier labels in the uncomputation stage. On the other hand, the algorithm by Simon can be implemented, up to error $\mathsf{poly}(n)2^{-n/3}$, using only the most-significant third of the classical Fourier labels, and therefore cannot succeed. To help with verifiability, we release Lean 4 code for our results, available at https://github.com/sragavan99/lean-ePrint-2026-1591-refutation.
Last updated:  2026-09-01
A Code-Based $(k,n)$-Threshold Secret Sharing Scheme with Integrity Verification
Sapna Jyoti Patel and Sumit Kumar Debnath
Threshold secret sharing schemes (TSSS) enable a dealer to distribute a secret among multiple participants such that only authorized subsets can reconstruct the secret while unauthorized subsets obtain no information. Existing secret sharing schemes (SSS) are often constrained by limited secret size, non-threshold access structures, or the absence of mechanisms for verifying the authenticity of shares and the integrity of the reconstructed secret. In this paper, we propose a novel $(k,n)$-threshold secret sharing scheme based on linear Maximum Distance Separable (MDS) codes. The proposed construction supports the sharing of comparatively larger secrets by representing the secret as a matrix over a finite field and exploits the linearity of MDS codes to achieve efficient share generation and reconstruction. To strengthen reliability, the scheme incorporates cryptographic hash functions for share authentication and integrity verification of the reconstructed secret. We prove that the proposed scheme satisfies correctness and perfect secrecy, thereby providing unconditional security against unauthorized coalitions. Experimental evaluation demonstrates that the proposed construction achieves efficient share generation and reconstruction while outperforming existing code-based secret sharing schemes in terms of supported secret size, scalability, and practical runtime.
Last updated:  2026-08-31
Adaptively Secure Hierarchical Attribute-Based Encryption from Witness Encryption
Rishab Goyal and Saikumar Yadugiri
Hierarchical attribute-based encryption (HABE), also called delegatable ABE, augments ABE with a public delegation algorithm that lets any user holding a secret key for a predicate $f$ locally derive a key for a more restrictive predicate $f \land g$. Since keys are no longer produced only by the master authority, an attacker may adaptively corrupt keys generated by honest users, which makes security far more delicate than for plain ABE. For general predicates, HABE was previously known in the standard model only with selective security from lattices, where the number of delegations had to be bounded a-priori and secret key size grew quadratically with it, or from obfuscation-flavored assumptions. Beyond identity-based predicates no construction achieved adaptive security without complexity leveraging. We revisit HABE through the lens of witness encryption (WE) and achieve the following. 1. A $\textbf{selectively-secure}$ HABE scheme for all polynomial-size predicates from witness encryption, statistically-sound NIZKs, and statistically-binding commitments, supporting an $\textit{unbounded}$ number of key delegations with secret key size growing only $\textit{linearly}$ with each delegation. 2. An $\textbf{adaptively-secure}$ HABE scheme for the same class, again supporting an $\textit{unbounded}$ number of key delegations, assuming in addition equivocal commitments and a mixed hierarchical functional encryption scheme, a new primitive that we introduce. Our constructions are in the standard model, avoid random oracles, complexity leveraging, and reduce black box to the polynomial hardness of the underlying primitives. On the technical front, we extend the witness encryption based ABE template of [Garg-Gentry-Sahai-Waters; STOC'13] to support public delegation. Encoding a delegated key as a proof that verifies its parent's proof makes proof size grow exponentially with the depth of the hierarchy, capping delegations at $O(1)$. So, we instead $\textit{chain}$ proofs rather than compose them. Adaptive security then calls for a genuinely hierarchical form of the dual-systems methodology, which is what mixed hierarchical functional encryption abstracts.
Last updated:  2026-08-31
Private and Verifiable Outsourcing of Open-Weight LLM Inference
Kanav Gupta, Jonathan Katz, and Ian Miers
Open-weight models allow clients to run LLMs locally, thus keeping their data private from untrusted providers. However, running large models requires massive hardware and storage resources (especially challenging on resource-constrained devices like smartphones), limiting local execution to smaller models. This leaves clients with a frustrating compromise: settle for a less-capable model that can be run locally, or sacrifice privacy by sending queries to an external server. We present an efficient protocol that allows a client to privately and verifiably outsource LLM inference of an open-weight model to a pair of malicious (but non-colluding) servers. Privacy implies that neither server learns anything about the client's queries. At the same time, the client can verify the claimed result using information posted by the model owner along with the model weights. Compared to prior state-of-the-art for private LLM inference (SIGMA, PETS' 24) -- which does not provide verifiability -- our protocol is $\approx$11--14$\times$ faster while imposing no overhead at the servers (beyond the cost of inference in the original model). Our protocol also scales to larger models not supported by prior work: for example, with our protocol a client can run the Llama 2-70B model using just 179~MB of local storage (instead of the 140~GB required to run the model locally).
Last updated:  2026-08-31
A Quasidifferential Analysis of the Wrong-Key Randomization Hypothesis
Tim Beyne, Gregor Leander, Mariia Mutkovina, and Ricardo Rodriguez Reveco
The Wrong-Key Randomization (WKR) hypothesis governs data-complexity estimates in differential cryptanalysis: wrong-key guesses are assumed to behave as a random permutation would. Exact computation of fixed-key differential probabilities was, until recently, infeasible. We use quasidifferential trails to compute the exact wrong-key distribution for the key-recovery map \(G_{k,k'} = F_{k'}^{-1}\!\circ F_k\) in PRESENT-like SPNs. A mask-first reformulation exposes a Walsh--Hadamard structure; restricting the transform to the low-dimensional support, together with SMT-guided trail enumeration, reduces the cost: for a 16-bit toy cipher, from~\(2^{80}\) to~\(2^{13}\); for \presentCipher, from~\(2^{192}\) to~\(2^{30}\); and for GIFT, from~\(2^{192}\) to~\(2^{32}\). For the toy cipher, PRESENT and GIFT, the computed distribution is a structured mixture: a large zero-probability class coexists with bottleneck classes orders of magnitude above the random-permutation mean, and nothing lies between them. Such a distribution is not unimodal, so no Poisson or binomial law fits it for any parameter and the hypothesis is formally false for all three targets. For PRESENT, however, we show that this deviation does not affect the security of Wang's 14-round differential attack. We cast the computed distribution as a structured composite hypothesis---the differential counterpart of the random-permutation/composite-hypothesis model used for wrong keys in linear cryptanalysis--and show that the shape of the wrong-key distribution, not merely its mean, governs how many wrong keys survive the key-recovery filter. For PRESENT with Wang's distinguisher, the structural signal is carried only by the right pairs, whose weight is too small for the deviation to surface; the hypothesis remains a safe heuristic in this case despite being formally false. Our SMT-based enumeration tool is publicly available.
Last updated:  2026-08-31
Order-Four Symmetry in BGV Bootstrapping: Faster Digit Extraction for Large Primes
Zhenyu Xiong, Mingsheng Wang, Zhedong Wang, and Han Wang
Bootstrapping is the computational bottleneck of BGV/BFV fully homomorphic encryption, scaling particularly poorly with large plaintext primes. Its two dominant stages: digit extraction and linear transforms. Recent work has reduced the digit-extraction polynomial degree via null-polynomial lattices and bounded-support constructions, but both evaluate the reduced polynomial via generic Paterson--Stockmeyer at cost $O(\sqrt{d})$ . We present two algebraic optimizations that address both stages simultaneously. For digit extraction, we prove that choosing the auxiliary radix $A$ with $A^2\equiv -1\pmod{p}$ induces an order-four character filter, forcing the canonical digit-extraction polynomial to satisfy $P_A(AX)+AP_A(X)=AX$ and eliminating all monomials $X^k$ with $k\not\equiv 1,3\pmod{4}$. The resulting structured decomposition$P_A(X)=\tfrac{1}{2}X+X^3Q(X^4)$ reduces non-scalar multiplications from $O(\sqrt{d})$ to $O(\sqrt{d/r})$. For linear transforms, we provide first concrete instantiation of a Galois-structured mixed-radix butterfly decomposition for non-power-of-two cyclotomics, reducing the automorphism count from $O(\sqrt{D})$ to $O(\log D)$. On the standard NTT-friendly large-prime set ($p=65537$, $m=2^{16}$, $32768$ slots), our single-threaded \HElib{} implementation achieves a $1.85\times$ digit-extraction speedup ($20.06$s to $10.81$s) and a $1.27\times$ total thin-bootstrapping speedup ($42.3$s to $33.3$s) over the state-of-the-art Ma et al.\ baseline, the three stages the method does not touch moving by at most one per cent. All comparisons are made against the Ma et al.\ baselines, run in the identical pipeline at the same auxiliary radix; across nineteen encrypted parameter sets with $1297\le p\le 65537$, the digit-extraction speedup is $1.72$--$1.88\times$ on general cyclotomic rings ($37637\le m\le 65047$) and $1.84$--$2.13\times$ on the power-of-two ring $m=2^{16}$. Every set we recommend is quoted with concrete bit security.
Last updated:  2026-08-31
Covert Federated Learning under Regulation based on Threshold Anamorphic Encryption
Wenxuan Xu, Huaqun Wang, and Debiao He
When communication systems are subject to strict external control, a powerful authority may monitor all transmitted messages and compel users to surrender their secret keys, thereby undermining user autonomy and the confidentiality of keys in encrypted communication. Anamorphic encryption (AE) enables covert communication under such surveillance by embedding hidden messages into innocent-looking ciphertexts. However, existing lattice-based AE constructions remain limited and typically rely on lattice trapdoor techniques, which impose restrictive parameter requirements and hinder their deployment in practical post-quantum cryptosystems such as Kyber. Moreover, existing constructions do not address the challenge of enabling covert communication among multiple parties under dictator-controlled environments. In this work, we propose \textbf{Threshold Anamorphic Encryption (TAE)}, a new cryptographic primitive that extends receiver-AE to the \textbf{$N$-out-of-$N$ threshold setting}, where the covert message can be recovered only through the collaboration of all $N$ participants. Then we propose \textbf{TAKyber}, a concrete instantiation of TAE constructed from the KyberPKE framework. TAKyber embeds covert information into the randomness of ciphertexts rather than the public matrix structure, avoiding the large aspect-ratio requirement imposed by lattice trapdoor techniques and enabling deployment on Kyber and other lattice-based encryption schemes whose public matrices do not satisfy such requirements. Furthermore, TAKyber distributes covert information into multiple components during encryption and enables \textbf{all $N$ participants to jointly reconstruct the covert ciphertext}, while preventing any subset of fewer than $N$ participants without the double key from obtaining any information about the covert message. Finally, we apply TAKyber to privacy-preserving federated learning, where participants can securely exchange encrypted model gradients while simultaneously transmitting covert information through the anamorphic channel under dictator-controlled environments.
Last updated:  2026-08-31
Lattice-based NIKE with optimal tightness
Roman Langrehr and Si An Oliver Tran
In this work we present a new variant of the non-interactive key exchange (NIKE) scheme based on the learning with errors (LWE) assumption and prove its security with a security reduction that incurs a security loss that is only linear in the number of users. This improves upon all prior reductions for lattice-based NIKE schemes, which had a security loss that is quadratic in the number of users. Our tight reduction can handle the setting with super-polynomial modulus-to-noise ratio and negligible correctness error as well as the more challenging setting with polynomial modulus-to-noise ratio and inverse polynomial correctness error. We also give a matching lower bound on the tightness for a natural class of lattice-based NIKE schemes (that captures all existing variants of lattice-based NIKE), showing that our security loss is optimal (up to constant factors). This generalizes a lower bound by Hesse, Hofheinz and Kohl (Crypto 2018) and is the first lower bound for the tightness of lattice-based NIKE schemes. Several previous lower bounds for the tightness of NIKE exist, but none of them can be applied to lattice-based schemes.
Last updated:  2026-08-31
Solving the Shortest Vector Problem in $2^{0.7314n+o(n)}$ Time via Discrete Gaussian Sampling on Superlattices
Yiming Gao, Yansong Feng, and Honggang Hu
We give a classical randomized algorithm for the Euclidean Shortest Vector Problem (SVP) on arbitrary full-rank lattices. It runs in $2^{0.7314n+o(n)}$ time and $2^{n/2+o(n)}$ space. More precisely, it returns a shortest vector with high probability and runs in $$ 2^{E_0n+o(n)} \quad\text{time and}\quad 2^{n/2+o(n)} \quad\text{space}, \qquad E_0=0.73133754\ldots . $$ This improves the $2^{n+o(n)}$ classical bound of Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS, STOC 2015). It also beats the previous best known worst-case quantum bounds of Aggarwal, Chen, Kumar, and Shen (ACKS, SIAM J.Comp.2025), namely $2^{0.9497n+o(n)}$ without QRAM and $2^{0.8345n+o(n)}$ with QRAM. The algorithm constructs a random prime-index superlattice $\Gamma\supset \mathcal{L}$ and applies the honest discrete Gaussian sampler of ADRS to $\Gamma$ with a parameter above the smoothing threshold. Then it simply scans the resulting samples and retains the shortest nonzero one that lies in $\mathcal{L}$. The analysis passes to the dual lattice $M=\Gamma^*$. A random linear constraint reduces the expected contribution of vectors outside $p\mathcal{L}^*$ by a factor smaller than $1/p$. A dual minimum bound, obtained by applying Poisson summation to a shortest dual line, controls the forced Gaussian mass on $p\mathcal{L}^*$. Consequently, $\Gamma$ is smooth at the sampling scale and a fixed shortest vector of $\mathcal{L}$ is hit with probability at least $2^{-E_0n-o(n)}$ per ideal sample.
Last updated:  2026-08-31
Post-Quantum Security of Keyed Sum of Permutations and Its Siblings
Nilanjan Datta, Avijit Dutta, Sougata Mandal, Hrithik Nandi, and Amlan Sinha
The rapid advancement of quantum computing poses significant challenges to the security of existing cryptographic constructions. Several constructions that are provably secure in the classical setting, e.g., the $3$-round Luby–Rackoff, Even–Mansour, Keyed Sum of Permutations, become vulnerable when the adversary is granted quantum oracle access (the Q2 model). In contrast, when the adversary is restricted to classical oracle queries while retaining the ability to perform quantum computations locally (the Q1 model), such attacks no longer apply. In this paper, we investigate the Q1 security of the Keyed Sum of Permutations construction and two closely related variants - one employing identical permutations and another using a single key. We prove that all three constructions achieve $n/3$-bit security in the Q1 model. In addition, for the same-key variant, we exhibit a key-recovery attack with matching complexity, thereby establishing the tightness of our security bound. For the remaining two constructions, we derive key-recovery attacks with complexity $2^{2n/3}$.
Last updated:  2026-08-31
APEX: AFS-based Permutation family for Efficiency and eXtensibility (feat. the APEX Suite)
Zhiguang Yan and Yongzhuang Wei
ARX-based cryptographic primitives have received considerable attention for their efficient software implementations. For a long time, however, constructing ARX primitives with provable resistance against single-trail differential and linear cryptanalysis remained an open problem. Dinu et al. addressed this problem by introducing the Long Trail Strategy (LTS), the first general design strategy for establishing such bounds for ARX symmetric-key primitives. A remaining challenge in applying LTS is the systematic design and analysis of large-state S-boxes that combine efficient implementation with strong multi-iteration differential and linear bounds. More recently, Yan et al. introduced a general framework for designing and analyzing such S-boxes, with the AFS family serving as a concrete instantiation. Given their excellent multi-iteration security bounds and outstanding software implementation efficiency, AFS boxes offer a viable solution to the core challenging problem in ARX cryptography—systematic design, accurate analysis, and the pursuit of an extreme and compact balance between cryptographic security and implementation performance. We thus argue that the potential of AFS boxes as nonlinear components in LTS-based primitives has long been undervalued. To demonstrate this potential and address the broader design challenge, we use AFS-64 to construct APEX, an efficient and extensible family of cryptographic permutations spanning state widths from 64 to 1536 bits. We then instantiate APEX in a broad range of symmetric primitives to demonstrate its extensibility and translate the security and implementation advantages of AFS into complete cryptographic designs. These include small-state hash functions and extendable-output functions, authenticated encryption with associated data (AEAD) schemes, an ultralightweight block cipher, large-state block and tweakable block ciphers, and large-state hash functions based on the Sponge-F mode and designed for China's Next-Generation Commercial Cryptographic Algorithms program. We derive differential and linear long-trail bounds for the underlying permutations and adapt the long-trail analysis to rate-restricted, same-capacity, and related-tweak settings. Together with analyses of other major attack classes, these results support the selected step counts and the stated security claims. Optimized implementations on 8-bit AVR, 32-bit ARMv7-M, and x86-64 demonstrate the practical software efficiency of APEX across diverse processor architectures. For 64-byte (resp. 1536-byte) messages, the small-state APEX-HASH functions achieve $1.14\text{--}1.37\times$ (resp. $1.14\text{--}1.17\times$) and $1.15\text{--}1.16\times$ (resp. $1.18\text{--}1.20\times$) the throughput of the corresponding Esch instances on AVR and ARM, respectively. The small-state APEX-AEAD schemes similarly achieve $1.17\text{--}1.48\times$ (resp. $1.14\text{--}1.19\times$) and $1.15\text{--}1.19\times$ (resp. $1.12\text{--}1.15\times$) the throughput of the corresponding Schwaemm instances. For the large-state hash functions targeting the NGCC program, $\mathrm{APEX}_{1536}^{12}\text{-HASH-F-512}$ achieves $2.09\times$ and $2.88\times$ the throughput of the fastest listed SHA3-512 implementations on x86-64 and ARM, respectively, for a 1-MiB message. The higher-security $\mathrm{APEX}_{1536}^{16}\text{-HASH-F-768}$ and $\mathrm{APEX}_{1536}^{20}\text{-HASH-F-1024}$ profiles achieve 6.02 and 11.82 cycles/byte on x86-64, and 123.72 and 239.63 cycles/byte on ARM, respectively. For block-cipher applications, the ultralightweight $\mathrm{APEX}_{64}^{8}\text{-BC-128}$ achieves encryption and decryption speedups of $1.18\text{--}1.21\times$ over CRAX-S across AVR and ARM, while the large-state $\mathrm{APEX}_{256}^{15}\text{-BC-256}$ achieves $1.77\times$ and $1.65\times$ speedups over SATURNIN-256/256 for encryption and decryption on ARM, respectively. The tweakable block cipher $\mathrm{APEX}_{256}^{15}\text{-TBC-256/128}$ achieves $1.38\times$ and $1.39\times$ speedups over TRAX-L for encryption and decryption, respectively. Taken together, these results show that APEX combines extensibility across state sizes and primitive classes with efficient software implementations on markedly different processor architectures.
Last updated:  2026-08-31
Arion: Arithmetization-Oriented Hashing for Zero-Knowledge Proof Systems
Luca Campa, Arnab Roy, Matthias Johann Steiner, and Stefano Trevisani
We propose the arithmetization-oriented (AO) hash function Arion, following a permutation-based design approach. We first define the permutation Arion-π over the finite field F_p, where (p > 2) is prime. The design of Arion-π is based on the recently introduced generalized triangular polynomial system, a novel algebraic framework for constructing cryptographic permutations using polynomials over finite fields. Using this permutation, we define the hash function Arion in two modes: the well-established Sponge construction and a feed-forward truncation mode (Trunc). Secure parameter sets are specified for prime fields commonly used in zero-knowledge proof applications, including the scalar fields of the BLS12-381 and BN254 elliptic curves. We provide an extensive security analysis of Arion, with particular emphasis on algebraic techniques — including interpolation and polynomial system solving (PoSSo) based techniques, such as Gröbner basis computations, and resultants — which are especially relevant for cryptographic primitives defined over prime fields. To the best of our knowledge, Arion is the first hash function whose security analysis is explicitly based on the algebraic invariant of the underlying ideal - the quotient ring dimension. In particular, we explicitly determine the dimension of the quotient ring associated with the CICO problem induced by the hashing modes. Furthermore, our analysis of the CICO-t problem applies to any t ≥ 1 and covers both the Sponge and feed-forward constructions. We evaluate the efficiency of Arion across several arithmetization frameworks — R1CS, Plonk, and AIR — and compare it with prominent AO hash functions, including Poseidon, Poseidon2, Anemoi, Griffin, and Rescue. Our results show that Arion is frequently the best-performing design in the Plonk setting and remains highly competitive, often ranking second, in both RoneCS and AIR. In terms of native performance, Arion is the only construction based on high-degree power maps that achieves performance comparable to Poseidon/Poseidon2. This makes it an attractive choice for applications where both zero-knowledge proving efficiency and native evaluation costs are important considerations.
Last updated:  2026-08-31
On the Security of Public Key Authenticated Encryption with Keyword Search with Sender-independent Search Complexity
Takeshi Yoshida and Keita Emura
Li et al. (IEEE Transactions on Dependable and Secure Computing 2026) proposed proxy-free public key authenticated encryption with ciphertext update and keyword search (proxy-free PAUKS). In this short note, we demonstrate that keyword information is leaked from updated ciphertexts. We also demonstrate that our attack is effective against the PAUKS scheme proposed by Li et al. (IEEE Transactions on Information Forensics and Security 2023).
Last updated:  2026-08-31
Quasar: A Field-Agnostic Polynomial Commitment Scheme with Polylogarithmic Verification from Quasi-Abelian Codes
Yuhao Jia, Zhe Li, Chaoping Xing, Yizhou Yao, and Chen Yuan
Polynomial commitment schemes (PCSs) are fundamental building blocks of modern zkSNARKs and often dominate their concrete prover and verifier costs. We introduce $\mathsf{Quasar}$, a field-agnostic PCS for multilinear polynomials that combines Quasi-Abelian (QA) codes with BaseFold (Zeilberger et al., CRYPTO 2024) through code switching (Ron-Zewi and Rothblum, JACM 2024). For a polynomial of length $N$ and security parameter $\lambda$, $\mathsf{Quasar}$ achieves concretely fast $O(N\log N)$ commitment, $O(N)$ evaluation time, and $O(\lambda\log^2 N)$ proof size and verifier time. Our starting point is a recent work of Li et al. (CRYPTO 2026), which shows that QA codes have fast encoding and strong concrete distance. This opens the door to building efficient PCSs from QA codes via Brakedown's paradigm (Golovnev et al., CRYPTO 2023). However, a direct instantiation, called QAPCS, inherits square-root proof size and verifier time, falling short of practical efficiency when $N$ is as large as $2^{25}$. We overcome this crucial limitation by showing that QA codes are essentially code-switchable. In contrast to existing code-switching arguments that utilize algebraic structures of either generator matrices or parity-check matrices, we look into QA encoding algorithms and propose an efficient encoding-oriented argument. Consequently, $\mathsf{Quasar}$ simultaneously enjoys fast proving from QAPCS, and polylogarithmic verification of BaseFold. We implement $\mathsf{Quasar}$ over the 127-bit Mersenne prime field with rate $1/2$ and 100-bit security. Under the 32-thread CPU setting, $\mathsf{Quasar}$ accelerates commitment and evaluation over BaseFold by $13.6\times$--$20.6\times$ and $5.2\times$--$63.8\times$, respectively. It is also $2.2\times$--$6.0\times$ faster in commitment than Brakedown and $2.1\times$--$4.0\times$ faster in commitment and $17.4\times$--$237.6\times$ faster in evaluation than BrakingBase, while providing smaller proofs and faster verification than both. Compared with QAPCS, it achieves up to $4.3\times$ faster verification and $2.9\times$ smaller proofs. Moreover, we observe that QA encoding naturally exposes massive parallelism, enabling a GPU acceleration strategy that is not directly available to the other code families. Across message lengths from $2^{12}$ to $2^{25}$, the GPU encoder is $32.9\times$--$148.3\times$ faster than the 32-thread CPU implementation. Over polynomial sizes $2^{20}$--$2^{29}$, the commitment with GPU acceleration further achieve a $3.4\times$--$16.7\times$ speedup relative to its 32-thread CPU implementation.
Last updated:  2026-08-30
Enhanced Differential-Linear Cryptanalysis of ChaCha Based on Bit Puncturing
Xinhai Wang, Lin Ding, Zhengting Li, Honglei Wang, Jiang Wan, and Bin Hu
ChaCha is one of the most extensively deployed symmetric ciphers. The security margin of ChaCha is directly related to the safety of many widely used lightweight security protocols and operating systems for constrained devices, such as TLS 1.3, SSH, Noise, WireGuard, S/MIME 4.0, Linux, Android, Chromium/Chrome, Firefox and Safari. This paper introduces a novel \textit{guessed key covering technique}. The objective of this technique is to identify partitioning-based functions whose required key bits are covered by those guessed for bit puncturing-based functions, enabling them to be processed jointly. Building on this, we propose a refined framework for differential-linear cryptanalysis of ChaCha called \texttt{ReBitP}, which combines the ideas of the bit puncturing technique, the partitioning technique and a two-phase distillation strategy. The key insight of \texttt{ReBitP} is to incorporate a carefully selected set of functions that are evaluated using the partitioning technique with different tail lengths into the first phase, without requiring additional key bits to be guessed. This early filtering via parity checks simultaneously lowers the time cost of the first phase and the time complexity of constructing the distillation table in the second phase. As applications, enhanced key recovery attacks on 7- and 7.5-round ChaCha256 are presented, achieving time complexities of $2^{142.08}$ and $2^{242.02}$, respectively. The cryptanalytic results are $2^{6.12}$ and $2^{1.58}$ times faster than the existing attacks, respectively. So far as we know, these are the best known key recovery attacks on 7- and 7.5-round ChaCha256. This definitely demonstrates the superiority of the refined framework \texttt{ReBitP}.
Last updated:  2026-08-30
Low-Latency Low-Randomness First-Order OPINI Gadgets and Their Formal Verification
Lixuan Wu, Yanhong Fan, Guowei Liu, Chaoran Wang, and Meiqin Wang
Masking is an essential countermeasure against side-channel attacks, yet implementing secure and low-latency hardware masking remains challenging. In particular, although OPINI provides strong composability guarantees for single-cycle iterative architectures, the prior low-latency OPINI gadget, HPC4, is limited to two-input multiplication. In this work, we present a low-latency, low-randomness, first-order OPINI gadget applicable to arbitrary Boolean functions, denoted as $\rm GOM$. Independent and concurrent work by Rahimi and Moradi proposes OTSM, which is also a generic, low-latency first-order OPINI gadget. Our construction involves two new techniques: (i)~extending the HPC4 idea---originally masking each share of one secret input with two bits of randomness---to masking each monomial derived from the input shares accordingly, and (ii)~a randomness-reassignment technique that enables the two circuits generating the output shares to reuse the same set of randomness while preserving the first-order OPINI security. To validate OPINI security, we propose a formal verification technique based on three symbolic reduction rules, and use it to verify multiple low-latency OPINI gadgets (i.e., HPC4, $\rm GOM$ and $\rm OTSM$). Leveraging the generality of our gadget, we instantiate several OPINI-secure S-boxes across different algebraic degrees. For the algebraic-degree-2 Ascon S-box, our gadget achieves a 21\% reduction in area and a 28\% reduction in randomness compared to the HPC4-based implementation. We further construct higher-degree S-boxes from the PRESENT, PRINCE and AES ciphers, report their hardware performance, and provide a comparison with the concurrent work $\rm OTSM$. The first-order OPINI security of all masked S-boxes is successfully verified within 20~minutes using our formal verification method. Finally, FPGA-based experiments confirm the practical security of the masked implementations.
Last updated:  2026-08-30
Full Key Recovery of Masked PRESENT on an Out-of-Order RISC-V Processor: A First Reported Case Study
Siddhartha Chowdhury, Nimish Mishra, Sarani Bhattacharya, and Debdeep Mukhopadhyay
Masking-based countermeasures such as Threshold Implementations and Probe-Isolating Non-Interference (PINI) protect cryptographic software by maintaining separation between sensitive shares under a prescribed leakage model. Modern out-of-order (OoO) processors, however, introduce backend mechanisms such as register renaming, dynamic scheduling, forwarding, speculative execution, and physical-register reuse that can create additional observations not represented at the ISA level. We develop a trace-driven backend analysis methodology that reconstructs physical-register histories and execution-time interactions from OoO RISC-V traces and relates these events to the semantics of masked computations. The analysis targets two classes of OoO-induced observations: Rename-Induced Transition Leakage (RIL), arising when distinct masked values successively occupy the same physical register, and IEW-Induced Dispatch Leakage, arising from transient overlap of share-processing instructions inside issue, execute, and writeback structures. We evaluate the methodology on masked PRESENT and on controlled compositions of first-order PINI1 gadgets. For masked PRESENT, although Q12-style rotations protect selected nonlinear operations, the affine share pair $(a_0,a_1)$ remains represented in distinct architectural registers. OoO physical-register reuse can nevertheless create transitions of the form \[ \operatorname{HW}_{\mathrm{bit}}(a_0[b]\oplus a_1[b]), \] which reconstruct the affine intermediate at the leakage-model level and yield a key-dependent channel. Using an instrumented gem5 OoO RISC-V model, we recover the complete 64-bit first-round PRESENT subkey from these backend observations. For PINI, we extend the observation space with OoO-created physical-register and backend-execution interactions and test whether each modeled observation remains simulatable within the first-order PINI circuit-share budget. The isolated gadget already exhibits local simulator-bound violations, while extending the computation through a share-wise linear layer and a second PINI1 gadget introduces additional cross-composition violations. Under the stressed baseline configuration, the number of cross-composition violation observations progresses from $0$ to $32$ and then to $128$, showing that PINI composability under its original probing model does not automatically extend to the considered OoO observation model. Finally, we evaluate physical observability on a SiFive P550-class OoO RISC-V processor using Linux-accessible thermal telemetry. A profiled forced-reference methodology directly recovers 60 of the 80 PRESENT master-key bits. Since the positions of the remaining 20 bits are known, exhaustive search over the resulting $2^{20}$ candidate space completes recovery of the full 80-bit key. Together, these results expose a cross-layer gap between software-level masking guarantees and OoO execution. Architecturally separated shares can acquire additional relationships through hidden backend state, producing observations that may exceed formal masking bounds and, in the PRESENT case, propagate into experimentally observable key-dependent behavior on real hardware.
Last updated:  2026-08-30
Wagner's $k$-Tree Revisited: Memory-Time Costs of Preimage Attacks on Incremental Hashes
Rui Ding, Lili Tang, Shaomin Chen, and Xiaorui Gong
Wagner's $k$-tree algorithm solves the generalized birthday problem and underlies preimage attacks on randomize-then-combine incremental hashes (EUROCRYPT '97) such as iSHAKE, LtHash, and AdHash. In its full-index execution, the $2^{k-1}$ index entries dominate peak memory at large $k$, and index trimming narrows each entry but leaves their number intact. Tang et al. (TCHES '26) introduced post-retrieval for the single-chain algorithm and left the $2^k$ exponent of the $k$-tree setting as an open problem. We resolve it by extending post-retrieval to the $k$-tree algorithm. This cuts the peak working memory to $P_k\ell N = O(k^2 \ell N)$, removing the $2^{k-1}$ index entries from the forward pass at the cost of a $\Theta(k)$ time overhead. Free $\delta$-level caching shrinks this time factor at no memory cost. The trade-off is starkly asymmetric: it removes an exponential number of index entries for only a linear recovery-time overhead. As a practical application, we revisit the list-item-reduction landscape for the $k$-tree algorithm under the memory-time product metric, $\mathsf{MT} = M \cdot T$. The gain is regime-dependent: for small $k$ the index entries do not yet dominate, so the recovery overhead outweighs the saving. For large $k$ the saving dominates, lowering the optimized $\log_2 \mathsf{MT}$ from $4\sqrt{n}$ to $2\sqrt{2n}$ at leading order. For fixed-size iSHAKE preimage attacks, we save approximately $51$ and $122$ bits over state-of-the-art index trimming for iSHAKE-128 and iSHAKE-256, respectively, in the unlimited-block setting, narrowing to roughly $6$ and $8$ bits under block-count caps.
Last updated:  2026-08-30
Architectural Leakage Analysis of Masked Cryptographic Software on RISC-V Cores
Siddhartha Chowdhury, Nimish Mishra, Sarani Bhattacharya, and Debdeep Mukhopadhyay
Software masking---particularly through threshold implementations---has long been regarded as a foundational defense mechanism against side-channel attacks. These schemes enforce the principles of non-completeness and uniformity, offering provable first-order resistance even under realistic leakage assumptions. However, such assurances were primarily developed under the simplified assumption of scalar or in-order execution, where instruction flow and data dependencies are well-behaved and predictable. Contemporary processors, by contrast, employ deeply optimized out-of-order (OoO) pipelines that rely on dynamic scheduling, register renaming, operand forwarding, and speculative execution. These aggressive microarchitectural behaviors, while improving performance, also create intricate dataflow interactions that can inadvertently violate the independence of masked shares. As a result, secret shares that are theoretically isolated may recombine transiently through register reuse, speculative reordering, or transition-based leakage in the physical register file. This raises a critical question: to what extent do masking countermeasures remain secure when executed on modern OoO architectures? To explore this question, we develop a systematic methodology for architectural leakage analysis based on fine-grained execution traces from an OoO RISC-V processor. The analysis correlates microarchitectural events with instruction-level behavior, reconstructs the evolution of physical-register assignments, and identifies instances where fundamental masking principles such as non-completeness or uniformity are violated. Through this structured approach, we establish a taxonomy of microarchitectural leakage classes and formalize two dominant categories: (1) \textit{Rename-Induced Transition Leakage (RIL)}, arising from register reuse and transitional dependencies between masked shares; and (2) \textit{IEW-Induced Dispatch Leakage}, originating from speculative instruction issue and execution reordering. The methodology is demonstrated across three representative studies: (i) a masked Toffoli gate, where violations of non-completeness are revealed; (ii) a masked PRESENT cipher, where 571 leakage events are identified due to register-induced transitions; and (iii) a Probe Isolating Non-Interference (PINI) experiment, which exposes how speculative and dynamic scheduling can compromise isolation guarantees, thereby weakening the composability of masked implementations that are provably secure under idealized models. These results underline a fundamental insight: the security of masking countermeasures cannot be evaluated in abstraction from the hardware on which they execute. Ensuring true resistance to side-channel attacks demands a holistic view that jointly considers both the algorithmic soundness of masking constructions and the microarchitectural realities of modern processors.
Last updated:  2026-08-30
Trust the Voice, Hide the Source: Anonymous Provenance for Verifiably Edited Audio
Xiyuan Fu, Zixing Wang, Yuncong Zhang, and Yu Chen
As synthetic speech becomes increasingly realistic, the need to authenticate audio recordings has become more urgent. Such authentication should allow a released recording to demonstrate that it was captured by an authorized device and modified only through the declared edits, while concealing both the unreleased content and the identity of the particular recorder. In this work, we propose PPAAS, a privacy-preserving framework for authenticated audio editing under a formal security model. The framework integrates a privacy-preserving capture-authentication scheme and a specialized zero-knowledge proof protocol for authenticated editing. The capture-authentication scheme establishes that the recording was produced by an authorized device group while concealing both the unreleased content and the individual recorder. The proof protocol certifies that the published audio results from a valid editing process and that the declared edits were applied correctly, while avoiding general-purpose circuit conversion and redundant proof generation over the full recording. It also naturally supports a broad class of audio transformations. We implement PPAAS and benchmark it against a general-purpose zkSNARK baseline for the same edit relations. The results show that our capture-authentication scheme is practical for resource-constrained recording devices, and for a $2^{14}$-sample removal from a $2^{19}$-sample recording, our proof protocol achieves $398\times$ faster proof generation and $160\times$ faster verification, reduces prover peak memory by over $1600\times$, and produces a $45\%$ smaller proof than the baseline.
Last updated:  2026-08-30
Careful with the Ring: Enhanced Hybrid Decoding Attacks against Module/Ring-LWE
Jianhua Hou and Haodong Jiang
In order to reduce size and improve efficiency, many lattice-based cryptographic schemes adopt structured variants of the Learning With Errors (LWE) problem, such as the Module-LWE and Ring-LWE. Nevertheless, when analyzing the concrete security of lattice-based schemes, these algebraic structures are usually not considered, given the absence of techniques to exploit them for accelerating known attacks. For the widely-used polynomial ring $\mathbb{Z}_q[x]/(x^N+1)$, we first propose an enhanced hybrid decoding attack against Module/Ring-LWE by leveraging the ring structure to accelerate its guessing and decoding steps. Then, we theoretically show that compared to the prior hybrid decoding attack, our new attack can lead to a complexity improvement linear in $N$ in the sparse secret setting. Moreover, we implement our new enhanced hybrid decoding attack on the benchmark instances established by [WSM+25, S{\&}P], and achieve several new records. In particular, compared with state-of-the-art methods given by [KKN+26, EC], our approach is 17$\times$ to 114$\times$ faster on the known broken instances. Finally, we show how to estimate the concrete bit security with our new hybrid attack under the same model as in the lattice estimator, and perform the analyses of the latest sparse Ring-LWE parameter sets used in Fully Homomorphic Encryption (FHE) schemes including [JM22, EC], [CCKS23, CCS], [BCKS24, EC], [CHKS25, EC] and [AKP25, C]. The numerical results show that compared to the best-known attack, our enhanced attack can improve the attack complexity by up to 13 bits for all the considered parameter sets. In particular, under our new enhanced hybrid decoding attack, 12 out of the 16 parameter sets fall below the targeted 128-bit security level.
Last updated:  2026-08-30
Efficiently Provable Approximations for Non-Polynomial Functions
Sriram Sridhar, Shravan Srinivasan, Dimitrios Papadopoulos, and Charalampos Papamanthou
Zero-Knowledge Proofs (ZKPs) are now widely used to verify the correctness of various types of computations. However, despite phenomenal advancements, current ZKPs are inefficient for applications that need accurate evaluation of non-polynomial functions over floating-point numbers, such as machine learning, decentralized finance, scientific computing, and geolocation. Current state-of-the-art approaches typically emulate floating-point numbers using fixed-point representations (via quantization), and handle \textit{non-polynomial} functions using lookup tables, piece-wise or low-degree polynomial approximations, which lead to sub-optimal performance and/or loss in accuracy or generality, limiting their potential for adoption in practice. In this work, we present a general framework for approximating a large class of non-polynomial functions using Gauss-Legendre quadrature, which supports efficient ZKPs of correct computation. We show that our approach can scale to decrease the error up to the inherent limits imposed by quantization, without increasing the multiplicative circuit depth beyond a small constant ($\leq 4$). This is a strong deviation from prior approximation techniques, where decreasing the error leads to increased multiplicative depth -- the main factor determining the error growth of an approximation. We implement and evaluate our approach in Noir/Barretenberg, and we obtain absolute errors $2-256\times$ lower than comparable baselines for most non-polynomial functions with low prover overhead. We also demonstrate an efficient prover and low errors for high-accuracy applications in DeFi and astronomy that require non-polynomial functions, again obtaining errors $4-64\times$ lower than the baseline approximations.
Last updated:  2026-08-30
Quantum Pessiland
Boyang Chen, Tomoyuki Morimae, and Takashi Yamakawa
Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of $UP\cap coUP$ implies $P^{\#P}\not\subseteq i.o.BQP/qpoly$, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from $P^{\#P}\not\subseteq i.o.BQP/qpoly$, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].
Last updated:  2026-08-29
The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and OPRFs
Mihir Bellare, Rishabh Ranjan, Doreen Riepel, and Ali Aldakheel
This paper initiates a concrete-security treatment of two-party secure computation. The first step is to propose, as target, a simple, indistinguishability-based definition that we call InI. This could be considered a poor choice if it were weaker than standard simulation-based definitions, but it is not; we show that for functionalities satisfying a condition called invertibility, that we define and show is met by functionalities of practical interest like PSI and its variants, the two definitions are equivalent. Based on this, we move forward to study the concrete security of a canonical OPRF-based construction of PSI, giving a tight proof of InI security of the constructed PSI protocol based on the security of the OPRF. This leads us to the concrete security of OPRFs, where we show how different DH-style assumptions on the underlying group yield proofs of different degrees of tightness, including some that are tight, for the well-known and efficient 2H-DH OPRF, and thus for the corresponding DH PSI protocol. We then give a new PSI protocol, called salted-DH PSI, that is as efficient as DH-PSI, yet enjoys tighter proofs.
Last updated:  2026-08-29
Spectral Theory of Isogeny Graphs and Quantum Sampling of Secure Supersingular Elliptic Curves
Maher Mamah, Jake Doliskani, and David Jao
In this paper, we study the problem of sampling random supersingular elliptic curves with unknown endomorphism rings. This problem has recently gained considerable attention as many isogeny-based cryptographic protocols require such ``secure'' curves for instantation, while existing methods achieve this only in a trusted-setup setting. We present the first provable quantum polynomial-time algorithms for sampling such curves with high probability, one of which is based on an algorithm of Booher et. al. One variant runs heuristically in $\tilde{O}(\log^{6.5} p)$ quantum gate complexity, and in $\tilde{O}(\log^{20} p)$ under the Generalized Riemann Hypothesis, and outputs a curve that is provably secure assuming quantum average-case hardness of the endomorphism ring problem. Another variant samples uniform $\mathcal O$-oriented curves with unknown endomorphism rings, for any imaginary quadratic order $\mathcal O$, with security based on the quantum average-hardness of Vectorization problem. When accompanied by an interactive quantum computation verification protocol, our algorithms provide a secure instantiation of the CGL hash function and related primitives and show quantum advantage over classical algorithms. Our analysis relies on a new spectral delocalization result for supersingular $\ell$-isogeny graphs: we prove the Quantum Unique Ergodicity conjecture and provide numerical evidence for complete eigenvector delocalization. We also prove a stronger $\varepsilon$-separation property for eigenvalues of isogeny graphs than that predicted in the quantum money protocol of Kane, Sharif, and Silverberg, thereby removing a key heuristic assumption in their construction.
Last updated:  2026-08-29
Universally Composable Hybrid PAKE Secure Against Harvest-Now-Decrypt-Later Attacks
Yasmine Vazirinejad, Feng Hao, You Lyu, and Shengli Liu
We present a hybrid password-authenticated key exchange (PAKE) protocol that is secure against harvest-now-decrypt-later (HNDL) attacks by quantum adversaries, and is universally composable under the parallel composition framework of Lyu and Liu (EUROCRYPT 2025). Existing hybrid PAKE constructions combine a classical PAKE with a post-quantum (PQ) PAKE, with the overall security intended to rely on the stronger of the two. However, identifying which PAKE is stronger is non-trivial, given the limited maturity of post-quantum PAKE designs. Recognizing that the immediate quantum threat is passive, we propose a different hybrid compiler: rather than combining two PAKEs, we encapsulate a classical PAKE within a standard post-quantum Key Encapsulation Mechanism (KEM). This modular separation avoids the fragility of post-quantum password handling while neutralizing HNDL attacks. Our compiler works with any two-pass or three-pass PAKEs. As a concrete instantiation, we construct a three-pass protocol that combines J-PAKE and a post-quantum KEM. We also implement the resulting protocol and provide performance results demonstrating that the hybrid construction remains practical, with the complete handshake executing in $2.81\text{ ms}$. This construction has the distinctive advantage that it does not require any ideal cipher, (constant-time) hash-to-curve, or trusted setup assumptions. Within the Lyu-Liu framework, we show that J-PAKE satisfies the notion of a Full DH-type PAKE. We model the KEM as a password-independent Simulatable DH-type component satisfying the minimal simulation properties required for parallel composition. To capture the prospective quantum threat, we formalize a stronger variant of the standard HNDL threat model—where the quantum adversary is explicitly granted the plaintext password—and prove that our protocol achieves Session Key Security and Post-Quantum Forward Secrecy. Our construction relies solely on standardized and widely deployed primitives, yielding a hybrid PAKE that is UC-secure, efficient, and well-suited for real-world deployment during the post-quantum transition.
Last updated:  2026-08-29
Silent-Share: Decoupling Hidden Threshold Matching from Pairing Operations via Group-Valued Oblivious Key-Value Stores
Jie Zhang, Xiaohong Li, Ruitao Feng, and Guangdong Bai
Matchmaking encryption (ME) enables bilateral access control with private policies, but existing pairing-based constructions tie receiver-side authorization cost to the policy size. This is especially problematic when one party holds a large hidden policy while the other holds only a small attribute set. We present Silent-Share, a bilateral hidden-policy threshold access-control protocol that decouples policy representation from pairing-based authorization. The construction combines a one-sided hidden-threshold policy-based key encapsulation mechanism (PB-KEM) with a sparse group-valued oblivious key-value store (GOKVS). The GOKVS compactly encodes policy-dependent group elements, so a receiver holding attribute set $\mathcal{A}$ performs exactly $2|\mathcal{A}|$ pairings, independent of the policy size $|\mathcal{P}|$ and threshold $d$. Total decapsulation additionally incurs a hidden-threshold reconstruction cost, characterized separately. Two independent one-sided instances are composed and bound with AES-GCM to realize bilateral authorization. We prove one-sided KEM confidentiality and policy hiding in the random-oracle model under a hidden common exponent assumption, and extend these guarantees to the bilateral composition. Our implementation on BN254 shows that, when the correct $d$-subset is provided, one-sided decapsulation for $|\mathcal{A}|=10$ takes about $394$ ms, dominated by pairing operations. The pairing-based authorization layer remains flat as $|\mathcal{P}|$ grows from $50$ to $800$, confirming the policy-size independence. The hidden-threshold reconstruction cost is reported separately and can dominate when $|\mathcal{A}|$ is large. Encapsulation is approximately $2$--$3\times$ faster than fuzzy matchmaking encryption across the tested parameter range.
Last updated:  2026-08-29
The Extended Wedge Attack
John Baena, Javier Verbel, and Luis Villota
The wedge attack of Ran (EUROCRYPT 2026) recovers the secret oil space of a UOV public key over fields of characteristic two by exploiting the fact that the polar forms of the public map are alternating. It has since been generalized in several directions, each carrying its own algebraic tools, e.g., Jin et al. (PKC 2026). Working directly with the polynomials of an oil and vinegar map, we give a simpler description of the attack, based on a dual decomposition of oil-vinegar polynomials, and we recover the original wedge attack and its odd-characteristic analogue as special cases. This framework leads to a generalization, which we call the extended wedge attack. We identify two explicit conditions on the parameters that guarantee that the attack terminates with the recovery of the secret space. We also prove that the matrix of the extended wedge attack is permutation equivalent to the truncated Macaulay matrix in the attack by Furue-Ikematsu (CRYPTO 2026).
Last updated:  2026-08-29
Communication-Efficient Private Join and Compute over Distributed Input Sets
Yunqing Sun, Xinran Cai, Hanlin Liu, Xiao Wang, and Wei Dong
Private Join and Compute (PJC) enables two parties to compute aggregates over matching records from their private datasets. In this work, we focus on the inner-product variant of PJC, which computes the inner product over matching records from their private datasets. It has important applications such as privacy-preserving ad conversion measurement. However, existing PJC protocols assume each party holds the entire dataset, which is often unrealistic in practice, where relevant datasets are distributed across multiple data owners. No existing PJC protocols directly support distributed input sets across multiple clients, while straightforward generic approaches introduce substantial overhead. We propose an efficient approximate PJC protocol for distributed input sets while keeping the communication sublinear in the input size. Our protocol works in the semi-honest setting and uses two non-colluding servers that learn nothing beyond the final approximation. The core technical contribution is a novel adaptation of the G\"odel Prize-winning AMS sketch redesigned for efficient evaluation under fully homomorphic encryption. Concretely, we show a new structured randomness that can be homomorphically generated from short seeds using just 3 levels of multiplication while maintaining the best plaintext accuracy bound. Based on our optimized implementation, clients can insert each input element into an encrypted sketch in 30 ms, which has a size of 250 KB, independent of input size. The servers can recover the final output within seconds, orders of magnitude faster than the generic method.
Last updated:  2026-08-28
BREAKMEIFYOUCAN!: Exploiting Keyspace Reduction and Relay Attacks in 3DES and AES-protected NFC Technologies
Nathan Nye, Philippe Teuwen, Tiernan Messmer, Steven Mauch, Struan Clark, Zinong Li, Zachary Weiss, and Lucifer Voeltner
This paper presents an in-depth analysis of vulnerabilities in MIFARE Ultralight C (MF0ICU2), MIFARE Ultralight AES (MF0AES), NTAG 223 DNA (NT2H2331G0 and NT2H2331S0), NTAG 224 DNA (NT2H2421G0 and NT2H2421S0), and widely circulated counterfeit Ultralight C cards based on Giantec GT23SC4489, Feiju FJ8010, and USCUID-UL. We reveal multiple avenues to substantially weaken the security of each technology and its implementation across a range of configurations. We demonstrate how, through relay-based man-in-the-middle techniques and partial key overwrites --- optionally combined with tearing techniques --- an attacker can reduce the keyspace of two-key Triple DES (2TDEA) from $2^{112}$ to $2^{28}$ or less in certain real-world deployments, thereby making brute-force key recovery feasible with modest computational resources. We further discuss how the MIFARE Ultralight AES protocol can be similarly affected, particularly when CMAC integrity checks are not enforced. We also find that the security offered by NTAG 223 DNA and NTAG 224 DNA is undermined by the absence of integrity checks on commands and the calculation of a CMAC over Secure Unique NFC (SUN) messages, providing an unauthenticated ciphertext oracle that facilitates key recovery. Field observations, especially in hospitality deployments, underscore the urgent need for proper configuration, key diversification, and counterfeit detection.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.