(57)【要約】【課題】  ＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつことを特長とする安全性の高い公開鍵暗号方式およびＩＤベース暗号方式を提供すること。【解決手段】  暗号文の受信者となる受信者側装置１１０は、乱数ｓ１,ｓ２を選び、公開の鍵情報の一部として、Ｐ,Ｑ∈Ｇ1、および、双線形写像ｅ：Ｇ1×Ｇ1→Ｇ2、を作成し、さらに、Ｐ1=s1ＰおよびＰ2=s2Ｐを公開の鍵情報の一部として作成する。暗号文の送信者である送信者側装置１２０は、受信者側装置１１０の公開の鍵情報Ｑ、双線形写像ｅを用いて、e(Ｑ,Ｐ1)およびe(Ｑ,Ｐ2)を計算し、さらに、これらの情報e(Ｑ,Ｐ1)およびe(Ｑ,Ｐ2)を用いて受信者側装置１１０に送信する暗号文を作成する。【選択図】図１
2008058944.tif 000002
【特許請求の範囲】
【請求項１】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
前記受信者側装置又は鍵管理センタ側装置が、
乱数ｓ１,ｓ２を選択するステップと、
公開する鍵情報の一部として、Ｐ,Ｑ∈Ｇ1、および、双線形写像ｅ：Ｇ1×Ｇ1→Ｇ2、を作成するステップと、
Ｐ1=s1ＰおよびＰ2=s2Ｐを公開する鍵情報の一部として作成するステップと、
作成したＰ、Ｑ、ｅ、Ｐ１、Ｐ２を、前記送信者側装置に送信するステップと、
を備え、
前記送信者側装置は、
前記受信者側装置又は前記鍵管理センタ側装置から、Ｐ、Ｑ、ｅ、Ｐ１、Ｐ２を受信するステップと、
受信したＰ、Ｑ、ｅ、Ｐ１、Ｐ２を用いて、e(Ｑ,Ｐ1)およびe(Ｑ,Ｐ2)を計算するステップと、
計算されたe(Ｑ,Ｐ1)およびe(Ｑ,Ｐ2)を用いて、前記受信者側装置に送信する暗号文を作成するステップと、
を備えること、
を特徴とする暗号通信方法。
【請求項２】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
（１）前記受信者側装置が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数１】
2008058944.tif 000106
なる双線形写像ｅを作成するステップと、
s1,s2∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶステップと、
【数２】
2008058944.tif 000107
を算出するステップと、
SKA=（s1Ｑ,s2Ｑ）を復号化鍵とし、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２）を暗号化鍵として、記憶部に記憶するステップ（但し、m,nは自然数、Ｈ１,Ｈ２は、
【数３】
2008058944.tif 000108
なるハッシュ関数を意味する。）と、
前記暗号化鍵PKAを出力するステップと、
を行い、
（２）前記送信者側装置が、
メッセージ文Ｍ∈{0,1}nに対して、ｒ∈Ｚｑをランダムに選ぶステップと、
前記受信者側装置が出力した前記暗号化鍵PKAを用いて、
【数４】
2008058944.tif 000109
を計算するステップと、
計算したＣ＝（Ｕ,Ｖ,Ｗ）を前記メッセージ文Ｍの暗号文として前記受信者側装置に送信するステップと、
を行い、
（３）前記受信者側装置が、
前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）に対して、前記記憶部に記憶した前記復号化鍵SKAを用いて、
【数５】
2008058944.tif 000110
により、Ｍ∈｛０，１｝nを計算するステップと、
【数６】
2008058944.tif 000111
の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
を行うこと、
を特徴とする暗号通信方法。
【請求項３】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
（１）前記受信者側装置が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数７】
2008058944.tif 000112
なる双線形写像ｅを作成するステップと、
s1,s2∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶステップと、
【数８】
2008058944.tif 000113
を算出するステップと、
SKA=（s1Ｑ,s2Ｑ）を復号化鍵とし、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３）を暗号化鍵として、記憶部に記憶するステップ（但し、m,nは自然数、Ｈ１,Ｈ２,Ｈ３は、
【数９】
2008058944.tif 000114
なるハッシュ関数を意味する。）と、
前記暗号化鍵PKAを出力するステップと、
を行い、
（２）前記送信者側装置が、
メッセージ文Ｍ∈{0,1}nに対して、σ∈{0,1}mをランダムに選ぶステップと、
前記受信者側装置が出力した前記暗号化鍵PKAを用いて、
【数１０】
2008058944.tif 000115
を計算するステップと、
【数１１】
2008058944.tif 000116
を計算するステップと、
計算したＣ＝（Ｕ,Ｖ,Ｗ）を前記メッセージ文Ｍの暗号文として前記受信者側装置に送信するステップと、
を行い、
（３）前記受信者側装置が、
前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）に対して、前記記憶部に記憶した前記復号化鍵SKAを用いて、
【数１２】
2008058944.tif 000117
により、σ∈｛０，１｝ｍを計算するステップと、
【数１３】
2008058944.tif 000118
により、Ｍを計算するステップと、
【数１４】
2008058944.tif 000119
により、r∈Ｚqを計算するステップと、
【数１５】
2008058944.tif 000120
の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
を行うこと
を特徴とする暗号通信方法。
【請求項４】
送信者側装置が、鍵管理センタ側装置により作成されたシステムパラメータを用いてメッセージ文の暗号文を作成し、受信者側装置が前記鍵管理センタ側装置により作成されたＩＤベース暗号用秘密鍵を用いて前記暗号文を復号する暗号通信方法であって、
（１）前記鍵管理センタ側装置が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数１６】
2008058944.tif 000121
なる双線形写像ｅを作成するステップと、
s0,s1∈Ｚ*qおよびＰ∈Ｇ1をランダムに選ぶステップと、
【数１７】
2008058944.tif 000122
を作成するステップと、
(s0,s1)をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,0,Ｐpub,1,Ｈ１,Ｈ２,Ｈ３,Ｈ4,Ｅ,Ｄ）を前記システムパラメータとして、記憶部に記憶するステップ（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２,Ｈ３,Ｈ4は、
【数１８】
2008058944.tif 000123
なるハッシュ関数を意味する。）と、
前記システムパラメータＰＫを出力するステップと、
前記受信者側装置より受信した受信者側ユーザの個別情報ＩＤAを記憶部に記憶するステップと、
ｂIDA∈{0,1}をランダムに選ぶステップと、
前記マスタ鍵(s0,s1)を用いて、
【数１９】
2008058944.tif 000124
を計算するステップと、
計算したＳＫＡ＝（ｂIDA,dIDA,0,dIDA,1）を前記受信者側ユーザのプライベート鍵として出力するステップと、
を行い、
（２）前記送信者側装置が、
メッセージ文Ｍ∈｛０，１｝ｎに対して、Ｒ∈｛０，１｝lをランダムに選ぶステップと、
メッセージ文Ｍ及びＲ、前記受信者側装置より受信した前記個別情報ＩＤＡ、前記鍵管理センタ側装置より出力された前記システムパラメータＰＫを用いて、
【数２０】
2008058944.tif 000125
なるｒ∈ＺqおよびＫ∈｛０，１｝mを計算するステップと、
【数２１】
2008058944.tif 000126
を計算するステップ（但し、ＥＫ（Ｍ）は平文Ｍをデータ暗号化鍵Ｋを用いて暗号化した結果を表す）と、
計算したＣ＝（Ｕ,Ｖ0,Ｖ1,Ｗ,Ｚ）を暗号文として前記受信者側装置に送信するステップと、
を行い、
（３）前記受信者側装置が、
前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ,Ｖ0,Ｖ1,Ｗ,Ｚ）に対して、前記鍵管理センタ側装置より出力された前記プライベート鍵ＳＫＡを用いて、
【数２２】
2008058944.tif 000127
なるＲ∈｛０，１｝lを計算するステップと、
【数２３】
2008058944.tif 000128
により、ｒ∈ＺqおよびＫ∈｛０，１｝mを計算するステップと、
【数２４】
2008058944.tif 000129
により、Ｍ∈｛０，１｝nを計算するステップ（但し、ＤＫ（Ｙ）は暗号文Ｙを鍵Ｋを用いて復号化した結果を表す。）と、
【数２５】
2008058944.tif 000130
の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
を行うこと、
を特徴とする暗号通信方法。
【請求項５】
請求項４に記載の暗号通信方法であって、
ハッシュ関数Ｈ１からＨ４への入力値を別のパラメータに変更することにより、暗号文の作成および復号化を行うこと、
を特徴とする暗号通信方法。
【請求項６】
送信者側装置が、鍵管理センタ側装置により作成されたシステムパラメータを用いてメッセージ文の暗号文を作成し、受信者側装置が前記鍵管理センタ側装置により作成されたＩＤベース暗号用秘密鍵を用いて前記暗号文を復号する暗号通信方法であって、
（１）前記鍵管理センタ側装置が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数２６】
2008058944.tif 000131
なる双線形写像ｅを作成するステップと、
s10,s11,s20,s21∈Ｚ*qおよびＰ∈Ｇ1をランダムに選ぶステップと、
【数２７】
2008058944.tif 000132
を作成するステップと、
ＳＫ＝（s10,s11,s20,s21）をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,10,Ｐpub,11,Ｐpub,1,Ｐpub,20,Ｐpub,21,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３,Ｈ4,Ｅ,Ｄ）をシステムパラメータとして、記憶部に記憶するステップ（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２,Ｈ３,Ｈ4は、
【数２８】
2008058944.tif 000133
なるハッシュ関数を意味する。）と、
前記システムパラメータＰＫを出力するステップと、
前記受信者側装置より受信した受信者側ユーザの個別情報ＩＤAを記憶部に記憶するステップと、
ｂIDA∈{0,1}をランダムに選ぶステップと、
前記マスタ鍵ＳＫを用いて、
【数２９】
2008058944.tif 000134
を計算するステップと、
計算したＳＫＡ＝（ｂIDA,d(1,IDA),d(2,IDA)）を前記受信者側ユーザのプライベート鍵として出力するステップと、
を行い、
（２）前記送信者側装置が、
メッセージ文Ｍ∈｛０，１｝ｎに対して、Ｒ∈｛０，１｝lをランダムに選ぶステップと、
メッセージ文Ｍ及びＲ、前記受信者側装置より受信した前記個別情報ＩＤＡ、前記鍵管理センタ側装置より出力されたシステムパラメータＰＫを用いて、
【数３０】
2008058944.tif 000135
なるｒ0,r1∈ＺqおよびＫ∈｛０，１｝mを計算するステップと、
【数３１】
2008058944.tif 000136
を計算するステップ（但し、ＥＫ（Ｍ）は平文Ｍをデータ暗号化鍵Ｋを用いて暗号化した結果を表す）と、
計算したＣ＝（Ｕ10,Ｕ11,Ｕ20,Ｕ21,Ｖ0,Ｖ1,Ｗ,Ｚ）を暗号文として前記受信者側装置に送信するステップと、
を行い、
（３）前記受信者側装置が、
前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ10,Ｕ11,Ｕ20,Ｕ21,Ｖ0,Ｖ1,Ｗ,Ｚ）に対して、前記鍵管理センタ側装置より出力された前記プライベート鍵ＳＫＡを用いて、
【数３２】
2008058944.tif 000137
なるＲ∈｛０，１｝lを計算するステップと、
【数３３】
2008058944.tif 000138
により、ｒ0,r1∈ＺqおよびＫ∈｛０，１｝mを計算するステップと、
【数３４】
2008058944.tif 000139
なるＲ’∈｛０，１｝lを計算するステップと、
【数３５】
2008058944.tif 000140
の第一の検査式が成立するか否かを検査するステップと、
前記第一の検査式が成立する場合に、
【数３６】
2008058944.tif 000141
を計算するステップ（但し、ＤＫ（Ｙ）は暗号文Ｙを鍵Ｋを用いて復号化した結果を表す。）と、
【数３７】
2008058944.tif 000142
の第二の検査式が成立するか否かを検査するステップと、
前記第二の検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記第一の検査式又は前記第二の検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
を行うこと、
を特徴とする暗号通信方法。
【請求項７】
請求項６に記載の暗号通信方法であって、
ハッシュ関数Ｈ１からＨ４への入力値を別のパラメータに変更することにより、暗号文の作成および復号化を行う
ことを特徴とする暗号通信方法。
【請求項８】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信システムであって、
前記受信者側装置又は鍵管理センタ側装置の演算部は、
乱数ｓ１,ｓ２を選択する処理と、
公開する鍵情報の一部として、Ｐ,Ｑ∈Ｇ1、および、双線形写像ｅ：Ｇ1×Ｇ1→Ｇ2、を作成する処理と、
Ｐ1=s1ＰおよびＰ2=s2Ｐを公開する鍵情報の一部として作成する処理と、
作成したＰ、Ｑ、ｅ、Ｐ１、Ｐ２を、通信部を介して前記送信者側装置に送信する処理と、
を行い、
前記送信者側装置の演算部は、
前記受信者側装置又は前記鍵管理センタ側装置から、Ｐ、Ｑ、ｅ、Ｐ１、Ｐ２を、通信部を介して受信する処理と、
受信したＰ、Ｑ、ｅ、Ｐ１、Ｐ２を用いて、e(Ｑ,Ｐ1)およびe(Ｑ,Ｐ2)を計算する処理と、
計算されたe(Ｑ,Ｐ1)およびe(Ｑ,Ｐ2)を用いて、前記受信者側装置に送信する暗号文を作成する処理と、
を行うこと、
を特徴とする暗号通信システム。
【請求項９】
送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置であって、
演算部が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数３８】
2008058944.tif 000143
なる双線形写像ｅを作成する処理と、
s1,s2∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶ処理と、
【数３９】
2008058944.tif 000144
を算出する処理と、
SKA=（s1Ｑ,s2Ｑ）を復号化鍵とし、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２）を暗号化鍵として、記憶部に記憶する処理（但し、m,nは自然数、Ｈ１,Ｈ２は、
【数４０】
2008058944.tif 000145
なるハッシュ関数を意味する。）と、
前記暗号化鍵PKAを出力する処理と、
を行うこと、
を特徴とする受信者側装置。
【請求項１０】
送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置であって、
演算部が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数４１】
2008058944.tif 000146
なる双線形写像ｅを作成する処理と、
s1,s2∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶ処理と、
【数４２】
2008058944.tif 000147
を算出する処理と、
SKA=（s1Ｑ,s2Ｑ）を復号化鍵とし、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３）を暗号化鍵として、記憶部に記憶する処理（但し、m,nは自然数、Ｈ１,Ｈ２,Ｈ３は、
【数４３】
2008058944.tif 000148
なるハッシュ関数を意味する。）と、
前記暗号化鍵PKAを出力する処理と、
を行うこと、
を特徴とする受信者側装置。
【請求項１１】
送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置であって、
演算部が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数４４】
2008058944.tif 000149
なる双線形写像ｅを作成する処理と、
s0,s1∈Ｚ*qおよびＰ∈Ｇ1をランダムに選ぶ処理と、
【数４５】
2008058944.tif 000150
を作成する処理と、
(s0,s1)をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,0,Ｐpub,1,Ｈ１,Ｈ２,Ｈ３,Ｈ4,Ｅ,Ｄ）を前記システムパラメータとして、記憶部に記憶する処理（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２,Ｈ３,Ｈ4は、
【数４６】
2008058944.tif 000151
なるハッシュ関数を意味する。）と、
前記システムパラメータＰＫを出力する処理と、
受信者側装置より受信した受信者側ユーザの個別情報ＩＤAを記憶部に記憶する処理と、
ｂIDA∈{0,1}をランダムに選ぶ処理と、
前記マスタ鍵(s0,s1)を用いて、
【数４７】
2008058944.tif 000152
を計算する処理と、
計算したＳＫＡ＝（ｂIDA,dIDA,0,dIDA,1）を前記受信者側ユーザのプライベート鍵として出力する処理と、
を行うこと、
を特徴とする鍵管理センタ側装置。
【請求項１２】
送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置であって、
演算部が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数４８】
2008058944.tif 000153
なる双線形写像ｅを作成する処理と、
s10,s11,s20,s21∈Ｚ*qおよびＰ∈Ｇ1をランダムに選ぶ処理と、
【数４９】
2008058944.tif 000154
を作成する処理と、
ＳＫ＝（s10,s11,s20,s21）をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,10,Ｐpub,11,Ｐpub,1,Ｐpub,20,Ｐpub,21,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３,Ｈ4,Ｅ,Ｄ）をシステムパラメータとして、記憶部に記憶する処理（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２,Ｈ３,Ｈ4は、
【数５０】
2008058944.tif 000155
なるハッシュ関数を意味する。）と、
前記システムパラメータＰＫを出力する処理と、
受信者側装置より受信した受信者側ユーザの個別情報ＩＤAを記憶部に記憶する処理と、
ｂIDA∈{0,1}をランダムに選ぶ処理と、
前記マスタ鍵ＳＫを用いて、
【数５１】
2008058944.tif 000156
を計算する処理と、
計算したＳＫＡ＝（ｂIDA,d(1,IDA),d(2,IDA)）を前記受信者側ユーザのプライベート鍵として出力する処理と、
を行うこと、
を特徴とする鍵管理センタ側装置。
【請求項１３】
コンピュータを、
送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置として機能させるプログラムであって、
前記コンピュータの演算手段に、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数５２】
2008058944.tif 000157
なる双線形写像ｅを作成する処理と、
s1,s2∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶ処理と、
【数５３】
2008058944.tif 000158
を算出する処理と、
SKA=（s1Ｑ,s2Ｑ）を復号化鍵とし、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２）を暗号化鍵として、記憶手段に記憶する処理（但し、m,nは自然数、Ｈ１,Ｈ２は、
【数５４】
2008058944.tif 000159
なるハッシュ関数を意味する。）と、
前記暗号化鍵PKAを出力する処理と、
を行わせること、
を特徴とするプログラム。
【請求項１４】
コンピュータを、
送信者側装置がメッセージ文の暗号文を作成するための暗号鍵を生成する受信者側装置として機能させるプログラムであって、
前記コンピュータの演算手段に、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数５５】
2008058944.tif 000160
なる双線形写像ｅを作成する処理と、
s1,s2∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶ処理と、
【数５６】
2008058944.tif 000161
を算出する処理と、
SKA=（s1Ｑ,s2Ｑ）を復号化鍵とし、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３）を暗号化鍵として、記憶部に記憶する処理（但し、m,nは自然数、Ｈ１,Ｈ２,Ｈ３は、
【数５７】
2008058944.tif 000162
なるハッシュ関数を意味する。）と、
前記暗号化鍵PKAを出力する処理と、
を行わせること、
を特徴とするプログラム。
【請求項１５】
コンピュータを、
送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置として機能させるプログラムであって、
前記コンピュータの演算手段に、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数５８】
2008058944.tif 000163
なる双線形写像ｅを作成する処理と、
s0,s1∈Ｚ*qおよびＰ∈Ｇ1をランダムに選ぶ処理と、
【数５９】
2008058944.tif 000164
を作成する処理と、
(s0,s1)をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,0,Ｐpub,1,Ｈ１,Ｈ２,Ｈ３,Ｈ4,Ｅ,Ｄ）を前記システムパラメータとして、記憶手段に記憶する処理（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２,Ｈ３,Ｈ4は、
【数６０】
2008058944.tif 000165
なるハッシュ関数を意味する。）と、
前記システムパラメータＰＫを出力する処理と、
受信者側装置より受信した受信者側ユーザの個別情報ＩＤAを記憶手段に記憶する処理と、
ｂIDA∈{0,1}をランダムに選ぶ処理と、
前記マスタ鍵(s0,s1)を用いて、
【数６１】
2008058944.tif 000166
を計算する処理と、
計算したＳＫＡ＝（ｂIDA,dIDA,0,dIDA,1）を前記受信者側ユーザのプライベート鍵として出力する処理と、
を行わせること、
を特徴とするプログラム。
【請求項１６】
コンピュータを、
送信者側装置がメッセージ文の暗号文を作成するためのシステムパラメータを生成する鍵管理センタ側装置として機能させるプログラムであって、
前記コンピュータの演算手段に、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【数６２】
2008058944.tif 000167
なる双線形写像ｅを作成する処理と、
s10,s11,s20,s21∈Ｚ*qおよびＰ∈Ｇ1をランダムに選ぶ処理と、
【数６３】
2008058944.tif 000168
を作成する処理と、
ＳＫ＝（s10,s11,s20,s21）をマスタ鍵とし、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,10,Ｐpub,11,Ｐpub,1,Ｐpub,20,Ｐpub,21,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３,Ｈ4,Ｅ,Ｄ）をシステムパラメータとして、記憶部に記憶する処理（但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２,Ｈ３,Ｈ4は、
【数６４】
2008058944.tif 000169
なるハッシュ関数を意味する。）と、
前記システムパラメータＰＫを出力する処理と、
受信者側装置より受信した受信者側ユーザの個別情報ＩＤAを記憶手段に記憶する処理と、
ｂIDA∈{0,1}をランダムに選ぶ処理と、
前記マスタ鍵ＳＫを用いて、
【数６５】
2008058944.tif 000170
を計算する処理と、
計算したＳＫＡ＝（ｂIDA,d(1,IDA),d(2,IDA)）を前記受信者側ユーザのプライベート鍵として出力する処理と、
を行わせること、
を特徴とするプログラム。
【請求項１７】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
前記受信者側装置又は鍵管理センタ側装置が、
公開鍵と秘密鍵のペアを複数生成する鍵生成ステップと、
前記鍵生成ステップで生成した複数の公開鍵を含む公開鍵情報を生成するステップと、
前記鍵生成ステップで生成した複数の秘密鍵を含む秘密鍵情報を生成するステップと、
前記送信者側装置が、
前記公開鍵情報を取得するステップと、
前記公開鍵情報に含まれる複数の公開鍵の全てを用いてメッセージを暗号化した暗号文を生成するステップと、
前記受信者側装置が、
前記暗号文を取得するステップと、
前記暗号文を前記秘密鍵情報で復号するステップと、
を備えることを特徴とする暗号通信方法。
【請求項１８】
請求項１７に記載の暗号通信方法であって、
前記公開鍵及び前記秘密鍵は、任意の暗号方式を選択することができること、
を特徴とする暗号通信方法。
【請求項１９】
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信システムであって、
前記受信者側装置又は鍵管理センタ側装置の演算部が、
公開鍵と秘密鍵のペアを複数生成する鍵生成処理と、
前記鍵生成処理で生成した複数の公開鍵を含む公開鍵情報を生成する処理と、
前記鍵生成処理で生成した複数の秘密鍵を含む秘密鍵情報を生成する処理と、
前記送信者側装置の演算部が、
前記公開鍵情報を取得する処理と、
前記公開鍵情報に含まれる複数の公開鍵の全てを用いてメッセージを暗号化した暗号文を生成する処理と、
前記受信者側装置の演算部が、
前記暗号文を取得する処理と、
前記暗号文を前記秘密鍵情報で復号する処理と、
を備えることを特徴とする暗号通信装置。
【請求項２０】
請求項１９に記載の暗号通信装置であって、
前記公開鍵及び前記秘密鍵は、任意の暗号方式を選択することができること、
を特徴とする暗号通信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号通信の技術に関する。
【背景技術】
【０００２】
公開鍵暗号システムにおいては、ユーザが作成した公開鍵を認証局（ＣＡ）に登録し、証明書を発行してもらう必要がある。すなわち、暗号文の送信者は受信者の公開鍵とその正当性の根拠である証明書を手に入れ、その上で送信するメッセージ文の暗号化を行う必要がある。
【０００３】
これに対して、ＣＡの証明書発行の手間を省いて、より簡単な公開鍵の管理を行うことを目的として、ユーザのＩＤ情報を公開鍵とする暗号システム（以下、ＩＤベース暗号システム）が提案された。
【０００４】
ＩＤベース暗号システムでは、暗号通信、認証（ディジタル署名、個人認証、等）を目的として用途に応じたアルゴリズムが用いられる。
【０００５】
例えば、暗号通信の場合、ユーザは、自身のＩＤ情報を公開鍵として鍵管理センタに登録し、該ＩＤ情報に対応するプライベート鍵を発行してもらう。暗号文の送信者は、受信者の該ＩＤ情報と鍵管理センタが作成したシステム・パラメータを用いて暗号文を作成し、受信者に送信する。受信者は、該プライベート鍵を用いてメッセージの復号化を行う。
【０００６】
公開鍵暗号システムでは、受信者の公開鍵はランダムなビット列であるのに対して、ＩＤベース暗号システムでは、メールアドレス等の個人情報であるため、取り扱いが容易で証明書を不要とすることができる。
【０００７】
多くのＩＤベース暗号方式が提案されたが、安全性の証明が可能な方式は長い間知られていなかったが、２００１年に、非特許文献１において、楕円曲線上の双線形写像の特性を利用することで、安全性の証明が可能な初めてのＩＤベースの暗号通信方式が提案された。非特許文献１の方式では、安全性を高めるために、非特許文献２に記載の変換方法を利用している。
【０００８】
以降、双線形写像を利用した様々な暗号システムが提案されるようになった。非特許文献２では、非特許文献１に記載の暗号通信方式をベースとして階層化されたシステムにおける安全性証明可能な階層的ＩＤベース暗号通信方式が提案された。
【０００９】
非特許文献３では、安全性証明において、タイトなセキュリティ・リダクションを実現するためのアイデアが提案され、非特許文献４では、同アイデアを用いて、タイトなセキュリティ・リダクションをもつＩＤベース暗号方法が具体的に提案された。
【００１０】
【非特許文献１】Boneh and M. Franklin. Identity Based Encryption From the Weil Pairing, http://crypto.stanford.edu/~dabo/pubs.html
【非特許文献２】E.Fujisaki and T.Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes, Crypto’99, LNCS1666, Springer-Verlag, pp.537554 （1999）
【非特許文献３】C. Gentry and A. Silverberg. Hierarchical ID-based Cryptography, http://eprint.iacr.org/2002/056
【非特許文献４】J. Katz, N. Wang. Efficiency Improvements for Signature Schemes with Tight Security Reductions, http://www.cs.umd.edu/~jkatz/
【非特許文献５】N. Attrapadung, J. Furukawa, T. Gomi, G. Hanaoka, H. Imai, R. Zhang. Identity-Based Encryption Schemes with Tight Security Reductions, http://eprint.iacr.org/2005/320
【発明の開示】
【発明が解決しようとする課題】
【００１１】
近年提案されている暗号には、その暗号の安全性の証明が可能であるものが多い。すなわち、暗号を破ることの計算量を数論問題などの計算量的複雑性をもつ問題（例えば、素因数分解問題、離散対数問題、Diffie-Hellman 問題、等）に置き換えて定量的に評価する。
【００１２】
セキュリティ・リダクションとは、暗号方式が安全性を証明する場合において、安全性の根拠（暗号学的仮定）とする数論問題の計算量的困難性と暗号方式の安全性の関係を示すひとつのパラメータである。セキュリティ・リダクションがタイトであることは、暗号の安全性が暗号学的仮定とする数論問題の計算量的困難性に近いことを意味する。
【００１３】
このことは、セキュリティ・リダクションの悪い（タイトでない）暗号方式と比較した場合、セキュリティ・リダクションがタイトな方式はより高い安全性を有することを意味し、また、一定の安全性を得るために必要な鍵長を短く設定できるメリットを有する。
【００１４】
ここで、セキュリティ・リダクションがタイトであったとしても、暗号学的仮定に用いられる数論問題の計算量的困難性が期待できないような場合には暗号の安全性に意味はなくなってしまう。よって、より計算量的困難性が期待されているような問題に対して、タイトなセキュリティ・リダクションを持ち、安全性が証明できるような暗号方式が理想的である。
【００１５】
本発明では、十分に計算量的困難性が期待されているＢＤＨ（Bilinear Diffie-Hellman）問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつことを特長とする安全性の高い公開鍵暗号方式およびＩＤベース暗号方式を提供することを目的とする。
【００１６】
また、さらに、ＢＤＨ問題よりも計算量的に簡単な問題であるＬＢＤＨ（List Bilinear Diffie-Hellman）問題に対してタイトなセキュリティ・リダクションを持つ暗号を用いた暗号システムが既に存在した場合において、暗号部分の入れ替えを行うのではなく、既に使われている暗号を利用しながら、ＢＤＨ問題に対してタイトなセキュリティ・リダクションを持つ暗号を用いた暗号システムに変換する方法を提供することを目的とする。
【課題を解決するための手段】
【００１７】
上記課題を解決するために、本発明では、双線形写像ｅ：Ｇ1×Ｇ1→Ｇ2、Ｐ,Ｑ∈Ｇ1、に対して、乱数ｓ１,ｓ２を選び、Ｐ1=ｓ１ＰおよびＰ2=ｓ２Ｐを公開の鍵情報の一部として作成し、暗号文の送信者は、e（Ｑ,Ｐ1）およびe（Ｑ,Ｐ2）を計算し、これらの値を用いて暗号文を作成する。以下、実現するための公開鍵暗号の一具体例について説明する。
【００１８】
例えば、本発明は、送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、前記受信者側装置又は鍵管理センタ側装置が、乱数ｓ１,ｓ２を選択するステップと、公開する鍵情報の一部として、Ｐ,Ｑ∈Ｇ1、および、双線形写像ｅ：Ｇ1×Ｇ1→Ｇ2、を作成するステップと、Ｐ1=ｓ１ＰおよびＰ2=ｓ２Ｐを公開する鍵情報の一部として作成するステップと、作成したＰ、Ｑ、ｅ、Ｐ１、Ｐ２を、前記送信者側装置に送信するステップと、を備え、前記送信者側装置は、前記受信者側装置又は前記鍵管理センタ側装置から、Ｐ、Ｑ、ｅ、Ｐ１、Ｐ２を受信するステップと、受信したＰ、Ｑ、ｅ、Ｐ１、Ｐ２を用いて、e（Ｑ,Ｐ1）およびe（Ｑ,Ｐ2）を計算するステップと、計算されたe（Ｑ,Ｐ1）およびe（Ｑ,Ｐ2）を用いて、前記受信者側装置に送信する暗号文を作成するステップと、を備えること、を特徴とする。
【００１９】
また、本発明は、送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、（１）前記受信者側装置が、
素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【００２０】
【数６６】
2008058944.tif 000003
【００２１】
なる双線形写像ｅを作成するステップと、
s1,s2∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶステップと、
【００２２】
【数６７】
2008058944.tif 000004
【００２３】
を算出するステップと、
SKA=（s1Ｑ,s2Ｑ）を復号化鍵とし、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２）を暗号化鍵として、記憶部に記憶するステップ（但し、m,nは自然数、Ｈ１,Ｈ２は、
【００２４】
【数６８】
2008058944.tif 000005
【００２５】
なるハッシュ関数を意味する。）と、
前期暗号化鍵ＰＫＡを出力するステップと、
を行い、
（２）前期送信者側装置が、
メッセージ文Ｍ∈｛０，１｝nに対して、ｒ∈Ｚqをランダムに選ぶステップと、
前記受信者側装置が出力した前記暗号化鍵ＰＫＡを用いて、
【００２６】
【数６９】
2008058944.tif 000006
【００２７】
を計算するステップと、
計算したＣ＝（Ｕ,Ｖ,Ｗ）を前記メッセージ文Ｍの暗号文として前記受信者側装置に送信するステップと、
を行い、
（３）前記受信者側装置が、
前記送信者側装置より受信した前記暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）に対して、前記記憶部に記憶した前記復号化鍵SKAを用いて、
【００２８】
【数７０】
2008058944.tif 000007
【００２９】
により、Ｍ∈｛０，１｝nを計算するステップと、
【００３０】
【数７１】
2008058944.tif 000008
【００３１】
の検査式が成立するか否かを検査するステップと、
前記検査式が成立する場合には、計算結果Ｍをメッセージ文として出力し、前記検査式が成立しない場合には、前記暗号文Ｃを不正な暗号文とみなして棄却するステップと、
を行うこと、を特徴とする。
【００３２】
また、本発明は、
送信者側装置がメッセージ文の暗号文を作成して送信し、受信者側装置が前記暗号文を受信して前記暗号文を復号する暗号通信方法であって、
前記受信者側装置又は鍵管理センタ側装置が、
公開鍵と秘密鍵のペアを複数生成する鍵生成ステップと、
前記鍵生成ステップで生成した複数の公開鍵を含む公開鍵情報を生成するステップと、
前記鍵生成ステップで生成した複数の秘密鍵を含む秘密鍵情報を生成するステップと、
前記送信者側装置が、
前記公開鍵情報を取得するステップと、
前記公開鍵情報に含まれる複数の公開鍵の全てを用いてメッセージを暗号化した暗号文を生成するステップと、
前記受信者側装置が、
前記暗号文を取得するステップと、
前記暗号文を前記秘密鍵情報で復号するステップと、
を備えることを特徴とする。
【発明の効果】
【００３３】
本発明の暗号システムによれば、十分な計算量的困難性を期待されるＢＤＨ（bilinear Diffie-Hellman）問題を暗号学的仮定として、タイトなセキュリティ・リダクションをもつ、安全性の高い公開鍵暗号方式およびＩＤベース暗号方式を提供することができる。これにより、利便性に優れ、かつ、安全な暗号通信方法と、その応用装置、システムを実現することができる。
【００３４】
また、さらに、既存の暗号システムを利用しながら、新しい暗号方法を提供することが可能であるため、システム入れ替えのためのコストを削減することができ、かつ、安全な暗号通信方法と、その応用装置、システムを実現することができる。
【発明を実施するための最良の形態】
【００３５】
図１は、本発明の第一及び第二の実施形態に共通する通信システム１００の概略図である。
【００３６】
図示するように、通信システム１００は、受信者側装置１１０と、送信者側装置１２０と、を備えており、これらは通信回線１４０に接続されている。
【００３７】
図２は、受信者側装置１１０の概略図である。
【００３８】
図示するように、受信者側装置１１０は、情報を入力する入力部１１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置１１０の各部の制御を行う演算部１１２と、記憶部１１５と、通信回線１４０を介して送信者側装置１２０と通信を行う通信部１１６と、情報を出力する出力部１１７と、を備えている。
【００３９】
また、演算部１１２は、暗号化鍵及び復号化鍵を生成する鍵情報生成部１１３と、暗復号化処理を行う暗復号化部１１４と、を有する。
【００４０】
図３は、送信者側装置１２０の概略図である。
【００４１】
図示するように、送信者側装置１２０は、情報を入力する入力部１２１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置１２０の各部の制御を行う演算部１２２と、記憶部１２５と、通信回線１４０を介して受信者側装置１１０と通信を行う通信部１２６と、情報を出力する出力部１２７と、を備えている。
【００４２】
また、演算部１２２は、乱数を生成する乱数生成部１２３と、暗復号化処理を行う暗復号化部１２４と、を有する。
【００４３】
上記構成の受信者側装置１１０及び送信者側装置１２０は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータ４００において、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部１１５、１２５に利用され、通信装置４０８が通信部１１６、１２６に利用され、入力装置４０６や読取装置４０５が入力部１１１、１２１に利用され、そして、出力装置４０７が出力部１１７、１２７に利用される。
【００４４】
この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
（第一の実施形態）
本発明の第一の実施形態について説明する。
【００４５】
本実施形態では、受信者側装置１１０を用いるユーザＡと送信者側装置１２０を用いるユーザＢが、ユーザＡが受信者側装置１１０において作成した公開鍵情報を用いて、通信回線１４０を介して暗号通信を行う方法について述べる。
【００４６】
なお、図５は、本発明の第一の実施形態における動作手順を説明するための図である。
１．受信者側装置１１０での処理
受信者側装置１１０において、演算部１１２は、入力部１１１を介してユーザＡから鍵生成の指示を受け付けると、鍵情報生成部１１３を用いて、素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【００４７】
【数７２】
2008058944.tif 000009
【００４８】
なる双線形写像ｅを作成する（Ｓ６１０）。
【００４９】
次に、演算部１１２は、鍵情報生成部１１３を用いて、ｓ１、ｓ２∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶ（Ｓ６１１）。
【００５０】
そして、演算部１１２の鍵情報生成部１１３は、ランダムに選んだｓ１、ｓ２及びＰを用いて、
【００５１】
【数７３】
2008058944.tif 000010
【００５２】
を生成する（Ｓ６１２）。
【００５３】
そして、演算部１１２は、SKA=（s1Ｑ,s2Ｑ）を復号化（秘密）鍵として、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２）を暗号化（公開）鍵として、両者を記憶部１１５に記憶する（Ｓ６１３）。但し、m,nは自然数、Ｈ１,Ｈ２は、
【００５４】
【数７４】
2008058944.tif 000011
【００５５】
なるハッシュ関数を意味する。
【００５６】
次に、演算部１１２は、Ｓ６１３で生成した暗号化（公開）鍵ＰＫＡ=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２）を、出力部１１７から出力するか、あるいは、通信部１１６から通信回線１４０を介して送信者側装置１２０に送信する（Ｓ６１４）。なお、出力部１１７から暗号化（公開）鍵ＰＫＡが出力された場合には、ユーザＡは、郵送等によりユーザＢに暗号化（公開）鍵ＰＫＡを通知する。
２．送信者側装置１２０での処理
送信者側装置１２０の演算部１２２は、通信部１２６が通信回線１４０を介して受信者側装置１１０より受信した、あるいは、ユーザＢが入力部１２１を介して入力した暗号化（公開）鍵ＰＫＡを記憶部１２５に記憶する（Ｓ６１５）。
【００５７】
次に、ユーザＢは、入力部１２１を介してメッセージ文Ｍ∈{0,1}ｎ（ｎは正整数）を入力する（Ｓ６１６）。
【００５８】
メッセージ文Ｍが入力されると、演算部１２２は、入力されたメッセージ文Ｍを記憶部１２５に記憶する（Ｓ６１７）。
【００５９】
そして、演算部１２２は、乱数生成部１２３を用いて、メッセージＭに対して、r∈Ｚ*ｑをランダムに選ぶ（Ｓ６１８）。
【００６０】
次に、演算部１２２は、Ｓ６１６で選択されたｒと、記憶部１２５に記憶されている暗号化（公開）鍵ＰＫＡ及びメッセージＭと、暗復号化部１２４を用いて、
【００６１】
【数７５】
2008058944.tif 000012
【００６２】
を計算する（Ｓ６１９）。
【００６３】
そして、演算部１２２は、Ｓ６１９で生成した暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）を、出力部１２７から出力するか、あるいは、通信部１２６から通信回線１４０を介して受信者側装置１１０に送信する（Ｓ６２０）。なお、出力部１２７から暗号文Ｃが出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
３．受信者側装置１１０での処理
受信者側装置１１０の演算部１１２は、通信部１１６が通信回線１４０を介して送信者側装置１２０より受信した、あるいは、ユーザＡが入力部１１１を介して入力した暗号文Ｃを記憶部１１５に記憶する（Ｓ６２１）。
【００６４】
次に、演算部１１２は、暗復号化部１１４を用いて、記憶部１１５に記憶されている暗号文Ｃに対して、記憶部１１５に記憶されているユーザＡの復号（秘密）鍵ＳＫＡから、
【００６５】
【数７６】
2008058944.tif 000013
【００６６】
により、Ｍ∈｛０，１｝ｎを計算する（Ｓ６２２）。
【００６７】
さらに、演算部１１２は、Ｓ２２での計算結果であるＭと、暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）と、から、
【００６８】
【数７７】
2008058944.tif 000014
【００６９】
の検査式が成立するか否かを検査する（Ｓ６２３）。この検査式が成立する場合には、Ｓ２０での計算結果Ｍをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）を不正な暗号文とみなして棄却する。
【００７０】
実施例１に記載の公開鍵暗号通信方法は、非特許文献１および非特許文献４に記載の手法と同様の手法により、Bilinear Diffie-Hellman（BDH）問題の計算量的困難性を暗号学的仮定として、IND-CCA2の意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-CCA2の意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【００７１】
本実施例における暗号通信方法において、暗号文の一部であるＷへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。
【００７２】
また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
（第二の実施形態）
次に、本発明の第二の実施形態について説明する。本実施形態は、第一の実施形態の変形例である。
【００７３】
図６は、本発明の第二の実施形態における動作手順を説明するための図である。
１．受信者側装置１１０での処理
受信者側装置１１０において、演算部１１２は、入力部１１１を介してユーザＡから鍵生成の指示を受け付けると、鍵情報生成部１１３を用いて、素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【００７４】
【数７８】
2008058944.tif 000015
【００７５】
なる双線形写像ｅを作成する（Ｓ６３０）。
【００７６】
次に、演算部１１２は、鍵情報生成部１１３を用いて、s1,s2∈Ｚ*qおよびＰ,Ｑ∈Ｇ1をランダムに選ぶ（Ｓ６３１）。
【００７７】
そして、演算部１１２の鍵情報生成部１１３は、ランダムに選んだｓ１、ｓ２及びＰを用いて、
【００７８】
【数７９】
2008058944.tif 000016
【００７９】
を生成する（Ｓ６３２）。
【００８０】
そして、演算部１１２は、SKA=（s1Ｑ,s2Ｑ）を復号化（秘密）鍵として、PKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３）を暗号化（公開）鍵として、両者を記憶部１１５に記憶する（Ｓ６３３）。但し、m,nは自然数、Ｈ１,Ｈ２,Ｈ３は、
【００８１】
【数８０】
2008058944.tif 000017
【００８２】
なるハッシュ関数を意味する。
【００８３】
次に、演算部１１２は、Ｓ６３３で生成した暗号化（公開）鍵をPKA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３）を、出力部１１７から出力するか、あるいは、通信部１１６から通信回線１４０を介して送信者側装置１２０に送信する（Ｓ６３４）。なお、出力部１１７から暗号化（公開）鍵ＰＫＡが出力された場合には、ユーザＡは、郵送等によりユーザＢに暗号化（公開）鍵ＰＫＡを通知する。
２．送信者側装置１２０での処理
送信者側装置１２０の演算部１２２は、通信部１２６が通信回線１４０を介して受信者側装置１１０より受信した、あるいは、ユーザＢが入力部１２１を介して入力した暗号化（公開）鍵ＰＫＡを記憶部１２５に記憶する（Ｓ６３５）
次に、ユーザＢは、入力部１２１を介してメッセージ文Ｍ∈{0,1}ｎ（ｎは正整数）を入力する（Ｓ６３６）。
【００８４】
メッセージ文Ｍが入力されると、演算部１２２は、入力されたメッセージ文Ｍを記憶部１２５に記憶する（Ｓ６３７）。
【００８５】
そして、演算部１２２は、乱数生成部１２３を用いて、メッセージＭに対して、σ∈{0,1}mをランダムに選ぶ（Ｓ６３８）。
【００８６】
次に、演算部１２２は、Ｓ６３８で選択されたσを用いて、
【００８７】
【数８１】
2008058944.tif 000018
【００８８】
を計算する（Ｓ６３９）。
【００８９】
そして、演算部１２２は、Ｓ６３９で計算されたｒと、記憶部１２５に記憶されている暗号化（公開）鍵ＰＫＡ及びメッセージＭと、暗復号化部１２４を用いて、
【００９０】
【数８２】
2008058944.tif 000019
【００９１】
を計算する（Ｓ６４０）。
【００９２】
そして、演算部１２２は、Ｓ６４０で生成した暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）を、出力部１２７から出力するか、あるいは、通信部１２６から通信回線１４０を介して受信者側装置１１０に送信する（Ｓ６４１）。なお、出力部１２７から暗号文Ｃが出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
３．受信者側装置１１０での処理
受信者側装置１１０の演算部１１２は、通信部１１６が通信回線１４０を介して送信者側装置１２０より受信した、あるいは、ユーザＡが入力部１１１を介して入力した暗号文Ｃを記憶部１１５に記憶する（Ｓ６４２）。
【００９３】
次に、演算部１１２は、暗復号化部１１４を用いて、記憶部１１５に記憶されている暗号文Ｃに対して、記憶部１１５に記憶されているユーザＡの復号（秘密）鍵ＳＫＡから、
【００９４】
【数８３】
2008058944.tif 000020
【００９５】
により、σ∈｛０，１｝ｍを計算する（Ｓ６４３）。
【００９６】
さらに、演算部１１２は、Ｓ４３での計算結果であるσと、暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）と、から、
【００９７】
【数８４】
2008058944.tif 000021
【００９８】
により、Ｍ∈｛０，１｝ｎを計算する（Ｓ６４４）。
【００９９】
さらに、演算部１１２は、Ｓ６４４での計算結果であるＭと、Ｓ６４３での計算結果であるσと、から、
【０１００】
【数８５】
2008058944.tif 000022
【０１０１】
により、r∈Ｚqを計算する（Ｓ６４５）。
【０１０２】
そして、演算部１１２は、Ｓ６４５での計算結果ｒと、暗号文Ｃ＝（Ｕ，Ｖ，Ｗ）と、から、
【０１０３】
【数８６】
2008058944.tif 000023
【０１０４】
の検査式が成立するか否かを検査する（Ｓ６４６）。この検査式が成立する場合には、Ｓ６４４での計算結果Ｍをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文Ｃ＝（Ｕ,Ｖ,Ｗ）を不正な暗号文とみなして棄却する。
【０１０５】
第二の実施形態に記載の公開鍵暗号通信方法は、第一の実施形態の場合と同様、Bilinear Diffie-Hellman（BDH）問題の計算量的困難性を暗号学的仮定として、IND-ID-CCAの意味での安全性を証明することが可能である。また、タイトなセキュリティ・リダクションをもつことも第一の実施形態の場合と同様に示される。
【０１０６】
図７は、本発明の第三及び第四の実施形態に共通する通信システム２００の概略図である。
【０１０７】
図示するように、通信システム２００は、受信者側装置２１０Ａと、送信者側装置２１０Ｂと、鍵管理センタ側装置２３０と、を備えており、これらは通信回線１４０に接続されている。
【０１０８】
図８は、受信者側装置２１０Ａ及び送信者側装置２１０Ｂの概略図である。本実施形態における受信者側装置２１０Ａ及び送信者側装置２１０Ｂは、同様の構成を有している。
【０１０９】
図示するように、受信者側装置２１０Ａ及び送信者側装置２１０Ｂは、情報を入力する入力部２１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置２１０Ａ又は送信者側装置２１０Ｂの各部の制御を行う演算部２１２と、記憶部２１５と、通信回線１４０を介して通信を行う通信部２１６と、情報を出力する出力部２１７と、を備えている。
【０１１０】
また、演算部２１２は、乱数を生成する乱数生成部２１３と、暗復号化処理を行う暗復号化部２１４と、を有する。
【０１１１】
図９は、鍵管理センタ側装置２３０の概略図である。
【０１１２】
図示するように、鍵管理センタ側装置２３０は、情報を入力する入力部２３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、鍵管理センタ側装置２３０の各部の制御を行う演算部２３２と、記憶部２３４と、通信回線１４０を介して受信者側装置２１０Ａ及び送信者側装置２１０Ｂと通信を行う通信部２３５と、情報を出力する出力部２３６と、を備えている。
【０１１３】
また、演算部２３２は、システムパラメータ、マスタ鍵及びプライベート鍵を生成する鍵情報生成部２３３を有する。
【０１１４】
上記構成の受信者側装置２１０Ａ、送信者側装置２１０Ｂ及び鍵管理センタ側装置２３０についても、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータ４００において、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部２１５、２３４に利用され、通信装置４０８が通信部２１６、２３５に利用され、入力装置４０６や読取装置４０５が入力部２１１、２３１に利用され、そして、出力装置４０７が出力部２１７、２３６に利用される。
【０１１５】
この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
（第三の実施形態）
本発明の第三の実施形態について説明する。
【０１１６】
本実施形態では、受信者側装置２１０Ａを用いるユーザＡと、送信者側装置２１０Ｂを用いるユーザＢと、が、鍵管理センタ側装置２３０が作成した鍵情報を用いて、通信回線１４０を介して暗号通信を行う方法について述べる。
【０１１７】
なお、図１０は、本発明における第三の実施形態における動作手順を説明するための図である。
１．鍵管理センタ側装置２３０での処理
鍵管理センタ側装置２３０において、演算部２３２は、入力部２３１を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部２３３を用いて、素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【０１１８】
【数８７】
2008058944.tif 000024
【０１１９】
なる双線形写像ｅを生成する（Ｓ６５０）。
【０１２０】
次に、演算部２３２は、鍵情報生成部２３３を用いて、s0,s1∈Ｚ*qおよびＰ∈Ｇ1をランダムに選ぶ（Ｓ６５１）。
【０１２１】
そして、演算処理部２３２の鍵情報生成部２３３は、ランダムに選んだｓ０、ｓ１及びＰを用いて、
【０１２２】
【数８８】
2008058944.tif 000025
【０１２３】
を生成する（Ｓ６５２）。
【０１２４】
そして、演算部２３２は、s＝（s0,s1）をマスタ鍵として、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,Ｈ１,Ｈ２,Ｈ３,Ｈ4,Ｅ,Ｄ）をシステムパラメータとして、両者を記憶部２３４に記憶する（Ｓ６５３）。但し、ｌ,ｍ,ｎは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２,Ｈ３,Ｈ4は、
【０１２５】
【数８９】
2008058944.tif 000026
【０１２６】
なるハッシュ関数を意味する。
【０１２７】
次に、演算部２３２は、Ｓ６５３で生成したシステムパラメータＰＫを、出力部２３６から出力するか、あるいは、通信部２３５から通信回線１４０を介して送信者側端末２１０Ｂに送信する（Ｓ６５４）。なお、出力部２３６からシステムパラメータＰＫが出力された場合には、鍵管理センタは郵送等によりユーザＢにシステムパラメータＰＫを通知する。
２．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａにおいて、演算部２１２は、入力部２１１を介してユーザＡより受け付けたユーザＡの個別情報ＩＤAを記憶部２１５に記憶するとともに、通信回線１４０を介して通信部２１６から鍵管理センタ側装置２３０に送信する（Ｓ６５５）。なお、ユーザＡの個別情報ＩＤAについては、ユーザＡが郵送等によって鍵管理センタに受信者側装置２１０Ａのアドレスとともに通知してもよい。
３．鍵管理センタ側装置２３０での処理
鍵管理センタ側装置２３０において、演算部２３２は、通信部２３５が通信回線１４０を介して受信者側装置２１０Ａより受信した、あるいは、入力部２３１を介して受信者側装置２１０Ａのアドレスとともに入力されたユーザＡの個別情報ＩＤＡを、受信者側装置２１０Ａのアドレスに対応付けて記憶部２３４に記憶する（Ｓ６５６）。
【０１２８】
そして、演算部２３２は、鍵情報生成部２３３を用いて、ｂIDA∈{0,1}をランダムに選ぶ（Ｓ６５７）。
【０１２９】
次に、演算部２３２は、鍵情報生成部２３３を用いて、記憶部２３４に記憶されているマスタ鍵ｓ及びユーザＡの個別情報ＩＤＡから、
【０１３０】
【数９０】
2008058944.tif 000027
【０１３１】
を計算する（Ｓ６５８）。
【０１３２】
そして、演算部２３２は、ＳＫＡ＝（ｂIDA,dIDA,0,dIDA,1）をユーザＡのプライベート鍵として、出力部２３６から出力するか、あるいは、通信回線１４０を介して通信部２３５から受信者側装置２１０Ａに安全な方法（例えば、鍵管理センタ側装置２３０が受信者側装置２１０Ａと共有する暗号鍵を用いた暗号通信）で送信する（Ｓ６５９）。なお、出力部２３６からプライベート鍵ＳＫＡが出力された場合には、鍵管理センタはＩＣカードの郵送等の安全な方法により、ユーザＡにプライベート鍵ＳＫＡを通知する。
４．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して鍵管理センタ側装置２３０より受信した、あるいは、入力部２１１を介して入力されたプライベート鍵ＳＫＡを、記憶部２１５に記憶する（Ｓ６６０）。
【０１３３】
また、演算部２１２は、ユーザＡから入力部２１１を介してユーザＡの個別情報ＩＤＡの送信指示を受けると、通信回線１４０を介して通信部２１６からユーザＡの個別情報ＩＤＡを送信する（Ｓ６６１）。
５．送信者側装置２１０Ｂでの処理
送信側装置２１０Ｂにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して鍵管理センタ側装置２３０より受信した、あるいは、入力部２１１を介して入力されたシステムパラメータＰＫを、記憶部２１５に記憶する（Ｓ６６２）。
【０１３４】
また、送信側装置２１０Ｂにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して受信側装置２１０Ａより受信した、あるいは、入力部２１１を介して入力されたユーザＡの個別情報ＩＤＡを、記憶部２１５に記憶する（Ｓ６６３）。
【０１３５】
次に、ユーザＢは、入力部２１１を介してメッセージ文Ｍ∈{0,1}ｎ（ｎは正整数）を入力する（Ｓ６６４）。
【０１３６】
メッセージ文Ｍが入力されると、演算部２１２は、入力されたメッセージＭを記憶部２１５に記憶する（Ｓ６６５）。
【０１３７】
そして、演算部２１２は、乱数生成部２１３を用いて、Ｒ∈｛０，１｝lをランダムに選ぶ（Ｓ６６６）。
【０１３８】
次に、演算部２１２は、Ｓ６６６で選択されたＲと、記憶部２１５に記憶されているメッセージ文Ｍ、システムパラメータＰＫ、ユーザＡの個別情報ＩＤＡ及びユーザＢの個別情報ＩＤＢと、を用いて、
【０１３９】
【数９１】
2008058944.tif 000028
【０１４０】
なるｒ∈ＺqおよびＫ∈｛０，１｝mを計算する（Ｓ６６７）。
【０１４１】
さらに、演算部２１２は、Ｓ６６７で計算されたｒ及びＫを用いて、
【０１４２】
【数９２】
2008058944.tif 000029
【０１４３】
を計算する（Ｓ６６８）。
【０１４４】
そして、演算部２１２は、Ｓ６６８で作成した暗号文Ｃ＝（Ｕ,Ｖ0,Ｖ1,Ｗ,Ｚ）を出力部２１７から出力するか、あるいは、通信回線１４０を介して通信部２１６から受信者側装置２１０Ａに送信する（Ｓ６６９）。なお、出力部２１７から暗号文が出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
６．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａの演算部２１２は、通信部２１６が通信回線１４０を介して送信者側装置２１０Ｂより受信した、あるいは、ユーザＡが入力部２１１を介して入力した暗号文Ｃを記憶部２１５に記憶する（Ｓ６７０）。
【０１４５】
次に、演算部２１２は、暗復号化部２１４を用いて、記憶部２１５に記憶されている暗号文Ｃに対して、記憶部２１５に記憶されているユーザＡの個別情報ＩＤＡ及びプライベート鍵ＳＫＡから、
【０１４６】
【数９３】
2008058944.tif 000030
【０１４７】
なるＲ∈｛０，１｝lを計算する（Ｓ６７１）。
【０１４８】
さらに、演算部２１２は、Ｓ７１で計算されたＲと、記憶部２１５に記憶されているユーザＡの個別情報ＩＤＡ及びユーザＢの個別情報ＩＤＢと、を用いて、
【０１４９】
【数９４】
2008058944.tif 000031
【０１５０】
により、ｒ∈ＺqおよびＫ∈｛０，１｝mを計算する（Ｓ６７２）。
【０１５１】
次に、演算部２１２は、Ｓ６７２で計算されたＫを用いて、
【０１５２】
【数９５】
2008058944.tif 000032
【０１５３】
により、Ｍ∈｛０，１｝nを計算する（Ｓ６７３）。
【０１５４】
そして、演算部２１２は、Ｓ６７１で計算されたＲと、Ｓ６７２で計算されたｒと、Ｓ６７３で計算されたＭと、暗号文Ｃと、から、
【０１５５】
【数９６】
2008058944.tif 000033
【０１５６】
の検査式が成立するか否かを検査する（Ｓ６７４）。この検査式が成立する場合には、Ｓ６７３での計算結果Ｍをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文Ｃ＝（Ｕ,Ｖ0,Ｖ1,Ｗ,Ｚ）を不正な暗号文とみなして棄却する。
【０１５７】
第三の実施形態に記載のＩＤベース暗号通信方法は、非特許文献４に記載の手法と同様の手法により、List Bilinear Diffie-Hellman（LBDH）問題の計算量的困難性を暗号学的仮定として、IND-ID-CCAの意味での安全性を証明することが可能である。
【０１５８】
このとき、本実施形態の公開鍵暗号方式をアドバンテージεでIND-ID-CCAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでLBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施形態のＩＤベース暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【０１５９】
また、本実施例の方式は、非特許文献４に記載の方式よりも、暗号化処理において、計算量の多い双線形写像の計算がひとつ少ないため、より高速な暗号化処理を実現できる。本実施形態における暗号通信方法において、暗号文の一部であるＷへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。
【０１６０】
本実施形態の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
（第四の実施形態）
本発明の第四の実施形態について説明する。
【０１６１】
本実施形態は、第三の実施形態に比べて、鍵長は長くなるが、暗号化及び復号化処理の高速性に優れる方式である。
【０１６２】
なお、図１１は、本発明における第四の実施形態における動作手順を説明するための図である。
１．鍵管理センタ側装置２３０での処理
鍵管理センタ側装置２３０において、演算部２３２は、入力部２３１を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部２３３を用いて、素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【０１６３】
【数９７】
2008058944.tif 000034
【０１６４】
なる双線形写像ｅを生成する（Ｓ６８０）。
【０１６５】
次に、演算部２３２は、鍵情報生成部２３３を用いて、s10,s11,s20,s21∈Ｚ*qおよびＰ∈Ｇ1をランダムに選ぶ（Ｓ６８１）。
【０１６６】
そして、演算処理部２３２の鍵情報生成部２３３は、ランダムに選んだｓ１０、ｓ１１、ｓ２０、ｓ２１及びＰを用いて、
【０１６７】
【数９８】
2008058944.tif 000035
【０１６８】
を生成する（Ｓ６８２）。
【０１６９】
そして、演算部２３２は、s＝（s10,s11,s20,s21）をマスタ鍵として、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,10,Ｐpub,11,Ｐpub,1,Ｐpub,20,Ｐpub,21,Ｐpub,2,Ｈ１,Ｈ２,Ｈ３,Ｈ4,Ｅ,Ｄ）をシステムパラメータとして、両者を記憶部２３４に記憶する（Ｓ６８３）。但し、l,m,nは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２,Ｈ３,Ｈ4は、
【０１７０】
【数９９】
2008058944.tif 000036
【０１７１】
なるハッシュ関数を意味する。
【０１７２】
次に、演算部２３２は、Ｓ８３で生成したシステムパラメータＰＫを、出力部２３６から出力するか、あるいは、通信部２３５から通信回線１４０を介して送信者側端末２１０Ｂに送信する（Ｓ６８４）。なお、出力部２３６からシステムパラメータＰＫが出力された場合には、鍵管理センタは郵送等によりユーザＢにシステムパラメータＰＫを通知する。
２．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａにおいて、演算部２１２は、入力部２１１を介してユーザＡより受け付けたユーザＡの個別情報ＩＤAを記憶部２１５に記憶するとともに、通信回線１４０を介して通信部２１６から鍵管理センタ側装置２３０に送信する（Ｓ６８５）。なお、ユーザＡの個別情報ＩＤAについては、ユーザＡが郵送等によって鍵管理センタに受信者側装置２１０Ａのアドレスとともに通知してもよい。
３．鍵管理センタ側装置２３０での処理
鍵管理センタ側装置２３０において、演算部２３２は、通信部２３５が通信回線１４０を介して受信者側装置２１０Ａより受信した、あるいは、入力部２３１を介して受信者側装置２１０Ａのアドレスとともに入力されたユーザＡの個別情報ＩＤＡを、受信者側装置２１０Ａのアドレスに対応付けて記憶部２３４に記憶する（Ｓ６８６）。
【０１７３】
そして、演算部２３２は、鍵情報生成部２３３を用いて、ｂIDA∈{0,1}をランダムに選ぶ（Ｓ６８７）。
【０１７４】
次に、演算部２３２は、鍵情報生成部２３３を用いて、記憶部２３４に記憶されているマスタ鍵ｓ及びユーザＡの個別情報ＩＤＡから、
【０１７５】
【数１００】
2008058944.tif 000037
【０１７６】
を計算する（Ｓ６８８）。但し、εはシステムに固有のストリングで予め定められているものとする。
【０１７７】
さらに、演算部２３２は、ＳＫＡ＝（ｂIDA,d（1,IDA）,d（2,IDA））をユーザＡのプライベート鍵として、出力部２３６から出力するか、あるいは、通信回線１４０を介して通信部２３５から受信者側装置２１０Ａに安全な方法（例えば、鍵管理センタ側装置２３０が受信者側装置２１０Ａと共有する暗号鍵を用いた暗号通信）で送信する（Ｓ６８９）。なお、出力部２３６からプライベート鍵ＳＫＡが出力された場合には、鍵管理センタはＩＣカードを梱包した郵送等の安全な方法により、ユーザＡにプライベート鍵ＳＫＡを通知する。
４．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して鍵管理センタ側装置２３０より受信した、あるいは、入力部２１１を介して入力されたプライベート鍵ＳＫＡを、記憶部２１５に記憶する（Ｓ６９０）。
【０１７８】
また、演算部２１２は、ユーザＡから入力部２１１を介してユーザＡの個別情報ＩＤＡの送信指示を受けると、通信回線１４０を介して通信部２１６からユーザＡの個別情報ＩＤＡを送信する（Ｓ６９１）。
５．送信者側装置２１０Ｂでの処理
送信側装置２１０Ｂにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して鍵管理センタ側装置２３０より受信した、あるいは、入力部２１１を介して入力されたシステムパラメータＰＫを、記憶部２１５に記憶する（Ｓ６９２）。
【０１７９】
また、送信側装置２１０Ｂにおいて、演算部２１２は、通信部２１６が通信回線１４０を介して受信側装置２１０Ａより受信した、あるいは、入力部２１１を介して入力されたユーザＡの個別情報ＩＤＡを、記憶部２１５に記憶する（Ｓ６９３）。
【０１８０】
次に、ユーザＢは、入力部２１１を介してメッセージ文Ｍ∈{0,1}ｎ（ｎは正整数）を入力する（Ｓ６９４）。
【０１８１】
メッセージ文Ｍが入力されると、演算部２１２は、入力されたメッセージＭを記憶部２１５に記憶する（Ｓ６９５）。
【０１８２】
そして、演算部２１２は、乱数生成部２１３を用いて、Ｒ∈｛０，１｝lをランダムに選ぶ（Ｓ６９６）。
【０１８３】
次に、演算部２１２は、Ｓ６９６で選択されたＲと、記憶部２１５に記憶されているメッセージ文Ｍ、システムパラメータＰＫ、ユーザＡの個別情報ＩＤＡ及びユーザＢの個別情報ＩＤＢと、を用いて、
【０１８４】
【数１０１】
2008058944.tif 000038
【０１８５】
なるｒ0,r1∈ＺqおよびＫ∈｛０，１｝mを計算する（Ｓ６９７）。
【０１８６】
さらに、演算部２１２は、Ｓ６９７で計算されたｒ０、ｒ１及びＫを用いて、
【０１８７】
【数１０２】
2008058944.tif 000039
【０１８８】
を計算する（Ｓ６９８）。
【０１８９】
そして、演算部２１２は、Ｓ９８で作成した暗号文Ｃ＝（Ｕ10,Ｕ11,Ｕ20,Ｕ21,Ｖ0,Ｖ1,Ｗ,Ｚ）を出力部２１７から出力するか、あるいは、通信回線１４０を介して通信部２１６から受信者側装置２１０Ａに送信する（Ｓ６９９）。なお、出力部２１７から暗号文が出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
６．受信者側装置２１０Ａでの処理
受信者側装置２１０Ａの演算部２１２は、通信部２１６が通信回線１４０を介して送信者側装置２１０Ｂより受信した、あるいは、ユーザＡが入力部２１１を介して入力した暗号文Ｃを記憶部２１５に記憶する（Ｓ７００）。
【０１９０】
次に、演算部２１２は、暗復号化部２１４を用いて、記憶部２１５に記憶されている暗号文Ｃに対して、記憶部２１５に記憶されているユーザＡの個別情報ＩＤＡ及びプライベート鍵ＳＫＡから、
【０１９１】
【数１０３】
2008058944.tif 000040
【０１９２】
なるＲ∈｛０，１｝lを計算する（Ｓ７０１）。
【０１９３】
さらに、演算部２１２は、Ｓ７０１で計算されたＲと、記憶部２１５に記憶されているユーザＡの個別情報ＩＤＡ及びユーザＢの個別情報ＩＤＢと、を用いて、
【０１９４】
【数１０４】
2008058944.tif 000041
【０１９５】
により、ｒ0,r1∈ＺqおよびＫ∈｛０，１｝mを計算する（Ｓ７０２）。
【０１９６】
次に、演算部２１２は、
【０１９７】
【数１０５】
2008058944.tif 000042
【０１９８】
なるＲ’∈｛０，１｝lを計算する（Ｓ７０３）。
【０１９９】
そして、演算部２１２は、Ｓ７０１で計算されたＲと、Ｓ７０２で計算されたｒと、Ｓ７０３で計算されたＲ’と、暗号文Ｃと、から、
【０２００】
【数１０６】
2008058944.tif 000043
【０２０１】
の検査式が成立するか否かを検査する（Ｓ７０４）。
【０２０２】
そして、この検査式が成立する場合には、
【０２０３】
【数１０７】
2008058944.tif 000044
【０２０４】
を計算する（Ｓ７０５）。
【０２０５】
さらに、演算部２１２は、
【０２０６】
【数１０８】
2008058944.tif 000045
【０２０７】
の検査式が成立するか否かを検査する（Ｓ７０６）。この検査式が成立する場合には、Ｓ７３での計算結果Ｍをメッセージ文として出力する。一方、この検査式が成立しない場合には、暗号文Ｃ＝（Ｕ10,Ｕ11,Ｕ20,Ｕ21,Ｖ0,Ｖ1,Ｗ,Ｚ）を不正な暗号文とみなして棄却する。
【０２０８】
本実施形態の暗号方式では、非特許文献１および非特許文献４に記載の手法と同様の手法により、BDH（Bilinear Diffie-Hellman）問題の計算量的困難性を暗号学的仮定にしてIND-ID-CCA安全であることが証明可能である。
【０２０９】
このとき、本実施形態の公開鍵暗号方式をアドバンテージεでIND-ID-CCAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施形態のＩＤベース暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【０２１０】
本実施形態のＩＤベース暗号方式は、計算量の大きい双線形写像を用いた計算が少ないため、効率の良い暗号化および復号化が可能である。
【０２１１】
本実施形態における暗号通信方法において、暗号文の一部であるＷへの入力値を本方式において利用される別のパラメータに変更することにより、上記と同様の手順により暗号文の作成およびメッセージの復号を行うことも可能である。
【０２１２】
また、本実施形態の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
【０２１３】
上記実施形態では、ユーザが各々の装置を利用して暗号通信を行うという一般形で述べたが、具体的には様々なシステムに適用される。例えば、電子ショッピングシステムでは、送信者であるユーザは消費者であり、受信者であるユーザは小売店、ユーザ側装置はパソコンなどの計算機となる。また、電子メールシステムでは、各々の装置はパソコンなどの計算機である。その他にも、従来の公開鍵暗号およびＩＤベース暗号が使われている様々なシステムに適用することが可能である。
【０２１４】
また、以上に記載した実施形態における各計算は、CPUがメモリ内の各プログラムを実行することにより行われるものとして説明したが、プログラムだけではなく、いずれかがハードウエア化された演算装置であって、他の演算装置や、CPUと、データのやりとりを行うものであっても良い。
【０２１５】
図１２は、本発明の第五、第六、第七及び第八の実施形態に共通する通信システム８００の概略図である。
【０２１６】
図示するように、通信システム８００は、受信者側装置８１０と、送信者側装置８２０と、を備えており、これらは通信回線１４０に接続されている。
【０２１７】
図１３は、受信者側装置８１０の概略図である。
【０２１８】
図示するように、受信者側装置８１０は、情報を入力する入力部８１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置８１０の各部の制御を行う演算部８１２と、記憶部８１５と、通信回線１４０を介して送信者側装置８２０と通信を行う通信部８１６と、情報を出力する出力部８１７と、を備えている。
【０２１９】
また、演算部８１２は、暗号化鍵及び復号化鍵を生成する鍵情報生成部８１３と、暗復号化処理を行う暗復号化部８１４と、を有する。
【０２２０】
図１４は、送信者側装置８２０の概略図である。
【０２２１】
図示するように、送信者側装置８２０は、情報を入力する入力部８２１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算を含む各種演算、および、送信者側装置８２０の各部の制御を行う演算部８２２と、記憶部８２５と、通信回線１４０を介して受信者側装置８１０と通信を行う通信部８２６と、情報を出力する出力部８２７と、を備えている。
【０２２２】
また、演算部８２２は、乱数を生成する乱数生成部８２３と、暗復号化処理を行う暗復号化部８２４と、を有する。
【０２２３】
上記構成の受信者側装置８１０及び送信者側装置８２０は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータ４００において、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部８１５、８２５に利用され、通信装置４０８が通信部８１６、８２６に利用され、入力装置４０６や読取装置４０５が入力部８１１、８２１に利用され、そして、出力装置４０７が出力部８１７、８２７に利用される。
【０２２４】
この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
（第五の実施形態）
図１５は、本発明の第五の実施形態における動作手順を説明するための図である。
【０２２５】
本実施形態は、通信回線１４０を介して、受信者側装置８１０と、送信者側装置８２０と、の間で暗号通信を行う暗号システムに関するものであり、公開鍵暗号（以下、暗号方式ＰＫＥ）が利用されている暗号通信システムが既に存在している状況を想定し、既存の暗号システムにおける暗号方法を利用しながら別の暗号システム（より安全性の高い暗号システム）を構築する場合について述べる。
【０２２６】
なお、本実施形態における受信者側装置８１０及び送信者側装置８２０は、ある共通の暗号方式に対応しているものとする。
１．受信者側装置８１０での処理
受信者側装置８１０において、演算部８１２は、入力部８１１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部８１３を用いて、暗号方式ＰＫＥの鍵生成のためのステップを２回実行することにより、２組の鍵のペア（ＰＫ１，ＳＫ１），（ＰＫ２，ＳＫ２）を生成する（Ｓ１０００）。
【０２２７】
次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部８１６又は出力部８１７を介して、
【０２２８】
【数１０９】
2008058944.tif 000046
【０２２９】
を新しい公開鍵として公開し（但し、ｎは負でない整数）（Ｓ１００１）、
【０２３０】
【数１１０】
2008058944.tif 000047
【０２３１】
を受信者側装置８１０のユーザの秘密鍵として記憶部８１５に記憶する（Ｓ１００２）。
２．送信者側装置８２０での処理
送信者側装置８２０の演算部８２２は、通信部８２６又は入力部８２１を介して、受信者側装置８１０が公開している公開鍵ＰＫを取得して、記憶部８２５に記憶する（Ｓ１００３）。
【０２３２】
次に、送信者側装置８２０のユーザは、入力部８２１を介してメッセージ文Ｍ∈{0,1}ｍ、ｍ＝ｎ（ｎは、公開鍵として公開されている負でない整数）を入力する（Ｓ１００４）。
【０２３３】
メッセージ文Ｍが入力されると、演算部８２２は、入力されたメッセージ文Ｍを記憶部８２５に記憶する（Ｓ１００５）。
【０２３４】
次に、演算部８２２は、乱数生成部８２３を用いて、メッセージ文Ｍに対して、暗号方式ＰＫＥのメッセージ空間に含まれるσ１，σ２をランダムに選ぶ（Ｓ１００６）。
【０２３５】
そして、演算部８２２は、暗復号化部８２４を用いて、
【０２３６】
【数１１１】
2008058944.tif 000048
【０２３７】
を計算する（Ｓ１００７）。但し、ＥＰＫ（ｘ）は、メッセージ文ｘを公開鍵ＰＫを用いて該暗号方式ＰＫＥにて暗号化した結果を表す。
【０２３８】
さらに、演算部８２２は、暗復号化部８２４を用いて、
【０２３９】
【数１１２】
2008058944.tif 000049
【０２４０】
を計算する（Ｓ１００８）。
【０２４１】
そして、送信者側装置８２０の演算部８２２は、ステップＳ１００８で生成した暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ）を出力部８２７から出力するか、あるいは、通信部８２６から通信回線１４０を介して、受信者側装置８１０に送信する（Ｓ１００９）。なお、出力部８２７から暗号文Ｃが出力された場合には、送信者側装置８２０のユーザは、郵送等により、受信者側装置８１０のユーザに暗号文Ｃを通知する。
３．受信者側装置８１０での処理
受信者側装置８１０の演算部８１２は、通信部８１６が通信回線１４０を介して送信者側装置８２０より受信した、あるいは、受信者側装置８１０のユーザが入力部８１１を介して入力した暗号文Ｃを記憶部８１５に記憶する（Ｓ１０１０）。なお、演算処理部８１２は、暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【０２４２】
次に、演算部８１２は、暗復号化部８１４を用いて、
【０２４３】
【数１１３】
2008058944.tif 000050
【０２４４】
を計算する（Ｓ１０１１）。但し、ＤＳＫ（ｙ）は、該暗号方式ＰＫＥにおいて、暗号文ｙを秘密鍵ＳＫを用いて復号化した結果を表す。
【０２４５】
そして、演算部８１２は、暗復号化部８１４を用いて、記憶部８１５に記憶されている暗号文Ｃに対して、
【０２４６】
【数１１４】
2008058944.tif 000051
【０２４７】
を計算することで、メッセージＭを復号する（Ｓ１０１２）。
【０２４８】
本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
（第六の実施形態）
次に、本発明の第六の実施形態について説明する。本実施形態は、第五の実施形態の変形例である。なお、本実施形態は、第五の実施形態よりも安全性の高い暗号システムを提供するものである。
【０２４９】
図１６は、本発明の第六の実施形態における動作手順を説明するための図である。
１．受信者側装置８１０での処理
受信者側装置８１０において、演算部８１２は、入力部８１１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部８１３を用いて、暗号方式ＰＫＥの鍵生成のためのステップを２回実行することにより、２組の鍵のペア（ＰＫ１，ＳＫ１），（ＰＫ２，ＳＫ２）を生成する（Ｓ１０２０）。
【０２５０】
次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部８１６又は出力部８１７を介して、
【０２５１】
【数１１５】
2008058944.tif 000052
【０２５２】
を新しい公開鍵として公開し（但し、ｎ１，ｎ２，ｎ３は負でない整数）（Ｓ１０２１）、
【０２５３】
【数１１６】
2008058944.tif 000053
【０２５４】
を受信者側装置８１０のユーザの秘密鍵として記憶部８１５に記憶する（Ｓ１０２２）。
２．送信者側装置８２０での処理
送信者側装置８２０の演算部８２２は、通信部８２６又は入力部８２１を介して、受信者側装置８１０が公開している公開鍵ＰＫを取得して、記憶部８２５に記憶する（Ｓ１０２３）。
【０２５５】
次に、送信者側装置８２０のユーザは、入力部８２１を介してメッセージ文Ｍ∈{0,1}ｍ、ｍ＝ｎ１（ｎ１は、公開鍵として公開されている負でない整数）を入力する（Ｓ１０２４）。
【０２５６】
メッセージ文Ｍが入力されると、演算部８２２は、入力されたメッセージ文Ｍを記憶部８２５に記憶する（Ｓ１０２５）。
【０２５７】
次に、演算部８２２は、乱数生成部８２３を用いて、メッセージ文Ｍに対して、暗号方式ＰＫＥのメッセージ空間に含まれるσ１，σ２をランダムに選び、また、Ｒ１，Ｒ２∈｛０，１｝ｍ、ｍ＝ｎ２（ｎ２は、公開鍵として公開されている負でない整数）をランダムに選ぶ（Ｓ１０２６）。
【０２５８】
そして、演算部８２２は、暗復号化部８２４を用いて、
【０２５９】
【数１１７】
2008058944.tif 000054
【０２６０】
を計算する（Ｓ１０２７）。但し、ＥＰＫ（ｘ；Ｒ）は、乱数Ｒを確率的暗号におけるコイントスとして利用し、メッセージ文ｘを公開鍵ＰＫを用いて該暗号方式ＰＫＥにて暗号化した結果を表す。即ち、暗号文が乱数Ｒによって変わってくるようにする。
【０２６１】
次に、演算部８２２は、乱数生成部８２３を用いて、τ∈{0,1}ｍ、ｍ＝ｎ３（ｎ３は、公開鍵として公開されている負でない整数）をランダムに選び（Ｓ１０２８）、さらに、演算部８２２は、暗復号化部８２４を用いて、
【０２６２】
【数１１８】
2008058944.tif 000055
【０２６３】
を計算する（Ｓ１０２９）。
【０２６４】
そして、送信者側装置８２０の演算部８２２は、ステップＳ１０２９で生成した暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ，Ｗ）を出力部８２７から出力するか、あるいは、通信部８２６から通信回線１４０を介して、受信者側装置８１０に送信する（Ｓ１０３０）。なお、出力部８２７から暗号文Ｃが出力された場合には、送信者側装置８２０のユーザは、郵送等により、受信者側装置８１０のユーザに暗号文Ｃを通知する。
３．受信者側装置８１０での処理
受信者側装置８１０の演算部８１２は、通信部８１６が通信回線１４０を介して送信者側装置８２０より受信した、あるいは、受信者側装置８１０のユーザが入力部８１１を介して入力した暗号文Ｃを記憶部８１５に記憶する（Ｓ１０３１）。なお、演算処理部８１２は、暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ，Ｗ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【０２６５】
次に、演算部８１２は、暗復号化部８１４を用いて、
【０２６６】
【数１１９】
2008058944.tif 000056
【０２６７】
を計算する（Ｓ１０３２）。但し、ＤＳＫ（ｙ）は、該暗号方式ＰＫＥにおいて、暗号文ｙを秘密鍵ＳＫを用いて復号化した結果を表す。
【０２６８】
そして、演算部８１２は、暗復号化部８１４を用いて、記憶部８１５に記憶されている暗号文Ｃに対して、
【０２６９】
【数１２０】
2008058944.tif 000057
【０２７０】
を計算し（Ｓ１０３３）、さらに、Ｍ∈{0,1}ｍ（ｍ＝ｎ１）、Ｒ１，Ｒ２∈｛０，１｝ｍ（ｍ＝ｎ２）、τ∈{0,1}ｍ（ｍ＝ｎ３）を計算し、
【０２７１】
【数１２１】
2008058944.tif 000058
【０２７２】
を検査する（Ｓ１０３４）。
【０２７３】
そして、検査にパスすれば，出力部８１７を介して、メッセージ文Ｍを出力し、検査にパスしなければ暗号文Ｃを不正な暗号文とみなして拒否する。
【０２７４】
本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
【０２７５】
本実施例の方法では、Bilinear Diffie-Hellman（BDH）問題の数学的性質であるランダム自己帰着性を利用するために、二重暗号の技術を用いる。ここで、二重暗号とは、既存の暗号システムによる暗号化および復号化を２度行うことを意味している。これにより、実施例１に記載の公開鍵暗号通信方法は、既存の暗号方式がＬＢＤＨ（List Bilinear Diffie-Hellman）問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるＢＤＨ（Bilinear Diffie-Hellman）問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
（第七の実施形態）
次に、本発明の第七の実施形態について説明する。本実施形態は、第五の実施形態の変形例である。なお、本実施形態は、非特許文献２に記載の変換方法を利用するものである。
【０２７６】
図１７は、本発明の第七の実施形態における動作手順を説明するための図である。
１．受信者側装置８１０での処理
受信者側装置８１０において、演算部８１２は、入力部８１１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部８１３を用いて、暗号方式ＰＫＥの鍵生成のためのステップを２回実行することにより、２組の鍵のペア（ＰＫ１，ＳＫ１），（ＰＫ２，ＳＫ２）を生成する（Ｓ１０４０）。
【０２７７】
次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部８１６又は出力部８１７を介して、
【０２７８】
【数１２２】
2008058944.tif 000059
【０２７９】
を新しい公開鍵として公開し（但し、ｎ１，ｎ２，ｎ３は負でない整数）（Ｓ１０４１）、
【０２８０】
【数１２３】
2008058944.tif 000060
【０２８１】
を受信者側装置８１０のユーザの秘密鍵として記憶部８１５に記憶する（Ｓ１０４２）。
２．送信者側装置８２０での処理
送信者側装置８２０の演算部８２２は、通信部８２６又は入力部８２１を介して、受信者側装置８１０が公開している公開鍵ＰＫを取得して、記憶部８２５に記憶する（Ｓ１０４３）。
【０２８２】
次に、送信者側装置８２０のユーザは、入力部８２１を介してメッセージ文Ｍ∈{0,1}ｍ、ｍ＝ｎ１（ｎ１は、公開鍵として公開されている負でない整数）を入力する（Ｓ１０４４）。
【０２８３】
メッセージ文Ｍが入力されると、演算部８２２は、入力されたメッセージ文Ｍを記憶部８２５に記憶する（Ｓ１０４５）。
【０２８４】
次に、演算部８２２は、乱数生成部８２３を用いて、メッセージ文Ｍに対して、暗号方式ＰＫＥのメッセージ空間に含まれるσ１，σ２をランダムに選び、また、ｒ１，ｒ２∈｛０，１｝ｍ、ｍ＝ｎ２（ｎ２は、公開鍵として公開されている負でない整数）をランダムに選ぶ（Ｓ１０４６）。
【０２８５】
そして、演算部８２２は、暗復号化部８２４を用いて、
【０２８６】
【数１２４】
2008058944.tif 000061
【０２８７】
を計算する（Ｓ１０４７）。
【０２８８】
さらに、演算部８２２は、暗復号化部８２４を用いて、
【０２８９】
【数１２５】
2008058944.tif 000062
【０２９０】
を計算する（Ｓ１０４８）。但し、ＥＰＫ（ｘ；Ｒ）は、乱数Ｒを確率的暗号におけるコイントスとして利用し、メッセージ文ｘを公開鍵ＰＫを用いて該暗号方式ＰＫＥにて暗号化した結果を表す。即ち、暗号文が乱数Ｒによって変わってくるようにする。
【０２９１】
次に、演算部８２２は、乱数生成部８２３を用いて、τ∈{0,1}ｍ、ｍ＝ｎ３（ｎ３は、公開鍵として公開されている負でない整数）をランダムに選び（Ｓ１０４９）、さらに、演算部８２２は、暗復号化部８２４を用いて、
【０２９２】
【数１２６】
2008058944.tif 000063
【０２９３】
を計算する（Ｓ１０５０）。
【０２９４】
そして、送信者側装置８２０の演算部８２２は、ステップＳ１０５０で生成した暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ）を出力部８２７から出力するか、あるいは、通信部８２６から通信回線１４０を介して、受信者側装置８１０に送信する（Ｓ１０５１）。なお、出力部８２７から暗号文Ｃが出力された場合には、送信者側装置８２０のユーザは、郵送等により、受信者側装置８１０のユーザに暗号文Ｃを通知する。
３．受信者側装置８１０での処理
受信者側装置８１０の演算部８１２は、通信部８１６が通信回線１４０を介して送信者側装置８２０より受信した、あるいは、受信者側装置８１０のユーザが入力部８１１を介して入力した暗号文Ｃを記憶部８１５に記憶する（Ｓ１０５２）。なお、演算処理部８１２は、暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【０２９５】
次に、演算部８１２は、暗復号化部８１４を用いて、
【０２９６】
【数１２７】
2008058944.tif 000064
【０２９７】
を計算する（Ｓ１０５３）。但し、ＤＳＫ（ｙ）は、該暗号方式ＰＫＥにおいて、暗号文ｙを秘密鍵ＳＫを用いて復号化した結果を表す。
【０２９８】
そして、演算部８１２は、暗復号化部８１４を用いて、記憶部８１５に記憶されている暗号文Ｃに対して、
【０２９９】
【数１２８】
2008058944.tif 000065
【０３００】
を計算し（Ｓ１０５４）、さらに、Ｍ∈{0,1}ｍ（ｍ＝ｎ１）、ｒ１，ｒ２∈｛０，１｝ｍ（ｍ＝ｎ２）、τ∈{0,1}ｍ（ｍ＝ｎ３）を計算し、
【０３０１】
【数１２９】
2008058944.tif 000066
【０３０２】
を検査する（Ｓ１０５５）。
【０３０３】
そして、検査にパスすれば，出力部８１７を介して、メッセージ文Ｍを出力し、検査にパスしなければ暗号文Ｃを不正な暗号文とみなして拒否する。
【０３０４】
本実施例の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
【０３０５】
また、第五及び第六の実施形態の場合と同様にして、既存の暗号方式がＬＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
（第八の実施形態）
本実施形態では、受信者側装置８１０を用いるユーザＡと送信者側装置８２０を用いるユーザＢとが通信を行う通信システム８００において、送信者側装置８２０のユーザＢが、ユーザＡの受信者側装置８１０において作成された公開鍵情報を用いて、通信回線１４０を介して暗号通信を行う方法について述べる。
【０３０６】
図１８は、本発明の第八の実施形態における動作手順を説明するための図である。
１．受信者側装置８１０での処理
受信者側装置８１０において、演算部８１２は、入力部８１１を介してユーザＡから鍵生成の指示を受け付けると、鍵情報生成部８１３を用いて、素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【０３０７】
【数１３０】
2008058944.tif 000067
【０３０８】
なる双線形写像ｅを作成する（Ｓ１０６０）。
【０３０９】
次に、演算部８１２は、鍵情報生成部８１３を用いて、ｓ1,ｓ2∈ＺqおよびＰ∈Ｇ1をランダムに選ぶ（Ｓ１０６１）。
【０３１０】
そして、演算部８１２の鍵情報生成部８１３は、ランダムに選んだｓ１、ｓ２及びＰを用いて、
【０３１１】
【数１３１】
2008058944.tif 000068
【０３１２】
を生成する（Ｓ１０６２）。
【０３１３】
そして、演算部８１２は、ＳＫA=（ｄIDA,1,ｄIDA,2）を復号化（秘密）鍵として、ＰＫA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,ＩＤA,Ｈ１,Ｈ２）を暗号化（公開）鍵として、両者を記憶部８１５に記憶する（Ｓ１０６３）。但し、
【０３１４】
【数１３２】
2008058944.tif 000069
【０３１５】
であり，ｍ,ｎは自然数、ＩＤA∈{０，１}m，Ｈ１,Ｈ２は、
【０３１６】
【数１３３】
2008058944.tif 000070
【０３１７】
なるハッシュ関数を意味する。
【０３１８】
次に、演算部８１２は、暗号化（公開）鍵ＰＫA=（ｑ,Ｇ1,Ｇ2,ｅ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,ＩＤA,Ｈ１,Ｈ２）を、出力部８１７から出力するか、あるいは、通信部８１６から通信回線１４０を介して送信者側装置８２０に送信する（Ｓ１０６４）。なお、出力部８１７から暗号化（公開）鍵ＰＫＡが出力された場合には、ユーザＡは、郵送等によりユーザＢに暗号化（公開）鍵ＰＫＡを通知する。
２．送信者側装置８２０での処理
送信者側装置８２０の演算部８２２は、通信部８２６が通信回線１４０を介して受信者側装置８１０より受信した、あるいは、ユーザＢが入力部８２１を介して入力した暗号化（公開）鍵ＰＫＡを記憶部８２５に記憶する（Ｓ１０６５）。
【０３１９】
次に、ユーザＢは、入力部８２１を介してメッセージ文Ｍ∈{０，１}ｎ（ｎは正整数）を入力する（Ｓ１０６６）。
【０３２０】
メッセージ文Ｍが入力されると、演算部８２２は、入力されたメッセージ文Ｍを記憶部８２５に記憶する（Ｓ１０６７）。
【０３２１】
そして、演算部８２２は、乱数生成部８２３を用いて、メッセージＭに対して、ｒ∈Ｚｑをランダムに選び（Ｓ１０６８）、
【０３２２】
【数１３４】
2008058944.tif 000071
【０３２３】
を計算する。さらに，記憶部１２５に記憶されている暗号化（公開）鍵ＰＫＡ及びメッセージＭと、暗復号化部１２４を用いて、
【０３２４】
【数１３５】
2008058944.tif 000072
【０３２５】
を計算し，さらに，
【０３２６】
【数１３６】
2008058944.tif 000073
【０３２７】
を計算する（Ｓ１０６９）。
【０３２８】
そして、演算部１２２は、暗号文Ｃ＝（Ｕ，Ｖ0，Ｖ1）を、出力部８２７から出力するか、あるいは、通信部８２６から通信回線１４０を介して受信者側装置８１０に送信する（Ｓ１０７０）。なお、出力部８２７から暗号文Ｃが出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
３．受信者側装置８１０での処理
受信者側装置８１０の演算部８１２は、通信部８１６が通信回線１４０を介して送信者側装置８２０より受信した、あるいは、ユーザＡが入力部８１１を介して入力した暗号文Ｃを記憶部８１５に記憶する（Ｓ１０７１）。
【０３２９】
次に、演算部８１２は、暗復号化部８１４を用いて、記憶部８１５に記憶されている暗号文Ｃに対して、記憶部８１５に記憶されているユーザＡの復号（秘密）鍵ＳＫＡから、
【０３３０】
【数１３７】
2008058944.tif 000074
【０３３１】
を計算し（Ｓ１０７２），
【０３３２】
【数１３８】
2008058944.tif 000075
【０３３３】
により、Ｍ∈｛０，１｝ｎを計算する（Ｓ１０７３）。
【０３３４】
本実施例に記載の公開鍵暗号通信方法は、非特許文献１および非特許文献４に記載の手法と同様の手法により、Bilinear Diffie-Hellman（BDH）問題の計算量的困難性を暗号学的仮定として、ＩＮＤ−ＣＰＡの意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-CPAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【０３３５】
本実施例における暗号通信方法は，下記非特許文献６、７に記載の方法などを用いることにより，ＩＮＤ−ＣＣＡの意味での安全に強化することが可能である。
非特許文献６：E. Fujisaki and T. Okamoto: How to enhance the security of the public-key encryption at minimum cost, PKC1999, LNCS 1560. pp.53-68, Springer-Verlag, 1999.
非特許文献７：E. Fujisaki and T. Okamoto: Secure integration of asymmetric and symmetric encryption schemes, Crypto’99, LNCS 1666. pp.537-554, Springer-Verlag, 1999.
また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
【０３３６】
また，本実施例の暗号方式において、（（１３６）式における）Ｖ0、Ｖ1の作成方法として、Ｈ2（ＩＤ||ｉ，ｖi,1，ｖi,2）を用いて共通鍵暗号における暗号化鍵Ｋを作成し、鍵Ｋを用いてメッセージ文Ｍを（該共通鍵暗号を用いて）暗号化することで、Ｖ0，Ｖ1を作成することも可能である．
図１９は、本発明の第九、第十、第十一及び第十二の実施形態に共通する通信システム９００の概略図である。
【０３３７】
図示するように、通信システム９００は、受信者側装置９１０Ａと、送信者側装置９１０Ｂと、鍵管理センタ側装置９３０と、を備えており、これらは通信回線１４０に接続されている。
【０３３８】
図２０は、受信者側装置９１０Ａ及び送信者側装置９１０Ｂの概略図である。本実施形態における受信者側装置９１０Ａ及び送信者側装置９１０Ｂは、同様の構成を有している。
【０３３９】
図示するように、受信者側装置９１０Ａ及び送信者側装置９１０Ｂは、情報を入力する入力部９１１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、受信者側装置９１０Ａ又は送信者側装置９１０Ｂの各部の制御を行う演算部９１２と、記憶部９１５と、通信回線１４０を介して通信を行う通信部９１６と、情報を出力する出力部９１７と、を備えている。
【０３４０】
また、演算部９１２は、乱数を生成する乱数生成部９１３と、暗復号化処理を行う暗復号化部９１４と、を有する。
【０３４１】
図２１は、鍵管理センタ側装置９３０の概略図である。
【０３４２】
図示するように、鍵管理センタ側装置９３０は、情報を入力する入力部９３１と、論理演算、べき乗算、剰余演算、ハッシュ関数演算、ランダム関数演算を含む各種演算、および、鍵管理センタ側装置９３０の各部の制御を行う演算部９３２と、記憶部９３４と、通信回線１４０を介して受信者側装置９１０Ａ又は送信者側装置９１０Ｂと通信を行う通信部９３５と、情報を出力する出力部９３６と、を備えている。
【０３４３】
また、演算部９３２は、システムパラメータ、マスタ鍵及びプライベート鍵を生成する鍵情報生成部９３３を有する。
【０３４４】
上記構成の受信者側装置９１０Ａ、送信者側装置９１０Ｂ及び鍵管理センタ側装置９３０についても、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ-ＲＯＭやＤＶＤ-ＲＯＭ等の可搬性を有する記憶媒体４０９から情報を読み出す読取装置４０４と、キーボードやマウスなどの入力装置４０５と、ディスプレイなどの出力装置４０６と、通信回線３００を介して相手装置と通信を行なうための通信装置４０７と、これらの各装置を接続するバス４０８とを備えた一般的なコンピュータ４００において、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。この場合、メモリ４０２や外部記憶装置４０３が記憶部９１５、９３４に利用され、通信装置４０８が通信部９１６、９３５に利用され、入力装置４０６や読取装置４０５が入力部９１１、９３１に利用され、そして、出力装置４０７が出力部９１７、９３６に利用される。
【０３４５】
この所定のプログラムは、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０４を介して記憶媒体４０９から、あるいは、通信装置４０７を介して通信回線１４０から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
（第九の実施形態）
図２２は、本発明の第九の実施形態における動作手順を説明するための図である。本実施形態では、第五の実施形態における方法をＩＤベース暗号に適用したものである。そして、第五の実施形態と同様に、ＩＤベース暗号（以下、暗号方式ＩＢＥ）が利用されている暗号通信システムが既に存在している状況を想定し、既存の暗号システムにおける暗号方式ＩＢＥを利用しながら別の暗号システム（より安全性の高い暗号システム）を構築する場合について述べる。
【０３４６】
なお、本実施形態における受信者側装置９１０Ａ、送信者側装置９１０Ｂ及び鍵管理センタ側装置９３０は、ある共通の暗号方式ＩＢＥに対応しているものとする。
１．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのセットアップのためのステップを２回実行することにより、２組の鍵のペア（ＰＫ１，ＭＳＫ１），（ＰＫ２，ＭＳＫ２）を生成する（Ｓ１０８０）。
【０３４７】
次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部９３５又は出力部９３６を介して、
【０３４８】
【数１３９】
2008058944.tif 000076
【０３４９】
をシステムパラメータとして公開し（但し、ｎは負でない整数）（Ｓ１０８１）、
【０３５０】
【数１４０】
2008058944.tif 000077
【０３５１】
を鍵管理センタのマスタ鍵として記憶部９３４に記憶する（Ｓ１０８２）。
【０３５２】
そして、鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザからプライベート鍵の生成指示を受け付けると、ＩＤ∈{0,1}ｍ、ｍ＝ｎ（ｎは、システムパラメータとして公開されている負でない整数）をＩＤ情報とするユーザに対して、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのプライベート鍵生成のためのステップを２回繰り返すことにより、２組のプライベート鍵のペアＳＫＩＤ，１，ＳＫＩＤ，２を生成し、通信部９３５又は出力部９３６を介して、これらのペアをプライベート鍵ＳＫＩＤとして、受信者側装置９１０Ａに送信又は出力する（Ｓ１０８３）。
２．送信者側装置９１０Ｂでの処理
送信者側装置９１０Ｂの演算部９１２は、通信部９１６又は入力部９１１を介して、鍵管理センタ側装置９３０が公開しているシステムパラメータＰＫを取得して、記憶部９１５に記憶する（Ｓ１０８４）。
【０３５３】
次に、送信者側装置９１０Ｂのユーザは、入力部９１１を介してメッセージ文Ｍ∈{0,1}ｍ、ｍ＝ｎ（ｎは、システムパラメータとして公開されている負でない整数）と、受信者側装置９１０ＡのユーザのＩＤ情報であるＩＤ∈{0,1}ｍ、ｍ＝ｎ（ｎは、システムパラメータとして公開されている負でない整数）を入力する（Ｓ１０８５）。
【０３５４】
メッセージ文ＭとＩＤ情報が入力されると、演算部９１２は、入力されたメッセージ文ＭとＩＤ情報を記憶部９１５に記憶する（Ｓ１０８６）。
【０３５５】
次に、演算部９１２は、乱数生成部９１３を用いて、メッセージ文Ｍ及びＩＤ情報に対して、暗号方式ＩＢＥのメッセージ空間に含まれるσ１，σ２をランダムに選ぶ（Ｓ１０８７）。
【０３５６】
そして、演算部９１２は、暗復号化部９１４を用いて、
【０３５７】
【数１４１】
2008058944.tif 000078
【０３５８】
を計算する（Ｓ１０８８）。但し、ＥＰＫ（ｘ）は、メッセージ文ｘをシステムパラメータＰＫを用いて該暗号方式ＩＢＥにて暗号化した結果を表す。
【０３５９】
さらに、演算部９１２は、暗復号化部９１４を用いて、
【０３６０】
【数１４２】
2008058944.tif 000079
【０３６１】
を計算する（Ｓ１０８９）。
【０３６２】
そして、送信者側装置９１０Ｂの演算部９１２は、ステップＳ１０８９で生成した暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ）を出力部９１７から出力するか、あるいは、通信部９１６から通信回線１４０を介して、受信者側装置９１０Ａに送信する（Ｓ１０９０）。なお、出力部９１７から暗号文Ｃが出力された場合には、送信者側装置９１０Ｂのユーザは、郵送等により、受信者側装置９１０Ａのユーザに暗号文Ｃを通知する。
３．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａの演算部９１２は、鍵管理センタ側装置９３０からプライベート鍵ＳＫＩＤを取得して、記憶部９１５に記憶する（Ｓ１０９１）。
【０３６３】
また、受信者側装置９１０Ａの演算部９１２は、通信部９１６が通信回線１４０を介して送信者側装置９１０Ｂより受信した、あるいは、受信者側装置９１０Ａのユーザが入力部９１１を介して入力した暗号文Ｃを記憶部９１５に記憶する（Ｓ１０９２）。なお、演算処理部９１２は、暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【０３６４】
次に、演算部９１２は、暗復号化部９１４を用いて、
【０３６５】
【数１４３】
2008058944.tif 000080
【０３６６】
を計算する（Ｓ１０９３）。但し、ＤＳＫＩＤ（ｙ）は、該暗号方式ＩＢＥにおいて、暗号文ｙを秘密鍵ＳＫＩＤを用いて復号化した結果を表す。
【０３６７】
そして、演算部９１２は、暗復号化部９１４を用いて、記憶部９１５に記憶されている暗号文Ｃに対して、
【０３６８】
【数１４４】
2008058944.tif 000081
【０３６９】
を計算することで、メッセージＭを復号する（Ｓ１０９４）。
【０３７０】
本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
（第十の実施形態）
図２３は、本発明の第十の実施形態における動作手順を説明するための図である。本実施形態では、第六の実施形態における方法をＩＤベース暗号に適用したものである。
１．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのセットアップのためのステップを２回実行することにより、２組の鍵のペア（ＰＫ１，ＭＳＫ１），（ＰＫ２，ＭＳＫ２）を生成する（Ｓ１１００）。
【０３７１】
次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部９３５又は出力部９３６を介して、
【０３７２】
【数１４５】
2008058944.tif 000082
【０３７３】
をシステムパラメータとして公開し（但し、ｎ１，ｎ２，ｎ３，ｎ４は負でない整数）（Ｓ１１０１）、
【０３７４】
【数１４６】
2008058944.tif 000083
【０３７５】
を鍵管理センタのマスタ鍵として記憶部９３４に記憶する（Ｓ１１０２）。
【０３７６】
そして、鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザからプライベート鍵の生成指示を受け付けると、ＩＤ∈{0,1}ｍ、ｍ＝ｎ４（ｎ４は、システムパラメータとして公開されている負でない整数）をＩＤ情報とするユーザに対して、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのプライベート鍵生成のためのステップを２回繰り返すことにより、２組のプライベート鍵のペアＳＫＩＤ，１，ＳＫＩＤ，２を生成し、通信部９３５又は出力部９３６を介して、これらのペアをプライベート鍵ＳＫＩＤとして、受信者側装置９１０Ａに送信又は出力する（Ｓ１１０３）。
２．送信者側装置９１０Ｂでの処理
送信者側装置９１０Ｂの演算部９１２は、通信部９１６又は入力部９１１を介して、鍵管理センタ側装置９３０が公開しているシステムパラメータＰＫを取得して、記憶部９１５に記憶する（Ｓ１１０４）。
【０３７７】
次に、送信者側装置９１０Ｂのユーザは、入力部９１１を介してメッセージ文Ｍ∈{0,1}ｍ、ｍ＝ｎ１（ｎ１は、システムパラメータとして公開されている負でない整数）と、受信者側装置９１０ＡのユーザのＩＤ情報であるＩＤ∈{0,1}ｍ、ｍ＝ｎ４（ｎ４は、システムパラメータとして公開されている負でない整数）を入力する（Ｓ１１０５）。
【０３７８】
メッセージ文Ｍ及びＩＤ情報が入力されると、演算部９１２は、入力されたメッセージ文ＭとＩＤ情報を記憶部９１５に記憶する（Ｓ１１０６）。
【０３７９】
次に、演算部９１２は、乱数生成部９１３を用いて、メッセージ文Ｍ及びＩＤ情報に対して、暗号方式ＩＢＥのメッセージ空間に含まれるσ１，σ２をランダムに選び、また、Ｒ１，Ｒ２∈｛０，１｝ｍ、ｍ＝ｎ２ｍ＝ｎ２（ｎ２は、システムパラメータとして公開されている負でない整数）をランダムに選ぶ（Ｓ１１０７）。
【０３８０】
そして、演算部９１２は、暗復号化部９１４を用いて、
【０３８１】
【数１４７】
2008058944.tif 000084
【０３８２】
を計算する（Ｓ１１０８）。但し、ＥＰＫ（ＩＤ，ｘ；Ｒ）は、乱数Ｒを確率的暗号におけるコイントスとして利用し、メッセージ文ｘをシステムパラメータＰＫを用いて該暗号方式ＩＢＥにて暗号化した結果を表す。
【０３８３】
さらに、演算部９１２は、暗復号化部９１４を用いて、
【０３８４】
【数１４８】
2008058944.tif 000085
【０３８５】
を計算する（Ｓ１１０９）。
【０３８６】
そして、送信者側装置９１０Ｂの演算部９１２は、ステップＳ１０８９で生成した暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ，Ｗ）を出力部９１７から出力するか、あるいは、通信部９１６から通信回線１４０を介して、受信者側装置９１０Ａに送信する（Ｓ１１１０）。なお、出力部９１７から暗号文Ｃが出力された場合には、送信者側装置９１０Ｂのユーザは、郵送等により、受信者側装置９１０Ａのユーザに暗号文Ｃを通知する。
３．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａの演算部９１２は、鍵管理センタ側装置９３０からプライベート鍵ＳＫＩＤを取得して、記憶部９１５に記憶する（Ｓ１１１１）。
【０３８７】
また、受信者側装置９１０Ａの演算部９１２は、通信部９１６が通信回線１４０を介して送信者側装置９１０Ｂより受信した、あるいは、受信者側装置９１０Ａのユーザが入力部９１１を介して入力した暗号文Ｃを記憶部９１５に記憶する（Ｓ１１１２）。なお、演算処理部９１２は、暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ，Ｗ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【０３８８】
次に、演算部９１２は、暗復号化部９１４を用いて、
【０３８９】
【数１４９】
2008058944.tif 000086
【０３９０】
を計算する（Ｓ１１１３）。但し、ＤＳＫＩＤ（ｙ）は、該暗号方式ＩＢＥにおいて、暗号文ｙを秘密鍵ＳＫＩＤを用いて復号化した結果を表す。
【０３９１】
そして、演算部９１２は、暗復号化部９１４を用いて、記憶部９１５に記憶されている暗号文Ｃに対して、
【０３９２】
【数１５０】
2008058944.tif 000087
【０３９３】
を計算し（Ｓ１１１４）、さらに、Ｍ∈{0,1}ｍ（ｍ＝ｎ１）、Ｒ１，Ｒ２∈｛０，１｝ｍ（ｍ＝ｎ２）、τ∈{0,1}ｍ（ｍ＝ｎ３）を計算し、
【０３９４】
【数１５１】
2008058944.tif 000088
【０３９５】
を検査する（Ｓ１１１５）。
【０３９６】
そして、検査にパスすれば，出力部８１７を介して、メッセージ文Ｍを出力し、検査にパスしなければ暗号文Ｃを不正な暗号文とみなして拒否する。
【０３９７】
本実施形態の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施形態では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
【０３９８】
また、実施例１の場合と同様にして、既存の暗号方式がＬＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
（第十一の実施形態）
図２４は、本発明の第十一の実施形態における動作手順を説明するための図である。本実施形態では、第七の実施形態における方法をＩＤベース暗号に適用したものである。
１．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザから鍵生成の指示を受け付けると、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのセットアップのためのステップを２回実行することにより、２組の鍵のペア（ＰＫ１，ＭＳＫ１），（ＰＫ２，ＭＳＫ２）を生成する（Ｓ１１２０）。
【０３９９】
次に、受信者側装置８１０は、入力部８１１を介してユーザからの指示を受けると、通信部９３５又は出力部９３６を介して、
【０４００】
【数１５２】
2008058944.tif 000089
【０４０１】
をシステムパラメータとして公開し（但し、ｎ１，ｎ２，ｎ３，ｎ４は負でない整数）（Ｓ１１２１）、
【０４０２】
【数１５３】
2008058944.tif 000090
【０４０３】
を鍵管理センタのマスタ鍵として記憶部９３４に記憶する（Ｓ１１２２）。
【０４０４】
そして、鍵管理センタ側装置９３０の演算部９３２は、入力部９３１を介してユーザからプライベート鍵の生成指示を受け付けると、ＩＤ∈{0,1}ｍ、ｍ＝ｎ４（ｎ４は、システムパラメータとして公開されている負でない整数）をＩＤ情報とするユーザに対して、鍵情報生成部９３３を用いて、暗号方式ＩＢＥのプライベート鍵生成のためのステップを２回繰り返すことにより、２組のプライベート鍵のペアＳＫＩＤ，１，ＳＫＩＤ，２を生成し、通信部９３５又は出力部９３６を介して、これらのペアをプライベート鍵ＳＫＩＤとして、受信者側装置９１０Ａに送信又は出力する（Ｓ１１２３）。
２．送信者側装置９１０Ｂでの処理
送信者側装置９１０Ｂの演算部９１２は、通信部９１６又は入力部９１１を介して、鍵管理センタ側装置９３０が公開しているシステムパラメータＰＫを取得して、記憶部９１５に記憶する（Ｓ１１２４）。
【０４０５】
次に、送信者側装置９１０Ｂのユーザは、入力部９１１を介してメッセージ文Ｍ∈{0,1}ｍ、ｍ＝ｎ１（ｎ１は、システムパラメータとして公開されている負でない整数）と、受信者側装置９１０ＡのユーザのＩＤ情報であるＩＤ∈{0,1}ｍ、ｍ＝ｎ４（ｎ４は、システムパラメータとして公開されている負でない整数）を入力する（Ｓ１１２５）。
【０４０６】
メッセージ文Ｍ及びＩＤ情報が入力されると、演算部９１２は、入力されたメッセージ文ＭとＩＤ情報を記憶部９１５に記憶する（Ｓ１１２６）。
【０４０７】
次に、演算部９１２は、乱数生成部９１３を用いて、メッセージ文Ｍ及びＩＤ情報に対して、暗号方式ＩＢＥのメッセージ空間に含まれるσ１，σ２をランダムに選び、また、ｒ１，ｒ２∈｛０，１｝ｍ、ｍ＝ｎ２（ｎ２は、システムパラメータとして公開されている負でない整数）をランダムに選ぶ（Ｓ１１２７）。
【０４０８】
そして、演算部９１２は、暗復号化部９１４を用いて、
【０４０９】
【数１５４】
2008058944.tif 000091
【０４１０】
を計算する（Ｓ１１２８）。
【０４１１】
さらに、演算部９１２は、暗復号化部９１４を用いて、
【０４１２】
【数１５５】
2008058944.tif 000092
【０４１３】
を計算する（Ｓ１１２９）。但し、ＥＰＫ（ＩＤ，ｘ；Ｒ）は、乱数Ｒを確率的暗号におけるコイントスとして利用し、メッセージ文ｘをシステムパラメータＰＫを用いて該暗号方式ＩＢＥにて暗号化した結果を表す。
【０４１４】
さらに、演算部９１２は、乱数生成部９１３を用いて、τ∈｛０，１｝ｍ、ｍ＝ｎ３（ｎ３は、システムパラメータとして公開されている負でない整数）をランダムに選び、暗復号化部９１４を用いて、
【０４１５】
【数１５６】
2008058944.tif 000093
【０４１６】
を計算する（Ｓ１１３０）。
【０４１７】
そして、送信者側装置９１０Ｂの演算部９１２は、ステップＳ１１３０で生成した暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ，Ｗ）を出力部９１７から出力するか、あるいは、通信部９１６から通信回線１４０を介して、受信者側装置９１０Ａに送信する（Ｓ１１３１）。なお、出力部９１７から暗号文Ｃが出力された場合には、送信者側装置９１０Ｂのユーザは、郵送等により、受信者側装置９１０Ａのユーザに暗号文Ｃを通知する。
３．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａの演算部９１２は、鍵管理センタ側装置９３０からプライベート鍵ＳＫＩＤを取得して、記憶部９１５に記憶する（Ｓ１１３２）。
【０４１８】
また、受信者側装置９１０Ａの演算部９１２は、通信部９１６が通信回線１４０を介して送信者側装置９１０Ｂより受信した、あるいは、受信者側装置９１０Ａのユーザが入力部９１１を介して入力した暗号文Ｃを記憶部９１５に記憶する（Ｓ１１３３）。なお、演算処理部９１２は、暗号文Ｃ＝（Ｕ１，Ｕ２，Ｖ，Ｗ）が暗号方式により定まる所定の暗号文空間に含まれない場合には、対暗号文を不正な暗号文とみなして拒否する。
【０４１９】
次に、演算部９１２は、暗復号化部９１４を用いて、
【０４２０】
【数１５７】
2008058944.tif 000094
【０４２１】
を計算する（Ｓ１１３４）。但し、ＤＳＫＩＤ（ｙ）は、該暗号方式ＩＢＥにおいて、暗号文ｙを秘密鍵ＳＫＩＤを用いて復号化した結果を表す。
【０４２２】
そして、演算部９１２は、暗復号化部９１４を用いて、記憶部９１５に記憶されている暗号文Ｃに対して、
【０４２３】
【数１５８】
2008058944.tif 000095
【０４２４】
を計算し（Ｓ１１３５）、さらに、Ｍ∈{0,1}ｍ（ｍ＝ｎ１）、Ｒ１，Ｒ２∈｛０，１｝ｍ（ｍ＝ｎ２）、τ∈{0,1}ｍ（ｍ＝ｎ３）を計算し、
【０４２５】
【数１５９】
2008058944.tif 000096
【０４２６】
を検査する（Ｓ１１３６）。
【０４２７】
そして、検査にパスすれば，出力部８１７を介して、メッセージ文Ｍを出力し、検査にパスしなければ暗号文Ｃを不正な暗号文とみなして拒否する。
【０４２８】
本実施例の方法では、既存の暗号システムの定義される群に依存することなく、新しい暗号システムを構築することが出来る。また、本実施例では、既存の暗号システムにおける暗号方法を利用しながら別の暗号システムを構築する場合について述べたが、既存の暗号システムが存在しない場合においても、元となる暗号方式を与えることにより、同様に新しい暗号方式を作ることが出来る。
【０４２９】
また、第六又は第七の実施形態の場合と同様にして、既存の暗号方式がＬＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って安全性が証明可能であるとき、この方式をブラックボックスとして利用しながら、より計算量的に困難な問題であるＢＤＨ問題を暗号学的仮定として、タイトなセキュリティ・リダクションを伴って選択メッセージ文攻撃に対して存在的偽造不可能な意味で安全であることがランダムオラクルモデル上で証明される。
（第十二の実施形態）
図２５は、本発明の第十二の実施形態における動作手順を説明するための図である。
【０４３０】
本実施形態では、受信者側装置９１０Ａを用いるユーザＡと、送信者側装置９１０Ｂを用いるユーザＢと、が、鍵管理センタ側装置９３０が作成した鍵情報を用いて、通信回線１４０を介して暗号通信を行う方法について述べる。
１．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０において、演算部９３２は、入力部９３１を介して鍵管理センタの管理者から鍵生成の指示を受け付けると、鍵情報生成部９３３を用いて、素数ｑ，位数ｑの加法群Ｇ1，位数ｑの乗法群Ｇ2，および、
【０４３１】
【数１６０】
2008058944.tif 000097
【０４３２】
なる双線形写像ｅを生成する（Ｓ１１４０）。
【０４３３】
次に、演算部９３２は、鍵情報生成部２３３を用いて、ｓ1，ｓ2∈ＺqおよびＰ∈Ｇ1をランダムに選ぶ（Ｓ１１４１）。
【０４３４】
そして、演算処理部９３２の鍵情報生成部９３３は、ランダムに選んだｓ1、ｓ2及びＰを用いて、
【０４３５】
【数１６１】
2008058944.tif 000098
【０４３６】
を生成する（Ｓ１１４２）。
【０４３７】
そして、演算部９３２は、ｓ＝（ｓ1，ｓ2）をマスタ鍵として、ＰＫ＝（ｑ,Ｇ1,Ｇ2,ｅ,ｌ,ｍ,ｎ,Ｐ,Ｐpub,1,Ｐpub,2,Ｈ１,Ｈ２,Ｅ,Ｄ）をシステムパラメータとして、両者を記憶部９３４に記憶する（Ｓ１１４３）。但し、ｌ,ｍ,ｎは自然数、Ｅは共通鍵暗号における暗号化関数、Ｄは共通鍵暗号における復号化関数を表し、Ｈ１,Ｈ２は、
【０４３８】
【数１６２】
2008058944.tif 000099
【０４３９】
なるハッシュ関数を意味する。
【０４４０】
次に、演算部９３２は、システムパラメータＰＫを、出力部９３６から出力するか、あるいは、通信部９３５から通信回線１４０を介して送信者側端末９１０Ｂに送信する（Ｓ１１４４）。なお、出力部９３６からシステムパラメータＰＫが出力された場合には、鍵管理センタは郵送等によりユーザＢにシステムパラメータＰＫを通知する。
２．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａにおいて、演算部９１２は、入力部９１１を介してユーザＡより受け付けたユーザＡの個別情報ＩＤAを記憶部９１５に記憶するとともに、通信回線１４０を介して通信部９１６から鍵管理センタ側装置９３０に送信する（Ｓ１１４５）。なお、ユーザＡの個別情報ＩＤAについては、ユーザＡが郵送等によって鍵管理センタに受信者側装置９１０Ａのアドレスとともに通知してもよい。
３．鍵管理センタ側装置９３０での処理
鍵管理センタ側装置９３０において、演算部９３２は、通信部９３５が通信回線１４０を介して受信者側装置９１０Ａより受信した、あるいは、入力部９３１を介して受信者側装置９１０Ａのアドレスとともに入力されたユーザＡの個別情報ＩＤＡを、受信者側装置９１０Ａのアドレスに対応付けて記憶部９３４に記憶する（Ｓ１１４６）。
【０４４１】
そして、演算部９３２は、鍵情報生成部９３３を用いて、ｂIDA∈{0,1}をランダムに選ぶ（Ｓ１１４７）。
【０４４２】
次に、演算部９３２は、鍵情報生成部９３３を用いて、記憶部９３４に記憶されているマスタ鍵ｓ及びユーザＡの個別情報ＩＤＡから、
【０４４３】
【数１６３】
2008058944.tif 000100
【０４４４】
を計算する（Ｓ１１４８）。
【０４４５】
そして、演算部９３２は、ＳＫＡ＝（ｂIDA,dIDA,1,dIDA,2）をユーザＡのプライベート鍵として、出力部９３６から出力するか、あるいは、通信回線１４０を介して通信部９３５から受信者側装置９１０Ａに安全な方法（例えば、鍵管理センタ側装置９３０が受信者側装置９１０Ａと共有する暗号鍵を用いた暗号通信）で送信する（Ｓ１１４９）。なお、出力部９３６からプライベート鍵ＳＫＡが出力された場合には、鍵管理センタはＩＣカードの郵送等の安全な方法により、ユーザＡにプライベート鍵ＳＫＡを通知する。
４．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａにおいて、演算部９１２は、通信部９１６が通信回線１４０を介して鍵管理センタ側装置９３０より受信した、あるいは、入力部９１１を介して入力されたプライベート鍵ＳＫＡを、記憶部９１５に記憶する（Ｓ１１５０）。
【０４４６】
また、演算部９１２は、ユーザＡから入力部９１１を介してユーザＡの個別情報ＩＤＡの送信指示を受けると、通信回線１４０を介して通信部９１６からユーザＡの個別情報ＩＤＡを送信する（Ｓ１１５１）。
５．送信者側装置９１０Ｂでの処理
送信側装置９１０Ｂにおいて、演算部９１２は、通信部９１６が通信回線１４０を介して鍵管理センタ側装置９３０より受信した、あるいは、入力部９１１を介して入力されたシステムパラメータＰＫを、記憶部９１５に記憶する（Ｓ１１５２）。
【０４４７】
また、送信側装置９１０Ｂにおいて、演算部９１２は、通信部９１６が通信回線１４０を介して受信側装置９１０Ａより受信した、あるいは、入力部９１１を介して入力されたユーザＡの個別情報ＩＤＡを、記憶部９１５に記憶する（Ｓ１１５３）。
【０４４８】
次に、ユーザＢは、入力部９１１を介してメッセージ文Ｍ∈{0,1}ｎ（ｎは正整数）を入力する（Ｓ１１５４）。
【０４４９】
メッセージ文Ｍが入力されると、演算部９１２は、入力されたメッセージＭを記憶部９１５に記憶する（Ｓ１１５５）。
【０４５０】
そして、演算部９１２は、乱数生成部９１３を用いて、ｒ∈Ｚqをランダムに選び（Ｓ１１５６）、
【０４５１】
【数１６４】
2008058944.tif 000101
【０４５２】
を計算する。さらに、記憶部９１５に記憶されているメッセージ文Ｍ、システムパラメータＰＫ、ユーザＡの個別情報ＩＤＡ及びユーザＢの個別情報ＩＤＢと、を用いて、
【０４５３】
【数１６５】
2008058944.tif 000102
【０４５４】
を計算し、
【０４５５】
【数１６６】
2008058944.tif 000103
【０４５６】
を計算する（Ｓ１１５７）。
【０４５７】
そして、演算部９１２は、暗号文Ｃ＝（Ｕ,Ｖ0,Ｖ1）を出力部９１７から出力するか、あるいは、通信回線１４０を介して通信部９１６から受信者側装置９１０Ａに送信する（Ｓ１１５８）。なお、出力部９１７から暗号文が出力された場合には、ユーザＢは、郵送等によりユーザＡに暗号文Ｃを通知する。
６．受信者側装置９１０Ａでの処理
受信者側装置９１０Ａの演算部９１２は、通信部９１６が通信回線１４０を介して送信者側装置９１０Ｂより受信した、あるいは、ユーザＡが入力部９１１を介して入力した暗号文Ｃを記憶部９１５に記憶する（Ｓ１１５９）。
【０４５８】
次に、演算部９１２は、暗復号化部９１４を用いて、記憶部９１５に記憶されている暗号文Ｃに対して、記憶部９１５に記憶されているユーザＡの個別情報ＩＤＡ及びプライベート鍵ＳＫＡから、
【０４５９】
【数１６７】
2008058944.tif 000104
【０４６０】
を計算し（Ｓ１１６０），
【０４６１】
【数１６８】
2008058944.tif 000105
【０４６２】
により、Ｍ∈｛０，１｝nを計算する（Ｓ１１６１）。
【０４６３】
本実施例に記載の公開鍵暗号通信方法は、非特許文献１および非特許文献４に記載の手法と同様の手法により、Bilinear Diffie-Hellman（BDH）問題の計算量的困難性を暗号学的仮定として、IND-ID-CPAの意味での安全性を証明することが可能である。このとき、本実施例の公開鍵暗号方式をアドバンテージεでIND-ID-CPAの意味で破ることができるアルゴリズムが存在したとすると、そのアルゴリズムを用いることでBDH問題をほぼアドバンテージεで解くことのできるアルゴリズムを構成できることが示される。これにより、本実施例の公開鍵暗号方式は、タイトなセキュリティ・リダクションをもつことがわかる。
【０４６４】
本実施例における暗号通信方法は、上記非特許文献６，７に記載の方法などを用いることにより，IND-ID-CCAの意味での安全に強化することが可能である。
【０４６５】
また、本実施例の暗号方式において、複数のハッシュ関数が利用されるが、一つのハッシュ関数に対して、入力値とは別に予めシードとなる値を複数定めておくことで異なる出力値を得るような関数を複数構成することができるが、このような方法でハッシュ関数を与えることも可能である。
【０４６６】
また，本実施例の暗号方式において、（（１３６）式における）Ｖ0，Ｖ1の作成方法として、Ｈ2（ＩＤ||ｉ，ｖi,1，ｖi,2）を用いて共通鍵暗号における暗号化鍵Ｋを作成し、鍵Ｋを用いてメッセージ文Ｍを（該共通鍵暗号を用いて）暗号化することで、Ｖ0，Ｖ1を作成することも可能である。
【０４６７】
上記実施例では、ユーザが各々の装置を利用して暗号通信を行うという一般形で述べたが、具体的には様々なシステムに適用される。例えば、電子ショッピングシステムでは、送信者であるユーザは消費者であり、受信者であるユーザは小売店、ユーザ側装置はパソコンなどの計算機となる。また、電子メールシステムでは、各々の装置はパソコンなどの計算機である。その他にも、従来の公開鍵暗号およびＩＤベース暗号が使われている様々なシステムに適用することが可能である。また、実施例における各計算は、CPUがメモリ内の各プログラムを実行することにより行われるものとして説明したが、プログラムだけではなく、いずれかがハードウエア化された演算装置であって、他の演算装置や、CPUと、データのやりとりを行うものであっても良い。
【図面の簡単な説明】
【０４６８】
【図１】第一及び第二の実施形態に共通する通信システム１００の概略図。
【図２】受信者側装置１１０の概略図。
【図３】送信者側装置１２０の概略図。
【図４】コンピュータ４００の概略図。
【図５】第一の実施形態における動作手順を説明するための図。
【図６】第二の実施形態における動作手順を説明するための図。
【図７】第三及び第四の実施形態に共通する通信システム２００の概略図。
【図８】受信者側装置２１０Ａ及び送信者側装置２１０Ｂの概略図。
【図９】鍵管理センタ側装置２３０の概略図。
【図１０】第三の実施形態における動作手順を説明するための図。
【図１１】第四の実施形態における動作手順を説明するための図。
【図１２】第五、第六、第七及び第八の実施形態の通信システム８００の概略図。
【図１３】受信者側装置１１０の概略図。
【図１４】送信者側装置１２０の概略図。
【図１５】第五の実施形態における動作手順を説明するための図。
【図１６】第六の実施形態における動作手順を説明するための図。
【図１７】第七の実施形態における動作手順を説明するための図。
【図１８】第八の実施形態における動作手順を説明するための図。
【図１９】第九、第十、第十一及び第十二の実施形態の通信システム９００の概略図。
【図２０】受信者側装置９１０Ａ及び送信者側装置９１０Ｂの概略図。
【図２１】鍵管理センタ側装置９３０の概略図。
【図２２】第九の実施形態における動作手順を説明するための図。
【図２３】第十の実施形態における動作手順を説明するための図。
【図２４】第十一の実施形態における動作手順を説明するための図。
【図２５】第十二の実施形態における動作手順を説明するための図。
【符号の説明】
【０４６９】
１００、２００、８００、９００：通信システム、１１０、２１０Ａ、８１０、９１０Ａ：受信者側装置、１１１、２１１、８１１、９１１：入力部、１１２、２１２、８１２、９１２：演算部、１１５、２１５、８１５、９１５：記憶部、１１６、２１６、８１６、９１６：通信部、１１７、２１７、８１７、９１７：出力部、１２０、２１０Ｂ、８２０、９１０Ｂ：送信者側装置、１２１、８２１：入力部、１２２、８２２：演算部、１２５、８２５：記憶部、１２６、８２６：通信部、１２７、８２７：出力部、２３０、９３０：鍵管理センタ側装置、２３１、９１１：入力部、２３２、９３２：演算部、２３４、９３４：記憶部、２３５、９３５：通信部、２３６、９３６：出力部、１４０：通信回線
【図１】
2008058944.tif 000171
【図２】
2008058944.tif 000172
【図３】
2008058944.tif 000173
【図４】
2008058944.tif 000174
【図５】
2008058944.tif 000175
【図６】
2008058944.tif 000176
【図７】
2008058944.tif 000177
【図８】
2008058944.tif 000178
【図９】
2008058944.tif 000179
【図１０】
2008058944.tif 000180
【図１１】
2008058944.tif 000181
【図１２】
2008058944.tif 000182
【図１３】
2008058944.tif 000183
【図１４】
2008058944.tif 000184
【図１５】
2008058944.tif 000185
【図１６】
2008058944.tif 000186
【図１７】
2008058944.tif 000187
【図１８】
2008058944.tif 000188
【図１９】
2008058944.tif 000189
【図２０】
2008058944.tif 000190
【図２１】
2008058944.tif 000191
【図２２】
2008058944.tif 000192
【図２３】
2008058944.tif 000193
【図２４】
2008058944.tif 000194
【図２５】
2008058944.tif 000195