量子コンピューターでも解けない暗号について

それは格子暗号です。

格子暗号の概念図を図に示します。格子とは、図ののように空間内に規則的に並んだ点の集合（図は2次元空間の例）であり、コンピュータの内部ではベクトルの集合（図中の黒矢印の組）として表現されます。このベクトルを適当に整数倍して足すことで、すべての格子点を網羅することができます。

耐量子計算機暗号の候補となっているいくつかの暗号方式に対して、このような評価を行うことにより、実用化の場面ごとに最適な方式を選ぶための基準作りを行うことができます。 

ラティスベースの暗号化は、1990年代半ばに、Ajtai-Dwork [1]とHoffstein-Pipher-Silverman [12]によって、2つの異なる形式で導入されました。 Stehl'e-Steinfeldの作業[19]のおかげで、Hoffstein-Pipher-Silvermanによって導入されたNTRU暗号システムは、エラーを伴う学習（Ring Learning With Error）（RLWE）問題に対してセキュリティが低下した暗号システムの変形であることがわかりました。 RLWE問題はLWE問題[17]のバージョンとして[14]で紹介されました：両方の問題はハードラティス問題への帰結を持っています、そしてそれ故に暗号の実用的なアプリケーションのために興味深いです。 ＲＬＷＥはナンバーリングＲ、モジュラスｑ、および誤差分布に依存する。このように、それは構造（リング）を追加しました。それはより大きな効率を可能にしますが、場合によっては追加の攻撃も可能にします。 RLWEの硬さは、特に多数の準同型暗号化方式の基礎として、暗号化にとって非常に重要です[2,3,4,5,6,13,19]。この方向での1つの主要な理論的結果は[14]の安全性低減定理であり、RLWE誤差分布が十分に大きく規定された形式のとき、R上の理想的な格子におけるある種のGapSVP問題をRLWEに低減する。今までのところ実用的な暗号アプリケーションではサイクロトミックリングだけが使用されていますが、パラメータ空間における安全性の境界を理解するために、一般数環、モジュラスおよびエラー分布に対するRLWEの硬さを研究することは重要です。最近、ある数の環、誤差分布、および特別な係数に対するRLWE問題のいわゆる非双対離散型に対する新しい攻撃が導入されました[7、8、9、10、11]。 RLWE問題は、その離散的なarXivに帰着します。1710.03316v1 [cs.CR] 2017年10月9日。そして、非双対ＲＬＷＥ問題は、誤り分布の変化までの双対問題と等価であり、そのため、非双対ＲＬＷＥは、単にＲＬＷＥのパラメータ空間における誤り分布の特定の選択として見ることができる。 RLWEという用語は、球面ガウス分布のために予約されていることがあります。この論文は[9]の拡張であり、ここで我々は様々なナンバーリングのためのRLWE問題の非双対離散変種の難しさをさらに探ります。