## In this issue
1. [2024/758] Admissible Parameters for the Crossbred Algorithm ...
2. [2025/253] Adaptively Secure IBE from Lattices with ...
3. [2025/885] Fast Fuzzy PSI from Symmetric-Key Techniques
4. [2025/887] Adaptively Secure Blockchain-Aided Decentralized ...
5. [2025/892] Practical cryptanalysis of pseudorandom correlation ...
6. [2025/893] MacaKey: Full-State Keyed Sponge Meets the ...
7. [2025/894] Achieving "beyond CCA1" security for linearly ...
8. [2025/898] A New Approach for LPN-based Pseudorandom ...
9. [2025/899] Improved Noise Bound in BFV Homomorphic Encryption ...
10. [2025/900] Exclusive Ownership of Fiat-Shamir Signatures: ML- ...
11. [2025/901] A Generic Framework for Practical Lattice-Based ...
12. [2025/902] On the Fiat–Shamir Security of Succinct Arguments ...
13. [2025/903] Rock and a Hard Place: Attack Hardness in Neural ...
14. [2025/904] The Security of ML-DSA against Fault-Injection Attacks
15. [2025/905] Authenticated Key Exchange Protocol with Remote ...
16. [2025/906] Covert Attacks on Machine Learning Training in ...
17. [2025/907] New Framework for Structure-Aware PSI From ...
18. [2025/908] SubLogarithmic Linear Time SNARKs from Compressed ...
19. [2025/909] Energy Consumption Framework and Analysis of Post- ...
20. [2025/910] Robust Threshold ECDSA with Online-Friendly Design ...
21. [2025/911] Fuzzy Private Set Intersection from VOLE
22. [2025/912] Enforcing arbitrary constraints on Bitcoin transactions
23. [2025/913] Hidden Number Problems in Fiat-Shamir based Post- ...
24. [2025/914] Tweakable Permutation-based Luby-Rackoff Constructions
25. [2025/915] Improved differential cryptanalysis of SPEEDY
26. [2025/916] Automated Verification of Consistency in Zero- ...
27. [2025/917] Jagged Polynomial Commitments (or: How to Stack ...
28. [2025/918] The Accidental Computer: Polynomial Commitments ...
29. [2025/919] Rep3 Reloaded: On the Cost of Function-Dependent ...
30. [2025/920] SQIsign2D$^2$: New SQIsign2D Variant by Leveraging ...
31. [2025/921] Zero-knowledge Authenticator for Blockchain: ...
32. [2025/922] $\mathsf{HyperWolf}$: Efficient Polynomial ...
33. [2025/923] SPECK: Signatures from Permutation Equivalence of ...
34. [2025/924] Card-Based Protocol Counting Connected Components ...
35. [2025/925] SCMAC and LOL2.0: An AEAD Design Framework and A ...
36. [2025/926] Polocolo: A ZK-Friendly Hash Function Based on ...
37. [2025/927] Enhancing Meme Token Market Transparency: A Multi- ...
38. [2025/928] HAWK: Having Automorphisms Weakens Key
39. [2025/929] The DROP Protocol: Dispute Resolution via ...
40. [2025/930] SEEC: Memory Safety Meets Efficiency in Secure Two- ...
41. [2025/931] Multivalued Broadcast with Optimal Length
42. [2025/932] Integral cryptanalysis in characteristic $p$
43. [2025/933] Fast elliptic curve scalar multiplications in ...
44. [2025/934] Diving Deep Into UC: Uncovering and Resolving ...
45. [2025/935] Side-channel safe conditional moves and swaps
46. [2025/936] Justvengers: Batched VOLE ZK Disjunctions in ...
47. [2025/937] Attacking Poseidon via Graeffe-Based Root-Finding ...
48. [2025/938] PSYLOCKE: Provably Secure Logic Locking with ...
49. [2025/939] On the security of one certificateless aggregate ...
50. [2025/940] Special Genera of Hermitian Lattices and ...
51. [2025/941] Proof of Exponentiation: Enhanced Prover Efficiency ...
52. [2025/942] On the (in)security of Proofs-of-Space based ...
53. [2025/943] On the Adaptive Security of Key-Unique Threshold ...
54. [2025/944] Succinct Witness Encryption for Batch Languages and ...
## 2024/758
* Title: Admissible Parameters for the Crossbred Algorithm and Semi-regular Sequences over Finite Fields
* Authors: John Baena, Daniel Cabarcas, Sharwan K. Tiwari, Javier Verbel, Luis Villota
* [Permalink](
https://eprint.iacr.org/2024/758)
* [Download](
https://eprint.iacr.org/2024/758.pdf)
### Abstract
Multivariate public key cryptography (MPKC) is one of the most promising alternatives to build quantum-resistant signature schemes, as evidenced in NIST's call for additional post-quantum signature schemes. The main assumption in MPKC is the hardness of the Multivariate Quadratic (MQ) problem, which seeks for a common root to a system of quadratic polynomials over a finite field. Although the Crossbred algorithm is among the most efficient algorithm to solve MQ over small fields, its complexity analysis stands on shaky ground. In particular, it is not clear for what parameters it works and under what assumptions.
In this work, we provide a rigorous analysis of the Crossbred algorithm over any finite field. We provide a complete explanation of the series of admissible parameters proposed in previous literature and explicitly state the regularity assumptions required for its validity. Moreover, we show that the series does not tell the whole story, hence we propose an additional condition for Crossbred to work. Additionally, we define and characterize a notion of regularity for systems over a small field, which is one of the main building blocks in the series of admissible parameters.
## 2025/253
* Title: Adaptively Secure IBE from Lattices with Asymptotically Better Efficiency
* Authors: Weidan Ji, Zhedong Wang, Lin Lyu, Dawu Gu
* [Permalink](
https://eprint.iacr.org/2025/253)
* [Download](
https://eprint.iacr.org/2025/253.pdf)
### Abstract
Current adaptively secure identity-based encryption (IBE) constructions from lattices are unable to achieve a good balance among the master public key size, secret key size, modulus and reduction loss. All existing lattice-based IBE schemes share a common restriction: the modulus is quadratic in the trapdoor norm.
In this work, we remove this restriction and present a new adaptively secure IBE scheme from lattices in the standard model, which improves the state-of-the-art construction proposed by Abla et al. (TCC 2021) and achieves asymptotically better efficiency. More precisely, we achieve the asymptotically minimal number of public vectors among all the existing schemes, along with a significantly smaller modulus compared to the scheme by Abla et al. (TCC 2021). Furthermore, our scheme enjoys the smallest Gaussian width of the secret key among all existing schemes and has the same tightness as Abla et al.'s scheme.
We propose a novel cross-multiplication design for our IBE scheme, along with several novel tools and techniques, including: (a) a homomorphic computation algorithm that outputs BGG+-style encoding with two distinct-norm trapdoors; (b) a sampling algorithm with hybrid Gaussian outputs; and (c) a partial rerandomization algorithm. These new tools and techniques are general and could find rich applications in lattice-based cryptography.
## 2025/885
* Title: Fast Fuzzy PSI from Symmetric-Key Techniques
* Authors: Cong Zhang, Yu Chen, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Anyu Wang, Xiaoyun Wang
* [Permalink](
https://eprint.iacr.org/2025/885)
* [Download](
https://eprint.iacr.org/2025/885.pdf)
### Abstract
Private set intersection (PSI) enables a sender holding a set $Q$ and a receiver holding a set $W$ to securely compute the intersection $Q\cap W$. Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q\in Q$ for which there exists $w\in W$ such that $\dist(q, w) \leq \delta$ with respect to some distance metric. Recently, Gao et al. (ASIACRYPT 2024) proposed the first FPSI protocols for $L_\infty$ and $L_{p\in[1,\infty)}$ distance with linear complexity. They summarized their FPSI construction into two steps: fuzzy mapping and fuzzy matching. However, their realizations of the two steps heavily rely on public key operations, namely the DH-key exchange and additively homomorphic encryption, resulting in low efficiency.
In this work, we propose new FPSI protocols for $L_\infty$ and $L_{p\in[1,\infty)}$ distances, primarily leveraging symmetric-key primitives.
We revisit the definition of fuzzy mapping and rigorously redefine it as a cryptographic scheme. We further introduce consistency for fuzzy mapping scheme, which could simplify the fuzzy matching step into plain PSI.
We then demonstrate how to execute fuzzy mapping step satisfying consistency. We also propose several new technologies to completely avoid the extensive use of computationally expensive public-key operations burden inherent in existing solutions.
We implement our FPSI protocols and compare them with the state-of-the-art FPSI protocols. Experiments show that our protocols perform better than state-of-the-art under all the parameters we tested. Specifically, our protocols achieve a $2.2-83.9 \times $ speedup in running time and $1.5-11.5 \times$ shrinking in communication cost, depending on set sizes, dimension and distance threshold.
## 2025/887
* Title: Adaptively Secure Blockchain-Aided Decentralized Storage Networks: Formalization and Generic Construction
* Authors: Xiangyu Su, Yuma Tamagawa, Mario Larangeira, Keisuke Tanaka
* [Permalink](
https://eprint.iacr.org/2025/887)
* [Download](
https://eprint.iacr.org/2025/887.pdf)
### Abstract
This work revisits the current Decentralized Storage Network (DSN) definition to propose a novel general construction based on a UTxO based ledger. To the best of our knowledge, this is the first adaptively secure UTxO blockchain-aided DSN. More concretely, we revisit the currently existing designs to thoroughly formalize the DSN definition and its security. Moreover we present a general construction, which a client delegates data to a DSN that keeps custody of it during a jointly agreed period. Our newly proposed approach, leveraged by the Extended UTxO (EUTxO) Model, neatly allows the storage network to offer automatic verifiability, i.e., without any interaction of the data owner, via proofs published in the blockchain. In summary, this work presents a redesign of the DSN with the aid of a EUTxO based blockchain, by (1) putting forth a formal and rigorous description of a blockchain-aided DSN protocol, (2) offering a thorough description of a practical EUTxO based DSN, and (3) detailing a security analysis showing that our protocol is adaptively secure by providing (rational) security guarantees.
## 2025/892
* Title: Practical cryptanalysis of pseudorandom correlation generators based on quasi-Abelian syndrome decoding
* Authors: Charles Bouillaguet, Claire Delaplace, Mickaël Hamdad, Damien Vergnaud
* [Permalink](
https://eprint.iacr.org/2025/892)
* [Download](
https://eprint.iacr.org/2025/892.pdf)
### Abstract
Quasi-Abelian Syndrome Decoding (QA-SD) is a recently introduced generalization of Ring-LPN that uses multivariate polynomials rings. As opposed to Ring-LPN, it enables the use of small finite field such as GF(3) and GF(4). It was introduced by Bombar et al (Crypto 2023) in order to obtain pseudorandom correlation generators for Beaver triples over small fields. This theoretical work was turned into a concrete and efficient protocol called F4OLEage by Bombar et al. (Asiacrypt 2024) that allows several parties to generate Beaver triples over GF(2).
We propose efficient algorithms to solve the decoding problem underlying the QA-SD assumption. We observe that it reduce to a sparse multivariate polynomial interpolation problem over a small finite field where the adversary only has access to random evaluation points, a blind spot in the otherwise rich landscape of sparse multivariate interpolation. We develop new algorithms for this problem: using simple techniques we interpolate polynomials with up to two monomials. By sending the problem to the field of complex numbers and using convex optimization techniques inspired by the field of “compressed sensing”, we can interpolate polynomials with more terms.
This enables us to break in practice parameters proposed by Bombar et al. at Crypto’23 and Asiacrypt’24 as well as Li et al. at Eurocrypt’25 (IACR flagship conferences Grand Slam). In the case of the F4OLEage protocol, our implementation recovers all the secrets in a few hours with probability 60%. This not only invalidates the security proofs, but it yields real-life privacy attacks against multiparty protocols using the Beaver triples generated by the broken pseudorandom correlation generators.
## 2025/893
* Title: MacaKey: Full-State Keyed Sponge Meets the Summation-Truncation Hybrid
* Authors: Charlotte Lefevre, Mario Marhuenda Beltrán
* [Permalink](
https://eprint.iacr.org/2025/893)
* [Download](
https://eprint.iacr.org/2025/893.pdf)
### Abstract
The keyed sponge construction has benefited from various efficiency advancements over time, most notably leading to the possibility to absorb over the entire state, as in the full-state keyed sponge. However, squeezing has always remained limited to blocks smaller than the permutation size, as security is determined by the capacity c, the size of the non-squeezed state. In this work, we present Macakey, an improved version of the full-state keyed sponge that not only absorbs over the entire state but also squeezes over the entire state. The scheme combines ideas of the full-state keyed sponge with those of the summation-truncation hybrid of Gunsing and Mennink. We demonstrate that, with no sacrifice in generic security and with only using c bits of extra storage, Macakey can significantly boost performance, particularly in scenarios requiring large amounts of output. For example, using the 320-bit Ascon permutation with a 256-bit capacity, Macakey outputs five times as many bits as the full-state keyed sponge.
## 2025/894
* Title: Achieving "beyond CCA1" security for linearly homomorphic encryption, without SNARKs?
* Authors: Marina Checri, Pierre-Emmanuel Clet, Marc Renard, Renaud Sirdey
* [Permalink](
https://eprint.iacr.org/2025/894)
* [Download](
https://eprint.iacr.org/2025/894.pdf)
### Abstract
In the wake of Manulis and Nguyen's Eurocrypt'24 paper, new CCA security notions, vCCA and vCCAD, and associated construction blueprints have been proposed to leverage either CPA or CPAD secure FHE beyond the CCA1 security barrier. These two notions are the strongest CCA security notions so far achievable, respectively, by correct and approximate homomorphic schemes. However, the only known construction strategies intimately require advanced SNARK machinery, undermining their practicality. In this context, this paper is an attempt to achieve these advanced CCA security notions in the restricted case of linearly homomorphic encryption, without resorting to SNARKs. To do so, we investigate the relationship between the Linear-Only Homomorphism (LOH) assumption, an assumption that has been used for more than a decade at the core of several proof-of-knowledge constructions, and these two recent security notions (vCCA and vCCAD). On the bright side, when working under the correctness assumption, we establish that the LOH property is sufficient to achieve vCCA security in both the private and public key settings. In the public key setting, we further show that a surprisingly simple and previously known Paillier-based construction also achieves this level of security, at only twice the cost of the baseline scheme. We then turn our attention to LWE-based schemes for which the Pandora box of decryption errors opens up. In the private key setting, we are able to achieve CPAD and vCCAD security but only in a fairly restrictive non-adaptive setting, in which vCCAD collapses onto a weak relaxation of CCA1. Finally, we eventually achieve adaptive vCCAD security provided that the number of ciphertexts given to the adversary is suitably restricted. While bridging the gap towards credible practicality requires further work, this is a first step towards obtaining linear homomorphic schemes achieving these recent CCA security notions by means only of relatively lightweight machinery.
## 2025/898
* Title: A New Approach for LPN-based Pseudorandom Functions: Low-Depth and Key-Homomorphic
* Authors: Youlong Ding, Aayush Jain, Ilan Komargodski
* [Permalink](
https://eprint.iacr.org/2025/898)
* [Download](
https://eprint.iacr.org/2025/898.pdf)
### Abstract
We give new constructions of pseudorandom functions (PRFs) computable in $\mathsf{NC}^1$ from (variants of the) Learning Parity with Noise (LPN) assumption. Prior to our work, the only $\mathsf{NC}^1$-computable PRF from LPN-style assumptions was due to Boyle et al. (FOCS 2020) who constructed a weak PRF from a new heuristic variant of LPN called variable-density LPN. We give the following three results:
(1) A weak PRF computable in $\mathsf{NC}^1$ from standard LPN.
(2) A (strong) encoded-input PRF (EI-PRF) computable in $\mathsf{NC}^1$ from sparse LPN. An EI-PRF is a PRF whose input domain is restricted to an efficiently sampleable and recognizable set. The input encoding can be computed in $\mathsf{NC}^{1+\epsilon}$ for any constant $\epsilon > 0$, implying a strong PRF computable in $\mathsf{NC}^{1+\epsilon}$.
(3) A (strong) PRF computable in $\mathsf{NC}^1$ from a (new, heuristic) seeded LPN assumption. In our assumption, columns of the public LPN matrix are generated by an $n$-wise independent distribution. Supporting evidence for the security of the assumption is given by showing resilience to linear tests.
As a bonus, all of our PRF constructions are key-homomorphic, an algebraic property that is useful in many symmetric-cryptography applications. No previously-known LPN-based PRFs are key-homomorphic, even if we completely ignore depth-efficiency. In fact, our constructions support key homomorphism for linear functions (and not only additive), a property that no previously-known PRF satisfies, including ones from LWE.
Additionally, all of our PRF constructions nicely fit into the substitution-permutation network (SPN) design framework used in modern block ciphers (e..g. AES). No prior PRF construction that has a reduction to a standard cryptographic assumptions (let alone LPN) has an SPN-like structure.
Technically, all of our constructions leverage a new recursive derandomization technique for LPN instances, which allows us to generate LPN error terms deterministically. This technique is inspired by a related idea from the LWE literature (Kim, EUROCRYPT 2020) for which devising an LPN analogue has been an outstanding open problem.
## 2025/899
* Title: Improved Noise Bound in BFV Homomorphic Encryption and Its Application to Multiplication
* Authors: Akshit Aggarwal, Yang Li, Srinibas Swain
* [Permalink](
https://eprint.iacr.org/2025/899)
* [Download](
https://eprint.iacr.org/2025/899.pdf)
### Abstract
Fully Homomorphic Encryption (FHE) enables computations on encrypted data without requiring decryption. However, each computation increases the noise level, which can eventually cause decryption failures once a certain threshold is reached. In particular, homomorphic multiplication significantly amplifies noise in the ciphertext. In this work, we revisit Ring-learning-With-Error (RLWE) based encryption proposed by Fan et al. and present an optimized noise growth approach by swapping the sample space for secret key and error distribution. Thereafter, we revisit BFV homomorphic multiplication proposed by Kim et al. (ASIACRYPT'21) and present an optimized noise bound. Later, we empirically check the hardness of proposed scheme using lattice estimator. Our analysis demonstrates that the proposed method achieves more than 128-bit security and achieves a lower noise bound than existing techniques.
## 2025/900
* Title: Exclusive Ownership of Fiat-Shamir Signatures: ML-DSA, SQIsign, LESS, and More
* Authors: Michael Meyer, Patrick Struck, Maximiliane Weishäupl
* [Permalink](
https://eprint.iacr.org/2025/900)
* [Download](
https://eprint.iacr.org/2025/900.pdf)
### Abstract
Exclusive ownership (EO) security is a feature of signature schemes that prevents adversaries from "stealing" an honestly generated signature by finding a new public key which verifies said signature. It is one of the beyond unforgeability features (BUFF) which were declared to be desirable features by NIST.. The BUFF transform allows to generically achieve exclusive ownership (and other properties) at the cost of an increased signature size. In this work, we study the EO security of (different variants of) Fiat-Shamir signatures. As our main result, we show that the commonly used variant of Fiat-Shamir signatures (where signatures consist of challenge-response tuples) with λ-bit challenges, can achieve about λ-bit EO security through its implicit usage of the BUFF transform—this presents a significant improvement to existing results that only provide λ/2-bit of EO security. This benefit of our result comes without an increase in signature size. For other variants of Fiat-Shamir signatures, we show worse bounds, which nevertheless improve upon existing results. Finally, we apply our results to several signature schemes: SQIsign and LESS (both round-2 NIST candidates); ML-DSA (NIST standard); CSI-FiSh; and Schnorr signatures. This shows that all these schemes achieve significantly better bounds regarding their EO security compared to existing results.
## 2025/901
* Title: A Generic Framework for Practical Lattice-Based Non-interactive Publicly Verifiable Secret Sharing
* Authors: Behzad Abdolmaleki, Mohammad Foroutani, Shahram Khazaei, Sajjad Nasirzadeh
* [Permalink](
https://eprint.iacr.org/2025/901)
* [Download](
https://eprint.iacr.org/2025/901.pdf)
### Abstract
Non-interactive publicly verifiable secret sharing (PVSS) schemes enable the decentralized (re-)sharing of secrets in adversarial environments, allowing anyone to verify the correctness of distributed shares. Such schemes are essential for large-scale decentralized applications, including committee-based systems that require both transparency and robustness. However, existing PVSS schemes rely on group-based cryptography, resulting them vulnerable to quantum attacks and limiting their suitability for post-quantum applications.
In this work, we propose the first practical, fully lattice-based, non-interactive PVSS scheme, grounded on standard lattice assumptions for post-quantum security. At the heart of our design is a generic framework that transforms vector commitments and linear encryption schemes into efficient PVSS protocols.. We enhance vector commitments by incorporating functional hiding and proof of smallness, ensuring that encrypted shares are both verifiable and privacy-preserving. Our construction introduces two tailored lattice-based encryption schemes, each supporting efficient proofs of decryption correctness. This framework provides strong verifiability guarantees while maintaining low proof sizes and computational efficiency, making it suitable for systems with large numbers of participants.
## 2025/902
* Title: On the Fiat–Shamir Security of Succinct Arguments from Functional Commitments
* Authors: Alessandro Chiesa, Ziyi Guan, Christian Knabenhans, Zihan Yu
* [Permalink](
https://eprint.iacr.org/2025/902)
* [Download](
https://eprint.iacr.org/2025/902.pdf)
### Abstract
We study the security of a popular paradigm for constructing SNARGs, closing a key security gap left open by prior work. The paradigm consists of two steps: first, construct a public-coin succinct interactive argument by combining a functional interactive oracle proof (FIOP) and a functional commitment scheme (FC scheme); second, apply the Fiat–Shamir transformation in the random oracle model. Prior work did not consider this generalized setting nor prove the security of this second step (even in special cases).
We prove that the succinct argument obtained in the first step satisfies state-restoration security, thereby ensuring that the second step does in fact yield a succinct non-interactive argument. This is provided the FIOP satisfies state-restoration security and the FC scheme satisfies a natural state-restoration variant of function binding (a generalization of position binding for vector commitment schemes).
Moreover, we prove that notable FC schemes satisfy state-restoration function binding, allowing us to establish, via our main result, the security of several SNARGs of interest (in the random oracle model). This includes a security proof of Plonk, in the ROM, based on ARSDH (a falsifiable assumption).
## 2025/903
* Title: Rock and a Hard Place: Attack Hardness in Neural Network-assisted Side Channel Analysis
* Authors: Seyedmohammad Nouraniboosjin, Fatemeh Ganji
* [Permalink](
https://eprint.iacr.org/2025/903)
* [Download](
https://eprint.iacr.org/2025/903.pdf)
### Abstract
Side-channel analysis (SCA) has become a crucial area in ensuring the security of hardware implementations against potential vulnerabilities. With advancements in machine learning (ML) and artificial intelligence (AI), neural network(NN)-assisted techniques for SCA have demonstrated significant effectiveness. However, a fundamental question remains unanswered: are traces corresponding to different subkeys equally hard to attack? This paper addresses this issue by leveraging explainable AI techniques to analyze the hardness levels and, consequently, the root cause of hardness. To systematically investigate this problem, we reintroduce hardness metrics in SCA, which have been known to the ML community. Those metrics include query hardness (QH), log odds (LO), and matrix-based Rényi entropy (MRE). The challenge in this regard is that (virtually all) hardness metrics in ML cannot be adopted as they are. This is because ML and SCA metrics have conflicting goals, namely boosting accuracy and rank. Through careful experimentation, we identify the shortcomings of QH and LO in SCA and recommend MRE as a suitable hardness metric for SCA.
We also study how hardness has been seen in SCA, where recent work has suggested the influence of class “labels” on the attack difficulty. Employing rigorous evaluation, our paper demonstrates that no statistically significant evidence can be found to support this claim. This leads us to the question of how much traces’ time samples affect the inherent hardness in distinguishing key candidates. Our novel explainable AI (XAI) approach not only answers this, but also makes a link between hardness and rank as the common performance metric in SCA. Our findings indicate that hardness values are influenced mainly by time samples rather than specific key labels. Furthermore, we examine whether hardness captures intrinsic properties of the traces, specifically, their lack of separability in feature space due to their inherent similarities. To this end, we introduce, for the first time in the context of SCA, the use of maximum mean discrepancy (MMD) as a principled metric.. MMD effectively links trace hardness with attack difficulty by quantifying distributional differences induced by traces’ time samples. In addition to visualization techniques showing the root cause of hardness based on MMD, we employ XAI to explain the connection between MMD and attack hardness. Our proposed methodology enhances the understanding
of attack difficulty in SCA and contributes to developing more robust evaluation metrics for profiling attacks.
## 2025/904
* Title: The Security of ML-DSA against Fault-Injection Attacks
* Authors: Haruhisa Kosuge, Keita Xagawa
* [Permalink](
https://eprint.iacr.org/2025/904)
* [Download](
https://eprint.iacr.org/2025/904.pdf)
### Abstract
Deterministic signatures are often used to mitigate the risks associated with poor-quality randomness, where the randomness in the signing process is generated by a pseudorandom function that takes a message as input. However, some studies have shown that such signatures are vulnerable to fault-injection attacks. To strike a balance, recent signature schemes often adopt "hedged" randomness generation, where the pseudorandom function takes both a message and a nonce as input. Aranha et al. (EUROCRYPT 2020) investigated the security of hedged Fiat-Shamir signatures against 1-bit faults and demonstrated security for certain types of bit-tampering faults. Grilo et al. (ASIACRYPT 2021) extended this proof to the quantum random oracle model. Last year, NIST standardized the lattice-based signature scheme ML-DSA, which adopts the hedged Fiat-Shamir with aborts. However, existing security proofs against bit-tampering faults do not directly apply, as Aranha et al. left this as an open problem. To address this gap, we analyze the security of ML-DSA against multi-bit fault-injection attacks. We provide a formal proof of security for a specific class of intermediate values, showing that faults at these points cannot be exploited. Furthermore, to highlight the infeasibility of stronger fault resilience, we present key-recovery attacks that exploit signatures generated under fault injection at the other intermediate values.
## 2025/905
* Title: Authenticated Key Exchange Protocol with Remote Randomness
* Authors: John C. W. Chan
* [Permalink](
https://eprint.iacr.org/2025/905)
* [Download](
https://eprint.iacr.org/2025/905.pdf)
### Abstract
A conventional Authenticated Key Exchange (AKE) protocol consumes fresh random coins from the local random source. However, recent studies of bad randomness expose the vulnerability of some AKE protocols under small subgroup attacks when the random coins are manipulated or being repeated. It is important to ensure the bad randomness of one random source will not affect the security of the AKE protocol as a whole.
Thus, we introduce the notion of remote randomness by introducing additional ephemeral keys generated by a fresh remote random source in the AKE protocol. In this paper, we argue that because of the thrive of cloud computing, it encourages high
speed internal data transfer within server clusters or virtual machines, including entropy pool data used in our remote randomness AKE protocols. We present a remote randomness modification to the HMQV protocol to demonstrate its resilience under the manipulation of local random sources. We then provide a new security model with the consideration of remote randomness and show thatthe modified AKE protocol is secure under our new model.
## 2025/906
* Title: Covert Attacks on Machine Learning Training in Passively Secure MPC
* Authors: Matthew Jagielski, Rahul Rachuri, Daniel Escudero, Peter Scholl
* [Permalink](
https://eprint.iacr.org/2025/906)
* [Download](
https://eprint.iacr.org/2025/906.pdf)
### Abstract
Secure multiparty computation (MPC) allows data owners to train machine learning models on combined data while keeping the underlying training data private. The MPC threat model either considers an adversary who passively corrupts some parties without affecting their overall behavior, or an adversary who actively modifies the behavior of corrupt parties. It has been argued that in some settings, active security is not a major concern, partly because of the potential risk of reputation loss if a party is detected cheating.
In this work we show explicit, simple, and effective attacks that an active adversary can run on existing passively secure MPC training protocols, while keeping essentially zero risk of the attack being detected. The attacks we show can compromise both the integrity and privacy of the model, including attacks reconstructing exact training data.
Our results challenge the belief that a threat model that does not include malicious behavior by the involved parties may be reasonable in the context of PPML, motivating the use of actively secure protocols for training.
## 2025/907
* Title: New Framework for Structure-Aware PSI From Distributed Function Secret Sharing
* Authors: Dung Bui, Gayathri Garimella, Peihan Miao, Phuoc Van Long Pham
* [Permalink](
https://eprint.iacr.org/2025/907)
* [Download](
https://eprint.iacr.org/2025/907.pdf)
### Abstract
Private set intersection (PSI) allows two parties to jointly compute the intersection of their private sets without revealing any additional information. Structure-aware PSI (sa-PSI), introduced by Garimella et al. (Crypto'22), is a variant where Alice's input set has a publicly known structure and Bob's input set remains unstructured, enabling new applications like fuzzy PSI. Their construction relies solely on lightweight cryptographic primitives such as symmetric-key primitives and oblivious transfer (OT) extension. Since then, there has been active research on sa-PSI based on lightweight cryptography. Notably, recent work by Garimella et al. (Crypto'24) achieves sa-PSI with both communication and computation costs only scaling with the description size of Alice's set, rather than its potentially large cardinality. However, this line of work remains largely theoretical, lacking efficient concrete implementations.
In this work, we close this gap by presenting a new framework for sa-PSI that achieves practical efficiency. We identify and eliminate a hidden multiplicative overhead proportional to the security parameter (e.g., 128) in prior symmetric-key-based sa-PSI constructions. A key building block of our new framework is a distributed Function Secret Sharing (dFSS) key generation protocol tailored to the structure of Alice's set, which may be of independent interest.. To demonstrate the practicality of our framework, we extend our dFSS protocol to support incremental evaluation, introduce new techniques for spatial hashing, and develop several new optimization techniques, including reducing the exponential dependence on dimension and enabling load balancing between the two parties.
We instantiate our framework for structured sets defined by unions of $d$-dimensional $\ell_\infty$ balls, and implement our protocols using only lightweight symmetric-key primitives and OT extension. Our experiments show concrete performance improvements of up to $27\times$ speedup in computation and $7.7\times$ reduction in communication in low-dimensional, large-radius settings compared to existing public-key-based fuzzy PSI protocols by van Baarsen & Pu (Eurocrypt'24) and Gao et al. (Asiacrypt'24).
## 2025/908
* Title: SubLogarithmic Linear Time SNARKs from Compressed Sum-Check
* Authors: Nitin Singh, Sikhar Patranabis
* [Permalink](
https://eprint.iacr.org/2025/908)
* [Download](
https://eprint.iacr.org/2025/908.pdf)
### Abstract
We leverage recently proposed multilinear polynomial commitment schemes, with linear time prover and constant proof size to reduce the communication complexity of the classical sum-check protocol for multivariate polynomials. Specifically, for degree $d$ multivariate polynomial in $\mu$ variables which can be decomposed into multilinear polynomials, we exhibit a sum-check protocol with $O((\ell +d)n)$ prover cost and $O(\ell + d\log \log n)$ communication for $n=2^\mu$. This enables us to break the $O(\log n)$ barrier for this ubiquitous primitive used in multilinear SNARKs and implies first construction of prover efficient (with $O_\lambda(n)$ proving cost) SNARKs using multilinear polynomials with $O(\log \log n)$ proof-size. Currently, lower communication is only obtained by SNARKs based on univariate polynomials which incur $O(n\log n)$ prover complexity due to inherent polynomial multiplication.
Concretely, using compressed sum-check in HyperPlonk protocol allows us to reduce the proof size from about $5.5$ KB $-$ $6$ KB to only about $1.5$ KB, making it competitive with univariate SNARKs like PLONK.
## 2025/909
* Title: Energy Consumption Framework and Analysis of Post-Quantum Key-Generation on Embedded Devices
* Authors: J Cameron Patterson, William J Buchanan, Callum Turino
* [Permalink](
https://eprint.iacr.org/2025/909)
* [Download](
https://eprint.iacr.org/2025/909.pdf)
### Abstract
The emergence of quantum computing and Shor's algorithm necessitates an imminent shift from current public key cryptography techniques to post-quantum robust techniques. NIST has responded by standardising Post-Quantum Cryptography (PQC) algorithms, with ML-KEM (FIPS-203) slated to replace ECDH (Elliptic Curve Diffie-Hellman) for key exchange. A key practical concern for PQC adoption is energy consumption. This paper introduces a new framework for measuring the PQC energy consumption on a Raspberry Pi when performing key generation. The framework uses both available traditional methods and the newly standardised ML-KEM algorithm via the commonly utilised OpenSSL library.
## 2025/910
* Title: Robust Threshold ECDSA with Online-Friendly Design in Three Rounds
* Authors: Guofeng Tang, Haiyang Xue
* [Permalink](
https://eprint.iacr.org/2025/910)
* [Download](
https://eprint.iacr.org/2025/910.pdf)
### Abstract
Threshold signatures, especially ECDSA, enhance key protection by addressing the single-point-of-failure issue. Threshold signing can be divided into offline and online phases, based on whether the message is required. Schemes with low-cost online phases are referred to as ``online-friendly". Another critical aspect of threshold ECDSA for real-world applications is robustness, which guarantees the successful completion of each signing execution whenever a threshold number $t$ of semi-honest participants is met, even in the presence of misbehaving signatories.
The state-of-the-art online-friendly threshold ECDSA without robustness was developed by Doerner et al. in S\&P'24, requiring only three rounds. Recent work by Wong et al. in NDSS'23 (WMY\(^+\)23) and NDSS'24 (WMC24) achieves robustness but demands additional communication rounds (7 and 4, respectively) or incurs costly operations in the online phase, such as computations over a homomorphic encryption scheme.
This paper presents the first three-round threshold ECDSA scheme with both robustness and an online-friendly design. The online phase of our scheme relies solely on several elliptic-curve group operations, which are 2 to 3 orders of magnitude less computationally intensive than those based on linearly homomorphic encryption schemes. We implement our protocol and conduct a comprehensive comparison with WMY$^+$23 and WMC24. Benchmark results show that the online phase of our scheme is $2.5\times$ faster than that of WMY$^+$23 and hundreds of times faster than that of WMC24. Lastly, we demonstrate that our techniques can be extended to construct an online-friendly and robust three-round threshold BBS+ scheme.
## 2025/911
* Title: Fuzzy Private Set Intersection from VOLE
* Authors: Aron van Baarsen, Sihang Pu
* [Permalink](
https://eprint.iacr.org/2025/911)
* [Download](
https://eprint.iacr.org/2025/911.pdf)
### Abstract
Private set intersection (PSI) is a well-researched cryptographic primitive that allows two parties to compute the intersection of their input sets without revealing any information about items outside of the intersection. Fuzzy private set intersection is a relatively new variant of PSI, where items are not matched exactly but ``fuzzily''. Most commonly, items are points $\mathbf{q},\mathbf{w}$ in $d$-dimensional integer space $\mathbb{Z}^d$ and a point is a fuzzy match to another if it lies within a ball of radius $\delta$ centered at this point, with respect to some distance metric.
Previous works either only support infinity $(L_{\infty}$) distance metric and standard PSI functionality, or support general Minkowski ($L_{\mathsf{p}}$, $\mathsf{p}\in[1,\infty]$) distance metrics and realize richer functionalities but rely on expensive homomorphic encryptions. Our work aims to bridge this gap by giving the first construction of a fuzzy PSI protocol for general Minkowski distance metrics relying on significantly cheaper operations during the online phase.
Our main building block is a novel fuzzy matching protocol based on an oblivious pseudorandom function (OPRF), which can be realized very efficiently from vector oblivious linear evaluation (VOLE). Our protocol is able to preserve the asymptotic complexity as well as the simplicity of the fuzzy matching protocol from van Baarsen and Pu (Eurocrypt '24), while being much more concretely efficient. Additionally, we achieve several asymptotic improvements by representing intervals succinctly. Finally, we present the first fuzzy PSI protocol for infinity distance that places no assumptions on the sets of points, while maintaining asymptotic complexities comparable to the state-of-the-art fuzzy PSI protocol.
## 2025/912
* Title: Enforcing arbitrary constraints on Bitcoin transactions
* Authors: Federico Barbacovi, Enrique Larraia
* [Permalink](
https://eprint.iacr.org/2025/912)
* [Download](
https://eprint.iacr.org/2025/912.pdf)
### Abstract
The challenge of enforcing constraints on Bitcoin transac-
tions has recently gained a lot of attention. The current approach to
solve this problem falls short in certain aspects, such as privacy and
programmability. We design a new solution that leverages zkSNARKs
and allows enforcing arbitrary constraints on Bitcoin transactions while
maintaining some information private. Our approach also bypasses the
non-Turing completeness of Bitcoin Script, allowing the enforcement of
unbounded constraints, namely constraints that repeat a certain opera-
tion an unbounded number of times.
## 2025/913
* Title: Hidden Number Problems in Fiat-Shamir based Post-Quantum Signatures
* Authors: Yi-Fu Lai, Jonas Meers, Julian Nowakowski
* [Permalink](
https://eprint.iacr.org/2025/913)
* [Download](
https://eprint.iacr.org/2025/913.pdf)
### Abstract
Schnorr and (EC)DSA signatures famously become completely insecure once a few bits of the random nonce are revealed to an attacker. In this work, we investigate whether post-quantum signature schemes allow for similar attacks. Specifically, we consider three Fiat-Shamir based signature schemes: Dilithium (lattices), LESS (codes) and CSI-FiSh (isogenies). Analogous to the attacks on Schnorr and (EC)DSA, we assume knowledge of some bits of the commitment randomness used in the underlying ID protocol. Such attacks belong to the broader class of Hidden Number Problems.
In the case of LESS, we give an efficient attack that requires knowledge of a single bit of the randomness in roughly \(20000\) signatures to completely recover the secret key. Our attack is based on the observation that knowledge of a single bit in the randomness is enough to distinguish secret key entries from random ones. Since for proposed parameters there are at most \(548\) candidates for each entry, we can enumerate all candidates and use the distinguisher to recover the secret key one entry at a time.
For Dilithium we are able to recover the whole secret key using at most 1792 signatures when either 3 or 4 least significant bits of the randomness are known (depending on the parameter set). Here the attack is based on the simple observation that knowledge of the least significant bits of the randomness immediately yields a linear relation in the secret key.
For CSI-FiSh, on the other hand, we obtain only an inefficient attack that requires exponentially many signatures. However, we prove that this attack is essentially optimal. Thus, our results show that CSI-FiSh comes equipped with an inherent leakage resilience. The argument easily extends to a wider class of signature schemes, but notably does not apply to the predecessor SeaSign.
## 2025/914
* Title: Tweakable Permutation-based Luby-Rackoff Constructions
* Authors: Bishwajit Chakraborty, Abishanka Saha
* [Permalink](
https://eprint.iacr.org/2025/914)
* [Download](
https://eprint.iacr.org/2025/914.pdf)
### Abstract
Liskov, Rivest, and Wagner, in their seminal work, formulated tweakable blockciphers and proposed two blockcipher-based design paradigms, LRW1 and LRW2, where the basic design strategy is to xor the masked tweak to the input and output of a blockcipher. The 2-round cascaded LRW2 and 4-round cascaded LRW1 have been proven to be secure up to $O(2^{3n/4})$ queries, but $n$-bit optimal security still remains elusive for these designs. In their paper, Liskov also posed an open challenge of embedding the tweak directly in the blockcipher, and to address this, Goldenberg et al. introduced the tweakable Luby-Rackoff (LR) constructions. They showed that if the internal primitives are random functions, then for tweaks with $t$ blocks, the construction needs $t + 6$ rounds to be optimally $n$-bit CPA secure and $2t + 8$ rounds to be optimally $n$-bit CCA secure, where respectively $t$ and $2t$ rounds were required to process the tweaks. Since blockciphers can be designed much more efficiently than pseudorandom functions, in many practical applications the internal primitives of LR ciphers are instantiated as blockciphers, which however would lead to a birthday-bound factor, which is not ideal for say lightweight cryptography.
This paper addresses the following two key questions affirmatively: (1) Can Goldenberg et al.'s results be extended to LR constructions with random permutations as internal primitives without compromising the optimal $n$-bit security? (2) Can the number of rounds required for handling long tweaks be reduced?
We formally define TLR-compatible functions, for processing the tweak, which when composed with 4-rounds and 5-rounds of LR construction with random permutations as internal primitives gives us respectively $n$-bit CPA and CCA secure tweakable permutations. For the security analysis, we proved general Mirror Theory result for three permutations. We also propose instantiating TLR-compatible functions with one round LR where a permutation (resp, two AXU hash functions) is used to mask single-block tweaks (resp., variable-length tweaks), thus proposing the $n$-bit CPA (resp., CCA) secure tweakable permutation candidates, $\mathsf{TLRP5}$ and $\mathsf{TLRP5+}$ (resp., $\mathsf{TLRP7}$ and $\mathsf{TLRP7+}$), using $5$ (resp., $7$) LR rounds, which is a significant reduction from the tweak-length-dependent results of Goldenberg et al. As a corollary, we also show $n$-bit CPA (resp., CCA) security of $5$-rounds (resp.. $7$-rounds) permutation-based LR construction, which is quite an improvement over the existing $2n/3$-bit security proved by Guo et al.
## 2025/915
* Title: Improved differential cryptanalysis of SPEEDY
* Authors: Tim Beyne, Addie Neyt
* [Permalink](
https://eprint.iacr.org/2025/915)
* [Download](
https://eprint.iacr.org/2025/915.pdf)
### Abstract
SPEEDY is a family of lightweight block ciphers designed by Leander et al. Several differential attacks have been reported on the SPEEDY variants. However, nearly all of these attacks are based on differential characteristics with probabilities that differ from their reported values. These discrepancies arise from incorrect calculations of the (key-averaged) probability, particularly in consecutive steps within one round without intermediate key addition. In this paper, we revisit all reported differential characteristics and accurately calculate their key-averaged probabilities using quasidifferential trails.. We extend this to also estimate the fixed-key probability. Our analysis reveals several characteristics with zero or significantly altered probability, invalidating several proposed attacks. We further implement a search algorithm and find a 5.5-round differential distinguisher that can be used to mount a full-round key recovery attack with a data complexity of $2^{183}$ and a time complexity of $2^{185}$. The memory complexity varies: in the chosen-plaintext setting, it is $2^{156}$, whereas in the chosen-ciphertext setting, it is $2^{36}$.
## 2025/916
* Title: Automated Verification of Consistency in Zero-Knowledge Proof Circuits
* Authors: Jon Stephens, Shankara Pailoor, Isil Dillig
* [Permalink](
https://eprint.iacr.org/2025/916)
* [Download](
https://eprint.iacr.org/2025/916.pdf)
### Abstract
Circuit languages like Circom and Gnark have become essential tools for programmable zero-knowledge cryptography, allowing developers to build privacy-preserving applications. These domain-specific languages (DSLs) encode both the computation to be verified (as a witness generator) and the corresponding arithmetic circuits, from which the prover and verifier can be automatically generated. However, for these programs to be correct, the witness generator and the arithmetic circuit need to be mutually consistent in a certain technical sense, and inconsistencies can result in security vulnerabilities. This paper formalizes the consistency requirement for circuit DSLs and proposes the first automated technique for verifying it. We evaluate the method on hundreds of real-world circuits, demonstrating its utility for both automated verification and uncovering errors that existing tools are unable to detect.
## 2025/917
* Title: Jagged Polynomial Commitments (or: How to Stack Multilinears)
* Authors: Tamir Hemo, Kevin Jue, Eugene Rabinovich, Gyumin Roh, Ron D. Rothblum
* [Permalink](
https://eprint.iacr.org/2025/917)
* [Download](
https://eprint.iacr.org/2025/917.pdf)
### Abstract
Modern SNARK constructions, almost ubiquitously, rely on a polynomial commitment scheme (PCS) --- a method by which a prover can commit to a large polynomial $P$ and later provide evaluation proofs of the form "P(x)=y" to the verifier.
In the context of zkVMs (i.e., proof-systems for general-purpose RAM computations), the common design is to represent the computation trace as a sequence of tables, one per CPU instruction, and commit to the these tables, or even their individual columns, as separate polynomials. Committing separately to these polynomials has a large overhead in verification costs, especially in hash-based systems.
In this work we drastically reduce this cost via a new construction which we call the jagged PCS. This PCS enables the prover to commit to the entire computation trace as a single polynomial, but then allows for the verifier to emulate access to the individual table or column polynomials, so that the arithmetization can proceed in the usual manner. The jagged PCS may be thought of as a sparse PCS for a very particular form of sparsity - namely, a "jagged" matrix in which each column has a different height.
Our construction of the jagged PCS is highly performant in practice. In contrast to existing sparse PCS constructions for general sparse polynomials, the jagged PCS does not require the prover to commit to any additional oracles and the prover cost is dominated by 5 finite field multiplications per element in the trace area. Furthermore, we implement the verifier as an arithmetic circuit that depends only on the total trace area - thereby significantly reducing the problem of "combinatorial explosion" often encountered in zkVM recursion.
## 2025/918
* Title: The Accidental Computer: Polynomial Commitments from Data Availability
* Authors: Alex Evans, Guillermo Angeris
* [Permalink](
https://eprint.iacr.org/2025/918)
* [Download](
https://eprint.iacr.org/2025/918.pdf)
### Abstract
In this paper, we show two simple variations of a data availability scheme which enable it to act as a multilinear polynomial commitment scheme over the data in a block. The first variation enables commitments over all of the block's data with zero prover overhead: the data availability construction simply serves both purposes. The second variation allows commitments over subsets of data with nonzero but still concretely small proving costs, since most work is already done during data encoding. This works especially well for blockchains with a high degree of data parallelism, as data-parallel computation is particularly amenable to efficient GKR proofs. Since, in GKR, opening the polynomial commitment contributes significantly to prover costs, our construction enables the prover to reuse work already done by the data availability scheme, reducing—or wholly removing—work associated with the polynomial commitment scheme.
## 2025/919
* Title: Rep3 Reloaded: On the Cost of Function-Dependent Preprocessing in Semi-Honest 3PC with Honest Majority
* Authors: Marcel Keller
* [Permalink](
https://eprint.iacr.org/2025/919)
* [Download](
https://eprint.iacr.org/2025/919.pdf)
### Abstract
Rep3 denotes the implementation of semi-honest three-party computation with an honest majority in MP-SPDZ (CCS'20). It uses replicated secret sharing with one message per multiplication and party as proposed by Araki et al. (CCS'16). This approach is rivaled by Astra (CCSW'19) and Trio (PETS'25), which use function-dependent preprocessing. The latter is more involved than, e.g., Beaver triples which can be used as a commodity.
In this work, we present a full implementation of Astra and Trio in MP-SPDZ, and we evaluate the costs of the different approaches. We show the equivalence of the schemes, which implies that a protocol in any of the schemes can be translated to one in another with the same overall communication cost. We also present an improvement to two important building blocks for privacy-preserving computation, namely secure comparison and probabilistic truncation used in fixed-point arithmetic. To evaluate our implementation, we have benchmarked machine learning training and inference in all three schemes, improving on Keller and Sun (ICML'22) by over 30%. Our implementation also highlights the large storage requirements of function-dependent preprocessing as it runs the two phases separately. To the best of our knowledge, this is the first implementation to do so.
## 2025/920
* Title: SQIsign2D$^2$: New SQIsign2D Variant by Leveraging Power Smooth Isogenies in Dimension One
* Authors: Zheng Xu, Kaizhan Lin, Chang-An Zhao, Yi Ouyang
* [Permalink](
https://eprint.iacr.org/2025/920)
* [Download](
https://eprint.iacr.org/2025/920.pdf)
### Abstract
In this paper, we propose SQIsign2D$^2$, a novel digital signature scheme within the SQIsign2D family. Unlike other SQIsign2D variants, SQIsign2D$^2$ employs the prime $p=CD-1$ as the field characteristic, where $D=2^{e_2}$, $C=3^{e_3}$ and $C\approx D\approx \sqrt{p}$. By leveraging accessible $C$-isogenies, SQIsign2D$^2$ significantly reduces the degree requirements for two-dimensional isogeny computations, thereby lowering the overall computational overhead compared to other SQIsign2D variants.
We also provide a proof-of-concept implementation of SQIsign2D$^2$, and give an efficiency comparison between SQIsign2D$^2$ and other SQIsign2D variants. In particular, the experimental results demonstrate that the key generation and signing phases of SQIsign2D$^2$ are more than twice as fast as those of SQIsign2D-East at the NIST-I security level, respectively. Additionally, the verification performance in SQIsign2D$^2$ exhibits marginally improved efficiency.
## 2025/921
* Title: Zero-knowledge Authenticator for Blockchain: Policy-private and Obliviously Updateable
* Authors: Kostas Kryptos Chalkias, Deepak Maram, Arnab Roy, Joy Wang, Aayush Yadav
* [Permalink](
https://eprint.iacr.org/2025/921)
* [Download](
https://eprint.iacr.org/2025/921.pdf)
### Abstract
Transaction details and participant identities on the blockchain are often publicly exposed. In this work, we posit that blockchain's transparency should not come at the cost of privacy. To that end, we introduce zero-knowledge authenticators (zkAt), a new cryptographic primitive for privacy-preserving authentication on public blockchains. zkAt utilizes zero-knowledge proofs to enable users to authenticate transactions, while keeping the underlying authentiction policies private.
Prior solutions for such {policy-private authentication} required the use of threshold signatures, which can only hide the threshold access structure itself. In comparison, zkAt provides privacy for arbitrarily complex authentication policies, and offers a richer interface even within the threshold access structure by, for instance, allowing for the combination of signatures under distinct signature schemes.
In order to construct zkAt, we design a compiler that transforms the popular Groth16 non-interactive zero knowledge (NIZK) proof system into a NIZK with equivocable verification keys, a property that we define in this work. Then, for any zkAt constructed using proof systems with this new property, we show that all public information must be independent of the policy, thereby achieving policy-privacy.
Next, we give an extension of zkAt, called zkAt+ wherein, assuming a trusted authority, policies can be updated obliviously in the sense that a third-party learns no new information when a policy is updated by the policy issuer. We also give a theoretical construction for zkAt+ using recursive NIZKs, and explore the integration of zkAt into modern blockchains. Finally, to evaluate their feasibility, we implement both our schemes for a specific threshold access structure. Our findings show that zkAt achieves comparable performance to traditional threshold signatures, while also attaining privacy for significantly more complex policies with very little overhead.
## 2025/922
* Title: $\mathsf{HyperWolf}$: Efficient Polynomial Commitment Schemes from Lattices
* Authors: Lizhen Zhang, Shang Gao, Bin Xiao
* [Permalink](
https://eprint.iacr.org/2025/922)
* [Download](
https://eprint.iacr.org/2025/922.pdf)
### Abstract
This work introduces $\mathsf{HyperWolf}$, a Hypercube-Wise Optimized polynomial commitment scheme based on Lattices over ring Fields.
The scheme achieves succinctness with $O(\log N)$ proof size and verifier time, along with linear prover cost. It supports both univariate and multilinear polynomials under a unified framework.
Inspired by the two-dimensional tensor structure employed in \cite{golovnev2021brakedown} to achieve sublinear efficiency, we generalize the idea to a $k$-dimensional tensor (hypercube) structure and design a $k$-round recursive proof protocol, where each round performs a dimensionality reduction, which results in an overall efficiency of $O(kN^{1/k})$. By setting $k = \log N$, our scheme achieves near-optimal asymptotic performance.
$\mathsf{HyperWolf}$ is fully transparent and relies only on the standard lattice assumption over rings. In terms of concrete efficiency, for polynomials with $N = 2^{25}$ coefficients, our scheme yields proof sizes that are $8\times$ smaller than the lattice-based scheme of \cite{cini2024polynomial} (Crypto24), and over $200\times$ smaller than $\mathsf{SLAP}$ \cite{albrecht2024slap} (Eurocrypt24). Compared to $\mathsf{Greyhound}$\cite{nguyen2024greyhound} (Crypto24), our proof size is of similar magnitude, while achieving significantly lower verifier time.
## 2025/923
* Title: SPECK: Signatures from Permutation Equivalence of Codes and Kernels
* Authors: Marco Baldi, Michele Battagliola, Rahmi El Mechri, Paolo Santini, Riccardo Schiavoni, Davide De Zuane
* [Permalink](
https://eprint.iacr.org/2025/923)
* [Download](
https://eprint.iacr.org/2025/923.pdf)
### Abstract
The ongoing search for secure post-quantum cryptographic primitives has led to the development of numerous novel digital signature schemes. In this paper we introduce $\mathsf{SPECK}$, a new signature protocol based on the similarities between the Permuted Kernel Problem ($\mathsf{PKP}$) and the Permutation Code Equivalence Problem ($\mathsf{PEP}$). At its core, $\mathsf{SPECK}$ is built on the permutation version of LESS, but introduces a key modification to the commitment step. Indeed, instead of committing to an entire permuted code, the prover commits to a random relaxed $\mathsf{PKP}$ (that we call $\mathsf{PECK}$, Permutation Equivalence of Codes and Kernel) instance by randomly choosing a codeword from a random permutation of the initial code. In this sense, the secret key is used as a trapdoor to solve the committed $\mathsf{PECK}$ instance. The new approach allows for a faster verification that does not involve gaussian elimination, while maintains roughly the same signature size as LESS. We present the $\mathsf{Speck}$ protocol in detail and provide a deep analysis of the security of the new introduced assumptions.
## 2025/924
* Title: Card-Based Protocol Counting Connected Components of Graphs
* Authors: Koji Nuida
* [Permalink](
https://eprint.iacr.org/2025/924)
* [Download](
https://eprint.iacr.org/2025/924.pdf)
### Abstract
Card-based cryptography is a research area for realizing cryptographic functionality, such as secure multiparty computation and zero-knowledge proofs, by using a deck of physical cards and/or other non-electrical tools. Motivated by zero-knowledge proofs for solutions in pencil puzzles, there is a direction of recent studies on card-based protocols to verify connectivity of a set of cells or edges on lattice-shaped boards. In this paper, we generalize the problem to counting connected components of subsets on any graph, and propose a card-based protocol for the problem.
## 2025/925
* Title: SCMAC and LOL2.0: An AEAD Design Framework and A New Version of LOL Stream Cipher Design Framework
* Authors: Dengguo Feng, Lin Jiao, Yonglin Hao, Qunxiong Zheng, Wenling Wu, Wenfeng Qi, Lei Zhang, Liting Zhang, Siwei Sun, Tian Tian
* [Permalink](
https://eprint.iacr.org/2025/925)
* [Download](
https://eprint.iacr.org/2025/925.pdf)
### Abstract
In this paper, we introduce SCMAC, a general framework that transforms large-memory stream ciphers into AEAD schemes. It represents an intermediate design paradigm between Encrypt-then-MAC and dedicated single-pass AEAD, partially integrating encryption and authentication mechanisms while mitigating the risk of state leakage associated with immediate absorption and squeezing. Consequently, this approach harmonizes high performance with enhanced security. Additionally, we propose LOL2.0, an enhanced version of the blockwise stream cipher design framework LOL. This new framework improves security through modifications to the FSM update and output functions, and increases flexibility in constructing LFSR components. Based on SCMAC}$ and LOL2.0, we present two AEAD ciphers, LOL2.0-Mini and LOL2.0-Double, which support both stream cipher and AEAD modes. These ciphers are tailored to Beyond 5G/6G environments, offering 256-bit key length and resistance to known cryptanalysis methods, including differential, linear, and integral attacks. They also provide 128-bit security against forgery attacks in the nonce-respecting setting. Due to their compatibility with AES-NI and SIMD instructions, LOL2.0-Mini and LOL2.0-Double achieve software performance of 90 Gbps and 144 Gbps in stream cipher mode, respectively. In AEAD mode, they perform at 59 Gbps and 110 Gbps, significantly faster than their predecessor's Encrypt-then-MAC versions.
## 2025/926
* Title: Polocolo: A ZK-Friendly Hash Function Based on S-boxes Using Power Residues (Full Version)
* Authors: Jincheol Ha, Seongha Hwang, Jooyoung Lee, Seungmin Park, Mincheol Son
* [Permalink](
https://eprint.iacr.org/2025/926)
* [Download](
https://eprint.iacr.org/2025/926.pdf)
### Abstract
Conventional hash functions are often inefficient in zero-knowledge proof settings, leading to design of several ZK-friendly hash functions. On the other hand, lookup arguments have recently been incorporated into zero-knowledge protocols, allowing for more efficient handling of ``ZK-unfriendly'' operations, and hence ZK-friendly hash functions based on lookup tables.
In this paper, we propose a new ZK-friendly hash function, dubbed $\mathsf{Polocolo}$, that employs an S-box constructed using power residues. Our approach reduces the numbers of gates required for table lookups, in particular, when combined with Plonk, allowing one to use such nonlinear layers over multiple rounds. We also propose a new MDS matrix for the linear layer of $\mathsf{Polocolo}$. In this way, $\mathsf{Polocolo}$ requires fewer Plonk gates compared to the state-of-the-art ZK-friendly hash functions. For example, when $t = 8$, $\mathsf{Polocolo}$ requires $21\%$ less Plonk gates compared to Anemoi, which is currently the most efficient ZK-friendly hash function, where $t$ denotes the size of the underlying permutation in blocks of $\mathbb F_p$. For $t = 3$, $\mathsf{Polocolo}$ requires $24\%$ less Plonk gates than Reinforced Concrete, which is one of the recent lookup-based ZK-friendly hash functions.
## 2025/927
* Title: Enhancing Meme Token Market Transparency: A Multi-Dimensional Entity-Linked Address Analysis for Liquidity Risk Evaluation
* Authors: Qiangqiang Liu, Qian Huang, Frank Fan, Haishan Wu, Xueyan Tang
* [Permalink](
https://eprint.iacr.org/2025/927)
* [Download](
https://eprint.iacr.org/2025/927.pdf)
### Abstract
Meme tokens represent a distinctive asset class within the cryptocurrency ecosystem, characterized by high community engagement, significant market volatility, and heightened vulnerability to market manipulation. This paper introduces an innovative approach to assessing liquidity risk in meme token markets using entity-linked address identification techniques. We propose a multi-dimensional method integrating fund flow analysis, behavioral similarity, and anomalous transaction detection to identify related addresses. We develop a comprehensive set of liquidity risk indicators tailored for meme tokens, covering token distribution, trading activity, and liquidity metrics. Empirical analysis of tokens like BabyBonk, NMT, and BonkFork validates our approach, revealing significant disparities between apparent and actual liquidity in meme token markets. The findings of this study provide significant empirical evidence for market participants and regulatory authorities, laying a theoretical foundation for building a more transparent and robust meme token ecosystem.
## 2025/928
* Title: HAWK: Having Automorphisms Weakens Key
* Authors: Daniël M. H. van Gent, Ludo N. Pulles
* [Permalink](
https://eprint.iacr.org/2025/928)
* [Download](
https://eprint.iacr.org/2025/928.pdf)
### Abstract
The search rank-2 module Lattice Isomorphism Problem (smLIP), over a cyclotomic ring of degree a power of two, can be reduced to an instance of the Lattice Isomorphism Problem (LIP) of at most half the rank if an adversary knows a nontrivial automorphism of the underlying integer lattice. Knowledge of such a nontrivial automorphism speeds up the key recovery attack on HAWK at least quadratically, which would halve the number of security bits.
Luo et al. (ASIACRYPT 2024) recently found an automorphism that breaks omSVP, the initial underlying hardness assumption of HAWK. The team of HAWK amended the definition of omSVP to include this so-called symplectic automorphism in their submission to the second round of NIST's standardization of additional signatures. This work provides confidence in the soundness of this updated definition, assuming smLIP is hard, since there are plausibly no more trivial automorphisms that allow winning the omSVP game easily.
Although this work does not affect the security of HAWK, it opens up a new attack avenue involving the automorphism group that may be theoretically interesting on its own.
## 2025/929
* Title: The DROP Protocol: Dispute Resolution via Observation in Public for Verifiable, In-Person Voting
* Authors: Josh Benaloh, Michael Naehrig, Olivier Pereira
* [Permalink](
https://eprint.iacr.org/2025/929)
* [Download](
https://eprint.iacr.org/2025/929.pdf)
### Abstract
Dispute resolution has been a significant challenge in verifiable election protocols since such protocols were first proposed more than forty years ago. This work explores the problem from a new perspective and offers strong dispute resolution for in-person voting by depending on observers.
It proposes a simple definition of dispute resolution as a property of a voting protocol---a definition that is independent of any other security goal. It also presents the DROP protocol, a verifiable, in-person voting protocol that runs in the presence of observers who will always reach a correct conclusion in the case of a dispute without ever being able to compromise privacy or facilitate coercion.
## 2025/930
* Title: SEEC: Memory Safety Meets Efficiency in Secure Two-Party Computation
* Authors: Henri Dohmen, Robin Hundt, Nora Khayata, Thomas Schneider
* [Permalink](
https://eprint.iacr.org/2025/930)
* [Download](
https://eprint.iacr.org/2025/930.pdf)
### Abstract
Secure Multi-Party Computation (MPC) allows multiple parties to perform privacy-preserving computation on their secret data. MPC protocols based on secret sharing have high throughput which makes them well-suited for batch processing, where multiple instances are evaluated in parallel.
So far, practical implementations of secret sharing-based MPC protocols mainly focus on runtime and communication efficiency, so the memory overhead of protocol implementations is often overlooked. Established techniques to reduce the memory overhead for constant-round garbled circuit protocols cannot be directly applied to secret sharing-based protocols because they would increase the round complexity. Additionally, state-of-the-art implementations of secret sharing-based MPC protocols are implemented in C/C++ and may exhibit memory unsafety and memory leaks, which could lead to undefined behavior.
In this paper, we present SEEC: SEEC Executes Enormous Circuits, a framework for secret sharing-based MPC
with a novel approach to address memory efficiency and safety without compromising on runtime and communication efficiency. We realize SEEC in Rust, a language known for memory-safety at close-to-native speed. To reduce the memory footprint, we develop an in-memory representation for sub-circuits. Thus, we never inline sub-circuit calls during circuit evaluation, a common issue that blows up memory usage in MPC implementations.
We compare SEEC with the state-of-the-art secret sharing-based MPC frameworks ABY (NDSS'15), MP-SPDZ (CCS'20), and MOTION (TOPS'22) w.r.t. runtime, memory, and communication efficiency. Our results show that our reliable and memory-safe implementation has competitive or even better performance.
## 2025/931
* Title: Multivalued Broadcast with Optimal Length
* Authors: Gabriel Dettling, Martin Hirt, Chen-Da Liu-Zhang
* [Permalink](
https://eprint.iacr.org/2025/931)
* [Download](
https://eprint.iacr.org/2025/931.pdf)
### Abstract
A multi-valued broadcast protocol allows a sender $P_s$ to broadcast an $\ell$-bit message $m$ to $n$ recipients.
For all relevant models, multi-valued broadcast protocols with asymptotically optimal communication complexity $\mathcal{O}(\ell n)+\mathrm{Poly}(n)$ have been published.
Despite their very low communication complexity, these protocols perform poorly in modern networks.
Even if the network allows all $n$ parties to send messages at the same time, the execution time of the protocols is proportional to $\ell n$ (instead of $\ell$).
Even if the network allows to use all bilateral channels at the same time, the execution time is still proportional to $\ell$ (instead of $\ell/n$).
We ask the natural question whether multi-valued broadcast protocols exist which take time proportional to $\ell$ if parties can simultaneously send messages, and even take time proportional to $\ell/n$ if the bilateral channels can be used simultaneously. We provide a complete characterization of multi-valued broadcast with a two-fold answer:
On the negative side, we prove that for $t<n$, multi-valued broadcast requires time proportional to $\ell n$, if parties can simultaneously send messages, respectively take time proportional to $\ell$ if bilateral channels can be used simultaneously.
On the positive side, we prove that for $t < (1-\epsilon)n$ (for any fixed $\epsilon$), multi-valued broadcast in time proportional to $\ell$ (when parties can send messages simultaneously), respectively proportional to $\ell/n$ (if bilateral channels can be used simultaneously) is possible. We provide such protocols both with cryptographic security as well as with statistical security.
## 2025/932
* Title: Integral cryptanalysis in characteristic $p$
* Authors: Tim Beyne, Michiel Verbauwhede
* [Permalink](
https://eprint.iacr.org/2025/932)
* [Download](
https://eprint.iacr.org/2025/932.pdf)
### Abstract
Integral and ultrametric integral cryptanalysis are generalized to finite rings of prime characteristic $p$ that are isomorphic to a product of fields. This extends, for instance, the complete state of the art in integral cryptanalysis from $\mathbf{F}_2^n$ to $\mathbf{F}_q^n$, for all prime powers $q$. A compact representation of transition matrices, based on convex polyhedra, is introduced to ensure that the proposed methods are computationally efficient even for large $p$.
Automated tools are developed and applied to a few generic and several concrete primitives. The analysis shows that previous degree estimates for Feistel-GMiMC, HadesMiMC, AES-Prime, small-pSquare and mid-pSquare are overly optimistic. Furthermore, except for AES-Prime, these primitives do not meet their design criteria unless their number of rounds is substantially increased.
## 2025/933
* Title: Fast elliptic curve scalar multiplications in SN(T)ARK circuits
* Authors: Liam Eagen, Youssef El Housni, Simon Masson, Thomas Piellard
* [Permalink](
https://eprint.iacr.org/2025/933)
* [Download](
https://eprint.iacr.org/2025/933.pdf)
### Abstract
Proof systems of arbitrary computations have found many applications in recent years. However, the proving algorithm has a consequent complexity tied to the size of the computation being proved. Thus, proving large computations is quite inefficient. One of these large computations is the scalar multiplication over an elliptic curve. In this work, we provide new techniques for reducing the time corresponding to proving a scalar multiplication, using integer lattice reduction or a (half) extended Euclidean algorithm in a ring of integers. We investigate optimizations in the case of small (complex multiplication) discriminant curves, and its generalization for multi scalar multiplications as used in signature verification. We provide an optimized Golang implementation for different elliptic curves in different proof systems settings. The speed-up in proving time is between 22% and 53% compared to the previous state-of-the-art.
## 2025/934
* Title: Diving Deep Into UC: Uncovering and Resolving Issues in Universal Composability
* Authors: Céline Chevalier, Éric Sageloli
* [Permalink](
https://eprint.iacr.org/2025/934)
* [Download](
https://eprint.iacr.org/2025/934.pdf)
### Abstract
Introduced by Canetti in 2001, Universal Composability (UC) is a widely adopted security model that enables the specification and proof of security for a broad range of protocols, offering strong security guarantees.
At its core lies the universal composition theorem (UC theorem), which ensures that protocols proven secure within the framework remain secure even when deployed in real-world environments with multiple instances of them.
In this work, we present two key contributions. First, we identify several problems with the UC framework, in particular the UC Theorem. They include counterexamples, limitations that make it unusable for important classes of protocols, and weaknesses in its proof. These problems reveal flaws in nearly all the fundamental concepts of UC.
Secondly, we update the main concepts of UC to address these problems. Although these revisions are nontrivial, our updated definitions are intended to stay as closely aligned with the original model as possible, while providing greater simplicity overall. To ensure the validity of these updates, we present a proof of the updated UC theorem, which is more detailed and modular than the original.
## 2025/935
* Title: Side-channel safe conditional moves and swaps
* Authors: David Santos, Michael Scott
* [Permalink](
https://eprint.iacr.org/2025/935)
* [Download](
https://eprint.iacr.org/2025/935.pdf)
### Abstract
Constant-time implementations are a cornerstone of secure
cryptographic systems, particularly in the context of key exchange protocols and digital signature schemes. These implementations are designed to eliminate timing side-channel vulnerabilities by ensuring that the program’s execution time is independent of secret data. A fundamental building block for achieving constant-time behavior is the conditional move operation. Unlike traditional branching constructs (such as if statements), which may introduce data-dependent timing variations, conditional moves allow developers to write logic that behaves identically at the hardware level regardless of input values. As a result, they are widely used in cryptographic libraries and standards to ensure both functional correctness and resistance to timing attacks. In this work, we describe our efforts to implement elliptic curve cryptography with some immunity against certain power leakage side-channel attacks, using standard C and Rust code.
## 2025/936
* Title: Justvengers: Batched VOLE ZK Disjunctions in $\mathcal{O}(R{+}B{+}C)$ Communication
* Authors: Yibin Yang
* [Permalink](
https://eprint.iacr.org/2025/936)
* [Download](
https://eprint.iacr.org/2025/936.pdf)
### Abstract
Recent progress on zero-knowledge proofs (ZKPs) based on vector oblivious linear evaluation (VOLE) offers a promising paradigm for scaling ZKPs over extremely large statements. In particular, VOLE-based ZK is currently the best choice in terms of end-to-end execution time. However, VOLE-based ZK incurs high communication overhead — it usually scales linearly with the circuit size.
To mitigate this, existing literature considers VOLE-based ZK over structured statements. In this work, we focus on the batched disjunctive statement — $\mathcal{P}$ and $\mathcal{V}$ agree on $B$ fan-in $2$ circuits $\mathcal{C}_1, \ldots, \mathcal{C}_{B}$ over a field $\mathbb{F}$; each circuit is of size $C$ with $n_{\mathit{in}}$ inputs. $\mathcal{P}$'s goal is to demonstrate the knowledge of $R$ witnesses $(\mathit{id}_j \in [B]$, $\boldsymbol{w}_j \in \mathbb{F}^{n_{\mathit{in}}})$ for each $j \in [R]$ s.t. $\forall j \in [R], \mathcal{C}_{\mathit{id}_j}(\boldsymbol{w}_j) = 0$ where neither $\boldsymbol{w}_j$ nor $\mathit{id}_j$ is revealed. Batched disjunctive statements are effective, e.g., in emulating the CPU execution inside ZK. Note, the naïve solution results in a circuit of size $\mathcal{O}(RBC)$.
To prove such a statement using VOLE-based ZK, the prior state-of-the-art protocol $\mathsf{Antman}$ (Weng et al., CCS'22) incurred $\mathcal{O}(BC + R)$ communication by additionally relying on AHE, whereas $\mathsf{Batchman}$ (Yang et al., CCS'23) achieved $\mathcal{O}(RC + B)$ communication using only VOLE.
In this work, we combine these two protocols non-trivially and present a novel protocol $\mathsf{Justvengers}$ — targeting the batched disjunctive statement — that incurs only $\mathcal{O}(R + B + C)$ communication and $\mathcal{O}(BC + (B + C)R\log R)$ computation for prover, using AHE and VOLE.
## 2025/937
* Title: Attacking Poseidon via Graeffe-Based Root-Finding over NTT-Friendly Fields
* Authors: Antonio Sanso, Giuseppe Vitto
* [Permalink](
https://eprint.iacr.org/2025/937)
* [Download](
https://eprint.iacr.org/2025/937.pdf)
### Abstract
This paper explores the algebraic structure of the Poseidon and Poseidon2 permutations
over NTT-friendly finite fields, with a focus on preimage recovery via root-finding
techniques. We introduce an algorithm for efficiently identifying single roots of high-degree
univariate polynomials that emerge from these constructions, based on the Graeffe transform
and the tangent Graeffe method. Our approach is evaluated on reduced-round bounty
instances of these permutations at various security levels, as proposed by the Ethereum
Foundation, demonstrating practical effectiveness. These results yield new insights into the
security of permutation-based cryptographic primitives instantiated over NTT-friendly prime
fields.
## 2025/938
* Title: PSYLOCKE: Provably Secure Logic Locking with Practical Efficiency
* Authors: Yohei Watanabe, Kyoichi Asano, Haruka Hirata, Tomoki Ono, Mingyu Yang, Mitsugu Iwamoto, Yang Li, Yuko Hara
* [Permalink](
https://eprint.iacr.org/2025/938)
* [Download](
https://eprint.iacr.org/2025/938.pdf)
### Abstract
Logic locking is an obfuscation technique designed to protect the intellectual property of hardware designs and has attracted considerable attention for over a decade. However, most logic locking schemes have been developed heuristically, leading the field into a cat-and-mouse game between attackers and defenders. Indeed, several proposed schemes have already been broken. While recent works have introduced provably secure logic locking, they often incur impractical overhead or fail to support the ASIC design paradigm while offering strong theoretical security guarantees.
In this work, we propose PSYLOCKE, a provably secure and practically efficient logic locking scheme that balances formal security guarantees with implementation feasibility. We introduce a new security paradigm that formalizes logic locking under predetermined allowable leakage, such as circuit topology, and we provide refined definitions of resilience against specific attacks. Our analysis bridges general security definitions and attack resilience, quantifying how leakage impacts the success of real-world attacks. PSYLOCKE is provably secure under topology leakage and achieves significant efficiency improvement compared to existing provably secure logic locking schemes. Alongside our theoretical analysis, we demonstrate through quantitative evaluations using widely-used benchmark circuits that PSYLOCKE strikes a favorable balance between practical performance and security. Concretely, PSYLOCKE reduced the Area-Power-Delay overhead by an order of magnitude while achieving the same security level, compared to the existing provably secure logic locking scheme.
## 2025/939
* Title: On the security of one certificateless aggregate signature scheme with dynamic revocation in vehicular ad-hoc networks
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](
https://eprint.iacr.org/2025/939)
* [Download](
https://eprint.iacr.org/2025/939.pdf)
### Abstract
We show that the certificateless signature scheme [Veh. Commun. 47: 100763 (2024)] is insecure, because an adversary can launch forgery attack for any message. The signer's certificateless public key is not tightly bound to the system public key. The inherent flaw results in that the adversary can find an efficient signing algorithm functionally equivalent to the valid signing algorithm. The findings in this note could be helpful for newcomers who are not familiar with the designing techniques for certificateless signatures.
## 2025/940
* Title: Special Genera of Hermitian Lattices and Applications to HAWK
* Authors: Guilhem Mureau
* [Permalink](
https://eprint.iacr.org/2025/940)
* [Download](
https://eprint.iacr.org/2025/940.pdf)
### Abstract
In its decisional form, the module-Lattice Isomorphism Problem (decision module-LIP) has received first attention in a paper by Ling, Liu and Mendelsohn. The authors gave a polynomial-time algorithm to distinguish spinor genera within the genus of a quadratic binary $\mathcal{O}_F$-lattice, assuming that $\mathcal{O}_F$ is a principal ideal domain. However, this algorithm would not impact cryptographic schemes based on decision module-LIP for lattices such as those employed in HAWK, i.e., for binary $\mathcal{O}_K$-lattices equipped with an Hermitian form (with $K$ a cyclotomic number field). Motivated by HAWK's framework, we investigate a concept that serves as an analogue of the spinor genus for Hermitian lattices, called special genus. This notion was studied by Shimura who provided a complete set of invariants for describing special genera. Building on this result, we propose an algorithm to determine whether two Hermitian lattices belong to the same special genus. Specifically for HAWK's lattice and sibblings, our algorithm runs in classical polynomial-time.. Nevertheless we provide numerical evidence suggesting that the ability to distinguish special genera does not, in practice, constitute a significative advantage for solving decision module-LIP.
## 2025/941
* Title: Proof of Exponentiation: Enhanced Prover Efficiency for Algebraic Statements
* Authors: Zhuo Wu, Shi Qi, Xinxuan Zhang, Yi Deng, Kun Lai, Hailong Wang
* [Permalink](
https://eprint.iacr.org/2025/941)
* [Download](
https://eprint.iacr.org/2025/941.pdf)
### Abstract
Recent years have seen the widespread adoption of zkSNARKs constructed over small fields, including but not limited to, the Goldilocks field, small Mersenne prime fields, and tower of binary fields. Their appeal stems primarily from their efficacy in proving computations with small bit widths, which facilitates efficient proving of general computations and offers significant advantages, notably yielding remarkably fast proving efficiency for tasks such as proof of knowledge of hash preimages. Nevertheless, employing these SNARKs to prove algebraic statements (e.g., RSA, ECDSA signature verification) presents efficiency challenges.
To address this problem, we first define a new circuit model: arithmetic circuits with additional \textit{exponentiation gates}. These gates serve as fundamental building blocks for establishing more intricate algebraic relations. Then we present a \textit{Hash-committed Commit-and-Prove (HCP)} framework to construct Non-interactive Zero-knowledge (NIZK) proofs for the satisfiability of these circuits. Specifically, when proving knowledge of group exponentiations in discrete logarithm hard groups and RSA groups, compared to verifying complex group exponentiations within SNARK circuits, our approach requires proving only more lightweight computations within the SNARK, such as zk-friendly hash functions (e.g., Poseidon hash function). The number of these lightweight computations depends solely on the security parameter. This differentiation leads to substantial speedups for the prover relative to direct SNARK methods, while maintaining competitive proof size and verification cost.
## 2025/942
* Title: On the (in)security of Proofs-of-Space based Longest-Chain Blockchains
* Authors: Mirza Ahad Baig, Krzysztof Pietrzak
* [Permalink](
https://eprint.iacr.org/2025/942)
* [Download](
https://eprint.iacr.org/2025/942.pdf)
### Abstract
The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under ``resource variability'', i..e., if the total hashing power varies greatly over time.
Proofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a ``longest-chain'' blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound.
Concretely, we consider a security game in which the honest parties at any point control $\phi>1$ times more space than the adversary. The adversary can change the honest space by a factor $1\pm \varepsilon$ with every block (dynamic availability), and ``replotting'' the space (which allows answering two challenges using the same space) takes as much time as $\rho$ blocks.
We prove that no matter what chain selection rule is used, in this game the adversary can create a fork of length $\phi^2\cdot \rho / \varepsilon$ that will be picked as the winner by the chain selection rule.
We also provide an upper bound that matches the lower bound up to a factor $\phi$. There exists a chain selection rule (albeit a very strange one) which in the above game requires forks of length at least $\phi\cdot \rho / \varepsilon$.
Our results show the necessity of additional assumptions to create a secure PoSpace based longest-chain blockchain. The Chia network in addition to PoSpace uses a verifiable delay function.
Our bounds show that an additional primitive like that is necessary.
## 2025/943
* Title: On the Adaptive Security of Key-Unique Threshold Signatures
* Authors: Elizabeth Crites, Chelsea Komlo, Mary Maller
* [Permalink](
https://eprint.iacr.org/2025/943)
* [Download](
https://eprint.iacr.org/2025/943.pdf)
### Abstract
In this work, we investigate the security assumptions required to prove the adaptive security of threshold signatures. Adaptive security is a strong notion of security that allows an adversary to corrupt parties at any point during the execution of the protocol, and is of practical interest due to recent standardization efforts for threshold schemes. Towards this end, we give two different impossibility results.
We begin by formalizing the notion of a key-unique threshold signature scheme, where public keys have a unique correspondence to secret keys and there is an efficient algorithm for checking that public keys are well-formed. Key-uniqueness occurs in many threshold schemes that are compatible with standard, single-party signatures used in practice, such as BLS, ECDSA, and Schnorr signatures.
Our first impossibility result demonstrates that it is impossible to prove the adaptive security of any key-unique threshold signature scheme under any non-interactive computational assumption for a broad class of reductions, in the range $⌊t/2⌋< t_c ≤ t$, where $n$ is the total number of parties, $t_c$ is the number of corrupted parties, and $t+ 1$ is the threshold. We begin by ruling out full adaptive security (i.e., $t_c = t$ corruptions) for key-unique threshold signatures under non-interactive computational assumptions, including, but not limited to, the discrete logarithm (DL), computational Diffie-Hellman (CDH), and q-Strong Diffie-Hellman (q-SDH) assumptions. We then generalize this impossibility result for all $t_c$ such that $⌊t/2⌋< t_c ≤ t$.
Our second impossibility result applies specifically to key-unique threshold Schnorr signatures, currently an active area of research. We demonstrate that, even under the interactive computational assumptions One-More Discrete Logarithm (OMDL) and Algebraic OMDL (AOMDL), it is impossible to prove adaptive security for $⌊t/2⌋< t_c ≤ t$ in the programmable ROM with rewinding.
Taken together, our results underscore the difficulty of achieving adaptive security for key-unique threshold signatures. However, we believe this work can open a new line of research, by indicating assumptions and properties to aim for when constructing adaptively secure threshold schemes.
## 2025/944
* Title: Succinct Witness Encryption for Batch Languages and Applications
* Authors: Lalita Devadas, Abhishek Jain, Brent Waters, David J. Wu
* [Permalink](
https://eprint.iacr.org/2025/944)
* [Download](
https://eprint.iacr.org/2025/944.pdf)
### Abstract
Witness encryption allows one to encrypt a message to an $\mathsf{NP}$ relation $\mathcal{R}$ and a statement $x$. The corresponding decryption key is any valid $\mathsf{NP}$ witness $w$. In a succinct witness encryption scheme, we require that the size of the ciphertext be sublinear in the size of the $\mathsf{NP}$ relation. Currently, all realizations of succinct witness encryption for $\mathsf{NP}$ rely on strong assumptions such as pseudorandom obfuscation, extractable witness encryption, or differing-inputs obfuscation. Notably, none of these notions are known from standard assumptions.
In this work, we consider a relaxation of succinct witness encryption for $\mathsf{NP}$ to the setting of batch $\mathsf{NP}$. In this setting, one encrypts to an $\mathsf{NP}$ relation $\mathcal{R}$ together with $K$ statements $x_1, \ldots, x_K$. In the basic version, one can decrypt if they have a witness $w_1, \ldots, w_K$ for all $K$ statements. The succinctness requirement is that the size of the ciphertext should be sublinear in the number of instances $K$, but is allowed to grow with the size of the $\mathsf{NP}$ relation (i.e., the size of a single instance). More generally, we can also impose a (monotone) policy $P \colon \{0,1\}^K \to \{0,1\}$ over the $K$ instances. In this case, decryption is possible only if there exists $w_1, \ldots, w_K$ such that $P(\mathcal{R}(x_1, w_1), \ldots, \mathcal{R}(x_K, w_K)) = 1$.
In this work, we initiate a systematic study of succinct witness encryption for batch languages. We start with two simple constructions that support CNF and DNF policies based on plain witness encryption in conjunction with a somewhere statistically sound batch argument for $\mathsf{NP}$ or a function-binding hash function. Then, using indistinguishability obfuscation, we show how to support policies that can be computed by read-once bounded-space Turing machines. The latter construction is in fact a unique witness map for monotone-policy batch $\mathsf{NP}$, and as such, also gives a SNARG for monotone-policy batch $\mathsf{NP}$ where the size of the common reference string is sublinear in the number of instances.
Finally, we demonstrate some immediate applications of succinct witness encryption for batch languages. We construct new succinct computational secret sharing schemes for CNFs, DNFs, and weighted threshold policies. We also show how to build distributed monotone-policy encryption, a notion that generalizes recent trustless primitives like distributed broadcast encryption and threshold encryption with silent setup.