[digest] 2025 Week 7

## In this issue

1. [2023/1536] Leaky McEliece: Secret Key Recovery From Highly ...
2. [2024/1572] Bounded Collusion-Resistant Registered Functional ...
3. [2024/1593] Stateful Communication with Malicious Parties
4. [2025/191] Adaptive Distributional Security: A Framework for ...
5. [2025/197] Cryptanalysis of a nonlinear filter-based stream cipher
6. [2025/202] Distributed Non-Interactive Zero-Knowledge Proofs
7. [2025/203] Ciphertext-Simulatable HE from BFV with Randomized ...
8. [2025/204] Simpler and Stronger Models for Deniable Authentication
9. [2025/205] Addressing Scalability Issues of Blockchains with ...
10. [2025/206] Revisiting the Differential-Linear Attacks on ...
11. [2025/207] Efficient Mixed Garbling from Homomorphic Secret ...
12. [2025/208] Reductions Between Code Equivalence Problems
13. [2025/209] NovaTEE: Private Clearing and Settlement on Trusted ...
14. [2025/210] Practical Keyword Private Information Retrieval ...
15. [2025/211] Prior-Based Label Differential Privacy via Secure ...
16. [2025/212] Constructing Quantum Implementations with the ...
17. [2025/213] An Innovative Lightweight Symmetric Encryption ...
18. [2025/214] Rejected Challenges Pose New Challenges: Key ...
19. [2025/215] A note on the genus of the HAWK lattice
20. [2025/216] Practical Circuit Privacy/Sanitization for TFHE
21. [2025/217] Assumption-Free Fuzzy PSI via Predicate Encryption
22. [2025/218] LSM Trees in Adversarial Environments
23. [2025/219] Slot a la carte: Centralization Issues in ...
24. [2025/220] The Quantum Decoherence Model: Everlasting ...
25. [2025/221] Uniformly Most Powerful Tests for Ad Hoc ...
26. [2025/222] A Robust Variant of ChaCha20-Poly1305
27. [2025/223] Building Hard Problems by Combining Easy Ones: ...
28. [2025/224] Lightweight Single-Server PIR with ...
29. [2025/225] “Check-Before-you-Solve”: Verifiable Time-lock Puzzles
30. [2025/226] Improved Subfield Curve Search For Specific Field ...
31. [2025/227] Two Is All It Takes: Asymptotic and Concrete ...
32. [2025/228] Network agnostic consensus in constant time
33. [2025/229] ETK: External-Operations TreeKEM and the Security ...
34. [2025/230] Privately Constrained PRFs from DCR: Puncturing and ...
35. [2025/231] NoIC: PAKE from KEM without Ideal Ciphers
36. [2025/232] Authenticated BitGC for Actively Secure Rate-One 2PC
37. [2025/233] Anamorphic Resistant Encryption: the Good, the Bad ...
38. [2025/234] Merkle Mountain Ranges are Optimal: On witness ...
39. [2025/235] Doubly Efficient Cryptography: Commitments, ...
40. [2025/236] Diamond iO: A Straightforward Construction of ...
41. [2025/237] UC-Security of Encrypted Key Exchange: A Tutorial
42. [2025/238] On the Power of Polynomial Preprocessing: Proving ...
43. [2025/239] DART: Decentralized, Anonymous, and Regulation- ...
44. [2025/240] Robust Non-Interactive Zero-Knowledge Combiners
45. [2025/241] IBE-IBE: Intent-Based Execution through Identity- ...
46. [2025/242] Rational Secret Sharing with Competition
47. [2025/243] K-Linkable Ring Signatures and Applications in ...
48. [2025/244] Provable Speedups for SVP Approximation Under ...
49. [2025/245] Silent Circuit Relinearisation: Sublinear-Size ...
50. [2025/246] Towards Optimal Early Stopping Agreement Protocols
51. [2025/247] LatticeFold+: Faster, Simpler, Shorter Lattice- ...
52. [2025/248] New Exchanged Boomerang Distinguishers for 5-Round AES

## 2023/1536

* Title: Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information
* Authors: Marcus Brinkmann, Chitchanok Chuengsatiansup, Alexander May, Julian Nowakowski, Yuval Yarom
* [Permalink](https://eprint.iacr.org/2023/1536)
* [Download](https://eprint.iacr.org/2023/1536.pdf)

### Abstract

The McEliece cryptosystem is a strong contender for post-quantum schemes, including key encapsulation for confidentiality of key exchanges in network protocols.

A McEliece secret key is a structured parity check matrix that is transformed via Gaussian elimination into an unstructured public key. We show that this transformation is highly critical with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by McEliece implementations in the cryptographic libraries Classic McEliece and Botan.

We propose a novel decoding algorithm to reconstruct a secret key from its public key with information from a Gaussian transformation leak. Even if the obtained side-channel leakage is extremely noisy, i.e., each bit is flipped with probability as high as τ ≈ 0.4, we succeed to recover the secret key in a matter of minutes for all proposed (Classic) McEliece instantiations. Remarkably, for high-security McEliece parameters, our attack is more powerful in the sense that it can tolerate even larger τ.

We demonstrate our attack on the constant-time reference implementation of Classic McEliece in a single-trace setting, using an STM32L592 ARM processor.

Our result stresses the necessity of properly protecting highly structured code-based schemes such as McEliece against side-channel leakage.



## 2024/1572

* Title: Bounded Collusion-Resistant Registered Functional Encryption for Circuits
* Authors: Yijian Zhang, Jie Chen, Debiao He, Yuqing Zhang
* [Permalink](https://eprint.iacr.org/2024/1572)
* [Download](https://eprint.iacr.org/2024/1572.pdf)

### Abstract

As an emerging primitive, Registered Functional Encryption (RFE) eliminates the key-escrow issue that threatens numerous works for functional encryption, by replacing the trusted authority with a transparent key curator and allowing each user to sample their decryption keys locally. In this work, we present a new black-box approach to construct RFE for all polynomial-sized circuits. It considers adaptive simulation-based security in the bounded collusion model (Gorbunov et al. - CRYPTO'12), where the security can be ensured only if there are no more than Q >= 1 corrupted users and $Q$ is fixed at the setup phase. Unlike earlier works, we do not employ unpractical Indistinguishability Obfuscation (iO). Conversely, it can be extended to support unbounded users, which is previously only known from iO.

Technically, our general compiler exploits garbled circuits and a novel variant of slotted Registered Broadcast Encryption (RBE), namely global slotted RBE. This primitive is similar to slotted RBE, but needs optimally compact public parameters and ciphertext, so as to satisfy the efficiency requirement of the resulting RFE. Then we present two concrete global slotted RBE from pairings and lattices, respectively. With proposed compiler, we hence obtain two bounded collusion-resistant RFE schemes. Here, the first scheme relies on k-Lin assumption, while the second one supports unbounded users under LWE and evasive LWE assumptions.



## 2024/1593

* Title: Stateful Communication with Malicious Parties
* Authors: Chen-Da Liu-Zhang, Christopher Portmann, Guilherme Rito
* [Permalink](https://eprint.iacr.org/2024/1593)
* [Download](https://eprint.iacr.org/2024/1593.pdf)

### Abstract

Cryptography's most common use is secure communication---e.g. Alice can use encryption to hide the contents of the messages she sends to Bob (confidentiality) and can use signatures to assure Bob she sent these messages (authenticity). While one typically considers stateless security guarantees---for example a channel that Alice can use to send messages securely to Bob---one can also consider stateful ones---e.g. an interactive conversation between Alice, Bob and their friends where participation is dynamic: new parties can join the conversation and existing ones can leave. A natural application of such stateful guarantees are messengers.

We introduce a modular abstraction for stateful group communication, called Chat Sessions, which captures security guarantees that are achievable in fully asynchronous settings when one makes no party-honesty assumptions: anyone (including group members themselves) can be fully dishonest. Our abstraction is parameterized by (and enforces) a permissions policy that defines what operations parties have the right to perform in a given chat state. We show how to construct, use and extend Chat Sessions.

Our construction is fully decentralized (in particular, it need not a delivery service), does not incur additional interaction between chat participants (other than what is inherent from chat operations like sending a message) and liveness depends solely on messages being delivered.

A key feature of Chat Sessions is modularity: we extend Chat Sessions to capture authenticity, confidentiality, anonymity and off-the-record, and show our construction provides these guarantees if the underlying communication channels do too. We complement this by proving Maurer et al.'s Multi-Designated Receiver Public Key Encryption scheme (Eurocrypt '22) constructs matching communication channels (i.e. with all these guarantees).

We use Chat Sessions to construct UatChat: a simple and equally modular messaging application. Since UatChat preserves each of the guarantees mentioned above, this means we give the first fully Off-The-Record messaging application: parties can plausibly deny not only having sent any messages but even of being aware of a chat's existence.



## 2025/191

* Title: Adaptive Distributional Security: A Framework for Input-Adaptive Cryptography
* Authors: Cruz Barnum, David Heath
* [Permalink](https://eprint.iacr.org/2025/191)
* [Download](https://eprint.iacr.org/2025/191.pdf)

### Abstract

It is often desirable to break cryptographic primitives into two components: an input-independent offline component, and a cheap online component used when inputs arrive. Security of such online/offline primitives must be proved in the input-adaptive setting: the adversary chooses its input adaptively, based on what it sees in the offline-phase. Proving security in the input-adaptive setting can be difficult, particularly when one wishes to achieve simulation security and avoid idealized objects like a random oracle (RO).

This work proposes a framework for reasoning about input-adaptive primitives: adaptive distributional security (ADS). Roughly, an ADS primitive provides security when it is used with inputs drawn from one of two distributions that are themselves hard to distinguish. ADS is useful as a framework for the following reasons:
    - An ADS definition can often circumvent impossibility results imposed on the corresponding simulation-based definition. This allows us to decrease the online-cost of primitives, albeit by using a weaker notion of security.
    - With care, one can typically upgrade an ADS-secure object into a simulation-secure object (by increasing cost in the online-phase).
    - ADS is robust, in the sense that (1) it enables a form of composition and (2) interesting ADS primitives are highly interconnected in terms of which objects imply which other objects.
    - Many useful ADS-secure objects are plausibly secure from straightforward symmetric-key cryptography.

We start by defining the notion of an ADS encryption (ADE) scheme.
A notion of input-adaptive encryption can be easily achieved from RO, and the ADE definition can be understood as capturing the concrete property provided by RO that is sufficient to achieve input-adaptivity. From there, we use ADE to achieve ADS variants of garbled circuits and oblivious transfer, to achieve simulation-secure garbled circuits, oblivious transfer, and two-party computation, and prove interconnectedness of these primitives. In sum, this results in a family of objects with extremely cheap online-cost.



## 2025/197

* Title: Cryptanalysis of a nonlinear filter-based stream cipher
* Authors: Tim Beyne, Michiel Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/197)
* [Download](https://eprint.iacr.org/2025/197.pdf)

### Abstract

It is shown that the stream cipher proposed by Carlet and Sarkar in ePrint report 2025/160 is insecure. More precisely, one bit of the key can be deduced from a few keystream bytes. This property extends to an efficient key-recovery attack. For example, for the proposal with 80 bit keys, a few kilobytes of keystream material are sufficient to recover half of the key.



## 2025/202

* Title: Distributed Non-Interactive Zero-Knowledge Proofs
* Authors: Alex B. Grilo, Ami Paz, Mor Perry
* [Permalink](https://eprint.iacr.org/2025/202)
* [Download](https://eprint.iacr.org/2025/202.pdf)

### Abstract

Distributed certification is a set of mechanisms that allows an all-knowing prover to convince the units of a communication network that the network's state has some desired property, such as being $3$-colorable or triangle-free. Classical mechanisms, such as proof labeling schemes (PLS), consist of a message from the prover to each unit, followed by on-e round of communication between each unit and its neighbors.
Later works consider extensions, called distributed interactive proofs, where the prover and the units can have multiple rounds of communication before the communication among the units. Recently, Bick, Kol, and Oshman (SODA '22) defined a zero-knowledge version of distributed interactive proofs, where the prover convinces the units of the network’s state without revealing any other information about the network’s state or structure.  In their work, they propose different variants of this model and show that many graph properties of interest can be certified with them.

In this work, we define and study distributed non-interactive zero-knowledge proofs (dNIZK); these can be seen as a non-interactive version of the aforementioned model, and also as a zero-knowledge version of PLS.  We prove the following:

- There exists a dNIZK protocol for $3$-coloring with  $O(\log n)$-bit messages from the prover and $O(\log n)$-size messages among neighbors. This disproves a conjecture from previous work asserting that the total number of bits from the prover should grow linearly with the number of edges. 

- There exists a family of dNIZK protocols for triangle-freeness, that presents a trade-off between the size of the messages from the prover and the size of the messages among neighbors. Interestingly, we also introduce a variant of this protocol where the message size depends only on the maximum degree of a node and not on the total number of nodes, improving upon the previous non-zero-knowledge protocol for this problem. 

-  There exists a dNIZK protocol for any graph property in NP in the random oracle models, which is secure against an arbitrary number of malicious parties. Previous work considered compilers from PLS to distributed zero-knowledge protocol, which results in protocols with parameters that are incomparable to ours.



## 2025/203

* Title: Ciphertext-Simulatable HE from BFV with Randomized Evaluation
* Authors: Intak Hwang, Seonhong Min, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2025/203)
* [Download](https://eprint.iacr.org/2025/203.pdf)

### Abstract

Homomorphic Encryption (HE) is a privacy-enhancing technology that enables computation over encrypted data without the need for decryption. A primary application of HE is in the construction of communication-efficient Two-Party Computation (2PC) protocols between a client and a server, serving as the key owner and the evaluator, respectively. However, the 2PC protocol built on an HE scheme is not necessarily secure, as the standard IND-CPA security of HE does not guarantee the privacy of the evaluation circuit.
Several enhanced security notions for HE, such as circuit privacy and sanitization, have been proposed to address this issue, but they require significant overhead in terms of parameter size or time complexity.

In this work, we introduce a novel security notion for HE, called ciphertext simulatability, which precisely captures the security requirements of HE in the construction of 2PC. Then, we provide a concrete construction of ciphertext-simulatable HE from the BFV scheme by modifying its evaluation algorithm. We provide theoretical analysis and demonstrate experimental results to ensure that our solution has insignificant overhead in terms of parameter size and error growth.
As a matter of independent interest, we demonstrate how our approach of designing ciphertext-simulatable BFV can be further extended to satisfy stronger security notions such as sanitization.



## 2025/204

* Title: Simpler and Stronger Models for Deniable Authentication
* Authors: Guilherme Rito, Christopher Portmann, Chen-Da Liu-Zhang
* [Permalink](https://eprint.iacr.org/2025/204)
* [Download](https://eprint.iacr.org/2025/204.pdf)

### Abstract

Deniable Authentication is a highly desirable guarantee for secure messaging: it allows Alice to authentically send a message $m$ to a designated receiver Bob in a *Plausibly Deniable* manner. Concretely, while Bob is guaranteed Alice sent $m$, he cannot convince a judge Judy that Alice really sent this message---even if he gives Judy his secret keys. This is because Judy knows Bob *can* make things up. This paper models the security of Multi-Designated Verifier Signatures (MDVS) and Multi-Designated Receiver Signed Public Key Encryption (MDRS-PKE)---two (related) types of schemes that provide such guarantees---in the Constructive Cryptography (CC) framework (Maurer and Renner, ICS '11).

The only work modeling dishonest parties' ability of "making things up" was by Maurer et al. (ASIACRYPT '21), who modeled the security of MDVS, also in CC.. Their security model has two fundamental limitations:
  1. deniability is not guaranteed when honest receivers read;
  2. it relies on the CC-specific concept of specifications. 

We solve both problems. Regarding the latter, our model is a standard simulator-based one. Furthermore, our composable treatment allowed to identify a new property, Forgery Invalidity, without which we do not know how to prove the deniability of neither MDVS nor MDRS-PKE when honest receivers read. Finally, we prove that Chakraborty et al.'s MDVS (EUROCRYPT '23) has this property, and that Maurer et al.'s MDRS-PKE (EUROCRYPT '22) preserves it from the underlying MDVS.



## 2025/205

* Title: Addressing Scalability Issues of Blockchains with Hypergraph Payment Networks
* Authors: Arad Kotzer, Bence Ladóczki, János Tapolcai, Ori Rottenstreich
* [Permalink](https://eprint.iacr.org/2025/205)
* [Download](https://eprint.iacr.org/2025/205.pdf)

### Abstract

Payment channels are auspicious candidates in layer-2 solutions to reduce the number of on-chain transactions on traditional blockchains and increase transaction throughput. To construct payment channels, peers lock funds on 2-of-2 multisig addresses and open channels between one another to transact via instant peer-to-peer transactions. Transactions between peers without a direct channel are made possible by routing the payment over a series of adjacent channels. In certain cases, this can lead to relatively low transaction success rates and high transaction fees. In this work, we introduce pliability to constructing payment channels and graft edges with more than two endpoints into the payment graph. We refer to these constructions as hyperedges. We present hyperedge-based topologies to form hypergraphs and compare them to Bitcoin's Lightning network and other state-of-the-art solutions. The results demonstrate that hyperedge-based implementations can both increase transaction success rate, in addition to decreasing the network cost by more than 50% compared to that of the Lightning Network.



## 2025/206

* Title: Revisiting the Differential-Linear Attacks on ChaCha from IEEE TIT and INDOCRYPT 2024 (Extended Abstract)
* Authors: Xinhai Wang, Lin Ding, Zhengting Li, Jiang Wan, Bin Hu
* [Permalink](https://eprint.iacr.org/2025/206)
* [Download](https://eprint.iacr.org/2025/206.pdf)

### Abstract

The ChaCha stream cipher has become one of the best known ARX-based ciphers because of its widely use in several systems, such as in TLS, SSH and so on. In this paper, we find some errors in the attacks on ChaCha256 from IEEE TIT and INDOCRYPT 2024, and then corrected cryptanalytic attacks on ChaCha256 are given. However, the corrected attacks have extremely large time and data complexities. The corrected results show that the technique proposed in IEEE TIT may not be able to obtain improved differential-linear attacks on ChaCha.



## 2025/207

* Title: Efficient Mixed Garbling from Homomorphic Secret Sharing and GGM-Tree
* Authors: Jian Guo, Wenjie Nan
* [Permalink](https://eprint.iacr.org/2025/207)
* [Download](https://eprint.iacr.org/2025/207.pdf)

### Abstract

We present new techniques for garbling mixed arithmetic and boolean circuits, utilizing the homomorphic secret sharing scheme introduced by Roy \& Singh (Crypto 2021), along with the half-tree protocol developed by Guo et al (Eurocrypt 2023). Compared to some two-party interactive protocols, our mixed garbling only requires several times $(<10)$ more communication cost.

We construct the bit decomposition/composition gadgets with communication cost $O((\lambda+\lambda_{\text{DCR}}/k)b)$ for integers in the range $(-2^{b-1}, 2^{b-1})$, requiring $O(2^k)$ computations for the GGM-tree. Our approach is compatible with constant-rate multiplication protocols, and the cost decreases as $k$ increases. Even for a small $k=8$, the concrete efficiency ranges from $6\lambda b$ ($b \geq 1000$ bits) to $9\lambda b$ ($b \sim 100$ bits) per decomposition/composition. In addition, we develop the efficient gadgets for mod $q$ and unsigned truncation based on bit decomposition and composition.

We construct efficient arithmetic gadgets over various domains. For bound integers, we improve the multiplication rate in the work of Meyer et al. (TCC 2024) from $\textstyle\frac{\zeta-2}{\zeta+1}$ to $\frac{\zeta-2}{\zeta}$. We propose new garbling schemes over other domains through bounded integers with our modular and truncation gadgets, which is more efficient than previous constructions. For $\mathbb{Z}_{2^b}$, additions and multiplication can be garbled with a communication cost comparable to our bit decomposition. For general finite field $\mathbb{F}_{p^n}$, particularly for large values of $p$ and $n$, we garble the addition and multiplication at the cost of $O((\lambda+\lambda_{\text{DCR}}/k)b)$, where $b = n\lceil \log p \rceil$. For applications to real numbers, we introduce an ``error-based'' truncation that makes the cost of multiplication dependent solely on the desired precision.



## 2025/208

* Title: Reductions Between Code Equivalence Problems
* Authors: Mahdi Cheraghchi, Nikhil Shagrithaya, Alexandra Veliche
* [Permalink](https://eprint.iacr.org/2025/208)
* [Download](https://eprint.iacr.org/2025/208.pdf)

### Abstract

In this paper we present two reductions between variants of the Code Equivalence problem. We give polynomial-time Karp reductions from Permutation Code Equivalence (PCE) to both Linear Code Equivalence (LCE) and Signed Permutation Code Equivalence (SPCE). Along with a Karp reduction from SPCE to the Lattice Isomorphism Problem (LIP) proved in a paper by Bennett and Win (2024), our second result implies a reduction from PCE to LIP.



## 2025/209

* Title: NovaTEE: Private Clearing and Settlement on Trusted Execution Hardware
* Authors: Ahmet Ramazan Ağırtaş, James Ball, Michael Belegris, Gustave Charles-Saigne
* [Permalink](https://eprint.iacr.org/2025/209)
* [Download](https://eprint.iacr.org/2025/209.pdf)

### Abstract

NovaTEE is a novel private multilateral settlement network designed to address critical inefficiencies in both traditional financial markets and cryptocurrency trading. The current clearing landscape suffers from fragmented capital allocation, restrictive prime brokerage relationships, and prolonged settlement timeframes in traditional finance, while cryptocurrency markets face challenges with over-collateralization, siloed lending pools, and security risks from centralized exchanges.

We introduce a settlement system that leverages Trusted Execution Environments (TEEs) and threshold cryptography to enable secure, private, and efficient settlement of obligations between multiple parties. The system utilizes a distributed key generation model and novel clearing mechanisms to optimize capital efficiency through multilateral netting, while maintaining strong privacy guarantees and regulatory compliance capabilities. By combining TEE-based security with advanced cryptographic protocols, including zero-knowledge proofs and sparse Merkle trees for data verification, our solution enables efficient cross-venue and cross-chain settlement while protecting sensitive trading information. This approach significantly reduces capital requirements for market participants, optimizes transaction costs, and provides institutional-grade clearing infrastructure without compromising on security or privacy. The system's architecture ensures that no single party has complete access to transaction details while maintaining auditability through a distributed backup network, offering a practical solution for institutional adoption of on-chain settlement.



## 2025/210

* Title: Practical Keyword Private Information Retrieval from Key-to-Index Mappings
* Authors: Meng Hao, Weiran Liu, Liqiang Peng, Cong Zhang, Pengfei Wu, Lei Zhang, Hongwei Li, Robert H. Deng
* [Permalink](https://eprint.iacr.org/2025/210)
* [Download](https://eprint.iacr.org/2025/210.pdf)

### Abstract

This paper introduces practical schemes for keyword Private Information Retrieval (keyword PIR), enabling private queries on public databases using keywords. Unlike standard index-based PIR, keyword PIR presents greater challenges, since the query's position within the database is unknown and the domain of keywords is vast. Our key insight is to construct an efficient and compact key-to-index mapping, thereby reducing the keyword PIR problem to standard PIR. To achieve this, we propose three constructions incorporating several new techniques. The high-level approach involves (1) encoding the server's key-value database into an indexable database with a key-to-index mapping and (2) invoking standard PIR on the encoded database to retrieve specific positions based on the mapping. We conduct comprehensive experiments, with results showing substantial improvements over the state-of-the-art keyword PIR, ChalametPIR (CCS'24), i.e., a $15\sim178 \times$ reduction in communication and $1.1 \sim 2.4 \times$ runtime improvement, depending on database size and entry length.. Our constructions are practical, executing keyword PIR in just 47 ms for a database containing 1 million 32-byte entries.



## 2025/211

* Title: Prior-Based Label Differential Privacy via Secure Two-Party Computation
* Authors: Amit Agarwal, Stanislav Peceny, Mariana Raykova, Phillipp Schoppmann, Karn Seth
* [Permalink](https://eprint.iacr.org/2025/211)
* [Download](https://eprint.iacr.org/2025/211.pdf)

### Abstract

Differential privacy (DP) is a fundamental technique used in machine learning (ML) training for protecting the privacy of sensitive individual user data. In the past few years, a new approach for combining prior-based Local Differential Privacy (LDP) mechanisms with a relaxed DP criterion, known as Label DP, has shown great promise in increasing the utility of the final trained model without compromising on the DP privacy budget. In this work, we identify a crucial privacy gap in the current implementations of these prior-based LDP mechanisms, namely the leakage of sensitive priors. We address the challenge of implementing such LDP mechanisms without leaking any information about the priors while preserving the efficiency and accuracy of the current insecure implementations. To that end, we design simple and efficient secure two-party computation (2PC) protocols for addressing this challenge, implement them, and perform end-to-end testing on standard datasets such as MNIST, CIFAR-10. Our empirical results indicate that the added security benefit essentially comes almost for free in the sense that the gap between the current insecure implementations and our proposed secure version, in terms of run-time overhead and accuracy degradation, is minimal. E.g., for CIFAR-10, with strong DP privacy parameter, the additional runtime due to 2PC is $\approx 3.9\%$ over WAN with $0.4\%$ decrease in accuracy over an insecure (non-2PC) approach.



## 2025/212

* Title: Constructing Quantum Implementations with the Minimal T-depth or Minimal Width and Their Applications
* Authors: Zhenyu Huang, Fuxin Zhang, Dongdai Lin
* [Permalink](https://eprint.iacr.org/2025/212)
* [Download](https://eprint.iacr.org/2025/212.pdf)

### Abstract

With the rapid development of quantum computers, optimizing the quantum implementations of symmetric-key ciphers, which constitute the primary components of the quantum oracles used in quantum attacks based on Grover and Simon's algorithms, has become an active topic in the cryptography community. In this field, a challenge is to construct quantum circuits that require the least amount of quantum resources. In this work, we aim to address the problem of constructing quantum circuits with the minimal T-depth or width (number of qubits) for nonlinear components, thereby enabling implementations of symmetric-key ciphers with the minimal T-depth or width. Specifically, we propose several general methods for obtaining quantum implementation of generic vectorial Boolean functions and multiplicative inversions in GF(2^n), achieving the minimal T-depth and low costs across other metrics. As an application, we present a highly compact T-depth-3 Clifford+T circuit for the AES S-box. Compared to the T-depth-3 circuits presented in previous works (ASIACRYPT 2022, IEEE TC 2024), our circuit has significant reductions in T-count, full depth and Clifford gate count. Compared to the state-of-the-art T-depth-4 circuits, our circuit not only achieves the minimal T-depth but also exhibits reduced full depth and closely comparable width. This leads to lower costs for the DW-cost and T-DW-cost. Additionally, we propose two methods for constructing minimal-width implementations of vectorial Boolean functions. As applications, for the first time, we present a 9-qubit Clifford+T circuit for the AES S-box, a 16-qubit Clifford+T circuit for a pair of AES S-boxes, and a 5-qubit Clifford+T circuit for the chi function of SHA3. These circuits can be used to derive quantum circuits that implement AES or SHA3 without ancilla qubits.



## 2025/213

* Title: An Innovative Lightweight Symmetric Encryption Algorithm Integrating NeoAlzette ARX S-box and XCR CSPRNG
* Authors: Jiang Yu
* [Permalink](https://eprint.iacr.org/2025/213)
* [Download](https://eprint.iacr.org/2025/213.pdf)

### Abstract

This paper introduces "Little OaldresPuzzle_Cryptic," a novel lightweight symmetric encryption algorithm.

At the core of this algorithm are two main cryptographic components: the NeoAlzette permutation S-box based on ARX (Addition-Rotation-XOR) primitives and the innovative pseudo-random number generator XorConstantRotation (XCR), used exclusively in the key expansion process. The NeoAlzette S-box, a non-linear function for 32-bit pairs, is meticulously designed for both encryption strength and operational efficiency, ensuring robust security in resource-constrained environments. During the encryption and decryption processes, a pseudo-randomly selected mixed linear diffusion function, distinct from XCR, is applied, enhancing the complexity and unpredictability of the encryption.

We comprehensively explore the various technical aspects of the Little OaldresPuzzle_Cryptic algorithm.

Its design aims to balance speed and security in the encryption process, particularly for high-speed data transmission scenarios. Recognizing that resource efficiency and execution speed are crucial for lightweight encryption algorithms, without compromising security, we conducted a series of statistical tests to validate the cryptographic security of our algorithm. These tests included assessments of resistance to linear and differential cryptanalysis, among other measures.

By combining the NeoAlzette S-box with sophisticated key expansion using XCR, and integrating the pseudo-randomly selected mixed linear diffusion function in its encryption and decryption processes, our algorithm significantly enhances its capability to withstand advanced cryptographic analysis techniques while maintaining lightweight and efficient operation. Our test results demonstrate that the Little OaldresPuzzle_Cryptic algorithm effectively supports the encryption and decryption needs of high-speed data, ensuring robust security and making it an ideal choice for various modern cryptographic application scenarios.

Keywords: Symmetric Encryption Algorithm, Lightweight Cryptography, ARX Primitives, PRNG, NeoAlzette S-boxes, XorConstantRotation, Diffusion and Confusion Layers, Cryptographic Security, Statistical Tests, Resource-Constrained Environments.



## 2025/214

* Title: Rejected Challenges Pose New Challenges: Key Recovery of CRYSTALS-Dilithium via Side-Channel Attacks
* Authors: Yuanyuan Zhou, Weijia Wang, Yiteng Sun, Yu Yu
* [Permalink](https://eprint.iacr.org/2025/214)
* [Download](https://eprint.iacr.org/2025/214.pdf)

### Abstract

Rejection sampling is a crucial security mechanism in lattice-based signature schemes that follow the Fiat-Shamir with aborts paradigm, such as ML-DSA/CRYSTALS-Dilithium. This technique transforms secret-dependent signature samples into ones that are statistically close to a secret-independent distribution (in the random oracle model). While many side-channel attacks have directly targeted sensitive data such as nonces, secret keys, and decomposed commitments, fewer studies have explored the potential leakage associated with rejection sampling. Notably, Karabulut~et~al. showed that leakage from rejected challenges can undermine, but not entirely break, the security of the Dilithium scheme.

Motivated by the above, we convert the problem of key recovery (from the leakage of rejection sampling) to an integer linear programming problem (ILP), where rejected responses of unique Hamming weights set upper/lower constraints of the product between the challenge and the private key. We formally study the worst-case complexity of the problem as well as empirically confirm the practicality of the rejected challenge attack. For all three security levels of Dilithium-2/3/5, our attack recovers the private key in seconds or minutes with a 100% Success Rate (SR).

Our attack leverages knowledge of the rejected challenge and response, and thus we propose methods to extract this information by exploiting side-channel leakage from  Number Theoretic Transform (NTT) operations. We demonstrate the practicality of this rejected challenge attack by using real side-channel leakage on a Dilithium-2 implementation running on an ARM Cortex-M4 microcontroller. To the best of our knowledge, it is the first efficient side-channel key recovery attack on ML-DSA/Dilithium that targets the rejection sampling procedure. Furthermore, we discuss some countermeasures to mitigate this security issue.



## 2025/215

* Title: A note on the genus of the HAWK lattice
* Authors: Daniël M. H. van Gent
* [Permalink](https://eprint.iacr.org/2025/215)
* [Download](https://eprint.iacr.org/2025/215.pdf)

### Abstract

The cryptographic scheme and NIST candidate HAWK makes use of a particular module lattice and relies for its security on the assumption that finding module lattice isomorphisms (module LIP) is hard. To support this assumption, we compute the mass of the HAWK lattice, which gives a lower bound on the number of isometry classes of module lattices which cannot be distinguished from the HAWK lattice by an easily computed invariant called the genus. This number turns out to be so large that an attack based on the genus alone seems infeasible.



## 2025/216

* Title: Practical Circuit Privacy/Sanitization for TFHE
* Authors: Intak Hwang, Seonhong Min, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2025/216)
* [Download](https://eprint.iacr.org/2025/216.pdf)

### Abstract

Fully homomorphic encryption (FHE) enables the computation of arbitrary circuits over encrypted data. A widespread application of FHE is a simple two-party computation (2PC) protocol, where the server evaluates a circuit over the client's encrypted data and its private inputs. However, while the security of FHE guarantees that the client's data is protected from the server, there is no inherent support for the privacy of the server's input and the circuit.

One effective solution to this problem is an additional algorithm for FHE called sanitization, introduced by Ducas and Stehlé (Eurocrypt 2016). Roughly speaking, a sanitization algorithm removes any meaningful information contained in the ciphertext, including previous evaluations of circuits. Following their definition, several constructions for sanitization have been proposed, particularly for TFHE. However, all of these methods were impractical, requiring several bootstrappings or an excessive amount of randomized evaluations.

In this work, we construct a novel sanitization algorithm for TFHE that overcomes these issues. Our method only adds two lightweight randomization steps to the original TFHE bootstrapping, without any modifications to the core algorithms. As a result, our algorithm achieves sanitization with a single bootstrapping and minimal randomization, bringing sanitization closer to practicality.

To empirically evaluate the efficiency of our method, we provide concrete benchmark results based on our proof-of-concept implementation. Our algorithm sanitizes a single TFHE ciphertext in 35.88 ms, which is only 3.4% (1.18 ms) slower than the original TFHE bootstrapping with the same parameters. When directly compared to previous works, our method achieves a speedup by a factor of 4.82 to 209.03.



## 2025/217

* Title: Assumption-Free Fuzzy PSI via Predicate Encryption
* Authors: Erik-Oliver Blass, Guevara Noubir
* [Permalink](https://eprint.iacr.org/2025/217)
* [Download](https://eprint.iacr.org/2025/217.pdf)

### Abstract

We present the first protocol for efficient Fuzzy Private Set Intersection (PSI) that achieves linear communication complexity, does not depend on restrictive assumptions on the distribution of party inputs, and abstains from inefficient fully homomorphic encryption. Specifically, our protocol enables two parties to compute all pairs of elements from their respective sets that are within a given Hamming distance, without constraints on how these sets are structured.

Our key insight is that securely computing the (threshold) Hamming distance between two inputs can be reduced to securely computing their inner product. Leveraging this reduction, we construct a Fuzzy PSI protocol using recent techniques for inner-product predicate encryption. To enable the use of predicate encryption in our setting, we establish that these predicate encryption schemes satisfy a weak notion of simulation security and demonstrate how their internal key derivation can be efficiently distributed without a trusted third party.

As a result, our Fuzzy PSI on top of predicate encryption features not only asymptotically optimal linear communication complexity but is also concretely practical.



## 2025/218

* Title: LSM Trees in Adversarial Environments
* Authors: Hayder Tirmazi
* [Permalink](https://eprint.iacr.org/2025/218)
* [Download](https://eprint.iacr.org/2025/218.pdf)

### Abstract

The Log Structured Merge (LSM) Tree is a popular choice for key-value stores that focus on optimized write throughput while maintaining performant, production-ready read latencies. To optimize read performance, LSM stores rely on a probabilistic data structure called the Bloom Filter (BF). In this paper, we focus on adversarial workloads that lead to a sharp degradation in read performance by impacting the accuracy of BFs used within the LSM store. Our evaluation shows up to $800\%$ increase in the read latency of lookups for popular LSM stores. We define adversarial models and security definitions for LSM stores. We implement adversary resilience into two popular LSM stores, LevelDB and RocksDB. We use our implementations to demonstrate how performance degradation under adversarial workloads can be mitigated.



## 2025/219

* Title: Slot a la carte: Centralization Issues in Ethereum's Proof-of-Stake Protocol
* Authors: János Tapolcai, Bence Ladóczki, Ábel Nagy
* [Permalink](https://eprint.iacr.org/2025/219)
* [Download](https://eprint.iacr.org/2025/219.pdf)

### Abstract

In this paper, we demonstrate that Ethereum's current proof-of-stake (PoS) consensus mechanism poses a significant threat to decentralisation. Our research focuses on the manipulability of distributed randomness beacons (DRBs) in leader selection. Specifically, we show that RANDAO - Ethereum's DRB - is seriously vulnerable to manipulations in its current form.  For example, if a lucrative slot is foreseen, there is a risk that staking entities may temporarily collude to control $33\%$ of the validators, enabling them to execute a series of RANDAO manipulation attacks that secure the target slot with a $99.5\%$ success rate. The effectiveness of our method stems from the fact that we work with a significantly richer model of the possible attacks compared to previous works. Our manipulative strategies work by missing blocks from the canonical chain - either by withholding blocks in the adversary's own slots or by forking out blocks proposed by others. We argue that while PoS can pave the path in the future for blockchains, Ethereum's current DRB implementation has to be replaced with a more secure mechanism.



## 2025/220

* Title: The Quantum Decoherence Model: Everlasting Composable Secure Computation and More
* Authors: Nico Döttling, Alexander Koch, Sven Maier, Jeremias Mechler, Anne Müller, Jörn Müller-Quade, Marcel Tieplet
* [Permalink](https://eprint.iacr.org/2025/220)
* [Download](https://eprint.iacr.org/2025/220.pdf)

### Abstract

Quantum cryptography allows to achieve security goals which are unobtainable using classical cryptography alone: it offers the promise of everlasting privacy. Thatis, an adversary trying to attack a protocol must succeed during the run of the protocol.
After the protocol has terminated, security holds unconditionally.
In this work, we initiate the study of a new model which we call the quantum decoherence model (QDM). In a nutshell, this model captures adversaries that are computationally bounded during the run of a protocol (and some time after), but become computationally unbounded long after the protocol terminates. Importantly, once the adversary becomes computationally unbounded, he can only remember a bounded number of qubits from before the computational bound was lifted.
We provide a variant of the Universal Composability framework which captures the new notion of quantum decoherence and augment it with quantum random oracles. As our main contribution, we construct a non-interactive commitment scheme achieving unconditional and statistical security against malicious senders and everlasting security against malicious receivers under our new security notion. Such commitments imply general secure multiparty computation with everlasting security.
Finally, we show that our core technique can be applied to a broader spectrum of problems. We show that it gives rise to everlasting public key encryption and OT in the QDM. Finally, we also consider the weaker notion of incompressible encryption in the setting of quantum decoherence, and show that post-quantum IND-CPA secure public
key encryption is sufficient to realize this notion without resorting to random oracles.
At the technical core of our constructions is a new, conceptually simple yet powerful reverse entropic uncertainty relation.



## 2025/221

* Title: Uniformly Most Powerful Tests for Ad Hoc Transactions in Monero
* Authors: Brandon Goodell, Rigo Salazar, Freeman Slaughter
* [Permalink](https://eprint.iacr.org/2025/221)
* [Download](https://eprint.iacr.org/2025/221.pdf)

### Abstract

We introduce a general, low-cost, low-power statistical test for transactions in transaction protocols with small anonymity set authentication (TPSASAs), such as Monero. The test classifies transactions as ad hoc (spontaneously constructed to spend a deterministically selected key) or self-churned (constructed from a probability distribution very close to that of the default wallet software, and with the same sender and receiver). The test is a uniformly most powerful (UMP) likelihood ratio tests (LRT) from the Neyman-Pearson Lemma, and makes no assumptions about user behavior. We extend these tests to expoit prior information about user behavior. We discuss test parameterization, as well as how anonymity set cardinality and user behavior impact test performance. We also describe a maximum-likelihood de-anonymization attack on Monero based on our test.



## 2025/222

* Title: A Robust Variant of ChaCha20-Poly1305
* Authors: Tim Beyne, Yu Long Chen, Michiel Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/222)
* [Download](https://eprint.iacr.org/2025/222.pdf)

### Abstract

The ChaCha20-Poly1305 AEAD scheme is widely used as an alternative for AES-GCM on platforms without AES hardware instructions. Although recent analysis by Degabriele et al. shows that ChaCha20-Poly1305 provides adequate security in the conventional multiuser model, the construction is totally broken when a single nonce is repeated – a real-word scenario that can occur due to faulty implementations or the desire to use random nonces.

We present a new nonce-misuse resistant and key-committing authenticated encryption scheme, called ChaCha20-Poly1305-PSIV, that is based on carefully combining the ChaCha20-Poly1305 building blocks into the NSIV paradigm proposed by Peyrin and Seurin (CRYPTO 2016) without performance loss. We analyze the security of the underlying mode PSIV in the multi-user faulty-nonce model assuming that the underlying permutation is ideal, and prove its key-committing security in the cmt-1 model. Rust and C implementations are provided, and benchmarks confirm that performance is comparable to the ChaCha20-Poly1305 implementation in libsodium.

In terms of security and efficiency (without hardware support), our proposal compares favorably to AES-GCM-SIV. Since we reuse the ChaCha20-Poly1305 building blocks, we expect ChaCha20-Poly1305-PSIV to benefit from existing analysis and to be easy to deploy in practice.



## 2025/223

* Title: Building Hard Problems by Combining Easy Ones: Revisited
* Authors: Yael Eisenberg, Christopher Havens, Alexis Korb, Amit Sahai
* [Permalink](https://eprint.iacr.org/2025/223)
* [Download](https://eprint.iacr.org/2025/223.pdf)

### Abstract

We establish the following theorem:
 
Let $\mathsf{O}_0, \mathsf{O}_1, \mathsf{R}$ be random functions from $\{0,1\}^n$ to $\{0,1\}^n$, $n \in \mathbb{N}$. For all polynomial-query-bounded distinguishers $\mathsf{D}$ making at most $q=\mathsf{poly}(n)$ queries to each oracle, there exists a poly-time oracle simulator $\mathsf{Sim}^{(\cdot)}$ and a constant $c>0$ such that the probability is negligible, that is
    $$\left|\Pr\left[{\mathsf{D}^{(\mathsf{O}_0+\mathsf{O}_1),(\mathsf{O}_0,\mathsf{O}_1,\mathsf{O}_0^{-1},\mathsf{O}_1^{-1})}(1^n)=1}\right]-\Pr\left[{\mathsf{D}^{\mathsf{R},\mathsf{Sim}^\mathsf{R}}(1^n)=1}\right]\right| = negl(n).$$



## 2025/224

* Title: Lightweight Single-Server PIR with $O_\lambda(n^{1/3})$ Communication
* Authors: Jian Liu, Kui Ren, Chun Chen
* [Permalink](https://eprint.iacr.org/2025/224)
* [Download](https://eprint.iacr.org/2025/224.pdf)

### Abstract

It is well-known that any single-server PIR scheme with sublinear communication necessitates public-key cryptography. Several recent studies, which we collectively refer to as lightweight PIR, demonstrate that this limitation can be circumvented to some extent. However, all such schemes require at least $O(n^{1/2})$ communication per-query, where $n$ is the size of the database. Indeed, the celebrated result provided by Ishai et al. (Crypto '24) implies that, with solely symmetric-key cryptography,  achieving per-query communication below  $O(n^{1/2})$  necessitates more than $O(n^{1/2})$ client storage. Whether this barrier can be overcome with limited use of public-key cryptography remains an open question. In this paper, we tackle this question by presenting the first lightweight single-server PIR scheme with $O_\lambda(n^{1/3})$ communication while allowing arbitrary (non-zero) client storage.



## 2025/225

* Title: “Check-Before-you-Solve”: Verifiable Time-lock Puzzles
* Authors: Jiajun Xin, Dimitrios Papadopoulos
* [Permalink](https://eprint.iacr.org/2025/225)
* [Download](https://eprint.iacr.org/2025/225.pdf)

### Abstract

Time-lock puzzles are cryptographic primitives that guarantee to the generator that the puzzle cannot be solved in less than $\mathcal{T}$ sequential computation steps. They have recently found numerous applications, e.g., in fair contract signing and seal-bid auctions. However, solvers have no a priori guarantee about the solution they will reveal, e.g., about its ``usefulness'' within a certain application scenario. In this work, we propose verifiable time-lock puzzles (VTLPs) that address this by having the generator publish a succinct proof that the solution satisfies certain properties (without revealing anything else about it). Hence solvers are now motivated to ``commit'' resources into solving the puzzle. We propose VTLPs that support proving arbitrary NP relations $\mathcal{R}$ about the puzzle solution.
At a technical level, to overcome the performance hurdles of the ``naive'' approach of simply solving the puzzle within a SNARK that also checks $\mathcal{R}$, our scheme combines the ``classic'' RSA time-lock puzzle of Rivest, Shamir, and Wagner, with novel building blocks for ``offloading'' expensive modular group exponentiations and multiplications from the SNARK circuit. We then propose a second VTLP specifically for checking RSA-based signatures and verifiable random functions (VRFs). Our second scheme does not rely on a SNARK and can have several applications, e.g., in the context of distributed randomness generation. Along the road, we propose new constant-size proofs for modular exponent relations over hidden-order groups that may be of independent interest. Finally, we experimentally evaluate the performance of our schemes and report the findings and comparisons with prior approaches.



## 2025/226

* Title: Improved Subfield Curve Search For Specific Field Characteristics
* Authors: Jesús-Javier Chi-Domínguez
* [Permalink](https://eprint.iacr.org/2025/226)
* [Download](https://eprint.iacr.org/2025/226.pdf)

### Abstract

Isogeny-based cryptography relies its security on the hardness of the supersingular isogeny problem: finding an isogeny between two supersingular curves defined over a quadratic field.

The Delfs-Galbraith algorithm is the most efficient procedure for solving the supersingular isogeny problem with a time complexity of $\tilde{\mathcal{O}}(p^{1/2})$ operations. The bottleneck of the Delfs-Galbraith algorithm is the so-called subfield curve search (i.e., finding an isogenous supersingular elliptic curve defined over the base field), which determines the time complexity.

Given that, for efficiency, most recent isogeny-based constructions propose using finite fields with field characteristics equal to $p = 2^a \cdot f - 1$ for some positive integers $a$ and $f$.
This work focuses on primes of that particular form, and it presents two new algorithms for finding subfield curves with a time complexity of $\mathcal{O}(p^{1/2})$ operations and a memory complexity polynomial in $\log_2{p}$. Such algorithms exploit the existence of large torsion-$2^a$ points and extend the subfield root detection algorithm of Santos, Costello, and Shi (Crypto 2022) to our case study. In addition, it is worth highlighting that these algorithms easily extend to primes of the form $p =2^a \cdot f + 1$ and $p = \ell^a \cdot f - 1$ with $\ell$ being a small integer.

This study also examines the usage of radical $3$-isogenies with the proposed extended subfield root detection algorithm. In this context, the results indicate that the radical $3$-isogeny approach is competitive compared with the state-of-the-art algorithms.



## 2025/227

* Title: Two Is All It Takes: Asymptotic and Concrete Improvements for Solving Code Equivalence
* Authors: Alessandro Budroni, Andre Esser, Ermes Franch, Andrea Natale
* [Permalink](https://eprint.iacr.org/2025/227)
* [Download](https://eprint.iacr.org/2025/227.pdf)

### Abstract

The Linear Code Equivalence ($\mathsf{LCE}$) problem asks, for two given linear codes $\mathcal{C}, \mathcal{C}'$, to find a monomial $\mathbf{Q}$ mapping $\mathcal{C}$ into $\mathcal{C}'$. Algorithms solving $\mathsf{LCE}$ crucially rely on a (heuristic) subroutine, which recovers the secret monomial from $\Omega(\log n)$ pairs of codewords $(\mathbf{v}_i, \mathbf{w}_i)\in \mathcal{C} \times \mathcal{C}'$ satisfying $\mathbf{w}_i = \mathbf{v}_i\mathbf{Q}$.. We greatly improve on this known bound by giving a constructive (heuristic) algorithm that recovers the secret monomial from any \emph{two} pairs of such codewords for any $q\geq 23$. We then show that this reduction in the number of required pairs enables the design of a more efficient algorithm for solving the $\mathsf{LCE}$ problem. Our asymptotic analysis shows that this algorithm outperforms previous approaches for a wide range of parameters, including all parameters proposed across the literature. Furthermore, our concrete analysis reveals significant bit security reductions for suggested parameters. Most notably, in the context of the LESS signature scheme, a second-round contender in the ongoing NIST standardization effort for post-quantum secure digital signatures, we obtain bit security reductions of up to 24 bits.



## 2025/228

* Title: Network agnostic consensus in constant time
* Authors: Simon Holmgaard Kamp, Julian Loss, Jesper Buus Nielsen
* [Permalink](https://eprint.iacr.org/2025/228)
* [Download](https://eprint.iacr.org/2025/228.pdf)

### Abstract

Network agnostic protocols (Blum, Katz, Loss TCC `19) are consensus or MPC protocols that strike a balance between purely synchronous and asynchronous protocols. Given thresholds $t_a,t_s$ that satisfy $t_a<n/3<t_s<n/2$ and $2t_s+t_a<n$, they have the unique property of remaining secure against an adversary that either (1) corrupts up to $t_s$ parties in a synchronous execution where all messages are delivered within a known bound $\Delta$ or (2) corrupts up to $t_a$ in an asynchronous execution where messages can be delayed arbitrarily. All existing network agnostic protocols follow a design pattern which first attempts to run a synchronous path, and then switches to an asynchronous path as a fallback option if the synchronous path times out after some time $T$ due to the network being asynchronous. Unfortunately, $T$ has to be set conservatively to account for the possibility that the synchronous path might take an unusually long time even when the network is synchronous. As a result, for various basic tasks including Byzantine Agreement or MPC, no existing network agnostic protocol is able to terminate for all honest parties within constant expected time in all possible executions.

In this work, we introduce a new paradigm to construct network agnostic consensus (and MPC) that, for the first time overcome this barrier. Using this new design pattern we first present simple protocols for reliable broadcast (RB) and binary agreement (BA)
that are responsive when no more than $t_a$ parties are corrupted and run in expected constant time regardless of the network conditions. We then extend our results to asynchronous common subset (ACS) and MPC. Notably, our approach reverses the order of the synchronous and asynchronous path by designing protocols that are first and foremost asynchronous and only fall back to the synchronous execution path when more than $t_a$ parties are corrupted.



## 2025/229

* Title: ETK: External-Operations TreeKEM and the Security of MLS in RFC 9420
* Authors: Cas Cremers, Esra Günsay, Vera Wesselkamp, Mang Zhao
* [Permalink](https://eprint.iacr.org/2025/229)
* [Download](https://eprint.iacr.org/2025/229.pdf)

### Abstract

The Messaging Layer Security protocol MLS is standardized in IETF’s RFC 9420 and allows a group of parties to securely establish and evolve group keys even if the servers are malicious. Its core mechanism is based on the TreeKEM protocol, but has gained many additional features and modifications during the development of the MLS standard. Over the last years, several partial security analyses have appeared of incomplete drafts of the protocol. One of the major additions to the TreeKEM design in MLS RFC 9420 (the final version of the standard) are the external operations, i.e., external commits and proposals, which interact deeply with the core TreeKEM protocol. These operations have not been considered in any previous security analysis, leaving their impact on the protocol’s overall security unclear.

In this work, we formalize ETK: External-Operations TreeKEM that includes external commits and proposals. We develop a corresponding ideal functionality $F_\mathit{ECGKA}$ and prove that ETK indeed realizes $F_\mathit{ECGKA}$.

Our work is the first cryptographic analysis that considers both the final changes to the standard’s version of TreeKEM as well as external proposals and external commits. Compared to previous works that considered MLS draft versions, our ETK protocol is by far the closest to the final MLS RFC 9420 standard. Our analysis implies that the core of MLS’s TreeKEM variant as defined in RFC 9420 is an ETK protocol that realizes $F_\mathit{ECGKA}$, when used with an SUF-CMA secure signature scheme, such as the IETF variant of Ed25519. We show that contrary to previous claims, MLS does not realize $F_\mathit{ECGKA}$ [Crypto2022] when used with signature schemes that only guarantee EUF-CMA, such as ECDSA.

Moreover, we show that the security of the protocol could be further strengthened by adding a functionality to insert PSKs, allowing another form of healing, and give a corresponding construction ETK-PSK and ideal functionality $F_{\mathit{ECGKA}^\mathit{PSK}}$ .



## 2025/230

* Title: Privately Constrained PRFs from DCR: Puncturing and Bounded Waring Rank
* Authors: Amik Raj Behera, Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl
* [Permalink](https://eprint.iacr.org/2025/230)
* [Download](https://eprint.iacr.org/2025/230.pdf)

### Abstract

A privately constrained pseudorandom function (pCPRF) is a PRF with the additional property that one can derive a constrained key that allows evaluating the PRF only on inputs satisfying a constraint predicate $C$, without revealing $C$ itself or leaking information about the PRF’s output on inputs that do not satisfy the constraint.

Existing privately constrained PRFs face significant limitations: either (1) they rely on assumptions known to imply fully-homomorphic encryption or indistinguishability obfuscation, (2) they support only highly restricted classes of constraints—for instance, no known group-based pCPRF even supports the simple class of puncturing constraints (where the constrained key permits evaluation on all but one point while hiding the punctured point), or (3) they are limited to polynomial-size input domains. A long-standing open question has been whether one can construct a privately constrained PRF from group-based assumptions for more expressive classes of constraints. In this work, we present a pCPRF based on the decisional composite residuosity (DCR) assumption that supports a highly expressive class of predicates, namely constraints with polynomially bounded Waring rank, which notably includes puncturing.

From a technical perspective, our work follows the general template of Couteau, Meyer, Passelègue, and Riahinia (Eurocrypt'23), who constructed a pCPRF from group-based homomorphic secret-sharing but were limited to inner-product constraints in the constraint-hiding setting. Leveraging novel techniques for computing with distributed discrete logarithms (DDLog), we enable the non-interactive authentication of powers of linear combinations of shares of some value. This, in turn, allows us to express constraints with polynomially bounded Waring rank.

Our construction is single-key, selectively secure, and supports an exponential-size domain.



## 2025/231

* Title: NoIC: PAKE from KEM without Ideal Ciphers
* Authors: Afonso Arriaga, Manuel Barbosa, Stanislaw Jarecki
* [Permalink](https://eprint.iacr.org/2025/231)
* [Download](https://eprint.iacr.org/2025/231.pdf)

### Abstract

We show a generic compiler from KEM to (Universally Composable) PAKE in the Random Oracle Model (ROM) and without requiring an Ideal Cipher.  The compiler is akin to Encrypted Key Exchange (EKE) by Bellovin-Merritt, but following the work of McQuoid et al. it uses only a 2-round Feistel to password-encrypt a KEM public key. The resulting PAKE incurs only insignificant cost overhead over the underlying KEM, and it is a secure UC PAKE if KEM is secure and key-anonymous under the Plaintext-Checking Attack (PCA).

Several KEM-to-PAKE compilers were shown recently, secure under the OW-PCA and ANO-PCA assumptions on KEM, but all used an Ideal Cipher in addition to ROM..  While there are techniques for emulating ROM against quantum attackers, it is currently unknown how to extend many of such techniques to the Ideal Cipher Model.  Consequently, doing without the Ideal Cipher in protocol design makes the resulting construction a more plausible candidate for post-quantum secure PAKE if instantiated with post-quantum PCA-secure and anonymous KEM, such as the ML-KEM standard itself.

Our construction and proofs build on many of the ideas underlying the KEM-to-PAKE compiler using 2-round Feistel given by McQuoid et al, but our protocol is more efficient and our proofs address limitations in the analysis therein.



## 2025/232

* Title: Authenticated BitGC for Actively Secure Rate-One 2PC
* Authors: Hanlin Liu, Xiao Wang, Kang Yang, Yu Yu
* [Permalink](https://eprint.iacr.org/2025/232)
* [Download](https://eprint.iacr.org/2025/232.pdf)

### Abstract

In this paper, we present a constant-round actively secure two-party computation protocol with small communication based on the ring learning with errors (RLWE) assumption with key-dependent message security. Our result builds on the recent BitGC protocol by Liu, Wang, Yang, and Yu (Eurocrypt 2025) with communication of one bit per gate for semi-honest security. First, we achieve a different manner of distributed garbling, where the global correlation is secret-shared among the two parties. The garbler always and only holds the garbled labels corresponding to the wire values when all inputs are zero, while the evaluator holds the labels corresponding to the real evaluation.  In the second phase, we run an authentication protocol that requires some extra communication, which allows two parties to check the correct computation of each gate by treating the ciphertext as commitments, now that the global key is distributed. For layered circuits, the extra communication for authentication is $o(1)$ bits per gate, resulting in total communication of $1+o(1)$ bits per gate. For generic circuits, the extra communication cost can be $1$ bit per gate in the worst case, and thus, the total communication cost would be 2 bits per gate.



## 2025/233

* Title: Anamorphic Resistant Encryption: the Good, the Bad and the Ugly
* Authors: Davide Carnemolla, Dario Catalano, Emanuele Giunta, Francesco Migliaro
* [Permalink](https://eprint.iacr.org/2025/233)
* [Download](https://eprint.iacr.org/2025/233.pdf)

### Abstract

Anamorphic encryption (AE), introduced by Persiano, Phan and Yung at Eurocrypt 22, allows to establish secure communication in scenarios where users might be forced to hand over their decryption keys to some hostile authority. Over the last few years, several work have improved our understanding of the primitive by proposing novel realizations, new security notions and studying inherent limitations.
This work makes progress, mainly, on this last line of research.
We show concrete realizations of so-called Anamorphic Resistant Encryption (ARE, for short). These are (public key) encryption schemes that, provably, cannot be turned anamorphic.
We also show that, under certain conditions, anamorphic encryption turns out to be equivalent to algorithm substitution attacks. This result allows to positively reinterpret our AREs as PKE schemes provably resistant to subversion attacks. To the best of our knowledge, these seem to be the first IND-CPA secure schemes that achieve subversion resistance without trust assumptions or non-black-box decomposition techniques.
Our two AREs heavily rely, among other things, on a direct usage of extremely lossy functions: here the lossyness property is used in the constructions, rather than just in the proofs. The first construction is in the public parameters model and also requires iO. The second construction eliminates the need of both public parameters and iO, but is in the random oracle and relies on the novel concept of robust extremely lossy functions with group structure, a primitive that we define and (show how to) realize in this paper.



## 2025/234

* Title: Merkle Mountain Ranges are Optimal: On witness update frequency for cryptographic accumulators
* Authors: Joseph Bonneau, Jessica Chen, Miranda Christ, Ioanna Karantaidou
* [Permalink](https://eprint.iacr.org/2025/234)
* [Download](https://eprint.iacr.org/2025/234.pdf)

### Abstract

We study append-only set commitments with efficient updates and inclusion proofs, or cryptographic accumulators. In particular, we examine how often the inclusion proofs (or witnesses) for individual items must change as new items are added to the accumulated set. Using a compression argument, we show unconditionally that to accumulate a set of $n$ items, any construction with a succinct commitment ($O(\lambda \text{ polylog} \ n)$ storage) must induce at least $\omega(n)$ total witness updates as $n$ items are sequentially added. In a certain regime, we strengthen this bound to $\Omega(n \log n/\log \log n)$ total witness updates. These lower bounds hold not just in the worst case, but with overwhelming probability over a random choice of the accumulated set. Our results show that a close variant of the Merkle Mountain range, an elegant construction that has become popular in practice, is essentially optimal.



## 2025/235

* Title: Doubly Efficient Cryptography: Commitments, Arguments and RAM MPC
* Authors: Wei-Kai Lin, Ethan Mook, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2025/235)
* [Download](https://eprint.iacr.org/2025/235.pdf)

### Abstract

Can a sender commit to a long input without even reading all of it? Can a prover convince a verifier that an NP statement holds without  even reading the entire witness? Can a set of parties run a multiparty computation (MPC) protocol in the RAM model, without necessarily even reading their entire inputs? We show how to construct such "doubly efficient" schemes in a setting where parties can preprocess their input offline, but subsequently they can engage in many different protocol executions over this input in sublinear online time. We do so in the plain model, without any common setup. Our constructions rely on doubly efficient private information retrieval (DEPIR) as a building block and can be instantiated based on Ring LWE.

In more detail, we begin by constructing doubly efficient (interactive) commitments, where the sender preprocesses the input offline, and can later commit to this input to arbitrary  receivers in sublinear online time. Moreover, the sender  can open individual bits of the committed input in sublinear time.  We then use these commitments to implement doubly succinct (interactive) arguments, where the prover preprocesses the statement/witness offline, and can subsequently run many proof protocols to convince arbitrary verifiers of the statement's validity in sublinear online time. Furthermore, we augment these to get a doubly efficient "commit, prove and locally open" protocol, where the prover can commit to a long preprocessed input, prove that it satisfies some global property, and locally open individual bits, all in sublinear time. Finally, we leverage these tools to construct a RAM-MPC with malicious security in the plain model. Each party individually preprocesses its input offline, and can then run arbitrary MPC executions over this input with arbitrary other parties. The online run-time of each MPC execution is only proportional to the RAM run-time of the underlying program, that can be sublinear in the input size.



## 2025/236

* Title: Diamond iO: A Straightforward Construction of Indistinguishability Obfuscation from Lattices
* Authors: Sora Suegami, Enrico Bottazzi
* [Permalink](https://eprint.iacr.org/2025/236)
* [Download](https://eprint.iacr.org/2025/236.pdf)

### Abstract

Indistinguishability obfuscation (iO) has seen remarkable theoretical progress, yet it remains impractical due to its high complexity and inefficiency. A common bottleneck in recent iO schemes is the reliance on bootstrapping techniques from functional encryption (FE) into iO, which requires recursively invoking the FE encryption algorithm for each input bit—creating a significant barrier to practical iO schemes.

In this work, we propose diamond iO, a new lattice-based iO construction that replaces the costly recursive encryption process with lightweight matrix operations. Our construction is proven secure under the learning with errors (LWE) and evasive LWE assumptions, as well as our new assumption—all-product LWE—in the pseudorandom oracle model. By leveraging the FE scheme for pseudorandom functionalities introduced by Agrawal et al. (ePrint’24) in a non-black-box manner, we remove the reliance on prior FE-to-iO bootstrapping techniques and thereby significantly reduce complexity. A remaining challenge is to reduce our new assumption to standard assumptions such as LWE, further advancing the goal of a practical and sound iO construction.



## 2025/237

* Title: UC-Security of Encrypted Key Exchange: A Tutorial
* Authors: Jiayu Xu
* [Permalink](https://eprint.iacr.org/2025/237)
* [Download](https://eprint.iacr.org/2025/237.pdf)

### Abstract

Password-Authenticated Key Exchange (PAKE) is a type of key exchange protocols secure against man-in-the-middle adversaries, in the setting where the two parties only agree upon a low-entropy "password" in advance. The first and arguably most well-studied PAKE protocol is Encrypted Key Exchange (EKE) (Bellovin and Marritt, 1992), and the standard security notion for PAKE is in the Universal Composability (UC) framework (Canetti et al., 2005). While the UC-security of EKE has been "folklore" knowledge for many years, a satisfactory formal proof has long been elusive.

In this work, we present a UC-security proof for the most common instantiation of EKE, which is based on hashed Diffie–Hellman. Our proof is in the random oracle + ideal cipher models, and under the computational Diffie–Hellman assumption. We thoroughly discuss the UC-security definition for PAKE, subtleties and pitfalls in the security proof, how to write a UC proof, and flaws in existing works; along the way we also present some philosophical discussions on security definitions and security proofs in general. In this way, we hope to draw attention to several understudied, underexplained or underappreciated aspects of the UC-security of EKE.

This tutorial can be viewed as a simplified version of the recent work by Januzelli, Roy and Xu (2025); however, we completely rewrite most of the materials there to make them much more approachable to beginners who have just learned the UC framework.



## 2025/238

* Title: On the Power of Polynomial Preprocessing: Proving Computations in Sublinear Time, and More
* Authors: Matteo Campanelli, Mario Carrillo, Ignacio Cascudo, Dario Fiore, Danilo Francati, Rosario Gennaro
* [Permalink](https://eprint.iacr.org/2025/238)
* [Download](https://eprint.iacr.org/2025/238.pdf)

### Abstract

Cryptographic proof systems enable a verifier to be convinced of of a computation's correctness  without re-executing it; common efficiency requirements include both succinct proofs and fast verification.
In this work we put forth the general study of cryptographic proof systems with sublinear proving time (after a preprocessing).
Prior work has achieved sublinear proving only for limited computational settings (e.g., vector commitments and lookup arguments), relying on specific assumptions or through non-black-box use of cryptographic primitives. In  this work we lift many of these limitations through the systematic study of a specific object: polynomial commitments (PC) with sublinear proving time, a choice motivated by the crucial role that PC play in the design of efficient cryptographic schemes. 
Our main result is a simple construction of a PC with sublinear prover based on any vector commitment scheme (VC) and any preprocessing technique for fast polynomial evaluation. We prove that this PC satisfies evaluation binding, which is the standard security notion for PC, and show how to expand our construction to achieve the stronger notion of knowledge soundness (extractability).
The first application of our result is a construction of "index-efficient" SNARKs  meaning that the prover is  sublinear, after preprocessing, in the size of the index (i.e., the NP-relation describing the proven statement).  Our main technical contribution is a method to transform a class of standard Polynomial Interactive Oracle Proofs (PIOPs) into index-efficient PIOPs. Our construction of index-efficient SNARKs makes black-box use of such index-efficient PIOPs and a PC with sublinear prover.
As a corollary, this yields the first lookup argument for unstructured tables in which the prover is sublinear in the size of the table, while making only black-box use of a VC and thus allowing instantiations from generic assumptions such as collision-resistant hash functions. Prior lookup arguments with sublinear provers were only known with non-black-box use of cryptographic primitives, or from pairings. Finally, our last application is a transformation that builds UC-secure SNARKs from simulation-extractable ones, with an approximately linear overhead in proving time (as opposed to quadratic in prior work).



## 2025/239

* Title: DART: Decentralized, Anonymous, and Regulation-friendly Tokenization
* Authors: Amirreza Sarencheh, Hamidreza Khoshakhlagh, Alireza Kavousi, Aggelos Kiayias
* [Permalink](https://eprint.iacr.org/2025/239)
* [Download](https://eprint.iacr.org/2025/239.pdf)

### Abstract

We introduce DART, a fully anonymous, account-based payment system designed to address a comprehensive set of real-world considerations, including regulatory compliance, while achieving constant transaction size. DART supports multiple asset types, enabling users to issue on-chain assets such as tokenized real-world assets. It ensures confidentiality and anonymity by concealing asset types, transaction amounts, balances, and the identities of both senders and receivers, while guaranteeing unlinkability between transactions. Our design provides a mechanism for asset-specific auditing. Issuers can designate asset-specific auditors for the assets they issue, with the system preserving the privacy of the auditor’s identity to achieve asset type privacy. Only the designated auditor is authorized to decrypt transactions related to their associated asset, and users efficiently prove the association between the (hidden) asset type and the (hidden) designated auditor in their transactions.

DART supports non-interactive payments, allowing an online sender to submit a transaction even when the receiver is offline, while still incorporating a receiver affirmation mechanism that captures the real-world compliance consideration where the receiver must confirm (or deny) an incoming transaction. To the best of our knowledge, this is the first scheme of this kind in the permissionless setting. To accommodate all eventualities, DART also incorporates a reversibility mechanism, enabling senders to reclaim funds from pending transactions if the receiver’s affirmation is not yet provided. Finally, it offers a privacy-preserving proof of balance (per asset type) mechanism.

Our system achieves full anonymity while supporting concurrent incoming and outgoing transactions, resolving a common issue that plagues many account-based anonymous systems. We further demonstrate how our system supports multi-party transactions, allowing payment to multiple receivers in one transaction efficiently. We provide a full formal model in the Universal Composition (UC) setting, as well as a UC protocol realization.



## 2025/240

* Title: Robust Non-Interactive Zero-Knowledge Combiners
* Authors: Michele Ciampi, Lorenzo Magliocco, Daniele Venturi, Yu Xia
* [Permalink](https://eprint.iacr.org/2025/240)
* [Download](https://eprint.iacr.org/2025/240.pdf)

### Abstract

A $t$-out-of-$n$ robust non-interactive zero-knowledge (NIZK) combiner is a construction that, given access to $n$ candidate instantiations of a NIZK for some language, itself implements a NIZK for the same language. Moreover, the combiner is secure, assuming at least $t$ of the given candidates are secure.
In this work, we provide the first definition of combiners for NIZK, and prove that no robust NIZK combiner exists assuming $t \le \lfloor n/2 \rfloor$ (unless the polynomial hierarchy collapses).

On the positive side, we provide different constructions of robust NIZK combiners for  $t >  \lfloor n/2 \rfloor$. In particular, we show how to obtain:

1) A black-box combiner working for a special class of {\em homomorphic} languages where $n,t$ are polynomial and $t > \lfloor n/2 \rfloor$. 

2) A non-black-box combiner working for any language, where $n,t$ are constant and $t > \lfloor n/2 \rfloor$.

3)  A non-black-box combiner working for any language, where $n,t$ are polynomial and $t > \lfloor 2n/3 \rfloor$.



## 2025/241

* Title: IBE-IBE: Intent-Based Execution through Identity-Based Encryption and Auctions
* Authors: Peyman Momeni, Fig Smith
* [Permalink](https://eprint.iacr.org/2025/241)
* [Download](https://eprint.iacr.org/2025/241.pdf)

### Abstract

This paper introduces a decentralized and leaderless sealed bid auction model for dynamic pricing of intents across blockchain networks. We leverage Multi-Party Computation (MPC) and Identity-Based Encryption (IBE) to improve pricing while ensuring fairness and decentralization. By addressing the vulnerabilities of current centralized or static pricing mechanisms, our approach fosters transparent, secure, and competitive price discovery. We further enhance the confidentiality of intents through Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Trusted Execution Environments (TEE). Our novel methodology mitigates the risks of frontrunning and centralization while preserving the rapid settlement times essential to decentralized finance (DeFi).



## 2025/242

* Title: Rational Secret Sharing with Competition
* Authors: Tiantian Gong, Zeyu Liu
* [Permalink](https://eprint.iacr.org/2025/242)
* [Download](https://eprint.iacr.org/2025/242.pdf)

### Abstract

The rational secret sharing problem (RSS) considers incentivizing rational parties to share their received information to reconstruct a correctly shared secret. Halpern and Teague (STOC'04) demonstrate that solving the RSS problem deterministically with explicitly bounded runtime is impossible, if parties prefer learning the secret than not learning, and they prefer fewer other parties to learn.

To overcome this impossibility result, we propose RSS with competition. We consider a slightly different yet sensible preference profile: Each party prefers to learn the secret early and prefers fewer parties learning before them. This preference profile changes the information-hiding dynamics among parties in prior works: First, those who have learned the secret are indifferent towards or even prefer informing others later; second, the competition to learn the secret earlier among different access groups in the access structure facilitates information sharing inside an access group. As a result, we are able to construct the first deterministic RSS algorithm that terminates in at most two rounds. Additionally, our construction does not employ any cryptographic machinery (being fully game-theoretic and using the underlying secret-sharing scheme as a black-box) nor requires the knowledge of the parties' exact utility function. Furthermore, we consider general access structures.



## 2025/243

* Title: K-Linkable Ring Signatures and Applications in Generalized Voting
* Authors: Wonseok Choi, Xinagyu Liu, Lirong Xia, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2025/243)
* [Download](https://eprint.iacr.org/2025/243.pdf)

### Abstract

$\textit{Linkable ring signatures}$ (LRS) allow a user to sign anonymously on behalf of a ring, while maintaining linkability—two signatures from the same signer are publicly identified, i.e., linked. This linkability makes LRS suitable to prevent double-voting in classical, $\textit{plurality}$ voting protocols—each voter casts one vote and the candidate with the most votes wins the election.

    Several voting scenarios rely on (generalized) rules rather than plurality. For example, in $\textit{ranked voting}$, voters submit a ranking of the candidates, and the outcome is a function of these rankings. Such generalized voting rules are common in social choice theory, and have recently found their way into blockchain governance, e.g., for prioritizing (voting on) proposed (candidate)  projects. However, unlike plurality voting, using LRS for voters to sign their votes (rankings) does not guarantee vote privacy as one can observe the rankings of each individual voter, which, depending on the scoring rule, is more information than what the outcome of the election offers.

We introduce $k$-$\textit{linkable ring signatures}$ ($k$-LRS) as a primitive for simultaneously achieving anonymity and privacy in generalized voting. A $k$-LRS scheme has the following properties:
   ($k$-)$\textit{Anonymity}$: a user can sign anonymously (on behalf of the ring) up to $k$ times, so that even an unbounded adversary cannot link his signatures.
   ($k$-)$\textit{Linkability}$: If any signer signs more than $k$ times, all his signatures are publicly linked $\textit{(individual $k$-linkability)}$; and, any set of $c$ signers cannot generate more than $k\cdot c$ unlinked signatures $\textit{(collective $k$-linkability)}$.

    We provide two constructions of $k$-LRS: one is from the DDH, and the other is from SIS (hence post-quantum). Finally, we show how $k$-LRS can be applied to a broad range of voting rules, including $\textit{score voting}$, $\textit{multi-voting}$, and $\textit{Borda}$. Our protocols are non-interactive voting—each voter just posts a message on a bulletin board—which highlights the potential of $k$-LRS in blockchain-governance scenarios.



## 2025/244

* Title: Provable Speedups for SVP Approximation Under Random Local Blocks
* Authors: Jianwei Li
* [Permalink](https://eprint.iacr.org/2025/244)
* [Download](https://eprint.iacr.org/2025/244.pdf)

### Abstract

We point out if assuming every local block appearing in the slide reduction algorithms [ALNS20] is `random' (as usual in the cryptographic background), then the combination of the slide reduction algorithms [ALNS20] and  Pouly-Shen 's algorithm [PoSh24] yields exponentially faster provably correct algorithms for $\delta$-approximate SVP for all approximation factors $n^{1/2+\varepsilon} \leq \delta \leq n^{O(1)}$, which is the regime most relevant for cryptography.



## 2025/245

* Title: Silent Circuit Relinearisation: Sublinear-Size (Boolean and Arithmetic) Garbled Circuits from DCR
* Authors: Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl
* [Permalink](https://eprint.iacr.org/2025/245)
* [Download](https://eprint.iacr.org/2025/245.pdf)

### Abstract

We introduce a general template for building garbled circuits with low communication, under the decisional composite residuosity (DCR) assumption. For the case of layered Boolean circuits, we can garble a circuit of size $s$ with communication proportional to $O(s/\log\log s)$ bits, plus an additive factor that is polynomial in the security parameter. For layered arithmetic circuits with $B$-bounded integer computation, we obtain a similar result: the garbled arithmetic circuit has size $O(s/\log\log s) \cdot (\lambda + \log B)$ bits, where $\lambda$ is the security parameter. These are the first constructions of general-purpose, garbled circuits with sublinear size, without relying on heavy tools like indistinguishability obfuscation or attribute-based and fully homomorphic encryption.

To achieve these results, our main technical tool is a new construction of a form of homomorphic secret sharing where some of the inputs are semi-private, that is, known to one of the evaluating parties. Through a new relinearisation technique that allows performing arbitrary additions and multiplications on semi-private shares, we build such an HSS scheme that supports evaluating any function of the form $C(x) \cdot C'(y)$, where $C$ is any polynomially-sized circuit applied to the semi-private input $y$, and $C'$ is a restricted-multiplication (or, NC1) circuit applied to the private input $x$. This significantly broadens the expressiveness of prior known HSS constructions.



## 2025/246

* Title: Towards Optimal Early Stopping Agreement Protocols
* Authors: Fatima Elsheimy, Julian Loss, Charalampos Papamanthou
* [Permalink](https://eprint.iacr.org/2025/246)
* [Download](https://eprint.iacr.org/2025/246.pdf)

### Abstract

Early stopping agreement protocols guarantee termination based on the actual number of malicious parties, $f \leq t$, encountered during execution, rather than assuming the worst-case scenario of $t<n$ many corruptions. The lower bound on the round complexity for such protocols is known to be $\min\{f+2, t+1\}$ many rounds. In this work, we substantially improve the state of the art for cryptographic early stopping protocols in the honest majority setting where $t<n/2$. In this scenario, the best known protocol due to Elsheimy, Loss, and Papamanthou (ASIACRYPT `24) achieves a round complexity of $(1+\epsilon)\cdot f$ for some constant $0<\epsilon<1$. We begin by introducing an improvement to the Elsheimy et al. approach which can be used to obtain the first polynomial-time early stopping agreement protocols in the $t<n/2$ corruption regime which achieve a complexity of $f+O(\sqrt{f})$. We then instantiate our generic framework with refined components to obtain a very concretely efficient protocol with a round complexity of only $f + 6\lceil\sqrt{f}\rceil+6$ and polynomial communication complexity. Finally, we show that it is possible to come within one round of the optimal round complexity by presenting a broadcast protocol based on the exponential information gathering approach, which achieves a round complexity of $\min\{f + 3, t + 1\}$, albeit with exponential communication complexity.



## 2025/247

* Title: LatticeFold+: Faster, Simpler, Shorter Lattice-Based Folding for Succinct Proof Systems
* Authors: Dan Boneh, Binyi Chen
* [Permalink](https://eprint.iacr.org/2025/247)
* [Download](https://eprint.iacr.org/2025/247.pdf)

### Abstract

Folding is a technique for building efficient succinct proof systems. Many existing folding protocols rely on the discrete-log based Pedersen commitment scheme, and are therefore not post-quantum secure and require a large (256-bit) field. Recently, Boneh and Chen constructed LatticeFold, a folding protocol using lattice-based commitments which is plausibly post-quantum secure and can operate with small (64-bit) fields. For knowledge soundness, LatticeFold requires the prover to provide a range proof on all the input witnesses using bit-decomposition, and this slows down the prover. In this work we present LatticeFold+, a very different lattice-based folding protocol that improves on LatticeFold in every respect: the prover is five to ten times faster, the verification circuit is simpler, and the folding proofs are shorter. To do so we develop two novel lattice techniques. First, we develop a new purely algebraic range proof which is much more efficient than the one in LatticeFold, and may be of independent interest. We further shrink the proof using double commitments (commitments of commitments). Second, we show how to fold statements about double commitments using a new sumcheck-based transformation.



## 2025/248

* Title: New Exchanged Boomerang Distinguishers for 5-Round AES
* Authors: Hanbeom Shin, Seonkyu Kim, Dongjae Lee, Deukjo Hong, Jaechul Sung, Seokhie Hong
* [Permalink](https://eprint.iacr.org/2025/248)
* [Download](https://eprint.iacr.org/2025/248.pdf)

### Abstract

In block ciphers, the attacker should not be able to distinguish a block cipher from a random permutation, making the existence of a distinguisher important. Cryptanalysis of the reduced-round variants of block ciphers is also important in cryptographic design. AES is the most widely used block cipher, and currently, the best-known distinguisher for 5-round AES has a data and time complexity of $2^{29.95}$ with a success probability of 55\%. In this paper, we propose the fully active exchanged boomerang and multiple exchanged boomerang distinguishers for 5-round AES, based on the retracing boomerang key-recovery attack. The fully active exchanged boomerang distinguisher utilizes the probability that either each byte of the diagonal of the returned plaintext pair is fully active, or the diagonal is inactive for all diagonals. This probability is very high, but we enhance it using the friends pair technique to distinguish a block cipher from a random permutation. The multiple exchanged boomerang distinguisher utilizes the fact that there are three trails where the probability of one diagonal of the returned plaintext pair being inactive is higher than the random probability, and one trail where it is equal to the random probability. This 5-round distinguisher has a complexity of $2^{27.08}$ and a success probability of 82\%, which represents a new best-known result for the secret-key distinguisher on 5-round AES.