デジタル署名システム、装置及びプログラム
【課題】 リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限する。
【解決手段】 署名者としてのユーザに固有の秘密鍵情報及び署名者が選択した他の複数のユーザの公開鍵情報及び署名者が指名した確認者の公開鍵情報を用いて、任意のデジタル情報に対するリング署名を生成するデジタル署名装置（１０）と、リング署名を検証する際に、確認者の公開鍵情報に対応する秘密鍵情報に基づいて、当該リング署名を検証する確認者用署名検証装置（２０）と、リング署名を検証する際に、確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置（３０）とを備える。
【解決手段】 署名者としてのユーザに固有の秘密鍵情報及び署名者が選択した他の複数のユーザの公開鍵情報及び署名者が指名した確認者の公開鍵情報を用いて、任意のデジタル情報に対するリング署名を生成するデジタル署名装置（１０）と、リング署名を検証する際に、確認者の公開鍵情報に対応する秘密鍵情報に基づいて、当該リング署名を検証する確認者用署名検証装置（２０）と、リング署名を検証する際に、確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置（３０）とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル署名方式の一種のリング署名方式を用いるデジタル署名システム、装置及びプログラムに係り、特に、署名者の匿名性と、検証者の制限とを両立し得るデジタル署名システム、装置及びプログラムに関する。
【背景技術】
【０００２】
デジタル署名方式として、従来からリング署名方式が知られている(例えば、非特許文献１及び非特許文献２参照)。
【０００３】
リング署名方式とは、以下の性質をもつデジタル署名方式である。
第１は、署名者がメンバを任意にＮ人選んで生成したグループの代表として署名を生成することが可能であるという性質である。
【０００４】
第２は、Ｎ人に含まれているユーザを含めた任意の検証者はＮ人のうちの１人が署名した事実は検証可能だが、どの１人が署名者であるかを特定するのが困難な性質である。
【０００５】
もう一つデジタル署名として、従来から指名確認者署名方式が知られている(例えば、非特許文献３参照)。
【０００６】
指名確認者署名方式とは、以下の性質を持つデジタル署名方式である。
【０００７】
第１は、署名者が任意に選んだユーザを確認者として指名し、その確認者は、署名の正当性を検証でき、それ以外のユーザは署名の正当性を検証できないという性質である。
【０００８】
第２は、署名者に確認者として指名されていないユーザは一人では署名の正当性を検証できないが、署名者に確認者として指名されているユーザと指名されていないユーザが対話的に証明をすることによって、指名されていないユーザも署名の正当性を確認することができるという性質である。
【０００９】
以上のようなリング署名方式及び指名確認者署名に関連する他の先行技術文献情報としては、後で引用する非特許文献４−８などがある。
【非特許文献１】Ｒ．リベスト、Ａ．シャミア、Ｙ．タウマン（R.Rivest, A.Shamir, Y.Tauman）著、「ハウ・トゥ・リーク・ア・シークレット（How to Leak a Secret）」、アジアクリプト２００１（ASIACRYPT2001）、ＬＮＣＳ ２２４８、シュプリンガー・フェアラーク（Springer-Verlag）、ｐｐ.５５２−５６５、２００１年
【非特許文献２】大久保、阿部、鈴木、辻井著、「証明長が短い １−ｏｕｔ−ｏｆ−ｎ証明」、暗号と情報セキュリティシンポジウム（ＳＣＩＳ２００２）、ｐｐ.１８９−１９３、２００２年
【非特許文献３】Ｄ．チャウム（D.Chaum）著、「デザイネイティッド・コンファーマー・シグニチャーズ（Designated Confirmer Signatures）」、ユーロクリプト'９４（EUROCRYPT'94）、ＬＮＣＳ ９５０、シュプリンガー・フェアラーク（Springer-Verlag）、ｐｐ.８６−９１、１９９４年
【非特許文献４】Ｍ．ミヘルス、Ｍ．スタドラー（M. Michels, M. Stadler）著、「ジェネリック・コンストラクションズ・フォア・セキュア・アンド・エフィシェント・コンファーマー・シグネチャー・スキームズ（Generic Constructions for Secure and Efficient Confirmer Signature Schemes）」、ユーロクリプト'９８（EUROCRYPT'98）、ＬＮＣＳ １４０３、ｐｐ.４０６−４２１、１９９８年
【非特許文献５】Ｍ．阿部、Ｍ．大久保、Ｋ．鈴木（M. Abe, M. Ohkubo, K. Suzuki）著、「１−アウト−オブ−ｎ・シグネチャーズ・フローム・ア・バラエティ・オブ・キーズ（1-out-of-n Signatures from a Variety of Keys）」、アジアクリプト２００２（ASIACRYPT2002）、ＬＮＣＳ ２５０１、ｐｐ.４１５−４３２、２００２年
【非特許文献６】Ａ．フジオカ、Ｔ．オカモト、Ｋ．オオタ（A. Fujioka, T. Okamoto, K. Ohta）著、「インタラクティブ・バイ−プルーフ・システムズ・アンド・アンデナイアブル・シグネチャー・スキームズ（Interactive Bi-Proof Systems and Undeniable Signature Schemes）」、ユーロクリプト'９１（EUROCRYPT'91）、ＬＮＣＳ ５４７、ｐｐ.２４３−２５６、１９９２年
【非特許文献７】Ｍ．ミヘルス、Ｍ．スタドラー（M. Michels, M. Stadler）著、「エフィシェント・コンバーチブル・アンデナイアブル・シグネチャー（エクステンデッド・アブストラクト）（Efficient Convertible Undeniable Signature (Extended Abstract）」、ピーアールオーシー・フォース・インターナショナル・ワークショップ・オン・セレクテッド・エリアズ・イン・クリプトグラフィー−エスエイシー'９７（Proc. 4th International Workshop on selected Areas in Cryptography - SAC'97）、ｐｐ.２３１−２４４、１９９７年
【非特許文献８】米沢、花岡、今井 著、「検証者が多数の場合に適した検証者指定署名」、暗号と情報セキュリティシンポジウム−ＳＣＩＳ２００３、ｐｐ．６７−７０、２００３年
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら以上のようなデジタル署名システムでは、リング署名及び指名確認者署名のそれぞれについて以下のような不都合がある。
【００１１】
リング署名は、公開されている情報を用いると、誰でも署名の正当性を検証できる。しかし、誰でも検証できるということは、署名者の意図しない範囲のメンバにも正当性を納得させてしまうことができて、署名の存在を悪用されてしまう可能性がある。
【００１２】
例えば、リング署名を用いて社内の不正告発システムを構築したとする。このシステムを導入した企業を仮にＡ社とする。Ａ社は告発システムを、自浄効果を期待して導入した。
【００１３】
Ａ社のある社員はこのシステムを用いて社内の不正を告発するリング署名付き文書を作成したとする。この署名は本来ならば社内にとどめて、内容を検討するために利用するものである。しかしながら、悪意や手違いから新聞社や放送メディアなどの第三者に渡ってしまい、署名が誰にでも検証が可能なことから署名の正当性を検証され、対処する前にＡ社の不正だけが取り上げられてしまう場合が考えられる。この場合、自浄効果の意味がなくなってしまう。
【００１４】
一方、指名確認者署名においては、署名者が一人しか存在しないので、確認時、検証時には、その人が署名したか否かという正当性を検証することになるため、匿名性がない。
【００１５】
まとめると、リング署名には、署名者が匿名性を持つ反面、署名の検証者が制限されないという不都合がある。指名確認者署名には、署名を検証可能な者を確認者又は確認者が対話する検証者に制限できる反面、署名者の匿名性が無いという不都合がある。
【００１６】
本発明は上記実情を考慮してなされたもので、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限し得るデジタル署名システム、装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
第１の発明は、署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置と、前記リング署名を検証する際に、前記確認者の公開鍵情報に対応する秘密鍵情報（ｘC）に基づいて、当該リング署名を検証する確認者用署名検証装置と、前記リング署名を検証する際に、前記確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置とを備えたデジタル署名システムである。
【００１８】
（作用）
第１の発明は、署名者としてのユーザに固有の秘密鍵情報（ｘi）及び署名者が選択した他の複数のユーザの公開鍵情報（ｙj）及び署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成する。
【００１９】
これにより、署名者は、リング署名に含めたい他のユーザとの事前やりとり無しで他のユーザの公開鍵情報を任意に選ぶことができ、リング署名からは各ユーザのうちの誰が署名したかが検証者には全くわからないという特徴を持ったリング署名を生成できる。
【００２０】
これに加え、署名者が署名時に指名した特定の確認者だけが検証でき、それ以外の検証者は一人では署名の正当性を検証できないが、先述の特定の確認者と対話を行うことで特定の確認者以外の検証者も署名の正当性を知ることができる署名を生成できる。
【００２１】
従って、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限することができる。
【００２２】
なお、第１の発明は、各装置からなる全体構成を「システム」として表現したが、これに限らず、全体構成又は各装置を「装置」、「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」として表現してもよい。
【発明の効果】
【００２３】
以上説明したように本発明によれば、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限できる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の一実施形態につき図面を参照して説明する。始めに、従来方式を改良した指名確認者署名方式を示し、続いて、この改良した指名確認者署名方式を前提とした本発明方式の概要を述べる。しかる後、本発明方式の一実施形態について説明する。
【００２５】
（１． 改良した指名確認者署名方式）
ここでは、従来の非特許文献４方式を本発明者により改良した指名確認者署名方式を示す。一般に、指名確認者署名は、署名者（Signer）、確認者（Confirmer）、一般的な検証者（Verifier）の三者で成立している。確認者は、署名者と対話、もしくは確認者のみで署名を検証できる。検証者は、確認者と対話することによってのみ、署名の検証が可能となる。
【００２６】
（１．１ 準備）
符号Ｓを署名者とする。符号Ｃを、署名者に指定された確認者とする。符号Ｖを、権限の無い一般の検証者とする。
【００２７】
ここで、ｑ｜ｐ−１を満たす大きな素数をｐ，ｑとする。位数がｑであるｐの部分群の生成元をｇとする。署名者Ｓは、ｘS∈Ｚｑを秘密鍵、ｙS＝ｇ{ｘ_S} ｍｏｄ ｐを公開鍵として生成し、公開鍵ｙSを公開する。さらに、確認者の秘密鍵をｘC∈Ｚｑ、公開鍵をｙC＝ｇ{ｘ_C}とする。また、符号ｈ，ｈｑを衝突困難性ハッシュ関数とする。
【００２８】
（１．２ 署名生成）
署名者Ｓは以下を計算する。
【数１】
【００２９】
但し、α，ｋ∈Ｚｑとし、σ（ｍ）＝（Ｔ，ｓ，ｄ1，ｄ2）をｍに対する署名として出力する。
【００３０】
（１．３ 署名検証（確認者Ｃによる））
確認者Ｃは、以下を検証する。
【数２】
【００３１】
確認者Ｃは、２つの検証結果が合格であれば署名を受理し、そうでなければ署名を棄却する。
【００３２】
（１．４ 署名検証（検証者Ｖによる））
ステップ１：
検証者Ｖは、署名情報が次式を満たすかを確認者Ｃとの対話証明により間接的に検証する。補足すると、次の対数の検証式は直接には計算されず、成り立つことが対話証明により確認される。
【数３】
【００３３】
検証者Ｖは、２つの検証結果が合格であれば署名を受理し、そうでなければ署名を棄却する。
【００３４】
（２． 本発明方式の概要）
図７は本発明方式の概略を示す模式図である。本発明方式は、上述した「改良した指名確認者署名方式」を連鎖的に行なう形式となっている。従来の非特許文献４の方式は、確認者Ｃは署名者Ｓと対話せずに署名検証が可能であるため、署名者の匿名性を保証できるリング署名の性質は損なわれない。また、非特許文献４の方式をそのままリング署名に適用すると、確認者Ｃによるメッセージｍに対するコミットメントの検証や、確認者Ｃの検証者Ｖに対するメッセージｍについてのコミットメントの知識証明（Interactive bi-proof）の計算量がグループサイズｎに比例してしまう。そこで、本発明方式では、コミットメントの検証が１回で済むように効率を改善している。
【００３５】
（２．１ 準備）
符号Ｇをグループメンバの集合とする。Ｕj（ｊ＝１，…，ｎ）をメンバ集合Ｇに属するメンバ、Ｕiを署名者とする。メンバＵjはｘj∈Ｚｑを秘密鍵、ｙj＝ｇ{ｘ_j} ｍｏｄ ｐとし、公開鍵ｙjを公開する。その他のエンティティとパラメータは、前述した指名確認者署名方式と同様とする。
【００３６】
（２．２ リング署名生成）
署名者Ｕiは、確認者Ｃの公開鍵に関連付けたメッセージｍに対するコミットメント（ｄ1，ｄ2）及びコミットメントに対するリング署名（ｄ1，ｄ2）（ｃ1，ｓ1，…，ｓn）を以下のように生成する。
【００３７】
ステップ１：
署名者Ｕiは、以下のＴi，ｄ1，ｄ2，ｃi+1を求める。但し、α，ｋ∈Ｚｑとする。
【数４】
【００３８】
ステップ３：
署名者Ｕiは、ｃiについて、以下のｓiを計算する。
【００３９】
ｓi＝α−ｘiｃi mod ｑ
ステップ４：
署名者Ｕiは、以上の計算結果からσ（ｍ）＝（ｃ1，ｓ1，…，ｓn，ｄ1，ｄ2）をメッセージｍに対する署名として出力する。
【００４０】
（２．３ リング署名検証（確認者Ｃによる））
確認者Ｃは、コミットメントの正当性を下式により検証する。
【数５】
【００４１】
ここで、確認者Ｃは、ｃ1＝ｃn+1となることを検証することにより、コミットメントに対するリング署名の正当性を検証する。確認者Ｃは、全ての検証結果が合格であれば署名を受理し、そうでなければ署名を棄却する。
【００４２】
（２．４ リング署名検証（検証者Ｖによる））
ステップ１：
検証者Ｖは、まず、ｊ＝１，…，ｎまで以下を繰り返す。
【数６】
【００４３】
検証者Ｖは、ｃ1＝ｃn+1となることを検査することにより、コミットメントに対するリング署名の正当性を検証する。
【００４４】
ステップ２：
また、検証者Ｖは、署名情報が次式を満たすかを確認者Ｃとの対話証明により検査し、メッセージに対するコミットコミットメントの正当性を検証する。検証の手順は、前述した「改良した指名確認者署名方式」と同様である。
【数７】
【００４５】
（３． 安全性）
ここでは、安全な指名確認者リング署名が満たす条件を示し、本発明方式がこれらの条件（i）〜（vi）を満たしていることを証明する。
【００４６】
（i）署名の完全性（Completeness of Signature）
署名者が正しい動作をした場合には、確認者が検証可能な署名を構成できること。
【００４７】
（ii）署名の偽造不可能性（Unforgeability of Signature）
リング署名を構成するグループのメンバ以外が署名を偽造できないこと。
【００４８】
（iii）署名者の曖昧性（Signer Ambiguity）
署名の情報から署名者の情報が漏れないこと。
【００４９】
（iv）署名の不可視性（Invisibility of Signature）
確認者Ｃ、又は確認者Ｃと対話証明を行なう検証者Ｖは、署名の正当性を検証できるが、それ以外のユーザは署名の正当性を検証できないこと。
【００５０】
（ｖ）検証の一貫性（Consistency of Verification）
確認者Ｃや検証者Ｖが正しい動作をした場合は、正しく検証ができること。
【００５１】
（vi）検証の非伝達性（Non-transferability of Verification）
確認者Ｃの秘密鍵に関する情報が対話証明において、検証者Ｖにほとんど漏れないこと。
【００５２】
本発明方式は、以上の要求条件に対して以下の定理が成り立つ。
【００５３】
（定理１：署名の完全性）
正しい秘密鍵をもつ署名者Ｕiがアルゴリズムに従い生成したリング署名は、確認者Ｃの署名検証に常に成功する。
証明：プロトコルから明らかである。
【００５４】
（定理２：署名の偽造不可能性）
本発明方式は、ランダムオラクルモデルと離散対数問題の困難性を仮定すると、グループメンバ以外の任意の敵が署名の偽造に成功する確率は無視できるほど小さい。
【００５５】
証明（Sketch）:ｄ，ｄがＤＤＨ仮定の下に不可視(invisible)であることは非特許文献４で証明されている。このとき、仮に本発明方式が偽造可能であると仮定すると、非特許文献５により提案されたリング署名を偽造可能な敵を構成することができる。
【００５６】
（定理３：署名者の曖昧性）
任意のメッセージに対するリング署名から署名者を特定できる確率は１／ｎである。
【００５７】
証明（Sketch）：ｓiを除くｓjはＺｑから一様にランダムに選ばれ、ｓiはαがＺｑ上から一様にランダムに選ばれるので、ｓiもＺｑ上に一様に分布する。また、ｄ1，ｄ2はメンバ公開鍵には関係しない。従って、グループメンバと（ｍ）を固定すると、（ｓ1，…，ｓn，ｄ1，ｄ2）は、署名者が誰であるかに関わらず、同様にｎｑのバリエーションをもつ。残りのｃ1は、グループメンバのリスト、（ｍ）及び（ｓ1，…，ｓn，ｄ1，ｄ2）より一意に決定できる。よって、署名者を特定できる確率は１／ｎである。
【００５８】
（定理４：署名の不可視性）
任意の敵に対して正しい署名とシミュレータの出力する署名を優位な確率で区別することが不可能なシミュレータを構成できる。
【００５９】
証明（Sketch）：メッセージｍに対するコミットメントは、不可視（invisible）であることが証明されている（非特許文献４参照）。また、本発明方式の署名偽造不可能性から、本発明方式の不可視性（invisibility）は、メッセージｍに対するコミットメントと等価であることを示すことが可能であり、よって定理４が成り立つ。
【００６０】
（定理５：検証の一貫性）
確認者Ｃと検証者Ｖの間で行われるリング署名検証プロトコルにおいて、正しいリング署名が検証に失敗する確率及び不正なリング署名が検証に成功する確率は任意の確認者Ｃに対して無視できる。
【００６１】
（定理６：検証の非伝達性）
確認者Ｃと検証者Ｖの間で行われるリング署名検証プロトコルは、最小知識対話証明（minimum knowledge bi-proof）である（非特許文献６参照）。
【００６２】
証明（定理５，６）：前述した「改良した指名確認者署名方式」は、非特許文献７に記載の対話証明システム（bi-proof system）を用いている。対話証明システムの完全性（completeness）、安定性（Soundness）、零知識証明性（Zero-Knowledgeness）は、非特許文献７によって証明されており、この性質から一貫性、非伝達性は明らかである。これは本発明方式でも成り立つ。
【００６３】
（効率の比較）
図８は従来方式と本発明方式とを比較して示す図である。具体的には従来方式と本発明方式とに関し、署名長、確認者Ｃによるコミットメントに対する検証コストと、リング署名の検証コスト、確認者Ｃと検証者Ｖ間での対話証明（bi-proof）とリング署名の検証コストに関しての比較結果を示している。｜ｐ｜は素数ｐのビット長を表している。
【００６４】
ここでは、リング署名方式（非特許文献２）と、非特許文献２及び非特許文献４を組み合わせただけのナイーブ（素朴）なプロトコルと、本発明方式とを比較した。
【００６５】
ナイーブなプロトコルは、本発明方式と比較して署名長がおよそ３倍となり、コミットメントの検証と対話証明の検証コストがＯ（ｎ）となる。これは、リング署名生成フェーズで、公開鍵ｙCに関するコミットメントをｎ回生成するためである。特に、確認者Ｃと検証者Ｖ間での対話証明が対話的に行われるため、このプロトコルの効率悪化は影響が大きい。本発明方式では、ｎ個のコミットメントの計算を一回にして検証可能となるように改良しているため、これらの検証コストがＯ（１）に抑制されている。
すなわち、本発明方式は、非特許文献４の方式をそのままリング署名に適用した場合に比べ、知識証明に関する効率を向上させることができる。
【００６６】
（応用）
ここでは、本発明方式の応用について述べる。非特許文献８では、複数の確認者Ｃを用いても、署名長が確認者Ｃの数に依存しない指名確認者署名方式が提案されている。これは、信頼できる機関（ＴＡ）を仮定し、この機関ＴＡが確認者Ｃの秘密鍵を多数使用放送暗号化スキーム（Multiple use broadcast encryption scheme）の技術を用いて配布することにより、確認者Ｃの集合が同じ鍵を共有できるようにしたものである。同様にこの技術を本発明方式に適用することにより、正しく秘密鍵を入手できる確認者Ｃは、誰でも署名を検証することができる。確認者Ｃと検証者Ｖ間の検証が頻繁に発生する場合には確認者の負荷を分散できるため、有用である。
以上が本発明方式の概要である。続いて、本発明の一実施形態について説明する。
【００６７】
（一実施形態）
図１は本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図であり、図２は図１における情報の流れを示す模式図である。このシステムは、複数のユーザ端末１０及び各１台のユーザ端末２０，３０を備えている。各ユーザ端末１０，２０，３０は、コンピュータにより実現される場合、それぞれ各端末１０，２０，３０の機能を実現するためのプログラムが予め記憶媒体又はネットワークから各端末のコンピュータにインストールされて実現される。
【００６８】
ユーザ端末は、ユーザ端末１０，２０，３０に分類される。
複数のユーザ端末１０は、署名者Ｓとしてのユーザｕのユーザ端末１０と、リング署名に用いられるグループメンバとしての各ユーザｋ，…のユーザ端末１０，…とを含む。
【００６９】
各ユーザ端末１０は、秘密鍵記憶装置１１及び署名生成部１２を備えている。
【００７０】
ここで、秘密鍵記憶装置１１は、署名者としてのユーザに固有の秘密鍵情報が記憶されるメモリであり、署名生成部１２から読出可能となっている。
【００７１】
署名生成部１２は、署名者としてのユーザに固有の秘密鍵情報（ｘi）及び署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するものであり、具体的には図３及び図４に示すステップＳＴ１２〜ＳＴ１７の処理を実行する機能をもっている。
【００７２】
これらの機能としては、例えば、デジタル署名装置としてのユーザ端末１０のコンピュータを、適切な第１乱数情報（α）に基づいて、第１リング要素関連情報（Ｔi）を生成する機能と、デジタル情報（ｍ）、適切な第２乱数情報（ｋ）、及びハッシュ関数に基づいて、第１コミットメント情報（ｄ1）を生成する機能と、確認者の公開鍵情報（ｙC）、適切な第２乱数情報（ｋ）に基づいて、第２コミットメント情報（ｄ2）を生成する機能と、第１及び第２コミットメント情報（ｄ1，ｄ2）、第１リング要素関連情報（Ｔｉ）及びハッシュ関数に基づいて、リング要素情報（ｃi+1、但し i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする）を生成する機能と、他のユーザに関する適切なメンバ乱数情報（ｓj）をランダムに生成する機能と、他のユーザの公開鍵情報（ｙj）、メンバ乱数情報（ｓｊ）、及びリング要素情報に基づいて、第２リング要素関連情報（Ｔｊ）を生成する機能と、第１及び第２コミットメント情報（ｄ1，ｄ2）、第２リング要素関連情報（Ｔｊ）及びハッシュ関数に基づいて、リング要素情報（ｃj+1、但し j = n の場合、ｃj+1＝ｃ{(j+1) mod n}）を生成する機能と、署名者の秘密鍵情報（ｘi）及び署名者に対応するリング要素情報（ｃi）に基づいて、署名者関連情報（ｓi）を生成する機能と、１番目のリング要素情報（ｃ1）、署名者関連情報（ｓi）、メンバ乱数情報（ｓj＝ｓ1，…，ｓi-1，ｓi+1，…，ｓn）、第１及び第２コミットメント情報（ｄ1，ｄ2）を含むリング署名｛σ（ｍ）＝（ｃ1，ｓ1，…，ｓn，ｄ1，ｄ2）｝を生成する機能とが含まれる。
【００７３】
ユーザ端末２０は、指定された確認者Ｃとしてのユーザcに操作されるものであり、秘密鍵記憶装置２１、確認者用署名検証部２２及び対話証明部２３を備えている。
【００７４】
秘密鍵記憶装置２１は、確認者としてのユーザに固有の秘密鍵情報が記憶されるメモリであり、確認者用署名検証部２２及び対話証明部２３から読出可能となっている。
【００７５】
確認者用署名検証部２２は、リング署名を検証する際に、確認者の公開鍵情報（ｙC）、この公開鍵情報に対応する秘密鍵情報（ｘC）及びデジタル情報（ｍ）に基づいて、当該リング署名を検証する第１検証機能と、リング署名を検証する際に、署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第２検証機能と、第１及び第２検証機能による検証に合格したとき、リング署名を受理するリング署名受理機能とを有し、具体的には図３及び図５のステップＳＴ２０〜ＳＴ２５に示す処理を実行する機能をもっている。
【００７６】
対話証明部２３は、検証者用の対話証明部３２による対話証明の際に動作するものであり、図６のステップＳＴ３３，ＳＴ３４，ＳＴ３６〜ＳＴ３８に示す処理を実行する機能をもっている。
【００７７】
ユーザ端末３０は、検証者Ｖとしてのユーザｖに操作されるものであり、検証者用署名検証部３１及び対話証明部３２を備えている。
【００７８】
検証者用署名検証部３１は、リング署名を検証する際に、署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第１検証機能と、この第１検証機能及び対話証明部３２の第２検証機能による検証に合格したとき、リング署名を受理するリング署名受理機能とを有し、具体的には図６のステップＳＴ３１，ＳＴ４０〜ＳＴ４２に示す処理を実行する機能をもっている。
【００７９】
対話証明部３２は、リング署名を検証する際に、確認者の公開鍵情報（ｙC）に基づき、確認者のユーザ端末２０との間の対話証明を介して、当該リング署名を検証する第２検証機能を有し、具体的には図６のステップＳＴ３２，ＳＴ３５，ＳＴ３９に示す処理を実行する機能をもっている。
【００８０】
また前提条件として、公開鍵基盤などにより、公開情報を安全に公開するための手段、例えば公開掲示板サーバ４０などが存在するとする。
【００８１】
公開掲示板サーバ４０は、公開される情報を記憶する公開情報記憶装置４１を有する。この公開掲示板サーバ４０によって実現される情報公開(掲載)手段を公開情報掲示板と呼ぶ。公開情報掲示板は全てのユーザがアクセスでき、かつ改ざんなどの不正が行われないように適切に管理されているとする。また、全てのユーザはインターネットなどのネットワーク５０に接続されているものとする。特に匿名性を必要とする場合は匿名ネットワークに接続されていてもよいが、その限りではない。
【００８２】
次に、以上のように構成されたデジタル署名システムの動作を図３のシーケンス図及び図４乃至図６の各フローチャートを用いて述べる。なお、本実施形態では、例えばべき乗を ^ で表し、下付添字を _ で表し、文字の真上の波形符号を \tilde で表す等というように１行で済む数式表現を用いている。この数式表現は、前述した本発明方式の概要説明におけるイメージ読込を要する数式表現とは異なるが、数式の内容は対応している。
【００８３】
（準備）：
本実施形態では、前提条件として、ユーザの公開鍵や公開情報は予め公開掲示板サーバ４０により公開されているものとする。公開の方法としては例えば公開鍵基盤などがあるが、ここでは限定しない。
【００８４】
まず、公開掲示板サーバ４０は、素数位数qの巡回群Gとその生成元gを選び公開する。ここでは、一例として、q|p-1 を満たす十分大きな素数p,qを選び、位数がqとなるZp*の部分群をGとし、p,q,gを公開するとする。
【００８５】
さらに、公開掲示板サーバ４０は、衝突困難性ハッシュ関数h:{0,1}^*→{0,1}^q，
h_q:{0,1}^*→{0,1}^qを任意に選び公開する。
【００８６】
また前提条件に従い各ユーザ端末１０，２０は、それぞれユーザu,k,cの操作により、x_u，x_k，x_c ∈ Zqをランダムに選び、以下を計算する。なお、記号^はべき乗を表す。
y_u=g^{x_u},
y_k=g^{x_k},
y_c=g^{x_c}
そして、各ユーザu,k,cのユーザ端末１０，２０は、y_u，y_k，y_cを公開鍵として公開する。
ステップＳＴ１０：リング署名の生成（図３、図４）
ユーザuとなるべきユーザは複数いると仮定する。その中でも特に署名者となるユーザuをユーザu_iとする。ユーザu_iは署名時に任意のグループを作成する。このグループに含まれるユーザuをユーザu_jとする。(j=1,...,n，j≠i)
ユーザu_iのユーザ端末１０は、署名生成部１１において、ユーザ秘密鍵x_i、メッセージm、及び公開情報掲示板14から取得可能な公開情報ＰＵＢＩ（ユーザu_jの公開鍵を含む）を入力として（ＳＴ１１）、以下のステップＳＴ１２〜ＳＴ１７の手順によりmに対するリング署名σを生成し、(m,σ)を出力する。
【００８７】
ステップＳＴ１２：α,k ∈Z_qをランダムに選ぶ。
【００８８】
ステップＳＴ１３：衝突困難性ハッシュ関数hとh_qを用いて以下の値を計算する。
T_i = g^α mod p,
d_1 = g^{k+h_q(m)} mod p,
d_2 = {y_C}^k mod p,
c_{i+1} = h(d_1‖ d_2 ‖ T_i)
但し、i = n の場合には c_{i+1} = c_{(i+1)mod n}とする。また、“‖”はデータの連結を表す。
【００８９】
ステップＳＴ１４： j=i+1,...,n,1,..., i-1について、s_j∈Z_qをランダムに選ぶ。
【００９０】
ステップＳＴ１５：j=i+1,...,n,1,..., i-1について、以下の値を計算する。
T_j = g^{s_j}{y_j}^{c_j} mod p,
c_{(j+1)mod n} = h(d_1 ‖ d_2 ‖ T_j)
但し、j = n の場合には c_{j+1} = c_{(j+1)mod n}とする。
【００９１】
ステップＳＴ１６：s_i = α - {x_i}{c_i} mod qを計算する。
【００９２】
ステップＳＴ１７：j=1,...,nについて、以下の値をリング署名σとして確認者ユーザｃのユーザ端末２０、または検証者ユーザｖのユーザ端末３０に送信する。
σ(m) = (c_1,s_j, d_1 ,d_2)
ステップＳＴ２０：リング署名の確認者による検証（図３、図５）
署名確認者であるユーザcのユーザ端末２０は、署名検証部２２において、メッセージmとmに対するリング署名σのペア(m,σ)及び公開掲示板サーバ４０から取得可能な公開情報ＰＵＢＩを用いて、以下のステップＳＴ２１〜ＳＴ２５の手順でリング署名の正当性とメッセージmに対するコミットメントの正当性を検証する。
【００９３】
ステップＳＴ２１：メッセージm及びリング署名σから、公開情報である衝突困難性ハッシュ関数h_q及び確認者の秘密鍵x_Cを用い、以下の式が成り立つことを検証する。
d_1^{x_C}/d_2 = {y_C}^{{h_q}(m)}
ステップＳＴ２２：j = 1, ..., nについて、公開情報である衝突困難性ハッシュ関数hを用いて以下の値を計算する。
T_j = g^{s_j}{y_j}^{c_j} mod p,
c_{j+1} = h(d_1 ‖ d_2 ‖ T_j)
ここで、c_1=c_{n+1}が成り立つことを検証する。
【００９４】
ステップＳＴ２３〜ＳＴ２５：上記ＳＴ２１，２２が共に成り立つ場合は検証合格（ＯＫを出力してリング署名σ（ｍ）を受理し、成り立たない場合は検証不合格（ＮＧ）を出力してリング署名σ（ｍ）を棄却する。
【００９５】
ステップＳＴ３０：リング署名の検証者による検証（図３、図６）
署名検証者であるユーザvのユーザ端末３０は、メッセージmとmに対するリング署名σのペア(m,σ)と公開掲示板サーバ４０から取得可能な公開情報ＰＵＢＩとを予め記憶装置（図示せず）に記憶しておく。そして、ユーザ端末３０は、記憶装置内のリング署名σのペア(m,σ)及び公開情報ＰＵＢＩを用いて、署名検証部３１においてコミットメントに対するリング署名の正当性の検証と、対話証明部３２において確認者ユーザcのユーザ端末２０の対話証明部２３との対話的証明により、リング署名に含まれるメッセージmに対するコミットメントの正当性を検証する。
【００９６】
ステップＳＴ３１：検証者のユーザ端末３０は、j = 1, ... , nについて、メッセージm、リング署名σ及び衝突困難性ハッシュ関数hより以下の値を計算する。
T_j = g^{s_j}{y_j}^{c_j} mod p,
c_{j+1} = h(d_1 ‖ d_2 ‖ T_j)
c_1=c_{n+1}となることを検査することにより、コミットメントに対するリング署名の正当性を検証する。
【００９７】
ステップＳＴ３２：検証者のユーザ端末３０は、署名情報がlog_g (y_C) = log_{d_1}({d_2}{y_C}^{{h_q}(m)}であるかを、以下のＳＴ３３〜ＳＴ３９に示すように、確認者との対話証明により検証する。
【００９８】
始めに、検証者のユーザ端末３０は、u,v ∈ Z_qをランダムに選び、a = {g^u}{y_C}^vを計算して、aを確認者のユーザ端末２０に送る。
【００９９】
ステップＳＴ３３：確認者のユーザ端末３３は、t, \tilde t, w ∈ Z_qをランダムに選択する。
【０１００】
ステップＳＴ３４：確認者のユーザ端末３３は、
r_1 = g^t, r_2 = {d_1}^t,
{{\tilde r}_1} = g^{\tilde t},
{{\tilde r}_2} = {d_1}^{\tilde t}
を計算し、検証者にr_1,r_2,{{\tilde r}_1},{{\tilde r}_2}を送信する。
【０１０１】
ステップＳＴ３５：検証者のユーザ端末２０は、u,vを確認者のユーザ端末３０に送信することによりコミットメントaを開示する。
【０１０２】
ステップＳＴ３６〜ＳＴ３８：確認者のユーザ端末３０は、もしa ≠ {g^u}{{y_C}^v}ならば、プロトコルを中止し、そうでない場合は、
s = t -(v+w)x_P,
{\tilde s} = {\tilde t}-(v+w)t
を計算し、sと{\tilde s}を検証者に送信する。
【０１０３】
ステップＳＴ３９：検証者のユーザ端末３０は、最初に、
{g^s}{y_C}^{v+w} = r_1,
{g^{\tilde s}}{{r_1}^{v+w}} = {\tilde r}_1,
{d_1}^{\tilde s}{{r_2}^{v+w}} = {\tilde r}_2
であるかを確認した後、
d_1^{s}({d_2}{y_C}^{{h_q}(m)})^{v+w} = r_2
を検査する。これにより、log_g (y_C) =log_{d_1}({d_2}{y_C}^{{h_q}(m)})
であることを間接的に検証する。
【０１０４】
ステップＳＴ４０〜ＳＴ４２：検証者のユーザ端末３０は、ステップＳＴ３１のc_1=c_{n+1}と、ステップＳＴ３２〜ＳＴ３９の対話証明によるlog_g (y_C) =log_{d_1}({d_2}{y_C}^{{h_q}(m)})との二つの検証が成り立つ場合は検証合格（ＯＫ）を出力してリング署名σ（ｍ）を受理し、成り立たない場合は検証不合格（ＮＧ）を出力してリング署名σ（ｍ）を棄却する。
【０１０５】
ステップＳＴ２０及びＳＴ３０の検証で、Ｎ人のうちの誰かは確実に署名をしているという事実を確かめることはできるが、どのメンバが署名したかということはわからない。
【０１０６】
また、確認者は自分の秘密鍵ｘCを用いて直接署名の正当性を検証できるが、検証者は確認者と対話を行うことで検証に必要な秘密情報を知らないまま、署名の正当性を確認できる。
【０１０７】
上述したように本実施形態によれば、署名者としてのユーザに固有の秘密鍵情報（ｘi）及び署名者が選択した他の複数のユーザの公開鍵情報（ｙj）及び署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成する。
【０１０８】
これにより、署名者は、リング署名に含めたい他のユーザとの事前やりとり無しで他のユーザの公開鍵情報を任意に選ぶことができ、リング署名からは各ユーザのうちの誰が署名したかが検証者には全くわからないという特徴を持ったリング署名を生成できる。
【０１０９】
これに加え、署名者が署名時に指名した特定の確認者だけが検証でき、それ以外の検証者は一人では署名の正当性を検証できないが、先述の特定の確認者と対話を行うことで特定の確認者以外の検証者も署名の正当性を知ることができる署名を生成できる。
【０１１０】
従って、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限することができる。
【０１１１】
補足すると、リング署名の検証を署名者が指名した確認者が介在したときのみ行えるようにする。詳しくは、一般的な安全性の仮定に基づいた方式を用いたリング署名の署名情報を、メッセージmに対するコミットメントと、コミットメントに対するリング署名に分けることで、署名の正当性を確認者は検証できるが、検証者はメッセージmに対するコミットメントを確認者との対話証明を行うことで検証可能となる。これにより、署名の流通範囲を制限することができる。
【０１１２】
また、署名者装置としてのユーザ端末１０は、リング署名として、ユーザ秘密鍵ｘSについて零知識であることが証明可能なデジタル署名を生成する。このため、デジタル署名の匿名性の安全性を数学的に困難な問題に帰着させること、つまり匿名性の安全性を証明することが可能となる。
【０１１３】
更に、図８に示したように、デジタル署名技術であるリング署名に確認者指名署名方式を単純に組み合わせると、計算量と署名データの大きさの増加量が大きい。本実施形態では、リング署名と確認者指名署名方式を単純に組み合わせるのではなく、計算量と署名データを大幅に削減できる方式となっている。具体的にはコミットメントの検証を１回で済ませる方式としたことにより、本実施形態は、効率の向上を実現させることができる。
【０１１４】
なお、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１１５】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１１６】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１１７】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１１８】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１９】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１２０】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１２１】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１２２】
【図１】本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図である。
【図２】図１における情報の流れを示す模式図である。
【図３】同実施形態における全体の動作を示すシーケンス図である。
【図４】同実施形態における署名生成の動作を説明するためのフローチャートである。
【図５】同実施形態における確認者による署名検証の動作を説明するためのフローチャートである。
【図６】同実施形態における検証者等による署名検証の動作を説明するためのフローチャートである。
【図７】本発明方式の概略を示す模式図である。
【図８】従来方式と本発明方式とを比較して示す図である。
【符号の説明】
【０１２３】
１０，２０，３０…ユーザ端末、１１，２１…秘密鍵記憶装置、１２…署名生成部、２２…確認者用署名検証部、２３，３２…対話証明部、３１…検証者用署名検証部、４０…公開掲示板サーバ、４１…公開情報記憶装置、５０…ネットワーク。
【技術分野】
【０００１】
本発明は、デジタル署名方式の一種のリング署名方式を用いるデジタル署名システム、装置及びプログラムに係り、特に、署名者の匿名性と、検証者の制限とを両立し得るデジタル署名システム、装置及びプログラムに関する。
【背景技術】
【０００２】
デジタル署名方式として、従来からリング署名方式が知られている(例えば、非特許文献１及び非特許文献２参照)。
【０００３】
リング署名方式とは、以下の性質をもつデジタル署名方式である。
第１は、署名者がメンバを任意にＮ人選んで生成したグループの代表として署名を生成することが可能であるという性質である。
【０００４】
第２は、Ｎ人に含まれているユーザを含めた任意の検証者はＮ人のうちの１人が署名した事実は検証可能だが、どの１人が署名者であるかを特定するのが困難な性質である。
【０００５】
もう一つデジタル署名として、従来から指名確認者署名方式が知られている(例えば、非特許文献３参照)。
【０００６】
指名確認者署名方式とは、以下の性質を持つデジタル署名方式である。
【０００７】
第１は、署名者が任意に選んだユーザを確認者として指名し、その確認者は、署名の正当性を検証でき、それ以外のユーザは署名の正当性を検証できないという性質である。
【０００８】
第２は、署名者に確認者として指名されていないユーザは一人では署名の正当性を検証できないが、署名者に確認者として指名されているユーザと指名されていないユーザが対話的に証明をすることによって、指名されていないユーザも署名の正当性を確認することができるという性質である。
【０００９】
以上のようなリング署名方式及び指名確認者署名に関連する他の先行技術文献情報としては、後で引用する非特許文献４−８などがある。
【非特許文献１】Ｒ．リベスト、Ａ．シャミア、Ｙ．タウマン（R.Rivest, A.Shamir, Y.Tauman）著、「ハウ・トゥ・リーク・ア・シークレット（How to Leak a Secret）」、アジアクリプト２００１（ASIACRYPT2001）、ＬＮＣＳ ２２４８、シュプリンガー・フェアラーク（Springer-Verlag）、ｐｐ.５５２−５６５、２００１年
【非特許文献２】大久保、阿部、鈴木、辻井著、「証明長が短い １−ｏｕｔ−ｏｆ−ｎ証明」、暗号と情報セキュリティシンポジウム（ＳＣＩＳ２００２）、ｐｐ.１８９−１９３、２００２年
【非特許文献３】Ｄ．チャウム（D.Chaum）著、「デザイネイティッド・コンファーマー・シグニチャーズ（Designated Confirmer Signatures）」、ユーロクリプト'９４（EUROCRYPT'94）、ＬＮＣＳ ９５０、シュプリンガー・フェアラーク（Springer-Verlag）、ｐｐ.８６−９１、１９９４年
【非特許文献４】Ｍ．ミヘルス、Ｍ．スタドラー（M. Michels, M. Stadler）著、「ジェネリック・コンストラクションズ・フォア・セキュア・アンド・エフィシェント・コンファーマー・シグネチャー・スキームズ（Generic Constructions for Secure and Efficient Confirmer Signature Schemes）」、ユーロクリプト'９８（EUROCRYPT'98）、ＬＮＣＳ １４０３、ｐｐ.４０６−４２１、１９９８年
【非特許文献５】Ｍ．阿部、Ｍ．大久保、Ｋ．鈴木（M. Abe, M. Ohkubo, K. Suzuki）著、「１−アウト−オブ−ｎ・シグネチャーズ・フローム・ア・バラエティ・オブ・キーズ（1-out-of-n Signatures from a Variety of Keys）」、アジアクリプト２００２（ASIACRYPT2002）、ＬＮＣＳ ２５０１、ｐｐ.４１５−４３２、２００２年
【非特許文献６】Ａ．フジオカ、Ｔ．オカモト、Ｋ．オオタ（A. Fujioka, T. Okamoto, K. Ohta）著、「インタラクティブ・バイ−プルーフ・システムズ・アンド・アンデナイアブル・シグネチャー・スキームズ（Interactive Bi-Proof Systems and Undeniable Signature Schemes）」、ユーロクリプト'９１（EUROCRYPT'91）、ＬＮＣＳ ５４７、ｐｐ.２４３−２５６、１９９２年
【非特許文献７】Ｍ．ミヘルス、Ｍ．スタドラー（M. Michels, M. Stadler）著、「エフィシェント・コンバーチブル・アンデナイアブル・シグネチャー（エクステンデッド・アブストラクト）（Efficient Convertible Undeniable Signature (Extended Abstract）」、ピーアールオーシー・フォース・インターナショナル・ワークショップ・オン・セレクテッド・エリアズ・イン・クリプトグラフィー−エスエイシー'９７（Proc. 4th International Workshop on selected Areas in Cryptography - SAC'97）、ｐｐ.２３１−２４４、１９９７年
【非特許文献８】米沢、花岡、今井 著、「検証者が多数の場合に適した検証者指定署名」、暗号と情報セキュリティシンポジウム−ＳＣＩＳ２００３、ｐｐ．６７−７０、２００３年
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら以上のようなデジタル署名システムでは、リング署名及び指名確認者署名のそれぞれについて以下のような不都合がある。
【００１１】
リング署名は、公開されている情報を用いると、誰でも署名の正当性を検証できる。しかし、誰でも検証できるということは、署名者の意図しない範囲のメンバにも正当性を納得させてしまうことができて、署名の存在を悪用されてしまう可能性がある。
【００１２】
例えば、リング署名を用いて社内の不正告発システムを構築したとする。このシステムを導入した企業を仮にＡ社とする。Ａ社は告発システムを、自浄効果を期待して導入した。
【００１３】
Ａ社のある社員はこのシステムを用いて社内の不正を告発するリング署名付き文書を作成したとする。この署名は本来ならば社内にとどめて、内容を検討するために利用するものである。しかしながら、悪意や手違いから新聞社や放送メディアなどの第三者に渡ってしまい、署名が誰にでも検証が可能なことから署名の正当性を検証され、対処する前にＡ社の不正だけが取り上げられてしまう場合が考えられる。この場合、自浄効果の意味がなくなってしまう。
【００１４】
一方、指名確認者署名においては、署名者が一人しか存在しないので、確認時、検証時には、その人が署名したか否かという正当性を検証することになるため、匿名性がない。
【００１５】
まとめると、リング署名には、署名者が匿名性を持つ反面、署名の検証者が制限されないという不都合がある。指名確認者署名には、署名を検証可能な者を確認者又は確認者が対話する検証者に制限できる反面、署名者の匿名性が無いという不都合がある。
【００１６】
本発明は上記実情を考慮してなされたもので、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限し得るデジタル署名システム、装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
第１の発明は、署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置と、前記リング署名を検証する際に、前記確認者の公開鍵情報に対応する秘密鍵情報（ｘC）に基づいて、当該リング署名を検証する確認者用署名検証装置と、前記リング署名を検証する際に、前記確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置とを備えたデジタル署名システムである。
【００１８】
（作用）
第１の発明は、署名者としてのユーザに固有の秘密鍵情報（ｘi）及び署名者が選択した他の複数のユーザの公開鍵情報（ｙj）及び署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成する。
【００１９】
これにより、署名者は、リング署名に含めたい他のユーザとの事前やりとり無しで他のユーザの公開鍵情報を任意に選ぶことができ、リング署名からは各ユーザのうちの誰が署名したかが検証者には全くわからないという特徴を持ったリング署名を生成できる。
【００２０】
これに加え、署名者が署名時に指名した特定の確認者だけが検証でき、それ以外の検証者は一人では署名の正当性を検証できないが、先述の特定の確認者と対話を行うことで特定の確認者以外の検証者も署名の正当性を知ることができる署名を生成できる。
【００２１】
従って、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限することができる。
【００２２】
なお、第１の発明は、各装置からなる全体構成を「システム」として表現したが、これに限らず、全体構成又は各装置を「装置」、「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」として表現してもよい。
【発明の効果】
【００２３】
以上説明したように本発明によれば、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限できる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の一実施形態につき図面を参照して説明する。始めに、従来方式を改良した指名確認者署名方式を示し、続いて、この改良した指名確認者署名方式を前提とした本発明方式の概要を述べる。しかる後、本発明方式の一実施形態について説明する。
【００２５】
（１． 改良した指名確認者署名方式）
ここでは、従来の非特許文献４方式を本発明者により改良した指名確認者署名方式を示す。一般に、指名確認者署名は、署名者（Signer）、確認者（Confirmer）、一般的な検証者（Verifier）の三者で成立している。確認者は、署名者と対話、もしくは確認者のみで署名を検証できる。検証者は、確認者と対話することによってのみ、署名の検証が可能となる。
【００２６】
（１．１ 準備）
符号Ｓを署名者とする。符号Ｃを、署名者に指定された確認者とする。符号Ｖを、権限の無い一般の検証者とする。
【００２７】
ここで、ｑ｜ｐ−１を満たす大きな素数をｐ，ｑとする。位数がｑであるｐの部分群の生成元をｇとする。署名者Ｓは、ｘS∈Ｚｑを秘密鍵、ｙS＝ｇ{ｘ_S} ｍｏｄ ｐを公開鍵として生成し、公開鍵ｙSを公開する。さらに、確認者の秘密鍵をｘC∈Ｚｑ、公開鍵をｙC＝ｇ{ｘ_C}とする。また、符号ｈ，ｈｑを衝突困難性ハッシュ関数とする。
【００２８】
（１．２ 署名生成）
署名者Ｓは以下を計算する。
【数１】
【００２９】
但し、α，ｋ∈Ｚｑとし、σ（ｍ）＝（Ｔ，ｓ，ｄ1，ｄ2）をｍに対する署名として出力する。
【００３０】
（１．３ 署名検証（確認者Ｃによる））
確認者Ｃは、以下を検証する。
【数２】
【００３１】
確認者Ｃは、２つの検証結果が合格であれば署名を受理し、そうでなければ署名を棄却する。
【００３２】
（１．４ 署名検証（検証者Ｖによる））
ステップ１：
検証者Ｖは、署名情報が次式を満たすかを確認者Ｃとの対話証明により間接的に検証する。補足すると、次の対数の検証式は直接には計算されず、成り立つことが対話証明により確認される。
【数３】
【００３３】
検証者Ｖは、２つの検証結果が合格であれば署名を受理し、そうでなければ署名を棄却する。
【００３４】
（２． 本発明方式の概要）
図７は本発明方式の概略を示す模式図である。本発明方式は、上述した「改良した指名確認者署名方式」を連鎖的に行なう形式となっている。従来の非特許文献４の方式は、確認者Ｃは署名者Ｓと対話せずに署名検証が可能であるため、署名者の匿名性を保証できるリング署名の性質は損なわれない。また、非特許文献４の方式をそのままリング署名に適用すると、確認者Ｃによるメッセージｍに対するコミットメントの検証や、確認者Ｃの検証者Ｖに対するメッセージｍについてのコミットメントの知識証明（Interactive bi-proof）の計算量がグループサイズｎに比例してしまう。そこで、本発明方式では、コミットメントの検証が１回で済むように効率を改善している。
【００３５】
（２．１ 準備）
符号Ｇをグループメンバの集合とする。Ｕj（ｊ＝１，…，ｎ）をメンバ集合Ｇに属するメンバ、Ｕiを署名者とする。メンバＵjはｘj∈Ｚｑを秘密鍵、ｙj＝ｇ{ｘ_j} ｍｏｄ ｐとし、公開鍵ｙjを公開する。その他のエンティティとパラメータは、前述した指名確認者署名方式と同様とする。
【００３６】
（２．２ リング署名生成）
署名者Ｕiは、確認者Ｃの公開鍵に関連付けたメッセージｍに対するコミットメント（ｄ1，ｄ2）及びコミットメントに対するリング署名（ｄ1，ｄ2）（ｃ1，ｓ1，…，ｓn）を以下のように生成する。
【００３７】
ステップ１：
署名者Ｕiは、以下のＴi，ｄ1，ｄ2，ｃi+1を求める。但し、α，ｋ∈Ｚｑとする。
【数４】
【００３８】
ステップ３：
署名者Ｕiは、ｃiについて、以下のｓiを計算する。
【００３９】
ｓi＝α−ｘiｃi mod ｑ
ステップ４：
署名者Ｕiは、以上の計算結果からσ（ｍ）＝（ｃ1，ｓ1，…，ｓn，ｄ1，ｄ2）をメッセージｍに対する署名として出力する。
【００４０】
（２．３ リング署名検証（確認者Ｃによる））
確認者Ｃは、コミットメントの正当性を下式により検証する。
【数５】
【００４１】
ここで、確認者Ｃは、ｃ1＝ｃn+1となることを検証することにより、コミットメントに対するリング署名の正当性を検証する。確認者Ｃは、全ての検証結果が合格であれば署名を受理し、そうでなければ署名を棄却する。
【００４２】
（２．４ リング署名検証（検証者Ｖによる））
ステップ１：
検証者Ｖは、まず、ｊ＝１，…，ｎまで以下を繰り返す。
【数６】
【００４３】
検証者Ｖは、ｃ1＝ｃn+1となることを検査することにより、コミットメントに対するリング署名の正当性を検証する。
【００４４】
ステップ２：
また、検証者Ｖは、署名情報が次式を満たすかを確認者Ｃとの対話証明により検査し、メッセージに対するコミットコミットメントの正当性を検証する。検証の手順は、前述した「改良した指名確認者署名方式」と同様である。
【数７】
【００４５】
（３． 安全性）
ここでは、安全な指名確認者リング署名が満たす条件を示し、本発明方式がこれらの条件（i）〜（vi）を満たしていることを証明する。
【００４６】
（i）署名の完全性（Completeness of Signature）
署名者が正しい動作をした場合には、確認者が検証可能な署名を構成できること。
【００４７】
（ii）署名の偽造不可能性（Unforgeability of Signature）
リング署名を構成するグループのメンバ以外が署名を偽造できないこと。
【００４８】
（iii）署名者の曖昧性（Signer Ambiguity）
署名の情報から署名者の情報が漏れないこと。
【００４９】
（iv）署名の不可視性（Invisibility of Signature）
確認者Ｃ、又は確認者Ｃと対話証明を行なう検証者Ｖは、署名の正当性を検証できるが、それ以外のユーザは署名の正当性を検証できないこと。
【００５０】
（ｖ）検証の一貫性（Consistency of Verification）
確認者Ｃや検証者Ｖが正しい動作をした場合は、正しく検証ができること。
【００５１】
（vi）検証の非伝達性（Non-transferability of Verification）
確認者Ｃの秘密鍵に関する情報が対話証明において、検証者Ｖにほとんど漏れないこと。
【００５２】
本発明方式は、以上の要求条件に対して以下の定理が成り立つ。
【００５３】
（定理１：署名の完全性）
正しい秘密鍵をもつ署名者Ｕiがアルゴリズムに従い生成したリング署名は、確認者Ｃの署名検証に常に成功する。
証明：プロトコルから明らかである。
【００５４】
（定理２：署名の偽造不可能性）
本発明方式は、ランダムオラクルモデルと離散対数問題の困難性を仮定すると、グループメンバ以外の任意の敵が署名の偽造に成功する確率は無視できるほど小さい。
【００５５】
証明（Sketch）:ｄ，ｄがＤＤＨ仮定の下に不可視(invisible)であることは非特許文献４で証明されている。このとき、仮に本発明方式が偽造可能であると仮定すると、非特許文献５により提案されたリング署名を偽造可能な敵を構成することができる。
【００５６】
（定理３：署名者の曖昧性）
任意のメッセージに対するリング署名から署名者を特定できる確率は１／ｎである。
【００５７】
証明（Sketch）：ｓiを除くｓjはＺｑから一様にランダムに選ばれ、ｓiはαがＺｑ上から一様にランダムに選ばれるので、ｓiもＺｑ上に一様に分布する。また、ｄ1，ｄ2はメンバ公開鍵には関係しない。従って、グループメンバと（ｍ）を固定すると、（ｓ1，…，ｓn，ｄ1，ｄ2）は、署名者が誰であるかに関わらず、同様にｎｑのバリエーションをもつ。残りのｃ1は、グループメンバのリスト、（ｍ）及び（ｓ1，…，ｓn，ｄ1，ｄ2）より一意に決定できる。よって、署名者を特定できる確率は１／ｎである。
【００５８】
（定理４：署名の不可視性）
任意の敵に対して正しい署名とシミュレータの出力する署名を優位な確率で区別することが不可能なシミュレータを構成できる。
【００５９】
証明（Sketch）：メッセージｍに対するコミットメントは、不可視（invisible）であることが証明されている（非特許文献４参照）。また、本発明方式の署名偽造不可能性から、本発明方式の不可視性（invisibility）は、メッセージｍに対するコミットメントと等価であることを示すことが可能であり、よって定理４が成り立つ。
【００６０】
（定理５：検証の一貫性）
確認者Ｃと検証者Ｖの間で行われるリング署名検証プロトコルにおいて、正しいリング署名が検証に失敗する確率及び不正なリング署名が検証に成功する確率は任意の確認者Ｃに対して無視できる。
【００６１】
（定理６：検証の非伝達性）
確認者Ｃと検証者Ｖの間で行われるリング署名検証プロトコルは、最小知識対話証明（minimum knowledge bi-proof）である（非特許文献６参照）。
【００６２】
証明（定理５，６）：前述した「改良した指名確認者署名方式」は、非特許文献７に記載の対話証明システム（bi-proof system）を用いている。対話証明システムの完全性（completeness）、安定性（Soundness）、零知識証明性（Zero-Knowledgeness）は、非特許文献７によって証明されており、この性質から一貫性、非伝達性は明らかである。これは本発明方式でも成り立つ。
【００６３】
（効率の比較）
図８は従来方式と本発明方式とを比較して示す図である。具体的には従来方式と本発明方式とに関し、署名長、確認者Ｃによるコミットメントに対する検証コストと、リング署名の検証コスト、確認者Ｃと検証者Ｖ間での対話証明（bi-proof）とリング署名の検証コストに関しての比較結果を示している。｜ｐ｜は素数ｐのビット長を表している。
【００６４】
ここでは、リング署名方式（非特許文献２）と、非特許文献２及び非特許文献４を組み合わせただけのナイーブ（素朴）なプロトコルと、本発明方式とを比較した。
【００６５】
ナイーブなプロトコルは、本発明方式と比較して署名長がおよそ３倍となり、コミットメントの検証と対話証明の検証コストがＯ（ｎ）となる。これは、リング署名生成フェーズで、公開鍵ｙCに関するコミットメントをｎ回生成するためである。特に、確認者Ｃと検証者Ｖ間での対話証明が対話的に行われるため、このプロトコルの効率悪化は影響が大きい。本発明方式では、ｎ個のコミットメントの計算を一回にして検証可能となるように改良しているため、これらの検証コストがＯ（１）に抑制されている。
すなわち、本発明方式は、非特許文献４の方式をそのままリング署名に適用した場合に比べ、知識証明に関する効率を向上させることができる。
【００６６】
（応用）
ここでは、本発明方式の応用について述べる。非特許文献８では、複数の確認者Ｃを用いても、署名長が確認者Ｃの数に依存しない指名確認者署名方式が提案されている。これは、信頼できる機関（ＴＡ）を仮定し、この機関ＴＡが確認者Ｃの秘密鍵を多数使用放送暗号化スキーム（Multiple use broadcast encryption scheme）の技術を用いて配布することにより、確認者Ｃの集合が同じ鍵を共有できるようにしたものである。同様にこの技術を本発明方式に適用することにより、正しく秘密鍵を入手できる確認者Ｃは、誰でも署名を検証することができる。確認者Ｃと検証者Ｖ間の検証が頻繁に発生する場合には確認者の負荷を分散できるため、有用である。
以上が本発明方式の概要である。続いて、本発明の一実施形態について説明する。
【００６７】
（一実施形態）
図１は本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図であり、図２は図１における情報の流れを示す模式図である。このシステムは、複数のユーザ端末１０及び各１台のユーザ端末２０，３０を備えている。各ユーザ端末１０，２０，３０は、コンピュータにより実現される場合、それぞれ各端末１０，２０，３０の機能を実現するためのプログラムが予め記憶媒体又はネットワークから各端末のコンピュータにインストールされて実現される。
【００６８】
ユーザ端末は、ユーザ端末１０，２０，３０に分類される。
複数のユーザ端末１０は、署名者Ｓとしてのユーザｕのユーザ端末１０と、リング署名に用いられるグループメンバとしての各ユーザｋ，…のユーザ端末１０，…とを含む。
【００６９】
各ユーザ端末１０は、秘密鍵記憶装置１１及び署名生成部１２を備えている。
【００７０】
ここで、秘密鍵記憶装置１１は、署名者としてのユーザに固有の秘密鍵情報が記憶されるメモリであり、署名生成部１２から読出可能となっている。
【００７１】
署名生成部１２は、署名者としてのユーザに固有の秘密鍵情報（ｘi）及び署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するものであり、具体的には図３及び図４に示すステップＳＴ１２〜ＳＴ１７の処理を実行する機能をもっている。
【００７２】
これらの機能としては、例えば、デジタル署名装置としてのユーザ端末１０のコンピュータを、適切な第１乱数情報（α）に基づいて、第１リング要素関連情報（Ｔi）を生成する機能と、デジタル情報（ｍ）、適切な第２乱数情報（ｋ）、及びハッシュ関数に基づいて、第１コミットメント情報（ｄ1）を生成する機能と、確認者の公開鍵情報（ｙC）、適切な第２乱数情報（ｋ）に基づいて、第２コミットメント情報（ｄ2）を生成する機能と、第１及び第２コミットメント情報（ｄ1，ｄ2）、第１リング要素関連情報（Ｔｉ）及びハッシュ関数に基づいて、リング要素情報（ｃi+1、但し i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする）を生成する機能と、他のユーザに関する適切なメンバ乱数情報（ｓj）をランダムに生成する機能と、他のユーザの公開鍵情報（ｙj）、メンバ乱数情報（ｓｊ）、及びリング要素情報に基づいて、第２リング要素関連情報（Ｔｊ）を生成する機能と、第１及び第２コミットメント情報（ｄ1，ｄ2）、第２リング要素関連情報（Ｔｊ）及びハッシュ関数に基づいて、リング要素情報（ｃj+1、但し j = n の場合、ｃj+1＝ｃ{(j+1) mod n}）を生成する機能と、署名者の秘密鍵情報（ｘi）及び署名者に対応するリング要素情報（ｃi）に基づいて、署名者関連情報（ｓi）を生成する機能と、１番目のリング要素情報（ｃ1）、署名者関連情報（ｓi）、メンバ乱数情報（ｓj＝ｓ1，…，ｓi-1，ｓi+1，…，ｓn）、第１及び第２コミットメント情報（ｄ1，ｄ2）を含むリング署名｛σ（ｍ）＝（ｃ1，ｓ1，…，ｓn，ｄ1，ｄ2）｝を生成する機能とが含まれる。
【００７３】
ユーザ端末２０は、指定された確認者Ｃとしてのユーザcに操作されるものであり、秘密鍵記憶装置２１、確認者用署名検証部２２及び対話証明部２３を備えている。
【００７４】
秘密鍵記憶装置２１は、確認者としてのユーザに固有の秘密鍵情報が記憶されるメモリであり、確認者用署名検証部２２及び対話証明部２３から読出可能となっている。
【００７５】
確認者用署名検証部２２は、リング署名を検証する際に、確認者の公開鍵情報（ｙC）、この公開鍵情報に対応する秘密鍵情報（ｘC）及びデジタル情報（ｍ）に基づいて、当該リング署名を検証する第１検証機能と、リング署名を検証する際に、署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第２検証機能と、第１及び第２検証機能による検証に合格したとき、リング署名を受理するリング署名受理機能とを有し、具体的には図３及び図５のステップＳＴ２０〜ＳＴ２５に示す処理を実行する機能をもっている。
【００７６】
対話証明部２３は、検証者用の対話証明部３２による対話証明の際に動作するものであり、図６のステップＳＴ３３，ＳＴ３４，ＳＴ３６〜ＳＴ３８に示す処理を実行する機能をもっている。
【００７７】
ユーザ端末３０は、検証者Ｖとしてのユーザｖに操作されるものであり、検証者用署名検証部３１及び対話証明部３２を備えている。
【００７８】
検証者用署名検証部３１は、リング署名を検証する際に、署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第１検証機能と、この第１検証機能及び対話証明部３２の第２検証機能による検証に合格したとき、リング署名を受理するリング署名受理機能とを有し、具体的には図６のステップＳＴ３１，ＳＴ４０〜ＳＴ４２に示す処理を実行する機能をもっている。
【００７９】
対話証明部３２は、リング署名を検証する際に、確認者の公開鍵情報（ｙC）に基づき、確認者のユーザ端末２０との間の対話証明を介して、当該リング署名を検証する第２検証機能を有し、具体的には図６のステップＳＴ３２，ＳＴ３５，ＳＴ３９に示す処理を実行する機能をもっている。
【００８０】
また前提条件として、公開鍵基盤などにより、公開情報を安全に公開するための手段、例えば公開掲示板サーバ４０などが存在するとする。
【００８１】
公開掲示板サーバ４０は、公開される情報を記憶する公開情報記憶装置４１を有する。この公開掲示板サーバ４０によって実現される情報公開(掲載)手段を公開情報掲示板と呼ぶ。公開情報掲示板は全てのユーザがアクセスでき、かつ改ざんなどの不正が行われないように適切に管理されているとする。また、全てのユーザはインターネットなどのネットワーク５０に接続されているものとする。特に匿名性を必要とする場合は匿名ネットワークに接続されていてもよいが、その限りではない。
【００８２】
次に、以上のように構成されたデジタル署名システムの動作を図３のシーケンス図及び図４乃至図６の各フローチャートを用いて述べる。なお、本実施形態では、例えばべき乗を ^ で表し、下付添字を _ で表し、文字の真上の波形符号を \tilde で表す等というように１行で済む数式表現を用いている。この数式表現は、前述した本発明方式の概要説明におけるイメージ読込を要する数式表現とは異なるが、数式の内容は対応している。
【００８３】
（準備）：
本実施形態では、前提条件として、ユーザの公開鍵や公開情報は予め公開掲示板サーバ４０により公開されているものとする。公開の方法としては例えば公開鍵基盤などがあるが、ここでは限定しない。
【００８４】
まず、公開掲示板サーバ４０は、素数位数qの巡回群Gとその生成元gを選び公開する。ここでは、一例として、q|p-1 を満たす十分大きな素数p,qを選び、位数がqとなるZp*の部分群をGとし、p,q,gを公開するとする。
【００８５】
さらに、公開掲示板サーバ４０は、衝突困難性ハッシュ関数h:{0,1}^*→{0,1}^q，
h_q:{0,1}^*→{0,1}^qを任意に選び公開する。
【００８６】
また前提条件に従い各ユーザ端末１０，２０は、それぞれユーザu,k,cの操作により、x_u，x_k，x_c ∈ Zqをランダムに選び、以下を計算する。なお、記号^はべき乗を表す。
y_u=g^{x_u},
y_k=g^{x_k},
y_c=g^{x_c}
そして、各ユーザu,k,cのユーザ端末１０，２０は、y_u，y_k，y_cを公開鍵として公開する。
ステップＳＴ１０：リング署名の生成（図３、図４）
ユーザuとなるべきユーザは複数いると仮定する。その中でも特に署名者となるユーザuをユーザu_iとする。ユーザu_iは署名時に任意のグループを作成する。このグループに含まれるユーザuをユーザu_jとする。(j=1,...,n，j≠i)
ユーザu_iのユーザ端末１０は、署名生成部１１において、ユーザ秘密鍵x_i、メッセージm、及び公開情報掲示板14から取得可能な公開情報ＰＵＢＩ（ユーザu_jの公開鍵を含む）を入力として（ＳＴ１１）、以下のステップＳＴ１２〜ＳＴ１７の手順によりmに対するリング署名σを生成し、(m,σ)を出力する。
【００８７】
ステップＳＴ１２：α,k ∈Z_qをランダムに選ぶ。
【００８８】
ステップＳＴ１３：衝突困難性ハッシュ関数hとh_qを用いて以下の値を計算する。
T_i = g^α mod p,
d_1 = g^{k+h_q(m)} mod p,
d_2 = {y_C}^k mod p,
c_{i+1} = h(d_1‖ d_2 ‖ T_i)
但し、i = n の場合には c_{i+1} = c_{(i+1)mod n}とする。また、“‖”はデータの連結を表す。
【００８９】
ステップＳＴ１４： j=i+1,...,n,1,..., i-1について、s_j∈Z_qをランダムに選ぶ。
【００９０】
ステップＳＴ１５：j=i+1,...,n,1,..., i-1について、以下の値を計算する。
T_j = g^{s_j}{y_j}^{c_j} mod p,
c_{(j+1)mod n} = h(d_1 ‖ d_2 ‖ T_j)
但し、j = n の場合には c_{j+1} = c_{(j+1)mod n}とする。
【００９１】
ステップＳＴ１６：s_i = α - {x_i}{c_i} mod qを計算する。
【００９２】
ステップＳＴ１７：j=1,...,nについて、以下の値をリング署名σとして確認者ユーザｃのユーザ端末２０、または検証者ユーザｖのユーザ端末３０に送信する。
σ(m) = (c_1,s_j, d_1 ,d_2)
ステップＳＴ２０：リング署名の確認者による検証（図３、図５）
署名確認者であるユーザcのユーザ端末２０は、署名検証部２２において、メッセージmとmに対するリング署名σのペア(m,σ)及び公開掲示板サーバ４０から取得可能な公開情報ＰＵＢＩを用いて、以下のステップＳＴ２１〜ＳＴ２５の手順でリング署名の正当性とメッセージmに対するコミットメントの正当性を検証する。
【００９３】
ステップＳＴ２１：メッセージm及びリング署名σから、公開情報である衝突困難性ハッシュ関数h_q及び確認者の秘密鍵x_Cを用い、以下の式が成り立つことを検証する。
d_1^{x_C}/d_2 = {y_C}^{{h_q}(m)}
ステップＳＴ２２：j = 1, ..., nについて、公開情報である衝突困難性ハッシュ関数hを用いて以下の値を計算する。
T_j = g^{s_j}{y_j}^{c_j} mod p,
c_{j+1} = h(d_1 ‖ d_2 ‖ T_j)
ここで、c_1=c_{n+1}が成り立つことを検証する。
【００９４】
ステップＳＴ２３〜ＳＴ２５：上記ＳＴ２１，２２が共に成り立つ場合は検証合格（ＯＫを出力してリング署名σ（ｍ）を受理し、成り立たない場合は検証不合格（ＮＧ）を出力してリング署名σ（ｍ）を棄却する。
【００９５】
ステップＳＴ３０：リング署名の検証者による検証（図３、図６）
署名検証者であるユーザvのユーザ端末３０は、メッセージmとmに対するリング署名σのペア(m,σ)と公開掲示板サーバ４０から取得可能な公開情報ＰＵＢＩとを予め記憶装置（図示せず）に記憶しておく。そして、ユーザ端末３０は、記憶装置内のリング署名σのペア(m,σ)及び公開情報ＰＵＢＩを用いて、署名検証部３１においてコミットメントに対するリング署名の正当性の検証と、対話証明部３２において確認者ユーザcのユーザ端末２０の対話証明部２３との対話的証明により、リング署名に含まれるメッセージmに対するコミットメントの正当性を検証する。
【００９６】
ステップＳＴ３１：検証者のユーザ端末３０は、j = 1, ... , nについて、メッセージm、リング署名σ及び衝突困難性ハッシュ関数hより以下の値を計算する。
T_j = g^{s_j}{y_j}^{c_j} mod p,
c_{j+1} = h(d_1 ‖ d_2 ‖ T_j)
c_1=c_{n+1}となることを検査することにより、コミットメントに対するリング署名の正当性を検証する。
【００９７】
ステップＳＴ３２：検証者のユーザ端末３０は、署名情報がlog_g (y_C) = log_{d_1}({d_2}{y_C}^{{h_q}(m)}であるかを、以下のＳＴ３３〜ＳＴ３９に示すように、確認者との対話証明により検証する。
【００９８】
始めに、検証者のユーザ端末３０は、u,v ∈ Z_qをランダムに選び、a = {g^u}{y_C}^vを計算して、aを確認者のユーザ端末２０に送る。
【００９９】
ステップＳＴ３３：確認者のユーザ端末３３は、t, \tilde t, w ∈ Z_qをランダムに選択する。
【０１００】
ステップＳＴ３４：確認者のユーザ端末３３は、
r_1 = g^t, r_2 = {d_1}^t,
{{\tilde r}_1} = g^{\tilde t},
{{\tilde r}_2} = {d_1}^{\tilde t}
を計算し、検証者にr_1,r_2,{{\tilde r}_1},{{\tilde r}_2}を送信する。
【０１０１】
ステップＳＴ３５：検証者のユーザ端末２０は、u,vを確認者のユーザ端末３０に送信することによりコミットメントaを開示する。
【０１０２】
ステップＳＴ３６〜ＳＴ３８：確認者のユーザ端末３０は、もしa ≠ {g^u}{{y_C}^v}ならば、プロトコルを中止し、そうでない場合は、
s = t -(v+w)x_P,
{\tilde s} = {\tilde t}-(v+w)t
を計算し、sと{\tilde s}を検証者に送信する。
【０１０３】
ステップＳＴ３９：検証者のユーザ端末３０は、最初に、
{g^s}{y_C}^{v+w} = r_1,
{g^{\tilde s}}{{r_1}^{v+w}} = {\tilde r}_1,
{d_1}^{\tilde s}{{r_2}^{v+w}} = {\tilde r}_2
であるかを確認した後、
d_1^{s}({d_2}{y_C}^{{h_q}(m)})^{v+w} = r_2
を検査する。これにより、log_g (y_C) =log_{d_1}({d_2}{y_C}^{{h_q}(m)})
であることを間接的に検証する。
【０１０４】
ステップＳＴ４０〜ＳＴ４２：検証者のユーザ端末３０は、ステップＳＴ３１のc_1=c_{n+1}と、ステップＳＴ３２〜ＳＴ３９の対話証明によるlog_g (y_C) =log_{d_1}({d_2}{y_C}^{{h_q}(m)})との二つの検証が成り立つ場合は検証合格（ＯＫ）を出力してリング署名σ（ｍ）を受理し、成り立たない場合は検証不合格（ＮＧ）を出力してリング署名σ（ｍ）を棄却する。
【０１０５】
ステップＳＴ２０及びＳＴ３０の検証で、Ｎ人のうちの誰かは確実に署名をしているという事実を確かめることはできるが、どのメンバが署名したかということはわからない。
【０１０６】
また、確認者は自分の秘密鍵ｘCを用いて直接署名の正当性を検証できるが、検証者は確認者と対話を行うことで検証に必要な秘密情報を知らないまま、署名の正当性を確認できる。
【０１０７】
上述したように本実施形態によれば、署名者としてのユーザに固有の秘密鍵情報（ｘi）及び署名者が選択した他の複数のユーザの公開鍵情報（ｙj）及び署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成する。
【０１０８】
これにより、署名者は、リング署名に含めたい他のユーザとの事前やりとり無しで他のユーザの公開鍵情報を任意に選ぶことができ、リング署名からは各ユーザのうちの誰が署名したかが検証者には全くわからないという特徴を持ったリング署名を生成できる。
【０１０９】
これに加え、署名者が署名時に指名した特定の確認者だけが検証でき、それ以外の検証者は一人では署名の正当性を検証できないが、先述の特定の確認者と対話を行うことで特定の確認者以外の検証者も署名の正当性を知ることができる署名を生成できる。
【０１１０】
従って、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限することができる。
【０１１１】
補足すると、リング署名の検証を署名者が指名した確認者が介在したときのみ行えるようにする。詳しくは、一般的な安全性の仮定に基づいた方式を用いたリング署名の署名情報を、メッセージmに対するコミットメントと、コミットメントに対するリング署名に分けることで、署名の正当性を確認者は検証できるが、検証者はメッセージmに対するコミットメントを確認者との対話証明を行うことで検証可能となる。これにより、署名の流通範囲を制限することができる。
【０１１２】
また、署名者装置としてのユーザ端末１０は、リング署名として、ユーザ秘密鍵ｘSについて零知識であることが証明可能なデジタル署名を生成する。このため、デジタル署名の匿名性の安全性を数学的に困難な問題に帰着させること、つまり匿名性の安全性を証明することが可能となる。
【０１１３】
更に、図８に示したように、デジタル署名技術であるリング署名に確認者指名署名方式を単純に組み合わせると、計算量と署名データの大きさの増加量が大きい。本実施形態では、リング署名と確認者指名署名方式を単純に組み合わせるのではなく、計算量と署名データを大幅に削減できる方式となっている。具体的にはコミットメントの検証を１回で済ませる方式としたことにより、本実施形態は、効率の向上を実現させることができる。
【０１１４】
なお、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１１５】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１１６】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０１１７】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１１８】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１９】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１２０】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１２１】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１２２】
【図１】本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図である。
【図２】図１における情報の流れを示す模式図である。
【図３】同実施形態における全体の動作を示すシーケンス図である。
【図４】同実施形態における署名生成の動作を説明するためのフローチャートである。
【図５】同実施形態における確認者による署名検証の動作を説明するためのフローチャートである。
【図６】同実施形態における検証者等による署名検証の動作を説明するためのフローチャートである。
【図７】本発明方式の概略を示す模式図である。
【図８】従来方式と本発明方式とを比較して示す図である。
【符号の説明】
【０１２３】
１０，２０，３０…ユーザ端末、１１，２１…秘密鍵記憶装置、１２…署名生成部、２２…確認者用署名検証部、２３，３２…対話証明部、３１…検証者用署名検証部、４０…公開掲示板サーバ、４１…公開情報記憶装置、５０…ネットワーク。
【特許請求の範囲】
【請求項１】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置と、
前記リング署名を検証する際に、前記確認者の公開鍵情報に対応する秘密鍵情報（ｘC）に基づいて、当該リング署名を検証する確認者用署名検証装置と、
前記リング署名を検証する際に、前記確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置と、
を備えたことを特徴とするデジタル署名システム。
【請求項２】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置であって、
第１乱数情報（α）に基づいて、第１リング要素関連情報（Ｔi）を生成する手段と、
前記デジタル情報（ｍ）、第２乱数情報（ｋ）、及びハッシュ関数に基づいて、第１コミットメント情報（ｄ1）を生成する手段と、
前記確認者の公開鍵情報（ｙC）、前記第２乱数情報（ｋ）に基づいて、第２コミットメント情報（ｄ2）を生成する手段と、
前記第１及び第２コミットメント情報（ｄ1，ｄ2）、前記第１リング要素関連情報（Ｔｉ）及びハッシュ関数に基づいて、リング要素情報（ｃi+1、但し i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする）を生成する手段と、
前記他のユーザに関するメンバ乱数情報（ｓｊ）をランダムに生成する手段と、
前記他のユーザの公開鍵情報（ｙj）、前記メンバ乱数情報（ｓｊ）、及びリング要素情報に基づいて、第２リング要素関連情報（Ｔｊ）を生成する手段と、
前記第１及び第２コミットメント情報（ｄ1，ｄ2）、前記第２リング要素関連情報（Ｔｊ）及びハッシュ関数に基づいて、リング要素情報（ｃj+1、但し j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）を生成する手段と、
前記署名者の秘密鍵情報（ｘi）及び署名者に対応するリング要素情報（ｃi）に基づいて、署名者関連情報（ｓi）を生成する手段と、
１番目のリング要素情報（ｃ1）、前記署名者関連情報（ｓi）、前記メンバ乱数情報（ｓj）、前記第１及び第２コミットメント情報（ｄ1，ｄ2）を含むリング署名｛σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）｝を生成する手段と、
を備えたことを特徴とするデジタル署名装置。
【請求項３】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・に関し、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj（但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCを用いて、任意のデジタル情報ｍに対するリング署名を生成するデジタル署名装置であって、
前記システムパラメータｇ及び第１乱数情報αに基づいて、式 Ｔi ＝ ｇα mod ｐ により、第１リング要素関連情報Ｔiを生成する手段と、
前記システムパラメータｇ、前記デジタル情報ｍ、第２乱数情報ｋ及びハッシュ関数ｈqに基づいて、式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ により（但し、_は下付文字を表す）、第１コミットメント情報ｄ1を生成する手段と、
前記確認者の公開鍵情報ｙC及び前記第２乱数情報ｋに基づいて、式 ｄ2 ＝ yCｋ mod ｐ により、第２コミットメント情報ｄ2を生成する手段と、
前記第１及び第２コミットメント情報ｄ1，ｄ2、前記第１リング要素関連情報Ｔｉ及びハッシュ関数ｈに基づいて、式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi) により、リング要素情報ｃi+1 を生成する手段（但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）と、
前記他のユーザに関するメンバ乱数情報ｓｊをランダムに生成する手段と、
前記システムパラメータｇ、前記他のユーザの公開鍵情報ｙj、前記メンバ乱数情報ｓｊ及びリング要素情報ｃjに基づいて、式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ により、第２リング要素関連情報Ｔｊを生成する手段と、
前記第１及び第２コミットメント情報ｄ1，ｄ2、前記第２リング要素関連情報Ｔｊ及びハッシュ関数ｈに基づいて、式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj) により、リング要素情報ｃj+1 を生成する手段（但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）と、
前記第１乱数情報α、前記署名者の秘密鍵情報ｘi及び署名者に対応するリング要素情報ｃiに基づいて、式 ｓi ＝ α − ｘiｃi mod ｑ により、署名者関連情報ｓiを生成する手段と、
１番目のリング要素情報ｃ1、前記署名者関連情報ｓi、前記メンバ乱数情報ｓj、前記第１及び第２コミットメント情報ｄ1，ｄ2を含むリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）を生成する手段と、
を備えたことを特徴とするデジタル署名装置。
【請求項４】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて生成された任意のデジタル情報（ｍ）に対するリング署名に関し、当該リング署名を検証する確認者用署名検証装置であって、
前記リング署名を検証する際に、前記確認者の公開鍵情報（ｙC）、この公開鍵情報に対応する秘密鍵情報（ｘC）及び前記デジタル情報（ｍ）に基づいて、当該リング署名を検証する第１検証手段と、
前記リング署名を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び前記他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする確認者用署名検証装置。
【請求項５】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・を用いると共に、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj、（但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCや第１乱数情報α、第２乱数情報ｋ、ハッシュ関数ｈ，ｈｑ及び前記他のユーザに関するメンバ乱数情報ｓｊを用いて任意のデジタル情報ｍに対し、以下のＡ式乃至Ｇ式：
Ａ式 Ｔi ＝ ｇα mod ｐ,
Ｂ式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ, （但し、_は下付文字を表す）、
Ｃ式 ｄ2 ＝ yCｋ mod ｐ,
Ｄ式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi), （但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
Ｅ式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ,
Ｆ式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj), （但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
Ｇ式 ｓi ＝ α − ｘiｃi mod ｑ,
の計算により生成されたリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）に関し、当該リング署名σ（ｍ）を検証する確認者用署名検証装置であって、
前記リング署名σ（ｍ）を検証する際に、前記確認者の公開鍵情報ｙC、この公開鍵情報に対応する秘密鍵情報ｘC、前記デジタル情報ｍ及び前記ハッシュ関数ｈqに基づいて、式 ｄ1{ｘ_C} ／ ｄ2 ＝ ｙC{{h_q}(m)} が成り立つことにより、当該リング署名σ（ｍ）を検証する第１検証手段と、
前記リング署名σ（ｍ）を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報ｙi及び前記他の複数のユーザの公開鍵情報ｙjからなる各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙnに基づいて、当該各ユーザに関してＪ＝ 1, ・・・ , i, ・・・ , n まで（但し、Ｊは j, i を読み替えた添字）以下のＨ式及びＩ式：
Ｈ式 ＴJ ＝ ｇ{s_J}ｙJ{c_J} mod ｐ,
Ｉ式 cJ+1 = h(ｄ1‖ｄ2‖ＴJ)
を繰り返し、このＩ式の結果からｃ1＝ｃn+1が成り立つことにより、当該リング署名σ（ｍ）を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする確認者用署名検証装置。
【請求項６】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて生成された任意のデジタル情報（ｍ）に対するリング署名に関し、当該リング署名を検証する検証者用署名検証装置であって、
前記リング署名を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び前記他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第１検証手段と、
前記リング署名を検証する際に、前記確認者の公開鍵情報（ｙC）に基づき、前記確認者の確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする検証者用署名検証装置。
【請求項７】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・を用いると共に、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj（但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCや第１乱数情報α、第２乱数情報ｋ、ハッシュ関数ｈ，ｈｑ及び前記他のユーザに関するメンバ乱数情報ｓｊを用いて以下のＡ式乃至Ｇ式：
Ａ式 Ｔi ＝ ｇα mod ｐ,
Ｂ式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ, （但し、_は下付文字を表す）、
Ｃ式 ｄ2 ＝ yCｋ mod ｐ,
Ｄ式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi), （但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
Ｅ式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ,
Ｆ式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj), （但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
Ｇ式 ｓi ＝ α − ｘiｃi mod ｑ,
の計算により生成されたリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）に関し、当該リング署名σ（ｍ）を検証する検証者用署名検証装置であって、
前記リング署名σ（ｍ）を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報ｙi及び前記他の複数のユーザの公開鍵情報ｙjからなる各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙnに基づいて、当該各ユーザに関してＪ＝ 1, ・・・ , i, ・・・ , n まで（但し、Ｊは j, i を読み替えた添字）以下のＨ式及びＩ式：
Ｈ式 ＴJ ＝ ｇ{s_J}ｙJ{c_J} mod ｐ,
Ｉ式 cJ+1 = h(ｄ1‖ｄ2‖ＴJ)
を繰り返し、このＩ式の結果からｃ1＝ｃn+1が成り立つことにより、当該リング署名σ（ｍ）を検証する第１検証手段と、
前記リング署名σ（ｍ）を検証する際に、前記確認者の公開鍵情報ｙCに基づき、前記確認者の確認者用署名検証装置との間の対話証明を介して、式 logｇ(ｙC) = log{d_1}（ｄ2ｙC{{h_q}(m)}） が成り立つことにより、当該リング署名σ（ｍ）を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えており、
前記第２検証手段は、
第３及び第４乱数情報ｕ，ｖを生成する手段と、
前記システムパラメータｇ、前記第３及び第４乱数情報ｕ，ｖに基づいて、式 ａ ＝ ｇｕｙCｖ により、コミットメント情報ａを計算する手段と、
このコミットメント情報ａを前記確認者用署名検証装置に送信する手段と、
前記確認者用署名検証装置から第１演算パラメータｒ1, ｒ2, {{\tilde r}_1}, {{\tilde r}_2}を受信する手段（但し、\tildeは波形ダッシュ符号を表す、ｒ1 = ｇt, ｒ2 = ｄ1t, {{\tilde r}_1} ＝ ｇ{\tilde t}, {{\tilde r}_2} ＝ ｄ1{\tilde t} 、ｔは第５乱数情報、\tilde tは第６乱数情報）と、
前記第１演算パラメータｒ1, ｒ2, {{\tilde r}_1}, {{\tilde r}_2}を受信すると、前記第３及び第４乱数情報ｕ，ｖを前記確認者用署名検証装置に送信することにより、前記コミットメント情報ａを開示する手段と、
前記コミットメント情報ａが前記確認者用署名検証装置により式ａ＝ｇｕｙCｖに基づいて検証されたとき、前記確認者用署名検証装置から第２演算パラメータｓ, {\tilde s}を受信する手段（但し、ｓ ＝ ｔ −（ｖ＋ｗ）ｘC、 {\tilde s} ＝ {\tilde t}−（ｖ＋ｗ）ｔ、ｗは第７乱数情報）と、
前記第２演算パラメータｓ, {\tilde s}を受信すると、以下のＪ式乃至Ｌ式：
Ｊ式 ｇｓｙC(v+w) ＝ ｒ1,
Ｋ式 ｇ{\tilde s}ｒ1{v+w} ＝ {\tilde r}_1,
Ｌ式 ｄ1{\tilde s}ｒ2{v+w} ＝ {\tilde r}_2
を確認する手段と、
前記確認に加え、式 ｄ1ｓ(ｄ2ｙC{{h_q}(m)}){v+w} ＝ ｒ2 を検査することにより、式 logｇ(ｙC) = log{d_1}（ｄ2ｙC{{h_q}(m)}）であることを間接的に検証する手段と、
を備えたことを特徴とする検証者用署名検証装置。
【請求項８】
署名者としてのユーザに固有の秘密鍵情報（ｘi）が記憶された記憶装置を有し、前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置に用いられるプログラムであって、
前記デジタル署名装置のコンピュータを、
第１乱数情報（α）に基づいて、第１リング要素関連情報（Ｔi）を生成する手段、
前記デジタル情報（ｍ）、第２乱数情報（ｋ）、及びハッシュ関数に基づいて、第１コミットメント情報（ｄ1）を生成する手段、
前記確認者の公開鍵情報（ｙC）、第２乱数情報（ｋ）に基づいて、第２コミットメント情報（ｄ2）を生成する手段、
前記第１及び第２コミットメント情報（ｄ1，ｄ2）、前記第１リング要素関連情報（Ｔｉ）及びハッシュ関数に基づいて、リング要素情報（ｃi+1、但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする）を生成する手段、
前記他のユーザに関するメンバ乱数情報（ｓｊ）をランダムに生成する手段、
前記他のユーザの公開鍵情報（ｙj）、前記メンバ乱数情報（ｓｊ）、及びリング要素情報に基づいて、第２リング要素関連情報（Ｔｊ）を生成する手段、
前記第１及び第２コミットメント情報（ｄ1，ｄ2）、前記第２リング要素関連情報（Ｔｊ）及びハッシュ関数に基づいて、リング要素情報（ｃj+1、但し j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）を生成する手段、
前記署名者の秘密鍵情報（ｘi）及び署名者に対応するリング要素情報（ｃi）に基づいて、署名者関連情報（ｓi）を生成する手段、
１番目のリング要素情報（ｃ1）、前記署名者関連情報（ｓj）、前記メンバ乱数情報（ｓj）、前記第１及び第２コミットメント情報（ｄ1，ｄ2）を含むリング署名｛σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）｝を生成する手段、
として機能させるためのプログラム。
【請求項９】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・や、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)が記憶される記憶装置を有し、この記憶装置を参照しつつ、前記署名者が選択した他の複数のユーザの公開鍵情報ｙj（但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCを用いて、任意のデジタル情報ｍに対するリング署名を生成するデジタル署名装置に用いられるプログラムであって、
前記デジタル署名装置のコンピュータを、
前記システムパラメータｇ及び第１乱数情報αに基づいて、式 Ｔi ＝ ｇα mod ｐ により、第１リング要素関連情報Ｔiを生成する手段、
前記システムパラメータｇ、前記デジタル情報ｍ、第２乱数情報ｋ及びハッシュ関数ｈqに基づいて、式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ により（但し、_は下付文字を表す）、第１コミットメント情報ｄ1を生成する手段、
前記確認者の公開鍵情報ｙC及び前記第２乱数情報ｋに基づいて、式 ｄ2 ＝ yCｋ mod ｐ により、第２コミットメント情報ｄ2を生成する手段、
前記第１及び第２コミットメント情報ｄ1，ｄ2、前記第１リング要素関連情報Ｔｉ及びハッシュ関数ｈに基づいて、式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi) により、リング要素情報ｃi+1 を生成する手段（但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
前記他のユーザに関するメンバ乱数情報ｓｊをランダムに生成する手段、
前記システムパラメータｇ、前記他のユーザの公開鍵情報ｙj、前記メンバ乱数情報ｓｊ及びリング要素情報ｃjに基づいて、式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ により、第２リング要素関連情報Ｔｊを生成する手段、
前記第１及び第２コミットメント情報ｄ1，ｄ2、前記第２リング要素関連情報Ｔｊ及びハッシュ関数ｈに基づいて、式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj) により、リング要素情報ｃj+1 を生成する手段（但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
前記第１乱数情報α、前記署名者の秘密鍵情報ｘi及び署名者に対応するリング要素情報ｃiに基づいて、式 ｓi ＝ α − ｘiｃi mod ｑ により、署名者関連情報ｓiを生成する手段、
１番目のリング要素情報ｃ1、前記署名者関連情報ｓi、前記メンバ乱数情報ｓj、前記第１及び第２コミットメント情報ｄ1，ｄ2を含むリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）を生成する手段、
として機能させるためのプログラム。
【請求項１０】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて生成された任意のデジタル情報（ｍ）に対するリング署名に関し、予め記憶装置に記憶された前記確認者の公開鍵情報に対応する秘密鍵情報（ｘC）に基づいて、当該リング署名を検証する確認者用署名検証装置に用いられるプログラムであって、
前記確認者用署名検証装置のコンピュータを、
前記リング署名を検証する際に、前記確認者の公開鍵情報（ｙC）、前記記憶装置内の前記秘密鍵情報（ｘC）及び前記デジタル情報（ｍ）に基づいて、当該リング署名を検証する第１検証手段、
前記リング署名を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び前記他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１１】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・を用いると共に、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj、（但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCや第１乱数情報α、第２乱数情報ｋ、ハッシュ関数ｈ，ｈｑ及び前記他のユーザに関するメンバ乱数情報ｓｊを用いて任意のデジタル情報ｍに対し、以下のＡ式乃至Ｇ式：
Ａ式 Ｔi ＝ ｇα mod ｐ,
Ｂ式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ, （但し、_は下付文字を表す）、
Ｃ式 ｄ2 ＝ yCｋ mod ｐ,
Ｄ式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi), （但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
Ｅ式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ,
Ｆ式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj), （但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
Ｇ式 ｓi ＝ α − ｘiｃi mod ｑ,
の計算により生成されたリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）に関し、当該リング署名σ（ｍ）を検証する確認者用署名検証装置に用いられるプログラムであって、
前記確認者用署名検証装置のコンピュータを、
前記リング署名σ（ｍ）を検証する際に、前記確認者の公開鍵情報ｙC及びこの公開鍵情報に対応する秘密鍵情報ｘCが記憶された記憶装置を参照しつつ、前記デジタル情報ｍ及び前記ハッシュ関数ｈqに基づいて、式 ｄ1{ｘ_C} ／ ｄ2 ＝ ｙC{{h_q}(m)} が成り立つことにより、当該リング署名σ（ｍ）を検証する第１検証手段、
前記リング署名σ（ｍ）を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報ｙi及び前記他の複数のユーザの公開鍵情報ｙjからなる各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙnに基づいて、当該各ユーザに関してＪ＝ 1, ・・・ , i, ・・・ , n まで（但し、Ｊは j, i を読み替えた添字）以下のＨ式及びＩ式：
Ｈ式 ＴJ ＝ ｇ{s_J}ｙJ{c_J} mod ｐ,
Ｉ式 cJ+1 = h(ｄ1‖ｄ2‖ＴJ)
を繰り返し、このＩ式の結果からｃ1＝ｃn+1が成り立つことにより、当該リング署名σ（ｍ）を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１２】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて生成された任意のデジタル情報（ｍ）に対するリング署名に関し、当該リング署名を検証する検証者用署名検証装置に用いられるプログラムであって、
前記検証者用署名検証装置のコンピュータを、
前記リング署名を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び前記他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第１検証手段、
前記リング署名を検証する際に、前記確認者の公開鍵情報（ｙC）に基づき、前記確認者の確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１３】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・を用いると共に、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj（但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCや第１乱数情報α、第２乱数情報ｋ、ハッシュ関数ｈ，ｈｑ及び前記他のユーザに関するメンバ乱数情報ｓｊを用いて以下のＡ式乃至Ｇ式：
Ａ式 Ｔi ＝ ｇα mod ｐ,
Ｂ式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ, （但し、_は下付文字を表す）、
Ｃ式 ｄ2 ＝ yCｋ mod ｐ,
Ｄ式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi), （但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
Ｅ式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ,
Ｆ式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj), （但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
Ｇ式 ｓi ＝ α − ｘiｃi mod ｑ,
の計算により生成されたリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）に関し、当該リング署名σ（ｍ）を検証する検証者用署名検証装置に用いられるプログラムであって、
前記検証者用署名検証装置のコンピュータを、
前記リング署名σ（ｍ）を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報ｙi及び前記他の複数のユーザの公開鍵情報ｙjからなる各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙnが記憶された記憶装置を参照しつつ、当該各ユーザに関してＪ＝ 1, ・・・ , i, ・・・ , n まで（但し、Ｊは j, i を読み替えた添字）以下のＨ式及びＩ式：
Ｈ式 ＴJ ＝ ｇ{s_J}ｙj{c_J} mod ｐ,
Ｉ式 cJ+1 = h(ｄ1‖ｄ2‖ＴJ)
を繰り返し、このＩ式の結果からｃ1＝ｃn+1が成り立つことにより、当該リング署名σ（ｍ）を検証する第１検証手段、
前記リング署名σ（ｍ）を検証する際に、前記確認者の公開鍵情報ｙCに基づき、前記確認者の確認者用署名検証装置との間の対話証明を介して、式 logｇ(ｙC) = log{d_1}（ｄ2ｙC{{h_q}(m)}） が成り立つことにより、当該リング署名σ（ｍ）を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させ、
前記第２検証手段は、
第３及び第４乱数情報ｕ，ｖを生成する手段と、
前記システムパラメータｇ、前記第３及び第４乱数情報ｕ，ｖに基づいて、式 ａ ＝ ｇｕｙCｖ により、コミットメント情報ａを計算する手段と、
このコミットメント情報ａを前記確認者用署名検証装置に送信する手段と、
前記確認者用署名検証装置から第１演算パラメータｒ1, ｒ2, {{\tilde r}_1}, {{\tilde r}_2}を受信する手段（但し、\tildeは波形ダッシュ符号を表す、ｒ1 = ｇt, ｒ2 = ｄ1t, {{\tilde r}_1} ＝ ｇ{\tilde t}, {{\tilde r}_2} ＝ ｄ1{\tilde t} 、ｔは第５乱数情報、\tilde tは第６乱数情報）と、
前記第１演算パラメータｒ1, ｒ2, {{\tilde r}_1}, {{\tilde r}_2}を受信すると、前記第３及び第４乱数情報ｕ，ｖを前記確認者用署名検証装置に送信することにより、前記コミットメント情報ａを開示する手段と、
前記コミットメント情報ａが前記確認者用署名検証装置により式ａ＝ｇｕｙCｖに基づいて検証されたとき、前記確認者用署名検証装置から第２演算パラメータｓ, {\tilde s}を受信する手段（但し、ｓ ＝ ｔ −（ｖ＋ｗ）ｘC、 {\tilde s} ＝ {\tilde t}−（ｖ＋ｗ）ｔ、ｗは第７乱数情報）と、
前記第２演算パラメータｓ, {\tilde s}を受信すると、以下のＪ式乃至Ｌ式：
Ｊ式 ｇｓｙC(v+w) ＝ ｒ1,
Ｋ式 ｇ{\tilde s}ｒ1{v+w} ＝ {\tilde r}_1,
Ｌ式 ｄ1{\tilde s}ｒ2{v+w} ＝ {\tilde r}_2
を確認する手段と、
前記確認に加え、式 ｄ1ｓ(ｄ2ｙC{{h_q}(m)}){v+w} ＝ ｒ2 を検査することにより、式 logｇ(ｙC) = log{d_1}（ｄ2ｙC{{h_q}(m)}）であることを間接的に検証する手段と、
を含んでいることを特徴とするプログラム。
【請求項１】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置と、
前記リング署名を検証する際に、前記確認者の公開鍵情報に対応する秘密鍵情報（ｘC）に基づいて、当該リング署名を検証する確認者用署名検証装置と、
前記リング署名を検証する際に、前記確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置と、
を備えたことを特徴とするデジタル署名システム。
【請求項２】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置であって、
第１乱数情報（α）に基づいて、第１リング要素関連情報（Ｔi）を生成する手段と、
前記デジタル情報（ｍ）、第２乱数情報（ｋ）、及びハッシュ関数に基づいて、第１コミットメント情報（ｄ1）を生成する手段と、
前記確認者の公開鍵情報（ｙC）、前記第２乱数情報（ｋ）に基づいて、第２コミットメント情報（ｄ2）を生成する手段と、
前記第１及び第２コミットメント情報（ｄ1，ｄ2）、前記第１リング要素関連情報（Ｔｉ）及びハッシュ関数に基づいて、リング要素情報（ｃi+1、但し i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする）を生成する手段と、
前記他のユーザに関するメンバ乱数情報（ｓｊ）をランダムに生成する手段と、
前記他のユーザの公開鍵情報（ｙj）、前記メンバ乱数情報（ｓｊ）、及びリング要素情報に基づいて、第２リング要素関連情報（Ｔｊ）を生成する手段と、
前記第１及び第２コミットメント情報（ｄ1，ｄ2）、前記第２リング要素関連情報（Ｔｊ）及びハッシュ関数に基づいて、リング要素情報（ｃj+1、但し j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）を生成する手段と、
前記署名者の秘密鍵情報（ｘi）及び署名者に対応するリング要素情報（ｃi）に基づいて、署名者関連情報（ｓi）を生成する手段と、
１番目のリング要素情報（ｃ1）、前記署名者関連情報（ｓi）、前記メンバ乱数情報（ｓj）、前記第１及び第２コミットメント情報（ｄ1，ｄ2）を含むリング署名｛σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）｝を生成する手段と、
を備えたことを特徴とするデジタル署名装置。
【請求項３】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・に関し、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj（但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCを用いて、任意のデジタル情報ｍに対するリング署名を生成するデジタル署名装置であって、
前記システムパラメータｇ及び第１乱数情報αに基づいて、式 Ｔi ＝ ｇα mod ｐ により、第１リング要素関連情報Ｔiを生成する手段と、
前記システムパラメータｇ、前記デジタル情報ｍ、第２乱数情報ｋ及びハッシュ関数ｈqに基づいて、式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ により（但し、_は下付文字を表す）、第１コミットメント情報ｄ1を生成する手段と、
前記確認者の公開鍵情報ｙC及び前記第２乱数情報ｋに基づいて、式 ｄ2 ＝ yCｋ mod ｐ により、第２コミットメント情報ｄ2を生成する手段と、
前記第１及び第２コミットメント情報ｄ1，ｄ2、前記第１リング要素関連情報Ｔｉ及びハッシュ関数ｈに基づいて、式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi) により、リング要素情報ｃi+1 を生成する手段（但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）と、
前記他のユーザに関するメンバ乱数情報ｓｊをランダムに生成する手段と、
前記システムパラメータｇ、前記他のユーザの公開鍵情報ｙj、前記メンバ乱数情報ｓｊ及びリング要素情報ｃjに基づいて、式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ により、第２リング要素関連情報Ｔｊを生成する手段と、
前記第１及び第２コミットメント情報ｄ1，ｄ2、前記第２リング要素関連情報Ｔｊ及びハッシュ関数ｈに基づいて、式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj) により、リング要素情報ｃj+1 を生成する手段（但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）と、
前記第１乱数情報α、前記署名者の秘密鍵情報ｘi及び署名者に対応するリング要素情報ｃiに基づいて、式 ｓi ＝ α − ｘiｃi mod ｑ により、署名者関連情報ｓiを生成する手段と、
１番目のリング要素情報ｃ1、前記署名者関連情報ｓi、前記メンバ乱数情報ｓj、前記第１及び第２コミットメント情報ｄ1，ｄ2を含むリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）を生成する手段と、
を備えたことを特徴とするデジタル署名装置。
【請求項４】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて生成された任意のデジタル情報（ｍ）に対するリング署名に関し、当該リング署名を検証する確認者用署名検証装置であって、
前記リング署名を検証する際に、前記確認者の公開鍵情報（ｙC）、この公開鍵情報に対応する秘密鍵情報（ｘC）及び前記デジタル情報（ｍ）に基づいて、当該リング署名を検証する第１検証手段と、
前記リング署名を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び前記他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする確認者用署名検証装置。
【請求項５】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・を用いると共に、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj、（但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCや第１乱数情報α、第２乱数情報ｋ、ハッシュ関数ｈ，ｈｑ及び前記他のユーザに関するメンバ乱数情報ｓｊを用いて任意のデジタル情報ｍに対し、以下のＡ式乃至Ｇ式：
Ａ式 Ｔi ＝ ｇα mod ｐ,
Ｂ式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ, （但し、_は下付文字を表す）、
Ｃ式 ｄ2 ＝ yCｋ mod ｐ,
Ｄ式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi), （但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
Ｅ式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ,
Ｆ式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj), （但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
Ｇ式 ｓi ＝ α − ｘiｃi mod ｑ,
の計算により生成されたリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）に関し、当該リング署名σ（ｍ）を検証する確認者用署名検証装置であって、
前記リング署名σ（ｍ）を検証する際に、前記確認者の公開鍵情報ｙC、この公開鍵情報に対応する秘密鍵情報ｘC、前記デジタル情報ｍ及び前記ハッシュ関数ｈqに基づいて、式 ｄ1{ｘ_C} ／ ｄ2 ＝ ｙC{{h_q}(m)} が成り立つことにより、当該リング署名σ（ｍ）を検証する第１検証手段と、
前記リング署名σ（ｍ）を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報ｙi及び前記他の複数のユーザの公開鍵情報ｙjからなる各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙnに基づいて、当該各ユーザに関してＪ＝ 1, ・・・ , i, ・・・ , n まで（但し、Ｊは j, i を読み替えた添字）以下のＨ式及びＩ式：
Ｈ式 ＴJ ＝ ｇ{s_J}ｙJ{c_J} mod ｐ,
Ｉ式 cJ+1 = h(ｄ1‖ｄ2‖ＴJ)
を繰り返し、このＩ式の結果からｃ1＝ｃn+1が成り立つことにより、当該リング署名σ（ｍ）を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする確認者用署名検証装置。
【請求項６】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて生成された任意のデジタル情報（ｍ）に対するリング署名に関し、当該リング署名を検証する検証者用署名検証装置であって、
前記リング署名を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び前記他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第１検証手段と、
前記リング署名を検証する際に、前記確認者の公開鍵情報（ｙC）に基づき、前記確認者の確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする検証者用署名検証装置。
【請求項７】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・を用いると共に、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj（但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCや第１乱数情報α、第２乱数情報ｋ、ハッシュ関数ｈ，ｈｑ及び前記他のユーザに関するメンバ乱数情報ｓｊを用いて以下のＡ式乃至Ｇ式：
Ａ式 Ｔi ＝ ｇα mod ｐ,
Ｂ式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ, （但し、_は下付文字を表す）、
Ｃ式 ｄ2 ＝ yCｋ mod ｐ,
Ｄ式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi), （但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
Ｅ式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ,
Ｆ式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj), （但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
Ｇ式 ｓi ＝ α − ｘiｃi mod ｑ,
の計算により生成されたリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）に関し、当該リング署名σ（ｍ）を検証する検証者用署名検証装置であって、
前記リング署名σ（ｍ）を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報ｙi及び前記他の複数のユーザの公開鍵情報ｙjからなる各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙnに基づいて、当該各ユーザに関してＪ＝ 1, ・・・ , i, ・・・ , n まで（但し、Ｊは j, i を読み替えた添字）以下のＨ式及びＩ式：
Ｈ式 ＴJ ＝ ｇ{s_J}ｙJ{c_J} mod ｐ,
Ｉ式 cJ+1 = h(ｄ1‖ｄ2‖ＴJ)
を繰り返し、このＩ式の結果からｃ1＝ｃn+1が成り立つことにより、当該リング署名σ（ｍ）を検証する第１検証手段と、
前記リング署名σ（ｍ）を検証する際に、前記確認者の公開鍵情報ｙCに基づき、前記確認者の確認者用署名検証装置との間の対話証明を介して、式 logｇ(ｙC) = log{d_1}（ｄ2ｙC{{h_q}(m)}） が成り立つことにより、当該リング署名σ（ｍ）を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えており、
前記第２検証手段は、
第３及び第４乱数情報ｕ，ｖを生成する手段と、
前記システムパラメータｇ、前記第３及び第４乱数情報ｕ，ｖに基づいて、式 ａ ＝ ｇｕｙCｖ により、コミットメント情報ａを計算する手段と、
このコミットメント情報ａを前記確認者用署名検証装置に送信する手段と、
前記確認者用署名検証装置から第１演算パラメータｒ1, ｒ2, {{\tilde r}_1}, {{\tilde r}_2}を受信する手段（但し、\tildeは波形ダッシュ符号を表す、ｒ1 = ｇt, ｒ2 = ｄ1t, {{\tilde r}_1} ＝ ｇ{\tilde t}, {{\tilde r}_2} ＝ ｄ1{\tilde t} 、ｔは第５乱数情報、\tilde tは第６乱数情報）と、
前記第１演算パラメータｒ1, ｒ2, {{\tilde r}_1}, {{\tilde r}_2}を受信すると、前記第３及び第４乱数情報ｕ，ｖを前記確認者用署名検証装置に送信することにより、前記コミットメント情報ａを開示する手段と、
前記コミットメント情報ａが前記確認者用署名検証装置により式ａ＝ｇｕｙCｖに基づいて検証されたとき、前記確認者用署名検証装置から第２演算パラメータｓ, {\tilde s}を受信する手段（但し、ｓ ＝ ｔ −（ｖ＋ｗ）ｘC、 {\tilde s} ＝ {\tilde t}−（ｖ＋ｗ）ｔ、ｗは第７乱数情報）と、
前記第２演算パラメータｓ, {\tilde s}を受信すると、以下のＪ式乃至Ｌ式：
Ｊ式 ｇｓｙC(v+w) ＝ ｒ1,
Ｋ式 ｇ{\tilde s}ｒ1{v+w} ＝ {\tilde r}_1,
Ｌ式 ｄ1{\tilde s}ｒ2{v+w} ＝ {\tilde r}_2
を確認する手段と、
前記確認に加え、式 ｄ1ｓ(ｄ2ｙC{{h_q}(m)}){v+w} ＝ ｒ2 を検査することにより、式 logｇ(ｙC) = log{d_1}（ｄ2ｙC{{h_q}(m)}）であることを間接的に検証する手段と、
を備えたことを特徴とする検証者用署名検証装置。
【請求項８】
署名者としてのユーザに固有の秘密鍵情報（ｘi）が記憶された記憶装置を有し、前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置に用いられるプログラムであって、
前記デジタル署名装置のコンピュータを、
第１乱数情報（α）に基づいて、第１リング要素関連情報（Ｔi）を生成する手段、
前記デジタル情報（ｍ）、第２乱数情報（ｋ）、及びハッシュ関数に基づいて、第１コミットメント情報（ｄ1）を生成する手段、
前記確認者の公開鍵情報（ｙC）、第２乱数情報（ｋ）に基づいて、第２コミットメント情報（ｄ2）を生成する手段、
前記第１及び第２コミットメント情報（ｄ1，ｄ2）、前記第１リング要素関連情報（Ｔｉ）及びハッシュ関数に基づいて、リング要素情報（ｃi+1、但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする）を生成する手段、
前記他のユーザに関するメンバ乱数情報（ｓｊ）をランダムに生成する手段、
前記他のユーザの公開鍵情報（ｙj）、前記メンバ乱数情報（ｓｊ）、及びリング要素情報に基づいて、第２リング要素関連情報（Ｔｊ）を生成する手段、
前記第１及び第２コミットメント情報（ｄ1，ｄ2）、前記第２リング要素関連情報（Ｔｊ）及びハッシュ関数に基づいて、リング要素情報（ｃj+1、但し j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）を生成する手段、
前記署名者の秘密鍵情報（ｘi）及び署名者に対応するリング要素情報（ｃi）に基づいて、署名者関連情報（ｓi）を生成する手段、
１番目のリング要素情報（ｃ1）、前記署名者関連情報（ｓj）、前記メンバ乱数情報（ｓj）、前記第１及び第２コミットメント情報（ｄ1，ｄ2）を含むリング署名｛σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）｝を生成する手段、
として機能させるためのプログラム。
【請求項９】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・や、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)が記憶される記憶装置を有し、この記憶装置を参照しつつ、前記署名者が選択した他の複数のユーザの公開鍵情報ｙj（但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCを用いて、任意のデジタル情報ｍに対するリング署名を生成するデジタル署名装置に用いられるプログラムであって、
前記デジタル署名装置のコンピュータを、
前記システムパラメータｇ及び第１乱数情報αに基づいて、式 Ｔi ＝ ｇα mod ｐ により、第１リング要素関連情報Ｔiを生成する手段、
前記システムパラメータｇ、前記デジタル情報ｍ、第２乱数情報ｋ及びハッシュ関数ｈqに基づいて、式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ により（但し、_は下付文字を表す）、第１コミットメント情報ｄ1を生成する手段、
前記確認者の公開鍵情報ｙC及び前記第２乱数情報ｋに基づいて、式 ｄ2 ＝ yCｋ mod ｐ により、第２コミットメント情報ｄ2を生成する手段、
前記第１及び第２コミットメント情報ｄ1，ｄ2、前記第１リング要素関連情報Ｔｉ及びハッシュ関数ｈに基づいて、式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi) により、リング要素情報ｃi+1 を生成する手段（但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
前記他のユーザに関するメンバ乱数情報ｓｊをランダムに生成する手段、
前記システムパラメータｇ、前記他のユーザの公開鍵情報ｙj、前記メンバ乱数情報ｓｊ及びリング要素情報ｃjに基づいて、式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ により、第２リング要素関連情報Ｔｊを生成する手段、
前記第１及び第２コミットメント情報ｄ1，ｄ2、前記第２リング要素関連情報Ｔｊ及びハッシュ関数ｈに基づいて、式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj) により、リング要素情報ｃj+1 を生成する手段（但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
前記第１乱数情報α、前記署名者の秘密鍵情報ｘi及び署名者に対応するリング要素情報ｃiに基づいて、式 ｓi ＝ α − ｘiｃi mod ｑ により、署名者関連情報ｓiを生成する手段、
１番目のリング要素情報ｃ1、前記署名者関連情報ｓi、前記メンバ乱数情報ｓj、前記第１及び第２コミットメント情報ｄ1，ｄ2を含むリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）を生成する手段、
として機能させるためのプログラム。
【請求項１０】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて生成された任意のデジタル情報（ｍ）に対するリング署名に関し、予め記憶装置に記憶された前記確認者の公開鍵情報に対応する秘密鍵情報（ｘC）に基づいて、当該リング署名を検証する確認者用署名検証装置に用いられるプログラムであって、
前記確認者用署名検証装置のコンピュータを、
前記リング署名を検証する際に、前記確認者の公開鍵情報（ｙC）、前記記憶装置内の前記秘密鍵情報（ｘC）及び前記デジタル情報（ｍ）に基づいて、当該リング署名を検証する第１検証手段、
前記リング署名を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び前記他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１１】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・を用いると共に、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj、（但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCや第１乱数情報α、第２乱数情報ｋ、ハッシュ関数ｈ，ｈｑ及び前記他のユーザに関するメンバ乱数情報ｓｊを用いて任意のデジタル情報ｍに対し、以下のＡ式乃至Ｇ式：
Ａ式 Ｔi ＝ ｇα mod ｐ,
Ｂ式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ, （但し、_は下付文字を表す）、
Ｃ式 ｄ2 ＝ yCｋ mod ｐ,
Ｄ式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi), （但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
Ｅ式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ,
Ｆ式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj), （但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
Ｇ式 ｓi ＝ α − ｘiｃi mod ｑ,
の計算により生成されたリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）に関し、当該リング署名σ（ｍ）を検証する確認者用署名検証装置に用いられるプログラムであって、
前記確認者用署名検証装置のコンピュータを、
前記リング署名σ（ｍ）を検証する際に、前記確認者の公開鍵情報ｙC及びこの公開鍵情報に対応する秘密鍵情報ｘCが記憶された記憶装置を参照しつつ、前記デジタル情報ｍ及び前記ハッシュ関数ｈqに基づいて、式 ｄ1{ｘ_C} ／ ｄ2 ＝ ｙC{{h_q}(m)} が成り立つことにより、当該リング署名σ（ｍ）を検証する第１検証手段、
前記リング署名σ（ｍ）を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報ｙi及び前記他の複数のユーザの公開鍵情報ｙjからなる各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙnに基づいて、当該各ユーザに関してＪ＝ 1, ・・・ , i, ・・・ , n まで（但し、Ｊは j, i を読み替えた添字）以下のＨ式及びＩ式：
Ｈ式 ＴJ ＝ ｇ{s_J}ｙJ{c_J} mod ｐ,
Ｉ式 cJ+1 = h(ｄ1‖ｄ2‖ＴJ)
を繰り返し、このＩ式の結果からｃ1＝ｃn+1が成り立つことにより、当該リング署名σ（ｍ）を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１２】
署名者としてのユーザに固有の秘密鍵情報（ｘi）及び前記署名者が選択した他の複数のユーザの公開鍵情報（ｙj、但しj = 1, ・・・ , i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報（ｙC）を用いて生成された任意のデジタル情報（ｍ）に対するリング署名に関し、当該リング署名を検証する検証者用署名検証装置に用いられるプログラムであって、
前記検証者用署名検証装置のコンピュータを、
前記リング署名を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報（ｙi）及び前記他の複数のユーザの公開鍵情報（ｙj）からなる各ユーザの公開鍵情報（ｙ1, ・・・ , ｙi, ・・・ , ｙn）に基づいて、当該リング署名を検証する第１検証手段、
前記リング署名を検証する際に、前記確認者の公開鍵情報（ｙC）に基づき、前記確認者の確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１３】
公開されているシステムパラメータｇ、素数ｐ，ｑ及び各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙn, ｙC, ・・・を用いると共に、署名者としてのユーザに固有の秘密鍵情報ｘi＝logｇ(ｙi)及び前記署名者が選択した他の複数のユーザの公開鍵情報ｙj（但しj = 1, ・・・ ,i-1, i+1, ・・・, n）及び前記署名者が指名した確認者の公開鍵情報ｙCや第１乱数情報α、第２乱数情報ｋ、ハッシュ関数ｈ，ｈｑ及び前記他のユーザに関するメンバ乱数情報ｓｊを用いて以下のＡ式乃至Ｇ式：
Ａ式 Ｔi ＝ ｇα mod ｐ,
Ｂ式 ｄ1 ＝ ｇ{k+h_q(m)} mod ｐ, （但し、_は下付文字を表す）、
Ｃ式 ｄ2 ＝ yCｋ mod ｐ,
Ｄ式 ｃi+1 = h(ｄ1‖ｄ2‖Ｔi), （但し、i = n の場合、ｃi+1＝ｃ{(i+1) mod n}とする。また、‖はデータの連結を表す）、
Ｅ式 Ｔj ＝ ｇ{s_j}ｙj{c_j} mod ｐ,
Ｆ式 cj+1 ＝ h(ｄ1‖ｄ2‖Ｔj), （但し、j = n の場合、ｃj+1＝ｃ{(j+1) mod n}とする）、
Ｇ式 ｓi ＝ α − ｘiｃi mod ｑ,
の計算により生成されたリング署名σ（ｍ）＝（ｃ1，ｓ1, ・・・ , ｓn，ｄ1，ｄ2）に関し、当該リング署名σ（ｍ）を検証する検証者用署名検証装置に用いられるプログラムであって、
前記検証者用署名検証装置のコンピュータを、
前記リング署名σ（ｍ）を検証する際に、前記署名者の秘密鍵情報に対応する公開鍵情報ｙi及び前記他の複数のユーザの公開鍵情報ｙjからなる各ユーザの公開鍵情報ｙ1, ・・・ , ｙi, ・・・ , ｙnが記憶された記憶装置を参照しつつ、当該各ユーザに関してＪ＝ 1, ・・・ , i, ・・・ , n まで（但し、Ｊは j, i を読み替えた添字）以下のＨ式及びＩ式：
Ｈ式 ＴJ ＝ ｇ{s_J}ｙj{c_J} mod ｐ,
Ｉ式 cJ+1 = h(ｄ1‖ｄ2‖ＴJ)
を繰り返し、このＩ式の結果からｃ1＝ｃn+1が成り立つことにより、当該リング署名σ（ｍ）を検証する第１検証手段、
前記リング署名σ（ｍ）を検証する際に、前記確認者の公開鍵情報ｙCに基づき、前記確認者の確認者用署名検証装置との間の対話証明を介して、式 logｇ(ｙC) = log{d_1}（ｄ2ｙC{{h_q}(m)}） が成り立つことにより、当該リング署名σ（ｍ）を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させ、
前記第２検証手段は、
第３及び第４乱数情報ｕ，ｖを生成する手段と、
前記システムパラメータｇ、前記第３及び第４乱数情報ｕ，ｖに基づいて、式 ａ ＝ ｇｕｙCｖ により、コミットメント情報ａを計算する手段と、
このコミットメント情報ａを前記確認者用署名検証装置に送信する手段と、
前記確認者用署名検証装置から第１演算パラメータｒ1, ｒ2, {{\tilde r}_1}, {{\tilde r}_2}を受信する手段（但し、\tildeは波形ダッシュ符号を表す、ｒ1 = ｇt, ｒ2 = ｄ1t, {{\tilde r}_1} ＝ ｇ{\tilde t}, {{\tilde r}_2} ＝ ｄ1{\tilde t} 、ｔは第５乱数情報、\tilde tは第６乱数情報）と、
前記第１演算パラメータｒ1, ｒ2, {{\tilde r}_1}, {{\tilde r}_2}を受信すると、前記第３及び第４乱数情報ｕ，ｖを前記確認者用署名検証装置に送信することにより、前記コミットメント情報ａを開示する手段と、
前記コミットメント情報ａが前記確認者用署名検証装置により式ａ＝ｇｕｙCｖに基づいて検証されたとき、前記確認者用署名検証装置から第２演算パラメータｓ, {\tilde s}を受信する手段（但し、ｓ ＝ ｔ −（ｖ＋ｗ）ｘC、 {\tilde s} ＝ {\tilde t}−（ｖ＋ｗ）ｔ、ｗは第７乱数情報）と、
前記第２演算パラメータｓ, {\tilde s}を受信すると、以下のＪ式乃至Ｌ式：
Ｊ式 ｇｓｙC(v+w) ＝ ｒ1,
Ｋ式 ｇ{\tilde s}ｒ1{v+w} ＝ {\tilde r}_1,
Ｌ式 ｄ1{\tilde s}ｒ2{v+w} ＝ {\tilde r}_2
を確認する手段と、
前記確認に加え、式 ｄ1ｓ(ｄ2ｙC{{h_q}(m)}){v+w} ＝ ｒ2 を検査することにより、式 logｇ(ｙC) = log{d_1}（ｄ2ｙC{{h_q}(m)}）であることを間接的に検証する手段と、
を含んでいることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００６−２０３８２６（Ｐ２００６−２０３８２６Ａ）
【公開日】平成１８年８月３日（２００６．８．３）
【国際特許分類】
【出願番号】特願２００５−１６１４５（Ｐ２００５−１６１４５）
【出願日】平成１７年１月２４日（２００５．１．２４）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成１８年８月３日（２００６．８．３）
【国際特許分類】
【出願日】平成１７年１月２４日（２００５．１．２４）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]