格子暗号
1996年にミクロス・Ajtai(英語版)は、良く知られた格子問題の困難性を利用した最初の格子暗号の構成を示した。 シンシア・ドワーク(英語版)は、短整数解問題(英語版) (SIS) と呼ばれる格子問題の平均時の計算困難性が、ある格子問題の最悪時の計算困難性と同等かそれ以上であることを示した。そして、SIS問題の計算困難性と等価な安全性を持つハッシュ関数を示した。
1998年に、Jeffrey Hoffstein、Jill Pipher、Joseph H. Silvermanの3人は、NTRU暗号と呼ばれる格子ベースの公開鍵暗号方式を提案した。 しかし、彼らの方式は、最悪時の格子問題を解くことと等価 (あるいはそれ以上) な安全性を持つかどうかは知られていない。最悪時の計算量的困難性の仮定の下で安全性が証明された最初の方式は、2005年にOded Regevによって提案されている。この論文では、計算困難な問題としてLWE問題(英語版) (Learning with Errors問題) も提案されている。それ以降、多くの後続研究がRegevの安全性証明を改善したり 、方式の効率を改善している 。 さらに多くの研究が、LWE問題や関連した問題を元にして、暗号プリミティブを構築することに専念してきた。例えば、2009年にGentryは初めての 完全準同型暗号方式を提案したが、これは格子問題に基づいている。