Paper 2026/2413
Fast Polynomial Arithmetic in the Exponent without Roots of Unity
Abstract
In cryptographic algorithms based on groups in which the discrete logarithm is supposed to be hard, it is frequent to perform polynomial arithmetic in the exponent of group elements. This old technique has become a critical operation in many recent advanced protocols, mostly related to commitments and zero-knowledge proofs, where polynomials of high degrees are involved. Number Theoretic Transform (NTT) techniques in the exponent are often implemented to gain speed. However, they require roots of unity to exist in the field GF(q) where q is the order of the group. In this work, we propose algorithms that preserve the quasi-linear complexity of the Fourier Transforms, even when no root of unity are available. For this, we develop a formalism for the algebraic structure of polynomials with coefficients in a group, that allows us to adapt asymptotically fast polynomial multiplication algorithms to the case of arithmetic in the exponent. In particular, we design an algorithm inspired by the Schönhage-Strassen algorithm, which runs about twice slower than NTT but does not require any arithmetic property on the order of the group. We explain how this can be adapted to batched KZG commitment proofs and the Bayer-Groth verifiable mixnet used in e-voting.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Contact author(s)
- pierrick gaudry @ loria fr
- History
- 2026-10-11: approved
- 2026-10-08: received
- See all versions
- Short URL
- https://ia.cr/2026/2413
- License
-
CC BY-SA
BibTeX
@misc{cryptoeprint:2026/2413,
author = {Diane Ducrocq and Pierrick Gaudry},
title = {Fast Polynomial Arithmetic in the Exponent without Roots of Unity},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2413},
year = {2026},
url = {https://eprint.iacr.org/2026/2413}
}
