(57)【要約】  Ｎ台の端末装置Ｕｉと、セッション鍵の交換に用いられる鍵配信サーバとが含まれる鍵配信システムであって、Ｎが偶数である場合、奇数番目の端末装置Ｕｉが所定の楕円曲線の第１のねじれ部分群の基底を用いた第１の公開値を計算し、偶数番目の端末装置Ｕｉが前記楕円曲線の第２のねじれ部分群の基底を用いた第２の公開値を計算する同種写像計算手段と、前記鍵配信サーバが、奇数番目の端末装置Ｕｉにより計算された第１の公開値を端末装置Ｕｉ−１及び端末装置Ｕｉ＋１に配信し、偶数番目の端末装置Ｕｉにより計算された第２の公開値を端末装置Ｕｉ−１及び端末装置Ｕｉ＋１に配信する配信手段と、前記配信手段により配信された第２の公開値を用いて奇数番目の端末装置Ｕｉが前記セッション鍵を生成し、前記配信手段により配信された第１の公開値を用いて偶数番目の端末装置Ｕｉが前記セッション鍵を生成する鍵生成手段と、を有し、前記同種写像計算手段は、Ｎが奇数である場合、前記端末装置Ｕｉのうち、所定の端末装置ＵＩが前記第１のねじれ部分群の基底を用いた第１の公開値と、前記第２のねじれ部分群の基底を用いた第２の公開値とを計算する、ことを特徴とする鍵配信システム。
2019198516.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ（ただし、Ｎ≧２）台の端末装置Ｕｉ（ｉ＝１，・・・，Ｎ）と、該Ｎ台の端末装置Ｕｉ間で同種写像暗号によるセッション鍵の交換に用いられる鍵配信サーバとが含まれる鍵配信システムであって、
Ｎが偶数である場合、前記端末装置Ｕｉのうち、奇数番目の端末装置Ｕｉ（ｉ＝１，・・・，Ｎ−１）が所定の楕円曲線の第１のねじれ部分群の基底を用いた第１の公開値を計算し、偶数番目の端末装置Ｕｉ（ｉ＝２，・・・，Ｎ）が前記楕円曲線の第２のねじれ部分群の基底を用いた第２の公開値を計算する同種写像計算手段と、
前記鍵配信サーバが、奇数番目の端末装置Ｕｉにより計算された第１の公開値を端末装置Ｕｉ−１（ただし、ｉ＝１である場合、Ｕ０＝ＵＮ）及び端末装置Ｕｉ＋１（ただし、ｉ＝Ｎである場合、ＵＮ＋１＝Ｕ１）に配信し、偶数番目の端末装置Ｕｉにより計算された第２の公開値を端末装置Ｕｉ−１及び端末装置Ｕｉ＋１に配信する配信手段と、
前記配信手段により配信された第２の公開値を用いて奇数番目の端末装置Ｕｉが前記セッション鍵を生成し、前記配信手段により配信された第１の公開値を用いて偶数番目の端末装置Ｕｉが前記セッション鍵を生成する鍵生成手段と、
を有し、
前記同種写像計算手段は、
Ｎが奇数である場合、前記端末装置Ｕｉのうち、予め決められた所定の端末装置ＵＩが前記第１のねじれ部分群の基底を用いた第１の公開値と、前記第２のねじれ部分群の基底を用いた第２の公開値とを計算する、ことを特徴とする鍵配信システム。
【請求項２】
Ｎ（ただし、Ｎ≧２）台の端末装置Ｕｉ（ｉ＝１，・・・，Ｎ）と、該Ｎ台の端末装置Ｕｉ間で同種写像暗号によるセッション鍵の交換に用いられる鍵配信サーバとが含まれる鍵配信システムであって、
前記端末装置Ｕｉが所定の楕円曲線の第１のねじれ部分群の基底を用いた第１の公開値と、前記楕円曲線の第２のねじれ部分群の基底を用いた第２の公開値とを計算する同種写像計算手段と、
前記鍵配信サーバが、前記端末装置Ｕｉにより計算された第１の公開値と第２の公開値とをそれぞれ端末装置Ｕｉ−１（ただし、ｉ＝１である場合、Ｕ０＝ＵＮ）及び端末装置Ｕｉ＋１（ただし、ｉ＝Ｎである場合、ＵＮ＋１＝Ｕ１）に配信する配信手段と、
前記配信手段により配信された第１の公開値及び第２の公開値を用いて、前記端末装置Ｕｉが前記セッション鍵を生成する鍵生成手段と、
を有することを特徴とする鍵配信システム。
【請求項３】
前記同種写像計算手段は、
前記第１のねじれ部分群の基底を｛ＰＡ，ＱＡ｝、前記第２のねじれ部分群の基底を｛ＰＢ，ＱＢ｝、前記第１のねじれ部分群に関する第１のねじれ疑似ランダム関数値をｍｉ、前記第１のねじれ部分群に関する第２のねじれ疑似ランダム関数値をｎｉ、［ｍｉ］ＰＡ＋［ｎｉ］ＱＡで生成される前記楕円曲線の部分群を核に持つ同種写像φｉとした場合に、前記第１の公開値として、φｉ（ＰＢ）及びφｉ（ＱＢ）を計算し、
前記第２のねじれ部分群に関する第３のねじれ疑似ランダム関数値をｍ´ｉ、前記第２のねじれ部分群に関する第４のねじれ疑似ランダム関数値をｎ´ｉ、［ｍ´ｉ］ＰＢ＋［ｎ´ｉ］ＱＢで生成される前記楕円曲線の部分群を核に持つ同種写像φ´ｉとした場合に、前記第２の公開値として、φ´ｉ（ＰＡ）及びφ´ｉ（ＱＡ）を計算する、
ことを特徴とする請求項１又は２に記載の鍵配信システム。
【請求項４】
前記鍵生成手段は、
前記配信手段により配信された第１の公開値φｉ−１（ＰＢ）及びφｉ−１（ＱＢ）並びにφｉ＋１（ＰＢ）及びφｉ＋１（ＱＢ）が配信された場合、［ｍｉ］φｉ−１（ＰＢ）＋［ｎｉ］φｉ−１（ＱＢ）で生成される楕円曲線の部分群を核に持つ同種写像に付随する楕円曲線の第１のｊ不変量と、［ｍｉ］φｉ＋１（ＰＢ）＋［ｎｉ］φｉ＋１（ＱＢ）で生成される楕円曲線の部分群を核に持つ同種写像に付随する楕円曲線の第２のｊ不変量とを計算し、計算された第１のｊ不変量及び第２のｊ不変量を用いて前記セッション鍵を生成し、
前記配信手段により配信された第２の公開値φｉ−１（ＰＡ）及びφｉ−１（ＱＡ）並びにφｉ＋１（ＰＡ）及びφｉ＋１（ＱＡ）が配信された場合、［ｍ´ｉ］φ´ｉ−１（ＰＡ）＋［ｎ´ｉ］φ´ｉ−１（ＱＡ）で生成される楕円曲線の部分群を核に持つ同種写像に付随する楕円曲線の第３のｊ不変量と、［ｍ´ｉ］φ´ｉ＋１（ＰＡ）＋［ｎ´ｉ］φ´ｉ＋１（ＱＡ）で生成される楕円曲線の部分群を核に持つ同種写像に付随する楕円曲線の第４のｊ不変量とを計算し、計算された第３のｊ不変量及び第４のｊ不変量を用いて前記セッション鍵を生成する、
ことを特徴とする請求項３に記載の鍵配信システム。
【請求項５】
同種写像暗号によるセッション鍵の交換に用いられる鍵配信サーバと接続される端末装置であって、
所定の楕円曲線の第１のねじれ部分群の基底を用いた第１の公開値又は／及び前記楕円曲線の第２のねじれ部分群の基底を用いた第２の公開値を計算する同種写像計算手段と、
前記セッション鍵を共有する１以上の他の端末装置のうち、所定の２台の端末装置でそれぞれ計算された第１の公開値又は／及び第２の公開値を前記鍵配信サーバから受信する受信手段と、
前記受信手段が受信した第１の公開値又は／及び第２の公開値を用いて、前記セッション鍵を生成する鍵生成手段と、
を有することを特徴とする端末装置。
【請求項６】
Ｎ（ただし、Ｎ≧２）台の端末装置Ｕｉ（ｉ＝１，・・・，Ｎ）と、該Ｎ台の端末装置Ｕｉ間で同種写像暗号によるセッション鍵の交換に用いられる鍵配信サーバとが含まれる鍵配信システムによる鍵配信方法であって、
Ｎが偶数である場合、前記端末装置Ｕｉのうち、奇数番目の端末装置Ｕｉ（ｉ＝１，・・・，Ｎ−１）が所定の楕円曲線の第１のねじれ部分群の基底を用いた第１の公開値を計算し、偶数番目の端末装置Ｕｉ（ｉ＝２，・・・，Ｎ）が前記楕円曲線の第２のねじれ部分群の基底を用いた第２の公開値を計算する同種写像計算手順と、
前記鍵配信サーバが、奇数番目の端末装置Ｕｉにより計算された第１の公開値を端末装置Ｕｉ−１（ただし、ｉ＝１である場合、Ｕ０＝ＵＮ）及び端末装置Ｕｉ＋１（ただし、ｉ＝Ｎである場合、ＵＮ＋１＝Ｕ１）に配信し、偶数番目の端末装置Ｕｉにより計算された第２の公開値を端末装置Ｕｉ−１及び端末装置Ｕｉ＋１に配信する配信手順と、
前記配信手順により配信された第２の公開値を用いて奇数番目の端末装置Ｕｉが前記セッション鍵を生成し、前記配信手順により配信された第１の公開値を用いて偶数番目の端末装置Ｕｉが前記セッション鍵を生成する鍵生成手順と、
を有し、
前記同種写像計算手順は、
Ｎが奇数である場合、前記端末装置Ｕｉのうち、予め決められた所定の端末装置ＵＩが前記第１のねじれ部分群の基底を用いた第１の公開値と、前記第２のねじれ部分群の基底を用いた第２の公開値とを計算する、ことを特徴とする鍵配信方法。
【請求項７】
Ｎ（ただし、Ｎ≧２）台の端末装置Ｕｉ（ｉ＝１，・・・，Ｎ）と、該Ｎ台の端末装置Ｕｉ間で同種写像暗号によるセッション鍵の交換に用いられる鍵配信サーバとが含まれる鍵配信システムによる鍵配信方法であって、
前記端末装置Ｕｉが所定の楕円曲線の第１のねじれ部分群の基底を用いた第１の公開値と、前記楕円曲線の第２のねじれ部分群の基底を用いた第２の公開値とを計算する同種写像計算手順と、
前記鍵配信サーバが、前記端末装置Ｕｉにより計算された第１の公開値と第２の公開値とをそれぞれ端末装置Ｕｉ−１（ただし、ｉ＝１である場合、Ｕ０＝ＵＮ）及び端末装置Ｕｉ＋１（ただし、ｉ＝Ｎである場合、ＵＮ＋１＝Ｕ１）に配信する配信手順と、
前記配信手順により配信された第１の公開値及び第２の公開値を用いて、前記端末装置Ｕｉが前記セッション鍵を生成する鍵生成手順と、
を有することを特徴とする鍵配信方法。
【請求項８】
同種写像暗号によるセッション鍵の交換に用いられる鍵配信サーバと接続される端末装置を、
所定の楕円曲線の第１のねじれ部分群の基底を用いた第１の公開値又は／及び前記楕円曲線の第２のねじれ部分群の基底を用いた第２の公開値を計算する同種写像計算手段、
前記セッション鍵を共有する１以上の他の端末装置のうち、所定の２台の端末装置でそれぞれ計算された第１の公開値又は／及び第２の公開値を前記鍵配信サーバから受信する受信手段、
前記受信手段が受信した第１の公開値又は／及び第２の公開値を用いて、前記セッション鍵を生成する鍵生成手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵配信システム、端末装置、鍵配信方法、及びプログラムに関する。
【背景技術】
【０００２】
スマートフォンやタブレット端末等の各種ユーザ端末の普及に伴って、何等かのデータをサーバに預託することで、このデータを多人数で共有するようなサービスが増えてきた。このようなサービスとしては、例えば、オンラインストレージサービス、グループチャットサービス、グループメールサービス等が挙げられる。【０００３】
上記のようなサービスを提供するシステムでは、例えば、通信路を暗号化することで通信経路上の盗聴防止が施されていたり、ユーザ端末にデータを残さないことによってユーザ端末の紛失や不正な持ち出しに起因する情報漏えい防止が施されていたりする。このように、上記のようなサービスを提供するシステムでは、通信経路に対する脅威（例えば、盗聴等）やユーザ端末に対する脅威（例えば、紛失や不正な持ち出し等）に対処が行われている場合が多い。【０００４】
ここで、上記のようなサービスを提供するシステムにおいては、サーバに対する脅威に起因する情報漏えいの恐れも考えられる。サーバに対する脅威には、例えば、サーバに対する外部からの攻撃やサーバ管理者等による内部不正等がある。これらの脅威に起因する情報漏えいを防止する方法として、例えば、サーバに対してはデータを秘匿化し、ユーザ端末でのみデータの復号可能なエンドツーエンド暗号化を行う方法がある。【０００５】
エンドツーエンド暗号化では、ユーザ端末間で用いる共通鍵をどのように共有するかが問題となる。これに対して、多者間鍵交換技術の１つとして、中央に認証サーバが配置されたスター型のネットワークにおいて、認証サーバに対していかなる情報も漏らさずにユーザ端末間で鍵（以下「セッション鍵」と表す。）を共有することが可能な動的多者鍵配布（ＤＭＫＤ：Dynamic Multi-Cast Key Distribution）プロトコルが知られている。ＤＭＫＤプロトコルによって、認証サーバに対してデータの内容を秘匿したままユーザ端末間でデータの送受信を行うことができるようになる。また、ＤＭＫＤプロトコルでは、データの送受信を行う複数のユーザ端末間でのみセッション鍵の共有を行うため、例えば、これらの複数のユーザ端末に対して新たなユーザ端末が追加された場合やこれらの複数のユーザ端末から或るユーザ端末が離脱した場合等にはセッション鍵が更新される。【０００６】
ところで、以下の参考文献１では、ＤＨ（Diffie-Hellman）鍵交換を用いたＤＭＫＤプロトコルが提案されている。【０００７】
［参考文献１］
K. Yoneyama, R. Yoshida, Y. Kawahara, T. Kobayashi, H. Fuji, and T. Yamamoto. 2016. Multi-Cast Key Distribution: Scalable, Dynamic and Provably Secure Construction. Cryptology ePrint Archive, Report 2016/833. (2016).
しかしながら、参考文献１で提案されているＤＭＫＤプロトコルは、ＤＨ鍵交換を用いているため、耐量子性がないことが知られている。このため、今後、量子コンピュータの実用化が進むにつれて、計算量仮定であるＣＤＨ（Computational Diffie-Hellman)・ＤＤＨ（Decisional Diffie-Hellman）問題が効率よく解かれてしまい、鍵共有の安全性が担保されない可能性がある。これに対して、鍵カプセル化メカニズム（ＫＥＭ：Key Encapsulation Mechanism）を用いることで、格子暗号や符号ベース暗号等の耐量子暗号に適用可能なＤＭＫＤプロトコルが提案されている（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】金城皓羽、岡野裕樹、斉藤恒和、草川恵太、小林鉄太郎、星野文学、「KEMを用いた動的多者鍵配布プロトコル」、SCIS2018
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、非特許文献１で提案されている手法は耐量子があるものの、鍵カプセル化メカニズムを用いているため、ＤＨ鍵交換を用いたＤＭＫＤプロトコルよりも１ラウンド多い通信が必要である。このため、非特許文献１で提案されている手法は、ＤＨ鍵交換を用いたＤＭＫＤプロトコルよりも余分な通信コストが必要であった。【００１０】
本発明は、上記の点に鑑みてなされたもので、耐量子性があり、かつ、通信コストが少ない多者間鍵交換を実現することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明の実施の形態は、Ｎ（ただし、Ｎ≧２）台の端末装置Ｕｉ（ｉ＝１，・・・，Ｎ）と、該Ｎ台の端末装置Ｕｉ間で同種写像暗号によるセッション鍵の交換に用いられる鍵配信サーバとが含まれる鍵配信システムであって、Ｎが偶数である場合、前記端末装置Ｕｉのうち、奇数番目の端末装置Ｕｉ（ｉ＝１，・・・，Ｎ−１）が所定の楕円曲線の第１のねじれ部分群の基底を用いた第１の公開値を計算し、偶数番目の端末装置Ｕｉ（ｉ＝２，・・・，Ｎ）が前記楕円曲線の第２のねじれ部分群の基底を用いた第２の公開値を計算する同種写像計算手段と、前記鍵配信サーバが、奇数番目の端末装置Ｕｉにより計算された第１の公開値を端末装置Ｕｉ−１（ただし、ｉ＝１である場合、Ｕ０＝ＵＮ）及び端末装置Ｕｉ＋１（ただし、ｉ＝Ｎである場合、ＵＮ＋１＝Ｕ１）に配信し、偶数番目の端末装置Ｕｉにより計算された第２の公開値を端末装置Ｕｉ−１及び端末装置Ｕｉ＋１に配信する配信手段と、前記配信手段により配信された第２の公開値を用いて奇数番目の端末装置Ｕｉが前記セッション鍵を生成し、前記配信手段により配信された第１の公開値を用いて偶数番目の端末装置Ｕｉが前記セッション鍵を生成する鍵生成手段と、を有し、前記同種写像計算手段は、Ｎが奇数である場合、前記端末装置Ｕｉのうち、予め決められた所定の端末装置ＵＩが前記第１のねじれ部分群の基底を用いた第１の公開値と、前記第２のねじれ部分群の基底を用いた第２の公開値とを計算する、ことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、耐量子性があり、かつ、通信コストが少ない多者間鍵交換を実現することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態における鍵交換システムのシステム構成の一例を示す図である。
【図２】本発明の実施の形態における鍵配信サーバの機能構成の一例を示す図である。
【図３】本発明の実施の形態におけるユーザ端末の機能構成の一例を示す図である。
【図４】本発明の実施の形態における鍵交換システムの事前処理の流れの一例を説明するための図である。
【図５】本発明の実施の形態における鍵交換システムの鍵交換処理の流れの一例を説明するための図である。
【図６】本発明の実施の形態における鍵配信サーバ及びユーザ端末のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について説明する。本発明の実施の形態では、耐量子暗号として同種写像暗号を用いて、非特許文献１で提案されている手法よりも少ないラウンド（２ラウンド）の通信で多者間鍵交換を行う鍵交換システム１について説明する。
【００１５】
＜システム構成＞
図１に示すように、本発明の実施の形態における鍵交換システム１には、鍵配信サーバ１０と、複数のユーザ端末２０とが含まれる。鍵配信サーバ１０と各ユーザ端末２０とは、例えばインターネット等のネットワーク３０を介して通信可能に接続されている。
【００１６】
鍵配信サーバ１０は、各ユーザ端末２０間で共通鍵を共有するために、各ユーザ端末２０の公開鍵の配信を行うサーバである。鍵配信サーバ１０は、１台の情報処理装置（コンピュータ）又は複数台の情報処理装置で実現される。
【００１７】
ユーザ端末２０は、本発明の実施の形態における鍵交換システム１に登録されているユーザが利用する端末である。各ユーザ端末２０は、鍵配信サーバ１０を介して、他のユーザ端末２０との間で公開鍵を交換することで、共通鍵を共有することができる。ユーザ端末２０としては、例えば、スマートフォンやタブレット端末、ＰＣ（パーソナルコンピュータ）、ウェアラブルデバイス、ゲーム機器、家電製品、組み込み機器等の種々の情報処理装置を用いることができる。
【００１８】
本発明の実施の形態では、鍵交換システム１に登録されているユーザのうち、鍵交換を行うユーザの数をＮとし、これらのユーザが利用するユーザ端末２０をそれぞれ「ユーザ端末２０１」、「ユーザ端末２０２」、・・・、「ユーザ端末２０Ｎ」と表す。したがって、本発明の実施の形態では、各ユーザ端末２０ｉ（１≦ｉ≦Ｎ）をそれぞれ表す記号として、添え字ｉ（１≦ｉ≦Ｎ）を用いる。また、本発明の実施の形態では、鍵配信サーバ１０を表す記号として、Ｓを用いる。
【００１９】
＜定義＞
ここで、本発明の実施の形態で用いる記号等を定義する。
【００２０】
整数をｎとして、整数環Ｚに対するｎを法とする剰余環（又は剰余類環）をＺ／ｎＺとする。
【００２１】
また、１以上の整数ｆを、
【００２２】
【数１】
2019198516.tif 000003
又は
【００２３】
【数２】
2019198516.tif 000004
が素数となるように選択する。ここで、ｌＡ及びｌＢは小さい素数（例えば、２及び３）であり、ｅＡ及びｅＢは整数である。
【００２４】
【数３】
2019198516.tif 000005
又は
【００２５】
【数４】
2019198516.tif 000006
が素数である場合、これらのうち素数である方（両方が素数である場合は任意に選んだ何れか一方）をｐと表す。
【００２６】
また、
【００２７】
【数５】
2019198516.tif 000007
を標数ｐの素体Ｆｐの２次拡大体とする。Ｅを
【００２８】
【数６】
2019198516.tif 000008
上の楕円曲線とする。例えば、
【００２９】
【数７】
2019198516.tif 000009
とすると、Ｅは
【００３０】
【数８】
2019198516.tif 000010
上の楕円曲線である。ここで、Ｏは無限遠点である。以降、本発明の実施の形態では、楕円曲線Ｅは超特異楕円曲線であるものとする。
【００３１】
楕円曲線Ｅのｊ不変量を、
【００３２】
【数９】
2019198516.tif 000011
とする。楕円曲線Ｅの任意の点Ｐと任意の整数ｍとに対して、Ｐのｍ個の和を［ｍ］Ｐと表す。ただし、和は、楕円曲線上の加算である。
【００３３】
整数ｍに対して、楕円曲線Ｅのｍねじれ部分群Ｅ［ｍ］を、Ｅ［ｍ］＝｛Ｐ∈Ｅ｜［ｍ］Ｐ＝Ｏ｝と定義する。ｍねじれ部分群Ｅ［ｍ］は、ｐで割り切れない整数ｍに対して、
【００３４】
【数１０】
2019198516.tif 000012
であることが知られている。ここで、
【００３５】
【数１１】
2019198516.tif 000013
は２つの群Ａ及びＢの間に同型写像が存在することを意味する。
【００３６】
本発明の実施の形態では、ｋをセキュリティパラメータ、シードｓ∈｛０，１｝ｋをインデックスとし、定義域Ｄｏｍｋと値域Ｒｎｇｋとを持つ関数族｛Ｆｓ：Ｄｏｍｋ→Ｒｎｇｋ｝ｓのうち、疑似ランダム関数と呼ばれる関数を使用する。また、本発明の実施の形態では、この疑似ランダム関数によるねじれ疑似ランダム関数ｔＰＲＦを使用する。なお、ねじれ疑似ランダム関数ｔＰＲＦは、入力の一部が知られたとしても、その関数の出力がランダム値と区別が困難であるという性質を有する関数である。
【００３７】
なお、ねじれ疑似ランダム関数については、例えば、以下の参考文献２に開示されている。
【００３８】
［参考文献２］
K. Yoneyama, R. Yoshida, Y. Kawahara, T. Kobayashi, H. Fuji, and T. Yamamoto. 2016. Multi-Cast Key Distribution: Scalable, Dynamic and Provably Secure Construction. Cryptology ePrint Archive, Report 2016/833. (2016).
＜機能構成＞
図２に示すように、本発明の実施の形態における鍵配信サーバ１０は、機能部として、セットアップ部１０１と、長期秘密ストリング生成部１０２と、短期秘密ストリング生成部１０３と、公開情報計算部１０４と、通信部１０５と、長期秘密ストリング記憶部１０６と、短期秘密ストリング記憶部１０７とを有する。これらの各機能部によって、鍵配信サーバ１０は、後述する事前処理（図４）及び鍵交換処理（図５）を実現することができる。
【００３９】
また、図３に示すように、本発明の実施の形態におけるユーザ端末２０は、機能部として、長期秘密ストリング生成部２０１と、短期秘密ストリング生成部２０２と、ねじれ疑似ランダム関数部２０３と、同種写像計算部２０４と、第１疑似ランダム関数部２０５と、秘密情報計算部２０６と、第２疑似ランダム関数部２０７と、通信部２０８と、長期秘密ストリング記憶部２０９と、短期秘密ストリング記憶部２１０と、セッション情報記憶部２１１とを有する。これら各機能部によって、各ユーザ端末２０は、後述する事前処理（図４）及び鍵交換処理（図５）を実現することができる。
【００４０】
＜事前処理＞
次に、本発明の実施の形態における鍵交換システム１の事前処理の流れについて、図４を参照しながら説明する。図４は、本発明の実施の形態における鍵交換システム１の事前処理の流れの一例を説明するための図である。なお、セキュリティパラメータｋは予め決められているものとする。例えば、ｋ＝２５６等に決められているものとする。
【００４１】
ステップＳ１０１：鍵配信サーバ１０のセットアップステップ
鍵配信サーバ１０のセットアップ部１０１は、ｋビットの数
【００４２】
【数１２】
2019198516.tif 000014
が素数となるように整数ｆを選択する。ここで、ｌＡ及びｌＢは素数、ｅＡ及びｅＢは整数である。
【００４３】
また、鍵配信サーバ１０のセットアップ部１０１は、
【００４４】
【数１３】
2019198516.tif 000015
上の超特異楕円曲線Ｅを生成し、
【００４５】
【数１４】
2019198516.tif 000016
と
【００４６】
【数１５】
2019198516.tif 000017
とを選択する。基底の選択方法は、例えば、以下の参考文献３に開示されている方法を用いることができる。
【００４７】
［参考文献３］
L. De Feo, D. Jao, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, In PQCrypto, pp.19-34, 2011.
更に、鍵配信サーバ１０のセットアップ部１０１は、Ｋｓｐａｃｅｋを鍵空間とし、以下のねじれ疑似ランダム関数ｔＰＲＦＡ，ｔＰＲＦＢ及びｔＰＲＦを生成する。
【００４８】
【数１６】
2019198516.tif 000018
また、鍵配信サーバ１０のセットアップ部１０１は、以下の疑似ランダム関数Ｆ及びＦ´を生成する。
【００４９】
【数１７】
2019198516.tif 000019
そして、鍵配信サーバ１０のセットアップ部１０１は、（ｐ，ｌＡ，ｅＡ，ｌＢ，ｅＢ，Ｅ，ＰＡ，ＱＡ，ＰＢ，ＱＢ，ｔＰＲＦＡ，ｔＰＲＦＢ，ｔＰＲＦ，Ｆ，Ｆ´）を公開する。これにより、各ユーザ端末２０は、これらの公開された情報を利用することができる。
【００５０】
ステップＳ１０２：鍵配信サーバ１０の長期秘密ストリング生成ステップ
鍵配信サーバ１０の長期秘密ストリング生成部１０２は、長期秘密ストリングとして、ｓｔＳ∈Ｋｓｐａｃｅｋと、ｓｔ´Ｓ∈｛０，１｝ｋとを一様ランダムに生成する。そして、鍵配信サーバ１０の長期秘密ストリング生成部１０２は、生成した長期秘密ストリング（ｓｔＳ，ｓｔ´Ｓ）を長期秘密ストリング記憶部１０６に保存する。
【００５１】
ステップＳ１０３：各ユーザ端末２０の長期秘密ストリング生成ステップ
各ユーザ端末２０の長期秘密ストリング生成部２０１は、長期秘密ストリングとして、ｓｔｉ∈Ｋｓｐａｃｅｋと、ｓｔ´ｉ∈｛０，１｝ｋとを一様ランダムに生成する。なお、ｓｔｉ及びｓｔ´ｉは、ユーザ端末２０ｉの長期秘密ストリング生成部２０１により生成された長期秘密ストリングである。
【００５２】
そして、各ユーザ端末２０の長期秘密ストリング生成部２０１は、生成した長期秘密ストリング（ｓｔｉ，ｓｔ´ｉ）を、自身の長期秘密ストリング記憶部２０９に保存する。
【００５３】
＜鍵交換処理＞
次に、本発明の実施の形態における鍵交換システム１の鍵交換処理の流れについて、図５を参照しながら説明する。図５は、本発明の実施の形態における鍵交換システム１の鍵交換処理の流れの一例を説明するための図である。
【００５４】
以降で説明する鍵交換処理は、鍵交換システム１の動作中に任意の回数実行が可能である。１回あたりの鍵交換の実行を「セッション」と呼ぶ。以降では、或るセッションにおける鍵配信サーバ１０及び各ユーザ端末２０の動作を説明する。なお、当該セッションを識別するセッション識別子をｓｉｄ∈｛０，１｝ｋとする。セッション識別子ｓｉｄの生成方法としては、任意の方法を用いることができる。例えば、非特許文献１に開示されているように、コミットメントを用いて生成する方法が挙げられる。鍵配信サーバ１０及び各ユーザ端末２０は、このｓｉｄを知っているものとする。
【００５５】
また、各ユーザ端末２０の中で代表となるユーザ端末２０（代表ユーザ端末）を決めておく。ユーザ端末２０１，ユーザ端末２０２，・・・，ユーザ端末２０Ｎのうち、任意のユーザ端末２０を代表ユーザ端末として良い。以降では、ユーザ端末２０１が代表ユーザ端末であるものとする。代表ユーザ端末の選択及び代表ユーザ端末であることを示す通知は、例えば、鍵配信サーバ１０により行われても良い。
【００５６】
また、ユーザ端末２０の添え字ｉはリング状であるものとする。すなわち、ｉ＝Ｎに対して１が加算された場合ｉ＝１となり、ｉ＝１から−１が減算された場合ｉ＝Ｎとなるものとする。
【００５７】
ここで、同種写像暗号では、ＤＨ鍵交換と異なり、或る２つのユーザ端末２０において、基底｛ＰＡ，ＱＡ｝から秘密鍵を生成するか又は基底｛ＰＢ，ＱＢ｝から秘密鍵を生成するかのいずれかによって計算の非対称性が生じる。
【００５８】
このため、実施例１では、ユーザ端末２０の数Ｎの偶奇によって代表ユーザ端末の処理が異なる場合について説明する。すなわち、実施例１では、Ｎが偶数である場合は、ユーザ端末２０１，ユーザ端末２０３，・・・，ユーザ端末２０Ｎ−１は基底｛ＰＡ，ＱＡ｝からそれぞれ公開値を計算し、ユーザ端末２０２，ユーザ端末２０４，・・・，ユーザ端末２０Ｎは基底｛ＰＢ，ＱＢ｝からそれぞれ公開値を計算する。一方で、Ｎが奇数である場合は、代表ユーザ端末であるユーザ端末２０１は基底｛ＰＡ，ＱＡ｝及び基底｛ＰＢ，ＱＢ｝の両方からそれぞれ公開値を計算し、ユーザ端末２０３，ユーザ端末２０５，・・・，ユーザ端末２０Ｎ−１は基底｛ＰＡ，ＱＡ｝からそれぞれ公開値を計算し、ユーザ端末２０２，ユーザ端末２０４，・・・，ユーザ端末２０Ｎは基底｛ＰＢ，ＱＢ｝からそれぞれ公開値を計算する。なお、公開値には、後述するφｉ（ＰＡ），φｉ（ＱＡ），φｉ（ＰＢ），φｉ（ＱＢ）が含まれる。
【００５９】
また、実施例２では、ユーザ端末２０の数Ｎの偶奇によらずに、全てのユーザ端末２０が基底｛ＰＡ，ＱＡ｝及び基底｛ＰＢ，ＱＢ｝の両方からそれぞれ共通鍵を生成する場合について説明する。
【００６０】
（実施例１）
以降では、実施例１について説明する。
【００６１】
≪Ｎが偶数である場合≫
まず、Ｎが偶数である場合について説明する。
【００６２】
ステップＳ２０１：第一鍵生成ステップ（Ｒｏｕｎｄ１）
以降のＳ２０１−１１〜Ｓ２０１−１５は、ｉが奇数である各ユーザ端末２０ｉ（ｉ＝１，３，・・・，Ｎ−１）が実行する。
【００６３】
Ｓ２０１−１１）短期秘密ストリング生成部２０２は、短期秘密ストリングとして、ｒｉ（１）∈｛０，１｝ｋと、ｒｉ（２）∈Ｋｓｐａｃｅｋと、ｒｉ（３）∈｛０，１｝ｋと、ｒｉ（４）∈Ｋｓｐａｃｅｋと、ｋｉ（１）∈｛０，１｝ｋと、ｋｉ（２）∈Ｋｓｐａｃｅｋとを一様ランダムに生成する。
【００６４】
そして、短期秘密ストリング生成部２０２は、短期秘密ストリング（ｒｉ（１），ｒｉ（２），ｒｉ（３），ｒｉ（４），ｋｉ（１），ｋｉ（２））を短期秘密ストリング記憶部２１０に保存する。
【００６５】
Ｓ２０１−１２）ねじれ疑似ランダム関数部２０３は、ｍｉ＝ｔＰＲＦＡ（ｒｉ（１），ｒｉ（２），ｓｔｉ，ｓｔ´ｉ）と、ｎｉ＝ｔＰＲＦＡ（ｒｉ（３），ｒｉ（４），ｓｔｉ，ｓｔ´ｉ）と、ｋｉ＝ｔＰＲＦ（ｋｉ（１），ｋｉ（２），ｓｔｉ，ｓｔ´ｉ）とを生成する。なお、長期秘密ストリング（ｓｔｉ，ｓｔ´ｉ）は、長期秘密ストリング記憶部２０９は記憶されているものを使用する。
【００６６】
Ｓ２０１−１３）同種写像計算部２０４は、［ｍｉ］ＰＡ＋［ｎｉ］ＱＡで生成されるＥの部分群Ｋｉを核に持つ同種写像φｉ：Ｅ→Ｅｉと、この同種写像φｉに付随する楕円曲線Ｅｉとを計算する。
【００６７】
なお、部分群Ｋｉを核に持つ同種写像φｉとは、Ｋｅｒφｉ＝Ｋｉとなる同種写像のことである。このような同種写像φｉと部分群Ｋｉとは１対１に対応することが知られている。また、同種写像φｉに付随する楕円曲線Ｅｉは、Ｅｉ＝Ｅ／Ｋｉとも表される。同種写像φｉの計算方法は、例えば、以下の参考文献４又は５に開示されている方法を用いることができる。
【００６８】
［参考文献４］
J. Velu, Isogenies entre courbes elliptiques, C. R. Acad. Sci. Paris Ser. A-B, 273:A238-241, 1971.
［参考文献５］
Lawrence C.Washington. Elliptic curves: Number theory and cryptography, 2nd ed., CRC Press, 2008.
Ｓ２０１−１４）同種写像計算部２０４は、φｉ（ＰＢ）とφｉ（ＱＢ）とを計算する。
【００６９】
Ｓ２０１−１５）そして、通信部２０８は、（φｉ（ＰＢ），φｉ（ＱＢ），Ｅｉ）を鍵配信サーバ１０に送信する。これより、各ユーザ端末２０ｉ（ｉ＝１，３，・・・，Ｎ−１）の公開値（φｉ（ＰＢ），φｉ（ＱＢ），Ｅｉ）が鍵配信サーバ１０に送信される。
【００７０】
以降のＳ２０１−２１〜Ｓ２０１−２５は、ｉが偶数である各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ）が実行する。
【００７１】
Ｓ２０１−２１）短期秘密ストリング生成部２０２は、短期秘密ストリングとして、ｒｉ（１）∈｛０，１｝ｋと、ｒｉ（２）∈Ｋｓｐａｃｅｋと、ｒｉ（３）∈｛０，１｝ｋと、ｒｉ（４）∈Ｋｓｐａｃｅｋと、ｋｉ（１）∈｛０，１｝ｋと、ｋｉ（２）∈Ｋｓｐａｃｅｋとを一様ランダムに生成する。
【００７２】
そして、短期秘密ストリング生成部２０２は、短期秘密ストリング（ｒｉ（１），ｒｉ（２），ｒｉ（３），ｒｉ（４），ｋｉ（１），ｋｉ（２））を短期秘密ストリング記憶部２１０に保存する。
【００７３】
Ｓ２０１−２２）ねじれ疑似ランダム関数部２０３は、ｍｉ＝ｔＰＲＦＢ（ｒｉ（１），ｒｉ（２），ｓｔｉ，ｓｔ´ｉ）と、ｎｉ＝ｔＰＲＦＢ（ｒｉ（３），ｒｉ（４），ｓｔｉ，ｓｔ´ｉ）と、ｋｉ＝ｔＰＲＦ（ｋｉ（１），ｋｉ（２），ｓｔｉ，ｓｔ´ｉ）とを生成する。なお、長期秘密ストリング（ｓｔｉ，ｓｔ´ｉ）は、長期秘密ストリング記憶部２０９は記憶されているものを使用する。
【００７４】
Ｓ２０１−２３）同種写像計算部２０４は、［ｍｉ］ＰＢ＋［ｎｉ］ＱＢで生成されるＥの部分群Ｋｉを核に持つ同種写像φｉ：Ｅ→Ｅｉと、この同種写像φｉに付随する楕円曲線Ｅｉとを計算する。
【００７５】
Ｓ２０１−２４）同種写像計算部２０４は、φｉ（ＰＡ）とφｉ（ＱＡ）とを計算する。
【００７６】
Ｓ２０１−２５）そして、通信部２０８は、（φｉ（ＰＡ），φｉ（ＱＡ），Ｅｉ）を鍵配信サーバ１０に送信する。これより、各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ）の公開値（φｉ（ＰＡ），φｉ（ＱＡ），Ｅｉ）が鍵配信サーバ１０に送信される。
【００７７】
なお、上記のＳ２０１−１２及びＳ２０１−２２におけるｍｉ及びｎｉは、長期秘密ストリング記憶部２０９に記憶されている長期秘密ストリングと、短期秘密ストリング記憶部２１０に記憶されている短期秘密ストリングとを用いて、必要なときにねじれ疑似ランダム関数から生成することができる。このため、安全上、ｍｉ及びｎｉは保存しないことが好ましい。
【００７８】
ただし、安全性をあまり考慮しないのであれば、上記のＳ２０１−１２でｍｉ及びｎｉを
【００７９】
【数１８】
2019198516.tif 000020
からランダムに生成して、保存しておいても良い。同様に、上記のＳ２０１−２２でｍｉ及びｎｉを
【００８０】
【数１９】
2019198516.tif 000021
からランダムに生成して、保存しておいても良い。
【００８１】
ステップＳ２０２：鍵配信ステップ（Ｒｏｕｎｄ１）
Ｓ２０２−１）通信部１０５は、ｉが奇数である各ユーザ端末２０ｉ（ｉ＝１，３，・・・，Ｎ−１）から公開値（φｉ（ＰＢ），φｉ（ＱＢ），Ｅｉ）を受信すると共に、ｉが偶数である各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ）から公開値（φｉ（ＰＡ），φｉ（ＱＡ），Ｅｉ）を受信する。
【００８２】
Ｓ２０２−２）通信部１０５は、ｉが奇数である各ユーザ端末２０ｉ（ｉ＝１，３，・・・，Ｎ−１）に対して、（ｓｉｄ，φｉ−１（ＰＡ），φｉ−１（ＱＡ），Ｅｉ−１，φｉ＋１（ＰＡ），φｉ＋１（ＱＡ），Ｅｉ＋１）を送信する。
【００８３】
また、通信部１０５は、ｉが偶数である各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ）に対して、（ｓｉｄ，φｉ−１（ＰＢ），φｉ−１（ＱＢ），Ｅｉ−１，φｉ＋１（ＰＢ），φｉ＋１（ＱＢ），Ｅｉ＋１）を送信する。
【００８４】
なお、上述したように、ユーザ端末２０の添え字ｉはリング状である。したがって、例えば、ｉ＝１であるユーザ端末２０１に対しては、（ｓｉｄ，φＮ（ＰＡ），φＮ（ＱＡ），ＥＮ，φ２（ＰＡ），φ２（ＱＡ），Ｅ２）が送信される。また、例えば、ｉ＝Ｎであるユーザ端末２０Ｎに対しては、（ｓｉｄ，φＮ−１（ＰＢ），φＮ−１（ＱＢ），ＥＮ−１，φ１（ＰＢ），φ１（ＱＢ），Ｅ１）が送信される。
【００８５】
ステップＳ２０３：第二鍵生成ステップ（Ｒｏｕｎｄ２）
以降のＳ２０３−１１〜Ｓ２０３−１６は、ｉが１以外の奇数である各ユーザ端末２０ｉ（ｉ＝３，５，・・・，Ｎ−１）が実行する。
【００８６】
Ｓ２０３−１１）通信部２０８は、鍵配信サーバ１０から（ｓｉｄ，φｉ−１（ＰＡ），φｉ−１（ＱＡ），Ｅｉ−１，φｉ＋１（ＰＡ），φｉ＋１（ＱＡ），Ｅｉ＋１）を受信する。
【００８７】
Ｓ２０３−１２）同種写像計算部２０４は、［ｍｉ］φｉ−１（ＰＡ）＋［ｎｉ］φｉ−１（ＱＡ）で生成されるＥｉ−１の部分群Ｋｉ−１，ｉを核に持つ同種写像φｉ−１，ｉ：Ｅｉ−１→Ｅｉ−１，ｉと、この同種写像φｉ−１，ｉに付随する楕円曲線Ｅｉ−１，ｉとを計算する。
【００８８】
同様に、同種写像計算部２０４は、［ｍｉ］φｉ＋１（ＰＡ）＋［ｎｉ］φｉ＋１（ＱＡ）で生成されるＥｉ＋１の部分群Ｋｉ＋１，ｉを核に持つ同種写像φｉ＋１，ｉ：Ｅｉ＋１→Ｅｉ＋１，ｉと、この同種写像φｉ＋１，ｉに付随する楕円曲線Ｅｉ＋１，ｉとを計算する。
【００８９】
Ｓ２０３−１３）同種写像計算部２０４は、楕円曲線Ｅｉ−１，ｉのｊ不変量ｊ（Ｅｉ−１，ｉ）と、楕円曲線Ｅｉ＋１，ｉのｊ不変量ｊ（Ｅｉ＋１，ｉ）とを計算する。
【００９０】
Ｓ２０３−１４）次に、第１疑似ランダム関数部２０５は、Ｋｉ（ｌ）＝Ｆ（ｓｉｄ，ｊ（Ｅｉ−１，ｉ））と、Ｋｉ（ｒ）＝Ｆ（ｓｉｄ，ｊ（Ｅｉ＋１，ｉ））とを計算する。
【００９１】
Ｓ２０３−１５）次に、第１疑似ランダム関数部２０５は、Ｋｉ（ｌ）とＫｉ（ｒ）とのビット毎の排他的論理和Ｔｉを計算する。すなわち、第１疑似ランダム関数部２０５は、
【００９２】
【数２０】
2019198516.tif 000022
を計算する。
【００９３】
Ｓ２０３−１６）そして、通信部２０８は、（ｋｉ，Ｔｉ）を鍵配信サーバ１０に送信する。なお、ｋｉは、第一鍵生成ステップ（Ｓ２０１）で生成されたものである。
【００９４】
以降のＳ２０３−２１〜Ｓ２０３−２６は、ｉが偶数である各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ）が実行する。
【００９５】
Ｓ２０３−２１）通信部２０８は、鍵配信サーバ１０から（ｓｉｄ，φｉ−１（ＰＢ），φｉ−１（ＱＢ），Ｅｉ−１，φｉ＋１（ＰＢ），φｉ＋１（ＱＢ），Ｅｉ＋１）を受信する。
【００９６】
Ｓ２０３−２２）同種写像計算部２０４は、［ｍｉ］φｉ−１（ＰＢ）＋［ｎｉ］φｉ−１（ＱＢ）で生成されるＥｉ−１の部分群Ｋｉ−１，ｉを核に持つ同種写像φｉ−１，ｉ：Ｅｉ−１→Ｅｉ−１，ｉと、この同種写像φｉ−１，ｉに付随する楕円曲線Ｅｉ−１，ｉとを計算する。
【００９７】
同様に、同種写像計算部２０４は、［ｍｉ］φｉ＋１（ＰＢ）＋［ｎｉ］φｉ＋１（ＱＢ）で生成されるＥｉ＋１の部分群Ｋｉ＋１，ｉを核に持つ同種写像φｉ＋１，ｉ：Ｅｉ＋１→Ｅｉ＋１，ｉと、この同種写像φｉ＋１，ｉに付随する楕円曲線Ｅｉ＋１，ｉとを計算する。
【００９８】
Ｓ２０３−２３）同種写像計算部２０４は、楕円曲線Ｅｉ−１，ｉのｊ不変量ｊ（Ｅｉ−１，ｉ）と、楕円曲線Ｅｉ＋１，ｉのｊ不変量ｊ（Ｅｉ＋１，ｉ）とを計算する。
【００９９】
Ｓ２０３−２４）次に、第１疑似ランダム関数部２０５は、Ｋｉ（ｌ）＝Ｆ（ｓｉｄ，ｊ（Ｅｉ−１，ｉ））と、Ｋｉ（ｒ）＝Ｆ（ｓｉｄ，ｊ（Ｅｉ＋１，ｉ））とを計算する。
【０１００】
Ｓ２０３−２５）次に、第１疑似ランダム関数部２０５は、Ｋｉ（ｌ）とＫｉ（ｒ）とのビット毎の排他的論理和Ｔｉを計算する。
【０１０１】
Ｓ２０３−２６）そして、通信部２０８は、（ｋｉ，Ｔｉ）を鍵配信サーバ１０に送信する。なお、ｋｉは、第一鍵生成ステップ（Ｓ２０１）で生成されたものである。
【０１０２】
以降のＳ２０３−３１〜Ｓ２０３−３７は、代表ユーザ端末であるユーザ端末２０１が実行する。
【０１０３】
Ｓ２０３−３１）通信部２０８は、鍵配信サーバ１０から（ｓｉｄ，φＮ（ＰＡ），φＮ（ＱＡ），ＥＮ，φ２（ＰＡ），φ２（ＱＡ），Ｅ２）を受信する。
【０１０４】
Ｓ２０３−３２）同種写像計算部２０４は、［ｍ１］φＮ（ＰＡ）＋［ｎ１］φＮ（ＱＡ）で生成されるＥＮの部分群ＫＮ，１を核に持つ同種写像φＮ，１：ＥＮ→ＥＮ，１と、この同種写像φＮ，１に付随する楕円曲線ＥＮ，１とを計算する。
【０１０５】
同様に、同種写像計算部２０４は、［ｍ１］φ２（ＰＡ）＋［ｎ１］φ２（ＱＡ）で生成されるＥ２の部分群Ｋ２，１を核に持つ同種写像φ２，１：Ｅ２→Ｅ２，１と、この同種写像φ２，１に付随する楕円曲線Ｅ２，１とを計算する。
【０１０６】
Ｓ２０３−３３）同種写像計算部２０４は、楕円曲線ＥＮ，１のｊ不変量ｊ（ＥＮ，１）と、楕円曲線Ｅ２，１のｊ不変量ｊ（Ｅ２，１）とを計算する。
【０１０７】
Ｓ２０３−３４）次に、第１疑似ランダム関数部２０５は、Ｋ１（ｌ）＝Ｆ（ｓｉｄ，ｊ（ＥＮ，１））と、Ｋ１（ｒ）＝Ｆ（ｓｉｄ，ｊ（Ｅ２，１））とを計算する。
【０１０８】
Ｓ２０３−３５）次に、第１疑似ランダム関数部２０５は、Ｋ１（ｌ）とＫ１（ｒ）とのビット毎の排他的論理和Ｔ１を計算する。
【０１０９】
Ｓ２０３−３６）次に、第１疑似ランダム関数部２０５は、Ｋ１（ｌ）とｋ１との排他的論理和Ｔ´を計算する。すなわち、第１疑似ランダム関数部２０５は、
【０１１０】
【数２１】
2019198516.tif 000023
を計算する。なお、ｋ１は、第一鍵生成ステップ（Ｓ２０１）で生成されたものである。
【０１１１】
Ｓ２０３−３７）そして、通信部２０８は、（Ｔ´，Ｔ１）を鍵配信サーバ１０に送信する。
【０１１２】
ステップＳ２０４：第三鍵生成ステップ（Ｒｏｕｎｄ２）
Ｓ２０４−１）通信部１０５は、ｉ＝１であるユーザ端末２０１から（Ｔ´，Ｔ１）を受信すると共に、ｉが１以外の各ユーザ端末２０ｉ（ｉ＝２，３，・・・，Ｎ）から（ｋｉ，Ｔｉ）を受信する。
【０１１３】
Ｓ２０４−２）短期秘密ストリング生成部１０３は、短期秘密ストリングとして、ｋＳ（１）∈｛０，１｝ｋと、ｋＳ（２）∈Ｋｓｐａｃｅｋとを一様ランダムに生成する。そして、短期秘密ストリング生成部１０３は、短期秘密ストリング（ｋＳ（１），ｋＳ（２））を短期秘密ストリング記憶部１０７に保存する。
【０１１４】
Ｓ２０４−３）次に、短期秘密ストリング生成部１０３は、短期秘密ストリング生成部１０３は、ｋＳ＝ｔＰＲＦ（ｋＳ（１），ｋＳ（２），ｓｔＳ，ｓｔ´Ｓ）と、
【０１１５】
【数２２】
2019198516.tif 000024
とを計算する。なお、ｓｔＳ及びｓｔ´Ｓは、長期秘密ストリング記憶部１０６に保存されているものを使用する。
【０１１６】
Ｓ２０４−４）次に、公開情報計算部１０４は、各ｉ∈｛２，・・・，Ｎ｝に対して、各Ｔｊ（１≦ｊ≦ｉ−１）同士の排他的論理和Ｔ´ｉを計算する。すなわち、公開情報計算部１０４は、
【０１１７】
【数２３】
2019198516.tif 000025
を計算する。
【０１１８】
Ｓ２０４−５）そして、通信部１０５は、各ユーザ端末２０ｉ（ｉ＝２，・・・，Ｎ）に対して、（ｋ´，Ｔ´ｉ，Ｔ´）を送信する。また、通信部１０５は、ユーザ端末２０１に対して、ｋ´を送信する。
【０１１９】
ステップＳ２０５：セッション鍵生成ステップ
以降のＳ２０５−１１〜Ｓ２０５−１４は、ｉが１以外であるユーザ端末２０ｉ（すなわち、代表ユーザ端末以外のユーザ端末２０）が実行する。
【０１２０】
Ｓ２０５−１１）通信部２０８は、鍵配信サーバ１０から（ｋ´，Ｔ´ｉ，Ｔ´）を受信する。
【０１２１】
Ｓ２０５−１２）秘密情報計算部２０６は、Ｔ´ｉとＴ´との排他的論理和を計算する。この排他的論理和はＫ１（ｌ）と一致する。すなわち、
【０１２２】
【数２４】
2019198516.tif 000026
である。
【０１２３】
Ｓ２０５−１３）次に、秘密情報計算部２０６は、Ｔ´とＫ１（ｌ）との排他的論理和を計算する。この排他的論理和はｋ１と一致する。すなわち、
【０１２４】
【数２５】
2019198516.tif 000027
である。
【０１２５】
Ｓ２０５−１４）次に、第２疑似ランダム関数部２０７は、
【０１２６】
【数２６】
2019198516.tif 000028
を計算する。このＫがセッション鍵となる。
【０１２７】
そして、第２疑似ランダム関数部２０７は、セッション鍵Ｋをセッション情報記憶部２１１に保存する。
【０１２８】
以降のＳ２０５−２１〜Ｓ２０５−２２は、ｉが１であるユーザ端末２０１（すなわち、代表ユーザ端末）が実行する。
【０１２９】
Ｓ２０５−２１）通信部２０８は、鍵配信サーバ１０からｋ´を受信する。
【０１３０】
Ｓ２０５−２２）次に、第２疑似ランダム関数部２０７は、
【０１３１】
【数２７】
2019198516.tif 000029
を計算する。このＫがセッション鍵となる。
【０１３２】
そして、第２疑似ランダム関数部２０７は、セッション鍵Ｋをセッション情報記憶部２１１に保存する。
【０１３３】
これにより、各ユーザ端末２０ｉ（ｉ＝１，２，・・・，Ｎ）間で同一のセッション鍵Ｋが共有される。このセッション鍵Ｋを用いて、各ユーザ端末２０間で送受信されるデータが暗号化される。
【０１３４】
≪Ｎが奇数である場合≫
次に、Ｎが奇数である場合について説明する。なお、Ｎが偶数である場合に説明した処理と同様の処理を行う箇所については、適宜、その説明を省略又は簡略化する。
【０１３５】
ステップＳ２０１：第一鍵生成ステップ（Ｒｏｕｎｄ１）
ｉが１以外の奇数である各ユーザ端末２０ｉ（ｉ＝３，５，・・・，Ｎ）は、上記のＳ２０１−１１〜Ｓ２０１−１５を実行する。また、ｉが偶数である各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ−１）は、上記のＳ２０１−２１〜Ｓ２０１−２５を実行する。
【０１３６】
以降のＳ２０１−３１〜Ｓ２０１−３５は、ｉが１であるユーザ端末２０１（すなわち、代表ユーザ端末）が実行する。
【０１３７】
Ｓ２０１−３１）短期秘密ストリング生成部２０２は、短期秘密ストリングとして、ｒ１（１）∈｛０，１｝ｋと、ｒ１（２）∈Ｋｓｐａｃｅｋと、ｒ１（３）∈｛０，１｝ｋと、ｒ１（４）∈Ｋｓｐａｃｅｋと、ｒ１（５）∈｛０，１｝ｋと、ｒ１（６）∈Ｋｓｐａｃｅｋと、ｒ１（７）∈｛０，１｝ｋと、ｒ１（８）∈Ｋｓｐａｃｅｋと、ｋ１（１）∈｛０，１｝ｋと、ｋ１（２）∈Ｋｓｐａｃｅｋとを一様ランダムに生成する。
【０１３８】
そして、短期秘密ストリング生成部２０２は、短期秘密ストリング（ｒ１（１），ｒ１（２），ｒ１（３），ｒ１（４），ｒ１（５），ｒ１（６），ｒ１（７），ｒ１（８），ｋ１（１），ｋ２（２））を短期秘密ストリング記憶部２１０に保存する。
【０１３９】
Ｓ２０１−３２）ねじれ疑似ランダム関数部２０３は、ｍ１＝ｔＰＲＦＡ（ｒ１（１），ｒ１（２），ｓｔ１，ｓｔ´１）と、ｎ１＝ｔＰＲＦＡ（ｒ１（３），ｒ１（４），ｓｔ１，ｓｔ´１）と、ｍＮ＋１＝ｔＰＲＦＢ（ｒ１（５），ｒ１（６），ｓｔ１，ｓｔ´１）と、ｎＮ＋１＝ｔＰＲＦＢ（ｒ１（７），ｒ１（８），ｓｔ１，ｓｔ´１）と、ｋ１＝ｔＰＲＦ（ｋ１（１），ｋ１（２），ｓｔ１，ｓｔ´１）とを生成する。なお、長期秘密ストリング（ｓｔ１，ｓｔ´１）は、長期秘密ストリング記憶部２０９は記憶されているものを使用する。
【０１４０】
Ｓ２０１−３３）同種写像計算部２０４は、［ｍ１］ＰＡ＋［ｎ１］ＱＡで生成されるＥの部分群Ｋ１を核に持つ同種写像φ１：Ｅ→Ｅ１と、この同種写像φ１に付随する楕円曲線Ｅ１とを計算する。
【０１４１】
また、同種写像計算部２０４は、［ｍＮ＋１］ＰＢ＋［ｎＮ＋１］ＱＢで生成されるＥの部分群ＫＮ＋１を核に持つ同種写像φＮ＋１：Ｅ→ＥＮ＋１と、この同種写像φＮ＋１に付随する楕円曲線ＥＮ＋１とを計算する。
【０１４２】
Ｓ２０１−３４）同種写像計算部２０４は、φ１（ＰＢ）と、φ１（ＱＢ）と、φＮ＋１（ＰＡ）と、φＮ＋１（ＱＡ）とを計算する。
【０１４３】
Ｓ２０１−３５）そして、通信部２０８は、（φ１（ＰＢ），φ１（ＱＢ），Ｅ１，φＮ＋１（ＰＡ），φＮ＋１（ＱＢ），ＥＮ＋１）を鍵配信サーバ１０に送信する。これより、代表ユーザ端末であるユーザ端末２０１の公開値（φ１（ＰＢ），φ１（ＱＢ），Ｅ１，φＮ＋１（ＰＡ），φＮ＋１（ＱＢ），ＥＮ＋１）が鍵配信サーバ１０に送信される。
【０１４４】
なお、上記のＳ２０１−３２におけるｍ１，ｎ１，ｍＮ＋１及びｎＮ＋１は、長期秘密ストリング記憶部２０９に記憶されている長期秘密ストリングと、短期秘密ストリング記憶部２１０に記憶されている短期秘密ストリングとを用いて、必要なときにねじれ疑似ランダム関数から生成することができる。このため、安全上、ｍ１，ｎ１，ｍＮ＋１及びｎＮ＋１は保存しないことが好ましい。
【０１４５】
ただし、安全性をあまり考慮しないのであれば、上記のＳ２０１−３２でｍ１及びｎ１を
【０１４６】
【数２８】
2019198516.tif 000030
からランダムに生成すると共に、ｍＮ＋１及びｎＮ＋１を
【０１４７】
【数２９】
2019198516.tif 000031
からランダムに生成し、保存しておいても良い。
【０１４８】
ステップＳ２０２：鍵配信ステップ（Ｒｏｕｎｄ１）
Ｓ２０２−３）通信部１０５は、ｉが１であるユーザ端末２０１から公開値（φ１（ＰＢ），φ１（ＱＢ），Ｅ１，φＮ＋１（ＰＡ），φＮ＋１（ＱＢ），ＥＮ＋１）を受信する。また、通信部１０５は、ｉが１以外の奇数である各ユーザ端末２０ｉ（ｉ＝３，５，・・・，Ｎ）から公開値（φｉ（ＰＢ），φｉ（ＱＢ），Ｅｉ）を受信すると共に、ｉが偶数である各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ−１）から公開値（φｉ（ＰＡ），φｉ（ＱＡ），Ｅｉ）を受信する。
【０１４９】
Ｓ２０２−４）通信部１０５は、ｉが奇数である各ユーザ端末２０ｉ（ｉ＝１，３，・・・，Ｎ）に対して、（ｓｉｄ，φｉ−１（ＰＡ），φｉ−１（ＱＡ），Ｅｉ−１，φｉ＋１（ＰＡ），φｉ＋１（ＱＡ），Ｅｉ＋１）を送信する。
【０１５０】
また、通信部１０５は、ｉが偶数である各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ−１）に対して、（ｓｉｄ，φｉ−１（ＰＢ），φｉ−１（ＱＢ），Ｅｉ−１，φｉ＋１（ＰＢ），φｉ＋１（ＱＢ），Ｅｉ＋１）を送信する。
【０１５１】
ステップＳ２０３：第二鍵生成ステップ（Ｒｏｕｎｄ２）
ｉが１以外の奇数である各ユーザ端末２０ｉ（ｉ＝３，５，・・・，Ｎ）は、上記のＳ２０３−１１〜Ｓ２０３−１６を実行する。また、ｉが偶数である各ユーザ端末２０ｉ（ｉ＝２，４，・・・，Ｎ−１）は、上記のＳ２０３−２１〜Ｓ２０３−２６を実行する。
【０１５２】
以降のＳ２０３−４１〜Ｓ２０３−４７は、ｉが１であるユーザ端末２０１（すなわち、代表ユーザ端末）が実行する。
【０１５３】
Ｓ２０３−４１）通信部２０８は、鍵配信サーバ１０から（ｓｉｄ，φＮ（ＰＡ），φＮ（ＱＡ），ＥＮ，φ２（ＰＡ），φ２（ＱＡ），Ｅ２）を受信する。
【０１５４】
Ｓ２０３−４２）同種写像計算部２０４は、［ｍＮ＋１］φＮ（ＰＢ）＋［ｎＮ＋１］φＮ（ＱＢ）で生成されるＥＮの部分群ＫＮ，Ｎ＋１を核に持つ同種写像φＮ，Ｎ＋１：ＥＮ→ＥＮ，Ｎ＋１と、この同種写像φＮ，Ｎ＋１に付随する楕円曲線ＥＮ，Ｎ＋１とを計算する。
【０１５５】
同様に、同種写像計算部２０４は、［ｍ１］φ２（ＰＡ）＋［ｎ１］φ２（ＱＡ）で生成されるＥ２の部分群Ｋ２，１を核に持つ同種写像φ２，１：Ｅ２→Ｅ２，１と、この同種写像φ２，１に付随する楕円曲線Ｅ２，１とを計算する。
【０１５６】
Ｓ２０３−４３）同種写像計算部２０４は、楕円曲線ＥＮ，Ｎ＋１のｊ不変量ｊ（ＥＮ，Ｎ＋１）と、楕円曲線Ｅ２，１のｊ不変量ｊ（Ｅ２，１）とを計算する。
【０１５７】
Ｓ２０３−４４）次に、第１疑似ランダム関数部２０５は、Ｋ１（ｌ）＝Ｆ（ｓｉｄ，ｊ（ＥＮ，Ｎ＋１））と、Ｋ１（ｒ）＝Ｆ（ｓｉｄ，ｊ（Ｅ２，１））とを計算する。
【０１５８】
Ｓ２０３−４５）次に、第１疑似ランダム関数部２０５は、Ｋ１（ｌ）とＫ１（ｒ）とのビット毎の排他的論理和Ｔ１を計算する。
【０１５９】
Ｓ２０３−４６）次に、第１疑似ランダム関数部２０５は、Ｋ１（ｌ）とｋ１との排他的論理和Ｔ´を計算する。
【０１６０】
Ｓ２０３−４７）そして、通信部２０８は、（Ｔ´，Ｔ１）を鍵配信サーバ１０に送信する。
【０１６１】
以降のステップＳ２０４〜ステップＳ２０５は、Ｎが偶数である場合と同様であるため、その説明を省略する。
【０１６２】
（実施例２）
以降では、実施例２について説明する。実施例２は、Ｎが偶数又は奇数のいずれであっても同様の処理を行うものである。すなわち、実施例２では、実施例１と異なり、Ｎの偶奇による場合分けが発生しない。
【０１６３】
ステップＳ２０１：第一鍵生成ステップ（Ｒｏｕｎｄ１）
以降のＳ２０１−４１〜Ｓ２０１−４５は、各ユーザ端末２０ｉ（ｉ＝１，２，・・・，Ｎ）が実行する。
【０１６４】
Ｓ２０１−４１）短期秘密ストリング生成部２０２は、短期秘密ストリングとして、ｒｉ（１）∈｛０，１｝ｋと、ｒｉ（２）∈Ｋｓｐａｃｅｋと、ｒｉ（３）∈｛０，１｝ｋと、ｒｉ（４）∈Ｋｓｐａｃｅｋと、ｒｉ（５）∈｛０，１｝ｋと、ｒｉ（６）∈Ｋｓｐａｃｅｋと、ｒｉ（７）∈｛０，１｝ｋと、ｒｉ（８）∈Ｋｓｐａｃｅｋと、ｋｉ（１）∈｛０，１｝ｋと、ｋｉ（２）∈Ｋｓｐａｃｅｋとを一様ランダムに生成する。
【０１６５】
そして、短期秘密ストリング生成部２０２は、短期秘密ストリング（ｒｉ（１），ｒｉ（２），ｒｉ（３），ｒｉ（４），ｒｉ（５），ｒｉ（６），ｒｉ（７），ｒｉ（８），ｋｉ（１），ｋｉ（２））を短期秘密ストリング記憶部２１０に保存する。
【０１６６】
Ｓ２０１−４２）ねじれ疑似ランダム関数部２０３は、ｍｉ（１）＝ｔＰＲＦＡ（ｒｉ（１），ｒｉ（２），ｓｔｉ，ｓｔ´ｉ）と、ｎｉ（１）＝ｔＰＲＦＡ（ｒｉ（３），ｒｉ（４），ｓｔｉ，ｓｔ´ｉ）と、ｍｉ（２）＝ｔＰＲＦＢ（ｒｉ（５），ｒｉ（６），ｓｔｉ，ｓｔ´ｉ）と、ｎｉ（２）＝ｔＰＲＦＢ（ｒｉ（７），ｒｉ（８），ｓｔｉ，ｓｔ´ｉ）と、ｋｉ＝ｔＰＲＦ（ｋｉ（１），ｋｉ（２），ｓｔｉ，ｓｔ´ｉ）とを生成する。なお、長期秘密ストリング（ｓｔｉ，ｓｔ´ｉ）は、長期秘密ストリング記憶部２０９は記憶されているものを使用する。
【０１６７】
Ｓ２０１−４３）同種写像計算部２０４は、［ｍｉ（１）］ＰＡ＋［ｎｉ（１）］ＱＡで生成されるＥの部分群Ｋｉ（１）を核に持つ同種写像φｉ（１）：Ｅ→Ｅｉ（１）と、この同種写像φｉ（１）に付随する楕円曲線Ｅｉ（１）とを計算する。
【０１６８】
また、同種写像計算部２０４は、［ｍｉ（２）］ＰＢ＋［ｎｉ（２）］ＱＢで生成されるＥの部分群Ｋｉ（２）を核に持つ同種写像φｉ（２）：Ｅ→Ｅｉ（２）と、この同種写像φｉ（２）に付随する楕円曲線Ｅｉ（２）とを計算する。
【０１６９】
Ｓ２０１−４４）同種写像計算部２０４は、φｉ（１）（ＰＢ）と、φｉ（１）（ＱＢ）と、φｉ（２）（ＰＡ）と、φｉ（２）（ＱＡ）とを計算する。
【０１７０】
Ｓ２０１−４５）そして、通信部２０８は、（φｉ（１）（ＰＢ），φｉ（１）（ＱＢ），Ｅｉ（１），φｉ（２）（ＰＡ），φｉ（２）（ＱＢ），Ｅｉ（２））を鍵配信サーバ１０に送信する。これより、各ユーザ端末２０ｉの公開値（φｉ（１）（ＰＢ），φｉ（１）（ＱＢ），Ｅｉ（１），φｉ（２）（ＰＡ），φｉ（２）（ＱＢ），Ｅｉ（２））が鍵配信サーバ１０に送信される。
【０１７１】
なお、上記のＳ２０１−４２におけるｍｉ（１），ｎｉ（１），ｍｉ（２）及びｎｉ（２）は、長期秘密ストリング記憶部２０９に記憶されている長期秘密ストリングと、短期秘密ストリング記憶部２１０に記憶されている短期秘密ストリングとを用いて、必要なときにねじれ疑似ランダム関数から生成することができる。このため、安全上、ｍｉ（１），ｎｉ（１），ｍｉ（２）及びｎｉ（２）は保存しないことが好ましい。
【０１７２】
ただし、安全性をあまり考慮しないのであれば、上記のＳ２０１−３２でｍｉ（１）及びｎｉ（１）を
【０１７３】
【数３０】
2019198516.tif 000032
からランダムに生成すると共に、ｍｉ（２）及びｎｉ（２）を
【０１７４】
【数３１】
2019198516.tif 000033
からランダムに生成し、保存しておいても良い。
【０１７５】
ステップＳ２０２：鍵配信ステップ（Ｒｏｕｎｄ１）
Ｓ２０２−５）通信部１０５は、各ユーザ端末２０ｉから公開値（φｉ（１）（ＰＢ），φｉ（１）（ＱＢ），Ｅｉ（１），φｉ（２）（ＰＡ），φｉ（２）（ＱＢ），Ｅｉ（２））を受信する。
【０１７６】
Ｓ２０２−６）通信部１０５は、各ユーザ端末２０ｉに対して、（ｓｉｄ，φｉ−１（１）（ＰＢ），φｉ−１（１）（ＱＢ），Ｅｉ−１（１），φｉ＋１（２）（ＰＡ），φｉ＋１（２）（ＱＢ），Ｅｉ＋１（２））を送信する。
【０１７７】
ステップＳ２０３：第二鍵生成ステップ（Ｒｏｕｎｄ２）
以降のＳ２０１−５１〜Ｓ２０１−５６は、各ユーザ端末２０ｉ（ｉ＝１，２，・・・，Ｎ）が実行する。ただし、Ｓ２０１−５４〜Ｓ２０３−５６は、代表ユーザ端末であるユーザ端末２０１と、それ以外のユーザ端末２０ｉ（ｉ＝２，３，・・・，Ｎ）とで処理内容が異なる。
【０１７８】
Ｓ２０３−５１）通信部２０８は、鍵配信サーバ１０から（ｓｉｄ，φｉ−１（１）（ＰＢ），φｉ−１（１）（ＱＢ），Ｅｉ−１（１），φｉ＋１（２）（ＰＡ），φｉ＋１（２）（ＱＢ），Ｅｉ＋１（２））を受信する。
【０１７９】
Ｓ２０３−５２）同種写像計算部２０４は、［ｍｉ（２）］φｉ−１（１）（ＰＢ）＋［ｎｉ（２）］φｉ−１（１）（ＱＢ）で生成されるＥｉ−１（１）の部分群Ｋｉ−１，ｉ（１）を核に持つ同種写像φｉ−１，ｉ（１）：Ｅｉ−１（１）→Ｅｉ−１，ｉ（１）と、この同種写像φｉ−１，ｉ（１）に付随する楕円曲線Ｅｉ−１，ｉ（１）とを計算する。
【０１８０】
同様に、同種写像計算部２０４は、［ｍｉ（１）］φｉ＋１（２）（ＰＡ）＋［ｎｉ（１）］φｉ＋１（２）（ＱＡ）で生成されるＥｉ＋１（２）の部分群Ｋｉ＋１，ｉ（２）を核に持つ同種写像φｉ＋１，ｉ（２）：Ｅｉ＋１（２）→Ｅｉ＋１，ｉ（２）と、この同種写像φｉ＋１，ｉ（２）に付随する楕円曲線Ｅｉ＋１，ｉ（２）とを計算する。
【０１８１】
Ｓ２０３−５３）同種写像計算部２０４は、楕円曲線Ｅｉ−１，ｉ（１）のｊ不変量ｊ（Ｅｉ−１，ｉ（１））と、楕円曲線Ｅｉ＋１，ｉ（２）のｊ不変量ｊ（Ｅｉ＋１，ｉ（２））とを計算する。
【０１８２】
Ｓ２０３−５４）ユーザ端末２０ｉ（ｉ＝２，３，・・・，Ｎ）の第１疑似ランダム関数部２０５は、Ｋｉ（ｌ）＝Ｆ（ｓｉｄ，ｊ（Ｅｉ−１，ｉ（１）））と、Ｋｉ（ｒ）＝Ｆ（ｓｉｄ，ｊ（Ｅｉ＋１，ｉ（２）））とを計算する。
【０１８３】
また、ユーザ端末２０１の第１疑似ランダム関数部２０５は、Ｋ１（ｌ）＝Ｆ（ｓｉｄ，ｊ（ＥＮ，１（１）））と、Ｋ１（ｒ）＝Ｆ（ｓｉｄ，ｊ（Ｅ２，１（２）））とを計算する。
【０１８４】
Ｓ２０３−５５）次に、ユーザ端末２０ｉ（ｉ＝２，３，・・・，Ｎ）の第１疑似ランダム関数部２０５は、Ｋｉ（ｌ）とＫｉ（ｒ）とのビット毎の排他的論理和Ｔｉを計算する。
【０１８５】
また、ユーザ端末２０１の第１疑似ランダム関数部２０５は、Ｋ１（ｌ）とＫ１（ｒ）との排他的論理和Ｔ１を計算すると共に、Ｋ１（ｌ）とｋ１との排他的論理和Ｔ´を計算する。なお、ｋ１は、第一鍵生成ステップ（Ｓ２０１）で生成されたものである。
【０１８６】
Ｓ２０３−５６）そして、ユーザ端末２０ｉ（ｉ＝２，３，・・・，Ｎ）の通信部２０８は、（ｋｉ，Ｔｉ）を鍵配信サーバ１０に送信する。なお、ｋｉは、第一鍵生成ステップ（Ｓ２０１）で生成されたものである。
【０１８７】
また、ユーザ端末２０１の通信部２０８は、（Ｔ´，Ｔ１）を鍵配信サーバ１０に送信する。
【０１８８】
以降のステップＳ２０４〜ステップＳ２０５は、実施例１と同様であるため、その説明を省略する。
【０１８９】
＜ハードウェア構成＞
図６に示すように、本発明の実施の形態における鍵配信サーバ１０及びユーザ端末２０は、入力装置３０１と、表示装置３０２と、外部Ｉ／Ｆ３０３と、ＲＡＭ（Random Access Memory）３０４と、ＲＯＭ（Read Only Memory）３０５と、ＣＰＵ（Central Processing Unit）３０６と、通信Ｉ／Ｆ３０７と、補助記憶装置３０８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【０１９０】
入力装置３０１は、例えばキーボードやマウス、タッチパネル等である。表示装置３０２は、例えばディスプレイ等である。なお、鍵配信サーバ１０は、入力装置３０１及び表示装置３０２のうちの少なくとも一方を有していなくても良い。
【０１９１】
外部Ｉ／Ｆ３０３は、外部装置とのインタフェースである。外部装置には、記録媒体３０３ａ等がある。記録媒体３０３ａとしては、例えば、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等が挙げられる。記録媒体３０３ａには、鍵配信サーバ１０の各機能部を実現する１以上のプログラムやユーザ端末２０の各機能部を実現する１以上のプログラム等が記録されていても良い。
【０１９２】
ＲＡＭ３０４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ３０５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。
【０１９３】
ＣＰＵ３０６は、ＲＯＭ３０５や補助記憶装置３０８等からプログラムやデータをＲＡＭ３０４上に読み出して処理を実行する演算装置である。鍵配信サーバ１０の各機能部やユーザ端末２０の各機能部は、ＣＰＵ３０６が１以上のプログラムを実行することによって実現される。
【０１９４】
通信Ｉ／Ｆ３０７は、ネットワーク３０に接続するためのインタフェースである。なお、鍵配信サーバ１０の各機能部を実現する１以上のプログラムやユーザ端末２０の各機能部を実現する１以上のプログラム等は、通信Ｉ／Ｆ３０７を介して、所定のサーバ等から取得（ダウンロード）されても良い。
【０１９５】
補助記憶装置３０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等の不揮発性の記憶装置である。補助記憶装置３０８には、鍵配信サーバ１０の各機能部を実現する１以上のプログラムやユーザ端末２０の各機能部を実現する１以上のプログラム等が記録される。
【０１９６】
本発明の実施の形態における鍵配信サーバ１０及びユーザ端末２０は、図６に示すハードウェア構成を有することにより、上述した各種処理を実現することができる。なお、図６では、本発明の実施の形態における鍵配信サーバ１０が１台の情報処理装置で実現される場合を示したが、これに限られない。本発明の実施の形態における鍵配信サーバ１０は、複数台の情報処理装置で実現されていても良い。
【０１９７】
＜まとめ＞
以上のように、本発明の実施の形態における鍵交換システム１では、ＤＭＫＤプロトコルにおけるＤＨ鍵交換を同種写像暗号に変更することで、耐量子性がある多者間鍵交換を実現することができる。
【０１９８】
しかも、本発明の実施の形態における鍵交換システム１の実施例１では、ユーザ端末２０の台数Ｎが偶数である場合、例えば、ユーザ端末２０１，ユーザ端末２０３，・・・，ユーザ端末２０Ｎ−１が基底｛ＰＡ，ＱＡ｝からそれぞれ公開値を計算し、ユーザ端末２０２，ユーザ端末２０４，・・・，ユーザ端末２０Ｎが基底｛ＰＢ，ＱＢ｝からそれぞれ公開値を計算する。これにより、（論理的に）リング状に配置されるユーザ端末２０の隣り合うユーザ端末２０同士は、異なる基底を使用して公開値を計算することなり、隣り合うユーザ端末２０同士での同種写像暗号の鍵交換を少ないラウンド数（２ラウンド）で容易に行うことができるようになる。
【０１９９】
一方で、ユーザ端末２０の台数Ｎが奇数である場合、代表ユーザ端末であるユーザ端末２０１が基底｛ＰＡ，ＱＡ｝及び基底｛ＰＢ，ＱＢ｝の両方からそれぞれ公開値を計算し、ユーザ端末２０３，ユーザ端末２０５，・・・，ユーザ端末２０Ｎ−１が基底｛ＰＡ，ＱＡ｝からそれぞれ公開値を計算し、ユーザ端末２０２，ユーザ端末２０４，・・・，ユーザ端末２０Ｎが基底｛ＰＢ，ＱＢ｝からそれぞれ公開値を計算する。このように、代表ユーザ端末が両方の基底｛ＰＡ，ＱＡ｝及び｛ＰＢ，ＱＢ｝からそれぞれ公開値を計算することで、ユーザ端末２０全体として、Ｎが偶数である場合と同様の振る舞いを実現することができ、同種写像暗号の鍵交換を少ないラウンド数で容易に行うことができるようになる。
【０２００】
また、本発明の実施の形態における鍵交換システム１の実施例２では、ユーザ端末２０の台数Ｎの偶奇によらず、全てのユーザ端末２０が基底｛ＰＡ，ＱＡ｝及び基底｛ＰＢ，ＱＢ｝の両方からそれぞれ公開値を計算する。これにより、ユーザ端末２０全体として、実施例１のＮが偶数である場合と同様の振る舞いを実現することができ、同種写像暗号の鍵交換を少ないラウンド数で容易に行うことができるようになる。更に、実施例２では、ユーザ数の偶奇に関わらず、同一の処理内容を用いるため、例えば、ユーザの偶奇に応じて条件分岐等が発生しない鍵交換処理を実現することができる。
【０２０１】
このように、本発明の実施の形態における鍵交換システム１では、耐量子性があり、かつ、非特許文献１と比べて少ないラウンド数（２ラウンド）の多者間鍵交換（すなわち、耐量子性があり、かつ、通信コストが少ない多者間鍵交換）を実現することができる。
【０２０２】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【０２０３】
本願は、日本国に２０１８年４月１１日に出願された基礎出願２０１８−０７６３４３号に基づくものであり、その全内容はここに参照をもって援用される。
【符号の説明】
【０２０４】
１        鍵交換システム
１０      鍵配信サーバ
２０      ユーザ端末
１０１    セットアップ部
１０２    長期秘密ストリング生成部
１０３    短期秘密ストリング生成部
１０４    公開情報計算部
１０５    通信部
１０６    長期秘密ストリング記憶部
１０７    短期秘密ストリング記憶部
２０１    長期秘密ストリング生成部
２０２    短期秘密ストリング生成部
２０３    ねじれ疑似ランダム関数部
２０４    同種写像計算部
２０５    第１疑似ランダム関数部
２０６    秘密情報計算部
２０７    第２疑似ランダム関数部
２０８    通信部
２０９    長期秘密ストリング記憶部
２１０    短期秘密ストリング記憶部
２１１    セッション情報記憶部
【図１】
2019198516.tif 000034
【図２】
2019198516.tif 000035
【図３】
2019198516.tif 000036
【図４】
2019198516.tif 000037
【図５】
2019198516.tif 000038
【図６】
2019198516.tif 000039
【国際調査報告】
2019198516.tif 000040
2019198516.tif 000041