間違いから学ぶ

暗号学において、エラー付き学習（LWE ）は安全な暗号化アルゴリズムを作成するために広く使用されている数学的な問題です。^[1]これは、秘密情報をエラーを含む一連の方程式として表現するという考えに基づいています。言い換えると、LWEはノイズを導入することで秘密の値を隠す方法です。^[2]より技術的な用語では、一部が間違っている可能性のある与えられたサンプルから有限環上の線形関数を推論する計算問題を指します。LWE問題は解決が難しいと推測されており、^[1]そのため暗号学で有用です。 ${\displaystyle n}$${\displaystyle f}$${\displaystyle y_{i}=f(\mathbf {x} _{i})}$

より正確には、LWE 問題は次のように定義されます。 を法とする整数の環を で表し、上の - ベクトルの集合を で 表します。ある未知の線形関数 が存在し、LWE 問題への入力はおよびのペアのサンプルです。したがって、高い確率で となります。さらに、等式からの偏差は、何らかの既知のノイズ モデルに従います。この問題では、関数 またはその近似値を高い確率で見つけることが求められます。 ${\displaystyle \mathbb {Z} _{q}}$ ${\displaystyle q}$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle n}$${\displaystyle \mathbb {Z} _{q}}$${\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}$${\displaystyle (\mathbf {x} ,y)}$${\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}$${\displaystyle y\in \mathbb {Z} _{q}}$${\displaystyle y=f(\mathbf {x} )}$${\displaystyle f}$

LWE問題は2005年にオデッド・レゲフ^{[3] （この研究で2018年の}ゲーデル賞を受賞）によって導入された。これはパリティ学習問題の一般化である。レゲフは、LWE問題がいくつかの最悪ケースの格子問題と同じくらい難しいことを示した。その後、LWE問題は、ペイカートによるエラー付きリング学習鍵交換[ ^5]などの公開鍵暗号システムを作成するための困難性仮定として使用されてきました^{[3] [4]}。

を 1 を法とする実数上の加法群で表します。を固定ベクトルとします。を 上の固定確率分布とします。上の分布を次のようにして表します。 ${\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }$${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$${\displaystyle \phi }$${\displaystyle \mathbb {T} }$${\displaystyle A_{\mathbf {s} ,\phi }}$${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$

1. 上の一様分布からベクトルを選び、${\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}$${\displaystyle \mathbb {Z} _{q}^{n}}$
2. 分布から数字を選び、${\displaystyle e\in \mathbb {T} }$${\displaystyle \phi }$
3. を評価します。ここで はにおける標準の内積であり、除算は実数体で行われます(または、より正式には、この「 による除算」はへの群準同型写像の表記です)。最終的な加算は で行われます。${\displaystyle t=\langle \mathbf {a} ,\mathbf {s} \rangle /q+e}$${\displaystyle \textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}}$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle q}$${\displaystyle \mathbb {Z} _{q}\longrightarrow \mathbb {T} }$${\displaystyle 1\in \mathbb {Z} _{q}}$${\displaystyle 1/q+\mathbb {Z} \in \mathbb {T} }$${\displaystyle \mathbb {T} }$
4. ペアを出力します。${\displaystyle (\mathbf {a} ,t)}$

エラー付き学習の問題とは 、から多項式個数の選択サンプルにアクセスできる場合に、を見つけることです。 ${\displaystyle \mathrm {LWE} _{q,\phi }}$${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$${\displaystyle A_{\mathbf {s} ,\phi }}$

任意の に対して、 を平均 0、分散 の 1 次元ガウス分布で表す。つまり、密度関数は であり、を法 1で考えることによって得られるの分布とする。ほとんどの結果で考慮される LWE のバージョンは、${\displaystyle \alpha >0}$${\displaystyle D_{\alpha }}$${\displaystyle \alpha ^{2}/(2\pi )}$${\displaystyle D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha }$${\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}$${\displaystyle \Psi _{\alpha }}$${\displaystyle \mathbb {T} }$${\displaystyle D_{\alpha }}$${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$

上で説明したLWE問題は、問題の探索バージョンです。決定バージョン ( DLWE ) では、ノイズの多い内積と(実際には、その離散化されたバージョン) からの一様ランダムサンプルを区別することが目標です。Regev ^[3]は、が 内の何らかの多項式で制限される素数である場合に、決定バージョンと探索バージョンが同等であることを示しました。 ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$${\displaystyle q}$${\displaystyle n}$

直感的には、探索問題に対する手順があれば、決定バージョンは簡単に解くことができます。つまり、決定問題の入力サンプルを探索問題のソルバーに渡すだけです。与えられたサンプルを で表します。ソルバーが候補 を返す場合、すべての に対してを計算します。サンプルが LWE 分布からのものである場合、この計算の結果は に従って分布しますが、サンプルが一様ランダムである場合、これらの量も一様に分布します。 ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$${\displaystyle \mathbf {s} }$${\displaystyle i}$${\displaystyle \{\langle \mathbf {a} _{i},\mathbf {s} \rangle -\mathbf {b} _{i}\}}$${\displaystyle \chi }$

反対方向では、決定問題に対するソルバーが与えられれば、探索バージョンは次のように解くことができます。一度に 1 つの座標を復元します。最初の座標 を取得するには、を推測し、次の操作を行います。一様にランダムに数値を選択します。指定されたサンプルを次のように変換します。 を計算します。変換されたサンプルを決定ソルバーに送信します。 ${\displaystyle \mathbf {s} }$${\displaystyle \mathbf {s} _{1}}$${\displaystyle k\in \mathbb {Z} _{q}}$${\displaystyle r\in \mathbb {Z} _{q}}$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$${\displaystyle \{(\mathbf {a} _{i}+(r,0,\ldots ,0),\mathbf {b} _{i}+(rk)/q)\}}$

推測が正しければ、変換によって分布はそれ自身になります。そうでない場合は、 は素数なので、一様分布になります。したがって、 が の何らかの多項式によって制限されるため、非常に低い確率で誤りを生じる決定問題に対する多項式時間ソルバーが与えられた場合、 のすべての可能な値を推測し、ソルバーを使用してどれが正しいかを確認するのに かかる時間は多項式時間だけです。${\displaystyle k}$${\displaystyle A_{\mathbf {s} ,\chi }}$${\displaystyle q}$${\displaystyle q}$${\displaystyle n}$${\displaystyle k}$

を取得した後、他の座標に対して同様の手順に従います。つまり、サンプルを同じ方法で変換し、 を計算してサンプルを変換します。ここで、 は座標にあります。^[3]${\displaystyle \mathbf {s} _{1}}$${\displaystyle \mathbf {s} _{j}}$${\displaystyle \mathbf {b} _{i}}$${\displaystyle \mathbf {a} _{i}}$${\displaystyle \mathbf {a} _{i}+(0,\ldots ,r,\ldots ,0)}$${\displaystyle r}$${\displaystyle j^{\text{th}}}$

Peikert ^[4]は、この簡約は、少し修正すれば、異なる小さな素数（ の多項式）の積である任意の に対して機能することを示した。主な考え方は、 の場合、各 に対して、 が と合同であるかどうかを推測して確認し、中国剰余定理を使用してを復元するというものである。 ${\displaystyle q}$${\displaystyle n}$${\displaystyle q=q_{1}q_{2}\cdots q_{t}}$${\displaystyle q_{\ell }}$${\displaystyle \mathbf {s} _{j}}$${\displaystyle 0\mod q_{\ell }}$${\displaystyle \mathbf {s} _{j}}$

Regev ^[3]は、任意のおよびに対してLWE問題とDLWE問題のランダム自己還元可能性を示した。からのサンプルが与えられた場合、が からのサンプルであることが簡単にわかる。 ${\displaystyle q}$${\displaystyle \chi }$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}$${\displaystyle A_{\mathbf {s} ,\chi }}$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}$${\displaystyle A_{\mathbf {s} +\mathbf {t} ,\chi }}$

そこで、となるような集合があり、 の分布に対して となると、DLWE は簡単です。 ${\displaystyle {\mathcal {S}}\subset \mathbb {Z} _{q}^{n}}$${\displaystyle |{\mathcal {S}}|/|\mathbb {Z} _{q}^{n}|=1/\operatorname {poly} (n)}$${\displaystyle A_{\mathbf {s} ',\chi }}$${\displaystyle \mathbf {s} '\leftarrow {\mathcal {S}}}$

そうすると、サンプル が与えられたときに、それが一様ランダムか からのものかを見分けることができる何らかの判別器 が存在することになります。 が から一様ランダムに選択される一様ランダムサンプルを から区別する必要がある場合、から一様ランダムにサンプリングされたさまざまな値を試し、 を計算してこれらのサンプルを に入力するだけで済みます。は の大部分を占めるので、 に対して多項式数の値を選択すると、 となるような値を見つける確率が高くなり、サンプルをうまく区別できるようになります。 ${\displaystyle {\mathcal {A}}}$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}$${\displaystyle A_{\mathbf {s} ',\chi }}$${\displaystyle A_{\mathbf {s} ,\chi }}$${\displaystyle \mathbf {s} }$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle \mathbf {t} }$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle \mathbf {t} }$${\displaystyle \mathbf {s} +\mathbf {t} \in {\mathcal {S}}}$${\displaystyle {\mathcal {A}}}$

したがって、そのようなものは存在できず、LWEとDLWE は(多項式係数まで) 平均的なケースでも最悪のケースと同じくらい困難であることを意味します。 ${\displaystyle {\mathcal {S}}}$

n次元格子について、平滑化パラメータ がとなる最小の を表すものとします。ここで はの双対であり、 は集合の各要素における関数値 を合計することによって集合 に拡張されます。が格子および実数について幅 のにおける離散ガウス分布 を表すものとします。それぞれの確率は に比例します。 ${\displaystyle L}$ ${\displaystyle \eta _{\varepsilon }(L)}$${\displaystyle s}$${\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \varepsilon }$${\displaystyle L^{*}}$${\displaystyle L}$${\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}$${\displaystyle D_{L,r}}$${\displaystyle L}$${\displaystyle r}$${\displaystyle L}$${\displaystyle r>0}$${\displaystyle x\in L}$${\displaystyle \rho _{r}(x)}$

離散ガウスサンプリング問題( DGS) は次のように定義されます: のインスタンスは、次元格子と数によって与えられます。目標は、 からサンプルを出力することです。Regev は、任意の関数 に対してからへの簡約が存在することを示しています。 ${\displaystyle DGS_{\phi }}$${\displaystyle n}$${\displaystyle L}$${\displaystyle r\geq \phi (L)}$${\displaystyle D_{L,r}}$${\displaystyle \operatorname {GapSVP} _{100{\sqrt {n}}\gamma (n)}}$${\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}}$${\displaystyle \gamma (n)\geq 1}$

Regev は次に、となる整数 のオラクルへのアクセスが与えられた場合、効率的な量子アルゴリズムが存在することを示します。これは、LWE の困難性を意味します。この主張の証明は任意の に対して有効ですが、暗号システムを作成するには、係数がの多項式でなければなりません。 ${\displaystyle DGS_{{\sqrt {2n}}\eta _{\varepsilon }(L)/\alpha }}$${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$${\displaystyle q}$${\displaystyle \alpha \in (0,1)}$${\displaystyle \alpha q>2{\sqrt {n}}}$${\displaystyle q}$${\displaystyle q}$${\displaystyle n}$

Peikertは^[4]、最悪の場合の問題からパラメータ、、およびのサンプルを使用して解く確率的多項式時間削減があることを証明しています。 ${\displaystyle \operatorname {GapSVP} _{\zeta ,\gamma }}$${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$${\displaystyle \operatorname {poly} (n)}$${\displaystyle \alpha \in (0,1)}$${\displaystyle \gamma (n)\geq n/(\alpha {\sqrt {\log n}})}$${\displaystyle \zeta (n)\geq \gamma (n)}$${\displaystyle q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {\log n}})}$

LWE問題は、いくつかの^{[3] [4] [6] [7]}暗号システムの構築に使用される汎用的な問題です。2005年にRegev ^[3]は、格子問題 （上記のように）およびの量子困難性を仮定すると、LWEの決定バージョンが困難であることを示しました。2009年にPeikert ^[4]は、関連問題 の古典的困難性のみを仮定して同様の結果を証明しました。Peikertの結果の欠点は、それが（SIVPと比較すると）より簡単な問題GapSVPの非標準バージョンに基づいていることです。 ${\displaystyle \mathrm {GapSVP} _{\gamma }}$${\displaystyle \gamma }$${\displaystyle \mathrm {SIVP} _{t}}$${\displaystyle t=O(n/\alpha )}$${\displaystyle \mathrm {GapSVP} _{\zeta ,\gamma }}$

Regev ^[3]はLWE問題の困難性に基づく公開鍵暗号システムを提案した。この暗号システムと安全性および正しさの証明は完全に古典的なものである。このシステムは と上の確率分布によって特徴付けられる。正しさと安全性の証明に使用されるパラメータの設定は ${\displaystyle m,q}$${\displaystyle \chi }$${\displaystyle \mathbb {T} }$

• ${\displaystyle q\geq 2}$通常はからまでの素数です。${\displaystyle n^{2}}$${\displaystyle 2n^{2}}$
• ${\displaystyle m=(1+\varepsilon )(n+1)\log q}$任意の定数${\displaystyle \varepsilon }$
• ${\displaystyle \chi =\Psi _{\alpha (n)}}$の場合、 は、平均と標準偏差を持つ正規変数をサンプリングし、その結果を で割って得られる確率分布です。${\displaystyle \alpha (n)\in o(1/{\sqrt {n}}\log n)}$${\displaystyle \Psi _{\beta }}$${\displaystyle 0}$${\displaystyle {\frac {\beta }{\sqrt {2\pi }}}}$${\displaystyle 1}$

暗号システムは次のように定義されます。

• 秘密鍵: 秘密鍵は均一にランダムに選択されます。${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$
• 公開鍵:ベクトルを一様かつ独立に選択します。誤差オフセットはに従って独立に選択します。公開鍵は${\displaystyle m}$${\displaystyle \mathbf {a} _{1},\ldots ,\mathbf {a} _{m}\in \mathbb {Z} _{q}^{n}}$${\displaystyle e_{1},\ldots ,e_{m}\in \mathbb {T} }$${\displaystyle \chi }$${\displaystyle (\mathbf {a} _{i},b_{i}=\langle \mathbf {a} _{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}}$
• 暗号化: ビットの暗号化はランダムなサブセットを選択し、次のように定義することによって行われます。${\displaystyle x\in \{0,1\}}$${\displaystyle S}$${\displaystyle [m]}$${\displaystyle \operatorname {Enc} (x)}$

${\displaystyle \left(\sum _{i\in S}\mathbf {a} _{i},{\frac {x}{2}}+\sum _{i\in S}b_{i}\right)}$

• 復号化:が よりもに近い場合、の復号化はであり、それ以外の場合は です。${\displaystyle (\mathbf {a} ,b)}$${\displaystyle 0}$${\displaystyle b-\langle \mathbf {a} ,\mathbf {s} \rangle /q}$${\displaystyle 0}$${\displaystyle {\frac {1}{2}}}$${\displaystyle 1}$

正しさの証明は、パラメータの選択といくつかの確率分析から得られます。安全性の証明は、LWEの決定バージョンへの還元によって行われます。これは、（上記のパラメータを持つ）の暗号化を区別するためのアルゴリズムであり、およびを区別するために使用できます。および上の一様分布${\displaystyle 0}$${\displaystyle 1}$${\displaystyle A_{s,\chi }}$${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$

Peikert ^{[4]は、あらゆる}選択暗号文攻撃に対しても安全なシステムを提案した。

LWEとリングLWEを鍵交換に使用するというアイデアは、2011年にシンシナティ大学のJintai Dingによって提案され、提出されました。このアイデアは行列乗算の結合性から生まれたもので、誤差を利用してセキュリティを提供します。この論文^[8]は、2012年に仮特許出願が提出された後、2012年に発表されました。

プロトコルのセキュリティは、LWE 問題を解くことの難しさに基づいて証明されています。2014 年に、Peikert は Ding と同じ基本的なアイデアに従ったキー転送方式^[9]を発表しました。この方式では、Ding の構築で丸めのために追加の 1 ビット信号を送信するという新しいアイデアも使用されています。Googleのポスト量子実験^{[11 ] に選択された「新しい希望」実装[10]}は、エラー分布に変化のある Peikert の方式を使用しています。

メイン記事:エラー署名付きリング学習

古典的なFeige–Fiat–Shamir 識別プロトコルの RLWE バージョンは、2011 年に Lyubashevsky によって作成され、デジタル署名に変換されました。この署名の詳細は、2012 年に Gunesyu、Lyubashevsky、および Popplemann によって拡張され、論文「実用的な格子ベースの暗号化 - 組み込みシステム向けの署名スキーム」で公開されました。これらの論文は、エラーのあるリング学習問題に直接基づくものや、同じ困難な RLWE 問題に結び付けられていないものなど、最近のさまざまな署名アルゴリズムの基礎を築きました。

• 耐量子暗号
• エラーのあるリング学習
• 格子ベースの暗号
• エラーのあるリング学習と鍵交換
• 短整数解（SIS）問題
• カイバー