ブラインド署名生成・検証方法、ブラインド署名生成装置、利用者装置、ブラインド署名検証装置、ブラインド署名生成・検証システム、ブラインド署名生成プログラム、利用者プログラム、ブラインド署名検証プログラム
【課題】ハッシュ関数に依存することなく、安全性が保証された効率的なブラインド署名を実現する。
【解決手段】ブラインド署名生成装置１０が、秘密鍵x,y,zと公開鍵g1,g2,w=g2x,u=g2y,v=g2zとを生成し、ｒをランダムに選択しh=g2rを計算して利用者装置２０に送る。利用者装置２０は、ｓ，Ｒをランダムに選択し、X=g1m・ψ(u)・ψ(v)s・(ψ(w・h))Rを計算してブラインド署名生成装置１０に送信する。ブラインド署名生成装置１０はＬをランダムに選択し、Y=(X・g1L・z)1/(x+r)を計算して（Ｙ，Ｌ）を利用者装置２０に送る。利用者装置２０はｔをランダムに選択してσ=(Y/g1R)1/t,α=wt-1・ht,β=s+L mod pを計算し、ｍとそのブラインド署名（σ，α，β）とをブラインド署名検証装置３０に送る。ブラインド署名検証装置３０は、σ≠1,α∈G2,e(σ,w・α)=e(g1,g2m・u・vβ)が成立するか否か検証する。
【解決手段】ブラインド署名生成装置１０が、秘密鍵x,y,zと公開鍵g1,g2,w=g2x,u=g2y,v=g2zとを生成し、ｒをランダムに選択しh=g2rを計算して利用者装置２０に送る。利用者装置２０は、ｓ，Ｒをランダムに選択し、X=g1m・ψ(u)・ψ(v)s・(ψ(w・h))Rを計算してブラインド署名生成装置１０に送信する。ブラインド署名生成装置１０はＬをランダムに選択し、Y=(X・g1L・z)1/(x+r)を計算して（Ｙ，Ｌ）を利用者装置２０に送る。利用者装置２０はｔをランダムに選択してσ=(Y/g1R)1/t,α=wt-1・ht,β=s+L mod pを計算し、ｍとそのブラインド署名（σ，α，β）とをブラインド署名検証装置３０に送る。ブラインド署名検証装置３０は、σ≠1,α∈G2,e(σ,w・α)=e(g1,g2m・u・vβ)が成立するか否か検証する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術の応用技術分野に関し、特にブラインド署名技術に関する。
【背景技術】
【０００２】
従来多くのブラインドディジタル署名方式が提案されているが、ほとんどの署名方式（ＲＳＡブラインド署名方式、ＤＳＡブラインド署名方式など（例えば、非特許文献１参照））は、ハッシュ関数を利用することで安全性が保証される。この場合、安全性の根拠はハッシュ値のランダム性に依存することになるが、ハッシュ値が完全にランダムなハッシュ関数は存在しない。
また、ハッシュ関数を利用しないブラインド署名方式としては、Juelsらの方式がある（例えば、非特許文献２参照）。
【非特許文献１】Chaum, D., "Security without Identification: Transaction Systems to Make Big Brother Obsolete", Communications of the ACM, vol.28, No.10, pp.1030-1044 (1985)
【非特許文献２】Juels, A., Luby, M, and Ostrovsky, R., "Security of Blind Digital Signatures, Proceedings of Crypto'97, LNCS 1294, pp.150-164 (1997)
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、Juelsらの方式は、一般的な二者間プロトコルに基づく方式であり、実用上の効率性は全く考慮されていない。そのため、この方式は全く実用性を持たない。
本発明はこのような点に鑑みてなされたものであり、ハッシュ関数に依存することなく、安全性が保証された効率的なブラインド署名を実現することを目的とする。
【課題を解決するための手段】
【０００４】
第１の発明では、まず、ブラインド署名生成装置の秘密鍵生成部が、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、公開鍵生成部が、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成する。そして、ｈ計算部が、ｈ＝ｇ２ｒ（ｒ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、ｈを利用者装置に送信する。
次に、利用者装置の受信部が、ｈと少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｗ，ｕ，ｖとを受信する。そして、利用者装置のＸ計算部が、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍ∈｛０，１，...，ｐ−１｝を署名対象情報とした場合における、Ｘ＝ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ・（ψ（ｗ・ｈ））Ｒ（ｓ，Ｒ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、Ｘをブラインド署名生成装置に送信する。
【０００５】
次に、ブラインド署名生成装置の受信部がＸを受信する。また、ブラインド署名生成装置のＹ計算部が、Ｙ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）（Ｌ,ｚ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、少なくともＹを利用者装置に送信する。
次に、利用者装置の受信部が少なくともＹを受信し、σ計算部が、σ＝（Ｙ／ｇ１Ｒ）１／ｔ（ｔ∈｛０，１，...，ｐ−１｝）を計算し、α計算部が、α＝ｗｔ−１・ｈｔを計算し、送信部が、署名対象情報ｍと、ブラインド署名（σ，α，β）と、をブラインド署名検証装置に送信する。
【０００６】
次に、ブラインド署名検証装置の受信部が、署名対象情報ｍとそのブラインド署名（σ，α，β）とを受信し、ブラインド署名生成装置から送信された公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖを受信する。そして、ブラインド署名検証装置の署名検証部が、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）（β＝ｓ＋Ｌ ｍｏｄ ｐ）が成立するか否かを検証する。
ここで、本発明では、双線形写像を用いることとしため、ハッシュ関数を必要としないブラインド署名を実現できる。また、このブラインド署名の安全性は、Strong Diffile-Hellman問題の求解困難性に基づいており、安全であるといえる。さらに、このブラインド署名の各処理に必要とされる演算量は、広く用いられているＲＳＡ署名などと同程度である。
【０００７】
また、第１の発明において好ましくは、利用者装置の証明結果情報生成部が、当該利用者装置に（ｍ，ｓ，Ｒ）が保持されていることを、少なくともｍを開示することなくブラインド署名生成装置に証明するための証明結果情報を生成し、送信部が、当該証明結果情報をブラインド署名生成装置に送信する。そして、ブラインド署名生成装置の受信部が、この証明結果情報を受信し、証明結果検証部が、証明結果情報を検証する。そして、この証明検証部が証明結果情報を合格と判断した場合にのみ、上述のブラインド署名生成装置のＹ計算部がＹを計算するための処理を実行する。
【０００８】
これにより、利用者装置が署名対象ｍに対応しないＸをブラインド署名生成装置に送信し、不正な或いは誤ったブラインド署名が生成されることを防止できる。
また、第１の発明において好ましくは、利用者装置の乱数生成部が、ａ１，ａ２，ａ３を｛０，１，...，ｐ−１｝からランダムに選択し、Ｗ計算部が、Ｗ＝ｇ１a１・ψ（ｖ）a２・（ψ（ｗ・ｈ））a３（上付き添え字ａ１，ａ２，ａ３は、それぞれａ１，ａ２，ａ３を示す）を計算し、送信部が、Ｗをブラインド署名生成装置に送信する。そして、ブラインド署名生成装置の受信部がＷを受信した後、乱数生成部が、ηを｛０，１，...，ｐ−１｝からランダムに選択し、送信部が、このηを利用者装置に送信する。次に、利用者装置の受信部が、ηを受信し、証明結果情報生成部が、証明結果情報としてｚ１＝ａ１＋η・ｍ ｍｏｄ ｐ，ｚ２＝ａ２＋η・ｓ ｍｏｄ ｐ，ｚ３＝ａ３＋η・Ｒ ｍｏｄ ｐを生成し、送信部が、当該証明結果情報をブラインド署名生成装置に送信する。そして、これに対し、ブラインド署名生成装置の証明結果検証部がｇ１ｚ１・ψ（ｖ）ｚ２・（ψ（ｗ・ｈ））ｚ３≡Ｗ・（Ｘ／ψ（ｕ））η（上付き添え字ｚ１，ｚ２，ｚ３は、それぞれｚ１，ｚ２，ｚ３を示す）が成り立つか否かにより、証明結果情報の検証を行う。
【０００９】
また、第１の発明において好ましくは、写像ψはＧ２からＧ１への同型写像である。
これにより、正確な署名検証が可能になる。
また、第１の発明において好ましくは、ブラインド署名生成装置の秘密鍵生成部が、秘密鍵ｘを生成する際に、秘密鍵ｚ∈｛０，１，...，ｐ−１｝も生成して記憶部に格納するステップをさらに有し、ブラインド署名生成装置の公開鍵生成部が生成する公開鍵はｖ＝ｇ２ｚであり、ブラインド署名生成装置の受信部がＸを受信するステップの後、ブラインド署名生成装置のＹ計算部がＹを計算して記憶部に格納するステップの前に、ブラインド署名生成装置の乱数生成部が、Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップをさらに有し、ブラインド署名生成装置の送信部は、ＹとともにＬをも利用者装置に送信し、利用者装置の受信部は、ＹとともにＬをも受信し、利用者装置の受信部が、ＹとともにＬをも受信するステップの後、利用者装置の送信部が署名対象情報ｍとブラインド署名（σ，α，β）とをブラインド署名検証装置に送信するステップの前に、利用者装置のβ計算部が、β＝ｓ＋Ｌ ｍｏｄ ｐを計算して記憶部に格納するステップをさらに有する。
【００１０】
これにより、署名の安全性がより向上する。
また、第２の発明では、まず、ブラインド署名生成装置の秘密鍵生成部が、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、ブラインド署名生成装置の公開鍵生成部が、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成する。そして、利用者装置の受信部が、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｕ，ｖを受信し、Ｘ計算部が、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝（ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ）ｔ（ｓ，ｔ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、Ｘをブラインド署名生成装置に送信する。
【００１１】
次に、ブラインド署名生成装置の受信部がＸを受信し、Ｙ計算部が、Ｙ＝（Ｘ・（ψ（ｖ））Ｌ）１／（ｘ＋ｒ）（ｒ，Ｌ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、少なくともＹを利用者装置に送信する。
そして、利用者装置の受信部が少なくともＹを受信し、ブラインド署名生成装置から送信された公開鍵ｗを受信し、τ計算部が、τ＝（ｆ・ｔ）−１ｍｏｄ ｐ（ｆ∈｛０，１，...，ｐ−１｝）を計算し、σ計算部が、σ＝Ｙτを計算し、α計算部が、α＝ｗｆ−１・Ｒｆ（Ｒ＝ｇ２ｒ，ｒ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ／ｔ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信する。
【００１２】
次に、ブラインド署名検証装置の受信部が、署名対象情報ｍとブラインド署名（σ，α，β）とを受信し、ブラインド署名生成装置から送信された公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖを受信し、署名検証部が、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証する。
ここで、第２の発明では、双線形写像を用いることとしため、ハッシュ関数を必要としないブラインド署名を実現できる。また、このブラインド署名の安全性は、Strong Diffile-Hellman問題の求解困難性に基づいており、安全であるといえる。さらに、このブラインド署名の各処理に必要とされる演算量は、広く用いられているＲＳＡ署名などと同程度である。
【００１３】
また、第２の発明において好ましくは、利用者装置の証明結果情報生成部が、（ｍ・ｔ ｍｏｄ ｐ，ｔ，ｓ・ｔ ｍｏｄ ｐ）を保持又は算出可能であることを、少なくともｍを開示することなくブラインド署名生成装置に証明するための証明結果情報を生成し、送信部が、証明結果情報をブラインド署名生成装置に送信し、ブラインド署名生成装置の受信部が、証明結果情報を受信し、証明結果検証部が、証明結果情報を検証する。そして、ブラインド署名生成装置のＹ計算部がＹを計算するための処理は、ブラインド署名生成装置の証明検証部が証明結果情報を合格と判断した場合にのみ実行される。
【００１４】
これにより、利用者装置が署名対象ｍに対応しないＸをブラインド署名生成装置に送信し、不正な或いは誤ったブラインド署名が生成されることを防止できる。
また、第２の発明において好ましくは、利用者装置の乱数生成部が、ａ１，ａ２，ａ３を｛０，１，...，ｐ−１｝からランダムに選択し、利用者装置のＷ計算部が、Ｗ＝ｇ１a１・ψ（ｕ）a２・ψ（ｖ）a３（上付き添え字ａ１，ａ２，ａ３は、それぞれａ１，ａ２，ａ３を示す）を計算し、利用者装置の送信部が、Ｗをブラインド署名生成装置に送信する。次に、ブラインド署名生成装置の受信部がＷを受信し、Ｗが受信された後、ブラインド署名生成装置の乱数生成部が、ηを｛０，１，...，ｐ−１｝からランダムに選択し、送信部が、ηを利用者装置に送信し、利用者装置の受信部がηを受信する。そして、証明結果情報は、ｚ１＝ａ１＋η・ｍ・ｔ ｍｏｄ ｐ，ｚ２＝ａ２＋η・ｔ ｍｏｄ ｐ，ｚ３＝ａ３＋η・ｓ・ｔ ｍｏｄ ｐであり、ブラインド署名生成装置の証明結果検証部は、ｇ１ｚ１・ψ（ｕ）ｚ２・ψ（ｖ）ｚ３≡Ｗ・Ｘη（上付き添え字ｚ１，ｚ２，ｚ３は、それぞれｚ１，ｚ２，ｚ３を示す）が成り立つか否かにより、証明結果情報の検証を行う。
【００１５】
また、第２の発明において好ましくは、写像ψはＧ２からＧ１への同型写像である。
これにより、正確な署名検証が可能になる。
また、第２の発明において好ましくは、ブラインド署名生成装置の受信部がＸを受信するステップの後、ブラインド署名生成装置の送信部が少なくともＹを利用者装置に送信するステップの前に、乱数生成部がｒ，Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、Ｒ計算部がＲ＝ｇ２ｒを計算し、送信部が、ＹとともにＲとＬをも利用者装置に送信する。利用者装置の受信部は、ＹとともにＲとＬをも受信し、α計算部は、受信されたＲを用いてα＝ｗｆ−１・Ｒｆを計算する。また、利用者装置の受信部がＹとともにＲとＬをも受信するステップの後、利用者装置の送信部が署名対象情報ｍとブラインド署名（σ，α，β）とをブラインド署名検証装置に送信するステップの前に、利用者装置のβ計算部がβ＝ｓ＋Ｌ／ｔ ｍｏｄ ｐを計算する。
【００１６】
これにより、署名の安全性がより向上する。
【発明の効果】
【００１７】
以上のように、本発明では、ハッシュ関数に依存することなく、安全性が保証された効率的なブラインド署名を実現できる。
【発明を実施するための最良の形態】
【００１８】
第１の実施の形態：
以下、本発明の第１の実施の形態を図面を参照して説明する。
〔双線形写像〕
本発明は、双線形写像を用いる点に特徴がある。まず、本発明で用いる双線形写像の説明を行う。
本発明では、（Ｇ１，Ｇ２）を以下のような性質を持つ双線形群とする。
＜性質１＞Ｇ１とＧ２とは、位数がｐ（ｐは素数）の２つの巡回群である。
【００１９】
＜性質２＞ｇ２は、Ｇ１の生成元であり、ｇ２は、Ｇ２の生成元である。
＜性質３＞ψは、Ｇ２からＧ１への同型写像であり、ψ（ｇ２）＝ｇ１を満たす。
＜性質４＞ｅは、双線形写像であり、ｅ：Ｇ１×Ｇ２→ＧＴで定義される。なお、「×」は直積を示す。また、ＧＴの位数もｐである。つまり、ａ，ｂ∈Ｇ１，ｃ，ｄ∈Ｇ２のとき、以下の関係が成り立つ。
e(a・b,c)=e(a,c)・e(b,c) …(1)
e(a,c・d)=e(a,c)・e(a,d) …(2)
＜性質５＞ｅ，ψ，Ｇ１，Ｇ２，ＧＴの群演算は効率的に計算できる。
【００２０】
なお、上述のような双線形写像ｅを有限体上の楕円曲線を用いて実現する実現例については、文献「Boneh, D. and Franklin, M., "Identity Based Encryption from the Weil Pairing", SIAM J. of Computing, Vol. 32, No.3 pp.586-615, (2003)」などに記載されている。また、上述した記号の意味等については、文献「Boneh, D. and Boyen, X., "Short Signature Without Random Oracles", Proceedings of Crypto'04, LNCS, Springer-Verlag (2004)」とほぼ同様である。
〔構成〕
次に、本形態の構成について説明する。
【００２１】
図１は、本形態におけるブラインド署名生成・検証システムの全体構成を例示したブロック図である。また、図２はブラインド署名生成装置の詳細構成を、図３は利用者装置の詳細構成を、図４はブラインド署名検証装置の詳細構成を、それぞれ例示したブロック図である。以下、これらの図を用いて、本形態の構成を説明する。
＜全体構成＞
図１に例示するように、本形態のブラインド署名生成・検証システム１は、ブラインド署名生成装置１０と、利用者装置２０と、ブラインド署名検証装置３０とを有している。ここで、ブラインド署名生成装置１０と利用者装置２０と、及び利用者装置２０とブラインド署名検証装置３０とは、それぞれネットワークを通じて通信可能に接続されている。
【００２２】
＜ブラインド署名生成装置の構成＞
図１及び図２に例示するように、本形態のブラインド署名生成装置１０は、秘密鍵生成部１０ａと、公開鍵生成部１０ｂと、乱数生成部１０ｃと、ｈ計算部１０ｄと、記憶部１０ｅと、証明結果検証部１０ｆと、Ｙ計算部１０ｇと、送信部１０ｈと、受信部１０ｉと、制御部１０ｊとを有している。
本形態のブラインド署名生成装置１０は、ＣＰＵ（Central Processing Unit）、補助記憶装置、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、入出力インタフェース、ＮＩＣ（Network Interface Card）等から構成される公知のコンピュータにブラインド署名生成プログラムが読み込まれことにより構築されるものである。
【００２３】
すなわち、図１及び図２の鍵生成部１０ａ、公開鍵生成部１０ｂ、乱数生成部１０ｃ、ｈ計算部１０ｄ、証明結果検証部１０ｆ、Ｙ計算部１０ｇ及び制御部１０ｊは、ブラインド署名生成プログラムが読み込まれたＣＰＵに相当する。また、送信部１０ｈ及び受信部１０ｉは、ブラインド署名生成プログラムが読み込まれたＣＰＵ１１の制御のもと通信処理を行うＮＩＣ等に相当する。また、記憶部１０ｅは、補助記憶装置、ＲＡＭ、レジスタ等により構成される。なお、ブラインド署名生成装置１０は、制御部１０ｊの制御のもと各処理を実行する。
【００２４】
＜利用者装置の構成＞
図１及び図３に例示するように、本形態の利用者装置２０は、受信部２０ａと、送信部２０ｂと、乱数生成部２０ｃと、Ｘ計算部２０ｄと、制御部２０ｅと、証明結果情報生成部２０ｆと、σ計算部２０ｇと、α計算部２０ｈと、β計算部２０ｉと、記憶部２０ｊとを有している。また、図３に例示するように、証明結果情報生成部２０ｆは、Ｗ計算部２０ｆａとｚ計算部２０ｆｂを有している。
本形態の利用者装置２０は、前述のような公知のコンピュータに利用者プログラムが読み込まれることにより構成される。すなわち、乱数生成部２０ｃ、Ｘ計算部２０ｄ、制御部２０ｅ、証明結果情報生成部２０ｆ、σ計算部２０ｇ、α計算部２０ｈ及びβ計算部２０ｉは、利用者プログラムが読み込まれたＣＰＵに相当する。また、受信部２０ａ及び送信部２０ｂは、利用者プログラムが読み込まれたＣＰＵの制御のもと通信処理を行うＮＩＣ等に相当する。また、記憶部２０ｊは、補助記憶装置、ＲＡＭ、レジスタ等により構成される。なお、利用者装置２０は、制御部２０ｅの制御のもと各処理を実行する。
【００２５】
＜ブラインド署名検証装置の構成＞
図１及び図４に例示するように、本形態のブラインド署名検証装置３０は、受信部３０ａと、署名検証部３０ｂと、署名検証結果出力部３０ｃと、制御部３０ｄと、記憶部３０ｅとを有している。
本形態のブラインド署名検証装置３０は、前述のような公知のコンピュータにブラインド署名検証プログラムが読み込まれることにより構成される。すなわち、署名検証部３０ｂ及び制御部３０ｄは、ブラインド署名検証プログラムが読み込まれたＣＰＵに相当する。また、受信部３０ａは、ブラインド署名検証プログラムが読み込まれたＣＰＵの制御のもと通信処理を行うＮＩＣ等に相当する。また、署名検証結果出力部３０ｃは、ブラインド署名検証プログラムが読み込まれたＣＰＵの制御のもとデータ出力を行う入出力インタフェース等に相当する。なお、ブラインド署名検証装置３０は、制御部３０ｄの制御のもと各処理を実行する。
【００２６】
〔処理〕
次に、本形態のブラインド署名生成・検証処理について説明する。
図５は、ブラインド署名生成装置１０の処理を説明するためのフローチャートである。また、図６は、利用者装置２０の処理を説明するためのフローチャートである。また、図７は、ブラインド署名検証装置３０の処理を説明するためのフローチャートである。以下、これらの図を用いて本形態のブラインド署名生成・検証処理を説明する。
＜ブラインド署名生成処理＞
本処理の前提として、ブラインド署名生成装置１０の秘密鍵生成部１０ａ、乱数生成部１０ｃ、利用者装置２０の乱数生成部２０ｃ、証明結果情報生成部２０ｆ、β計算部２０ｉが、共通の素数ｐを利用できるように設定しておく。これは、ブラインド署名生成プログラム及び利用者プログラムのコードに素数ｐを記述して実現してもよいし、別途素数ｐのデータをＣＰＵに読み込ませて実現してもよい。また、利用者装置２０の記憶部２０ｊに署名対象情報（例えば文書）ｍ∈｛０，１，...，ｐ−１｝を格納しておく。本形態では、この署名対象情報ｍのブラインド署名を生成する。
【００２７】
本形態では、まず、ブラインド署名生成装置１０（図２）の秘密鍵生成部１０ａが、秘密鍵ｘ，ｙ，ｚ∈｛０，１，...，ｐ−１｝を（例えばランダムに）生成し、当該秘密鍵（ｘ，ｙ，ｚ）を記憶部１０ｅに格納する（図５／ステップＳ１）。なお、ランダムな値の生成には、例えば、公知の擬似乱数生成アルゴリズムを利用するが、入力値や、予め定められた値をランダム（任意）な値として用いてもよい（以下も同様）。
次に、ブラインド署名生成装置１０の公開鍵生成部１０ｂが、記憶部１０ｅから秘密鍵（ｘ，ｙ，ｚ）を読み込み、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ＝ｇ２ｙ，ｖ＝ｇ２ｚを生成し、当該公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を記憶部１０ｅに格納する（ステップＳ２）。
【００２８】
次に、乱数生成部１０ｃが、ｒを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１０ｅに格納する（ステップＳ３）。そして、ｈ計算部１０ｄが、記憶部１０ｅからｒと公開鍵ｇ２とを読み込み、ｈ＝ｇ２ｒを計算し、このｈを記憶部１０ｅに格納する（ステップＳ４）。そして、記憶部１０ｅに格納されたｈが送信部１０ｈに送られ、送信部１０ｈは、ｈを利用者装置２０に送信する（ステップＳ５）。
利用者装置２０（図３）は、受信部２０ａにおいてｈを受信し、記憶部２０ｊに格納する（図６／ステップＳ２１）。次に、乱数生成部２０ｃが、ｓとＲを｛０，１，...，ｐ−１｝からそれぞれランダムに選択して記憶部２０ｊに格納する（ステップＳ２２）。
【００２９】
また、利用者装置２０は、制御部２０ｅの制御のもと、送信部２０ｂからブラインド署名生成装置１０に対して公開鍵の発行要求情報を送信する。これを受けたブラインド署名生成装置１０は、記憶部１０ｅの公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を送信部１０ｈから利用者装置２０に送信し、利用者装置２０は、受信部２０ａでこれを受信し記憶部２０ｊに格納する（ステップＳ２３）。なお、この例の利用者装置２０は公開鍵ｇ２を使用しない。よって、利用者装置２０が公開鍵（ｇ１，ｗ，ｕ，ｖ）のみを取得する構成としてもよい。
【００３０】
次に利用者装置２０のＸ計算部２０ｄが、記憶部２０ｊから公開鍵（ｇ１，ｗ，ｕ，ｖ）と（ｓ，Ｒ）とｈと署名対象情報ｍとを読み込み、
X=g1m・ψ(u)・ψ(v)s・(ψ(w・h))R …(3)
を計算し、その演算結果Ｘを記憶部２０ｊに格納する（ステップＳ２４）。そして、このＸが送信部２０ｂに送られ、送信部２０ｂが、このＸをブラインド署名生成装置１０に送信する（ステップＳ２５）。なお、このＸは、ブラインド署名生成装置１０（図２）の受信部１０ｉで受信され記憶部１０ｅに格納される（図５／ステップＳ６）。
【００３１】
また、利用者装置２０（図３）は、（ｍ，ｓ，Ｒ）を保持していることを、少なくともｍを開示することなく（ｓ及びＲの少なくとも一方も開示しない構成も含む）ブラインド署名生成装置１０に証明する。
［証明の概要］
まず、証明結果情報生成部２０ｆが、当該利用者装置２０の記憶部２０ｊに（ｍ，ｓ，Ｒ）が格納されていることを、少なくともｍを開示することなく（好ましくは、ｍ，ｓ，Ｒを開示することなく）ブラインド署名生成装置１０に証明するための処理を実行し、その証明を行うための証明結果情報を生成して記憶部２０ｊに格納する（図６／ステップＳ２６）。そして、送信部２０ｂが、その証明結果情報をブラインド署名生成装置１０に送信する（ステップＳ２７）。ブラインド署名生成装置１０の受信部１０ｉは、この証明結果情報を受信し、証明結果検証部１０ｆが、この証明結果情報を検証する（図５／ステップＳ７）。そして、証明結果検証部１０ｆが、この証明結果情報を不合格と判断すれば、ブラインド署名生成装置１０の制御部１０ｊは処理をエラー終了させる。一方、証明結果検証部１０ｆが、この証明結果情報を合格と判断すれば、ステップＳ９以降の処理が実行される（ステップＳ８）。
【００３２】
［証明の具体例（証明の一例）］
次に、上記のステップＳ２６，Ｓ２７（図６）及びステップＳ７（図５）の処理の具体例を説明する。なお、本発明は、この具体例には限定されない。
図８は、上記のステップＳ２６，Ｓ２７及びステップＳ７の処理の具体例を説明するためのフローチャートである。以下、このフローチャートに従ってこの具体例の説明を行っていく。
まず、利用者装置２０（図３）の乱数生成部２０ｃが、（ａ１，ａ２，ａ３）を｛０，１，...，ｐ−１｝からランダムに選択して記憶部２０ｊに格納する（ステップＳ５１）。次に、証明結果情報生成部２０ｆのＷ計算部２０ｆａが、記憶部２０ｊから（ａ１，ａ２，ａ３）とｇ１とｖとｗとｈとを読み込み、
W=g1a1・ψ(v)a2・(ψ(w・h))a3 …(4)
を計算し、その演算結果Ｗを記憶部２０ｊに格納する（ステップＳ５２）。次に、記憶部２０ｊに格納されたＷが送信部２０ｂに送られ、送信部２０ｂは、Ｗをブラインド署名生成装置１０に送信する（ステップＳ５３）。
【００３３】
ブラインド署名生成装置１０（図２）の受信部１０ｉはこのＷを受信する（ステップＳ５４）。Ｗが受信された後、乱数生成部１０ｃが、ηを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１０ｅに格納する（ステップＳ５５）。このηは送信部１０ｈに送られ、送信部１０ｈは、このηを利用者装置２０に送信する（ステップＳ５６）。
利用者装置２０（図３）の受信部２０ａは、このηを受信して記憶部２０ｊに格納する（ステップＳ５７）。次に、証明結果情報生成部２０ｆのｚ計算部２０ｆｂが、記憶部２０ｊから（ａ１，ａ２，ａ３）とηとｍと（ｓ，Ｒ）とを読み込み、
z1=a1+η・m mod p
z2=a2+η・s mod p …(5)
z3=a3+η・R mod p
を計算し、その演算結果（ｚ１，ｚ２，ｚ３）を証明結果情報として記憶部２０ｊに格納する（ステップＳ５８）。次に、この証明結果情報（ｚ１，ｚ２，ｚ３）は、送信部２０ｂに送られ、送信部２０ｂは、証明結果情報（ｚ１，ｚ２，ｚ３）をブラインド署名生成装置１０に送信する（ステップＳ５９）。
【００３４】
ブラインド署名生成装置１０（図２）の受信部１０ｉは、この証明結果情報（ｚ１，ｚ２，ｚ３）を受信し、記憶部１０ｅに格納する（ステップＳ６０）。そして、証明結果検証部１０ｆが、記憶部１０ｅから、ｇ１，ｗ，ｕ，ｖ，ｈ，Ｗ，Ｘ，η，（ｚ１，ｚ２，ｚ３）を読み込み、
g1z1・ψ(v)z2・(ψ(w・h))z3≡W・(X/ψ(u))η …(6)
が成り立つか否かにより、証明結果情報の検証を行う（ステップＳ６１）。ここで、式（６）が成立する場合、証明結果検証部１０ｆは、証明結果が正当である旨を出力する（ステップＳ６２）。一方、式（６）が成立しない場合、証明結果検証部１０ｆは、証明結果が不当である旨を出力する（ステップＳ６３）。
【００３５】
そして、上述したステップＳ５１以降の処理を複数回繰り返し、全てのループにおいて証明結果が正当であると出力された場合、証明結果検証部１０ｆは、証明結果情報が合格であると判断し、１度でも証明結果が不当であると出力された場合、証明結果情報が不合格であると判断する（図５／ステップＳ８／［証明の具体例（証明の一例）］の説明終わり）。
証明結果検証部１０ｆが、証明結果情報を合格と判断した場合、ブラインド署名生成装置１０の乱数生成部１０ｃは、Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１０ｅに格納する（ステップＳ９）。次に、Ｙ計算部１０ｇが、記憶部１０ｅからＸ，ｇ１，Ｌ，ｚ，ｘ，ｒを読み込み、
Y=(X・g1L・z)1/(x+r) …(7)
を計算して記憶部１０ｅに格納する（ステップＳ１０）。次に、記憶部１０ｅに格納された（Ｙ，Ｌ）が送信部１０ｈに送られ、送信部１０ｈは、この（Ｙ，Ｌ）を利用者装置２０に送信する（ステップＳ１１）。
【００３６】
利用者装置２０（図３）の受信部２０ａは、この（Ｙ，Ｌ）を受信し、記憶部２０ｊに格納する（図６／ステップＳ２８）。次に、乱数生成部２０ｃが、ｔを｛０，１，...，ｐ−１｝からランダムに選択して記憶部２０ｊに格納する（ステップＳ２９）。そして、σ計算部２０ｇが、記憶部２０ｊからＹとｇ１とＲとｔとを読み込み、
σ=(Y/g1R)1/t …(8)
を計算し、その演算結果σを記憶部２０ｊに格納する（ステップＳ３０）。また、α計算部２０ｈが、記憶部２０ｊからｗとｈとｔとを読み込み、
α=wt-1・ht …(9)
を計算し、その演算結果αを記憶部２０ｊに格納する（ステップＳ３１）。さらに、β計算部２０ｉが、記憶部２０ｊからｓとＬとを読み込み、
β=s+L mod p …(10)
を計算し、その演算結果βを記憶部２０ｊに格納する（ステップＳ３２）。以上のように生成された（σ，α，β）が署名対象情報ｍのブラインド署名となる。そして、記憶部２０ｊに格納された署名対象情報ｍとそのブラインド署名（σ，α，β）とは送信部２０ｂに送られ、送信部２０ｂは、署名対象情報ｍとそのブラインド署名（σ，α，β）とをブラインド署名検証装置３０に送信する（ステップＳ３３）。
【００３７】
＜ブラインド署名検証処理＞
ブラインド署名検証装置（図４）の受信部３０ａは、上記の署名対象情報ｍとそのブラインド署名（σ，α，β）とを受信し、これらを記憶部３０ｅに格納する（ステップＳ４１）。また、受信部３０ａが、ブラインド署名生成装置１０から送信された公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を受信し、記憶部３０ｗに格納する（ステップＳ４２）。なお、ブラインド署名生成装置１０への公開鍵の配送依頼手順は、前述した利用者装置１０の場合と同様であるため説明を省略する。
【００３８】
次に署名検証部３０ｂが、記憶部３０ｅから署名対象情報ｍとそのブラインド署名（σ，α，β）と公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）とを読み込み、
σ≠1, α∈G2, e(σ,w・α)=e(g1,g2m・u・vβ) …(11)
が全て成立するか否かを検証する（ステップＳ４３）。ここで、式（１１）が成立する場合、署名検証部３０ｂは、署名検証が合格である旨の情報を署名検証結果出力部３０ｃに送り、署名検証結果出力部３０ｃは署名検証が合格である旨を出力する（ステップＳ４４）。一方、式（１１）が成立しなかった場合、署名検証部３０ｂは、署名検証が不合格である旨の情報を署名検証結果出力部３０ｃに送り、署名検証結果出力部３０ｃは署名検証が不合格である旨を出力する（ステップＳ４５）。
【００３９】
＜署名検証が正しく行われる理由＞
次に、式（１１）が成立する場合になぜ署名が合格であるといえるかについて説明する。
まず、前述の式（７）に式（３）を代入すると、
Y=(X・g1L・z)1/(x+r)=((g1m・ψ(u)・ψ(v)s・(ψ(w・h))R)・g1L・z)1/(x+r) …(12)
となる。また、前述の＜性質３＞より、ψは、Ｇ２からＧ１への同型写像であり、ψ（ｇ２）＝ｇ１を満たすため、式（１２）は、
Y=g1(m+y+(s+L)・z)/(x+r)・g1R …(13)
と変形できる。
【００４０】
そして、式（１３）と式（１０）により、式（８）は、
σ=(Y/g1R)1/t=g1(m+y+(s+L)・z)/(t・x+t・r)=g1(m+y+β・z)/(t・x+t・r) …(14)
と変形できる。
ここで、δ=(t‐1)・x+t・rとすると、式（１４）は、
σ=g1(m+y+β・z)/(x+((t‐1)・x+t・r))=g1(m+y+β・z)/(x+δ) …(15)
となる。
また、この場合、w=g2x（ステップＳ２），h=g2r（ステップＳ４）より、式（９）は、
α=wt-1・ht=g2(t‐1)・x+t・r=g2δ …(16)
となる。
【００４１】
これらより、式（１１）の左辺は、
e(σ,w・α)=e(g1(m+y+β・z)/(x+δ), g2x+δ) …(17)
と変形できる。さらに、＜性質４＞により、ｅは双線形写像であり、式（２）を満たすことから、式（１７）は、
e(σ,w・α)=e(g1(m+y+β・z)/(x+δ), g2x+δ)
=e(g1(m+y+β・z)/(x+δ), g2)・e(g1(m+y+β・z)/(x+δ), g2)・…・e(g1(m+y+β・z)/(x+δ), g2) …(18)
と変形でき、式（１）を満たすことから、式（１８）は、
e(σ,w・α)=e(g1(m+y+β・z), g2)
=e(g1, g2)・e(g1, g2)・…・e(g1, g2) …(19)
と変形できる。さらに、ｅは式（２）を満たし、u=g2y, v=g2z（ステップＳ２）より、式（１９）は、
e(σ,w・α)=e(g1, g2(m+y+β・z))
=e(g1, g2mu・vβ)=式（１１）の右辺
となる。
【００４２】
〔本形態の効果〕
本形態のブラインド署名には、ハッシュ関数が使われていない。また、本形態のブラインド署名生成処理及びブラインド署名検証処理の安全性はStrong Diffile-Hellman問題の求解困難性に基づいており、安全であるといえる。さらに、本形態のブラインド署名生成処理及びブラインド署名検証処理の処理速度は、現在最も広く使われているＲＳＡ署名などと同程度であり、高い実用性を持つ。
例えば、双線形写像の典型的な実現例では、Ｇ１＝Ｇ２となるような楕円曲線を用い、この楕円曲線のパラメータを２００ビット程度にすることが可能である。このときのブラインド署名（σ，α，β）のデータサイズは２００ビット程度（つまり、σ，α，β合計で６００ビット程度）となり、ＲＳＡ署名のデータサイズよりも小さくなる。
【００４３】
〔変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、ステップＳ２６，Ｓ２７（図６）及びステップＳ７（図５）において、利用者装置２０が、（ｍ，ｓ，Ｒ）を保持していることを、少なくともｍを開示することなく、ブラインド署名生成装置１０に証明し、この証明が成功した場合にのみ、ステップＳ９（図５）以降の処理を実行することとした。しかし、この証明処理を行うことなく、ステップＳ９（図５）以降の処理を実行することとしてもよい。
【００４４】
また、本形態では、ψをＧ２からＧ１への同型写像とした。しかし、ψをＧ２からＧ１への準同型写像とした構成であってもよい。
また、本形態では、ブラインド署名生成装置１０が秘密鍵ｘ，ｙ，ｚを生成し、ｕ＝ｇ２ｙによって公開鍵ｕを生成することとした。しかし、秘密鍵ｙを生成せず、公開鍵ｕを巡回群Ｇ２から任意に選択する構成でもよい。
また、本形態では、ブラインド署名生成装置１０がＬを｛０，１，．．．，ｐ−１｝からランダムに選択し、これを利用者装置２０に送信することとした。しかし、ブラインド署名生成装置１０がＬの選択や送信を行わない構成としてもよい。この場合、ブラインド署名生成装置１０が、利用者装置２０との間で既に共有しているＬ（０も含む）を用いてＹ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）を計算し、利用者装置２０がこのＬを用いてβを計算してもよい。ここでＬ＝０であるなら秘密鍵ｚは不要となり、ブラインド署名生成装置１０が、秘密鍵ｚを生成せず、公開鍵ｖを巡回群Ｇ２から任意に選択する構成を採ることもできる。また、この場合、利用者装置２０はｓをそのままβとして用いることもできる。
【００４５】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
第２の実施の形態：
次に、本発明の第２の実施の形態を図面を参照して説明する。なお、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する部分については説明を簡略化する。
【００４６】
〔構成〕
次に、本形態の構成について説明する。
図９は、本形態におけるブラインド署名生成・検証システムの全体構成を例示したブロック図である。また、図１０はブラインド署名生成装置の詳細構成を、図１１は利用者装置の詳細構成を、それぞれ例示したブロック図である。なお、ブラインド署名検証装置３０は、第１の実施の形態のものと同じである。以下、これらの図を用いて、本形態の構成を説明する。
【００４７】
＜全体構成＞
図９に例示するように、本形態のブラインド署名生成・検証システム１０１は、ブラインド署名生成装置１１０と、利用者装置１２０と、ブラインド署名検証装置３０とを有している。ここで、ブラインド署名生成装置１１０と利用者装置１２０と、及び利用者装置１２０とブラインド署名検証装置３０とは、それぞれネットワークを通じて通信可能に接続されている。
＜ブラインド署名生成装置の構成＞
図９及び図１０に例示するように、本形態のブラインド署名生成装置１１０は、秘密鍵生成部１１０ａと、公開鍵生成部１１０ｂと、乱数生成部１１０ｃと、Ｒ計算部１１０ｄ、記憶部１１０ｅと、証明結果検証部１１０ｆと、Ｙ計算部１１０ｇと、送信部１１０ｈと、受信部１１０ｉと、制御部１１０ｊとを有している。
【００４８】
本形態のブラインド署名生成装置１１０は、第１の実施の形態と同様、公知のコンピュータにブラインド署名生成プログラムが読み込まれことにより構築される。
すなわち、図９及び図１０の鍵生成部１１０ａ、公開鍵生成部１１０ｂ、乱数生成部１１０ｃ、Ｒ計算部１１０ｄ、証明結果検証部１１０ｆ、Ｙ計算部１１０ｇ及び制御部１１０ｊは、ブラインド署名生成プログラムが読み込まれたＣＰＵに相当する。また、送信部１１０ｈ及び受信部１１０ｉは、ブラインド署名生成プログラムが読み込まれたＣＰＵの制御のもと通信処理を行うＮＩＣ等に相当する。また、記憶部１１０ｅは、補助記憶装置、ＲＡＭ、レジスタ等により構成される。なお、ブラインド署名生成装置１１０は、制御部１１０ｊの制御のもと各処理を実行する。
【００４９】
＜利用者装置の構成＞
図９及び図１１に例示するように、本形態の利用者装置１２０は、受信部１２０ａと、送信部１２０ｂと、乱数生成部１２０ｃと、Ｘ計算部１２０ｄと、制御部１２０ｅと、証明結果情報生成部１２０ｆと、σ計算部１２０ｇと、α計算部１２０ｈと、β計算部１２０ｉと、記憶部１２０ｊと、τ計算部１２０ｋとを有している。また、図１１に例示するように、証明結果情報生成部１２０ｆは、Ｗ計算部１２０ｆａとｚ計算部１２０ｆｂを有している。
【００５０】
本形態の利用者装置１２０は、第１の実施の形態と同様、公知のコンピュータに利用者プログラムが読み込まれることにより構成される。すなわち、乱数生成部１２０ｃ、Ｘ計算部１２０ｄ、制御部１２０ｅ、証明結果情報生成部１２０ｆ、σ計算部１２０ｇ、α計算部１２０ｈ、β計算部１２０ｉ及びτ計算部１２０ｋは、利用者プログラムが読み込まれたＣＰＵに相当する。また、受信部１２０ａ及び送信部１２０ｂは、利用者プログラムが読み込まれたＣＰＵの制御のもと通信処理を行うＮＩＣ等に相当する。また、記憶部１２０ｊは、補助記憶装置、ＲＡＭ、レジスタ等により構成される。なお、利用者装置１２０は、制御部１２０ｅの制御のもと各処理を実行する。
【００５１】
＜ブラインド署名検証装置の構成＞
第１の実施の形態で説明した通りである。ここでは説明を省略する。
〔処理〕
次に、本形態のブラインド署名生成処理について説明する。
図１２は、ブラインド署名生成装置１１０の処理を説明するためのフローチャートである。また、図１３は、利用者装置２０の処理を説明するためのフローチャートである。以下、これらの図を用いて本形態のブラインド署名生成処理を説明する。なお、署名検証処理については、第１の実施の形態と同じであるため説明を省略する。
【００５２】
＜ブラインド署名生成処理＞
本処理の前提として、ブラインド署名生成装置１１０の秘密鍵生成部１１０ａ、乱数生成部１１０ｃ、利用者装置１２０の乱数生成部１２０ｃ、証明結果情報生成部１２０ｆ、β計算部１２０ｉ，τ計算部１２０ｋが、共通の素数ｐを利用できるように設定しておく。これは、ブラインド署名生成プログラム及び利用者プログラムのコードに素数ｐを記述して実現してもよいし、別途素数ｐのデータをＣＰＵに読み込ませて実現してもよい。また、利用者装置１２０の記憶部１２０ｊに署名対象情報（例えば文書）ｍ∈｛０，１，．．．，ｐ−１｝を格納しておく。本形態では、この署名対象情報ｍのブラインド署名を生成する。
【００５３】
本形態では、まず、ブラインド署名生成装置１１０（図１０）の秘密鍵生成部１１０ａが、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を（例えばランダムに）生成し、当該秘密鍵ｘを記憶部１１０ｅに格納する（図１２／ステップＳ１０１）。
次に、ブラインド署名生成装置１１０の公開鍵生成部１１０ｂが、記憶部１１０ｅから秘密鍵ｘを読み込み、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、当該公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を記憶部１１０ｅに格納する（ステップＳ１０２）。
【００５４】
次に、利用者装置１２０（図１１）の乱数生成部１２０ｃが、ｓとｔを｛０，１，...，ｐ−１｝からそれぞれランダムに選択して記憶部１２０ｊに格納する（ステップＳ１２１）。
また、利用者装置１２０は、制御部１２０ｅの制御のもと、送信部１２０ｂからブラインド署名生成装置１１０に対して公開鍵の発行要求情報を送信する。これを受けたブラインド署名生成装置１１０は、記憶部１１０ｅの公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を送信部１１０ｈから利用者装置１２０に送信し、利用者装置１２０は、受信部１２０ａでこれを受信し記憶部１２０ｊに格納する（ステップＳ１２２）。なお、この例の利用者装置１２０は公開鍵ｇ２を使用しない。よって、利用者装置１２０が公開鍵（ｇ１，ｗ，ｕ，ｖ）のみを取得する構成としてもよい。
【００５５】
次に利用者装置１２０のＸ計算部１２０ｄが、記憶部１２０ｊから公開鍵（ｇ１，ｗ，ｕ，ｖ）と（ｓ，ｔ）と署名対象情報ｍとを読み込み、
X=(g1m・ψ(u)・ψ(v)s)t …(20)
を計算し、その演算結果Ｘを記憶部１２０ｊに格納する（ステップＳ１２３）。
そして、このＸが送信部１２０ｂに送られ、送信部１２０ｂが、このＸをブラインド署名生成装置１１０に送信する（ステップＳ１２４）。なお、このＸは、ブラインド署名生成装置１１０（図１０）の受信部１１０ｉで受信され、記憶部１１０ｅに格納される（図１２／ステップＳ１０３）。
【００５６】
また、利用者装置１２０（図１１）は、（m・ｔ ｍｏｄ p，t，s・ｔ mod p）を保持或いは算出可能である旨を、少なくともｍを開示することなく（好ましくは、ｍ，ｓ，ｔを開示することなく）ブラインド署名生成装置１１０に証明する。
［証明の概要］
まず、証明結果情報生成部１２０ｆが、（m・ｔ ｍｏｄ p，t，s・ｔ mod p）を保持或いは算出可能である旨を、少なくともｍを開示することなく（好ましくは、ｍ，ｓ，ｔを開示することなく）ブラインド署名生成装置１１０に証明するための処理を実行し、その証明を行うための証明結果情報を生成して記憶部１２０ｊに格納する（図１３／ステップＳ１２５）。そして、送信部１２０ｂが、その証明結果情報をブラインド署名生成装置１１０に送信する（ステップＳ１２６）。ブラインド署名生成装置１１０の受信部１１０ｉは、この証明結果情報を受信し、証明結果検証部１１０ｆが、この証明結果情報を検証する（図１２／ステップＳ１０４）。そして、証明結果検証部１１０ｆが、この証明結果情報を不合格と判断すれば、ブラインド署名生成装置１１０の制御部１１０ｊは処理をエラー終了させる。一方、証明結果検証部１１０ｆが、この証明結果情報を合格と判断すれば、ステップＳ１０６以降の処理が実行される（ステップＳ１０５）。
【００５７】
［証明の具体例（証明の一例）］
次に、上記のステップＳ１２５，Ｓ１２６（図１３）及びステップＳ１０４（図１２）の処理の具体例を説明する。なお、本発明は、この具体例には限定されない。
図１４は、上記のステップＳ１２５，Ｓ１２６及びステップＳ１０４の処理の具体例を説明するためのフローチャートである。以下、このフローチャートに従ってこの具体例の説明を行っていく。
まず、利用者装置１２０（図１１）の乱数生成部１２０ｃが、（ａ１，ａ２，ａ３）を｛０，１，...，ｐ−１｝からランダムに選択して記憶部１２０ｊに格納する（ステップＳ１５１）。次に、証明結果情報生成部１２０ｆのＷ計算部１２０ｆａが、記憶部１２０ｊから（ａ１，ａ２，ａ３）とｇ１とｕとｖとを読み込み、
Ｗ＝ｇ１a１・ψ（ｕ）a２・ψ（ｖ）a３ …(21)
を計算し、その演算結果Ｗを記憶部１２０ｊに格納する（ステップＳ１５２）。次に、記憶部１２０ｊに格納されたＷが送信部１２０ｂに送られ、送信部１２０ｂは、Ｗをブラインド署名生成装置１１０に送信する（ステップＳ１５３）。
【００５８】
ブラインド署名生成装置１１０（図１０）の受信部１１０ｉはこのＷを受信する（ステップＳ１５４）。Ｗが受信された後、乱数生成部１１０ｃが、ηを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１１０ｅに格納する（ステップＳ１５５）。このηは送信部１１０ｈに送られ、送信部１１０ｈは、このηを利用者装置１２０に送信する（ステップＳ１５６）。
利用者装置１２０（図１１）の受信部１２０ａは、このηを受信して記憶部１２０ｊに格納する（ステップＳ１５７）。次に、証明結果情報生成部１２０ｆのｚ計算部１２０ｆｂが、記憶部１２０ｊから（ａ１，ａ２，ａ３）とηとｍとＲとを読み込み、
z1=a1+η・m・t mod p
z2=a2+η・t mod p …(22)
z3=a3+η・s・t mod p
を計算し、その演算結果（ｚ１，ｚ２，ｚ３）を証明結果情報として記憶部１２０ｊに格納する（ステップＳ１５８）。次に、この証明結果情報（ｚ１，ｚ２，ｚ３）は、送信部１２０ｂに送られ、送信部１２０ｂは、証明結果情報（ｚ１，ｚ２，ｚ３）をブラインド署名生成装置１１０に送信する（ステップＳ１５９）。
【００５９】
ブラインド署名生成装置１１０（図１０）の受信部１１０ｉは、この証明結果情報（ｚ１，ｚ２，ｚ３）を受信し、記憶部１１０ｅに格納する（ステップＳ１６０）。そして、証明結果検証部１１０ｆが、記憶部１１０ｅから、ｇ１，ｕ，ｖ，Ｗ，Ｘ，η，（ｚ１，ｚ２，ｚ３）を読み込み、
g1z1・ψ(u)z2・ψ(v)z3≡W・(X)η …(23）
が成り立つか否かにより、証明結果情報の検証を行う（ステップＳ１６１）。ここで、式（２３）が成立する場合、証明結果検証部１１０ｆは、証明結果が正当である旨を出力する（ステップＳ１６２）。一方、式（２３）が成立しない場合、証明結果検証部１１０ｆは、証明結果が不当である旨を出力する（ステップＳ１６３）。
【００６０】
そして、上述したステップＳ１５１以降の処理を複数回繰り返し、全てのループにおいて証明結果が正当であると出力された場合、証明結果検証部１１０ｆは、証明結果情報が合格であると判断し、１度でも証明結果が不当であると出力された場合、証明結果情報が不合格であると判断する（図１２／ステップＳ１０５／［証明の具体例（証明の一例）］の説明終わり）。
証明結果検証部１１０ｆが、証明結果情報を合格と判断した場合、ブラインド署名生成装置１１０の乱数生成部１１０ｃは、ｒ，Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１１０ｅに格納する（ステップＳ１０６）。次に、Ｙ計算部１１０ｇが、記憶部１１０ｅからＸ，Ｌ，ｖ，ｘ，ｒを読み込み、
Y=(X・ψ(v)L)1/(x+r) …(24）
を計算して記憶部１１０ｅに格納する（ステップＳ１０７）。
【００６１】
また、Ｒ計算部１１０ｄが、記憶部１１０ｅからｇ２，ｒを読み込み、
R=g2r …(25）
を計算して記憶部１１０ｅに格納する（ステップＳ１０８）。
次に、記憶部１１０ｅに格納された（Ｙ，Ｒ，Ｌ）が送信部１１０ｈに送られ、送信部１１０ｈは、この（Ｙ，Ｒ，Ｌ）を利用者装置１２０に送信する（ステップＳ１０９）。利用者装置１２０（図１１）の受信部１２０ａは、この（Ｙ，Ｒ，Ｌ）を受信し、記憶部１２０ｊに格納する（図１３／ステップＳ１２７）。次に、乱数生成部１２０ｃが、ｆを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１２０ｊに格納する（ステップＳ１２８）。そして、τ計算部１２０ｋが、記憶部１２０ｊからｆとｔとを読み込み、
τ=(f・t)-1mod p …(26）
を計算し、その演算結果τを記憶部１２０ｊに格納する（ステップＳ１２９）。また、σ計算部１２０ｇが、記憶部１２０ｊからＹとτとを読み込み、
σ=Yτ …(27)
を計算し、その演算結果σを記憶部１２０ｊに格納する（ステップＳ１３０）。また、α計算部１２０ｈが、記憶部１２０ｊからｗとｈとｔとを読み込み、
α=wf-1・Rf …(28)
を計算し、その演算結果αを記憶部１２０ｊに格納する（ステップＳ１３１）。さらに、β計算部１２０ｉが、記憶部１２０ｊからｓとＬとｔとを読み込み、
β=s+L/t mod p …(29)
を計算し、その演算結果βを記憶部１２０ｊに格納する（ステップＳ１３２）。以上のように生成された（σ，α，β）が署名対象情報ｍのブラインド署名となる。そして、記憶部１２０ｊに格納された署名対象情報ｍとそのブラインド署名（σ，α，β）とは送信部１２０ｂに送られ、送信部１２０ｂは、署名対象情報ｍとそのブラインド署名（σ，α，β）とをブラインド署名検証装置１３０に送信する（ステップＳ１３３）。
【００６２】
＜ブラインド署名検証処理＞
本形態のブラインド署名検証処理でも、第１の実施の形態と同じく、
σ≠1, α∈G2, e(σ,w・α)=e(g1,g2m・u・vβ) …(30)
が成立する場合に署名が合格であると判断する。
＜署名検証が正しく行われる理由＞
次に、式（３０）が成立する場合になぜ署名が合格であるといえるかについて説明する。
【００６３】
まず、前述の式（２４）に式（２０）を代入すると、
Y=(X・ψ(v)L)1/(x+r)=((g1m・ψ(u)・ψ(v)s)t・ψ(v)L)1/(x+r)
=(g1m・ψ(u)・ψ(v)s+L/t)t/(x+r) …(31)
となる。これと式（２６）を式（２７）に代入すると、
σ=Yτ=Y1/(f・t)=(g1m・ψ(u)・ψ(v)s+L/t)1/(f・x+f・r) …(32)
となる。そして、式（３２）に式（２９）を代入し、さらに、δ=(f‐1)x+f・r mod pとすると、
σ=(g1m・ψ(u)・ψ(v)β)1/(x+(f−1)x+f・r)=(g1m・ψ(u)・ψ(v)β)1/(x+δ) …(33)
となる。また、w=g2xと式（２５）とを式（２８）に代入し、上記のδを用いて表現すると、
α=wf-1・Rf=g2f-1+r=g2(f‐1)x+f・r)=g2δ …(34)
となる。
【００６４】
これらより、式（１１）の左辺は、
e(σ,w・α)=e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2x+δ） …(35)
と変形できる。さらに、＜性質４＞により、ｅは双線形写像であり、式（２）を満たすことから、式（３５）は、
e(σ,w・α)=e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2x+δ）=e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2）・e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2）・…・e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2） …(36)
と変形でき、式（１）を満たすことから、式（３６）は、
e(σ,w・α)=e(g1m・ψ(u)・ψ(v)β，g2） …(37)
と変形できる。また、ｕ，ｖ∈Ｇ２でありu=g2y, v=g2zと書ける（ｙ，ｚ∈｛０，１，...，ｐ−１｝）ため、式（３７）は、
e(σ,w・α)=e(g1m・ψ(g2y)・ψ(g2z)β，g2） …(37)
と書ける。また、前述の＜性質３＞より、ψは、Ｇ２からＧ１への同型写像であり、さらにψ（ｇ２）＝ｇ１を満たすため、式（３７）は、
e(σ,w・α)=e(g1m・ψ(g2y)・ψ(g2z)β，g2）=e(g1(m+y+β・z), g2) …(38)
と変形できる。さらに、式（１）を満たすことから、式（３８）は、
e(σ,w・α)=e(g1, g2)・e(g1, g2)・…・e(g1, g2) …(39)
と変形でき、式（２）を満たすことから、式（３９）は、
e(σ,w・α)=e(g1, g2(m+y+β・z)) …(40)
と変形できる。そして、u=g2y, v=g2zとおいているのだから、式（４０）は、
e(σ,w・α)=e(g1, g2mu・vβ)=式（３０）の右辺
となる。
【００６５】
〔本形態の効果〕
本形態のブラインド署名には、ハッシュ関数が使われていない。また、本形態のブラインド署名生成処理及びブラインド署名検証処理の安全性はStrong Diffile-Hellman問題の求解困難性に基づいており、安全であるといえる。さらに、本形態のブラインド署名生成処理及びブラインド署名検証処理の処理速度は、現在最も広く使われているＲＳＡ署名などと同程度であり、高い実用性を持つ。
〔変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、ステップＳ１２５，Ｓ１２６（図１３）及びステップＳ１０４（図１２）において、利用者装置１２０が、（m・ｔ ｍｏｄ p，t，s・ｔ mod p）を保持又は算出可能である旨を、少なくともｍを開示することなく、ブラインド署名生成装置１１０に証明し、この証明が成功した場合にのみ、ステップＳ１０６（図１２）以降の処理を実行することとした。しかし、この証明処理を行うことなく、ステップＳ１０６（図１２）以降の処理を実行することとしてもよい。
【００６６】
また、本形態では、ψをＧ２からＧ１への同型写像とした。しかし、ψをＧ２からＧ１への準同型写像とした構成であってもよい。
また、本形態では、ブラインド署名生成装置１１０がｒ，Ｌを｛０，１，．．．，ｐ−１｝からランダムに選択し、Ｒ＝ｇ２ｒを算出し、ＹとともにＬとＲを利用者装置１２０に送信することとした。しかし、ブラインド署名生成装置１１０がＲやＬの選択・算出・送信を行わない構成としてもよい。この場合、例えば、ブラインド署名生成装置１１０と利用者装置１２０とは事前にｒ，Ｌを共用しているものとし、ブラインド署名生成装置１１０は、これらを用いてＹ＝（Ｘ・ψ（ｖ）Ｌ）１／（ｘ＋ｒ）を計算し、利用者装置１２０は、これらｒ，Ｌをを用いて、Ｒ＝ｇ２ｒ、α＝ｗｆ−１・Ｒｆ及びβ＝ｓ＋Ｌ／ｔ ｍｏｄ ｐを計算する。
【００６７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、各実施の形態の処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７０】
本発明の産業上の利用分野としては、例えば、電子現金や電子投票の分野などを例示できる。
【図面の簡単な説明】
【００７１】
【図１】図１は、第１の実施の形態におけるブラインド署名生成・検証システムの全体構成を例示したブロック図である。
【図２】図２は、第１の実施の形態におけるブラインド署名生成装置の詳細構成を例示したブロック図である。
【図３】図３は、第１の実施の形態における利用者装置の詳細構成を例示したブロック図である。
【図４】図４は、第１，２の実施の形態におけるブラインド署名検証装置の詳細構成を例示したブロック図である。
【図５】図５は、第１の実施の形態におけるブラインド署名生成装置の処理を説明するためのフローチャートである。
【図６】図６は、第１の実施の形態における利用者装置の処理を説明するためのフローチャートである。
【図７】図７は、第１，２の実施の形態におけるブラインド署名検証装置の処理を説明するためのフローチャートである。
【図８】図８は、ステップＳ２６，Ｓ２７及びステップＳ７の処理の具体例を説明するためのフローチャートである。
【図９】図９は、第２の実施の形態におけるブラインド署名生成・検証システムの全体構成を例示したブロック図である。
【図１０】図１０は、第２の実施の形態におけるブラインド署名生成装置の詳細構成を例示したブロック図である。
【図１１】図１１は、第２の実施の形態における利用者装置の詳細構成を例示したブロック図である。
【図１２】図１２は、第２の実施の形態におけるブラインド署名生成装置の処理を説明するためのフローチャートである。
【図１３】図１３は、第２の実施の形態における利用者装置の処理を説明するためのフローチャートである。
【図１４】図１４は、Ｓ１２５，Ｓ１２６及びステップＳ１０４の処理の具体例を説明するためのフローチャートである。
【符号の説明】
【００７２】
１，１０１ ブラインド署名生成・検証システム
１０，１１０ ブラインド署名生成装置
２０，１２０ 利用者装置
３０ ブラインド署名検証装置
【技術分野】
【０００１】
本発明は、暗号技術の応用技術分野に関し、特にブラインド署名技術に関する。
【背景技術】
【０００２】
従来多くのブラインドディジタル署名方式が提案されているが、ほとんどの署名方式（ＲＳＡブラインド署名方式、ＤＳＡブラインド署名方式など（例えば、非特許文献１参照））は、ハッシュ関数を利用することで安全性が保証される。この場合、安全性の根拠はハッシュ値のランダム性に依存することになるが、ハッシュ値が完全にランダムなハッシュ関数は存在しない。
また、ハッシュ関数を利用しないブラインド署名方式としては、Juelsらの方式がある（例えば、非特許文献２参照）。
【非特許文献１】Chaum, D., "Security without Identification: Transaction Systems to Make Big Brother Obsolete", Communications of the ACM, vol.28, No.10, pp.1030-1044 (1985)
【非特許文献２】Juels, A., Luby, M, and Ostrovsky, R., "Security of Blind Digital Signatures, Proceedings of Crypto'97, LNCS 1294, pp.150-164 (1997)
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、Juelsらの方式は、一般的な二者間プロトコルに基づく方式であり、実用上の効率性は全く考慮されていない。そのため、この方式は全く実用性を持たない。
本発明はこのような点に鑑みてなされたものであり、ハッシュ関数に依存することなく、安全性が保証された効率的なブラインド署名を実現することを目的とする。
【課題を解決するための手段】
【０００４】
第１の発明では、まず、ブラインド署名生成装置の秘密鍵生成部が、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、公開鍵生成部が、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成する。そして、ｈ計算部が、ｈ＝ｇ２ｒ（ｒ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、ｈを利用者装置に送信する。
次に、利用者装置の受信部が、ｈと少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｗ，ｕ，ｖとを受信する。そして、利用者装置のＸ計算部が、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍ∈｛０，１，...，ｐ−１｝を署名対象情報とした場合における、Ｘ＝ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ・（ψ（ｗ・ｈ））Ｒ（ｓ，Ｒ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、Ｘをブラインド署名生成装置に送信する。
【０００５】
次に、ブラインド署名生成装置の受信部がＸを受信する。また、ブラインド署名生成装置のＹ計算部が、Ｙ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）（Ｌ,ｚ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、少なくともＹを利用者装置に送信する。
次に、利用者装置の受信部が少なくともＹを受信し、σ計算部が、σ＝（Ｙ／ｇ１Ｒ）１／ｔ（ｔ∈｛０，１，...，ｐ−１｝）を計算し、α計算部が、α＝ｗｔ−１・ｈｔを計算し、送信部が、署名対象情報ｍと、ブラインド署名（σ，α，β）と、をブラインド署名検証装置に送信する。
【０００６】
次に、ブラインド署名検証装置の受信部が、署名対象情報ｍとそのブラインド署名（σ，α，β）とを受信し、ブラインド署名生成装置から送信された公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖを受信する。そして、ブラインド署名検証装置の署名検証部が、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）（β＝ｓ＋Ｌ ｍｏｄ ｐ）が成立するか否かを検証する。
ここで、本発明では、双線形写像を用いることとしため、ハッシュ関数を必要としないブラインド署名を実現できる。また、このブラインド署名の安全性は、Strong Diffile-Hellman問題の求解困難性に基づいており、安全であるといえる。さらに、このブラインド署名の各処理に必要とされる演算量は、広く用いられているＲＳＡ署名などと同程度である。
【０００７】
また、第１の発明において好ましくは、利用者装置の証明結果情報生成部が、当該利用者装置に（ｍ，ｓ，Ｒ）が保持されていることを、少なくともｍを開示することなくブラインド署名生成装置に証明するための証明結果情報を生成し、送信部が、当該証明結果情報をブラインド署名生成装置に送信する。そして、ブラインド署名生成装置の受信部が、この証明結果情報を受信し、証明結果検証部が、証明結果情報を検証する。そして、この証明検証部が証明結果情報を合格と判断した場合にのみ、上述のブラインド署名生成装置のＹ計算部がＹを計算するための処理を実行する。
【０００８】
これにより、利用者装置が署名対象ｍに対応しないＸをブラインド署名生成装置に送信し、不正な或いは誤ったブラインド署名が生成されることを防止できる。
また、第１の発明において好ましくは、利用者装置の乱数生成部が、ａ１，ａ２，ａ３を｛０，１，...，ｐ−１｝からランダムに選択し、Ｗ計算部が、Ｗ＝ｇ１a１・ψ（ｖ）a２・（ψ（ｗ・ｈ））a３（上付き添え字ａ１，ａ２，ａ３は、それぞれａ１，ａ２，ａ３を示す）を計算し、送信部が、Ｗをブラインド署名生成装置に送信する。そして、ブラインド署名生成装置の受信部がＷを受信した後、乱数生成部が、ηを｛０，１，...，ｐ−１｝からランダムに選択し、送信部が、このηを利用者装置に送信する。次に、利用者装置の受信部が、ηを受信し、証明結果情報生成部が、証明結果情報としてｚ１＝ａ１＋η・ｍ ｍｏｄ ｐ，ｚ２＝ａ２＋η・ｓ ｍｏｄ ｐ，ｚ３＝ａ３＋η・Ｒ ｍｏｄ ｐを生成し、送信部が、当該証明結果情報をブラインド署名生成装置に送信する。そして、これに対し、ブラインド署名生成装置の証明結果検証部がｇ１ｚ１・ψ（ｖ）ｚ２・（ψ（ｗ・ｈ））ｚ３≡Ｗ・（Ｘ／ψ（ｕ））η（上付き添え字ｚ１，ｚ２，ｚ３は、それぞれｚ１，ｚ２，ｚ３を示す）が成り立つか否かにより、証明結果情報の検証を行う。
【０００９】
また、第１の発明において好ましくは、写像ψはＧ２からＧ１への同型写像である。
これにより、正確な署名検証が可能になる。
また、第１の発明において好ましくは、ブラインド署名生成装置の秘密鍵生成部が、秘密鍵ｘを生成する際に、秘密鍵ｚ∈｛０，１，...，ｐ−１｝も生成して記憶部に格納するステップをさらに有し、ブラインド署名生成装置の公開鍵生成部が生成する公開鍵はｖ＝ｇ２ｚであり、ブラインド署名生成装置の受信部がＸを受信するステップの後、ブラインド署名生成装置のＹ計算部がＹを計算して記憶部に格納するステップの前に、ブラインド署名生成装置の乱数生成部が、Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップをさらに有し、ブラインド署名生成装置の送信部は、ＹとともにＬをも利用者装置に送信し、利用者装置の受信部は、ＹとともにＬをも受信し、利用者装置の受信部が、ＹとともにＬをも受信するステップの後、利用者装置の送信部が署名対象情報ｍとブラインド署名（σ，α，β）とをブラインド署名検証装置に送信するステップの前に、利用者装置のβ計算部が、β＝ｓ＋Ｌ ｍｏｄ ｐを計算して記憶部に格納するステップをさらに有する。
【００１０】
これにより、署名の安全性がより向上する。
また、第２の発明では、まず、ブラインド署名生成装置の秘密鍵生成部が、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、ブラインド署名生成装置の公開鍵生成部が、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成する。そして、利用者装置の受信部が、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｕ，ｖを受信し、Ｘ計算部が、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝（ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ）ｔ（ｓ，ｔ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、Ｘをブラインド署名生成装置に送信する。
【００１１】
次に、ブラインド署名生成装置の受信部がＸを受信し、Ｙ計算部が、Ｙ＝（Ｘ・（ψ（ｖ））Ｌ）１／（ｘ＋ｒ）（ｒ，Ｌ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、少なくともＹを利用者装置に送信する。
そして、利用者装置の受信部が少なくともＹを受信し、ブラインド署名生成装置から送信された公開鍵ｗを受信し、τ計算部が、τ＝（ｆ・ｔ）−１ｍｏｄ ｐ（ｆ∈｛０，１，...，ｐ−１｝）を計算し、σ計算部が、σ＝Ｙτを計算し、α計算部が、α＝ｗｆ−１・Ｒｆ（Ｒ＝ｇ２ｒ，ｒ∈｛０，１，...，ｐ−１｝）を計算し、送信部が、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ／ｔ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信する。
【００１２】
次に、ブラインド署名検証装置の受信部が、署名対象情報ｍとブラインド署名（σ，α，β）とを受信し、ブラインド署名生成装置から送信された公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖを受信し、署名検証部が、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証する。
ここで、第２の発明では、双線形写像を用いることとしため、ハッシュ関数を必要としないブラインド署名を実現できる。また、このブラインド署名の安全性は、Strong Diffile-Hellman問題の求解困難性に基づいており、安全であるといえる。さらに、このブラインド署名の各処理に必要とされる演算量は、広く用いられているＲＳＡ署名などと同程度である。
【００１３】
また、第２の発明において好ましくは、利用者装置の証明結果情報生成部が、（ｍ・ｔ ｍｏｄ ｐ，ｔ，ｓ・ｔ ｍｏｄ ｐ）を保持又は算出可能であることを、少なくともｍを開示することなくブラインド署名生成装置に証明するための証明結果情報を生成し、送信部が、証明結果情報をブラインド署名生成装置に送信し、ブラインド署名生成装置の受信部が、証明結果情報を受信し、証明結果検証部が、証明結果情報を検証する。そして、ブラインド署名生成装置のＹ計算部がＹを計算するための処理は、ブラインド署名生成装置の証明検証部が証明結果情報を合格と判断した場合にのみ実行される。
【００１４】
これにより、利用者装置が署名対象ｍに対応しないＸをブラインド署名生成装置に送信し、不正な或いは誤ったブラインド署名が生成されることを防止できる。
また、第２の発明において好ましくは、利用者装置の乱数生成部が、ａ１，ａ２，ａ３を｛０，１，...，ｐ−１｝からランダムに選択し、利用者装置のＷ計算部が、Ｗ＝ｇ１a１・ψ（ｕ）a２・ψ（ｖ）a３（上付き添え字ａ１，ａ２，ａ３は、それぞれａ１，ａ２，ａ３を示す）を計算し、利用者装置の送信部が、Ｗをブラインド署名生成装置に送信する。次に、ブラインド署名生成装置の受信部がＷを受信し、Ｗが受信された後、ブラインド署名生成装置の乱数生成部が、ηを｛０，１，...，ｐ−１｝からランダムに選択し、送信部が、ηを利用者装置に送信し、利用者装置の受信部がηを受信する。そして、証明結果情報は、ｚ１＝ａ１＋η・ｍ・ｔ ｍｏｄ ｐ，ｚ２＝ａ２＋η・ｔ ｍｏｄ ｐ，ｚ３＝ａ３＋η・ｓ・ｔ ｍｏｄ ｐであり、ブラインド署名生成装置の証明結果検証部は、ｇ１ｚ１・ψ（ｕ）ｚ２・ψ（ｖ）ｚ３≡Ｗ・Ｘη（上付き添え字ｚ１，ｚ２，ｚ３は、それぞれｚ１，ｚ２，ｚ３を示す）が成り立つか否かにより、証明結果情報の検証を行う。
【００１５】
また、第２の発明において好ましくは、写像ψはＧ２からＧ１への同型写像である。
これにより、正確な署名検証が可能になる。
また、第２の発明において好ましくは、ブラインド署名生成装置の受信部がＸを受信するステップの後、ブラインド署名生成装置の送信部が少なくともＹを利用者装置に送信するステップの前に、乱数生成部がｒ，Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、Ｒ計算部がＲ＝ｇ２ｒを計算し、送信部が、ＹとともにＲとＬをも利用者装置に送信する。利用者装置の受信部は、ＹとともにＲとＬをも受信し、α計算部は、受信されたＲを用いてα＝ｗｆ−１・Ｒｆを計算する。また、利用者装置の受信部がＹとともにＲとＬをも受信するステップの後、利用者装置の送信部が署名対象情報ｍとブラインド署名（σ，α，β）とをブラインド署名検証装置に送信するステップの前に、利用者装置のβ計算部がβ＝ｓ＋Ｌ／ｔ ｍｏｄ ｐを計算する。
【００１６】
これにより、署名の安全性がより向上する。
【発明の効果】
【００１７】
以上のように、本発明では、ハッシュ関数に依存することなく、安全性が保証された効率的なブラインド署名を実現できる。
【発明を実施するための最良の形態】
【００１８】
第１の実施の形態：
以下、本発明の第１の実施の形態を図面を参照して説明する。
〔双線形写像〕
本発明は、双線形写像を用いる点に特徴がある。まず、本発明で用いる双線形写像の説明を行う。
本発明では、（Ｇ１，Ｇ２）を以下のような性質を持つ双線形群とする。
＜性質１＞Ｇ１とＧ２とは、位数がｐ（ｐは素数）の２つの巡回群である。
【００１９】
＜性質２＞ｇ２は、Ｇ１の生成元であり、ｇ２は、Ｇ２の生成元である。
＜性質３＞ψは、Ｇ２からＧ１への同型写像であり、ψ（ｇ２）＝ｇ１を満たす。
＜性質４＞ｅは、双線形写像であり、ｅ：Ｇ１×Ｇ２→ＧＴで定義される。なお、「×」は直積を示す。また、ＧＴの位数もｐである。つまり、ａ，ｂ∈Ｇ１，ｃ，ｄ∈Ｇ２のとき、以下の関係が成り立つ。
e(a・b,c)=e(a,c)・e(b,c) …(1)
e(a,c・d)=e(a,c)・e(a,d) …(2)
＜性質５＞ｅ，ψ，Ｇ１，Ｇ２，ＧＴの群演算は効率的に計算できる。
【００２０】
なお、上述のような双線形写像ｅを有限体上の楕円曲線を用いて実現する実現例については、文献「Boneh, D. and Franklin, M., "Identity Based Encryption from the Weil Pairing", SIAM J. of Computing, Vol. 32, No.3 pp.586-615, (2003)」などに記載されている。また、上述した記号の意味等については、文献「Boneh, D. and Boyen, X., "Short Signature Without Random Oracles", Proceedings of Crypto'04, LNCS, Springer-Verlag (2004)」とほぼ同様である。
〔構成〕
次に、本形態の構成について説明する。
【００２１】
図１は、本形態におけるブラインド署名生成・検証システムの全体構成を例示したブロック図である。また、図２はブラインド署名生成装置の詳細構成を、図３は利用者装置の詳細構成を、図４はブラインド署名検証装置の詳細構成を、それぞれ例示したブロック図である。以下、これらの図を用いて、本形態の構成を説明する。
＜全体構成＞
図１に例示するように、本形態のブラインド署名生成・検証システム１は、ブラインド署名生成装置１０と、利用者装置２０と、ブラインド署名検証装置３０とを有している。ここで、ブラインド署名生成装置１０と利用者装置２０と、及び利用者装置２０とブラインド署名検証装置３０とは、それぞれネットワークを通じて通信可能に接続されている。
【００２２】
＜ブラインド署名生成装置の構成＞
図１及び図２に例示するように、本形態のブラインド署名生成装置１０は、秘密鍵生成部１０ａと、公開鍵生成部１０ｂと、乱数生成部１０ｃと、ｈ計算部１０ｄと、記憶部１０ｅと、証明結果検証部１０ｆと、Ｙ計算部１０ｇと、送信部１０ｈと、受信部１０ｉと、制御部１０ｊとを有している。
本形態のブラインド署名生成装置１０は、ＣＰＵ（Central Processing Unit）、補助記憶装置、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、入出力インタフェース、ＮＩＣ（Network Interface Card）等から構成される公知のコンピュータにブラインド署名生成プログラムが読み込まれことにより構築されるものである。
【００２３】
すなわち、図１及び図２の鍵生成部１０ａ、公開鍵生成部１０ｂ、乱数生成部１０ｃ、ｈ計算部１０ｄ、証明結果検証部１０ｆ、Ｙ計算部１０ｇ及び制御部１０ｊは、ブラインド署名生成プログラムが読み込まれたＣＰＵに相当する。また、送信部１０ｈ及び受信部１０ｉは、ブラインド署名生成プログラムが読み込まれたＣＰＵ１１の制御のもと通信処理を行うＮＩＣ等に相当する。また、記憶部１０ｅは、補助記憶装置、ＲＡＭ、レジスタ等により構成される。なお、ブラインド署名生成装置１０は、制御部１０ｊの制御のもと各処理を実行する。
【００２４】
＜利用者装置の構成＞
図１及び図３に例示するように、本形態の利用者装置２０は、受信部２０ａと、送信部２０ｂと、乱数生成部２０ｃと、Ｘ計算部２０ｄと、制御部２０ｅと、証明結果情報生成部２０ｆと、σ計算部２０ｇと、α計算部２０ｈと、β計算部２０ｉと、記憶部２０ｊとを有している。また、図３に例示するように、証明結果情報生成部２０ｆは、Ｗ計算部２０ｆａとｚ計算部２０ｆｂを有している。
本形態の利用者装置２０は、前述のような公知のコンピュータに利用者プログラムが読み込まれることにより構成される。すなわち、乱数生成部２０ｃ、Ｘ計算部２０ｄ、制御部２０ｅ、証明結果情報生成部２０ｆ、σ計算部２０ｇ、α計算部２０ｈ及びβ計算部２０ｉは、利用者プログラムが読み込まれたＣＰＵに相当する。また、受信部２０ａ及び送信部２０ｂは、利用者プログラムが読み込まれたＣＰＵの制御のもと通信処理を行うＮＩＣ等に相当する。また、記憶部２０ｊは、補助記憶装置、ＲＡＭ、レジスタ等により構成される。なお、利用者装置２０は、制御部２０ｅの制御のもと各処理を実行する。
【００２５】
＜ブラインド署名検証装置の構成＞
図１及び図４に例示するように、本形態のブラインド署名検証装置３０は、受信部３０ａと、署名検証部３０ｂと、署名検証結果出力部３０ｃと、制御部３０ｄと、記憶部３０ｅとを有している。
本形態のブラインド署名検証装置３０は、前述のような公知のコンピュータにブラインド署名検証プログラムが読み込まれることにより構成される。すなわち、署名検証部３０ｂ及び制御部３０ｄは、ブラインド署名検証プログラムが読み込まれたＣＰＵに相当する。また、受信部３０ａは、ブラインド署名検証プログラムが読み込まれたＣＰＵの制御のもと通信処理を行うＮＩＣ等に相当する。また、署名検証結果出力部３０ｃは、ブラインド署名検証プログラムが読み込まれたＣＰＵの制御のもとデータ出力を行う入出力インタフェース等に相当する。なお、ブラインド署名検証装置３０は、制御部３０ｄの制御のもと各処理を実行する。
【００２６】
〔処理〕
次に、本形態のブラインド署名生成・検証処理について説明する。
図５は、ブラインド署名生成装置１０の処理を説明するためのフローチャートである。また、図６は、利用者装置２０の処理を説明するためのフローチャートである。また、図７は、ブラインド署名検証装置３０の処理を説明するためのフローチャートである。以下、これらの図を用いて本形態のブラインド署名生成・検証処理を説明する。
＜ブラインド署名生成処理＞
本処理の前提として、ブラインド署名生成装置１０の秘密鍵生成部１０ａ、乱数生成部１０ｃ、利用者装置２０の乱数生成部２０ｃ、証明結果情報生成部２０ｆ、β計算部２０ｉが、共通の素数ｐを利用できるように設定しておく。これは、ブラインド署名生成プログラム及び利用者プログラムのコードに素数ｐを記述して実現してもよいし、別途素数ｐのデータをＣＰＵに読み込ませて実現してもよい。また、利用者装置２０の記憶部２０ｊに署名対象情報（例えば文書）ｍ∈｛０，１，...，ｐ−１｝を格納しておく。本形態では、この署名対象情報ｍのブラインド署名を生成する。
【００２７】
本形態では、まず、ブラインド署名生成装置１０（図２）の秘密鍵生成部１０ａが、秘密鍵ｘ，ｙ，ｚ∈｛０，１，...，ｐ−１｝を（例えばランダムに）生成し、当該秘密鍵（ｘ，ｙ，ｚ）を記憶部１０ｅに格納する（図５／ステップＳ１）。なお、ランダムな値の生成には、例えば、公知の擬似乱数生成アルゴリズムを利用するが、入力値や、予め定められた値をランダム（任意）な値として用いてもよい（以下も同様）。
次に、ブラインド署名生成装置１０の公開鍵生成部１０ｂが、記憶部１０ｅから秘密鍵（ｘ，ｙ，ｚ）を読み込み、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ＝ｇ２ｙ，ｖ＝ｇ２ｚを生成し、当該公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を記憶部１０ｅに格納する（ステップＳ２）。
【００２８】
次に、乱数生成部１０ｃが、ｒを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１０ｅに格納する（ステップＳ３）。そして、ｈ計算部１０ｄが、記憶部１０ｅからｒと公開鍵ｇ２とを読み込み、ｈ＝ｇ２ｒを計算し、このｈを記憶部１０ｅに格納する（ステップＳ４）。そして、記憶部１０ｅに格納されたｈが送信部１０ｈに送られ、送信部１０ｈは、ｈを利用者装置２０に送信する（ステップＳ５）。
利用者装置２０（図３）は、受信部２０ａにおいてｈを受信し、記憶部２０ｊに格納する（図６／ステップＳ２１）。次に、乱数生成部２０ｃが、ｓとＲを｛０，１，...，ｐ−１｝からそれぞれランダムに選択して記憶部２０ｊに格納する（ステップＳ２２）。
【００２９】
また、利用者装置２０は、制御部２０ｅの制御のもと、送信部２０ｂからブラインド署名生成装置１０に対して公開鍵の発行要求情報を送信する。これを受けたブラインド署名生成装置１０は、記憶部１０ｅの公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を送信部１０ｈから利用者装置２０に送信し、利用者装置２０は、受信部２０ａでこれを受信し記憶部２０ｊに格納する（ステップＳ２３）。なお、この例の利用者装置２０は公開鍵ｇ２を使用しない。よって、利用者装置２０が公開鍵（ｇ１，ｗ，ｕ，ｖ）のみを取得する構成としてもよい。
【００３０】
次に利用者装置２０のＸ計算部２０ｄが、記憶部２０ｊから公開鍵（ｇ１，ｗ，ｕ，ｖ）と（ｓ，Ｒ）とｈと署名対象情報ｍとを読み込み、
X=g1m・ψ(u)・ψ(v)s・(ψ(w・h))R …(3)
を計算し、その演算結果Ｘを記憶部２０ｊに格納する（ステップＳ２４）。そして、このＸが送信部２０ｂに送られ、送信部２０ｂが、このＸをブラインド署名生成装置１０に送信する（ステップＳ２５）。なお、このＸは、ブラインド署名生成装置１０（図２）の受信部１０ｉで受信され記憶部１０ｅに格納される（図５／ステップＳ６）。
【００３１】
また、利用者装置２０（図３）は、（ｍ，ｓ，Ｒ）を保持していることを、少なくともｍを開示することなく（ｓ及びＲの少なくとも一方も開示しない構成も含む）ブラインド署名生成装置１０に証明する。
［証明の概要］
まず、証明結果情報生成部２０ｆが、当該利用者装置２０の記憶部２０ｊに（ｍ，ｓ，Ｒ）が格納されていることを、少なくともｍを開示することなく（好ましくは、ｍ，ｓ，Ｒを開示することなく）ブラインド署名生成装置１０に証明するための処理を実行し、その証明を行うための証明結果情報を生成して記憶部２０ｊに格納する（図６／ステップＳ２６）。そして、送信部２０ｂが、その証明結果情報をブラインド署名生成装置１０に送信する（ステップＳ２７）。ブラインド署名生成装置１０の受信部１０ｉは、この証明結果情報を受信し、証明結果検証部１０ｆが、この証明結果情報を検証する（図５／ステップＳ７）。そして、証明結果検証部１０ｆが、この証明結果情報を不合格と判断すれば、ブラインド署名生成装置１０の制御部１０ｊは処理をエラー終了させる。一方、証明結果検証部１０ｆが、この証明結果情報を合格と判断すれば、ステップＳ９以降の処理が実行される（ステップＳ８）。
【００３２】
［証明の具体例（証明の一例）］
次に、上記のステップＳ２６，Ｓ２７（図６）及びステップＳ７（図５）の処理の具体例を説明する。なお、本発明は、この具体例には限定されない。
図８は、上記のステップＳ２６，Ｓ２７及びステップＳ７の処理の具体例を説明するためのフローチャートである。以下、このフローチャートに従ってこの具体例の説明を行っていく。
まず、利用者装置２０（図３）の乱数生成部２０ｃが、（ａ１，ａ２，ａ３）を｛０，１，...，ｐ−１｝からランダムに選択して記憶部２０ｊに格納する（ステップＳ５１）。次に、証明結果情報生成部２０ｆのＷ計算部２０ｆａが、記憶部２０ｊから（ａ１，ａ２，ａ３）とｇ１とｖとｗとｈとを読み込み、
W=g1a1・ψ(v)a2・(ψ(w・h))a3 …(4)
を計算し、その演算結果Ｗを記憶部２０ｊに格納する（ステップＳ５２）。次に、記憶部２０ｊに格納されたＷが送信部２０ｂに送られ、送信部２０ｂは、Ｗをブラインド署名生成装置１０に送信する（ステップＳ５３）。
【００３３】
ブラインド署名生成装置１０（図２）の受信部１０ｉはこのＷを受信する（ステップＳ５４）。Ｗが受信された後、乱数生成部１０ｃが、ηを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１０ｅに格納する（ステップＳ５５）。このηは送信部１０ｈに送られ、送信部１０ｈは、このηを利用者装置２０に送信する（ステップＳ５６）。
利用者装置２０（図３）の受信部２０ａは、このηを受信して記憶部２０ｊに格納する（ステップＳ５７）。次に、証明結果情報生成部２０ｆのｚ計算部２０ｆｂが、記憶部２０ｊから（ａ１，ａ２，ａ３）とηとｍと（ｓ，Ｒ）とを読み込み、
z1=a1+η・m mod p
z2=a2+η・s mod p …(5)
z3=a3+η・R mod p
を計算し、その演算結果（ｚ１，ｚ２，ｚ３）を証明結果情報として記憶部２０ｊに格納する（ステップＳ５８）。次に、この証明結果情報（ｚ１，ｚ２，ｚ３）は、送信部２０ｂに送られ、送信部２０ｂは、証明結果情報（ｚ１，ｚ２，ｚ３）をブラインド署名生成装置１０に送信する（ステップＳ５９）。
【００３４】
ブラインド署名生成装置１０（図２）の受信部１０ｉは、この証明結果情報（ｚ１，ｚ２，ｚ３）を受信し、記憶部１０ｅに格納する（ステップＳ６０）。そして、証明結果検証部１０ｆが、記憶部１０ｅから、ｇ１，ｗ，ｕ，ｖ，ｈ，Ｗ，Ｘ，η，（ｚ１，ｚ２，ｚ３）を読み込み、
g1z1・ψ(v)z2・(ψ(w・h))z3≡W・(X/ψ(u))η …(6)
が成り立つか否かにより、証明結果情報の検証を行う（ステップＳ６１）。ここで、式（６）が成立する場合、証明結果検証部１０ｆは、証明結果が正当である旨を出力する（ステップＳ６２）。一方、式（６）が成立しない場合、証明結果検証部１０ｆは、証明結果が不当である旨を出力する（ステップＳ６３）。
【００３５】
そして、上述したステップＳ５１以降の処理を複数回繰り返し、全てのループにおいて証明結果が正当であると出力された場合、証明結果検証部１０ｆは、証明結果情報が合格であると判断し、１度でも証明結果が不当であると出力された場合、証明結果情報が不合格であると判断する（図５／ステップＳ８／［証明の具体例（証明の一例）］の説明終わり）。
証明結果検証部１０ｆが、証明結果情報を合格と判断した場合、ブラインド署名生成装置１０の乱数生成部１０ｃは、Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１０ｅに格納する（ステップＳ９）。次に、Ｙ計算部１０ｇが、記憶部１０ｅからＸ，ｇ１，Ｌ，ｚ，ｘ，ｒを読み込み、
Y=(X・g1L・z)1/(x+r) …(7)
を計算して記憶部１０ｅに格納する（ステップＳ１０）。次に、記憶部１０ｅに格納された（Ｙ，Ｌ）が送信部１０ｈに送られ、送信部１０ｈは、この（Ｙ，Ｌ）を利用者装置２０に送信する（ステップＳ１１）。
【００３６】
利用者装置２０（図３）の受信部２０ａは、この（Ｙ，Ｌ）を受信し、記憶部２０ｊに格納する（図６／ステップＳ２８）。次に、乱数生成部２０ｃが、ｔを｛０，１，...，ｐ−１｝からランダムに選択して記憶部２０ｊに格納する（ステップＳ２９）。そして、σ計算部２０ｇが、記憶部２０ｊからＹとｇ１とＲとｔとを読み込み、
σ=(Y/g1R)1/t …(8)
を計算し、その演算結果σを記憶部２０ｊに格納する（ステップＳ３０）。また、α計算部２０ｈが、記憶部２０ｊからｗとｈとｔとを読み込み、
α=wt-1・ht …(9)
を計算し、その演算結果αを記憶部２０ｊに格納する（ステップＳ３１）。さらに、β計算部２０ｉが、記憶部２０ｊからｓとＬとを読み込み、
β=s+L mod p …(10)
を計算し、その演算結果βを記憶部２０ｊに格納する（ステップＳ３２）。以上のように生成された（σ，α，β）が署名対象情報ｍのブラインド署名となる。そして、記憶部２０ｊに格納された署名対象情報ｍとそのブラインド署名（σ，α，β）とは送信部２０ｂに送られ、送信部２０ｂは、署名対象情報ｍとそのブラインド署名（σ，α，β）とをブラインド署名検証装置３０に送信する（ステップＳ３３）。
【００３７】
＜ブラインド署名検証処理＞
ブラインド署名検証装置（図４）の受信部３０ａは、上記の署名対象情報ｍとそのブラインド署名（σ，α，β）とを受信し、これらを記憶部３０ｅに格納する（ステップＳ４１）。また、受信部３０ａが、ブラインド署名生成装置１０から送信された公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を受信し、記憶部３０ｗに格納する（ステップＳ４２）。なお、ブラインド署名生成装置１０への公開鍵の配送依頼手順は、前述した利用者装置１０の場合と同様であるため説明を省略する。
【００３８】
次に署名検証部３０ｂが、記憶部３０ｅから署名対象情報ｍとそのブラインド署名（σ，α，β）と公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）とを読み込み、
σ≠1, α∈G2, e(σ,w・α)=e(g1,g2m・u・vβ) …(11)
が全て成立するか否かを検証する（ステップＳ４３）。ここで、式（１１）が成立する場合、署名検証部３０ｂは、署名検証が合格である旨の情報を署名検証結果出力部３０ｃに送り、署名検証結果出力部３０ｃは署名検証が合格である旨を出力する（ステップＳ４４）。一方、式（１１）が成立しなかった場合、署名検証部３０ｂは、署名検証が不合格である旨の情報を署名検証結果出力部３０ｃに送り、署名検証結果出力部３０ｃは署名検証が不合格である旨を出力する（ステップＳ４５）。
【００３９】
＜署名検証が正しく行われる理由＞
次に、式（１１）が成立する場合になぜ署名が合格であるといえるかについて説明する。
まず、前述の式（７）に式（３）を代入すると、
Y=(X・g1L・z)1/(x+r)=((g1m・ψ(u)・ψ(v)s・(ψ(w・h))R)・g1L・z)1/(x+r) …(12)
となる。また、前述の＜性質３＞より、ψは、Ｇ２からＧ１への同型写像であり、ψ（ｇ２）＝ｇ１を満たすため、式（１２）は、
Y=g1(m+y+(s+L)・z)/(x+r)・g1R …(13)
と変形できる。
【００４０】
そして、式（１３）と式（１０）により、式（８）は、
σ=(Y/g1R)1/t=g1(m+y+(s+L)・z)/(t・x+t・r)=g1(m+y+β・z)/(t・x+t・r) …(14)
と変形できる。
ここで、δ=(t‐1)・x+t・rとすると、式（１４）は、
σ=g1(m+y+β・z)/(x+((t‐1)・x+t・r))=g1(m+y+β・z)/(x+δ) …(15)
となる。
また、この場合、w=g2x（ステップＳ２），h=g2r（ステップＳ４）より、式（９）は、
α=wt-1・ht=g2(t‐1)・x+t・r=g2δ …(16)
となる。
【００４１】
これらより、式（１１）の左辺は、
e(σ,w・α)=e(g1(m+y+β・z)/(x+δ), g2x+δ) …(17)
と変形できる。さらに、＜性質４＞により、ｅは双線形写像であり、式（２）を満たすことから、式（１７）は、
e(σ,w・α)=e(g1(m+y+β・z)/(x+δ), g2x+δ)
=e(g1(m+y+β・z)/(x+δ), g2)・e(g1(m+y+β・z)/(x+δ), g2)・…・e(g1(m+y+β・z)/(x+δ), g2) …(18)
と変形でき、式（１）を満たすことから、式（１８）は、
e(σ,w・α)=e(g1(m+y+β・z), g2)
=e(g1, g2)・e(g1, g2)・…・e(g1, g2) …(19)
と変形できる。さらに、ｅは式（２）を満たし、u=g2y, v=g2z（ステップＳ２）より、式（１９）は、
e(σ,w・α)=e(g1, g2(m+y+β・z))
=e(g1, g2mu・vβ)=式（１１）の右辺
となる。
【００４２】
〔本形態の効果〕
本形態のブラインド署名には、ハッシュ関数が使われていない。また、本形態のブラインド署名生成処理及びブラインド署名検証処理の安全性はStrong Diffile-Hellman問題の求解困難性に基づいており、安全であるといえる。さらに、本形態のブラインド署名生成処理及びブラインド署名検証処理の処理速度は、現在最も広く使われているＲＳＡ署名などと同程度であり、高い実用性を持つ。
例えば、双線形写像の典型的な実現例では、Ｇ１＝Ｇ２となるような楕円曲線を用い、この楕円曲線のパラメータを２００ビット程度にすることが可能である。このときのブラインド署名（σ，α，β）のデータサイズは２００ビット程度（つまり、σ，α，β合計で６００ビット程度）となり、ＲＳＡ署名のデータサイズよりも小さくなる。
【００４３】
〔変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、ステップＳ２６，Ｓ２７（図６）及びステップＳ７（図５）において、利用者装置２０が、（ｍ，ｓ，Ｒ）を保持していることを、少なくともｍを開示することなく、ブラインド署名生成装置１０に証明し、この証明が成功した場合にのみ、ステップＳ９（図５）以降の処理を実行することとした。しかし、この証明処理を行うことなく、ステップＳ９（図５）以降の処理を実行することとしてもよい。
【００４４】
また、本形態では、ψをＧ２からＧ１への同型写像とした。しかし、ψをＧ２からＧ１への準同型写像とした構成であってもよい。
また、本形態では、ブラインド署名生成装置１０が秘密鍵ｘ，ｙ，ｚを生成し、ｕ＝ｇ２ｙによって公開鍵ｕを生成することとした。しかし、秘密鍵ｙを生成せず、公開鍵ｕを巡回群Ｇ２から任意に選択する構成でもよい。
また、本形態では、ブラインド署名生成装置１０がＬを｛０，１，．．．，ｐ−１｝からランダムに選択し、これを利用者装置２０に送信することとした。しかし、ブラインド署名生成装置１０がＬの選択や送信を行わない構成としてもよい。この場合、ブラインド署名生成装置１０が、利用者装置２０との間で既に共有しているＬ（０も含む）を用いてＹ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）を計算し、利用者装置２０がこのＬを用いてβを計算してもよい。ここでＬ＝０であるなら秘密鍵ｚは不要となり、ブラインド署名生成装置１０が、秘密鍵ｚを生成せず、公開鍵ｖを巡回群Ｇ２から任意に選択する構成を採ることもできる。また、この場合、利用者装置２０はｓをそのままβとして用いることもできる。
【００４５】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
第２の実施の形態：
次に、本発明の第２の実施の形態を図面を参照して説明する。なお、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する部分については説明を簡略化する。
【００４６】
〔構成〕
次に、本形態の構成について説明する。
図９は、本形態におけるブラインド署名生成・検証システムの全体構成を例示したブロック図である。また、図１０はブラインド署名生成装置の詳細構成を、図１１は利用者装置の詳細構成を、それぞれ例示したブロック図である。なお、ブラインド署名検証装置３０は、第１の実施の形態のものと同じである。以下、これらの図を用いて、本形態の構成を説明する。
【００４７】
＜全体構成＞
図９に例示するように、本形態のブラインド署名生成・検証システム１０１は、ブラインド署名生成装置１１０と、利用者装置１２０と、ブラインド署名検証装置３０とを有している。ここで、ブラインド署名生成装置１１０と利用者装置１２０と、及び利用者装置１２０とブラインド署名検証装置３０とは、それぞれネットワークを通じて通信可能に接続されている。
＜ブラインド署名生成装置の構成＞
図９及び図１０に例示するように、本形態のブラインド署名生成装置１１０は、秘密鍵生成部１１０ａと、公開鍵生成部１１０ｂと、乱数生成部１１０ｃと、Ｒ計算部１１０ｄ、記憶部１１０ｅと、証明結果検証部１１０ｆと、Ｙ計算部１１０ｇと、送信部１１０ｈと、受信部１１０ｉと、制御部１１０ｊとを有している。
【００４８】
本形態のブラインド署名生成装置１１０は、第１の実施の形態と同様、公知のコンピュータにブラインド署名生成プログラムが読み込まれことにより構築される。
すなわち、図９及び図１０の鍵生成部１１０ａ、公開鍵生成部１１０ｂ、乱数生成部１１０ｃ、Ｒ計算部１１０ｄ、証明結果検証部１１０ｆ、Ｙ計算部１１０ｇ及び制御部１１０ｊは、ブラインド署名生成プログラムが読み込まれたＣＰＵに相当する。また、送信部１１０ｈ及び受信部１１０ｉは、ブラインド署名生成プログラムが読み込まれたＣＰＵの制御のもと通信処理を行うＮＩＣ等に相当する。また、記憶部１１０ｅは、補助記憶装置、ＲＡＭ、レジスタ等により構成される。なお、ブラインド署名生成装置１１０は、制御部１１０ｊの制御のもと各処理を実行する。
【００４９】
＜利用者装置の構成＞
図９及び図１１に例示するように、本形態の利用者装置１２０は、受信部１２０ａと、送信部１２０ｂと、乱数生成部１２０ｃと、Ｘ計算部１２０ｄと、制御部１２０ｅと、証明結果情報生成部１２０ｆと、σ計算部１２０ｇと、α計算部１２０ｈと、β計算部１２０ｉと、記憶部１２０ｊと、τ計算部１２０ｋとを有している。また、図１１に例示するように、証明結果情報生成部１２０ｆは、Ｗ計算部１２０ｆａとｚ計算部１２０ｆｂを有している。
【００５０】
本形態の利用者装置１２０は、第１の実施の形態と同様、公知のコンピュータに利用者プログラムが読み込まれることにより構成される。すなわち、乱数生成部１２０ｃ、Ｘ計算部１２０ｄ、制御部１２０ｅ、証明結果情報生成部１２０ｆ、σ計算部１２０ｇ、α計算部１２０ｈ、β計算部１２０ｉ及びτ計算部１２０ｋは、利用者プログラムが読み込まれたＣＰＵに相当する。また、受信部１２０ａ及び送信部１２０ｂは、利用者プログラムが読み込まれたＣＰＵの制御のもと通信処理を行うＮＩＣ等に相当する。また、記憶部１２０ｊは、補助記憶装置、ＲＡＭ、レジスタ等により構成される。なお、利用者装置１２０は、制御部１２０ｅの制御のもと各処理を実行する。
【００５１】
＜ブラインド署名検証装置の構成＞
第１の実施の形態で説明した通りである。ここでは説明を省略する。
〔処理〕
次に、本形態のブラインド署名生成処理について説明する。
図１２は、ブラインド署名生成装置１１０の処理を説明するためのフローチャートである。また、図１３は、利用者装置２０の処理を説明するためのフローチャートである。以下、これらの図を用いて本形態のブラインド署名生成処理を説明する。なお、署名検証処理については、第１の実施の形態と同じであるため説明を省略する。
【００５２】
＜ブラインド署名生成処理＞
本処理の前提として、ブラインド署名生成装置１１０の秘密鍵生成部１１０ａ、乱数生成部１１０ｃ、利用者装置１２０の乱数生成部１２０ｃ、証明結果情報生成部１２０ｆ、β計算部１２０ｉ，τ計算部１２０ｋが、共通の素数ｐを利用できるように設定しておく。これは、ブラインド署名生成プログラム及び利用者プログラムのコードに素数ｐを記述して実現してもよいし、別途素数ｐのデータをＣＰＵに読み込ませて実現してもよい。また、利用者装置１２０の記憶部１２０ｊに署名対象情報（例えば文書）ｍ∈｛０，１，．．．，ｐ−１｝を格納しておく。本形態では、この署名対象情報ｍのブラインド署名を生成する。
【００５３】
本形態では、まず、ブラインド署名生成装置１１０（図１０）の秘密鍵生成部１１０ａが、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を（例えばランダムに）生成し、当該秘密鍵ｘを記憶部１１０ｅに格納する（図１２／ステップＳ１０１）。
次に、ブラインド署名生成装置１１０の公開鍵生成部１１０ｂが、記憶部１１０ｅから秘密鍵ｘを読み込み、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、当該公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を記憶部１１０ｅに格納する（ステップＳ１０２）。
【００５４】
次に、利用者装置１２０（図１１）の乱数生成部１２０ｃが、ｓとｔを｛０，１，...，ｐ−１｝からそれぞれランダムに選択して記憶部１２０ｊに格納する（ステップＳ１２１）。
また、利用者装置１２０は、制御部１２０ｅの制御のもと、送信部１２０ｂからブラインド署名生成装置１１０に対して公開鍵の発行要求情報を送信する。これを受けたブラインド署名生成装置１１０は、記憶部１１０ｅの公開鍵（ｇ１，ｇ２，ｗ，ｕ，ｖ）を送信部１１０ｈから利用者装置１２０に送信し、利用者装置１２０は、受信部１２０ａでこれを受信し記憶部１２０ｊに格納する（ステップＳ１２２）。なお、この例の利用者装置１２０は公開鍵ｇ２を使用しない。よって、利用者装置１２０が公開鍵（ｇ１，ｗ，ｕ，ｖ）のみを取得する構成としてもよい。
【００５５】
次に利用者装置１２０のＸ計算部１２０ｄが、記憶部１２０ｊから公開鍵（ｇ１，ｗ，ｕ，ｖ）と（ｓ，ｔ）と署名対象情報ｍとを読み込み、
X=(g1m・ψ(u)・ψ(v)s)t …(20)
を計算し、その演算結果Ｘを記憶部１２０ｊに格納する（ステップＳ１２３）。
そして、このＸが送信部１２０ｂに送られ、送信部１２０ｂが、このＸをブラインド署名生成装置１１０に送信する（ステップＳ１２４）。なお、このＸは、ブラインド署名生成装置１１０（図１０）の受信部１１０ｉで受信され、記憶部１１０ｅに格納される（図１２／ステップＳ１０３）。
【００５６】
また、利用者装置１２０（図１１）は、（m・ｔ ｍｏｄ p，t，s・ｔ mod p）を保持或いは算出可能である旨を、少なくともｍを開示することなく（好ましくは、ｍ，ｓ，ｔを開示することなく）ブラインド署名生成装置１１０に証明する。
［証明の概要］
まず、証明結果情報生成部１２０ｆが、（m・ｔ ｍｏｄ p，t，s・ｔ mod p）を保持或いは算出可能である旨を、少なくともｍを開示することなく（好ましくは、ｍ，ｓ，ｔを開示することなく）ブラインド署名生成装置１１０に証明するための処理を実行し、その証明を行うための証明結果情報を生成して記憶部１２０ｊに格納する（図１３／ステップＳ１２５）。そして、送信部１２０ｂが、その証明結果情報をブラインド署名生成装置１１０に送信する（ステップＳ１２６）。ブラインド署名生成装置１１０の受信部１１０ｉは、この証明結果情報を受信し、証明結果検証部１１０ｆが、この証明結果情報を検証する（図１２／ステップＳ１０４）。そして、証明結果検証部１１０ｆが、この証明結果情報を不合格と判断すれば、ブラインド署名生成装置１１０の制御部１１０ｊは処理をエラー終了させる。一方、証明結果検証部１１０ｆが、この証明結果情報を合格と判断すれば、ステップＳ１０６以降の処理が実行される（ステップＳ１０５）。
【００５７】
［証明の具体例（証明の一例）］
次に、上記のステップＳ１２５，Ｓ１２６（図１３）及びステップＳ１０４（図１２）の処理の具体例を説明する。なお、本発明は、この具体例には限定されない。
図１４は、上記のステップＳ１２５，Ｓ１２６及びステップＳ１０４の処理の具体例を説明するためのフローチャートである。以下、このフローチャートに従ってこの具体例の説明を行っていく。
まず、利用者装置１２０（図１１）の乱数生成部１２０ｃが、（ａ１，ａ２，ａ３）を｛０，１，...，ｐ−１｝からランダムに選択して記憶部１２０ｊに格納する（ステップＳ１５１）。次に、証明結果情報生成部１２０ｆのＷ計算部１２０ｆａが、記憶部１２０ｊから（ａ１，ａ２，ａ３）とｇ１とｕとｖとを読み込み、
Ｗ＝ｇ１a１・ψ（ｕ）a２・ψ（ｖ）a３ …(21)
を計算し、その演算結果Ｗを記憶部１２０ｊに格納する（ステップＳ１５２）。次に、記憶部１２０ｊに格納されたＷが送信部１２０ｂに送られ、送信部１２０ｂは、Ｗをブラインド署名生成装置１１０に送信する（ステップＳ１５３）。
【００５８】
ブラインド署名生成装置１１０（図１０）の受信部１１０ｉはこのＷを受信する（ステップＳ１５４）。Ｗが受信された後、乱数生成部１１０ｃが、ηを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１１０ｅに格納する（ステップＳ１５５）。このηは送信部１１０ｈに送られ、送信部１１０ｈは、このηを利用者装置１２０に送信する（ステップＳ１５６）。
利用者装置１２０（図１１）の受信部１２０ａは、このηを受信して記憶部１２０ｊに格納する（ステップＳ１５７）。次に、証明結果情報生成部１２０ｆのｚ計算部１２０ｆｂが、記憶部１２０ｊから（ａ１，ａ２，ａ３）とηとｍとＲとを読み込み、
z1=a1+η・m・t mod p
z2=a2+η・t mod p …(22)
z3=a3+η・s・t mod p
を計算し、その演算結果（ｚ１，ｚ２，ｚ３）を証明結果情報として記憶部１２０ｊに格納する（ステップＳ１５８）。次に、この証明結果情報（ｚ１，ｚ２，ｚ３）は、送信部１２０ｂに送られ、送信部１２０ｂは、証明結果情報（ｚ１，ｚ２，ｚ３）をブラインド署名生成装置１１０に送信する（ステップＳ１５９）。
【００５９】
ブラインド署名生成装置１１０（図１０）の受信部１１０ｉは、この証明結果情報（ｚ１，ｚ２，ｚ３）を受信し、記憶部１１０ｅに格納する（ステップＳ１６０）。そして、証明結果検証部１１０ｆが、記憶部１１０ｅから、ｇ１，ｕ，ｖ，Ｗ，Ｘ，η，（ｚ１，ｚ２，ｚ３）を読み込み、
g1z1・ψ(u)z2・ψ(v)z3≡W・(X)η …(23）
が成り立つか否かにより、証明結果情報の検証を行う（ステップＳ１６１）。ここで、式（２３）が成立する場合、証明結果検証部１１０ｆは、証明結果が正当である旨を出力する（ステップＳ１６２）。一方、式（２３）が成立しない場合、証明結果検証部１１０ｆは、証明結果が不当である旨を出力する（ステップＳ１６３）。
【００６０】
そして、上述したステップＳ１５１以降の処理を複数回繰り返し、全てのループにおいて証明結果が正当であると出力された場合、証明結果検証部１１０ｆは、証明結果情報が合格であると判断し、１度でも証明結果が不当であると出力された場合、証明結果情報が不合格であると判断する（図１２／ステップＳ１０５／［証明の具体例（証明の一例）］の説明終わり）。
証明結果検証部１１０ｆが、証明結果情報を合格と判断した場合、ブラインド署名生成装置１１０の乱数生成部１１０ｃは、ｒ，Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１１０ｅに格納する（ステップＳ１０６）。次に、Ｙ計算部１１０ｇが、記憶部１１０ｅからＸ，Ｌ，ｖ，ｘ，ｒを読み込み、
Y=(X・ψ(v)L)1/(x+r) …(24）
を計算して記憶部１１０ｅに格納する（ステップＳ１０７）。
【００６１】
また、Ｒ計算部１１０ｄが、記憶部１１０ｅからｇ２，ｒを読み込み、
R=g2r …(25）
を計算して記憶部１１０ｅに格納する（ステップＳ１０８）。
次に、記憶部１１０ｅに格納された（Ｙ，Ｒ，Ｌ）が送信部１１０ｈに送られ、送信部１１０ｈは、この（Ｙ，Ｒ，Ｌ）を利用者装置１２０に送信する（ステップＳ１０９）。利用者装置１２０（図１１）の受信部１２０ａは、この（Ｙ，Ｒ，Ｌ）を受信し、記憶部１２０ｊに格納する（図１３／ステップＳ１２７）。次に、乱数生成部１２０ｃが、ｆを｛０，１，...，ｐ−１｝からランダムに選択して記憶部１２０ｊに格納する（ステップＳ１２８）。そして、τ計算部１２０ｋが、記憶部１２０ｊからｆとｔとを読み込み、
τ=(f・t)-1mod p …(26）
を計算し、その演算結果τを記憶部１２０ｊに格納する（ステップＳ１２９）。また、σ計算部１２０ｇが、記憶部１２０ｊからＹとτとを読み込み、
σ=Yτ …(27)
を計算し、その演算結果σを記憶部１２０ｊに格納する（ステップＳ１３０）。また、α計算部１２０ｈが、記憶部１２０ｊからｗとｈとｔとを読み込み、
α=wf-1・Rf …(28)
を計算し、その演算結果αを記憶部１２０ｊに格納する（ステップＳ１３１）。さらに、β計算部１２０ｉが、記憶部１２０ｊからｓとＬとｔとを読み込み、
β=s+L/t mod p …(29)
を計算し、その演算結果βを記憶部１２０ｊに格納する（ステップＳ１３２）。以上のように生成された（σ，α，β）が署名対象情報ｍのブラインド署名となる。そして、記憶部１２０ｊに格納された署名対象情報ｍとそのブラインド署名（σ，α，β）とは送信部１２０ｂに送られ、送信部１２０ｂは、署名対象情報ｍとそのブラインド署名（σ，α，β）とをブラインド署名検証装置１３０に送信する（ステップＳ１３３）。
【００６２】
＜ブラインド署名検証処理＞
本形態のブラインド署名検証処理でも、第１の実施の形態と同じく、
σ≠1, α∈G2, e(σ,w・α)=e(g1,g2m・u・vβ) …(30)
が成立する場合に署名が合格であると判断する。
＜署名検証が正しく行われる理由＞
次に、式（３０）が成立する場合になぜ署名が合格であるといえるかについて説明する。
【００６３】
まず、前述の式（２４）に式（２０）を代入すると、
Y=(X・ψ(v)L)1/(x+r)=((g1m・ψ(u)・ψ(v)s)t・ψ(v)L)1/(x+r)
=(g1m・ψ(u)・ψ(v)s+L/t)t/(x+r) …(31)
となる。これと式（２６）を式（２７）に代入すると、
σ=Yτ=Y1/(f・t)=(g1m・ψ(u)・ψ(v)s+L/t)1/(f・x+f・r) …(32)
となる。そして、式（３２）に式（２９）を代入し、さらに、δ=(f‐1)x+f・r mod pとすると、
σ=(g1m・ψ(u)・ψ(v)β)1/(x+(f−1)x+f・r)=(g1m・ψ(u)・ψ(v)β)1/(x+δ) …(33)
となる。また、w=g2xと式（２５）とを式（２８）に代入し、上記のδを用いて表現すると、
α=wf-1・Rf=g2f-1+r=g2(f‐1)x+f・r)=g2δ …(34)
となる。
【００６４】
これらより、式（１１）の左辺は、
e(σ,w・α)=e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2x+δ） …(35)
と変形できる。さらに、＜性質４＞により、ｅは双線形写像であり、式（２）を満たすことから、式（３５）は、
e(σ,w・α)=e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2x+δ）=e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2）・e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2）・…・e((g1m・ψ(u)・ψ(v)β)1/(x+δ)，g2） …(36)
と変形でき、式（１）を満たすことから、式（３６）は、
e(σ,w・α)=e(g1m・ψ(u)・ψ(v)β，g2） …(37)
と変形できる。また、ｕ，ｖ∈Ｇ２でありu=g2y, v=g2zと書ける（ｙ，ｚ∈｛０，１，...，ｐ−１｝）ため、式（３７）は、
e(σ,w・α)=e(g1m・ψ(g2y)・ψ(g2z)β，g2） …(37)
と書ける。また、前述の＜性質３＞より、ψは、Ｇ２からＧ１への同型写像であり、さらにψ（ｇ２）＝ｇ１を満たすため、式（３７）は、
e(σ,w・α)=e(g1m・ψ(g2y)・ψ(g2z)β，g2）=e(g1(m+y+β・z), g2) …(38)
と変形できる。さらに、式（１）を満たすことから、式（３８）は、
e(σ,w・α)=e(g1, g2)・e(g1, g2)・…・e(g1, g2) …(39)
と変形でき、式（２）を満たすことから、式（３９）は、
e(σ,w・α)=e(g1, g2(m+y+β・z)) …(40)
と変形できる。そして、u=g2y, v=g2zとおいているのだから、式（４０）は、
e(σ,w・α)=e(g1, g2mu・vβ)=式（３０）の右辺
となる。
【００６５】
〔本形態の効果〕
本形態のブラインド署名には、ハッシュ関数が使われていない。また、本形態のブラインド署名生成処理及びブラインド署名検証処理の安全性はStrong Diffile-Hellman問題の求解困難性に基づいており、安全であるといえる。さらに、本形態のブラインド署名生成処理及びブラインド署名検証処理の処理速度は、現在最も広く使われているＲＳＡ署名などと同程度であり、高い実用性を持つ。
〔変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、ステップＳ１２５，Ｓ１２６（図１３）及びステップＳ１０４（図１２）において、利用者装置１２０が、（m・ｔ ｍｏｄ p，t，s・ｔ mod p）を保持又は算出可能である旨を、少なくともｍを開示することなく、ブラインド署名生成装置１１０に証明し、この証明が成功した場合にのみ、ステップＳ１０６（図１２）以降の処理を実行することとした。しかし、この証明処理を行うことなく、ステップＳ１０６（図１２）以降の処理を実行することとしてもよい。
【００６６】
また、本形態では、ψをＧ２からＧ１への同型写像とした。しかし、ψをＧ２からＧ１への準同型写像とした構成であってもよい。
また、本形態では、ブラインド署名生成装置１１０がｒ，Ｌを｛０，１，．．．，ｐ−１｝からランダムに選択し、Ｒ＝ｇ２ｒを算出し、ＹとともにＬとＲを利用者装置１２０に送信することとした。しかし、ブラインド署名生成装置１１０がＲやＬの選択・算出・送信を行わない構成としてもよい。この場合、例えば、ブラインド署名生成装置１１０と利用者装置１２０とは事前にｒ，Ｌを共用しているものとし、ブラインド署名生成装置１１０は、これらを用いてＹ＝（Ｘ・ψ（ｖ）Ｌ）１／（ｘ＋ｒ）を計算し、利用者装置１２０は、これらｒ，Ｌをを用いて、Ｒ＝ｇ２ｒ、α＝ｗｆ−１・Ｒｆ及びβ＝ｓ＋Ｌ／ｔ ｍｏｄ ｐを計算する。
【００６７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、各実施の形態の処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７０】
本発明の産業上の利用分野としては、例えば、電子現金や電子投票の分野などを例示できる。
【図面の簡単な説明】
【００７１】
【図１】図１は、第１の実施の形態におけるブラインド署名生成・検証システムの全体構成を例示したブロック図である。
【図２】図２は、第１の実施の形態におけるブラインド署名生成装置の詳細構成を例示したブロック図である。
【図３】図３は、第１の実施の形態における利用者装置の詳細構成を例示したブロック図である。
【図４】図４は、第１，２の実施の形態におけるブラインド署名検証装置の詳細構成を例示したブロック図である。
【図５】図５は、第１の実施の形態におけるブラインド署名生成装置の処理を説明するためのフローチャートである。
【図６】図６は、第１の実施の形態における利用者装置の処理を説明するためのフローチャートである。
【図７】図７は、第１，２の実施の形態におけるブラインド署名検証装置の処理を説明するためのフローチャートである。
【図８】図８は、ステップＳ２６，Ｓ２７及びステップＳ７の処理の具体例を説明するためのフローチャートである。
【図９】図９は、第２の実施の形態におけるブラインド署名生成・検証システムの全体構成を例示したブロック図である。
【図１０】図１０は、第２の実施の形態におけるブラインド署名生成装置の詳細構成を例示したブロック図である。
【図１１】図１１は、第２の実施の形態における利用者装置の詳細構成を例示したブロック図である。
【図１２】図１２は、第２の実施の形態におけるブラインド署名生成装置の処理を説明するためのフローチャートである。
【図１３】図１３は、第２の実施の形態における利用者装置の処理を説明するためのフローチャートである。
【図１４】図１４は、Ｓ１２５，Ｓ１２６及びステップＳ１０４の処理の具体例を説明するためのフローチャートである。
【符号の説明】
【００７２】
１，１０１ ブラインド署名生成・検証システム
１０，１１０ ブラインド署名生成装置
２０，１２０ 利用者装置
３０ ブラインド署名検証装置
【特許請求の範囲】
【請求項１】
ブラインド署名生成装置と利用者装置とブラインド署名検証装置とによって実行されるブラインド署名生成・検証方法であって、
ブラインド署名生成装置の秘密鍵生成部が、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成して記憶部に格納するステップと、
ブラインド署名生成装置の公開鍵生成部が、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成して記憶部に格納するステップと、
ブラインド署名生成装置のｈ計算部が、ｈ＝ｇ２ｒ（ｒ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、ｈを利用者装置に送信するステップと、
利用者装置の受信部が、ｈを受信するステップと、
利用者装置の受信部が、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｗ，ｕ，ｖを受信するステップと、
利用者装置のＸ計算部が、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ・（ψ（ｗ・ｈ））Ｒ（ｓ，Ｒ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置の送信部が、Ｘをブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部がＸを受信するステップと、
ブラインド署名生成装置のＹ計算部が、Ｙ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）（Ｌ,ｚ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、少なくともＹを利用者装置に送信するステップと、
利用者装置の受信部が少なくともＹを受信するステップと、
利用者装置のσ計算部が、σ＝（Ｙ／ｇ１Ｒ）１／ｔ（ｔ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置のα計算部が、α＝ｗｔ−１・ｈｔを計算して記憶部に格納するステップと、
利用者装置の送信部が、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信するステップと、
ブラインド署名検証装置の受信部が、署名対象情報ｍと上記ブラインド署名（σ，α，β）とを受信するステップと、
ブラインド署名検証装置の受信部が、ブラインド署名生成装置から送信された公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖを受信するステップと、
ブラインド署名検証装置の署名検証部が、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証するステップと、
を有することを特徴とするブラインド署名生成・検証方法。
【請求項２】
請求項１に記載のブラインド署名生成・検証方法であって、
利用者装置の証明結果情報生成部が、当該利用者装置に（ｍ，ｓ，Ｒ）が保持されていることを、少なくともｍを開示することなくブラインド署名生成装置に証明するための証明結果情報を生成し、それを記憶部に格納するステップと、
利用者装置の送信部が、上記証明結果情報をブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部が、上記証明結果情報を受信するステップと、
ブラインド署名生成装置の証明結果検証部が、上記証明結果情報を検証するステップと、を有し、
上記のブラインド署名生成装置のＹ計算部がＹを計算するための処理は、
ブラインド署名生成装置の証明検証部が上記証明結果情報を合格と判断した場合にのみ実行される、
ことを特徴とするブラインド署名生成・検証方法。
【請求項３】
請求項２に記載のブラインド署名生成・検証方法であって、
利用者装置の乱数生成部が、ａ１，ａ２，ａ３を｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、
利用者装置のＷ計算部が、Ｗ＝ｇ１a１・ψ（ｖ）a２・（ψ（ｗ・ｈ））a３（上付き添え字ａ１，ａ２，ａ３は、それぞれａ１，ａ２，ａ３を示す）を計算して記憶部に格納するステップと、
利用者装置の送信部が、Ｗをブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部がＷを受信するステップと、
Ｗが受信された後、ブラインド署名生成装置の乱数生成部が、ηを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、ηを利用者装置に送信するステップと、
利用者装置の受信部が、ηを受信するステップと、を有し、
上記証明結果情報は、
ｚ１＝ａ１＋η・ｍ ｍｏｄ ｐ，ｚ２＝ａ２＋η・ｓ ｍｏｄ ｐ，ｚ３＝ａ３＋η・Ｒ ｍｏｄ ｐであり、
上記ブラインド署名生成装置の証明結果検証部は、
ｇ１ｚ１・ψ（ｖ）ｚ２・（ψ（ｗ・ｈ））ｚ３≡Ｗ・（Ｘ／ψ（ｕ））η（上付き添え字ｚ１，ｚ２，ｚ３は、それぞれｚ１，ｚ２，ｚ３を示す）が成り立つか否かにより、上記証明結果情報の検証を行う、
ことを特徴とするブラインド署名生成・検証方法。
【請求項４】
請求項１に記載のブラインド署名生成・検証方法であって、
上記写像ψはＧ２からＧ１への同型写像である、
ことを特徴とするブラインド署名生成・検証方法。
【請求項５】
請求項１に記載のブラインド署名生成・検証方法であって、
ブラインド署名生成装置の秘密鍵生成部が、秘密鍵ｘを生成する際に、秘密鍵ｚ∈｛０，１，...，ｐ−１｝も生成して記憶部に格納するステップをさらに有し、
ブラインド署名生成装置の公開鍵生成部が生成する公開鍵はｖ＝ｇ２ｚであり、
ブラインド署名生成装置の受信部がＸを受信するステップの後、ブラインド署名生成装置のＹ計算部がＹを計算して記憶部に格納するステップの前に、ブラインド署名生成装置の乱数生成部が、Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップをさらに有し、
ブラインド署名生成装置の送信部は、ＹとともにＬをも利用者装置に送信し、
利用者装置の受信部は、ＹとともにＬをも受信し、
利用者装置の受信部が、ＹとともにＬをも受信するステップの後、利用者装置の送信部が署名対象情報ｍとブラインド署名（σ，α，β）とをブラインド署名検証装置に送信するステップの前に、利用者装置のβ計算部が、β＝ｓ＋Ｌ ｍｏｄ ｐを計算して記憶部に格納するステップをさらに有する、
ことを特徴とするブラインド署名生成・検証方法。
【請求項６】
ブラインド署名生成装置であって、
秘密鍵生成部と、公開鍵生成部と、送信部と、受信部と、ｈ計算部と、Ｙ計算部とを有し、
上記秘密鍵生成部は、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、
上記公開鍵生成部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、
上記送信部は、公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖの少なくとも一部を利用者装置及びブラインド署名検証装置に送信し、
上記ｈ計算部は、ｈ＝ｇ２ｒ（ｒ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、ｈを利用者装置に送信し、
上記受信部は、利用者装置から送信されたＸを受信し、
上記Ｙ計算部は、Ｙ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）（Ｌ,ｚ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、少なくともＹを利用者装置に送信する、
ことを特徴とするブラインド署名生成装置。
【請求項７】
利用者装置であって、
送信部と、受信部と、Ｘ計算部と、σ計算部と、α計算部とを有し、
上記受信部は、ｈと公開鍵ｇ１，ｗ，ｕ，ｖとを少なくとも受信し、
上記Ｘ計算部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とし、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ・（ψ（ｗ・ｈ））Ｒ（ｓ，Ｒ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、Ｘをブラインド署名生成装置に送信し、
上記受信部は、少なくともブラインド署名生成装置から送信されたＹを受信し、
上記σ計算部は、σ＝（Ｙ／ｇ１Ｒ）１／ｔ（ｔ∈｛０，１，...，ｐ−１｝）を計算し、
上記α計算部は、α＝ｗｔ−１・ｈｔを計算し、
上記送信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ ｍｏｄ ｐ，Ｌ∈｛０，１，...，ｐ−１｝）と、をブラインド署名検証装置に送信する、
ことを特徴とする利用者装置。
【請求項８】
ブラインド署名検証装置であって、
受信部と、署名検証部とを有し、
上記受信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）と、公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖとを受信し、
上記署名検証部は、ｐを素数とし、Ｇ１とＧ２を位数がｐの巡回群とし、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証する、
ことを特徴とするブラインド署名検証装置。
【請求項９】
ブラインド署名生成装置と利用者装置とブラインド署名検証装置とからなるブラインド署名生成・検証システムであって、
上記ブラインド署名生成装置は、秘密鍵生成部と、公開鍵生成部と、送信部と、受信部と、ｈ計算部と、Ｙ計算部とを有し、
上記秘密鍵生成部は、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、上記公開鍵生成部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、上記ブラインド署名生成装置の送信部は、公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖの少なくとも一部を利用者装置及びブラインド署名検証装置に送信し、上記ｈ計算部は、ｈ＝ｇ２ｒ（ｒ∈｛０，１，...，ｐ−１｝）を計算し、上記送信部は、ｈを利用者装置に送信し、上記受信部は、利用者装置から送信されたＸを受信し、上記Ｙ計算部は、Ｙ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）（Ｌ,ｚ∈｛０，１，...，ｐ−１｝）を計算し、上記ブラインド署名生成装置の送信部は、少なくともＹを利用者装置に送信し、
上記利用者装置は、送信部と、受信部と、Ｘ計算部と、σ計算部と、α計算部とを有し、上記利用者装置の受信部は、ｈと公開鍵ｇ１，ｗ，ｕ，ｖとを少なくとも受信し、上記Ｘ計算部は、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ・（ψ（ｗ・ｈ））Ｒ（ｓ，Ｒ∈｛０，１，...，ｐ−１｝）を計算し、上記利用者装置の上記送信部は、Ｘをブラインド署名生成装置に送信し、上記利用者装置の上記受信部は、ブラインド署名生成装置から送信されたＹを少なくとも受信し、上記σ計算部は、σ＝（Ｙ／ｇ１Ｒ）１／ｔ（ｔ∈｛０，１，...，ｐ−１｝）を計算し、上記α計算部は、α＝ｗｔ−１・ｈｔを計算し、上記利用者装置の上記送信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）と、をブラインド署名検証装置に送信し、
上記ブラインド署名検証装置は、受信部と、署名検証部とを有し、
上記ブラインド署名検証装置の受信部は、署名対象情報ｍと上記ブラインド署名と公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖとを受信し、上記署名検証部は、ｐを素数とし、Ｇ１とＧ２を位数がｐの巡回群とし、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）（β＝ｓ＋Ｌ ｍｏｄ ｐ）が成立するか否かを検証する、
ことを特徴とするブラインド署名生成・検証システム。
【請求項１０】
ブラインド署名生成装置と利用者装置とブラインド署名検証装置とによって実行されるブラインド署名生成・検証方法であって、
ブラインド署名生成装置の秘密鍵生成部が、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成して記憶部に格納するステップと、
ブラインド署名生成装置の公開鍵生成部が、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成して記憶部に格納するステップと、
利用者装置の受信部が、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｕ，ｖを受信するステップと、
利用者装置のＸ計算部が、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝（ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ）ｔ（ｓ，ｔ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置の送信部が、Ｘをブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部がＸを受信するステップと、
ブラインド署名生成装置のＹ計算部が、Ｙ＝（Ｘ・（ψ（ｖ））Ｌ）１／（ｘ＋ｒ）（ｒ，Ｌ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、少なくともＹを利用者装置に送信するステップと、
利用者装置の受信部が少なくともＹを受信するステップと、
利用者装置の受信部が、ブラインド署名生成装置から送信された公開鍵ｗを受信するステップと、
利用者装置のτ計算部が、τ＝（ｆ・ｔ）−１ ｍｏｄ ｐ（ｆ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置のσ計算部が、σ＝Ｙτを計算して記憶部に格納するステップと、
利用者装置のα計算部が、α＝ｗｆ−１・Ｒｆ（Ｒ＝ｇ２ｒ，ｒ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置の送信部が、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ／ｔ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信するステップと、
ブラインド署名検証装置の受信部が、署名対象情報ｍと上記ブラインド署名（σ，α，β）とを受信するステップと、
ブラインド署名検証装置の受信部が、ブラインド署名生成装置から送信された公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖを受信するステップと、
ブラインド署名検証装置の署名検証部が、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証するステップと、
を有することを特徴とするブラインド署名生成・検証方法。
【請求項１１】
請求項１０に記載のブラインド署名生成・検証方法であって、
利用者装置の証明結果情報生成部が、（ｍ・ｔ ｍｏｄ ｐ，ｔ，ｓ・ｔ ｍｏｄ ｐ）を保持又は算出可能であることを、少なくともｍを開示することなくブラインド署名生成装置に証明するための証明結果情報を生成し、それを記憶部に格納するステップと、
利用者装置の送信部が、上記証明結果情報をブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部が、上記証明結果情報を受信するステップと、
ブラインド署名生成装置の証明結果検証部が、上記証明結果情報を検証するステップと、を有し、
上記のブラインド署名生成装置のＹ計算部がＹを計算するための処理は、
ブラインド署名生成装置の証明検証部が上記証明結果情報を合格と判断した場合にのみ実行される、
ことを特徴とするブラインド署名生成・検証方法。
【請求項１２】
請求項１１に記載のブラインド署名生成・検証方法であって、
利用者装置の乱数生成部が、ａ１，ａ２，ａ３を｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、
利用者装置のＷ計算部が、Ｗ＝ｇ１a１・ψ（ｕ）a２・ψ（ｖ）a３（上付き添え字ａ１，ａ２，ａ３は、それぞれａ１，ａ２，ａ３を示す）を計算して記憶部に格納するステップと、
利用者装置の送信部が、Ｗをブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部がＷを受信するステップと、
Ｗが受信された後、ブラインド署名生成装置の乱数生成部が、ηを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、ηを利用者装置に送信するステップと、
利用者装置の受信部が、ηを受信するステップと、を有し、
上記証明結果情報は、
ｚ１＝ａ１＋η・ｍ・ｔ ｍｏｄ ｐ，ｚ２＝ａ２＋η・ｔ ｍｏｄ ｐ，ｚ３＝ａ３＋η・ｓ・ｔ ｍｏｄ ｐであり、
上記ブラインド署名生成装置の証明結果検証部は、
ｇ１ｚ１・ψ（ｕ）ｚ２・ψ（ｖ）ｚ３≡Ｗ・Ｘη（上付き添え字ｚ１，ｚ２，ｚ３は、それぞれｚ１，ｚ２，ｚ３を示す）が成り立つか否かにより、上記証明結果情報の検証を行う、
ことを特徴とするブラインド署名生成・検証方法。
【請求項１３】
請求項１０に記載のブラインド署名生成・検証方法であって、
上記写像ψはＧ２からＧ１への同型写像である、
ことを特徴とするブラインド署名生成・検証方法。
【請求項１４】
請求項１０に記載のブラインド署名生成・検証方法であって、
ブラインド署名生成装置の受信部がＸを受信するステップの後、ブラインド署名生成装置の送信部が少なくともＹを利用者装置に送信するステップの前に、ブラインド署名生成装置の乱数生成部がｒ，Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、Ｒ計算部がＲ＝ｇ２ｒを計算して記憶部に格納するステップとを有し、
ブラインド署名生成装置の送信部は、ＹとともにＲとＬをも利用者装置に送信し、
利用者装置の受信部は、ＹとともにＲとＬをも受信し、
利用者装置のα計算部は、受信されたＲを用いてα＝ｗｆ−１・Ｒｆを計算し、
利用者装置の受信部がＹとともにＲとＬをも受信するステップの後、利用者装置の送信部が署名対象情報ｍとブラインド署名（σ，α，β）とをブラインド署名検証装置に送信するステップの前に、利用者装置のβ計算部がβ＝ｓ＋Ｌ／ｔ ｍｏｄ ｐを計算して記憶部に格納するステップをさらに有する、
ことを特徴とするブラインド署名生成・検証方法。
【請求項１５】
ブラインド署名生成装置であって、
秘密鍵生成部と、公開鍵生成部と、送信部と、受信部と、Ｙ計算部とを有し、
上記秘密鍵生成部は、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、
上記公開鍵生成部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、
上記受信部は、利用者装置から送信されたＸを受信し、
上記Ｙ計算部は、Ｙ＝（Ｘ・（ψ（ｖ））Ｌ）１／（ｘ＋ｒ）（ｒ，Ｌ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、少なくともＹを利用者装置に送信する、
ことを特徴とするブラインド署名生成装置。
【請求項１６】
利用者装置であって、
送信部と、受信部と、Ｘ計算部と、τ計算部と、σ計算部と、α計算部とを有し、
上記受信部は、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｕ，ｖを受信し、
上記Ｘ計算部は、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝（ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ）ｔ（ｓ，ｔ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、Ｘをブラインド署名生成装置に送信し、
上記受信部は、少なくともブランド署名生成装置から送信されたＹを受信し、
上記受信部は、ブラインド署名生成装置から送信された公開鍵ｗを受信し、
上記τ計算部は、τ＝（ｆ・ｔ）−１ ｍｏｄ ｐ（ｆ∈｛０，１，...，ｐ−１｝）を計算し、
上記σ計算部は、σ＝Ｙτを計算し、
上記α計算部は、α＝ｗｆ−１・Ｒｆ（Ｒ＝ｇ２ｒ，ｒ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ／ｔ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信する、
ことを特徴とする利用者装置。
【請求項１７】
ブラインド署名生成装置と利用者装置とブラインド署名検証装置とからなるブラインド署名生成・検証システムであって、
上記ブラインド署名生成装置は、秘密鍵生成部と、公開鍵生成部と、送信部と、受信部と、Ｙ計算部とを有し、
上記秘密鍵生成部は、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、上記公開鍵生成部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、上記受信部は、利用者装置から送信されたＸを受信し、上記Ｙ計算部は、Ｙ＝（Ｘ・（ψ（ｖ））Ｌ）１／（ｘ＋ｒ）（ｒ，Ｌ∈｛０，１，...，ｐ−１｝）を計算し、上記送信部は、少なくともＹを利用者装置に送信し、
上記利用者装置は、送信部と、受信部と、Ｘ計算部と、τ計算部と、σ計算部と、α計算部とを有し、
上記受信部は、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｕ，ｖを受信し、上記Ｘ計算部は、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝（ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ）ｔ（ｓ，ｔ∈｛０，１，...，ｐ−１｝）を計算し、上記送信部は、Ｘをブラインド署名生成装置に送信し、上記受信部は、少なくともブランド署名生成装置から送信されたＹを受信し、上記受信部は、ブラインド署名生成装置から送信された公開鍵ｗを受信し、上記τ計算部は、τ＝（ｆ・ｔ）−１ｍｏｄ ｐ（ｆ∈｛０，１，...，ｐ−１｝）を計算し、上記σ計算部は、σ＝Ｙτを計算し、上記α計算部は、α＝ｗｆ−１・Ｒｆ（Ｒ＝ｇ２ｒ，ｒ∈｛０，１，...，ｐ−１｝）を計算し、上記送信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ／ｔ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信し、
上記ブラインド署名検証装置は、受信部と、署名検証部とを有し、
上記受信部は、署名対象情報ｍと上記ブラインド署名（σ，α，β）と、公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖとを受信し、上記署名検証部は、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証する、
ことを特徴とするブラインド署名生成・検証システム。
【請求項１８】
請求項６又は１５に記載のブラインド署名生成装置としてコンピュータを機能させるためのブラインド署名生成プログラム。
【請求項１９】
請求項７又は１６に記載の利用者装置としてコンピュータを機能させるための利用者プログラム。
【請求項２０】
請求項８に記載のブラインド署名検証装置としてコンピュータを機能させるためのブラインド署名検証プログラム。
【請求項１】
ブラインド署名生成装置と利用者装置とブラインド署名検証装置とによって実行されるブラインド署名生成・検証方法であって、
ブラインド署名生成装置の秘密鍵生成部が、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成して記憶部に格納するステップと、
ブラインド署名生成装置の公開鍵生成部が、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成して記憶部に格納するステップと、
ブラインド署名生成装置のｈ計算部が、ｈ＝ｇ２ｒ（ｒ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、ｈを利用者装置に送信するステップと、
利用者装置の受信部が、ｈを受信するステップと、
利用者装置の受信部が、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｗ，ｕ，ｖを受信するステップと、
利用者装置のＸ計算部が、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ・（ψ（ｗ・ｈ））Ｒ（ｓ，Ｒ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置の送信部が、Ｘをブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部がＸを受信するステップと、
ブラインド署名生成装置のＹ計算部が、Ｙ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）（Ｌ,ｚ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、少なくともＹを利用者装置に送信するステップと、
利用者装置の受信部が少なくともＹを受信するステップと、
利用者装置のσ計算部が、σ＝（Ｙ／ｇ１Ｒ）１／ｔ（ｔ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置のα計算部が、α＝ｗｔ−１・ｈｔを計算して記憶部に格納するステップと、
利用者装置の送信部が、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信するステップと、
ブラインド署名検証装置の受信部が、署名対象情報ｍと上記ブラインド署名（σ，α，β）とを受信するステップと、
ブラインド署名検証装置の受信部が、ブラインド署名生成装置から送信された公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖを受信するステップと、
ブラインド署名検証装置の署名検証部が、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証するステップと、
を有することを特徴とするブラインド署名生成・検証方法。
【請求項２】
請求項１に記載のブラインド署名生成・検証方法であって、
利用者装置の証明結果情報生成部が、当該利用者装置に（ｍ，ｓ，Ｒ）が保持されていることを、少なくともｍを開示することなくブラインド署名生成装置に証明するための証明結果情報を生成し、それを記憶部に格納するステップと、
利用者装置の送信部が、上記証明結果情報をブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部が、上記証明結果情報を受信するステップと、
ブラインド署名生成装置の証明結果検証部が、上記証明結果情報を検証するステップと、を有し、
上記のブラインド署名生成装置のＹ計算部がＹを計算するための処理は、
ブラインド署名生成装置の証明検証部が上記証明結果情報を合格と判断した場合にのみ実行される、
ことを特徴とするブラインド署名生成・検証方法。
【請求項３】
請求項２に記載のブラインド署名生成・検証方法であって、
利用者装置の乱数生成部が、ａ１，ａ２，ａ３を｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、
利用者装置のＷ計算部が、Ｗ＝ｇ１a１・ψ（ｖ）a２・（ψ（ｗ・ｈ））a３（上付き添え字ａ１，ａ２，ａ３は、それぞれａ１，ａ２，ａ３を示す）を計算して記憶部に格納するステップと、
利用者装置の送信部が、Ｗをブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部がＷを受信するステップと、
Ｗが受信された後、ブラインド署名生成装置の乱数生成部が、ηを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、ηを利用者装置に送信するステップと、
利用者装置の受信部が、ηを受信するステップと、を有し、
上記証明結果情報は、
ｚ１＝ａ１＋η・ｍ ｍｏｄ ｐ，ｚ２＝ａ２＋η・ｓ ｍｏｄ ｐ，ｚ３＝ａ３＋η・Ｒ ｍｏｄ ｐであり、
上記ブラインド署名生成装置の証明結果検証部は、
ｇ１ｚ１・ψ（ｖ）ｚ２・（ψ（ｗ・ｈ））ｚ３≡Ｗ・（Ｘ／ψ（ｕ））η（上付き添え字ｚ１，ｚ２，ｚ３は、それぞれｚ１，ｚ２，ｚ３を示す）が成り立つか否かにより、上記証明結果情報の検証を行う、
ことを特徴とするブラインド署名生成・検証方法。
【請求項４】
請求項１に記載のブラインド署名生成・検証方法であって、
上記写像ψはＧ２からＧ１への同型写像である、
ことを特徴とするブラインド署名生成・検証方法。
【請求項５】
請求項１に記載のブラインド署名生成・検証方法であって、
ブラインド署名生成装置の秘密鍵生成部が、秘密鍵ｘを生成する際に、秘密鍵ｚ∈｛０，１，...，ｐ−１｝も生成して記憶部に格納するステップをさらに有し、
ブラインド署名生成装置の公開鍵生成部が生成する公開鍵はｖ＝ｇ２ｚであり、
ブラインド署名生成装置の受信部がＸを受信するステップの後、ブラインド署名生成装置のＹ計算部がＹを計算して記憶部に格納するステップの前に、ブラインド署名生成装置の乱数生成部が、Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップをさらに有し、
ブラインド署名生成装置の送信部は、ＹとともにＬをも利用者装置に送信し、
利用者装置の受信部は、ＹとともにＬをも受信し、
利用者装置の受信部が、ＹとともにＬをも受信するステップの後、利用者装置の送信部が署名対象情報ｍとブラインド署名（σ，α，β）とをブラインド署名検証装置に送信するステップの前に、利用者装置のβ計算部が、β＝ｓ＋Ｌ ｍｏｄ ｐを計算して記憶部に格納するステップをさらに有する、
ことを特徴とするブラインド署名生成・検証方法。
【請求項６】
ブラインド署名生成装置であって、
秘密鍵生成部と、公開鍵生成部と、送信部と、受信部と、ｈ計算部と、Ｙ計算部とを有し、
上記秘密鍵生成部は、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、
上記公開鍵生成部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、
上記送信部は、公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖの少なくとも一部を利用者装置及びブラインド署名検証装置に送信し、
上記ｈ計算部は、ｈ＝ｇ２ｒ（ｒ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、ｈを利用者装置に送信し、
上記受信部は、利用者装置から送信されたＸを受信し、
上記Ｙ計算部は、Ｙ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）（Ｌ,ｚ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、少なくともＹを利用者装置に送信する、
ことを特徴とするブラインド署名生成装置。
【請求項７】
利用者装置であって、
送信部と、受信部と、Ｘ計算部と、σ計算部と、α計算部とを有し、
上記受信部は、ｈと公開鍵ｇ１，ｗ，ｕ，ｖとを少なくとも受信し、
上記Ｘ計算部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とし、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ・（ψ（ｗ・ｈ））Ｒ（ｓ，Ｒ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、Ｘをブラインド署名生成装置に送信し、
上記受信部は、少なくともブラインド署名生成装置から送信されたＹを受信し、
上記σ計算部は、σ＝（Ｙ／ｇ１Ｒ）１／ｔ（ｔ∈｛０，１，...，ｐ−１｝）を計算し、
上記α計算部は、α＝ｗｔ−１・ｈｔを計算し、
上記送信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ ｍｏｄ ｐ，Ｌ∈｛０，１，...，ｐ−１｝）と、をブラインド署名検証装置に送信する、
ことを特徴とする利用者装置。
【請求項８】
ブラインド署名検証装置であって、
受信部と、署名検証部とを有し、
上記受信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）と、公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖとを受信し、
上記署名検証部は、ｐを素数とし、Ｇ１とＧ２を位数がｐの巡回群とし、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証する、
ことを特徴とするブラインド署名検証装置。
【請求項９】
ブラインド署名生成装置と利用者装置とブラインド署名検証装置とからなるブラインド署名生成・検証システムであって、
上記ブラインド署名生成装置は、秘密鍵生成部と、公開鍵生成部と、送信部と、受信部と、ｈ計算部と、Ｙ計算部とを有し、
上記秘密鍵生成部は、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、上記公開鍵生成部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、上記ブラインド署名生成装置の送信部は、公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖの少なくとも一部を利用者装置及びブラインド署名検証装置に送信し、上記ｈ計算部は、ｈ＝ｇ２ｒ（ｒ∈｛０，１，...，ｐ−１｝）を計算し、上記送信部は、ｈを利用者装置に送信し、上記受信部は、利用者装置から送信されたＸを受信し、上記Ｙ計算部は、Ｙ＝（Ｘ・ｇ１Ｌ・ｚ）１／（ｘ＋ｒ）（Ｌ,ｚ∈｛０，１，...，ｐ−１｝）を計算し、上記ブラインド署名生成装置の送信部は、少なくともＹを利用者装置に送信し、
上記利用者装置は、送信部と、受信部と、Ｘ計算部と、σ計算部と、α計算部とを有し、上記利用者装置の受信部は、ｈと公開鍵ｇ１，ｗ，ｕ，ｖとを少なくとも受信し、上記Ｘ計算部は、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ・（ψ（ｗ・ｈ））Ｒ（ｓ，Ｒ∈｛０，１，...，ｐ−１｝）を計算し、上記利用者装置の上記送信部は、Ｘをブラインド署名生成装置に送信し、上記利用者装置の上記受信部は、ブラインド署名生成装置から送信されたＹを少なくとも受信し、上記σ計算部は、σ＝（Ｙ／ｇ１Ｒ）１／ｔ（ｔ∈｛０，１，...，ｐ−１｝）を計算し、上記α計算部は、α＝ｗｔ−１・ｈｔを計算し、上記利用者装置の上記送信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）と、をブラインド署名検証装置に送信し、
上記ブラインド署名検証装置は、受信部と、署名検証部とを有し、
上記ブラインド署名検証装置の受信部は、署名対象情報ｍと上記ブラインド署名と公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖとを受信し、上記署名検証部は、ｐを素数とし、Ｇ１とＧ２を位数がｐの巡回群とし、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）（β＝ｓ＋Ｌ ｍｏｄ ｐ）が成立するか否かを検証する、
ことを特徴とするブラインド署名生成・検証システム。
【請求項１０】
ブラインド署名生成装置と利用者装置とブラインド署名検証装置とによって実行されるブラインド署名生成・検証方法であって、
ブラインド署名生成装置の秘密鍵生成部が、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成して記憶部に格納するステップと、
ブラインド署名生成装置の公開鍵生成部が、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成して記憶部に格納するステップと、
利用者装置の受信部が、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｕ，ｖを受信するステップと、
利用者装置のＸ計算部が、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝（ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ）ｔ（ｓ，ｔ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置の送信部が、Ｘをブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部がＸを受信するステップと、
ブラインド署名生成装置のＹ計算部が、Ｙ＝（Ｘ・（ψ（ｖ））Ｌ）１／（ｘ＋ｒ）（ｒ，Ｌ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、少なくともＹを利用者装置に送信するステップと、
利用者装置の受信部が少なくともＹを受信するステップと、
利用者装置の受信部が、ブラインド署名生成装置から送信された公開鍵ｗを受信するステップと、
利用者装置のτ計算部が、τ＝（ｆ・ｔ）−１ ｍｏｄ ｐ（ｆ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置のσ計算部が、σ＝Ｙτを計算して記憶部に格納するステップと、
利用者装置のα計算部が、α＝ｗｆ−１・Ｒｆ（Ｒ＝ｇ２ｒ，ｒ∈｛０，１，...，ｐ−１｝）を計算して記憶部に格納するステップと、
利用者装置の送信部が、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ／ｔ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信するステップと、
ブラインド署名検証装置の受信部が、署名対象情報ｍと上記ブラインド署名（σ，α，β）とを受信するステップと、
ブラインド署名検証装置の受信部が、ブラインド署名生成装置から送信された公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖを受信するステップと、
ブラインド署名検証装置の署名検証部が、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証するステップと、
を有することを特徴とするブラインド署名生成・検証方法。
【請求項１１】
請求項１０に記載のブラインド署名生成・検証方法であって、
利用者装置の証明結果情報生成部が、（ｍ・ｔ ｍｏｄ ｐ，ｔ，ｓ・ｔ ｍｏｄ ｐ）を保持又は算出可能であることを、少なくともｍを開示することなくブラインド署名生成装置に証明するための証明結果情報を生成し、それを記憶部に格納するステップと、
利用者装置の送信部が、上記証明結果情報をブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部が、上記証明結果情報を受信するステップと、
ブラインド署名生成装置の証明結果検証部が、上記証明結果情報を検証するステップと、を有し、
上記のブラインド署名生成装置のＹ計算部がＹを計算するための処理は、
ブラインド署名生成装置の証明検証部が上記証明結果情報を合格と判断した場合にのみ実行される、
ことを特徴とするブラインド署名生成・検証方法。
【請求項１２】
請求項１１に記載のブラインド署名生成・検証方法であって、
利用者装置の乱数生成部が、ａ１，ａ２，ａ３を｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、
利用者装置のＷ計算部が、Ｗ＝ｇ１a１・ψ（ｕ）a２・ψ（ｖ）a３（上付き添え字ａ１，ａ２，ａ３は、それぞれａ１，ａ２，ａ３を示す）を計算して記憶部に格納するステップと、
利用者装置の送信部が、Ｗをブラインド署名生成装置に送信するステップと、
ブラインド署名生成装置の受信部がＷを受信するステップと、
Ｗが受信された後、ブラインド署名生成装置の乱数生成部が、ηを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、
ブラインド署名生成装置の送信部が、ηを利用者装置に送信するステップと、
利用者装置の受信部が、ηを受信するステップと、を有し、
上記証明結果情報は、
ｚ１＝ａ１＋η・ｍ・ｔ ｍｏｄ ｐ，ｚ２＝ａ２＋η・ｔ ｍｏｄ ｐ，ｚ３＝ａ３＋η・ｓ・ｔ ｍｏｄ ｐであり、
上記ブラインド署名生成装置の証明結果検証部は、
ｇ１ｚ１・ψ（ｕ）ｚ２・ψ（ｖ）ｚ３≡Ｗ・Ｘη（上付き添え字ｚ１，ｚ２，ｚ３は、それぞれｚ１，ｚ２，ｚ３を示す）が成り立つか否かにより、上記証明結果情報の検証を行う、
ことを特徴とするブラインド署名生成・検証方法。
【請求項１３】
請求項１０に記載のブラインド署名生成・検証方法であって、
上記写像ψはＧ２からＧ１への同型写像である、
ことを特徴とするブラインド署名生成・検証方法。
【請求項１４】
請求項１０に記載のブラインド署名生成・検証方法であって、
ブラインド署名生成装置の受信部がＸを受信するステップの後、ブラインド署名生成装置の送信部が少なくともＹを利用者装置に送信するステップの前に、ブラインド署名生成装置の乱数生成部がｒ，Ｌを｛０，１，...，ｐ−１｝からランダムに選択して記憶部に格納するステップと、Ｒ計算部がＲ＝ｇ２ｒを計算して記憶部に格納するステップとを有し、
ブラインド署名生成装置の送信部は、ＹとともにＲとＬをも利用者装置に送信し、
利用者装置の受信部は、ＹとともにＲとＬをも受信し、
利用者装置のα計算部は、受信されたＲを用いてα＝ｗｆ−１・Ｒｆを計算し、
利用者装置の受信部がＹとともにＲとＬをも受信するステップの後、利用者装置の送信部が署名対象情報ｍとブラインド署名（σ，α，β）とをブラインド署名検証装置に送信するステップの前に、利用者装置のβ計算部がβ＝ｓ＋Ｌ／ｔ ｍｏｄ ｐを計算して記憶部に格納するステップをさらに有する、
ことを特徴とするブラインド署名生成・検証方法。
【請求項１５】
ブラインド署名生成装置であって、
秘密鍵生成部と、公開鍵生成部と、送信部と、受信部と、Ｙ計算部とを有し、
上記秘密鍵生成部は、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、
上記公開鍵生成部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、
上記受信部は、利用者装置から送信されたＸを受信し、
上記Ｙ計算部は、Ｙ＝（Ｘ・（ψ（ｖ））Ｌ）１／（ｘ＋ｒ）（ｒ，Ｌ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、少なくともＹを利用者装置に送信する、
ことを特徴とするブラインド署名生成装置。
【請求項１６】
利用者装置であって、
送信部と、受信部と、Ｘ計算部と、τ計算部と、σ計算部と、α計算部とを有し、
上記受信部は、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｕ，ｖを受信し、
上記Ｘ計算部は、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝（ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ）ｔ（ｓ，ｔ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、Ｘをブラインド署名生成装置に送信し、
上記受信部は、少なくともブランド署名生成装置から送信されたＹを受信し、
上記受信部は、ブラインド署名生成装置から送信された公開鍵ｗを受信し、
上記τ計算部は、τ＝（ｆ・ｔ）−１ ｍｏｄ ｐ（ｆ∈｛０，１，...，ｐ−１｝）を計算し、
上記σ計算部は、σ＝Ｙτを計算し、
上記α計算部は、α＝ｗｆ−１・Ｒｆ（Ｒ＝ｇ２ｒ，ｒ∈｛０，１，...，ｐ−１｝）を計算し、
上記送信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ／ｔ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信する、
ことを特徴とする利用者装置。
【請求項１７】
ブラインド署名生成装置と利用者装置とブラインド署名検証装置とからなるブラインド署名生成・検証システムであって、
上記ブラインド署名生成装置は、秘密鍵生成部と、公開鍵生成部と、送信部と、受信部と、Ｙ計算部とを有し、
上記秘密鍵生成部は、ｐを素数とした場合における、秘密鍵ｘ∈｛０，１，...，ｐ−１｝を生成し、上記公開鍵生成部は、Ｇ１とＧ２を位数がｐの巡回群とし、ｇ１をＧ１の生成元とし、ｇ２をＧ２の生成元とした場合における、公開鍵ｇ１，ｇ２，ｗ＝ｇ２ｘ，ｕ∈Ｇ２，ｖ∈Ｇ２を生成し、上記受信部は、利用者装置から送信されたＸを受信し、上記Ｙ計算部は、Ｙ＝（Ｘ・（ψ（ｖ））Ｌ）１／（ｘ＋ｒ）（ｒ，Ｌ∈｛０，１，...，ｐ−１｝）を計算し、上記送信部は、少なくともＹを利用者装置に送信し、
上記利用者装置は、送信部と、受信部と、Ｘ計算部と、τ計算部と、σ計算部と、α計算部とを有し、
上記受信部は、少なくともブラインド署名生成装置から送信された公開鍵ｇ１，ｕ，ｖを受信し、上記Ｘ計算部は、ψをＧ２からＧ１への写像ψ（ｇ２）＝ｇ１とし、ｍを署名対象情報とした場合における、Ｘ＝（ｇ１ｍ・ψ（ｕ）・ψ（ｖ）ｓ）ｔ（ｓ，ｔ∈｛０，１，...，ｐ−１｝）を計算し、上記送信部は、Ｘをブラインド署名生成装置に送信し、上記受信部は、少なくともブランド署名生成装置から送信されたＹを受信し、上記受信部は、ブラインド署名生成装置から送信された公開鍵ｗを受信し、上記τ計算部は、τ＝（ｆ・ｔ）−１ｍｏｄ ｐ（ｆ∈｛０，１，...，ｐ−１｝）を計算し、上記σ計算部は、σ＝Ｙτを計算し、上記α計算部は、α＝ｗｆ−１・Ｒｆ（Ｒ＝ｇ２ｒ，ｒ∈｛０，１，...，ｐ−１｝）を計算し、上記送信部は、署名対象情報ｍと、ブラインド署名（σ，α，β）（β＝ｓ＋Ｌ／ｔ ｍｏｄ ｐ）と、をブラインド署名検証装置に送信し、
上記ブラインド署名検証装置は、受信部と、署名検証部とを有し、
上記受信部は、署名対象情報ｍと上記ブラインド署名（σ，α，β）と、公開鍵ｇ１，ｇ２，ｗ，ｕ，ｖとを受信し、上記署名検証部は、ｅをＧ１×Ｇ２→ＧＴの双線形写像とした場合における、σ≠１，α∈Ｇ２，ｅ（σ，ｗ・α）＝ｅ（ｇ１，ｇ２ｍ・ｕ・ｖβ）が成立するか否かを検証する、
ことを特徴とするブラインド署名生成・検証システム。
【請求項１８】
請求項６又は１５に記載のブラインド署名生成装置としてコンピュータを機能させるためのブラインド署名生成プログラム。
【請求項１９】
請求項７又は１６に記載の利用者装置としてコンピュータを機能させるための利用者プログラム。
【請求項２０】
請求項８に記載のブラインド署名検証装置としてコンピュータを機能させるためのブラインド署名検証プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００７−１１０６６８（Ｐ２００７−１１０６６８Ａ）
【公開日】平成１９年４月２６日（２００７．４．２６）
【国際特許分類】
【出願番号】特願２００６−５４５９４（Ｐ２００６−５４５９４）
【出願日】平成１８年３月１日（２００６．３．１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成１９年４月２６日（２００７．４．２６）
【国際特許分類】
【出願日】平成１８年３月１日（２００６．３．１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]