From Newsgroup: sci.crypt

## In this issue
1. [2025/261] HasteBoots: Proving FHE Bootstrapping in Seconds
2. [2025/367] Partial Lattice Trapdoors: How to Split Lattice ...
3. [2025/890] SPEEDY: Caught at Last
4. [2025/1284] A Hybrid Algorithm for the Regular Syndrome ...
5. [2025/1555] Information-theoretic MPC with Constant ...
6. [2025/1556] CryptoFace: End-to-End Encrypted Face Recognition
7. [2025/1557] On Achieving ``Best-in-the-Multiverse'' MPC
8. [2025/1558] Lower Bounding Update Frequency in Short ...
9. [2025/1559] A New Generalized Lattice Attack Against a Family ...
10. [2025/1560] On the Termination of the HotStuff Protocol Within ...
11. [2025/1561] A Traceable Threshold Asmuth--Bloom Secret Sharing ...
12. [2025/1562] Formally Verified Correctness Bounds for Lattice- ...
13. [2025/1563] Optimized Constant-Time Implementation of terSIDH
14. [2025/1564] SoK: Blockchain Consensus in the Quantum Age
15. [2025/1565] Game Changer: A Modular Framework for OPRF Security
16. [2025/1566] Lattice-based Threshold Blind Signatures
17. [2025/1567] Bootstrappable Fully Homomorphic Attribute-Based ...
18. [2025/1568] Montgomery Curves: Exact Enumeration and ...
19. [2025/1569] How Hard Can It Be to Formalize a Proof? Lessons ...
20. [2025/1570] Multi-Message Quantum Broadcast with Fine-Grained ...
21. [2025/1571] Attribute-based Quantum Broadcast Encryption with ...
22. [2025/1572] Quantum Implementation of MD5
23. [2025/1573] OneTwoPAKE: Two-Round Strong Asymmetric PAKE with ...
24. [2025/1574] Information-Theoretic Random-Index PIR
25. [2025/1575] BitPriv: A Privacy-Preserving Protocol for DeFi ...
26. [2025/1576] Compressed verification for post-quantum signatures ...
27. [2025/1577] A Template SCA Attack on the Kyber/ML-KEM Pair- ...
28. [2025/1578] Back to the future: simple threshold decryption ...
29. [2025/1579] TACITA: Threshold Aggregation without Client ...
30. [2025/1580] IronDict: Transparent Dictionaries from Polynomial ...
31. [2025/1581] Cryptanalysis of ChiLow with Cube-Like Attacks
32. [2025/1582] Breaking Omert|a: On Threshold Cryptography, Smart ...
33. [2025/1583] Compact Lattice-Coded (Multi-Recipient) Kyber ...
34. [2025/1584] PriSrv+: Privacy and Usability-Enhanced Wireless ...
35. [2025/1585] LEAF: Compact and Efficient Blind Signature from ...
36. [2025/1586] A Note on Feedback-PRF Mode of KDF from NIST SP 800-108
37. [2025/1587] Secure Agents
38. [2025/1588] Query-Optimal IOPPs for Linear-TIme Encodable Codes
39. [2025/1589] Symmetric Group-Based Public-Key Cryptosystem with ...
40. [2025/1590] The AIIP Problem: Toward a Post-Quantum Hardness ...
41. [2025/1591] HE-SecureNet: An Efficient and Usable Framework for ...
42. [2025/1592] MegaBlocks: Breaking the Logarithmic I/O-Overhead ...
## 2025/261
* Title: HasteBoots: Proving FHE Bootstrapping in Seconds
* Authors: Fengrun Liu, Haofei Liang, Tianyu Zhang, Yuncong Hu, Xiang Xie, Haisheng Tan, Yu Yu
* [Permalink](https://eprint.iacr.org/2025/261)
* [Download](https://eprint.iacr.org/2025/261.pdf)
### Abstract
Fully Homomorphic Encryption (FHE) enables computations on encrypted data, ensuring privacy for outsourced computation. However, verifying the integrity of FHE computations remains a significant challenge, especially for bootstrapping, the most computationally intensive operation in FHE. Prior approaches, including zkVM-based solutions and general-purpose SNARKs, suffer from inefficiencies, with proof generation times ranging from several hours to days. In this work, we propose HasteBoots, a succinct argument tailored for FHE operations. By designing customized polynomial interactive oracle proofs and optimized polynomial commitment schemes, HasteBoots achieves proof generation in a few seconds for FHE NAND with bootstrapping, significantly outperforming existing methods. Our approach demonstrates the potential for scalable and efficient verifiable FHE, paving the way for practical, privacy-preserving computations.
## 2025/367
* Title: Partial Lattice Trapdoors: How to Split Lattice Trapdoors, Literally
* Authors: Martin R. Albrecht, Russell W. F. Lai, Oleksandra Lapiha, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2025/367)
* [Download](https://eprint.iacr.org/2025/367.pdf)
### Abstract
Lattice trapdoor algorithms allow us to sample hard random lattices together with their trapdoors, given which short preimage vectors of any given target images can be sampled efficiently. This enables a wide range of advanced cryptographic primitives, such as attribute-based encryption and homomorphic signatures. To obtain thresholdised variants of these primitives, one approach is to design a non-interactive mechanism to distribute the preimage sampling process. While generic tools such as the universal thresholdiser exist for this task, they require homomorphically sampling from Gaussian distributions which is non-trivial. We ask: can we distribute lattice trapdoors non-interactively and algebraically?
We present a natural approach to this problem: splitting full trapdoors into partial trapdoors for different lower-rank sublattices that allow the local sampling of short sublattice vectors, using essentially only linear algebra but not generic tools such as fully homomorphic encryption or multiparty computation. Our partial trapdoor algorithms generate (partial) preimages of dimension linear in the recovery threshold $t$ but otherwise polylogarithmic in the number of shareholders k. Given sufficiently many short sublattice vectors, these can then be combined to yield short vectors in the original lattice. This process can be repeated an unbounded polynomial number of times without needing the (full) trapdoor owner to intervene. A wide range of lattice-trapdoor-based primitives can be thresholdised non-interactively by simply substituting the trapdoor preimage sampling procedure with our partial analogue.
We prove the one-wayness and indistinguishability properties of our construction, against adversaries who are given at most t-1 partial trapdoors, from the +|-SIS and +|-LWE assumptions, which were previously shown to be implied by the plain SIS and LWE assumptions, respectively. The security proofs extend naturally to the ring or module settings under the respective analogues of these assumptions.
## 2025/890
* Title: SPEEDY: Caught at Last
* Authors: Christina Boura, Patrick Derbez, Baptiste Germon, Rachelle Heim Boissier, Mar|!a Naya-Plasencia
* [Permalink](https://eprint.iacr.org/2025/890)
* [Download](https://eprint.iacr.org/2025/890.pdf)
### Abstract
SPEEDY is a family of ultra-low-latency block ciphers designed by Leander et al. in 2021. In 2023, Boura et al. proposed a differential attack on the full 7-round variant, SPEEDY-7-192. However, shortly thereafter, Beyne and Neyt demonstrated that this attack was invalid, as the dominant differential characteristic it relied upon had probability zero. A similar issue affects another differential attack proposed the same year by Wang et al., which also targets SPEEDY-7-192 and suffers from the same flaw. As a result, the question of finding a valid attack on this cipher remained an open problem.
In this work, we resolve this problem by presenting the first valid differential attack on SPEEDY-7-192. We verify the validity of our distinguisher using the quasidifferential framework. Moreover, our search for the differential distinguisher is significantly more rigorous than in previous works: starting from a pool of one-round trails, our method explores a larger portion of the search space. We also fully exploit probabilistic extensions of the distinguisher to identify optimal parameters for the key recovery step. Our best attack on SPEEDY-7-192 is a chosen-ciphertext attack with data and time complexity of $2^{174.53}$. In addition, we present differential attacks on 4-round SPEEDY-5-192 and 5-round SPEEDY-6-192, which currently represent the best known attacks against these smaller variants.
## 2025/1284
* Title: A Hybrid Algorithm for the Regular Syndrome Decoding Problem
* Authors: Tianrui Wang, Anyu Wang, Kang Yang, Hanlin Liu, Yu Yu, Jun Zhang, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2025/1284)
* [Download](https://eprint.iacr.org/2025/1284.pdf)
### Abstract
Regular Syndrome Decoding (RSD) is a variant of the traditional Syndrome Decoding (SD) problem, where the error vector is divided into consecutive, equal-length blocks, each containing exactly one nonzero element. Recently, RSD has gained significant attention due to its extensive applications in cryptographic constructions, including MPC, ZK protocols, and more. The computational complexity of RSD has primarily been analyzed using two methods: Information Set Decoding (ISD) approach and algebraic approach.
In this paper, we introduce a new hybrid algorithm for solving the RSD problem. This algorithm can be viewed as replacing the meet-in-the-middle enumeration in ISD with a process that solves quadratic equations. Our new algorithm demonstrates superior performance across a wide range of concrete parameters compared to previous methods, including both ISD and algebraic approaches, for parameter sets over both large fields (q = 2^128) and binary fields (q = 2). For parameter sets used in prior works, our algorithm reduces the concrete security of RSD by up to 20 bits compared to the state-of-the-art algorithms. We also provide an asymptotic analysis, identifying a broader parameter region where RSD is solvable in polynomial time compared to ISD and algebraic methods over binary fields. Additionally, we apply our algorithm to evaluate the security of the ZK protocol Wolverine (IEEE S&P 2021) and the OT protocol Ferret (ACM CCS 2020). Our results reduce the security level of Wolverine, which targets a 128-bit security level, to about 111 bits, and also marginally lowers the security of Ferret below the targeted 128-bit level for the first time.
## 2025/1555
* Title: Information-theoretic MPC with Constant Communication Overhead
* Authors: Ashish Choudhury, Ivan Damg|Nrd, Shravani Patil, Arpita Patra
* [Permalink](https://eprint.iacr.org/2025/1555)
* [Download](https://eprint.iacr.org/2025/1555.pdf)
### Abstract
We study the feasibility of constant communication-overhead information-theoretic Multiparty Computation tolerating malicious adversaries in both the synchronous and asynchronous network settings. A simple observation based on the results of Damg\aa rd, Larsen and Neilsen (CRYPTO 2019) allows us to conclude that (a) any statistically-secure MPC with $n = 2t+s$, $s > 0$ requires a communication complexity of $\Theta(\frac{n|C|}{s})$ bits in the synchronous setting; (b) any statistically-secure MPC with $n = 3t+s$, $s > 0$ requires a communication complexity of $\Theta(\frac{n|C|}{s})$ bits in the asynchronous setting; where $C$ denotes the circuit, $n$ denotes the number of parties and $t$ denotes the number of corruptions. Both the results hold even for abort security.
To match the above bounds for $s = \Theta(t)$, we propose two protocols in the synchronous and respectively in the asynchronous setting, both with guaranteed output delivery and a communication complexity of $O(|C|\kappa)$ bits, for a statistical security parameter $\kappa$, a running time of $O(D)$ for circuit depth $D$ (in expectancy in the asynchronous setting). For this, we require circuits with a SIMD structure. Our constructs are the first constant-overhead statistically-secure MPC protocols with optimal resilience.
Our first technical contributions is a verifiable secret sharing (VSS) protocol with constant-overhead per secret through two-dimensional packing. A second contribution is a degree-reduction (from a higher degree packed sharing to a lower degree packed sharing) protocol with constant overhead.
As a bonus, a simplified version of our statistical MPC protocols, plugged with the VSSs derived from the earlier works of Abraham, Asharov, Patil and Patra (EUROCRYPT 2023 and 2024) allow us to obtain perfectly-secure MPC protocols with a communication cost of $O(|C|\kappa)$ bits, where $\kappa = \Theta(\log(n))$, and a running time of $O(D)$ with the resiliency of $n = 3t+\Theta(t)$ in synchronous setting and $n=4t+\Theta(t)$ in the asynchronous setting. These resiliency are optimal in perfect setting due to the lower bounds of Damg\aa rd, Patil, Patra, Roy (Eprint 2025) even for abort security.
## 2025/1556
* Title: CryptoFace: End-to-End Encrypted Face Recognition
* Authors: Wei Ao, Vishnu Naresh Boddeti
* [Permalink](https://eprint.iacr.org/2025/1556)
* [Download](https://eprint.iacr.org/2025/1556.pdf)
### Abstract
Face recognition is central to many authentication, security, and personalized applications. Yet, it suffers from significant privacy risks, particularly arising from unauthorized access to sensitive biometric data. This paper introduces CryptoFace, the first end-to-end encrypted face recognition system with fully homomorphic encryption (FHE). It enables secure processing of facial data across all stages of a face-recognition processrCofeature extraction, storage, and matchingrCowithout exposing raw images or features. We introduce a mixture of shallow patch convolutional networks to support higher-dimensional tensors via patch-based processing while reducing the multiplicative depth and, thus, inference latency. Parallel FHE evaluation of these networks ensures near-resolution-independent latency. On standard face recognition benchmarks, CryptoFace significantly accelerates inference and increases verification accuracy compared to the state-of-the-art FHE neural networks adapted for face recognition. CryptoFace will facilitate secure face recognition systems requiring robust and provable security. The code is available at https://github.com/human-analysis/CryptoFace.
## 2025/1557
* Title: On Achieving ``Best-in-the-Multiverse'' MPC
* Authors: Anasuya Acharya, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam * [Permalink](https://eprint.iacr.org/2025/1557)
* [Download](https://eprint.iacr.org/2025/1557.pdf)
### Abstract
The notion of Best-of-Both-Worlds introduced in the work of Ishai et al. (CRYPTO 2006) investigated whether an MPC protocol can simultaneously provide two incomparable security guarantees: guaranteed output delivery against an honest majority and security with abort against a dishonest majority and provided tight upper and lower bounds in the presence of computationally bounded, i.e., PPT adversaries. Another line of works starting from the work of Chaum (CRYPTO 1989) considered protocols that simultaneously achieved security against an unbounded adversary corrupting a minority of the parties and security against arbitrary corruption by a PPT adversary.
In this work, we generalize previous work to investigate a fundamental challenge of designing an MPC in a multiverse where security is specified with respect to (1) GOD, (2) fairness, (3) security w.r.t. unbounded adversaries, and (4) security with abort. The work of Lucas et al. (PODC 2010) resolved this question when considering threshold adversaries; however, the case of general adversary structures remains open. Our main result completely characterizes when a protocol can simultaneously achieve all properties. Namely, given adversary structures $Z_{\mathsf{GOD}}, Z_{fair}, Z_{S}$ and $Z_{C}$, we provide tight upper and lower bounds for when an MPC protocol can provide GOD, fairness, and security with abort respectively for unbounded and PPT adversaries w.r.t. these adversary structures.
## 2025/1558
* Title: Lower Bounding Update Frequency in Short Accumulators and Vector Commitments
* Authors: Hamza Abusalah, Gaspard Anthoine, Gennaro Avitabile, Emanuele Giunta * [Permalink](https://eprint.iacr.org/2025/1558)
* [Download](https://eprint.iacr.org/2025/1558.pdf)
### Abstract
We study the inherent limitations of additive accumulators and updatable vector commitments (VCs) with constant-size digest (i.e., independent of the number of committed elements).
Specifically, we prove two lower bounds on the expected number of membership proofs that must be updated when a \emph{single} element is added (or updated) in such data structures. Our results imply that when the digest bit length approaches the concrete security level, then the expected number of proofs invalidated due to an append operation for a digest committing to $n$ elements is nearly maximal: $n-\mathsf{negl}(\lambda)$ in the case of exponential-size universes, and $n-o(n)$ for super-polynomial universes. Our results have significant implications for stateless blockchain designs relying on constant-size VCs, suggesting that the overhead of frequent proof updates may offset the benefits of reducing global state storage.
## 2025/1559
* Title: A New Generalized Lattice Attack Against a Family of RSA-Like Cryptosystems
* Authors: Michel Seck, Abdoul Aziz Ciss
* [Permalink](https://eprint.iacr.org/2025/1559)
* [Download](https://eprint.iacr.org/2025/1559.pdf)
### Abstract
Recently, Cotan and Teseleanu (NordSec 2023) published an RSA-like cryptosystem. While in RSA, the public exponent $e$ and the private exponent $d$ are related by the equation $ed - k(p-1)(q-1) = 1$, in their scheme, $e$ and $d$ are related to the equation $ed - k(p^n-1)(q^n-1) = 1$ for some positive integer $n$. Teseleanu (CSCML 2024) showed that one can factor the modulus $N$ using a lattice attack if $d$ is small. In this paper, we extend his attack by showing that if the private exponent is either too small or too large, one can factor $N$ in polynomial time by solving the generalized equation $eu - (p^n - 1)(q^n - 1)v = \pm 1$ using lattice reduction techniques.
## 2025/1560
* Title: On the Termination of the HotStuff Protocol Within the Universally Composable Framework
* Authors: Yuhang Zeng, Zhixin Dong, Xian Xu
* [Permalink](https://eprint.iacr.org/2025/1560)
* [Download](https://eprint.iacr.org/2025/1560.pdf)
### Abstract
HotStuff has gained widespread application in scenarios such as consortium chains in recent years due to its linear view change and pipelined decision making mechanisms. Although there have been studies on the performance of this algorithm, there remains a lack of analysis and formal termination proofs regarding its composability. This paper, for the first time, constructs a comprehensive formal system for the HotStuff protocol in a partially synchronous network environment under the Universally Composable (UC) framework and proves the termination of the HotStuff protocol within the UC framework.
Specifically, we establish the ideal function and demonstrate that the HotStuff protocol UC realizes this ideal function, which guarantees the indistinguishability between the real protocol of HotStuff and the ideal function.
Notably, in the context of network delay attacks, this paper uses a phased time analysis method with an exponential backoff timeout mechanism to show that the protocol can still achieve consensus within a bounded amount of time.
The results of this work not only establish a formal proof paradigm for analyzing termination of BFT protocols in a composable framework, but also provide important theoretical foundations for ensuring reliable termination in industrial-grade blockchain systems (such as the Meta Diem project and ChangrCOan Chain that employ HotStuff).
## 2025/1561
* Title: A Traceable Threshold Asmuth--Bloom Secret Sharing Scheme
* Authors: Maria Leslie, Ratna Dutta
* [Permalink](https://eprint.iacr.org/2025/1561)
* [Download](https://eprint.iacr.org/2025/1561.pdf)
### Abstract
In a t-out-of-n threshold secret sharing scheme, accountability is crucial when a subset of f < t servers collude to leak secret shares. Traceable Threshold Secret Sharing (TTSS) ensures that leaked shares can be traced back to the compromised servers while preventing false accusations through non-imputability. In CryptorCO24, Boneh et al. proposed new definitions and more practical constructions for TTSS based on ShamirrCOs and BlakleyrCOs secret sharing schemes, removing the practical limitation of existing TTSS.
Our work presents a traceable secret sharing scheme built upon an additive variant of the Asmuth-Bloom scheme, relying only on black-box access to the reconstruction box R. In our model, a subset of f < t colluding servers can construct a reconstruction box R that recovers the secret with the assistance of an additional t reA f random shares. We note that integrating tracing in the standard (t, n)-Asmuth-Bloom Secret Sharing (ABSS) scheme exhibits a tracing leakage issue. We fix this limitation by introducing additive variants of ABSS, ABSS-I and ABSS-II that retain the security of the original scheme ABSS while splitting the secret s into t additive components and generating all shares from the additive components of s. Based on ABSS-I, we construct a TTSS scheme, TTSS-I, that introduces traceability into the framework and is proven to be universally traceable in the random oracle model, assuming R is a universally good reconstruction box. We integrate a tracing mechanism in ABSS-II and propose a second scheme, TTSS-II, which extends TTSS-I by additionally concealing partial information about the additive component of the secret s to introduce non-imputability to prevent the tracer from falsely accusing any honest party by fabricating evidence of its corruption. The security of TTSS-II is also in the random oracle model and relies on the hardness of the discrete logarithm problem.
## 2025/1562
* Title: Formally Verified Correctness Bounds for Lattice-Based Cryptography
* Authors: Manuel Barbosa, Matthias J. Kannwischer, Thing-han Lim, Peter Schwabe, Pierre-Yves Strub
* [Permalink](https://eprint.iacr.org/2025/1562)
* [Download](https://eprint.iacr.org/2025/1562.pdf)
### Abstract
Decryption errors play a crucial role in the security of KEMs based on Fujisaki-Okamoto because the concrete security guarantees provided by this transformation directly depend on the probability of such an event being bounded by a small real number. In this paper we present an approach to formally verify the claims of statistical probabilistic bounds for incorrect decryption in lattice-based KEM constructions. Our main motivating example is the PKE encryption scheme underlying ML-KEM. We formalize the statistical event that is used in the literature to heuristically approximate ML-KEM decryption errors and confirm that the upper bounds given in the literature for this event are correct. We consider FrodoKEM as an additional example, to demonstrate the wider applicability of the approach and the verification of a correctness bound without heuristic approximations. We also discuss other (non-approximate) approaches to bounding the probability of ML-KEM decryption.
## 2025/1563
* Title: Optimized Constant-Time Implementation of terSIDH
* Authors: Taehun Kang, Donghoe Heo, Jeonghwan Lee, Suhri Kim, Changmin Lee
* [Permalink](https://eprint.iacr.org/2025/1563)
* [Download](https://eprint.iacr.org/2025/1563.pdf)
### Abstract
Since supersingular isogeny Diffie-Hellman (SIDH) was broken by a polynomial-time attack, several countermeasures were proposed. Among them, terSIDH has been highlighted for its high performance, yet it exposes a side-channel vulnerability. The total isogeny degree depends on the private key, causing variation in isogeny computation times. This dependency makes terSIDH susceptible to timing attacks. The ratio between the worst- and the best-case execution times of terSIDH was about 32.67 times. In this work, we propose the first constant-time terSIDH. By adding dummy operations, we reduce the dependency of isogeny computations on the private key, ensuring that the algorithmrCOs execution time remains constant regardless of the private key. Since such countermeasures are generally slower than their non-constant-time counterparts, we applied additional optimizations to mitigate this overhead. Moreover, we present the first C implementation of terSIDH having 128-bit security. We compared our method against CSIDH-4096, a representative isogeny-based key exchange protocol with the same security level. For key generation, the worst-case of terSIDH, CSIDH-4096, and our constant-time method take 1.77 s, 5.18 s, and 1.58 s, respectively. These results demonstrate that our proposed constant-time method is faster than the worst-case of terSIDH while also being significantly more efficient than CSIDH-4096.
## 2025/1564
* Title: SoK: Blockchain Consensus in the Quantum Age
* Authors: Aleck Nash, Christian Eduardo Terron Garcia, Henry Chimal-Dzul, Kim-Kwang Raymond Choo
* [Permalink](https://eprint.iacr.org/2025/1564)
* [Download](https://eprint.iacr.org/2025/1564.pdf)
### Abstract
Consensus protocols are an important building block in blockchain and blockchain-based systems. The recent focus in developing practical quantum computers reinforces the importance of designing quantum-resistant cryptographic protocols, and in the context of this paper quantum-resistant consensus protocols. In this paper, we systematically review the extant literature on quantum-resistant consensus protocols published between 2019 and 2024. As part of
the review, we identify a number of limitations and challenges and discuss potential future research directions.
## 2025/1565
* Title: Game Changer: A Modular Framework for OPRF Security
* Authors: Karla Friedrichs, Anja Lehmann, Cavit |uzbay
* [Permalink](https://eprint.iacr.org/2025/1565)
* [Download](https://eprint.iacr.org/2025/1565.pdf)
### Abstract
Oblivious pseudorandom functions (OPRFs) allow the blind evaluation of a pseudorandom function, which makes them a versatile building block that enjoys usage in numerous applications. So far, security of OPRFs is predominantly captured in the Universal Composability (UC) framework, where an ideal functionality covers the expected security and privacy properties. While the OPRF functionality appears intuitive at first, the ideal-world paradigm also comes with a number of challenges: from imposing idealized building blocks when building OPRFs, to the lack of modularity, and requiring intricate UC knowledge to securely maneuver their usage. Game-based definitions are a simpler way to cover security properties. They model each property in a single game, which grants modularity in formalizing, proving, and using OPRFs. Interestingly, the few game-based works on OPRFs each re-invent the security model, with considerable variation. Thus, the advantages of the game-based approach remain out of reach: definitions are not easily accessible and comparability across works is low. In this work, we therefore systematize all existing notions into a clear, hierarchical framework. We unify or separate properties, making hidden relations explicit. This effort reveals the necessity of two novel properties: an intermediate privacy notion and a stronger unpredictability notion. Finally, we analyze the two most prominent constructions in our framework: HashDH and 2HashDH. The former does not achieve UC security, but has advantages in applications that require key rotation or updatability; yet it lacks a security analysis. We show that it achieves most security properties in our framework. We also observe that HashDH and 2HashDH do not satisfy our strongest privacy notion, indicating that the guarantees by the UC functionality are not as well understood as we might expect them to be. Overall, we hope that our framework facilitates the usage and design of OPRFs.
## 2025/1566
* Title: Lattice-based Threshold Blind Signatures
* Authors: Sebastian Faller, Guilhem Niot, Michael Reichle
* [Permalink](https://eprint.iacr.org/2025/1566)
* [Download](https://eprint.iacr.org/2025/1566.pdf)
### Abstract
Blind signatures are a central tool for privacy-preserving protocols. They allow users to obtain signatures from a signer without the signer seeing the signed message. For instance, it enables electronic cash: signatures correspond to coins which can be issued by the bank in a privacy-preserving manner via blind signing. To mitigate the risk of key compromise, threshold blind signatures allow the distribution of the signing key amongst N parties. While recent works have focused on improving the security of this primitive in the classical setting, no construction is known to date in the post-quantum setting. We present the first construction of a threshold blind signature secure in the post-quantum setting, based on lattices. We prove its security under an interactive variant of the SIS assumption introduced in [Agrawal et al., CCSrCO22]. Our construction has a reasonable overhead of a factor of roughly 1.4 X to 2.5 X in signature size over comparable non-threshold blind signatures over lattices under heuristic but natural assumptions.
## 2025/1567
* Title: Bootstrappable Fully Homomorphic Attribute-Based Encryption with Unbounded Circuit Depth
* Authors: Feixiang Zhao, Shixin Chen, Man Ho Au, Jian Weng, Huaxiong Wang, Jian Guo
* [Permalink](https://eprint.iacr.org/2025/1567)
* [Download](https://eprint.iacr.org/2025/1567.pdf)
### Abstract
Homomorphic attribute-based encryption (HABE) is a useful cryptographic primitive that supports both fine-grained access control and computation over ciphertexts. However, existing HABE schemes are limited to the homomorphic evaluation of circuits with either bounded depth or a restricted number of inputs. To address this problem, we introduce a bootstrappable, fully homomorphic attribute-based encryption (FHABE) scheme that supports computations of circuits with unbounded depth over cross-attribute ciphertexts. Compared to state-of-the-art schemes, the proposed scheme also has a more lightweight ciphertext and eliminates the reliance on the random oracle model. Additionally, we extend the FHABE to a proxy re-encryption setting, proposing an attribute-based homomorphic proxy re-encryption scheme that facilitates efficient sharing of encrypted data. This scheme is the first lattice-based multi-hop attribute-based proxy re-encryption scheme with unbounded hops of re-encryptions, which may be of independent interest.
## 2025/1568
* Title: Montgomery Curves: Exact Enumeration and Probabilistic Analysis
* Authors: Tsai Yi-Ju
* [Permalink](https://eprint.iacr.org/2025/1568)
* [Download](https://eprint.iacr.org/2025/1568.pdf)
### Abstract
This paper addresses the question of how many distinct Montgomery curves exist over a finite field $\mathbb{F}_p$ for a given order. We provide a complete answer by presenting precise counting formulas from two perspectives: (1) the number of $\mathbb{F}_p$-isomorphism classes, and (2) the number of coefficient pairs $(A,B)$. Additionally, we propose conjectural formulas that approximate the probability of a randomly chosen curve having an order with a specific, cryptographically relevant structure. As a byproduct of our methods, we also establish a novel identity for the Kronecker-Hurwitz class number.
## 2025/1569
* Title: How Hard Can It Be to Formalize a Proof? Lessons from Formalizing CryptoBox Three Times in EasyCrypt
* Authors: Fran|oois Dupressoir, Andreas H|+lsing, Cameron Low, Matthias Meijers, Charlotte Mylog, Sabine Oechsner
* [Permalink](https://eprint.iacr.org/2025/1569)
* [Download](https://eprint.iacr.org/2025/1569.pdf)
### Abstract
Provable security is a cornerstone of modern cryptography, aiming to provide formal and precise security guarantees. However, for various reasons, security proofs are not always properly verified, possibly leading to unwarranted security claims and, in the worst case, deployment of insecure constructions. To further enhance trust and assurance, machine-checked cryptography makes these proofs more formal and rigorous. Unfortunately, the complexity of writing machine-verifiable proofs remains prohibitively high in many interesting use-cases. In this paper, we investigate the sources of this complexity, specifically examining how the style of security definitions influences the difficulty of constructing machine-verifiable proofs in the context of game-playing security.
Concretely, we present a new security proof for the generic construction of a PKAE scheme from a NIKE and AE scheme, written in a code-based, game-playing style a|C la Bellare and Rogaway, and compare it to the same proof written in the style of state-separating proofs, a methodology for developing modular game-playing security proofs. Additionally, we explore a third rCLblendedrCY style designed to avoid anticipated difficulties with the formalization. Our findings suggest that the choice of definition style impacts proof complexityrCoincluding, we argue, in detailed pen-and-paper proofsrCowith trade-offs depending on the proof writerrCOs goals.
## 2025/1570
* Title: Multi-Message Quantum Broadcast with Fine-Grained Access Control
* Authors: Sayatan Ganguly, Shion Samadder Chaudhury
* [Permalink](https://eprint.iacr.org/2025/1570)
* [Download](https://eprint.iacr.org/2025/1570.pdf)
### Abstract
Several subscription-based systems require fine-grained,
dynamic access control, which traditional broadcast
encryption schemes fail to handle efficiently. Attribute-based
and policy-based access structures offer a flexible and scalable
solution by encoding access rules directly into the encryption
mechanism. With the advent and development of quantum
networks, attribute-based and policy-based quantum broadcast
encryption (PBQBE) becomes necessary for enforcing such
controls securely in a post-quantum world. In this paper, we
present a general construction of quantum broadcast encryption
for multiple messages simultaneously, based on routing and
traversing a given attribute-based and, consequently, a policy-based
access tree when a user satisfies a unique policy. Our
scheme can handle dynamic systems with frequently changing
access patterns and can be deployed seamlessly with classical
systems. Compared to existing constructions, our scheme offers
hierarchical access, policy control, scalability, and revocation
while maintaining provable security guarantees.
## 2025/1571
* Title: Attribute-based Quantum Broadcast Encryption with Composite Policies via Symmetric Unitary t-Designs
* Authors: Sayatan Ganguly, Shion Samadder Chaudhury
* [Permalink](https://eprint.iacr.org/2025/1571)
* [Download](https://eprint.iacr.org/2025/1571.pdf)
### Abstract
In an emerging era of quantum technologies, securing quantum communications is paramount. In this paper, we introduce two frameworks for attribute-based quantum broadcast encryption (AB-QBE), enabling fine-grained access control over sensitive quantum data. The first scheme, Multi-Policy Quantum Private Broadcast Encryption (MP-QPBE), leverages symmetric unitary \(t\)-designs to construct a protocol where decryption is possible upon satisfying a composite set of access policies simultaneously. This approach ensures that a user can only access the broadcasted quantum state if their attributes fulfill multiple predefined criteria. In our MP-QPBE, we first perform symmetrization of the initial quantum message for the encryption of the tensor product of distinct pure states, a scenario not directly addressed by previous quantum private broadcasting schemes. We demonstrate that this method is information-theoretically secure. The second scheme, Component-wise Independent Quantum Broadcast Encryption (CI-QBE), offers an alternative, lossless approach where each quantum message is encrypted independently using a unitary \(1\)-design. It provides greater flexibility and is applicable to arbitrary quantum states, including mixed states, without the information loss inherent in symmetrization. We provide a comprehensive security analysis for both constructions, proving their robustness against unauthorized users and adversaries with quantum side information. A comparative analysis highlights the trade-offs between the two schemes in terms of security guarantees, quantum resource requirements, and practical applicability, offering a nuanced perspective on designing secure multi-user quantum communication systems.
## 2025/1572
* Title: Quantum Implementation of MD5
* Authors: Sangmin Cha, GyeongJu Song, Seyoung Yoon, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2025/1572)
* [Download](https://eprint.iacr.org/2025/1572.pdf)
### Abstract
Quantum attacks such as GroverrCOs algorithm reduce the security of classical hash functions such as MD5. In this paper, we present
an efficient quantum circuit for the MD5 hash function and apply GroverrCOs algorithm to perform an effective pre-image attack. Our MD5 quantum
circuit first focuses on reducing quantum circuit depth, while also considering the number of qubits. To this end, we applied DraperrCOs carrylookahead adder to the MD5 quantum circuit and modified its structure.
When DraperrCOs adder was applied to the proposed MD5 structure, there
was an approximately 81.4% reduction compared to before application.
As a result, the proposed MD5 quantum circuit uses only 858 qubits and
has a depth of 7,598.
## 2025/1573
* Title: OneTwoPAKE: Two-Round Strong Asymmetric PAKE with Ideal Security
* Authors: Yashvanth Kondi, Ian McQuoid, Kelsey Melissaris, Claudio Orlandi, Lawrence Roy, LaKyah Tyner
* [Permalink](https://eprint.iacr.org/2025/1573)
* [Download](https://eprint.iacr.org/2025/1573.pdf)
### Abstract
Strong Asymmetric Password-Authenticated Key Exchange (saPAKE) enables a client, holding only a low-entropy password, to repeatedly establish shared high-entropy session keys with a server holding a digest of the expected password. Integrally, the only online attacks afforded to the adversary are those inevitable impersonation and dictionary attacks. As opposed to previous modeling, saPAKE addionally requires that any offline password search against the serverrCOs storage takes place
after adaptive server compromise.
We present OneTwoPAKE, the first saPAKE protocol to simultaneously:
1. realize the full (unweakened ) strong aPAKE functionality;
2. not admit a speedup in an offline password search; (aka, has simulation-rate of 1 );
3. use only a single round trip, with the client speaking first; and
4. avoid generic algebraic models.
Similar to prior work, we instantiate our saPAKE from an OPRF over insecure channels secure against adaptive server compromise. In contrast to prior work, our OPRF is online-extractable and input-committing, enabling our protocol to realize the full saPAKE functionality.
Of independent interest are our OPRF functionality and construction. We introduce the first formal model of such an OPRF, and our OPRF protocol is the first Dodis-Yampolskiy-based OPRF proven UC-secure against malicious adversaries without authenticated channels.
Our framework demonstrates the feasibility of achieving all of the above properties simultaneously. Though our constructions are not as efficient as those of prior work, our saPAKE boasts the minimal round complexity, achieves full security, and, in terms of idealized models, relies only on the random oracle model. As future work may further close the efficiency gap, our framework may lead to practically deployable solutions.
## 2025/1574
* Title: Information-Theoretic Random-Index PIR
* Authors: Sebastian Kolby, Lawrence Roy, Jure Sternad, Sophia Yakoubov
* [Permalink](https://eprint.iacr.org/2025/1574)
* [Download](https://eprint.iacr.org/2025/1574.pdf)
### Abstract
A Private Information Retrieval (PIR) protocol allows a client to learn the $i$th row of a database held by one or more servers, without revealing $i$ to the servers. A Random-Index PIR (RPIR) protocol, introduced by Gentry et al. (TCC 2021), is a PIR protocol where, instead of being chosen by the client, $i$ is random. This has applications in e.g. anonymous committee selection. Both PIR and RPIR protocols are interesting only if the communication complexity is smaller than the database size; otherwise, the trivial solution where the servers send the entire database suffices.
Unlike PIR, where the client must send at least one message (to encode information about $i$), RPIR can be executed in a single round of server-to-client communication. In this paper, we study such one-round, information-theoretic RPIR protocols. The only known construction in this setting is SimpleMSRPIR (Gentry et al.), which requires the servers to communicate approximately $\frac{N}{2}$ bits, $N$ being the database size. We show an $\Omega(\sqrt{N})$ lower bound on communication complexity for one-round two-server information-theoretic RPIR, and a sublinear upper bound. Finally, we show how to use a sublinear amount of database-independent correlated randomness among multiple servers to get near-optimal online communication complexity (the size of one row plus the size of one index description per server).
## 2025/1575
* Title: BitPriv: A Privacy-Preserving Protocol for DeFi Applications on Bitcoin
* Authors: Ioannis Alexopoulos, Zeta Avarikioti, Paul Gerhart, Matteo Maffei, Dominique Schr||der
* [Permalink](https://eprint.iacr.org/2025/1575)
* [Download](https://eprint.iacr.org/2025/1575.pdf)
### Abstract
Bitcoin secures over a trillion dollars in assets but remains largely absent from decentralized finance (DeFi) due to its restrictive scripting language. The emergence of BitVM, which enables verification of arbitrary off-chain computations via on-chain fraud proofs, opens the door to expressive Bitcoin-native applications without altering consensus rules. A key challenge for smart contracts executed on a public blockchain, however, is the privacy of data: for instance, bid privacy is crucial in auctions and transaction privacy is leveraged in MEV-mitigation techniques such as proposer-builder separation. While different solutions have been recently proposed for Ethereum, these are not applicable to Bitcoin.
In this work, we present BitPriv, the first Bitcoin-compatible protocol to condition payments based on the outcome of a secure two-party computation (2PC). The key idea is to let parties lock collateral on-chain and to evaluate a garbled circuit off-chain: a cut-and-choose mechanism deters misbehavior and any violation can be proven and punished on-chain via BitVM. This design achieves security against rational adversaries, ensuring that deviation is irrational under financial penalties.
We showcase the new class of applications enabled by BitPriv as well as evaluate its performance through a privacy-preserving double-blind marketplace in Bitcoin. In the optimistic case, settlement requires only two transactions and under \$3 in fees; disputes are more expensive (ree\$507) with their cost tied to the specific BitVM implementation, but their mere feasibility acts as a strong deterrent. BitPriv provides a blueprint for building enforceable, privacy-preserving DeFi primitives on Bitcoin without trusted hardware, sidechains, or protocol changes.
## 2025/1576
* Title: Compressed verification for post-quantum signatures with long-term public keys
* Authors: Gustavo Banegas, Ana|2lle Le D|-v|-hat, Benjamin Smith
* [Permalink](https://eprint.iacr.org/2025/1576)
* [Download](https://eprint.iacr.org/2025/1576.pdf)
### Abstract
Many signature applications---such as root certificates,
secure software updates, and authentication protocols---involve
long-lived public keys that are transferred or installed once
and then used for many verifications.
This key longevity makes post-quantum signature schemes with
conservative assumptions (e.g., structure-free lattices)
attractive for long-term security.
But many such schemes, especially those with short
signatures, suffer from extremely large public keys. Even
in scenarios where bandwidth is not a major concern, large
keys increase storage costs and slow down verification.
We address this with a method to replace large public keys in
GPV-style signatures with smaller, private verification keys.
This significantly reduces verifier storage and
runtime while preserving security. Applied to
the conservative, short-signature schemes
\Wave and \Squirrels,
our method compresses \Squirrels[-I] keys from
\SI{665}{\kilo\byte} to \SI{20.7}{\kilo\byte} and \Wave[822] keys
from \SI{3.5}{\mega\byte} to \SI{207.97}{\kilo\byte}.
## 2025/1577
* Title: A Template SCA Attack on the Kyber/ML-KEM Pair-Pointwise Multiplication
* Authors: Sedric Nkotto
* [Permalink](https://eprint.iacr.org/2025/1577)
* [Download](https://eprint.iacr.org/2025/1577.pdf)
### Abstract
Kyber a.k.a ML-KEM has been stardardized by NIST under FIPS-203 and will definetely in the coming years be implemented in several commercial products. However the resilience of implementations against side channel attacks is still an open
and practical concern. One of the drawbacks of the ongoing side channel analysis
research related to PQC schemes is the availability of open source datasets. Luckily
some opensource datasets start popping up. For instance the one recently published
by Rezaeezade et al. in [2]. This dataset captures power consumption during a pair-
pointwise multiplication occuring in the course of ML-KEM decapsulation process
and involving the decapsulation (sub)key and ciphertexts. In this paper we present
a template side channel attack targetting that operation, which yields a complete
recovery of the decapsulation secret (sub)key.
## 2025/1578
* Title: Back to the future: simple threshold decryption secure against adaptive corruptions
* Authors: Victor Shoup
* [Permalink](https://eprint.iacr.org/2025/1578)
* [Download](https://eprint.iacr.org/2025/1578.pdf)
### Abstract
We present a practical, non-interactive threshold decryption scheme. It can be proven CCA secure with respect to adaptive corruptions in the random oracle model under a standard computational assumption, namely, the DDH assumption. Our scheme, called TDH2a, is a minor tweak on the TDH2 scheme presented by Shoup and Gennaro at Eurocrypt 1998, which was proven secure against static corruptions under the same assumptions. The design and analysis of TDH2a are based on a straightforward extension of the simple information-theoretic argument underlying the security of the Cramer-Shoup encryption scheme presented at Crypto 1998.
## 2025/1579
* Title: TACITA: Threshold Aggregation without Client Interaction
* Authors: Varun Madathil, Arthur Lazzaretti, Zeyu Liu, Charalampos Papamanthou * [Permalink](https://eprint.iacr.org/2025/1579)
* [Download](https://eprint.iacr.org/2025/1579.pdf)
### Abstract
Secure aggregation enables a central server to compute the sum of client inputs without learning any individual input, even in the presence of dropouts or partial participation. This primitive is fundamental to privacy-preserving applications such as federated learning, where clients collaboratively train models without revealing raw data.
We present a new secure aggregation protocol, TACITA, in the single-server setting that satisfies four critical properties simultaneously: (1) one-shot communication from clients with no per-instance setup, (2) input-soundness, i.e. the server cannot manipulate the ciphertexts, (3) constant-size communication per client, independent of the number of participants per-instance, and (4) robustness to client dropouts
Previous works on secure aggregation - Willow and OPA (CRYPTO'25) that achieve one-shot communication do not provide input soundness, and allow the server to manipulate the aggregation. They consequently do not achieve full privacy and only achieve Differential Privacy guarantees at best. We achieve full privacy at the cost of assuming a PKI. Specifically, TACITA relies on a novel cryptographic primitive we introduce and realize: succinct multi-key linearly homomorphic threshold signatures (MKLHTS), which enables verifiable aggregation of client-signed inputs with constant-size signatures.
To encrypt client inputs, we adapt the Silent Threshold Encryption (STE) scheme of Garg et al. (CRYPTO 2024) to support ciphertext-specific decryption and additive homomorphism.
We formally prove security in the Universal Composability framework and demonstrate practicality through an open-source proof-of-concept implementation, showing our protocol achieves scalability without sacrificing efficiency or requiring new trust assumptions.
## 2025/1580
* Title: IronDict: Transparent Dictionaries from Polynomial Commitments
* Authors: Hossein Hafezi, Alireza Shirzad, Benedikt B|+nz, Joseph Bonneau
* [Permalink](https://eprint.iacr.org/2025/1580)
* [Download](https://eprint.iacr.org/2025/1580.pdf)
### Abstract
We present IronDict, a transparent dictionary construction based on polynomial commitment schemes. Transparent dictionaries enable an untrusted server to maintain a mutable dictionary and provably serve clients lookup queries. A major open challenge is supporting efficient auditing by lightweight clients. Previous solutions either incurred high server costs (limiting throughput) or high client lookup verification costs, hindering them from modern messaging key transparency deployments with billions of users. Our construction makes black-box use of a generic multilinear polynomial commitment scheme and inherits its security notions, i.e. binding and zero-knowledge. We implement our construction with the recent KZH scheme and find that a dictionary with $1$ billion entries can be verified on a consumer-grade laptop in $35$ ms, a $300\times$ improvement over the state of the art, while also achieving $150{,}000\times$ smaller proofs ($8$ KB). In addition, our construction ensures perfect privacy with concretely efficient costs for both the client and the server. We also show fast-forwarding techniques based on incremental verifiable computation (IVC) and checkpoints to enable even faster client auditing.
## 2025/1581
* Title: Cryptanalysis of ChiLow with Cube-Like Attacks
* Authors: Shuo Peng, Jiahui He, Kai Hu, Zhongfeng Niu, Shahram Rasoolzadeh, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2025/1581)
* [Download](https://eprint.iacr.org/2025/1581.pdf)
### Abstract
Proposed in EUROCRYPT~2025, \chilow is a family of tweakable block ciphers and a related PRF built on the novel nonlinear $\chichi$ function, designed to enable efficient and secure embedded code encryption.
The only key-recovery results of \chilow are from designers which can reach at most 4 out of 8 rounds, which is not enough for a low-latency cipher like \chilow: more cryptanalysis efforts are expected.
Considering the low-degree $\chichi$ function, we present three kinds of cube-like attacks on \chilow-32 under both single-tweak and multi-tweak settings, including
\begin{itemize}
\item[-] a \textit{conditional cube attack} in the multi-tweak setting, which enables full key recovery for 5-round and 6-round instances with time complexities $2^{32}$ and $2^{120}$, data complexities $2^{23.58}$ and $2^{40}$, and negligible memory requirements, respectively.
\item[-] a \textit{borderline cube attack} in the multi-tweak setting, which recovers the full key of 5-round \chilow-32 with time, data, and memory complexities of $2^{32}$, $2^{18.58}$, and $2^{33.56}$, respectively. For 6-round \chilow-32, it achieves full key recovery with time, data, and memory complexities of $2^{34}$, $2^{33.58}$, and $2^{54.28}$, respectively.
Both attacks are practical.
\item [-] an \textit{integral attack} on 7-round \chilow-32 in the single-tweak setting.
By combining a 4-round borderline cube with three additional rounds, we reduce the round-key search space from $2^{96}$ to $2^{73}$. Moreover, we present a method to recover the master key based on round-key information, allowing us to recover the master key for 7-round \chilow-32 with a time complexity of $2^{127.78}$.
\end{itemize}
All of our attacks respect security claims made by the designers.
Though our analysis does not compromise the security of the full 8-round \chilow, we hope that our results offer valuable insights into its security properties.
## 2025/1582
* Title: Breaking Omert|a: On Threshold Cryptography, Smart Collusion, and Whistleblowing
* Authors: Mahimna Kelkar, Aadityan Ganesh, Aditi Partap, Joseph Bonneau, S. Matthew Weinberg
* [Permalink](https://eprint.iacr.org/2025/1582)
* [Download](https://eprint.iacr.org/2025/1582.pdf)
### Abstract
Cryptographic protocols often make honesty assumptions---e.g., fewer than $t$ out of $n$ participants are adversarial. In practice, these assumptions can be hard to ensure, particularly given monetary incentives for participants to collude and deviate from the protocol.
In this work, we explore combining techniques from cryptography and mechanism design to discourage collusion. We formalize protocols in which colluders submit a cryptographic proof to whistleblow against their co-conspirators, revealing the dishonest behavior publicly. We provide general results on the cryptographic feasibility, and show how whistleblowing fits a number of applications including secret sharing, randomness beacons, and anonymous credentials.
We also introduce smart collusion---a new model for players to collude. Analogous to blockchain smart contracts, smart collusion allows colluding parties to arbitrarily coordinate and impose penalties on defectors (e.g., those that blow the whistle). We show that unconditional security is impossible against smart colluders even when whistleblowing is anonymous and can identify all colluding players.
On the positive side, we construct a whistleblowing protocol that requires only a small deposit and can protect against smart collusion even with roughly $t$ times larger deposit.
## 2025/1583
* Title: Compact Lattice-Coded (Multi-Recipient) Kyber without CLT Independence Assumption
* Authors: Shuiyin Liu, Amin Sakzad
* [Permalink](https://eprint.iacr.org/2025/1583)
* [Download](https://eprint.iacr.org/2025/1583.pdf)
### Abstract
This work presents a joint design of encoding and encryption procedures for public key encryptions (PKEs) and key encapsulation mechanism (KEMs) such as Kyber, without relying on the assumption of independent decoding noise components, achieving reductions in both communication overhead (CER) and decryption failure rate (DFR). Our design features two techniques: ciphertext packing and lattice packing. First, we extend the Peikert-Vaikuntanathan-Waters (PVW) method to Kyber: $\ell$ plaintexts are packed into a single ciphertext. This scheme is referred to as P$_\ell$-Kyber. We prove that the P$_\ell$-Kyber is IND-CCA secure under the M-LWE hardness assumption. We show that the decryption decoding noise entries across the $\ell$ plaintexts (also known as layers) are mutually independent. Second, we propose a cross-layer lattice encoding scheme for the P$_\ell$-Kyber, where every $\ell$ cross-layer information symbols are encoded to a lattice point. This way we obtain a \emph{coded} P$_\ell$-Kyber, where the decoding noise entries for each lattice point are mutually independent. Therefore, the DFR analysis does not require the assumption of independence among the decryption decoding noise entries. Both DFR and CER are greatly decreased thanks to ciphertext packing and lattice packing. We demonstrate that with $\ell=24$ and Leech lattice encoder, the proposed coded P$_\ell$-KYBER1024 achieves DFR $<2^{-281}$ and CER $ = 4.6$, i.e., a decrease of CER by $90\%$ compared to KYBER1024. If minimizing CPU runtime is the priority, our C implementation shows that the E8 encoder provides the best trade-off among runtime, CER, and DFR. Additionally, for a fixed plaintext size matching that of standard Kyber ($256$ bits), we introduce a truncated variant of P$_\ell$-Kyber that deterministically removes ciphertext components carrying surplus information bits. Using $\ell=8$ and E8 lattice encoder, we show that the proposed truncated coded P$_\ell$-KYBER1024 achieves a $10.2\%$ reduction in CER and improves DFR by a factor of $2^{30}$ relative to KYBER1024. Finally, we demonstrate that constructing a multi-recipient PKE and a multi-recipient KEM (mKEM) using the proposed truncated coded P$_\ell$-KYBER1024 results in a $20\%$ reduction in bandwidth consumption compared to the existing schemes.
## 2025/1584
* Title: PriSrv+: Privacy and Usability-Enhanced Wireless Service Discovery with Fast and Expressive Matchmaking Encryption
* Authors: Yang Yang, Guomin Yang, Yingjiu Li, Pengfei WU, Rui Shi, Minming Huang, Jian Weng, HweeHwa Pang, Robert H. Deng
* [Permalink](https://eprint.iacr.org/2025/1584)
* [Download](https://eprint.iacr.org/2025/1584.pdf)
### Abstract
Service discovery is a fundamental process in wireless networks, enabling devices to find and communicate with services dynamically, and is critical for the seamless operation of modern systems like 5G and IoT. This paper introduces PriSrv+, an advanced privacy and usability-enhanced service discovery protocol for modern wireless networks and resource-constrained environments. PriSrv+ builds upon PriSrv (NDSS'24), by addressing critical limitations in expressiveness, privacy, scalability, and efficiency, while maintaining compatibility with widely-used wireless protocols such as mDNS, BLE, and Wi-Fi.
A key innovation in PriSrv+ is the development of Fast and Expressive Matchmaking Encryption (FEME), the first matchmaking encryption scheme capable of supporting expressive access control policies with an unbounded attribute universe, allowing any arbitrary string to be used as an attribute. FEME significantly enhances the flexibility of service discovery while ensuring robust message and attribute privacy. Compared to PriSrv, PriSrv+ optimizes cryptographic operations, achieving 7.62$\times$ faster for encryption and 6.23$\times$ faster for decryption, and dramatically reduces ciphertext sizes by 87.33$\%$. In addition, PriSrv+ reduces communication costs by 87.33$\%$ for service broadcast and 86.64$\%$ for anonymous mutual authentication compared with PriSrv. Formal security proofs confirm the security of FEME and PriSrv+. Extensive evaluations on multiple platforms demonstrate that PriSrv+ achieves superior performance, scalability, and efficiency compared to existing state-of-the-art protocols.
## 2025/1585
* Title: LEAF: Compact and Efficient Blind Signature from Code-based Assumptions
* Authors: Yi-Fu Lai, Edoardo Persichetti
* [Permalink](https://eprint.iacr.org/2025/1585)
* [Download](https://eprint.iacr.org/2025/1585.pdf)
### Abstract
Recently, Hanzlik, Lai, Paracucchi, Slamanig, Tang proposed several blind signature frameworks, collectively named Tanuki(s) (Asiacrypt'25), built upon cryptographic group actions. Their work introduces novel techniques and culminates in a concurrently secure blind signature framework. Straightforward instantiations based on CSIDH (CSI-FiSh) and LESS yield signature sizes of 4.5 KB and 64 KB respectively, providing the first efficient blind signatures in the isogeny-based and code-based literature allowing concurrent executions.


In this work, we improve the code-based instantiations by using the canonical form of linear equivalent codes by a careful treatment. However, the canonical form does not naturally support a group action structure, which is central to the security proofs of Tanuki(s). Consequently and unfortunately, the original security guarantees do not directly apply. To address this, we develop two distinct non-black-box reductions for both blindness and the one-more unforgeability.
In the end, the improvements do not compromise the security.

This results in a concurrently secure code-based blind signature scheme with a compact signature size of 4.4 KB, which is approximately 1% smaller than the isogeny-based one. We also provide a C implementation where the signing time in 99ms and 268 Mcycles on an Intel i7 2.3~GHz CPU. We also look forward to our approaches benefiting advanced constructions built on top of LESS in the future.
## 2025/1586
* Title: A Note on Feedback-PRF Mode of KDF from NIST SP 800-108
* Authors: Ritam Bhaumik, Avijit Dutta, Tetsu Iwata, Ashwin Jha, Kazuhiko Minematsu, Mridul Nandi, Yu Sasaki, Meltem S||nmez Turan, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2025/1586)
* [Download](https://eprint.iacr.org/2025/1586.pdf)
### Abstract
We consider FB-PRF, one of the key derivation functions defined in NIST SP 800-108 constructed from a pseudorandom function in a feedback mode. The standard allows some flexibility in the specification, and we show that one specific instance of FB-PRF allows an efficient distinguishing attack.
## 2025/1587
* Title: Secure Agents
* Authors: Nakul Khambhati, Joonwon Lee, Gary Song, Rafail Ostrovsky, Sam Kumar * [Permalink](https://eprint.iacr.org/2025/1587)
* [Download](https://eprint.iacr.org/2025/1587.pdf)
### Abstract
Organizations increasingly need to pool their sensitive data for collaborative computation while keeping their own data private from each other. One approach is to use a family of cryptographic protocols called Secure Multi-Party Computation (MPC). Another option is to use a set of cloud services called clean rooms. Unfortunately, neither approach is satisfactory. MPC is orders of magnitude more resource-intensive than regular computation, making it impractical for workloads like data analytics and AI. Clean rooms do not give users the flexibility to perform arbitrary computations.
We propose and develop an approach and system called a secure agent and utilize it to create a virtual clean room, Flexroom, that is both performant and flexible. Secure agents enable parties to create a phantom identity that they can collectively control, using maliciously secure MPC, which issues API calls to external services with parameters that remain secret from all participating parties. Importantly, in Flexroom, the secure agent uses MPC not to perform the computation itself, but instead merely to orchestrate the computation in the cloud, acting as a distinct trusted entity jointly governed by all parties. As a result, Flexroom enables collaborative computation with unfettered flexibility, including the ability to use convenient cloud services. By design, the collaborative computation runs at plaintext speeds, so the overhead of Flexroom will be amortized over a long computation.
## 2025/1588
* Title: Query-Optimal IOPPs for Linear-TIme Encodable Codes
* Authors: Anubhav Baweja, Pratyush Mishra, Tushar Mopuri, Matan Shtepel
* [Permalink](https://eprint.iacr.org/2025/1588)
* [Download](https://eprint.iacr.org/2025/1588.pdf)
### Abstract
We present the first IOPP for a linear-time encodable code that achieves linear prover time and $O(\lambda)$ query complexity, for a broad range of security parameters $\lambda$. No prior work is able to simultaneously achieve this efficiency: it either supports linear-time encodable codes but with worse query complexity [FICS; ePrint 2025], or achieves $O(\lambda)$ query complexity but only for quasilinear-time encodable codes [Minzer, Zheng; FOCS 2025]. Furthermore, we prove a matching lower bound that shows that the query complexity of our IOPP is asymptotically optimal (up to additive factors) for codes with constant rate.
We obtain our result by tackling a ubiquitous subproblem in IOPP constructions: checking that a batch of claims hold. Our novel solution to this subproblem is twofold. First, we observe that it is often sufficient to ensure that, with all but negligible probability, most of the claims hold. Next, we devise a new `lossy batching' technique which convinces a verifier of the foregoing promise with lower query complexity than that required to convince it that all the claims hold. This method differs significantly from the line-versus-point test used to achieve query-optimal IOPPs (for quasilinear-time encodable codes) in prior work [Minzer, Zheng; FOCS 2025], and may be of independent interest.
Our IOPP can handle all codes that support efficient codeswitching [Ron-Zewi, Rothblum; JACM 2024], including several linear-time encodable codes. Via standard techniques, our IOPP can be used to construct the first (to the best of our knowledge) IOP for NP with $O(n)$ prover time and $O(\lambda)$ query complexity. We additionally show that our IOPP (and by extension the foregoing IOP) is round-by-round tree-extractable and hence can be used to construct a SNARK in the random oracle model with $O(n)$ prover time and $O(\lambda \log n)$ proof size.
## 2025/1589
* Title: Symmetric Group-Based Public-Key Cryptosystem with Large Prime Moduli * Authors: Kaveh Dastouri
* [Permalink](https://eprint.iacr.org/2025/1589)
* [Download](https://eprint.iacr.org/2025/1589.pdf)
### Abstract
We introduce a novel public-key cryptosystem based on the symmetric groups $S_{p_1} \times S_{p_2} $, where \( p_1, p_2 \) are large primes. The modulus \( N = f(\lambda_1) \cdot f(\lambda_2) \), with partitions \( \lambda_1 \in P(p_1) \), \( \lambda_2 \in P(p_2) \), and \( f(\lambda_i) = |C_{\lambda_i}| \cdot m_1(\lambda_i) \), leverages conjugacy class sizes to ensure large prime factors, including \( p_1, p_2 \). A partition selection strategy using non-repeated composition numbers guarantees robust security, surpassing RSA by supporting multiple large primes and deterministic key generation. Efficient decryption is achieved via known factorizations, and a lightweight symmetric hash primitive provides message authentication. We provide rigorous security analysis, practical implementation, and comparisons to multi-prime RSA, advancing algebraic cryptography for modern applications.
## 2025/1590
* Title: The AIIP Problem: Toward a Post-Quantum Hardness Assumption from Affine Iterated Inversion over Finite Fields
* Authors: MINKA MI NGUIDJOI Thierry Emmanuel
* [Permalink](https://eprint.iacr.org/2025/1590)
* [Download](https://eprint.iacr.org/2025/1590.pdf)
### Abstract
We introduce the Affine Iterated Inversion Problem (AIIP), a new candidate hard problem
for post-quantum cryptography, based on inverting iterated polynomial maps over finite fields.
Given a polynomial f ree Fq[x] of degree d reN 2, an iteration parameter n, and a target y ree Fq,
AIIP requires finding an input x such that f(n)(x) = y, where f(n) denotes the n-fold composi
tion of f. We establish the computational hardness of AIIP through two independent analytical
frameworks: first, by establishing a formal connection to the Discrete Logarithm Problem in
the Jacobian of hyperelliptic curves of exponentially large genus; second, via a polynomial
time reduction to solving structured systems of multivariate quadratic (MQ) equations. The
f
irst construction provides number-theoretic evidence for hardness by embedding an AIIP in
stance into the arithmetic of a high-genus curve, while the second reduction proves worst-case
hardness relative to the NP-hard MQ problem. For the quadratic case f(x) = x2 + +#, we
show that the induced MQ system is heuristically indistinguishable from a random system, and
we formalize a sufficient condition for its pseudorandomness under a standard cryptographic
assumption. We provide a detailed security analysis against classical and quantum attacks,
derive concrete parameters for standard security levels, and discuss the potential of AIIP as
a foundation for digital signatures and public-key encryption. This dual hardness foundation,
rooted in both algebraic geometry and multivariate algebra, positions AIIP as a versatile and
promising primitive for post-quantum cryptography.
## 2025/1591
* Title: HE-SecureNet: An Efficient and Usable Framework for Model Training via Homomorphic Encryption
* Authors: Thomas Schneider, Huan-Chih Wang, Hossein Yalame
* [Permalink](https://eprint.iacr.org/2025/1591)
* [Download](https://eprint.iacr.org/2025/1591.pdf)
### Abstract
Energy-efficient edge devices are essential for the widespread deployment of machine learning (ML) services. However, their limited computational capabilities make local model training infeasible. While cloud-based training offers a scalable alternative, it raises serious privacy concerns when sensitive data is outsourced. Homomorphic Encryption (HE) enables computation directly on encrypted data and has emerged as a promising solution to this privacy challenge. Yet, current HE-based training frameworks face several shortcomings: they often lack support for complex models and non-linear functions, struggle to train over multiple epochs, and require cryptographic expertise from end users.
We present HE-SecureNet, a novel framework for privacy-preserving model training on encrypted data in a single-clientrCoserver setting, using hybrid HE cryptosystems. Unlike prior HE-based solutions, HE-SecureNet supports advanced models such as Convolutional Neural Networks and handles non-linear operations including ReLU, Softmax, and MaxPooling. It introduces a level-aware training strategy that eliminates costly ciphertext level alignment across epochs. Furthermore, HE-SecureNet automatically converts ONNX models into optimized secure C++ training code, enabling seamless integration into privacy-preserving ML pipelinerCowithout requiring cryptographic knowledge.
Experimental results demonstrate the efficiency and practicality of our approach. On the Breast Cancer dataset, HE-SecureNet achieves a 5.2|u speedup and 33% higher accuracy compared to ConcreteML (Zama) and TenSEAL (OpenMined). On the MNIST dataset, it reduces CNN training latency by 2|u relative to Glyph (Lou et al., NeurIPSrCO20), and cuts communication overhead by up to 66|u on MNIST and 42|u on CIFAR-10 compared to MPC-based solutions.
## 2025/1592
* Title: MegaBlocks: Breaking the Logarithmic I/O-Overhead Barrier for Oblivious RAM
* Authors: Gilad Asharov, Eliran Eiluz, Ilan Komargodski, Wei-Kai Lin
* [Permalink](https://eprint.iacr.org/2025/1592)
* [Download](https://eprint.iacr.org/2025/1592.pdf)
### Abstract
Oblivious RAM (ORAM) is a central cryptographic primitive that enables secure memory access while hiding access patterns. Among existing ORAM paradigms, hierarchical ORAMs were long considered impractical despite their asymptotic optimality. However, recent advancements (FutORAMa, CCS'23) demonstrate that hierarchical ORAM-based schemes can be made efficient given sufficient client-side memory. In this work, we present a new hierarchical ORAM construction that achieves practical performance without requiring large local memory.
From a theoretical standpoint, we identify that there is a gap in the literature concerning the asymmetric setting, where the logical word size is asymptotically smaller than the physical memory block size. In this scenario, the best-known construction (OptORAMa, J.\ ACM '23,) turns every logical query into $O(\log N)$ physical memory accesses (quantity known as ``I/O overhead''), whereas the lower bound of Komargodski and Lin (CRYPTO'21) implies that $\Omega(\log N /\log\log N)$ accesses are needed.
We close this gap by constructing an optimal ORAM for the asymmetric setting, achieving an I/O overhead of $O(\log N / \log\log N)$. Our construction features exceptionally small constants (between 1 and 4, depending on the block size) and operates without requiring large local memory. We implement our scheme and compare it to PathORAM (CCS'13) and FutORAMa, demonstrating significant improvement. For 1TB logical memory, our construction obtains $\times 10$-$\times 30$ reduction in I/O overhead and bandwidth compared to PathORAM, and $\times 7$--$\times 26$ improvement over FutORAMa. This improvement applies when those schemes weren't designed to operate on large blocks, as in our settings, and the exact improvement depends on the physical block size and the exact local memory available.
--- Synchronet 3.21a-Linux NewsLink 1.2