From Newsgroup: sci.crypt

## In this issue
1. [2025/1609] Many-time Linkable Ring Signatures
2. [2025/1657] ORQ: Complex Analytics on Private Data with Strong ...
3. [2025/1663] IVC in the Open-and-sign Random Oracle Model
4. [2025/1666] Trout: Two-Round Threshold ECDSA from Class Groups
5. [2025/1667] Persistence of Hourglass(-like) Structure: Improved ...
6. [2025/1668] Post-Quantum Cryptography in Practice: A Literature ...
7. [2025/1669] Experience from UNITA Elections: Reconciling ...
8. [2025/1670] Mixderive: A New Framework of Deriving Linear ...
9. [2025/1671] QKD Oracles for Authenticated Key Exchange
10. [2025/1672] All Paths Lead to the Root
11. [2025/1673] Strong Designated Verifier Signatures with Non- ...
12. [2025/1674] Secure Rate-Distortion-Perception Trade-Off with ...
13. [2025/1675] Surtr: Transparent Verification with Simple yet ...
14. [2025/1676] Honest Majority Constant-Round MPC with Linear ...
15. [2025/1677] DiffierCoHellman Key Exchange from Commutativity to ...
16. [2025/1678] Two-Key Variant of the Four-Round Cascading LRW1
17. [2025/1679] SoK: Connecting the Dots in Privacy-Preserving ML - ...
18. [2025/1680] ChipmunkRing: A Practical Post-Quantum Ring ...
19. [2025/1681] Modular Forms and Hecke Operators for Post-Quantum ...
20. [2025/1682] pod: An Optimal-Latency, Censorship-Free, and ...
21. [2025/1683] Proving the Security of PeerDAS without the AGM
22. [2025/1684] FHEMaLe: Framework for Homomorphic Encrypted ...
23. [2025/1685] Toss: Garbled PIR from Table-Only Stacking
24. [2025/1686] Honest Users Make Honest Mistakes: A Framework for ...
25. [2025/1687] Web3 Recovery Mechanisms and User Preferences
26. [2025/1688] SUMMER: Recursive Zero-Knowledge Proofs for ...
27. [2025/1689] IPCrypt: Optimal, Practical Encryption of IP ...
28. [2025/1690] A Tight Quantum Algorithm for Multiple Collision Search
29. [2025/1691] Pilvi: Lattice Threshold PKE with Small Decryption ...
30. [2025/1692] Combined Stability: Protecting against Combined Attacks
31. [2025/1693] Quasi-perfect (de)compression of elliptic curve ...
32. [2025/1694] Lattice Reduction via Dense Sublattices: A ...
33. [2025/1695] Mk-PIR: Multi-Keyword Private Information Retrieval
34. [2025/1696] Threshold ECDSA in Two Rounds
35. [2025/1697] Extract Discriminative Features: Profiled Side- ...
36. [2025/1698] SNARK Lower Bounds via Communication Complexity
37. [2025/1699] A Constant-Rate Compiler for MPC over Noisy Networks
38. [2025/1700] Computationally-Sound Symbolic Cryptography in Lean
39. [2025/1701] BPSec-MLS: Asynchronous Key Agreement for Space ...
40. [2025/1702] Lattice-Based Group Signatures in the Standard ...
41. [2025/1703] Updatable Signature from Lattices
42. [2025/1704] Data Anonymisation with the Density Matrix Classifier
43. [2025/1705] Security Amplification of Threshold Signatures in ...
44. [2025/1706] Kani's lemma from Clifford algebra
45. [2025/1707] Is It Even Possible? On the Parallel Composition of ...
46. [2025/1708] The Semantic Holder (SH): Algebraic Extraction for ...
47. [2025/1709] The zkVot Protocol: A Distributed Computation ...
48. [2025/1710] Information-Theoretic Broadcast-Optimal MPC
49. [2025/1711] Accelerating FHEW-like Bootstrapping via New ...
50. [2025/1712] The Syndrome-Space Lens: A Complete Resolution of ...
51. [2025/1713] Ilyazh-Web3E2E: A Post-Quantum Hybrid Protocol for ...
52. [2025/1714] Verifiable PIR with Small Client Storage
53. [2025/1715] UltraMixer: A Compliant Zero-Knowledge Privacy ...
54. [2025/1716] Beyond Shannon: Operational Perfect Secrecy as a ...
55. [2025/1717] Large-Plaintext Functional Bootstrapping in FHE ...
56. [2025/1718] Indistinguishability Obfuscation from Ring Key- ...
57. [2025/1719] Bribers, Bribers on The Chain, Is Resisting All in ...
58. [2025/1720] BATTLE rCo Bonded Adversarial TournamenT with ...
## 2025/1609
* Title: Many-time Linkable Ring Signatures
* Authors: Nam Tran, Khoa Nguyen, Dongxi Liu, Josef Pieprzyk, Willy Susilo
* [Permalink](https://eprint.iacr.org/2025/1609)
* [Download](https://eprint.iacr.org/2025/1609.pdf)
### Abstract
Linkable ring signatures (Liu et al., ACISP'04) is a ring signature scheme with a linking mechanism for detecting signatures from the same signer. This functionality has found many practical applications in electronic voting, cryptocurrencies, and whistleblowing systems. However, existing linkable ring signature schemes impose a fundamental limitation: users can issue only one signature, and after that their anonymity is not guaranteed. This limited number of usage is inadequate for many real-world scenarios.
This work introduces the notion of Many-time Linkable Ring Signatures, extending the anonymity guarantees of standard linkable ring signatures. Specifically, many-time linkable ring signatures ensure that signers remain anonymous as long as the number of their signatures is smaller than a system-global threshold. Only when a signer exceeds this threshold the anonymity is lost. We formalize this via a security notion called T-anonymity, which guarantees that adversaries cannot distinguish signatures from users who have each produced at most T signatures. This new notion of anonymity generalizes one-time anonymity in previous linkable schemes, while providing stronger guarantees than existing constructions. We also present a lattice-based construction with proven security in the quantum random oracle model (QROM).
## 2025/1657
* Title: ORQ: Complex Analytics on Private Data with Strong Security Guarantees * Authors: Eli Baum, Sam Buxbaum, Nitin Mathai, Muhammad Faisal, Vasiliki Kalavri, Mayank Varia, John Liagouris
* [Permalink](https://eprint.iacr.org/2025/1657)
* [Download](https://eprint.iacr.org/2025/1657.pdf)
### Abstract
We present ORQ, a system that enables collaborative analysis of large private datasets using cryptographically secure multi-party computation (MPC). ORQ protects data against semi-honest or malicious parties and can efficiently evaluate relational queries with multi-way joins and aggregations that have been considered notoriously expensive under MPC. To do so, ORQ eliminates the quadratic cost of secure joins by leveraging the fact that, in practice, the structure of many real queries allows us to join records and apply the aggregations rCLon the flyrCY while keeping the result size bounded. On the system side, ORQ contributes generic oblivious operators, a data-parallel vectorized query engine, a communication layer that amortizes MPC network costs, and a dataflow API for expressing relational analyticsrCoall built from the ground up.
We evaluate ORQ in LAN and WAN deployments on a diverse set of workloads, including complex queries with multiple joins and custom aggregations. When compared to state-of-the-art solutions, ORQ significantly reduces MPC execution times and can process one order of magnitude larger datasets. For our most challenging workload, the full TPC-H benchmark, we report results entirely under MPC with Scale Factor 10rCoa scale that had previously been achieved only with information leakage or the use of trusted third parties.
## 2025/1663
* Title: IVC in the Open-and-sign Random Oracle Model
* Authors: Mary Maller, Nicolas Mohnblatt, Arantxa Zapico
* [Permalink](https://eprint.iacr.org/2025/1663)
* [Download](https://eprint.iacr.org/2025/1663.pdf)
### Abstract
Incrementally verifiable computation (IVC) is a powerful cryptographic primitive, particularly suited for proving long-running machine computations. Previous work shows that IVC can be constructed by recursively composing SNARKs. Unfortunately, theoretical challenges limit the provable security of known IVC constructions. Recursive composition may quickly lead to a blowup in extraction time and may require arithmetic circuits to enforce constraints about random oracle calls. Furthermore, composition presents a practical challenge: proofs are often expressed in a form that is not friendly to the arithmetic circuits that produce them.
To mitigate the theoretical challenges, we present the Open-and-Sign Random Oracle Model (osROM) as an extension to the signed random oracle of Chiesa and Tromer (ICS '10). This model, while strictly harder to instantiate than the Random Oracle Model, allows the design of protocols that can efficiently verify calls to the oracle and support straight-line extractors. As a result, IVC constructions in the osROM can be shown to have provable security for polynomial depths of computation.
Under our new model, we construct a framework to build secure IVC schemes from simple non-interactive reductions of knowledge. Our construction natively supports cycles of elliptic curves in the style of Ben-Sasson et al. (CRYPTO '14), thus answering the practical challenge outlined above. Finally, we analyze the HyperNova (CRYPTO '24) IVC scheme in the osROM and show that it is secure over a two-cycle of elliptic curves, for polynomial depths of computation.
## 2025/1666
* Title: Trout: Two-Round Threshold ECDSA from Class Groups
* Authors: Hila Dahari-Garbian, Ariel Nof, Luke Parker
* [Permalink](https://eprint.iacr.org/2025/1666)
* [Download](https://eprint.iacr.org/2025/1666.pdf)
### Abstract
We present Trout (Two-ROUnd Threshold), the \textit{first} distributed two-round ECDSA signing protocol for arbitrary thresholds. Trout has constant upload bandwidth per-party and processing time linear in the amount of participants. Moreover, Trout achieves the Identifiable Abort (IA) property, which means that if the protocol cannot terminate due to a failure, parties can attribute the failure to a specific party. We achieve this without a trusted setup.
Our protocol relies on linear-homomorphic encryptions and commitments over class groups. To obtain our result, we leverage the recent construction of an exponent-VRF (Boneh et al., Eurocrypt 2025) and a novel protocol to multiply an encrypted value with a committed value and simultaneously decrypt it, which we call "scaled decryption". We believe that this protocol may be of independent interest.
Our protocol has a very low communication cost of just 6.5 KB sent per party. Furthermore, we implemented our protocol in Rust and provide benchmarks for various configurations, showing its practicality even for 100 parties. Our implementation includes a constant-time variant which, to the best of our knowledge, is the first of its kind for class-group-based threshold ECDSA protocols.
## 2025/1667
* Title: Persistence of Hourglass(-like) Structure: Improved Differential-Linear Distinguishers for Several ARX Ciphers
* Authors: Xinxin Gong, Qingju Wang, Yonglin Hao, Lin Jiao, Xichao Hu
* [Permalink](https://eprint.iacr.org/2025/1667)
* [Download](https://eprint.iacr.org/2025/1667.pdf)
### Abstract
The ARX structure plays a crucial role in symmetric-key primitives, with differential-linear (DL) attacks being among the most effective cryptanalysis techniques against ARX ciphers. In this paper, we present a systematic re-decomposition technique for DL distinguishers of ARX ciphers and identify for the first time the hourglass(-like) structural commonalities among optimal DL distinguishers searched out by various deduction techniques, also supported through comprehensive experiments, which motivate us to develop an efficient and generalized approach to construct optimal hourglass(-like) structural DL distinguishers. Our method yields significant advances when applied to \speck, \alzette, and the underlying permutations of \siphash{} and \chaskey: (1) the first 11- to 14-round DL distinguishers of \alzette; (2) the first (valid) DL distinguishers for 11-round \speck32, 12-round \speck48, and 16-round \speck96; (3) deterministic (correlation $\pm1$) 3-round DL distinguishers for \siphash-2-4 and significantly improved 4-round ones. All these distinguishers are equipped with both theoretical and experimental verifications. We further analyze ARX-based Latin dance stream ciphers, achieving improved DL distinguishers for 7/7.25-round \chacha, 8-round \salsa, and 5.5-round \forro. Though some of the improvements are not significant, we have verified the effectiveness of our method across a broader range of instances. This work provides new insights for DL distinguisher construction and enhances understanding of the security of ARX ciphers.
## 2025/1668
* Title: Post-Quantum Cryptography in Practice: A Literature Review of Protocol-Level Transitions and Readiness
* Authors: Obianuju Egbuagha, Emmanuel Ikwunna
* [Permalink](https://eprint.iacr.org/2025/1668)
* [Download](https://eprint.iacr.org/2025/1668.pdf)
### Abstract
This paper presents a structured literature review of ongoing global efforts to integrate post-quantum cryptography (PQC) into widely deployed communication and identity protocols. We analyze current readiness, standardization initiatives, hybrid cryptographic approaches, and deployment challenges across multiple layers of the protocol stack, including TLS, SSH, VPNs, certificate infrastructure, and messaging protocols.
The report also discusses hybrid cryptographic strategies, current deployment efforts, and the technical challenges facing real-world implementation, including performance, interoperability, and resistance to side-channel attacks. With insights from recent research, industry trials, and open source tools, the report aims to provide a clear and accessible overview of the growing role of PQC in securing the future of digital communication.
We aim to guide researchers, developers, and policymakers in understanding the state of PQC integration and encourage broader involvement in the testing, implementation, and evaluation of next-generation cryptographic solutions.
## 2025/1669
* Title: Experience from UNITA Elections: Reconciling Revote, E2E Verifiability and Low Coercion
* Authors: Feng Hao, Luke Harrison, Saverio Veltri, Irene Pugliatti, Chris Sinclair, Gareth Nixon
* [Permalink](https://eprint.iacr.org/2025/1669)
* [Download](https://eprint.iacr.org/2025/1669.pdf)
### Abstract
This paper presents an experience of designing, building and deploying an online voting system for the Student Assembly elections in the UNITA Alliance with the following requirements. First, the system should allow voters to vote as many times as they wish before the electionrCOs closing time with only the last vote being counted (known as revote). Second, the system should allow end-to-end (E2E) verifiability. Third, the system should allow voters to cast votes under the minimum influence from external forces or coercion. Developing an online voting system to meet these requirements poses a unique challenge. In this pa- per, we present an online voting system for UNITA elections, based on a variant of the DRE-ip protocol to provide E2E verifiability with support for revote. The system adopts a two-server architecture and implements a separation of control between the two servers to protect the voterrCOs anonymity. The first UNITA elections were successfully concluded in March 2025, providing a case study for reconciling revote, E2E verifiability and low coercion in a real-world setting. The use of verifiable online voting to empower students from different European universities to elect the Student Assembly also serves as a model for more inclusive democratic governance of a university alliance.
## 2025/1670
* Title: Mixderive: A New Framework of Deriving Linear Approximations and Improved Differential-Linear Distinguishers for ChaCha
* Authors: Zhengting Li, Lin Ding, Xinhai Wang, Jiang Wan
* [Permalink](https://eprint.iacr.org/2025/1670)
* [Download](https://eprint.iacr.org/2025/1670.pdf)
### Abstract
ChaCha is a well-known ARX-based cipher and has become one of the most widely used ciphers in the real world. In this paper, a systematic three-case framework called \emph{Mixderive} to find linear approximations for ChaCha is proposed. By this new framework, new linear approximations for 3.5- and 4-round ChaCha are found, which are significantly better than the existing linear approximations proposed at EUROCRYPT 2021 and ASIACRYPT 2022. These improvements confirm the effectiveness of \emph{Mixderive}. In addition, new 2- and 2.5-round linear approximations for ChaCha are found by \emph{Mixderive}. Based on these new findings, new differential-linear distinguishers for 7- and 7.5-round ChaCha256 with complexities ${2^{162.28}}$ and ${2^{247.08}}$ are proposed, which improve the best known distinguishers by factors of ${2^{4.61}}$ and ${2^{4.46}}$, respectively. To the best of our knowledge, both cryptanalytic results are the best.
## 2025/1671
* Title: QKD Oracles for Authenticated Key Exchange
* Authors: Kathrin H||velmanns, Daan Planken, Christian Schaffner, Sebastian Verschoor
* [Permalink](https://eprint.iacr.org/2025/1671)
* [Download](https://eprint.iacr.org/2025/1671.pdf)
### Abstract
Authenticated Key Exchange (AKE) establishes shared ('symmetric') cryptographic keys which are essential for secure online communication. AKE protocols can be constructed from public-key cryptography like Key Encapsulation Mechanisms (KEMs). Another approach is to use Quantum Key Distribution (QKD) to establish a symmetric key, which uses quantum communication. Combining post-quantum AKE and QKD appropriately may provide security against quantum attacks even if only one of the two approaches turns out to be secure.
We provide an extensive review of existing security analyses for combined AKE and their formal security models, and identify some gaps in their treatment of QKD key IDs. In particular, improper handling of QKD key IDs leads to Dependent-Key attacks on AKE.
As our main conceptual contribution, we model QKD as an oracle that closely resembles the standard ETSI 014 QKD interface. We demonstrate the usability of our QKD oracle for cryptographic security analyses by integrating it into a prominent security model for AKE, called CK+ model, thereby obtaining a security model for combined AKE that catches Dependent-Key attacks. In this model, we formally prove security of a new protocol that combines QKD with a triple-KEM handshake. This is the first provably secure hybrid protocol that maintains information-theoretic security of QKD.
## 2025/1672
* Title: All Paths Lead to the Root
* Authors: Th|-ophile Br|-zot, Chlo|- H|-bant
* [Permalink](https://eprint.iacr.org/2025/1672)
* [Download](https://eprint.iacr.org/2025/1672.pdf)
### Abstract
In an attempt to fix the defects of the definition of forward security for Symmetric Searchable Encryption (SSE) schemes, Amjad et al. [2] proposed injection security. This new security property is strictly stronger than most security properties known to date, which makes it particularly challenging to design schemes meeting its requirements. In this work, we show how it is possible to use trees to decorrelate the modification of an index from its effects, hence achieving injection security. In addition to being conceptually simple, our scheme features non-interactive, stateless and mutation-free search operations that allow supporting concurrent readers easily. Finally, the proposed reference implementation is efficient: both Insert and Search operations execute in milliseconds even when operating on an index with up to a million entries and volumes up to a thousand.
## 2025/1673
* Title: Strong Designated Verifier Signatures with Non-delegatability from CSIDH
* Authors: Hiroki Minamide, Keisuke Tanaka, Masayuki Tezuka
* [Permalink](https://eprint.iacr.org/2025/1673)
* [Download](https://eprint.iacr.org/2025/1673.pdf)
### Abstract
Abstract. Designated verifier signature allows a signer to designate a verifier who can verify the signature. A strong designated verifier signature (SDVS) enhances privacy by ensuring that the signature itself does not leak information about the signerrCOs identity to anyone other than the designated verifier. Non-delegatability is a property, as it prevents the signerrCOs ability to generate valid signatures from being delegated to others. This property is important for SDVS applications such as e-voting. To date, post-quantum SDVS schemes with non-delegatability have been proposed. These schemes are lattice-based or hash-based schemes. While isogeny-based SDVS schemes have been proposed, none of the existing works provide a proof of non-delegatability.
In this paper, we present the first isogeny-based SDVS scheme with a formal proof of non-delegatability. Our construction uses the quadratic twists of elliptic curves. The security of our scheme is proven under the commutative supersingular isogeny gap DiffierCoHellman assumption and the group action inversion problem assumption in the random oracle model.
## 2025/1674
* Title: Secure Rate-Distortion-Perception Trade-Off with Side Information
* Authors: Gustaf |ahlgren, Onur G|+nl|+
* [Permalink](https://eprint.iacr.org/2025/1674)
* [Download](https://eprint.iacr.org/2025/1674.pdf)
### Abstract
Secure rate-distortion-perception (RDP) trade-offs are relevant for applications such as semantic compression, where the perceptual quality needs to be maximized. We study a framework for secure RDP over an ideal public communication channel in the presence of an eavesdropper, where the legitimate parties also have access to side information correlated with the source. The exact rate region for the secure RDP trade-off is established when both the encoder and the decoder have access to the side information. We then characterize an inner bound when only the decoder has access to the side information and establish the exact region for a special case. Moreover, we provide an RDP example to illustrate remarkable gains in communication rate due to common randomness, which is not possible to obtain for rate-distortion trade-offs. Our results show that binning-based schemes can achieve high perceptual quality, low distortion, and strong secrecy simultaneously, establishing the information-theoretic limits for next-generation trustworthy semantic compression systems.
## 2025/1675
* Title: Surtr: Transparent Verification with Simple yet Strong Coercion Mitigation
* Authors: Rosario Giustolisi, Maryam Sheikhi Garjan, Peter Browne R|+nne
* [Permalink](https://eprint.iacr.org/2025/1675)
* [Download](https://eprint.iacr.org/2025/1675.pdf)
### Abstract
Transparent verification allows voters to directly identify their vote in cleartext in the final tally result. Both Selene and Hyperion offer this simple and intuitive verification method, and at the same time allow for coercion to be mitigated under the assumption that tally servers can privately notify voters of the keying material needed for verification. Subsequently, a voter can generate fake keying material to deceive a coercer.
In this paper, we propose Surtr, a new scheme that enables transparent verification without requiring a private notification channel. This approach strengthens coercion mitigation, since a coercer can monitor the notification channel, and simplifies the process by eliminating the need for voters to generate fake keying material for the coercer.
## 2025/1676
* Title: Honest Majority Constant-Round MPC with Linear Communication from One-Way Functions
* Authors: Junru Li, Yifan Song
* [Permalink](https://eprint.iacr.org/2025/1676)
* [Download](https://eprint.iacr.org/2025/1676.pdf)
### Abstract
Secure multiparty computation (MPC) faces a fundamental efficiency trade-off between round complexity and communication complexity: without fully homomorphic encryption, protocols with constant round complexity (e.g., protocols based on garbled circuits) incur high communication cost, while communication-efficient approaches (e.g., protocols based on secret sharing) have round complexity linear in the depth of the circuit. In this work, we focus on reducing the communication complexity of constant-round MPC protocols in the honest majority setting. Existing results either rely on strong assumptions (e.g., random oracles, DDH, LPN) or incur high communication of $\Omega(|C|n^2\kappa)$ bits under one-way functions (OWFs). However, non-constant-round MPC protocols can achieve linear communication in the number of parties even with information-theoretic security.
We resolve this gap by presenting the first constant-round honest majority MPC protocol with linear communication complexity of $O(|C|n\kappa + n^2\kappa^2+n^4\kappa)$ only from OWFs. We introduce novel techniques for computing garbled circuits via party virtualization and efficient local computation of virtual parties, which optimize the existing protocols on multiparty garbling. These allow us to overcome the $O(n^2\kappa)$ bit of communication per-gate bottleneck of prior protocols, matching the scalability of the best non-constant-round protocols in the same setting.
## 2025/1677
* Title: DiffierCoHellman Key Exchange from Commutativity to Group Laws
* Authors: Dung Hoang Duong, Youming Qiao, Chuanqi Zhang
* [Permalink](https://eprint.iacr.org/2025/1677)
* [Download](https://eprint.iacr.org/2025/1677.pdf)
### Abstract
In DiffierCoHellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose DiffierCoHellman key exchange in the group action framework (BrassardrCoYung, Crypto'90; JirCoQiaorCoSongrCoYun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, G|+nther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.
## 2025/1678
* Title: Two-Key Variant of the Four-Round Cascading LRW1
* Authors: Shreya Dey, Avijit Dutta, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2025/1678)
* [Download](https://eprint.iacr.org/2025/1678.pdf)
### Abstract
In EUROCRYPT'20, Bao et al. have proved that three rounds of cascaded LRW1 construction provide security up to $2^{2n/3}$ queries. However, in a recent work by Khairallah et al., it has been shown that the construction provides only birthday bound security via exhibiting a distinguishing attack on the construction, and thereby invalidating the claim of Bao et al. In an independent and contemporaneous work, Datta et al. have shown that four rounds of cascading of the $\textsf{LRW1}$ construction, dubbed as $\textsf{CLRW1}^4$rCobased on four independent keyed block ciphersrCoachieves $3n/4$-bit CCA security. In this paper, we have shown that a key reduced variant of the $\textsf{CLRW1}^4$ construction, dubbed as $\textsf{R}\mbox{-}\textsf{CLRW1}^4$ based on two independent keyed block ciphers, achieves $2n/3$-bit CCA security. The security proof of our construction relies on a heavy use of the H-Coefficient technique and non-trivial analysis in lower-bounding the real interpolation probability for good transcripts.
## 2025/1679
* Title: SoK: Connecting the Dots in Privacy-Preserving ML - Systematization of MPC Protocols and Conversions Between Secret Sharing Schemes
* Authors: Martin Zbudila, Ajith Suresh, Hossein Yalame, Omid Mirzamohammadi, Aysajan Abidin, Bart Preneel
* [Permalink](https://eprint.iacr.org/2025/1679)
* [Download](https://eprint.iacr.org/2025/1679.pdf)
### Abstract
Privacy-preserving machine learning (PPML) has become increasingly important due to the need to protect sensitive data during training and inference. Secure multiparty computation (MPC) and homomorphic encryption (HE) have emerged as foundational technologies, enabling secure computation over private data. In this work, we provide a systematic comparative overview of MPC frameworks for PPML, focusing on protocols that introduce novel approaches rather than incremental improvements. Frameworks are analyzed based on computational and communication complexity, throughput, security guarantees, and applicability in small-party settings. Each underlying primitive in PPML is examined from an MPC perspective, highlighting its role and trade-offs. We also emphasize the diversity of secret-sharing schemes and associated interoperability challenges, proposing scheme conversions to facilitate efficient hybrid solutions. This Systematization of Knowledge guides researchers in identifying open problems and practitioners in selecting effective MPC-based frameworks for real-world PPML deployment.
## 2025/1680
* Title: ChipmunkRing: A Practical Post-Quantum Ring Signature Scheme for Blockchain Applications
* Authors: Dmitrii A. Gerasimov
* [Permalink](https://eprint.iacr.org/2025/1680)
* [Download](https://eprint.iacr.org/2025/1680.pdf)
### Abstract
We introduce ChipmunkRing, a practical post-quantum ring signature construction tailored for blockchain environments. Building on our Chipmunk lattice-based cryptographic framework, this implementation delivers compact digital signatures ranging from 20.5 to 279.7KB, with rapid signing operations completing in 1.1-15.1ms and efficient validation processes requiring only 0.4-4.5ms for participant groups of 2-64 members. The cornerstone of our approach is Acorn VerificationrCoa streamlined zero-knowledge protocol that supersedes the classical Fiat-Shamir methodology. This innovation enables linear O(n) authentication complexity using concise 96-byte cryptographic proofs per participant, yielding a remarkable 17.7|u performance enhancement for 32-member rings when compared to conventional techniques. Our work includes preliminary security estimates indicating approximately 112-bit security against known quantum algorithms (NIST Level 5, see Section~\ref{sec:quantum-security}), extensive computational benchmarking, and comprehensive support for both standard anonymity sets and collaborative threshold constructions with flexible participation requirements.
## 2025/1681
* Title: Modular Forms and Hecke Operators for Post-Quantum Cryptography
* Authors: Trey Li
* [Permalink](https://eprint.iacr.org/2025/1681)
* [Download](https://eprint.iacr.org/2025/1681.pdf)
### Abstract
We introduce modular forms and Hecke operators to cryptography and propose the Hecke problem as a new foundation for post-quantum cryptography. Given two modular forms, the Hecke problem asks to recover the Hecke operator that maps one to the other. While there is a deep relation to isogeny problems through the modularity theorem, this problem is rooted in arithmetic geometry and differs fundamentally in structure and mechanism. We prove NP-hardness of this problem and use it to construct a non-interactive key exchange scheme that achieves higher efficiency than isogeny-based schemes and smaller key sizes than lattice-based and code-based schemes.
## 2025/1682
* Title: pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer
* Authors: Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, Dionysis Zindros
* [Permalink](https://eprint.iacr.org/2025/1682)
* [Download](https://eprint.iacr.org/2025/1682.pdf)
### Abstract
This work addresses the inherent issues of high latency in blockchains and low scalability in traditional consensus protocols. We present pod, a novel notion of consensus whose first priority is to achieve the physically-optimal latency of $2\delta$, or one round-trip, i.e., requiring only one network trip (duration $\delta$) for writing a transaction and one for reading it.
To accomplish this, we first eliminate inter-replica communication. Instead, clients send transactions directly to all replicas, which independently process transactions and append them to local logs. Replicas assigns a timestamp and a sequence number to each transaction in their logs, allowing clients to extract valuable metadata about the transactions and the system state. Later on, clients retrieve these logs and extract transactions (and associated metadata) from them.
Necessarily, this construction achieves weaker properties than a total-order broadcast protocol, due to existing lower bounds. Our work models the primitive of pod and defines its security properties. We then show pod-core, a protocol that satisfies properties such as transaction confirmation within $2\delta$, censorship resistance against Byzantine replicas, and accountability for safety violations. We show that single-shot auctions can be realized using the pod notion and observe that it is also sufficient for other popular applications.
## 2025/1683
* Title: Proving the Security of PeerDAS without the AGM
* Authors: Benedikt Wagner, Arantxa Zapico
* [Permalink](https://eprint.iacr.org/2025/1683)
* [Download](https://eprint.iacr.org/2025/1683.pdf)
### Abstract
Data availability sampling (DAS) enables clients to verify availability of data without downloading it entirely. This concept is crucial to Ethereum's roadmap. An instantiation of this concept, known as PeerDAS, relies at its core on a variant of KZG polynomial commitments and is set to be integrated into Ethereum. To assess the security of PeerDAS, Wagner and Zapico (ePrint 2024) provided a formal analysis, proving its security as a cryptographic primitive. However, their proof relies on the algebraic group model - an idealized framework known to be uninstantiable (Zhandry, CRYPTO 2022).
In this work, we establish the security of \peerdas in the standard model under falsifiable assumptions. Specifically, we eliminate reliance on the algebraic group model and instead base our proof on the ARSDH assumption (Lipmaa et al., EUROCRYPT 2024), thus strengthening the theoretical foundations of PeerDAS and enhancing confidence in its security.
## 2025/1684
* Title: FHEMaLe: Framework for Homomorphic Encrypted Machine Learning
* Authors: B PRADEEP KUMAR REDDY, SAMEEKSHA GOYAL, RUCHIKA MEEL, Ayantika Chatterjee
* [Permalink](https://eprint.iacr.org/2025/1684)
* [Download](https://eprint.iacr.org/2025/1684.pdf)
### Abstract
Machine learning (ML) has revolutionized various industries by leveraging predictive models and data-driven insights, often relying on cloud
computing for large-scale data processing. However, this dependence introduces challenges such as bandwidth constraints and network latency. Edge
computing mitigates these issues by enabling localized processing, reducing reliance on continuous cloud connectivity, and optimizing resource
allocation for dynamic workloads. Given the limited computational capacity of sensory nodes in ML systems, edge devices provide an effective
solution by offloading processing tasks. However, a critical challenge in this paradigm is to ensure user privacy while handling sensitive data
both in the cloud and in edge processing. To address this, we propose a Fully Homomorphic Encryption (FHE) enabled framework that enables
ML computations directly on encrypted data, eliminating need for decryption. The main challenge to design such framework is that ML complex
implementation steps need to be revisited with suitable optimizations to match FHE processing requirements. There are different standard libraries to
support basic computation blocks on which encrypted ML processing is to be developed. These libraries vary in supported computation operators,
computational complexity and memory demands. Those in-turn introduces latency and throughput challenges, especially on resource-constrained
edge nodes. For example, in general HE library CKKS(Cheon-Kim-Kim-Song) with packing and approximate homomorphic operation support is
known to be the best choice for privacy preserving AI algorithm implementation. However, analysis shows leveled CKKS is limited in implementing
complex operators and hence not suitable for few specific ML algorithms like KNN, Logistic Regression or general activations in NN etc without any
approximation. To avoid accuracy drops associated with approximations, Torus based FHE library (TFHE) can be a better choice to make certain
ML implementations feasible. Moreover, our study shows compared to TFHE, CKKS with huge memory requirement is not suitable for resource
constrained edge. Thus, underlying library choice to design such framework is crucial considering the trade-off between latency and accuracy. In
this work, we propose an integrated framework FHEMaLe for encrypted ML processing which takes model architecture, desired accuracy, and
platform preference as inputs and based on that appropriate execution environment is selected: a cloud platform leveraging the CKKS homomorphic
encryption library or an edge platform using the TFHE library. Further, analysis shows the limitation of performing FHE ML on a single edge device
and hence our framework partitions encrypted data, transmits it via a fabric API, and performs distributed encrypted ML computations across the
edge cluster. We implement distributed ML inference for algorithms such as EYE+-Nearest Neighbors (KNN) (Cloud CKKS=248 sec, Edge TFHE=37
min), Support Vector Machine (SVM) (Cloud CKKS=18 sec, Edge TFHE=4.15 min), and Logistic Regression (LR) ( Cloud CKKS=17 sec, Edge
TFHE=7.82 min) on a cluster of 11 edge nodes. This work explains why KNN suffers from a major performance bottleneck in encrypted domain and
may not be a great choice for encrypted ML processing without application specific optimizations. Furthermore, our encrypted operators are capable of supporting encrypted NN processing
(Cloud CKKS= 57 sec), but we explain why CKKS is a preferred choice in this case. The distributed nature of our implementation shows a promise
of further improvement and scalability with the support of larger cluster.
## 2025/1685
* Title: Toss: Garbled PIR from Table-Only Stacking
* Authors: Lucien K. L. Ng, Vladimir Kolesnikov
* [Permalink](https://eprint.iacr.org/2025/1685)
* [Download](https://eprint.iacr.org/2025/1685.pdf)
### Abstract
Garbled Circuits (GC) are a foundational primitive for secure two-party computation (2PC). Garbled Private Information Retrieval (GPIR) is a GC technique for looking up a public array or database (DB) on a private index unknown to either party. GPIR immediately enables GC evaluation of functions implemented as a publicly known lookup table (LUT).
However, GPIR is costly. It can be realized by a linear scan, by adapting Garbled RAM, by stacking GC branches implementing access to table elements, and, most recently, via the GC lookup table scheme logrow (Heath et al., Eurocrypt 2024). For an $N$-row DB lookup of $m$-bit rows, logrow has computation cost $\approx O(N m \kappa)$ and communication cost $O(m(\log N \cdot \kappa + N))$. This makes logrow practical only for tables up to about $2^{15}$ rows.
We propose Toss, a new efficient GPIR protocol with dramatically reduced bandwidth consumptionrCoan especially scarce resource in MPCrCoboth asymptotically and concretely. Our communication cost is $O\!\left(\sqrt{N}\, m \sqrt{\kappa}\right)$ with a small constant, which is sublinear in both $N$ and the security parameter $\kappa$. Our computation cost is $O\!\left(N m \kappa + \bigl(\sqrt{N/\kappa}\, m + N\bigr) c_\kappa \right)$, where $c_\kappa$ is the cost of a hash evaluation. This computation cost is comparable to, or slightly lower than, that of logrow.
In concrete terms, for a $2^{20}$-row LUT of 8-bit items, we achieve more than a $31\times$ reduction in communication compared to logrow. On a laptop over a 100 Mbps channel, throughput increases from approximately $10.6$ lookups/s to $81$ lookups/s, a $>7.5\times$ improvement. On a 10 Mbps channel, Toss achieves more than $28\times$ better throughput. The improvement grows with $N$; for example, for $N=2^{25}$ and $m=32$, the gain exceeds $512\times$.
Toss builds on stacked garbling (SGC) and logrow, incorporating multiple low-level optimizations and requiring a reworking of their internals and interfaces. We emphasize that constructing GPIR directly from SGC incurs logarithmic computational overhead, which decreases throughput in typical rCLlaptop + LANrCY testbeds. Our design avoids this pitfall. We implement Toss and report on its performance, demonstrating its substantial communication savings and practical efficiency.
## 2025/1686
* Title: Honest Users Make Honest Mistakes: A Framework for Analysing eID Protocols
* Authors: Ole Martin Edstr|+m, Kristian Gj|+steen, Hans Heum, Sjouke Mauw, Felix Stutz
* [Permalink](https://eprint.iacr.org/2025/1686)
* [Download](https://eprint.iacr.org/2025/1686.pdf)
### Abstract
Electronic identification (eID) protocols and federated identity management systems play an increasingly important role in our modern society, both on the internet through services from Google and others, and through the eIDAS regulation in Europe. A key feature of eID protocols is that humans are intimately involved in the protocol, often responsible for critical security steps. Traditional security analyses of such protocols typically assume flawless user behaviour, yet widespread real-world adoption makes user mistakes inevitable.
We present a framework for analysing the security of eID protocols that can model users making mistakes. It is suitable for automated analysis with Tamarin and supports fine-grained corruption modelling of protocol actors. We demonstrate the framework's utility by describing and analysing common eID protocols based on passwords, mobile applications and authentication tokens, as well as by systematically evaluating the impact of various combinations of user mistakes on security.
## 2025/1687
* Title: Web3 Recovery Mechanisms and User Preferences
* Authors: Easwar Vivek Mangipudi, Panagiotis Chatzigiannis, Konstantinos Chalkias, Aniket Kate, Mohsen Minaei, Mainack Mondal
* [Permalink](https://eprint.iacr.org/2025/1687)
* [Download](https://eprint.iacr.org/2025/1687.pdf)
### Abstract
In a Web3 (blockchain) setting, account recovery allows users to regain access to their accounts after losing their authentication credentials. Although recovery mechanisms are well-established and extensively analyzed in the context of Web2 systems, Web3 presents distinct challenges. Web3 account access is typically tied to cryptographic key pairs, and private keys are not entrusted to centralized entities. This design improves security, but significantly complicates the recovery process, making it difficult or even impossible for users to regain access after loss of keys. Given the critical role that recovery plays in ensuring long-term feasibility and trust in digital systems, a range of recovery mechanisms has been proposed to accommodate the unique properties of Web3. These mechanisms aim to help users manage key loss without introducing undue friction or risk.
Although there has been an exponential increase in the use of cryptocurrency wallets in the last decade, the popularity and usage of the corresponding recovery mechanisms remain unclear. Furthermore, it is still unclear how users perceive these recovery mechanisms and what they expect from them. In this work, our objective is to empirically understand and analyze user perceptions of the various recovery mechanisms. To this end, we conducted a user survey of 331 participants and asked them to rate different mechanisms on usability, security, and availability. The results show interesting aspects of the user preferences, including their view of sharing keys among different devices and trusting their friends or family. Based on our findings, we provide insight and future directions for the developer and research community.
## 2025/1688
* Title: SUMMER: Recursive Zero-Knowledge Proofs for Scalable RNN Training
* Authors: Yuange Li, Xiong Fan
* [Permalink](https://eprint.iacr.org/2025/1688)
* [Download](https://eprint.iacr.org/2025/1688.pdf)
### Abstract
Zero-knowledge proofs of training (zkPoT) enable a prover to certify that a model was trained on a committed dataset under a prescribed algorithm without revealing the model or data. Proving recurrent neural network (RNN) training is challenging due to hidden-state recurrence and cross-step weight sharing, which require proofs to enforce recurrence, gradients, and nonlinear activations across time.
We present SUMMER (SUMcheck and MERkle tree), a recursive zkPoT for scalable RNNs. SUMMER generates sumcheck-based proofs that backpropagation through time (BPTT) was computed correctly over a quantized finite field, while nonlinearities such as $\tanh$ and softmax are validated by lookup arguments. Per-step commitments and proofs are folded with Merkle trees, yielding a final commitment and a succinct proof whose size and verification time are independent of the number of iterations.
SUMMER offers (i) the first end-to-end zkPoT for RNN training, including forward, backward, and parameter updates; (ii) the first use of LogUp for nonlinear operations with a batched interface; and (iii) efficient recursive composition of lookup and sumcheck proofs. On a Mini-Char-RNN with 12M parameters, the prover runs in 70.1 seconds per iteration, $8.5\times$ faster and $11.6\times$ more memory efficient than the IVC baseline, with 165 kilobyte proofs verified in 20 milliseconds.
## 2025/1689
* Title: IPCrypt: Optimal, Practical Encryption of IP Addresses for Privacy and Measurement
* Authors: Frank Denis
* [Permalink](https://eprint.iacr.org/2025/1689)
* [Download](https://eprint.iacr.org/2025/1689.pdf)
### Abstract
This paper introduces efficient, practical methods for encrypting IPv4/IPv6 addresses while preserving utility in logs, telemetry, and third-party data exchange.
We focus on three practical goals: (i) format-compatible encryption that keeps outputs in the IPv6 address space and handles IPv4 inputs canonically; (ii) prefix-preserving encryption that retains network structure for analytics while hiding host identity; and (iii) non-deterministic encryption that resists correlation while remaining compact and invertible.
We give deterministic, prefix-preserving, and two non-deterministic variants, with security models and arguments under standard assumptions, plus explicit usage bounds and operating limits.
We also relate each variant to known efficiency lower bounds (ciphertext expansion and primitive calls) and state our claims within deployable parameter ranges.
## 2025/1690
* Title: A Tight Quantum Algorithm for Multiple Collision Search
* Authors: Xavier Bonnetain, Johanna Loyer, Andr|- Schrottenloher, Yixin Shen
* [Permalink](https://eprint.iacr.org/2025/1690)
* [Download](https://eprint.iacr.org/2025/1690.pdf)
### Abstract
Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a single collision, the known quantum algorithms match the query lower bound. This is not the case for the problem of finding multiple collisions, despite its regular appearance as a sub-component in sieving-type algorithms.
At EUROCRYPT 2019, Liu and Zhandry gave a query lower bound $\Omega{}(2^{m/3 + 2k/3})$ for finding $2^k$ collisions in a random function with $m$-bit output. At EUROCRYPT 2023, Bonnetain et al. gave a quantum algorithm matching this bound for a large range of $m$ and $k$, but not all admissible values. Like many previous collision-finding algorithms, theirs is based on the MNRS quantum walk framework, but it chains the walks by reusing the state after outputting a collision.
In this paper, we give a new algorithm that tackles the remaining non-optimal range, closing the problem. Our algorithm is tight (up to a polynomial factor) in queries, and also in time under a quantum RAM assumption. The idea is to extend the chained walk to a regime in which several collisions are returned at each step, and the "walks" themselves only perform a single diffusion layer.
## 2025/1691
* Title: Pilvi: Lattice Threshold PKE with Small Decryption Shares and Improved Security
* Authors: Valerio Cini, Russell W. F. Lai, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2025/1691)
* [Download](https://eprint.iacr.org/2025/1691.pdf)
### Abstract
Threshold public-key encryption (tPKE) enables any subset of $t$ out of $K$ parties to decrypt non-interactively, while any ciphertext remain secure if less that $t$ decryption shares are known. Despite recent progress, existing lattice-based tPKEs face at least one of the following drawbacks: (1) having large decryption share size -- polynomial in $K$ and some even exponential in $t$, (2) proven secure only against relaxed security models where the adversary is not allowed to see decryption shares of challenge ciphertexts, and (3) lack of concrete efficiency, in particular due to the requirement of super-polynomial modulus for noise flooding.
We present $\mathsf{Pilvi}$, a new thresholdised variant of RegevrCOs public-key encryption scheme, which achieves both small decryption shares and a strong form of simulation-based security under the Learning with Errors (LWE) assumption. Our construction has decryption share size $t \cdot \log K \cdot \mathsf{poly}(\lambda)$ and allows the use of a polynomial-size modulus assuming an a priori bound on the number of queries $Q$. It remains secure even when an adaptive adversary requests partial decryptions of both challenge and non-challenge ciphertexts, as long as for each ciphertext the number of corrupt parties plus the number of shares obtained is less than $t$. We provide concrete parameter suggestions for 128-bit security for a wide range of $(t,K,Q)$, including cases where $t \approx K/2$ for up to $K \leq 32$ users and $Q \leq 2^{60}$ partial decryption queries. The ciphertext size ranges from $14$ to $58$ KB and the partial decryption share size ranges from $1$ to $4$ KB.
Along the way, we abstract out a general purpose tool called the threshold-LWE assumption, which we prove to follow from LWE. The threshold-LWE assumption captures the core steps in security proofs of schemes involving Shamir's secret-sharing the LWE secret with carefully chosen evaluation points, the algebraic structures from the latter being what enabling the efficiency of our tPKE scheme. As an additional application, we also show how to construct distributed pseudorandom functions (dPRFs) from the threshold-LWE assumption.
## 2025/1692
* Title: Combined Stability: Protecting against Combined Attacks
* Authors: Dilara Toprakhisar, Svetla Nikova, Ventzislav Nikov
* [Permalink](https://eprint.iacr.org/2025/1692)
* [Download](https://eprint.iacr.org/2025/1692.pdf)
### Abstract
Physical attacks pose serious challenges to the secure implementation of cryptographic algorithms. While side-channel analysis (SCA) has received significant attention, leading to well-established countermeasures, fault attacks and especially their combination with SCA (i.e., combined attacks) remain less researched. Addressing such combined attacks often requires a careful integration of masking and redundancy techniques to resist the reciprocal effects of faults and probes. Recent research on combined security has gained momentum, with most approaches relying on composable security notions involving error correction, typically applied after each nonlinear operation. While effective, this approach introduces an area and performance overhead, along with additional security challenges posed by the correction circuits themselves.
In this work, we take a different direction, following the concept of stability introduced in StaTI (CHES 2024), which ensures fault propagation to protect against ineffective faults. We extend this concept to combined security by proposing a new composable security notion, combined stability, which integrates an extended stability notion, diffused stability, with arbitrarily composable glitch-extended probing security notions. Notably, this framework requires only a single error detection at the end of the computation, avoiding costly intermediate error checks and corrections. To demonstrate practicality, we describe a combined secure AES S-box hardware implementation. Our results show that this approach, achieving combined security with competitive implementation costs, offers a promising alternative to error-correction-based schemes.
## 2025/1693
* Title: Quasi-perfect (de)compression of elliptic curve points in the highly $2$-adic scenario
* Authors: Dimitri Koshelev
* [Permalink](https://eprint.iacr.org/2025/1693)
* [Download](https://eprint.iacr.org/2025/1693.pdf)
### Abstract
This short note is devoted to a significant enhancement of [8] by resolving satisfactorily the problem formulated at the end of that article. More precisely, a new laconic, secure, and efficient (de)compression method is provided for points of any elliptic curve over any highly $2$-adic finite field of large characteristic. Such fields are ubiquitous in modern elliptic curve cryptography, whereas they severely slow down the conventional $x$-coordinate (de)compression technique. In comparison with the main method from the cited work, the new one requires neither complicated mathematical formulas nor conditions on the curve. Thereby, the current work is universal and much more implementation-friendly, which justifies its existence, despite the absence of interesting mathematics behind it.
8. Koshelev, D.: Point (de)compression for elliptic curves over highly $2$-adic finite fields. Advances in Mathematics of Communications 19(5), 1539rCo1559 (2025), https://doi.org/10.3934/amc.2025008
## 2025/1694
* Title: Lattice Reduction via Dense Sublattices: A Cryptanalytic No-Go
* Authors: L|-o Ducas, Johanna Loyer
* [Permalink](https://eprint.iacr.org/2025/1694)
* [Download](https://eprint.iacr.org/2025/1694.pdf)
### Abstract
Most concrete analyses of lattice reduction focus on the BKZ algorithm or its variants relying on Shortest Vector Problem (SVP) oracles. However, a variant by Li and Nguyen (Cambridge U. Press 2014) exploits more powerful oracles, namely for the Densest rank-$k$ Sublattice Problem ($DSP_k$) for $k \geq 2$. We first observe that, for random lattices, $DSP_2$ --and possibly even $DSP_3$-- seems heuristically not much more expensive than solving SVP with the current best algorithm. We indeed argue that a densest sublattice can be found among pairs or triples of vectors produced by lattice sieving, at a negligible additional cost. This gives hope that this approach could be competitive.
We therefore proceed to a heuristic and average-case analysis of the slope of $DSP_k$-BKZ output, inspired by a theorem of Kim (Journal of Number Theory 2022) which suggests a prediction for the volume of the densest rank-$k$ sublattice of a random lattice.
Under this heuristic, the slope for $k=2$ or $3$ appears tenuously better than that of BKZ, making this approach less effective than regular BKZ using the "Dimensions for Free'' of Ducas (EUROCRYPT 2018). Furthermore, our experiments show that this heuristic is overly optimistic.
Despite the hope raised by our first observation, we therefore conclude that this approach appears to be a No-Go for cryptanalysis of generic lattice problems.
## 2025/1695
* Title: Mk-PIR: Multi-Keyword Private Information Retrieval
* Authors: Shengnan Zhao, Junyu Lu, Yuchen Huang, Dongdong Miao, Chuan Zhao
* [Permalink](https://eprint.iacr.org/2025/1695)
* [Download](https://eprint.iacr.org/2025/1695.pdf)
### Abstract
Private information retrieval (PIR) enables a client to fetch a record from databases held by untrusted servers while hiding the access pattern (index or keyword) from the servers.
In practical settings, however, data objects (e.g., articles, videos) are commonly tagged with multiple identifiers, which can be structured as {index, value, keywords}. Current PIR schemes are constrained to retrieving records based on a single index or a single keyword, and cannot efficiently handle conjunctive queries requiring multiple keywords. To address this limitation, we propose Mk-PIR, a PIR scheme that enables a client to retrieve records that match all specified keywords simultaneously.
We propose two distinct constructions: $\textsf{MkPIR}^\mathbf{I}$, an inverted-index-based solution built upon our Oblivious Set Intersection (OSI) primitive, which enables private intersection computation on the server side without revealing client queries; and $\textsf{MkPIR}^\mathbf{F}$, a forward-index-based solution utilizing our Private Subset Determination (PSD), which privately outputs matching indices by verifying subset relationships.
Two constructions adapt to diverse database configurations where keywords are not required to be the primary key. Experimental results show that the average time to determine whether an index satisfies multiple keywords ranges from 0.5 to 332 ms, demonstrating that Mk-PIR achieves flexible query capabilities with modest performance overhead.
## 2025/1696
* Title: Threshold ECDSA in Two Rounds
* Authors: Yingjie Lyu, Zengpeng Li, Hong-Sheng Zhou, Xudong Deng
* [Permalink](https://eprint.iacr.org/2025/1696)
* [Download](https://eprint.iacr.org/2025/1696.pdf)
### Abstract
We propose the first two-round multi-party signing protocol for the Elliptic Curve Digital Signature Algorithm (ECDSA) in the threshold-optimal setting, reducing the number of rounds by one compared to the state of the art (Doerner et al., S&P '24). We also resolve the security issue of presigning pointed out by Groth and Shoup (Eurocrypt '22), evading a security loss that increases with the number of pre-released, unused presignatures, for the first time among threshold-optimal schemes.
Our construction builds on Non-Interactive Multiplication (NIM), a notion proposed by Boyle et al. (PKC '25), which allows parties to evaluate multiplications on secret-shared values in one round. In particular, we use the construction of Abram et al. (Eurocrypt '24) instantiated with class groups. The setup is minimal and transparent, consisting of only two class-group generators. The signing protocol is efficient in bandwidth, with a message size of 1.9 KiB at 128-bit security, and has competitive computational performance.
## 2025/1697
* Title: Extract Discriminative Features: Profiled Side-Channel Analysis for Cryptosystems Based on Supervised Contrastive Learning
* Authors: Zoushaojie Jiang, An Wang, Yaoling Ding, Annv Liu, Zheng Liu, Jing Yu, Liehuang Zhu
* [Permalink](https://eprint.iacr.org/2025/1697)
* [Download](https://eprint.iacr.org/2025/1697.pdf)
### Abstract
Deep learning-based profiled side-channel analysis (SCA) targeting cryptographic implementations has attracted significant attention in recent years. Generalizable deep learning mechanisms, such as contrastive learning-based profiled SCA (CL-SCA), can enhance the effectiveness of SCA without reliance on specific network architectures and hyperparameters. This independence enables robust adaptation across diverse attack scenarios. Nonetheless, CL-SCA relies heavily on data augmentation and may mistakenly push apart physical leakage traces that should belong to the same class, which interferes with the extraction of discriminative features crucial for SCA performance. To address these limitations, we propose a profiled SCA method based on supervised contrastive learning, called SupCL-SCA. This method enhances the learning of discriminative features that facilitate key recovery by leveraging supervised information to guide the extraction of similarities in feature space. Compared with state-of-the-art methods, SupCL-SCA not only retains their general applicability and inherent advantages but also eliminates reliance on complex data augmentation and multi-stage training. Additionally, we propose a cosine distance-based Intra-Inter Distance Ratio (IIDR) metric to assess the discriminative capability of models in deep learning-based profiled SCA methods. We evaluate SupCL-SCA on three publicly available datasets covering different implementations and platforms. Experimental results show that SupCL-SCA consistently reduces the number of traces required to recover the key compared to the original methods, demonstrating enhanced attack capability.
## 2025/1698
* Title: SNARK Lower Bounds via Communication Complexity
* Authors: Rishabh Bhadauria, Alexander R. Block, Prantar Ghosh, Justin Thaler * [Permalink](https://eprint.iacr.org/2025/1698)
* [Download](https://eprint.iacr.org/2025/1698.pdf)
### Abstract
We initiate the study of lower bounding the verification time of Succinct Non-interactive ARguments of Knowledge (SNARKs) built in the Polynomial Interactive Oracle Proof + Polynomial Commitment Scheme paradigm. The verification time of these SNARKs is generally dominated by the polynomial commitment scheme, and so we want to understand if polynomial commitment schemes admit lower bounds on the verification time. By recognizing that polynomial commitment schemes are also often built by applying cryptography to some information-theoretic core protocol, we seek to separate this core from the cryptography in a way that meaningfully captures the verification time required by the polynomial commitment scheme verifier.
We provide strong evidence that several polynomial commitment schemes have (nearly) optimal verifier times. Our evidence comes from connecting polynomial commitment schemes to certain information-theoretic protocols known as communication protocols from the field of communication complexity, a link which we believe to be of independent interest. Through this lens, we model the verifier work in the cryptographic protocols as information (i.e., number of bits) exchanged between parties in the communication protocols, allowing us to leverage lower bounds from communication complexity. These lower bounds give strong evidence that the verifier time in these polynomial commitment schemes must be at least the number of bits exchanged in the communication protocol.
We extract the communication protocol cores of three polynomial commitment schemes and lower bound the bits exchanged in these cores. The lower bounds we obtain match (up to poly-logarithmic factors) the best-known (asymptotic) verification times of the polynomial commitment schemes we examine in this work. Specifically, we show that for univariate/multilinear polynomials of size $N=2^n$:
- the communication core of Hyrax PCS (Wahby et al., S&P 2016) requires $\Omega(\sqrt{N})$ bits to be exchanged;
- the communication core of Bulletproofs PCS (Bootle et al., EUROCRYPT 2016; B|+nz et al., S&P 2018) requires $\Omega(N)$ bits to be exchanged; and
- the communication core of Dory PCS (Lee, TCC 2021) requires $\Omega(\log(N))$ bits to be exchanged.
Our results strongly suggest a negative answer to a longstanding open question on whether the Bulletproofs verifier can be made sublinear time.
## 2025/1699
* Title: A Constant-Rate Compiler for MPC over Noisy Networks
* Authors: Ran Gelles, Carmit Hazay, Manuj Mukherjee, Jaspal Singh, Arun Yeragudipati, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2025/1699)
* [Download](https://eprint.iacr.org/2025/1699.pdf)
### Abstract
The study of efficient multi-party computation (MPC) has been a central focus in the cryptographic literature, producing a wide range of innovative techniques that have substantially improved the practicality of MPC in real-world applications. However, the vast majority of this work assumes reliable communication channels and neglects the impact of network-level noiserCoa fundamental characteristic of modern communication systems. Although classical error-correcting codes can be used to address such noise, they often introduce significant overhead, potentially offsetting the efficiency gains provided by advanced cryptographic methods. To the best of our knowledge, existing efforts to circumvent this limitation rely on alternative techniques restricted to the two-party setting, with approaches that do not naturally generalize to the multi-party case.
We initiate the study of information-theoretic MPC over noisy networks for more than two parties. We construct an MPC protocol that is secure against a semi-honest majority with an optimal communication overhead in circuit size: it computes any circuit $\mathcal{C}$ with communication complexity proportional to its size, i.e., $O(|\mathcal{C}|)$. Our protocol departs from the classical MPC methodology by introducing a novel multi-party interactive-coding that remedies channel noise through a new rewinding technique that also maintains the properties required for secure computation. The ideas of our interactive coding can be applied also to other MPC scenarios to eliminate channel noise. In fact, our treatment uncovers (and resolves) a subtle flaw in the constant-rate 2PC construction by Gelles et al. [SCN~'18] over noisy channels.
## 2025/1700
* Title: Computationally-Sound Symbolic Cryptography in Lean
* Authors: Stefan Dziembowski, Grzegorz Fabia+aski, Daniele Micciancio, Rafa+e Stefa+aski
* [Permalink](https://eprint.iacr.org/2025/1700)
* [Download](https://eprint.iacr.org/2025/1700.pdf)
### Abstract
We present a formally-verified (in Lean 4) framework for translating symbolic cryptographic proofs into the computationally-sound ones. Symbolic cryptography is a well-established field that allows reasoning about cryptographic protocols in an abstract way and is relatively easy to verify using proof assistants. Unfortunately, -ait often lacks a connection to the computational aspects of real-world cryptography. Computationally-sound cryptography, on the other hand, captures this connection much better, but it is often more complex, less accessible, and much harder to verify formally. Several works in the past have provided a bridge between the two, but, to our knowledge, none of them have been implemented in a proof assistant.
We close this gap by formalizing the translation from symbolic to computationally-sound cryptography in Lean 4. Our framework is based on the work of Micciancio (Eurocrypt, 2010) and Li and Micciancio (CSF, 2018), which builds on the idea of using co-induction (instead of induction) for reasoning about an adversary's knowledge in a symbolic setting. Our work encompasses (1) the formalization of the symbolic cryptography framework, (2) the formalization of the computationally sound cryptography framework, and (3) the formalization of the translation between the two. We also provide (4) an extended example of circuit garbling, which is a well-known cryptographic protocol frequently used in secure multi-party computation.
We believe that our work will serve as a foundation for future research in the area of formal verification of cryptographic protocols, as it enables reasoning about cryptographic protocols more abstractly while still providing a formally verified connection to the computational aspects of real-world cryptography.
## 2025/1701
* Title: BPSec-MLS: Asynchronous Key Agreement for Space Communications
* Authors: Xisen Tian, Paul Westland
* [Permalink](https://eprint.iacr.org/2025/1701)
* [Download](https://eprint.iacr.org/2025/1701.pdf)
### Abstract
Key agreement is the cornerstone of any secure communications channel whether over the traditional internet or in delay tolerant networks used in space communications. However, space systems that rely on pre-shared keys face insurmountable limitations in both security and scalability. A single key compromise can expose all past and future encrypted communications, and the static nature of pre-shared keys prevents dynamic group membership, making it difficult to add or remove devices without invalidating entire key sets. To address these challenges, the Messaging Layer Security (MLS) protocol -- a recently introduced internet standard for asynchronous group key establishment -- offers promising capabilities. Its potential to provide efficient and dynamic key agreement for federated interplanetary architectures (e.g. government-commercial collaborations) has been previously recognized, particularly with integration of MLS with the Bundle Protocol Security (BPSec) framework. In this work, we present the first empirical findings on the integration of MLS with BPSec in a realistic space communications scenario and provide insights into its deployment in future space architectures.
## 2025/1702
* Title: Lattice-Based Group Signatures in the Standard Model, Revisited
* Authors: Nam Tran, Khoa Nguyen, Dongxi Liu, Josef Pieprzyk, Willy Susilo
* [Permalink](https://eprint.iacr.org/2025/1702)
* [Download](https://eprint.iacr.org/2025/1702.pdf)
### Abstract
The study of lattice-based group signatures has been a prominent research direction since 2010. While recent advances in the field have yielded schemes in the random oracle model with strong security properties and nearly practical efficiency, the current state of affairs for lattice-based group signatures in the standard model is still much less satisfactory. Existing schemes, proposed by Katsumata and Yamada (EUROCRYPT'19) or implied by generic non-interactive zero-knowledge proofs for NP (by Peikert and Shiehian at CRYPTO'19 and by Waters at STOC'24), either only fulfil a weak notion of anonymity called selfless anonymity, or require a strong lattice assumption, or suffer from extremely large signatures and/or public keys.
This work aims to enhance the state of affairs for lattice-based group signatures in the standard model. We provide improved constructions that simultaneously achieves: (i) signature and public key sizes significantly smaller than those of known schemes; (ii) full anonymity in the CPA and CCA senses; (iii) security based on standard SIS and LWE assumptions with polynomial approximation factors regarding worst-case lattice problems (in general lattices). Our design approach slightly departs from that of existing pairing-based and lattice-based constructions. In the design process, we adapt and develop several lattice-based cryptographic ingredients that may be of independent interest. At the heart of our constructions is a reasonably efficient non-interactive zero-knowledge proof system for relations typically appearing in advanced privacy-preserving lattice-based cryptographic protocols. These relations are addressed by a trapdoor $\Sigma$-protocol with an inverse polynomial soundness error, which is made non-interactive via the standard-model Fiat-Shamir transform of Canetti et al. (STOC'19) and a compiler by Libert et al. (ASIACRYPT'20).
## 2025/1703
* Title: Updatable Signature from Lattices
* Authors: Haotian Yin, Jie Zhang, Wanxin Li, Yuji Dong, Eng Gee Lim, Dominik Wojtczak
* [Permalink](https://eprint.iacr.org/2025/1703)
* [Download](https://eprint.iacr.org/2025/1703.pdf)
### Abstract
Updatable Signature (US) schemes allow updating signatures so that they can be verified using a new key. This updating feature is useful for key rotation in practice. Cini et al. (PKC'21) first formalised this primitive. However, their post-quantum-secure US scheme does not satisfy their security definition, i.e., without unlinkability and only bounded unforgeability. This paper aims to solve this problem by providing a new fully secure construction. First, we simplify the definition of unlinkability by a hybrid argument, and reduce the update oracle of the unforgeability experiment by assuming unlinkability. Then, we construct our US scheme from verifiable encryption and the SIS assumption. This scheme is fully unlinkable and unforgeable, but also a unique signature scheme in each epoch, allowing only one signature for each message during one epoch and rendering a stateful signer/proxy. This is sufficient for many applications.
## 2025/1704
* Title: Data Anonymisation with the Density Matrix Classifier
* Authors: David Garvin, Mattia Fiorentini, Oleksiy Kondratyev, Marco Paini
* [Permalink](https://eprint.iacr.org/2025/1704)
* [Download](https://eprint.iacr.org/2025/1704.pdf)
### Abstract
We propose a new data anonymisation method based on the concept of a quantum feature map. The main advantage of the proposed solution is that a high degree of security is combined with the ability to perform classification tasks directly on the anonymised (encrypted) data resulting in the same or even higher accuracy compared to that obtained when working with the original plain text data. This enables important usecases in medicine and finance where anonymised datasets from different organisations can be combined to facilitate improved machine learning outcomes utilising the combined dataset. Examples include combining medical diagnostic imaging results across hospitals, or combining fraud detection datasets across financial institutions. We use the Wisconsin Breast Cancer dataset to obtain results on Rigetti's quantum simulator and Ankaa-3 quantum processor. We compare the results with classical benchmarks and with those obtained from an alternative anonymisation approach using a Restricted Boltzmann Machine to generate synthetic datasets. Finally, we introduce concepts from the theory of quantum magic to optimise the circuit ansatz and hyperparameters used within the quantum feature map.
## 2025/1705
* Title: Security Amplification of Threshold Signatures in the Standard Model
* Authors: Karen Azari, Cecilia Boschini, Kristina Host|ikov|i, Michael Reichle * [Permalink](https://eprint.iacr.org/2025/1705)
* [Download](https://eprint.iacr.org/2025/1705.pdf)
### Abstract
The current standardization calls for threshold signatures have highlighted the need for appropriate security notions providing security guarantees strong enough for broad application. To address this, Bellare et al. [Crypto'22] put forward a hierarchy of unforgeability notions for threshold signatures. Recently, Navot and Tessaro [Asiacrypt'24] introduced a new game-based definition of strong (one-more) unforgeability for threshold signatures, which however does not achieve Bellare's strongest level of security.
Navot and Tessaro analyzed several existing schemes w.r.t. their strong unforgeability security notion, but all positive results rely on idealized models. This is in contrast to the weaker security notion of (standard) unforgeability, for which standard-model constructions exist. This leaves open a fundamental question: is getting strong unforgeability fundamentally harder than standard unforgeability for threshold signatures?
In this paper we bridge this gap, by showing a generic construction lifting any unforgeable threshold signature scheme to strong unforgeability. The building blocks of our construction can be instantiated in the standard model under standard assumptions. The achieved notion of strong unforgeability extends the definition of Navot and Tessaro to achieve the strongest level of security according to the hierarchy of Bellare et al. (following a recent classification of security notions for (blind) threshold signatures by Lehmann, Nazarian, and |uzbay [Eurocrypt'25]).
The starting point for our transformation is an existing construction for single-user signatures from chameleon hash functions by Steinfeld, Pieprzyk and Wang [RSA'07]. We first simplify their construction by relying on a stronger security notion for chameleon hash functions. The bulk of our technical contribution is then to translate this framework into the threshold setting. Towards this goal, we introduce a game-based definition for threshold chameleon hash functions (TCHF) and provide a construction of TCHF that is secure under DLOG in the standard model. We believe that our new notion of TCHF might also be of independent interest.
## 2025/1706
* Title: Kani's lemma from Clifford algebra
* Authors: Tomoki Moriya
* [Permalink](https://eprint.iacr.org/2025/1706)
* [Download](https://eprint.iacr.org/2025/1706.pdf)
### Abstract
In 1997, Kani proved Kani's lemma, which asserts that a commutative diagram of four $g$rCadimensional abelian varieties induces an isogeny between product abelian varieties of dimension $2g$, in counting the number of genus-$2$ curves admitting two distinct elliptic subcovers. In these years, KanirCOs lemma plays a fundamental role in isogeny-based cryptography: KanirCOs lemma has found numerous cryptographic applications, including both cryptanalysis and protocol construction. However, direct investigation into the lemma itself remains scarce.
In this work, we propose a generalization of KanirCOs lemma. We present a novel formulation that, given a commutative diagram of $2^{n+1}$ abelian varieties of dimension $g$, yields an isogeny of dimension $2^{n}g$. We further establish a connection between this generalized lemma and the theory of Clifford algebras, using the latter as a foundational tool in our construction. To exemplify our framework, we explicitly construct the resulting $2^{n}g$rCadimensional isogenies for the cases $n=1,2,3$. The cases of $n=2,3$ provide nontrivial generalizations of the original Kani's lemma. This generalization is expected to have novel applications in the fields of both mathematics and cryptography.
## 2025/1707
* Title: Is It Even Possible? On the Parallel Composition of Asynchronous MPC Protocols
* Authors: Ran Cohen, Pouyan Forghani, Juan Garay, Rutvik Patel, Vassilis Zikas * [Permalink](https://eprint.iacr.org/2025/1707)
* [Download](https://eprint.iacr.org/2025/1707.pdf)
### Abstract
Despite several known idiosyncrasies separating the synchronous and the asynchronous models, asynchronous secure multi-party computation (MPC) protocols demonstrate high-level similarities to synchronous MPC, both in design philosophy and abstract structure. As such, a coveted, albeit elusive, desideratum is to devise automatic translators (e.g., protocol compilers) of feasibility and efficiency results from one model to the other.
In this work, we demonstrate new challenges associated with this goal. Specifically, we study the case of parallel composition in the asynchronous setting. We provide formal definitions of this composition operation in the UC framework, which, somewhat surprisingly, have been missing from the literature. Using these definitions, we then turn to charting the feasibility landscape of asynchronous parallel composition.
We first prove strong impossibility results for composition operators that do not assume knowledge of the functions and/or the protocols that are being composed. These results draw a grim feasibility picture, which is in sharp contrast with the synchronous model, and highlight the question:
Is asynchronous parallel composition even a realistic goal?
To answer the above (in the affirmative), we provide conditions on the composed protocols that enable a useful form of asynchronous parallel composition, as it turns out to be common in existing constructions.
## 2025/1708
* Title: The Semantic Holder (SH): Algebraic Extraction for Legal Opposability * Authors: MINKA MI NGUIDJOI Thierry Emmanuel
* [Permalink](https://eprint.iacr.org/2025/1708)
* [Download](https://eprint.iacr.org/2025/1708.pdf)
### Abstract
This manuscript introduces Semantic Holder (SH), the opposability primitive within the Chaotic Affine Secure Hash (CASH) toolkit, completing the frameworkrCOs implementation of the Q2CSI philosophy. SH enables legally opposable interpretations through algebraic extraction from polynomial iteration traces, working in concert with CEE (confidentiality) and AOW (reliability). Building upon the Affine Iterated Inversion Problem (AIIP) foundation, SH provides mathematically verifiable legal interpretations with guaranteed minimum opposability bounds. We establish that SH maintains an opposability score raa reN 0.60 through rigorous entropy preservation, institutional explainability, and legal contestability guarantees. The primitive features efficient STARK-proof verifiable computation, cross-jurisdictional compatibility, and quantum resistance through its reduction to AIIP hardness. We demonstrate practical applications in legal smart contracts, regulatory compliance auditing, and digital evidence authentication, providing concrete parameter recommendations for standard security levels. SH represents a
significant advancement in cryptographic systems that must operate within legal constraints, enabling transparent and verifiable legal opposability without compromising security or performance.
## 2025/1709
* Title: The zkVot Protocol: A Distributed Computation Protocol for Censorship Resistant Anonymous Voting
* Authors: Yunus G|+rlek, Kadircan Bozkurt
* [Permalink](https://eprint.iacr.org/2025/1709)
* [Download](https://eprint.iacr.org/2025/1709.pdf)
### Abstract
zkVot is a client side trustless distributed computation protocol that utilizes zero knowledge proving technology. It is designed to achieve anonymous and censorship resistant voting while ensuring scalability. The protocol is created as an example of how modular and distributed computation can improve both the decentralization and the scalability of the internet.
A complete and working implementation of this paper is available on https://github.com/node101-io/zkvot. It is important to emphasize that zkVot is one of the first complete implementations of a fully censorship resistant anonymous voting application that can scale up to a meaningful number of voters.
## 2025/1710
* Title: Information-Theoretic Broadcast-Optimal MPC
* Authors: Michele Ciampi, Ivan Damg|Nrd, Divya Ravi, Luisa Siniscalchi, Sophia Yakoubov
* [Permalink](https://eprint.iacr.org/2025/1710)
* [Download](https://eprint.iacr.org/2025/1710.pdf)
### Abstract
Broadcast, though often used as a black box in cryptographic protocols, is expensive to realize in terms of rounds and communication complexity. We investigate the minimal use of broadcast in round-optimal information-theoretic MPC, with statistical security. For information-theoretic MPC with guaranteed output delivery, four rounds of communication are necessary and sufficient (Applebaum, Kachlon and Patra, FOCS 2020; Applebaum, Kachlon and Patra, STOC 2023). We show that broadcast is unavoidable in the second and third rounds of statistical MPC protocols. To complement our lower bounds, we modify the protocol of Applebaum, Kachlon and Patra (STOC 2023) to make use of broadcast only in the second and third round. Along the way, we show that the sharing phase of any three-round information-theoretic VSS protocol must also make use of broadcast in the second and third rounds.
## 2025/1711
* Title: Accelerating FHEW-like Bootstrapping via New Configurations of the Underlying Cryptosystems
* Authors: Han Wang, Ming Luo, Han Xia, Mingsheng Wang, Hanxu Hou
* [Permalink](https://eprint.iacr.org/2025/1711)
* [Download](https://eprint.iacr.org/2025/1711.pdf)
### Abstract
This work introduces a new configuration of the GSW fully homomorphic encryption (FHE) (Gentry, Sahai, Waters~Crypto 2013), with a squared gadget ,batching and scale-based homomorphic operation.
This configuration offers improved efficiency compared to existing approaches. By utilizing our proposed method as the underlying building block, we can accelerate
FHEW-like bootstrapping implementations, including the libraries of FHEW and TFHE. We conduct comprehensive experiments to evaluate the concrete performance of our method, demonstrating improvements of more than 2 times faster. For example, the current ring GSW under OpenFHE takes 84 ms and TFHE takes 11.4 ms, while our approach achieves 26.2 ms and 4.8 ms, respectively. These improvements have significant implications for the practical aspects of FHE, enhancing real-world usability.
## 2025/1712
* Title: The Syndrome-Space Lens: A Complete Resolution of Proximity Gaps for Reed-Solomon Codes
* Authors: Russell Okamoto
* [Permalink](https://eprint.iacr.org/2025/1712)
* [Download](https://eprint.iacr.org/2025/1712.pdf)
### Abstract
We resolve the Correlated Agreement (CA) problem for Reed-Solomon codes up to the information-theoretic capacity limit by introducing a fundamental change of basis: from the traditional evaluation domain to the syndrome space. Viewed through this rCLSyndrome-Space Lens,rCY the problem of proximity testing transforms into a transparent question of linear-algebraic geometry: a single affine line of syndromes traversing a family of low-dimensional subspaces. This new perspective makes a sharp phase transition at the capacity boundary visible, allowing for a complete characterization of the problem's behavior across all parameter regimes, yielding short, self-contained proofs.
Classification. We establish a precise trichotomy organized by the rank margin $\Delta := t-d$. At the capacity boundary ($\Delta=0$), the CA premise is information-theoretically vacuous, and we prove that no rigidity can be concluded without imposing additional structure. One step beyond capacity ($\Delta=1$), the problem enters a rCLknife-edgerCY regime where unconditional rigidity does not hold; soundness is recovered either through a combinatorial witness (such as a repeated error support or a small union of supports) or by adding protocol-level structure (such as independent two-fold MCA checks, DEEP/STIR out-of-domain sampling, or a global error locator). For stricter gaps ($\Delta\ge 2$), unconditional rigidity holds under a simple algebraic condition ($(r{+}1)k<m{+}1$), with explicit quantitative bounds.
MCA and Practical Implications. Below capacity ($\delta<1-\rho$), the strengthened mutual correlated agreement (MCA) problem reduces to ordinary correlated agreement. MCA holds under the same hypotheses as CA. When folds are generated with independent challenges (e.g., via domain-separated Fiat-Shamir), the per-round security margins add. The model-scoped soundness law is $\Pr[\mathrm{FA}] \le q^{-(\sum \Delta_i) s}$, providing a clear and complete rulebook for selecting safe and efficient parameters in FRI/STARK systems. This work bypasses the complex machinery of list-decoding algorithms entirely and resolves the long-standing open problem concerning the gap between the Johnson bound and capacity.
## 2025/1713
* Title: Ilyazh-Web3E2E: A Post-Quantum Hybrid Protocol for Forward-Secure Decentralized Messaging
* Authors: Ilyas Zhaisenbayev
* [Permalink](https://eprint.iacr.org/2025/1713)
* [Download](https://eprint.iacr.org/2025/1713.pdf)
### Abstract
We propose Ilyazh-Web3E2E, a post-quantum hybrid messaging protocol combining classical and PQ-secure KEMs with forward secrecy and robust rekeying. The design augments the Double Ratchet model with hybrid key encapsulation (X25519 + ML-KEM), digital authentication (Ed25519 + ML-DSA), and re-encapsulation-based ratcheting for long-lived Web3 identity protection. The protocol emphasizes forward secrecy, post-compromise security, and decentralized identities. We sketch IND-CCA and AKE security arguments, present a concrete wire format, and provide comparisons with PQXDH and PQ3.
## 2025/1714
* Title: Verifiable PIR with Small Client Storage
* Authors: Mayank Rathee, Keewoo Lee, Raluca Ada Popa
* [Permalink](https://eprint.iacr.org/2025/1714)
* [Download](https://eprint.iacr.org/2025/1714.pdf)
### Abstract
Efficient Verifiable Private Information Retrieval (vPIR) protocols, and more generally Verifiable Linearly Homomorphic Encryption (vLHE), suffer from high client storage. VeriSimplePIR (USENIX Security 2024), the state-of-the-art vPIR protocol, requires clients to persistently maintain over 1 GiB of local storage to privately access an 8 GiB remote database. We present a new vPIR protocol that reduces the client state by orders of magnitude while preserving online latency. In our protocol, clients only need to store 512 KiB for an 8 GiB database, achieving a 2000|u improvement. Our vPIR protocol is built over our new vLHE scheme. Unlike VeriSimplePIR, our scheme doesnrCOt use random oracles and relies only on standard lattice assumptions - (R)LWE and SIS. These improvements come at a 2.5|u cost in server throughput over VeriSimplePIR. Despite this throughput overhead, we achieve a comparable online latency to VeriSimplePIR by implementing several optimizations including query-level preprocessing. We also introduce the notion of covert vPIR (cvPIR), where stateful clients enjoy full vPIR security, while even stateless clients benefit from covert security against a malicious server.
## 2025/1715
* Title: UltraMixer: A Compliant Zero-Knowledge Privacy Layer for Tokenized Real-World Assets
* Authors: Zonglun Li, Hong Kang, Xue Liu
* [Permalink](https://eprint.iacr.org/2025/1715)
* [Download](https://eprint.iacr.org/2025/1715.pdf)
### Abstract
Real-world-asset (RWA) tokens endow underlying assets with fractional ownership and more continuous settlement, yet recording these claims on transparent public ledgers exposes flows and positions, undermining market confidentiality. Practical deployments must reconcile enforceable access control with principled privacy once assets are shielded. We present UltraMixer, a noncustodial privacy layer natively compatible with ERC-3643. Compliance is enforced at the boundary via zero-knowledge proofs of whitelist membership, while in-mixer transfers and atomic trades operate over commitments with nullifiers to prevent double-spend. A generalized UTXO encoding supports heterogeneous assets (fungible and non-fungible) under a unified commitment scheme. For selective disclosure, UltraMixer provides a verdict-only $\Delta$-Window Proof of Holding that attests to continuous ownership across a time interval without revealing balances, identities, or linkages. Gas-aware batching and composable emergency controls (pause, freeze/unfreeze, force-transfer) preserve practicality and governance. The resulting architecture delivers regulator-compatible confidentiality for permissioned RWA markets.
## 2025/1716
* Title: Beyond Shannon: Operational Perfect Secrecy as a Generalised Model for Information-Theoretic Security
* Authors: Adrian Neal
* [Permalink](https://eprint.iacr.org/2025/1716)
* [Download](https://eprint.iacr.org/2025/1716.pdf)
### Abstract
ShannonrCOs 1949 theorem defines perfect secrecy as a condition where every possible message remains equally likely given any ciphertext, which requires a key at least as long as the message. This definition, while foundational, is binary and assumes uniform message priorsrCoassumptions rarely met in real communication systems. It cannot express the fact that secrecy degrades gradually as key entropy decreases, and it does not account for semantic structure or contextual knowledge available to adversaries.
This paper extends ShannonrCOs framework by introducing Operational Perfect Secrecy (OPS), which defines secrecy in terms of adversarial success probability rather than requiring complete message-space coverage. Within this framework we also define two new forms of information-theoretic security: Combinatorial ITS (C-ITS), which achieves OPS through combinatorial ambiguity of candidate decryptions, and Dimensional Ambiguity ITS (DA-ITS), which achieves OPS by concealing the dimensionality of the key space itself. We show that OPS converges to Shannon secrecy when the support size approaches the message space, while providing meaningful guarantees even with shorter keys.
These results generalise the concept of perfect secrecy into a continuous, operational measure and establish a new theoretical foundation for scalable information-theoretic security.
## 2025/1717
* Title: Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys
* Authors: Kuiyuan Duan, Hongbo Li, Dengfa Liu, Guangsheng Ma
* [Permalink](https://eprint.iacr.org/2025/1717)
* [Download](https://eprint.iacr.org/2025/1717.pdf)
### Abstract
Functional bootstrapping is a core technique in Fully Homomorphic Encryption(FHE). For large plaintext, to evaluate a general function homomorphically over a ciphertext, in the FHEW/TFHE approach, since the function in look-up table form is encoded in the coefficients of a test polynomial, the degree of the polynomial must be high enough to hold the entire table.
This increases the bootstrapping time complexity and memory cost, as the size of bootstrapping keys and keyswitching keys need to be large accordingly.
In this paper, we propose to encode the look-up table of any function in a polynomial vector, whose coefficients can hold more data. The corresponding representation of the additive group ${\mathbb Z}_q$ used in the RGSW-based bootstrapping is the group of monic monomial permutation matrices, which integrates the permutation matrix representation used by Alperin-Sheriff and Peikert in 2014, and the monic monomial representation used in the FHEW/TFHE scheme. We make comprehensive investigation of the new representation, and propose a new bootstrapping algorithm based on it.
The new algorithm supports functional bootstrapping of large-plaintexts, and achieves polynomial reduction in key sizes and a constant-factor improvement in run-time cost.
## 2025/1718
* Title: Indistinguishability Obfuscation from Ring Key-Homomorphic Weak PRFs
* Authors: Hart Montgomery, Sikhar Patranabis
* [Permalink](https://eprint.iacr.org/2025/1718)
* [Download](https://eprint.iacr.org/2025/1718.pdf)
### Abstract
A weak pseudorandom function $F: \mathcal{K} \times \mathcal{X} \rightarrow \mathcal{Y}$ is said to be ring key-homomorphic if, given $F \left(k_{1}, x \right)$ and $F \left(k_{2}, x \right)$, there are efficient algorithms to compute $F \left(k_{1} \oplus k_{2}, x \right)$ and $F \left(k_{1} \otimes k_{2}, x \right)$ where $\oplus$ and $\otimes$ are the addition and multiplication operations in the ring $\mathcal{K}$, respectively. A recent work by Alamati et al. (CT-RSA' 23) initiated the study of ring key-homomorphic weak PRFs (RKHwPRFs) and showed that any RKHwPRF can be used to construct multiparty noninteractive key exchange (NIKE) for an arbitrary number of parties. In this work, we show that any RKHwPRF can, in fact, be used to construct indistinguishability obfuscation (iO) for all circuits in NC$^1$, which in turn can be bootstrapped to all polynomial-size circuits using standard techniques. The proof of security for our iO construction is in the standard model, and our assumptions (including weakenings of RKHwPRFs) are program-independent.
We also consider restricted versions of RKHwPRFs that are structurally weaker than a classic RKHwPRF but suffice for all our constructions. We show how to instantiate these restricted RKHwPRFs from various multilinear maps and associated assumptions. Our framework gives several new results, notably the first iO scheme that relies on SXDH over the multilinear map presented by Ma and Zhandry (TCC' 18) (the authors only presented a NIKE protocol in their paper). To our knowledge, this candidate multilinear map has not been successfully cryptanalyzed, and the SXDH assumption plausibly holds over it.
Our result in a sense completes the work initiated by Alamati et al. (Eurocrypt' 19, JoC '23) on building cryptosystems from generic Minicrypt primitives with structure. Given our construction of iO from RKHwPRFs, almost all of the major known cryptosystems can be built from a weak PRF with either a group or ring homomorphism over either the input space or the key space. Thus, a major contribution of this work is advancing the study of the relationship between structure and cryptography.
## 2025/1719
* Title: Bribers, Bribers on The Chain, Is Resisting All in Vain? Trustless Consensus Manipulation Through Bribing Contracts
* Authors: Bence So||ki-T||th, Istv|in Andr|is Seres, Kamilla Kara, |Ubel Nagy, Bal|izs Pej||, Gergely Bicz||k
* [Permalink](https://eprint.iacr.org/2025/1719)
* [Download](https://eprint.iacr.org/2025/1719.pdf)
### Abstract
The long-term success of cryptocurrencies largely depends on the incentive compatibility provided to the validators. Bribery attacks, facilitated trustlessly via smart contracts, threaten this foundation. This work introduces, implements, and evaluates three novel and efficient bribery contracts targeting Ethereum validators. The first bribery contract enables a briber to fork the blockchain by buying votes on their proposed blocks. The second contract incentivizes validators to voluntarily exit the consensus protocol, thus increasing the adversary's relative staking power. The third contract builds a trustless bribery market that enables the briber to auction off their manipulative power over the RANDAO, Ethereum's distributed randomness beacon. Finally, we provide an initial game-theoretical analysis of one of the described bribery markets.
## 2025/1720
* Title: BATTLE rCo Bonded Adversarial TournamenT with Logarithmic Escalation
* Authors: Sergio Demian Lerner, Ariel Futoransky
* [Permalink](https://eprint.iacr.org/2025/1720)
* [Download](https://eprint.iacr.org/2025/1720.pdf)
### Abstract
In our work, we introduce BATTLE, Bonded Adversarial TournamenT with Logarithmic Escalation, a tournament-style protocol that solves multiparty disputes with simultaneous assertions such that (i) bounds honest asserter capital requirements to a constant minimum initial capital and (ii) resolves any number $C$ of concurrent challenges in $\mathcal{O}(\log C)$ dispute rounds, by reinvesting dispute rewards to fund subsequent rounds (progressive buy-ins) (iii) can be realized on a stateful (Quasi)Turing-complete smart-contract enabled blockchain.
BATTLE solves a set of conflicting assertions by creating a tournament with two phases: (1) a bracket among competing asserters with one dispute per party per round, and (2) a challenger phase against the winning assertion where the asserter engages in increasing number of simultaneous disputes each round.
--- Synchronet 3.21a-Linux NewsLink 1.2