Paper 2016/682

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

Steven D. Galbraith, Joel Laity, and Barak Shani

Abstract

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 finds significant Fourier coefficients of functions on any finite abelian group. Their algorithm stimulated a lot of interest in the cryptography community, especially in the context of ``bit security''. This manuscript attempts to be a friendly and comprehensive guide to the tools and results in this field. The intended readership is cryptographers who have heard about these tools and seek an understanding of their mechanics and their usefulness and limitations. A compact overview of the algorithm is presented with emphasis on the ideas behind it. We show how these ideas can be extended to a ``modulus-switching'' variant of the algorithm. We survey some applications of this algorithm, and explain that several results should be taken in the right context. In particular, we point out that some of the most important bit security problems are still open. Our original contributions include: a discussion of the limitations on the usefulness of these tools; an answer to an open question about the modular inversion hidden number problem.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Significant Fourier transformGoldreich-Levin algorithmKushilevitz-Mansour algorithmbit security of Diffie-Hellman
Contact author(s)
barak shani @ auckland ac nz
History
2018-12-13: last of 3 revisions
2016-07-12: received
See all versions
Short URL
https://ia.cr/2016/682
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/682,
      author = {Steven D.  Galbraith and Joel Laity and Barak Shani},
      title = {Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations},
      howpublished = {Cryptology ePrint Archive, Paper 2016/682},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/682}},
      url = {https://eprint.iacr.org/2016/682}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.