2016
Fast Fourier orthogonalization
Publication
Publication
Presented at the
International Symposium on Symbolic and Algebraic Computation, Waterloo, ON, Canada
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 | |
---|---|
, , , , | |
Thales Communications & Security Gennevilliers, France | |
S.A. Abramov , E.V. Zima , X-S. Gao | |
doi.org/10.1145/2930889.2930923 | |
International Symposium on Symbolic and Algebraic Computation | |
Organisation | Cryptology |
Ducas, L., & Prest, T. (2016). Fast Fourier orthogonalization. In S. A. Abramov, E. V. Zima, & X.-S. Gao (Eds.), . doi:10.1145/2930889.2930923 |