(57)【要約】【課題】署名者のＩＤ情報に基づいて作成される公開鍵を多重署名に利用可能とする。【解決手段】センター装置１０は、ペアリングが定義可能な代数曲線のｎねじれ点の集合Ｅ[ｎ]の元であるＰ及びＱと、当該Ｐ及びＱと秘密情報ｓとから生成されたＰpub＝ｓＰ及びＱpub＝ｓＱと、署名者のＩＤ情報からマッピングされた＜Ｐ＞（点Ｐによって生成される巡回群）に属する点である当該署名者の公開鍵ＱIDiとを公開する。署名生成装置１１-i（ｉ＝１,２,…,ｎ）は、乱数ｋiと点Ｑとに依存する点Ｒiを、第１の署名データとして生成する。署名生成装置１１-iは、秘密鍵ＤIDi＝ｓＱIDiと、Ｍと、ｋiと、Ｒiと、Ｐpubとに基づいて、＜Ｐ＞に属する点Ｓiを第２の署名データとして生成する。署名検証装置１２は、Ｒi及びＳiのペアと、Ｍと、Ｑ、Ｐpub及びＱpubと、ＱIDiとに基づき、上記代数曲線上のペアリングを用いた署名検査式に従署名検査を行う。【選択図】      図１
2006203825.tif 000002
【特許請求の範囲】
【請求項１】
文書データＭに対する電子署名データを生成し、この電子署名データに基づいて署名検証を行う電子署名システムにおいて、
センター装置によって通信ネットワークを介して公開される情報であって、ペアリングが定義可能な代数曲線のｎねじれ点の集合Ｅ[ｎ]の元であるＰ及びＱと、当該Ｐ及びＱと秘密情報ｓとから生成された公開情報Ｐpub＝ｓＰ及びＱpub＝ｓＱと、署名者のＩＤ情報から特定の関数に従ってマッピングされた＜Ｐ＞（点Ｐによって生成される巡回群）に属する点である、当該署名者の公開鍵ＱIDiとを含む情報の少なくとも一部を利用して、文書データＭに対する電子署名データを生成する署名生成装置と、
前記署名生成装置によって生成された電子署名データと前記センター装置によって公開される情報の少なくとも一部とに基づいて署名検証を行う署名検証装置とを具備し、
前記署名生成装置は、
前記点Ｑによって生成される巡回群＜Ｑ＞に属する点Ｒiであって、乱数ｋiと前記点Ｑとに依存する点Ｒiを、第１の署名データとして生成する第１の署名生成手段と、
予め配布された秘密鍵ＤIDi＝ｓＱIDiであって、前記秘密情報ｓ及び前記公開鍵ＱIDiに基づき前記センター装置によって生成された秘密鍵ＤIDi＝ｓＱIDiと、前記文書データＭと、前記乱数ｋiと、前記点Ｒiと、前記公開情報Ｐpubとに基づいて、前記＜Ｐ＞に属する点Ｓiを第２の署名データとして生成する第２の署名生成手段とを有し、
前記署名検証装置は、前記署名装置によって生成された前記第１の署名データＲi及び前記第２の署名データＳiのペアと、前記文書データＭと、前記センター装置によって公開されている前記Ｑ、Ｐpub及びＱpubと、前記署名者の公開鍵ＱIDiとに基づいて、前記代数曲線上のペアリングを用いた署名検査式に従って署名を検査する署名検査手段を有する
ことを特徴とする電子署名システム。
【請求項２】
前記第２の署名生成手段は、
Ｓi＝ｆiＤIDi＋ｋiｇiＰpub
で定義される関係式（ｆiはＭ,Ｒiのうちの少なくともＭをハッシュ空間にマッピングするためのハッシュ関数、ｇiはＭ,Ｒiのうちの少なくともＲiをハッシュ空間にマッピングするためのハッシュ関数、ハッシュ空間はハッシュ関数の値域となるバイナリデータの集合）または当該関係式と等価な関係式に従って、前記第２の署名データを生成し、
前記署名検査手段は、
ｅ(Ｓi,Ｑ)＝ｅ(ｆiＱIDi,Ｑpub)ｅ(Ｐpub,ｇiＲi）
ここで、ｅ( , )は代数曲線のペアリング
で定義される関係式または当該関係式と等価な関係式に従って署名を検査する
ことを特徴とする請求項１記載の電子署名システム。
【請求項３】
前記文書データＭに対する電子署名データは、ｎ者から構成される複数の署名者の操作に従って生成されるものであり、
前記ＱIDi、前記ｋi及び前記ＤIDiは、それぞれｉ番目の署名者に対応した公開鍵、乱数及び秘密鍵であり、
前記Ｒi及び前記Ｓiは、それぞれｉ番目の署名者の第１及び第２の署名データであり、
前記第１の署名生成手段は、前記ｉ番目の署名者の第１の署名データＲiを、少なくとも前記乱数ｋiと、前記Ｑとに基づいて生成し、
前記第２の署名生成手段は、前記ｉ番目の署名者の第２の署名データＳiを、ｉ−１番目の署名者の第２の署名データＳi-1と、前記文書データＭと、１番目乃至ｎ番目の署名者の第１の署名データＲ1乃至Ｒnのうちの少なくとも一部と、前記ｉ番目の署名者の公開鍵ＤIDiと、前記ｉ番目の署名者に対応した乱数ｋiと、前記公開情報Ｐpubとに基づいて生成し、
前記署名検査手段は、前記Ｒ1乃至Ｒnのうちの少なくともＲnと、ｎ番目の署名者の第２の署名データＳnと、前記文書データＭと、前記Ｑ、Ｐpub及びＱpubと、１番目乃至ｎ番目の全ての署名者の公開鍵ＱID1乃至ＱIDnとに基づいて署名を検査する
ことを特徴とする請求項１記載の電子署名システム。
【請求項４】
前記第１の署名生成手段は、前記ｉ番目の署名者の第１の署名データＲiを、
Ｒi＝ｋiＱ
により生成し、
前記第２の署名生成手段は、前記ｉ番目の署名者の第２の署名データＳiを、
Ｓi＝Ｓi-1＋ｆiＤIDi＋ｋiｇiＰpub
で示される関係式（ｆiはＭ,Ｒ1,…Ｒiのうちの少なくともＭをハッシュ空間にマッピングするためのハッシュ関数、ｇiはＭ,Ｒ1,…Ｒiのうちの少なくともＲiをハッシュ空間にマッピングするためのハッシュ関数、ハッシュ空間はハッシュ関数の値域となるバイナリデータの集合）または当該関係式と等価な関係式に従って生成し、
前記署名検査手段は、
ｅ(Ｓn,Ｑ)＝ｅ(Σ(ｆjＱIDj),Ｑpub)ｅ(Ｐpub,Σ(ｇjＲj))
ここで、ｅ( , )は代数曲線のペアリング、Σ(ｆjＱIDj),はｊ＝１からｊ＝ｎまでのｆjＱIDjの和、,Σ(ｇjＲj)は、ｊ＝１からｊ＝ｎまでのｇjＲjの和
で定義される関係式または当該関係式と等価な関係式に従って署名を検査する
ことを特徴とする請求項３記載の電子署名システム。
【請求項５】
前記第１の署名生成手段は、前記ｉ番目の署名者の第１の署名データＲiを、ｉ-1番目の署名者の第１の署名データＲi-1と、前記乱数ｋi及び前記Ｑとに基づいて生成し、
前記第２の署名生成手段は、前記ｉ番目の署名者の第２の署名データＳiを、
Ｓi＝Ｓi-1＋ｆnＤIDi＋ｋiｇnＰpub
で示される関係式（ｆnはＭ,Ｒnのうちの少なくともＭをハッシュ空間にマッピングするためのハッシュ関数、ｇnはＭ,Ｒnのうちの少なくともＲnをハッシュ空間にマッピングするためのハッシュ関数、ハッシュ空間はハッシュ関数の値域となるバイナリデータの集合）または当該関係式と等価な関係式に従って生成し、
前記署名検査手段は、
ｅ(Ｓn,Ｑ)＝ｅ(Σ(ｆjＱIDj),Ｑpub)ｅ(Ｐpub,ｇjＲj)
ここで、ｅ( , )は代数曲線のペアリング
で定義される関係式または当該関係式と等価な関係式に従って署名を検査する
ことを特徴とする請求項３記載の電子署名システム。
【請求項６】
前記文書データＭに対する電子署名データは、ｎ者から構成される複数の署名者の操作に従って生成されるものであり、
前記ＱIDi、前記ｋi及び前記ＤIDiは、それぞれｉ番目の署名者に対応した公開鍵、乱数及び秘密鍵であり、
前記署名生成装置は、＜Ｐ＞に属する点であるｉ番目の署名者の順序鍵Ｇiを、ｉ−１番目の署名書の順序鍵Ｇi-1と、ｉ番目の署名者の公開鍵ＱIDiと、ｉ番目の署名者の秘密情報ｔiとに基づき生成する順序鍵生成手段を更に有し、
前記署名検証装置は、ｎ番目の署名者の順序鍵Ｇn及びｎ−１番目の署名書の順序鍵Ｇn-1と、ｎ番目の署名者の秘密情報ｔn及び前記点Ｑから生成される公開情報としての順序鍵検証情報Ａn＝ｔnＱと、ｎ番目の署名者の公開鍵ＱIDnとに基づいて、前記代数曲線上のペアリングを用いた順序鍵検査式に従って前記順序鍵Ｇnを検査する順序鍵検査手段を更に有し、
前記第１の署名生成手段は、前記ｉ番目の署名者の第１の署名データＲiを、前記ｉ番目の署名者の秘密情報ｔiと、ｉ-1番目の署名者の第１の署名データＲi-1と、前記乱数ｋi及び前記点Ｑとに基づいて生成し、
前記第２の署名生成手段は、前記ｉ番目の署名者の第２の署名データＳiを、前記ｉ番目の署名者の秘密情報ｔiと、ｉ−１番目の署名者の第２の署名データＳi-1と、前記ｉ番目の署名者の公開鍵ＤIDiと、前記文書データＭと、１番目乃至ｎ番目の署名者の第１の署名データＲ1乃至Ｒnのうちの少なくともＲnと、前記ｉ番目の署名者に対応した乱数ｋiと、前記公開情報Ｐpubとに基づいて生成し、
前記署名検査手段は、前記Ｒ1乃至Ｒnのうちの少なくともＲnと、ｎ番目の署名者の第２の署名データＳnと、前記ｎ番目の署名者の順序鍵Ｇnと、前記文書データＭと、前記Ｑ、Ｐpub及びＱpubとに基づいて署名を検査する
ことを特徴とする請求項１記載の電子署名システム。
【請求項７】
前記第１の署名生成手段は、前記ｉ番目の署名者の第１の署名データＲiを、
Ｒi＝ｔiＲi-1＋ｋiＱ
により生成し、
前記第２の署名生成手段は、前記ｉ番目の署名者の第２の署名データＳiを、
Ｓi＝ｔi(Ｓi-1＋ｆnＤIDi)＋ｋiｇnＰpub
で示される関係式（ｆnはＭ,Ｒ1,…Ｒnのうちの少なくともＭをハッシュ空間にマッピングするためのハッシュ関数、ｇnはＭ,Ｒ1,…Ｒnのうちの少なくともＲnをハッシュ空間にマッピングするためのハッシュ関数、ハッシュ空間はハッシュ関数の値域となるバイナリデータの集合）または当該関係式と等価な関係式に従って生成し、
前記署名検査手段は、
ｅ(Ｓn,Ｑ)＝ｅ(Ｇn,ｆnＱpub)ｅ(ｇnＰpub,Ｒn)
ここで、ｅ( , )は代数曲線のペアリング
で定義される関係式または当該関係式と等価な関係式に従って署名を検査する
ことを特徴とする請求項６記載の電子署名システム。
【請求項８】
前記文書データＭに対する電子署名データは、ｎ者から構成される複数の署名者の操作に従って生成されるものであり、
前記ＱIDi、前記ｋi及び前記ＤIDiは、それぞれｉ番目の署名者に対応した公開鍵、乱数及び秘密鍵であり、
前記第１の署名生成手段は、前記ｉ番目の署名者の第１の署名データＲiを、前記ｉ番目の署名者の秘密情報ｔiと、ｉ-1番目の署名者の第１の署名データＲi-1と、ｉ番目の署名者の公開鍵ＱIDiと、前記乱数ｋi及び前記点Ｑとに基づいて生成し、
前記署名生成装置は、ｉ−１番目の署名者の順序鍵Ｂi-1を、前記ｉ−１番目の署名書の第１の署名データＲi-1と、前記公開情報Ｑpubとに基づき、
Ｂi-1＝ｅ(Ｒi-1,Ｑpub)
により生成する順序鍵生成手段を更に有し、
前記第２の署名生成手段は、前記ｉ番目の署名者の第２の署名データＳiを、前記ｉ番目の署名者の秘密情報ｔiと、ｉ−１番目の署名者の第２の署名データＳi-1と、前記ｉ番目の署名者の公開鍵ＤIDiと、前記文書データＭと、１番目乃至ｎ番目の署名者の第１の署名データＲ1乃至Ｒnのうちの少なくともＲnと、前記ｉ番目の署名者に対応した乱数ｋiと、前記公開情報Ｐpubとに基づいて生成し、
前記署名検査手段は、ｎ番目の署名者の順序鍵Ｂnを、ｎ−１番目の署名者の第１の署名データＲn-1と、ｎ番目の署名者の公開鍵ＱIDnと、ｎ番目の署名者の秘密情報ｔn及び前記点Ｑから生成される公開情報としての順序鍵検証情報Ａn＝ｔnＱとに基づき、ペアリングを用いた順序鍵検査式
Ｂn＝ｅ(Ｒn-1＋ＱIDn,Ａn)
により検査する順序鍵検査手段を更に有し、
前記署名検査手段は、前記Ｒ1乃至Ｒnのうちの少なくともＲnと、ｎ番目の署名者の第２の署名データＳnと、前記文書データＭと、前記順序鍵検査手段によって正当であると判定された前記順序鍵Ｂnと、前記Ｐpubとに基づいて
ｅ(Ｓn,Ｑ)＝Ｂnｅ(ｇnＰpub,Ｒn)
ここで、ｅ( , )は代数曲線のペアリング、ｇnはＭ,Ｒ1,…Ｒnのうちの少なくともＭ及びＲnをハッシュ空間にマッピングするためのハッシュ関数、ハッシュ空間はハッシュ関数の値域となるバイナリデータの集合
で定義される関係式または当該関係式と等価な関係式に従って署名を検査する
ことを特徴とする請求項１記載の電子署名システム。
【請求項９】
センター装置によって通信ネットワークを介して公開される情報であって、ペアリングが定義可能な代数曲線のｎねじれ点の集合Ｅ[ｎ]の元であるＰ及びＱと、当該Ｐ及びＱと秘密情報ｓとから生成された公開情報Ｐpub＝ｓＰ及びＱpub＝ｓＱと、署名者のＩＤ情報から特定の関数に従ってマッピングされた＜Ｐ＞（点Ｐによって生成される巡回群）に属する点である、当該署名者の公開鍵ＱIDiとを含む情報の少なくとも一部を利用して、文書データＭに対する電子署名データを生成し、この電子署名データに基づいて署名検証を行う電子署名方法であって、
前記点Ｑによって生成される巡回群＜Ｑ＞に属する点Ｒiであって、乱数ｋiと前記点Ｑとに依存する点Ｒiを、前記通信ネットワークに接続された署名生成装置によって第１の署名データとして生成するステップと、
予め配布された秘密鍵ＤIDi＝ｓＱIDiであって、前記秘密情報ｓ及び前記公開鍵ＱIDiに基づき前記センター装置によって生成された秘密鍵ＤIDi＝ｓＱIDiと、前記文書データＭと、前記乱数ｋiと、前記点Ｒiと、前記公開情報Ｐpubとに基づいて、前記＜Ｐ＞に属する点Ｓiを前記署名生成装置によって第２の署名データとして生成するステップと、
前記第１の署名データＲi及び前記第２の署名データＳiのペアと、前記文書データＭと、前記センター装置によって公開されている前記Ｑ、Ｐpub及びＱpubと、前記署名者の公開鍵ＱIDiとに基づいて、前記代数曲線上のペアリングを用いた署名検査式に従って署名を前記通信ネットワークに接続された署名検証装置によって検査するステップと
を具備することを特徴とする電子署名方法。
【請求項１０】
前記文書データＭに対する電子署名データは、ｎ者から構成される複数の署名者の操作に従って生成されるものであり、
前記ＱIDi、前記ｋi及び前記ＤIDiは、それぞれｉ番目の署名者に対応した公開鍵、乱数及び秘密鍵であり、
前記Ｒi及び前記Ｓiは、それぞれｉ番目の署名者の第１及び第２の署名データであり、
前記ｉ番目の署名者の第１の署名データＲiは、ｉ番目の署名者に対応した署名生成装置によって、少なくとも前記乱数ｋiと、前記Ｑとに基づいて生成され、
前記ｉ番目の署名者の第２の署名データＳiは、ｉ−１番目の署名者の第２の署名データＳi-1と、前記文書データＭと、１番目乃至ｎ番目の署名者の第１の署名データＲ1乃至Ｒnのうちの少なくとも一部を受けて、ｉ番目の署名者に対応した署名生成装置によって、前記Ｓi-1と、前記Ｍと、前記Ｒ1乃至Ｒnのうちの少なくとも一部と、前記ｉ番目の署名者の公開鍵ＤIDiと、前記ｉ番目の署名者に対応した乱数ｋiと、前記公開情報Ｐpubとに基づいて生成され、
前記署名の検査は、前記Ｒ1乃至Ｒnのうちの少なくともＲnと、ｎ番目の署名者の第２の署名データＳnと、前記文書データＭとを受けて、前記署名検査装置によって、前記Ｒ1乃至Ｒnのうちの少なくともＲnと、前記Ｓnと、前記Ｑ、Ｐpub及びＱpubと、１番目乃至ｎ番目の全ての署名者の公開鍵ＱID1乃至ＱIDnとに基づいて行われる
ことを特徴とする請求項９記載の電子署名方法。
【請求項１１】
センター装置によって通信ネットワークを介して公開される情報であって、ペアリングが定義可能な代数曲線のｎねじれ点の集合Ｅ[ｎ]の元であるＰ及びＱと、当該Ｐ及びＱと秘密情報ｓとから生成された公開情報Ｐpub＝ｓＰ及びＱpub＝ｓＱと、署名者のＩＤ情報から特定の関数に従ってマッピングされた＜Ｐ＞（点Ｐによって生成される巡回群）に属する点である、当該署名者の公開鍵ＱIDiとを含む情報の少なくとも一部を利用して、文書データＭに対する電子署名データを生成し、この電子署名データに基づいて署名検証を行うのに用いられるプログラムであって、
コンピュータに、
前記点Ｑによって生成される巡回群＜Ｑ＞に属する点Ｒiであって、乱数ｋiと前記点Ｑとに依存する点Ｒiを、第１の署名データとして生成するステップと、
予め配布された秘密鍵ＤIDi＝ｓＱIDiであって、前記秘密情報ｓ及び前記公開鍵ＱIDiに基づき前記センター装置によって生成された秘密鍵ＤIDi＝ｓＱIDiと、前記文書データＭと、前記乱数ｋiと、前記点Ｒiと、前記公開情報Ｐpubとに基づいて、前記＜Ｐ＞に属する点Ｓiを前記署名生成装置によって第２の署名データとして生成するステップと、
前記第１の署名データＲi及び前記第２の署名データＳiのペアと、前記文書データＭと、前記センター装置によって公開されている前記Ｑ、Ｐpub及びＱpubと、前記署名者の公開鍵ＱIDiとに基づいて、前記代数曲線上のペアリングを用いた署名検査式に従って署名を前記通信ネットワークに接続された署名検証装置によって検査するステップと
実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書データに対する電子署名データを作成し、この電子署名データに基づいて署名検証を行う電子署名システムに係り、特に複数の署名者が関与する多重署名に好適な電子署名システム、電子署名方法及びプログラムに関する。
【背景技術】
【０００２】
従来から、電子署名の作成法として様々な方法が考案されている。署名の中には、稟議書や契約書等複数の署名を必要とするものがある。その電子版で、単純に個々の電子署名を連結したものよりも署名長を短くできるものは、多重署名と呼ばれる。この多重署名についても、様々な方法が提案されている。例えば、特許文献１及び非特許文献１には、署名者の順番を問わない多重署名方式が記載されている。特許文献１に記載された多重署名方式は、ElGamal署名方式の変形であり、ElGamal型多重署名方式と呼ぶことができる。
【０００３】
更に、非特許文献２には、特許文献１または非特許文献１に記載の多重署名方式と異なって、署名者の順番を固定とした縦列型の多重署名方式が記載されている。
【０００４】
一方暗号・署名技術においては、公開鍵とそれに対応する秘密鍵の所有者を結び付ける方法の１つとして、所有者のＩＤ情報から公開鍵を作成する方法が知られている。これを用いる場合は、通常ＰＫＩ（Public Key Infrastructure：公開鍵認証基盤）等で用いられる公開鍵証明書等は不用になり、より簡易なセキュリティシステムの構築が可能になる、という利点がある。
【０００５】
ＩＤ情報に基づく暗号・署名技術については、近年楕円曲線のペアリングを用いた方式が多数考案されている。例えば署名については、特許文献２にElGamal型署名とSchnorr型署名が記載され、非特許文献３にElGamal型署名が記載されている。
【特許文献１】特開平１０−１５３９５６号公報（段落００１８）
【特許文献２】特開２００４−２０１１２４号公報（段落００６０乃至００６６、段落００６７乃至００７６）
【非特許文献１】K. Ohta and T. Okamoto,“Multisignature schemes secure aganst active insider attacks”, IEICE Trans. Fundamentals Vol. E82-A (1999), No.1, pp.21-31O
【非特許文献２】M. Burmester, Y. Desmedt, H.Doi, M. Mambo, E. Okamoto, M. Tada, and Y. Yoshifuji,“A Structured ElGamal-Type Multisignature Scheme”,PKC2000, LNCS 1751, Springer-Verlag (2000), pp.466-483
【非特許文献３】K. G. Paterson, “ID-based signatures from pairings on elliptic curves”, Electronics Letters 38(18) (2002), pp.1025-1026
【発明の開示】
【発明が解決しようとする課題】
【０００６】
そこで、上記特許文献２または非特許文献３に記載されたＩＤ情報に基づく署名技術を、特許文献１、非特許文献１または非特許文献２に記載の多重署名方式に適用することが考えられる。しかしながら、特許文献２または非特許文献２に記載されたＩＤ情報に基づく署名技術は、ElGamal署名に類似した方式であり、その方式のままでは多重署名を構築することには向いていない。
【０００７】
本発明は上記事情を考慮してなされたものでその目的は、署名者の検証用の鍵としてＩＤ情報に基づいて作成される公開鍵を多重署名に利用可能な電子署名システム、電子署名方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明の１つの観点によれば、文書データＭに対する電子署名データを生成し、この電子署名データに基づいて署名検証を行う電子署名システムが提供される。このシステムは、センター装置によって通信ネットワークを介して公開される情報であって、ペアリングが定義可能な代数曲線のｎねじれ点の集合Ｅ[ｎ]の元であるＰ及びＱと、当該Ｐ及びＱと秘密情報ｓとから生成された公開情報Ｐpub＝ｓＰ及びＱpub＝ｓＱと、署名者のＩＤ情報から特定の関数に従ってマッピングされた＜Ｐ＞（点Ｐによって生成される巡回群）に属する点である、当該署名者の公開鍵ＱIDiとを含む情報の少なくとも一部を利用して、文書データＭに対する電子署名データを生成する署名生成装置と、上記署名生成装置によって生成された電子署名データと上記センター装置によって公開される情報の少なくとも一部とに基づいて署名検証を行う署名検証装置とを具備する。上記署名生成装置は第１及び第２の署名生成手段を有し、上記署名検証装置は署名検査手段を有する。
【０００９】
上記第１の署名生成手段は、上記点Ｑによって生成される巡回群＜Ｑ＞に属する点Ｒiであって、乱数ｋiと上記点Ｑとに依存する点Ｒiを、第１の署名データとして生成する。上記第２の署名生成手段は、予め配布された秘密鍵ＤIDi＝ｓＱIDiであって、上記秘密情報ｓ及び上記公開鍵ＱIDiに基づき上記センター装置によって生成された秘密鍵ＤIDi＝ｓＱIDiと、上記文書データＭと、上記乱数ｋiと、上記点Ｒiと、上記公開情報Ｐpubとに基づいて、上記＜Ｐ＞に属する点Ｓiを第２の署名データとして生成する。上記署名検査手段は、上記署名装置によって生成された上記第１の署名データＲi及び上記第２の署名データＳiのペアと、上記文書データＭと、上記センター装置によって公開されている上記Ｑ、Ｐpub及びＱpubと、上記署名者の公開鍵ＱIDiとに基づいて、上記代数曲線上のペアリングを用いた署名検査式に従って署名を検査する。
【００１０】
このような構成においては、＜Ｑ＞に属する点が第１の署名データＲiとして生成され、＜Ｐ＞に属する点が第２の署名データＳiとして生成される。この第２の署名データＳiには、署名者のＩＤ（＝ＩＤi）がマッピングされた＜Ｐ＞に属する点である公開鍵ＱIDiと秘密情報ｓとに基づいて生成された秘密鍵ＤIDi＝ｓＱIDiが反映されている。このＳiとＰiのペアが署名データとして用いられて、文書データＭと、Ｑ、Ｐpub及びＱpubと、公開鍵ＱIDiとに基づいて、代数曲線（例えば楕円曲線）上のペアリングを用いた署名検査式に従って署名検査が行われる。これにより、署名者の検証用の鍵としてＩＤ情報に基づいて作成される公開鍵ＱIDiを多重署名に利用することが可能となる。
【００１１】
そこで、上記文書データＭに対する電子署名データが、ｎ者から構成される複数の署名者の操作に従って生成されるものであり、上記ＱIDi、上記ｋi及び上記ＤIDiは、それぞれｉ番目の署名者に対応した公開鍵、乱数及び秘密鍵であり、上記Ｒi及び上記Ｓiは、それぞれｉ番目の署名者の第１及び第２の署名データであるものとする。この場合、上記第１の署名生成手段は、上記ｉ番目の署名者の第１の署名データＲiを、少なくとも上記乱数ｋiと、上記Ｑとに基づいて生成するように構成され、上記第２の署名生成手段は、上記ｉ番目の署名者の第２の署名データＳiを、ｉ−１番目の署名者の第２の署名データＳi-1と、上記文書データＭと、１番目乃至ｎ番目の署名者の第１の署名データＲ1乃至Ｒnのうちの少なくとも一部と、上記ｉ番目の署名者の公開鍵ＤIDiと、上記ｉ番目の署名者に対応した乱数ｋiと、上記公開情報Ｐpubとに基づいて生成するように構成される。また、上記署名検査手段は、上記Ｒ1乃至Ｒnのうちの少なくともＲnと、ｎ番目の署名者の第２の署名データＳnと、上記文書データＭと、上記Ｑ、Ｐpub及びＱpubと、１番目乃至ｎ番目の全ての署名者の公開鍵ＱID1乃至ＱIDnとに基づいて署名を検査するように構成される。このような構成により、ＱIDiを利用した多重署名が実現できる。
【００１２】
代数曲線上のペアリングを用いた署名検査式としては、例えばｉ番目の署名者の第２の署名データＳiが、
Ｓi＝Ｓi-1＋ｆiＤIDi＋ｋiｇiＰpub
で示される関係式（ｆiはＭ,Ｒ1,…Ｒiのうちの少なくともＭをハッシュ空間にマッピングするためのハッシュ関数、ｇiはＭ,Ｒ1,…Ｒiのうちの少なくともＲiをハッシュ空間にマッピングするためのハッシュ関数、ハッシュ空間はハッシュ関数の値域となるバイナリデータの集合）または当該関係式と等価な関係式に従って生成される構成とするならば、
ｅ(Ｓn,Ｑ)＝ｅ(Σ(ｆjＱIDj),Ｑpub)ｅ(Ｐpub,Σ(ｇjＲj))
ここで、ｅ( , )は代数曲線のペアリング、Σ(ｆjＱIDj),はｊ＝１からｊ＝ｎまでのｆjＱIDjの和、,Σ(ｇjＲj)は、ｊ＝１からｊ＝ｎまでのｇjＲjの和
で定義される関係式または当該関係式と等価な関係式を用いることが可能である。
【００１３】
また、ｉ番目の署名者の第２の署名データＳiが、
Ｓi＝Ｓi-1＋ｆnＤIDi＋ｋiｇnＰpub
で示される関係式（ｆnはＭ,Ｒnのうちの少なくともＭをハッシュ空間にマッピングするためのハッシュ関数、ｇnはＭ,Ｒnのうちの少なくともＲnをハッシュ空間にマッピングするためのハッシュ関数、ハッシュ空間はハッシュ関数の値域となるバイナリデータの集合）または当該関係式と等価な関係式に従って生成される構成とするならば、代数曲線上のペアリングを用いた署名検査式としては、例えば
ｅ(Ｓn,Ｑ)＝ｅ(Σ(ｆnＱIDj),Ｑpub)ｅ(Ｐpub,ｇnＲj)
ここで、ｅ( , )は代数曲線のペアリング
で定義される関係式または当該関係式と等価な関係式を用いることが可能である。
【００１４】
なお、上記した電子署名システムに係る発明は、当該システムで実現される電子署名の手順を実行する電子署名方法に係る発明として捉えることも、当該方法で適用される電子署名の手順をコンピュータに実行させるためのプログラムの発明として捉えることも可能である。
【発明の効果】
【００１５】
本発明によれば、ペアリングが定義可能な代数曲線のｎねじれ点の集合Ｅ[ｎ]の元であるＰ及びＱのうちのＰによって生成される巡回群＜Ｐ＞に属する点に、署名者のＩＤ情報をマッピングすることで得られる公開鍵を第２の署名データＳiに反映させて、当該第２の署名データＳiを＜Ｐ＞に属する点とすると共に、第２の署名データＳiとペアをなす第１の署名データを乱数ｋiと点Ｑとに依存する点、つまり＜Ｑ＞に属する点とし、代数曲線上のペアリングを用いた署名検査式に従って署名を検査することにより、署名者のＩＤ情報から変換された公開鍵を多重署名に利用することが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態につき図面を参照して説明する。  
まず、本発明の実施の形態で適用される楕円曲線のペアリング（ベイユペアリング）について説明する。有限体（有限体ベクトル）Ｆq上の楕円曲線Ｅについて、当該楕円曲線のｎねじれ点の集合Ｅ[ｎ]の２点（元）Ｐ,Ｑをとる。ペアリングｅ( , )＝ｅn( , )は、Ｅ[ｎ]の元Ｐ,ＱからＦqまたはその拡大体に含まれる位数ｎの乗法群（Ｆqn）への写像ｅ(Ｐ,Ｑ)であり、以下の性質を有する。点は全て集合Ｅ[ｎ]内で考える。
【００１７】
（非退化）
ある点Ｐが任意の点Ｑに対して、ｅ(Ｐ,Ｑ)＝１を満たすとき、Ｐ＝０である。
【００１８】
（反対称）
任意の点Ｐ,Ｑに対して、
ｅ(Ｐ,Ｑ)＝ｅ(Ｑ,Ｐ)＾(−１)
ｅ(Ｐ,Ｐ)＝ｅ(Ｑ,Ｑ)＝１
が成立する。但し、ｅ(Ｑ,Ｐ)＾(−１)は、ｅ(Ｑ,Ｐ)の−１乗、つまりｅ(Ｑ,Ｐ)-1を表す。このように本実施形態では、Ｘa（Ｘのａ乗）をＸ＾ａで表現する。なお、Ｘaの表現形式を用いることもある。
【００１９】
（双線形）
任意の点Ｐ,Ｑ,Ｒに対して、
ｅ(Ｐ＋Ｑ,Ｒ)＝ｅ(Ｐ,Ｒ)ｅ(Ｑ,Ｒ)
ｅ(Ｐ,Ｑ＋Ｒ)＝ｅ(Ｐ,Ｑ)ｅ(Ｐ,Ｒ)
が成立する。
【００２０】
特に、Ｆqの元ａに対して、
ｅ(ａＰ,Ｑ)＝ｅ(Ｐ,ａＱ)＝ｅ(Ｐ,Ｑ)＾ａ
が成立する。
【００２１】
楕円曲線上のペアリングを暗号・署名に応用する場合は、以下のような条件
１．ｎの最大素因子は１６０ビット以上
２．ｑ＞２1024
３．Ｅ[ｎ]はＦqのいかなる部分体上の楕円曲線の点の成す群にも含まれない。
【００２２】
を満たすように楕円曲線Ｅとｎねじれ群Ｅ[ｎ]を選ぶことが好ましい。
【００２３】
以下、上記の楕円曲線のペアリングの性質を多重署名に利用した本発明の一実施形態について説明する。図１は本発明の一実施形態に係る電子署名システムの基本構成を示すブロック図である。図１のシステムは、センター装置１０と、署名生成装置１１-1乃至１１-nと、署名検証装置１２とから構成される。センター装置１０、署名生成装置１１-1乃至１１-n及び署名検証装置１２は、通信ネットワーク１３により接続されている。本実施形態では、説明を簡略化するために、１番目乃至ｎ番目の署名者によって利用される署名生成装置が、それぞれ署名生成装置１１-1乃至１１-nであるものとする。つまりｉ番目(ｉ＝１,２,…,ｎ)の署名者は、署名生成装置１１-iを利用するものとする。このｉ番目の署名者の識別情報（ＩＤ）をＩＤiと表現する。
【００２４】
センター装置１０は、公開情報と秘密情報ｓとを予め準備する。公開情報は、楕円曲線Ｅのパラメータを含む。公開情報はまた、Ｐ,Ｐpub,Ｑ,Ｑpub,Ｈ1,Ｈ2及びＨ3の各パラメータを含む。公開情報はセンター装置１０の記憶装置（図示せず）に格納されており、署名生成装置１１-1乃至１１-n及び署名検証装置１２から通信ネットワーク１３を介して読み出すことが可能である。
【００２５】
上記Ｐ,Ｑは、上述したように有限体Ｆq上の楕円曲線Ｅのｎねじれ点の集合Ｅ[ｎ]の元で、Ｑは＜Ｐ＞（点Ｐによって生成される巡回群）に属さないものとする。この場合、点Ｑによって生成される巡回群を＜Ｑ＞で表すと、Ｅ[ｎ]はａＰ＋ｂＱ（ａ,ｂは整数）の形の点の集合となる。これをＥ[ｎ]＝＜Ｐ＞＋＜Ｑ＞で表す。また、Ｈ1は、署名者のＩＤを＜Ｐ＞の元へ写像するための関数、Ｈ2及びＨ3は、それぞれ、文書データ（平文、メッセージ）Ｍ及び署名（第１の署名データ）Ｒをハッシュ空間にマッピングするためのハッシュ関数である。本実施形態では、ハッシュ空間とはハッシュ関数の値域となるバイナリデータの集合であると定義される。
【００２６】
またＰpub,Ｑpubは、それぞれ次式
Ｐpub＝ｓＰ
Ｑpub＝ｓＱ
を満たす点である。
【００２７】
センター装置１０は、ｉ（ｉ＝１,２,…,ｎ）番目の署名者（署名者ｉ）のＩＤ、つまりＩＤiと、関数Ｈ1とに基づき、ｉ番目の署名者の公開鍵ＱIDiを次式
ＱIDi＝Ｈ1(ＩＤi)
に従って計算する。ＱIDiは、ＩＤiの＜Ｐ＞の元に対する写像、つまり＜Ｐ＞に属する点であることに注意されたい。センター装置１０は、この公開鍵ＱIDiと秘密情報ｓとに基づき、ｉ番目の署名者の秘密鍵ＤIDiを次式
ＤIDi＝ｓＱIDi
に従って計算する。つまりセンター装置１０は、ＩＤiとＨ1と秘密情報ｓとに基づき、秘密鍵ＤIDiをＤIDi＝ｓＨ1(ＩＤi)の計算により取得する。この秘密鍵ＤIDiも＜Ｐ＞に属する点であることに注意されたい。
【００２８】
公開鍵ＱIDiと秘密鍵ＤIDiとのペアを、ＩＤがＩＤiであるｉ番目の署名者の鍵ペアと呼ぶ。この鍵ペアは、多重署名の場合には、署名者の数だけ用意される。
【００２９】
秘密鍵ＤIDiは、署名生成装置１１-iを利用するｉ番目の署名者に秘密裏に配布される。これにより、署名生成装置１１-1乃至１１-nの後述する秘密鍵記憶装置１１０には、それぞれ、１番目乃至ｎ番目の署名者のＩＤ、つまりＩＤ１乃至ＩＤｎに対応した秘密鍵ＤID1乃至ＤIDnが格納される。
【００３０】
署名生成装置１１-i（ｉ＝１,２,…,ｎ）は、文書データＭに対する電子署名データを生成する。署名検証装置１２は、電子署名データに基づいて署名検証を行う。本実施形態では、署名生成装置１１-iにおいても署名検証が行われる。そのため署名生成装置１１-iは署名検証機能を有する。そこで本実施形態では、署名生成装置１１-iの署名検証機能を利用して、署名検証装置１２を実現している。つまり署名生成装置１１-iと署名検証装置１２とは共通の構成を有する。ここでは、署名生成装置１１-iを署名検証装置１２として用いることも、逆に署名検証装置１２を署名生成装置１１-iとして用いることも可能である。また、署名生成装置１１-1〜１１-nの１つを署名検証装置１２として兼用することも可能である。勿論、署名検証装置１２を署名生成装置１１-iとは異なる構成の専用の装置とすることも可能である。
【００３１】
図２は、署名生成装置１１-1〜１１-n及び署名検証装置１２の構成を示すブロック図である。署名生成装置１１-1〜１１-n及び署名検証装置１２は、それぞれ、秘密鍵記憶装置１１０と、記憶装置１１１と、公開情報読出部１１２と、乱数生成部１１３と、第１署名部１１４と、第２署名部１１５と、署名受信部１１６と、署名送信部１１７と、公開鍵計算部１１８と、署名検査部１１９と、制御部１２０と、順序鍵生成部１２１と、順序鍵検査部１２２とから構成される。
【００３２】
秘密鍵記憶装置１１０は、当該記憶装置１１０を有する装置が署名生成装置１１-iの場合に、秘密鍵ＤIDiを格納するのに用いられる。記憶装置１１１は、公開情報記憶部１１１ａ、公開鍵記憶部１１１ｂ及び署名記憶部１１１ｃの各記憶部として用いられる記憶領域を有する。公開情報記憶部１１１ａは、センター装置１０によって公開されている公開情報を格納するのに用いられ、公開鍵記憶部１１１ｂは公開情報に基づいて生成される公開鍵（の情報）を格納するのに用いられる。署名記憶部１１１ｃは、署名送信部１１７によって受信された（または第１署名部１１４もしくは第２署名部１１５によって生成された）署名（署名データ）を格納するのに用いられる。
【００３３】
公開情報読出部１１２はセンター装置１０または公開情報記憶部１１１ａから公開情報を読み出す。乱数生成部１１３は署名生成に必要な乱数ｋiを生成する。第１署名部１１４は、第１の署名（署名データ）Ｒiを生成する。Ｒiは、乱数ｋiと点Ｑとに依存する。第２署名部１１５は、少なくとも公開情報Ｐpubと秘密鍵ＤIDと文書データＭとを用いて第２の署名（署名データ）Ｓiを生成する。これら両署名部１１４及び１１５は、当該署名部１１４及び１１５を有する装置が署名生成装置１１-iの場合に用いられる。
【００３４】
署名受信部１１６は、当該署名受信部１１６を有する装置（署名生成装置１１-iまたは署名検証装置１２）宛ての署名（署名データ）を通信ネットワーク１３から受信する。署名送信部１１７は、当該署名受信部１１６を有する装置が署名生成装置１１-iの場合に用いられ、署名生成装置１１-(i+1)または署名検証装置１２に署名（署名データ）を送信する。
【００３５】
公開鍵計算部１１８は、センター装置１０と同様に、ＩＤiと関数Ｈ1とに基づき、ｉ番目の署名者の公開鍵ＱIDi＝Ｈ1(ＩＤi)を計算する。関数Ｈ1は、センター装置１０から取得可能である。署名検査部１１９は、当該署名検査部１１９を有する装置が署名生成装置１１-iの場合には、署名生成装置１１-(i-1)によって生成された署名を少なくとも検査（検証）し、当該署名検査部１１９を有する装置が署名検証装置１２の場合には、署名生成装置１１-nによって生成された署名を少なくとも検査する。制御部１２０は、当該制御部１２０を有する装置における署名生成または署名検証を制御する。順序鍵生成部１２１及び順序鍵検査部１２２は、後述する縦列型の多重署名法を適用する場合に必要となるもので、ここでの説明は省略する。
【００３６】
公開情報読出部１１２、乱数生成部１１３、第１署名部１１４、第２署名部１１５、署名受信部１１６、署名送信部１１７、公開鍵計算部１１８、署名検査部１１９、制御部１２０、順序鍵生成部１２１及び順序鍵検査部１２２は、コンピュータにインストールされた所定のソフトウェアプログラムを当該コンピュータ（内のＣＰＵ）が読み取って実行することにより実現される。このプログラムは、コンピュータで読み取り可能な記憶媒体に予め格納して頒布可能である。また、このプログラムが、ネットワークを介してダウンロード（頒布）されても構わない。
【００３７】
＜変形ElGamal署名＞
次に、図１のシステムにおけるＩＤをベースとした変形ElGamal署名について図３のフローチャートを参照して説明する。まず、署名生成装置１１-i（ｉ＝１,２,…,ｎ）による署名生成について説明する。この署名生成は、署名生成装置１１-1乃至１１-nに共通である。そこで、署名生成装置１１-iを利用する署名者、つまりｉ番目の署名者の識別情報ＩＤiをＩＤと表現する。
【００３８】
公開情報読出部１１２は、センター装置１０から公開情報であるＱ,Ｐpub,Ｈ2,Ｈ3を読み出す（ステップＳ１）。センター装置１０から読み出された公開情報は、署名生成装置１１-iで利用可能なように、記憶装置１１１の公開情報記憶部１１１ａに格納される。これにより、次回からは、上述の公開情報を公開情報記憶部１１１ａから速やかに読み出すことができる。
【００３９】
乱数生成部１１３は乱数ｋを生成する（ステップＳ２）。すると第１署名部１１４は、次式
Ｒ＝ｋＱ
に従う計算によって、乱数ｋと点Ｑとに依存する点Ｒを署名（第１の署名データ）として生成する（ステップＳ３）。Ｒは＜Ｑ＞に属する点である。
【００４０】
一方、第２署名部１１５は、乱数ｋと、点Ｒと、公開情報Ｐpubと、秘密鍵ＤIDと、ハッシュ関数Ｈ2及びＨ3と、平文Ｍとを用いて、次式
Ｓ＝Ｈ2(Ｍ)ＤID＋ｋＨ3(Ｒ)Ｐpub                              …（１）
に従う計算を行うことによって、署名（第２の署名データ）Ｓを生成する（ステップＳ４）。上記式（１）の右辺第１項Ｈ2(Ｍ)ＤID及び右辺第２項ｋＨ3(Ｒ)Ｐpubは、いずれも＜Ｐ＞に属する点を表す。したがって、署名Ｓは＜Ｐ＞に属する点である。このようにして、署名生成装置１１-iは署名（Ｓ,Ｒ）を生成する。
【００４１】
次に、署名生成装置１１-iまたは署名検証装置１２による署名検証について説明する。まず、公開情報読出部１１２は、センター装置１０から公開情報としてＱ,Ｑpub,Ｐpub,Ｈ1,Ｈ2,Ｈ3を読み出す（ステップＳ１１）。ここで、Ｑ,Ｐpub,Ｈ2,Ｈ3は、先のＲの計算に際してセンター装置１０から読み出されて公開情報記憶部１１１ａに格納されていることから、当該公開情報記憶部１１１ａから読み出すことも可能である。
【００４２】
公開鍵計算部１１８は、関数Ｈ1と署名Ｓの署名者のＩＤとに基づき、次式
ＱID＝Ｈ1(ＩＤ)
に従って当該署名者の公開鍵ＱIDを計算する（ステップＳ１２）。上記したようにＨ1は公開されていることから、公開鍵ＱIDはＩＤから誰でも（署名生成装置１１-1乃至１１-n及び署名検証装置１２のいずれでも）計算可能である。計算された公開鍵ＱIDは、署名生成装置１１-iにおいて利用可能なように公開鍵記憶部１１１ｂに格納される。
【００４３】
署名検査部１１９は、公開鍵ＱIDと、平文Ｍと、公開情報であるＱ,Ｑpub,Ｐpub,Ｈ2及びＨ3とに基づき、次式
ｅ(Ｓ,Ｑ)＝ｅ(ＱID,Ｑpub)＾Ｈ2(Ｍ)ｅ(Ｐpub,Ｒ)＾Ｈ3(Ｒ)      …（２）
ここで、ｅ( , )は楕円曲線のペアリングを表す
が成立するか否かを検査する（ステップＳ１３）。
【００４４】
署名検査部１１９は、上記式（２）が成立する場合は、署名（Ｓ,Ｒ）が正当であると判定する。これに対して、上記式（２）が成立しない場合は、署名検査部１１９は、署名（Ｓ,Ｒ）は正しくないと判定する。
【００４５】
ここで、上記式（２）が成立するか否かにより署名（Ｓ,Ｒ）が検証できることを証明する。まず、署名（Ｓ,Ｒ）、即ち
Ｒ＝ｋＱ，Ｓ＝Ｈ2(Ｍ)ＤID＋ｋＨ3(Ｒ)Ｐpub
から、式（２）が導かれることを証明する。
【００４６】
式（２）の左辺のｅ(Ｓ,Ｑ)は、Ｓ＝Ｈ2(Ｍ)ＤID＋ｋＨ3(Ｒ)Ｐpubを代入すると、次式
ｅ(Ｓ,Ｑ)＝ｅ(Ｈ2(Ｍ)ＤID＋ｋＨ3(Ｒ)Ｐpub,Ｑ)
＝ｅ(Ｈ2(Ｍ)ＤID,Ｑ)ｅ(ｋＨ3(Ｒ)Ｐpub,Ｑ)          …（３）
のように表される。
【００４７】
また、
ＤID＝ｓＱID，Ｐpub＝ｓＰ
であることから、上記式（３）は、次式
ｅ(Ｓ,Ｑ)＝ｅ(ｓＨ2(Ｍ)ＱID,Ｑ)ｅ(ｓｋＨ3(Ｒ)Ｐ,Ｑ)        …（４）
のように表される。また、ペアリングの性質（双線形）から、上記式（４）は、次式
ｅ(Ｓ,Ｑ)＝ｅ(Ｈ2(Ｍ)ＱID,Ｑ)sｅ(ｋＨ3(Ｒ)Ｐ,Ｑ)s
＝ｅ(Ｈ2(Ｍ)ＱID,sＱ)ｅ(sＨ3(Ｒ)Ｐ,ｋＱ)          …（５）
のように表される。
【００４８】
また、
Ｑpub＝ｓＱ，  Ｐpub＝ｓＰ，  Ｒ＝ｋＱ
であることとペアリングの性質（双線形）から、上記式（５）は、次式
ｅ(Ｓ,Ｑ)＝ｅ(Ｈ2(Ｍ)ＱID,Ｑpub)ｅ(Ｈ3(Ｒ)Ｐpub,Ｒ)
＝ｅ(ＱID,Ｑpub)＾Ｈ2(Ｍ)ｅ(Ｐpub,Ｒ)＾Ｈ3(Ｒ)
のように表される。これにより、Ｒ＝ｋＱ，Ｓ＝Ｈ2(Ｍ)ＤID＋ｋＨ3(Ｒ)Ｐpub
から、式（２）が導かれることが証明された。
【００４９】
次に、その逆の証明を行う。そのためには、問題を一般化してペアリングの性質を考えると、＜Ｐ＞に属する点Ａ,Ｂについて、ｅ(Ａ,Ｑ)＝ｅ(Ｂ,Ｑ)のときＡ＝Ｂとなることを示せば良い。ここで、ｅ(Ｐ,Ｑ)はＥ[ｎ]から１のｎ乗根への写像となっていることに注意する。
【００５０】
まず、Ａ＝ａＰ,Ｂ＝ｂＰと表すことができる。したがってｅ(Ａ,Ｑ)＝ｅ(Ｂ,Ｑ)
は、
ｅ(ａＰ,Ｑ)＝ｅ(ｂＰ,Ｑ)
と表すことができる。よってｅ(ａＰ,Ｑ)＝ｅ(ｂＰ,Ｑ)は、
ｅ(Ｐ,Ｑ)＾ａ＝ｅ(Ｐ,Ｑ)＾ｂ
と表すことができる。
【００５１】
ａ,ｂはｎの約数で、ｅ(Ｐ,Ｑ)は１のｎ乗根であるので、ｅ(Ｐ,Ｑ)＝１でないならば、ａ＝ｂとなり、したがってＡ＝Ｂとなる。これにより、式（２）が成立するならば、Ｒ＝ｋＱ，Ｓ＝Ｈ2(Ｍ)ＤID＋ｋＨ3(Ｒ)Ｐpubであることが証明された。
【００５２】
ここで、ｅ(Ｐ,Ｑ)＝１でないと仮定したのは次のような理由による。もしｅ(Ｐ,Ｑ)＝１であるとすると、Ｅ[ｎ]の全ての元Ｃ＝ａＰ＋ｂＱ、Ｄ＝ｃＰ＋ｄＱについて
ｅ(Ｃ,Ｄ)＝ｅ(Ｐ,Ｐ)＾ａ×ｅ(Ｑ,Ｑ)＾ｂ×ｅ(Ｐ,Ｑ)＾(ａｄ＋ｂｄ)
＝１
となってしまう。そこで、ｅ(Ｐ,Ｑ)＝１でないという仮定が設けられる。
【００５３】
なお、署名生成及び署名検証に、それぞれ上記式（１）及び（２）と等価な関係式を用いることも可能である。例えば、式（２）と等価な関係式として、
ｅ(Ｓ,Ｑ)＝ｅ(Ｈ2(Ｍ)ＱID,Ｑpub)ｅ(Ｐpub,Ｈ3(Ｒ)Ｒ)
を適用することが可能である。
【００５４】
また、例えばハッシュ関数Ｈ2,Ｈ3に代えて、Ｍ及びＲのペアをハッシュ空間にマッピングするハッシュ関数Ｆ,Ｇを用いて、署名生成及び署名検証を一般化して、次式
Ｓ＝Ｆ(Ｍ,Ｒ)ＤID＋ｋＧ(Ｍ,Ｒ)Ｐpub                        …（６）
または当該式（６）と等価な関係式に従って署名Ｓを生成することも可能である。この場合、例えば次式
ｅ(Ｓ,Ｑ)＝ｅ(ＱID,Ｑpub)＾Ｆ(Ｍ,Ｒ)ｅ(Ｐpub,Ｒ)＾Ｇ(Ｍ,Ｒ)  …（７）
ここで、ｅ( , )は楕円曲線のペアリング
が成立するか否かによって、署名（Ｓ,Ｒ）を検証することも可能である。また、式（７）に代えて、当該式（７）と等価な関係式、例えば
ｅ(Ｓ,Ｑ)＝ｅ(Ｆ(Ｍ,Ｒ)ＱID,Ｑpub)ｅ(Ｐpub,Ｇ(Ｍ,Ｒ)Ｒ)
を用いることも可能である。
【００５５】
＜１巡型多重署名（並列型）＞
本実施形態の特徴は、上述の変形ElGamal署名を並列型の１巡型多重署名に適用した点にある。以下、並列型の１巡型多重署名について説明する。ここでは、説明の都合上、１番目乃至ｎ番目の署名者が、それぞれ署名生成装置１１-1乃至１１-nを使用するものとする。つまり、署名生成装置１１-1,１１-2,…,１１-nの順番で署名データが送信されるものとする。この場合、署名生成装置１１-iには、署名生成装置１１-(i-1）の署名送信部１１７から、部分署名（Ｓi-1,Ｒ1,…,Ｒi-1）と平文Ｍとが送信される。
【００５６】
まず、ＩＤがＩＤi（ｉ＝１,…,ｎ）であるｉ番目の署名者が利用する署名生成装置１１-iによる署名生成処理について図４のフローチャートを参照して説明する。今、署名生成装置１１-(i-1）の署名送信部１１７から署名生成装置１１-i宛てに送信された部分署名（Ｓi-1,Ｒ1,…,Ｒi-1）と平文Ｍが、当該署名生成装置１１-iの署名受信部１１６によって受信されたものとする。この部分署名（Ｓi-1,Ｒ1,…,Ｒi-1）と平文Ｍとは、記憶装置１１１の署名記憶部１１１ｃに格納される。
【００５７】
この状態において、署名生成装置１１-iの公開情報読出部１１２は、センター装置１０から公開情報であるＱ,Ｑpub,Ｐpub,Ｈ1,Ｈ2,Ｈ3を読み出す（ステップＳ２１）。読み出された公開情報は、記憶装置１１１の公開情報記憶部１１１ａに格納される。
【００５８】
公開鍵計算部１１８は、関数Ｈ1と、署名生成装置１１-1乃至１１-(i-1)を利用する１番目乃至ｉ−１番目の署名者のＩＤであるＩＤ１乃至ＩＤi-1とに基づき、次式
ＱID1＝Ｈ1(ＩＤ1)，ＱID2＝Ｈ1(ＩＤ2)，…，ＱIDi-1＝Ｈ1(ＩＤi-1)
に従って当該１番目乃至ｉ−１番目の署名者の公開鍵ＱID1乃至ＱIDi-1を計算する（ステップＳ２２）。計算された公開鍵ＱID1乃至ＱIDi-1は、署名生成装置１１-iにおいて利用可能なように公開鍵記憶部１１１ｂに格納される。
【００５９】
署名検査部１１９は、署名送信部１１７によって受信された部分署名（Ｓi-1,Ｒ1,…,Ｒi-1）が正当であるか否かを、平文Ｍと、公開鍵ＱIDj（ｊ＝１,２,…,ｉ−１）と、公開情報Ｑpub,Ｐpub,Ｈ2及びＨ3とに基づき、次式
ｅ(Ｓi-1,Ｑ)＝{Πｅ(ＱIDj,Ｑpub)}＾Ｈ2(Ｍ)
×{Πｅ(Ｐpub,Ｒj)＾Ｈ3(Ｒj)}                  …（８）
が成立するか否かによって検査（検証）する（ステップＳ２３,Ｓ２４）。ここで、ｅ( , )は楕円曲線のペアリングを示す。また、Ｘj＝ｅ(ＱIDj,Ｑpub)またはＸj＝ｅ(Ｐpub,Ｒj)＾Ｈ3(Ｒj)とすると、ΠＸjはｊ＝１からｊ＝ｉ−１までのＸjの積を示す。
【００６０】
もし、上記式（８）が成立しないならば、署名検査部１１９は部分署名が不正であると判定する。この場合、署名生成装置１１-iでの処理は終了する。これに対して上記式（８）が成立するならば、署名検査部１１９は部分署名が正当であると判定する。この場合、乱数生成部１１３は乱数ｋiを生成する（ステップＳ２５）。すると第１署名部１１４は、次式
Ｒi＝ｋiＱ
に従う計算によって、乱数ｋiと点Ｑとに依存する点Ｒiを署名（第１の署名データ）として生成する（ステップＳ２６）。Ｒiは＜Ｑ＞に属する点である。
【００６１】
一方、第２署名部１１５は、乱数ｋiと、ステップＳ２６で生成されたＲiと、公開情報Ｐpubと、ｉ番目の署名者の秘密鍵ＤIDiと、ハッシュ関数Ｈ2及びＨ3と、署名Ｓi-1と、平文Ｍとを用いて、次式
Ｓi＝Ｓi-1＋Ｈ2(Ｍ)ＤIDi＋ｋiＨ3(Ｒi)Ｐpub                    …（９）
に従う計算を行うことによって、署名（第２の署名データ）Ｓiを生成する（ステップＳ２７）。このようにして、署名生成装置１１-iは署名（Ｒi,Ｓi）を生成する。
【００６２】
署名送信部１１７は、署名生成装置１１-(i-1)から送信されたＲ1,…,Ｒi-1に、署名生成装置１１-iにて生成されたＲi及びＳiを付加し、部分署名（Ｓi,Ｒ1,…,Ｒi）として、署名生成装置１１-(i-1)から送信された平文Ｍと共に、ｉ＋１番目の署名者が使用する署名生成装置１１-(i+1)に送信する（ステップＳ２８）。但し、ｉ＝ｎの場合の署名生成装置１１-i、つまり署名生成装置１１-nは、（Ｓi,Ｒ1,…,Ｒi）つまり（Ｓn,Ｒ1,…,Ｒn）と平文Ｍとを署名検証装置１２に送信する。このように、最後の署名者であるｎ番目の署名者が使用する署名生成装置１１-nは、（Ｓn,Ｒ1,…,Ｒn）を平文Ｍに対する多重署名として、当該平文Ｍと共に署名検証装置１２に送信する。
【００６３】
なお、１番目の署名者が利用する署名生成装置１１-1ではステップＳ２２及びＳ２３は実行されない。また、署名生成装置１１-1では、ステップＳ２７において、Ｓ0＝０としてＳi＝Ｓ1＝Ｈ2(Ｍ)ＤID1＋ｋ1Ｈ3(Ｒ1)Ｐpubが計算される。この場合、署名生成装置１１-1から署名生成装置１１-2には、当該署名生成装置１１-1で生成された部分署名（Ｓ1,Ｒ1）が平文Ｍと共に送信される。
【００６４】
上記式（９）は、次式
Ｓi＝Ｓi-1＋Ｈ2(Ｍ)ＤIDi＋ｋiＨ3(Ｒi)Ｐpub
＝Ｈ2(Ｍ)ΣＤIDj＋ΣｋjＨ3(Ｒj)Ｐpub                      …（１０）
のように表すことができる。ここで、Ｘj＝ＤIDjまたはＸj＝ｋjＨ3(Ｒj)Ｐpubとすると、ΣＸjはｊ＝１からｊ＝ｉまでのＸjの和、つまりＸ1＋Ｘ2＋…＋Ｘiを示す。ＤIDj及びＰpubは、いずれも＜Ｐ＞に属する点であり、上記式（１０）の右辺第１項Ｈ2(Ｍ)ΣＤIDj及び右辺第２項ΣｋjＨ3(Ｒj)Ｐpubは、いずれも＜Ｐ＞に属する点を表す。したがって、Ｓiも＜Ｐ＞に属する点である。
【００６５】
次に、署名検証装置１２による多重署名に対する検証処理について図５のフローチャートを参照して説明する。今、署名生成装置１１-nの署名送信部１１７から署名検証装置１２宛てに送信された多重署名（Ｓn,Ｒ1,…,Ｒn）が、当該署名検証装置１２の署名受信部１１６によって受信されたものとする。多重署名（Ｓn,Ｒ1,…,Ｒn）と平文Ｍとは、記憶装置１１１の署名記憶部１１１ｃに格納される。
【００６６】
この状態において、署名検証装置１２の公開情報読出部１１２は、センター装置１０から公開情報であるＱ,Ｑpub,Ｐpub,Ｈ1,Ｈ2,Ｈ3を読み出す（ステップＳ３１）。センター装置１０から読み出された公開情報は、署名検証装置１２において利用可能なように記憶装置１１１の公開情報記憶部１１１ａに格納される。
【００６７】
公開鍵計算部１１８は、関数Ｈ1と、署名生成装置１１-1乃至１１-nを利用する１番目乃至ｎ番目の署名者のＩＤであるＩＤ１乃至ＩＤnとに基づき、次式
ＱID1＝Ｈ1(ＩＤ1)，ＱID2＝Ｈ1(ＩＤ2)，…，ＱIDn＝Ｈ1(ＩＤn)
に従って１番目乃至ｎ番目の署名者の公開鍵ＱID1乃至ＱIDnを計算する（ステップＳ３２）。計算された公開鍵ＱID1乃至ＱIDi-nは公開鍵記憶部１１１ｂに格納される。
【００６８】
すると署名検査部１１９は、署名送信部１１７によって受信された多重署名（Ｓn,Ｒ1,…,Ｒn）が正当であるか否かを、平文Ｍと、公開鍵ＱIDj（ｊ＝１,２,…,ｎ）と、公開情報Ｑpub,Ｐpub,Ｈ2及びＨ3とに基づき、次式
ｅ(Ｓn,Ｑ)＝{Πｅ(ＱIDj,Ｑpub)}＾Ｈ2(Ｍ)
×{Πｅ(Ｐpub,Ｒj)＾Ｈ3(Ｒj)}                  …（１１）
が成立するか否かによって検証する（ステップＳ３３）。ここで、ｅ( , )は楕円曲線のペアリングを示す。また、Ｘj＝ｅ(ＱIDj,Ｑpub)またはＸj＝ｅ(Ｐpub,Ｒj)＾Ｈ3(Ｒj)とすると、ΠＸjはｊ＝１からｊ＝ｎまでのＸjの積を示す。
【００６９】
なお、署名検証に、上記式（１１）と等価な関係式を用いることも可能である。例えば、式（１１）と等価な関係式として、
ｅ(Ｓn,Ｑ)＝Πｅ(Ｈ2(Ｍ)ＱIDj,Ｑpub)
×Πｅ(Ｐpub,Ｈ3(Ｒj)Ｒj)                      …（１２）
を適用することが可能である。ここで、Ｘj＝ｅ(Ｈ2(Ｍ)ＱIDj,Ｑpub)}またはＸj＝ｅ(Ｐpub,Ｈ3(Ｒj)Ｒj)とすると、ΠＸjはｊ＝１からｊ＝ｎまでのＸjの積を示す。
【００７０】
また、式（１１）と等価な他の関係式として、
ｅ(Ｓn,Ｑ)＝ｅ(ΣＱIDj,Ｑpub)＾Ｈ2(Ｍ)
×ｅ(Ｐpub,ΣＨ3(Ｒj)Ｒj)                      …（１３）
を適用することも可能である。ここで、Ｘj＝ＱIDjまたはＸj＝Ｈ3(Ｒj)Ｒjとすると、ΣＸjはｊ＝１からｊ＝ｎまでのＸjの和を示す。
【００７１】
なお、式（８）と等価な関係式については、上記式（１２）または（１３）に関して、ｎをｉ−１に置き換えれば良い。
【００７２】
ここで、上述の変形ElGamal署名を適用した１巡型多重署名のＩＤベース版として一般化（拡張）を進めると、署名Ｓiを、例えば次式
Ｓi＝ΣｆjＤIDj＋ΣｇjｋjＰpub
で表すことが可能である。ここで、ｆj及びｇjは、それぞれｆj＝Ｆj(Ｍ,Ｒ1,…,Ｒj)，ｇj＝Ｇj(Ｍ,Ｒ1,…,Ｒj)で表されるハッシュ関数である。また、Ｘj＝ｋjＱまたはＸj＝ｆjＤIDjまたはＸj＝ΣｇjｋjＰpubとすると、ΣＸjはｊ＝１からｊ＝ｉまでのＸjの和を示す。明らかなように、右辺第１項ｆjＤIDj及び右辺第２項ｇjｋjＰpubは、いずれも＜Ｐ＞に属する点を表す。したがって、Ｓiも＜Ｐ＞に属する点である。
【００７３】
この場合、次式
ｅ(Ｓn,Ｑ)＝ｅ(ΣfjＱIDj,Ｑpub)ｅ(Ｐpub,ΣｇjＲj))
または当該式と等価な関係式が成立するか否かによって、多重署名（Ｓn,Ｒ1,…,Ｒn）を検証すれば良い。ここで、ｅ( , )は楕円曲線のペアリングを示す。また、Ｘj＝ｆjＱIDjまたはＸj＝ｇjＲjとすると、ΣＸjはｊ＝１からｊ＝ｎまでのＸjの和を示す。なお、ｆjによるマッピングの要素として、Ｍ,Ｒ1,…,Ｒjのうちの少なくともＭを含み、ｇjによるマッピングの要素として、Ｍ,Ｒ1,…,Ｒjのうちの少なくともＲjを含むものであっても良い。また、fjをＭ,Ｒ1,…,Ｒjに無関係に１として、ｇjによるマッピングの要素として、Ｍ,Ｒ1,…,Ｒjのうちの少なくともＭ及びＲjを含むものとしても良い。
【００７４】
［第１の変形例：２巡型多重署名（並列型）］
次に上記実施形態の第１の変形例について説明する。この第１の変形例は、前述の変形ElGamal署名を並列型の２巡型多重署名に適用した点にある。ここでは、上記実施形態と同様に、１番目乃至ｎ番目の署名者が、それぞれ署名生成装置１１-1乃至１１-nを使用するものとする。この場合、１巡目では、署名生成装置１１-iには、署名生成装置１１-(i-1）の署名送信部１１７から、署名Ｒi-1が送信される。また、２巡目では、署名生成装置１１-iには、署名生成装置１１-(i-1）の署名送信部１１７から、部分署名（Ｓi-1,Ｒn）と平文Ｍとが送信される。
【００７５】
まず、ＩＤがＩＤi（ｉ＝１,…,ｎ）のｉ番目の署名者が利用する署名生成装置１１-iによる１巡目の署名生成処理について図６のフローチャートを参照して説明する。今、署名生成装置１１-(i-1）の署名送信部１１７から署名生成装置１１-i宛てに送信された署名Ｒi-1が、当該署名生成装置１１-iの署名受信部１１６によって受信されたものとする。この署名Ｒi-1は、記憶装置１１１の署名記憶部１１１ｃに格納される。
【００７６】
この状態において、署名生成装置１１-iの公開情報読出部１１２は、センター装置１０から公開情報であるＱを読み出す（ステップＳ４１）。センター装置１０から読み出された公開情報は、署名生成装置１１-iにおいて利用可能なように、記憶装置１１１の公開情報記憶部１１１ａに格納される。
【００７７】
乱数生成部１１３は乱数ｋiを生成する（ステップＳ４２）。すると第１署名部１１４は、次式
Ｒi＝ｋiＱ＋Ｒi-1
に従う計算によって、乱数ｋiと点ＱとＲi-1とに依存する点Ｒiを署名（第１の署名データ）として生成する（ステップＳ４３）。ここで、ｉ＝１の場合の署名生成装置１１-i、つまり署名生成装置１１-1にはＲi-1＝Ｒ0は送信されない。そこで署名生成装置１１-1では、ステップＳ４３においてＲ0としてＲ0＝０が用いられるものとする。
【００７８】
署名送信部１１７は、第１署名部１１４によって生成されたＲiを、ｉ＋１番目の署名者が使用する署名生成装置１１-(i+1)に送信する（ステップＳ４４）。但し、ｉ＝ｎの場合の署名生成装置１１-i、つまり署名生成装置１１-nは、ＲiつまりＲnを、１番目の署名者が使用する署名生成装置１１-1に送信する。このように、最後の署名者であるｎ番目の署名者が使用する署名生成装置１１-nは、Ｒnを署名生成装置１１-1に送信する。
【００７９】
次に、署名生成装置１１-iによる２巡目の署名生成処理について図７のフローチャートを参照して説明する。今、署名生成装置１１-(i-1）の署名送信部１１７から署名生成装置１１-i宛てに送信された部分署名（Ｓi-1,Ｒn）と平文Ｍが、当該署名生成装置１１-iの署名受信部１１６によって受信されたものとする。この部分署名（Ｓi-1,Ｒn）と平文Ｍとは、記憶装置１１１の署名記憶部１１１ｃに格納される。
【００８０】
この状態において、署名生成装置１１-iの公開情報読出部１１２は、センター装置１０または公開情報記憶部１１１ａから公開情報であるＱ,Ｑpub,Ｐpub,Ｈ1,Ｈ2,Ｈ3を読み出す（ステップＳ５１）。センター装置１０から読み出された公開情報は、記憶装置１１１の公開情報記憶部１１１ａに格納される。
【００８１】
公開鍵計算部１１８は、関数Ｈ1と、署名生成装置１１-1乃至１１-(i-1)を利用する１番目乃至ｉ−１番目の署名者のＩＤであるＩＤ１乃至ＩＤi-1とに基づき、次式
ＱID1＝Ｈ1(ＩＤ1)，ＱID2＝Ｈ1(ＩＤ2)，…，ＱIDi-1＝Ｈ1(ＩＤi-1)
に従って当該１番目乃至ｉ−１番目の署名者の公開鍵ＱID1乃至ＱIDi-1を計算する（ステップＳ５２）。計算された公開鍵ＱID1乃至ＱIDi-1は公開鍵記憶部１１１ｂに格納される。
【００８２】
すると署名検査部１１９は、署名送信部１１７によって受信された部分署名（Ｓi-1,Ｒn）が正当であるか否かを、平文Ｍと、公開鍵ＱIDj（ｊ＝１,２,…,ｉ−１）と、公開情報Ｑpub,Ｐpub,Ｈ2及びＨ3とに基づき、次式
ｅ(Ｓi-1,Ｑ)＝{Πｅ(ＱIDj,Ｑpub)}＾Ｈ2(Ｍ)
×ｅ(Ｐpub,Ｒi-1)＾Ｈ3(Ｍ,Ｒn)                 …（１４）
が成立するか否かによって検査（検証）する（ステップＳ５３,Ｓ５４）。ここで、ｅ( , )は楕円曲線のペアリングを示す。また、Ｘj＝ｅ(ＱIDj,Ｑpub)とすると、ΠＸjはｊ＝１からｊ＝ｉ−１までのＸjの積を示す。
【００８３】
もし、上記式（１４）が成立しないならば、署名検査部１１９は部分署名が不正であると判定する。この場合、署名生成装置１１-iでの処理は終了する。これに対して上記式（１４）が成立するならば、署名検査部１１９は部分署名が正当であると判定する。この場合、第２署名部１１５は、乱数ｋiと、公開情報Ｐpubと、ｉ番目の署名者の秘密鍵ＤIDiと、ハッシュ関数Ｈ2及びＨ3と、署名Ｓi-1及びＲnと、平文Ｍとを用いて、次式
Ｓi＝Ｓi-1＋Ｈ2(Ｍ)ＤIDi＋ｋiＨ3(Ｍ,Ｒn)Ｐpub                  …（１５）
に従う計算を行うことによって、署名（第２の署名データ）Ｓiを生成する（ステップＳ５５）。
【００８４】
署名送信部１１７は、署名生成装置１１-(i-1)から送信（伝達）されたＲnに、署名生成装置１１-iにて生成されたＳiを付加し、部分署名（Ｓi,Ｒn）として、署名生成装置１１-(i-1)から送信された平文Ｍと共に、ｉ＋１番目の署名者が使用する署名生成装置１１-(i+1)に送信する（ステップＳ５６）。但し、ｉ＝ｎの場合の署名生成装置１１-i、つまり署名生成装置１１-nは、（Ｓi,Ｒn）つまり（Ｓn,Ｒn）と平文Ｍとを署名検証装置１２に送信する。このように、最後の署名者であるｎ番目の署名者が使用する署名生成装置１１-nは、（Ｓn,Ｒn）を平文Ｍに対する多重署名として、当該平文Ｍと共に署名検証装置１２に送信する。
【００８５】
なお、１番目の署名者が利用する署名生成装置１１-1ではステップＳ５２乃至Ｓ５４は実行されない。また、署名生成装置１１-1では、ステップＳ５５において、Ｓi-1＝Ｓ0＝０としてＳi＝Ｓ1＝Ｈ2(Ｍ)ＤID1＋ｋ1Ｈ3(Ｍ,Ｒn)Ｐpubが計算される。
【００８６】
次に、署名検証装置１２による多重署名に対する検証処理について図８のフローチャートを参照して説明する。今、署名生成装置１１-nの署名送信部１１７から署名検証装置１２宛てに送信された多重署名（Ｓn,Ｒn）が、当該署名検証装置１２の署名受信部１１６によって受信されたものとする。多重署名（Ｓn,Ｒn）と平文Ｍとは、記憶装置１１１の署名記憶部１１１ｃに格納される。
【００８７】
この状態において、署名検証装置１２の公開情報読出部１１２は、センター装置１０から公開情報であるＱ,Ｑpub,Ｐpub,Ｈ1,Ｈ2,Ｈ3を読み出す（ステップＳ６１）。センター装置１０から読み出された公開情報は、記憶装置１１１の公開情報記憶部１１１ａに格納される。
【００８８】
公開鍵計算部１１８は、関数Ｈ1と、署名生成装置１１-1乃至１１-nを利用する１番目乃至ｎ番目の署名者のＩＤであるＩＤ１乃至ＩＤnとに基づき、次式
ＱID1＝Ｈ1(ＩＤ1)，ＱID2＝Ｈ1(ＩＤ2)，…，ＱIDn＝Ｈ1(ＩＤn)
に従って１番目乃至ｎ番目の署名者の公開鍵ＱID1乃至ＱIDnを計算する（ステップＳ６２）。計算された公開鍵ＱID1乃至ＱIDnは公開鍵記憶部１１１ｂに格納される。
【００８９】
すると署名検査部１１９は、署名送信部１１７によって受信された多重署名（Ｓn,Ｒn）が正当であるか否かを、平文Ｍと、公開鍵ＱIDj（ｊ＝１,２,…,ｎ）と、公開情報Ｑpub,Ｐpub,Ｈ2及びＨ3とに基づき、次式
ｅ(Ｓn,Ｑ)＝{Πｅ(ＱIDj,Ｑpub)}＾Ｈ2(Ｍ)
×ｅ(Ｐpub,Ｒn)＾Ｈ3(Ｍ,Ｒn)}                  …（１６）
が成立するか否かによって検証する（ステップＳ６３）。ここで、ｅ( , )は楕円曲線のペアリングを示す。また、Ｘj＝ｅ(ＱIDj,Ｑpub)とすると、ΠＸjはｊ＝１からｊ＝ｎまでのＸjの積を示す。
【００９０】
上述した２巡型多重署名によれば、先に述べた１巡型多重署名と比べて、手間はかかるものの、署名者の数ｎの増加による署名サイズの増加を抑えることができる。
【００９１】
なお、式（１６）と等価な関係式として、
ｅ(Ｓn,Ｑ)＝Πｅ(Ｈ2(Ｍ)ＱIDj,Ｑpub)
×ｅ(Ｐpub,Ｈ3(Ｍ,Ｒn)Ｒn)                      …（１７）
を適用することが可能である。ここで、Ｘj＝ｅ(Ｈ2(Ｍ)ＱIDj,Ｑpub)とすると、ΠＸjはｊ＝１からｊ＝ｎまでのＸjの積を示す。
【００９２】
また、式（１６）と等価な他の関係式として、
ｅ(Ｓn,Ｑ)＝ｅ(ΣＱIDj,Ｑpub)＾Ｈ2(Ｍ)
×ｅ(Ｐpub,Ｈ3(Ｍ,Ｒn)Ｒn)                      …（１８）
を適用することも可能である。ここで、ΣＱIDjはｊ＝１からｊ＝ｎまでのＱIDjの和、つまりＱID1＋ＱID2＋…＋ＱIDnを示す。
【００９３】
なお、式（１４）と等価な関係式については、上記式（１７）または（１８）において、ｎをｉ−１に置き換えれば良い。
【００９４】
また、この第１の変形例の２巡型多重署名においても、前述の２巡型多重署名と同様の一般化が可能であり、署名Ｒi及びＳiを、それぞれ次式
Ｒi＝ΣｋjＱ
Ｓi＝ΣｆnＤIDj＋ΣｇnｋjＰpub
で表すことが可能である。ここで、ｆn及びｇnは、それぞれｆn＝Ｆn(Ｍ,Ｒ1,…,Ｒn)，ｇn＝Ｆn(Ｍ,Ｒ1,…,Ｒn)で示されるハッシュ関数である。また、Ｘj＝ｋjＱ、Ｘj＝ｆnＤIDjまたはＸj＝ｇnｋjＰpubとすると、ΣＸjは、ｊ＝１からｊ＝ｉまでのＸjの和を示す。
【００９５】
次に、一般化されたＩＤベース版多重署名の安全性について検討する。この安全性は、第１の変形例における１巡型多重署名についても共通である。そこで以下の説明では、ハッシュ関数の表記としてｆj及びｇjを採用する。必要があれば、ｆj及びｇjを、それぞれｆn及びｇnに置き換えられたい。まず、署名Ｓiの生成に、ハッシュ関数としてｆjのみ使用する（ｇj＝１）場合、署名Ｓiは偽造可能である。この場合、多重署名は安全ではない。これに対し、ハッシュ関数としてｆj及びｇjの両方を用いるか、或いはｇjのみ使用する（ｆj＝１）場合には、多重署名の安全性は、ΣＱIDj＝ｓ-1(ΣＤIDj)という条件式を用いて、ΣＤIDjを求める問題に帰着する。ここで、Ｘj＝ＱIDjまたはＸj＝ＤIDjとすると、ΣＸjはｊ＝１からｊ＝ｎまでのＸjの和を示す。但し、ｇjのみを使用する場合には、ｇjによるマッピングの要素として、Ｍ,Ｒ1,…,Ｒjのうちの少なくともＭ及びＲjを含ませることが必要である。
【００９６】
［第２の変形例：２巡型多重署名（縦列型）］
次に上記実施形態の第２の変形例について説明する。この第２の変形例の特徴は、前述の変形ElGamal署名を縦列型の２巡型多重署名に適用した点にある。ここでは、上記実施形態と同様に、１番目乃至ｎ番目の署名者が、それぞれ署名生成装置１１-1乃至１１-nを使用するものとする。
【００９７】
まず、ｉ番目（ｉ＝１,…,ｎ）の署名者が利用する署名生成装置１１-iによる順序鍵生成処理について図９のフローチャートを参照して説明する。この順序鍵生成処理は、署名生成装置１１-(i-1)にて生成された順序鍵Ｇi-1を検証する順序鍵検証処理を含む。ここでは、ｉ番目の署名者に固有の秘密情報ｔiがセンター装置１０にて生成される。秘密情報ｔiはｉ番目の署名者に秘密裏に配布される。秘密情報ｔiは署名生成装置１１-iの秘密鍵記憶装置１１０に格納される。ここで、順序鍵Ｇiと秘密情報ｔiとのペア（Ｇi,ｔi）を鍵ペアと呼ぶ。
【００９８】
署名生成装置１１-iは順序鍵検証情報生成手段として機能し、公開情報Ｑと秘密情報ｔiとに基づき、順序鍵（縦列型用順序鍵）Ｇiの検証に用いられる公開情報（順序鍵検証情報）Ａiを次式
Ａi＝ｔiＱ
に従って生成する。Ａiは＜Ｑ＞に属する点である。署名生成装置１１-iは、生成されたＡiをＤIDiで署名を付けて公開する。公開されたＡiは、署名生成装置１１-1乃至１１-n及び署名検証装置１２の公開情報記憶部１１１ａに格納される。公開情報（順序鍵検証情報）Ａiは、順序鍵Ｇiそれ自体ではないため、署名順序を変えても再度の作成は不要である。
【００９９】
さて、署名生成装置１１-iには、署名生成装置１１-(i-1）の署名送信部１１７から、ｉ−２番目の署名者の順序鍵Ｇi-2とｉ−１番目の署名者の順序鍵Ｇi-1が送信される。この順序鍵Ｇi-2及びＧi-1は、署名生成装置１１-iの署名受信部１１６で受信されて、記憶装置１１１に格納される。順序鍵Ｇi-2及びＧi-1のうちのＧi-2は、以下の説明から理解されるように、署名生成装置１１-(i-1）によって正当であると検証されている。
【０１００】
この状態において、署名生成装置１１-iの公開情報読出部１１２は、センター装置１０から公開情報であるＱ,Ｈ1を読み出すと共に、公開情報記憶部１１１ａから公開情報であるＡi-1を読み出す（ステップＳ７１）。センター装置１０から読み出された公開情報は公開情報記憶部１１１ａに格納される。
【０１０１】
公開鍵計算部１１８は、関数Ｈ1と、ｉ−１番目及びｉ番目の署名者のＩＤであるＩＤi-1及びＩＤiとに基づき、次式
ＱIDi-1＝Ｈ1(ＩＤi-1)，ＱIDi＝Ｈ1(ＩＤi)
に従って当該ｉ−１番目及びｉ番目の署名者の公開鍵ＱIDi-1及びＱIDiを計算する（ステップＳ７２）。但し、署名生成装置１１-1では、ＱIDiのみ、つまりＱID1のみが計算される。
【０１０２】
順序鍵検査部１２２は、先に受信された順序鍵Ｇi-1が正当であるか否かを、順序鍵Ｇi-2と、公開鍵ＱIDi-1と、公開情報Ａi-1とに基づき、次式
ｅ(Ｇi-1,Ｑ)＝ｅ(Ｇi-2＋ＱIDi-1,Ａi-1)                        …（１９）
が成立するか否かによって検証する（ステップＳ７３,Ｓ７４）。ここで、ｅ( , )は楕円曲線のペアリングを示す。また、ｉ＝１の場合のＧi-1つまりＧ0は、Ｇi-1＝Ｇ0＝０であるものとする。なお、署名生成装置１１-1ではステップＳ７３,Ｓ７４は実行されない。
【０１０３】
もし、上記式（１９）が成立しないならば、順序鍵検査部１２２は順序鍵Ｇi-1が不正であると判定する。この場合、署名生成装置１１-iでの処理は終了する。これに対して上記式（１９）が成立するならば、順序鍵検査部１２２は順序鍵Ｇi-1が正当であると判定する。すると順序鍵生成部１２１は、秘密情報ｔiと、順序鍵Ｇi-1と、公開鍵ＱIDiとを用いて、次式
Ｇi＝ｔi(Ｇi-1＋ＱIDi)
に従う計算を行うことによって、順序鍵Ｇiを生成する（ステップＳ７５）。ここでは、ｉ＝１の場合、Ｇi-1＝Ｇ0＝０であることから、Ｇi＝Ｇ1としてｔ1ＱID1が生成される。ＱIDiは＜Ｐ＞に属する点である。したがって、順序鍵Ｇiも＜Ｐ＞に属する点である。
【０１０４】
署名送信部１１７は、順序鍵生成部１２１によって生成されたＧi及び当該Ｇiの生成に用いられたＧi-1を署名生成装置１１-(i+1)に送信する（ステップＳ７６）。但し、ｉ＝ｎの場合の署名生成装置１１-i、つまり署名生成装置１１-nは、Ｇi-1及びＧiつまりＧn-1及びＧnを署名検証装置１２に送信する。
【０１０５】
次に、署名検証装置１２による順序鍵検証処理について図１０のフローチャートを参照して説明する。
【０１０６】
署名検証装置１２の公開情報読出部１１２は、センター装置１０から公開情報であるＱ,Ｈ1を読み出すと共に、公開情報記憶部１１１ａから公開情報であるＡnを読み出す（ステップＳ８１）。センター装置１０から読み出された公開情報は公開情報記憶部１１１ａに格納される。
【０１０７】
公開鍵計算部１１８は、関数Ｈ1と、ｎ番目の署名者のＩＤであるＩＤnとに基づき、次式
ＱIDn＝Ｈ1(ＩＤn)
に従って当該ｎ番目の署名者の公開鍵ＱIDnを計算する（ステップＳ８２）。計算された公開鍵ＱIDnは署名生成装置１１-1の公開鍵記憶部１１１ｂに格納される。
【０１０８】
順序鍵検査部１２２は、先に受信された順序鍵Ｇnが正当であるか否かを、順序鍵Ｇn-1と、公開鍵ＱIDnと、公開情報Ａnとに基づき、次式
ｅ(Ｇn,Ｑ)＝ｅ(Ｇn-1＋ＱIDn,Ａn)                              …（２０）
が成立するか否かによって検証する（ステップＳ８３）。ここで、ｅ( , )は楕円曲線のペアリングを示す。もし、上記式（２０）が成立するならば、順序鍵Ｇnが正当であると判定される。この段階で、全ての順序鍵Ｇ1乃至Ｇnが正当であると判定されたことになる。これにより、縦列型多重署名が可能となる。
【０１０９】
次に、ｉ番目の署名者が利用する署名生成装置１１-iによる１巡目の署名生成処理について図１１のフローチャートを参照して説明する。なお、署名生成装置１１-iには、署名生成装置１１-(i-1）の署名送信部１１７から、１巡目には署名Ｒi-1が送信され、２巡目では部分署名（Ｓi-1,Ｒn）と平文Ｍとが送信される点は、上記第１の変形例（並列型の２巡型多重署名）と同様である。
【０１１０】
今、署名生成装置１１-(i-1）の署名送信部１１７から署名生成装置１１-i宛てに送信された署名Ｒi-1が、当該署名生成装置１１-iの署名受信部１１６によって受信されたものとする。この署名Ｒi-1は、記憶装置１１１の署名記憶部１１１ｃに格納される。
【０１１１】
この状態において、署名生成装置１１-iの公開情報読出部１１２は、センター装置１０または公開情報記憶部１１１ａから公開情報であるＱを読み出す（ステップＳ９１）。一方、乱数生成部１１３は乱数ｋiを生成する（ステップＳ９２）。すると第１署名部１１４は、次式
Ｒi＝ｔiＲi-1＋ｋiＱ
に従う計算によって、秘密情報ｔiと点（署名）Ｒi-1とに依存し、且つ乱数ｋiと点Ｑとに依存する点Ｒiを署名（第１の署名データ）として生成する（ステップＳ９３）。ここで、ｉ＝１の場合の署名生成装置１１-i、つまり署名生成装置１１-1にはＲi-1＝Ｒ0は送信されない。そこで署名生成装置１１-1では、ステップＳ９３においてＲ0としてＲ0＝０が用いられるものとする。この場合、Ｒ1＝ｋ1Ｑとなる。Ｒiは＜Ｑ＞に属する点である。
【０１１２】
署名送信部１１７は、第１署名部１１４によって生成されたＲiを、ｉ＋１番目の署名者が使用する署名生成装置１１-(i+1)に送信する（ステップＳ９４）。但し、ｉ＝ｎの場合の署名生成装置１１-i、つまり署名生成装置１１-nは、Ｒnを１番目の署名者が使用する署名生成装置１１-1に送信する。
【０１１３】
次に、署名生成装置１１-iによる２巡目の署名生成処理について図１２のフローチャートを参照して説明する。今、署名生成装置１１-(i-1）の署名送信部１１７から署名生成装置１１-i宛てに送信された部分署名（Ｓi-1,Ｒn）と平文Ｍとが、当該署名生成装置１１-iの署名受信部１１６によって受信されたものとする。この部分署名（Ｓi-1,Ｒn）と平文Ｍとは、記憶装置１１１の署名記憶部１１１ｃに格納される。
【０１１４】
この状態において、署名生成装置１１-iの公開情報読出部１１２は、センター装置１０または公開情報記憶部１１１ａから公開情報であるＱ,Ｑpub,Ｐpub,Ｈ3を読み出す（ステップＳ１０１）。センター装置１０から読み出された公開情報は、記憶装置１１１の公開情報記憶部１１１ａに格納される。
【０１１５】
すると署名検査部１１９は、署名送信部１１７によって受信された部分署名（Ｓi-1,Ｒn）が正当であるか否かを、平文Ｍと、順序鍵Ｇi-1と、公開情報Ｑpub,Ｐpubと、ハッシュ関数Ｈ3と、署名Ｒi-1とに基づき、次式
ｅ(Ｓi-1,Ｑ)＝ｅ(Ｇi-1,Ｑpub)ｅ(Ｈ3(Ｍ,Ｒn)Ｐpub,Ｒi-1)      …（２１）
が成立するか否かによって検査（検証）する（ステップＳ１０２,Ｓ１０３）。ここで、ｅ( , )は楕円曲線のペアリングを示す。
【０１１６】
もし、上記式（２０）が成立しないならば、署名検査部１１９は部分署名が不正であると判定する。この場合、署名生成装置１１-iでの処理は終了する。これに対して上記式（２０）が成立するならば、署名検査部１１９は部分署名が正当であると判定する。
【０１１７】
第２署名部１１５は、部分署名が正当であると判定された場合、乱数ｋiと、公開情報Ｐpubと、ｉ番目の署名者の秘密情報ｔiと、ｉ番目の署名者の秘密鍵ＤIDiと、ハッシュ関数Ｈ3と、署名Ｓi-1及びＲnと、平文Ｍとを用いて、次式
Ｓi＝ｔi(Ｓi-1＋ＤIDi)＋ｋiＨ3(Ｍ,Ｒn)Ｐpub
に従う計算を行うことによって、署名（第２の署名データ）Ｓiを生成する（ステップＳ１０４）。ＤIDi及びＰpubは＜Ｐ＞に属する点である。したがって、Ｓiも＜Ｐ＞に属する点である。
【０１１８】
署名送信部１１７は、署名生成装置１１-(i-1)から送信（伝達）されたＲnに、署名生成装置１１-iにて生成されたＳiを付加し、部分署名（Ｓi,Ｒn）として、署名生成装置１１-(i-1)から送信された平文Ｍと共に、ｉ＋１番目の署名者が使用する署名生成装置１１-(i+1)に送信する（ステップＳ１０５）。但し、ｉ＝ｎの場合の署名生成装置１１-i、つまり署名生成装置１１-nは、（Ｓi,Ｒn）つまり（Ｓn,Ｒn）と平文Ｍとを署名検証装置１２に送信する。
【０１１９】
なお、１番目（ｉ＝１）の署名者が利用する署名生成装置１１-1ではステップＳ１０２及びＳ１０３は実行されない。また、署名生成装置１１-1では、ステップＳ１０４において、Ｓi-1＝Ｓ0＝０としてＳi＝Ｓ1が計算される。
【０１２０】
次に、署名検証装置１２による多重署名に対する検証処理について図１３のフローチャートを参照して説明する。今、署名生成装置１１-nの署名送信部１１７から署名検証装置１２宛てに送信された多重署名（Ｓn,Ｒn）及び平文Ｍが、当該署名検証装置１２の署名受信部１１６によって受信されたものとする。
【０１２１】
この状態において、署名検証装置１２の公開情報読出部１１２は、センター装置１０または公開情報記憶部１１１ａから公開情報であるＱ,Ｑpub,Ｐpub,Ｈ3を読み出す（ステップＳ１１１）。すると署名検査部１１９は、署名送信部１１７によって受信された多重署名（Ｓn,Ｒn）が正当であるか否かを、点Ｑと、平文Ｍと、順序鍵Ｇnと、公開情報Ｑpub,Ｐpubと、ハッシュ関数Ｈ3と、署名Ｒnとに基づき、次式
ｅ(Ｓn,Ｑ)＝ｅ(Ｇn,Ｑpub)}ｅ(Ｈ3(Ｍ,Ｒn)Ｐpub,Ｒn)
が成立するか否かによって検証する（ステップＳ１１２）。ここで、ｅ( , )は楕円曲線のペアリングを示す。
【０１２２】
［第３の変形例：２巡型多重署名（縦列型）］
次に、上記実施形態の第３の変形例について説明する。第３の変形例の特徴は、上記第２の変形例とは異なって、２巡型多重署名（縦列型）において鍵ペア（順序鍵）生成と署名生成とがまとめて行われる点に特徴がある。
【０１２３】
この第３の変形例で適用される縦列型の２巡型多重署名（以下、縦列型多重署名と称する）を理解しやすくするために、２つの平文への署名の連結について説明する。楕円曲線のｎねじれ点の集合Ｅ[ｎ]＝＜Ｐ＞＋＜Ｑ＞が、２つの生成元Ｐ,Ｑを持つことを利用すると、以下に述べるように、２つの平文、即ち第１の平文Ｍ1及び第２の平文Ｍ2に対する署名を、ペアリングを用いて連結することができる。
【０１２４】
まず、平文Ｍ1に対する署名者を第１の署名者と呼び、平文Ｍ2に対する署名者を第２の署名者と呼ぶ。また、第１の署名者の公開鍵と秘密鍵とのペア（第１の鍵ペア）を（Ｑ1,Ｄ1）とし、第２の署名者の公開鍵と秘密鍵とのペア（第２の鍵ペア）を（Ｑ2,Ｄ2）とする。Ｑ1,Ｑ2及びＤ1,Ｄ2は、ＱIDi及びＤIDiと同様に、いずれも＜Ｐ＞に属する点である。ここでは、Ｍ1に対する署名としてＵ1とＶ1とが生成され、Ｍ2に対する署名としてＵ2とＶ2とが生成される。
【０１２５】
署名Ｕ1は、乱数ｋ1と点Ｑとに基づき、次式
Ｕ1＝ｋ1Ｑ
に従って、例えば署名生成装置１１-1の第１署名部１１４により生成される。
【０１２６】
同様に、署名Ｕ2は、乱数ｋ2と点Ｑとに基づき、次式
Ｕ2＝ｋ2Ｑ
に従って、例えば署名生成装置１１-2の第１署名部１１４により生成される。Ｕ1,Ｕ2は、Ｒiと同様に、＜Ｑ＞に属する点である。
【０１２７】
一方、署名Ｖ1は、平文Ｍ1と、乱数ｋ1と、秘密鍵Ｄ1と、ハッシュ関数Ｈ3と、公開情報Ｐpubと、後述するＵ＝Ｕ1＋φ(Ｕ2)とに基づき、次式
Ｖ1＝Ｄ1＋ｋ1Ｈ3(Ｍ1,Ｕ)Ｐpub
に従って、例えば署名生成装置１１-1の第２署名部１１５により生成される。
【０１２８】
同様に、署名Ｖ2は、平文Ｍ2と、乱数ｋ2と、秘密鍵Ｄ2と、ハッシュ関数Ｈ3と、公開情報Ｐpubと、Ｕ＝Ｕ1＋φ(Ｕ2)とに基づき、次式
Ｖ2＝Ｄ2＋ｋ2Ｈ3(Ｍ2,Ｕ)Ｐpub
に従って、例えば署名生成装置１１-2の第２署名部１１５により生成される。Ｖ1,Ｖ2は、＜Ｐ＞に属する点である。
【０１２９】
次に、署名Ｕ1,Ｕ2が、次式
Ｕ＝Ｕ1＋φ(Ｕ2)
に従って、例えば署名生成装置１１-2の第１署名部１１４により連結される。ここで、φはdistortion mapと呼ばれるＥ[ｎ]上の自己同型写像であり、φ(Ｑ)＝Ｐであるものとする。この場合、上記Ｕは、＜Ｑ＞に属する点と＜Ｐ＞に属する点とを含む。
【０１３０】
同様に、署名Ｖ1,Ｖ2が、次式
Ｖ＝Ｖ1＋φ(Ｖ2)
に従って、例えば署名生成装置１１-2の第２署名部１１５により連結される。ここでφ(Ｐ)＝Ｑであるものとすると、上記Ｖは、＜Ｐ＞に属する点と＜Ｑ＞に属する点とを含む。
【０１３１】
（Ｕ,Ｖ）が、２つの平文Ｍ1,Ｍ2に対する署名となる。この（Ｕ,Ｖ）の署名長は、平文Ｍ1に対する署名（Ｕ1,Ｖ1）と、平文Ｍ2に対する署名（Ｕ2,Ｖ2）とを単純に連結したものの１／２となっている。但し、Ｕ,Ｖは、いずれも＜Ｐ＞に属する点と＜Ｑ＞に属する点とを含む。このため、Ｍ1,Ｍ2に対する署名の検証では、例えばＵから、＜Ｐ＞または＜Ｑ＞に属する点の要素だけを抽出する必要がある。
【０１３２】
そこで、Ｍ1,Ｍ2に対する署名の検証は署名検証装置１２によって次のように行われる。まず、Ｍ1に対する署名の検証は、点Ｑと、平文Ｍ1と、公開鍵Ｑ1と、公開情報Ｑpubと、ハッシュ関数Ｈ3と、署名Ｕ,Ｖとに基づき、次式
ｅ(Ｖ,Ｑ)＝ｅ(Ｑ1,Ｑpub)ｅ(Ｈ3(Ｍ1,Ｕ)Ｐ,Ｕ)
が成立するか否かによって行われる。ｅ(Ｈ3(Ｍ1,Ｕ)Ｐ,Ｕ)では、ｅ(Ｐ,Ｐ)＝１とｅ(Ｐ,Ｑ＋Ｒ)＝ｅ(Ｐ,Ｑ)ｅ(Ｐ,Ｒ)の性質とから、Ｕに含まれている＜Ｐ＞に属する点の要素がキャンセルされて、＜Ｑ＞に属する点の要素だけが抽出される。
【０１３３】
一方、Ｍ2に対する署名の検証は、点Ｐと、平文Ｍ2と、公開鍵Ｑ2と、公開情報Ｐpubと、ハッシュ関数Ｈ3と、署名Ｕ,Ｖとに基づき、次式
ｅ(Ｐ,Ｖ)＝ｅ(Ｐpub,φ(Ｑ2))ｅ(Ｕ,Ｈ3(Ｍ2,Ｕ)Ｑ)
が成立するか否かによって行われる。ｅ(Ｕ,Ｈ3(Ｍ2,Ｕ)Ｑ)では、ｅ(Ｑ,Ｑ)＝１とｅ(Ｐ＋Ｑ,Ｒ)＝ｅ(Ｐ,Ｒ)ｅ(Ｑ,Ｒ)の性質とから、Ｕに含まれている＜Ｑ＞に属する点の要素がキャンセルされて、＜Ｐ＞に属する点の要素だけが抽出される。
【０１３４】
次に、第３の変形例の特徴である、上述した署名連結の縦列型多重署名への応用について説明する。ここでは、順序鍵に相当する鍵の生成と署名生成とがまとめて行われる。
【０１３５】
まず、１番目乃至ｎ番目の署名者が、それぞれ署名生成装置１１-1乃至１１-nを使用するものとする。この場合、１巡目では、署名生成装置１１-iには、署名生成装置１１-(i-1）の署名送信部１１７から、署名Ｒi-2,Ｒi-1が送信される。また、２巡目では、署名生成装置１１-iには、署名生成装置１１-(i-1）の署名送信部１１７から、部分署名（Ｓi-1,Ｒn）と平文Ｍとが送信される。
【０１３６】
まず、ＩＤがＩＤi（ｉ＝１,…,ｎ）であるｉ番目の署名者が利用する署名生成装置１１-iによる１巡目の署名生成処理について図１４のフローチャートを参照して説明する。今、署名生成装置１１-(i-1）の署名送信部１１７から署名生成装置１１-i宛てに送信された署名Ｒi-2,Ｒi-1が、当該署名生成装置１１-iの署名受信部１１６によって受信されたものとする。受信された署名Ｒi-2,Ｒi-1は、署名記憶部１１１ｃに格納される。
【０１３７】
この状態において、署名生成装置１１-iの公開情報読出部１１２は、センター装置１０から公開情報であるＱ,Ｈ1を読み出す（ステップＳ１２１）。一方、乱数生成部１１３は乱数ｋiを生成する（ステップＳ１２２）。すると公開鍵計算部１１８は、ｉ番目の署名者の公開鍵ＱIDiを次式
ＱIDi＝Ｈ1(ＩＤi)
に従って計算する（ステップＳ１２３）。
【０１３８】
第１署名部１１４は、上記公開鍵ＱIDiの計算結果を利用し、次式
Ｒi＝ｔi(Ｒi-1＋ＱIDi)＋ｋiＱ
に従う計算によって、秘密情報ｔiと点（署名）Ｒi-1と公開鍵ＱIDiとに依存し、且つ乱数ｋiと点Ｑとに依存する点Ｒiを署名（第１の署名データ）として生成する（ステップＳ１２４）。ＱIDiは前記したように＜Ｐ＞に属する点である。したがってＲiは、例えば第２の変形例と異なり、＜Ｑ＞に属する点だけでなく、＜Ｐ＞に属する点をも含むことに注意されたい。また、Ｒiに含まれるｔiＱIDiは、第２の変形例における順序鍵Ｇiそれ自体ではないが、当該順序鍵Ｇiに相当する。つまりステップＳ１２４で生成されるＲiは、第２の変形例における署名Ｒiと順序鍵Ｇiとの両要素を含むことと等価である。このようにステップＳ１２４では、署名生成と順序鍵の要素(隠れ順序鍵)との生成が同時に行われる。なお、ｉ＝１の場合の署名生成装置１１-i、つまり署名生成装置１１-1では、Ｒi-1＝Ｒ0＝０が用いられるものとする。この場合、Ｒ1＝ｔ1ＱID1＋ｋ1Ｑとなる。
【０１３９】
署名送信部１１７は、第１署名部１１４によって生成されたＲiと、当該Ｒiの生成に用いられたＲi-1とを、ｉ＋１番目の署名者が使用する署名生成装置１１-(i+1)に送信する（ステップＳ１２５）。但し、ｉ＝ｎの場合の署名生成装置１１-i、つまり署名生成装置１１-nは、Ｒi及びＲi-1、つまりＲn及びＲn-1を署名検証装置１２に送信する。
【０１４０】
次に、署名生成装置１１-iによる順序鍵生成を含む２巡目の署名生成処理について図１５のフローチャートを参照して説明する。今、署名生成装置１１-(i-1）の署名送信部１１７から署名生成装置１１-i宛てに送信された部分署名（Ｓi-1,Ｒn）と平文Ｍとが、当該署名生成装置１１-iの署名受信部１１６によって受信されたものとする。
【０１４１】
この状態において、署名生成装置１１-iの公開情報読出部１１２は、センター装置１０または公開情報記憶部１１１ａから公開情報であるＱ,Ｑpub,Ｐpub,Ｈ1,Ｈ3,Ａi-1を読み出す（ステップＳ１３１）。すると公開鍵計算部１１８は、ｉ−１番目の署名者の公開鍵ＱIDi-1を次式
ＱIDi-1＝Ｈ1(ＩＤi-1)
に従って計算する（ステップＳ１３２）。
【０１４２】
順序鍵生成部１２１は、順序鍵Ｂi-1を、１巡目で受信されたＲi-1と、公開情報Ｑpubとを用いて、次式
Ｂi-1＝ｅ(Ｒi-1,Ｑpub)
に従う計算を行うことによって生成（復元）する（ステップＳ１３３）。
【０１４３】
すると順序鍵検査部１２２は、ステップＳ１３３で生成された順序鍵Ｂi-1が正当であるか否かを、１巡目で受信されたＲi-2と、公開鍵ＱIDi-1と、公開情報Ａi-1とに基づき、次式
Ｂi-1＝ｅ(Ｒi-2＋ＱIDi-1,Ａi-1)                              …（２２）
が成立するか否かによって検証する（ステップＳ１３４,Ｓ１３５）。ここで、Ａi-1は＜Ｑ＞に属する点であることから、ｅ(Ｒi-2＋ＱIDi-1,Ａi-1)によって、Ｒi-2に含まれる＜Ｑ＞に属する点の要素がキャンセルされる。このことは、式（２２）が、上記第２の変形例での順序鍵Ｇi-1の検証に用いられた式（１９）と等価であることを示す。
【０１４４】
もし、上記式（２２）が成立しないならば、順序鍵検査部１２２は順序鍵Ｂi-1が不正であると判定する。この場合、署名生成装置１１-iでの処理は終了する。これに対して上記式（２２）が成立するならば、順序鍵検査部１２２は順序鍵Ｂi-1が正当であると判定する。
【０１４５】
公開鍵計算部１１８は、順序鍵Ｂi-1が正当であると判定された場合、受信された部分署名（Ｓi-1,Ｒn）が正当であるか否かを、当該順序鍵Ｂi-1と、平文Ｍと、公開情報Ｐpubと、ハッシュ関数Ｈ3と、署名Ｒn及びＲi-1とに基づき、次式
ｅ(Ｓi-1,Ｑ)＝Ｂi-1ｅ(Ｈ3(Ｍ,Ｒn)Ｐpub,Ｒi-1)
＝ｅ(Ｒi-1,Ｑpub)ｅ(Ｈ3(Ｍ,Ｒn)Ｐpub,Ｒi-1)      …（２３）
が成立するか否かによって検査する（ステップＳ１３６,Ｓ１３７）。ここで、Ｐpub,Ｑpubは、それぞれ＜Ｐ＞,＜Ｑ＞に属する点である。このため、ｅ(Ｒi-1,Ｑpub)によって、Ｒi-1に含まれる＜Ｐ＞に属する点の要素（順序鍵Ｇi-1に相当する要素）が抽出される。また、ｅ(Ｈ3(Ｍ,Ｒn)Ｐpub,Ｒi-1)によって、Ｒi-1に含まれる＜Ｑ＞に属する点の要素（第２の変形例におけるＲiに相当する要素）が抽出される。このことは、式（２３）が、上記第２の変形例での部分署名(Ｓi-1,Ｒn)の検証に用いられた式（２１）と等価であることを示す。
【０１４６】
もし、上記式（２３）が成立しないならば、署名検査部１１９は部分署名が不正であると判定する。この場合、署名生成装置１１-iでの処理は終了する。これに対して上記式（２３）が成立するならば、署名検査部１１９は部分署名が正当であると判定する。
【０１４７】
第２署名部１１５は、部分署名が正当であると判定された場合、平文Ｍと、乱数ｋiと、公開情報Ｐpubと、ｉ番目の署名者の秘密情報ｔiと、ｉ番目の署名者の秘密鍵ＤIDiと、ハッシュ関数Ｈ3と、署名Ｓi-1及びＲnとを用いて、次式
Ｓi＝ｔi(Ｓi-1＋ＤIDi)＋ｋiＨ3(Ｍ,Ｒn)Ｐpub
に従う計算を行うことによって、署名（第２の署名データ）Ｓiを生成する（ステップＳ１３８）。ＤIDi及びＰpubは＜Ｐ＞に属する点である。したがって、Ｓiも＜Ｐ＞に属する点である。
【０１４８】
署名送信部１１７は、署名生成装置１１-(i-1)から送信（伝達）されたＲnに、署名生成装置１１-iにて生成されたＳiを付加し、部分署名（Ｓi,Ｒn）として、署名生成装置１１-(i-1)から送信された平文Ｍと共に、ｉ＋１番目の署名者が使用する署名生成装置１１-(i+1)に送信する（ステップＳ１３９）。但し、ｉ＝ｎの場合の署名生成装置１１-i、つまり署名生成装置１１-nは、（Ｓi,Ｒn）つまり（Ｓn,Ｒn）と平文Ｍとを、署名検証装置１２に送信する。
【０１４９】
なお、１番目（ｉ＝１）の署名者が利用する署名生成装置１１-1ではステップＳ１３２乃至Ｓ１３７は実行されない。また、署名生成装置１１-1では、ステップＳ１３８において、Ｓi-1＝Ｓ0＝０としてＳi＝Ｓ1が計算される。
【０１５０】
次に、署名検証装置１２による多重署名に対する検証処理について図１６のフローチャートを参照して説明する。今、署名生成装置１１-nの署名送信部１１７から署名検証装置１２宛てに送信された多重署名（Ｓn,Ｒn）及び平文Ｍが、当該署名検証装置１２の署名受信部１１６によって受信されたものとする。
【０１５１】
この状態において、署名検証装置１２の公開情報読出部１１２は、センター装置１０または公開情報記憶部１１１ａから公開情報であるＱ,Ｑpub,Ｐpub,Ｈ1,Ｈ3,Ａnを読み出す（ステップＳ１４１）。すると公開鍵計算部１１８は、ｎ番目の署名者の公開鍵ＱIDnを次式
ＱIDn＝Ｈ1(ＩＤn)
に従って計算する（ステップＳ１４２）。
【０１５２】
順序鍵生成部１２１は、順序鍵Ｂnを、受信されたＲnと、公開情報Ｑpubとを用いて、次式
Ｂn＝ｅ(Ｒn,Ｑpub)
に従う計算を行うことによって生成（復元）する（ステップＳ１４３）。
【０１５３】
すると順序鍵検査部１２２は、ステップＳ１４３で生成された順序鍵Ｂnを、１巡目で受信されたＲn-1と、公開鍵ＱIDnと、公開情報Ａnとに基づき、次式
Ｂn＝ｅ(Ｒn-1＋ＱIDn,Ａn)
が成立するか否かによって検証する（ステップＳ１４４）。
【０１５４】
署名検査部１１９は、順序鍵Ｂnが正当であるならば、署名送信部１１７によって受信された多重署名（Ｓn,Ｒn）が正当であるか否かを、点Ｑと、平文Ｍと、順序鍵Ｂnと、公開情報Ｐpubと、ハッシュ関数Ｈ3と、署名Ｒnとに基づき、次式
ｅ(Ｓn,Ｑ)＝Ｂnｅ(Ｈ3(Ｍ,Ｒn)Ｐpub,Ｒn)
＝ｅ(Ｒn,Ｑpub)ｅ(Ｈ3(Ｍ,Ｒn)Ｐpub,Ｒn)
が成立するか否かによって検証する（ステップＳ１４５）。
【０１５５】
上述した第３の変形例によれば、署名Ｓiの生成と同時に順序鍵Ｒiが生成される。したがって、第３の変形例で適用される縦列型の多重署名（２巡型多重署名）方法は、署名順序の変更が頻繁にある場合に有効である。なお、上記Ｂnを
Ｂn＝ｅ(Ｒn,Ｈ2(Ｍ,Ｒn)Ｑpub)
または
Ｂn＝ｅ(Ｒn,Ｈ2(Ｍ)Ｑpub)
とすることも可能である。この場合、上記Ｈ3(Ｍ,Ｒn)に代えてＨ3(Ｒn)を用いることも可能である。
【０１５６】
なお、本発明は、上記実施形態またはその変形例そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。例えば、上記実施形態またはその変形例では、Ｐ,Ｑが、有限体Ｆq上の楕円曲線Ｅのｎねじれ点の集合Ｅ[ｎ]の元であるとしたが、ペアリングが定義可能な代数曲線であれば、楕円曲線に限るものではない。また、上記実施形態またはその変形例に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態またはその変形例に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【０１５７】
【図１】本発明の一実施形態に係る電子署名システムの基本構成を示すブロック図。
【図２】署名生成装置１１-1〜１１-n及び署名検証装置１２の構成を示すブロック図。
【図３】同実施形態におけるＩＤをベースとした変形ElGamal署名の基本的な動作の手順を示すフローチャート。
【図４】同実施形態で適用される１巡型多重署名法における署名生成処理の手順を示すフローチャート。
【図５】上記１巡型多重署名法における署名検証処理の手順を示すフローチャート。
【図６】上記実施形態の第１の変形例で適用される２巡型多重署名法（並列型）における１巡目の署名生成処理の手順を示すフローチャート。
【図７】上記２巡型多重署名法（並列型）における２巡目の署名生成処理の手順を示すフローチャート。
【図８】前記２巡型多重署名法（並列型）における署名検証処理の手順を示すフローチャート。
【図９】上記実施形態の第２の変形例で適用される２巡型多重署名法（縦列型）における順序鍵生成処理の手順を示すフローチャート。
【図１０】上記第２の変形例における順序鍵検証処理の手順を示すフローチャート。
【図１１】上記第２の変形例における１巡目の署名生成処理の手順を示すフローチャート。
【図１２】上記第２の変形例における２巡目の署名生成処理の手順を示すフローチャート。
【図１３】上記第２の変形例における署名検証処理の手順を示すフローチャート。
【図１４】上記実施形態の第３の変形例で適用される２巡型多重署名（縦列型）における１巡目の署名生成処理の手順を示すフローチャート。
【図１５】上記第３の変形例における順序鍵生成を含む２巡目の署名生成処理の手順を示すフローチャート。
【図１６】上記第３の変形例における署名検証処理の手順を示すフローチャート。
【符号の説明】
【０１５８】
１０…センター装置、１１-1〜１１-n…署名生成装置、１２…署名検証装置、１３…通信ネットワーク、１１０…秘密鍵記憶装置、１１１…記憶装置、１１１ａ…公開情報記憶部、１１１ｂ…公開鍵記憶部、１１１ｃ…署名記憶部、１１２…公開情報読出部、１１３…乱数生成部、１１４…第１署名部、１１５…第２署名部、１１６…署名受信部、１１７…署名送信部、１１８…公開鍵計算部、１１９…署名検査部、１２０…制御部、１２１…順序鍵生成部、１２２…順序鍵検査部。
【図１】
2006203825.tif 000003
【図２】
2006203825.tif 000004
【図３】
2006203825.tif 000005
【図４】
2006203825.tif 000006
【図５】
2006203825.tif 000007
【図６】
2006203825.tif 000008
【図７】
2006203825.tif 000009
【図８】
2006203825.tif 000010
【図９】
2006203825.tif 000011
【図１０】
2006203825.tif 000012
【図１１】
2006203825.tif 000013
【図１２】
2006203825.tif 000014
【図１３】
2006203825.tif 000015
【図１４】
2006203825.tif 000016
【図１５】
2006203825.tif 000017
【図１６】
2006203825.tif 000018