(57)【要約】【課題】管理者を不要とし、署名者の匿名性を有し、署名者以外のユーザによる否認が可能であり、検証をオフラインで実施できるデジタル署名情報を生成するデジタル署名情報生成装置を提供すること。【解決手段】  署名生成端末は、署名対象の文書と署名者の秘密鍵を用いて、署名者以外のユーザの否認を可能にする第１の成分を生成し、署名者以外のユーザの公開鍵の全部又は一部と該秘密鍵を用いて、第１の情報が該秘密鍵を用いて生成されたことを保証する第２の成分を生成し、第１の成分と第２の成分を含むデジタル署名情報を出力する。署名検証端末は、検証をオフラインで実施でき、署名者の特定又は否認は署名検証端末との間のオンラインでの実施となる。【選択図】      図５
2006203660.tif 000002
【特許請求の範囲】
【請求項１】
署名対象のデータを入力する入力手段と、
前記データに対する署名者となる第１のユーザの秘密鍵を記憶する記憶手段と、
前記第１のユーザ以外の第２のユーザの公開鍵の全部又は一部を取得する取得手段と、
前記データ及び前記秘密鍵を用いて、個々の前記第２のユーザが前記データに対する署名者であることを否認することを可能にする第１の情報を生成する第１の生成手段と、
前記公開鍵の全部又は一部及び前記秘密鍵を用いて、前記第１の情報が前記秘密鍵を用いて生成されたことを保証するための第２の情報を生成する第２の生成手段と、
前記第１の情報及び前記第２の情報を含むデジタル署名情報を出力する出力手段とを備えたことを特徴とするデジタル署名情報生成装置。
【請求項２】
前記出力手段は、前記デジタル署名情報に、前記第２の情報の生成に用いた公開鍵又はこれらを特定可能な情報を含む第３の情報をも含めて出力するものであることを特徴とする請求項１に記載のデジタル署名情報生成装置。
【請求項３】
前記第１の生成手段及び前記第２の生成手段は、前記第１の情報及び前記第２の情報の生成に乱数をも用いるものであることを特徴とする請求項１または２に記載のデジタル署名情報生成装置。
【請求項４】
前記データは、前記第１の情報及び前記第２の情報を用いて検証されるものであることを特徴とする請求項１ないし３のいずれか１項に記載のデジタル署名情報生成装置。
【請求項５】
前記第２の情報は、非対話零知識証明を用いて検証されるものであることを特徴とする請求項１ないし３のいずれか１項に記載のデジタル署名情報生成装置。
【請求項６】
前記第２の生成手段は、前記第２の情報を生成するにあたって、前記公開鍵の全部を用いる方法、前記公開鍵のうちから予め定められた数を選択して用いる方法、又は使用すべき公開鍵の数を決定し、前記公開鍵のうちから当該決定された数を選択して用いる方法のいずれかを採るものであることを特徴とする請求項１ないし３のいずれか１項に記載のデジタル署名情報生成装置。
【請求項７】
前記デジタル署名情報を用いた検証を行う署名検証装置と通信するための手段を更に備えたことを特徴とする請求項１ないし６のいずれか１項に記載のデジタル署名情報生成装置。
【請求項８】
署名対象のデータを入力するステップと、
前記データ及び前記データに対する署名者となる第１のユーザの秘密鍵を用いて、前記第１のユーザ以外の個々の第２のユーザが前記データに対する署名者であることを否認することを可能にする第１の情報を生成するステップと、
前記第１のユーザ以外の第２のユーザの公開鍵の全部又は一部及び前記秘密鍵を用いて、前記第１の情報が前記秘密鍵を用いて生成されたことを保証するための第２の情報を生成するステップと、
前記第１の情報及び前記第２の情報を含むデジタル署名情報を出力するステップとを有することを特徴とするデジタル署名情報生成方法。
【請求項９】
デジタル署名情報生成装置としてコンピュータを機能させるためのプログラムにおいて、
前記プログラムは、
署名対象のデータを入力するステップと、
前記データ及び前記データに対する署名者となる第１のユーザの秘密鍵を用いて、前記第１のユーザ以外の個々の第２のユーザが前記データに対する署名者であることを否認することを可能にする第１の情報を生成するステップと、
前記第１のユーザ以外の第２のユーザの公開鍵の全部又は一部及び前記秘密鍵を用いて、前記第１の情報が前記秘密鍵を用いて生成されたことを保証するための第２の情報を生成するステップと、
前記第１の情報及び前記第２の情報を含むデジタル署名情報を出力するステップとをコンピュータに実行させるものであることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル署名情報を生成するためのデジタル署名情報生成装置、デジタル署名情報生成方法及びプログラムに関する。
【背景技術】
【０００２】
情報化社会の発展に伴い、データをデジタル化しネットワークを通じてやり取りするコミュニケーション形態が増加している。デジタルデータ（以下、データとはデジタルデータを指すものとする）は、第三者による作成や複製や改ざん等が容易であるため、データの真正性が重要になる場合には、データに信頼性を持たせるためにデジタル署名（電子署名）の技術が利用される。
【０００３】
基本的なデジタル署名では、例えば、署名者側においては、署名対象のデータにハッシュ関数を適用してハッシュ値を求め、このハッシュ値を署名者の秘密鍵で変換してデジタル署名情報を生成し、このデジタル署名情報を署名対象データに付加して、デジタル署名付データとする。一方、検証者側においては、例えば、検証対象のデジタル署名付データのデータ部分にハッシュ関数を適用して得た第１のデータと、検証対象のデータに付加されているデジタル署名情報を署名者とされている者の公開鍵で逆変換して得た第２のデータとを比較することによって、検証を行う。
【０００４】
デジタル署名情報の偽造や秘密鍵の解読は困難であることから、デジタル署名情報を用いた検証により、署名者とされるユーザがデータに電子証明を行ったという事実（確かに当該データ及び当該署名者の秘密鍵を用いて当該デジタル署名が生成されたという事実）が保証できる。
【０００５】
なお、本明細書において、グループ管理者、署名者、検証者、認証局等について説明する動作は、基本的には、それらに係る装置の動作を意味するものである。
【０００６】
ところで、ネットワーク上のサービスの多様化により、デジタル署名にも様々な機能が求められている。例えば、電子決済や電子投票等において署名者個人のプライバシー保護を実現するために、匿名性を有するデジタル署名が開発されている。匿名性を有するデジタル署名においては、これを利用するユーザは、複数のユーザが加入するグループに所属する。そして、署名者となるユーザは、そのグループに対応する公開鍵で正当性の検証が可能なデジタル署名あるいはそのグループに属する全てのユーザの公開鍵で正当性の検証が可能なデジタル署名を、当該ユーザ自身の秘密鍵を用いて生成する。匿名性を保証するデジタル署名は、検証者がそのグループに属する者のうちのいずれかが当該デジタル署名を生成した事実を検証することはできるが、当該デジタル署名を実際に生成した署名者を特定することはできない。
【０００７】
従来の匿名性を保証する署名方法は、大きく二つに分類される。一つはグループ署名（例えば非特許文献１参照）であり、もう一つはリング署名（例えば特許文献１参照）である。以下、従来のグループ署名とリング署名について簡単に説明する。
【０００８】
グループ署名では、署名者は、グループ管理者と交信を行って署名鍵を生成する。グループ管理者は、グループに対応する公開鍵を生成して認証局に登録する。このとき、グループに対応する公開鍵が予め定められていて各署名者の署名鍵を生成する方法と、各署名者からグループへの参加及び署名鍵の生成を受けるたびに公開鍵を更新して認証局に再登録を行う方法とがある。署名は、証明者の署名鍵を用いて行われ、検証は、グループに対応する公開鍵を用いて行われる。
【０００９】
従来のグループ署名では、グループ管理者が署名者を特定することが可能であるため、署名者が意図しないところで署名者の特定が行われて匿名性の破棄すなわちプライバシーに係る情報の暴露がなされる可能性があった。また、署名者は署名鍵を生成するためにグループ管理者と交信を行わなければならず鍵生成の効率が悪いことに加えて、グループ管理者に秘密情報が集中するためグループ管理者の管理を厳密に行わなければならないという問題点があった。
【００１０】
また、グループ管理者を必要としないグループ署名方式も提案されているが、検証のために検証者と署名者との間のオンラインによる多数回の交信が行われる必要があるため、検証処理の効率が悪いことに加えて、匿名性を保証するために匿名通信技術を用いる必要があった。
【００１１】
すなわち、従来のグループ署名においては、管理者を不要とし、署名者の匿名性を有し、署名者以外のユーザによる否認（自身が真の署名者ではないことの主張）が可能であり、検証をオフラインで実施できるものはなかった。
【００１２】
一方、リング署名では、署名は、動的に選択され認証局から入手された複数の他のユーザの公開鍵及び署名者の署名鍵を用いて行われ（以下、公開鍵が選択された他のユーザを、真の署名者に対してダミー署名者と呼ぶ）、検証は、署名者及びダミー署名者の公開鍵を用いて行われる。
【００１３】
従来のリング署名においても、管理者を不要とし、署名者の匿名性を有し、署名者以外のユーザによる否認が可能であり、検証をオフラインで実施できるものはなかった。
【特許文献１】特開２００４−２２９１３７公報
【非特許文献１】「須賀，市村，“否認機能を持つリング署名”，暗号と情報セキュリティシンポジウム２００３」
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従来のデジタル署名においては、管理者を不要とし、署名者の匿名性を有し、署名者以外のユーザによる否認が可能であり、検証をオフラインで実施できるものはなかった。
【００１５】
本発明は、上記事情を考慮してなされたもので、管理者を不要とし、署名者の匿名性を有し、署名者以外のユーザによる否認が可能であり、検証をオフラインで実施できるデジタル署名情報を生成するデジタル署名情報生成装置、デジタル署名情報生成方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明は、署名対象のデータを入力する入力手段と、前記データに対する署名者となる第１のユーザの秘密鍵を記憶する記憶手段と、前記第１のユーザ以外の第２のユーザの公開鍵の全部又は一部を取得する取得手段と、前記データ及び前記秘密鍵を用いて、個々の前記第２のユーザが前記データに対する署名者であることを否認することを可能にする第１の情報を生成する第１の生成手段と、前記公開鍵の全部又は一部及び前記秘密鍵を用いて、前記第１の情報が前記秘密鍵を用いて生成されたことを保証するための第２の情報を生成する第２の生成手段と、前記第１の情報及び前記第２の情報を含むデジタル署名情報を出力する出力手段とを備えたことを特徴とする。
【００１７】
署名対象のデータにデジタル署名情報が付加されて、署名付きデータとして、受け渡しされる。署名付きデータは、デジタル署名情報生成装置と署名検証装置との間で、通信媒体を介して付け渡しされてもよいし、記録媒体を介して付け渡しされてもよい。
【００１８】
署名検証装置は、署名対象のデータ、該データに付加されたデジタル署名情報並びに署名者及びダミー署名者の公開鍵により、（オフラインで）検証を行うことができる。また、特定の署名者が署名を生成したか否かについての特定が必要な場合には、署名検証装置からデジタル署名情報生成装置に問い合わせて（オンラインの対話により）当該装置に係るユーザが当該デジタル署名情報を生成したこと又は当該デジタル署名情報を生成していないことを検証する。
【００１９】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。  
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムとしても成立し、該プログラムを記録したコンピュータ読み取り可能な記録媒体としても成立する。
【発明の効果】
【００２０】
本発明によれば、管理者を不要とし、署名者の匿名性を有し、署名者以外のユーザによる否認が可能であり、検証をオフラインで実施できるデジタル署名情報を生成するデジタル署名情報生成装置、デジタル署名情報生成方法及びプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面を参照しながら本発明の実施形態について説明する。
【００２２】
ここで、本実施形態に係るデジタル署名について説明するのに先立って、非特許文献１に開示されたデジタル署名について言及する。
【００２３】
非特許文献１では、署名者の人数をＬ人とし、各署名者Ｐｉ（ｉ∈｛０，…，Ｌ−１｝）は公開情報（ｐi，ｑｉ，ｇｉ，ｙｉ，Ｈｉ）を公開しているものとする。ただし、ｐｉとｑｉは、ｑｉがｐｉ−１を割り切るような十分大きな素数とする。ｇｉは位数がｑｉとなるＺ／ｐｉＺ＝｛０，１，…，ｐｉ−１｝内の乗法群Ｇの生成元とする。ｙｉは署名者が秘密裏に保持する秘密情報xｉ∈Ｚ／ｑｉＺ＝｛０，１，…，ｑｉ−１｝に対してｙｉ＝ｇxi  ｍｏｄ  ｐｉより計算される値である。Ｈｉは任意のビット長の値をＧの元に写すハッシュ関数とする。また、Ｈを任意のビット長の値をｌ1ビットの値に写すような、全ての署名者が共通で用いるハッシュ関数とする。
【００２４】
非特許文献１において、署名者Ｐｋは、他の署名者の公開鍵を利用して２種類の署名を生成する。１つ目は、文書Ｍと署名者以外のユーザが自分は署名を生成していないということを主張するための成分Ｒｅｐに対する署名であり、２つ目は文書ＭとＲｅｐのハッシュ値Ｈ（Ｒｅｐ）に対する署名である。
【００２５】
１つ目の署名成分の計算は以下の通りである。
【００２６】
署名者Ｐkは、ａ’∈Ｚ／ｑkＺをランダムに選択し、Ｔ’k＝ｇka’  ｍｏｄ  ｐk及びｃ’k+1＝Ｈk（Ｍ，Ｒｅｐ，Ｔ’k）を計算する。
【００２７】
次に、署名者Ｐkは、ｊ＝ｋ＋１，…，Ｌ−１，０（＝Ｌ），…，ｋ−１について、ｓ’j∈Ｚ／ｑjＺをランダムに選択し、Ｐjの公開情報（ｐj，ｑj，ｇj，ｙj，Ｈj）を用いて、Ｔ’j＝ｇjs’jｙjc’j  ｍｏｄ  ｐj及びｃ’j+1＝Ｈj（Ｍ，Ｒｅｐ，Ｔ’j）を計算する。
【００２８】
最後に、署名者Ｐkは、ｓ’k＝ａ’−ｘkｃ’k  ｍｏｄ  ｑkを計算し、Ｒ１＝（Ｈ（Ｒｅｐ），ｃ’０，ｓ’０，…，ｃ’L-1，ｓ’L-1）を１つ目の署名成分とする。
【００２９】
２つ目の署名成分の計算は以下の通りである。
【００３０】
署名者Ｐkは、ａ’’＝Ｈ（Ｒ１）を計算してａ＝ａ’＋ａ’’  ｍｏｄ  ｑkとおいて、Ｔk＝ｇkａ  ｍｏｄ  ｐk及びｃk+1＝Ｈk（Ｍ，Ｈ（Ｒｅｐ），Ｔk）を計算する。
【００３１】
次に、署名者Ｐkは、ｊ＝ｋ＋１，…，Ｌ−１，０（＝Ｌ），…，ｋ−１について、ｓj∈Ｚ／ｑjＺをランダムに選択し、Ｐjの公開情報（ｐj，ｑj，ｇj，ｙj，Ｈj）を用いて、Ｔj＝ｇjsjｙjcj  ｍｏｄ  ｐj及びｃj+1＝Ｈj（Ｍ，Ｈ（Ｒｅｐ），Ｔj）を計算する。
【００３２】
最後に、署名者Ｐkは、ｓk＝ａ−ｘkｃk  ｍｏｄ  ｑkを計算し、Ｒ２＝（ｃ０，ｓ０，…，ｃL-1，ｓL-1）を２つ目の署名成分とする。
【００３３】
このとき、非特許文献１に開示されている通り、２つ目の署名成分の計算におけるａ＝ａ’＋Ｈ（Ｒ１）  ｍｏｄ  ｑkが正しく生成されているかを保証する手段はなく、署名者が偽りなくａを生成している場合にのみ、署名者以外のユーザが「自分は署名を生成していない」ことを主張できる。
【００３４】
次に、非特許文献１において、署名者が偽りなく署名を生成した場合には、署名から署名者の特定が可能となることを説明する。
【００３５】
署名者Ｐiの公開情報（ｐi，ｑi，ｇi，ｙi，Ｈi）、文書Ｍ、Ｒｅｐ、署名Ｒ１＝（Ｈ（Ｒｅｐ），ｃ’０，ｓ’０，…，ｃ’L-1，ｓ’L-1）、署名Ｒ２＝（ｃ０，ｓ０，…，ｃL-1，ｓL-1）が公開されているとする。このとき、署名者Ｐkの署名生成手段から、ｇkskｙkck＝ｇa-xkckｙkck＝ｇka  ｍｏｄ  ｐkとｇks’ｋｙkc’k＝ｇa’-xkc’kｙkc’k＝ｇka’  ｍｏｄｐkが成り立つ。ここで、署名者を特定しようと試みるもの（非特許文献１に開示される方法の匿名性を破ろうとするもの）は、ａ’’＝Ｈ（Ｒ１）を計算し、ｇisiｙici≡ｇis’iｙic’iｇia’’  （ｍｏｄ  ｐi）となるｉを全数探索により決定する。ｉ＝ｋについてはａ＝ａ’＋ａ’’  ｍｏｄ  ｑｋであるため、上述した合同式が成り立つ。一方、ｉ≠ｋについてはｃi及びｃ’iがハッシュ関数の出力であるため、上述の合同式を満たす可能性は低い。このため、上述した合同式により決定されるｉに対してＰiが署名者であると特定することが可能となる。
【００３６】
このように非特許文献１に開示された技術では、「署名者以外のユーザが自分は署名を生成していないということを証明できる成分（２種類の署名）」が偽りなく生成されたかどうかを確認する手段がないため、偽ったデジタル署名情報を生成することで、検証には成功するが、署名者自身も署名成の事実を否認できるような署名を生成することができるという問題があるとともに、検証者によりデジタル署名から署名者を容易に特定することができるという問題がある。
【００３７】
一方、本実施形態によれば、署名者は、「署名者以外の他のユーザが自分はデジタル署名情報を生成していない（自分は署名者ではない）ということを証明できる」第１の成分を、他のユーザの公開鍵を用いずに生成する。さらに、署名者は、「署名者が第１の成分を正しく生成していることを保証する」第２の成分を計算するため、署名者が偽って検査式に合格するデジタル署名情報を生成することは不可能である。よって、上述したような問題は起こらない。
【００３８】
以下、本実施形態のデジタル署名について詳しく説明する。
【００３９】
なお、以下の説明では、デジタル署名の対象を文書と呼んでいるが、文書はどのようなデータであっても構わない。
【００４０】
本実施形態に係るデジタル署名情報（以下、単に署名とも呼ぶ）を生成するデジタル署名情報生成装置により、管理者を仮定しない否認可能なオフライン検証型の匿名性を有するデジタル署名が実現される。また、デジタル署名した署名者の特定又は署名者以外の他のユーザのデジタル署名についての否認は、検証者が署名者又は署名者以外の他のユーザと通信をすることによって可能になる。
【００４１】
まず、本実施形態に係る署名生成処理で生成される署名者の特定又は否認を可能とする成分について説明する。
【００４２】
署名者の特定又は否認を可能とする成分及びその特定又は否認の方法は、ゼロ知識否認不可署名（例えば、「D. Chaum, “Zero-Knowledge Undeniable Signature,” in Proceedings of EUROCRYPT ’90」など）を利用することができる。
【００４３】
本実施形態では、安全性の保証を可能とするため、岡本らにより改良された否認不可署名（「T. Okamoto and D. Pointcheval, “,” in Proceedings of CT-RSA 2001」（以下、文献Ａと呼ぶ））を利用した場合を例にとって説明する。
【００４４】
ここで、文献Ａにより開示された方法について説明する。
【００４５】
なお、文献Ａは、匿名性がなく、検証にオンラインを必要とするものであるが、本実施形態は、匿名性を有し、検証をオフラインで実施できるものである。
【００４６】
システムの管理者あるいは署名者となる各ユーザは、ｐ，ｑ，ｇ，Ａ，Ｆを公開する。ここで、ｐはｌビットの素数、ｑはｐ−１を割り切るｌ1ビットの素数、ｇは位数ｑの乗法群Ａの生成元であり、Ｇは任意のビット長の数からＡへの耐衝突一方向性ハッシュ関数、Ｆは任意の長さの数からｌ2ビットの数への耐衝突一方向性ハッシュ関数とする。ここで、耐衝突性とはＧ（ａ）＝Ｇ（ｂ）を満たすａ，ｂを見つけることが困難であることを表し、一方向性とはｃが与えられたときにＧ（ａ）＝ｃを満たすａを見つけることが困難であることを表す。
【００４７】
まず、否認不可署名の鍵の生成から否認不可署名の生成までについて説明する。
【００４８】
図７に、否認不可署名の鍵の生成手順（署名者の加入及び署名生成）を示す。また、図８に、否認不可署名の生成手順を示す。
【００４９】
署名者となるユーザは、ｓ∈Ｚ／ｑＺ＝｛０，１，…，ｑ−１｝をランダムに選択して秘密鍵とし（ステップＳ１０１Ｋ）、ｋ＝ｇs  ｍｏｄ  ｐを計算して（ステップＳ１０２Ｋ）、公開鍵として公開し、あるいは認証局に登録する（ステップＳ１０３Ｋ）。
【００５０】
署名者は、デジタル署名対象の文書Ｍを受け付けた後（ステップＳ１０１Ｓ）、ｗ＝Ｇ（Ｍ）を計算し（ステップＳ１０２Ｓ）、Ｓ＝ｗｓ  ｍｏｄ  ｐを計算して（ステップＳ１０３Ｓ）、（Ｍ，Ｓ）を署名付き文書として公開する（ステップＳ１０４Ｓ）。
【００５１】
一方、検証者は、（Ｍ，Ｓ）が正しい署名付き文書であること又は正しくないこと（署名者がＭに正しく署名をしたこと又はＭに正しく署名をしていないこと）を、署名者と交信を行い以下に説明する確認プロトコル(Confirmation Protocol)あるいは否認プロトコル(Disavowal Protocol)を実行することで検証する。各プロトコルでは、検証者は署名者とK回の繰り返し処理を行い、全ての処理に合格するときに確認または否認を受理する。
【００５２】
図９に、検証装置（署名検証装置）における否認不可署名の検証手順を示す。また、図１０に、署名装置（デジタル署名情報生成装置）における否認不可署名の検証手順を示す。
【００５３】
検証者は、署名付き文書（Ｍ，Ｓ）を、特定のユーザ（例えば、署名者であることを確認しようとする対象のユーザ、または、署名者でないことを確認しようとする対象のユーザ）に問い合わせて（ステップＳ１０１Ｖｖ）、待機する（ステップＳ１０２Ｖｖ）。
【００５４】
この特定のユーザは、問い合わせを受け付けた後（ステップＳ１０１Ｖｓ）、ｗ＝Ｇ（Ｍ）を計算して（ステップＳ１０２Ｖｓ）、Ｓ＝ｗs  ｍｏｄ  ｐが成り立つかどうかを検査して（ステップＳ１０３Ｖｓ）、検査式が成り立つ場合には、（Ｍ，Ｓ）が正しい署名付き文書であるとして検証者に確認プロトコルを実行することを伝え（ステップＳ１０４Ｖｓ）、成り立たない場合には、（Ｍ，Ｓ）が正しくない署名付き文書であるとして検証者に否認プロトコルを実行することを伝えて（ステップＳ１０５Ｖｓ）、待機する（ステップＳ１０６Ｖｓ）。
【００５５】
（確認プロトコル）
図１１に、検証装置（署名検証装置）における否認不可署名の確認手順を示す。また、図１２に、署名装置（デジタル署名情報生成装置）における否認不可署名の確認手順を示す。
【００５６】
検証者は、上記の特定のユーザから確認プロトコルを実行する連絡を受け付けた場合（ステップＳ１０１Ｃｖ）、カウンタとしてcnt=0と設定し（ステップS１０２Ｃｖ）、ｗ＝Ｇ（Ｍ）を計算する（ステップＳ１０３Ｃｖ）。
【００５７】
次に、検証者は、ａ，ｂ∈Ｚ／ｑＺをランダムに選択して（ステップＳ１０４Ｃｖ）、ｃ＝ｗaｇb  ｍｏｄ  ｐを計算して（ステップＳ１０５Ｃｖ）、上記の特定のユーザに送信して（ステップＳ１０６Ｃｖ）、待機する（ステップＳ１０７Ｃｖ）。
【００５８】
上記の特定のユーザは、検証者からｃを受け付けた後（ステップＳ１０１Ｃｓ）、ｒ∈Ｚ／ｑＺをランダムに選択して（ステップＳ１０２Ｃｓ）、ｔ＝ｃｇr  ｍｏｄ  ｐ及びｕ＝ｔs  ｍｏｄ  ｐを計算して（ステップＳ１０３Ｃｓ）、検証者に送信し（ステップＳ１０４Ｃｓ）、待機する（ステップＳ１０５Ｃｓ）。
【００５９】
検証者は、上記の特定のユーザからｔ，ｕを受け付けた後（ステップＳ１０８Ｃｖ）、ａ，ｂを上記の特定のユーザに送信して（ステップＳ１０９Ｃｖ）、待機する（ステップＳ１１０Ｃｖ）。
【００６０】
上記の特定のユーザは、検証者からａ，ｂを受け付けた後（ステップＳ１０６Ｃｓ）、ｃ＝ｗaｇb  ｍｏｄ  ｐが成り立つかどうかを検査する（ステップＳ１０７Ｃｓ）。検査に合格の場合には、ｒを検証者に送信し（ステップＳ１０８Ｃｓ）、不合格の場合には、（例えば、検証者が不正な処理をした、あるいは、通信路上でエラーが発生したと判断して）処理を停止する（ステップＳ１０９Ｃｓ）。
【００６１】
検証者は、上記の特定のユーザからｒを受け付けた後（ステップＳ１１１Ｃｖ）、ｔ＝ｃｇr  ｍｏｄ  ｐ及びｕ＝Ｓaｋb+r  ｍｏｄ  ｐが成り立つかどうか検査する（ステップＳ１１２Ｃｖ）。検査に不合格の場合には、（上記の特定のユーザが不正な処理をした、あるいは、通信路上でエラーが発生したと判断して）処理を停止する（ステップＳ１１７Ｃｖ）。
【００６２】
検査に合格の場合には、cnt=cnt+1とし（ステップS１１３Ｃｖ）、cnt=Kかどうか検査する（ステップS１１４Ｃｖ）。検査に不合格の場合にはステップＳ１０４Ｃｖに戻る（ステップＳ１１５Ｃｖ）。検査に合格の場合には、（Ｍ，Ｓ）を正しい署名付き文書として受理する（ステップＳ１１６Ｃｖ）。
【００６３】
（否認プロトコル）
図１３に、検証装置（署名検証装置）における否認不可署名の否認手順を示す。図１４に、署名装置（デジタル署名情報生成装置）における否認不可署名の否認手順を示す。
【００６４】
他方、検証者は、上記の特定のユーザから否認プロトコルを実行する連絡を受け付けた場合（ステップＳ１０１Ｄｖ）、カウンタとしてcnt=0と設定し（ステップS１０２Ｄｖ）、ｗ＝Ｇ（Ｍ）を計算する（ステップＳ１０3Ｄｖ）。
【００６５】
次に、検証者は、ａ∈｛０，…，ｍａｘ｝とｂ∈Ｚ／ｑＺをランダムに選択して（ステップＳ１０４Ｄｖ），ｃ１＝ｗaｇb  ｍｏｄ  ｐとｃ2＝Ｓaｋb  ｍｏｄ  ｐを計算して（ステップＳ１０５Ｄｖ）、上記の特定のユーザに送信して（ステップＳ１０６Ｄｖ）、待機する（ステップＳ１０７Ｄｖ）。ステップＳ１０３Ｄｖのｍａｘは、後にａが全数探索により見つけられる程度の小さな数として設定される。
【００６６】
上記の特定のユーザは、検証者からｃ1，ｃ2を受け付けた後（ステップＳ１０１Ｄｓ）、（ｃ１ｓ／ｃ2）＝（ｗ／Ｓ）a  ｍｏｄ  ｐを満たすａを探索し（ステップＳ１０２Ｄｓ）、ｒ∈Ｚ／ｑＺをランダムに選択して（ステップＳ１０３Ｄｓ）、ｔ＝Ｆ（ｒ，ａ）を計算して（ステップＳ１０４Ｄｓ）、検証者に送信し（ステップＳ１０５Ｄｓ）、待機する（ステップＳ１０６Ｄｓ）。
【００６７】
検証者は、上記の特定のユーザからｔを受け付けた後（ステップＳ１０８Ｄｖ）、ｂを上記の特定のユーザに送信して（ステップＳ１０９Ｄｖ）、待機する（ステップＳ１１０Ｄｖ）。
【００６８】
上記の特定のユーザは、検証者からｂを受け付けた後（ステップＳ１０７Ｄｓ）、ｃ1＝ｗaｇb  ｍｏｄ  ｐとｃ2＝Ｓaｋb  ｍｏｄ  ｐが成り立つかどうかを検査する（ステップＳ１０８Ｄｓ）。検査に合格の場合には、ｒを検証者に送信して（ステップＳ１０９Ｄｓ）、不合格の場合には、（検証者が不正な処理をした、あるいは、通信路上でエラーが発生したと判断して）処理を停止する（ステップＳ１１０Ｄｓ）。
【００６９】
検証者は、上記の特定のユーザからｒを受け付けた後（ステップＳ１１１Ｄｖ）、ｔ＝Ｆ（ｒ，ａ）が成り立つかどうか検査する（ステップＳ１１２Ｄｖ）。検査に不合格の場合には、（上記の特定のユーザが不正な処理をした、あるいは、通信路上でエラーが発生したと判断して）処理を停止する（ステップＳ１１７Ｄｖ）。
【００７０】
検査に合格の場合には、cnt=cnt+1とし（ステップS１１３Ｄｖ）、cnt=Kかどうか検査する（ステップS１１４Ｄｖ）。検査に不合格の場合にはステップＳ１０４Ｄｖに戻る（ステップＳ１１５Ｄｖ）。検査に合格の場合には、上記の特定のユーザによる（Ｍ，Ｓ）の否認を受理する（ステップＳ１１６Ｄｖ）。
【００７１】
さて、以下では、上記したような否認不可署名を利用した、管理者を仮定しない否認可能なオフライン検証型の匿名性を有する署名方法の構成例を示す。
【００７２】
（第１の構成例）
まず、第１の構成例について説明する。
【００７３】
なお、署名対象の文書にデジタル署名情報を付加した署名付き文書自体は、デジタル署名情報生成装置と署名検証装置との間で、通信媒体を介して付け渡しされてもよいし、記録媒体を介して付け渡しされてもよい。
【００７４】
（共通パラメータの準備）
以下、本構成例に係るデジタル署名情報生成装置、署名検証装置を構成するために用いる関数と、それら関数の入出力データの長さについて説明する。
【００７５】
安全な署名交換システムの構成例を記述するにあたり、安全性のパラメータｌ，ｌ1，ｌ2を以下のように選択する。ｌは離散対数問題が計算困難とされるビット長である１０２４とし、ｌ1はそのときの位数１０２３、ｌ2は総当りによる探索が困難とされるビット長である８０などである。このとき、ｌビットの素数ｐ及びｐ−１を割り切るｌ１ビットの素数ｑ、位数ｑの乗法群Ａとその生成元ｇが認証局により公開されているとする。また、任意のビット長の値をＡの元に写像するハッシュ関数Ｇ、任意のビット長の値をＺ／ｑＺの元に写像するハッシュ関数Ｈ、任意のビット長の値をｌ2ビットの値に写像するハッシュ関数Ｆ、否認プロトコルで用いられるあまり大きくない値ｍａｘが公開されているとする。ハッシュ関数Ｇ，Ｈ，Ｆは、例えばＳＨＡなどのハッシュ関数である（例えば、「M. Bellare and P. Rogaway, “Optimal Asymmetric Encryption−How to encrypt with RSA” Advances in Cryptology−EUROCRYPT’94 LNCS, Springer-Verlag, 1995」等にその具体例が挙げられている）。
【００７６】
（デジタル署名情報生成装置）
図１に、本構成例に係るデジタル署名情報生成装置のブロック図の一例を示す。
【００７７】
演算器２０１は、多倍長の演算を実行する部分であり、具体的には、排他的論理和の計算、ビット連結・分割、ビットの比較などを行う。
【００７８】
乱数生成部２０２は、署名生成時に必要な乱数を発生させる部分である。
【００７９】
乱数メモリ２０３は、乱数生成部２０２により生成された乱数を保存する。
【００８０】
秘密鍵メモリ２０４は、当該装置のユーザＰの公開鍵暗号方式に関する秘密鍵を格納するメモリである。
【００８１】
署名生成部２０５は、署名生成処理や確認及び否認プロトコルを行う際に、秘密鍵メモリ２０４に保存された秘密鍵を読み出す。
【００８２】
入出力部２０６は、生成された当該装置のユーザＰのデジタル署名情報を送信する。入出力部２０６は、自装置と外部との間で取り交わされるその他のデータの入出力も行う。
【００８３】
関数演算部２０７，２０８，２０９は、それぞれ、ランダム関数Ｇ，Ｈ，Ｆによる演算を行う。当該装置のユーザＰのデジタル署名情報の生成や確認及び否認プロトコルにおいては、関数演算部２０７，２０８，２０９に保存されたランダム関数を利用する。ランダム関数は、事前に取り決められたものを保存しておいてもよいし、署名者ごとに定められた関数を入出力部２０６を介して入手・保存してもよい。
【００８４】
制御部２１１は、装置全体の制御を司る。
【００８５】
メモリ２１２は、各種データを記憶する。
【００８６】
なお、デジタル署名情報生成装置は、機能的には、鍵に関する処理を行う機能部分と、後述するデジタル署名情報の第１の成分を生成する機能部分と、デジタル署名情報の第２の成分を生成する機能部分とを有する。
【００８７】
また、デジタル署名情報生成装置は、署名対象の文書にデジタル署名情報を付加した署名付き文書を、ネットワークを介して署名検証装置又は他の装置へ送信する機能や、（署名検証装置又は他の装置との間の受け渡しのために）記録媒体へ書き込む機能を含んでもよい。
【００８８】
（公開鍵及び秘密鍵の準備）
署名者となる各ユーザは、それぞれ、図１に示されるデジタル署名情報生成装置を使用する。認証局により公開されたｐ，ｑ，Ａ，ｇに対して、各ユーザＰj（ｊ＝1，…，Ｌ）は、ｓj∈Ｚ／ｑＺをランダムに選択して秘密鍵メモリ２０４に格納し、公開鍵ｋj＝ｇsj  ｍｏｄ  ｐを計算して公開する。
【００８９】
（署名生成手順）
以下、署名者Ｐiによる署名生成の処理手順について説明する。
【００９０】
図２に、本構成例に係る署名生成処理手順の一例を示す。
【００９１】
以下の例では説明を簡潔にするために、公開鍵を登録しているＬ人のうち、署名者となるユーザＰiを除くＬ−１人のユーザをダミー署名者として選択する方法を例にとって説明する。この方法の他にも、例えば、署名者Ｐiが署名生成時にＬ’≦Ｌ-1を満たす任意のＬ’人のダミー署名者を選択して、ユーザ（署名者たるユーザ、選択されたダミー署名者たるユーザ又は選択されなかったユーザ）を特定するための添え字（以下の例で示すｉやｊ）を動的に決定する方法なども可能である（なお、Ｌ’を固定する方法も可能であり、Ｌ’をも動的に決定する方法も可能である）。
【００９２】
ここで、ステップＳ３０１〜Ｓ３０３により計算されるデジタル署名情報の第１の成分Ｓを利用することで、下記に示す確認及び否認プロトコルにより、署名者Ｐiは、第１の成分Ｓを生成した事実を否認することができず、署名者以外のユーザＰjは、第１の成分Ｓを生成していないという事実を証明することができる。
【００９３】
一方、ステップＳ３０４〜Ｓ３１１で計算されるデジタル署名情報の第２の成分（ｙ，ｂ，ｃ１，ｄ１，…，ｃL，ｄL）は、第１の成分ＳがユーザＰ１，…，ＰLの公開鍵ｋ１，…，ｋLのいずれかの成分と同一の指数（秘密鍵ｓi）をもつことを証明する非対話零知識証明となっている。
【００９４】
署名者Ｐiは、署名対象の文書Ｍを受け付けた後（ステップＳ３０１）、ｗ＝Ｇ（Ｍ）を計算して（ステップＳ３０２）、確認又は否認を行うための第１の成分Ｓ＝ｗsi  ｍｏｄ  ｐを計算する（ステップＳ３０３）。
【００９５】
次に、署名者Ｐiは、第２の成分を計算する。
【００９６】
すなわち、ｂ’∈Ｚ／ｑＺをランダムに選択し（ステップＳ３０４）、ｙ＝ｗb’  ｍｏｄ  ｐを計算する（ステップＳ３０５）。
【００９７】
ｊ＝１，…，ｉ−１，ｉ＋１，…，Ｌについて、ｃj，ｄj∈Ｚ／ｑＺをランダムに選択して、ａj＝ｇcjｋjdj  ｍｏｄ  ｐ，  ｂj＝ｗcjＳdj  ｍｏｄ  ｐを計算する（ステップＳ３０６）。
【００９８】
ｅ’∈Ｚ／ｑＺをランダムに選択し（ステップＳ３０７）、ａi＝ｇｅ’  ｍｏｄ  ｐ，  ｂi＝ｗe’  ｍｏｄ  ｐを計算する（ステップＳ３０８）。
【００９９】
ａ１，ｂ１，…，ａL，ｂLの計算が完了した後、ｄ＝Ｈ（Ｍ，ｗ，Ｓ，ｙ，ｋ１，…，ｋL，ａ１，ｂ１，…，ａL，ｂL）を計算し（ステップＳ３０９）、ｄi＝ｄ−（ｄ１＋…＋ｄi-1＋ｄi+1＋…＋ｄL）  ｍｏｄ  ｑ及びｃi＝ｅ’−ｄiｓi  ｍｏｄ  ｑを計算する（ステップＳ３１０）。
【０１００】
そして、ｂ＝ｂ’＋ｄｓi  ｍｏｄ  ｑを計算する（ステップＳ３１１）。
【０１０１】
最後に、署名者Ｐiは、（Ｍ，Ｓ，ｙ，ｂ，ｃ１，ｄ１，…，ｃL，ｄL，ｋ１，…，ｋL）を署名付き文書として公開する（ステップＳ３１２）。
【０１０２】
なお、（Ｍ，Ｓ，ｙ，ｂ，ｃ１，ｄ１，…，ｃL，ｄL，ｋ１，…，ｋL）において、Ｍが署名対象の文書、Ｓが第１の成分、（ｙ，ｂ，ｃ１，ｄ１，…，ｃL，ｄL）が第２の成分である。
【０１０３】
また、ｋ１，…，ｋLはそれぞれユーザＰ１，…，ＰLの公開鍵である。なお、デジタル署名情報にユーザＰ１，…，ＰLの公開鍵を含ませる代わりに、それらを特定可能とする情報を含ませるようにしてもよい。
【０１０４】
（署名検証装置）
図３に、本実施形態に係る署名検証装置のブロック図の一例を示す。
【０１０５】
演算器４０１は、多倍長の演算を実行する部分であり、具体的には、排他的論理和の計算、ビット連結・分割、ビットの比較などを行う。
【０１０６】
入出力部４０６は、デジタル署名情報生成装置により生成された署名付き文書（Ｍ，Ｓ，ｙ，ｂ，ｃ１，ｄ１，…，ｃL，ｄL，ｋ１，…，ｋL）を受け付ける。入出力部４０６は、自装置と外部との間で取り交わされるその他のデータの入出力も行う。
【０１０７】
判定部４１３は、入出力部４０６から受け付けられたデジタル署名情報について、（Ｍ，Ｓ，ｙ，ｂ，ｃ１，ｄ１，…，ｃL，ｄL，ｋ1，…，ｋL）から構成されるか否かを検査する。
【０１０８】
署名検証部４０７は、ユーザＰ１，…，ＰLの公開鍵ｋ1，…，ｋLを利用してデジタル署名情報を検証する。
【０１０９】
関数演算部４０７，４０８，４０９は、それぞれ、ランダム関数Ｇ，Ｈ，Ｆによる演算を行う。署名検証や確認又は否認プロトコルにおいては、関数演算部４０８，４０９，４１０に保存されたランダム関数を利用する。ランダム関数は、事前に取り決められたものを保存しておいてもよいし、署名者ごとに定められた関数を入出力部４０６を介して入手・保存してもよい。
【０１１０】
制御部４１１は、装置全体の制御を司る。
【０１１１】
メモリ４１２は、各種データを記憶する。
【０１１２】
なお、署名検証装置は、機能的には、鍵に関する処理を行う機能部分と、オフラインでのデータの真正性の検証に関する処理を行う機能部分と、オンラインで署名者の特定又は否認に関する処理を行う機能部分とを有する。
【０１１３】
また、署名検証装置は、署名対象の文書にデジタル署名情報を付加した署名付き文書を、ネットワークを介してデジタル署名情報生成装置又は他の装置から受信する機能や、署名付き文書を記録した記録媒体から読み込む機能を含んでもよい。
【０１１４】
（署名検証手順）
以下、本構成例に係るデジタル署名情報生成装置により生成されたデジタル署名情報を検証する方法について説明する。
【０１１５】
図４に、本構成例に係る署名検証処理手順の一例を示す。
【０１１６】
検証者は、署名付き文書（Ｍ，Ｓ，ｙ，ｂ，ｃ１，ｄ１，…，ｃL，ｄL，ｋ１，…，ｋL）を受け付けた後（ステップＳ５０１）、ｗ＝Ｇ（Ｍ）を計算する（ステップＳ５０２）。
【０１１７】
次に、検証者は、ｊ＝１，…，Ｌについて、ａj＝ｇcjｋjdj  ｍｏｄ  ｐ及びｂj＝ｗcjＳdj  ｍｏｄ  ｐを計算し（ステップＳ５０３）、ｄ＝Ｈ（Ｍ，ｗ，Ｓ，ｙ，ｋ1，…，ｋL，ａ1，ｂ1，…，ａL，ｂL）を計算する（ステップＳ５０４）。
【０１１８】
最後に、検証者は、ｙＳd＝ｗb  ｍｏｄ  ｐかつｄ＝ｄ1＋…＋ｄL  ｍｏｄ  ｑが成り立つかどうか検査して（ステップＳ５０５）、検査に合格なら署名を受理し（ステップＳ５０６）、不合格なら署名を棄却する（ステップＳ５０７）。
【０１１９】
（確認及び否認プロトコル）
本構成例における確認及び否認プロトコルは、（Ｍ，Ｓ）を用いて上述した文献Ａの確認及び否認プロトコルと同じ処理により実行することができる。
【０１２０】
以上説明した第１の構成例では、有限体の乗法群上の離散対数問題を利用した例を示したが、楕円曲線の点のなす加法群に対しても同様のプロトコルが実現可能である。より具体的には、例えば、標数ｐの体上で定義された楕円曲線Ｅの上の点Ｐと、点Ｐで生成される位数ｑの加法群Ａを用いればよい。また、本構成例のｇの代わりにＰを利用し、乗法群における冪乗剰余演算を楕円曲線上のスカラー倍算に、乗法群における剰余乗算を楕円曲線上の加算にそれぞれ置き換えればよい。
【０１２１】
なお、公開鍵は必要に応じて取得できればよく、認証局を用いない構成も可能である。
【０１２２】
本構成例によれば、署名検証時には、署名者と通信を行う必要がなく、署名者の特定あるいは署名者以外のユーザの否認には、対象となるユーザとの通信を必要とするデジタル署名を実現することができる。
【０１２３】
また、本構成例によれば、グループ管理者が不要であり、各署名者が自ら公開鍵と秘密鍵を生成することができるため鍵生成の効率が良く、全署名者の秘密情報が集中することもないため管理が容易となる。さらに、自らが署名者ではない署名で疑いがかけられた場合には、署名生成処理で生成された署名者の特定又は否認が可能となる第１の成分により署名を生成していないという事実を証明できる。また、署名者の特定には署名者を除く全てのダミー署名者が否認を行わない限り署名者との交信が必要であり、署名者が意図しないところでの匿名性の破棄、すなわちプライバシーに係る情報の暴露はより起こりづらい。また、検証処理において検証者と署名者本人との交信が不要となるため、検証処理の効率が良く、匿名通信技術なども不要となる。
【０１２４】
（第２の構成例）
次に、第２の構成例について説明する。
【０１２５】
本構成例は、より高いレベルの安全性を保証するために、第１の構成例で用いた否認不可署名（文献Ａの否認不可署名）の署名生成過程において、署名者が乱数Ｒを生成してｗをＧ（Ｍ，Ｒ）により計算し、Ｍ，Ｒ，Ｓを署名付き文書として公開するようにしたものである。
【０１２６】
以下では、第１の構成例と相違する点を中心に説明する。
【０１２７】
（共通パラメータの準備）
本構成例に係るデジタル署名情報生成装置、署名検証装置を構成するために用いる関数と、それら関数の入出力データの長さについては、第１の構成例と同じである。
【０１２８】
（デジタル署名情報生成装置）
本構成例におけるデジタル署名情報生成装置は、第１の構成例（図１）と同じで構わない。ただし、関数演算部２０７，２０８のランダム関数Ｇ，Ｈは、乱数Ｒをもパラメータとして持つものである。
【０１２９】
（公開鍵及び秘密鍵の準備）
本構成例における公開鍵及び秘密鍵の生成方法は、第１の構成例と同じである。
【０１３０】
（署名生成手順）
本構成例における署名生成手順は、第１の構成例（図２）とほぼ同じであるため、これと相違する点について説明する。
【０１３１】
署名者となるユーザＰiは、署名対象の文書Ｍを受け付けた後（ステップＳ３０１）、乱数Ｒを生成して、ｗ＝Ｇ（Ｍ，Ｒ）を計算して（ステップＳ３０２）、ステップＳ３０８までは第１の構成例における署名生成手順と同じ処理を行う。
【０１３２】
ａ1，ｂ1，…，ａL，ｂLの計算が完了した後、署名者Ｐiは、ｄ＝Ｈ（Ｍ，Ｒ，ｗ，Ｓ，ｙ，ｋ1，…，ｋL，ａ1，ｂ1，…，ａL，ｂL）を計算し（ステップＳ３０９）、ステップＳ３１１まで第１の構成例における署名生成手順と同じ処理を行い、（Ｍ，Ｒ，Ｓ，ｙ，ｂ，ｃ1，ｄ1，…，ｃL，ｄL，ｋ1，…，ｋL）を署名付き文書として公開する（ステップＳ３１２）。
【０１３３】
（署名検証装置）
本構成例における署名検証装置は、第１の構成例（図３）と同じである。ただし、関数演算部４０７，４０８のランダム関数Ｇ，Ｈは、乱数Ｒをもパラメータとして持つものである。
【０１３４】
（署名検証手順）
本構成例における署名生成手順は、第１の構成例（図４）とほぼ同じであるため、これと相違する点について説明する。
【０１３５】
検証者は、署名付き文書（Ｍ，Ｒ，Ｓ，ｙ，ｂ，ｃ1，ｄ1，…，ｃL，ｄL，ｋ1，…，ｋL）を受け付けた後（ステップＳ５０１）、ｗ＝Ｇ（Ｍ，Ｒ）を計算する（ステップＳ５０２）。その後、検証者は第１の構成例と同様にして、ｊ＝１，…，Ｌについてａj＝ｇcjｋjdj  ｍｏｄ  ｐ，  ｂj＝ｗcjＳdj  ｍｏｄ  ｐを計算し（ステップＳ５０３）、ｄ＝Ｈ（Ｍ，Ｒ，ｗ，Ｓ，ｙ，ｋ1，…，ｋL，ａ1，ｂ1，…，ａL，ｂL）を計算する（ステップＳ５０４）。
【０１３６】
最後に、検証者は、ステップＳ４０５を行い、検査結果に応じて、署名を受理し、あるいは署名を棄却する（ステップＳ５０６，Ｓ５０７）。
【０１３７】
（確認及び否認プロトコル）
本構成例における確認及び否認プロトコルは、第１の構成例で用いた確認及び否認プロトコル（文献Ａの確認及び否認プロトコル）とほぼ同じであるが、相違する点は、ｗをＧ（Ｍ）ではなくｗ＝Ｇ（Ｍ，Ｒ）により計算する点（ステップＳ１０２Ｓ，ステップＳ１０２Ｖｓ，ステップＳ１０２Ｃｖ，ステップＳ１０２Ｄｖ）と、署名付き文書を（Ｍ，Ｓ）ではなく（Ｍ，Ｒ，Ｓ）とする点（ステップＳ１０４Ｓ，ステップＳ１０１Ｖｖ，ステップＳ１０４Ｖｓ，ステップＳ１０５Ｖｓ，ステップＳ１１６Ｃｖ，ステップＳ１１７Ｃｖ，ステップＳ１１６Ｄｖ，ステップＳ１１７Ｄｖ）である。
【０１３８】
なお、公開鍵は必要に応じて取得できればよく、認証局を用いない構成も可能である。
【０１３９】
本構成例によれば、第１の構成例の効果に加えて、乱数をも用いることにより、より高いレベルの安全性を保証することができる。
【０１４０】
（第３の構成例）
第３の構成例では、第１の構成例又は第２の構成例を用いたシステムについて説明する。
【０１４１】
なお、以下では、具体例としては、第１の構成例を用いた場合を例示している。
【０１４２】
図５に、本構成例に係るデジタル署名システムの一例を示す。
【０１４３】
本デジタル署名システムには、認証局６０１、署名生成端末（第１又は第２の構成例に係るデジタル署名情報生成装置）６０２1〜６０２Ｌ、署名検証端末６０３が含まれる。これらは、ネットワーク６００を介して通信可能である。
【０１４４】
署名生成端末には、第１又は第２の構成例に係るデジタル署名情報生成装置を用いる。署名検証端末には、第１又は第２の構成例に係る署名検証装置（署名生成端末に対応するもの）を用いる。
【０１４５】
なお、認証局は複数存在してもよい。また、署名検証端末は複数存在してもよい。また、署名生成端末の機能と署名検証装置の機能とを兼ね備えた端末が存在してもよい。
【０１４６】
各認証局及び端末は、それぞれ、固有の識別情報ＩＤを有するものとする。
【０１４７】
（共通パラメータの準備）
まず、認証局６０１は、第１又は第２の構成例の「共通パラメータの設定」に従い、ｌビットの素数ｐ、ｐ−１を割り切るｌ１ビットの素数ｑ、位数ｑの乗法群Ａとその生成元ｇ、任意のビット長の値をＡの元に写像するハッシュ関数Ｇ、任意のビット長の値をＺ／ｑＺの元に写像するハッシュ関数Ｈ、及び、任意のビット長の値をｌ2ビットの値に写像するＦ、否認プロトコルで用いられるあまり大きくない値ｍａｘを公開する。
【０１４８】
（公開鍵及び秘密鍵の準備と登録）
次に、署名生成端末ｉ（ｉは1からＬまでのいずれかをあらわす）は、共通パラメータをネットワーク６００を通じて入手して自端末内部に保存し、第１又は第２の構成例の「公開鍵及び秘密鍵の準備」に基づいて、自端末内で秘密鍵ｓiと公開鍵ｋiを生成して、秘密鍵ｓiを秘密裏に保持し、公開鍵ｋiをネットワーク６００を通じて自らの識別情報ＩＤiとともに認証局６０１に送信する。
【０１４９】
認証局６０１は、署名生成端末ｉから識別情報ＩＤi及び公開鍵ｋiを受け取り、必要に応じて署名生成端末ｉが過去に不正な処理を行った端末であるかなどの調査を行った後、識別情報ＩＤi及び公開鍵ｋiを、例えば図６に示すような表として、保存する。
【０１５０】
（署名生成手順）
署名生成端末ｉにユーザから署名対象の文書Ｍが入力される。
【０１５１】
このとき、署名生成端末ｉは、必要に応じて認証局６０１に問い合わせを行って、ネットワーク６００経由で他の署名生成端末の公開鍵ｋj（ｊは1からＬのうちｉ以外のインデックスのいずれかをあらわす）を複数入手する。他の署名生成端末の公開鍵が署名生成端末ｉに保存されている場合には、上記の問い合わせを行う必要はない。
【０１５２】
その後、署名対象の文書Ｍ、他の署名生成端末の公開鍵、署名生成端末ｉが内部に保存する秘密鍵ｓi及び共通パラメータ、署名生成端末ｉが内部で生成する乱数成分を用いて第１又は第２の構成例の「署名生成手段」に基づいて署名生成を行い、（Ｍ，Ｓ，ｙ，ｂ，ｃ1，ｄ1，…，ｃL，ｄL，ｋ1，…，ｋL）を、署名付き文書として、ネットワーク６００上に公開する。
【０１５３】
なお、署名付き文書に含まれる公開鍵ｋ1，…，ｋLの代わりに、対応する署名生成端末の識別情報ＩＤ1，…，ＩＤLを添付することも可能である。あるいは、公開鍵と識別情報の両方を付加してもよい。
【０１５４】
（署名検証手順）
署名検証端末６０３は、ネットワーク６００を通して署名付き文書（Ｍ，Ｓ，ｙ，ｂ，ｃ1，ｄ1，…，ｃL，ｄL，ｋ1，…，ｋL）を入手する。
【０１５５】
署名検証端末６０３は、認証極６０１に問い合わせを行い、公開鍵ｋ1，…，ｋLに対応する署名生成端末の識別情報ＩＤ1，…，ＩＤLを入手する。あるいは、署名付き文書に公開鍵ｋ1，…，ｋLの代わりに、識別情報ＩＤ1，…，ＩＤLが付加されている場合には、認証極６０１に問い合わせを行い識別情報ＩＤ1，…，ＩＤLに対応する署名生成端末の公開鍵ｋ1，…，ｋLを入手する。
【０１５６】
次に、署名検証端末６０３は、第１又は第２の構成例の「署名検証手段」に基づいて署名付き文書の正当性を検証する。検査に合格の場合には、署名付き文書が識別情報ＩＤ1，…，ＩＤLに対応するＬ個の署名生成端末のうちのいずれかにより生成されたとして署名を受理する。検査に不合格の場合には、署名を棄却する。
【０１５７】
以上の署名検証処理は、署名生成端末との通信を必要とせず、また、署名検証処理に合格する場合においても、いずれの署名生成端末が署名を生成したかの特定は困難である。
【０１５８】
（確認及び否認プロトコル）
署名検証端末６０３がある署名生成端末（署名生成端末ｉ）が署名付き文書（Ｍ，Ｓ，ｙ，ｂ，ｃ1，ｄ1，…，ｃL，ｄL，ｋ1，…，ｋL）を生成したか否かを確認する方法について説明する。
【０１５９】
署名検証端末６０３は、署名生成端末ｉに向けて確認及び否認プロトコルの実行依頼と署名付き文書のうち（Ｍ，Ｓ）を送信する。
【０１６０】
署名生成端末ｉは第１又は第２の構成例の「確認及び否認プロトコル」に基づいて、（Ｍ，Ｓ）が自らの秘密鍵に基づいて生成された署名である場合には、確認プロトコルを、そうでない場合には、否認プロトコルを、署名検証装置６０３との間で実行する。
【０１６１】
なお、公開鍵は必要に応じて取得できればよく、認証極を用いない構成も可能である。
【０１６２】
なお、以上の各機能は、ハードウェアとしても実現可能であるし、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。  
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０１６３】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１６４】
【図１】本発明の一実施形態に係るデジタル署名情報生成装置の構成例を示す図
【図２】同実施形態に係る署名生成処理手順の一例を示すフローチャート
【図３】同実施形態に係る署名検証装置の構成例を示す図
【図４】同実施形態に係る署名検証処理手順の一例を示すフローチャート
【図５】同実施形態に係るデジタル署名システムの構成例を示す図
【図６】同実施形態に係る認証極により保存及び公開される識別情報及び公開鍵のリストの構成例を示す図
【図７】否認不可署名の鍵の生成手順を示すフローチャート
【図８】否認不可署名の生成手順を示すフローチャート
【図９】検証装置（署名検証装置）における否認不可署名の検証手順を示すフローチャート
【図１０】署名装置（デジタル署名情報生成装置）における否認不可署名の検証手順を示すフローチャート
【図１１】検証装置（署名検証装置）における否認不可署名の確認手順を示すフローチャート
【図１２】署名装置（デジタル署名情報生成装置）における否認不可署名の確認手順を示すフローチャート
【図１３】検証装置（署名検証装置）における否認不可署名の否認手順を示すフローチャート
【図１４】署名装置（デジタル署名情報生成装置）における否認不可署名の否認手順を示すフローチャート
【符号の説明】
【０１６５】
２０１，４０１…演算器、２０２…乱数生成器、２０３…乱数メモリ、２０４…秘密鍵メモリ、２０５…署名生成部、２０６，４０６…入出力部、２０７〜２０９，４０７〜４０９…ランダム関数演算部、２１１，４１１…制御部、２１２，４１２…メモリ、６００…ネットワーク、６０１…認証局、６０２1〜６０２Ｌ…署名生成端末、６０３…署名検証端末
【図１】
2006203660.tif 000003
【図２】
2006203660.tif 000004
【図３】
2006203660.tif 000005
【図４】
2006203660.tif 000006
【図５】
2006203660.tif 000007
【図６】
2006203660.tif 000008
【図７】
2006203660.tif 000009
【図８】
2006203660.tif 000010
【図９】
2006203660.tif 000011
【図１０】
2006203660.tif 000012
【図１１】
2006203660.tif 000013
【図１２】
2006203660.tif 000014
【図１３】
2006203660.tif 000015
【図１４】
2006203660.tif 000016