The classical fast Fourier transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the {\em circular convolution ring} R[x]/(x^d−1) --- a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix-vector products when the matrix is *circulant*. In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of matrices with circulant blocks of size d×d . We show that, when d is composite, it is possible to proceed to the orthogonalization in an inductive way ---up to an appropriate re-indexation of rows and columns. This leads to a structured Gram-Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the nearest plane algorithm. The complexity of both algorithms may be brought down to Θ(dlogd). Our results easily extend to *cyclotomic rings*, and can be adapted to Gaussian samplers. This finds applications in lattice-based cryptography, improving the performances of trapdoor functions.
, , , ,
Thales Communications & Security Gennevilliers, France
S.A. Abramov , E.V. Zima , X-S. Gao
International Symposium on Symbolic and Algebraic Computation

Ducas, L., & Prest, T. (2016). Fast Fourier orthogonalization. In S. A. Abramov, E. V. Zima, & X.-S. Gao (Eds.), . doi:10.1145/2930889.2930923