Newsportal USENET - [digest] 2025 Week 10

## In this issue

1. [2024/1589] A Systematic Study of Sparse LWE
2. [2025/196] Endomorphisms for Faster Cryptography on Elliptic ...
3. [2025/374] Simple and General Counterexamples for Private-Coin ...
4. [2025/385] MERCURY: A multilinear Polynomial Commitment Scheme ...
5. [2025/395] Provably Secure Approximate Computation Protocols ...
6. [2025/396] Trail-Estimator: An Automated Verifier for ...
7. [2025/397] Blind Signatures from Cryptographic Group Actions
8. [2025/398] Tight Adaptive Simulation Security for Identity- ...
9. [2025/399] Computational Quantum Anamorphic Encryption and ...
10. [2025/400] Re-Randomize and Extract: A Novel Commitment ...
11. [2025/401] PEGASIS: Practical Effective Class Group Action ...
12. [2025/402] Related-Key Differential and Boomerang ...
13. [2025/403] Periodic Table of Cryptanalysis: Geometric Approach ...
14. [2025/404] SNARKs for Stateful Computations on Authenticated Data
15. [2025/405] Withdrawable signatures in Fiat-Shamir with aborts ...
16. [2025/406] AsyRand: fast asynchronous distributed randomness ...
17. [2025/407] Delegatable ABE with Full Security from Witness ...
18. [2025/408] Hybrid Obfuscated Key Exchange and KEMs
19. [2025/409] Low Communication Threshold FHE from Standard ...
20. [2025/410] TreeKEM: A Modular Machine-Checked Symbolic ...
21. [2025/411] Security of the Ascon Authenticated Encryption Mode ...
22. [2025/412] Multi-Authority Functional Encryption: Corrupt ...
23. [2025/413] Garblet: Multi-party Computation for Protecting ...
24. [2025/414] Deimos Cipher: A High-Entropy, Secure Encryption ...
25. [2025/415] On the Soundness of Algebraic Attacks against Code- ...
26. [2025/416] Trapdoor Hash Functions and PIR from Low-Noise LPN
27. [2025/417] Evaluation of Privacy-aware Support Vector Machine ...
28. [2025/418] ProofFrog: A Tool For Verifying Game-Hopping Proofs
29. [2025/419] Samaritan: Linear-time Prover SNARK from New ...
30. [2025/420] Non-Interactive Verifiable Aggregation
31. [2025/421] A Note on Obfuscation-based Attacks on Private-coin ...
32. [2025/422] Private Computation on Common Fuzzy Records
33. [2025/423] Multi-Client Attribute-Based Unbounded Inner ...
34. [2025/424] Matchmaker: Fast Secure Inference across Deployment ...
35. [2025/425] A Note on the Blindness of the Scheme from ePrint ...
36. [2025/426] Exploring How to Authenticate Application Messages ...
37. [2025/427] BUFFing Threshold Signature Schemes
38. [2025/428] On Improved Cryptanalytic Results against ChaCha ...
39. [2025/429] Enhanced CKKS Bootstrapping with Generalized ...
40. [2025/430] Non-interactive Anonymous Tokens with Private ...
41. [2025/431] Commitment Schemes Based on Module-LIP
42. [2025/432] Black-Box (and Fast) Non-Malleable Zero Knowledge
43. [2025/433] MIDAS: an End-to-end CAD Framework for Automating ...
44. [2025/434] Fine-Grained Verifier NIZK and Its Applications
45. [2025/435] Constant-Time Code: The Pessimist Case
46. [2025/436] The Algebraic One-More MISIS Problem and ...
47. [2025/437] Improved Cryptanalysis of ChaCha: Beating PNBs with ...

## 2024/1589

* Title: A Systematic Study of Sparse LWE
* Authors: Aayush Jain, Huijia Lin, Sagnik Saha
* [Permalink](https://eprint.iacr.org/2024/1589)
* [Download](https://eprint.iacr.org/2024/1589.pdf)

### Abstract

In this work, we introduce the sparse LWE assumption, an assumption that draws inspiration from both Learning with Errors (Regev JACM 10) and Sparse Learning Parity with Noise (Alekhnovich FOCS 02). Exactly like LWE, this assumption posits indistinguishability of $(\mathbf{A}, \mathbf{s}\mathbf{A}+\mathbf{e} \mod p)$ from $(\mathbf{A}, \mathbf{u})$ for a random $\mathbf{u}$ where the secret $\mathbf{s}$, and the error vector $\mathbf{e}$ is generated exactly as in LWE. However, the coefficient matrix $\mathbf{A}$ in sparse LPN is chosen randomly from $\mathbb{Z}^{n\times m}_{p}$ so that each column has Hamming weight exactly $k$ for some small $k$. We study the problem in the regime where $k$ is a constant or polylogarithmic. The primary motivation for proposing this assumption is efficiency. Compared to LWE, the samples can be computed and stored with roughly $O(n/k)$ factor improvement in efficiency. Our results can be summarized as:

Foundations:
We show several properties of sparse LWE samples, including: 1) The hardness of LWE/LPN with dimension $k$ implies the hardness of sparse LWE/LPN with sparsity $k$ and arbitrary dimension $n \ge k$. 2) When the number of samples $m=\Omega(n \log p)$, length of the shortest vector of a lattice spanned by rows of a random sparse matrix is large, close to that of a random dense matrix of the same dimension (up to a small constant factor). 3) Trapdoors with small polynomial norm exist for random sparse matrices with dimension $n \times m = O(n \log p)$. 4) Efficient algorithms for sampling such matrices together with trapdoors exist when the dimension is $n \times m = \widetilde{\mathcal{O}}(n^2)$.

Cryptanalysis:
We examine the suite of algorithms that have been used to break LWE and sparse LPN. While naively many of the attacks that apply to LWE do not exploit sparsity, we consider natural extensions that make use of sparsity. We propose a model to capture all these attacks. Using this model we suggest heuristics on how to identify concrete parameters. Our initial cryptanalysis suggests that concretely sparse LWE with a modest $k$ and slightly bigger dimension than LWE will satisfy similar level of security as LWE with similar parameters.

Applications:
We show that the hardness of sparse LWE implies very efficient homomorphic encryption schemes for low degree computations. We obtain the first secret key Linearly Homomorphic Encryption (LHE) schemes with slightly super-constant, or even constant, overhead, which further has applications to private information retrieval, private set intersection, etc. We also obtain secret key homomorphic encryption for arbitrary constant-degree polynomials with slightly super-constant, or constant, overhead.

We stress that our results are preliminary. However, our results make a strong case for further investigation of sparse LWE.

## 2025/196

* Title: Endomorphisms for Faster Cryptography on Elliptic Curves of Moderate CM Discriminants, II
* Authors: Dimitri Koshelev, Antonio Sanso
* [Permalink](https://eprint.iacr.org/2025/196)
* [Download](https://eprint.iacr.org/2025/196.pdf)

### Abstract

The present article is a natural extension of the previous one about the GLV method of accelerating a (multi-)scalar multiplication on elliptic curves of moderate CM discriminants $D < 0$. In comparison with the first article, much greater magnitudes of $D$ (in absolute value) are achieved, although the base finite fields of the curves have to be pretty large. This becomes feasible by resorting to quite powerful algorithmic tools developed primarily in the context of lattice-based and isogeny-based cryptography. Curiously, pre-quantum cryptography borrows research outcomes obtained when seeking conversely quantum-resistant solutions or attacks on them.

For instance, some $2$-cycle of pairing-friendly MNT curves (with $-D \approx 100{,}000{,}000$, i.e., $\log_2(-D) \approx 26.5$) is relevant for the result of the current article. The given $2$-cycle was generated at one time by Guillevic to provide $\approx 128$ security bits, hence it was close to application in real-world zk-SNARKs. Another more performant MNT $2$-cycle (with slightly smaller security level, but with much larger $D$) was really employed in the protocol Coda (now Mina) until zero-knowledge proof systems on significantly faster pairing-free (or half-pairing) $2$-cycles were invented. It is also shown in the given work that more lollipop curves, recently proposed by Costello and Korpal to replace MNT ones, are now covered by the GLV technique.

## 2025/374

* Title: Simple and General Counterexamples for Private-Coin Evasive LWE
* Authors: Nico Döttling, Abhishek Jain, Giulio Malavolta, Surya Mathialagan, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2025/374)
* [Download](https://eprint.iacr.org/2025/374.pdf)

### Abstract

We present a simple counterexample to all known variants of the private-coin evasive learning with errors (LWE) assumption. Unlike prior works, our counterexample is direct, it does not use heavy cryptographic machinery (such as obfuscation or witness encryption), and it applies to all variants of the assumption. Our counterexample can be seen as a "zeroizing" attack against evasive LWE, calling into question the soundness of the underlying design philosophy.

## 2025/385

* Title: MERCURY: A multilinear Polynomial Commitment Scheme with constant proof size and no prover FFTs
* Authors: Liam Eagen, Ariel Gabizon
* [Permalink](https://eprint.iacr.org/2025/385)
* [Download](https://eprint.iacr.org/2025/385.pdf)

### Abstract

We construct a pairing-based polynomial commitment scheme for multilinear polynomials of size $n$ where
constructing an opening proof requires $O(n)$ field operations, and $2n+O(\sqrt n)$ scalar multiplications. Moreover,
the opening proof consists of a constant number of field elements.
This is a significant improvement over previous works which would require either
1. $O(n\log n)$ field operations; or
2. $O(\log n)$ size opening proof.

The main technical component is a new method of verifiably folding a witness via univariate polynomial division.
As opposed to previous methods, the proof size and prover time remain constant *regardless of the folding factor*.

## 2025/395

* Title: Provably Secure Approximate Computation Protocols from CKKS
* Authors: Intak Hwang, Yisol Hwang, Miran Kim, Dongwon Lee, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2025/395)
* [Download](https://eprint.iacr.org/2025/395.pdf)

### Abstract

Secure multi-party computation (MPC) enables collaborative, privacy-preserving computation over private inputs. Advances in homomorphic encryption (HE), particularly the CKKS scheme, have made secure computation practical, making it well-suited for real-world applications involving approximate computations. However, the inherent approximation errors in CKKS present significant challenges in developing MPC protocols.

This paper investigates the problem of secure approximate MPC from CKKS. We first analyze CKKS-based protocols in two-party setting. When only one party holds a private input and the other party acts as an evaluator, a simple protocol with the noise smudging technique on the encryptor's side achieves security in the standard manner. When both parties have private inputs, we demonstrate that the protocol incorporating independent errors from each party achieves a relaxed standard security notion, referred to as a liberal security. Nevertheless, such a protocol fails to satisfy the standard security definition. To address this limitation, we propose a novel protocol that employs a distributed sampling approach to generate smudging noise in a secure manner, which satisfies the standard security definition.

Finally, we extend the two-party protocols to the multi-party setting. Since the existing threshold CKKS-based MPC protocol only satisfies the liberal security, we present a novel multi-party protocol achieving the standard security by applying multi-party distributed sampling of a smudging error.

For all the proposed protocols, we formally define the functionalities and provide rigorous security analysis within the simulation-based security framework. To the best of our knowledge, this is the first work to explicitly define the functionality of CKKS-based approximate MPC and achieve formal security guarantees.

## 2025/396

* Title: Trail-Estimator: An Automated Verifier for Differential Trails in Block Ciphers
* Authors: Thomas Peyrin, Quan Quan Tan, Hongyi Zhang, Chunning Zhou
* [Permalink](https://eprint.iacr.org/2025/396)
* [Download](https://eprint.iacr.org/2025/396.pdf)

### Abstract

Differential cryptanalysis is a powerful technique for attacking block ciphers, wherein the Markov cipher assumption and stochastic hypothesis are commonly employed to simplify the search and probability estimation of differential trails. However, these assumptions often neglect inherent algebraic constraints, potentially resulting in invalid trails and inaccurate probability estimates. Some studies identified violations of these assumptions and explored how they impose constraints on key material, but they have not yet fully captured all relevant ones. This study proposes Trail-Estimator, an automated verifier for differential trails on block ciphers, consisting of two parts: a constraint detector Cons-Collector and a solving tool Cons-Solver. We first establish the fundamental principles that will allow us to systematically identify all constraint subsets within a differential trail, upon which Cons-Collector is built. Then, Cons-Solver utilizes specialized preprocessing techniques to efficiently solve the detected constraint subsets, thereby determining the key space and providing a comprehensive probability distribution of differential trails. To validate its effectiveness, Trail-Estimator is applied to verify 14 differential trails for the SKINNY, LBLOCK, and TWINE block ciphers. Experimental results show that Trail-Estimator consistently identifies previously undetected constraints for SKINNY and discovers constraints for the first time for LBLOCK and TWINE. Notably, it is the first tool to discover long nonlinear constraints extending beyond five rounds in these ciphers. Furthermore, Trail-Estimator's accuracy is validated by experiments showing its predictions closely match the real probability distribution of short-round differential trails.

## 2025/397

* Title: Blind Signatures from Cryptographic Group Actions
* Authors: Dung Hoang Duong, Xuan Thanh Khuc, Youming Qiao, Willy Susilo, Chuanqi Zhang
* [Permalink](https://eprint.iacr.org/2025/397)
* [Download](https://eprint.iacr.org/2025/397.pdf)

### Abstract

We provide a generic construction of blind signatures from cryptographic group actions following the framework of the blind signature CSIOtter introduced by Katsumata et al. (CRYPTO'23) in the context of isogeny (commutative group action). We adapt and modify that framework to make it work even for non-commutative group actions. As a result, we obtain a blind signature from abstract group actions which are proven to be secure in the random oracle model. We also propose an instantiation based on a variant of linear code equivalence, interpreted as a symmetric group action.

## 2025/398

* Title: Tight Adaptive Simulation Security for Identity-based Inner-Product FE in the (Quantum) Random Oracle Model
* Authors: Tenma Edamura, Atsushi Takayasu
* [Permalink](https://eprint.iacr.org/2025/398)
* [Download](https://eprint.iacr.org/2025/398.pdf)

### Abstract

Abdalla et al. (ASIACRYPT 2020) introduced a notion of identity-based inner-product functional encryption (IBIPFE) that combines identity-based encryption and inner-product functional encryption (IPFE). Thus far, several pairing-based and lattice-based IBIPFE schemes have been proposed. However, there are two open problems. First, there are no known IBIPFE schemes that satisfy the adaptive simulation-based security. Second, known IBIPFE schemes that satisfy the adaptive indistinguishability-based security or the selective simulation-based security do not have tight reductions. In this paper, we propose lattice-based and pairing-based IBIPFE schemes that satisfy the tight adaptive simulation-based security. At first, we propose a generic transformation from an indistinguishability-based secure $(L + 1)$-dimensional (IB)IPFE scheme to a simulation-based secure $L$-dimensional (IB)IPFE scheme. The proposed transformation improves Agrawal et al.'s transformation for plain IPFE (PKC 2020) that requires an indistinguishability-based secure $2L$-dimensional scheme. Then, we construct a lattice-based IBIPFE scheme that satisfies the tight adaptive indistinguishability-based security under the LWE assumption in the quantum random oracle model. We apply the proposed transformation and obtain the first lattice-based IBIPFE scheme that satisfies adaptive simulation-based security. Finally, we construct a pairing-based IBIPFE scheme that satisfies the tight adaptive simulation-based security under the DBDH assumption in the random oracle model. The pairing-based scheme does not use the proposed transformation towards the best efficiency.

## 2025/399

* Title: Computational Quantum Anamorphic Encryption and Anamorphic Secret Sharing
* Authors: SAYANTAN GANGULY, Shion Samadder Chaudhury
* [Permalink](https://eprint.iacr.org/2025/399)
* [Download](https://eprint.iacr.org/2025/399.pdf)

### Abstract

The concept of anamorphic encryption, first formally introduced by Persiano et al. in their influential 2022 paper titled ``Anamorphic Encryption: Private Communication Against a Dictator,'' enables embedding covert messages within ciphertexts. One of the key distinctions between a ciphertext embedding a covert message and an original ciphertext, compared to an anamorphic ciphertext, lies in the indistinguishability between the original ciphertext and the anamorphic ciphertext. This encryption procedure has been defined based on a public-key cryptosystem. Initially, we present a quantum analogue of the classical anamorphic encryption definition that is based on public-key encryption. Additionally, we introduce a definition of quantum anamorphic encryption that relies on symmetric key encryption. Furthermore, we provide a detailed generalized construction of quantum anamorphic symmetric key encryption within a general framework, which involves taking any two quantum density matrices of any different dimensions and constructing a single quantum density matrix, which is the quantum anamorphic ciphertext containing ciphertexts of both of them. Subsequently, we introduce a definition of computational anamorphic secret-sharing and extend the work of \c{C}akan et al. on computational quantum secret-sharing to computational quantum anamorphic secret-sharing, specifically addressing scenarios with multiple messages, multiple keys, and a single share function. This proposed secret-sharing scheme demonstrates impeccable security measures against quantum adversaries.

## 2025/400

* Title: Re-Randomize and Extract: A Novel Commitment Construction Framework Based on Group Actions
* Authors: Kaijie Jiang, Anyu Wang, Hengyi Luo, Guoxiao Liu, Tang Gang, Yanbin Pan, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2025/400)
* [Download](https://eprint.iacr.org/2025/400.pdf)

### Abstract

Cryptographic group actions have attracted growing attention as a useful tool for constructing cryptographic schemes.
Among their applications, commitment schemes are particularly interesting as fundamental primitives, playing a crucial role in protocols such as zero-knowledge proofs, multi-party computation, and more.

In this paper, we introduce a novel framework to construct commitment schemes based on cryptographic group actions.
Specifically, we propose two key techniques for general group actions: re-randomization and randomness extraction.
Roughly speaking, a re-randomization algorithm introduces randomness within an orbit for any input element, while a randomness extractor maps this randomness to uniformity over the message space.
We demonstrate that these techniques can significantly facilitate the construction of commitment schemes, providing a flexible framework for constructing either perfectly hiding or perfectly binding commitments, depending on the type of extractor involved.
Moreover, we extend our framework to support the construction of commitments with additional desirable properties beyond hiding and binding, such as dual-mode commitments and enhanced linkable commitments.
These extensions are achieved by further adapting the extractor to satisfy trapdoor or homomorphic properties.
Finally, we instantiate all our proposed commitment schemes using lattices, specifically leveraging the lattice isomorphism problem (LIP) and the lattice automorphism problem (LAP) as underlying cryptographic assumptions.
To the best of our knowledge, this is the first commitment scheme construction based on LIP/LAP.
Additionally, we use LIP to provide a repair and improvement to the tensor isomorphism-based non-interactive commitment scheme proposed by D'Alconzo, Flamini, and Gangemi (ASIACRYPT 2023), which was recently shown to be insecure by an attack from Gilchrist, Marco, Petit, and Tang (CRYPTO 2024).

## 2025/401

* Title: PEGASIS: Practical Effective Class Group Action using 4-Dimensional Isogenies
* Authors: Pierrick Dartois, Jonathan Komada Eriksen, Tako Boris Fouotsa, Arthur Herlédan Le Merdy, Riccardo Invernizzi, Damien Robert, Ryan Rueger, Frederik Vercauteren, Benjamin Wesolowski
* [Permalink](https://eprint.iacr.org/2025/401)
* [Download](https://eprint.iacr.org/2025/401.pdf)

### Abstract

In this paper, we present the first practical algorithm to compute an effective group action of the class group of any imaginary quadratic order $\mathcal{O}$ on a set of supersingular elliptic curves primitively oriented by $\mathcal{O}$. Effective means that we can act with any element of the class group directly, and are not restricted to acting by products of ideals of small norm, as for instance in CSIDH. Such restricted effective group actions often hamper cryptographic constructions, e.g. in signature or MPC protocols.

Our algorithm is a refinement of the Clapoti approach by Page and Robert, and uses $4$-dimensional isogenies. As such, it runs in polynomial time, does not require the computation of the structure of the class group, nor expensive lattice reductions, and our refinements allows it to be instantiated with the orientation given by the Frobenius endomorphism. This makes the algorithm practical even at security levels as high as CSIDH-4096. Our implementation in SageMath takes 1.5s to compute a group action at the CSIDH-512 security level, 21s at CSIDH-2048 level and around 2 minutes at the CSIDH-4096 level. This marks the first instantiation of an effective cryptographic group action at such high security levels. For comparison, the recent KLaPoTi approach requires around 200s at the CSIDH-512 level in SageMath and 2.5s in Rust.

## 2025/402

* Title: Related-Key Differential and Boomerang Cryptanalysis in the Fixed-Key Model
* Authors: Chengcheng Chang, Kai Hu, Muzhou Li, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2025/402)
* [Download](https://eprint.iacr.org/2025/402.pdf)

### Abstract

Differential cryptanalysis, along with its variants such as boomerang attacks, is widely used to evaluate the security of block ciphers. These cryptanalytic techniques often rely on assumptions like the \textit{hypothesis of stochastic equivalence} and \textit{Markov ciphers assumption}. Recently, more attention has been paid to verifying whether differential characteristics (DCs) meet these assumptions, finding both positive and negative results.
A part of these efforts includes the automatic search methods for both the value and difference propagation (e.g., Liu et al. CRYPTO 2020, Nageler et al. ToSC 2025/1), structural constraints analysis (e.g., Tan and Peyrin, ToSC 2022/4), and the quasidifferential (Beyne and Rijmen, CRYPTO 2022).
Nevertheless, less attention has been paid to the related-key DCs and boomerang distinguishers, where the same assumptions are used. To the best of our knowledge, only some related-tweakey DCs of \skinny were checked thanks to its linear word-based key-schedule, and no similar work is done for boomerang distinguishers.

The verification of related-key DCs and boomerang distinguishers is as important as that of DCs, as they often hold the longest attack records for block ciphers.
This paper focuses on investigating the validity of DCs in the related-key setting and boomerang distinguishers in both single- and related-key scenarios.
For this purpose, we generalize Beyne and Rijmen's quasidifferential techniques for the related-key DCs and boomerang attacks.

First, to verify related-key DCs, the related-key quasi-DC is proposed. Similar to the relationship between the quasi-DC and DC, the exact probability of a related-key DC is equal to the sum of all corresponding related-key quasi-DCs' correlations.
Since the related-key quasi-DCs involve the key information, we can determine the probability of the target related-key DC in different key subspaces.
We find both positive and negative results.
For example, we verify the 18-round related-key DC used in the best attack on \gift-64 whose probability is $2^{-58}$, finding that this related-key DC has a higher probability for $2^{128} \times (2^{-5} + 2^{-8})$ keys which is around $2^{-50}$, but it is impossible for the remaining keys.

Second, we identify proper bases to describe the boomerang distinguishers with the geometric approach. A quasi-BCT is constructed to consider the value influence in the boomerang connectivity table (BCT). For the DC parts, the quasi-biDDT is used. Connecting the quasi-BCT and quasi-biDDT, we can verify the probability of a boomerang distinguisher with quasi-boomerang characteristics..
This also allows us to analyze the probability of the boomerang in different key spaces.
For a 17-round boomerang distinguisher of \skinny-64-128 whose probability is $2^{-50}$, we find that the probability can be $2^{-44}$ for half of keys, and impossible for the other half.

## 2025/403

* Title: Periodic Table of Cryptanalysis: Geometric Approach with Different Bases
* Authors: Kai Hu, Chi Zhang, Chengcheng Chang, Jiashu Zhang, Meiqin Wang, Thomas Peyrin
* [Permalink](https://eprint.iacr.org/2025/403)
* [Download](https://eprint.iacr.org/2025/403.pdf)

### Abstract

In the past three decades, we have witnessed the creation of various cryptanalytic attacks. However, relatively little research has been done on their potential underlying connections. The geometric approach, developed by Beyne in 2021, shows that a cipher can be viewed as a linear operation when we treat its input and output as points in an induced \textit{free vector space}.
By performing a change of basis for the input and output spaces, one can obtain various transition matrices. Linear, differential, and (ultrametic) integral attacks have been well reinterpreted by Beyne's theory in a unified way.

Thus far, the geometric approach always uses the same basis for the input and output spaces. We observe here that this restriction is unnecessary and allowing different bases makes the geometric approach more flexible and able to interpret/predict more attack types. Given some set of bases for the input and output spaces, a family of basis-based attacks is defined by combining them, and all attacks in this family can be studied in a unified automatic search method.

We revisit three kinds of bases from previous geometric approach papers and extend them to four extra ones by introducing new rules when generating new bases. With the final seven bases, we can obtain $7^{2d}$ different basis-based attacks in the $d$-th order spaces, where the \textit{order} is defined as the number of messages used in one sample during the attack.

We then provide four examples of applications of this new framework. First, we show that by choosing a better pair of bases, Beyne and Verbauwhede's ultrametric integral cryptanalysis can be interpreted as a single element of a transition matrix rather than as a linear combination of elements. This unifies the ultrametric integral cryptanalysis with the previous linear and quasi-differential attacks.
Second, we revisit the multiple-of-$n$ property with our refined geometric approach and exhibit new multiple-of-$n$ distinguishers that can reach more rounds of the \skinny-64 cipher than the state-of-the-art.
Third, we study the multiple-of-$n$ property for the first-order case, which is similar to the subspace trail but it is the divisibility property that is considered. This leads to a new distinguisher for 11-round-reduced \skinny-64..
Finally, we give a closed formula for differential-linear approximations without any assumptions, even confirming that the two differential-linear approximations of \simeck-32 and \simeck-48 found by Hadipour \textit{et al.} are deterministic independently of concrete key values.
We emphasize that all these applications were not possible before.

## 2025/404

* Title: SNARKs for Stateful Computations on Authenticated Data
* Authors: Johannes Reinhart, Erik-Oliver Blass, Bjoern Annighoefer
* [Permalink](https://eprint.iacr.org/2025/404)
* [Download](https://eprint.iacr.org/2025/404.pdf)

### Abstract

We present a new generalization of (zk-)SNARKs combining two additional features at the same time. Besides the verification of correct computation, our new SNARKs also allow, first, the verification of input data authenticity. Specifically, a verifier can confirm that the input to the computation originated from a trusted source. Second, our SNARKs support verification of stateful computations across multiple rounds, ensuring that the output of the current round correctly depends on the internal state of the previous round. Our SNARKs are specifically suited to applications in cyber-physical control systems, where computations are periodically carried out and need to be checked immediately. Our focus is on concrete practicality, so we abstain from arithmetizing hash functions or signatures in our SNARKs. Rather, we modify the internals of an existing SNARK to extend its functionality. Additionally, we present new optimizations to reduce proof size, prover time, and verification time in our setting. With our construction, prover runtime improves significantly over the baseline by a factor of 89. Verification time is 70 % less for computations on authenticated data and 33 % less for stateful computations. To demonstrate relevance and practicality, we implement and benchmark our new SNARKs in a sample real-world scenario with
a (simple) quadcopter flight control system.

## 2025/405

* Title: Withdrawable signatures in Fiat-Shamir with aborts constructions
* Authors: Ramses Fernandez
* [Permalink](https://eprint.iacr.org/2025/405)
* [Download](https://eprint.iacr.org/2025/405.pdf)

### Abstract

This article presents an extension of the work performed by Liu, Baek and Susilo on withdrawable signatures to the Fiat-Shamir with aborts paradigm. We introduce an abstract construction, and provide security proofs for this proposal. As an instantiation, we provide a concrete construction for a withdrawable signature scheme based on Dilithium.

## 2025/406

* Title: AsyRand: fast asynchronous distributed randomness beacon with reconfiguration
* Authors: Liang Zhang, Tao Liu, Zhanrong Ou, Haibin Kan, Jiheng Zhang
* [Permalink](https://eprint.iacr.org/2025/406)
* [Download](https://eprint.iacr.org/2025/406.pdf)

### Abstract

Distributed randomness beacon protocols, which generate publicly verifiable randomness at regular intervals, are crucial for a wide range of applications. The publicly verifiable secret sharing (PVSS) scheme is a promising cryptographic primitive for implementing beacon protocols, such as Hydrand (S\&P '20) and SPURT (S\&P '22). However, two key challenges for practical deployment remain unresolved: asynchrony and reconfiguration. In this paper, we introduce the $AsyRand$ beacon protocol to address these challenges. In brief, $AsyRand$ leverages Bracha Reliable Broadcast (BRB) or BRB-like protocols for message dissemination and incorporates a producer-consumer model to decouple the production and consumption of PVSS commitments. In the producer-consumer model, PVSS commitments are produced and consumed using a queue data structure. Specifically, the producer process is responsible for generating new PVSS commitments and reaching consensus on them within the queue, while the consumer process continuously consumes the commitments to recover PVSS secrets and generate new beacon values. This separation allows the producer and consumer processes to operate simultaneously and asynchronously, without the need for a global clock. Moreover, the producer-consumer model enables each party to detect potential faults in other parties by monitoring the queue length. If necessary, parties in $AsyRand$ can initiate a removal process for faulty parties. BRB is also employed to facilitate the addition of new parties without requiring a system restart. In summary, $AsyRand$ supports reconfiguration, enhancing both the protocol's usability and reliability. Additionally, we propose a novel PVSS scheme based on the $\Sigma$ protocol, which is of independent interest. Regarding complexity, $AsyRand$ achieves state-of-the-art performance with $O(n^2)$ communication complexity, $O(n)$ computation complexity, and $O(n)$ verification complexity.

## 2025/407

* Title: Delegatable ABE with Full Security from Witness Encryption
* Authors: Rishab Goyal, Saikumar Yadugiri
* [Permalink](https://eprint.iacr.org/2025/407)
* [Download](https://eprint.iacr.org/2025/407.pdf)

### Abstract

Delegatable Attribute-Based Encryption (DABE) is a well-known generalization of ABE, proposed to mirror organizational hierarchies. In this work, we design a fully-secure DABE scheme from witness encryption and other simple assumptions. Our construction does not rely on Random Oracles, and we provide a black-box reduction to polynomial hardness of underlying assumptions. To the best of our knowledge, this is the first DABE construction (beyond hierarchical identity-based encryption) that achieves full security without relying on complexity leveraging. Our DABE supports an unbounded number of key delegations, and the secret key size grows just linearly with each key delegation operation.

## 2025/408

* Title: Hybrid Obfuscated Key Exchange and KEMs
* Authors: Felix Günther, Michael Rosenberg, Douglas Stebila, Shannon Veitch
* [Permalink](https://eprint.iacr.org/2025/408)
* [Download](https://eprint.iacr.org/2025/408.pdf)

### Abstract

Hiding the metadata in Internet protocols serves to protect user privacy, dissuade traffic analysis, and prevent network ossification. Fully encrypted protocols require even the initial key exchange to be obfuscated: a passive observer should be unable to distinguish a protocol execution from an exchange of random bitstrings. Deployed obfuscated key exchanges such as Tor's pluggable transport protocol obfs4 are Diffie–Hellman-based, and rely on the Elligator encoding for obfuscation. Recently, Günther, Stebila, and Veitch (CCS '24) proposed a post-quantum variant pq-obfs, using a novel building block called obfuscated key encapsulation mechanisms (OKEMs): KEMs whose public keys and ciphertexts look like random bitstrings.

For transitioning real-world protocols, pure post-quantum security is not enough. Many are taking a hybrid approach, combining traditional and post-quantum schemes to hedge against security failures in either component. While hybrid KEMs are already widely deployed (e.g., in TLS 1.3), existing hybridization techniques fail to provide hybrid obfuscation guarantees for OKEMs. Further, even if a hybrid OKEM existed, the pq-obfs protocol would still not achieve hybrid obfuscation.

In this work, we address these challenges by presenting the first OKEM combiner that achieves hybrid IND-CCA security with hybrid ciphertext obfuscation guarantees, and using this to build Drivel, a modification of pq-obfs that is compatible with hybrid OKEMs. Our OKEM combiner allows for a variety of practical instantiations, e.g., combining obfuscated versions of DHKEM and ML-KEM. We additionally provide techniques to achieve unconditional public key obfuscation for LWE-based OKEMs, and explore broader applications of hybrid OKEMs, including a construction of the first hybrid password-authenticated key exchange (PAKE) protocol secure against adaptive corruptions in the UC model.

## 2025/409

* Title: Low Communication Threshold FHE from Standard (Module-)LWE
* Authors: Hiroki Okada, Tsuyoshi Takagi
* [Permalink](https://eprint.iacr.org/2025/409)
* [Download](https://eprint.iacr.org/2025/409.pdf)

### Abstract

Threshold fully homomorphic encryption (ThFHE) is an extension of FHE that can be applied to multiparty computation (MPC) with low round complexity. Recently, Passelègue and Stehlé (Asiacrypt 2024) presented a simulation-secure ThFHE scheme with polynomially small decryption shares from “yet another” learning with errors assumption (LWE), in which the norm of the secret key is leaked to the adversary. While “yet another” LWE is reduced from standard LWE, its module variant, “yet another” module-LWE (MLWE), lacks a known reduction from standard MLWE. Because of this, it is left as an open question to extend their scheme to the MLWE-based construction.

In this paper, we address this open problem: we propose a simulation-secure ThFHE scheme with polynomially small decryption shares whose security is (directly) reduced from standard LWE/MLWE. Our core technique, which we call “noise padding”, eliminates the need of “yet another” assumptions: we distribute shares of a small error and use them to adjust the distribution of decryption noise so that no information about the secret key is leaked. As side benefits of our construction, our ThFHE efficiently realizes arbitrary T-out-of-N threshold decryption via simple Shamir secret sharing instead of {0, 1}-linear secret sharing. Furthermore, the sizes of keys, ciphertexts and decryption shares in our scheme are constant w.r.t. the number of parties N ; we achieve compactness w.r.t. N.

## 2025/410

* Title: TreeKEM: A Modular Machine-Checked Symbolic Security Analysis of Group Key Agreement in Messaging Layer Security
* Authors: Théophile Wallez, Jonathan Protzenko, Karthikeyan Bhargavan
* [Permalink](https://eprint.iacr.org/2025/410)
* [Download](https://eprint.iacr.org/2025/410.pdf)

### Abstract

The Messaging Layer Security (MLS) protocol standard proposes a novel tree-based protocol that enables efficient end-to-end encrypted messaging over large groups with thousands of members. Its functionality can be divided into three components: TreeSync for authenticating and synchronizing group state, TreeKEM for the core group key agreement, and TreeDEM for group message encryption. While previous works have analyzed the security of abstract models of TreeKEM, they do not account for the precise low-level details of the protocol standard. This work presents the first machine-checked security proof for TreeKEM. Our proof is in the symbolic Dolev-Yao model and applies to a bit-level precise, executable, interoperable specification of the protocol. Furthermore, our security theorem for TreeKEM composes naturally with a previous result for TreeSync to provide a strong modular security guarantee for the published MLS standard.

## 2025/411

* Title: Security of the Ascon Authenticated Encryption Mode in the Presence of Quantum Adversaries
* Authors: Nathalie Lang, Stefan Lucks, Bart Mennink, Suprita Talnikar
* [Permalink](https://eprint.iacr.org/2025/411)
* [Download](https://eprint.iacr.org/2025/411.pdf)

### Abstract

We examine the post-quantum security of the Ascon authenticated encryption (AE) mode. In spite of comprehensive research of Ascon's classical security, the potential impact of quantum adversaries on Ascon has not yet been explored much. We investigate the generic security of the Ascon AE mode in the setting where the adversary owns a quantum computer to improve its attack, while the adversarial encryption or decryption queries are still classical. In this so-called Q1 model, Ascon achieves security up to approximately $\min\{2^{c/3},2^{k/2}\}$ evaluations, where $c$ is the capacity, $k$ the key size, and the adversary is block-wise adaptive but restricted to one forgery attempt. Our technique is based on applying the semi-classical one-way to hiding (O2H) lemma, and on tailoring the puncture set to the Ascon mode.
Additionally, we discuss different parameter choices for Ascon and compare our results to generic quantum attacks, such as Grover-based key search and state recovery.

## 2025/412

* Title: Multi-Authority Functional Encryption: Corrupt Authorities, Dynamic Collusion, Lower Bounds, and More
* Authors: Rishab Goyal, Saikumar Yadugiri
* [Permalink](https://eprint.iacr.org/2025/412)
* [Download](https://eprint.iacr.org/2025/412.pdf)

### Abstract

Decentralization is a great enabler for adoption of modern cryptography in real-world systems. Widespread adoption of blockchains and secure multi-party computation protocols are perfect evidentiary examples for dramatic rise in deployment of decentralized cryptographic systems. Much of cryptographic research can be viewed as reducing (or eliminating) the dependence on trusted parties, while shielding from stronger adversarial threats. In this work, we study the problem of multi-authority functional encryption (MAFE), a popular decentralized generalization of functional encryption (FE). Our main contributions are:

1. We design MAFE for all poly-sized circuits, in the bounded collusion model, under the minimal assumption of PKE/OWFs. Prior to our work, this required either sub-exponentially secure obfuscation, or $\log n$-party key exchange, or Random Oracles and sub-exponentially secure PKE. We also extend our constructions to the dynamic collusion model under the minimal assumptions of IBE/OWFs. Unlike all prior works, our MAFE systems are truly dynamic and put no restrictions on the maximum number of authorities.

2. Under the hardness of learning with errors (LWE) assumption, we design MAFE for all poly-sized circuits where we allow adversaries to adaptively corrupt local authorities. We allow an adversary to corrupt any $k$ out of $n$ local authorities as long as ${{n}\choose{k}}$ = poly$(\lambda)$. Prior to this, such MAFE relied on sub-exponentially secure obfuscation. Additionally, we design a new MAFE compiler for boosting selective authority corruptions to non-adaptive authority corruptions.

3. We prove a tight implication from MAFE to (VBB/indistinguishability) obfuscation. We show that MAFE implies obfuscation only if the number of attribute bits (jointly) controlled by all corrupt local authorities is $\omega(\log \lambda)$. This proves optimality of our second result for a wide range of parameters.

4. Finally, we propose a new MAFE system that we refer to as multi-authority attribute-based functional encryption (MA-ABFE). We view it as an approach to get best of both worlds (fully collusion resistant MA-ABE, and bounded collusion resistant MAFE). By combining our results with prior MA-ABE results, we obtain MA-ABFE for $\mathsf{NC}^1 \circ \mathsf{P}/\mathsf{Poly}$ from standard pairing-based assumptions, and for $\mathsf{DNF} \circ \mathsf{P}/\mathsf{Poly}$ from LWE, both in the Random Oracle Model. We also describe a simple construction of MA-ABE for general predicates from witness encryption, and combining with known results, we also get MA-ABFE for $\mathsf{P}/\mathsf{Poly} \circ \mathsf{P}/\mathsf{Poly}$ from evasive LWE.

## 2025/413

* Title: Garblet: Multi-party Computation for Protecting Chiplet-based Systems
* Authors: Mohammad Hashemi, Shahin Tajik, Fatemeh Ganji
* [Permalink](https://eprint.iacr.org/2025/413)
* [Download](https://eprint.iacr.org/2025/413.pdf)

### Abstract

The introduction of shared computation architectures assembled from
heterogeneous chiplets introduces new security threats. Due to the shared logical and physical resources, an untrusted chiplet can act maliciously to surreptitiously probe the data communication between chiplets or sense the computation shared between them. This paper presents Garblet, the first framework to leverage the flexibility offered by chiplet technology and Garbled Circuits (GC)-based MPC to enable efficient, secure computation even in the presence of potentially compromised chiplets. Our approach integrates a customized hardware Oblivious Transfer (OT) module and an optimized evaluator engine into chiplet-based platforms. This configuration distributes the tasks of garbling and evaluating circuits across two chiplets, reducing communication costs and enhancing computation speed. We implement this framework on an AMD/Xilinx UltraScale+ multi-chip module and demonstrate its effectiveness using benchmark functions. Additionally, we introduce a novel circuit decomposition technique that allows for parallel processing across multiple chiplets to further improve computational efficiency. Our results highlight the potential of chiplet systems for accelerating GC (e.g., the time complexity of garbled AES is 0.0226ms) in order to guarantee the security and privacy of the computation on chiplets.

## 2025/414

* Title: Deimos Cipher: A High-Entropy, Secure Encryption Algorithm with Strong Diffusion and Key Sensitivity
* Authors: Mohsin Belam
* [Permalink](https://eprint.iacr.org/2025/414)
* [Download](https://eprint.iacr.org/2025/414.pdf)

### Abstract

Deimos Cipher is a symmetric encryption algorithm designed to achieve high entropy and strong diffusion while maintaining efficiency.
It employs advanced cryptographic transformations to ensure robust security against modern cryptanalysis techniques.
Entropy tests demonstrate its ability to generate highly randomized ciphertext, surpassing industry standards.
Avalanche effect analysis confirms optimal diffusion, achieving an average bit change of 50.18% in large datasets.
Key sensitivity tests reveal a 50.54% ciphertext difference for minimal key variations, ensuring strong resistance to differential cryptanalysis.
With fast encryption and decryption speeds, Deimos Cipher offers a balanced approach between security and performance, making it suitable for secure communication and data protection.
This paper presents the algorithm's design, security analysis, and benchmarking against established cryptographic standards.

## 2025/415

* Title: On the Soundness of Algebraic Attacks against Code-based Assumptions
* Authors: Miguel Cueto Noval, Simon-Philipp Merz, Patrick Stählin, Akin Ünal
* [Permalink](https://eprint.iacr.org/2025/415)
* [Download](https://eprint.iacr.org/2025/415.pdf)

### Abstract

We study recent algebraic attacks (Briaud-Øygarden EC'23) on the Regular Syndrome Decoding (RSD) problem and the assumptions underlying the correctness of their attacks' complexity estimates. By relating these assumptions to interesting algebraic-combinatorial problems, we prove that they do not hold in full generality. However, we show that they are (asymptotically) true for most parameter sets, supporting the soundness of algebraic attacks on RSD. Further, we prove—without any heuristics or assumptions—that RSD can be broken in polynomial time whenever the number of error blocks times the square of the size of error blocks is larger than 2 times the square of the dimension of the code.

Additionally, we use our methodology to attack a variant of the Learning With Errors problem where each error term lies in a fixed set of constant size. We prove that this problem can be broken in polynomial time, given a sufficient number of samples. This result improves on the seminal work by Arora and Ge (ICALP'11), as the attack's time complexity is independent of the LWE modulus.

## 2025/416

* Title: Trapdoor Hash Functions and PIR from Low-Noise LPN
* Authors: Damiano Abram, Giulio Malavolta, Lawrence Roy
* [Permalink](https://eprint.iacr.org/2025/416)
* [Download](https://eprint.iacr.org/2025/416.pdf)

### Abstract

Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given a encoding key for a function $f$, a hash on $x$ together with a (small) input encoding allow one to recover $f(x)$. TDHs are a versatile tool and a useful building block for more complex cryptographic protocols.

In this work, we propose the first TDH construction assuming the (quasi-polynomial) hardness of the LPN problem with noise rate $\epsilon = O(\log^{1+\beta} n / n)$ for $\beta>0$, i.e., in the so-called low-noise regime. The construction achieves $2^{\Theta(\log^{1-\beta} \lambda)}$ compression factor. As an application, we obtain a private-information retrieval (PIR) with communication complexity $L / 2^{\Theta(\log^{1-\beta} L)}$, for a database of size L. This is the first PIR scheme with non-trivial communication complexity (asymptotically smaller than $L$) from any code-based assumption.

## 2025/417

* Title: Evaluation of Privacy-aware Support Vector Machine (SVM) Learning using Homomorphic Encryption
* Authors: William J Buchanan, Hisham Ali
* [Permalink](https://eprint.iacr.org/2025/417)
* [Download](https://eprint.iacr.org/2025/417.pdf)

### Abstract

The requirement for privacy-aware machine learning increases as we continue to use PII (Personally Identifiable Information) within machine training. To overcome these privacy issues, we can apply Fully Homomorphic Encryption (FHE) to encrypt data before it is fed into a machine learning model. This involves creating a homomorphic encryption key pair, and where the associated public key will be used to encrypt the input data, and the private key will decrypt the output. But, there is often a performance hit when we use homomorphic encryption, and so this paper evaluates the performance overhead of using the SVM machine learning technique with the OpenFHE homomorphic encryption library.. This uses Python and the scikit-learn library for its implementation. The experiments include a range of variables such as multiplication depth, scale size, first modulus size, security level, batch size, and ring dimension, along with two different SVM models, SVM-Poly and SVM-Linear. Overall, the results show that the two main parameters which affect performance are the ring dimension and the modulus size, and that SVM-Poly and SVM-Linear show similar performance levels.

## 2025/418

* Title: ProofFrog: A Tool For Verifying Game-Hopping Proofs
* Authors: Ross Evans, Matthew McKague, Douglas Stebila
* [Permalink](https://eprint.iacr.org/2025/418)
* [Download](https://eprint.iacr.org/2025/418.pdf)

### Abstract

Cryptographic proofs allow researchers to provide theoretical guarantees on the security that their constructions provide. A proof of security can completely eliminate a class of attacks by potential adversaries. Human fallibility, however, means that even a proof reviewed by experts may still hide flaws or outright errors. Proof assistants are software tools built for the purpose of formally verifying each step in a proof, and as such have the potential to prevent erroneous proofs from being published and insecure constructions from being implemented.

Unfortunately, existing tooling for verifying cryptographic proofs has found limited adoption in the cryptographic community, in part due to concerns with ease of use. We present ProofFrog: a new tool for verifying cryptographic game-hopping proofs. ProofFrog is designed with the average cryptographer in mind, using an imperative syntax similar to C for specifying games and a syntax for proofs that closely models pen-and-paper arguments. As opposed to other proof assistant tools which largely operate by manipulating logical formulae, ProofFrog manipulates abstract syntax trees (ASTs) into a canonical form to establish indistinguishable or equivalent behaviour for pairs of games in a user-provided sequence. We also detail the domain-specific language developed for use with the ProofFrog proof engine, the exact transformations it applies to canonicalize ASTs, and case studies of verified proofs. A tool like ProofFrog that prioritizes ease of use can lower the barrier of entry to using computer-verified proofs and aid in catching insecure constructions before they are made public.

## 2025/419

* Title: Samaritan: Linear-time Prover SNARK from New Multilinear Polynomial Commitments
* Authors: Chaya Ganesh, Sikhar Patranabis, Nitin Singh
* [Permalink](https://eprint.iacr.org/2025/419)
* [Download](https://eprint.iacr.org/2025/419.pdf)

### Abstract

We study linear-time prover SNARKs and make the following contributions:

We provide a framework for transforming a univariate polynomial commitment scheme into a multilinear polynomial commitment scheme. Our transformation is generic, can be instantiated with any univariate scheme and improves on prior transformations like Gemini (EUROCRYPT 2022) and Virgo (S&P 2020) in all relevant parameters: proof size, verification complexity, and prover complexity. Instantiating the above framework with the KZG univariate polynomial commitment scheme, we get SamaritanPCS – the first multilinear polynomial commitment scheme with constant proof size and linear-time prover. SamaritanPCS is a drop-in replacement for the popular PST scheme, and improves upon PST in all relevant parameters.

We construct LogSpartan – a new multilinear PIOP for R1CS based on recent techniques for lookup arguments. Compiling this PIOP using SamaritanPCS gives Samaritan – a SNARK in the universal and updatable SRS setting. Samaritan has linear-time prover, logarithmic verification and logarithmic proof size. Concretely, its proof size is one of the smallest among other known linear-time prover SNARKs without relying on concretely expensive proof recursion techniques. For an R1CS instance with 1 million constraints, Samaritan (over BLS12-381 curve) has a proof size of 6.7KB.

We compare Samaritan with other linear-time prover SNARKs in the updatable setting. We asymptotically improve on the $\log^2 n$ proof size of Spartan. Unlike Libra (CRYPTO 2019), the argument size of Samaritan is independent of the circuit depth. Compared to Gemini (EUROCRYPT 2022), Samaritan achieves 3$\times$ smaller argument size at 1 million constraints. We match the argument size of HyperPlonk, which is the smallest linear-time SNARK for the Plonkish constraint system, while achieving slightly better verification complexity.

We believe that our transformation and our techniques for applying lookups based on logarithmic derivatives to the multilinear setting are of wider interest.

## 2025/420

* Title: Non-Interactive Verifiable Aggregation
* Authors: Ojaswi Acharya, Suvasree Biswas, Weiqi Feng, Adam O'Neill, Arkady Yerukhimovich
* [Permalink](https://eprint.iacr.org/2025/420)
* [Download](https://eprint.iacr.org/2025/420.pdf)

### Abstract

Consider a weak analyst that wishes to outsource data collection and computation of aggregate statistics over a a potentially large population of (also weak) clients to a powerful server. For flexibility and efficiency, we consider public-key and non-interactive protocols, meaning the clients know the analyst's public key but do not share secrets, and each client sends at most one message. Furthermore, the final step should be silent, whereby the analyst simply downloads the (encrypted) result from the server when needed. To capture this setting, we define a new primitive we call Non-Interactive Verifiable Aggregation (NIVA).
We require both privacy and robustness for a NIVA protocol to be deemed secure. Namely, our security notion for NIVA ensures that the clients' data remains private to both the server and the analyst, while also ensuring that malicious clients cannot skew the results by providing faulty data.
We propose a secure NIVA protocol, which we call PEAR (for Private, Efficient, Accurate, Robust), which can validate inputs according to any NP validity rule. PEAR is based on a novel combination of functional encryption for inner-products (Abdalla et al., PKC 2015) and fully-linear probabilistically-checkable proofs (Boneh et al., Crypto 2019). We emphasize that PEAR is non-interactive, public-key, and makes black-box use of the underlying cryptographic primitives. Additionally, we devise substantial optimizations of PEAR for practically-relevant validity rules. Finally, we implement PEAR to show feasibility for such validity rules, conducting a thorough performance evaluation. In particular, we compare PEAR to two more straightforward or "off-the-shelf" NIVA protocols and show performance gains, demonstrating the merit of our new approach. The bottleneck in our protocol comes from the fact that we require the underlying IPFE scheme to be "unrestricted" over a large field. As more efficient such schemes are developed, they can be immediately be plugged into PEAR for further gains.

## 2025/421

* Title: A Note on Obfuscation-based Attacks on Private-coin Evasive LWE
* Authors: Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada
* [Permalink](https://eprint.iacr.org/2025/421)
* [Download](https://eprint.iacr.org/2025/421.pdf)

### Abstract

The evasive learning with errors (evasive LWE) assumption is a new assumption recently introduced by Wee (Eurocrypt 2022) and Tsabary (Crypto 2022) independently, as a significant strengthening of the standard LWE assumption.
While the assumption is known to imply various strong primitives including witness encryption [Wee22,Tsabary22], the assumption in the most general case (i.e., the private coin variant) is considered quite implausible due to the obfuscation based attack mentioned in [Wee22]. This obfuscation based attack is then later formalized by Vaikuntanathan, Wee, and Wichs [VWW22].
In this note, we revisit their attack and show that the attack actually does not work by showing a concrete counterexample. We then show that their attack can be made valid with some modifications. Along the way, we also improve the counterexample by making it provable. Specifically, our counterexample is valid assuming the (plain) LWE assumption and the existence of instance-hiding witness encryption, whereas their original counterexample was dependent on the heuristic assumption of the existence of an ideal obfuscation.

## 2025/422

* Title: Private Computation on Common Fuzzy Records
* Authors: Kyoohyung Han, Seongkwang Kim, Yongha Son
* [Permalink](https://eprint.iacr.org/2025/422)
* [Download](https://eprint.iacr.org/2025/422.pdf)

### Abstract

Private computation on common records refers to analyze data from two databases containing shared records without revealing personal information. As a basic requirement for private computation, the databases involved essentially need to be aligned by a common identification system. However, it is hard to expect such common identifiers in real world scenario. For this reason, multiple quasi-identifiers can be used to identify common records. As some quasi-identifiers might be missing or have typos, it is important to support fuzzy records setting. Identifying common records using quasi-identifiers requires manipulation of highly sensitive information, which could be privacy concerns.

This work studies the problem of enabling such data analysis on the fuzzy records of quasi-identifiers. To this end, we propose ordered threshold-one (OTO) matching which can be efficiently realized by circuit-based private set intersection (CPSI) protocols and some multiparty computation (MPC) techniques. Furthermore, we introduce some generic encoding techniques from traditional matching rules to the OTO matching. Finally, we achieve a secure efficient private computation protocol which supports various matching rules which have already been widely used.

We also demonstrate the superiority of our proposal with experimental validation. First, we empirically check that our encoding to OTO matching does not affect accuracy a lot for the benchmark datasets found in the fuzzy record matching literature. Second, we implement our protocol and achieve significantly faster performance at the cost of communication overhead compared to previous privacy-preserving record linkage (PPRL) protocols. In the case of 100K records for each dataset, our work shows 147.58MB communication cost, 10.71s setup time, and 1.97s online time, which is 7.78 times faster compared to the previous work (50.12 times faster when considering online time only).

## 2025/423

* Title: Multi-Client Attribute-Based Unbounded Inner Product Functional Encryption, and More
* Authors: Subhranil Dutta, Aikaterini Mitrokotsa, Tapas Pal, Jenit Tomy
* [Permalink](https://eprint.iacr.org/2025/423)
* [Download](https://eprint.iacr.org/2025/423.pdf)

### Abstract

This paper presents the concept of a multi-client functional encryption (MC-FE) scheme for attribute-based inner product functions (AB-IP), initially proposed by Abdalla et al. [ASIACRYPT’20], in an unbounded setting. In such a setting, the setup is independent of vector length constraints, allowing secret keys to support functions of arbitrary lengths, and clients can dynamically choose vector lengths during encryption. The functionality outputs the sum of inner products if vector lengths and indices meet a specific relation, and all clients’ attributes satisfy the key’s policy. We propose the following constructions based on the matrix decisional Diffie-Hellman assumption in a natural permissive setting
of unboundedness:

– the first multi-client attribute-based unbounded IPFE (MC-AB-UIPFE) scheme secure in the standard model, overcoming previous limitations where clients could only encrypt fixed-length data;
– the first multi-input AB-UIPFE (MI-AB-UIPFE) in the public key setting; improving upon prior bounded constructions under the same assumption;
– the first dynamic decentralized UIPFE (DD-UIPFE); enhancing the dynamism property of prior works.

Technically, we follow the blueprint of Agrawal et al. [CRYPTO’23] but begin with a new unbounded FE called extended slotted unbounded IPFE. We first construct a single-input AB-UIPFE in the standard model and then extend it to multi-input settings. In a nutshell, our work demonstrates the applicability of function-hiding security of IPFE in realizing variants of multi-input FE capable of encoding unbounded
length vectors both at the time of key generation and encryption.

## 2025/424

* Title: Matchmaker: Fast Secure Inference across Deployment Scenarios
* Authors: Neha Jawalkar, Nishanth Chandran, Divya Gupta, Rahul Sharma, Arkaprava Basu
* [Permalink](https://eprint.iacr.org/2025/424)
* [Download](https://eprint.iacr.org/2025/424.pdf)

### Abstract

Secure Two-Party Computation (2PC) enables secure inference with cryptographic guarantees that protect the privacy of the model owner and client. However, it adds significant performance overhead. In this work, we make 2PC-based secure inference efficient while considering important deployment scenarios.
We observe that the hitherto unconsidered latency of fetching keys from storage significantly impacts performance, as does network speed. We design a Linear Secret Sharing (LSS)-based system $LSS^M$ and a Function Secret Sharing (FSS)-based system $FSS^M$ for secure inference, optimized for small key size and communication, respectively. Notably, our highly-optimized and hardware-aware CPU-based $LSS^M$ outperforms prior GPU-based LSS systems by up to $50\times$. We then show that the best choice between $LSS^M$ and $FSS^M$ depends on the deployment scenario.
In fact, under certain deployments, a combination of $LSS^M$ and $FSS^M$ can leverage heterogeneous processing across CPU and GPU. Such protocol-system co-design lets us outperform state-of-the-art secure inference systems
by up to $21\times$ (geomean $3.25\times$).

## 2025/425

* Title: A Note on the Blindness of the Scheme from ePrint 2025/397
* Authors: Lucjan Hanzlik
* [Permalink](https://eprint.iacr.org/2025/425)
* [Download](https://eprint.iacr.org/2025/425.pdf)

### Abstract

This note demonstrates that the blind signature scheme based on cryptographic group actions, as proposed in ePrint paper 2025/397, fails to ensure blindness. Specifically, we construct an adversary that achieves a $1/8$ advantage in the blindness experiment. The attack leverages selective abort techniques (also known as selective failure attacks), a well-known strategy in the MPC literature.

## 2025/426

* Title: Exploring How to Authenticate Application Messages in MLS: More Efficient, Post-Quantum, and Anonymous Blocklistable
* Authors: Keitaro Hashimoto, Shuichi Katsumata, Guillermo Pascual-Perez
* [Permalink](https://eprint.iacr.org/2025/426)
* [Download](https://eprint.iacr.org/2025/426.pdf)

### Abstract

The Message Layer Security (MLS) protocol has recently been standardized by the IETF. MLS is a scalable secure group messaging protocol expected to run more efficiently compared to the Signal protocol at scale, while offering a similar level of strong security. Even though MLS has undergone extensive examination by researchers, the majority of the works have focused on confidentiality.

In this work, we focus on the authenticity of the application messages exchanged in MLS. Currently, MLS authenticates every application message with an EdDSA signature and while manageable, the overhead is greatly amplified in the post-quantum setting as the NIST-recommended Dilithium signature results in a 40x increase in size. We view this as an invitation to explore new authentication modes that can be used instead. We start by taking a systematic view on how application messages are authenticated in MLS and categorize authenticity into four different security notions. We then propose several authentication modes, offering a range of different efficiency and security profiles. For instance, in one of our modes, COSMOS++, we replace signatures with one-time tokens and a MAC tag, offering roughly a 75x savings in the post-quantum communication overhead. While this comes at the cost of weakening security compared to the authentication mode used by MLS, the lower communication overhead seems to make it a worthwhile trade-off with security.

## 2025/427

* Title: BUFFing Threshold Signature Schemes
* Authors: Marc Fischlin, Aikaterini Mitrokotsa, Jenit Tomy
* [Permalink](https://eprint.iacr.org/2025/427)
* [Download](https://eprint.iacr.org/2025/427.pdf)

### Abstract

We explore advanced security notions for threshold signature schemes, focusing on Beyond UnForgeability Features (BUFF), introduced by Cremers et al. (S&P’21) in the non-threshold setting. The BUFF properties protect against attacks based on maliciously chosen keys, e.g., expropriating a message-signature pair under a new public key (called exclusive ownership). We first formalize these notions in the threshold setting and examine their relationships. Notably, unlike regular signature schemes, the hierarchy of variants of exclusive ownership notions only holds for threshold schemes if they are also robust.
We then present a generic compiler that transforms any threshold signature scheme to satisfy exclusive ownership, and message-bound signature properties with minimal overhead. Furthermore, we modify the threshold BLS signature scheme to achieve these additional properties without increasing the signature size. Lastly, we identify specific structures in threshold signature schemes where BUFF properties can be naturally extended from the underlying standard signature scheme, and we analyze and prove the security properties in some of the existing threshold schemes.

## 2025/428

* Title: On Improved Cryptanalytic Results against ChaCha for Reduced Rounds ≥ 7
* Authors: Nitin Kumar Sharma, Sabyasachi Dey, Santanu Sarkar, Subhamoy Maitra
* [Permalink](https://eprint.iacr.org/2025/428)
* [Download](https://eprint.iacr.org/2025/428.pdf)

### Abstract

In this paper, we analyze the subtle issues of complexity estimates related to state-of-the-art cryptanalytic efforts on ChaCha. In this regard, we demonstrate that the currently best-known cryptanalytic result on $7$-round ChaCha with time $2^{189.7}$ and data $2^{102.63}$ [Xu et al., ToSC 2024] can be estimated as $2^{178.12}$ for time and $2^{101.09}$ for data complexity. We improve the best-known result for the $7.25$ round by obtaining an improved set of Probabilistic Neutral Bits and considering our revised estimation. Our result with time complexity $2^{212.43}$ and data complexity $2^{100.56}$ improves the result of Xu et al., where they could achieve time and data complexity $2^{223.9}$ and $2^{100.80}$, respectively. For both the $7$ and $7.25$ rounds, we can show an improvement of the order of $2^{11}$ in the time complexity.. For $7.5$-round, we improve the result of Dey [IEEE-IT 2024], which reports the time and data complexity of $2^{255.24}$ and $2^{32.64}$, respectively. By applying the formula of the same paper and incorporating additional PNBs, we obtain improved time and data complexity of $2^{253.23}$ and $2^{34.47}$, respectively. Thus, this paper describes the currently best-known cryptanalytic results against reduced round ChaCha. Our results do not affect the security claims of the complete algorithm with 20 rounds. Also, we provide a rebuttal of the Work by Wang et al. \cite{wangeprint} and analyze their claim about the error in the ``Divide-and-Conquer'' Approach.

## 2025/429

* Title: Enhanced CKKS Bootstrapping with Generalized Polynomial Composites Approximation
* Authors: Seonhong Min, Joon-woo Lee, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2025/429)
* [Download](https://eprint.iacr.org/2025/429.pdf)

### Abstract

Bootstrapping in approximate homomorphic encryption involves evaluating the modular reduction function. Traditional methods decompose the modular reduction function into three components: scaled cosine, double-angle formula, and inverse sine. While these approaches offer a strong trade-off between computational cost and level consumption, they lack flexibility in parameterization.

In this work, we propose a new method to decompose the modular reduction function with improved parameterization, generalizing prior trigonometric approaches. Numerical experiments demonstrate that our method achieves near-optimal approximation errors. Additionally, we introduce a technique that integrates the rescaling operation into matrix operations during bootstrapping, further reducing computational overhead.

## 2025/430

* Title: Non-interactive Anonymous Tokens with Private Metadata Bit
* Authors: Foteini Baldimtsi, Lucjan Hanzlik, Quan Nguyen, Aayush Yadav
* [Permalink](https://eprint.iacr.org/2025/430)
* [Download](https://eprint.iacr.org/2025/430.pdf)

### Abstract

Anonymous tokens with private metadata bit (ATPM) have received increased interest as a method for anonymous client authentication while also embedding trust signals that are only readable by the authority who holds the issuance secret key and nobody else. A drawback of all existing ATPM constructions is that they require client-issuer interaction during the issuance process. In this work, we build the first non-interactive anonymous tokens (NIAT) with private metadata bit, inspired by the recent work of Hanzlik (Eurocrypt '23) on non-interactive blind signatures. We discuss how the non-interaction property during the issuance process allows for more efficient issuance protocols that avoid the need for online signing. We construct an efficient NIAT scheme based on Structure-preserving Signatures on Equivalence Classes (SPS-EQ) and experimentally evaluate its performance. We also present an extension to our NIAT construction that allows the identification of clients who attempt to double-spend (i.e., present the same token twice).

## 2025/431

* Title: Commitment Schemes Based on Module-LIP
* Authors: Hengyi Luo, Kaijie Jiang, Yanbin Pan, Anyu Wang
* [Permalink](https://eprint.iacr.org/2025/431)
* [Download](https://eprint.iacr.org/2025/431.pdf)

### Abstract

Recently, Jiang et al. (EUROCRYPT 2025) proposed a universal framework for constructing commitment schemes using group actions, and instantiated it with the Lattice Isomorphism Problem (LIP). This paper attempts to construct an instantiation based on module-LIP with this framework. More precisely, we first present a reduction from $\mathcal{O}_{\mathbb{L}}^2$-LIP to $\mathcal{O}_{\mathbb{L}}^2$-LAP. Then we develop a re-randomized algorithm based on the self-reduction framework of Module-LIP (Ducas et al. ASIACRYPT 2022), adapting it to the framework to construct commitment schemes.

## 2025/432

* Title: Black-Box (and Fast) Non-Malleable Zero Knowledge
* Authors: Vincenzo Botta, Michele Ciampi, Emmanuela Orsini, Luisa Siniscalchi, Ivan Visconti
* [Permalink](https://eprint.iacr.org/2025/432)
* [Download](https://eprint.iacr.org/2025/432.pdf)

### Abstract

Non-malleable zero-knowledge (NMZK), originally introduced in the seminal work of Dolev, Dwork, and Naor (STOC 91), is a fundamental concept for modeling the security of proof systems against man-in-the-middle attacks.

Recently, Kim, Liang, and Pandey (CRYPTO 2022) presented the first efficient constant-round NMZK argument system based solely on symmetric-key cryptography. Their construction relies on a non-black-box use of the involved cryptographic primitives and on multiple executions of Ligero (CCS 2017) that affect both the round complexity and the computational efficiency of their protocol. Their work left open the natural important challenge of achieving NMZK using the underlying primitives only in a black-box fashion (regardless of the number of rounds and actual efficiency).

In this paper, we solve the aforementioned open problem by presenting the first NMZK argument system based on the black-box use of cryptographic primitives. Our work is optimal in the use of primitives since we only need one-way functions, and asymptotically optimal in the number of rounds since we only require a constant number of rounds. Our argument system is non-malleable with respect to the strong "simulation-extractability" flavor of non-malleability.

Furthermore, we also show that our construction can be efficiently instantiated in Minicrypt, significantly improving upon the work of Kim et al., both in terms of round complexity and computational efficiency.

## 2025/433

* Title: MIDAS: an End-to-end CAD Framework for Automating Combinational Logic Locking
* Authors: Akashdeep Saha, Siddhartha Chowdhury, Rajat Subhra Chakraborty, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2025/433)
* [Download](https://eprint.iacr.org/2025/433.pdf)

### Abstract

Logic locking has surfaced as a notable safeguard
against diverse hazards that pose a risk to the integrated circuit
(IC) supply chain. Existing literature on logic locking largely
encompasses the art of proposing new constructions, on the one
hand, and unearthing weaknesses in such algorithms on the
other. Somehow, in this race of make and break, the stress on
automation of adopting such techniques on real-life circuits has
been rather limited. For the first time, we present a generic
end-to-end combinational logic locking CAD framework, MIDAS.
This framework analyses circuit netlists and generates locked
netlists. Due to its generic circuit analysis, it bridges the gap,
integrates diverse logic locking techniques, and offers a scope of
integration of potential future ones. MIDAS framework’s efficacy
has been verified through its application on ISCAS’85 and
ISCAS’99 benchmark circuits, locked using six different schemes
such as EPIC, Anti-SAT, SFLL-HD, SFLL-fault, CAS-Lock, and
LoPher. MIDAS minimizes the hardware overhead requirements
of otherwise resource-intensive locking technique LoPher by
extracting an influential portion of circuit to lock and utilizing
a simple fitness function. We also assess the overhead increase
for the aforementioned locking methods, thereby complicating
the identification of influential nodes within the locked netlists.
Finally, we evaluate MIDAS by selectively locking parts of a
commercially-designed open-source RISC-V core.

## 2025/434

* Title: Fine-Grained Verifier NIZK and Its Applications
* Authors: Shuai Han, Shengli Liu, Xiangyu Liu, Dawu Gu
* [Permalink](https://eprint.iacr.org/2025/434)
* [Download](https://eprint.iacr.org/2025/434.pdf)

### Abstract

In this paper, we propose a new type of non-interactive zero-knowledge (NIZK), called Fine-grained Verifier NIZK (FV-NIZK), which provides more flexible and more fine-grained verifiability of proofs than standard NIZK that supports public verifiability and designated-verifier NIZK (DV-NIZK) that supports private verifiability. FV-NIZK has two statistically (or computationally) equivalent verification approaches:

--- a master verification using the master secret key $msk$;

--- a fine-grained verification using a derived secret key $sk_d$, which is derived from $msk$ w.r.t. $d$ (which may stand for user identity, email address, vector, etc.).

We require unbounded simulation soundness (USS) of FV-NIZK to hold, even if an adversary obtains derived secret keys $sk_d$ with $d$ of its choices, and define proof pseudorandomness which stipulates the pseudorandomness of proofs for adversaries that are not given any secret key.

We present two instantiations of FV-NIZK for linear subspace languages, based on the matrix decisional Diffie-Hellman (MDDH) assumption.
One of the FV-NIZK instantiations is pairing-free and achieves almost tight USS and proof pseudorandomness. We also adapt the two instantiations to support unbounded fine-grained secret key delegations.

We illustrate the usefulness of FV-NIZK by showing two applications and obtain the following pairing-free schemes:

--- the first almost tightly multi-challenge CCA (mCCA)-secure inner-product functional encryption (IPFE) scheme without pairings;

--- the first public-key encryption (PKE) scheme that reconciles the inherent contradictions between public verifiability and anonymity.
We formalize such PKE as Fine-grained Verifiable PKE (FV-PKE), which derives a special key from the decryption secret key, such that for those who obtain the derived key, they can check the validity of ciphertexts but the anonymity is lost from their views (CCA-security still holds for them), while for others who do not get the derived key, they cannot do the validity check but the anonymity holds for them.

Our FV-PKE scheme achieves almost tight mCCA-security for adversaries who obtain the derived keys, and achieves almost tight ciphertext pseudorandomness (thus anonymity) for others who do not get any derived key.

## 2025/435

* Title: Constant-Time Code: The Pessimist Case
* Authors: Thomas Pornin
* [Permalink](https://eprint.iacr.org/2025/435)
* [Download](https://eprint.iacr.org/2025/435.pdf)

### Abstract

This note discusses the problem of writing cryptographic implementations in software, free of timing-based side-channels, and many ways in which that endeavour can fail in practice. It is a pessimist view: it highlights why such failures are expected to become more common, and how constant-time coding is, or will soon become, infeasible in all generality.

## 2025/436

* Title: The Algebraic One-More MISIS Problem and Applications to Threshold Signatures
* Authors: Chenzhi Zhu, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2025/436)
* [Download](https://eprint.iacr.org/2025/436.pdf)

### Abstract

This paper introduces a new one-more computational problem for lattice-based cryptography, which we refer to as the Algebraic One-More MISIS problem, or AOM-MISIS for short. It is a modification of the AOM-MLWE problem recently introduced by Espitau et al. (CRYPTO ’24) to prove security of new two-round threshold signatures.

Our first main result establishes that the hardness of AOM-MISIS is implied by the hardness of MSIS and MLWE (with suitable parameters), both of which are standard assumptions for efficient lattice-based cryptography. We prove this result via a new generalization of a technique by Tessaro and Zhu (EUROCRYPT ’23) used to prove hardness of a one-more problem for linear hash functions assuming their collision resistance, for which no clear lattice analogue was known. Since the hardness of AOM-MISIS implies the hardness of AOM-MLWE, our result resolves the main open question from the work of Espitau et al.., who only provided a similar result for AOM-MLWE restricted to selective adversaries, a class which does not cover the use for threshold signatures.

Furthermore, we show that our novel formulation of AOM-MISIS offers a better interface to develop tighter security bounds for state-of-the-art two-round threshold signatures. We exemplify this by providing new proofs of security, assuming the hardness of MLWE and MSIS, for two threshold signatures, the one proposed in the same work by Espitau et al., as well as a recent construction by Chairattana-Apirom et al. (ASIACRYPT 2024). For the former scheme, we also show that it satisfies the strongest security notion (TS-UF-4) in the security hierarchy of Bellare et al. (CRYPTO ’22), as a result of independent interest.

## 2025/437

* Title: Improved Cryptanalysis of ChaCha: Beating PNBs with Bit Puncturing
* Authors: Antonio Flórez-Gutiérrez, Yosuke Todo
* [Permalink](https://eprint.iacr.org/2025/437)
* [Download](https://eprint.iacr.org/2025/437.pdf)

### Abstract

ChaCha is a widely deployed stream cipher and one of the most important symmetric primitives. Due to this practical importance, many cryptanalysis have been proposed. Until now, Probabilistic Neutral Bits (PNBs) have been the most successful. Given differential-linear distinguishers, PNBs are the technique for key recovery relying on an experimental backward correlation obtained through blackbox analysis. A careful theoretical analysis exploiting the round function design may find a better attack and improve our understanding, but the complicated nature of the ARX structure makes such analysis difficult.
%
We propose a theoretical methodology inspired by bit puncturing, which was recently proposed at Eurocrypt 2024. Our method has a theoretical foundation and is thus fundamentally different from PNBs, to which it is the first effective alternative. As a result, we significantly improved the attack complexity for 6, 7, and 7.5-round ChaCha. The 7-round attack is about $2^{40}$ times faster than the previous best. Furthermore, we propose the first 7.5-round attack with a non-negligible advantage over an exhaustive search.

Date	Sujet	#		Auteur
10 Mar 25	[digest] 2025 Week 10	1		IACR ePrint Archive