(57)【要約】【課題】  ＲＳＡ問題に代表される落し戸付一方向性関数の逆関数演算の計算困難さに安全性の根拠をおく場合に、署名順番が進んでも鍵のサイズの増加を阻止する。【解決手段】  第ｉ番目の署名σｉを生成する際に、第ｉ−１番目の署名σi-1を分割し、ｋ２ビットの第２部分データσi-1,R及び残りの第１部分データσi-1,Lを得る。ここで、ｋ０ビットの乱数ｒｉを連結したときに（ｋ０＋ｋ２）ビットを越えてしまう第１部分データσi-1,Lを、署名生成関数の入力側にある２項演算の入力から外す。これにより、２項演算の計算結果ｓｉのサイズを（ｋ０＋ｋ２）ビットで一定とし、結果的にＲＳＡ署名生成関数の入力サイズ（鍵長ｋビット）を一定にする。続いて、２項演算の入力から外した第１部分データσi-1,Lを署名生成関数による署名値ｚｉに連結し、署名σｉ（＝σi-1,L‖ｚｉ）を生成する。【選択図】  図１
2005210512.tif 000002
【特許請求の範囲】
【請求項１】
他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する多重署名生成装置による多重署名方法であって、
前記第ｉ−１番目の署名σi-1を２つに分割し、ｋ２ビットの第２部分データσi-1,R及び残りの第１部分データσi-1,Lを得る工程と、
ｋ０ビットの乱数データｒｉを生成する工程と、
前記第１部分データσi-1,L 、前記第２部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを得る工程と、
前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを得る工程と、
前記第２ランダム関数値ｇｉと、前記第２部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る工程と、
前記計算結果ｓｉ及び前記第１ランダム関数値ｗｉに基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを得る工程と、
前記第１部分データσi-1,Lを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,L‖ｚｉ）を生成する工程と、
この第ｉ番目の署名σｉを出力する工程と、
を備えたことを特徴とする多重署名方法。
【請求項２】
他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する多重署名生成装置による多重署名方法であって、
前記第ｉ−１番目の署名σi-1を３つに分割し、ｋ１ビットの第１部分データσi-1,L、ｋ２ビットの第３部分データσi-1,R及び残りの第２部分データσi-1,Mを得る工程と、
ｋ０ビットの乱数データｒｉを生成する工程と、
前記第２部分データσi-1,M、前記第３部分データσi-1,R、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを得る工程と、
前記第１ランダム関数値ｗｉ及び前記第１部分データσi-1,Lの２項演算を計算し、ｋ１ビットの計算結果ｗｉ’を得る工程と、
前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを得る工程と、
前記第２ランダム関数値ｇｉと、前記第３部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る工程と、
前記計算結果ｓｉ及びｗｉ’に基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを得る工程と、
前記第２部分データσi-1,Mを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,M‖ｚｉ）を生成する工程と、
この第ｉ番目の署名σｉを出力する工程と、
を備えたことを特徴とする多重署名方法。
【請求項３】
請求項１又は請求項２に記載の多重署名生成方法において、
前記署名生成関数として、ＲＳＡ署名生成関数を用いることを特徴とする多重署名生成方法。
【請求項４】
他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する多重署名生成装置であって、
前記第ｉ−１番目の署名σi-1及び前記文書データｘを入力するための入力手段と、
前記入力された第ｉ−１番目の署名σi-1を２つに分割し、ｋ２ビットの第２部分データσi-1,R及び残りの第１部分データσi-1,Lを得る分割手段と、
ｋ０ビットの乱数データｒｉを生成する乱数生成手段と、
前記第１部分データσi-1,L 、前記第２部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段と、
前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段と、
前記第２ランダム関数値ｇｉと、前記第２部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る２項演算手段と、
前記計算結果ｓｉ及び前記第１ランダム関数値ｗｉに基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを生成する署名値生成手段と、
前記第１部分データσi-1,Lを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,L‖ｚｉ）を生成する連結手段と、
この第ｉ番目の署名σｉ及び前記文書データｘを出力する出力手段と、
を備えたことを特徴とする多重署名生成装置。
【請求項５】
請求項４に記載の多重署名生成装置において、
前記２項演算手段は、前記２項演算として排他的論理和を演算することを特徴とする多重署名生成装置。
【請求項６】
請求項４に記載の多重署名生成装置において、
前記入力手段は、ｉ＝１のとき、前記他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1として、ｋ２ビット以上の定数σ0を入力することを特徴とする多重署名生成装置。
【請求項７】
請求項４又は請求項５に記載の多重署名生成装置において、
前記入力手段に文書データｘを入力する前に、第１番目乃至第ｉ−１番目までの署名者の識別情報を含む文書データｘ’に第ｉ番目の署名者の識別情報ＩＤｉを連結し、前記入力される文書データｘを作成する識別情報連結手段を備えたことを特徴とする多重署名生成装置。
【請求項８】
第ｉ−１番目の署名σi-1を分割して得られるｋ２ビットの第２部分データσi-1,R及び残りの第１部分データσi-1,Lと、ｋ０ビットの乱数データｒｉと、前記第１部分データσi-1,L 、前記第２部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施して得られるｋ１ビットの第１ランダム関数値ｗｉと、前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施して得られる（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉと、前記第２ランダム関数値ｇｉと前記第２部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算して得られる（ｋ２＋ｋ０）ビットの計算結果ｓｉと、前記計算結果ｓｉ及び前記第１ランダム関数値ｗｉに基づくｋビットのデータに署名生成関数を施して得られるｋビットの署名値ｚｉとから作成され、前記第１部分データσi-1,Lを前記署名値ｚｉに連結して生成される第ｉ番目の署名σｉ（＝σi-1,L‖ｚｉ）及び文書データｘが入力されたとき、この多重した署名σｉの正当性を検証する多重署名検証装置であって、
前記第ｉ番目の署名σi及び前記文書データｘが記憶される記憶手段と、
前記第ｉ番目の署名σi及び前記文書データｘを前記記憶手段に入力するための入力手段と、
前記記憶手段内の第ｉ番目の署名σiを２つに分割し、ｋビットの署名値ｚｉ及び残りの第１部分データσi-1,Lを得る第１分割手段と、
前記署名値ｚｉに署名検証関数を施し、（ｋ２＋ｋ０）ビットの計算結果ｓｉ及びｋ１ビットの第１ランダム関数値ｗｉを演算する検証関数演算手段と、
前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段と、
前記第２ランダム関数値ｇｉと前記計算結果ｓｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの２項演算結果を得る２項演算手段と、
前記第１部分データσi-1,L、前記２項演算結果及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉ’を演算する第１のランダム関数演算手段と、
前記検証関数演算手段により得られた第１ランダム関数値ｗｉと前記第１のランダム関数演算手段により得られた第１ランダム関数値ｗｉ’とを互いに検証し、両者が一致したとき、第ｉ番目の署名を正当であると判定する署名検証手段と、
前記第ｉ番目の署名が正当のとき、前記２項演算結果をｋ２ビットの第２部分データσi-1,R及びｋ０ビットの乱数データｒｉに分割する第２分割手段と、
前記第１部分データσi-1,L及び第２部分データσi-1,Rを連結して第ｉ−１番目の署名σi-1を復元する署名復元手段と、
前記第ｉ−１番目の署名σi-1及び文書データｘを前記第ｉ番目の署名σi及び前記文書データｘとして前記記憶手段を更新する更新手段と、
前記更新手段による更新が完了すると、前記第１分割手段、前記検証関数演算手段、前記第２のランダム関数演算手段、前記２項演算手段、前記第１のランダム関数演算手段、前記署名検証手段、前記第２分割手段、前記署名復元手段及び前記更新手段を再実行するように制御する制御手段と、
を備えたことを特徴とする多重署名検証装置。
【請求項９】
請求項８に記載の多重署名検証装置において、
前記制御手段は、前記更新手段により更新された署名σi-1が署名σ0の場合、前記再実行の制御に代えて、この署名σ0が予め設定された署名初期値σ0と一致するか否かを検証し、両者が一致するときには、前記多重した署名σｉを受理する署名受理手段を備えたことを特徴とする多重署名検証装置。
【請求項１０】
請求項８に記載の多重署名検証装置において、
前記制御手段は、前記再実行の制御の前に、前記文書データｘから署名順番が第ｉ番目の署名者の識別情報ＩＤｉを削除し、得られた文書データｘ’を前記文書データｘに置き換える識別情報削除手段を備えたことを特徴とする多重署名検証装置。
【請求項１１】
他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する多重署名生成装置であって、
前記第ｉ−１番目の署名σi-1及び前記文書データｘを入力するための入力手段と、
前記第ｉ−１番目の署名σi-1を３つに分割し、ｋ１ビットの第１部分データσi-1,L、ｋ２ビットの第３部分データσi-1,R及び残りの第２部分データσi-1,Mを得る分割手段と、
ｋ０ビットの乱数データｒｉを生成する乱数生成手段と、
前記第２部分データσi-1,M、前記第３部分データσi-1,R、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段と、
前記第１ランダム関数値ｗｉ及び前記第１部分データσi-1,Lの２項演算を計算し、ｋ１ビットの計算結果ｗｉ’を得る第１の２項演算手段と、
前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段と、
前記第２ランダム関数値ｇｉと、前記第３部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る第２の２項演算手段と、
前記計算結果ｓｉ及びｗｉ’に基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを生成する署名値生成手段と、
前記第２部分データσi-1,Mを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,M‖ｚｉ）を生成する連結手段と、
この第ｉ番目の署名σｉを出力する出力手段と、
を備えたことを特徴とする多重署名生成装置。
【請求項１２】
請求項１１に記載の多重署名生成装置において、
前記第１及び第２の２項演算手段は、前記２項演算として排他的論理和を演算することを特徴とする多重署名生成装置。
【請求項１３】
請求項１１に記載の多重署名生成装置において、
前記入力手段は、ｉ＝１のとき、前記他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1として、（２ｋ１＋ｋ２）ビット以上の定数σ0を入力することを特徴とする多重署名生成装置。
【請求項１４】
請求項１１又は請求項１２に記載の多重署名生成装置において、
前記入力手段に文書データｘを入力する前に、第１番目乃至第ｉ−１番目までの署名者の識別情報を含む文書データｘ’に第ｉ番目の署名者の識別情報ＩＤｉを連結し、前記入力される文書データｘを作成する識別情報連結手段を備えたことを特徴とする多重署名生成装置。
【請求項１５】
第ｉ−１番目の署名σi-1を分割して得られるｋ１ビットの第１部分データσi-1,L、ｋ２ビットの第３部分データσi-1,R及び残りの第２部分データσi-1,Mと、ｋ０ビットの乱数データｒｉと、前記第２部分データσi-1,M、前記第３部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施して得られるｋ１ビットの第１ランダム関数値ｗｉと、前記第１ランダム関数値ｗｉと前記第１部分データσi-1,Lとの２項演算を計算して得られるｋ１ビットの計算結果ｗｉ’と、前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施して得られる（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉと、前記第２ランダム関数値ｇｉと前記第３部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算して得られる（ｋ２＋ｋ０）ビットの計算結果ｓｉと、前記計算結果ｓｉ及びｗｉ’に基づくｋビットのデータに署名生成関数を施して得られるｋビットの署名値ｚｉとから作成され、前記第２部分データσi-1,Mを前記署名値ｚｉに連結して生成される第ｉ番目の署名σｉ（＝σi-1,M‖ｚｉ）及び文書データｘが入力されたとき、この多重した署名σｉの正当性を検証する多重署名検証装置であって、
前記第ｉ番目の署名σi及び前記文書データｘが記憶される記憶手段と、
前記第ｉ番目の署名σi及び前記文書データｘを前記記憶手段に入力するための入力手段と、
前記記憶手段内の第ｉ番目の署名σiを２つに分割し、ｋビットの署名値ｚｉ及び｝残りの第２部分データσi-1,Mを得る第１分割手段と、
前記署名値ｚｉに署名検証関数を施し、（ｋ２＋ｋ０）ビットの計算結果ｓｉ及びｋ１ビットの計算結果ｗｉ’を演算する検証関数演算手段と、
前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段と、
前記第２ランダム関数値ｇｉと前記計算結果ｓｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの２項演算結果を得る第１の２項演算手段と、
前記２項演算結果をｋ２ビットの第３部分データσi-1,R及びｋ０ビットの乱数データｒｉに分割する第２分割手段と、
前記第２部分データσi-1,M、前記２項演算結果及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段と、
前記検証関数演算手段により得られた計算結果ｗｉ’と前記第１のランダム関数演算手段により得られた第１ランダム関数値ｗｉとの２項演算を計算し、ｋ１ビットの第１部分データσi-1,Lを得る第２の２項演算手段と、
前記第１部分データσi-1,L、前記第２部分データσi-1,M及び前記第３部分データσi-1,Rを連結して第ｉ−１番目の署名σi-1を復元する署名復元手段と、
前記第ｉ−１番目の署名σi-1及び文書データｘを前記第ｉ番目の署名σi及び前記文書データｘとして前記記憶手段を更新する更新手段と、
前記更新手段による更新が完了すると、前記第１分割手段、前記検証関数演算手段、前記第２のランダム関数演算手段、前記第１の２項演算手段、前記第２分割手段、前記第１のランダム関数演算手段、前記第２の２項演算手段、前記署名復元手段及び前記更新手段を再実行するように制御する制御手段と、
前記制御手段により署名順番ｉ＝２で前記第２の２項演算手段を再実行したとき、当該第２の２項演算手段により得られた第１部分データσ1,Lが予め設定された値と一致するか否かを検証し、両者が不一致のときには、前記多重した署名σｉを棄却する署名棄却手段と、
前記制御手段により署名順番ｉ＝１で前記第２の２項演算手段を再実行したとき、当該第２の２項演算手段により得られた第１部分データσ0,Lが予め設定された部分初期値と一致するか否かを検証し、両者が一致するときには、前記多重した署名σｉを受理する署名受理手段と、
を備えたことを特徴とする多重署名検証装置。
【請求項１６】
請求項１５に記載の多重署名検証装置において、
前記制御手段は、前記再実行の制御の前に、前記文書データｘから署名順番が第ｉ番目の署名者の識別情報ＩＤｉを削除し、得られた文書データｘ’を前記文書データｘに置き換える識別情報削除手段を備えたことを特徴とする多重署名検証装置。
【請求項１７】
他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する多重署名生成装置のコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記第ｉ−１番目の署名σi-1及び前記文書データｘをメモリに入力するための入力手段、
前記メモリ内の第ｉ−１番目の署名σi-1を２つに分割し、ｋ２ビットの第２部分データσi-1,R及び残りの第１部分データσi-1,Lを得る分割手段、
ｋ０ビットの乱数データｒｉを生成する乱数生成手段、
前記第１部分データσi-1,L 、前記第２部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段、
前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段、
前記第２ランダム関数値ｇｉと、前記第２部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る２項演算手段、
前記計算結果ｓｉ及び前記第１ランダム関数値ｗｉに基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを生成する署名値生成手段、
前記第１部分データσi-1,Lを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,L‖ｚｉ）を生成する連結手段、
この第ｉ番目の署名σｉ及び前記文書データｘを出力する出力手段、
として機能させるためのプログラム。
【請求項１８】
請求項１７に記載のプログラムにおいて、
前記２項演算手段としては、２項演算として排他的論理和を演算する機能を実現させることを特徴とするプログラム。
【請求項１９】
請求項１７に記載のプログラムにおいて、
前記入力手段としては、ｉ＝１のとき、前記他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1として、ｋ２ビット以上の定数σ0を入力する機能を実現させることを特徴とするプログラム。
【請求項２０】
請求項１７又は請求項１８に記載のプログラムにおいて、
前記コンピュータを、
前記入力手段に文書データｘを入力する前に、第１番目乃至第ｉ−１番目までの署名者の識別情報を含む文書データｘ’に第ｉ番目の署名者の識別情報ＩＤｉを連結し、前記入力される文書データｘを作成する識別情報連結手段、
として機能させるためのプログラム。
【請求項２１】
第ｉ−１番目の署名σi-1を分割して得られるｋ２ビットの第２部分データσi-1,R及び残りの第１部分データσi-1,Lと、ｋ０ビットの乱数データｒｉと、前記第１部分データσi-1,L 、前記第２部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施して得られるｋ１ビットの第１ランダム関数値ｗｉと、前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施して得られる（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉと、前記第２ランダム関数値ｇｉと前記第２部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算して得られる（ｋ２＋ｋ０）ビットの計算結果ｓｉと、前記計算結果ｓｉ及び前記第１ランダム関数値ｗｉに基づくｋビットのデータに署名生成関数を施して得られるｋビットの署名値ｚｉとから作成され、前記第１部分データσi-1,Lを前記署名値ｚｉに連結して生成される第ｉ番目の署名σｉ（＝σi-1,L‖ｚｉ）及び文書データｘが入力されたとき、この多重した署名σｉの正当性を検証する多重署名検証装置のコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記第ｉ番目の署名σi及び前記文書データｘをメモリに入力するための入力手段、
前記メモリ内の第ｉ番目の署名σiを２つに分割し、ｋビットの署名値ｚｉ及び残りの第１部分データσi-1,Lを得る第１分割手段、
前記署名値ｚｉに鍵長ｋビットの署名検証関数を施し、（ｋ２＋ｋ０）ビットの計算結果ｓｉ及びｋ１ビットの第１ランダム関数値ｗｉを演算する検証関数演算手段、
前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段、
前記第２ランダム関数値ｇｉと前記計算結果ｓｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの２項演算結果を得る２項演算手段、
前記第１部分データσi-1,L、前記２項演算結果及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉ’を演算する第１のランダム関数演算手段、
前記検証関数演算手段により得られた第１ランダム関数値ｗｉと前記第１のランダム関数演算手段により得られた第１ランダム関数値ｗｉ’とを互いに検証し、両者が一致したとき、第ｉ番目の署名を正当であると判定する署名検証手段、
前記第ｉ番目の署名が正当のとき、前記２項演算結果をｋ２ビットの第2部分データσi-1,R及びｋ０ビットの乱数データｒｉに分割する第２分割手段、
前記第１部分データσi-1,L及び第２部分データσi-1,Rを連結して第ｉ−１番目の署名σi-1を復元する署名復元手段、
前記第ｉ−１番目の署名σi-1及び文書データｘを前記第ｉ番目の署名σi及び前記文書データｘとして前記メモリを更新する更新手段、
前記更新手段による更新が完了すると、前記第１分割手段、前記検証関数演算手段、前記第２のランダム関数演算手段、前記２項演算手段、前記第１のランダム関数演算手段、前記署名検証手段、前記第２分割手段、前記署名復元手段及び前記更新手段を再実行するように制御する制御手段、
として機能させるためのプログラム。
【請求項２２】
請求項２１に記載のプログラムにおいて、
前記制御手段は、前記更新手段により更新された署名σi-1が署名σ0の場合、前記再実行の制御に代えて、この署名σ0が予め設定された署名初期値σ0と一致するか否かを検証し、両者が一致するときには、前記多重した署名σｉを受理する署名受理手段を含むことを特徴とするプログラム。
【請求項２３】
請求項２１に記載のプログラムにおいて、
前記制御手段は、前記再実行の制御の前に、前記文書データｘから署名順番が第ｉ番目の署名者の識別情報ＩＤｉを削除し、得られた文書データｘ’を前記文書データｘに置き換える識別情報削除手段を含むことを特徴とするプログラム。
【請求項２４】
他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する多重署名生成装置のコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記第ｉ−１番目の署名σi-1及び前記文書データｘをメモリに入力するための入力手段、
前記メモリ内の第ｉ−１番目の署名σi-1を３つに分割し、ｋ１ビットの第１部分データσi-1,L、ｋ２ビットの第３部分データσi-1,R及び残りの第２部分データσi-1,Mを得る分割手段、
ｋ０ビットの乱数データｒｉを生成する乱数生成手段、
前記第２部分データσi-1,M、前記第３部分データσi-1,R、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段、
前記第１ランダム関数値ｗｉ及び前記第１部分データσi-1,Lの２項演算を計算し、ｋ１ビットの計算結果ｗｉ’を得る第１の２項演算手段、
前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段、
前記第２ランダム関数値ｇｉと、前記第３部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る第２の２項演算手段、
前記計算結果ｓｉ及びｗｉ’に基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを生成する署名値生成手段、
前記第２部分データσi-1,Mを前記署名値ｚｉに連結し、ビットの第ｉ番目の署名σｉ（＝σi-1,M‖ｚｉ）を生成する連結手段、
この第ｉ番目の署名σｉを出力する出力手段、
として機能させるためのプログラム。
【請求項２５】
請求項２４に記載のプログラムにおいて、
前記第１及び第２の２項演算手段としては、前記２項演算として排他的論理和を演算する機能を実現させることを特徴とするプログラム。
【請求項２６】
請求項２４に記載のプログラムにおいて、
前記入力手段としては、ｉ＝１のとき、前記他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1として、（２ｋ１＋ｋ２）ビット以上の定数σ0を入力する機能を実現させることを特徴とするプログラム。
【請求項２７】
請求項２４又は請求項２５に記載のプログラムにおいて、
前記コンピュータを、
前記入力手段に文書データｘを入力する前に、第１番目乃至第ｉ−１番目までの署名者の識別情報を含む文書データｘ’に第ｉ番目の署名者の識別情報ＩＤｉを連結し、前記入力される文書データｘを作成する識別情報連結手段、
として機能させるためのプログラム。
【請求項２８】
第ｉ−１番目の署名σi-1を分割して得られるｋ１ビットの第１部分データσi-1,L、ｋ２ビットの第３部分データσi-1,R及び残りの第２部分データσi-1,Mと、ｋ０ビットの乱数データｒｉと、前記第２部分データσi-1,M、前記第３部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施して得られるｋ１ビットの第１ランダム関数値ｗｉと、前記第１ランダム関数値ｗｉと前記第１部分データσi-1,Lとの２項演算を計算して得られるｋ１ビットの計算結果ｗｉ’と、前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施して得られる（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉと、前記第２ランダム関数値ｇｉと前記第３部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算して得られる（ｋ２＋ｋ０）ビットの計算結果ｓｉと、前記計算結果ｓｉ及びｗｉ’に基づくｋビットのデータに署名生成関数を施して得られるｋビットの署名値ｚｉとから作成され、前記第２部分データσi-1,Mを前記署名値ｚｉに連結して生成される第ｉ番目の署名σｉ（＝σi-1,M‖ｚｉ）及び文書データｘが入力されたとき、この多重した署名σｉの正当性を検証する多重署名検証装置のコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記第ｉ番目の署名σi及び前記文書データｘをメモリに入力するための入力手段、
前記メモリ内の第ｉ番目の署名σiを２つに分割し、ｋビットの署名値ｚｉ及び｝残りの第２部分データσi-1,Mを得る第１分割手段、
前記署名値ｚｉに署名検証関数を施し、（ｋ２＋ｋ０）ビットの計算結果ｓｉ及びｋ１ビットの計算結果ｗｉ’を演算する検証関数演算手段、
前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段、
前記第２ランダム関数値ｇｉと前記計算結果ｓｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの２項演算結果を得る第１の２項演算手段、
前記２項演算結果をｋ２ビットの第３部分データσi-1,R及びｋ０ビットの乱数データｒｉに分割する第２分割手段、
前記第２部分データσi-1,M、前記２項演算結果及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段、
前記検証関数演算手段により得られた計算結果ｗｉ’と前記第１のランダム関数演算手段により得られた第１ランダム関数値ｗｉとの２項演算を計算し、ｋ１ビットの第１部分データσi-1,Lを得る第２の２項演算手段、
前記第１部分データσi-1,L、前記第２部分データσi-1,M及び前記第３部分データσi-1,Rを連結して第ｉ−１番目の署名σi-1を復元する署名復元手段、
前記第ｉ−１番目の署名σi-1及び文書データｘを前記第ｉ番目の署名σi及び前記文書データｘとして前記記憶手段を更新する更新手段、
前記更新手段による更新が完了すると、前記第１分割手段、前記検証関数演算手段、前記第２のランダム関数演算手段、前記第１の２項演算手段、前記第２分割手段、前記第１のランダム関数演算手段、前記第２の２項演算手段、前記署名復元手段及び前記更新手段を再実行するように制御する制御手段、
前記制御手段により署名順番ｉ＝２で前記第２の２項演算手段を再実行したとき、当該第２の２項演算手段により得られた第１部分データσ1,Lが予め設定された値と一致するか否かを検証し、両者が不一致のときには、前記多重した署名σｉを棄却する署名棄却手段、
前記制御手段により署名順番ｉ＝１で前記第２の２項演算手段を再実行したとき、当該第２の２項演算手段により得られた第１部分データσ0,Lが予め設定された部分初期値と一致するか否かを検証し、両者が一致するときには、前記多重した署名σｉを受理する署名受理手段、
として機能させるためのプログラム。
【請求項２９】
請求項２８に記載のプログラムにおいて、
前記制御手段は、前記再実行の制御の前に、前記文書データｘから署名順番が第ｉ番目の署名者の識別情報ＩＤｉを削除し、得られた文書データｘ’を前記文書データｘに置き換える識別情報削除手段を含むことを特徴とするプログラム。
【請求項３０】
それぞれ他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1に基づいて、文書データｘに対する第ｉ番目の署名σiを生成する機能を有するＮ台（Ｎ＝１，２，…，ｉ，…，Ｎ−１，Ｎ）の多重署名生成装置と、１台の多重署名検証装置とを備えた多重署名システムであって、
前記各多重署名生成装置は、
前記第ｉ−１番目の署名σi-1及び前記文書データｘを入力するための入力手段と、
前記入力された第ｉ−１番目の署名σi-1を２つに分割し、ｋ２ビットの第２部分データσi-1,R及び残りの第１部分データσi-1,Lを得る分割手段と、
ｋ０ビットの乱数データｒｉを生成する乱数生成手段と、
前記第１部分データσi-1,L 、前記第２部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段と、
前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段と、
前記第２ランダム関数値ｇｉと、前記第２部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る２項演算手段と、
前記計算結果ｓｉ及び前記第１ランダム関数値ｗｉに基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを生成する署名値生成手段と、
前記第１部分データσi-1,Lを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,L‖ｚｉ）を生成する連結手段と、
この第ｉ番目の署名σｉ及び前記文書データｘを出力する出力手段と、
を備えたことを特徴とする多重署名システム。
【請求項３１】
請求項３０に記載の多重署名システムにおいて、
前記多重署名検証装置は、
前記第ｉ番目の署名σi及び前記文書データｘが記憶される記憶手段と、
前記第ｉ番目の署名σi及び前記文書データｘを前記記憶手段に入力するための入力手段と、
前記記憶手段内の第ｉ番目の署名σiを２つに分割し、ｋビットの署名値ｚｉ及び残りの第１部分データσi-1,Lを得る第１分割手段と、
前記署名値ｚｉに署名検証関数を施し、（ｋ２＋ｋ０）ビットの計算結果ｓｉ及びｋ１ビットの第１ランダム関数値ｗｉを演算する検証関数演算手段と、
前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段と、
前記第２ランダム関数値ｇｉと前記計算結果ｓｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの２項演算結果を得る２項演算手段と、
前記第１部分データσi-1,L、前記２項演算結果及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉ’を演算する第１のランダム関数演算手段と、
前記検証関数演算手段により得られた第１ランダム関数値ｗｉと前記第１のランダム関数演算手段により得られた第１ランダム関数値ｗｉ’とを互いに検証し、両者が一致したとき、第ｉ番目の署名を正当であると判定する署名検証手段と、
前記第ｉ番目の署名が正当のとき、前記２項演算結果をｋ２ビットの第２部分データσi-1,R及びｋ０ビットの乱数データｒｉに分割する第２分割手段と、
前記第１部分データσi-1,L及び第２部分データσi-1,Rを連結して第ｉ−１番目の署名σi-1を復元する署名復元手段と、
前記第ｉ−１番目の署名σi-1及び文書データｘを前記第ｉ番目の署名σi及び前記文書データｘとして前記記憶手段を更新する更新手段と、
前記更新手段による更新が完了すると、前記第１分割手段、前記検証関数演算手段、前記第２のランダム関数演算手段、前記２項演算手段、前記第１のランダム関数演算手段、前記署名検証手段、前記第２分割手段、前記署名復元手段及び前記更新手段を再実行するように制御する制御手段と、
を備えたことを特徴とする多重署名システム。
【請求項３２】
それぞれ他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する機能を有するＮ台（Ｎ＝１，２，…，ｉ，…，Ｎ−１，Ｎ）の多重署名生成装置と、１台の多重署名検証装置とを備えた多重署名システムであって、
前記各多重署名生成装置は、
前記第ｉ−１番目の署名σi-1及び前記文書データｘを入力するための入力手段と、
前記第ｉ−１番目の署名σi-1を３つに分割し、ｋ１ビットの第１部分データσi-1,L、ｋ２ビットの第３部分データσi-1,R及び残りの第２部分データσi-1,Mを得る分割手段と、
ｋ０ビットの乱数データｒｉを生成する乱数生成手段と、
前記第２部分データσi-1,M、前記第３部分データσi-1,R、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段と、
前記第１ランダム関数値ｗｉ及び前記第１部分データσi-1,Lの２項演算を計算し、ｋ１ビットの計算結果ｗｉ’を得る第１の２項演算手段と、
前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段と、
前記第２ランダム関数値ｇｉと、前記第３部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る第２の２項演算手段と、
前記計算結果ｓｉ及びｗｉ’に基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを生成する署名値生成手段と、
前記第２部分データσi-1,Mを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,M‖ｚｉ）を生成する連結手段と、
この第ｉ番目の署名σｉを出力する出力手段と、
を備えたことを特徴とする多重署名システム。
【請求項３３】
請求項３２に記載の多重署名システムにおいて、
前記多重署名検証装置は、
前記第ｉ番目の署名σi及び前記文書データｘが記憶される記憶手段と、
前記第ｉ番目の署名σi及び前記文書データｘを前記記憶手段に入力するための入力手段と、
前記記憶手段内の第ｉ番目の署名σiを２つに分割し、ｋビットの署名値ｚｉ及び｝残りの第２部分データσi-1,Mを得る第１分割手段と、
前記署名値ｚｉに署名検証関数を施し、（ｋ２＋ｋ０）ビットの計算結果ｓｉ及びｋ１ビットの計算結果ｗｉ’を演算する検証関数演算手段と、
前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを演算する第２のランダム関数演算手段と、
前記第２ランダム関数値ｇｉと前記計算結果ｓｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの２項演算結果を得る第１の２項演算手段と、
前記２項演算結果をｋ２ビットの第３部分データσi-1,R及びｋ０ビットの乱数データｒｉに分割する第２分割手段と、
前記第２部分データσi-1,M、前記２項演算結果及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを演算する第１のランダム関数演算手段と、
前記検証関数演算手段により得られた計算結果ｗｉ’と前記第１のランダム関数演算手段により得られた第１ランダム関数値ｗｉとの２項演算を計算し、ｋ１ビットの第１部分データσi-1,Lを得る第２の２項演算手段と、
前記第１部分データσi-1,L、前記第２部分データσi-1,M及び前記第３部分データσi-1,Rを連結して第ｉ−１番目の署名σi-1を復元する署名復元手段と、
前記第ｉ−１番目の署名σi-1及び文書データｘを前記第ｉ番目の署名σi及び前記文書データｘとして前記記憶手段を更新する更新手段と、
前記更新手段による更新が完了すると、前記第１分割手段、前記検証関数演算手段、前記第２のランダム関数演算手段、前記第１の２項演算手段、前記第２分割手段、前記第１のランダム関数演算手段、前記第２の２項演算手段、前記署名復元手段及び前記更新手段を再実行するように制御する制御手段と、
前記制御手段により署名順番ｉ＝２で前記第２の２項演算手段を再実行したとき、当該第２の２項演算手段により得られた第１部分データσ1,Lが予め設定された値と一致するか否かを検証し、両者が不一致のときには、前記多重した署名σｉを棄却する署名棄却手段と、
前記制御手段により署名順番ｉ＝１で前記第２の２項演算手段を再実行したとき、当該第２の２項演算手段により得られた第１部分データσ0,Lが予め設定された部分初期値と一致するか否かを検証し、両者が一致するときには、前記多重した署名σｉを受理する署名受理手段と、
を備えたことを特徴とする多重署名システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の署名者がある文書に対して順次署名生成処理を行うことで１つの署名を生成する多重署名方法、装置、プログラム及びシステムに関する。
【背景技術】
【０００２】
一般に、暗号方法は共通鍵暗号方式と公開鍵暗号方式との二種類に類別できる。公開鍵暗号方式は、共通鍵方式で問題となる鍵配送を不要とする利点がある。
【０００３】
例えば公開鍵暗号方式においては、各利用者Ａ，Ｂ，…は、公開鍵と秘密鍵との組を生成し、公開鍵を公開簿に登録する。ここで、各利用者Ａ，Ｂ，…は利用者の総数とは無関係に１組の鍵の組のみを用意すればよい。利用時には、例えば利用者Ａは、公開簿内の利用者Ｂの公開鍵を用いて暗号文を生成し、この暗号文を利用者Ｂに送信する。利用者Ｂは、受信した暗号文を自己の秘密鍵で復号する。このように、公開鍵暗号方式は、利用者Ａ，Ｂ間の鍵配送を不要としている。代表的な公開鍵暗号方式として、ＲＳＡ(Rivest-Shamir-Adleman)暗号、ＥｌＧａｍａｌ暗号、楕円曲線暗号などが挙げられる。
【０００４】
以上のような公開鍵暗号方式は、落し戸付一方向性関数を利用している。落し戸付一方向性関数とは、ある向きの計算が容易に実行可能であるのに対し、逆向きの計算が秘密情報無しでは実行困難であるような関数である。
【０００５】
すなわち、公開鍵暗号方式の落し戸付一方向性関数は、公開簿内の公開鍵により、任意の利用者にある向きの計算（暗号文生成）を容易に実行可能とする性質と、各利用者が秘密鍵を保存することにより、第三者には逆向きの計算（暗号文復号）を実行困難とする性質とをもっている。
【０００６】
この落し戸付一方向性関数の性質を暗号方式と逆向きの使い方をすることで、署名方式が実現される。署名方式においては、秘密情報を持つ署名者のみが、第三者に検証可能な署名を生成できる。例えば各利用者Ａ，Ｂ，…は、公開鍵と秘密鍵との組を生成し、公開鍵を公開簿に登録する。利用時には、例えば利用者Ａは、自己の秘密鍵を用いて文書から署名を生成し、文書と署名を利用者Ｂに送信する。利用者Ｂは、署名と文書に対して、公開簿内の利用者Ａの公開鍵を作用させて署名の正当性を検証する。代表的な署名方式としては、ＲＳＡ署名、ＤＳＡ(Digital Signature Algorithm)、ＥＣＤＳＡ(Elliptic Curve Digital Signature Algorithm)などがある。
【０００７】
かかる署名方式を応用した技術として多重署名方式がある。多重署名方式とは、ある文書に対して複数の署名者が順次署名生成処理を行い、１つの署名を生成する方式である。多重署名方式は、例えば、ある組織内で文書を回覧して順次承認印を押すというシステムを電子的に実現する技術と考えられる。
【０００８】
多重署名方式と同様の効果をもたらす技術としては、ある文書に対して各署名者がそれぞれ署名を生成し、得られた各署名を連結する連結署名方式が考えられる。ここで、多重署名方式とは、生成する多重署名のサイズを、連結署名方式により得られる連結署名のサイズよりも小さくし得る方式をいう。
【０００９】
ここで、多重署名方式と連結署名方式の概念を図１０を用いて説明する。図１０（ａ）は多重署名方式の概念を示し、図１０（ｂ）は連結署名方式の概念を示す。
【００１０】
図１０（ａ）では、１番目の署名者であるユーザ１が文書ｘ に対する署名１を生成した後、２番目の署名者であるユーザ２に文書ｘと署名１を送る。 ユーザ２は文書ｘに対する署名として、署名１を利用して“署名１・２”を生成する。ここで、“署名１・２”はユーザ１，２が共に文書ｘを承認した旨を保証する署名であり、図１０（ｂ）に示す如き、ユーザ１の署名１と、ユーザ２の署名２とを連結したデータよりもサイズを小さくしている。以後、同様の作業をＮ番目の署名者であるユーザＮまで行い、“多重署名１・２…Ｎ”を生成する。
【００１１】
また、“多重署名１・２…Ｎ”は、図１１に示すように、正当性が検証される。ここで、多重署名の検証用装置は、文書ｘと“多重署名１…Ｎ”に対し、多重署名生成時の公開鍵１,…,Ｎに基づいて検証処理を実行し、その結果に応じて多重署名を受理又は棄却する。
【００１２】
このような多重署名方式には、幾つかの付加機能が提案されている。代表的な機能として、文書可変性(Message Flexibility)、署名順番可変性(Order Flexibility)、署名順番検証可能性(Order Verifiability)がある。ここで、文書可変性とは、複数のユーザが文書を回覧する際に、文書を更新又は変更しながら多重署名を生成できる性質をいう。
【００１３】
例えば図１２に示すように、署名順番が１番目のユーザ１は、文書ｘ１に対して署名１を生成する。次に、署名順番が２番目のユーザ２は、文書ｘ１を更新又は変更し、差分情報としての文書ｘ２を得ると、文書ｘ１と文書ｘ２に対し、署名１を利用して“署名１・２”を生成する。ここで、“署名１・２”は、ユーザ１が文書ｘ１を承認した旨と、ユーザ２が文書ｘ１,ｘ２を承認した旨とを保証する署名である。
【００１４】
以下、同様にして、署名順番がＮ番の署名者であるユーザＮまで順次、文書ｘ１の更新又は変更と署名生成とが実行され、“多重署名１…Ｎ”が得られる。
【００１５】
署名順番可変性とは、署名生成の段階まで署名順番を自由に変更できる性質をいう。さらに、署名順番検証可能性とは、多重署名の検証処理において、署名を生成した署名者の順番が検証可能である性質をいう。例えば、ある多重署名方式が署名順番検証可能であるとき、Ｎ人の署名者により生成された多重署名が受理されると、検証者は、２番目の署名者が、文書を承認したことと、１番目の署名者の署名処理を承認したことと、を確認できる。本明細書中の多重署名方式は、文書可変性・署名順番可変性・署名順番検証可能性を備えているものとする。
【００１６】
一方、多重署名方式には、受動的な攻撃方法と能動的な攻撃方法が存在する。受動的な攻撃方法とは、攻撃者が公開情報のみを利用し、任意の文書に対する多重署名を偽造する方法である。能動的な攻撃方法とは、公開情報を利用し、任意の文書に対する多重署名を偽造する過程において、次の条件（i）〜（iii）を満たすときをいう。
【００１７】
（i）他の署名者の公開鍵を基に自らの公開鍵又は公開鍵と秘密鍵の組を作り、自ら正規の署名者として多重署名システムに参加できる。  
（ii）何人かの署名者と結託して当該署名者の秘密鍵を受け取ることができる。  
（iii）任意の文書の多重署名を任意の正規の署名者に生成してもらうことができる。
【００１８】
また、能動的な攻撃方法において、攻撃者がなりすましている署名者、及び攻撃者に結託している署名者を不正な署名者と呼ぶ。攻撃者が出力した署名が偽造署名であるとは、署名に関与したと考えられる署名者のグループのうち、少なくとも１人の署名者が不正な署名者でなく、署名に対応した文書に対して署名生成依頼を受けていないときをいう。
【００１９】
また、能動的な攻撃方法のうち、特に、鍵生成時に他の署名者の公開鍵を用いて自らの鍵を設定し、署名者の秘密鍵を用いずに多重署名を生成する方法が適応的内部者攻撃（Adaptive Insider Attack）として知られている。
【００２０】
このような能動的攻撃方法は、受動的攻撃方法よりも強力な攻撃方法である。よって、能動的攻撃方法に対しても安全な多重署名方法を構成することは、より強い安全性を保証できることを意味する。
【００２１】
この種の安全性に関し、多重署名方式は、第１の方式及び第２の方式の２通りに分類される。第１の方式は、離散対数問題の計算困難性を安全性の根拠として、ゼロ知識証明の概念により安全性証明が行われる方式である。代表的な方式としては、太田-岡本方式、及びMicali-太田-Reyzin方式がある。これら第１の方式は、多重署名のサイズが署名者の人数に依存せず１人の署名者による署名のサイズと同じであり、署名検証処理コストを抑制可能である、などの特徴がある。しかし、第１の方式の安全性は、ゼロ知識対話証明に基づくため、帰着の効率が悪く、緊密な安全性を有していない。ここで、緊密とは、ある問題を解く計算困難さと、別の問題を解く計算困難さの間の乖離度をいう。
【００２２】
一般に、多重署名方式の安全性を示すには、多重署名方式を破る問題を落し戸付一方向性関数の一方向性を破る問題に帰着させる。すなわち、多重署名方式を破ることができれば、落し戸付一方向性関数の一方向性を破ることができることを示すことで、多重署名方式の安全性を証明する。
【００２３】
詳しくは、多重署名方式を破ることができれば、高い確率で落し戸付一方向性関数の一方向性を破ることができることを示せるとき、当該多重署名方式を破る困難さは離散対数問題やＲＳＡ問題に代表される落し戸付一方向性関数の一方向性を破る困難さと同等と考えられる。このとき、多重署名方式は落し戸付一方向性関数の一方向性に対して緊密な安全性をもつといえる。
【００２４】
逆に、多重署名方式を破ることができても、低い確率でしか落し戸付一方向性関数の一方向性を破ることができないとき、多重署名方式は落し戸付一方向性関数の一方向性に対して緊密な安全性をもっていないという。
【００２５】
ここで、ある計算困難な問題を安全性の根拠とする２つの方式があり、一方が計算困難な問題に対して緊密な安全性をもち、他方が緊密な安全性を持たない場合を考える。この場合、緊密な安全性を持たない方式は、緊密な安全性をもつ方式と同等の安全性を保証するためには、より大きなサイズの鍵を用い、計算コストと保存領域を犠牲にする問題がある。上述した第１の方式はこれに該当する。
【００２６】
一方、多重署名方式の分類のうち、第２の方式は緊密な安全性を有するため、第１の方式の問題を解決するものとなっている。詳しくは、第２の方式は、素因数分解問題の計算困難さを安全性の根拠とする方式である。代表例としては、ＲＳＡ問題の計算困難さを安全性の根拠とする見富-宮地方式（例えば、非特許文献１参照。）及び河内-多田方式（例えば、非特許文献２参照。）がある。
【００２７】
ここで、見富らの方式は、図１３に示すように、第ｉ番目の署名者が文書ｘにハッシュ関数Ｈｉを施し、得られたハッシュ値と前回の署名σi-1との排他的論理和をＲＳＡ署名関数に入力し、ｉ番目の署名σｉを得る方式である。
【００２８】
また、河内らの方式は、図１４に示すように、第ｉ番目の署名者が文書ｘ、前回の署名σi-1及び乱数ｒｉに第１のハッシュ関数Ｈｉを施し、得られた第１ハッシュ値ｗｉに第２のハッシュ関数Ｇｉを施し、第２ハッシュ値を得る。次に、第２ハッシュ値と、前回の署名σi-1及び乱数ｒｉとの排他的論理和を演算し、演算結果ｓｉを得る。更に、この演算結果ｓｉと第１ハッシュ値ｗｉとをＲＳＡ関数に入力し、ｉ番目の署名σｉを得る方式である。
【００２９】
いずれにしても、これら第２の方式は、安全性がゼロ知識対話証明に基づく第１の方式に比べ、ＲＳＡ問題の計算困難さに対して緊密な安全性を有している。
【００３０】
しかしながら、見富らの方式が有する安全性は、ＲＳＡ問題の計算困難さに対して十分に緊密ではない。さらに、見富らの方式は署名者の署名鍵のサイズを署名順序が進むにつれて大きく取らなければならず、署名者の署名順番が限定される、署名鍵のサイズの増加に伴って計算量が増加する、などの問題がある。さらに、署名者の署名順番の制限を無くすには各署名者が異なるサイズの鍵を複数保存・登録しなければならない、という問題がある。
【００３１】
一方、河内らの方式が有する安全性は、ＲＳＡ問題の計算困難さに対して十分に緊密である。しかしながら、河内らの方式は、見富らの方式と同様、署名者の署名鍵のサイズを署名順序が進むにつれて大きく取らなければならないため、署名順番が制限される、署名鍵のサイズの増加に伴い計算量が増加する、などの問題がある。
【非特許文献１】Ｓ．三富（S. Mitomi）、Ａ．宮地（A. Miyaji）、“ア・ゼネラル・モデル・オブ・マルチシグネチャ・スキームズ・ウィズ・メッセージ・フレキシビリティ、オーダー・フレキシビリティ、アンド・オーダー・ベリファイアビリティ（A General Model of Multisignature Schemes with Message Flexibility, Order Flexibility, and Order Verifiability）”、アイイーアイシーイー・トランザクション・オブ・ファンダメンタルズ（IEICE Transaction of fundamentals）、２００１年、Ｅ−８４−Ａ， pp．2488-2499
【非特許文献２】Ｋ．河内（K. Kawauchi）、Ｍ．多田（M. Tada）、“オン・ジ・イグザクト・セキュリティ・オブ．マルチシグネチャ・スキームズ・ベースト・オン・アールエスエイ（On the exact security of multisignature schemes based on RSA）”、ジ・エイトス・オーストララシアン・コンファレンス・インフォメーション・セキュリティ・アンド・プライバシ（エイシーアイエスピー ２００３）（The Eighth Australasian Conference Information Security and Privacy (ACISP 2003)、シュプリンガー−フェアラーク（Springer-Verlag）、２００３年、レクチャー・ノーツ・イン・コンピュータ・サイエンス・２７２７（Lecture Notes in Computer Science 2727）、 pp．336-349
【非特許文献３】Ｍ．ベラル（M. Bellare）、Ｐ．ロガウェイ（P. Rogaway）、“オプティマル・アシンメトリック・エンクリプション − ハウ・トゥー・エンクリプト・ウィズ・アールエスエイ（Optimal Asymmetric Encryption − How to encrypt with RSA）”、アドバンセズ・イン・クリプトロジー − ユーロクリプト’９４ エルエヌシーエス（Advances in Cryptology − EUROCRYPT’94 LNCS）、シュプリンガー・フェアラーク（Springer-Verlag）、１９９５年
【発明の開示】
【発明が解決しようとする課題】
【００３２】
以上説明したように多重署名方式では、第２の方式のようにＲＳＡ問題の計算困難さに安全性の根拠をおく場合、署名順番が進むにつれて鍵のサイズを大きくしなければならないという問題がある。そのため、鍵のサイズに依存して署名順番が制限される、鍵が増加するにつれて計算量が増加するなどの問題がある。
【００３３】
本発明は上記実情を考慮してなされたもので、ＲＳＡ問題に代表される落し戸付一方向性関数の逆関数演算の計算困難さに安全性の根拠をおく場合に、署名順番が進んでも鍵のサイズの増加を阻止し得る多重署名方法、装置、プログラム及びシステムを提供することを目的とする。
【課題を解決するための手段】
【００３４】
第１の発明は、他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する多重署名生成装置による多重署名方法であって、前記第ｉ−１番目の署名σi-1を２つに分割し、ｋ２ビットの第２部分データσi-1,R及び残りの第１部分データσi-1,Lを得る工程と、ｋ０ビットの乱数データｒｉを生成する工程と、前記第１部分データσi-1,L 、前記第２部分データσi-1,R 、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを得る工程と、前記第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを得る工程と、前記第２ランダム関数値ｇｉと、前記第２部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る工程と、前記計算結果ｓｉ及び前記第１ランダム関数値ｗｉに基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを得る工程と、前記第１部分データσi-1,Lを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,L‖ｚｉ）を生成する工程と、この第ｉ番目の署名σｉを出力する工程と、を備えた多重署名方法である。
【００３５】
第２の発明は、他の多重署名生成装置により生成された第ｉ−１番目の署名σi-1と文書データｘとに基づいて、文書データｘに対する第ｉ番目の署名σiを生成する多重署名生成装置による多重署名方法であって、前記第ｉ−１番目の署名σi-1を３つに分割し、ｋ１ビットの第１部分データσi-1,L、ｋ２ビットの第３部分データσi-1,R及び残りの第２部分データσi-1,Mを得る工程と、ｋ０ビットの乱数データｒｉを生成する工程と、前記第２部分データσi-1,M、前記第３部分データσi-1,R、前記乱数データｒｉ及び前記文書データｘに第１ランダム関数Ｈｉ’を施し、ｋ１ビットの第１ランダム関数値ｗｉを得る工程と、前記第１ランダム関数値ｗｉ及び前記第１部分データσi-1,Lの２項演算を計算し、ｋ１ビットの計算結果ｗｉ’を得る工程と、前記計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉを得る工程と、前記第２ランダム関数値ｇｉと、前記第３部分データσi-1,R及び前記乱数データｒｉとの２項演算を計算し、（ｋ２＋ｋ０）ビットの計算結果ｓｉを得る工程と、前記計算結果ｓｉ及びｗｉ’に基づくｋビットのデータに署名生成関数を施し、ｋビットの署名値ｚｉを得る工程と、前記第２部分データσi-1,Mを前記署名値ｚｉに連結し、第ｉ番目の署名σｉ（＝σi-1,M‖ｚｉ）を生成する工程と、この第ｉ番目の署名σｉを出力する工程と、を備えた多重署名方法である。
【００３６】
（作用）
第１及び第２の発明は、従来の方式（図１３及び図１４参照）とは異なり、図１又は図２に示すように、第ｉ番目の署名σｉを生成する際に、第ｉ−１番目の署名σi-1を分割し、ｋ２ビットの部分データσi-1,R及び残りの部分データ（第１発明ではσi-1,L，第２の発明ではσi-1,L，σi-1,M）を得る。ここで、ｋ０ビットの乱数ｒｉを連結したときに（ｋ０＋ｋ２）ビットを越えてしまう部分データ（第１発明ではσi-1,L，第２の発明ではσi-1,L，σi-1,M）を、署名生成関数の入力側にある２項演算の入力から外す。これにより、２項演算の計算結果ｓｉのサイズを（ｋ０＋ｋ２）ビットで一定とし、結果的に署名生成関数の入力サイズを一定にする。従って、ＲＳＡ問題に代表される一方向性関数の逆関数演算の計算困難さに安全性の根拠をおく場合に、署名順番が進んでも鍵のサイズの増加を阻止することができる。
【発明の効果】
【００３７】
以上説明したように本発明によれば、ＲＳＡ問題に代表される一方向性関数の逆関数演算の計算困難さに安全性の根拠をおく場合に、署名順番が進んでも鍵のサイズの増加を阻止することができる。
【発明を実施するための最良の形態】
【００３８】
以下、本発明の各実施形態について図面を参照しながら説明するが、その前に各実施形態の概要を述べる。第１の実施形態は前述した第１の発明（図１参照）に対応し、第２の実施形態は第２の発明（図２参照）に対応している。
【００３９】
各実施形態では、多重署名システムの安全性を確保する観点から、署名生成関数としては、ＲＳＡ署名に代表される署名方式を使用する。各実施形態で用いられる、第ｉ−１晩目の署名者が用いる署名生成関数を一般にｆｉ−１で表す。ｆとしては、後に述べるＲＳＡ関数や、Ｒａｂｉｎ関数を用いることが可能である。以下では、まず、入出力サイズがｋビットとなる署名生成関数を用いて各実施形態を説明する。さらに、ＲＳＡ関数やＲａｂｉｎ関数を用いる場合に生じる変形例について図１５及び図１６を用いて説明する。
【００４０】
２つのランダム関数Ｈｉ’，Ｇｉは、例えばＳＨＡなどのハッシュ関数とする。なお、ランダム関数Ｈｉ’，Ｇｉの具体例は非特許文献３に挙げられている。続いて、各実施形態を具体的に述べる。
【００４１】
（第１の実施形態）
図３は本発明の第１の実施形態に係る多重署名システムの構成を示す模式図である。この多重署名システムは、Ｎ台の署名生成装置Ｓｇ１〜ＳｇＮ及び１台の署名検証装置Ｖが互いにネットワークを介して接続されている。
【００４２】
ここで、各署名生成装置Ｓｇ１〜ＳｇＮは、互いに同一のハードウェア構成を有するので、ここでは署名生成装置Ｓｇｉを代表例に挙げて説明する。
【００４３】
署名生成装置Ｓｇｉは、図４に示すように、メモリ１、入出力部２、乱数発生器３、乱数メモリ４、演算器５、Ｈi’関数演算部６、Ｇi関数演算部７、公開鍵暗号署名生成部８ｓ、秘密鍵メモリ９及び制御部１０ｓを備えている。なお、乱数発生器３及び秘密鍵メモリ９を除く各要素１〜１０は、互いにバスを介して接続されている。また、各部８ｓ，１０ｓの添字ｓは、署名生成処理を表している。同様に、後述する添字ｖは署名検証処理を表す。
【００４４】
ここで、メモリ１は、各部２〜１０から読出書込可能な記憶部であり、例えば文書データｘ、署名σi-1、第１部分データσi-1,L、第２部分データσi-1,R、第１ランダム関数値ｗｉ、第２ランダム関数値ｇｉ、計算結果ｓｉ、署名値ｚｉ、署名σｉといったデータが記憶される。
【００４５】
文書データｘは、第１番目乃至第ｉ−１番目までの署名者の識別子を含む文書データｘ’に第ｉ番目の署名者の識別情報ＩＤｉを連結して得られるものである。
【００４６】
署名者の識別子ＩＤｉは、署名順番可変性を持つ本実施形態の多重署名検証において、どの署名者の公開鍵をどの順番で作用させればよいかを知る上で重要な情報となる。補足すると、ここでは署名者の識別子ＩＤｉを署名生成順番ｉと同一視して説明している。一般には、識別子ＩＤｉの順番ｉと署名順番ｉとは無関係の場合が多いが、署名順番ｉと署名者の識別情報ＩＤｉとを対応付けることで、識別子ＩＤｉと署名順番ｉとを同一視することが可能である。
【００４７】
署名者の識別子ＩＤｉは、署名に添付させて送信することが考えられるが、以下の各実施形態では文書可変性の性質を利用し、前の署名順番ＩＤi-1の署名者から受けた文書データｘ’に自分の識別子ＩＤｉを連結して新たな文書データｘとして署名生成処理を行い、自らの識別子ＩＤｉのついた新たな文書データｘを次の署名順番ｉ＋１の署名者に送信することが可能である。
【００４８】
入出力部２は、署名生成装置Ｓｉと外部との間のインターフェイス装置であり、例えば、ユーザの操作により、文書データｘ及び署名σi-1を入力してメモリ１に書込む機能と、署名生成処理の結果、メモリ１に記憶された署名σｉ及び文書データｘを出力する機能とをもっている。
【００４９】
乱数発生器３は、署名生成時に必要な乱数ｒｉを発生させる部分であり、生成された乱数ｒｉを乱数メモリ４に書込む機能をもっている。
【００５０】
乱数メモリ４は、乱数発生器３から書込まれた乱数ｒｉを演算器５から読出可能に保持するものである。
【００５１】
演算器５は、各部６〜１０ｓに制御され、メモリ１内のデータに対する多倍長の演算を実行する部分であり、例えば、排他的論理和等の２項演算の計算、ビット連結・分割、ビットの比較、などを実行する機能と、実行結果をメモリ１に書込む機能をもっている。ここで、２項演算は、排他的論理和である場合を説明するが、これに限らず、排他的論理和に代えて、２のべき乗を法とした加算などを用いてもよい。但し、２のべき乗を法とした加算の場合、署名検証を可能にするための適切な処理を加える必要がある。適切な処理としては、例えば第１ランダム関数Ｈｉ’の出力を１ビット短くして先頭に０を添加する処理、署名検証時に桁あふれを検出するコードを追加する処理、複数の候補の中から正しい値を探す処理、などが挙げられる。
【００５２】
Ｈi’関数演算部６は、メモリ１内の第１部分データσi-1,L 、第２部分データσi-1,R 、乱数データｒｉ及び文書データｘに第１ランダム関数Ｈｉ’を施す機能と、得られたｋ１ビットの第１ランダム関数値ｗｉをメモリ１に書込む機能とをもっている。
【００５３】
ここで、第１ランダム関数Ｈi’としては、例えばＳＨＡ１などのハッシュ関数を用い、任意の長さの入力に対し、ｋ１ビットの乱数を出力するものとする。第１ランダム関数Ｈi’には一方向性と耐衝突性が要求されており、ｋ１の値としては例えば１００ビットから２００ビットの値を用いる。また、第１ランダム関数Ｈi’は各利用者に特有のランダム関数を用いてもよいし、全て又は一部の利用者で同じランダム関数を用いることも可能である。いずれにしても第１ランダム関数Ｈｉ’は、添字ｉにより、署名者の識別子ＩＤｉと対応付けて表している。また、第１のランダム関数Ｈｉ’と第２のランダム関数Ｇｉを同一の関数とし、関数演算部６，７を１つのみに削減することも可能である。
【００５４】
Ｇｉ関数演算部７は、メモリ１内の第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施す機能と、得られた（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉをメモリ１に書込む機能とをもっている。
【００５５】
ここで、第２ランダム関数Ｇｉとしては、例えばＳＨＡ１などのハッシュ関数を用い、ｋ１ビットの長さの入力に対し、ｋ０+ｋ２ビットの乱数を出力するものとする。ここで、各ビット長ｋ，ｋ０，ｋ１，ｋ２の間には、ｋ=ｋ０+ｋ１+ｋ２の関係が成り立つものとする。ｋ０は、署名者が生成させる乱数のサイズを表し、例えば８０ビットから２００ビットの値を用いる。ｋ２は、署名者が多重署名を生成する際に、多重署名のサイズの増加を抑えるために、前の署名順番の署名者が生成した署名情報のうち該当ビットを自らの署名生成関数及び第１のランダム関数Ｈｉ’への入力とする部分のサイズを表し、具体的にはｋ２＝ｋ−ｋ０−ｋ１であり、例えば６００ビットから８００ビットの値を用いる。第２ランダム関数Ｇiには一方向性と耐衝突性が要求される。また、Ｇiは各利用者に特有のランダム関数を用いてもよいし、全て又は一部の利用者で同じランダム関数を用いることも可能である。いずれにしても、第２ランダム関数Ｇｉは、添字ｉにより、署名者の識別子ＩＤｉと対応付けて表している。
【００５６】
公開鍵暗号署名生成部８ｓは、落し戸付一方向性関数ｆを用いた公開鍵暗号方式により、秘密鍵メモリ９内の秘密鍵に基づいて、メモリ１内の計算結果ｓｉ及び第１ランダム関数値ｗｉに基づくｋ（＝ｋ０＋ｋ１＋ｋ２）ビットのデータに署名生成関数を施す機能と、得られたｋビットの署名値ｚｉをメモリ１に書込む機能とをもっている。また、落し戸付一方向性関数ｆは、ＲＳＡ暗号方式に代表される公開鍵暗号方式が用いられる。落し戸付一方向性関数ｆの入出力値の長さをｋで表すとき、一般にｋは１０２４ビットや２０４８ビットなどが選択される。なお、各署名者が用いる署名生成関数の入出力サイズは署名順番に依存しないため、署名生成関数は通常の署名生成の用途で用いる署名生成関数を用いることが可能である。  秘密鍵メモリ９は、署名者（署名生成装置利用者）の公開鍵暗号方式に関する秘密鍵を格納するメモリであり、公開鍵暗号署名生成部８ｓから読出可能となっている。
【００５７】
制御部１０ｓは、入力された第ｉ−１番目の署名σi-1及び文書データｘに基づいて、文書データｘに対する第ｉ番目の署名σｉを生成し、得られた署名σｉ及び文書データｘを出力するように各部１〜９を制御するものである。具体的には制御部１０ｓは、図５に示すように各部１〜９を制御する機能をもっている。
【００５８】
一方、署名検証装置Ｖは、図５に示すように、署名生成装置Ｓｇｉの各要素１〜１０ｓのうち、乱数発生器３、乱数メモリ４及び秘密鍵メモリ９が省略され、公開鍵暗号署名生成部８ｓに代えて、公開鍵暗号署名検証部８ｖを有し、署名生成処理のための制御部１０ｓに代えて、署名検証処理のための制御部１０ｖを備えている。なお、署名検証装置Ｖの残りの要素１，２，５〜７は、署名生成装置Ｓｇｉとは入出力データの内容が異なるものの、署名生成装置で述べた要素１，２，５〜７と同様の処理機能をもっている。
【００５９】
ここで、公開鍵暗号署名検証部８ｖは、署名生成装置Ｓ１〜ＳＮと同一の公開鍵暗号方式により、メモリ１内の公開鍵に基づいて、メモリ１内の署名値ｚｉに鍵長ｋビットのＲＳＡ署名検証関数を施す機能と、得られた（ｋ２＋ｋ０）ビットの計算結果ｓｉ及びｋ１ビットの第１ランダム関数値ｗｉをメモリ１に書込む機能とをもっている。
【００６０】
制御部１０ｖは、入力された第ｉ番目の署名σi及び文書データｘに基づいて、この署名σｉの正当性を検証するように各部１〜８ｖを制御するものである。具体的には制御部１０ｖは、図５に示すように各部１〜８ｖを制御する機能をもっている。
【００６１】
次に、以上のように構成された多重署名システムの動作を図６及び図７のフローチャートを用いて説明する。
【００６２】
（署名生成処理）
署名者は、第ｉ−１番目の署名者から受けた署名σi-1及び文書データｘ’に関し、文書データｘ’に自己の識別子ＩＤｉを連結してなる文書データｘに自己の署名を添付するため、署名生成装置Ｓｇｉを利用する。ここで、文書データｘ’＝ｘ1‖…‖ｘi-1‖ＩＤ1‖…‖ＩＤi-1である。但し、ｉ番目の署名者が文書データｘ’を修正した場合、修正後の差分情報ｘiが連結され、文書データｘ’＝ｘ1‖…‖ｘi-1‖ｘi‖ＩＤ1‖…‖ＩＤi-1となる。また、署名対象の文書データｘ＝ｘ’‖ＩＤｉ＝ｘ1‖…‖ｘi‖ＩＤ1‖…‖ＩＤiである。この署名生成装置では、制御部１０ｓにより、図１及び図５に示すように、各部１〜９が動作する。
【００６３】
署名順番が１番の署名者は、署名をつけるべき文書ｘを入手し、前の署名者の署名情報σ0として、０がｋ２個連結した情報０k2を準備する。
【００６４】
入出力部２は、署名者の操作により、｛ｋ＋（ｉ−２）（ｋ０＋ｋ１）｝ビット（但し、ｋ＝ｋ０＋ｋ１＋ｋ２）の第ｉ−１番目の署名σi-1及び文書データｘを読込み、それぞれメモリ１に書込む（ＳＴ１）。但し、署名順番が１番の場合、入出力部２は、署名初期値σ０として０がｋ２個連結した情報０k2をメモリ１に書込む。
【００６５】
演算器５は、メモリ１内の第ｉ−１番目の署名σi-1を２つに分割し、得られた下位ｋ２ビットの第２部分データσi-1,R及び残りの（ｉ−１）（ｋ０＋ｋ１）ビットの第１部分データσi-1,Lをメモリ１に書込む（ＳＴ２）。なお、署名順番が１番の場合、第２部分データσi-1,R＝σ0であり、第１部分データσi-1,Lは存在しない。
【００６６】
乱数発生器３は、ｋ０ビットの乱数データｒｉを生成し、この乱数ｒｉをメモリ１に書込む（ＳＴ３）。
【００６７】
Ｈｉ’関数演算部６は、メモリ１内の第１部分データσi-1,L 、第２部分データσi-1,R 、乱数データｒｉ及び文書データｘに第１ランダム関数Ｈｉ’を施し、得られたｋ１ビットの第１ランダム関数値ｗｉ（＝Ｈｉ’（ｘ‖σi-1,L‖σi-1,R‖ｒｉ））をメモリ１に書込む（ＳＴ４）。
【００６８】
Ｇｉ関数演算部７は、メモリ１内の第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、得られた（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉ（＝Ｇｉ（ｗｉ））をメモリ１に書込む。
【００６９】
演算器５は、メモリ１内の第２ランダム関数値ｇｉと、第２部分データσi-1,R及び乱数データｒｉの連結データ（σi-1,R‖ｒｉ）との排他的論理和を計算し、得られた（ｋ２＋ｋ０）ビットの計算結果ｓｉをメモリ１に書込む（ＳＴ５）。
【００７０】
公開鍵暗号署名生成部８ｓは、落し戸付一方向性関数ｆを用いた公開鍵暗号方式により、秘密鍵メモリ９内の秘密鍵に基づいて、メモリ１内の計算結果ｓｉ及び第１ランダム関数値ｗｉの連結データ（ｓｉ‖ｗｉ）からなるｋ（＝ｋ０＋ｋ１＋ｋ２）ビットのデータに署名生成関数を施し、得られたｋビットの署名値ｚｉ（＝ｆi-1（ｓｉ‖ｗｉ））をメモリ１に書込む（ＳＴ６）。
【００７１】
入出力部２は、メモリ１内の第１部分データσi-1,Lを署名値ｚｉに連結し、得られた｛ｋ＋（ｉ−１）（ｋ０＋ｋ１）｝ビットの第ｉ番目の署名σｉ（＝σi-1,L‖ｚｉ）及び文書データｘを出力する（ＳＴ７）。但し、署名順番が１番の場合には、第１部分データσi-1,Lが存在しないので、署名値ｚ１＝署名σ１となる。
【００７２】
なお、以上のような第ｉ番目の署名σｉの生成処理は、受け取った第ｉ−１番目の署名σi-1を検証した後に行なってもよい。この検証は、後述する署名検証処理により実行可能である。
【００７３】
（署名検証処理）
署名検証者は、第ｉ番目の署名σｉ及び文書データｘが入力されたとき、この多重した署名σｉの正当性を検証するため、署名検証装置ｖを利用する。署名検証装置ｖは、署名検証処理を行う際に、各署名者の公開鍵を入出力部２から公開鍵暗号署名検証部８ｖに読み込むことにより、署名検証処理が可能となる。
【００７４】
署名検証装置ｖにおいては、図６に示すように、署名検証者の操作により、入出力部２が検証対象の文書データｘ及び第ｉ番目の署名σｉをメモリ１に書込む（ＳＴ１１）。
【００７５】
演算器５は、メモリ１内の第ｉ番目の署名σiを２つに分割し、得られた下位ｋビットの署名値ｚｉ及び残りの（ｉ−１）（ｋ０＋ｋ１）ビットの第１部分データσi-1,Lをメモリ１に書込む（ＳＴ１２）。
【００７６】
公開鍵暗号署名検証部８ｖは、公開鍵暗号方式により、メモリ１内の公開鍵に基づいて、メモリ１内の署名値ｚｉに署名検証関数を施し（ｆｉ（ｚｉ）＝ｓｉ‖ｗｉ）、得られた上位（ｋ２＋ｋ０）ビットの計算結果ｓｉ及び下位ｋ１ビットの第１ランダム関数値ｗｉをメモリ１に書込む（ＳＴ１３）。
【００７７】
Ｇｉ関数演算部７は、メモリ１内の第１ランダム関数値ｗｉに第２ランダム関数Ｇｉを施し、得られた（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉ（＝Ｇｉ(ｗｉ)）をメモリ１に書込む。
【００７８】
演算器５は、メモリ１内の第２ランダム関数値ｇｉと計算結果ｓｉとの排他的論理和を計算し、（ｋ２＋ｋ０）ビットの計算結果（σi-1,R‖ｒｉ）を得る（ＳＴ１４）。
【００７９】
Ｈｉ’関数演算部７は、メモリ１内の第１部分データσi-1,L、計算結果（σi-1,R‖ｒｉ）及び文書データｘに第１ランダム関数Ｈｉ’を施し、得られたｋ１ビットの第１ランダム関数値ｗｉ’（＝Ｈｉ’（ｘ‖σi-1,L‖σi-1,R‖ｒｉ））をメモリ１内に書込む（ＳＴ１５）。
【００８０】
制御部１０ｖは、メモリ１内からステップＳＴ１３により得られた第１ランダム関数値ｗｉとステップＳＴ１５により得られた第１ランダム関数値ｗｉ’とを読み出して両者を互いに検証し（ＳＴ１６）、両者が一致したとき、第ｉ番目の署名を正当であると判定する。
【００８１】
この第ｉ番目の署名が正当のとき、演算器５は、メモリ１内の計算結果（σi-1,R‖ｒｉ）を上位ｋ２ビットの第２部分データσi-1,R及び下位ｋ０ビットの乱数データｒｉに分割し、それぞれメモリ１に書込む。
【００８２】
また、演算器５は、メモリ１内の第１部分データσi-1,L及び第２部分データσi-1,Rを連結して第ｉ−１番目の署名σi-1（＝σi-1,L‖σi-1,R）を復元する。
【００８３】
制御部１０ｖは、この第ｉ−１番目の署名σi-1及び文書データｘを第ｉ番目の署名σi及び文書データｘとしてメモリ１を更新する。
【００８４】
制御部１０ｖは、この更新の完了後、ｉ＝１か否かを判定し（ＳＴ１７）、ｉ＝１でないときには、前述したステップＳＴ１１〜ＳＴ１７を再実行するように、各部１〜８ｖを制御する。但し、制御部１０ｖは、再実行の制御の前に、文書データｘから署名順番が第ｉ番目の署名者の識別情報ＩＤｉを削除し、得られた文書データｘ’を文書データｘに置き換える。
【００８５】
一方、制御部１０ｖは、ｉ＝１のとき（ＳＴ１７；ＹＥＳ）には更新した署名σ0が予め設定された署名初期値０k2と一致するか否かを検証し（ＳＴ１９）、両者が一致するときには、多重した署名σｉを受理し（ＳＴ２０）、署名検証処理を終了する。
【００８６】
また、制御部１０ｖは、ステップＳＴ１９又はＳＴ１６にて両者が不一致のとき、署名を棄却し（ＳＴ２１）、署名検証処理を終了する。
【００８７】
（乱数ｒｉ及びランダム関数Ｈｉ’，Ｇｉの役割）
ここで、以上の動作における乱数ｒｉ、第１のランダム関数Ｈi’、第２のランダム関数Ｇiの役割を述べる。
【００８８】
乱数ｒｉは、安全性の向上、より厳密には帰着効率の向上に関与している。前述したように、一般に多重署名方式の安全性は、帰着により証明される。安全性証明は、多重署名方式が安全でなければ、ＲＳＡ問題に代表される落し戸付一方向性関数の逆関数演算を実行することができることを示すことで行われる。すなわち、多重署名方式を破る偽造者が存在するならば、シミュレーション環境で偽造者を動作させ、偽造者から情報を得ることでＲＳＡ問題を破るようなアルゴリズムを構成する。
【００８９】
証明の中での乱数ｒiの役割は、直観的には、シミュレーションにより署名依頼に適切に回答できなくなった文書に対して偽造者が当該文書の署名依頼を出力した際、新たな乱数により署名依頼への回答を適切にシミュレートできることにある。署名方式ＰＳＳにおける乱数も同様の役割を果たしている。このとき、偽造者に乱数がランダムに選ばれたことを保証するために、乱数は真にランダムに選ぶ必要があるが、ここで選んだ乱数が過去に選んだ乱数と同一であって、署名依頼への回答を適切にシミュレートできないときには安全性証明が破綻する。従って、ランダムに選んだ乱数は過去に選んだものと異なる必要があり、そのためには乱数のサイズを十分に大きく取る必要がある。一般的には、乱数ｒｉのサイズｋ０としては、８０〜１６０ビットの値を選べば十分である。
【００９０】
第１及び第２のランダム関数Ｈi’，Ｇiの第１の役割は、署名検証における署名の正当性を保証することである。すなわち、ステップＳＴ１６において、署名検証処理の過程で計算された値ｗｉと第１のランダム関数の出力ｗｉ’とが一致するかどうか、ステップＳＴ１９において、署名検証処理の過程で計算された値ｓｉと第２のランダム関数Ｇｉの出力Ｇ（ｗｉ）との排他的論理和から得られる値σ0,R＝σ０が、署名順番が０番目の署名者が初期値として用いた値０k2に等しいかどうか、で署名を受理するか否かを判定している。
【００９１】
さらに、第１及び第２のランダム関数Ｈi’，Ｇiの第２の役割は、安全性証明において偽造者を動作させる環境のシミュレートを適切に実現することが挙げられる。安全性証明はランダムオラクルの仮定の基で行われることに注意する。ここで、ランダムオラクルモデルとは、ランダム関数が理想的であり、同一の入力に対しては同一の出力を得るが、ある入力を与えて計算するまではその入力に対応する出力は１ビットとして予測できない状況をいう。
【００９２】
（多重署名方式が安全な理由）
本実施形態の多重署名方式が安全である直観的な理由は、次のように説明できる。多重署名方式が安全であるとは、直観的には、いかなる攻撃者も任意の文書に対して署名を偽造できないときをいう。このとき、攻撃者はＮ人の署名者による多重署名を偽造する際、少なくとも一人の署名者を除いて最大Ｎ-１人の署名者と結託して、Ｎ-１人の署名者の秘密鍵を入手することが許されている。今、攻撃者が少なくとも一人のある署名者の署名生成関数として用いられている落し戸付一方向性関数fiの一方向性を破らずに、偽造署名を生成する場合を考える。
【００９３】
このとき、攻撃者にとって最良の攻撃手順は、先に署名候補ｚi’を決めて、次に適切な文書ｘを定めることである。攻撃者はｚi’を定めると、一方向性関数ｆiを計算可能な向きに作用させてｓi‖ｗi＝fi(ｚi’)を求めることができ、以下、多重署名検証手順に従ってσi-1、σi-2，・・・，σ1，σ0を計算することが可能である。
【００９４】
しかし、第１及び第２のランダム関数Ｈｉ’，Ｇｉの性質、及び、一方向性関数ｆiが一対一関数であることから、次の状況（ａ）（ｂ）は偶然でしか起こりえない。
【００９５】
（ａ）ランダムに選んだｚiに対して各署名者の署名情報に対応するｗiが第１のランダム関数Ｈｉ’にｘ,σi-１‖ｒiを入力して得られる値と一致すること。
【００９６】
（ｂ）ランダムなｚiに対して得られる署名σ0と初期値データ０k2とが一致すること。
【００９７】
従って、署名の偽造は困難である。
【００９８】
（能動的な攻撃に対する安全性）
本実施形態の多重署名に関し、能動的な攻撃を行う攻撃者を考える。攻撃者は正規署名者に対して、自ら選んだ文書に対して署名依頼を行い、対応する署名を受け取り、そこで得た情報を基に第１実施形態に対して攻撃を行う。
【００９９】
署名依頼を行うことで得られる情報は、受け取った署名σi=σi-１,L‖zi’の署名検証を行うことで得られる情報、すなわち、文書ｘと前の署名順番の署名者の署名情報σi-１に対して乱数ｒiが選ばれて、第１のランダム関数Ｈi’に文書と署名情報と乱数の連結データｘ‖σi-１,L‖σi-１,R‖ｒiが入力されたときにｗiが出力されること、ｗiを第２のランダム関数Ｇiに入力して得られるＧi(ｗi)とσi-１,R‖ｒiとの排他的論理和を計算するとｓiと等しくなること、落し戸付一方向性関数の逆関数演算f-1(ｓi‖ｗi)がｚi’と等しくなること、である。
【０１００】
能動的攻撃により本実施形態の署名方式の偽造が成功するか否かは、データｓi‖ｗiに対して落し戸付一方向性関数の逆関数演算ｚi’=ｆ-1(ｓi‖ｗi)が計算できるか否かによる。今、攻撃者が能動的攻撃を行った結果、及び、自ら選んだｚi’を落し戸付一方向性関数に入力することでｓi‖ｗiを計算して、組(ｓi‖ｗi,ｚi’=ｆ-1(ｓi‖ｗi))を多数所有しているとする。
【０１０１】
一般に、文書ｘ、σi-１、乱数ｒiを任意に選んだとしても、第１及び第２のランダム関数Ｈｉ’，Ｇｉの性質から、計算されたｓi‖ｗiが保有したリストにあるｓ‖ｗと一致することは起こりえない。
【０１０２】
従って、受動的な攻撃と同様、攻撃者にとって最良の攻撃手順は、先に署名候補ｚi’を決めて、次に適切な文書ｘを定めることである。ここで、保有している(ｓ‖ｗ,ｚ)の中で、特に能動的に得られた組に対して、データｗから得られる値Ｇ(ｗ)とデータｓとの排他的論理和により計算されるσi-１,R‖ｒに、署名依頼として出力したσi-１,Lと文書ｘとは異なるσi-１,L’とｘ’を添加して連結データ（ｘ‖σi-１,L’‖σi-１,R‖ｒ）を得たとする。しかしながら、この連結データを第１のランダム関数Ｈi’に入力した際に、第１のランダム関数Ｈi’の出力がｗと等しくなるようにσi-１,L’とｘ’を見つけることは、第１のランダム関数Ｈi’の性質から困難である。このため、攻撃は不可能である。
【０１０３】
なお、署名依頼に出力したσi-１,Lとｘとは異なるσi-１,L’とｘ’を選ぶ理由は、次の通りである。すなわち、署名依頼に出力したσi-１,Lとｘを用いた場合、σi-１,R‖ｒにσi-１,Lとｘを第１のランダム関数に入力して得られる値はｗと一致はするが、仮にｘとσi-１,L‖σi-１,Rに対する署名として署名σi-１,L‖ｚを出力したとしても、この署名は能動的攻撃である署名依頼により正規の署名者が生成した署名そのものである。従って、署名の偽造、すなわち、正規の署名者が承認していない文書に対して新たな署名を出力すること、には成功しないからである。
【０１０４】
従って、本実施形態の多重署名方式に対しても能動的な攻撃により得られた情報を用いて偽造署名を出力することは困難であり、上述した理由から本実施形態の安全性が証明できる。安全性の議論と同様の議論は、後述する第２実施形態の安全性にも適用できる。
【０１０５】
上述したように本実施形態によれば、図１に示すように、第ｉ番目の署名σｉを生成する際に、第ｉ−１番目の署名σi-1を分割し、ｋ０ビットの乱数ｒｉを連結したときに（ｋ０＋ｋ２）ビットを越える部分（σi-1,L）を、署名生成関数ｆｉ−１の入力側にある２項演算の入力から外す。これにより、２項演算の計算結果ｓｉのサイズを（ｋ０＋ｋ２）ビットで一定とし、結果的に署名生成関数の入力サイズ（ｋビット）を一定にする。従って、落し戸付一方向性関数の逆関数演算の計算困難さに安全性の根拠をおく場合に、署名順番が進んでも鍵のサイズの増加を阻止することができる。
【０１０６】
詳しくは、当該署名者は、前の署名順番の署名者の署名情報を２つ以上の部分に分ける。そのうち１つは該当ビットが署名生成関数に入力される部分であり、残りの部分は該当ビットが第１のランダム関数Ｈｉ’に入力された後に署名生成関数の出力に添付されて当該署名者の署名として出力される部分である。この分割により、署名生成関数への入力の長さを署名順番に依存しないようにすることで、各署名者の鍵のサイズは署名順番や総署名者数に依存することなく一定にできる。
【０１０７】
より詳しくは、本実施形態は、図１４に示した方法とは異なり、第ｉ−１番目の署名σi-1のうち、下位ｋ２ビットの第２部分データ（σi-1,R）を署名生成関数ｆｉ−１に入力し、残りの部分（σi-1,L）を署名生成関数に入力せずに署名値ｚｉに添付することにより、緊密な安全性を保ちつつ、各署名者が用いる署名生成関数の入力サイズ、すなわち、秘密鍵のサイズを署名順番や総署名者数に依存することなく一定にとることができる。
【０１０８】
従って、本方法を実装する際には、署名順番を署名生成関数の入力サイズに制限されることなく自由に選ぶことが可能で（署名順番可変性）あり、さらに、既存技術と異なり署名生成関数の入力サイズが署名順番に依存して増加することがないため、署名順番が大きくなるにつれて計算量が増加する問題を解決できる。また、計算量の増加を抑えるとともに、実用的に署名順番可変性・署名順番検証可能性を実現できる。
【０１０９】
なお、本実施形態は、次のように変形してもよい。  
例えば、署名生成処理においては、署名初期値σ０として、０がｋ２個連結した情報０k2を用いていたが、これに限らず、ｋ２ビット以上のサイズをもつ固定値を用いるように変形してもよい。
【０１１０】
以上で説明した上記実施形態は、署名生成関数を一般化したものについて説明したが、具体的な例として、署名生成関数としてＲＳＡ関数やＲａｂｉｎ関数を用いる場合には、実装等において制約を受ける。従って、厳密にはＲＳＡ署名方式やＲａｂｉｎ署名方式は、ｋビットの値であっても法の値より大きい値を入力とすることはできないが、法の値より大きな値を入力するための技術が知られており、例えば図１５や図１６に示すような変形例を構成することが可能である。
【０１１１】
図１５の方法では、本実施形態の処理手順を示す図６のステップＳＴ１において、ｋ+(ｉ−２)（ｋ０＋ｋ１）＋ｉ−２ビットの第ｉ−１番目σｉ−１を読み込み、ステップＳＴ２において、ｋ２ビットからなる第２の部分σｉ−１,Ｒと(ｉ−１)（ｋ０＋ｋ１）＋ｉ−１ビットからなる第一の部分σｉ−１,Ｌに分割した後、ステップＳＴ６において、ｓｉとｗｉを連結した情報の先頭に０を連結して得られるｋ＝１＋ｋ０＋ｋ１＋ｋ２ビットのデータ０‖ｓｉ‖ｗｉに対して、ｚｉをｆｉ-１（０‖ｓｉ‖ｗｉ）により計算する．最後に、ステップＳＴ７において、(ｉ−１)（ｋ０＋ｋ１）＋ｉ−１ビットの第一の部分σｉ−１,Ｌとｋビットのｚｉを連結して、ｋ＋(ｉ−１)（ｋ０＋ｋ１）＋ｉ−１ビットの値の第ｉ番目の署名σｉを計算する。この変形例における署名検証処理では、ステップＳＴ１３において、ＲＳＡ署名またはＲａｂｉｎ署名の公開鍵を署名値ｚiに作用した後、先頭ビットが０になるか否かを検査し、先頭ビットが０のときには公開鍵を作用させて得られるデータのうち、２ビット目からｋ０+ｋ２ビットをｓｉ、下位ｋ１ビットをｗiとおき、署名検証処理を行う。検査の結果、先頭ビットが０でないときには、署名を棄却すればよい。
【０１１２】
図１６の方法では、本実施形態の処理手順を示す図６のステップＳＴ１において、ｋ+(ｉ−２)（ｋ０＋ｋ１）＋ｉ−２ビットの第ｉ−１番目σｉ−１を読み込み、ステップＳＴ２において、ｋ２ビットからなる第２の部分σｉ−１,Ｒと(ｉ−１)（ｋ０＋ｋ１）＋ｉ−２ビットからなる第一の部分σｉ−１,Ｌに分割する。さらに、ステップＳＴ６において、ｓｉとｗｉを連結して得られるｋ＝１＋ｋ０＋ｋ１＋ｋ２ビットのデータの先頭ビットｓｉ１と残りのｋ−１ビットからなるｓ’ｉ‖ｗｉに分割して、ｚｉをｆｉ-１（ｓ’ｉ‖ｗｉ）により計算する．最後に、ステップＳＴ７において、(ｉ−１)（ｋ０＋ｋ１）＋ｉ−２ビットの第一の部分σｉ−１,Ｌとｓｉとｗｉを連結して得られるデータの先頭ビットｓｉ１とｋビットのｚｉを連結して、ｋ＋(ｉ−１)（ｋ０＋ｋ１）＋ｉ−１ビットからなるσｉ−１,Ｌ‖ｓｉ１‖ｚｉの値の第ｉ番目の署名σｉを計算する。  さらに、ステップＳＴ６では、計算結果ｓiと第１ランダム関数値ｗiの連結データを署名生成関数に入力する場合を述べたが、これに限らず、計算結果ｓiとｗiから生成される別のデータを署名生成関数に入力するように変形してもよい。例えば、第３のランダム関数Ｇ’を用いてｓiをｓi’とし、ｗｉ’とＧ’(ｓi)との排他的論理和の計算結果をｗｉ”とし、これらのデータｓi’，ｗi”を連結したデータ（ｓi’‖ｗi”）を署名生成関数に入力する変形例などが考えられる。
【０１１３】
（第２の実施形態）
次に、本発明の第２の実施形態に係る多重署名システムについて前述した図３乃至図５を参照しながら説明する。
【０１１４】
すなわち、本実施形態は、ハードウェア構成としては第１の実施形態と同様であるが、第１の実施形態とは異なり、図１に示した方式に代えて、図２に示した方式を実行するものである。これに伴い、署名生成装置Ｓｇｉの制御部１０ｓが図８に示すように各部１〜９を制御するものとなっており、署名検証装置ｖの制御部１０ｖが図９に示すように各部１〜８ｖを制御するものとなっている。
【０１１５】
次に、以上のように構成された多重署名システムの動作を図８及び図９のフローチャートを用いて説明する。
【０１１６】
（署名生成処理）
署名者は、第ｉ−１番目の署名者から受けた署名σi-1及び文書データｘ’に関し、文書データｘ’に自己の識別子ＩＤｉを連結してなる文書データｘに自己の署名を添付するため、署名生成装置Ｓｇｉを利用する。ここで、文書データｘ’＝ｘ1‖…‖ｘi-1‖ＩＤ1‖…‖ＩＤi-1である。但し、ｉ番目の署名者が文書データｘ’を修正した場合、修正後の差分情報ｘiが連結され、文書データｘ’＝ｘ1‖…‖ｘi-1‖ｘi‖ＩＤ1‖…‖ＩＤi-1となる。また、署名対象の文書データｘ＝ｘ’‖ＩＤｉ＝ｘ1‖…‖ｘi‖ＩＤ1‖…‖ＩＤiである。この署名生成装置では、制御部１０ｓにより、図２及び図８に示すように、各部１〜９が動作する。
【０１１７】
署名順番が１番の署名者は、署名をつけるべき文書ｘを入手し、前の署名者の署名情報σ0として、０が２ｋ１＋ｋ２個連結した情報０2k1+k2を準備する。
【０１１８】
入出力部２は、署名者の操作により、｛ｋ＋ｋ１＋（ｉ−２）ｋ０）｝ビット（但し、ｋ＝ｋ０＋ｋ１＋ｋ２）の第ｉ−１番目の署名σi-1及び文書データｘを読込み、それぞれメモリ１に書込む（ＳＴ３１）。但し、署名順番が１番の場合、入出力部２は、署名初期値σ０として０が２ｋ１＋ｋ２個連結した情報０2k1+k2をメモリ１に書込む。
【０１１９】
演算器５は、メモリ１内の第ｉ−１番目の署名σi-1を３つに分割し、得られた上位ｋ１ビットの第１部分データσi-1,L、下位ｋ２ビットの第３部分データσi-1,R及び残りの｛ｋ１＋（ｉ−１）ｋ０｝ビットの第２部分データσi-1,Mをメモリ１に書込む（ＳＴ３２）。
【０１２０】
乱数発生器３は、ｋ０ビットの乱数データｒｉを生成し、この乱数ｒｉをメモリ１に書込む（ＳＴ３３）。
【０１２１】
Ｈｉ’関数演算部６は、メモリ１内の第２部分データσi-1,M 、第３部分データσi-1,R 、乱数データｒｉ及び文書データｘに第１ランダム関数Ｈｉ’を施し、得られたｋ１ビットの第１ランダム関数値ｗｉ（＝Ｈｉ’（ｘ‖σi-1,M‖σi-1,R‖ｒｉ））をメモリ１に書込む（ＳＴ３４）。
【０１２２】
演算器５は、メモリ１内の第１ランダム関数値ｗｉと、第１部分データσi-1,Lとの排他的論理和を計算し、得られたｋ１ビットの計算結果ｗｉ’をメモリ１に書込む（ＳＴ３５）。
【０１２３】
Ｇｉ関数演算部７は、メモリ１内の計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、得られた（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉ（＝Ｇｉ（ｗｉ））をメモリ１に書込む。
【０１２４】
演算器５は、メモリ１内の第２ランダム関数値ｇｉと、第３部分データσi-1,R及び乱数データｒｉの連結データ（σi-1,R‖ｒｉ）との排他的論理和を計算し、得られた（ｋ２＋ｋ０）ビットの計算結果ｓｉをメモリ１に書込む（ＳＴ３６）。
【０１２５】
公開鍵暗号署名生成部８ｓは、落し戸付一方向性関数ｆを用いた公開鍵暗号方式により、秘密鍵メモリ９内の秘密鍵に基づいて、メモリ１内の計算結果ｓｉ及びｗｉ’の連結データ（ｓｉ‖ｗｉ’）に鍵長ｋ（＝ｋ０＋ｋ１＋ｋ２）ビットの署名生成関数ｆｉ−１を施し、得られたｋビットの署名値ｚｉ（＝ｆi-1（ｓｉ‖ｗｉ’））をメモリ１に書込む（ＳＴ３７）。
【０１２６】
入出力部２は、メモリ１内の第２部分データσi-1,Mを署名値ｚｉに連結し、得られた｛ｋ＋ｋ１＋（ｉ−１）ｋ０）｝ビットの第ｉ番目の署名σｉ（＝σi-1,M‖ｚｉ）及び文書データｘを出力する（ＳＴ３８）。
【０１２７】
なお、以上のような第ｉ番目の署名σｉの生成処理は、受け取った第ｉ−１番目の署名σi-1を検証した後に行なってもよい。この検証は、後述する署名検証処理により実行可能である。
【０１２８】
（署名検証処理）
署名検証者は、第ｉ番目の署名σｉ及び文書データｘが入力されたとき、この多重した署名σｉの正当性を検証するため、署名検証装置ｖを利用する。署名検証装置ｖは、署名検証処理を行う際に、各署名者の公開鍵を入出力部２から公開鍵暗号署名検証部８ｖに読み込むことにより、署名検証処理が可能となる。
【０１２９】
署名検証装置ｖにおいては、図９に示すように、署名検証者の操作により、入出力部２が検証対象の文書データｘ及び｛ｋ＋ｋ１＋（ｉ−１）ｋ０）｝ビットの第ｉ番目の署名σｉをメモリ１に書込む（ＳＴ４１）。
【０１３０】
制御部１０ｖは、メモリ１内の文書データｘにおける識別子ＩＤ１〜ＩＤｉに基づいて署名順番ｉを読み込む（ＳＴ４２）。
【０１３１】
演算器５は、メモリ１内の第ｉ番目の署名σiを２つに分割し、得られた下位ｋビットの署名値ｚｉ及び残りの｛ｋ１＋（ｉ−１）ｋ０）｝ビットの第２部分データσi-1,Mをメモリ１に書込む（ＳＴ４３）。
【０１３２】
公開鍵暗号署名検証部８ｖは、公開鍵暗号方式により、メモリ１内の公開鍵に基づいて、メモリ１内の署名値ｚｉに鍵長ｋビットのＲＳＡ署名検証関数を施し（ｆｉ（ｚｉ）＝ｓｉ‖ｗｉ’）、得られた上位（ｋ２＋ｋ０）ビットの計算結果ｓｉ及び下位ｋ１ビットの計算結果ｗｉ’をメモリ１に書込む（ＳＴ４４）。
【０１３３】
Ｇｉ関数演算部７は、メモリ１内の計算結果ｗｉ’に第２ランダム関数Ｇｉを施し、得られた（ｋ２＋ｋ０）ビットの第２ランダム関数値ｇｉ（＝Ｇｉ(ｗｉ’)）をメモリ１に書込む。
【０１３４】
演算器５は、メモリ１内の第２ランダム関数値ｇｉと計算結果ｓｉとの排他的論理和を計算し、得られた（ｋ２＋ｋ０）ビットの計算結果（σi-1,R‖ｒｉ）をメモリ１に書込む（ＳＴ４５）。
【０１３５】
また、演算器５は、メモリ１内の計算結果（σi-1,R‖ｒｉ）を上位ｋ２ビットの第３部分データσi-1,R及び下位ｋ０ビットの乱数データｒｉに分割し、それぞれメモリ１に書込む。
【０１３６】
ここで、制御部１０ｖは、ステップＳＴ４２で読み込んだ署名順番ｉが３以上であれば（ＳＴ４６；ＹＥＳ）、ステップＳＴ４７に進む。
【０１３７】
ステップＳＴ４７では、Ｈｉ’関数演算部７は、メモリ１内の第２部分データσi-1,M、計算結果（σi-1,R‖ｒｉ）及び文書データｘに第１ランダム関数Ｈｉ’を施し、得られたｋ１ビットの第１ランダム関数値ｗｉ（＝Ｈｉ’（ｘ‖σi-1,M‖σi-1,R‖ｒｉ））をメモリ１に書込む。
【０１３８】
演算器５は、メモリ１内の計算結果ｗｉ’と第１ランダム関数値ｗｉとの排他的論理和を計算し、得られた第１部分データσi-1,Lをメモリ１に書込む（ＳＴ４８）。
【０１３９】
しかる後、演算器５は、メモリ１内の第１〜第３部分データσi-1,L，σi-1,M，σi-1,Rを連結して第ｉ−１番目の署名σi-1を復元する。
【０１４０】
制御部１０ｖは、この第ｉ−１番目の署名σi-1及び文書データｘを第ｉ番目の署名σi及び文書データｘとしてメモリ１を更新する（ＳＴ４９）。
【０１４１】
制御部１０ｖは、この更新の完了後、ｉ−１をｉとして（ＳＴ５０）、前述したステップＳＴ４１〜ＳＴ４９を再実行するように、各部１〜８ｖを制御する。但し、制御部１０ｖは、再実行の制御の前に、文書データｘから署名順番が第ｉ番目の署名者の識別情報ＩＤｉを削除し、得られた文書データｘ’を文書データｘに置き換える。
【０１４２】
このようなステップＳＴ４１〜ＳＴ５０のループ処理により、ステップＳＴ４２で読み込んだ署名順番ｉが３未満となり（ＳＴ４６；ＮＯ）、ｉ＝２となったとする（ＳＴ５１；ＹＥＳ）。
【０１４３】
このとき、前述したステップＳＴ４７，ＳＴ４８と同様のステップＳＴ５２，ＳＴ５３が実行される。すなわち、Ｈｉ’関数演算部７は、メモリ１内の第２部分データσ1,M、計算結果（σ1,R‖ｒ2）及び文書データｘに第１ランダム関数Ｈｉ’を施し、得られたｋ１ビットの第１ランダム関数値ｗ２（＝Ｈ２’（ｘ‖σ1,M‖σ1,R‖ｒ2））をメモリ１に書込む（ＳＴ５２）。演算器５は、メモリ１内の計算結果ｗ2’と第１ランダム関数値ｗ2との排他的論理和を計算し、得られた第１部分データσ1,Lをメモリ１に書込む（ＳＴ５３）。
【０１４４】
ここで、制御部１０ｖは、ステップＳＴ５３により得られた第１部分データσ1,Lが予め設定された値０k1と一致するか否かを検証し、両者が不一致のときには、ステップＳＴ５５に進んで署名σｉを棄却する。但し、ここでは両者が一致する場合を述べる。
【０１４５】
制御部１０ｖは、両者が一致する場合、前述したステップＳＴ４９に進む。
【０１４６】
次に、このようなステップＳＴ４９，ＳＴ５０，ＳＴ４１〜ＳＴ４６に進み、ステップＳＴ４２で読み込んだ署名順番ｉが３未満となり（ＳＴ４６；ＮＯ）、ｉ＝２でなく（ＳＴ５１；ＮＯ）、ｉ＝１となったとする。
【０１４７】
このとき、制御部１０ｖは、メモリ１内の第３部分データσ0,Rが予め設定した値０k2と一致するか否かを検証し、両者が不一致のときには、ステップＳＴ５５に進んで署名σｉを棄却する。但し、ここでは両者が一致する場合を述べる。
【０１４８】
このとき、前述したステップＳＴ４７，ＳＴ４８と同様のステップＳＴ５７，ＳＴ５８が実行される。すなわち、Ｈｉ’関数演算部７は、メモリ１内の第２部分データσ0,M、計算結果（σ0,R‖ｒ1）及び文書データｘに第１ランダム関数Ｈ1’を施し、得られたｋ１ビットの第１ランダム関数値ｗ1（＝Ｈ1’（ｘ‖σ0,M‖σ0,R‖ｒ1））をメモリ１に書込む（ＳＴ５７）。演算器５は、メモリ１内の計算結果ｗ1’と第１ランダム関数値ｗ1との排他的論理和を計算し、得られた第１部分データσ0,Lをメモリ１に書込む（ＳＴ５８）。
【０１４９】
ここで、制御部１０ｖは、ステップＳＴ５８により得られた第１部分データσ0,Lが予め設定された値０k1と一致するか否かを検証し、両者が不一致のときには、ステップＳＴ５５に進んで署名σｉを棄却して処理を終了する。一方、両者が一致するときには、制御部１０ｖは、署名σｉを受理し（ＳＴ６０）、署名検証処理を終了する。
【０１５０】
（乱数ｒｉ及びランダム関数Ｈｉ’，Ｇｉの役割）
乱数ｒi、第１及び第２のランダム関数Ｈi’，Ｇiの役割は、第１実施形態の場合と同様である。
【０１５１】
（多重署名方式が安全な理由）
多重署名方式が安全である直観的な理由は、第１実施形態の場合と同様である。  
（能動的な攻撃に対する安全性）
能動的な攻撃に対する安全性は、第１実施形態の場合と同様である。  
上述したように本実施形態によれば、図２に示すように、第ｉ番目の署名σｉを生成する際に、第ｉ−１番目の署名σi-1を分割し、ｋ０ビットの乱数ｒｉを連結したときに（ｋ０＋ｋ２）ビットを越える部分（σi-1,L，σi-1,M）を、署名生成関数の入力側にある２項演算の入力から外す。これにより、２項演算の計算結果ｓｉのサイズを（ｋ０＋ｋ２）ビットで一定とし、結果的に署名生成関数の入力サイズ（鍵長ｋビット）を一定にする。従って、ＲＳＡ問題に代表される落し戸付一方向性関数の逆関数演算の計算困難さに安全性の根拠をおく場合に、署名順番が進んでも鍵のサイズの増加を阻止することができる。
【０１５２】
詳しくは、本実施形態は、前回の署名σi-1の全てに第１のランダム関数Ｈｉ’を施した第１の実施形態とは異なり、前回の署名σi-1を３つに分割し、その第２及び第３部分データσi-1,M，σi-1,Rのみを第１のランダム関数の入力とし、第１部分データσi-1,Lを第１のランダム関数Ｈｉ’の出力に排他的論理和として反映させることにより、緊密な安全性を保ちつつ、多重署名のサイズを従来技術よりも小さくでき、通信コストを低減させることができる。
【０１５３】
ここで、署名生成関数の入力に反映させる部分σi-１,Lのサイズは、第１のランダム関数Ｈｉ’の出力サイズｋ１より小さくても良い。このときには、第１のランダム関数Ｈｉ’の出力の所定部分に対してσi-１,Lの排他的論理和を計算し、署名検証処理においても、当該部分からσi-１,Lを復元すればよい。
【０１５４】
また、署名生成関数は、その入出力サイズが署名順番に依存しないため、通常の署名生成の用途で用いる署名生成関数を用いることができる。
【０１５５】
なお、本実施形態は、次のように変形してもよい。
【０１５６】
例えば署名生成処理においては、署名初期値σ０として、０が２ｋ１+ｋ２個連結した情報０2k1+k2を用いていたが、これに限らず、２ｋ１+ｋ２ビット以上の任意の固定値を用いるように変形してもよい。さらに、ｋ２ビット以上の値であれば、異なるサイズの固定値を利用するように変形することもできる。但し、ｋ２ビット以上の固定値を用いる場合には、安全性を保証するために、第２実施形態の署名順番が１番目と２番目の署名に関する署名生成処理及び署名検証処理を、第１実施形態の署名順番が１番目と２番目の署名に関する署名生成処理と署名検証処理に置き換える必要がある。
【０１５７】
なお、説明は省略するが、署名生成関数としてＲＳＡ関数を用いる場合には、本発明の第一の実施形態で説明したことと同様な変形例で実現可能であることは勿論である。  さらに、ステップＳＴ３６では、計算結果ｓiとｗi’の連結データを署名生成関数に入力する場合を述べたが、これに限らず、計算結果ｓiとｗi’から生成される別のデータを署名生成関数に入力するように変形してもよい。例えば、第３のランダム関数Ｇ’を用いてｓiをｓi’とおき、ｗi’とＧ’(ｓi)との排他的論理和の計算結果をｗ”とし、ｓi’とｗi”を連結したデータ（ｓi’‖ｗi”）を署名生成関数に入力する変形例などが考えられる。
【０１５８】
また、第１のランダム関数Ｈ1’〜ＨN’と第２のランダム関数Ｇ1〜ＧNのそれぞれについて、各署名者で共通のランダム関数Ｈ’，Ｇを使用してもよく、さらに、第１のランダム関数と第２のランダム関数を互いに同一の関数とし、ランダム関数演算部を１つのみに削減することも可能である。
【０１５９】
なお、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１６０】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１６１】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１６２】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【０１６３】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１６４】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１６５】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１６６】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１６７】
【図１】本発明の第１の実施形態に係る多重署名システムによる署名生成方式を示す模式図である。
【図２】本発明の第２の実施形態に係る多重署名システムによる署名生成方式を示す模式図である。
【図３】本発明の第１の実施形態に係る多重署名システムの構成を示す模式図である。
【図４】同実施形態における署名生成装置の構成を示す模式図である。
【図５】同実施形態における署名検証装置の構成を示す模式図である。
【図６】同実施形態における署名生成装置の動作を示すフローチャートである。
【図７】同実施形態における署名検証装置の動作を示すフローチャートである。
【図８】本発明の第２の実施形態における署名生成装置の動作を示すフローチャートである。
【図９】同実施形態における署名検証装置の動作を示すフローチャートである。
【図１０】一般的な多重署名方式及び連結署名方式の概念を示す模式図である。
【図１１】一般的な多重署名方式の検証用装置の概念を示す模式図である。
【図１２】一般的な多重署名方式の文書可変性の概念を示す模式図である。
【図１３】従来の多重署名方法における署名生成方式の一例を示す模式図である。
【図１４】従来の多重署名方法における署名生成方式の一例を示す模式図である。
【図１５】本発明の第１の実施形態における変形例を示す模式図である。
【図１６】同実施形態における他の変形例を示す模式図である。
【符号の説明】
【０１６８】
１…メモリ、２…入出力部、３…乱数生成器、４…乱数メモリ、５…演算器、６…Ｈｉ’関数演算部、７…Ｇｉ関数演算部、８ｓ…公開鍵暗号署名生成部、８ｖ…公開鍵暗号署名検証部、９…秘密鍵メモリ、１０ｓ，１０ｖ…制御部、Ｓｇ１〜ＳｇＮ…署名生成装置、Ｖ…署名検証装置。
【図１】
2005210512.tif 000003
【図２】
2005210512.tif 000004
【図３】
2005210512.tif 000005
【図４】
2005210512.tif 000006
【図５】
2005210512.tif 000007
【図６】
2005210512.tif 000008
【図７】
2005210512.tif 000009
【図８】
2005210512.tif 000010
【図９】
2005210512.tif 000011
【図１０】
2005210512.tif 000012
【図１１】
2005210512.tif 000013
【図１２】
2005210512.tif 000014
【図１３】
2005210512.tif 000015
【図１４】
2005210512.tif 000016
【図１５】
2005210512.tif 000017
【図１６】
2005210512.tif 000018