デジタル署名システム、装置及びプログラム
【課題】リング署名の利用・検証を署名者が希望する範囲のみで行うように確実に制限する。
【解決手段】署名者が匿名性を持ちながら、検証者(確認者)を指定できる手段と、確認者が、他人の署名を元にしていない正しい手順で作られた署名であるか、また、署名が正当であるかを検証できる手段を備えた確認者署名検証装置（２０）を備える。
【解決手段】署名者が匿名性を持ちながら、検証者(確認者)を指定できる手段と、確認者が、他人の署名を元にしていない正しい手順で作られた署名であるか、また、署名が正当であるかを検証できる手段を備えた確認者署名検証装置（２０）を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル署名方式の一種のリング署名方式を用いるデジタル署名システム、装置及びプログラムに係り、例えばリング署名の利用・検証を、署名者が希望する範囲のみで行うように確実に制限し得るデジタル署名システム、装置及びプログラムに関する。
【背景技術】
【０００２】
デジタル署名方式の一種として、従来からリング署名方式が知られている。リング署名方式とは、以下の性質をもつデジタル署名方式である。
第１は、署名者がメンバを任意にＮ人選んで生成したグループの代表として署名を生成することが可能であるという性質である。
【０００３】
第２は、Ｎ人に含まれているユーザを含めた任意の検証者はＮ人のうちの１人が署名した事実は検証可能だが、どの１人が署名者であるかを特定するのが困難な性質である。
【０００４】
また、リング署名とは異なる種類のデジタル署名として、従来から指名確認者署名方式が知られている。指名確認者署名方式とは、以下の性質を持つデジタル署名方式である。
【０００５】
第１は、署名者が任意に選んだユーザを確認者として指名し、その確認者は、署名の正当性を検証でき、それ以外のユーザは署名の正当性を検証できないという性質である。
【０００６】
第２は、署名者に確認者として指名されていないユーザは一人では署名の正当性を検証できないが、署名者に確認者として指名されているユーザと指名されていないユーザが対話的に証明をすることによって、指名されていないユーザも署名の正当性を確認することができるという性質である。
【０００７】
以上のようなリング署名方式及び指名確認者署名に関連する他の先行技術文献情報としては、後で引用する非特許文献１−３などがある。
【０００８】
だが、リング署名には、署名者が匿名性を持つ反面、署名の検証者が制限されないという不都合があり、一方、指名確認者署名には、署名を検証可能な者を確認者または確認者が対話する検証者に制限できる反面、署名者の匿名性が無いという不都合がある。このような実情を考慮し、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限し得る技術が特許文献１に開示されている。
【０００９】
また、暗号化するメッセージを知っていなければ、暗号文を作れない頑強性という性質をもつ暗号方式として、クラマー・シャウプ暗号と呼ばれる方式が非特許文献４に開示されている。
【非特許文献１】Ｍ．阿部、Ｍ．大久保、Ｋ．鈴木（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）、ｐｐ.２３１−２４４、１９９７年
【非特許文献４】Ｒ．クラマー、Ｖ．シャウプ（R. Cramer, V.Shoup）著、「ア・プラクティカル・パブリック・キー・クリプトシステム・プロバブリー・セキュア・アゲインスト・アダプティブ・チョーズン・サイファテキスト・アタック（A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack)」、クリプト’９８（CRYPTO'98） ＬＮＣＳ １４６２， ｐｐ. １３−２５、１９９８年
【特許文献１】特開２００６−２０３８２６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら特許文献１の方式では、他人の署名の一部を元にして、新たに生成した自身の署名に対して対話的検証を行うことにより、元にした他人の署名の正当性を同時に検証可能となってしまう。これにより指名確認者や元の署名者が意図しない署名の正当性を第三者が知り得るという問題がある。
【００１１】
以下、この問題を具体的に説明する。
対象となる平文mに対する署名のコミットメントをd1＝g^(k + Hq(m‖L)) mod p, d2＝yc^k mod pとする。このm, d1, d2を用いて、次のd1’，d2’を計算する。
【００１２】
d1’＝d1・g^(k’ + Hq(m’‖L) - Hq(m‖L)) mod p,
d2’＝d2・yc^k’ mod p
但し、k’は乱数、m’は任意の平文。
【００１３】
このとき、d1’＝g^{(k+k’) + Hq(m’‖L)} mod p, d2’＝yc^(k+k’) mod pであるから、d1’，d2’は、m’に対する正しいコミットメントである。このため、コミットメントとしてd1’，d2’を用いたm’に対する署名を生成して対話的署名検証を行うことで、検証に成功すれば対象の署名も正当であり、検証に失敗すれば対象の署名も不正であると判断できる。これにより、対象とする署名について対話的署名検証を行わずに、その署名検証が可能となってしまう。
【００１４】
つまり、本来ならば署名者が指定した確認者と、確認者が許可した検証者に対してのみその署名の正当性を示すべきであるにもかかわらず、間接的に、署名生成可能な第三者が、知りたいと思う署名の正当性を確認することができてしまう。
【００１５】
本発明は上記実情を考慮してなされたもので、リング署名の利用・検証を、署名者が希望する範囲のみで行うように確実に制限し得るデジタル署名システム、装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の一局面は、署名者としてのユーザに固有の秘密鍵情報（ｘ_i）及びこの署名者を含み当該署名者が選択した他の複数ユーザの公開鍵情報（y_1, y_2, … ｙ_n）及び署名者が指名した確認者の複数の公開鍵情報（ｃ_C，ｄ_C，ｈ_C）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置と、前記リング署名を検証する際に、前記確認者の複数の公開鍵情報に対応する複数の秘密鍵情報（ｘ_C１，ｘ_C２，ｙ_C１，ｙ_C２，ｓ_C）に基づいて、当該リング署名を検証する確認者用署名検証装置と、前記リング署名を検証する際に、前記確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置とを備えたデジタル署名システムである。
【００１７】
なお、本発明の一局面は、各装置からなる全体構成を「システム」として表現したが、これに限らず、全体構成又は各装置を「装置」、「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」として表現してもよい。
【００１８】
（作用）
本発明の一局面は、署名者としてのユーザに固有の秘密情報（ｘ_i）及びこの署名者を含み当該署名者が選択した他の複数のユーザの公開鍵情報（y_1, y_2, … ｙ_n）及び署名者が指名した確認者の公開鍵情報（ｃ_C，ｄ_C，ｈ_C）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成する。
【００１９】
これにより、署名者は、リング署名に含めたい他のユーザとの事前やりとり無しで他のユーザの公開鍵情報を任意に選ぶことができ、リング署名からは各ユーザのうちの誰が署名したかが検証者には全くわからないという特徴を持ったリング署名を生成できる。
【００２０】
これに加え、署名者が署名時に指名した特定の確認者だけが検証でき、それ以外の検証者は一人では署名の正当性を検証できないが、先述の特定の確認者と対話を行うことで特定の確認者以外の検証者も署名の正当性を知ることができる署名を生成できる。
【００２１】
更に、過去に別の署名者が生成した署名情報の一部を使って、不正に新たな署名を生成した場合、署名検証に失敗することにより、リング署名の利用・検証を、署名者が希望する範囲のみで行うように確実に制限することができる。
【発明の効果】
【００２２】
以上説明したように本発明によれば、リング署名の利用・検証を、署名者が希望する範囲のみで確実に行うように制限できる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の一実施形態について図面を用いて説明するが、その前に、本発明の実施形態に関連するクラマー・シャウプ暗号の概要を述べる（詳細は非特許文献４参照。）。
【００２４】
［公開鍵・秘密鍵ペア生成］
公開パラメータとして素数位数qの乗法巡回群Gとその生成元g_1と汎用一方向性ハッシュ関数を入力とし、以下の処理を行う。
【００２５】
（１）g_1, g_2 ∈ G をランダムに選択する。
（２）x_1, x_2, y_1, y_2, z ∈ Z_qをランダムに選択する。
（３）c＝g_1＾｛x_1｝g_2＾｛x_2｝, d＝g_1＾｛y_1｝g_2＾｛y_2｝, h＝g_1＾zを計算する。
（４）ハッシュ関数Ｈを汎用一方向性ハッシュ関数の集合から選択する。
（５）公開鍵（g_1, g_2, c, d, h, H)、秘密鍵（x_1, x_2, y_1, y_2, z）を出力する。
【００２６】
［暗号化］
公開鍵（g_1, g_2, c, d, h, H）、メッセージm ∈ Gを入力とし、以下の処理を行う。
【００２７】
（１）r ∈ Z_qをランダムに選択する。
（２）u_1 ＝ g_1＾r, u_2 ＝ g_2＾r, e＝h＾{r}・mを計算する。
（３）α＝Ｈ（u_1, u_2, e）を計算する。
（４）v ＝ c＾r・d＾{rα}を計算する。
（５）暗号文（u_1, u_2, e, v）を出力する。
【００２８】
［復号］
暗号文（u_1, u_2, e, v）を入力とし、以下の処理を行う。
【００２９】
（１）α＝H（u_1, u_2, e）を計算する。
（２）u_1＾｛x_1＋y_1・α｝u_2＾｛x_2＋y_2・α｝＝ Vが成り立つか否かを検証し、否の場合には無効な暗号文として拒絶して処理を終了する。
（３）m ＝ e／{u_1＾z}を計算し、平文として出力する。
以上がクラマー・シャウプ暗号の概要である。
【００３０】
続いて、本発明の一実施形態について説明する。
（１． 本発明の実施形態の概要）
図７は本発明の実施形態方式の概略を示す模式図である。本実施形態方式は、過去に別の署名者が生成した署名情報の一部を使って、不正に新たな署名を生成しようとしても、確認者Cの検証に失敗する。そのため、署名検証は、署名者が信用する確認者が決めた範囲でのみ確実に行われる。
【００３１】
（１．１ 準備）
符号Gをグループメンバの集合とする。U_j （j ＝ 1，…，n）をメンバ集合Ｇに属するメンバ、U_iを署名者とする。符号Cを、署名者に指定された確認者とする。符号Vを、権限の無い一般の検証者とする。
【００３２】
ここで、q｜p-1を満たす大きな素数をp,qとする。位数がqであるpの部分群の生成元をg、g_1、g_２とする（但し、下線_の右側は下付添字を表す）。メンバU_jはｘ_j∈Z_qを秘密鍵、ｙ_j＝g^{ｘ_j} mod pとし、公開鍵y_jを公開する（但し、 ^ は、べき乗を表す）。さらに、確認者の秘密鍵をx_C1、x_C2、y_C1、y_C2、s_C ∈Z_q、公開鍵をc_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod pとする。また、符号H：｛0, 1｝^＊→｛0, 1｝^ｌ，H_q：｛0, 1｝^＊→Z_qを衝突困難性ハッシュ関数とする。更に、符号Lを署名者U_iが任意に選んだユーザグループの公開鍵リストとし、ここでは簡単のためにL＝｛y_1, y_2, ・・・, y_n｝に固定する。
【００３３】
（１．２ 署名生成）
署名者Ｕiは、以下の手順により平文mに対する指名確認者リング署名σを生成する。
【００３４】
(1) 平文m、公開鍵暗号リストLに対して、クラマー・シャウプ暗号を変形したコミットメントCC ＝ (u_1, u_2, e, v)を下式により計算する。但し、r ∈Z_qとする。
【００３５】
u_1 = g_1＾r mod p,
u_2 = g_2＾r mod p,
e =h_C＾ｒ・g_1＾Hｑ(m‖L),
b =H_ｑ(u_1‖u_2‖e),
v =c_C＾r・d_C＾rb mod p
(2) T_i = g^α mod p、 c_{i+1} = H(CC‖T_i)を計算する。但し、α∈Z_q。
【００３６】
(3) j = i+1, . . . , n, 1, . . . , i-1について、
T_j = g^s_j・ y_j^c_j mod p,
c_{j+1} mod n = H(CC‖T_j)
を順次計算する。但し、s_j ∈ Z_q。
【００３７】
(4) 秘密鍵x_iを用いてs_i = α−x_i・c_i mod qを計算し、
署名σ = (c_1, s_1, . . . , s_n, CC, L)を出力する。
【００３８】
（１．３ 署名検証）
確認者Cは、以下の手順により、平文mに対する署名σ = (c_1, s_1, . . . , s_n, CC, L)の正当性を検証する。
【００３９】
(1) まずb = H_{q}(u_1‖u_2‖e)を計算し、次に下式が成り立つことをそれぞれ検証する(コミットメントの正当性検証)。
【００４０】
v =u_1＾(x_{c1}+by_{c1})・u2＾(x_{c2}+by_{c2}) mod p,
g＾{H_{q}(m‖L)} = e/{ u_ 1}＾(s_c) mod p.
(2) j = 1, . . . , nについてT_j = g＾s_j・ y_j＾c_j mod p、c_(j+１) = H(CC‖T_j)を順次計算し，c_1 = c_(n+1)となることを検証する(コミットメントに対するリング署名の正当性検証)。
【００４１】
(1)(2) 両方の検証が成功した場合のみ署名検証成功とする。
【００４２】
（１．４ 対話的署名検証）
検証者Vは、以下の確認者Cとの対話により、平文mに対する署名σ = (c_1， s_1， . . . ， s_n，CC，L)の正当性を検証する。
【００４３】
(1) 検証者Vは，j = 1, . . . , nについてT_j =g＾s_j・ y_j＾c_j mod p、 c_{j+1}= H(CC‖T_j)を順次計算し，c_1=c_{n+1}となることを検証する。成り立たない場合は署名検証失敗とする(コミットメントに対するリング署名の正当性検証)。
【００４４】
(2) 検証者Vは、乱数α_1、 β_1 ∈Z_qを生成し、
a_1 = g_1＾α_1・c_C＾β_1 mod p,
を計算して確認者Cへ送る。
【００４５】
(3) 確認者Cは、乱数k_1、 k_2、 k_3、 k_4、 k_5、〜k_1、 〜k_2、 〜k_3、 〜k_4、〜k_5、w ∈Z_qを選び、以下のk_1、 k_2、 k_3、 k_4、k_5、 〜k_1、 〜k_2、 〜k_3、 〜k_4、〜k_5、wを(mod p 上で) 計算して検証者Vへ送る。
【００４６】
r_1 = (g_1＾k_1）(g_2＾k_2）、
r_2 = (g_1＾k_3）(g_2＾k_4）、
r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、
r_4 = g_1＾k_5、r_5 = u_1＾k_5、
〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、
〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、
〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、
〜r_4 = (u_１)＾(〜k_5)、
〜r_5 = e＾(〜k_5)
(4) 検証者Vは、α_1, β_1を確認者Cへ送る。
【００４７】
(5) 確認者Cは、a_1=g_1^α_1・c_C＾β_1 mod p が成り立つかを検証し、成り立たない場合はプロトコルを終了する。成り立つ場合は、以下のs_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5,を(mod q 上で) 計算して、検証者Vに送る。
【００４８】
s_c1 = k_1 − (β_1 + w)・x_{c1},
s_c2 = k_2 - (β_1 + w)・x_{c2},
s_c3 = k_3 - (β_1 + w)・y_{c1},
s_c4 = k_4 - (β_1 + w)・y_{c2},
s_c5 = k_5 - (β_1 + w)・s_c,
〜s_c1 = 〜k_1 − (β_1 + w)・k_1,
〜s_c2 = 〜k_2 - (β_1 + w)・k_2,
〜s_c3 = 〜k_3 - (β_1 + w)・k_3,
〜s_c4 = 〜k_4 - (β_1 + w)・k_4,
〜s_c5 = 〜k_5 - (β_1 + w)・k_5.
(6) 検証者Vは、下式を(mod p 上で) 計算する。
【００４９】
r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) ,
r_2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) ,
r_4 = g_1＾{s_c5}・h_C＾(β_1 + w),
〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ},
〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ},
〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ},
〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},
〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}
上記の式がすべて成り立つことを確認した後、
r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},
r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}
の２つの式が両方成り立てば検証成功、どちらか１つでも成り立たなければ検証失敗となる。
【００５０】
（２． 安全性）
特許文献１の方式では、他人の署名の一部を元にして、新たに生成した自身の署名に対して対話的検証を行うことにより、元にした他人の署名の正当性を同時に検証可能となってしまう。これにより指名確認者や元の署名者が意図しない署名の正当性を第三者が知り得るという問題があった。本実施形態方式は、この問題に直接関係する署名の不可視性(Invisibility of Signature)を再定義しその定義を満たすことを示す。また、その他の安全性の定義も示す。
【００５１】
以下は、安全な指名確認者リング署名が満たす条件を示し、本実施形態方式がこれらの条件（i）〜（vi）を満たしていることを証明する。
【００５２】
（i）署名の完全性（Completeness of Signature）
署名者が正しい動作をした場合には、確認者が検証可能な署名を構成できること。
【００５３】
（ii）署名の偽造不可能性（Unforgeability of Signature）
リング署名を構成するグループのメンバ以外が署名を偽造できないこと。
【００５４】
（iii）署名者の曖昧性（Signer Ambiguity）
署名の情報から署名者の情報が漏れないこと。
【００５５】
（iv）署名の不可視性（Invisibility of Signature）
敵Aは、全ての公開情報を得られるとともに、確認者C 以外の全てのユーザと結託することができる。また敵Aは、任意の署名について確認者オラクルOcを用いて対話的署名検証を行うことができる。Ａは、これら試行の後、二つの平文m_b (b∈{0, 1})と署名者U_i，公開鍵リストLを決定し、テストオラクルπに入力する，テストオラクルπは、ランダムにb∈{0, 1}を選択し、署名σ = Sig(m_b, x_i, L, y_C)をAに返す。その後、Aは再びOcにアクセスできるが、σについて尋ねることはできないこととする。最後に敵Aはb’∈{0, 1}を出力する。b’ = bのとき敵Aは攻撃に成功したといい、この成功確率が無視できるほど小さいとき、指名確認者リング署名方式は，署名の不可視性(Invisibility of Signature)を持つ。
【００５６】
（ｖ）検証の一貫性（Consistency of Verification）
確認者Ｃや検証者Ｖが正しい動作をした場合は、正しく検証ができること。
【００５７】
（vi）検証の非伝達性（Non-transferability of Verification）
確認者Ｃの秘密鍵に関する情報が対話証明において、検証者Ｖにほとんど漏れないこと。
【００５８】
本実施形態方式は、以上の要求条件に対して以下の定理が成り立つ。
【００５９】
（定理１：署名の完全性）
正しい秘密鍵をもつ署名者U_iがアルゴリズムに従い生成したリング署名は、確認者Cの署名検証に常に成功する。
証明：プロトコルから明らかである。
【００６０】
（定理２：署名の偽造不可能性）
本実施形態方式は、ランダムオラクルモデルと離散対数問題の困難性を仮定すると、グループメンバ以外の任意の敵が署名の偽造に成功する確率は無視できるほど小さい。
【００６１】
証明（Sketch）:本実施形態方式が偽造可能であると仮定すると、非特許文献１により提案されたリング署名を偽造可能な敵を構成することができる。
【００６２】
（定理３：署名者の曖昧性）
任意のメッセージに対するリング署名から署名者を特定できる確率は１／ｎである。
【００６３】
証明（Sketch）：s_iを除くs_jはZ_qから一様にランダムに選ばれ、s_iはαがZ_q上から一様にランダムに選ばれるので、s_iもZ_q上に一様に分布する。また、CC = (u_1, u_2, e, v)はメンバ公開鍵には関係しない。従って、グループメンバとメッセージmを固定すると、（s_1, …, s_n, (u_1, u_2, e, v)）は、署名者が誰であるかに関わらず、同様にｎｑのバリエーションをもつ。残りのｃ_1は、グループメンバのリスト、メッセージm及び（s_1, …, s_n, (u_1, u_2, e, v)）より一意に決定できる。よって、署名者を特定できる確率は１／ｎである。
【００６４】
（定理４：署名の不可視性）
本実施形態方式は、ＤＤＨ(decisional Diffie-Hellman)仮定のもとで、署名の不可視性(Invisibility of Signature)を持つ。
【００６５】
証明（Sketch）：本実施形態方式の署名の不可視性を無視できない確率で破る敵Aを利用して、クラマー・シャウプ暗号の適応的選択暗号文攻撃に対する識別不可能性（Indistinguishability）を破る敵Bを構成する。Bへの入力である公開パラメータ(p, q, g_1, g_2, H_q) および公開鍵(c, d, h)を本実施形態方式の公開パラメータおよび確認者Cの公開鍵(c_C, d_C, h_C)として敵Aに入力し、各ユーザの鍵ペアはランダムに生成して入力する。また、対話的署名検証オラクルOCのシミュレートには，ゼロ知識対話証明（zero-knowledge bi-proof）のシミュレータを用いればよい。
【００６６】
敵Aが出力した平文m_a (a∈{0, 1})と公開鍵リストLに対して、〜m_a = g_1＾H(m_a‖L) (a∈{0, 1})を計算してテストオラクルπへ送る。テストオラクルπから送り返された暗号文Enc( 〜m_a)を用いて署名σ = (c_1, s_1, . . . , s_n, Enc( 〜m_a), L)を生成し，敵Aに入力する。最終的に、敵Aが出力したa’を敵Bの出力とする。
【００６７】
ゼロ知識対話証明のシミュレートの失敗確率はクエリー（query）の回数(多項式回) で抑えられる。また、コミットメント(暗号文)を識別することなく署名の不可視性を破れる確率はランダムしかありえないため無視できる。よって、敵Aが有意な確率で本実施形態方式の署名の不可視性を破れるならば、敵Bは有意な確率でクラマー・シャウプ暗号の識別不可能性を破ることができる。クラマー・シャウプ暗号はＤＤＨ仮定のもとで適応的選択暗号文攻撃に対して識別不可能（Indistinguishable）であることから、本実施形態方式はＤＤＨ仮定のもとで署名の不可視性を持つと言える。
【００６８】
補足説明：なお、ＤＤＨ仮定とはＤＤＨ問題を解くことが困難であるという仮定である。ここで、ＤＤＨ問題について説明する。素数位数ｑの乗法巡回群をＧとする。ランダムな４つ組（g_1, g_2, u_1, u_2）∈Ｇ４の分布をＲとする。g_1, g_2 ∈ Ｇとr ∈ Z_qとをランダムに選び、u_1 ＝ g_1^r、u_2 ＝ g_2^rとした４つ組（g_1, g_2, u_1, u_2）∈Ｇ４の分布をＤとする。このとき、任意に与えられた４つ組（g_1, g_2, u_1, u_2）が分布Ｒ，Ｄのいずれに属するかを見分ける問題をＤＤＨ問題と呼ぶ。上述した本実施形態方式の署名の不可視性は、ＤＤＨ問題の困難性（ＤＤＨ仮定）に帰着される。
【００６９】
（定理５：検証の一貫性）
確認者Ｃと検証者Ｖの間で行われるリング署名検証プロトコルにおいて、正しいリング署名が検証に失敗する確率及び不正なリング署名が検証に成功する確率は任意の確認者Ｃに対して無視できる。
【００７０】
（定理６：検証の非伝達性）
確認者Ｃと検証者Ｖの間で行われるリング署名検証プロトコルは、最小知識対話証明（minimum knowledge bi-proof）である（非特許文献２参照）。
【００７１】
証明（定理５，６）：本実施形態方式は、非特許文献３に記載の対話証明システム（bi-proof system）を応用している。対話証明システムの完全性（completeness）、安定性（Soundness）、零知識証明性（Zero-Knowledgeness）は、非特許文献３によって証明されており、この性質から一貫性、非伝達性は明らかである。これは本実施形態方式でも成り立つ。
【００７２】
以上が本発明の実施形態方式の概要である。続いて、本発明の一実施形態について具体的に説明する。
【００７３】
（一実施形態）
図１は本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図であり、図２は図１における情報の流れを示す模式図である。このシステムは、複数のユーザ端末１０及び各１台のユーザ端末２０，３０を備えている。各ユーザ端末１０，２０，３０は、コンピュータにより実現される場合、それぞれ各端末１０，２０，３０の機能を実現するためのプログラムが予め記憶媒体又はネットワークから各端末のコンピュータにインストールされて実現される。
【００７４】
ユーザ端末は、ユーザ端末１０，２０，３０に分類される。
複数のユーザ端末１０は、署名者としてのユーザｕのユーザ端末１０と、リング署名に用いられるグループメンバとしての各ユーザｋ，…のユーザ端末１０，…とを含む。
【００７５】
各ユーザ端末１０は、秘密鍵記憶装置１１及び署名生成部１２を備えている。
【００７６】
ここで、秘密鍵記憶装置１１は、署名者としてのユーザに固有の秘密鍵情報が記憶されるメモリであり、署名生成部１２から読出可能となっている。
【００７７】
署名生成部１２は、署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_j）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n））と、署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）とに基づいて、任意のデジタル情報（ｍ）に対するリング署名を生成するものであり、具体的には図３及び図４に示すステップＳＴ１２〜ＳＴ１７の処理を実行する機能をもっている。
【００７８】
これらの機能としては、例えば、署名者の秘密鍵情報（ｘ_i）を秘密鍵記憶装置１１に書き込む機能と、デジタル情報（ｍ）、リスト（L）、乱数（r）、確認者の公開鍵情報（c_C, d_C, h_C）及びハッシュ関数（H_{q}( )）に基づいて、コミットメント情報（CC）を計算する機能と、第１乱数情報（α）、コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第１リング要素情報（c_{i+1}）を計算する機能と、ユーザ番号（j = i+1, …, n, 1, …, i-1）毎に、ユーザ乱数情報（s_j）、ユーザ公開鍵情報（y_j）、第１リング要素情報（c_j）、コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第２リング要素情報（c_{j+1} mod n）を順次計算する機能と、第１乱数情報（α）、秘密鍵記憶装置１１内の秘密鍵情報（ｘ_i）及び署名者に対応するリング要素情報（ｃ_i）に基づいて、署名者関連情報（ｓ_i）を生成する機能と、１番目のリング要素情報（ｃ_1）、ユーザ乱数情報（ｓ_j）、署名者関連情報（ｓ_i）、コミットメント情報（CC）及びリスト（L）を含むリング署名（σ = (c_1, s_1, …, s_n, CC, L)）を出力する機能とが含まれる。
【００７９】
署名生成部１２の機能は、詳しくは、署名者の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)を秘密鍵記憶装置１１に書き込む機能と、デジタル情報ｍ、リストL、システムパラメータg_1, g_2、乱数r、確認者の公開鍵情報c_C, d_C, h_C及びハッシュ関数H_{q}( )に基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L), 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p により、コミットメント情報CC ＝ (u_1, u_2, e, v)を計算する機能（但し、‖は連接を表す）と、システムパラメータg、第１乱数情報α、コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_i = g^α mod p 及び式c_{i+1} = H(CC‖T_i)により、第１リング要素情報c_{i+1}を計算する機能と、ユーザ番号j = i+1, …, n, 1, …, i-1毎に、システムパラメータg、ユーザ乱数情報s_j、ユーザ公開鍵情報y_j、第１リング要素情報c_j 、コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g^s_j・ y_j^c_j mod p 及び式c_{j+1} mod n = H(CC‖T_j)により、第２リング要素情報c_{j+1} mod n を順次計算する機能と、第１乱数情報α、秘密鍵記憶装置１１内の秘密鍵情報ｘ_i及び署名者に対応するリング要素情報ｃ_iに基づいて、式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ により、署名者関連情報ｓ_iを生成する機能と、１番目のリング要素情報ｃ_1、ユーザ乱数情報ｓ_j、署名者関連情報ｓ_i、コミットメント情報CC及びリストLを含むリング署名σ = (c_1, s_1, …, s_n, CC, L) を出力する機能とを含んでいる。
【００８０】
ユーザ端末２０は、指定された確認者Ｃとしてのユーザcに操作されるものであり、秘密鍵記憶装置２１、確認者用署名検証部２２及び対話証明部２３を備えている。
【００８１】
秘密鍵記憶装置２１は、確認者としてのユーザに固有の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）が記憶されるメモリであり、確認者用署名検証部２２及び対話証明部２３から読出可能となっている。
【００８２】
確認者用署名検証部２２は、リング署名（σ）を検証する際に、秘密鍵記憶装置２１内の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）に基づいて、リング署名（σ）を検証する第１検証機能と、リスト（Ｌ）内の公開鍵情報（ｙ_j）に基づいて、リング署名（σ）を検証する第２検証機能と、第１及び第２検証手段による検証に合格したとき、リング署名を受理するリング署名受理機能とを有し、具体的には図３及び図５のステップＳＴ２０〜ＳＴ２５に示す処理を実行する機能をもっている。
【００８３】
ここで、第１検証機能としては、例えば、リング署名σを検証する際に、当該リング署名σ内のコミットメント情報CCと、ハッシュ関数H_{q}とに基づいて、式b = H_{q}(u_1‖u_2‖e)により、コミットメント部分情報bを計算する機能と、このコミットメント部分情報b、秘密鍵記憶装置２１内の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C 、コミットメント情報CC 及びシステムパラメータgに基づいて、第１式v =u_1＾(x_{c1}+by_{c1})・u2＾(x_{c2}+by_{c2}) mod p 及び第２式g＾{H_{q}(m‖L)} = e/{ u_ 1}＾(s_c) mod pが成り立つことをそれぞれ検証する機能とが含まれる。
【００８４】
第２検証機能としては、例えば、ユーザ番号j = 1, . . . , n毎に、システムパラメータg、リング署名σ内のユーザ乱数情報s_j、ユーザ公開鍵情報y_j、リング署名σ内の第１リング要素情報c_j 、コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する機能とが含まれる。
【００８５】
対話証明部２３は、検証者用の対話証明部３２による対話証明の際に動作するものであり、図６のステップＳＴ３３，ＳＴ３４，ＳＴ３６〜ＳＴ３８に示す処理を実行する機能をもっている。
【００８６】
対話証明部２３の機能としては、例えば、ユーザ端末３０から値a_1を受けると、値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを計算してユーザ端末３０に送信する機能（但し、ｒ_1 = (g_1＾k_1）(g_2＾k_2）、r_2 = (g_1＾k_3）(g_2＾k_4）、r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、r_4 = g_1＾k_5、r_5 = u_1＾k_5、〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、〜r_4 = (u_１)＾(〜k_5)、〜r_5 = e＾(〜k_5)。ここで、k_1、 k_2、 k_3、 k_4 、 k_5、 〜k_1、 〜k_2、〜 k_3、 〜k_4、 〜k_5、 w ∈Z_q）と、ユーザ端末３０から乱数α_1、 β_1を受けると、式a_1=g_1^α_1・c_C＾β_1 mod pが成り立つことが検証した後、値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5を計算してユーザ端末３０に送信する機能（但し、s_c1 = k_1 − (β_1 + w)・x_{c1}, s_c2 = k_2 - (β_1 + w)・x_{c2}, s_c3 = k_3 - (β_1 + w)・y_{c1}, s_c4 = k_4 - (β_1 + w)・y_{c2}, s_c5 = k_5 - (β_1 + w)・s_c, 〜s_c1 = 〜k_1 − (β_1 + w)・k_1, 〜s_c2 = 〜k_2 - (β_1 + w)・k_2, 〜s_c3 = 〜k_3 - (β_1 + w)・k_3, 〜s_c4 = 〜k_4 - (β_1 + w)・k_4, 〜s_c5 = 〜k_5 - (β_1 + w)・k_5）とを含んでいる。
【００８７】
ユーザ端末３０は、検証者Ｖとしてのユーザｖに操作されるものであり、検証者用署名検証部３１、対話証明部３２及び記憶装置３３を備えている。
【００８８】
検証者用署名検証部３１は、リング署名を検証する際に、記憶装置３３内のリスト（Ｌ）内の公開鍵情報（y_j）に基づいて、リング署名（σ）を検証する第１検証機能と、この第１検証機能及び対話証明部３２の第２検証機能による検証に合格したとき、リング署名を受理するリング署名受理機能とを有し、具体的には図６のステップＳＴ３１，ＳＴ４３〜ＳＴ４５に示す処理を実行する機能をもっている。
【００８９】
ここで、第１検証機能としては、例えば、リング署名σを検証する際に、ユーザ番号j = 1, . . . , n毎に、システムパラメータg、リング署名σ内のユーザ乱数情報s_j、ユーザ公開鍵情報y_j、リング署名σ内の第１リング要素情報c_j 、コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する機能を含んでいる。
【００９０】
対話証明部３２は、記憶装置３３内の確認者の公開鍵情報（c_C, d_C, h_C）に基づき、確認者のユーザ端末２０との間の対話証明を介して、当該リング署名を検証する第２検証機能を有し、具体的には図６のステップＳＴ３２，ＳＴ３５，ＳＴ３９〜ＳＴ４２に示す処理を実行する機能をもっている。
【００９１】
ここで、第２検証機能としては、例えば、乱数α_1、 β_1 を生成すると共に、この乱数α_1, β_1及び記憶装置３３内のシステムパラメータg_1,確認者の公開鍵情報c_Cに基づいて、式a_1 = g_1＾α_1・c_C＾β_1 mod p により計算した値a_1をユーザ端末２０に送信する機能と、ユーザ端末２０から値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを受信する機能（但し、ｒ_1 = (g_1＾k_1）(g_2＾k_2）、r_2 = (g_1＾k_3）(g_2＾k_4）、r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、r_4 = g_1＾k_5、r_5 = u_1＾k_5、〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、〜r_4 = (u_１)＾(〜k_5)、〜r_5 = e＾(〜k_5)。ここで、k_1、 k_2、 k_3、 k_4 、 k_5、 〜k_1、 〜k_2、〜 k_3、 〜k_4、 〜k_5、 w ∈Z_q）と、値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wの受信後、乱数α_1、 β_1をユーザ端末２０に送信する機能と、ユーザ端末２０により式a_1=g_1^α_1・g_2＾β_1 mod pが成り立つことが検証された後、ユーザ端末２０から値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5を受信する機能（但し、s_c1 = k_1 − (β_1 + w)・x_{c1}, s_c2 = k_2 - (β_1 + w)・x_{c2}, s_c3 = k_3 - (β_1 + w)・y_{c1}, s_c4 = k_4 - (β_1 + w)・y_{c2}, s_c5 = k_5 - (β_1 + w)・s_c, 〜s_c1 = 〜k_1 − (β_1 + w)・k_1, 〜s_c2 = 〜k_2 - (β_1 + w)・k_2, 〜s_c3 = 〜k_3 - (β_1 + w)・k_3, 〜s_c4 = 〜k_4 - (β_1 + w)・k_4, 〜s_c5 = 〜k_5 - (β_1 + w)・k_5）と、値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5の受信後、当該値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5、前述した値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、w、記憶装置３３内の公開鍵情報c_C, d_C, h_C、デジタル情報ｍ及びリング署名σ = (c_1, s_1, …, s_n, CC, L)に基づいて、式r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) , 式r_ 2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) , 式r_4 = g_1＾{s_c5}・h_C＾(β_1 + w), 式〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ}, 式〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ}, 式〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ}, 式〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},式〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}の式が成り立つことを確認した後、r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}の２つの式が両方成り立つか、どちらか１つでも成り立たないことを検証する機能とを含んでいる。
【００９２】
記憶装置３３は、システムパラメータg, g_1, g_2及び素数ｐ，ｑと、リストＬ＝｛y_1, y_2, … , y_n｝と、確認者の公開鍵情報c_C, d_C, h_Cと、デジタル情報ｍと、リング署名σとを記憶するためのメモリであり、検証者用署名検証部３１及び対話証明部３２から読出／書込可能となっている。
【００９３】
また前提条件として、公開鍵基盤などにより、公開情報を安全に公開するための手段、例えば公開掲示板サーバ４０などが存在するとする。
【００９４】
公開掲示板サーバ４０は、公開される情報を記憶する公開情報記憶装置４１を有する。この公開掲示板サーバ４０によって実現される情報公開(掲載)手段を公開情報掲示板と呼ぶ。公開情報掲示板は全てのユーザがアクセスでき、かつ改ざんなどの不正が行われないように適切に管理されているとする。また、全てのユーザはインターネットなどのネットワーク５０に接続されているものとする。特に匿名性を必要とする場合は匿名ネットワークに接続されていてもよいが、その限りではない。
【００９５】
次に、以上のように構成されたデジタル署名システムの動作を図３のシーケンス図及び図４乃至図６の各フローチャートを用いて述べる。なお、本実施形態では、例えば、べき乗を＾で表し、下付添字を_で表し、文字の真上の波形符号を〜で表す等というように１行で済む数式表現を用いている。このような明細書中の数式表現は、図面中の数式表現とは異なるが、これらの数式表現が示す数式の内容は一致している。
（準備）：
本実施形態では、前提条件として、ユーザの公開鍵や公開情報は予め公開掲示板サーバ４０により公開されているものとする。公開の方法としては例えば公開鍵基盤などがあるが、ここでは限定しない。
【００９６】
まず、公開掲示板サーバ４０は、素数位数qの巡回群Gとその生成元g, g_1, g_2を選び公開する。ここでは、一例として、q|p-1を満たす十分大きな素数p, qを選び、位数がqとなるZ_p*の部分群をGとし、p, q, g、g_1、g_２を公開するとする。
【００９７】
さらに、公開掲示板サーバ４０は、衝突困難性ハッシュ関数H:{0,1}^*→{0,1}^q, H_q:{0,1}^*→{0,1}^qを任意に選び公開する。
【００９８】
また前提条件に従い各ユーザ端末１０，２０は、それぞれユーザu, k, cの操作により、x_u, x_k, x_c ∈ Z_qをランダムに選び、以下を計算する。なお、記号^はべき乗を表す。
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, σ)を出力する。
【００９９】
ステップＳＴ１２：α,r ∈ Z_qをランダムに選ぶ。
【０１００】
ステップＳＴ１３：衝突困難性ハッシュ関数HとH_qを用いて以下の値を計算する。
u_1 = g_1＾r mod p,
u_2 = g_2＾r mod p,
e = h_C＾r・g_1＾{H_{q}(m‖L)},
b = H_{q}(u_1‖u_2‖e),
v = c_C＾r・d_C＾rb mod p
T_i = g^α mod p,
c_{i+1} = H(u_1‖ u_2 ‖ e ‖ b ‖ v ‖ 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(CC ‖ 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, CC, L)
ステップＳＴ２０：リング署名の確認者による検証（図３、図５）
署名確認者であるユーザcのユーザ端末２０は、署名検証部２２において、メッセージmとmに対するリング署名σのペア(m,σ)及び公開掲示板サーバ４０から取得可能な公開情報ＰＵＢＩを用いて、以下のステップＳＴ２１〜ＳＴ２５の手順でリング署名の正当性とメッセージmに対するコミットメントの正当性を検証する。
【０１０５】
ステップＳＴ２１：リング署名σから、公開情報である衝突困難性ハッシュ関数H_qを用い、以下の値を計算する。
b = H_{q}(u_1 ‖ u_2 ‖e)
ステップＳＴ２２：リング署名σから、確認者の秘密鍵（x_C1, x_C2, y_C1, y_C2, s_C）を用い、以下が成り立つことを検証する。
v = u_1＾(x_{c1}+b・y_{c1})・u_2＾(x_{c2}+b・y_{c2}) mod p
ステップＳＴ２３：メッセージm及びリング署名σから、公開情報である衝突困難性ハッシュ関数H_qを用い、以下が成り立つことを検証する。
【０１０６】
e/{u_ 1}＾(s_c) = g＾{H_{q}(m‖L)} mod p
ステップＳＴ２４：j = 1, ..., nについて、公開情報である衝突困難性ハッシュ関数Hを用いて以下の値を計算する。
T_j = g^{s_j}{y_j}^{c_j} mod p,
c_{j+1} = H(CC‖ 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(CC‖ T_j)
c_1 = c_{n+1}となることを検査することにより、コミットメントに対するリング署名の正当性を検証する。
【０１１０】
ステップＳＴ３２：検証者のユーザ端末３０は、署名情報がlog_{g_1} (h_C) = log_{u_1}(e / {g_1}^{H_{q}(m‖L)}かつlog_{g_1} (c_C){d_C}^b = log_{u_1}vであるかを、以下のＳＴ３３〜ＳＴ３９に示すように、確認者との対話証明により検証する。
【０１１１】
始めに、検証者のユーザ端末３０は、{α_1},{β_1}∈ Z_qをランダムに選び、a_1 = {{g_1}^{α_1}}{{c_C}^{β_1}} mod pを計算して、{a_1},{a_2}を確認者のユーザ端末２０に送る。
【０１１２】
ステップＳＴ３３：確認者のユーザ端末３３は、k_1, k_2, k_3, k_4, 、 〜k_1、 〜k_2、 〜k_3、 〜k_4、w ∈ Z_qをランダムに選択する。
【０１１３】
ステップＳＴ３４：確認者のユーザ端末３３はmod p上で、
r_1 = (g_1＾k_1）(g_2＾k_2）、
r_2 = (g_1＾k_3）(g_2＾k_4）、
r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、
r_4 = g_1＾k_5、r_5 = u_1＾k_5、
〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、
〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、
〜r_3 = (g_1^(〜k_1))(g_2^(〜k_2))(u_1＾b)^(〜k_3) (u_2＾b)^(〜k_4)、
〜r_4 = (u_１)＾(〜k_5)、
〜r_5 = e＾(〜k_5)
を計算し、検証者にr_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを送信する。
【０１１４】
ステップＳＴ３５：検証者のユーザ端末２０は、{α_1},{β_1}を確認者のユーザ端末３０に送信することによりコミットメントa_1を開示する。
【０１１５】
ステップＳＴ３６〜ＳＴ３８：確認者のユーザ端末３０は、もしa _1 ≠ {{g_1}^{α_1}}{{c_C}^{β_1}} mod p ならば、プロトコルを中止し、そうでない場合は、
s_c1 = k_1 − (β_1 + w)・x_{c1},
s_c2 = k_2 - (β_1 + w)・x_{c2},
s_c3 = k_3 - (β_1 + w)・y_{c1},
s_c4 = k_4 - (β_1 + w)・y_{c2},
s_c5 = k_5 - (β_1 + w)・s_c,
〜s_c1 = 〜k_1 − (β_1 + w)・k_1,
〜s_c2 = 〜k_2 - (β_1 + w)・k_2,
〜s_c3 = 〜k_3 - (β_1 + w)・k_3,
〜s_c4 = 〜k_4 - (β_1 + w)・k_4,
〜s_c5 = 〜k_5 - (β_1 + w)・k_5.
を計算し、s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5,を検証者に送信する。
【０１１６】
ステップＳＴ３９〜ＳＴ４２：検証者のユーザ端末３０は、
r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) ,
r_2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) ,
r_4 = g_1＾{s_c5}・h_C＾(β_1 + w),
〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ},
〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ},
〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ},
〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},
〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}
上記の式がすべて成り立つことを確認した後、
r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},
r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}
をすべてmod p上で検査する。２つの式が両方成り立てば検証成功、どちらか１つでも成り立たなければ検証失敗となる。これにより、log_{g_1} (h_C) = log_{u_1}(e / {g_1}^{H_{q}(m‖L)})かつlog_{g_1} (c_C){d_C}^t = log_{u_1}v であることを間接的に検証する。
【０１１７】
ステップＳＴ４３〜ＳＴ４５：検証者のユーザ端末３０は、ステップＳＴ３１のc_1 = c_{n+1}と、ステップＳＴ３２〜ＳＴ３９の対話証明によるlog_{g_1} (h_C) = log_{u_1}(e / {g_1}^{H_{q}(m‖L)})かつlog_{g_1} (c_C){d_C}^b = log_{u_1}vとの二つの検証が成り立つ場合は検証合格（ＯＫ）を出力してリング署名σ（ｍ）を受理し、成り立たない場合は検証不合格（ＮＧ）を出力してリング署名σ（ｍ）を棄却する。
【０１１８】
ステップＳＴ２０及びＳＴ３０の検証で、Ｎ人のうちの誰かは確実に署名をしているという事実を確かめることはできるが、どのメンバが署名したかということはわからない。
【０１１９】
また、確認者は自分の秘密鍵（x_C1, x_C2, y_C1, y_C2, s_C）を用いて直接署名の正当性を検証できるが、検証者は確認者と対話を行うことで検証に必要な秘密情報を知らないまま、署名の正当性を確認できる。
【０１２０】
上述したように本実施形態によれば、署名者としてのユーザに固有の秘密鍵情報（x_i）及び署名者が選択した他の複数のユーザの公開鍵情報（y_j）及び署名者が指名した確認者の公開鍵情報（c_C, d_C, h_C）を用いて、任意のデジタル情報（m）に対するリング署名を生成する。
【０１２１】
これにより、署名者は、リング署名に含めたい他のユーザとの事前やりとり無しで他のユーザの公開鍵情報を任意に選ぶことができ、リング署名からは各ユーザのうちの誰が署名したかが検証者には全くわからないという特徴を持ったリング署名を生成できる。
【０１２２】
これに加え、署名者が署名時に指名した特定の確認者だけが検証でき、それ以外の検証者は一人では署名の正当性を検証できないが、先述の特定の確認者と対話を行うことで特定の確認者以外の検証者も署名の正当性を知ることができる署名を生成できる。
【０１２３】
更に、公開鍵暗号方式であるクラマー・シャウプ暗号が持つ頑強性という性質を用いているため、不正な署名者が過去の署名情報の一部を使うと、署名検証に通るような新たな署名を生成することができない。それにより確認者が意図しない署名の正当性を対話的に第三者に証明してしまうことを阻止できる。
【０１２４】
これにより、リング署名の利用・検証を、署名者が希望する範囲のみで行うように確実に制限することができる。すなわち、署名者に指名された確認者は、正しく作られた署名のみを選んで検証または、第三者に対して対話的に正当性を証明することが確実にできるようになる。
【０１２５】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１２６】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１２７】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１２８】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１２９】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１３０】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１３１】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１３２】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１３３】
【図１】本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図である。
【図２】図１における情報の流れを示す模式図である。
【図３】同実施形態における全体の動作を示すシーケンス図である。
【図４】同実施形態における署名生成の動作を説明するためのフローチャートである。
【図５】同実施形態における確認者による署名検証の動作を説明するためのフローチャートである。
【図６】同実施形態における検証者等による署名検証の動作を説明するためのフローチャートである。
【図７】本実施形態方式の概略を示す模式図である。
【符号の説明】
【０１３４】
１０，２０，３０…ユーザ端末、１１，２１…秘密鍵記憶装置、１２…署名生成部、２２…確認者用署名検証部、２３，３２…対話証明部、３１…検証者用署名検証部、３３…記憶装置、４０…公開掲示板サーバ、４１…公開情報記憶装置、５０…ネットワーク。
【技術分野】
【０００１】
本発明は、デジタル署名方式の一種のリング署名方式を用いるデジタル署名システム、装置及びプログラムに係り、例えばリング署名の利用・検証を、署名者が希望する範囲のみで行うように確実に制限し得るデジタル署名システム、装置及びプログラムに関する。
【背景技術】
【０００２】
デジタル署名方式の一種として、従来からリング署名方式が知られている。リング署名方式とは、以下の性質をもつデジタル署名方式である。
第１は、署名者がメンバを任意にＮ人選んで生成したグループの代表として署名を生成することが可能であるという性質である。
【０００３】
第２は、Ｎ人に含まれているユーザを含めた任意の検証者はＮ人のうちの１人が署名した事実は検証可能だが、どの１人が署名者であるかを特定するのが困難な性質である。
【０００４】
また、リング署名とは異なる種類のデジタル署名として、従来から指名確認者署名方式が知られている。指名確認者署名方式とは、以下の性質を持つデジタル署名方式である。
【０００５】
第１は、署名者が任意に選んだユーザを確認者として指名し、その確認者は、署名の正当性を検証でき、それ以外のユーザは署名の正当性を検証できないという性質である。
【０００６】
第２は、署名者に確認者として指名されていないユーザは一人では署名の正当性を検証できないが、署名者に確認者として指名されているユーザと指名されていないユーザが対話的に証明をすることによって、指名されていないユーザも署名の正当性を確認することができるという性質である。
【０００７】
以上のようなリング署名方式及び指名確認者署名に関連する他の先行技術文献情報としては、後で引用する非特許文献１−３などがある。
【０００８】
だが、リング署名には、署名者が匿名性を持つ反面、署名の検証者が制限されないという不都合があり、一方、指名確認者署名には、署名を検証可能な者を確認者または確認者が対話する検証者に制限できる反面、署名者の匿名性が無いという不都合がある。このような実情を考慮し、リング署名方式で署名されたデジタル署名の利用・検証を署名者が希望する範囲のみで行うように制限し得る技術が特許文献１に開示されている。
【０００９】
また、暗号化するメッセージを知っていなければ、暗号文を作れない頑強性という性質をもつ暗号方式として、クラマー・シャウプ暗号と呼ばれる方式が非特許文献４に開示されている。
【非特許文献１】Ｍ．阿部、Ｍ．大久保、Ｋ．鈴木（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）、ｐｐ.２３１−２４４、１９９７年
【非特許文献４】Ｒ．クラマー、Ｖ．シャウプ（R. Cramer, V.Shoup）著、「ア・プラクティカル・パブリック・キー・クリプトシステム・プロバブリー・セキュア・アゲインスト・アダプティブ・チョーズン・サイファテキスト・アタック（A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack)」、クリプト’９８（CRYPTO'98） ＬＮＣＳ １４６２， ｐｐ. １３−２５、１９９８年
【特許文献１】特開２００６−２０３８２６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら特許文献１の方式では、他人の署名の一部を元にして、新たに生成した自身の署名に対して対話的検証を行うことにより、元にした他人の署名の正当性を同時に検証可能となってしまう。これにより指名確認者や元の署名者が意図しない署名の正当性を第三者が知り得るという問題がある。
【００１１】
以下、この問題を具体的に説明する。
対象となる平文mに対する署名のコミットメントをd1＝g^(k + Hq(m‖L)) mod p, d2＝yc^k mod pとする。このm, d1, d2を用いて、次のd1’，d2’を計算する。
【００１２】
d1’＝d1・g^(k’ + Hq(m’‖L) - Hq(m‖L)) mod p,
d2’＝d2・yc^k’ mod p
但し、k’は乱数、m’は任意の平文。
【００１３】
このとき、d1’＝g^{(k+k’) + Hq(m’‖L)} mod p, d2’＝yc^(k+k’) mod pであるから、d1’，d2’は、m’に対する正しいコミットメントである。このため、コミットメントとしてd1’，d2’を用いたm’に対する署名を生成して対話的署名検証を行うことで、検証に成功すれば対象の署名も正当であり、検証に失敗すれば対象の署名も不正であると判断できる。これにより、対象とする署名について対話的署名検証を行わずに、その署名検証が可能となってしまう。
【００１４】
つまり、本来ならば署名者が指定した確認者と、確認者が許可した検証者に対してのみその署名の正当性を示すべきであるにもかかわらず、間接的に、署名生成可能な第三者が、知りたいと思う署名の正当性を確認することができてしまう。
【００１５】
本発明は上記実情を考慮してなされたもので、リング署名の利用・検証を、署名者が希望する範囲のみで行うように確実に制限し得るデジタル署名システム、装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の一局面は、署名者としてのユーザに固有の秘密鍵情報（ｘ_i）及びこの署名者を含み当該署名者が選択した他の複数ユーザの公開鍵情報（y_1, y_2, … ｙ_n）及び署名者が指名した確認者の複数の公開鍵情報（ｃ_C，ｄ_C，ｈ_C）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置と、前記リング署名を検証する際に、前記確認者の複数の公開鍵情報に対応する複数の秘密鍵情報（ｘ_C１，ｘ_C２，ｙ_C１，ｙ_C２，ｓ_C）に基づいて、当該リング署名を検証する確認者用署名検証装置と、前記リング署名を検証する際に、前記確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置とを備えたデジタル署名システムである。
【００１７】
なお、本発明の一局面は、各装置からなる全体構成を「システム」として表現したが、これに限らず、全体構成又は各装置を「装置」、「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」として表現してもよい。
【００１８】
（作用）
本発明の一局面は、署名者としてのユーザに固有の秘密情報（ｘ_i）及びこの署名者を含み当該署名者が選択した他の複数のユーザの公開鍵情報（y_1, y_2, … ｙ_n）及び署名者が指名した確認者の公開鍵情報（ｃ_C，ｄ_C，ｈ_C）を用いて、任意のデジタル情報（ｍ）に対するリング署名を生成する。
【００１９】
これにより、署名者は、リング署名に含めたい他のユーザとの事前やりとり無しで他のユーザの公開鍵情報を任意に選ぶことができ、リング署名からは各ユーザのうちの誰が署名したかが検証者には全くわからないという特徴を持ったリング署名を生成できる。
【００２０】
これに加え、署名者が署名時に指名した特定の確認者だけが検証でき、それ以外の検証者は一人では署名の正当性を検証できないが、先述の特定の確認者と対話を行うことで特定の確認者以外の検証者も署名の正当性を知ることができる署名を生成できる。
【００２１】
更に、過去に別の署名者が生成した署名情報の一部を使って、不正に新たな署名を生成した場合、署名検証に失敗することにより、リング署名の利用・検証を、署名者が希望する範囲のみで行うように確実に制限することができる。
【発明の効果】
【００２２】
以上説明したように本発明によれば、リング署名の利用・検証を、署名者が希望する範囲のみで確実に行うように制限できる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の一実施形態について図面を用いて説明するが、その前に、本発明の実施形態に関連するクラマー・シャウプ暗号の概要を述べる（詳細は非特許文献４参照。）。
【００２４】
［公開鍵・秘密鍵ペア生成］
公開パラメータとして素数位数qの乗法巡回群Gとその生成元g_1と汎用一方向性ハッシュ関数を入力とし、以下の処理を行う。
【００２５】
（１）g_1, g_2 ∈ G をランダムに選択する。
（２）x_1, x_2, y_1, y_2, z ∈ Z_qをランダムに選択する。
（３）c＝g_1＾｛x_1｝g_2＾｛x_2｝, d＝g_1＾｛y_1｝g_2＾｛y_2｝, h＝g_1＾zを計算する。
（４）ハッシュ関数Ｈを汎用一方向性ハッシュ関数の集合から選択する。
（５）公開鍵（g_1, g_2, c, d, h, H)、秘密鍵（x_1, x_2, y_1, y_2, z）を出力する。
【００２６】
［暗号化］
公開鍵（g_1, g_2, c, d, h, H）、メッセージm ∈ Gを入力とし、以下の処理を行う。
【００２７】
（１）r ∈ Z_qをランダムに選択する。
（２）u_1 ＝ g_1＾r, u_2 ＝ g_2＾r, e＝h＾{r}・mを計算する。
（３）α＝Ｈ（u_1, u_2, e）を計算する。
（４）v ＝ c＾r・d＾{rα}を計算する。
（５）暗号文（u_1, u_2, e, v）を出力する。
【００２８】
［復号］
暗号文（u_1, u_2, e, v）を入力とし、以下の処理を行う。
【００２９】
（１）α＝H（u_1, u_2, e）を計算する。
（２）u_1＾｛x_1＋y_1・α｝u_2＾｛x_2＋y_2・α｝＝ Vが成り立つか否かを検証し、否の場合には無効な暗号文として拒絶して処理を終了する。
（３）m ＝ e／{u_1＾z}を計算し、平文として出力する。
以上がクラマー・シャウプ暗号の概要である。
【００３０】
続いて、本発明の一実施形態について説明する。
（１． 本発明の実施形態の概要）
図７は本発明の実施形態方式の概略を示す模式図である。本実施形態方式は、過去に別の署名者が生成した署名情報の一部を使って、不正に新たな署名を生成しようとしても、確認者Cの検証に失敗する。そのため、署名検証は、署名者が信用する確認者が決めた範囲でのみ確実に行われる。
【００３１】
（１．１ 準備）
符号Gをグループメンバの集合とする。U_j （j ＝ 1，…，n）をメンバ集合Ｇに属するメンバ、U_iを署名者とする。符号Cを、署名者に指定された確認者とする。符号Vを、権限の無い一般の検証者とする。
【００３２】
ここで、q｜p-1を満たす大きな素数をp,qとする。位数がqであるpの部分群の生成元をg、g_1、g_２とする（但し、下線_の右側は下付添字を表す）。メンバU_jはｘ_j∈Z_qを秘密鍵、ｙ_j＝g^{ｘ_j} mod pとし、公開鍵y_jを公開する（但し、 ^ は、べき乗を表す）。さらに、確認者の秘密鍵をx_C1、x_C2、y_C1、y_C2、s_C ∈Z_q、公開鍵をc_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod pとする。また、符号H：｛0, 1｝^＊→｛0, 1｝^ｌ，H_q：｛0, 1｝^＊→Z_qを衝突困難性ハッシュ関数とする。更に、符号Lを署名者U_iが任意に選んだユーザグループの公開鍵リストとし、ここでは簡単のためにL＝｛y_1, y_2, ・・・, y_n｝に固定する。
【００３３】
（１．２ 署名生成）
署名者Ｕiは、以下の手順により平文mに対する指名確認者リング署名σを生成する。
【００３４】
(1) 平文m、公開鍵暗号リストLに対して、クラマー・シャウプ暗号を変形したコミットメントCC ＝ (u_1, u_2, e, v)を下式により計算する。但し、r ∈Z_qとする。
【００３５】
u_1 = g_1＾r mod p,
u_2 = g_2＾r mod p,
e =h_C＾ｒ・g_1＾Hｑ(m‖L),
b =H_ｑ(u_1‖u_2‖e),
v =c_C＾r・d_C＾rb mod p
(2) T_i = g^α mod p、 c_{i+1} = H(CC‖T_i)を計算する。但し、α∈Z_q。
【００３６】
(3) j = i+1, . . . , n, 1, . . . , i-1について、
T_j = g^s_j・ y_j^c_j mod p,
c_{j+1} mod n = H(CC‖T_j)
を順次計算する。但し、s_j ∈ Z_q。
【００３７】
(4) 秘密鍵x_iを用いてs_i = α−x_i・c_i mod qを計算し、
署名σ = (c_1, s_1, . . . , s_n, CC, L)を出力する。
【００３８】
（１．３ 署名検証）
確認者Cは、以下の手順により、平文mに対する署名σ = (c_1, s_1, . . . , s_n, CC, L)の正当性を検証する。
【００３９】
(1) まずb = H_{q}(u_1‖u_2‖e)を計算し、次に下式が成り立つことをそれぞれ検証する(コミットメントの正当性検証)。
【００４０】
v =u_1＾(x_{c1}+by_{c1})・u2＾(x_{c2}+by_{c2}) mod p,
g＾{H_{q}(m‖L)} = e/{ u_ 1}＾(s_c) mod p.
(2) j = 1, . . . , nについてT_j = g＾s_j・ y_j＾c_j mod p、c_(j+１) = H(CC‖T_j)を順次計算し，c_1 = c_(n+1)となることを検証する(コミットメントに対するリング署名の正当性検証)。
【００４１】
(1)(2) 両方の検証が成功した場合のみ署名検証成功とする。
【００４２】
（１．４ 対話的署名検証）
検証者Vは、以下の確認者Cとの対話により、平文mに対する署名σ = (c_1， s_1， . . . ， s_n，CC，L)の正当性を検証する。
【００４３】
(1) 検証者Vは，j = 1, . . . , nについてT_j =g＾s_j・ y_j＾c_j mod p、 c_{j+1}= H(CC‖T_j)を順次計算し，c_1=c_{n+1}となることを検証する。成り立たない場合は署名検証失敗とする(コミットメントに対するリング署名の正当性検証)。
【００４４】
(2) 検証者Vは、乱数α_1、 β_1 ∈Z_qを生成し、
a_1 = g_1＾α_1・c_C＾β_1 mod p,
を計算して確認者Cへ送る。
【００４５】
(3) 確認者Cは、乱数k_1、 k_2、 k_3、 k_4、 k_5、〜k_1、 〜k_2、 〜k_3、 〜k_4、〜k_5、w ∈Z_qを選び、以下のk_1、 k_2、 k_3、 k_4、k_5、 〜k_1、 〜k_2、 〜k_3、 〜k_4、〜k_5、wを(mod p 上で) 計算して検証者Vへ送る。
【００４６】
r_1 = (g_1＾k_1）(g_2＾k_2）、
r_2 = (g_1＾k_3）(g_2＾k_4）、
r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、
r_4 = g_1＾k_5、r_5 = u_1＾k_5、
〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、
〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、
〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、
〜r_4 = (u_１)＾(〜k_5)、
〜r_5 = e＾(〜k_5)
(4) 検証者Vは、α_1, β_1を確認者Cへ送る。
【００４７】
(5) 確認者Cは、a_1=g_1^α_1・c_C＾β_1 mod p が成り立つかを検証し、成り立たない場合はプロトコルを終了する。成り立つ場合は、以下のs_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5,を(mod q 上で) 計算して、検証者Vに送る。
【００４８】
s_c1 = k_1 − (β_1 + w)・x_{c1},
s_c2 = k_2 - (β_1 + w)・x_{c2},
s_c3 = k_3 - (β_1 + w)・y_{c1},
s_c4 = k_4 - (β_1 + w)・y_{c2},
s_c5 = k_5 - (β_1 + w)・s_c,
〜s_c1 = 〜k_1 − (β_1 + w)・k_1,
〜s_c2 = 〜k_2 - (β_1 + w)・k_2,
〜s_c3 = 〜k_3 - (β_1 + w)・k_3,
〜s_c4 = 〜k_4 - (β_1 + w)・k_4,
〜s_c5 = 〜k_5 - (β_1 + w)・k_5.
(6) 検証者Vは、下式を(mod p 上で) 計算する。
【００４９】
r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) ,
r_2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) ,
r_4 = g_1＾{s_c5}・h_C＾(β_1 + w),
〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ},
〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ},
〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ},
〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},
〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}
上記の式がすべて成り立つことを確認した後、
r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},
r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}
の２つの式が両方成り立てば検証成功、どちらか１つでも成り立たなければ検証失敗となる。
【００５０】
（２． 安全性）
特許文献１の方式では、他人の署名の一部を元にして、新たに生成した自身の署名に対して対話的検証を行うことにより、元にした他人の署名の正当性を同時に検証可能となってしまう。これにより指名確認者や元の署名者が意図しない署名の正当性を第三者が知り得るという問題があった。本実施形態方式は、この問題に直接関係する署名の不可視性(Invisibility of Signature)を再定義しその定義を満たすことを示す。また、その他の安全性の定義も示す。
【００５１】
以下は、安全な指名確認者リング署名が満たす条件を示し、本実施形態方式がこれらの条件（i）〜（vi）を満たしていることを証明する。
【００５２】
（i）署名の完全性（Completeness of Signature）
署名者が正しい動作をした場合には、確認者が検証可能な署名を構成できること。
【００５３】
（ii）署名の偽造不可能性（Unforgeability of Signature）
リング署名を構成するグループのメンバ以外が署名を偽造できないこと。
【００５４】
（iii）署名者の曖昧性（Signer Ambiguity）
署名の情報から署名者の情報が漏れないこと。
【００５５】
（iv）署名の不可視性（Invisibility of Signature）
敵Aは、全ての公開情報を得られるとともに、確認者C 以外の全てのユーザと結託することができる。また敵Aは、任意の署名について確認者オラクルOcを用いて対話的署名検証を行うことができる。Ａは、これら試行の後、二つの平文m_b (b∈{0, 1})と署名者U_i，公開鍵リストLを決定し、テストオラクルπに入力する，テストオラクルπは、ランダムにb∈{0, 1}を選択し、署名σ = Sig(m_b, x_i, L, y_C)をAに返す。その後、Aは再びOcにアクセスできるが、σについて尋ねることはできないこととする。最後に敵Aはb’∈{0, 1}を出力する。b’ = bのとき敵Aは攻撃に成功したといい、この成功確率が無視できるほど小さいとき、指名確認者リング署名方式は，署名の不可視性(Invisibility of Signature)を持つ。
【００５６】
（ｖ）検証の一貫性（Consistency of Verification）
確認者Ｃや検証者Ｖが正しい動作をした場合は、正しく検証ができること。
【００５７】
（vi）検証の非伝達性（Non-transferability of Verification）
確認者Ｃの秘密鍵に関する情報が対話証明において、検証者Ｖにほとんど漏れないこと。
【００５８】
本実施形態方式は、以上の要求条件に対して以下の定理が成り立つ。
【００５９】
（定理１：署名の完全性）
正しい秘密鍵をもつ署名者U_iがアルゴリズムに従い生成したリング署名は、確認者Cの署名検証に常に成功する。
証明：プロトコルから明らかである。
【００６０】
（定理２：署名の偽造不可能性）
本実施形態方式は、ランダムオラクルモデルと離散対数問題の困難性を仮定すると、グループメンバ以外の任意の敵が署名の偽造に成功する確率は無視できるほど小さい。
【００６１】
証明（Sketch）:本実施形態方式が偽造可能であると仮定すると、非特許文献１により提案されたリング署名を偽造可能な敵を構成することができる。
【００６２】
（定理３：署名者の曖昧性）
任意のメッセージに対するリング署名から署名者を特定できる確率は１／ｎである。
【００６３】
証明（Sketch）：s_iを除くs_jはZ_qから一様にランダムに選ばれ、s_iはαがZ_q上から一様にランダムに選ばれるので、s_iもZ_q上に一様に分布する。また、CC = (u_1, u_2, e, v)はメンバ公開鍵には関係しない。従って、グループメンバとメッセージmを固定すると、（s_1, …, s_n, (u_1, u_2, e, v)）は、署名者が誰であるかに関わらず、同様にｎｑのバリエーションをもつ。残りのｃ_1は、グループメンバのリスト、メッセージm及び（s_1, …, s_n, (u_1, u_2, e, v)）より一意に決定できる。よって、署名者を特定できる確率は１／ｎである。
【００６４】
（定理４：署名の不可視性）
本実施形態方式は、ＤＤＨ(decisional Diffie-Hellman)仮定のもとで、署名の不可視性(Invisibility of Signature)を持つ。
【００６５】
証明（Sketch）：本実施形態方式の署名の不可視性を無視できない確率で破る敵Aを利用して、クラマー・シャウプ暗号の適応的選択暗号文攻撃に対する識別不可能性（Indistinguishability）を破る敵Bを構成する。Bへの入力である公開パラメータ(p, q, g_1, g_2, H_q) および公開鍵(c, d, h)を本実施形態方式の公開パラメータおよび確認者Cの公開鍵(c_C, d_C, h_C)として敵Aに入力し、各ユーザの鍵ペアはランダムに生成して入力する。また、対話的署名検証オラクルOCのシミュレートには，ゼロ知識対話証明（zero-knowledge bi-proof）のシミュレータを用いればよい。
【００６６】
敵Aが出力した平文m_a (a∈{0, 1})と公開鍵リストLに対して、〜m_a = g_1＾H(m_a‖L) (a∈{0, 1})を計算してテストオラクルπへ送る。テストオラクルπから送り返された暗号文Enc( 〜m_a)を用いて署名σ = (c_1, s_1, . . . , s_n, Enc( 〜m_a), L)を生成し，敵Aに入力する。最終的に、敵Aが出力したa’を敵Bの出力とする。
【００６７】
ゼロ知識対話証明のシミュレートの失敗確率はクエリー（query）の回数(多項式回) で抑えられる。また、コミットメント(暗号文)を識別することなく署名の不可視性を破れる確率はランダムしかありえないため無視できる。よって、敵Aが有意な確率で本実施形態方式の署名の不可視性を破れるならば、敵Bは有意な確率でクラマー・シャウプ暗号の識別不可能性を破ることができる。クラマー・シャウプ暗号はＤＤＨ仮定のもとで適応的選択暗号文攻撃に対して識別不可能（Indistinguishable）であることから、本実施形態方式はＤＤＨ仮定のもとで署名の不可視性を持つと言える。
【００６８】
補足説明：なお、ＤＤＨ仮定とはＤＤＨ問題を解くことが困難であるという仮定である。ここで、ＤＤＨ問題について説明する。素数位数ｑの乗法巡回群をＧとする。ランダムな４つ組（g_1, g_2, u_1, u_2）∈Ｇ４の分布をＲとする。g_1, g_2 ∈ Ｇとr ∈ Z_qとをランダムに選び、u_1 ＝ g_1^r、u_2 ＝ g_2^rとした４つ組（g_1, g_2, u_1, u_2）∈Ｇ４の分布をＤとする。このとき、任意に与えられた４つ組（g_1, g_2, u_1, u_2）が分布Ｒ，Ｄのいずれに属するかを見分ける問題をＤＤＨ問題と呼ぶ。上述した本実施形態方式の署名の不可視性は、ＤＤＨ問題の困難性（ＤＤＨ仮定）に帰着される。
【００６９】
（定理５：検証の一貫性）
確認者Ｃと検証者Ｖの間で行われるリング署名検証プロトコルにおいて、正しいリング署名が検証に失敗する確率及び不正なリング署名が検証に成功する確率は任意の確認者Ｃに対して無視できる。
【００７０】
（定理６：検証の非伝達性）
確認者Ｃと検証者Ｖの間で行われるリング署名検証プロトコルは、最小知識対話証明（minimum knowledge bi-proof）である（非特許文献２参照）。
【００７１】
証明（定理５，６）：本実施形態方式は、非特許文献３に記載の対話証明システム（bi-proof system）を応用している。対話証明システムの完全性（completeness）、安定性（Soundness）、零知識証明性（Zero-Knowledgeness）は、非特許文献３によって証明されており、この性質から一貫性、非伝達性は明らかである。これは本実施形態方式でも成り立つ。
【００７２】
以上が本発明の実施形態方式の概要である。続いて、本発明の一実施形態について具体的に説明する。
【００７３】
（一実施形態）
図１は本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図であり、図２は図１における情報の流れを示す模式図である。このシステムは、複数のユーザ端末１０及び各１台のユーザ端末２０，３０を備えている。各ユーザ端末１０，２０，３０は、コンピュータにより実現される場合、それぞれ各端末１０，２０，３０の機能を実現するためのプログラムが予め記憶媒体又はネットワークから各端末のコンピュータにインストールされて実現される。
【００７４】
ユーザ端末は、ユーザ端末１０，２０，３０に分類される。
複数のユーザ端末１０は、署名者としてのユーザｕのユーザ端末１０と、リング署名に用いられるグループメンバとしての各ユーザｋ，…のユーザ端末１０，…とを含む。
【００７５】
各ユーザ端末１０は、秘密鍵記憶装置１１及び署名生成部１２を備えている。
【００７６】
ここで、秘密鍵記憶装置１１は、署名者としてのユーザに固有の秘密鍵情報が記憶されるメモリであり、署名生成部１２から読出可能となっている。
【００７７】
署名生成部１２は、署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_j）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n））と、署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）とに基づいて、任意のデジタル情報（ｍ）に対するリング署名を生成するものであり、具体的には図３及び図４に示すステップＳＴ１２〜ＳＴ１７の処理を実行する機能をもっている。
【００７８】
これらの機能としては、例えば、署名者の秘密鍵情報（ｘ_i）を秘密鍵記憶装置１１に書き込む機能と、デジタル情報（ｍ）、リスト（L）、乱数（r）、確認者の公開鍵情報（c_C, d_C, h_C）及びハッシュ関数（H_{q}( )）に基づいて、コミットメント情報（CC）を計算する機能と、第１乱数情報（α）、コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第１リング要素情報（c_{i+1}）を計算する機能と、ユーザ番号（j = i+1, …, n, 1, …, i-1）毎に、ユーザ乱数情報（s_j）、ユーザ公開鍵情報（y_j）、第１リング要素情報（c_j）、コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第２リング要素情報（c_{j+1} mod n）を順次計算する機能と、第１乱数情報（α）、秘密鍵記憶装置１１内の秘密鍵情報（ｘ_i）及び署名者に対応するリング要素情報（ｃ_i）に基づいて、署名者関連情報（ｓ_i）を生成する機能と、１番目のリング要素情報（ｃ_1）、ユーザ乱数情報（ｓ_j）、署名者関連情報（ｓ_i）、コミットメント情報（CC）及びリスト（L）を含むリング署名（σ = (c_1, s_1, …, s_n, CC, L)）を出力する機能とが含まれる。
【００７９】
署名生成部１２の機能は、詳しくは、署名者の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)を秘密鍵記憶装置１１に書き込む機能と、デジタル情報ｍ、リストL、システムパラメータg_1, g_2、乱数r、確認者の公開鍵情報c_C, d_C, h_C及びハッシュ関数H_{q}( )に基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L), 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p により、コミットメント情報CC ＝ (u_1, u_2, e, v)を計算する機能（但し、‖は連接を表す）と、システムパラメータg、第１乱数情報α、コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_i = g^α mod p 及び式c_{i+1} = H(CC‖T_i)により、第１リング要素情報c_{i+1}を計算する機能と、ユーザ番号j = i+1, …, n, 1, …, i-1毎に、システムパラメータg、ユーザ乱数情報s_j、ユーザ公開鍵情報y_j、第１リング要素情報c_j 、コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g^s_j・ y_j^c_j mod p 及び式c_{j+1} mod n = H(CC‖T_j)により、第２リング要素情報c_{j+1} mod n を順次計算する機能と、第１乱数情報α、秘密鍵記憶装置１１内の秘密鍵情報ｘ_i及び署名者に対応するリング要素情報ｃ_iに基づいて、式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ により、署名者関連情報ｓ_iを生成する機能と、１番目のリング要素情報ｃ_1、ユーザ乱数情報ｓ_j、署名者関連情報ｓ_i、コミットメント情報CC及びリストLを含むリング署名σ = (c_1, s_1, …, s_n, CC, L) を出力する機能とを含んでいる。
【００８０】
ユーザ端末２０は、指定された確認者Ｃとしてのユーザcに操作されるものであり、秘密鍵記憶装置２１、確認者用署名検証部２２及び対話証明部２３を備えている。
【００８１】
秘密鍵記憶装置２１は、確認者としてのユーザに固有の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）が記憶されるメモリであり、確認者用署名検証部２２及び対話証明部２３から読出可能となっている。
【００８２】
確認者用署名検証部２２は、リング署名（σ）を検証する際に、秘密鍵記憶装置２１内の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）に基づいて、リング署名（σ）を検証する第１検証機能と、リスト（Ｌ）内の公開鍵情報（ｙ_j）に基づいて、リング署名（σ）を検証する第２検証機能と、第１及び第２検証手段による検証に合格したとき、リング署名を受理するリング署名受理機能とを有し、具体的には図３及び図５のステップＳＴ２０〜ＳＴ２５に示す処理を実行する機能をもっている。
【００８３】
ここで、第１検証機能としては、例えば、リング署名σを検証する際に、当該リング署名σ内のコミットメント情報CCと、ハッシュ関数H_{q}とに基づいて、式b = H_{q}(u_1‖u_2‖e)により、コミットメント部分情報bを計算する機能と、このコミットメント部分情報b、秘密鍵記憶装置２１内の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C 、コミットメント情報CC 及びシステムパラメータgに基づいて、第１式v =u_1＾(x_{c1}+by_{c1})・u2＾(x_{c2}+by_{c2}) mod p 及び第２式g＾{H_{q}(m‖L)} = e/{ u_ 1}＾(s_c) mod pが成り立つことをそれぞれ検証する機能とが含まれる。
【００８４】
第２検証機能としては、例えば、ユーザ番号j = 1, . . . , n毎に、システムパラメータg、リング署名σ内のユーザ乱数情報s_j、ユーザ公開鍵情報y_j、リング署名σ内の第１リング要素情報c_j 、コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する機能とが含まれる。
【００８５】
対話証明部２３は、検証者用の対話証明部３２による対話証明の際に動作するものであり、図６のステップＳＴ３３，ＳＴ３４，ＳＴ３６〜ＳＴ３８に示す処理を実行する機能をもっている。
【００８６】
対話証明部２３の機能としては、例えば、ユーザ端末３０から値a_1を受けると、値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを計算してユーザ端末３０に送信する機能（但し、ｒ_1 = (g_1＾k_1）(g_2＾k_2）、r_2 = (g_1＾k_3）(g_2＾k_4）、r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、r_4 = g_1＾k_5、r_5 = u_1＾k_5、〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、〜r_4 = (u_１)＾(〜k_5)、〜r_5 = e＾(〜k_5)。ここで、k_1、 k_2、 k_3、 k_4 、 k_5、 〜k_1、 〜k_2、〜 k_3、 〜k_4、 〜k_5、 w ∈Z_q）と、ユーザ端末３０から乱数α_1、 β_1を受けると、式a_1=g_1^α_1・c_C＾β_1 mod pが成り立つことが検証した後、値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5を計算してユーザ端末３０に送信する機能（但し、s_c1 = k_1 − (β_1 + w)・x_{c1}, s_c2 = k_2 - (β_1 + w)・x_{c2}, s_c3 = k_3 - (β_1 + w)・y_{c1}, s_c4 = k_4 - (β_1 + w)・y_{c2}, s_c5 = k_5 - (β_1 + w)・s_c, 〜s_c1 = 〜k_1 − (β_1 + w)・k_1, 〜s_c2 = 〜k_2 - (β_1 + w)・k_2, 〜s_c3 = 〜k_3 - (β_1 + w)・k_3, 〜s_c4 = 〜k_4 - (β_1 + w)・k_4, 〜s_c5 = 〜k_5 - (β_1 + w)・k_5）とを含んでいる。
【００８７】
ユーザ端末３０は、検証者Ｖとしてのユーザｖに操作されるものであり、検証者用署名検証部３１、対話証明部３２及び記憶装置３３を備えている。
【００８８】
検証者用署名検証部３１は、リング署名を検証する際に、記憶装置３３内のリスト（Ｌ）内の公開鍵情報（y_j）に基づいて、リング署名（σ）を検証する第１検証機能と、この第１検証機能及び対話証明部３２の第２検証機能による検証に合格したとき、リング署名を受理するリング署名受理機能とを有し、具体的には図６のステップＳＴ３１，ＳＴ４３〜ＳＴ４５に示す処理を実行する機能をもっている。
【００８９】
ここで、第１検証機能としては、例えば、リング署名σを検証する際に、ユーザ番号j = 1, . . . , n毎に、システムパラメータg、リング署名σ内のユーザ乱数情報s_j、ユーザ公開鍵情報y_j、リング署名σ内の第１リング要素情報c_j 、コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する機能を含んでいる。
【００９０】
対話証明部３２は、記憶装置３３内の確認者の公開鍵情報（c_C, d_C, h_C）に基づき、確認者のユーザ端末２０との間の対話証明を介して、当該リング署名を検証する第２検証機能を有し、具体的には図６のステップＳＴ３２，ＳＴ３５，ＳＴ３９〜ＳＴ４２に示す処理を実行する機能をもっている。
【００９１】
ここで、第２検証機能としては、例えば、乱数α_1、 β_1 を生成すると共に、この乱数α_1, β_1及び記憶装置３３内のシステムパラメータg_1,確認者の公開鍵情報c_Cに基づいて、式a_1 = g_1＾α_1・c_C＾β_1 mod p により計算した値a_1をユーザ端末２０に送信する機能と、ユーザ端末２０から値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを受信する機能（但し、ｒ_1 = (g_1＾k_1）(g_2＾k_2）、r_2 = (g_1＾k_3）(g_2＾k_4）、r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、r_4 = g_1＾k_5、r_5 = u_1＾k_5、〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、〜r_4 = (u_１)＾(〜k_5)、〜r_5 = e＾(〜k_5)。ここで、k_1、 k_2、 k_3、 k_4 、 k_5、 〜k_1、 〜k_2、〜 k_3、 〜k_4、 〜k_5、 w ∈Z_q）と、値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wの受信後、乱数α_1、 β_1をユーザ端末２０に送信する機能と、ユーザ端末２０により式a_1=g_1^α_1・g_2＾β_1 mod pが成り立つことが検証された後、ユーザ端末２０から値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5を受信する機能（但し、s_c1 = k_1 − (β_1 + w)・x_{c1}, s_c2 = k_2 - (β_1 + w)・x_{c2}, s_c3 = k_3 - (β_1 + w)・y_{c1}, s_c4 = k_4 - (β_1 + w)・y_{c2}, s_c5 = k_5 - (β_1 + w)・s_c, 〜s_c1 = 〜k_1 − (β_1 + w)・k_1, 〜s_c2 = 〜k_2 - (β_1 + w)・k_2, 〜s_c3 = 〜k_3 - (β_1 + w)・k_3, 〜s_c4 = 〜k_4 - (β_1 + w)・k_4, 〜s_c5 = 〜k_5 - (β_1 + w)・k_5）と、値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5の受信後、当該値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5、前述した値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、w、記憶装置３３内の公開鍵情報c_C, d_C, h_C、デジタル情報ｍ及びリング署名σ = (c_1, s_1, …, s_n, CC, L)に基づいて、式r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) , 式r_ 2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) , 式r_4 = g_1＾{s_c5}・h_C＾(β_1 + w), 式〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ}, 式〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ}, 式〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ}, 式〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},式〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}の式が成り立つことを確認した後、r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}の２つの式が両方成り立つか、どちらか１つでも成り立たないことを検証する機能とを含んでいる。
【００９２】
記憶装置３３は、システムパラメータg, g_1, g_2及び素数ｐ，ｑと、リストＬ＝｛y_1, y_2, … , y_n｝と、確認者の公開鍵情報c_C, d_C, h_Cと、デジタル情報ｍと、リング署名σとを記憶するためのメモリであり、検証者用署名検証部３１及び対話証明部３２から読出／書込可能となっている。
【００９３】
また前提条件として、公開鍵基盤などにより、公開情報を安全に公開するための手段、例えば公開掲示板サーバ４０などが存在するとする。
【００９４】
公開掲示板サーバ４０は、公開される情報を記憶する公開情報記憶装置４１を有する。この公開掲示板サーバ４０によって実現される情報公開(掲載)手段を公開情報掲示板と呼ぶ。公開情報掲示板は全てのユーザがアクセスでき、かつ改ざんなどの不正が行われないように適切に管理されているとする。また、全てのユーザはインターネットなどのネットワーク５０に接続されているものとする。特に匿名性を必要とする場合は匿名ネットワークに接続されていてもよいが、その限りではない。
【００９５】
次に、以上のように構成されたデジタル署名システムの動作を図３のシーケンス図及び図４乃至図６の各フローチャートを用いて述べる。なお、本実施形態では、例えば、べき乗を＾で表し、下付添字を_で表し、文字の真上の波形符号を〜で表す等というように１行で済む数式表現を用いている。このような明細書中の数式表現は、図面中の数式表現とは異なるが、これらの数式表現が示す数式の内容は一致している。
（準備）：
本実施形態では、前提条件として、ユーザの公開鍵や公開情報は予め公開掲示板サーバ４０により公開されているものとする。公開の方法としては例えば公開鍵基盤などがあるが、ここでは限定しない。
【００９６】
まず、公開掲示板サーバ４０は、素数位数qの巡回群Gとその生成元g, g_1, g_2を選び公開する。ここでは、一例として、q|p-1を満たす十分大きな素数p, qを選び、位数がqとなるZ_p*の部分群をGとし、p, q, g、g_1、g_２を公開するとする。
【００９７】
さらに、公開掲示板サーバ４０は、衝突困難性ハッシュ関数H:{0,1}^*→{0,1}^q, H_q:{0,1}^*→{0,1}^qを任意に選び公開する。
【００９８】
また前提条件に従い各ユーザ端末１０，２０は、それぞれユーザu, k, cの操作により、x_u, x_k, x_c ∈ Z_qをランダムに選び、以下を計算する。なお、記号^はべき乗を表す。
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, σ)を出力する。
【００９９】
ステップＳＴ１２：α,r ∈ Z_qをランダムに選ぶ。
【０１００】
ステップＳＴ１３：衝突困難性ハッシュ関数HとH_qを用いて以下の値を計算する。
u_1 = g_1＾r mod p,
u_2 = g_2＾r mod p,
e = h_C＾r・g_1＾{H_{q}(m‖L)},
b = H_{q}(u_1‖u_2‖e),
v = c_C＾r・d_C＾rb mod p
T_i = g^α mod p,
c_{i+1} = H(u_1‖ u_2 ‖ e ‖ b ‖ v ‖ 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(CC ‖ 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, CC, L)
ステップＳＴ２０：リング署名の確認者による検証（図３、図５）
署名確認者であるユーザcのユーザ端末２０は、署名検証部２２において、メッセージmとmに対するリング署名σのペア(m,σ)及び公開掲示板サーバ４０から取得可能な公開情報ＰＵＢＩを用いて、以下のステップＳＴ２１〜ＳＴ２５の手順でリング署名の正当性とメッセージmに対するコミットメントの正当性を検証する。
【０１０５】
ステップＳＴ２１：リング署名σから、公開情報である衝突困難性ハッシュ関数H_qを用い、以下の値を計算する。
b = H_{q}(u_1 ‖ u_2 ‖e)
ステップＳＴ２２：リング署名σから、確認者の秘密鍵（x_C1, x_C2, y_C1, y_C2, s_C）を用い、以下が成り立つことを検証する。
v = u_1＾(x_{c1}+b・y_{c1})・u_2＾(x_{c2}+b・y_{c2}) mod p
ステップＳＴ２３：メッセージm及びリング署名σから、公開情報である衝突困難性ハッシュ関数H_qを用い、以下が成り立つことを検証する。
【０１０６】
e/{u_ 1}＾(s_c) = g＾{H_{q}(m‖L)} mod p
ステップＳＴ２４：j = 1, ..., nについて、公開情報である衝突困難性ハッシュ関数Hを用いて以下の値を計算する。
T_j = g^{s_j}{y_j}^{c_j} mod p,
c_{j+1} = H(CC‖ 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(CC‖ T_j)
c_1 = c_{n+1}となることを検査することにより、コミットメントに対するリング署名の正当性を検証する。
【０１１０】
ステップＳＴ３２：検証者のユーザ端末３０は、署名情報がlog_{g_1} (h_C) = log_{u_1}(e / {g_1}^{H_{q}(m‖L)}かつlog_{g_1} (c_C){d_C}^b = log_{u_1}vであるかを、以下のＳＴ３３〜ＳＴ３９に示すように、確認者との対話証明により検証する。
【０１１１】
始めに、検証者のユーザ端末３０は、{α_1},{β_1}∈ Z_qをランダムに選び、a_1 = {{g_1}^{α_1}}{{c_C}^{β_1}} mod pを計算して、{a_1},{a_2}を確認者のユーザ端末２０に送る。
【０１１２】
ステップＳＴ３３：確認者のユーザ端末３３は、k_1, k_2, k_3, k_4, 、 〜k_1、 〜k_2、 〜k_3、 〜k_4、w ∈ Z_qをランダムに選択する。
【０１１３】
ステップＳＴ３４：確認者のユーザ端末３３はmod p上で、
r_1 = (g_1＾k_1）(g_2＾k_2）、
r_2 = (g_1＾k_3）(g_2＾k_4）、
r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、
r_4 = g_1＾k_5、r_5 = u_1＾k_5、
〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、
〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、
〜r_3 = (g_1^(〜k_1))(g_2^(〜k_2))(u_1＾b)^(〜k_3) (u_2＾b)^(〜k_4)、
〜r_4 = (u_１)＾(〜k_5)、
〜r_5 = e＾(〜k_5)
を計算し、検証者にr_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを送信する。
【０１１４】
ステップＳＴ３５：検証者のユーザ端末２０は、{α_1},{β_1}を確認者のユーザ端末３０に送信することによりコミットメントa_1を開示する。
【０１１５】
ステップＳＴ３６〜ＳＴ３８：確認者のユーザ端末３０は、もしa _1 ≠ {{g_1}^{α_1}}{{c_C}^{β_1}} mod p ならば、プロトコルを中止し、そうでない場合は、
s_c1 = k_1 − (β_1 + w)・x_{c1},
s_c2 = k_2 - (β_1 + w)・x_{c2},
s_c3 = k_3 - (β_1 + w)・y_{c1},
s_c4 = k_4 - (β_1 + w)・y_{c2},
s_c5 = k_5 - (β_1 + w)・s_c,
〜s_c1 = 〜k_1 − (β_1 + w)・k_1,
〜s_c2 = 〜k_2 - (β_1 + w)・k_2,
〜s_c3 = 〜k_3 - (β_1 + w)・k_3,
〜s_c4 = 〜k_4 - (β_1 + w)・k_4,
〜s_c5 = 〜k_5 - (β_1 + w)・k_5.
を計算し、s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5,を検証者に送信する。
【０１１６】
ステップＳＴ３９〜ＳＴ４２：検証者のユーザ端末３０は、
r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) ,
r_2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) ,
r_4 = g_1＾{s_c5}・h_C＾(β_1 + w),
〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ},
〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ},
〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ},
〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},
〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}
上記の式がすべて成り立つことを確認した後、
r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},
r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}
をすべてmod p上で検査する。２つの式が両方成り立てば検証成功、どちらか１つでも成り立たなければ検証失敗となる。これにより、log_{g_1} (h_C) = log_{u_1}(e / {g_1}^{H_{q}(m‖L)})かつlog_{g_1} (c_C){d_C}^t = log_{u_1}v であることを間接的に検証する。
【０１１７】
ステップＳＴ４３〜ＳＴ４５：検証者のユーザ端末３０は、ステップＳＴ３１のc_1 = c_{n+1}と、ステップＳＴ３２〜ＳＴ３９の対話証明によるlog_{g_1} (h_C) = log_{u_1}(e / {g_1}^{H_{q}(m‖L)})かつlog_{g_1} (c_C){d_C}^b = log_{u_1}vとの二つの検証が成り立つ場合は検証合格（ＯＫ）を出力してリング署名σ（ｍ）を受理し、成り立たない場合は検証不合格（ＮＧ）を出力してリング署名σ（ｍ）を棄却する。
【０１１８】
ステップＳＴ２０及びＳＴ３０の検証で、Ｎ人のうちの誰かは確実に署名をしているという事実を確かめることはできるが、どのメンバが署名したかということはわからない。
【０１１９】
また、確認者は自分の秘密鍵（x_C1, x_C2, y_C1, y_C2, s_C）を用いて直接署名の正当性を検証できるが、検証者は確認者と対話を行うことで検証に必要な秘密情報を知らないまま、署名の正当性を確認できる。
【０１２０】
上述したように本実施形態によれば、署名者としてのユーザに固有の秘密鍵情報（x_i）及び署名者が選択した他の複数のユーザの公開鍵情報（y_j）及び署名者が指名した確認者の公開鍵情報（c_C, d_C, h_C）を用いて、任意のデジタル情報（m）に対するリング署名を生成する。
【０１２１】
これにより、署名者は、リング署名に含めたい他のユーザとの事前やりとり無しで他のユーザの公開鍵情報を任意に選ぶことができ、リング署名からは各ユーザのうちの誰が署名したかが検証者には全くわからないという特徴を持ったリング署名を生成できる。
【０１２２】
これに加え、署名者が署名時に指名した特定の確認者だけが検証でき、それ以外の検証者は一人では署名の正当性を検証できないが、先述の特定の確認者と対話を行うことで特定の確認者以外の検証者も署名の正当性を知ることができる署名を生成できる。
【０１２３】
更に、公開鍵暗号方式であるクラマー・シャウプ暗号が持つ頑強性という性質を用いているため、不正な署名者が過去の署名情報の一部を使うと、署名検証に通るような新たな署名を生成することができない。それにより確認者が意図しない署名の正当性を対話的に第三者に証明してしまうことを阻止できる。
【０１２４】
これにより、リング署名の利用・検証を、署名者が希望する範囲のみで行うように確実に制限することができる。すなわち、署名者に指名された確認者は、正しく作られた署名のみを選んで検証または、第三者に対して対話的に正当性を証明することが確実にできるようになる。
【０１２５】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１２６】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１２７】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１２８】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１２９】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１３０】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１３１】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１３２】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１３３】
【図１】本発明の一実施形態に係るデジタル署名システムの構成を示すブロック図である。
【図２】図１における情報の流れを示す模式図である。
【図３】同実施形態における全体の動作を示すシーケンス図である。
【図４】同実施形態における署名生成の動作を説明するためのフローチャートである。
【図５】同実施形態における確認者による署名検証の動作を説明するためのフローチャートである。
【図６】同実施形態における検証者等による署名検証の動作を説明するためのフローチャートである。
【図７】本実施形態方式の概略を示す模式図である。
【符号の説明】
【０１３４】
１０，２０，３０…ユーザ端末、１１，２１…秘密鍵記憶装置、１２…署名生成部、２２…確認者用署名検証部、２３，３２…対話証明部、３１…検証者用署名検証部、３３…記憶装置、４０…公開掲示板サーバ、４１…公開情報記憶装置、５０…ネットワーク。
【特許請求の範囲】
【請求項１】
署名者としてのユーザに固有の秘密鍵情報（x_i）及びこの署名者を含み当該署名者が選択した他の複数のユーザの公開鍵情報（y_1, y_2, … y_n）及び前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）を用いて、任意のデジタル情報（m）に対するリング署名を生成するデジタル署名装置と、
前記確認者の複数の公開鍵情報（c_C, d_C, h_C）に対応する複数の秘密鍵情報（x_C1, x_C2, y_C1, y_C2, s_C）に基づいて、当該リング署名を検証する確認者用署名検証装置と、
前記確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置と、
を備えたことを特徴とするデジタル署名システム。
【請求項２】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_ｊ）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n））と、当該署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）とに基づいて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置であって、
当該署名者の秘密鍵情報（ｘ_i）を記憶する秘密鍵記憶手段と、
前記デジタル情報（ｍ）、前記リスト（L）、乱数（r）、前記指名した確認者の公開鍵情報（c_C, d_C, h_C）及びハッシュ関数（H_{q}( )）に基づいて、コミットメント情報（CC）を計算する手段と、
第１乱数情報（α）、前記コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第１リング要素情報（c_{i+1}）を計算する手段と、
ユーザ番号（j = i+1, …, n, 1, …, i-1）毎に、ユーザ乱数情報（s_j）、ユーザ公開鍵情報（y_j）、第１リング要素情報（c_j）、前記コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第２リング要素情報（c_{j+1} mod n）を順次計算する手段と、
前記第１乱数情報（α）、前記秘密鍵記憶手段内の秘密鍵情報（ｘ_i）及び署名者に対応するリング要素情報（ｃ_i）に基づいて、署名者関連情報（ｓ_i）を生成する手段と、
１番目のリング要素情報（ｃ_1）、前記ユーザ乱数情報（ｓ_j）、前記署名者関連情報（ｓ_i）、前記コミットメント情報（CC）及び前記リスト（L）を含むリング署名（σ = (c_1, s_1, …, s_n, CC, L)）を出力する手段と、
を備えたことを特徴とするデジタル署名装置。
【請求項３】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_ｊのリストＬ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）とに基づいて、任意のデジタル情報ｍに対するリング署名を生成するデジタル署名装置であって、
前記署名者の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)を記憶する秘密鍵記憶手段と、
前記デジタル情報ｍ、前記リストL、前記システムパラメータg_1, g_2、乱数r、前記確認者の公開鍵情報c_C, d_C, h_C及びハッシュ関数H_{q}( )に基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L), 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p により、コミットメント情報CC ＝ (u_1, u_2, e, v)を計算する手段（但し、‖は連接を表す）と、
前記システムパラメータg、第１乱数情報α、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_i = g^α mod p 及び式c_{i+1} = H(CC‖T_i)により、第１リング要素情報c_{i+1}を計算する手段と、
ユーザ番号j = i+1, …, n, 1, …, i-1毎に、前記システムパラメータg、ユーザ乱数情報s_j、ユーザ公開鍵情報y_j、第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g^s_j・ y_j^c_j mod p 及び式c_{j+1} mod n = H(CC‖T_j)により、第２リング要素情報c_{j+1} mod n を順次計算する手段と、
前記第１乱数情報α、前記秘密鍵記憶手段内の秘密鍵情報ｘ_i及び署名者に対応するリング要素情報ｃ_iに基づいて、式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ により、署名者関連情報ｓ_iを生成する手段と、
１番目のリング要素情報ｃ_1、前記ユーザ乱数情報s_j、前記署名者関連情報ｓ_i、前記コミットメント情報CC及び前記リストLを含むリング署名σ = (c_1, s_1, …, s_n, CC, L) を出力する手段と、
を備えたことを特徴とするデジタル署名装置。
【請求項４】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_ｊ）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）と、任意のデジタル情報（ｍ）とに基づいて生成されたリング署名（σ）に関し、当該リング署名σを検証する確認者用署名検証装置であって、
前記確認者の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）を記憶する秘密鍵記憶手段と、
前記秘密鍵記憶手段内の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）に基づいて、前記リング署名（σ）を検証する第１検証手段と、
前記リスト（Ｌ）内の公開鍵情報（ｙ_ｊ）に基づいて、前記リング署名（σ）を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする確認者用署名検証装置。
【請求項５】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_ｊのリストＬ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）と、乱数rと、第１乱数情報αと、ハッシュ関数H_{q}( ), H_( )と、ユーザ乱数情報s_jと、任意のデジタル情報ｍとに基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L)（但し、‖は連接を表す）, 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p 、CC ＝ (u_1, u_2, e, v), 式T_i = g^α mod p, 式c_{i+1} = H(CC‖T_i), 式T_j = g^s_j・ y_j^c_j mod p , 式c_{j+1} mod n = H(CC‖T_j) 及び 式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ の計算により生成されたリング署名σ = (c_1, s_1, …, s_n, CC, L) に関し、当該リング署名σを検証する確認者用署名検証装置であって、
前記確認者の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C を記憶する秘密鍵記憶手段と、
前記リング署名σを検証する際に、当該リング署名σ内のコミットメント情報CCと、ハッシュ関数H_{q}とに基づいて、式b = H_{q}(u_1‖u_2‖e)により、コミットメント部分情報bを計算する手段と、
このコミットメント部分情報t、前記秘密鍵記憶手段内の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C 、前記コミットメント情報CC 及び前記システムパラメータgに基づいて、第１式v =u_1＾(x_{c1}+by_{c1})・u2＾(x_{c2}+by_{c2}) mod p 及び第２式g＾{H_{q}(m‖L)} = e/{ u_ 1}＾(s_c) mod pが成り立つことをそれぞれ検証する第１検証手段と、
ユーザ番号j = 1, . . . , n毎に、前記システムパラメータg、前記リング署名σ内のユーザ乱数情報s_j、前記ユーザ公開鍵情報y_j、前記リング署名σ内の第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする確認者用署名検証装置。
【請求項６】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_ｊ）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）と、任意のデジタル情報（ｍ）とに基づいて生成されたリング署名（σ）に関し、確認者用署名検証装置との対話証明を介して当該リング署名（σ）を検証する検証者用署名検証装置であって、
前記リスト（Ｌ＝｛y_1, … , y_n｝）と、前記確認者の複数の公開鍵情報（c_C, d_C, h_C）と、前記デジタル情報（ｍ）と、前記リング署名（σ）とを記憶するための記憶手段と、
前記記憶手段内のリスト（Ｌ）内の公開鍵情報（y_j）に基づいて、前記リング署名（σ）を検証する第１検証手段と、
前記記憶手段内の確認者の公開鍵情報（c_C, d_C, h_C）に基づき、前記確認者用署名検証装置との間の対話証明を介して、前記リング署名（σ）を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする検証者用署名検証装置。
【請求項７】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_ｊのリストＬ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）と、乱数rと、第１乱数情報αと、ハッシュ関数H_{q}( ), H_( )と、ユーザ乱数情報s_jと、任意のデジタル情報ｍとに基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L)（但し、‖は連接を表す）, 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p 、CC ＝ (u_1, u_2, e, v), 式T_i = g^α mod p, 式c_{i+1} = H(CC‖T_i), 式T_j = g^s_j・ y_j^c_j mod p , 式c_{j+1} mod n = H(CC‖T_j) 及び 式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ の計算により生成されたリング署名σ = (c_1, s_1, …, s_n, CC, L) に関し、確認者用署名検証装置との対話証明を介して当該リング署名σを検証する検証者用署名検証装置であって、
前記システムパラメータg, g_1, g_2及び素数ｐ，ｑと、前記リストＬ＝｛y_1, y_2, , … , y_j , … , y_n｝と、前記確認者の公開鍵情報c_C, d_C, h_Cと、前記デジタル情報ｍと、前記リング署名σとを記憶するための記憶手段と、
前記リング署名σを検証する際に、ユーザ番号j = 1, . . . , n毎に、前記システムパラメータg、前記リング署名σ内のユーザ乱数情報s_j、前記ユーザ公開鍵情報y_j、前記リング署名σ内の第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する第１検証手段と、
乱数α_1, β_1を生成すると共に、この乱数α_1, β_1及び前記記憶手段内のシステムパラメータg_1と、前記記憶手段内の公開鍵情報 c＿Cに基づいて、式a_1 = g_1＾α_1・c＿C＾β_1 mod p により計算した値a_1_を前記確認者用検証装置に送信する手段と、
前記確認者用検証装置から値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを受信する手段（但し、ｒ_1 = (g_1＾k_1）(g_2＾k_2）、r_2 = (g_1＾k_3）(g_2＾k_4）、r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)＾k_3)((u_2＾b) ＾k_4) 、r_4 = g_1＾k_5、r_5 = u_1＾k_5、〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、〜r_4 = (u_１)＾(〜k_5)、〜r_5 = e＾(〜k_5)。ここで、k_1、 k_2、 k_3、 k_4 、 k_5、 〜k_1、 〜k_2、〜 k_3、 〜k_4、 〜k_5、 w ∈Z_q ）と、
前記値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wの受信後、前記乱数α_1, β_1を前記確認者用検証装置に送信する手段と、
前記確認者用検証装置により式a_1=g_1^α_1・c＿C＾β_1 mod pが成り立つことが検証された後、前記確認者用検証装置から値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5を受信する手段（但し、s_c1 = k_1 − (β_1 + w)・x_{c1}, s_c2 = k_2 - (β_1 + w)・x_{c2}, s_c3 = k_3 - (β_1 + w)・y_{c1}, s_c4 = k_4 - (β_1 + w)・y_{c2}, s_c5 = k_5 - (β_1 + w)・s_c, 〜s_c1 = 〜k_1 − (β_1 + w)・k_1, 〜s_c2 = 〜k_2 - (β_1 + w)・k_2, 〜s_c3 = 〜k_3 - (β_1 + w)・k_3, 〜s_c4 = 〜k_4 - (β_1 + w)・k_4, 〜s_c5 = 〜k_5 - (β_1 + w)・k_5と、
前記値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5の受信後、当該値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5、前記値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、w、前記記憶手段内の公開鍵情報c_C, d_C, h_C、前記デジタル情報ｍ及び前記リング署名σ = (c_1, s_1, …, s_n, CC, L)に基づいて、式r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) , 式r_ 2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) , 式r_4 = g_1＾{s_c5}・h_C＾(β_1 + w), 式〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ}, 式〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ}, 式〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ}, 式〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},式〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}の式が一つでも成り立たなければ、プロトコルを中止し、すべて成り立つことを確認できたら、r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}の２つの式が両方成り立つ、あるいは、どちらか１つでも成り立たないことを検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする検証者用署名検証装置。
【請求項８】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_j）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）とに基づいて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置に用いられるプログラムであって、
前記デジタル署名装置を、
前記署名者の秘密鍵情報（ｘ_i）を当該デジタル署名装置の秘密鍵記憶手段に書き込む手段、
前記デジタル情報（ｍ）、前記リスト（L）、乱数（r）、前記確認者の公開鍵情報（c_C, d_C, h_C）及びハッシュ関数（H_{q}( )）に基づいて、コミットメント情報（CC）を計算する手段、
第１乱数情報（α）、前記コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第１リング要素情報（c_{i+1}）を計算する手段、
ユーザ番号（j = i+1, …, n, 1, …, i-1）毎に、ユーザ乱数情報（s_j）、ユーザ公開鍵情報（y_j）、第１リング要素情報（c_j）、前記コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第２リング要素情報（c_{j+1} mod n）を順次計算する手段、
前記第１乱数情報（α）、前記秘密鍵記憶手段内の秘密鍵情報（ｘ_i）及び署名者に対応するリング要素情報（ｃ_i）に基づいて、署名者関連情報（ｓ_i）を生成する手段、
１番目のリング要素情報（ｃ_1）、前記ユーザ乱数情報（ｓ_j）、前記署名者関連情報（ｓ_i）、前記コミットメント情報（CC）及び前記リスト（L）を含むリング署名（σ = (c_1, s_1, …, s_n, CC, L)）を出力する手段、
として機能させるためのプログラム。
【請求項９】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_jのリストＬ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）とに基づいて、任意のデジタル情報ｍに対するリング署名を生成するデジタル署名装置に用いられるプログラムであって、
前記デジタル署名装置を、
前記署名者の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)を当該デジタル署名装置の秘密鍵記憶手段に書き込む手段、
前記デジタル情報ｍ、前記リストL、前記システムパラメータg_1, g_2、乱数r、前記確認者の公開鍵情報c_C, d_C, h_C及びハッシュ関数H_{q}( )に基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L), 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p により、コミットメント情報CC ＝ (u_1, u_2, e, v)を計算する手段（但し、‖は連接を表す）、
前記システムパラメータg、第１乱数情報α、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_i = g^α mod p 及び式c_{i+1} = H(CC‖T_i)により、第１リング要素情報c_{i+1}を計算する手段、
ユーザ番号j = i+1, …, n, 1, …, i-1毎に、前記システムパラメータg、ユーザ乱数情報s_j、ユーザ公開鍵情報y_j、第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g^s_j・ y_j^c_j mod p 及び式c_{j+1} mod n = H(CC‖T_j)により、第２リング要素情報c_{j+1} mod n を順次計算する手段、
前記第１乱数情報α、前記秘密鍵記憶手段内の秘密鍵情報ｘ_i及び署名者に対応するリング要素情報ｃ_iに基づいて、式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ により、署名者関連情報ｓ_iを生成する手段、
１番目のリング要素情報ｃ_1、前記ユーザ乱数情報s_j、前記署名者関連情報ｓ_i、前記コミットメント情報CC及び前記リストLを含むリング署名σ = (c_1, s_1, …, s_n, CC, L) を出力する手段、
として機能させるためのプログラム。
【請求項１０】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_j）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）と、任意のデジタル情報（ｍ）とに基づいて生成されたリング署名（σ）に関し、当該リング署名σを検証する確認者用署名検証装置に用いられるプログラムであって、
前記確認者用署名検証装置を、
前記確認者の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）を当該確認者用署名検証装置の秘密鍵記憶手段に書き込む手段、
前記秘密鍵記憶手段内の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）に基づいて、前記リング署名（σ）を検証する第１検証手段、
前記リスト（Ｌ）内の公開鍵情報（ｙ_j）に基づいて、前記リング署名（σ）を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１１】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_jのリストＬ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）と、乱数rと、第１乱数情報αと、ハッシュ関数H_{q}( ), H_( )と、ユーザ乱数情報s_jと、任意のデジタル情報ｍとに基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L)（但し、‖は連接を表す）, 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p 、CC ＝ (u_1, u_2, e, v), 式T_i = g^α mod p, 式c_{i+1} = H(CC‖T_i), 式T_j = g^s_j・ y_j^c_j mod p , 式c_{j+1} mod n = H(CC‖T_j) 及び 式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ の計算により生成されたリング署名σ = (c_1, s_1, …, s_n, CC, L) に関し、当該リング署名σを検証する確認者用署名検証装置に用いられるプログラムであって、
前記確認者用署名検証装置を、
前記確認者の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C を当該確認者用署名検証装置の秘密鍵記憶手段に書き込む手段、
前記リング署名σを検証する際に、当該リング署名σ内のコミットメント情報CCと、ハッシュ関数H_{q}とに基づいて、式b = H_{q}(u_1‖u_2‖e)により、コミットメント部分情報bを計算する手段、
このコミットメント部分情報t、前記秘密鍵記憶手段内の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C 、前記コミットメント情報CC 及び前記システムパラメータgに基づいて、第１式v =u_1＾(x_{c1}+by_{c1})・u2＾(x_{c2}+by_{c2}) mod p 及び第２式g＾{H_{q}(m‖L)} = e/{ u_ 1}＾(s_c) mod pが成り立つことをそれぞれ検証する第１検証手段、
ユーザ番号j = 1, . . . , n毎に、前記システムパラメータg、前記リング署名σ内のユーザ乱数情報s_j、前記ユーザ公開鍵情報y_j、前記リング署名σ内の第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１２】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_j）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）と、任意のデジタル情報（ｍ）とに基づいて生成されたリング署名（σ）に関し、確認者用署名検証装置との対話証明を介して当該リング署名（σ）を検証する検証者用署名検証装置に用いられるプログラムであって、
前記検証者用署名検証装置を、
前記リスト（Ｌ＝｛y_1, … , y_n｝）と、前記確認者の複数の公開鍵情報（c_C, d_C, h_C）と、前記デジタル情報（ｍ）と、前記リング署名（σ）とを当該検証者用署名検証装置の記憶手段に書き込む手段、
前記記憶手段内のリスト（Ｌ）内の公開鍵情報（y_j）に基づいて、前記リング署名（σ）を検証する第１検証手段、
前記記憶手段内の確認者の公開鍵情報（c_C, d_C, h_C）に基づき、前記確認者用署名検証装置との間の対話証明を介して、前記リング署名（σ）を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１３】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_jのリストＬ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）と、乱数rと、第１乱数情報αと、ハッシュ関数H_{q}( ), H_( )と、ユーザ乱数情報s_jと、任意のデジタル情報ｍとに基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L)（但し、‖は連接を表す）, 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p 、CC ＝ (u_1, u_2, e, v), 式T_i = g^α mod p, 式c_{i+1} = H(CC‖T_i), 式T_j = g^s_j・ y_j^c_j mod p , 式c_{j+1} mod n = H(CC‖T_j) 及び 式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ の計算により生成されたリング署名σ = (c_1, s_1, …, s_n, CC, L) に関し、確認者用署名検証装置との対話証明を介して当該リング署名σを検証する検証者用署名検証装置に用いられるプログラムであって、
前記検証者用署名検証装置を、
前記システムパラメータg, g_1, g_2及び素数ｐ，ｑと、前記リストＬ＝｛y_1, y_2, , … , y_j , … , y_n｝と、前記確認者の公開鍵情報c_C, d_C, h_Cと、前記デジタル情報ｍと、前記リング署名σとを当該検証者用署名検証装置の記憶手段に書き込む手段、
前記リング署名σを検証する際に、ユーザ番号j = 1, . . . , n毎に、前記システムパラメータg、前記リング署名σ内のユーザ乱数情報s_j、前記ユーザ公開鍵情報y_j、前記リング署名σ内の第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する第１検証手段、
乱数α_1、 β_1 を生成すると共に、この乱数α_1, β_1及び前記記憶手段内のシステムパラメータg_1と、前記記憶手段内の公開鍵情報c＿Cに基づいて、式a_1 = g_1＾α_1・c＿C＾β_1 mod p により計算した値a_1を前記確認者用検証装置に送信する手段、
前記確認者用検証装置から値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを受信する手段（（但し、ｒ_1 = (g_1＾k_1）(g_2＾k_2）、r_2 = (g_1＾k_3）(g_2＾k_4）、r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、r_4 = g_1＾k_5、r_5 = u_1＾k_5、〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、〜r_4 = (u_１)＾(〜k_5)、〜r_5 = e＾(〜k_5)。ここで、k_1、 k_2、 k_3、 k_4 、 k_5、 〜k_1、 〜k_2、〜 k_3、 〜k_4、 〜k_5、 w ∈Z_q ）、
前記値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wの受信後、前記乱数α_1、 β_1を前記確認者用検証装置に送信する手段、
前記確認者用検証装置により式a_1=g_1^α_1・c＿C＾β_1 mod pが成り立つことが検証された後、前記確認者用検証装置から値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5を受信する手段（但し、s_c1 = k_1 − (β_1 + w)・x_{c1}, s_c2 = k_2 - (β_1 + w)・x_{c2}, s_c3 = k_3 - (β_1 + w)・y_{c1}, s_c4 = k_4 - (β_1 + w)・y_{c2}, s_c5 = k_5 - (β_1 + w)・s_c, 〜s_c1 = 〜k_1 − (β_1 + w)・k_1, 〜s_c2 = 〜k_2 - (β_1 + w)・k_2, 〜s_c3 = 〜k_3 - (β_1 + w)・k_3, 〜s_c4 = 〜k_4 - (β_1 + w)・k_4, 〜s_c5 = 〜k_5 - (β_1 + w)・k_5）、
前記値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5の受信後、当該値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5、前記値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、w、前記記憶手段内の公開鍵情報c_C, d_C, h_C、前記デジタル情報ｍ及び前記リング署名σ = (c_1, s_1, …, s_n, CC, L)に基づいて、式r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) , 式r_ 2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) , 式r_4 = g_1＾{s_c5}・h_C＾(β_1 + w), 式〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ}, 式〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ}, 式〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ}, 式〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},式〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}の式が成り立つことを確認した後、r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}の２つの式が両方成り立つか、どちらか１つでも成り立たないことを検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１】
署名者としてのユーザに固有の秘密鍵情報（x_i）及びこの署名者を含み当該署名者が選択した他の複数のユーザの公開鍵情報（y_1, y_2, … y_n）及び前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）を用いて、任意のデジタル情報（m）に対するリング署名を生成するデジタル署名装置と、
前記確認者の複数の公開鍵情報（c_C, d_C, h_C）に対応する複数の秘密鍵情報（x_C1, x_C2, y_C1, y_C2, s_C）に基づいて、当該リング署名を検証する確認者用署名検証装置と、
前記確認者用署名検証装置との間の対話証明を介して、当該リング署名を検証する検証者用署名検証装置と、
を備えたことを特徴とするデジタル署名システム。
【請求項２】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_ｊ）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n））と、当該署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）とに基づいて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置であって、
当該署名者の秘密鍵情報（ｘ_i）を記憶する秘密鍵記憶手段と、
前記デジタル情報（ｍ）、前記リスト（L）、乱数（r）、前記指名した確認者の公開鍵情報（c_C, d_C, h_C）及びハッシュ関数（H_{q}( )）に基づいて、コミットメント情報（CC）を計算する手段と、
第１乱数情報（α）、前記コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第１リング要素情報（c_{i+1}）を計算する手段と、
ユーザ番号（j = i+1, …, n, 1, …, i-1）毎に、ユーザ乱数情報（s_j）、ユーザ公開鍵情報（y_j）、第１リング要素情報（c_j）、前記コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第２リング要素情報（c_{j+1} mod n）を順次計算する手段と、
前記第１乱数情報（α）、前記秘密鍵記憶手段内の秘密鍵情報（ｘ_i）及び署名者に対応するリング要素情報（ｃ_i）に基づいて、署名者関連情報（ｓ_i）を生成する手段と、
１番目のリング要素情報（ｃ_1）、前記ユーザ乱数情報（ｓ_j）、前記署名者関連情報（ｓ_i）、前記コミットメント情報（CC）及び前記リスト（L）を含むリング署名（σ = (c_1, s_1, …, s_n, CC, L)）を出力する手段と、
を備えたことを特徴とするデジタル署名装置。
【請求項３】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_ｊのリストＬ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）とに基づいて、任意のデジタル情報ｍに対するリング署名を生成するデジタル署名装置であって、
前記署名者の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)を記憶する秘密鍵記憶手段と、
前記デジタル情報ｍ、前記リストL、前記システムパラメータg_1, g_2、乱数r、前記確認者の公開鍵情報c_C, d_C, h_C及びハッシュ関数H_{q}( )に基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L), 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p により、コミットメント情報CC ＝ (u_1, u_2, e, v)を計算する手段（但し、‖は連接を表す）と、
前記システムパラメータg、第１乱数情報α、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_i = g^α mod p 及び式c_{i+1} = H(CC‖T_i)により、第１リング要素情報c_{i+1}を計算する手段と、
ユーザ番号j = i+1, …, n, 1, …, i-1毎に、前記システムパラメータg、ユーザ乱数情報s_j、ユーザ公開鍵情報y_j、第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g^s_j・ y_j^c_j mod p 及び式c_{j+1} mod n = H(CC‖T_j)により、第２リング要素情報c_{j+1} mod n を順次計算する手段と、
前記第１乱数情報α、前記秘密鍵記憶手段内の秘密鍵情報ｘ_i及び署名者に対応するリング要素情報ｃ_iに基づいて、式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ により、署名者関連情報ｓ_iを生成する手段と、
１番目のリング要素情報ｃ_1、前記ユーザ乱数情報s_j、前記署名者関連情報ｓ_i、前記コミットメント情報CC及び前記リストLを含むリング署名σ = (c_1, s_1, …, s_n, CC, L) を出力する手段と、
を備えたことを特徴とするデジタル署名装置。
【請求項４】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_ｊ）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）と、任意のデジタル情報（ｍ）とに基づいて生成されたリング署名（σ）に関し、当該リング署名σを検証する確認者用署名検証装置であって、
前記確認者の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）を記憶する秘密鍵記憶手段と、
前記秘密鍵記憶手段内の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）に基づいて、前記リング署名（σ）を検証する第１検証手段と、
前記リスト（Ｌ）内の公開鍵情報（ｙ_ｊ）に基づいて、前記リング署名（σ）を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする確認者用署名検証装置。
【請求項５】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_ｊのリストＬ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）と、乱数rと、第１乱数情報αと、ハッシュ関数H_{q}( ), H_( )と、ユーザ乱数情報s_jと、任意のデジタル情報ｍとに基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L)（但し、‖は連接を表す）, 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p 、CC ＝ (u_1, u_2, e, v), 式T_i = g^α mod p, 式c_{i+1} = H(CC‖T_i), 式T_j = g^s_j・ y_j^c_j mod p , 式c_{j+1} mod n = H(CC‖T_j) 及び 式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ の計算により生成されたリング署名σ = (c_1, s_1, …, s_n, CC, L) に関し、当該リング署名σを検証する確認者用署名検証装置であって、
前記確認者の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C を記憶する秘密鍵記憶手段と、
前記リング署名σを検証する際に、当該リング署名σ内のコミットメント情報CCと、ハッシュ関数H_{q}とに基づいて、式b = H_{q}(u_1‖u_2‖e)により、コミットメント部分情報bを計算する手段と、
このコミットメント部分情報t、前記秘密鍵記憶手段内の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C 、前記コミットメント情報CC 及び前記システムパラメータgに基づいて、第１式v =u_1＾(x_{c1}+by_{c1})・u2＾(x_{c2}+by_{c2}) mod p 及び第２式g＾{H_{q}(m‖L)} = e/{ u_ 1}＾(s_c) mod pが成り立つことをそれぞれ検証する第１検証手段と、
ユーザ番号j = 1, . . . , n毎に、前記システムパラメータg、前記リング署名σ内のユーザ乱数情報s_j、前記ユーザ公開鍵情報y_j、前記リング署名σ内の第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする確認者用署名検証装置。
【請求項６】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_ｊ）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）と、任意のデジタル情報（ｍ）とに基づいて生成されたリング署名（σ）に関し、確認者用署名検証装置との対話証明を介して当該リング署名（σ）を検証する検証者用署名検証装置であって、
前記リスト（Ｌ＝｛y_1, … , y_n｝）と、前記確認者の複数の公開鍵情報（c_C, d_C, h_C）と、前記デジタル情報（ｍ）と、前記リング署名（σ）とを記憶するための記憶手段と、
前記記憶手段内のリスト（Ｌ）内の公開鍵情報（y_j）に基づいて、前記リング署名（σ）を検証する第１検証手段と、
前記記憶手段内の確認者の公開鍵情報（c_C, d_C, h_C）に基づき、前記確認者用署名検証装置との間の対話証明を介して、前記リング署名（σ）を検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする検証者用署名検証装置。
【請求項７】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_ｊのリストＬ＝｛y_1, y_2, … , y_n｝（但しｊ = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）と、乱数rと、第１乱数情報αと、ハッシュ関数H_{q}( ), H_( )と、ユーザ乱数情報s_jと、任意のデジタル情報ｍとに基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L)（但し、‖は連接を表す）, 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p 、CC ＝ (u_1, u_2, e, v), 式T_i = g^α mod p, 式c_{i+1} = H(CC‖T_i), 式T_j = g^s_j・ y_j^c_j mod p , 式c_{j+1} mod n = H(CC‖T_j) 及び 式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ の計算により生成されたリング署名σ = (c_1, s_1, …, s_n, CC, L) に関し、確認者用署名検証装置との対話証明を介して当該リング署名σを検証する検証者用署名検証装置であって、
前記システムパラメータg, g_1, g_2及び素数ｐ，ｑと、前記リストＬ＝｛y_1, y_2, , … , y_j , … , y_n｝と、前記確認者の公開鍵情報c_C, d_C, h_Cと、前記デジタル情報ｍと、前記リング署名σとを記憶するための記憶手段と、
前記リング署名σを検証する際に、ユーザ番号j = 1, . . . , n毎に、前記システムパラメータg、前記リング署名σ内のユーザ乱数情報s_j、前記ユーザ公開鍵情報y_j、前記リング署名σ内の第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する第１検証手段と、
乱数α_1, β_1を生成すると共に、この乱数α_1, β_1及び前記記憶手段内のシステムパラメータg_1と、前記記憶手段内の公開鍵情報 c＿Cに基づいて、式a_1 = g_1＾α_1・c＿C＾β_1 mod p により計算した値a_1_を前記確認者用検証装置に送信する手段と、
前記確認者用検証装置から値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを受信する手段（但し、ｒ_1 = (g_1＾k_1）(g_2＾k_2）、r_2 = (g_1＾k_3）(g_2＾k_4）、r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)＾k_3)((u_2＾b) ＾k_4) 、r_4 = g_1＾k_5、r_5 = u_1＾k_5、〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、〜r_4 = (u_１)＾(〜k_5)、〜r_5 = e＾(〜k_5)。ここで、k_1、 k_2、 k_3、 k_4 、 k_5、 〜k_1、 〜k_2、〜 k_3、 〜k_4、 〜k_5、 w ∈Z_q ）と、
前記値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wの受信後、前記乱数α_1, β_1を前記確認者用検証装置に送信する手段と、
前記確認者用検証装置により式a_1=g_1^α_1・c＿C＾β_1 mod pが成り立つことが検証された後、前記確認者用検証装置から値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5を受信する手段（但し、s_c1 = k_1 − (β_1 + w)・x_{c1}, s_c2 = k_2 - (β_1 + w)・x_{c2}, s_c3 = k_3 - (β_1 + w)・y_{c1}, s_c4 = k_4 - (β_1 + w)・y_{c2}, s_c5 = k_5 - (β_1 + w)・s_c, 〜s_c1 = 〜k_1 − (β_1 + w)・k_1, 〜s_c2 = 〜k_2 - (β_1 + w)・k_2, 〜s_c3 = 〜k_3 - (β_1 + w)・k_3, 〜s_c4 = 〜k_4 - (β_1 + w)・k_4, 〜s_c5 = 〜k_5 - (β_1 + w)・k_5と、
前記値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5の受信後、当該値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5、前記値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、w、前記記憶手段内の公開鍵情報c_C, d_C, h_C、前記デジタル情報ｍ及び前記リング署名σ = (c_1, s_1, …, s_n, CC, L)に基づいて、式r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) , 式r_ 2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) , 式r_4 = g_1＾{s_c5}・h_C＾(β_1 + w), 式〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ}, 式〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ}, 式〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ}, 式〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},式〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}の式が一つでも成り立たなければ、プロトコルを中止し、すべて成り立つことを確認できたら、r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}の２つの式が両方成り立つ、あるいは、どちらか１つでも成り立たないことを検証する第２検証手段と、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段と、
を備えたことを特徴とする検証者用署名検証装置。
【請求項８】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_j）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）とに基づいて、任意のデジタル情報（ｍ）に対するリング署名を生成するデジタル署名装置に用いられるプログラムであって、
前記デジタル署名装置を、
前記署名者の秘密鍵情報（ｘ_i）を当該デジタル署名装置の秘密鍵記憶手段に書き込む手段、
前記デジタル情報（ｍ）、前記リスト（L）、乱数（r）、前記確認者の公開鍵情報（c_C, d_C, h_C）及びハッシュ関数（H_{q}( )）に基づいて、コミットメント情報（CC）を計算する手段、
第１乱数情報（α）、前記コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第１リング要素情報（c_{i+1}）を計算する手段、
ユーザ番号（j = i+1, …, n, 1, …, i-1）毎に、ユーザ乱数情報（s_j）、ユーザ公開鍵情報（y_j）、第１リング要素情報（c_j）、前記コミットメント情報（CC）及びハッシュ関数（H( )）に基づいて、第２リング要素情報（c_{j+1} mod n）を順次計算する手段、
前記第１乱数情報（α）、前記秘密鍵記憶手段内の秘密鍵情報（ｘ_i）及び署名者に対応するリング要素情報（ｃ_i）に基づいて、署名者関連情報（ｓ_i）を生成する手段、
１番目のリング要素情報（ｃ_1）、前記ユーザ乱数情報（ｓ_j）、前記署名者関連情報（ｓ_i）、前記コミットメント情報（CC）及び前記リスト（L）を含むリング署名（σ = (c_1, s_1, …, s_n, CC, L)）を出力する手段、
として機能させるためのプログラム。
【請求項９】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_jのリストＬ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）とに基づいて、任意のデジタル情報ｍに対するリング署名を生成するデジタル署名装置に用いられるプログラムであって、
前記デジタル署名装置を、
前記署名者の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)を当該デジタル署名装置の秘密鍵記憶手段に書き込む手段、
前記デジタル情報ｍ、前記リストL、前記システムパラメータg_1, g_2、乱数r、前記確認者の公開鍵情報c_C, d_C, h_C及びハッシュ関数H_{q}( )に基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L), 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p により、コミットメント情報CC ＝ (u_1, u_2, e, v)を計算する手段（但し、‖は連接を表す）、
前記システムパラメータg、第１乱数情報α、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_i = g^α mod p 及び式c_{i+1} = H(CC‖T_i)により、第１リング要素情報c_{i+1}を計算する手段、
ユーザ番号j = i+1, …, n, 1, …, i-1毎に、前記システムパラメータg、ユーザ乱数情報s_j、ユーザ公開鍵情報y_j、第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g^s_j・ y_j^c_j mod p 及び式c_{j+1} mod n = H(CC‖T_j)により、第２リング要素情報c_{j+1} mod n を順次計算する手段、
前記第１乱数情報α、前記秘密鍵記憶手段内の秘密鍵情報ｘ_i及び署名者に対応するリング要素情報ｃ_iに基づいて、式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ により、署名者関連情報ｓ_iを生成する手段、
１番目のリング要素情報ｃ_1、前記ユーザ乱数情報s_j、前記署名者関連情報ｓ_i、前記コミットメント情報CC及び前記リストLを含むリング署名σ = (c_1, s_1, …, s_n, CC, L) を出力する手段、
として機能させるためのプログラム。
【請求項１０】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_j）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）と、任意のデジタル情報（ｍ）とに基づいて生成されたリング署名（σ）に関し、当該リング署名σを検証する確認者用署名検証装置に用いられるプログラムであって、
前記確認者用署名検証装置を、
前記確認者の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）を当該確認者用署名検証装置の秘密鍵記憶手段に書き込む手段、
前記秘密鍵記憶手段内の複数の秘密鍵情報（x_C1、x_C2、y_C1、y_C2、s_C）に基づいて、前記リング署名（σ）を検証する第１検証手段、
前記リスト（Ｌ）内の公開鍵情報（ｙ_j）に基づいて、前記リング署名（σ）を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１１】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_jのリストＬ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）と、乱数rと、第１乱数情報αと、ハッシュ関数H_{q}( ), H_( )と、ユーザ乱数情報s_jと、任意のデジタル情報ｍとに基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L)（但し、‖は連接を表す）, 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p 、CC ＝ (u_1, u_2, e, v), 式T_i = g^α mod p, 式c_{i+1} = H(CC‖T_i), 式T_j = g^s_j・ y_j^c_j mod p , 式c_{j+1} mod n = H(CC‖T_j) 及び 式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ の計算により生成されたリング署名σ = (c_1, s_1, …, s_n, CC, L) に関し、当該リング署名σを検証する確認者用署名検証装置に用いられるプログラムであって、
前記確認者用署名検証装置を、
前記確認者の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C を当該確認者用署名検証装置の秘密鍵記憶手段に書き込む手段、
前記リング署名σを検証する際に、当該リング署名σ内のコミットメント情報CCと、ハッシュ関数H_{q}とに基づいて、式b = H_{q}(u_1‖u_2‖e)により、コミットメント部分情報bを計算する手段、
このコミットメント部分情報t、前記秘密鍵記憶手段内の秘密鍵情報x_C1、x_C2、y_C1、y_C2、s_C 、前記コミットメント情報CC 及び前記システムパラメータgに基づいて、第１式v =u_1＾(x_{c1}+by_{c1})・u2＾(x_{c2}+by_{c2}) mod p 及び第２式g＾{H_{q}(m‖L)} = e/{ u_ 1}＾(s_c) mod pが成り立つことをそれぞれ検証する第１検証手段、
ユーザ番号j = 1, . . . , n毎に、前記システムパラメータg、前記リング署名σ内のユーザ乱数情報s_j、前記ユーザ公開鍵情報y_j、前記リング署名σ内の第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１２】
署名者としてのユーザに固有の秘密鍵情報（ｘ_i）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報（ｙ_j）のリスト（Ｌ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n））と、前記署名者が指名した確認者の複数の公開鍵情報（c_C, d_C, h_C）と、任意のデジタル情報（ｍ）とに基づいて生成されたリング署名（σ）に関し、確認者用署名検証装置との対話証明を介して当該リング署名（σ）を検証する検証者用署名検証装置に用いられるプログラムであって、
前記検証者用署名検証装置を、
前記リスト（Ｌ＝｛y_1, … , y_n｝）と、前記確認者の複数の公開鍵情報（c_C, d_C, h_C）と、前記デジタル情報（ｍ）と、前記リング署名（σ）とを当該検証者用署名検証装置の記憶手段に書き込む手段、
前記記憶手段内のリスト（Ｌ）内の公開鍵情報（y_j）に基づいて、前記リング署名（σ）を検証する第１検証手段、
前記記憶手段内の確認者の公開鍵情報（c_C, d_C, h_C）に基づき、前記確認者用署名検証装置との間の対話証明を介して、前記リング署名（σ）を検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【請求項１３】
公開されているシステムパラメータg, g_1, g_2（但し、_は下付文字を表す）及び素数ｐ，ｑと、署名者としてのユーザに固有の秘密鍵情報ｘ_i＝log_{g}(ｙ_i)（但し、y_iは署名者の公開鍵情報を表す）と、この署名者を含み当該署名者が選択した複数のユーザの公開鍵情報ｙ_jのリストＬ＝｛y_1, y_2, … , y_n｝（但しj = 1, 2, …, n）と、前記署名者が指名した確認者の公開鍵情報c_C ＝ {g_1}^{x_C1}・{g_2}^{x_C2} mod p、d_C＝{g_1}^{y_C1}・{g_2}^{y_C2} mod p、h_C ＝ {g_1}^{s_C} mod p （但し、 ^ は、べき乗を表す。 x_C1、x_C2、y_C1、y_C2、s_C は確認者の秘密鍵情報を表す）と、乱数rと、第１乱数情報αと、ハッシュ関数H_{q}( ), H_( )と、ユーザ乱数情報s_jと、任意のデジタル情報ｍとに基づいて、式u_1 = g_1＾r mod p, 式u_2 = g_2＾r mod p, 式e =h_C＾ｒ・g_1＾H_{q}(m‖L)（但し、‖は連接を表す）, 式b =H_{q}(u_1‖u_2‖e), 式v =c_C＾r・d_C＾rb mod p 、CC ＝ (u_1, u_2, e, v), 式T_i = g^α mod p, 式c_{i+1} = H(CC‖T_i), 式T_j = g^s_j・ y_j^c_j mod p , 式c_{j+1} mod n = H(CC‖T_j) 及び 式 ｓ_i ＝ α − ｘ_i・ｃ_i mod ｑ の計算により生成されたリング署名σ = (c_1, s_1, …, s_n, CC, L) に関し、確認者用署名検証装置との対話証明を介して当該リング署名σを検証する検証者用署名検証装置に用いられるプログラムであって、
前記検証者用署名検証装置を、
前記システムパラメータg, g_1, g_2及び素数ｐ，ｑと、前記リストＬ＝｛y_1, y_2, , … , y_j , … , y_n｝と、前記確認者の公開鍵情報c_C, d_C, h_Cと、前記デジタル情報ｍと、前記リング署名σとを当該検証者用署名検証装置の記憶手段に書き込む手段、
前記リング署名σを検証する際に、ユーザ番号j = 1, . . . , n毎に、前記システムパラメータg、前記リング署名σ内のユーザ乱数情報s_j、前記ユーザ公開鍵情報y_j、前記リング署名σ内の第１リング要素情報c_j 、前記コミットメント情報CC及びハッシュ関数H( )に基づいて、式T_j = g＾s_j・ y_j＾c_j mod p 及び式c_(j+１) = H(CC‖T_j)を順次計算することにより、式c_1 = c_(n+1)が成り立つことを検証する第１検証手段、
乱数α_1、 β_1 を生成すると共に、この乱数α_1, β_1及び前記記憶手段内のシステムパラメータg_1と、前記記憶手段内の公開鍵情報c＿Cに基づいて、式a_1 = g_1＾α_1・c＿C＾β_1 mod p により計算した値a_1を前記確認者用検証装置に送信する手段、
前記確認者用検証装置から値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wを受信する手段（（但し、ｒ_1 = (g_1＾k_1）(g_2＾k_2）、r_2 = (g_1＾k_3）(g_2＾k_4）、r_3 = (u_1＾k_1) (u_2＾k_2) ((u_1＾b)k_3)((u_2＾b)k_4) 、r_4 = g_1＾k_5、r_5 = u_1＾k_5、〜r_1 = (g_1^(〜k_1)) (g_2^(〜k_2))、〜r_2 = (g_1^(〜k_3)) (g_2^(〜k_4))、〜r_3 = (g_1^(〜k_1)) (g_2^(〜k_2))(u_1＾b)^( 〜k_3) (u_2＾b)^( 〜k_4)、〜r_4 = (u_１)＾(〜k_5)、〜r_5 = e＾(〜k_5)。ここで、k_1、 k_2、 k_3、 k_4 、 k_5、 〜k_1、 〜k_2、〜 k_3、 〜k_4、 〜k_5、 w ∈Z_q ）、
前記値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、wの受信後、前記乱数α_1、 β_1を前記確認者用検証装置に送信する手段、
前記確認者用検証装置により式a_1=g_1^α_1・c＿C＾β_1 mod pが成り立つことが検証された後、前記確認者用検証装置から値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5を受信する手段（但し、s_c1 = k_1 − (β_1 + w)・x_{c1}, s_c2 = k_2 - (β_1 + w)・x_{c2}, s_c3 = k_3 - (β_1 + w)・y_{c1}, s_c4 = k_4 - (β_1 + w)・y_{c2}, s_c5 = k_5 - (β_1 + w)・s_c, 〜s_c1 = 〜k_1 − (β_1 + w)・k_1, 〜s_c2 = 〜k_2 - (β_1 + w)・k_2, 〜s_c3 = 〜k_3 - (β_1 + w)・k_3, 〜s_c4 = 〜k_4 - (β_1 + w)・k_4, 〜s_c5 = 〜k_5 - (β_1 + w)・k_5）、
前記値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5の受信後、当該値s_c1, s_c2, s_c3, s_c4,s_c5, 〜s_c1, 〜s_c2, 〜s_c3, 〜s_c4, 〜s_c5、前記値r_1、r_2、r_3、r_4、r_5、 〜r_1、 〜r_2、〜r_3、 〜r_4、〜r_5、w、前記記憶手段内の公開鍵情報c_C, d_C, h_C、前記デジタル情報ｍ及び前記リング署名σ = (c_1, s_1, …, s_n, CC, L)に基づいて、式r_1 = g_1^{s_c1}・g_2^{s_c2}・c＾(β_1 + w) , 式r_ 2 =(g_1)^{s_c3}・(g_2)＾{s_c4}・(d＾(β_1 + w)) , 式r_4 = g_1＾{s_c5}・h_C＾(β_1 + w), 式〜r_1 = g_1＾{〜s_c1} g_2＾{〜s_c2}・r_1＾{{β_1}＋ｗ}, 式〜r_2 = g_1＾{〜s_c3}・g_2＾{〜s_c4}・r_2^{{β_1}＋ｗ}, 式〜r_3 = u_1＾{〜s_c1}・u_2＾{〜s_c2} (u_1^b)＾{〜s_c3}・(u_2^b)＾{〜s_c4}・ r_3＾{{β_1}＋ｗ}, 式〜r_4 = g_1＾{s_c5}・r_4＾{{β_1}＋ｗ},式〜r_5 = u_1＾{s_c5}・r_5＾{{β_1}＋ｗ}の式が成り立つことを確認した後、r_3 = u_1＾{s_c1}・u_2＾{s_c2}・(u_1^b)＾{s_c3}・(u_2^b) ＾{s_c4}・v^{{β_1}＋ｗ},r_5 = u_1＾{s_c5}・(eh_C＾{H_ｑ(m‖L)})＾{{β_1}+w}の２つの式が両方成り立つか、どちらか１つでも成り立たないことを検証する第２検証手段、
前記第１及び第２検証手段による検証に合格したとき、前記リング署名を受理するリング署名受理手段、
として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００９−２２５３５６（Ｐ２００９−２２５３５６Ａ）
【公開日】平成２１年１０月１日（２００９．１０．１）
【国際特許分類】
【出願番号】特願２００８−７０２３５（Ｐ２００８−７０２３５）
【出願日】平成２０年３月１８日（２００８．３．１８）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ２００７年１０月３１日 社団法人情報処理学会発行の「情報処理学会シンポジウムシリーズＶｏｌ．２００７，Ｎｏ．１０ コンピュータセキュリティシンポジウム２００７」に発表
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成２１年１０月１日（２００９．１０．１）
【国際特許分類】
【出願日】平成２０年３月１８日（２００８．３．１８）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ２００７年１０月３１日 社団法人情報処理学会発行の「情報処理学会シンポジウムシリーズＶｏｌ．２００７，Ｎｏ．１０ コンピュータセキュリティシンポジウム２００７」に発表
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]