(57)【要約】【課題】匿名署名に使用できる署名方式の多様性を向上させつつ、署名協力者数の自由度をも確保する。【解決手段】ｋ−ｏｕｔ−ｏｆ−ｎ匿名署名の構成において、少なくとも一部の署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）として、Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数を用い、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として、二項演算ａ（＋）ｉｂ及びａ（−）ｉｂを（ａ（＋）ｉｂ）（−）ｉｂ＝ａを満たす演算とした場合における、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）を用い、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）として、Ｆｉの逆置換関数をＩｉとした場合におけるＩｉ（ｓｋ，ｃ（＋）ｉｒ）を用いる。そして、署名権能者が使用する署名方式に応じ、コミットメント作成関数Ａｉ（ｓｋ，ｒ）、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）及び回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）を切替て匿名署名の作成及び検証を行う。【選択図】        図１
2004312512.tif 000002
【特許請求の範囲】
【請求項１】
署名権能者であるが実際には署名に協力しない非署名者に対応する任意な数ｓｉを生成する（ｉは各署名権能者に対応する識別子。以下同様。）第１の任意数生成手段と、
上記非署名者に対応する任意な整数ｚｉを生成する第２の任意数生成手段と、
上記第２の任意数生成手段によって生成された上記整数ｚｉのハッシュ値ｃｉ’を求める第１のハッシュ関数演算手段と、
上記非署名者の公開鍵ｐｋｉを抽出する公開鍵抽出手段と、
上記第１の公開鍵抽出手段で抽出された上記公開鍵ｐｋｉ、上記第１の任意数生成手段によって生成された上記任意な数ｓｉ、及び上記第１のハッシュ関数演算手段によって算出されたハッシュ値ｃｉ’を、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）に代入する擬似コミットメント作成手段と、
署名権能者であり実際に署名に協力する署名者に対応する任意な数ｒｉを生成する第３の任意数生成手段と、
上記署名者に対応する秘密鍵ｓｋｉを抽出する秘密鍵抽出手段と、
上記秘密鍵抽出手段において抽出された上記秘密鍵ｓｋｉ、及び上記第３の任意数生成手段によって生成された上記任意な数ｒｉを、コミットメント作成関数Ａｉ（ｓｋ，ｒ）に代入するコミットメント作成手段と、
少なくとも上記擬似コミットメント作成手段による演算結果と上記コミットメント作成手段における演算結果とをビット結合し、そのビット結合結果のハッシュ値ｃ０を求める第２のハッシュ関数演算手段と、
上記署名権能者の人数をｎとし、上記署名者の人数をｋとし、上記第１のハッシュ関数演算手段において求められた全ての上記ハッシュ値ｃｉ’に対する（ｉ，ｃｉ’）及び上記第２のハッシュ関数演算手段において求められた上記ハッシュ値ｃ０に対する（０，ｃ０）を（Ｘ，Ｙ）平面上の点とした場合における、これらの点全てを通るｎ−ｋ次の一変数多項式Ｐ（Ｘ）を算出する多項式算出手段と、
上記署名者に対応する上記識別子ｉを、上記多項式算出手段において算出された上記一変数多項式Ｐ（Ｘ）に代入し、その演算結果Ｐ（ｉ）のハッシュ値ｃｉを求める第３のハッシュ関数演算手段と、
上記秘密鍵抽出手段において抽出された上記秘密鍵ｓｋｉ、上記第３の任意数生成手段によって生成された上記任意な数ｒｉ、及び上記第３のハッシュ関数演算手段によって求められた上記ハッシュ値ｃｉを、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）に代入する回復演算手段と、
少なくとも、上記多項式算出手段によって算出された上記一変数多項式Ｐ（Ｘ）を特定するための多項式情報Ｐ’、上記第１の任意数生成手段によって生成された上記任意な数ｓｉ、及び上記回復演算手段による演算結果ｓｉを出力する署名出力手段と、
を有し、
少なくとも一部の上記署名権能者に対応する、上記コミットメント作成関数Ａｉ（ｓｋ，ｒ）は、Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数であり、上記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）は、上記識別子ｉに対応する落とし戸付き一方向性置換関数をＦｉとし、二項演算ａ（＋）ｉｂ及びａ（−）ｉｂを（ａ（＋）ｉｂ）（−）ｉｂ＝ａを満たす演算とした場合における、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）であり、上記回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）は、上記Ｆｉの逆置換関数をＩｉとした場合におけるＩｉ（ｓｋ，ｃ（＋）ｉｒ）であること、
を特徴とする匿名署名装置。
【請求項２】
落とし戸付き一方向性置換関数に基づく署名方式を採っている上記署名権能者に対応する前記コミットメント作成関数Ａｉ（ｓｋ，ｒ）として、Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数を選択し、前記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）を選択し、前記回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）としてＩｉ（ｓｋ，ｃ（＋）ｉｒ）を選択し、
離散対数問題に基づく署名方式を採っている上記署名権能者に対応する前記コミットメント作成関数Ａｉ（ｓｋ，ｒ）、前記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）、及び前記回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）として、離散対数型の関数を選択する関数型選択手段を、
さらに有することを特徴とする請求項１記載の匿名署名装置。
【請求項３】
少なくとも一部の上記署名権能者に対応する前記コミットメント作成関数Ａｉ（ｓｋ，ｒ）は、ｒを出力する関数であることを特徴とする請求項１或いは２の何れかに記載の匿名署名装置。
【請求項４】
匿名署名装置から出力された多項式情報Ｐ’、及び署名情報ｓｉの入力を受け付ける署名入力手段と、
上記署名入力部において入力された上記多項式情報Ｐ’によって特定される上記一変数多項式Ｐ（Ｘ）に、各署名権能者に対応する識別子ｉを代入し、そのハッシュ値ｃｉ’’を求める多項式代入手段と、
上記署名権能者の公開鍵ｐｋｉを抽出する公開鍵抽出手段と、
上記公開鍵抽出部によって抽出された上記公開鍵ｐｋｉ、上記署名入力部において入力された上記署名情報ｓｉ、及び上記多項式代入部で求めたハッシュ値ｃｉ’’を、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）に代入するコミットメント回復手段と、
少なくとも上記コミットメント回復手段における代入結果をビット結合し、そのビット結合結果のハッシュ値と、上記一変数多項式Ｐ（Ｘ）に０を代入した結果とが等しかった場合に、署名が正しいものと判断する多項式評価手段と、
を有し、
少なくとも一部の上記署名権能者に対応する、上記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）は、コミットメント作成関数Ａｉ（ｓｋ，ｒ）をＡｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数とし、上記識別子ｉに対応する落とし戸付き一方向性置換関数をＦｉとし、二項演算ａ（＋）ｉｂ及びａ（−）ｉｂを（ａ（＋）ｉｂ）（−）ｉｂ＝ａを満たす演算とした場合における、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）であること、
を特長とする署名検証装置。
【請求項５】
落とし戸付き一方向性置換関数に基づく署名方式を採っている上記署名権能者に対応する前記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）を選択し、
離散対数問題に基づく署名方式を採っている上記署名権能者に対応する前記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として、離散対数型の関数を選択する関数型選択手段を、
さらに有することを特長とする請求項４記載の署名検証装置。
【請求項６】
少なくとも一部の上記署名権能者に対応する前記コミットメント作成関数Ａｉ（ｓｋ，ｒ）は、ｒを出力する関数であることを特徴とする請求項４或いは５の何れかに記載の署名検証装置。
【請求項７】
匿名署名装置によって、
上記署名権能者であるが実際には署名に協力しない非署名者に対応する任意な数ｓｉを生成し（ｉは各署名権能者に対応する識別子。以下同様。）、
上記非署名者に対応する任意な整数ｚｉを生成し、
生成された上記整数ｚｉのハッシュ値ｃｉ’を求め、
上記非署名者の公開鍵ｐｋｉを抽出し、
抽出した上記公開鍵ｐｋｉ、生成した上記任意な数ｓｉ、及び算出した上記ハッシュ値ｃｉ’を、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）に代入し、
署名権能者であり実際に署名に協力する署名者に対応する任意な数ｒｉを生成し、
上記署名者に対応する秘密鍵ｓｋｉを抽出し、
抽出した上記秘密鍵ｓｋｉ、及び生成した上記任意な数ｒｉを、コミットメント作成関数Ａｉ（ｓｋ，ｒ）に代入し、
少なくとも上記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）への代入結果と、上記コミットメント作成関数Ａｉ（ｓｋ，ｒ）への代入結果とをビット結合し、そのビット結合結果のハッシュ値ｃ０を求め、
上記署名権能者の人数をｎとし、上記署名者の人数をｋとし、求められた全ての上記ハッシュ値ｃｉ’に対する（ｉ，ｃｉ’）及び上記ハッシュ値ｃ０に対する（０，ｃ０）を（Ｘ，Ｙ）平面上の点とした場合における、これら点すべて（ｉ，ｃｉ’）を通るｎ−ｋ次の一変数多項式Ｐ（Ｘ）を算出し、
上記署名者に対応する上記識別子ｉを、算出された上記一変数多項式Ｐ（Ｘ）に代入し、その演算結果Ｐ（ｉ）のハッシュ値ｃｉを求め、
抽出した上記秘密鍵ｓｋｉ、生成した上記任意な数ｒｉ、及び上記第３のハッシュ関数演算ステップによるハッシュ値ｃｉを、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）に代入し、
少なくとも、算出した上記一変数多項式Ｐ（Ｘ）を特定するための多項式情報Ｐ’、生成した上記任意な数ｓｉ、及び上記回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）への代入結果ｓｉを出力し、
署名検証装置によって、
上記匿名署名装置から出力された上記多項式情報Ｐ’、上記任意な数ｓｉ、及び上記代入結果ｓｉの入力を受け付け、
入力された上記多項式情報Ｐ’によって特定される上記一変数多項式Ｐ（Ｘ）に、上記識別子ｉを代入し、そのハッシュ値ｃｉ’’を求め、
上記署名権能者の公開鍵ｐｋｉを抽出し、
抽出した上記公開鍵ｐｋｉ、入力された上記任意な数ｓｉ或いは代入結果ｓｉ、及び上記一変数多項式Ｐ（Ｘ）への上記識別子ｉの代入結果のハッシュ値ｃｉ’’を、上記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）に代入し、
少なくともこのコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）への代入結果をビット結合し、そのビット結合結果のハッシュ値と、上記一変数多項式Ｐ（Ｘ）に０を代入した結果とが等しかった場合に、署名が正しいものと判断し、
少なくとも一部の上記署名権能者に対応する、上記コミットメント作成関数Ａｉ（ｓｋ，ｒ）は、Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数であり、上記コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）は、上記識別子ｉに対応する落とし戸付き一方向性置換関数をＦｉとし、二項演算ａ（＋）ｉｂ及びａ（−）ｉｂを（ａ（＋）ｉｂ）（−）ｉｂ＝ａを満たす演算とした場合における、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）であり、上記回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）は、上記Ｆｉの逆置換関数をＩｉとした場合におけるＩｉ（ｓｋ，ｃ（＋）ｉｒ）であること、
を特長とする匿名署名方法。
【請求項８】
請求項１から３の何れかに記載された匿名署名装置としてコンピュータを機能させるための匿名署名プログラム。
【請求項９】
請求項４から６の何れかに記載された署名検証装置としてコンピュータを機能させるための署名検証プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、署名者の匿名性を保持しつつ電子署名を行う匿名署名装置、匿名署名方法、匿名署名プログラム、その電子署名を検証する署名検証装置及び署名検証プログラムに関し、特に、署名方式の多様性を向上させた匿名署名装置、署名検証装置、匿名署名方法、匿名署名プログラム及び署名検証プログラムに関する。
【０００２】
【従来の技術】
署名者の匿名性を確保する電子署名方法として、これまで様々な匿名署名方法が提唱されている。以下では、まずこの従来の匿名署名方法について説明する。
ｋ−ｏｕｔ−ｏｆ−ｎ匿名署名：
ｋ−ｏｕｔ−ｏｆ−ｎ匿名署名とは、ｎ名のうち少なくともｋ名以上が協力した時に初めて発行可能なデジタル署名を生成する方法であり、受理した署名からは、このｎ名のうち、どのｋ名による署名なのかを特定することが不可能な署名方法をいう（例えば、非特許文献１参照。）。まず、この従来のｋ−ｏｕｔ−ｏｆ−ｎ匿名署名方法について説明する。なお、ここでは以下の記法を用いる。
・Ｚａは、０以上ａ以下の整数の集合｛０，…，ａ｝を表す。
・｜ａ｜は、整数ａの２進表現のビット数を表す。但し、ａが集合の場合には、そ
の集合の大きさを表す。
・ａ←ｂは、集合ｂからランダムに元を一つ選び、その元をａと呼ぶことを表す
。
・Ｚａ［Ｘ］ｂは、係数がＺａに属するｂ次の一変数多項式の全集合を表す。
・［ａ］ｂは、ビット列ａの先頭ｂビットを表す。
・ａ‖ｂは、ビット列ａとｂのビット結合を表す。
【０００３】
まず、このｋ−ｏｕｔ−ｏｆ−ｎ匿名署名の前提として、ｐｋを公開鍵、ｓｋを秘密鍵とするとき、３つのアルゴリズムＡ，Ｚ，Ｖが存在し、ｓｋに関する３交信正直検証者ゼロ知識証明（３−ｍｏｖｅ  Ｈｏｎｅｓｔ  Ｖｅｒｉｆｉｅｒ  Ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ  Ｐｒｏｏｆ  ｏｆ  Ｋｎｏｗｌｅｄｇｅ）が以下のように構成できるものとする。
▲１▼証明者は、ランダムなｒを選び、ａ＝Ａ（ｓｋ，ｒ）を検証者へ送る（ステップ１０１）。
▲２▼検証者は、ランダムにｃを選び、証明者へ送る（ステップ１０２）。
▲３▼証明者は、ｓ＝Ｚ（ｓｋ，ｒ，ｃ）を検証者へ送る（ステップ１０３）。
▲４▼検証者は、ａ’＝Ｖ（ｐｋ，ｓ，ｃ）を計算し、ａ’＝ａならば受理する。そうでなければ拒否する（ステップ１０４）。
ここで、ステップ１０１で証明者が作るａを「コミットメント」と呼び、このコミットメントの元となるｒを選ぶ空間をＲとする。また、ステップ１０２で検証者が選ぶｃを「チャレンジ」と呼び、このチャレンジを選ぶ空間をＣとする。さらに、ｓを「回答」と呼び、この回答ｓが分布する空間をＳとする。また、以下では、Ａ（ｓｋ，ｒ）をコミットメント作成関数と呼び、Ｚ（ｓｋ，ｒ，ｃ）を回答作成関数と呼び、Ｖ（ｐｋ，ｓ，ｃ）をコミットメント回復関数と呼ぶこととする。
【０００４】
また、上記の３交信正直検証者ゼロ知識証明が構成されるためには、この手順が、衝突特性（Ｃｏｌｌｉｓｉｏｎ  Ｐｒｏｐｅｒｔｙ）と呼ばれる特性を備えることが必須である。衝突特性とは、検証者が受理する２つの会話記録（ａ，ｃ，ｓ）と（ａ，ｃ’，ｓ’）があり、ｃ≠ｃ’のとき、これらの会話記録から秘密鍵ｓｋを導出する効率的な手段が存在するという特性をいう。
この衝突特性を持つ知識の３交信正直検証者ゼロ知識証明が存在する代表的な例として、素数ｐが作る乗法群上の離散対数問題に基づく公開鍵が挙げられる。すなわち、ｐ，ｑをそれぞれ大きな素数とし、ｑはｐ−１を割り切るものとし、ｇをｐの位数ｑの部分群の生成源とし、ｇ，  ｑ，  ｐを共通パラメータとし、ｘ∈Ｚｑを秘密鍵、ｙ＝ｇｘｍｏｄ  ｐ及びｇ，ｐ，ｑの４つ組を公開鍵とした場合である。
この場合、上記の記法に対応する知識の３交信正直検証者ゼロ知識証明は、以下のようになる。
▲１▼証明者は、ｒ←Ｚｑを選び、ａ＝ｇｒを検証者へ送る。
▲２▼検証者は、ｃ←Ｚｑを選び、証明者へ送る。
▲３▼証明者は、ｓ＝ｒ−ｃｘ  ｍｏｄ  ｑを検証者へ送る。
▲４▼検証者は、ａ’＝ｇｓｙｃｍｏｄ  ｐを計算し、ａ’＝ａならば受理する。そうでなければ拒否する。
この手順によって、検証者は、証明者が秘密鍵ｘを知っていることを納得する。なお、この例では、Ｃ＝Ｓ＝Ｚｑである。以下では，このような効率的な３交信正直検証者ゼロ知識証明が存在する公開鍵を「離散対数型」と呼ぶ。
【０００５】
次に、上述の３交信正直検証者ゼロ知識証明が構成されることを前提に、従来のｋ−ｏｕｔ−ｏｆ−ｎ匿名署名手順の説明を行う。
なお、以下では、Ｌをｎ人の署名権能者にそれぞれ対応するｎ個の公開鍵の集合、即ちＬ＝［ｐｋｉ｜ｉ＝１，．．．，ｎ］とし、ＣｉをＬ中のｉ番目の公開鍵ｐｋｉ（ｉ番目の署名権能者の公開鍵）に関するゼロ知識証明で用いられるチャレンジのための空間を意味するものとし、ｐをどの｜Ｃｉ｜よりも小さな、最も大きい素数とし、Ｈを｜ｐ｜−１ビット出力のハッシュ関数とする。また、添え字のｉが、Ｌ中のｉ番目の署名権能者に対応することを意味することは、以下のその他の表記についても同様である。また、署名者は、Ｌに含まれる公開鍵ｐｋｉに対応する秘密鍵ｓｋｉのうち、ｋ個の秘密鍵ｓｋｉを知るものとする。すなわち、このｋ個の秘密鍵ｓｋｉに対応する署名権能者が署名に協力し、それぞれの秘密鍵ｓｋｉを署名者に提供しているものとする。ここで、Ｑ⊆［１，…．，ｎ］を、署名者が知っている秘密鍵ｓｋｉに対応する識別子ｉ（署名に協力した署名権能者に対応する識別子ｉ）の集合とし、｜Ｑ｜＝ｋと定義する。
【０００６】
署名者は、以下の手順で文書ｍに対する署名を生成する。
１．集合Ｑに属さない識別子ｉに対応する処理
▲１▼ｓｉ←Ｓｉ
▲２▼ｃｉ←Ｃｉ
▲３▼ａｉ：＝Ｖｉ（ｐｋｉ，ｓｉ，ｃｉ）
２．集合Ｑに属する識別子ｉに対応する処理
▲１▼ｒｉ←Ｚｑ
▲２▼ａｉ：＝Ａｉ（ｓｋｉ，ｒｉ）
３．上記手順で求めた全てのａｉ［ｉ＝１，．．．，ｎ］を用い、ｃ０：＝Ｈ（Ｌ‖ｋ‖ａ１‖…‖ａｎ‖ｍ）を求める。
４．上記手順（１．▲２▼及び３）で求めた全てのｃｉ（ｃ０を含む）に対して、（ｉ，ｃｉ）  を（Ｘ，Ｙ）平面上の点と見なし、これら全ての点（ｉ，ｃ＃ｉ）を通るｎ−ｋ次の一変数多項式Ｐ（Ｘ）∈Ｚｐ［Ｘ］ｎ−ｋを求める。
５．集合Ｑに属する識別子ｉに対し、ｓｉ＝Ｚｉ（ｓｋ，ｒｉ，Ｐ（ｉ））を実行する。
６．上記手順（１．▲１▼及び５）で求めたｓｉを用いて生成した（Ｐ’，ｋ，ｓ１，…，ｓｎ）を、（Ｌ，ｍ）に対する署名として出力する。なお、ここでＰ’は一変数多項式Ｐ（Ｘ）の全ての係数の並びを表す。
【０００７】
検証者は、以下の手順により、この（Ｌ，ｍ）に対する署名（Ｐ’，ｋ，ｓ１，…，ｓｎ）の正当性を検証する。
７．Ｐ’より一変数多項式Ｐ（Ｘ）∈Ｚｐ［Ｘ］ｎ−ｋを特定する。
８．Ｐ（０）＝Ｈ（Ｌ‖ｋ‖Ｖ１（ｐｋ１，ｓ１，Ｐ（１））‖…‖Ｖｎ（ｐｋｎ，ｓｎ，Ｐ（ｎ））‖ｍ）が成立すれば、正しい署名と認める。
以上説明したように、このｋ−ｏｕｔ−ｏｆ−ｎ匿名署名の場合、検証者は、署名（Ｐ’，ｋ，ｓ１，…，ｓｎ）の内容から、一変数多項式Ｐ（Ｘ）がｎ−ｋ次式であることをｋの値とともに知ることができる。そのため、この検証者は、署名者がｃｉ及びｓｉの値を自由に調整できるのは高々ｎ−ｋ個までであり、それ以外のｓｉを含めた検証が成立するということは、少なくともｋ個の正当な秘密鍵を用いて署名がなされていることが分かる。一方、署名（Ｐ’，ｋ，ｓ１，…，ｓｎ）には、どの識別子ｉに対応する秘密鍵ｓｋｉが使用されたかについての情報が一切含まれていない。従って、この検証者は、署名者がどの公開鍵ｐｋｉに対応する秘密鍵ｓｋｉを保持しているのかを見分けることができず、これにより署名の匿名性が確保される。
【０００８】
次に、従来の別の匿名署名方法について説明する。
Ｒｉｎｇ型匿名署名：
Ｒｉｎｇ型匿名署名は、ＲＳＡのような落とし戸付き一方向性関数に基づく鍵を扱う方法である（例えば、非特許文献２参照。）。
なお、以下の説明では、入出力域Ｃｐを持つｎ個の落とし戸付き一方向性置換関数をＦｐｋ０，…，Ｆｐｋ（ｎ−１）とし、Ｉｓｋ０，…，Ｉｓｋ（ｎ−１）をこれらに対応する逆置換関数とし、ｐｋｉ，ｓｋｉを識別子ｉに対応する署名権能者の公開鍵、秘密鍵とする。ここで、公開鍵ｐｋｉを知るものは誰でも、入力ｘに対してＦｐｋｉ（ｘ）を容易に計算でき、落とし戸情報（秘密鍵）ｓｋｉを知る者は誰でも入力ｙに対してＩｓｋｉ（ｙ）を計算することができるが、ｓｋｉを知らない場合にはＩｓｋｉ（ｙ）を計算することが困難であるものとする。以下では，このような公開鍵を「落とし戸型」と呼ぶことにする。また、ｎは十分大きい（例えば、１０２４程度）  ものとし、Ｈをハッシュ関数、ＥＫ，ＤＫを、それぞれ共通鍵をＫとする共通鍵暗号の暗号化関数、復号関数とし、ａ（ＸＯＲ）ｂをａとｂとのビット毎排他的論理和とする。
【０００９】
図１６は、このＲｉｎｇ型署名方法を説明するための概念図である。
ここでは識別子ｉに対応する署名権能者の秘密鍵ｓｋｉを用いて署名を生成するものとする。以下にこの署名作成手順を説明する。
１．Ｋ：＝Ｈ（ｍ）
２．ｚ０←Ｃを生成する。
３．ｊ＝０，…，ｉ−１まで以下を繰り返す。
（ａ）ｓｊ←Ｃ
（ｂ）ｙｊ：＝Ｆｐｋｉ（ｓｊ）
（ｃ）ｚ’ｊ：＝ｚｊ（ＸＯＲ）ｙｊ
（ｄ）ｚｊ＋１：＝ＥＫ（ｚ’ｊ）
すなわち、まず初期値ｚ０とＦｐｋ０（ｓ０）とのビット毎排他的論理和（３０１ａ）をとり、その結果ｚ’０を暗号化関数ＥＫで暗号化（３０１ｂ）したものをｚ１とし、次に、このｚ１とＦｐｋ１（ｓ１）とのビット毎排他的論理和（３０２ａ）をとり、その結果ｚ’１を暗号化関数ＥＫで暗号化（３０２ｂ）したものをｚ２とし、さらにそのｚ２とＦｐｋ２（ｓ２）とのビット毎排他的論理和（３０３ａ）をとるといった処理をｊ＝ｉ−１まで、すなわち、暗号化関数ＥＫでの暗号化（３１０ｂ）まで繰り返し、その出力ｚｉを求める。
４．ｚｎ−１’：＝ＤＫ（ｚ０）
５．ｊ＝ｎ−１，…，ｉ＋１まで以下を繰り返す。
（ａ）ｓｊ←Ｃ
（ｂ）ｙｊ：＝Ｆｐｋｉ（ｓｊ）
（ｃ）ｚｊ：＝ｚｊ’（ＸＯＲ）ｙｊ
（ｄ）ｚｊ−１’：＝ＤＫ（ｚｊ）
すなわち、初期値ｚ０を復号関数ＤＫで復号したｚｎ−１’とＦｐｋ（ｎ−１）（ｓｎ−１）とのビット毎排他的論理和をとり、その結果ｚｎ−１を復号関数ＤＫで復号したｚｎ−２’とＦｐｋ（ｎ−２）（ｓｎ−２）とのビット毎排他的論理和をとりといった処理を、ｊ＝ｉ＋１まで逆方向に繰り返していき、その出力ｚｉ’を求める。
６．ｙｉ：＝ｚｉ（ＸＯＲ）ｚ’ｉ
７．ｓｉ：＝Ｉｓｋｉ（ｙｉ）
なお、このようなｓｉを求めることができるのは、秘密鍵ｓｋｉを知っている識別子ｉに対応する署名権能者のみである。
８．（ｚ０，ｓ０，ｓ１，…，ｓｎ−１）を文書ｍに対する署名として出力する。
【００１０】
検証者は、以下の手順により、この署名（ｚ０，ｓ０，ｓ１，…，ｓｎ−１）の正当性を検証する。
９．Ｋ：＝Ｈ（ｍ）
１０．ｊ＝０，…，ｎ−１まで以下を繰り返す。
▲１▼ｙｊ：＝Ｆｊ（ｓｊ）
▲２▼ｚ’ｊ：＝ｚｊ（ＸＯＲ）ｙｊ
▲３▼ｚｊ＋１：＝ＥＫ（ｚ’ｊ）
すなわち、図１６における初期値ｚ０に対し、前述したビット毎排他的論理和（３０１ａ）、暗号化（３０１ｂ）、ビット毎排他的論理和（３０２ａ）、暗号化（３０２ｂ）という処理を、暗号化（３２１ｂ）まで順次繰り返していく。
１１．その結果、ｚｎ＝ｚ０となれば署名が正当であると判断する。
つまり、上述のようにビット毎排他的論理和及び暗号化を繰り返していった結果、最終的にもとの初期値ｚ０と同値となることは、通常、何れかの署名権能者の秘密鍵ｓｋｉを用い上述した７．の処理が行われた場合に限られる。しかし、検証者はどの秘密鍵ｓｋｉを用いてこの処理が行われたのかは知ることができない。これにより、署名者の匿名性を保持しつつ署名を行うことができる。
【００１１】
【非特許文献１】
Ｒｏｎａｌｄ  Ｃｒａｍｅｒ，  Ｉｖａｎ  Ｄａｍｇａｒｄ，  Ｂｅｒｒｙ  Ｓｃｈｏｅｎｍａｋｅｒｓ，  ”Ｐｒｏｏｆｓ  ｏｆ  Ｐａｒｔｉａｌ  Ｋｎｏｗｌｅｄｇｅ  ａｎｄ  Ｓｉｍｐｌｉｆｉｅｄ  Ｄｅｓｉｇｎ  ｏｆ  Ｗｉｔｎｅｓｓ  Ｈｉｄｉｎｇ  Ｐｒｏｔｏｃｏｌｓ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ’９４，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ８３９，  ｐｐ．  １７４−１８７，  Ｓｐｒｉｇｅｒ−Ｖｅｒｌａｇ，  １９９４
【非特許文献２】
Ｒｏｎａｌｄ  Ｌ．Ｒｉｖｅｓｔ，  Ａｄｉ  Ｓｈａｍｉｒ，  Ｙａｅｌ  Ｔａｕｍａｎ，  ”Ｈｏｗ  ｔｏ  Ｌｅａｋ  ａ  Ｓｅｃｒｅｔ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＡＳＩＡＣＲＹＰＴ  ２００１，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ２２４８，  ｐｐ．５５２−５６５，  Ｓｐｒｉｇｅｒ−Ｖｅｒｌａｇ，  ２００１
【００１２】
【発明が解決しようとする課題】
しかし、従来の匿名署名方法では、署名者が使用できる署名方式が限定されてしまうという問題点がある。
すなわち、従来のｋ−ｏｕｔ−ｏｆ−ｎ匿名署名の場合、使用できる署名方式は離散対数方の公開鍵を用いた方式のみであり、落とし戸型の公開鍵を用いた署名方式を使用することはできない。同様に、従来のＲｉｎｇ型匿名署名の場合、使用できるのは落とし戸型の公開鍵を用いた署名方式のみであり、離散対数方の公開鍵を用いた署名方式を用いることはできない。従って、例えば、離散対数型の署名或いは落とし戸型の署名しか行えない署名権能者が混在する場合、これら双方の署名権能者を当該匿名署名に参加させることはできない。
また、Ｒｉｎｇ型匿名署名の場合、真に署名に協力でき、それが立証される署名者は１人のみであり、ｋ−ｏｕｔ−ｏｆ−ｎ匿名署名のような閾値的な署名構造を採ることができない。そのため、検証者が署名から知ることができるのは、高々１人の署名権能者が署名に協力したことのみであり、検証者が確認可能な署名協力者数を増やし、この署名に対する信頼性を向上させることはできない。
【００１３】
この発明はこのような点に鑑みてなされたものであり、匿名署名に使用可能な署名方式の多様性を向上させつつ、署名協力者数の自由度をも確保することが可能な匿名署名装置を提供することを目的とする。
また、この発明の他の目的は、匿名署名に使用できる署名方式の多様性を向上させつつ、署名協力者数の自由度をも確保することが可能な署名検証装置を提供することである。
【００１４】
さらに、この発明の他の目的は、匿名署名に使用できる署名方式の多様性を向上させつつ、署名協力者数の自由度をも確保することが可能な匿名署名方法を提供することである。
また、この発明の他の目的は、匿名署名に使用できる署名方式の多様性を向上させつつ、署名協力者数の自由度をも確保することを可能とする機能をコンピュータに実行させるための匿名署名プログラムを提供することである。
さらに、この発明の他の目的は、匿名署名に使用できる署名方式の多様性を向上させつつ、署名協力者数の自由度をも確保することを可能とする機能をコンピュータに実行させるための署名検証プログラムを提供することである。
【００１５】
【課題を解決するための手段】
この発明では上記課題を解決するために、ｋ−ｏｕｔ−ｏｆ−ｎ匿名署名の構成において、少なくとも一部の署名権能者に対応する、コミットメント作成関数Ａｉ（ｓｋ，ｒ）をＡｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数とし、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）をＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）とし、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）をＩｉ（ｓｋ，ｃ（＋）ｉｒ）とする。ここでは、識別子ｉに対応する落とし戸付き一方向性置換関数をＦｉとし、二項演算ａ（＋）ｉｂ及びａ（−）ｉｂを（ａ（＋）ｉｂ）（−）ｉｂ＝ａを満たす演算とし、Ｆｉの逆置換関数をＩｉとしている。
これにより、従来離散対数型の署名方式しか用いることができなかったｋ−ｏｕｔ−ｏｆ−ｎ匿名署名において、落とし戸型の署名をも用いることが可能となり、匿名署名に使用できる署名方式の多様化を図ることができる。また、ｋ−ｏｕｔ−ｏｆ−ｎ匿名署名の構造をそのまま採ることができるため、閾値的な署名構造を採ることができ、署名に対する信頼性を向上させることも可能である。
【００１６】
【発明の実施の形態】
以下、この発明の実施の形態について説明する。なお、上述した従来の技術の説明において示した記法その他の定義は、以下の説明においても有効である。
この形態の匿名署名方式も従来のｋ−ｏｕｔ−ｏｆ−ｎ匿名署名と同様、ｐｋｉを公開鍵、ｓｋｉを秘密鍵とするとき、コミットメント作成関数Ａｉ（ｓｋ，ｒ）、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）及び回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）が存在し、以下に示す３交信正直検証者ゼロ知識証明が構成されることを前提とする。
▲１▼証明者は、ランダムなｒｉを選び、ａ＝Ａｉ（ｓｋｉ，ｒｉ）を検証者へ送る。
▲２▼検証者は、ランダムにｃｉを選び、証明者へ送る。
▲３▼証明者は、ｓ＝Ｚｉ（ｓｋｉ，ｒｉ，ｃｉ）を検証者へ送る。
▲４▼検証者は、ａ’＝Ｖｉ（ｐｋｉ，ｓｉ，ｃｉ）を計算し、ａ’＝ａならば受理する。そうでなければ拒否する。
ただし、この形態では、少なくとも一部の署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）としてＡｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数を採り、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）としてＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｃ）を採り、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）としてＩｉ（ｓｋ，ｃ（＋）ｉｒ）を採る。ここで、Ｆｉは識別子ｉに対応する入出力域Ｃｉの落とし戸付き一方向性置換関数であり、ＩｉはＦｉの逆置換関数であって、全てのｘ∈Ｃｉに対してＩｉ（Ｆｉ（ｘ））＝ｘが成り立つものである。また、公開鍵ｐｋｉを知るものは誰でも、入力ｘに対してＦｉ（ｘ）を容易に計算でき、落とし戸情報（秘密鍵）ｓｋｉを知る者は誰でも入力ｙに対してＩｉ（ｙ）を計算することができるが、ｓｋｉを知らない場合にはＩｉ（ｙ）を計算することが困難であるものとする。また、Ｃｉは、ｉ番目の公開鍵ｐｋｉ（ｉ番目の署名権能者の公開鍵）に関するゼロ知識証明で用いられるチャレンジのための空間を意味するアーベル群である。さらに、二項演算ａ（＋）ｉｂ及びａ（−）ｉｂは、（ａ（＋）ｉｂ）（−）ｉｂ＝ａを満たす演算である。
【００１７】
次に、この形態の概略について説明する。
本形態の匿名署名システムは、匿名署名を生成する匿名署名装置、及び生成された匿名署名を検証する署名検証装置から構成される。
図１は、公知のコンピュータに所定のプログラムを実行させることによって構成される本形態の匿名署名装置１の概略を例示した機能ブロック図である。以下、この図１を用い、匿名署名装置１の概略構成及びその処理の概略について説明する。
〔事前処理〕
まず、匿名署名作成の事前処理として、少なくとも一部の署名権能者に対応する、コミットメント作成関数Ａｉ（ｓｋ，ｒ）としてＡｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数が、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）としてＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）が、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）としてＩｉ（ｓｋ，ｃ（＋）ｉｒ）が、それぞれ関数メモリ２に格納される。なお、少なくとも一部の署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）を、ｒを出力する関数、すなわち、ｒ＝Ａｉ（ｓｋ，ｒ）である関数としてもよい。これにより、署名作成時における演算処理を簡略化することができる。
【００１８】
〔署名作成処理〕
まず、各署名権能者の公開鍵ｐｋｉをｎ個含む公開鍵リストＬ＝［ｐｋｉ｜ｉ＝１，．．．，ｎ］、及び署名権能者のうち実際に署名に協力するｋ名分の署名者の秘密鍵ｓｋｉを含む秘密鍵リストＫ＝［ｓｋｉ｜ｉ⊆Ｑ］がレジスタ３に格納され、その後、各識別子（ｉ＝１，…，ｎ）に対し、以下の処理が行われる。なお、Ｑ⊆［ｉ＝１，．．．，ｎ］，｜Ｑ｜＝ｋは実際に署名に協力する署名者（匿名署名装置１に秘密鍵ｓｋｉを提供し、匿名署名装置１が秘密鍵ｓｋｉを知る署名権能者）に対応する識別子ｉの集合を意味する。
非署名者（署名権能者であるが実際には署名に協力しない者）の識別子ｉに対応する処理：
第１の任意数生成部４において、非署名者に対応する任意な数ｓｉを生成し（ｓｉ←Ｃｉ）、その任意な数ｓｉを擬似コミットメント作成部７及び署名出力部１５に送る。また、第２の任意数生成部５において、この非署名者に対応する任意な整数ｚｉを生成し（ｚｉ←Ｚｐ）、その結果をハッシュ関数演算部６に送る。なお、ｐは、どの｜Ｃｉ｜よりも小さな、最大の素数である。
この整数ｚｉが送られたハッシュ関数演算部６は、送られた整数ｚｉのハッシュ値ｃｉ’を求め（Ｈｉ（ｚｉ））、そのハッシュ値ｃｉ’を擬似コミットメント作成部７及び多項式算出部１１に送る。なお、Ｈは、｜ｐ｜−１ビット出力のハッシュ関数である。
【００１９】
次に擬似コミットメント作成部７は、レジスタ３からこの非署名者の公開鍵ｐｋｉを抽出し（第１の公開鍵抽出手段に相当）、さらに、関数メモリからコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）を抽出する。なお、ここで抽出されるコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）は、識別子ｉに対応する署名権能者がどのような署名方式を用いるかによって異なるが、この署名権能者が落とし戸型の署名方式を採っていた場合、上述のＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）がコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として抽出されることになる。
その後、擬似コミットメント作成部７は、レジスタ３から抽出した公開鍵ｐｋｉ、第１の任意数生成部４によって生成された任意な数ｓｉ、及び第１のハッシュ関数演算部によって算出されたハッシュ値ｃｉ’を、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）に代入し、その演算結果ａｉを第２のハッシュ関数演算部１０に送る。
【００２０】
署名者（署名権能者であり実際に署名に協力する者）の識別子ｉに対応する処理：
まず、第３の任意数生成部８において任意な数ｒｉを生成し、その任意な数ｒｉをコミットメント作成部９及び回復演算部１４に送る。次に、コミットメント作成部９において、署名者に対応する秘密鍵ｓｋｉをレジスタ３から抽出し（秘密鍵抽出手段に相当）、関数メモリ２からコミットメント作成関数Ａｉ（ｓｋ，ｒ）を抽出する。なお、ここで抽出されるコミットメント作成関数Ａｉ（ｓｋ，ｒ）は、識別子ｉに対応する署名権能者がどのような署名方式を用いるかによって異なるが、この署名権能者が落とし戸型の署名方式を採っていた場合、上述のＡｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数がコミットメント作成関数Ａｉ（ｓｋ，ｒ）として抽出されることになる。その後、コミットメント作成部９は、抽出した秘密鍵ｓｋｉ、及び第３の任意数生成部８によって生成された数ｒｉを、コミットメント作成関数Ａｉ（ｓｋ，ｒ）に代入し、その演算結果ａｉを第２のハッシュ関数演算部１０に送る。
【００２１】
全ての識別子（ｉ＝１，…，ｎ）に対応する処理：
第２のハッシュ関数演算部１０において、少なくとも擬似コミットメント作成部７による演算結果ａｉとコミットメント作成部９における演算結果ａｉとをビット結合し、そのビット結合結果のハッシュ値ｃ０を求め、そのハッシュ値ｃ０を多項式算出部１１に送る。多項式算出部１１は、署名権能者の人数をｎとし、署名者の人数をｋとし、第１のハッシュ関数演算部６において求められた全てのハッシュ値ｃｉ’に対する（ｉ，ｃｉ’）及び第２のハッシュ関数演算部１０において求められたハッシュ値ｃ０に対する（０，ｃ０）を（Ｘ，Ｙ）平面上の点とした場合における、これらの点全てを通るｎ−ｋ次の一変数多項式Ｐ（Ｘ）を算出する。算出された一変数多項式Ｐ（Ｘ）は第３のハッシュ関数演算部１３に送られ、この一変数多項式Ｐ（Ｘ）  を特定するための多項式情報Ｐ’は署名出力部１５に送られる。一変数多項式Ｐ（Ｘ）が送られた第３のハッシュ関数演算部１３は、カウンタ１２において生成され、そこから送られた署名者に対応する識別子ｉを、この一変数多項式Ｐ（Ｘ）に代入し、その演算結果Ｐ（ｉ）のハッシュ値ｃｉを求める。求められたハッシュ値ｃｉは回復演算部１４に送られ、この回復演算部１４は、関数メモリ２から回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）を抽出する。なお、ここで抽出される回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）は、識別子ｉに対応する署名権能者がどのような署名方式を用いるかによって異なるが、この署名権能者が落とし戸型の署名方式を採っていた場合、上述のＩｉ（ｓｋ，ｃ（＋）ｉｒ）が回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）として抽出されることになる。
次に回復演算部１４は、抽出した秘密鍵ｓｋｉ、第３の任意数生成部８によって生成された数ｒｉ、及び第３のハッシュ関数演算部１３によって求められたハッシュ値ｃｉを、抽出した回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）に代入し、その演算結果ｓｉを署名出力部１５に送る。そして、署名出力部１５は、少なくとも、多項式算出部１１によって算出された一変数多項式Ｐ（Ｘ）を特定するための多項式情報Ｐ’、第１の任意数生成部４によって生成された任意な数ｓｉ、及び回復演算部による演算結果ｓｉを署名σとして出力する。
【００２２】
図２は、公知のコンピュータに所定のプログラムを実行させることによって構成される本形態の署名検証装置２０の概略を例示した機能ブロック図である。以下、この図２を用い、署名検証装置２０の概略構成及びその処理の概略について説明する。
〔事前処理〕
まず、署名検証処理の事前処理として、少なくとも一部の署名権能者に対応するコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）としてＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）が関数メモリ２３に格納される。なお、少なくとも一部の署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）を、ｒを出力する関数とし、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）をＦｉ（ｐｋ，ｓ）（−）ｉｃとしてもよい。これにより、署名検証時における演算処理を簡略化することができる。
〔署名検証処理〕
まず、署名入力部２１において、匿名署名装置１から出力された多項式情報Ｐ’、及び署名情報ｓｉを有する署名σの入力を受け付け、その多項式情報Ｐ’を多項式代入部２４に、署名情報ｓｉをコミットメント回復部２５に送る。また、各署名権能者の公開鍵ｐｋｉをｎ個含む公開鍵リストＬ＝［ｐｋｉ｜ｉ＝１，．．．，ｎ］がレジスタ２２に格納される。なお、この公開鍵リストＬは、例えば、署名σとともに匿名署名装置１から出力されたものとする。
【００２３】
次に、多項式代入部２４においてレジスタ２２の公開鍵リストＬから識別子［ｉ＝１，．．．，ｎ］（各署名権能者に対応する識別子ｉ）を抽出し、それらを順次、多項式情報Ｐ’によって特定される一変数多項式Ｐ（Ｘ）に代入し、その代入結果のハッシュ値ｃｉ’’＝Ｈｉ（Ｐ（ｉ））をコミットメント回復部２５に送る。また、この一変数多項式Ｐ（Ｘ）は、多項式代入部２４から多項式評価部２７に送られる。
コミットメント回復部２５では、レジスタ２２から署名権能者の公開鍵ｐｋｉを抽出し（公開鍵抽出手段に相当）、抽出した公開鍵ｐｋｉ、署名入力部２１において入力された署名情報ｓｉ、及び多項式代入部２４で求めたハッシュ値ｃｉ’’を、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）に代入する。なお、このコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）は関数メモリ２３から抽出したものである。そして、この抽出されるコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）は、識別子ｉに対応する署名権能者がどのような署名方式を用いるかによって異なるが、この署名権能者が落とし戸型の署名方式を採っていた場合、上述のＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）がコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として抽出されることになる。
次に、ハッシュ関数演算部２６において、少なくとも、コミットメント回復部２５における代入結果をビット結合し、そのビット結合結果のハッシュ値ｈを多項式評価部２７に送る。このハッシュ値ｈが送られた多項式評価部２７は、このハッシュ値ｈと、多項式代入部２４から送られた一変数多項式Ｐ（Ｘ）に０を代入した結果とを比較し、これらが等しかった場合に、署名が正しいものと判断し、その検証結果を出力する。
【００２４】
次に、この形態の詳細について説明する。
図３は、この形態における匿名署名システム１００の全体構成を例示した概念図である。
図３に例示するように、この例の匿名署名システム１００は、匿名署名を生成する匿名署名装置１１０、及び送信された署名を検証する署名検証装置１３０によって構成され、これらはネットワーク１５０を介して通信可能なように接続されている。
図４は、この例の匿名署名装置１１０のハードウェア構成を例示したブロック図である。
図４に例示するように、この例の匿名署名装置１１０は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１０ａ、キーボード等の入力装置１１０ｂ、半導体メモリ等の記憶装置１１０ｃ、液晶ディスプレイ等の出力装置１１０ｄ、ネットワーク１５０との通信を可能にする通信制御装置１１０ｅ、及びこれらをデータのやり取りが可能なように接続するバス１１０ｆを有しており、記憶装置１１０ｃに記憶された所定のプログラムをＣＰＵ１１０ａで実行することにより、その処理機能を実現する。なお、ここでは説明を省略するが、署名権能者端末装置１０１〜１０３、及び署名検証装置１３０も匿名署名装置１１０と同様なハードウェア構成を採るものとする。
【００２５】
図５は、図４に例示したハードウェアにおいて所定のプログラムを実行させることにより実現される匿名署名装置１１０の機能構成を例示したブロック図であり、図６は関数メモリ１１１に記録される関数表２３０のデータ構成を、図７の（ａ）は、公開鍵リスト２１０のデータ構成を、（ｂ）は秘密鍵リスト２２０のデータ構成を、それぞれ例示した概念図である。また、図８は、図４に例示したものと同等なハードウェアにおいて所定のプログラムを実行させることにより実現される署名検証装置１３０の機能構成を例示したブロック図であり、図９は、関数メモリ１３１に記録される関数表２４０のデータ構成を例示した概念図である。さらに、図１０から図１５は、この形態における匿名署名の生成から、その検証までの処理を説明するためのフローチャートである。
【００２６】
以下、これらの図を用いて、本形態における匿名署名装置１１０及び署名検証装置１３０の機能構成及びその処理について説明していく。なお、以下では、離散対数を構成する群としてｐｉを素数とする乗法群Ｚｐｉを、また、落とし戸付き一方向性関数としてＲＳＡ演算を用いる場合を例にとって説明する。
〔事前処理〕
まず、匿名署名装置１１０に対する事前処理として、コミットメント作成関数Ａｉ（ｓｋ，ｒ）２０２、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）２０３、及び回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）２０４を、署名権能者が使用する公開鍵方式ｌ（ｉ）２０１に対応付けた関数表２００を関数メモリ１１１に格納する（図６）。
【００２７】
この例の場合、関数表２００には、公開鍵方式ｌ（ｉ）２０１として、公開鍵が離散対数型であることを示す記号「Ｄ」、及び公開鍵が落とし戸型であることを示す記号「Ｔ」が格納されている。そして、この記号「Ｄ」に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）２０２としてａｉ＝ｇｉｒｉｍｏｄ  ｐｉが、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）２０３としてａｉ＝ｇｉｓｉｙｉｃｉｍｏｄ  ｐｉが、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）２０４としてｓｉ＝ｒｉ−ｃｉｘｉｍｏｄ  ｑｉが、記号「Ｔ」に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）２０２としてｒを出力する関数ａｉ＝ｒｉ（Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数に相当）が、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）２０３としてａｉ＝ｓｉｅｉｃｉ−１ｍｏｄ  Ｎｉ（Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）に相当）が、及び回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）２０４としてｓｉ＝（ｒｉｃｉ）ｄｉｍｏｄ  Ｎｉ（Ｉｉ（ｓｋ，ｃ（＋）ｉｒ）に相当）がそれぞれ格納されている。なお、ｐｉ，ｑｉは大きな素数であり、ｑｉはｐｉ−１を割り切るものとする。また、ｇｉはｐｉの位数ｑｉの部分群の生成元であり、ｘｉ∈Ｚｑｉ，ｙｉ＝ｇｉｘｉｍｏｄ  ｐｉとする。さらに、Ｎｉは２つの大きな素数の積であり、ｅｉ，ｄｉは、３≧ｅｉ＜Ｎｉ、及びｅｉｄｉ≡１  ｍｏｄφ（Ｎｉ）を満たすものとする（φはオイラー関数）。
また、署名検証装置１３０に対する事前処理として、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）２４２を、署名権能者が使用する公開鍵方式ｌ（ｉ）２４１に対応付けた関数表２４０を関数メモリ１３１に格納する（図９）。
【００２８】
この例の場合、関数表２４０には、公開鍵方式ｌ（ｉ）２４１として、上述の記号「Ｄ」及び記号「Ｔ」が格納され、この記号「Ｄ」に対応するコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）２４２としてａｉ＝ｇｉｓｉｙｉｃｉｍｏｄ  ｐｉが、記号「Ｔ」に対応するコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）２４２としてａｉ＝ｓｉｅｉｃｉ−１ｍｏｄ  Ｎｉ（Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）に相当）がそれぞれ格納されている。
〔署名作成処理〕
署名の作成を行う場合、まず、匿名署名装置１１０の入力部１１４に、公開鍵リスト（Ｌ）２１０、秘密鍵リスト（Ｋ）２２０及び文書（ｍ）２３０が入力される（図３、図４、図７）。
図７の（ａ）に例示するように、この例の公開鍵リスト（Ｌ）２１０は、ｎ名の各署名権能者に対応する識別子（ｉ）２１１に、各署名権能者が使用する公開鍵方式（ｌ（ｉ））２１２及び公開鍵（ｐｋｉ）２１２を対応付けた構成となっており、例えば、識別子１には、公開鍵方式（ｌ（１））＝Ｔ、及び公開鍵（ｐｋ１）が、識別子２には、公開鍵方式（ｌ（２））＝Ｄ、及び公開鍵（ｐｋ２）が、それぞれ対応付けられている。また、図７の（ｂ）に例示するように、この例の秘密鍵リスト（Ｋ）２２０は、実際に署名に協力するｋ名の署名者に対応する識別子（ｉ）２２１に、ｋ個の各署名者の秘密鍵（ｓｋｉ）２２２を対応付けた構成となっており、例えば、インデックス２，３，５，７，８に対し、秘密鍵ｓｋ２，ｓｋ３，ｓｋ５，ｓｋ７，ｓｋ８が対応付けられている。
【００２９】
なお、この例では、公開鍵方式（ｌ（ｉ））＝Ｄ（離散対数型）である場合には、公開鍵ｐｋｉ＝（ｙｉ，ｇｉ，ｑｉ，ｐｉ）であり、秘密鍵ｓｋｉ＝（ｘｉ，ｇｉ，ｑｉ，ｐｉ）あり、公開鍵方式（ｌ（ｉ））＝Ｔ（落とし戸型）である場合には、公開鍵ｐｋｉ＝（ｅｉ，Ｎｉ）であり、秘密鍵ｓｋｉ＝（ｄｉ，Ｎｉ）である。また、このように入力された公開鍵リスト（Ｌ）２１０、秘密鍵リスト（Ｋ）２２０及び文書（ｍ）２３０はレジスタ１１３に送られ、そこで格納される。
次に、素数生成部１１５において、ｐ≧ｍａｘ［ｓｉｚｅ（Ｃ１），…，ｓｉｚｅ（Ｃｎ）］となる素数ｐを生成する（ステップＳ１）。すなわち、Ｃｉを公開鍵リストＬ中のｉ番目の公開鍵ｐｋｉに関するゼロ知識証明で用いるチャレンジのための空間とした場合において、どの｜Ｃｉ｜よりも多きな、最も小さい素数ｐを生成する。なお、素数ｐの生成は、例えばＲａｂｉｎ法等、非常に高い確率で素数となるような確率的素数生成方法を用いて行ってもよく、生成した素数ｐは、レジスタ１１３に送られて記録される他、任意数生成部１１７にも送られる。
【００３０】
次に、制御部１２８が保持するカウンタ（図示せず）のカウント値をｉ＝１とし（ステップＳ２）、このｉがｉ∈Ｑであるか否か判断する（ステップＳ３）。すなわち、制御部１２８において、レジスタ１１３から秘密鍵リスト２２０を抽出し、この秘密鍵リスト２２０の識別子２２１がｉを有する（ｉ∈Ｑ）か否か判断する。そして、ｉ∈Ｑであると判断された場合にはステップＳ１０の処理に進み、ｉ∈Ｑでないと判断された場合にはステップＳ４の処理に進む。例えば、この段階ではｉ＝１であり、このｉの値「１」は秘密鍵リスト２２０の識別子２２１に存在しないため、ｉ∈Ｑでないと判断され、ステップＳ４の処理へ進む。
ステップＳ４では、任意数生成部１１６において、任意な数ｓｉ←Ｃｉを例えばランダムに選び、その任意な数ｓｉを擬似コミットメント作成部１１９に送る。また、任意数生成部１１７において、任意な整数ｚｉ←Ｚｐを例えばランダムに選び、選んだ整数ｚｉをハッシュ関数演算部１１８に送る（ステップＳ５）。この整数ｚｉが送られたハッシュ関数演算部１１８は、この整数ｚｉのハッシュ値（ｃｉ’＝Ｈｉ（ｚｉ））を計算し、そのハッシュ値ｃｉ’を擬似コミットメント作成部１１９に送る（ステップＳ６）。なお、ここで処理を行っている識別子ｉに対応する公開鍵方式（ｌ（ｉ））がＤ（離散対数型）であった場合、この例のハッシュ関数Ｈｉは｜ｑｉ｜−１ビットの出力域を持つハッシュ関数である。具体的には、例えば、このｑｉが１６１ビット以下の場合、１６０ビット出力のＳＨＡ−１関数を利用し、その出力のＬＳＢ側から｜ｑｉ｜−１ビットをこのハッシュ値として利用する。一方、現在処理を行っている識別子ｉに対応する公開鍵方式（ｌ（ｉ））が鍵方式（ｌ（ｉ））＝Ｔ（落とし戸型）であった場合、この例のハッシュ関数Ｈｉは、ＺＮｉ＼［０］の出力値を持つハッシュ関数である。具体的には、例えば、Ｎｉが１０２４ビットの場合（ＳＨＡ１（Ｎｉ‖１）‖ＳＨＡ１（Ｎｉ‖２）‖…‖ＳＨＡ１（Ｎｉ‖＜１０２４／１６０＞＋１）ｍｏｄ  Ｎｉ‖１をハッシュ値として出力する。なお、ＺＮｉ＼［０］とは、ＺＮｉから０を除いた集合、すなわち、１以上Ｎｉ未満の自然数の集合｛１，…，Ｎｉ−１｝を意味し、＜１０２４／１６０＞は１０２４／１６０以上の最小の整数を意味する。
【００３１】
次に、擬似コミットメント作成部１１９において、レジスタ１１３から公開鍵ｐｋｉを、関数型選択部１１２を介して関数メモリ１１１からコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）を、それぞれ取得し、ａｉ＝Ｖｉ（ｐｋｉ，ｓｉ，ｃｉ）の演算を行う（ステップＳ７）。以下、図１４（ａ）のフローチャートを用い、この際行われるコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）の取得手順について説明する。
まず、制御部１２８から関数型選択部１１２に対し、処理中の識別子ｉの情報が送られる。この関数型選択部１１２は、落とし戸付き一方向性置換関数に基づく署名方式を採っている署名権能者に対応するコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）としてＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）を選択し、離散対数問題に基づく署名方式を採っている署名権能者に対応するコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として離散対数型の関数を選択する機能を有しており、この送られた識別子ｉの情報をもとにこの関数型の選択を行う。すなわち、関数型選択部１１２は、まず、レジスタ１１３から公開鍵リスト（Ｌ）２１０を抽出し、制御部１２８から送られた識別子ｉに対応する公開鍵方式（ｌ（ｉ））が離散対数型（Ｄ）であるか否かを判断する（ステップＳ６１）。
【００３２】
ここで、公開鍵方式（ｌ（ｉ））が離散対数型（Ｄ）であった場合、関数型選択部１１２は、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として離散対数型の関数であるａｉ＝ｇｉｓｉｙｉｃｉｍｏｄ  ｐｉを選択し（ステップＳ６２）、公開鍵方式（ｌ（ｉ））が落とし戸型（Ｔ）であった場合には、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）としてＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）に相当するａｉ＝ｓｉｅｉｃｉ−１ｍｏｄ  Ｎｉを選択する（ステップＳ６３）。そして、関数型選択部１１２は、この選択した関数を関数メモリ１１１から抽出し、擬似コミットメント作成部１１９に送る。
このようにコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）が送られた擬似コミットメント作成部１１９は、上述のように送られたｐｋｉ，ｓｉ，ｃｉをこの関数に代入する（ａｉ＝Ｖｉ（ｐｋｉ，ｓｉ，ｃｉ））。そして、この演算結果ａｉはハッシュ関数演算部１２２に送られ、次のステップＳ８の処理に移る。
【００３３】
ステップＳ８では制御部１２８のカウント値ｉをｉ＝ｉ＋１とし、次のステップＳ９においてｉ＞ｎであるか否かを判断する。なお、このｎは、例えば、公開鍵リスト（Ｌ）２１０から取得した情報である。そして、ｉ＞ｎであると判断された場合には、ステップＳ１２に進み、そうでなければステップＳ３に戻る。
ステップＳ３においてｉ∈Ｑであると判断された場合、任意数生成部１２０は、任意な数ｒｉ←Ｒｉを例えばランダムに選択し、その任意な数ｒｉをコミットメント作成部１２１及び回復演算部１２６に送る（ステップＳ１０）。なお、ＲｉはＬ中のｉ番目の公開鍵ｐｋｉ（ｉ番目の署名権能者の公開鍵）に関するゼロ知識証明で用いられるレスポンスのための空間を意味する。
この任意な数ｒｉを受け取ったコミットメント作成部１２１は、さらにレジスタ１１３から秘密鍵ｓｋｉを、関数型選択部１１２を介して関数メモリ１１１からコミットメント作成関数Ａｉ（ｓｋ，ｒ）を、それぞれ取得し、ａｉ＝Ａｉ（ｓｋｉ，ｒｉ）の演算を行う（ステップＳ１１）。以下、図１４（ｂ）のフローチャートを用い、この際行われるコミットメント作成関数Ａｉ（ｓｋ，ｒ）の取得手順について説明する。
【００３４】
まず、制御部１２８から関数型選択部１１２に対し、処理中の識別子ｉの情報が送られる。この関数型選択部１１２は、落とし戸付き一方向性置換関数に基づく署名方式を採っている署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）として、Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数を選択し、離散対数問題に基づく署名方式を採っている署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）として、離散対数型の関数を選択する機能を有しており、この送られた識別子ｉの情報をもとにこの関数型の選択を行う。すなわち、関数型選択部１１２は、まず、レジスタ１１３から公開鍵リスト（Ｌ）２１０を抽出し、制御部１２８から送られた識別子ｉに対応する公開鍵方式（ｌ（ｉ））が離散対数型（Ｄ）であるか否かを判断する（ステップＳ７１）。
ここで、公開鍵方式（ｌ（ｉ））が離散対数型（Ｄ）であった場合、関数型選択部１１２は、コミットメント作成関数Ａｉ（ｓｋ，ｒ）として離散対数型の関数であるａｉ＝ｇｉｒｉｍｏｄ  ｐｉを選択し（ステップＳ７２）、公開鍵方式（ｌ（ｉ））が落とし戸型（Ｔ）であった場合には、コミットメント作成関数Ａｉ（ｓｋ，ｒ）として、Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数であるａｉ＝ｒｉを選択する（ステップＳ７３）。そして、関数型選択部１１２は、この選択した関数を関数メモリ１１１から抽出し、コミットメント作成部１２１に送る。
【００３５】
このようにコミットメント作成関数Ａｉ（ｓｋ，ｒ）が送られたコミットメント作成部１２１は、上述のように送られたｓｋｉ，ｒｉをこの関数に代入する（ａｉ＝Ａｉ（ｓｋｉ，ｒｉ））。そして、この演算結果ａｉはハッシュ関数演算部１２２に送られ、次のステップＳ８及びステップＳ９の処理に移る。
その後、同様にステップＳ３からステップＳ９の処理を繰り返し、ステップＳ９の判断においてｉ≦ｎとなった場合、次のステップＳ１２の処理に移る。
ステップＳ１２では、ハッシュ関数演算部１２２において、レジスタ１１３から公開鍵リストＬ、秘密鍵の個数ｋ、文書ｍ、及び素数ｐを取得し、これらと擬似コミットメント作成部１１９及びコミットメント作成部１２１から送られたａｉをビット結合し、そのビット結合結果のハッシュ値（ｃ０＝Ｈ（Ｌ‖ｋ‖ｐ‖ａ１‖…‖ａｎ‖ｍ）を演算する（ステップＳ１２）。そのハッシュ値ｃ０は多項式算出部１２３に送られ、この多項式算出部１２３は、ハッシュ関数演算部１１８において求められた全てのハッシュ値ｃｉ’に対する（ｉ，ｃｉ’）及びハッシュ関数演算部１２２において求められたハッシュ値ｃ０に対する（０，ｃ０）を（Ｘ，Ｙ）平面上の点とした場合における、これらの点全てを通るｎ−ｋ次の一変数多項式Ｐ（Ｘ）∈Ｚｐ［Ｘ］ｎ−ｋを求める。この一変数多項式Ｐ（Ｘ）の算出は、例えば、Ｌａｇｒａｎｇｅ補完によって、
【数１】
2004312512.tif 000003
を用いて求めることができる（ステップＳ１３）。ただし、ｉ−ｊが素数ｐを割り切る場合にはＰ（Ｘ）は求まらないため、この場合、ステップＳ１に戻って処理をやり直す。一方、Ｐ（Ｘ）が求まった場合には、求まった一変数多項式Ｐ（Ｘ）をハッシュ関数演算部１２５に送り、さらにこのＰ（Ｘ）を特定するための情報（例えば、Ｐ（Ｘ）の係数）Ｐ’を通信部１２７に送る。
【００３６】
次に、カウンタ１２４のカウント値ｉを１とし（ステップＳ１４）、このカウント値ｉがｉ∈Ｑであるか否かを判断する。ここでｉ∈Ｑでなかった場合、ステップＳ１９の処理に進む。一方、ｉ∈Ｑであった場合、ハッシュ関数演算部１２５において、カウンタ１２４から供給されたカウント値ｉを一変数多項式Ｐ（Ｘ）に代入（ｚｉ＝Ｐ（ｉ））し（ステップＳ１６）、この代入結果ｚｉのハッシュ値ｃｉ＝Ｈｉ（ｚｉ）を計算して（ステップＳ１７）、その結果を回復演算部１２６に送る。
このハッシュ値ｃｉを受け取った回復演算部１２６は、さらにレジスタ１１３から秘密鍵ｓｋｉを、関数型選択部１１２を介して関数メモリ１１１から回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）を、それぞれ取得しｓｉ＝Ｚｉ（ｓｋｉ，ｒｉ，ｃｉ）の演算を行う（ステップＳ１８）。以下、図１５のフローチャートを用い、この際行われる回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）の取得手順について説明する。
【００３７】
まず、制御部１２８から関数型選択部１１２に対し、処理中の識別子ｉの情報が送られる。この関数型選択部１１２は、落とし戸付き一方向性置換関数に基づく署名方式を採っている署名権能者に対応する回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）としてＩｉ（ｓｋ，ｃ（＋）ｉｒ）を、離散対数問題に基づく署名方式を採っている署名権能者に対応する回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）として離散対数型の関数を選択する機能を有しており、この送られた識別子ｉの情報をもとにこの関数型の選択を行う。すなわち、関数型選択部１１２は、まず、レジスタ１１３から公開鍵リスト（Ｌ）２１０を抽出し、制御部１２８から送られた識別子ｉに対応する公開鍵方式（ｌ（ｉ））が離散対数型（Ｄ）であるか否かを判断する（ステップＳ８１）。
ここで、公開鍵方式（ｌ（ｉ））が離散対数型（Ｄ）であった場合、関数型選択部１１２は、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）として離散対数型の関数であるｓｉ＝ｒｉ−ｃｉｘｉｍｏｄ  ｑｉを選択し（ステップＳ８２）、公開鍵方式（ｌ（ｉ））が落とし戸型（Ｔ）であった場合には、Ｉｉ（ｓｋ，ｃ（＋）ｉｒ）に相当するｓｉ＝（ｒｉｃｉ）ｄｉｍｏｄ  ＮＩを選択する（ステップＳ８３）。そして、関数型選択部１１２は、この選択した関数を関数メモリ１１１から抽出し、回復演算部１２６に送る。
このように回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）を受け取った回復演算部１２６は、上述のように受け取ったｓｋｉ，ｒｉ，ｃｉをこの関数に代入する（ｓｉ＝Ｚｉ（ｓｋｉ，ｒｉ，ｃｉ））。そして、この演算結果ｓｉは通信部１２７に送られる。
【００３８】
次に、カウンタ１２４のカウント値ｉを１加算し（ステップＳ１９）、制御部１２８において、ｉ＞ｎであるか否かを判断する。ここで、ｉ＞ｎでなかった場合にはステップＳ１５に戻る。一方、ｉ＞ｎであった場合、通信部１２７によってレジスタ１１３から公開鍵リストＬ、秘密鍵の個数ｋ、文書ｍ、及び素数ｐを取得し、さらに、任意数生成部１１６や回復演算部１２６から送られたｓｉ、多項式算出部１２３から送られたＰ’を用い、Ｌ、ｋ、ｍの署名σ＝（Ｐ’，ｐ，ｓ１，…，ｓｎ）を生成する（ステップＳ２１）。このように生成された署名σ＝（Ｐ’，ｐ，ｓ１，…，ｓｎ）は、Ｌ、ｋ、ｍとともにネットワーク１５０を介して署名検証装置１３０に送られる。
〔署名検証処理〕
まず、通信部１３４において、ネットワーク１５０を介して匿名署名装置１１０から送信されたＬ、ｋ、ｍとその署名σ＝（Ｐ’，ｐ，ｓ１，…，ｓｎ）を受信する。そして、受信したＬをレジスタ１３３に送って記憶させ、ｓ１，…，ｓｎをコミットメント回復部１３６に送り、Ｐ’を多項式代入部１３５及び多項式検証部１４０に送り、ｐ、Ｌ、ｋ、ｍをハッシュ関数演算部１３７に送る。次に、多項式検証部１４０において、取得したｐがｐ≧ｍａｘ［ｓｉｚｅ（Ｃ１），…，ｓｉｚｅ（Ｃｎ）］を満たすか否かを確認する。ここでｐ≧ｍａｘ［ｓｉｚｅ（Ｃ１），…，ｓｉｚｅ（Ｃｎ）］でなければ、署名を拒否して（ステップＳ３３）処理を終了する。一方、ｐ≧ｍａｘ［ｓｉｚｅ（Ｃ１），…，ｓｉｚｅ（Ｃｎ）］であれば、多項式検証部１４０において、受け取ったＰ’によって特定される一変数多項式Ｐ（Ｘ）の係数の数がｎ−ｋ＋１個以下であること、及びこの一変数多項式Ｐ（Ｘ）の全ての係数が０以上ｐ未満であることを確認する（ステップＳ３２）。以下、この多項式検証部１４０における処理を図１３のフローチャートを用いて説明する。
【００３９】
まず、一変数多項式Ｐ（Ｘ）の次数がｎ−ｋ以下であるか否か、すなわち一変数多項式Ｐ（Ｘ）の係数の数がｎ−ｋ＋１個以下であるか否かを判断し、この次数がｎ−ｋ以下であればステップＳ５３に進み、そうでなければ検証失敗として処理を終了する（ステップＳ５２）。次に、多項式検証部１４０が有する図示しないカウンタのカウント値ｊを０にリセットし（ステップＳ５３）、一変数多項式Ｐ（Ｘ）の一つの係数Ｐ’ｊが０以上ｐ未満の整数であるか否か判断する（ステップＳ５４）。ここで、係数Ｐ’ｊが０以上ｐ未満の整数であればカウント値ｊに１を加算し（ステップＳ５５）、そうでなければ検証失敗として処理を終了する。カウント値ｊの加算後（ステップＳ５５）、ｊ＞ｎ−ｋであるか否かを判断し（ステップＳ５６）、ｊ＞ｎ−ｋであった場合には検証成功として処理を終了する（ステップＳ５７）。
この検証が失敗した場合、署名を拒否して（ステップＳ３３）処理を終了し、成功した場合には、制御部１４１が有する図示していないカウンタのカウント値ｉを１にする（ステップＳ３４）。
次に、多項式代入部１３５において通信部からＰ’を取得し、これによって特定される一変数多項式Ｐ（Ｘ）に、制御部１４１から送られるカウント値ｉを代入し、その代入結果のハッシュ値ｃｉ’’＝Ｈｉ（Ｐ（ｉ））をコミットメント回復部１３６に送る（ステップＳ３５）。
【００４０】
また、関数型選択部１３２は、落とし戸付き一方向性置換関数に基づく署名方式を採っている署名権能者に対応するコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）としてＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）を選択し、離散対数問題に基づく署名方式を採っている署名権能者に対応するコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として離散対数型の関数を選択する機能を有しており、制御部１４１から送られたカウント値ｉを用い、使用する関数型の選択を行う。すなわち、関数型選択部１３２は、まず、受け取った公開鍵リスト（Ｌ）２１０を検索し、識別子ｉに対応する公開鍵方式（ｌ（ｉ））が離散対数型（Ｄ）であるか否かを判断する。ここで、公開鍵方式（ｌ（ｉ））が離散対数型（Ｄ）であった場合、関数型選択部１３２は、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として離散対数型の関数であるａｉ＝ｇｉｓｉｙｉｃｉｍｏｄ  ｐｉを選択し、公開鍵方式（ｌ（ｉ））が落とし戸型（Ｔ）であった場合には、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）としてＡｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）に相当するａｉ＝ｓｉｅｉｃｉ−１ｍｏｄ  Ｎｉを選択する。そして、関数型選択部１３２は、この選択した関数を関数メモリ１３１から抽出し、コミットメント回復部１３６に送る。
【００４１】
このコミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）を受け取ったコミットメント回復部１３６は、これにｐｋｉ，ｓｉ，ｃｉ’’を代入し、その演算結果ａｉ’をハッシュ関数演算部１３７に送る（ステップＳ３６）。その後、制御部１４１のカウント値ｉを１加算し（ステップＳ３７）、その結果ｉ＞ｎとなったか否かを判断する（ステップＳ３８）。ここで、ｉ＞ｎとなっていない場合にはステップＳ３５の処理に戻り、ｉ＞ｎとなった場合には、ハッシュ関数演算部１３７において、Ｌ、ｋ、ｐ、ａ１’，…，ａｉ’、ｍをビット結合し、そのビット結合結果のハッシュ値ｚ０’＝Ｈ（Ｌ‖ｋ‖ｐ‖ａ１’‖…‖ａｎ’‖ｍ）を求める（ステップＳ３９）。求められたハッシュ値ｚ０’は多項式評価部１３８に送られ、多項式評価部１３８は、多項式代入部１３５から取得した一変数多項式Ｐ（Ｘ）に０を代入し（ステップＳ４０）、その代入結果ｚ０とハッシュ値ｚ０’が等しいか否かを判断する（ステップＳ４１）。ここで等しいと判断された場合、多項式評価部１３８は、その旨の情報（Ｇ）を出力部１３９に送り、出力部１３９は署名を受理する旨の検証結果を出力する（ステップＳ４２）。一方、等しくないと判断された場合には、多項式評価部１３８は、その旨の情報（ＮＧ）を出力部１３９に送り、出力部１３９は署名を拒否する旨の検証結果を出力する（ステップＳ４３）。
【００４２】
このように、本形態では、ｋ−ｏｕｔ−ｏｆ−ｎ匿名署名の構成において、少なくとも一部の署名権能者に対応する、コミットメント作成関数Ａｉ（ｓｋ，ｒ）をＡｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数とし、コミットメント回復関数を、二項演算ａ（＋）ｉｂ及びａ（−）ｉｂを（ａ（＋）ｉｂ）（−）ｉｂ＝ａを満たす演算とした場合における、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）とし、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）を、Ｆｉの逆置換関数をＩｉとした場合におけるＩｉ（ｓｋ，ｃ（＋）ｉｒ）とすることとした。そのため、従来、離散対数型の署名方式しか用いることができなかったｋ−ｏｕｔ−ｏｆ−ｎ匿名署名において、落とし戸型の署名をも用いることが可能となり、匿名署名に使用できる署名方式の多様化を図ることが可能となった。また、ｋ−ｏｕｔ−ｏｆ−ｎ匿名署名の構造をそのまま採ることができるため、署名協力者数の多様性も確保できる。
さらに、この例では、関数型選択部１１２、１３２において、落とし戸付き一方向性置換関数に基づく署名方式を採っている署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）として、Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数を選択し、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）として、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）を選択し、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）としてＩｉ（ｓｋ，ｃ（＋）ｉｒ）を選択し、離散対数問題に基づく署名方式を採っている署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）、及び回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）として、離散対数型の関数を選択することとした。落とし戸付き一方向性置換関数に基づく署名方式を採っている署名権能者、及び離散対数問題に基づく署名方式を採っている署名権能者双方を署名者に採りこむことができ、匿名署名の利便性及び信頼性を向上させることが可能となった。
【００４３】
また、少なくとも一部の署名権能者に対応するコミットメント作成関数Ａｉ（ｓｋ，ｒ）を、ｒを出力する関数とすることにより、演算処理を簡略化することが可能となった。
なお、この発明は上述の実施の形態に限定されるものではない。例えば、本形態では、離散対数を構成する群としてｐｉを素数とする乗法群Ｚｐｉを、また、落とし戸付き一方向性関数としてＲＳＡ演算を用いる場合を例にとって説明したが、離散対数問題を構成する群は、楕円曲線上の加法群をはじめ、その元を容易に標本できるような有限群であるならば、どのような群であってもよい。
また、本形態では、コンピュータ上で所定のプログラムを実行させることにより、匿名署名装置１、１３０及び署名検証装置２０、１３０を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
また、上述のように、この形態における処理機能は、コンピュータによって実現することができる。この場合、匿名署名装置１、１３０及び署名検証装置２０、１３０が有すべき機能の処理内容はプログラムによって記述され、このプログラムをコンピュータで実行することにより、上記処理機能をコンピュータ上で実現することができる。
【００４４】
また、この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ＤＶＤ−ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｒｅｃｏｒｄａｂｌｅ）／ＲＷ（ＲｅＷｒｉｔａｂｌｅ）等を、光磁気記録媒体として、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｃ）等を、半導体メモリとしてＥＰＲＯＭ（Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）等を用いることができる。
【００４５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することしてもよく、さらに、コンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【００４６】
【発明の効果】
以上説明したようにこの発明では、少なくとも一部の署名権能者に対応する、コミットメント作成関数Ａｉ（ｓｋ，ｒ）を、Ａｉ（ｓｋ，ｒ）＝Ａｉ（ｐｋ，ｒ）となる関数とし、コミットメント回復関数Ｖｉ（ｐｋ，ｓ，ｃ）を、識別子ｉに対応する落とし戸付き一方向性置換関数をＦｉとし、二項演算ａ（＋）ｉｂ及びａ（−）ｉｂを（ａ（＋）ｉｂ）（−）ｉｂ＝ａを満たす演算とした場合における、Ａｉ（ｐｋ，Ｆｉ（ｐｋ，ｓ）（−）ｉｃ）とし、回答作成関数Ｚｉ（ｓｋ，ｒ，ｃ）を、Ｆｉの逆置換関数をＩｉとした場合におけるＩｉ（ｓｋ，ｃ（＋）ｉｒ）とした。これにより、離散対数型の署名方式に加え、落とし戸型の署名方式をも匿名署名に組み込むことが可能となり、匿名署名に使用できる署名方式の多様性を向上させることができる。また、従来のｋ−ｏｕｔ−ｏｆ−ｎ匿名署名に落とし戸型の署名方式を組み込むことができるため、従来のｋ−ｏｕｔ−ｏｆ−ｎ匿名署名と同様、署名協力者数の自由度を確保することができる。
【図面の簡単な説明】
【図１】匿名署名装置１の概略を例示した機能ブロック図。
【図２】署名検証装置の概略を例示した機能ブロック図。
【図３】匿名署名システムの全体構成を例示した概念図。
【図４】匿名署名装置のハードウェア構成を例示したブロック図。
【図５】匿名署名装置の機能構成を例示したブロック図。
【図６】関数メモリに記録される関数表のデータ構成を例示した概念図。
【図７】公開鍵リスト及び秘密鍵リストのデータ構成を例示した概念図。
【図８】署名検証装置の機能構成を例示したブロック図。
【図９】関数メモリに記録される関数表のデータ構成を例示した概念図。
【図１０】匿名署名の生成処理を説明するためのフローチャート。
【図１１】匿名署名の生成処理を説明するためのフローチャート。
【図１２】署名検証処理を説明するためのフローチャート。
【図１３】多項式検証部における処理を説明するためのフローチャート。
【図１４】関数型選択部における処理を説明するためのフローチャート。
【図１５】関数型選択部における処理を説明するためのフローチャート。
【図１６】Ｒｉｎｇ型署名方法を説明するための概念図。
【符号の説明】
１、１１０  匿名署名装置
２０、１３０  署名検証装置
１１２、１３２  関数型選択部
２００  関数表
２１０  公開鍵リスト
【図１】
2004312512.tif 000004
【図２】
2004312512.tif 000005
【図３】
2004312512.tif 000006
【図４】
2004312512.tif 000007
【図５】
2004312512.tif 000008
【図６】
2004312512.tif 000009
【図７】
2004312512.tif 000010
【図８】
2004312512.tif 000011
【図９】
2004312512.tif 000012
【図１０】
2004312512.tif 000013
【図１１】
2004312512.tif 000014
【図１２】
2004312512.tif 000015
【図１３】
2004312512.tif 000016
【図１４】
2004312512.tif 000017
【図１５】
2004312512.tif 000018
【図１６】
2004312512.tif 000019