Welcome to the resource topic for 2015/1014
Title:
Fast Fourier Orthogonalization
Authors: Léo Ducas, Thomas Prest
Abstract:The classical fast Fourier transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the {\em circular convolution ring} \mathbb 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\times 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 \Theta(d \log d). 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.
ePrint: https://eprint.iacr.org/2015/1014
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .