(57)【特許請求の範囲】
【請求項１】
読み書き可能な記憶媒体と、
初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}を入力し、前記記憶媒体に保存する入力手段と、
前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、pk_{i_{j}}を署名装置i_{j}の公開鍵、||をビット列同士の連結とするとき、T_{m} = M_{1}||…||M_{m}||pk_{i_{1}}||…||pk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存するT_{m}計算手段と、
Hをハッシュ関数、○を排他的論理和とするとき、前記記憶媒体から必要なデータを読み込み、U=H(T_{m})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存する排他的論理和計算手段と、
前記記憶媒体から必要なデータを読み込み、n_{i_{m}}を署名装置i_{m}のRSAモジュラス、d_{i_{m}}を秘密鍵（p_{i_{m}}，q_{i_{m}}, d_{i_{m}}）の第３項とするとき、U＜n_{i_{m}}であれば、v= u^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外であれば、v=Uを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、
前記記憶媒体から必要なデータを読み込み、κをセキュリティ・パラメータとするとき、v'=v + n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射変換手段と、
前記記憶媒体から必要なデータを読み込み、v'＜n_{i_{m}}ならば、u_{i_{m}} = v'^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外ならば、u_{i_{m}} = v'を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、
前記記憶媒体からu_{i_{m}}を読み込み、署名文として出力する出力手段と、
を含むことを特徴とする署名装置。
【請求項２】
請求項１に記載される署名装置において、w_{i_{m}}=u_{i_{m-1}}、または、hをハッシュ関数としたとき、w_{i_{m}}=h(u_{i_{m-1}})を計算し、計算結果を前記記憶媒体に保存するwセット手段を含み、前記計算したw_{i_{m}}を補助情報として、前記作成した署名文u_{i_{m}}と組にして出力するものであることを特徴とする署名装置。
【請求項３】
読み書き可能な記録媒体と、
他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存する入力手段と、
変数jにm-1をセットするj初期化手段と、
前記記憶媒体から必要なデータを読み込み、n_{i_{j}}、e_{i_{j}}を署名装置i_{j}の公開鍵（n_{i_{j}}, e_{i_{j}}）の第１項、第２項とするとき、u_{i_{j}}<n_{i_{j}}であれば、v'=u_{i_{j}}^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、v'=u_{i_{j}を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、
前記記憶媒体から必要なデータを読み込み、κをセキュリティ・パラメータとするとき、v=v'- n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射計算手段と、
前記記憶媒体から必要なデータを読み込み、v<n_{i_{j}}であれば、U=v^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、U=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、
前記変数jが0になるまで、前記変数jを-1する毎に前記第二変換手段、前記全単射計算手段、前記第一変換手段による前記ステップが繰り返し実行された後、前記記憶媒体から必要なデータを読み込み、T_{j} = M_{1}||…||M_{j}||pk_{i_{1}}||…||pk_{i_{j}}を計算し、計算結果を前記記憶媒体に保存するT_{j}計算手段と、
前記記憶媒体から必要なデータを読み込み、u_{i_{j-1}}=H(T_{j})○Uを計算し、計算結果を前記記憶媒体に保存するu計算手段と、
前記記憶媒体から必要なデータを読み込み、u=予め定められた初期値であるかどうかを判定するu判定手段と、
u=予め定められた初期値であれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段とを備えたことを特徴とする検証装置。
【請求項４】
読み書き可能な記録媒体と、
他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、1つ前の署名装置が入力した署名文またはそのハッシュ値である補助情報v_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存する入力手段と、
前記記憶媒体から必要なデータを読み込み、T_{m-1} = M_{1}||…||M_{m-1}||pk_{i_{1}}||…||pk_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するT_{m-1}計算手段と、
前記記憶媒体から必要なデータを読み込み、v''=H(T_{m-1})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するv''計算手段と、
前記記憶媒体から必要なデータを読み込み、n_{i_{m-1}}、e_{i_{m-1}}を署名装置i_{m-1}の公開鍵（n_{i_{m-1}}, e_{i_{m-1}}）の第１項、第２項とするとき、v''<n_{i_{m-1}}であれば、v'=v''^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、v'=v''を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、
前記記憶媒体から必要なデータを読み込み、κをセキュリティ・パラメータとするとき、v=v'- n_{i_{m-1}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射計算手段と、
前記記憶媒体から必要なデータを読み込み、v<n_{i_{m-1}}であれば、u_{i_{m-2}}=v^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、u_{i_{m-2}}=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、
前記記憶媒体から必要なデータを読み込み、u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致するかどうかを判定するu判定手段と、
u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致すれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段とを備えたことを特徴とする検証装置。
【請求項５】
読み書き可能な記憶媒体を有するコンピュータを、
初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}を入力し、前記記憶媒体に保存する入力手段と、
前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、pk_{i_{j}}を署名装置i_{j}の公開鍵、||をビット列同士の連結とするとき、T_{m} = M_{1}||…||M_{m}||pk_{i_{1}}||…||pk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存するT_{m}計算手段と、
Hをハッシュ関数、○を排他的論理和とするとき、前記記憶媒体から必要なデータを読み込み、U=H(T_{m})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存する排他的論理和計算手段と、
前記記憶媒体から必要なデータを読み込み、n_{i_{m}}を署名装置i_{m}のRSAモジュラス、d_{i_{m}}を秘密鍵（p_{i_{m}}，q_{i_{m}}, d_{i_{m}}）の第３項とするとき、U＜n_{i_{m}}であれば、v= u^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外であれば、v=Uを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、
前記記憶媒体から必要なデータを読み込み、κをセキュリティ・パラメータとするとき、v'=v + n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射変換手段と、
前記記憶媒体から必要なデータを読み込み、v'＜n_{i_{m}}ならば、u_{i_{m}} = v'^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外ならば、u_{i_{m}} = v'を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、
前記記憶媒体からu_{i_{m}}を読み込み、署名文として出力する出力手段と、
して機能させるためのプログラム。
【請求項６】
請求項５に記載されるプログラムにおいて、前記コンピュータをさらに、w_{i_{m}}=u_{i_{m-1}}、または、hをハッシュ関数としたとき、w_{i_{m}}=h(u_{i_{m-1}})を計算し、計算結果を前記記憶媒体に保存するwセット手段、として機能させ、かつ、前記計算したw_{i_{m}}を補助情報として、前記作成した署名文u_{i_{m}}と組にして出力するためのプログラム。
【請求項７】
読み書き可能な記録媒体を有するコンピュータを、
他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存する入力手段と、
変数jにm-1をセットするj初期化手段と、
前記記憶媒体から必要なデータを読み込み、n_{i_{j}、e_{i_{j}}を署名装置i_{j}の公開鍵（n_{i_{j}}, e_{i_{j}}）の第１項、第２項とするとき、u_{i_{j}}<n_{i_{j}}であれば、v'=u_{i_{j}}^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、v'=u_{i_{j}を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、
前記記憶媒体から必要なデータを読み込み、n_{i_{m}}を署名装置i_{m}の公開鍵（n_{i_{m}}, e_{i_{m}}）の第１項、κをセキュリティ・パラメータとするとき、vv=v'- n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射計算手段と、
前記記憶媒体から必要なデータを読み込み、v<n_{i_{j}}であれば、U=v^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、U=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、
前記変数jが0になるまで、前記変数jを-1する毎に前記第二変換手段、前記全単射計算手段、前記第一変換手段による前記ステップが繰り返し実行された後、前記記憶媒体から必要なデータを読み込み、T_{j} = M_{1}||…||M_{j}||pk_{i_{1}}||…||pk_{i_{j}}を計算し、計算結果を前記記憶媒体に保存するT_{j}計算手段と、
前記記憶媒体から必要なデータを読み込み、u_{i_{j-1}}=H(T_{j})○Uを計算し、計算結果を前記記憶媒体に保存するu計算手段と、
前記記憶媒体から必要なデータを読み込み、u=予め定められた初期値であるかどうかを判定するu判定手段と、
u=予め定められた初期値であれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段として機能させるためのプログラム。
【請求項８】
読み書き可能な記録媒体を有するコンピュータを、
他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、1つ前の署名装置が入力した署名文またはそのハッシュ値である補助情報v_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存する入力手段と、
前記記憶媒体から必要なデータを読み込み、T_{m-1} = M_{1}||…||M_{m-1}||pk_{i_{1}}||…||pk_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するT_{m-1}計算手段と、
前記記憶媒体から必要なデータを読み込み、v''=H(T_{m-1})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するv''計算手段と、
前記記憶媒体から必要なデータを読み込み、n_{i_{m-1}}、e_{i_{m-1}}を署名装置i_{m-1}の公開鍵（n_{i_{j}}, e_{i_{j}}）の第１項、第２項とするとき、v''<n_{i_{m-1}}であれば、v'=v''^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、v'=v''を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、
前記記憶媒体から必要なデータを読み込み、κをセキュリティ・パラメータとするとき、v=v'- n_{i_{m-1}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射計算手段と、
前記記憶媒体から必要なデータを読み込み、v<n_{i_{m-1}}であれば、u_{i_{m-2}}=v^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、u_{i_{m-2}}=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、
前記記憶媒体から必要なデータを読み込み、u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致するかどうかを判定するu判定手段と、
u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致すれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段として機能させるためのプログラム。
【請求項９】
初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文、前記署名装置に入力されたメッセージが入力されると、前記メッセージと自装置の公開鍵及び既に署名した署名装置の公開鍵とを連結した結果を計算し、前記連結結果のハッシュ値と前記署名文との排他的論理和を導出する手段を少なくとも含む署名装置であって、
前記排他的論理和が、前記署名装置の公開鍵の一部であるRSAモジュラスを超える場合には、前記排他的論理和をそのまま出力し、超えない場合には、前記排他的論理和にRSA署名に準じた署名を行った結果を出力する第一の手段と、
前記第一の手段の出力に対して前記RSAモジュラスだけ大きいほうに写像させる関数をかける第二の手段と、
前記第二の手段での演算結果が前記RSAモジュラスを超える場合には、前記全単射手段での演算結果をそのまま出力し、超えない場合には、前記第二の手段での演算結果にRSA署名に準じた署名を行った結果を出力する第三の変換手段と、
をさらに含む、ことを特徴とする署名装置。
【請求項１０】
請求項９記載の署名装置の複数が順々に署名操作を行って作成した署名文が正当であるかどうかを検証する検証装置であって、それぞれの署名装置における署名を検証するために、
前記署名文が、対応する署名装置のRSAモジュラスを超える場合にはそのまま出力し、超えない場合には、RSA署名に準じた署名を行った結果を出力する第四の手段と、
前記第四の手段の出力に対して前記RSAモジュラスだけ小さいほうに写像させる関数をかける第五の手段と、
前記第五の手段の出力が前記RSAモジュラスを超える場合には、前記第五の手段の出力をそのまま出力し、超えない場合には、前記第五の手段の出力に、RSA署名に準じた署名を行った結果を出力する第六の手段と、
前記署名装置に入力されたメッセージと自装置の公開鍵及び既に署名した署名装置の公開鍵とを連結した結果のハッシュ値と前記第六の手段の出力の排他的論理和を求める第七の手段と、
を含み、
それぞれの前記署名装置に対する前記第七の手段による出力結果に基づき検証の成功、失敗を判定する、ことを特徴とする検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は署名および検証方法ならびに署名および検証装置に関し、特に複数の署名装置が署名する状況における、署名長が署名装置の数に依存しない署名および検証方法ならびに署名および検証装置に関する。
【背景技術】
【０００２】
計算機やインターネット環境の普及に伴い、電子的にメッセージを送受信する機会が増えている。このような場合には、メッセージを送信する途中でメッセージが改竄されることを防ぐため、メッセージに電子署名を添付することが望ましい。【０００３】
しかしRSAやDSAといったよく知られた署名方式を用いて複数の署名装置が署名を作成した場合、全員が署名したことを表すには、全署名装置が個々に署名文を作成し、それらの署名文を全て保存する必要がある。この為、署名文のデータ長の合計値が署名装置の台数に比例するので、署名装置数が多い場合には効率がよくない。【０００４】
このような問題を解決する署名方式の1つとして、非特許文献1に記載される署名方式が提案されている。図11に、この従来の署名方式の手順を示す。【０００５】
なお、本明細書において使用する記号の意味について、ここで定義しておく。「||」はビット列同士の連結を意味する。「○」はビット毎の排他的論理和を意味する。「^」は右の被演算子を指数として左の被演算子をべき乗した値を算出する算術演算子を表する。例えば、f^{-1}はf-1のことである。「_{x}」はxが添え字であることを表す。例えば、u_{i}はuiのことである。【０００６】
図11を参照すると、署名対象となる署名文u_{i_{m-1}}が入力されると(S3F100)、所有している鍵の正当性の検証(S3F101)と署名文u_{i_{m-1}}の正当性の検証(S3F102)を実施した後、自署名装置の公開鍵及び既に署名した署名装置の公開鍵を連結したT_{m}を計算する(S3F103)。次に、T_{m}のハッシュ値と署名文u_{i_{m-1}}の排他的論理和Uを計算し(S3F104)、Uのビット列のうちはじめのセキュリティパラメタkビットをa、残りをsとする(S3F105)。次に、aと自署名装置のRSAモジュラスn_{i_{m}}とを比較し(S3F106)、aがRSAモジュラスn_{i_{m}}よりも小さいときは、aに対して秘密鍵d_{i_{m}}でRSA方式に準じて署名文u_{i_{m}}を計算し(S3F107)、出力する(S3F109)。このときsに制御情報として1ビットの情報0を付け加える。また、aがRSAモジュラスn_{i_{m}}よりも大きいときは、モジュラスより大きい数に対してはRSA署名を計算できないので、aをn_{i_{m}}だけ減算したものに対して署名文u_{i_{m}}を計算し(S3F108)、出力する(S3F109)。このときはsに制御情報として1ビットの情報1を付け加える。【０００７】
このように、RSAの場合、署名装置のRSAモジュラスn_{i_{m}}より大きい数に対しては署名を計算できないので、非特許文献1による従来技術では、若し大きい場合はモジュラスn_{i_{m}}だけ減算してから署名を付ける。このとき、後の検証を可能にするために、後ろに1bitの制御情報(モジュラスを超えていた場合は1、そうでない場合は0)を付けておく。署名文u_{i_{m}}の検証時は、署名装置の公開鍵を署名順番と逆順に使用して検証を繰り返していき、最終的に予め定められた初期値が得られるところまで遡って検証できることにより、正しい署名であると判断する。
【非特許文献１】Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, Hovav Shacham.Sequential Aggregate Signatures from Trapdoor Permutations. In Advances in Cryptology -- EUROCRYPT 2004,vol. 3027 of LNCS, pp. 74-90. Springer-Verlag, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
非特許文献1に記載された従来の署名方式によれば、複数の署名装置が順々に署名しても署名文のデータ長の合計値が署名装置の台数に比例しないため、署名文を記憶する場合にはメモリ量の削減が可能になり、通信する場合には通信量の削減が可能になる。しかしながら、署名長は固定値＋署名回数であり、署名回数が増えると少しずつではあるが署名長が伸びるという問題点がある。【０００９】
本発明の目的は、上述した従来の署名方式が有する問題点を改善し、署名長が署名装置の数によらずに一定になるようにすることにある。
【課題を解決するための手段】
【００１０】
請求項1にかかる署名方法は、初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文、メッセージ、および自署名装置の秘密鍵を入力とし、入力と同じ長さの署名文を出力する署名装置における署名方法であって、前記出力した署名文が、その前記出力した署名文の作成にかかわった署名装置が各々の署名装置に入力された前記メッセージに署名したことを示すものであることを特徴とする。【００１１】
請求項2にかかる署名方法は、請求項1に記載された署名方法において、署名文を計算する操作が第1および第2の2つのステップを持ち、前記第1ステップ（f^{-1}の部分の操作）の計算にはトラップドアつき一方向性置換の逆関数を用い、前記第2ステップ（h^{-1}の部分の操作）の計算には、前記第1ステップのものと同じもしくは異なるトラップドアつき一方向性置換の逆関数を用い、前記第1ステップが終了したら計算結果を記憶媒体に記憶し、前記第2ステップ開始時には必要なデータを前記記憶媒体から読み出し、前記第2ステップが終了したら計算結果を前記記憶媒体に記憶することを特徴とする。【００１２】
請求項3にかかる署名方法は、請求項2に記載された署名方法において、前記第1ステップでは、前記第1ステップへの入力がもし前記トラップドアつき一方向性置換の値域の元であればその前記トラップドアつき一方向性置換の逆関数で前記入力を写像し、そうでなければ何もしないというものであり、前記第2ステップへの入力がもし前記トラップドアつき一方向性置換の値域の元であればその前記トラップドアつき一方向性置換の逆関数で前記入力を写像し、そうでなければ何もしないというものであることを特徴とする。【００１３】
請求項4にかかる署名方法は、請求項3に記載された署名方法において、前記第2ステップで用いる前記トラップドアつき一方向性置換の計算がさらに第1および第2のサブステップからなり、前記第1サブステップ（φ^{-1}の部分の操作）では、署名文全体の空間上の全単射を計算し、その全単射が多項式時間で計算でき、しかもその前記全単射の逆関数も多項式時間で計算できるものであり、前記第2サブステップ(g^{-1}の部分の操作)ではトラップドアつき一方向性置換の逆関数を用い、もし前記トラップドアつき一方向性置換の値域の元であればその前記トラップドアつき一方向性置換の逆関数で前記入力を写像し、そうでなければ何もしないというものであり、前記第1サブステップおよび前記第2サブステップの開始時には必要なデータを前記記憶媒体から読み込み、前記第1サブステップおよび前記第2サブステップの終了時には計算結果を前記記憶媒体に書き込むことを特徴とする。【００１４】
請求項5にかかる署名方法は、請求項4に記載された署名方法において、前記第1ステップで使用する前記トラップドアつき一方向性置換と、前記第2ステップの前記第2サブステップで使用する前記トラップドアつき一方向性置換とがRSA関数であることを特徴とする。【００１５】
請求項6にかかる署名方法は、請求項5に記載された署名方法において、前記第2ステップの前記第1サブステップで使用する前記全単射が、φ(x) = x - n_{i_{m}} mod 2^{κ}とかけ、前記n_{i_{m}}が署名装置i_{m}の公開鍵の一部であるRSAモジュラスであり、前記κがセキュリティ・パラメータであることを特徴とする。【００１６】
請求項7にかかる署名方法は、請求項6に記載された署名方法において、前記第1ステップの前にT_{m}計算ステップがあり、前記T_{m}計算ステップでは、T_{m} = M_{1}||…||M_{m}||pk_{i_{1}}||…||pk_{i_{m}}を計算し、各jに対し前記M_{1},…, M_{j}がj番目の署名装置に入力されたメッセージであり、前記pk_{i_{j}}が署名装置i_{j}の公開鍵であることを特徴とする。【００１７】
請求項8にかかる署名方法は、請求項7に記載された署名方法で、前記第1ステップの前に排他的論理和計算ステップがあり、前記排他的論理和計算ステップでは、U=H(T_{m})○u_{i_{m-1}}を計算し、前記Hがハッシュ関数で、前記u_{i_{m-1}}が前記入力された署名文であり、○が排他的論理和であることを特徴とする。【００１８】
請求項9にかかる署名方法は、請求項8に記載された署名方法で、前記第1ステップより前に鍵正当性検証ステップがあり、前記鍵正当性検証ステップではpk_{i_{1}},…, pk_{i_{m-1}}が全て異なることを確認するが、ただしm=1の場合は何も確認しないステップであることを特徴とする。【００１９】
請求項10にかかる署名方法は、請求項9に記載された署名方法で、前記第1ステップより前に、入力の署名文を検証する署名文検証ステップがあることを特徴とする。【００２０】
請求項11にかかる署名方法は、請求項8に記載された署名方法で、前記第1ステップより前に、pk_{i_{1}},…, pk_{i_{m-1}}が全て異なることを確認する鍵正当性検証ステップと、入力の署名文を検証する署名文検証ステップとがあることを特徴とする。【００２１】
請求項12にかかる署名方法は、請求項1ないし11の何れか1項に記載された署名方法において、入力の初期値もしくは署名文またはそれらのハッシュ値を補助情報として作成し前記記憶媒体に書き込むステップを含み、前記補助情報と署名文とを組にして出力することを特徴とする。【００２２】
請求項13にかかる署名方法は、入力手段が、初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}を入力し、記憶媒体に保存するステップ、T_{m}計算手段が、前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、pk_{i_{j}}を署名装置i_{j}の公開鍵、||をビット列同士の連結とするとき、T_{m} = M_{1}||…||M_{m}||pk_{i_{1}}||…||pk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存するステップ、排他的論理和計算手段が、Hをハッシュ関数、○を排他的論理和とするとき、前記記憶媒体から必要なデータを読み込み、U=H(T_{m})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するステップ、第一変換手段が、前記記憶媒体から必要なデータを読み込み、n_{i_{m}}を自署名装置のRSAモジュラスとするとき、U＜n_{i_{m}}であれば、v= u^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外であれば、v=Uを計算し、計算結果を前記記憶媒体に保存するステップ、全単射変換手段が、前記記憶媒体から必要なデータを読み込み、κをセキュリティ・パラメータとするとき、v'=v + n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存するステップ、第二変換手段が、前記記憶媒体から必要なデータを読み込み、v'＜n_{i_{m}}ならば、u_{i_{m}} = v'^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外ならば、u_{i_{m}} = v'を計算し、計算結果を前記記憶媒体に保存するステップ、出力手段が、前記記憶媒体からu_{i_{m}}を読み込み、署名文として出力するステップ、を含むことを特徴とする。【００２３】
請求項14にかかる署名方法は、請求項13に記載される署名方法において、wセット手段が、w_{i_{m}}=u_{i_{m-1}}、または、hをハッシュ関数としたとき、w_{i_{m}}=h(u_{i_{m-1}})を計算し、計算結果を前記記憶媒体に保存するステップを含み、前記計算したw_{i_{m}}を補助情報として、前記作成した署名文u_{i_{m}}と組にして出力することを特徴とする。【００２４】
請求項15にかかる検証方法は、複数の署名装置が順々に署名操作を行って作成した署名文uが正当であるかどうかを検証する検証装置における検証方法において、検証を通過するのは、署名文uが、前記出力した署名文がその前記出力した署名文の作成にかかわった署名装置が各々の署名装置に入力された前記メッセージに署名したときおよびそのときのみであり、前記署名文uのビット長が前記署名文uを計算するのにかかわった前記署名装置の数に依存しない定数であることを特徴とする。【００２５】
請求項16にかかる検証方法は、複数の署名装置が順々に署名操作を行って作成した署名文uが正当であるかどうかを検証する検証装置における検証方法において、検証を通過するのは、署名文uを作成した署名装置が正当な方法で署名文uを作成したときおよびそのときのみであり、前記署名文uのビット長が前記署名文uを計算するのにかかわった前記署名装置の数に依存しない定数であり、しかも前記署名文uの検証は、前記複数の署名装置のうち最後の1台が署名操作を施す前のデータである補助情報wを使って行うことを特徴とする。【００２６】
請求項17にかかる検証方法は、請求項15または16に記載された検証方法において、署名文を検証する操作が第1および第2の2つのステップがあり、前記第1ステップ（hの部分の操作）の計算にはトラップドアつき一方向性置換を用い、前記第2ステップ（fの部分の操作）の計算には、前記第1ステップのものと同じもしくは異なるトラップドアつき一方向性置換を用い、前記第1ステップおよび第2ステップを開始する際、記憶媒体から必要なデータを読み込み、前記第1ステップおよび第2ステップを終了する際、前記記憶媒体に計算結果を書き込むことを特徴とする。【００２７】
請求項18にかかる検証方法は、請求項17に記載された検証方法において、前記第1ステップでは、前記第1ステップへの入力がもし前記トラップドアつき一方向性置換の定義域の元であればその前記トラップドアつき一方向性置換で前記入力を写像し、そうでなければ何もしないものであり、前記第2ステップへの入力がもし前記トラップドアつき一方向性置換の定義域の元であればその前記トラップドアつき一方向性置換で前記入力を写像し、そうでなければ何もしないものであることを特徴とする。【００２８】
請求項19にかかる検証方法は、請求項18に記載された検証方法において、前記第1ステップで用いる前記トラップドアつき一方向性置換の計算がさらに第1および第2の2つのサブステップからなり、前記第1サブステップ(gの部分の操作)ではトラップドアつき一方向性置換の関数を用い、もし前記トラップドアつき一方向性置換の値域の元であればその前記トラップドアつき一方向性置換の関数で入力を写像し、そうでなければ何もしないというものであり、前記第2サブステップ（φの部分の操作）では、署名文全体の空間上の全単射を計算し、その全単射が多項式時間で計算でき、しかもその前記全単射の逆関数も多項式時間で計算できるものであり、前記第1サブステップおよび前記第2サブステップの開始時には必要なデータを前記記憶媒体から読み込み、前記第1サブステップおよび前記第2サブステップの終了時には計算結果を前記記憶媒体に書き込むことを特徴とする。【００２９】
請求項20にかかる検証方法は、請求項19に記載された検証方法において、前記第1ステップの前記第1サブステップで使用する前記トラップドアつき一方向性置換と、前記第2ステップで使用する前記トラップドアつき一方向性置換とがRSA関数であることを特徴とする。【００３０】
請求項21にかかる検証方法は、請求項20に記載された検証方法において、前記第1ステップの前記第2サブステップで使用する前記全単射が、φ(x) = x + n_i_{m} mod 2^{κ}とかけ、前記n_{i_{m}}が署名装置i_{m}の公開鍵の一部であるRSAモジュラスであり、前記κがセキュリティ・パラメータであることを特徴とする。【００３１】
請求項22にかかる検証方法は、請求項21に記載された検証方法において、前記第2ステップの後にT_{j}計算ステップがあり、前記T_{j}計算ステップでは、T_{j} = M_{1}||…||M_{j}||pk_{i_{1}}||…||pk_{i_{j}}を計算するものであり、ここで、各jに対し前記M_{1}, ..., M_{j}がj番目の署名装置に入力されたメッセージであり、前記pk_{i_{j}}が署名装置i_{j}の公開鍵であることを特徴とする。【００３２】
請求項23にかかる検証方法は、請求項22に記載された検証方法において、前記T_{j}計算ステップの後に、Hをハッシュ関数、Uを第2ステップの計算結果とするとき、前記記憶媒体から必要なデータを読み込み、u_{i_{j-1}}=H(T_{j})○Uを計算し、計算結果を前記記憶媒体に保存するu計算ステップがあることを特徴とする。【００３３】
請求項24にかかる検証方法は、請求項23に記載された検証方法において、前記第1ステップ、前記第2ステップ、前記T_{j}計算ステップおよび前記u計算ステップを、j=m-1,…,1に対して繰り返すことを特徴とする。【００３４】
請求項25にかかる検証方法は、請求項24に記載された検証方法において、前記第1ステップ、前記第2ステップ、前記T_{j}計算ステップおよび前記u計算ステップを、j=m-1,…,1に対して繰り返す前に、鍵正当性検証ステップがあり、前記鍵正当性検証ステップでは、pk_{i_{1}},…, pk_{i_{m-1}}が全て異なることを確認するが、ただしm=1の場合は何も確認しないものであることを特徴とする。【００３５】
請求項26にかかる検証方法は、請求項25に記載された検証方法において、前記第1ステップ、前記第2ステップ、前記T_{j}計算ステップおよび前記u計算ステップを、j=m-1,…,1に対して繰り返した後に、検証結果として初期値が得られたかどうかを判定するu判定ステップがあることを特徴とする。【００３６】
請求項27にかかる検証方法は、請求項21に記載された検証方法において、前記第1ステップの前にT_{m-1}計算ステップおよびv''計算ステップがあり、前記T_{m-1}計算ステップでは、T_{m-1} = M_{1}||…||M_{m-1}||pk_{i_{1}}||…||pk_{i_{m-1}}を計算するものであり、ここで、M_{1},…, M_{m-1}が1,…,m-1番目の署名装置に入力されたメッセージであり、前記pk_{i_{j}}が署名装置i_{j}の公開鍵であり、前記v''計算ステップでは、v''=H(T_{m-1})○u_{i_{m-1}}を計算するものであり、かつ、前記第1ステップは前記v''を入力とし、かつ、前記第2ステップの後に、前記第2ステップの計算結果が前記補助情報に一致するか判定するu判定ステップがあることを特徴とする。【００３７】
請求項28にかかる検証方法は、入力手段が、他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存するステップ、j初期化手段が、変数jにm-1をセットするステップ、第二変換手段が、前記記憶媒体から必要なデータを読み込み、u_{i_{j}}<n_{i_{j}}であれば、v'=u_{i_{j}}^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、v'=u_{i_{j}を計算し、計算結果を前記記憶媒体に保存するステップ、全単射計算手段が、前記記憶媒体から必要なデータを読み込み、v=v'- n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存するステップ、第一変換手段が、前記記憶媒体から必要なデータを読み込み、v<n_{i_{j}}であれば、U=v^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、U=vを計算し、計算結果を前記記憶媒体に保存するステップ、前記変数jが0になるまで、前記変数jを-1する毎に前記第二変換手段、前記全単射計算手段、前記第一変換手段による前記ステップを繰り返すステップ、T_{j}計算手段が、前記記憶媒体から必要なデータを読み込み、T_{j} = M_{1}||…||M_{j}||pk_{i_{1}}||…||pk_{i_{j}}を計算し、計算結果を前記記憶媒体に保存するステップ、u計算手段が、前記記憶媒体から必要なデータを読み込み、u_{i_{j-1}}=H(T_{j})○Uを計算し、計算結果を前記記憶媒体に保存するステップ、u判定手段が、前記記憶媒体から必要なデータを読み込み、u=予め定められた初期値であるかどうかを判定するステップ、出力手段が、u=予め定められた初期値であれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力するステップ、を含むことを特徴とする。【００３８】
請求項29にかかる検証方法は、入力手段が、他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、1つ前の署名装置が入力した署名文またはそのハッシュ値である補助情報v_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存するステップ、T_{m-1}計算手段が、前記記憶媒体から必要なデータを読み込み、T_{m-1} = M_{1}||…||M_{m-1}||pk_{i_{1}}||…||pk_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するステップ、v''計算手段が、前記記憶媒体から必要なデータを読み込み、v''=H(T_{m-1})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するステップ、第二変換手段が、前記記憶媒体から必要なデータを読み込み、v''<n_{i_{m-1}}であれば、v'=v''^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、v'=v''を計算し、計算結果を前記記憶媒体に保存するステップ、全単射計算手段が、前記記憶媒体から必要なデータを読み込み、v=v'- n_{i_{m-1}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存するステップ、第一変換手段が、前記記憶媒体から必要なデータを読み込み、v<n_{i_{m-1}}であれば、u_{i_{m-2}}=v^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、u_{i_{m-2}}=vを計算し、計算結果を前記記憶媒体に保存するステップ、u判定手段が、前記記憶媒体から必要なデータを読み込み、u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致するかどうかを判定するステップ、出力手段が、u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致すれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力するステップ、を含むことを特徴とする。【００３９】
請求項30にかかる署名装置は、読み書き可能な記憶媒体と、初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}を入力し、前記記憶媒体に保存する入力手段と、前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、pk_{i_{j}}を署名装置i_{j}の公開鍵、||をビット列同士の連結とするとき、T_{m} = M_{1}||…||M_{m}||pk_{i_{1}}||…||pk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存するT_{m}計算手段と、Hをハッシュ関数、○を排他的論理和とするとき、前記記憶媒体から必要なデータを読み込み、U=H(T_{m})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存する排他的論理和計算手段と、前記記憶媒体から必要なデータを読み込み、n_{i_{m}}を自署名装置のRSAモジュラスとするとき、U＜n_{i_{m}}であれば、v= u^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外であれば、v=Uを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、前記記憶媒体から必要なデータを読み込み、κをセキュリティ・パラメータとするとき、v'=v + n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射変換手段と、前記記憶媒体から必要なデータを読み込み、v'＜n_{i_{m}}ならば、u_{i_{m}} = v'^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外ならば、u_{i_{m}} = v'を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、前記記憶媒体からu_{i_{m}}を読み込み、署名文として出力する出力手段と、を含むことを特徴とする。【００４０】
請求項31にかかる署名装置は、請求項30に記載される署名装置において、w_{i_{m}}=u_{i_{m-1}}、または、hをハッシュ関数としたとき、w_{i_{m}}=h(u_{i_{m-1}})を計算し、計算結果を前記記憶媒体に保存するwセット手段を含み、前記計算したw_{i_{m}}を補助情報として、前記作成した署名文u_{i_{m}}と組にして出力するものであることを特徴とする。【００４１】
請求項32にかかる検証装置は、読み書き可能な記録媒体と、他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存する入力手段と、変数jにm-1をセットするj初期化手段と、前記記憶媒体から必要なデータを読み込み、u_{i_{j}}<n_{i_{j}}であれば、v'=u_{i_{j}}^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、v'=u_{i_{j}を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、前記記憶媒体から必要なデータを読み込み、v=v'- n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射計算手段と、前記記憶媒体から必要なデータを読み込み、v<n_{i_{j}}であれば、U=v^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、U=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、前記変数jが0になるまで、前記変数jを-1する毎に前記第二変換手段、前記全単射計算手段、前記第一変換手段による前記ステップが繰り返し実行された後、前記記憶媒体から必要なデータを読み込み、T_{j} = M_{1}||…||M_{j}||pk_{i_{1}}||…||pk_{i_{j}}を計算し、計算結果を前記記憶媒体に保存するT_{j}計算手段と、前記記憶媒体から必要なデータを読み込み、u_{i_{j-1}}=H(T_{j})○Uを計算し、計算結果を前記記憶媒体に保存するu計算手段と、前記記憶媒体から必要なデータを読み込み、u=予め定められた初期値であるかどうかを判定するu判定手段と、u=予め定められた初期値であれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段とを備えたことを特徴とする。【００４２】
請求項33にかかる検証装置は、読み書き可能な記録媒体と、他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、1つ前の署名装置が入力した署名文またはそのハッシュ値である補助情報v_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存する入力手段と、前記記憶媒体から必要なデータを読み込み、T_{m-1} = M_{1}||…||M_{m-1}||pk_{i_{1}}||…||pk_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するT_{m-1}計算手段と、前記記憶媒体から必要なデータを読み込み、v''=H(T_{m-1})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するv''計算手段と、前記記憶媒体から必要なデータを読み込み、v''<n_{i_{m-1}}であれば、v'=v''^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、v'=v''を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、前記記憶媒体から必要なデータを読み込み、v=v'- n_{i_{m-1}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射計算手段と、前記記憶媒体から必要なデータを読み込み、v<n_{i_{m-1}}であれば、u_{i_{m-2}}=v^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、u_{i_{m-2}}=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、前記記憶媒体から必要なデータを読み込み、u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致するかどうかを判定するu判定手段と、u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致すれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段とを備えたことを特徴とする。【００４３】
請求項34にかかるプログラムは、読み書き可能な記憶媒体を有するコンピュータを、初期値もしくは他の複数の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}を入力し、前記記憶媒体に保存する入力手段と、前記記憶媒体および公開鍵記憶装置から必要なデータを読み込み、pk_{i_{j}}を署名装置i_{j}の公開鍵、||をビット列同士の連結とするとき、T_{m} = M_{1}||…||M_{m}||pk_{i_{1}}||…||pk_{i_{m}}を計算し、計算結果を前記記憶媒体に保存するT_{m}計算手段と、Hをハッシュ関数、○を排他的論理和とするとき、前記記憶媒体から必要なデータを読み込み、U=H(T_{m})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存する排他的論理和計算手段と、前記記憶媒体から必要なデータを読み込み、n_{i_{m}}を自署名装置のRSAモジュラスとするとき、U＜n_{i_{m}}であれば、v= u^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外であれば、v=Uを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、前記記憶媒体から必要なデータを読み込み、κをセキュリティ・パラメータとするとき、v'=v + n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射変換手段と、前記記憶媒体から必要なデータを読み込み、v'＜n_{i_{m}}ならば、u_{i_{m}} = v'^{d_{i_{m}}} mod n_{i_{m}}を計算し、それ以外ならば、u_{i_{m}} = v'を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、前記記憶媒体からu_{i_{m}}を読み込み、署名文として出力する出力手段と、して機能させることを特徴とする。【００４４】
請求項35にかかるプログラムは、請求項34に記載されるプログラムにおいて、前記コンピュータをさらに、w_{i_{m}}=u_{i_{m-1}}、または、hをハッシュ関数としたとき、w_{i_{m}}=h(u_{i_{m-1}})を計算し、計算結果を前記記憶媒体に保存するwセット手段、として機能させ、かつ、前記計算したw_{i_{m}}を補助情報として、前記作成した署名文u_{i_{m}}と組にして出力することを特徴とする。【００４５】
請求項36にかかるプログラムは、読み書き可能な記録媒体を有するコンピュータを、他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存する入力手段と、変数jにm-1をセットするj初期化手段と、前記記憶媒体から必要なデータを読み込み、u_{i_{j}}<n_{i_{j}}であれば、v'=u_{i_{j}}^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、v'=u_{i_{j}を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、前記記憶媒体から必要なデータを読み込み、v=v'- n_{i_{m}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射計算手段と、前記記憶媒体から必要なデータを読み込み、v<n_{i_{j}}であれば、U=v^{e_{i_{j}}} mod n_{i_{j}}を計算し、それ以外であれば、U=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、前記変数jが0になるまで、前記変数jを-1する毎に前記第二変換手段、前記全単射計算手段、前記第一変換手段による前記ステップが繰り返し実行された後、前記記憶媒体から必要なデータを読み込み、T_{j} = M_{1}||…||M_{j}||pk_{i_{1}}||…||pk_{i_{j}}を計算し、計算結果を前記記憶媒体に保存するT_{j}計算手段と、前記記憶媒体から必要なデータを読み込み、u_{i_{j-1}}=H(T_{j})○Uを計算し、計算結果を前記記憶媒体に保存するu計算手段と、前記記憶媒体から必要なデータを読み込み、u=予め定められた初期値であるかどうかを判定するu判定手段と、u=予め定められた初期値であれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段として機能させることを特徴とする。【００４６】
請求項37にかかるプログラムは、読み書き可能な記録媒体を有するコンピュータを、他の1以上の署名装置が順々に署名操作を行って作成した署名文u_{i_{m-1}}、1つ前の署名装置が入力した署名文またはそのハッシュ値である補助情報v_{i_{m-1}}、それらの署名装置に入力されたメッセージM_{1},…, M_{m-1}、それらの署名装置の公開鍵pk_{i_{1}},…,pk_{i_{m-1}}を入力し、記憶媒体に保存する入力手段と、前記記憶媒体から必要なデータを読み込み、T_{m-1} = M_{1}||…||M_{m-1}||pk_{i_{1}}||…||pk_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するT_{m-1}計算手段と、前記記憶媒体から必要なデータを読み込み、v''=H(T_{m-1})○u_{i_{m-1}}を計算し、計算結果を前記記憶媒体に保存するv''計算手段と、前記記憶媒体から必要なデータを読み込み、v''<n_{i_{m-1}}であれば、v'=v''^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、v'=v''を計算し、計算結果を前記記憶媒体に保存する第二変換手段と、前記記憶媒体から必要なデータを読み込み、v=v'- n_{i_{m-1}} mod 2^{κ}を計算し、計算結果を前記記憶媒体に保存する全単射計算手段と、前記記憶媒体から必要なデータを読み込み、v<n_{i_{m-1}}であれば、u_{i_{m-2}}=v^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、それ以外であれば、u_{i_{m-2}}=vを計算し、計算結果を前記記憶媒体に保存する第一変換手段と、前記記憶媒体から必要なデータを読み込み、u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致するかどうかを判定するu判定手段と、u_{i_{m-2}}またはそのハッシュ値が前記補助情報v_{i_{m-1}}と一致すれば、検証成功を示す通知を出力し、そうでなければ、検証失敗を示す通知を出力する出力手段と、して機能させることを特徴とする。【００４７】
『作用』
本発明にあっては、署名装置i_{m}において、入力された署名文u_{i_{m-1}}がモジュラスn_{i_{m}}を超える場合には何もせず、超えない場合にはRSA署名に準じた署名を行う第1操作と、第1操作の結果に対して、モジュラスn_{i_{m}}だけ大きいほうに写像させる関数をかける第2操作と、この第2操作の結果がモジュラスn_{i_{m}}を超える場合には何もせず、超えない場合にはRSA署名に準じた署名を行う第3操作とを行う。ここで、各署名装置のRSAモジュラスのビット長がセキュリティ・パラメータκに等しいとすると、署名文u_{i_{m-1}}および署名装置i_{m}のモジュラスn_{i_{m}}は、2^{κ}より小さい数になる。第1操作では、0〜n_{i_{m}}の値をとる署名文u_{i_{m-1}}についてはRSA署名に準じた署名が行われるため、第1操作後の値は0〜n_{i_{m}}になり、他方、n_{i_{m}}〜2^{κ}の値をとる署名文u_{i_{m-1}}については何もしないので、第1操作後の値はn_{i_{m}}〜2^{κ}になる。また、第2操作では、第1操作後の値から2^{κ}をモジュラスとするn_{i_{m}}の加算を行うので、第2操作後の値も2^{κ}より小さい数になるが、第1操作後の値がn_{i_{m}}〜2^{κ}であったものは第2操作後は0〜n_{i_{m}}になる。従って、第3操作において、第2操作後の値が0〜n_{i_{m}}となるものに対してRSA署名に準じた署名を行うことで、任意の値の署名文u_{i_{m-1}}に対し、少なくとも1回はRSA署名が行われることになる。また、第3操作後の値、つまり署名値u_{i_{m}}の値と入力の署名文u_{i_{m-1}}の値とは1対1に対応するため、署名値u_{i_{m}}の値から、施された署名操作が一意に決定できるため、非特許文献1におけるような制御ビットを付加する必要がなくなる。
【発明の効果】
【００４８】
第1の効果は，署名長が署名装置の数に依存しないことである。その理由は署名前のデータと、署名後にできるデータのビット数が不変であることによる。【００４９】
第2の効果は、署名装置の順番を、署名のたびに変えることができることである。その理由は第1の効果の場合と同じで署名前のデータと、署名後にできるデータのビット数が不変であることによる。この為、各署名装置への入力が、その署名装置が何番目に署名を行うのかによらず一定であり、その為に何番目であっても同じ操作で署名ができる。【００５０】
第3の効果は，署名装置と結託した攻撃者が、経路の途中でhonestな署名装置を通っている署名文を偽造できないことにある。その理由は署名装置への入力uがいかなるものであっても、署名時に最大2回行うRSA計算の少なくとも一方でuが変化するからである。【００５１】
第4の効果は、システムの運用を始めた段階で署名装置の数mがわかっている必要はなく、署名装置の数mは運用中に動的に変わっても支障なく適用できることである。その理由は、署名装置の数がm+1台のときの署名手順は、署名装置の数がm台のときの署名手順を行った後に同様の署名操作をさらに1回行うというものであり、署名装置の数mに署名の操作方法が依存しないからである。
【図面の簡単な説明】
【００５２】
【図１】本発明の第1の実施の形態のブロック図である。
【図２】本発明の第1の実施の形態における署名装置の構成を示すブロック図である。
【図３】本発明の第1の実施の形態における署名装置の動作を示す流れ図である。
【図４】本発明の第1の実施の形態における検証装置の構成を示すブロック図である。
【図５】本発明の第1の実施の形態における検証装置の動作を示す流れ図である。
【図６】本発明の第2の実施の形態のブロック図である。
【図７】本発明の第2の実施の形態における署名装置の構成を示すブロック図である。
【図８】本発明の第2の実施の形態における署名装置の動作を示す流れ図である。
【図９】本発明の第2の実施の形態における検証装置の構成を示すブロック図である。
【図１０】本発明の第2の実施の形態における検証装置の動作を示す流れ図である。
【図１１】従来の署名装置の動作を示す流れ図である。
【符号の説明】
【００５３】
i_{1},…,i_{m-1}    署名装置
i_{1}-2,…,i_{m-1}-2    検証装置
i_{1}-3,…,i_{m-1}-3    鍵記憶装置
i_{1}-4,…,i_{m-1}-4    鍵正当性検証装置
i_{1}-5,…,i_{m-1}-5    鍵生成装置
M_{1},…, M_{m}    メッセージ
u_ {i_{0}},…, u_ {i_{m-1}}    署名文
w_ {i_{0}},…, w_ {i_{m-1}}    補助情報
【発明を実施するための最良の形態】
【００５４】
『第1の実施の形態』
図1を参照すると、本発明の第1の実施の形態は、署名装置i_{1},…,i_{m}、検証装置i_{1}-2,…,i_{m}-2、公開鍵記憶装置i_{1}-3,…,i_{m}-3、鍵正当性検証装置i_{1}-4,…,i_{m}-4、秘密鍵記憶装置i_{1}-5,…,i_{m}-5から構成される。【００５５】
図2を参照すると、署名装置i_{m}は、入力手段S1B100、T_{m}計算手段S1B103、排他的論理和計算手段S1B104、第一変換手段S1B105、全単射変換手段S1B106、第二変換手段S1B107、記憶媒体S1B108および出力手段S1B109から構成される。他の署名装置も署名装置i_{m}と同様の構成を有する。【００５６】
図4を参照すると、検証装置i_{m}-2は、入力手段V1B100、j初期化手段V1B102、j判定手段V1B103、第二変換手段V1B104、全単射変換手段V1B105、第一変換手段V1B106、T_{j}計算手段V1B107、u計算手段V1B108、j減少手段V1B109、記憶媒体V1B1010、u判定手段V1B1011、accept出力手段V1B1012およびreject出力手段V1B1013から構成される。他の検証装置も検証装置i_{m}-2と同様の構成を有する。【００５７】
本実施の形態の概略を述べる。まず、署名装置i_{1}に、署名装置i_{1}の公開鍵秘密鍵ペア、初期値u_{i_{0}}、およびメッセージM_{1}が入力される。署名装置i_{1}はu_{i_{0}}を用いてメッセージM_{1}に対する署名文u_{i_{1}}を作成する。以下順に署名装置i_{j}に、署名装置i_{j}の公開鍵秘密鍵ペア、直前の署名装置が出力した署名文u_{i_{j-1}}、およびメッセージM_{j}が入力され、署名装置i_{j}はこれら用いて署名文u_{i_{j}}を作成する。署名文u_{i_{j}}は、署名装置i_{1}がメッセージM_{1}に署名し、署名装置i_{2}がメッセージM_{2}に署名し、…、署名装置i_{j}がメッセージM_{j}に署名したことを表すデータである。【００５８】
各jに対し、検証装置i_{j}に署名装置i_{1},…,i_{j}の公開鍵とメッセージM_{1},…,M_{j-1}、および署名文u_{i_{j-1}}が入力される。すると検証装置i_{j}は署名文u_{i_{j-1}}がメッセージM_{1},…,M_{j-1}に対する、署名装置i_{1},…,i_{j-1}の秘密鍵を使って作成された署名文であるかどうかを検証する。【００５９】
本実施の形態のシステムの目標は、署名文u_{i_{m}}、すなわち署名装置i_{1}がメッセージM_{1}に署名し、署名装置i_{2}がメッセージM_{2}に署名し、…、署名装置i_{m}がメッセージM_{m}に署名したことを表すデータを作成することである。【００６０】
なお、本実施の形態のシステムの運用を始めた段階で署名装置の数mがわかっている必要はない。署名装置の数mは運用中に動的に変わってもよい。また、署名装置i_{1},…,i_{m}の動作は全て同様である。検証装置、公開鍵記憶装置、鍵正当性検証装置、秘密鍵記憶装置も全て基本的に同じ動作を行う。【００６１】
次に本実施の形態の詳細を述べる。【００６２】
署名装置i_{j}の公開鍵pk_{i}、秘密鍵sk_{i}はそれぞれ(n_{i},e_{i}) 、（p_{i_{j}}，q_{i_{j}}, d_{i_{j}}）で、次の5性質を満たすものである。
1. p_{i_{j}}，q_{i_{j}}は素数。
2. n_{i_{j}} =p_{i_{j}}q_{i_{j}}
3. n_{i_{j}}のビット長がセキュリティパラメータκに等しい。
4. p_{i_{j}}，q_{i_{j}}のビット長が同程度。
5. e_{i_{j}}はΦ(n_{i})と互いに素。
6. d_{i_{j}}=e_{i_{j}} -1 mod  Φ(n_{i})
ただし、ここでΦ(n_{i})は1以上n_{i}未満でn_{i}と互いに素な整数の個数。これらの性質を満たす(pk_{i},(sk_{i})の作り方は、例えば、非特許文献2「Alfred J. Menezes Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press.」（http://www.cacr.math.uwaterloo.ca/hac/）に記載されている。【００６３】
安全性の観点から言えば、e_{i_{j}}がΦ(n_{i})と互いに素であることを皆が確認できることが望ましい。この確認を可能にする方法としてたとえばe_{i_{j}}をn_{i}よりも大きい素数にするという方法がある。しかし、必ずしもe_{i_{j}}がこの性質を満たす必要はない。【００６４】
各j=1,…,mに対し、秘密鍵記憶装置i_{j}-5は秘密鍵sk_{i_{j}}を記憶し、さらに公開鍵記憶装置i_{j}-3は、公開鍵pk_{1},…,pk_{m}を記憶する。【００６５】
鍵正当性検証装置i_{m}-4の動作を説明する。鍵正当性検証装置i_{m}-4は、公開鍵pk_{i_{1}},…, pk_{i_{m-1}}の正当性を確認する装置である。正当性を確認するには、まず鍵記憶装置i_{m}-3からpk_{i_{1}},…, pk_{i_{m-1}}を読み込み、pk_{i_{1}},…, pk_{i_{m-1}}が全て異なることを確認する。ただしm=1の場合は何も確認しない。【００６６】
安全性の観点から言えば、e_{i_{j}}がΦ(n_{i})と互いに素であることも確認しておくことが望ましいが、この確認は省略することも可能である。【００６７】
署名装置i_{m}の動作を説明する。メッセージM_{1},…, M_{m}、および署名装置i_{1} ,…,i_{m-1}が公開鍵pk_{i_{1}},…, pk_{i_{m-1}}を使って作成したメッセージM_{1},…, M_{m-1}に対する署名文u_{i_{m-1}}が署名装置i_{m}に入力されたとき、署名装置i_{m}がメッセージM_{m}に署名する方法を、図2、図3を参照して説明する。【００６８】
署名装置i_{m}は、まず入力手段S1B101により、M_{1},…, M_{m}、pk_{i_{1}},…, pk_{i_{m}}、sk_{i_{m}}、u_{i_{m-1}}を読み込み、記憶媒体S1B108に記憶する(S1F100)。ただし、m=1の場合は、u_{i_{0}}=0が満たされているものとする。【００６９】
次に署名装置i_{m}は、u_{i_{m-1}}、M_{1},…, M_{m-1}、pk_{i_{1}},…, pk_{i_{m-1}}を検証装置i_{m}-2に送る。検証装置i_{m}-2は、署名文u_{i_{m-1}}の正当性を検証する(S1B101,S1F102)。この際、検証装置i_{m}-2は、pk_{i_{1}},…, pk_{i_{m-1}}を鍵正当性検証装置i_{m}-4に送る。鍵正当性検証装置i_{m}-4は、鍵の正当性を検証する(S1B102,S1F101)。ただしm=1の場合はu_{i_{0}}=0であることのみを確認する。【００７０】
安全性の観点から言えば、上述のu_{i_{m-1}}の検証と鍵正当性検証とを行うことが望ましいが、効率化を図るためにその何れか一方または双方の操作を省略してもよい。【００７１】
次に署名装置i_{m}は、T_{m}計算手段S1B103により、記憶媒体S1B108から必要なデータを読み込み、T_{m} = M_{1}||…||M_{m}||pk_{i_{1}}||…||pk_{i_{m}}を計算する(S1F103)。T_{m}計算手段S1B103は、計算が終わったら記憶媒体S1B108にT_{m}を書き込む。【００７２】
次に署名装置i_{m}は、排他的論理和手段S1B104により、記憶媒体S1B108から必要なデータを読み込み、U=H(T_{m})○u_{i_{m-1}}を計算し、計算結果を記憶媒体S1B108に記憶する(S1F104)。ここで、Hは入力と同じビット数のハッシュ値を出力するハッシュ関数である。【００７３】
次に署名装置i_{m}は、第一変換手段S1B105により、署名装置i_{m}に入力されたデータを記憶媒体S1B108から読み込み、まず、Uがn_{i_{m}}より小さいかどうかを判定する(S1F105)。そして、U＜n_{i_{m}}であれば、署名装置i_{m}は、第一変換手段S1B105により、v= u^{d_{i_{m}}} mod n_{i_{m}}を計算し、計算結果を記憶媒体S1B108に書き込む(S1F106)。逆にU≧n_{i_{m}}であれば、署名装置i_{m}は、第一変換手段S1B105により、v=uとし、計算結果を記憶媒体S1B108に書き込む(S1F107)。【００７４】
そして次に、署名装置i_{m}は、全単射変換手段S1B106により、記憶媒体S1B108から必要なデータを読み込み、v'=v + n_{i_{m}} mod 2^{κ}を計算し、計算結果を記憶媒体S1B108に書き込む(S1F108)。【００７５】
次に署名装置i_{m}は、第二変換手段S1B107により、記憶媒体S1B108から必要なデータを読み込み、v'がn_{i_{m}}より小さいかどうかを判定する(S1F109)。もしv'＜n_{i_{m}}ならば、署名装置i_{m}は、第二変換手段S1B107により、u_{i_{m}} = v'^{d_{i_{m}}} mod n_{i_{m}}を計算し、計算結果を記憶媒体S1B108に書き込む(S1F1010)。逆に、もしv'≧n_{i_{m}}ならば、署名装置i_{m}は、第二変換手段S1B107により、u_{i_{m}} = v'を計算し、計算結果を記憶媒体S1B108に書き込む(S1F1011)。【００７６】
そして最後に、署名装置i_{m}は、出力手段S1B109により、記憶媒体S1B108からu_{i_{m}}を読み込み、出力する(S1F1012)。【００７７】
このように、署名装置i_{m}は、入力された署名文u_{i_{m-1}}がモジュラスn_{i_{m}}を超えるかどうかを判定し、超える場合には何もせず、超えない場合にはRSA方式に準じた署名を行う第1操作を行い、この第1操作の結果に対して、モジュラスn_{i_{m}}だけ大きいほうに写像させる関数をかける第2操作を行い、この第2操作の結果がモジュラスn_{i_{m}}を超えるかどうかを判定し、超える場合には何もせず、超えない場合にはRSA方式に準じた署名を行う第3操作を行うものであり、署名文u_{i_{m-1}}の値によってはRSA署名が2度実施される冗長さはあるものの、署名値u_{i_{m}}の値によって、施された署名操作が一意に決定できるため、非特許文献1におけるような制御ビットを付加する必要がなくなる。【００７８】
次に、検証装置i_{m}-2が署名文u_{m-1}を検証する方法を図4、図5を参照して説明する。【００７９】
検証装置i_{m}-2は、まず入力手段V1B100により、公開鍵記憶装置i_{m}-3からpk_{i_{1}},…,pk_{i_{m-1}}を読み込み、さらにメッセージM_{1},…, M_{m-1}を読み込む(V1F100)。読み込んだデータは、入力手段V1B100により記憶媒体V1B1010に書き込まれる。【００８０】
次に検証装置i_{m}-2は、入力手段V1B100により、pk_{i_{1}},…,pk_{i_{m-1}}を鍵検証装置i_{m}-4に送り、公開鍵pk_{i_{1}},…,pk_{i_{m-1}}の正当性を検証してもらう(V1B101, V1F101)。【００８１】
次に検証装置i_{m}-2は、1つ前の署名装置から最初の署名装置まで遡って順に検証処理を行うために、まず、j初期化手段V1B102により、どの署名装置における署名を検証しているかを管理する変数jにm-1をセットする(V1F102)。【００８２】
次に検証装置i_{m}-2は、j判定手段V1B103により、j>0かどうかを判定する(V1F103)。【００８３】
以下、j>0の場合の検証装置i_{m}-2の動作を説明する。j>0でない場合の動作については後述する。【００８４】
次に検証装置i_{m}-2は、第二変換手段V1B104により、まず記憶媒体V1B1010から必要なデータを読み込み、u_{i_{j}}<n_{i_{j}}であるかどうかを判定する(V1F104)。【００８５】
そして、もしu_{i_{j}}<n_{i_{j}}であれば、検証装置i_{m}-2は、第二変換手段V1B104により、v'=u_{i_{j}}^{e_{i_{j}}} mod n_{i_{j}}を計算し、計算結果を記憶媒体V1B1010に書き込む(V1F105)。【００８６】
逆に、もしu_{i_{j}}<n_{i_{j}}でなければ、検証装置i_{m}-2は、第二変換手段V1B104により、v'=u_{i_{j}とし、計算結果を記憶媒体V1B1010に書き込む(V1F106)。【００８７】
次に検証装置i_{m}-2は、全単射計算手段V1B105により、記憶媒体V1B1010から必要なデータを読み込み、v=v'- n_{i_{m}} mod 2^{κ}を計算し、計算結果を記憶媒体V1B1010に書き込む(V1F107)。【００８８】
次に検証装置i_{m}-2は、第一変換手段V1B106により、記憶媒体V1B1010から必要なデータを読み込み、まずv<n_{i_{j}}であるかどうかを判定する(V1F108)。【００８９】
そして、もしv<n_{i_{j}}であれば、検証装置i_{m}-2は、第一変換手段V1B106により、U=v^{e_{i_{j}}} mod n_{i_{j}}を計算し、計算結果を記憶媒体V1B1010に書き込む(V1F109)。【００９０】
他方、もしv<n_{i_{j}}でなければ、検証装置i_{m}-2は、第一変換手段V1B106により、U=vとし、計算結果を記憶媒体V1B1010に書き込む(V1F1010)。【００９１】
次に検証装置i_{m}-2は、T_{j}計算手段V1B107により、記憶媒体V1B1010から必要なデータを読み込み、T_{j} = M_{1}||…||M_{j}||pk_{i_{1}}||…||pk_{i_{j}}を計算し、計算結果を記憶媒体V1B1010に書き込む(V1F1011)。【００９２】
検証装置i_{m}-2は次に、u計算手段V1B108により、記憶媒体V1B1010から必要なデータを読み込み、u_{i_{j-1}}=H(T_{j})○Uを計算し、計算結果を記憶媒体V1B1010に書き込む(V1F1012)。【００９３】
そして次に検証装置i_{m}-2は、j減少手段V1B109により、j=j-1とする(V1F1013)。【００９４】
そして再び検証装置i_{m}-2は、j判定手段V1B103により、j>0かどうかを判定する(V1F103)。【００９５】
もしj>0であれば、検証装置i_{m}-2は、ステップV1F104以降の処理を行う。【００９６】
もしj=0であれば、検証装置i_{m}-2は、u判定手段V1B1011により、記憶媒体V1B1010から必要なデータを読み込み、u=0であるかどうかを調べる(V1F1014)。【００９７】
そしてu=0であれば、検証装置i_{m}-2は、accept出力手段V1B1012により、検証成功を示すacceptを出力し(V1F1015)、そうでなければ、reject出力手段V1B1013により、検証失敗を示すrejectを出力する(V1F1016)。【００９８】
さて、図5の点線で囲った部分の操作をf(x), g(x), h(x), φ(x)とする。
すなわち、
f（ｘ）= x^{e_{i_{j}}} mod n_{i_{j}}    if x < n_{i_{j}}
= x    otherwise. 
g（ｘ）= x^{e_{i_{j}}} mod n_{i_{j}}    if x < n_{i_{j}}
= x    otherwise. 
φ(x)= x + n_{i_{j}} mod 2^{κ}
h(x)= g(φ(x))
とする。【００９９】
すると、図3の点線で囲った部分の操作f^{-1}(x), g^{-1} (x), h^{-1} (x), φ^{-1} (x)は、それぞれf(x), g(x), h(x), φ(x)の逆関数である。【０１００】
従って、本実施の形態における署名装置i_{m}は、u_{i_{m}}=(g_{m}^{-1}(φ^{-1}(f_{m}^{-1}(H(T_{m})○u_{i_{m-1}}))))なる計算式によって、署名文を作成していることになる。また、本実施の形態における検証装置i_{m}-2は、u_{i_{m-2}}=H(T_{m-1})○(f_{m-1}(φ(g_{m-1}(u_{i_{m-1}}))))によって、1つ前の署名装置の入力となった署名文を求
め、以下、同様の処理を最初の署名装置まで繰り返して入力の初期値を求め、求めた初期値が予め定められた初期値(本実施の形態の場合は値0)に一致するかどうかを調べていることになる。【０１０１】
次に本実施の形態の効果を説明する。【０１０２】
第1の効果は、署名長が署名装置の数に依存しないことである。その理由は、署名前のデータと、署名後にできるデータのビット数が不変であることによる。【０１０３】
第2の効果は、署名装置の順番を、署名のたびに変えることができることにある。その理由は、第1の効果の場合と同じで署名前のデータと、署名後にできるデータのビット数が不変であることによる。この為、各署名装置への入力が、その署名装置が何番目に署名を行うのかによらず一定であり、その為に何番目であっても同じ操作で署名ができる。ただし、どの順番で署名が行われたのかを、何らかの形で検証装置に通知する必要はある。【０１０４】
第3の効果は、署名装置と結託した攻撃者が、経路の途中でhonestな署名装置を通っている署名文を偽造できないことにある。その理由は、署名装置への入力uがいかなるものであっても、署名時に二回行うRSA計算の少なくとも一方でuが変化するからである。【０１０５】
第4の効果は、システムの運用を始めた段階で署名装置の数mがわかっている必要はなく、署名装置の数mは運用中に動的に変わっても支障なく適用できることである。その理由は、署名装置の数がm+1台のときの署名手順は、署名装置の数がm台のときの署名手順を行った後に同様の署名操作をさらに1回行うというものであり、署名装置の数mに署名の操作方法が依存しないからである。【０１０６】
なお、以上の第1の実施の形態では、もっとも典型的な例であるRSA関数を使って説明したが、より一般に{0,1}＾{κ}のある部分集合Xが存在して、以下の条件(1),(2)が満たされるならば、第1の実施の形態と同様に、署名者の人数に署名長が依存せずかつ安全な署名方式を実現できる。
(1)f,gがトラップドアつき一方向性置換でXがfの定義域にもｇの定義域にも含まれるものであること。
(2)φがφもφ^{-1}も多項式時間で計算できる{0,1}＾{κ}上の全単射であって、{0,1}＾{κ}＼XをXに写すものであること。
ここで、トラップドアつき一方向性置換とは、以下の4性質を満たす関数のことである。
1)fを計算するのは容易。
2)トラップドア（秘密鍵ともいう）を知らない人にはf^{-1}を計算するのは困難。
3)トラップドアを知っている人にはf^{-1}を計算するのは容易。
4)全単射である。【０１０７】
さらに一般に{0,1}＾{κ}のある部分集合Xが存在して、以下の条件(1),(2)が満たされるならば、第1の実施の形態と同様に、署名者の人数に署名長が依存せずかつ安全な署名方式を実現できる。
(1)fがトラップドアつき一方向性置換でXがｆの定義域にふくまれるものであること。
(2)かつhがトラップドアつき一方向性置換で{0,1}＾{κ}＼Xがhの定義域にふくまれるものであること。【０１０８】
『第2の実施の形態』
図6を参照すると、本発明の第2の実施の形態は、署名装置i_{1},…,i_{m}、検証装置i_{1}-2,…,i_{m}-2、公開鍵記憶装置i_{1}-3,…,i_{m}-3、鍵正当性検証装置i_{1}-4,…,i_{m}-4、秘密鍵記憶装置i_{1}-5,…,i_{m}-5から構成される。【０１０９】
図7を参照すると、署名装置i_{m}は、入力手段S1B100、T_{m}計算手段S1B103、排他的論理和計算手段S1B104、第一変換手段S1B105、全単射変換手段S1B106、第二変換手段S1B107、記憶媒体S1B108、出力手段S1B109およびwセット手段S2B100から構成される。他の署名装置も署名装置i_{m}と同様の構成を有する。【０１１０】
図9を参照すると、検証装置i_{m}-2は、入力手段V2B200、T_{m-1}計算手段V2B202、v''計算手段V2B203、第二変換手段V2B204、全単射変換手段V2B205、第一変換手段V2B206、u判定手段V2B207、accept出力手段V2B208、reject出力手段V2B209および記憶媒体V2B2010から構成される。他の検証装置も検証装置i_{m}-2と同様の構成を有する。【０１１１】
本実施の形態の概略を述べる。まず、署名装置i_{1}に、署名装置i_{1}の公開鍵秘密鍵ペア、初期値u_{i_{0}}、およびメッセージM_{1}が入力される。署名装置i_{1}はu_{i_{0}}を用いてメッセージM_{1}に対する署名文u_{i_{1}}を作成し、かつ、初期値u_{i_{0}}を補助情報w_{i_{1}}として作成し、u_{i_{1}}とw_{i_{1}}の組を出力する。次に、署名装置i_{2}に、署名装置i_{2}の公開鍵秘密鍵ペア、u_{i_{1}}とw_{i_{1}}の組、およびメッセージM_{2}が入力される。署名装置i_{2}はu_{i_{1}}を用いてメッセージM_{2}に対する署名文u_{i_{2}}を作成し、かつ、u_{i_{1}}を補助情報w_{i_{2}}として作成し、u_{i_{2}}とw_{i_{2}}の組を出力する。以下順に署名装置i_{j}に、署名装置i_{j}の公開鍵秘密鍵ペア、直前の署名装置が出力した署名文u_{i_{j-1}}と補助情報w_{i_{j-1}}、およびメッセージM_{j}が入力され、署名装置i_{j}はこれら用いて署名文u_{i_{j}}と補助情報w_{i_{j}}の組を作成する。u_{i_{j}}は、第1の実施の形態と同様の署名文であり、署名装置i_{1}がメッセージM_{1}に署名し、署名装置i_{2}がメッセージM_{2}に署名し、…、署名装置i_{j}がメッセージM_{j}に署名したことを表すデータである。【０１１２】
また、w_{i_{j}}は、署名文u_{i_{j}}の検証を簡易に行えるようにするための補助情報であり、本実施の形態の場合、署名装置i_{j}の入力となった署名文u_{i_{j-1}}そのものである。各jに対し、検証装置i_{j}に署名装置i_{1},…,i_{j}の公開鍵とメッセージM_{1},…,M_{j-1}、およびu_{i_{j-1}},w_{i_{j-1}}が入力されると、検証装置i_{j}は、u_{i_{j-1}}がメッセージM_{1},…,M_{j-1}に対する、署名装置i_{1},…,i_{j-1}の公開鍵を使って作成された署名文であるかどうかを、補助情報w_{i_{j-1}}を活用して検証する。【０１１３】
本実施の形態のシステムの目標は、第1の実施の形態と同じく、署名文u_{i_{m}}、すなわち署名装置i_{1}がメッセージM_{1}に署名し、署名装置i_{2}がメッセージM_{2}に署名し、…、署名装置i_{m}がメッセージM_{m}に署名したことを表すデータを作成することである。【０１１４】
なお、第1の実施の形態と同様に、本実施の形態のシステムにおいてもその運用を始めた段階で署名装置の数mがわかっている必要はない。署名装置の数mは運用中に動的に変わってもよい。また、署名装置i_{1},…,i_{m}の動作は全て同様である。検証装置、公開鍵記憶装置、鍵正当性検証装置、秘密鍵記憶装置も全て基本的に同じ動作を行う。【０１１５】
次に本実施の形態の詳細を、第1の実施の形態との相違点を中心に説明する。【０１１６】
署名装置i_{ｊ}の公開鍵pk_{i}、秘密鍵sk_{i}は、第1の実施の形態と同様に作成され、各j=1,…,mに対し、秘密鍵記憶装置i_{j}-5は秘密鍵sk_{i_{j}}を記憶し、さらに公開鍵記憶装置i_{j}-3は、公開鍵pk_{1},…,pk_{m}を記憶する。【０１１７】
鍵正当性検証装置の動作は第1の実施の形態と同じである。【０１１８】
メッセージM_{1},…, M_{m}、および署名装置i_{1} ,…,i_{m-1}が公開鍵 pk_{i_{1}},…, pk_{i_{m-1}}を使って作成した、メッセージM_{1},…, M_{m-1}に対する署名文u_{i_{m-1}}と補助情報w_{i_{m-1}}が署名装置i_{m}に入力されたときの、署名装置i_{m}がメッセージM_{m}に署名する方法は、補助情報を作成する手順が追加されている点で第1の実施の形態と相違し、それ以外は第1の実施の形態と同じである。これを図7、図8を参照して説明すると、本実施の形態の場合、署名装置i_{m}は、ステップS1F102の処理に続けて、wセット手段S2B100により、w_{i_{m}}=u_{i_{m-1}}を計算し、計算結果を記憶媒体S1B108に書き込む(S2F100)。記録媒体S1B108に書き込まれた補助情報w_{i_{m}}は、出力手段S1B109により、第1の実施の形態と同様の手順で作成されて記録媒体S1B108に書き込まれている署名文u_{i_{m}}と一緒に読み出され、出力される(S1F1012')。【０１１９】
次に、検証装置i_{m}-2が署名文u_{m-1}を検証する方法を図9および図10を参照して説明する。【０１２０】
検証装置i_{m}-2は、まず入力手段V2B200により、公開鍵記憶装置i_{m}-3からpk_{i_{1}},…,pk_{i_{m-1}}を読み込み、さらにメッセージM_{1},…, M_{m-1}を読み込み、記憶媒体V2B2010に保存する(V2F200)。【０１２１】
次に検証装置i_{m}-2は、入力手段V2B200により、pk_{i_{1}},…,pk_{i_{m-1}}を鍵検証装置i_{m}-4に送り、公開鍵pk_{i_{1}},…,pk_{i_{m-1}}の正当性を検証してもらう(V2F201)。【０１２２】
次に検証装置i_{m}-2は、T_{m-1}計算手段V2B202により、必要なデータを記憶媒体V2B2010から読み込み、T_{m-1} = M_{1}||…||M_{m-1}||pk_{i_{1}}||…||pk_{i_{m-1}}を計算し、計算結果のT_{m-1}を記憶媒体V2B2010に保存する（V2F202）。【０１２３】
次に検証装置i_{m}-2は、v''計算手段V2B203により、必要なデータを記憶媒体V2B2010から読み込み、v''=H(T_{m-1})○u_{i_{m-1}}を計算し、計算結果のv''を記憶媒体V2B2010に保存する(V2F203)。【０１２４】
次に検証装置i_{m}-2は、第二変換手段V2B204により、必要なデータを記憶媒体V2B2010から読み込み、v''<n_{i_{m-1}}であるかどうかを判定する(V2F204)。もしv''<n_{i_{m-1}}であれば、検証装置i_{m}-2は、第二変換手段V2B204により、v'=v''^{e_{i_{m-1}}} mod n_{i_{m-1}}を計算し、計算結果のv'を記憶媒体V2B2010に保存する(V2F205)。他方v''<n_{i_{m-1}}でなければ、検証装置i_{m}-2は、v'=v''とし、計算結果のv'を記憶媒体V2B2010に保存する(V2F206)。【０１２５】
次に検証装置i_{m}-2は、全単射変換手段V2B205により、必要なデータを記憶媒体V2B2010から読み込み、v=v' - n_{i_{m-1}} mod 2^{κ}を計算し、計算結果のvを記憶媒体V2B2010に保存する(V2F207)。【０１２６】
次に検証装置i_{m}-2は、第一変換手段V2B206により、必要なデータを記憶媒体V2B2010から読み込み、v<n_{i_{m-1}}であるかどうかを判定する(V2F208)。もしv<n_{i_{m-1}}であれば、検証装置i_{m}-2は、第一変換手段V2B206により、u _{i_{m-2}} = v^{e_{i_{m-1}}} mod n_{i_{m-1}}}を計算し、計算結果のu _{i_{m-2}}を記憶媒体V2B2010に保存する(V2F209)。他方、もしu_{i_{m-2}}<n_{i_{m-1}}でなければ、検証装置i_{m}-2はu _{i_{m-1}}}=vとし、計算結果のu _{i_{m-2}}を記憶媒体V2B2010に保存する(V2F2010)。【０１２７】
次に検証装置i_{m}-2は、u判定手段V2B2011により、必要なデータを記憶媒体V2B2010から読み込み、u_{i_{m-2}}} =w_{i_{m-1}}であるかどうかを調べる(V2F2011)。もしu_{i_{m-2}}} =w _{i_{m-1}}であれば、検証装置i_{m}-2は、accept出力手段V2B208により、acceptを出力し(V2F2012)、そうでなければ、reject出力手段V2B209により、rejectを出力する(V2F2013)。【０１２８】
次に本実施の形態の効果を説明する。【０１２９】
第1の効果は、署名長が署名装置の数に依存しないことである。その理由は、署名前のデータと、署名後にできるデータのビット数が不変であることによる。ただし、第1の実施の形態と比較すると、補助情報の分だけデータ長は長くなる。【０１３０】
第2の効果は、第1の実施の形態に比べて検証計算にかかる計算量を削減することができることである。その理由は、第1の実施の形態では、最終的に初期値を求める必要があるため既に署名を行った署名装置の数に比例した検証計算が必要なのに対し、本実施の形態では、直前の署名装置の入力となった署名文が補助情報として伝達されているため、1署名装置分の検証計算を行えばよいからである。ただし、本実施の形態は、1つ前の署名装置が信頼できるという前提が必要であるため、そのような前提なしに安全性を証明できる第1の実施の形態よりは安全性は低くなる。【０１３１】
その他、第1の実施の形態と同様の効果が奏される。【０１３２】
なお、本実施の形態では、署名文u_{i_{j}}と組になる補助情報w_{i_{j}}として、署名装置i_{j}の入力となった署名文u_{i_{j-1}}そのものとしたが、hを入力と同じビット数のハッシュ値を出力する所定のハッシュ関数とし、u_{i_{j-1}}のハッシュ値h(u_{i_{j-1}})を補助情報w_{i_{j}}としてもよい。また、本実施の形態に対しても第1の実施の形態と同様の付加変更が可能である。【０１３３】
以上本発明の実施の形態について説明したが、本発明は以上の実施の形態にのみ限定されず、その他各種の付加変更が可能である。また、本発明の署名装置および検証装置は、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態における署名装置および検証装置として機能させる。
【図１】
0004848957.tif 000002
【図２】
0004848957.tif 000003
【図３】
0004848957.tif 000004
【図４】
0004848957.tif 000005
【図５】
0004848957.tif 000006
【図６】
0004848957.tif 000007
【図７】
0004848957.tif 000008
【図８】
0004848957.tif 000009
【図９】
0004848957.tif 000010
【図１０】
0004848957.tif 000011
【図１１】
0004848957.tif 000012