(57)【要約】【課題】高速かつ軽量な鍵交換システム、鍵交換方法及び鍵交換プログラムを提供すること。【解決手段】開始ノード１０及び応答ノード２０が行列演算を含む鍵交換プロトコルを実行する鍵交換システム１は、第１行列の転置行列と第２行列との積の転置行列を、第３行列と第４行列の転置行列との積として算出する算出部１１１及び２１１を備え、第３行列は、第２行列の転置行列に相当し、かつ、第２行列と独立してランダム値に基づいて生成され、第４行列は、第１行列の転置行列に相当し、かつ、第１行列と独立してランダム値に基づいて生成される。【選択図】図１
2019101057.tif 000002
【特許請求の範囲】
【請求項１】
開始ノード及び応答ノードが行列演算を含む鍵交換プロトコルを実行する鍵交換システムであって、
第１行列の転置行列と第２行列との積の転置行列を、第３行列と第４行列の転置行列との積として算出する算出部を備え、
前記第３行列は、前記第２行列の転置行列に相当し、かつ、前記第２行列と独立してランダム値に基づいて生成され、
前記第４行列は、前記第１行列の転置行列に相当し、かつ、前記第１行列と独立してランダム値に基づいて生成される鍵交換システム。
【請求項２】
開始ノード及び応答ノードが行列演算を含む鍵交換プロトコルを実行する鍵交換システムであって、
第１行列の転置行列と第２行列との積を、第４行列と第３行列の転置行列との積として算出する算出部を備え、
前記第３行列は、前記第２行列の転置行列に相当し、かつ、前記第２行列と独立してランダム値に基づいて生成され、
前記第４行列は、前記第１行列の転置行列に相当し、かつ、前記第１行列と独立してランダム値に基づいて生成される鍵交換システム。
【請求項３】
前記算出部は、前記第２行列が第５行列の転置行列と第６行列との積に基づく場合に、前記第３行列を、第７行列と第８行列の転置行列との積に基づいて算出し、
前記第７行列は、前記第６行列の転置行列に相当し、かつ、前記第６行列と独立してランダム値に基づいて生成され、
前記第８行列は、前記第５行列の転置行列に相当し、かつ、前記第５行列と独立してランダム値に基づいて生成される請求項１又は請求項２に記載の鍵交換システム。
【請求項４】
前記算出部は、前記第１行列が第９行列と第１０行列との積に基づく場合に、前記第４行列を、第１１行列と第１２行列との積に基づいて算出し、
前記第１１行列は、前記第１０行列の転置行列に相当し、かつ、前記第１０行列と独立してランダム値に基づいて生成され、
前記第１２行列は、前記第９行列の転置行列に相当し、かつ、前記第９行列と独立してランダム値に基づいて生成される請求項１から請求項３のいずれかに記載の鍵交換システム。
【請求項５】
前記算出部は、
前記第１２行列を転置した第１３行列を算出し、
前記第１１行列と前記第１２行列との積を、前記第１１行列と前記第１３行列の転置行列との積として算出する請求項４に記載の鍵交換システム。
【請求項６】
開始ノード及び応答ノードが行列演算を含む鍵交換プロトコルを実行する鍵交換方法であって、
第１行列の転置行列と第２行列との積の転置行列を、第３行列と第４行列の転置行列との積として算出し、
前記第３行列は、前記第２行列の転置行列に相当し、かつ、前記第２行列と独立してランダム値に基づいて生成され、
前記第４行列は、前記第１行列の転置行列に相当し、かつ、前記第１行列と独立してランダム値に基づいて生成される鍵交換方法。
【請求項７】
開始ノード及び応答ノードが行列演算を含む鍵交換プロトコルを実行する鍵交換方法であって、
第１行列の転置行列と第２行列との積を、第４行列と第３行列の転置行列との積として算出し、
前記第３行列は、前記第２行列の転置行列に相当し、かつ、前記第２行列と独立してランダム値に基づいて生成され、
前記第４行列は、前記第１行列の転置行列に相当し、かつ、前記第１行列と独立してランダム値に基づいて生成される鍵交換方法。
【請求項８】
請求項１から請求項５のいずれかに記載の鍵交換システムにおける前記開始ノード又は前記応答ノードとしてコンピュータを機能させるための鍵交換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号における鍵交換プロトコルを実行するためのシステム、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、ＩｏＴ（Ｉｎｔｅｒｎｅｔ  ｏｆ  Ｔｈｉｎｇｓ）端末等の非力な端末においても動作し、量子計算機による解読に対して耐性を持つ暗号方式として、次世代公開鍵暗号方式が研究されている。
例えば、次世代公開鍵暗号における鍵交換プロトコルして、ＬＷＥ問題に基づくＦｒｏｄｏ（非特許文献１参照）が提案されている。さらに、このプロトコルを高速化したものとして、Ｒｉｎｇ−ＬＷＥ問題に基づくＮｅｗＨｏｐｅ（非特許文献２参照）が提案されている。ただし、Ｒｉｎｇ−ＬＷＥ問題については、セキュリティ上の問題が指摘されている。
また、非特許文献３では、ＬＷＲ問題に基づく鍵交換プロトコルが提案されている。このプロトコルは、Ｆｒｏｄｏと比較して高速である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｊ．  Ｂｏｓ，  Ｃ．  Ｃｏｓｔｅｌｌｏ，  Ｌ．  Ｄｕｃａｓ，  Ｉ．  Ｍｉｒｏｎｏｖ，  Ｍ．  Ｎａｅｈｒｉｇ，  Ｖ．  Ｎｉｋｏｌａｅｎｋｏ，  Ａ．  Ｒａｇｈｕｎａｔｈａｎ，  ａｎｄ  Ｄ．  Ｓｔｅｂｉｌａ，  Ｆｒｏｄｏ：  Ｔａｋｅ  ｏｆｆ  ｔｈｅ  ｒｉｎｇ！  Ｐｒａｃｔｉｃａｌ，  Ｑｕａｎｔｕｍ−Ｓｅｃｕｒｅ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  ｆｒｏｍ  ＬＷＥ，  ｈｔｔｐｓ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１６／６５９／，  ２０１６．
【非特許文献２】Ｅ．  Ａｌｋｉｍ，  Ｌ．  Ｄｕｃａｓ，  Ｔ．  Ｐｏｐｐｅｌｍａｎｎ，  ａｎｄ  Ｐ．  Ｓｃｈｗａｂｅ，  Ｐｏｓｔ−ｑｕａｎｔｕｍ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ａ  ｎｅｗ  ｈｏｐｅ，  ｈｔｔｐｓ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１５／１０９２／，  ２０１５．
【非特許文献３】Ｚ．  Ｊｉｎ  ａｎｄ  Ｙ．  Ｚｈａｏ，  Ｏｐｔｉｍａｌ  Ｋｅｙ  Ｃｏｎｓｅｎｓｕｓ  ｉｎ  Ｐｒｅｓｅｎｃｅ  ｏｆ  Ｎｏｉｓｅ，  ｈｔｔｐｓ：／／ｉｔ．ａｒｘｉｖ．ｏｒｇ／ａｂｓ／１６１１．０６１５０／，  ２０１７．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
前述の非特許文献３で提案された鍵交換プロトコルは、図８に示すように開始者と応答者とが複数の演算により共通の秘密鍵Ｋ１＝Ｋ２を算出する。
ここで、図中の楕円で囲まれた行列演算のうちＭ１〜Ｍ４では、転置行列と行列の積演算が計４回行われている。この積演算の高速かつ軽量な実装は、以下のように困難であった。具体的には、転置行列ＡＴと行列Ｂとの積Ｃ＝ＡＴＢの演算方法として、下記の２つが挙げられる。
【０００５】
演算方法１：  次の数式に基づき、図９のアルゴリズム１を利用する方法。
【数１】
2019101057.tif 000003
【０００６】
アルゴリズム１をプログラムとして実装する場合、行列Ａ及びＢは、２次元配列として実装することが一般的である。この場合、Ｃ［ｉ］［ｊ］の計算（ステップＳ１）において、Ａ［ｋ］［ｉ］及びＢ［ｋ］［ｊ］を取得する必要があり（ステップＳ２）、ｋの値に応じて非連続な領域へのメモリアクセスが発生する。例えば、図１０に、要素数３×３の２次元配列Ａに対するアクセスの様子を示す。この例では、Ａ［０］［０］の値からＡ［１］［０］の値、及びＡ［１］［０］の値からＡ［２］［０］の値へ、非連続なメモリ領域へのアクセスが発生している。
このため、アルゴリズム１では、キャッシュミスの発生する頻度が増大し、高速な処理を行う妨げとなっていた。
【０００７】
演算方法２：  次の数式に基づき、図１１のアルゴリズム２を利用する方法。
【数２】
2019101057.tif 000004
【０００８】
アルゴリズム２では，行列Ａ及びＢの転置行列を事前に計算することで、Ｃ［ｉ］［ｊ］の計算（ステップＳ３）の際に、連続した領域Ａ［ｉ］［ｋ］及びＢ［ｊ］［ｋ］へのメモリアクセスを行わせることができる（ステップＳ４）。例えば、図１２に，要素数３×３の２次元配列Ａに対するアクセスの様子を示す。この例では、Ａ［０］［０］の値からＡ［０］［１］の値、及びＡ［０］［１］の値からＡ［０］［２］の値へ、連続したメモリ領域へのアクセスが発生している。
しかしながら、アルゴリズム２では、転置行列の計算が処理のオーバヘッドとなっていた。また、事前計算した転置行列を格納するため、使用するメモリ量も増大していた。
【０００９】
本発明は、高速かつ軽量な鍵交換システム、鍵交換方法及び鍵交換プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明に係る鍵交換システムは、開始ノード及び応答ノードが行列演算を含む鍵交換プロトコルを実行する鍵交換システムであって、第１行列の転置行列と第２行列との積の転置行列を、第３行列と第４行列の転置行列との積として算出する算出部を備え、前記第３行列は、前記第２行列の転置行列に相当し、かつ、前記第２行列と独立してランダム値に基づいて生成され、前記第４行列は、前記第１行列の転置行列に相当し、かつ、前記第１行列と独立してランダム値に基づいて生成される。
【００１１】
本発明に係る鍵交換システムは、開始ノード及び応答ノードが行列演算を含む鍵交換プロトコルを実行する鍵交換システムであって、第１行列の転置行列と第２行列との積を、第４行列と第３行列の転置行列との積として算出する算出部を備え、前記第３行列は、前記第２行列の転置行列に相当し、かつ、前記第２行列と独立してランダム値に基づいて生成され、前記第４行列は、前記第１行列の転置行列に相当し、かつ、前記第１行列と独立してランダム値に基づいて生成される。
【００１２】
前記算出部は、前記第２行列が第５行列の転置行列と第６行列との積に基づく場合に、前記第３行列を、第７行列と第８行列の転置行列との積に基づいて算出し、前記第７行列は、前記第６行列の転置行列に相当し、かつ、前記第６行列と独立してランダム値に基づいて生成され、前記第８行列は、前記第５行列の転置行列に相当し、かつ、前記第５行列と独立してランダム値に基づいて生成されてもよい。
【００１３】
前記算出部は、前記第１行列が第９行列と第１０行列との積に基づく場合に、前記第４行列を、第１１行列と第１２行列との積に基づいて算出し、前記第１１行列は、前記第１０行列の転置行列に相当し、かつ、前記第１０行列と独立してランダム値に基づいて生成され、前記第１２行列は、前記第９行列の転置行列に相当し、かつ、前記第９行列と独立してランダム値に基づいて生成されてもよい。
【００１４】
前記算出部は、前記第１２行列を転置した第１３行列を算出し、前記第１１行列と前記第１２行列との積を、前記第１１行列と前記第１３行列の転置行列との積として算出してもよい。
【００１５】
本発明に係る鍵交換方法は、開始ノード及び応答ノードが行列演算を含む鍵交換プロトコルを実行する鍵交換方法であって、第１行列の転置行列と第２行列との積の転置行列を、第３行列と第４行列の転置行列との積として算出し、前記第３行列は、前記第２行列の転置行列に相当し、かつ、前記第２行列と独立してランダム値に基づいて生成され、前記第４行列は、前記第１行列の転置行列に相当し、かつ、前記第１行列と独立してランダム値に基づいて生成される。
【００１６】
本発明に係る鍵交換方法は、開始ノード及び応答ノードが行列演算を含む鍵交換プロトコルを実行する鍵交換方法であって、第１行列の転置行列と第２行列との積を、第４行列と第３行列の転置行列との積として算出し、前記第３行列は、前記第２行列の転置行列に相当し、かつ、前記第２行列と独立してランダム値に基づいて生成され、前記第４行列は、前記第１行列の転置行列に相当し、かつ、前記第１行列と独立してランダム値に基づいて生成される。
【００１７】
本発明に係る鍵交換プログラムは、前記鍵交換システムにおける前記開始ノード又は前記応答ノードとしてコンピュータを機能させるためのものである。
【発明の効果】
【００１８】
本発明によれば、鍵交換プロトコルが高速かつ軽量に実装される。
【図面の簡単な説明】
【００１９】
【図１】第１実施形態に係る鍵交換システムの機能構成を示す図である。
【図２】第１実施形態に係る鍵交換プロトコルによる演算手順を示す図である。
【図３】第１実施形態に係るアルゴリズム３を示す図である。
【図４】第１実施形態に係るアルゴリズム４を示す図である。
【図５】第１実施形態に係るパラメータの値を例示する図である。
【図６】第１実施形態に係るパラメータに設定される確率分布を例示する図である。
【図７】第２実施形態に係る鍵交換プロトコルによる演算手順を示す図である。
【図８】従来の鍵交換プロトコルによる演算手順を示すシーケンス図である。
【図９】従来のアルゴリズム１を示す図である。
【図１０】非連続なメモリアクセスを例示する図である。
【図１１】従来のアルゴリズム２を示す図である。
【図１２】連続したメモリアクセスを例示する図である。
【発明を実施するための形態】
【００２０】
［第１実施形態］
以下、本発明の第１実施形態について説明する。
図１は、本実施形態に係る鍵交換システム１の機能構成を示す図である。
鍵交換システム１は、開始ノード１０と応答ノード２０との間で公開情報のみを送受信し、互いに同一の秘密鍵を生成するための鍵交換プロトコルを実行する。
【００２１】
開始ノード１０は、制御部１１０、記憶部１２０、通信部１３０及び各種の入出力インタフェース等を備えた情報処理装置（コンピュータ）である。
応答ノード２０もまた、制御部２１０、記憶部２２０、通信部２３０及び各種の入出力インタフェース等を備えた情報処理装置（コンピュータ）である。
【００２２】
制御部１１０及び制御部２１０は、それぞれ記憶部１２０及び記憶部２２０に格納されたソフトウェア（鍵交換プログラム）を読み出して実行することにより、それぞれ算出部１１１及び算出部２１１として機能し、通信部１３０及び通信部２３０を介して互いに協働することで鍵交換方法を実現する。
【００２３】
算出部１１１及び算出部２１１は、鍵交換プロトコルに含まれる行列演算について、第１行列（Ａ）の転置行列と第２行列（Ｂ）との積の転置行列「（ＡＴ・Ｂ）Ｔ」を、第３行列（Ｂ’）と第４行列（Ａ’）の転置行列との積「Ｂ’・Ａ’Ｔ」として算出する。
この演算は、例えば、図２で後述するＭ１１〜Ｍ１３の演算が該当し、これらの演算Ｍ１１〜Ｍ１３は、それぞれ従来のプロトコル（図８）の演算Ｍ１〜Ｍ３から変換されたものである。
【００２４】
「（ＡＴ・Ｂ）Ｔ＝Ｂ’・Ａ’Ｔ」となるためには、Ａ’及びＢ’は、それぞれＡ及びＢの転置行列である。ただし、Ａ（又はＢ）がランダム値に基づいて所定の確率分布で生成される行列、又はこれらの行列同士の演算により生成される行列である場合、Ａ’（又はＢ’）は、Ａ（又はＢ）の転置行列に相当し、かつ、Ａ（又はＢ）とは独立して生成される。
ここで、Ａ’がＡの転置行列に相当するとは、Ａ’の行数がＡの列数に等しく、Ａ’の列数がＡの行数に等しく、さらに、Ａのｉ行ｊ列の要素がランダムに生成されるため、Ａ’のｊ行ｉ列の要素もランダムに生成されてよいことを示す。
【００２５】
また、算出部１１１及び算出部２１１は、第２行列（Ｂ）が第５行列（Ｃ）の転置行列と第６行列（Ｄ）との積「ＣＴ・Ｄ」に基づく場合に、第２行列（Ｂ）の転置行列に相当する第３行列（Ｂ’）を、第７行列（Ｄ’）と第８行列（Ｃ’）の転置行列との積「Ｄ’・Ｃ’Ｔ」に基づいて算出する。
この演算は、例えば、図２で後述する演算Ｍ１１で用いる行列を求めるための演算Ｍ１４が該当し、この演算Ｍ１４は、従来のプロトコル（図８）のＭ４から変換されたものである。
【００２６】
Ｂ’がＢの転置行列に相当、すなわち「Ｄ’・Ｃ’Ｔ＝（ＣＴ・Ｄ）Ｔ」となるためには、Ｃ’及びＤ’は、それぞれＣ及びＤの転置行列である。Ｃ（又はＤ）がランダム値に基づいて所定の確率分布で生成される行列、又はこれらの行列同士の演算により生成される行列である場合、Ｃ’（又はＤ’）は、Ｃ（又はＤ）の転置行列に相当し、かつ、Ｃ（又はＤ）とは独立して生成される。
【００２７】
また、算出部１１１及び算出部２１１は、第１行列（Ａ）が第９行列と第１０行列との積「Ｅ・Ｆ」に基づく場合に、第１行列（Ａ）の転置行列に相当する第４行列（Ａ’）を、第１１行列（Ｆ’）と第１２行列（Ｅ’）との積「Ｆ’・Ｅ’」に基づいて算出する。
この演算は、例えば、図２で後述する演算Ｍ１２で用いる行列を求めるための演算Ｍ１５が該当し、この演算Ｍ１５は、従来のプロトコル（図８）のＭ５から変換されたものである。
【００２８】
Ａ’がＡの転置行列に相当、すなわち「Ｆ’・Ｅ’＝（Ｅ・Ｆ）Ｔ」となるためには、Ｅ’及びＦ’は、それぞれＥ及びＦの転置行列である。Ｅ（又はＦ）がランダム値に基づいて所定の確率分布で生成される行列、又はこれらの行列同士の演算により生成される行列である場合、Ｅ’（又はＦ’）は、Ｅ（又はＦ）の転置行列に相当し、かつ、Ｅ（又はＦ）とは独立して生成される。
【００２９】
また、算出部１１１及び算出部２１１は、第１１行列と第１２行列との積「Ｆ’・Ｅ’」を計算する際に、まず、第１２行列（Ｅ’）を転置した第１３行列（Ｇ＝Ｅ’Ｔ）を算出し、第１１行列と第１２行列との積（Ｆ’・Ｅ’）を、第１１行列と第１３行列の転置行列との積「Ｆ’・ＧＴ」として算出する。
【００３０】
このように、算出部１１１及び算出部２１１は、プロトコルに含まれる行列の積演算を、ある行列とある行列の転置行列との積に変換して計算することにより、２次元配列として実装された行列要素を、連続した領域へのメモリアクセスで取得できる。
【００３１】
図２は、本実施形態に係る鍵交換プロトコルによる開始ノード１０及び応答ノード２０の演算手順を示す図である。
このプロトコルでは、従来（図８）と同様に、開始ノード１０と応答ノード２０とは、事前にパラメータｎ、ｌＡ、ｌＢ、ｐ、ｑ、ｍ及びｇ、並びに確率分布χを合意しておく。
【００３２】
ステップＳ１１において、開始ノード１０は、ｎ×ｎ型の行列Ａ’を生成する。Ａ’の各要素は、正整数ｑを法とする剰余環Ｚｑからランダムに選択される。
なお、行列Ａ’は、従来の鍵交換プロトコル（図８）における行列Ａの転置行列に相当するが、行列Ａとは独立してランダムに生成される。
【００３３】
ステップＳ１２において、開始ノード１０は、ｌＡ×ｎ型の行列Ｘ１’を生成する。Ｘ１’の各要素は、開始ノード１０と応答ノード２０とで事前に合意した確率分布χからサンプリングされる。
なお、行列Ｘ１’は、従来の鍵交換プロトコル（図８）におけるｎ×ｌＡ型の行列Ｘ１の転置行列に相当するが、行列Ｘ１とは独立してランダムに生成される。
【００３４】
ステップＳ１３において、開始ノード１０は、
【数３】
2019101057.tif 000005
と定義される関数を用いて、ｌＡ×ｎ型の行列Ｙ１’を、
【数４】
2019101057.tif 000006
と計算する。
【００３５】
ステップＳ１４において、開始ノード１０は、応答ノード２０に対して、行列Ａ’及びＹ１’を送付する。
【００３６】
ステップＳ２１において、応答ノード２０は、ｌＢ×ｎ型の行列Ｘ２’を生成する。Ｘ２’の各要素は、開始ノード１０と応答ノード２０とで事前に合意した確率分布χからサンプリングされる。
【００３７】
ステップＳ２２において、応答ノード２０は、ｌＢ×ｎ型の行列Ｙ２’を、
【数５】
2019101057.tif 000007
と計算する。
【００３８】
ステップＳ２３において、応答ノード２０は、ｌＡ×ｎ型の行列ε’を生成する。ε’の各要素は、
【数６】
2019101057.tif 000008
の整数からランダムに選択される。
【００３９】
ステップＳ２４において、応答ノード２０は、ｌＢ×ｌＡ型の行列Σ２’を、
【数７】
2019101057.tif 000009
と計算する。
【００４０】
ステップＳ２５において、応答ノード２０は、ｌＢ×ｌＡ型の行列Ｋ２’及びｌＢ×ｌＡ型の行列Ｖ’を、（Ｋ２’，Ｖ’）←Ｃｏｎ（Σ２’）と計算する。なお、関数Ｃｏｎは、図３のアルゴリズム３に示すように、Σ２’の要素σ２’を、パラメータｑ、ｍ、ｇを用いてＫ２’の要素ｋ２’及びＶ’の要素ｖ’に変換するものである。
【００４１】
ステップＳ２６において、応答ノード２０は、開始ノード１０に対して、行列Ｙ２’及びＶ’を送付する。
【００４２】
ステップＳ３１において、開始ノード１０は、ｌＢ×ｌＡ型の行列Σ１’を、
【数８】
2019101057.tif 000010
と計算する。
【００４３】
ステップＳ３２において、開始ノード１０は、ｌＢ×ｌＡ型の行列Ｋ１’を、Ｋ１’←Ｒｅｃ（Σ１’，Ｖ’）と計算する。なお、関数Ｒｅｃは、図３のアルゴリズム３に示すように、Σ１’の要素σ１’及びＶ’の要素ｖ’を、パラメータｑ、ｍ、ｇを用いてＫ１’の要素ｋ１’に変換するものである。
【００４４】
図４に、本実施形態に係る行列と転置行列との積演算のアルゴリズム４を示す。
この処理では、アルゴリズム２（図１１）のように転置行列の事前計算は不要である。さらに、Ｃ［ｉ］［ｊ］の計算（ステップＳ５）の際に、連続した領域Ａ［ｉ］［ｋ］及びＢ［ｊ］［ｋ］へのメモリアクセスを行わせることができる（ステップＳ６）。
行列の各要素の演算において、連続した領域へのメモリアクセスが行われるため、キャッシュミスによる実行効率の低下が抑止される。
【００４５】
図５に、本実施形態の鍵交換プロトコルに用いるパラメータの値を例示する。
また、図６に、パラメータχに設定される確率分布Ｄ１を例示する。
これらのパラメータを採用した場合、非特許文献３に示された従来の鍵交換プロトコル（図８）は、約９．１７ｍｓｅｃで完了した。
これに対し、同一のハードウェア構成で本実施形態の鍵交換プロトコル（図２）は、約３．４０ｍｓｅｃで完了し、約２．７倍高速に動作した。
【００４６】
本実施形態によれば、鍵交換システム１は、従来の鍵交換プロトコルに含まれる転置行列と行列との積演算を、行列と転置行列との積演算に置き換え、従来のプロトコルによる鍵（Ｋ１，Ｋ２）に対して転置行列に相当する鍵（Ｋ１’，Ｋ２’）を出力した。
これにより、鍵交換システム１は、積演算の各要素を計算する際に、２次元配列として実装された各行列の要素を順に、連続した領域へのメモリアクセスで取得できる。したがって、鍵交換システム１は、転置行列の事前計算をすることなく、キャッシュミスによる実行効率の低下を抑止し、鍵交換プロトコルを高速かつ軽量に実装できる。
【００４７】
また、鍵交換システム１は、積演算される各行列がさらに別の行列演算により算出される場合、これらを、行列と転置行列との積演算、又は転置ではない行列と行列との積演算に置き換えた。
これにより、鍵交換システム１は、従来の鍵交換プロトコルの手順に従いつつ、各手順の演算をより効率的な計算手法により実現できる。したがって、鍵交換システム１は、鍵交換プロトコルをより高速かつ軽量に実装できる。
【００４８】
また、鍵交換システム１は、行列と行列との積演算に関しても、一方の行列の転置行列を事前計算することにより、行列と転置行列との積演算のアルゴリズムを利用できる。
これにより、鍵交換システム１は、アルゴリズム２（図１１）のように事前に２回の転置計算を行うのに比べて１回の転置計算のみにより、連続した領域へのメモリアクセスを実現できる。したがって、さらに鍵交換プロトコルの高速化が期待できる。
【００４９】
［第２実施形態］
以下、本発明の第２実施形態について説明する。
本実施形態の鍵交換システム１は、第１実施形態と同様の構成（図１）であるが、開始ノード１０及び応答ノード２０が備える算出部１１１及び算出部２１１の機能が異なる。
第１実施形態では、従来のプロトコルによる鍵に対して転置行列に相当する鍵（Ｋ１’，Ｋ２’）を出力したが、本実施形態では、従来と同等の鍵（Ｋ１，Ｋ２）を出力する。
【００５０】
算出部１１１及び算出部２１１は、鍵交換プロトコルに含まれる行列演算について、第１行列（Ａ）の転置行列と第２行列（Ｂ）との積「ＡＴ・Ｂ」を、第４行列（Ａ’）と第３行列（Ｂ’）の転置行列との積「Ａ’・Ｂ’Ｔ」として算出する。
この演算は、例えば、図７で後述するＭ２１〜Ｍ２３の演算が該当し、これらの演算Ｍ２１〜Ｍ２３は、それぞれ従来のプロトコル（図８）の演算Ｍ１〜Ｍ３から変換されたものである。
【００５１】
「ＡＴ・Ｂ＝Ａ’・Ｂ’Ｔ」となるためには、Ａ’及びＢ’は、それぞれＡ及びＢの転置行列である。ただし、Ａ（又はＢ）がランダム値に基づいて所定の確率分布で生成される行列、又はこれらの行列同士の演算により生成される行列である場合、Ａ’（又はＢ’）は、Ａ（又はＢ）の転置行列に相当し、かつ、Ａ（又はＢ）とは独立して生成される。
【００５２】
図７は、本実施形態に係る鍵交換プロトコルによる開始ノード１０及び応答ノード２０の演算手順を示す図である。
なお、ステップＳ１１〜Ｓ２３は、第１実施形態（図２）と同一である。この後のステップＳ２７〜Ｓ２９及びＳ３３〜Ｓ３４は、第１実施形態のステップＳ２４〜Ｓ２６及びＳ３１〜Ｓ３２に対応する。
【００５３】
ステップＳ２７において、応答ノード２０は、ｌＡ×ｌＢ型の行列Σ２を、
【数９】
2019101057.tif 000011
と計算する。
【００５４】
ステップＳ２８において、応答ノード２０は、ｌＡ×ｌＢ型の行列Ｋ２及びｌＡ×ｌＢ型の行列Ｖを、（Ｋ２，Ｖ）←Ｃｏｎ（Σ２）と計算する。なお、関数Ｃｏｎは、第１実施形態と同様、図３のアルゴリズム３に示すように、Σ２の要素σ２を、パラメータｑ、ｍ、ｇを用いてＫ２の要素ｋ２及びＶの要素ｖに変換するものである。
【００５５】
ステップＳ２９において、応答ノード２０は、開始ノード１０に対して、行列Ｙ２’及びＶを送付する。
【００５６】
ステップＳ３３において、開始ノード１０は、ｌＡ×ｌＢ型の行列Σ１を、
【数１０】
2019101057.tif 000012
と計算する。
【００５７】
ステップＳ３４において、開始ノード１０は、ｌＡ×ｌＢ型の行列Ｋ１を、Ｋ１←Ｒｅｃ（Σ１，Ｖ）と計算する。なお、関数Ｒｅｃは、第１実施形態と同様、図３のアルゴリズム３に示すように、Σ１の要素σ１及びＶの要素ｖを、パラメータｑ、ｍ、ｇを用いてＫ１の要素ｋ１に変換するものである。
【００５８】
本実施形態によれば、鍵交換システム１は、従来の鍵交換プロトコルに含まれる転置行列と行列との積演算を、行列と転置行列との積演算に置き換え、従来のプロトコルによる鍵に相当する鍵（Ｋ１，Ｋ２）を出力した。
これにより、鍵交換システム１は、従来のプロトコルと同等の演算結果を得られると共に、第１実施形態と同様の効果が期待できる。
【００５９】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、前述した実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、実施形態に記載されたものに限定されるものではない。
【００６０】
鍵交換システム１による鍵交換方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００６１】
１  鍵交換システム
１０  開始ノード
２０  応答ノード
１１０  制御部
１１１  算出部
１２０  記憶部
１３０  通信部
２１０  制御部
２１１  算出部
２２０  記憶部
２３０  通信部
【図１】
2019101057.tif 000013
【図２】
2019101057.tif 000014
【図３】
2019101057.tif 000015
【図４】
2019101057.tif 000016
【図５】
2019101057.tif 000017
【図６】
2019101057.tif 000018
【図７】
2019101057.tif 000019
【図８】
2019101057.tif 000020
【図９】
2019101057.tif 000021
【図１０】
2019101057.tif 000022
【図１１】
2019101057.tif 000023
【図１２】
2019101057.tif 000024