[digest] 2025 Week 22

## In this issue

1. [2023/1716] Attribute-Based Encryption for Circuits of ...
2. [2025/270] A Decomposition Approach for Evaluating Security of ...
3. [2025/868] Delegated PSI from Homomorphic Encryptions
4. [2025/945] Quantum Security Analysis of the Key-Alternating ...
5. [2025/946] Logup*: faster, cheaper logup argument for small- ...
6. [2025/947] Quantum Rewinding for IOP-Based Succinct Arguments
7. [2025/948] Resolving the Efficiency-Utility Dilemma of ...
8. [2025/949] Almost-Total Puzzles and Their Applications
9. [2025/950] Breaking Poseidon Challenges with Graeffe ...
10. [2025/951] Enhancing Provable Security and Efficiency of ...
11. [2025/952] A Provably Secure W-OTS$^+$ based on MQ Problem
12. [2025/953] Tight Multi-User Security of CCM and Enhancement by ...
13. [2025/954] Poseidon and Neptune: Gröbner Basis Cryptanalysis ...
14. [2025/955] Towards Better Integral Distinguishers over ...
15. [2025/956] LEAF: A Low-Latency Evaluation Architecture for ...
16. [2025/957] Laurent Polynomial-Based Linear Transformations for ...
17. [2025/958] Efficient Pairings Final Exponentiation Using ...
18. [2025/959] Zero-Trust Post-quantum Cryptography Implementation ...
19. [2025/960] A Framework for Advanced Signature Notions
20. [2025/961] Addendum to How Small Can S-boxes Be?
21. [2025/962] An almost key-homomorphic post-quantum block cipher ...
22. [2025/963] Permutation-Based Hashing with Stronger (Second) ...
23. [2025/964] TOOP: A transfer of ownership protocol over Bitcoin
24. [2025/965] Multiparty FHE Redefined: A Framework for Unlimited ...
25. [2025/966] Multiparty Homomorphic Secret Sharing and More from ...
26. [2025/967] Registered Functional Encryption for Pseudorandom ...
27. [2025/968] Learning with Alternating Moduli, Arora-Ge over ...
28. [2025/969] Decentralized Data Archival: New Definitions and ...
29. [2025/970] How to Verify that a Small Device is Quantum, ...
30. [2025/971] Sabot: Efficient and Strongly Anonymous ...
31. [2025/972] Generalized BGV, BFV, and CKKS for Homomorphic ...
32. [2025/973] On Proving Equivalence Class Signatures Secure from ...

## 2023/1716

* Title: Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More
* Authors: Yao-Ching Hsieh, Huijia Lin, Ji Luo
* [Permalink](https://eprint.iacr.org/2023/1716)
* [Download](https://eprint.iacr.org/2023/1716.pdf)

### Abstract

Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, STOC ’09; Brakerski–Vaikuntanathan, FOCS ’11], there is still a significant gap in understanding related homomorphic primitives supporting all *unrestricted* polynomial-size computations.  One prominent example is attribute-based encryption (ABE).  The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov–Vaikuntanathan–Wee, STOC ’13; Boneh et al., Eurocrypt ’14], only accommodate circuits up to a *predetermined* depth, akin to leveled homomorphic encryption.  In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth.  Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes.  So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation.  An interesting question that has remained open for over a decade is whether the circular security assumptions enabling FHE can similarly benefit ABE.

In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations.

- Relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size.

- Based on the *evasive circular* LWE assumption, a stronger variant of the recently proposed *evasive* LWE assumption [Wee, Eurocrypt ’22; Tsabary, Crypto ’22], we construct full-fledged ABE and predicate encryption (PE) schemes for circuits of unbounded depth and size.

Our LFE, 1-key FE, and reusable garbling schemes achieve almost optimal succinctness (up to polynomial factors in the security parameter).  Their ciphertexts and input encodings have sizes linear in the input length, while function digest, secret keys, and garbled circuits have constant sizes independent of circuit parameters (for Boolean outputs).  In fact, this gives the first constant-size garbled circuits without relying on indistinguishability obfuscation.  Our ABE and PE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant-size.



## 2025/270

* Title: A Decomposition Approach for Evaluating Security of Masking
* Authors: Vahid Jahandideh, Bart Mennink, Lejla Batina
* [Permalink](https://eprint.iacr.org/2025/270)
* [Download](https://eprint.iacr.org/2025/270.pdf)

### Abstract

Masking is a common countermeasure against side-channel attacks that encodes secrets into multiple shares, each of which may be subject to leakage. A key question is under what leakage conditions, and to what extent, does increasing the number of shares actually improve the security of these secrets. Although this question has been studied extensively in low-SNR regimes, scenarios where the adversary obtains substantial information—such as on low-noise processors or through static power analysis—have remained underexplored.
In this paper, we address this gap by deriving necessary and sufficient noise requirements for masking security in both standalone encodings and linear gadgets. We introduce a decomposition technique that reduces the relationship between an extended-field variable and its leakage into subproblems involving linear combinations of the variable’s bits. By working within binary subfields, we derive optimal bounds and then lift these results back to the extended field.
Beyond binary fields, we also present a broader framework for analyzing masking security in other structures, including prime fields. As an application, we prove a conjecture by Dziembowski et al. (TCC 2016), which states that for an additive group \(\mathbb{G}\) with its largest subgroup \(\mathbb{H}\), a \(\delta\)-noisy leakage satisfying \(\delta < 1 - \tfrac{|\mathbb{H}|}{|\mathbb{G}|}\) ensures that masking enhances the security of the secret.



## 2025/868

* Title: Delegated PSI from Homomorphic Encryptions
* Authors: Sicheng Wei, Jingwei Hu
* [Permalink](https://eprint.iacr.org/2025/868)
* [Download](https://eprint.iacr.org/2025/868.pdf)

### Abstract

This paper presents an efficient protocol for private set intersection in a setting with multiple set owners and a semi-honest cloud server. The core idea is to reduce the intersection computation to secure operations over Bloom filters, enabling both scalability and efficiency. By leveraging this transformation, our protocols achieve strong privacy guarantees while minimizing computation and communication overhead.



## 2025/945

* Title: Quantum Security Analysis of the Key-Alternating Ciphers
* Authors: Chen Bai, Mehdi Esmaili, Atul Mantri
* [Permalink](https://eprint.iacr.org/2025/945)
* [Download](https://eprint.iacr.org/2025/945.pdf)

### Abstract

In this work, we study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even–Mansour (EM) cipher underlying many block cipher constructions, including AES. While the classical security of KAC and the quantum security of the $1$-round KAC (i.e. Even-Mansour) cipher are well understood, the quantum resistance of multi-round KAC remains largely unexplored. We focus on the $2$-round KAC construction, defined using public $n$-bit permutations $P_1$, $P_2$ and keys $k_0$, $k_1$, and $k_2$ as $E(x) = P_2(P_1(x \oplus k_0) \oplus k_1) \oplus k_2.$ Our main contributions are as follows:

1. Quantum Lower Bounds. We provide the first formal analysis showing that a $2$-round KAC is quantum-secure in both the $Q1$ and $Q2$ models. Specifically, in the $Q1$ model, a (non-adaptive) adversary must make at least $2^{2n/5}$ quantum queries to the public permutations and at least $2^{2n/5}$ classical queries to the cipher in order to distinguish it from a random permutation (in contrast to the classical lower bound of $2^{2n/3}$ queries). As a corollary, we show that in the $Q2$ model, a (non-adaptive) adversary requires $2^{n/4}$ quantum queries. To achieve such a result, we employ the quantum hybrid method along with recently proposed lifting theorems in the ideal cipher and random permutation oracle model.

2. Quantum Key-Recovery Attack. We give the first nontrivial quantum key-recovery attack on multi-round KAC in the $Q1$ model where the adversary has quantum access to all of the public permutations. Our quantum attack applies to any $t$-round KAC and achieves quantum query complexity $O(2^{\alpha n})$, where $\alpha = \frac{t(t+1)}{(t+1)^2 + 1}$, improving over the best known classical bound of $O(2^{\alpha' n})$, where $\alpha' = \frac{t}{t+1}$, from Bogdanov et al. (EUROCRYPT 2012). The attack leverages a novel application of quantum walk algorithms specifically adapted to the KAC structure.

3. The $Q1^*$ Model. To bridge the classical and $Q1$ settings, we introduce the $Q1^*$, in which the adversary has quantum superposition access to at most one permutation. This model is crucial for our $Q1$ lower bound and supports similar key-recovery attacks to Q1, using fewer quantum resources. We believe $Q1^*$ is of independent interest.



## 2025/946

* Title: Logup*: faster, cheaper logup argument for small-table indexed lookups
* Authors: Lev Soukhanov
* [Permalink](https://eprint.iacr.org/2025/946)
* [Download](https://eprint.iacr.org/2025/946.pdf)

### Abstract

Logup argument (in it's modern GKR version, as described in eprint:2023/1284 paper) is a logarithmic derivative-based unindexed lookup argument. An indexed lookup argument can be constructed from unindexed one using standard trick.
   
    In this short informal note, we explain a different way of obtaining indexed lookup from logup, which does not commit any additional arrays of the size of the indexing array. That makes it particularly amenable for lookups in small tables (giving, to our knowledge, a first argument with this property).

    Additionally, this argument is not subject to numerator overflow issue that requires additional mitigation described in eprint:2024/2067.

    Improvements to SPARK / Lasso protocols are also discussed.



## 2025/947

* Title: Quantum Rewinding for IOP-Based Succinct Arguments
* Authors: Alessandro Chiesa, Marcel Dall'Agnol, Zijing Di, Ziyi Guan, Nicholas Spooner
* [Permalink](https://eprint.iacr.org/2025/947)
* [Download](https://eprint.iacr.org/2025/947.pdf)

### Abstract

We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. Specifically, we prove that an interactive variant of the *BCS transformation* is secure in the standard model against quantum adversaries when the vector commitment scheme is collapse binding.

Prior work established the post-quantum security of Kilian's succinct interactive argument, a special case of the BCS transformation for one-message IOPs (i.e., PCPs). That analysis is inherently limited to one message because the reduction, like all prior quantum rewinding reductions, aims to extract classical information (a PCP string) from the quantum argument adversary. Our reduction overcomes this limitation by instead extracting a *quantum algorithm* that implements an IOP adversary; representing such an adversary classically may in general require exponential complexity.

Along the way we define *collapse position binding*, which we propose as the ``correct'' definition of collapse binding for vector commitment schemes, eliminating shortcomings of prior definitions.

As an application of our results, we obtain post-quantum secure succinct arguments, in the standard model (no oracles), with the *best asymptotic complexity known*.



## 2025/948

* Title: Resolving the Efficiency-Utility Dilemma of Threshold Linearly Homomorphic Encryption via Message-Space Adapter
* Authors: Yijia Chang, Rongmao Chen, Chao Lin, Songze Li, Xinyi Huang
* [Permalink](https://eprint.iacr.org/2025/948)
* [Download](https://eprint.iacr.org/2025/948.pdf)

### Abstract

Threshold linearly homomorphic encryption (ThLHE) is a useful cryptographic tool for secure computation in multi-party settings, with applications in electronic voting, secure multiparty computation (MPC), and beyond. Although ThLHE offers significant advantages such as low communication overhead, its adoption in modern systems is hindered by a critical dilemma between efficiency and utility. Precisely, existing ThLHE schemes either suffer from high decryption complexity—typically $\mathcal{O}(N^2\log N)$ or worse for $N$ parties—or impose extra restrictions on the message space or participant set, limiting their practicality in large-scale and dynamic settings.


In this work, we resolve this efficiency-utility dilemma for ThLHE by introducing a novel primitive termed message-space adapter (MeSA). By developing a lattice-based MeSA for exponential ElGamal (Exp-ElGamal), we mitigate the small-message restriction of Exp-ElGamal while preserving its efficient threshold decryption. This leads to the design of the first ThLHE scheme that achieves quasi-linear decryption complexity without restrictions on the message space or participant set. We implement a prototype of this new ThLHE scheme and validate the quasi-linear growth of its running time with respect to $N$.

Beyond resolving this dilemma, we further extend the applications of our new ThLHE scheme. Specifically, we apply it to construct the first multi-party fully homomorphic encryption scheme with quasi-linear computation complexity and constant communication complexity, while supporting arbitrary threshold and dynamic participant set. This demonstrates the extra benefits of our ThLHE scheme with broader applicability.



## 2025/949

* Title: Almost-Total Puzzles and Their Applications
* Authors: Xiao Liang, Omkant Pandey, Yuhao Tang, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2025/949)
* [Download](https://eprint.iacr.org/2025/949.pdf)

### Abstract

Public-coin protocols are cryptographic protocols in which all messages sent by a specific party (typically the receiver or verifier) consist solely of random bits. These protocols have been extensively studied $\textit{in the classical setting}$ due to their advantageous properties in several scenarios, such as the parallel repetition of interactive arguments, and the design of secure multi-party computation with low round complexity, among others. Curiously, $\textit{post-quantum}$ constructions of public-coin protocols remain limited, particularly when optimization is sought in additional factors like round complexity or hardness assumptions.

We introduce the concept of $\textit{almost-total puzzles}$, a novel cryptographic primitive characterized by two key properties: (i) hardness against any efficient adversary, and (ii) an "almost-total" guarantee of the existence of solutions, even when the puzzle generator is malicious. We demonstrate that this primitive can be derived from one-way functions in public-coin, requiring only two rounds. By leveraging this primitive, we obtain a family of new $\textit{public-coin}$ results in both the classical and post-quantum settings, based on the $\textit{minimal assumption} $ of (post-quantum) one-way functions, including:

- five-round post-quantum extractable commitments and witness-indistinguishable arguments of knowledge, where the (knowledge) extractors achieve the $\textit{coherently expected quantum-polynomial-time}$
($\mathsf{EQPT}_c$) simulation proposed by Lombardi, Ma, and Spooner [FOCS'22];

- five-round classical extractable commitments that $\textit{do not suffer from over extraction}$;

- five-round classical delayed-input strong witness-indistinguishable arguments of knowledge, and delayed-input witness-hiding arguments of knowledge;

- the five-round post-quantum analogue of the last item, but with the difference that (1) the input can be delayed until the third round, and (2) post-quantum arguments of knowledge are again defined w.r.t.  $\mathsf{EQPT}_c$-simulation;

- $O(\log^* \lambda)$-round post-quantum non-malleable commitments.



## 2025/950

* Title: Breaking Poseidon Challenges with Graeffe  Transforms and Complexity Analysis by FFT  Lower Bounds
* Authors: Ziyu Zhao, Jintai Ding
* [Permalink](https://eprint.iacr.org/2025/950)
* [Download](https://eprint.iacr.org/2025/950.pdf)

### Abstract

Poseidon and Poseidon2 are cryptographic hash functions designed for efficient zero-knowledge proof protocols and have been widely adopted in Ethereum applications. To encourage security research, the Ethereum Foundation announced a bounty program in November 2024 for breaking the Poseidon challenges, i.e. solving the CICO (Constrained Input, Constrained Output) problems for round-reduced Poseidon constructions. In this paper, we explain how to apply the Graeffe transform to univariate polynomial solving, enabling efficient interpolation attacks against Poseidon. We will provide an open-source code and details our approach for solving several challenges valued at $20000 in total. Compared to existing attacks, we improves 2^{13} and 2^{4.5} times in wall time and memory usage, respectively. For all challenges we solved, the cost of memory access turns out to be an essential barrier, which makes the security margin much larger than expected. We actually prove that the memory access cost for FFT grows as the 4/3-power of the input size, up to a logarithmic factor. This indicates the commonly used pseudo linear estimate may be overly conservative. This is very different from multivariate equation solving whose main bottleneck is linear algebra over finite fields. Thus, it might be preferable to choose parameters such that the best known attack is interpolation, as it presents more inherent hardness.



## 2025/951

* Title: Enhancing Provable Security and Efficiency of Permutation-based DRBGs
* Authors: Woohyuk Chung, Seongha Hwang, Hwigyeom Kim, Jooyoung Lee
* [Permalink](https://eprint.iacr.org/2025/951)
* [Download](https://eprint.iacr.org/2025/951.pdf)

### Abstract

We revisit the security analysis of the permutation-based deterministic random bit generator~(DRBG) discussed by Coretti et al. at CRYPTO 2019. Specifically, we prove that their construction, based on the sponge construction, and hence called Sponge-DRBG in this paper, is secure up to $O\left(\min \left\{2^{\frac{c}{2}}, 2^{\frac{\lambda}{2}}\right\}\right)$ queries in the seedless robustness model, where $\lambda$ is the required min-entropy and $c$ is the sponge capacity. This significantly improves the provable security bound from the existing $O\left(\min \left\{2^{\frac{c}{3}}, 2^{\frac{\lambda}{2}}\right\}\right)$ to the birthday bound. We also show that our bound is tight by giving matching attacks.

As the Multi-Extraction game-based reduction proposed by Chung et al. at Asiacrypt 2024 is not applicable to Sponge-DRBG in a straightforward manner, we further refine and generalize the proof technique so that it can be applied to a broader class of DRBGs to improve their provable security.
 
We also propose a new permutation-based DRBG, dubbed POSDRBG, with almost the optimal output rate $1$, outperforming the output rate $\frac{r}{n}$ of Sponge-DRBG, where $n$ is the output size of the underlying permutation and $r=n-c$. We prove that POSDRBG is tightly secure up to $O\left(\min \left\{2^{\frac{c}{2}}, 2^{\frac{\lambda}{2}}\right\}\right)$ queries. Thus, to the best of our knowledge, POSDRBG is the first permutation-based DRBG that achieves the optimal output rate of 1, while maintaining the same level of provable security as Sponge-DRBG in the seedless robustness model.



## 2025/952

* Title: A Provably Secure W-OTS$^+$ based on MQ Problem
* Authors: Zijun Zhuang, Yingjie Zhang, Jintai Ding
* [Permalink](https://eprint.iacr.org/2025/952)
* [Download](https://eprint.iacr.org/2025/952.pdf)

### Abstract

In 2022, Antonov showed that SHA-256 does not satisfy some secure property that SPHINCS$^+$ needs, and a fogery attack based on this observation reduces the concrete classical security by approximately 40 bits of security. This illustrates a more general concern: the provable security of some hash-based signature schemes can be compromised when implemented with certain real-world hash functions, and motivates the need to design new functions with rigorous, provable security guarantees. Besides, it has been shown that from W-OTS to W-OTS$^+$, the security requirement for the hash function's collision resistance can be relaxed to second-preimage resistance (SPR), which means that it is possible to use some functions with SPR property to instantiate the underlying function family  $\mathcal{F}_n$ in W-OTS$^+$, and obtain a provably secure W-OTS$^+$.
In this paper, we use multivariate quadratic functions (MQ functions) to  instantiate  $\mathcal{F}_n$ in W-OTS$^+$, which yields the first provably secure W-OTS$^+.$ To prove its security, we need to derive the SPR property of MQ functions. The key is to show the $\mathbf{NP}$-hardness of finding second preimages.
Furthermore, we prove the multi-function, multi-target one-wayness (MM-OW) and the multi-function, multi-target second-preimage resistance (MM-SPR) of MQ functions, which implies the provable security of MQ-based W-OTS$^+$ in the multi-user setting, on the condition that the number of users is $O(n^{1-\epsilon})$  for some $\epsilon\in (0,1)$, where $n$ is the security parameter.



## 2025/953

* Title: Tight Multi-User Security of CCM and Enhancement by Tag-Based Key Derivation Applied to GCM and CCM
* Authors: Yusuke Naito, Yu Sasaki, Takeshi Sugawara
* [Permalink](https://eprint.iacr.org/2025/953)
* [Download](https://eprint.iacr.org/2025/953.pdf)

### Abstract

$\textsf{GCM}$ and $\textsf{CCM}$ are block cipher (BC) based authenticated encryption modes. In multi-user (mu) security, a total number of BC invocations by all users $\sigma$ and the maximum number of BC invocations per user $\sigma_\mathsf{u}$ are crucial factors. For $\textsf{GCM}$, the tight mu-security bound has been identified as $\frac{\sigma_\mathsf{u} \sigma}{2^n} + \frac{u p + u^2}{2^k}$, where $k$ and $n$ are respectively the key and block sizes, $u$ is the number of users, $p$ is the number of offline queries.In contrast, the $\mathsf{CCM}$'s mu-security bound is still unclear. Two bounds of $\frac{u \sigma_\mathsf{u}^2}{2^n} + \frac{u p + u^2}{2^k}$ and $\frac{\sigma^2}{2^n} + \frac{u p + u \sigma}{2^k}$ have been derived by Luykx~et~al.~(Asiacrypt~2017) and Zhang~et~al.~(CCS~2024), respectively, but both are not tight and worse than the $\textsf{GCM}$'s bound.  Moreover, methods to enhance mu security without disruptive changes in the scheme have been considered for $\textsf{GCM}$, namely nonce randomization ($\textsf{NR}$) to improve offline security and nonce-based key derivation ($\textsf{KD}$) to improve online security, but their applicability to $\textsf{CCM}$ has never been discussed. In this paper, we prove an improved mu-security bound of $\textsf{CCM}$, which is tight, and reaches the $\textsf{GCM}$'s bound. We then prove that $\textsf{NR}$ and $\textsf{KD}$ applied to $\textsf{CCM}$ result in the same bounds for the case to $\textsf{GCM}$. An important takeaway is that $\textsf{CCM}$ is now proved to be as secure as $\textsf{GCM}$. Moreover, we argue that $\textsf{NR}$ and $\textsf{KD}$ can be insufficient for some applications with massive data, and propose a new enhancement method called nonce-based and tag-based key derivation ($\textsf{NTKD}$) that is applied to $\textsf{GCM}$ and $\textsf{CCM}$. We prove that the resulting schemes meet such real-world needs.



## 2025/954

* Title: Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails
* Authors: Lorenzo Grassi, Katharina Koschatko, Christian Rechberger
* [Permalink](https://eprint.iacr.org/2025/954)
* [Download](https://eprint.iacr.org/2025/954.pdf)

### Abstract

At the current state of the art, algebraic attacks are the most efficient method for finding preimages and collisions for arithmetization-oriented hash functions, such as the closely related primitives Poseidon/Poseidon2 and Neptune. In this paper, we revisit Gröbner basis (GB) attacks that exploit subspace trails to linearize some partial rounds, considering both sponge and compression modes.

Starting from Poseidon's original security evaluation, we identified some inaccuracies in the model description that may lead to misestimated round requirements. Consequently, we reevaluate and improve the proposed attack strategy. We find that depending on the concrete instantiation, the original security analysis of Poseidon under- or overestimates the number of rounds needed for security. Moreover, we demonstrate that GB attacks leveraging subspace trails can outperform basic GB attacks for Poseidon/Poseidon2 and Neptune.

We propose a variant of the previous attack strategy that exploits a crucial difference between Poseidon/Poseidon2 and Neptune: while Poseidon's inverse round functions have a high degree, Neptune's inverse external rounds maintain the same degree as the forward rounds. Using this new model, we demonstrate that Neptune's security in compression mode cannot be reduced to its security against the Constrained-Input-Constrained-Output (CICO) problem. To the best of our knowledge, this is the first time a concrete example has been provided where finding preimages is easier than solving the corresponding CICO problem.

Our results emphasize the importance of considering the mode of operation in security analysis while confirming the overall security of Poseidon/Poseidon2 and Neptune against the presented algebraic attacks.



## 2025/955

* Title: Towards Better Integral Distinguishers over $\mathbb{F}_{p}$ Based on Exact Coefficients of Monomials
* Authors: Muzhou Li, Jiamin Cui, Longzheng Cui, Kai Hu, Chao Niu, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2025/955)
* [Download](https://eprint.iacr.org/2025/955.pdf)

### Abstract

Symmetric primitives used in multi-party computation, fully homomorphic encryption, and zero-knowledge proofs are often defined over Finite Field $\mathbb{F}_{q}$ with $q=2^t$ or an odd prime $p$. Integral attack is one of the most effective methods against such primitives due to the common use of low-degree non-linear layers. This in turn highlights the importance of a deeper understanding of degree growth. For ciphers defined over $\mathbb{F}_{2^t}$, numerous works have explored the growth of the algebraic degree. However, these methods cannot be directly applied to $\mathbb{F}_{p}$. At CRYPTO 2020, Beyne et al. extended the integral cryptanalysis to $\mathbb{F}_{p}$ by comparing degree with $s(p-1)$ when using $p^s$ data. However, given that the precise degree evaluation remains fundamentally challenging and often computationally infeasible, one may lose better integral distinguishers.

In this paper, we present the first automatic search model over $\mathbb{F}_{p}$ based on the exact coefficient $\mathcal{A}$ of the monomial $\prod_{w=1}^{s}x_w^{p-1}$ contained in the algebraic representation. This model is constructed following the Computation-Traceback-Determine framework, where $\mathcal{A}$ is represented by several sums of multinomial coefficients under specific conditions. The existence of integral properties is then transformed into a determination of whether these sums can consistently equal $0\bmod{p}$. This determination is facilitated by four newly developed propositions based on Lucas Theorem. To demonstrate the effectiveness of our framework, we apply it to all variants of GMiMC. As a result, we achieve the best integral distinguishers for GMiMC-erf/-crf using large primes when they are used as block ciphers. For GMiMC-nyb/-mrf using 32/64-bit primes, our integral distinguishers cover more rounds than all other attacks. Meanwhile, all distinguishers we identified are no worse than those trivial ones predicted only considering the maximal degree. This shows the necessity of considering exact coefficients when searching for integral distinguishers over $\mathbb{F}_p$. Our framework is further employed to assess the security of two HADES  designs: HadesMiMC and Poseidon2$^\pi$. The results reveal that the full rounds at the beginning and end of HADES provide sufficient resistance against integral cryptanalysis.



## 2025/956

* Title: LEAF: A Low-Latency Evaluation Architecture for Feedforward Block in Privacy-Preserving Transformer Inference
* Authors: Linru Zhang, Xiangning Wang, Xianhui Lu, Huaxiong Wang, Kwok Yan Lam
* [Permalink](https://eprint.iacr.org/2025/956)
* [Download](https://eprint.iacr.org/2025/956.pdf)

### Abstract

Fully homomorphic encryption (FHE) is an appealing and promising solution for privacy-preserving transformer inference to protect users' privacy. However, the huge computational overhead makes it unrealistic to apply FHE in real-world transformers for large language models (LLM). Current FHE-based approaches to secure transformer inference face significant performance challenges, with total latency exceeding 5 hours for 32-input batches.
The feedforward block, comprising a large-scale matrix multiplication followed by a GELU evaluation, is widely recognized as one of the most computationally intensive components in privacy-preserving transformer inference. In the state-of-the-art system NEXUS, evaluating the feedforward block incurs a total latency of 5,378 seconds, processing up to 32 inputs per batch.
We aim to reduce the latency and propose LEAF, a low-latency evaluation architecture for the feedforward block. LEAF introduces a novel combination of fast matrix multiplication and an asymptotically efficient algorithm for computing non-polynomial activations. When evaluated on the BERT-base model, LEAF reduces total latency to 53.4 seconds, offering a $100\times$ speedup over the state-of-the-art method in the same environment. Our implementations are available.



## 2025/957

* Title: Laurent Polynomial-Based Linear Transformations for Improved Functional Bootstrapping
* Authors: San Ling, Benjamin Hong Meng Tan, Huaxiong Wang, Allen Siwei Yang
* [Permalink](https://eprint.iacr.org/2025/957)
* [Download](https://eprint.iacr.org/2025/957.pdf)

### Abstract

Following Gentry's seminal work (STOC 2009), Fully Homomorphic Encryption (FHE) has made significant advancements and can even evaluate functions in the bootstrapping process, called functional bootstrapping. Recently, Liu and Wang (ASIACRYPT 2023) proposed a new approach to functional bootstrapping, which bootstrapped ciphertexts in 7ms amortized time. Their methods packed the secret key of the TFHE cryptosystem into a ciphertext of the BFV cryptosystem, followed by performing functional bootstrapping of TFHE within BFV. However, while this yields high amortized efficiency, it faces high latency and computational complexity of $\mathcal{O}(\sqrt{t})$ ciphertext-ciphertext multiplications due to use of large BFV plaintext primes that serve as the TFHE ciphertext modulus, $t = 65537$, to maximize SIMD slots.

In this work, we adapt their techniques to achieve lower latency functional bootstrapping by relaxing the requirement for prime BFV plaintext modulus to prime powers, $t = p^r$. We first introduce an improved linear transformation stage, multiplying Laurent Polynomial packed secret key and ciphertexts, $a_{ij}$ and $sk_j$, evaluating a $\mathbb{Z}_{p^r}$ linear map. With this, we reduce the number of operations needed to evaluate the linear phase of bootstrapping. Finally, we generalize their functional bootstrapping procedure from plaintext space $\mathbb{Z}_t$ to $\mathbb{Z}_{p^r}$ via leveraging the digit extraction algorithm, achieving a theoretical complexity of $\mathcal{O}(r^2\sqrt{p})$ ciphertext-ciphertext multiplications. Additionally, we enable a multi-valued bootstrapping scheme that permits the evaluation of multiple functions over a shared input. To the best of our knowledge, this is the first demonstration of such a method for TFHE ciphertexts that relies predominantly on BFV-based techniques.

In our experiments, we achieve overall runtimes as low as 49.873s, representing latency reductions of at least $26\times$, while noting a $19\times$ slowdown in amortized performance.



## 2025/958

* Title: Efficient Pairings Final Exponentiation Using Cyclotomic Cubing for Odd Embedding Degrees Curves
* Authors: Walid Haddaji, Loubna Ghammam, Nadia El Mrabet, Leila Ben Abdelghani
* [Permalink](https://eprint.iacr.org/2025/958)
* [Download](https://eprint.iacr.org/2025/958.pdf)

### Abstract

In pairings-based cryptographic applications, final exponentiation with a large fixed exponent ensures distinct outputs for the Tate pairing and its derivatives. Despite notable advancements in optimizing elliptic curves with even embedding degrees, improvements for those with odd embedding degrees, particularly those divisible by \(3\), remain underexplored. This paper introduces three methods for applying cyclotomic cubing in final exponentiation and enhancing computational efficiency. The first allows for the execution of one cyclotomic cubing based on the final exponentiation structure. The second leverages some existing seeds structure to enable the use of cyclotomic cubing and extends this strategy to generate new seeds. The third allows generating sparse ternary representation seeds to apply cyclotomic cubing as an alternative to squaring. These optimizations improve performance by up to $19.3\%$ when computing the final exponentiation for the optimal Ate pairing on $BLS15$ and $BLS27$, the target elliptic curves of this study.



## 2025/959

* Title: Zero-Trust Post-quantum Cryptography Implementation Using Category Theory
* Authors: Ilias Cherkaoui, Ciaran Clarke, Jerry Horgan, Indrakshi Dey
* [Permalink](https://eprint.iacr.org/2025/959)
* [Download](https://eprint.iacr.org/2025/959.pdf)

### Abstract

This paper blends post-quantum cryptography (PQC) and zero trust
architecture (ZTA) to secure the access for AI models, formalized through
the abstract mathematical lens of category theory. In this work, latticebased
PQC primitives are assigned ZTA components that include microsegmentation
and context-aware authentication, leading to a visual compositional
framework that describes cryptographic workflows as morphisms
and trust policies as functors, showing how category theory allows for
fine-grained policies and adaptive trust. This quantum-resistant algorithm
viewing perspective offers an ease for protection against adversarial
AI threats. The paper uses a concrete implementation to attest to the
effectiveness of the theoretical contribution, rendering it a crypto-agile
transition using categorical proofs for AI security .



## 2025/960

* Title: A Framework for Advanced Signature Notions
* Authors: Patrick Struck, Maximiliane Weishäupl
* [Permalink](https://eprint.iacr.org/2025/960)
* [Download](https://eprint.iacr.org/2025/960.pdf)

### Abstract

The beyond unforgeability features formalize additional security properties for signature schemes. We develop a general framework of binding properties for signature schemes that encompasses existing beyond unforgeability features and reveals new notions. Furthermore, we give new results regarding various transforms: We show that the transform by Cremers et al. (SP'21) achieves all of our security notions and provide requirements such that this is also the case for the transform by Pornin and Stern (ACNS'05). Finally, we connect our framework to unforgeability notions.



## 2025/961

* Title: Addendum to How Small Can S-boxes Be?
* Authors: Yu Sun, Lixuan Wu, Chenhao Jia, Tingting Cui, Kai Hu, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2025/961)
* [Download](https://eprint.iacr.org/2025/961.pdf)

### Abstract

In ToSC 2025(1), Jia et al. proposed an SAT-aided automatic search tool for the S-box design. A part of the functionality of this tool is to search for implementations of an S-box with good area and gate-depth complexity. However, it is well-known that the gate depth complexity cannot precisely reflect the latency of an implementation. To overcome this problem, Rasoolzadeh introduced the concept of latency complexity, a more precise metric for the latency cost of implementing an S-box than the gate depth complexity in the real world.
In this addendum, we adapt Jia et al.'s tool to prioritize latency as the primary metric and area as the secondary metric to search for good implementations for existing S-boxes. The results show that the combination of Jia et al.'s tool and Rasoolzadeh's latency complexity can lead to lower-latency S-box implementations. For S-boxes used in LBlock, Piccolo, SKINNY-64, RECTANGLE, PRESENT and TWINE, which are popular targets in this research line, we find new implementations with lower latency. We conducted synthesis comparisons of the area and latency under multiple standard libraries, where our results consistently outperformed in terms of latency. For example, for LBlock-S0, our solution reduces latency by around 50.0% ∼73.8% compared to previous implementations in TSMC 90nm library with the latency-optimized synthesis option.



## 2025/962

* Title: An almost key-homomorphic post-quantum block cipher with key rotation and security update for long-term secret storage
* Authors: Thomas Prévost, Bruno Martin, Olivier Alibart
* [Permalink](https://eprint.iacr.org/2025/962)
* [Download](https://eprint.iacr.org/2025/962.pdf)

### Abstract

In this paper, we propose a new block cipher primitive, based on ring-LWE, which allows key rotation with a possible security update. This makes it possible to double the security of the ciphertext with each key rotation. Our scheme could therefore be used for long-term secret storage, allowing the security of the ciphertext to be adapted to the attacker's computing power, without the need for decryption.

We propose an implementation of our cryptographic scheme and prove its security.



## 2025/963

* Title: Permutation-Based Hashing with Stronger (Second) Preimage Resistance - Application to Hash-Based Signature Schemes
* Authors: Siwei Sun, Shun Li, Zhiyu Zhang, Charlotte Lefevre, Bart Mennink, Zhen Qin, Dengguo Feng
* [Permalink](https://eprint.iacr.org/2025/963)
* [Download](https://eprint.iacr.org/2025/963.pdf)

### Abstract

The sponge is a popular construction of hash function design. It operates with a $b$-bit permutation on a $b$-bit state, that is split into a $c$-bit inner part and an $r$-bit outer part. However, the security bounds of the sponge are most often dominated by the capacity $c$: If the length of the digest is $n$ bits, the construction achieves $\min\{n/2,c/2\}$-bit collision resistance and $\min\{n,c/2\}$-bit second preimage resistance (and a slightly more complex but similar bound for preimage resistance). In certain settings, these bounds are too restrictive. For example, the recently announced Chinese call for a new generation of cryptographic algorithms expects hash functions with 1024-bit digests and 1024-bit preimage and second preimage resistance, rendering the classical sponge design basically unusable, except with an excessively large permutation. We present the SPONGE-DM construction to salvage the sponge in these settings. This construction differs from the sponge by evaluating the permutation during absorption in a Davies-Meyer mode. We also present SPONGE-EDM, that evaluates potentially round-reduced permutations during absorption in Encrypted Davies-Meyer mode, and SPONGE-EDM$^c$, that optimizes the amount of feed-forward data in this construction. We prove that these constructions generically achieve $\min\{n/2,c/2\}$-bit collision resistance as the sponge does, but they achieve $n$-bit preimage resistance and $\min\{n,c-\log_2(\alpha)\}$-bit second preimage resistance, where $\alpha$ is the maximum size of the first preimage in blocks. With such constructions, one could improve the security (resp., efficiency) without sacrificing the efficiency (resp., security) of hash-based signature schemes whose security relies solely on the (second) preimage resistance of the underlying hash functions. Also, one could use the $1600$-bit Keccak permutation with capacity $c=1088$ and rate $r=512$ to achieve $512$-bit collision resistance and $1024$-bit preimage and second preimage resistance, without making extra permutation calls. To encourage further cryptanalysis, we propose two concrete families of instances of SPONGE-EDM (expected to be weaker than SPONGE-DM), using SHA3 and Ascon. Moreover, we concretely demonstrate the security and performance advantages of these instances in the context of hashing and hash-based signing.



## 2025/964

* Title: TOOP: A transfer of ownership protocol over Bitcoin
* Authors: Ariel Futoransky, Fadi Barbara, Ramses Fernandez, Gabriel Larotonda, Sergio Lerner
* [Permalink](https://eprint.iacr.org/2025/964)
* [Download](https://eprint.iacr.org/2025/964.pdf)

### Abstract

The Transfer of Ownership Protocol (TOOP) enables a secure transfer of assets from Bitcoin to other blockchains and back. This is achieved through a committee-based validation protocol that requires only 1-out-of-nhonest security. The protocol operates in distinct phases: the lock phase, where the initial setup and individual assets are locked on Bitcoin, and the unlocking with ownership transfer phase, where the asset is transferred to a possibly different legitimate owner. This protocol solves a limitation of all existing BitVM-like protocols that restricts the unlocking transfers to only addresses known and preregistered during lock and setup. Accordingly, our protocol avoids the financially costly, regulatory problematic, and congestion-prone front-and-reimburse paradigm. TOOP has been implemented for the first time in Cardinal, a protocol for wrapping Bitcoin Unspent Transaction Outputs (UTxOs) onto the Cardano blockchain, with Bitcoin Ordinals represented as Cardano Non-Fungible Tokens (NFTs).



## 2025/965

* Title: Multiparty FHE Redefined: A Framework for Unlimited Participants
* Authors: Robin Jadoul, Barry van Leeuwen, Oliver Zajonc
* [Permalink](https://eprint.iacr.org/2025/965)
* [Download](https://eprint.iacr.org/2025/965.pdf)

### Abstract

Multiparty fully homomorphic encryption (MPFHE) is a generalization of (multi-key) fully homomorphic encryption ((MK)FHE) that lives on the cusp between multiparty computation (MPC) and FHE, enabling a computation over encrypted data using multiple keys. However, contrary to MKFHE it seeks to reduce the noise inflation based on the number of parties by allowing the parties to first compute shared data in MPC before executing the computation in FHE. Generally, MPFHE protocols have required ad-hoc constructions and adaptations to already existing protocols. In this work we present a new framework that standardizes the approach of MPFHE to allow the use of a broad spectrum of MPC and FHE protocols, while eliminating the noise inflation based on the participating number of parties. This presents the first ever multiparty FHE protocol which allows an arbitrary number of participants. We then show a case study of this using the FINAL scheme and show that we reduce the required key material by 40-99.9% compared to the MKFHE FINAL scheme, FINALLY, 8-71% compared to the AKÖ scheme, and 65-70% compared to the Park-Rovira scheme. Moreover, we reduce the bootstrapping time for the AKÖ, Park-Rovira, and KMS schemes by 75-99.7%.



## 2025/966

* Title: Multiparty Homomorphic Secret Sharing and More from LPN and MQ
* Authors: Geoffroy Couteau, Naman Kumar, Xiaxi Ye
* [Permalink](https://eprint.iacr.org/2025/966)
* [Download](https://eprint.iacr.org/2025/966.pdf)

### Abstract

We give the first constructions of multiparty pseudorandom correlation generators, distributed point functions, and (negligible-error) homomorphic secret sharing for constant-degree polynomials for any number of parties without using LWE or iO. Our constructions are proven secure under the combination of LPN with dimension $n$, $2n$ samples, and noise rate $n^{\varepsilon-1}$ for a small constant $\varepsilon$, and MQ with $n$ variables and $n^{1+\delta}$ equations.

As applications of our results, we obtain from the same assumptions secure multiparty computation protocols with sublinear communication and silent preprocessing, as well as private information retrieval for $M$ servers and size-$\lambda^d$ databases with optimal download rate and client-to-server communication $M^d\cdot \lambda^3$.



## 2025/967

* Title: Registered Functional Encryption for Pseudorandom Functionalities from Lattices: Registered ABE for Unbounded Depth Circuits and Turing Machines, and More
* Authors: Tapas Pal, Robert Schädlich, Erkan Tairi
* [Permalink](https://eprint.iacr.org/2025/967)
* [Download](https://eprint.iacr.org/2025/967.pdf)

### Abstract

Registered functional encryption (RFE) is a generalization of public-key encryption that enables computation on encrypted data (like classical FE), but without needing a central trusted authority. Concretely, the users choose their own public keys and register their keys together with a function with an (untrusted) key curator. The key curator aggregates all of the individual public keys into a short master public key, which serves as the public key of the FE scheme.

Currently, we only know RFE constructions for restricted functionalities using standard assumptions, or for all circuits using powerful tools such as indistinguishability obfuscation, and only in the non-uniform model. In this work, we make progress on this front by providing the first lattice-based constructions of RFE for pseudorandom functionalities, where the model of computation is either non-uniform (unbounded depth circuits) or uniform (Turing machines). Intuitively, we call a functionality pseudorandom if the output of the circuit is indistinguishable from uniform for every input seen by the adversary.. Security relies on LWE and a recently introduced primitive called pseudorandom FE (prFE), which currently can be instantiated from evasive LWE.

We illustrate the versatility of these new functionalities for RFE by leveraging them to achieve key-policy and ciphertext-policy registered attribute-based encryption and registered predicate encryption schemes (KP-RABE, CP-RABE and RPE) for both unbounded depth circuits and Turing machines. Existing RABE constructions support only bounded depth circuits, and prior to our work there neither existed RABE for uniform models of computation nor RPE. As an appealing feature, all our constructions enjoy asymptotic optimality in the sense that their parameters depend neither on the length of public attributes nor the size of policies.

Along the way, we can also improve on the state-of-the-art for classical attribute-based encryption (ABE) and predicate encryption (PE). Specifically, we obtain new constructions for KP-ABE, CP-ABE and PE for Turing machines with optimal asymptotic parameters. For KP-ABE, this is an in improvement in terms of efficiency, whereas for CP-ABE and PE we are not aware of any prior purely lattice-based construction supporting Turing machines.



## 2025/968

* Title: Learning with Alternating Moduli, Arora-Ge over Composite Moduli, and Weak PRFs
* Authors: Yilei Chen, Liheng Ji, Wenjie Li
* [Permalink](https://eprint.iacr.org/2025/968)
* [Download](https://eprint.iacr.org/2025/968.pdf)

### Abstract

In TCC 2018, Boneh, Ishai, Passelègue, Sahai, and Wu propose candidates of weak and strong PRFs by evaluating linear functions over coprime moduli alternatively. Such PRFs can be evaluated by low-depth circuits and are MPC-friendly. However, they have not been able to base the security of their PRFs on well-formed assumptions other than assuming that the PRF constructions themselves are secure. 

In this paper, we formalize a new assumption called Learning with Alternating Moduli (LAM). We show that over certain large moduli, the LAM assumption is as hard as the Learning with Errors (LWE) assumption. For LAM over constant moduli, we do not know how to base its hardness on the LWE assumption. Instead, we provide
    (i) polynomial-time attacks on LAM with constant prime-power moduli and certain constant non-prime-power moduli, and
    (ii) evidence of the sub-exponential hardness of LAM with other moduli by analyzing the effect of typical attacks.

More specifically, we put forward two new attacks. The first attack is a recursive algorithm that solves LWE with certain constant composite moduli and error distributions. The algorithm extends the Arora-Ge algorithm for LWE from prime moduli to composite moduli, and it also solves LAM for certain parameters. The second attack is a polynomial-time attack that rules out the existence of weak PRFs in $\mathsf{NC}^0[p]$ for any prime $p$.

Based on our studies, we propose candidate weak PRFs in $\mathsf{NC}^0[p_1,p_2]$ for some distinct primes $p_1,p_2$ based on LAM over constant moduli, or the Learning with Rounding (LWR) assumption over constant moduli. Compared to the weak PRF candidates by Boneh et al., our weak PRF candidates live in the same complexity class while having the advantage of being based on well-formed assumptions.



## 2025/969

* Title: Decentralized Data Archival: New Definitions and Constructions
* Authors: Elaine Shi, Rose Silver, Changrui Mu
* [Permalink](https://eprint.iacr.org/2025/969)
* [Download](https://eprint.iacr.org/2025/969.pdf)

### Abstract

We initiate the study of a new abstraction
called incremental decentralized data archival (${\sf iDDA}$).
Specifically, imagine that there is an ever-growing, massive database such as a blockchain, a comprehensive  human knowledge base like Wikipedia,  or the Internet archive.  We want to build a decentralized archival of such datasets
to ensure long-term robustness and sustainability. 

We identify several important properties
that an ${\sf iDDA}$ scheme should satisfy. First,
to promote heterogeneity and decentralization,
we want to encourage even weak nodes  with limited space (e.g., users' home computers) to contribute.  The minimum space requirement to contribute should be approximately independent of the data size.   Second, if a collection of nodes together receive rewards commensurate with contributing a total of $m$ blocks of space, then we want the following reassurances:  1) if $m$ is at least the database size, we should be able to reconstruct the entire dataset; and 2)  these nodes should actually be commiting roughly $m$ space in aggregate --- even when $m$ is much larger than the data size,  the nodes should be storing redundant copies of the database rather than storing just one copy, and yet impersonating arbitrarily many pseudonyms to get unbounded rewards. 

We propose new definitions  that mathematically formalize the aforementioned requirements of an ${\sf iDDA}$ scheme.
We also devise an efficient construction in the random oracle model which satisfies the desired security requirements.   Our scheme incurs  only $\widetilde{O}(1)$ audit cost, as well as  $\widetilde{O}(1)$ update cost for both the publisher and each node, where $\widetilde{O}(\cdot)$ hides polylogarithmic factors. Further, the minimum space provisioning required to contribute is as small as polylogarithmic.

Our construction exposes several interesting technical challenges. Specifically, we show that a straightforward application of the standard hierarchical data structure fails, since both our security definition and  the underlying cryptographic primitives we employ lack the desired compositional  guarantees. We devise novel techniques to overcome these compositional issues, resulting in a construction with provable security while still retaining efficiency. Finally, our new definitions also make a conceptual contribution, and lay the theoretical groundwork for the study of ${\sf iDDA}$.   We raise several interesting open problems along this direction.



## 2025/970

* Title: How to Verify that a Small Device is Quantum, Unconditionally
* Authors: Giulio Malavolta, Tamer Mour
* [Permalink](https://eprint.iacr.org/2025/970)
* [Download](https://eprint.iacr.org/2025/970.pdf)

### Abstract

A proof of quantumness (PoQ) allows a classical verifier to efficiently test if a quantum machine is performing a computation that is infeasible for any classical machine. In this work, we propose a new approach for constructing PoQ protocols where soundness holds unconditionally assuming a bound on the memory of the prover, but otherwise no restrictions on its runtime. In this model, we propose two protocols:
    1. A simple protocol with a quadratic gap between the memory required by the honest parties and the memory bound of the adversary. The soundness of this protocol relies on Raz's (classical) memory lower bound for matrix inversion (Raz, FOCS 2016).
    2. A protocol that achieves an exponential gap, building on techniques from the literature on the bounded storage model (Dodis et al., Eurocrypt 2023).

Both protocols are also efficiently verifiable. Despite having worse asymptotics, our first protocol is conceptually simple and relies only on arithmetic modulo 2, which can be implemented with one-qubit Hadamard and CNOT gates, plus a single one-qubit non-Clifford gate.



## 2025/971

* Title: Sabot: Efficient and Strongly Anonymous Bootstrapping of Communication Channels
* Authors: Christoph Coijanovic, Laura Hetz, Kenneth G. Paterson, Thorsten Strufe
* [Permalink](https://eprint.iacr.org/2025/971)
* [Download](https://eprint.iacr.org/2025/971.pdf)

### Abstract

Anonymous communication is vital for enabling individuals to participate in social discourse without fear of marginalization or persecution. An important but often overlooked part of anonymous communication is the bootstrapping of new communication channels, generally assumed to occur out-of-band. However, if the bootstrapping discloses metadata, communication partners are revealed even if the channel itself is fully anonymized. We propose Sabot, the first anonymous bootstrapping protocol that achieves both strong cryptographic privacy guarantees and bandwidth-efficient communication. In Sabot, clients cooperatively generate a private relationship matrix, which encodes who wants to contact whom. Clients communicate with k ≥ 2 servers to obtain “their” part of the matrix and augment the received information using Private Information Retrieval (PIR) to learn about their prospective communication partners. Compared to previous solutions, Sabot achieves stronger privacy guarantees and reduces the bandwidth overhead by an order of magnitude.



## 2025/972

* Title: Generalized BGV, BFV, and CKKS for Homomorphic Encryption over Matrix Rings
* Authors: Bence Mali
* [Permalink](https://eprint.iacr.org/2025/972)
* [Download](https://eprint.iacr.org/2025/972.pdf)

### Abstract

Some of the most valuable applications of homomorphic encryption, such as encrypted machine learning inference, require efficient large-scale plaintext-ciphertext and ciphertext-ciphertext matrix multiplications. Current state-of-the-art techniques for matrix multiplications all build on the ability to pack many ciphertexts into a ciphertext and compute on them in a Single Instruction, Multiple Data (SIMD) manner. However, to fit the operation of matrix multiplication into this computational model, a large number of additional costly operations need to be performed, such as the rotation of elements between the plaintext slots.

In this work, we propose an orthogonal approach to performing encrypted matrix operations with BGV-like encryption schemes, where the plaintext and ciphertext spaces are generalized to a matrix ring of arbitrary dimension. To deal with the inherent problem of noncommutativity in the case of matrix rings, we present a new superoperator technique to better represent linear and quadratic expressions in the secret key, which allows for the relinearization of ciphertexts after multiplication. The security of the modified encryption schemes is based on Module-LWE with module rank equal to the dimension of the matrices. With this construction, we demonstrate that Ring-LWE, Module-LWE, and LWE are potentially equally efficient for homomorphic encryption, both in terms of useful information density and noise growth, only for different sizes of matrices.



## 2025/973

* Title: On Proving Equivalence Class Signatures Secure from Non-interactive Assumptions
* Authors: Balthazar Bauer, Georg Fuchsbauer, Fabian Regen
* [Permalink](https://eprint.iacr.org/2025/973)
* [Download](https://eprint.iacr.org/2025/973.pdf)

### Abstract

Equivalence class signatures (EQS), introduced by Hanser
and Slamanig (AC’14, J.Crypto’19), sign vectors of elements from a bi-
linear group. Their main feature is “adaptivity”: given a signature on a
vector, anyone can transform it to a (uniformly random) signature on any
multiple of the vector. A signature thus authenticates equivalence classes
and unforgeability is defined accordingly. EQS have been used to improve
the efficiency of many cryptographic applications, notably (delegatable)
anonymous credentials, (round-optimal) blind signatures, group signa-
tures and anonymous tokens. EQS security implies strong anonymity
(or blindness) guarantees for these schemes which hold against malicious signers without trust assumptions.

Unforgeability of the original EQS construction is proven directly in
the generic group model. While there are constructions from standard
assumptions, these either achieve prohibitively weak security notions
(PKC’18) or they require a common reference string (AC’19, PKC’22),
which reintroduces trust assumptions avoided by EQS.

In this work we ask whether EQS schemes that satisfy the original secu-
rity model can be proved secure under standard (or even non-interactive)
assumptions with standard techniques. Our answer is negative: assum-
ing a reduction that, after running once an adversary breaking unforge-
ability, breaks a non-interactive computational assumption, we construct
efficient meta-reductions that either break the assumption or break class-
hiding, another security requirement for EQS.