(57)【要約】【課題】クラウド鍵管理型の鍵交換方式における認証処理やそれに必要な情報の管理を削減する。【解決手段】鍵装置１１２は、回線認証可能な何れかの回線の回線情報に対応する登録情報を格納し、第１端末装置１１１が他の第２端末装置１２１との鍵交換のために得た公開情報に対応する情報、および第１端末装置１１１が使用した回線認証に成功した使用回線の回線情報に対応する回線対応情報を受け付け、回線対応情報が登録情報に対応する場合に、少なくとも公開情報に対応する情報と秘密鍵とを用いて得られる鍵対応情報を出力する。【選択図】図１
2016129301.tif 000002
【特許請求の範囲】
【請求項１】
回線認証可能な何れかの回線の回線情報に対応する登録情報を格納する登録情報記憶部と、
第１端末装置が他の第２端末装置との鍵交換のために得た公開情報に対応する情報、および前記第１端末装置が使用した回線認証に成功した使用回線の回線情報に対応する回線対応情報を受け付ける入力部と、
前記回線対応情報が前記登録情報に対応する場合に、少なくとも前記公開情報に対応する情報と秘密鍵とを用いて得られる鍵対応情報を出力する出力部と、
を有する鍵装置。
【請求項２】
請求項１の鍵装置であって、
前記登録情報は、前記回線情報に対応する公開された第１固有情報または当該第１固有情報に対して一義的に決まる情報であり、
前記回線対応情報は、前期回線認証に成功した使用回線の回線情報に対応する公開された第２固有情報または当該第２固有情報に対して一義的に決まる情報である、鍵装置。
【請求項３】
請求項１または２の鍵装置であって、
前記入力部は、前記秘密鍵を特定するための情報を受け付け、
前記秘密鍵は、前記秘密鍵を特定するための情報によって特定される、鍵装置。
【請求項４】
請求項１から３の何れかの鍵装置であって、
前記秘密鍵は、前記回線対応情報に対応する、鍵装置。
【請求項５】
請求項１から４の何れかの鍵装置であって、
前記公開情報に対応する情報は、前記公開情報の撹乱情報であり、
前記鍵対応情報は、前記公開情報と前記秘密鍵とを用いて得られる共有情報を自己訂正処理によって得るための情報である、鍵装置。
【請求項６】
他の端末装置との鍵交換のために得た公開情報に対応する情報を使用回線に出力する出力部を含む端末装置と、
回線認証可能な何れかの回線の回線情報に対応する登録情報を格納する登録情報記憶部と、前記公開情報に対応する情報、および回線認証に成功した前記使用回線の回線情報に対応する回線対応情報を受け付ける入力部と、前記回線対応情報が前記登録情報に対応する場合に、少なくとも前記公開情報に対応する情報と秘密鍵とを用いて得られる鍵対応情報を出力する出力部と、を含む鍵装置と、
を有する鍵交換システム。
【請求項７】
他の第２端末装置との鍵交換のために得た第２公開情報に対応する情報を第１使用回線に出力する出力部を含む第１端末装置と、
回線認証可能な何れかの回線の第１回線情報に対応する第１登録情報を格納する第１登録情報記憶部と、前記第２公開情報に対応する情報、および回線認証に成功した前記第１使用回線の回線情報に対応する第１回線対応情報を受け付ける第１入力部と、前記第１回線対応情報が前記第１登録情報に対応する場合に、少なくとも前記第１公開情報に対応する情報と第１秘密鍵とを用いて得られる第１鍵対応情報を出力する第１出力部と、を含む第１鍵装置と、
前記第１端末装置との鍵交換のために得た第１公開情報に対応する情報を第２使用回線に出力する出力部を含む前記第２端末装置と、
回線認証可能な何れかの回線の第２回線情報に対応する第２登録情報を格納する第２登録情報記憶部と、前記第１公開情報に対応する情報、および回線認証に成功した前記第２使用回線の回線情報に対応する第２回線対応情報を受け付ける第２入力部と、前記第２回線対応情報が前記第２登録情報に対応する場合に、少なくとも前記第２公開情報に対応する情報と第２秘密鍵とを用いて得られる第２鍵対応情報を出力する第２出力部と、を含む第２鍵装置と、
を有する鍵交換システム。
【請求項８】
請求項１から５の何れかの鍵装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関するものであり、特に、クラウド鍵管理型の鍵交換技術に関する。
【背景技術】
【０００２】
鍵交換（鍵共有）方式とは、盗聴されてもよい通信路を用いて複数の端末装置が安全に鍵を交換（共有）するための方式をいう（例えば、非特許文献１等参照）。通常の鍵交換方式では、各端末装置が、鍵交換を行う他の端末装置の秘密鍵に対応する公開情報を得、この公開情報と自らの秘密鍵とを用いて共通鍵を生成する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】岡本龍明，“鍵交換：現代暗号の誕生とその発展”，[online]，Japan Science and Technology Agency，p70-76、[平成２７年１月２日検索]、インターネット＜https://www.jstage.jst.go.jp/article/essfr/1/4/1_4_4_70/_pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００４】
鍵装置が秘密鍵を保持する「クラウド鍵管理型」で鍵交換方式を実現することもできる。この場合、端末装置が公開情報および認証情報（証明書、ＩＤ、パスワード等）を鍵装置に送信し、鍵装置が認証情報を用いて認証処理を行い、認証成功であれば、当該公開情報と秘密鍵とを用いて共通鍵またはそれを得るための情報を生成し、それを当該端末装置に送信する。
【０００５】
しかしながら、このようなクラウド鍵管理型の鍵交換方式では、認証処理やそれに必要な情報の管理を端末装置またはユーザーごとに個々に行わなければならない。
【０００６】
本発明の課題は、クラウド鍵管理型の鍵交換方式における認証処理やそれに必要な情報の管理を削減することである。
【課題を解決するための手段】
【０００７】
鍵装置は、回線認証可能な何れかの回線の回線情報に対応する登録情報を格納し、第１端末装置が他の第２端末装置との鍵交換のために得た公開情報に対応する情報、および前記第１端末装置が使用した回線認証に成功した使用回線の回線情報に対応する回線対応情報を受け付け、前記回線対応情報が前記登録情報に対応する場合に、少なくとも前記公開情報に対応する情報と秘密鍵とを用いて得られる鍵対応情報を出力する。
【発明の効果】
【０００８】
本発明では、回線認証に成功した使用回線の回線情報に対応する回線対応情報に基づき、使用回線ごとに応答情報の出力の有無が定められるため、クラウド鍵管理型の鍵交換方式における認証処理やそれに必要な情報の管理を削減できる。
【図面の簡単な説明】
【０００９】
【図１】図１は実施形態の鍵交換システムの機能構成を例示したブロック図である。
【図２】図２は実施形態の鍵交換方法を例示したフロー図である。
【図３】図３は鍵交換のために公開情報を送受信する様子を例示したフロー図である。
【図４】図４は実施形態の鍵交換システムの機能構成を例示したブロック図である。
【図５】図５は自己訂正処理を例示したフロー図である。
【発明を実施するための形態】
【００１０】
以下、図面を参照して本発明の実施形態を説明する。
［第１実施形態］
第１実施形態を説明する。
＜構成＞
本形態の構成を説明する。図１に例示するように、本形態の鍵交換システム１は、端末装置１１１，１２１（第１端末装置，第２端末装置）と鍵装置１１２，１２２（第１鍵装置，第２鍵装置）とを有する。端末装置１１１と鍵装置１１２とは、回線認証機能および回線情報通知機能を備える公衆回線を通じて通信可能に構成されている。同様に、端末装置１２１と鍵装置１２２とは、回線認証機能および回線情報通知機能を備える公衆回線を通じて通信可能に構成されている。
【００１１】
回線認証 (network based authentication)とは、「このユーザーは確かにこの回線から通信してきた」ということを確認するためのユーザー認証技術である。回線認証自体は公知であり、例えば、参考文献１（“ＮＴＴデータ、ＮＧＮの回線情報を利用した認証連携機能を開発〜セキュリティを容易に確保するための仕組みを確立〜”、[online]、株式会社ＮＴＴデータ、[平成２６年１２月３１日検索]、インターネット＜http://www.nttdata.com/jp/ja/news/release/2009/091600.html＞）や米国特許出願公開第US2007-0234404 A1号明細書などに開示されている。端末装置１１１が公衆回線の特定の回線を用いて鍵装置１１２と通信を行う場合、端末装置１１１が使用する回線に対応する回線情報 (network based identification)が認証装置に送られる。回線情報の例は、例えば、参考文献２（Nir Yosef, Roded Sharan, and William Stafford Noble, “Improved network-based identification of protein orthologs,” Oxford Journals, Science & Mathematics Bioinformatics, Volume 24, Issue 16, pp. i200-i206, http://bioinformatics.oxfordjournals.org/content/24/16/i200.）に開示されている。認証装置での回線認証が成功である場合、端末装置１１１はこの回線を通じて鍵装置１１２と通信を行うことができる。認証装置での回線認証が失敗である場合、端末装置１１１はこの回線を通じて鍵装置１１２と通信を行うことができない。回線認証の具体例は、ＮＧＮ（next generation network）の回線認証やＥＡＰ−ＳＩ認証などがある。回線情報の具体例は、回線に接続される機器に固有な識別子、ゲートウェイ（ホームゲートウエイ等）のＭＡＣアドレス、フレッツナンバー（登録商標）、ＩＭＳＩ（International Mobile Subscriber Identity）、メールアドレス、所属部署名などである。
【００１２】
回線情報通知機能とは、或る回線を用いた通信において通信先の装置にその回線の回線情報を通知する機能である。回線情報通知機能も公知であり、例えば、参考文献３（“回線情報通知機能”、[online]、東日本電信電話株式会社、フレッツ公式ホームページ、[平成２６年１２月３１日検索]、インターネット＜http://flets.com/asc/s_outline.html＞）などに開示されている。端末装置１１１が或る回線を通じて鍵装置１１２と通信を行う場合、その回線の回線情報または当該回線情報に対して一義的に決まる情報が鍵装置１１２に通知される。以上のことは、端末装置１２１が公衆回線の特定の回線を用いて鍵装置１２２と通信を行う場合も同様である。
【００１３】
図１に例示するように、本形態の端末装置１１１は、記憶部１１１１と出力部１１１３と入力部１１１４と鍵交換処理部１１１５と通信部１１１６を有し、端末装置１２１は、記憶部１２１１と出力部１２１３と入力部１２１４と鍵交換処理部１２１５と通信部１２１６を有する。本形態の鍵装置１１２は、記憶部１１２１，１１２２と、入力部１１２３と、出力部１１２４と、判定部１１２５と、代理演算部１１２６とを有し、鍵装置１２２は、記憶部１２２１，１２２２と、入力部１２２３と、出力部１２２４と、判定部１２２５と、代理演算部１２２６とを有する。各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を含む汎用または専用のコンピュータに所定のプログラムが読み込まれることで構成されたものである。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。各処理部から出力された情報は、図示していない一時メモリに格納され、必要に応じて読み出されて各処理部の処理に用いられる。なお、表記の便宜上、図１では端末装置１１１と端末装置１２１と鍵装置１１２と鍵装置１２２とを１個ずつ図示しているが、これらの少なくとも一部の装置が存在してもよい。この際、２個以上の端末装置１１１や鍵装置１１２が同一の回線に接続されてもよいし、２個以上の端末装置１２１や鍵装置１２２が同一の回線に接続されてもよい。
【００１４】
＜事前処理＞
本形態では、秘密鍵ｓｋ１とそれに対応する公開鍵ｐｋ１との鍵ペア（ｓｋ１，ｐｋ１）、および秘密鍵ｓｋ２とそれに対応する公開鍵ｐｋ２との鍵ペア（ｓｋ２，ｐｋ２）が事前に設定される。鍵ペアの構成はベースとなる鍵交換方式に依存する（具体例は後述）。１組のみの鍵ペアが設定されてもよいし、互いに異なる複数組の鍵ペアが設定されてもよい。１組のみの鍵ペア（ｓｋ１，ｐｋ１）が設定された場合には、１個の秘密鍵ｓｋ１とそれに対応する公開鍵ｐｋ１（秘密鍵を特定するための情報）とが互いに対応付けられて鍵装置１１２の記憶部１１２１に格納される。互いに異なる複数組の鍵ペア（ｓｋ１，ｐｋ１）が設定された場合には、互いに異なる複数個の公開鍵ｐｋ１とそれらに対応する公開鍵ｐｋ１とが互いに対応付けられて記憶部１１２１に格納される。このような秘密鍵ｓｋ１とそれらに対応付けられた公開鍵ｐｋ１とを含むリストを「ｓｋ−Ｌｉｓｔ１」と表記する。なお、１組のみの鍵ペア（ｓｋ１，ｐｋ１）が設定された場合、ｓｋ−Ｌｉｓｔ１に代えてｓｋ１そのものが記憶部１１２１に格納されてもよい。同様に、１組のみの鍵ペア（ｓｋ２，ｐｋ２）が設定された場合には、１個の秘密鍵ｓｋ２とそれに対応する公開鍵ｐｋ２（秘密鍵を特定するための情報）とが互いに対応付けられて鍵装置１２２の記憶部１２２１に格納される。互いに異なる複数組の鍵ペア（ｓｋ２，ｐｋ２）が設定された場合には、互いに異なる複数個の公開鍵ｐｋ２とそれらに対応する公開鍵ｐｋ２とが互いに対応付けられて記憶部１２２１に格納される。このような秘密鍵ｓｋ２とそれらに対応付けられた公開鍵ｐｋ２とを含むリストを「ｓｋ−Ｌｉｓｔ２」と表記する。１組のみの鍵ペア（ｓｋ２，ｐｋ２）が設定された場合、ｓｋ−Ｌｉｓｔ２に代えてｓｋ２そのものが記憶部１２２１に格納されてもよい。
【００１５】
また、事前登録処理として、鍵装置１１２が鍵交換のための処理を行う回線の回線情報に対応する「登録情報」が事前設定され、鍵装置１１２の記憶部１１２２（登録情報記憶部）に格納される。鍵装置１１２が「鍵交換のための処理を行う回線」とは、鍵装置１１２に鍵交換のための処理を委託する端末装置１１１がその依頼に用いる回線を意味する。また、鍵交換のための処理を受けることができる権能のことを「鍵交換処理権限」と呼ぶことにする。本形態の「登録情報」は、回線認証可能な何れかの回線の回線情報に対応する。「登録情報」は、鍵装置１１２が鍵交換のための処理を行う回線の回線情報そのものであってもよいし、その回線情報に対して一義的に決まる情報であってもよい。また、回線情報の種類によっては、非公開である等の理由により、鍵装置１１２が回線認証のための回線情報からユーザーを識別することが困難な場合があり、回線認証のための回線情報を用いて鍵交換処理権限の有無の管理を行うことが困難な場合もある。例えば、端末装置として携帯電話を用いる場合、回線認証にはＩＭＥＩやＩＭＳＩなどの回線情報を用いるが、鍵装置１１２がＩＭＥＩやＩＭＳＩを用いてこのような管理を行うことが困難な場合もある。また、ＮＧＮの回線認証用の回線情報にフレッツナンバーを用いる場合、鍵装置１１２がこのフレッツナンバーを用いてこのような管理を行うことが困難な場合もある。鍵装置１１２にとっては、汎用性の高い電話番号等の一般的な回線情報を用いた管理のほうが容易な場合が多い。そこで、１個の回線に対して複数個の回線情報が紐づいている場合に、その一部の回線情報（例えば、ＩＭＥＩ，ＩＭＳＩ，フレッツナンバー，ＭＡＣアドレス等）が回線認証に用いられ、この回線認証に用いられた回線情報に紐づいた（対応する）他の回線情報（一般的な回線情報等）が管理に用いられてもよい。回線認証に用いられた回線情報に紐づいた他の回線情報を「固有情報」と呼ぶことにする。「固有情報」は公開情報であってもよいし、非公開情報であってもよい。結局、「登録情報」は、鍵装置１１２が鍵交換のための処理を行う回線の回線認証に用いられる回線情報そのものであってもよいし、その回線情報に対して一義的に決まる情報であってもよいし、鍵装置１１２が鍵交換のための処理を行う回線の固有情報であってもよいし、この固有情報に対して一義的に決まる情報であってもよいし、鍵装置１１２が鍵交換のための処理を行う回線の回線認証に用いられる回線情報とそれに紐づいた固有情報との組であってもよいし、その組に対して一義的に決まる情報であってもよいし、これらの何れかの情報を含む情報であってもよい。以下では、記憶部１１２２に格納された「登録情報」を含むリストを「Ｌｉｓｔ１」と表記する。
【００１６】
同様に、事前登録処理として、鍵装置１２２が鍵交換のための処理を行う回線の回線情報に対応する「登録情報」が事前設定され、鍵装置１２２の記憶部１２２２（登録情報記憶部）に格納される。この「登録情報」も、鍵装置１２２が鍵交換のための処理を行う回線の回線認証に用いられる回線情報そのものであってもよいし、その回線情報に対して一義的に決まる情報であってもよいし、鍵装置１２２が鍵交換のための処理を行う回線の固有情報であってもよいし、この固有情報に対して一義的に決まる情報であってもよいし、鍵装置１２２が鍵交換のための処理を行う回線の回線認証に用いられる回線情報とそれに紐づいた固有情報との組であってもよいし、その組に対して一義的に決まる情報であってもよいし、これらの何れかの情報を含む情報であってもよい。以下では、記憶部１２２２に格納された「登録情報」を含むリストを「Ｌｉｓｔ２」と表記する。
【００１７】
さらに、鍵装置１１２が鍵交換のための処理を行う回線を利用する端末装置１１１の記憶部１１１１に、何れかの秘密鍵ｓｋ１に対応する公開鍵ｐｋ１が格納される。同様に、鍵装置１２２が鍵交換のための処理を行う回線を利用する端末装置１２１の記憶部１２１１に、何れかの秘密鍵ｓｋ１に対応する公開鍵ｐｋ１が格納される。
【００１８】
＜鍵交換処理＞
図２および図３を用いて本形態の鍵交換処理を説明する。本形態では端末装置１１１と端末装置１２１との間で鍵交換を行い、その処理の一部を鍵装置１１２，１２２が代行する。
【００１９】
図３に例示するように、まず、端末装置１１１から端末装置１２１に公開情報β１−１，・・・，β１−Ｎ１（ただし、、Ｎ１は正の整数）が送信され、端末装置１２１から端末装置１１１に公開情報β２−１，・・・，β２−Ｎ２（ただし、Ｎ２は正の整数）が送信される。すなわち、端末装置１１１の鍵交換処理部１１１５は、記憶部１１１１から公開鍵ｐｋ１を読み込み、それを用いて端末装置１２１と鍵交換を行うための公開情報β１−ｎ１（ただし、ｎ１＝１，・・・，Ｎ１）を得て通信部１１１６に送る。通信部１１１６は公開情報β１−ｎ１を端末装置１２１に送信する。公開情報β１−ｎ１は端末装置１１１に対応する情報である。公開情報β１−ｎ１は端末装置１２１の通信部１２１６に入力され、鍵交換処理部１２１５に送られる。同様に、端末装置１２１の鍵交換処理部１２１５は、記憶部１２１１から公開鍵ｐｋ２を読み込み、それを用いて端末装置１１１と鍵交換を行うための公開情報β２−ｎ２（ただし、ｎ２＝１，・・・，Ｎ２）を得て通信部１２１６に送る。公開情報β２−ｎ２は端末装置１２１に対応する情報である。通信部１２１６は公開情報β２−ｎ２を端末装置１１１に送信する。公開情報β２−ｎ２は端末装置１１１の通信部１１１６に入力され、鍵交換処理部１１１５に送られる。鍵交換処理部１１１５は、公開情報β２−１，・・・，β２−Ｎ２から公開情報β２を得、鍵交換処理部１２１５は、公開情報β１−１，・・・，β１−Ｎ２から公開情報β１を得る。鍵交換処理部１２１５は、β１−１，・・・，β１−Ｎ１のすべてをβ１としてもよいし、それらの一部をβ１としてもよいし、β１−１，・・・，β１−Ｎ１のすべてまたは一部に対応する情報をβ１としてもよいし、β１−１，・・・，β１−Ｎ１のすべてまたは一部を用いて得られる情報をβ１としてもよい。同様に、鍵交換処理部１１１５は、β２−１，・・・，β２−Ｎ２のすべてをβ２としてもよいし、それらの一部をβ２としてもよいし、β２−１，・・・，β２−Ｎ２のすべてまたは一部に対応する情報をβ２としてもよいし、β２−１，・・・，β２−Ｎ２のすべてまたは一部を用いて得られる情報をβ２としてもよい。また、公開情報β１−ｎ１が端末装置１１１以外（例えば、鍵生成装置）から端末装置１２１に送信されてもよいし、公開情報β２−ｎ２が端末装置１２１以外から端末装置１１１に送信されてもよい。公開情報β１−ｎ１，β２−ｎ２およびβ１,β２の構成はベースとなる鍵交換方式（具体例は後述）に依存する（ステップＳ１０００）。
【００２０】
公開情報β２を得た端末装置１１１の鍵交換処理部１１１５は、公開情報β２を出力部１１１３に送る。鍵装置１１２の記憶部１１２１にｓｋ−Ｌｉｓｔ１が格納されている場合、鍵交換処理部１１１５は、さらに記憶部１１１１から読み込んだ公開鍵ｐｋ１（秘密鍵ｓｋ１を特定するための情報）を出力部１１１３に送る。出力部１１１３は、鍵装置１１２を宛先とし、公衆回線の所定の回線（使用回線）に対して公開情報β２を含む「要求情報」を出力する。ただし、記憶部１１２１にｓｋ−Ｌｉｓｔ１が格納されている場合、「要求情報」はさらに公開鍵ｐｋ１を含む（鍵交換処理要求：ステップＳ１１０１）。
【００２１】
公開情報β２を含む「要求情報」が出力された回線（使用回線）の回線情報ｄｘ１は、回線認証機能を提供する認証装置（図示せず）に送られ、この認証装置は回線情報ｄｘ１を用いた回線認証を行う（ステップＳ１１０２）。回線認証が失敗であった場合（ステップＳ１１０３）、エラー情報が端末装置１１１に送信される。送信されたエラー情報は、入力部１１１４に入力されて鍵交換処理部１１１５に送られ、鍵交換処理部１１１５は鍵交換処理を終了する（ステップＳ１１０４）。
【００２２】
一方、回線認証が成功であった場合（ステップＳ１１０３）、公開情報β２を含む「要求情報」が鍵装置１１２に送信され、さらに回線情報通知機能を提供する通知装置（図示せず）が、回線情報ｄｘ１に対応する回線対応情報ｘ１を鍵装置１１２に送信する。回線対応情報ｘ１は、回線情報ｄｘ１そのものであってもよいし、その回線情報ｄｘ１に対して一義的に決まる情報であってもよいし、回線情報ｄｘ１に紐付けられた固有情報ｉｄであってもよいし、この固有情報ｉｄに対して一義的に決まる情報であってもよいし、回線情報ｄｘ１とそれに紐づいた固有情報ｉｄとの組であってもよいし、その組に対して一義的に決まる情報であってもよいし、これらの何れかの情報を含む情報であってもよい（ステップＳ１１０５）。回線対応情報ｘ１、および公開情報β２を含む「要求情報」は、鍵装置１１２の入力部１１２３に入力される（受け付けられる）。入力部１１２３に入力される回線対応情報ｘ１は、回線認証に成功した回線（使用回線）に対応する情報である。回線対応情報ｘ１は判定部１１２５に送られ、公開情報β２を含む「要求情報」は代理演算部１１２６に送られる（ステップＳ１１０６）。判定部１１２５は、回線対応情報ｘ１が記憶部１１２２に格納されたリストＬｉｓｔ１の何れかの「登録情報」に対応するかを判定する。例えば、リストＬｉｓｔ１に含まれる「登録情報」が回線認証に用いられる回線情報そのものであり、回線対応情報ｘ１も回線情報ｄｘ１そのものである場合、判定部１１２５は『リストＬｉｓｔ１が回線対応情報ｘ１に一致する「登録情報」を含むか』を判定する。リストＬｉｓｔ１に含まれる「登録情報」が「固有情報」であり、回線対応情報ｘ１が回線情報ｄｘ１に紐付けられた「固有情報」である場合にも、判定部１１２５は『リストＬｉｓｔ１が回線対応情報ｘ１に一致する「登録情報」を含むか』を判定する。リストＬｉｓｔ１に含まれる「登録情報」が回線認証に用いられる回線情報そのものであり、回線対応情報ｘ１が回線情報ｄｘ１に紐付けられた「固有情報」である場合には、判定部１１２５は『リストＬｉｓｔ１が回線対応情報ｘ１に対応する「登録情報」を含むか』を判定する。その他、「登録情報」および回線対応情報ｘ１に用いられる情報の種別に応じた方法で、回線対応情報ｘ１が「登録情報」に対応するかを判定すればよい（ステップＳ１１０７）。回線対応情報ｘ１がリストＬｉｓｔ１の何れの「登録情報」にも対応しない場合（例えば、リストＬｉｓｔ１が回線対応情報ｘ１に一致する「登録情報」を含まない場合）（ステップＳ１１０８）、出力部１１２４からエラー情報が送信される。送信されたエラー情報は、端末装置１１１の入力部１１１４に入力されて鍵交換処理部１１１５に送られ、鍵交換処理部１１１５は鍵交換処理を終了する（ステップＳ１１０９）。一方、回線対応情報ｘ１がリストＬｉｓｔ１の何れかの「登録情報」に対応する場合（例えば、リストＬｉｓｔ１が回線対応情報ｘ１に一致する「登録情報」を含む場合）（ステップＳ１１０８）、代理演算部１１２６は記憶部１１２１から秘密鍵ｓｋ１を抽出する。「要求情報」が公開鍵ｐｋ１を含む場合、代理演算部１１２６は、「要求情報」が含む公開鍵ｐｋ１を用いて記憶部１１２１に格納されたｓｋ−Ｌｉｓｔ１を検索し、公開鍵ｐｋ１に対応する秘密鍵ｓｋ１を抽出する。代理演算部１１２６は、少なくとも、「要求情報」が含む公開情報β２に対応する情報と、抽出した秘密鍵ｓｋ１（秘密鍵を特定するための情報によって特定される秘密鍵）を用い、鍵対応情報λ１を生成して出力する。鍵対応情報λ１の生成方法はベースとなる鍵交換方式に依存する（具体例は後述）（ステップＳ１１１０）。鍵対応情報λ１は出力部１１２４に入力される。出力部１１２４は、端末装置１１１を宛先とし、回線対応情報ｘ１に対応する回線に対して鍵対応情報λ１を出力する（ステップＳ１１１１）。
【００２３】
鍵対応情報λ１は、端末装置１１１の入力部１１１４に入力されて鍵交換処理部１１１５に送られる（ステップＳ１１１２）。鍵交換処理部１１１５は、鍵対応情報λ１に対応する共有鍵Ｋを得て出力する（ステップＳ１１１３）。
【００２４】
端末装置１２１および鍵装置１２２でも同様な処理が行われる。すなわち、公開情報β１を得た鍵交換処理部１２１５は、公開情報β１を出力部１２１３に送る。鍵装置１２２の記憶部１２２１にｓｋ−Ｌｉｓｔ２が格納されている場合、鍵交換処理部１２１５は、さらに記憶部１２１１から読み込んだ公開鍵ｐｋ２（秘密鍵ｓｋ２を特定するための情報）を出力部１２１３に送る。出力部１２１３は、鍵装置１２２を宛先とし、公衆回線の所定の回線（使用回線）に対して公開情報β１を含む「要求情報」を出力する。ただし、記憶部１２２１にｓｋ−Ｌｉｓｔ２が格納されている場合、「要求情報」はさらに公開鍵ｐｋ２を含む（鍵交換処理要求：ステップＳ１２０１）。
【００２５】
公開情報β１を含む「要求情報」が出力された回線（使用回線）の回線情報ｄｘ２は、回線認証機能を提供する認証装置（図示せず）に送られ、この認証装置は回線情報ｄｘ２を用いた回線認証を行う（ステップＳ１２０２）。回線認証が失敗であった場合（ステップＳ１２０３）、エラー情報が端末装置１２１に送信される。送信されたエラー情報は、入力部１２１４に入力されて鍵交換処理部１２１５に送られ、鍵交換処理部１２１５は鍵交換処理を終了する（ステップＳ１２０４）。
【００２６】
一方、回線認証が成功であった場合（ステップＳ１２０３）、公開情報β１を含む「要求情報」が鍵装置１２２に送信され、さらに回線情報通知機能を提供する通知装置（図示せず）が、回線情報ｄｘ２に対応する回線対応情報ｘ２を鍵装置１２２に送信する。回線対応情報ｘ２は、回線情報ｄｘ２そのものであってもよいし、その回線情報ｄｘ２に対して一義的に決まる情報であってもよいし、回線情報ｄｘ２に紐付けられた固有情報ｉｄであってもよいし、この固有情報ｉｄに対して一義的に決まる情報であってもよいし、回線情報ｄｘ２とそれに紐づいた固有情報ｉｄとの組であってもよいし、その組に対して一義的に決まる情報であってもよいし、これらの何れかの情報を含む情報であってもよい（ステップＳ１２０５）。回線対応情報ｘ２、および公開情報β１を含む「要求情報」は、鍵装置１２２の入力部１２２３に入力される（受け付けられる）。入力部１２２３に入力される回線対応情報ｘ２は、回線認証に成功した回線（使用回線）に対応する情報である。回線対応情報ｘ２は判定部１２２５に送られ、公開情報β１を含む「要求情報」は代理演算部１２２６に送られる（ステップＳ１２０６）。判定部１２２５は、回線対応情報ｘ２が記憶部１２２２に格納されたリストＬｉｓｔ２の何れかの「登録情報」に対応するかを判定する（ステップＳ１２０７）。回線対応情報ｘ２がリストＬｉｓｔ２の何れの「登録情報」にも対応しない場合（ステップＳ１２０８）、出力部１２２４からエラー情報が送信される。送信されたエラー情報は、端末装置１２１の入力部１２１４に入力されて鍵交換処理部１２１５に送られ、鍵交換処理部１２１５は鍵交換処理を終了する（ステップＳ１２０９）。一方、回線対応情報ｘ２がリストＬｉｓｔ２の何れかの「登録情報」に対応する場合（ステップＳ１２０８）、代理演算部１２２６は記憶部１２２１から秘密鍵ｓｋ２を抽出する。「要求情報」が公開鍵ｐｋ２を含む場合、代理演算部１２２６は、「要求情報」が含む公開鍵ｐｋ２を用いて記憶部１２２１に格納されたｓｋ−Ｌｉｓｔ２を検索し、公開鍵ｐｋ２に対応する秘密鍵ｓｋ２を抽出する。代理演算部１２２６は、少なくとも、「要求情報」が含む公開情報β１に対応する情報と、抽出した秘密鍵ｓｋ２（秘密鍵を特定するための情報によって特定される秘密鍵）とを用い、鍵対応情報λ２を生成して出力する。鍵対応情報λ２の生成方法はベースとなる鍵交換方式に依存する（具体例は後述）（ステップＳ１２１０）。鍵対応情報λ２は出力部１２２４に入力される。出力部１２２４は、端末装置１２１を宛先とし、回線対応情報ｘ２に対応する回線に対して鍵対応情報λ２を出力する（ステップＳ１２１１）。
【００２７】
鍵対応情報λ２は、端末装置１２１の入力部１２１４に入力されて鍵交換処理部１２１５に送られる（ステップＳ１２１２）。鍵交換処理部１２１５は、鍵対応情報λ２に対応する共有鍵Ｋを得て出力する（ステップＳ１２１３）。
【００２８】
以下、ベースとなる鍵交換方式を具体化して例示する。
＜実施例１−１＞
実施例１−１ではＤＨＭ（Diffie-Hellman-Merkle）鍵交換方式をベースとして用いる。
《一般的なＤＨＭ鍵交換方式》
Ｇを素数ｐの可換群、ｇを群Ｇの単位元以外の元、ｘ∈Ｚｐを第１主体の秘密鍵、ｇｘ∈Ｇを第１主体の公開鍵、ｙ∈Ｚｐを第２主体の秘密鍵、ｇｙ∈Ｇを第２主体の公開鍵とする。
（１−１−ａ）第１主体がｇｘを第２主体に送る。
（１−１−ｂ）第２主体がｇｙを第１主体に送る。
（１−１−ｃ）第１主体はｇｙと秘密鍵ｘを用いて共有鍵Ｋ＝（ｇｙ）ｘを計算する。
（１−１−ｄ）第２主体はｇｘと秘密鍵ｙを用いて共有鍵Ｋ＝（ｇｘ）ｙを計算する。
Ｇは可換群であるため、Ｋ＝（ｇｙ）ｘ＝（ｇｘ）ｙが成立する。
【００２９】
《ＤＨＭ鍵交換方式をベースとした本形態の方式》
この実施例では、ｓｋ１＝ｘ、ｐｋ１＝ｇｘ、ｓｋ２＝ｙ、ｐｋ２＝ｇｙ、β１＝ｇｘ、β２＝ｇｙ、λ１＝Ｋ＝（ｇｙ）ｘ、λ２＝Ｋ＝（ｇｘ）ｙとし、第１実施形態の各処理を実行する。
【００３０】
＜実施例１−２＞
実施例１−２ではデジタル署名を用いた認証鍵交換（ＡＫＥ：Advent of Modern Cryptography and Its Advance）方式をベースとして用いる。
《一般的なデジタル署名を用いたＡＫＥ方式》
Ｇを素数ｐの可換群、ｇを群Ｇの単位元以外の元、ｘ∈Ｚｐを第１主体の秘密鍵、ｇｘ∈Ｇを第１主体の公開鍵、ｙ∈Ｚｐを第２主体の秘密鍵、ｇｙ∈Ｇを第２主体の公開鍵、Ｓｉｇａを第１主体の署名鍵、ＶｅｒａをＳｉｇａに対応する検証鍵、Ｓｉｇｂを第２主体の署名鍵、ＶｅｒｂをＳｉｇｂに対応する検証鍵とし、ＩＤＡを第１主体のユーザー識別子とし、ＩＤＢを第２主体のユーザー識別子とする。
（１−２−ａ）第１主体はｇｘとＩＤＡを第２主体に送る。
（１−２−ｂ）第２主体はｇｙとＩＤＢを第１主体に送る。
（１−２−ｃ）第１主体は、ｇｘとＩＤＡと電子署名Ｓｉｇａ（ｇｙ，ｇｘ，ＩＤＢ）を第２主体に送る。ただし、Ｓｉｇａ（ｇｙ，ｇｘ，ＩＤＢ）は、Ｓｉｇａを用いて（ｇｙ，ｇｘ，ＩＤＢ）に対して得られる署名値である。また、（ｇｙ，ｇｘ，ＩＤＢ）はｇｙ，ｇｘ，ＩＤＢのビット結合値等である。
（１−２−ｄ）第２主体は、ｇｙとＩＤＢと電子署名Ｓｉｇｂ（ｇｘ，ｇｙ，ＩＤＡ）を第１主体に送る。
（１−２−ｅ）第１主体は、検証鍵Ｖｅｒｂと（ｇｘ，ｇｙ，ＩＤＡ）を用いて電子署名Ｓｉｇｂ（ｇｘ，ｇｙ，ＩＤＡ）の検証を行い、合格であればｇｙと秘密鍵ｘを用いて共有鍵Ｋ＝（ｇｙ）ｘを計算する。
（１−２−ｆ）第２主体は、検証鍵Ｖｅｒａを用いて電子署名Ｓｉｇ（ｇｙ，ｇｘ，ＩＤＢ）の検証を行い、合格であればｇｘと秘密鍵ｙを用いて共有鍵Ｋ＝（ｇｘ）ｙを計算する。
【００３１】
《デジタル署名を用いたＡＫＥ方式をベースとした本形態の方式》
この実施例では、ｓｋ１＝ｘ、ｐｋ１＝ｇｘ、ｓｋ２＝ｙ、ｐｋ２＝ｇｙ、β１＝ｇｘ、β２＝ｇｙ、λ１＝Ｋ＝（ｇｙ）ｘ、λ２＝Ｋ＝（ｇｘ）ｙとし、第１実施形態の各処理を実行する。ただし、記憶部１１１１には、公開鍵ｐｋ１に加え、署名鍵Ｓｉｇａ、検証鍵Ｖｅｒｂ、ユーザー識別子ＩＤＡが格納される。記憶部１２１１には、公開鍵ｐｋ２に加え、署名鍵Ｓｉｇｂ、検証鍵Ｖｅｒａ、ユーザー識別子ＩＤＢが格納される。
【００３２】
ステップＳ１０００では、まず、端末装置１１１の鍵交換処理部１１１５が記憶部１１１１からβ１＝ｐｋ１＝ｇｘとＩＤＡを読み込み、通信部１１１６に送る。通信部１１１６はこれらを端末装置１２１に送信する。これらは端末装置１２１の通信部１２１６で受信され、鍵交換処理部１２１５に送られ、記憶部１２１１に格納される（１−２−ａ）。次に、端末装置１２１の鍵交換処理部１２１５が記憶部１２１１からβ２＝ｐｋ２＝ｇｙとＩＤＢを読み込み、通信部１２１６に送る。通信部１２１６はこれらを端末装置１１１に送信する。これらは端末装置１１１の通信部１１１６で受信され鍵交換処理部１１１５に送られ、記憶部１１１１に格納される（１−２−ｂ）。次に、端末装置１１１の鍵交換処理部１１１５が記憶部１１１１からｇｙ，ｇｘ，ＩＤＡ，ＩＤＢ，Ｓｉｇａを読み込み、Ｓｉｇａ（ｇｙ，ｇｘ，ＩＤＢ）を生成し、ｇｘとＩＤＡとＳｉｇａ（ｇｙ，ｇｘ，ＩＤＢ）を通信部１１１６に送る。通信部１１１６はこれらを端末装置１２１に送信する。これらは端末装置１２１の通信部１２１６で受信され、鍵交換処理部１２１５に送られ、記憶部１２１１に格納される（１−２−ｃ）。次に、端末装置１２１の鍵交換処理部１２１５が記憶部１２１１からｇｙ，ｇｘ，ＩＤＡ，ＩＤＢ，Ｓｉｇｂを読み込み、Ｓｉｇｂ（ｇｘ，ｇｙ，ＩＤＡ）を生成し、ｇｙとＩＤＢとＳｉｇｂ（ｇｘ，ｇｙ，ＩＤＡ）を通信部１２１６に送る。通信部１２１６はこれらを端末装置１１１に送信する。これらは端末装置１１１の通信部１１１６で受信され鍵交換処理部１１１５に送られ、記憶部１１１１に格納される（１−２−ｄ）。鍵交換処理部１１１５は、記憶部１１１１からＶｅｒｂと（ｇｘ，ｇｙ，ＩＤＡ）とＳｉｇｂ（ｇｘ，ｇｙ，ＩＤＡ）を読み込み、Ｖｅｒｂと（ｇｘ，ｇｙ，ＩＤＡ）を用いてＳｉｇｂ（ｇｘ，ｇｙ，ＩＤＡ）の検証を行い、合格であればステップＳ１１０１以降の処理に進む（１−２−ｅ）。鍵交換処理部１２１５は、Ｖｅｒａと（ｇｙ，ｇｘ，ＩＤＢ）とＳｉｇ（ｇｙ，ｇｘ，ＩＤＢ）を読み込み、Ｖｅｒａと（ｇｙ，ｇｘ，ＩＤＢ）を用いてＳｉｇ（ｇｙ，ｇｘ，ＩＤＢ）の検証を行い、合格であればステップＳ１２０１以降の処理に進む（１−２−ｆ）。
【００３３】
＜実施例１−３＞
実施例１−３ではＭＱＶ（Menezes-Qu-Vanstone）鍵交換方式をベースとして用いる。
《一般的なＭＱＶ鍵交換方式》
Ｇを素数ｐの可換群、ｇを群Ｇの単位元以外の元、ａ∈Ｚｐを第１主体の秘密鍵（長期秘密鍵、固定秘密鍵）、Ａ＝ｇａ∈Ｇを第１主体の公開鍵（長期公開鍵、固定公開鍵）、ｘ∈Ｚｐを第１主体の一時秘密鍵、Ｘ＝ｇｘ∈Ｇを第１主体の一時公開鍵、ｂ∈Ｚｐを第２主体の秘密鍵、Ｂ＝ｇｂ∈Ｇを第２主体の公開鍵、ｙ∈Ｚｐを第１主体の一時秘密鍵、Ｙ＝ｇｙ∈Ｇを第２主体の一時公開鍵とする。
（１−３−ａ）第１主体は（Ａ，Ｘ）を第２主体に送る。
（１−３−ｂ）第２主体は（Ｂ，Ｙ）を第１主体に送る。
（１−３−ｃ）第１主体はｋ＝｛Ｙ｝｜ｐ｜、ｄ＝｛Ｘ｝｜ｐ｜を計算する。ここで、｛Ｙ｝｜ｐ｜は、Ｙをビット表現した際の上位ｐビットを意味する。｛Ｘ｝｜ｐ｜についても同様である。
（１−３−ｄ）第１主体はσ＝（ＹＢｋ）ｘ＋ａｄを計算し、共有鍵Ｋ＝ＫＤＦ（σ）を得る。ただし、ＫＤＦはKey Derivation Functionであり、入力値をそれに対応する乱数に変換する関数である。
（１−３−ｅ）第２主体はｋ＝｛Ｙ｝｜ｐ｜、ｄ＝｛Ｘ｝｜ｐ｜を計算する。
（１−３−ｆ）第２主体はσ＝（ＸＡｄ）ｙ＋ｂｋを計算し、共有鍵Ｋ＝ＫＤＦ（σ）を得る。
ここで、Ｇは可換群であり、σ＝（ＹＢｋ）ｘ＋ａｄ＝ｇ（ｙ+ｂｋ）（ｘ＋ａｄ）＝（ＸＡｄ）ｙ＋ｂｋが成立する。
【００３４】
《ＭＱＶ鍵交換方式をベースとした本形態の方式》
この実施例では、ｓｋ１＝ａ”、ｐｋ１＝Ａ＝ｇａ”、ｓｋ２＝ｂ”、ｐｋ２＝Ｂ＝ｇｂ”、β１＝ＸＡｋ、β２＝ＹＢｋ、λ１＝ＹＢｋａ”、λ２＝ＸＡｋｂ”、ｋ＝｛Ｙ｝｜ｐ｜、ｄ＝｛Ｘ｝｜ｐ｜、Ｋ＝ＫＤＦ（（ＹＢｋ）ｘ＋ａ”ｄ）＝ＫＤＦ（（ＸＡｄ）ｙ＋ｂ”ｋ）とし、第１実施形態の各処理を実行する。ただし、記憶部１１１１には、公開鍵ｐｋ１＝Ａに加え、一時秘密鍵ｘ、一時公開鍵Ｘが格納され、記憶部１２１１には、公開鍵ｐｋ２＝Ｂに加え、一時秘密鍵ｙ、一時公開鍵Ｙが格納される。
【００３５】
ステップＳ１０００では、まず、端末装置１１１の鍵交換処理部１１１５が記憶部１１１１から（Ａ，Ｘ）を読み込んで通信部１１１６に送る。通信部１１１６は（Ａ，Ｘ）を端末装置１２１に送る。（Ａ，Ｘ）は通信部１２１６で受信されて鍵交換処理部１２１５に送られ、記憶部１２１１に格納される（１−３−ａ）。次に、端末装置１２１の鍵交換処理部１２１５が記憶部１２１１から（Ｂ，Ｙ）を読み込んで通信部１２１６に送る。通信部１２１６は（Ｂ，Ｙ）を端末装置１１１に送る。（Ｂ，Ｙ）は通信部１１１６で受信されて鍵交換処理部１１１５に送られ、記憶部１１１１に格納される（１−３−ｂ）。鍵交換処理部１１１５は、記憶部からＸ,Ｙを読み込んでｋ＝｛Ｙ｝｜ｐ｜、ｄ＝｛Ｘ｝｜ｐ｜を計算し、それらを記憶部１１１１に格納する（１−３−ｃ）。その後、ステップＳ１１０１〜Ｓ１１１２の処理が行われ、鍵交換処理部１１１５はλ１＝ＹＢｋａ”を得る。鍵交換処理部１１１５はλ１と記憶部１１１１から読み出したｘ,ｄとを用いてＫ＝ＫＤＦ（（ＹＢｋ）ｘ＋ａ”ｄ）を計算して出力する（ステップＳ１１１３,１−３−ｄ）。端末装置１２１の鍵交換処理部１２１５は、記憶部からＸ,Ｙを読み込んでｋ＝｛Ｙ｝｜ｐ｜、ｄ＝｛Ｘ｝｜ｐ｜を計算し、それらを記憶部１１１１に格納する（１−３−ｅ）。その後、ステップＳ１２０１〜Ｓ１２１２の処理が行われ、鍵交換処理部１２１５はλ２＝ＸＡｋｂ”を得る。鍵交換処理部１２１５はλ２と記憶部１１１１から読み出したｙ,ｄとを用いてＫ＝ＫＤＦ（（ＸＡｄ）ｙ＋ｂ”ｋ）を計算して出力する（ステップＳ１２１３,１−３−ｆ）。
【００３６】
＜実施例１−４＞
実施例１−４ではＨＭＱＶ（Hashed Menezes-Qu-Vanstone）鍵交換方式をベースとして用いる。
《一般的なＨＭＱＶ鍵交換方式》
ＨＭＱＶ鍵交換方式のＭＱＶ鍵交換方式との相違点は、ｋ＝｛Ｙ｝｜ｐ｜、ｄ＝｛Ｘ｝｜ｐ｜に代えてｋ＝Ｈａｓｈ（Ｙ,Ａ）,ｄ＝Ｈａｓｈ（Ｘ,Ｂ）とする点である。ここでＨａｓｈ（Ｙ,Ａ）は、（Ｙ,Ａ）に対する暗号学的なハッシュ値である。（Ｙ,Ａ）はＹ,Ａのビット結合値等である。Ｈａｓｈ（Ｘ,Ｂ）についても同様である。その他はＭＱＶ鍵交換方式と同じである。
【００３７】
《デジタル署名を用いたＡＫＥ方式をベースとした本形態の方式》
実施例１−４の実施例１−３との相違点は、ｋ＝Ｈａｓｈ（Ｙ,Ａ）,ｄ＝Ｈａｓｈ（Ｘ,Ｂ）とする点のみであり、その他は実施例１−３と同じである。
【００３８】
＜実施例１−５＞
実施例１−５ではＦＳＵ認証鍵交換方式（ｉｄ−ｉｄ−ＡＫＥ）をベースとして用いる。
《一般的なＦＳＵ認証鍵交換方式（ｉｄ−ｉｄ−ＡＫＥ）》
κをセキュリティパラメータとし、Ｇ１，Ｇ２，ＧＴを位数がκビット長の素数ｑの巡回群とし、ｇ１∈Ｇ１，ｇ２∈Ｇ２，ｇＴ∈ＧＴをそれぞれの群の生成元とする。ｅ：Ｇ１×Ｇ２→ＧＴをペアリングとし、ｇＴ＝ｅ（ｇ１，ｇ２）を満たすものとする。Ｈ：｛０，１｝*→｛０，１｝κ、Ｈ１：｛０，１｝*→Ｇ１、Ｈ２：｛０，１｝*→Ｇ２をそれぞれ暗号学的ハッシュ関数とする。２以上の自然数ｍに対して、ｍ個の多項式ｐｉ∈Ｚｑ［ｕ０，ｕ１，ｖ０，ｖ１］（ｉ＝１，・・・，ｍ）を以下のように与える。
【数１】
2016129301.tif 000003
ここで、ｃ（ｉ，０，０），ｃ（ｉ，０，１），ｃ（ｉ，１，０），ｃ（ｉ，１，１）は公開情報であり、定数であってもよいし、後述の短期公開鍵、公開鍵、ユーザー識別子等に依存して決まる値でもよい。鍵生成装置がマスタ秘密鍵ｚ∈Ｚｑをランダムに選択・保持し、マスタ公開鍵Ｚ１＝ｇ１ｚ∈Ｇ１とＺ２＝ｇ２ｚ∈Ｇ２を計算して公開する。ＩＤＡを第１主体のユーザー識別子とし、ＩＤＢを第２主体のユーザー識別子とする。ＩＤＡおよびＩＤＢは公開情報である。第１主体は、ＱＡ，１＝Ｈ１（ＩＤＡ）∈Ｇ１とＱＡ，２＝Ｈ２（ＩＤＡ）∈Ｇ２を公開鍵として計算して公開する。同様に、第２主体は、ＱＢ，１＝Ｈ１（ＩＤＢ）∈Ｇ１とＱＢ，２＝Ｈ２（ＩＤＢ）∈Ｇ２を公開鍵（長期公開鍵、固定公開鍵）として計算して公開する。
【００３９】
（鍵生成処理）鍵生成装置は、公開鍵（ＱＡ，１，ＱＡ，２），（ＱＢ，１，ＱＢ，２）をそれぞれ入力とし、秘密鍵（長期秘密鍵、固定秘密鍵）の２つのペアＤＡ，１＝ＱＡ，１ｚ，ＤＡ，２＝ＱＡ，２ｚとＤＢ，１＝ＱＢ，１ｚ，ＤＢ，２＝ＱＢ，２ｚを計算し、第１主体に秘密鍵のペア（ＤＡ，１，ＤＡ，２）を、第２主体に秘密鍵のペア（ＤＢ，１，ＤＢ，２）を配布する。第１主体は短期秘密鍵ｘＡ∈Ｚｑをランダムに選び、短期公開鍵のペアＸＡ，１＝ｇ１ｘＡ，ＸＡ，２＝ｇ２ｘＡを生成する。同様に、第２主体は短期秘密鍵ｘＢ∈Ｚｑをランダムに選び、短期公開鍵のペアＸＢ，１＝ｇ１ｘＢ，ＸＢ，２＝ｇ２ｘＢを生成する。ただし、上付き添え字の「ｘＡ」や「ｘＢ」は、それぞれ「ｘＡ」や「ｘＢ」を表す。
【００４０】
（１−５−ａ）第１主体は第２主体へ（ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２）を送信する。
（１−５−ｂ）第２主体は第１主体へ（ＩＤＡ，ＩＤＢ，ＸＢ，１，ＸＢ，２）を送信する。
（１−５−ｃ）第１主体はｅ（ＸＢ，１，ｇ２）＝ｅ（ｇ１，ＸＢ，２）を満たすかを確認し、第２主体はｅ（ＸＡ，１，ｇ２）＝ｅ（ｇ１，ＸＡ，２）を満たすかを確認する。正しくなければ、鍵生成処理からやり直す。正しければ、以下に進む。
【００４１】
（１−５−ｄ）第１主体は、以下の（１−５−ｄ−１）〜（１−５−ｄ−３）を行う。
（１−５−ｄ−１）第１主体は、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＤＡ，１ｃ（ｉ，０，０）Ｚ１ｃ（ｉ，１，０）ｘＡ，ＱＢ，２）ｅ（ＤＡ，１ｃ（ｉ，０，１）Ｚ１ｃ（ｉ，１，１）ｘＡ，ＸＢ，２）を計算する。
（１−５−ｄ−２）第１主体は、σｍ＋１＝ＸＢ，１ｘＡおよびσｍ＋２＝ＸＢ，２ｘＡを計算する。
（１−５−ｄ−３）第１主体は、共有鍵Ｋ＝Ｈ（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２，ＸＢ，１，ＸＢ，２）を計算する。
【００４２】
（１−５−ｅ）第２主体は、以下の（１−５−ｅ−１）〜（１−５−ｅ−３）を行う。
（１−５−ｅ−１）第２主体は、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＱＡ，１，ＤＢ，２ｃ（ｉ，０，０）Ｚ２ｃ（ｉ，０，１）ｘＢ）ｅ（ＸＡ，１，ＤＢ，２ｃ（ｉ，１，０）Ｚ２ｃ（ｉ，０，１）ｘＢ）を計算する。
（１−５−ｅ−２）第２主体は、σｍ＋１＝ＸＡ，１ｘＢおよびσｍ＋２＝ＸＡ，２ｘＢを計算する。
（１−５−ｅ−３）第２主体は、共有鍵Ｋ＝Ｈ（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２，ＸＢ，１，ＸＢ，２）を計算する。
【００４３】
ここでＱＡ，１＝ｇ１ｑ（Ａ，１）∈Ｇ１，ＱＢ，２＝ｇ２ｑ（Ｂ，２）∈Ｇ２とすると、ｅの双線形より、両者が計算したσ１，・・・，σｍ，σｍ＋１，σｍ＋２には以下が成り立つ。
・ｉ＝１，・・・，ｍについてσｉ＝ｇＴｚｐｉ（ｑ（Ａ，１），ｘＡ，ｑ（Ｂ，２），ｘＢ）（ただし、上付き添え字の「ｐｉ」は「ｐｉ」を表す）
・σｍ＋１＝ｇ１ｘＡｘＢおよびσｍ＋２＝ｇ２ｘＡｘＢ
従って両者の共通鍵Ｋは一致する。
【００４４】
《ＦＳＵ認証鍵交換方式（ｉｄ−ｉｄ−ＡＫＥ）をベースとした本形態の方式》
この実施例では、ｓｋ１＝（ＤＡ，１，ｘＡ）、ｐｋ１＝（ＱＡ，１，ＸＡ，１）、ｓｋ２＝（ＤＢ，２，ｘＢ）、ｐｋ２＝（ＱＢ，２，ＸＢ，２）、β１＝（ＸＡ，１，ＸＡ，２）、β２＝（ＸＢ，１，ＸＢ，２）、λ１＝（σ１，・・・，σｍ，σｍ＋１，σｍ＋２）、λ２＝（σ１，・・・，σｍ，σｍ＋１，σｍ＋２）、Ｋ＝Ｈ（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２，ＸＢ，１，ＸＢ，２）とし、第１実施形態の各処理を実行する。ただし、記憶部１１１１には、ｐｋ１＝（ＱＡ，１，ＸＡ，１）の他、ＩＤＡ，ＩＤＢ，ＸＡ，２が格納され、記憶部１２１１には、ｐｋ２＝（ＱＢ，２，ＸＢ，２）の他、ＩＤＡ，ＩＤＢ，ＸＢ，１が格納される。記憶部１１２１には、ｓｋ１＝（ＤＡ，１，ｘＡ）の他、Ｚ１，ＱＢ，２が格納され、記憶部１２２１には、ｓｋ２＝（ＤＢ，２，ｘＢ）の他、Ｚ２，ＱＡ，１が格納される。
【００４５】
ステップＳ１０００では、まず、端末装置１１１の鍵交換処理部１１１５が記憶部１１１１から（ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２）を読み込み、通信部１１１６に送る。通信部１１１６は（ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２）を端末装置１２１に送信する。（ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２）は通信部１２１６で受信されて鍵交換処理部１２１５に送られ、記憶部１２１１に格納される（１−５−ａ）。端末装置１２１の鍵交換処理部１２１５が記憶部１２１１から（ＩＤＡ，ＩＤＢ，ＸＢ，１，ＸＢ，２）を読み込み、通信部１２１６に送る。通信部１２１６は（ＩＤＡ，ＩＤＢ，ＸＢ，１，ＸＢ，２）を端末装置１１１に送信する。（ＩＤＡ，ＩＤＢ，ＸＢ，１，ＸＢ，２）は通信部１１１６で受信されて鍵交換処理部１１１５に送られ、記憶部１１１１に格納される（１−５−ｂ）。鍵交換部１１１５は記憶部１１１１から読み込んだβ２＝（ＸＢ，１，ＸＢ，２）がｅ（ＸＢ，１，ｇ２）＝ｅ（ｇ１，ＸＢ，２）を満たすかを確認し、鍵交換部１２１５は記憶部１２１１から読み込んだβ１＝（ＸＡ，１，ＸＡ，２）がｅ（ＸＡ，１，ｇ２）＝ｅ（ｇ１，ＸＡ，２）を満たすかを確認する。正しくなければ、鍵生成からやり直す。正しければステップＳ１１０１，Ｓ１２０１以降の処理に進む（１−５−ｃ）。
【００４６】
ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＤＡ，１ｃ（ｉ，０，０）Ｚ１ｃ（ｉ，１，０）ｘＡ，ＱＢ，２）ｅ（ＤＡ，１ｃ（ｉ，０，１）Ｚ１ｃ（ｉ，１，１）ｘＡ，ＸＢ，２）を計算し（１−５−ｄ−１）、σｍ＋１＝ＸＢ，１ｘＡおよびσｍ＋２＝ＸＢ，２ｘＡを計算し（１−５−ｄ−２）、λ１を得る。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＱＡ，１，ＤＢ，２ｃ（ｉ，０，０）Ｚ２ｃ（ｉ，０，１）ｘＢ）ｅ（ＸＡ，１，ＤＢ，２ｃ（ｉ，１，０）Ｚ２ｃ（ｉ，０，１）ｘＢ）を計算し（１−５−ｅ−１）、σｍ＋１＝ＸＡ，１ｘＢおよびσｍ＋２＝ＸＡ，２ｘＢを計算し（１−５−ｅ−２）、λ２を得る。
【００４７】
ステップＳ１１１３では、鍵交換処理部１１１５が、λ１と記憶部１１１１に格納された情報とを用いて共通鍵Ｋを得て出力し（１−５−ｄ−３）、ステップＳ１２１３では、鍵交換処理部１２１５が、λ２と記憶部１２１１に格納された情報とを用いて共通鍵Ｋを得て出力する（１−５−ｅ−３）。
【００４８】
＜実施例１−５の変形例１＞
実施例１−５の変形例１として、ｓｋ１＝ＤＡ，１とし、ｐｋ１＝ＱＡ，１とし、ｓｋ２＝ＤＢ，２とし、ｐｋ２＝ＱＢ，２とし、β１＝Ｐｉ,Ａ＝ＱＡ，１ｃ（ｉ，０，０）ＸＡ，１ｃ（ｉ，１，０）とし、β２＝Ｐｉ,Ｂ＝ＱＢ，２ｃ（ｉ，０，０）ＸＢ，２ｃ（ｉ，０，１）とし、λ１＝ζＡ,ｉ＝ｅ（ＤＡ，１，Ｐｉ,Ｂ）とし、λ２＝ζＢ,ｉ＝ｅ（Ｐｉ,Ａ，ＤＢ，２）としてもよい。ただし、記憶部１１１１には、ｐｋ１＝ＱＡ，１の他、ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２が格納され、記憶部１２１１には、ｐｋ２＝ＱＢ，２の他、ＩＤＡ，ＩＤＢ，ＸＢ，１，ＸＢ，２が格納される。記憶部１１２１には、ｓｋ１＝ＤＡ，１の他、ｘＡ，Ｚ１，ＱＢ，２が格納され、記憶部１２２１には、ｓｋ２＝（ＤＢ，２，ｘＢ）の他、ｘＢ，Ｚ２，ＱＡ，１が格納される。
【００４９】
ステップＳ１０００は実施例１−５と同じである。ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、λ１＝ζＡ,ｉ＝ｅ（ＤＡ，１，Ｐｉ,Ｂ）（ｉ＝１，・・・，ｍ）を計算する。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、λ２＝ζＢ,ｉ＝ｅ（Ｐｉ,Ａ，ＤＢ，２）（ｉ＝１，・・・，ｍ）を計算する。ステップＳ１１１３では、鍵交換処理部１１１５が、λ１と記憶部１１１１に格納された情報とを用いて共通鍵Ｋを得て出力し（１−５−ｄ）、ステップＳ１２１３では、鍵交換処理部１２１５が、λ２と記憶部１２１１に格納された情報とを用いて共通鍵Ｋを得て出力する（１−５−ｅ）。
【００５０】
＜実施例１−５の変形例２＞
実施例１−５の変形例２として、β１＝（Ｐｉ,Ａ，αｉ，Ａ）、β２＝（Ｐｉ,Ｂ，αｉ，Ｂ）、λ１＝（ζＡ,ｉ，αｉ，ＢｘＡ）、λ２＝（ζＢ,ｉ，αｉ，ＡｘＢ）としてもよい。ただし、
Ｐｉ,Ａ＝ＱＡ，１ｃ（ｉ，０，０）ＸＡ，１ｃ（ｉ，１，０）
Ｐｉ,Ｂ＝ＱＢ，２ｃ（ｉ，０，０）ＸＢ，２ｃ（ｉ，０，１）
ζＡ,ｉ＝ｅ（ＤＡ，１，Ｐｉ,Ｂ）
ζＢ,ｉ＝ｅ（Ｐｉ,Ａ，ＤＢ，２）
【数２】
2016129301.tif 000004
【数３】
2016129301.tif 000005
である。記憶部１１１１には、ｐｋ１＝（ＱＡ，１，ＸＡ，１）の他、ＩＤＡ，ＩＤＢ，ＸＡ，２が格納され、記憶部１２１１には、ｐｋ２＝（ＱＢ，２，ＸＢ，２）の他、ＩＤＡ，ＩＤＢ，ＸＢ，１が格納される。
【００５１】
ステップＳ１０００は実施例１−５と同じである。ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、λ１＝（ζＡ,ｉ，αｉ，ＢｘＡ）（ｉ＝１，・・・，ｍ）を計算する。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、λ２＝（ζＢ,ｉ，αｉ，ＡｘＢ）（ｉ＝１，・・・，ｍ）を計算する。ステップＳ１１１３では、鍵交換処理部１１１５が、λ１と記憶部１１１１に格納された情報とを用いて共通鍵Ｋを得て出力し（１−５−ｄ）、ステップＳ１２１３では、鍵交換処理部１２１５が、λ２と記憶部１２１１に格納された情報とを用いて共通鍵Ｋを得て出力する（１−５−ｅ）。
【００５２】
＜実施例１−５の変形例３＞
実施例１−５の変形例２として、β１＝（Ｐｉ,Ａ，Ｐ’ｉ,Ａ，α’ｉ，Ａ）、β２＝（Ｐｉ,Ｂ，Ｐ’ｉ,Ｂ，α’ｉ，Ｂ）、λ１＝（ζＡ,ｉ，ζ’Ａ,ｉ，α’ｉ，ＢｘＡ）、λ２＝（ζＢ,ｉ，ζ’Ｂ,ｉ，α’ｉ，ＡｘＢ）としてもよい。ただし、
Ｐｉ,Ａ＝ＱＡ，１ｃ（ｉ，０，０）ＸＡ，１ｃ（ｉ，１，０）
Ｐｉ,Ｂ＝ＱＢ，２ｃ（ｉ，０，０）ＸＢ，２ｃ（ｉ，０，１）
Ｐ’ｉ,Ａ＝ＱＡ，１ｃ（ｉ，０，1）ＸＡ，１ｃ（ｉ，１，1）
Ｐ’ｉ,Ｂ＝ＱＢ，２ｃ（ｉ，1，０）ＸＢ，２ｃ（ｉ，1，１）
ζＡ,ｉ＝ｅ（ＤＡ，１，Ｐｉ,Ｂ）
ζＢ,ｉ＝ｅ（Ｐｉ,Ａ，ＤＢ，２）
ζ’Ａ,ｉ＝ｅ（Ｚ１ｘＡ，Ｐ’ｉ,Ｂ）
ζ’Ｂ,ｉ＝ｅ（Ｐ’ｉ,Ａ，Ｚ２ｘＢ）
【数４】
2016129301.tif 000006
【数５】
2016129301.tif 000007
である。記憶部１１１１には、ｐｋ１＝（ＱＡ，１，ＸＡ，１）の他、ＩＤＡ，ＩＤＢ，ＸＡ，２が格納され、記憶部１２１１には、ｐｋ２＝（ＱＢ，２，ＸＢ，２）の他、ＩＤＡ，ＩＤＢ，ＸＢ，１が格納される。
【００５３】
ステップＳ１０００は実施例１−５と同じである。ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、λ１＝（ζＡ,ｉ，ζ’Ａ,ｉ，α’ｉ，ＢｘＡ）（ｉ＝１，・・・，ｍ）を計算する。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、λ２＝（ζＢ,ｉ，ζ’Ｂ,ｉ，α’ｉ，ＡｘＢ）（ｉ＝１，・・・，ｍ）を計算する。ステップＳ１１１３では、鍵交換処理部１１１５が、λ１と記憶部１１１１に格納された情報とを用いて共通鍵Ｋを得て出力し（１−５−ｄ）、ステップＳ１２１３では、鍵交換処理部１２１５が、λ２と記憶部１２１１に格納された情報とを用いて共通鍵Ｋを得て出力する（１−５−ｅ）。
【００５４】
＜実施例１−６＞
実施例１−６ではＦＳＵ認証鍵交換方式（ｃｅｒｔ−ｃｅｒｔ−ＡＫＥ）をベースとして用いる。
《一般的なＦＳＵ認証鍵交換方式（ｃｅｒｔ−ｃｅｒｔ−ＡＫＥ）》
κをセキュリティパラメータとし、Ｇを位数がκビット長の素数ｑの巡回群とし、ｇ∈Ｇを群Ｇの生成元とする。Ｈ：｛０，１｝*→｛０，１｝κ、Ｈ１：｛０，１｝*→Ｇをそれぞれ暗号学的ハッシュ関数とする。前述の式（１）のようにｍ個（ただし、ｍは２以上の自然数）の多項式ｐｉ∈Ｚｑ［ｕ０，ｕ１，ｖ０，ｖ１］（ｉ＝１，・・・，ｍ）を与える。第１主体は、秘密鍵（長期秘密鍵、固定秘密鍵）ｓＡ∈Ｚｑを持ち、公開鍵（長期公開鍵、固定公開鍵）ＳＡ＝ｇｓＡを公開する。第２主体は、秘密鍵ｓＢ∈Ｚｑを持ち、公開鍵ＳＢ＝ｇｓＢを公開する。ただし、上付き添え字の「ｓＡ」は「ｓＡ」を表し、「ｓＢ」は「ｓＢ」を表す。認証局は公開鍵ＳＡと公開鍵ＳＢを認証する。第１主体は、短期秘密鍵ｘＡ∈Ｚｑをランダムに選び、短期公開鍵ＸＡ＝ｇｘＡを公開する。同様に、第２主体は、短期秘密鍵ｘＢ∈Ｚｑをランダムに選び、短期公開鍵ＸＢ＝ｇｘＢを公開する。ただし、上付き添え字の「ｘＡ」は「ｘＡ」を表し、「ｘＢ」は「ｘＢ」を表す。
【００５５】
（１−６−ａ）第１主体は第２主体へ（ＩＤＡ，ＩＤＢ，ＸＡ）を送信する。
（１−６−ｂ）第２主体は第１主体へ（ＩＤＡ，ＩＤＢ，ＸＢ）を送信する。
【００５６】
（１−６−ｃ）第１主体は、以下の（１−６−ｃ−１）および（１−６−ｃ−２）を行う。
（１−６−ｃ−１）第１主体は、ｉ＝１，・・・，ｍについてσｉ＝ＸＢｃ（ｉ，０，１）ｓＡ＋ｃ（ｉ，１，０）ｘＡＳＢｃ（ｉ，０，０）ｓＡ＋ｃ（ｉ，１，１）ｘＡを計算する。
（１−６−ｃ−２）第１主体は、共有鍵Ｋ＝Ｈ（σ１，・・・，σｍ，ＩＤＡ，ＩＤＢ，ＸＡ，ＸＢ）を計算する。
【００５７】
（１−６−ｄ）第２主体は、以下の（１−６−ｄ−１）および（１−６−ｄ−２）を行う。
（１−６−ｄ−１）第２主体は、ｉ＝１，・・・，ｍについてσｉ＝ＸＡｃ（ｉ，１，０）ｓＢ＋ｃ（ｉ，１，１）ｘＢＳＡｃ（ｉ，０，０）ｓＢ＋ｃ（ｉ，０，１）ｘＢを計算する。
（１−６−ｄ−２）第２主体は、共有鍵Ｋ＝Ｈ（σ１，・・・，σｍ，ＩＤＡ，ＩＤＢ，ＸＡ，ＸＢ）を計算する。
【００５８】
ここで、両者が計算したσ１，・・・，σｍは、σｉ＝ｇｐｉ（ｓＡ，ｘＡ，ｓＢ，ｘＢ）の関係を満たすため、両者の共通鍵Ｋは一致する。
【００５９】
《ＦＳＵ認証鍵交換方式（ｃｅｒｔ−ｃｅｒｔ−ＡＫＥ）をベースとした本形態の方式》
この実施例では、ｓｋ１＝（ｓＡ，ｘＡ）、ｐｋ１＝（ＳＡ，ＸＡ）、ｓｋ２＝（ｓＢ，ｘＢ）、ｐｋ２＝（ＳＢ，ＸＢ）、β１＝ＸＡ、β２＝ＸＢ、λ１＝（σ１，・・・，σｍ）、λ２＝（σ１，・・・，σｍ）、Ｋ＝Ｈ（σ１，・・・，σｍ，ＩＤＡ，ＩＤＢ，ＸＡ，ＸＢ）とし、第１実施形態の各処理を実行する。ただし、記憶部１１１１には、ｐｋ１＝（ＳＡ，ＸＡ）の他、ｘＡ，ＩＤＡ，ＩＤＢ，ＸＡが格納され、記憶部１２１１には、ｐｋ２＝（ＳＢ，ＸＢ）の他、ｘＢ，ＩＤＡ，ＩＤＢ，ＸＢが格納される。記憶部１１２１には、ｓｋ１＝（ｓＡ，ｘＡ）の他、ＳＢが格納され、記憶部１２２１には、ｓｋ２＝（ｓＢ，ｘＢ）の他、ＳＡが格納される。
【００６０】
ステップＳ１０００では、まず、端末装置１１１の鍵交換処理部１１１５が記憶部１１１１から（ＩＤＡ，ＩＤＢ，ＸＡ）を読み込み、通信部１１１６に送る。通信部１１１６は（ＩＤＡ，ＩＤＢ，ＸＡ）を端末装置１２１に送信する。（ＩＤＡ，ＩＤＢ，ＸＡ）は通信部１２１６で受信されて鍵交換処理部１２１５に送られ、記憶部１２１１に格納される（１−６−ａ）。端末装置１２１の鍵交換処理部１２１５が記憶部１２１１から（ＩＤＡ，ＩＤＢ，ＸＢ）を読み込み、通信部１２１６に送る。通信部１２１６は（ＩＤＡ，ＩＤＢ，ＸＢ）を端末装置１１１に送信する。（ＩＤＡ，ＩＤＢ，ＸＢ）は通信部１１１６で受信されて鍵交換処理部１１１５に送られ、記憶部１１１１に格納される（１−６−ｂ）。
【００６１】
その後、ステップＳ１１０１，Ｓ１２０１以降の処理に進む。ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてσｉ＝ＸＢｃ（ｉ，０，１）ｓＡ＋ｃ（ｉ，１，０）ｘＡＳＢｃ（ｉ，０，０）ｓＡ＋ｃ（ｉ，１，１）ｘＡを計算し（１−６−ｃ−１）、λ１を得る。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてσｉ＝ＸＡｃ（ｉ，１，０）ｓＢ＋ｃ（ｉ，１，１）ｘＢＳＡｃ（ｉ，０，０）ｓＢ＋ｃ（ｉ，０，１）ｘＢを計算し（１−６−ｄ−１）、λ２を得る。
【００６２】
ステップＳ１１１３では、鍵交換処理部１１１５が、λ１と記憶部１１１１に格納された情報とを用いて共通鍵Ｋを得て出力し（１−６−ｃ−２）、ステップＳ１２１３では、鍵交換処理部１２１５が、λ２と記憶部１２１１に格納された情報とを用いて共通鍵Ｋを得て出力する（１−６−ｄ−２）。
【００６３】
＜実施例１−６の変形例１＞
実施例１−６の変形例１として、（１−６−ａ）に代えて第１主体は第２主体へ（ＳＡ，ＸＡ）を送信し（１−６−ａ）’、（１−６−ｂ）に代えて第２主体は第１主体へ（ＳＢ，ＸＢ）を送信し（１−６−ｂ）’、ｓｋ１＝ｘＡとし、ｐｋ１＝ＸＡとし、ｓｋ２＝ｘＢとし、ｐｋ２＝ＸＢとし、β１＝αＡ，ｉ＝ＸＡｃ（ｉ，１，１）ＳＡｃ（ｉ，０，１）とし、β２＝αＢ，ｉ＝ＸＢｃ（ｉ，１，０）ＳＢｃ（ｉ，１，１）とし、λ１＝αＢ，ｉｘＡとし、λ２＝αＡ，ｉｘＢとし、Ｋ＝Ｈ（σ１，・・・，σｍ，ＳＡ，ＳＢ，ＸＡ，ＸＢ）としてもよい。ただし、記憶部１１１１には、ｐｋ１＝ＸＡの他、ＳＡが格納され、記憶部１２１１には、ｐｋ２＝ＸＢの他、ＳＢが格納される。
【００６４】
ステップＳ１０００では、まず、端末装置１１１の鍵交換処理部１１１５が記憶部１１１１から（ＳＡ，ＸＡ）を読み込み、通信部１１１６に送る。通信部１１１６は（ＳＡ，ＸＡ）を端末装置１２１に送信する。（ＳＡ，ＸＡ）は通信部１２１６で受信されて鍵交換処理部１２１５に送られ、記憶部１２１１に格納される（１−６−ａ）’。端末装置１２１の鍵交換処理部１２１５が記憶部１２１１から（ＳＢ，ＸＢ）を読み込み、通信部１２１６に送る。通信部１２１６は（ＳＢ，ＸＢ）を端末装置１１１に送信する。（ＳＢ，ＸＢ）は通信部１１１６で受信されて鍵交換処理部１１１５に送られ、記憶部１１１１に格納される（１−６−ｂ）’。
【００６５】
その後、ステップＳ１１０１，Ｓ１２０１以降の処理に進む。ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてλ１＝αＢ，ｉｘＡを計算し、λ１を得る。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてλ２＝αＡ，ｉｘＢを計算し、λ２を得る。
【００６６】
ステップＳ１１１３では、鍵交換処理部１１１５がλ１と記憶部１１１１に格納された情報とを用い、ｉ＝１，・・・，ｍについてσｉ＝ＸＢｃ（ｉ，０，１）ｓＡ＋ｃ（ｉ，１，０）ｘＡＳＢｃ（ｉ，０，０）ｓＡ＋ｃ（ｉ，１，１）ｘＡ＝λ１・ＸＢｃ（ｉ，０，１）ｓＡＳＢｃ（ｉ，０，０）ｓＡを計算し、共通鍵Ｋを得る。ステップＳ１２１３では、鍵交換処理部１２１５がλ２と記憶部１２１１に格納された情報とを用い、ｉ＝１，・・・，ｍについてσｉ＝ＸＡｃ（ｉ，１，０）ｓＢ＋ｃ（ｉ，１，１）ｘＢＳＡｃ（ｉ，０，０）ｓＢ＋ｃ（ｉ，０，１）ｘＢ＝λ２・ＸＡｃ（ｉ，１，０）ｓＢＳＡｃ（ｉ，０，０）ｓＢを計算し、共通鍵Ｋを得る。
【００６７】
＜実施例１−６の変形例２＞
実施例１−６の変形例２として、（１−６−ａ）に代えて第１主体は第２主体へ（ＳＡ，ＸＡ）を送信し（１−６−ａ）’、（１−６−ｂ）に代えて第２主体は第１主体へ（ＳＢ，ＸＢ）を送信し（１−６−ｂ）’、ｓｋ１＝（ｓＡ，ｘＡ）とし、ｐｋ１＝（ＳＡ，ＸＡ）とし、ｓｋ２＝（ｓＢ，ｘＢ）とし、ｐｋ２＝（ＳＢ，ＸＢ）とし、β１＝（αＡ，ｉ,βＡ，ｉ）＝（ＸＡｃ（ｉ，１，１）ＳＡｃ（ｉ，０，１）,ＸＡｃ（ｉ，１，０）ＳＡｃ（ｉ，０，０））とし、β２＝（αＢ，ｉ,βＢ，ｉ）＝（ＸＢｃ（ｉ，１，０）ＳＢｃ（ｉ，１，１）,ＸＢｃ（ｉ，０，１）ＳＢｃ（ｉ，０，０））とし、λ１＝（αＢ，ｉｘＡ，βＢ，ｉｓＡ）とし、λ２＝（αＡ，ｉｘＢ,βＡ，ｉｓＢ）とし、Ｋ＝Ｈ（σ１，・・・，σｍ，ＳＡ，ＳＢ，ＸＡ，ＸＢ）としてもよい。
【００６８】
ステップＳ１０００は実施例１−６の変形例１と同じであり、その後、ステップＳ１１０１，Ｓ１２０１以降の処理に進む。ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてλ１＝（αＢ，ｉｘＡ，βＢ，ｉｓＡ）を計算し、λ１を得る。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてλ２＝（αＡ，ｉｘＢ,βＡ，ｉｓＢ）を計算し、λ２を得る。
【００６９】
ステップＳ１１１３では、鍵交換処理部１１１５がλ１＝（αＢ，ｉｘＡ，βＢ，ｉｓＡ）と記憶部１１１１に格納された情報とを用い、ｉ＝１，・・・，ｍについてσｉ＝ＸＢｃ（ｉ，０，１）ｓＡ＋ｃ（ｉ，１，０）ｘＡＳＢｃ（ｉ，０，０）ｓＡ＋ｃ（ｉ，１，１）ｘＡ＝αＢ，ｉｘＡβＢ，ｉｓＡを計算し、共通鍵Ｋを得る。ステップＳ１２１３では、鍵交換処理部１２１５がλ２＝（αＡ，ｉｘＢ,βＡ，ｉｓＢ）および記憶部１２１１に格納された情報を用い、ｉ＝１，・・・，ｍについてσｉ＝ＸＡｃ（ｉ，１，０）ｓＢ＋ｃ（ｉ，１，１）ｘＢＳＡｃ（ｉ，０，０）ｓＢ＋ｃ（ｉ，０，１）ｘＢ＝αＡ，ｉｘＢβＡ，ｉｓＢを計算し、共通鍵Ｋを得る。
【００７０】
＜実施例１−７＞
実施例１−７ではＦＳＵ認証鍵交換方式（ｃｅｒｔ−ｉｄ−ＡＫＥ）をベースとして用いる。
《一般的なＦＳＵ認証鍵交換方式（ｃｅｒｔ−ｉｄ−ＡＫＥ）》
κをセキュリティパラメータとし、Ｇ１，Ｇ２，ＧＴを位数がκビット長の素数ｑの巡回群とし、ｇ１∈Ｇ１，ｇ２∈Ｇ２，ｇＴ∈ＧＴをそれぞれの群の生成元とする。ｅ：Ｇ１×Ｇ２→ＧＴをペアリングとし、ｇＴ＝ｅ（ｇ１，ｇ２）を満たすものとする。Ｈ：｛０，１｝*→｛０，１｝κ、Ｈ１：｛０，１｝*→Ｇ１、Ｈ２：｛０，１｝*→Ｇ２をそれぞれ暗号学的ハッシュ関数とする。多項式ｐｉ（ただしｉ＝１，・・・，ｍ、ｍは２以上の自然数）を式（１）のように与える。鍵生成装置がマスタ秘密鍵ｚ∈Ｚｑをランダムに選択・保持し、マスタ公開鍵Ｚ１＝ｇ１ｚ∈Ｇ１とＺ２＝ｇ２ｚ∈Ｇ２を計算して公開する。第１主体は、ユーザー識別子ＩＤＡを持ち、ＱＡ，１＝Ｈ１（ＩＤＡ）∈Ｇ１とＱＡ，２＝Ｈ２（ＩＤＡ）∈Ｇ２を公開鍵として計算して公開する。
【００７１】
（鍵生成処理）鍵生成装置は、公開鍵（ＱＡ，１，ＱＡ，２）を入力とし、秘密鍵（長期秘密鍵、固定秘密鍵）のペアＤＡ，１＝ＱＡ，１ｚ，ＤＡ，２＝ＱＡ，２ｚを計算し、第１主体に秘密鍵のペア（ＤＡ，１，ＤＡ，２）を配布する。第２主体は、秘密鍵ｓＢ∈Ｚｑを持ち、公開鍵のペアＳＢ，１＝ｇ１ｓＢ∈Ｇ１とＳＢ，２＝ｇ２ｓＢ∈Ｇ２を計算して公開する。認証局は公開鍵（ＳＢ，１，ＳＢ，２）を認証する。第１主体は短期秘密鍵ｘＡ∈Ｚｑをランダムに選び、短期公開鍵のペアＸＡ，１＝ｇ１ｘＡ，ＸＡ，２＝ｇ２ｘＡを生成する。同様に、第２主体は短期秘密鍵ｘＢ∈Ｚｑをランダムに選び、短期公開鍵のペアＸＢ，１＝ｇ１ｘＢ，ＸＢ，２＝ｇ２ｘＢを生成する。
【００７２】
（１−７−ａ）第１主体は第２主体へ（ＩＤＡ，ＸＡ，１，ＸＡ，２）を送信する。
（１−７−ｂ）第２主体は第１主体へ（ＳＢ，１，ＳＢ，２，ＸＢ，１，ＸＢ，２）を送信する。
（１−７−ｃ）第１主体はｅ（ＸＢ，１，ｇ２）＝ｅ（ｇ１，ＸＢ，２）であるかとｅ（ＳＢ，１，ｇ２）＝ｅ（ｇ１，ＳＢ，２）であるかを確認し、第２主体はｅ（ＸＡ，１，ｇ２）＝ｅ（ｇ１，ＸＡ，２）であるかを確認する。正しくなければ、鍵生成処理からやり直す。正しければ、以下に進む。
【００７３】
（１−７−ｄ）第１主体は、以下の（１−７−ｄ−１）〜（１−７−ｄ−４）を行う。
（１−７−ｄ−１）第１主体は、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＤＡ，１ｃ（ｉ，０，０）Ｚ１ｃ（ｉ，１，０）ｘＡ，ＳＢ，２）ｅ（ＤＡ，１ｃ（ｉ，０，１）Ｚ１ｃ（ｉ，１，１）ｘＡ，ＸＢ，２）を計算する。
（１−７−ｄ−２）第１主体は、σｍ＋１＝ＸＢ，１ｘＡおよびσｍ＋２＝ＸＢ，２ｘＡを計算する。
（１−７−ｄ−３）第１主体は、σｍ＋３＝ＳＢ，１ｘＡおよびσｍ＋４＝ＳＢ，２ｘＡを計算する。
（１−７−ｄ−４）第１主体は、共有鍵Ｋ＝Ｈ（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，σｍ＋３，σｍ＋４，ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２，ＸＢ，１，ＸＢ，２，ＳＢ，１，ＳＢ，２）を計算する。
【００７４】
（１−７−ｅ）第２主体は、以下の（１−７−ｅ−１）〜（１−７−ｅ−４）を行う。
（１−７−ｅ−１）第２主体は、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＱＡ，１，Ｚ２ｃ（ｉ，０，０）ｓＢ＋ｃ（ｉ，０，１）ｘＢ）ｅ（ＸＡ，１，Ｚ２ｃ（ｉ，１，０）ｓＢ＋ｃ（ｉ，１，１）ｘＢ）を計算する。
（１−７−ｅ−２）第２主体は、σｍ＋１＝ＸＡ，１ｘＢおよびσｍ＋２＝ＸＡ，２ｘＢを計算する。
（１−７−ｅ−３）第２主体は、σｍ＋３＝ＸＡ，１ｓＢおよびσｍ＋４＝ＸＡ，２ｓＢを計算する。
（１−７−ｅ−４）第２主体は、共有鍵Ｋ＝Ｈ（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，σｍ＋３，σｍ＋４，ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２，ＸＢ，１，ＸＢ，２，ＳＢ，１，ＳＢ，２）を計算する。
【００７５】
ここでＱＡ，１＝ｇ１ｑ（Ａ，１）∈Ｇ１とすると、ｅの双線形より、両者が計算したσ１，・・・，σｍ，σｍ＋１，σｍ＋２には以下が成り立つ。
・ｉ＝１，・・・，ｍについてσｉ＝ｇＴｚｐｉ（ｑ（Ａ，１），ｓＢ，ｘＡ，ｘＢ）
・σｍ＋１＝ｇ１ｘＡｘＢおよびσｍ＋２＝ｇ２ｘＡｘＢ
・σｍ＋３＝ｇ１ｘＡｓＢおよびσｍ＋４＝ｇ２ｘＡｓＢ
従って両者の共通鍵Ｋは一致する。
【００７６】
《ＦＳＵ認証鍵交換方式（ｃｅｒｔ−ｉｄ−ＡＫＥ）をベースとした本形態の方式》
この実施例では、ｓｋ１＝（ＤＡ，１，ｘＡ）、ｐｋ１＝（ＱＡ，１，ＸＡ，１）、ｓｋ２＝（ｓＢ，ｘＢ）、ｐｋ２＝（ＳＢ，１，ＸＢ，１，ＸＢ，２）、β１＝（ＸＡ，１，ＸＡ，２）、β２＝（ＳＢ，１，ＳＢ，２，ＸＢ，１，ＸＢ，２）、λ１＝（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，σｍ＋３）、λ２＝（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，σｍ＋３）、Ｋ＝Ｈ（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，σｍ＋３，σｍ＋４，ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２，ＸＢ，１，ＸＢ，２，ＳＢ，１，ＳＢ，２）とし、第１実施形態の各処理を実行する。ただし、記憶部１１１１には、ｐｋ１＝（ＱＡ，１，ＸＡ，１）の他、ＩＤＡ，ＩＤＢ，ＸＡ，２が格納され、記憶部１２１１には、ｐｋ２＝（ＳＢ，１，ＸＢ，１，ＸＢ，２）の他、ＳＢ，２，ＩＤＡ，ＩＤＢが格納される。記憶部１１２１には、ｓｋ１＝（ＤＡ，１，ｘＡ）の他、Ｚ１，ＱＢ，２が格納され、記憶部１２２１には、ｓｋ２＝（ｓＢ，ｘＢ）の他、Ｚ２，ＱＡ，１が格納される。
【００７７】
ステップＳ１０００では、まず、端末装置１１１の鍵交換処理部１１１５が記憶部１１１１から（ＩＤＡ，ＸＡ，１，ＸＡ，２）を読み込み、通信部１１１６に送る。通信部１１１６は（ＩＤＡ，ＸＡ，１，ＸＡ，２）を端末装置１２１に送信する。（ＩＤＡ，ＸＡ，１，ＸＡ，２）は通信部１２１６で受信されて鍵交換処理部１２１５に送られ、記憶部１２１１に格納される（１−７−ａ）。端末装置１２１の鍵交換処理部１２１５が記憶部１２１１から（ＳＢ，１，ＳＢ，２，ＸＢ，１，ＸＢ，２）を読み込み、通信部１２１６に送る。通信部１２１６は（ＳＢ，１，ＳＢ，２，ＸＢ，１，ＸＢ，２）を端末装置１１１に送信する。（ＳＢ，１，ＳＢ，２，ＸＢ，１，ＸＢ，２）は通信部１１１６で受信されて鍵交換処理部１１１５に送られ、記憶部１１１１に格納される（１−７−ｂ）。鍵交換部１１１５は記憶部１１１１から読み込んだβ２＝（ＳＢ，１，ＳＢ，２，ＸＢ，１，ＸＢ，２）がｅ（ＳＢ，１，ｇ２）＝ｅ（ｇ１，ＳＢ，２）を満たすかを確認し、鍵交換部１２１５は記憶部１２１１から読み込んだβ１＝（ＸＡ，１，ＸＡ，２）がｅ（ＸＡ，１，ｇ２）＝ｅ（ｇ１，ＸＡ，２）を満たすかを確認する。正しくなければ、鍵生成からやり直す。正しければステップＳ１１０１，Ｓ１２０１以降の処理に進む（１−７−ｃ）。
【００７８】
ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＤＡ，１ｃ（ｉ，０，０）Ｚ１ｃ（ｉ，１，０）ｘＡ，ＳＢ，２）ｅ（ＤＡ，１ｃ（ｉ，０，１）Ｚ１ｃ（ｉ，１，１）ｘＡ，ＸＢ，２）を計算し（１−７−ｄ−１）、σｍ＋１＝ＸＢ，１ｘＡおよびσｍ＋２＝ＸＢ，２ｘＡを計算し（１−７−ｄ−２）、σｍ＋３＝ＳＢ，１ｘＡおよびσｍ＋４＝ＳＢ，２ｘＡを計算し、λ１を得る。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＱＡ，１，Ｚ２ｃ（ｉ，０，０）ｓＢ＋ｃ（ｉ，０，１）ｘＢ）ｅ（ＸＡ，１，Ｚ２ｃ（ｉ，１，０）ｓＢ＋ｃ（ｉ，１，１）ｘＢ）を計算し（１−７−ｅ−１）、σｍ＋１＝ＸＡ，１ｘＢおよびσｍ＋２＝ＸＡ，２ｘＢを計算し（１−７−ｅ−２）、σｍ＋３＝ＸＡ，１ｓＢおよびσｍ＋４＝ＸＡ，２ｓＢを計算し、λ２を得る。
【００７９】
ステップＳ１１１３では、鍵交換処理部１１１５が、λ１と記憶部１１１１に格納された情報とを用いて共通鍵Ｋを得て出力し、ステップＳ１２１３では、鍵交換処理部１２１５が、λ２と記憶部１２１１に格納された情報とを用いて共通鍵Ｋを得て出力する。
【００８０】
＜実施例１−７の変形例１＞
実施例１−７の変形例１として、ｓｋ１＝ＤＡ，１とし、ｐｋ１＝ＱＡ，１とし、ｓｋ２＝ｓＢとし、ｐｋ２＝ＳＢ，１とし、β１＝βｉ,Ａ＝ＱＡ，１ｃ（ｉ，０，０）ＸＡ，１ｃ（ｉ，１，０）またはβ’ｉ,Ａ＝ｅ(ＱＡ，１ｃ（ｉ，０，０）ＸＡ，１ｃ（ｉ，１，０），Ｚ２)とし、β２＝αｉ,Ｂ＝ＳＢ，２ｃ（ｉ，０，０）ＸＢ，２ｃ（ｉ，０，１）とし、λ１＝ｅ（ＤＡ，１,αｉ,Ｂ）とし、λ２＝ｅ（βｉ,Ａ,Ｚ２ｓＢ）またはλ２＝β’ｉ,ＡｓＢとし、Ｋ＝Ｈ（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，σｍ＋３，σｍ＋３，σｍ＋４，ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２，ＸＢ，１，ＸＢ，２，ＳＢ，１，ＳＢ，２）としてもよい。ただし、記憶部１１１１には、ｐｋ１＝ＱＡ，１の他、ＩＤＡ，ＩＤＢ，ＸＡ，１,ＸＡ，２,Ｚ２が格納され、記憶部１２１１には、ｐｋ２＝ＳＢ，１の他、ＳＢ，２，ＩＤＡ，ＩＤＢ，ＸＢ，１，ＸＢ，２が格納される。記憶部１１２１には、ｓｋ１＝ＤＡ，１が格納され、記憶部１２２１には、ｓｋ２＝ｓＢの他、Ｚ２が格納される。
【００８１】
ステップＳ１０００は実施例１−７と同じであり、その後、ステップＳ１１０１，Ｓ１２０１以降の処理に進む。ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてλ１＝ｅ（ＤＡ，１,αｉ,Ｂ）を計算し、λ１を得る。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてλ２＝ｅ（βｉ,Ａ,Ｚ２ｓＢ）またはλ２＝ｅ(ＱＡ，１ｃ（ｉ，０，０）ＸＡ，１ｃ（ｉ，１，０），Ｚ２)ｓＢを計算し、λ２を得る。
【００８２】
ステップＳ１１１３では、鍵交換処理部１１１５がλ１と記憶部１１１１に格納された情報とを用い、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＤＡ，１ｃ（ｉ，０，０）Ｚ１ｃ（ｉ，１，０）ｘＡ，ＳＢ，２）ｅ（ＤＡ，１ｃ（ｉ，０，１）Ｚ１ｃ（ｉ，１，１）ｘＡ，ＸＢ，２）＝λ１・ｅ（Ｚ１，ＳＢ，２ｃ（ｉ，１，０）ｘＡＸＢ，２ｃ（ｉ，１，１）ｘＡ）を計算し、共通鍵Ｋを得る。ステップＳ１２１３では、鍵交換処理部１２１５がλ２と記憶部１２１１に格納された情報とを用い、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＱＡ，１，Ｚ２ｃ（ｉ，０，０）ｓＢ＋ｃ（ｉ，０，１）ｘＢ）ｅ（ＸＡ，１，Ｚ２ｃ（ｉ，１，０）ｓＢ＋ｃ（ｉ，１，１）ｘＢ）＝λ２・ｅ（ＱＡ，１ｃ（ｉ，０，１）ＸＡ，２ｃ（ｉ，１，１），Ｚ２ｘＢ）を計算し、共通鍵Ｋを得る。
【００８３】
＜実施例１−７の変形例２＞
実施例１−７の変形例２として、ｓｋ１＝（ＤＡ，１，ｘＡ）とし、ｐｋ１＝（ＱＡ，１，ＸＡ，１）とし、ｓｋ２＝（ｓＢ，ｘＢ）とし、ｐｋ２＝（ＳＢ，１，ＸＢ，１，ＸＢ，２）とし、β１＝（β１’,β１”）とし、β１’をβｉ,Ａ＝ＱＡ，１ｃ（ｉ，０，０）ＸＡ，１ｃ（ｉ，１，０）またはβ’ｉ,Ａ＝ｅ(ＱＡ，１ｃ（ｉ，０，０）ＸＡ，１ｃ（ｉ，１，０），Ｚ２)とし、β１”をβ１,ｉ,Ａ＝ＱＡ，１ｃ（ｉ，０，１）ＸＡ，１ｃ（ｉ，１，１）またはβ２,ｉ,Ａ＝ｅ（ＱＡ，１ｃ（ｉ，０，１）ＸＡ，１ｃ（ｉ，１，１）,Ｚ２）とし、β２＝（β２’,β２”）とし、β２’＝αｉ,Ｂ＝ＳＢ，２ｃ（ｉ，０，０）ＸＢ，２ｃ（ｉ，０，１）とし、β２”をβｉ,Ｂ＝ＳＢ，２ｃ（ｉ，１，０）ＸＢ，２ｃ（ｉ，１，１）またはβ’ｉ,Ｂ＝ｅ（Ｚ１,ＳＢ，２ｃ（ｉ，１，０）ＸＢ，２ｃ（ｉ，１，１））とし、λ１＝（λ１ｉ’,λ１ｉ”）とし、λ１ｉ’＝ｅ（ＤＡ，１,αｉ,Ｂ）とし、λ１ｉ”をｅ（Ｚ１ｘＡ,βｉ,Ｂ）またはβ’ｉ,ＢｘＡとし、λ２＝（λ２ｉ’,λ２ｉ”）とし、λ２ｉ’をｅ（βｉ,Ａ,Ｚ２ｓＢ）またはβ’ｉ,ＡｓＢとし、λ２ｉ”をｅ（β１,ｉ,Ａ,Ｚ２ｘＢ）またはβ２,ｉ,ＡｘＢとし、Ｋ＝Ｈ（σ１，・・・，σｍ，σｍ＋１，σｍ＋２，σｍ＋３，σｍ＋４，ＩＤＡ，ＩＤＢ，ＸＡ，１，ＸＡ，２，ＸＢ，１，ＸＢ，２，ＳＢ，１，ＳＢ，２）としてもよい。ただし、記憶部１１１１には、ｐｋ１＝ＱＡ，１の他、ＩＤＡ，ＩＤＢ，ＸＡ，１,ＸＡ，２,が格納され、記憶部１２１１には、ｐｋ２＝（ＳＢ，１，ＸＢ，１，ＸＢ，２）の他、ＳＢ，２，ＩＤＡ，ＩＤＢが格納される。記憶部１１２１には、ｓｋ１＝（ＤＡ，１，ｘＡ）の他、Ｚ１が格納され、記憶部１２２１には、ｓｋ２＝（ｓＢ，ｘＢ）の他、Ｚ２が格納される。
【００８４】
ステップＳ１０００は実施例１−７と同じであり、その後、ステップＳ１１０１，Ｓ１２０１以降の処理に進む。ステップＳ１１１０では、代理演算部１１２６がβ２および記憶部１１２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてλ１＝（λ１ｉ’,λ１ｉ”）を計算し、λ１を得る。ステップＳ１２１０では、代理演算部１２２６がβ１および記憶部１２２１から読み込んだ情報を用い、ｉ＝１，・・・，ｍについてλ２＝（λ２ｉ’,λ２ｉ”）を計算し、λ２を得る。
【００８５】
ステップＳ１１１３では、鍵交換処理部１１１５がλ１と記憶部１１１１に格納された情報とを用い、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＤＡ，１ｃ（ｉ，０，０）Ｚ１ｃ（ｉ，１，０）ｘＡ，ＳＢ，２）ｅ（ＤＡ，１ｃ（ｉ，０，１）Ｚ１ｃ（ｉ，１，１）ｘＡ，ＸＢ，２）＝λ１ｉ’λ１ｉ”を計算し、共通鍵Ｋを得る。ステップＳ１２１３では、鍵交換処理部１２１５がλ２と記憶部１２１１に格納された情報とを用い、ｉ＝１，・・・，ｍについてσｉ＝ｅ（ＱＡ，１，Ｚ２ｃ（ｉ，０，０）ｓＢ＋ｃ（ｉ，０，１）ｘＢ）ｅ（ＸＡ，１，Ｚ２ｃ（ｉ，１，０）ｓＢ＋ｃ（ｉ，１，１）ｘＢ）＝λ２ｉ’λ２ｉ”を計算し、共通鍵Ｋを得る。
【００８６】
＜第１実施形態の特徴＞
本形態では、絶対数の多い個々の端末装置１１１，１２１やそれらのユーザーごとに認証処理の管理を行うのではなく、絶対数の少ない回線ごとに認証処理の管理を行う。そのため、認証処理や管理のコストを削減できる。
【００８７】
本形態では、端末装置１１１，１２１やそれらのユーザーごとに個々に登録が行われるのではなく、鍵装置１１２，１２２が鍵交換のための処理を行う回線ごとに登録が行われる。そのため、個々の端末装置１１１，１２１やそれらのユーザーを登録することなく、登録済みの回線を正当に使用する権限がある複数の端末装置１１１，１２１に対し、鍵装置１１２，１２２での処理を許可することができ、登録手続きを簡易化できる。また、回線に対して鍵交換処理権限を与えるため、本システム専用の設定を行う前の端末装置１１１，１２１に対しても鍵交換処理権限を与えることができる。すなわち、本形態の鍵交換処理機能を実行するためのプログラムを端末装置１１１，１２１にインストールする前であっても、その端末装置１１１，１２１が使用する回線に対応する回線情報を特定することはでき、その回線に対応する「登録情報」を含むリストを鍵装置１１２，１２２に格納することができる。また「登録情報」および「回線対応情報」として、公開された固有情報または当該固有情報に対して一義的に決まる情報を用いた場合、非公開の情報を用いることなく、上述の管理を実現できる。
【００８８】
また、本形態では端末装置１１１，１２１の正当性が公衆回線内の回線認証によって担保される。そのため、端末装置１１１，１２１やそのユーザーが署名生成のための特別な認証処理を別途行う必要がなく、それに必要な秘密情報を別途保持する必要もない。
【００８９】
また、鍵装置１１２や記憶部１２２にｓｋ−Ｌｉｓｔ１やｓｋ−Ｌｉｓｔ２を格納し、公開鍵ｐｋ１や公開鍵ｐｋ２を用いて、鍵交換処理に用いる秘密鍵ｓｋ１やｓｋ２を特定する構成の場合、複数種類の秘密鍵ｓｋ１やｓｋ２についての鍵交換処理を鍵装置１１２，１２２に委託できる。
【００９０】
なお、回線対応情報ｘ１に対応する秘密鍵ｓｋ１を用いて鍵対応情報λ１が生成されてもよいし、回線対応情報ｘ２に対応する秘密鍵ｓｋ２を用いて鍵対応情報λ２が生成されてもよい。これらの変形例では、例えば、秘密鍵ｓｋ１（ｓｋ２）とそれらに対応付けられた公開鍵ｐｋ１（ｐｋ２）とを含むリストｓｋ−Ｌｉｓｔ１（ｓｋ−Ｌｉｓｔ２）に代え、秘密鍵ｓｋ１（ｓｋ２）とそれらに対応付けられた「登録情報」とを含むリストｓｋ−Ｌｉｓｔ１（ｓｋ−Ｌｉｓｔ２）が用いられる。回線対応情報ｘ１（ｘ２）がリストＬｉｓｔ１（Ｌｉｓｔ２）の何れかの「登録情報」に対応する場合（ステップＳ１１０８，Ｓ１２０８）、代理演算部１１２６（１２２６）は、回線対応情報ｘ１（ｘ２）を用いて記憶部１１２１（１２２１）に格納されたｓｋ−Ｌｉｓｔ１（ｓｋ−Ｌｉｓｔ２）を検索し、回線対応情報ｘ１（ｘ２）に対応する秘密鍵ｓｋ１（ｓｋ２）を抽出し、鍵対応情報λ１（λ２）を生成する。あるいは、ｓｋ−Ｌｉｓｔ１（ｓｋ−Ｌｉｓｔ２）を省略し、Ｌｉｓｔ１（Ｌｉｓｔ２）が秘密鍵ｓｋ１（ｓｋ２）とそれらに対応付けられた「登録情報」とを含んでもよい。この構成では、回線対応情報ｘ１（ｘ２）がリストＬｉｓｔ１（Ｌｉｓｔ２）の何れかの「登録情報」に対応する場合（ステップＳ１１０８，Ｓ１２０８）、代理演算部１１２６（１２２６）は、その「登録情報」に対応付けられた鍵ｓｋ１（ｓｋ２）を抽出し、鍵対応情報λ１（λ２）を生成する。
【００９１】
また第１実施形態では、「秘密鍵を特定するための情報」として公開鍵ｐｋ１（ｐｋ２）を用いる例を示したが、鍵ＩＤその他の情報を「秘密鍵を特定するための情報」としてもよい。また、ステップＳ１１０１（Ｓ１２０１）で公開情報β２（β１）を含まない「要求情報」を送信し、ステップＳ１１０８（Ｓ１２０８）で回線対応情報ｘ１（ｘ２）がリストＬｉｓｔ１（Ｌｉｓｔ２）の何れかの「登録情報」に対応すると判定されてから、端末装置１１１（１２１）から鍵装置１１２（１２２）に公開情報β２（β１）を含む「要求情報」を送信し、ステップＳ１１１０（Ｓ１２１０）以降の処理が実行されてもよい。
【００９２】
第１実施形態では、鍵装置１１２，１２２に秘密鍵ｓｋ１，ｓｋ２を格納し、端末装置１１１，１２１の双方が鍵装置１１２，１２２に鍵交換処理の一部の処理を委託した。しかしながら、端末装置１２１が自ら秘密鍵ｓｋ２格納し、鍵装置１２２を用いることなく、第１実施形態で説明した端末装置１１１との間で鍵交換処理を実行してもよい。逆に、端末装置１１１が自ら秘密鍵ｓｋ１格納し、鍵装置１１２を用いることなく、第１実施形態で説明した端末装置１２１との間で鍵交換処理を実行してもよい。
【００９３】
［第２実施形態］
次に第２実施形態を説明する。第２実施形態は第１実施形態の変形例であり、自己訂正技術を用い、各端末装置が各鍵装置から鍵対応情報を得て鍵交換を行うものである。本形態の「公開情報に対応する情報」は、鍵交換のために他の端末装置から得た「公開情報」の撹乱情報であり、「鍵対応情報」は、「公開情報」と「秘密鍵」とを用いて得られる共有情報を自己訂正処理によって得るための情報である。自己訂正技術とは、必ずしも正しい計算結果を出力するとは限らない計算機やシステムを用いて常に正しい計算を行う（正しい計算結果を出力する計算機を用いた場合に正しい計算結果を出力し、必ずしも正しい結果を出力するとは限らない計算機を用いた場合に、正しい計算結果を得るか、または計算できない旨の結果を得る）技術である。自己訂正技術自体は公知技術であり、例えば、参考文献４（国際公開ＷＯ／２０１２／０５７１３４号公報）、参考文献５（国際公開ＷＯ／２０１１／０８６９９２号公報）、および参考文献６（国際公開ＷＯ／２０１２／１２１１５２号公報）等に開示されている。以下では、第１実施形態との相違点を中心に説明し、既に説明した事項については同じ参照番号を流用して説明を簡略化する。
【００９４】
本形態の構成を説明する。図１に例示するように、本形態の鍵交換システム２は、端末装置２１１，２２１（第１端末装置，第２端末装置）と鍵装置２１２，２２２（第１鍵装置，第２鍵装置）とを有する。端末装置２１１と鍵装置２１２とは、回線認証機能および回線情報通知機能を備える公衆回線を通じて通信可能に構成されている。同様に、端末装置２２１と鍵装置２２２とは、回線認証機能および回線情報通知機能を備える公衆回線を通じて通信可能に構成されている。
【００９５】
図１に例示するように、本形態の端末装置２１１は、記憶部１１１１と出力部２１１３と入力部２１１４と鍵交換処理部２１１５と通信部１１１６を有し、端末装置２２１は、記憶部１２１１と出力部２２１３と入力部２２１４と鍵交換処理部２２１５と通信部１２１６を有する。本形態の鍵装置１１２は、記憶部１１２１，１１２２と、入力部２１２３と、出力部２１２４と、判定部１１２５と、代理演算部２１２６とを有し、鍵装置２２２は、記憶部１２２１，１２２２と、入力部１２２３と、出力部１２２４と、判定部１２２５と、代理演算部２２２６とを有する。各装置は、例えば、前述したコンピュータに所定のプログラムが読み込まれることで構成されてもよいし、電子回路を用いて一部またはすべての処理部が構成されてもよい。
【００９６】
＜事前処理＞
第１実施形態と同じである。
【００９７】
＜鍵交換処理＞
図４および図５を用いて本形態の鍵交換処理を説明する。本形態では端末装置２１１と端末装置２２１との間で鍵交換を行い、その処理の一部を、鍵装置２１２，２２２が自己訂正技術を用いて代行する。
【００９８】
まず、第１実施形態で説明したステップＳ１０００の処理が実行される。
端末装置２１１の鍵交換処理部２１１５は、「鍵処理要求」を出力部２１１３に送る。鍵装置２１２の記憶部１１２１にｓｋ−Ｌｉｓｔ１が格納されている場合、鍵交換処理部１１１５は、さらに記憶部１１１１から読み込んだ公開鍵ｐｋ１（秘密鍵ｓｋ１を特定するための情報）を出力部２１１３に送る。出力部２１１３は、鍵装置２１２を宛先とし、公衆回線の所定の回線（使用回線）に対して「鍵処理要求」を含む「要求情報」を出力する。ただし、記憶部１１２１にｓｋ−Ｌｉｓｔ１が格納されている場合、「要求情報」はさらに公開鍵ｐｋ１を含む（鍵交換処理要求：ステップＳ２１０１）。その後、第１実施形態で説明したステップＳ１１０２〜Ｓ１１０３の処理に進む。ステップＳ１１０３で回線認証が成功であった場合、「要求情報」が鍵装置２１２に送信され、さらに回線情報通知機能を提供する通知装置（図示せず）が、回線情報ｄｘ１に対応する回線対応情報ｘ１を鍵装置２１２に送信する（ステップＳ２１０５）。回線対応情報ｘ１、および「鍵処理要求」を含む「要求情報」は、鍵装置２１２の入力部２１２３に入力される（受け付けられる）。入力部２１２３に入力される回線対応情報ｘ１は、回線認証に成功した回線（使用回線）に対応する情報である。回線対応情報ｘ１は判定部１１２５に送られ、「要求情報」は代理演算部２１２６に送られる（ステップＳ２１０６）。その後、第１実施形態で説明したステップＳ１１０７〜Ｓ１１０９の処理に進む。ステップＳ１１０８で、回線対応情報ｘ１がリストＬｉｓｔ１の何れかの「登録情報」に対応すると判定された場合、端末装置２１１の鍵交換処理部２１１５と鍵装置２１２の代理演算部２１２６とが自己訂正処理を行い（ステップＳ２１１０）、その結果を用い、鍵交換処理部２１１５が共通鍵Ｋを得る（ステップＳ２１１３）。この詳細は後述する。
【００９９】
同様に、端末装置２２１の鍵交換処理部２２１５は、「鍵処理要求」を出力部２２１３に送る。鍵装置２２２の記憶部１１２１にｓｋ−Ｌｉｓｔ２が格納されている場合、鍵交換処理部１１１５は、さらに記憶部１１１１から読み込んだ公開鍵ｐｋ２（秘密鍵ｓｋ２を特定するための情報）を出力部２２１３に送る。出力部２２１３は、鍵装置２２２を宛先とし、公衆回線の所定の回線（使用回線）に対して「鍵処理要求」を含む「要求情報」を出力する。ただし、記憶部１１２１にｓｋ−Ｌｉｓｔ２が格納されている場合、「要求情報」はさらに公開鍵ｐｋ２を含む（鍵交換処理要求：ステップＳ２２０１）。その後、第１実施形態で説明したステップＳ１２０２〜Ｓ１２０３の処理に進む。ステップＳ１２０３で回線認証が成功であった場合、「要求情報」が鍵装置２２２に送信され、さらに回線情報通知機能を提供する通知装置（図示せず）が、回線情報ｄｘ１に対応する回線対応情報ｘ１を鍵装置２２２に送信する（ステップＳ２２０５）。回線対応情報ｘ１、および「鍵処理要求」を含む「要求情報」は、鍵装置２２２の入力部２２２３に入力される（受け付けられる）。入力部２２２３に入力される回線対応情報ｘ１は、回線認証に成功した回線（使用回線）に対応する情報である。回線対応情報ｘ１は判定部１１２５に送られ、「要求情報」は代理演算部２２２６に送られる（ステップＳ２２０６）。その後、第１実施形態で説明したステップＳ１２０７〜Ｓ１２０９の処理に進む。ステップＳ１２０８で、回線対応情報ｘ１がリストＬｉｓｔ２の何れかの「登録情報」に対応すると判定された場合、端末装置２２１の鍵交換処理部２２１５と鍵装置２２２の代理演算部２２２６とが自己訂正処理を行い（ステップＳ２２１０）、その結果を用い、鍵交換処理部２２１５が共通鍵Ｋを得る（ステップＳ２２１３）。この詳細は後述する。
【０１００】
≪ステップＳ２１１０の自己訂正処理およびステップＳ２１１３の処理≫
ステップＳ２１１０の自己訂正処理では、まず、鍵交換処理部２１１５が鍵交換のために得た公開情報β２の撹乱情報（公開情報に対応する情報）を出力部２１１３に送る。出力部２１１３は、公開情報β２の撹乱情報ｄβ２を上述の使用回線に出力する（ステップＳＣ−１）。公開情報β２の撹乱情報ｄβ２は鍵装置２１２の入力部２１２３に入力され、代理演算部２１２６に送られる。代理演算部２１２６は、少なくとも公開情報β２の撹乱情報ｄβ２と記憶部１１２１から読み込んだ秘密鍵ｓｋ１とを用い、共有情報Ω１を自己訂正処理によって得るための鍵対応情報λ１を得て出力する。鍵対応情報λ１は出力部２１２４から上述の使用回線に出力される（ステップＳＣ−２）。鍵対応情報λ１は、端末装置２１１の入力部２１１４に入力され、鍵交換処理部２１１５に送られる。鍵交換処理部２１１５は、鍵対応情報λ１から共有情報Ω１を得、得られた共有情報Ω１を用いて共通鍵Ｋを得て出力する（ステップＳＣ−３）。鍵交換処理部２１１５は、鍵対応情報λ１から共有情報Ω１が得られない場合にはエラーを出力する。あるいは、鍵対応情報λ１から共有情報Ω１が得られない場合、所定の回数を上限として、鍵対応情報λ１から共有情報Ω１が得られるまで上述のステップＳＣ−１，２の処理が繰り返されてもよい。この場合、鍵交換処理部２１１５は、鍵対応情報λ１から共有情報Ω１を得た場合に上述のステップＳＣ−３を実行し、所定の回数だけ上述のステップＳＣ−１，２の処理を繰り返しても共有情報Ω１が得られない場合にエラーを出力する。
【０１０１】
例えば、Ｇ，Ｈが群、公開情報β２が群Ｈの元、ｆが秘密鍵ｓｋ１を用いて公開情報β２に対応する共有情報Ω１＝ｆ（β２）∈Ｇを得るための関数、Ｘ１，Ｘ２が群Ｇに値を持つ確率変数、ｘ１が確率変数Ｘ１の実現値、ｘ２が確率変数Ｘ２の実現値、ａ，ｂが互いに素であるランダムな自然数である。ａ，ｂの一方が１などの定数であってもよい。この場合、公開情報β２の撹乱情報ｄβ２は、公開情報β２に対応する群Ｈの元であるτ１および／またはτ２であり、鍵対応情報λ１はｚ１および／またはｚ２である。ただし、ｚ１＝ｆ（τ１）あるいはｚ１≠ｆ（τ１）であり、ｚ２＝ｆ（τ２）あるいはｚ２≠ｆ（τ２）である。ｚ１＝ｆ（τ１）である場合もあればｚ１＝ｆ（τ１）でない場合もあり、ｚ２＝ｆ（τ２）である場合もあればｚ２＝ｆ（τ２）でない場合もある。すなわち、代理演算部２１２６は、或る確率より大きな確率でｆ（τ１）を正しく計算し、得られた計算結果をｚ１とし、或る確率より大きな確率でｆ（τ２）を正しく計算し、得られた計算結果をｚ２とする。なお、「或る確率」は１００％未満の確率である。「或る確率」の例は無視することができない確率であり、「無視することができない確率」の例は、セキュリティパラメータκについての広義単調増加関数である多項式を多項式ψ（κ）とした場合の１／ψ（κ）以上の確率である。すなわち、代理演算部２１２６は、意図的又は意図的ではない誤差を含んだ計算結果を出力する。ステップＳＣ−３において、鍵交換処理部２１１５は、ｕａ＝ｖｂを満たすｕ＝ｆ（χ）ｂｘ1およびｖ＝ｆ（χ）ａｘ2に対応するΩ１＝ｕｂ’ｖａ’を共有情報として得、得られた共有情報Ω１を用いて共通鍵Ｋを得て出力する。ただし、ａ’，ｂ’はａ’ａ＋ｂ’ｂ＝１を満たす整数である。ｕａ＝ｖｂを満たすｚ１および／またはｚ２が得られていない場合、鍵交換処理部２１１５は、共有情報Ω１を得ることができない旨のエラー情報を出力する。あるいは、ｕａ＝ｖｂを満たすｚ１および／またはｚ２が得られていない場合、鍵交換処理部２１１５が新たに生成した撹乱情報ｄβ２を出力し、出力部２１１３が撹乱情報ｄβ２を鍵装置２１２に送信し、代理演算部２１２６が鍵対応情報λ１を計算し、出力部２１２４が鍵対応情報λ１を端末装置２１１に送信し、鍵交換処理部２１１５がｕａ＝ｖｂを満たすか否かの判定を行ってもよい。ここで、ｕａ＝ｖｂを満たす場合にはΩ１＝ｕｂ’ｖａ’を共有情報として得、得られた共有情報Ω１を用いて共通鍵Ｋを得て出力する。この処理を所定回数繰り返してもｕａ＝ｖｂを満たすｚ１および／またはｚ２が得られていない場合に、鍵交換処理部２１１５が、共有情報Ω１を得ることができない旨のエラー情報を出力してもよい。
【０１０２】
≪τ１，τ２、ｕ，ｖの具体例１≫
例えば、Ｇ，Ｈが群、ｈ１，ｈ２が単位元ではない群Ｈの元（例えば、生成元）、ｒ１，ｒ２が０以上のランダムな自然数、ｆが秘密鍵ｓｋ１を用いて公開情報β２に対応する共有情報Ω１＝ｆ（β２）∈Ｇを得るための準同型性関数、τ１＝（ｈ１−ｒ１，ｈ１ｒ１β２ｂ）、τ２＝（ｈ２−ｒ２，ｈ２ｒ２β２ａ）、ｕ＝ｆ（τ１）＝ｆ（ｈ１−ｒ１）ｆ（ｈ１ｒ１β２ｂ）、ｖ＝ｆ（τ２）＝ｆ（ｈ２−ｒ２）ｆ（ｈ２ｒ２β２ａ）であってもよい。
【０１０３】
≪τ１，τ２、ｕ，ｖの具体例２≫
例えば、Ｇ，Ｈが巡回群、μｈが群Ｈの生成元、ν＝ｆ（μh）、ｆが秘密鍵ｓｋ１を用いて公開情報β２に対応する共有情報Ω１＝ｆ（β２）∈Ｇを得るための準同型性関数、ｒ１，ｒ２が０以上のランダムな自然数、τ１＝μｈｒ１β２ｂ、τ２＝μｈｒ２β２ａ、ｕ＝ｚ１ν−ｒ１、ｖ＝ｚ２ν−ｒ２であってもよい。
【０１０４】
≪τ１，τ２、ｕ，ｖの具体例３≫
例えば、Ｇを巡回群、群Ｈが群Ｇの直積群Ｇ×Ｇ、β２＝（ｃ１，ｃ２）∈Ｈ、ｆが秘密鍵ｓｋ１を用いて公開情報β２に対応する共有情報Ω１＝ｆ（β２）∈Ｇを得るための準同型性関数、（Ｖ，Ｗ）が群Ｈの元、ｆ（Ｖ，Ｗ）＝Ｙ、ｒ４〜ｒ７を０以上の自然数の乱数、τ１＝（ｃ２ｂＷｒ４，ｃ１ｂＶｒ４μｇｒ５）、τ２＝（ｃ２ａＷｒ６，ｃ１ａＶｒ６μｇｒ７）、ｕ＝ｚ１Ｙ−ｒ４μｇ−ｒ５、ｖ＝ｚ２Ｙ−ｒ６μｇ−ｒ７であってもよい。
【０１０５】
図５を用い、τ１，τ２、ｕ，ｖの具体例１の場合の自己訂正処理を例示する。
まず、端末装置２１１の鍵交換処理部２１１５が上述のａ，ｂ，ａ’，ｂ’を選択し（ステップＳ２１１１ａ）し、ｔ＝１に設定する（ステップＳ２１１１ｂ）。鍵交換処理部２１１５は、τ１＝（ｈ１−ｒ１，ｈ１ｒ１β２ｂ）、τ２＝（ｈ２−ｒ２，ｈ２ｒ２β２ａ）を上述のように鍵装置２１２の代理演算部２１２６に送る（ステップＳ２１１１ｃ）。代理演算部２１２６は、ｈ１，ｈ２を定め、ｕ＝ｆ（τ１）＝ｆ（ｈ１−ｒ１）ｆ（ｈ１ｒ１β２ｂ）およびｖ＝ｆ（τ２）＝ｆ（ｈ２−ｒ２）ｆ（ｈ２ｒ２β２ａ）を得（ステップＳ２１１２ａ）、これらを鍵交換処理部２１１５に送る（ステップＳ２１１２ｂ）。鍵交換処理部２１１５は、ｕａ＝ｖｂを満たすかを判定する（ステップＳ２１１１ｄ）。ここで、ｕａ＝ｖｂを満たす場合、鍵交換処理部２１１５は、共有情報Ω１＝ｕｂ’ｖａ’を用いて共通鍵Ｋを得て出力する（ステップＳ２１１１ｈ）。一方、ｕａ＝ｖｂを満たさない場合、鍵交換処理部２１１５はｔ＝Ｔｍａｘであるかを判定する。なお、Ｔｍａｘは所定の正の整数である。ｔ＝Ｔｍａｘである場合、鍵交換処理部２１１５はエラー「⊥」を出力して処理を終える（ステップＳ２１１１ｇ）。ｔ＝Ｔｍａｘでない場合、鍵交換処理部２１１５はｔ＋１を新たなｔとし（ステップＳ２１１１ｆ）、処理をステップＳ２１１１ａに戻す。
【０１０６】
≪ステップＳ２２１０の自己訂正処理およびステップＳ２２１３の処理≫
ステップＳ２２１０の自己訂正処理は、「端末装置２１１、鍵交換処理部２１１５、鍵装置２１２、代理演算部２１２６、出力部２１１３、入力部２１１４、出力部２１２４、入力部２１２３、記憶部１１２１、公開情報β２、撹乱情報ｄβ２、鍵対応情報λ１、共有情報Ω１、秘密鍵ｓｋ１」が「端末装置２２１、鍵交換処理部２２１５、鍵装置２２２、代理演算部２２２６、出力部２２１３、入力部２２１４、出力部２２２４、入力部２２２３、記憶部１２２１、公開情報β１、撹乱情報ｄβ１、鍵対応情報λ２、共有情報Ω２、秘密鍵ｓｋ２」に置換される以外、ステップＳ２１１０の自己訂正処理と同じでよい。
【０１０７】
以下、ベースとなる鍵交換方式を具体化して自己訂正処理を例示する。各例でも「要求情報」からβ１やβ２が省かれる。
＜実施例１−５の変形例１の場合＞
前述した実施例１−５の変形例１に自己訂正処理を導入する場合、鍵交換処理部２１１５は、代理演算部２１２６との間で、β２＝Ｐｉ,Ｂかつｆ（χ）＝ｅ（ＤＡ，１，χ）とした自己訂正処理を行ってΩ１＝ζＡ,ｉ＝ｅ（ＤＡ，１，Ｐｉ,Ｂ）を得、共通鍵Ｋを計算する。また、鍵交換処理部２１１６は、代理演算部２２２６との間で、β１＝Ｐｉ,Ａかつｆ（χ）＝ｅ（χ，ＤＢ，２）とした自己訂正処理を行ってΩ２＝ζＢ,ｉ＝ｅ（Ｐｉ,Ａ，ＤＢ，２）を得、共通鍵Ｋを計算する。
【０１０８】
＜実施例１−５の変形例２の場合＞
前述した実施例１−５の変形例２に自己訂正処理を導入する場合、鍵交換処理部２１１５は、代理演算部２１２６との間で、β２＝Ｐｉ,Ｂかつｆ（χ）＝ｅ（ＤＡ，１，χ）とした自己訂正処理を行ってλ１＝ζＡ,ｉ＝ｅ（ＤＡ，１，Ｐｉ,Ｂ）を得、さらにβ２＝αｉ，Ｂ（式（３））かつｆ（χ）＝χｘＡとした自己訂正処理を行ってλ１＝αｉ，ＢｘＡを得、共通鍵Ｋを計算する。また、交換処理部２２１５は、代理演算部２２２６との間で、β１＝Ｐｉ,Ａかつｆ（χ）＝ｅ（χ，ＤＢ，２）とした自己訂正処理を行ってλ２＝ζＢ,ｉ＝ｅ（Ｐｉ,Ａ，ＤＢ，２）を得、さらにβ１＝αｉ，Ａ（式（２））かつｆ（χ）＝χｘＢとした自己訂正処理を行ってλ２＝αｉ，ＡｘＢを得、共通鍵Ｋを計算する。
【０１０９】
＜実施例１−５の変形例３の場合＞
前述した実施例１−５の変形例３に自己訂正処理を導入する場合、鍵交換処理部２１１５は、代理演算部２１２６との間で、β２＝Ｐｉ,Ｂかつｆ（χ）＝ｅ（ＤＡ，１，χ）とした自己訂正処理を行ってλ１＝ζＡ,ｉ＝ｅ（ＤＡ，１，Ｐｉ,Ｂ）を得、β２＝Ｐ’ｉ,Ｂかつｆ（χ）＝ｅ（Ｚ１ｘＡ，χ）とした自己訂正処理を行ってλ１＝ζ’Ａ,ｉ＝ｅ（Ｚ１ｘＡ，Ｐ’ｉ,Ｂ）を得、β２＝α’ｉ，Ｂ（式（５））かつｆ（χ）＝χｘＡとした自己訂正処理を行ってλ１＝α’ｉ，ＢｘＡを得、β２＝Ｐ’ｉ,Ｂかつｆ（χ）＝ｅ（Ｚ１ｘＡ，χ）とした自己訂正処理を行ってλ１＝ζ’Ａ,ｉ＝ｅ（Ｚ１ｘＡ，Ｐ’ｉ,Ｂ）を得、共通鍵Ｋを計算する。また、交換処理部２２１５は、代理演算部２２２６との間で、β１＝Ｐｉ,Ａかつｆ（χ）＝ｅ（χ，ＤＢ，２）とした自己訂正処理を行ってλ２＝ζＢ,ｉ＝ｅ（Ｐｉ,Ａ，ＤＢ，２）を得、β１＝Ｐ’ｉ,Ａかつｆ（χ）＝ｅ（χ，Ｚ２ｘＢ）とした自己訂正処理を行ってλ２＝ζ’Ｂ,ｉ＝ｅ（Ｐ’ｉ,Ａ，Ｚ２ｘＢ）を得、β１＝α’ｉ，Ａ（式（４））かつｆ（χ）＝χｘＢとした自己訂正処理を行ってλ２＝α’ｉ，ＡｘＢを得、共通鍵Ｋを計算する。
【０１１０】
＜実施例１−６の変形例１の場合＞
前述した実施例１−６の変形例１に自己訂正処理を導入する場合、鍵交換処理部２１１５は、代理演算部２１２６との間で、β２＝αＢ，ｉかつｆ（χ）＝χｘＡとした自己訂正処理を行ってλ１＝αＢ，ｉｘＡを得、共通鍵Ｋを計算する。交換処理部２２１５は、代理演算部２２２６との間で、β１＝αＡ，ｉかつｆ（χ）＝χｘＢとした自己訂正処理を行ってλ２＝αＡ，ｉｘＢを得、共通鍵Ｋを計算する。
【０１１１】
＜実施例１−６の変形例２の場合＞
前述した実施例１−６の変形例２に自己訂正処理を導入する場合、鍵交換処理部２１１５は、代理演算部２１２６との間で、β２＝αＢ，ｉかつｆ（χ）＝χｘＡとした自己訂正処理を行ってλ１＝αＢ，ｉｘＡを得、β２＝βＢ，ｉかつｆ（χ）＝χｓＡとした自己訂正処理を行ってλ１＝βＢ，ｉｓＡを得、共通鍵Ｋを計算する。交換処理部２２１５は、代理演算部２２２６との間で、β１＝αＡ，ｉかつｆ（χ）＝χｘＢとした自己訂正処理を行ってλ２＝αＡ，ｉｘＢを得、β１＝βＡ，ｉかつｆ（χ）＝χｓＢとした自己訂正処理を行ってλ２＝βＡ，ｉｓＢを得、共通鍵Ｋを計算する。
【０１１２】
＜実施例１−７の変形例１の場合＞
前述した実施例１−７の変形例１に自己訂正処理を導入する場合、鍵交換処理部２１１５は、代理演算部２１２６との間で、β２＝αｉ,Ｂかつｆ（χ）＝ｅ（ＤＡ，１,χ）とした自己訂正処理を行ってλ１＝ｅ（ＤＡ，１,αｉ,Ｂ）を得、共通鍵Ｋを計算する。交換処理部２２１５は、代理演算部２２２６との間で、β１＝βｉ,Ａかつｆ（χ）＝ｅ（χ,Ｚ２ｓＢ）またはβ１＝β’ｉ,Ａかつｆ（χ）＝χｓＢとした自己訂正処理を行ってλ２＝ｅ（βｉ,Ａ,Ｚ２ｓＢ）またはλ２＝β’ｉ,ＡｓＢを得、共通鍵Ｋを計算する。
【０１１３】
＜実施例１−７の変形例２の場合＞
前述した実施例１−７の変形例２に自己訂正処理を導入する場合、鍵交換処理部２１１５は、代理演算部２１２６との間で、β２＝αｉ,Ｂかつｆ（χ）＝ｅ（ＤＡ，１,χ）とした自己訂正処理を行ってλ１＝ｅ（ＤＡ，１,αｉ,Ｂ）を得、かつ、β２＝βｉ,Ｂかつｆ（χ）＝ｅ（Ｚ１ｘＡ,χ）とした自己訂正処理を行ってλ１＝ｅ（Ｚ１ｘＡ,βｉ,Ｂ）を得るかβ２＝β’ｉ,Ｂかつｆ（χ）＝χｘＡとした自己訂正処理を行ってλ１＝β’ｉ,ＢｘＡを得、共通鍵Ｋを計算する。交換処理部２２１５は、代理演算部２２２６との間で、β１＝βｉ,Ａかつｆ（χ）＝ｅ（χ,Ｚ２ｓＢ）とした自己訂正処理を行ってλ２＝ｅ（βｉ,Ａ,Ｚ２ｓＢ）を得るかβ１＝β’ｉ,ＡかつχｓＢとした自己訂正処理を行ってλ２＝β’ｉ,ＡｓＢを得、かつ、β１＝β１,ｉ,Ａかつｆ（χ）＝ｅ（χ,Ｚ２ｘＢ）とした自己訂正処理を行ってλ２＝ｅ（β１,ｉ,Ａ,Ｚ２ｘＢ）を得るかβ１＝β２,ｉ,Ａかつｆ（χ）＝χｘＢとした自己訂正処理を行ってλ２＝β２,ｉ,ＡｘＢを得、共通鍵Ｋを計算する。
【０１１４】
＜第２実施形態の特徴＞
本形態でも第１実施形態と同様な効果を得ることができる。さらに、本形態では自己訂正技術を用いるため、鍵装置２１２,２２２が必ずしも正しい答えを返すとは限らない場合でも、端末装置２１１,２２１間で不正な共通鍵を共有してしまうことを避けることができる。なお、第２実施形態では、鍵装置２１２，２２２に秘密鍵ｓｋ１，ｓｋ２を格納し、端末装置２１１，２２１の双方が自己訂正技術によって鍵装置２１２，２２２に鍵交換処理の一部の処理を委託した。しかしながら、端末装置２２１が自ら秘密鍵ｓｋ２格納し、鍵装置２２２を用いることなく、第２実施形態で説明した端末装置２１１との間で鍵交換処理を実行してもよい。逆に、端末装置２１１が自ら秘密鍵ｓｋ１格納し、鍵装置２１２を用いることなく、第２実施形態で説明した端末装置２２１との間で鍵交換処理を実行してもよい。
【０１１５】
［その他］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１６】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１１７】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１１９】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０１２０】
１，２  鍵交換システム
１１１，１２１，２１１，２２１  端末装置
１１２，１２２，２１２，２２２  鍵装置
【図１】
2016129301.tif 000008
【図２】
2016129301.tif 000009
【図３】
2016129301.tif 000010
【図４】
2016129301.tif 000011
【図５】
2016129301.tif 000012