(57)【特許請求の範囲】
【請求項１】
エンティティの特定情報を複数のブロックに分割した分割特定情報を用いて前記エンティティ固有の秘密鍵を生成する装置において、前記複数のブロックの中の１つのブロックの分割特定情報に対して複数の秘密鍵を生成する第１生成手段と、前記１つのブロック以外の残りのブロックの分割特定情報に対して各１つの秘密鍵を生成する第２生成手段とを備え、前記第１生成手段及び第２生成手段で生成した秘密鍵を前記エンティティ固有の秘密鍵としており、前記エンティティ固有の秘密鍵を生成する演算式は以下であることを特徴とする秘密鍵生成装置。
【数１】
0003657803.tif 000027
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及 びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【数２】
0003657803.tif 000028
【請求項２】
各エンティティの特定情報を複数のブロックに分割した分割特定情報を用いて生成した各エンティティ固有の秘密鍵を使用して求めた共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、前記複数のブロックの中の１つのブロックの分割特定情報に対して複数の秘密鍵を生成する第１生成手段と、前記１つのブロック以外の残りのブロックの分割特定情報に対して各１つの秘密鍵を生成する第２生成手段と、前記第１生成手段及び第２生成手段で生成した秘密鍵に含まれている、暗号文の送信先である相手のエンティティの分割特定情報に対応する成分を選び出す手段と、選び出した成分を用いて共通鍵を生成する手段と、生成した共通鍵を用いて平文を暗号文に暗号化する手段とを備えており、前記各エンティティ固有の秘密鍵を生成する演算式は以下であることを特徴とする暗号化装置。
【数３】
0003657803.tif 000029
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【数４】
0003657803.tif 000030
【請求項３】
前記共通鍵を生成する演算式は以下であることを特徴とする請求項２記載の暗号化装置。
【数５】
0003657803.tif 000031
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【請求項４】
センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記センタ装置が複数設けられており、その複数のセンタ装置夫々は、各エンティティの特定情報を複数のブロックに分割した分割特定情報を用いて各エンティティ固有の秘密鍵を生成することとし、前記複数のセンタ装置の中の１つのセンタ装置は、前記複数のブロックの中の１つのブロックの分割特定情報に対して複数の秘密鍵を生成し、前記１つのセンタ装置以外の残りのセンタ装置夫々は、前記１つのブロック以外の残りのブロックの分割特定情報に対して１つの秘密鍵を生成し、各エンティティ装置は、自身固有の秘密鍵に含まれている、相手のエンティティの分割特定情報に対応する成分を用いて前記共通鍵を生成するようにしており、前記センタ装置における秘密鍵を生成する演算式は以下であることを特徴とする暗号通信方法。
【数６】
0003657803.tif 000032
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【数７】
0003657803.tif 000033
【請求項５】
前記共通鍵を生成する演算式は以下であることを特徴とする請求項４記載の暗号通信方法。
【数８】
0003657803.tif 000034
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【請求項６】
送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、各エンティティの特定情報を複数のブロックに分割した分割特定情報を用いて以下の演算式に従い各エンティティ固有の秘密鍵を生成して各エンティティ装置へ送付する複数のセンタ装置と、該センタ装置から送付された自身の秘密鍵に含まれている、通信対象のエンティティ装置の分割特定情報に対応する成分を使用して以下の演算式に従い、前記暗号化処理及び復号処理に用いる共通鍵を生成する複数のエンティティ装置とを有することを特徴とする暗号通信システム。
【数９】
0003657803.tif 000035
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【数１０】
0003657803.tif 000036
【数１１】
0003657803.tif 000037
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【請求項７】
暗号通信システムのエンティティ装置に設けられており、平文から暗号文への暗号化処理及び暗号文から平文への復号処理に用いる共通鍵を生成する共通鍵生成装置において、エンティティの特定情報を複数のブロックに分割した分割特定情報毎に以下の演算式に従って作成された前記エンティティ固有の秘密鍵を格納する格納手段と、格納されている秘密鍵の中から、通信相手のエンティティの分割特定情報に対応する成分を選び出す選出手段と、選び出した成分を使用して以下の演算式に従って前記共通鍵を生成する手段とを備えることを特徴とする共通鍵生成装置。
【数１２】
0003657803.tif 000038
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【数１３】
0003657803.tif 000039
【数１４】
0003657803.tif 000040
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【請求項８】
暗号通信システムにおける平文から暗号文への暗号化処理及び暗号文から平文への復号処理に用いる共通鍵をエンティティ装置で生成するためのコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、前記エンティティの特定情報を複数のブロックに分割した分割特定情報毎に以下の演算式に従って作成された前記エンティティ固有の秘密鍵の中から、通信相手のエンティティの分割特定情報に対応する成分を選び出させる手順と、コンピュータに、選び出した成分を使用して以下の演算式に従って前記共通鍵を生成させる手順とを含むコンピュータプログラムを記録してあることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【数１５】
0003657803.tif 000041
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【数１６】
0003657803.tif 000042
【数１７】
0003657803.tif 000043
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、エンティティ固有の秘密鍵を生成する秘密鍵生成装置、情報の内容が当事者以外にはわからないように情報を暗号化する暗号化装置、暗号文にて通信を行う暗号通信方法及び暗号通信システム、共通鍵を生成する共通鍵生成装置並びに共通鍵を生成するためのコンピュータプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
高度情報化社会と呼ばれる現代社会では、コンピュータネットワークを基盤として、ビジネス上の重要な文書・画像情報が電子的な情報という形で伝送通信されて処理される。このような電子情報は、容易に複写が可能である、複写物とオリジナルとの区別が困難であるという性質があり、情報保全の問題が重要視されている。特に、「コンピュータリソースの共有」，「マルチアクセス」，「広域化」の各要素を満たすコンピュータネットワークの実現が高度情報化社会の確立に不可欠であるが、これは当事者間の情報保全の問題とは矛盾する要素を含んでいる。このような矛盾を解消するための有効な手法として、人類の過去の歴史上主として軍事，外交面で用いられてきた暗号技術が注目されている。
【０００３】
暗号とは、情報の意味が当事者以外には理解できないように情報を交換することである。暗号において、誰でも理解できる元の文（平文）を第三者には意味がわからない文（暗号文）に変換することが暗号化であり、また、暗号文を平文に戻すことが復号であり、この暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗号化の過程及び復号の過程には、それぞれ暗号化鍵及び復号鍵と呼ばれる秘密の情報が用いられる。復号時には秘密の復号鍵が必要であるので、この復号鍵を知っている者のみが暗号文を復号でき、暗号化によって情報の秘密性が維持され得る。
【０００４】
暗号化鍵と復号鍵とは、等しくても良いし、異なっていても良い。両者の鍵が等しい暗号方式は、共通鍵暗号方式と呼ばれ、米国商務省標準局が採用したＤＥＳ（Data Encryption Standards)はその典型例である。このような共通鍵暗号方式の従来例は、次のような３種の方法に分類できる。
【０００５】
(1)  第１の方法
暗号通信を行う可能性がある相手との共通鍵をすべて秘密保管しておく方法。
(2)  第２の方法
暗号通信の都度、予備通信により鍵を共有し合う方法（Diffie-Hellmanによる鍵共有方式，公開鍵方式による鍵配送方式など）。
(3)  第３の方法
各ユーザ（エンティティ）の氏名，住所などの個人を特定する公開された特定情報（ＩＤ（Identity）情報）を利用して、予備通信を行うことなく、送信側のエンティティ，受信側のエンティティが独立に同一の共通鍵を生成する方法（ＫＰＳ（Key Predistribution System），ＩＤ−ＮＩＫＳ（ID-based Non-Interactive Key Sharing Schemes) など）。
【０００６】
【発明が解決しようとする課題】
このような従来の３種の方法には、以下に述べるような問題がある。第１の方法では、すべての共通鍵を保管しておくようにするので、不特定多数のユーザがエンティティとなって暗号通信を行うネットワーク社会には適さない。また、第２の方法は、鍵共有のための予備通信が必要である点が問題である。
【０００７】
第３の方法は、予備通信が不要であり、公開された相手のＩＤ情報とセンタから予め配布されている固有の秘密パラメータとを用いて、任意の相手との共通鍵を生成できるので、便利な方法である。しかしながら、次のような２つの問題点がある。一つは、センタがBig Brother となる（すべてのエンティティの秘密を握っており、Key Escrow System になってしまう）点である。もう一つは、ある数のエンティティが結託するとセンタの秘密を演算できる可能性がある点である。この結託問題については、これを計算量的に回避するための工夫が多数なされているが、完全な解決は困難である。
【０００８】
この結託問題の難しさは、ＩＤ情報に基づく秘密パラメータがセンタ秘密と個人秘密との二重構造になっていることに起因する。第３の方法では、センタの公開パラメータと個人の公開ＩＤ情報とこの２種類の秘密パラメータとにて暗号系が構成され、しかも各エンティティが各自に配布された個人秘密を見せ合ってもセンタ秘密が露呈されないようにする必要がある。よって、その暗号系の構築の実現には解決すべき課題が多い。
【０００９】
そこで、本発明者等は、特定情報（ＩＤ情報）をいくつかに分割し、複数の各センタからその分割した特定情報に基づくすべての秘密鍵をエンティティに配布することにより、数学的構造を最小限に抑えることができて、結託問題の回避を可能にし、その暗号系の構築が容易であるＩＤ−ＮＩＫＳによる秘密鍵生成方法，暗号化方法及び暗号通信方法を提案している（特願平11−16257 号）。
【００１０】
結託問題を解決することを目的として提案されてきたエンティティの特定情報に基づく種々の暗号系が不成功となった理由は、エンティティの結託情報からセンタ秘密を割り出せないようにするための工夫を数学的構造に求め過ぎていたためである。数学的構造が複雑過ぎると、安全性を証明するための方法も困難となる。そこで、特願平11−16257 号の提案方法では、エンティティの特定情報をいくつかに分割し、分割した各特定情報についてすべての秘密鍵をエンティティに配布することにより、数学的構造を最小限に抑えるようにする。この提案方法では、複数のセンタが設けられ、各センタはあるエンティティの分割した１つの特定情報に対応する秘密鍵を生成する。よって、すべてのエンティティの秘密を１つのセンタが握るようなことはなく、各センタがBig Brother にならない。
【００１１】
そして、本発明者等は、この提案方法の改良を研究してきた。特に、特定のエンティティの攻撃に必要なすべてのエンティティを買収し、買収したエンティティの秘密鍵のすべてを用いることにより、その特定のエンティティを攻撃するという乱数置換攻撃に強い改良方法を研究してきた。
【００１２】
本発明は斯かる事情に鑑みてなされたものであり、上記提案方法を改良してより乱数置換攻撃に強くした秘密鍵生成装置，暗号化装置，暗号通信方法，暗号通信システム，共通鍵生成装置及び記録媒体を提供することを目的とする。
【００１３】
【課題を解決するための手段】
請求項１に係る秘密鍵生成装置は、エンティティの特定情報を複数のブロックに分割した分割特定情報を用いて前記エンティティ固有の秘密鍵を生成する装置において、前記複数のブロックの中の１つのブロックの分割特定情報に対して複数の秘密鍵を生成する第１生成手段と、前記１つのブロック以外の残りのブロックの分割特定情報に対して各１つの秘密鍵を生成する第２生成手段とを備え、前記第１生成手段及び第２生成手段で生成した秘密鍵を前記エンティティ固有の秘密鍵とするようにしており、前記エンティティ固有の秘密鍵を生成する演算式は以下であることを特徴とする。
【００１４】
【数１８】
0003657803.tif 000002
【００１５】
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及 びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【００１６】
【数１９】
0003657803.tif 000003
【００１９】
請求項２に係る暗号化装置は、各エンティティの特定情報を複数のブロックに分割した分割特定情報を用いて生成した各エンティティ固有の秘密鍵を使用して求めた共通鍵を用いて平文を暗号文に暗号化する暗号化装置において、前記複数のブロックの中の１つのブロックの分割特定情報に対して複数の秘密鍵を生成する第１生成手段と、前記１つのブロック以外の残りのブロックの分割特定情報に対して各１つの秘密鍵を生成する第２生成手段と、前記第１生成手段及び第２生成手段で生成した秘密鍵に含まれている、暗号文の送信先である相手のエンティティの分割特定情報に対応する成分を選び出す手段と、選び出した成分を用いて共通鍵を生成する手段と、生成した共通鍵を用いて平文を暗号文に暗号化する手段とを備えており、前記各エンティティ固有の秘密鍵を生成する演算式は以下であることを特徴とする。
【００２０】
【数２０】
0003657803.tif 000004
【００２１】
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【００２２】
【数２１】
0003657803.tif 000005
【００２３】
請求項３に係る暗号化装置は、請求項２において、前記共通鍵を生成する演算式は以下であることを特徴とする。
【００２４】
【数２２】
0003657803.tif 000006
【００２５】
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【００２７】
請求項４に係る暗号通信方法は、センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記センタ装置が複数設けられており、その複数のセンタ装置夫々は、各エンティティの特定情報を複数のブロックに分割した分割特定情報を用いて各エンティティ固有の秘密鍵を生成することとし、前記複数のセンタ装置の中の１つのセンタ装置は、前記複数のブロックの中の１つのブロックの分割特定情報に対して複数の秘密鍵を生成し、前記１つのセンタ装置以外の残りのセンタ装置夫々は、前記１つのブロック以外の残りのブロックの分割特定情報に対して１つの秘密鍵を生成し、各エンティティ装置は、自身固有の秘密鍵に含まれている、相手のエンティティの分割特定情報に対応する成分を用いて前記共通鍵を生成するようにしており、前記センタ装置における秘密鍵を生成する演算式は以下であることを特徴とする。
【００２８】
【数２３】
0003657803.tif 000007
【００２９】
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【００３０】
【数２４】
0003657803.tif 000008
【００３１】
請求項５に係る暗号通信方法は、請求項４において、前記共通鍵を生成する演算式は以下であることを特徴とする。
【００３２】
【数２５】
0003657803.tif 000009
【００３３】
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【００３４】
請求項６に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、各エンティティの特定情報を複数のブロックに分割した分割特定情報を用いて以下の演算式に従い各エンティティ固有の秘密鍵を生成して各エンティティ装置へ送付する複数のセンタ装置と、該センタ装置から送付された自身の秘密鍵に含まれている、通信対象のエンティティ装置の分割特定情報に対応する成分を使用して以下の演算式に従い、前記暗号化処理及び復号処理に用いる共通鍵を生成する複数のエンティティ装置とを有することを特徴とする。
【００３５】
【数２６】
0003657803.tif 000010
【００３６】
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【００３７】
【数２７】
0003657803.tif 000011
【００３８】
【数２８】
0003657803.tif 000012
【００３９】
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【００４０】
請求項７に係る共通鍵生成装置は、暗号通信システムのエンティティ装置に設けられており、平文から暗号文への暗号化処理及び暗号文から平文への復号処理に用いる共通鍵を生成する共通鍵生成装置において、エンティティの特定情報を複数のブロックに分割した分割特定情報毎に以下の演算式に従って作成された前記エンティティ固有の秘密鍵を格納する格納手段と、格納されている秘密鍵の中から、通信相手のエンティティの分割特定情報に対応する成分を選び出す選出手段と、選び出した成分を使用して以下の演算式に従って前記共通鍵を生成する手段とを備えることを特徴とする。
【００４１】
【数２９】
0003657803.tif 000013
【００４２】
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【００４３】
【数３０】
0003657803.tif 000014
【００４４】
【数３１】
0003657803.tif 000015
【００４５】
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【００４６】
請求項８に係る記録媒体は、暗号通信システムにおける平文から暗号文への暗号化処理及び暗号文から平文への復号処理に用いる共通鍵をエンティティ装置で生成するためのコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、前記エンティティの特定情報を複数のブロックに分割した分割特定情報毎に以下の演算式に従って作成された前記エンティティ固有の秘密鍵の中から、通信相手のエンティティの分割特定情報に対応する成分を選び出させる手順と、コンピュータに、選び出した成分を使用して以下の演算式に従って前記共通鍵を生成させる手順とを含むコンピュータプログラムを記録してあることを特徴とする。
【００４７】
【数３２】
0003657803.tif 000016
【００４８】
但し、
ベクトルｓij：エンティティｉのｊ番目の分割特定情報に対応する秘密鍵（ｊ                        ＝１，２，・・・，Ｋ）
［ベクトルＩij］：エンティティｉのｊ番目の分割特定情報
ベクトル１：成分がすべて１であるＫ次元ベクトル
Ｈj ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｋ：エンティティｉの特定情報のブロック分割数
αi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：Ｎ＝ＰＱ（Ｐ，Ｑは素数）
βij：エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
ｇ：Ｎを法とする最大生成元
ベクトルｇit：エンティティｉの特定情報の第１ブロックに関する秘密鍵（ｔ                        ＝０，１，２，・・・，Ｔ）
Ｔ：指数部分の次数
ｃをスカラーとし、（ｉ），（ii）に示すＡ，Ｂを行列した場合、Ｂ＝ｃA 及          びＢ＝〈Ａ〉c は、それぞれ（iii)及び（iv）を表す
【００４９】
【数３３】
0003657803.tif 000017
【００５０】
【数３４】
0003657803.tif 000018
【００５１】
但し、
ｇtim （＝ベクトルｇit［ベクトルＩm1］）
：エンティティｉの特定情報の第１ブロックについて自身のベクトルｇitか              ら選び出した、エンティティｍのベクトルＩm1に対応する成分（ｔ＝０，              １，２，・・・，Ｔ）
ｘ1im ＝ベクトルｓi1［ベクトルＩm1］
ｘjim （＝ベクトルｓij［ベクトルＩmj］）
：エンティティｉの特定情報の第ｊブロックについて自身のベクトルｓijか              ら選び出した、エンティティｍのベクトルＩmjに対応する成分（ｊ＝２，              ３，・・・，Ｋ）
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵          ｙim：（Ｋ−１）個のｘjim の和（ｊ＝２，３，・・・，Ｋ）
即ち、ｙim＝ｘ2im ＋ｘ3im ＋・・・＋ｘKim 
【００５２】
本発明では、全ブロックすべての計算を完了して初めて共通鍵が求められるようにしており、特定のエンティティの特定情報の分割ブロックを独立して攻撃できないようになっていて、乱数置換攻撃を回避できる。
【００５３】
【発明の実施の形態】
以下、本発明の実施の形態について具体的に説明する。
図１は、本発明の暗号通信システムの構成を示す模式図である。情報の隠匿を信頼できる複数（Ｋ個）のセンタ１が設定されており、これらのセンタ１としては、例えば社会の公的機関を該当できる。
【００５４】
これらの各センタ１と、この暗号系システムを利用するユーザとしての複数の各エンティティａ，ｂ，…，ｚとは、秘密通信路２a1，…，２aK、２b1，…，２bK、・・・、２z1，…，２zKにより接続されており、これらの秘密通信路を介して各センタ１から秘密の鍵情報が各エンティティａ，ｂ，…，ｚへ伝送されるようになっている。また、２人のエンティティの間には通信路３ab，３az，３bz，…が設けられており、この通信路３ab，３az，３bz，…を介して通信情報を暗号化した暗号文が互いのエンティティ間で伝送されるようになっている。
【００５５】
（センタ１での準備処理）
センタ１は以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
公開鍵  Ｎ    Ｎ＝ＰＱ
Ｋ    ＩＤベクトルの分割ブロック数
Ｍj   分割したＩＤベクトルのサイズ（ｊ＝１，２，・・・，Ｋ）
Ｌ    ＩＤベクトルのサイズ（Ｌ＝Ｍ1 ＋Ｍ2 ＋・・・＋ＭK ）
Ｔ    指数部分の次数
秘密鍵  Ｐ，Ｑ    大きな素数
ｇ    Ｎを法とする最大生成元
Ｈj   乱数からなる２Mj×２Mjの対称行列
αi   エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
βij  エンティティｉの個人秘密乱数
（但し、βi1＋βi2＋・・・＋βiK＝λ（Ｎ））
【００５６】
各エンティティの氏名，住所などを示す特定情報であるＩＤベクトルをＬ次元２進ベクトルとし、図２に示すようにそのＩＤベクトルをブロックサイズＭ1 ，Ｍ2 ，・・・，ＭK 毎にＫ個のブロックに分割する。例えば、エンティティｉのＩＤベクトル（ベクトルＩi ）を式（１）のように分割する。分割特定情報である各ベクトルＩij（ｊ＝１，２，・・・，Ｋ）をＩＤ分割ベクトルと呼ぶ。
【００５７】
【数３５】
0003657803.tif 000019
【００５８】
（エンティティの登録処理）
エンティティｉに登録を依頼された各センタ１は、準備した鍵とエンティティｉのＫ個のＩＤ分割ベクトルについて、それぞれに対応するＫ個の秘密鍵ベクトルｓij（ｊ＝１，２，・・・，Ｋ）を以下の式（2-1)，（2-2)，・・・，（2-j)，・・・，（2-K)に従って計算する。
【００５９】
【数３６】
0003657803.tif 000020
【００６０】
但し、ベクトル１は、すべての成分が１であるＫ次元のベクトルを表す。また、Ｈj ［ベクトルＩij］は対称行列Ｈj からベクトルＩijに対応した行を１行抜き出したものを表し、［・］の操作を参照と定義する。
【００６１】
次に、第１ブロックに関して、（Ｔ＋１）個の秘密鍵ベクトルｇit（ｔ＝０，１，２，・・・，Ｔ）を以下の式（3-0)，（3-1)，（3-2)，・・・，（3-t)，・・・，（3-T)に従って計算する。
【００６２】
【数３７】
0003657803.tif 000021
【００６３】
但し、ｃをスカラー、（４），（５）に示すＡ，Ｂを行列とした場合、Ｂ＝ｃA 及びＢ＝〈Ａ〉c は、それぞれ（６）及び（７）を表す。
【００６４】
【数３８】
0003657803.tif 000022
【００６５】
そして、１つのセンタ１は、第１ブロックに関する（Ｔ＋１）個の秘密鍵ベクトルｇit（ｔ＝０，１，２，・・・，Ｔ）を秘密裏にエンティティｉへ送り、残りの（Ｋ−１）の各センタ１は、第２ブロック以降に関する（Ｋ−１）個の秘密鍵ベクトルｓij（ｊ＝２，３，・・・，Ｋ）を秘密裏にエンティティｉへ送る。
【００６６】
（エンティティ間の共通鍵の生成処理）
エンティティｉは、第１ブロックに関して、自身の（Ｔ＋１）個の秘密鍵ベクトルｇitの中から、エンティティｍのＩＤ分割ベクトルであるベクトルＩm1に対応する成分のベクトルｇit［ベクトルＩm1］を選び出す。この選び出したものを（8-0)，（8-1)，・・・，（8-t)，・・・，（8-T)に示す。
【００６７】
【数３９】
0003657803.tif 000023
【００６８】
次に、エンティティｉは、ｊ＝２，３，・・・，Ｋの第２，第３，・・・，第Ｋの各ブロックに関して、自身の秘密鍵ベクトルｓijの中から、エンティティｍのＩＤ分割ベクトルであるベクトルＩmjに対応する成分のベクトルｓij［ベクトルＩmj］を各ブロック毎に選び出す。この選び出したものを（9-2)，・・・，（9-j)，・・・，（9-K)に示す。
【００６９】
【数４０】
0003657803.tif 000024
【００７０】
更に、（10）のように整数環上でこれらのすべての和ｙimを求める。
【００７１】
【数４１】
0003657803.tif 000025
【００７２】
そして、Ｎを法として以下の（11）のような計算を行うことにより、共通鍵Ｋimを求める。この（11）の計算において、全ブロックの計算を完了することにより、個人秘密乱数αi はその逆元との乗算にて消去され、Ｋ個の個人秘密乱数βij  はそれらの加算にて消去される。このＫimはエンティティｍ側から求めた共通鍵Ｋmiと一致する。
【００７３】
【数４２】
0003657803.tif 000026
【００７４】
なお、上式においてｘ1im ＝ベクトルｓi1［ベクトルＩm1］と置いたが、これは、エンティティｉ自身にもわからない。また、Ｔは比較的小さな数であるので、指数部分はべき乗を順次繰り返し行うことにより計算することができる。
【００７５】
なお、上記例において、各ブロックのサイズＭj は全ブロックにおいて一定であっても良いし、その一部または全部のブロックで異なっていても良い。しかし、第１ブロックに関して秘密鍵ベクトルｇitを求めるので、全ブロックについてそのサイズを一定にした場合、第１ブロックについての秘密が大きくなってしまう。よって、第１ブロックのサイズを他のブロックのサイズよりも小さくするようにした方が良い。特に、Ｍ1 ＝１とした場合、配布する秘密を最小限にすることができ、最も安全性が高くなる。
【００７６】
ここで、不特定多数のエンティティの結託によって暗号システム全体を攻撃するような結託攻撃に対する本発明の安全性について考察する。エンティティの総数を100 万人とした場合、1000000 ≒２20であるので、Ｍj ＝１，Ｋ＝20となる。ここで、Ｔ＝32とした場合、共有鍵Ｋimの指数部分の項数は、20Ｈ32＝51Ｃ32≒4.85×1013となる。この項数は、全エンティティ間の共有鍵の総数 1000000Ｃ2 ≒5 ×1012を超える。よって、項数＞共有鍵の総数の条件を満たし、結託攻撃に対して安全である。
【００７７】
次に、上述した暗号システムにおけるエンティティ間の情報の通信について説明する。図３は、２人のエンティティａ，ｂ間における情報の通信状態を示す模式図である。図３の例は、エンティティａが平文（メッセージ）Ｍを暗号文Ｃに暗号化してそれをエンティティｂへ伝送し、エンティティｂがその暗号文Ｃを元の平文（メッセージ）Ｍに復号する場合を示している。
【００７８】
１番目のセンタ１には、各エンティティａ，ｂ固有の秘密鍵ベクトルｓa1，ｓb1と（Ｔ＋１）個の秘密鍵ベクトルｇat，ｇbt（ｔ＝０，１，２，・・・，Ｔ）とを、前記式（2-1)と（3-0)，・・・，（3-T)とに従って計算する秘密鍵生成器１ａが備えられている。そして、各エンティティａ，ｂから登録が依頼されると、そのエンティティａ，ｂの秘密鍵ベクトルｇat，ｇbtがエンティティａ，ｂへ送付される。
【００７９】
ｊ（ｊ＝２，３，・・・，Ｋ）番目のセンタ１には、各エンティティａ，ｂ固有の秘密鍵ベクトルｓaj，ｓbjを前記式（2-2)，・・・，（2-K)に従って計算する秘密鍵生成器１ａが備えられている。そして、各エンティティａ，ｂから登録が依頼されると、そのエンティティａ，ｂの秘密鍵ベクトルｓaj，ｓbjがエンティティａ，ｂへ送付される。
【００８０】
エンティティａ側には、各センタ１から送られるこれらの秘密鍵ベクトルｇat（ｔ＝０，１，２，・・・，Ｔ），ｓaj（ｊ＝２，３，・・・，Ｋ）をテーブル形式で格納しているメモリ１０と、これらの秘密鍵ベクトルの中からエンティティｂに対応する成分であるベクトルｇat［ベクトルＩb1］（ｔ＝０，１，２，・・・，Ｔ），ベクトルｓaj［ベクトルＩbj］（ｊ＝２，３，・・・，Ｋ）を選び出す成分選出器１１と、選び出されたこれらの成分を使用してエンティティａが求めるエンティティｂとの共通鍵Ｋabを生成する共通鍵生成器１２と、共通鍵Ｋabを用いて平文（メッセージ）Ｍを暗号文Ｃに暗号化して通信路３０へ出力する暗号化器１３とが備えられている。
【００８１】
また、エンティティｂ側には、各センタ１から送られるこれらの秘密鍵ベクトルｇbt（ｔ＝０，１，２，・・・，Ｔ），ｓbj（ｊ＝２，３，・・・，Ｋ），をテーブル形式で格納しているメモリ２０と、これらの秘密ベクトルの中からエンティティａに対応する成分であるベクトルｇbt［ベクトルＩa1］（ｔ＝０，１，２，・・・，Ｔ），ベクトルｓbj［ベクトルＩaj］（ｊ＝２，３，・・・，Ｋ）を選び出す成分選出器２１と、選び出されたこれらの成分を使用してエンティティｂが求めるエンティティａとの共通鍵Ｋbaを生成する共通鍵生成器２２と、共通鍵Ｋbaを用いて通信路30から入力した暗号文Ｃを平文Ｍに復号して出力する復号器２３とが備えられている。
【００８２】
エンティティａからエンティティｂへ情報を伝送しようとする場合、まず、各センタ１で求められて、予めメモリ１０に格納されている秘密鍵ベクトルｇat（ｔ＝０，１，２，・・・，Ｔ），ｓaj（ｊ＝２，３，・・・，Ｋ）が成分選出器１１へ読み出される。そして、成分選出器11にて、エンティティｂに対応する成分であるベクトルｇat［ベクトルＩb1］（ｔ＝０，１，２，・・・，Ｔ），ベクトルｓaj［ベクトルＩbj］（ｊ＝２，３，・・・，Ｋ）が選び出されて共通鍵生成器１２へ送られる。共通鍵生成器１２にて、これらの成分を使用して（11）に従って共通鍵Ｋabが求められ、暗号化器１３へ送られる。暗号化器１３において、この共通鍵Ｋabを用いて平文Ｍが暗号文Ｃに暗号化され、暗号文Ｃが通信路３０を介して伝送される。
【００８３】
通信路３０を伝送された暗号文Ｃはエンティティｂの復号器２３へ入力される。各センタ１で求められて、予めメモリ２０に格納されている秘密鍵ベクトルｓbj（ｊ＝２，３，・・・，Ｋ），ｇbt（ｔ＝０，１，２，・・・，Ｔ）が成分選出器２１へ読み出される。そして、成分選出器２１にて、エンティティａに対応する成分であるベクトルｇbt［ベクトルＩa1］（ｔ＝０，１，２，・・・，Ｔ），ベクトルｓbj［ベクトルＩaj］（ｊ＝２，３，・・・，Ｋ）が選び出されて共通鍵生成器２２へ送られる。共通鍵生成器２２にて、これらの成分を使用して（11）に従って共通鍵Ｋbaが求められ、復号器２３へ送られる。復号器２３において、この共通鍵Ｋbaを用いて暗号文Ｃが平文Ｍに復号される。
【００８４】
このような例では、複数のセンタが設けられ、各センタはエンティティの分割した１つのＩＤ情報に対応する鍵を生成するようにしたので、すべてのエンティティの秘密を１つのセンタが握るようなことはなく、各センタがBig Brother にならない。また、各エンティティ固有の秘密鍵ベクトルが予めエンティティ側のメモリに格納されているので、共通鍵生成に要する時間が短くて済む。
【００８５】
図４は、本発明の記録媒体の実施の形態の構成を示す図である。ここに例示するプログラムは、各センタからエンティティｉへ送られてくる秘密鍵ベクトルｓij，ｇitの中からエンティティｍに対応する成分を選び出す処理と、これらの選び出した成分を使用して共通鍵Ｋimを求める処理とを含んでおり、以下に説明する記録媒体に記録されている。なお、コンピュータ４０は、各エンティティ側に設けられている。
【００８６】
図４において、コンピュータ４０とオンライン接続する記録媒体４１は、コンピュータ４０の設置場所から隔たって設置される例えばＷＷＷ(World Wide Web)のサーバコンピュータを用いてなり、記録媒体４１には前述の如きプログラム４１ａが記録されている。記録媒体４１から読み出されたプログラム４１ａがコンピュータ４０を制御することにより、各エンティティにおいて通信対象のエンティティに対する共通鍵を演算する。
【００８７】
コンピュータ４０の内部に設けられた記録媒体４２は、内蔵設置される例えばハードディスクドライブまたはＲＯＭなどを用いてなり、記録媒体４２には前述の如きプログラム４２ａが記録されている。記録媒体４２から読み出されたプログラム４２ａがコンピュータ４０を制御することにより、各エンティティにおいて通信対象のエンティティに対する共通鍵を演算する。
【００８８】
コンピュータ４０に設けられたディスクドライブ４０ａに装填して使用される記録媒体４３は、運搬可能な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシブルディスクなどを用いてなり、記録媒体４３には前述の如きプログラム４３ａが記録されている。記録媒体４３から読み出されたプログラム４３ａがコンピュータ４０を制御することにより、各エンティティにおいて通信対象のエンティティに対する共通鍵を演算する。
【００８９】
【発明の効果】
以上詳述したように、本発明では、全ブロックすべての計算を完了して初めて乱数項が消去されるようにしているので、分割ブロックを独立して攻撃できないようになっていて、乱数置換攻撃を回避することが可能である。
【図面の簡単な説明】
【図１】  本発明の暗号通信システムの構成を示す模式図である。
【図２】  エンティティのＩＤベクトルの分割例を示す模式図である。
【図３】  ２人のエンティティ間における情報の通信状態を示す模式図である。
【図４】  記録媒体の実施の形態の構成を示す図である。
【符号の説明】
１  センタ
１ａ  秘密鍵生成器
１０，２０  メモリ
１１，２１  成分選出器
１２，２２  共通鍵生成器
１３  暗号化器
２３  復号器
３０  通信路
４０  コンピュータ
４１，４２，４３  記録媒体
【図１】
0003657803.tif 000044
【図２】
0003657803.tif 000045
【図３】
0003657803.tif 000046
【図４】
0003657803.tif 000047