Paper 2024/1036

A note on the G-FFT

Ulrich Haböck, Polygon Labs
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)
PDF
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
Creative Commons Attribution-ShareAlike
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.