数学的な背景
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/14 02:45 UTC 版)
格子（英語版） L ⊂ R n {\displaystyle L\subset \mathbb {R} ^{n}} とは、基底ベクトル b 1 , … , b n ∈ R n {\displaystyle \mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\in \mathbb {R} ^{n}} の整数線形結合で表現できる全てのベクトルから成る集合である。つまり、 L = { ∑ a i b i : a i ∈ Z } {\displaystyle L={\Big \{}\sum a_{i}\mathbf {b} _{i}\ :\ a_{i}\in \mathbb {Z} {\Big \}}} である。例えば Z n {\displaystyle \mathbb {Z} ^{n}} は、普通の直行基底 R n {\displaystyle \mathbb {R} ^{n}} から生成される格子である。重要なのは、異なる基底が同一の格子を生成しうるということである。たとえば、直行基底 ( 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を解くのが実際に難しいならば、暗号が破られないことが保障されている。
※この「数学的な背景」の解説は、「格子暗号」の解説の一部です。
「数学的な背景」を含む「格子暗号」の記事については、「格子暗号」の概要を参照ください。
- 数学的な背景のページへのリンク
