New lattice-based cryptographic constructions

Research output: Contribution to journalArticlepeer-review


We introduce the use of Fourier analysis on lattices as an integral part of a lattice-based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions that are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (O(n1.5) instead of O(n7)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions with an improved security guarantee in terms of the unique shortest vector problem. Surprisingly, both results are derived from one theorem that presents two indistinguishable distributions on the segment [0, 1). It seems that this theorem can have further applications; as an example, we use it to solve an open problem in quantum computation related to the dihedral hidden subgroup problem.

Original languageEnglish (US)
Pages (from-to)899-942
Number of pages44
JournalJournal of the ACM
Issue number6
StatePublished - Nov 2004


  • Average-case hardness
  • Cryptography
  • Lattice
  • Public key encryption
  • Quantum computing

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'New lattice-based cryptographic constructions'. Together they form a unique fingerprint.

Cite this