Lattice problem とは

コンピュータ科学では、格子問題は格子上の最適化問題の一種である。このような問題の予想される難易度は、安全な格子ベースの暗号システムの構築の中心である。そのような暗号システムのアプリケーションでは、ベクトル空間(多くの場合、 Q n {\displaystyle \mathbb {Q} ^{n}} )またはフリーモジュール(多くの場合、 Z n {\displaystyle \mathbb {Z} ^{n}} )上の格子が一般的に考慮されます。
以下のすべての問題について、ベクトル空間VとノルムNの基礎を(他のより特定のインプットに加えて)与えていると仮定します。通常考えられるノルムはL2です。しかし、他の規範(Lpなど)も考慮され、さまざまな結果に現れます。 λ ( L ) {\displaystyle \lambda (L)} は、格子Lにおける最短の非ゼロベクトルの長さ、すなわち、
λ ( L ) = min v L { 0 } v N {\displaystyle \lambda (L)=\min _{v\in L\setminus \{\mathbf {0} \}}\|v\|_{N}}