(57)【要約】【課題】利用者装置が検証装置に署名を渡さずに、利用者装置が署名を所有していることを検証可能にする。【解決手段】素数ｑと、バイリニアペアリングｅ：Ｇ1×Ｇ2→ＧTが存在する位数ｑの群Ｇ1，Ｇ2，ＧTとを公開し、利用者装置は、コミットメント鍵ckを使って情報ｍに対するコミットメントＣを演算し、署名要求メッセージＭとして署名生成装置に送信し、署名生成装置は、群Ｇ1，Ｇ2の生成元ｇ1、ｇ2とＺqに属する乱数ｘ、ｙ、ｒを使って署名要求メッセージＭとの演算により複数の要素の組をＭに対する署名σとして生成して利用者装置に送信し、利用者装置は署名σの要素に対し、ペアリング等式が成立するか検証し、コミットメントＣと署名σに対する非対話ゼロ知識証明をそれぞれ生成し、情報ｍと共にブラインド署名として検証装置に与え、検証装置は、非対話ゼロ知識証明を検証する。【選択図】図１
2010200065.tif 000002
【特許請求の範囲】
【請求項１】
利用者装置と、署名生成装置と、検証装置とを含み、素数ｑと、バイリニアペアリングｅ：Ｇ1×Ｇ2→ＧTが存在する位数ｑの群Ｇ1，Ｇ2，ＧTとを公開した署名検証システムであり、
上記利用者装置は、上記Ｇ1の元ｇ、ｈ1とＧ2の元ｈ2とを含むコミットメント鍵ckを使って情報ｍに対するコミットメントＣを演算し、署名要求メッセージＭとして上記署名生成装置に送信するコミットメント生成部と、
署名生成装置から受信した署名σの要素に対し、ペアリング等式が成立するか検証する署名検証部と、
検証に成功した場合は、上記コミットメントＣに対する非対話ゼロ知識証明と上記署名σに対する非対話ゼロ知識証明をそれぞれ生成し、上記情報ｍと共にブラインド署名として上記検証装置に与えるゼロ知識証明生成部と、を含み、
上記署名生成装置は、上記群Ｇ1，Ｇ2の生成元ｇ1、ｇ2とＺqに属する乱数ｘ、ｙ、ｒを使って上記利用者装置から受信した署名要求メッセージＭとの演算により群Ｇ1，Ｇ2，ＧTのいずれかの元となる複数の要素の組をＭに対する署名σとして生成し、上記利用者装置にブラインド署名として送信する電子署名生成部と、を含み、
上記検証装置は、上記公開パラメータと上記コミットメント鍵を使って上記利用者装置から受信したコミットメントに対する非対話ゼロ知識証明と署名に対する非対話ゼロ知識証明とを検証し、検証に成功した場合は上記ブラインド署名を受け入れるゼロ知識証明検証部を含むことを特徴とする署名検証システム。
【請求項２】
請求項１記載の署名検証システムにおいて、
上記利用者装置は、Ｚqに属する乱数ｔとηを生成する第１乱数生成部と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出部と、署名変形部とを含み、上記コミットメント生成部は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証部は上記署名としてσ＝(ａ1，ａ2，ａ3，ａ4，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'を使って次の４つのペアリング等式
e(ｇ1，ａ5)＝e(ａ1，ｇ2)
e(Ｍ，ａ5)＝e(ａ2，ｇ2)
e(ａ2，Ｙ')＝e(ａ4，ｇ2)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形部は上記署名σの各要素ai, i=1,…,5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'2, a'3, a'4, a'5)を生成して上記ゼロ知識証明生成部に与え、上記ゼロ知識証明生成部は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'2): e(C, a'5)e(a'2, g2-1)＝１}
NIZK{(a'2, a'4): e(a'2, Y')e(a'4, g2-1)＝１}
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}
とを生成して上記乱数η出処理された要素ａ'1，ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置は、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成部と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択部と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'を含む公開鍵pkを公開する公開鍵生成部とを含み、上記電子署名生成部は、
ａ1＝ｇ1r
ａ2＝Ｍr 
ａ3＝ｇ1rxＭrxy 
ａ4＝Ｍry 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ2，ａ3，ａ4，ａ5の組を上記署名σとして出力し、
上記検証装置は、上記コミットメント鍵ckと上記乱数ηで処理された要素ａ'1，ａ'5を使って上記コミットメントＣに対する非対話ゼロ知識証明Prf(C)と上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')とを検証することを特徴とする署名検証システム。
【請求項３】
請求項１記載の署名検証システムにおいて、
上記利用者装置は、Ｚqに属する乱数ｔとηを生成する第１乱数生成部と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出部と、署名変形部とを含み、上記コミットメント生成部は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証部は上記署名としてσ＝(ａ1，ａ3，ａ4，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'を使って次の３つのペアリング等式
e(ａ1，Ｙ')＝e(ｇ1，ａ5)
e(Ｍ，ａ5)＝e(ａ4，ｇ2)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形部は上記署名σの各要素ai, i=1, 3, 4, 5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'3, a'4, a'5)を生成して上記ゼロ知識証明生成部に与え、上記ゼロ知識証明生成部は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}  
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'4): e(C, a'5)e(a'4, g2-1)＝１}  
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}
とを生成して上記乱数η出処理された要素ａ'1，ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置は、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成部と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択部と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'を含む公開鍵pkを公開する公開鍵生成部とを含み、上記電子署名生成部は、
ａ1＝ｇ1r 
ａ3＝ｇ1rxＭrxy 
ａ4＝Ｍry 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ3，ａ4，ａ5の組を上記署名σとして出力し、
上記検証装置は、上記コミットメント鍵ckと上記乱数η出処理された要素ａ'1，ａ'5を使って上記コミットメントＣに対する非対話ゼロ知識証明Prf(C)と上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')とを検証することを特徴とする署名検証システム。
【請求項４】
請求項１記載の署名検証システムにおいて、
上記利用者装置は、Ｚqに属する乱数ｔとηを生成する第１乱数生成部と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出部と、署名変形部ととを含み、上記コミットメント生成部は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証部は上記署名としてσ＝(ａ1，ａ3，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'，Ｙを使って次の２つのペアリング等式
e(ａ1，ｇ2)＝e(Ｍｇ1，ａ5)
e(ａ3，ｇ2)＝e(ａ1，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形部は上記署名σの各要素ai, i=1, 3, 5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'3, a'5)を生成して上記ゼロ知識証明生成部に与え、上記ゼロ知識証明生成部は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'1): e(C, a'5-1)e(a'1, g2)＝１}  
NIZK{(a'1, a'3): e(a'3, g2)e(a'1, X'-1)＝１}
とを生成して上記乱数η出処理された要素ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置は、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成部と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択部と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2y，Ｙ＝ｇ1yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙを含む公開鍵pkを公開する公開鍵生成部とを含み、上記電子署名生成部は、
ａ1＝ＭryＹr 
ａ3＝ＹrxＭrxy 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ3，ａ5の組を上記署名σとして出力し、
上記検証装置は、上記コミットメント鍵ckと上記乱数η出処理された要素ａ'5を使って上記コミットメントＣに対する非対話ゼロ知識証明Prf(C)と上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')とを検証することを特徴とする署名検証システム。
【請求項５】
請求項１乃至４のいずれかに記載の署名検証システムにおいて、上記コミットメント鍵を予め生成し、要求に応じて上記利用者装置及び上記検証装置に与える登録装置が設けられていることを特徴とする署名検証システム。
【請求項６】
請求項１乃至４のいずれかに記載の署名検証システムにおいて、登録装置が設けられており、上記利用者装置は、上記コミットメント鍵を生成し、上記登録装置に登録するコミットメント鍵生成部を含んでおり、上記登録装置は要求に応じて上記コミットメント鍵を上記検証装置に与えることを特徴とする署名検証システム。
【請求項７】
素数ｑと、バイリニアペアリングｅ：Ｇ1×Ｇ2→ＧTが存在する位数ｑの群Ｇ1，Ｇ2，ＧTとが公開された署名検証システムに使用される、利用者装置と、署名生成装置と、検証装置とによる署名検証方法であり、
上記利用者装置が、上記Ｇ1の元ｇ、ｈ1とＧ2の元ｈ2とを含むコミットメント鍵ckを使って情報ｍに対するコミットメントＣを演算し、署名要求メッセージＭとして上記署名生成装置に送信するコミットメント生成段階と、
上記署名生成装置が、上記群Ｇ1，Ｇ2の生成元ｇ1、ｇ2とＺqに属する乱数ｘ、ｙ、ｒを使って上記利用者装置から受信した署名要求メッセージＭとの演算により群Ｇ1，Ｇ2，ＧTのいずれかの元となる複数の要素の組をＭに対する署名σとして生成し、上記利用者装置に送信する電子署名生成段階と、
上記利用者装置が上記署名生成装置から受信した署名σの要素に対し、ペアリング等式が成立するか検証する署名検証段階と、
検証に成功した場合は、上記利用者装置が上記コミットメントＣに対する非対話ゼロ知識証明と上記署名σに対する非対話ゼロ知識証明をそれぞれ生成し、上記情報ｍと共にブラインド署名として上記検証装置に与えるゼロ知識証明生成段階と、
上記検証装置が、上記公開パラメータと上記コミットメント鍵を使って、上記利用者装置から受信したコミットメントに対する非対話ゼロ知識証明と署名に対する非対話ゼロ知識証明とを検証し、検証に成功したら上記ブラインド署名を受け入れるゼロ知識証明検証段階を含むことを特徴とする署名検証方法。
【請求項８】
請求項７記載の署名検証方法において、
上記利用者装置が、Ｚqに属する乱数ｔとηを生成する第１乱数生成段階と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出段階と、署名を変形する段階とを含み、上記コミットメント生成段階は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証段階は上記署名としてσ＝(ａ1，ａ2，ａ3，ａ4，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'を使って次の４つのペアリング等式
e(ｇ1，ａ5)＝e(ａ1，ｇ2)
e(Ｍ，ａ5)＝e(ａ2，ｇ2)
e(ａ2，Ｙ')＝e(ａ4，ｇ2)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')
が成立するか検証し、成立した場合は、上記署名を変形する段階は上記署名σの各要素ai, i=1,…,5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'2, a'3, a'4, a'5)を生成して上記ゼロ知識証明生成段階に与え、上記ゼロ知識証明生成段階は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'2): e(C, a'5)e(a'2, g2-1)＝１}
NIZK{(a'2, a'4): e(a'2, Y')e(a'4, g2-1)＝１}
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}
とを生成して上記乱数η出処理された要素ａ'1，ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置が、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成段階と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択段階と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'を含む公開鍵pkを公開する公開鍵生成段階とを含み、上記電子署名生成段階は、
ａ1＝ｇ1r
ａ2＝Ｍr 
ａ3＝ｇ1rxＭrxy 
ａ4＝Ｍry 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ2，ａ3，ａ4，ａ5の組を上記署名σとして出力し、
上記検証装置による上記ゼロ知識証明検証段階は、上記コミットメント鍵ckと上記乱数ηで処理された要素ａ'1，ａ'5を使って上記コミットメントＣに対する非対話ゼロ知識証明Prf(C)と上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')とを検証することを特徴とする署名検証方法。
【請求項９】
請求項７記載の署名検証方法において、
上記利用者装置が、Ｚqに属する乱数ｔと乱数ηを生成する第１乱数生成段階と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出段階と、署名変形段階とを含み、上記コミットメント生成段階は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証段階は上記署名としてσ＝(ａ1，ａ3，ａ4，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'を使って次の３つのペアリング等式
e(ａ1，Ｙ')＝e(ｇ1，ａ5)
e(Ｍ，ａ5)＝e(ａ4，ｇ2)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形段階は上記署名σの各要素ai, i=1, 3, 4, 5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'3, a'4, a'5)を生成して上記ゼロ知識証明生成段階に与え、上記ゼロ知識証明生成段階は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}  
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'4): e(C, a'5)e(a'4, g2-1)＝１}  
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}
とを生成して上記乱数ηで処理された要素ａ'1，ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置が、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成段階と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択段階と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'を含む公開鍵pkを公開する公開鍵生成段階とを含み、上記電子署名生成段階は、
ａ1＝ｇ1r 
ａ3＝ｇ1rxＭrxy 
ａ4＝Ｍry 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ3，ａ4，ａ5の組を上記署名σとして出力し、
上記検証装置による上記ゼロ知識証明検証段階は、上記コミットメント鍵ckと上記乱数ηで処理された要素ａ'1，ａ'5を使って上記コミットメントＣに対する非対話ゼロ知識証明Prf(C)と上記上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')とを検証することを特徴とする署名検証方法。
【請求項１０】
請求項７記載の署名検証方法において、
上記利用者装置が、Ｚqに属する乱数ｔとηを生成する第１乱数生成段階と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出段階と、署名変形段階とを含み、上記コミットメント生成段階は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証段階は上記署名としてσ＝(ａ1，ａ3，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'，Ｙを使って次の２つのペアリング等式
e(ａ1，ｇ2)＝e(Ｍｇ1，ａ5)
e(ａ3，ｇ2)＝e(ａ1，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形段階は上記署名σの各要素ai, i=1, 3, 5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'3, a'5)を生成して上記ゼロ知識証明生成段階に与え、上記ゼロ知識証明生成段階は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'1): e(C, a'5-1)e(a'1, g2)＝１}  
NIZK{(a'1, a'3): e(a'3, g2)e(a'1, X'-1)＝１}
とを生成して上記乱数ηで処理された要素ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置が、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成段階と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択段階と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2y，Ｙ＝ｇ1yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙを含む公開鍵pkを公開する公開鍵生成段階とを含み、上記電子署名生成段階は、
ａ1＝ＭryＹr 
ａ3＝ＹrxＭrxy 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ3，ａ5の組を上記署名σとして出力し、
上記検証装置による上記ゼロ知識証明検証段階は、上記コミットメント鍵ckと上記乱数ηで処理された要素ａ'5を使って上記コミットメントＣに対する非対話ゼロ知識証明Prf(C)と上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')とを検証することを特徴とする署名検証方法。
【請求項１１】
請求項７乃至１０のいずれかに記載の署名検証方法において、登録装置が設けられており、上記登録装置が上記コミットメント鍵を予め生成し、要求に応じて上記利用者装置及び上記検証装置に与える段階を含むことを特徴とする署名検証方法。
【請求項１２】
請求項７乃至１０のいずれかに記載の署名検証方法において、登録装置が設けられており、上記利用者装置が、上記コミットメント鍵を生成し、上記登録装置に登録するコミットメント鍵生成段階を含んでおり、上記登録装置が、要求に応じて上記コミットメント鍵を上記検証装置に与える段階を含んでいることを特徴とする署名検証方法。
【請求項１３】
素数ｑと、バイリニアペアリングｅ：Ｇ1×Ｇ2→ＧTが存在する位数ｑの群Ｇ1，Ｇ2，ＧTとが公開された署名検証システムに使用される、利用者装置と、署名生成装置とによるブラインド署名生成方法であり、
上記利用者装置が、上記Ｇ1の元ｇ、ｈ1とＧ2の元ｈ2とを含むコミットメント鍵ckを使って情報ｍに対するコミットメントＣを演算し、署名要求メッセージＭとして上記署名生成装置に送信するコミットメント生成段階と、
上記署名生成装置が、上記群Ｇ1，Ｇ2の生成元ｇ1、ｇ2とＺqに属する乱数ｘ、ｙ、ｒを使って上記利用者装置から受信した署名要求メッセージＭとの演算により群Ｇ1，Ｇ2，ＧTのいずれかの元となる複数の要素の組をＭに対する署名σとして生成し、上記利用者装置に送信する電子署名生成段階と、
上記利用者装置が上記署名生成装置から受信した署名σの要素に対し、ペアリング等式が成立するか検証する署名検証段階と、
検証に成功した場合は、上記利用者装置が上記コミットメントＣに対する非対話ゼロ知識証明と上記署名σに対する非対話ゼロ知識証明をそれぞれ生成し、上記情報ｍと共にブラインド署名として出力するゼロ知識証明生成段階と、を含むことを特徴とするブラインド署名生成方法。
【請求項１４】
請求項１３記載のブラインド署名生成方法において、
上記利用者装置が、Ｚqに属する乱数ｔとηを生成する第１乱数生成段階と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出段階と、署名を変形する段階とを含み、上記コミットメント生成段階は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証段階は上記署名としてσ＝(ａ1，ａ2，ａ3，ａ4，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'を使って次の４つのペアリング等式
e(ｇ1，ａ5)＝e(ａ1，ｇ2)
e(Ｍ，ａ5)＝e(ａ2，ｇ2)
e(ａ2，Ｙ')＝e(ａ4，ｇ2)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')
が成立するか検証し、成立した場合は、上記署名を変形する段階は上記署名σの各要素ai, i=1,…,5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'2, a'3, a'4, a'5)を生成して上記ゼロ知識証明生成段階に与え、上記ゼロ知識証明生成段階は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'2): e(C, a'5)e(a'2, g2-1)＝１}
NIZK{(a'2, a'4): e(a'2, Y')e(a'4, g2-1)＝１}
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}
とを生成して上記乱数ηで処理された要素ａ'1，ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置が、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成段階と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択段階と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'を含む公開鍵pkを公開する公開鍵生成段階とを含み、上記電子署名生成段階は、
ａ1＝ｇ1r
ａ2＝Ｍr 
ａ3＝ｇ1rxＭrxy 
ａ4＝Ｍry 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ2，ａ3，ａ4，ａ5の組を上記署名σとして出力することを特徴とするブラインド署名生成方法。
【請求項１５】
請求項１３記載のブラインド署名生成方法において、
上記利用者装置が、Ｚqに属する乱数ｔと乱数ηを生成する第１乱数生成段階と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出段階と、署名変形段階とを含み、上記コミットメント生成段階は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証段階は上記署名としてσ＝(ａ1，ａ3，ａ4，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'を使って次の３つのペアリング等式
e(ａ1，Ｙ')＝e(ｇ1，ａ5)
e(Ｍ，ａ5)＝e(ａ4，ｇ2)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形段階は上記署名σの各要素ai, i=1, 3, 4, 5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'3, a'4, a'5)を生成して上記ゼロ知識証明生成段階に与え、上記ゼロ知識証明生成段階は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}  
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'4): e(C, a'5)e(a'4, g2-1)＝１}  
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}
とを生成して上記乱数ηで処理された要素ａ'1，ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置が、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成段階と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択段階と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'を含む公開鍵pkを公開する公開鍵生成段階とを含み、上記電子署名生成段階は、
ａ1＝ｇ1r 
ａ3＝ｇ1rxＭrxy 
ａ4＝Ｍry 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ3，ａ4，ａ5の組を上記署名σとして出力することを特徴とするブラインド署名生成方法。
【請求項１６】
請求項１３記載のブラインド署名生成方法において、
上記利用者装置が、Ｚqに属する乱数ｔとηを生成する第１乱数生成段階と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出段階と、署名変形段階とを含み、上記コミットメント生成段階は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証段階は上記署名としてσ＝(ａ1，ａ3，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'，Ｙを使って次の２つのペアリング等式
e(ａ1，ｇ2)＝e(Ｍｇ1，ａ5)
e(ａ3，ｇ2)＝e(ａ1，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形段階は上記署名σの各要素ai, i=1, 3, 5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'3, a'5)を生成して上記ゼロ知識証明生成部に与え、上記ゼロ知識証明生成段階は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'1): e(C, a'5-1)e(a'1, g2)＝１}  
NIZK{(a'1, a'3): e(a'3, g2)e(a'1, X'-1)＝１}
とを生成して上記乱数ηで処理された要素ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力し、
上記署名生成装置が、上記乱数ｒ、ｘ、ｙを生成する第２乱数生成段階と、上記群Ｇ1、Ｇ2から生成元ｇ1、ｇ2を選択する生成元選択段階と、Ｘ'＝ｇ1x，Ｙ'＝ｇ2y，Ｙ＝ｇ1yを計算し、ｇ1、ｇ2、Ｘ'，Ｙ'，Ｙを含む公開鍵pkを公開する公開鍵生成段階とを含み、上記電子署名生成段階は、
ａ1＝ＭryＹr 
ａ3＝ＹrxＭrxy 
ａ5＝ｇ2ry 
を演算し、上記ａ1，ａ3，ａ5の組を上記署名σとして出力することを特徴とするブラインド署名生成方法。
【請求項１７】
素数ｑと、ペアリングｅと、ペアリングｅ：Ｇ1×Ｇ2→ＧTが存在する位数ｑの群Ｇ1，Ｇ2，ＧTとが公開された署名検証システムに使用される利用者装置であり、
上記Ｇ1の元ｇ、ｈ1とＧ2の元ｈ2とを含むコミットメント鍵ckを使って情報ｍに対するコミットメントＣを演算し、署名要求メッセージＭとして署名生成装置に送信するコミットメント生成部と、
上記署名生成装置から受信した署名σの要素に対し、ペアリング等式が成立するか検証する署名検証部と、
検証に成功した場合は、上記コミットメントＣに対する非対話ゼロ知識証明と上記署名σに対する非対話ゼロ知識証明をそれぞれ生成し、上記情報ｍと共にブラインド署名として出力するゼロ知識証明生成部と、を含むことを特徴とする利用者装置。
【請求項１８】
請求項１７記載の利用者装置は、更に、Ｚqに属する乱数ｔとηを生成する第１乱数生成部と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出部と、署名変更部とを含み、
上記コミットメント生成部は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証部は上記署名として上記署名生成装置が
ａ1＝ｇ1r
ａ2＝Ｍr 
ａ3＝ｇ1rxＭrxy 
ａ4＝Ｍry 
ａ5＝ｇ2ry 
を演算して生成した生成した署名σ＝(ａ1，ａ2，ａ3，ａ4，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'を使って次の４つのペアリング等式
e(ｇ1，ａ5)＝e(ａ1，ｇ2)
e(Ｍ，ａ5)＝e(ａ2，ｇ2)
e(ａ2，Ｙ')＝e(ａ4，ｇ2)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形部は上記署名σの各要素ai, i=1,…,5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'2, a'3, a'4, a'5)を生成して上記ゼロ知識証明生成部に与え、上記ゼロ知識証明生成部は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'2): e(C, a'5)e(a'2, g2-1)＝１}
NIZK{(a'2, a'4): e(a'2, Y')e(a'4, g2-1)＝１}
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}
とを生成して上記乱数ηで処理された要素ａ'1，ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力することを特徴とする利用者装置。
【請求項１９】
請求項１７記載の利用者装置は、更に、Ｚqに属する乱数ｔとηを生成する第１乱数生成部と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出部と、署名変形部とを含み、
上記コミットメント生成部は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証部は上記署名として上記署名生成装置が
ａ1＝ｇ1r 
ａ3＝ｇ1rxＭrxy 
ａ4＝Ｍry 
ａ5＝ｇ2ry 
を演算して生成した上記署名σ＝(ａ1，ａ3，ａ4，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'を使って次の３つのペアリング等式
e(ａ1，Ｙ')＝e(ｇ1，ａ5)
e(Ｍ，ａ5)＝e(ａ4，ｇ2)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形部は上記署名σの各要素ai, i=1,…,5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'2, a'3, a'4, a'5)を生成して上記ゼロ知識証明生成部に与え、上記ゼロ知識証明生成部は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}  
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'4): e(C, a'5)e(a'4, g2-1)＝１}  
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}
とを生成して上記乱数ηで処理された要素ａ'1，ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力することを特徴とする利用者装置。
【請求項２０】
請求項１７記載の利用者装置は、更に、Ｚqに属する乱数ｔとηを生成する第１乱数生成部と、上記元ｈ2と上記乱数ｔから開封情報Ｈ'＝ｈ2tを計算する開封情報算出部と、署名変形部とを含み、
上記コミットメント生成部は上記コミットメント鍵に含まれる上記元ｇ、ｈ1と上記乱数ｔとを使って上記情報ｍに対しコミットメントＣ＝ｇmｈ1tを演算し、上記署名検証部は上記署名として上記署名生成装置が
ａ1＝ＭryＹr 
ａ3＝ＹrxＭrxy 
ａ5＝ｇ2ry 
を演算して生成した署名σ＝(ａ1，ａ3，ａ5)を上記署名生成装置から受信し、上記コミットメントＣ＝Ｍと、上記署名生成装置が生成した公開鍵に含まれるｇ1，ｇ2，Ｘ'，Ｙ'，Ｙを使って次の２つのペアリング等式
e(ａ1，ｇ2)＝e(Ｍｇ1，ａ5)
e(ａ3，ｇ2)＝e(ａ1，Ｘ')
が成立するか検証し、成立した場合は、上記署名変形部は上記署名σの各要素ai, i=1, 3, 5、を上記乱数ηでそれぞれ処理して変形された署名σ'＝(a'1, a'3, a'5)を生成して上記ゼロ知識証明生成部に与え、上記ゼロ知識証明生成部は、上記開封情報Ｈ'を使って上記コミットメントＣに対し非対話ゼロ知識証明Prf(C)：
NIZK{(C,H'): e(C/gm, h2)e(h1-1, H')＝１}
と、上記変形された署名σ'に対する非対話ゼロ知識証明Prf(σ')：
NIZK{(C, a'1): e(C, a'5-1)e(a'1, g2)＝１}  
NIZK{(a'1, a'3): e(a'3, g2)e(a'1, X'-1)＝１}
とを生成して上記乱数ηで処理された要素ａ'5と共にｍ、Prf(C)、Prf(σ')を上記ブラインド署名として出力することを特徴とする利用者装置。
【請求項２１】
請求項１７乃至２０のいずれかに記載のブラインド署名を生成する利用者装置としてコンピュータを機能させるためのブラインド署名生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、利用者装置が署名生成装置から署名を得て、検証装置にその署名を与えずに署名の正当性を検証させる署名検証システム、署名検証方法、ブラインド署名生成方法、利用者装置、及びブラインド署名生成プログラムに関する。
【背景技術】
【０００２】
電子署名は電子現金やクレデンシャルシステムなど、様々な暗号プロトコルにおいて基本的な構成要素として利用されている。ブラインド署名方式は、利用者ＡがメッセージＭの内容を秘匿にしたまま、署名者からメッセージＭに対する署名σを得ることができる方法である。利用者は署名者から得た署名σを変換し、検証者に変換した署名ｓを提出する。提出された署名ｓは、確かにＭに対する署名者の署名であることが検証可能であり、提出された署名ｓは、たとえ署名者であってもその署名ｓが、署名者が利用者Ａに与えたものであることを識別できないという特徴がある。つまり、署名者と利用者間での直接的な署名ｓの授受関係を知られることがないので、安全性の点で優れている。しかしながら、署名ｓの検証のためには、利用者はメッセージＭと共に署名ｓを検証者に渡す必要があるため、署名者から利用者に送信された署名σと、利用者から検証者に送信された署名ｓとメッセージＭを盗聴することにより、σとｓ、Ｍの関係が知られてしまい、好ましくない。
【０００３】
Universal composable model上で安全性証明が可能なブラインド署名方式が非特許文献１に提案されている。ユニバーサルコンポーザブルモデルは、複数のプロトコルや暗号アルゴリズムが用いられて１つのシステムを成しているような場合の安全性証明に適したモデルであり、ランダムオラクルモデルに比べていくつもの暗号ツールが混ざっているような複雑なプロトコルなどを想定しているモデルである。このような複合的なシステムの場合、従来のランダムオラクルモデルでは、たとえ個々（例えば、ある暗号アルゴリズムとある署名アルゴリズムなど）の安全性が単独で証明できていたとしても、システム全体の安全性を保証するものにはならず、システムの安全性を示す場合には、システム全体を捉えて証明しなおさなければならない。
【０００４】
ユニバーサルコンポーザブルモデルでは、個々の安全性が個のモデル上で証明されていた場合、システム全体の安全性はその積み上げで示せることになり、個々の（暗号アルゴリズムや署名アルゴリズム）の安全性が示されていれば、システム全体の安全性はそこから導くことができる特徴を持っている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Aggelos Kiayias, Hong-Sheng Zhou: "Equivocal Blind Signatures and Adaptie UC-Security", TCC 2008, pp.340-355.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１で示されている従来のユニバーサルコンポーザブルモデルで安全性証明可能なブラインド署名を構成する要求条件は複雑・難解で、必要以上に過多な条件を、安全性の性質として求めるものであり、従って非効率的なものであった。この発明の目的は、利用者が検証者に署名を渡さずに、利用者がメッセージに対する署名を確かに所有していることを検証できる、ユニバーサルコンポーザブルモデル上で安全性証明可能で効率的なブラインド署名方法を用いた署名検証システム、署名検証方法、ブラインド署名生成方法、利用者装置、及びブラインド署名生成プログラムを提供することである。
【課題を解決するための手段】
【０００７】
この発明によれば、利用者装置と、署名生成装置と、検証装置とを含み、素数ｑと、バイリニアペアリングｅ：Ｇ1×Ｇ2→ＧTが存在する位数ｑの群Ｇ1，Ｇ2，ＧTとを公開した署名検証システムにおいて、
【０００８】
上記利用者装置は、上記Ｇ1の元ｇ、ｈ1とＧ2の元ｈ2とを含むコミットメント鍵ckを使って情報ｍに対するコミットメントＣを演算し、署名要求メッセージＭとして上記署名生成装置に送信し、署名生成装置から受信した署名σの要素に対し、ペアリング等式が成立するか検証し、検証に成功した場合は、上記コミットメントＣに対する非対話ゼロ知識証明と上記署名σに対する非対話ゼロ知識証明をそれぞれ生成し、上記情報ｍと共にブラインド署名として上記検証装置に与え、
【０００９】
上記署名生成装置は、上記群Ｇ1，Ｇ2の生成元ｇ1、ｇ2と位数ｑの剰余群Ｚqに属する乱数ｘ、ｙ、ｒを使って上記利用者装置から受信した署名要求メッセージＭとの演算により群Ｇ1，Ｇ2，ＧTのいずれかの元となる複数の要素の組をＭに対する署名σとして生成し、上記利用者装置にブラインド署名として送信し、
【００１０】
上記検証装置は、上記公開パラメータと上記コミットメント鍵を使って上記利用者装置から受信したコミットメントに対する非対話ゼロ知識証明と署名に対する非対話ゼロ知識証明とを検証し、検証に成功した場合は上記ブラインド署名を受け入れるように構成される。
【発明の効果】
【００１１】
本発明の署名検証システムによれば、利用者装置は公開されているバイリニアペアリングの群の任意の値を用いて情報ｍに対しコミットメントＣを生成し、署名生成装置は前記群の任意の値を用いて署名要求メッセージＭ＝Ｃに対し署名σを生成し、利用者装置はコミットメントＣと署名σに対しそれぞれバイリニアペアリングｅの群の値を知っていることを証明できる非対話ゼロ知識証明を生成して情報ｍと共にブラインド署名として検証装置に与える。従って、ユニバーサルコンポーザブルモデル上で安全性証明可能なブラインド署名方式が可能である。しかも、署名装置から利用者装置への署名と、利用者装置から検証装置へのブラインド署名を盗聴してもそれら間の対応関係を第３者は特定することができない。
【図面の簡単な説明】
【００１２】
【図１】この発明による署名検証システムを示すブロック図。
【図２】図１の署名検証システムによる処理手順の一例を示すフロー図。
【図３】実施例１における利用者装置の機能構成の一例を示すブロック図。
【図４】図３の利用者装置による処理手順の一例を示すフロー図。
【図５】実施例１における署名生成装置の機能構成の一例を示すブロック図。
【図６】図５の署名生成装置による処理手順の一例を示すフロー図。
【図７】実施例１における検証装置の機能構成の一例を示すブロック図。
【図８】図７の検証装置による処理手順の一例を示すフロー図。
【図９】実施例２における利用者装置の機能構成の一例を示すブロック図。
【図１０】図９の利用者装置による処理手順の一例を示すフロー図。
【図１１】実施例２における署名生成装置の機能構成の一例を示すブロック図。
【図１２】図１１の署名生成装置による処理手順の一例を示すフロー図。
【図１３】実施例２における検証装置の機能構成の一例を示すブロック図。
【図１４】図１３の検証装置による処理手順の一例を示すフロー図。
【図１５】実施例３における利用者装置の機能構成の一例を示すブロック図。
【図１６】図１５の利用者装置による処理手順の一例を示すフロー図。
【図１７】実施例３における署名生成装置の機能構成の一例を示すブロック図。
【図１８】図１７の署名生成装置による処理手順の一例を示すフロー図。
【図１９】実施例３における検証装置の機能構成の一例を示すブロック図。
【図２０】図１９の検証装置による処理手順の一例を示すフロー図。
【図２１】この発明の署名検証システムにおける利用者装置のハードウェア構成を例示したブロック図。
【発明を実施するための形態】
【００１３】
図１はこの発明が実施される電子署名検証システム１０の構成の概要を示し、図２は署名検証システムにおける処理手順を示す。電子署名検証システムは利用者装置１００と、署名生成装置２００と、検証装置３００と、登録装置４００とを含んでいる。登録装置４００は予め大きな素数ｑと、バイリニアペアリングｅ：Ｇ1×Ｇ2→ＧTを満足する位数ｑの群Ｇ1、Ｇ2、ＧTとを決め、公開パラメータｖ＝(q, G1, G2, GT, e)として保持している。Ｇ1、Ｇ2はそれらの任意の生成元をｈ1、ｈ2とすると、任意の乱数ｔに対し、ｈ1tからｈ2tを計算できるのは乱数ｔを知っている場合に限られるという性質を有する群である。なお、ｇbとは、ｇ∈Ｇに対し、群Ｇで定義される演算をｂ回行うことを意味する。バイリニアペアリングｅとしては、WeilペアリングやTateペアリングを使用することができる。
【００１４】
利用者装置１００は予め公開パラメータｖを登録装置４００から取得し(S11)、公開パラメータｖに基づいてコミットメント鍵ckを生成し、登録装置４００に登録する(S12)。コミットメントを行うごとに公開パラメータｖを要求しなくても、公開パラメータｖを記憶しておき、それを使用してもよい。利用者装置１００は更に、入力された情報ｍに対し、コミットメント鍵ck＝(v, g, h1, h2)を使ってコミットメントＣを生成し、署名要求メッセージＭとして署名生成装置２００に送る(S１3)。なお、コミットメント鍵ckに公開パラメータｖを含めないでもよく、以下の各実施例でも同様である。
【００１５】
署名生成装置２００は、予め公開パラメータｖを登録装置４００から取得し(S21)、公開パラメータｖに基づいて公開鍵pkと秘密鍵skを生成し、公開鍵pkを登録装置４００に登録する(S22)。利用者装置１００から受信したコミットメントＣである署名要求メッセージＭに対し秘密鍵skを使って署名σを生成し、利用者装置１００に送信する(S23)。
【００１６】
利用者装置１００は、登録装置４００から公開鍵pkを取得し(S14)、それを使って受信した署名σを検証し(S15)、正当であればコミットメントＣに対する非対話ゼロ知識証明Prf(C)とブラインド署名σに対する非対話ゼロ知識証明Prf(σ)を生成し、情報ｍと共にブラインド署名として検証装置３００に送信する(S16)。検証装置３００は、予め登録装置４００から公開パラメータｖを取得し(S31)、更に登録装置４００からコミットメント鍵ckを取得する(S32)。受信した非対話ゼロ知識証明Prf(C)と非対話ゼロ知識証明Prf(σ)を、公開パラメータｖとコミットメント鍵ckと情報ｍを使って検証する(S33)。検証に成功すれば、利用者装置１００が確かに情報ｍに対応するコミットメントＣに対する署名σを所有しており、従って、情報ｍに対するコミットメントＣを所有していることが確認できたことになる。
【００１７】
コミットメントＣ及びブラインド署名σに対する非対話ゼロ知識証明は、例えば Jens Groth, Amit Sahai, "Efficient Non-interractive Proof Systems for Bilinear Groups", EUROCRYPT 2008, pp.415-432に開示されているペアリングの群の要素に対する非対話ゼロ知識証明を使用することができる。
【００１８】
上述のシステムの概要は以下の実施例に共通である。以下に各実施例の詳細を説明する。なお、上述では利用者装置１００がコミットメント鍵ck＝(v, g, h1, h2)を生成し、登録装置４００に登録する場合を説明したが、登録装置４００がコミットメント鍵ckを生成し、利用者装置１００及び検証装置３００に与えるようにしてもよい。その場合は図３の利用者装置１００中のコミットメント鍵生成部１１０は不要であり、また図４中のステップＳ１２は登録装置４００からのコミットメント鍵取得ステップに置き換えられる。以下の各実施例においても利用者装置１００がコミットメント鍵ckを生成する場合を示すが、登録装置４００がコミットメント鍵を生成してもよい。
【実施例１】
【００１９】
［登録装置］
登録装置４００は信頼できる第三者等が管理し、公開パラメータｖを登録及び公開している。例えば、登録装置４００は、図示してない通信部と、記憶部と、制御部を有し、通信部を介して、利用者装置１００、署名生成装置２００及び検証装置３００に公開パラメータｖを送信する。また、署名生成装置２００から公開鍵pkを受信し、記憶部に登録し、要求に応じて利用者装置１００に公開鍵pkを送信する。以下、特に記述しなくとも、これら装置との通信は通信部を介して行われるものとする。通信部は、例えば、ＬＡＮアダプタ等により構成され、ＬＡＮやインターネット等からなるネットワークと接続される。但し、利用者装置１００、署名生成装置２００、検証装置３００は必ずしも通信部を有さずともよく、例えば、キーボード等の入力装置から公開パラメータｖを入力してもよいし、また、ＵＳＢメモリ等の可搬媒体に公開パラメータｖを記憶し、それを入力してもよい。以下、同様に各装置（利用者装置、署名生成装置及び検証装置）は送信部を有さずともよく、装置間のデータの入出力は、通信以外の方法であってもよい。登録装置４００の図示してない記憶部は、公開パラメータｖ、コミットメント鍵ck、公開鍵pk等を記憶する。なお、上記「登録」とは、記憶部に記憶することを意味してもよい。また、「公開」とは、利用者の求めに応じて、情報（例えば、公開パラメータｖ、コミットメント鍵ck、公開鍵pk等）を閲覧可能、または、取得可能とすることを意味する。制御部は、各処理を制御する。
【００２０】
［利用者装置］
図３は、利用者装置１００の構成例を示し、図４は、利用者装置１００の処理手順S100の一例を示す。利用者装置１００は、通信部１０１と、記憶部１０２と、制御部１０３と、コミットメント鍵生成部１１０と、乱数生成部１２０と、コミットメント生成部１３０と、開封情報生成部１４０と、署名検証部１５０と、署名変形部１６０と、ゼロ知識証明生成部１７０とを含んでいる。
【００２１】
本実施例の利用者装置１００は、制御部１０３の制御のもと各処理を実行する。利用者装置１００は、登録装置４００から公開パラメータｖを受け取る。例えば、通信部１０１は、署名生成装置２００、登録装置４００及び検証装置３００と通信を行い、登録装置４００から公開パラメータｖを受信し、記憶部１０２に記憶する(S110)。以下、特に記述しなくとも、署名生成装置２００、登録装置４００及び検証装置３００と通信する際には、通信部１０１を介して行われるものとする。
【００２２】
また、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部１０２に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部１０２に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。
【００２３】
コミットメント鍵生成部１１０は、記憶部１０２から公開パラメータｖ＝(q, G1, G2, GT, e)が入力され、Ｇ1から生成元ｇ及びｈ１を、Ｇ2から生成元ｈ2を無作為に選択し、これら生成元を用いてコミットメント鍵ck＝(v, g, h1, h2)を生成し，登録装置４００に登録する。また、生成元ｈ1をコミットメント生成部１３０へ出力し、生成元ｈ2を開封情報算出部１４０へ出力する(S120)。
【００２４】
乱数生成部１２０は、Ｚqに属する任意の乱数ｔ及びηを生成し、記憶部１０２に保存すると共に乱数ｔを開封情報算出部１４０及びコミットメント生成部１３０へ出力する(S130)。開封情報算出部１４０は、Ｇ２の生成元ｈ２及び乱数ｔが入力され、開封情報Ｈ＝ｈ2tを算出する(S140)。これにより開封情報Ｈが離散対数問題が困難な元となる。開放情報算出部１４０は、開封情報Ｈ＝ｈ2tをゼロ知識証明生成部１７０に出力する。
【００２５】
コミットメント生成部１３０は、乱数生成部１２０から乱数ｔを、コミットメント鍵生成部１２０からＧ1の生成元ｇ、ｈ1を、さらに情報ｍを入力され、コミットメントＣ＝ｇｍｈ1tを生成し、署名要求メッセージＭ＝Ｃとして署名生成装置２００に送信する(S150)。また、コミットメントＣを署名検証部１５０とゼロ知識証明生成部１７０に与える。なお、情報ｍ∈Ｚqであり、補助記憶装置やメモリ上のデータ等、もしくは、入力インターフェース、キーボード、マウス等から入力されるデータである。
【００２６】
署名検証部１５０と署名変形部１６０と、ゼロ知識証明生成部１７０の説明は次の署名生成装置２００の説明の後に行う。
【００２７】
［署名生成装置］
図５は、署名生成装置２００の構成例を示す図である。図６は、署名生成装置２００の処理手順S200の一例を示す図である。署名生成装置２００は、通信部２０１と、記憶部２０２と、制御部２０３と、生成元選択部２１０と、乱数生成部２２０と、公開鍵生成部２３０と、電子署名生成部２４０を有する。
【００２８】
本実施例の署名生成装置２００は、制御部２０３の制御のもと各処理を実行する。署名生成装置２００は、以下、特に記述しなくとも、登録装置４００及び利用者装置１００と通信する際には、通信部２０１を介して行われるものとする。また、特に示さない限り、入出力される各データや演算過程の各データは、逐一、記憶部２０２に格納・読み出され、各演算処理が進められる。但し、必ずしも記憶部２０２に記憶しなければならないわけではなく、各部間で直接データを受け渡してもよい。署名生成装置２００は、登録装置４００から公開パラメータｖを受信し、記憶部２０２に保存する(S210)。
【００２９】
生成元選択部２１０は、与えられた公開パラメータｖ中の群Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択し、公開パラメータｖを入力され、生成元ｇ１及びｇ２を公開鍵生成部２３０及び電子署名生成部２４０へ出力する(S220)。乱数生成部２２０は、Ｚqに属する乱数ｒ、ｘ及びｙを生成し、乱数ｘ、ｙを公開鍵生成部２３０へ、乱数ｒ、ｘ、ｙを電子署名生成部２４０へ出力し(S230)。乱数生成部２２０は更に乱数ｘ、ｙを秘密鍵sk＝(x, y)として記憶部２０２に秘密に保存する(S240)。なお、秘密鍵skには、対応する公開鍵pkを含め、sk＝(pk, x, y)としてもよい。他の実施例においても同様である。公開鍵pkについての詳細は後述する。
【００３０】
公開鍵生成部２３０は、ｘ、ｙ、ｇ1及びｇ2が入力され、Ｘ'＝ｇ2x、Ｙ'＝ｇ2yを計算し、公開鍵pk＝(v, g1, g2, X', Y')を生成し、通信部２０１を介して、登録装置４００へ送られ、登録される(S250)。ただし、ここではＸＤＨ仮定を前提としている。ＸＤＨはThe External Diffie-Hellman (XDH) assumptionの略であり、いわゆる楕円のペアリングなどが存在する場合に、以下の３つの性質を持つことを想定した仮定である。
【００３１】
・The discrete logarithm problem (DLP)→離散対数問題
・The computational Diffie-Hellman problem (CDH)→いわゆるＤＨ問題
・The computational co-Diffie-Hellman problem (co-DH)
【００３２】
上記のうち、co-DHとは以下のように双対の片方のグループの情報を与えられて、与えられたのとは別のグループのＤＨを計算する問題であり、これを解くのが難しいことを仮定している。具体的には、以下の通りである。
【００３３】
(G1; G2)上のThe co-Diffie-Hellman (co-DH) problemは：
G1, G2をそれぞれP1, P2により生成した位数Ｌの巡回群とする。(G1,G2)上のco-DH問題は(P1; aP1; P2)が与えられaP2を計算することである。
【００３４】
公開鍵pkには、利用した公開パラメータｖの代わりに、それを表す鍵情報ｉを含めpk＝(i, g1, g2, X', Y')としてもよい。この場合には、以下で説明する検証装置３００は、鍵情報ｉに基づいて、登録装置４００に対応する公開パラメータｖiを要求する。また、登録装置４００の記憶している公開パラメータの中から対応する公開パラメータｖを特定することができる場合には、公開鍵pkに公開パラメータｖや、公開パラメータを表示する鍵情報ｉ等を含まなくともよく、検証装置３００は、情報ｍ及び電子署名σを受け付けた際に、登録装置４００に公開パラメータｖを要求する。これらのことは、後述の他の実施例にも当てはまる。
【００３５】
電子署名生成部２４０は、ｇ1、ｇ2、ｒ、ｘ、ｙ及び利用者装置１００から受信したコミットメントＣである署名要求メッセージＭ∈Ｇ1が入力され、署名要求メッセージＭに対し、以下の５つの式
ａ1＝ｇ1r                (1)
ａ2＝Ｍr                 (2)
ａ3＝ｇ1rxＭrxy            (3)
ａ4＝Ｍry                (4)
ａ5＝ｇ2ry                (5)
を計算し、これら５つの値の組を署名要求メッセージＭに対する電子署名σ＝(a1, a2, a3, a4, a5)∈Ｇ15×Ｇ2とし、利用者装置１００に送信する(S260)。
【００３６】
以下、利用者装置１００の説明に戻る。
署名検証部１５０は署名生成装置２００の公開鍵pk＝(v, g1, g2, X', Y')を登録装置４００から取得し(S160)、署名生成装置２００から受信した署名σ＝(a1, a2, a3, a4, a5)と署名要求メッセージＭ（即ちコミットメントＣ）の組に対する検証を、次の４つのペアリング等式が成立するか検査することにより行う(S170)。
【００３７】
e(ｇ1，ａ5)＝e(ａ1，ｇ2)           (6)
e(Ｍ，ａ5)＝e(ａ2，ｇ2)            (7)
e(ａ2，Ｙ')＝e(ａ4，ｇ2)            (8)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')          (9)
【００３８】
＜検証の妥当性＞
式(6)は式(1)及び(5)を用いて、以下のように表すことができる。
【００３９】
e(ｇ1，ｇ2r)＝e (ｇ1r，ｇ2)          (6)'
これが成立することにより、バイリニアペアリングの性質から、両辺中の利用者装置１００に知らされていない乱数ｒが同一であることを確認することができる。同様に、式(7)は式(1)及び(2)を用いて、以下のように表すことができる。
【００４０】
e(Ｍ，ｇ2r)＝e(Ｍr，ｇ2)            (7)'
式(6)'でｒの同一性が確認されたので、式(7)'が成立することにより、送信したＭ＝Ｃと署名の対象となったＭが同一であることを確認することができる。式(8)は式(2)、(4)、Ｙ'＝ｇ2yを用いて、以下のように表すことができる。
【００４１】
e(Ｍr，ｇ2y)＝e(Ｍry，ｇ2)            (8)’
式(6)'と(7)'で乱数ｒの同一性とメッセージＭの同一性が確認されたので、式(8)'が成り立つ場合には、乱数ｙが正しいことが確認できる。式(9)は、式(1)、(3)、(4)、Ｘ'＝ｇ2xを用いて、以下のように表すことができる。
【００４２】
e(ｇ1rxＭrxy，ｇ2)＝e(ｇ1rＭry，ｇ2x)        (9)’
式(6)', (7)', (8)'で乱数ｒ、メッセージＭ、及び乱数ｙが正しいことが確認できたので、式(9)'が成り立つ場合には、乱数ｘが正しいことが確認できる。これらの処理により、電子署名σを作成できるのは、秘密鍵sk＝(ｘ，ｙ)を知っている署名者のみであることが確認できる。
【００４３】
署名検証部１５０で署名σの検証に成功すると、署名に対する非対話ゼロ知識証明を生成し、検証装置３００に送信するが、その署名σの一部の要素を後述のように検証用情報としてそのまま検証装置３００に送信しなければならないので、署名σそのものに対し非対話ゼロ知識証明を生成すると、盗聴した署名の要素から署名装置と利用者装置間のどのセッションで生成された署名が現在利用者装置から出力されたブラインド署名のデータにリンクしているのか特定される危険がある。そこで、安全性を高めるため、署名変形部１６０は乱数生成部１２０で生成した乱数ηを使って署名σの各要素に対し演算処理することにより署名σを署名σ'＝(a'1, a'2, a'3, a'4, a'5)に変形する。ここでは演算処理a'i＝aiη、i=1,…,5、により署名σ'に変形する(S180)。ゼロ知識証明生成部１７０は開封情報Ｈを使って情報ｍに関するコミットメントＣに対する非対話ゼロ知識証明Prf(C)を以下のように生成する。
【００４４】
Prf(C)：NIZK{(C,H): e(C/gm, h2)e(h1-1, H)＝１}          (10)
式(10)は、利用者装置１００が検証装置３００に対し(Ｃ，Ｈ)を隠したまま利用者装置１００が(Ｃ，Ｈ)を確かに所有していることを、e(C/gm, h2)e(h1-1, H)＝１が成立することにより証明する非対話ゼロ知識証明を表す。
【００４５】
ゼロ知識証明生成部１７０は更に、変形された署名σ'中の要素ａ'2，ａ'3，ａ'4について同様に、以下の３つの非対話ゼロ知識証明を生成する。
【００４６】
Prf(σ')：NIZK{(C, a'2): e(C, a'5)e(a'2, g2-1)＝１}            (11)
NIZK{(a'2, a'4): e(a'2, Y')e(a'4, g2-1)＝１}          (12)
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}        (13)
式(11), (12), (13)は利用者装置１００が検証装置に対しそれぞれ(C, a'2), (a'2, a'4), (a'3, a'4)を隠したまま利用者装置１００がこれらを確かに所有していることを、それぞれの等式が成立することにより証明する非対話ゼロ知識証明を表し、これら３つのゼロ知識証明をまとめてPrf(σ')と表すことにする。非対話ゼロ知識証明Prf(C)とPrf(σ')は情報ｍおよび検証用情報としての要素ａ'1，ａ'5と共に検証装置３００に送信される(S180)。
【００４７】
非対話ゼロ知識証明としては、ペアリングの群の要素に対する非対話ゼロ知識証明であればどのようなものでもよく、例えば非特許文献２に示されている技術を使用してもよい。後述の他の実施例についても同様である。
【００４８】
［検証装置］
図７は検証装置３００の構成を示し、図８はその検証処理手順S300の一例を示す。検証装置３００は、通信部３０１と、記憶部３０２と、制御部３０３と、ゼロ知識証明検証部３１０とから構成されている。制御部３０３は通信部３０１、記憶部３０２、ゼロ知識証明検証部３１０の動作を制御する。検証装置３００は、通信部３０１により利用者装置１００及び登録装置４００と通信し、登録装置４００から公開パラメータｖ＝(q, G1, G2, GT, e)を取得して記憶部３０２に保存し(S310)、更に登録装置４００からコミットメント鍵ck＝(v, g, h1, h2)を取得し、記憶部３０２に保存する(S320)。
【００４９】
検証装置３００は通信部３０１により利用者装置１００から情報ｍ、署名σ'の要素ａ'1，ａ'5、コミットメントＣに対する非対話ゼロ知識証明Rrf(C)、署名σ'に対する非対話ゼロ知識証明Prf(σ')を受信し、記憶部３０２に保存すると共にゼロ知識証明検証部３１０に与える(S330)。ゼロ知識証明検証部３１０は、Prf(C)について、式(10)が成立することをコミットメント鍵ckと公開パラメータｖを使って検証する(S340)。また、Prf(σ')について署名σ'の要素ａ'1，ａ'5を使って、
e(ｇ1, ａ'5)＝e(ａ'1，ｇ2)                      (14)
が成立するか検証し、成立すれば署名装置２００が署名生成に使用した乱数ｒと、利用者装置から受信したａ'1＝ａ1η，ａ'5＝ａ5ηに含まれる乱数ｒ（式(1)と(5)を参照）が一致していることを確認できる。
【００５０】
Prf(σ')について更に各式(11),(12),(13)が成立することを、公開パラメータｖを使って検証し、検証に成功すれば、Prf(C)、Prf(σ')、ｍの組を正当なブラインド署名として受け入れる(S350)。
【００５１】
実施例１では利用者装置１００がコミットメント鍵ck＝(v, g, h1, h2)を生成して登録装置４００に登録する場合を示したが、前述のように、登録装置４００がコミットメント鍵ckを生成し、要求に応じて利用者装置１００及び検証装置３００に与えるようにしてもよい。
【実施例２】
【００５２】
実施例２は、実施例１における署名σの要素数を１つ減らして４つとし、署名σの検証式の数も１つ減らして３つとすることにより、処理情報量を減らし、従って処理時間を短縮可能にしたものである。実施例２による署名検証システムの基本構成と全体の処理手順は図１及び図２に示すものと同じであり、図及び説明を省略する。異なる点は利用者装置１００、署名生成装置２００、及び検証装置３００のそれぞれの内部構成である。以下にこれらについて説明する。
【００５３】
実施例２においても、実施例１と同様に前提としてｑを大きな素数とし、Ｇ1，Ｇ2，ＧTを位数ｑの群とし、ｅを効率的に計算可能なバイリニアペアリングｅ：Ｇ1×Ｇ2→ＧTとし、ｖ＝（q, G1, G2, GT, e)を公開パラメータとする。
【００５４】
［利用者装置］
図９は、実施例２による利用者装置１００の構成例を示し、図１０は、利用者装置１００の処理手順S100の一例を示す。利用者装置１００は、通信部１０１と、記憶部１０２と、制御部１０３と、コミットメント鍵生成部１１０と、乱数生成部１２０と、コミットメント生成部１３０と、開封情報生成部１４０と、署名検証部１５１と、署名変形部１６１と、ゼロ知識証明生成部１７１とを含んでいる。図９の利用者装置は、図３の利用者装置における署名検証部１５０と署名変形部１６０とゼロ知識証明生成部１７０が署名検証部１５１と署名変形部１６１とゼロ知識証明生成部１７１に変更されているだけである。また、図１０の処理手順は図４の処理手順におけるステップS170, S180，S190がステップS171, S181，S191に変更されているだけである。
【００５５】
本実施例２の利用者装置１００は、登録装置４００から公開パラメータｖを受信し、記憶部１０２に記憶する(S110)。コミットメント鍵生成部１１０は、記憶部１０２から公開パラメータｖ＝(ｑ,Ｇ1,Ｇ2，ＧT，ｅ)が入力され、Ｇ1から生成元ｇ及びｈ１を、Ｇ2から生成元ｈ2を無作為に選択し、これら生成元を用いてコミットメント鍵ck＝(ｖ，ｇ，ｈ1，ｈ2)を生成し，登録装置４００に登録する。また、生成元ｈ1をコミットメント生成部１３０へ出力し、生成元ｈ2を開封情報算出部１４０へ出力する(S120)。
【００５６】
乱数生成部１２０は、Ｚqに属する乱数ｔ及びηを生成し、記憶部１０２に保存すると共に乱数ｔを開封情報算出部１４０及びコミットメント生成部１３０へ出力する(S130)。開封情報算出部１４０は、Ｇ２の生成元ｈ２及び乱数ｔが入力され、開封情報Ｈ＝ｈ2tを算出する(S140)。これにより開封情報Ｈが離散対数問題が困難な元となる。開放情報算出部１４０は、開封情報Ｈ＝ｈ2tをゼロ知識証明生成部１７１に出力する。  コミットメント生成部１３０は、乱数生成部１２０から乱数ｔを、コミットメント鍵生成部１２０からＧ1の生成元ｇ、ｈ1を、さらに情報ｍを入力され、コミットメントＣ＝ｇｍｈ1tを生成し、署名要求メッセージＭ＝Ｃとして署名生成装置２００に送信する(S150)。また、コミットメントＣを署名検証部１５０とゼロ知識証明生成部１７１に与える。
【００５７】
署名検証部１５１と署名変形部１６１とゼロ知識証明生成部１７１の説明は次の署名生成装置２００の説明の後に行う。
【００５８】
［署名生成装置］
図１１は、実施例２の署名生成装置２００の構成例を示し、図１２はその署名生成処理手順S200の一例を示す。署名生成装置２００は、通信部２０１と、記憶部２０２と、制御部２０３と、生成元選択部２１０と、乱数生成部２２０と、公開鍵生成部２３０と、電子署名生成部２４１を有する。図１１の署名生成装置は図５の署名生成装置における電子署名生成部２４０が電子署名生成部２４１に変更されているだけであり、また図１２の処理手順は図６の処理手順におけるステップS260がステップS261に変更されているだけである。
【００５９】
実施例２の署名生成装置２００は、登録装置４００から公開パラメータｖを受信し、記憶部２０２に保存する(S210)。生成元選択部２１０は、与えられた公開パラメータｖ中の群Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択し、公開パラメータｖを入力され、生成元ｇ１及びｇ２を公開鍵生成部２３０及び電子署名生成部２４０へ出力する(S220)。乱数生成部２２０は、Ｚqに属する乱数ｒ、ｘ及びｙを生成し、乱数ｘ、ｙを公開鍵生成部２３０へ、乱数ｒ、ｘ、ｙを電子署名生成部２４０へ出力し(S230)。乱数生成部２２０は更に乱数ｘ、ｙを秘密鍵sk＝(x, y)として記憶部２０２に秘密に保存する(S240)。なお、秘密鍵skには、対応する公開鍵pkを含め、sk＝(pk, x, y)としてもよい。他の実施例においても同様である。公開鍵pkについての詳細は後述する。
【００６０】
公開鍵生成部２３０は、ｘ、ｙ、ｇ1及びｇ2が入力され、Ｘ'＝ｇ2x、Ｙ'＝ｇ2yを計算し、公開鍵pk＝(v, g1, g2, X', Y')を生成し、通信部２０１を介して、登録装置４００へ送られ、登録される(S250)。ただし、ここでも前述と同様にＸＤＨ仮定を前提とする。
【００６１】
電子署名生成部２４０は、ｇ1、ｇ2、ｒ、ｘ、ｙ及び利用者装置１００から受信したコミットメントＣである署名要求メッセージＭ∈Ｇ1が入力され、署名要求メッセージＭに対し、実施例１とは異なり、以下の４つの式
ａ1＝ｇ1r                (15)
ａ3＝ｇ1rxＭrxy            (16)
ａ4＝Ｍry                (17)
ａ5＝ｇ2ry                (18)
を計算し、これら４つの値の組を署名要求メッセージＭに対する電子署名σ＝(a1, a3, a4, a5)∈Ｇ14×Ｇ2とし、利用者装置１００に送信する(S261）。
【００６２】
以下、図９の利用者装置１００の説明に戻る。
署名検証部１５１は署名生成装置２００の公開鍵pk＝(v, g1, g2, X', Y')を登録装置４００から取得し(S160)、署名生成装置２００から受信した署名σ＝(a1, a3, a4, a5)と署名要求メッセージＭ（即ちコミットメントＣ）の組に対する検証を、次の３つのペアリング等式が成立するか検査することにより行う(S171）。
【００６３】
e(ａ1，Ｙ')＝e(ｇ1，ａ5)           (19)
e(Ｍ，ａ5)＝e(ａ4，ｇ2)            (20)
e(ａ3，ｇ2)＝e(ａ1ａ4，Ｘ')          (21)
【００６４】
＜検証の妥当性＞
式(19)は式(15), (18)及びＹ'＝ｇ2yを用いて、以下のように表すことができる。
【００６５】
e(ｇr1，ｇ2y)＝e(ｇ1，ｇ2ry)          (19)'
これが成立することにより、バイリニアペアリングの性質から、両辺中の利用者装置１００に知らされていない乱数ｒ及びｙが同一であることを確認することができる。同様に、式(20)は式(18)及び(17)を用いて、以下のように表すことができる。
【００６６】
e(Ｍ，ｇ2ry)＝e(Ｍry，ｇ2)            (20)'
式(19)'でｒ，ｙの同一性が確認されたので、式(18)'が成立することにより、送信したＭ＝Ｃと署名の対象となったＭが同一であることを確認することができる。式(21)は、式(15)、(18)、(17)、Ｘ'＝ｇ2xを用いて、以下のように表すことができる。
【００６７】
e(ｇ1rxＭrxy，ｇ2)＝e(ｇ1rＭry，ｇ2x)        (21)’
式(19)', (20)'で乱数ｒ、ｙ及びメッセージＭが正しいことが確認できたので、式(21)'が成り立つ場合には、乱数ｘが正しいことが確認できる。これらの処理により、電子署名σを作成できるのは、秘密鍵sk＝(x, y)を知っている署名者のみであることが確認できる。
【００６８】
署名検証部１５１で署名σの検証に成功すると、署名変形部１６１波乱趨勢西部１２０で生成された乱数ηを使って署名σを署名σ'＝(a'1, a'3, a'4, a'5)、ただしa'i＝aiη、i=1, 3, 4, 5、に変形する。ゼロ知識証明生成部１７１は開封情報Ｈを使って情報ｍに関するコミットメントＣに対する非対話ゼロ知識証明Prf(C)を以下のように生成する。
【００６９】
Prf(C)：NIZK{(C,H): e(C/gm, h2)e(h1-1, H)＝１}          (22)
式(22)は、利用者装置１００が検証装置３００に対し(Ｃ，Ｈ)を隠したまま利用者装置１００が(Ｃ，Ｈ)を確かに所有していることを、等式e(C/gm, h2)e(h1-1, H)＝１が成立することにより証明する非対話ゼロ知識証明を表す。
【００７０】
ゼロ知識証明生成部１７１は更に、変形された署名σ'中の要素ａ'3，ａ'4について同様に、以下の２つの非対話ゼロ知識証明を生成する。
【００７１】
Prf(σ')：NIZK{(C, a'4): e(C, a'5)e(a'4, g2-1)＝１}            (23)
NIZK{(a'3, a'4): e(a'3, g2)e(a'1a'4, X'-1)＝１}        (24)
式(23), (24)は利用者装置１００が検証装置に対しそれぞれ(C, a'4)、(a'3, a'4)を隠したまま利用者装置１００がこれらを確かに所有していることを、それぞれの等式が成立することにより証明する非対話ゼロ知識証明を表し、これら２つのゼロ知識証明をまとめてPrf(σ')と表すことにする。非対話ゼロ知識証明Prf(C)とPrf(σ')は情報ｍ及び要素ａ'1，ａ'5と共に検証装置３００に送信される(S191）。
【００７２】
［検証装置］
図１３は実施例２の検証装置３００の構成を示し、図１４はその検証処理手順S300を示す。検証装置３００は、通信部３０１と、記憶部３０２と、制御部３０３と、ゼロ知識証明検証部３１１とから構成されている。図１３の検証装置は、図７におけるゼロ知識証明検証部３１０がゼロ知識証明検証部３１１に変更されているだけである。また、図１４の処理手順は、図８におけるステップS350がステップS351に変更されているだけである。
【００７３】
検証装置３００は、登録装置４００から公開パラメータｖ＝(q, G1, G2, GT, e)を取得して記憶部３０２に保存し(S310)、更に登録装置４００からコミットメント鍵ck＝(v, g, h1, h2)を取得し、記憶部３０２に保存する(S320)。さらに、検証装置３００は利用者装置１００から情報ｍ、署名σ'の要素ａ'1，ａ'5、コミットメントＣに対する非対話ゼロ知識証明Rrf(C)、署名σ'に対する非対話ゼロ知識証明Prf(σ')を受信し、記憶部３０２に保存すると共にゼロ知識証明検証部３１１に与える(S330)。ゼロ知識証明検証部３１１は、Prf(C)について、式(22)が成立することをコミットメント鍵ckと公開パラメータｖを使って検証する(S340)。また、Prf(σ')について署名σ'の要素ａ'1，ａ'5を使って、
e(ａ'1、Ｙ')＝e(ｇ1，ａ'5)                      (25)
が成立するか検証し、成立すれば署名装置２００が署名生成に使用した乱数ｒと、利用者装置から受信したａ'1＝ａ1η，ａ'5＝ａ5ηに含まれる乱数ｒ（式(15)と(18)を参照）が一致していることを確認できる。
【００７４】
Prf(σ')について更に各式(23),(24)が成立することを、公開パラメータｖを使って検証し、検証に成功すれば、Prf(C)、Prf(σ')、ｍの組を正当なブラインド署名として受け入れる(S351）。
【００７５】
実施例２においても利用者装置１００がコミットメント鍵ck＝(G1, G2, GT, g, h1, h2)を生成して登録装置４００に登録する場合を示したが、前述のように、登録装置４００がコミットメント鍵ckを生成し、要求に応じて利用者装置１００及び検証装置３００に与えるようにしてもよい。
【実施例３】
【００７６】
実施例３は、実施例１における署名σの要素数を２つ減らして３つとし、署名σの検証式の数も２つ減らして２つとすることにより、実施例２より処理情報量を更に減らし、従って処理時間を短縮可能にしたものである。実施例３による署名検証システムの基本構成と全体の処理手順は図１及び図２に示すものと同じであり、図及び説明を省略する。異なる点は利用者装置１００、署名生成装置２００、及び検証装置３００のそれぞれの内部構成である。以下にこれらについて説明する。
【００７７】
実施例３においても、実施例１と同様に前提としてｑを大きな素数とし、Ｇ1，Ｇ2，ＧTを位数ｑの群とし、ｅを効率的に計算可能なバイリニアペアリングｅ：Ｇ1×Ｇ2→ＧTとし、ｖ＝（q, G1, G2, GT, e)を公開パラメータとする。
【００７８】
［利用者装置］
図１５は、実施例２による利用者装置１００の構成例を示し、図１６は、利用者装置１００の処理手順S100の一例を示す。利用者装置１００は、通信部１０１と、記憶部１０２と、制御部１０３と、コミットメント鍵生成部１１０と、乱数生成部１２０と、コミットメント生成部１３０と、開封情報生成部１４０と、署名検証部１５２と、署名変形部１６２と、ゼロ知識証明生成部１７２とを含んでいる。図１５の利用者装置は、図３の利用者装置における署名検証部１５０と署名変形部１６０とゼロ知識証明生成部１７０が署名検証部１５２と署名変形部１６２とゼロ知識証明生成部１７２に変更されているだけである。また、図１６の処理手順は、図４の処理手順におけるステップS170, S180，S190がステップS172, S182，S192に変更されているだけである。
【００７９】
本実施例３の利用者装置１００は、登録装置４００から公開パラメータｖを受信し、記憶部１０２に記憶する(S110)。コミットメント鍵生成部１１０は、記憶部１０２から公開パラメータｖ＝(q, G1, G2, GT, e)が入力され、Ｇ1から生成元ｇ及びｈ１を、Ｇ2から生成元ｈ2を無作為に選択し、これら生成元を用いてコミットメント鍵ck＝(v, g, h1, h2)を生成し，登録装置４００に登録する。また、生成元ｈ1をコミットメント生成部１３０へ出力し、生成元ｈ2を開封情報算出部１４０へ出力する(S120)。
【００８０】
乱数生成部１２０は、Ｚqに属する乱数ｔ及びηを生成し、記憶部１０２に保存すると共に乱数ｔを開封情報算出部１４０及びコミットメント生成部１３０へ出力する(S130)。開封情報算出部１４０は、Ｇ２の生成元ｈ２及び乱数ｔが入力され、開封情報Ｈ＝ｈ2tを算出する(S140)。これにより開封情報Ｈが離散対数問題が困難な元となる。開放情報算出部１４０は、開封情報Ｈ＝ｈ2tをゼロ知識証明生成部１７２に出力する。
【００８１】
コミットメント生成部１３０は、乱数生成部１２０から乱数ｔを、コミットメント鍵生成部１２０からＧ1の生成元ｇ、ｈ1を、さらに情報ｍを入力され、コミットメントＣ＝ｇｍｈ1tを生成し、署名要求メッセージＭ＝Ｃとして署名生成装置２００に送信する(S150)。また、コミットメントＣを署名検証部１５０とゼロ知識証明生成部１７２に与える。
【００８２】
署名検証部１５２と署名変形部１６２とゼロ知識証明生成部１７２の説明は次の署名生成装置２００の説明の後に行う。
【００８３】
［署名生成装置］
図１７は、実施例２の署名生成装置２００の構成例を示し、図１８はその署名生成処理手順S200の一例を示す。署名生成装置２００は、通信部２０１と、記憶部２０２と、制御部２０３と、生成元選択部２１０と、乱数生成部２２０と、公開鍵生成部２３２と、電子署名生成部２４２を有する。図１７の署名生成装置は、図５の署名生成装置における公開鍵生成部２３０と電子署名生成部２４０が公開鍵生成部２３２と電子署名生成部２４２に変更されているだけであり、また図１８の処理手順は図６の処理手順におけるステップS250, S260がステップS252, S262に変更されているだけである。
【００８４】
実施例３の署名生成装置２００は、登録装置４００から公開パラメータｖを受信し、記憶部２０２に保存する(S210)。生成元選択部２１０は、与えられた公開パラメータｖ中の群Ｇ１及びＧ２からそれぞれ生成元ｇ１及びｇ２を無作為に選択し、公開パラメータｖを入力され、生成元ｇ１及びｇ２を公開鍵生成部２３０及び電子署名生成部２４０へ出力する(S220)。乱数生成部２２０は、Ｚqに属する乱数ｒ、ｘ及びｙを生成し、乱数ｘ、ｙを公開鍵生成部２３０へ、乱数ｒ、ｘ、ｙを電子署名生成部２４０へ出力し(S230)。乱数生成部２２０は更に乱数ｘ、ｙを秘密鍵sk＝(x, y)として記憶部２０２に秘密に保存する(S240)。なお、秘密鍵skには、対応する公開鍵pkを含め、sk＝(pk, x, y)としてもよい。他の実施例においても同様である。公開鍵pkについての詳細は後述する。
【００８５】
公開鍵生成部２３２は、ｘ、ｙ、ｇ1及びｇ2が入力され、Ｘ'＝ｇ2x、Ｙ'＝ｇ2yを計算し、更にＹ＝ｇ1yを計算し、公開鍵pk＝(v, g1, g2, X', Y', Y)を生成し、通信部２０１を介して、登録装置４００へ送られ、登録する(S252）。ただし、ここではＳＸＤＨ(asymmetric XDH)仮定を前提とし、その仮定の下ではＹ'＝ｇ2yとＹ＝ｇ1yとが公開されていたとしても互いに独立であり、互いの情報を一切漏らさない。なお、ＳＸＤＨ仮定は前述のＸＤＨ仮定をペアリングの双方のグループに対して仮定しているものである。
【００８６】
電子署名生成部２４２は、ｇ1、ｇ2、ｒ、ｘ、ｙ及び利用者装置１００から受信したコミットメントＣである署名要求メッセージＭ∈Ｇ1が入力され、署名要求メッセージＭに対し、実施例１とは異なり、以下の３つの式
ａ1＝ＭryＹr                (26)
ａ3＝ＹrxＭrxy               (27)
ａ5＝ｇ2ry                  (28)
を計算し、これら３つの値の組を署名要求メッセージＭに対する電子署名σ＝(ａ1，ａ3，ａ5)∈Ｇ12×Ｇ2とし、利用者装置１００に送信する(S262）。
【００８７】
以下、図１５の利用者装置１００の説明に戻る。
署名検証部１５２は署名生成装置２００の公開鍵pk＝(v, g1, g2, X', Y', Y)を登録装置４００から取得し(S160)、署名生成装置２００から受信した署名σ＝(ａ1，ａ3，ａ5)と署名要求メッセージＭ（即ちコミットメントＣ）の組に対する検証を、次の２つのペアリング等式が成立するか検査することにより行う(S172）。
【００８８】
e(ａ1，ｇ2)＝e(Ｍｇ1，ａ5)           (29)
e(ａ3，ｇ2)＝e(ａ1，Ｘ')            (30)
【００８９】
＜検証の妥当性＞
式(29)は式(26), (28)及びＹ＝ｇ1yを用いて、以下のように表すことができる。
【００９０】
e((Ｍｇ1)ry，ｇ2)＝e(Ｍｇ1，ｇ2ry)          (29)'
これが成立することにより、バイリニアペアリングの性質から、両辺中の利用者装置１００に知らされていない乱数ｒ及びｙが同一であることを確認することができる。式(30)は、式(27)、(26)及びＸ'＝ｇ2x、Ｙ＝ｇ1yを用いて、以下のように表すことができる。
【００９１】
e((ＹrＭry)x，ｇ2)＝e(ＹrＭry，ｇ2x)        (30)’
式(29)で乱数ｒ、ｙが正しいことが確認できたので、式(30)が成り立つ場合には、メッセージＭと乱数ｘが正しいことが確認できる。これらの処理により、電子署名σを作成できるのは、秘密鍵sk＝(ｘ，ｙ)を知っている署名者のみであることが確認できる。
【００９２】
署名検証部１５２で署名σの検証に成功すると、署名変形部１６２は乱数生成部１２０で生成された乱数ηを使って署名σを署名σ'＝(a'1, a'3, a'5)、ただしa'i＝aiη、i=1, 3, 5、に変形する(S182)。ゼロ知識証明生成部１７２は開封情報Ｈを使って情報ｍに関するコミットメントＣに対する非対話ゼロ知識証明Prf(C)を以下のように生成する。
【００９３】
Prf(C)：NIZK{(C,H): e(C/gm, h2)e(h1-1, H)＝１}          (31)
式(31)は、利用者装置１００が検証装置３００に対し(Ｃ，Ｈ)を隠したまま利用者装置１００が(Ｃ，Ｈ)を確かに所有していることを、等式e(C/gm, h2)e(h1-1, H)＝１が成立することにより証明する非対話ゼロ知識証明を表す。
【００９４】
更に、変形された署名σ'中の要素ａ'1，ａ'3について同様に、以下の２つの非対話ゼロ知識証明を生成する。
【００９５】
Prf(σ')：NIZK{(C, a'1): e(C, a'5-1)e(a'1, g2)＝１}            (32)
NIZK{(a'1, a'3): e(a'3, g2)e(a'1, X'-1)＝１}          (33)
式(32), (33)は利用者装置１００が検証装置に対しそれぞれ(C, a'1)、(a'1, a'3)を隠したまま利用者装置１００がこれらを確かに所有していることを、それぞれの等式が成立することにより証明する非対話ゼロ知識証明を表し、これら２つのゼロ知識証明をまとめてPrf(σ')と表すことにする。非対話ゼロ知識証明Prf(C)とPrf(σ')は情報ｍ及び要素ａ'5と共に検証装置３００に送信される(S192）。
【００９６】
［検証装置］
図１９は実施例２の検証装置３００の構成を示し、図２０はその検証処理手順S300の一例を示す。検証装置３００は、通信部３０１と、記憶部３０２と、制御部３０３と、ゼロ知識証明検証部３１２とから構成されている。図１９の検証装置は、図７におけるゼロ知識証明検証部３１０がゼロ知識証明検証部３１２に変更されているだけである。また、図２０の処理手順は、図８におけるステップS350がステップS352に変更されているだけである。
【００９７】
検証装置３００は、登録装置４００から公開パラメータｖ＝(q, G1, G2, GT, e)を取得して記憶部３０２に保存し(S310)、更に登録装置４００からコミットメント鍵ck＝(v, g, h1, h2)を取得し、記憶部３０２に保存する(S320)。さらに、検証装置３００は利用者装置１００から情報ｍ、署名σ'の要素ａ'5、コミットメントＣに対する非対話ゼロ知識証明Rrf(C)、署名σ'に対する非対話ゼロ知識証明Prf(σ')を受信し、記憶部３０２に保存すると共にゼロ知識証明検証部３１２に与える(S330)。ゼロ知識証明検証部３１２は、Prf(C)について、式(31)が成立することをコミットメント鍵ckと公開パラメータｖを使って検証する(S340)。
【００９８】
Prf(σ')について更に各式(32),(33)が成立することを、公開パラメータｖを使って検証し、検証に成功すれば、Prf(C)、Prf(σ')、ｍの組を正当なブラインド署名として受け入れる(S350)。
【００９９】
実施例３においても利用者装置１００がコミットメント鍵ck＝(G1, G2, GT, g, h1, h2)を生成して登録装置４００に登録する場合を示したが、前述のように、登録装置４００がコミットメント鍵ckを生成し、要求に応じて利用者装置１００及び検証装置３００に与えるようにしてもよい。
【０１００】
＜ハードウェア構成＞
図２１は、図１に示したこの発明による署名検証システムにおける利用者装置１００のハードウェア構成を例示したブロック図である。署名生成装置２００、検証装置３００及び登録装置４００も同様の構成とすることができる。
【０１０１】
図２１に例示するように、この例の利用者装置１００は、ＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【０１０２】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インターフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インターフェース等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、署名生成装置２００、検証装置３００及び登録装置４００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ(Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。
【０１０３】
なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【０１０４】
上述のように、プログラム領域１４ａ，１６ａには、図４の処理手順で示される図３の利用者装置１００のコミットメント鍵生成部１１０、乱数生成部１２０、コミットメント生成部１３０、開封情報算出部１４０、署名検証部１５０、署名変形部１６０、ゼロ知識証明生成部１７０等の処理を実行するためのプログラムが格納される。利用者装置１００の処理手順（図４）を実行するプログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラムが単体でそれぞれの機能を実現してもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものでもよい。
【０１０５】
ＣＰＵ１１（図２１）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【０１０６】
署名生成装置２００、検証装置３００、登録装置４００もそれぞれ同様に構成できる。前述の図３、５、７は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成される利用者装置１００、署名生成装置２００、検証装置３００の機能構成を例示したブロック図である。
【０１０７】
例えば図５の署名生成装置２００の場合、記憶部２０２は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、通信部２０１と、記憶部２０２と、制御部２０３と、生成元選択部２１０と、乱数生成部２２０と、公開鍵生成部２３０と、電子署名生成部２４０は、ＣＰＵ１１に署名生成プログラムを実行させることにより構成されるものである。利用者装置１００、検証装置３００についても同様である。
【０１０８】
図２１を参照性説明したこの発明をコンピュータで実施する構成は、実施例２及び３にも適用できる。
【図１】
2010200065.tif 000003
【図２】
2010200065.tif 000004
【図３】
2010200065.tif 000005
【図４】
2010200065.tif 000006
【図５】
2010200065.tif 000007
【図６】
2010200065.tif 000008
【図７】
2010200065.tif 000009
【図８】
2010200065.tif 000010
【図９】
2010200065.tif 000011
【図１０】
2010200065.tif 000012
【図１１】
2010200065.tif 000013
【図１２】
2010200065.tif 000014
【図１３】
2010200065.tif 000015
【図１４】
2010200065.tif 000016
【図１５】
2010200065.tif 000017
【図１６】
2010200065.tif 000018
【図１７】
2010200065.tif 000019
【図１８】
2010200065.tif 000020
【図１９】
2010200065.tif 000021
【図２０】
2010200065.tif 000022
【図２１】
2010200065.tif 000023