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.
Additional Metadata
Keywords public-key cryptography / Fast Fourier Transform, Gram-Schmidt Orthogonalization, Nearest Plane Algorithm, Lattice Algorithms, Lattice Trapdoor Functions.
THEME Information (theme 2)
Stakeholder Thales Communications & Security Gennevilliers, France
Editor S.A. Abramov , E.V. Zima , X-S. Gao
Persistent URL dx.doi.org/10.1145/2930889.2930923
Conference International Symposium on Symbolic and Algebraic Computation
Citation
Ducas, L, & Prest, T. (2016). Fast Fourier orthogonalization. In S.A Abramov, E.V Zima, & X-S Gao (Eds.), . doi:10.1145/2930889.2930923

Additional Files
24688B.pdf Author Manuscript , 505kb
Publisher Version