エラーのあるリング学習

ポスト量子暗号において、エラー付きリング学習（RLWE）は、量子コンピュータによる暗号解読を防ぎ、準同型暗号化の基礎を提供するように設計された、 NewHopeなどの新しい暗号化アルゴリズムの基礎となる計算問題です。 公開鍵暗号化は、それ以上の情報がなければ解くのが難しいと考えられているが、問題構築に使用された一部の情報がわかっている場合は簡単に解ける数学的問題の構築に依存しています。現在暗号化で使用されているこの種の問題の一部は、十分に大きな量子コンピュータが構築された場合に攻撃を受けるリスクがあるため、耐性のある問題が求められています。

RLWE は、より正確には環上のエラー付き学習と呼ばれ、有限体上の多項式環に特化した、より大きなエラー付き学習(LWE) 問題です。 ^[1] 量子コンピュータでも RLWE 問題を解くのは困難であると想定されているため、整数因数分解と離散対数問題が 1980 年代初頭から公開鍵暗号の基礎となってきたのと同様に、RLWE ベースの暗号は将来、公開鍵暗号の基礎となる可能性があります。^{[2]暗号を環上のエラー付き学習問題に基づくものとする重要な特徴は、RLWE 問題の解が格子内の}最短ベクトル問題(SVP) のバージョンを解くために使用できることです(この SVP 問題から RLWE 問題への多項式時間縮減が提示されています^[1] )。

現代の暗号、特に公開鍵暗号の安全性は、問題のサイズが十分に大きく、解決すべき問題のインスタンスがランダムに選択される場合、特定の計算問題を解決することは困難であるという仮定に基づいています。1970年代から使用されてきた古典的な例は、整数因数分解問題です。2つの素数が十分に大きく、ランダムに選択された場合、それらの素数の積を因数分解することは計算上困難であると考えられています。^[3] 2015年現在、研究により、2つの384ビット素数の積の因数分解は実現されていますが、2つの512ビット素数の積は実現されていません。整数因数分解は、広く使用されているRSA暗号化アルゴリズムの基礎を形成しています。

エラー付き環学習（RLWE）問題は、有限体からの係数を持つ多項式の算術に基づいています。^[1] 典型的な多項式は次のように表現されます。 ${\textstyle a(x)}$

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

多項式は通常の方法で加算および乗算できます。RLWE コンテキストでは、多項式の係数とそれらの係数を含むすべての演算は有限体、通常は素数 の体で実行されます。加算と乗算の演算を含む有限体上の多項式の集合は、無限多項式環( ) を形成します。RLWE コンテキストは、この無限環の有限商環を扱います。商環は通常、既約多項式 を法としてすべての多項式を約分することによって形成される有限商 (因数) 環です。この有限商環は、多くの著者が と書くかのように書くことができます。^[1]${\textstyle \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q}}$${\textstyle q}$${\textstyle \mathbf {F} _{q}[x]}$${\textstyle \mathbf {F} _{q}[x]}$ ${\textstyle \Phi (x)}$${\displaystyle \mathbf {F} _{q}[x]/\ファイ (x)}$${\displaystyle \mathbf {Z} _{q}[x]/\ファイ (x)}$

多項式の次数が の場合、商環はからの係数を持つ を法とした未満の次数の多項式の環になります。値、は、多項式とともに、RLWE 問題の数学的コンテキストを部分的に定義します。 ${\displaystyle \Phi (x)}$${\textstyle n}$${\displaystyle n}$${\displaystyle \Phi (x)}$${\displaystyle F_{q}}$${\textstyle n}$${\textstyle q}$${\displaystyle \Phi (x)}$

RLWE 問題に必要なもう 1 つの概念は、あるノルムに関する「小さな」多項式という概念です。RLWE 問題で使用される一般的なノルムは、無限大ノルム (一様ノルムとも呼ばれます) として知られています。多項式の無限大ノルムは、これらの係数を整数として見た場合の、多項式の最大係数です。したがって、 は、多項式の無限大ノルムが であることを示しています。したがって、 の最大係数は です。 ${\displaystyle ||a(x)||_{\infty }=b}$${\displaystyle a(x)}$${\displaystyle b}$${\displaystyle b}$${\displaystyle a(x)}$

RLWE 問題を理解するために必要な最後の概念は、 におけるランダム多項式の生成と「小さな」多項式の生成です。 ランダム多項式は、から多項式の係数をランダムにサンプリングするだけで簡単に生成できます。ここで、 は通常、集合 として表されます。 ${\displaystyle \mathbf {F} _{q}[x]/\ファイ (x)}$${\displaystyle n}$${\displaystyle \mathbf {F} _{q}}$${\displaystyle \mathbf {F} _{q}}$${\displaystyle \{-(q-1)/2,...,-1,0,1,...,(q-1)/2\}}$

「小さな」多項式をランダムに生成するには、 から多項式の係数を、係数が小さいことを保証するか、または非常に小さい可能性の高い方法で生成します。が素数の場合、これを行う一般的な方法は 2 つあります。 ${\displaystyle \mathbf {F} _{q}}$${\displaystyle q}$

1. 均一サンプリングの使用 – 小さな多項式の係数は、小さな係数のセットから均一にサンプリングされます。を よりはるかに小さい整数とします。 セットから係数をランダムに選択すると、多項式は境界 ( ) に対して小さくなります。${\textstyle b}$${\textstyle q}$${\textstyle \{-b,-b+1,-b+2,\ldots ,-2,-1,0,1,2,\ldots ,b-2,b-1,b\}}$${\textstyle b}$
2. 離散ガウスサンプリングの使用– の値が奇数の場合、多項式の係数は、平均と分布パラメータを持つ離散ガウス分布に従って集合からサンプリングすることによりランダムに選択されます。参考文献には、これを実現する方法が詳細に説明されています。これは均一サンプリングよりも複雑ですが、アルゴリズムのセキュリティを証明できます。Dwarakanath と Galbraith による論文「制約付きデバイスでの格子ベース暗号化のための離散ガウスからのサンプリング」では、この問題の概要が説明されています。^[4]${\textstyle q}$${\textstyle \{-(q-1)/2,\ldots ,(q-1)/2\}}$${\displaystyle 0}$${\textstyle \sigma }$

RLWE問題は、「探索」バージョンと「決定」バージョンの2つの異なる方法で表現できます。どちらも同じ構成から始まります。

• ${\displaystyle a_{i}(x)}$を のすべての係数を持つからのランダムだが既知の多項式の集合とする。${\displaystyle \mathbf {F} _{q}[x]/\ファイ (x)}$${\displaystyle \mathbf {F} _{q}}$
• ${\displaystyle e_{i}(x)}$環内の境界に対する小さなランダムかつ未知の多項式の集合とする。${\displaystyle b}$${\displaystyle \mathbf {F} _{q}[x]/\ファイ (x)}$
• ${\displaystyle s(x)}$環内の境界に対する小さな未知の多項式とする。${\displaystyle b}$${\displaystyle \mathbf {F} _{q}[x]/\ファイ (x)}$
• ${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$。

検索バージョンでは、多項式ペアのリストが与えられた場合に、未知の多項式を見つけます。 ${\displaystyle s(x)}$${\displaystyle (a_{i}(x),b_{i}(x))}$

問題の決定バージョンは、次のように記述できます。多項式のペアのリストが与えられた場合、多項式が として構築されたか、のすべての係数を使用してからランダムに生成されたかを判断します。 ${\displaystyle (a_{i}(x),b_{i}(x))}$${\displaystyle b_{i}(x)}$${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$${\displaystyle \mathbf {F} _{q}[x]/\ファイ (x)}$${\displaystyle \mathbf {F} _{q}}$

この問題の難しさは、商多項式 ( )、その次数 ( )、体 ( )、および小ささの境界 ( ) の選択によってパラメータ化されます。多くの RLWE ベースの公開鍵アルゴリズムでは、秘密鍵は小さな多項式 と のペアになります。対応する公開鍵は、 、および多項式からランダムに選択された多項式 のペアになります。 および が与えられた場合、多項式 を復元することは計算上不可能であるはずです。 ${\displaystyle \Phi (x)}$${\displaystyle n}$${\displaystyle \mathbf {F} _{q}}$${\displaystyle b}$${\displaystyle s(x)}$${\displaystyle e(x)}$${\displaystyle a(x)}$${\displaystyle \mathbf {F} _{q}[x]/\ファイ (x)}$${\displaystyle t(x)=(a(x)\cdot s(x))+e(x)}$${\displaystyle a(x)}$${\displaystyle t(x)}$${\displaystyle s(x)}$

多項式が円分多項式である場合、RLWE問題の探索バージョンを解く難しさは、整数ベクトルとして表される の要素から形成された理想的な格子内の短いベクトル（必ずしも最短ベクトルではない）を見つけることと同等です。^[1] この問題は一般に近似最短ベクトル問題（α-SVP）として知られており、最短ベクトルのα倍よりも短いベクトルを見つける問題です。この同値性の証明の著者は次のように書いています。 ${\displaystyle \Phi (x)}$${\displaystyle \mathbf {Z} [x]/\ファイ (x)}$

「...我々は、（最悪の場合の）理想格子上の近似SVPからリングLWEの探索バージョンへの量子還元を与える。ここでの目標は、任意の数のノイズのある積から秘密を（任意のに対して高い確率で）回復することである。」 ${\displaystyle \mathbf {R} }$${\displaystyle s\in \mathbf {R} _{q}}$${\displaystyle s}$^[1]

その引用では、指輪はであり、指輪はです。 ${\displaystyle \mathbf {R} }$${\displaystyle \mathbf {Z} [x]/\ファイ (x)}$${\displaystyle \mathbf {R} _{q}}$${\displaystyle \mathbf {F} _{q}[x]/\ファイ (x)}$

正則格子におけるα-SVPは、2001年のDaniele Micciancioの研究によりNP困難であることが知られていますが、一般的なエラー問題への還元に必要なαの値についてはNP困難ではありません。 ^[5] しかし、理想格子におけるα-SVPの難しさが平均α-SVPと同等であることを示す証明はまだありません。むしろ、理想格子で解決するのが難しいα-SVPインスタンスがある場合、RLWE問題はランダムインスタンスで困難になるという証明があります。 [ ^1]

理想格子における最短ベクトル問題の難しさについて、研究者のマイケル・シュナイダーは「今のところ、理想格子の特殊な構造を利用する SVP アルゴリズムは存在しない。理想格子における SVP (および他のすべての格子問題) の解決は、通常の格子におけるのと同じくらい難しいと広く信じられている」と書いている。^[6] 通常の格子におけるこれらの問題の難しさは、NP 困難であることが証明されている。^[5] しかし、少数の研究者は、理想格子が通常の格子と同じセキュリティ特性を共有していると信じていない。^[7]

Peikert は、これらのセキュリティ等価性により、RLWE 問題は将来の暗号の優れた基礎となると考えています。彼は次のように書いています。 「(何らかの正式な攻撃モデルの範囲内で) ランダムなインスタンスで暗号システムを破る唯一の方法は、最悪の場合 に基礎となる格子問題を解決することであるという数学的証明があります」 (強調は原文のまま)。^[8]

RLWE ベースの暗号化が、エラーを伴わない学習 (LWE) ベースの暗号化に比べて優れている点は、公開鍵と秘密鍵のサイズです。RLWE 鍵は、LWE の鍵の平方根とほぼ同じです。^[1] 128ビットのセキュリティを実現するために、RLWE 暗号化アルゴリズムでは約 7000 ビットの長さの公開鍵を使用します。^[9] 対応する LWE 方式では、同じレベルのセキュリティを実現するために 4900 万ビットの公開鍵が必要になります。^{[1] [検証失敗]} 一方、RLWE 鍵は、128 ビット レベルのセキュリティを実現するために、それぞれ 3072 ビットと 256 ビットの公開鍵サイズを必要とする RSA や楕円曲線 Diffie-Hellman などの現在使用されている公開鍵アルゴリズムの鍵サイズよりも大きくなります。ただし、計算の観点からは、RLWE アルゴリズムは既存の公開鍵システムと同等かそれ以上であることが示されています。^[10]

RLWE 暗号化アルゴリズムには 3 つのグループがあります。

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

2014年に、Peikert ^[12]は、Dingの同じ基本的なアイデアに従った鍵転送方式を発表しました。この方式では、Dingの構築における丸めのために追加の1ビット信号を送信するという新しいアイデアも活用されています。Diffie-Hellman鍵交換の古典的なMQVバリアントのRLWEバージョンは、後にZhangらによって公開されました。^[13] 両方の鍵交換のセキュリティは、理想的な格子内の近似短ベクトルを見つける問題に直接関係しています。

古典的なフェイジ・フィアット・シャミール識別プロトコルのRLWE版は、2011年にリュバシェフスキーによって作成され、デジタル署名に変換されました。^[14] この署名の詳細は、2012年にグネシュ、リュバシェフスキー、ポップルマンによって拡張され、論文「実用的な格子ベース暗号化 - 組み込みシステム向け署名スキーム」で発表されました。^[15] これらの論文は、リング学習のエラー問題に直接基づくものや、同じ困難なRLWE問題に結び付けられていないものなど、最近のさまざまな署名アルゴリズムの基礎を築きました。^[16]

準同型暗号化は、暗号化されたデータを復号化せずに計算を実行できる暗号化の一種です。準同型暗号化の目的は、機密データの計算を、そのデータを信頼すべきではないコンピューティング デバイスで実行できるようにすることです。これらのコンピューティング デバイスは、準同型暗号化から出力される暗号文を処理できます。2011 年に、Brakesky と Vaikuntanathan は、「リング LWE からの完全準同型暗号化とキー依存メッセージのセキュリティ」を発表しました。これは、RLWE 問題に直接準同型暗号化スキームを構築したものです。^[17]