格子暗号
たとえば、直交基底 ( 1 , 0 , 0 ) {\displaystyle (1,0,0)} 、 ( 0 , 1 , 0 ) {\displaystyle (0,1,0)} 、 ( 0 , 0 , 1 ) {\displaystyle (0,0,1)} から Z 3 {\displaystyle \mathbb {Z} ^{3}} が生成されるが, ( 3 , 1 , 4 ) {\displaystyle (3,1,4)} 、 ( 1 , 5 , 9 ) {\displaystyle (1,5,9)} 、 ( 2 , − 1 , 0 ) {\displaystyle (2,-1,0)} も同じ格子を生成する別の基底である。
格子を用いた計算量的な問題で最も重要なものは最短ベクトル問題(英語版) (SVP,あるいはGapSVP) であり、これは、格子内の非ゼロのベクトルのうち最短のベクトルを求めよ、という問題である。この問題は、近似解 (最短ベクトル長の高々 n {\displaystyle n} の多項式倍の長さのベクトル) であっても、効率的に見つけられないと考えられており、さらには量子コンピュータを使ったとしても難しいと考えられている。多くの格子ベース暗号では、SVPを解くのが実際に難しいならば、暗号が破られないことが保障されている。