(57)【特許請求の範囲】
【請求項１】
署名受信装置と、該署名受信装置と通信する署名装置と、前記署名受信装置の出力を入力とする署名提示装置と、該署名提示装置と通信する署名検証装置とからなり、前記署名提示装置が署名受信装置から受け取ったブラインド公開識別子を変更を加えずに署名検証装置に送信する制限付ブラインド署名システムであって、
前記署名装置は、秘密のデータである前記署名装置の秘密鍵と、該秘密鍵に対応する公開鍵と、第1の乱数とが入力され、前記秘密鍵と前記公開鍵と前記第1の乱数から第１のブラインド署名を生成して、該第1のブラインド署名を前記署名受信装置へ出力し、
前記署名受信装置は、前記署名装置の公開鍵と、メッセージと、秘密のデータである前記署名受信装置の秘密識別子と、公開されているデータであり、前記秘密識別子に依存したデータである前記署名受信装置の公開識別子と、第２の乱数とが入力されて、該第２の乱数から秘密のデータであるブラインド因子を生成し、前記秘密識別子と前記ブラインド因子とから計算されるブラインド秘密識別子を生成して出力し、前記ブラインド秘密識別子と前記第1のブラインド署名に依存したデータであるブラインド公開識別子を生成して出力し、前記第１のブラインド署名から前記メッセージがメンバー証明書の一部となるグループ署名である第２のブラインド署名を生成して出力し、前記公開鍵と前記第２の乱数から前記ブラインド秘密識別子のコミットであるブラインドコミットメントを生成して出力し、前記公開識別子の送信作業を含むデータの通信を前記署名装置と行い、
前記署名提示装置は、前記公開鍵と、前記ブラインド秘密識別子と、前記ブラインド公開識別子と、前記第２のブラインド署名と、第３の乱数と、が入力され、これらの入力状態を示す入力状態表示信号を前記署名検証装置へ出力し、
前記署名検証装置は、前記入力状態表示信号と、前記公開鍵と、前記ブラインド公開識別子と、第４の乱数と、が入力され、これらの各入力が、前記ブラインド公開識別子、前記ブラインド秘密識別子、前記第２のブラインド署名が前記署名提示装置に入力されていることを示す場合には「正当」を、その他の場合には「不当」を出力することを特徴とする制限付ブラインド署名システム。
【請求項２】
請求項１記載の制限付ブラインド署名システムを構成する署名受信装置であって、
前記第２のブラインド署名が前記秘密鍵により生成されたグループ署名であることを特徴とする署名受信装置。
【請求項３】
請求項１記載の制限付ブラインド署名システムを構成する署名装置であって、
前記ブラインドコミットメントを獲得する前記通信手段を備え、前記ブラインドコミットメントがコミットしたデータであるブラインド秘密識別子に対する署名である第１のブラインド署名を前記秘密鍵により生成されたグループ署名として生成することを特徴とする署名装置。
【請求項４】
請求項２記載の署名受信装置において、
前記秘密識別子と前記第２の乱数とを入力し、前記第２の乱数からブラインド因子を生成し、前記ブラインド因子と前記秘密識別子からブラインド秘密識別子を生成し出力するブラインド秘密識別子生成装置と、
前記公開鍵と前記ブラインド秘密識別子と前記第２の乱数が入力され、前記ブラインド秘密識別子のコミットメントであるブラインドコミットメントを生成して前記署名装置に送付するブラインドコミットメント生成装置と、
前記公開識別子を署名装置に送付する公開識別子送信装置と、
前記ブラインド秘密識別子と前記第２の乱数とが入力され、前記署名装置と通信することで、前記ブラインドコミットメントが前記ブラインド秘密識別子のコミットメントであることの知識の証明を前記署名装置に対して行うブラインドコミットメント証明装置と、
前記署名装置から前記ブラインドコミットメントによりコミットされた前記ブラインド秘密識別子に対するグループ署名である第１のブラインド署名を受け取り、前記署名を検証して第２のブラインド署名を出力するブラインド署名受信装置と、
を含むことを特徴とする署名受信装置。
【請求項５】
請求項３記載の署名装置において、
前記署名受信装置と通信することにより署名受信装置の公開識別子を受信する公開識別子受信装置と、
前記署名受信装置より送られたブラインドコミットメントを受信し、前記署名装置の公開識別子とブラインドコミットメントと公開鍵と前記第１の乱数とが入力され、署名受信装置と通信することにより前記公開識別子が依存するデータである秘密識別子と乱数から生成されたあるブラインド因子とから計算されるあるブラインド秘密識別子が前記署名受信装置に存在している場合には前記ブラインドコミットメントはこのブラインド秘密識別子のコミットメントであることの知識の証明を検証し、証明を正当と認めれば「正当」をその他の場合は「不当」を出力するブラインドコミットメント検証装置と、
前記秘密鍵と公開鍵と前記ブラインドコミットメントと前記第１の乱数とが入力され、前記ブラインドコミットメント検証装置が「正当」を出力すれば前記ブラインドコミットメントがコミットしたブラインド秘密識別子に対するグループ署名を生成し、署名受信装置に送信するグループ署名生成装置と、
を含むことを特徴とする署名装置。
【請求項６】
請求項１記載の制限付ブラインド署名システムを構成する署名提示装置であって、
前記公開鍵と、前記ブラインド公開識別子と、前記ブラインド秘密識別子と、前記第２のブラインド署名と、前記第３の乱数とが入力され、
前記入力状態を示す信号として、
入力された前記ブラインド公開識別子を前記署名検証装置に送付し、
あるブラインド秘密識別子が存在して、前記ブラインド公開識別子がこのブラインド秘密識別子に依存するデータであることの知識の証明と、このブラインド秘密識別子に対するグループ署名である第２のブラインド署名の知識の証明とを署名検証装置と通信して行う知識証明装置を含むことを特徴とする署名提示装置。
【請求項７】
請求項１記載の制限付ブラインド署名システムを構成する署名検証装置であって、
前記ブラインド公開識別子を前記署名提示装置より受信し、前記公開鍵と、前記第４の乱数と、が入力され、あるブラインド秘密識別子が存在して前記ブラインド公開識別子がこのブラインド秘密識別子に依存するデータであることの知識の証明とこのブラインド秘密識別子に対するグループ署名である第２のブラインド署名の知識の証明との検証を前記署名提示装置と通信して行う知識証明検証装置を含むことを特徴とする署名検証装置。
【請求項８】
請求項４記載の署名受信装置において、
前記ブラインドコミットメント証明装置は、
証明コミットメント装置と、第１の挑戦値獲得装置と、証明レスポンス装置よりなり、前記証明コミットメント装置は、乱数のコミットメントである証明コミットメントを生成するものであり、前記第１の挑戦値獲得装置は証明コミットメントを前記署名装置に送付し、前記署名装置から挑戦値を受信するものであり、前記証明レスポンス装置は、前記挑戦値と、前記証明コミットメントの生成に使った前記第２の乱数と前記ブラインド秘密識別子と前記ブラインド因子とから証明のレスポンスを生成するものであることを特徴とする署名受信装置。
【請求項９】
請求項５記載の署名装置において、
前記ブラインドコミットメント検証装置は、第１の挑戦値生成装置と、証明検証装置よりなり、前記第１の挑戦値生成装置は、証明のコミットメントと呼ばれるデータを受信するのを待ち、受信したならば前記乱数を用いてランダムな数である挑戦値を生成し、前記署名受信装置に送付し、前記署名検証装置は、前記署名受信装置より証明のレスポンスと呼ばれるデータを受信するのを待ち、これを受信したら、前記証明のコミットメント、前記挑戦値、前記証明のレスポンスが、ある検証式を満たすかどうかで、「正当」あるいは「不当」を出力するものであることを特徴とする署名装置。
【請求項１０】
請求項６記載の署名提示装置において、
第２の挑戦値獲得装置を備え、証明のコミットメントの他に公開鍵とブラインド公開識別子が入力され、前記証明のコミットメントと前記公開鍵と前記ブラインド公開識別子を含むデータのハッシュ値を挑戦値として出力することを特徴とする署名提示装置。
【請求項１１】
請求項７記載の署名検証装置において、
第２の挑戦値生成装置を備え、前記証明のコミットメントと前記公開鍵と前記ブラインド公開識別子を含むデータのハッシュ値を挑戦値として出力することを特徴とする署名検証装置。
【請求項１２】
署名受信装置と、該署名受信装置と通信する署名装置と、前記署名受信装置出力を入力する署名提示装置と、該署名提示装置と通信する署名検証装置とからなる制限付ブラインド署名システムであって、
前記署名装置は、秘密のデータである前記署名装置の秘密鍵と、該秘密鍵に対応する公開鍵と、第１の乱数とが入力され、前記秘密鍵と前記公開鍵と前記第1の乱数から第１のブラインド署名を生成して、該第1のブラインド署名を前記署名受信装置へ出力し、
前記署名受信装置は、前記署名装置の公開鍵と、メッセージと、第２の乱数と、前記第１のブラインド署名とが入力され、これらの各入力から前記メッセージがメンバー証明書の一部となるグループ署名である第２のブラインド署名を出力し、
前記署名提示装置には、前記公開鍵と、前記メッセージと、前記署名受信装置の出力である前記第２のブラインド署名と、第３の乱数と、が入力され、これらの入力状態を示す信号を前記署名検証装置へ出力し、
前記署名検証装置は、前記公開鍵と、第４の乱数と、が入力され、これらの各入力が、前記メッセージ、前記第２のブラインド署名が前記署名提示装置に入力されていることを示す場合には「正当」を、その他の場合には「不当」を出力することを特徴とする制限付ブラインド署名システム。
【請求項１３】
請求項１２記載の制限付ブラインド署名システムを構成する署名受信装置であって、
前記メッセージのコミットメントであるブラインドコミットメントを前記署名装置に送信することを特徴とする署名受信装置。
【請求項１４】
請求項１２記載の制限付ブラインド署名システムを構成する署名装置であって、
前記メッセージのコミットメントであるブラインドコミットメントを入力し、前記ブラインドコミットメントがコミットしたデータであるメッセージに対する署名であり、かつ、前記秘密鍵により生成された、メンバ証明書に前記メッセージを含むグループ署名である第１のブラインド署名を生成して前記署名受信装置に送ることを特徴とする署名装置。
【請求項１５】
請求項１３に記載の署名受信装置において、
前記公開鍵と前記メッセージと前記乱数が入力され、前記メッセージのコミットメントであるブラインドコミットメントを生成し、前記署名装置に送付するブラインドコミットメント生成装置と、
前記メッセージと前記公開鍵と前記乱数とが入力され、署名装置と通信することで、
前記ブラインドコミットメントが前記メッセージのコミットメントであることの知識の証明を署名装置に対して行う証明コミットメント装置と、
前記署名装置から前記ブラインドコミットメントによりコミットメントされた第１のブラインド署名を受け取って検証し、第２のブラインド署名を出力するブラインド署名受信装置と、
を含むことを特徴とする署名受信装置。
【請求項１６】
請求項１４に記載の署名装置において、
公開鍵と、乱数と、ともに、前記署名受信装置から送られたブラインドコミットメントとが入力され、前記ブラインドコミットメントが前記メッセージのコミットメントであることの知識の証明を検証し、証明結果が正当と認めるものであれば「正当」を、その他の場合は「不当」を出力する証明検証装置と、
前記秘密鍵と公開鍵と前記ブラインドコミットメントと乱数とが入力され、前記証明検証装置が「正当」を出力すると、前記ブラインドコミットメントがコミットメントしたメッセージをメンバ証明書として含むグループ署名を生成し，署名受信装置に送信するグループ署名生成装置と、
を含むことを特徴とする署名装置。
【請求項１７】
請求項１２記載の制限付ブラインド署名システムを構成する署名提示装置であって、
前記メッセージを前記署名検証装置に送付し、メッセージがメンバ証明書に含まれるグループ署名について、メンバ証明の知識を保持す知識証明装置を、
含むことを特徴とする署名提示装置。
【請求項１８】
請求項１２記載の制限付ブラインド署名システムを構成する署名検証装置であって、
メッセージを前記署名提示装置より受信し、前記署名提示装置がメッセージをメンバ証明書に含むグループ署名のメンバ証明の知識を保持していることの検証を行う知識検証装置を、
含むことを特徴とする署名検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名者が署名受信者の決定したメッセージを知ることなく、このメッセージに対する署名を署名受信者が受け取ることができるブラインド署名方法および装置に関し、特に、署名受信者が受け取ることができる署名が、署名受信者の公開された識別子と関連づけられたメッセージに限る制限付ブラインド署名システムおよび装置に関する。
【背景技術】
【０００２】
[従来の技術１]
従来の制限付ブラインド署名の例として、非特許文献1（"Untraceable  Off-line  Cash  in  Wallets  with  Observers  (Extended  Abstract",  Advances  in  Cryptology,  Proceedings  Crypto'93,  Lecture  Note  on  Computer  Science  773,  D.  Stinson,  Ed.,  Springer-Verlag,  1994  pp.302-318）に掲載されている方法がある。【０００３】
上記の方式を以下に簡単に説明する。制限付ブラインド署名は３、署名者が用いる署名装置、署名受信者が用いる署名受信装置、署名受取人が示す署名を検証するための署名検証装置の３個の装置が使われる。以下では、pとqをq|p-1なる素数.Gqを体(Z/pZ)*の位数qの元の集合とする。【０００４】
g,  g[1]  と  g[2]  は  Gq  の元、u[1]  はZ/qZ  の元で、I=g[1]u[1]  mod  pを署名受取装置の公開された識別子とする。x  はZ/qZ  の元で、署名者の秘密鍵で、h=gx  mod  pは署名者の公開鍵とする。Hash  は暗号学的なハッシュ関数とする。【０００５】
署名装置から署名受信装置は以下の手順で制限付ブラインド署名を受け取る。【０００６】
署名装置は
z  =  (Ig[2])x  mod  p
を計算し、署名受信装置に送る。【０００７】
署名装置は、無作為に  w  をZq  から選び、
a  =  gw  mod  p
b  =  (I  g[2])w  mod  p
を計算し、a,b  を署名受信装置へ送信する。【０００８】
署名受信装置は,  s,x[1],x[2],u,v  をZ/qZ  からランダムに選び、
A  =  (Ig[2])s  mod  p
z'  =  zs  mod  p
B  =  g[1]x[1]g[2]x[2]  mod  p
a'  =  augv
b'  =  bsuAv  mod  p
c'  =  Hash(A,B,z',a',b')
c  =  c'/u  mod  q
を計算し、c  を署名装置に送信する。【０００９】
署名装置は
r  =  c  x+  w  mod  q
を計算して、r  を署名受信装置に送信する。【００１０】
署名受信装置は、
r  =  hc  a  mod  p
Ig[2])r  =  zc  b  mod  p
が成り立つことを確認し、成り立たなければ、正当な署名を受け取れなかったものとして修了する。成り立てば、
r'  =  ru+v  mod  q
を求め、署名受信装置は(A,B,z',a',b',r')  を制限付ブラインド署名とする。【００１１】
署名検証装置の動作を以下に表す。【００１２】
署名検証装置は、
c'=Hash(A,B,z',a',b',r')  を計算し、
gr'  =  hc'a'  mod  p
Ar'  =  z'c'b'  mod  p
なる関係を満たすかどうかを調べる。両式が満たされるならば制限付ブラインド署名は正当であると見なし、その他の場合は不当な署名であると見なす。【００１３】
上記制限付ブラインド署名の特徴を記す。【００１４】
上記署名検証装置が確認するような関係を満たす、  (A,B,z',a',b',r')  は署名装置の秘密鍵xがなくては計算できない値の組であり、このような組は,  署名装置が何らかの承認を与えたことを意味すると考えることができる。このような意味において本手続きは署名手続きの一種である。【００１５】
又、署名装置は(A,B,z',a',b',r')  を上記署名手続きにおいて入手することはできない。又、  (A,B,z',a',b',r')  を入手しても、I  に関する署名手続きを行った際に署名受信装置が入手し得たものなのか判別することができない。この意味において、本署名手続きはブラインド署名の一種である。【００１６】
又、(A,z')  は、
z'=  Ax  mod  p
を満たす。署名受取人はこのような関係を満たす(A,B,z',a',b',r')  のみしか署名者との通信によって手にいれることができないという意味において、このブラインド署名は、制限付ブラインド署名と呼ばれる。【００１７】
上記制限付ブラインド署名の有用な応用例として、オフライン匿名電子現金があげられる。【００１８】
この技術を電子現金に応用する場合、銀行が署名装置を保持し、銀行に口座を持つ者の識別子をI  とし、電子現金(A,B,z',a',b',r')  を引き落とす。この時、  I  の口座から対応する金額を引き落とす。I  は電子現金を使用するとき、  (A,B,z',a',b',r')  を相手に渡す。これは、銀行の協力がなければ作れないものであるので、受取人は電子現金を信用することができる。受取人はこれを銀行に持っていき、対応する金額を受け取ることができる。この時、I  と電子現金の対応は、電子現金がブラインド署名であるため銀行には分からなく、支払いの匿名性が確保できる。一方、電子現金は単なるデータであるため、二重使用が容易である。しかし、二回使用した場合、電子現金にはI  と一定の関係があるという制限がついていたため、二重使用を行ったIを特定することができる。この性質により二重使用を避けることができる。上では省略したが、上記の支払い手続きは、単なるデータの受け渡しではなく、特殊なプロトコルを使うことにより、二回使用した場合に、Iとの関係が発覚するようになっている。【００１９】
上記従来の技術はランダムオラクモデルを仮定すると安全であることが知られている。ランダムオラクルモデルとは、およそ、上記ハッシュ関数が真の乱数を返す関数であるとする仮定である。【００２０】
［従来の技術２（グループ署名）］
従来、この種のグループ署名システムは、複数のメンバーから構成されるグループにおいて、グループに所属する、あるユーザが署名を作成し、また、その署名を確認するためのものである。そして、その署名は、署名者がグループのいずれかのメンバーであることは検証できるが、通常ではグループ内のどのメンバーであるかは分からないという性質のものである。ただし、その一方で、万が一のために、署名から実際の署名者を特定する機能（以下、追跡と称す）がグループ署名システムには備えられている。【００２１】
一般に、グループ署名システムでは、グループ管理者と呼ばれるエンティティがグループ内に存在し、グループへの新たなメンバーの登録手続きおよび署名者の追跡を行う。その場合、グループ署名システムにおいて、グループへのメンバーの登録や、グループ署名の署名者追跡は、全てグループ管理者の権限で行われることとなる。【００２２】
非特許文献２（G.  Ateniese,  J.  Camenisch,  M.  Joye  and  G.  Tsudik,  “A  Practical  and  Provable  Secure  Coalition-Resistant  Group  Signature  Scheme,  ”In  Advances  in  Cryptology--CRYPTO2000,  LNCS  1880,  pp.255-270,  Springer-Verlag,  2000．）に記載された第１の従来技術のグループ署名システムは、公開情報開示手段と署名装置とを有している。【００２３】
図１は、非特許文献２に開示される技術によるグループ署名システムにおける署名装置の構成を示すブロック図である。図１を参照すると、署名装置は、第１の乱数生成器９０１、第２の乱数生成器９０２、第３の乱数生成器９０３、第４の乱数生成器９０４、第５の乱数生成器９０５、第６の乱数生成器９０６、第１の暗号化データ作成手段９０７、第２の暗号化データ作成手段９０８、第１の変換データ作成手段９０９、第２の変換データ作成手段９１０、知識署名作成手段９１１、メンバー情報記憶部９１２、秘密情報記憶部９１３、メッセージ入力手段９１４および署名出力手段９１５から構成されている。【００２４】
第１の乱数生成器９０１は、第１の暗号化データ作成手段９０７で使用する乱数を生成する。【００２５】
第２の乱数生成器９０２は、第２の暗号化データ作成手段９０８で使用する乱数を生成する。【００２６】
第３の乱数生成器９０３は、第１の変換データ作成手段９０９で使用する乱数を生成するとともに、その乱数をグループ署名の要素として署名出力手段９１５に出力する。【００２７】
第４の乱数生成器９０４は、第２の変換データ作成手段９１０で使用する乱数を生成するとともに、その乱数をグループ署名の要素として署名出力手段９１５に出力する。【００２８】
第５の乱数生成器９０５は、第２の変換データ作成手段９１０で使用する乱数を生成するとともに、その乱数をグループ署名の要素として署名出力手段９１５に出力する。【００２９】
第６の乱数生成器９０６は、知識署名作成手段９１１で使用する乱数を生成する。【００３０】
第１の暗号化データ作成手段９０７は、第１の乱数生成器９０１で生成された乱数と、メンバー情報記憶部９１２に記憶されているメンバー証明書の第１の要素とを入力として、メンバー証明書の第１の要素の暗号化データ（以下、第１の暗号化データと称す）を知識署名作成手段９１１および署名出力手段９１５に出力する。【００３１】
第２の暗号化データ作成手段９０８は、第２の乱数生成器９０２で生成された乱数と、秘密情報記憶部９１３に記憶されている署名鍵の変換データとを入力として、署名鍵の変換データの第１の要素の暗号化データ（以下、第２の暗号化データと称す）を知識署名作成手段９１１および署名出力手段９１５に出力する。【００３２】
第１の変換データ作成手段９０９は、第３の乱数生成器９０３で生成された乱数と、メンバー情報記憶部９１２に記憶されているメンバー証明書の第１の要素を入力として、メンバー証明書の第１の要素の変換データ（以下、第１の変換データと称す）を知識署名作成手段９１１および署名出力手段９１５に出力する。【００３３】
第２の変換データ作成手段９１０は、第４の乱数生成器９０４および第５の乱数生成器９０５で生成された乱数と、メンバー情報記憶部９１２に記憶されているメンバー証明書の第１の要素を入力として、メンバー証明書の第１の要素の変換データ（以下、第２の変換データと称す）を知識署名作成手段９１１および署名出力手段９１５に出力する。【００３４】
知識署名作成手段９１１は、メッセージ入力手段９１４から入力されたメッセージ、第６の乱数生成器９０６で生成された乱数、第１の暗号化データ、第２の暗号化データ、第１の変換データ、第２の変換データ、メンバー証明書の第１および第２の要素、および署名鍵を入力として、メンバー証明書および署名鍵に関する情報を漏らすことなくメンバー証明書および署名鍵を正しく所有していることを証明することのできる知識署名データを出力する。【００３５】
メンバー情報記憶部９１２は、グループ署名を発行するために用いるメンバー証明書を記憶する。メンバー証明書は第１の要素と第２の要素とからなる。【００３６】
秘密情報記憶部９１３は署名鍵を記憶する。【００３７】
メッセージ入力手段９１４は、署名を付加すべきメッセージを入力する。【００３８】
署名出力手段９１５は、メッセージ、第１の暗号化データ、第２の暗号化データ、第１の変換データ、第２の変換データ、第３の乱数、第４の乱数、第５の乱数、および知識署名データをグループ署名として出力する。【００３９】
以上の構成により、第１の従来技術のグループ署名システムはグループ署名を作成することができる。【００４０】
上記の技術では、ハッシュ関数を使っているためにランダムオラクルモデルのもとでしか方式の安全性が証明されないことである。ランダムオラクルモデルのもとで安全性が証明されたある暗号方式で、ハッシュ関数を具体的な関数に置き換えた場合、そのハッシュ関数がいかなる良い性質を持っていようと、決して安全にならないことが非特許文献３（Ran  Canetti,  Oded  Goldreich,  Shai  Halevi:  The  Random  Oracle  Methodology,  Revisited  (Preliminary  Version).  STOC  1998:  209-218]）に示されている。
【非特許文献１】"Untraceable  Off-line  Cash  in  Wallets  with  Observers  (Extended  Abstract",  Advances  in  Cryptology,  Proceedings  Crypto'93,  Lecture  Note  on  Computer  Science  773,  D.  Stinson,  Ed.,  Springer-Verlag,  1994  pp.302-318
【非特許文献２】G.  Ateniese,  J.  Camenisch,  M.  Joye  and  G.  Tsudik,  “A  Practical  and  Provable  Secure  Coalition-Resistant  Group  Signature  Scheme,  ”In  Advances  in  Cryptology--CRYPTO2000,  LNCS  1880,pp.255-270,Springer-Verlag,2000．
【非特許文献３】Ran  Canetti,  Oded  Goldreich,  Shai  Halevi:  The  Random  Oracle  Methodology,  Revisited  (Preliminary  Version).  STOC  1998:  209-218]
【発明の開示】
【発明が解決しようとする課題】
【００４１】
従来の技術の問題点は、ハッシュ関数を使っているためにランダムオラクルモデルのもとでしか方式の安全性が証明されないことである。ランダムオラクルモデルのもとで安全性が証明されたある暗号方式で、ハッシュ関数を具体的な関数に置き換えた場合、そのハッシュ関数がいかなる良い性質を持っていようと、決して安全にならない方式であることが知られている。すなわち、ランダムオラクルモデルのもとで安全性が証明された暗号方式は、暗号の安全性が何らかの解くことが困難であろうと予想されている問題の困難性に帰着されるわけではない。このことは、従来の技術の方式に対して示された安全性の根拠はかなり弱いといえる。よって、例えば従来の技術を用いた電子現金は偽造が可能で、使用者が分からないまま大量に複製して使用することができる可能性がある。【００４２】
本発明の目的は、ランダムオラクルモデルを仮定する事なく安全性を証明できるという高い安全性を持った、制限付ブラインド署名システムを提案することである。
【課題を解決するための手段】
【００４３】
本発明の制限付ブラインド署名システムは、署名受信装置と、該署名受信装置と通信する署名装置と、前記署名受信装置の出力を入力とする署名提示装置と、該署名提示装置と通信する署名検証装置とからなり、前記署名提示装置が署名受信装置から受け取ったブラインド公開識別子を変更を加えずに署名検証装置に送信する制限付ブラインド署名システムであって、
前記署名装置は、秘密のデータである前記署名装置の秘密鍵と、該秘密鍵に対応する公開鍵と、第1の乱数とが入力され、前記秘密鍵と前記公開鍵と前記第1の乱数から第１のブラインド署名を生成して、該第1のブラインド署名を前記署名受信装置へ出力し、
前記署名受信装置は、前記署名装置の公開鍵と、メッセージと、秘密のデータである前記署名受信装置の秘密識別子と、公開されているデータであり、前記秘密識別子に依存したデータである前記署名受信装置の公開識別子と、第２の乱数とが入力されて、該第２の乱数から秘密のデータであるブラインド因子を生成し、前記秘密識別子と前記ブラインド因子とから計算されるブラインド秘密識別子を生成して出力し、前記ブラインド秘密識別子と前記第1のブラインド署名に依存したデータであるブラインド公開識別子を生成して出力し、前記第１のブラインド署名から前記メッセージがメンバー証明書の一部となるグループ署名である第２のブラインド署名を生成して出力し、前記公開鍵と前記第２の乱数から前記ブラインド秘密識別子のコミットであるブラインドコミットメントを生成して出力し、前記公開識別子の送信作業を含むデータの通信を前記署名装置と行い、
前記署名提示装置は、前記公開鍵と、前記ブラインド秘密識別子と、前記ブラインド公開識別子と、前記第２のブラインド署名と、第３の乱数と、が入力され、これらの入力状態を示す入力状態表示信号を前記署名検証装置へ出力し、
前記署名検証装置は、前記入力状態表示信号と、前記公開鍵と、前記ブラインド公開識別子と、第４の乱数と、が入力され、これらの各入力が、前記ブラインド公開識別子、前記ブラインド秘密識別子、前記第２のブラインド署名が前記署名提示装置に入力されていることを示す場合には「正当」を、その他の場合には「不当」を出力することを特徴とする。
【００４４】
本発明の署名受信装置は、上記の制限付ブラインド署名システムを構成する署名受信装置であって、
前記第２のブラインド署名が前記秘密鍵により生成されたグループ署名であることを特徴とする。
【００４５】
本発明の署名装置は、上記の制限付ブラインド署名システムを構成する署名装置であって、
前記ブラインドコミットメントを獲得する前記通信手段を備え、前記ブラインドコミットメントがコミットしたデータであるブラインド秘密識別子に対する署名である第１のブラインド署名を前記秘密鍵により生成されたグループ署名として生成することを特徴とする。
【００４６】
上記の署名受信装置は、前記秘密識別子と前記第２の乱数とを入力し、前記第２の乱数からブラインド因子を生成し、前記ブラインド因子と前記秘密識別子からブラインド秘密識別子を生成し出力するブラインド秘密識別子生成装置と、
前記公開鍵と前記ブラインド秘密識別子と前記第２の乱数が入力され、前記ブラインド秘密識別子のコミットメントであるブラインドコミットメントを生成して前記署名装置に送付するブラインドコミットメント生成装置と、
前記公開識別子を署名装置に送付する公開識別子送信装置と、
前記ブラインド秘密識別子と前記第２の乱数とが入力され、前記署名装置と通信することで、前記ブラインドコミットメントが前記ブラインド秘密識別子のコミットメントであることの知識の証明を前記署名装置に対して行うブラインドコミットメント証明装置と、
前記署名装置から前記ブラインドコミットメントによりコミットされた前記ブラインド秘密識別子に対するグループ署名である第１のブラインド署名を受け取り、前記署名を検証して第２のブラインド署名を出力するブラインド署名受信装置と、
を含むこととしてもよい。
【００４７】
上記の署名装置は、
前記署名受信装置と通信することにより署名受信装置の公開識別子を受信する公開識別子受信装置と、
前記署名受信装置より送られたブラインドコミットメントを受信し、前記署名装置の公開識別子とブラインドコミットメントと公開鍵と前記第１の乱数とが入力され、署名受信装置と通信することにより前記公開識別子が依存するデータである秘密識別子と乱数から生成されたあるブラインド因子とから計算されるあるブラインド秘密識別子が前記署名受信装置に存在している場合には前記ブラインドコミットメントはこのブラインド秘密識別子のコミットメントであることの知識の証明を検証し、証明を正当と認めれば「正当」をその他の場合は「不当」を出力するブラインドコミットメント検証装置と、
前記秘密鍵と公開鍵と前記ブラインドコミットメントと前記第１の乱数とが入力され、前記ブラインドコミットメント検証装置が「正当」を出力すれば前記ブラインドコミットメントがコミットしたブラインド秘密識別子に対するグループ署名を生成し、署名受信装置に送信するグループ署名生成装置と、
を含むこととしてもよい。
【００４８】
本発明の署名提示装置は、上記の制限付ブラインド署名システムを構成する署名提示装置であって、
前記公開鍵と、前記ブラインド公開識別子と、前記ブラインド秘密識別子と、前記第２のブラインド署名と、前記第３の乱数とが入力され、
前記入力状態を示す信号として、
入力された前記ブラインド公開識別子を前記署名検証装置に送付し、
あるブラインド秘密識別子が存在して、前記ブラインド公開識別子がこのブラインド秘密識別子に依存するデータであることの知識の証明と、このブラインド秘密識別子に対するグループ署名である第２のブラインド署名の知識の証明とを署名検証装置と通信して行う知識証明装置を含むことを特徴とする。
【００４９】
本発明の署名検証装置は、上記の制限付ブラインド署名システムを構成する署名検証装置であって、
前記ブラインド公開識別子を前記署名提示装置より受信し、前記公開鍵と、前記第４の乱数と、が入力され、あるブラインド秘密識別子が存在して前記ブラインド公開識別子がこのブラインド秘密識別子に依存するデータであることの知識の証明とこのブラインド秘密識別子に対するグループ署名である第２のブラインド署名の知識の証明との検証を前記署名提示装置と通信して行う知識証明検証装置を含むことを特徴とする。
【００５０】
上記の署名受信装置は、
前記ブラインドコミットメント証明装置は、
証明コミットメント装置と、第１の挑戦値獲得装置と、証明レスポンス装置よりなり、前記証明コミットメント装置は、乱数のコミットメントである証明コミットメントを生成するものであり、前記第１の挑戦値獲得装置は証明コミットメントを前記署名装置に送付し、前記署名装置から挑戦値を受信するものであり、前記証明レスポンス装置は、前記挑戦値と、前記証明コミットメントの生成に使った前記第２の乱数と前記ブラインド秘密識別子と前記ブラインド因子とから証明のレスポンスを生成するものであるものとしてもよい。
【００５１】
上記の署名装置は、
前記ブラインドコミットメント検証装置は、第１の挑戦値生成装置と、証明検証装置よりなり、前記第１の挑戦値生成装置は、証明のコミットメントと呼ばれるデータを受信するのを待ち、受信したならば前記乱数を用いてランダムな数である挑戦値を生成し、前記署名受信装置に送付し、前記署名検証装置は、前記署名受信装置より証明のレスポンスと呼ばれるデータを受信するのを待ち、これを受信したら、前記証明のコミットメント、前記挑戦値、前記証明のレスポンスが、ある検証式を満たすかどうかで、「正当」あるいは「不当」を出力するものであるものとしてもよい。
【００５２】
上記の署名提示装置は、
第２の挑戦値獲得装置を備え、証明のコミットメントの他に公開鍵とブラインド公開識別子が入力され、前記証明のコミットメントと前記公開鍵と前記ブラインド公開識別子を含むデータのハッシュ値を挑戦値として出力するとしてもよい。
【００５３】
上記の署名検証装置は、
第２の挑戦値生成装置を備え、前記証明のコミットメントと前記公開鍵と前記ブラインド公開識別子を含むデータのハッシュ値を挑戦値として出力するとしてもよい。
【００５４】
本発明の他の形態による制限付ブラインド署名システムは、署名受信装置と、該署名受信装置と通信する署名装置と、前記署名受信装置出力を入力する署名提示装置と、該署名提示装置と通信する署名検証装置とからなる制限付ブラインド署名システムであって、
前記署名装置は、秘密のデータである前記署名装置の秘密鍵と、該秘密鍵に対応する公開鍵と、第１の乱数とが入力され、前記秘密鍵と前記公開鍵と前記第1の乱数から第１のブラインド署名を生成して、該第1のブラインド署名を前記署名受信装置へ出力し、
前記署名受信装置は、前記署名装置の公開鍵と、メッセージと、第２の乱数と、前記第１のブラインド署名とが入力され、これらの各入力から前記メッセージがメンバー証明書の一部となるグループ署名である第２のブラインド署名を出力し、
前記署名提示装置には、前記公開鍵と、前記メッセージと、前記署名受信装置の出力である前記第２のブラインド署名と、第３の乱数と、が入力され、これらの入力状態を示す信号を前記署名検証装置へ出力し、
前記署名検証装置は、前記公開鍵と、第４の乱数と、が入力され、これらの各入力が、前記メッセージ、前記第２のブラインド署名が前記署名提示装置に入力されていることを示す場合には「正当」を、その他の場合には「不当」を出力することを特徴とする。
【００５５】
本発明の他の形態による署名受信装置は、上記の他の形態による制限付ブラインド署名システムを構成する署名受信装置であって、
前記メッセージのコミットメントであるブラインドコミットメントを前記署名装置に送信することを特徴とする。
【００５６】
本発明の他の形態による署名装置は、上記の他の形態による制限付ブラインド署名システムを構成する署名装置であって、
前記メッセージのコミットメントであるブラインドコミットメントを入力し、前記ブラインドコミットメントがコミットしたデータであるメッセージに対する署名であり、かつ、前記秘密鍵により生成された、メンバ証明書に前記メッセージを含むグループ署名である第１のブラインド署名を生成して前記署名受信装置に送ることを特徴とする。【００５７】
上記の他の形態による署名受信装置は、
前記公開鍵と前記メッセージと前記乱数が入力され、前記メッセージのコミットメントであるブラインドコミットメントを生成し、前記署名装置に送付するブラインドコミットメント生成装置と、
前記メッセージと前記公開鍵と前記乱数とが入力され、署名装置と通信することで,  前記ブラインドコミットメントが前記メッセージのコミットメントであることの知識の証明を署名装置に対して行う証明コミットメント装置と、
前記署名装置から前記ブラインドコミットメントによりコミットメントされた第１のブラインド署名を受け取って検証し、第２のブラインド署名を出力するブラインド署名受信装置と、
を含むこととしてもよい。【００５８】
上記の他の形態による署名装置は、
公開鍵と、乱数と、ともに、前記署名受信装置から送られたブラインドコミットメントとが入力され、前記ブラインドコミットメントが前記メッセージのコミットメントであることの知識の証明を検証し、証明結果が正当と認めるものであれば「正当」を、その他の場合は「不当」を出力する証明検証装置と、
前記秘密鍵と公開鍵と前記ブラインドコミットメントと乱数とが入力され、前記証明検証装置が「正当」を出力すると、前記ブラインドコミットメントがコミットメントしたメッセージをメンバ証明書として含むグループ署名を生成し,  署名受信装置に送信するグループ署名生成装置と、
を含むこととしてもよい。【００５９】
本発明の他の形態による署名提示装置は上記の他の形態による制限付ブラインド署名システムを構成する署名提示装置であって、
前記メッセージを前記署名検証装置に送付し、メッセージがメンバ証明書に含まれるグループ署名について、メンバ証明の知識を保持す知識証明装置を、
含むことを特徴とする。【００６０】
本発明の他の形態による署名検証装置は上記の他の形態による制限付ブラインド署名システムを構成する署名検証装置であって、
メッセージを前記署名提示装置より受信し、前記署名提示装置がメッセージをメンバ証明書に含むグループ署名のメンバ証明の知識を保持していることの検証を行う知識検証装置を、
含むことを特徴とする。
【発明の効果】
【００６３】
本発明によれば、署名受信装置の受け取る制限付ブラインド署名は、その安全性がランダムオラクルモデルに依存せずに証明できるため、不正な受信装置が署名装置の助けを借りることなく署名を入手する可能性が非常に低い。このようなことができる不正な受信装置が仮に存在するならば、この受信装置を用いて強RSA問題あるいは、離散対数問題等を解くことができる。これらの問題は現在の多くの公開鍵暗号方式の安全性が依拠している問題であり、上記不正な受信装置の存在は、現在のほとんどの公開鍵暗号方式を使えなくするほどの影響があり、このようなことが起ることは稀である。
【図面の簡単な説明】
【００６４】
【図１】従来技術のグループ署名システムにおける署名装置の構成を示すブロック図である。
【図２】本発明の第１の実施形態の署名受信装置の構成例を示すブロック図である。
【図３】本発明の第２の実施形態の署名装置の構成例を示すブロック図である。
【図４】本発明の第３の実施形態の署名提示装置の構成例を示すブロック図である。
【図５】本発明の第４の実施形態の署名検証装置の構成例を示すブロック図である。
【図６】本発明の第５の実施形態の挑戦値獲得装置の構成例を示すブロック図である。
【図７】本発明の第７の実施形態の署名受信装置、署名装置、署名提示装置、署名検証装置からなるシステムの構成例を示すブロック図である。
【図８】本発明の第８の実施形態の署名受信装置の構成例を示すブロック図である。
【図９】本発明の第９の実施形態の署名装置の構成例を示すブロック図である。
【図１０】本発明の第１０の実施形態の署名提示装置の構成例を示すブロック図である。
【図１１】本発明の第１１の実施形態の署名検証装置の構成例を示すブロック図である。
【図１２】本発明の第１２の実施形態の署名受信装置の構成例を示すブロック図である。
【図１３】本発明の第１３の実施形態の署名装置の構成例を示すブロック図である。
【図１４】本発明の第１４の実施形態の署名受信装置の構成例を示すブロック図である。
【図１５】本発明の第１５の実施形態の署名装置の構成例を示すブロック図である。
【符号の説明】
【００６５】
１００    署名受信装置
１０１    公開鍵
１０２    秘密識別子
１０３    公開識別子
１０４    乱数
１０５    ブラインド識別子生成装置
１０６    ブラインド因子
１０７    ブラインド秘密識別子
１０８    ブラインドコミットメント装置
１０９    ブラインドコミットメント
１１０    証明コミットメント
１１１    証明のコミットメント
１１２    挑戦値
１１３    挑戦値獲得装置
１１４    証明レスポンス装置
１１５    証明のレスポンス
１１６    ブラインド署名
１１７    ブラインド公開識別子
１１８    公開識別子送信装置
２００    署名装置
２０１    秘密鍵
２０２    乱数
２０３    挑戦値生成装置
２０５    証明検証装置
２０６    検証結果
２０７    グループ署名生成装置
２０８    公開識別子受信装置
２０９    ブラインドコミットメント受信装置
３００    署名提示装置
３０１    乱数
３０２    証明コミットメント装置
３０３    証明のコミットメント
３０４    挑戦値獲得装置
３０５    挑戦値
３０６    証明レスポンス生成装置
３０７    証明のレスポンス
４００    署名検証装置
４０１    乱数
４０２    挑戦値生成装置
４０３    証明検証装置
４０４    検証結果
【発明を実施するための最良の形態】
【００６６】
本発明の一実施形態について図面を参照して詳細に説明する。【００６７】
最初に前提となることを説明する。【００６８】
L=(Lm,Ls,Lc,Le,Lq,Ln,Lp,LE)  は安全性の尺度となる変数の列で、例えば、(380,60,160,60,160,2048,1600,382)  の値を使えば、現在においてはおよそ安全と言える。これらの値は計算機の性能の向上にしたがって、より大きな値をとる必要がある。【００６９】
pとqは素数で、q|p-1  なる関係を満たすとする。Gqは乗法群(Z/pZ)*の位数qの部分群である。【００７０】
署名受信装置には秘密の識別子である秘密識別子と、公開の識別子である公開識別子の二つのデータが格納される。
mとnは整数であり、j=1,...,mに関するB[j]  は一様無作為に選ばれた  Gq  の要素であり、p,q,m,n,B[j]は上記識別子の形態を定める要素で、領域変数と呼び、Dom  と記す。【００７１】
具体的には、署名受信装置の秘密識別子は体Z/qZ  上のランダムに生成されたn×m  行列、
a[ij]∈Z/qZ  ;  i=1,...,n;  j=1,....,m
で、これをSidと記す。公開識別子は、
D[i]  =  Πj=1mB[j]a[ij]  mod  p・・・式(1)
なるi=i,...,n  に関するD[i]である。これをPidと記す。【００７２】
署名装置には秘密鍵と公開鍵の二つのデータが格納される。P,Q,P',Q'は、P=2P'+1、  Q=2Q'+1なる関係を満たすランダムに生成された4個の素数である。n=PQなる整数である。i=1,,,.n;j=1,...,m  に関してA,H,G[ij]は(Z/nZ)*  から一様無作為に選ばれた要素である。【００７３】
秘密鍵は、(P,Q)で、これをSkeyと記す。【００７４】
公開鍵は領域変数Domと、n,A,H,G[ij]:i=1,...,n;j=1,...,mで、これをPkey  と記す。【００７５】
次に、本発明による装置の実施形態を述べる。【００７６】
［実施形態１］
図２は本発明による署名受信装置１００の構成を示すブロック図である。【００７７】
署名受信装置１００は署名装置２００と送受信し、公開鍵１０１、秘密識別子１０２、公開識別子１０３および乱数１０４を入力し、ブラインド公開識別子１１７、ブラインド秘密識別子１０７、ブラインド署名１１６’を出力するもので、ブラインド識別子生成装置１０５、ブラインド因子１０６、ブラインド秘密識別子１０７、ブラインドコミットメント装置１０８、ブラインドコミットメント１０９、証明コミットメント装置１１０、証明のコミットメント１１１、挑戦値１１２、挑戦値獲得装置１１３、証明レスポンス装置１１４、ブラインド署名受信装置１１５、ブラインド署名１１６、公開識別子送信装置１１８、証明のレスポンス１２０から構成されている。【００７８】
なお、署名受信装置１００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、ブラインド因子１０６、ブラインド秘密識別子１０７、ブラインドコミットメント１０９、証明のコミットメント１１１、挑戦値１１２、証明のレスポンス１１５、ブラインド署名１１６は記憶装置内に設定される。また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の構成要件のうち、証明のコミットメント１１１、挑戦値１１２、挑戦値獲得装置１１３、証明レスポンス装置１１４、証明のレスポンス１２０は証明部１１９を構成する。【００７９】
署名受信装置１００には、
署名装置の公開鍵１０１：Pkey=(Dom,n,  A,H,G[ij]:i=1,...,n;j=1,...,m)、ここで、  Dom=(p,q,m,n,B[j]:j=1,...,m)と、
署名受信装置の秘密識別子１０２：Sid=(a[ij]∈Z/qZ  :  i=1,...,n;  j=1,....,m)と、
署名受信装置の公開識別子１０３：  Pid=(D[i]:i=1,...,n)と、
乱数１０４と、が入力される.
署名受信装置１００を構成するブラインド識別子生成装置１０５は、入力された乱数１０４から、ランダムに整数s∈Z/qZ  を生成し、これをブラインド因子１０６とし、ブラインド秘密識別子１０７、
b[ij]  =  s  a[ij]  mod  q  i=1,...,n;j=1,...,m・・・式（２）
を計算する。【００８０】
署名受信装置１００を構成するブラインドコミットメント装置１０８は、入力された乱数１０４からランダムに整数r'∈{0,1}Ln/2  を生成し、ブラインド秘密識別子のコミットメントであるブラインドコミットメント１０９、
H'  =  Hr'  Πi=1nΠj=1m  G[ij]a'[ij]  mod  n・・・式(３)
を計算し、署名装置２００に送付する。【００８１】
署名受信装置１００を構成する公開識別子送信装置１１８は、署名装置２００に署名受信装置１００の公開識別子１０３を送付し、署名装置２００と通信することにより、式(1),  式(2)、式（３）および、a[ij]∈{0,1}lLq+Lc+Lc  :i=1,...,n;j=1,...,m
を満たすs,r',  a[ij]:i=1,...,n;j=1,...,mの知識を、証明部１１９において以下のように証明する。【００８２】
[証明手続き始まり]
署名受信装置１００は、入力された乱数１０４からランダムな、
t[i]  ∈Z/qZ:  i=1,...,n
t'[i]  ∈Z/qZ:  i=1,...,n
s'  ∈Z/qZ
b'[ij]∈{0,1}Lq+Lc+Ls:  i=1,...,n;j=1,....,m
u∈{0,1}Ln/2+Lc+Ls
を生成する。【００８３】
署名受信装置１００は、証明コミットメント装置１１０を用いて、
F[i]  =  D[i]sHt[i]  mod  p  i=1,...,n
F'[i]  =  D[i]s'Ht'[i]  mod  p  i=1,...,n
F''[i]=Ht'[i]  Πj=1mB[j]b'[ij]  mod  p  i=1,...,n
H''  =Hu  Πi=1nΠj=1m  G[ij]b'[ij]  mod  n
を計算し、
F[i]:i=1,...,n,F'[i]:i=1,...,n,F''[i]:i=1,...,n,H''  を証明のコミットメント１１１として署名装置２００に送信する。【００８４】
署名受信装置１００は、挑戦値獲得装置１１３に対して、署名装置２００より証明の挑戦値１１２  c∈{0,1}Lc  が送られるのを待つ。【００８５】
これを受信したならば、署名受信装置１００を構成する証明レスポンス装置１１４は、
s''  =  sc  +  s'  mod  q
t''[i]  =  t[i]c  +  t'[i]  mod  q  i=1,...,n
b''[ij]=  b[ij]  c  +  b'[ij]  i=1,...,n;j=1,....,m
u''  =  r'c  +u  i=1,...,n
を計算して、
s''  ,t''[i]:i=1,...,n,b''[ij]:i=1,...,n;j=1,....,m,u'  を証明のレスポンス１１５として署名装置２００に送信する。【００８６】
[証明手続き終わり]
署名受信装置１００を構成するブラインド署名受信装置１１５は、ブラインド署名１１６ Cer=(Y,E,r'') が署名装置２００から送られてくるのを待つ。
【００８７】
受信したならば、これがブラインド秘密識別子の正しいグループ署名であることを、以下の式、
A  =  YEH'Hr''  mod  n
E-2LE∈{0,1}Le+Lc+Ls
r''∈{0,1}Ln/2
が成り立つことより確認する。確認できたら、ブラインド公開識別子１１７、
Bpid  =  D'[i]  =  D[i]smod  p:i=1,...,n
を生成し、ブラインド公開識別子１１７、
Bpid  =  D'[i]  =  D[i]s  mod  p:i=1,...,n
ブラインド秘密識別子１０７、
Bsid  =  b[ij]:i=1,...,n;j=1,...,m
ブラインド署名１１６’、
Bcer  =  (Y,E,r=r'+r'')
を出力する。【００８８】
［実施形態２］
図３は本発明による署名装置２００の実施形態の構成を示すブロック図である。【００８９】
署名装置２００は、公開鍵１０１、秘密鍵２０１および乱数２０２を入力し、署名受信装置１００と送受信するもので、挑戦値１１２、ブラインド署名１１６、挑戦値生成装置２０３、証明検証装置２０５、検証結果２０６、グループ署名生成装置２０７、公開識別子受信装置２０８、ブラインドコミットメント受信装置２０９から構成される。【００９０】
なお、署名装置２００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、挑戦値１１２、ブラインド署名１１６、検証結果２０６は記憶装置内に設定される。また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の構成要件のうち、挑戦値１１２、挑戦値生成装置２０３、証明検証装置２０５、検証結果２０６は検証部２０４を構成する。【００９１】
署名装置２００には、
秘密鍵２０１；(P,Q)  と、
公開鍵１０１：  Dom,  n,A,H,G[ij]:i=1,...,n;j=1,...,m  ;ここで、Dom=(p,q,m,n,B[j]:j=1,...,m)と、
乱数２０２とが入力される。【００９２】
署名装置２００を構成する公開識別子受信装置２０８は、署名受信装置１００からの署名受信装置１００の公開識別子１０３：Pid  を受信するのを待つ。【００９３】
署名装置２００を構成するブラインドコミットメント受信装置２０９は、署名受信装置１００からのブラインドコミットメント１０９を署名受信装置１００より送付されるのを待つ。【００９４】
これを受信したならば、署名装置２００は署名受信装置１００と通信することにより、式(1)、式(2)および、
a[ij]  ∈{0,1}lLq+Lc+Lc  :i=1,...,n;j=1,...,m
を満たす、
s,r',  a[ij]:i=1,...,n;j=1,...,m
の知識を署名受信装置１００が持つことを検証部２０４により以下のように検証する。【００９５】
［検証手続き始まり］
さらに署名受信装置１００からの証明のコミットメント１１１
F[i]:i=1,...,n,F'[i]:i=1,...,n,F''[i]:i=1,...,n,H''
が送られてくるのを待ち、これを受信したならば、挑戦値生成装置２０３を用い、入力された乱数より、
証明の挑戦値１１２：  c∈{0,1}Lc
をランダムに生成して、署名受信装置１００に送信する。【００９６】
署名装置２００は、署名受信装置１００より証明のレスポンス１１５、
s''  ,t''[i]:i=1,...,n,b''[ij]:i=1,...,n;j=1,....,m,u'
が送られてくるのを待ち、受信したならば、証明検証装置２０５を用いて、
D[i]s''Ht''[i]  =  F[i]cF'[i]  mod  p  i=1,...,n
Ht''[i]Πj=1m  B[j]b''[ij]  =F[i]cF''[i]  mod  p  i=1,...,n
Hu''  Πi=1nΠj=1m  G[ij]b''[ij]  =H'cH''  mod  n
b''[ij]∈{0,1}Lq+Lc+Ls  i=1,...,n;j=1,....,m,u'
u''∈  {0,1}Ln/2+Lc+Ls
が全て成り立つことを確認する。確認できたら検証結果２０６として正当を出力する。【００９７】
[検証手続き204終わり]
検証結果が正当である場合、署名装置はグループ署名生成装置２０７を用いて、入力された乱数２０２から、
E=2LE+e  が素数となるようなe∈{0,1}Leとr''∈{0,1}Ln/2をランダムに生成する。【００９８】
署名装置２００は、Y=(A/(H'Hr''))1/E  mod  nを計算し,  ブラインド署名１１６：  Cer=(Y,E,r'')  を署名受信装置１００に送信し、動作を終了する。【００９９】
［実施形態３，４］
次に、署名提示装置と署名検証装置が通信することで、署名提示装置がブラインド署名を保有していることを、署名検証装置に証明する方法を記述する。【０１００】
［実施形態３］
図４は本発明による署名提示装置３００の実施形態の構成を示すブロック図である。【０１０１】
署名提示装置３００は、ブラインド公開識別子１１７、ブラインド秘密識別子１０７、ブラインド署名１１６’、公開鍵１０１、乱数３０１を入力し、署名検証装置４００と送受信を行なうもので、証明コミットメント装置３０２、証明のコミットメント３０３、挑戦値獲得装置３０４、挑戦値３０５、証明レスポンス生成装置３０６、証明のレスポンス３０７から構成される。【０１０２】
なお、署名提示装置３００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、証明のコミットメント３０３、挑戦値３０５、証明のレスポンス３０７は記憶装置内に設定される。また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の各構成要件により証明部３０８を構成する。【０１０３】
署名提示装置３００には、
公開鍵１０１：Dom,n,A,H,G[ij]:i=1,...,n;j=1,...,m、ここで、Dom=(p,q,m,n,B[j]:j=1,...,m)  と、
ブラインド公開識別子１１７：Bpid  =  D'[i]  =  D[i]s  mod  p:i=1,...,nと、
ブラインド秘密識別子１０７：Bsid  =  b[ij]:i=1,...,n;j=1,...,m  と、
ブラインド署名１１６：Bcer  =  (Y,E,r)  と、
乱数３０１とが入力される。【０１０４】
署名提示装置３００はブラインド公開識別子１１７：Bpid  を署名検証装置４００に送る。【０１０５】
署名提示装置３００は署名検証装置４００と通信することにより、
D'[i]  =  Πj=1mB[j]b[ij]  mod  p  i=1,...,n
A  =YEHr  Πi=1nΠ  j=1mG[ij]b[ij]  mod  n
E-  2LE∈{0,1}Le+Lc+Ls
b[ij]∈{0,1}Lq+Lc+Ls
を満たす
Y,E,r,  a[ij]:i=1,...,n;j=1,...,m
の知識を、証明部３０８により以下のように証明する。【０１０６】
[証明手続き始まり]
署名提示装置３００は入力された乱数３０１から、
t∈{0,1}Ln/2
Le+Lc+Ls
r'∈{0,1}Ln/2+LE+Lc+Ls+2
b'[ij]∈{0,1}Lq+Lc+Ls
をランダムに生成する.
署名提示装置３００は、証明コミットメント装置３０２を用いて、
U  =  Ht  Y  mod  n
A'  =  Ue'Hr'  Πi=1n  Πj=1mG[ij]b'[ij}  mod  n
D''[i]=  Πj=1mB[j]b'[ij]  mod  n  i=1,...,n
を生成して,  U,A'  D''[i]:i=1,...,n  を証明のコミットメント３０３として出力する.
署名提示装置３００を構成する挑戦値獲得装置３０４は、証明のコミットメント３０３を署名検証装置４００に送り、署名検証装置４００より証明の挑戦値３０５：c∈{0,1}Lc  が送られるのを待つ。受信したならば、証明レスポンス生成装置３０６を用いて、
e''  =  e  c  +e'
r''  =  (r-tE)c  +r'
b''[ij]  =  b[ij]  c  +  b'[ij]  i=1,...,n;j=1,...,m
を計算して,  e''  ,r'',b''[ij]:i=1,...,n;j=1,...,m  を証明のレスポンス３０７として署名検証装置４００に送付する。【０１０７】
[証明手続き終わり]
その後、動作を終了する。【０１０８】
［実施形態４］
図５は本発明による署名検証装置４００の実施形態の構成を示すブロック図である。【０１０９】
署名検証装置４００は、乱数４０１、公開鍵１０１を入力して検証結果４０４を出力し、署名提示装置３００と送受信を行なうもので、ブラインド公開識別子１１７、証明のコミットメント３０３、挑戦値３０５、挑戦値生成装置４０２、証明検証装置４０３から構成される。【０１１０】
なお、署名検証装置４００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、ブラインド公開識別子１１７、証明のコミットメント３０３、挑戦値３０５は記憶装置内に設定される。また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、証明のコミットメント３０３、挑戦値３０５、挑戦値生成装置４０２、証明検証装置４０３により検証部４０６を構成する。【０１１１】
署名検証装置４００には、
公開鍵１０１：Dom,n,A,H,G[ij]:i=1,...,n;j=1,...,m  、ここで、Dom=(p,q,m,n,B[j]:j=1,...,m)  と、
乱数４０１とが入力される。【０１１２】
署名検証装置４００は、署名提示装置３００よりブラインド公開識別子１１７：Bpid  が送られてくるのを待つ。【０１１３】
署名検証装置４００は署名提示装置３００と通信することにより、
D'[i]  =  Πj=1mB[j]b[ij]  mod  p  i=1,...,n
A  =YEHr  Πi=1n  Πj=1mG[ij]b[ij]  mod  n
E-  2LE∈{0,1}Le+Lc+Ls
b[ij]∈{0,1}Lq+Lc+Ls
を満たす
Y,E,r,  a[ij]:i=1,...,n;j=1,...,m
の知識を署名提示装置３００が保有していることを、検証部４０６により以下のように検証する。【０１１４】
［検証手続き始まり］
署名検証装置４００を構成する挑戦値獲得装置４０２は、署名提示装置３００より証明のコミットメント３０３  U,A'  D''[i]:i=1,...,n  が送られてくるのを待つ。これを受信したならば、入力された乱数４０１より、
証明の挑戦値３０５：c∈{0,1}Lc
をランダムに生成して、署名提示装置３００に送信する。【０１１５】
署名提示装置３００より、証明のレスポンス３０６
e''  ,r'',b''[ij]:i=1,...,n;j=1,...,m  が送られてくるのを待つ。受信したならば、署名検証装置４００を構成する証明検証装置４０３は、
c'  =  c  2LE+e''
とし、
Uc'  Hr''  Πi=1n  Πj=1mG[ij]b''[ij]  =AcA'  mod  n
Πj=1mB[j]b''[ij]  =D[i]cD''[i]  mod  p
e''∈{0,1}Le+Lc+Ls
b''[ij]∈{0,1}Lq+Lc+Lsi=1,...,n;j=1,...,m
が全て成り立つことを確認する。確認できたら証明を検証結果４０４として「正当」を出力する。【０１１６】
［検証手続き終わり］
証明検証が正当であれば署名提示を正当と見なす。【０１１７】
［実施形態５］
図６は、挑戦値獲得関数がハッシュ関数である場合の署名提示装置５００の実施形態の構成を示すブロック図である。【０１１８】
挑戦値獲得装置５０１は、
(p,q,m,n,B[j]:j=1,...,m),
n,A,H,G[ij]:i=1,...,n;j=1,...,m
Bpid  =  D'[i]  =  D[i]s  mod  p:i=1,...,n
U,A'  D''[i]:i=1,...,n
のハッシュ値を挑戦値５０２：cとして出力する。【０１１９】
［実施形態６］
挑戦値生成関数がハッシュ関数である場合の署名検証装置の実施形態では、実施形態４における署名検証装置において挑戦値生成関数が、実施形態５の挑戦値生成関数と同じものを使用する。【０１２０】
［実施形態７］
図７は実施形態１〜４の署名受信装置１００、  署名装置２００  署名提示装置３００、署名検証装置４００を用いたシステムの構成を示すブロック図である。【０１２１】
本実施形態は、署名受信装置１００、署名装置２００、署名提示装置３００、署名検証装置４００とからなるシステムで、署名受信装置１００と署名装置２００は互いに通信する手段６０１を備え、署名提示装置３００は署名受信装置１００の出力を入力し、署名提示装置３００と署名検証装置４００は互いに通信する手段６０２を備えている。【０１２２】
署名受信装置１００には、署名装置の公開鍵と、署名受信装置１００の秘密のデータである秘密識別子１０２と、署名受信装置１００の公開されているデータであり、秘密識別子１０２に依存したデータである公開識別子１０３と、乱数１０４とが入力されている。【０１２３】
署名装置２００には、署名装置の秘密のデータである秘密鍵２０１と、署名装置の公開されているデータである公開鍵１０１と、乱数２０２とが入力され、署名受信装置１００と署名装置２００が互いに通信することで、署名受信装置１００が、ブラインド秘密識別子１０７と、ブラインド公開識別子１１７と、ブラインド署名１１６とを出力する。【０１２４】
署名提示装置３００には、公開鍵１０１と、署名受信装置１００の出力である、ブラインド秘密識別子１０７と、ブラインド公開識別子１１７と、ブラインド署名１１６と、乱数３０１と、が入力されている。【０１２５】
署名検証装置４００には、公開鍵１０１と、乱数４０１とが入力され、署名提示装置３００と署名検証装置４００が互いに通信し、署名提示装置３００にブラインド公開識別子１１７、ブラインド秘密識別子１０７、ブラインド署名１１６のデータが入力されていれば、署名検証装置４００は「正当」を検証結果４０４として出力し、その他の場合は「不当」を検証結果４０４として出力する。【０１２６】
以下に、本発明の第８ないし第１７の実施形態に説明する。【０１２７】
まず、第８ないし第１１の実施形態に共通することについて説明する。【０１２８】
L=(Ls,Lc,Le,Lq,Ln,LE)  は安全性の尺度となる変数の列で、例えば(60,160,60,160,2048,382)  の値を使えば2005年現在においてはおよそ安全と言える.  これらの値は計算機の性能の向上にしたがって、より大きな値をとる必要がある。【０１２９】
署名受信装置にはメッセージm  ∈  {0,1}Lqが格納される。【０１３０】
署名装置には秘密鍵と公開鍵の二つのデータが格納される。P,Q,P',Q'  は,  P=2P'+1,  Q=2Q'+1  なる関係を満たすランダムに生成された4個の素数であり、N=PQ  なる整数である。A,H,G,F  は  QR(N)  から一様無作為に選ばれた要素である。ここで  QR(N)  とは、  (Z/NZ)*  の要素の部分集合で、ある  (Z/NZ)*  の要素  a  が存在して、  a2  と表せるもののことである。【０１３１】
秘密鍵は,  (P,Q)で,  これを  Skey  と記す。
公開鍵は  N,A,H,G,F  で,  これをPkey  と記す。【０１３２】
以下に、個々の実施の形態を述べる。【０１３３】
［実施形態８］
図８は本発明による署名受信装置１１００の構成を示すブロック図である。【０１３４】
署名受信装置１００は署名装置１２００と送受信し、公開鍵１１０１、メッセージ１１０３および乱数１１０４を入力し、ブラインドコミットメント１１０９、証明のレスポンス１１１５、ブラインド署名１１１６’を出力するもので、ブラインドコミットメント装置１１０８、ブラインドコミットメント１１０９、証明コミットメント装置１１１０、証明のコミットメント１１１１、挑戦値１１２、挑戦値獲得装置１１１３、証明レスポンス装置１１１４、証明のレスポンス１１１５、ブラインド署名受信装置１１１７、ブラインド署名１１１６から構成されている。【０１３５】
なお、署名受信装置１１００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、ブラインドコミットメント１１０９、挑戦値１１２、証明のレスポンス１１１５、ブラインド署名１１１６は記憶装置内に設定される。また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の構成要件のうち、証明コミットメント装置１１１０、証明のコミットメント１１１１、挑戦値１１２、挑戦値獲得装置１１１３、証明レスポンス装置１１１４、証明のレスポンス１１１５、ブラインド署名受信装置１１１７、ブラインド署名１１１６は証明部１１１９を構成する。【０１３６】
署名受信装置１１００には、
署名装置の公開鍵１１０１  Pkey=(A,H,G,F)  と、
メッセージ１１０３  m  と、
乱数１１０４と、
が入力される。【０１３７】
署名受信装置１１００を構成するブラインドコミットメント装置１１０８は、入力された乱数からランダムに整数  r',s  ∈  {0,1}Ln/2  を生成し、ブラインド秘密識別子のコミットメントであるブラインドコミットメント１１０９
式(1)  H'  =  Hr'  Gm  Fs  mod  N
を計算し、署名装置１２００に送付する。【０１３８】
署名受信装置１１００は、署名装置１２００と通信することにより,  式(1)  および
m,s  ∈{0,1}Lq+Lc+Ls
r'  ∈{0,1}Ln/2+Lc+Ls
を満たす
m,s,r'
の知識を、以下のように証明する。【０１３９】
［証明手続き１１１９始まり］
署名受信装置１１００は、入力された乱数１１０４からランダムな、
m',s'  ∈  {0,1}Lq+Lc+Ls:  i=1,...,n;j=1,....,m
u  ∈  {0,1}Ln/2+Lc+Ls
を生成する。【０１４０】
署名受信装置１１００を構成する証明コミットメント装置１１１０は、
H''  =HuGm'Fs'  mod  N
を計算し、
H''  を証明のコミットメント１１１１として署名装置１２００に送信する。【０１４１】
署名受信装置１１００を構成する挑戦値獲得装置１１１３は、署名装置１２００より証明の挑戦値１１１２  c  ∈  {0,1}Lc  が送られるのを待つ。【０１４２】
これを受信したならば、署名受信装置１１００を構成する証明レスポンス装置１１１４は、
s''  =  sc  +  s'
m''=  m  c  +  m'
u''  =  r'c  +u
を計算して、
s''  ,m'',u''  を証明のレスポンス１１１５として署名装置１２００に送信する。
［証明手続き１１１９終わり］
署名受信装置１１００を構成するブラインド署名受信装置１１１５は、署名１１１６  Cer=(Y,E,r'')  を署名装置１２００から送られてくるのを待つ。【０１４３】
受信したならば,  これが正しいグループ署名であることを、以下の式、
A  =  YEH'Hr''  mod  N
E-2LE  ∈  {0,1}Le+Lc+Ls
r''∈  {0,1}Ln/2+Lc+Ls
が成り立つことより確認する。【０１４４】
確認できたら、ブラインド署名１１１６’
Bcer  =  (Y,E,r=r'+r'',s)
を出力する。【０１４５】
［実施形態９］
図９は本発明による署名装置１２００の実施形態の構成を示すブロック図である。【０１４６】
署名装置１２００は、公開鍵１１０１、秘密鍵１２０１および乱数１２０２を入力し、署名受信装置１１００と送受信するもので、挑戦値１１１２、ブラインド署名１１１６、挑戦値生成装置１２０３、証明検証装置１２０５、検証結果１２０６、グループ署名生成装置１２０７、ブラインドコミットメント受信装置１２０９から構成される。【０１４７】
なお、署名装置１２００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、挑戦値１１１２、ブラインド署名１１１６、検証結果１２０６は記憶装置内に設定される。また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の構成要件のうち、挑戦値１１１２、挑戦値生成装置１２０３、証明検証装置１２０５、検証結果１２０６は検証部１２０４を構成する。【０１４８】
署名装置１２００には、
秘密鍵２０１(P,Q)  と、
公開鍵１１０１  N,A,H,G,Fと、
乱数１２０２と、
が入力される。【０１４９】
署名装置１２００を構成するブラインドコミットメント受信装置１２０９は、署名受信装置１１００からブラインドコミットメントH'１１０９を受信するのを待つ。【０１５０】
さらに署名装置１２００は、署名受信装置１１００より証明のコミットメント１１１１  H''  が送付されるのを待つ。【０１５１】
これを受信したならば,  署名装置１２００は署名受信装置１１００と通信することにより、式(1)  および
s,m  ∈{0,1}Lq+Lc+Ls  :i=1,...,N;j=1,...,m
r'  ∈{0,1}Lq+Lc+Ls  :i=1,...,n;j=1,...,m
を満たす
m,s,r'
の知識を署名受信装置１１００が持つことを以下のように検証する。【０１５２】
［検証部１２０４による検証手続き始まり］
署名装置１２００を構成する挑戦値生成装置１２０３は、署名受信装置１１００より証明のコミットメント１１１１H''  を受信すると、入力された乱数より
証明の挑戦値１１１２  c  ∈  {0,1}Lc
をランダムに生成して、署名受信装置１１００に送信する。【０１５３】
署名装置１２００は、署名受信装置１１００より証明のレスポンス１１１５
s''  ,m'',u''
が送られてくるのを待ち、
受信したならば、証明検証装置１２０５を用いて、
Hu''  Gm''  Fs''  =H'cH''  mod  N
m'',s''  ∈  {0,1}Lq+Lc+Ls
u''  ∈  {0,1}Ln/2+Lc+Ls
が全て成り立つことを確認する。確認できたら検証結果１２０６として正当を出力する。
［検証手続き１２０４終わり］
検証結果が正当である場合、署名装置１２００を構成するグループ署名生成装置１２０７は、入力された乱数１２０２から、
E=2LE+e  が素数となるような  e  ∈  {0,1}Leと
r''  ∈  {0,1}Ln/2を
ランダムに生成する.
署名装置１２００は、
Y=(A/(H'Hr''))1/E  mod  N
を計算し、ブラインド署名１１１６  Cer=(Y,E,r'')  を署名受信装置１１００に送信し、動作を終了する。【０１５４】
次に、署名提示装置と署名検証装置が通信することで、署名提示装置がブラインド署名を保有していることを、署名検証装置に証明する方法について説明する。【０１５５】
［実施の形態１０］
図１０は本発明による署名提示装置１３００の実施形態の構成を示すブロック図である。【０１５６】
署名提示装置１３００は、公開鍵１１０１、ブラインド署名１１１６、メッセージ１１１７、乱数１３０１を入力し、署名検証装置１４００と送受信を行なうもので、証明コミットメント装置１３０２、証明のコミットメント１３０３、挑戦値獲得装置１３０４、挑戦値１３０５、証明レスポンス生成装置１３０６、証明のレスポンス１３０７から構成される。【０１５７】
なお、署名提示装置１３００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、証明のコミットメント１３０３、挑戦値１３０５、証明のレスポンス１３０７は記憶装置内に設定される。また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、上記の各構成要件により証明部１３０８を構成する。【０１５８】
署名提示装置１３００には、
公開鍵１１０１  N,A,H,G,F  と、
メッセージ１１１７  mと、
ブラインド署名１１１６
Bcer  =  (Y,E,r,s)  と、
乱数１３０１と、
が入力される。【０１５９】
署名提示装置１３００はメッセージ１１１７  m  を署名検証装置１４００に送る。【０１６０】
署名提示装置１３００は署名検証装置1400と通信することにより、
A  =YEHr  GmFs  mod  N
E-  2LE  ∈  {0,1}Le+Lc+Ls
m,s  ∈  {0,1}Lq+Lc+Ls
を満たす
Y,E,r,s
の知識を以下のように証明する。但し、  m  は公開されている。【０１６１】
［証明部１３０８による証明手続き始まり］
署名提示装置１３００は入力された乱数１３０１から、
t  ∈  {0,1}Ln/2
e'  ∈  {0,1}Le+Lc+Ls
r'  ∈  {0,1}Ln/2+LE+Lc+Ls+2
b'[ij]  ∈  {0,1}Lq+Lc+Ls
をランダムに生成する。【０１６２】
署名提示装置１３００を構成する証明コミットメント装置１３０２は、
U  =  Ht  Y  mod  N
A'  =  Ue'Hr'  Fb'  mod  N
を生成して、  U,A'  を証明のコミットメント１３０３として出力する。【０１６３】
署名提示装置１３００を構成する挑戦値獲得装置１３０４は、証明のコミットメント１３０３を署名検証装置に送り、署名検証装置１４００より証明の挑戦値１３０５  c  ∈  {0,1}Lc  が送られてくるのを待つ。【０１６４】
受信したならば,  証明レスポンス生成装置１３０６を用いて、
e''  =  e  c  +e'
r''  =  (r-tE)c  +r'
b''  =  s  c  +  b'
を計算して、  e''  ,r'',b''を証明のレスポンス１３０７として署名検証装置１４００に送付する。
［証明手続き終わり］
動作を終了する。【０１６５】
［実施の形態１１］
図１１は本発明による署名検証装置１４００の実施形態の構成を示すブロック図である。【０１６６】
署名検証装置１４００は、乱数１４０１、公開鍵１１０１を入力して検証結果１４０４を出力し、署名提示装置１３００と送受信を行なうもので、メッセージ１１１７、証明のコミットメント１３０３、挑戦値１３０５、挑戦値生成装置１４０２、証明検証装置１４０３から構成される。【０１６７】
なお、署名検証装置１４００は、入力装置、出力装置、記憶装置および制御装置からなる一般的なコンピュータシステムにより構成されるもので、メッセージ１１１７、証明のコミットメント１３０３、挑戦値１３０５は記憶装置内に設定される。また、これら以外の装置もコンピュータシステム内に仮想的に構成される。また、証明のコミットメント１３０３、挑戦値１３０５、挑戦値生成装置１４０２、証明検証装置１４０３により検証部１４０６を構成する。【０１６８】
署名検証装置１４００には、
公開鍵１１０１  N,A,H,G,F  と、
乱数１４０１と、
が入力される。【０１６９】
署名検証装置１４００は、  署名提示装置１３００よりメッセージ  １１１７  m  が送られてくるのを待つ。
署名検証装置１４００は署名提示装置１３００と通信することにより、
A  =YEHr  Gm  Fsmod  N
E-  2LE  ∈  {0,1}Le+Lc+Ls
m,s  ∈  {0,1}Lq+Lc+Ls
r  ∈  {0,1}Ln/2+Lc+Ls
を満たす
Y,E,r,s
の知識を署名提示装置が保有していることを、以下のように検証する。【０１７０】
［検証部１４０６による検証手続き始まり］
署名検証装置１４００は、署名提示装置１３００より証明のコミットメント１３０３  U,A'  が送られてくるのを待つ.
これを受信したならば、挑戦値獲得装置１４０２は、入力された乱数１４０１より、
証明の挑戦値１３０５  c  ∈  {0,1}Lc
をランダムに生成して、署名提示装置１３００に送信し、署名提示装置１３００より証明のレスポンス１３０６e''  ,r'',b''  が送られてくるのを待つ。【０１７１】
証明のレスポンス１３０６e''  ,r'',b''  を受信したならば、署名検証装置１４００を構成する証明検証装置１４０３は、
c'  =  c  2LE+e''
とし、
Uc'  Hr''  Fb''[ij]  =AcA'  G-mc  mod  N
e''  ∈  {0,1}Le+Lc+Ls
b''  ∈  {0,1}Lq+Lc+Ls
が全て成り立つことを確認する。確認できたら証明を検証結果１４０４  として「正当」を出力する。
［検証手続き1406終わり］
証明検証が正当であれば署名提示を正当と見なす。【０１７２】
次に、本発明の実施形態１２、１３について説明する。まず、これらの実施形態に共通する事柄を説明する。【０１７３】
L=(Lm,Ls,Lc,Le,Lq,Ln,Lp,LE)  は安全性の尺度となる変数の列で,  例えば(380,60,160,60,160,2048,1600,382)  の値を使えば2005  年現在においてはおよそ安全と言える。これらの値は計算機の性能の向上にしたがって、より大きな値をとる必要がある。【０１７４】
p  と  q  は素数で,  q|p-1  なる関係を満たすとする.  Gq  は乗法群(Z/pZ)*  の位数q  の部分群である。【０１７５】
署名受信装置には秘密の識別子である秘密識別子と、公開の識別子である公開識別子の二つのデータが格納される。
m  と  n  は整数であり,
j=1,...,m  に関する  B[j]  は  一様無作為に選ばれた  Gq  の要素であり、
p,q,m,n,B[j]  は上記識別子の形態を定める要素で、領域変数と呼び、Dom  と記す。【０１７６】
具体的には、署名受信装置の秘密識別子は体  Z/qZ  上のランダムに生成された  n  ×  m  行列、
a[ij]  ∈  Z/qZ  ;  i=1,...,n;  j=1,....,m
で、これを  Sid  と記す。公開識別子は、
式(1)  D[i]  =  Πj=1mB[j]a[ij]  mod  p
なるi=i,...,n  に関する  D[i]  である。これを  Pid  と記す。【０１７７】
署名装置には秘密鍵と公開鍵の二つのデータが格納される。P,Q,P',Q'  は,  P=2P'+1,  Q=2Q'+1  なる関係を満たすランダムに生成された4個の素数で、N=PQ  なる整数である。i=1,,,.n;j=1,...,m  に関して  A,H,G[ij]  は  QR(N)  から一様無作為に選ばれた要素である。【０１７８】
秘密鍵は  (P,Q)で、これを  Skey  と記す。【０１７９】
公開鍵は領域変数Dom  と  N,A,H,G[ij]:i=1,...,n;j=1,...,m  で、これをPkey  と記す。【０１８０】
以下に、個々の実施形態について説明する。【０１８１】
［実施形態１２］
図１２は本発明による署名受信装置２１００の構成を示すブロック図である。【０１８２】
本実施形態は、実施形態１として図２に示した署名受信装置１００を、署名装置２２００からの暗号文２１２０を公開識別子送信装置１１８に入力する構成としたものである。【０１８３】
実施の形態1  において  Dom  に,  E[1],E[2]  ∈  QR(N)2  を追加し、E[2]=E[1]x  となる秘密鍵  x  に追加する。【０１８４】
署名受信装置は最初に,  署名装置より(E[1],E[2])を公開鍵とするElGamal  暗号方式による暗号文２１２０、  (C[11],C[12]),(C[ij1],C[ij2]):i=1,...,n;j=1,...,m  を受信する。【０１８５】
実施例形態１に示した署名受信装置１００ではブラインドコミットメント
H'  =  Hr'  Πi=1nΠj=1m  G[ij]a'[ij]  mod  N
を計算し、署名装置２００に送付したが、署名受信装置２１００は、これの代りに,
式(３)  H'[1]  =  C[11]r'  Πi=1nΠj=1m  G[ij1]a'[ij]  mod  N
H'[2]  =  C[12]r'  Πi=1nΠj=1m  G[ij2]a'[ij]  mod  N
を計算して証明装置２２００に送付する。【０１８６】
実施形態１で行なう証明においては  証明のコミットメントを生成するが、ここでは,  H''  の代りに、署名受信装置２１００が署名装置２２００に対して、
H''[1]  =C[11]u  Πi=1nΠj=1m  G[ij1]b'[ij]  mod  N
H''[2]  =C[12]u  Πi=1nΠj=1m  G[ij2]b'[ij]  mod  N
を計算し、送付する。【０１８７】
以上が実施形態１との違いである。【０１８８】
［実施形態１３］
図１３は本発明による署名装置２２００の構成を示すブロック図である。【０１８９】
本実施形態は、実施形態２として図３に示した署名装置２００を、公開鍵１０１および乱数２０２から暗号文２１２０を生成し、署名受信装置２１００へ送信する署名装置２２００としたものである。【０１９０】
以下に、実施形態２に示した署名装置２００との差異について主に説明する。【０１９１】
署名装置２２００は、最初に、
E=2LE+e  が素数となるような  e  ∈  {0,1}Le
を生成する。【０１９２】
署名装置２２００は,(E[1],E[2])を公開鍵１０１とするElGamal  暗号方式による、H1/E  の暗号文２１２０  (C[11],C[12])、とG[ij]1/E  の暗号文  (C[ij1],C[ij2]):i=1,...,n;j=1,...,m  を生成して、署名受信装置２１００に送付する。【０１９３】
実施形態２で署名受信装置１００より受け取るブラインドコミットメントは１０９H'  ∈  QR(N)であったが、ここでは(H'[1],H'[2])∈QR(N)2  である。【０１９４】
実施形態２で署名受信装置１００より受け取る証明のコミットメント１１１は  H''  ∈  QR(N)であったが、ここでは(H''[1],H''[2])∈QR(N)2  である。【０１９５】
署名受信装置２１００が署名装置２２００に対して、実施形態２で行なう検証において、
Hu''  Πi=1nΠj=1m  G[ij]b''[ij]  =H'cH''  mod  N
が成り立つことを確認したが、ここでは、これの代りに、
C[11]u''  Πi=1nΠj=1m  C[ij1]b''[ij]  =H'[1]cH''[1]  mod  N
C[12]u''  Πi=1nΠj=1m  C[ij2]b''[ij]  =H'[2]cH''[2]  mod  N
が成り立つことを確認する。【０１９６】
検証結果が正当である場合、署名装置２２００はグループ署名生成装置２０７を用いて、入力された乱数２０２から、
r''  ∈  {0,1}Ln/2をランダムに生成し、署名装置２００は、
Y=  (A  /Hr'')1/E  /  (H'[2]/H'[1]x)  mod  N
を計算し、ブラインド署名１１６  Cer=(Y,E,r'')  を署名受信装置２１００に送信し、動作を終了する。【０１９７】
次に、本発明の実施形態１４、１５について説明する。まず、これらの実施形態の前提となる事柄を説明する。【０１９８】
L=(Ls,Lc,Le,Lq,Ln,LE)  は安全性の尺度となる変数の列で、例えば(60,160,60,160,2048,382)  の値を使えば２００５年現在においてはおよそ安全と言える.  これらの値は計算機の性能の向上にしたがって,  より大きな値をとる必要がある。【０１９９】
署名受信装置にはメッセージm  ∈  {0,1}Lqが格納される。【０２００】
署名装置には秘密鍵と公開鍵の二つのデータが格納される。P,Q,P',Q'  は,  P=2P'+1,  Q=2Q'+1  なる関係を満たすランダムに生成された4個の素数であり、N=PQ  なる整数である。A,H,G,F  は  QR(N)  から一様無作為に選ばれた要素である。ここで  QR(N)  とは(Z/NZ)*  の要素の部分集合で、ある  (Z/NZ)*  の要素  a  が存在して、a2  と表せるもののことである。【０２０１】
秘密鍵は(P,Q)で、これを  Skey  と記す。【０２０２】
公開鍵は  N,A,H,G,F  で、これをPkey  と記す。【０２０３】
［実施形態１４］
図１４は本発明による署名受信装置３１００の構成を示すブロック図である。【０２０４】
本実施形態の署名受信装置３１００は、実施形態８として図８に示した署名受信装置１１００を、署名装置３２００からの暗号文３１２０をブラインドコミットメント装置１１０８に入力する構成としたものである。【０２０５】
本実施形態について、特に実施形態8  との差異を主として以下に説明する。【０２０６】
実施形態８におけるDom  に,  E[1],E[2]  ∈  QR(N)2  を追加し、E[2]=E[1]x  となる  x  秘密鍵に追加する。【０２０７】
署名受信装置３１００は、最初に、署名装置３２００より(E[1],E[2])を公開鍵とするElGamal  暗号方式による暗号文３１２０  (C[11],C[12]),(C[21],C[22]),(C[31],C[32])を受信する。【０２０８】
実施形態８の署名受信装置１１００ではブラインドコミットメント
H'  =  Hr'  Gm  Fs  mod  N
を計算し、署名装置１２００に送付したが、署名受信装置３１００ではこれの代りに、
式(３)  H'[1]  =  C[11]r'  C[21]m  C[31]s  mod  N
H'[2]  =  C[12]r'  C[22]m  C[32]s  mod  N
を計算して署名装置３２００に送付する。【０２０９】
実施形態８で行なう証明においては証明のコミットメントを生成するが、ここでは、署名受信装置３１００が署名装置３２００に対して、H''  の代りに、
H''[1]  =C[11]uC[21]m'C[31]s'  mod  N
H''[2]  =C[12]uC[22]m'C[33]s'  mod  N
を計算し、送付する。【０２１０】
以上が実施形態８との違いである。【０２１１】
［実施形態１５］
図１５は本発明による署名装置３２００の構成を示すブロック図である。【０２１２】
本実施形態は、実施形態９として図９に示した署名装置１２００を、公開鍵１１０１から暗号文３１２０を生成し、署名受信装置３１００へ送信する署名装置３２００としたものである。【０２１３】
以下に、実施形態９に示した署名装置１２００との差異について主に説明する。【０２１４】
署名装置３２００は最初に、
E=2LE+e  が素数となるような  e  ∈  {0,1}Le
を生成する。【０２１５】
署名装置３２００は、(E[1],E[2])を公開鍵とするElGamal  暗号方式による,  暗号文の集合３１２０  H1/E  の暗号文  (C[11],C[12])と、G1/E  の暗号文(C[21],C[22])  と、F1/E  の暗号文(C[31],C[32])  と、を生成して、署名受信装置３１００に送付する。【０２１６】
実施形態９で署名受信装置１１００より受け取るブラインドコミットメントは  H'  ∈  QR(N)であったが、ここでは(H'[1],H'[2])∈QR(N)2  である。【０２１７】
実施形態９で署名受信装置１１００より受け取る証明のコミットメントは  H''  ∈  QR(N)であったが、ここでは(H''[1],H''[2])∈QR(N)2  である。【０２１８】
実施形態１２で署名受信装置２１００が署名装置２２００に対して行なう検証において、
Hu''  Gm''  Fs''  =H'cH''  mod  N
が成り立つことを確認したが、ここでは、これの代りに
C[11]u''  C[21]m''  C[31]s''  =H'[1]cH''[1]  mod  N
C[12]u''  C[22]m''  C[32]s''  =H'[2]cH''[2]  mod  N
が成り立つことを確認する。【０２１９】
検証結果が正当である場合、  署名装置はグループ署名生成装置１２０７を用いて、入力された乱数１２０２から、
r''  ∈  {0,1}Ln/2をランダムに生成し、署名装置３２００は、
Y=  (A  /Hr'')1/E  /  (H'[2]/H'[1]x)  mod  N
を計算し、ブラインド署名１１１６  Cer=(Y,E,r'')  を署名受信装置３１００に送信し、動作を終了する。【０２２０】
［実施形態１６］
本実施形態は、挑戦値獲得関数がハッシュ関数である場合の署名提示装置の実施形態であり、実施形態１０における署名提示装置１３００において、挑戦値獲得関数１５００は、この関数に入力された値のハッシュ値を挑戦値１５００  c  として出力する。【０２２１】
［実施例１７］
本実施形態は、挑戦値生成関数がハッシュ関数である場合の署名検証装置の実施形態であり、実施形態１１における署名検証装置１４００において、挑戦値生成関数として、実施形態１６の挑戦値生成関数と同じものを使用する。
【図１】
0004973193.tif 000002
【図２】
0004973193.tif 000003
【図３】
0004973193.tif 000004
【図４】
0004973193.tif 000005
【図５】
0004973193.tif 000006
【図６】
0004973193.tif 000007
【図７】
0004973193.tif 000008
【図８】
0004973193.tif 000009
【図９】
0004973193.tif 000010
【図１０】
0004973193.tif 000011
【図１１】
0004973193.tif 000012
【図１２】
0004973193.tif 000013
【図１３】
0004973193.tif 000014
【図１４】
0004973193.tif 000015
【図１５】
0004973193.tif 000016