■

Oded Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography," STOC 2005.

主結果はGapSVPからランダム線型符号の復号問題への帰着であるが，これを基にGapSVPベースの公開鍵暗号系の構成を与えている．
つまり，ある近似パラメータのGapSVPが量子多項式時間に入らなければ安全性が保証できるような格子系公開鍵暗号を提案している．
使っている主なテクニックは量子フーリエ変換，格子と双対格子の関係，実空間上の格子点を中心としたある種の Gaussian Measure．