間違いから学ぶ

Mathematical problem in cryptography

暗号学において、誤り学習（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問題は、ペイケルトによる誤りを含む鍵交換を伴うリング学習[ ^{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の決定版への還元によって行われる。LWEとは、（上記のパラメータを持つ）の暗号化を区別するアルゴリズムであり、そしてを区別するために使用できる。そして、上の一様分布は、 ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle A_{s,\chi }}$ ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$

CCAセキュア暗号システム

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

鍵交換

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

このプロトコルの安全性は、LWE問題の解の難しさに基づいて証明されています。2014年、PeikertはDingの基本的なアイデアに基づいた鍵転送方式^[9]を発表しました。この方式では、Dingの構築において丸め処理のために1ビットの信号を追加するという新しいアイデアも採用されています。Googleのポスト量子実験^{[11 ]に選ばれた「New Hope」実装[10]}は、誤り分布に変化を持たせたPeikertの方式を採用しています。

エラー署名付きリング学習 (RLWE-SIG)

古典的なフェイジ・フィアット・シャミール識別プロトコルのRLWE版は、 2011年にリュバシェフスキーによって作成され、デジタル署名に変換されました。この署名の詳細は、2012年にグネシュユ、リュバシェフスキー、ポプルマンによって拡張され、論文「実用的な格子ベース暗号 - 組み込みシステム向け署名スキーム」として発表されました。これらの論文は、リング学習の誤り問題に直接基づくものもあれば、RLWEの困難な問題とは結びつかないものもある、近年の様々な署名アルゴリズムの基礎を築きました。

参照

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

参考文献

1. Regev, Oded (2009). 「格子、エラー学習、ランダム線形符号、そして暗号について」. Journal of the ACM . 56 (6): 1– 40. arXiv : 2401.03703 . doi :10.1145/1568318.1568324. S2CID  207156623.
2. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2013年11月). 「理想格子と環上の誤差学習について」 . Journal of the ACM . 60 (6): 1– 35. doi :10.1145/2535925. ISSN  0004-5411. S2CID  1606347.
3. Oded Regev、「格子、エラー学習、ランダム線形符号、暗号化について」、第37回ACMコンピューティング理論シンポジウム議事録（米国メリーランド州ボルチモア：ACM、2005年）、84–93、http://portal.acm.org/citation.cfm?id=1060590.1060603。
4. Chris Peikert、「最悪ケースの最短ベクトル問題からの公開鍵暗号システム：拡張概要」、第41回ACMコンピューティング理論シンポジウム議事録（米国メリーランド州ベセスダ：ACM、2009年）、333–342、http://portal.acm.org/citation.cfm?id=1536414.1536461。
5. Peikert, Chris (2014-10-01). 「インターネットのための格子暗号」. Mosca, Michele (編).ポスト量子暗号. コンピュータサイエンス講義ノート. 第8772巻. Springer International Publishing. pp.  197– 219. CiteSeerX 10.1.1.800.4743 . doi :10.1007/978-3-319-11659-4_12. ISBN  978-3-319-11658-7. S2CID  8123895。
6. Chris Peikert と Brent Waters、「Lossy trapdoor functions and their applications」、第 40 回 ACM コンピューティング理論シンポジウムの議事録 (ビクトリア、ブリティッシュ コロンビア、カナダ: ACM、2008)、187-196、http://portal.acm.org/citation.cfm?id=1374406。
7. Craig Gentry、Chris Peikert、Vinod Vaikuntanathan、「ハード格子のトラップドアと新しい暗号構造」、第40回ACMコンピューティング理論シンポジウム議事録（ビクトリア、ブリティッシュコロンビア、カナダ：ACM、2008年）、197-206、http://portal.acm.org/citation.cfm?id=1374407。
8. Lin, Jintai Ding, Xiang Xie, Xiaodong (2012-01-01). 「誤り学習問題に基づく、シンプルで証明可能な安全な鍵交換方式」. Cryptology ePrint Archive .{{cite journal}}: CS1 maint: multiple names: authors list (link)
9. Peikert, Chris (2014-01-01). 「インターネットのための格子暗号」. Cryptology ePrint Archive .
10. Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01). 「ポスト量子鍵交換 - 新たな希望」. Cryptology ePrint Archive .
11. 「ポスト量子暗号の実験」。Googleオンラインセキュリティブログ。 2017年2月8日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Learning_with_errors&oldid=1321958564"