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

Last updated:  2026-09-14
Towards Making Doubly-Efficient PIR Practical
Pan Xiao, Heng Zhang, Rending Ouyang, Cong Zhang, Jian Liu, Kui Ren, and Chun Chen
Doubly-efficient private information retrieval (DEPIR) enables sublinear per-query work (in the database size $N$) for both client and server, while requiring no client state. Despite its theoretical promise, single-server DEPIR exhibits a prohibitive concrete efficiency gap: for $N=2^{23}$, the state-of-the-art construction (Eurocrypt '25) requires a 733TB server state and over $2^{37}$ online RAM/Disk reads, rending it infeasible to execute. This paper advances single-server DEPIR towards practicality through a series of algorithmic innovations. Compared with the state-of-the-art, we achieve a 4 orders of magnitude reduction in server state and a 6 orders of magnitude reduction in query time. In particular, for the same level database ($N=2^{23}$), querying $5461$ elements in a single batch requires only 171GB of server state and $2^{24}$ online RAM/disk reads, yielding a 112s total query time and a 21ms amortized query time.
Last updated:  2026-09-14
New Pseudorandom Correlation Functions and Exponent VRFs from DCR
Archisman Dutta, Lisa Kohl, Lawrence Roy, and Peter Scholl
Pseudorandom correlation functions (PCFs) allow two parties to expand short correlated keys into an unbounded, locally evaluatable source of correlated randomness. In this paper, we give the first constructions of PCFs for correlated oblivious transfer (COT) and vector oblivious linear evaluation (VOLE) correlations over $\mathbb{Z}_M$ for an arbitrary modulus $M$, with reasonable concrete efficiency. Our construction comes with a lightweight, two-round distributed setup protocol, and relies solely on the decisional composite residuosity (DCR) assumption. As part of our security analysis, we introduce a new family of extended power DDH problems over subgroup indistinguishability groups, and give a novel master theorem showing that this is implied by standard DCR. This suffices to prove security of our PCF based on DCR, and also implies that prior constructions relying on related power-DDH style assumptions in composite groups can be based on DCR alone. We further extend our construction to obtain a PCF for oblivious linear evaluation (OLE) and general degree-two correlations over $\mathbb{F}_2$. As an application of our PCF for VOLE, we derive a designated-verifier exponent-verifiable random function (eVRF), where the publicly verifiable output is the VRF output in the exponent. As an independent contribution, we additionally give a publicly verifiable eVRF from an offline/online variant of homomorphic secret sharing. Both of these constructions have much shorter proof sizes than prior work.
Last updated:  2026-09-14
Simple and Efficient SKL-IBE with Classical Revocation from LWE
Ho Nguyen Pham, Duong Hieu Phan, Quoc-Huy Vu, and Weiqiang Wen
Secure key leasing (SKL) is a quantum cryptographic primitive that enables the leasing of decryption keys to delegated users with the guarantee that, once revoked, the lessees irreversibly lose decryption capability. A key feature that makes SKL practically relevant is classical revocation: the ability to revoke keys at any time and from anywhere, without relying on a quantum channel. In this work, we revisit SKL schemes for public-key encryption (PKE) and identity-based encryption (IBE), and present a new approach for concrete efficiency under the standard Learning With Errors (LWE) assumption. First, we refine the security analysis of the Dual-Regev SKL-PKE scheme with classical revocation from [Ananth, Poremba, and Vaikuntanathan, TCC 2023; Ananth, Hu, and Huang, TCC 2024], establishing security under the polynomial hardness of LWE with polynomial modulus. Together with the resource efficiency of the Dual-Regev-based construction, our analysis shows that this approach yields the most quantum-efficient known SKL-PKE scheme. Second, we present a simple and efficient construction of selectively secure SKL-IBE with classical revocation from standard LWE. Our approach directly extends the Dual-Regev SKL-PKE within the IBE framework of [Agrawal, Boneh, and Boyen, Eurocrypt 2010], avoiding garbled circuits and obfuscation-based assumptions and achieving improved concrete efficiency over prior generic approaches.
Last updated:  2026-09-14
Dimension Reduction for Theta Series of Ideal Lattices
Runkun Liu, Zhaoyang Liang, and Dan Ding
Theta series are fundamental functions that record lattice-vector lengths and connect lattice geometry with Gaussian quantities such as Gaussian mass and the smoothing parameter. For ideal lattices under the canonical embedding, arithmetic coordinates are generally coupled, making fixed-coset theta-series evaluation and related Gaussian computations difficult in high dimensions. We show that an explicit, verifiable relative-basis condition yields an exact factorization of each fixed-coset theta series into lower-dimensional factors. For each fixed coset, when n = ℓ n₀, its n-dimensional theta-series computation is replaced by ℓ independent computations in dimension n₀. Equivalently, the canonical Gram matrix is block diagonal in the relative coordinates, and the factorization holds for every Gaussian parameter without approximation or a smoothing assumption. We verify the condition for several cyclotomic and non-cyclotomic extensions and derive explicit formulas for representative cyclotomic families. The same factorization gives lower-dimensional identities for Gaussian masses, independent Gaussian sampling within a fixed coset, and smoothing-parameter equations. It reduces the dimension of each coset calculation, while the outer sum over the residue classes in I_q remains unchanged. Our implementation achieves speedups of up to 335×, 215.45×, and 7.9× for fixed-coset theta-series evaluation, numerical smoothing-parameter evaluation, and sequential Gaussian sampling, respectively.
Last updated:  2026-09-14
Client-Efficient Online-Offline Private Information Retrieval
Hoang-Dung Nguyen, Jorge Guajardo, and Thang Hoang
Private Information Retrieval (PIR) permits clients to query data entries from a public database hosted on untrusted servers while preserving client privacy. Traditional PIR models suffer from high computation and/or bandwidth overhead due to linear database processing for privacy. Recently, Online-Offline PIR (OO-PIR) has been proposed to improve PIR practicality by precomputing query-independent materials to accelerate online access. While state-of-the-art OO-PIR schemes (e.g., S&P’24, CRYPTO’23) successfully reduce online processing cost to sublinear levels, they still impose substantial bandwidth and storage burdens on the client, especially when operating on large databases. In this paper, we propose Pirex, a new two-server OO-PIR with semi-honest security that offers minimal client inbound bandwidth and storage cost while retaining the sublinear processing efficiency. The Pirex design is simple with most operations are naturally low-cost and streamlined (e.g., XOR, PRF, modular arithmetic). We have fully implemented Pirex and evaluated its real-world performance using commodity hardware. Our results showed that Pirex outperforms existing OO-PIR schemes by at least two orders of magnitude. With a 1 TB database, Pirex takes 55ms to retrieve a 4 KB entry, compared with 9-30s by state-of-the-art. For practical databases with billions of 4 KB entries, Pirex only takes 16 KB of inbound bandwidth, which is up to three orders of magnitude more efficient.
Last updated:  2026-09-14
On the Security of Constraint-Friendly Map-to-Curve Relations
Youssef El Housni and Benedikt Bünz
Standard hash-to-curve constructions first hash the message to a field element through a cryptographic hash-to-field step, then map this field element to an elliptic-curve point. Inside constraint systems, this inner cryptographic hash is often the dominant cost. Groth, Malvai, Miller and Zhang (Asiacrypt 2025) introduced \emph{constraint-friendly map-to-elliptic-curve-group relations} that bypass this step, achieving substantial reductions in circuit size. Their security proof works in the Elliptic Curve Generic Group Model (EC-GGM). We identify three gaps. First, the security bound in terms of the message space size $M$ and tweak bound $T$ is not explicitly analyzed, and the bounds stated for the concrete instantiations are loose. Second, the EC-GGM does not capture the algebraic structure of most deployed curves; we exhibit a concrete signature forgery using the parameters claimed secure. Third, the construction requires a congruence condition on the field that is not satisfied by all deployed curves; we extend it to any field, although witness generation remains practical only for fields of low 2-adicity. As a countermeasure we propose a $y$-increment variant that, on the $j=0$ curves used in practice, neutralizes the algebraic attack, removes the field restriction in practice, and preserves a comparable constraint count. We implement and benchmark both constructions in the open-source gnark (Go) library; the attack is additionally demonstrated via a self-contained SageMath simulation and confirmed at the circuit level against the authors' own Noir (Rust) implementation.
Last updated:  2026-09-14
Fast cube roots in Fp2 via the algebraic torus
Youssef El Housni
Computing cube roots in quadratic extensions of finite fields is a subroutine that arises in elliptic-curve point decompression, hash-to-curve and isogeny-based protocols. While the factorization $p^2-1=(p-1)(p+1)$ suggests a known subgroup decomposition, computing a cube root via separate operations in the two subgroups does not beat a direct $\mathbb{F}_{p^2}$ exponentiation in practice. We propose a carefully engineered algorithm that reduces the $\mathbb{F}_{p^2}$ cube root to a single $\mathbb{F}_p$ addition chain and a single Lucas sequence in the algebraic torus $\mathbb{T}_2(\mathbb{F}_p)$. The concrete formulas apply to primes $p \equiv 1 \pmod 3$ with $v_3(p-1) \leq 2$, which includes all six primes considered here. We prove correctness in all residuosity cases and implement the algorithm in Go. Benchmarks on six primes spanning pairing-based and isogeny-based cryptography show $1.6–2.3 \times$ speed-ups over direct (addition chain) exponentiations in $\mathbb{F}_{p^2}$.
Last updated:  2026-09-14
Leopard: A High-Performance Framework for Updatable Private Set Intersection
Xiaowei Li, Shi-Feng Sun, Yanxue Jia, Hao Li, and Dawu Gu
Updatable Private Set Intersection (UPSI) extends conventional PSI protocols to dynamic scenarios, where input sets evolve over time. A straightforward approach is to rerun the entire PSI protocol after each update, incurring redundant computational and communication overhead. Although several UPSI schemes have been proposed to enable updates without full protocol re-execution, existing constructions remain impractical. Building on the high efficiency of unbalanced PSI designs, this work introduces Leopard---a general framework that leverages unbalanced PSI to realize UPSI without complete re-execution, while handling both insertions and deletions. Leopard is compatible with any unbalanced PSI protocol and achieves further performance gains by reusing internal data structures across updates. Specifically, we observe that certain data structures in unbalanced PSI can be incrementally updated instead of fully rebuilt. We provide an FHE-based instantiation of Leopard that demonstrates substantial performance improvements through such data structure reuse. Through comprehensive experiments, we evaluate Leopard's performance. Compared to Badrinarayanan et al. (ASIACRYPT 2024) and Alborch et al. (ACNS 2026), our instantiations reduce computational cost by up to 111.28× and at least 1.48×, and communication cost by up to 118.97× and up to 522.01×, respectively.
Last updated:  2026-09-14
A unified reduction from RLWE to MP-LWE
Alice Pellet-Mary and Wenwen Xia
The Middle-Product Learning With Errors (MP-LWE) problem, introduced by Roşca, Sakzad, Steinfeld, and Stehlé (Crypto 2017), is a structured variant of LWE defined independently of any specific number field $K$. Its hardness has been based on the hardness of Ring-LWE (RLWE) over families of number fields. Two main reductions exist, one from Roşca, Sakzad, Steinfeld, and Stehlé (Crypto’17) and Njah Nchiwo and Pellet-Mary (PKC’26), and another one due to Peikert and Pepin (Journal of Cryptology’24). Both reductions cover different families of number fields, and none of the two supersedes the other. In this work, we propose a unified reduction from RLWE to MP-LWE parameterized by a pair of field elements $(y_a,y_s) \in K^2$, which recovers both prior reductions as concrete instantiations. Optimizing the choice of $(y_a,y_s)$, we obtain the first reduction from RLWE to MP-LWE that holds for all number fields $K = \mathbb{Q}[X]/f(X)$ where $f$ is a monic irreducible polynomial of a given degree and with polynomially bounded coefficients (and whose discriminant is coprime to the modulus $q$ of the RLWE and MP-LWE problems, a constraint that also appeared in previous works). This new reduction supersedes the two previously known reductions.
Last updated:  2026-09-14
Provenance Graphs for AML/CFT: Asset Tracing and Freezing in Private Payments
Maxence Brugeres and Petr Kuznetsov
Anti-money laundering and counter-terrorist financing (AML/CFT) rules require payment service providers to assess incoming funds' provenance: for a target account, which earlier transfers contributed to it, how closely, and through which intermediaries? On transparent ledgers such as Bitcoin or Ethereum, this reduces to a graph traversal over the public transaction history. In private payment systems such as Zerocash or Tornado Cash Nova coins are burnt and created at each payment, while the sender, receiver, and amount are hidden. Provenance analysis is then impossible: the cryptography protects ordinary and illicit users alike. This creates an apparent deadlock, not merely a trade-off. We avoid this deadlock by giving a regulator a specific and bounded investigative capability rather than full visibility or none. Our construction extends Zerocash but applies naturally to most private systems with the same spend-and-create coin model (Tornado Cash, Railgun, Lelantus, etc.) The capability is backward provenance within a bounded neighbourhood of a transfer, together with the power to freeze funds derived from a designated illicit source, and to reconstruct a full clear-text provenance graph when a holder chooses to disclose. Everything outside that capability remains hidden from the supervisor and from every other party: receivers, amounts, the link from an output to its later spend, and the provenance of any coin that has not been disclosed.
Last updated:  2026-09-14
Selective ML-Guided Beam Search for Differential-Trail Discovery in GIFT-64
Alireza Gholizadeh Shahrbejari and Reza Ebrahimi Atani
Beam search bounds differential-trail exploration, but may still expand many intermediate differences. We test whether a learned short-horizon tail-cost residual can reduce this work while leaving classical selection in control. A regressor estimates a residual adjustment to an active-nibble heuristic. With four or two rounds remaining, the post-selection policy protects the best $25\%$ of the classical frontier, removes at most $30\%$ of accepted states, and abstains when fewer than five states can be pruned. It cannot restore candidates already rejected by classical selection. We develop the method on a state-grouped GIFT-64 corpus and evaluate it on $D=8$ and $D=12$ holdouts and a $D=16$ stress test. Target recovery and the best classical cost are preserved on all $48$ holdout cases and all $18$ stress cases. Aggregate node reductions are $6.832\%$, $0.099\%$, and $0.040\%$ at $D=8$, $D=12$, and $D=16$. An equal-budget ablation fixes the frontier, protected core, and pruning quota while changing only the removed-state ranking. Learned and classical ranking preserve all $48$ holdout cases, with aggregate reductions of $2.359\%$ and $2.411\%$. Their removal sets differ on $57$ of $85$ active frontiers, but the learned score does not establish a measurable advantage over the classical control. Random ranking produces larger raw reductions but loses quality. All comparisons use a bounded classical baseline; no globally optimal trails are claimed.
Last updated:  2026-09-14
Optimal Amplification via Bias-Resilient Combiners
Benny Applebaum and Nathan Geier
Cryptographic combiners take $n$ candidate schemes for some primitive $P$, and realize it securely provided that at least $k$ candidates are secure. Intuitively, we expect that if we plug $n$ independent instances of a $\delta$-weak candidate for $P$ into the combiner, assuming $\delta \ll (n-k)/n$, security should be amplified and the resulting candidate should exhibit a significantly smaller weakness. This intuition relies on the implicit “all-or-nothing” assumption that each candidate fails with probability $\delta$ and is otherwise perfectly secure, allowing us to bound the failure probability of the combiner using a simple binomial tail bound. However, this intuition often fails for standard security notions where, for example, a weak candidate may consistently leak partial information rather than exhibit a clean all-or-nothing failure. Recently, Applebaum, Bitansky and Geier (CRYPTO 2026) showed that indistinguishability combiners inherently act as security amplifiers. However, this general result incurs a multiplicative loss of roughly $2^{n-k}$ in the error parameter relative to the natural all-or-nothing bound. Moreover, the combiner-is-amplifier approach is fundamentally restricted to the regime $\delta < 0.5$. Consequently, both the resulting error rate and the amplification threshold $\delta_0$ are suboptimal. In this work, we overcome these limitations by establishing a new specialized framework of bias-resilient indistinguishability combiners. This formulation allows us to achieve the optimal all-or-nothing bound without the exponential penalty. We observe that bias-resilience provides a unifying abstraction for security amplification across different primitives, neatly capturing prior ad hoc results such as those for weak PRGs and weak NIZK. As our main application, we use this framework to establish a generalized XOR lemma over prime fields $\mathbb{F}_p$, showing that the sum modulo $p$ of independent weakly pseudorandom elements becomes computationally indistinguishable from uniform. This improves upon a recent work by Shimizu and Yasunaga (STOC 2026) by achieving a sample complexity that is independent of the field size. Finally, we explore the idealized notion of an all-or-nothing amplifier. We establish a tight characterization of the multiplicative penalty incurred when applying such an amplifier to candidate schemes that only guarantee standard weak indistinguishability error.
Last updated:  2026-09-14
Optimistic History-Independent Sleepy Atomic Broadcast
Kwok-Yan Lam, Zhenliang Lu, Qiang Tang, and Xinrui Zhang
The latency of sleepy consensus protocols has been improved significantly, with recent designs achieving constant-round confirmation. However, existing protocols either rely on unrealistic additional assumptions about access to historical messages, where messages sent in round $t$ may depend on messages received in rounds $[t-k,t-1]$ for some $k>1$, or do not consider optimizing performance under optimistic conditions. In this work, we study history-independent sleepy atomic broadcast protocols while simultaneously considering optimistic conditions, where messages sent in round $t$ depend only on messages received in round $t-1$. We first design a sleepy atomic broadcast protocol that achieves a confirmation latency of $2\Delta$ ($\Delta$ is the upper bound on network delay) and an optimal latency of $\Delta$ under up to $1/5$ corruption. Second, we present a super-optimistic atomic broadcast protocol, achieving a best-case latency of $2\Delta$ under fault-free executions. Building on this insight, we propose an optimistic sleepy atomic broadcast protocol that relaxes the super-optimistic condition to tolerate sub-optimal faults. As a building block, we introduce an optimistic graded agreement protocol, $OptimisticGA$, which enables a dynamic optimistic quorum with four decision grades. Built on $OptimisticGA$, our optimistic atomic broadcast protocol achieves a good-case latency of $2\Delta$ when the leader is honest, while tolerating up to $1/6$ corruptions rather than requiring a fault-free setting. When corruption is more than $1/6$, it seamlessly adapts to $1/3$ resilience with a good-case latency of $3\Delta$. All protocols require no historical messages and tolerate an adversary that grows proportionally with honest nodes, with a minimal delay of $\Delta$.
Last updated:  2026-09-14
NTRU with Hints: Secret Key Recovery under Partial Leakage on NTRU-based Signatures
Honglin Shao, Yuejun Liu, Mingyao Shao, Wei Cheng, and Yongbin Zhou
Post-quantum cryptography has become pivotal for ensuring communication security in the quantum era. NTRU-based signature schemes have gained attention due to their computational efficiency and compact public keys and signatures, which reduce communication overheads. However, the algebraic structure of NTRU lattices introduces vulnerabilities in physical attack scenarios, where partial secret key leakage can severely undermine system security. In this paper, we propose the Dimension-and-Sample Reduced NTRU Attack (DSRNA). The core principle of DSRNA is to apply a dimension-reduction strategy that transforms the NTRU instance into a lower-dimensional NTRU instance with fewer samples, which is efficiently solvable via lattice basis reduction. Furthermore, we design a unified hint-embedding technique that jointly exploits side information from both secret keys $f$ and $g$, thereby improving both attack efficiency and success rates. We evaluate the residual security of Falcon and its variants Mitaka and Hawk, under perfect, modular and approximate leakage models. Experimental results demonstrate security degradation. Compared to the method of May et al. at Asiacrypt 2023, DSRNA achieves speedups of $5.8\times$ for Falcon-512 with 400 leaked coefficients and over $29.4\times$ for Falcon-1024 with 905 coefficients. This study reveals the potential vulnerability of NTRU-based signature schemes to partial secret key leakage.
Last updated:  2026-09-14
Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes
Thai Hung Le
Enhanced Gabidulin Matrix Codes (EGMC), introduced by Aragon, Couvreur, Dyseryn, Gaborit, and Vincotte at Asiacrypt 2024, were designed to hide the algebraic structure of Gabidulin matrix codes while enabling very compact McEliece- and Niederreiter-type encryption schemes, with ciphertexts as small as 65 bytes at the claimed 128-bit security level. Their security relies on the assumption that a masked EGMC code is hard to distinguish from a random matrix code. We show that this enhanced construction leaves enough structure for an equivalent code of the secret key to be recovered. Unlike previous cryptanalysis, our attack combines combinatorial and algebraic techniques to recover a Gabidulin-equivalent compressed code. This code can then be extended to a full-length equivalent secret key in polynomial time. As a result, the attack provides both a distinguisher and a key-recovery attack against the EGMC encryption schemes. The attack breaks all 16 proposed EGMC parameter sets by large margins. For example, for the claimed 128-bit parameter set (2,17,37,4,0), it reduces the security level from 186 bits to 35 bits and in our implementation, the equivalent secret key of this parameter set is recovered in less than 10 minutes.
Last updated:  2026-09-14
Robust Side Channel Analysis with Blocking and Quantification of Leakage
Alicja Kario and George Pantelakis
While an abundance of SCA methodologies have arisen over the years with impressive theoretical backgrounds, they fail to take into account some important real-world aspects in the analysis. Most of them fail on three key points. First, most assume IID or normally distributed data points in their framework without verifying that the experimental setup indeed meets that requirement. Second, most methods rely on visual aspects or failed statistical tests to define the success or failure of the tests without quantifying the precision of their measurement with formal boundaries. Third, in most cases, the test harness is not completely oblivious to the secret data, remaining completely free of data-dependent branching, conditional formatting, or conditional triggering, which can leak environmental noise and contaminate the data points. We are proposing a new SCA methodology, which we named BLAQ, to bridge this gap between the theoretical mathematical models and the real-world imperfect testing environment.
Last updated:  2026-09-14
Storing Less in-the-Head: An Area-Efficient Hardware Architecture for SDitH-v2
Stef Halmans, Niklas Höher, Dina Hesse, Sanjay Deshpande, Jakub Szefer, and Tim Güneysu
In 2022, the National Institute of Standards and Technology (NIST) initiated a second call for post-quantum digital signature proposals to broaden algorithmic diversity beyond the already standardized schemes based on structured lattices and hashes. While five out of the 14 second-round entries were built on the MPC-in-the-Head paradigm, only two advanced into the recently announced third round. Despite their theoretical appeal, available results on their implementation costs imply a reduced applicability to resource-constrained embedded devices. In this work we analyze one of the remaining candidates, the revised second version of the Syndrome Decoding in the Head (SDitH) signature scheme based on the VOLE-in-the-Head framework, and showcase that these issues are not inherent to the family of algorithms. We propose an area-efficient hardware design including highly optimized variants of both Batch Line Commitment (BLC) and Polynomial Interactive Oracle Proof (PIOP) routines. As a result, we reduce memory requirements by a factor of 22 to 52 compared to the approach of the reference implementation and by a factor of 40 to 88 compared to the previous hardware implementation of SDitH-v1, while still achieving competitive runtimes. To the best of our knowledge, this yields the most compact hardware implementation of any MPCitH or code-based signature primitive, with our algorithmic improvements directly transferable to software designs. During our analysis, we additionally determined nine significant discrepancies between specification and reference implementation of SDitH-v2, with a subset breaking test vector compatibility. Beyond addressing these issues, we suggest specification changes to further reduce resource usage on embedded targets without compromising security assumptions.
Last updated:  2026-09-14
A Partial Injection from Unsatisfiable to Uniquely Satisfiable Quadratic Systems
Gabriele Radici and Massimiliano Sala
Let $\mathrm{MQ}_0(n)$ and $\mathrm{MQ}_1(n)$ be the sets of square systems of $n$ quadratic equations in $n$ variables over $\mathbb{F}_2$ having, respectively, no solution and exactly one solution, and write $\alpha_0=|\mathrm{MQ}_0(n)|$, $\alpha_1=|\mathrm{MQ}_1(n)|$. It is known that $\alpha_0<\alpha_1$, so injections $\mathrm{MQ}_0(n)\hookrightarrow\mathrm{MQ}_1(n)$ exist; the proof is a counting argument and produces no map. We exhibit a partial injection $\tau$, in the following sense. The map $\tau$ adds to a system a single correction supported on an affine flat of codimension two through a point read off by a three-point decoder; it is computable in $\Theta(n^3)$ bit operations from the dense coefficient representation, with no precomputation and no advice. We prove that there is a subset $\mathcal{D}\subseteq\mathrm{MQ}_0(n)$ with $|\mathcal{D}|/|\mathrm{MQ}_0(n)|>0.745$, uniformly in $n\ge3$, on which $\tau$ is injective into $\mathrm{MQ}_1(n)$. We then show that inverting $\tau$ is \emph{equivalent} to locating a zero of the image system --- the solvable case of the multivariate quadratic problem, and its one-solution case on the uniquely solvable part of the image --- and that $\tau$ is randomly self-reducible on each orbit of its symmetry group. Under the standard assumption that solvable $\mathrm{MQ}$ is hard on average --- the planted-$\mathrm{MQ}$ assumption of $\mathrm{MQ}$-based identification and signature schemes --- $\tau$ is therefore a one-way function, injective on $\mathcal{D}$, explicit and randomly self-reducible on each orbit, between two sets which are, as languages, complexity-theoretically far apart. We also show that the associated flat-collision problem is NP-complete.
Last updated:  2026-09-14
Angular Watermarking: Sharp Leakage Bounds and Public Subspace Validation
Bin He
Fresh payloads need not hide persistent watermark geometry. For a Gaussian latent model with refreshed fair angular bits and isotropic covariance, we derive the exact fourth-order signature, the boundary of distributional hiding, and an attainable obstruction imposed by a uniform decoding margin. A fixed-probe learner has sufficient observation count O(p3 log p/c2) at fixed rank, accuracy and confidence, where c is the angular signal strength. Our central statistical result is a sharp, dimension-independent centered fourth-tensor covariance bound. It yields public finite-sample lower bounds on a frozen candidate’s carrier overlap, using independent validation directions, a carrier-dimension bound and scale information, without the secret key or payload. Exact partial-index spectra expose the tradeoff between geometric compression and validation variance. On eight fixed candidates, known- and unknown-scale lower bounds average 0.173 and 0.057, while oracle overlap averages 0.600. Population identities characterize feedback signal; a paired, budgeted MIPP comparison evaluates empirical training with independent Gaussian threshold calibration and a shared public spectral initialization control. All rank failures, zero-threshold sensitivities and negative results are reported. The guarantees concern latent subspaces under the stated iid model and exact arithmetic. They do not establish convergence of same-data adaptive training, ordered bit recovery or a neural watermark attack.
Last updated:  2026-09-14
Sublinear-Communication Layered MPC from HSS
Anasuya Acharya, Pierre Meyer, Divya Ravi, and Rahul Satish
The server-aided Secure Multi-Party Computation (MPC) model with dynamic participation, where servers may join or leave during the computation is particularly well-suited for practical, long-running applications. Unfortunately, existing protocols supporting dynamic participation either incur communication costs that scale linearly with the circuit size or rely on the heavy hammer of Fully Homomorphic Encryption (FHE). This contrasts with “classic” MPC protocols, where sublinear communication can be achieved without FHE. Focusing on the Layered MPC framework (introduced by David, Ishai, Konring, Kushilevitz, and Narayanan, CRYPTO 2023), we show that this overhead is not inherent. We construct sublinear-communication Layered MPC protocols while maintaining a minimal number of online servers — only two or three per layer. Our constructions rely on a layered-friendly adaptation of Homomorphic Secret Sharing (HSS), which we formalize as HSS with Layered Resharing.
Last updated:  2026-09-14
Silk: Computation-Efficient and Post-Quantum-Friendly Randomness Beacon
Binyang Hou, Jiamian Yan, Liang Zhang, Borui Chen, and Haibin Kan
Distributed randomness beacons enable mutually distrustful parties to jointly generate public randomness. Several existing beacons built from secret sharing use costly pairings or group operations to verify shares. Their underlying discrete-logarithm assumptions are also vulnerable to quantum attacks. Moreover, running a separate Byzantine fault-tolerant (BFT) consensus instance for each output incurs repeated computation and communication costs, even when secrets are shared in batches. We present Silk, a computation-efficient, post-quantum-friendly and deterministic randomness beacon under partial synchrony. Silk's sharing protocol, Mulberry, realizes batched asynchronous verifiable secret sharing with partial output (bAVSS-PO), using hash-based share verification to reduce computation cost. Silk further amortizes BFT consensus across a batch of outputs, requiring only one BFT instance per batch. We establish Mulberry's bAVSS-PO properties and Silk's beacon properties under static corruption and the stated security assumptions. We implement Silk and Mulberry in Rust and evaluate their computation and communication costs. In WAN experiments with 121 replicas across eight AWS regions, Silk achieves a throughput of 5.414 outputs/s, 1.53× that of Rondo [NDSS'25] and 4.18× that of Spurt [IEEE S&P'22].
Last updated:  2026-09-14
Scale, Round, Break: Simple Leakage Attacks on Secret Sharing Schemes
Katharina Boudgoust and Mark Simkin
We study the local leakage resilience of $t$-out-of-$n$ threshold secret sharing schemes. We present a remarkably simple, perfectly correct attack that fully breaks any scheme with linear reconstruction over a finite field using $\lg t + \mathcal{O}(1)$ bits of leakage per share. In particular, this yields concretely efficient attacks on additive secret sharing and on Shamir’s scheme for arbitrarily large thresholds over arbitrarily large finite fields. Our key technical idea is an approximately linear scale-and-round function that maps shares from an arbitrarily large field into a much smaller ring, while preserving the distance of well-separated secrets. Our results provides two surprising insights: Bigger finite fields do not necessarily improve leakage resilience and increasing the reconstruction threshold in Shamir’s scheme does not help too much either.
Last updated:  2026-09-14
Finite-Precision Error Analysis of Cryptanalytic Model Extraction
Duo Xu, Liu Zhang, and Zilong Wang
Cryptanalytic model extraction treats the parameters of a neural network as hidden secrets and attempts to recover them from black-box oracle access. Existing attacks have shown that such recovery is possible for several neural-network architectures, but practical evaluations typically assume high-precision target-model evaluation, often in float64. This assumption creates a mismatch with deployed machine-learning systems, where models are commonly evaluated in float32 or lower-precision formats. We study cryptanalytic signature recovery under finite-precision target-model evaluation. We decompose the recovery pipeline into numerical subproblems, including critical-point localization, finite-difference estimation and perturbed linear-system solving, and analyze how errors are introduced, propagated, and amplified across these stages. We further relate the resulting perturbation amplification to intrinsic properties of the target network, including the geometry of local linear regions and local parameter-to-gradient sensitivity. In particular, we derive approximate instability boundaries for key precision-sensitive stages of the recovery pipeline. When the target model is evaluated in float32, oracle-induced perturbations cannot be removed by higher-precision downstream computation, leading to a substantially higher local error floor than in the float64 setting. Experimental results suggest that recovery becomes less stable as the network size increases. We also discuss how the finite-precision perspective extends to hard-label recovery and piecewise-affine network components, while smooth non-piecewise-linear activations require additional curvature-aware error modeling.
Last updated:  2026-09-14
SoK: Private Transformer Inference Across Systems, Models, and Cryptography
Andes Y. L. Kei and Sherman S. M. Chow
Private inference can protect user queries and model weights without trusted hardware or statistical privacy relaxations, but transformers combine large secret matrix multiplications, costly nonlinearities, and sequential autoregressive execution. Prior surveys organize the literature mainly by cryptographic backend, deployment setting, or supported operation, obscuring when techniques remain applicable or composable across execution phases, model adaptations, or security boundaries. We systematize 58 cryptographic private transformer frameworks (2022--2026) across three interacting levels: systems (execution and optimization), models (cryptography--machine learning co-design and adaptation), and cryptography (secure realization of transformer operations). This analysis reveals two recurring cross-backend applicability constraints: optimizations do not transfer unchanged across execution phases when they require values not yet available, while data-dependent pruning, cache management, routing, and sparsity require private execution structure to be hidden, constrained, predicted, or disclosed. Against an output-only reference baseline, we identify four classes of security concerns affecting 5 frameworks and synthesize composition boundaries in maliciously secure designs. We find that 16 frameworks rely on empirically calibrated or distribution-specific mechanisms and 21 require additional training, limiting generalization and cross-framework comparability. We distill these findings into 12 open problems and 16 outlooks spanning protocol efficiency, cross-level co-design, dynamic execution, security, evaluation, and scalability.
Last updated:  2026-09-14
On the (Im)possibility of Asynchronous Proactive Secret Sharing
Erica Blum, Yingzi Gao, Julian Loss, Yuan Lu, Zhenliang Lu, and Qiang Tang
In this paper, we systematically study the (im)possibilities of proactive secret sharing (PSS) in fully asynchronous authenticated networks. To reflect the subtleties arising from the absence of a global clock, we first formalize a hierarchy of natural mobile adversary models for asynchronous PSS (APSS), capturing different adversarial capabilities over corrupted parties and distinct ways of accounting for mobile corruption in asynchrony. Under these models, we then (i) establish new impossibility results by exhibiting generic attacks on APSS, thereby deriving the corresponding resilience upper bounds, and (ii) demonstrate the tightness of these bounds via explicit APSS protocols achieving optimal resilience in each model.
Last updated:  2026-09-14
Fair Distributed Exchange via Threshold Adaptor Signatures
Ruben Baecker, Paul Gerhart, Jonathan Katz, and Dominique Schröder
Adaptor signatures enable scriptless protocols on blockchains such as Bitcoin by allowing a buyer to lock a coin based on an NP statement and release payment to any party that reveals the corresponding witness. They underlie a broad class of layer-2 protocols, including payment channels, cross-chain swaps, and coin-mixing services, which today secure billions of dollars in locked value. Fairness for existing adaptor-signature constructions, however, is inherently two-party, so does not apply to deployments in which the buyer or witness holder is operated by a committee. In this work, we formalize and solve the fair exchange problem in that setting. We consider a buyer group holding shares of a signing key controlling a coin, and a seller group holding shares of a secret witness. The goal is to guarantee fairness both between groups (ensuring that each group obtains its asset if and only if the other does), as well as within groups (ensuring that all honest buyers learn the witness and all honest sellers receive payment), even in the presence of malicious insiders and/or partial information leakage. We present efficient protocols achieving these guarantees under standard cryptographic assumptions on scriptless blockchains with timelocks. Our construction introduces two new primitives of independent interest, threshold adaptor signatures and certified witness encryption, which we define, analyze, and instantiate efficiently.
Last updated:  2026-09-14
Refining Leakage Diagram Analyses for Random Probing Security
Sonia Belaïd, Ghozlane Boukacem, Gaëtan Cassiers, Victor Normand, and Mélissa Rossi
Masking is a widely used countermeasure against side-channel attacks, where sensitive variables are split into randomized shares in order to prevent information leakage from intermediate computations. Its security is commonly analyzed in the random probing model, in which each internal variable leaks independently with some probability $p$. Constructing large masked circuits that achieve random probing security (RPS) is challenging, and a common approach is to rely on composability frameworks ensuring that suitable local gadget-level properties imply circuit-level guarantees. Recent works have introduced compositional frameworks based on leakage diagrams to derive security guarantees in the random probing model. While elegant and scalable, these approaches rely on conservative analyses and security proofs tailored to specific gadget constructions. In this work, we revisit and refine a leakage-diagram approach published in TCHES 2023. We formalize and generalize the proof to show that the probability of an orbit in the leakage diagram upper bounds the adversary's RPS advantage. Our analysis identifies the local gadget-level conditions needed for this composition result, refines the analysis of edge inclusion probabilities in leakage diagrams for the underlying multiplication gadgets, leading to tighter final security bounds, and improves the combinatorial analysis of orbits through a detailed study of small cases and new structural properties for larger ones. We evaluate the resulting constructions on AES. Our results significantly improve the concrete security guarantees compared to previous leakage diagram analyses, while also improving the randomness complexity compared to existing composable approaches.
Last updated:  2026-09-14
Quantum Discrete Logarithms on Elliptic Curves with $5n/2+o(n)$ Logical Qubits and $\widetilde O(n^2)$ Toffoli Gates
Sunghyeon Jo and Gye Jin Lee
We give a quantum algorithm for the elliptic curve discrete logarithm problem over an \(n\)-bit prime field using \(\frac{5}{2}n+o(n)\) logical qubits and \(\widetilde O(n^2)\) Toffoli gates. Luo et al.'s exact space-efficient affine construction uses \(3n+O(\log n)\) qubits with \(O(n^3/\log n)\) Toffoli gates; ours lowers the leading qubit term from \(3n\) to \(\frac{5}{2}n\) and the Toffoli count to near-quadratic. We construct an exact in-place modular inverter with \(\frac{3}{2}n+o(n)\) logical qubits and \(\widetilde O(n)\) Toffoli gates. For consecutive Euclidean remainders \(R>r\) and coefficient magnitudes \(0\le T<t\), the invariant \(Rt+rT=p\) allows us to store only three of \(R,r,T,t\) in the persistent Euclidean state and reconstruct the fourth on demand. Temporary Euclidean data are recovered from the updated state and erased after each update. The arithmetic queries used in these steps are implemented in sublinear workspace using measurement-based uncomputation. We then use Hua's identity to reduce the variable-square multiplications needed for affine point addition to inversions, yielding exact controlled point addition within \(\frac{5}{2}n+o(n)\) logical qubits and \(\widetilde O(n)\) Toffoli gates.
Last updated:  2026-09-14
Revisiting Differential-Linear Cryptanalysis via a Walsh-Transform Perspective
Jiahui He, Kai Hu, Zhongfeng Niu, Bart Preneel, and Meiqin Wang
Standard differential-linear (SDL) cryptanalysis has matured rapidly, now backed by the SDL connectivity table (SDLCT) framework, multi-round middle-part extensions, and automated CP-based search models. The rotational differential-linear (RDL) variant lacks even an SDLCT counterpart, and the analogous combination of internal differentials with linear approximations, which we call internal differential-linear (IDL) cryptanalysis, has never been formulated. We unify SDL, RDL, and IDL in a single Walsh-transform framework on the difference transition function (DTF). Existing SDL machinery, including recent multi-round middle-part search models, transfers to RDL and IDL, yielding efficient correlation computation and distinguisher search. For ARX primitives, we derive a $2\times 2$ matrix-product formula for the SDL and RDL correlations of a single modular addition. The formula exposes a rank-$1$ structure on the input-difference matrix that decouples the running product into independent factors, making a CP approximation with only linear inequalities and table lookups practical. This partially resolves the open problem of Niu et al. (CRYPTO 2022). We apply the framework to \xoodoo-$p$, \ascon-$p$, \alzette, \siphash, and \specksixtyfour. For \xoodoo-$p$, we obtain a 6-round RDL distinguisher and the first IDL distinguisher in the literature (both at 6 rounds). For \ascon-$p$, the first RDL distinguisher (6 rounds). For \alzette, an 8-round RDL distinguisher, doubling the previous 4-round best. For \siphash, the longest known distinguisher (5 rounds). For \specksixtyfour, the longest known SDL distinguisher (14 rounds).
Last updated:  2026-09-14
Compare Before Clearing: Exact Integral-Comparison Frontiers for Lattice Extraction
Xiang Wang and Shihui Fu
Lattice extraction often produces openings normalized by challenge differences, whereas an inconsistency must ultimately yield a short integral SIS relation. Clearing each extracted branch before comparison removes every denominator obstruction carried by that branch, including factors irrelevant to the mismatch that is eventually tested. We formalize direct integral comparison for generic polynomial block systems. If block \(a\) has width \(r_a\) and the two extraction centers differ on \(J\), the minimum worst-case coefficient degree is \(\max\{\max_a r_a,\sum_{a\in J} r_a\}\). Within a branch-separated polynomial integralize-then-compare architecture, it is \(2\sum_a r_a\). The coordinate case gives \(\max\{1,h\}\) and \(2L\), where \(h=|J|\). Exact conditional resampling obtains the required partially synchronized successful executions without a reciprocal-success loss. The coordinate schedule uses at most \(2L+1\) additional retry invocations in unconditional expectation. Two cases illustrate the bounds. For Cyclo-style coordinate folding, one unsynchronized coordinate has the same certified radius as same-root synchronization. For two independently extracted Esgin-style Vandermonde stars, direct comparison has degree \(\binom{k+1}{2}\) in the anchor-universal polynomial-linear model. The degree is \(k^2\) within the stated branch-separated integralize-then-compare architecture.
Last updated:  2026-09-14
SNARKs over Small Prime Fields without Extension Field Multiplication
Yuanju Wei, Kaixuan Wang, Binwu Xiang, Xinxuan Zhang, Yi Deng, Xudong Zhu, Hailong Wang, Li Lin, and Lei Wang
Sumcheck-based transparent SNARKs over small prime fields encounter a basic soundness bottleneck. When instantiated over $\mathbb{F}_p$, the round-by-round soundness error is $O(d/p)$, where $d$ is the degree parameter in the sumcheck instance. This is non-negligible for small $p$. A common remedy is to work over an extension field, which departs from native $\mathbb{F}_p$ arithmetic and requires implementing general $\mathbb{F}_{p^k}$ arithmetic, in particular multiplication. A natural alternative is to amplify soundness by parallel repetition. However, naive $k$-parallel repetition does not achieve a proportional $k$-fold increase in round-by-round soundness for multi-round sumcheck. In this work, we propose the \emph{packed sumcheck protocol}, which amplifies round-by-round soundness over $\mathbb{F}_p$ by combining repetition with folding, while avoiding extension field multiplication. The core idea is to couple $k$ independent instances within each round using random matrix challenges from the matrix ring $\mathbb{F}_p^{k \times k}$, so that every folding step mixes all $k$ coordinates. For degree-$d$ claims, we obtain round-by-round soundness error $\bigl(((2k-1)d)/p\bigr)^k$. The prover uses $O((kd^2+k^2d)N)$ base field multiplications and the verifier uses $O(k^2 d\mu)$ base field operations, with communication $O(k d\mu)$ base field elements, where $N=2^\mu$ is the size of the $\mu$-dimensional Boolean hypercube. To compile the packed sumcheck protocol into SNARKs, we introduce \emph{matrix-weighted multilinear extension (MW-MLE) commitments}, capturing the matrix-weighted linear forms induced by packed sumcheck, and instantiate them by adapting Brakedown (CRYPTO~2023) and Basefold (CRYPTO~2024). The resulting components are integrated into the HyperPlonk (EUROCRYPT~2023) framework by replacing its sumcheck and polynomial commitment modules with packed variants, obtaining transparent SNARK instantiations without extension field multiplication in the Random Oracle Model. We further apply our packed techniques to construct a TFHE-friendly SNARK; we evaluate its prover performance for a single bootstrapping, obtaining a prover time of 2.2 seconds.
Last updated:  2026-09-14
Improved Multi-Party Distributed Point Functions from Oblivious Tensor Evaluation
Kelong Cong, Emmanuela Orsini, and Erik Pohle
A multi-party distributed point function (DPF) compresses a point function instance $f_{\alpha,\beta}$, i.e., $f$ evaluates to $\beta$ at $\alpha$ and to $0$ otherwise, into short keys that are distributed to $N$ parties. Each key allows a party to locally derive an additive share of the point function evaluation. DPFs have become a widespread building block for cryptographic protocols and sometimes rely on a distributed setup. In this work, we present an $N$-party, full-threshold DPF for full-domain evaluation making black-box use of oblivious tensor evaluation. Let $L$ denote the domain size of the point function and $\lambda$ the security parameter. Instantiated with the non-interactive oblivious tensor evaluation primitive (NIOTE) by Abram et al. (STOC '25) based on learning with errors (LWE), we obtain $N$-party DPFs with (i) key-size $\mathcal{O}(N \cdot \mathsf{poly}(\lambda) \cdot \log^2 L)$ with a $\log L$-round distributed setup protocol, or (ii) similar key-size with almost $(\log \log L)$-rounds (asymptotically $\Theta(\log L)$ but for relevant values of $L$ in practice equal to $\log \log L$), or (iii) key-size $\mathcal{O}(N \cdot \mathsf{poly}(\lambda) \cdot \log L \cdot \sqrt{L})$ with $(\log \log L)$-round distributed setup (also asymptotically). Our construction improves over most of the state of the art either in terms of key-size or in the setup round complexity.
Last updated:  2026-09-14
Separating Pseudorandom Generators from Logarithmic Pseudorandom States
Mohammed Barhoush
Pseudorandom generators (PRGs) are a foundational primitive in classical cryptography, underpinning a wide range of constructions. In the quantum setting, pseudorandom quantum states (PRSs) were proposed as a potentially weaker assumption that might serve as a substitute for PRGs in cryptographic applications. Two primary size regimes of PRSs have been studied: logarithmic-size and linear-size. Interestingly, logarithmic PRSs have led to powerful cryptographic applications, such as digital signatures and quantum public-key encryption with tamper-resilient keys, that have not been realized from their linear counterparts. However, PRGs have only been black-box separated from linear PRSs, leaving open the fundamental question of whether PRGs are also separated from logarithmic PRSs. In this work, we resolve this open problem. We establish a quantum black-box separation between (quantum-evaluable) PRGs and PRSs of either size regime. Specifically, we construct a unitary quantum oracle with inverse access relative to which no black-box construction of PRG from (logarithmic or linear) PRS exists. This does not directly separate PRG from some of the applications of SPRS since these applications involve, as a first step, a non-black-box construction of a notion termed bot-PRGs. To address this, we present another unitary separation showing that PRG are also separated from bot-PRGs. Thus, we obtain separation from digital signatures and quantum public-key encryption.
Last updated:  2026-09-13
Beasley: Efficient Zero-Knowledge Proofs for Lattice-based Round-Optimal Oblivious Pseudorandom Functions
Baiyu Li, Ting-Yuan Wang, and Jiapeng Zhang
Verifiable oblivious pseudorandom functions (VOPRFs) enable a client to evaluate a pseudorandom function on a private input under a server-held key while verifying that the server evaluated the function honestly using its committed key. Existing practical VOPRFs rely mainly on assumptions that are vulnerable to quantum attacks. Prior lattice-based constructions achieving both round optimality and malicious security have remained theoretical proposals without concrete implementations, largely because proving the correct evaluation of the underlying lattice-based PRF in zero-knowledge is prohibitively expensive. We present Beasley, the first concrete prototype implementation of a round-optimal, maliciously secure, lattice-based VOPRF from standard lattice assumptions. Beasley builds upon the framework of Albrecht et al. (PKC 2021) and LeOPaRd (CRYPTO 2026), introducing two core optimizations: First, we generalize the Boneh-Lewi-Montgomery-Raghunathan (BLMR13) pseudorandom function where each step processes w input bits simultaneously; instantiated with w=4 in our implementation, this reduces evaluation depth and running time by a factor of 4 without impact on security; Second, we replace LaBRADOR-style proofs with a ring-switching sumcheck protocol and develop an efficient arithmetization of the OPRF computation. This design allows us to use a relatively large ring dimension of 512, simultaneously delivering fast ring arithmetic and compact keys with efficient exact range proofs without security-degrading slack. Benchmarked on a commodity consumer laptop using a single core with AVX2, Beasley generates the full client request and NIZK proof in 520 ms, with a server verification time of 15.3 ms, a peak RAM footprint of 113.7 MB, and a client communication size of 109 KB. The NIZK proof itself is 75.4 KB. Our results demonstrate that maliciously secure, lattice-based VOPRFs can achieve practical performance for real-world applications.
Last updated:  2026-09-13
On Limits on the Provable Consequences of Quantum Pseudorandomness
Samuel Bouaziz--Ermann, Minki Hhan, Garazi Muguruza, and Quoc-Huy Vu
There are various notions of quantum pseudorandomness, such as pseudorandom unitaries (PRUs), pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs) and quantum-computable PRGs. Unlike the different notions of classical pseudorandomness, which are known to be existentially equivalent to each other, the relations among quantum pseudorandomness have yet to be fully established. We present evidence suggesting that some forms of quantum pseudorandomness are unlikely to be constructed from the others. This indicates that quantum pseudorandomness behaves quite differently from classical pseudorandomness. Our main result is a unitary oracle separation where log-length output PRFSGs exist but quantum-computable pseudorandom generators (QPRGs) with negligible correctness error do not. This result suggests that the inverse-polynomial error in the state-of-the-art construction of QPRGs from log-length PRSGs is inherent. To achieve this, we prove a novel differential geometric \emph{barrier theorem} for the product Haar measure on quantum states which replaces the usual concentration inequalities by certifying a non-negligible ``gap'' between two large trace-separated sets. Our separation is based on an oracle that outputs Haar random quantum states for each bit string, which can be viewed as a quantum version of the random oracle model, where output strings are replaced by quantum states. Variations of this oracle can be used to study other relationships between quantum cryptographic primitives, and we use it to achieve partial separations, that highlight technical difficulties when dealing with ancillary registers, measurements, and adaptivity in the quantum setting. More precisely, we obtain separations showing limitations of: (i) deriving ancilla-free pseudorandom unitaries (PRUs) from PRFSGs, and (ii) a natural way of constructing super-log-length output PRSGs from log-length output PRFSGs. The latter partly complements the known hardness of shrinking the PRSG output lengths.
Last updated:  2026-09-13
On Succinct Obfuscation via Propositional Proofs
Abhishek Jain, Zhengzhong Jin, Surya Mathialagan, and Omer Paneth
A central line of inquiry in the study of indistinguishability obfuscation (IO) is to minimize the size of the obfuscation. Today we know how to obfuscate programs represented as Turing machines, where the size of the obfuscation grows only with the input size and not with the machine's running time. Jain and Jin [FOCS 2022] showed how to remove the dependency on the input size for functionally equivalent programs where equivalence can be proven in Cook's theory PV. In this work we investigate the limits of the pursuit of succinct obfuscation. We consider the task of obfuscating a program with a large description, most of which can be made public while some portion of the description is secret. We put forth a new notion of fully succinct IO where the size of the obfuscated program only grows with the size of the program's secret part and not with the public part or with the input size. Starting with input-succinct IO for PV-equivalent machines, which is known from super-polynomially hard IO for circuits and LWE, we construct fully succinct IO for the same class of programs. We refer to such an obfuscation as fully succinct pv-IO. Next, we show how to bootstrap our fully succinct pv-IO to achieve full IO security. Our bootstrapping theorems are based on succinct cryptographic primitives with seemingly weaker functionality: either succinct witness encryption or SNARGs for NP with unique proofs. We also require that the correctness of these primitives can be proven in theory PV. We show that these assumptions are sufficient and necessary. We demonstrate several applications of fully succinct IO and pv-IO: (i) We give the first IO construction where the size of the obfuscated program is less than twice the size of the original program for a large class of useful programs. (ii) We show how to avoid padding the program before obfuscating it—a step often necessitated by security analysis—by replacing the padding with a public random string. (iii) We give the first construction of succinct computational secret sharing for access structures represented by polynomial-size monotone circuits where the share size does not grow with the size of the access structure.
Last updated:  2026-09-13
New Imperfect High Threshold and Slice Secret Sharing Schemes
Andrej Bogdanov and Yanbo Chen
We present new constructions of (n - t + 1)-out-of-n threshold and slice secret sharing schemes for short secrets with imperfect secrecy for constant t and growing n. Our main results are 1. an ε-differentially secret, (n - t + 1)-out-of-n bit secret sharing scheme with share alphabet size Õ_t(1/ε^2). In contrast, perfect secrecy requires share alphabet size n - t + 1 (Bogdanov, Guo, and Komargodski, ToC 2020). For t > 3, the security of our scheme relies on a conjecture about factorizations of univariate polynomials in finite fields. 2. an ε-statistically secret bit secret sharing scheme for every (n-2)-out-of-n slice with share size O(log n log 1/ε). Previous constructions with comparable parameters achieved only computational security (Beimel, Farràs, Lasri, and Nir, TCC 2024). Variants of our first construction produce plain and anonymous (n-1)-out-of-n weak bit secret sharing schemes with optimal share size. We discuss the relevance of these schemes to secret sharing duality.
Last updated:  2026-09-13
Sharp Minimum-Distance Tails for BAA Codes
Majid Khabbazian
Fast randomized linear codes used in pseudorandom correlation generators and code-based proof systems require quantitative guarantees on the probability of sampling a code with insufficient distance. For chosen-block Block--Accumulate--Accumulate (BAA) codes, prior work provides finite-length upper bounds, sparse failure mechanisms, and permutation obstructions that persist under every nonzero coordinate scaling. We determine the global minimum-distance lower tail across field sizes. For a fixed-length constituent of minimum distance $d\ge2$, sufficiently small fixed $\delta>0$, and $Q=q-1$, we prove, uniformly over finite fields and constituent coefficients, \[ \PP[d_{\min}\le\floor{\delta N}] =\Theta\!\left(N^{1-d} +N^{1-\ceil{d/2}}Q^{-\floor{d/2}}\right). \] A support-dependent weighted-gap estimate controls every active-block count and every cancellation layer. It identifies linear field growth as the exact order needed for the $N^{1-d}$ law. Certified extensions reach distance $0.30$ for $[16,8,9]_q$ MDS blocks and $0.60$ for $[16,4,13]_q$ MDS blocks over all $q\ge2^{20}$; binary instances reach their stated useful thresholds. For the two MDS families, when $Q/N\to\infty$, we further prove that the known marked one-block coefficient is the leading constant of the actual failure probability. Grouping full-block gap events and bounding their dependence gives near-exact two-sided finite certificates at the published large-field benchmarks. These show that the existing numerical guarantees are essentially optimal for the unchanged ensemble. \keywords{Random linear codes \and BAA codes \and Minimum distance \and Pseudorandom correlation generators \and Sampling failure}
Last updated:  2026-09-13
Round-Optimal Subversion-Resilient UC PAKE from Malleable Trapdoor Smooth Projective Hash Functions
Behzad Abdolmaleki, Suvradip Chakraborty, Shahram Khazaei, Lorenzo Magliocco, Nahid Roustaeifar, Behzad Vahdani, and Daniele Venturi
Password-Authenticated Key Exchange (PAKE) allows two parties to establish a common high-entropy secret from a possibly low-entropy pre-shared secret such as a password. In this paper, we revisit the question of constructing PAKE protocols with subversion resilience in the framework of universal composability (UC), where the latter roughly means that UC security still holds even if one of the two parties is malicious and the honest party's code has been subverted (in an undetectable manner). The latter goal was recently achieved by Chakraborty, Magliocco, Magri and Venturi (ASIACRYPT 2024), based on sanitation of oblivious transfer protocols and dual-mode cryptosystems via cryptographic reverse firewalls (Mironov and Stephens-Davidowitz, EUROCRYPT 2015). Our contributions are as follows: - We introduce so-called malleable trapdoor smooth projective hash functions (M-TSPHF), as an enhancement of trapdoor smooth projective hash functions (Benhamouda et al., CRYPTO 2013). Our extension incorporates new properties including key malleability and element rerandomizability. - We give a generic construction of subversion-resilient UC PAKE based on M-TSPHF and other standard cryptographic primitives. As we demonstrate, our PAKE protocol can be instantiated efficiently yielding an improved round and communication complexity with respect to the previous protocol of Chakraborty et al. In particular, our PAKE protocol achieves round optimality, as it concludes in a single round.
Last updated:  2026-09-13
Nested MuSig2
Nadav Kohen
Bitcoin Improvement Proposal 327 specifies a variant of the MuSig2 multi-signature protocol that is becoming widely adopted in Bitcoin applications. This protocol enables multiple participants to collaboratively compute (BIP 340) Schnorr signatures for a single aggregate public key efficiently, while preventing external parties from distinguishing whether multiple signers were involved. It has been widely proposed that it should be secure to allow MuSig2 participant keys to themselves be "nested" MuSig2-aggregated keys. No security argument has previously been presented for this practice, though various applications have been proposed that assume the security of such an operation. In this work, we propose NestedMuSig2, a recursive variant of MuSig2 that enables a tree of nested cosigners to privately generate aggregate Schnorr signatures while maintaining all of the efficiency and security benefits of MuSig2, including non-interactive public key aggregation. Nested signers in this scheme cannot distinguish between cosigners that are using further nesting and those that are not. In particular, this means that NestedMuSig2 is compatible with all existing protocols that use MuSig2. We reduce the security of NestedMuSig2 to the AOMDL assumption in the random oracle model. Similarly, we reduce the security of a more efficient and compact variant to the AOMDL assumption in the random oracle model used in conjunction with the algebraic group model.
Last updated:  2026-09-13
Beyond DCR: HSS and PCFs from Subgroup Indistinguishability
Sebastian Hasler
We construct homomorphic secret sharing (HSS) and pseudorandom correlation functions (PCFs) in a general group-theoretic framework, with security based on the subgroup indistinguishability (SgI) assumption introduced by Brakerski and Goldwasser (Crypto 2010). Under certain instantiations of this framework, SgI corresponds to decisional composite residuosity (DCR), but other instantiations are possible as well. Hence, our work expands the set of assumptions that imply HSS and PCFs. Our constructions crucially rely on the existence of an efficient distributed discrete logarithm (DDLog) algorithm for the utilized group. We construct a new DDLog algorithm that works in general groups as long as the order $t$ of the base is smooth. In particular, our DDLog supports the prime-power case, which was previously an open problem. Moreover, we apply a divide-and-conquer optimization that significantly improves the performance from $\mathcal O(\log^2 t / \log \log t)$ group operations (Abram et al., Crypto 2022) to $\mathcal O(\log t \log \log t)$. Toward constructing PCFs, we introduce a new notion of public-coin subgroup indistinguishability (PC-SgI). We show that, in certain instantiations, SgI implies PC-SgI, so no new assumption is required. We then obtain PCFs for VOLE, OT, OLE, and degree-two correlations, all generically under PC-SgI. Our PCFs for OLE and degree-two correlations additionally rely on the sparse LPN assumption. Along the way, we discover and patch two security issues in prior work: first, an attack on decisional Diffie–Hellman (DDH) in the Joye–Libert instantiation by Abram et al. (Crypto 2022), and second, a flaw in the security proofs of optimized variants of the IKNP OT extension protocol and of many silent OT extension protocols.
Last updated:  2026-09-13
Exact Error-Compensated Pruning in Matrix Multiplication Time
Xiaoyu Li
We characterize the arithmetic complexity of reproducing a prescribed error-compensated pruning procedure: select weights for removal, set them to zero, and propagate each removal error to later columns. With its interaction factor supplied, an $m\times d$ layer with $m=\Theta(d^\alpha)$ admits a recursive execution in $O_\varepsilon(d^{\omega(\alpha,1,1)+\varepsilon}+C)$ operations, where $C$ is the decision cost. The execution preserves every corrected group snapshot and every subsequent decision, including unequal groups and stateful column policies. For every fixed row-wise $r$-of-$q$ rule, the exponent is exactly $\omega(\alpha,1,1)$; one row already has quadratic complexity. In square dimensions, matching lower bounds also hold for per-column half selection, whole-group half selection under every contiguous partition, and the reference implementation's inclusive threshold rule with its actual removal count. Under the inverse-Cholesky kernel, all these square lower bounds survive raw calibration and every prescribed nonnegative damping. The square reductions encode an arbitrary product with quadratic overhead, weights bounded by four, covariance condition number below two, and separated score cuts. Their mechanism is a source-to-target factor cancellation, with separate snapshot bounds and isolated guards enforcing the different selectors. A local coefficient-extraction argument validates the exponent comparison in the presence of comparisons and square roots. The results concern exact numerical execution in a nonuniform scalar model; raw rectangular preprocessing and the direct inverse-matrix kernel are treated separately.
Last updated:  2026-09-13
Structure-Preserving Compressing Primitives: Vector Commitments and Accumulators and Applications
Stephan Krenn, Omid Mir, and Daniel Slamanig
Compressing primitives such as accumulators and vector commitments, allow to rep- resent large data sets with some compact, ideally constant-size value. Moreover, they support operations like proving membership or non-membership with minimal, ideally also constant- size, storage and communication overhead. In recent years, these primitives have found numer- ous practical applications, with many constructions based on various hardness assumptions. So far, however, it has been elusive to construct these primitives in a strictly structure-preserving setting, i.e., in a bilinear group in a way that messages, commitments and openings are all ele- ments of the two source groups. Interestingly, backed by existing impossibility results, not even conventional commitments with such constraints are known in this setting. However, in many practical applications it would be convenient or even required to be structure-preserving, e.g., to commit or accumulate group elements. In this paper we investigate whether strictly structure-preserving compressing primitives can be realized. We close this gap by presenting the first strictly structure-preserving commitment that is shrinking (and in particular constant-size). We circumvent existing impossibility results by em- ploying a more structured message space, i.e., a variant of the Diffie-Hellman message space. Our main results are constructions of structure-preserving vector commitments as well as structure- preserving accumulators. We first discuss generic constructions and then present concrete con- structions under the Diffie-Hellman Exponent assumption. To demonstrate the usefulness of our constructions, we discuss various applications. Most notable, we present the first entirely prac- tical constant-size ring signature scheme in bilinear groups (i.e., the discrete logarithm setting). Concretely, using the popular BLS12-381 pairing-friendly curve, our ring signatures achieve a size of roughly 3 Kbits.
Last updated:  2026-09-13
NP-Hardness of Ideal Lattice Problems
Daniel E. Martin
We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\ell_2$ norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.
Last updated:  2026-09-13
Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States
Minki Hhan
Quantum computation gives rise to new pseudorandom primitives for states and unitaries, including pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs), and pseudorandom unitaries (PRUs). In this paper, we show a full unitary oracle separation between PRFSGs and PRUs. The separation holds between the strongest state notion and the weakest unitary notion: even adaptively secure, quantum-accessible PRFSGs do not imply non-adaptively secure, forward-only PRUs, even when their implementations are allowed to be non-unitary and use an arbitrary number of ancillary qubits. This reveals a fundamental distinction between pseudorandomness for quantum states and for quantum unitaries. Our main technical idea is to view a candidate PRU construction with access to state generation oracles as a map from the underlying oracle states to implemented unitaries, and to study the derivatives of this map. These derivatives are inherently low rank, and we exploit this low-rank structure to distinguish the resulting unitaries from truly random ones. We believe this differential perspective may be useful for studying other structural questions about quantum states and unitaries.
Last updated:  2026-09-13
On the Communication Complexity of Sleepy Consensus
Qiang Tang and Yuchen Ye
Sleepy consensus allows parties to join and leave execution arbitrarily, which is a fundamental requirement for large-scale distributed systems. Classic longest-chain protocols, such as Bitcoin and its variants, achieve consensus under this model but suffer from inherent long latency. In contrast, recent protocols that build upon the classic view-based BFT paradigm can achieve constant expected latency and short best-case latency under optimal resilience, but they often incur high communication cost. We observe that the high communication overhead stems from the time-shifted quorums, a technique that makes quorum certificates transferable under dynamic participation. The technique relies on extensive message forwarding to reconcile parties' inconsistent local views, and thus incurs a cubic communication cost unavoidably. In this work, we tackle the problem by proposing a novel way to transfer certificates. Building on this, we construct a Byzantine Agreement (BA) protocol secure against the state-of-the-art growing adversary model. Our BA protocol achieves optimal resilience, constant expected round complexity, and an expected communication complexity of $O(nNL+nN\kappa+nN\log N)$, where $n$ is the maximum number of awake parties throughout the execution, $N$ is the total number of eligible parties, $L$ is the input length, and $\kappa$ is the security parameter. We also present an efficient recovery mechanism for our BA, incurring only $O(N\kappa+nL)$ bits per recovering party. Then we extend our BA to an Atomic Broadcast (ABC) protocol that achieves optimal resilience, constant expected latency, and an expected amortized communication complexity of $O(nNL+nN\kappa+nN\log N)$ per input value. The recovery mechanism for our ABC incurs $O(N\kappa+n\ell L+n\ell \kappa)$ bits per recovering party, where $\ell$ is the number of views that the party has slept for. Last but not least, we establish communication lower bounds of $\Omega(N^2L)$ for sleepy BA and ABC. The result shows that our BA and ABC are communication-optimal when $L$ is sufficiently large (i.e., when $L=\Omega(\kappa+\log N)$), and highlights a fundamental limitation of communication efficiency in the sleepy model.
Last updated:  2026-09-13
THED: Threshold Dilithium from FHE
Jai Hyun Park, Alain Passelègue, and Damien Stehlé
We describe THED, a threshold version of the Dilithium signature scheme (ML-DSA), whose issued signatures are valid for the genuine Dilithium verification algorithm. The signing protocol has two rounds of communication, one of which that lends itself to preprocessing. The scheme supports arbitrary number of users and threshold parameter. The construction consists in running Dilithium's signing algorithm under Threshold Fully Homomorphic Encryption (ThFHE), except for the computation of the signing challenge that happens in clear. For signing-mask generation, SHAKE is replaced by a ring variant of the Darkmatter PRF under an additional pseudorandomness assumption. Due to the type of operations performed, we rely on the CKKS scheme for homomorphic computations. However, a number of challenges remain, for which we develop new tools. In particular, we describe a CKKS-BFV continuum that helps for modular operations in the context of other non-arithmetic operations, a hybrid-format homomorphic comparison when the input is the sum of a bit-decomposed integer and a small integer, and a modulus-thrifty homomorphic comparison of larger non-bit-decomposed integers. Furthermore, to ensure the protocol is communication efficient, we developed a new threshold decryption method for CKKS providing more compact decryption shares. Our proof-of-concept implementation of the FHE components of the signing protocol runs in under 1.3s on an RTX-5090 GPU, with 23.6KB of communication per party for the NIST level-2 Dilithium variant. In the randomized signing mode, most of the computation can be run in an offline phase without the message to be signed; the online cost then shrinks to under 0.25s. Apart from the two decryption steps, this computation is entirely public and can be delegated to a server with more powerful hardware.
Last updated:  2026-09-13
Information-Theoretic Hiding in Quantum Marginal Fibers
Jaroslav Hruby
We study information-theoretic hiding when an adversary has unrestricted quantum processing but physical access to only one region from a declared family of subsystems. Perfectly hidden classical codewords lie in one fiber of the corresponding marginal map. We organize trace-distance diameter, orthogonal zero-error packing, and exact coherent subspace hiding on this fixed-marginal set, distinguishing equality of basis-state marginals from the cross-term conditions of quantum error correction.
Last updated:  2026-09-13
zkAgent: Verifiable LLM Agent Execution via One-Shot Transcript Proofs
Lizheng Wang, Hancheng Lou, Chongrong Li, Yu Yu, and Yuncong Hu
LLM-based agents, which interleave large language model inference with external tool calls, are increasingly deployed in high-stakes settings. In real-world deployments, each model inference and provider-hosted tool execute behind the provider's API. Even when the agent loop runs on the user's device, these provider-executed steps still remain opaque to the user. This opacity creates an end-to-end integrity gap: a malicious provider may substitute the advertised model or fabricate tool observations to steer subsequent agent behavior. Existing zero-knowledge proof systems for LLMs prove only the Transformer computation of a single inference, leaving the rest of the inference pipeline, long-form autoregressive generation, and external tool interactions outside the proof. We present zkAgent, the first SNARK system for verifiable agent execution. zkAgent proves the complete inference pipeline, from token-to-embedding lookup and positional encoding to Transformer computation and decoding. It further binds each tool observation to an authenticated execution via zkTLS or zkVM subproofs, yielding a single end-to-end proof. To scale beyond per-token proving, we introduce one-shot transcript proving: by exploiting the Transformer's causal attention mask, zkAgent proves an entire multi-step agent transcript in a single forward pass, avoiding the substantial overhead incurred by one-proof-per-token generation. We make this batched proof sound with a weight-dependent quantization scheme that is both input-independent and unconditionally complete. On GPT-2 with a 512-token transcript, zkAgent achieves a $1047.4\times$ prover speedup over the state of the art (zkGPT, USENIX Security'25), amortizing to $0.30$s/token. On a real-world coding-assistant execution, zkAgent completes end-to-end proving in $93.18$s with $1.63$s verification, making verifiable agent execution practical.
Last updated:  2026-09-13
Optimal Collision Side-Channel Attacks
Cezary Glowacz and Vincent Grosso
Collision side-channel attacks are efficient attacks against cryptographic implementations, however, optimal collision side-channel attacks and how to compute them efficiently is an open question. In this paper, we show that collision side-channel attacks can be derived using the maximum likelihood principle when the distribution of the values of the leakage function is known. This allows us to exhibit the optimal collision side-channel attack and its efficient computation. Finally, we are able to compute an upper bound for the success rate of the optimal post-processing strategy, and we show that our method and the optimal strategy have success rates close to each other. Attackers can benefit from our method as we present an efficient collision side-channel attack. Evaluators can benefit from our method as we present a tight upper bound for the success rate of the optimal strategy.
Last updated:  2026-09-13
Constant-Size Issuer Hiding for BBS Credentials via Randomizable Keys
Andrea Flamini, Karla Friedrichs, and Anja Lehmann
Anonymous credentials (AC) equip users with credentials on attested attributes, which enable them to prove data-minimizing statements over their attributes. However, in standard ACs, each credential presentation reveals the credential issuer, which could be more information than intended and necessary, e.g., when merely proving age or personhood. Issuer-Hiding Anonymous Credentials (IHAC) address this limitation and hide the issuer in the presentation. That is, they only reveal that the user has a credential from an issuer within a certain trust set, referred to as the policy. Recent works by Sanders and Traore', and Katz and Sefranek show how to add issuer hiding to PS - and BBS - based credentials while keeping presentations constant-size, i.e., not scaling in the number of issuers. However, both constructions require the verifier to generate dedicated policy-key pairs, turning verification into a secret-key operation. Managing these verifier-specific keys introduces additional complexity and affects the resulting practical privacy and security guarantees. An orthogonal work by Flamini et al. avoids verifier - specific keys but at the cost of presentations that scale linearly - or logarithmically when using more involved proof systems - in the policy size, which becomes a bottleneck for scenarios with hundreds or thousands of issuers. In this work, we close this gap and propose IHBBS, the first IHAC scheme from standard BBS signatures that achieves constant-size presentations and is publicly verifiable, i.e., does not rely on any verifier-specific secret keys. At the core of our construction is a new technique to multiplicatively randomize BBS public keys and adapt the signatures accordingly, which we believe to be of independent interest.
Last updated:  2026-09-13
A Simple and Unified Approach for Proving Knowledge of Isogenies between Abelian Varieties
Jonathan Komada Eriksen, Riccardo Invernizzi, Jannik Spiessens, and Frederik Vercauteren
In this paper we introduce a simple and unified approach, based on generic proof systems, to prove knowledge of any isogeny between two principally polarized abelian varieties in any dimension, assuming that the $2^m$-torsion is accessible for sufficiently large $m$. Previous generic proof approaches were only able to prove knowledge of a smooth degree isogeny between elliptic curves, where for each small prime factor $\ell$ of the degree, bespoke constraints had to be derived, typically from (a variant of) the $\ell$-th modular polynomial. Our approach is much simpler in that it relies on proving knowledge of a $2^n$-isogeny between two principally polarized abelian varieties in any dimension. Furthermore, our approach is unified in that the constraints are essentially the same for each dimension, resulting in a simpler and easier-to-optimize algorithm. Our construction has immediate applications to proving knowledge of an isogeny of any degree between two elliptic curves, by using a higher dimensional representation. Indeed, by a result of Robert, any isogeny can be embedded in a $2^n$-isogeny by increasing the dimension, and conversely, the knowledge of a $2^n$-isogeny between products of varieties implies the knowledge of an isogeny of degree $\leq 2^n$ between a factor of the domain and codomain. Our generic proof does not disclose the degree of the secret isogeny, nor does it rely on knowing the endomorphism ring, thereby solving an open problem posed by Beullens, De Feo, Galbraith, and Petit in 2023. Two use cases are immediate. First, if one wants to prove knowledge of any isogeny between two supersingular curves over $\mathbb{F}_{p^2}$, e.g. during the generation of an elliptic curve with unknown endomorphism ring. Second, to prove knowledge of a secret isogeny coming from the class group action on oriented supersingular elliptic curves, e.g. CSIDH with curves defined over $\mathbb{F}_p$. Computing such group actions is typically done using qt-Pegasis, which naturally results in a 4-dimensional representation of the isogeny. Lastly, we propose two tailored zero-knowledge proof systems that improve proving time and proof size without loss of generality and provide the first implementation in dimension 2 and 4 by implementing both proof systems in Rust.
Last updated:  2026-09-13
The Limits of $t$-Private Share Conversion
Bar Alon
Private information retrieval (PIR) protocols allow a user to retrieve an entry from a database held by several servers without revealing any information about the index to any individual server. State-of-the-art information-theoretic PIR protocols are based on a combination of matching vectors over the ring $\mathbb{Z}_m$ and decoding polynomials (Efremenko, SICOMP 2012; Dvir and Gopi, STOC 2015; Ghasemi, Kopparty, and Sudan, STOC 2025). Decoding polynomials are sparse polynomials over a field $\mathbb{F}_q$, where $q$ is a prime power coprime to $m$, that evaluate to a nonzero value at $1$ and to $0$ on a certain set of inputs determined by $m$. The properties of decoding polynomials were abstracted by Beimel, Ishai, Kushilevitz, and Orlov (CCC 2012) through the notion of share conversions. Share conversions allow a set of parties to locally convert a secret shared under one scheme into a related secret shared under another scheme. They constructed a share conversion from $\mathbb{Z}_m$ to $\mathbb{F}_{q}$ for various values of $m$ and prime-powers $q$. More recent PIR protocols by Dvir and Gopi and by Ghasemi et al. were abstracted by Alon, Beimel, and Lasri (TCC 2025). The share conversion they considered transforms shares from the ring $\mathbb{Z}_m$ to a finite field $\mathbb{F}_q$, where $q$ is a prime-power coprime to $m$. We observe that if the initial conversion is based on a $t$-private secret-sharing scheme, then the resulting PIR protocol of Alon et al. is also $t$-private: no set of $t$ servers learns any information about the user's index. We call such share conversions $t$-private share conversions. Moreover, the resulting PIR protocol could potentially achieve communication complexity better than that of the best-known $t$-private PIR protocols, due to Woodruff and Yekhanin (CCC 2005) and Barkol, Ishai, and Weinreb (APPROX-RANDOM 2007). This raises the natural question of whether $t$-private share conversions exist. We show that there is no $t$-private share conversion from $\mathbb{Z}_m$ to $\mathbb{F}_q$ when $t\geq 2$ and $q$ is coprime to $m$. As a result, the PIR framework of Alon et al. cannot be instantiated in a way that yields a $t$-private PIR protocol. We further generalize the result to conversions whose output is in the ring $\mathbb{Z}_{m'}$.
Last updated:  2026-09-13
Lightning, Field-Agnostic Super-Efficient Polynomial Commitment Scheme
Wenjie Qu, Yanpei Guo, and Jiaheng Zhang
Polynomial commitment schemes (PCS) are a fundamental building block of modern zkSNARKs. In this paper, we propose \emph{Lightning}, a new coding-based PCS that achieves state-of-the-art prover efficiency. Our main technical contribution is a systematic code family, the \emph{Lightning code}, which can be instantiated from any base code with constant relative distance. Compared with the base code, the Lightning code significantly reduces encoding cost by trading off relative distance. At a comparably small relative distance, Lightning's $\delta=0.005$ configuration has an equivalent encoding cost $2.8\times$ lower than Brakedown-fastest at $\delta=0.0043$; at the common relative distance $\delta=0.020$, its equivalent encoding cost is $1.53\times$ lower than that of the Brakedown code. We integrate the Lightning code into the standard coding-based PCS framework of Ligero and Brakedown. When committing to $2^{28}$ coefficients at matched proof sizes, Lightning reduces commitment time from about $349$s to $256$s ($1.36\times$ faster) for $80$MB proofs, compared with Brakedown.
Last updated:  2026-09-13
An Improved Randomized AKS-class Primality Proving Algorithm
Haining Fan
We present an improved AKS condition $\binom {e \cdot |S|+ de - 1}{de - 1} \ge n^{\lceil \sqrt{d e/3} \rceil}$ in our randomized AKS algorithm, which tests $(x-s)^{n^j} \equiv x^{n^j} - s \pmod{x^e-r}$ for $1 \le j \le d$, where $s \in S \subset \mathbb Z_n$ and $d$ denotes the multiplicative order of $n$ modulo $e$. It is based on Bernstein's result but better than his condition $\binom {e \cdot |S|+ e - 1}{e - 1} > n^{\lceil \sqrt{d^2 e/3} \rceil}$ when $d>1$. This improved condition allows us to select a smaller $e$ when $d>1$: the improvement ratio is between $d$ and $d^2$ for $0 < |S| < \sqrt d$, and between $d^2$ and $d^3$ for $|S| \ge \sqrt d$. Because $d \in (\log n)^{O(1)}$, the condition $|S| \ge \sqrt{d}$ can be satisfied deliberately. As a result, we reduce both the theoretical time and space complexities by factors in the range $[d^2, d^3)$ compared with Bernstein's algorithm.
Last updated:  2026-09-12
A Low-Communication Garbled RAM from Homomorphic Secret Sharing
Chase Fickes, Jinye He, and Wei-Kai Lin
Garbled circuits are fundamental in modern cryptography and secure two- or multi-party computation. For real-world programs that are naturally expressed in the Random-Access Machine (RAM) model, garbled RAM is the RAM counterpart of garbled circuits: they avoid the cost of compiling the entire program into a circuit, with communication complexity serving as the primary efficiency metric. We study the setting in which the RAM program is public, while the input data and memory contents remain secret except for the prescribed output. We construct a garbled RAM for programs running in time $T$ over memory consisting of $N$ words of $W$ bits each, the scheme achieves \[ O(T \cdot (W + \lambda) \cdot \log N) + \mathrm{poly} (\lambda) \] bits in communication, where $\lambda$ is the security parameter. For sufficiently large word size $W\ge \lambda$ and running time $T\ge\mathrm{poly}(\lambda)$, the communication becomes $O(T W \log N)$, asymptotically matching the bandwidth of an optimal oblivious RAM. Since any secure garbled RAM must hide memory accesses as in oblivious RAMs, our construction can be viewed as compiling an oblivious RAM into a non-interactive analogue, without incurring additional asymptotic communication cost. Technically, our garbled RAM builds on the recent succinct garbled circuits of Ishai, Li, and Lin (Crypto'25) and Li, Lin, and Lu (Eurocrypt'26), which are in turn based on homomorphic secret sharing. Accordingly, we inherit their circular-power variants of the Decisional Diffie-Hellman or Ring Learning-With-Errors assumptions. We also use techniques from the recent work on garbled arithmetic RAM, called Zebra, by Gu, Ghoshal, and Shi (Eurocrypt'26). Compared to Zebra, which achieves the same $O(TW\log N)$ communication for *arithmetic* RAM programs that only perform arithmetic over large and bounded integers, our work focuses on the standard *boolean* RAM model. Compared to the best garbled RAM in the random oracle model, due to Liu, Liu, Luo, and Heath (ACM CCS'26), we remove a multiplicative factor $\lambda$ in communication.
Last updated:  2026-09-12
One More A: Sharper Tails Without Scaling
Uncategorized
Majid Khabbazian
Show abstract
Uncategorized
Repeat--accumulate--accumulate (RAA) codes have minimum distance linear in the block length with probability tending to one, both with and without random coordinate scaling. Sharp results, however, reveal a tradeoff between the two constructions. For block length \(N=rn\) and fixed repetition factor \(r\ge4\), the probability that the minimum distance is at most \(\delta N\) is \(\Theta(N^{2-r})\) for unscaled RAA and \(\Theta(N^{1-r})\) for scaled RAA, on their common proved range \(0<\delta\le1/10\). Thus scaling reduces the failure probability by a factor of order \(N\). This improvement comes at a cost: the scaled result requires \(q=\Omega(N)\) over \(\F_q\), and the encoder uses two length-\(N\) layers of coordinatewise field multiplications. In contrast, unscaled RAA works over a fixed field of characteristic greater than \(r\), and its accumulator stages use only field additions. In this work, we show that adding a third accumulator provides a substantially larger reliability gain without random scaling. For the unscaled repeat--accumulate--accumulate--accumulate ensemble \[ G_3=R\Pi_1A\Pi_2A\Pi_3A, \] where \(R\) is \(r\)-fold repetition, \(A\) is the accumulator, and the \(\Pi_i\) are independent uniform interleavers, we prove that \[ \Prb[d_{\min}(G_3)\le\delta N] =\Theta_{r,\delta}\!\left(N^{\,2-r-\ceil{r/2}}\right) \] for every fixed \(r\ge4\) and \(0<\delta\le1/10\), uniformly over all finite fields of characteristic greater than \(r\). Hence the field size need not grow with \(N\), and the encoder requires three accumulator passes but no coordinatewise field multiplications. On the common threshold range, its failure probability is smaller by a factor of order \(N^{\ceil{r/2}}\) than that of unscaled RAA and by a factor of order \(N^{\ceil{r/2}-1}\) than that of scaled RAA. For example, when \(r=4\), the respective failure probabilities have orders \(N^{-2}\), \(N^{-3}\), and \(N^{-4}\).
Last updated:  2026-09-12
Symmetric Models for Syndrome Decoding
Elisa Gorla and Simone Trebiani
This paper introduces a new polynomial model for the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. The model is based on elementary symmetric polynomials. We estimate the computational complexity of solving the corresponding polynomial system by establishing bounds on the degree of regularity and on the solving degree of the ideal associated to the model. The complexity estimate is lower than for previous polynomial models. We also provide a variant of the model whose complexity depends directly on the specific instance of the SDP and is lower than for the first model. Finally, we discuss how to apply our ap- proach to solve other variants of the SDP.
Last updated:  2026-09-12
Improvements to Lucas-sequence modular square roots and primality testing
Mike Hamburg
Lucas sequences are a helpful tool in mathematical and cryptographic calculations, providing in particular an efficient way to exponentiate in a quotient ring $R[x]/(x^2 - Px + Q)$. As with exponentiation in other finite rings and fields, we can use the periodic nature of these sequences to find roots of polynomials. Since they behave differently in the ring $\mathbb{Z}/N$ depending on whether $N$ is prime, Lucas sequences are also useful for primality testing. In this paper, we discuss improvements to Lucas-sequence algorithms for square roots and heuristic primality testing. Our first application is modular square roots. It is straightforward to take square roots modulo primes $p\equiv \{3,5,7\}$ mod 8. When $p\equiv 1$ mod 8, and especially when $p-1$ is divisible by many powers of 2, Müller's algorithm and Kim-Koo-Kwon are attractive options. Both of these use Lucas sequences. Here we show how to simplify and speed up Kim-Koo-Kwon. We also show a variant on Müller's algorithm which works even when $p\equiv 3$ mod 4, which would be useful if $p$ were secret. Our second application is heuristic primality testing. The Baillie-PSW primality test combines a strong Fermat test with a strong Lucas test. The recent Baillie-Fiori-Wagstaff variant strengthens Baillie-PSW. Here we show an improved variant, $\mathtt{SuperBFPSW}$, which is stronger than Baillie-Fiori-Wagstaff, but also faster than the original Baillie-PSW.
Last updated:  2026-09-12
Discrete Gaussian Sampling Meets BDGL Decoding: Solving the Shortest Vector Problem in $2^{0.5596n+o(n)}$ Time
Yiming Gao, Yansong Feng, and Honggang Hu
Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS) gave a $2^{n+o(n)}$ time algorithm for the Shortest Vector Problem (SVP) based on discrete Gaussian sampling (DGS), together with an honest sampler producing $2^{n/2}$ samples above the smoothing parameter in $2^{n/2+o(n)}$ time and space. Gao, Feng, and Hu (GFH) subsequently introduced DGS on random prime-index superlattices, making this sampler available at the shortest vector scale and obtaining a $2^{0.7314n+o(n)}$ time algorithm. In a different direction, the Becker--Ducas--Gama--Laarhoven (BDGL) sieve uses spherical product codes to find correlated pairs and runs in $2^{0.2925n+o(n)}$ time under the random list heuristic. We combine the random superlattice DGS framework with a single BDGL product code decoding layer. The algorithm splits the DGS output into two lists. For a fixed shortest vector $v$, the Gaussian midpoint identity turns the event $X-Y=v$ into a birthday event, while equal quotient labels certify that the reported difference belongs to the input lattice. The product code decoder locates the corresponding pair without enumerating all pairwise differences. Our analysis makes no random list assumption. For a fixed shortest vector $v$, once the retained lists contain a pair $x,y$ with $x-y=v$, the BDGL product code finds that pair with high probability. We extend the product code analysis so that this guarantee is compatible with the claimed time and space bounds. A centered quotient line gives a $2^{0.5822n+o(n)}$ time algorithm. We then replace the line through the zero residue with a random affine translate. This lets us target a rarer midpoint shell. As a result, we obtain a randomized classical algorithm for SVP that runs in $2^{0.5596n+o(n)}$ time and uses $2^{n/2+o(n)}$ space.
Last updated:  2026-09-12
Network-Agnostic VSS with Quadratic Communication in Computational Setting
Yusong Yao, Qi Feng, Cong Peng, Min Luo, and Debiao He
Verifiable secret sharing (VSS) is a core primitive in multiparty computation (MPC). Bhimrajka et al. [PKC'24, TIT'26] proposed the first computationally network-agnostic VSS and VSS-based MPC, which seamlessly accommodate both synchronous and asynchronous network models. However, their VSS requires Byzantine Agreement (BA) and incurs $O(n^5)$ bits of communication per sharing among $n$ parties, and their MPC requires honest participation from nearly all parties. We revisit the network-agnostic VSS architecture and propose a more efficient and general network-agnostic VSS structure. Our key technique is a new virtual-party strategy, which introduces more parties for reconstruction. With this technique, network-agnostic VSS is BA-free and performs as efficiently as synchronous VSS. Specifically, in terms of communication, our VSS costs $O(n^2)$ bits in the one-shot case and $O(n)$ bits in the round-by-round case with the dispute-control technique, yielding the first computationally network-agnostic VSS protocols with amortized linear communication complexity. Besides, we further address a series of subtle yet necessary hurdles in adapting existing results to network-agnostic models, including the erasure coding techniques in Reliable Broadcast (RBC), packed secret sharing techniques in VSS, and the correlated polynomial techniques in MPC.
Last updated:  2026-09-12
Towards Practical Iterative Rejection Sampling: A Compact and Efficient Signature over Module Lattices
Yifan Ming, Jipeng Zhang, Zihan Liu, Guofeng Tang, Pengfei Chen, Yutao Sun, Si Gao, Cong Zhang, and Long Chen
Lattice signatures face a strict trade-off among compactness, implementation simplicity, and reliance on standard lattice assumptions: ML-DSA-44 requires a 2420-byte signature (3732 bytes combined) and HAETAE-120 takes 1474 bytes (2466 bytes combined), while Falcon-512 achieves 555 bytes but relies on complex floating-point arithmetic. We propose SHUTTLE, a compact Fiat–Shamir signature built on a standard MLWE public-key structure with unforgeability bound to MSIS in the random oracle model. At NIST Level I, SHUTTLE achieves a signature size of 1175 bytes (and 2167 bytes combined)—a 51% reduction in signature size over ML-DSA-44 and 20% smaller than HAETAE-120 using purely integer arithmetic. SHUTTLE resolves prior compact schemes’ limitations via three core techniques: (1) replacing secret-dependent rejection in the iterative sampling loop with a deterministic transition bounded by Rényi divergence, relegating restarts solely to public bounds and encoding checks (occurring with negligible probability $\approx 2^{-30}$); (2) reformulating transition logic in the logarithmic domain into simple integer interval comparisons; and (3) employing an asymmetric stretch-and-compress mechanism to offset MLWE parameter expansion. By eliminating secret-dependent rejection from the inner loop, SHUTTLE achieves constant-time execution with fast signing (1406k cycles, about $3\times$ faster than HAETAE-120) and verification faster than ML-DSA-44.
Last updated:  2026-09-12
Proactive Secret Sharing without Erasures
Alexandru Cojocaru, Aggelos Kiayias, Yu Shen, and Petros Wallden
Proactive secret-sharing (PSS) offers security for shared secrets in a setting of a mobile adversary which, over time, may corrupt the whole shareholder set. This remarkable property is achieved by having parties proactively and in a coordinated manner refresh their shares on a regular basis, while it assumes that the adversary never manages to corrupt more than a threshold number of parties between two consecutive share refresh operations. A common assumption for achieving PSS is the ability of parties to securely erase their private state once they have performed the refresh operation. Motivated by the difficulty in the real world to ensure secure erasure, we investigate whether it is possible to achieve PSS without erasures. As in the classic model of computation it can be easily shown that PSS without erasures is impossible, we hence ask whether it is possible to achieve PSS via quantum computation, while still requiring only classical communication. We answer the question in the affirmative by utilizing one-shot signatures and post-quantum classical extractable witness encryption. In the process of developing our result, we define and construct threshold one-shot decryption and make connections to quantum money with classical communication both of which may be of independent interest. Finally, we show how, by combining post-quantum secure functional witness encryption with our PSS, it is possible for the secret to be used without explicitly being reconstructed, something that paves the way towards proactively secure threshold cryptography without erasures.
Last updated:  2026-09-12
New Asymptotic Results on Predicting Polynomial Congruential Generators
Yansong Feng, Abderrahmane Nitaj, Yanbin Pan, and Mengce Zheng
We investigate cryptanalytic attacks for predicting polynomial congruential generators (PCGs) from arbitrarily long sequences of consecutive truncated outputs. Such attacks naturally yield systems of modular polynomial equations, which can be solved using Coppersmith's method. However, deriving the corresponding success conditions by hand requires substantial combinatorial summation, which is typically both time-consuming and tedious. Existing automated Coppersmith methods assist with this computation, but they generally provide only numerical bounds for fixed systems, whereas in our setting the number of equations is itself a parameter. Inspired by the Newton-polytope framework of Feng et al.~(Crypto~2025), we express the success condition as the volume of a high-dimensional polytope and compute it symbolically as a function of the number of outputs. We improve existing asymptotic bounds for the Pollard generator and for linear congruential generators. We also obtain new attacks on quadratic congruential generators (QCGs) with partially known coefficients and on perturbed Power Generators with an unknown masking constant, matching bounds previously achieved only under stronger assumptions on the map $F(x)$.
Last updated:  2026-09-12
Bonsai: Scalable Private Payments
Patrick O'Grady, Lúcás Críostóir Meier, and Guru-Vamsi Policharla
Virtually all deployed private payment systems publish a nullifier for every transaction to prevent double spending. At a million transactions per second, the nullifier set grows by a petabyte each year. In this work, we tackle the question of sustaining massive throughput in private payments while ensuring the system can be run on commodity hardware. We construct Bonsai, an account-based private payment scheme where validators store a single commitment per account and never store any nullifiers. Instead, each user privately maintains the nullifiers of the payments it has received, and can prune older nullifiers to cold storage so that its active state remains small. An external observer only learns that an account performed some action (send/receive) but never learns the amount or counterparty of a payment. To verify proofs at this rate, we add zero-knowledge to Pari [USENIX '26] with no increase in proof size and negligible prover overhead, and use it with a batch verification strategy. Our prototype verifies over a million operations per second on an M5 MacBook Pro.
Last updated:  2026-09-11
When Module Lattice Leaks: Horizontal Fusion Attacks on ML-DSA Implementation
Yuhan Zhao, Dalin He, Wei Cheng, Yuejun Liu, Jingdian Ming, and Yongbin Zhou
The standardization of ML-DSA has shifted the cryptographic community's focus toward its practical security. While profiled attacks against its implementations are well studied with a few traces, non-profiling attacks are widely assumed to require large trace complexity. We challenge this by introducing horizontal fusion attacks, demonstrating that non-profiling, few-trace key recovery is highly practical against ML-DSA, even against masked implementations. We expose a structural vulnerability in the module lattice from a side-channel perspective. In particular, in ML-DSA's matrix-vector multiplication ($\hat{\mathbf{A}} \circ \hat{\mathbf{y}}$), the row-wise reuse of the ephemeral secret vector $\hat{\mathbf{y}}$ indicates that one single signature generation exposes $k$ (the row-wise size of $\hat{\mathbf{A}}$) leakage instances of the same secret-dependent intermediate value, each with a distinct and known coefficient of $\hat{\mathbf{A}}$. However, exploiting this in practice is highly non-trivial due to noise and/or compiler optimizations. To overcome this, we propose a variance-based weighted fusion strategy. This approach weights each operation by how far its leading candidate is separated from the runner-up candidates, and the signing relation ($\mathbf{y} = \mathbf{z} - c \cdot \mathbf{s}_1$) lets us extract the signed coefficients of the secret key. Moreover, we introduce a fast, INTT-based algebraic sieve that further increases the success rate of key recovery. Putting together, we achieve full key recovery using merely 4 traces against ML-DSA-87 (the highest security parameter set) with non-profiling correlation analysis. On the state-of-the-art first-order masked ML-DSA implementation, our attack extracts the secret key using no more than 90 traces. To the best of our knowledge, these non-profiling results establish a new record in trace complexity for both unprotected and first-order masked ML-DSA implementations, even comparable to these profiling-based attacks.
Last updated:  2026-09-11
Decentralized Multi-Authority Functional Encryption with Malicious Authorities from Standard Assumptions
Rishab Goyal and Saikumar Yadugiri
We design decentralized multi-authority functional encryption (MAFE) for $\mathsf{P/Poly}$ circuits from minimal assumptions in both the bounded-collusion and fully collusion-resistant models, i.e., from public-key encryption and from functional encryption, respectively. Prior constructions required sub-exponentially hard public-key encryption with random oracles (bounded collusion) or sub-exponentially-hard obfuscation (collusion-resistant). Under the additional assumption of SXDH or LWE, our constructions remain secure against an adversary that corrupts any $k$ of the $n$ local authorities, provided $\binom{n}{k} = \mathsf{poly}(\lambda)$, covering, for example, $k = O(1)$ and $n = \mathsf{poly}(\lambda)$ or $k = O(\log \lambda)$ and $n = O(\log \lambda)$. Complementing this, we show that any MAFE scheme that tolerates corruption of more than $\chi = O(\log \lambda)$ authorities and remains non-trivially compact (i.e., parameter sizes scale sub-linearly in $2^{\chi}$) implies indistinguishability obfuscation. Thus, our scheme is essentially optimal across a wide parameter regime. Along the way, we introduce two abstractions, MAFE with $\textit{synchronous setup}$ and $\textit{synchronous key generation} $ that provide a path to constructing multi-authority encryption schemes from their centralized counterparts, and may be useful for designing other multi-authority encryption systems.
Last updated:  2026-09-11
Large-Universe (Multi-Authority) ABE from LWE
Pratish Datta, Yannis Rouselakis, Junichi Tomida, and Nikhil Vanjani
An attribute-based encryption (ABE) scheme is "large-universe" if its attribute universe is superpolynomial and is not enumerated during setup. In the multi-authority setting, we further require that each authority can independently manage a superpolynomial set of attributes and dynamically issue an arbitrary polynomial number of secret keys per user. Although large-universe (multi-authority) ABE from pairings is well studied, explicit lattice-based constructions have remained elusive. In the centralized setting, a standard workaround is to instantiate lattice-based ABE for general circuits and encode each attribute as a bit string; however, unless one adopts non-standard lattice assumptions, this approach typically yields prohibitively large ciphertexts. In the multi-authority setting, even though lattice-based ABE for general circuits is known, this bit-encoding approach applied to those schemes does not yield a genuine large-universe construction. We close this gap by presenting the first lattice-based large-universe (multi-authority) ABE schemes under the Learning With Errors (LWE) assumption, achieving ciphertext and key sizes that are comparable to those in the pairing-based setting. Concretely, we construct: • a large-universe key-policy ABE scheme with ciphertext size $O(t)$; • a large-universe ciphertext-policy ABE scheme with ciphertext size $O(|f|)$; and • a large-universe multi-authority ABE scheme, where $t$ is the number of attributes, $|f|$ is the policy size, and the $O(\cdot)$ notation suppresses $\tilde{O}(\lambda)$ factors. All schemes support policies in disjunctive normal form (DNF) and are proved secure in the random oracle model. We further develop more efficient variants of our key-policy and ciphertext-policy ABE schemes over ideal lattices under the Ring-LWE assumption, aiming for practical performance on the order of seconds to minutes. Experimental results from our implementations confirm practical runtimes and memory consumption, providing concrete evidence that large-universe lattice-based ABE is feasible for efficient real-world deployment.
Last updated:  2026-09-11
Efficient Single-Server Stateful PIR Using Format-Preserving Encryption
Pranav Shriram Arunachalaramanan and Ling Ren
Recently, Stateful Private Information Retrieval (PIR) has emerged as a promising new paradigm of PIR. Despite significant recent progress, state-of-the-art single-server schemes in this paradigm still suffer from practical inefficiencies in communication, computation, and/or client storage. In this work, we construct a new single-server stateful PIR scheme called HarmonyPIR that achieves efficient communication, computation, and client storage. From a technical standpoint, we build on the recent work of Wang and Ren (EUROCRYPT 25) and propose a new hint organization that uses only a single random permutation. The random permutation can be instantiated using either AES or the recently standardized FF1 Format-Preserving Encryption, yielding two variants of HarmonyPIR. Our new scheme achieves up to two orders of magnitude better amortized computation and up to five times better amortized communication than state-of-the-art schemes.
Last updated:  2026-09-11
Post-Quantum Private Set Intersection for Small Sets
Junxin Liu, Mike Rosulek, and Ni Trieu
Are private set intersection (PSI) protocols ready for the post-quantum future? We focus on the PSI protocol of Rosulek \& Trieu (``RT21'', ACM CCS 2021), which is the current state-of-the-art for PSI on small sets (less than a thousand items). The RT21 protocol presents some fundamental barriers to post-quantum security. First, although it is written in terms of an arbitrary KEM, it requires certain properties of Diffie-Hellman KEM that simply are not satisfied by any post-quantum candidates. Second, even if adapted to post-quantum KEMs, it would require an ideal permutation with blocklength larger than any known viable candidate. We show how to modify the RT21 to make it compatible with post-quantum KEM candidates like ML-KEM. We also describe a direct domain-extension construction for ideal permutations, showing how to construct a huge-block ideal permutation directly from one with smaller blocklength, such as the Keccak permutation family. Along the way, we also introduce new abstractions for \emph{oblivious key-value stores} (Garimella et al., Crypto 2021) that make the analysis of these kinds of PSI protocols more modular. We implemented our protocol and evaluated its performance across different network settings and instantiations. We achieve PSI from standardized post-quantum primitives with latency as low as $0.25$ ms/item and communication as low as $1.67$ KiB/item. We find that the performance penalty for post-quantum security ranges from 1.25$\times$ to 5.92$\times$ in latency and is 16.7$\times$ in communication, depending on the instantiation.
Last updated:  2026-09-11
Zero-Knowledge Proofs for Gradient Boosted Decision Trees
Jiacheng Gao, Wenjie Qu, Yuan Zhang, Sheng Zhong, and Jiaheng Zhang
Gradient boosted decision trees (GBDTs) are widely used for tabular data in finance, healthcare, and risk ssessment. As GBDT training and inference are increasingly outsourced, clients need to verify that models are trained as claimed and predictions are consistent with those models, while providers may need to keep training data and model parameters private. This makes zero-knowledge proofs for GBDT training and inference a natural solution. Existing approaches typically compile training certification into circuits and prove their execution using generic ZKP backends, incurring high prover costs. Directly proving the underlying algebraic relations offers an alternative, but proving each relation separately incurs substantial costs for committing to and opening auxiliary witnesses. Batching is challenging because these witnesses have different shapes and sizes and are encoded over different domains. We present \textsc{Terrae}, a zero-knowledge proof system for quantized GBDT training and inference based on KZG polynomial commitments. \textsc{Terrae} avoids both proving circuit computation and proving each constraint separately by leveraging the structure of GBDT training and two new batching techniques: domain-lifting batching for low-degree algebraic constraints and interleaving batching for same-form non-native constraints. Both techniques work over differently-sized domains and reduce many constraints to a single claim without introducing extra polynomial commitments. We also design a histogram proof that proves the correctness of aggregating sample-wise updates into histograms, which may be of independent interest. Our evaluation shows that, compared with prior work CertXGB instantiated with the same KZG backend, \textsc{Terrae} achieves proof-generation speedups of $3.18$--$13.55\times$ for training and $1.96$--$4.31\times$ for inference across completed benchmark comparisons, with lower peak prover memory, at the cost of moderately larger proofs and higher verification time.
Last updated:  2026-09-11
Proving Authenticated Key Exchange via Memory-Efficient Reductions
Jiaxin Pan and Runzhi Zeng
We initiate the study of memory efficiency in proving the security of authenticated key exchange (AKE) protocols: We first revise the security model for AKE protocols in order to prove their security in a memory-efficient manner without compromising its capability of capturing usual attacks. We formally show that security in our model implies {security in} previous ones, and thus our model captures the same security as before. After that we propose a generic construction of AKE from key encapsulation mechanisms (KEMs) and digital signature schemes, motivated by the signed Diffie-Hellman protocol. Under the multi-user security of the signature scheme and (relatively weak) one-way security against plaintext checking attacks of the KEM, our generic construction is proven to be tightly secure (in terms of success probability) via memory-tight reductions in the random oracle model. This gives us the first memory-tight AKE protocol, and it largely reduces the memory consumption of proving AKE protocols. Given that most post-quantum assumptions (e.g., the Learning-With-Errors and Short-Integer-Solution assumptions) are memory-sensitive, our improvement on memory consumption holds significant value for post-quantum AKE protocols.
Last updated:  2026-09-11
Parallelized Authenticated Encryption with Tag Combiners
Christoph Dobraunig and Charlotte Lefevre
When looking at authenticated encryption schemes, we have schemes that process the input data by having serial calls to their underlying building blocks, like duplex-based constructions, and schemes that allow for parallel calls to their underlying building blocks, like the Galois Counter Mode (GCM). Naturally, one can parallelize a serial scheme by distributing the data to encrypt over different calls to the serial scheme. However, there are many different choices to be made, like how to choose the nonce for the different instances, or if and how to combine the multiple tags into a single one. In this paper, we investigate different possible choices providing proofs for their security. Interestingly, we see a huge variance in the provable properties and hence, the security in making a serial scheme parallel. Or, motivating the problem more generally, we are investigating tag combiners, where the single tags to be combined are secret to the adversary.
Last updated:  2026-09-11
Better Security Proofs for X3DH and XHMQV
Jiawei Bao, Jiaxin Pan, and Runzhi Zeng
The Signal protocol is used by billions of users daily and recognized as the gold standard for end-to-end encrypted messaging. Its initial handshake protocol X3DH uses XEdDSA to sign its semi-static key and allows parties to derive a session key asynchronously. The protocol is implemented over Curve25519, relying on the assumed 128-bit hardness for solving Discrete Logarithms (DL). Previous non-tight reductions incur a large loss in the number of sessions, and the resulting concrete security guarantees fall far below the intended 128-bit security level. This motivates the development of tight security bounds for these protocols. In this paper, we improve the security analysis of X3DH and its recent enhancement XHMQV (Fiedler et al., CRYPTO'25) by providing tight security reductions under multi-user Diffie–Hellman (DH) assumptions (Kiltz et al., CT-RSA'23) in the Random Oracle Model. Unlike prior work, our proofs are in the more realistic multi-Test setting. The variant of X3DH that we analyze hashes additional context into the session key. Although this modification is minor, it yields tight security bounds and provides a stronger justification for the use of Curve25519. In light of our results, the Signal developers plan to adopt the same modification.
Last updated:  2026-09-11
A Tight Analysis of GHOST Consistency
Peter Gaži, Zahra Motaqy, and Alexander Russell
The GHOST protocol was proposed in 2015 as an alternative to the Nakamoto consensus mechanism that underlies Bitcoin. In con- trast to the Nakamoto longest-chain rule, the GHOST rule justifies selec- tion of a chain by maximizing subtree weights rather than path lengths. This chain selection rule has been adopted by a variety of consensus protocols and is featured in the currently deployed protocol supporting Ethereum. We establish an exact characterization of the consistency region of the GHOSTprotocol,identifyingtherelationshipbetweennetworkdelay,the rate of honest block production, and the rate of adversarial block pro- duction that guarantees that the protocol reaches consensus. In contrast to the Nakamoto consensus protocol, we find that the region depends on the convention used by the protocol for tiebreaking: we establish tight results for both adversarial tiebreaking, in which ties are broken adver- sarially in order to frustrate consensus, and deterministic tiebreaking, in which ties between pairs of blocks are broken consistently throughout an execution. We provide explicit attacks for both conventions which stall consensus outside of the consistency region. Our results conclude that the consistency region of GHOST can be strictly improved by incorporating a tiebreaking mechanism; in either case, however, the final region of consistency is inferior to the region of longest-chain rule consensus. On the other hand, in the region where the GHOST protocol is secure it provides superior defense of settled blocks against periods of adversarial majority than the longest-chain rule and, in this sense, is preferable from the perspective of self-healing.
Last updated:  2026-09-11
Differential Meet-in-the-Middle Attacks on Feistel Ciphers
Bastien Michel, Dounia M'foukh, and María Naya-Plasencia
Differential meet-in-the-middle attacks, introduced by Boura et al. in 2023, propose a new way of dealing with differential distinguishers. It allows, in particular, to combine differential attacks with initial structures, that were usually used exclusively for meet-in-the-middle attacks. Several applications of this new technique have been published, but so far the results on Feistel constructions have not improved much upon previous best known attacks. In this paper, we apply them on Feistel constructions with all the improvements proposed so far, and we propose some additional new ideas to generically improve these kinds of attacks. We also propose an automatized tool for optimizing the attacks on Simon-like constructions. Our tool outputs a graphical representation of the attack that makes it very easy to verify. All this has allowed us to provide improved single-key key-recovery attacks on most of the variants of Simon, Simeck and CLEFIA-256, that increase the highest number of rounds attacked by 1 or 2 in nearly all the cases.
Last updated:  2026-09-11
Succinct Two-Round Two-Party Signing from PCFs
Lennart Braun, Geoffroy Couteau, Kelsey Melissaris, Mahshid Riahinia, and Elahe Sadeghi
We introduce new two-party threshold signature schemes with strong efficiency and security. The application of our methodology to the two most popular signatures, Schnorr and ECDSA, yields two-round, two-party, stateless and deterministic signing with 4-12 ms of computation on one core of a standard laptop, extremely low communication -- 96 B for Schnorr, and 128 B for ECDSA -- and full concurrent simulatable security. At the heart of our approach is a new pseudorandom correlation function (PCF) for vector-OLE that admits an efficient key generation protocol; we design an end-to-end maliciously-secure and highly parallelizable DKG for this PCF and, using this DKG, we obtain an estimated runtime of 44 s for the (one-time) distributed setup of Schnorr and ECDSA on one core of a standard laptop.
Last updated:  2026-09-11
Lattice-based Secret-Key Functional Encryption for Constant-Degree Polynomials
Valerio Cini, Russell W. F. Lai, Akin Ünal, and Ivy K. Y. Woo
We present a lattice-based construction of secret-key functional encryption (FE) for low-norm polynomials of any constant degree $d$, hence also for $\mathsf{NC}^{0}$ circuits. We rely on two core ingredients: 1. New trapdoor and preimage sampling algorithms for certain degree-$d$ tensor-structured matrices, used to generate functional secret keys. 2. A new $k$-LWE-style assumption where short preimages of non-zero images with respect to the above tensor-structured matrix are given as hints, under which we prove that our secret-key FE scheme is selectively secure (under unbounded collusion). To gain confidence in the new assumption, we prove that the standard LWE assumption implies the degree-$1$ case and cryptanalyse the $d > 1$ case. As a corollary, we obtain a new pathway to post-quantum secure indistinguishability obfuscation (iO), conditioned on the above new assumption, standard LWE, and the existence of polynomial-stretch pseudorandom generators in $\mathsf{NC}^{0}$. Along the way, we give a new, simple (public-key) FE scheme for linear functions with selective security under the standard LWE assumption.
Last updated:  2026-09-11
SoK: PQC PAKEs - Design, Security and Performance
Nouri Alnahawi, David Haas, Erik Mauß, and Alexander Wiesmaier
Password Authenticated Key Exchange (PAKE) establishes secure communication channels using passwords for authentication. Currently, standardized PAKEs rely on classical asymmetric cryptography. However, these PAKEs may become insecure should the expected quantum threat become a reality. Despite the growing interest in realizing quantum-safe PAKEs, they did not receive much attention from the ongoing Post-Quantum Cryptography (PQC) integration efforts. Hence, there is a significant awareness gap compared to PQC primitives subject to the official standardization processes. We provide a comprehensive overview of existing PQC PAKEs, classify their design rationales and authentication methods, and address aspects related to their security and performance. We identify PAKE designs that are still unexplored in the PQC realm and discuss the possibility of their adaptation. Thus, we offer a detailed reference for future work on PQC PAKEs.
Last updated:  2026-09-11
Statistical MPC with a Constant Communication Overhead
Ashish Choudhury, Ivan Damgård, Shravani Patil, and Arpita Patra
We study the feasibility of constant communication-overhead statistically-secure MPC tolerating malicious adversaries in the synchronous setting and guaranteed output delivery (GOD). We propose a protocol with $n = 3t + 1$ for SIMD circuits with a communication overhead of ${\cal O}(1)$ and round complexity ${\cal O}(D)$ for circuit depth $D$, where $n$ is the number of parties and $t$ is the maximum number of corruptions. Moreover, our protocol achieves GOD. This is the first MPC protocol with above characteristics. To design our protocol, we give two major contributions. Our first technical contribution is a verifiable secret sharing (VSS) protocol that achieves constant per-secret overhead via two-dimensional packing. Our second contribution is a constant-overhead degree-reduction protocol that converts a high-degree packed sharing into a lower-degree packed sharing.
Last updated:  2026-09-11
Almost Linear-Time Permutation Check
Benedikt Bünz, Jessica Chen, Zachary DeStefano, and Binyi Chen
Permutation and lookup arguments are at the core of most deployed SNARK protocols today. Most modern techniques for performing them require a grand product check. This requires either committing to large field elements (e.g. in Plonk) or using GKR (e.g. in Spartan) which has worse verifier cost and proof size. Moreover, both have a soundness error that grows linearly with the input size. We reduce permutation argument to sumcheck argument and present two permutation arguments that have $\mathsf{polylog}(n)/|\mathbb{F}|$ soundness error. BiPerm only requires the prover to perform $O(n)$ field operations on top of committing to the witness, but at the cost of limiting the choices of PCS. We show a general construction, MulPerm, which has no restriction on the PCS choice and its prover performs essentially linear field operations, $n\cdot \tilde O(\sqrt{\log(n)})$. Both permutation arguments generalize to lookups. We demonstrate how our arguments can be used to improve SNARK systems such as HyperPlonk (Eurocrypt 2023) and Spartan (Crypto 2020), and build a GKR-based protocol for proving non-uniform circuits. Further, MulPerm enables the fastest succinct argument with sublinear verification for arbitrary circuits over small fields. Plugging MulPerm into prior small field constructions overcomes the previous lack of an efficient permutation argument with sufficiently small soundness error.
Last updated:  2026-09-11
Oblivious Signaling
Mirza Kamrul Bashar Shuhan, Foteini Baldimtsi, and Giuseppe Ateniese
An anonymous messaging service has to solve a basic routing problem: a server must deliver an encrypted message to its recipient without learning who the recipient is. Broadcasting all ciphertexts hides the destination but forces every recipient to constantly scan for new messages. Oblivious Message Retrieval (OMR; CRYPTO~'22) tackles this by using fully homomorphic encryption (FHE) to let an untrusted server perform message retrieval on a recipient's behalf without learning which messages are pertinent. We introduce Oblivious Signaling, which shifts this cost from retrieval to sending. The server maintains a fixed-size encrypted inbox for each recipient. When a sender submits a message, the server applies the same homomorphic update to every inbox: the intended inbox absorbs the message, and the rest remain unchanged at the plaintext level. The update is uniform, can be parallelized across inboxes, and ties the delivery cost strictly to the size of the anonymity set rather than global traffic. Recipients retrieve by fetching and decrypting their inbox, so checking for new messages is independent of the global traffic. We formalize receiver privacy against an untrusted server, even when it colludes with other users, give a concrete construction based on fully homomorphic encryption, and analyze the resulting "digital postage'' trade-off: delivery is expensive, but checking is cheap. Our prototype identifies practical regimes in which this cost-model shift is preferable to scan-based retrieval, even with highly optimized OMR implementations. This cost model is well-suited to settings where recipients check frequently, and messages arrive sporadically, and it naturally discourages high-volume spam.
Last updated:  2026-09-11
Addition-Efficient MDS Matrices from Superconcentrators (Full Version)
Jooyoung Lee, Seungmin Park, and Mincheol Son
MDS matrices are a key structure for providing optimal diffusion in symmetric primitives. However, the theoretical analysis of their cost remains limited. This issue is particularly relevant to arithmetization-oriented permutations, where designs often either use costly MDS matrices or sacrifice the MDS property to reduce the number of constraints. This paper studies the number of fan-in-two additions needed to implement MDS matrices. We represent fan-in-two addition constraints by a directed acyclic graph and derive lower bounds on the number of additions using the established result that any such computation graph implementing an MDS matrix must be a superconcentrator. Building on size-reduction lemmas for superconcentrators, we present a recursive algorithm that improves both lower and upper bounds for $t\times t$ matrices with $t\leq 8$. As a result, we obtain explicit MDS matrices over large primes for $t=3,4,5,6,7,8$, requiring $5,8,12,16,21,26$ additions, respectively. These bounds are tight for $t\leq 6$. We also use the same superconcentrator graphs as templates for MDS matrices with $k$-bit words. For $t=5,6,7$, our matrices require fewer XORs than the state of the art for most considered parameter choices in this line of work.
Last updated:  2026-09-10
A Compact Post-quantum Strong Designated Verifier Signature Scheme from Isogenies
Farzin Renan, Wendi Gao, and Jason T. LeGrow
Strong designated verifier signatures are a variant of digital signatures in which only one party—the designated verifier—is able to verify the authenticity of a signature. We propose a new strong designated verifier signature scheme based on (abelian) cryptographic group actions.
Last updated:  2026-09-10
Criminology: Refined Techniques for Compression Side-Channel Attacks
Yuanming Song, Lenka Mareková, and Kenneth G. Paterson
It has been known for two decades that performing compression before encryption is dangerous, because it introduces a side channel leaking information about plaintexts through ciphertext lengths: the compressed plaintext length may be visible in the ciphertext length, and the amount of compression obtained is plaintext-dependent; hence an adversary can obtain some leakage about the plaintext via observation of ciphertext lengths. This issue was first pointed out by Kelsey (FSE 2002) and turned into a practical plaintext recovery attack in the form of the CRIME attack on SSL and TLS by Rizzo and Duong in 2012. A long series of variations and attacks against other systems followed. Despite the known dangers, the compress-then-encrypt paradigm is still prevalent in practice today. This may be because the compression-based side channel is susceptible to noise and may require a large number of queries to enable plaintext recovery, and so can be mitigated by either adding noise (e.g. with random padding) or limiting an adversary's interaction with the system. We demonstrate that this side channel is much more powerful than previously thought. We focus on the widely-used DEFLATE algorithm in our analysis. We present novel techniques that enable strong amplification of small length differences arising during compression. Our telescoping and chaining amplification techniques exploit the way in which DEFLATE replaces common strings by shorter back-references. Our collision-based amplification technique focusses on exploiting hash table collisions in DEFLATE implementations. This involves a deeper examination (and exploitation) of the internals of DEFLATE than in previous works. These insights result in compressed length differences growing linearly with the length of queries. Compared with length differences of a few bits or bytes in prior work, our new amplification techniques thus enable us to defeat existing noise-based countermeasures. Finally, we introduce the concept of CRIME automata, these being carefully crafted query strings that enable an attacker to exert fine control over the internal behaviour of DEFLATE and produce differences in the output lengths of the compressor according to various criteria (such as whether the DEFLATE sliding window contains a given target string). In turn, our automata are composed in a modular fashion from gadgets having different functions, including matching against target strings, performing logical operations between other gadgets, and, most importantly, amplifying differences in output lengths using the above-mentioned techniques. We provide multiple, concrete automata designs that serve different attack goals. These designs are supported by experiments and a publicly available codebase demonstrating the power, flexibility, and practical impact of our CRIME automata approach.
Last updated:  2026-09-10
Component-Dual Compression and the Exact Characteristic-Two Contribution Region of the Relaxed Non-Fano Port
Shahram Khazaei and Maghsood Parviz
Jafari and Khazaei (Journal of Cryptology, 2021) introduced a kernel-based lower-bound method for linear secret-sharing schemes by fixing one minimal qualified coalition and comparing its participant components with those arising from auxiliary minimal qualified coalitions. These comparisons form a star. We extend the same mechanism from stars to coalition-labelled trees and obtain new characteristic-two inequalities for the relaxed-line non-Fano port $\widehat N$. For this access structure, the tree method is strictly stronger than the star method, yielding facet inequalities not implied by the star inequalities. We also show that the tree method does not determine the full contribution region. To complete the analysis of $\widehat N$, we introduce component-dual compression (CDC). CDC replaces each share by the span of the components selected from minimal reconstructions and realizes the duals of these compressed spaces in a common coordinate system indexed by the original minimal coalitions. This yields the remaining lower-bound inequalities. Together with matching constructions, the star, tree, and CDC bounds determine the complete characteristic-two linear contribution region of $\widehat N$, with maximum and average linear information ratios $5/4$.
Last updated:  2026-09-10
Lower Bounds for PIR with Preprocessing from Blackbox Cryptography
Alexander Hoover, Giuseppe Persiano, and Kevin Yeo
Single-server private information retrieval (PIR) schemes are known to require linear query time. Recent works circumvent these classical lower bounds by leveraging preprocessing to answer queries in sublinear time. We prove computation lower bounds for PIR with preprocessing schemes making blackbox usage of any cryptography (such as random oracles or virtual blackbox obfuscation). If the client stores $s$ bits about an $n$-bit database, then answering $k = \Omega(s)$ queries requires either $\Omega(n/s)$ amortized online communication or $\Omega(n/s)$ amortized server cryptographic operations. This is tight, as known constructions match either bound while outperforming the other. Our lower bound is unconditional and allows arbitrary query protocols, weakened privacy, and server-side database encodings (including doubly efficient PIR) whenever the encoding is independent of the blackbox cryptography. Previous bounds were only known conditionally and for restricted classes of preprocessing, e.g., under non-encoding assumptions. Our framework also yields $\Omega(n/s)$ communication lower bounds for schemes with $o(n/s)$ server cryptographic operations, communication-determined server cryptography, or perfect privacy in the idealized model. Finally, we prove lower bounds for symmetric PIR with client preprocessing in the random oracle model and give a matching construction using only one-way functions in the online phase.
Last updated:  2026-09-10
Multi-Party Distributed Point Functions, Revisited
Elaine Shi, Tianyao Gu, Xuanye Zheng, Yue Yang, Yiping Liu, and Yucheng Fu
In this paper, we revisit the design of multi-party distributed point functions (DPFs) and make several new contributions that advance the state of the art. We begin by revisiting security amplification, a fundamental tool underlying many DPF constructions. In particular, the recent landmark work of Goel, Wang, and Wang (CRYPTO'25) critically relies on security amplification and, for a general polynomial number of parties, gives the only known construction based on one-way functions (OWFs) that achieves sublinear dependence on the input domain size. Unfortunately, due to a known gap in the proof of the security amplification theorem of Boyle et al. (CRYPTO'22), we currently still lack a fully established security amplification theorem for DPFs. We fill this gap by providing a new proof of security amplification for DPFs with tight parameters. Equipped with this security amplification theorem as a key technical tool, we develop several new techniques that asymptotically improve the communication cost of multi-party DPFs in both the honest-majority and corrupt-majority settings. Our main results are summarized below, where $N$ denotes the input domain size, $m$ denotes the number of parties, and $t$ denotes the corruption threshold: In the all-but-one-corrupt setting, we describe a new scheme based on OWFs with $\widetilde{O}_\lambda\left(N^{\frac12 + \epsilon} \cdot \sqrt{m}\right)$ share size where $\epsilon > 0$ is an arbitrarily small constant. In comparison, the best previously known OWF-based construction due to Goel et al. incurs $\widetilde{O}_\lambda\left(N^{\frac12 + \epsilon}\cdot m^3\right)$ share size. In the honest-majority setting, assuming $m > (1+\epsilon)D t$ for some integer $D \ge 2$ and arbitrarily small constant $\epsilon > 0$, we construct a new OWF-based scheme with share size $\widetilde{O}_\lambda(N^{\frac{1+\epsilon}{2D}})$, as well as an information-theoretically secure scheme with share size $\widetilde{O}(N^{1/D})$. Both constructions achieve an exponential factor improvement in their dependence on $m$ and $t$ compared to the state-of-the-art schemes of Bunn, Kushilevitz, and Ostrovsky.
Last updated:  2026-09-10
Efficient Transaction Traceability for Auditable Privacy-Preserving Ledgers
Elli Androulaki, Angelo De Caro, Kaoutar Elkhiyaoui, Rebekah Mercer, and Elina van Kempen
Privacy-preserving distributed ledgers enable transaction processing systems in which users can submit transactions without revealing their identities or transaction details. Regulated and institutional settings impose additional requirements: authorized parties must be able to efficiently trace transactions to their originators without compromising overall system privacy. Existing approaches suffer from important limitations, including restricted parallel transaction formation, high computational overhead, and overly broad auditor access to user secrets. We present a framework for efficient tracing that eliminates concurrency issues while limiting auditor access. We formalize our security requirements via an ideal functionality and propose a black-box construction based on pseudorandom functions and anonymous credentials, with two concrete instantiations: one using hash-based PRFs and zk-SNARKs, and another using algebraic PRFs and Sigma protocols. Our experimental evaluation demonstrates practicality, incurring only a few milliseconds of overhead for the added tracing capabilities.
Last updated:  2026-09-10
CAPSS: A Framework for SNARK-Friendly Post-Quantum Signatures
Thibauld Feneuil and Matthieu Rivain
In this paper, we present a general framework for constructing SNARK-friendly post-quantum signature schemes based on minimal assumptions, specifically the security of an arithmetization-oriented family of permutations. The term "SNARK-friendly" here refers to the efficiency of the signature verification process in terms of SNARK constraints, such as R1CS constraints. Within the CAPSS framework, signature schemes are designed as proofs of knowledge of a secret preimage of a one-way function, where the one-way function is derived from the chosen permutation family. To obtain compact signatures with SNARK-friendly verification, we rely on SmallWood, a recently proposed hash-based zero-knowledge argument scheme well suited for statements arising in this context. From this proof system which we tweak towards SNARK-friendliness, the CAPSS framework offers a generic transformation of any arithmetization-oriented permutation family into a SNARK-friendly post-quantum signature scheme. We provide concrete instances built on permutations such as Rescue-Prime, Poseidon, Griffin, and Anemoi. For the Anemoi family, achieving 128-bit security, our approach produces signatures of sizes ranging from 9.5 to 15.5 KB, with R1CS constraints between 24K and 35K. This represents a 4-6x reduction in signature size and a 5-8x reduction in R1CS constraints compared to Loquat (CRYPTO 2024), a SNARK-friendly post-quantum signature scheme based on the Legendre PRF. We showcase CAPSS through aggregated signatures, achieving sub-kilobyte amortized size for large batches, and anonymous credentials, enabling presentation proofs under 150 KB, thus highlighting the practicality of SNARK-friendly, symmetric-based designs for post-quantum primitives.
Last updated:  2026-09-10
New Constructions of Functional Adaptor Signatures: Broader Functions and Improved Efficiency
Nikhil Vanjani, Garrett Greiner, Sri AravindaKrishnan Thyagarajan, and Pratik Soni
Functional adaptor signatures (FAS) are a novel cryptographic primitive introduced at CCS'24 that enable privacy-preserving, fine-grained data-payment exchanges between a seller and a buyer in a trustless and atomic manner. In this setup, the seller holds sensitive data \(x\) (e.g., patient records, climate data), and the buyer specifies a function \(f\) (e.g., aggregate, sum). FAS guarantees that the buyer learns \(f(x)\) (and nothing beyond) if and only if the seller receives payment in blockchain-based tokens. Unlike generic smart contracts, FAS-powered solutions excel in privacy, efficiency, and compatibility with diverse blockchain systems. However, prior FAS constructions were limited to linear functions (where $f$ was linear in $x$), restricting their applicability to more complex and prevalent applications including data analytics and ML model evaluations. In this work, we extend the capabilities of FAS to support higher-degree functions \((\textit{deg} \geq 2)\), significantly broadening its range of applications. Our core contribution is a novel FAS design leveraging homomorphic encryption, which simultaneously achieves enhanced efficiency and compatibility for general functions. This approach diverges fundamentally from the restricted design in CCS'24 which relied on connections to functional encryption. We implement our homomorphic encryption-based FAS for functions arising in applications such as data analytics and machine learning inference. Remarkably, even for linear functions, our new design achieves an order-of-magnitude improvement in performance compared to CCS'24 constructions. Furthermore, our solutions seamlessly integrate with prominent blockchain systems, requiring only a basic signature verification script on standard transactions, thus ensuring practical deployability. As a conceptual contribution, we introduce the general paradigm of a blockchain-based functional fair exchange (FFE) protocol, rigorously define buyer and seller fairness, and show that FAS implies the general goal of FFE.
Last updated:  2026-09-10
SmallWood: Hash-Based Polynomial Commitments and Zero-Knowledge Arguments for Relatively Small Instances
Thibauld Feneuil and Matthieu Rivain
Zero-knowledge proofs (ZKPs) are a fundamental building block in cryptography, enabling powerful privacy-preserving and verifiable computations. In the post-quantum era, hash-based ZKPs have emerged as a promising direction due to their conjectured resistance to quantum attacks, along with their simplicity and efficiency. In this work, we introduce SmallWood, a hash-based polynomial commitment scheme (PCS) and zero-knowledge argument system optimized for relatively small instances. Building on the recent degree-enforcing commitment scheme (DECS) from the Threshold-Computation-in-the-Head (TCitH) framework, we refine its formalization and combine it with techniques from Brakedown. This results in a new hash-based PCS that is particularly efficient for polynomials of relatively small degree -typically up to $2^{16}$- outperforming existing approaches in this range. Leveraging this new PCS, we design a hash-based zero-knowledge argument system that outperforms the state-of-the-art in terms of proof sizes for witness sizes ranging from $2^6$ to $2^{16}$. Additionally, we present exact zero-knowledge arguments for lattice-based problems using SmallWood, demonstrating highly competitive performance: our scheme yields proof sizes under 25 KB across a wide range of lattice parameters, including Kyber and Dilithium instances.
Last updated:  2026-09-10
Azkaban: A Zero-Knowledge Abstract Analysis for Neural Networks
Sankha Das, Lucien L. K. Ng, Yibin Yang, Vladimir Kolesnikov, and Teodora Baluta
Deep neural networks (DNNs) are increasingly used in sensitive applications, where certifying properties such as adversarial robustness and fairness is crucial. Several recent works propose DNN certification systems using zero-knowledge proofs (ZKPs)— cryptographic primitives that allow verifying certificates while maintaining confidentiality of the model. While certification algorithms typically treat the DNN as a function over reals, naively translating these algorithms into finite-precision implementations can result in unsound certification due to rounding errors. In ZKPs, this unsoundness is amplified due to a larger precision loss from fixed-point arithmetic emulated using finite fields. In this work, we highlight an overlooked gap in the soundness of prior protocols. We propose AZKABAN, a system for zero-knowledge abstract interpretation-based analysis with end-to-end soundness. We introduce operators for sound interval analysis over finite-fields, including efficient ZKP-amenable algorithms for inner-products and division, while preventing privacy leaks due to non-linear activations. We implement our system which is comprehensive in terms of supporting both feed-forward and convolutional neural networks. AZKABAN improves over the state-of-the-art ZK individual fairness certification protocol by up to two orders of magnitude in end-to-end proof time. Further, it scales to much larger models than those considered in the state-of-the-art. AZKABAN also provides, to our knowledge, the first solution for ZK robustness certification.
Last updated:  2026-09-10
AIPA: Anonymous Image Provenance Authentication in Online Social Networks via Unlinkable Pseudonym Certificates and zk-SNARKs
Linsheng Yu and Yanqing Yao
Generative AI has made high-fidelity deepfakes easy to produce, and online social networks (OSNs) spread them widely across users and platforms. Publicly verifying an image's provenance, i.e., where an image came from and what edits it has undergone, can help combat deepfakes. The Coalition for Content Provenance and Authenticity (C2PA) offers an industry standard, but depends on trusted software and hardware. Through digital signatures and zero-knowledge proofs, cryptographic image authentication eliminates the reliance on trusted editors. However, deploying such schemes in OSNs faces three problems: preserving signer privacy, maintaining provenance authenticity across edits, and ensuring efficient verification. To ensure signer anonymity in image provenance, we propose an unlinkable pseudonym certificate scheme (UPCS) based on anonymous credentials, which reduces online signing and verification to ordinary digital signature operations taking only 0.017 and 0.066 ms. Building on UPCS, zk-SNARKs, and hash chains, we propose an anonymous image provenance authentication (AIPA) scheme, ensuring the authenticity of provenance and editing history of an image as it propagates across mutually untrusted editors, while preserving signer privacy. To achieve efficient verification in OSNs, we introduce VIMz-Loua, a GPU-accelerated image proof system with a dedicated JPEG-compression circuit, whose proofs remain a constant 448 B and verify in 6-12 ms across image sizes. We formally prove the security of UPCS and AIPA, and implement an end-to-end workflow in a simulated OSN environment, where the full multi-edit provenance lineage is only 40.2 KB (6.5% of the published image), and is verified in 4.28 s.
Last updated:  2026-09-10
Design and Analysis of Isogeny-Based Strong Designated Verifier Signature
Abhinav Sharma and Vikas Srivastava
Strong designated-verifier signatures provide authentication while restricting verification to a chosen verifier and protecting the signer from transferable evidence. Designing such signatures in the post-quantum setting is challenging because authentication, signer privacy, simulation, and efficiency must be achieved simultaneously. Recently, Renan proposed CSI-SDVS, a compact post-quantum strong designated-verifier signature scheme built from CSIDH-style commutative isogeny class-group actions. We show that its response design, $z_i=b_i-s_i$, breaks privacy of the signer's identity: because the PSI experiment reveals both candidate signer secret keys, an adversary can reconstruct the signing randomness and identify the actual signer with overwhelming probability. We validate the attack over 30,000 executions, obtaining 100\% signer identification in the main 128-bit experiment and for $\eta\in \{1,2,4,8\}$. In the following, we propose an isogeny-based strong designated verifier signature. We prove correctness, non-transferability, signer privacy, and strong unforgeability under Gap Parallelization in the random-oracle model. For $\eta=1$, the redesigned signature is 113 bytes compared with 49 bytes in CSI-SDVS, while signer key sizes remain unchanged.
Last updated:  2026-09-10
Balanced and Adaptively Secure Asynchronous Common Coin and Byzantine Agreement With Sub-Quadratic Communication
Hanwen Feng, Tiancheng Mai, and Qiang Tang
Distributed common randomness generation (i.e., the common coin problem) is a cornerstone of randomized distributed computing. While a long line of research has sought scalable solutions, the asynchronous setting remains a challenge. Specifically, while Blum et al. (TCC'21) achieved sub-quadratic communication complexity, their approach lacks ``balance'': certain nodes must still send $\Omega(n)$ messages, creating a scalability bottleneck. Furthermore, their solution only tolerates a $1/3 - \epsilon$ fraction of corrupted nodes, whereas the classic construction by Cachin et al. (PODC'00) tolerates up to $1/2$ under the same setup assumptions. In this work, we close these gaps by presenting the first balanced asynchronous common coin protocol with sub-quadratic communication complexity. In our construction, the communication cost of every honest node is bounded by $\widetilde{O}(\sqrt{n})$. Our protocol tolerates an adaptive adversary corrupting up to $(1/2 - \epsilon)n$ nodes. Beyond these asymptotic improvements, our solution avoids the heavy cryptographic machinery (such as fully homomorphic encryption) required by Blum et al. and terminates in just two deterministic rounds, compared to the dozens of expected rounds in prior work. At the heart of our construction are explicit and efficient sampler constructions. These samplers partition a population with an honest majority of at least $(1/2+\epsilon)n$ nodes into $O(\sqrt{n})$ communities, ensuring that a majority of these communities maintain a ``forever-honest'' majority. By leveraging how communities are allocated, we design mechanisms that allow each community to collectively emulate a single ``virtual node'' in Cachin et al.'s protocol. Reducing the number of participants from $n$ physical nodes to $O(\sqrt{n})$ virtual nodes drives the total communication complexity to a sub-quadratic level. Finally, we extend our methodology to Asynchronous Binary Byzantine Agreement (ABA), yielding the first balanced ABA protocol with sub-quadratic communication complexity that tolerates up to $(1/3 - \epsilon)n$ adaptive corruptions.
Last updated:  2026-09-10
Lattice-based Threshold Traitor Tracing with Public Traceability
Sébastien Canard, Nathan Papon, and Duong Hieu Phan
Since the introduction of Threshold Traitor Tracing by Boneh, Partap and Rotem at CRYPTO '24, several works have extended the functionalities within the framework or improved the parameters. However, most of the existing solution fall short in providing post quantum security guarantees. The only lattice-based construction, due to Das et al. from EUROCRYPT '26, achieves post-quantum security but is limited to private tracing: a dedicated tracing authority holds a secret tracing key. In a threshold system, where the fundamental goal is to distribute trust, such a single point of failure is undesirable. In this work, we construct the first threshold traitor tracing scheme that simultaneously achieves post-quantum security and public traceability, where anyone can trace a pirate decoder without any secret tracing key. Our core building block is a Q-Partite Threshold Public Key Encryption (QTPKE) scheme, which is known to imply threshold traitor tracing when combined with a robust IPP code: we build QTPKE from plain Learning With Errors (LWE) using a key-shifting mechanism on top of Regev's encryption scheme thresholdised via {0,1}-Linear Secret Sharing. We finally prove the security of our scheme in the standard model under standard lattice assumptions.
Last updated:  2026-09-10
Pseudo-Oil Subspaces and the Geometry of Underdetermined MQ Problems
Massimo Ostuzzi
The concrete security of multivariate post-quantum signature schemes is coming under increasing scrutiny as the NIST standardisation process for additional signatures approaches its final stages. Among the leading candidates, the security of MAYO and QR-UOV relies on the hardness of the underdetermined multivariate quadratic (MQ) problem. This work revisits Hashimoto's algorithm for solving underdetermined systems of MQ equations, reinterpreting it as a computation of a pseudo-oil subspace. In light of this geometric point of view, we design a new algorithm that, by computing richer pseudo-oil structures, distributes algebraic work across more than two Gröbner Basis steps, subdividing the initial MQ problem into multiple subproblems that can be solved separately, while linearising multiple equations. Optimising a set of discrete parameters, we select the best trade-off between algebraic solving and combinatorial search. Concretely, our approach lowers the cost of the direct attack against Security Level I parameter sets of MAYO and QR-UOV by 7 and 8 bits, respectively.
Last updated:  2026-09-10
LFSRs and Boolean Masking: An In-depth Security Analysis
Anna Guinet, Jan Schoone, Niklas Höher, Dina Hesse, and Tim Güneysu
Masking is a widely adopted countermeasure to protect cryptographic implementations from side-channel attacks. Subsequent research has focused on designing masking schemes and formally proving their security, notably through the development of automated tools, within models abstracting the reality of a sidechannel analysis. These designs rely on an external source of randomness; however, there is currently no consensus on the choice of (pseudo-)random number generators for masking. To the best of our knowledge, existing formal proofs for masking security do not consider particular choices of random number generators, but rather assume that they yield uniformly distributed and independent random variables. In that context, we introduce the first verification framework that jointly analyzes a pseudorandom number generator— specifically, but not limited to, a linear feedback shift register—and a masking scheme, in the d-probing model. Our framework relies on the Walsh-Hadamard transform by drawing on techniques from linear cryptanalysis, which we extend to the robust probing model. We demonstrate our method on 4-bit and 8-bit S-boxes, provide a detailed analysis of the formal verification outcomes, and corroborate the findings with practical evaluations on an FPGA.
Last updated:  2026-09-10
Testing Security Equivalence in the Random Probing Model
Anna Guinet, Carina Graw, Lukas Koletzko, Jan Richter-Brockmann, Holger Dette, and Tim Güneysu
The random probing model is a theoretical model that abstracts the physical leakage of an embedded device running a cryptographic scheme with more realistic assumptions compared to the threshold probing model. It assumes that the wires of the target device leak their assigned values with probability $p$, and the said values may reveal information about secret data, which could lead to a security violation. From that, we can compute the probability $\epsilon$ that a side-channel adversary may learn secret data from any random combination of wires as a function of the number of wire combinations that breaches security with rate $p$. This model is used to evaluate the security of masked cryptographic implementations, or simply named circuits; and the research community has been focusing so far on approximating or estimating the probability $\epsilon$ for one circuit. Yet, no proposition has been made to quickly compare the probability $\epsilon$ of different circuits, e.g., a circuit and its optimized version. In this context, we present two statistical tests to make decisions about the level of security in the random probing model: the equivalence test compares the security of two circuits in terms of $\epsilon$'s and the superiority test decides whether the undetermined $\epsilon$ of one circuit falls below a security threshold $\epsilon_0$, both with quantified uncertainty about the computations of the probabilities $\epsilon$'s. The validity of these tests is proven mathematically sound and verified via empirical studies on small masked S-boxes.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.