JP3283202B2 - 暗号通信方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、情報の内容が当事
者以外にはわからないように情報を暗号化して通信する
安全性が高い暗号通信方法に関する。

【０００２】

【従来の技術】高度情報化社会と呼ばれる現代社会で
は、コンピュータネットワークを基盤として、ビジネス
上の重要な文書・画像情報が電子的な情報という形で伝
送通信されて処理される。このような電子情報は、容易
に複写が可能である、複写物とオリジナルとの区別が困
難であるという性質があり、情報保全の問題が重要視さ
れている。特に、「コンピュータリソースの共有」，
「マルチアクセス」，「広域化」の各要素を満たすコン
ピュータネットワークの実現が高度情報化社会の確立に
不可欠であるが、これは当事者間の情報保全の問題とは
矛盾する要素を含んでいる。このような矛盾を解消する
ための有効な手法として、人類の過去の歴史上主として
軍事，外交面で用いられてきた暗号技術が注目されてい
る。

【０００３】暗号とは、情報の意味が当事者以外には理
解できないように情報を交換することである。暗号にお
いて、誰でも理解できる元の文（平文）を第三者には意
味がわからない文（暗号文）に変換することが暗号化で
あり、また、暗号文を平文に戻すことが復号であり、こ
の暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗
号化の過程及び復号の過程には、それぞれ暗号化鍵及び
復号鍵と呼ばれる秘密の情報が用いられる。復号時には
秘密の復号鍵が必要であるので、この復号鍵を知ってい
る者のみが暗号文を復号でき、暗号化によって情報の秘
密性が維持され得る。

【０００４】暗号化鍵と復号鍵とは、等しくても良い
し、異なっていても良い。両者の鍵が等しい暗号系は、
共通鍵暗号系と呼ばれ、米国商務省標準局が採用したＤ
ＥＳ（Data Encryption Standards)はその典型例であ
る。また、両者の鍵が異なる暗号系の一例として、公開
鍵暗号系と呼ばれる暗号系が提案された。この公開鍵暗
号系は、暗号系を利用する各ユーザ（エンティティ）が
暗号化鍵と復号鍵とを一対ずつ作成し、暗号化鍵を公開
鍵リストにて公開し、復号鍵のみを秘密に保持するとい
う暗号系である。公開鍵暗号系では、この一対となる暗
号化鍵と復号鍵とが異なり、一方向性関数を利用するこ
とによって暗号化鍵から復号鍵を割り出せないという特
徴を持たせている。

【０００５】公開鍵暗号系は、暗号化鍵を公開するとい
う画期的な暗号系であって、高度情報化社会の確立に必
要な上述した３つの要素に適合するものであり、情報通
信技術の分野等での利用を図るべく、その研究が活発に
行われ、典型的な公開鍵暗号系としてＲＳＡ暗号系が提
案された。このＲＳＡ暗号系は、一方向性関数として素
因数分解の困難さを利用して実現されている。また、離
散対数問題を解くことの困難さ（離散対数問題）を利用
した公開鍵暗号系も種々の手法が提案されてきた。

【０００６】また、各エンティティの住所，氏名等の個
人を特定するＩＤ（Identity）情報を利用する暗号系が
提案された。この暗号系では、ＩＤ情報に基づいて送受
信者間で共通の暗号化鍵を生成する。また、このＩＤ情
報に基づく暗号技法は、（１）暗号文通信に先立って送
受信者間での予備通信を必要とする方式と、（２）暗号
文通信に先立って送受信者間での予備通信を必要としな
い方式とがある。特に、（２）の手法は予備通信が不要
であるので、エンティティの利便性が高く、将来の暗号
系の中枢をなすものと考えられている。

【０００７】この（２）の手法による暗号系は、ＩＤ−
ＮＩＫＳ（ID-based non-interactive key sharing sch
eme)と呼ばれており、通信相手のＩＤ情報を用いて予備
通信を行うことなく暗号化鍵を共有する方式を採用して
いる。ＩＤ−ＮＩＫＳは、送受信者間で公開鍵，秘密鍵
を交換する必要がなく、また鍵のリスト及び第三者によ
るサービスも必要としない方式であり、任意のエンティ
ティ間で安全に通信を行える。

【０００８】図１２は、このＩＤ−ＮＩＫＳのシステム
の原理を示す図である。信頼できるセンタの存在を仮定
し、このセンタを中心にして共有鍵生成システムを構成
している。図１２において、エンティティＸの名前，住
所，電話番号等のＩＤ情報は、ハッシュ関数ｈ（・）を
用いてｈ（ＩＤ_X ）で表す。センタは任意のエンティテ
ィＸに対して、センタ公開情報｛ＰＣ_i ｝，センタ秘密
情報｛ＳＣ_i ｝及びエンティティＸのＩＤ情報ｈ（ＩＤ
_X ）に基づいて、以下のように秘密情報Ｓ_Xiを計算し、
秘密裏にエンティティＸへ配布する。 Ｓ_Xi＝Ｆ_i （｛ＳＣ_i ｝，｛ＰＣ_i ｝，ｈ（ＩＤ_X ））

【０００９】エンティティＸは他の任意のエンティティ
Ｙとの間で、暗号化，復号のための共有鍵Ｋ_XYを、エン
ティティＸ自身の秘密情報｛Ｓ_Xi｝，センタ公開情報
｛ＰＣ_i ｝及び相手先のエンティティＹのＩＤ情報ｈ
（ＩＤ_Y ）を用いて以下のように生成する。Ｋ _XY ＝ｆ（｛Ｓ _Xi ｝，｛ＰＣ _i ｝，ｈ（ＩＤ _Y ）） また、エンティティＹも同様にエンティティＸへの鍵を
共有鍵Ｋ_YXを生成する。もし常にＫ_XY＝Ｋ_YXの関係が成
立すれば、この鍵Ｋ_XY，Ｋ_YXをエンティティＸ，Ｙ間で
暗号化鍵，復号鍵として使用できる。

【００１０】上述した公開鍵暗号系では、例えばＲＳＡ
暗号系の場合にその公開鍵の長さは現在の電話番号の十
数倍となり、極めて煩雑である。これに対して、ＩＤ−
ＮＩＫＳでは、各ＩＤ情報を名簿という形式で登録して
おけば、この名簿を参照して任意のエンティティとの間
で共有鍵を生成することができる。従って、図１２に示
すようなＩＤ−ＮＩＫＳのシステムが安全に実現されれ
ば、多数のエンティティが加入するコンピュータネット
ワーク上で便利な暗号系を構築できる。このような理由
により、ＩＤ−ＮＩＫＳが将来の暗号系の中心となると
期待されている。

【００１１】対称行列を利用した分離可能な演算を用い
るＩＤ−ＮＩＫＳは、センタの秘密情報とエンティティ
との公開鍵の演算方法、及び乱数の有無に応じて、以下
の４種類に分類される。 （１）積和型ＮＩＫＳ （２）乱数付加積和型ＮＩＫＳ （３）べき積型ＮＩＫＳ （４）乱数付加乱べき積型ＮＩＫＳ

【００１２】これらの各種類のＮＩＫＳについて、以下
に簡単に説明するが、その前に演算の定義及びその定義
に基づく諸定理を示す。

【００１３】Ａ＝（ａ_ij），Ｂ＝（ｂ_ij），Ｃ＝
（ｃ_ij）を適当な大きさの行列とした場合に、以下の演
算（定義１〜３）を定義する。

【００１４】

【数３】

【００１５】また、上記定義に従うと、以下の諸定理
（定理１〜５）が成立する。但し、ｔは転置を意味す
る。

【００１６】

【数４】

【００１７】上記（１）〜（４）の何れの形式において
も、センタは秘密裏に以下に示すような準備，を行
う。 適当なｎ×ｎの対称行列Ｔを生成する。 登録を要求してきたエンティティのＩＤをｎ個の成
分を有する適当なベクトルに変換するための公開ハッシ
ュ関数ｈ（・）を生成する。

【００１８】（１）積和型ＮＩＫＳ エンティティｘに登録を依頼されたセンタは、ハッシュ
関数で示されるエンティティｘの公開情報（公開鍵）ベ
クトルｖ_x （＝ｈ（ＩＤ_x ））と、対称行列Ｔとを用い
て、以下の計算に従って、エンティティｘの秘密情報
（秘密鍵）ベクトルｓ_x を求めて、エンティティｘへ秘
密裏に送る。

【００１９】

【数５】

【００２０】以下の計算に従って、エンティティｉがエ
ンティティｊとの共有鍵Ｋ_ijを求め、エンティティｊが
エンティティｉとの共有鍵Ｋ_jiを求める。明らかにＫ_ij
＝Ｋ _jiとなる。

【００２１】

【数６】

【００２２】（２）乱数付加積和型ＮＩＫＳ エンティティｘに登録を依頼されたセンタは、ベクトル
ｖ_x （＝ｈ（ＩＤ_x ））と対称行列Ｔと乱数ベクトルｒ
_x とを用いて、以下の計算に従って、ベクトルｓ_x を求
めて、エンティティｘへ秘密裏に送る。但し、○は適当
な算法を示す。

【００２３】

【数７】

【００２４】エンティティｉがエンティティｊとの鍵共
有を行うために、以下の計算を行う。ここで、適当な手
法によって乱数項を消去することにより、共有鍵を共有
できる。

【００２５】

【数８】

【００２６】（３）べき積型ＮＩＫＳ エンティティｘに登録を依頼されたセンタは、ベクトル
ｖ_x （＝ｈ（ＩＤ_x ））と対称行列Ｔとを用いて、以下
の計算に従って、ベクトルｓ_x を求めて、エンティティ
ｘへ秘密裏に送る。

【００２７】

【数９】

【００２８】以下の計算に従って、エンティティｉがエ
ンティティｊとの共有鍵Ｋ_ijを求め、エンティティｊが
エンティティｉとの共有鍵Ｋ_jiを求める。上述のべき積
演算の定理１より、Ｋ_ij＝Ｋ_jiとなる。

【００２９】

【数１０】

【００３０】（４）乱数付加乱べき積型ＮＩＫＳ エンティティｘに登録を依頼されたセンタは、ベクトル
ｖ_x （＝ｈ（ＩＤ_x ））と対称行列Ｔと乱数ベクトルｒ
_x とを用いて、以下の計算に従って、ベクトルｓ_x を求
めて、エンティティｘに秘密裏に送る。但し、○は適当
な算法を示す。

【００３１】

【数１１】

【００３２】エンティティｉがエンティティｊとの鍵共
有を行うために、以下の計算に行う。ここで、適当な手
法によって乱数項を消去することにより、共有鍵を共有
できる。

【００３３】

【数１２】

【００３４】

【発明が解決しようとする課題】通信相手のＩＤ情報を
用いて予備通信を行うことなく暗号化鍵及び復号鍵とな
る共有鍵を互いに共有するようなＩＤ−ＮＩＫＳにあっ
ては、複数のエンティティの結託等の攻撃に対して十分
に安全であることが望まれる。しかしながら、以上のよ
うなＩＤ−ＮＩＫＳにおいては、攻撃法が検討されて、
適当な人数のエンティティが結託すればセンタの秘密パ
ラメータが露呈するという問題を含んでいる。暗号学的
に安全なＩＤ−ＮＩＫＳを構築できるか否かは、高度情
報化社会に重要な問題であり、より理想的な暗号方式の
探究が進められている。

【００３５】本発明は斯かる事情に鑑みてなされたもの
であり、エンティティが結託してもセンタの秘密パラメ
ータが露呈することなく暗号文が復号されず、安全性が
極めて高い新規のＩＤ−ＮＩＫＳによる暗号通信方法を
提供することを目的とする。

【００３６】

【課題を解決するための手段】請求項１に係る暗号通信
方法は、センタ装置から複数のエンティティ装置夫々へ
各エンティティ固有の暗号鍵を送付し、一方のエンティ
ティ装置が前記センタ装置から送付された該エンティテ
ィ固有の暗号鍵と公開された他方のエンティティの公開
鍵とを利用して平文を暗号文に暗号化して他方のエンテ
ィティ装置へ伝送し、該他方のエンティティ装置が伝送
された暗号文を前記センタ装置から送付された該エンテ
ィティ固有の暗号鍵と公開された前記一方のエンティテ
ィの公開鍵とを利用して元の平文に復号することによ
り、エンティティ装置間で情報の通信を行う暗号通信方
法において、前記センタ装置にて、公開鍵として公開さ
れた各エンティティ固有の第１の鍵とセンタ装置が管理
する対称行列とから（２）式に基づいて、第１の鍵を変
数とする第１の関数で表される各エンティティ固有の秘
密の第２の鍵を生成し、各エンティティ固有の乱数と第
２の鍵とから（３）式に基づいて第１秘密鍵を生成し、
前記乱数から（４）式に基づいて第２秘密鍵を生成し、
生成した第１秘密鍵及び第２秘密鍵を各エンティティ装
置に送付し、一方のエンティティ装置にて、第１秘密鍵
及び第２秘密鍵と他方のエンティティの第１の鍵とを用
いて、自身の第２の鍵及び相手の第１の鍵を２変数とす
る第２の関数で表され、平文を暗号文に暗号化する際及
び暗号文を平文に復号する際に用いる両エンティティ間
で共有する第３の鍵を（５），（６）式に基づいて生成
し、第１の鍵、第２の鍵及び第３の鍵を使用して、エン
ティティ装置間で暗号化した情報の通信を行うこととす
るが、第２の関数に第１の関数を代入して得られる、自
身及び相手の第１の鍵を変数とする第３の関数を、それ
ぞれの変数について（１）式に定義されるような分離不
可能な関数に設定することを特徴とする。ｆ（ｘ＋ｙ）≠ｆ（ｘ）○ｆ（ｙ） …（１） 但し、 適当な可換な算法を○として、関数ｆ（・）が次
式を満たす場合に、関数ｆ（・）は算法○により分離不
可能であると定義する。

【００３７】

【数１３】

【００３８】

【数１４】

【００３９】

【００４０】

【００４１】

【００４２】

【００４３】

【００４４】

【００４５】

【００４６】

【００４７】

【００４８】

【００４９】

【００５０】

【００５１】以下、本発明の暗号通信方法におけるＩＤ
−ＮＩＫＳの概念について説明する。

【００５２】まず、線形の概念を一般化して、関数にお
ける分離可能を次のように定義する。適当な可換な算法
を○として、関数ｆ（・）が次の関係式を満たす場合
に、その関数ｆ（・）は算法○により分離可能であると
定義する。 ｆ（ｘ＋ｙ）＝ｆ（ｘ）○ｆ（ｙ） 例えば、ｆ（ｘ）＝ａｘ，ｆ（ｘ）＝ａ^x は、以下に示
すように分離可能である。 ｆ（ｘ＋ｙ）＝ａ（ｘ＋ｙ）＝ａｘ＋ａｙ＝ｆ（ｘ）＋
ｆ（ｙ） ｆ（ｘ＋ｙ）＝ａ^x+y ＝ａ^x ・ａ^y ＝ｆ（ｘ）・ｆ
（ｙ）

【００５３】また、行列のべき積演算の定義は、Ａ，
Ｂ，Ｃをそれぞれｍ×ｌ，ｌ×ｎ，ｍ×ｎの行列とする
と、前述したように、以下のようになる。

【００５４】

【数１５】

【００５５】また、２×２行列について、右べき積，左
べき積を具体的に例示すると、以下のようになる。

【００５６】

【数１６】

【００５７】次に、ＮＩＫＳを実現するための条件及び
安全なＮＩＫＳであるための条件について考察する。但
しｉ，ｊ，ｋ，１，ｙ及びｚはエンティティを表し、ｓ
_i はエンティティｉの秘密鍵（特許請求の範囲の第２の
鍵）、ｖ_i は多くの場合にＩＤのハッシュ値であるエン
ティティｉの公開鍵（特許請求の範囲の第１の鍵）、Ｋ
_ijはエンティティｉが求めたエンティティｊとの共有鍵
（特許請求の範囲の第３の鍵）とする。

【００５８】ＮＩＫＳを実現するためには、以下の３つ
の条件が必要である。 〔条件１（秘密鍵生成条件）〕センタはエンティティｉ
の公開鍵ｖ_i から対応する秘密鍵ｓ_i を求めることがで
きる。

【００５９】

【数１７】

【００６０】〔条件２（共有鍵生成条件）〕エンティテ
ィｉの秘密鍵ｓ_i とエンティティｊの公開鍵ｖ_j とから
共有鍵Ｋ_ijを生成できる。

【００６１】〔条件３（鍵共有条件）〕エンティティｉ
がエンティティｊに対して生成する共有鍵Ｋ_ijと、エン
ティティｊがエンティティｉに対して生成する共有鍵Ｋ
_jiとは等しい。Ｋ_ij＝Ｋ_ji

【００６２】また、安全なＮＩＫＳには、以下の５つの
条件が必要である。 〔条件４（秘密鍵の安全性）〕 いかなるエンティティｉも自身の公開鍵ｖ _i から自身の
秘密鍵ｓ_i を求められない。

【００６３】

【数１８】

【００６４】〔条件５（共有鍵の安全性）〕２人のエン
ティティｙ，ｚの公開鍵ｖ_y ，ｖ_z からエンティティ
ｙ，ｚ間の共有鍵Ｋ_yzを求められない。

【００６５】

【数１９】

【００６６】〔条件６（結託に対する秘密鍵の安全
性）〕複数のエンティティｉ，ｊ，…の結託によって、
公開鍵ｖ_i ，ｖ_j ，…と秘密鍵ｓ_i ，ｓ_j ，…とをいく
ら集めても、他のいかなるエンティティｚの秘密鍵ｓ _z
を求められない。

【００６７】

【数２０】

【００６８】〔条件７（結託に対する共有鍵の安全
性）〕複数のエンティティｉ，ｊ，…の結託によって、
公開鍵ｖ_i ，ｖ_j ，…と秘密鍵ｓ_i ，ｓ_j ，…とをいく
ら集めても、他のいかなるエンティティｙ，ｚ間の共有
鍵Ｋ_yzを求められない。なお、複数のエンティティｉ，
ｊ，ｋ，…の結託によって、エンティティｉ，ｊ，ｋ，
…間の共有鍵Ｋ_ij，Ｋ_ik，Ｋ_jk，…をいくら集めても、
他のいかなるエンティティｙ，ｚ間の共有鍵Ｋ_yzを求め
られないという条件も含まれる。

【００６９】

【数２１】

【００７０】〔条件８（センタ秘密の安全性）〕いかな
る攻撃によってもセンタ秘密は求められない。

【００７１】上述した条件１〜５は、それぞれ条件９〜
１３と同値である。 〔条件９〕センタは、秘密鍵を生成するための関数（秘
密鍵生成関数：特許請求の範囲の第１の関数）ｆ（・）
を計算できる。 ｓ_i ＝ｆ（ｖ_i ）

【００７２】〔条件１０〕共有鍵を生成するための関数
（共有鍵生成関数：特許請求の範囲の第２の関数）Ｆ
（・）は２変数関数で表せる。 Ｋ_ij＝Ｆ（ｓ_i ，ｖ_j ） から対応する秘密鍵ｓ_i を求めることができる。

【００７３】〔条件１１〕共有鍵生成関数Ｆ（・）に秘
密鍵生成関数ｆ（・）を代入して得られる、公開鍵を変
数とする関数（共有鍵公開関数：特許請求の範囲の第３
の関数））Ｆ_p （・）は、対称関数である。 Ｆ_p （ｖ_i ，ｖ_j ）＝Ｆ_p （ｖ_j ，ｖ_i ） 但し、 Ｆ_p （ｖ_i ，ｖ_j ）＝Ｆ（ｆ（ｖ_i ），ｖ_j ）＝Ｆ（ｓ
_i ｖ_j ）

【００７４】〔条件１２〕各エンティティは、秘密鍵生
成関数ｆ（・）を計算できない。

【００７５】〔条件１３〕各エンティティは、共有鍵公
開関数Ｆ_p （・）を計算できない。

【００７６】上記条件６，条件７を満たすためには、線
形攻撃が適用できないか、または、それぞれ以下の条件
１４，条件１５を満たせば良い。

【００７７】〔条件１４〕秘密鍵生成関数ｆ（・）は分
離不可能な関数である。 ｆ（ｘ＋ｙ）≠ｆ（ｘ）○ｆ（ｙ） もし分離可能な関数であると、エンティティの結託に伴
う秘密鍵による結託攻撃により破られる。例えば、エン
ティティｉ，ｊが結託して、ｖ_z ＝ｖ_i ＋ｖ_j と表され
る場合には、両エンティティｉ，ｊの秘密鍵ｓ_i ，ｓ_j
を用意すれば、以下のようにして、エンティティｚの秘
密鍵ｓ_z を求めることができる。 ｓ_z ＝ｆ（ｖ_z ） ＝ｆ（ｖ_i ）○ｆ（ｖ_j ） ＝ｓ_i ○ｓ_j

【００７８】〔条件１５〕共有鍵公開関数Ｆ_p （・）は
分離不可能な関数である。 Ｆ_p （ａ，ｘ＋ｙ）≠Ｆ_p （ａ，ｘ）○Ｆ_p （ａ，ｙ） 〔条件１１〕より、Ｆ_p （・）は対称関数であるので、
次式も成立する。 Ｆ_p （ｘ＋ｙ，ａ）≠Ｆ_p （ｘ，ａ）○Ｆ_p （ｙ，ａ） もし分離可能な関数であると、エンティティの結託に伴
う共有鍵による結託攻撃により破られてしまう。エンテ
ィティｉ，ｊが結託して、ｖ_z ＝ｖ_i ＋ｖ_j と表される
場合には、Ｋ_iy（＝Ｆ（ｓ_i ，ｖ_y ）＝Ｆ_p （ｖ_i ，ｖ
_y ））及びＫ_jy＝（Ｆ（ｓ_j ，ｖ_y ）＝Ｆ_p （ｖ_j ，ｖ
_y ））を準備しておけば、以下のようにして、エンティ
ティｙ，ｚ間の共有鍵Ｋ_yzを求めることができる。 Ｋ_yz＝Ｆ_p （ｖ_y ，ｖ_z ） ＝Ｆ_p （ｖ_y ，ｖ_i ＋ｖ_j ） ＝Ｆ_p （ｖ_y ，ｖ_i ）○Ｆ_p （ｖ_y ，ｖ_j ） ＝Ｆ_p （ｖ_i ，ｖ_y ）○Ｆ_p （ｖ_j ，ｖ_y ） ＝Ｋ_iy○Ｋ_jy また、ｖ_y ＝ｖ_i ＋ｖ_j ，ｖ_z ＝ｖ_k ＋ｖ_l と表される
場合には、Ｋ_ik，Ｋ_il，Ｋ_jk及びＫ_jlを準備しておけ
ば、以下のようにして、Ｋ_yzを求めることができる。 Ｋ_yz＝Ｆ_p （ｖ_y ，ｖ_z ） ＝Ｆ_p （ｖ_i ，ｖ_z ）○Ｆ_p （ｖ_j ，ｖ_z ） ＝Ｆ_p （ｖ_i ，ｖ_k ）○Ｆ_p （ｖ_i ，ｖ_l ） ○Ｆ_p （ｖ_j ，ｖ_k ）○Ｆ_p （ｖ_j ，ｖ_l ） ＝Ｋ_ik○Ｋ_il○Ｋ_jk○Ｋ_jl

【００７９】この条件は厳しく、途中の計算によらず、
最後の鍵共有形がべき積型となっているだけで条件１５
を満たさない。

【００８０】ところで、線形攻撃が適用できないために
は、例えば以下の条件１６を満たせば良い。 〔条件１６〕 攻撃目標のエンティティの公開鍵が、結託したエン
ティティの公開鍵の線形結合で表せない。 線形結合で表されるが、○の逆算法ができない。即
ち、下記式において、算法○に対するｆ（ｙ）の逆元が
求められない。 ｆ（ｘ−ｙ）＝ｆ（ｘ）○（ｆ（ｙ））^-1 エンティティは、自身の秘密鍵を知ることができな
い。

【００８１】このような条件１６を満たすことにより、
安全なべき型ＮＩＫＳを実現できる可能性がある。しか
しながら、現状では条件１６を満たす方式はなく、条
件１６を満たそうとする方式は、ユークリッド攻撃に
より、結託行列の逆行列が求まらなくても破れてしまう
ことが知られている。よって、条件１６を満たそうと
するアプローチが有力であると考えられる。

【００８２】以上のような考察に基づいて、本発明のＩ
Ｄ−ＮＩＫＳの暗号方式では、上述の共有鍵公開関数を
分離不可能な関数に設定する（条件１５）。また、個人
乱数を導入して各エンティティの秘密鍵を判らなくし、
この乱数も秘密と考えて上述の秘密鍵生成関数を分離不
可能な関数と見なせるようにする（条件１４）。更に、
各エンティティは自身の秘密鍵を知ることができないよ
うにする（条件１６）。以上のようにすれば、如何な
る人数のエンティティの結託に対しても安全であるＩＤ
−ＮＩＫＳを実現できる。

【００８３】

【発明の実施の形態】以下、本発明の実施の形態につい
て具体的に説明する。

【００８４】図１は、本発明の暗号通信方法を実施する
ためのシステムの構成を示す模式図である。情報の隠匿
を信頼できるセンタ１が設定されており、このセンタ１
としては、例えば社会の公的機関を該当できる。このセ
ンタ１と、この暗号系システムを利用するユーザとして
の複数の各エンティティａ，ｂ，…，ｚとは秘密通信路
２ａ，２ｂ，…，２ｚにより接続されており、この秘密
通信路秘密通信路暗号文を通信し合う２ａ，２ｂ，…，
２ｚを介してセンタ１から秘密の鍵情報が各エンティテ
ィａ，ｂ，…，ｚへ伝送されるようになっている。ま
た、２人のエンティティの間には通信路３ab，３az，３
bz，…が設けられており、この通信路３ab，３az，３b
z，…を介して通信情報を暗号化した暗号文が互いのエ
ンティティ間で伝送されるようになっている。

【００８５】以下に、本発明のＩＤ−ＮＩＫＳの実施の
形態を説明する。まず、（センタでの準備処理），（エ
ンティティの登録処理），（エンティティ間の共有鍵の
生成処理）の順序で、本発明の暗号系を説明する。

【００８６】（センタでの準備処理）センタは以下の公
開鍵及び秘密鍵を準備し、公開鍵を公開する。

【００８７】但し、λ（・）はCarmichael関数とする。
また、エンティティのＩＤ情報からｎ次元の公開鍵ベク
トルｖを計算するためのハッシュ関数ｈ（・）も同時に
公開する。ハッシュ関数はデータ列を別のデータ列に変
換する関数であり、一般的には長いデータ列を短いデー
タ列に変換する関数である。但し、このハッシュ関数を
用いて公開鍵ベクトルｖを計算した場合に、全成分の和
がｅとなるようにする。具体的には、公開鍵ベクトルｖ
が２値ベクトルである場合にはSchalkwijkアルゴリズム
を用いればよいし、一般的には、（ｎ−１）個の成分を
ハッシュ値で求め、最後の１個の成分を全体の和がｅと
なるように求めればよい。

【００８８】

【数２２】

【００８９】（エンティティの登録処理）エンティティ
ｉに登録を依頼されたセンタは、準備した鍵とエンティ
ティｉの公開鍵ベクトルｖ_i （＝ｈ（ＩＤ_i ））とを用
いて以下の計算を行って、エンティティｉのベクトルｘ
_i （特許請求の範囲の第１秘密鍵）とｙ_i （特許請求の
範囲の第２秘密鍵）とを求め、求めたベクトルｘ_i 及び
ｙ_i をエンティティｉへ秘密裏に送って、登録を完了す
る。この際、直接エンティティｉに秘密鍵ｓ_i を送らな
い。

【００９０】

【数２３】

【００９１】（エンティティ間の共有鍵の生成処理）エ
ンティティｉは、エンティティｊとの鍵共有を行うため
に、以下の計算を行って、ｋ_ij及び共有鍵Ｋ_ijを求め
る。

【００９２】

【数２４】

【００９３】上記ｋ_ij，Ｋ_ijを求める際の実際の計算の
手法を、ベクトルｖ_j が多値ベクトルである一般的な
場合、ベクトルｖ_j の各成分が比較的小さい場合、
ベクトルｖ_j が２値ベクトルである特別な場合に分け
て、下記に示す。

【００９４】

【数２５】

【００９５】次に、上述した暗号システムにおけるエン
ティティ間の情報の通信について説明する。図２は、２
人のエンティティａ，ｂ間における情報の通信状態を示
す模式図である。図２の例は、エンティティａが平文
（メッセージ）Ｍを暗号文Ｃに暗号化してそれをエンテ
ィティｂへ伝送し、エンティティｂがその暗号文Ｃを元
の平文（メッセージ）Ｍに復号する場合を示している。

【００９６】エンティティａ側には、エンティティｂの
個人識別情報ＩＤ_b を入力し、ハッシュ関数を利用して
ベクトルｖ_b （公開鍵）を得る公開鍵生成器１１と、セ
ンタから送られる秘密のベクトルｘ_a 及びｙ_a と公開鍵
生成器１１からの公開鍵であるベクトルｖ_b とに基づい
てエンティティａが求めるエンティティｂとの共有鍵Ｋ
_abを生成する共有鍵生成器１２と、共有鍵Ｋ_abを用いて
平文（メッセージ）Ｍを暗号文Ｃに暗号化して通信路３
０へ出力する暗号化器１３とが備えられている。また、
エンティティｂ側には、エンティティａの個人識別情報
ＩＤ_a を入力し、ハッシュ関数を利用してベクトルｖ_a
（公開鍵）を得る公開鍵生成器２１と、センタから送ら
れる秘密のベクトルｘ_b 及びｙ_b と公開鍵生成器２１か
らの公開鍵であるベクトルｖ_a とに基づいてエンティテ
ィｂが求めるエンティティａとの共有鍵Ｋ_baを生成する
共有鍵生成器２２と、共有鍵Ｋ_baを用いて通信路３０か
ら入力した暗号文Ｃを平文（メッセージ）Ｍに復号して
出力する復号器２３とが備えられている。

【００９７】図３は、図２の共有鍵生成器１２及び２２
の内部構成を示す図である。共有鍵生成器１２及び２２
は、センタから送られるベクトルｘを記憶する第１レジ
スタ４１と、ベクトルｘの各成分を記憶する第２レジス
タ４２と、公開鍵生成器１１及び２１から送られるベク
トルｖを記憶する第３レジスタ４３と、ベクトルｖの各
成分を記憶する第４レジスタ４４と、自然数Ｎを記憶す
る第５レジスタ４５と、第２，第４，第５レジスタ４
２，４４，４５の出力に応じて指数演算を行う第１高速
指数演算器４６と、予めセットされてｋを記憶する第６
レジスタ４７と、第１高速指数演算器４６及び第６レジ
スタ４７の出力を乗算する乗算器４８と、センタから送
られるｙを記憶する第７レジスタ４９と、自然数Ｐを記
憶する第８レジスタ５０と、第６，第７，第８レジスタ
４７，４９，５０の出力に応じて指数演算を行って共有
鍵Ｋを出力する第２高速指数演算器５１とを有する。

【００９８】なお、自然数Ｎ及びＰには、Ｐ＝Ｎ＋１の
関係があるので、第５レジスタ４５の最下位のビットを
１にして作成したものを第８レジスタ５０として利用す
るようにしても良い。また、ベクトルｘの各成分とｙ、
ベクトルｖの各成分とｋ、ｍｏｄ Ｎとｍｏｄ Ｐのそ
れぞれの入力を切り換えるようにすれば、１個の高速指
数演算器のみを使用する構成も可能である。

【００９９】次に、動作について説明する。エンティテ
ィａからエンティティｂへ情報を伝送しようとする場
合、まず、エンティティｂの個人識別情報ＩＤ_b が公開
鍵生成器１１に入力されてベクトルｖ_b （公開鍵）が得
られ、得られたベクトルｖ_b が共有鍵生成器１２へ送ら
れる。また、センタから（Ｂ）に従って求められたベク
トルｘ_a 及びｙ_a が共有鍵生成器１２へ入力される。図
３に示す構成を有する共有鍵生成器１２にて、（Ｃ）に
従って共有鍵Ｋ_abが求められ、暗号化器１３へ送られ
る。暗号化器１３において、この共有鍵Ｋ_abを用いて平
文（メッセージ）Ｍが暗号文Ｃに暗号化され、暗号文Ｃ
が通信路３０を介して伝送される。通信路３０を伝送さ
れた暗号文Ｃはエンティティｂの復号器２３へ入力され
る。エンティティａの個人識別情報ＩＤ_a が公開鍵生成
器２１に入力されてベクトルｖ_a （公開鍵）が得られ、
得られたベクトルｖ_a が共有鍵生成器２２へ送られる。
また、センタから（Ｂ）に従って求められたベクトルｘ
_b 及びｙ_b が共有鍵生成器２２へ入力される。図３に示
す構成を有する共有鍵生成器２２にて、（Ｃ）に従って
共有鍵Ｋ_baが求められ、復号器２３へ送られる。復号器
２３において、この共有鍵Ｋ_baを用いて暗号文Ｃが平文
（メッセージ）Ｍに復号される。

【０１００】次に、このような本発明の暗号系が、安全
なＩＤ−ＮＩＫＳを実現できていること、即ち、前述し
た条件１〜７を満たすことを検証する。

【０１０１】（条件１について）秘密鍵生成関数ｆ
（・）は、以下の式で定義され、センタにてエンティテ
ィの公開鍵から対応する秘密鍵を求めることができる。

【０１０２】

【数２６】

【０１０３】（条件２について）共有鍵生成関数Ｆ
（・）は、以下の式で定義され、一方のエンティティの
秘密鍵と他方のエンティティの公開鍵とから共有鍵を生
成できる。

【０１０４】

【数２７】

【０１０５】（条件３について）共有鍵公開関数Ｆ
_p （・）は、以下の式で定義され、Ｔが対称行列である
ので、以下の式で示すように、Ｆ_p （・）は対称関数で
あって、互いのエンティティが生成する共有鍵は等しく
なる。

【０１０６】

【数２８】

【０１０７】（条件４について）各エンティティは、セ
ンタ秘密である対称行列Ｔを知らない限り、自身の秘密
鍵を計算できない。

【０１０８】（条件５について）各エンティティは、セ
ンタ秘密である対称行列Ｔを知らない限り、エンティテ
ィ間の共有鍵を計算できない。

【０１０９】（条件６について）本発明の暗号方式は、
条件１４を直接的には満たさないが、条件１６を満た
すので、条件６も満たすことになる。例えば、ベクトル
ｖ_z ≡ベクトルｖ_i ＋ベクトルｖ_j である場合に、ベク
トルｓ_z ≡ベクトルｓ_i ・ベクトルｓ_j となるが、エン
ティティの秘密鍵のベクトルｓ_i をエンティティに直接
送付せずに、個人乱数ｒ_i を用いてベクトルｘ_i として
から送付するようにしているため、ベクトルｘ_z とベク
トルｘ_i ・ベクトルｘ_j とは等しくならず、個人秘密ベ
クトルｘ_zを求めることができない。なお、エンティテ
ィは自身の個人乱数を知ることはできないが、この個人
乱数は共有鍵を生成する段階で消去される。

【０１１０】（条件７について）共有鍵公開関数Ｆ
_p （・）は、以下の式で示されるように、分離不可能な
関数であるので、複数のエンティティの結託によって、
公開鍵と秘密鍵とをいくら集めても、他のいかなるエン
ティティ間の共有鍵を求められない。

【０１１１】

【数２９】

【０１１２】（条件８について）センタ秘密（ｐ，ｑ，
ｄ，Ｌ，ｒ_i ，ｇ及びＴ）は、複数のエンティティが結
託しても露呈しない。センタ秘密の中のｐ，ｑ，ｄ，
Ｌ，ｒ_i 及びｇが露呈しない根拠は以下の通りである。 ｐ，ｑ：素因数分解の難しさ ｄ，Ｌ：ＲＳＡ暗号系の安全性 ｒ_i ：離散対数問題の難しさ ｇ ：ｒ_i 未知による安全性

【０１１３】次に、結託攻撃に対する対称行列Ｔの安全
性について説明する。もし、本発明の暗号方式において
個人乱数がない場合、即ち、ベクトルｖ_i ，ベクトルｓ
_i ，ベクトルｖ_j ，ベクトルｓ_j ，…を用いた攻撃が可
能な場合、結託者１人についてｎ個の式が得られるが、
ｍ人が結託したとしてもｍｎ個の線形独立な式が得られ
るわけではない。

【０１１４】Ｔが対称行列であるので、最初の結託者１
人で最大ｎ個の線形独立な式が得られ、２人目が結託す
ることにより最大（ｎ−１）個の新たな線形独立な式が
得られる。以降同様に、新たに１人ずつ結託するエンテ
ィティが増えていくにつれて新たに得られる線形独立な
式が減っていく。従って、ｎ人のエンティティが結託す
る場合には、最大で、ｎ＋（ｎ−１）＋…＋２＋１＝
｛ｎ（ｎ＋１）／２｝個の線形独立な式が得られる。一
方、センタ秘密変数も｛ｎ（ｎ＋１）／２｝個であるの
で、ｎ人のエンティティの結託によって、対称行列Ｔが
解けることが考えられる。

【０１１５】次に、本発明の方式のように個人乱数が付
加されている場合を考えると、センタの秘密行列の｛ｎ
（ｎ＋１）／２｝個のセンタ秘密変数に加えて、更に個
人乱数もセンタ秘密変数となる。よって、ｍ人のエンテ
ィティが結託する場合には、センタ秘密変数は｛ｎ（ｎ
＋１）／２＋ｍ｝個となる。この結果、任意の人数のエ
ンティティが結託しても、対称行列Ｔを解くことは不可
能である。以下、これが不可能である理由を、結託人数
毎に分けて説明する。

【０１１６】（ｎ人未満のエンティティが結託する場
合）センタ秘密変数の数が、結託によって得られる線形
独立な式の数を上回るので、解くことができない。

【０１１７】（ｎ人のエンティティが結託する場合）最
初の１人では、上述した乱数を設けない場合と同様に最
大ｎ個の線形独立な式が得られる。次に、２人目が結託
すると、個人秘密乱数に関する項が１つ増えるので、乱
数を設けない場合に比べて１つ多い最大ｎ個の線形独立
な式が得られる。更に、３人目が結託すると、乱数を設
けない場合に比べて１つ多い最大（ｎ−１）個の線形独
立な式が得られる。以降同様に、新たに１人ずつ結託す
るエンティティが増えていくにつれて新たに得られる線
形独立な式が減っていく。従って、ｎ人のエンティティ
が結託する場合には、最大で、ｎ＋ｎ＋（ｎ−１）＋…
＋２＝｛ｎ（ｎ＋１）／２＋（ｎ−１）｝個の線形独立
な式が得られる。一方、センタ秘密変数は｛ｎ（ｎ＋
１）／２＋ｎ｝個であるので、線形独立な式の数がセン
タ秘密変数の数よりも１つ少なくなり、対称行列Ｔは解
けない。

【０１１８】（（ｎ＋１）人のエンティティが結託する
場合）ｎ人の場合に比べて新たに１つの個人秘密乱数が
加わるが、その他のｎ項は線形従属であるので、新たな
線形独立な式は１つしか得られない。このように、セン
タ秘密変数が１つ増加し、線形独立な式が１つ増加する
だけであるので、ｎ人の結託で解けなければ、（ｎ＋
１）人の結託でも対称行列Ｔは解けない。

【０１１９】（（ｎ＋２）人以上のエンティティが結託
する場合）ｎ人，（ｎ＋１）人の結託の場合の関係より
帰納的に、何人結託しても対称行列Ｔは解けない。

【０１２０】このように、センタでの秘密行列Ｔは任意
の人数のエンティティによる結託攻撃に対して安全であ
る。

【０１２１】ここで、個人乱数を設ける場合と個人乱数
を設けない場合とにおけるセンタの秘密行列Ｔの安全性
の具体例について説明する。図４は、個人乱数を設け
ず、５人のエンティティが結託した場合を示す。図４に
示すように、５×５の行列Ｔは対称行列であるので、成
分の未知数は１５個である。また、図４に示すように、
線形独立な式の数は５＋４＋３＋２＋１＝１５となる。
よって、未知数の個数と線形独立な式の数とが一致する
ため、解くことができ、センタの秘密行列Ｔが求められ
てしまうことになる。

【０１２２】一方、図５は、個人乱数を設け、５人のエ
ンティティが結託した場合を示す。個人乱数もセンタ側
での秘密と考えると、図５に示すように、未知数は行列
Ｔ由来の１５個と乱数由来の５個との合計２０個であ
る。また、図５に示すように、線形独立な式の数は５＋
５＋４＋３＋２＝１９となる。よって、未知数の個数が
線形独立な式の数より多くなるため、解くことができ
ず、センタの秘密が求められない。図６に、この場合の
方程式を示す。

【０１２３】次に、本発明の暗号通信方法における数値
例について説明する。図７〜図９に第１の数値例（公開
鍵のベクトルｖの成分が多値である場合）を示す。ま
ず、センタにて、図７（ａ）に示すように、公開鍵
（Ｐ，Ｎ，ｅ）及び秘密鍵（ｐ，ｑ，Ｌ，ｄ，ｇ，Ｔ，
ｒ_i ，ｒ_j ，ｒ_k ）を設定する。また、各エンティティ
ｉ，ｊ，ｋのＩＤに基づく多値の公開鍵のベクトル
ｖ_i ，ｖ_j ，ｖ_k を計算して、図７（ｂ）のように設定
する。このような設定条件に基づいて、各エンティティ
ｉ，ｊ，ｋのベクトルｘ_i ，ｘ_j ，ｘ_k を求めると図７
（ｃ）のようになり、ｒ_i ^-1，ｒ_j ^-1，ｒ_k ^-1及び
ｙ_i ，ｙ_j ，ｙ_k を求めると図７（ｄ）のようになる。
そして、エンティティｉ，ｊ間の共有鍵Ｋ_ij＝Ｋ_ji、エ
ンティティｉ，ｋ間の共有鍵Ｋ_ik＝Ｋ_ki、エンティティ
ｊ，ｋ間の共有鍵Ｋ_jk＝Ｋ_kjは、それぞれ、図８
（ａ），（ｂ），（ｃ）のように求まる。また、この第
１の数値例における結託攻撃に対する安全性を図９に示
す。未知数が９個あって線形独立な式の数が８本である
ので、解くことができず、センタでの秘密は保持され
る。

【０１２４】図１０，図１１に第２の数値例（公開鍵の
ベクトルｖの成分が２値である場合）を示す。まず、セ
ンタにて、図１０（ａ）に示すように、公開鍵（Ｐ，
Ｎ，ｅ）及び秘密鍵（ｐ，ｑ，Ｌ，ｄ，ｇ，Ｔ，ｒ_i ，
ｒ_j ）を設定する。また、各エンティティｉ，ｊのＩＤ
に基づく２値の公開鍵ベクトルｖ_i ，ｖ_j を計算して、
図１０（ｂ）のように設定する。このような設定条件に
基づいて、各エンティティｉ，ｊのｒ_i ^-1，ｒ_j ^-1及び
ベクトルｓ_i ，ｓ_j を求めると図１０（ｃ）のようにな
る。更に、エンティティｉにおけるベクトルｘ_i ，ｙ_i
及び，共有鍵Ｋ_ijを求めると図１１（ａ）に示すように
なり、同様に、エンティティｊにおけるベクトルｘ_j ，
ｙ_j 及び，共有鍵Ｋ_jiを求めると図１１（ｂ）に示すよ
うになる。

【０１２５】

【発明の効果】以上詳述したように、本発明では、前述
したＮＩＫＳを実現するための３つの条件及びその安全
性を確保するための５つの条件を満足するので、如何な
る人数のエンティティが結託しても、センタの秘密パラ
メータは露呈されず暗号文が復号されることがなく、極
めて高い安全性を達成できる。

【図面の簡単な説明】

【図１】本発明の暗号通信方法を実施するためのシステ
ムの構成を示す模式図である。

【図２】２人のエンティティ間における情報の通信状態
を示す模式図である。

【図３】図２の共有鍵生成器の内部構成を示す図であ
る。

【図４】個人乱数を設けない場合のセンタでの秘密の安
全性を説明する図である。

【図５】個人乱数を設けた場合のセンタでの秘密の安全
性を説明する図である。

【図６】本発明の安全性を表す数値例を示す図である。

【図７】本発明の第１の数値例を示す図である。

【図８】本発明の第１の数値例を示す図である。

【図９】本発明の第１の数値例を示す図である。

【図１０】本発明の第２の数値例を示す図である。

【図１１】本発明の第２の数値例を示す図である。

【図１２】ＩＤ−ＮＩＫＳのシステムの原理構成図であ
る。

【符号の説明】

１ センタ １１，２１ 公開鍵生成器 １２，２２ 共有鍵生成器 １３ 暗号化器 ２３ 復号器 ３０ 通信路

───────────────────────────────────────────────────── フロントページの続き (72)発明者 笠原 正雄 大阪府箕面市粟生外院４丁目15番３号 (72)発明者 藤川 篤則 東京都町田市中町２−２−８ (72)発明者 村上 恭通 京都府宇治市槙島町本屋敷51−６ 村田 機械株式会社社宅Ｂ棟602号 (56)参考文献 特開 平８−8972（ＪＰ，Ａ) 予備通信不要なＩＤ−ｂａｓｅｄ暗号 化鍵共有の新方式の提案（第３報），電 子情報通信学会技術研究報告，1991年11 月29日，Ｖｏｌ．91，Ｎｏ．359（ＩＳ ＥＣ91−39），ｐ．21−24 ＩＤによる共通暗号化鍵生成方式 逐 次加算型乱数項消去法の提案，電子情報 通信学会技術研究報告，1992年12月 ７ 日，Ｖｏｌ．92，Ｎｏ．355（ＩＳＥＣ 92−60），ｐ．29−38 (58)調査した分野(Int.Cl.⁷，ＤＢ名) H04L 9/08 ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】 センタ装置から複数のエンティティ装置
   夫々へ各エンティティ固有の暗号鍵を送付し、一方のエ
   ンティティ装置が前記センタ装置から送付された該エン
   ティティ固有の暗号鍵と公開された他方のエンティティ
   の公開鍵とを利用して平文を暗号文に暗号化して他方の
   エンティティ装置へ伝送し、該他方のエンティティ装置
   が伝送された暗号文を前記センタ装置から送付された該
   エンティティ固有の暗号鍵と公開された前記一方のエン
   ティティの公開鍵とを利用して元の平文に復号すること
   により、エンティティ装置間で情報の通信を行う暗号通
   信方法において、前記センタ装置にて、 公開鍵として公開された各エンテ
   ィティ固有の第１の鍵とセンタ装置が管理する対称行列
   とから（２）式に基づいて、第１の鍵を変数とする第１
   の関数で表される各エンティティ固有の秘密の第２の鍵
   を生成し、各エンティティ固有の乱数と第２の鍵とから
   （３）式に基づいて第１秘密鍵を生成し、前記乱数から
   （４）式に基づいて第２秘密鍵を生成し、生成した第１
   秘密鍵及び第２秘密鍵を各エンティティ装置に送付し、 一方のエンティティ装置にて、第１秘密鍵及び第２秘密
   鍵と他方のエンティティの第１の鍵とを用いて、 自身の
   第２の鍵及び相手の第１の鍵を２変数とする第２の関数
   で表され、平文を暗号文に暗号化する際及び暗号文を平
   文に復号する際に用いる両エンティティ間で共有する第
   ３の鍵を（５），（６）式に基づいて生成し、 第１の鍵、第２の鍵及び第３の鍵を 使用して、エンティ
   ティ装置間で暗号化した情報の通信を行うこととする
   が、第２の関数に第１の関数を代入して得られる、自身
   及び相手の第１の鍵を変数とする第３の関数を、それぞ
   れの変数について（１）式に定義されるような分離不可
   能な関数に設定することを特徴とする暗号通信方法。ｆ（ｘ＋ｙ）≠ｆ（ｘ）○ｆ（ｙ） …（１） 但し、 適当な可換な算法を○として、関数ｆ（・）が次
   式を満たす場合に、関数ｆ（・）は算法○により分離不
   可能であると定義する。 【数１】 【数２】