Breaking Poseidon Challenges with Graeffe Transforms and Complexity Analysis by FFT Lower Bounds

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 improve 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 pseudolinear 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.

Keywords: Poseidon, Graeffe transform, interpolation attack, root finding, FFT lower bounds, zero-knowledge proofs

1. Introduction

Cryptographic hash functions are fundamental to modern cryptography. With the rise of advanced applications such as zero-knowledge proofs, especially STARK protocols [BBHR19], there is a growing demand for hash functions that are efficient not only on conventional hardware but also when represented as arithmetic circuits over large prime fields. While general designs like SHA-2 and SHA-3 are highly optimized for modern CPUs, they cannot be represented as small arithmetic circuits, which essentially becomes a bottleneck for the performance of proof systems. As a result, several new so-called STARK-friendly or arithmetization-oriented constructions have been proposed, including Rescue-Prime [SAD20,AKM+22], Feistel-MiMC [AGR+16], Poseidon [GKR+21], and Reinforced Concrete [GKL+22]. Among these, Poseidon and its successor Poseidon2 [GKS23] have emerged as top performers in recent STARK benchmarks by StarkNet, making them promising candidates for use in Ethereum and other applications that require efficient and verifiable computation.

However, unlike classic hash functions such as SHA-2 and SHA-3, which have been thoroughly analyzed over decades, these STARK-friendly constructions are relatively recent and lack extensive cryptanalysis. Their security cannot be directly inferred from traditional designs. The best known attacks are also quite different: instead of relying on differential path search, they often exploit the algebraic structure of these hash functions.

The participants in the Ethereum Foundation’s bounty program are required to solve the CICO (Constrained Input, Constrained Output) problems for the inner sponge permutation (denoted by Perm) under different Poseidon parameterizations. The CICO problem asks for input and output pairs such that the last several elements in both are zero. For example, Poseidon-64 asks for X_0, \ldots, X_6, Y_0, \ldots, Y_6 such that \mathsf{Perm}(X_0, \ldots, X_6, 0) = (Y_0, \ldots, Y_6, 0).

Currently, the most effective attack against Poseidon is the interpolation attack [JK97]. The interpolation attack first fixes X_1, \ldots, X_6 to random values. Then, the mapping from X_0 to the last coordinate of \mathsf{Perm}(X_0, \ldots, X_6, 0) becomes a univariate polynomial. In practice, these univariate polynomials typically have roots with high probability, so solutions to the CICO problem can be found by univariate polynomial root finding.

The Graeffe Transform. Historically, the Graeffe transform dates back to the 1820s–1830s, with independent contributions from Dandelin, Lobachevsky, and Gräffe [Hou59]. It was originally designed for finding roots of real polynomials by mapping each root to its square, effectively spreading the roots apart and making them easier to find numerically.

Suppose f(x) is a degree-d polynomial with roots r_1, \ldots, r_d \in \mathbb{R}, ordered so that |r_0| > |r_1| > \cdots > |r_{d-1}|. The Graeffe transform of f(x), denoted by \mathsf{GT}_2(f), is defined such that

This construction yields a new polynomial whose roots are exactly r_0^2, r_1^2, \ldots, r_{d-1}^2. By applying the Graeffe transform v times, one obtains a polynomial whose roots are r_0^{2^v} \gg r_1^{2^v} \gg \cdots \gg r_{d-1}^{2^v}. By Vieta’s formulas, the coefficients approximately yield the original roots.

Contribution. This work improves the most time-consuming root finding step of the interpolation attack by using the Graeffe transform. Suppose \omega_\ell is a primitive \ell-th root of unity in the underlying field. Given a polynomial f, the Graeffe transform \mathsf{GT}_\ell computes a new polynomial g = \mathsf{GT}_\ell(f) such that g(x^\ell) = f(x)f(x\omega_\ell^1) \cdots f(x\omega_\ell^{\ell-1}). If f has a root x_0 \in \mathbb{F}_p and \ell divides |\mathbb{F}_p^\times|, then x_0^\ell will be a root of g which lies in a subgroup of \mathbb{F}_p^\times of size (p-1)/\ell. By taking a large enough \ell, x_0^\ell can be found easily by enumeration, from which we can recover x_0.

Compared to the previous record in [BBLP22], the implementation is about 2^{13} times faster in wall time and uses 2^{4.5} times less memory. With this, the authors were able to solve the previously unsolved 24-bit, 28-bit, and 32-bit Poseidon-64 challenges, corresponding to polynomials of degree 7^{12}, 7^{13}, and 7^{15}, respectively.

Roadmap. Section 2 reviews background on the Poseidon permutation and introduces the Skip First Rounds Trick. Section 3 details the Graeffe transform and its application to univariate polynomial root finding. Section 4 describes the implementation and presents performance results, including a discussion on security. Section 5 proves an asymptotic lower bound for the memory access cost during FFT. Section 6 concludes.

2. Preliminaries

2.1 Notations

All indices start from 0. Bold uppercase letters denote matrices, while bold lowercase letters denote vectors. The i-th entry of a vector \mathbf{v} is written as v_i, and the (i, j)-th position of a matrix \mathbf{M} is \mathbf{M}_{i,j}. We denote by \mathbb{F}_p the prime field with p elements, and by \mathbb{F}_p^\times its multiplicative group. When the underlying field is clear, we denote the cost of multiplying two degree-d polynomials by \mathsf{M}(d).

Throughout the paper, the following primes are used:

to denote the Goldilocks prime and BLS12-381, respectively.

2.2 The Poseidon Permutation and the CICO Problem

The Poseidon2 sponge permutation is based on the HADES [GLR+20] design strategy. After the input (x_0, \ldots, x_{t-1}) \in \mathbb{F}_p^t is transformed by the matrix \mathbf{M}_{\mathcal{E}}, the permutation proceeds by applying R_F/2 full rounds, R_P partial rounds, and then another R_F/2 full rounds. Each RC gate represents the addition of a round constant. The S-box S is the power map x \mapsto x^\alpha, where \alpha is chosen as the smallest integer greater than 1 such that the S-box is invertible. During the partial rounds, the S-box and RC gates only apply to the first state.

For the Poseidon-64 challenges, the linear transformations are taken to be specific matrices \mathbf{M}_{\mathcal{E}} and \mathbf{M}_{\mathcal{I}}, where (\mathbf{M}_{\mathcal{I}})_{i,j} = 1 + \mu_i if i = j and 1 otherwise.

The Poseidon-64 and Poseidon-256 challenge instances have u = 1, which means we only require the last coordinate of both the input and output to be zero.

The differences between Poseidon and Poseidon2 are: (a) Poseidon does not apply the initial linear transform before the first round; (b) Poseidon uses the same MDS matrix for all rounds; (c) for the partial rounds, Poseidon also applies the RC gates to all states.

2.3 Skip First Rounds Trick

This subsection provides a brief review of the Skip First Rounds Trick from [BBLP22], which was also used in the challenges. For simplicity, the focus is on the case of Poseidon-64. This technique reduces the polynomial degree by a factor of \alpha for Poseidon2 and by \alpha^2 for Poseidon, respectively. The impact is less significant for Poseidon2, owing to the presence of the initial linear transformation—this is precisely why [GKS23] introduced the initial linear transform in the first place.

Let the last row of (\mathbf{M}_{\mathcal{E}})^{-1} be (\lambda_0, \ldots, \lambda_{t-1}). Then, (y_0, \ldots, y_{t-1}) corresponds to an input whose last coordinate is zero if and only if

Under appropriate choices of the variables, the permutation becomes a univariate polynomial in y_0 of degree \alpha^{R_F + R_P - 1}. Finding the roots of this polynomial gives a solution to the CICO problem, so the polynomial degree can be reduced by a factor of \alpha.

3. Root Finding for Univariate Polynomials

This section first reviews current polynomial solving methods for practical attacks on STARK-friendly hash functions, then presents the Graeffe transform-based algorithm in detail, with a focus on the Goldilocks field.

3.1 GCD-Based Methods

The polynomials that appear in interpolation attacks usually have only a few roots in the underlying field, much like random polynomials. This allows the use of the following GCD-based root finding approach, which was used to set the Poseidon interpolation record [BBLP22].

If f(x) is a polynomial of degree d over \mathbb{F}_p, the GCD-based approach first replaces f(x) with its GCD with the Frobenius polynomial x^p - x, reducing the problem to the case where f(x) is split over \mathbb{F}_p, then finds the roots by the Berlekamp algorithm [Ber71] or the Cantor–Zassenhaus algorithm [CZ81].

Before the GCD computation, since f(x) usually has degree much less than x^p - x, it will be helpful to compute g(x) = x^p - x \mod f(x) using the square-and-multiply method, requiring O(\log p) modular polynomial multiplications for a total cost of O(\log(p) \mathsf{M}(d)). The GCD itself can be computed by the Half-GCD algorithm in O(\log(n) \mathsf{M}(d)), but this step is the most troublesome part of the root finding process.

The GCD computation is unattractive for several reasons: (a) the Half-GCD algorithm is highly sequential, making it notoriously difficult to parallelize; (b) the constant factor is quite large (bounded by 22 \log(n) \mathsf{M}(d) in the original paper [Moe73]); and (c) the recursive form is extremely painful to implement, especially with large memory or GPU parallelism.

3.2 Root Finding via Graeffe Transform

Proof. Let h(x) = f(x)f(x\omega_\ell^1) \cdots f(x\omega_\ell^{\ell-1}). By construction, h(x) is invariant under the substitution x \mapsto x\omega_\ell, which multiplies the coefficient of x^i by \omega_\ell^i. Thus, the coefficients of x^i in h(x) can be nonzero only if \omega_\ell^i = 1, i.e., i is a multiple of \ell. Therefore, the existence of g(x) is guaranteed, and the degree of g(x) is \deg(h(x))/\ell = d. The coefficients lie in \mathbb{F}_p because each coefficient of h(x) is fixed under any Galois conjugation.

Proof. Suppose \omega is a primitive \ell_0 \ell_1-th root of unity. Then \omega^{\ell_1} is a primitive \ell_0-th root of unity, and \omega^{\ell_0} is a primitive \ell_1-th root of unity. By the definition of the Graeffe transform:

Lemma 2 allows the Graeffe transform of large order \ell to be computed by successively applying Graeffe transforms of smaller orders. This can be done effectively when \ell is smooth, which is exactly the case for the challenges solved.

For \ell = 2, if f(x) = f_0(x^2) + x f_1(x^2), then

Therefore, the Graeffe transform of order 2 is given by \mathsf{GT}_2(f) = f_0(x)^2 - x f_1(x)^2. This can be computed using two FFTs and one invFFT with FFT group size at least d, costing only \mathsf{M}(d/2).

For \ell \geqslant 3, the recursive method from [GHL15] is used. If P_h(x) is the product P_h(x) = f(x)f(x\omega_\ell^1) \cdots f(x\omega_\ell^{h-1}), then it suffices to compute P_\ell(x) recursively:

The paper presents Algorithm 2 for root finding over the Goldilocks field. The algorithm successively applies Graeffe transforms of orders matching the factorization p_{64} - 1 = 2^{32} \cdot 3 \cdot 5 \cdot 17 \cdot 257 \cdot 65537. First, repeated \mathsf{GT}_2 operations are applied while \beta is even, then \mathsf{GT}_3, \mathsf{GT}_5, \mathsf{GT}_{17}, and \mathsf{GT}_{257} are applied in sequence. Once the polynomial degree is small enough, roots are found by enumeration, and then the original root is recovered by backtracking through each Graeffe step.

The overall cost of the algorithm is estimated to be approximately (\log_2(p_{64}) - \log_2(d) + 1) \mathsf{M}(d/2). The constant factor is much smaller than that of GCD-based methods, which is part of the reason for the speedup.

The numbers 2, 3, 5, 17, 257 in Algorithm 2 exactly correspond to the factorization of p_{64} - 1. The algorithm can be adapted to other prime fields, as long as the multiplicative group size of the field is smooth enough. For instance:

4. Implementation and Security Estimation

4.1 Implementation Details

The Graeffe transform-based algorithm was implemented in C++ with CUDA, with about 4k–5k lines in total. The code uses a modular design which decouples memory management, polynomial algorithms, and field arithmetic. It can be adapted to other 64-bit prime fields by changing the FFT group choice and field arithmetic code as long as the multiplicative group size is smooth enough. With this implementation, the 24-, 28-, and 32-bit Poseidon-64 challenges were solved, corresponding to polynomial degrees 7^{12}, 7^{13}, and 7^{15}, respectively.

Architecture. The code was developed on a dual-socket Intel Xeon Platinum 8474C server equipped with several Nvidia RTX 4090 graphics cards. Each card is connected to the system’s 2TB RAM via a PCIe 4.0 interface, providing a unidirectional bandwidth of roughly 200 GiB/s in total under real-world conditions. Almost no low-level optimization of finite field arithmetic or FFT routines was performed for GPU or CPU architectures; the performance is mainly determined by memory bandwidth rather than compute throughput.

Memory Issue. Even after significant improvements to the root finding algorithm, the “32-bit” challenge still takes several days. For other well-known hard problems (lattice problems, multivariate polynomial system solving, or decoding [ALM19]), it is typically feasible to solve instances up to 60 or even 70 “bits.” This suggests that the Poseidon interpolation attack has some inherent hardness, and that previous security estimates might have been somewhat too conservative.

Performance. Compared with previous GCD-based results in [BBLP22], for degrees 7^{12} and 7^{13}, the new result is about 10,000 times faster and uses only 4% to 5% of the memory. For 7^{15}, although swapping data to disk causes some slowdown, the method is still about 6,000 times faster than the previous result.

4.2 Security Estimation

Based on the implementation results, a security estimation for the interpolation attack is provided. The focus is on the “128-bit” instance of Poseidon, where the prime field size is p_{255}. The central question is how to quantify the impact of memory access on the attack.

Using the physical fact that the cost of moving information is at least proportional to the distance it travels, the paper proves in Theorem 1 that the memory access cost for executing FFT is at least proportional to the 4/3-power of the input size. Based on this, the root finding cost is modeled as scaling with the 4/3-power of the polynomial degree.

For 128-bit security, the estimation script gives round numbers R_F = 8, R_P = 56, corresponding to a polynomial degree of 5^{63} using the Skip First Rounds Trick. The attack cost is estimated as:

SHA-256 permutations. So the current parameter choice looks somewhat conservative, and it may be tempting to reduce the number of rounds for better efficiency.

It is crucial to remark that this estimation applies only when a single zero is required in both the input and output of the sponge permutation. Otherwise, the best known attack would involve multivariate polynomial solving, where the main bottleneck is linear algebra over finite fields and memory cost is less relevant.

5. Memory Access Lower Bounds for FFT

This section proves a lower bound for the data movement cost of the fast Fourier transform. Specifically, it shows that any arithmetic circuit corresponding to the FFT algorithm, regardless of how it is realized in three-dimensional space, will require information to travel a total distance roughly proportional to the 4/3-power of the input size. The proof makes use of two physical facts.

To prove the theorem, the paper first introduces the Directed Acyclic Graph (DAG) for the FFT circuit. The DAG consists of n input nodes and n output nodes. A directed edge v_i \to v_j indicates that the value at node v_j (linearly) depends on the value at node v_i.

The nodes are labeled v_{i,0}, v_{i,1}, \ldots, v_{i,e_2} for i = 0, \ldots, n-1. From each node v_{i,s} with 0 \leqslant s < e_2, there are two directed edges: one to v_{i,s+1} and one to v_{i \oplus 2^{e_2-1-s}, s+1}.

Proof. For each i_0 \in \{0, \ldots, n-1\} with i_0 < i_0 \oplus 2^r, a subgraph G_{i_0} = (V_{i_0}, E_{i_0}) of the DAG is constructed:

By construction, the images for different i_0 are pairwise disjoint. The memory movement cost within G_{i_0} is at least \|\mathbf{p}(i_0) - \mathbf{p}(i_0 \oplus 2^r)\| by the triangle inequality, since both output nodes are endpoints of directed paths starting from the same node.

Proof. By Fact 2, there exists a constant C_0 such that there are at most C_0 R^3 field elements stored within any ball of radius R. For each i:

The proof concludes by taking the sum over all 0 \leqslant i \leqslant n - 1.

Proof. Let S(r) = \sum_{i \in \{0,\ldots,n-1\}, i < i \oplus 2^r} \|\mathbf{p}(i) - \mathbf{p}(i \oplus 2^r)\|. Let r_0 be such that S(r_0) is the largest among S(0), \ldots, S(e_2 - 1). Using the triangle inequality and the binary representation of j:

as desired.

Proof of Theorem 1. Combining Lemma 3, Lemma 4, and Lemma 5: there exists an r such that the memory movement cost is at least S(r) \geqslant \frac{1}{n e_2} \cdot \mathcal{O}(n^{7/3}) = \tilde{\mathcal{O}}(n^{4/3}), since e_2 = \log_2 n.

6. Conclusions

The paper presents a Graeffe transform-based algorithm for root finding over finite fields, used to solve several Poseidon challenges from the Ethereum Foundation. The results show a speedup of several orders of magnitude over previous methods, while using only about 4–5% of the memory. Based on these results, a security estimate for interpolation attacks with the current proposed parameters is provided. In particular, it is proven that the FFT algorithm incurs a memory access cost proportional to the 4/3-power of the input size, up to logarithmic factors, which differs from previous analyses using hierarchical memory models.

A few points are worth highlighting. First, these results apply only to the classical setting; the quantum resistance of root finding in interpolation attacks, or other potential attacks, remains unclear compared to the well-established hardness of problems used in post-quantum cryptography.

Moreover, FFTs are also used in other cryptanalytic contexts. For example, certain dual lattice attacks on LWE [MAT22] use FFTs to accelerate the distinguishing step. The lower bound for FFTs derived here may be relevant in those settings as well, indicating that some attack complexity estimates in the literature may be overly optimistic.

Acknowledgements

The authors would like to thank the Ethereum Foundation for launching the Poseidon bounty program, which is the initial motivation and starting point for this research. On May 22nd, about one month after submitting the first bounty instance, the report and code were sent to the Ethereum Foundation and later the authors were informed about ongoing parallel work by Antonio Sanso (Ethereum Foundation Poseidon Group) and Giuseppe Vitto [SV25], who independently studied a similar idea. While their work places more emphasis on the tangent Graeffe Transform, this paper provides a complexity analysis based on FFT lower bounds. In the case of Poseidon-64, the results are roughly two orders of magnitude faster.

References

• [ACG+19] Albrecht, M.R., Cid, C., Grassi, L., Khovratovich, D., Lüftenegger, R., Rechberger, C., Schofnegger, M.: “Algebraic cryptanalysis of STARK-friendly designs: Application to MARVELlous and MiMC.” In: ASIACRYPT 2019, pp. 371–397. Springer (2019). doi: 10.1007/978-3-030-34618-8_13.
• [AGR+16] Albrecht, M.R., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: “MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity.” In: ASIACRYPT 2016, Part I. Vol. 10031. LNCS. Springer (2016), pp. 191–219. doi: 10.1007/978-3-662-53887-6_7.
• [ALM19] Aragon, N., Lavauzelle, J., Lequesne, M.: decodingchallenge.org (2019). decodingchallenge.org.
• [AD18] Ashur, T., Dhooghe, S.: “MARVELlous: a STARK-friendly family of cryptographic primitives.” Cryptology ePrint Archive, Paper 2018/1098 (2018). eprint.iacr.org/2018/1098.
• [AKM+22] Ashur, T., Kindi, A., Meier, W., Szepieniec, A., Threadbare, B.: “Rescue-Prime Optimized.” Cryptology ePrint Archive, Paper 2022/1577 (2022). eprint.iacr.org/2022/1577. [page on this site]
• [BBO+24] Bariant, A., Boeuf, A., Lemoine, A., Manterola Ayala, I., Øygarden, M., Perrin, L., Raddum, H.: “The algebraic freelunch: Efficient Gröbner basis attacks against arithmetization-oriented primitives.” In: CRYPTO 2024, pp. 139–173. Springer (2024). doi: 10.1007/978-3-031-68385-5_5.
• [BBLP22] Bariant, A., Bouvier, C., Leurent, G., Perrin, L.: “Algebraic attacks against some arithmetization-oriented primitives.” IACR Trans. Symmetric Cryptol. 2022(3), 73–101 (2022). doi: 10.46586/tosc.v2022.i3.73-101.
• [BBHR19] Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: “Scalable zero knowledge with no trusted setup.” In: CRYPTO 2019, Part III, pp. 701–732. Springer (2019). doi: 10.1007/978-3-030-26954-8_23.
• [BCKL] Ben-Sasson, E., Carmon, D., Kopparty, S., Levit, D.: “Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Low-degree Extension in Time O(n \log n) over all Finite Fields.” SIAM.
• [Ber71] Berlekamp, E.R.: “Factoring polynomials over large finite fields.” In: SYMSAC ’71. ACM (1971). doi: 10.1145/800204.806290.
• [Bes49] Best, G.C.: “Notes on the Graeffe method of root squaring.” The American Mathematical Monthly 56(2), 91–94 (1949).
• [BS24] Brodetsky, S., Smeal, G.: “On Graeffe’s method for complex roots of algebraic equations.” Math. Proc. Cambridge Phil. Soc. 22(2), 83–87 (1924). doi: 10.1017/S0305004100002802.
• [Buc06] Buchberger, B.: “Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal.” J. Symbolic Comput. 41(3), 475–511 (2006). doi: 10.1016/j.jsc.2005.09.007.
• [BDMM09] Buchmann, J.A., Ding, J., Mohamed, M.S.E., Mohamed, W.S.A.E.: “MutantXL: Solving multivariate polynomial equations for cryptanalysis.” In: Symmetric Cryptography (2009).
• [CZ81] Cantor, D.G., Zassenhaus, H.: “A new algorithm for factoring polynomials over finite fields.” Math. Comp. 36, 587–592 (1981).
• [EF24] Ethereum Foundation: “Poseidon cryptanalysis initiative 2024–2026.” poseidon-initiative.info (2024).
• [FGLM93] Faugère, J., Gianni, P., Lazard, D., Mora, T.: “Efficient computation of zero-dimensional Gröbner bases by change of ordering.” J. Symbolic Comput. 16(4), 329–344 (1993). doi: 10.1006/jsco.1993.1051.
• [Fau99] Faugère, J.C.: “A new efficient algorithm for computing Gröbner bases (F4).” J. Pure Appl. Algebra 139(1), 61–88 (1999). doi: 10.1016/S0022-4049(99)00005-5.
• [GKL+22] Grassi, L., Khovratovich, D., Lüftenegger, R., Rechberger, C., Schofnegger, M., Walch, R.: “Reinforced Concrete: A fast hash function for verifiable computation.” In: CCS ’22. ACM (2022), pp. 1323–1335. doi: 10.1145/3548606.3560686. [page on this site]
• [GKR+21] Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: “Poseidon: A new hash function for Zero-Knowledge proof systems.” In: 30th USENIX Security Symposium. USENIX Association (Aug 2021), pp. 519–535. usenix.org. [page on this site]
• [GKS23] Grassi, L., Khovratovich, D., Schofnegger, M.: “Poseidon2: A faster version of the Poseidon hash function.” Cryptology ePrint Archive, Paper 2023/323 (2023). eprint.iacr.org/2023/323. [page on this site]
• [GLR+20] Grassi, L., Lüftenegger, R., Rechberger, C., Rotaru, D., Schofnegger, M.: “On a generalization of substitution-permutation networks: The HADES design strategy.” In: EUROCRYPT 2020, Part II. Springer (2020), pp. 674–704. doi: 10.1007/978-3-030-45724-2_23. [page on this site]
• [GHL15] Grenet, B., van der Hoeven, J., Lecerf, G.: “Randomized root finding over finite FFT-fields using tangent Graeffe transforms.” In: ISSAC ’15. ACM (2015), pp. 197–204. doi: 10.1145/2755996.2756647.
• [GHL16] Grenet, B., Hoeven, J., Lecerf, G.: “Deterministic root finding over finite fields using Graeffe transforms.” Appl. Algebra Eng. Commun. Comput. 27(3), 237–257 (Jun 2016). doi: 10.1007/s00200-015-0280-5.
• [Hoe22] van der Hoeven, J.: “Optimizing the Half-GCD algorithm.” ArXiv abs/2212.12389 (2022). arxiv.org/abs/2212.12389.
• [HM20] van der Hoeven, J., Monagan, M.: “Implementing the tangent Graeffe root finding method.” In: ICMS 2020. Springer (2020), pp. 482–492.
• [Hou59] Householder, A.S.: “Dandelin, Lobachevsky, or Graeffe.” The American Mathematical Monthly 66(6), 464–466 (1959).
• [JK97] Jakobsen, T., Knudsen, L.R.: “The interpolation attack on block ciphers.” In: Fast Software Encryption. Springer (1997), pp. 28–40.
• [JK81] Jia-Wei, H., Kung, H.T.: “I/O complexity: The red-blue pebble game.” In: STOC ’81. ACM (1981), pp. 326–333. doi: 10.1145/800076.802486.
• [MAT22] MATZOV: “Report on the security of LWE: Improved dual lattice attack.” (Apr 2022). doi: 10.5281/zenodo.6412487.
• [Moe73] Moenck, R.T.: “Fast computation of GCDs.” In: STOC ’73. ACM (1973), pp. 142–151. doi: 10.1145/800125.804045.
• [MCB+10] Mohamed, M.S.E., Cabarcas, D., Ding, J., Buchmann, J., Bulygin, S.: “MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals.” In: ICISC 2009. Springer (2010), pp. 87–100.
• [NIST23] NIST: “FAQ on Kyber512.” NIST PQC FAQ (December 2023).
• [Pan96] Pan, V.Y.: “Parallel computation of polynomial GCD and some related parallel computations over abstract fields.” Theoretical Computer Science 162(2), 173–223 (1996). doi: 10.1016/0304-3975(96)00030-8.
• [RSZ11] Ranjan, D., Savage, J., Zubair, M.: “Strong I/O lower bounds for binomial and FFT computation graphs.” In: COCOON 2011. Springer (2011), pp. 134–145.
• [SV25] Sanso, A., Vitto, G.: “Attacking Poseidon via Graeffe-based root-finding over NTT-friendly fields.” Cryptology ePrint Archive, Paper 2025/937 (2025). eprint.iacr.org/2025/937. [page on this site]
• [SS71] Schönhage, A., Strassen, V.: “Schnelle Multiplikation großer Zahlen.” Computing 7(3–4), 281–292 (1971). doi: 10.1007/BF02242355.
• [SS13] Scquizzato, M., Silvestri, F.: “Communication lower bounds for distributed-memory computations.” CoRR abs/1307.1805 (2013). arxiv.org/abs/1307.1805.
• [SAD20] Szepieniec, A., Ashur, T., Dhooghe, S.: “Rescue-Prime: a standard specification (SoK).” Cryptology ePrint Archive, Paper 2020/1143 (2020). eprint.iacr.org/2020/1143. [page on this site]