[digest] 2025 Week 23

## In this issue

1. [2023/210] New Generic Constructions of Error-Correcting PIR ...
2. [2024/361] Key Exchange with Tight (Full) Forward Secrecy via ...
3. [2025/201] Cryptanalysis of Isogeny-Based Quantum Money with ...
4. [2025/259] Improved Resultant Attack against Arithmetization- ...
5. [2025/616] State Machine Replication Among Strangers, Fast and ...
6. [2025/889] At the Top of the Hypercube -- Better Size-Time ...
7. [2025/1019] Silent Splitter: Privacy for Payment Splitting via ...
8. [2025/1020] Separating Pseudorandom Codes from Local Oracles
9. [2025/1021] Black-Box Crypto is Useless for Pseudorandom Codes
10. [2025/1022] Burn Your Vote: Decentralized and Publicly ...
11. [2025/1023] Universal Channel Rebalancing: Flexible Coin ...
12. [2025/1024] Towards Trustless Provenance: A Privacy-Preserving ...
13. [2025/1025] Secure Noise Sampling for Differentially Private ...
14. [2025/1026] Malicious Security in Collaborative zk-SNARKs: More ...
15. [2025/1027] Parallel Repetition for Post-Quantum Arguments
16. [2025/1028] Group Key Progression: Strong Security for Shared ...
17. [2025/1029] Improved Key Recovery Attacks of Ascon
18. [2025/1030] Everlasting Anonymous Rate-Limited Tokens
19. [2025/1031] Quasidifferential Saves Infeasible Differential: ...
20. [2025/1032] Constant-Round Asynchronous MPC with Optimal ...
21. [2025/1033] Trusted Hardware-Assisted Leaderless Byzantine ...
22. [2025/1034] JANUS: Enhancing Asynchronous Common Subset with ...
23. [2025/1035] Continuous Group-Key Agreement: Concurrent Updates ...
24. [2025/1036] A Critique on Average-Case Noise Analysis in RLWE- ...
25. [2025/1037] Committed Vector Oblivious Linear Evaluation and ...
26. [2025/1038] Security of Operations on Random Numbers: A Review
27. [2025/1039] Unbounded Distributed Broadcast Encryption and ...
28. [2025/1040] Weave: Efficient and Expressive Oblivious Analytics ...
29. [2025/1041] Rubato: Provably Post-Quantum Secure and Batched ...
30. [2025/1042] Crowhammer: Full Key Recovery Attack on Falcon with ...
31. [2025/1043] Designing QC-MDPC Public Key Encryption Schemes ...
32. [2025/1044] When Threshold Meets Anamorphic Signatures: What is ...
33. [2025/1045] Constrained Verifiable Random Functions Without ...
34. [2025/1046] A Quasi-polynomial Time Algorithm for the ...
35. [2025/1047] Orient Express: Using Frobenius to Express Oriented ...
36. [2025/1048] One-way multilinear functions of the second order ...
37. [2025/1049] XHMQV: Better Efficiency and Stronger Security for ...
38. [2025/1050] Integral Resistance of Block Ciphers with Key ...
39. [2025/1051] Synergy: A Lightweight Block Cipher with Variable ...
40. [2025/1052] How to Trace Viral Content in End-to-End Encrypted ...
41. [2025/1053] Breaking the 1/λ-Rate Barrier for Arithmetic Garbling
42. [2025/1054] Rewardable Naysayer Proofs
43. [2025/1055] Single-server Stateful PIR with Verifiability and ...
44. [2025/1056] Private Signaling Secure Against Actively Corrupted ...

## 2023/210

* Title: New Generic Constructions of Error-Correcting PIR and Efficient Instantiations
* Authors: Reo Eriguchi, Kaoru Kurosawa, Koji Nuida
* [Permalink](https://eprint.iacr.org/2023/210)
* [Download](https://eprint.iacr.org/2023/210.pdf)

### Abstract

A $b$-error-correcting $m$-server Private Information Retrieval (PIR) protocol enables a client to privately retrieve a data item of a database from $m$ servers even in the presence of $b$ malicious servers. List-decodable PIR is a generalization of error-correcting PIR to achieve a smaller number of servers at the cost of giving up unique decoding. Previous constructions of error-correcting and list-decodable PIR have exponential computational complexity in $m$ or cannot achieve sub-polynomial communication complexity $n^{o(1)}$, where $n$ is the database size. Recently, Zhang, Wang and Wang (ASIACCS 2022) presented a non-explicit construction of error-correcting PIR with $n^{o(1)}$ communication and polynomial computational overhead in $m$. However, their protocol requires the number of servers to be larger than the minimum one $m=2b+1$ and they left it as an open problem to reduce it. As for list-decodable PIR, there is no construction with $n^{o(1)}$ communication.

In this paper, we propose new generic constructions of error-correcting and list-decodable PIR from any one-round regular PIR. Our constructions increase computational complexity only by a polynomial factor in $m$ while the previous generic constructions incur $\binom{m}{b}$ multiplicative overheads. Instantiated with the best-known protocols, our construction provides for the first time an explicit error-correcting PIR protocol with $n^{o(1)}$ communication, which reduces the number of servers of the protocol by Zhang, Wang and Wang (ASIACCS 2022). For sufficiently large $b$, we also show the existence of $b$-error-correcting PIR with $n^{o(1)}$ communication achieving the minimum number of servers, by allowing for two rounds of interaction. Furthermore, we show an extension to list-decodable PIR and obtain for the first time a protocol with $n^{o(1)}$ communication. Other instantiations improve the communication complexity of the state-of-the-art $t$-private protocols in which $t$ servers may collude. Along the way, we formalize the notion of \textit{locally surjective map families}, which generalize perfect hash families and may be of independent interest.



## 2024/361

* Title: Key Exchange with Tight (Full) Forward Secrecy via Key Confirmation
* Authors: Jiaxin Pan, Doreen Riepel, Runzhi Zeng
* [Permalink](https://eprint.iacr.org/2024/361)
* [Download](https://eprint.iacr.org/2024/361.pdf)

### Abstract

Weak forward secrecy (wFS) of authenticated key exchange (AKE) protocols is a passive variant of (full) forward secrecy (FS). A natural mechanism to upgrade from wFS to FS is the use of key confirmation messages which compute a message authentication code (MAC) over the transcript. Unfortunately, Gellert, Gjøsteen, Jacobson and Jager (GGJJ, CRYPTO 2023) show that this mechanism inherently incurs a loss proportional to the number of users, leading to an overall non-tight reduction, even if wFS was established using a tight reduction.

Inspired by GGJJ, we propose a new notion, called one-way verifiable weak forward secrecy (OW-VwFS), and prove that OW-VwFS can be transformed tightly to FS using key confirmation in the random oracle model (ROM). To implement our generic transformation, we show that several tightly wFS AKE protocols additionally satisfy our OW-VwFS notion tightly. We highlight that using the recent lattice-based protocol from Pan, Wagner, and Zeng (CRYPTO 2023) can give us the first lattice-based tightly FS AKE via key confirmation in the classical random oracle model. Besides this, we also obtain a Decisional-Diffie-Hellman-based protocol that is considerably more efficient than the previous ones.

Finally, we lift our study on FS via key confirmation to the quantum random oracle model (QROM). While our security reduction is overall non-tight, it matches the best existing bound for wFS in the QROM (Pan, Wagner, and Zeng, ASIACRYPT 2023), namely, it is square-root- and session-tight. Our analysis is in the multi-challenge setting, and it is more realistic than the single-challenge setting as in Pan et al..



## 2025/201

* Title: Cryptanalysis of Isogeny-Based Quantum Money with Rational Points
* Authors: Hyeonhak Kim, DongHoe Heo, Seokhie Hong
* [Permalink](https://eprint.iacr.org/2025/201)
* [Download](https://eprint.iacr.org/2025/201.pdf)

### Abstract

Quantum money is the cryptographic application of the quantum no-cloning theorem. It has recently been instantiated by Montgomery and Sharif (Asiacrypt '24) from class group actions on elliptic curves. In this work, we propose a concrete cryptanalysis by leveraging the efficiency of evaluating division polynomials with the coordinates of rational points, offering a speedup of $O(\log^4p)$ compared to the brute-force attack. Since our attack still requires exponential time, it remains impractical to forge a quantum banknote. Interestingly, due to the inherent properties of quantum money, our attack method also results in a more efficient verification procedure. Our algorithm leverages the properties of quadratic twists to utilize rational points in verifying the cardinality of the superposition of elliptic curves. We expect this approach to contribute to future research on elliptic-curve-based quantum cryptography.



## 2025/259

* Title: Improved Resultant Attack against Arithmetization-Oriented Primitives
* Authors: Augustin Bariant, Aurélien Boeuf, Pierre Briaud, Maël Hostettler, Morten Øygarden, Håvard Raddum
* [Permalink](https://eprint.iacr.org/2025/259)
* [Download](https://eprint.iacr.org/2025/259.pdf)

### Abstract

In the last decade, the introduction of advanced cryptographic protocols operating on large finite fields $\mathbb{F}_q$ has raised the need for efficient cryptographic primitives in this setting, commonly referred to as Arithmetization-Oriented (AO). The cryptanalysis of AO hash functions is essentially done through the study of the CICO problem on the underlying permutation. Two recent works at Crypto 2024 and Asiacrypt 2024 managed to solve the CICO problem much more efficiently than traditional Gröbner basis methods, using respectively advanced Gröbner basis techniques and resultants.

In this paper, we propose an attack framework based on resultants that applies to a wide range of AO permutations and improves significantly upon these two recent works. Our improvements mainly come from an efficient reduction procedure that we propose and rigorously analyze, taking advantage of fast multivariate multiplication. We present the most efficient attacks on Griffin, Arion, Anemoi, and Rescue. We show that most variants of Griffin, Arion and Anemoi fail to reach the claimed security level. For the first time, we successfully break a parameter set of Rescue, namely its $512$-bit security variant. The presented theory and complexity estimates are backed up with experimental attacks. Notably, we practically find CICO solutions for $8$ out of $10$ rounds of Griffin, $11$ out of $20$ rounds of Anemoi,  $6$ out of $18$ rounds of Rescue, improving by respectively $1$, $3$ and $1$ rounds on the previous best practical attacks.



## 2025/616

* Title: State Machine Replication Among Strangers, Fast and Self-Sufficient
* Authors: Juan Garay, Aggelos Kiayias, Yu Shen
* [Permalink](https://eprint.iacr.org/2025/616)
* [Download](https://eprint.iacr.org/2025/616.pdf)

### Abstract

A set of unacquainted  parties, some of which may misbehave, communicate with each other over an unauthenticated and unreliable gossip network. They wish to jointly replicate a state machine $\Pi$ so that each one of them has fair access to its operation. Specifically, assuming parties' computational power is measured as queries to an oracle machine $H(\cdot)$, parties can issue symbols to the state machine in proportion to their queries to $H(\cdot)$ at a given fixed rate. Moreover, if such access to the state machine is provided continuously in expected constant time installments we qualify it as fast fairness.

A state machine replication (SMR) protocol in this permissionless setting is expected to offer consistency across parties and reliably process all symbols that honest parties wish to add to it in a timely manner despite  continuously fluctuating participation and in the presence of an adversary who commands less than half of the total queries to $H(\cdot)$ per unit of time.

A number of protocols strive to offer the above guarantee together with fast settlement  --- notably, the Bitcoin blockchain offers a protocol that settles against Byzantine adversaries in polylogarithmic rounds, while fairness only holds in a fail-stop adversarial model (due to the fact that Byzantine behavior can bias access to the state machine in the adversary's favor). In this work, we put forth the first Byzantine-resilient protocol solving SMR in this setting with both expected-constant-time settlement and fast fairness. Furthermore, our protocol is self-sufficient in the sense of performing its own time keeping while tolerating an adaptively fluctuating set of parties.



## 2025/889

* Title: At the Top of the Hypercube -- Better Size-Time Tradeoffs for Hash-Based Signatures
* Authors: Dmitry Khovratovich, Mikhail Kudinov, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2025/889)
* [Download](https://eprint.iacr.org/2025/889.pdf)

### Abstract

Hash-based signatures have been studied for decades and have recently gained renewed attention due to their post-quantum security. At the core of the most prominent hash-based signature schemes, XMSS and SPHINCS+, lies a one-time signature scheme based on hash chains due to Winternitz. In this scheme, messages are encoded into vectors of positions (i.e., vertices in a hypercube) in the hash chains, and the signature contains the respective chain elements. The encoding process is crucial for the efficiency and security of this construction. In particular, it determines a tradeoff between signature size and computational costs. Researchers have been trying to improve this size-time tradeoff curve for decades, but all improvements have been arguably marginal.

In this work, we revisit the encoding process with the goal of minimizing verification costs and signature sizes. As our first result, we present a novel lower bound for the verification cost given a fixed signature size. Our lower bound is the first to directly apply to general encodings including randomized, non-uniform, and non-injective ones.

Then, we present new encodings and prove their security. Inspired by our lower bound, these encodings follow a counterintuitive approach: we map messages non-uniformly into the top layers of a much bigger hypercube than needed but the encoding itself has (hard to find) collisions. With this, we get a 20 % to 40 % improvement in the verification cost of the signature while keeping the same security level and the same size.
Our constructions can be directly plugged into any signature scheme based on hash chains, which includes SPHINCS+ and XMSS.



## 2025/1019

* Title: Silent Splitter: Privacy for Payment Splitting via New Protocols for Distributed Point Functions
* Authors: Margaret Pierce, Saba Eskandarian
* [Permalink](https://eprint.iacr.org/2025/1019)
* [Download](https://eprint.iacr.org/2025/1019.pdf)

### Abstract

In a world where financial transactions are primarily performed or recorded online, protecting sensitive transaction details has become crucial. Roommates sharing housing costs or friends splitting travelling expenses may use applications such as Splitwise to easily track debts and minimize the number of individual repayments. However, these apps reveal potentially sensitive financial transaction activity to their operators. In this paper, we present Silent Splitter, a privacy-preserving payment splitting system which enables users to securely set up groups, perform transactions within those groups, and "settle up" without revealing group membership or any sensitive transaction details (such as the users involved or amount of money exchanged) to the system itself. Silent Splitter operates in the two server setting and uses Distributed Point Functions (DPFs) to securely record transactions. Of independent interest, we also present new protocols for proving knowledge of properties of DPFs as part of our system.



## 2025/1020

* Title: Separating Pseudorandom Codes from Local Oracles
* Authors: Nico Döttling, Anne Müller, Mahesh Sreekumar Rajasree
* [Permalink](https://eprint.iacr.org/2025/1020)
* [Download](https://eprint.iacr.org/2025/1020.pdf)

### Abstract

Pseudorandom codes (PRCs) are error-correcting codes with the distinguishing feature that their codewords are computationally indistinguishable from random strings. Introduced by Christ and Gunn (CRYPTO 2024), PRCs have found applications in areas such as AI watermarking, where both robustness and pseudorandomness are essential. All known constructions of PRCs rely on coding-theoretic hardness assumptions. In this work, we study how inherent the use of coding-theoretic hardness is in the construction of pseudorandom codes.

We show that there is no black-box construction of PRCs with binary alphabets capable of decoding from a constant fraction of Bernoulli noise from a class of oracles we call local oracles. The class of local oracles includes random oracles and trapdoor permutation oracles, and can be interpreted as a meaningful notion of oracles that are not resilient against noise. Our separation result is cast in the Impagliazzo-Rudich framework and crucially relies on the Bonami-Beckner hypercontractivity theorem on the Boolean hypercube.

As a complementary result, we show that PRCs with large alphabets that can tolerate high error rates can indeed be constructed in a black-box manner from one-way functions.



## 2025/1021

* Title: Black-Box Crypto is Useless for Pseudorandom Codes
* Authors: Sanjam Garg, Sam Gunn, Mingyuan Wang
* [Permalink](https://eprint.iacr.org/2025/1021)
* [Download](https://eprint.iacr.org/2025/1021.pdf)

### Abstract

A pseudorandom code is a keyed error-correction scheme with the property that any polynomial number of encodings appear random to any computationally bounded adversary. We show that the pseudorandomness of any code tolerating a constant rate of random errors cannot be based on black-box reductions to almost any generic cryptographic primitive: for instance, anything that can be built from random oracles, generic multilinear groups, and virtual black-box obfuscation. Our result is optimal, as Ghentiyala and Guruswami (2024) observed that pseudorandom codes tolerating any sub-constant rate of random errors exist using a black-box reduction from one-way functions.

The key technical ingredient in our proof is the hypercontractivity theorem for Boolean functions, which we use to prove our impossibility in the random oracle model. It turns out that this easily extends to an impossibility in the presence of "crypto oracles," a notion recently introduced---and shown to be capable of implementing all the primitives mentioned above---by Lin, Mook, and Wichs (EUROCRYPT 2025).



## 2025/1022

* Title: Burn Your Vote: Decentralized and Publicly Verifiable Anonymous Voting at Scale
* Authors: Stefan Dziembowski, Shahriar Ebrahimi, Haniyeh Habibi, Parisa Hassanizadeh, Pardis Toolabi
* [Permalink](https://eprint.iacr.org/2025/1022)
* [Download](https://eprint.iacr.org/2025/1022.pdf)

### Abstract

Secure and trustworthy electronic voting requires more than correctness and censorship resistance, it must also ensure voter privacy, vote confidentiality, and protection against coercion. Prior work attempt to address these challenges using heavyweight cryptographic primitives such as homomorphic encryption, time-lock puzzles, or multi-party computation. These approaches often involve complex computations, depend on trusted parties, and typically do not scale well. We propose a lightweight, fully on-chain anonymous voting protocol based on a novel application of the proof-of-burn (PoB) mechanism. Voters anonymously commit to their votes by burning tokens to pseudorandom addresses and later submit zero-knowledge proofs attesting to their valid participation. Our design achieves vote integrity, coercion resistance, and unlinkability without relying on encrypted ballots, trusted third parties, or centralized tallying. The tallying process is public and operates on plaintext votes that are authenticated yet unlinkable to voters. This enables flexible voting models—including token-weighted and quadratic voting—with minimal on-chain overhead. We formally analyze the protocol’s security guarantees and demonstrate support for a broad range of voting models. We implement the protocol as an open-source library fully compatible with the Ethereum Virtual Machine (EVM), and our experimental evaluation confirms its high scalability and improved efficiency compared to the state-of-the-art.



## 2025/1023

* Title: Universal Channel Rebalancing: Flexible Coin Shifting in Payment Channel Networks
* Authors: Stefan Dziembowski, Shahriar Ebrahimi, Omkar Gavhane, Susil Kumar Mohanty
* [Permalink](https://eprint.iacr.org/2025/1023)
* [Download](https://eprint.iacr.org/2025/1023.pdf)

### Abstract

Payment Channel Networks (PCNs) enhance blockchain scalability by enabling off-chain transactions. However, repeated unidirectional multi-hop payments often cause channel imbalance or depletion, limiting scalability and usability. Existing rebalancing protocols, such as Horcrux [NDSS’25] and Shaduf [NDSS’22], rely on on-chain operations, which hinders efficiency and broad applicability.
  We propose Universal Channel Rebalancing (UCRb), a blockchain-agnostic, fully off-chain framework that ensures correct behavior among untrusted participants without on-chain interaction.
  UCRb incorporates the following core innovations:
  (1) a fair and reliable incentive-compatible mechanism that encourages voluntary user participation in off-chain channel rebalancing, 
  (2) integration of Pedersen commitments to achieve atomic off-chain payments and rebalancing operations, while ensuring balance security, and 
  (3) zero-knowledge proofs to enable privacy-preserving channel initialization and coin shifting, ensuring that user identities and fund allocations remain hidden throughout the process.

  We evaluate UCRb using real-world Lightning Network dataset and compare its performance against state-of-the-art solutions including Horcrux, Shaduf, and Revive [CCS'17].
  UCRb exhibits a success ratio enhancement between 15% and 50%, while also reducing the required user deposits by 72%--92%. It maintains an almost negligible rate of channel depletion. Additionally, the long-term performance of UCRb is roughly 1.5 times that of its short-term performance, suggesting that continuous operation leads to improved efficiency. We implement a prototype for UCRb smart contracts and demonstrate its practicality through extensive evaluation. As \texttt{CoinShift} operations require no on-chain interaction, the protocol incurs minimal gas costs. For instance, opening and closing channels with 10 neighbors costs only 130K-160K gas—significantly lower than comparable solutions.



## 2025/1024

* Title: Towards Trustless Provenance: A Privacy-Preserving Framework for On-chain Media Verification
* Authors: Piotr Mikołajczyk, Parisa Hassanizadeh, Shahriar Ebrahimi
* [Permalink](https://eprint.iacr.org/2025/1024)
* [Download](https://eprint.iacr.org/2025/1024.pdf)

### Abstract

As generative models continue to evolve, verifying the authenticity, provenance, and integrity of digital media has become increasingly critical—particularly for domains like journalism, digital art, and scientific documentation.
In this work, we present a decentralized verifiable media ecosystem for managing, verifying, and transacting authentic digital media using zero-knowledge proofs (ZKPs).
Building on VIMz (Dziembowski et al., PETS'25), we extend the framework in three key directions. First, we generalize the model to support arbitrary image regions to achieve selective transformations support such as redaction and regional blurring—features commonly required in privacy-preserving applications. Second, we introduce performance optimizations that yield up to an 18% improvement in off-chain proof generation, and enhance the framework to support cost-efficient on-chain verification. Third, we design and implement a modular smart contract architecture to support a wide range of decentralized media applications.
As a flagship use case, we develop a decentralized media marketplace that enables permissionless licensing, ownership transfer, and verifiable attribution.. In this setting, users can share transformed media—such as cropped, blurred, or resized previews—alongside ZKPs that prove derivation from a signed original, eliminating the need to trust the seller.
Unlike prior fair exchange protocols, which rely on trusted descriptions or encrypted payload delivery, our system enables verifiable public previews and origin-bound proofs without revealing the full content. This approach unlocks new applications beyond marketplaces, including automated infringement dispute resolution and photography contests with verifiable criteria.



## 2025/1025

* Title: Secure Noise Sampling for Differentially Private Collaborative Learning
* Authors: Olive Franzese, Congyu Fang, Radhika Garg, Somesh Jha, Nicolas Papernot, Xiao Wang, Adam Dziedzic
* [Permalink](https://eprint.iacr.org/2025/1025)
* [Download](https://eprint.iacr.org/2025/1025.pdf)

### Abstract

Differentially private stochastic gradient descent (DP-SGD) trains machine learning (ML) models with formal privacy guarantees for the training set by adding random noise to gradient updates. In collaborative learning (CL), where multiple parties jointly train a model, noise addition occurs either (i) before or (ii) during secure gradient aggregation. The first option is deployed in distributed DP methods, which require greater amounts of total noise to achieve security, resulting in degraded model utility. The second approach preserves model utility but requires a secure multiparty computation (MPC) protocol.. Existing methods for MPC noise generation require tens to hundreds of seconds of runtime per noise sample because of the number of parties involved. This makes them impractical for collaborative learning, which often requires thousands or more samples of noise in each training step.

We present a novel protocol for MPC noise sampling tailored to the collaborative learning setting. It works by constructing an approximation of the distribution of interest which can be efficiently sampled by a series of table lookups. Our method achieves significant runtime improvements and requires much less communication compared to previous work, especially at higher numbers of parties. It is also highly flexible – while previous MPC sampling methods tend to be optimized for specific distributions, we prove that our method can generically sample
noise from statistically close approximations of arbitrary discrete distributions. This makes it compatible with a wide variety of DP mechanisms. Our experiments demonstrate the efficiency and utility of our method applied to a discrete Gaussian mechanism for differentially private collaborative learning. For 16 parties, we achieve a runtime of 0.06 seconds and 11.59 MB total communication per sample, a 230× runtime improvement and 3× less communication compared to the prior state-of-the-art for sampling from discrete Gaussian distribution in MPC.



## 2025/1026

* Title: Malicious Security in Collaborative zk-SNARKs: More than Meets the Eye
* Authors: Sanjam Garg, Aarushi Goel, Abhishek Jain, Bhaskar Roberts, Sruthi Sekar
* [Permalink](https://eprint.iacr.org/2025/1026)
* [Download](https://eprint.iacr.org/2025/1026.pdf)

### Abstract

Collaborative zk-SNARKs (Ozdemir and Boneh, USENIX’22) are a multiparty variant of zk-SNARKs where multiple, mutually distrustful provers, each holding a private input, jointly compute a zk-SNARK using their combined inputs.. A sequence of works has proposed efficient constructions of collaborative zk-SNARKs using a common template that involves designing secure multiparty computation (MPC) protocols to emulate a zk-SNARK prover without making non-black-box use of cryptography. To achieve security against malicious adversaries, these works adopt compilers from the MPC literature that transform semi-honest MPC into malicious-secure MPC.

In this work, we revisit this design template.
• Pitfalls: We demonstrate two pitfalls in the template, which can lead to a loss of input privacy. We first show that it is possible to compute collaborative proofs on invalid witnesses, which in turn can leak the inputs of honest provers. Next, we show that using state-of-the-art malicious security compilers as-is for proof computation is insecure, in general. Finally, we discuss mitigation strategies.
• Malicious Security Essentially for Free: As our main technical result, we show that in the honest-majority setting, one can forego malicious security checks performed by state-of-the-art malicious security compilers during collaborative proof generation of several widely used zk-SNARKs. In other words, we can avoid the overheads of malicious security compilers, enabling faster proof generation.

To the best of our knowledge, this is the first example of non-trivial computations where semi-honest MPC protocols achieve malicious security. The observations underlying our positive results are general and may have applications beyond collaborative zkSNARKs.



## 2025/1027

* Title: Parallel Repetition for Post-Quantum Arguments
* Authors: Andrew Huang, Yael Tauman Kalai
* [Permalink](https://eprint.iacr.org/2025/1027)
* [Download](https://eprint.iacr.org/2025/1027.pdf)

### Abstract

In this work, we show that parallel repetition of public-coin interactive arguments reduces the soundness error at an exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least $t$ of the executions are accepted (for some threshold $t$). Prior to this work, these results were known only when the cheating prover was assumed to be classical.

We also prove a similar result for three-message private-coin arguments.  Previously, Bostanci, Qian, Spooner, and Yuen (STOC 2024) proved such a parallel repetition result in the more general setting of quantum protocols, where the verifier and communication may be quantum. We consider only protocols where the verifier is classical, but obtain a simplified analysis, and for the more general setting of threshold verifiers.



## 2025/1028

* Title: Group Key Progression: Strong Security for Shared Persistent Data
* Authors: Matilda Backendal, David Balbás, Miro Haller
* [Permalink](https://eprint.iacr.org/2025/1028)
* [Download](https://eprint.iacr.org/2025/1028.pdf)

### Abstract

End-to-end encryption allows data to be outsourced and stored on an untrusted server, such as in the cloud, without compromising data privacy. In the setting when this data is shared between a group of users, members also all share access to the same static key material used for data encryption. When the group membership changes, access control is only enforced by the server: security breaches or compelled disclosure would allow even a removed member to decrypt the current shared data.

We propose to move away from static keys and instead use a group key progression (GKP) scheme, a novel primitive that enables a dynamic group of users to agree on a persistent sequence of keys while keeping a compact local state. GKP ensures that group members can only derive keys within a certain interval of the sequence, a notion that we call interval access control (IAC), and also provide post-compromise security. Our GKP construction, called Grappa, combines continuous group key agreement (CGKA, by Alwen et al., 2020) with a new abstraction called interval scheme. The latter is a symmetric-key primitive that can derive a sequence of keys from a compact state while preserving IAC. We explore different interval scheme constructions and simulate their storage and communication costs when used in group settings. The most efficient of them is a generalization of dual key regression (Shafagh et al., 2020), which we formalize and prove secure. Overall, our protocols offer a practical and robust solution to protect persistent data shared by a group.



## 2025/1029

* Title: Improved Key Recovery Attacks of Ascon
* Authors: Shuo Peng, Kai Hu, Jiahui He, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2025/1029)
* [Download](https://eprint.iacr.org/2025/1029.pdf)

### Abstract

Ascon, a family of algorithms that support hashing and Authenticated Encryption with Associated Data (AEAD), is the final winner of the NIST Lightweight Cryptography Project.
As a research hotspot, Ascon has received substantial third-party security evaluation. Among all the results of Ascon-128 (the primary recommendation of AEAD), the key recovery attack can only be achieved by reducing the initialization phase to 7 rounds or fewer, regardless of whether it violates the security claims made by the designers (i.e., misuse of the nonce or exceeding data limits $2^{64}$).
In this paper, we, from two aspects (misuse-free setting and misused setting), improve the key recovery attack on Ascon-128 using the cube attack method.
In one part, we present a faster method to recover the superpolies for a 64-dimensional cube in the output bits of the 7-round initialization, enabling us to recover the secret key with a time complexity of $2^{95.96}$ and a data complexity of $2^{64}$.
Our 7-round key recovery attack, based on the full key space, greatly improves the time complexity, making it the best result to date.
Additionally, we utilize several techniques to extend state recovery to key recovery, answering the open problem of transitioning from full state recovery in the encryption phase to key recovery for Ascon-128 (ToSc Vol 4, 2022). By combining encryption phase state recovery with initialization phase key recovery, we can achieve 8-round and 9-round initialization phase key recovery in the nonce misuse scenario, with time complexities of $2^{101}$ and $2^{123.92}$, respectively.
This represents an improvement of two rounds over previous results in the misused setting.
Our first key recovery attack is also applicable to Ascon-128a, achieving
 the same result. In cases where the full state, prior to the encryption phase, can be recovered in other Ascon AEAD modes, our second key recovery attack will also be useful. It is worth noting that this work does not threaten the security of the full 12 rounds Ascon, but we expect that our results provide new insights
into the security of Ascon.



## 2025/1030

* Title: Everlasting Anonymous Rate-Limited Tokens
* Authors: Rutchathon Chairattana-Apirom, Nico Döttling, Anna Lysyanskaya, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2025/1030)
* [Download](https://eprint.iacr.org/2025/1030.pdf)

### Abstract

Anonymous rate-limited tokens are a special type of credential that can be used to improve the efficiency of privacy-preserving authentication systems like Privacy Pass. In such a scheme, a user obtains a "token dispenser" by interacting with an issuer, and the dispenser allows the user to create up to a pre-determined number $k$ of unlinkable and publicly verifiable tokens. Unlinkable means that one should not be able to tell that two tokens originate from the same dispenser, but also they cannot be linked to the interaction that generated the dispenser. Furthermore, we can limit the rate at which these tokens are created by linking each token to a context (e.g., the service we are authenticating to), and imposing a limit $N \leq k$ such that seeing more than $N$ tokens for the same context will reveal the identity of the user.
Constructions of such tokens were first given by Camenisch, Hohenberger and Lysyanskaya (EUROCRYPT '05) and Camenisch, Hohenberger, Kohlweiss, Lysyanskaya, and Meyerovich (CCS '06).

In this work, we present the first construction of \emph{everlasting} anonymous rate-limited tokens, for which unlinkability holds against computationally unbounded adversaries, whereas other security properties (e.g., unforgeability) remain computational. Our construction relies on pairings. While several parameters in our construction unavoidably grow with $k$, the key challenge we resolve is ensuring that the complexity of dispensing a token is independent of the parameter $k$.

We are motivated here by the goal of providing solutions that are robust to potential future quantum attacks against the anonymity of previously stored tokens. A construction based on post-quantum secure assumptions (e.g., based on lattices) would be rather inefficient---instead, we take a pragmatic approach dispensing with post-quantum security for properties not related to privacy.



## 2025/1031

* Title: Quasidifferential Saves Infeasible Differential: Improved Weak-Key Key-Recovery Attacks on Round-Reduced GIFT
* Authors: Chengcheng Chang, Meiqin Wang, Wei Wang, Kai Hu
* [Permalink](https://eprint.iacr.org/2025/1031)
* [Download](https://eprint.iacr.org/2025/1031.pdf)

### Abstract

\gift, including \gift-64 and \gift-128, is a family of lightweight block ciphers with outstanding implementation performance and high security, which is a popular underlying primitive chosen by many AEADs such as \sundae.  Currently, differential cryptanalysis is the best key-recovery attack on both ciphers, but they have stuck at 21 and 27 rounds for \gift-64 and \gift-128, respectively. Recently, Beyne and Rijmen proposed the quasidifferential transition matrix for differential cryptanalysis at CRYPTO 2022 and showed that the fixed-key probability of a differential (characteristic) can be expressed as the sum of correlations of all quasidifferential trails corresponding to this differential (characteristic). As pointed out by Beyne and Rijmen in their paper, the quasidifferential methodology is useful in identifying weak-key differential attacks.
    In this paper, we apply Beyne and Rijmen's method to \gift. Some differential characteristics with small (average) probabilities can have much larger probabilities when weak-key conditions hold. Improved weak-key differential attacks on \gift-64 and \gift-128 are thus obtained. For \gift-64, the probability of a 13-round differential is improved from $2^{-62.06}$ to $2^{-57.82}$ with 4 bits of weak-key conditions, then an improved differential key-recovery attack on 21-round \gift-64 is obtained with $2^{117.42}/2^{64}$ time/data complexities; the probability of a 13-round multiple differential (containing 33 characteristics) is improved from $2^{-58.96}$ to $2^{-55.67}$ with 4 bits of weak-key conditions, then an improved multiple differential key-recovery attack on 21-round \gift-64 is obtained with $2^{123.27}/2^{64}$ time/data complexities. For \gift-128, the probability of a 20-round differential is improved from $2^{-121.83}$ to $2^{-114.77}$ with 6 bits of weak-key conditions; the probability of a 21-round multiple differential (containing 2 differentials) is improved from $2^{-128.38}$ to $2^{-122.77}$ with 4 bits of weak-key conditions. Improved (multiple) differential weak-key key-recovery attacks are obtained for 27 and 28 rounds of \gift-128 with $2^{115.77}$/$2^{115.77}$ and $2^{123.77}$/$2^{123.77}$ time/data complexities, respectively. As far as we know, this is the first time that a (weak-key)  key-recovery attack can reach 28 rounds of \gift-128.
    Additionally, as an independent interest, we perform the first differential attack on \sundae. The differential used in this attack is checked with quasidifferential trails, thus the probability is reliable. Our attack is nonce-respecting and has significantly better complexities than the currently best attack.



## 2025/1032

* Title: Constant-Round Asynchronous MPC with Optimal Resilience and Linear Communication
* Authors: Junru Li, Yifan Song
* [Permalink](https://eprint.iacr.org/2025/1032)
* [Download](https://eprint.iacr.org/2025/1032.pdf)

### Abstract

In this work, we consider secure multiparty computation (MPC) in the asynchronous network setting. MPC allows $n$ parties to compute a public function on their private inputs against an adversary corrupting at most $t$ of them. We consider both communication complexity and round complexity of asynchronous MPC (AMPC) with the optimal resilience $n=3t+1$.

    Without fully homomorphic encryptions, the best-known result in this setting is achieved by Coretti, Garay, Hirt, and Zikas (ASIACRYPT 2016), which requires $O(|C|n^3\kappa)$ bits of communication assuming one-way functions, where $\kappa$ is the security parameter. On the other hand, the best-known non-constant-round AMPC by Goyal, Liu, and Song (CRYPTO 2024) can achieve $O(|C|n)$ communication even in the information-theoretic setting. In this work, we give the first construction of a constant-round AMPC with $O(|C|n\kappa)$ bits of communication that achieves malicious security with abort assuming random oracles. We provide new techniques for adapting the MPC-in-the-head framework in the asynchronous network to compute a constant-size garbled circuit.



## 2025/1033

* Title: Trusted Hardware-Assisted Leaderless Byzantine Fault Tolerance Consensus
* Authors: Liangrong Zhao, Jérémie Decouchant, Joseph K. Liu, Qinghua Lu, Jiangshan Yu
* [Permalink](https://eprint.iacr.org/2025/1033)
* [Download](https://eprint.iacr.org/2025/1033.pdf)

### Abstract

Byzantine Fault Tolerance (BFT) Consensus protocols with trusted hardware assistance have been extensively explored for their improved resilience to tolerate more faulty processes. Nonetheless, the potential of trust hardware has been scarcely investigated in leaderless BFT protocols. RedBelly is assumed to be the first blockchain network whose consensus is based on a truly leaderless BFT algorithm. This paper proposes a trusted hardware-assisted leaderless BFT consensus protocol by offering a hybrid solution for the set BFT problem defined in the RedBelly blockchain. Drawing on previous studies, we present two crucial trusted services: the counter and the collector. Based on these two services, we introduce two primitives to formulate our leaderless BFT protocol: a hybrid verified broadcast (VRB) protocol and a hybrid binary agreement.. The hybrid VRB protocol enhances the hybrid reliable broadcast protocol by integrating a verification function. This addition ensures that a broadcast message is verified not only for authentication but also for the correctness of its content. Our hybrid BFT consensus is integrated with these broadcast protocols to deliver binary decisions on all proposals. We prove the correctness of the proposed hybrid protocol and demonstrate its enhanced performance in comparison to the prior trusted BFT protocol.



## 2025/1034

* Title: JANUS: Enhancing Asynchronous Common Subset with Trusted Hardware
* Authors: Liangrong Zhao, Hans Schmiedel, Qin Wang, Jiangshan Yu
* [Permalink](https://eprint.iacr.org/2025/1034)
* [Download](https://eprint.iacr.org/2025/1034.pdf)

### Abstract

Asynchronous common subset (ACS) has been extensively studied since the asynchronous Byzantine fault tolerance (BFT) framework was introduced by Ben-Or, Kemler, and Rabin (BKR).
The line of work (i.e., HoneyBadgerBFT, BEAT, EPIC) uses parallel reliable broadcast (RBC) and asynchronous binary agreement (ABA) instances to reach an agreement on a subset of proposed transactions.

In this paper, we further progress the BKR paradigm by presenting Janus, the first hybrid ACS protocol leveraging trusted hardware components.
Janus is the first ACS protocol that tolerates a minority of Byzantine processes and that has O(n^2) message complexity.
Supported by trusted hardware components, we introduce a provable broadcast primitive to replace RBC, and develop a resilient binary agreement protocol. Messages for concurrent instances of agreement are aggregated into vectors. Our experimental results demonstrate significant performance improvements over predominant ACS constructions with a 92%+ increase compared to HoneyBadgerBFT and a 47%+ increase compared to BEAT.
Additionally, we provide a comparison with open-source hybrid BFT protocols that operate under a partially synchronous network, highlighting the performance enhancement compared to previous hybrid protocols that also tolerate the Byzantine minority (e.g., MinBFT and Damysus, by 49%+).



## 2025/1035

* Title: Continuous Group-Key Agreement: Concurrent Updates without Pruning
* Authors: Benedikt Auerbach, Miguel Cueto Noval, Boran Erol, Krzysztof Pietrzak
* [Permalink](https://eprint.iacr.org/2025/1035)
* [Download](https://eprint.iacr.org/2025/1035.pdf)

### Abstract

Continuous Group Key Agreement (CGKA) is the primitive underlying secure group messaging.
It allows a large group of $N$ users to maintain a shared secret key that is frequently rotated by the group members in order to achieve forward secrecy and post compromise security.
The group messaging scheme Messaging Layer Security (MLS) standardized by the IETF makes use of a CGKA called TreeKEM which arranges the $N$ group members in a binary tree.
Here, each node is associated with a public-key,
each user is assigned one of the leaves,
and a user knows the corresponding secret keys from their leaf to the root.
To update the key material known to them, a user must just replace keys at $\log(N)$ nodes, which requires them to create and upload $\log(N)$ ciphertexts.. Such updates must be processed sequentially by all users, which for large groups is impractical.
To allow for concurrent updates, TreeKEM uses the ``propose and commit'' paradigm, where multiple users can concurrently propose to update (by just sampling a fresh leaf key), and a single user can then commit to all proposals at once.

Unfortunately, this process destroys the binary tree structure as the tree gets pruned and some nodes must be ``blanked'' at the cost of increasing the in-degree of others, which makes the commit operation, as well as, future commits more costly.
In the worst case, the update cost (in terms of uploaded ciphertexts) per user can grow from $\log(N)$ to $\Omega(N)$.

In this work we provide two main contributions.
First, we show that MLS' communication complexity is bad not only in the worst case but also if the proposers and committers are chosen at random:
even if there's just one update proposal for every commit the expected cost is already over $\sqrt{N}$, and it approaches $N$ as this ratio changes towards more proposals.

Our second contribution is a new variant of propose and commit for TreeKEM which for moderate amounts of update proposals per commit provably achieves an update cost of $\Theta(\log(N))$ assuming the proposers and committers are chosen at random.



## 2025/1036

* Title: A Critique on Average-Case Noise Analysis in RLWE-Based Homomorphic Encryption
* Authors: Mingyu Gao, Hongren Zheng
* [Permalink](https://eprint.iacr.org/2025/1036)
* [Download](https://eprint.iacr.org/2025/1036.pdf)

### Abstract

Homomorphic encryption schemes based on the Ring-Learning-with-Errors problem require accurate ciphertext noise analysis to ensure correctness and security. However, ring multiplications during homomorphic computations make the noise in the result ciphertexts difficult to characterize. Existing average-case noise analyses derive a bound on the noise by either assuming it follows a Gaussian distribution, or giving empirical formulae, with strong independence assumption and the Central Limit Theorem extensively applied. In this work, we question the validity of these methods, by showing that the noise exhibits a heavy-tailed distribution via exact calculation of its variance and kurtosis, for both independent and dependent noises. The heavy-tailedness suggests the failing probability of bounds derived from these methods may not be negligible, and we experimentally demonstrate several cases where the noise growth is underestimated.



## 2025/1037

* Title: Committed Vector Oblivious Linear Evaluation and Its Applications
* Authors: Yunqing Sun, Hanlin Liu, Kang Yang, Yu Yu, Xiao Wang, Chenkai Weng
* [Permalink](https://eprint.iacr.org/2025/1037)
* [Download](https://eprint.iacr.org/2025/1037.pdf)

### Abstract

We introduce the notion of committed vector oblivious linear evaluation (C-VOLE), which allows a party holding a pre-committed vector to generate VOLE correlations with multiple parties on the committed value. It is a unifying tool that can be found useful in zero-knowledge proofs (ZKPs) of committed values, actively secure multi-party computation, private set intersection (PSI), etc.

To achieve the best efficiency, we design a tailored commitment scheme and matching C-VOLE protocols, both based on the learning parity with noise assumption. In particular, exploiting the structures of the carefully designed LPN-based commitment minimizes the cost of ensuring consistency between the committed vector and VOLE correlation. As a result, we achieve a 28$\times$ improvement over the protocol proposed in prior work (Usenix 2021) that uses ZKP to prove the correct opening of the commitment. We also apply C-VOLE to design a PSI protocol that allows one server to run PSI repeatedly with multiple clients while ensuring that the same set is used across all executions. Compared with the state-of-the-art PSI (CCS 2024) with similar security requirements, our protocol reduces the communication overhead by a factor of 35$\times$.



## 2025/1038

* Title: Security of Operations on Random Numbers: A Review
* Authors: Tejas Sharma, Ashish Kundu
* [Permalink](https://eprint.iacr.org/2025/1038)
* [Download](https://eprint.iacr.org/2025/1038.pdf)

### Abstract

Random numbers are often used in cryptography algorithms,
protocols, and in several security and non-security applications. Such us-
ages often apply Arithmetic and Boolean operations on pseudorandom
numbers, such as addition, XOR, NOT, bit shifts, and other operations,
in order to achieve the desired amount of entropy and desired level of
security. In this paper, we have reviewed, studied, and analyzed the se-
curity properties of these operations on random numbers: do Arithmetic
and Boolean operations and other related operations on cryptograph-
ically secure pseudorandom numbers lead to cryptographically secure
pseudorandom numbers; do they lead to loss of preservation of entropy?



## 2025/1039

* Title: Unbounded Distributed Broadcast Encryption and Registered ABE from Succinct LWE
* Authors: Hoeteck Wee, David J. Wu
* [Permalink](https://eprint.iacr.org/2025/1039)
* [Download](https://eprint.iacr.org/2025/1039.pdf)

### Abstract

We construct distributed broadcast encryption and registered attribute-based encryption (ABE) that support an arbitrary polynomial of users from the succinct LWE assumption. Specifically, if we take $\lambda$ to be the security parameter and $N$ to be the number of users, we obtain the following:

* We obtain a distributed broadcast encryption scheme where the size of the public parameters, user public/secret keys, and ciphertexts are optimal (i.e., have size $\mathsf{poly}(\lambda, \log N)$). Security relies on the $\mathsf{poly}(\lambda, \log N)$-succinct LWE assumption. Previously, this was only known from indistinguishability obfuscation or witness encryption. All constructions that did not rely on these general tools could only support an a priori bounded number of users.

* We obtain a key-policy registered ABE scheme that supports arbitrary bounded-depth Boolean circuit policies from the $\mathsf{poly}(\lambda, d, \log N)$-succinct LWE assumption in the random oracle model, where $d$ is the depth of the circuit computing the policy. The public parameters, user public/secret keys, and ciphertexts have size $\mathsf{poly}(\lambda, d, \log N)$, which are optimal up to the $\mathsf{poly}(d)$ factor. This is the first registered ABE scheme with nearly-optimal parameters. All previous schemes (including constructions based on indistinguishability obfuscation, witness encryption, or evasive LWE) either have ciphertexts that scale with the policy size and attribute length, or can only support a bounded number of users (with long public parameters and public keys that scale with the number of users).



## 2025/1040

* Title: Weave: Efficient and Expressive Oblivious Analytics at Scale
* Authors: Mahdi Soleimani, Grace Jia, Anurag Khandelwal
* [Permalink](https://eprint.iacr.org/2025/1040)
* [Download](https://eprint.iacr.org/2025/1040.pdf)

### Abstract

Many distributed analytics applications that are offloaded to the cloud operate on sensitive data. Even when the computations for such analytics workloads are confined to trusted hardware enclaves and all stored data and network communications are encrypted, several studies have shown that they are still vulnerable to access pattern attacks. Prior efforts towards preventing access pattern leakage often incur network and compute overheads that are logarithmic in dataset size, while also limiting the functionality of supported analytics jobs.

We present Weave, an efficient, expressive, and secure analytics platform that scales to large datasets.  Weaveemploys a combination of noise injection and hardware memory isolation via enclave page caches to reduce the network and compute overheads for oblivious analytics to a constant factor. Weave also employs several optimizations and extensions that exploit dataset and workload-specific properties to ensure performance at scale without compromising on functionality. Our evaluations show that Weave reduces the end-to-end execution time for a wide range of analytics jobs on large real-world datasets by $4$--$10\times$ compared to prior state-of-the-art while providing strong obliviousness guarantees.



## 2025/1041

* Title: Rubato: Provably Post-Quantum Secure and Batched Asynchronous Randomness Beacon
* Authors: Linghe Yang, Jian Liu, Jingyi Cui, Guangquan Xu, Yude Bai, Wei Wang
* [Permalink](https://eprint.iacr.org/2025/1041)
* [Download](https://eprint.iacr.org/2025/1041.pdf)

### Abstract

Distributed Randomness Beacons (DRBs) provide secure, unbiased random numbers for decentralized systems. However, existing protocols face critical limitations. Most rely on cryptographic assumptions which are vulnerable to quantum attacks, risking long-term security in asynchronous networks where unbounded delays may allow attackers time to exploit these weaknesses. Many achieve low beacon generation rates, often below 100 beacons per minute in moderate-scale networks (e.g., Spurt IEEE S&P’22), hindering their use in applications requiring high-throughput randomness. Additionally, traditional Verifiable Secret Sharing (VSS)-based DRBs, using a share-consensus-reconstruct paradigm, are unsuitable for asynchronous networks due to circular dependencies between beacon generation and consensus. Given these limitations, we propose Rubato, the first provably post-quantum secure DRB for asynchronous environments, incorporating a lattice-based batched Asynchronous Verifiable Secret Sharing scheme (bAVSS-PQ). Rubato supports batching of $\mathcal{O}(\lambda^2)$ secrets with communication complexity $\mathcal{O}(\lambda n^3 \log n)$ and tolerates Byzantine faults in up to one-third of the nodes. Integrated with DAG-based consensus protocols like Bullshark or Tusk, its epoch-staggered architecture resolves circular dependencies, enabling efficient and secure randomness generation. Evaluations across 10 to 50 nodes show Rubato generates 5200 to 350 beacons per minute with per-beacon latencies of 11.60 to 96.37 milliseconds, achieving a consensus throughput of 186,088 transactions per second with a latency of 16.78 seconds at 30 nodes. Rubato offers robust post-quantum security and high performance for small-to-medium-scale decentralized systems.



## 2025/1042

* Title: Crowhammer: Full Key Recovery Attack on Falcon with a Single Rowhammer Bit Flip
* Authors: Calvin Abou Haidar, Quentin Payet, Mehdi Tibouchi
* [Permalink](https://eprint.iacr.org/2025/1042)
* [Download](https://eprint.iacr.org/2025/1042.pdf)

### Abstract

The Rowhammer attack is a fault-injection technique leveraging the density of RAM modules to trigger persistent hardware bit flips that can be used for probing or modifying protected data. In this paper, we show that Falcon, the hash-and-sign signature scheme over NTRU lattices selected by NIST for standardization, is vulnerable to an attack using Rowhammer.

Falcon's Gaussian sampler is the core component of its security, as it allows to provably decorrelate the short basis used for signing and the generated signatures. Other schemes, lacking this guarantee (such as NTRUSign, GGH or more recently Peregrine) were proven insecure. However, performing efficient and secure lattice Gaussian sampling has proved to be a difficult task, fraught with numerous potential vulnerabilities to be exploited. To avoid timing attacks, a common technique is to use distribution tables that are traversed to output a sample. The official Falcon implementation uses this technique, employing a hardcoded reverse cumulative distribution table (RCDT). Using Rowhammer, we target Falcon's RCDT to trigger a very small number of targeted bit flips, and prove that the resulting distribution is sufficiently skewed to perform a key recovery attack.

Namely, we show that a single targeted bit flip suffices to fully recover the signing key, given a few hundred million signatures, with more bit flips enabling key recovery with fewer signatures. Interestingly, the Nguyen–Regev parallelepiped learning attack that broke NTRUSign, GGH and Peregrine does not readily adapt to this setting unless the number of bit flips is very large. However, we show that combining it with principal component analysis (PCA) yields a practical attack.

This vulnerability can also be triggered with other types of persistent fault attacks on memory like optical faults. We suggest cheap countermeasures that largely mitigate it, including rejecting signatures that are unusually short.



## 2025/1043

* Title: Designing QC-MDPC Public Key Encryption Schemes with Niederreiter's Construction and a Bit Flipping Decoder with Bounded DFR
* Authors: Alessandro Annechini, Alessandro Barenghi, Gerardo Pelosi, Simone Perriello
* [Permalink](https://eprint.iacr.org/2025/1043)
* [Download](https://eprint.iacr.org/2025/1043.pdf)

### Abstract

Post-quantum public key encryption (PKE) schemes employing Quasi-cyclic (QC) sparse
parity-check matrix codes are enjoying significant success, thanks to their
good performance profile and reduction to believed-hard problems from coding
theory.
However, using QC sparse parity-check matrix codes (i.e., QC-MDPC/LDPC codes)
comes with a significant challenge: determining in closed-form their decoding
failure rate (DFR), as decoding failures are known to leak information on the
private key.
Furthermore, there is no formal proof that changing the (constant) rate of the
employed codes does not change the nature of the underlying hard problem, nor
of the hardness of decoding random QC codes is formally related to the
decoding hardness of random codes.
In this work, we address and solve these challenges, providing a novel
closed-form estimation of the decoding failure rate  for three-iteration bit
flipping decoders, and proving computational equivalences among the
aforementioned problems.
This allows us to design systematically a Niederreiter-style QC-MDPC PKE,
enjoying the flexibility granted by freely choosing the code rate, and the
significant improvements in tightness of our DFR bound.
We report a $2\times$ improvement in public key and ciphertext size
w.r.t. the previous best cryptosystem design with DFR closed-form bounds,
LEDAcrypt-KEM. Furthermore, we show that our PKE parameters yield $30$% smaller
public key size and $2.6\times$ smaller ciphertexts w.r.t. HQC,
which is the key encapsulation method employing a code based PKE, recently selected by the US NIST for standardization.



## 2025/1044

* Title: When Threshold Meets Anamorphic Signatures: What is Possible and What is Not!
* Authors: Hien Chu, Khue Do, Lucjan Hanzlik, Sri AravindaKrishnan Thyagarajan
* [Permalink](https://eprint.iacr.org/2025/1044)
* [Download](https://eprint.iacr.org/2025/1044.pdf)

### Abstract

Anamorphic signatures allow covert communication through signatures in environments where encryption is restricted. They enable trusted recipients with a double key to extract hidden messages while the signature remains indistinguishable from a fresh and regular one. However, the traditional notion of anamorphic signatures suffers from vulnerabilities, particularly when a single recipient or sender is compromised, exposing all hidden messages and providing undeniable proof that citizens are part of the anamorphic exchange.

To address these limitations, we explore a threshold-based approach to distribute trust among multiple recipients, preventing adversaries from decrypting anamorphic messages even if some recipients are compromised. Our first contribution is the formalization of the notion of \emph{threshold-recipient anamorphic signatures}, where decryption is possible only through collaboration among a subset of recipients.

We then explore a \emph{stronger model} where the dictator controls the key generation process through which it learns all secret keys and how citizens store cryptographic keys. A particular example of this model in the real world is a dictator providing citizens with electronic identity documents (eIDs) and blocking all other usage of cryptography. We demonstrate that anamorphic communication is still possible even in such a scenario. Our construction is secure against post-quantum adversaries and does not rely on any computational assumptions except the random oracle model.

Finally, we show an \emph{impossibility result} for encoding anamorphic messages with a threshold-sender model when using many existing threshold signature schemes and the adversary is part of the signing group. Our work outlines both the possibilities and limitations of extending anamorphic signatures with threshold cryptography, offering new insights into improving the security and privacy of individuals under authoritarian regimes.



## 2025/1045

* Title: Constrained Verifiable Random Functions Without Obfuscation and Friends
* Authors: Nicholas Brandt, Miguel Cueto Noval, Christoph U. Günther, Akin Ünal, Stella Wohnig
* [Permalink](https://eprint.iacr.org/2025/1045)
* [Download](https://eprint.iacr.org/2025/1045.pdf)

### Abstract

CVRFs are PRFs that unify the properties of verifiable and constrained PRFs. Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy in 2014, it has been an open problem to construct CVRFs without using heavy machinery such as multilinear maps, obfuscation or functional encryption.

We solve this problem by constructing a prefix-constrained verifiable PRF that does not rely on the aforementioned assumptions. Essentially, our construction is a verifiable version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group elements. These outputs can be verified using pairings since the underlying PRG is of degree 2.

We prove the selective security of our construction under the Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which we dub recursive Decisional Diffie-Hellman (recursive DDH).

We prove the soundness of recursive DDH in the generic group model assuming the hardness of the Multivariate Quadratic (MQ) problem and a new variant thereof, which we call MQ+.

Last, in terms of applications, we observe that our CVRF is also an exponent (C)VRF in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25) with various applications to threshold cryptography in mind. In addition to that, we give further applications for prefix-CVRFs in the blockchain setting, namely, stake-pooling and compressible randomness beacons.



## 2025/1046

* Title: A Quasi-polynomial Time Algorithm for the Extrapolated Dihedral Coset Problem over Power-of-Two Moduli
* Authors: Shi Bai, Hansraj Jangir, Elena Kirshanova, Tran Ngo, William Youmans
* [Permalink](https://eprint.iacr.org/2025/1046)
* [Download](https://eprint.iacr.org/2025/1046.pdf)

### Abstract

The Learning With Errors (LWE) problem, introduced by Regev  (STOC'05), is one of the fundamental problems in lattice-based cryptography, believed to be hard even for quantum adversaries. Regev (FOCS'02) showed that LWE reduces to the quantum Dihedral Coset Problem (DCP). Later, Brakerski, Kirshanova, Stehlé and Wen (PKC'18) showed that LWE reduces to a generalization known as the Extrapolated Dihedral Coset Problem (EDCP). We present a quasi-polynomial time quantum algorithm for the EDCP problems over power-of-two moduli using a quasi-polynomial number of samples, which also applies to the SLWE problem defined by Chen, Liu, and Zhandry (Eurocrypt'22). Our EDCP algorithm can be viewed as a provable variant to the "Simon-meets-Kuperberg" algorithm introduced by Bonnetain and Naya-Plasencia (Asiacrypt'18), adapted to the EDCP setting. We stress that our algorithm does not affect the security of LWE with standard parameters, as the reduction from standard LWE to EDCP limits the number of samples to be polynomial.



## 2025/1047

* Title: Orient Express: Using Frobenius to Express Oriented Isogenies
* Authors: Wouter Castryck, Riccardo Invernizzi, Gioella Lorenzon, Jonas Meers, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2025/1047)
* [Download](https://eprint.iacr.org/2025/1047.pdf)

### Abstract

In this paper we study supersingular elliptic curves primitively oriented by an imaginary quadratic order, where the orientation is determined by an endomorphism that factors through the Frobenius isogeny. In this way, we partly recycle one of the main features of CSIDH, namely the fact that the Frobenius orientation can be represented for free. This leads to the most efficient family of ideal-class group actions in a range where the discriminant is significantly larger than the field characteristic $p$. Moreover, if we orient with a non-maximal order $\mathcal{O} \subset \mathbb{Q}(\sqrt{-p})$ and we assume that it is feasible to compute the  ideal-class group of the maximal order, then also the ideal-class group of $\mathcal{O}$ is known and we recover the central feature of SCALLOP-like constructions.

We propose two variants of our scheme. In the first one, the orientation is by a suborder of the form $\mathbb{Z}[f\sqrt{-p}]$ for some $f$ coprime to $p$, so this is similar to SCALLOP. In the second one, inspired by the work of Chenu and Smith, the orientation is by an order of the form $\mathbb{Z}[\sqrt{-dp}]$ where $d$ is square-free and not a multiple of $p$. We give practical ways of generating parameters, together with a proof-of-concept SageMath implementation of both variants, which shows the effectiveness of our construction.



## 2025/1048

* Title: One-way multilinear functions of the second order with linear shifts
* Authors: Stanislav Semenov
* [Permalink](https://eprint.iacr.org/2025/1048)
* [Download](https://eprint.iacr.org/2025/1048.pdf)

### Abstract

We introduce and analyze a novel class of binary operations on finite-dimensional vector spaces over a field \( K \), defined by second-order multilinear expressions with linear shifts. These operations generate polynomials whose degree increases linearly with each iterated application, while the number of distinct monomials grows combinatorially. We demonstrate that, despite the non-associative and non-commutative nature in general, these operations exhibit power associativity and internal commutativity when iterated on a single vector. This allows for well-defined exponentiation \( a^n \). Crucially, the absence of a simple closed-form expression for \( a^n \) suggests a one-way property: computing \( a^n \) from \( a \) and \( n \) is straightforward, but recovering \( n \) from \( a^n \) (the Discrete Iteration Problem) appears computationally hard. We propose a Diffie–Hellman-like key exchange protocol utilizing these properties over finite fields, defining an Algebraic Diffie–Hellman Problem (ADHP). The proposed structures are of interest for cryptographic primitives, algebraic dynamics, and computational algebra.



## 2025/1049

* Title: XHMQV: Better Efficiency and Stronger Security for Signal’s Initial Handshake based on HMQV
* Authors: Rune Fiedler, Felix Günther, Jiaxin Pan, Runzhi Zeng
* [Permalink](https://eprint.iacr.org/2025/1049)
* [Download](https://eprint.iacr.org/2025/1049.pdf)

### Abstract

The Signal protocol is the most widely deployed end-to-end-encrypted messaging protocol. Its initial handshake protocol X3DH allows parties to asynchronously derive a shared session key without the need to be online simultaneously, while providing implicit authentication, forward secrecy, and a form of offline deniability. The X3DH protocol has been extensively studied in the cryptographic literature and is acclaimed for its strong "maximum-exposure" security guarantees, hedging against compromises of users' long-term keys and medium-term keys but also the ephemeral randomness used in the handshake. This maximum-exposure security is achieved by deriving keys from the concatenation of 3–4 Diffie–Hellman (DH) secrets, each combining two long-term, medium-term, or ephemeral DH shares.

Remarkably, X3DH's approach of concatenating plain DH combinations is sub-optimal, both in terms of maximum-exposure security and performance. Indeed, Krawczyk's well-known HMQV protocol (Crypto '05) is a high-performance, DH-based key exchange that provides strong security against long-term and ephemeral key compromise. One might hence wonder: why not base Signal's initial handshake on HMQV?

In this work, we study this question and show that a carefully adapted variant of HMQV, which we call XHMQV, indeed enables stronger security and efficiency while matching the constraints of Signal's initial handshake. Most notably, HMQV does not work as a drop-in replacement for X3DH, as the latter's asynchronicity requires the protocol to handle cases where one party runs out of ephemeral keys (pre-uploaded to the Signal server). Our XHMQV design hence augments HMQV with medium-term keys analogous to those used in X3DH. We prove that XHMQV provides security in all 3–4 compromise scenarios where X3DH does and additionally in 1–2 further scenarios, strengthening the handshake's maximum-exposure guarantees while using more efficient group operations. We further confirm that our XHMQV design achieves deniability guarantees comparable to X3DH. Our security model is the first to capture Signal's long-term key reuse between DH key exchange and signatures, which may be of independent interest.



## 2025/1050

* Title: Integral Resistance of Block Ciphers with Key Whitening by Modular Addition
* Authors: Christof Beierle, Phil Hebborn, Gregor Leander, Yevhen Perehuda
* [Permalink](https://eprint.iacr.org/2025/1050)
* [Download](https://eprint.iacr.org/2025/1050.pdf)

### Abstract

Integral attacks exploit structural weaknesses in symmetric cryptographic primitives by analyzing how subsets of inputs propagate to produce outputs with specific algebraic properties. For the case of (XOR) key-alternating block ciphers using (independent) round keys, at ASIACRYPT'21, Hebborn et al. established the first non-trivial lower bounds on the number of rounds required for ensuring integral resistance in a quite general sense. For the case of adding keys by modular addition, no security arguments are known so far. Here, we present a unified framework for analyzing the integral resistance of primitives using (word-wise) modular addition for key whitening, allowing us to not only fill the gap for security arguments, but also to overcome the heavy computational cost inherent in the case of XOR-whitening.



## 2025/1051

* Title: Synergy: A Lightweight Block Cipher with Variable Bit Rotation Feistel Network
* Authors: Anders Lindman
* [Permalink](https://eprint.iacr.org/2025/1051)
* [Download](https://eprint.iacr.org/2025/1051.pdf)

### Abstract

Synergy is a lightweight block cipher designed for resource-constrained environments such as IoT devices, embedded systems, and mobile applications. Built around a 16-round Feistel network, 8 independent pseudorandom number generators (PRNGs) ensure strong diffusion and confusion through the generation of per-block unique round keys. With a 1024-bit key and a 64-bit block size, Synergy mitigates vulnerabilities to ML-based cryptanalysis by using a large key size in combination with key- and data-dependent bit rotations, which reduce statistical biases and increase unpredictability. By utilizing 32-bit arithmetic for efficient processing, Synergy achieves high throughput, low latency, and low power consumption, providing performance and security for applications where both are critical.



## 2025/1052

* Title: How to Trace Viral Content in End-to-End Encrypted Messaging
* Authors: Pedro Branco, Matthew Green, Aditya Hegde, Abhishek Jain, Gabriel Kaptchuk
* [Permalink](https://eprint.iacr.org/2025/1052)
* [Download](https://eprint.iacr.org/2025/1052.pdf)

### Abstract

We study the problem of combating *viral* misinformation campaigns in end-to-end encrypted (E2EE) messaging systems such as WhatsApp. We propose a new notion of Hop Tracking Signatures (HTS) that allows for tracing originators of messages that have been propagated on long forwarding paths (i.e., gone viral), while preserving anonymity of everyone else. We define security for HTS against malicious servers.  

We present both negative and positive results for HTS: on the one hand, we show that HTS does not admit succinct constructions if tracing and anonymity thresholds differ by exactly one "hop". On the other hand, by allowing for a larger gap between tracing and anonymity thresholds, we can build succinct HTS schemes where the signature size does not grow with the forwarding path. Our positive result relies on streaming algorithms and strong cryptographic assumptions.

Prior works on tracing within E2EE messaging systems either do not achieve security against malicious servers or focus only on tracing originators of pre-defined banned content.



## 2025/1053

* Title: Breaking the 1/λ-Rate Barrier for Arithmetic Garbling
* Authors: Geoffroy Couteau, Carmit Hazay, Aditya Hegde, Naman Kumar
* [Permalink](https://eprint.iacr.org/2025/1053)
* [Download](https://eprint.iacr.org/2025/1053.pdf)

### Abstract

Garbled circuits, introduced in the seminal work of Yao (FOCS, 1986), have received considerable attention in the boolean setting due to their efficiency and application to round-efficient secure computation. In contrast, arithmetic garbling schemes have received much less scrutiny. The main efficiency measure of garbling schemes is their rate, defined as the bit size of each gate's output divided by the size of the (amortized) garbled gate. Despite recent progress, state-of-the-art garbling schemes for arithmetic circuits suffer from important limitations: all existing schemes are either restricted to $B$-bounded integer arithmetic circuits (a computational model where the arithmetic is performed over $\mathbb{Z}$ and correctness is only guaranteed if no intermediate computation exceeds the bound $B$) and achieve constant rate only for very large bounds $B = 2^{\Omega(\lambda^3)}$, or have a rate at most $O(1/\lambda)$ otherwise, where $\lambda$ denotes a security parameter. In this work, we improve this state of affairs in both settings.

 - As our main contribution, we introduce the first arithmetic garbling scheme over modular rings $\mathbb{Z}_B$ with rate $O(\log\lambda/\lambda)$, breaking for the first time the $1/\lambda$-rate barrier for modular arithmetic garbling. Our construction relies on the power-DDH assumption.

 - As a secondary contribution, we introduce a new arithmetic garbling scheme for $B$-bounded integer arithmetic that achieves a constant rate for bounds $B$ as low as $2^{O(\lambda)}$. Our construction relies on a new non-standard KDM-security assumption on Paillier encryption with small exponents.



## 2025/1054

* Title: Rewardable Naysayer Proofs
* Authors: Gennaro Avitabile, Luisa Siniscalchi, Ivan Visconti
* [Permalink](https://eprint.iacr.org/2025/1054)
* [Download](https://eprint.iacr.org/2025/1054.pdf)

### Abstract

Combining verifiable computation with optimistic approaches is a promising direction to scale blockchain applications.
The basic idea consists of saving computations by avoiding the verification of proofs unless there are complaints.

A key tool to design systems in the above direction has been recently proposed by Seres, Glaeser and Bonneau [FC'24] who formalized the concept of a Naysayer proof: an efficient to verify proof disproving a more demanding to verify original proof.

In this work, we discuss the need of rewarding naysayer provers, the risks deriving from front-running attacks, and the failures of generic approaches trying to defeat them.
Next, we introduce the concept of verifiable delayed naysayer proofs and show a construction leveraging proofs of sequential work, without relying on any additional infrastructure.



## 2025/1055

* Title: Single-server Stateful PIR with Verifiability and Balanced Efficiency
* Authors: Pranav Shriram Arunachalaramanan, Ling Ren
* [Permalink](https://eprint.iacr.org/2025/1055)
* [Download](https://eprint.iacr.org/2025/1055.pdf)

### Abstract

Recent stateful private information retrieval (PIR) schemes have significantly improved amortized computation and amortized communication while aiming to keep client storage minimal. However, all the schemes in the literature still suffer from a poor tradeoff between client storage and computation.
We present BALANCED-PIR, a stateful PIR scheme that effectively balances computation and client storage. For a database of a million entries, each of 8 bytes, our scheme requires 0.2 MB of client storage, 0.2 ms of amortized computation, and 11.14 KB of amortized communication. Compared with the state-of-the-art scheme using a similar storage setting, our scheme is almost 9x better in amortized computation and 40x better in offline computation.

Verifiable private information retrieval has been gaining more attention recently. However, all existing schemes require linear amortized computation and huge client storage. We present Verifiable BALANCED-PIR, a verifiable stateful PIR scheme with sublinear amortized computation and small client storage. In fact, our Verifiable BALANCED-PIR adds modest computation, communication, and storage costs on top of BALANCED-PIR. Compared with the state-of-the-art verifiable scheme, the client storage of our scheme is 100x smaller, the amortized computation is 15x less, and the amortized communication is 2.5x better.



## 2025/1056

* Title: Private Signaling Secure Against Actively Corrupted Servers
* Authors: Haotian Chu, Xiao Wang, Yanxue Jia
* [Permalink](https://eprint.iacr.org/2025/1056)
* [Download](https://eprint.iacr.org/2025/1056.pdf)

### Abstract

Private signaling allows servers to identify a recipient's messages on a public bulletin board without knowing the recipient's metadata. It is a central tool for systems like privacy-preserving blockchains and anonymous messaging. However, unless with TEE, current constructions all assume that the servers are only passively corrupted, which significantly limits their practical relevance. In this work, we present a TEE-free simulation-secure private signaling protocol assuming two non-colluding servers, either of which can be actively corrupted.
 
Crucially, we convert signal retrieval into a problem similar to private set intersection and use custom-built zero-knowledge proofs to ensure consistency with the public bulletin board. As a result, our protocol achieves lower server-to-server communication overhead and a much smaller digest compared to state-of-the-art semi-honest protocol. For example, for a board size of $2^{19}$ messages, the resulting digest size is only 33.57KB. Our protocol is also computationally efficient: retrieving private signals only takes about 2 minutes, using 16 threads and a LAN network.