(57)【特許請求の範囲】
【請求項１】
エンティティの特定情報に基づいて前記エンティティ固有の秘密鍵を生成する装置において、前記エンティティの特定情報を複数のブロックに分割した分割特定情報を取得する手段と、各ブロックに固有の対称行列から前記エンティティの分割特定情報に対応して１行の行ベクトルを抜き出す手段と、抜き出した１行の行ベクトルを用いて前記エンティティ固有の前記秘密鍵を以下の演算式に従って生成する手段とを備えることを特徴とする秘密鍵生成装置。
【数１】
0003546943.tif 000028
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特 定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル 、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報 に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
【請求項２】
前記ＮがＮ＝ＰＱ（Ｐ，Ｑは素数）であるか、または、前記Ｎが素数であり、前記ｇはＮを法とする最大生成元である請求項１記載の秘密鍵生成装置。
【請求項３】
平文を暗号文に暗号化する暗号化装置において、各エンティティの特定情報を複数のブロックに分割した分割特定情報を取得する手段と、各ブロックに固有の対称行列から各エンティティの分割特定情報に対応して１行の行ベクトルを抜き出す手段と、抜き出した１行の行ベクトルを用いて各エンティティ固有の秘密鍵を生成する秘密鍵生成手段と、生成した秘密鍵に含まれている、暗号文の送信先である相手のエンティティの分割特定情報に対応する成分を選び出す手段と、選び出した成分を用いて共通鍵を生成する共通鍵生成手段と、生成した共通鍵を用いて平文を暗号文に暗号化する手段とを備えており、前記秘密鍵生成手段にて各エンティティ固有の秘密鍵を生成する演算式は以下であることを特徴とする暗号化装置。
【数２】
0003546943.tif 000029
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特                  定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル                  、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報                  に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク                    トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
【請求項４】
前記ＮがＮ＝ＰＱ（Ｐ，Ｑは素数）であるか、または、前記Ｎが素数であり、前記ｇはＮを法とする最大生成元である請求項３記載の暗号化装置。
【請求項５】
前記共通鍵生成手段にて前記共通鍵を生成する演算式は以下である請求項３又は４記載の暗号化装置。
【数３】
0003546943.tif 000030
但し、
ＳR,im：エンティティｉの秘密鍵ベクトルｓR,i (j) の中から、エンティティ ｍの分割特定情報に対応する成分ｓR,imj (j) を抜き出し、抜き出し たものの整数環上での総和であり、以下のように表されるもの
ＳL,im：エンティティｉの秘密鍵ベクトルｓL,i (j) の中から、エンティティ ｍの分割特定情報に対応する成分ｓL,imj (j) を抜き出し、抜き出し たものの整数環上での総和であり、以下のように表されるもの
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵【数４】
0003546943.tif 000031
【請求項６】
センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記センタ装置が複数設けられており、その複数のセンタ装置夫々は、各エンティティの特定情報を複数のブロックに分割した分割特定情報を取得し、各ブロックに固有の対称行列から各エンティティの分割特定情報に対応して１行の行ベクトルを抜き出し、抜き出した１行の行ベクトルを用いて各エンティティ固有の秘密鍵を生成し、各エンティティ装置は、自身固有の秘密鍵に含まれている、相手のエンティティの分割特定情報に対応する成分を用いて前記共通鍵を生成するようにしており、前記センタ装置にて秘密鍵を生成する演算式は以下であることを特徴とする暗号通信方法。
【数５】
0003546943.tif 000032
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特 定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル 、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報 に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
【請求項７】
前記ＮがＮ＝ＰＱ（Ｐ，Ｑは素数）であるか、または、前記Ｎが素数であり、前記ｇはＮを法とする最大生成元である請求項６記載の暗号通信方法。
【請求項８】
前記共通鍵を生成する演算式は以下である請求項６または７記載の暗号通信方法。
【数６】
0003546943.tif 000033
但し、
ＳR,im：エンティティｉの秘密鍵ベクトルｓR,i (j) の中から、エンティティ ｍの分割特定情報に対応する成分ｓR,imj (j) を抜き出し、抜き出し たものの整数環上での総和であり、以下のように表されるもの
ＳL,im：エンティティｉの秘密鍵ベクトルｓL,i (j) の中から、エンティティ ｍの分割特定情報に対応する成分ｓL,imj (j) を抜き出し、抜き出し たものの整数環上での総和であり、以下のように表されるもの
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵
【数７】
0003546943.tif 000034
【請求項９】
送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、各エンティティの特定情報を複数のブロックに分割した分割特定情報を取得し、各ブロックに固有の対称行列から各エンティティの分割特定情報に対応して１行の行ベクトルを抜き出し、抜き出した１行の行ベクトルを用いて、以下の演算式に従い、各エンティティ固有の秘密鍵を生成して各エンティティ装置へ送付する複数のセンタ装置と、該センタ装置から送付された自身の秘密鍵に含まれている、通信対象のエンティティの分割特定情報に対応する成分を選び出す成分選出器、及び選び出した成分を用いて、以下の演算式に従い、前記暗号化処理及び復号処理に用いる共通鍵を生成する共通鍵生成器を備える複数のエンティティ装置とを有することを特徴とする暗号通信システム。
【数８】
0003546943.tif 000035
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特 定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル 、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報 に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
【数９】
0003546943.tif 000036
但し、
ＳR,im：エンティティｉの秘密鍵ベクトルｓR,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓR,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
ＳL,im：エンティティｉの秘密鍵ベクトルｓL,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓL,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵【数１０】
0003546943.tif 000037
【請求項１０】
コンピュータに、暗号通信システムにおける平文から暗号文への暗号化処理及び暗号文から平文への復号処理に用いる共通鍵をエンティティ側で生成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、前記エンティティの特定情報を複数のブロックに分割した分割特定情報毎に以下の演算式に従って生成されてメモリに予め格納されている前記エンティティ固有の秘密鍵を前記メモリから読み出させる手順と、コンピュータに、読み出した秘密鍵の中から通信相手のエンティティの分割特定情報に対応する成分を選び出す処理を成分選出器が行うように該成分選出器を制御させる手順と、コンピュータに、選び出した成分を使用して以下の演算式に従って前記共通鍵を生成する処理を演算部を含む共通鍵生成器が行うように該共通鍵生成器を制御させる手順とを含むコンピュータプログラムを記録してあることを特徴とする記録媒体。
【数１１】
0003546943.tif 000038
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特                  定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル                  、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報                  に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク                    トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
【数１２】
0003546943.tif 000039
但し、
ＳR,im：エンティティｉの秘密鍵ベクトルｓR,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓR,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
ＳL,im：エンティティｉの秘密鍵ベクトルｓL,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓL,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵
【数１３】
0003546943.tif 000040
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、エンティティ固有の秘密鍵を生成する秘密鍵生成装置、情報の内容が当事者以外にはわからないように情報を暗号化する暗号化装置、暗号文にて通信を行う暗号通信方法及び暗号通信システム、並びに、共通鍵を生成するためのコンピュータプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
高度情報化社会と呼ばれる現代社会では、コンピュータネットワークを基盤として、ビジネス上の重要な文書・画像情報が電子的な情報という形で伝送通信されて処理される。このような電子情報は、容易に複写が可能である、複写物とオリジナルとの区別が困難であるという性質があり、情報保全の問題が重要視されている。特に、「コンピュータリソースの共有」，「マルチアクセス」，「広域化」の各要素を満たすコンピュータネットワークの実現が高度情報化社会の確立に不可欠であるが、これは当事者間の情報保全の問題とは矛盾する要素を含んでいる。このような矛盾を解消するための有効な手法として、人類の過去の歴史上主として軍事，外交面で用いられてきた暗号技術が注目されている。
【０００３】
暗号とは、情報の意味が当事者以外には理解できないように情報を交換することである。暗号において、誰でも理解できる元の文（平文）を第三者には意味がわからない文（暗号文）に変換することが暗号化であり、また、暗号文を平文に戻すことが復号であり、この暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗号化の過程及び復号の過程には、それぞれ暗号化鍵及び復号鍵と呼ばれる秘密の情報が用いられる。復号時には秘密の復号鍵が必要であるので、この復号鍵を知っている者のみが暗号文を復号でき、暗号化によって情報の秘密性が維持され得る。
【０００４】
暗号化鍵と復号鍵とは、等しくても良いし、異なっていても良い。両者の鍵が等しい暗号方式は、共通鍵暗号方式と呼ばれ、米国商務省標準局が採用したＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄｓ）はその典型例である。このような共通鍵暗号方式の従来例は、次のような３種の方法に分類できる。
【０００５】
▲１▼  第１の方法
暗号通信を行う可能性がある相手との共通鍵をすべて秘密保管しておく方法。
▲２▼  第２の方法
暗号通信の都度、予備通信により鍵を共有し合う方法（Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎによる鍵共有方式，公開鍵方式による鍵配送方式など）。
▲３▼  第３の方法
各ユーザ（エンティティ）の氏名，住所などの個人を特定する公開された特定情報（ＩＤ（Ｉｄｅｎｔｉｔｙ）情報）を利用して、予備通信を行うことなく、送信側のエンティティ，受信側のエンティティが独立に同一の共通鍵を生成する方法（ＫＰＳ（Ｋｅｙ  Ｐｒｅｄｉｓｔｒｉｂｕｔｉｏｎ  Ｓｙｓｔｅｍ），ＩＤ−ＮＩＫＳ（ＩＤ−ｂａｓｅｄ  Ｎｏｎ−Ｉｎｔｅｒａｃｔｉｖｅ  Ｋｅｙ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅｓ）  など）。
【０００６】
このような従来の３種の方法には、以下に述べるような問題がある。第１の方法では、すべての共通鍵を保管しておくようにするので、不特定多数のユーザがエンティティとなって暗号通信を行うネットワーク社会には適さない。また、第２の方法は、鍵共有のための予備通信が必要である点が問題である。
【０００７】
第３の方法は、予備通信が不要であり、公開された相手の特定情報（ＩＤ情報）とセンタから予め配布されている固有の秘密パラメータとを用いて、任意の相手との共通鍵を生成できるので、便利な方法である。しかしながら、次のような２つの問題点がある。一つは、センタがＢｉｇ  Ｂｒｏｔｈｅｒ  となる（すべてのエンティティの秘密を握っており、Ｋｅｙ  Ｅｓｃｒｏｗ  Ｓｙｓｔｅｍ  になってしまう）点である。もう一つは、ある数のエンティティが結託するとセンタの秘密を演算できる可能性がある点である。この結託問題については、これを計算量的に回避するための工夫が多数なされているが、完全な解決は困難である。
【０００８】
この結託問題の難しさは、特定情報（ＩＤ情報）に基づく秘密パラメータがセンタ秘密と個人秘密との二重構造になっていることに起因する。第３の方法では、センタの公開パラメータと個人の公開された特定情報（ＩＤ情報）とこの２種類の秘密パラメータとにて暗号系が構成され、しかも各エンティティが各自に配布された個人秘密を見せ合ってもセンタ秘密が露呈されないようにする必要がある。よって、その暗号系の構築の実現には解決すべき課題が多い。
【０００９】
【発明が解決しようとする課題】
そこで、本発明者等は、特定情報（ＩＤ情報）をいくつかに分割し、複数の各センタからその分割した特定情報（ＩＤ情報）に基づくすべての秘密鍵をエンティティに配布することにより、数学的構造を最小限に抑えることができて、結託問題の回避を可能にし、その暗号系の構築が容易であるＩＤ−ＮＩＫＳによる秘密鍵生成方法，暗号化方法及び暗号通信方法を提案している（特願平１１−１６２５７  号，特願平１１−５９０４９  号，特願平１１−１３９２８５号、以下、これらを先行例という）。
【００１０】
結託問題を解決することを目的として提案されてきたエンティティの特定情報（ＩＤ情報）に基づく種々の暗号系が不成功となった理由は、エンティティの結託情報からセンタ秘密を割り出せないようにするための工夫を数学的構造に求め過ぎていたためである。数学的構造が複雑過ぎると、安全性を証明するための方法も困難となる。そこで、先行例の提案方法では、エンティティの特定情報（ＩＤ情報）をいくつかに分割し、分割した各特定情報（ＩＤ情報）についてすべての秘密鍵をエンティティに配布することにより、数学的構造を最小限に抑えるようにする。
【００１１】
これらの先行例では、信頼される複数のセンタが設けられ、各センタは各エンティティの分割した各特定情報（ＩＤ情報）に対応する数学的構造を持たない秘密鍵を夫々生成して、各エンティティへ送付する。各エンティティは、各センタから送られてきたこれらの秘密鍵と通信相手の公開されている特定情報（ＩＤ情報）とから共通鍵を、予備通信を行わずに生成する。よって、すべてのエンティティの秘密を１つのセンタが握るようなことはなく、各センタがＢｉｇ  Ｂｒｏｔｈｅｒ  にならない。
【００１２】
そして、本発明者等は、エンティティの特定情報（ＩＤ情報）の分割を利用したこの先行例の改良を研究し続けており、特に、特定のエンティティの攻撃に必要なすべてのエンティティを買収し、買収したエンティティの秘密鍵のすべてを用いることにより、その特定のエンティティを攻撃するという乱数置換攻撃に強い改良方法を研究している。
【００１３】
本発明は斯かる事情に鑑みてなされたものであり、上記先行例を改良してより乱数置換攻撃に強くした秘密鍵生成装置、暗号化装置、暗号通信方法、暗号通信システム及び記録媒体を提供することを目的とする。
【００１４】
【課題を解決するための手段】
請求項１に係る秘密鍵生成装置は、エンティティの特定情報に基づいて前記エンティティ固有の秘密鍵を生成する装置において、前記エンティティの特定情報を複数のブロックに分割した分割特定情報を取得する手段と、各ブロックに固有の対称行列から前記エンティティの分割特定情報に対応して１行の行ベクトルを抜き出す手段と、抜き出した１行の行ベクトルを用いて前記エンティティ固有の前記秘密鍵を以下の演算式に従って生成する手段とを備えることを特徴とする。
【数１４】
0003546943.tif 000002
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特                  定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル                  、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報                  に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク                    トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
請求項２に係る秘密鍵生成装置は、請求項１において、前記ＮがＮ＝ＰＱ（Ｐ，Ｑは素数）であるか、または、前記Ｎが素数であり、前記ｇはＮを法とする最大生成元であることを特徴とする。
【００１５】
請求項３に係る暗号化装置は、平文を暗号文に暗号化する暗号化装置において、各エンティティの特定情報を複数のブロックに分割した分割特定情報を取得する手段と、各ブロックに固有の対称行列から各エンティティの分割特定情報に対応して１行の行ベクトルを抜き出す手段と、抜き出した１行の行ベクトルを用いて各エンティティ固有の秘密鍵を生成する秘密鍵生成手段と、生成した秘密鍵に含まれている、暗号文の送信先である相手のエンティティの分割特定情報に対応する成分を選び出す手段と、選び出した成分を用いて共通鍵を生成する共通鍵生成手段と、生成した共通鍵を用いて平文を暗号文に暗号化する手段とを備えており、前記秘密鍵生成手段にて各エンティティ固有の秘密鍵を生成する演算式は以下であることを特徴とする。
【数１５】
0003546943.tif 000003
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特                  定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル                  、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報                  に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク                    トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
請求項４に係る暗号化装置は、請求項３において、前記ＮがＮ＝ＰＱ（Ｐ，Ｑは素数）であるか、または、前記Ｎが素数であり、前記ｇはＮを法とする最大生成元であることを特徴とする。
請求項５に係る暗号化装置は、請求項３又は４において、前記共通鍵生成手段にて前記共通鍵を生成する演算式は以下であることを特徴とする。
【数１６】
0003546943.tif 000004
但し、
ＳR,im：エンティティｉの秘密鍵ベクトルｓR,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓR,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
ＳL,im：エンティティｉの秘密鍵ベクトルｓL,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓL,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵
【数１７】
0003546943.tif 000005
【００１６】
請求項６に係る暗号通信方法は、センタ装置から複数のエンティティ装置夫々へ各エンティティ固有の秘密鍵を送付し、一方のエンティティ装置が前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた共通鍵を用いて平文を暗号文に暗号化して他方のエンティティ装置へ伝送し、該他方のエンティティ装置が伝送された暗号文を、前記センタ装置から送付された該エンティティ固有の秘密鍵から求めた、前記共通鍵と同一の共通鍵を用いて元の平文に復号することにより、エンティティ装置間で情報の通信を行う暗号通信方法において、前記センタ装置が複数設けられており、その複数のセンタ装置夫々は、各エンティティの特定情報を複数のブロックに分割した分割特定情報を取得し、各ブロックに固有の対称行列から各エンティティの分割特定情報に対応して１行の行ベクトルを抜き出し、抜き出した１行の行ベクトルを用いて各エンティティ固有の秘密鍵を生成し、各エンティティ装置は、自身固有の秘密鍵に含まれている、相手のエンティティの分割特定情報に対応する成分を用いて前記共通鍵を生成するようにしており、前記センタ装置にて秘密鍵を生成する演算式は以下であることを特徴とする。
【数１８】
0003546943.tif 000006
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特                  定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル                  、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報                  に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク                    トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
請求項７に係る暗号通信方法は、請求項６において、前記ＮがＮ＝ＰＱ（Ｐ，Ｑは素数）であるか、または、前記Ｎが素数であり、前記ｇはＮを法とする最大生成元であることを特徴とする。
請求項８に係る暗号通信方法は、請求項６又は７において、前記共通鍵を生成する演算式は以下であることを特徴とする。
【数１９】
0003546943.tif 000007
但し、
ＳR,im：エンティティｉの秘密鍵ベクトルｓR,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓR,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
ＳL,im：エンティティｉの秘密鍵ベクトルｓL,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓL,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵
【数２０】
0003546943.tif 000008
請求項９に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を元の平文に復号する復号処理を、複数のエンティティ装置間で相互に行う暗号通信システムにおいて、各エンティティの特定情報を複数のブロックに分割した分割特定情報を取得し、各ブロックに固有の対称行列から各エンティティの分割特定情報に対応して１行の行ベクトルを抜き出し、抜き出した１行の行ベクトルを用いて、以下の演算式に従い、各エンティティ固有の秘密鍵を生成して各エンティティ装置へ送付する複数のセンタ装置と、該センタ装置から送付された自身の秘密鍵に含まれている、通信対象のエンティティの分割特定情報に対応する成分を選び出す成分選出器、及び選び出した成分を用いて、以下の演算式に従い、前記暗号化処理及び復号処理に用いる共通鍵を生成する共通鍵生成器を備える複数のエンティティ装置とを有することを特徴とする。
【数２１】
0003546943.tif 000009
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特                  定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル                  、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報                  に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク                    トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
【数２２】
0003546943.tif 000010
但し、
ＳR,im：エンティティｉの秘密鍵ベクトルｓR,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓR,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
ＳL,im：エンティティｉの秘密鍵ベクトルｓL,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓL,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵
【数２３】
0003546943.tif 000011
請求項１０に係る記録媒体は、コンピュータに、暗号通信システムにおける平文から暗号文への暗号化処理及び暗号文から平文への復号処理に用いる共通鍵をエンティティ側で生成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、前記エンティティの特定情報を複数のブロックに分割した分割特定情報毎に以下の演算式に従って生成されてメモリに予め格納されている前記エンティティ固有の秘密鍵を前記メモリから読み出させる手順と、コンピュータに、読み出した秘密鍵の中から通信相手のエンティティの分割特定情報に対応する成分を選び出す処理を成分選出器が行うように該成分選出器を制御させる手順と、コンピュータに、選び出した成分を使用して以下の演算式に従って前記共通鍵を生成する処理を演算部を含む共通鍵生成器が行うように該共通鍵生成器を制御させる手順とを含むコンピュータプログラムを記録してあることを特徴とする。
【数２４】
0003546943.tif 000012
但し、
ベクトルｓR,i (j) ，ベクトルｓL,i (j) ：エンティティｉのｊ番目の分割特                  定情報に対応する２種類の秘密鍵（ｊ＝１，２，・・・，Ｊ）
ベクトルｈR,i (j) ，ベクトルｈL,i (j) ：エンティティｉの鍵分割ベクトル                  、ベクトルｈR,i (j) ＋ベクトルｈL,i (j) ＝ベクトルｈi (j) 
ベクトルｈi (j) ：行列Ｈ(j) より、エンティティｉのｊ番目の分割特定情報                  に対応した行を１行抜き出したベクトル
Ｈ(j) ：乱数からなる２Mj×２Mjの対称行列
Ｍj ：エンティティｉのｊ番目の分割特定情報のサイズ
Ｊ：エンティティｉの特定情報のブロック分割数
αi ，βi ：エンティティｉの個人秘密乱数
（但し、ｇｃｄ（αi ，λ（Ｎ））＝１，
ｇｃｄ（βi ，λ（Ｎ））＝１，
λ（・）はカーマイケル関数）
Ｎ：整数
γi (j) ，ｃi ：エンティティｉの個人秘密乱数
（但し、γi (1) ＋γi (2) ＋・・・＋γi (J) ＋ｃi ＝λ（Ｎ））
ベクトルγR,i (j) ，ベクトルγL,i (j) ：エンティティｉの乱数分割ベク                    トル，エンティティｍに対してベクトルγR,im(j) ＋ベクトルγL, im(j) ＝γi (j) ベクトル１
（但し、ベクトル１＝（１，１，・・・，１））
ｇ：Ｎと互いに素な整数
Ｔ：指数部分の次数
【数２５】
0003546943.tif 000013
但し、
ＳR,im：エンティティｉの秘密鍵ベクトルｓR,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓR,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
ＳL,im：エンティティｉの秘密鍵ベクトルｓL,i (j) の中から、エンティティ                  ｍの分割特定情報に対応する成分ｓL,imj (j) を抜き出し、抜き出し                  たものの整数環上での総和であり、以下のように表されるもの
Ｋim：一方のエンティティｉが他方のエンティティｍに対して生成する共通鍵
【数２６】
0003546943.tif 000014
【００１７】
先行例では、分割した特定情報の各ブロックについて、１つずつの秘密鍵を生成しており、十分多くの結託者が結託した乱数置換攻撃に対する安全性に少し問題がある。そこで、本発明では、分割した特定情報の各ブロックにおける秘密鍵（各ブロックに固有の対称行列からエンティティの分割特定情報に対応して抜き出した１行の行ベクトル）を複数の部分和に分割し、各要素に相異なるエンティティ固有の乱数を付加して、各エンティティ固有の秘密鍵を生成する。よって、分割した特定情報を利用した暗号化方式において、先行例では、分割特定情報が同じである場合に、複数のエンティティで同じ鍵を使用することになることもあるが、本発明では、そのようなことがなく、乱数置換攻撃に対する安全性を高めることができる。
【００１８】
【発明の実施の形態】
以下、本発明の実施の形態について具体的に説明する。
図１は、本発明の暗号通信システムの構成を示す模式図である。情報の隠匿を信頼できる複数（Ｊ個）のセンタ１が設定されており、これらのセンタ１としては、例えば社会の公的機関を該当できる。
【００１９】
これらの各センタ１と、この暗号系システムを利用するユーザとしての複数の各エンティティａ，ｂ，…，ｚとは、秘密通信路２ａ１，…，２ａＪ、２ｂ１，…，２ｂＪ、・・・、２ｚ１，…，２ｚＪにより接続されており、これらの秘密通信路を介して各センタ１から秘密の鍵情報が各エンティティａ，ｂ，…，ｚへ伝送されるようになっている。また、２人のエンティティの間には通信路３ａｂ，３ａｚ，３ｂｚ，…が設けられており、この通信路３ａｂ，３ａｚ，３ｂｚ，…を介して通信情報を暗号化した暗号文が互いのエンティティ間で伝送されるようになっている。
【００２０】
各エンティティの氏名，住所などを示す特定情報であるＩＤベクトルをＬ次元２進ベクトルとし、図２に示すようにそのＩＤベクトルをブロックサイズＭ１  ，Ｍ２  ，・・・，ＭＪ  毎にＪ個のブロックに分割する。例えば、エンティティｉのＩＤベクトル（ベクトルＩｉ  ）を下記（１）のように分割する。分割特定情報である各ベクトルＩｉ  （ｊ）  （ｊ＝１，２，・・・，Ｊ）をＩＤ分割ベクトルと呼ぶ。ここで、Ｍｊ  ＝Ｍとすると、全てのＩＤ分割ベクトルのサイズが等しくなる。また、Ｍｊ  ＝１と設定することも可能である。
【００２１】
【数２７】
0003546943.tif 000015
【００２２】
（センタ１での準備処理）
センタ１は以下の公開鍵及び秘密鍵を準備し、公開鍵を公開する。
0003546943.tif 000016
【００２３】
（エンティティの登録処理）
エンティティｉに登録を依頼されたセンタ１は、準備した鍵とエンティティｉのＪ個のＩＤ分割ベクトルについて、それぞれに対応する２種類のＪ個のベクトルｓＲ，ｉ  （ｊ）  ，ベクトルｓＬ，ｉ  （ｊ）  を下記（２），（３）に従って計算し、計算したこれらの秘密鍵を秘密裏にエンティティｉへ配布する。
【００２４】
【数２８】
0003546943.tif 000017
【００２５】
更に、センタ１は、｛（Ｔ＋１）（Ｔ＋２）／２｝個（ｐ＋ｑ＋ｒ＝Ｔ）の下記（４）に示す秘密鍵を計算して、それらの秘密鍵を秘密裏にエンティティｉへ配布する。
【００２６】
【数２９】
0003546943.tif 000018
【００２７】
但し、ａｉ  ，ｂｉ  ，ｃｉ  は、それぞれ下記（５）〜（７）の条件を満たす。
【００２８】
【数３０】
0003546943.tif 000019
【００２９】
（エンティティ間の共通鍵の生成処理）
エンティティｉは、ｊ＝１，２，・・・，Ｊの第１，第２，・・・，第Ｊの各ブロックに関して、自身の秘密鍵ベクトルｓＲ，ｉ  （ｊ）  の中から、エンティティｍのＩＤ分割ベクトルＩｍ  （ｊ）  に対応する成分ｓＲ，ｉｍｊ  （ｊ）  （簡単のため第ｍｊ  成分とした）を抜き出し、抜き出したものの整数環上での総和ＳＲ，ｉｍを求める。同様に、自身の秘密鍵ベクトルｓＬ，ｉ  （ｊ）  の中から、エンティティｍのＩＤ分割ベクトルＩｍ  （ｊ）  に対応する成分ｓＬ，ｉｍｊ  （ｊ）  を抜き出し、抜き出したものの整数環上での総和ＳＬ，ｉｍを求める。これらの総和ＳＲ，ｉｍ，ＳＬ，ｉｍは、それぞれ下記（８），（９）で示される。但し、簡単のため、下記（１０），（１１）のように設定した。
【００３０】
【数３１】
0003546943.tif 000020
【００３１】
そして、Ｎを法として下記（１２）のような計算を行うことにより、共通鍵Ｋｉｍを求める。下記（１２）において、Ｔは比較的小さな数であるので、指数部分はべき乗を順次繰り返して行うことにより計算することができる。この共通鍵Ｋｉｍはエンティティｍ側から求めた共通鍵Ｋｍｉと一致する。
【００３２】
【数３２】
0003546943.tif 000021
【００３３】
この方式では、例えばＪ＝２０，Ｔ＝８と比較的小さな値であっても、ｇの指数部の項数は  ２５６×１０８  と爆発的に増加する。しかしながら、このことを実現するために配布している上記（４）の秘密鍵の個数は４５個で良い。
【００３４】
なお、上述した実施の形態では、ＲＳＡ暗号に基づく安全性を有するようにＮ＝ＰＱ（Ｐ，Ｑは大きな素数）としたが、このＮは整数であれば良い。また、離散対数問題に基づく安全性を有するようにＮ＝Ｐ（Ｐは大きな素数）と設定しても良い。また、多くのべき乗を生成して安全性を高めるように、ｇを法Ｎによる最大生成元としたが、ｇはＮと互いに素な整数であれば任意の数であって良い。
【００３５】
また、上述した実施の形態では、エンティティへの秘密鍵を２分割し、指数部でＴ次多項式を実現するために３項定理を利用しているが、エンティティに配布する秘密鍵の分割数は任意であって良く、その分割数をｋとした場合には、（ｋ＋１）項定理を利用すれば良い。
【００３６】
次に、このような方式の安全性について考察する。
（分離攻撃に対する安全性）
安全なＩＤ−ＮＩＫＳの必要条件として、秘密鍵生成関数及び鍵共有関数が多項式時間で分離できてはならないことが知られている。本方式は、明らかにこの安全性の必要条件を満たしている。
【００３７】
（離散対数問題による安全性）
たとえｇが露呈した場合でも、離散対数問題の困難さにより、個人秘密鍵ａｉ  ，ｂｉ  ，ｃｉ  を上記（４）の秘密鍵から求めることは困難である。より厳密には、下記（１３）とする。但し、Δｐ＝ｐ−ｐ′，Δｑ＝ｑ−ｑ′，Δｒ＝ｒ−ｒ′と置いている。
【００３８】
【数３３】
0003546943.tif 000022
【００３９】
ｐ＋ｑ＋ｒ＝ｐ′＋ｑ′＋ｒ′＝Ｔであるので、Δｐ＋Δｑ＋Δｒ＝０となるような下記（１４）が離散対数問題により守られていることが分かる。
【００４０】
【数３４】
0003546943.tif 000023
【００４１】
（ＲＳＡ暗号による安全性）
たとえａｉ  ，ｂｉ  が露呈した場合でも、ＲＳＡ暗号の安全性により、個人秘密乱数αｉ  ，βｉ  を求めることは困難である。
【００４２】
（乱数置換攻撃に対する安全性）
エンティティの分割した特定情報を利用する鍵共有方式では、ＩＤ分割ベクトルの一部が全く同じであった場合には、それらのエンティティが部分的に同じ鍵を使用していることになる。この点に着目した有力な攻撃法として乱数置換攻撃が考えられる。この攻撃に対して先行例は弱い。これに対して、本発明の方式では、各エンティティ毎に異なる個人秘密乱数γｉ  （ｊ）  を使用し、更にこれを２つのベクトルγＲ，ｉ  （ｊ）  ，γＬ，ｉ  （ｊ）  に分割した上、それぞれに異なる個人秘密乱数αｉ  ，βｉ  を乗じて、秘密鍵を生成しているので、単独では消去することができない。従って、先行例に対しては成立している乱数置換攻撃が、本発明の方式では成立しない。
【００４３】
（カーマイケル関数の安全性）
結託したエンティティにより、相異なる２式が、カーマイケル関数λ（Ｎ）を法として、同じ値を表す場合に、λ（Ｎ）は露呈する。このような攻撃の代表的なものとしてループ攻撃がある。本発明の方式では、秘密鍵も複数の部分（２つの部分）に分割して各エンティティへ配布しているので、上記（１２）に示すようにすべての計算を完了して初めて共通鍵が生成され、鍵共有手続きの途中の段階では、同じ値を相異なる２式を用いて表現することは不可能である。従って、カーマイケル関数λ（Ｎ）は露呈しない。
【００４４】
（未知変数と方程式との数）
センタ１より配布されている方程式の数と未知変数の数との関係について考える。分割ＩＤ情報の各ブロックは同じ構造を有するので、１つのブロックにて考えれば十分である。Ｍｊ  ＝１の場合について考えると、４個の方程式が与えられるが、乱数項γｉｍが４個与えられる。また、｛ｈｉｍ｝が同様に４個与えられる。これらには３つの拘束条件が与えられるので、５つの変数が与えられることになる。Ｍｊ  ≧２の場合についても、常に未知変数の数が方程式の数より多くなることは、容易に確かめられる。従って、攻撃者が未知変数の全てを確定することは不可能である。
【００４５】
次に、上述した暗号システムにおけるエンティティ間の情報の通信について説明する。図３は、２人のエンティティａ，ｂ間における情報の通信状態を示す模式図である。図３の例は、エンティティａが平文（メッセージ）Ｍを暗号文Ｃに暗号化してそれをエンティティｂへ伝送し、エンティティｂがその暗号文Ｃを元の平文（メッセージ）Ｍに復号する場合を示している。
【００４６】
ｊ（ｊ＝１，２，・・・，Ｊ）番目のセンタ１には、各エンティティａ、ｂ固有の秘密鍵ベクトルｓＲ，ａ  （ｊ）  ，ｓＬ，ａ  （ｊ）  、秘密鍵ベクトルｓＲ，ｂ  （ｊ）  ，ｓＬ，ｂ  （ｊ）  を上記（２），（３）に従って計算する秘密鍵生成器１ａが備えられている。また、何れかのセンタ１の秘密鍵生成器１ａは、上記（４）に示す各エンティティａ，ｂ固有の秘密鍵を計算する。そして、各エンティティａ，ｂから登録が依頼されると、これらの秘密鍵がエンティティａ，ｂへ送付される。
【００４７】
エンティティａ側には、センタ１から送られるこれらの秘密鍵をテーブル形式で格納しているメモリ１０と、これらの秘密鍵の中からエンティティｂに対応する成分を選び出す成分選出器１１と、選び出されたこれらの成分及び上記（４）に示す秘密鍵を使用してエンティティａが求めるエンティティｂとの共通鍵Ｋａｂを生成する共通鍵生成器１２と、共通鍵Ｋａｂを用いて平文（メッセージ）Ｍを暗号文Ｃに暗号化して通信路３０へ出力する暗号化器１３とが備えられている。
【００４８】
また、エンティティｂ側には、センタ１から送られるこれらの秘密鍵をテーブル形式で格納しているメモリ２０と、これらの秘密鍵の中からエンティティａに対応する成分を選び出す成分選出器２１と、選び出されたこれらの成分及び上記（４）に示す秘密鍵を使用してエンティティｂが求めるエンティティａとの共通鍵Ｋｂａを生成する共通鍵生成器２２と、共通鍵Ｋｂａを用いて通信路３０から入力した暗号文Ｃを平文Ｍに復号して出力する復号器２３とが備えられている。
【００４９】
エンティティａからエンティティｂへ情報を伝送しようとする場合、まず、センタ１で求められて、予めメモリ１０に格納されている上記（２），（３）に示す秘密鍵が成分選出器１１へ読み出される。そして、成分選出器１１にて、エンティティｂに対応する成分が選び出されて共通鍵生成器１２へ送られる。共通鍵生成器１２にて、これらの成分及び上記（４）に示す秘密鍵を使用して、上記（８），（９），（１２）に従って共通鍵Ｋａｂが求められ、暗号化器１３へ送られる。暗号化器１３において、この共通鍵Ｋａｂを用いて平文Ｍが暗号文Ｃに暗号化され、暗号文Ｃが通信路３０を介して伝送される。
【００５０】
通信路３０を伝送された暗号文Ｃはエンティティｂの復号器２３へ入力される。センタ１で求められて、予めメモリ２０に格納されている上記（２），（３）に示す秘密鍵が成分選出器２１へ読み出される。そして、成分選出器２１にて、エンティティａに対応する成分が選び出されて共通鍵生成器２２へ送られる。共通鍵生成器２２にて、これらの成分及び上記（４）に示す秘密鍵を使用して、上記（８），（９），（１２）に従って共通鍵Ｋｂａが求められ、復号器２３へ送られる。復号器２３において、この共通鍵Ｋｂａを用いて暗号文Ｃが平文Ｍに復号される。
【００５１】
このような例では、複数のセンタが設けられ、各センタはエンティティの分割した１つのＩＤ情報に対応する秘密鍵を生成するようにしたので、すべてのエンティティの秘密を１つのセンタが握るようなことはなく、各センタがＢｉｇ  Ｂｒｏｔｈｅｒ  にならない。また、各エンティティ固有の秘密鍵ベクトルが予めエンティティ側のメモリに格納されているので、共通鍵生成に要する時間が短くて済む。
【００５２】
上述した方式（以下、基本方式という）では、指数部でｃｉ  と結合して初めて乱数部分が消去されるようになっているので、極めて強固な安全性を実現できている。これに対して、このｃｉ  をなくすことにより、基本方式と比べて安全性は多少犠牲にすることになるが、エンティティへ配布する秘密の数を大幅に減らすことができるという実用面に重点を置いた、簡易的な本発明の他の方式について、以下に説明する。
【００５３】
（センタ１での準備処理）
センタ１は、基本方式と同様の公開鍵及び秘密鍵を準備し、公開鍵を公開する。但し、個人秘密乱数ｃｉ  を使用しないので、γｉ  （ｊ）  は、下記（１５）を満たす。即ち、この簡易化方式では、基本方式においてｃｉ  ＝０と設定した場合に相当する。
γｉ  （１）  ＋γｉ  （２）  ＋・・・＋γｉ  （Ｊ）  ＝λ（Ｎ）    …（１５）
【００５４】
（エンティティの登録処理）
エンティティｉに登録を依頼されたセンタ１は、準備した鍵とエンティティｉのＪ個のＩＤ分割ベクトルについて、それぞれに対応する２種類のＪ個のベクトルｓＲ，ｉ  （ｊ）  ，ベクトルｓＬ，ｉ  （ｊ）  を下記（１６），（１７）に従って計算し、計算したこれらの秘密鍵を秘密裏にエンティティｉへ配布する。
【００５５】
【数３５】
0003546943.tif 000024
【００５６】
更に、センタ１は、（Ｔ＋１）個（ｐ＋ｑ＝Ｔ）の下記（１８）に示す秘密鍵を計算して、それらの秘密鍵を秘密裏にエンティティｉへ配布する。
【００５７】
【数３６】
0003546943.tif 000025
【００５８】
但し、ａｉ  ，ｂｉ  は、それぞれ下記（１９），（２０）の条件を満たす。
【００５９】
【数３７】
0003546943.tif 000026
【００６０】
（エンティティ間の共通鍵の生成処理）
エンティティｉは、基本方式と同様に、ｊ＝１，２，・・・，Ｊの第１，第２，・・・，第Ｊの各ブロックに関して、整数環上での総和ＳＲ，ｉｍ，ＳＬ，ｉｍを求める。そして、Ｎを法として下記（２１）のような計算を行うことにより、共通鍵Ｋｉｍを求める。下記（２１）において、Ｔは比較的小さな数であるので、指数部分はべき乗を順次繰り返して行うことにより計算することができる。この共通鍵Ｋｉｍはエンティティｍ側から求めた共通鍵Ｋｍｉと一致する。
【００６１】
【数３８】
0003546943.tif 000027
【００６２】
この簡易化方式は、基本方式においてｃｉ  ＝０と設定した場合に相当するので、指数部でＴ次多項式を実現するために二項定理を利用するだけで良く、エンティティへ配布する秘密鍵を｛（Ｔ＋１）（Ｔ＋２）／２｝個から（Ｔ＋１）個に削減することができる。指数部で初めてｃｉ  が消去されるという安全性はないが、その他の安全性に関しては、すべて基本方式に準じる。
【００６３】
図４は、本発明の記録媒体の実施の形態の構成を示す図である。ここに例示するプログラムは、センタからエンティティｉへ送られてくる上記（２），（３）または（１６），（１７）に示す秘密鍵の中からエンティティｍに対応する成分を選び出す処理と、これらの選び出した成分及び上記（４）または（１８）に示す秘密鍵を使用して共通鍵Ｋｉｍを求める処理とを含んでおり、以下に説明する記録媒体に記録されている。なお、コンピュータ４０は、各エンティティ側に設けられている。
【００６４】
図４において、コンピュータ４０とオンライン接続する記録媒体４１は、コンピュータ４０の設置場所から隔たって設置される例えばＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）のサーバコンピュータを用いてなり、記録媒体４１には前述の如きプログラム４１ａが記録されている。記録媒体４１から読み出されたプログラム４１ａがコンピュータ４０を制御することにより、各エンティティにおいて通信対象のエンティティに対する共通鍵を演算する。
【００６５】
コンピュータ４０の内部に設けられた記録媒体４２は、内蔵設置される例えばハードディスクドライブまたはＲＯＭなどを用いてなり、記録媒体４２には前述の如きプログラム４２ａが記録されている。記録媒体４２から読み出されたプログラム４２ａがコンピュータ４０を制御することにより、各エンティティにおいて通信対象のエンティティに対する共通鍵を演算する。
【００６６】
コンピュータ４０に設けられたディスクドライブ４０ａに装填して使用される記録媒体４３は、運搬可能な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシブルディスクなどを用いてなり、記録媒体４３には前述の如きプログラム４３ａが記録されている。記録媒体４３から読み出されたプログラム４３ａがコンピュータ４０を制御することにより、各エンティティにおいて通信対象のエンティティに対する共通鍵を演算する。
【００６７】
【発明の効果】
以上詳述したように、本発明では、分割した特定情報の各ブロック（各分割ＩＤベクトル）における秘密鍵を複数の部分和に分割し、各要素に相異なるエンティティ固有の乱数を付加して、各エンティティ固有の秘密鍵を生成するようにしたので、十分な数の結託者による乱数置換攻撃に弱いという先行例の問題点を解消できる、強力なＩＤ−ＮＩＫＳの暗号化方式，暗号通信システムを提供することができる。
【００９４】
【図面の簡単な説明】
【図１】本発明の暗号通信システムの構成を示す模式図である。
【図２】エンティティのＩＤベクトルの分割例を示す模式図である。
【図３】２人のエンティティ間における情報の通信状態を示す模式図である。
【図４】記録媒体の実施の形態の構成を示す図である。
【符号の説明】
１  センタ
１ａ  秘密鍵生成器
１０，２０  メモリ
１１，２１    成分選出器
１２，２２  共通鍵生成器
１３  暗号化器
２３  復号器
３０  通信路
４０  コンピュータ
４１，４２，４３  記録媒体
【図１】
0003546943.tif 000041
【図２】
0003546943.tif 000042
【図３】
0003546943.tif 000043
【図４】
0003546943.tif 000044