Paper 2024/1036
A note on the G-FFT
Abstract
For primes $p$ with $p+1$ being smooth, the G-FFT from Li and Xing [LX23] is an algebraic FFT, which at first glance seems equivalent to the circle FFT from [IACR eprint 2024/278]: It also uses the circle curve over $\mathbb F_p$ (in other words the projective line) as underlying domain, and interpolates by low-degree functions with poles over the same set of points. However, their approach to control the degree of the FFT basis is fundamentally different. The G-FFT makes use of punctured Riemann-Roch spaces, and the construction works with the group doubling map only, no projection onto the $x$-axis involved. In this note we give an elementary description of the G-FFT without using abstract algebra. We describe a variant which uses a simpler, and in our opinion more natural function space, and which treats the exceptional point of the domain (the group identity) differently. In comparison to the circle FFT, the G-FFT (both the original as well as our variant) has the following downsides. Interpolation and domain evaluation costs the double number of multiplications (the twiddle is not an ``odd'' function), and the function space is not invariant under the group action, causing additional overhead when applied in STARKs.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- algebraic FFT
- Contact author(s)
- uhaboeck @ polygon technology
- History
- 2024-10-05: revised
- 2024-06-26: received
- See all versions
- Short URL
- https://ia.cr/2024/1036
- License
-
CC BY-SA
BibTeX
@misc{cryptoeprint:2024/1036, author = {Ulrich Haböck}, title = {A note on the G-{FFT}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1036}, year = {2024}, url = {https://eprint.iacr.org/2024/1036} }