From Newsgroup: sci.crypt

## In this issue
1. [2025/387] Generic Composition: From Classical to Quantum Security
2. [2025/1002] Cool + Cruel = Dual, and New Benchmarks for Sparse LWE
3. [2025/1003] Low-Latency Dynamically Available Total Order Broadcast
4. [2025/1306] Rethinking Learning-based Symmetric Cryptanalysis: ...
5. [2025/2024] A Note Comparing Three Incentive Designs Against ...
6. [2025/2025] Migration to Post-Quantum Cryptography: From ECDSA ...
7. [2025/2026] Whom do you trust? PRISM: Lightweight Key ...
8. [2025/2027] Accurate BGV Parameters Selection: Accounting for ...
9. [2025/2028] Improving ML-KEM and ML-DSA on OpenTitan - ...
10. [2025/2029] Forging Dilithium and Falcon Signatures by Single ...
11. [2025/2030] Succinct Zero-knowledge Proofs from One-way ...
12. [2025/2031] A Note on Notes: Towards Scalable Anonymous ...
13. [2025/2032] TrX: Encrypted Mempools in High Performance BFT ...
14. [2025/2033] Vestigial Vulnerabilities in Deployed Verifiable ...
15. [2025/2034] MtDB: A Decentralized Multi-Tenant Database for ...
16. [2025/2035] Multivariate Commitments and Signatures with ...
17. [2025/2036] On new variants of funcCPA security and related ...
18. [2025/2037] On the Simulation-Extractability of Proof-Carrying Data
19. [2025/2038] Breaking and Fixing MacaKey
20. [2025/2039] Non-Delegatable Commitments
21. [2025/2040] The Algebraic CheapLunch: Extending FreeLunch ...
22. [2025/2041] Sum-check Is All You Need: An Opinionated Survey on ...
23. [2025/2042] Threshold Anonymous Credentials with Silent Setup
24. [2025/2043] Key-Recovery Side-Channel Attack on the Berlekamp- ...
25. [2025/2044] New Asymptotic Results on Predicting Non-linear ...
26. [2025/2045] Handling Noisy Plaintext Checking Oracles with SPiRiT
27. [2025/2046] On ReedrCoSolomon Proximity Gaps Conjectures
28. [2025/2047] Enabling Index-free Adjacency in Oblivious Graph ...
29. [2025/2048] Time-Lock Encrypted Storage for Blockchains
30. [2025/2049] Black-Box Separation Between Multi-Collision ...
31. [2025/2050] TPL: Power Leakage Model Based on Technology Library
32. [2025/2051] All Polynomial Generators Preserve Distance with ...
33. [2025/2052] SoK: Systematizing Hybrid Strategies for the ...
34. [2025/2053] DIFA-Rent: Division Property Based Fault Attacks on ...
35. [2025/2054] Optimal Proximity Gaps for Subspace-Design Codes ...
36. [2025/2055] On Proximity Gaps for ReedrCoSolomon Codes
37. [2025/2056] Unclonable Cryptography in Linear Quantum Memory
38. [2025/2057] Distributed Key Generation for Efficient Threshold-CKKS
39. [2025/2058] Real-Time Encrypted Emotion Recognition Using ...
40. [2025/2059] Compact, Efficient and Non-Separable Hybrid Signatures
41. [2025/2060] Multi-homogeneous XL
42. [2025/2061] Multivariate Signatures with Polynomial Factorization
43. [2025/2062] Cryptanalysis of Multi-Party Key Exchange Protocols ...
44. [2025/2063] QUIC-MLS: Making a Space Security Draft Standard ...
## 2025/387
* Title: Generic Composition: From Classical to Quantum Security
* Authors: Nathalie Lang, Jannis Leuther, Stefan Lucks
* [Permalink](https://eprint.iacr.org/2025/387)
* [Download](https://eprint.iacr.org/2025/387.pdf)
### Abstract
Authenticated encryption (AE) provides both authenticity and privacy.
We investigate the security of generically composing unauthenticated encryption and authentication in a quantum setting where adversarial queries as well as the responses to those may be in superposition. This extends the work from Bellare and Namprempre in 2000, who considered the classical setting. First, we disprove a claim made by Soukharev et al. at PQCrypto 2016. Namely, we show that a chosen-plaintext (IND-qCPA) secure symmetric encryption scheme and a plus-one unforgeable message authentication code (MAC) exist, such that their generic (Encrypt-then-MAC) composition fails to achieve chosen-ciphertext (IND-qCCA) security.
On the other hand, we show that a stronger MAC (namely a qPRF) suffices for the composed scheme to be IND-qCCA secure.
Furthermore, the IND-qCCA notion proposed in related work assumes a randomized encryption operation. We propose to replace the randomness by a nonce, and to authenticate associated data, in addition to the message.
## 2025/1002
* Title: Cool + Cruel = Dual, and New Benchmarks for Sparse LWE
* Authors: Alexander Karenin, Elena Kirshanova, Julian Nowakowski, Eamonn W. Postlethwaite, Ludo N. Pulles, Fernando Virdia, Paul Vi|-
* [Permalink](https://eprint.iacr.org/2025/1002)
* [Download](https://eprint.iacr.org/2025/1002.pdf)
### Abstract
The sparse secret Learning with Errors (LWE) problem is a widely used assumption in efficient fully homomorphic constructions.
In [Wenger et al. IEEE S\&P 2025] two approaches, `Cool and CruelrCO (C+C) and the machine learning based `SALSA', were benchmarked against the well established primal attack on sparse secrets. The authors concluded that C+C outperforms SALSA and both outperform the primal attack.
In this work we show that the apparently novel C+C is an instantiation of a known dual attack [Albrecht, EUROCRYPT 2017].
To argue this we introduce a framework for dimension reduction in the bounded distance decoding problem that may be of independent interest.
Furthermore we prove that the C+C `phenomenon' is an expression of the geometry of the well known Z-shape basis in $q$-ary lattices, despite claims to the contrary.
We also show that a correctly parametrised primal attack outperforms C+C both in parameter regimes studied by Wenger et al. and in new parameter regimes.
To support this claim, we provide an open source implementation of two variants of the primal attack that are relevant for sparse secret LWE: Drop+Solve [May--Silverman, CaLC 2001] and Guess+Verify [Albrecht et al. SAC 2019].
## 2025/1003
* Title: Low-Latency Dynamically Available Total Order Broadcast
* Authors: Sravya Yandamuri, Nibesh Shrestha, Luca Zanolini, Kartik Nayak
* [Permalink](https://eprint.iacr.org/2025/1003)
* [Download](https://eprint.iacr.org/2025/1003.pdf)
### Abstract
This work addresses the problem of Byzantine Fault-Tolerant (BFT) Total-Order Broadcast (TOB) in a dynamically available setting, where parties can transition between online and offline states without knowing the number of active parties. Existing dynamically available protocols rely on a synchronous network assumption, which means their latency remains tied to the pessimistic network delay $\Delta$, even when the actual network delay is $\delta << \Delta$. This raises the question of whether a dynamically available BFT TOB protocol can maintain safety and liveness under synchrony while committing blocks at a rate closer to the actual network delay. We answer this question affirmatively by designing the first dynamically available BFT TOB protocol that can commit blocks at the rate of $O(\Delta_{ideal})$ where $\Delta_{ideal} < 2\delta$.
## 2025/1306
* Title: Rethinking Learning-based Symmetric Cryptanalysis: a Theoretical Perspective
* Authors: Yufei Yuan, Haiyi Xu, Jiaye Teng, Lei Zhang, Wenling Wu
* [Permalink](https://eprint.iacr.org/2025/1306)
* [Download](https://eprint.iacr.org/2025/1306.pdf)
### Abstract
In this paper, we revisit the standard approach to constructing neural distinguishers in symmetric cryptanalysis and introduce a game-like model, the Coin-Tossing model, to generalize this methodology. From the perspective of Boolean functions, we show that many classical cryptanalytic techniques can be generalized as a specific family of Boolean functions, termed the CPF class. We further explore the connection between learning CPF Boolean functions in the Coin-Tossing model and the well-known Learning Parity with Noise (LPN) problem. Leveraging the theoretical analysis, we identify key attributes of CPF functions that significantly affect how effectively machine learning algorithms can learn them. To validate our conclusions, we also conduct extensive experiments based on machine learning algorithms. Incorporating our theoretical insights, we propose an advanced 8-round and 9-round neural distinguisher for SPECK32/64 by reducing the problem complexity. Additionally, we propose a method based on the Goldreich-Levin algorithm to analyze and interpret what black-box distinguishers learn. Using this approach, we reinterpret several established neural distinguishers in terms of Fourier expansion. It is able to resolve the previous neural distinguisher in several Fourier terms. Notably, we identify a new type of distinguisher from neural networks that has not been discovered by cryptanalysts, which can be considered as a variant of the Differential-Linear distinguisher. We also demonstrate that the neural network not only learned the optimal Differential-Linear (DL) distinguishers found using existing MILP/MIQCP models, but also discovered even superior ones.
## 2025/2024
* Title: A Note Comparing Three Incentive Designs Against Privacy-Targeted Collusion
* Authors: Tiantian Gong
* [Permalink](https://eprint.iacr.org/2025/2024)
* [Download](https://eprint.iacr.org/2025/2024.pdf)
### Abstract
We compare three recent works on collusion deterrence mechanisms [SP'24, Eurocrypt'25, CCS'25] in privacy-preserving multi-party computations. They follow the same whistleblowing structure where an evidence collection module collects collusion evidence, and a mechanism assigns payments to deter incentive-driven parties from collusion.
For evidence collection module, two works [SP'24, Eurocrypt'25] provide a general method for generating collusion evidence while tolerating pre-existing leakage. The other work [CCS'25] abstracts evidence generation away, except for transparent service applications where the output is treated as the evidence.
For the incentive mechanisms, two works [SP'24, Eurocrypt'25] consider a mix of rational and malicious parties, and rational parties can act as an individual or as a member of a strong coalition, inside which parties trust each other and never harm other members. When parties act as individuals, given bounded malicious parties, one can design mechanisms to disincentivize collusion. When parties act as a coalition, the mechanisms can only limit the size of coalitions for exclusive secrets, i.e., more parties learning the secret reduces the value received by individuals. The most recent work [CCS'25] only models rational parties but considers colluding parties establishing retaliatory contracts to discourage betrayal among colluders. It was shown to be impossible to maintain non-collusion outcome if retaliatory contracts can impose unbounded penalties, and feasible to guarantee non-collusion otherwise. This is weaker than a strong coalition but admits mechanisms protecting secrets of a general nature.
## 2025/2025
* Title: Migration to Post-Quantum Cryptography: From ECDSA to ML-DSA
* Authors: Daniel Dinu
* [Permalink](https://eprint.iacr.org/2025/2025)
* [Download](https://eprint.iacr.org/2025/2025.pdf)
### Abstract
Cryptography is a fundamental building block of many security features like secure boot, remote attestation, trusted platform module (TPM), memory/disk encryption, and secure communication, providing confidentiality, data integrity, authentication, and non-repudiation. Post-Quantum Cryptography (PQC) marks an important milestone in the history of modern cryptography. It encompasses cryptographic algorithms designed to withstand cryptanalytic attacks from both quantum and classical computers.
Organizations around the world are currently in the process of migrating to the PQC algorithms standardized by the National Institute of Standards and Technologies (NIST). Compared to the previous changes of cryptographic algorithms, the transition to PQC poses new challenges. We exemplify some of them by analyzing implementation attacks (e.g., side-channel and fault injection) and countermeasures applicable to the signature generation of the Elliptic Curve Digital Signature Algorithm (ECDSA), a widely used cryptographic algorithm, and the Module-Lattice-Based Digital Signature Algorithm (ML-DSA), a quantum-resistant algorithm set to replace the former.
## 2025/2026
* Title: Whom do you trust? PRISM: Lightweight Key Transparency for All
* Authors: Sebastian Pusch, Ryan Quinn Ford, Joachim von zur Gathen, Alexander Markowetz
* [Permalink](https://eprint.iacr.org/2025/2026)
* [Download](https://eprint.iacr.org/2025/2026.pdf)
### Abstract
End-to-end encrypted (E2EE) messaging platforms serving hundreds of millions of users face a fundamental vulnerability: users must trust service providers to distribute authentic public keys. This problem creates opportunities for sophisticated man-in-the-middle attacks and surveillance. While key transparency systems promise to eliminate this trust requirement, existing solutions have failed to achieve practical deployment due to prohibitive cost in computation and bandwidth, and inadequate infrastructure.
Our main innovation is the integration of a zero-knowledge virtual machine to create a rCLrolluprCY architecture on a third-party data availability layer via which every user automatically checks the integrity of the whole key directory. Counterintuitively, this approach yields substantial performance improvements over custom-built zk proof circuits and enables verification of targeted policies within the cryptographic proof system.
We introduce PRISM, the first practically deployable key transparency protocol that eliminates hidden backdoors in E2EE services through automatic, trust-minimized verification. Our system advances beyond previous approaches by proving not just structural validity of key directory updates, but their semantic correctness as well.
Previous solutions require some form of manual interaction by the user. This burden prevented wide spread adoption. Our solution however eliminates user intervention entirely.
This paper is intended as an overview rather than an exhaustive specification. Our implemented system already integrates additional components whose full complexity exceeds the scope of this short presentation.
## 2025/2027
* Title: Accurate BGV Parameters Selection: Accounting for Secret and Public Key Dependencies in Average-Case Analysis
* Authors: Beatrice Biasioli, Chiara Marcolla, Nadir Murru, Matilda Urani
* [Permalink](https://eprint.iacr.org/2025/2027)
* [Download](https://eprint.iacr.org/2025/2027.pdf)
### Abstract
The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is one of the most significant fully homomorphic encryption (FHE) schemes.
It belongs to a class of FHE schemes whose security is based on the presumed intractability of the Learning with Errors (LWE) problem and its ring variant (RLWE).
Such schemes deal with a quantity, called noise, which increases each time a homomorphic operation is performed.
Specifically, in order for the scheme to work properly, it is essential that the noise remains below a certain threshold throughout the process.
For BGV, this threshold strictly depends on the ciphertext modulus, which is one of the initial parameters whose selection heavily affects both the efficiency and security of the scheme.
For an optimal parameter choice, it is crucial to accurately estimate the noise growth, particularly that arising from multiplication, which is the most complex operation.
In this work, we propose a novel average-case approach that precisely models noise evolution and guides the selection of initial parameters, improving efficiency while ensuring security.
The key innovation of our method lies in accounting for the dependencies among ciphertext errors generated with the same key, and in providing general guidelines for accurate parameter selection that are library-independent.
## 2025/2028
* Title: Improving ML-KEM and ML-DSA on OpenTitan - Efficient Multiplication Vector Instructions for OTBN
* Authors: Ruben Niederhagen, Hoang Nguyen Hien Pham
* [Permalink](https://eprint.iacr.org/2025/2028)
* [Download](https://eprint.iacr.org/2025/2028.pdf)
### Abstract
This work improves upon the instruction set extension proposed in the paper "Towards ML-KEM and ML-DSA on OpenTitan", in short OTBNTW, for OpenTitanrCOs big number coprocessor OTBN. OTBNTW introduces a dedicated vector instruction for prime-field Montgomery multiplication, with a high multi-cycle latency and a relatively low utilization of the underlying integer multiplication unit. The design targets post-quantum cryptographic schemes ML-KEM and ML-DSA, which rely on 12-bit and 23-bit prime field arithmetic, respectively. We improve the efficiency of the Montgomery multiplication by fully exploiting existing integer multiplication resources and move modular multiplication from hardware back to software by providing more powerful and versatile integer-multiplication vector instructions. This enables us not only to reduce the overall computational overhead through lazy reduction in software but also to improve performance in other functions beyond finite-field arithmetic. We provide two variants of our instruction set extension, each offering different trade-offs between resource usage and performance. For ML-KEM and ML-DSA, we achieve a speedup of up to 17% in cycle count, with an ASIC area increase of up to 6% and an FPGA resource usage increase of up to 4% more LUT, 20% more CARRY4, 1% more FF, and the same number of DSP compared to OTBNTW. Overall, we significantly reduce the ASIC time-area product, if the designs are clocked at their individual maximum frequency, and at least match that of OTBNTW, if the designs are clocked at the same frequency.
## 2025/2029
* Title: Forging Dilithium and Falcon Signatures by Single Fault Injection
* Authors: Sven Bauer, Fabrizio De Santis
* [Permalink](https://eprint.iacr.org/2025/2029)
* [Download](https://eprint.iacr.org/2025/2029.pdf)
### Abstract
Embedded devices commonly rely on digital signatures to ensure both integrity and authentication. For example, digital signatures are typically verified during the boot process or firmware updates to verify the integrity of a system. They are also used to ensure authenticity of a communication party in secure protocols.
Fault injection can be used to tamper with a device in order to cause malfunctioning during cryptographic computations. For example, fault injections can be used to disturb digital signing operations. With the right type of fault an attacker can compute private keys from faulted signatures. However, fault injections can also be used during verification to get maliciously crafted digital signatures accepted during signature verification with catastrophic consequences for the security of an embedded device.
In this paper, we introduce new non-obvious fault injection attacks on the verification routines of Dilithium and Falcon signature schemes, which allow an attacker to get signatures for arbitrary messages accepted by fault injection. We demonstrate the feasibility of our attacks by simulations using an ARM Cortex-M4 and the pqm4 library as a target of evaluation and pinpoint vulnerable instructions. Finally, we propose and discuss possible countermeasures against these attacks.
## 2025/2030
* Title: Succinct Zero-knowledge Proofs from One-way Functions:The Blackbox Way * Authors: Eden Florentz- Konopnicki, Ron D. Rothblum
* [Permalink](https://eprint.iacr.org/2025/2030)
* [Download](https://eprint.iacr.org/2025/2030.pdf)
### Abstract
Zero-knowledge proofs allow to encode a computation so that it can be verified without revealing any additional information beyond its correctness. In this work we focus on proofs that are statistically sound meaning that even an unbounded prover cannot make the verifier accept a false statement, except with negligible probability, and computationally zero-knowledge. The seminal result of Goldreich, Micali and Wigderson (CRYPTO 1986) shows that, assuming the existence of a one-way function, such zero-knowledge proofs exist for all languages in NP.
Some of the early protocols, such as that of GMW, have a large polynomial overhead in communication compared to the original NP witness. A line of works has shown that in many cases this communication overhead can be avoided.
Most recently, Athamnah et al. (TCC 2024) constructed zero-knowledge proofs for all bounded-depth NP relations, where the communication complexity is only larger by an additive factor than the original NP witness. The main caveat of their result is that the protocol makes a non-blackbox use of the one-way function.
In this work we show that such succinct zero-knowledge proofs exist for the same class of NP relations, where the protocol makes only a blackbox use of a one-way function. Our protocol achieves a negligible soundness error, in contrast to recent works which can achieve, at best, an inverse polynomial error.
## 2025/2031
* Title: A Note on Notes: Towards Scalable Anonymous Payments via Evolving Nullifiers and Oblivious Synchronization
* Authors: Sean Bowe, Ian Miers
* [Permalink](https://eprint.iacr.org/2025/2031)
* [Download](https://eprint.iacr.org/2025/2031.pdf)
### Abstract
Anonymous payment protocols based on Zerocash (IEEE S&P 2014) have seen widespread deployment in decentralized cryptocurrencies, as have derivative protocols for private smart contracts. Despite their strong privacy properties, these protocols have a fundamental scaling limitation in that they require every consensus participant to maintain a perpetually growing set of nullifiers --- unlinkable revocation tokens used to detect double-spending --- which must be stored, queried and updated by all validating nodes. This set grows linearly in the number of historic transactions and cannot be discarded without the undesirable effect of destroying unspent funds.
In this short note, we introduce a new technique that enables continual, permanent pruning of nullifiers by validators, without imposing significant computation, bandwidth or latency overhead for users, and without compromising privacy. Our main contribution is a general model we call oblivious synchronization, whereby users ask untrusted remote services (which ingest and process the public ledger) to create succinct proofs that coins are unspent and otherwise valid. Crucially, these services are fully oblivious to their clients' transaction details and cannot link their clients to any transactions that ultimately appear on the public ledger. Moreover, these services only keep ephemeral state per client and users can freely switch between services without incurring redundant computational effort.
## 2025/2032
* Title: TrX: Encrypted Mempools in High Performance BFT Protocols
* Authors: Rex Fernando, Guru-Vamsi Policharla, Andrei Tonkikh, Zhuolun Xiang
* [Permalink](https://eprint.iacr.org/2025/2032)
* [Download](https://eprint.iacr.org/2025/2032.pdf)
### Abstract
MEV (Maximal Extractable Value) remains one of the most corrosive forces in blockchain systems, enabling frontrunning, sandwiching, and other manipulations that directly exploit users. The core culprit is the transparent mempool: validators see transactions before they are ordered. Encrypted mempools are a promising solution by hiding transaction contents until after ordering.
We present the first integration of encrypted mempools with a high-performance BFT protocol. Our system uses a cryptographic scheme based on recent work on batched threshold encryption, and improves on the cryptographic state of the art in this line of work. The system ensures confidentiality of transactions during ordering while sustaining performance on par with leading BFT designs. Specifically, the proposal-to-execution latency of our system yields only a 27 ms overhead (14%) compared to the baseline. The result is a practical consensus layer that simultaneously defends against MEV and delivers the throughput and latency needed for real deployments. This work closes the gap between cryptographic defenses and production-ready consensus, showing that robust MEV protection and high performance can, in fact, coexist.
## 2025/2033
* Title: Vestigial Vulnerabilities in Deployed Verifiable E-Voting Systems
* Authors: Thomas Haines, Jarrod Rose
* [Permalink](https://eprint.iacr.org/2025/2033)
* [Download](https://eprint.iacr.org/2025/2033.pdf)
### Abstract
Electronic voting systems claiming to provide verifiability are seeing increased adoption. Previous work on analyzing these systems has focused on vulnerabilities arising in the specification and implementation of the core protocol and primitives; once the system has been analyzed for these vulnerabilities and appropriate fixes deployed, one might have hoped that the systems would provide the claimed security.
In this paper, we discuss two categories of vulnerabilities which still seem prevalent in otherwise carefully designed, implemented, and audited systems. We present ten examples of vulnerabilities or weaknesses in these categories drawn from the SwissPost and Belenios systems. Our discussion covers why vulnerabilities in these categories maybe escaping detection and what can be done about it; all the solutions we considered are unsatisfactory and our aim is to highlight this area as an important open problem.
## 2025/2034
* Title: MtDB: A Decentralized Multi-Tenant Database for Secure Data Sharing
* Authors: Showkot Hossain, Wenyi Tang, Changhao Chenli, Haijian Sun, WenZhan Song, Seokki Lee, Mic Bowman, Taeho Jung
* [Permalink](https://eprint.iacr.org/2025/2034)
* [Download](https://eprint.iacr.org/2025/2034.pdf)
### Abstract
Healthcare data sharing is fundamental for advancing medical research and enhancing patient care, yet it faces significant challenges in privacy, data ownership, and interoperability due to fragmented data silos across institutions and strict regulations (e.g., GDPR, HIPAA). To bridge these gaps, we propose MtDB, a novel decentralized database architecture addressing secure data sharing in multi-tenant database ecosystems. MtDB employs blockchain for metadata coordination and sharing, IPFS for distributed data addressing, a universal SQL query interface for data access, and Intel SGX for integrity-protected query execution with enforced access control. We provide an open-source implementation demonstrating MtDBrCOs capabilities for secure, patient-centric healthcare data sharing while preserving ownership and enforcing policies. Experimental results show MtDB achieves 35 milliseconds query latency for indexed queries over 400M multi-tenant medical records while maintaining cryptographic security guarantees, with only 1.2rCo1.3|u performance overhead compared to non-secure baselines.
## 2025/2035
* Title: Multivariate Commitments and Signatures with Efficient Protocols
* Authors: Charles Bouillaguet, Thibauld Feneuil, Jules Maire, Matthieu Rivain, Julia Sauvage, Damien Vergnaud
* [Permalink](https://eprint.iacr.org/2025/2035)
* [Download](https://eprint.iacr.org/2025/2035.pdf)
### Abstract
We revisit multivariate commitments based on the hardness of solving systems of multivariate quadratic (MQ) equations over finite fields. We analyze a simple construction where a message -| is committed as c = (-| + F(r), G(r)), with F and G random quadratic maps. We prove that the scheme is computationally hiding assuming the intractability of the MQ problem. Its binding property reduces to solving random bilinear systems. We prove that this problem is NP-complete and study the performance of existing algebraic and hybrid attacks. We show that this commitment is well-suited for integration with zero-knowledge proofs. Using the Threshold-computation-in-the-Head framework, we construct zero-knowledge efficient arguments of knowledge for the opening and arguments for relations on committed values. We apply this to construct an efficient blind signature scheme |a la Fischlin, and we demonstrate that our techniques yield a fully multivariate construction of signatures with efficient protocols, enabling practical post-quantum anonymous credentials.
## 2025/2036
* Title: On new variants of funcCPA security and related CCA-secure constructions
* Authors: Caroline Fontaine, Marc Renard, Renaud Sirdey, Oana Stan
* [Permalink](https://eprint.iacr.org/2025/2036)
* [Download](https://eprint.iacr.org/2025/2036.pdf)
### Abstract
FuncCPA is a recent security notion in which the CPA game is extended by a functional re-encryption oracle in order to model setups in which a server performing FHE computations is allowed to interactively delegate part of the computation back to the client. In this paper, we study funcCPA-style variants of several CCA security notions, including CCA1 and the more recent vCCA security. Contrary to the CPA case where a strict separation holds between CPA and funcCPA, we show that these new variants are equivalent to their respective originating CCA security notions.
Interestingly, funcCPA-style security notions also model setups where, rather than delegating part of the encrypted domain computation all the way back to the client, the server has the ability to perform this delegation towards a honest or semi-honest client proxy it hosts, such as a secure enclave. We then provide a number of blueprints for achieving both FHE-like capabilities and advanced CCA security properties which may then meaningfully be implemented by leveraging on the combination of a partially homormophic scheme and a semi-honest non-colluding enclave hosted within the server performing the encrypted domain calculations itself.
## 2025/2037
* Title: On the Simulation-Extractability of Proof-Carrying Data
* Authors: Behzad Abdolmaleki, Matteo Campanelli, Quang Dao, Hamidreza Khoshakhlagh
* [Permalink](https://eprint.iacr.org/2025/2037)
* [Download](https://eprint.iacr.org/2025/2037.pdf)
### Abstract
With proof-carrying data (PCD), nodes in a distributed computation can certify its correct execution obtaining proofs with low-verification overhead (relative to the complexity of the computation). As PCD systemsrCoand their special case, incrementally verifiable computation (IVC)rCosee rapid adoption in practice, understanding their robustness against malleability attacks becomes crucial. In particular, it remains unexplored whether recursive proof systems satisfy simulation extractability (SIM-EXT)rCoa property ensuring non-malleability and composability.
This work provides the first systematic study of simulation extractability for PCD. We begin by observing that the standard SIM-EXT notion for non-recursive zkSNARKs does not directly extend to PCD/IVC settings. To address this, we propose a new, tailored definition of SIM-EXT for proof-carrying data that accounts for their idiosyncratic features. Using this framework, we prove two general results: (1) that a simulation-extractable SNARK implies a simulation-extractable PCD when used recursively, and (2) that even lighter PCD constructionsrCobuilt from a (not necessarily succinct) argument of knowledge (NARK) combined with a split-accumulation schemerCoachieve SIM-EXT of PCD by requiring SIM-EXT only from the underlying NARK. Our results show that many modern PCD systems are already simulation-extractable by design.
## 2025/2038
* Title: Breaking and Fixing MacaKey
* Authors: Bishwajit Chakraborty, Chandranan Dhar
* [Permalink](https://eprint.iacr.org/2025/2038)
* [Download](https://eprint.iacr.org/2025/2038.pdf)
### Abstract
The sponge construction underpins many modern symmetric primitives, enabling efficient hashing and authenticated encryption. While full-state absorption is known to be secure in keyed sponges, the security of full-state squeezing has remained unclear. Recently, Lefevre and Marhuenda-Beltr\'an introduced \(\textsf{MacaKey}\), claiming provable security even when both phases operate over the full state. In this work, we revisit this claim and show that \(\textsf{MacaKey}\) is insecure. A simple four-query distinguishing attack violates its claimed bound, exploiting the exposure of the full internal state and the resulting loss of secrecy in the capacity portion during squeezing. We then propose two simple yet effective fixes that restore security with negligible overhead. The first,
\(\textsf{pMacaKey}\), introduces an additional permutation between the absorption and squeezing phases to re-randomize the internal state. The second, \(\textsf{KeyMacaKey}\), achieves a similar effect by incorporating a keyed finalization step without requiring an extra permutation call. We formally prove the security of both \(\textsf{pMacaKey}\) and \(\textsf{KeyMacaKey}\) in the random permutation model. Both variants retain the full-state efficiency of \(\textsf{MacaKey}\) while ensuring strong, provable security guarantees.
## 2025/2039
* Title: Non-Delegatable Commitments
* Authors: Georg Fuchsbauer, Pranav Garimidi, Guru-Vamsi Policharla, Max Resnick, Ertem Nusret Tas
* [Permalink](https://eprint.iacr.org/2025/2039)
* [Download](https://eprint.iacr.org/2025/2039.pdf)
### Abstract
Cryptographic commitments allow a party to commit to a value such that it is computationally infeasible to later open that commitment to a different value. Although they are ubiquitous, standard commitment schemes allow the committer to outsource both the generation of the commitment and the openings to a third party. This is benign for most use cases; however, when commitments serve as cryptographic attestations of work such as relaying blocks or storing data, participants can outsource the task and still claim credit, undermining the intended economic properties of the protocol. This work initiates the study of non-delegatable commitments, a new primitive where forming a commitment requires possession of a private key, and delegating the commitment process necessarily leaks that key. We formally define the primitive and provide a generic construction that is secure in the random oracle model given a polynomial commitment scheme. Additionally, we show how this primitive can be applied to solve a variety of mechanism design problems.
## 2025/2040
* Title: The Algebraic CheapLunch: Extending FreeLunch Attacks on Arithmetization-Oriented Primitives Beyond CICO-1
* Authors: Antoine Bak, Augustin Bariant, Aur|-lien Boeuf, Pierre Briaud, Morten |yygarden, Atharva Phanse
* [Permalink](https://eprint.iacr.org/2025/2040)
* [Download](https://eprint.iacr.org/2025/2040.pdf)
### Abstract
The security of many arithmetization-oriented (AO) hash functions depends of the hardness of Constrained-input constrained-output (CICO) problems. These problems have received significant attention from the cryptographic community in recent years, with notable advances in Gr||bner basis and resultant-based attacks, yet progress has mainly been limited to CICO problems restricted to a single output. In this work, we build on the "FreeLunch method" of Bariant et al. (Crypto 2024) that constructs Gr||bner bases "for free" in this particular case, and extend it to CICO problems with multiple outputs. More precisely, we consider tools for solving weighted polynomial systems, and show how to apply them in the AO setting. This results in new polynomial modelings, more efficient methods for computing the initial Gr||bner basis under certain assumptions, and improved complexity estimates for the change of ordering step, derived from tighter upper bounds on the ideal degree. We apply our framework to Poseidon, Neptune and XHash8, where our assumptions are experimentally verified, and theory matches practice. For Griffin and ArionHash our assumptions are not verified, leaving us with improved, yet loose, upper bounds on the ideal degree. While our results do not threaten the security of any full-round hash function, they provide new insights into the security of these primitives under more general CICO problems.
## 2025/2041
* Title: Sum-check Is All You Need: An Opinionated Survey on Fast Provers in SNARK Design
* Authors: Justin Thaler
* [Permalink](https://eprint.iacr.org/2025/2041)
* [Download](https://eprint.iacr.org/2025/2041.pdf)
### Abstract
SNARKs work by having a prover commit to a witness and then prove that the committed witness is valid. The proverrCOs work is dominated by two tasks: (i) committing to data and (ii) proving that the committed data is well-formed. The central thesis of this survey is that fast SNARKs minimize both costs by using the sum-check protocol.
But not all uses of sum-check are equally effective. The fastest SNARKs invoke sum-check in highly sophisticated ways, exploiting repeated structure in computation to aggressively minimize commitment costs and prover work. I survey the key ideas that enable this: batch evaluation arguments, read/write memory checking, virtual polynomials, sparse sum-checks, and small-value preservation. These techniques unlock the full potential of the sum-check protocol as a foundation for fast SNARK proving.
## 2025/2042
* Title: Threshold Anonymous Credentials with Silent Setup
* Authors: Preshtha Garg, Sanjam Garg, Guru-Vamsi Policharla, Bhaskar Roberts
* [Permalink](https://eprint.iacr.org/2025/2042)
* [Download](https://eprint.iacr.org/2025/2042.pdf)
### Abstract
Anonymous credentials allow users to authenticate themselves in an anonymous and unlinkable fashion. By the end of 2026, EU member states will be required to issue digital identity wallets to their residents that enable authentication in this manner. In decentralized settings, we desire schemes with additional properties: schemes that allow multiple authorities to issue credentials, hide the identities of the issuers, and allow verifiers to dynamically choose their policies.
We present the first construction of issuer-hiding anonymous credentials with constant-sized showing, threshold issuance, and no requirement of interactive setup. Silent (non-interactive) setup is crucial as the various issuers may be slow-moving, independent organizations that are unwilling to coordinate in a distributed key generation protocol beforehand. Our construction also supports dynamic verifier policies. This is useful if different verifiers disagree about which issuers they trust or what threshold they accept.
At the heart of our scheme, we construct threshold structure-preserving signatures with silent setup and prove security in the generic group model. We also provide a NIZK for anonymous showing that is more efficient than a standard application of Groth-Sahai proofs. Finally, we provide an implementation of our scheme in Rust, along with concrete efficiency metrics.
## 2025/2043
* Title: Key-Recovery Side-Channel Attack on the Berlekamp-Massey Decoding Algorithm in the Classic McEliece KEM
* Authors: Andrei Alexei, Marios Omar Choudary, Vlad-Florin Dragoi
* [Permalink](https://eprint.iacr.org/2025/2043)
* [Download](https://eprint.iacr.org/2025/2043.pdf)
### Abstract
In this article, we provide the first side-channel attack on the Berlekamp- Massey (BM) algorithm, which is the decoder used in the decryption process of the Classic McEliece KEM. We conduct a chosen plaintext key recovery attack that exploits the power consumption of the BM, which is highly dependent on the secret Goppa support elements. We exploit the relation between plaintexts of small
Hamming weight, secret elements in the Goppa support and power traces using an efficient Template Attack. Our method completely recovers the secret Goppa support
for the first parameter set of the Classic McEliece KEM using a single attack trace
per secret coefficient. The entire support can be recovered in less than 7 seconds on
a standard computer. Our experiments are performed using the ChipWhisperer-Lite board platform with the ARM Cortex-M4 microcontroller.
## 2025/2044
* Title: New Asymptotic Results on Predicting Non-linear Polynomial Congruential Generators
* Authors: Mengce Zheng, Yansong Feng, Abderrahmane Nitaj, Yanbin Pan
* [Permalink](https://eprint.iacr.org/2025/2044)
* [Download](https://eprint.iacr.org/2025/2044.pdf)
### Abstract
We investigate cryptanalytic attacks on non-linear polynomial congruential generators (PCGs), a class of number-theoretic pseudorandom number generators. A PCG operates by iterating an algebraic map $F(x) \bmod{p}$ on a secret initial seed $v_0$ using fixed parameters, and outputs a truncated portion of each state (for example, the most significant bits). We propose new and improved lattice-based attacks that exploit systems of modular polynomial equations derived from PCGs.
Specifically, we analyze three common non-linear PCGs: the Quadratic Congruential Generator (QCG), the Power Generator, and the Pollard Generator. We establish asymptotic bounds for predicting these PCGs, assuming the adversary has access to an infinitely long output sequence. To derive these bounds, we develop new symbolic techniques that build on the automated Coppersmith's method framework recently developed by Feng et al. (Crypto '25). Our approach is more flexible than previous methods and is particularly well-suited for deriving symbolic bounds. Applying our techniques, we obtain the best-known analytical results for asymptotic attacks on these PCGs:
We present, for the first time, asymptotic attack bounds on QCGs with partially known coefficients.
We extend and improve the asymptotic attack of Herrmann and May (Asiacrypt '09) on Power Generators.
We improve the asymptotic attack of Bauer et al. (PKC '12) on Pollard Generators and confirm their conjecture.
We validate our theoretical findings with numerical experiments that demonstrate the practicality and efficacy of our attacks.
## 2025/2045
* Title: Handling Noisy Plaintext Checking Oracles with SPiRiT
* Authors: Paco Poilbout, Thomas Roche, Laurent Imbert
* [Permalink](https://eprint.iacr.org/2025/2045)
* [Download](https://eprint.iacr.org/2025/2045.pdf)
### Abstract
Post-Quantum key encapsulation mechanisms based on the re-encryption framework of Fujisaki and Okamoto have proved very sensitive to Plaintext Checking Oracle (PCO) attacks. The first theoretic works on PCO attacks were rapidly followed by practical attacks on real implementations, notably on NIST standardized ML-KEM. The actual realization of a PCO relies on side-channel leakages that are inherently noisy ; even more so if the implementation embeds side-channel countermeasures.
In this paper we tackle the often overlooked complications caused by highly noisy PCOs. We demonstrate that the impact of wrong oracle answers can be very efficiently reduced with the use of the so-called Sequential Probability Ratio Test (SPRT). This test can be seen as an elegant and natural early abort strategy on top of the commonly used approaches based on majority-voting or the likelyhood ratio test. As far as we know, this is the first use of SPRT in the context of side-channel attacks. We show that it allows to divide by a factor up to 3 the attack complexity compared to the traditional approaches. By establishing new comparisons with recently published noisy PCO attacks we emphasize that SPRT should be considered as the novel baseline for all future works in this line of research.
## 2025/2046
* Title: On ReedrCoSolomon Proximity Gaps Conjectures
* Authors: Elizabeth Crites, Alistair Stewart
* [Permalink](https://eprint.iacr.org/2025/2046)
* [Download](https://eprint.iacr.org/2025/2046.pdf)
### Abstract
We disprove a range of conjectures for Reed-Solomon codes underpinning the security and efficiency of many modern proof systems, including SNARKs based on FRI (Ben-Sasson-Bentov-Horesh-Riabzev, ICALPrCO18), DEEP-FRI (Ben-Sasson-Goldberg-Kopparty-Saraf, ITCSrCO20), STIR (Arnon-Chiesa-Fenzi-Yogev, CRYPTOrCO24), and WHIR (Arnon-Chiesa-Fenzi-Yogev, preprint). Concretely, we prove that the following conjectures are false:
1. The correlated agreement up-to-capacity conjecture of Ben-Sasson-Carmon-Ishai-Kopparty-Saraf (J. ACMrCO23),
2. The mutual correlated agreement up-to-capacity conjecture of WHIR,
3. The list-decodability up-to-capacity conjecture of DEEP-FRI, which follows from existing results in the literature.
We then propose minimal modifications to these conjectures up to the list-decoding capacity bound.
Our second main contribution is a proof that correlated agreement with small enough error probability implies list decoding of Reed-Solomon codes. Thus, any future results on our correlated agreement conjectures with small enough error probability would imply similar results in classical list decoding. A reduction from proximity gaps to list-decodability was heretofore a natural open problem.
## 2025/2047
* Title: Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications
* Authors: Weiqi Feng, Xinle Cao, Adam O'Neill, Chuanhui Yang
* [Permalink](https://eprint.iacr.org/2025/2047)
* [Download](https://eprint.iacr.org/2025/2047.pdf)
### Abstract
Obliviousness has been regarded as an essential property in encrypted databases (EDBs) for mitigating leakage from access patterns. Yet despite decades of work, practical oblivious graph processing remains an open problem. In particular, all existing approaches fail to enable the design of index-free adjacency (IFA), i.e., each vertex preserves the physical positions of its neighbors. However, IFA has been widely recognized as necessary for efficient graph processing and is fundamental in native graph databases (e.g., Neo4j).
In this work, we propose a core technique named delayed duplication to resolve the conflict between IFA and obliviousness. To the best of our knowledge, we are the first to address this conflict with both practicality and strict security. Based on the new technique, we utilize elaborate data structures to develop a new EDB named Grove for processing expressive graph queries. The experimental results demonstrate that incorporating IFA makes Grove impressively outperform the state-of-the-art work across multiple graph-processing tasks, such as the well-known neighbor query and $t$-hop query.
## 2025/2048
* Title: Time-Lock Encrypted Storage for Blockchains
* Authors: Amit Agarwal, Kushal Babel, Sourav Das, Babak Poorebrahim Gilkalaye * [Permalink](https://eprint.iacr.org/2025/2048)
* [Download](https://eprint.iacr.org/2025/2048.pdf)
### Abstract
We introduce time-lock encrypted storage (tTLES), a storage service provided by blockchains. In tTLES, clients store encrypted values towards a future decryption time $\tau_{tgt}$ (measured in block height). The security of tTLES requires that a value is decrypted only if (i) the encrypted value is included in the blockchain, and (ii) the time $\tau_{tgt}$ has passed. This is crucially different from existing schemes, which only enforce either of these conditions but not both. We formalize tTLES, and present an efficient protocol that relies on (in a black-box manner) a threshold identity-based encryption scheme, and a recent batch threshold decryption scheme. Finally, we discuss various applications that will benefit from tTLES.
## 2025/2049
* Title: Black-Box Separation Between Multi-Collision Resistance and Collision Resistance
* Authors: Xinyu Mao, Jiapeng Zhang
* [Permalink](https://eprint.iacr.org/2025/2049)
* [Download](https://eprint.iacr.org/2025/2049.pdf)
### Abstract
A $K$-multi-collision-resistant hash function ($K$-MCRH) is a shrinking keyed function for which it is computationally infeasible to find $K$ distinct inputs that map to the same output under a randomly chosen hash key; the case $K = 2$ coincides with the standard definition of collision-resistant hash function (CRH).
A natural question is whether $K$-MCRH implies CRH for $K \geq 3$, as noted by Komargodski, Naor, and Yogev (EUROCRYPT 2018) and also by Jain, Li, Robere, and Xun (FOCS 2024).
We resolve this question for all constant $K$, showing that there is no black-box construction of $K$-MCRH from $(K + 1)$-MCRH for all constant $K \geq 2$. We also show that there is no black-box construction of distributional CRH (which is another relaxation of CRH) from 3-MCRH, answering an open question posed by Komargodski and Yogev (CRYPTO 2018) and also by Berman, Degwekar, Rothblum, and Vasudevan (EUROCRYPT 2018). Besides applications in cryptography, our separation also implies black-box separations between TFNP search problems, which are related to problems in proof complexity and other areas.
## 2025/2050
* Title: TPL: Power Leakage Model Based on Technology Library
* Authors: Sumesh Manjunath Ramesh, Hoda Alkhzaimi
* [Permalink](https://eprint.iacr.org/2025/2050)
* [Download](https://eprint.iacr.org/2025/2050.pdf)
### Abstract
In our increasingly interconnected world, the security of embedded devices plays a critical role in protecting sensitive information. Evaluating this security requires a meticulous examination of how cryptographic processes are implemented within the hardware of these devices. One widely employed technique for this purpose is Power Side Channel Analysis. At the heart of Correlation Power Side Channel Analysis lies the concept of the power consumption model, which helps to simulate power consumption while executing cryptographic operations on hardware. In this model, along with the hypothetical secret key, is correlated with the actual power consumption during the execution of a cryptographic operation under an unknown secret key. This approach enables the detection of potential vulnerabilities in cryptographic implementations. In this research, we introduce a novel power leakage model called the Technology library Power Leakage Model. This model is rooted in semiconductor technology. By aligning our model closely with specific semiconductor technology, we achieve a more realistic representation of power consumption. Our study provides compelling evidence for the effectiveness of the Power Leakage Model. We successfully extracted secret keys from an AES implementation using Correlation Power Analysis (CPA). Importantly, our Power Leakage Model can be adapted to accommodate various semiconductor technologies such as $55nm$ or $14nm$ technologies. In this work, we also compared the newly proposed leakage model with the Hamming Distance model and empirically evaluated that both models perform similarly when linear correlation techniques are used in CPA.
## 2025/2051
* Title: All Polynomial Generators Preserve Distance with Mutual Correlated Agreement
* Authors: Sarah Bordage, Alessandro Chiesa, Ziyi Guan, Ignacio Manzur
* [Permalink](https://eprint.iacr.org/2025/2051)
* [Download](https://eprint.iacr.org/2025/2051.pdf)
### Abstract
A generator is a function that maps a random seed to a list of coefficients. We study generators that preserve distance to a linear code: the linear combination of any list of vectors using coefficients sampled by the generator has distance to the code no smaller than that of the original vectors, except for a small error. Distance preservation plays a central role in modern probabilistic proofs, and has been formalized in several ways. We study \emph{mutual correlated agreement}, the strongest known form of distance preservation.
We initiate the systematic study of mutual correlated agreement, aiming to characterize the class of generators with this property. Towards this, we study polynomial generators, a rich class that includes all examples of generators considered in the distance preservation literature. Our main result is that \emph{all polynomial generators guarantee mutual correlated agreement for every linear code}. This improves on prior work both in generality (the class of generators covered) and in parameters (the error bounds).
We additionally provide new results for the case where the linear code is a Reed--Solomon code, which is of particular interest in applications. We prove that all polynomial generators satisfy mutual correlated agreement for ReedrCoSolomon codes up to the Johnson bound. In particular, we improve upon the state-of-the-art by Ben-Sasson, Carmon, Ishai, Kopparty, and Saraf (FOCS 2020) and resolve a question posed by Arnon, Chiesa, Fenzi, and Yogev (Eurocrypt 2025).
Along the way we develop a flexible and general toolbox for mutual correlated agreement, are the first to establish distance preservation for generators that lie beyond polynomial generators.
## 2025/2052
* Title: SoK: Systematizing Hybrid Strategies for the Transition to Post-Quantum Cryptography
* Authors: Abdoul Ahad Fall
* [Permalink](https://eprint.iacr.org/2025/2052)
* [Download](https://eprint.iacr.org/2025/2052.pdf)
### Abstract
The rapid advancements in quantum computing pose a significant threat to widely used cryptographic standards such as RSA and Elliptic-Curve Diffie-Hellman (ECDH), which are fundamental to securing digital communications and protecting sensitive data worldwide. The increasing feasibility of "harvest now, decrypt later" strategies where adversaries collect encrypted data today with the intent of decrypting it once quantum computing reaches sufficient maturity underscores the urgency of transitioning toward quantum-resistant cryptographic solutions. A pragmatic approach to maintaining security during this transitional period is the adoption of hybrid cryptographic techniques, which integrate traditional cryptographic mechanisms with post-quantum cryptography (PQC) and Quantum Key Distribution (QKD).
This paper presents a comprehensive review of hybrid cryptographic approaches, focusing on their incorporation into widely adopted security protocols such as TLS 1.3 and QUIC. We examine the key challenges associated with deploying hybrid cryptography, including performance trade-offs, security guarantees, and compatibility with existing infrastructure. Beyond protocol-level implementations, we explore the initiatives undertaken by global standardization bodies and leading technology firms to facilitate a seamless transition toward a quantum-secure future. By analyzing current strategies and insights from early adopters, we identify the critical factors that organizations must consider to effectively implement hybrid cryptographic solutions, ensuring resilience against emerging cryptographic threats.
## 2025/2053
* Title: DIFA-Rent: Division Property Based Fault Attacks on DEFAULT and BAKSHEESH
* Authors: Shibam Ghosh, Anup Kumar Kundu, Dhiman Saha
* [Permalink](https://eprint.iacr.org/2025/2053)
* [Download](https://eprint.iacr.org/2025/2053.pdf)
### Abstract
Fault attacks have historically been one of the most popular gray-box attacks in Cryptographic literature.
In such attacks, an attacker tries to inject perturbations while executing a cipher and exploit the faulty outputs to recover the key.
While the efficiency of such an attack is measured by number of faults required and size of the reduced key-space, another pivotal temporal parameter in the point of fault injection which has not received considerable attention.
In this work, we plug this gap for a special class of ciphers namely DEFAULT and BAKSHEESH which boast of an SBox with one or more linear structures (LS).
We make new observations which lead to the improvement of Division Property based fault attacks (DIFA) introduced by Kundu et al. in ACNS 2023.
We show that these linear structures are particularly responsible for giving the higher fault penetration in these ciphers.
We improve the state-of-the-art for BAKSHEESH from 30 to 28 rounds and for DEFAULT from 75 to 72 using the single round random nibble fault model.
While for BAKSHEESH we are able to uniquely recover the key, for DEFAULT, we are able to reduce the key-space to $2^{64}$.
This leads to the best fault attacks on BAKSHEESH and DEFAULT in terms of number of rounds penetrated for fault injection.
Our work reiterates the fact that a property induced (in this case LS in SBox)) for some particular Cryptographic purposes (like fault attack resistance) may manifest orthogonally for another (increasing fault penetration) and thus adds value to block cipher design space exploration and fault attack counter-measure development.
## 2025/2054
* Title: Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes
* Authors: Rohan Goyal, Venkatesan Guruswami
* [Permalink](https://eprint.iacr.org/2025/2054)
* [Download](https://eprint.iacr.org/2025/2054.pdf)
### Abstract
Reed-Solomon (RS) codes were recently shown to exhibit an intriguing $\textit{proximity gap}$ phenomenon. Specifically, given a collection of strings with some algebraic structure (such as belonging to a line or affine space), either all of them are $\delta$-close to RS codewords, or most of them are $\delta$-far from the code. Here $\delta$ is the proximity parameter which can be taken to be the Johnson radius $1-\sqrt{R}$ of the RS code ($R$ being the code rate), matching its best known list-decodability. Proximity gaps play a crucial role in the soundness analysis of Interactive Oracle Proof (IOP) protocols used in Succinct Non-Interactive Arguments of Knowledge (SNARKs) and the resulting proof sizes.
Proving proximity gaps beyond the Johnson radius, and in particular approaching $1-R$ (which is best possible), has been posed multiple times as a challenge with significant practical consequences to the efficiency of SNARKs. Here we prove that variants of RS codes, such as folded RS codes and univariate multiplicity codes, indeed have proximity gaps for $\delta$ approaching $1-R$. The result applies more generally to codes with a certain subspace-design property. Our proof hinges on a clean property we abstract called line (or more generally curve) decodability, which we establish leveraging and adapting techniques from recent progress on list-decoding such codes. Importantly, our analysis avoids the heavy algebraic machinery used in previous works, and requires a field size only linear in the block length.
The behavior of subspace-design codes w.r.t ``local properties'' has recently been shown to be similar to random linear codes and random RS codes (where the evaluation points are chosen at random from the underlying field). We identify a local property that implies curve decodability, and thus also proximity gaps, and thereby conclude that random linear and random RS codes also exhibit proximity gaps up to the $1-R$ bound. Our results also establish the stronger (mutual) correlated agreement property which implies proximity gaps. Additionally, we also a show a $\textit{slacked}$ proximity gap theorem for constant-sized fields using AEL-based constructions and local property techniques.
## 2025/2055
* Title: On Proximity Gaps for ReedrCoSolomon Codes
* Authors: Eli Ben-Sasson, Dan Carmon, Ulrich Hab||ck, Swastik Kopparty, Shubhangi Saraf
* [Permalink](https://eprint.iacr.org/2025/2055)
* [Download](https://eprint.iacr.org/2025/2055.pdf)
### Abstract
This paper is about the proximity gaps phenomenon for Reed-Solomon codes.
Very roughly, the proximity gaps phenomenon for a code $\mathcal C \subseteq \mathbb F_q^n$ says that for two vectors $f,g \in \mathbb F_q^n$, if sufficiently many linear combinations $f + z \cdot g$ (with $z \in \mathbb F_q$) are close to $\mathcal C$ in Hamming distance, then so are both $f$ and $g$, up to a proximity loss of $\varepsilon^*$.
Determining the optimal quantitative form of proximity gaps for Reed--Solomon codes has recently become of great interest because of applications to interactive proofs and cryptography, and in particular, to scalable transparent arguments of knowledge (STARKs) and other modern hash based argument systems used on blockchains today.
Our main results show improved positive and negative results for proximity gaps for Reed-Solomon codes of constant relative distance $\delta \in (0,1)$.
1. For proximity gaps up to the unique decoding radius $\delta/2$, we show that arbitrarily small proximity loss $\varepsilon^* > 0$ can be achieved with only $O_{\varepsilon^*}(1)$ exceptional $z$'s (improving the previous bound of $O(n)$ exceptions).

2. For proximity gaps up to the Johnson radius $J(\delta)$, we show that proximity loss $\varepsilon^* = 0$ can be achieved with only $O(n)$ exceptional $z$'s (improving the previous bound of $O(n^2)$ exceptions).
This significantly reduces the soundness error in the aforementioned arguments systems.
3. In the other direction, we show that for some Reed--Solomon codes and some $\delta$, proximity gaps at or beyond the Johnson radius $J(\delta)$ with arbitrarily small proximity loss $\varepsilon^*$ needs to have at least $\Omega(n^{1.99})$ exceptional $z$'s.
4. More generally, for all constants $\tau$, we show that for some Reed-Solomon codes and some $\delta = \delta(\tau)$, proximity gaps at radius $\delta - \Omega_{\tau}(1)$ with arbitrarily small proximity loss $\varepsilon^*$ needs to have $n^{\tau}$ exceptional $z$'s.
5. Finally, for all Reed-Solomon codes, we show that improved proximity gaps imply improved bounds for their list-decodability. This shows that improved bounds on the list-decoding radius of Reed-Solomon codes is a prerequisite for any new proximity gaps results beyond the Johnson radius.
## 2025/2056
* Title: Unclonable Cryptography in Linear Quantum Memory
* Authors: Omri Shmueli, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2025/2056)
* [Download](https://eprint.iacr.org/2025/2056.pdf)
### Abstract
Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys. Typically, this is to ensure the keys cannot be copied by an adversary, owing to the quantum no-cloning theorem. Unfortunately, due to quantum state's tendency to decohere, persistent quantum memory will likely be one of the most challenging resources for quantum computers. As such, it will be important to minimize persistent memory in quantum protocols.
In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens. These are important unclonable primitives, where quantum signing keys allow for signing a single message but not two. Naturally, these quantum signing keys would require storage in long-term quantum memory. Very recently, the first OSS was constructed in a classical oracle model and also in the standard model, but we observe that the quantum memory required for these protocols is quite large. In this work, we significantly decrease the quantum secret key size, in some cases achieving asymptotically optimal size. To do so, we develop novel techniques for proving the security of cryptosystems using coset states, which are one of the main tools used in unclonable cryptography.
## 2025/2057
* Title: Distributed Key Generation for Efficient Threshold-CKKS
* Authors: Seonhong Min, Guillaume Hanrot, Jai Hyun Park, Alain Passel|?gue, Damien Stehl|-
* [Permalink](https://eprint.iacr.org/2025/2057)
* [Download](https://eprint.iacr.org/2025/2057.pdf)
### Abstract
Threshold fully homomorphic encryption provides efficient multi-party computation with low round-complexity. Among fully homomorphic encryption schemes, CKKS (Cheon-Kim-Kim-Song) enables high-throughput computations on both approximate and exact data. As most interesting applications involve deep computations, they require bootstrapping, the most efficient variants of which rely on sparse ternary secret keys. Unfortunately, so far, key generation protocols for threshold-CKKS either assume a trusted dealer, or lead to dense and non-ternary secret keys that severely damage computational throughput. In the latter case, the impact is so large that one often considers off-loading bootstrapping to an interactive protocol [Mouchet et al., PETS'21].
We introduce a novel Distributed Key Generation (DKG) protocol for threshold-CKKS. At a high level, it consists in running the existing distributed key generation algorithm from Mouchet et al. resulting in large secret keys, and using it to homomorphically evaluate the sparse-secret key generation algorithm. At the end, the parties obtain additive shares of a sparse secret key. The main technical challenge is to obtain an algorithm for sampling sparse ternary vectors of prescribed Hamming weight that can be CKKS-evaluated in an efficient manner. In the process, we design a new sampler of one-hot vectors that outperforms the one from [Boneh et al., AFT'20]. We also design a rejection-sampling algorithm to map several one-hot vectors into a vector of prescribed Hamming weight. The whole process can be performed with only two CKKS bootstraps, even for a significant number of users.
We present several variants of the DKG protocol, with~2 to~4 communication rounds, as well as an extension to key generation delegation. We implemented the 4-round protocol; its computational components run in 2.13s on GPU (RTX4090).
## 2025/2058
* Title: Real-Time Encrypted Emotion Recognition Using Homomorphic Encryption
* Authors: Gyeongwon Cha, Dongjin Park, Yejin Choi, Eunji Park, Joon-Woo Lee
* [Permalink](https://eprint.iacr.org/2025/2058)
* [Download](https://eprint.iacr.org/2025/2058.pdf)
### Abstract
Emotion recognition has been an actively researched topic in the field of HCI. However, multimodal datasets used for
emotion recognition often contain sensitive personal information, such as physiological signals, facial images, and behavioral
patterns, raising significant privacy concerns. In particular, the privacy issues become crucial in workplace settings because
of the risks such as surveillance and unauthorized data usage caused by the misuse of collected datasets. To address this
issue, we propose an Encrypted Emotion Recognition (EER) framework that performs real-time inference on encrypted data
using the CKKS homomorphic encryption (HE) scheme. We evaluated the proposed framework using publicly available
WESAD and Hide-and-seek datasets, demonstrating successful stress/emotion recognition under encryption. The results
demonstrated that encrypted inference achieved similar accuracy to plaintext inference, with accuracy of 0.966 (plaintext)
vs. 0.967 (ciphertext) on the WESAD dataset, and 0.868 for both cases on the Hide-and-Seek dataset. Encrypted inference
was performed on a GPU, with average inference times of 333 milliseconds for the general model and 455 milliseconds for
the personalized model. Furthermore, we validated the feasibility of semi-supervised learning and model personalization in
encrypted environments, enhancing the frameworkrCOs real-world applicability. Our findings suggest that the EER framework
provides a scalable, privacy-preserving solution for emotion recognition in domains such as healthcare and workplace settings,
where securing sensitive data is of critical importance.
## 2025/2059
* Title: Compact, Efficient and Non-Separable Hybrid Signatures
* Authors: Julien Devevey, Morgane Guerreau, Maxime Rom|-as
* [Permalink](https://eprint.iacr.org/2025/2059)
* [Download](https://eprint.iacr.org/2025/2059.pdf)
### Abstract
The transition to post-quantum cryptography involves balancing the long-term threat of quantum adversaries with the need for post-quantum algorithms and their implementations to gain maturity safely. Hybridization, i.e. combining classical and post-quantum schemes, offers a practical and safe solution.
We introduce a new security notion for hybrid signatures, Hybrid EU-CMA, which captures cross-protocol, separability, and recombination attacks that may occur during the post-quantum transition, while encompassing standard unforgeability guarantees.
Using this framework, we adapt the Fiat-Shamir (with or without aborts) transform to build hybrid signature schemes that satisfy our notion from two identification schemes.
Compared to simple concatenation of signatures, our construction (i) has no separability issues, (ii) reduces signature size, (iii) runs faster, and (iv) remains easily implementable.
As a concrete application, we propose Silithium, a hybrid signature combining the identification schemes underlying EC-Schnorr and ML-DSA.
Implementing Silithium requires only an ML-DSA implementation supporting the ``external $\mu$'' option during verification and an elliptic curve library.
In the security analysis, we show that our scheme can be safely used along with ML-DSA and either EC-Schnorr or ECDSA.
A proof-of-concept OpenSSL implementation demonstrates its practicality, simplicity, and performance.
## 2025/2060
* Title: Multi-homogeneous XL
* Authors: Kai-Chun Ning, Lars Ran, Simona Samardjiska
* [Permalink](https://eprint.iacr.org/2025/2060)
* [Download](https://eprint.iacr.org/2025/2060.pdf)
### Abstract
Algebraic cryptanalysis is an important and versatile tool in the evaluation of the security of various cryptosystems especially in multivariate cryptography. Its effectiveness can be determined by analyzing the Polynomial System Solving problem (PoSSo). However, the polynomial systems arising from cryptanalytic algebraic models often exhibit structure that is crucial for the solving complexity and is often not well understood.
In this paper we turn our focus to multi-homogeneous systems that very often arise in algebraic models. Despite their overwhelming presence, both the theory and the practical solving methods are not complete. Our work fills this gap.

We develop a theory for multi-homogeneous systems that extends the one for regular and semi-regular sequences. We define "border-regular" systems and provide exact statements about the rank of a specific submatrix of the Macaulay that we associate to these systems. We then use our theoretical results to define Multi-homogeneous XL - an algorithm that extends XL to the multi-homogeneous case. We further provide fully optimized implementation of Multi-homogeneous XL that uses sparse linear algebra and can handle a vast parameter range of multi-homogeneous systems. To the best of our knowledge this is the first implementation of its kind, and we make it publicly available.
## 2025/2061
* Title: Multivariate Signatures with Polynomial Factorization
* Authors: Irene Di Muzio, Martin Feussner, Igor Semaev
* [Permalink](https://eprint.iacr.org/2025/2061)
* [Download](https://eprint.iacr.org/2025/2061.pdf)
### Abstract
We propose a new multivariate digital signature scheme whose central mapping arises from the product of two one-variate polynomials over a finite field $\mathbb{F}_q$. The resulting quadratic transformation is efficiently invertible through polynomial factorization, defining the trapdoor mechanism. The public key comprises $m$ bilinear forms in $2n$ variables, obtained by masking the central map with secret linear transformations. A reference implementation targeting NIST security level 1 achieves a 24-byte signature and a 23-kilobyte public key. This signature size is among the smallest ever proposed for level 1 security and the scheme achieves verification efficiency comparable to the fastest existing designs. Security relies on the hardness of solving certain bilinear systems, for which it seems no efficient classical or quantum algorithms are known.
## 2025/2062
* Title: Cryptanalysis of Multi-Party Key Exchange Protocols over a Modified Supertropical Semiring
* Authors: Sulaiman Alhussaini, Serge-#|a Sergeev
* [Permalink](https://eprint.iacr.org/2025/2062)
* [Download](https://eprint.iacr.org/2025/2062.pdf)
### Abstract
We present a cryptanalysis of a multi-party key exchange protocol over a modified supertropical semiring, as proposed in a recent work of R. Ponmaheshkumar, J. Ramalingam, and R. Perumal. Building on the established methods for solving linear systems $A \otimes x=b$ over the tropical semiring, as well as on our recent work on solving such systems over layered semirings such as the symmetrized and supertropical semirings, we develop a method to compute a solution of $A \otimes x=b$ over the above mentioned modified supertropical semiring. This method enables the attacker to recover the shared secret key by solving the one-sided linear system derived from the public messages of the protocol. Our findings show that this modified supertropical platform does not provide the intended security and motivate further exploration of secure semiring-based constructions.
## 2025/2063
* Title: QUIC-MLS: Making a Space Security Draft Standard Resilient for Disconnected Environments
* Authors: Benjamin Dowling, Britta Hale, Xisen Tian, Bhagya Wimalasiri
* [Permalink](https://eprint.iacr.org/2025/2063)
* [Download](https://eprint.iacr.org/2025/2063.pdf)
### Abstract
Among standardization efforts for space and interplanetary
network security, the Internet Engineering Task Force (IETF) is driv-
ing work on space network security, accounting for the unique proper-
ties of space environments that make space communication challenging.
This includes long, variable-length delays, packet loss, and intermittent end-to-end connectivity. Within these efforts, there is a focus on using IP-based protocols for security, and in particular the use of the QUIC protocol. This is unsurprising given QUICrCOs growing popularity and of-
fer of optimization intended for reducing latency. However, QUIC uses
the Transport Layer Security (TLS) key exchange handshake protocol,
which was originally designed for rCyconnect and forgetrCO style Internet con- nections at scale. It is also session-based, where protocol participants require reestablishment of the session for each reconnection rCo a costly maneuver in the space setting. Furthermore, TLS by default does not
achieve strong post-compromise security properties within sessions, ex- hibiting a risk under long-lived connections, and need for synchronous handshakes to counteract this are in functional contrast to the space environment, which has intermittent end-to-end connectivity.
We address both drawbacks of QUIC by introducing QUIC-MLS: a vari-
ant of QUIC which replaces the session-based, synchronous TLS hand-
shake with the standardized continuous key agreement protocol, Mes-
saging Layer Security (MLS), which achieves asynchronous forward se-
crecy and post-compromise security. In addition to the design itself, we implement our design and provide benchmarks, and analyze our new
construction in a formal cryptographic model.
--- Synchronet 3.21a-Linux NewsLink 1.2