[digest] 2025 Week 24

## In this issue

1. [2024/859] Novel approximations of elementary functions in ...
2. [2025/254] Garbled Lookup Tables from Homomorphic Secret Sharing
3. [2025/376] Another Look at the Quantum Security of the ...
4. [2025/976] The Large Block Cipher Family Vistrutah
5. [2025/1006] Adding Feeding Forward Back to the Sponge Construction
6. [2025/1068] Efficient Modular Multiplication Using Vector ...
7. [2025/1069] PRESENT Full Round Emulation : Structural Flaws and ...
8. [2025/1070] Zeus: Defending against Fee Stealing and Griefing ...
9. [2025/1071] PICS: Private Intersection over Committed (and ...
10. [2025/1072] How to Model Unitary Oracles
11. [2025/1073] LAPWN: A Lightweight User–Server Authentication ...
12. [2025/1074] Multiparty Distributed Point Functions
13. [2025/1075] Secure and Practical Cold (and Hot) Staking
14. [2025/1076] Weight reduction in distributed protocols: new ...
15. [2025/1077] Shorter VOLE-in-the-Head-based Signatures from ...
16. [2025/1078] A Theoretical Perspective on the Formal ...
17. [2025/1079] Revisiting Discrete Logarithm Reductions
18. [2025/1080] Leftover Hash Lemma(s) Over Cyclotomic Rings
19. [2025/1081] FABLE: Batched Evaluation on Confidential Lookup ...
20. [2025/1082] Treebeard: A Scalable and Fault Tolerant ORAM Datastore
21. [2025/1083] The complexity of the SupportMinors Modeling for ...
22. [2025/1084] How to (not) combine Oblivious Pseudorandom Functions
23. [2025/1085] SmallWood: Hash-Based Polynomial Commitments and ...
24. [2025/1086] Fairness in the Wild: Secure Atomic Swap with ...
25. [2025/1087] Cryptography meets worst-case complexity: Optimal ...
26. [2025/1088] Homomorphic Field Trace Revisited : Breaking the ...
27. [2025/1089] Rugged Pseudorandom Permutations with Beyond- ...
28. [2025/1090] Concrete Treatment of Signal Handshake’s ...
29. [2025/1091] Quantum Computing without the Linear Algebra
30. [2025/1092] OwlC: Compiling Security Protocols to Verified, ...
31. [2025/1093] On the Concrete Security of BBS/BBS+ Signatures
32. [2025/1094] Key Updatable Identity-Based-Signature Schemes
33. [2025/1095] Ideally HAWKward: How Not to Break Module-LIP
34. [2025/1096] CuFDFB: Fast and Private Computation on Non-Linear ...
35. [2025/1097] Oracle-Based Multistep Strategy for Solving ...
36. [2025/1098] Isogeny-based key exchange from orientations of ...
37. [2025/1099] Lattice-Based Accumulator and Application to ...
38. [2025/1100] Tanuki: New Frameworks for (Concurrently Secure) ...
39. [2025/1101] A Note on One Authentication and Key Agreement ...
40. [2025/1102] TEEMS: A Trusted Execution Environment based ...
41. [2025/1103] Universally Composable Succinct Vector Commitments ...
42. [2025/1104] Better GBFV Bootstrapping and Faster Encrypted Edit ...
43. [2025/1105] Low-cost anonymous reputation update for IoT ...
44. [2025/1106] b4M: Holistic Benchmarking for MPC
45. [2025/1107] Early Stopping is Cheap
46. [2025/1108] Laconic PSI on Authenticated Inputs and Applications
47. [2025/1109] Kahrobaei--Koupparis DSS: universal forgery
48. [2025/1110] A Framework for Compiling Custom Languages as ...
49. [2025/1111] SEAF: Secure Evaluation on Activation Functions ...
50. [2025/1112] Hydrangea: Optimistic Two-Round Partial Synchrony ...
51. [2025/1113] Computational Attestations of Polynomial Integrity ...

## 2024/859

* Title: Novel approximations of elementary functions in zero-knowledge proofs
* Authors: Kaarel August Kurik, Peeter Laud
* [Permalink](https://eprint.iacr.org/2024/859)
* [Download](https://eprint.iacr.org/2024/859.pdf)

### Abstract

In this paper, we study the computation of complex mathematical functions in statements executed on top of zero-knowledge proofs (ZKP); these functions may include roots, exponentials and logarithms, trigonometry etc. While existing approaches to these functions in privacy-preserving computations (and sometimes also in general-purpose processors) have relied on polynomial approximation, more powerful methods are available for ZKP. In this paper, we note that in ZKP, all algebraic functions are exactly computable. Recognizing that, we proceed to the approximation of transcendental functions with algebraic functions. We develop methods of approximation, instantiate them on a number of common transcendental functions, and benchmark their precision and efficiency in comparison with best polynomial approximations.



## 2025/254

* Title: Garbled Lookup Tables from Homomorphic Secret Sharing
* Authors: Liqiang Liu, Tianren Liu, Bo Peng
* [Permalink](https://eprint.iacr.org/2025/254)
* [Download](https://eprint.iacr.org/2025/254.pdf)

### Abstract

Garbled Circuit (GC) is a fundamental tool in cryptography, especially in secure multiparty computation.  Most garbling schemes follow a gate-by-gate paradigm.  The communication cost is proportional to the circuit size times the security parameter $\lambda$.

Recently, Heath, Kolesnikov and Ng (Eurocrypt 2024) partially transcend the circuit size barrier by considering large gates.  To garble an arbitrary $n$-input $m$-output gate, their scheme requires $O(nm\lambda) + 2^nm$ bits of communication.  The security relies on circular correlation robust hash functions (CCRH).

We further improve the communication cost to $O(n \lambda_{\sf DCR} + m\lambda)$, removing the exponential term.  The computation cost is $O(2^n (\lambda_{\sf DCR})^2)$, dominated by $O(2^nn)$ exponentiations. Our construction is built upon recent progress in DCR-based Homomorphic Secret Sharing (HSS), so it additionally relies on the decisional composite residuosity (DCR) assumption.

As an intermediate step, we construct programmable distributed point functions with decomposable keys, relying on the DCR assumption.  Previously, such primitive can only be constructed from multilinear maps or sub-exponential lattice assumptions.



## 2025/376

* Title: Another Look at the Quantum Security of the Vectorization Problem with Shifted Inputs
* Authors: Paul Frixons, Valerie Gilchrist, Péter Kutas, Simon-Philipp Merz, Christophe Petit
* [Permalink](https://eprint.iacr.org/2025/376)
* [Download](https://eprint.iacr.org/2025/376.pdf)

### Abstract

Cryptographic group actions provide a basis for simple post-quantum generalizations of many cryptographic protocols based on the discrete logarithm problem (DLP). However, many advanced group action-based protocols do not solely rely on the core group action problem (the so-called vectorization problem), but also on variants of this problem, to either improve efficiency or enable new functionalities. In particular, the security of the CSI-SharK threshold signature protocol relies on the hardness of the Vectorization Problem with Shifted Inputs where (in DLP formalism) the adversary not only receives $g$ and $g^x$, but also $g^{x^c}$ for multiple known values of $c$. A natural open question is whether the extra data provided to the adversary in this variant allows them to solve the underlying problem more efficiently.
    In this paper, we revisit the concrete quantum security of this problem. We start from a quantum multiple hidden shift algorithm of Childs and van Dam, which to the best of our knowledge was never applied in cryptography before.. We specify algorithms for its subroutines and we provide concrete complexity estimates for both these subroutines and the overall algorithm.
    We apply our analysis to the CSI-SharK protocol. In prior analyses based on Kuperberg's algorithms, group action evaluations contributed to a significant part of the overall T-gate cost. For CSI-SharK suggested parameters, our new approach requires significantly fewer calls to the group action evaluation subroutine, leading to  significant complexity improvements overall. We describe two instances of our approach, one which lowers the T-gate complexity, and the other the QRAM requirements. We obtain significant speedups -- even in both metrics simultaneously -- and we quantify the degradation of the quantum security of the protocol when the number of curves in the public key increases.



## 2025/976

* Title: The Large Block Cipher Family Vistrutah
* Authors: Roberto Avanzi, Bishwajit Chakraborty, Eik List
* [Permalink](https://eprint.iacr.org/2025/976)
* [Download](https://eprint.iacr.org/2025/976.pdf)

### Abstract

Vistrutah is a large block cipher with block sizes of 256 and 512 bits. It iterates a step function that applies two AES rounds to each 128-bit block of the state, followed by a state-wide cell permutation. Like Simpira, Haraka, Pholkos, and ASURA, Vistrutah leverages AES instructions to achieve high performance.

For each component of Vistrutah, we conduct a systematic evaluation of functions that can be efficiently implemented on both Intel and Arm architectures. We therefore expect them to perform efficiently on any recent vector instruction set architecture (ISA) with AES support. Our evaluation methodology combines latency estimation on an abstracted vector ISA with security analysis. The goal is to maximize the ratio
of "bits of security per unit of time", i.e., to achieve the highest security for a given performance target, or equivalently, the best performance for a given security level within this class of designs. Implementations confirm the accuracy of our latency model. Vistrutah even performs significantly better than Rijndael-256-256.

We support our security claims with a comprehensive ad-hoc cryptanalysis. An isomorphism between Vistrutah-512, the 512-bit wide variant, and the AES, allows us to also leverage the extensive cryptanalysis of AES and apply it to Vistrutah-512.

A core design principle is the use of an inline key schedule: all round keys are computed during each encryption or decryption operation without requiring memory storage. In fact, rekeying has no associated overheads. Key schedules like the AES’s must precompute and store round keys in memory for acceptable performance. However, in 2010 Kamal and Youssef showed this makes cold boot attacks more effective. Vistrutah’s approach minimizes leakage to at most one value during context switches. Furthermore, expensive key schedules reduce key agility, limiting the design of modes of operation.

Vistrutah is particularly well-suited for Birthday-Bound modes of operation, including Synthetic IV modes and Accordion modes for 256-bit block ciphers. It can serve as a building block for compression functions (such as Matyas-Meyer-Oseas) in wide Merkle-Damgard hash functions. Additionally, it can implement "ZIP" wide pseudo-random functions as recently proposed by Florez-Gutierrez et al. in 2024.

Finally, we present short, i.e., reduced-round versions of Vistrutah which are analyzed taking into account the restrictions posed on attackers by specific modes of operation. In particular, we model the use of the block ciphers in Hash-Encrypt-Hash (HEH) constructions such as HCTR2 as well as in ForkCiphers. These short versions of Vistrutah can be used to accelerate modes of operation without sacrificing security.



## 2025/1006

* Title: Adding Feeding Forward Back to the Sponge Construction
* Authors: Chun Guo, Kai Hu, Yanhong Fan, Yong Fu, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2025/1006)
* [Download](https://eprint.iacr.org/2025/1006.pdf)

### Abstract

Avoiding feeding forward seems to be a major goal of the sponge construction. We make a step back and investigate adding feeding forward back to sponge. The obtained sponge-with-feeding-forward construction has a number of benefits: (1) In the random permutation model, its preimage and second preimage security bounds are much better than the standard sponge with the same capacity, while collision and indifferentiability security bounds are comparable; (2) Its collision and (second) preimage security can be reduced to well-defined properties of the underlying permutation, i.e., correlation intractability w.r.t.. certain family of evasive relations.



We further incorporate several somewhat new ideas to form detailed hash and XOF constructions SpongeFwd: (1) Feeding-forward is only applied to the capacity part, and the final output(s) is the capacity part (with the rate part discarded). In this way, when $c$ equals the primary hash output size $h$, a single permutation-call suffices for squeezing. This also simplifies the underlying evasive relations for the reduction security proof. (2) We replace the hash IV with the first message block to have the best possible efficiency. (3) We employ a parallel structure to define an XOF variant. (4) We use HAIFI-style counter inputs to achieve both length-independent second-preimage security and domain separation for XOF.

The better (second) preimage security enables constructing 512-bit output hash function from Keccak-p[800]: with 512-bit capacity, its collision and (second) preimage security bounds are the same as the standard SHA-3-512, while its hardware area is reduced by roughly 38% (according to our preliminary estimation).



## 2025/1068

* Title: Efficient Modular Multiplication Using Vector Instructions on Commodity Hardware
* Authors: Simon Langowski, Srini Devadas
* [Permalink](https://eprint.iacr.org/2025/1068)
* [Download](https://eprint.iacr.org/2025/1068.pdf)

### Abstract

Modular arithmetic is the computational backbone of many cryptographic and scientific algorithms. 
In particular, modular multiplication in a large prime field is computationally expensive and dictates the runtime of many algorithms. While it is relatively easy to utilize vectorization to accelerate batches of independent modular multiplications, our goal is to reduce the latency of a $\textit{single}$ modular multiplication under a generic prime using vectorization, while maintaining constant-time execution.

We investigate the technique of Residue Number System (RNS) Montgomery modular multiplication. We first contribute a unified view of algorithmic optimizations in prior art. This view enables us to further reduce the number of elementwise multiplications in an algorithm with a simplified structure that we prove correct.

We explore AVX512 acceleration on CPUs, and show how to map our algorithm to vector instructions. We implement our algorithm in C++ and achieve $\approx 4 \times$ speedup, which is nearly maximal, for $1024+$-bit primes on a CPU with AVX512 over optimized library implementations of standard Montgomery modular multiplication algorithms. GPUs contain vector cores that each support tens of physical threads. We show how to intelligently map our algorithm to threads in a vector core, ``overparallelizing'' to minimize latency. We show substantial speedups over a commercial library implementation of standard modular multiplication algorithms across a wide range of prime sizes.



## 2025/1069

* Title: PRESENT Full Round Emulation : Structural Flaws and Predictable Outputs
* Authors: Gopal Singh
* [Permalink](https://eprint.iacr.org/2025/1069)
* [Download](https://eprint.iacr.org/2025/1069.pdf)

### Abstract

The Internet of Things (IoT) has become integral to modern life, enabling smart cities, healthcare, and industrial automation. However, the increasing connectivity of IoT devices exposes them to various cyber threats, necessitating robust encryption methods. The PRESENT cipher, a lightweight block cipher, is well-suited for resource-constrained IoT environments, offering strong security with minimal computational overhead. This paper explores the application of deep learning (DL) techniques in cryptanalysis, specifically using an Aggregated Perceptron Group (APG) Model, which employs a Multi-Layer Perceptron (MLP) to predict input-output relations for each round of the PRESENT cipher’s encryption, excluding the key. This approach focuses solely on emulating the cipher's Substitution Permutation Network (SPN), capturing its essential structure and revealing the structural flaws in the way data is transformed through rounds. The models are chained together to generate the final ciphertext for any 64-bit plaintext with high accuracy, reducing the probability form a random guess of $2^{64}$. The results demonstrate the potential of DL models in cryptanalysis, providing insights into the security of lightweight ciphers in IoT communications and highlighting the practicality of deep learning for cryptographic analysis on standard computing systems.



## 2025/1070

* Title: Zeus: Defending against Fee Stealing and Griefing Attacks in Multi-Hop Payments
* Authors: JIngyu Liu, Yingjie Xue, Di Wu, Jian Liu, Xuechao Wang
* [Permalink](https://eprint.iacr.org/2025/1070)
* [Download](https://eprint.iacr.org/2025/1070.pdf)

### Abstract

Payment Channel Networks (PCNs) are the most scalable and trust-minimized solution to Bitcoin's scalability challenges. Within PCNs, connected payer and payee can make arbitrary off-chain transactions through multi-hop payments (MHPs) over payment channel paths, while intermediate relays charge relay fees by providing liquidity.
  However, current MHP protocols face critical security threats including fee-stealing attacks and griefing attacks. In this paper, we identify new fee-stealing attacks targeting most existing MHP protocols. Second, we prove that eliminating griefing attacks in current MHP protocols is impossible by reducing the problem to fair secret exchange. Finally, we introduce Zeus, the first Bitcoin-compatible MHP protocol that is secure against fee-stealing attacks and offers bounded griefing protection against $k$-cost-sensitive adversaries—those who only launch griefing attacks when the expected damage exceeds a $k$ fraction of their own cost. These guarantees are established through rigorous proofs in the Global Universal Composability (GUC) framework. Our comprehensive evaluation demonstrates that Zeus reduces worst-case griefing damage to 28\% and 75\% compared to MHP schemes such as AMHL~(NDSS'19) and Blitz~(USENIX SEC'21), respectively. Our results further show that, even under the most adverse configurations within the Lightning Network, Zeus imposes costs on adversaries that are at least ten times greater than their potential damage.



## 2025/1071

* Title: PICS: Private Intersection over Committed (and reusable) Sets
* Authors: Aarushi Goel, Peihan Miao, Phuoc Van Long Pham, Satvinder Singh
* [Permalink](https://eprint.iacr.org/2025/1071)
* [Download](https://eprint.iacr.org/2025/1071.pdf)

### Abstract

Private Set Intersection (PSI) enables two parties to compute the intersection of their private sets without revealing any additional information. While maliciously secure PSI protocols prevent many attacks, adversaries can still exploit them by using inconsistent inputs across multiple sessions. This limitation stems from the definition of malicious security in secure multiparty computation, but is particularly problematic in PSI because: (1) real-world applications---such as Apple’s PSI protocol for CSAM detection and private contact discovery in messaging apps---often require multiple PSI executions over consistent inputs, and (2) the PSI functionality makes it relatively easy for adversaries to infer additional information.

We propose {\em Private Intersection over Committed Sets (PICS)}, a new framework that enforces input consistency across multiple sessions via committed sets. Building on the state-of-the-art maliciously secure PSI framework (i.e., VOLE-PSI [EUROCRYPT 2021]), we present an efficient instantiation of PICS % in the random oracle model using lightweight cryptographic tools. We implement our protocol to demonstrate concrete efficiency. Compared to VOLE-PSI, for input sets of size $2^{24}$, our communication overhead is as low as $1.1\%$. Our end-to-end performance overhead  is $130\%$ in the LAN setting and decreases to $80\%-10\%$ in the WAN setting with bandwidths ranging from $200$ to $5$ Mbps.



## 2025/1072

* Title: How to Model Unitary Oracles
* Authors: Mark Zhandry
* [Permalink](https://eprint.iacr.org/2025/1072)
* [Download](https://eprint.iacr.org/2025/1072.pdf)

### Abstract

We make the case for modeling unitary oracles by allowing for controlled access to the oracle as well as its conjugate transpose (inverse), but also its conjugate and transpose. Controlling and conjugate transposes are common if even standard, but conjugates and transposes appear to be non-standard. In order to justify our modeling, we give several formal examples of what goes wrong or is missed when using a more restrictive modeling. We also argue that our model is the "right" level of granularity, and that other transformations likely do not correspond to efficient computation. We also discuss other modeling choices, such as ancillas and approximation error.

Through our exploration, we uncover interesting phenomena. Examples include an attack on the recent pseudorandom unitary construction of Ma and Huang (STOC'25) if used incorrectly as a publicly evaluatable unitary, and a quantum complexity-theoretic separation that follows from a purely classical separation.



## 2025/1073

* Title: LAPWN: A Lightweight User–Server Authentication Protocol for Wireless Networks
* Authors: Sajjad Alizadeh, Reza Hooshmand
* [Permalink](https://eprint.iacr.org/2025/1073)
* [Download](https://eprint.iacr.org/2025/1073.pdf)

### Abstract

The Internet of Things (IoT) is composed of interconnected devices that exchange data over a network,
enabling applications in healthcare, transportation, and smart environments. As IoT ecosystems expand,
ensuring security and privacy remains a critical challenge. Many IoT devices rely on wireless
networks for data transmission, making them vulnerable to eavesdropping, tracking, and tampering.
This highlights the need for robust authentication mechanisms. To address these concerns, numerous
authentication protocols have been proposed. However, many fail to ensure adequate security against
both passive and active attacks. In this research, we introduce LAPWN, a lightweight protocol for
user–server communication, specifically designed for constrained environments, ensuring a balance
between security and efficiency. The proposed protocol is implemented as a fully functional Python
application, demonstrating its practical usability and evaluating its efficiency in real-world scenarios.
To validate its security, we performboth informal and formal analyses, utilizing Scyther, ProVerif, and
the Real-or-Random (RoR) model. The results confirm that LAPWN provides a secure, lightweight,
and efficient authentication solution with low computational and communication overhead. Furthermore,
performance evaluations show that it surpasses existing authentication protocols, making it a
highly effective solution for secure user–server interactions in constrained environments.



## 2025/1074

* Title: Multiparty Distributed Point Functions
* Authors: Aarushi Goel, Mingyuan Wang, Zhiheng Wang
* [Permalink](https://eprint.iacr.org/2025/1074)
* [Download](https://eprint.iacr.org/2025/1074.pdf)

### Abstract

We present the first construction of multiparty distributed point functions based on one-way functions, where the share sizes remain sublinear in the domain size and grow {\em only polynomially} with the number of parties. In contrast, existing multiparty distributed point function constructions in Minicrypt have share sizes that grow {\em exponentially} with the number of parties.



## 2025/1075

* Title: Secure and Practical Cold (and Hot) Staking
* Authors: Mario Larangeira
* [Permalink](https://eprint.iacr.org/2025/1075)
* [Download](https://eprint.iacr.org/2025/1075.pdf)

### Abstract

The stake delegation technique is what turns the general Proof of Stake (PoS) into a practical protocol for a large number of participants, ensuring the security of the distributed system, in what is known as Delegated PoS (DPoS). Karakostas et al. (SCN ’20) formalized the delegation method paving the way for a whole industry of stake pools by proposing a formal definition for wallet as a universal composable (UC) functionality and introducing a corresponding protocol. On the other hand, a widely used technique named hot/cold wallet was formally studied by Das et al. (CCS ’19 and ’21), and Groth and Shoup (Eurocrypt ’22) for different key derivation methods in the Proof of Work (PoW) setting, but not PoS. Briefly, while hot wallets are exposed to the risks of the network, the cold wallet is kept offline, thus more secure. However this may impair some capabilities given that the cold wallet is kept indefinitely offline. It is straightforward to observe that this “double wallet” design is not naturally portable to the setting where delegation is paramount, i.e., DPoS. This work identifies challenges for PoS Hot/Cold Wallet and proposes a secure and practical protocol.



## 2025/1076

* Title: Weight reduction in distributed protocols: new algorithms and analysis
* Authors: Anatoliy Zinovyev
* [Permalink](https://eprint.iacr.org/2025/1076)
* [Download](https://eprint.iacr.org/2025/1076.pdf)

### Abstract

We study the problem of minimizing the total weight of (potentially many) participants of a distributed protocol, a necessary step when the original values are large but the scheme to be deployed scales poorly with the weights. We assume that $\alpha$ fraction of the original weights can be corrupted and we must output new weights with at most $\beta$ adversarial fraction, for $\alpha < \beta$. This problem can be viewed from the prism of electing a small committee that does the heavy work, a powerful tool for making distributed protocols scalable. We solve the variant that requires giving parties potentially multiple seats in the committee and counting each seat towards the cost of the solution. Moreover, we focus on the ``deterministic'' version of the problem where the computed committee must be secure for any subset of parties that can be corrupted by the adversary; such a committee can be smaller than a randomly sampled one in some cases and is useful when security against adaptive corruptions is desired but parties in the sub-protocol speak multiple times.

Presented are new algorithms for the problem as well as analysis of prior work. We give two variants of the algorithm Swiper (PODC 2024), one that significantly improves the running time without sacrificing the quality of the output and the other improving the output for a reasonable increase in the running time. We prove, however, that all known algorithms, including our two variants of Swiper, have worst case approximation ratio $\Omega(n)$. To counter that, we give the first polynomial time algorithm with approximation factor $n / \log^2 n$ and also the first sub-exponential time exact algorithm, practical for some real-world inputs. Of theoretical interest is another polytime algorithm that we present, based on linear programming, whose output is no worse than an optimal solution to the problem with slightly different parameters.

We implemented and tested previous and new algorithms, comparing them on the stake distributions of popular proof-of-stake blockchains, and found that our second variant of Swiper computes solutions extremely close to the optimal, confirmed by our exact algorithm.



## 2025/1077

* Title: Shorter VOLE-in-the-Head-based Signatures from Vector Semi-Commitment
* Authors: Seongkwang Kim, Byeonghak Lee, Mincheol Son
* [Permalink](https://eprint.iacr.org/2025/1077)
* [Download](https://eprint.iacr.org/2025/1077.pdf)

### Abstract

The VOLE-in-the-Head (VOLEitH) paradigm transforms VOLE-based zero-knowledge proofs into post-quantum signature schemes by allowing public verification. We introduce reduced VOLE-in-the-Head (rVOLEitH), which incorporates the Vector Semi-Commitment (VSC) technique. VSC, originally developed for MPC-in-the-Head (MPCitH) schemes, reduces commitment size while maintaining security by relaxing the binding property. We adapt the ideal cipher version of VSC (IC-VSC) into the VOLEitH framework, leading to a reduction in signature size. Our security analysis proves that rVOLEitH achieves existential unforgeability under chosen-message attacks (EUF-CMA) in the ideal cipher model. Compared to existing VOLEitH-based signatures, our approach reduces signature size by up to 6.0\% while improving computational efficiency.

Furthermore, we analyze the impact of eliminating individual seed commitments and demonstrate a practical attack against a recently proposed VOLEitH variant that lacks such commitments. Our results establish rVOLEitH as an optimized and secure alternative for post-quantum signatures, improving both efficiency and security in the VOLEitH paradigm.



## 2025/1078

* Title: A Theoretical Perspective on the Formal Verification of IoT Protocols Using LTL and Rewriting Logic in Maude
* Authors: Delia-Iustina Grigoriță
* [Permalink](https://eprint.iacr.org/2025/1078)
* [Download](https://eprint.iacr.org/2025/1078.pdf)

### Abstract

As Internet of Things (IoT) systems become increasingly complex, verifying communication protocols is essential to guarantee their security and correctness. This paper introduces a brief introduction to the theoretical concepts of how to use formal techniques, LTL and rewriting logic within the Maude system to verify the security and proper behavior of the protocols. While rewriting logic explains how various events occur over time, LTL explains how a property can be formulated. This theoretical perspective is intended to inform future applications and research.



## 2025/1079

* Title: Revisiting Discrete Logarithm Reductions
* Authors: Maiara F. Bollauf, Roberto Parisella, Janno Siim
* [Permalink](https://eprint.iacr.org/2025/1079)
* [Download](https://eprint.iacr.org/2025/1079.pdf)

### Abstract

A reduction showing that the hardness of the discrete logarithm ($\mathsf{DL}$) assumption implies the hardness of the computational Diffie-Hellman     ($\mathsf{CDH}$) assumption in groups of order $p$, where $p - 1$ is smooth, was first presented by den Boer [Crypto, 88].}
 We also consider groups
of prime order $p$, where $p - 1$ is somewhat smooth (say, every prime $q$ that divides $p - 1$ is less than $2^{100}$).
Several practically relevant groups satisfy this condition.
 1.     We present a concretely efficient version of the reduction for such groups.
 In particular, among practically relevant groups, we obtain the most efficient and tightest reduction in the literature for BLS12-381, showing that $\mathsf{DL}$ = $\mathsf{CDH}$.
2.      By generalizing the reduction, we show that in these groups the $n$-Power $\mathsf{DL}$ ($n$-$\mathsf{PDL}$) assumption implies $n$-Diffie-Hellman Exponent ($n$-$\mathsf{DHE}$) assumption, where $n$ is polynomial in the security parameter.
On the negative side, we show there is no generic reduction, which could demonstrate that $n$-$\mathsf{PDL}$ implies the $n$-Generalized Diffie-Hellman Exponent ($n$-$\mathsf{GDHE}$) assumption.
This is in stark contrast with the algebraic group model, where this implication holds.



## 2025/1080

* Title: Leftover Hash Lemma(s) Over Cyclotomic Rings
* Authors: Katharina Boudgoust, Oleksandra Lapiha
* [Permalink](https://eprint.iacr.org/2025/1080)
* [Download](https://eprint.iacr.org/2025/1080.pdf)

### Abstract

In this work, we propose a novel systematic approach for obtaining leftover hash lemmas (LHLs) over cyclotomic rings. Such LHLs build a fundamental tool in lattice-based cryptography, both in theoretical reductions as well as in the design of cryptographic primitives. The scattered set of prior works makes it difficult to navigate the landscape and requires a substantial effort to understand the mathematical constraints under which the LHL holds over cyclotomic rings. This is especially painful if one’s given setting does not fit exactly into prior studies.

We argue that all prior approaches boil down to two different proof strategies, resulting in two main theorems. From there on, we are able to recover all previous flavours of seemingly independent LHLs as corollaries. Moreover, we showcase the power of our interpretation by providing new statements, covering mathematical settings not considered before. Our work further proves LHLs in the presence of leakage for both approaches and provides novel bounds for wide families of leakage functions.



## 2025/1081

* Title: FABLE: Batched Evaluation on Confidential Lookup Tables in 2PC
* Authors: Zhengyuan Su, Qi Pang, Simon Beyzerov, Wenting Zheng
* [Permalink](https://eprint.iacr.org/2025/1081)
* [Download](https://eprint.iacr.org/2025/1081.pdf)

### Abstract

Abstract
Secure two-party computation (2PC) is a cryptographic technique that enables two mutually distrusting parties to jointly evaluate a function over their private inputs. We consider a 2PC primitive called confidential lookup table (LUT) evaluation, which is useful in privacy-preserving ML inference and data analytics. In this setting, a server holds a confidential LUT and evaluates it over an input secret-shared between a client and the server, producing a secret-shared output. Existing approaches for 2PC LUT evaluation suffer from high asymptotic complexity and practical inefficiency, with some designs lacking confidentiality guarantees for the LUT. Recognizing that many applications involving confidential LUT evaluation require processing multiple inputs with the same LUT, we propose FABLE, a system designed to efficiently evaluate a LUT on a large batch of queries simultaneously. Compared to the state-of-the-art confidential LUT evaluation methods, FABLE achieves up to 28.46-101.47$\times$ speedup in LAN environments and up to 50.10-392.93$\times$ speedup in WAN environments.



## 2025/1082

* Title: Treebeard: A Scalable and Fault Tolerant ORAM Datastore
* Authors: Amin Setayesh, Cheran Mahalingam, Emily Chen, Sujaya Maiyya
* [Permalink](https://eprint.iacr.org/2025/1082)
* [Download](https://eprint.iacr.org/2025/1082.pdf)

### Abstract

We present Treebeard - the first scalable and fault tolerant Oblivious RAM (ORAM) based datastore designed to protect applications from access pattern attacks. Current ORAM systems face challenges in practical adoption due to their limited ability to handle concurrent workloads, scale effectively, and ensure fault tolerance. We address all three limitations in Treebeard by utilizing a multi-layer architecture that scales horizontally, handling thousands of requests in parallel, while replicating the data to prevent data loss upon failures. Experimental evaluation demonstrates Treebeard's ability to scale linearly, achieving a throughput of 160K ops/sec with 16 machines; this behavior is similar to the enclave-based state-of-the-art, Snoopy. Being fault-tolerant, Treebeard recovers from failures with close to zero downtime and achieves 13.8x the throughput of QuORAM, the latest fault tolerant ORAM system, even without scaling.



## 2025/1083

* Title: The complexity of the SupportMinors Modeling for the MinRank Problem
* Authors: Giulia Gaggero, Elisa Gorla, Daniel Cabarcas
* [Permalink](https://eprint.iacr.org/2025/1083)
* [Download](https://eprint.iacr.org/2025/1083.pdf)

### Abstract

In this note, we provide proven estimates for the complexity of the SupportMinors Modeling, mostly confirming the heuristic complexity estimates contained in the original article.



## 2025/1084

* Title: How to (not) combine Oblivious Pseudorandom Functions
* Authors: Sebastian Faller, Julia Hesse
* [Permalink](https://eprint.iacr.org/2025/1084)
* [Download](https://eprint.iacr.org/2025/1084.pdf)

### Abstract

An oblivious pseudorandom function (OPRF) is a cryptographic tool that enables fast and secure authentication and key derivation from passwords. In the past few years, the adoption of OPRFs has flourished and today they are at the core of the PIN-protected backup methods of WhatsApp and Signal, and of privacy-enhancing browser technologies. All vendors deploy the so-called 2Hash-Diffie-Hellman (2HashDH) OPRF, which relies on discrete-logarithm-type assumptions that are standard yet known to be prone to quantum attacks.

Recent advancements in cryptographic research (e.g., Beullens et al., Eurocrypt 2025) have brought up post-quantum OPRFs that are fast enough to deploy them in the setting of, e.g., WhatsApp or Signal. Yet none of these constructions are based on standard assumptions.

In this work, we investigate combiners for OPRFs, namely a "best-of-both'' combination of a classical and a post-quantum OPRF that is secure as long as one of them is. First, we give formal evidence that so-called black-box combiners do not exist, indicating that combining OPRFs is subtle and bears similarities with other powerful yet hard-to-combine cryptographic primitives like oblivious transfer (OT).

We then give a (non-black-box) combiner for OPRFs and show that it can be instantiated with 2HashDH and the currently most efficient post-quantum OPRFs based on Legendre symbols. In particular, the reliance on the less standard Legendre-based hardness assumption does not harm the security of 2HashDH. This gives vendors a viable path to lift the security of their OPRF deployments to a post-quantum level.



## 2025/1085

* Title: SmallWood: Hash-Based Polynomial Commitments and Zero-Knowledge Arguments for Relatively Small Instances
* Authors: Thibauld Feneuil, Matthieu Rivain
* [Permalink](https://eprint.iacr.org/2025/1085)
* [Download](https://eprint.iacr.org/2025/1085.pdf)

### Abstract

Zero-knowledge proofs (ZKPs) are a fundamental building block in cryptography, enabling powerful privacy-preserving and verifiable computations. In the post-quantum era, hash-based ZKPs have emerged as a promising direction due to their conjectured resistance to quantum attacks, along with their simplicity and efficiency.

In this work, we introduce SmallWood, a hash-based polynomial commitment scheme (PCS) and zero-knowledge argument system optimized for relatively small instances. Building on the recent degree-enforcing commitment scheme (DECS) from the Threshold-Computation-in-the-Head (TCitH) framework, we refine its formalization and combine it with techniques from Brakedown. This results in a new hash-based PCS that is particularly efficient for polynomials of relatively small degree —typically up to $2^{16}$— outperforming existing approaches in this range.

Leveraging this new PCS, we design a hash-based zero-knowledge argument system that outperforms the state-of-the-art in terms of proof sizes for witness size ranging from $2^6$ to $2^{16}$. Additionally, we present exact zero-knowledge arguments for lattice-based problems using SmallWood, demonstrating highly competitive performance: our scheme yields proof sizes under 25 KB across a wide range of lattice parameters, including Kyber and Dilithium instances.



## 2025/1086

* Title: Fairness in the Wild: Secure Atomic Swap with External Incentives
* Authors: Hao Chung, Elisaweta Masserova, Elaine Shi, Sri AravindaKrishnan Thyagarajan
* [Permalink](https://eprint.iacr.org/2025/1086)
* [Download](https://eprint.iacr.org/2025/1086.pdf)

### Abstract

Atomic swaps enable asset exchanges across blockchains without relying on trusted intermediaries, and are a key component of decentralized finance (DeFi) ecosystems. Recently, Chung, Masserova, Shi, and Thyagarajan introduced Rapidash (Financial Cryptography 2025), an atomic swap protocol that remains incentive compatible under user-miner collusion, by ensuring that the honest strategy forms a coalition-resistant Nash equilibrium. However, their model assumes a closed system where players act solely based on internal protocol incentives. In practice, participants may be influenced by external incentives such as off-chain rewards or adversarial bribes, which can undermine such equilibrium guarantees.

In this work, we introduce a new game-theoretic notion, bounded maximin fairness, which ensures that honest participants remain protected against rational adversaries with arbitrary but bounded external incentives. We construct an atomic swap protocol that satisfies this notion, while preserving the equilibrium properties of prior work in the absence of external influence.

As we show, our protocol is easy to implement and can be instantiated even in Bitcoin’s limited scripting language.



## 2025/1087

* Title: Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions
* Authors: Rahul Ilango, Alex Lombardi
* [Permalink](https://eprint.iacr.org/2025/1087)
* [Download](https://eprint.iacr.org/2025/1087.pdf)

### Abstract

We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis.
   
1) Obfuscation can serve as a general-purpose worst-case to average-case reduction, reducing the existence of various forms of cryptography to corresponding worst-case assumptions.
2) We can therefore hope to overcome barriers in cryptography and average-case complexity by (i) making worst-case hardness assumptions beyond $\mathsf{P}\neq \mathsf{NP}$, and (ii) leveraging worst-case hardness reductions, either proved by traditional complexity-theoretic methods or facilitated further by cryptography.

Concretely, our results include:
    - Optimal hardness. Assuming sub-exponential indistinguishability obfuscation, we give fine-grained worst-case to average case reductions for circuit-SAT. In particular, if finding an $\mathsf{NP}$-witness requires nearly brute-force time in the worst case, then the same is true for some efficiently sampleable distribution. In fact, we show that under these assumptions, there exist families of one-way functions with optimal time-probability security tradeoffs.

   Under an additional, stronger assumption -- the optimal non-deterministic hardness of refuting circuit-SAT -- we construct additional cryptographic primitives such as PRGs and public-key encryption that have such optimal time-advantage security tradeoffs.

- Direct Product Hardness. Again assuming $i\mathcal O$ and optimal non-deterministic hardness of SAT refutation, we show that the ``(search) $k$-fold SAT problem'' -- the computational task of finding satisfying assignments to $k$ circuit-SAT instances simultaneously -- has (optimal) hardness roughly $(T/2^n)^k$ for time $T$ algorithms. In fact, we build ``optimally secure one-way product functions'' (Holmgren-Lombardi, FOCS '18), demonstrating that optimal direct product theorems hold for some choice of one-way function family.

- Single-Input Correlation Intractability. Assuming either $i\mathcal O$ or $\mathsf{LWE}$, we show a worst-case to average-case reduction for strong forms of single-input correlation intractability. That is, powerful forms of correlation-intractable hash functions exist provided that a collection of \emph{worst-case} ``correlation-finding'' problems are hard.
  
- Non-interactive Proof of Quantumness. Assuming sub-exponential $i\mathcal O$ and OWFs, we give a non-interactive proof of quantumness based on the worst-case hardness of the white-box Simon problem. In particular, this proof of quantumness result does not explicitly assume quantum advantage for an average-case task.

To help prove our first two results, we show along the way how to improve the Goldwasser-Sipser ``set lower bound'' protocol to have communication complexity quadratically smaller in the multiplicative approximation error $\epsilon$.



## 2025/1088

* Title: Homomorphic Field Trace Revisited : Breaking the Cubic Noise Barrier
* Authors: Kang Hoon Lee, Ji Won Yoon
* [Permalink](https://eprint.iacr.org/2025/1088)
* [Download](https://eprint.iacr.org/2025/1088.pdf)

### Abstract

We present a novel homomorphic trace evaluation algorithm $\mathsf{RevHomTrace}$, which mitigates the phase amplification problem that comes with the definition of the field trace. Our $\mathsf{RevHomTrace}$ overcomes the phase amplification with only a negligible computational overhead, thereby improving the usability of the homomorphic field trace algorithm. Moreover, our tweak also improves the noise propagation of the $\mathsf{HomTrace}$ and breaks the traditional $O(N^{3})$ variance bound in previous works into $O(N \log N)$.

Our experimental results obtained by integrating $\mathsf{RevHomTrace}$ into state-of-the-art homomorphic encryption algorithms further demonstrate the usefulness of our algorithm. Specifically, $\mathsf{RevHomTrace}$ improves the noise accumulation of the (high precision) circuit bootstrapping, which also achieves maximal $1.40\times$ speedup by replacing the costly high precision trace evaluation. Also, based on our idea of $\mathsf{RevHomTrace}$, we present low latency, high precision LWE-to-GLWE packing algorithm $\mathtt{MS}$-$\mathtt{PackLWEs}$. We also show that our $\mathtt{MS}$-$\mathtt{PackLWEs}$ significantly reduces the packing error without severe degradation of performance.



## 2025/1089

* Title: Rugged Pseudorandom Permutations with Beyond-Birthday-Bound Security
* Authors: Nilanjan Datta, Jean Paul Degabriele, Avijit Dutta, Vukašin Karadžić, Hrithik Nandi
* [Permalink](https://eprint.iacr.org/2025/1089)
* [Download](https://eprint.iacr.org/2025/1089.pdf)

### Abstract

A rugged pseudorandom permutation (RPRP) is a security notion for variable-length tweakable ciphers that is strictly weaker than the traditional notion of a strong pseudorandom permutation. Being a weaker security notion it admits more efficient constructions. Yet the notion is strong enough so that any such construction can lend itself to a number of practical applications. It can be used to construct onion encryption, misuse-resistant AEAD, and AEAD secure under the release of unverified plaintext. Two recent works have introduced the notion, explored some of its applications, and studied a number of constructions that meet this notion. However, no constructions are known to achieve this notion with beyond-birthday-bound security. Current cloud applications are processing amounts of data that go well beyond the traditional $2^{32}$ barrier, and $2^{64}$ is becoming the new target. As such, the need for encryption with beyond-birthday-bound security has become a very practical concern. In this work, we present the first constructions for variable-length tweakable ciphers that satisfy RPRP security beyond the birthday bound. From these constructions, we readily obtain efficient AEAD schemes that are optimally secure against once misuse and the release of unverified plaintext.



## 2025/1090

* Title: Concrete Treatment of Signal Handshake’s Deniability: Efficient Post-Quantum Deniable Ring Signature
* Authors: Shuichi Katsumata, Guilhem Niot, Ida Tucker, Thom Wiggers
* [Permalink](https://eprint.iacr.org/2025/1090)
* [Download](https://eprint.iacr.org/2025/1090.pdf)

### Abstract

The Signal protocol relies on a handshake protocol, formerly X3DH and now PQXDH, to set up secure conversations. One of its privacy properties, of value to Signal, is deniability, allowing users to deny participation in communications. Prior analyses of deniability for these protocols, including post-quantum variants, use models highly tailored to the individual protocols and generally make ad-hoc adaptations to ``standard'' AKE definitions, obscuring the concrete deniability guarantees and complicating comparisons across protocols. Building on Hashimoto et al.’s abstraction for Signal handshake protocols (USENIX’25)'s abstraction for Signal handshake protocols (USENIX'25), we address this gap by presenting a unified framework for analyzing their deniability. We analyze Signal's classically secure X3DH and harvest-now-decrypt-later-secure PQXDH, and show that PQXDH is deniable against harvest-now-judge-later attacks, where a quantum judge retrospectively assesses the participation of classical users. We further analyze post-quantum alternatives like RingXKEM, whose deniability relies on ring signatures (RS).
By introducing a novel metric inspired by differential privacy, we provide relaxed, pragmatic guarantees for deniability. We also use this metric to define deniability for RS, a relaxation of anonymity, allowing us to build an efficient RS from NIST-standardized Falcon (and MAYO), which is not anonymous, but is provably deniable.



## 2025/1091

* Title: Quantum Computing without the Linear Algebra
* Authors: Aws Albarghouthi
* [Permalink](https://eprint.iacr.org/2025/1091)
* [Download](https://eprint.iacr.org/2025/1091.pdf)

### Abstract

Quantum computing is often introduced through the lens of linear algebra with notation that is inherited from quantum mechanics. In this paper, we take an operational view of quantum computing that is easy to demonstrate programmatically. The hope is that this viewpoint will (1) demystify quantum computing and make it more accessible to a wider audience, particularly computer science students and software engineers, and (2) possibly serve as the basis of a formal foundation for automatically reasoning about quantum programs.
We treat the state of a quantum computer as a set and present the operations of a quantum computer—quantum gates and measurements—using familiar functional set transformations (think map, filter, fold, etc.). By the end of the paper, we will have implemented a simple quantum circuit simulator that can be used to simulate small quantum circuits. The code is available at https://github.com/qqq-wisc/qwla.



## 2025/1092

* Title: OwlC: Compiling Security Protocols to Verified, Secure, High-Performance Libraries
* Authors: Pratap Singh, Joshua Gancher, Bryan Parno
* [Permalink](https://eprint.iacr.org/2025/1092)
* [Download](https://eprint.iacr.org/2025/1092.pdf)

### Abstract

Cryptographic security protocols, such as TLS or WireGuard, form the foundation of a secure Internet; hence, a long line of research has shown how to formally verify their high-level designs. Unfortunately, these formal guarantees have not yet reached real-world implementations of these protocols, which still rely on testing and ad-hoc manual audits for security and correctness. This gap may be explained, in part, by the substantial performance and/or development overhead imposed by prior efforts to verify implementations.

To make it more practical to deploy verified implementations of security protocols, we present OwlC, the first fully automated, security-preserving compiler for verified, high-performance implementations of security protocols. From a high-level protocol specification proven computationally secure in the Owl language, OwlC emits an efficient, interoperable, side-channel resistant Rust library that is automatically formally verified to be correct.

We produce verified libraries for all previously written Owl protocols, and we also evaluate OwlC on two new verified case studies: WireGuard and Hybrid Public-Key Encryption (HPKE). Our verified implementations interoperate with existing implementations, and their performance matches unverified industrial baselines on end-to-end benchmarks.



## 2025/1093

* Title: On the Concrete Security of BBS/BBS+ Signatures
* Authors: Rutchathon Chairattana-Apirom, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2025/1093)
* [Download](https://eprint.iacr.org/2025/1093.pdf)

### Abstract

BBS/BBS+ signatures are the most promising solution to instantiate practical and lightweight anonymous credentials. They underlie standardization efforts by the W3C and the IRTF. Due to their potential for large scale deployment, it is paramount to understand their concrete security, but a number of questions have been left open by prior works. To this end, the security proofs by Au et al. (SCN '06), Camenisch et al. (TRUST '16), and Tessaro and Zhu (EUROCRYPT '23) show reductions from $q$-SDH in groups of prime order $p$, where $q$ is the number of issued signatures.
   
    However, these prior works left the possibility open that BBS/BBS+ is "even more secure" than what can be guaranteed by such proofs. Indeed, while the $q$-SDH assumption is subject to an attack that uses $O(\sqrt{p/q})$ group exponentiations (Cheon, EUROCRYPT '06) for several choices of $q$, no attack with a similar complexity appears to affect either of BBS+ and "deterministic" BBS, for which the best known attacks amount to recovering the secret key by breaking the discrete logarithm problem. The assumption that this attack is best possible also seemingly justifies the choice of parameters in practice.

    Our result shows that this expectation is not true. We show new attacks against BBS+ and deterministic BBS which, after seeing $q$ signatures, allow us to recover the secret key with the same complexity as solving the $\Theta(q)$-Discrete Logarithm problem, which in turn is proportional to $O(\sqrt{p/q})$ for many choices of $q$. Further, we also extend the attack to a reduction showing that the security of BBS+ and deterministic BBS implies the $\Theta(q)$-SDH assumption.



## 2025/1094

* Title: Key Updatable Identity-Based-Signature Schemes
* Authors: Tobias Guggemos, Farzin Renan
* [Permalink](https://eprint.iacr.org/2025/1094)
* [Download](https://eprint.iacr.org/2025/1094.pdf)

### Abstract

Identity-based signature ($\textsf{IBS}$) schemes eliminate the need for certificate management, reducing both signature size and verification time. However, the challenge of updating stolen identity-based signature keys (or revoking and re-issueing them) has received limited attention. Existing generic solutions, such as managing revocation lists or periodically renewing user keys, are inefficient and introduce significant networking overhead in dynamic environments.
In this work, we address this gap by introducing a symmetric element that enables key updates in $\textsf{IBS}$ schemes via a single multicast message. The network overhead of our solutions scales logarithmic with the number of system users, while computation and memory overhead are constant. Furthermore, we generalize our method by proposing a framework to transform any $\textsf{IBS}$ scheme into a key-updatable signature scheme ($\textsf{KUSS}$), and we define the token security (unforgeability), forward security, and post-compromise security requirements for such transformations. We demonstrate the versatility of our framework by providing five instantiations of $\textsf{KUSS}$ based on Schnorr-type $\textsf{IBS}$, pairing-based $\textsf{IBS}$, and isogeny-based $\textsf{IBS}$. Finally, we analyze the security of these instantiations.



## 2025/1095

* Title: Ideally HAWKward: How Not to Break Module-LIP
* Authors: Clémence Chevignard, Guilhem Mureau
* [Permalink](https://eprint.iacr.org/2025/1095)
* [Download](https://eprint.iacr.org/2025/1095.pdf)

### Abstract

The module-Lattice Isomorphism Problem (module-LIP) was introduced by Ducas et al. (ASIACRYPT 22) in~\cite{HAWK:cryptoeprint:2022/1155}, and used within the signature scheme and NIST candidate HAWK. In~\cite{modLIPtotallyreal}, Mureau et al. (EUROCRYPT24) pointed out that over certain number fields $F$, the problem can be reduced to enumerating solutions of $x^2 + y^2 = q$ (where $q \in \O_F$ is given and $x,y \in \O_F$ are the unknowns). Moreover one can always reduce to a similar equation which has only \textit{few} solutions. This key insight led to a heuristic polynomial-time algorithm for solving module-LIP on those specific instances. Yet this result doesn't threaten HAWK for which the problem can be reduced to enumerating solutions of $x^2 + y^2 + z^2 + t^2 = q$ (where $q \in \O_F$ is given and $x,y,z,t \in \O_F$ are the unknowns). We show that, in all likelihood, solving this equation requires the enumeration of a \textit{too large} set to be feasible, thereby making irrelevant a straightforward adaptation of the approach in~\cite{modLIPtotallyreal}.



## 2025/1096

* Title: CuFDFB: Fast and Private Computation on Non-Linear Functions Using FHE
* Authors: Shutong Jin, Shiyu Shen, Hao Yang, Donglong Chen, Wangchen Dai, Ray C. C. Cheung
* [Permalink](https://eprint.iacr.org/2025/1096)
* [Download](https://eprint.iacr.org/2025/1096.pdf)

### Abstract

Privacy-preserving neural network inference using Fully Homomorphic Encryption (FHE) faces significant challenges in efficiently evaluating non-polynomial functions, such as activation functions, which are critical for introducing non-linearity in neural networks. Full-Domain Functional Bootstrap (FDFB) algorithms provide a promising solution by enabling the evaluation of arbitrary functions while simultaneously refreshing ciphertexts to manage noise accumulation. Despite their theoretical advantages, the practicality of FDFB algorithms has been limited by excessive computational overhead, often exceeding 1000 ms per ciphertext, which restricts their scalability for large neural networks.

To overcome the computational bottlenecks of FDFB, we have re-engineered the algorithms for massively parallel execution on GPUs. Our primary contribution is a hierarchical parallelization strategy that exploits concurrency at the thread, stream, and device levels. A key optimization involves the use of CUDA streams to create a data pipeline that effectively mitigates the overhead of memory transfers between the host and device. This optimized architecture achieves a significant speedup of up to 524$\times$ compared to CPU-based implementations. Our implementation maintains full precision for evaluating various activation functions, confirming its viability for large-scale, privacy-preserving machine learning tasks and paving the way for practical FHE-based deep learning.



## 2025/1097

* Title: Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher
* Authors: Roberto La Scala, Sharwan K. Tiwari
* [Permalink](https://eprint.iacr.org/2025/1097)
* [Download](https://eprint.iacr.org/2025/1097.pdf)

### Abstract

The multistep solving strategy consists in a divide-and-conquer approach: when a multivariate polynomial system is computationally infeasible to solve directly, one variable is assigned over the elements of the base finite field, and the procedure is recursively applied to the resulting simplified systems. In a previous work by the same authors (among others), this approach proved effective in the algebraic cryptanalysis of the Trivium cipher.

In this paper, we present a new implementation of the corresponding algorithm based on a Depth-First Search strategy, along with a novel complexity analysis leveraging tree structures. We further introduce the notion of an ``oracle function'' as a general predictive tool for deciding whether the evaluation of a new variable is necessary to simplify the current polynomial system. This notion allows us to unify all previously proposed variants of the multistep strategy, including the classical hybrid approach, by appropriately selecting the oracle function.

Finally, we apply the multistep solving strategy to the cryptanalysis of the low-latency block cipher Aradi, recently introduced by the NSA. We present the first full-round algebraic attack, raising concerns about the cipher’s actual security with respect to its key length.



## 2025/1098

* Title: Isogeny-based key exchange from orientations of large discriminant
* Authors: Marc Houben
* [Permalink](https://eprint.iacr.org/2025/1098)
* [Download](https://eprint.iacr.org/2025/1098.pdf)

### Abstract

We describe an algorithm to efficiently evaluate class group actions on supersingular elliptic curves that are oriented by an imaginary quadratic order of arbitrarily large discriminant. Contrary to CSIDH, this allows to increase the post-quantum security of the group action without increasing the size of the base field. In particular, we describe instances where Kuperberg's algorithm loses to generic supersingular isogeny path finding. Our algorithm is fully deterministic, strictly constant time, dummy free, and can be implemented without conditional branches. We show that the (restricted effective) group action can be employed in a non-interactive key exchange protocol, that we argue is asymptotically more efficient than CSIDH.



## 2025/1099

* Title: Lattice-Based Accumulator and Application to Anonymous Credential Revocation
* Authors: Victor Youdom Kemmoe, Anna Lysyanskaya, Ngoc Khanh Nguyen
* [Permalink](https://eprint.iacr.org/2025/1099)
* [Download](https://eprint.iacr.org/2025/1099.pdf)

### Abstract

An accumulator is a cryptographic system for compactly representing a set of elements such that every element in the set has a short membership witness. A dynamic accumulator, furthermore, allows elements to be added to and deleted from the accumulator.  Camenisch and Lysyanskaya (CRYPTO'02) constructed the first dynamic accumulator under the strong-RSA assumption and showed how it can be used to enable revocation of anonymous credentials.  In this paper, we give a lattice-based dynamic accumulator tailor-made for enabling revocation of post-quantum anonymous credential systems. As a concrete example, we instantiate our dynamic accumulator on top of the anonymous credential system implemented in the LaZer library (ACM CCS 2024).



## 2025/1100

* Title: Tanuki: New Frameworks for (Concurrently Secure) Blind Signatures from Post-Quantum Groups Actions
* Authors: Lucjan Hanzlik, Yi-Fu Lai, Marzio Mula, Eugenio Paracucchi, Daniel Slamanig, Gang Tang
* [Permalink](https://eprint.iacr.org/2025/1100)
* [Download](https://eprint.iacr.org/2025/1100.pdf)

### Abstract

Blind signatures are fundamental cryptographic primitives enabling privacy-preserving authentication and have seen renewed interest in the post-quantum literature.
Existing efficient constructions predominantly rely on Fischlin’s generic paradigm instantiated over lattice assumptions, while blinding techniques for sigma-protocol-based blind signatures remain sparse beyond lattices. Moreover, achieving provable concurrent security under polynomially many sessions has been a longstanding open challenge for this approach in the post-quantum literature as evidenced by the recent attacks in EC’24 and PKC’24.


This work broadens the landscape of post-quantum blind signatures by introducing novel techniques and proposing four frameworks based on general cryptographic group actions, without requiring commutativity. Our constructions admit instantiations under diverse post-quantum assumptions, including CSIDH (isogeny-based), LESS (code-based, NIST round-two), and more. These frameworks offer flexible trade-offs in assumptions (from interactive one-more to the standard inversion problem) and key/signature sizes, and culminate in a construction that achieves security under polynomially many concurrent sessions. This enables the first efficient blind signatures from isogenies and codes with provable concurrent security with 3.9 and 56 KB respectively. We also outline several directions for optimization and further instantiations for future work.



## 2025/1101

* Title: A Note on One Authentication and Key Agreement Scheme for UAV-Assisted VANETs for Emergency Rescue
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2025/1101)
* [Download](https://eprint.iacr.org/2025/1101.pdf)

### Abstract

We show that the key agreement scheme  [IEEE TNSE, 1454--1468, 2004] is insecure against ephemeral secret leakage attack and smart card loss attack, not as claimed. This failure results from its simple encryption, in which only bitwise XOR operations are used to encrypt the messages.



## 2025/1102

* Title: TEEMS: A Trusted Execution Environment based Metadata-protected Messaging System
* Authors: Sajin Sasy, Aaron Johnson, Ian Goldberg
* [Permalink](https://eprint.iacr.org/2025/1102)
* [Download](https://eprint.iacr.org/2025/1102.pdf)

### Abstract

Ensuring privacy of online messaging remains a challenge.  While the contents or data of online communications are often protected by end-to-end encryption, the metadata of communications are not.  Metadata such as who is communicating with whom, how much, and how often, are leaked by popular messaging systems today.

In the last four decades we have witnessed a rich literature of designs towards metadata-protecting communications systems (MPCS).  While recent MPCS works often target metadata-protected messaging systems, no existing construction simultaneously attains four desirable properties for messaging systems, namely (i) low latency, (ii) high throughput, (iii) horizontal scalability, and (iv) asynchronicity.  Existing designs often capture disjoint subsets of these properties.  For example, PIR-based approaches achieve low latency and asynchronicity but have low throughput and lack horizontal scalability, mixnet-based approaches achieve high throughput and horizontal scalability but lack asynchronicity, and approaches based on trusted execution environments (TEEs) achieve high throughput and asynchronicity but lack horizontal scalability.

In this work, we present TEEMS, the first MPCS designed for metadata-protected messaging that simultaneously achieves all four desirable properties. Our distributed TEE-based system uses an oblivious mailbox design to provide metadata-protected messaging.  TEEMS presents novel oblivious routing protocols that adapt prior work on oblivious distributed sorting.  Moreover, we introduce the notion of ID and token channels to circumvent shortcomings of prior designs.  We empirically demonstrate TEEMS' ability to support $2^{20}$ clients engaged in metadata-protected conversations in under 1 s, with 205 cores, achieving an 18× improvement over prior work for latency and throughput, while supporting significantly better scalability and asynchronicity properties.



## 2025/1103

* Title: Universally Composable Succinct Vector Commitments and Applications
* Authors: Ran Canetti, Megan Chen
* [Permalink](https://eprint.iacr.org/2025/1103)
* [Download](https://eprint.iacr.org/2025/1103.pdf)

### Abstract

We develop a toolbox for modular construction and analysis of succinct, non-interactive commitments and vector commitments in the random oracle model, while guaranteeing universally composable security. To demonstrate its power, we use the toolbox to construct and analyze a modular variant of the Kilian-Micali ZK-SNARK. Along the way we also propose a new UC formulation of a global random oracle, that avoids a weakness in existing formulations and also enables expressing more nuanced, session-specific abstractions. We hope that this toolbox will be useful for building secure applications in settings where both succinctness and non-interactivity are key.



## 2025/1104

* Title: Better GBFV Bootstrapping and Faster Encrypted Edit Distance Computation
* Authors: Robin Geelen, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2025/1104)
* [Download](https://eprint.iacr.org/2025/1104.pdf)

### Abstract

We propose a new iterative method to convert a ciphertext from the Generalized BFV (GBFV) to the regular BFV scheme. In particular, our conversion starts from an encrypted plaintext that lives in a large cyclotomic ring modulo a small-norm polynomial $t(x)$, and gradually changes the encoding to a smaller cyclotomic ring modulo a larger integer $p$. Previously, only a trivial conversion method was known, which did not change the underlying cyclotomic ring.

Using our improved conversion algorithm, we can bootstrap the GBFV scheme almost natively, in the sense that only a very small fraction of the operations is computed inside regular BFV. Specifically, we evaluate (an adapted version of) the slot-to-coefficient transformation entirely in the GBFV scheme, whereas the previous best method used the BFV scheme for that transformation. This insight allows us to bootstrap either with less noise growth, or much faster than the state-of-the-art.

We implement our new bootstrapping in Microsoft SEAL. Our experiments show that, for the same remaining noise budget, our bootstrapping runs in only 800 ms when working with ciphertexts containing 1024 slots over $\mathbb{F}_{p}$ with $p = 2^{16}+1$. This is $1.6\times$ faster than the state-of-the-art.

Finally, we use our improved GBFV bootstrapping in an application that computes an encrypted edit distance. Compared to the recent TFHE-based Leuvenshtein algorithm, our GBFV version is almost two orders of magnitude faster in the amortized sense.



## 2025/1105

* Title: Low-cost anonymous reputation update for IoT applications
* Authors: Alex Shafarenko
* [Permalink](https://eprint.iacr.org/2025/1105)
* [Download](https://eprint.iacr.org/2025/1105.pdf)

### Abstract

This paper presents a novel approach to zero-trust anonymous reputation update in crowd sensing IoT applications. We use a suite of cryptographic functions to achieve anonymity, including unlinkability of sensing reports to the principals that submit them and to one another, while enabling the infrastructure to reliably quantify the degree of trust expressed as a reputation level. The protocol is low-cost for the anonymous participant due to the use of cheap standard algorithms: low-exponent modular exponentia- tion and cryptographic hashing, which makes it quite suitable for IoT.



## 2025/1106

* Title: b4M: Holistic Benchmarking for MPC
* Authors: Karl W. Koch, Dragos Rotaru, Christian Rechberger
* [Permalink](https://eprint.iacr.org/2025/1106)
* [Download](https://eprint.iacr.org/2025/1106.pdf)

### Abstract

Secure Multi-Party Computation (MPC) is becoming more and more usable in practice. The practicality origins primarily from well-established general-purpose MPC frameworks, such as MP-SPDZ. However, to evaluate the practicality of an MPC program in the envisioned environments, still many benchmarks need to be done. We identified three challenges in the context of performance evaluations within the MPC domain: first, the cumbersome process to holistically benchmark MPC programs; second, the difficulty to find the best-possible MPC setting for a given task and envisioned environment; and third, to have consistent evaluations of the same task or problem area across projects and papers. In this work, we address the gap of tedious and complex benchmarking of MPC. Related works so far mostly provide a comparison for certain programs with different engines.

To the best of our knowledge, for the first time the whole benchmarking pipeline is automated; provided by our open-sourced framework Holistic Benchmarking for MPC (b4M). b4M is easy to configure using TOML files, outputs ready-to-use graphs, and provides even the MPC engine itself as own benchmark dimension. Furthermore it takes three relatively easy steps to add further engines: first, integrate engine-specific commands into b4M’s runner class; second, output performance metrics in b4M’s format; third, provide a Docker container for the engine’s parties.

To showcase b4M, we provide an exemplary evaluation for the computation of the dot product and logistic regression using a real-world dataset. With this work, we move towards fully-automated evaluations of MPC programs, protocols, and engines, which smoothens the setup process and viewing various trade-offs.. Hence, b4M advances MPC development by improving the benchmarking usability aspect of it.



## 2025/1107

* Title: Early Stopping is Cheap
* Authors: Fatima Elsheimy, Simon Holmgaard Kamp, Julian Loss
* [Permalink](https://eprint.iacr.org/2025/1107)
* [Download](https://eprint.iacr.org/2025/1107.pdf)

### Abstract

Minimizing both the round and communication complexity of Byzantine agreement (BA) is fundamental question in distributed computing. A long line of works has focused on early-stopping deterministic protocols that can terminate within a number of synchronous rounds that is proportional to $f$, where $f$ is the \emph{actual number} of corruptions in an execution, as opposed to an upper bound $t$. This can lead to major benefits when $f\ll t$. A very different style of randomized protocol has focused on \emph{player replaceable} BA protocols with communication complexity linear in the number of parties $n$ and adaptive security, which rely on only a small and rotating subcommittee of parties to ever speak in the protocol. One downside of existing player-replaceable protocols is that they require $O(r)$ rounds to terminate with overwhelming probability $1-2^r$.
    For applications demanding high security guarantees, this can easily become the bottleneck of a player replaceable protocol. Motivated by this gap in the literature, we give the first protocol that is simultaneously player-replaceable \emph{and} early stopping (with overwhelming probability). Let $1>\alpha>0$ and $1>\epsilon>0$ be constants and let $\lambda$ and $\kappa$ denote suitable security parameters. Our protocol is secure against up to $t<(1-\alpha)\cdot n/2$ adaptive Byzantine corruptions and terminates in $(1+\epsilon)\cdot f$ many rounds with probability $1-2^\lambda$, given $f\leq t$ corruptions. Moreover, our protocol has constant expected round complexity and communication bounded by $O(n\cdot \lambda^3 \cdot \kappa ).$



## 2025/1108

* Title: Laconic PSI on Authenticated Inputs and Applications
* Authors: James Bartusek, Sanjam Garg, Abhishek Jain, Guru-Vamsi Policharla
* [Permalink](https://eprint.iacr.org/2025/1108)
* [Download](https://eprint.iacr.org/2025/1108.pdf)

### Abstract

A common issue with using secure computation in practice is that its security does not place any restrictions on what an adversary can use as input in the protocol. In this work, we focus on the practically-motivated setting of (two-message, labeled) private set intersection (PSI), and advocate for a clean and versatile solution to this problem: PSI on authenticated inputs.

Our central contributions are summarized as follows.
- We formulate a novel definition of PSI on authenticated inputs that has the potential for use in several applications, from content moderation in end-to-end encrypted systems to watchlists in anonymous e-cash systems.
- We design a concretely-efficient and laconic (i.e., the size of the receiver's message is independent of its set size) protocol for PSI on authenticated inputs.
- We build on our PSI protocol to obtain the first laconic set pre-constrained group signature scheme, improving on that of Bartusek et al. (Eurocrypt 23).

We also explore various optimizations to our basic protocol, including reducing the receiver's concrete run time, and a tradeoff between crs size and message size.



## 2025/1109

* Title: Kahrobaei--Koupparis DSS: universal forgery
* Authors: Alexander Ushakov
* [Permalink](https://eprint.iacr.org/2025/1109)
* [Download](https://eprint.iacr.org/2025/1109.pdf)

### Abstract

Regardless of the choice of parameters, knowledge of a single signed message, i.e., a pair message/signature, produced by Kahrobaei-Koupparis digital signature scheme is sufficient to forge a valid signature for any other message.



## 2025/1110

* Title: A Framework for Compiling Custom Languages as Efficiently  Verifiable Virtual Machines
* Authors: Assimakis A. Kattis, Brian Klatt, Philip Quirk, Logan Allen
* [Permalink](https://eprint.iacr.org/2025/1110)
* [Download](https://eprint.iacr.org/2025/1110.pdf)

### Abstract

In this work, we develop a framework for compiling languages into efficient Interactive Oracle Proofs (IOPs, or ‘circuits’), motivated by applications in verifiable Virtual Machine (zkVM) design. We provide a set of sufficient conditions on a language under which it can be compiled into an efficient IOP, alongside corresponding performance costs. We identify a subclass of languages, which we denote as traversable, and demonstrate how traversable languages can be efficiently compiled as circuits using established techniques.

To demonstrate the efficacy of our compilation framework, we develop a zkVM for the Nock programming language by (1) formalizing the existing Nock specification, and (2) applying our techniques to design an efficient IOP representation for the Nock VM. The resulting circuit is small, on par with existing state-of-the-art zkVM designs and can be generated for any traversable language in a generic way.



## 2025/1111

* Title: SEAF: Secure Evaluation on Activation Functions with Dynamic Precision for Secure Two-Party Inference
* Authors: Hao Guo, Zhaoqian Liu, Ximing Fu, Zhusen Liu
* [Permalink](https://eprint.iacr.org/2025/1111)
* [Download](https://eprint.iacr.org/2025/1111.pdf)

### Abstract

Secure evaluation of non-linear functions is one of the most expensive operations in secure two-party computation, particularly for activation functions in privacy preserving machine learning (PPML). This work introduces SEAF, a novel framework for efficient Secure Evaluation on Activation Functions. SEAF is based on the linear approximation approach, but enhances it by introducing two key innovations: Trun-Eq based interval test protocols and linear approximation with dynamic precision, which have the potential for broader applicability. Furthermore, we classify common activation functions into several categories, and present specialized methods to evaluate them using our enhanced techniques. Our implementation of SEAF demonstrates $3.5 \times$ to $5.9 \times$ speedup on activation functions $\mathsf{Tanh}$ and $\mathsf{Sigmoid}$ compared to SirNN (S\&P'21). When applied on $\mathsf{GELU}$, SEAF outperforms Iron (NeurIPS'22) by more than $10 \times$ and Bolt (S\&P'24) by up to $3.4 \times$. For end-to-end secure inference on BERT, the original $\mathsf{GELU}$ accounts for $31.3 \%$ and $22.5 \%$ of the total runtime in Iron and Bolt, respectively. In contrast, our optimized $\mathsf{GELU}$ reduces these proportions to  $4.3 \%$ and $9.8 \%$, eliminating $\mathsf{GELU}$ as a bottleneck in secure inference.



## 2025/1112

* Title: Hydrangea: Optimistic Two-Round Partial Synchrony with One-Third Fault Resilience
* Authors: Nibesh Shrestha, Aniket Kate, Kartik Nayak
* [Permalink](https://eprint.iacr.org/2025/1112)
* [Download](https://eprint.iacr.org/2025/1112.pdf)

### Abstract

We present Hydrangea, a partially synchronous Byzantine fault-tolerant state machine replication protocol that achieves a latency of two rounds optimistically while maintaining high adversarial resilience. In particular, for a system of $n = 3f + 3p + 1$ parties, if up to $p$ parties are faulty, then the protocol can obtain a latency of two rounds. Otherwise, the protocol can obtain a latency of three rounds while tolerating $f$ Byzantine faults and $p$ crash faults {\em simultaneously}.



## 2025/1113

* Title: Computational Attestations of Polynomial Integrity Towards Verifiable Back-Propagation
* Authors: Dustin Ray, Caroline El Jazmi
* [Permalink](https://eprint.iacr.org/2025/1113)
* [Download](https://eprint.iacr.org/2025/1113.pdf)

### Abstract

Recent advancements in machine learning accuracy and utility have been driven by the effective combination of sophisticated models with high-performance computational scaling. As the development of large-scale models shifts away from commodity hardware to outsourced computation, it becomes paramount to ensure that the training process is executed with integrity and transparency. This encompasses verifying that adequate computational resources were expended and that the resulting model is accurate, rather than the product of skipped steps or resource-saving shortcuts by the external provider. Building on our previous efforts, which demonstrated the computational feasibility of using this system to argue correctness for differentially-private linear regression, we extend those results to achieve fully provable back-propagation—a cornerstone operation in modern machine learning training. Our system achieves complete zero-knowledge, revealing nothing about the input data during training, and ensures quantum security by relying on no weak cryptographic primitives. Efficiency is substantially increased through the use of a fixed-point decimal representation, reducing the computational overhead typically associated with floating-point arithmetic. Notably, our solution is doubly efficient, achieving a logarithmic-time verifier and a linear-time prover. Implemented entirely in Rust without reliance on external machine learning libraries, and executed within a cryptographically secure virtual machine, this work represents a significant advancement toward verifiable, secure, and efficient outsourced machine learning computations.