[digest] 2025 Week 25

## In this issue

1. [2023/867] Security Analysis of Forward Secure Log Sealing in ...
2. [2024/1665] DMM: Distributed Matrix Mechanism for ...
3. [2025/282] Transistor: a TFHE-friendly Stream Cipher
4. [2025/366] Enabling Microarchitectural Agility: Taking ML-KEM ...
5. [2025/668] (Interleaved) Extended Gabidulin Codes, More ...
6. [2025/896] InstaRand: Instantly Available and Instantly ...
7. [2025/1061] On the Adaptive Security of FROST
8. [2025/1116] The Pipes Model for Latency Analysis
9. [2025/1117] Speeding Up Sum-Check Proving
10. [2025/1118] Extracting Some Layers of Deep Neural Networks in ...
11. [2025/1119] Strong Secret Sharing with Snitching
12. [2025/1120] Traceable Secret Sharing Schemes for General Access ...
13. [2025/1121] 1-private n-party AND from 5 random bits
14. [2025/1122] An Induction Principle for Hybrid Arguments in ...
15. [2025/1123] Cryptographic Treatment of Key Control Security -- ...
16. [2025/1124] Toxic Decoys: A Path to Scaling Privacy-Preserving ...
17. [2025/1125] Reusable Designated Verifier NIZK from Lossy ...
18. [2025/1126] Leakage-Resilient Extractors against Number-on- ...
19. [2025/1127] KIVR: Committing Authenticated Encryption Using ...
20. [2025/1128] Solving LWE with Independent Hints about Secret and ...
21. [2025/1129] Lattice-based Obfuscation from NTRU and Equivocal LWE
22. [2025/1130] An Open-Source Framework for Efficient Side-Channel ...
23. [2025/1131] Empowering Privacy: A Zero Cost Protocol for ...
24. [2025/1132] Foundations of Multi-Designated Verifier Signature: ...
25. [2025/1133] A Note on the Rank Defect Phenomena in The ...
26. [2025/1134] Optimal Dimensionality Reduction using Conditional ...
27. [2025/1135] Keep It Unsupervised: Horizontal Attacks Meet ...
28. [2025/1136] Learning Parity with Quantization: Achieving Full- ...
29. [2025/1137] Security Analysis on UOV Families with Odd ...
30. [2025/1138] ZK-NR: A Layered Cryptographic Architecture for ...
31. [2025/1139] From Permissioned to Proof-of-Stake Consensus
32. [2025/1140] Unconditionally secure encryption algorithm with ...
33. [2025/1141] LZKSA: Lattice-Based Special Zero-Knowledge Proofs ...
34. [2025/1142] OnionPIRv2: Efficient Single-Server PIR
35. [2025/1143] Wedges, oil, and vinegar -- An analysis of UOV in ...
36. [2025/1144] Parasol Compiler: Pushing the Boundaries of FHE ...
37. [2025/1145] Dynamic Group Signatures with Verifier-Local Revocation
38. [2025/1146] QV-net: Decentralized Self-Tallying Quadratic ...
39. [2025/1147] Jigsaw: Doubly Private Smart Contracts
40. [2025/1148] On the Composition of Single-Keyed Tweakable Even- ...
41. [2025/1149] An Efficient Encryption Scheme Based on $(U+V, ...
42. [2025/1150] Lightweight Sorting in Approximate Homomorphic ...
43. [2025/1151] Faster signature verification with 3-dimensional ...
44. [2025/1152] ZK-ProVer: Proving Programming Verification in Non- ...
45. [2025/1153] Privacy-aware White and Black List Searching for ...
46. [2025/1154] Evaluation of Modular Polynomials from ...
47. [2025/1155] On the Security of Group Ring Learning with Errors
48. [2025/1156] An efficient construction of Raz's two-source ...
49. [2025/1157] General Multi-Prime Multi-Power RSA - A ...
50. [2025/1158] Bridging Bitcoin to Second Layers via BitVM2
51. [2025/1159] $\mathsf{DekartProof}$: Efficient Vector Range ...
52. [2025/1160] Black-box Approaches to Authenticated Dictionaries: ...
53. [2025/1161] High-Performance FPGA Accelerator for the Post- ...
54. [2025/1162] SV-LLM: An Agentic Approach for SoC Security ...
55. [2025/1163] Efficient, Scalable Threshold ML-DSA Signatures: An ...
56. [2025/1164] Man-in-the-Middle and Key Recovery Attacks against ...
57. [2025/1165] Automated Analysis and Synthesis of Message ...
58. [2025/1166] Threshold Signatures Reloaded: ML-DSA and Enhanced ...
59. [2025/1167] Security Analysis on a Public-Key Inverted-Index ...
60. [2025/1168] On Frontrunning Risks in Batch-Order Fair Systems ...

## 2023/867

* Title: Security Analysis of Forward Secure Log Sealing in Journald
* Authors: Felix Dörre, Astrid Ottenhues
* [Permalink](https://eprint.iacr.org/2023/867)
* [Download](https://eprint.iacr.org/2023/867.pdf)

### Abstract

This paper presents a security analysis of forward-secure log sealing in the journald logging system, which is installed by default in almost all modern Linux distributions. Forward-secure log sealing is a cryptographic technique used to ensure the integrity of past log entries even in the event of a full system compromise. We identify multiple security vulnerabilities in journald resulting from a gap between the model of the cryptographic primitives and their usage in a larger context. Our contribution is both theoretical and practical: As a practical contribution, we discovered attacks on the log sealing in journald and provide descriptions as well as implementations of the attacks. In particular one vulnerability allows to forge arbitrary logs for past entries without the validation tool noticing any problem. This finding completely breaks the security guarantee of log sealing. For all described vulnerabilities we provide patches, the two more serious ones are merged in systemd version 255. As a theoretical contribution, we provide formal definitions that capture the expected security properties of log sealing. We demonstrate our attacks on the vulnerable version of journald by showing how an attacker can defeat this security definition. Furthermore, we provide a modified version of the logging scheme which underlies the one in journald and prove that it satisfies our security definition. Since our patches have been merged, our logging scheme is the basis for the log sealing in journald. This work narrows the gap between theory and practice. It provides a practical example of the problems that can occur when applying cryptographic primitives to a complex real world system. It makes the logging implementation used in many Linux distributions more secure and demonstrates the importance of rigorous security analysis of cryptographic systems.



## 2024/1665

* Title: DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning Based on Constant-Overhead Linear Secret Resharing
* Authors: Alexander Bienstock, Ujjwal Kumar, Antigoni Polychroniadou
* [Permalink](https://eprint.iacr.org/2024/1665)
* [Download](https://eprint.iacr.org/2024/1665.pdf)

### Abstract

Federated Learning (FL) solutions with central Differential Privacy (DP) have seen large improvements in their utility in recent years arising from the $\textit{matrix mechanism}$, while FL solutions with distributed (more private) DP have lagged behind. In this work, we introduce the $\textit{distributed}$ matrix mechanism to achieve the best-of-both-worlds; better privacy of distributed DP and better utility from the matrix mechanism. We accomplish this using a novel cryptographic protocol that securely transfers sensitive values across client committees of different training iterations with constant communication overhead. This protocol accommodates the dynamic participation of users required by FL, including those that may drop out from the computation. We provide experiments which show that our mechanism indeed significantly improves the utility of FL models compared to previous distributed DP mechanisms, with little added overhead.



## 2025/282

* Title: Transistor: a TFHE-friendly Stream Cipher
* Authors: Jules Baudrin, Sonia Belaïd, Nicolas Bon, Christina Boura, Anne Canteaut, Gaëtan Leurent, Pascal Paillier, Léo Perrin, Matthieu Rivain, Yann Rotella, Samuel Tap
* [Permalink](https://eprint.iacr.org/2025/282)
* [Download](https://eprint.iacr.org/2025/282.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) allows computations on encrypted data without requiring decryption, ensuring data privacy during processing.  However, FHE introduces a significant expansion of ciphertext sizes compared to plaintexts, which results in higher communication. A practical solution to mitigate this issue is  transciphering, where only the master key is homomorphically encrypted, while the actual data is encrypted using a symmetric cipher, usually a stream cipher. The server then homomorphically evaluates the stream cipher to convert the encrypted data into a homomorphically encrypted form.

We introduce Transistor, a stream cipher specifically designed for efficient homomorphic evaluation within the TFHE scheme, a widely-used FHE framework known for its fast bootstrapping and ability to handle low-precision data. Transistor operates on $\mathbb{F}_{17}$ which is chosen to optimize TFHE performances. Its components are carefully engineered to both control noise growth and provide strong security guarantees. First, a simple TFHE-friendly implementation technique for LFSRs allows us to use such components to cheaply increase the state size. At the same time, a small Finite State Machine is the only part of the state updated non-linearly, each non-linear operation corresponding in TFHE to a rather expensive Programmable Bootstrapping. This update is done using an AES-round-like transformation. But, in contrast to other stream ciphers like SNOW or LEX, our construction comes with information-theoretic security arguments proving that an attacker cannot obtain any information about the secret key from three or fewer consecutive keystream outputs. These information-theoretic arguments are then combined with a thorough analysis of potential correlations to bound the minimal keystream length required for recovering the secret key.

Our implementation of Transistor significantly outperforms the state of the art of TFHE transciphering, achieving a throughput of over 60 bits/s on a standard CPU, all while avoiding the need for an expensive initialization process.



## 2025/366

* Title: Enabling Microarchitectural Agility: Taking ML-KEM & ML-DSA from Cortex-M4 to M7 with SLOTHY
* Authors: Amin Abdulrahman, Matthias J. Kannwischer, Thing-Han Lim
* [Permalink](https://eprint.iacr.org/2025/366)
* [Download](https://eprint.iacr.org/2025/366.pdf)

### Abstract

Highly-optimized assembly is commonly used to achieve the best performance for popular cryptographic schemes such as the newly standardized ML-KEM and ML-DSA.
The majority of implementations today rely on hand-optimized assembly for the core building blocks to achieve both security and performance.
However, recent work by Abdulrahman et al. takes a new approach, writing a readable base assembly implementation first and leaving the bulk of the optimization work to a tool named SLOTHY based on constraint programming.
SLOTHY performs instruction scheduling, register allocation, and software pipelining simultaneously using constraints modeling the architectural and microarchitectural details of the target platform.

In this work, we extend SLOTHY and investigate how it can be used to migrate already highly hand-optimized assembly to a different microarchitecture, while maximizing performance.
As a case study, we optimize state-of-the-art Arm Cortex-M4 implementations of ML-KEM and ML-DSA for the Arm Cortex-M7.

Our results suggest that this approach is promising:
For the number-theoretic transform (NTT) – the core building block of both ML-DSA and ML-KEM – we achieve speed-ups of $1.97\times$ and $1..69\times$, respectively.
For Keccak – the permutation used by SHA-3 and SHAKE and also vastly used in ML-DSA and ML-KEM – we achieve speed-ups of 30% compared to the M4 code and 5% compared to hand-optimized M7 code.
For many other building blocks, we achieve similarly significant speed-ups of up to $2.35\times$.
Overall, this results in 11 to 33% faster code for the entire cryptosystems.



## 2025/668

* Title: (Interleaved) Extended Gabidulin Codes, More Attacks on Rank Decoding Problem, and Their Applications to Cryptosystems
* Authors: Yongcheng Song, Rongmao Chen, Fangguo Zhang, Xinyi Huang, Jian Weng, Huaxiong Wang
* [Permalink](https://eprint.iacr.org/2025/668)
* [Download](https://eprint.iacr.org/2025/668.pdf)

### Abstract

In this paper, we investigate the Extended Gabidulin (EG) codes and the Interleaved EG (IEG) codes, develop more powerful attacks on the variants of the Rank Decoding (RD) problem, and enhance rank-based cryptosystems such as RQC and ROLLO.

First, we develop a general decoding algorithm for the (I)EG codes by solving the Linear Reconstruction (LR) problem. We find that the (I)EG codes can be probabilistically decoded by Welch-Berlekamp like algorithm, can achieve arbitrarily small decoding failure rate, and can decode up to the rank Gilbert-Varshamov bound (even close to the minimal distance). Our conclusion intrinsically shows that it is not necessary to require that the generator be linearly independent as Gabidulin codes for designing decodable codes from $q$-polynomials. An interesting and important byproduct is that we demonstrate that decoding interleaved Gabidulin codes can be achieved deterministically by solving the LR problem. It has long been believed that there are only probabilistic decoding algorithms for interleaved Gabidulin codes (IEEE TIT 2011, DCC 2014, DCC 2024).

Second, we develop the Blockwise Puncturing (BP) strategy for attacking on the Blockwise RD (BRD) problem (Asiacrypt 2023, IEEE TIT 2025) and Non-Homogenous RD (NHRD) problem (NIST PQC 2020, IEEE TIT 2024). We find that the BP strategy can significantly speed up the overdetermined MM modeling and  even underdetermined MM modelings. When the proposed attacks are applied to existing rank-based cryptosystems based on the BRD and NHRD problems, such as RQC (IEEE TIT 2025, IEEE TIT 2024, PQC 2024) and ROLLO (IEEE TIT 2025, IEEE TIT 2022), the most parameters sets are lower than the claimed security. This implies that these cryptosystems should enlarge parameters to resist the MM attack with the BP strategy.

Third, we apply the EG codes to RQC based on the BRD problem. We find that the gain of using the EG codes in decoding capacity outweighs the complexity loss in solving the BRD problem with the BP strategy, which still makes it possible to design more efficient RQC. As a result, RQC remains attractive sizes with a bandwidth of about 2.3 KB for 128-bit security. Overall, RQC still outperforms Hamming metric ones of NIST PQC Round 4 submissions, such as HQC, BIKE, and Classic McEliece, in terms of bandwidth, especially about 65% more compact than the NIST PQC selected  HQC.



## 2025/896

* Title: InstaRand: Instantly Available and Instantly Verifiable On-chain Randomness
* Authors: Jacob Gorman, Lucjan Hanzlik, Aniket Kate, Pratyay Mukherjee, Pratik Sarkar, Sri AravindaKrishnan Thyagarajan
* [Permalink](https://eprint.iacr.org/2025/896)
* [Download](https://eprint.iacr.org/2025/896.pdf)

### Abstract

Web3 applications, such as on-chain gaming, require unbiased and publicly verifiable randomness that can be obtained quickly and cost-effectively whenever needed. Existing services, such as those based on Verifiable Random Functions (VRF), incur network delays and high fees due to their highly interactive nature. FlexiRand [CCS 2023] addressed these problems by hiding the output of the VRF and using that as a seed to derive many randomnesses locally. These randomnesses are instantly available for usage. However, these randomnesses can not be verified independently (or instantly) without disclosing the seed, leaving scope for malicious actors to cheat.
   
    To solve this problem, we introduce a new notion, called instantly-verifiable VRF (iVRF), which enables the generation of many randomnesses from one VRF output seed, such that each of them is verifiable independently - this enables the $first$ solution to $cost-effectively$ generate randomnesses, such that they are $instantly$ $available$ and also $independently/instantly$ $verifiable$.

    To instantiate we propose a generic construction called InstaRand - it combines any (possibly distributed) VRF at the server's end with another VRF at the client's end to construct an iVRF. Our specific instantiation uses the BLS-based GLOW-DVRF [Euro S&P 2021] at the server's end and the DDH-based VRF of Goldberg et al. [RFC 2023] at the client's end. We use the universal composability framework to analyze the security. Moreover, due to its generality, InstaRand can be instantiated with any post-quantum secure VRF to yield a post-quantum secure iVRF.

    Our experiments demonstrate that our instantiation of InstaRand is $highly$ $practical$. The client incurs a $one-time$ cost to generate the seed (server's VRF output) by querying the GLOW-dVRF servers once. Once the seed is set up, the client locally generates the pseudorandom value on demand in $0.18~ms$, avoiding the client-server round-trip delay. Each value can be independently verified in $0.22~ms$. This yields a $400\times$ improvement in terms of output generation and $20\times$ improvement in verification cost over existing solutions.



## 2025/1061

* Title: On the Adaptive Security of FROST
* Authors: Elizabeth Crites, Jonathan Katz, Chelsea Komlo, Stefano Tessaro, Chenzhi Zhu
* [Permalink](https://eprint.iacr.org/2025/1061)
* [Download](https://eprint.iacr.org/2025/1061.pdf)

### Abstract

FROST and its variants are state-of-the-art protocols for threshold Schnorr signatures that are used in real-world applications. While static security of these protocols has been shown by several works, the security of these protocols under adaptive corruptions—where an adversary can choose which parties to corrupt at any time based on information it learns during protocol executions—has remained a notorious open problem that has received renewed attention due to recent standardization efforts for threshold schemes.

We show adaptive security (without erasures) of FROST and several variants under different corruption thresholds and computational assumptions. Let n be the total number of parties, t+1 the signing threshold, and t_c an upper bound on the number of corrupted parties.

1. We prove adaptive security when t_c = t/2 in the random oracle model (ROM) based on the algebraic one-more discrete logarithm assumption (AOMDL)—the same conditions under which FROST is proven statically secure.

2. We introduce the low-dimensional vector representation (LDVR) problem, parameterized by t_c, t, and n, and prove adaptive security in the algebraic group model (AGM) and ROM based on the AOMDL assumption and the hardness of the LDVR problem for the corresponding parameters. In some regimes (including some t_c >t/2) we show the LDVR problem is unconditionally hard, while in other regimes (in particular, when t_c = t) we show that hardness of the LDVR problem is necessary for adaptive security to hold. In fact, we show that hardness of the LDVR problem is necessary for proving adaptive security of a broad class of threshold Schnorr signatures.



## 2025/1116

* Title: The Pipes Model for Latency Analysis
* Authors: Andrew Lewis-Pye, Kartik Nayak, Nibesh Shrestha
* [Permalink](https://eprint.iacr.org/2025/1116)
* [Download](https://eprint.iacr.org/2025/1116.pdf)

### Abstract

Protocols for State-Machine-Replication (sometimes called 'blockchain' protocols)  generally make use of rotating leaders to drive consensus. In typical protocols (henceforth called 'single-sender' protocols), the leader is a single processor responsible for making and disseminating proposals to others. Since the leader acts as a bottleneck, apparently limiting throughput, a recent line of research has investigated the use of 'multi-sender' protocols in which many processors distribute proposals in parallel. Examples include DAG-based protocols such as DAG-Rider, Bullshark, Sailfish, Cordial Miners, Mysticeti, and variants such as Autobahn. However, existing models do not allow for a formal analysis to determine whether these protocols can actually handle higher throughputs than single-sender protocols such as PBFT, Tendermint, and HotStuff.

In this paper, we describe a very simple model that allows for such an analysis. For any given protocol, the model allows one to calculate latency as a function of  network bandwidth, network delays, the number of processors $n$, and the incoming transaction rate. Each protocol has a latency bottleneck: an incoming transaction rate at which latency becomes unbounded over the protocol execution, i.e., a maximum throughput that the protocol can handle without unbounded latency. 

With the aim of building to an analysis for state-of-the-art State-Machine-Replication (SMR) protocols, we begin by considering protocols for simpler primitives, such as Best-effort Broadcast and Reliable Broadcast. For Best-effort Broadcast, we establish a tight lower bound on latency for single-sender and multi-sender protocols when blocks are distributed without the use of techniques such as erasure coding. Perhaps unsurprisingly, a key difference between the single-sender and multi-sender approaches in this case is a factor $n$ in the point at which the latency bottleneck appears. However, for other primitives such as Reliable Broadcast,  our results may be more surprising: the factor $n$ difference now disappears, and maximum throughput for the two approaches differs by a constant factor, while multi-sender approaches will generally have latency that grows more quickly with $n$. For state-of-the-art SMR protocols, the picture that emerges is one with seemingly inherent trade-offs. If one compares single-sender protocols that use pipelining and erasure coding, such as DispersedSimplex, with DAG-based protocols such as Sailfish or Bullshark, the former are seen to have lower latency for a wide range of throughputs, while the benefit of the latter protocols is that they have  a latency bottleneck which is higher by a constant factor.



## 2025/1117

* Title: Speeding Up Sum-Check Proving
* Authors: Suyash Bagad, Quang Dao, Yuval Domb, Justin Thaler
* [Permalink](https://eprint.iacr.org/2025/1117)
* [Download](https://eprint.iacr.org/2025/1117.pdf)

### Abstract

At the core of the fastest known SNARKs is the sum-check protocol. In this paper, we describe two complementary optimizations that significantly accelerate sum-check proving in key applications.

The first targets scenarios where polynomial evaluations involve small values, such as unsigned 32-bit integers or elements of small subfields within larger extension fields. This setting is common in applications such as Jolt, a state-of-the-art zero-knowledge virtual machine (zkVM) built on the sum-check protocol. Our core idea is to replace expensive multiplications over large fields with cheaper operations over smaller domains, yielding both asymptotic speedups and significant constant-factor improvements.

The second optimization addresses a common pattern where sum-check is applied to polynomials of the form $g(x) = \mathsf{eq}(r, x) \cdot p(x)$, where $\mathsf{eq}$ is the multilinear extension of the equality function. We present a technique that substantially reduces the prover's cost associated with the equality polynomial component. We also describe how to combine both optimizations, which is essential for applications like Spartan within Jolt.

We have implemented and integrated our optimizations into the Jolt zkVM. Our benchmarks show consistent $2\text{-}3\times$ speedups for proving the first sum-check of Spartan within Jolt, with performance gains reaching 20$\times$ or more when baseline methods approach their memory limits.



## 2025/1118

* Title: Extracting Some Layers of Deep Neural Networks in the Hard-Label Setting
* Authors: Isaac A. Canales-Martínez, David Santos
* [Permalink](https://eprint.iacr.org/2025/1118)
* [Download](https://eprint.iacr.org/2025/1118.pdf)

### Abstract

Although studied for several years now, parameter extraction of Deep Neural Networks (DNNs) has seen the major advances only in recent years. Carlini et al. (Crypto 2020) and Canales-Martínez et al. (Eurocrypt 2024) showed how to extract the parameters of ReLU-based DNNs efficiently (polynomial time and polynomial number of queries, as a function on the number of neurons) in the raw-output setting, i.e., when the attacker has access to the raw output of the DNN. On the other hand, the more realistic hard-label setting gives the attacker access only to the most likely label after the DNN's raw output has been processed. Recently, Carlini et al. (Eurocrypt 2025) presented an efficient parameter extraction attack in the hard-label setting applicable to DNNs having a large number of parameters.

The work in Eurocrypt 2025 recovers the parameters of all layers except the output layer. The techniques presented there are not applicable to this layer due to its lack of ReLUs. In this work, we fill this gap and present a technique that allows recovery of the output layer. Additionally, we show parameter extraction methods that are more efficient when the DNN has contractive layers, i.e., when the number of neurons decreases in those layers. We successfully apply our methods to some networks trained on the CIFAR-10 dataset. Asymptotically, our methods have polynomial complexity in time and number of queries. Thus, a complete extraction attack combining the techniques by Carlini et al. and ours remains with polynomial complexity. Moreover, real execution time is decreased when attacking DNNs with the required contractive architecture.



## 2025/1119

* Title: Strong Secret Sharing with Snitching
* Authors: Jan Bormet, Stefan Dziembowski, Sebastian Faust, Tomasz Lizurej, Marcin Mielniczuk
* [Permalink](https://eprint.iacr.org/2025/1119)
* [Download](https://eprint.iacr.org/2025/1119.pdf)

### Abstract

One of the main shortcomings of classical distributed cryptography is its reliance on a certain fraction of participants remaining honest. Typically, honest parties are assumed to follow the protocol and not leak any information, even if behaving dishonestly would benefit them economically. More realistic models used in blockchain consensus rely on weaker assumptions, namely that no large coalition of corrupt parties exists, although every party can act selfishly. This is feasible since, in a consensus protocol, active misbehavior can be detected and "punished" by other parties. However, "information leakage", where an adversary reveals sensitive information via, e.g., a subliminal channel, is often impossible to detect and, hence, much more challenging to handle.

    A recent approach to address this problem was proposed by Dziembowski, Faust, Lizurej, and Mielniczuk (ACM CCS 2024), who introduced a new notion called secret sharing with snitching. This primitive guarantees that as long as no large coalition of mutually trusting parties exists, every leakage of the shared secret produces a "snitching proof" indicating that some party participated in the illegal secret reconstruction. This holds in a very strong model, where mutually distrusting parties use an MPC protocol to reconstruct any information about the shared secret. Such a "snitching proof" can be sent to a smart contract (modeled as a "judge") deployed on the blockchain, which punishes the aving party financially.

    In this paper, we extend the results from the work of CCS'24  by addressing its two main shortcomings. Firstly, we significantly strengthen the attack model by considering the case when mutually distrusting parties can also rely on a trusted third party (e.g., a smart contract). We call this new primitive strong secret sharing with snitching (SSSS).
    We present an SSSS protocol that is secure in this model. Secondly, unlike in the construction from CCS'24, our protocol does not require the honest parties to perform any MPC computations on hash functions. Besides its theoretical interest, this improvement is of practical importance, as it allows the construction of SSSS from any (even very "MPC-unfriendly") hash function.



## 2025/1120

* Title: Traceable Secret Sharing Schemes for General Access Structures
* Authors: Oriol Farràs, Miquel Guiot
* [Permalink](https://eprint.iacr.org/2025/1120)
* [Download](https://eprint.iacr.org/2025/1120.pdf)

### Abstract

Traceable secret sharing complements traditional schemes by enabling the identification of parties who sell their shares. In the model introduced by Boneh, Partap, and Rotem [CRYPTO’24], a group of corrupted parties generates a reconstruction box $R$ that, given enough valid shares as input, reconstructs the secret. The goal is to trace $R$ back to at least one of the corrupted parties using only black-box access to it.

While their work provides efficient constructions for threshold access structures, it does not apply to the general case. In this work, we extend their framework to general access structures and present the first traceable scheme supporting them.

In the course of our construction, we also contribute to the study of anonymous secret sharing, a notion recently introduced by Bishop et al. [CRYPTO’25], which strengthens classical secret sharing by requiring that shares do not reveal the identities of the parties holding them. We further advance this area by proposing new and stronger definitions, and presenting an anonymous scheme for general access structures that satisfies them.



## 2025/1121

* Title: 1-private n-party AND from 5 random bits
* Authors: Samuel Dittmer, Rafail Ostrovsky
* [Permalink](https://eprint.iacr.org/2025/1121)
* [Download](https://eprint.iacr.org/2025/1121.pdf)

### Abstract

In the field of information-theoretic cryptography, randomness complexity is a key metric for protocols for private computation, that is, the number of random bits needed to realize the protocol. Although some general bounds are known, even for the relatively simple example of $n$-party AND, the exact complexity is unknown.

We improve the upper bound from Couteau and Ros\'en in Asiacrypt 2022 on the (asymptotic) randomness complexity of $n$-party AND from 6 to 5 bits, that is, we give a $1$-private protocol for computing the AND of $n$ parties' inputs requiring $5$ bits of additional randomness, for all $n \geq 120$. Our construction, like that of Couteau and Ros\'en, requires a single source of randomness.


Additionally, we consider the modified setting of Goyal, Ishai, and Song (Crypto '22) where helper parties without any inputs are allowed to assist in the computation. In this setting, we show that the randomness complexity of computing a general boolean circuit $C$ $1$-privately is exactly 2 bits, and this computation can be performed with seven helper parties per gate.



## 2025/1122

* Title: An Induction Principle for Hybrid Arguments in Nominal-SSProve
* Authors: Markus Krabbe Larsen, Carsten Schürmann
* [Permalink](https://eprint.iacr.org/2025/1122)
* [Download](https://eprint.iacr.org/2025/1122.pdf)

### Abstract

Inductive reasoning in form of hybrid arguments is prevalent in cryptographic security proofs, but they are not integrated into formalisms used to model cryptographic security proofs, such as, for example, state-separating proofs. In this paper we present an induction principle for hybrid arguments that says that two games are many-steps indistinguishable if they are, respectively, indistinguishable from the end points of an iterated one-step indistinguishability argument. We demonstrate how to implement this induction rule in Nominal-SSProve by taking advantage of the nominal character of state-variables and illustrate its versatility by proving a general reduction from many-time CPA-security to one-time CPA-security for any asymmetric encryption scheme. We
then specialize the result to ElGamal and reduce CPA-secure to the decisional Diffie Hellman-assumption.



## 2025/1123

* Title: Cryptographic Treatment of Key Control Security -- In Light of NIST SP 800-108
* Authors: Ritam Bhaumik, Avijit Dutta, Akiko Inoue, Tetsu Iwata, Ashwin Jha, Kazuhiko Minematsu, Mridul Nandi, Yu Sasaki, Meltem Sönmez Turan, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2025/1123)
* [Download](https://eprint.iacr.org/2025/1123.pdf)

### Abstract

This paper studies the security of key derivation functions (KDFs), a central class of cryptographic algorithms used to derive multiple independent-looking keys (each associated with a particular context) from a single secret. The main security requirement is that these keys are pseudorandom (i.e., the KDF is a pseudorandom function). This paper initiates the study of an additional security property, called key control (KC) security, first informally put forward in a recent update to NIST Special Publication (SP) 800-108 standard for KDFs. Informally speaking, KC security demands that, given a known key, it is hard for an adversary to find a context that forces the KDF-derived key for that context to have a property that is specified a-priori and is hard to satisfy (e.g., that the derived key consists mostly of 0s, or that it is a weak key for a cryptographic algorithm using it).
We provide a rigorous security definition for KC security, and then move on to the analysis of the KDF constructions specified in NIST SP 800-108. We show, via security proofs in the random oracle model, that the proposed constructions based on XOFs or hash functions can accommodate for reasonable security margins (i.e., 128-bit security) when instantiated from KMAC and HMAC. We also show, via attacks, that all proposed block-cipher based modes of operation (while implementing mitigation techniques to prevent KC security attacks affecting earlier version of the standard) only achieve at best 72-bit KC security for 128-bit blocks, as with AES.



## 2025/1124

* Title: Toxic Decoys: A Path to Scaling Privacy-Preserving Cryptocurrencies
* Authors: Christian Cachin, François-Xavier Wicht
* [Permalink](https://eprint.iacr.org/2025/1124)
* [Download](https://eprint.iacr.org/2025/1124.pdf)

### Abstract

Anonymous cryptocurrencies attracted much attention over the past decade, yet ensuring both integrity and privacy in an open system remains challenging. Their transactions preserve privacy because they do not reveal on which earlier transaction they depend, specifically which outputs of previous transactions are spent. However, achieving privacy imposes a significant storage overhead due to two current limitations. First, the set of potentially unspent outputs of transactions grows indefinitely because the design hides cryptographically which one have been consumed; and, second, additional data must be stored for each spent output to ensure integrity, that is, to prevent that it can be spent again. We introduce a privacy-preserving payment scheme that mitigates these issues by randomly partitioning unspent outputs into fixed-size bins. Once a bin has been referenced in as many transactions as its size, it is pruned from the ledger. This approach reduces storage overhead while preserving privacy. We first highlight the scalability benefits of using smaller untraceability sets instead of considering the entire set of outputs, as done in several privacy-preserving cryptocurrencies. We then formalize the security and privacy notions required for a scalable, privacy-preserving payment system and analyze how randomized partitioning plays a key role in both untraceability and scalability. To instantiate our approach, we provide constructions based on Merkle trees and one based on cryptographic accumulators. We finally show the storage benefits of our scheme and analyze its resilience against large-scale flooding attacks using empirical transaction data.



## 2025/1125

* Title: Reusable Designated Verifier NIZK from Lossy Trapdoor Functions
* Authors: Riddhi Ghosal, Ilan Komargodski, Brent Waters
* [Permalink](https://eprint.iacr.org/2025/1125)
* [Download](https://eprint.iacr.org/2025/1125.pdf)

### Abstract

Understanding the minimal assumptions necessary for constructing non-interactive zero-knowledge arguments (NIZKs) for NP and placing it within the hierarchy of cryptographic primitives has been a central goal in cryptography. Unfortunately, there are very few examples of ``generic'' constructions of NIZKs or any of its natural relaxations.

In this work, we consider the relaxation of NIZKs to the designated-verifier model (DV-NIZK) and present a new framework for  constructing (reusable) DV-NIZKs for NP generically from  lossy trapdoor functions and PRFs computable by polynomial-size branching programs (a class that includes NC1). Previous ``generic'' constructions  of DV-NIZK for NP from standard primitives relied either on (doubly-enhanced) trapdoor permutations or on a public-key encryption scheme plus a KDM-secure secret key encryption scheme.

Notably, our DV-NIZK framework achieves statistical zero-knowledge. To our knowledge, this is the first DV-NIZK construction from any ``generic" standard assumption with statistical zero-knowledge that does not already yield a NIZK..

A key technical component of our construction is an efficient, unconditionally secure secret sharing scheme for non-monotone functions with randomness recovery for all polynomial-size branching programs. As an independent contribution we present an incomparable randomness recoverable (monotone) secret sharing for NC1 in a model with trusted setup that guarantees computational privacy assuming one-way functions. We believe that these primitives will be useful in related contexts in the future.



## 2025/1126

* Title: Leakage-Resilient Extractors against Number-on-Forehead Protocols
* Authors: Eshan Chattopadhyay, Jesse Goodman
* [Permalink](https://eprint.iacr.org/2025/1126)
* [Download](https://eprint.iacr.org/2025/1126.pdf)

### Abstract

Given a sequence of $N$ independent sources $\mathbf{X}_1,\mathbf{X}_2,\dots,\mathbf{X}_N\sim\{0,1\}^n$, how many of them must be good (i.e., contain some min-entropy) in order to extract a uniformly random string? This question was first raised by Chattopadhyay, Goodman, Goyal and Li (STOC '20), motivated by applications in cryptography, distributed computing, and the unreliable nature of real-world sources of randomness. In their paper, they showed how to construct explicit low-error extractors for just $K \geq N^{1/2}$ good sources of polylogarithmic min-entropy. In a follow-up, Chattopadhyay and Goodman improved the number of good sources required to just $K \geq N^{0.01}$ (FOCS '21). In this paper, we finally achieve $K=3$.

Our key ingredient is a near-optimal explicit construction of a new pseudorandom primitive, called a leakage-resilient extractor (LRE) against number-on-forehead (NOF) protocols. Our LRE can be viewed as a significantly more robust version of Li's low-error three-source extractor (FOCS '15), and resolves an open question put forth by Kumar, Meka, and Sahai (FOCS '19) and Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, and Zuckerman (FOCS '20). Our LRE construction is based on a simple new connection we discover between multiparty communication complexity and non-malleable extractors, which shows that such extractors exhibit strong average-case lower bounds against NOF protocols.



## 2025/1127

* Title: KIVR: Committing Authenticated Encryption Using Redundancy and Application to GCM, CCM, and More
* Authors: Yusuke Naito, Yu Sasaki, Takeshi Sugawara
* [Permalink](https://eprint.iacr.org/2025/1127)
* [Download](https://eprint.iacr.org/2025/1127.pdf)

### Abstract

Constructing a committing authenticated encryption (AE)
satisfying the CMT-4 security notion is an ongoing research challenge.
We propose a new mode KIVR, a black-box conversion for adding the
CMT-4 security to existing AEs. KIVR is a generalization of the Hash-
then-Enc (HtE) [Bellare and Hoang, EUROCRYPT 2022] and uses a
collision-resistant hash function to generate an initial value (or nonce)
and a mask for redundant bits, in addition to a temporary key. We ob-
tain a general bound r/2 + tag-col with r-bit redundancy for a large class
of CTR-based AEs, where tag-col is the security against tag-collision at-
tacks. Unlike HtE, the security of KIVR linearly increases with r, achiev-
ing beyond-birthday-bound security. With a t-bit tag, tag-col lies 0 ≤
tag-col ≤ t/2 depending on the target AE. We set tag-col = 0 for GCM,
GCM-SIV, and CCM, and the corresponding bound r/2 is tight for GCM
and GCM-SIV. With CTR-HMAC, tag-col = t/2, and the bound (r + t)/2
is tight.



## 2025/1128

* Title: Solving LWE with Independent Hints about Secret and Errors
* Authors: Qian Lu, Yansong Feng, Yanbin Pan
* [Permalink](https://eprint.iacr.org/2025/1128)
* [Download](https://eprint.iacr.org/2025/1128.pdf)

### Abstract

At CRYPTO 2020, Dachman-Soled et al. introduced a framework for to analyze the security loss of Learning with Errors ($\text{LWE}$), which enables the incremental integration of leaked hints into lattice-based attacks. Later  Nowakowski and May at ASIACRYPT 2023 proposed a novel method capable of integrating and combining an arbitrary number of both perfect and modular hints for the  LWE secret within a unified framework, which achieves better efficiency in constructing the lattice basis and makes the attacks more practical. In this paper, we first consider solving LWE with independent hints about both the secret and errors. Firstly, we introduce a novel approach to embed the hints for secret into the $\text{LWE}$ lattice by just matrix multiplication instead of the  LLL reduction as in Nowakowski and May's attack, which further reduces the time complexity to construct the lattice basis. For example, given 234 perfect hints about CRYSTALS-KYBER 512, our method reduces the running time from 2.16 hours to 0.35 hours. Secondly, we show how to embed the hints about errors into the obtained lattice basis.



## 2025/1129

* Title: Lattice-based Obfuscation from NTRU and Equivocal LWE
* Authors: Valerio Cini, Russell W. F. Lai, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2025/1129)
* [Download](https://eprint.iacr.org/2025/1129.pdf)

### Abstract

Indistinguishability obfuscation (iO) turns a program unintelligible without altering its functionality and is a powerful cryptographic primitive that captures the power of most known primitives. Recent breakthroughs have successfully constructed iO from well-founded computational assumptions, yet these constructions are unfortunately insecure against quantum adversaries. In the search of post-quantum secure iO, a line of research investigates constructions from fully homomorphic encryption (FHE) and tailored decryption hint release mechanisms. Proposals in this line mainly differ in their designs of decryption hints, yet all known attempts either cannot be proven from a self-contained computational assumption, or are based on novel lattice assumptions which are subsequently cryptanalysed. 

In this work, we propose a new plausibly post-quantum secure construction of iO by designing a new mechanism for releasing decryption hints. Unlike prior attempts, our decryption hints follow a public Gaussian distribution subject to decryption correctness constraints and are therefore in a sense as random as they could be. To generate such hints efficiently, we develop a general-purpose tool called primal lattice trapdoors, which allow sampling trapdoored matrices whose Learning with Errors (LWE) secret can be equivocated. We prove the security of our primal lattice trapdoors construction from the NTRU assumption. The security of the iO construction is then argued, along with other standard lattice assumptions, via a new Equivocal LWE assumption, for which we provide evidence for plausibility and identify potential targets for further cryptanalysis.



## 2025/1130

* Title: An Open-Source Framework for Efficient Side-Channel Analysis on Cryptographic Implementations
* Authors: Takuya Kojima, Masaki Morita, Hideki Takase, Hiroshi Nakamura
* [Permalink](https://eprint.iacr.org/2025/1130)
* [Download](https://eprint.iacr.org/2025/1130.pdf)

### Abstract

Side-channel attacks are increasingly recognized as a significant threat to hardware roots of trust. As a result, cryptographic module designers must ensure that their modules are resilient to such attacks before deployment. However, efficient evaluation of side-channel vulnerabilities in cryptographic implementations remains challenging. This paper introduces an open-source framework integrating FPGA designs, power measurement tools, and high-performance side-channel analysis libraries to streamline the evaluation process. The framework provides design templates for two widely used FPGA boards in the side-channel analysis community, enabling Shell-Role architecture, a modern FPGA design pattern. This shell abstraction allows designers to focus on developing cryptographic modules while utilizing standardized software tools for hardware control and power trace acquisition. Additionally, the framework includes acceleration plugins for ChipWhisperer, the leading open-source side-channel analysis platform, to enhance the performance of correlation power analysis (CPA) attacks. These plugins exploit modern many-core processors and Graphics Processing Units (GPUs) to speed up analysis significantly. To showcase the capabilities of the proposed framework, we conducted multiple case studies and highlighted significant findings that advance side-channel research. Furthermore, we compare our CPA plugins with existing tools and show that our plugins achieve up to 8.60x speedup over the state-of-the-art CPA tools.



## 2025/1131

* Title: Empowering Privacy: A Zero Cost Protocol for Concealing LGBTQ Search Queries
* Authors: Akshit Aggarwal, Pulkit Bharti, Yang Li, Srinibas Swain
* [Permalink](https://eprint.iacr.org/2025/1131)
* [Download](https://eprint.iacr.org/2025/1131.pdf)

### Abstract

FHE-based private information retrieval (PIR) is widely used to maintain the secrecy of the client queries in a client-server architecture. There are several ways to implement FHE-based PIR. Most of these approaches results in server computation overhead. Attempts for reducing the server computation overhead results in  1) fetching incorrect results, 2) leakage of queries, 3) large number of homomorphic operations (which is a time consuming process), and 4) downloading the entire dataset in the client side. In this work, we design a three server based approach where the first server discuss the nature of dataset, second server stores the computation results performed over first server, and third server stores the dataset in accordance to the proposed novel technique, that is, restricted bin packing algorithm (RBA). The proposed three server based approach optimise the aforementioned limitations. Later we implement the designed protocol using Tenseal library. Our protocol provides to retrieve the data by providing security to the client's query.



## 2025/1132

* Title: Foundations of Multi-Designated Verifier Signature: Comprehensive Formalization and New Constructions in Subset Simulation
* Authors: Keitaro Hashimoto, Kyosuke Yamashita, Keisuke Hara
* [Permalink](https://eprint.iacr.org/2025/1132)
* [Download](https://eprint.iacr.org/2025/1132.pdf)

### Abstract

A multi-designated verifier signature (MDVS) is a digital signature that empowers a signer to designate specific verifiers capable of verifying signatures.. Notably, designated verifiers are allowed to not only verify signatures but also simulate “fake” signatures indistinguishable from real ones produced by the original signer. Since this property is useful for realizing off-the-record (i.e., deniable) communication in group settings, MDVS is attracting attention in secure messaging. Recently, Damgård et al. (TCC’20) and Chakraborty et al. (EUROCRYPT’23) have introduced new MDVS schemes, allowing a subset of designated verifiers to simulate signatures in contrast to the conventional one, which requires all designated verifiers for signature simulation. They also define a stronger notion of security for them. This work delves into this new MDVS and offers a comprehensive formalization. We identify all possible security levels of MDVS schemes in subset simulations and prove that some of them are not feasible. Furthermore, we demonstrate that MDVS schemes meeting the security notion defined by Chakraborty et al. imply IND-CCA secure public-key encryption schemes. Beyond formalization, we present new constructions of MDVS schemes in subset simulation. Notably, we introduce a new construction of strongly secure MDVS schemes based on ring signatures and public-key encryption, accompanied by a generic conversion for achieving consistency through non-interactive zero-knowledge arguments.. Finally, we evaluate the efficiency of our MDVS schemes in classical and post-quantum settings, showing their practicality.



## 2025/1133

* Title: A Note on the Rank Defect Phenomena in The Linearization Attack on Elisabeth-4
* Authors: Antoine Bak
* [Permalink](https://eprint.iacr.org/2025/1133)
* [Download](https://eprint.iacr.org/2025/1133.pdf)

### Abstract

This note gives an explanation for a phenomenon which appeared in the cryptanalysis of the Elisabeth-4 stream cipher, a stream cipher optimized for Torus Fully Homomorphic Encryption (TFHE). This primitive was broken in 2023 by a linearization attack. The authors of this attack made an observation on the rank of the linear system they generated, which was lower than expected. They have provided a partial explanation for it using some properties of the negacyclic lookup tables (NLUT), one of the potential building block of the ciphers optimized for TFHE. NLUTs are defined as functions over integers modulo 2^n such that for all x, L(x + 2^(n−1) ) = −L(x). Their explanation of the rank defect of the linear system relies on the observation that the least significant bit of L(x) does not depend on the most significant bit of x, which prevents some monomials from appearing in the algebraic normal form (ANF) of the system. In this note, we prove a stronger property of the ANF of NLUTs and use it to give full proof of their observation on the rank of the system.



## 2025/1134

* Title: Optimal Dimensionality Reduction using Conditional Variational AutoEncoder
* Authors: Sana Boussam, Mathieu Carbone, Benoît Gérard, Guénaël Renault, Gabriel Zaid
* [Permalink](https://eprint.iacr.org/2025/1134)
* [Download](https://eprint.iacr.org/2025/1134.pdf)

### Abstract

The benefits of using Deep Learning techniques to enhance side-channel attacks performances have been demonstrated over recent years.
Most of the work carried out since then focuses on discriminative models.
However, one of their major limitations is the lack of theoretical results.
Indeed, this lack of theoretical results, especially concerning the choice of neural network architecture to consider or the loss to prioritize to build an optimal model, can be problematic for both attackers and evaluators.
Recently, Zaid et al. addressed this problem by proposing a generative model that bridges conventional profiled attacks and deep learning techniques, thus providing a model that is both explicable and interpretable.
Nevertheless the proposed model has several limitations.
Indeed, the architecture is too complex, higher-order attacks cannot be mounted and desynchronization is not handled by this model.
In this paper, we address the first limitation namely the architecture complexity, as without a simpler model, the other limitations cannot be treated properly.
To do so, we propose a new generative model that relies on solid theoretical results.
This model is based on conditional variational autoencoder and converges towards the optimal statistical model i.e. it performs an optimal attack.
By building on and extending the state-of-the-art theoretical works on dimensionality reduction, we integrate into this neural network an optimal dimensionality reduction i.e. a dimensionality reduction that is achieved without any loss of information.
This results in a gain of $\mathcal{O}(D)$, with $D$ the dimension of traces, compared to Zaid et al. neural network in terms of architecture complexity, while at the same time enhancing the explainability and interpretability.
In addition, we propose a new attack strategy based on our neural network, which reduces the attack complexity of generative models from $\mathcal{O}(N)$ to $\mathcal{O}(1)$, with $N$ the number of generated traces.
We validate all our theoretical results experimentally using extensive simulations and various publicly available datasets covering symmetric, asymmetric pre and post-quantum cryptography implementations.



## 2025/1135

* Title: Keep It Unsupervised: Horizontal Attacks Meet Simple Classifiers
* Authors: Sana Boussam, Ninon Calleja Albillos
* [Permalink](https://eprint.iacr.org/2025/1135)
* [Download](https://eprint.iacr.org/2025/1135.pdf)

### Abstract

In the last years, Deep Learning algorithms have been browsed and applied to Side-Channel Analysis in order to enhance attack’s performances. In some cases, the proposals came without an indepth analysis allowing to understand the tool, its applicability scenarios, its limitations and the advantages it brings with respect to classical statistical tools. As an example, a study presented at CHES 2021 proposed a corrective iterative framework to perform an unsupervised attack which achieves a 100% key bits recovery.
In this paper we analyze the iterative framework and the datasets it was applied onto. The analysis suggests a much easier and interpretable way to both implement such an iterative framework and perform the attack using more conventional solutions, without affecting the attack’s performances.



## 2025/1136

* Title: Learning Parity with Quantization: Achieving Full-Rate Encryption by Exploiting Quantization Noise in Code-Based Cryptography
* Authors: Shanxiang Lyu, Ling Liu, Cong Ling
* [Permalink](https://eprint.iacr.org/2025/1136)
* [Download](https://eprint.iacr.org/2025/1136.pdf)

### Abstract

The Learning Parity with Noise (LPN) problem has become a cornerstone for building lightweight, post-quantum secure encryption schemes. Despite its widespread adoption, LPN-based constructions suffer from a fundamental efficiency limitation: the essential noise term that provides security simultaneously requires error correction coding, leading to bandwidth overhead. We introduce a variant of LPN termed Learning Parity with Quantization (LPQ). While maintaining the ``learning from noisy equations'' framework, LPQ generates Bernoulli-like noise from code-aided quantization and enables simultaneous security and compression. Formally, the $\text{LPQ}_{N,n,\mathcal{C}}$ problem challenges adversaries to distinguish the triplet $(\mathbf{A}, Q_{\mathcal{C}}(\mathbf{A}\mathbf{s} \oplus \mathbf{u}), \mathbf{u})$ from uniform, where  $Q_{\mathcal{C}}$ is a vector quantization function based on an $(N,K)$ code $\mathcal{C}$, and   $\mathbf{u}$ serves as a public dither. We establish the hardness of LPQ through  a tight reduction from the LPN problem, maintaining equivalent security guarantees. We demonstrate LPQ’s practical efficacy through a full rate (i.e., rate-1) symmetric key encryption scheme, where LPQ combined with an extendable output function (XOF) achieves optimal ciphertext efficiency ($|\text{ct}| = |\text{pt}|$).



## 2025/1137

* Title: Security Analysis on UOV Families with Odd Characteristics: Using Symmetric Algebra
* Authors: Yi Jin, Yuansheng Pan, Xiaoou He, Boru Gong, Jintai Ding
* [Permalink](https://eprint.iacr.org/2025/1137)
* [Download](https://eprint.iacr.org/2025/1137.pdf)

### Abstract

Multivariate public key cryptosystems represent a promising family of post-quantum cryptographic schemes. Extensive research has demonstrated that multivariate polynomials are particularly well-suited for constructing digital signature schemes. Notably, the Unbalanced Oil and Vinegar (UOV) signature scheme and its variants have emerged as leading candidates in NIST's recent call for additional digital signature proposals.
  Security analysis against UOV variants are typically categorized into key-recovery attacks and forgery attacks, with the XL algorithm serving as one of the most significant methods for mounting key-recovery attacks. Recently, Lars Ran introduced a new attack against UOV variants that could be seen as an XL attack using exterior algebra; nevertheless, this new attacking algorithm is applicable only when the underlying (finite) field of the UOV variant is of characteristic $2$.
  In this work, we address this limitation by proposing a unified framework. Specifically, we first propose the notion of reduced symmetric algebra over any field, whose strength can be gleaned from the fact that it is essentially symmetric algebra when the characteristic $p$ of the underlying field is $0$ and is exterior algebra when $p=2$. Based upon the reduced symmetric algebra, we then propose a new XL attack against all UOV variants. Our XL attack is equivalent to Lars Ran's one for those UOV variants whose underlying fields are of characteristic $p=2$; more importantly, our XL attack can also be applied to analyze those UOV variants with odd characteristic, such as QR-UOV submitted to NIST's PQC Standardization Project. It should be noted that in regard to those 12 QR-UOV recommended instances, our XL attack does not outperform existing key-recovery counterparts; nevertheless, it is the optimal key-recovery attack for some specific UOV instances with odd characteristic.



## 2025/1138

* Title: ZK-NR: A Layered Cryptographic Architecture for  Explainable Non-Repudiation
* Authors: Thierry Emmanuel MINKA MI NGUIDJOI, MANI ONANA Flavien Serge, DJOTIO NDIÉ Thomas
* [Permalink](https://eprint.iacr.org/2025/1138)
* [Download](https://eprint.iacr.org/2025/1138.pdf)

### Abstract

This paper introduces ZK-NR, a modular cryptographic protocol designed to ensure privacy-preserving non-repudiation in the co-production of digital public services. By integrating Merkle commitments, zero-knowledge proofs (STARKs), threshold BLS signatures, and post-quantum Dilithium authentication, ZK-NR enables the creation of secure, verifiable, and auditable evidence across decentralized infrastructures. Unlike traditional digital signatures or blockchain-based logs, ZK-NR provides formally verifiable attestations without disclosing sensitive content, making it suitable for public finance, e-government, and regulated digital ecosystems. The protocol is modeled in Tamarin and implemented as a proof-of-concept using open cryptographic tools. This contribution offers a reproducible foundation for future infrastructures requiring long-term trust, data minimization, and legal admissibility, particularly in contexts where citizens and institutions share responsibility for digital evidence.. ZK-NR addresses the tension between confidentiality and accountability, providing an interoperable and future-ready layer for trustworthy public service delivery.
This preliminary work focuses on architectural composition and implementation feasibility. It does not include formal security proofs.



## 2025/1139

* Title: From Permissioned to Proof-of-Stake Consensus
* Authors: Jovan Komatovic, Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, Ertem Nusret Tas
* [Permalink](https://eprint.iacr.org/2025/1139)
* [Download](https://eprint.iacr.org/2025/1139.pdf)

### Abstract

This paper presents the first generic compiler that transforms any permissioned consensus protocol into a proof-of-stake permissionless consensus protocol.. For each of the following properties, if the initial permissioned protocol satisfies that property in the partially synchronous setting, the consequent proof-of-stake protocol also satisfies that property in the partially synchronous and quasi-permissionless setting (with the same fault-tolerance): consistency; liveness; optimistic responsiveness; every composable log-specific property; and message complexity of a given order. Moreover, our transformation ensures that the output protocol satisfies accountability (identifying culprits in the event of a consistency violation), whether or not the original permissioned protocol satisfied it.



## 2025/1140

* Title: Unconditionally secure encryption algorithm with unified confidentiality and integrity
* Authors: Zhen-Hu Ning
* [Permalink](https://eprint.iacr.org/2025/1140)
* [Download](https://eprint.iacr.org/2025/1140.pdf)

### Abstract

One-Time Pad (OTP), introduced by Shannon, is well-known as an unconditionally secure encryption algorithm and has become the cornerstone of modern cryptography. However, the unconditional security of OTP applies solely to confidentiality and does not extend to integrity. Hash functions such as SHA2, SHA3 or SM3 applies only to integrity but not to confidentiality and also can not obtain unconditional security. Encryption and digital signatures based on asymmetric cryptography can provide confidentiality, integrity and authentication, but they can only achieve computational security. Leveraging the fundamental principles of quantum mechanics，Quantum key distribution（QKD）can achieve unconditional security in theory. However, due to limitations in eavesdropping detection, the use of classical channels and imperfections in quantum devices, it cannot reach unconditional security in practical applications. In this paper, based on  polynomial rings and the theory of probability, we propose an unconditionally secure encryption algorithm with unified confidentiality and integrity. The main calculation of the  encryption algorithm is  Cyclic Redundancy Check(CRC).  Theoretical analysis proves that the encryption algorithm not only meets the unconditional security of confidentiality, but also guarantees the unconditional security of integrity, especially suitable for high-security communications such as finance, military, government and other fields.



## 2025/1141

* Title: LZKSA: Lattice-Based Special Zero-Knowledge Proofs for Secure Aggregation's Input Verification
* Authors: Zhi Lu, Songfeng Lu
* [Permalink](https://eprint.iacr.org/2025/1141)
* [Download](https://eprint.iacr.org/2025/1141.pdf)

### Abstract

In many fields, the need to securely collect and aggregate data from distributed systems is growing. However, designs that rely solely on encrypted data transmission make it difficult to trace malicious users. To address this challenge, we have enhanced the secure aggregation (SA) protocol proposed by Bell et al. (CCS 2020) by introducing verification features that ensure compliance with user inputs and encryption processes while preserving data privacy. We present LZKSA, a quantum-safe secure aggregation system with input verification. LZKSA employs seven zero-knowledge proof (ZKP) protocols based on the Ring Learning with Errors problem, specifically designed for secure aggregation. These protocols verify whether users have correctly used SA keys and their $L_{\infty}$, $L_2$ norms and cosine similarity of data, meet specified constraints, to exclude malicious users from current and future aggregation processes. The specialized ZKPs we propose significantly enhance proof efficiency. In practical federated learning scenarios, our experimental evaluations demonstrate that the proof generation time for $L_{\infty}$ and $L_2$ constraints is reduced to about $10^{-3}$ of that required by the current state-of-the-art method, RoFL (S\&P 2023), and ACORN (USENIX 2023). For example, the proof generation/verification time of RoFL, ACORN and LZKSA for $L_{\infty}$ is 94s/29.9s, 78.7s/33.9s, and 0.02s/0.0062s for CIFAR10, respectively.



## 2025/1142

* Title: OnionPIRv2: Efficient Single-Server PIR
* Authors: Yue Chen, Ling Ren
* [Permalink](https://eprint.iacr.org/2025/1142)
* [Download](https://eprint.iacr.org/2025/1142.pdf)

### Abstract

This paper presents OnionPIRv2, an efficient implementation of OnionPIR incorporating standard orthogonal techniques and engineering improvements.  OnionPIR is a single-server PIR scheme that improves response size and computation cost by utilizing recent advances in somewhat homomorphic encryption (SHE) and carefully composing two lattice-based SHE schemes to control the noise growth of SHE. OnionPIRv2 achieves $2.5$x-$3.6$x response overhead for databases with moderately large entries (around $4$ KB or above) and up to $1600$ MB/s server computation throughput.



## 2025/1143

* Title: Wedges, oil, and vinegar -- An analysis of UOV in characteristic 2
* Authors: Lars Ran
* [Permalink](https://eprint.iacr.org/2025/1143)
* [Download](https://eprint.iacr.org/2025/1143.pdf)

### Abstract

The Unbalanced Oil and Vinegar construction (UOV) has been the backbone of multivariate cryptography since the fall of HFE-based schemes. In fact, 7 UOV-based schemes have been submitted to the NIST additional call for signatures, and 4 of these made it to the second round. For efficiency considerations, most of these schemes are defined over a field of characteristic 2. This has as a side effect that the polar forms of the UOV public maps are not only symmetric, but also alternating.

In this work, we propose a new key-recovery attack on UOV in characteristic 2 that makes use of this property. We consider the polar forms of the UOV public maps as elements of the exterior algebra. We show that these are contained in a certain subspace of the second exterior power that is dependent on the oil space. This allows us to define relations between the polar forms and the image of the dual of the oil space under the Plücker embedding. With this, we can recover the secret oil space using sparse linear algebra.

This new attack has an improved complexity over previous methods and reduces the security by 4, 11, and 20 bits for uov-Ip, uov-III, and uov-V, respectively. Furthermore, the attack is applicable to MAYO$_2$ and improves on the best attack by 28 bits.



## 2025/1144

* Title: Parasol Compiler: Pushing the Boundaries of FHE Program Efficiency
* Authors: Rick Weber, Ryan Orendorff, Ghada Almashaqbeh, Ravital Solomon
* [Permalink](https://eprint.iacr.org/2025/1144)
* [Download](https://eprint.iacr.org/2025/1144.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a key technology to enable privacy-preserving computation. While optimized FHE implementations already exist, the inner workings of FHE are technically complex. This makes it challenging, especially for non-experts, to develop highly-efficient FHE programs that can exploit the advanced hardware of today. Although several compilers have emerged to help in this process, due to design choices, they are limited in terms of application support and the efficiency levels they can achieve.

In this work, we showcase how to make FHE accessible to non-expert developers while retaining the performance provided by an expert-level implementation. We introduce Parasol, a novel end-to-end compiler encompassing a virtual processor with a custom Instruction Set Architecture (ISA) and a low-level library that implements FHE operations. Our processor integrates with existing compiler toolchains, thereby providing mainstream language support. We extract parallelism at multiple levels via our processor design and its computing paradigm. Specifically, we champion a Circuit Bootstrapping (CBS)-based paradigm, enabling efficient FHE circuit composition with multiplexers. Furthermore, Parasol’s underlying design highlights the benefits of expressing FHE computations at a higher level—producing highly compact program representations. Our experiments demonstrate the superiority of Parasol, in terms of runtime (up to 17x faster), program size (up to 22x smaller), and compile time (up to 32x shorter) compared to the current state-of-the-art. We expect the FHE computing paradigm underlying Parasol to attract future interest since it exposes added parallelism for FHE accelerators to exploit.



## 2025/1145

* Title: Dynamic Group Signatures with Verifier-Local Revocation
* Authors: Callum London, Daniel Gardham, Constantin Catalin Dragan
* [Permalink](https://eprint.iacr.org/2025/1145)
* [Download](https://eprint.iacr.org/2025/1145.pdf)

### Abstract

Group Signatures are fundamental cryptographic primitives that allow users to sign a message on behalf of a predefined set of users, curated by the group manager. The security properties ensure that members of the group can sign anonymously and without fear of being framed. In dynamic group signatures, the group manager has finer-grained control over group updates while ensuring membership privacy (i.e., hiding when users join and leave). The only known scheme that achieves standard security properties and membership privacy has been proposed by Backes et al. CCS 2019. However, they rely on an inefficient revocation mechanism that re-issues credentials to all active members during every group update, and users have to rely on a secure and private channel to join the group.
In this paper, we introduce a dynamic group signature that supports verifier-local revocation, while achieving strong security properties, including membership privacy for users joining over a public channel. Moreover, when our scheme is paired with structure-preserving signatures over equivalence class it enjoys a smaller signature size compared to Backes et al. Finally, as a stand-alone contribution we extend the primitive Asynchronous Remote Key Generation (Frymann et al. CCS 2020) with trapdoors and introduce new security properties to capture this new functionality, which is fundamental to the design of our revocation mechanism



## 2025/1146

* Title: QV-net: Decentralized Self-Tallying Quadratic Voting with Maximal Ballot Secrecy
* Authors: Zibo Zhou, Zongyang Zhang, Feng Hao, Bowen Zheng, Zulkarnaim Masyhur
* [Permalink](https://eprint.iacr.org/2025/1146)
* [Download](https://eprint.iacr.org/2025/1146.pdf)

### Abstract

Decentralized e-voting enables secure and transparent elections without relying on trusted authorities, with blockchain emerging as a popular platform. It has compelling applications in Decentralized Autonomous Organizations (DAOs), where governance relies on voting with blockchain-issued tokens. Quadratic voting (QV), a mechanism that mitigates the dominance of large token holders, has been adopted by many DAO elections to enhance fairness. However, current QV systems deployed in practice publish voters' choices in plaintext with digital signatures. The open nature of all ballots comprises voter privacy, potentially affecting voters' honest participation. Prior research proposes using cryptographic techniques to encrypt QV ballots, but they work in a centralized setting, relying on a trusted group of tallying authorities to administrate an election. However, in DAO voting, there is no trusted third party.  

In this paper, we propose QV Network (QV-net), the first decentralized quadratic voting scheme, in which voters do not need to trust any third party other than themselves for ballot secrecy. QV-net is self-tallying with maximal ballot secrecy. Self-tallying allows anyone to compute election results once all ballots are cast. Maximal ballot secrecy ensures that what each voter learns from QV-net is nothing more than the tally and their own ballot. We provide an open-source implementation of QV-net to demonstrate its practicality based on real-world DAO voting settings, reporting only a few milliseconds for voting and a maximum of 255 milliseconds for tallying.

The exceptional efficiency of QV-net is attributed to the design of two new Zero-Knowledge Argument of Knowledge (ZKAoK) protocols for QV ballot secrecy and integrity. Previous works generally rely on pairing-friendly curves to prove the well-formedness of an encrypted QV ballot. But they incur heavy computation and large data sizes. We tackle the challenges of appropriately formalizing and proving ZKAoK relations for QV without using these curves. Specifically, we develop a succinct ZKAoK to prove a new relation: the sum of squares of a private vector's components equals a private scalar. We also introduce the first aggregated range proof to prove that values committed under different keys fall within their respective ranges. Together, these two new zero-knowledge protocols enable us to build an efficient decentralized QV scheme and are of independent interest.



## 2025/1147

* Title: Jigsaw: Doubly Private Smart Contracts
* Authors: Sanjam Garg, Aarushi Goel, Dimitris Kolonelos, Rohit Sinha
* [Permalink](https://eprint.iacr.org/2025/1147)
* [Download](https://eprint.iacr.org/2025/1147.pdf)

### Abstract

Privacy is a growing concern for smart contracts on public ledgers.
In recent years, we have seen several practical systems for privacy-preserving smart contracts, but they only target privacy of on-chain data, and rely on trusted off-chain parties with user data -- for instance, a decentralized finance application (e.g. exchange) relies on an off-chain matching engine to process client orders that get settled on-chain, where privacy only applies to the on-chain data.
Privacy conscious users demand stronger notions of privacy, for their identity and their data, from all other parties in the ecosystem.

We propose a novel framework for smart contracts that ensures {\em doubly private}
execution, addressing {both on-chain and off-chain privacy} requirements.
In our framework, clients submit their requests in a privacy-preserving manner to a group of (potentially mutually untrusting) servers. These servers collaboratively match client requests without learning any information about the data or identities of the clients.

We then present {\em Jigsaw}, an efficient cryptographic realization of our proposed framework. {\em Jigsaw} builds on the ZEXE architecture (Bowe et al., S\&P 2020), which leverages zkSNARKs, and extends Collaborative zkSNARKs (Ozdemir and Boneh, USENIX 2022) to enable proof generation by a group of servers.

In Jigsaw, we introduce a novel collaborative zkSNARK construction that achieves low latency and reduced proving time, and showcase these advantages over sample applications ranging from trading in a decentralized exchange to auctions and voting.
Our experiments demonstrate that {\em Jigsaw} is roughly $40-50$x faster in proof generation and uses orders-of-magnitude less bandwidth than the naive approach of using off-the-shelf Collaborative zkSNARKs.



## 2025/1148

* Title: On the Composition of Single-Keyed Tweakable Even-Mansour for Achieving BBB Security
* Authors: Avik Chakraborti, Mridul Nandi, Suprita Talnikar, Kan Yasuda
* [Permalink](https://eprint.iacr.org/2025/1148)
* [Download](https://eprint.iacr.org/2025/1148.pdf)

### Abstract

Observing the growing popularity of random permutation (RP)-based designs (e.g, Sponge), Bart Mennink in CRYPTO 2019 has initiated an interesting research in the direction of RP-based pseudorandom functions (PRFs). Both are claimed to achieve beyond-the-birthday-bound  (BBB) security of $2n/3$ bits ($n$ being the input block size in bits) but require two instances of RPs and can handle only one-block inputs. In this work, we extend research in this direction by providing two new BBB-secure constructions by composing the tweakable Even-Mansour appropriately.  Our first construction requires only one instance of an RP and requires only one key.  Our second construction extends the first to a nonce-based  Message Authentication Code (MAC) using a universal hash to deal with multi-block inputs.  We show that the hash key can be derived from the original key when the underlying hash is the Polyhash. We provide matching attacks for both constructions to demonstrate the tightness of the proven security bounds.



## 2025/1149

* Title: An Efficient Encryption Scheme Based on $(U+V, U+W)$ Codes
* Authors: Yang Yang, Fangguo Zhang
* [Permalink](https://eprint.iacr.org/2025/1149)
* [Download](https://eprint.iacr.org/2025/1149.pdf)

### Abstract

In this paper, we propose an improvement to the McEliece encryption scheme by replacing the Goppa code with a  $(U+V,U+W)$ code. Specifically, we embed the generator matrices of a split Reed-Solomon code into the generator matrix of the $(U+V,U+W)$ code. This approach disrupts the algebraic structure of Reed-Solomon codes, thereby enhancing resistance against structural attacks targeting such codes, while simultaneously preserving their excellent error-correcting capabilities. As a result, the proposed scheme achieves a significant reduction in public key size. Under the hardness assumptions of the decoding problem and the code distinguishing problem for $(U+V,U+W)$ codes, we prove that the scheme achieves indistinguishability under chosen-plaintext attacks (IND-CPA security). Finally, we provide recommended parameters for various security levels and compare the proposed scheme with other code-based public key encryption schemes.



## 2025/1150

* Title: Lightweight Sorting in Approximate Homomorphic Encryption
* Authors: Lorenzo Rovida, Alberto Leporati, Simone Basile
* [Permalink](https://eprint.iacr.org/2025/1150)
* [Download](https://eprint.iacr.org/2025/1150.pdf)

### Abstract

Sorting encrypted values is an open research problem that plays a crucial role in the broader objective of providing efficient and practical privacy-preserving online services.
The current state of the art work by Mazzone, Everts, Hahn and Peter (USENIX Security '25) proposes efficient algorithms for ranking, indexing and sorting based on the CKKS scheme, which deviates from the compare-and-swap paradigm, typically used by sorting networks, using a permutation-based approach. This allows to build shallow sorting circuits in a very simple way.
In this work, we follow up their work and explore different approaches to approximate the nonlinear functions required by the encrypted circuit (where only additions and multiplications can be evaluated), and we propose simpler solutions that allow for faster computations and smaller memory requirements.

In particular, we drastically reduce the upper bound on the depth of the circuits from 65 to 20, making our circuits usable in relatively small rings such as $N=2^{16}$, even for sorting values while preserving up to three decimal places. As an example, our circuit sorts 128 values with duplicates in roughly 20 seconds on a laptop, using roughly 1 GB of memory, maintaining a precision of 0.01.
Furthermore, we propose an implementation of a swap-based bitonic network that is not based on approximations of the sgn$(x)$ function, which scales linearly with the number of values, useful when the number of available slots is small.



## 2025/1151

* Title: Faster signature verification with 3-dimensional decomposition
* Authors: Vojtech Suchanek, Marek Sys, Lukasz Chmielewski
* [Permalink](https://eprint.iacr.org/2025/1151)
* [Download](https://eprint.iacr.org/2025/1151.pdf)

### Abstract

We introduce a novel technique for verifying Schnorr signatures using fast endomorphisms. Traditionally, fast endomorphisms over prime field curves are used to decompose a scalar into two scalars of half of the size. This work shows that the context of the verification of signatures allows for the decomposition into three scalars of a third of the size. We apply our technique to three scenarios: verification of a single Schnorr signature, batch verification, and verification of BLS signatures within the Blind Diffie-Hellman key exchange protocol. Our experiments on AMD x86 and ARM Cortex-M4 platforms show performance improvements of approximately 20%, 13%, and 27%, respectively. The technique can also be used to accelerate the verification of ECDSA signatures, provided that one additional bit of information is appended to the signature.

As part of our work, we analyze the performance of 3-dimensional lattice reduction algorithms, which are critical for multi-scalar decompositions. To identify the most efficient approach, we experimentally compare Semaev’s algorithm --- known for its best asymptotic complexity --- with the simpler Lagrange’s algorithm. Our results reveal that, despite its simplicity, Lagrange’s algorithm is nearly twice as fast as Semaev’s in practice.



## 2025/1152

* Title: ZK-ProVer: Proving Programming Verification in Non-Interactive Zero-Knowledge Proofs
* Authors: Haoyu Wei, Jingyu Ke, Ruibang Liu, Guoqiang Li
* [Permalink](https://eprint.iacr.org/2025/1152)
* [Download](https://eprint.iacr.org/2025/1152.pdf)

### Abstract

Program verification ensures software correctness through formal methods but incurs substantial computational overhead. It typically encodes program execution into formulas that are verified using a SAT solver and its extensions. However, this process exposes sensitive program details and requires redundant computations when multiple parties need to verify correctness. To overcome these limitations, zero-knowledge proofs (ZKPs) generate compact, reusable proofs with fast verification times, while provably hiding the program’s internal logic. We propose a two-phase zero-knowledge protocol that hides program implementation details throughout verification. Phase I uses a zero-knowledge virtual machine (zkVM) to encode programs into SAT formulas without
revealing their semantics. Phase II employs the encoding of resolution proofs for UNSAT instances and circuits for satisfying assignment verification for SAT instances through PLONKish circuits. Evaluation on the Boolector benchmark demonstrates that our method achieves verification time that is efficient and is independent of clause width for UNSAT instances and formula size for SAT instances. The resulting ZKPs enable efficient verification of program properties while providing strong end-to-end privacy guarantees.



## 2025/1153

* Title: Privacy-aware White and Black List Searching for Fraud Analysis
* Authors: William J Buchanan, Jamie Gilchrist, Zakwan Jaroucheh, Dmitri Timosenko, Nanik Ramchandani, Hisham Ali
* [Permalink](https://eprint.iacr.org/2025/1153)
* [Download](https://eprint.iacr.org/2025/1153.pdf)

### Abstract

In many areas of cybersecurity, we require access to Personally Identifiable Information (PII), such as names, postal addresses and email addresses. Unfortunately, this can lead to data breaches, especially in relation to data compliance regulations such as GDPR. An Internet Protocol (IP) address is an identifier that is assigned to a networked device to enable it to communicate over networks that use IP. Thus, in applications which are privacy-aware, we may aim to hide the IP address while aiming to determine if the address comes from a blacklist. One solution to this is to use homomorphic encryption to match an encrypted version of an IP address to a blacklisted network list. This matching allows us to encrypt the IP address and match it to an encrypted version of a blacklist. In this paper, we use the OpenFHE library \cite{OpenFHE} to encrypt network addresses with the BFV homomorphic encryption scheme. In order to assess the performance overhead of BFV, we implement a matching method using the OpenFHE library and compare it against partial homomorphic schemes, including Paillier, Damgard-Jurik, Okamoto-Uchiyama, Naccache-Stern and Benaloh. The main findings are that the BFV method compares favourably against the partial homomorphic methods in most cases.



## 2025/1154

* Title: Evaluation of Modular Polynomials from Supersingular Elliptic Curves
* Authors: Maria Corte-Real Santos, Jonathan Komada Eriksen, Antonin Leroux, Michael Meyer, Lorenz Panny
* [Permalink](https://eprint.iacr.org/2025/1154)
* [Download](https://eprint.iacr.org/2025/1154.pdf)

### Abstract

We present several new algorithms to evaluate modular polynomials of level $\ell$ modulo a prime $p$ on an input $j$.
    More precisely, we introduce two new generic algorithms, sharing the following similarities: they are based on a CRT approach; they make use of supersingular curves and the Deuring correspondence; and, their memory requirements are optimal.

    The first algorithm combines the ideas behind a hybrid algorithm of Sutherland in 2013 with a recent algorithm to compute modular polynomials using supersingular curves introduced in 2023 by Leroux. The complexity (holding around several plausible heuristic assumptions) of the resulting algorithm matches the $O(\ell^3 \log^{3} \ell + \ell \log p)$ time complexity of the best known algorithm by Sutherland, but has an optimal memory requirement.   
   
    Our second algorithm is based on a sub-algorithm that can evaluate modular polynomials efficiently on supersingular $j$-invariants defined over $\mathbb{F}_p$, and achieves heuristic complexity quadratic in both $\ell$ and $\log j$, and linear in $\log p$. In particular, it is the first generic algorithm with optimal memory requirement to obtain a quadratic complexity in~$\ell$.
   
    Additionally, we show how to adapt our method to the computation of other types of modular polynomials such as the one stemming from Weber's function. 
   
    Finally, we provide an optimised implementation of the two algorithms detailed in this paper, though we emphasise that various modules in our codebase
    may find applications outside their use in this paper.



## 2025/1155

* Title: On the Security of Group Ring Learning with Errors
* Authors: Andrew Mendelsohn, Charles Grover, Cong Ling
* [Permalink](https://eprint.iacr.org/2025/1155)
* [Download](https://eprint.iacr.org/2025/1155.pdf)

### Abstract

We propose a dimension-reducing transformation on Group Ring Learning with Errors (GRLWE) samples. We exhibit an efficiently computable isomorphism which takes samples defined over the group rings used in the construction of GRLWE to twice as many samples defined over matrix rings, in half the dimension. This is done by composing two maps: the first map is a transformation showing that the group rings used are orders in central simple algebras, and the second map takes the obtained central simple algebra to a matrix ring. When combined with lattice reduction on the resulting matrix samples, this gives an attack on the GRLWE problem. We extend this attack to other groups proposed for cryptographic use by the creators of GRLWE, and display some numerical results quantifying the effects of the transformation, using the `Lattice Estimator'.. We then give a family of groups from which GRLWE-style group rings can be constructed which are immune to our attack, namely the generalized quaternion groups. Finally, we discuss the merits and vulnerabilities of a number of different forms of structured LWE.



## 2025/1156

* Title: An efficient construction of Raz's two-source randomness extractor with improved parameters
* Authors: Cameron Foreman, Lewis Wooltorton, Kevin Milner, Florian J. Curchod
* [Permalink](https://eprint.iacr.org/2025/1156)
* [Download](https://eprint.iacr.org/2025/1156.pdf)

### Abstract

Randomness extractors are algorithms that distill weak random sources into near-perfect random numbers. Two-source extractors enable this distillation process by combining two independent weak random sources. Raz’s extractor (STOC '05) was the first to achieve this in a setting where one source has linear min-entropy (i.e., proportional to its length), while the other has only logarithmic min-entropy in its length. However, Raz's original construction is impractical due to a polynomial computation time of at least degree 4. Our work solves this problem by presenting an improved version of Raz's extractor with quasi-linear computation time, as well as a new analytic theorem with reduced entropy requirements. We provide comprehensive analytical and numerical comparisons of our construction with others in the literature, and we derive strong and quantum-proof versions of our efficient Raz extractor. Additionally, we offer an easy-to-use, open-source code implementation of the extractor and a numerical parameter calculation module.



## 2025/1157

* Title: General Multi-Prime Multi-Power RSA - A Generalization of RSA and CRT-RSA to Regular Integers Modulo $n$
* Authors: Klaus Dohmen, Mandy Lange-Geisler
* [Permalink](https://eprint.iacr.org/2025/1157)
* [Download](https://eprint.iacr.org/2025/1157.pdf)

### Abstract

Based on a sharpening of Carmichael’s theorem and Euler’s theorem we generalize RSA and CRT-RSA to arbitrary integer moduli $n > 1$, while restricting messages to integers $m$ which are regular modulo $n$, meaning that they have a John-von-Neumann pseudoinverse modulo $n$. We prove the correctness and completeness of our encryption and decryption method for this class of messages, and show that the restriction to regular integers is negligible, since under reasonable assumptions almost all integers are regular modulo $n$.



## 2025/1158

* Title: Bridging Bitcoin to Second Layers via BitVM2
* Authors: Robin Linus, Lukas Aumayr, Zeta Avarikioti, Matteo Maffei, Andrea Pelosi, Orfeas Thyfronitis Litos, Christos Stefo, David Tse, Alexei Zamyatin
* [Permalink](https://eprint.iacr.org/2025/1158)
* [Download](https://eprint.iacr.org/2025/1158.pdf)

### Abstract

A holy grail in blockchain infrastructure is a trustless bridge between Bitcoin and its second layers or other chains. We make progress toward this vision by introducing the first light-client based Bitcoin bridge. At the heart of its design lies BitVM2-core, a novel paradigm that enables arbitrary program execution on Bitcoin, combining Turing-complete expressiveness with the security of Bitcoin consensus. BitVM2-bridge advances prior approaches by reducing the trust assumption from an honest majority (t-of-n) to existential honesty (1-of-n) during setup. Liveness is guaranteed with only one rational operator, and any user can act as a challenger, enabling permissionless verification.. A production-level implementation of BitVM2 has been developed and a full challenge verification has been executed on the Bitcoin mainnet.



## 2025/1159

* Title: $\mathsf{DekartProof}$: Efficient Vector Range Proofs and Their Applications
* Authors: Dan Boneh, Trisha Datta, Rex Fernando, Kamilla Nazirkhanova, Alin Tomescu
* [Permalink](https://eprint.iacr.org/2025/1159)
* [Download](https://eprint.iacr.org/2025/1159.pdf)

### Abstract

Let $p$ be a prime and consider a committed vector $\vec{v} = (v_1, \ldots, v_m) \in \mathbb{F}_p^m$.
We develop new techniques for succinctly proving in zero-knowledge that all the elements of $\vec{v}$ are in the range $\{0,1,\ldots,n\}$ for some $n<p$.
We refer to this as a batched zero-knowledge range proof, or a batched ZKRP.
This problem comes up often in cryptography: it is needed in publicly verifiable secret sharing (PVSS), confidential transactions, and election protocols.
Our approach makes use of a multilinear polynomial commitment scheme and the sum check protocol to efficiently provide a batch range proof for the entire vector.
Along the way we introduce a new type of a Polynomial Interactive Oracle Proof (PIOP) we call a Homomorphic PIOP that can be compiled into a SNARK.
We use an HPIOP to construct a new efficient zero-knowledge version of the sum check protocol. 
We compare our new techniques with existing range proofs and lookup arguments.



## 2025/1160

* Title: Black-box Approaches to Authenticated Dictionaries: New Constructions and Lower Bounds
* Authors: Francesca Falzon, Harjasleen Malvai, Emanuel Opel
* [Permalink](https://eprint.iacr.org/2025/1160)
* [Download](https://eprint.iacr.org/2025/1160.pdf)

### Abstract

Authenticated dictionaries (ADs) enable secure lookups to a dictionary hosted by an untrusted server and are a key component of various real-world applications, including transparency systems and cryptocurrencies. Despite significant overlap in techniques for building ADs and related primitives, such as memory checkers and accumulators (i.e., authenticated sets), these relationships have yet to be formalized.

In this work, we give a rigorous treatment of ADs and prove their precise connection to the latter two cornerstone primitives. We start by laying out the minimal algorithms and security properties needed in practice and introduce a new security notion for ADs called write-committing, which requires update proofs to guarantee an exact count of changes.

We prove that any AD built from a black-box authenticated set (AS) makes at least $\Omega(\log n)$ AS calls per lookup and obeys a trade-off between lookups and updates. With optimal lookups, such a scheme requires at least $\Omega(\log n/\log\log n)$ AS calls per update.
We also resolve the open question of constructing a secure AD from only black-box access to an AS and present two schemes adhering to the trade-off: one with optimal lookup overhead and the other with higher lookup complexity, but which only requires two AS calls for an update.

Finally, we make strides towards unifying memory checkers and ADs. To this end, we present two constructions for memory checkers with black-box access to an AD: one that incurs constant overhead (but needs write-committing) and a second that only requires the AD to be lookup-secure but incurs logarithmic overhead. We then give a simple AD construction using a memory checker as a black-box, with $\mathcal{O}(1)$ overhead.

Our results demonstrate the inherent limitations of ADs built from accumulators but lay the foundation for extending existing results on memory checkers and other primitives, such as vector commitments, to ADs.



## 2025/1161

* Title: High-Performance FPGA Accelerator for the Post-quantum Signature Scheme CROSS
* Authors: Patrick Karl, Francesco Antognazza, Alessandro Barenghi, Gerardo Pelosi, Georg Sigl
* [Permalink](https://eprint.iacr.org/2025/1161)
* [Download](https://eprint.iacr.org/2025/1161.pdf)

### Abstract

A significant effort in designing and engineering post-quantum cryptosystems is currently ongoing, also as a result of the National Institute of Standards and Technology (NIST) Post-quantum Cryptography (PQC) standardization process that started in 2016 and recently completed selecting two Key Encapsulation Mechanisms (KEMs), CRYSTALS-Kyber and HQC, and three digital signatures CRYSTALS-Dilithium, Falcon, and SPHINCS+ for standardization. In 2022, NIST launched another standardization effort for additional post-quantum digital signatures, preferably not based on the security assumptions of structured lattices, and with performance better than or equal to that of already standardized schemes (e.g., SPHINCS+ ). This initiative has narrowed down the initial 40 candidates to 14 in October 2024, eliciting public scrutiny of their algorithms and technical evaluation of their performance figures. Among the schemes admitted to the second round of  evaluation, the code-based CROSS signature scheme was praised for its speed and the noticeably smaller signature sizes over the standardized version of SPHINCS+ . In this work, we present the first RTL hardware design of CROSS tailored for FPGA devices, delineating efficient implementation strategies for the critical components of the cryptographic scheme. Depending on the chosen security level, our design generates a key pair in 9 to 152 µs, signs a message in 404 µs to 5.89 ms, and verifies a signature in 322 µs to 4.38 ms on the NIST reference FPGA, a Xilinx Artix-7 device, proving competitive when compared with other candidates in the on-ramp standardization effort, namely LESS, MEDS, MAYO, Raccoon and SDitH, and comparable to current standard-selected ML-DSA, FN-DSA, and SLH-DSA in terms of efficiency.



## 2025/1162

* Title: SV-LLM: An Agentic Approach for SoC Security Verification using Large Language Models
* Authors: Dipayan Saha, Shams Tarek, Hasan Al Shaikh, Khan Thamid Hasan, Pavan Sai Nalluri, Md. Ajoad Hasan, Nashmin Alam, Jingbo Zhou, Sujan Kumar Saha, Mark Tehranipoor, Farimah Farahmandi
* [Permalink](https://eprint.iacr.org/2025/1162)
* [Download](https://eprint.iacr.org/2025/1162.pdf)

### Abstract

Ensuring the security of complex system-on-chips (SoCs) designs is a critical imperative, yet traditional verification techniques struggle to keep pace due to significant challenges in automation, scalability, comprehensiveness, and adaptability. The advent of large language models (LLMs), with their remarkable capabilities in natural language understanding, code generation, and advanced reasoning, presents a new paradigm for tackling these issues. Moving beyond monolithic models, an agentic approach allows for the creation of multi-agent systems where specialized LLMs collaborate to solve complex problems more effectively. Recognizing this opportunity, we introduce SV-LLM, a novel multi-agent assistant system designed to automate and enhance SoC security verification. By integrating specialized agents for tasks like verification question answering, security asset identification, threat modeling, test plan and property generation, vulnerability detection, and simulation-based bug validation, SV-LLM streamlines the workflow. To optimize their performance in these diverse tasks, agents leverage different learning paradigms, such as in-context learning, fine-tuning, and retrieval-augmented generation (RAG). The system aims to reduce manual intervention, improve accuracy, and accelerate security analysis, supporting proactive identification and mitigation of risks early in the design cycle. We demonstrate its potential to transform hardware security practices through illustrative case studies and experiments that showcase its applicability and efficacy.



## 2025/1163

* Title: Efficient, Scalable Threshold ML-DSA Signatures: An MPC Approach
* Authors: Alexander Bienstock, Leo de Castro, Daniel Escudero, Antigoni Polychroniadou, Akira Takahashi
* [Permalink](https://eprint.iacr.org/2025/1163)
* [Download](https://eprint.iacr.org/2025/1163.pdf)

### Abstract

A threshold signature is an advanced protocol that splits a secret signing key among multiple parties, allowing any subset above a threshold to jointly generate a signature. While post-quantum (PQ) threshold signatures are actively being studied --- especially in response to NIST's recent call for threshold schemes --- most existing solutions are tailored to specially designed, threshold-friendly signature schemes. In contrast, many real-world applications, such as distributed certificate authorities and digital currencies, require signatures that remain verifiable under the standardized verification procedures already in use. Given NIST's recent standardization of PQ signatures and ongoing industry deployment efforts, designing an efficient threshold scheme that interoperates with NIST-standardized verification remains a critical open problem.

In this work, we present the first efficient and scalable solution for multi-party generation of the module-lattice digital signature algorithm (ML-DSA), one of NIST's PQ signature standards. Our contributions are two-fold. First, we present a variant of the ML-DSA signing algorithm that is amenable to efficient multi-party computation (MPC) and prove that this variant achieves the same security as the original ML-DSA scheme. Second, we present several efficient & scalable MPC protocols to instantiate the threshold signing functionality. Our protocols can produce threshold signatures with as little as 100 KB (per party) of online communication per rejection-sampling round. In addition, we instantiate our protocols in the honest-majority setting, which allows us to avoid any additional public key assumptions.

The signatures produced by our protocols verify under the same implementation of ML-DSA verification for all three security levels. Thus, signatures and verification keys of our scheme are (naturally) the same size as that of ML-DSA; previous lattice-based threshold schemes could not match both of these sizes. Overall, our solution is the only method for producing threshold ML-DSA signatures compatible with NIST-standardized verification that scales to an arbitrary number of parties, without any new assumptions.



## 2025/1164

* Title: Man-in-the-Middle and Key Recovery Attacks against QP-KEM
* Authors: Nick Aquina, Simon Rommel, Idelfonso Tafur Monroy
* [Permalink](https://eprint.iacr.org/2025/1164)
* [Download](https://eprint.iacr.org/2025/1164.pdf)

### Abstract

The Q-problem has been introduced as a new post-quantum hard problem. We present two man-in-the-middle and three key recovery attacks against the key exchange protocol based on the Q-problem. The man-in-the-middle attacks take negligible time and allow the attacker to recover the exchanged key. The most effective key recovery attack has a computational complexity of $2^{40}$. We also propose countermeasures against all attacks.



## 2025/1165

* Title: Automated Analysis and Synthesis of Message Authentication Codes
* Authors: Stefan Milius, Dominik Paulus, Dominique Schröder, Lutz Schröder, Julian Thomas
* [Permalink](https://eprint.iacr.org/2025/1165)
* [Download](https://eprint.iacr.org/2025/1165.pdf)

### Abstract

Message Authentication Codes (MACs) represent a fundamental symmetric key primitive, serving to ensure the authenticity and integrity of transmitted data.
As a building block in authenticated encryption and in numerous deployed standards, including TLS, IPsec, and SSH, MACs play a central role in practice.
Due to their importance for practice, MACs have been subject to extensive research, leading to prominent schemes such as HMAC, CBCMAC, or LightMAC.
Despite the existence of various MACs, there is still considerable interest in creating schemes that are more efficient, potentially parallelizable, or have specific non-cryptographic attributes, such as being patent-free.

In this context, we introduce an automated method for analyzing and synthesizing MAC schemes.
In order to achieve this goal, we have constructed a framework that restricts the class of MACs in such a way that it is sufficiently expressive to cover known constructions, yet also admits automated reasoning about the security guarantees of both known and new schemes.
Our automated analysis has identified a novel category of MACs, termed "hybrid" MACs. These MACs operate by processing multiple blocks concurrently, with each block managed by a different, specified MAC scheme. A key finding is that in certain scenarios, the hybrid MAC marginally outperforms the simultaneous operation of the individual MACs. This improvement is attributed to the hybrid approach exploiting the strengths and compensating for the weaknesses of each distinct MAC scheme involved.
Our implementation confirms that we have successfully identified new schemes that have comparable performance with state-of-the-art schemes and in some settings seem to be slightly more efficient.



## 2025/1166

* Title: Threshold Signatures Reloaded: ML-DSA and Enhanced Raccoon with Identifiable Aborts
* Authors: Giacomo Borin, Sofía Celi, Rafael del Pino, Thomas Espitau, Guilhem Niot, Thomas Prest
* [Permalink](https://eprint.iacr.org/2025/1166)
* [Download](https://eprint.iacr.org/2025/1166.pdf)

### Abstract

Threshold signatures enable multiple participants to collaboratively produce a digital signature, ensuring both fault tolerance and decentralization. As we transition to the post-quantum era, lattice-based threshold constructions have emerged as promising candidates. However, existing approaches often struggle to scale efficiently, lack robustness guarantees, or are incompatible with standard schemes — most notably, the NIST-standard ML-DSA.
In this work, we explore the design space of Fiat-Shamir-based lattice threshold signatures and introduce the two most practical schemes to date. First, we present an enhanced TRaccoon-based [DKM+24] construction that supports up to 64 participants with identifiable aborts, leveraging novel short secret-sharing techniques to achieve greater scalability than previous state-of-the-art methods. Second — and most importantly — we propose the first practical ML-DSA-compatible threshold signature scheme, supporting up to 6 users.
We provide full implementations and benchmarks of our schemes, demonstrating their practicality and efficiency for real-world deployment as protocol messages are computed in at most a few milliseconds, and communication cost ranges from 10.5 kB to 525 kB depending on the threshold.



## 2025/1167

* Title: Security Analysis on a Public-Key Inverted-Index Keyword Search Scheme with Designated Tester
* Authors: Mizuki Hayashi, Keita Emura
* [Permalink](https://eprint.iacr.org/2025/1167)
* [Download](https://eprint.iacr.org/2025/1167.pdf)

### Abstract

Gao et al. (IEEE Internet of Things Journal 2024) proposed public-key inverted-index keyword search with designated tester as an extension of public key encryption with keyword search (PEKS). In their scheme, a server (a tester) has a secret key and uses the key for running the search algorithm due to the designated tester setting. They proved that no information of keyword is revealed from trapdoors under the decisional Diffie-Hellman (DDH) assumption. However, they also employed a symmetric pairing which can be seen as a DDH-solver.. Thus, it is expected that information of keyword is revealed from trapdoors since the underlying complexity assumption does not hold. In this paper, we demonstrate two attacks against the Gao et al.'s scheme where information of keyword is revealed from a trapdoor. The first attack completes by using only the server's secret key in addition to the challenge trapdoor, without any additional encryption/trapdoor queries. We remark that an adversary is not allowed to obtain the server's secret key in their security model, and our attack is outside of their security model. Thus, we discuss the roles of the server, and stress that our attack scenario is reasonable. The second attack does not employ the server's secret key and utilizes linkability of two trapdoors.  In both attacks, the attack complexity is just two pairing computations and is feasible in terms of the computational cost.



## 2025/1168

* Title: On Frontrunning Risks in Batch-Order Fair Systems for Blockchains (Extended Version)
* Authors: Eunchan Park, Taeung Yoon, Hocheol Nam, Deepak Maram, Min Suk Kang
* [Permalink](https://eprint.iacr.org/2025/1168)
* [Download](https://eprint.iacr.org/2025/1168.pdf)

### Abstract

In timing-sensitive blockchain applications, such as decentralized finance (DeFi), achieving first-come-first-served (FCFS) transaction ordering among decentralized nodes is critical to prevent frontrunning attacks. Themis[CCS'23], a state-of-the-art decentralized FCFS ordering system, has become a key reference point for high-throughput fair ordering systems for real-world blockchain applications, such as rollup chains and decentralized sequencing, and has influenced the design of several subsequent proposals. In this paper, we critically analyze its core system property of practical batch-order fairness and evaluate the frontrunning resistance claim of Themis.  We present the Ambush attack, a new frontrunning technique that achieves nearly 100% success against the practical batch-order fair system with only a single malicious node and negligible attack costs. This attack causes a subtle temporary information asymmetry among nodes, which is allowed due to the heavily optimized communication model of the system. A fundamental trade-off we identify is a challenge in balancing security and performance in these systems; namely, enforcing timely dissemination of transaction information among nodes (to mitigate frontrunning) can easily lead to non-negligible network overheads (thus, degrading overall throughput performance). We show that it is yet possible to balance these two by delaying transaction dissemination to a certain tolerable level for frontrunning mitigation while maintaining high throughput. Our evaluation demonstrates that the proposed delayed gossiping mechanism can be seamlessly integrated into existing systems with only minimal changes.