理想的な格子

離散数学において、理想格子は格子の特殊なクラスであり、巡回格子の一般化である。^{[1]理想格子は}数論 の多くの部分で自然に現れるが、他の分野にも存在する。特に、暗号学において重要な位置を占めている。ミシアンチョは巡回格子の一般化を理想格子と定義した。暗号システムにおいて理想格子を使用すると、格子を記述するために必要なパラメータの数を平方根だけ減らすことができ、効率が向上する。理想格子は新しい概念だが、同様の格子クラスは古くから使用されている。例えば、理想格子の特殊なケースである巡回格子は、NTRUEncryptやNTRUSignで使用されている。

理想格子は、リング学習とエラーに基づく量子コンピュータ攻撃耐性暗号の基礎にもなります。^{[2]これらの暗号システムは}、最短ベクトル問題（SVP）がこれらの理想格子では困難である という仮定の下で、安全であることが証明されています。

一般的に、イデアル格子は、次数 の何らかの既約多項式に対する の 形の環のイデアルに対応する格子である。^{[1]これまでの研究における}イデアル格子の定義はすべて、次の一般的な概念の例である。を加法群がに同型である環（すなわち、階数の自由- 加法群）とし、 を- 次元実ベクトル空間内の何らかの格子 （例えば）に写像する加法同型とする。埋め込みによる環のイデアル格子の族は、すべての格子 の集合であり、 は^[3]のイデアルである。${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle f}$${\displaystyle n}$${\displaystyle R}$${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle \mathbb {Z} }$ ${\displaystyle n}$${\displaystyle \sigma}$${\displaystyle R}$${\displaystyle \sigma (R)}$${\displaystyle n}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle R}$${\displaystyle \sigma}$${\displaystyle \sigma (I)}$${\displaystyle I}$${\displaystyle R.}$

を次数の単項多項式とし、商環 を考えます。 ${\displaystyle f\in \mathbb {Z} [x]}$${\displaystyle n}$ ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$

標準的な代表集合と多項式とベクトルの同一視を使用すると、商環 は整数格子と同型（加法群として）となり、任意のイデアルは対応する整数部分格子 を定義します。 ${\displaystyle \lbrace (g{\bmod {f}}):g\in \mathbb {Z} [x]\rbrace }$ ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle I\subseteq \mathbb {Z} [x]/\langle f\rangle }$${\displaystyle {\mathcal {L}}(I)\subseteq \mathbb {Z} ^{n}}$

理想格子は、次数の単項多項式 と理想 に対してとなる整数格子です。 ${\displaystyle {\mathcal {L}}(B)\subseteq \mathbb {Z} ^{n}}$${\displaystyle B=\lbrace g{\bmod {f}}:g\in I\rbrace }$${\displaystyle f}$${\displaystyle n}$ ${\displaystyle I\subseteq \mathbb {Z} [x]/\langle f\rangle }$

結果として得られる関数が衝突耐性を持つための 関連する特性は次のようになります。${\displaystyle f}$

• ${\displaystyle f}$は、 還元不可能 でなければなりません。
• 量的な意味では、環ノルムは任意の多項式 と比べてそれほど大きくありません。${\displaystyle \lVert g\rVert _{f}}$${\displaystyle \lVert g\rVert _{\infty }}$${\displaystyle g}$

最初の性質は、環 のあらゆるイデアルがのフルランク格子を定義し、証明において基本的な役割を果たすことを意味します。 ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$${\displaystyle \mathbb {Z} ^{n}}$

補題:が次数の単項既約整数多項式であるときのの任意のイデアルは 、 内のフルランク格子に同型である。 ${\displaystyle I}$${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$${\displaystyle f}$${\displaystyle n}$${\displaystyle \mathbb {Z} ^{n}}$

DingとLindner ^[4]は、理想格子と一般格子の区別が多項式時間で実行できるという証拠を示し、実際にはランダムに選択された格子が理想的になることは決してないことを示した。彼らは、格子がフルランクを持つ場合、つまり基底が線形独立ベクトルで構成される場合のみを考慮した。これは基本的な制限ではない。なぜなら、LyubashevskyとMicciancioは、格子が既約単項多項式に関して理想的である場合、上記の補題で与えられているように、それはフルランクを持つことを示したからである。 ${\displaystyle n}$

アルゴリズム:フルランク基底を持つ理想格子の識別

データ:フルランク基底結果: がに関して理想格子を張る場合はtrue、 、それ以外の場合はfalse。 ${\displaystyle B\in \mathbb {Z} ^{(n,n)}}$
${\displaystyle {\textbf {q}}}$${\displaystyle B}$${\displaystyle {\textbf {q}}}$

1. HNFに変身${\displaystyle B}$
2. 、、およびを計算します。${\displaystyle A={\rm {adj}}(B)}$${\displaystyle d=\det(B)}$${\displaystyle z=B_{(n,n)}}$
3. 積を計算する${\displaystyle P=AMB{\bmod {d}}}$
4. Pの最後の列のみがゼロでない 場合
5. この列と同じになるように設定${\displaystyle c=P_{(\centerdot ,n)}}$
6. それ以外の場合はfalseを返す
7. もしも ​​${\displaystyle z\mid c_{i}}$${\displaystyle i=1,\ldots ,n}$
8. CRTを使用して検索し、${\displaystyle q^{\ast }\equiv (c/z){\bmod {(}}d/z)}$${\displaystyle q^{\ast }\equiv 0{\bmod {\ }}z}$
9. それ以外の場合はfalseを返す
10. もし そうなら${\displaystyle Bq^{\ast }\equiv 0{\bmod {(}}d/z)}$
11. true を返す、${\displaystyle q=Bq^{\ast }/d}$
12. それ以外の場合はfalseを返す

ここで行列Mは

${\displaystyle M={\begin{pmatrix}0&\cdot &\cdot &\cdot &0\\&&&&\cdot \\&&&&\cdot \\I_{n-1}&&&&\cdot \\&&&&0\end{pmatrix}}}$

このアルゴリズムを使用すると、多くの格子が理想格子ではないことがわかります。たとえば、とすると、 ${\displaystyle n=2}$${\displaystyle k\in \mathbb {Z} \smallsetminus \lbrace 0,\pm 1\rbrace }$

${\displaystyle B_{1}={\begin{pmatrix}k&0\\0&1\end{pmatrix}}}$

理想的ですが

${\displaystyle B_{2}={\begin{pmatrix}1&0\\0&k\end{pmatrix}}}$

そうではありません。これはリュバシェフスキーとミチアンチョが示した例です。^[5]${\displaystyle B_{2}}$${\displaystyle k=2}$

これにアルゴリズムを実行し、基底をBとすると、行列Bはすでにエルミート標準形になっているので、最初のステップは不要です。行列式は、随伴行列です。${\displaystyle d=2}$

${\displaystyle A={\begin{pmatrix}2&0\\0&1\end{pmatrix}},}$

${\displaystyle M={\begin{pmatrix}0&0\\1&0\end{pmatrix}}}$

そして最後に、製品は ${\displaystyle P=AMB{\bmod {d}}}$

${\displaystyle P={\begin{pmatrix}0&0\\1&0\end{pmatrix}}.}$

この時点でアルゴリズムは停止します。これは、 が理想格子にまたがる場合、 の最後の列を除くすべての列がゼロになる必要があるためです。 ${\displaystyle P}$${\displaystyle B}$

Micciancio ^{[6] は、}多項式環 のイデアルに対応する構造化巡回格子のクラスを導入し、巡回格子への Poly( n )-SVPの制限の最悪ケース困難性に基づいて、証明可能に安全な最初の一方向関数を提示しました。(問題γ -SVP は、与えられた格子の非ゼロベクトルを計算することであり、そのノルムは最短の非ゼロ格子ベクトルのノルムのγ倍以下です。) 同時に、その代数構造のおかげで、この一方向関数は、NTRU方式の評価時間とストレージコストに匹敵する高い効率を享受しています。その後、Lyubashevsky と Micciancio ^[5]および Peikert と Rosen ^{[7]はそれぞれ独立して、Micciancio の関数を修正して、効率的で証明可能に安全な}衝突耐性ハッシュ関数を構築する方法を示しました。このため、彼らはより一般的な理想格子のクラスを導入しました。これは多項式環のイデアルに対応します。衝突耐性は、 Poly(n)-SVP の理想格子への制限の困難さに依存しています(Poly( n )-Ideal-SVP と呼ばれます)。平均ケースの衝突検出問題は Ideal-SIS と呼ばれる自然な計算問題であり、Ideal-SVP の最悪のケースと同じくらい困難であることが示されている。理想格子からの証明可能で安全な効率的な署名方式も提案されていますが、^{[1] [8] 、}理想格子 から効率的で証明可能で安全な公開鍵暗号化を構築することは興味深い未解決の問題でした。 ${\displaystyle \mathbb {Z} [x]/(x^{n}-1)}$${\displaystyle {\tilde {O}}(n)}$ ${\displaystyle \mathbb {Z} [x]/f(x)}$

LWE と Ring LWE を鍵交換に使用する基本的なアイデアは、2011 年に Jintai Ding によってシンシナティ大学で提案され、Ring LWEを使用した量子耐性鍵交換の最先端の説明を提供しました。論文^[9]は、 2012 年に仮特許出願が提出された後、2012 年に発表されました。2014 年に、Peikert ^[10]は Ding と同じ基本的なアイデアに従った鍵転送スキームを発表しました。このスキームでは、Ding の構築で丸めのために追加の信号を送信するという新しいアイデアも利用されています。同じ概念を使用したデジタル署名は、数年前に Vadim Lyubashevsky によって「Lattice Signatures Without Trapdoors」で行われました。^[11] Peikert と Lyubashevsky の研究を合わせると、同じセキュリティ削減を備えた Ring-LWEベースの量子攻撃耐性アルゴリズム のスイートが提供されます。

暗号における理想格子の主な有用性は、そのような格子内で近似的な最短ベクトルを見つけることの難しさに基づいて、非常に効率的で実用的な衝突耐性ハッシュ関数を構築できるという事実に由来しています。 ^[1] PeikertとRosen、^[7]、およびLyubashevskyとMicciancioによって 独立して構築された衝突耐性ハッシュ関数は、理想格子（巡回格子の一般化）に基づいており、高速で実用的な実装を提供しました。^[3]これらの結果は、識別スキームや署名を含む他の効率的な暗号構築への道を開いた。

Lyubashevsky と Micciancio ^[5]は、理想格子の最短ベクトル問題の最悪困難性に基づいて、安全であることが証明できる効率的な衝突耐性 ハッシュ関数の構築法を示した。彼らはハッシュ関数族を次のように定義した。環 （は次数の単項式で、 はおよそ の位数の整数）が与えられた場合、ランダムな要素（ は定数）を生成する。 順序付けられた-組によってハッシュ関数が決定される。 これは、 （ は の戦略的に選択されたサブセット）内の要素を にマッピングする。 要素 の場合、ハッシュは である。ここで、キー（ハッシュ関数）のサイズはであり、多項式 を適切に選択するために、この操作は高速フーリエ変換（FFT）^{[引用が必要]}を使用して100 分以内に実行できる。は定数であるため、ハッシュには の時間が必要である。彼らは、ハッシュ関数族が衝突耐性があることを証明するために、ランダムに選ばれたハッシュ関数に対して、次のような問題を 無視できない確率で見つけることに成功する多項式時間アルゴリズム が存在する場合、「最短ベクトル問題」と呼ばれる特定の問題が、環のすべてのイデアルに対して多項式時間で解けることを示しました。 ${\displaystyle R=\mathbb {Z} _{p}[x]/\langle f\rangle }$${\displaystyle f\in \mathbb {Z} _{p}[x]}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n^{2}}$${\displaystyle m}$${\displaystyle a_{1},\dots ,a_{m}\in R}$${\displaystyle m}$${\displaystyle m}$${\displaystyle h=(a_{1},\ldots ,a_{m})\in R^{m}}$${\displaystyle D^{m}}$${\displaystyle D}$${\displaystyle R}$${\displaystyle R}$${\displaystyle b=(b_{1},\ldots ,b_{m})\in D^{m}}$${\displaystyle h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i}}$${\displaystyle O(mn\log p)=O(n\log n)}$${\displaystyle \alpha _{i}\centerdot b_{i}}$${\displaystyle O(n\log n\log \log n)}$ ${\displaystyle f}$${\displaystyle m}$${\displaystyle O(n\log n\log \log n)}$${\displaystyle b\neq b'\in D^{m}}$${\displaystyle h(b)=h(b')}$ ${\displaystyle h\in R^{m}}$ ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$

2006年のLyubashevskyとMicciancioの研究に基づいて、MicciancioとRegev ^[12]は理想格子に基づくハッシュ関数の次のアルゴリズムを定義しました。

• パラメータ:、およびベクトルfを持つ整数。${\displaystyle q,n,m,d}$${\displaystyle n\mid m}$ ${\displaystyle \in \mathbb {Z} ^{n}}$
• キー: 内で独立かつ一様にランダムに選択されたベクトル。${\displaystyle m/n}$${\displaystyle a_{1},\ldots ,a_{m/n}}$${\displaystyle \mathbb {Z} _{q}^{n}}$
• ハッシュ関数: によって与えられます。${\displaystyle f_{A}:\lbrace 0,\ldots ,d-1\rbrace ^{m}\longrightarrow \mathbb {Z} _{q}^{n}}$${\displaystyle f_{A}(y)=[F\ast a_{1}|\ldots |F\ast a_{m/n}]y{\bmod {\ }}q}$

ここでパラメータは、f はのベクトルであり、は構造化ブロックを持つブロック行列です。 ${\displaystyle n,m,q,d}$${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle A}$${\displaystyle A^{(i)}=F\ast a^{(i)}}$

平均して（逆多項式確率のみを使用しても）内の短いベクトルを見つけることは、ベクトルf が次の 2 つの特性を満たす 場合、最悪の場合、理想的な格子上でさまざまな格子問題（近似SVPや SIVP など）を解くのと同じくらい困難です。${\displaystyle \Lambda _{q}^{\perp }([F\ast a_{1}|\ldots |F\ast a_{m/n}])}$

• 任意の 2 つの単位ベクトルu、vに対して、ベクトル[F∗u]v は小さな（つまり、 の多項式、通常はノルム）を持ちます。${\displaystyle n}$${\displaystyle O({\sqrt {n}}))}$
• この多項式は整数に対して既約であり、つまり、より小さい次数の整数多項式の積には含まれません。${\displaystyle f(x)=x^{n}+f_{n}x^{n-1}+\cdots +f_{1}\in \mathbb {Z} [x]}$

最初の特性は巡回行列に対応するベクトルによって満たされます。なぜなら、 [F∗u]vのすべての座標は1 で制限されるため となるからです。しかし、に対応する多項式はに因数分解されるため既約ではなく、これが衝突が効率的に検出される理由です。したがって、 は衝突耐性ハッシュ関数 を得るための良い選択ではありませんが、他の多くの選択が可能です。たとえば、両方の特性が満たされる (したがって、最悪のセキュリティ保証を備えた 衝突耐性ハッシュ関数になる) fのいくつかの選択は次のとおりです。${\displaystyle \mathbf {F} =(-1,0,\ldots ,0)}$${\displaystyle \lVert [{\textbf {F}}\ast {\textbf {u}}]{\textbf {v}}\rVert \leq {\sqrt {n}}}$${\displaystyle x^{n}-1}$${\displaystyle \mathbf {f} =(-1,0,\ldots ,0)}$${\displaystyle (x-1)(x^{n-1}+x^{n-2}+\cdots +x+1)}$${\displaystyle \mathbf {f} =(-1,0,\ldots ,0)}$

• ${\displaystyle \mathbf {f} =(1,\ldots ,1)\in \mathbb {Z} ^{n}}$ここで は素数であり、${\displaystyle n+1}$
• ${\displaystyle \mathbf {f} =(1,0,\ldots ,0)\in \mathbb {Z} ^{n}}$2の累乗に等しい。${\displaystyle n}$

デジタル署名方式は、最も重要な暗号プリミティブの 1 つです。これらは、格子問題の最悪ケースの困難性に基づく一方向関数を使用して取得できます。ただし、実用的ではありません。エラー学習問題が暗号コンテキストに適用されて以来、エラー学習、エラーリング学習、トラップドア格子に基づく新しいデジタル署名方式が数多く開発されてきました。

理想的な（例えば巡回的な）格子における最短ベクトルの近似の複雑さに基づいたデジタル署名の直接的な構築。 ^[8] LyubashevskyとMicciancioの方式^[8]は、理想的な格子に基づく最悪のケースのセキュリティ保証を備えており、現在までに知られている中で最も漸近的に効率的な構成であり、ほぼ線形時間で実行される署名生成および検証アルゴリズムを生み出します。^[12]

彼らの研究によって提起された主要な未解決問題の一つは、同様の効率を持ちながら、より弱い困難性仮定に基づいたワンタイム署名を構築することである。例えば、最短ベクトル問題（SVP） （理想的な格子 内）を の係数以内に近似することの困難性に基づいたセキュリティを備えたワンタイム署名を提供できれば素晴らしいだろう。^[8]${\displaystyle {\tilde {O}}(n)}$

これらの構築は、ワンタイム署名（つまり、単一のメッセージに安全に署名できる署名）から一般的な署名スキームへの標準的な変換と、最終的には、任意の既約多項式 の環内のイデアルに対応するすべての格子内の最短ベクトルを近似することの最悪のケースの困難さに基づくセキュリティを持つ格子ベースのワンタイム署名の新しい構築に基づいています。 ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle f}$

鍵生成アルゴリズム: 入力: 、次数 の既約多項式。 ${\displaystyle 1^{n}}$ ${\displaystyle f\in \mathbb {Z} }$${\displaystyle n}$

1. セット、、${\displaystyle p\longleftarrow (\varphi n)^{3}}$${\displaystyle m\longleftarrow \lceil \log n\rceil }$${\displaystyle R\longleftarrow \mathbb {Z} _{p}[x]/\langle f\rangle }$
2. すべての正の に対して、集合 とを 次のように定義します。${\displaystyle i}$${\displaystyle DK_{i}}$${\displaystyle DL_{i}}$

${\displaystyle DK_{i}=\lbrace {\hat {y}}\in R^{m}}$そのような${\displaystyle \lVert {\hat {y}}\rVert _{\infty }\leq 5ip^{1/m}\rbrace }$

${\displaystyle DL_{i}=\lbrace {\hat {y}}\in R^{m}}$そのような${\displaystyle \lVert {\hat {y}}\rVert _{\infty }\leq 5in\varphi p^{1/m}\rbrace }$

1. 一様ランダムに選択${\displaystyle h\in {\mathcal {H}}_{R,m}}$
2. 一様にランダムな文字列を選択する${\displaystyle r\in \lbrace 0,1\rbrace ^{\lfloor \log ^{2}n\rfloor }}$
3. もし そうなら${\displaystyle r=0^{\lfloor \log ^{2}n\rfloor }}$
4. セット${\displaystyle j=\lfloor \log ^{2}n\rfloor }$
5. それ以外
6. 文字列の最初の1の位置に設定する${\displaystyle j}$${\displaystyle r}$
7. 終了の場合
8. それぞれから独立かつ均一にランダム に選ぶ${\displaystyle {\hat {k}},{\hat {l}}}$${\displaystyle DK_{j}}$${\displaystyle DL_{j}}$
9. 署名キー:検証キー:${\displaystyle ({\hat {k}},{\hat {l}})}$${\displaystyle (h,h({\hat {k}}),h({\hat {l}}))}$

署名アルゴリズム:

入力:署名キーを含むメッセージ${\displaystyle z\in R}$${\displaystyle \lVert z\rVert _{\infty }\leq 1}$${\displaystyle ({\hat {k}},{\hat {l}})}$

出力： ${\displaystyle {\hat {s}}\longleftarrow {\hat {k}}z+{\hat {l}}}$

検証アルゴリズム:

入力:メッセージ; 署名; 検証キー${\displaystyle z}$${\displaystyle {\hat {s}}}$${\displaystyle (h,h({\hat {k}}),h({\hat {l}}))}$

出力:「ACCEPT」、ifおよび${\displaystyle \lVert {\hat {s}}\rVert _{\infty }\leq 10\varphi p^{1/m}n\log ^{2}n}$${\displaystyle {\hat {s}}={\hat {k}}z+{\hat {l}}}$

それ以外の場合は「拒否」。

ハッシュ関数は非常に効率的で、複素数 に対して高速フーリエ変換 (FFT) を使用して、時間とともに漸近的に計算できます。ただし、実際には、これにはかなりのオーバーヘッドが伴います。Micciancio と Regev ^{[12]によって定義された}ハッシュ関数のSWIFFTファミリは、本質的には、の(FFT) を使用して上記のハッシュ関数を高度に最適化された変形です。ベクトルfは2 の累乗に等しい場合 に設定されるため、対応する多項式は既約です。を で割り切れる素数とし、を後で選択される上の可逆行列とします。 SWIFFTハッシュ関数は、から一様選択されたベクトルで構成されるキーと入力をにマッピングします。ここで、 は前 と同じで、 です。可逆行列による乗算により、一様選択されたが一様選択された にマッピングされます。さらに、 の場合に限ります。これら 2 つの事実を合わせると、SWIFFTで衝突を見つけることは、基礎となる理想格子関数で衝突を見つけることと同等であり、SWIFFTの衝突耐性特性は、理想格子上の最悪ケースの格子問題との関連によってサポートされていることがわかります。 ${\displaystyle {\tilde {O}}(m)}$${\displaystyle \mathbb {Z} _{q}}$${\displaystyle (1,0,\dots ,0)\in \mathbb {Z} ^{n}}$${\displaystyle n}$${\displaystyle x^{n}+1}$${\displaystyle q}$${\displaystyle 2n}$${\displaystyle q-1}$${\displaystyle {\textbf {W}}\in \mathbb {Z} _{q}^{n\times n}}$${\displaystyle \mathbb {Z} _{q}}$ ${\displaystyle {\tilde {a}}^{(1)},\ldots ,{\tilde {a}}^{(m/n)}}$${\displaystyle m/n}$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle y\in \lbrace 0,\ldots ,d-1\rbrace ^{m}}$${\displaystyle {\textbf {W}}^{\centerdot }f_{A}(y){\bmod {\ }}q}$${\displaystyle {\textbf {A}}=[{\textbf {F}}\ast \alpha ^{(1)},\ldots ,{\textbf {F}}\ast \alpha ^{(m/n)}]}$${\displaystyle \alpha ^{(i)}={\textbf {W}}^{-1}{\tilde {a}}^{(i)}{\bmod {q}}}$ ${\displaystyle {\textbf {W}}^{-1}}$${\displaystyle {\tilde {a}}\in \mathbb {Z} _{q}^{n}}$${\displaystyle \alpha \in \mathbb {Z} _{q}^{n}}$${\displaystyle {\textbf {W}}^{\centerdot }f_{A}(y)={\textbf {W}}^{\centerdot }f_{A}(y'){\pmod {q}}}$${\displaystyle f_{A}(y)=f_{A}(y'){\pmod {q}}}$${\displaystyle f_{A}}$

SWIFFT ハッシュ関数のアルゴリズムは次のとおりです。

• パラメータ:が 2 の累乗、が素数、となるような整数。${\displaystyle n,m,q,d}$${\displaystyle n}$${\displaystyle q}$${\displaystyle 2n\mid (q-1)}$${\displaystyle n\mid m}$
• キー: 内で独立かつ一様にランダムに選択されたベクトル。${\displaystyle m/n}$${\displaystyle {\tilde {a}}_{1},\ldots ,{\tilde {a}}_{m/n}}$${\displaystyle \mathbb {Z} _{q}^{n}}$
• 入力: ベクトル。${\displaystyle m/n}$${\displaystyle y^{(1)},\dots ,y^{(m/n)}\in \lbrace 0,\dots ,d-1\rbrace ^{n}}$
• 出力:ベクトル。ここで、 は要素ごとのベクトル積です。${\displaystyle \sum _{i=1}^{m/n}{\tilde {a}}^{(i)}\odot ({\textbf {W}}y^{(i)})\in \mathbb {Z} _{q}^{n}}$${\displaystyle \odot }$

エラー付き学習 (LWE)問題は、最悪のケースの格子問題と同じくらい難しいことが示されており、多くの暗号化アプリケーションの基礎となっています。しかし、これらのアプリケーションは、LWEの使用に伴う固有の二次オーバーヘッドのために非効率的です。本当に効率的なLWEアプリケーションを実現するために、Lyubashevsky、Peikert、Regev ^{[3] は、幅広いクラスのリングで}LWE問題の適切なバージョンを定義し、これらのリング内の理想的な格子上の最悪のケースの仮定の下でその困難性を証明しました。彼らは、このLWEバージョンをリング LWE と呼びました。

とします。ここで、セキュリティパラメータは2 の累乗であり、有理数上で既約となります。(この特定の値は、この研究で特別な役割を果たす 円分多項式の族から来ています)。${\displaystyle f(x)=x^{n}+1\in \mathbb {Z} [x]}$${\displaystyle n}$${\displaystyle f(x)}$${\displaystyle f(x)}$

を法とする整数多項式の環とします。の元（すなわち、 を法とする剰余）は、通常、 未満の次数の整数多項式で表されます。を（ の多項式で制限される）十分に大きい公開素数を法として、 をと の両方を法とする整数多項式の環とします。 の元は、からの係数である -未満の次数の多項式で表すことができます。 ${\displaystyle R=\mathbb {Z} [x]/\langle f(x)\rangle }$${\displaystyle f(x)}$${\displaystyle R}$${\displaystyle f(x)}$${\displaystyle n}$${\displaystyle q\equiv 1{\bmod {2}}n}$${\displaystyle n}$${\displaystyle R_{q}=R/\langle q\rangle =\mathbb {Z} _{q}[x]/\langle f(x)\rangle }$${\displaystyle f(x)}$${\displaystyle q}$${\displaystyle R_{q}}$${\displaystyle n}$${\displaystyle \lbrace 0,\dots ,q-1\rbrace }$

上述の環では、R-LWE 問題は次のように記述できます。を秘密にされている一様ランダムな環要素とします。標準 LWE と同様に、攻撃者の目的は、任意の数の (独立した)「ランダム ノイズ 環方程式」を真に一様のものから区別することです。より具体的には、ノイズ方程式は の形式であり、ここで a は一様ランダムであり、積は上の特定の分布から選択された「小さな」ランダム誤差項によって摂動されます。 ${\displaystyle s=s(x)\in R_{q}}$${\displaystyle (a,b\approx a\centerdot s)\in R_{q}\times R_{q}}$${\displaystyle a\centerdot s}$${\displaystyle R}$

彼らは、理想格子上の近似SVP (最悪の場合)からリング LWE の探索バージョンへの量子還元を与えました。ここでの目標は、任意の数のノイズの多い積から秘密を(任意の に対して高い確率で) 復元することです。この結果は、一般格子に対する Regev の反復量子還元の一般的な概要に従っていますが、 ^[13]理想格子は、還元の「代数的」要素と「幾何学的」要素の両方でいくつかの新しい技術的な障害をもたらします。彼ら^[3]は 、代数的数論、特に数体の標準埋め込みと中国剰余定理を使用してこれらの障害を克服しました。彼らは次の定理を得ました。 ${\displaystyle R}$${\displaystyle s\in R_{q}}$${\displaystyle s}$

定理 を次数の任意の数体とします。を任意とし、(有理)整数係数がとなるものとします。 -から-への確率的多項式時間量子還元が存在します。ここで です。 ${\displaystyle K}$${\displaystyle n}$${\displaystyle \alpha =\alpha (n)\in (0,1)}$${\displaystyle q=q(n)\geq 2}$${\displaystyle \alpha \centerdot q\geq \omega ({\sqrt {\log n}})}$${\displaystyle K}$${\displaystyle DGS_{\gamma }}$${\displaystyle {\mathcal {O}}_{K}}$${\displaystyle LWE_{q,\Psi \leq \alpha }}$${\displaystyle \gamma =\eta _{\epsilon }(I)\centerdot \omega ({\sqrt {\log n}})/\alpha }$

2013年、Guneysu、Lyubashevsky、およびPopplemanは、リング学習エラー問題に基づくデジタル署名方式を提案しました。^[14] 2014年、Peikertは論文「インターネットのための格子暗号」でリング学習エラー鍵交換（RLWE-KEX）を発表しました。^[10]これはSinghの研究によってさらに発展しました。^[15]

Stehle、Steinfeld、Tanaka、Xagawa ^[16]は、 LWE問題の構造化バリアント（Ideal-LWE）を定義し、理想格子における近似SVPの最悪ケースの困難性に基づく効率的な公開鍵暗号化方式を記述した。これは、-Ideal-SVPの最悪ケースのインスタンスのサブ指数量子攻撃に対する困難性にセキュリティが依存する、最初のCPAセキュア公開鍵暗号化方式である。これは漸近的に最適な効率を達成し、公開鍵/秘密鍵の長さは ビットであり、償却暗号化/復号化コストはメッセージビットあたりのビット操作である（コスト をかけて一度にビットを暗号化する）。ここでのセキュリティ仮定は、-Ideal-SVPはいかなるサブ指数時間量子アルゴリズムでも解くことができないというものである。これは、標準的な公開鍵暗号のセキュリティ仮定よりも強力であることは注目に値する。一方、ほとんどの公開鍵暗号とは対照的に、格子ベースの暗号は サブ指数量子攻撃に対するセキュリティを可能にする。 ${\displaystyle {\tilde {O}}(n^{2})}$${\displaystyle {\tilde {O}}(n)}$${\displaystyle {\tilde {O}}(1)}$${\displaystyle {\tilde {\Omega }}(n)}$${\displaystyle {\tilde {O}}(n)}$${\displaystyle {\tilde {O}}(n^{2})}$

一般格子に基づく暗号システムのほとんどは、エラー付き学習 (LWE)の平均ケースの困難性に依存しています。彼らの方式は、彼らが Ideal-LWE と呼ぶ LWE の構造化された変形に基づいています。彼らは、理想格子への制限から生じる 2 つの主な困難を回避するために、いくつかの手法を導入する必要がありました。第 1 に、非構造化格子に基づくこれまでの暗号システムはすべて、限界距離復号問題 (BDD) からLWEへの Regev の最悪ケースから平均ケースへの古典的な還元を利用しています (これは、 SVPからLWEへの量子還元における古典的なステップです)。この還元は、考慮されている格子の非構造化を利用しており、Ideal-LWE に含まれる構造化格子には引き継がれないようです。特に、LWE 行列の行の確率的独立性により、単一の行を考慮できます。第二に、以前の暗号システムで使用されていた他の要素、つまり、LWEの計算型から決定型への Regev の縮約も Ideal-LWE では機能しないようです。これは、 LWE行列の列の確率的独立性に依存しているからです。

これらの困難を克服するために、彼らは古典的な還元ステップを避けました。代わりに、量子ステップを使用して、 SIS (平均ケース衝突検出問題) からLWEへの新しい量子平均ケース還元を構築しました。これは、Ideal-SIS から Ideal-LWE にも機能します。最悪ケースの Ideal-SVP から平均ケースの Ideal-SIS への還元と組み合わせて、Ideal-SVP から Ideal-LWE への量子還元を取得しました。これは、Ideal-LWE の計算バリアントの困難さを示しています。決定バリアントの困難さを取得できなかったため、汎用のハードコア関数を使用して暗号化用の疑似ランダムビットを導出しました。これが、SVPの指数的困難性を想定する必要があった理由です。

完全準同型暗号化（FHE）方式は、暗号化されたデータを復号化することなく計算できる方式です。完全準同型暗号化方式を構築する問題は、Rivest、Adleman、ShamirによるRSAの発明直後の1978年に、 Rivest、Adleman、Dertouzos ^[17]によって初めて提唱されました。^[18]

暗号化方式が回路 の準同型である場合、任意の回路 に対して、 ${\displaystyle \varepsilon =({\mathsf {KeyGen}},{\mathsf {Encrypt}},{\mathsf {Decrypt}},{\mathsf {Eval}})}$${\displaystyle {\mathcal {C}}}$${\displaystyle C\in {\mathcal {C}}}$

、、および、 が与えられた場合、${\displaystyle PK,SK\leftarrow {\mathsf {KeyGen}}(1^{\lambda })}$${\displaystyle y={\mathsf {Encrypt}}(PK,x)}$${\displaystyle y'={\mathsf {Eval}}(PK,C,y)}$

それはそうである。 ${\displaystyle {\mathsf {Decrypt}}(SK,y')=C(x)}$

${\displaystyle \varepsilon }$は、スキームのセキュリティパラメータで あるサイズのすべての回路に対して準同型である場合、完全に準同型です。${\displaystyle \operatorname {poly} (\lambda )}$${\displaystyle \lambda }$

2009年に、ジェントリー^{[19]は、完全}準同型暗号化方式を構築する問題に対する最初の解決策を提案しました。彼の方式は理想格子に基づいていました。

• 格子ベースの暗号
• 準同型暗号
• エラーのあるリング学習と鍵交換
• 耐量子暗号
• 短整数解問題