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