(57)【特許請求の範囲】
【請求項１】
センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された他方のエンティティの公開鍵とから求めた共有鍵を利用して平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された前記一方のエンティティの公開鍵とから求めた、前記共有鍵と同一の共有鍵を利用して元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記各エンティティ固有の秘密鍵は、各エンティティの複数の公開鍵と各エンティティ固有の複数の乱数とを用い、複数個の各数それぞれを法として生成した複数の秘密鍵であり、各エンティティ装置は、生成した複数の秘密鍵と相手のエンティティの複数の公開鍵とを用いて前記共有鍵を生成するようにしており、前記センタ装置における４個の前記秘密鍵を生成する演算式は下記式（Ａ）であり、各エンティティ装置における前記共有鍵を生成する演算式は下記式（Ｂ）であることを特徴とする暗号通信方法。
【数１】
0003622072.tif 000033
但し、
ベクトルｓ11,i：エンティティｉの第１の秘密鍵
ベクトルｓ22,i：エンティティｉの第２の秘密鍵
ベクトルｓ21,i：エンティティｉの第３の秘密鍵
ベクトルｓ12,i：エンティティｉの第４の秘密鍵
ベクトルｖ1,i ：エンティティｉの第１の公開鍵
ベクトルｖ2,i ：エンティティｉの第２の公開鍵
Ｐ1 ，Ｐ2 ，Ｐ3 ：公開された素数
Ａ1 ，Ａ2 ：センタ装置秘密の乱数からなる対称行列
Ａ3 ：センタ装置秘密の乱数からなる行列
ベクトルγ1,i ：乱数からなる第１の個人乱数ベクトル
ベクトルγ2,i ：乱数からなる第２の個人乱数ベクトル
【数２】
0003622072.tif 000034
但し、
Ｋij：一方のエンティティ装置ｉが他方のエンティティ装置ｊに対して生成する 共有鍵
ベクトルｖ1,j ：エンティティｊの第１の公開鍵
ベクトルｖ2,j ：エンティティｊの第２の公開鍵
Ａ11,ij ′，Ａ22,ij ′，Ａ21,ij ′，Ａ12,ij ′：共有鍵Ｋijを生成するため の中間値
【請求項２】
センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された他方のエンティティの公開鍵とから求めた共有鍵を利用して平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された前記一方のエンティティの公開鍵とから求めた、前記共有鍵と同一の共有鍵を利用して元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記各エンティティ固有の秘密鍵は、各エンティティの複数の公開鍵と各エンティティ固有の複数の乱数とを用い、複数個の各数それぞれを法として生成した複数の秘密鍵であり、各エンティティ装置は、生成した複数の秘密鍵と相手のエンティティの複数の公開鍵とを用いて前記共有鍵を生成するようにしており、各エンティティの公開鍵はｄ個であり、前記センタ装置におけるｄ2 個の前記秘密鍵を生成する演算式が下記式（Ｃ）であり、各エンティティ装置における前記共有鍵を生成する演算式が下記式（Ｄ）であることを特徴とする暗号通信方法。
【数３】
0003622072.tif 000035
但し、
Ａyz（ｙ，ｚ＝１，２，…，ｄ）：ｎ×ｎの対称行列Ａを行方向，列方向共にｎ        1 ，ｎ2 ，…，ｎd 毎に区切った小行列（但し、ｎ＝ｎ1 ＋ｎ2 ＋…＋ｎd ）
ベクトルｓyz,i：エンティティｉのｄ2 個の秘密鍵
ベクトルｖz,i ：エンティティｉの公開鍵の列ベクトルｖi をｎ1 ，ｎ2 ，…，        ｎd の大きさで列方向に分割したベクトル
ベクトルγyz,i：エンティティｉの個人乱数の列ベクトルγz,i をｎ1 ，ｎ2 ，        …，ｎd の大きさで列方向に分割したベクトル
Ｐyz：公開された素数
【数４】
0003622072.tif 000036
但し、
Ｋij：一方のエンティティ装置ｉが他方のエンティティ装置ｊに対して生成する        共有鍵
ベクトルｖy,j ：エンティティｊの公開鍵の行ベクトルｖj をｎ1 ，ｎ2 ，…，        ｎd の大きさで行方向に分割したベクトル
Ａyz,ij ′：共有鍵Ｋijを生成するためのｄ2 個の中間値
【請求項３】
請求項２記載の各エンティティの公開鍵がｄ個、各エンティティの秘密鍵がｄ2 個となる組を複数組用いることを特徴とする暗号通信方法。
【請求項４】
センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された他方のエンティティの公開鍵とから求めた共有鍵を利用して平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された前記一方のエンティティの公開鍵とから求めた、前記共有鍵と同一の共有鍵を利用して元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記各エンティティ固有の秘密鍵は、各エンティティの複数の公開鍵と各エンティティ固有の複数の乱数とを用い、複数個の各数それぞれを法として生成した複数の秘密鍵であり、各エンティティ装置は、生成した複数の秘密鍵と相手のエンティティの複数の公開鍵とを用いて前記共有鍵を生成するようにしており、前記センタ装置における２ｄ個の前記秘密鍵を生成する演算式は下記式（Ｅ）であり、各エンティティ装置における前記共有鍵を生成する演算式は下記式（Ｆ）であることを特徴とする暗号通信方法。
【数５】
0003622072.tif 000037
但し、
ベクトルｓr,i ：エンティティｉのｄ個の秘密鍵
ベクトルｔr,i ：エンティティｉのｄ個の秘密鍵
Ａr ：センタ装置秘密の乱数からなる行列
Ｂr ＝ tＡr 
ベクトルｖr,i ：エンティティｉのｄ個の公開鍵
ベクトルγr,i ：乱数からなるｄ個の個人乱数ベクトル
Ｐr ：公開された素数
【数６】
0003622072.tif 000038
但し、
Ｋij：一方のエンティティ装置ｉが他方のエンティティ装置ｊに対して生成する        共有鍵
ベクトルｖr,j ：エンティティｊのｄ個の公開鍵
Ａr,ij′，Ｂr,ij′：共有鍵Ｋijを生成するための中間値
【請求項５】
各エンティティの特定情報をハッシュ関数を利用して計算することにより、各エンティティの前記複数の公開鍵を求めることを特徴とする請求項１〜４の何れかに記載の暗号通信方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報の内容が当事者以外にはわからないように情報を暗号化して通信する安全性が高い暗号通信方法に関する。
【０００２】
【従来の技術】
高度情報化社会と呼ばれる現代社会では、コンピュータネットワークを基盤として、ビジネス上の重要な文書・画像情報が電子的な情報という形で伝送通信されて処理される。このような電子情報は、容易に複写が可能である、複写物とオリジナルとの区別が困難であるという性質があり、情報保全の問題が重要視されている。特に、「コンピュータリソースの共有」，「マルチアクセス」，「広域化」の各要素を満たすコンピュータネットワークの実現が高度情報化社会の確立に不可欠であるが、これは当事者間の情報保全の問題とは矛盾する要素を含んでいる。このような矛盾を解消するための有効な手法として、人類の過去の歴史上主として軍事，外交面で用いられてきた暗号技術が注目されている。
【０００３】
暗号とは、情報の意味が当事者以外には理解できないように情報を交換することである。暗号において、誰でも理解できる元の文（平文）を第三者には意味がわからない文（暗号文）に変換することが暗号化であり、また、暗号文を平文に戻すことが復号であり、この暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗号化の過程及び復号の過程には、それぞれ暗号化鍵及び復号鍵と呼ばれる秘密の情報が用いられる。復号時には秘密の復号鍵が必要であるので、この復号鍵を知っている者のみが暗号文を復号でき、暗号化によって情報の秘密性が維持され得る。
【０００４】
暗号化鍵と復号鍵とは、等しくても良いし、異なっていても良い。両者の鍵が等しい暗号系は、共通鍵暗号系と呼ばれ、米国商務省標準局が採用したＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄｓ）はその典型例である。また、両者の鍵が異なる暗号系の一例として、公開鍵暗号系と呼ばれる暗号系が提案された。この公開鍵暗号系は、暗号系を利用する各ユーザ（エンティティ）が暗号化鍵と復号鍵とを一対ずつ作成し、暗号化鍵を公開鍵リストにて公開し、復号鍵のみを秘密に保持するという暗号系である。公開鍵暗号系では、この一対となる暗号化鍵と復号鍵とが異なり、一方向性関数を利用することによって暗号化鍵から復号鍵を割り出せないという特徴を持たせている。
【０００５】
公開鍵暗号系は、暗号化鍵を公開するという画期的な暗号系であって、高度情報化社会の確立に必要な上述した３つの要素に適合するものであり、情報通信技術の分野等での利用を図るべく、その研究が活発に行われ、典型的な公開鍵暗号系としてＲＳＡ暗号系が提案された。このＲＳＡ暗号系は、一方向性関数として素因数分解の困難さを利用して実現されている。また、離散対数問題を解くことの困難さ（離散対数問題）を利用した公開鍵暗号系も種々の手法が提案されてきた。
【０００６】
また、各エンティティの住所，氏名等の個人を特定するＩＤ（Ｉｄｅｎｔｉｔｙ）情報を利用する暗号系が提案された。この暗号系では、ＩＤ情報に基づいて送受信者間で共通の暗号化鍵を生成する。また、このＩＤ情報に基づく暗号技法には、（１）暗号文通信に先立って送受信者間での予備通信を必要とする方式と、（２）暗号文通信に先立って送受信者間での予備通信を必要としない方式とがある。特に、（２）の手法は予備通信が不要であるので、エンティティの利便性が高く、将来の暗号系の中枢をなすものと考えられている。
【０００７】
この（２）の手法による暗号系は、ＩＤ−ＮＩＫＳ（ＩＤ−ｂａｓｅｄ  ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ  ｋｅｙ  ｓｈａｒｉｎｇ  ｓｃｈｅｍｅ）と呼ばれており、通信相手のＩＤ情報を用いて予備通信を行うことなく暗号化鍵を共有する方式を採用している。ＩＤ−ＮＩＫＳは、送受信者間で公開鍵，秘密鍵を交換する必要がなく、また鍵のリスト及び第三者によるサービスも必要としない方式であり、任意のエンティティ間で安全に通信を行える。
【０００８】
図３は、このＩＤ−ＮＩＫＳのシステムの原理を示す図である。信頼できるセンタの存在を仮定し、このセンタを中心にして共有鍵生成システムを構成している。図３において、エンティティＸの特定情報であるエンティティＸの名前，住所，電話番号等のＩＤ情報は、ハッシュ関数ｈ（・）を用いてｈ（ＩＤＸ  ）で表す。センタは任意のエンティティＸに対して、センタ公開情報｛ＰＣｉ  ｝，センタ秘密情報｛ＳＣｉ  ｝及びエンティティＸのＩＤ情報ｈ（ＩＤＸ  ）に基づいて、以下のように秘密情報ＳＸｉを計算し、秘密裏にエンティティＸへ配布する。
ＳＸｉ＝Ｆｉ  （｛ＳＣｉ  ｝，｛ＰＣｉ  ｝，ｈ（ＩＤＸ  ））
【０００９】
エンティティＸは他の任意のエンティティＹとの間で、暗号化，復号のための共有鍵ＫＸＹを、エンティティＸ自身の秘密情報｛ＳＸｉ｝，センタ公開情報｛ＰＣｉ  ｝及び相手先のエンティティＹのＩＤ情報ｈ（ＩＤＹ  ）を用いて以下のように生成する。
ＫＸＹ＝ｆ（｛ＳＸｉ｝，｛ＰＣｉ  ｝，ｈ（ＩＤＹ  ））
また、エンティティＹも同様にエンティティＸへの鍵を共有鍵ＫＹＸを生成する。もし常にＫＸＹ＝ＫＹＸの関係が成立すれば、この鍵ＫＸＹ，ＫＹＸをエンティティＸ，Ｙ間で暗号化鍵，復号鍵として使用できる。
【００１０】
上述した公開鍵暗号系では、例えばＲＳＡ暗号系の場合にその公開鍵の長さは現在の電話番号の十数倍となり、極めて煩雑である。これに対して、ＩＤ−ＮＩＫＳでは、各ＩＤ情報を名簿という形式で登録しておけば、この名簿を参照して任意のエンティティとの間で共有鍵を生成することができる。従って、図３に示すようなＩＤ−ＮＩＫＳのシステムが安全に実現されれば、多数のエンティティが加入するコンピュータネットワーク上で便利な暗号系を構築できる。このような理由により、ＩＤ−ＮＩＫＳが将来の暗号系の中心になると期待されている。
【００１１】
【発明が解決しようとする課題】
通信相手のＩＤ情報を用いて予備通信を行うことなく暗号化鍵及び復号鍵となる共有鍵を互いに共有するようなＩＤ−ＮＩＫＳにあっては、複数のエンティティの結託等の攻撃に対して十分に安全であることが望まれる。しかしながら、以上のようなＩＤ−ＮＩＫＳにおいては、攻撃法が検討されて、適当な人数のエンティティが結託すればセンタの秘密パラメータが露呈するという問題を含んでいる。暗号学的に安全なＩＤ−ＮＩＫＳを構築できるか否かは、高度情報化社会に重要な問題であり、より理想的な暗号方式の探究が進められている。
【００１２】
そこで、本発明者等は、秘密鍵生成関数及び鍵共有関数が分離不可能であり、確率的に鍵共有が可能であり、安全性が高い新規のＩＤ−ＮＩＫＳによる暗号通信方法及び暗号通信システムを提案している（特願平１０−２６２０３５号）。特願平１０−２６２０３５号で提案したこのＩＤ−ＮＩＫＳ（以下、先行例という）は、２つの有限体上での演算により、１組の鍵ペアを計算し、この鍵ペアの双方を整数環上で加算することにより、乱数部を消去するようにしたものである。以下、先行例について簡単に説明する。
【００１３】
〔センタでの準備処理〕
センタは以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
0003622072.tif 000002
また、エンティティの特定情報であるエンティティのＩＤからｍビットの正整数からなるｎ次元の公開鍵ベクトルを生成する一方向性関数ベクトルｈ（・）も同時に公開する。但し、乱数ベクトルγｉ  と任意のエンティティの公開鍵ベクトルｖｊ  との内積がＰ及びＱを超えないように設定する。ここでは、議論を簡単にするために、パラメータｂを下記式（１）のように設定し、ｂ＞０の場合について考える。
ｂ＝ｋ−（ｌ＋ｍ＋  ｌｏｇ２  ｎ）    …（１）
【００１４】
〔エンティティの登録処理〕
エンティティｉに登録を依頼されたセンタは、準備した鍵とエンティティｉの公開鍵ベクトルｖｉ  （＝ベクトルｈ（ＩＤｉ  ））とを用いて以下の式（２）と式（３）とに従って、エンティティｉの秘密鍵ベクトルｓｉ  と秘密鍵ベクトルｔｉ  とを求め、求めたベクトルｓｉ  及びベクトルｔｉ  をエンティティｉへ秘密裏に送って、登録を完了する。但し、ｍｏｄは、二項演算子のｍｏｄである。即ち、ａ  ｍｏｄ  Ｐ  はａをＰで割った剰余を求める演算を表すとする。
【００１５】
【数７】
0003622072.tif 000003
【００１６】
〔エンティティ間の共有鍵の生成処理〕
エンティティｉは、以下の計算を行って、エンティティｊとの共有鍵Ｋｉｊを求める。まず、法Ｐ及び法Ｑによる式（４）及び式（５）に従って、それぞれＡｉｊ′及びＢｉｊ′を求め、次に整数環上で式（６）の計算によりＫｉｊを得る。
【００１７】
【数８】
0003622072.tif 000004
【００１８】
この先行例では、ｂを充分大きくした場合、約（１−１／２ｂ  ）４  という極めて高い確率で互いに鍵を共有することが可能である。
【００１９】
本発明は斯かる事情に鑑みてなされたものであって、先行例を改良したものであり、より安全性を高くできるＩＤ−ＮＩＫＳによる暗号通信方法を提供することを目的とする。
【００２０】
【課題を解決するための手段】
請求項１に係る暗号通信方法は、センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された他方のエンティティの公開鍵とから求めた共有鍵を利用して平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された前記一方のエンティティの公開鍵とから求めた、前記共有鍵と同一の共有鍵を利用して元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記各エンティティ固有の秘密鍵は、各エンティティの複数の公開鍵と各エンティティ固有の複数の乱数とを用い、複数個の各数それぞれを法として生成した複数の秘密鍵であり、各エンティティ装置は、生成した複数の秘密鍵と相手のエンティティの複数の公開鍵とを用いて前記共有鍵を生成するようにしており、前記センタ装置における４個の前記秘密鍵を生成する演算式は下記式（Ａ）であり、各エンティティ装置における前記共有鍵を生成する演算式は下記式（Ｂ）であることを特徴とする。
【００２１】
【数９】
0003622072.tif 000005
【００２２】
但し、
ベクトルｓ11,i：エンティティｉの第１の秘密鍵
ベクトルｓ22,i：エンティティｉの第２の秘密鍵
ベクトルｓ21,i：エンティティｉの第３の秘密鍵
ベクトルｓ12,i：エンティティｉの第４の秘密鍵
ベクトルｖ1,i ：エンティティｉの第１の公開鍵
ベクトルｖ2,i ：エンティティｉの第２の公開鍵
Ｐ1 ，Ｐ2 ，Ｐ3 ：公開された素数
Ａ1 ，Ａ2 ：センタ装置秘密の乱数からなる対称行列
Ａ3 ：センタ装置秘密の乱数からなる行列
ベクトルγ1,i ：乱数からなる第１の個人乱数ベクトル
ベクトルγ2,i ：乱数からなる第２の個人乱数ベクトル
【００２３】
【数１０】
0003622072.tif 000006
【００２４】
但し、
Ｋij：一方のエンティティ装置ｉが他方のエンティティ装置ｊに対して生成する 共有鍵
ベクトルｖ1,j ：エンティティｊの第１の公開鍵
ベクトルｖ2,j ：エンティティｊの第２の公開鍵
Ａ11,ij ′，Ａ22,ij ′，Ａ21,ij ′，Ａ12,ij ′：共有鍵Ｋijを生成するため の中間値
【００２８】
請求項２に係る暗号通信方法は、センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された他方のエンティティの公開鍵とから求めた共有鍵を利用して平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された前記一方のエンティティの公開鍵とから求めた、前記共有鍵と同一の共有鍵を利用して元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記各エンティティ固有の秘密鍵は、各エンティティの複数の公開鍵と各エンティティ固有の複数の乱数とを用い、複数個の各数それぞれを法として生成した複数の秘密鍵であり、各エンティティ装置は、生成した複数の秘密鍵と相手のエンティティの複数の公開鍵とを用いて前記共有鍵を生成するようにしており、各エンティティの公開鍵はｄ個であり、前記センタ装置におけるｄ2 個の前記秘密鍵を生成する演算式が下記式（Ｃ）であり、各エンティティ装置における前記共有鍵を生成する演算式が下記式（Ｄ）であることを特徴とする。
【００２９】
【数１１】
0003622072.tif 000007
【００３０】
但し、
Ａｙｚ（ｙ，ｚ＝１，２，…，ｄ）：ｎ×ｎの対称行列Ａを行方向，列方向共にｎ１  ，ｎ２  ，…，ｎｄ  毎に区切った小行列（但し、ｎ＝ｎ１  ＋ｎ        ２  ＋…＋ｎｄ  ）
ベクトルｓｙｚ，ｉ：エンティティｉのｄ２  個の秘密鍵
ベクトルｖｚ，ｉ  ：エンティティｉの公開鍵の列ベクトルｖｉ  をｎ１  ，ｎ        ２  ，…，ｎｄ  の大きさで列方向に分割したベクトル
ベクトルγｙｚ，ｉ：エンティティｉの個人乱数の列ベクトルγｚ，ｉ  をｎ１  ，ｎ２  ，…，ｎｄ  の大きさで列方向に分割したベクトル
Ｐｙｚ：公開された素数
【００３１】
【数１２】
0003622072.tif 000008
【００３２】
但し、
Ｋij：一方のエンティティ装置ｉが他方のエンティティ装置ｊに対して                生成する共有鍵
ベクトルｖy,j ：エンティティｊの公開鍵の行ベクトルｖj をｎ1 ，ｎ2 ，…，        ｎd の大きさで行方向に分割したベクトル
Ａyz,ij ′：共有鍵Ｋijを生成するためのｄ2 個の中間値
【００３３】
請求項３に係る暗号通信方法は、請求項２記載の各エンティティの公開鍵がｄ個、各エンティティの秘密鍵がｄ2 個となる組を複数組用いることを特徴とする。
【００３４】
請求項４に係る暗号通信方法は、センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された他方のエンティティの公開鍵とから求めた共有鍵を利用して平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵と公開された前記一方のエンティティの公開鍵とから求めた、前記共有鍵と同一の共有鍵を利用して元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記各エンティティ固有の秘密鍵は、各エンティティの複数の公開鍵と各エンティティ固有の複数の乱数とを用い、複数個の各数それぞれを法として生成した複数の秘密鍵であり、各エンティティ装置は、生成した複数の秘密鍵と相手のエンティティの複数の公開鍵とを用いて前記共有鍵を生成するようにしており、前記センタ装置における２ｄ個の前記秘密鍵を生成する演算式は下記式（Ｅ）であり、各エンティティ装置における前記共有鍵を生成する演算式は下記式（Ｆ）であることを特徴とする。
【００３５】
【数１３】
0003622072.tif 000009
【００３６】
但し、
ベクトルｓr,i ：エンティティｉのｄ個の秘密鍵
ベクトルｔr,i ：エンティティｉのｄ個の秘密鍵
Ａr ：センタ装置秘密の乱数からなる行列
Ｂr ＝ tＡr 
ベクトルｖr,i ：エンティティｉのｄ個の公開鍵
ベクトルγr,i ：乱数からなるｄ個の個人乱数ベクトル
Ｐr ：公開された素数
【００３７】
【数１４】
0003622072.tif 000010
【００３８】
但し、
Ｋij：一方のエンティティ装置ｉが他方のエンティティ装置ｊに対して生成する        共有鍵
ベクトルｖr,j ：エンティティｊのｄ個の公開鍵
Ａr,ij′，Ｂr,ij′：共有鍵Ｋijを生成するための中間値
【００３９】
請求項５に係る暗号通信方法は、請求項１〜４の何れかにおいて、各エンティティの特定情報をハッシュ関数を利用して計算することにより、各エンティティの前記複数の公開鍵を求めることを特徴とする。
【００４２】
本発明では、各エンティティの公開鍵を複数個用いるようにしており、これらの複数の公開鍵を組み合わせて乱数を消去するようにしたので、乱数消去の複雑さが増して、先行例よりも安全性の向上を図れる。また、乱数を分割したので、桁の繰り上がり問題をより軽減できる。
【００４３】
【発明の実施の形態】
図１は、本発明の暗号通信システムの構成を示す模式図である。情報の隠匿を信頼できるセンタ１が設定されており、このセンタ１としては、例えば社会の公的機関を該当できる。このセンタ１と、この暗号系システムを利用するユーザとしての複数の各エンティティａ，ｂ，…，ｚとは秘密通信路２ａ，２ｂ，…，２ｚにより接続されており、この秘密通信路２ａ，２ｂ，…，２ｚを介してセンタ１から秘密の鍵情報が各エンティティａ，ｂ，…，ｚへ伝送されるようになっている。また、２人のエンティティの間には通信路３ａｂ，３ａｚ，３ｂｚ，…が設けられており、この通信路３ａｂ，３ａｚ，３ｂｚ，…を介して通信情報を暗号化した暗号文が互いのエンティティ間で伝送されるようになっている。
【００４４】
（第１実施の形態）
以下に、本発明のＩＤ−ＮＩＫＳの第１実施の形態（各エンティティで２つの公開鍵を使用する方式）について説明する。
【００４５】
〔センタ１での準備処理〕
センタ１は以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
0003622072.tif 000011
また、エンティティの特定情報であるエンティティのＩＤからｍビットの正整数からなるｎ次元の公開鍵ベクトルを生成する２通りの一方向性関数ベクトルｈ１  （・），ｈ２  （・）も同時に公開する。但し、パラメータｂを下記式のように設定し、ｂ＞０の場合について考える。
ｂ＝ｋ−（ｌ＋ｍ＋  ｌｏｇ２  ｎ）
【００４６】
〔エンティティの登録処理〕
エンティティｉに登録を依頼されたセンタ１は、準備した鍵とエンティティｉの公開鍵ベクトルｖ１，ｉ  （＝ベクトルｈ１  （ＩＤｉ  ））及び公開鍵ベクトルｖ２，ｉ  （＝ベクトルｈ２  （ＩＤｉ  ））とを用いて以下の式（７）〜式（１０）に従って、エンティティｉの秘密鍵ベクトルｓ１１，ｉ，秘密鍵ベクトルｓ１２，ｉ，秘密鍵ベクトルｓ２１，ｉ，秘密鍵ベクトルｓ２２，ｉを求め、求めたこれらの各ベクトルをエンティティｉへ秘密裏に送って、登録を完了する。なお、ｍｏｄは、二項演算子のｍｏｄである。即ち、ａ  ｍｏｄ  Ｐ  はａをＰで割った剰余を求める演算を表すとする。
【００４７】
【数１５】
0003622072.tif 000012
【００４８】
〔エンティティ間の共有鍵の生成処理〕
エンティティｉは、以下の計算を行って、エンティティｊとの共有鍵Ｋｉｊを求める。まず、法Ｐ１  及び法Ｐ２  において式（１１）及び式（１２）に従って、それぞれＡ１１，ｉｊ  ′及びＡ２２，ｉｊ  ′を求め、次に、法Ｐ３  において式（１３）及び式（１４）に従って、それぞれＡ２１，ｉｊ  ′及びＡ１２，ｉｊ  ′を求め、次に、整数環上で式（１５）の計算によりＫｉｊを得る。
【００４９】
【数１６】
0003622072.tif 000013
【００５０】
ここで、先行例と同様に、ｂを十分大きくとる場合には、圧倒的に高い確率でＫｉｊ＝Ｋｊｉが成立する。
【００５１】
次に、上述した暗号システムにおけるエンティティ間の情報の通信について説明する。図２は、２人のエンティティａ，ｂ間における情報の通信状態を示す模式図である。図２の例は、エンティティａが平文（メッセージ）Ｍを暗号文Ｃに暗号化してそれをエンティティｂへ伝送し、エンティティｂがその暗号文Ｃを元の平文（メッセージ）Ｍに復号する場合を示している。
【００５２】
エンティティａ側には、エンティティｂの個人識別情報ＩＤｂ  を入力し、ハッシュ関数を利用してベクトルｖ１，ｂ  及びｖ２，ｂ  （公開鍵）を得る公開鍵生成器１１と、センタ１から送られる秘密のベクトルｓ１１，ａ，ｓ２２，ａ，ｓ２１，ａ及びｓ１２，ａと公開鍵生成器１１からの公開鍵であるベクトルｖ１，ｂ  及びｖ２，ｂ  とに基づいてエンティティａが求めるエンティティｂとの共有鍵Ｋａｂを生成する共有鍵生成器１２と、共有鍵Ｋａｂを用いて平文（メッセージ）Ｍを暗号文Ｃに暗号化して通信路３０へ出力する暗号化器１３とが備えられている。
【００５３】
また、エンティティｂ側には、エンティティａの個人識別情報ＩＤａ  を入力し、ハッシュ関数を利用してベクトルｖ１，ａ  及びｖ２，ａ  （公開鍵）を得る公開鍵生成器２１と、センタ１から送られる秘密のベクトルｓ１１，ｂ，ｓ２２，ｂ，ｓ２１，ｂ及びｓ１２，ｂと公開鍵生成器２１からの公開鍵であるベクトルｖ１，ａ  及びｖ２，ａ  とに基づいてエンティティｂが求めるエンティティａとの共有鍵Ｋｂａを生成する共有鍵生成器２２と、共有鍵Ｋｂａを用いて通信路３０から入力した暗号文Ｃを平文（メッセージ）Ｍに復号して出力する復号器２３とが備えられている。
【００５４】
次に、動作について説明する。エンティティａからエンティティｂへ情報を伝送しようとする場合、まず、エンティティｂの個人識別情報ＩＤｂ  が公開鍵生成器１１に入力されてベクトルｖ１，ｂ  及びｖ２，ｂ  （公開鍵）が得られ、得られたベクトルｖ１，ｂ  及びｖ２，ｂ  が共有鍵生成器１２へ送られる。また、センタ１から式（７）〜（１０）に従って求められたベクトルｓ１１，ａ，ｓ２２，ａ，ｓ２１，ａ及びｓ１２，ａが共有鍵生成器１２へ入力される。そして、式（１１）〜（１５）に従って共有鍵Ｋａｂが求められ、暗号化器１３へ送られる。暗号化器１３において、この共有鍵Ｋａｂを用いて平文（メッセージ）Ｍが暗号文Ｃに暗号化され、暗号文Ｃが通信路３０を介して伝送される。
【００５５】
通信路３０を伝送された暗号文Ｃはエンティティｂの復号器２３へ入力される。エンティティａの個人識別情報ＩＤａ  が公開鍵生成器２１に入力されてベクトルｖ１，ａ  及びｖ２，ａ  （公開鍵）が得られ、得られたベクトルｖ１，ａ  及びｖ２，ａ  が共有鍵生成器２２へ送られる。また、センタ１から式（７）〜（１０）に従って求められたベクトルｓ１１，ｂ，ｓ２２，ｂ，ｓ２１，ｂ及びｓ１２，ｂが共有鍵生成器２２へ入力される。そして、式（１１）〜（１５）に従って共有鍵Ｋｂａが求められ、復号器２３へ送られる。復号器２３において、この共有鍵Ｋｂａを用いて暗号文Ｃが平文（メッセージ）Ｍに復号される。
【００５６】
次に、この暗号化方式の形式的表現について説明する。第１実施の形態における暗号化方式の理解を容易にするために、上記（７）〜（１０）の各式を、以下のように各小行列に対応させて表現するものと定義する。この形式的表現における行列とベクトルとの積演算は、各小行列間の区切りを越えて加算を行わない点について通常の行列の積演算と若干異なっている。また、（  ）内は法を表す。
【００５７】
【数１７】
0003622072.tif 000014
【００５８】
また、上記式（１１）〜（１４）は以下のように表される。
【００５９】
【数１８】
0003622072.tif 000015
【００６０】
行列Ａについて、Ａの全ての小行列の和を求める操作をΣＡで表現すれば、共有鍵Ｋｉｊは以下のように表すことができる。
【００６１】
【数１９】
0003622072.tif 000016
【００６２】
この形式的表現によると、第１実施の形態は法まで含めた場合に対称行列を用いた方式と考えられ、乱数項を除けば従来の積和型ＮＩＫＳと類似していることが分かる。従って、法まで含んだ対称行列を用いれば、先行例のＮＩＫＳは一般的に表記できることになる。
【００６３】
（第２実施の形態）
以下に、本発明のＩＤ−ＮＩＫＳの第２実施の形態（各エンティティでｄ個の公開鍵を使用する一般化方式）について説明する。第２実施の形態では、ｎ１  ，ｎ２  ，…，ｎｄ  の大きさのｄ個の公開鍵を用いる。ｎ×ｎの対称行列Ａを用意し、行方向及び列方向にそれぞれｎ１  ，ｎ２  ，…，ｎｄ  毎に区切った小行列をＡｙｚ（ｙ，ｚ＝１，２，…，ｄ）で表す。但し、ｎ＝ｎ１  ＋ｎ２  ＋…＋ｎｄ  とする。
【００６４】
Ａが対称行列であるので、行列Ａの（ｙ，ｚ）−小行列に関して、Ａｙｚ＝  ｔＡｚｙが成立する。また、各小行列内では法は同一のものとし、法に関してＰｙｚ＝Ｐｚｙが満たされるものとする。更に、乱数項は共有鍵生成時に消去される必要があるので、ベクトルｏを零ベクトルとして、以下の式（１６）を満たすものとする。この場合、エンティティｉの秘密鍵はｄ２  個の式によって表現される。
【００６５】
【数２０】
0003622072.tif 000017
【００６６】
〔センタ１での準備処理〕
センタ１は以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
0003622072.tif 000018
また、エンティティのＩＤからｍビットの正整数からなるｎ次元の公開鍵ベクトルを生成する一方向性関数ベクトルｈ（・）も同時に公開する。但し、パラメータｂｒ  （ｒ＝１，２，…，ｄ）を下記式のように設定し、ｂｒ  ＞０の場合について考える。
ｂｒ  ＝ｋ−（ｌ＋ｍ＋  ｌｏｇ２  ｎｒ  ）
【００６７】
〔エンティティの登録処理〕
エンティティｉに登録を依頼されたセンタ１は、準備した鍵とエンティティｉの公開鍵ベクトルｖｉ  （＝ベクトルｈ（ＩＤｉ  ））とを用いて以下の式（１７）に従って、エンティティｉのｄ２  個の秘密鍵ベクトルｓｙｚ，ｉを求め、求めたこれらの各ベクトルをエンティティｉへ秘密裏に送って、登録を完了する。但し、ベクトルｖｚ，ｉ  及びベクトルγｙｚ，ｉは、それぞれ、列ベクトルｖｉ  及びベクトルγｚ，ｉ  をｎ１  ，ｎ２  ，…，ｎｄ  の大きさで列方向に分割したベクトルを表す。また、ｍｏｄは、二項演算子のｍｏｄである。
【００６８】
【数２１】
0003622072.tif 000019
【００６９】
〔エンティティ間の共有鍵の生成処理〕
エンティティｉは、以下の計算を行って、エンティティｊとの共有鍵Ｋｉｊを求める。まず、それぞれの法Ｐｙｚについて式（１８）に従って、Ａｙｚ，ｉｊ  ′を求め、次に、整数環上で式（１９）の計算によりＫｉｊを得る。
【００７０】
【数２２】
0003622072.tif 000020
【００７１】
第２実施の形態における鍵共有（Ｋｉｊ＝Ｋｊｉが成立する）について検証する。式（１７）を式（１８）に代入すると、以下の式（２０），（２１）のようになる。すべてのｂｒ  を十分大きくとる場合には、高い確率で式（２１）の第１式が成立する。この場合、式（１９）を計算すると、式（１６）より乱数項が消去されるので、高い確率でＫｉｊ＝Ｋｊｉが成立する。
【００７２】
【数２３】
0003622072.tif 000021
【００７３】
なお、エンティティ間の情報の通信動作については、第１実施の形態と同様であるので、その説明は省略する。
【００７４】
第２実施の形態に対して前述の形式的表現を用いると、エンティティｉのｄ２  個の秘密鍵をまとめて以下のように表現できる。
【００７５】
【数２４】
0003622072.tif 000022
【００７６】
また、共有鍵Ｋｉｊは以下のように表現できる。
【００７７】
【数２５】
0003622072.tif 000023
【００７８】
（第３実施の形態）
以下に、本発明のＩＤ−ＮＩＫＳの第３実施の形態（第２実施の形態での公開鍵を複数組使用する一般化方式）について説明する。第３実施の形態は、第２実施の形態における公開鍵を複数組（ｃ組）準備し、これらのｃ組全体の和をとって初めて乱数が消去されるようにした一般化方式である。以下の例では、ｃ＝２とし、ｎ１  ，ｎ２  ，…，ｎｄ  の大きさのｄ個の公開鍵と、ｎ１  ″，ｎ２  ″，…，ｎｅ  ″の大きさのｅ個の公開鍵とを用いる場合について説明する。
【００７９】
〔センタ１での準備処理〕
センタ１は以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
0003622072.tif 000024
【００８０】
〔エンティティの登録処理〕
エンティティｉに登録を依頼されたセンタ１は、準備した鍵とエンティティｉの公開鍵ベクトルｖｉ  （＝ベクトルｈ（ＩＤｉ  ））とを用いて以下の式（２２）及び（２３）に従って、エンティティｉのｄ２  個の秘密鍵ベクトルｓｙｚ，ｉ及びｅ２  個の秘密鍵ベクトルｔｙｚ，ｉを求め、求めたこれらの各ベクトルをエンティティｉへ秘密裏に送って、登録を完了する。但し、ベクトルｖｚ，ｉ  及びベクトルγｙｚ，ｉは、それぞれ、列ベクトルｖｉ  及びベクトルγｚ，ｉ  をｎ１  ，ｎ２  ，…，ｎｄ  の大きさで列方向に分割したベクトルを表し、ベクトルｖｚ，ｉ  ″及びベクトルδｙｚ，ｉは、それぞれ、列ベクトルｖｉ  及びベクトルδｚ，ｉ  をｎ１  ″，ｎ２  ″，…，ｎｅ  ″の大きさで列方向に分割したベクトルを表し、また、ｍｏｄは、二項演算子のｍｏｄである。ここで、ベクトルｖｉ  については、分割の方法が異なるだけで、式（２２），（２３）共に同一のベクトルを使用している。
【００８１】
【数２６】
0003622072.tif 000025
【００８２】
なお、乱数項については、これらの２組の鍵を用いて初めて消去されるように、下記式（２４）を満たすように設定する。
【００８３】
【数２７】
0003622072.tif 000026
【００８４】
〔エンティティ間の共有鍵の生成処理〕
エンティティｉは、以下の計算を行って、エンティティｊとの共有鍵Ｋｉｊを求める。まず、それぞれの法Ｐｙｚ，Ｑｙｚについて式（２５），式（２６）に従って、Ａｙｚ，ｉｊ  ′，Ｂｙｚ，ｉｊ  ′を求め、次に、整数環上で式（２７）の計算によりＫｉｊを得る。
【００８５】
【数２８】
0003622072.tif 000027
【００８６】
式（２４）よりすべての項の和をとれば乱数項は消去されるので、第２実施の形態と同様に、すべてのｂｒ  を十分大きくとる場合には、高い確率でＫｉｊ＝Ｋｊｉが成立する。
【００８７】
なお、先行例は、この第３実施の形態において、ｃ＝２，ｄ＝ｅ＝１とした場合に相当することが分かる。
【００８８】
なお、エンティティ間の情報の通信動作については、第１実施の形態と同様であるので、その説明は省略する。
【００８９】
（第４実施の形態）
以下に、本発明のＩＤ−ＮＩＫＳの第４実施の形態（秘密鍵の使用を２ｄ個に制限した方式）について説明する。第２実施の形態ではｄ（ｄ＋１）／２個の多くの秘密鍵を持たねばならず、また、第３実施の形態では第２実施の形態の更に約ｃ倍の秘密鍵を持つ必要があり、それらの方式をそのまま利用することは実用的でない。そこで、第４実施の形態として、使用する秘密鍵の個数を２ｄ個に抑えた実用的な方式を説明する。
【００９０】
〔センタ１での準備処理〕
センタ１は以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
0003622072.tif 000028
また、エンティティのＩＤからｍビットの正整数からなるｄ個のｎ次元の公開鍵ベクトルｖｒ，ｉ  ＝ベクトルｈｒ  （ＩＤｉ  ）（ｒ＝１，２，…，ｄ）を生成するｄ通りの一方向性関数ベクトルｈ１  （・），ｈ２  （・），…，ｈｄ  （・）も同時に公開する。但し、パラメータｂを下記式のように設定し、ｂ＞０の場合について考える。
ｂ＝ｋ−（ｌ＋ｍ＋  ｌｏｇ２  ｎ）
【００９１】
〔エンティティの登録処理〕
エンティティｉに登録を依頼されたセンタ１は、準備した鍵とエンティティｉのｄ個の公開鍵ベクトルｖ１，ｉ  ，ｖ２，ｉ  ，…，ｖｄ，ｉ  とを用いて以下の式（２８）及び（２９）に従って、エンティティｉの各ｄ個の秘密鍵ベクトルｓｒ，ｉ  及びｔｒ，ｉ  を求め、求めたこれらの各ベクトルをエンティティｉへ秘密裏に送って、登録を完了する。但し、Ｂｒ  ＝  ｔＡｒ  と置き、また、添字がｄ＋１になる場合は１に変換して扱うものとする。
【００９２】
【数２９】
0003622072.tif 000029
【００９３】
〔エンティティ間の共有鍵の生成処理〕
エンティティｉは、以下の計算を行って、エンティティｊとの共有鍵Ｋｉｊを求める。まず、法Ｐｒ  について式（３０），式（３１）に従って、Ａｒ，ｉｊ′，Ｂｒ，ｉｊ′を求め、次に、整数環上で式（３２）の計算によりＫｉｊを得る。
【００９４】
【数３０】
0003622072.tif 000030
【００９５】
なお、エンティティ間の情報の通信動作については、第１実施の形態と同様であるので、その説明は省略する。
【００９６】
この第４実施の形態における形式的表現を以下に表す。
〔ｄ＝２の場合（第３実施の形態に該当）〕
【００９７】
【数３１】
0003622072.tif 000031
【００９８】
〔ｄ≧３の場合（第２実施の形態に該当）〕
【００９９】
【数３２】
0003622072.tif 000032
【０１００】
【発明の効果】
以上詳述したように、本発明では、大きな素数を法とする有限体上の演算をした後に、整数環上の加算により乱数を消去するようにしており、実用的に十分高い確率で鍵を共有できる。また、先行例を改良し、複数の公開鍵を用いて公開鍵ベクトルのサイズをより大きくするようにしたので、先行例と比べてよりより安全性を高くできる。
【図面の簡単な説明】
【図１】本発明の暗号通信システムの構成を示す模式図である。
【図２】２人のエンティティ間における情報の通信状態を示す模式図である。
【図３】ＩＤ−ＮＩＫＳのシステムの原理構成図である。
【符号の説明】
１  センタ
１１，２１  公開鍵生成器
１２，２２  共有鍵生成器
１３  暗号化器
２３  復号器
３０  通信路
【図１】
0003622072.tif 000039
【図２】
0003622072.tif 000040
【図３】
0003622072.tif 000041