本発明を実施するための形態について図� ��を参照して詳細に説明する。

 図1は、本実施形態による電子署名システ ムの構成を示すブロック図である。図1を参� �すると、本実施形態の電子署名システムは� �鍵生成装置11、署名装置12、および検証装置1 3を有している。

 鍵生成装置11は、鍵生成アルゴリズムが� �装されており、そのアルゴリズムに基づい� �鍵を生成する。鍵を生成する際、鍵生成装� �11にはセキュリティ・パラメータκが与えら� ��る。鍵生成装置11は、そのセキュリティ・� �ラメータκを入力として公開鍵pkと秘密鍵sk� �出力する。

 署名装置12は、署名アルゴリズムが実装� �れており、そのアルゴリズムに基づいて電� �署名を生成する。署名装置12には、鍵生成装 置11の生成した公開鍵pkおよび秘密鍵skと、電 子署名を添付すべきメッセージMとが与えら� �る。署名装置12は、それら公開鍵pk、秘密鍵s k、およびメッセージMを入力として電子署名� �を出力する。

 検証装置13は、検証アルゴリズムが実装� �れており、そのアルゴリズムに基づいて電� �署名を検証する。検証装置13には、鍵生成装 置11の生成した公開鍵pkと、署名装置12の生成 した電子署名σと、その電子署名σが添付さ� �たメッセージMとが与えられる。検証装置13� �、それら公開鍵pk、電子署名σ、およびメッ� ��ージMを入力として電子署名σが正当なもの� ��あるか否か検証する。

 鍵生成装置11、署名装置12、および検証装 置13は全てハードウェア的には不図示の演算� ��、記憶部、および通信部を有する構成であ� ��。一般的に、演算部にはCPUが用いられ、記� ��部にはメモリやハードディスクが用いられ� ��。また、一般的に、通信部はインターネッ� ��上の通信を可能にする構成である。ただし� ��演算部、記憶部、通信部はこれら一般的な� ��成に限定されるものではない。

 また、署名装置12は鍵生成装置11の出力を 入力として動作するため、実際の運用では署 名装置12が鍵生成装置11を兼ねる構成を採用� �ることが多い。ただし、必ずしも署名装置12 が鍵生成装置11を兼ねる必要はない。さらに� ��名装置12が検証装置13も兼ねる構成を採用す ることも多い。ただし、やはり署名装置12が� ��証装置13を兼ねる必要はない。

 本実施形態の電子署名方式の概要につい� ��説明する。

 ここで「署名者」という人物(または団体)� �鍵生成装置11および署名装置12を所有してい� ��とする。また、「検証者」という人物(また は団体)が検証装置13を所有しているとする。 1台の署名装置12を複数人で兼用していてもよ いが、話を簡単にするため以下では1台の署� �装置12には1人の使用者しかいないと仮定す� �。
同様に、1台の鍵生成装置11にも1人の使用者� �かおらず、1台の検証装置13にも1人の使用者� ��かいないと仮定する。ただし、複数人で装� ��を兼用する場合も同様に運用することがで� ��る。

 図2は、本実施形態による電子署名方式の 処理の流れの概略を示すフローチャートであ る。図2を参照すると、まず署名者による「� �前準備」の処理が行われる(ステップ101)。続 いて、同じく署名者による実際の「署名」の 処理が行われる(ステップ102)。最後に検証者� ��よる「検証」の処理が行われる(ステップ103 )。

 署名者の行動として上述した「事前準備� ��と「署名」の2つがある。事前準備は一度だ け行えばよい。事前準備を一旦済ませれば、 「署名」を行うことでいくつものメッセージ に対して何度でも電子署名を作成することが できる。

 署名者による「事前準備」について説明� ��る。

 署名者は、まずセキュリティ・パラメー� ��と呼ばれる値κを決定する。セキュリティ� �パラメータκは、電子署名を偽造するのがど の程度難しいのかを示す尺度である。セキュ リティ・パラメータκが大きければ大きいほ� ��電子署名を偽造するのが困難になる。続い� ��、署名者は、セキュリティ・パラメータκ� �入力して鍵生成装置11上で鍵生成アルゴリズ ムを動作させる。

 鍵生成装置11は、セキュリティ・パラメ� �タκを入力として鍵生成アルゴリズムを実行 することで公開鍵と呼ばれるデータpkと秘密� ��と呼ばれるデータskとを生成する。そして� �鍵生成装置11は生成した公開鍵pkと秘密鍵sk� �署名装置12に送る。署名装置12は鍵生成装置1 1から受けた公開鍵pkと秘密鍵skを記憶部に保� ��する。

 さらに、鍵生成装置11は公開鍵pkを何らか の方法で他の装置に公開する。ここでは公開 鍵pkを公開する方法は特に限定されない。例� ��ばPKI(Public Key Infrastructure)を用いて公開鍵pk を公開してもよく、公開鍵pkを公開掲示板に� ��き込むことにしてもよい。

 一方、秘密鍵skは他者に知られれば容易� �電子署名が偽造されてしまう。そこで、署� �装置12はこれを秘密裏に保存する。ここでは 秘密鍵skを秘密裏に保存する方法は特に限定� ��れない。例えば署名装置12にパスワードを� �定することにより、パスワードを知らない� �が署名装置12を利用できないようにしてもよ い。他の方法として、署名装置12を安全な場� ��に保管することにしてもよく、秘密鍵skを� �タンパー装置に保管することにしてもよい� �

 以上で署名者による「事前準備」が終了� ��る。

 次に署名者による「署名」について説明� ��る。

 署名者は署名装置12に署名アルゴリズム� �実行させる。署名装置12は、記憶部から公開 鍵pkと秘密鍵skと署名対象のメッセージMとを� ��み込み、これらのデータを使って電子署名� �を作成し、記憶部に書き込む。更に、署名� �置12は、署名者の要求に応じ、通信部を使っ てメッセージMと電子署名σを他の装置に送信 する。

 以上で署名者による「署名」が終了する� ��

 検証者はメッセージMに対して生成された 電子署名σを検証する。

 その際、検証者は、まず検証装置13によ� �て署名者の公開鍵pkと、メッセージMと、メ� �セージMに対する電子署名σとを入手する。� �証装置13は、公開鍵pk、メッセージM、および 電子署名σを通信部で入手し、記憶部に書き� ��む。ここでは公開鍵pkを作成した署名者のID がSであるとする。検証者の意図するところ� �、電子署名σが署名者Sによって正当な方法� �作成された電子署名であるか否かを検証す� �ことである。

 そこで、検証者は検証装置13上で検証ア� �ゴリズムを動作させる。検証装置13は記憶部 から公開鍵pk、メッセージM、および電子署名 σを読み込み、電子署名σを検証する。検証� �置13からは検証結果としてacceptとrejectの2種� �のデータのうちいずれか一方が出力される� �

 acceptは「電子署名σは署名者Sが正当な方� ��で作成したメッセージMに対する電子署名で ある」という意味である。rejectは「電子署名 σは署名者Sが正当な方法で作成したメッセー ジMに対する電子署名ではない」という意味� �ある。

 本実施形態の鍵生成アルゴリズム、署名� ��ルゴリズム、および検証アルゴリズムは、� ��造不能性を満たす任意の電子署名方式とカ� ��レオン・コミットメント方式とを融合させ� ��ことで強偽造不能性を有する電子署名方式� ��実現するものである。

 カメレオン・コミットメント方式につい� ��説明する。

 カメレオン・コミットメント方式では一� ��にGenCam、Com、Cam、ComVerという4つの関数(ア� �ゴリズム)が用いられる。

 GenCamアルゴリズムは、セキュリティ・パ� ��メータκを入力としてカメレオン・コミッ� �メント方式の公開鍵pkcamと秘密鍵skcamを生成� ��る関数である。

 Comアルゴリズムは、公開鍵pkcamとメッセ� �ジm_0を入力としてコミットメントと呼ばれ� �データCと乱数tとを生成する関数である。

 Camアルゴリズムは、公開鍵pkcamと秘密鍵sk camとメッセージmとコミットメントCと乱数tを 入力として乱数rを生成する関数である。

 ComVerアルゴリズムは、公開鍵pkcamとメッ� �ージmと乱数rとを入力としてコミットメント Cを生成する関数である。

 以下、既存のカメレオン・コミットメン� ��方式の各関数のアルゴリズムについて説明� ��る。

 ここでは{G_κ}を群の属とする。G_κとして どのような群を選んでもかまわないが、公開 鍵暗号方式を用いているので安全性の観点か らG_κ上の離散対数問題が困難であることが� �ましい。ここでG_κの位数をq_κとし、位数q_� �の巡回群をZ_κとする。

 また、以下の説明では、G_κの元gをx乗する� ��作をg^xもしくはg^{x}と書くことにする。ま� �、Hは、値域がビット列であり、しかもその� ��ット列がlog
qビット以下のハッシュ関数を示すものとす� �。

 まず、GenCamアルゴリズムについて説明す� ��。GenCamアルゴリズムにはセキュリティ・パ� ��メータκが入力される。GenCamアルゴリズム� �、まずセキュリティ・パラメータκで定まる 群G_κから元gをランダムに選択し、巡回群Z_κ から元xをランダムに選択する。そして、選� �したg、xの値を用いてh=g^xを算出し、公開鍵p kcam=(κ,g,h)と秘密鍵skcam=xを出力する。

 次に、Comアルゴリズムについて説明する� ��Comアルゴリズムには、GenCamアルゴリズムか� ��出力された公開鍵pkcam=(κ,g,h)と、任意のメ� �セージm_0とが入力される。Comアルゴリズム� �、巡回群Z_κから元tをランダムに選択し、そ のtの値と、公開鍵pkcamに含まれているg、hの� ��とを用いてコミットメントC=g^{H(m_0)}h^tを算� ��する。Comアルゴリズムの出力は乱数tとコミ ットメントCである。

 次に、Camアルゴリズムについて説明する� ��Camアルゴリズムには、GenCamアルゴリズムで� ��成された公開鍵pkcamおよび秘密鍵skcamと、Com アルゴリズムで生成された乱数tおよびコミ� �トメントCと、メッセージmとが入力される。 関数Camは、それら入力した値を用いて、Z_κ� �元の中から、H(m_0)+tx=H(m)+rxmodq_κを満たす元r� ��選択する。Camアルゴリズムの出力は乱数rで ある。

 最後に、ComVerアルゴリズムについて説明� ��る。ComVerアルゴリズムには、公開鍵pkcam=(κ, g,h)、メッセージm、および乱数rが入力される 。ComVerアルゴリズムは、それら入力された値 を用いてコミットメントC=g^{H(m)}h^rを算出す� �。ComVerアルゴリズムの出力はコミットメン� �Cである。

 以下、本実施形態の電子署名システムの� ��施例について説明する。

 (第1の実施例)
 ここでは、偽造不能性を満たす任意の電子� ��名方式のシステムをσ’とする。システムσ ’の鍵生成アルゴリズムをGen’とし、署名ア ルゴリズムをSig’とし、検証アルゴリズムを Ver’とする。

 また、カメレオン・コミットメント方式� ��システムをδとする。システムδの各関数の アルゴリズムをGenCam、Com、Cam、ComVerとする。

 また、第1の実施例によって実現される強 偽造不能性を満たす電子署名方式のシステム をσとする。システムσの鍵生成アルゴリズ� �をGenとし、署名アルゴリズムをSigとし、検� �アルゴリズムをVerとする。

 図3は、第1の実施例による各装置の構成� �示すブロック図である。図3を参照すると、� ��生成装置11はGen’部21およびGenCam部22を有し� ��いる。署名装置12はCom部31、Sig’部32、およ� ��Cam部33を有している。また、検証装置13はCom Ver部41およびVer’部42を有している。

 鍵生成装置11においてGen’部21は、セキュ リティ・パラメータκを入力として、偽造不� ��性を満たす電子署名方式のシステムσ’の� �生成アルゴリズムGen’を実行し、公開鍵pk’ および秘密鍵sk’を生成する。GenCam部22は、� �キュリティ・パラメータκを入力として、関 数GenCamのアルゴリズムを実行し、公開鍵pkcam� ��よび秘密鍵skcamを生成する。

 Gen’部21の生成した公開鍵pk’とGenCam部22� ��生成した公開鍵pkcamとの組が、鍵生成装置11 による鍵生成アルゴリズムGenの公開鍵pkとし� ��出力される。また、Gen’部21の生成した秘� �鍵sk’とGenCam部22の生成した秘密鍵skcamとの� �が、鍵生成装置11による鍵生成アルゴリズム Genの秘密鍵skとして出力される。

 署名装置12においてCom部31は、公開鍵pkに� ��まれている公開鍵pkcamと任意のメッセージm_ 0とを入力として、関数Comのアルゴリズムを� �行し、コミットメントCおよび乱数tを生成す る。Sig’部32は、Com部31で生成されたコミッ� �メントCと、秘密鍵skに含まれている秘密鍵sk ’とを入力として、偽造不能性を満たす電子 署名方式のシステムσ’の署名アルゴリズムS ig’を実行し、電子署名σ’を生成する。Cam� �33は、電子署名を生成する対象であるメッセ ージMと電子署名σ’とからなるメッセージm� �、Com部31で生成されたコミットメントCおよ� �乱数tと、公開鍵pkcamおよび秘密鍵skcamとを入 力として、関数Camのアルゴリズムを実行し、 乱数rを生成する。

 Sig’部32の生成した電子署名σ’とCam部33� ��生成した乱数rとを含むビット例が、署名装 置12による署名アルゴリズムSigの電子署名σ� �して出力される。

 検証装置13においてComVer部41は、電子署名 σに含まれている電子署名σ’および乱数rと� ��メッセージMと電子署名σ’で作ったメッセ� ��ジmと、公開鍵pkに含まれている公開鍵pkcam� �を入力として、ComVerアルゴリズムを実行し� �コミットメントCを生成する。Ver’部42は、Co mVer部41で生成されたコミットメントCと、公� �鍵pkに含まれている公開鍵pk’と、電子署名� �に含まれている電子署名σ’とを入力として 、偽造不能性を満たす電子署名方式のシステ ムσ’の検証アルゴリズムVer’を実行し、acce ptまたはrejectの検証結果を出力する。

 第1の実施形態による電子署名システムの 動作について説明する。

 図4は、第1の実施形態の鍵生成装置11によ る鍵生成アルゴリズムGenの動作を示すフロー チャートである。図4を参照すると、まず鍵� �成装置11は入力κを記憶部から読み込む(ステ ップ201)。続いて、鍵生成装置11はGen’(κ)を� �行し、Gen’(κ)の出力(pk,sk)を算出する(ステ� �プ202)。続いて、鍵生成装置11はGenCam(κ)を実� ��し、GenCam(κ)の出力(pkcam,skcam)を算出する。(� ��テップ203)。続いて、鍵生成装置11は公開鍵p k=(pk’,pkcam)と、秘密鍵sk=(sk’,skcam)を生成す� �(ステップ204)。最後に、鍵生成装置11は公開� ��pkと秘密鍵skを記憶部に書き込む(ステップ20 5)。

 図5は、第1の実施形態の署名装置12による 署名アルゴリズムSigの動作を示すフローチャ ートである。ビット列Mとビット列σをつなげ てできるビット列をM||σと示す。図5を参照す ると、署名装置12は、公開鍵pk=(pk’,pkcam)、秘 密鍵sk=(sk’,skcam)、およびメッセージMを記憶� ��から読み込む(ステップ301)。続いて、署名� �置12はCom(pkcam,m_0)を実行し、Com(pkcam,m_0)の出� �(C,t)を算出する(ステップ302)。続いて、署名� ��置12はSig’(sk’,C)を実行し、Sig’(sk’,C)の� �力σ’を算出する(ステップ303)。続いて、署� ��装置12はm=M||σ’とする(ステップ304)。続い� �、署名装置12はCam(pkcam,skcam,m,C,t)を実行し、Ca m(pkcam,skcam,m,C,t)の出力rを算出する(ステップ30 5)。続いて、署名装置12はσ=(σ’,r)とする(ス� ��ップ306)。続いて、署名装置12は電子署名σ� �記憶部に書き込む(ステップ307)。

 図6は、第1の実施形態の検証装置13による 検証アルゴリズムVerの動作を示すフローチャ ートである。図6を参照すると、検証装置13は 、まず公開鍵pk=(pk’,pkcam)、メッセージM、お� ��び電子署名σ=(σ’,r)を記憶部から読み込む( ステップ401)。続いて、検証装置13はm=M||σ’� �する(ステップ402)。続いて、検証装置13はC=Co mVer(pkcam,m,r)を計算する(ステップ403)。最後に� ��検証装置13はVer’(pk,C,σ’)=acceptならacceptを� ��憶部に書き込み、そうでなければrejectを記� ��部に書き込む(ステップ404)。

 以上説明したように、本実施例によれば� ��署名装置12は、カメレオン・コミットメン� �方式のシステムδの公開鍵pkcamを用いてシス� ��ムδのComアルゴリズムでコミットメントCお� ��び乱数tを生成する。また、署名装置12は、� ��造不能性を満たすシステムσ’の秘密鍵sk’ を用いてシステムσ’の署名アルゴリズムSig� ��で電子署名σ’を生成する。さらに、署名� �置12は、メッセージMに電子署名σ’を付加し たメッセージmと、コミットメントCと、乱数t と、公開鍵pkcamと、秘密鍵skcamとを用いてシ� �テムδのCamアルゴリズムで乱数rを生成する� �さらに、署名装置12は、その電子署名σ’と� ��数rを組み合わせて電子署名σとする。した� ��って、偽造不能性を満たす任意の電子署名� ��式とカメレオン・コミットメント方式を組� ��合わせることにより強偽造不能性を満たす� ��子署名方式を実現することができる。

 (第2の実施例)
 第1の実施例では任意のカメレオン・コミッ トメント方式から強偽造不能性の電子署名を 得る例を示したが、第2の実施例では第1の実� ��例の特殊な例を示す。

 第1の実施例における任意のカメレオン・ コミットメント方式として既存の方式を用い てもよい。しかし、安全性の観点から言えば 、以下に説明する第2の実施例のカメレオン� �コミットメント方式(GenCam_n,Com_n,Cam_n,ComVer_n)� ��用いた方がより安全性が高まる。

 第2の実施例のカメレオン・コミットメン ト方式は、GenCam_n,Com_n,Cam_n,ComVer_nの各アルゴ� ��ズムで実現されるものとする。ここでnは整 数であるとする。

 第2の実施例による電子署名システムは図 3に示した第1の実施例と同様の構成を有して� ��る。第2の実施例は、鍵生成装置11、署名装� ��12、および検証装置13で実行されるカメレオ ン・コミットメント方式のアルゴリズムだけ が第1の実施例と異なる。

 以下、カメレオン・コミットメント方式� ��GenCam_n,Com_n,Cam_n,ComVer_nのアルゴリズムにつ� �て説明をする。

 図7は、第2の実施例の鍵生成装置11による GenCam_nアルゴリズムの動作を示すフローチャ� ��トである。図7を参照すると、鍵生成装置11� ��、まず記憶部から入力κを読み込む(ステッ� ��501)。続いて、鍵生成装置11はG_κの元gをラ� �ダムに選択する(ステップ502)。続いて、鍵生 成装置11はZ_κの元x_1,・・・,x_nをランダムに� ��択する(ステップ503)。続いて、鍵生成装置11 はh_1=g^{x_1},・・・,h_n=g^{x_n}とする(ステップ50 4)。続いて、鍵生成装置11はpkcam=(κ,g,h_1,・・� ��,h_n)、skcam=(x_1,・・・,x_n)とする(ステップ505 )。最後に、鍵生成装置11は記憶部に出力(pkcam ,skcam)を書き込む(ステップ506)。

 図8は、第2の実施例の署名装置12によるCom _nアルゴリズムの動作を示すフローチャート� ��ある。図8を参照すると、署名装置12は、ま� ��記憶部から入力pkcam=(κ,g,h_1,・・・,h_n)、m_0� ��読み込む(ステップ601)。続いて、署名装置12 はZ_κの元t_1,・・・,t_nを選択し、t=(t_1,・・� �,t_n)とする(ステップ602)。続いて、署名装置1 2はC=g^{H(m_0)}h_1^{t_1}・・・h_n^{t_n}とする(ステ� ��プ603)。続いて、署名装置12は記憶部に出力( C,t)を書き込む(ステップ604)。

 図9は、第2の実施例の署名装置12によるCam _nアルゴリズムの動作を示すフローチャート� ��ある。図9を参照すると、署名装置12は、ま� ��記憶部から入力pkcam=(κ,g,h_1,・・・,h_n)、skca m=(x_1,・・・,x_n)、m、C、t=(t_1,・・・,t_n)を読� ��込む(ステップ701)。続いて、署名装置12はZ_� �の元の中から、H(m_0)+t_1x_1+・・・+t_nx_n=H(m)+r_ 1x_1+・・・+r_nx_n mod q_κを満たすものを選択� ��、r=(r_1,・・・,r_n)とする(ステップ702)。最� �に、署名装置12は記憶部に出力rを書き込む(� ��テップ703)。

 図10は、第2の実施例の検証装置13によるCo mVer_nアルゴリズムの動作を示すフローチャー トである。図10を参照すると、検証装置13は� �まず記憶部から入力としてpkcam=(κ,g,h_1,・・� ��,h_n)、m、r=(r_1,・・・,r_n)を読み込む(ステッ プ801)。続いて、検証装置13はC=g^{H(m)}h_1^{r_1}� �・・h_n^{r_n}とする(ステップ802)。最後に、検 証装置13は記憶部に出力Cを書き込む(ステッ� �803)。

 以上説明したように、第2の実施例によれ ば、拡張したカメレオン・コミットメント方 式を用いているので、より安全性が高められ ている。

 (第3の実施例)
 第3の実施例は、第2の実施例の演算量を低� �した例である。第3の実施例による電子署名� ��ステムは図3に示した第1、第2の実施例と同� ��の構成を有している。第3の実施例は、第2� �実施例におけるCom_nアルゴリズムの代わりに 、演算を削減したCom’_nアルゴリズムを適用� ��、第2の実施例におけるCam_nアルゴリズムの� ��わりに、演算を削減したCam’_nアルゴリズ� �を適用している。

 図11は、第3の実施例の署名装置12によるCo m’_nアルゴリズムの動作を示すフローチャー トである。図11を参照すると、署名装置12は� �まず記憶部から入力pkcam=(κ,g,h_1,・・・,h_n)� �m_0を読み込む(ステップ901)。続いて、署名装 置12はZ_κの元tをランダムに選択する(ステッ� ��902)。続いて、署名装置12はC=g^tする(ステッ� ��903)。最後に、署名装置12は記憶部に出力(C,t )を書き込む(ステップ904)。

 図12は、第3の実施例の署名装置12によるCa m’_nアルゴリズムの動作を示すフローチャー トである。図12を参照すると、署名装置12は� �まず記憶部から入力pkcam=(κ,g,h_1,・・・,h_n)� �skcam=(x_1,・・・,x_n)、m、C、tを読み込む(ステ ップ1001)。続いて、署名装置12はZ_κの元r_1,・ ・・,r_nの中で、t=H(m)+r_1x_1+・・・+r_nx_n mod q _κを満たすものを選択し、r=(r_1,・・・,r_n)と する(ステップ1002)。最後に、署名装置12は記� ��部に出力rを書き込む(ステップ1003)。

 以上説明したように、第3の実施例によれば 、第2の実施例のアルゴリズムを単純化して� �るので演算量を低減することができる。