## 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.


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)