エラーのあるリング学習と鍵交換

暗号学において、公開鍵交換アルゴリズムは、2 つのパーティが秘密鍵を作成して共有し、その秘密鍵を使用してメッセージを暗号化できるようにする暗号アルゴリズムです。リング学習付きエラー鍵交換( RLWE-KEX ) は、量子コンピュータを所有する敵に対して安全であるように設計された、新しいクラスの公開鍵交換アルゴリズムの 1 つです。これが重要なのは、現在使用されている公開鍵アルゴリズムの一部は、量子コンピュータが実装された場合、そのようなコンピュータによって簡単に破られてしまうためです。RLWE -KEX は、格子を含む特定の数学的問題を解決することの難しさに基づいた一連のポスト量子暗号アルゴリズムの 1 つです。古い格子ベースの暗号アルゴリズムとは異なり、RLWE -KEX は、格子の既知の難問に証明可能に還元できます。

1980 年代以降、インターネットを介した暗号鍵交換とデジタル署名のセキュリティは、主に少数の公開鍵アルゴリズムに基づいてきました。これらのアルゴリズムのセキュリティは、同様に少数の、古典的コンピューティングにおける計算上困難な問題に基づいています。これらの問題とは、慎重に選ばれた 2 つの素数の積を因数分解する難しさ、慎重に選ばれた有限体における離散対数を計算する難しさ、慎重に選ばれた楕円曲線群における離散対数を計算する難しさです。これらの問題は、古典的コンピュータ (1940 年代から今日まで世界中で知られているタイプのコンピュータ) で解くのは非常に困難ですが、5 千から 1 万ビットのメモリしか使用しない比較的小型の量子コンピュータでは、むしろ簡単に解けます。コンピュータ業界では、2030 年頃にはより大規模な量子コンピュータが利用可能になるという楽観的な見方があります。十分なサイズの量子コンピュータが構築された場合、これら 3 つの古典的に困難な問題に基づく公開鍵アルゴリズムはすべて安全ではなくなります。この公開鍵暗号化は現在、インターネット Web サイトのセキュリティ保護、コンピュータのログイン情報の保護、コンピュータが悪意のあるソフトウェアを受け入れるのを防ぐ目的で使用されています。

量子コンピュータによる攻撃を受けない暗号は、量子耐性暗号、またはポスト量子暗号と呼ばれます。量子耐性暗号アルゴリズムの1つのクラスは、2005年にOded Regevによって導入された「エラー付き学習」と呼ばれる概念に基づいています。 ^[1] エラー付き学習の特殊な形式は、有限体上の多項式環内で動作します。この特殊な形式は、エラー付き環学習またはRLWEと呼ばれます。

RLWEパラダイムを使用して動作する暗号化アルゴリズムは多種多様です。この記事で紹介した公開鍵、鍵交換アルゴリズムに加えて、公開鍵暗号化アルゴリズム、準同型暗号化アルゴリズム、RLWEデジタル署名アルゴリズムがあります。

鍵交換アルゴリズムは、通信リンク上の 2 人の通信者間で共有秘密鍵を確立する公開鍵アルゴリズムの一種です。鍵交換の典型的な例は、Diffie-Hellman 鍵交換です。この交換は、回線の一方の端からの 1 回の送信と、リンクのもう一方の端からの 1 回の送信で構成されます。Diffie -Hellmanと楕円曲線 Diffie-Hellmanは、2 つの最も一般的な鍵交換アルゴリズムです。

RLWE キー交換は、信頼できない通信チャネル上で秘密キーを確立するために広く使用されているDiffie- Hellman キー交換と楕円曲線 Diffie-Hellmanキー交換の「量子耐性」代替として設計されています。Diffie-Hellman や楕円曲線 Diffie-Hellman と同様に、Ring-LWE キー交換は「前方秘匿性」と呼ばれる暗号化特性を提供します。その目的は、大量監視プログラムの有効性を低減し、大量の復号化を可能にするような侵害を受ける可能性のある長期秘密キーが存在しないようにすることです。

素整数 qから始めて、Ring-LWE鍵交換は、 を法とする整数体 の係数を持つ多項式を法とする多項式環 (つまり、環)で機能します。多項式の乗算と加算は、乗算結果を法として簡約した通常の方法で機能します。 ${\displaystyle \Phi (x)}$${\displaystyle R_{q}:=Z_{q}[x]/\ファイ (x)}$${\displaystyle \Phi (x)}$

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

2014年に、PeikertはDingの同じ基本的なアイデアに従った鍵転送方式^[3]を発表しました。この方式では、Dingの構築における丸めのために追加の1ビット信号を送信するという新しいアイデアも使用されています。

Googleのポスト量子実験^[5 ]に選択された「New Hope」実装^[4]は、誤差分布に変化を持たせたPeikertの方式を採用している。

128ビットよりいくらか大きいセキュリティのために、SinghはPeikertの方式で6956ビットの公開鍵を持つパラメータのセットを提示している。^[6]対応する秘密鍵はおよそ14,000ビットになる。Diffie-Hellman鍵交換の古典的なMQVバリアントのRLWEバージョンは、後にZhangらによって2014年に公開された。両方の鍵交換のセキュリティは、理想的な格子内の近似短ベクトルを見つける問題に直接関係している。この記事では、DingのRLWEの研究「エラーのある学習問題に基づくシンプルで証明可能な安全な鍵交換方式」^[2]を詳しく追っていく。 このプレゼンテーションでは、典型的な多項式は次のように表現される。

${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}$

この多項式の係数はqを法とする整数である 。この多項式は円分多項式となる。nが2の累乗のとき、 ^{[6] [7]}${\displaystyle a_{i}}$${\displaystyle \Phi (x)}$${\displaystyle \ファイ (x)=x^{n}+1.}$

RLWE-KEX は、「無限ノルム」と呼ばれる尺度に関して「小さい」と見なされる多項式を使用します。多項式の無限ノルムは、係数がZ内の整数 (つまり、集合 {−( q  − 1)/2,..., 0, ... ( q − 1)/2} から) と見なされる場合の、多項式の最大係数の値です。アルゴリズムのセキュリティは、無限ノルムに関して小さいランダムな多項式を生成する機能に依存します。これは、小さいことが保証されているか、非常に小さい可能性がある多項式 (s _n-1、...、s ₀ ) の係数をランダムに生成するだけで行われます。これを行うには、2 つの一般的な方法があります。 ${\displaystyle Zq}$

1. 均一サンプリングの使用– 小さな多項式の係数は、小さな係数の集合から均一にサンプリングされます。b はqよりはるかに小さい整数とします。集合 { − b、 −b + 1、 −b + 2、 ... −2、 −1、 0、 1、 2、 ... 、b  − 2、b  − 1、b } から係数をランダムに選択すると、多項式は境界 (b) に対して小さくなります。 Singh は b = 5 を使用することを提案しています。^{[6]したがって、係数は集合 {} q  − 5、q  − 4、q  − 3、q  − 2、q − 1、 0、 1、 2、 3、 4、 5 } から選択 されます。
2. 離散ガウスサンプリングの使用– q の値が奇数の場合、係数は 平均 0 および分布パラメータ σ の離散ガウス分布に従って、 集合 { −(q − 1)/2 から ( q − 1)/2 } からサンプリングしてランダムに選択されます。参考文献には、これがどのように達成されるかが詳細に説明されています。これは均一サンプリングよりも複雑ですが、アルゴリズムのセキュリティを証明できます。ガウスサンプリングの概要は、Peikert のプレゼンテーションに記載されています。^[8]

この記事の残りの部分では、ランダムな小さな多項式は、単にDとして指定される分布に従ってサンプリングされます。さらに、 q は奇数の素数であり、 q は 1 mod 4 および 1 mod 2n に一致します。 q と n のその他のケースについては、「リング LWE 暗号化ツールキット」および Singh の「ラティス暗号化を使用したインターネット用のさらに実用的な鍵交換」で詳しく説明されています。^{[9] [10]}および Singh の別の論文。ネットワークのすべてのユーザーが共有する固定の公開多項式 a(x)。これは、暗号的に安全なソースから決定論的に生成されます。

前述のようにa ( x )が与えられれば、公開鍵交換における「秘密鍵」として、小さな多項式s ( x ) とe ( x ) をランダムに選択することができます。対応する公開鍵は、多項式p ( x ) = a ( x ) s ( x ) + 2 e ( x )になります。

鍵交換は 2 つのデバイス間で行われます。鍵交換の開始者は (I) で、応答者は (R) で表されます。I と R は両方ともq、n、a ( x ) を知っており、パラメータ の分布に従って小さな多項式を生成することができます。分布は通常、リング 上の離散ガウス分布です。以下の説明には、鍵交換によってリンクの両端で同じ鍵が生成される理由については説明されていません。代わりに、実行する手順を簡潔に指定します。鍵交換によって開始者と応答者が同じ鍵を持つ理由を完全に理解するには、Ding らの参考文献 [ ^{2]を参照してください。}${\displaystyle \chi _{\alpha }}$${\displaystyle \alpha}$${\displaystyle \chi _{\alpha }}$${\displaystyle R_{q}=Z_{q}[x]/\ファイ (x)}$

鍵交換は、イニシエーター (I) が次の操作を行うことから始まります。

開始:

1. 分布 からサンプリングして、係数が小さい2 つの多項式と を生成します。${\displaystyle s_{I}}$${\displaystyle e_{I}}$${\displaystyle \chi _{\alpha }}$
2. 計算${\displaystyle p_{I}=as_{I}+2e_{I}.}$
3. イニシエーターは多項式をレスポンダーに送信します。${\displaystyle p_{I}}$

応答：

1. 分布 からサンプリングして、係数が小さい2 つの多項式と を生成します。${\displaystyle s_{R}}$${\displaystyle e_{R}}$${\displaystyle \chi _{\alpha }}$
2. 計算します。${\displaystyle p_{R}=as_{R}+2e_{R}}$
3. から小さな を生成します。 を計算します。 次に。${\displaystyle e'_{R}}$${\displaystyle \chi _{\alpha }}$${\displaystyle k_{R}=p_{I}s_{R}+2e'_{R}}$${\displaystyle k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}}$
4. 信号関数を使ってを求めます 。これはの各係数に 関数を適用して計算されます。${\displaystyle \operatorname {Sig} }$${\displaystyle w=\operatorname {Sig} (k_{R})}$${\displaystyle Sig}$${\displaystyle k_{R}}$
5. 応答側のキーストリームは、調整情報と多項式に基づいて計算されます。${\displaystyle sk_{R}=\operatorname {Mod} _{2}(k_{R},w)}$${\displaystyle w}$${\displaystyle k_{R}}$
6. 応答者は開始者にと を送信します。${\displaystyle p_{R}}$${\displaystyle w}$

仕上げる：

1. 応答者から受信します。${\displaystyle p_{R}}$${\displaystyle w}$
2. からサンプルを抽出し、計算します。${\displaystyle e'_{I}}$${\displaystyle \chi _{\alpha }}$${\displaystyle k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}}$
3. イニシエーター側のキーストリームは、調整情報と多項式から として生成されます。${\displaystyle sk_{I}=\operatorname {Mod} _{2}(k_{I},w)}$${\displaystyle w}$${\displaystyle k_{I}}$

上記の鍵交換では、シグナル関数は以下のように定義されます。 ${\displaystyle \operatorname {Sig} }$

のサブセットを定義します。ここで、およびはそれぞれ切り捨てと最も近い整数への丸めを表します。 ${\displaystyle \mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}}$${\displaystyle Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}}$${\displaystyle \lfloor .\rfloor }$${\displaystyle \lfloor .\rceil }$

関数はEの補関数の特性関数です。 ${\displaystyle \operatorname {Sig} }$

${\displaystyle \operatorname {Sig} :Zq\rightarrow \{0,1\}}$:${\displaystyle \operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}}$

${\displaystyle \operatorname {Mod} _{2}}$は、次のように定義される誤差項を除去する mod 2 演算です。${\displaystyle \operatorname {Mod} _{2}(v,w)={\biggl (}v+w.{\frac {q-1}{2}}{\Biggr )}{\bmod {q}}{\bmod {2}}}$

との値は ほぼ等しいだけであることに注意してください。このほぼ等しい値を使用して共有キーを抽出するために、信号関数とも呼ばれる調整関数が使用されます。この関数は、 の多項式の各係数が存在する領域を示し、と の誤差項が異なる mod q 演算をもたらさないことを確認するのに役立ちます。 ${\displaystyle k_{I}}$${\displaystyle k_{R}}$${\displaystyle v}$${\displaystyle R_{q}}$${\displaystyle k_{R}}$${\displaystyle k_{I}}$

照合とキー文字列生成の方法は、問題となっている特定のRLWE-KEXスキームによって異なります。一部の方法はモジュラー算術に基づいていますが、他の方法は高次元幾何学に基づいています。^{[6] [11]}

鍵交換が適切に機能した場合、発信者の文字列と応答者の文字列は同じになります。

選択されたパラメータの詳細に応じて、このキー交換で同じキーが生成されない可能性は極めて低くなります。キー交換のパラメータは、キー交換の失敗の可能性を非常に低くするように選択できます。これは、検出できない文字化けやデバイス障害の可能性よりもはるかに低くなります。

上で紹介した RLWE-KEX 交換は、多項式を法としてn  − 1 次以下の多項式環で動作しました。この説明では、n は 2 の累乗であり、q は 1 (mod 2n) と合同な素数であると仮定しました。Peikert の論文で示されたガイダンスに従って、Singh は RLWE-KEX の 2 セットのパラメータを提案しました。 ${\displaystyle \Phi (x)}$

128ビットのセキュリティの場合、n = 512、q = 25601、${\displaystyle \Phi (x)=x^{512}+1}$

256ビットのセキュリティの場合、n = 1024、q = 40961、${\displaystyle \Phi (x)=x^{1024}+1}$

鍵交換ではランダムサンプリングと固定境界を使用するため、鍵交換でイニシエーターとレスポンダーに同じ鍵が生成されない可能性がわずかにあります。ガウスパラメータσが均一サンプリング境界( b )=5(Singhを参照)と仮定すると、^[6] 、鍵合意失敗の確率は¹²⁸ビットのセキュアパラメータでは2-71未満、256ビットのセキュアパラメータでは2-91未満になり^ます。 ${\textstyle {\frac {8}{\sqrt {2\pi }}}}$

2015年11月の論文で、Alkim、Ducas、Pöppelmann、Schwabeは、n = 1024、q =12289、= x ¹⁰²⁴ + 1というパラメータを推奨しています。 ^[11]これは、Singhのn = 1024パラメータに比べて公開鍵のサイズが70%削減され、NewHopeという名前でNISTのポスト量子暗号標準化プロジェクトに提出されました。 ${\displaystyle \Phi (x)}$

また、2015 年 11 月の論文では、アルキム、デュカス、ペッペルマン、シュワベは、鍵交換の基本多項式 (上記の a(x)) の選択は、交換ごとに安全な乱数生成器からランダムに生成するか、「何も隠さない」または NUMS 技術を使用して検証可能な方法で作成することを推奨しています。^[11]この方法で生成されたパラメーターの例には、インターネット鍵交換 (RFC 2409) の素数があり、これは数学定数 pi の数字を素数のデジタル表現に埋め込みます。^[12]彼らの最初の方法は、多くの鍵交換にわたる攻撃コストの償却を防止しますが、Dan Bernstein が NIST 楕円曲線に対して説明したような隠れた攻撃の可能性を残すリスクがあります。^[13] NUMS アプローチは償却が可能ですが、pi や e などの一般的な数学定数のみが使用される場合は、通常、Bernstein 攻撃を回避します。

この鍵交換のセキュリティは、理想的な格子における最短ベクトル問題(SVP)の最悪解と同じくらい難しいことが証明されている、エラーを伴うリング学習問題の根底にある困難さに基づいています。^{[1] [2]} 特定の格子パラメータセットの実用的なセキュリティを測定する最良の方法は、BKZ 2.0 格子削減アルゴリズムです。^[14] BKZ 2.0 アルゴリズムによると、上記の鍵交換パラメータは、それぞれ 128 ビットまたは 256 ビットを超えるセキュリティを提供します。

2014年にダグラス・ステビラは、自身の研究と「リング学習エラー問題からのTLSプロトコルのポスト量子鍵交換」で発表された他の研究に基づいて、OpenSSL 1.0.1fのパッチを作成しました。^[15] Singhの研究を実装したソフトウェアは、GitHubのhttps://github.com/vscrypto/ringlweにあります。^[6]

上で説明したアプローチのバリエーションとして、Zhang、Zhang、Ding、Snook、Dagdelen の論文「理想格子からの量子後認証鍵交換」に認証バージョンが発表されています。^[16] 格子と調整機能を使用して Diffie-Hellman のような鍵交換を作成するという概念は、フランスの研究者 Aguilar、Gaborit、Lacharme、Schrek、Zemor が PQCrypto 2010 で「Noisy Diffie-Hellman Protocols」という講演で初めて発表したようです。^[17]

2015年11月、アルキム、デュカス、ポッペルマン、シュワベは、ペイカートの以前の研究を基に、格子攻撃のより保守的なコスト計算を使用してパラメータを推奨しました。^[11]アルキム、デュカス、ポッペルマン、シュワベの研究に基づいたソフトウェアは、GitHubのhttps://github.com/tpoeppelmann/newhopeにあります。^[11]

• 耐量子暗号
• 格子ベースの暗号
• 理想的な格子暗号
• エラー署名付きリング学習
• エラーのあるリング学習