(57)【特許請求の範囲】
【請求項１】
署名依頼装置、署名装置、検証装置および開示装置を有し、
前記署名依頼装置、前記署名装置、前記検証装置および前記開示装置は、それぞれブラインド署名のシステムパラメータｐｒｍ＝（ｐ，ｑ，ｇ，ｈ）（ｐ，ｑはｑ｜ｐ−１となる素数、ｇ，ｈは群Ｚｐ＊の位数ｑの部分群Ｇの元）を保持し、
前記署名装置は、秘密鍵ｘ（ｘはｑ以下のランダムな自然数）を生成し、公開鍵ｙ＝ｇｘmodｐを計算して、ｘ，ｙを保持するとともに、ｙを前記署名依頼装置、前記検証装置および前記開示装置へ送信して、各装置がｙを保持するようにし、
前記開示装置は、秘密鍵ｒｓｋ＝（ｘｔ，ｄｋ）を生成し、公開鍵ｒｐｋ＝（ｙｔ＝ｇｘｔmodｐ，ｅｋ）を計算し（ｘｔはｑ以下のランダムな自然数、ｄｋおよびｅｋはそれぞれ検証可能暗号の秘密鍵および公開鍵）、ｒｓｋ，ｒｐｋを保持するとともに、ｒｐｋを前記署名依頼装置、前記署名装置および前記検証装置へ送信して、各装置がｒｐｋを保持するようにし、
（１）前記署名依頼装置は署名のための秘密鍵、公開鍵の組（Ｓｋ，ＰＫ）を作成し、前記署名装置にＰＫの鍵証明書生成を依頼し、
前記署名装置は、特定の文字列Infoを前記署名依頼装置に返すとともに、前記署名依頼装置又は署名依頼者を識別する情報（ＩＤ）を登録し、
前記署名依頼装置は、ｇ以下の自然数γをランダムに選び、ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ‖Info）（Ｈ１は任意のビット列であるｐ‖ｑ‖ｇ‖ｈ‖ｙ‖InfoをＧに写す一方向性ハッシュ関数）、ｚｕ＝ｚ１/γ，ξ＝ｇγ，Ｅ＝εｅｋ（γ）（εｅｋはｅｋでγを暗号化する関数），Ｐ＝Γ（（ｚｕ，ξ），γ，ｅｋ）（ΓはＥに対応する平文（＝γ）が１／logｚｚｕ（＝γ）およびlogｇξ（＝γ）と等しいことを署名装置にゼロ知識証明するための関数）を計算し、（ｚｕ，ξ，Ｅ，Ｐ）を前記署名装置に送信し、
前記署名装置は、ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ‖Info）を計算して、（ｚｕ，ξ，Ｅ，Ｐ）が正しいか検証し、正しい場合、ｑ以下の自然数ｖ，ｕ，ｓ１，ｓ２，ｄをランダムに選び、ｚ１＝ｙｔｖ，ｚ２＝ｚｕ／ｚ１，Ｐｓ＝Γｓ（ｚ１，ｙｔ，ｖ）（Γｓはlogｙｔｚ１（＝ｖ）の値を知っていることを署名依頼装置にゼロ知識証明するための関数）、ａ＝ｇｕ，ｂ１＝ｇｓ1ｚ１ｄ，ｂ２＝ｈｓ２ｚ２ｄ，ξｖを計算し、（Ｐｓ，ｚ１，ａ，ｂ１，ｂ２）を前記署名依頼装置に送信し、（ＩＤ，ξｖ）を保存し、
前記署名依頼装置は（ｚ１，ｂ１，ｂ２）がＧの元かどうか、（ｚ１，ｙｔ，Ｐｓ）が正しいか検証し、（ｚ１，ｂ１，ｂ２）がＧの元であり、かつ、（ｚ１，ｙｔ，Ｐｓ）が正しい場合、ｑ以下の自然数ｔ１，ｔ２，ｔ３，ｔ４，ｔ５をランダムに選び、ζ１＝ｚ１γ，ζ２＝ｚ／ζ１，α＝ａｇt１ｙｔ２，β１＝ｂ１γｇｔ３ζ１ｔ５，β２＝ｂ２γｈｔ４ζ２ｔ５，ε＝Ｈ２（ζ１‖α‖β１‖β２‖ＰＫ）（Ｈ２は任意の文字列をｑ以下の自然数に写す一方向性ハッシュ関数）、ｅ＝ε−ｔ２−ｔ５を計算し、ｅを前記署名装置に送信し、
前記署名装置は、ｃ＝ｅ−ｄ，ｒ＝ｕ−ｃｘを計算し、（ｒ，ｃ，ｓ１，ｓ２，ｄ）を前記署名依頼装置に送信し、
前記署名依頼装置は、ρ＝ｒ＋ｔ１，ω＝ｃ＋ｔ２，σ１＝γｓ１＋ｔ３，σ２＝γｓ２＋ｔ４，δ＝ｄ＋ｔ５を計算し、ω＋δ＝Ｈ２（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2ζ２δ‖ＰＫ）が成り立つか検証し、成り立つ場合、Σ＝（ζ１，ρ，ω，σ１，σ２，δ）をＰＫの証明書とする、
（２）前記署名依頼装置は、（ＳＫ，ＰＫ）を用いてメッセージｍｓｇに対する署名Ｓを生成し、Ｔ＝（Ｓ，ＰＫ，Info，Σ）を鍵証明書を含んだ署名の組とし、ｍｓｇ，Ｔを出力し、
前記検証装置は、ｍｓｇ，Ｔを入力として、Infoが所定の条件を満たすか確認し、満たす場合、ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ‖Info）を計算し、ω＋δ＝Ｈ２（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2(ｚ／ζ１)δ‖ＰＫ）が成り立つか検証し、成り立つ場合、Ｓがｍｓｇの正しい署名であるか検証する、
（３）前記開示装置および前記署名装置はｍｓｇ，Ｔを入力し、
前記開示装置は、Ｉ＝ζ１1/ｘtを計算し、Ｉを前記署名装置に送信し、
前記署名装置は、（ＩＤ，ξｖ）の組からＩ＝ξｖとなるようなξｖを見つけ、該ξｖに対応するＩＤから、ｍｓｇの署名Ｓを生成した署名依頼装置または署名依頼者を特定する、
ことを特徴とする部分ブラインド署名・検証・追跡方法。
【請求項２】
署名依頼装置、署名装置、検証装置および開示装置を有し、
前記署名依頼装置、前記署名装置、前記検証装置および前記開示装置は、それぞれブラインド署名のシステムパラメータｐｒｍ＝（ｐ，ｑ，ｇ，ｈ）（ｐ，ｑはｑ｜ｐ−１となる素数、ｇ，ｈは群Ｚｐ＊の位数ｑの部分群Ｇの元）を保持し、
前記署名装置は、秘密鍵ｘ（ｘはｑ以下のランダムな自然数）を生成し、公開鍵ｙ＝ｇｘmodｐを計算して、ｘ，ｙを保持するとともに、ｙを前記署名依頼装置、前記検証装置および前記開示装置へ送信して、各装置がｙを保持するようにし、
前記開示装置は、秘密鍵ｒｓｋ＝（ｘｔ，ｄｋ）を生成し、公開鍵ｒｐｋ＝（ｙｔ＝ｇｘｔmodｐ，ｅｋ）を計算し（ｘｔはｑ以下のランダムな自然数、ｄｋおよびｅｋはそれぞれ検証可能暗号の秘密鍵および公開鍵）、ｒｓｋ，ｒｐｋを保持するとともに、ｒｐｋを前記署名依頼装置、前記署名装置および前記検証装置へ送信して、各装置がｒｐｋを保持するようにし、
（１）前記署名依頼装置は署名のための秘密鍵、公開鍵の組（Ｓｋ，ＰＫ）を作成し、前記署名装置にＰＫの鍵証明書生成を依頼し、
前記署名装置は、特定の文字列Infoを前記署名依頼装置に返すともに、前記署名依頼装置又は署名依頼者を識別する情報（ＩＤ）を登録し、
前記署名依頼装置は、ｇ以下の自然数γをランダムに選び、ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ）（Ｈ１は任意のビット列であるｐ‖ｑ‖ｇ‖ｈ‖ｙをＧに写す一方向性ハッシュ関数）、ｚｕ＝ｚ１/γ，ξ＝ｇγ，Ｅ＝εｅｋ（γ）（εｅｋはｅｋでγを暗号化する関数），Ｐ＝Γ（（ｚｕ，ξ），γ，ｅｋ）（ΓはＥに対応する平文（＝γ）が１／logｚｚｕ（＝γ）およびlogｇξ（＝γ）と等しいことを署名装置にゼロ知識証明するための関数）を計算し、（ｚｕ，ξ，Ｅ，Ｐ）を前記署名装置に送信し、
前記署名装置は、ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ）を計算して、（ｚｕ，ξ，Ｅ，Ｐ）が正しいか検証し、正しい場合、ｑ以下の自然数ｖ，ｕ，ｓ１，ｓ２，ｄをランダムに選び、ｚ１＝ｙｔｖ，ｚ２＝ｚｕ／ｚ１Info，Ｐｓ＝Γｓ（ｚ１，ｙｔ，ｖ）（Γｓはlogｙｔｚ１（＝ｖ）の値を知っていることを署名依頼装置にゼロ知識証明するための関数）、ａ＝ｇｕ，ｂ１＝ｇｓ1ｚ１ｄ，ｂ２＝ｈｓ２ｚ２ｄ，ξｖを計算し、（Ｐｓ，ｚ１，ａ，ｂ１，ｂ２）を署名依頼装置に送信し、（ＩＤ，ξｖ）を保存し、
前記署名依頼装置は（ｚ１，ｂ１，ｂ２）がＧの元かどうか、（ｚ１，ｙｔ，Ｐｓ）が正しいか検証し、（ｚ１，ｂ１，ｂ２）がＧの元であり、かつ、（ｚ１，ｙｔ，Ｐｓ）が正しい場合、ｑ以下の自然数ｔ１，ｔ２，ｔ３，ｔ４，ｔ５をランダムに選び、ζ１＝ｚ１γ，ζ２＝ｚ／ζ１Info，α＝ａｇt１ｙｔ２，β１＝ｂ１γｇｔ３ζ１ｔ５，β２＝ｂ２γｈｔ４ζ２ｔ５，ε＝Ｈ２（ζ１‖α‖β１‖β２‖ＰＫ）（Ｈ２は任意の文字列をｑ以下の自然数に写す一方向性ハッシュ関数）、ｅ＝ε−ｔ２−ｔ５を計算し、ｅを前記署名装置に送信し、
前記署名装置は、ｃ＝ｅ−ｄ，ｒ＝ｕ−ｃｘを計算し、（ｒ，ｃ，ｓ１，ｓ２，ｄ）を前記署名依頼装置に送信し、
前記署名依頼装置は、ρ＝ｒ＋ｔ１，ω＝ｃ＋ｔ２，σ１＝γｓ１＋ｔ３，σ２＝γｓ２＋ｔ４，δ＝ｄ＋ｔ５を計算し、ω＋δ＝Ｈ２（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2ζ２δ‖ＰＫ）が成り立つか検証し、成り立つ場合、Σ＝（ζ１，ρ，ω，σ１，σ２，δ）をＰＫの証明書とする、
（２）前記署名依頼装置は、（ＳＫ，ＰＫ）を用いてメッセージｍｓｇに対する署名Ｓを生成し、Ｔ＝（Ｓ，ＰＫ，Info，Σ）を鍵証明書を含んだ署名の組とし、ｍｓｇ，Ｔを出力し、
前記検証装置は、ｍｓｇ，Ｔを入力として、Infoが所定の条件を満たすか確認し、満たす場合、ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ）を計算し、ω＋δ＝Ｈ２（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2(ｚ／ζ１Info)δ‖ＰＫ）が成り立つか検証し、成り立つ場合、Ｓがｍｓｇの正しい署名であるか検証する、
（３）前記開示装置および前記署名装置はｍｓｇ，Ｔを入力し、
前記開示装置は、Ｉ＝ζ１1/ｘtを計算し、Ｉを前記署名装置に送信し、
前記署名装置は、（ＩＤ，ξｖ）の組からＩ＝ξｖとなるようなξｖを見つけ、該ξｖに対応するＩＤから、ｍｓｇの署名Ｓを生成した署名依頼装置または署名依頼者を特定する、
ことを特徴とする部分ブラインド署名・検証・追跡方法。
【請求項３】
署名依頼装置、署名装置、検証装置および開示装置を備え、請求項１もしくは２に記載の部分ブラインド署名・検証・追跡方法を実施することを特徴とする部分ブラインド署名・検証・追跡システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は電子署名の応用技術であり、特にブラインド署名方式と呼ばれる、署名者に対して署名対象文書の秘匿を目的とする署名方式の機能拡張技術に関する。
【背景技術】
【０００２】
署名依頼者のプライバシ保護および不正防止を両立させるための署名技術として、署名依頼者の追跡機能を有するブラインド署名方式が知られている（例えば非特許文献１）。これはＦair  Ｂlind  Ｓignature（ＦＢＳ）と呼ばれ、署名依頼者が署名者に対して署名依頼文書を伏せたまま署名付与してもらうことができる、ブラインド署名と呼ばれる技術の拡張であり、ある権限者（開示機関）だけは、ブラインド署名によって生成された特定の署名付き文書から署名依頼者を識別する、あるいは特定の署名依頼者に対応する署名付き文書を識別することが可能な技術である。また最近では、ＦＢＳのある種の安全性が証明された方式も提案されている（非特許文献２）。
【０００３】
さらに、署名者をＣＡ（Ｃertificate  Ａithority）、署名依頼文書を署名公開鍵とし、署名依頼者はＣＡに対してＦＢＳを用いて該署名公開鍵を知られることなく鍵証明書を発行してもらうことで、ＣＡは開示機関と協力しない限りは、署名依頼者と署名公開鍵との対応関係を知ることができないような方式も提案されている（非特許文献３）。このような権限分散手法を用いることで、ユーザ（＝署名依頼者）からみたサービス提供者（＝ＣＡ、開示機関）に対する信頼性向上、およびサービス提供者の情報漏洩防止といった効果が期待できる。
【０００４】
【非特許文献１】Ｍ．Ｓtadler，Ｊ．Ｍ．Ｐiveteau，and  Ｊ．Ｃamenisch，“Ｆair  blind  signatures，”ＥＵＲＯＣＲＹＰＴ  ’95，ＬＮＣＳ  ９２１，pp．２０９−２１９，Ｓpinger  Ｖerlag，１９９５
【非特許文献２】Ｍ．Ａbe  and  Ｍ．Ｏhkubo，“Ｐrovably  secure  fair  blind  signatures  with  tight  revocation，”ＡＳＩＡＣＲＹＯＴ  ’０１，ＬＮＣＳ  ２２４８，pp．５８３−６０１，Ｓpinger  Ｖerlag，２００１
【非特許文献３】千田、谷口、塩野入、金井  「代理アクセスを利用した匿名認証方式」  情報処理学会研究報告  Ｖol．２００５，Ｎo．３３，pp．２３５−２４０，２００５
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述のようなＦＢＳを鍵証明書の発行に応用した方式は、該鍵証明書に有効期限やユーザ属性等のオープンな情報を記述できることが望ましいと考えられる。例えばＩＴＵ（国際電気通信連合）が定めた鍵証明書の仕様であるＸ．５０９ｖ３の証明書フォーマットでは、バージョン情報や証明書番号、署名アルゴリズムといった情報が含まれる。以降、この種の鍵証明書に埋め込むオープンな情報をInfoと表記する。しかしながら、署名者、署名依頼者及び検証者に対してオープンな情報を署名依頼文書に埋め込み、かつ追跡機能を有するようなブラインド署名方式は、現在まで提案されていない。
【０００６】
本発明は、このような状況に鑑みてなされたもので、追跡機能を有するブラインド署名（ＦＢＳ）を部分ブラインド署名（ＰＢＳ；Ｐartially  Ｂlind  Ｓignature）に拡張し、署名者がＩnfoを鍵証明書にオープンな情報として記述することが可能な、追跡機能を有する部分ブラインド署名・検証・追跡方法及びシステムを提供することにある。
【課題を解決するための手段】
【０００７】
部分ブラインド署名（ＰＢＳ）は、署名者に対して部分的に伏せた文書を署名依頼することが可能な技術である。これについては、例えば文献「Ｍ．Ａbe  and  Ｔ．Ｏkamato，“Ｐrovably  secure  partially  blind  signatures，“ＣＲＹＰＴＯ，‘００，ＬＮＣＳ  １８８０，pp．２７１−２８６，Ｓpringer  Ｖerlag，２０００」（以下、非特許文献４）に詳述されている。
【０００８】
本発明は、ＦＢＳをＰＢＳに拡張し、任意のブラインド署名で用いる群の元を、オープンな情報Ｉnfoを用いて生成する。例えば非特許文献４で提案されているＦＢＳでは、ｐ，ｑを素数とし、Ｈ１（・）を任意のビット列から群Ｚｐ＊に写すハッシュ関数とし、ｇ，ｈ，ｙをＺｐ＊の元として、署名者はｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ）を生成するが（‖はデータの連結を表す）、本発明では、ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ‖Info）とする、あるいはｇ，ｈ，ｙの何れかを同様の操作により生成することで、非特許文献４のＦＢＳをＰＢＳとできる。
【０００９】
また、本発明は、上記のようにInfoを含めて群の元を構成するのではなく、事前に決定されたInfoを定数として署名発行処理及び署名検証処理で該Infoを利用するようにプロトコルを変更することで、ＦＢＳをＰＢＳに拡張する。
【発明の効果】
【００１０】
本発明によれば、署名者などが指定したオープンな情報を含み、かつ追跡機能を有するようなブラインド署名を生成することができる。これにより、追跡機能を有するブラインド署名を応用した鍵証明書発行方式のより柔軟な運用が可能となる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明の実施の形態について図面を参照して詳述する。なお、本発明は追跡機能を有するブラインド署名（ＦＢＳ）を部分ブラインド署名（ＰＢＳ）に拡張するものであるが、高いセキュリティを有することが望ましいという理由から、以下の第１，２の実施の形態ともに、非特許文献２で提案された（ある種の安全性が保証された）ＦＢＳを元にＰＢＳへ拡張する例について説明する。但し、本発明の拡張は非特許文献２のＦＢＳに限ったものではなく、他のＦＢＳに容易に適用できることは言うまでもない。
【００１２】
［第１の実施の形態］
本実施の形態は、署名者が指定したオープンな情報Ｉnfoを含み、かつ追跡機能を有するようなブラインド署名を生成するもので、以下では、非特許文献２で提案されているＦＢＳに対して、非特許文献４で提案されているＰＢＳの技術を適用することでＰＢＳの機能を追加する方法について、図面を用いて説明する。
【００１３】
図１は本実施の形態のシステム構成を示す図であり、署名依頼装置１０、署名装置２０、検証装置３０、開示装置（管理装置）４０、及びこれら装置を結ぶネットワーク５０からなる。署名依頼装置１０には、パソコン、携帯端末、携帯電話、その他、利用者が操作する任意の機器（利用者端末装置）が含まれる。署名装置２０、検証装置３０、開示装置４０はサーバ装置であり、その具体的構成は所謂コンピュータシステムと同様である。
【００１４】
署名依頼装置１０、署名装置２０、検証装置３０、開示装置４０では、ＦＢＳのシステムパラメータｐｒｍ＝（ｐ，ｑ，ｇ，ｈ）が生成、共有されているものとする。ここでｐ，ｑはｑ｜ｐ−１となる素数、ｇ，ｈは乗法群Ｚｐ＊の位数ｑの部分群Ｇの元である。
【００１５】
＜鍵生成＞
署名装置２０は秘密鍵ｘを生成・保管し、公開鍵ｙ＝ｇｘmodｐを計算する。ここで、ｘはｑ以下のランダムな自然数である。また、開示装置４０は秘密鍵ｒｓｋ＝（ｘｔ，ｄｋ）を生成・保管し、公開鍵ｒｐｋ＝（ｙｔ＝ｇｘｔmodｐ，ｅｋ）を計算する。ここで、ｘｔはｑ以下のランダムな自然数、ｅｋ，ｄｋはそれぞれある検証可能暗号（ＶＥ；Ｖerifiable  Ｅncryption）の公開鍵および秘密鍵である。なお、ＶＥの説明および具体例は非特許文献２に示されている。全ての装置１０〜４０がｙ，ｒｐｋを共有する。署名依頼装置１０はＲＳＡ署名やＳchnorr署名など、任意の署名方式の秘密鍵、公開鍵の組（Ｓｋ，ＰＫ）を作成する。図１に、ここまでの各装置１０〜４０が保持する情報を示す。
【００１６】
＜ブラインド署名＞
署名依頼装置１０は、署名装置２０にＰＫの鍵証明書生成を依頼する。鍵証明書生成の処理は非特許文献２のＦＢＳとほぼ等しいが、Ｇの元ｚの生成が異なる。非特許文献２ＦＢＳでは、以下のようにしてｚを生成している。  
ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ）
ここでＨ１は任意のビット列であるｐ‖ｑ‖ｇ‖ｈ‖ｙをＧに写す一方向性ハッシュ関数である。本実施の形態では、該ＦＢＳにＰＢＳの機能を追加するために、ｚを以下のようにして生成する。
ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ‖Info）
【００１７】
ここでInfoは署名装置２０が指定したオープンな情報である。なお、Infoの埋め込みについて、基本的には一意的に生成されない元であれば、上記同様の方法によりｚ以外の値に対してもInfoの埋め込みが可能である。
【００１８】
以上を踏まえ、署名依頼装置１０がＰＫの鍵証明書を取得する手順について説明する。図２に、本実施の形態における鍵証明書生成の詳細な処理フローを示す。  
署名依頼装置１０は署名装置２０に鍵証明書の生成を依頼する（ステップ１０１）。署名装置２０は特定の文字列Infoを署名依頼装置１０に返す（ステップ１０２）。また、署名装置２０は署名依頼装置１０（または署名依頼者）を識別する情報（ＩＤ）を登録する（ステップ１０３）。
【００１９】
署名依頼装置１０では、以下の処理を行う。  
（ａ）ｑ以下のランダムな自然数γをブラインド係数として選ぶ（ステップ１０４）。
（ｂ）ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ‖Info），ｚｕ＝ｚ１/γ，ξ＝ｇγ，Ｅ＝εｅｋ（γ），Ｐ＝Γ（（ｚｕ，ξ），γ，ｅｋ）を計算する（ステップ１０５）。ここで、εは検証可能暗号（ＶＥ）の暗号化関数であり、Ｅ＝εｅｋ（γ）は該ＶＥの関数を用いて公開鍵ｅｋによりγを暗号化した暗号文である。ΓはＥに対応する平文（＝γ）が１／logｚｚｕ（＝γ）およびlogｇξ（＝γ）と等しいことを署名装置２０にゼロ知識証明するための関数であり、Ｐは該証明のための述語（predicate）である。  
（ｃ）（ｚｕ，ξ，Ｅ，Ｐ）を署名装置２０に送信する（ステップ１０６）。
【００２０】
署名依頼装置１０から（ｚｕ，ξ，Ｅ，Ｐ）を受信した署名装置２０は以下の処理を行う。
（ａ）ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ‖Info）を計算し、（ｚｕ，ξ，Ｅ，Ｐ）が正しい結果かどうか検証する（ステップ１０７）。検証ＯＫであれば次に進み、ＮＧであれば署名依頼装置１０の不正として処理を終了する。
（ｂ）ｑ以下のランダムな自然数ｖ，ｕ，ｓ１，ｓ２，ｄを選ぶ（ステップ１０８）。
（ｃ）ｚ１＝ｙｔｖ，ｚ２＝ｚｕ／ｚ１，Ｐｓ＝Γｓ（ｚ１，ｙｔ，ｖ），ａ＝ｇｕ，ｂ１＝ｇｓ1ｚ１ｄ，ｂ２＝ｈｓ２ｚ２ｄを計算する（ステップ１０９）。ここで、Γｓはlogｙｔｚ１（＝ｖ）の値を知っていることを署名依頼装置１０にゼロ知識証明する関数であり、Ｐｓは該証明のための述語である。
（ｄ）（Ｐｓ，ｚ１，ａ，ｂ１，ｂ２）を署名依頼装置に送信する(ステップ１１０)。
（ｅ）ξｖを計算する（ステップ１１１）。
（ｆ）ＩＤとξｖの対応を示す（ＩＤ，ξｖ）の組を保存する（ステップ１１２）。
【００２１】
署名装置２０から（Ｐｓ，ｚ１，ａ，ｂ１，ｂ２）を受信した署名依頼装置１０は以下の処理を行う。  
（ａ）（ｚ１，ｂ１，ｂ２）がＧの元かどうか、および（ｚ１，ｙｔ，Ｐｓ）が正しい結果かどうか検証する（ステップ１１３）。両方とも検証ＯＫであれば次に進み、どちらか一方でもＮＧであれば署名装置の不正として処理を終了する。
（ｂ）ｑ以下のランダムな自然数ｔ１，ｔ２，ｔ３，ｔ４，ｔ５を選ぶ（ステップ１１４）。
（ｃ）ζ１＝ｚ１γ，ζ２＝ｚ／ζ１，α＝ａｇt１ｙｔ２，β１＝ｂ１γｇｔ３ζ１ｔ５，β２＝ｂ２γｈｔ４ζ２ｔ５，ε＝Ｈ２（ζ１‖α‖β１‖β２‖ＰＫ），ｅ＝ε−ｔ２−ｔ５を計算する（ステップ１１５）。ここでＨ２は任意の文字列をｑ以下の自然数に写す一方向性ハッシュ関数とする。
（ｄ）ｅを署名装置２０に送信する（ステップ１１６）。
【００２２】
署名依頼装置１０からｅを受信した署名装置１０は以下の処理を行う。
（ａ）ｃ＝ｅ−ｄ，ｒ＝ｕ−ｃｘを計算する（ステップ１１７）。
（ｂ）((ｒ，ｃ，ｓ１，ｓ２，ｄ)を署名依頼装置１０に送信する(ステップ１１８)。
【００２３】
署名装置２０から（ｒ，ｃ，ｓ１，ｓ２，ｄ）を受信した署名依頼装置１０は以下の処理を行う。  
（ａ）ρ＝ｒ＋ｔ１，ω＝ｃ＋ｔ２，σ１＝γｓ１＋ｔ３，σ２＝γｓ２＋ｔ４，δ＝ｄ＋ｔ５を計算する（ステップ１１９）。  
（ｂ）ω＋δ＝Ｈ２（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2ζ２δ‖ＰＫ）が成り立つかどうか検証する（ステップ１２０）。検証ＯＫであれば次に進み、ＮＧであれば署名装置２０の不正として処理を終了する。  
（ｃ）Σ＝（ζ１，ρ，ω，σ１，σ２，δ）をＰＫの証明書として出力する（ステップ１２１）。
【００２４】
＜署名検証＞
署名装置２０よりＰＫの証明書Σ＝（ζ１，ρ，ω，σ１，σ２，δ）を得た署名依頼装置１０は、（ＳＫ，ＰＫ）を用いてメッセージｍｓｇに対する署名Ｓを生成し、Ｔ＝（Ｓ，ＰＫ，Info，Σ）を鍵証明書を含んだ署名の組とする。
【００２５】
署名検証は、ＰＫの鍵証明書の正当性検証とメッセージｍｓｇの署名Ｓの正当性検証からなるとする。図３に、本実施の形態における署名検証の処理フローを示す。  
署名依頼装置１０は、ｍｓｇ，Ｔを検証装置３０へ送信する（ステップ２０１）。ここで、Ｔ＝(Ｓ，ＰＫ，Info，Σ)であり、Σ＝(ζ１，ρ，ω，σ１，σ２，δ)である。
【００２６】
署名依頼装置１０から（ｍｓｇ，Ｔ）を受信した検証装置３０は以下の処理を行う。  
（ａ）Infoが所定の条件を満たすものであるか確認する（ステップ２０２）。ＯＫであれば次に進み、ＮＧであれば処理を終了する。  
（ｂ）ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ‖Info）を計算する（ステップ２０３）。  
（ｃ）ω＋δ＝Ｈ２（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2(ｚ／ζ１δ)‖ＰＫ）が成り立つかどうか検証する（ステップ２０４）。検証ＯＫであれば次に進み、ＮＧであれば署名装置２０の不正として処理を終了する。  
（ｄ）ＰＫに対応する署名方式の検証アルゴリズムを用いて、Ｓがｍｓｇの正しい署名であるか検証する（ステップ２０５）。検証ＮＧであれば署名装置２０の不正とする。
【００２７】
上記処理において、ステップ２０２〜２０４はＰＫの鍵証明書の正当性検証であり、ステップ２０５はメッシセージｍｓｇの署名Ｓの正当性検証である。
【００２８】
＜署名追跡＞
これは、例えば、メッセージｍｓｇが不正なメッセージだとして、メッセージｍｓｇの署名Ｓの生成者を特定したい場合に実施する。図４に、本実施の形態における署名追跡の処理フローを示す。  
１．検証装置３０は、ｍｓｇ，Ｔを開示装置４０、署名装置２０に送信する（ステップ３０１）。  
２．開示装置４０および署名装置２０は検証装置３０と同様の検証処理（図３）を行い、検証ＯＫとなることを確認する（ステップ３０２）。もしＮＧであれば処理を終了する。
【００２９】
３．開示装置４０は以下の処理を行う。  
（ａ）Ｉ＝ζ１1/ｘtを計算する（ステップ３０３）。  
（ｂ）Ｉを署名装置２０に送信する（ステップ３０４）。
【００３０】
４．開示装置４０からＩを受信した署名装置２０は以下の処理を行う。  
（ａ）保持してある（ＩＤ，ξｖ）からＩ＝ξｖとなるようなξｖを見つける（ステップ３０５）。  
（ｂ）該ξｖに対応するＩＤから、ｍｓｇの署名Ｓを生成した署名依頼装置（または署名依頼者）を特定する（ステップ３０６）。ここでは署名依頼者とする。  
（ｃ）特定した署名依頼者を開示装置４０に送信する（ステップ３０７）。  
５．開示装置４０は署名装置２０から送られた署名依頼者を検証装置３０に送信する（ステップ３０８）。
【００３１】
これにより、開示装置２０及び署名装置４０が協力した場合に限り、メッセージｍｓｇの署名Ｓを生成した署名依頼装置（又は署名依頼者）を特定することができる。
【００３２】
［第２の実施の形態］
本実施の形態では、非特許文献２で提案されているＦＢＳに対して、署名装置と署名依頼装置が事前に合意して得られる共通情報Infoを、署名発行処理および署名検証処理で定数として用いる必要があるようにすることで、ＰＢＳの機能を追加する方法について説明する。
【００３３】
本実施の形態のシステム構成は、第１の実施の形態と同様であり、図１に示すように、署名依頼装置１０、署名装置２０、検証装置３０、開示装置４０、及びこれら装置を結ぶネットワークからなる。署名依頼装置１０、署名装置２０、検証装置３０、開示装置４０では、第１の実施の形態と同様に、ＦＢＳのシステムパラメータｐｒｍ＝（ｐ，ｑ，ｇ，ｈ）が生成、共有されているものとする。ここでｐ，ｑはｑ｜ｐ−１となる素数、ｇ，ｈは乗法群Ｚｐ*の位数ｑの部分群Ｇの元である。
【００３４】
＜鍵生成＞
署名装置２０は秘密鍵ｘを生成・保管し、ｙ＝ｇｘmodｐを計算する。ここで、ｘはｑ以下のランダムな自然数である。開示装置４０は秘密鍵ｒｓｋ＝（ｘｔ，ｄｋ）を生成・保管し、ｒｐｋ＝（ｙｔ＝ｇｘｔ（modｐ），ｅｋ）を計算する。ここでｘｔはｑ以下のランダムな自然数、ｅｋ，ｄｋはそれぞれある検証可能暗号（ＶＥ；Ｖerifiable  Ｅncryption）の公開鍵および秘密鍵である。全ての装置１０〜４０がｙ，ｒｐｋを共有する。署名依頼装置１０はＲＳＡ署名やＳchnorr署名など、任意の署名方式の秘密鍵、公開鍵の組（ＳＫ，ＰＫ）を作成する。ここまでは、第１の実施の形態と同じである。
【００３５】
＜ブラインド署名＞
署名依頼装置１０は、署名装置２０にＰＫの鍵証明書生成を依頼する。鍵証明書生成の処理は、第１の実施の形態と同様であるが、非特許文献２のＦＢＳの署名発行処理において、以下の変更を行えば良い。  
ｚ２＝ｚｕ／ｚ１  →  ｚｕ／ｚ１Info
ζ２＝ｚ／ζ１  →  ｚ／ζ１Info
ω＋δ＝Ｈ（（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2(ｚ／ζ１)δ‖ｍｓｇ）
→  Ｈ（（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2(ｚ／ζ１info)δ‖ｍｓｇ）
【００３６】
以下では、署名依頼装置１０がＰＫの鍵証明書を取得する手順を上記の変更を踏まえて説明する。処理フローは図２と同様であるので省略する。  
署名依頼装置１０は署名装置２０に鍵証明書の生成を依頼する。署名装置２０は特定の文字列Infoを署名依頼装置１０に返す。ここで、Infoはｑ以下の自然数とする。また、署名装置２０は署名依頼装置１０（または署名依頼者）を識別する情報（ＩＤ）を登録する。
【００３７】
署名依頼装置１０は以下の処理を行う。  
（ａ）ｑ以下のランダムな自然数γ(ブラインド係数)を選ぶ。  
（ｂ）ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ），ｚｕ＝ｚ１/γ，ξ＝ｇγ，Ｅ＝εｅｋ（γ），Ｐ＝Γ（（ｚｕ，ξ），γ，ｅｋ）を計算する。ここでεはＶＥの暗号化関数であり、特にＥ＝εｅｋ（γ）は該ＶＥの関数を用いて公開鍵ｅｋによりγを暗号化した暗号文である。ΓはＥに対応する平文（＝γ）が１／logｚｚｕ（＝γ）およびlogｇξ（＝γ）と等しいことを署名装置２０にゼロ知識証明するための関数であり、特にＰは該証明のための述語（predicate）である。
【００３８】
（ｃ）（ｚｕ，ξ，Ｅ，Ｐ）を署名装置２０に送信する。
【００３９】
署名依頼装置１０から（ｚｕ，ξ，Ｅ，Ｐ）を受信した署名装置２０は以下の処理を行う。  
（ａ）ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ）を計算し、（ｚｕ，ξ，Ｅ，Ｐ）が正しい結果かどうか検証する。検証ＯＫであれば次に進み、ＮＧであれば署名依頼装置１０の不正として処理を終了する。  
（ｂ）ｑ以下のランダムな自然数ｖ，ｕ，ｓ１，ｓ２，ｄを選ぶ。  
（ｃ）ｚ１＝ｙｔｖ，ｚ２＝ｚｕ／ｚ１Info，Ｐｓ＝Γｓ（ｚ１，ｙｔ，ｖ），ａ＝ｇｕ，ｂ１＝ｇｓ１ｚ１ｄ，ｂ２＝ｈｓ２ｚ２ｄを計算する。ここでΓｓはlogｙｔｚ１（＝ｖ）の値を知っていることを署名依頼装置１０にゼロ知識証明するための関数であり、Ｐｓは該証明のための述語である。  
（ｄ）（Ｐｓ，ｚ１，ａ，ｂ１，ｂ２）を署名依頼装置１０に送信する。  
（ｅ）ξｖを計算する。  
（ｆ）（ＩＤ，ξｖ）の組を保存する。
【００４０】
署名装置２０から（Ｐｓ，ｚ１，ａ，ｂ１，ｂ２）を受信した署名依頼装置１０は以下の処理を行う。  
（ａ）（ｚ１，ｂ１，ｂ２）がＧの元かどうか、および（ｚ１，ｙｔ，Ｐｓ）が正しい結果かどうか検証する。両方とも検証ＯＫであれば次に進み、どちらか一方でもＮＧであれば署名装置２０の不正として処理を終了する。  
（ｂ）ｑ以下のランダムな自然数ｔ１，ｔ２，ｔ３，ｔ４，ｔ５を選ぶ。  
（ｃ）ζ１＝ｚ１γ，ζ２＝ｚ／ζ１Info，α＝ａｇｔ1ｙｔ2，β１＝ｂ１γｇｔ3ζ１ｔ5，β２＝ｂ２γｈｔ4ζ２ｔ5，ε＝（ζ１‖α‖β１‖β２‖ＰＫ），ｅ＝ε−ｔ２−ｔ５を計算する。ここでＨ２は任意の文字列をｑ以下の自然数に写す一方向性ハッシュ関数とする。  
（ｄ）ｅを署名装置２０に送信する。
【００４１】
署名依頼装置１０からｅを受信した署名装置２０は以下の処理を行う。  
（ａ）ｃ＝ｅ−ｄ，ｒ＝ｕ−ｃｘを計算する。  
（ｂ）（ｒ，ｃ，ｓ１，ｓ２，ｄ）を署名依頼装置１０に送信する。
【００４２】
署名装置２０から（ｒ，ｃ，ｓ１，ｓ２，ｄ）を受信した署名依頼装置１０は以下の処理を行う。  
（ａ）ρ＝ｒ＋ｔ１，ω＝ｃ＋ｔ２，σ１＝γｓ１＋ｔ３，σ２＝γｓ２＋ｔ４，δ＝ｄ＋ｔ５を計算する。  
（ｂ）ω＋δ＝Ｈ２（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2ζ２δ‖ＰＫ）が成り立つかどうか検証する。検証ＯＫであれば次に進み、ＮＧであれば署名装置２０の不正として処理を終了する。  
（ｃ）Σ＝（ζ１，ρ，ω，σ１，σ２，δ）をＰＫの証明書として出力する。
【００４３】
＜署名検証＞
本実施の形態における署名検証の処理フローを図５に示す。署名装置２０よりＰＫの証明書Σ＝（ζ１，ρ，ω，σ１，σ２，δ）を得た署名依頼装置１０は、次に（ＳＫ，ＰＫ）を用いてメッセージｍｓｇに対する署名Ｓを生成し、Ｔ＝（Ｓ，ＰＫ，Info，Σ）を鍵証明書を含んだ署名の組とする。
【００４４】
署名依頼装置１０は、メッセージｍｓｇ，Ｔ＝（ｓ，ＰＫ，info，Σ）を検証装置３０に送信する（ステップ４０１）。
【００４５】
署名依頼装置１０から，ｍｓｇ，Ｔを受信した検証装置３０は、以下の処理を行う。  
（ａ）Infoが所定の条件を満たすものであるか確認する（ステップ４０２）。ＯＫであれば次に進み、ＮＧであれば処理を終了する。  
（ｂ）ｚ＝Ｈ１（ｐ‖ｑ‖ｇ‖ｈ‖ｙ）を計算する（ステップ４０３）。  
（ｃ）ω＋δ＝Ｈ２（ζ１‖ｇρｙω‖ｇσ1ζ１δ‖ｈσ2（ｚ／ζ1Info）δ‖ＰＫ）が成り立つかどうか検証する（ステップ４０４）。検証ＯＫであれば次に進み、ＮＧであれば署名装置２０の不正として処理を終了する。  
（ｄ）ＰＫに対応する署名方式の検証アルゴリズムを用いて、Ｓがｍｓｇの正しい署名であるか検証する（ステップ４０５）。検証ＮＧであれば署名装置２０の不正とする。
【００４６】
上記処理において、ステップ４０２〜４０４はＰＫの鍵証明書の正当性検証であり、ステップ４０５はｍｓｇの署名Ｓの正当性検証である。
【００４７】
＜署名追跡＞
メッセージｍｓｇは不正なメッセージだとして、該ｍｓｇの署名Ｓの生成者を特定したい場合、検証装置３０は開示装置４０および署名装置２０にｍｓｇ，Ｔを送付にする。開示装置４０および署名装置２０はｍｓｇ，Ｔを入力して以下の処理を行う。
【００４８】
１．開示装置４０および署名装置２０は検証装置３０と同様の検証の処理（図５）を行い、検証ＯＫとなることを確認する。もしＮＧであれば処理を終了する。  
２．開示装置４０は以下の処理を行う。  
（ａ）Ｉ＝ζ１１／ｘｔを計算する。  
（ｂ）Ｉを署名装置２０に送信する。  
３．開示装置４０からＩを受信した署名装置２０は以下の処理を行う。  
（ａ）（ＩＤ，ξｖ）からＩ＝ξｖとなるようなξｖを見つける。  
（ｂ）該ξｖに対応するＩＤから、メッセージｍｓｇの署名Ｓを生成した署名依頼装置（または署名依頼者）を特定する。
【００４９】
上記処理は図４と同様である。これにより、開示装置４０および署名装置３０が協力した場合に限り、メッセージｍｓｇの署名Ｓを生成した署名依頼装置（または署名依頼者）を特定することが出来る。
【００５０】
なお、図１で示したシステム構成における各装置の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２〜図５で示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００５１】
【図１】本発明の実施の形態のシステム構成を示す図。
【図２】第１の実施の形態における鍵証明書生成の処理フロー図。
【図３】第１の実施の形態における署名検証の処理フロー図。
【図４】第１の実施の形態における署名追跡の処理フロー図。
【図５】第２の実施の形態における署名検証の処理フロー図。
【符号の説明】
【００５２】
１０  署名依頼装置
２０  署名装置
３０  検証装置
４０  開示装置
５０  ネットワーク
【図１】
0004577720.tif 000002
【図２】
0004577720.tif 000003
【図３】
0004577720.tif 000004
【図４】
0004577720.tif 000005
【図５】
0004577720.tif 000006