JP6818220B2 - 鍵共有装置、鍵共有方法及び鍵共有プログラム - Google Patents

Description

この発明は、２者間で鍵を共有する技術に関する。

量子計算機の開発が、世界的に進められている。量子計算機の出現に対しても安全性を維持できる暗号方式として、同種写像を用いた暗号の提案が行われている。

非特許文献１には、１ラウンドのＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ（以下、ＤＨ）鍵共有方式を、認証機能付きの方式に変換するＢｉｃｌｉｑｕｅ変換法が記載されている。

Ｆｕｊｉｏｋａ， Ａ．： Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ ｏｆ ｓｔｒｏｎｇｌｙ ｓｅｃｕｒｅ ａｕｔｈｅｎｔｉｃａｔｅｄ ｋｅｙ ｅｘｃｈａｎｇｅｓ ｗｉｔｈｏｕｔ ＮＡＸＯＳ ｔｅｃｈｎｉｑｕｅ． ＩＥＩＣＥ Ｔｒａｎｓａｃｔｉｏｎｓ ９６−Ａ（６）， １０８８−１０９９ （２０１３）， ａ ｐｒｅｌｉｍｉｎａｒｙ ｖｅｒｓｉｏｎ ｏｆ ｔｈｉｓ ｐａｐｅｒ ａｐｐｅａｒｅｄ ｉｎ ＩＷＳＥＣ ２０１１ （２０１１） Ｄｅ Ｆｅｏ， Ｌ．， Ｊａｏ， Ｄ．， Ｐｌｕｔ， Ｊ．： Ｔｏｗａｒｄｓ ｑｕａｎｔｕｍ−ｒｅｓｉｓｔａｎｔ ｃｒｙｐｔｏｓｙｓｔｅｍｓ ｆｒｏｍ ｓｕｐｅｒｓｉｎｇｕｌａｒ ｅｌｌｉｐｔｉｃ ｃｕｒｖｅ ｉｓｏｇｅｎｉｅｓ． Ｊ． Ｍａｔｈ． Ｃｒｙｐｔ． ８（３）， ２０９−２４７ （２０１４）

ＤＨ鍵共有方式は、耐量子性を持たない。これまでは、耐量子性を持つ、１ラウンドの認証機能付きの鍵共有方式がなかった。
耐量子性を持つ、１ラウンドの認証機能付きの鍵共有方式を構成するための候補となる技術として、超特異同種写像ＤＨ（以下、ＳＩＤＨ）鍵共有方式（非特許文献２参照）がある。ＳＩＤＨ鍵共有方式は、最近になって活発に研究されるようになっているものの、ＳＩＤＨ鍵共有方式の非対称性から認証機能付きの鍵共有方式への変換法が知られていない。
この発明は、非対称性を持つ鍵共有方式を認証機能付きの鍵共有方式に変換可能にすることを目的とする。

この発明に係る鍵共有装置は、
２つの静的鍵から１つの静的鍵を選択する鍵選択部と、
前記鍵選択部によって選択された静的鍵を用いて、相手側と共有する共有鍵を生成する鍵生成部と
を備える。

この発明では、２つの静的鍵から選択された１つの静的鍵を用いて共有鍵を生成する。これにより、非対称性を持つ鍵共有方式を認証機能付きの鍵共有方式に変換することが可能になる。

ＳＩＤＨ鍵共有方式の説明図。 ＳＩＤＨ鍵共有方式のアルゴリズムを示す図。 記法の説明図。 ＳＩＤＨ鍵共有方式のアルゴリズムを簡潔化して示す図。 実施の形態１に係る鍵共有システム１の構成図。 実施の形態１に係る鍵共有装置１０の構成図。 実施の形態１に係る事前処理のフローチャート。 実施の形態１に係る鍵共有処理のフローチャート。 実施の形態１に係る鍵共有処理のアルゴリズムを示す図。 変形例２に係る鍵共有装置１０の構成図。

実施の形態１．
実施の形態１では、非対称性を持つ鍵共有方式として、ＳＩＤＨ鍵共有方式を例として説明する。

＊＊＊記法の説明＊＊＊
以下で用いられる記法を説明する。ここでは、ＳＩＤＨ鍵共有方式を説明した上で、記法を説明する。
なお、文中での下付き文字及び上付き文字の記載に制限がある。そのため、以下の文中では、“＿”を下付き文字を表すための記号とし、“＾”を上付き文字を表す記号として用い、文中では表現できない下付き文字及び上付き文字をこられの記号を用いて表す。例えば、Ｎ＿ｉはＮ_ｉを表し、Ｎ＾ｉはＮ^ｉを表すものとする。

＜ＳＩＤＨ鍵共有方式＞
図１及び図２を参照して、ＳＩＤＨ鍵共有方式を説明する。ここでは、ＡｌｉｃｅとＢｏｂが鍵共有を行うとする。
２つの小素数Ｌ_Ａ，Ｌ_Ｂ（例えば、Ｌ_Ａ＝２，Ｌ_Ｂ＝３）と、小さい値ｆとに対して、数１１になるように大きい素数ｐが選択される。

ここで、値ｅ_Ａ，ｅ_Ｂは、数１１における式（２）が成立するように選択される。また、数１１における記号Θは、ランダウの記号であり、漸近的に上下からおさえられることを意味する。また、λは、セキュリティパラメータである。
位数ｐ^２の有限体Ｆ＿｛ｐ^２｝上に定義された超特異楕円曲線Ｅであって、数１２に示す有理点群を持つ超特異楕円曲線Ｅが選択される。

位数Ｌ_Ａ＾｛ｅ_Ａ｝の核を持つ同種写像φ_Ａと、位数Ｌ_Ｂ＾｛ｅ_Ｂ｝の核を持つ同種写像φ_Ｂが用いられる。同種写像φ_Ａに対して、その核をＫｅｒ（φ_Ａ）＝＜Ｒ_Ａ＞とし、同種写像φ_Ｂに対して、その核をＫｅｒ（φ_Ｂ）＝＜Ｒ_Ｂ＞とする。φ_Ｂ（Ｒ_Ａ）を核とする同種写像をφ_ＢＡとし、φ_Ａ（Ｒ_Ｂ）核とする同種写像をφ_ＡＢとする。
すると、図１に示す関係が成立する。つまり、超特異楕円曲線Ｅから同種写像φ_Ａにより超特異楕円曲線Ｅ_Ａ＝Ｅ／＜Ｒ_Ａ＞が得られ、超特異楕円曲線Ｅ_Ａから同種写像φ_ＡＢにより超特異楕円曲線Ｅ／＜Ｒ_Ａ，Ｒ_Ｂ＞が得られる（ルート１）。また、超特異楕円曲線Ｅから同種写像φ_Ｂにより超特異楕円曲線Ｅ_Ｂ＝Ｅ／＜Ｒ_Ｂ＞が得られ、超特異楕円曲線Ｅ_Ｂから同種写像φ_ＢＡにより超特異楕円曲線Ｅ／＜Ｒ_Ａ，Ｒ_Ｂ＞が得られる（ルート２）。

数１３に示す超特異楕円曲線Ｅ上の点Ｐ_Ａ，Ｑ_Ａ，Ｐ_Ｂ，Ｑ_Ｂが生成元として選択される。超特異楕円曲線Ｅと、生成元Ｐ_Ａ，Ｑ_Ａ，Ｐ_Ｂ，Ｑ_Ｂと、値Ｌ_Ａ，Ｌ_Ｂ，ｅ_Ａ，ｅ_Ｂとが公開パラメータとされる。

また、ＡｌｉｃｅとＢｏｂの秘密鍵空間が、それぞれ、数１４に示すＳＫ_Ａ，ＳＫ_Ｂとされる。

図２に示すように、Ａｌｉｃｅは、秘密鍵空間ＳＫ_Ａからランダムに選択された秘密鍵（ｍ_Ａ，ｎ_Ａ）を用いて、Ｒ_Ａ＝ｍ_ＡＰ_Ａ＋ｎ_ＡＱ_Ａを計算する。Ａｌｉｃｅは、Ｒ_Ａを用いて超特異楕円曲線Ｅ_Ａと、同種写像φ_Ａとを計算する。そして、Ａｌｉｃｅは、超特異楕円曲線Ｅ_Ａと、同種写像φ_Ａを用いて計算されたφ_Ａ（Ｐ_Ｂ）及びφ_Ａ（Ｑ_Ｂ）とをＢｏｂに送信する。
同様に、Ｂｏｂは、秘密鍵空間ＳＫ_Ｂからランダムに選択された秘密鍵（ｍ_Ｂ，ｎ_Ｂ）を用いて、Ｒ_Ｂ＝ｍ_ＢＰ_Ｂ＋ｎ_ＢＱ_Ｂを計算する。Ｂｏｂは、Ｒ_Ｂを用いて超特異楕円曲線Ｅ_Ｂと、同種写像φ_Ｂとを計算する。そして、Ｂｏｂは、超特異楕円曲線Ｅ_Ｂと、同種写像φ_Ｂを用いて計算されたφ_Ｂ（Ｐ_Ａ）及びφ_Ｂ（Ｑ_Ａ）とをＡｌｉｃｅに送信する。

Ａｌｉｃｅは、秘密鍵（ｍ_Ａ，ｎ_Ａ）と、Ｂｏｂによって送信されたφ_Ｂ（Ｐ_Ａ）及びφ_Ｂ（Ｑ_Ａ）とを用いて、Ｒ_ＢＡ＝ｍ_Ａφ_Ｂ（Ｐ_Ａ）＋ｎ_Ａφ_Ｂ（Ｑ_Ａ）を計算する。Ａｌｉｃｅは、Ｒ_ＢＡと、Ｂｏｂによって送信された超特異楕円曲線Ｅ_Ｂとから、共有鍵Ｋ_{Ａｌｉｃｅ}＝ｊ（Ｅ_Ｂ／＜Ｒ_ＢＡ＞）を計算する。ここで、ｊは、ｊ−不変量である。
同様に、Ｂｏｂは、秘密鍵（ｍ_Ｂ，ｎ_Ｂ）と、Ａｌｉｃｅによって送信されたφ_Ａ（Ｐ_Ｂ）及びφ_Ａ（Ｑ_Ｂ）とを用いて、Ｒ_ＡＢ＝ｍ_Ｂφ_Ａ（Ｐ_Ｂ）＋ｎ_Ｂφ_Ａ（Ｑ_Ｂ）を計算する。Ｂｏｂは、Ｒ_ＡＢと、Ａｌｉｃｅによって送信された超特異楕円曲線Ｅ_Ａとから、共有鍵Ｋ_Ｂｏｂ＝ｊ（Ｅ_Ａ／＜Ｒ_ＡＢ＞）を計算する。

つまり、鍵共有を行う一方（ここではＢｏｂ）が図１のルート１の計算を行い、他方（ここではＡｌｉｃｅ）が図１のルート２の計算を行う。
ここで、＜ｍ_Ａφ_Ｂ（Ｐ_Ａ）＋ｎ_Ａφ_Ｂ（Ｑ_Ａ）＞＝＜φ_Ｂ（Ｒ_Ａ）＞＝ｋｅｒφ_ＢＡであり、＜ｍ_Ｂφ_Ａ（Ｐ_Ｂ）＋ｎ_Ｂφ_Ａ（Ｑ_Ｂ）＞＝＜φ_Ａ（Ｒ_Ｂ）＞＝ｋｅｒφ_ＡＢである。そのため、ｊ−不変量の間の等式Ｋ_{Ａｌｉｃｅ}＝ｊ（Ｅ_Ｂ／ｋｅｒφ_ＢＡ）＝ｊ（Ｅ／＜Ｒ_Ａ，Ｒ_Ｂ＞）＝ｊ（Ｅ_Ａ／ｋｅｒφ_ＡＢ）＝Ｋ_Ｂｏｂが成立する。したがって、Ｋ＝Ｋ_{Ａｌｉｃｅ}＝Ｋ_Ｂｏｂが共有鍵となる。

ここで、Ａｌｉｃｅが用いる公開パラメータＰ_Ａ，Ｑ_Ａ及び秘密鍵空間ＳＫ_ＡはＬ_Ａのべき乗に基づく要素であり、Ｂｏｂが用いる公開パラメータＰ_Ｂ，Ｑ_Ｂ及び秘密鍵空間ＳＫ_ＢはＬ_Ｂのべき乗に基づく要素である。したがって、公開パラメータＰ_Ａ，Ｑ_Ａ及び秘密鍵空間ＳＫ_Ａと、公開パラメータＰ_Ｂ，Ｑ_Ｂ及び秘密鍵空間ＳＫ_Ｂとは、異なる分類の要素である。ＡｌｉｃｅとＢｏｂとは、必ず異なる分類の要素を用いる必要があり、同じ分類の要素を用いて鍵共有を行うことはできない。
このように、鍵共有を行う二者間で用いる情報が異なることを、非対称性と呼ぶ。つまり、ＳＩＤＨ鍵共有方式は非対称性を持つ。

＜記法＞
図３を参照して、ＳＩＤＨ鍵共有方式を簡潔に記載するための記法を説明する。
公開パラメータに含まれる超特異楕円曲線Ｅ及び生成元Ｐ_Ａ，Ｑ_Ａ，Ｐ_Ｂ，Ｑ_Ｂが“ｇ”と記述される。Ａｌｉｃｅの秘密鍵（ｍ_Ａ，ｎ_Ａ）が“ａ”と記述され、Ｂｏｂの秘密鍵（ｍ_Ｂ，ｎ_Ｂ）が“ｂ”と記述される。
上述した超特異楕円曲線Ｅの集合がＳＳＥＣ_ｐと記述される。補助ねじれ点基底を有する上述した超特異楕円曲線Ｅの集合が、ＳＳＥＣ_ｐ，Ａ及びＳＳＥＣ_ｐ，Ｂと記述される。ＳＳＥＣ_ｐ，ＡはＡｌｉｃｅがＢｏｂに送信する情報の集合であり、ＳＳＥＣ_ｐ，ＢはＢｏｂがＡｌｉｃｅに送信する情報の集合である。

そして、“ｇ^ａ”と“ｇ^ｂ”と“（ｇ^ｂ）^ａ”と“（ｇ^ａ）^ｂ”とが以下のように定義される。
ｇ^ａ：＝（Ｅ_Ａ：φ_Ａ（Ｐ_Ｂ），φ_Ａ（Ｑ_Ｂ））∈ＳＳＥＣ_ｐ，Ａ，ｗｈｅｒｅ Ｒ_Ａ＝ｍ_ＡＰ_Ａ＋ｎ_ＡＱ_Ａ，φ_Ａ：Ｅ→Ｅ_Ａ＝Ｅ／＜Ｒ_Ａ＞
ｇ^ｂ：＝（Ｅ_Ｂ：φ_Ｂ（Ｐ_Ａ），φ_Ｂ（Ｑ_Ａ））∈ＳＳＥＣ_ｐ，Ｂ，ｗｈｅｒｅ Ｒ_Ｂ＝ｍ_ＢＰ_Ｂ＋ｎ_ＢＱ_Ｂ，φ_Ｂ：Ｅ→Ｅ_Ｂ＝Ｅ／＜Ｒ_Ｂ＞
（ｇ^ｂ）^ａ：＝ｊ（Ｅ_ＢＡ），ｗｈｅｒｅ Ｒ_ＢＡ＝ｍ_Ａφ_Ｂ（Ｐ_Ａ）＋ｎ_Ａφ_Ｂ（Ｑ_Ａ），φ_ＢＡ：Ｅ_Ｂ→Ｅ_ＢＡ＝Ｅ_Ｂ／＜Ｒ_ＢＡ＞
（ｇ^ａ）^ｂ：＝ｊ（Ｅ_ＡＢ），ｗｈｅｒｅ Ｒ_ＡＢ＝ｍ_Ｂφ_Ａ（Ｐ_Ｂ）＋ｎ_Ｂφ_Ａ（Ｑ_Ｂ），φ_ＡＢ：Ｅ_Ａ→Ｅ_ＡＢ＝Ｅ_Ａ／＜Ｒ_ＡＢ＞

以上の記法を用いて、ＳＩＤＨ鍵共有方式を記述すると、図４に示すようになる。
ここで、公開パラメータは、ｇ＝（Ｅ；Ｐ_Ａ，Ｑ_Ａ，Ｐ_Ｂ，Ｑ_Ｂ）と、ｅ＝（Ｌ_Ａ，Ｌ_Ｂ，ｅ_Ａ，ｅ_Ｂ）である。
Ａｌｉｃｅは、秘密鍵空間ＳＫ_Ａからランダムに選択された秘密鍵ａを用いて、ｇ^ａを計算する。そして、Ａｌｉｃｅは、ｇ^ａをＢｏｂに送信する。同様に、Ｂｏｂは、秘密鍵空間ＳＫ_Ｂからランダムに選択された秘密鍵ｂを用いて、ｇ^ｂを計算する。そして、Ｂｏｂは、ｇ^ｂをＡｌｉｃｅに送信する。
Ａｌｉｃｅは、秘密鍵ａと、Ｂｏｂによって送信されたｇ^ｂとを用いて、共有鍵Ｋ_{Ａｌｉｃｅ}＝（ｇ^ｂ）^ａを計算する。同様に、Ｂｏｂは、秘密鍵ｂと、Ａｌｉｃｅによって送信されたｇ^ａとを用いて、共有鍵Ｋ_Ｂｏｂ＝（ｇ^ａ）^ｂを計算する。共有鍵Ｋ_{Ａｌｉｃｅ}＝（ｇ^ｂ）^ａ＝（ｇ^ａ）^ｂ＝共有鍵Ｋ_Ｂｏｂである。

＊＊＊構成の説明＊＊＊
図５を参照して、実施の形態１に係る鍵共有システム１の構成を説明する。
鍵共有システム１は、複数の鍵共有装置１０を備える。図５では、鍵共有システム１は、鍵共有装置１０Ａ〜鍵共有装置１０Ｄの鍵共有装置１０を備える。鍵共有装置１０は、ＰＣ（Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ）及びスマートフォンといったコンピュータである。鍵共有装置１０間は、伝送路３０を介して接続されている。伝送路３０は、インターネット、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）等である。

図６を参照して、実施の形態１に係る鍵共有装置１０の構成を説明する。
鍵共有装置１０は、プロセッサ１１と、メモリ１２と、ストレージ１３と、通信インタフェース１４とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。

プロセッサ１１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）である。プロセッサ１１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）である。

メモリ１２は、データを一時的に記憶する記憶装置である。メモリ１２は、具体例としては、ＳＲＡＭ（Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）である。

ストレージ１３は、データを保管する記憶装置である。ストレージ１３は、具体例としては、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）である。また、ストレージ１３は、ＳＤ（登録商標，Ｓｅｃｕｒｅ Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ，登録商標）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）といった可搬記録媒体であってもよい。

通信インタフェース１４は、外部の装置と通信するためのインタフェースである。通信インタフェース１４は、具体例としては、Ｅｔｈｅｒｎｅｔ（登録商標）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）、ＨＤＭＩ（登録商標，Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ Ｍｕｌｔｉｍｅｄｉａ Ｉｎｔｅｒｆａｃｅ）のポートである。

鍵共有装置１０は、機能構成要素として、受信部２１と、鍵選択部２２と、鍵生成部２３と、送信部２４とを備える。鍵生成部２３は、静的鍵生成部２５と、一時鍵生成部２６と、共有鍵生成部２７とを備える。鍵共有装置１０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ１３には、鍵共有装置１０の各機能構成要素の機能を実現するプログラムが格納されている。このプログラムは、プロセッサ１１によりメモリ１２に読み込まれ、プロセッサ１１によって実行される。これにより、鍵共有装置１０の各機能構成要素の機能が実現される。

図６では、プロセッサ１１は、１つだけ示されていた。しかし、プロセッサ１１は、複数であってもよく、複数のプロセッサ１１が、各機能を実現するプログラムを連携して実行してもよい。

＊＊＊動作の説明＊＊＊
図７から図９を参照して、実施の形態１に係る鍵共有システム１の動作を説明する。
実施の形態１に係る鍵共有システム１の動作は、実施の形態１に係る鍵共有方法に相当する。また、実施の形態１に係る鍵共有システム１の動作は、実施の形態１に係る鍵共有プログラムの処理に相当する。

鍵共有システム１は、公開パラメータとして、ｇ＝（Ｅ；Ｐ_１，Ｑ_１，Ｐ_２，Ｑ_２）と、ｅ＝（Ｌ_１，Ｌ_２，ｅ_１，ｅ_２）とを用いる。なお、ここでは、添え字が、図４で説明したＳＩＤＨ鍵共有方式における“Ａ”及び“Ｂ”から“１”及び“２”に変更されている。公開パラメータには、Ｌ_１のｅ_１乗に基づく（Ｐ_１，Ｑ_１）とＬ_２のｅ_２乗に基づく（Ｐ_２，Ｑ_２）との２つの分類のパラメータが含まれている。
また、鍵共有システム１は、数１５に示す（Ｐ_１，Ｑ_１）と同じ分類である、Ｌ_１のｅ_１乗に基づく秘密鍵空間ＳＫ_１と、（Ｐ_２，Ｑ_２）と同じ分類である、Ｌ_２のｅ_２乗に基づく秘密鍵空間ＳＫ_２とを用いる。

図７を参照して、実施の形態１に係る事前処理を説明する。
事前処理は、鍵共有システム１が備える各鍵共有装置１０により、後述する鍵共有処理が行われる前に実行される。ここでは、鍵共有装置１０Ａと鍵共有装置１０Ｂとが鍵共有を行う場合を例として説明する。

（ステップＳ１１：公開パラメータ取得処理）
受信部２１は、公開パラメータを取得する。
具体的には、受信部２１は、公開用のサーバから、公開パラメータであるｇ＝（Ｅ；Ｐ_１，Ｑ_１，Ｐ_２，Ｑ_２）と、ｅ＝（Ｌ_１，Ｌ_２，ｅ_１，ｅ_２）とを受信して、メモリ１２に書き込む。公開パラメータは、鍵共有システム１の管理装置によって生成され、公開用のサーバに記憶されている。

（ステップＳ１２：静的鍵生成処理）
静的鍵生成部２５は、ステップＳ１１で取得された公開パラメータに基づき、静的鍵を生成する。
具体的には、鍵共有装置１０Ａでは、静的鍵生成部２５は、メモリ１２から公開パラメータを読み出す。静的鍵生成部２５は、秘密鍵空間ＳＫ_１からランダムに要素を選択して静的秘密鍵ａ_１＝（ｍ_Ａ，１，ｎ_Ａ，１）を生成する。静的鍵生成部２５は、秘密鍵空間ＳＫ_２からランダムに要素を選択して静的秘密鍵ａ_２＝（ｍ_Ａ，２，ｎ_Ａ，２）を生成する。また、静的鍵生成部２５は、静的秘密鍵ａ_１を用いて、静的公開鍵Ａ_１＝ｇ＾ａ_１を生成する。静的鍵生成部２５は、静的秘密鍵ａ_２を用いて、静的公開鍵Ａ_２＝ｇ＾ａ_２を生成する。静的鍵生成部２５は、静的秘密鍵ａ_１及び静的公開鍵Ａ_１の組と、静的秘密鍵ａ_２及び静的公開鍵Ａ_２の組とをメモリ１２に書き込む。
同様に、鍵共有装置１０Ｂでは、静的鍵生成部２５は、メモリ１２から公開パラメータを読み出す。静的鍵生成部２５は、秘密鍵空間ＳＫ_１からランダムに要素を選択して静的秘密鍵ｂ_１＝（ｍ_Ｂ，１，ｎ_Ｂ，１）を生成する。静的鍵生成部２５は、秘密鍵空間ＳＫ_２からランダムに要素を選択して静的秘密鍵ｂ_２＝（ｍ_Ｂ，２，ｎ_Ｂ，２）を生成する。また、静的鍵生成部２５は、静的秘密鍵ｂ_１を用いて、静的公開鍵Ｂ_１＝ｇ＾ｂ_１を生成する。静的鍵生成部２５は、静的秘密鍵ｂ_２を用いて、静的公開鍵Ｂ_２＝ｇ＾ｂ_２を生成する。静的鍵生成部２５は、静的秘密鍵ｂ_１及び静的公開鍵Ｂ_１の組と、静的秘密鍵ｂ_２及び静的公開鍵Ｂ_２の組とをメモリ１２に書き込む。
ここで、静的秘密鍵ａ_１及び静的公開鍵Ａ_１の組と、静的秘密鍵ａ_２及び静的公開鍵Ａ_２の組と、静的秘密鍵ｂ_１及び静的公開鍵Ｂ_１の組と、静的秘密鍵ｂ_２及び静的公開鍵Ｂ_２の組とをそれぞれ静的鍵と呼ぶ。静的秘密鍵ａ_１及び静的公開鍵Ａ_１の組と、静的秘密鍵ｂ_１及び静的公開鍵Ｂ_１の組とは、Ｌ_１のべき乗に基づく要素であり、（Ｐ_１，Ｑ_１）と同じ分類である。静的秘密鍵ａ_２及び静的公開鍵Ａ_２の組と、静的秘密鍵ｂ_２及び静的公開鍵Ｂ_２の組とは、Ｌ_２のべき乗に基づく要素であり、（Ｐ_２，Ｑ_２）と同じ分類である。

（ステップＳ１３：鍵公開処理）
送信部２４は、ステップＳ１２で生成された静的公開鍵をメモリ１２から読み出す。そして、送信部２４は、読み出された静的公開鍵を公開用のサーバに送信して、鍵共有システム１が備える各鍵共有装置１０に公開する。
鍵共有装置１０Ａであれば、送信部２４は、静的公開鍵Ａ_１及び静的公開鍵Ａ_２をメモリ１２から読み出し、読み出された静的公開鍵Ａ_１及び静的公開鍵Ａ_２を公開用のサーバに送信する。鍵共有装置１０Ｂであれば、送信部２４は、静的公開鍵Ｂ_１及び静的公開鍵Ｂ_２をメモリ１２から読み出し、読み出された静的公開鍵Ｂ_１及び静的公開鍵Ｂ_２を公開用のサーバに送信する。

図８及び図９を参照して、実施の形態１に係る鍵共有処理を説明する。
前提として、鍵共有装置１０は、鍵共有を行う相手側の静的公開鍵を公開用のサーバから取得して、メモリ１２に記憶しているものとする。

（ステップＳ２１：鍵選択処理）
鍵選択部２２は、分類の異なる２つの静的鍵から、１つの静的鍵を選択する。
具体的には、鍵選択部２２は、分類の異なる２つの静的鍵から、相手側と異なる分類の静的鍵を選択する。つまり、鍵共有装置１０Ａでは、鍵選択部２２は、静的秘密鍵ａ_１及び静的公開鍵Ａ_１の組と、静的秘密鍵ａ_２及び静的公開鍵Ａ_２の組とのうち、鍵共有を行う相手側である鍵共有装置１０Ｂと異なる組を選択する。同様に、鍵共有装置１０Ｂでは、鍵選択部２２は、静的秘密鍵ｂ_１及び静的公開鍵Ｂ_１の組と、静的秘密鍵ｂ_２及び静的公開鍵Ｂ_２の組とのうち、鍵共有を行う相手側である鍵共有装置１０Ａと異なる組を選択する。
具体例としては、鍵選択部２２は、鍵の共有を開始する開始側か否かに応じて、２つの静的鍵のうち、一方を選択する。これに限らず、予め定められたルールに従い、互いに異なる組が選択されるようにしておけばよい。鍵選択部２２は、選択された静的鍵をメモリ１２に書き込む。
ここでは、鍵選択部２２は、鍵の共有を開始する開始側の鍵共有装置１０（ここでは、鍵共有装置１０Ａとする）である場合には、（Ｐ_１，Ｑ_１）と同じ分類である、静的秘密鍵ａ_１及び静的公開鍵Ａ_１の組を選択する。一方、鍵選択部２２は、開始側に応答して鍵の共有を行う応答側の鍵共有装置１０（ここでは、鍵共有装置１０Ｂとする）である場合には、（Ｐ_２，Ｑ_２）と同じ分類である、静的秘密鍵ｂ_２及び静的公開鍵Ｂ_２の組を選択する。例えば、鍵共有開始前の事前通信でどちらが開始側であるかを特定することが可能である。

（ステップＳ２２：一時鍵生成処理）
一時鍵生成部２６は、ステップＳ２１で選択された静的鍵と同じ分類の一時鍵を生成する。
具体的には、一時鍵生成部２６は、ステップＳ２１で選択された静的鍵と同じ分類の秘密鍵空間からランダムに要素を選択して一時秘密鍵を生成する。開始側の鍵共有装置１０Ａの一時鍵生成部２６は、静的秘密鍵ａ_１及び静的公開鍵Ａ_１の組と同じ分類の秘密鍵空間ＳＫ_１からランダムに要素を選択して一時秘密鍵ｘ＝（ｍ_ｘ，ｎ_ｘ）を生成する。また、応答側の鍵共有装置１０Ｂの一時鍵生成部２６は、静的秘密鍵ｂ_２及び静的公開鍵Ｂ_２の組と同じ分類の秘密鍵空間ＳＫ_２からランダムに要素を選択して一時秘密鍵ｙ＝（ｍ_ｙ，ｎ_ｙ）を生成する。
また、一時鍵生成部２６は、一時秘密鍵を用いて、一時公開鍵を生成する。開始側の鍵共有装置１０Ａの一時鍵生成部２６は、一時秘密鍵ｘを用いて、一時公開鍵Ｘ＝ｇ^ｘを生成する。また、応答側の鍵共有装置１０Ｂの一時鍵生成部２６は、一時秘密鍵ｙを用いて、一時公開鍵Ｙ＝ｇ^ｙを生成する。
一時秘密鍵と一時公開鍵とを総称して一時鍵と呼ぶ。一時鍵生成部２６は、生成された一時鍵をメモリ１２に書き込む。

（ステップＳ２３：一時公開鍵送信処理）
送信部２４は、ステップＳ２２で生成された一時公開鍵を、鍵共有の相手側の鍵共有装置１０に送信する。
具体的には、送信部２４は、メモリ１２から一時公開鍵を読み出す。送信部２４は、読み出された一時公開鍵を、通信インタフェース１４を介して相手側の鍵共有装置１０に送信する。すると、一時公開鍵は、伝送路３０を通って、相手側の鍵共有装置１０に送信され、相手側の鍵共有装置１０の受信部２１によって受信される。
開始側の鍵共有装置１０Ａの送信部２４は、一時公開鍵Ｘを応答側の鍵共有装置１０Ｂに送信する。鍵共有装置１０Ｂの受信部２１は、一時公開鍵Ｘを受信してメモリ１２に書き込む。また、応答側の鍵共有装置１０Ｂは、一時公開鍵Ｙを開始側の鍵共有装置１０Ａに送信する。鍵共有装置１０Ａの受信部２１は、一時公開鍵Ｙを受信してメモリ１２に書き込む。

（ステップＳ２４：共有鍵生成処理）
共有鍵生成部２７は、ステップＳ２１で選択された静的鍵と、ステップＳ２２で生成された一時秘密鍵と、ステップＳ２３で相手側によって生成された一時公開鍵と、相手側の静的公開鍵とを用いて、共有鍵を生成する。
具体的には、共有鍵生成部２７は、ステップＳ２１で選択された静的鍵と、ステップＳ２２で生成された一時秘密鍵と、ステップＳ２３で受信された相手側の一時公開鍵と、相手側の静的公開鍵とを、メモリ１２から読み出す。そして、共有鍵生成部２７は、以下のように、値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４とを計算し、メモリ１２に書き込む。
開始側の鍵共有装置１０Ａの共有鍵生成部２７は、値Ｚ_１＝Ｙ＾ａ_１、値Ｚ_２＝Ｂ_２ ^ｘ、値Ｚ_３＝Ｂ_２＾ａ_１、値Ｚ_４＝Ｙ^ｘのように、値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４とを計算する。応答側の鍵共有装置１０Ｂの共有鍵生成部２７は、値Ｚ_１＝Ａ_１ ^ｙ、値Ｚ_２＝Ｘ＾ｂ_２、値Ｚ_３＝Ａ_１＾ｂ_２、値Ｚ_４＝Ｘ^ｙのように、値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４とを計算する。
ここで、値Ｚ_１＝Ｙ＾ａ_１＝（ｇ^ｙ）＾ａ_１＝（ｇ＾ａ_１）^ｙ＝Ａ_１ ^ｙである。値Ｚ_２＝Ｂ_２ ^ｘ＝（ｇ＾ｂ_２）^ｘ＝（ｇ^ｘ）＾ｂ_２＝Ｘ＾ｂ_２である。値Ｚ_３＝Ｂ_２＾ａ_１＝（ｇ＾ｂ_２）＾ａ_１＝（ｇ＾ａ_１）＾ｂ_２＝Ａ_１＾ｂ_２である。値Ｚ_４＝Ｙ^ｘ＝（ｇ^ｙ）^ｘ＝（ｇ^ｘ）^ｙ＝Ｘ^ｙである。したがって、開始側の鍵共有装置１０Ａで計算される値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４と、応答側の鍵共有装置１０Ｂで計算される値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４とは、いずれも等しい。

共有鍵生成部２７は、計算された値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４とを用いて、共通鍵Ｋを生成する。
具体例としては、共有鍵生成部２７は、値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４とを入力としてハッシュ関数Ｈを計算して、共通鍵Ｋを生成する。この際、共有鍵生成部２７は、値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４とに加え、プロトコルの識別子であるΠと、開始側の鍵共有装置１０Ａの識別子Ａと、応答側の鍵共有装置１０Ｂの識別子Ｂと、開始側の鍵共有装置１０Ａの一時公開鍵Ｘと、応答側の鍵共有装置１０Ｂの一時公開鍵Ｙとも入力としてもよい。つまり、共有鍵生成部２７は、Ｋ＝Ｈ（Π，Ｚ_１，Ｚ_２，Ｚ_３，Ｚ_４，Ａ，Ｂ，Ｘ，Ｙ）を計算して、共通鍵Ｋを計算してもよい。

なお、値Ｚ_１と値Ｚ_２と値Ｚ_３と値Ｚ_４との一部を１つの値にまとめるといった修正を加えてもよい。

＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る鍵共有システム１は、２つの分類の静的鍵を用意しておき、鍵共有の相手側と異なる静的鍵を用いるようにする。これにより、非対称性を持つ鍵共有方式を認証機能付きの鍵共有方式に変換することが可能になる。

認証機能付きの鍵共有について説明する。
認証機能付きの鍵共有のプロトコルでは、鍵共有を行う二者は、自身の静的な公開鍵を持ち、一時公開鍵を交換する。そして、鍵共有を行う二者は、相手側の静的な公開鍵と、相手側から受け取った一時公開鍵と、自身の静的な公開鍵に対応する静的な秘密鍵と、自身の一時公開鍵に対応する一時秘密鍵とに基づき共有鍵を計算する。
静的な公開鍵及び静的な秘密鍵を総称して静的鍵と呼ぶ。静的鍵は、長期間変更されない鍵である。一時公開鍵及び一時秘密鍵を総称して一時鍵と呼ぶ。一時鍵は、共有鍵を生成する際に一時的に用いられる鍵である。共有鍵は、二者間で共有される鍵である。
認証機能付きの鍵共有プロトコルでは、相手側の静的な公開鍵を用いて共有鍵が計算される。静的な公開鍵は、長期間変更されない鍵である。そのため、共有鍵を共有する相手を特定可能である。

また、実施の形態１に係る鍵共有システム１は、ＳＩＤＨ鍵共有方式を変換することにより、１ラウンドの認証機能付きの鍵共有方式を実現することが可能である。

１ラウンドについて説明する。
１ラウンドは、鍵共有を行う二者がメッセージを独立かつ同時に送ることが可能であることを意味する。つまり、１ラウンドは、二者のうち一方から他方へメッセージを送り、このメッセージを受けて他方から一方へメッセージを返すという往復通信が不要であることを意味する。この往復通信が必要であることは２ｐａｓｓと呼ばれる。１ラウンドの認証機能付きの鍵共有方式を実現することにより、鍵共有装置１０は、鍵共有の開始前に一時鍵を計算しておくことが可能である。そして、鍵共有を行う鍵共有装置１０同士で、同時に一時鍵の交換を行うことが可能である。したがって、効率的に鍵共有を行うことが可能である。

なお、文献“Ｆｕｊｉｏｋａ， Ａ．， Ｓｕｚｕｋｉ， Ｋ．， Ｘａｇａｗａ， Ｋ．， Ｙｏｎｅｙａｍａ， Ｋ．： Ｓｔｒｏｎｇｌｙ ｓｅｃｕｒｅ ａｕｔｈｅｎｔｉｃａｔｅｄ ｋｅｙ ｅｘｃｈａｎｇｅ ｆｒｏｍ ｆａｃｔｏｒｉｎｇ， ｃｏｄｅｓ， ａｎｄ ｌａｔｔｉｃｅｓ． Ｄｅｓ． Ｃｏｄｅｓ Ｃｒｙｐｔｏｇｒａｐｈｙ ７６（３），４６９−５０４ （２０１５）， ａ ｐｒｅｌｉｍｉｎａｒｙ ｖｅｒｓｉｏｎ ａｐｐｅａｒｅｄ ｉｎ ＰＫＣ ２０１２ （２０１２）”に記載された方法で実現される認証機能付きの鍵共有方式は、往復通信が必要であり、１ラウンドの認証機能付きの鍵共有方式ではない。
また、実施の形態１に係る鍵共有システム１で実現される認証機能付きの鍵共有方式は、単一の楕円曲線において実現される方式である。そのため、上記文献に記載された鍵共有方式に比べ、通信するデータサイズを小さくすることができる。つまり、効率的な鍵共有方式を実現することができる。

また、実施の形態１に係る鍵共有システム１は、２つの分類の静的鍵を用意しておき、開始側か応答側かによって静的鍵を選択する。そのため、実施の形態１に係る鍵共有システム１で実現される認証機能付きの鍵共有方式は、認証システムを攻撃する方法である反射攻撃に対する耐性がある。反射攻撃については、文献“Ｔａｎｅｎｂａｕｍ， Ａ．Ｓ．： Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ． Ｐｅａｒｓｏｎ （２００２）”に記載がある。

また、実施の形態１に係る鍵共有システム１で実現される認証機能付きの鍵共有方式は、量子計算機に対して安全性を担保できるだけでなく、量子ランダムオラクルモデルにおける安全性についても証明可能である。

＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、非対称性を持つ鍵共有方式として、ＳＩＤＨ鍵共有方式を例として説明した。しかし、ＳＩＤＨ鍵共有方式に限らず、他の鍵共有方式に対して２つの静的鍵を用意しておき、鍵共有の相手側と異なる静的鍵を用いるようにするという技術を適用して、その鍵共有方式を認証機能付きの鍵共有方式に変換することも可能である。適用対象の鍵共有方式が耐量子性を持つ方式であれば、変換して得られた認証機能付きの鍵共有方式も耐量子性を持つ方式である可能性がある。

＜変形例２＞
実施の形態１では、各機能構成要素がソフトウェアで実現された。しかし、変形例２として、各機能構成要素はハードウェアで実現されてもよい。この変形例２について、実施の形態１と異なる点を説明する。

図１０を参照して、変形例２に係る鍵共有装置１０の構成を説明する。
各機能構成要素がハードウェアで実現される場合には、鍵共有装置１０は、プロセッサ１１とメモリ１２とストレージ１３とに代えて、電子回路１５を備える。電子回路１５は、各機能構成要素と、メモリ１２と、ストレージ１３との機能とを実現する専用の回路である。

電子回路１５としては、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）が想定される。
各機能構成要素を１つの電子回路１５で実現してもよいし、各機能構成要素を複数の電子回路１５に分散させて実現してもよい。

＜変形例３＞
変形例３として、一部の各機能構成要素がハードウェアで実現され、他の各機能構成要素がソフトウェアで実現されてもよい。

プロセッサ１１とメモリ１２とストレージ１３と電子回路１５とを処理回路という。つまり、各機能構成要素の機能は、処理回路により実現される。

１０ 鍵共有装置、１１ プロセッサ、１２ メモリ、１３ ストレージ、１４ 通信インタフェース、１５ 電子回路、２１ 受信部、２２ 鍵選択部、２３ 鍵生成部、２４ 送信部、２５ 静的鍵生成部、２６ 一時鍵生成部、２７ 共有鍵生成部、３０ 伝送路。

Claims (4)

1. 事前に記憶装置に記憶された静的秘密鍵及び静的公開鍵の組である静的鍵であって、数１に示す公開鍵Ａ１及び秘密鍵ａ１の組と、公開鍵Ａ２及び秘密鍵ａ２の組とである、異なる素数に基づき生成された分類の異なる２つの静的鍵から、鍵の共有を開始する開始側か否かに応じて静的鍵を選択することにより、相手側によって選択される静的鍵と異なる分類の静的鍵を選択する鍵選択部と、
   前記鍵選択部によって選択された静的鍵を用いて、前記相手側と共有する共有鍵を生成する鍵生成部と
   を備え、
   前記鍵生成部は、
   前記鍵選択部によって選択された静的鍵と同じ分類の一時鍵Ｘであって、数２に示す一時鍵Ｘを生成する一時鍵生成部と、
   前記鍵選択部によって選択された静的鍵と、前記相手側によって生成された一時鍵とを用いて、前記共有鍵を生成する共有鍵生成部と
   を備える鍵共有装置。
   

   

   
2. 前記共有鍵生成部は、数３に示す一時鍵Ｙを用いて、数４に示す値Ｚ１と値Ｚ２と値Ｚ３と値Ｚ４とに基づき共有鍵を生成する
   請求項１に記載の鍵共有装置。
   

   

   
3. コンピュータが、事前に記憶装置に記憶された静的秘密鍵及び静的公開鍵の組である静的鍵であって、数５に示す公開鍵Ａ１及び秘密鍵ａ１の組と、公開鍵Ａ２及び秘密鍵ａ２の組とである、異なる素数に基づき生成された分類の異なる２つの静的鍵から、鍵の共有を開始する開始側か否かに応じて静的鍵を選択することにより、相手側によって選択される静的鍵と異なる分類の静的鍵を選択し、
   コンピュータが、選択された静的鍵と同じ分類の一時鍵Ｘであって、数６に示す一時鍵Ｘを生成し、選択された静的鍵と、前記相手側によって生成された一時鍵とを用いて、相手側と共有する共有鍵を生成する鍵共有方法。
   

   

   
4. 事前に記憶装置に記憶された静的秘密鍵及び静的公開鍵の組である静的鍵であって、数７に示す公開鍵Ａ１及び秘密鍵ａ１の組と、公開鍵Ａ２及び秘密鍵ａ２の組とである、異なる素数に基づき生成された分類の異なる２つの静的鍵から、鍵の共有を開始する開始側か否かに応じて静的鍵を選択することにより、相手側によって選択される静的鍵と異なる分類の静的鍵を選択する鍵選択処理と、
   前記鍵選択処理によって選択された静的鍵を用いて、相手側と共有する共有鍵を生成する鍵生成処理と
   をコンピュータに実行させ、
   前記鍵生成処理では、
   前記鍵選択処理によって選択された静的鍵と同じ分類の一時鍵Ｘであって、数８に示す一時鍵Ｘを生成する一時鍵生成処理と、
   前記鍵選択処理によって選択された静的鍵と、前記相手側によって生成された一時鍵とを用いて、前記共有鍵を生成する共有鍵生成処理と
   をコンピュータに実行させる鍵共有プログラム。
   

   

   

Images