(57)【要約】【課題】暗号プロトコルに用いられる２つの問題の間で、同等の安全性を持つように双方向にパラメータを導出できる設計装置、設計方法及び設計プログラムを提供すること。【解決手段】設計装置１は、計算の困難性に基づく２種類の暗号プロトコルにおいて、第１の暗号プロトコルが依拠する第１の問題を解くためのアルゴリズムによる計算量のオーダと、第２の暗号プロトコルが依拠する第２の問題を解くためのアルゴリズムによる計算量のオーダとを等式で結ぶことで得られるパラメータの関係式を記憶する記憶部２０と、第１の暗号プロトコルで設定される第１のパラメータ群の入力を受け付ける入力部１１と、第１のパラメータ群から、関係式により第２の暗号プロトコルで設定される第２のパラメータ群を導出する導出部１２と、第２のパラメータ群を出力する出力部１３と、を備える。【選択図】図１
2019113698.tif 000002
【特許請求の範囲】
【請求項１】
計算の困難性に基づく２種類の暗号プロトコルにおいて、第１の暗号プロトコルが依拠する第１の問題を解くためのアルゴリズムによる計算量のオーダと、第２の暗号プロトコルが依拠する第２の問題を解くためのアルゴリズムによる計算量のオーダとを等式で結ぶことで得られるパラメータの関係式を記憶する記憶部と、
前記第１の暗号プロトコルで設定される第１のパラメータ群の入力を受け付ける入力部と、
前記第１のパラメータ群から、前記関係式により前記第２の暗号プロトコルで設定される第２のパラメータ群を導出する導出部と、
前記第２のパラメータ群を出力する出力部と、を備える設計装置。
【請求項２】
前記第１の問題はＬｅａｒｎｉｎｇ  ｗｉｔｈ  Ｅｒｒｏｒｓ（ＬＷＥ）問題であり、前記第２の問題はＬｅａｒｎｉｎｇ  ｗｉｔｈ  Ｒｏｕｎｄｉｎｇ（ＬＷＲ）問題である請求項１に記載の設計装置。
【請求項３】
前記第１の問題を解くためのアルゴリズム及び前記第２の問題を解くためのアルゴリズムは、共通の計算アルゴリズムである請求項１又は請求項２に記載の設計装置。
【請求項４】
コンピュータが、
計算の困難性に基づく２種類の暗号プロトコルにおいて、第１の暗号プロトコルが依拠する第１の問題を解くためのアルゴリズムによる計算量のオーダと、第２の暗号プロトコルが依拠する第２の問題を解くためのアルゴリズムによる計算量のオーダとを等式で結ぶことで得られるパラメータの関係式を記憶し、
前記第１の暗号プロトコルで設定される第１のパラメータ群の入力を受け付ける入力ステップと、
前記第１のパラメータ群から、前記関係式により前記第２の暗号プロトコルで設定される第２のパラメータ群を導出する導出ステップと、
前記第２のパラメータ群を出力する出力ステップと、を実行する設計方法。
【請求項５】
コンピュータに、
計算の困難性に基づく２種類の暗号プロトコルにおいて、第１の暗号プロトコルが依拠する第１の問題を解くためのアルゴリズムによる計算量のオーダと、第２の暗号プロトコルが依拠する第２の問題を解くためのアルゴリズムによる計算量のオーダとを等式で結ぶことで得られるパラメータの関係式を記憶させ、
前記第１の暗号プロトコルで設定される第１のパラメータ群の入力を受け付ける入力ステップと、
前記第１のパラメータ群から、前記関係式により前記第２の暗号プロトコルで設定される第２のパラメータ群を導出する導出ステップと、
前記第２のパラメータ群を出力する出力ステップと、を実行させるための設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号プロトコルの設計装置、設計方法及び設計プログラムに関する。
【背景技術】
【０００２】
従来、暗号化、認証、鍵共有等のセキュリティ機能を実現するために、様々な暗号プロトコルが提案されている。また、これらの暗号プロトコルは、問題解読のための計算困難性を利用したものが多く、それぞれ用途に応じた適切な安全性を確保するためのパラメータが設定されて利用される。
【０００３】
例えば、量子計算機に耐性を持つと期待されている格子暗号に用いられるＬｅａｒｎｉｎｇ  ｗｉｔｈ  Ｅｒｒｏｒｓ（ＬＷＥ）問題は、非特許文献１で紹介されているように、最悪時格子問題への帰着が証明されている計算困難な問題である。
また、Ｌｅａｒｎｉｎｇ  ｗｉｔｈ  Ｒｏｕｎｄｉｎｇ（ＬＷＲ）問題は、非特許文献２で提唱されたＬＷＥ問題に派生する問題であり、その解読困難性はＬＷＥ問題に帰着することによって保証されている。ＬＷＥ問題には、離散正規分布に従う擬似乱数の生成モジュールが必要な一方、ＬＷＲ問題には必要ないため、ＬＷＥ問題に基づく暗号プロトコルよりも高速かつ軽量な暗号プロトコルが設計できることが期待されている。
【０００４】
非特許文献３には、ＬＷＥ問題以上の解読困難性を持つＬＷＲ問題のパラメータを導出する手法が提案されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｒｅｇｅｖ，  Ｏ．：  Ｏｎ  ｌａｔｔｉｃｅｓ，  ｌｅａｒｎｉｎｇ  ｗｉｔｈ  ｅｒｒｏｒｓ，  ｒａｎｄｏｍ  ｌｉｎｅａｒ  ｃｏｄｅｓ，  ａｎｄ  ｃｒｙｐｔｏｇｒａｐｈｙ，  Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  ＡＣＭ  （ＪＡＣＭ），  Ｖｏｌ．  ５６，  Ｎｏ．  ６，  ｐ．  ３４  （２００９）．
【非特許文献２】Ｂａｎｅｒｊｅｅ，  Ａ．，  Ｐｅｉｋｅｒｔ，  Ｃ．  ａｎｄ  Ｒｏｓｅｎ，  Ａ．：  Ｐｓｅｕｄｏｒａｎｄｏｍ  ｆｕｎｃｔｉｏｎｓ  ａｎｄ  ｌａｔｔｉｃｅｓ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＥＵＲＯＣＲＹＰＴ  ２０１２，  ｐｐ．  ７１９−７３７  （２０１２）．
【非特許文献３】Ａｌｗｅｎ，  Ｊ．，  Ｋｒｅｎｎ，  Ｓ．，  Ｐｉｅｔｒｚａｋ，  Ｋ．，  ａｎｄ  Ｗｉｃｈｓ，  Ｄ．：  Ｌｅａｒｎｉｎｇ  ｗｉｔｈ  ｒｏｕｎｄｉｎｇ，  ｒｅｖｉｓｉｔｅｄ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＣＲＹＰＴＯ  ２０１３，  ｐｐ．  ５７−７４  （２０１３）．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献３の導出手法では、パラメータの１つであるサンプル数に大きな制約があった。すなわち、ＬＷＲ問題に基づく暗号プロトコルを設計する際に、ＬＷＥ問題に基づく暗号プロトコルに比べて、鍵値の空間（法）が大きくなり過ぎてしまい、現実的なサイズの暗号を構成することが難しかった。
また、この導出手法では、あるＬＷＲ問題以上の解読困難性を持つＬＷＥ問題を一意に定めることはできず、ＬＷＥ問題とＬＷＲ問題とを双方向に置き換えることは難しかった。
【０００７】
本発明は、暗号プロトコルに用いられる２つの問題の間で、同等の安全性を持つように双方向にパラメータを導出できる設計装置、設計方法及び設計プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る設計装置は、計算の困難性に基づく２種類の暗号プロトコルにおいて、第１の暗号プロトコルが依拠する第１の問題を解くためのアルゴリズムによる計算量のオーダと、第２の暗号プロトコルが依拠する第２の問題を解くためのアルゴリズムによる計算量のオーダとを等式で結ぶことで得られるパラメータの関係式を記憶する記憶部と、前記第１の暗号プロトコルで設定される第１のパラメータ群の入力を受け付ける入力部と、前記第１のパラメータ群から、前記関係式により前記第２の暗号プロトコルで設定される第２のパラメータ群を導出する導出部と、前記第２のパラメータ群を出力する出力部と、を備える。
【０００９】
前記第１の問題はＬＷＥ問題であり、前記第２の問題はＬＷＲ問題であってもよい。
【００１０】
前記第１の問題を解くためのアルゴリズム及び前記第２の問題を解くためのアルゴリズムは、共通の計算アルゴリズムであってもよい。
【００１１】
本発明に係る設計方法は、コンピュータが、計算の困難性に基づく２種類の暗号プロトコルにおいて、第１の暗号プロトコルが依拠する第１の問題を解くためのアルゴリズムによる計算量のオーダと、第２の暗号プロトコルが依拠する第２の問題を解くためのアルゴリズムによる計算量のオーダとを等式で結ぶことで得られるパラメータの関係式を記憶し、前記第１の暗号プロトコルで設定される第１のパラメータ群の入力を受け付ける入力ステップと、前記第１のパラメータ群から、前記関係式により前記第２の暗号プロトコルで設定される第２のパラメータ群を導出する導出ステップと、前記第２のパラメータ群を出力する出力ステップと、を実行する。
【００１２】
本発明に係る設計プログラムは、コンピュータに、計算の困難性に基づく２種類の暗号プロトコルにおいて、第１の暗号プロトコルが依拠する第１の問題を解くためのアルゴリズムによる計算量のオーダと、第２の暗号プロトコルが依拠する第２の問題を解くためのアルゴリズムによる計算量のオーダとを等式で結ぶことで得られるパラメータの関係式を記憶させ、前記第１の暗号プロトコルで設定される第１のパラメータ群の入力を受け付ける入力ステップと、前記第１のパラメータ群から、前記関係式により前記第２の暗号プロトコルで設定される第２のパラメータ群を導出する導出ステップと、前記第２のパラメータ群を出力する出力ステップと、を実行させるためのものである。
【発明の効果】
【００１３】
本発明によれば、暗号プロトコルに用いられる２つの問題の間で、同等の安全性を持つように双方向にパラメータを導出できる。
【図面の簡単な説明】
【００１４】
【図１】実施形態に係る設計装置の機能構成を示す図である。
【図２】実施形態に係る関係式及びパラメータの導出手順を示す図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係る設計装置１の機能構成を示す図である。
設計装置１は、サーバ装置又はパーソナルコンピュータ等の情報処理装置（コンピュータ）であり、制御部１０、記憶部２０、及び各種の入出力デバイスを備える。
【００１６】
制御部１０は、設計装置１の全体を制御する部分であり、記憶部２０に記憶された各種プログラムを適宜読み出して実行することにより、本実施形態における機能を実現している。制御部１０は、ＣＰＵであってよい。
【００１７】
記憶部２０は、ハードウェア群を設計装置１として機能させるための設計プログラムを含む各種ソフトウェア、及び各種データ等の記憶領域であり、ＲＯＭ、ＲＡＭ、フラッシュメモリ又はハードディスク（ＨＤＤ）等であってよい。
【００１８】
記憶部２０は、解読のための計算の困難性に基づく２種類の暗号プロトコルにおいて、第１の暗号プロトコルが依拠する第１の問題を解くためのアルゴリズムによる計算量のオーダと、第２の暗号プロトコルが依拠する第２の問題を解くためのアルゴリズムによる計算量のオーダとを等式で結ぶことで得られるパラメータの関係式を記憶する。
本実施形態では、一例として、ＬＷＥ問題とＬＷＲ問題とを対象とし、両者のパラメータを相互に導出するための後述の関係式が設定される。
また、第１の問題を解くためのアルゴリズム及び第２の問題を解くためのアルゴリズムは、共通の計算アルゴリズムであってよい。
【００１９】
制御部１０は、入力部１１と、導出部１２と、出力部１３とを備える。
設計装置１は、これらの機能部が協働することで、一方の問題（ＬＷＥ問題又はＬＷＲ問題）のパラメータを入力として、同等の解読困難性を持つ他方の問題のパラメータを、記憶部２０に記憶された関係式を用いて導出する。
【００２０】
入力部１１は、第１の暗号プロトコルで設定される第１のパラメータ群の入力を受け付ける。
導出部１２は、第１のパラメータ群から、関係式により第２の暗号プロトコルで設定される第２のパラメータ群を導出する。
出力部１３は、第２のパラメータ群を出力する。
【００２１】
図２は、本実施形態に係る関係式及びパラメータの導出手順を示す図である。
ＬＷＥ問題及びＬＷＲ問題を解読するために、以下の文献Ａにおいて、ＢＫＷ（Ｂｌｕｍ，  Ｋａｌａｉ，  Ｗａｓｓｅｒｍａｎ）アルゴリズムが提案されている。
文献Ａ：  Ｄｕｃ，  Ａ．，  Ｔｒａｍｅｒ，  Ｆ．  ａｎｄ  Ｖａｕｄｅｎａｙ，  Ｓ．：  Ｂｅｔｔｅｒ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ＬＷＥ  ａｎｄ  ＬＷＲ，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＥＵＲＯＣＲＹＰＴ  ２０１５，  ｐｐ．  １７３−２０２  （２０１５）．
【００２２】
ＢＫＷアルゴリズムを用いた場合、以下の文献Ｂによれば、ＬＷＥ問題を解読する際の最小計算量は、αｌｗｅ＝√２πσとすると、
【数１】
2019113698.tif 000003
と見積もられる。ただし、ａ，ｂはａｂ＝ｎ（次元）を満たす自然数である。
文献Ｂ：  上中谷健，國廣昇，高安敦：  最小サンプルでＬＷＥ問題を解くためのＢＫＷアルゴリズム，  ＳＣＩＳ，  Ｖｏｌ．  ２Ｄ４，  Ｎｏ．  ５  （２０１６）．
すなわち、ＬＷＥ問題を解読する際の計算量のオーダは、
【数２】
2019113698.tif 000004
に漸近的に従うことが解析的に求められる。
なお、ａは、ＢＫＷアルゴリズムにおける入力パラメータである。
【００２３】
また、ＢＫＷアルゴリズムを用いてＬＷＲ問題を解読する際の最小計算量は、αｌｗｒ＝π／（ｐ√６）とすると、ＬＷＥ問題の場合と同様に、
【数３】
2019113698.tif 000005
と見積もられる。すなわち、ＬＷＲ問題を解読する際の計算量のオーダは、
【数４】
2019113698.tif 000006
に漸近的に従うことが解析的に求められる。
【００２４】
これら２つの計算量のオーダを等号で結ぶことにより、ＬＷＥ問題とＬＷＲ問題とが同等の解読困難性を持つためのパラメータの関係式が次のように導かれる。
【数５】
2019113698.tif 000007
【００２５】
この関係式を用いることにより、次元ｎ、法ｑ、ノイズの分散σのＬＷＥ問題を入力として、同等以上の解読困難性を持つ次元ｎ、法ｑ、丸め演算の法ｐのＬＷＲ問題が導出される。
具体的には、次元ｎ及び法ｑを共通としたとき、丸め演算の法ｐを、
【数６】
2019113698.tif 000008
とすると、ＬＷＲ問題は、入力のＬＷＥ問題以上の解読困難性を持つ。
【００２６】
また、次元ｎ、法ｑ、丸め演算の法ｐのＬＷＲ問題を入力として、同等の解読困難性を持つ次元ｎ、法ｑ、ノイズの分散σのＬＷＥ問題が導出される。
具体的には、次元ｎ及び法ｑを共通としたとき、ノイズの分散σを、
【数７】
2019113698.tif 000009
とすると、ＬＷＥ問題は、入力のＬＷＲ問題と同等の解読困難性を持つ。
【００２７】
本実施形態によれば、設計装置１は、アルゴリズムの計算量を解読困難性とみなし、２つの問題の計算量のオーダを等式で結ぶことで得られたパラメータの関係式を記憶する。これにより、設計装置１は、この関係式に基づいて、一方の問題のパラメータを入力として、同等の解読困難性を持つ他方の問題のパラメータを導出できる。
したがって、設計装置１は、暗号プロトコルに用いられる２つの問題の間で、暗号が同等の安全性を持つように双方向にパラメータを導出できる。
特に、ＬＷＥ問題とＬＷＲ問題との間で、サンプル数に関する制約を受けずに、同等の解読困難性を持つ暗号プロトコルを双方向に容易に設計することが可能になる。
【００２８】
この結果、２つの問題の解読困難性を容易に比較できるため、双方の問題に基づく暗号プロトコルの設計及び安全性の評価を、一方の問題に帰着して容易に行うことができる。
例えば、以下の文献Ｃには、ＬＷＥ問題及びＬＷＲ問題の双方に基づく鍵交換プロトコルが示されている。このプロトコルにおいて、一方の問題のパラメータを決定することで、設計装置１は、他方の問題のパラメータを自動的に導出できる。
文献Ｃ：  Ｚｈｅｎｇｚｈｏｎｇ  Ｊｉｎ  ａｎｄ  Ｙｕｎｌｅｉ  Ｚｈａｏ，  Ｏｐｔｉｍａｌ  Ｋｅｙ  Ｃｏｎｓｅｎｓｕｓ  ｉｎ  Ｐｒｅｓｅｎｃｅ  ｏｆ  Ｎｏｉｓｅ，  ｈｔｔｐｓ：／／ｉｔ．ａｒｘｉｖ．ｏｒｇ／ｐｄｆ／１６１１．０６１５０．ｐｄｆ
【００２９】
また、問題を解読するための計算量が２つの問題に共通したアルゴリズムにより見積もられることにより、双方の解読困難性を精度よく比較できる。さらに、関係式が簡略化されることが期待でき、双方向のパラメータ導出が容易になる。
【００３０】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、前述した実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、実施形態に記載されたものに限定されるものではない。
【００３１】
前述の実施形態では、ＬＷＥ問題とＬＷＲ問題とに基づく暗号プロトコルの場合を例示したが、これには限られない。例えば、ＬＷＥ問題は、最悪時格子問題から派生しており、ＬＷＥ問題のパラメータと最悪時格子問題のパラメータとの間にも、同様に関係式が定義でき、双方向に同等の安全性を持つ暗号プロトコルが設計できる。
このとき、２つの問題は、同一の問題から派生していることが好ましく、この場合、数式が類似することにより、関係式が簡略化されることが期待できる。
【００３２】
また、関係式を定義するために用いられる、問題を解読するための計算量のオーダは、前述の実施形態とは異なる数式による見積もりが採用されてもよい。
【００３３】
設計装置１による設計方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００３４】
１  設計装置
１０  制御部
１１  入力部
１２  導出部
１３  出力部
２０  記憶部
【図１】
2019113698.tif 000010
【図２】
2019113698.tif 000011