Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations

Steven D. Galbraith, Joel Laity, Barak Shani

Ideas from Fourier analysis have been used in cryptography for the last three decades. Akavia, Goldwasser and Safra unified some of these ideas to give a complete algorithm that fi…