(57)【特許請求の範囲】
【請求項１】
センタと通信可能に接続された２つのエンティティ夫々を特定する特定情報ＩＤa ，ＩＤb が公開されており、エンティティ夫々の特定情報を楕円曲線上の点に変換するための関数ｆ（）及び前記楕円曲線上で定義されるベイユペアリングのアルゴリズム＜，＞が公開されており、これら公開されている特定情報、関数及びアルゴリズムに基づき前記エンティティ間で予備通信なしに鍵共有を行う鍵共有システムであって、
前記センタは、
エンティティ夫々の特定情報ＩＤa ，ＩＤb 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して公開鍵Ｐa ＝ｆ（ＩＤa ），Ｐb ＝ｆ（ＩＤb ）を生成する公開鍵生成器
並びに
該公開鍵生成器が生成したエンティティ夫々の公開鍵Ｐa ，Ｐb を受け付け、乱数ｒを生成し、受け付けた公開鍵Ｐa ，Ｐb 及び生成した乱数ｒの積として秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ），Ｓb ＝ｒ・ｆ（ＩＤb ）を生成する秘密鍵生成器
を備え、
生成した秘密鍵Ｓa ，Ｓb を対応するエンティティ夫々に配布するようにしてあり、
前記エンティティ夫々は、
通信相手のエンティティの特定情報ＩＤa （又はＩＤb ）及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して通信相手のエンティティの公開鍵Ｐa （又はＰb ）を生成する公開鍵生成器
並びに
該公開鍵生成器で生成した公開鍵Ｐa （又はＰb ）、前記センタから配布された自身の秘密鍵Ｓb （又はＳa ）及び前記アルゴリズム＜，＞を受け付け、受け付けた公開鍵、及び秘密鍵をアルゴリズムに代入して共通鍵Ｋba＝＜Ｐa ，Ｓb ＞（又はＫab＝＜Ｓa ，Ｐb ＞）を生成する共通鍵生成器
を備えることを特徴とする鍵共有システム。
【請求項２】
前記楕円曲線は、その上で定義される離散対数問題を多項式時間で解くことができない楕円曲線である請求項１に記載の鍵共有システム。
【請求項３】
前記センタ又はエンティティの公開鍵生成器は、同一エンティティの複数の特定情報を受け付け、受け付けた複数の特定情報それぞれを前記関数に代入して複数の公開鍵を生成するようにしてある請求項１または２に記載の鍵共有システム。
【請求項４】
エンティティを特定する特定情報ＩＤa を楕円曲線上の点に変換するための公開されている関数ｆ（）に基づいて前記エンティティの秘密鍵を生成する秘密鍵生成装置であって、
エンティティの特定情報ＩＤa 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して公開鍵Ｐa ＝ｆ（ＩＤa ）を生成する手段と、
該手段が生成した公開鍵Ｐa を受け付け、乱数ｒを生成し、受け付けた公開鍵及び生成した乱数ｒの積として秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ）を生成する手段と
を備えることを特徴とする秘密鍵生成装置。
【請求項５】
エンティティを特定する特定情報ＩＤa を楕円曲線上の点に変換するための公開されている関数ｆ（）に基づいて前記エンティティの秘密鍵を生成する秘密鍵生成装置であって、
前記エンティティの特定情報ＩＤa 、前記関数ｆ（）及びハッシュ関数ｈ（）を受け付け、公開鍵Ｐa ＝ｆ（ｈ（ＩＤa ））を生成する手段と、
該手段が生成した公開鍵Ｐa を受け付け、乱数ｒを生成し、受け付けた公開鍵Ｐa 及び生成した乱数ｒの積として秘密鍵Ｓa ＝ｒ・ｆ（ｈ（ＩＤa ））を生成する手段と
を備えることを特徴とする秘密鍵生成装置。
【請求項６】
第１エンティティを特定する特定情報ＩＤa に基づいてセンタで生成される秘密鍵Ｓa と、通信相手の第２エンティティを特定する特定情報ＩＤb に基づく公開鍵Ｐb と、エンティティを特定する特定情報を楕円曲線上の点に変換するための関数ｆ（）とから共通鍵を生成する共通鍵生成システムであって、
前記センタは、
前記第１エンティティの特定情報ＩＤa 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して第１エンティティの公開鍵Ｐa ＝ｆ（ＩＤa ）を生成する手段と、
該手段が生成した公開鍵Ｐa を受け付け、乱数ｒを生成し、受け付けた公開鍵Ｐa 及び生成した乱数ｒの積として第１エンティティの秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ）を生成する手段と
を備えており、
前記第１エンティティは、
前記第２エンティティの特定情報ＩＤb 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して第２エンティティの公開鍵Ｐb ＝ｆ（ＩＤb ）を生成する公開鍵生成器と、
該公開鍵生成器で生成した第２エンティティの公開鍵Ｐb 、前記センタで生成した第１エンティティの秘密鍵Ｓa 及び前記楕円曲線上で定義されるベイユペアリングのアルゴリズム＜，＞を受け付け、受け付けた公開鍵Ｐb 、秘密鍵Ｓa をアルゴリズム＜，＞に代入して共通鍵Ｋab＝＜Ｓa ，Ｐb ＞を生成する共通鍵生成器と
を備えることを特徴とする共通鍵生成システム。
【請求項７】
センタと通信可能に接続された複数のエンティティそれぞれへ前記センタから各エンティティの秘密鍵を送付し、一方のエンティティが前記センタから送付された自身の秘密鍵と他方のエンティティの公開鍵とから求めた共通鍵を用いて平文を暗号文に暗号化して前記他方のエンティティへ伝送し、前記他方のエンティティが伝送された暗号文を、前記センタから送付された自身の秘密鍵と前記一方のエンティティの公開鍵とから求めた、前記共通鍵と同一の共通鍵を用いて平文に復号することにより、エンティティ間で情報の通信を行う暗号通信方法において、
前記センタは、
エンティティ夫々の特定情報ＩＤa ，ＩＤb 及び該特定情報を楕円曲線上の点に変換するための関数ｆ（）を受け付け、
受け付けた特定情報を関数に代入してエンティティ夫々の公開鍵Ｐa ＝ｆ（ＩＤa ），Ｐb ＝ｆ（ＩＤb ）を生成し、
乱数ｒを生成し、
生成したエンティティ夫々の公開鍵Ｐa ，Ｐb 及び生成した乱数ｒの積としてエンティティ夫々の秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ），Ｓb ＝ｒ・ｆ（ＩＤb ）を生成し、
生成した秘密鍵を対応するエンティティ夫々に配布し、
前記エンティティ夫々は、
通信相手のエンティティの特定情報ＩＤa（又はＩＤb ）、及び前記関数ｆ（）を受け付け、
受け付けた特定情報を関数に代入して通信相手のエンティティの公開鍵Ｐa （又はＰb ）を生成し、
生成した公開鍵Ｐa （又はＰb ）、前記センタから送付された自身の秘密鍵Ｓb （又はＳa ）、及び公開されている、前記楕円曲線上で定義されるベイユペアリングのアルゴリズム＜，＞を受け付け、受け付けた公開鍵及び秘密鍵を前記アルゴリズムに代入して共通鍵Ｋba＝＜Ｐa ，Ｓb ＞（又はＫab＝＜Ｓa ，Ｐb ＞）を生成する
ことを特徴とする暗号通信方法。
【請求項８】
センタと通信可能に接続された複数のエンティティを備え、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び送信された暗号文を平文に復号する復号処理を、複数のエンティティ間で相互に行うこととし、各エンティティを特定する特定情報に基づいて各エンティティの秘密鍵を生成して各エンティティへ送付するセンタと、該センタから送付された自身の秘密鍵と通信対象のエンティティの特定情報に基づく公開鍵とを用いて前記暗号化処理及び復号処理に使用する共通鍵を生成する複数のエンティティとを有し、エンティティ夫々の特定情報を楕円曲線上の点に変換するための関数及び前記楕円曲線上で定義されるベイユペアリングのアルゴリズムが公開されている暗号通信システムであって、
前記センタは、
エンティティ夫々の特定情報ＩＤa ，ＩＤb 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して公開鍵Ｐa ＝ｆ（ＩＤa ），Ｐb ＝ｆ（ＩＤb ）を生成する公開鍵生成器
並びに
該公開鍵生成器が生成したエンティティ夫々の公開鍵Ｐa ，Ｐb を受け付け、乱数ｒを生成し、受け付けた公開鍵Ｐa ，Ｐb 及び生成した乱数ｒの積として秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ），Ｓb ＝ｒ・ｆ（ＩＤb ）を生成する秘密鍵生成器
を備え、
生成した秘密鍵Ｓa ，Ｓb を対応するエンティティ夫々に配布するようにしてあり、
エンティティ夫々は、
通信相手のエンティティの特定情報ＩＤa （又はＩＤb ）及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して通信相手のエンティティの公開鍵Ｐa （又はＰb ）を生成する公開鍵生成器
並びに
該公開鍵生成器で生成した公開鍵Ｐa （又はＰb ）、前記センタから送付された自身の秘密鍵Ｓb （又はＳa ）及び前記アルゴリズム＜，＞を受け付け、受け付けた公開鍵、秘密鍵をアルゴリズムに代入して共通鍵Ｋba＝＜Ｐa ，Ｓb ＞（又はＫab＝＜Ｓa ，Ｐb ＞）を生成する共通鍵生成器
を備えることを特徴とする暗号通信システム。
【請求項９】
コンピュータを請求項４または５に記載の秘密鍵生成装置として機能させるためのコンピュータプログラムを記録してあることを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、予備通信なして両エンティティ間で共通鍵を共有し合う鍵共有システム、センタにて各エンティティ固有の秘密鍵を生成する秘密鍵生成装置、各エンティティで暗号化処理・復号処理に必要な共通鍵を生成する共通鍵生成システム、情報の内容が当事者以外にはわからないように暗号文にて通信を行う暗号通信方法及び暗号通信システム、並びに、これらのシステムまたは装置を実現するためのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
高度情報化社会と呼ばれる現代社会では、コンピュータネットワークを基盤として、ビジネス上の重要な文書・画像情報が電子的な情報という形で伝送通信されて処理される。このような電子情報は、容易に複写が可能である、複写物とオリジナルとの区別が困難であるという性質があり、情報保全の問題が重要視されている。特に、「コンピュータリソースの共有」，「マルチアクセス」，「広域化」の各要素を満たすコンピュータネットワークの実現が高度情報化社会の確立に不可欠であるが、これは当事者間の情報保全の問題とは矛盾する要素を含んでいる。このような矛盾を解消するための有効な手法として、人類の過去の歴史上主として軍事，外交面で用いられてきた暗号技術が注目されている。
【０００３】
暗号とは、情報の意味が当事者以外には理解できないように情報を交換することである。暗号において、誰でも理解できる元の文（平文）を第三者には意味がわからない文（暗号文）に変換することが暗号化であり、また、暗号文を平文に戻すことが復号であり、この暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗号化の過程及び復号の過程には、それぞれ暗号化鍵及び復号鍵と呼ばれる秘密の情報が用いられる。復号時には秘密の復号鍵が必要であるので、この復号鍵を知っている者のみが暗号文を復号でき、暗号化によって情報の秘密性が維持され得る。
【０００４】
暗号化鍵と復号鍵とは、等しくても良いし、異なっていても良い。両者の鍵が等しい暗号系は、共通鍵暗号系と呼ばれ、米国商務省標準局が採用したＤＥＳ（Data Encryption Standards)はその典型例である。また、両者の鍵が異なる暗号系の一例として、公開鍵暗号系と呼ばれる暗号系が提案された。この公開鍵暗号系は、暗号系を利用する各ユーザ（エンティティ）が暗号化鍵と復号鍵とを一対ずつ作成し、暗号化鍵を公開鍵リストにて公開し、復号鍵のみを秘密に保持するという暗号系である。公開鍵暗号系では、この一対となる暗号化鍵と復号鍵とが異なり、一方向性関数を利用することによって暗号化鍵から復号鍵を割り出せないという特徴を持たせている。
【０００５】
公開鍵暗号系は、暗号化鍵を公開するという画期的な暗号系であって、高度情報化社会の確立に必要な上述した３つの要素に適合するものであり、情報通信技術の分野等での利用を図るべく、その研究が活発に行われ、典型的な公開鍵暗号系としてＲＳＡ暗号系が提案された。このＲＳＡ暗号系は、一方向性関数として素因数分解の困難さを利用して実現されている。また、離散対数問題を解くことの困難さ（離散対数問題）を利用した公開鍵暗号系も種々の手法が提案されてきた。
【０００６】
また、各エンティティの住所，氏名，電子メールのアドレス等の個人を特定するＩＤ（Identity）情報を利用する暗号系が提案された。この暗号系では、ＩＤ情報に基づいて送受信者間で共通の暗号化・復号鍵を生成する。また、このＩＤ情報に基づく暗号技法には、（１）暗号文通信に先立って送受信者間での予備通信を必要とする方式と、（２）暗号文通信に先立って送受信者間での予備通信を必要としない方式とがある。特に、（２）の手法は予備通信が不要であるので、エンティティの利便性が高く、将来の暗号系の中枢をなすものと考えられている。
【０００７】
この（２）の手法による暗号系は、ＩＤ−ＮＩＫＳ（ID-based non-interactive key sharing scheme)と呼ばれており、通信相手のＩＤ情報を用いて予備通信を行うことなく暗号化・復号鍵を共有する方式を採用している。ＩＤ−ＮＩＫＳは、送受信者間で公開鍵，秘密鍵を交換する必要がなく、また鍵のリスト及び第三者によるサービスも必要としない方式であり、任意のエンティティ間で安全に通信を行える。
【０００８】
図４は、このＩＤ−ＮＩＫＳのシステムの原理を示す図である。信頼できるセンタの存在を仮定し、このセンタを中心にして共通鍵生成システムを構成している。図４において、エンティティＸの特定情報であるエンティティＸの名前，住所，電話番号，メールアドレス等のＩＤ情報を｛ＩＤX ｝で表す。センタは任意のエンティティＸに対して、センタ公開情報｛ＰＣi ｝，センタ秘密情報｛ＳＣi ｝及びエンティティＸのＩＤ情報｛ＩＤX ｝に基づいて、以下のように秘密情報ＳXiを計算し、秘密裏にエンティティＸへ配布する。
ＳXi＝Ｆi （｛ＳＣi ｝，｛ＰＣi ｝，｛ＩＤX ｝）
【０００９】
エンティティＸは他の任意のエンティティＹとの間で、暗号化，復号のための共通鍵ＫXYを、エンティティＸ自身の秘密情報｛ＳXi｝，センタ公開情報｛ＰＣi ｝及び相手先のエンティティＹのＩＤ情報｛ＩＤY ｝を用いて以下のように生成する。
ＫXY＝ｆ（｛ＳXi｝，｛ＰＣi ｝，｛ＩＤY ｝）
また、エンティティＹも同様にエンティティＸへの共通鍵ＫYXを生成する。もし常にＫXY＝ＫYXの関係が成立すれば、この鍵ＫXY，ＫYXをエンティティＸ，Ｙ間で暗号化鍵，復号鍵として使用できる。
【００１０】
上述した公開鍵暗号系では、例えばＲＳＡ暗号系の場合にその公開鍵の長さは現在の電話番号の十数倍となり、極めて煩雑である。これに対して、ＩＤ−ＮＩＫＳでは、各ＩＤ情報を名簿という形式で登録しておけば、この名簿を参照して任意のエンティティとの間で共通鍵を生成することができる。従って、図４に示すようなＩＤ−ＮＩＫＳのシステムが安全に実現されれば、多数のエンティティが加入するコンピュータネットワーク上で便利な暗号系を構築できる。このような理由により、ＩＤ−ＮＩＫＳが将来の暗号系の中心になると期待されている。
【００１１】
【発明が解決しようとする課題】
通信相手のＩＤ情報を用いて予備通信を行うことなく暗号化鍵及び復号鍵となる共通鍵を互いに共有するようなＩＤ−ＮＩＫＳにあっては、特に複数のエンティティが結託する結託攻撃に対して十分に安全であることが望まれる。そして、暗号学的に安全なＩＤ−ＮＩＫＳを構築できるか否かは、高度情報化社会にとって重要な問題であり、より理想的な暗号方式の探究が進められている。
【００１２】
本発明は斯かる事情に鑑みてなされたものであり、各エンティティの特定情報（ＩＤ情報）に基づいて、楕円暗号で利用されている楕円曲線等の代数曲線上の点に写像することにより、予備通信を行うことなく両エンティティ間で容易に共通鍵を共有し合える鍵共有システム、この鍵共有システムに基づいて安全なＩＤ−ＮＩＫＳを構築できるための秘密鍵生成装置，共通鍵生成システム，暗号通信方法及び暗号通信システム、並びに、これらのシステムまたは装置を実現するためのプログラムを記録した記録媒体を提供することを目的とする。
【００１３】
【課題を解決するための手段】
請求項１に係る鍵共有システムは、センタと通信可能に接続された２つのエンティティ夫々を特定する特定情報ＩＤa ，ＩＤb が公開されており、エンティティ夫々の特定情報を楕円曲線上の点に変換するための関数ｆ（）及び前記楕円曲線上で定義されるベイユペアリングのアルゴリズム＜，＞が公開されており、これら公開されている特定情報、関数及びアルゴリズムに基づき前記エンティティ間で予備通信なしに鍵共有を行う鍵共有システムであって、前記センタは、エンティティ夫々の特定情報ＩＤa ，ＩＤb 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して公開鍵Ｐa ＝ｆ（ＩＤa ），Ｐb ＝ｆ（ＩＤb ）を生成する公開鍵生成器並びに該公開鍵生成器が生成したエンティティ夫々の公開鍵Ｐa ，Ｐb を受け付け、乱数ｒを生成し、受け付けた公開鍵Ｐa ，Ｐb 及び生成した乱数ｒの積として秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ），Ｓb ＝ｒ・ｆ（ＩＤb ）を生成する秘密鍵生成器を備え、生成した秘密鍵Ｓa ，Ｓb を対応するエンティティ夫々に配布するようにしてあり、前記エンティティ夫々は、通信相手のエンティティの特定情報ＩＤa （又はＩＤb ）及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して通信相手のエンティティの公開鍵Ｐa （又はＰb ）を生成する公開鍵生成器並びに該公開鍵生成器で生成した公開鍵Ｐa （又はＰb ）、前記センタから配布された自身の秘密鍵Ｓb （又はＳa ）及び前記アルゴリズム＜，＞を受け付け、受け付けた公開鍵、及び秘密鍵をアルゴリズムに代入して共通鍵Ｋba＝＜Ｐa ，Ｓb ＞（又はＫab＝＜Ｓa ，Ｐb ＞）を生成する共通鍵生成器を備えることを特徴とする。
【００１７】
請求項２に係る鍵共有システムは、請求項１において、前記楕円曲線は、その上で定義される離散対数問題を多項式時間で解くことができない楕円曲線であることを特徴とする。
【００１９】
請求項３に係る鍵共有システムは、請求項１または２において、前記センタ又はエンティティの公開鍵生成器は、同一エンティティの複数の特定情報を受け付け、受け付けた複数の特定情報それぞれを前記関数に代入して複数の公開鍵を生成するようにしてあることを特徴とする。
【００２０】
請求項４に係る秘密鍵生成装置は、エンティティを特定する特定情報ＩＤa を楕円曲線上の点に変換するための公開されている関数ｆ（）に基づいて前記エンティティの秘密鍵を生成する秘密鍵生成装置であって、エンティティの特定情報ＩＤa 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して公開鍵Ｐa ＝ｆ（ＩＤa ）を生成する手段と、該手段が生成した公開鍵Ｐa を受け付け、乱数ｒを生成し、受け付けた公開鍵及び生成した乱数ｒの積として秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ）を生成する手段とを備えることを特徴とする。
【００２１】
請求項５に係る秘密鍵生成装置は、エンティティを特定する特定情報ＩＤa を楕円曲線上の点に変換するための公開されている関数ｆ（）に基づいて前記エンティティの秘密鍵を生成する秘密鍵生成装置であって、前記エンティティの特定情報ＩＤa 、前記関数ｆ（）及びハッシュ関数ｈ（）を受け付け、公開鍵Ｐa ＝ｆ（ｈ（ＩＤa ））を生成する手段と、該手段が生成した公開鍵Ｐa を受け付け、乱数ｒを生成し、受け付けた公開鍵Ｐa 及び生成した乱数ｒの積として秘密鍵Ｓa ＝ｒ・ｆ（ｈ（ＩＤa ））を生成する手段とを備えることを特徴とする。
【００２２】
請求項６に係る共通鍵生成システムは、第１エンティティを特定する特定情報ＩＤa に基づいてセンタで生成される秘密鍵Ｓa と、通信相手の第２エンティティを特定する特定情報ＩＤb に基づく公開鍵Ｐb と、エンティティを特定する特定情報を楕円曲線上の点に変換するための関数ｆ（）とから共通鍵を生成する共通鍵生成システムであって、前記センタは、前記第１エンティティの特定情報ＩＤa 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して第１エンティティの公開鍵Ｐa ＝ｆ（ＩＤa ）を生成する手段と、該手段が生成した公開鍵Ｐa を受け付け、乱数ｒを生成し、受け付けた公開鍵Ｐa 及び生成した乱数ｒの積として第１エンティティの秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ）を生成する手段とを備えており、前記第１エンティティは、前記第２エンティティの特定情報ＩＤb 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して第２エンティティの公開鍵Ｐb ＝ｆ（ＩＤb ）を生成する公開鍵生成器と、該公開鍵生成器で生成した第２エンティティの公開鍵Ｐb 、前記センタで生成した第１エンティティの秘密鍵Ｓa 及び前記楕円曲線上で定義されるベイユペアリングのアルゴリズム＜，＞を受け付け、受け付けた公開鍵Ｐb 、秘密鍵Ｓa をアルゴリズム＜，＞に代入して共通鍵Ｋab＝＜Ｓa ，Ｐb ＞を生成する共通鍵生成器とを備えることを特徴とする。
【００２５】
請求項７に係る暗号通信方法は、センタと通信可能に接続された複数のエンティティそれぞれへ前記センタから各エンティティの秘密鍵を送付し、一方のエンティティが前記センタから送付された自身の秘密鍵と他方のエンティティの公開鍵とから求めた共通鍵を用いて平文を暗号文に暗号化して前記他方のエンティティへ伝送し、前記他方のエンティティが伝送された暗号文を、前記センタから送付された自身の秘密鍵と前記一方のエンティティの公開鍵とから求めた、前記共通鍵と同一の共通鍵を用いて平文に復号することにより、エンティティ間で情報の通信を行う暗号通信方法において、前記センタは、エンティティ夫々の特定情報ＩＤa ，ＩＤb 及び該特定情報を楕円曲線上の点に変換するための関数ｆ（）を受け付け、受け付けた特定情報を関数に代入してエンティティ夫々の公開鍵Ｐa ＝ｆ（ＩＤa ），Ｐb ＝ｆ（ＩＤb ）を生成し、乱数ｒを生成し、生成したエンティティ夫々の公開鍵Ｐa ，Ｐb 及び生成した乱数ｒの積としてエンティティ夫々の秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ），Ｓb ＝ｒ・ｆ（ＩＤb ）を生成し、生成した秘密鍵を対応するエンティティ夫々に配布し、前記エンティティ夫々は、通信相手のエンティティの特定情報ＩＤa（又はＩＤb ）、及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して通信相手のエンティティの公開鍵Ｐa （又はＰb ）を生成し、生成した公開鍵Ｐa （又はＰb ）、前記センタから送付された自身の秘密鍵Ｓb （又はＳa ）、及び公開されている、前記楕円曲線上で定義されるベイユペアリングのアルゴリズム＜，＞を受け付け、受け付けた公開鍵及び秘密鍵を前記アルゴリズムに代入して共通鍵Ｋba＝＜Ｐa ，Ｓb ＞（又はＫab＝＜Ｓa ，Ｐb ＞）を生成することを特徴とする。
【００２８】
請求項８に係る暗号通信システムは、センタと通信可能に接続された複数のエンティティを備え、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び送信された暗号文を平文に復号する復号処理を、複数のエンティティ間で相互に行うこととし、各エンティティを特定する特定情報に基づいて各エンティティの秘密鍵を生成して各エンティティへ送付するセンタと、該センタから送付された自身の秘密鍵と通信対象のエンティティの特定情報に基づく公開鍵とを用いて前記暗号化処理及び復号処理に使用する共通鍵を生成する複数のエンティティとを有し、エンティティ夫々の特定情報を楕円曲線上の点に変換するための関数及び前記楕円曲線上で定義されるベイユペアリングのアルゴリズムが公開されている暗号通信システムであって、前記センタは、エンティティ夫々の特定情報ＩＤa ，ＩＤb 及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して公開鍵Ｐa ＝ｆ（ＩＤa ），Ｐb ＝ｆ（ＩＤb ）を生成する公開鍵生成器並びに該公開鍵生成器が生成したエンティティ夫々の公開鍵Ｐa ，Ｐb を受け付け、乱数ｒを生成し、受け付けた公開鍵Ｐa ，Ｐb 及び生成した乱数ｒの積として秘密鍵Ｓa ＝ｒ・ｆ（ＩＤa ），Ｓb ＝ｒ・ｆ（ＩＤb ）を生成する秘密鍵生成器を備え、生成した秘密鍵Ｓa ，Ｓb を対応するエンティティ夫々に配布するようにしてあり、エンティティ夫々は、通信相手のエンティティの特定情報ＩＤa （又はＩＤb ）及び前記関数ｆ（）を受け付け、受け付けた特定情報を関数に代入して通信相手のエンティティの公開鍵Ｐa （又はＰb ）を生成する公開鍵生成器並びに該公開鍵生成器で生成した公開鍵Ｐa （又はＰb ）、前記センタから送付された自身の秘密鍵Ｓb （又はＳa ）及び前記アルゴリズム＜，＞を受け付け、受け付けた公開鍵、秘密鍵をアルゴリズムに代入して共通鍵Ｋba＝＜Ｐa ，Ｓb ＞（又はＫab＝＜Ｓa ，Ｐb ＞）を生成する共通鍵生成器を備えることを特徴とする。
【００２９】
請求項９に係る記録媒体は、コンピュータを請求項４または５に記載の秘密鍵生成装置として機能させるためのコンピュータプログラムを記録してあることを特徴とする。
【００３１】
本発明では、各エンティティの特定情報（ＩＤ情報）に基づいて、楕円暗号で利用されている楕円曲線，超楕円曲線等の代数曲線上の点に写像し、その写像値を各エンティティの公開鍵とする。この代数曲線及び写像のアルゴリスムは公開する。センタでは、各エンティティの特定情報（ＩＤ情報）に基づき代数曲線上の点に写像し、その写像値とセンタ自身の秘密情報とを用いて、各エンティティ固有の秘密鍵を生成し、これを対応するエンティティへ秘密裏に送付する。各エンティティは、センタから送られる自身固有の秘密鍵と、通信相手の特定情報（ＩＤ情報）に基づき代数曲線上の点に写像した写像値とを用いて、暗号化処理・復号処理に用いる共通鍵を生成する。この際、楕円曲線上で定義されるペアリング（ベイユ（Weil）ペアリング，テイト（Tate）ペアリング等) を利用して、予備通信を行うことなく、両エンティティ間で同一の共通鍵を共有する。本発明における代数曲線上の点への写像は、各エンティティ，センタの何れでも可能である。
【００３２】
本発明では、安全性の根拠を代数曲線上の離散対数問題（例えば楕円曲線上の離散対数問題、以下、これを単に楕円離散対数問題という）に置いている。複数のエンティティによる結託攻撃にて本発明の暗号システムが破られることは、例えば楕円離散対数問題が解かれることと等価であるかまたはそれ以上に困難であり、その安全性は極めて高い。
【００３３】
【発明の実施の形態】
本発明の実施の形態について具体的に説明する。
図１は、本発明の暗号通信システムの構成を示す模式図である。情報の隠匿を信頼できるセンタ１が設定されており、このセンタ１としては、例えば社会の公的機関を該当できる。このセンタ１と、この暗号通信システムを利用するユーザとしての複数の各エンティティＡ，Ｂ，…，Ｚとは、秘密通信路２ａ，２ｂ，…，２ｚにより接続されており、これらの秘密通信路２ａ，２ｂ，…，２ｚを介してセンタ１から秘密の鍵情報（秘密鍵Ｓa ，Ｓb ，…，Ｓz ）が各エンティティＡ，Ｂ，…，Ｚへ伝送されるようになっている。また、２人のエンティティの間には通信路３ab，３az，３bz，…が設けられており、この通信路３ab，３az，３bz，…を介して通信情報を暗号化した暗号文が互いのエンティティ間で伝送されるようになっている。
【００３４】
以下、代数曲線として楕円曲線を用いる場合の本発明における基本方式について説明する。
まず、本発明で用いる楕円曲線のベイユペアリングの基本的性質を述べる。ベイユペアリングは、楕円曲線上の点がなす群Ｅ／Ｆq から有限体上Ｆd （但し、ｄ＝ｑk ）の乗法群への写像である。ベイユペアリングには、以下に示すよう双線形性と交換則とが成り立つ。なお、＜，＞はベイユペアリングを表し、Ｐ，Ｐ1 ，Ｐ2 ，Ｑ，Ｑ1 ，Ｑ2 は楕円曲線上の点を示す。
【００３５】
（双線形性）
＜Ｐ1 ＋Ｐ2 ，Ｑ＞＝＜Ｐ1 ，Ｑ＞＜Ｐ2 ，Ｑ＞
＜Ｐ，Ｑ1 ＋Ｑ2 ＞＝＜Ｐ，Ｑ1 ＞＜Ｐ，Ｑ2 ＞
（交換則）
＜Ｐ，Ｑ＞＝＜Ｑ，Ｐ＞-1
双線形性を有するので、ｍを整数とした場合、以下のような等式が成立する。
＜ｍＰ，Ｑ＞＝＜Ｐ，Ｑ＞m 
＜Ｐ，ｍＱ＞＝＜Ｐ，Ｑ＞m 
【００３６】
ベイユペアリングに基づく鍵共有法を以下に説明する。
（センタ１での秘密鍵生成）
任意のエンティティＡの名前，住所，電話番号，メールアドレス等の特定情報（ＩＤ情報）をＩＤa とする。センタ１は、ベイユペアリングのアルゴリズム＜，＞と任意のエンティティＡのＩＤ情報ＩＤa を楕円曲線上の点Ｐa ∈Ｅ／Ｆq に変換して（写像して）公開鍵を求める関数ｆ（）とを公開する。また、センタ１は、秘密の乱数ｒを生成し、この乱数ｒとエンティティＡの公開鍵Ｐa とを用いて下記（１）のようにエンティティＡの秘密鍵Ｓa を求め、求めた秘密鍵Ｓa を秘密裏にエンティティＡへ配布する。
Ｓa ＝ｒＰa       …（１）
【００３７】
以上のような秘密情報，公開情報をまとめると、次のようになる。
センタ１の公開情報    ：＜，＞，ｆ（）
センタ１の秘密情報    ：ｒ（ランダムな整数）
エンティティＡの公開鍵：Ｐa （＝ｆ（ＩＤa ））
エンティティＡの秘密鍵：Ｓa （＝ｒ・ｆ（ＩＤa ））
【００３８】
（エンティティＡ，Ｂでの共通鍵生成）
各エンティティは、センタ１から配布された自身の秘密鍵と通信相手であるエンティティの公開鍵とから、楕円曲線上でのベイユペアリングを利用して、共通鍵を生成する。
（第１例）
エンティティＡのＩＤ情報ＩＤa とエンティティＢのＩＤ情報ＩＤb との間での大小比較を行えるアルゴリスムを設定し、ペアリングを計算する際にその大小情報を用いてペアリングの順序を適切に設定する。このアルゴリスムとしては、辞書式または２進数で表したときの大小などが可能である。なお、ペアリングの順序を設定する方法として、ＩＤ情報ＩＤa ，ＩＤb を変換（写像）した後の公開鍵Ｐa ，Ｐb の大小情報を用いることも可能である。
【００３９】
例えば、ＩＤa ＞ＩＤb である場合、エンティティＡは、自身の秘密鍵Ｓa と、エンティティＢのＩＤ情報ＩＤb を楕円曲線に写像した公開鍵Ｐb とを用いて、下記（２）に従って共通鍵Ｋabを生成する。
0004450969.tif 000002
【００４０】
一方、ＩＤa ＞ＩＤb である場合、エンティティＢは、エンティティＡのＩＤ情報ＩＤa を楕円曲線に写像した公開鍵Ｐa と自身の秘密鍵Ｓb とを用いて、下記（３）に従って共通鍵Ｋbaを生成する。
0004450969.tif 000003
よって、エンティティＡが生成する共通鍵ＫabとエンティティＢが生成する共通鍵Ｋbaとは一致して、両エンティティＡ，Ｂ間で共通鍵を共有できる。
【００４１】
以下に、上記のようなＩＤ情報の大小関係を設定しないで鍵共有を可能とする２つの例について説明する。
【００４２】
（第２例）
ｘ，ｙに関する対称関数ｇ（ｘ，ｙ）（但し、ｇ（ｘ，ｙ）＝ｘｙは除く）を設定する。以下の例では、ｇ（ｘ，ｙ）＝ｘ＋ｙとする。エンティティＡは、ｇ（ｘ，ｙ）＝ｘ＋ｙに従って下記（４）のように、共通鍵Ｋab＝ｋab＋ｋbaを生成する。
0004450969.tif 000004
【００４３】
一方、エンティティＢは、ｇ（ｘ，ｙ）＝ｘ＋ｙに従って下記（５）のように、共通鍵Ｋba＝ｋba＋ｋabを生成する。
0004450969.tif 000005
よって、エンティティＡが生成する共通鍵ＫabとエンティティＢが生成する共通鍵Ｋbaとは一致して、両エンティティＡ，Ｂ間で共通鍵を共有できる。なお、他の種類の対称関数ｇ（ｘ，ｙ）を利用しても、同様に鍵共有が可能である。
【００４４】
（第３例）
エンティティＡは、第２例で示したｋabを用いて、下記（６）のように、共通鍵Ｋab＝ｋab＋ｋab-1を生成する。
0004450969.tif 000006
【００４５】
エンティティＢは、第２例で示したｋbaを用いて、下記（７）のように、共通鍵Ｋba＝ｋba＋ｋba-1を生成する。
0004450969.tif 000007
よって、エンティティＡが生成する共通鍵ＫabとエンティティＢが生成する共通鍵Ｋbaとは一致して、両エンティティＡ，Ｂ間で共通鍵を共有できる。
【００４６】
（第４例）
エンティティＡは、自身の秘密鍵Ｓa とエンティティＢの公開鍵Ｐb とを用いて、下記（８）のようにして、中間鍵Ｉabを生成する。
0004450969.tif 000008
【００４７】
エンティティＢは、自身の秘密鍵Ｓb とエンティティＡの公開鍵Ｐa とを用いて、下記（９）のようにして、中間鍵Ｉbaを生成する。
0004450969.tif 000009
【００４８】
ここで、ベイユペアリングにおける前述した（交換則）により、Ｉab×Ｉba＝１の関係が成立することが分かる。このような逆数の関係を利用して、両エンティティＡ，Ｂ間で鍵共有を行うことも可能である。
【００４９】
以上のようにして、ベイユペアリングを利用して、各エンティティ間で等しい共通鍵を容易に生成できる。
【００５０】
なお、上述した例では、エンティティＡのＩＤ情報ＩＤa から直接に写像点Ｐa を求めるようにしたが、一方向性関数を用いてＩＤ情報ＩＤa を変換し、その変換値から写像点Ｐa を求めるようにしても良い。この際、一方向性関数の例としてハッシュ関数ｈ（）を用いた場合、公開鍵Ｐa ＝ｆ（ｈ（ＩＤa ）），秘密鍵Ｓa ＝ｒ・ｆ（ｈ（ＩＤa ））となる。
【００５１】
エンティティが、センタ１の秘密情報ｒを求めることを困難にするためには、次の２つの条件が必要である。
（条件１）ｑを２160 以上に設定すること。
（条件２）＃Ｅ／Ｆq ｜ｑk −１かつｑk ＞２1024を満たすような整数ｋが存在すること。
【００５２】
（条件１）は、楕円離散対数問題を求めることを困難にするために必要である。（条件２）は、有限体Ｆd （但し，ｄ＝ｑk ）の離散対数問題を求めることを困難にするために必要である。
【００５３】
次に、上述した鍵共有方式を利用した暗号システムにおけるエンティティ間の情報通信について説明する。図２は、２人のエンティティＡ，Ｂ間における情報の通信状態を示す模式図である。図２の例は、エンティティＡが平文（メッセージ）Ｍを暗号文Ｃに暗号化してそれをエンティティＢへ伝送し、エンティティＢがその暗号文Ｃを元の平文（メッセージ）Ｍに復号する場合を示している。
【００５４】
センタ１には、関数ｆ（）を用いて、各エンティティＡ，ＢのＩＤ情報ＩＤa ，ＩＤb を楕円曲線に写像した写像位置である公開鍵Ｐa ，Ｐb を得る公開鍵生成器１ａと、その公開鍵Ｐa ，Ｐb とセンタ固有の秘密情報ｒとを用いて各エンティティＡ，Ｂの秘密鍵Ｓa ，Ｓb を求める秘密鍵生成器１ｂとが備えられている。そして、センタ１から各エンティティＡ，Ｂへ、前記（１）に従って生成された秘密鍵Ｓa ，Ｓb が送付される。
【００５５】
エンティティＡ側には、エンティティＢのＩＤ情報ＩＤb を入力し、それを楕円曲線に写像した写像位置である公開鍵Ｐb を得る公開鍵生成器１１と、センタ１から送られる秘密鍵Ｓa と公開鍵生成器１１からの公開鍵Ｐb とに基づいてエンティティＡが求めるエンティティＢとの共通鍵Ｋabを生成する共通鍵生成器１２と、共通鍵Ｋabを使用して平文（メッセージ）Ｍを暗号文Ｃに暗号化して通信路３０へ出力する暗号化器１３とが備えられている。
【００５６】
また、エンティティＢ側には、エンティティＡのＩＤ情報ＩＤa を入力し、それを楕円曲線に写像した写像位置である公開鍵Ｐa を得る公開鍵生成器２１と、センタ１から送られる秘密鍵Ｓb と公開鍵生成器２１からの公開Ｐa とに基づいてエンティティＢが求めるエンティティＡとの共通鍵Ｋbaを生成する共通鍵生成器２２と、通信路３０から入力した暗号文Ｃを共通鍵Ｋbaを使用して平文（メッセージ）Ｍに復号して出力する復号器２３とが備えられている。
【００５７】
次に、動作について説明する。エンティティＡからエンティティＢへ情報を伝送しようとする場合、まず、エンティティＢのＩＤ情報ＩＤb が公開鍵生成器１１に入力されて公開鍵Ｐb が得られ、得られた公開鍵Ｐb が共通鍵生成器１２へ送られる。また、センタ１から秘密鍵Ｓa が共通鍵生成器１２へ入力される。そして、前記（２），（４）または（６）に従って共通鍵Ｋabが求められて、暗号化器１３へ送られる。暗号化器１３において、この共通鍵Ｋabを用いて平文（メッセージ）Ｍが暗号文Ｃに暗号化され、暗号文Ｃが通信路３０を介して伝送される。
【００５８】
通信路３０を伝送された暗号文ＣはエンティティＢの復号器２３へ入力される。エンティティＡのＩＤ情報ＩＤa が公開鍵生成器２１に入力されて公開鍵Ｐa が得られ、得られた公開鍵Ｐa が共通鍵生成器２２へ送られる。また、センタ１から秘密鍵Ｓb が共通鍵生成器２２へ入力される。そして、前記（３），（５）または（７）に従って共通鍵Ｋbaが求められて、復号器２３へ送られる。復号器２３において、この共通鍵Ｋbaを用いて暗号文Ｃが平文（メッセージ）Ｍに復号される。
【００５９】
次に、本発明における安全性について説明する。本発明の安全性は、楕円離散対数問題と後述するようにこれと等価である拡張楕円離散対数問題とに基づいている。
【００６０】
〔楕円離散対数問題と拡張楕円離散対数問題との等価性〕
通常の楕円離散対数問題とは、楕円曲線Ｅ上の任意の点Ｐとそのｒ倍点Ｑ＝ｒＰが与えられている場合に、Ｐ，Ｑからｒを求める問題である。ここで、下記（10）のように、楕円曲線上の任意の点Ｐi （１≦ｉ≦ｎ−１）とその点Ｐi に基づくＱが与えられている場合に、ある１組のｒi （１≦ｉ≦ｎ−１）を求める問題を拡張楕円離散対数問題と定義する。楕円離散対数問題と拡張楕円離散対数問題との等価性について考察する。なお、議論の簡単化のために楕円曲線は素数位数ｐとする。
【００６１】
【数１】
0004450969.tif 000010
【００６２】
（楕円離散対数問題から拡張楕円離散対数問題への帰着）
楕円離散対数問題がベースポイントＰを基準として解けると仮定する。Ｐi （１≦ｉ≦ｎ−１）及びＱは、夫々楕円曲線上のベースポイントＰを基準として係数を、下記（11）のように求めることができる。
【００６３】
【数２】
0004450969.tif 000011
【００６４】
係数ｒi ′，ｒ′をＦp の元として、下記（12）の不定方程式を解くことにより、ｒi （１≦ｉ≦ｎ−１）を求めることが可能である。よって、拡張楕円離散対数問題を解くことができる。
【００６５】
【数３】
0004450969.tif 000012
【００６６】
（拡張楕円離散対数問題から楕円離散対数問題への帰着）
任意の拡張楕円離散対数問題が解けると仮定する。ここで、楕円曲線上の点Ｐi （１≦ｉ≦ｎ）に対して、下記（13）で示される拡張楕円離散対数問題を解き、これを行列を用いて表すと下記（14）のようになる。
【００６７】
【数４】
0004450969.tif 000013
【００６８】
上記（14）の行列について係数のみを抜き出すと下記（15）のような関係式が得られ、下記（16）のように変形可能である。
【００６９】
【数５】
0004450969.tif 000014
【００７０】
上記（16）から分かるように、点Ｐi （１≦ｉ≦ｎ−１）はＰn の定数倍で表すことが可能である。即ち、拡張楕円離散対数問題を解くことによって、Ｐi ＝ｒi ′Ｐn を満たすｒi ′を求めることができる。
以上のことから、楕円離散対数問題と拡張楕円離散対数問題とは等価になる。
【００７１】
〔センタの秘密情報に関する安全性〕
エンティティＣの公開鍵Ｐc と秘密鍵Ｓc とからセンタの秘密情報ｒを得ることは、楕円離散対数問題を解くことと等価であって、困難である。
エンティティＡの公開鍵Ｐa とエンティティＢの公開鍵Ｐb とから＜Ｐa ，Ｐb ＞を計算し、これと共通鍵Ｋab＝＜Ｐa ，Ｐb ＞r とからｒを得ることは離散対数問題を解くことと等価であって、困難である。
よって、どのエンティティもセンタの秘密情報ｒを求めることができない。
【００７２】
〔エンティティの秘密鍵に関する安全性〕
ｎ人のエンティティが結託してエンティティＣの秘密鍵Ｓc を偽造する攻撃について考察する。エンティティＣの公開鍵Ｐc が下記（17）のように他のエンティティの公開鍵の線形結合によって表すことが可能であると仮定すると、前記（１）にこの線形結合を代入すると、下記（18）の関係式が成立するので、エンティティＣの秘密鍵Ｓc が露呈する。
0004450969.tif 000015
【００７３】
しかし、上記（17）での係数ｕi を得るには拡張楕円離散対数問題を解く必要があり、このような攻撃は困難であるといえる。よって、安全性は拡張楕円離散対数問題を解くことの難しさに基づいている。
【００７４】
ここで、この秘密鍵の安全性について更に詳述する。拡張楕円離散対数問題は、ＰをＥ／Ｆq 上の任意の点、（Ｇ1 ，Ｇ2 ）をＥ／Ｆq の生成元とした場合に、下記（19）において係数ｕ1 ，ｕ2 を求める問題である。
Ｐ＝ｕ1 Ｇ1 ＋ｕ2 Ｇ2         …（19）
【００７５】
Ｇ1 ，Ｇ2 の次数を＃（Ｇ1 ），＃（Ｇ2 ）と定義する。但し、＃（Ｇ1 ）｜＃（Ｇ2 ）とする。拡張楕円離散対数問題が解けるとすれば、Ｐ＝ｕ1 Ｇ1 ＋ｕ2 Ｇ2 での係数ｕ1 ，ｕ2 及びＱ＝ｖ1 Ｇ1 ＋ｖ2 Ｇ2 での係数ｖ1 ，ｖ2 は求まり、楕円離散対数問題Ｑ＝ｒＰは、下記（20）のように解ける。
【００７６】
【数６】
0004450969.tif 000016
【００７７】
上記（17）を解く問題と拡張楕円離散対数問題との等価性について考察する。上記（17）が解けたとすると、下記（21）のｒi,j を求めることができる。
【００７８】
【数７】
0004450969.tif 000017
【００７９】
そして、下記（22）の式において、左辺の（ｎ−２）×（ｎ−２）の行列式が、Ｐn-1 ＝Ｇ1 ，Ｐn ＝Ｇ2 である＃（Ｇ2 ）に素であるという仮定のもとで、その下記（22）の式を解くことができる。行列式が＃（Ｇ2 ）に素でない場合には、上記（21）の別の解ｒi,j を選択できる。
【００８０】
【数８】
0004450969.tif 000018
【００８１】
この結果、上記（17）が解けるとすれば、下記（23）に示すＰi と（Ｇ1 ，Ｇ2 ）との拡張楕円離散対数問題も解ける。
【００８２】
【数９】
0004450969.tif 000019
【００８３】
これとは逆に、拡張楕円離散対数問題が解ければ、上記（17）が解けることを示す。Ｐi と（Ｇ1 ，Ｇ2 ）との拡張楕円離散対数問題を下記（24）のように定義し、ＰC と（Ｇ1 ，Ｇ2 ）との拡張楕円離散対数問題を下記（25）のように定義すると、下記（26）に示すような関係が成立する。
【００８４】
【数１０】
0004450969.tif 000020
【００８５】
ｖj とｒi,j が与えられている場合には、ｕi が解けることは明らかである。よって、上記（17）を解く問題と拡張楕円離散対数問題とは等価である。また、楕円曲線の群が周期的である場合、拡張楕円離散対数問題が楕円離散対数問題と等価であることは明らかである。よって、この場合、上記（17）を解く問題は楕円離散対数問題と等価になる。
【００８６】
〔エンティティ間の共通鍵に関する安全性〕
ｎ人のエンティティの結託により、エンティティＡ，エンティティＣ間の共通鍵を偽造する攻撃について考察する。エンティティＣの公開鍵Ｐc が上記（17）のように他のエンティティの公開鍵の線形結合によって表すことが可能であると仮定すると、下記（27），（28）のように、両エンティティＡ，Ｃ間の共通鍵Ｋac，Ｋcaが露呈する。エンティティＣの秘密鍵Ｓc が線形結合により書き表せる場合も同様に考えられる。
【００８７】
【数１１】
0004450969.tif 000021
【００８８】
しかしながら、上記（17）での係数ｕi を求めるには拡張楕円離散対数問題を解くことになり、このような攻撃は困難である。
【００８９】
もし、エンティティＡが自身の公開鍵Ｐa ，秘密鍵Ｓa から他のエンティティ間の共通鍵Ｋbcを偽造しようとしても不可能である。なぜなら、秘密鍵Ｓb ，Ｓc はエンティティＢ，Ｃの秘密情報であり、それらは秘密情報ｒなしでは求められないからである。よって、どのエンティティも共通鍵Ｋbcを偽造できない。
【００９０】
秘密鍵Ｓb ，Ｓc なしに結託エンティティＩの秘密鍵Ｓi から共通鍵Ｋbcを求める結託攻撃は、秘密鍵Ｓi から秘密鍵Ｓb ，Ｓc を求める場合と同じ問題になる。また、結託エンティティＩ，Ｊ間の共通鍵Ｋijから共通鍵Ｋbcを求める結託攻撃は、センタの秘密情報ｒを知らないので、困難な問題となる。共通鍵Ｋbcを求める問題は、Diffe-Hellman 型問題に帰着する。
【００９１】
ところで、エンティティＡは共通鍵Ｋab，Ｋacを算出することが可能であるので、共通鍵Ｋab，Ｋacから共通鍵Ｋbcを求めることができるとすれば、エンティティＡは他エンティティ間の共通鍵を偽造可能である。しかし、このような攻撃法は本発明には適用困難である。
【００９２】
以下、本発明の他の実施の形態である、各エンティティのＩＤ情報をベクトルに拡張した鍵共有方式について説明する。
【００９３】
エンティティＡのＩＤ情報であるベクトルＰa を下記（29）のように表す。
ベクトルＰa ＝（Ｐa1，Ｐa2，・・・，Ｐan）      …（29）
また、センタ１の秘密情報としてｎ×ｎの対称行列Ｒを下記（30）のように設定する。
【００９４】
【数１２】
0004450969.tif 000022
【００９５】
センタ１は、このベクトルＰa 及び対称行列Ｒを用い、下記（31）に従って、エンティティＡの秘密鍵（ベクトルＳa ）を求め、求めた秘密鍵を秘密裏にエンティティＡへ送付する。
【００９６】
【数１３】
0004450969.tif 000023
【００９７】
エンティティＡは、エンティティＢとの共通鍵Ｋabを下記（32）に従って生成する。但し、点と点との積はベイユペアリングの値とする。
【００９８】
【数１４】
0004450969.tif 000024
【００９９】
また、エンティティＢは、エンティティＡとの共通鍵Ｋbaを同様に生成する。そして、前述した実施の形態の第１例のように各エンティティＡ，Ｂ間のＩＤ情報の大小関係を考慮するようにした場合には、Ｋab＝Ｋbaとなり、同一の共通鍵を共有し合うことができる。
【０１００】
次に、この実施の形態における安全性について考察する。
〔センタの秘密情報に関する安全性〕
エンティティＣの公開鍵ベクトルＰc と秘密鍵ベクトルＳc とからセンタの秘密行列Ｒを得ることは、拡張楕円離散対数問題を解くことと等価であって、困難である。
エンティティＡの公開鍵ベクトルＰa とエンティティＢの公開鍵ベクトルＰb とから＜Ｐai，Ｐbj＞（１≦ｉ，ｊ≦ｎ）を計算し、これと下記（33）に示す共通鍵Ｋabとから行列Ｒの各成分ｒij（１≦ｉ，ｊ≦ｎ）を得ることは、拡張楕円離散対数問題が楕円離散対数問題とが等価であることと同様に、拡張離散対数問題と離散対数問題とで等価である。
【０１０１】
【数１５】
0004450969.tif 000025
【０１０２】
以上のことから、センタ１の秘密情報（対称行列Ｒ）は露呈しない。
【０１０３】
〔エンティティの秘密鍵に関する安全性〕
ｎ人のエンティティが結託してエンティティＣの秘密鍵ベクトルＳc を偽造する攻撃について考察する。エンティティＣの公開鍵ベクトルＰc が下記（34）のように他のエンティティの公開鍵ベクトルの線形結合によって表すことが可能であると仮定すると、前記（31）にこの線形結合を代入すると、下記（35）の関係式が成立するので、エンティティＣの秘密鍵ベクトルＳc が露呈する。
【０１０４】
【数１６】
0004450969.tif 000026
【０１０５】
しかし、前記（31）での成分を得るには拡張楕円離散対数問題を解く必要があり、このような攻撃は困難であるといえる。よって、安全性は拡張楕円離散対数問題を解くことの難しさに基づいている。
【０１０６】
〔エンティティ間の共通鍵に関する安全性〕
ｎ人のエンティティの結託により、エンティティＡ，エンティティＣ間の共通鍵を偽造する攻撃について考察する。エンティティＣの公開鍵ベクトルＰc が上記（34）のように他のエンティティの公開鍵ベクトルの線形結合によって表すことが可能であると仮定すると、下記（36），（37）のように、両エンティティＡ，Ｃ間の共通鍵Ｋac，Ｋcaが露呈する。エンティティＣの秘密鍵ベクトルＳc が線形結合により書き表せる場合も同様に考えられる。
【０１０７】
【数１７】
0004450969.tif 000027
【０１０８】
しかしながら、上記（34）での係数ｕi を求めるには拡張楕円離散対数問題を解くことになり、このような攻撃は困難である。
【０１０９】
また、この実施の形態にあっても、上述した実施の形態と同様に、あるエンティティが自身の共通鍵から他のエンティティ同士間の共通鍵を生成することは困難である。
【０１１０】
なお、エンティティのＩＤ情報をｎ×ｎの対称行列に拡張することも可能である。この場合、共通鍵行列ｋab＝（ｓij）と共通鍵行列ｋba＝（ｔji）とは、下記（38）の関係を満たす。
ｓij＝ｔji-1          …（38）
【０１１１】
なお、上述した例ではベイユペアリングを用いる場合について説明したが、楕円曲線上のペアリングとしてテイト（Ｔａｔｅ）ペアリングを利用する場合にあっても、同様に両エンティティ間で鍵共有を行える。
【０１１２】
また、ベイユペアリング及びテイトペアリングの何れの場合にあっても、鍵共有を行う際のペアリング＜Ｐ，Ｑ＞において、点Ｐの座標と点Ｑの座標とが異なる体に属するようにペアリングの計算を拡張することができる。また、点Ｐの座標を小さな体で定義するとペアリングの計算を高速に行うことができる。
【０１１３】
楕円曲線の定義体を変更する利点は、確実に共通鍵が１とならないようにできるという点、及び、高速に計算できるという点である。楕円曲線の定義体を変更する場合、つまり、２通りの定義体を用いる場合には、２通りの公開鍵への対応のさせ方が必要である。従来のＩＤ−ＮＩＫＳでは、エンティティがＩＤ情報によって決まる１通りの公開鍵と自身の秘密鍵とを用いて鍵共有を行っているが、この方式では、ＩＤ情報に基づいて、定義体が異なる同一の楕円曲線上の点へ、２通りの異なるやり方によって公開鍵を写像し、ＩＤ情報または公開鍵に基づき、一方のエンティティが何れか一方の定義体による公開鍵を使用し、他方のエンティティが他方の定義体による公開鍵を使用して、鍵共有を行う。
【０１１４】
全エンティティを２つのグループＧ1 ，Ｇ2 に分ける。グループＧ1 に属するエンティティはＰを含む群の元を、グループＧ2 に属するエンティティはＱを含む群の元を夫々ＩＤ情報として用いることにより、グループＧ1 のエンティティとグループＧ2 のエンティティとにおいて鍵を共有することが可能である。
各エンティティが２種類のＩＤ情報を有しており、エンティティＡとエンティティＢとの各ＩＤ情報に何らかの大小関係を示すアルゴリズムを設定し、何れのエンティティがどちらのＩＤ情報を使用するかを決定することにより、鍵の共有化を行える。
各エンティティが２種類のＩＤ情報を有しており、両エンティティ間で２種類の値を計算し、その２つの計算値を足し合わせる等、同じ値になる演算を用いて共通鍵を生成する。
Ｐを含む群の元とＱを含む群の元との間の変換を適切に定め、その変換をシステム固有の公開情報として用いることにより、鍵の共有化が可能である。
【０１１５】
なお、上述した例では代数曲線として楕円曲線を用いる場合について説明したが、超楕円曲線を用いる場合にあっても、超楕円離散対数問題及びペアリングを定義できるので、簡単に拡張することができる。
【０１１６】
図３は、本発明の記録媒体の実施の形態の構成を示す図である。ここに例示するプログラムは、各エンティティのＩＤ情報とセンタ固有の秘密情報とに基づき前述した手法にて各エンティティ固有の秘密鍵を生成する処理（エンティティのＩＤ情報に基づき楕円曲線上の点に写像して写像値を得るステップと、その写像値とセンタ固有の秘密情報とを用いて秘密鍵を生成するステップ）を含むか、または、エンティティ自身の秘密鍵と通信相手のエンティティの公開鍵とに基づき前述した手法にて共通鍵を生成する処理（通信相手のエンティティのＩＤ情報に基づき楕円曲線上の点に写像して写像値を得るステップと、その写像値とエンティティ自身の秘密鍵とを用いて共通鍵を生成するステップ）を含んでおり、以下に説明する記録媒体に記録されている。なお、コンピュータ４０は、センタ１側か、または、各エンティティ側に設けられている。
【０１１７】
図３において、コンピュータ４０とオンライン接続する記録媒体４１は、コンピュータ４０の設置場所から隔たって設置される例えばＷＷＷ(World Wide Web)のサーバコンピュータを用いてなり、記録媒体４１には前述の如きプログラム４１ａが記録されている。記録媒体４１から読み出されたプログラム４１ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【０１１８】
コンピュータ４０の内部に設けられた記録媒体４２は、内蔵設置される例えばハードディスクドライブまたはＲＯＭ等を用いてなり、記録媒体４２には前述の如きプログラム４２ａが記録されている。記録媒体４２から読み出されたプログラム４２ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【０１１９】
コンピュータ４０に設けられたディスクドライブ４０ａに装填して使用される記録媒体４３は、運搬可能な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシブルディスク等を用いてなり、記録媒体４３には前述の如きプログラム４３ａが記録されている。記録媒体４３から読み出されたプログラム４３ａがコンピュータ４０を制御することにより、各エンティティ固有の秘密鍵を生成するか、または、両エンティティ間の共通鍵を生成する。
【０１２０】
【発明の効果】
以上詳述したように、本発明では、各エンティティのＩＤ情報から生成する公開鍵を楕円曲線上で写像するようにしたので、予備通信を行うことなく両エンティティ間で容易に共通鍵を共有し合うことができる。また、本発明ではその安全性が代数曲線上の離散対数問題に置かれており、結託攻撃などの攻撃に対して強く、ＩＤ−ＮＩＫＳの発展に本発明は寄与できる。
【図面の簡単な説明】
【図１】本発明の暗号通信システムの構成を示す模式図である。
【図２】２人のエンティティ間における情報の通信状態を示す模式図である。
【図３】記録媒体の実施の形態の構成を示す図である。
【図４】ＩＤ−ＮＩＫＳのシステムの原理構成図である。
【符号の説明】
１  センタ
１１，２１  公開鍵生成器
１２，２２  共通鍵生成器
１３  暗号化器
２３  復号器
３０  通信路
４０  コンピュータ
４１，４２，４３  記録媒体
Ａ，Ｂ，Ｚ  エンティティ
【図１】
0004450969.tif 000028
【図２】
0004450969.tif 000029
【図３】
0004450969.tif 000030
【図４】
0004450969.tif 000031