匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、追跡機能付き匿名署名システム、それらの方法及びプログラム
【課題】追跡機能付きのリング署名方式にランダムオラクルモデルによらずに安全性証明をつける。更に、グループの構成員数がＮの場合に署名の情報量をＯ（√Ｎ）に抑制する。
【解決手段】追跡機能付きのリング署名方式のアルゴリズムを、ＳＤＨ（Strong Diffie-Hellman）仮定に基づき構成する。また、ＲとＣとの関連付け、ΣとＬとの関連付け、ΣとＲとの関連付けに際し、それぞれのパラメータを行列にマッピングした上で、証明を作成しそれを検証する。
【解決手段】追跡機能付きのリング署名方式のアルゴリズムを、ＳＤＨ（Strong Diffie-Hellman）仮定に基づき構成する。また、ＲとＣとの関連付け、ΣとＬとの関連付け、ΣとＲとの関連付けに際し、それぞれのパラメータを行列にマッピングした上で、証明を作成しそれを検証する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループの一員による署名であるが誰が署名をしたかは特定することができないグループ匿名署名を行うための、匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、追跡機能付き匿名署名システム、それらの方法及びプログラムに関する。
【背景技術】
【０００２】
リング署名方式はグループ署名方式の一種であり、管理者を置くことなく、署名者が構成員を自由に選定してグループ（リング）を構成することができる。この方式では、グループのどの構成員も署名をすることができるが、検証者はグループのいずれかの構成員が署名したことは検証できるにとどまり、どの構成員が署名したのかは特定することはできない。そのため、基本的には完全な匿名性が保障される。
【０００３】
しかしながら、このような完全な匿名性という性質により、例えば１つのメッセージテーマ（issue）に対して構成員ごとに１回の署名（メッセージ投稿）のみを認めるという制約を設けたくても、匿名であるが故、設けられないというような問題があった。
【０００４】
そこで、そのような問題に対処すべく考案された追跡機能付きのリング署名方式（例えば、非特許文献１、２）が開示されている。非特許文献１、２の方式では、タグを利用してリング署名を構成する。署名者はタグごとに一度だけ署名を生成することができる。署名者が同じタグを用いて別のメッセージの署名生成を試みた場合、その署名者が暴露される。また、リング署名の構成員である署名者以外の者がそのリング署名の生成に用いたタグやメッセージに対して真の署名者に成りすまして署名を生成しようとしても、署名を作成することができない。このような方式は、例えば電子投票等に利用した場合、投票者の匿名性を保持した上で、「二重投票を追跡できる」「偽造投票を阻止できる」などの利点がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】E. Fujisaki and K. Suzuki、"Traceable ring signature"、Public Key Cryptography-PKC 2007、LNCS 4450、Springer-Verlag、2007年、p.181-200
【非特許文献２】E. Fujisaki and K. Suzuki、"Traceable ring signature"、IEICE TRANS. FUNDAMENTLS, E91-A(1)、2008年1月、p.83-93
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１、２の追跡機能付きのリング署名方式は、安全性証明がランダムオラクルモデル（参考文献１参照）に基づいているが、ランダムオラクルによる安全性証明の場合、例えば参考文献２で示されているように、ランダムオラクルで安全であると証明された方式であっても、現実にはどう実装しても安全でない方式が存在する。そのため、より一層の安全性を担保するには数学的な根拠に基づき安全性証明がつくことが望ましい。
［参考文献１］M. Bellare and P. Rogaway、"Random Oracles are Practical: A Paradigm for Designing Efficient Protocols"、Proc. of the First ACM Conference on Computer and Communications Security 、1993年11月、p.62-73
［参考文献２］R. Canetti, O. Goldreich and S.Halevi、"The Random Oracle Methodology, Revisited"、Proc. of ACM STOC98、1998年、p.209-218
ランダムオラクルモデルを用いずに安全性証明を行う署名方式は、例えば参考文献３にて開示されている。参考文献３の署名方式の安全性証明は、ｑ−ＳＤＨ（Strong Diffie-Hellman）仮定に基づくものである。ｑ−ＳＤＨ仮定は大まかには、素数ｐを位数とする巡回群Ｇの生成元をｇとし、ｘ∈Z/pZ（Z/pZはｐを法とする剰余類群）がランダムに与えられたとき、
【０００７】
【数１】
が与えられても、
【０００８】
【数２】
（ｃ∈(Z/pZ)*、(Z/pZ)*はｐと互いに素な剰余類群）を多項式時間内に求めることは困難であるという仮定であり、数学的に安全性を保証することができる。
【０００９】
そこで、本発明の目的は、従来の追跡機能付きのリング署名方式を、参考文献３で開示された署名方式をベースにアルゴリズムを見直すことにより、ランダムオラクルモデルによらずに安全性証明をつけることが可能な追跡機能付きのリング署名方式を実現することにある。
［参考文献３］D. Boneh and X. Boyen、"Short Signatures Without Random Oracles"、Advances In Cryptology-EUROCRYPT 2004、LNCS 3027、Springer-Verlag、2004年、p.56-73
【００１０】
また、非特許文献１、２の追跡機能付きのリング署名方式においては、署名の情報量がグループの構成員数Ｎに比例するＯ（Ｎ）であり、システムへの負荷や処理時間などへの影響が、構成員の増加に比例して大きくなってしまうという問題があった。この点、参考文献４では、追跡機能無しのリング署名方式において、署名の情報量を√Ｎに比例するＯ（√Ｎ）に抑制するアルゴリズムが開示されている。これは大まかには、例えばＣがコミットするｙIと同じ値をコミットする元がＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ }の中に１つ存在することを証明するような場合に、Ｙiを√Ｎ×√Ｎの行列内にマッピングすることで、行又は列単位での署名の証明処理を可能とし、よって署名として必要な情報量の圧縮を図るものである。
【００１１】
そこで本発明は、ランダムオラクルモデルによらずに安全性証明がつく追跡機能付きのリング署名方式において、更に参考文献４で開示されたアルゴリズムを応用することにより、署名の情報量をＯ（√Ｎ）に抑制することもあわせて目的とする。
［参考文献４］N. Chandran, J. Groth, and A. Sahai、"Ring Signatures of Sub-linear Size without Random Oracles"、Automata, Languages and Programming、LNCS 4596、Springer-Verlag、2007年、p.423-434
【課題を解決するための手段】
【００１２】
本発明の追跡機能付き匿名署名システムは、匿名署名生成装置と匿名署名検証装置と匿名署名追跡判定装置とから構成される。当該システムは、位数ｎが大きな素数ｐ、ｑの積である巡回群Ｇと、その生成元ｇと、ｈ∈Ｇ（ｈ≠ｇ）と、zcrs∈Ｇと、位数ｎの巡回群ＧＴと、ペアリング関数ｅ：Ｇ×Ｇ→ＧＴと、ハッシュ関数Ｈ：｛０、１}*→Ｚ／ｎＺと、ハッシュ関数Ｈ´（≠Ｈ）：｛０、１}*→Ｚ／ｎＺと、ランダムな値ｘi∈Ｚ／ｎＺ（Ｚ／ｎＺはｎを法とする剰余類群、ｉ∈{１、２、・・・、Ｎ}は構成員の識別子）に基づき、
【００１３】
【数３】
（ｇxは楕円曲線上の点ｇのスカラー倍（ｘ倍）演算を表す、以下の乗算表記につき同様。）
として得られた各構成員のＢＢ署名検証鍵ｙiのコミットメント
【００１４】
【数４】
（ｄiはランダムな値（ｄi∈Ｚ／ｎＺ）。ｙ・ｈは楕円曲線上の点ｙと点ｈとの楕円加算を表す、以下の積算表記につき同様。）
の集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、が公開され、上記各構成員が自身のＢＢ署名検証鍵ｙiとそれに対応する秘密のＢＢ署名鍵ｘiとを保有するという条件下で用いる。
【００１５】
匿名署名生成装置は、ＯＴ署名鍵生成器と、ハッシュ関数演算器と、ＢＢ署名生成器と、四則演算器と、乱数生成器と、コミットメント生成器と、証明生成器と、ＯＴ署名生成器とから構成される。
ＯＴ署名鍵生成器は、ＯＴ署名鍵skと、それと対応するＯＴ署名検証鍵vkと、を生成して出力する。
【００１６】
ハッシュ関数演算器は、署名対象事項を特定する情報issueと署名対象のメッセージｍと上記Ｒと上記ＯＴ署名検証鍵vkとが入力され、タグＴ＝(issue‖Ｙ１‖Ｙ２‖・・・‖ＹＮ)（‖はビット結合を表す。）を生成し、ハッシュ値Ｈ（Ｔ）、Ｈ´(Ｔ)、Ｈ（Ｔ‖ｍ）、及びＨ(vk)を演算して出力する。
【００１７】
ＢＢ署名生成器は、ｇと、リングの構成員である署名者Ｉ∈｛１、２、・・、Ｎ｝のＢＢ署名鍵ｘIと、ハッシュ値Ｈ(Ｔ)、Ｈ（vk）、及びＨ´(Ｔ)と、が入力され、ＢＢ署名鍵ｘIを用いて当該Ｈ(Ｔ) 、Ｈ（vk）、及びＨ´(Ｔ)のＢＢ署名σI、σvk、及びｚをそれぞれ、
【００１８】
【数５】
により生成し出力する。
四則演算器は、ＢＢ署名σIと、ｇと、ｈと、ハッシュ値Ｈ（Ｔ‖ｍ）とが入力され、Ｑを、
【００１９】
【数６】
により演算するとともに、ハッシュ値Ｈ（Ｔ‖ｍ）とＱとから、ｉ＝Ｉ以外の全てのｉ（１≦ｉ≦ｎ）についてσｉを、σi＝ｇＨ(Ｔ,ｍ)・Ｑｉにより演算し、各演算結果を出力する。
乱数生成器は、ランダムな値η、ｄI、ｓ、ｂ、ｆ、ｒ∈Ｚ／ｎＺをそれぞれ生成して出力するとともに、
【００２０】
【数７】
について、
【００２１】
【数８】
をランダムに生成して出力する。
【００２２】
コミットメント生成器は、ｈと、ＢＢ署名検証鍵ｙIと、ＢＢ署名σI、σvk、及びｚと、値ｄI、ｓ、ｂ、及びｆとが入力され、ＢＢ署名検証鍵ｙIのコミットメントＣ、ＢＢ署名σIのコミットメントＬ、ＢＢ署名σvkのコミットメントＬvk、及びＢＢ署名ｚのコミットメントＬzを、それぞれ、
【００２３】
【数９】
により生成して出力する。
【００２４】
証明生成器は、ｇと、ｈと、ＢＢ署名鍵ｘIと、ＢＢ署名検証鍵ｙIと、ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、Ｈ(Ｔ‖ｍ）、及びＨ´(Ｔ）と、ＢＢ署名ｚと、コミットメントＬ、Ｌvk、及びＬzと、値ｓ、ｒ、η、ｆ、ｔτ、λτ、ｗτ、ｔτ´、λτ´、及びｗτ´（１≦τ≦√Ｎ）と、上記集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、上記σｉ（１≦ｉ≦ｎ、ｉ＝Ｉを含む）と、が入力され、Ｑがｇχという形をしていることの証明πＱを、
【００２５】
【数１０】
により生成し、署名者ＩのＨ(Ｔ)のＢＢ署名σＩが署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明πＣ,Ｌを、
πＣ,Ｌ＝(ｇＨ(Ｔ)・ｙＩ)ｓ・Ｌｒ
により生成し、署名者ＩのＨ（vk）のＢＢ署名σvkが署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【００２６】
【数１１】
により生成し、また、ｚがｇχという形をしていることの証明πｚを、
【００２７】
【数１２】
により生成し、Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの証明
【００２８】
【数１３】
により生成し、署名者ＩのＨ´(Ｔ)のＢＢ署名ｚが署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【００２９】
【数１４】
により生成し、ＣとしてコミットされたＢＢ署名検証鍵ｙIと同じ値がコミットされた元がＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ}の中に一つ存在することを示す証明ΠＲ,Ｃを、
【００３０】
【数１５】
の組として生成し、ＬとしてコミットされたＢＢ署名σIと同じ値がΣ＝{σ１、σ２、・・・、σＮ}の中に一つ存在することを示す証明ΠＬ,Σを、
【００３１】
【数１６】
の組として生成し、証明ΠＲ,ＣでリングＲの中に一つ存在した要素をＹＥ、証明ΠＬ,ΣでΣの中に一つ存在した要素をσＥ´としたとき、Ｅ＝Ｅ´であることを示す証明ΠＲ,Σを、
【００３２】
【数１７】
の組として生成し、生成した各証明を出力する。
【００３３】
ＯＴ署名生成器は、ＯＴ署名検証鍵vkと、ＯＴ署名鍵skと、タグＴと、メッセージｍと、コミットメントＣ、Ｌ、Ｌvk、及びＬzと、ＢＢ署名ｚと、δと、δcrsと、Ｑと、証明
【００３４】
【数１８】
とが入力され、ＯＴ署名鍵skを用いて
【００３５】
【数１９】
の署名sig0を生成し、タグ付き文書（Ｔ、ｍ）のＲに関する匿名署名
【００３６】
【数２０】
を生成し出力する。
【００３７】
匿名署名検証装置は、ＯＴ署名検証器と、ハッシュ関数演算器と、署名検証器とから構成される。
ＯＴ署名検証器は、ＯＴ署名検証鍵vkと、匿名署名
【００３８】
【数２１】
とが入力され、ＯＴ署名検証鍵vkを用いてsig0から
【００３９】
【数２２】
を復号する。
【００４０】
ハッシュ関数演算器は、タグＴと、ＯＴ署名検証鍵vkと、メッセージｍとが入力され、ハッシュ関数Ｈ(Ｔ）、Ｈ（vk）、Ｈ´(Ｔ）、及びＨ(Ｔ‖ｍ)を演算して出力する。
証明検証器は、上記ｇと、上記ｈと、上記ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、Ｈ´(Ｔ）、及びＨ(Ｔ‖ｍ)と、Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、ＯＴ署名検証器で復号された
【００４１】
【数２３】
とが入力され、全てのｉ（１≦σi≦Ｎ）についてσｉ＝ｇＨ(Ｔ,ｍ)・ＱｉによりΣ＝{σ１、σ２、・・・、σＮ}を復元し、
【００４２】
【数２４】
を検証し、更にΠＲ,Ｃに関し、
【００４３】
【数２５】
がすべて成立すること、更にΠＬ,Σに関し、
【００４４】
【数２６】
がすべて成立すること、更にΠＲ,Σに関し、
【００４５】
【数２７】
がすべて成立することをそれぞれ検証し、すべての検証が成功した場合に、sigをタグ付き文書(Ｔ、ｍ)のリングＲに関する正当な匿名署名とみなす。
【００４６】
匿名署名追跡判定装置は、同一のタグＴで文書が異なる２つのタグ付き文書（Ｔ、ｍ）及び（Ｔ、ｍ´）と、これら２つのタグ付き文書についての、各構成員のＢＢ署名検証鍵のコミットメントの集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}に係る２つの正しい匿名署名
【００４７】
【数２８】
とが入力され、各タグ付き文書について、それぞれσｉ＝ｇＨ(Ｔ,ｍ)・Ｑｉ、σｉ´＝ｇＨ(Ｔ,ｍ´)・Ｑ´ｉにより、ＢＢ署名の集合Σ＝{σ１、σ２、・・・、σＮ}、Σ´＝{σ１´、σ２´、・・・、σＮ´}を復元し、ΣとΣ´とを対照してσI＝σI´となる要素が発見された場合に署名者Ｉを出力する。
【発明の効果】
【００４８】
本発明により、ランダムオラクルモデルを用いずに安全性証明がつく追跡機能付きのリング署名方式を実現することができ、なおかつ署名の情報量をＯ（√Ｎに抑制することができる。
【図面の簡単な説明】
【００４９】
【図１】本発明の追跡機能付き匿名署名システム１の機能構成例を示す図。
【図２】本発明の追跡機能付き匿名署名システム１の処理フロー例を示す図。
【図３】Ｑ、ｍに基づき生成したσi（１≦ｉ≦Ｎ）を結んで得られる直線のイメージ図。
【図４】各証明の相関関係を示す図。
【発明を実施するための形態】
【００５０】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００５１】
〔方式の基本要件〕
本発明においては、追跡機能付きのリング署名方式における以下の基本要件を満たすように構成した。
(1)匿名性
同じ署名者が施した署名は、それが各タグにおいて１度目である限り、誰が施したかを特定できない。
(2)タグによる関連付け
同じ署名者によって同じタグに施された署名は関連付けられる。言いかえれば、あるタグに施すことができる署名の数の上限はリングの構成員数である。
(3)追跡・公開性
同じ署名者が、あるタグについて２以上の異なるメッセージに署名を施した場合、その署名者は明らかにされる。
(4)偽造困難性
ある署名者になりすまして署名を偽造することは困難である。
【００５２】
〔アルゴリズム〕
本システムで実現する追跡機能付きのリング署名方式は、準備、署名生成、署名検証、追跡判定の４つのアルゴリズムからなる。これらを追跡機能付き匿名署名システム１０として構成した例を図１に示す。追跡機能付き匿名署名システム１０は、匿名署名生成装置１００と匿名署名検証装置２００と匿名署名追跡判定装置３００とから構成される。
【００５３】
以下、各アルゴリズムについて説明する。
＜準備＞
位数ｎが大きな素数ｐ、ｑの積である巡回群Ｇと、その生成元ｇと、ｈ∈Ｇ（ｈ≠ｇ）と、zcrs∈Ｇと、位数ｎの巡回群ＧＴと、ペアリング関数ｅ：Ｇ×Ｇ→ＧＴと、ハッシュ関数Ｈ：｛０、１}*→Ｚ／ｎＺと、ハッシュ関数Ｈ´（≠Ｈ）：｛０、１}*→Ｚ／ｎＺ、を共通参照情報として公開する。ここで、ペアリング関数ｅとは、２入力１出力の関数で楕円曲線Ｅ上の２点Ｐ、Ｑについて、ｅ(ａＰ、ｂＱ)＝ｅ(Ｐ、Ｑ)ab＝ｅ(ｂＰ、ａＱ)というような双線形性を成立させる関数である。
【００５４】
更に、ランダムな値ｘi∈Ｚ／ｎＺ（Ｚ／ｎＺはｎを法とする剰余類群、ｉ∈{１、２、・・・、Ｎ}は構成員の識別子）に基づき、
【００５５】
【数２９】
（ｇxは楕円曲線上の点ｇのスカラー倍（ｘ倍）演算を表す、以下の乗算表記につき同様。）
として求めた各構成員のＢＢ署名検証鍵ｙiについて、それぞれコミットメントを、
【００５６】
【数３０】
（ｄiはランダムな値（ｄi∈Ｚ／ｎＺ）。ｙ・ｈは楕円曲線上の点ｙと点ｈとの楕円加算を表す、以下の積算表記につき同様。）
により生成し、その集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}を公開する。
また、上記各構成員は、自身のＢＢ署名検証鍵ｙiとそれに対応する秘密のＢＢ署名鍵ｘiとを予め保有する。
【００５７】
＜署名生成＞
図１に署名生成アルゴリズムの処理を担う匿名署名生成装置１００の機能構成ブロックの構成例を、図２に処理フロー例を示す。
匿名署名生成装置１００は、ＯＴ署名鍵生成器１０１と、ハッシュ関数演算器１０２と、ＢＢ署名生成器１０３と、四則演算器１０４と、乱数生成器１０５と、コミットメント生成器１０６と、証明生成器１０７と、ＯＴ署名生成器１０８とから構成される。
【００５８】
ＯＴ署名鍵生成器１０１は、ＯＴ署名鍵skとそれと対応するＯＴ署名検証鍵vkとを生成して出力する（Ｓ１）。本発明においては、上記のＢＢ署名鍵・検証鍵ｘi、ｙiと当該ＯＴ署名鍵・検証鍵sk、vkの２種類の鍵ペアを用いる。ランダムオラクルを用いずに安全性証明がつく参考文献３で開示された署名方式には、短い文書にしか署名がつけられないが、文書に対して署名が一意に決定するＢＢ１署名と、文書に対して署名が一意に確定しないが長い文書に署名がつけられるＢＢ２署名があり、ＢＢ２署名は使い捨ての署名鍵・検証鍵を生成し、ＢＢ１署名で使い捨て検証鍵に署名し、使い捨て署名鍵で長い文書に署名をする方式である。そこで本発明においては、この２つのＢＢ署名を用途によって使い分けてアルゴリズムを構成する。以下、ＢＢ１署名に係る鍵をＢＢ署名鍵・検証鍵と呼び、ＢＢ２署名に係る使い捨ての鍵をＯＴ署名鍵・検証鍵と呼ぶ。なお、ＯＴ署名鍵・検証鍵はその都度使い捨てるため、一度の使用に耐えうる安全性を有する方式であれば、いかなる公開鍵暗号方式によるものでも構わない。
【００５９】
ハッシュ関数演算器１０２には、議題や質問事項などの署名対象事項を特定する情報であるissueと、署名対象のメッセージｍと、各構成員のＢＢ署名検証鍵ｙiのコミットメントＹiの集合であるＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、ＯＴ署名検証鍵vkとが入力される。そして、タグＴ＝issue‖Ｙ１‖Ｙ２‖・・・‖ＹＮ（‖はビット結合を表す。）を生成し、ハッシュ値Ｈ（Ｔ）と、ハッシュ値Ｈ´(Ｔ)と、ハッシュ値Ｈ（Ｔ‖ｍ）と、ハッシュ値Ｈ(vk)とを演算して出力する（Ｓ２）。
【００６０】
ＢＢ署名生成器１０３は、ｇと、リングの構成員である署名者Ｉ∈｛１、２、・・、Ｎ｝のＢＢ署名鍵ｘIと、ハッシュ値Ｈ(Ｔ)と、ハッシュ値Ｈ（vk）とハッシュ値Ｈ´(Ｔ)とが入力され、Ｈ(Ｔ)、Ｈ（vk）、Ｈ´(Ｔ)のＢＢ署名σI、σvk、ｚをそれぞれ、
【００６１】
【数３１】
により生成し、生成した各署名を出力する（Ｓ３）。
四則演算器１０４は、ＢＢ署名σIとｇとハッシュ値Ｈ（Ｔ‖ｍ）とが入力され、Ｑを、
【００６２】
【数３２】
により演算して出力する（Ｓ４）。
【００６３】
ここでＱは、図３に示すような、logｇσIとＨ（Ｔ‖ｍ）とを結ぶ直線の傾きとして観念されるものである。本発明では、このＱとＨ（Ｔ‖ｍ）とに基づき署名者Ｉ以外のグループのメンバｉ（１≦ｉ≦Ｎ）のダミーの署名σiを生成、復元する（ただし復元の際には、署名者Ｉの署名は匿名状態にあるため、他と同様にＱとＨ（Ｔ‖ｍ）とに基づき復元する）。このＮ個のσiを結んだ傾きＱの直線は、あるタグＴについてメッセージｍが異なると（例えばｍ´）図３に示すように傾きがＱ´に変化するが、同じ署名者Ｉが署名している限り、２本の直線は１点（横軸が署名者Ｉの所）で交差する。そのため、検証側で復元されたタグＴについてのメッセージｍとｍ´に対する署名集合Σ＝{σ１、σ２、・・・、σＮ}とΣ´＝{σ１´、σ２´、・・・、σＮ´}とを照合することで、σＩ＝σＩ´が発見された場合には、同じ署名者Ｉが同じタグＴに対し異なる２つのメッセージに署名していると検出することができる。
【００６４】
乱数生成器１０５は、ランダムな値η、ｄI、ｓ、ｂ、ｆ、ｒ∈Ｚ／ｎＺをそれぞれ生成して出力する（Ｓ５）。なお、Ｓ５の処理はＳ１〜Ｓ４と並行して行っても構わない。
【００６５】
コミットメント生成器１０６は、ｈと、ＢＢ署名検証鍵ｙIと、ＢＢ署名σI、σvk、ｚと、ランダム値ｄI、ｓ、ｂ、ｆと、が入力され、ＢＢ署名検証鍵ｙIのコミットメントＣ、ＢＢ署名σIのコミットメントＬ、ＢＢ署名σvkのコミットメントＬvk、ＢＢ署名ｚのコミットメントＬzをそれぞれ、
【００６６】
【数３３】
により生成し出力する（Ｓ６）。このように各情報をコミットして署名生成・検証処理することにより、秘密情報の解読危険性を低減することができる。
【００６７】
証明生成器１０７は、ｇと、ｈと、ＢＢ署名鍵ｘIと、ＢＢ署名検証鍵ｙIと、ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、Ｈ(Ｔ‖ｍ）、Ｈ´(Ｔ）と、ＢＢ署名ｚと、コミットメントＬ、Ｌvk、Ｌzと、ランダム値ｓ、ｒ、η、ｆと、が入力され、以下の各証明を生成し出力する（Ｓ７）。
・Ｑがｇχという形をしていることの証明πＱ
【００６８】
【数３４】
【００６９】
・署名者ＩのＨ(Ｔ)のＢＢ署名σＩが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明πＣ,Ｌ
πＣ,Ｌ＝(ｇＨ(Ｔ)・ｙＩ)ｓ・Ｌｒ
・署名者ＩのＨ（vk）のＢＢ署名σvkが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【００７０】
【数３５】
・ｚがｇχという形をしていることの証明πｚ
【００７１】
【数３６】
・Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの証明
【００７２】
【数３７】
・署名者ＩのＨ´(Ｔ)のＢＢ署名zが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【００７３】
【数３８】
【００７４】
・ＣとしてコミットされたＢＢ署名検証鍵ｙIと同じ値がコミットされた元がＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ}の中に一つ存在することを示す証明ΠR,C
・ＬとしてコミットされたＢＢ署名σIと同じ値がΣ＝{σ１、σ２、・・・、σＮ}の中に一つ存在することを示す証明ΠL,Σ
・証明ΠR,CでリングＲの中に一つ存在した要素をＹE、証明ΠL,Σで上記Σの中に一つ存在した要素をσE´としたとき、Ｅ＝Ｅ´であることを示す証明ΠR,Σ
【００７５】
本発明においては、ハッシュ関数Ｈ´(Ｔ)についてのＢＢ署名ｚを生成し、更にこのｚに係る証明を生成して検証するが、これは次の理由による。先に説明したように、同じ署名者ＩがあるタグＴに対し２つの異なるメッセージｍ、ｍ´に署名した場合、ＱとＨ（Ｔ‖ｍ）に基づき生成したＮ個のσiを結んだ直線と、Ｑ´とＨ（Ｔ‖ｍ´）に基づき生成したＮ個のσi´を結んだ直線と、が１点（横軸が署名者Ｉの所）で交差することから、各メッセージについて生成された２つの署名集合Σ、Σ´において、σＩ＝σＩ´なる要素が存在したことをもって、重複署名がされたと判定する。しかし、悪意を持った２名の構成員が結託することで、２名がそれぞれ生成した直線をＩの所で交差させて誤判定に導くことができる可能性がある。そこで、各構成員のＢＢ署名鍵ｘIとタグＴとから、ハッシュＨとは異なる別のハッシュＨ´を用いて各構成員ごとに一意に定まるＢＢ署名ｚを生成し、このｚについても検証することで、このような結託攻撃を防御することができる。
【００７６】
また、ΠR,C、ΠL,Σ、ΠR,Σの各証明について、ここでは生成方法を特定しないが、これは非特許文献１、２などの従来技術によって生成することが可能なためである。この場合の署名の情報量は従来どおりＯ(Ｎ)となる。署名の情報量をＯ（√Ｎ）に抑制する新たなアルゴリズムについては、実施例２として後述する。
【００７７】
ＯＴ署名生成器１０８には、上記ＯＴ署名検証鍵vkと、上記ＯＴ署名鍵skと、上記タグＴと、上記メッセージｍと、上記コミットメントＣ、Ｌ、Ｌvk、Ｌzと、上記ＢＢ署名ｚと、上記δと、上記δcrsと、上記Ｑと、上記証明
【００７８】
【数３９】
とが入力される。まず、ＯＴ署名鍵skを用いて
【００７９】
【数４０】
の署名sig0を生成する。そして、タグ付き文書（Ｔ、ｍ）の上記Ｒに関する匿名署名
【００８０】
【数４１】
を生成して出力する（Ｓ８）。
【００８１】
＜署名検証＞
図１に署名検証アルゴリズムの処理を担う匿名署名検証装置２００の機能構成ブロックの構成例を、図２に処理フロー例を示す。
匿名署名検証装置２００は、ＯＴ署名検証器２０１とハッシュ関数演算器２０２と証明検証器２０３とから構成される。
ＯＴ署名検証器２０１は、ＯＴ署名検証鍵vkと匿名署名
【００８２】
【数４２】
とが入力され、ＯＴ署名検証鍵vkを用いて、sig0から
【００８３】
【数４３】
を復号する。復号できなかった場合には、不正なＯＴ署名であったと判定する（Ｓ１１）。
【００８４】
ハッシュ関数演算器２０２は、上記タグＴと、上記ＯＴ署名検証鍵vkとが入力され、ハッシュ関数Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）を演算して出力する（Ｓ１２）。
証明検証器２０３は、ｇと、ｈと、ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）と、ＯＴ署名検証器２０１で復号された
【００８５】
【数４４】
【００８６】
とが入力され、以下の各関係式の成立の確認により署名の正当性を検証する（Ｓ１３）。
・Ｑがｇχという形をしていることの確認
ｅ(Ｑ、ｈ)＝ｅ(ｇ、πＱ)
・署名者ＩのＨ(Ｔ)のＢＢ署名σＩが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの確認
ｅ(ｇＨ(Ｔ)・Ｃ、Ｌ)＝ｅ(ｇ、ｇ) ・ｅ(ｈ、πＣ，Ｌ)
・署名者ＩのＨ（vk）のＢＢ署名σvkが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの確認
【００８７】
【数４５】
【００８８】
・ｚがｇχという形をしていることの確認
ｅ(ｚ、ｈ)＝ｅ(ｇ、πＺ)
・Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの確認
δ・δcrs＝ｇ
ｅ(δ、δ・ｇ-1)＝ｅ(δcrs、δcrs・ｇ-1)＝ｅ(ｈ、πδ)
【００８９】
【数４６】
【００９０】
・署名者ＩのＨ´(Ｔ)のＢＢ署名zが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの確認
【００９１】
【数４７】
【００９２】
なお、ΠR,C、ΠL,Σ、ΠR,Σの検証については、ここでは実施方法を特定しないが、これは非特許文献１、２などの従来技術によって実施することが可能なためである。証明生成器１０７において署名の情報量をＯ（√Ｎ）に抑制するアルゴリズムに基づき証明を生成した場合には、後述する実施例２に示すアルゴリズムにより検証する。
【００９３】
以上の各証明の相関関係を図４に示す。
そして、証明検証器２０３におけるすべての検証が成功した場合に、sigをタグ付き文書（Ｔ、ｍ）のリングＲに関する正当な匿名署名とみなす。
【００９４】
＜追跡判定＞
追跡判定アルゴリズムの処理を担う匿名署名追跡判定装置３００の追跡機能付き匿名署名システム１内での位置づけを図１に、システム全体の処理フロー内での位置づけを図２に示す。
匿名署名追跡判定装置３００は、同一のタグＴで文書が異なる２つのタグ付き文書（Ｔ、ｍ）、（Ｔ、ｍ´）と、これら２つのタグ付き文書に対する各構成員のＢＢ署名検証鍵のコミットメントの集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}に関する２つの正しい匿名署名
【００９５】
【数４８】
【００９６】
とが入力され、各タグ付き文書について、それぞれσi＝ｇＨ(Ｔ,ｍ)・Ｑｉ、σi´＝ｇＨ(Ｔ,ｍ´)・Ｑ´ｉにより、ＢＢ署名の集合Σ＝{σ１、σ２、・・・、σＮ}、Σ´＝{σ１´、σ２´、・・・、σＮ´}を復元し、σI(∈Σ)＝σI´(∈Σ´)となる要素が発見された場合に、重複署名がされたと判定し署名者Ｉを出力する（Ｓ２１）。
【００９７】
以上のようなアルゴリズムにより、ランダムオラクルモデルによらずに安全性証明がつく追跡機能付きのリング署名方式を実現することができる。
【実施例２】
【００９８】
実施例２では、参考文献４で開示されたアルゴリズムを実施例１の追跡機能付きのリング署名方式に応用し、署名の情報量をＯ(Ｎ)からＯ(√Ｎ）に抑制するアルゴリズムを説明する。実施例１とは構成は共通であるが、匿名署名生成装置１００については、四則演算器１０４、乱数生成器１０５、及び証明生成器１０７、また匿名署名検証装置２００については、ハッシュ関数演算器２０２、及び証明検証器２０３につき、一部処理が追加される。そこで、ここでは追加部分についてのみ説明し、共通する部分の説明は省略する。
【００９９】
四則演算器１０４は、更に、ハッシュ値Ｈ（Ｔ‖ｍ）とＱとから、ｉ＝Ｉ以外の全てのｉ（１≦ｉ≦ｎ）について、ＢＢ署名σiを、σi＝ｇＨ(Ｔ,ｍ)・Ｑｉにより演算して出力する。
乱数生成器１０５は、更に、
【０１００】
【数４９】
について、
【０１０１】
【数５０】
【０１０２】
をランダムに生成して出力する。なお、Ｉ＝(ｕ−１)√Ｎ＋ｖは、ＢＢ署名σＩ、ＢＢ署名検証鍵のコミットメントＹＩをそれぞれ、√Ｎ×√Ｎの行列上のσｕ,ｖ、Ｙｕ,ｖにマッピングする関係式である。
【０１０３】
証明生成器１０７は、更に、ランダム値ｔτ、λτ、ｗτ、ｔτ´、λτ´、ｗτ´（１≦τ≦√Ｎ）と、集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、ＢＢ署名σi（１≦ｉ≦ｎ、ｉ＝Ｉを含む）と、がそれぞれ入力され、証明ΠＲ,Ｃ、ΠＬ,Σ、ΠＲ,Σをそれぞれ以下のように生成し出力する。
【０１０４】
なお、生成にあたっては、σｉ、Ｙｉ（１≦ｉ≦Ｎ）を、ｉ＝(ε−１)√Ｎ＋φの関係式により√Ｎ×√Ｎの行列上のσε,φ、Ｙε,φ（１≦ε、φ≦√Ｎ）にそれぞれマッピングする。
【０１０５】
【数５１】
【０１０６】
【数５２】
・証明ΠＲ,Σは、以下のπα,α´,ε、πγ,γ´,φの組からなる。
【０１０７】
【数５３】
ハッシュ関数演算器２０２は、更に上記ｍが入力され、ハッシュ関数Ｈ(Ｔ‖ｍ)を演算して出力する。
【０１０８】
証明検証器２０３は、更に上記ハッシュ関数Ｈ(Ｔ‖ｍ)と、Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}とが入力され、まず全てのｉ（１≦σi≦Ｎ）について、σｉ＝ｇＨ(Ｔ,ｍ)・ＱｉによりΣ＝{σ１、σ２、・・・、σＮ}を復元する。そして、証明ΠＲ,Ｃ、ΠＬ,Σ、ΠＲ,Σについて、以下の各関係式の成立を確認することにより署名の正当性を検証する。
●証明ΠＲ,Ｃについて
・各α（又は各γ）がｈχかｇ・ｈχのいずれかの形をしていることの確認
【０１０９】
【数５４】
・各α（又は各γ）のうち１つがｇ・ｈχの形をしていることの確認
【０１１０】
【数５５】
・その１つのα（又はγ）が、各Ｙのうちの１つに対応するものであることの確認
【０１１１】
【数５６】
・その１つのＹが、Ｃ（ｙＩのコミットメント）であることの確認
【０１１２】
【数５７】
【０１１３】
●証明ΠＬ,Σについて、
・各α（又は各γ）がｈχかｇ・ｈχのいずれかの形をしていることの確認
【０１１４】
【数５８】
・各α（又は各γ）のうち１つがｇ・ｈχの形をしていることの確認
【０１１５】
【数５９】
・その１つのα（又はγ）が、各σのうちの１つに対応するものであることの確認
【０１１６】
【数６０】
・その１つのσが、σＩであることの確認
【０１１７】
【数６１】
【０１１８】
●証明ΠＲ,Σについて、
・証明ΠＲ,ＣでリングＲの中に１つ存在した要素をＹＥ、証明ΠＬ,Σで上記Σの中に１つ存在した要素をσＥ´としたとき、Ｅ＝Ｅ´であることの確認
【０１１９】
【数６２】
【０１２０】
以上のように、Ｙi、σiをそれぞれ√Ｎ×√Ｎの行列内にマッピングし、それに基づき証明を生成することで、行又は列単位での署名の証明処理を可能とし、よって署名として必要な情報量を√Ｎに比例するＯ（√Ｎ）に抑制することができる。
【０１２１】
本発明における匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、追跡機能付き匿名署名システム、それらの方法及びプログラムは、上記の実施形態に限定されるものではなく、本発明を逸脱しない範囲で適宜変更が可能である。また、上記に説明した処理は記載の順に従った時系列において実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行してもよい。
【０１２２】
また、匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、又は追跡機能付き匿名署名システムにおける処理機能をコンピュータによって実現する場合、匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、又は追跡機能付き匿名署名システムが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより上記匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、又は追跡機能付き匿名署名システムにおける処理機能がコンピュータ上で実現される。
【０１２３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦自己の記録装置に格納する。そして、処理の実行時、このコンピュータは自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、更に、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータからこのコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって上記の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。また、この形態ではコンピュータ上で所定のプログラムを実行させることにより、匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、又は追跡機能付き匿名署名システムを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【技術分野】
【０００１】
本発明は、グループの一員による署名であるが誰が署名をしたかは特定することができないグループ匿名署名を行うための、匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、追跡機能付き匿名署名システム、それらの方法及びプログラムに関する。
【背景技術】
【０００２】
リング署名方式はグループ署名方式の一種であり、管理者を置くことなく、署名者が構成員を自由に選定してグループ（リング）を構成することができる。この方式では、グループのどの構成員も署名をすることができるが、検証者はグループのいずれかの構成員が署名したことは検証できるにとどまり、どの構成員が署名したのかは特定することはできない。そのため、基本的には完全な匿名性が保障される。
【０００３】
しかしながら、このような完全な匿名性という性質により、例えば１つのメッセージテーマ（issue）に対して構成員ごとに１回の署名（メッセージ投稿）のみを認めるという制約を設けたくても、匿名であるが故、設けられないというような問題があった。
【０００４】
そこで、そのような問題に対処すべく考案された追跡機能付きのリング署名方式（例えば、非特許文献１、２）が開示されている。非特許文献１、２の方式では、タグを利用してリング署名を構成する。署名者はタグごとに一度だけ署名を生成することができる。署名者が同じタグを用いて別のメッセージの署名生成を試みた場合、その署名者が暴露される。また、リング署名の構成員である署名者以外の者がそのリング署名の生成に用いたタグやメッセージに対して真の署名者に成りすまして署名を生成しようとしても、署名を作成することができない。このような方式は、例えば電子投票等に利用した場合、投票者の匿名性を保持した上で、「二重投票を追跡できる」「偽造投票を阻止できる」などの利点がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】E. Fujisaki and K. Suzuki、"Traceable ring signature"、Public Key Cryptography-PKC 2007、LNCS 4450、Springer-Verlag、2007年、p.181-200
【非特許文献２】E. Fujisaki and K. Suzuki、"Traceable ring signature"、IEICE TRANS. FUNDAMENTLS, E91-A(1)、2008年1月、p.83-93
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１、２の追跡機能付きのリング署名方式は、安全性証明がランダムオラクルモデル（参考文献１参照）に基づいているが、ランダムオラクルによる安全性証明の場合、例えば参考文献２で示されているように、ランダムオラクルで安全であると証明された方式であっても、現実にはどう実装しても安全でない方式が存在する。そのため、より一層の安全性を担保するには数学的な根拠に基づき安全性証明がつくことが望ましい。
［参考文献１］M. Bellare and P. Rogaway、"Random Oracles are Practical: A Paradigm for Designing Efficient Protocols"、Proc. of the First ACM Conference on Computer and Communications Security 、1993年11月、p.62-73
［参考文献２］R. Canetti, O. Goldreich and S.Halevi、"The Random Oracle Methodology, Revisited"、Proc. of ACM STOC98、1998年、p.209-218
ランダムオラクルモデルを用いずに安全性証明を行う署名方式は、例えば参考文献３にて開示されている。参考文献３の署名方式の安全性証明は、ｑ−ＳＤＨ（Strong Diffie-Hellman）仮定に基づくものである。ｑ−ＳＤＨ仮定は大まかには、素数ｐを位数とする巡回群Ｇの生成元をｇとし、ｘ∈Z/pZ（Z/pZはｐを法とする剰余類群）がランダムに与えられたとき、
【０００７】
【数１】
が与えられても、
【０００８】
【数２】
（ｃ∈(Z/pZ)*、(Z/pZ)*はｐと互いに素な剰余類群）を多項式時間内に求めることは困難であるという仮定であり、数学的に安全性を保証することができる。
【０００９】
そこで、本発明の目的は、従来の追跡機能付きのリング署名方式を、参考文献３で開示された署名方式をベースにアルゴリズムを見直すことにより、ランダムオラクルモデルによらずに安全性証明をつけることが可能な追跡機能付きのリング署名方式を実現することにある。
［参考文献３］D. Boneh and X. Boyen、"Short Signatures Without Random Oracles"、Advances In Cryptology-EUROCRYPT 2004、LNCS 3027、Springer-Verlag、2004年、p.56-73
【００１０】
また、非特許文献１、２の追跡機能付きのリング署名方式においては、署名の情報量がグループの構成員数Ｎに比例するＯ（Ｎ）であり、システムへの負荷や処理時間などへの影響が、構成員の増加に比例して大きくなってしまうという問題があった。この点、参考文献４では、追跡機能無しのリング署名方式において、署名の情報量を√Ｎに比例するＯ（√Ｎ）に抑制するアルゴリズムが開示されている。これは大まかには、例えばＣがコミットするｙIと同じ値をコミットする元がＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ }の中に１つ存在することを証明するような場合に、Ｙiを√Ｎ×√Ｎの行列内にマッピングすることで、行又は列単位での署名の証明処理を可能とし、よって署名として必要な情報量の圧縮を図るものである。
【００１１】
そこで本発明は、ランダムオラクルモデルによらずに安全性証明がつく追跡機能付きのリング署名方式において、更に参考文献４で開示されたアルゴリズムを応用することにより、署名の情報量をＯ（√Ｎ）に抑制することもあわせて目的とする。
［参考文献４］N. Chandran, J. Groth, and A. Sahai、"Ring Signatures of Sub-linear Size without Random Oracles"、Automata, Languages and Programming、LNCS 4596、Springer-Verlag、2007年、p.423-434
【課題を解決するための手段】
【００１２】
本発明の追跡機能付き匿名署名システムは、匿名署名生成装置と匿名署名検証装置と匿名署名追跡判定装置とから構成される。当該システムは、位数ｎが大きな素数ｐ、ｑの積である巡回群Ｇと、その生成元ｇと、ｈ∈Ｇ（ｈ≠ｇ）と、zcrs∈Ｇと、位数ｎの巡回群ＧＴと、ペアリング関数ｅ：Ｇ×Ｇ→ＧＴと、ハッシュ関数Ｈ：｛０、１}*→Ｚ／ｎＺと、ハッシュ関数Ｈ´（≠Ｈ）：｛０、１}*→Ｚ／ｎＺと、ランダムな値ｘi∈Ｚ／ｎＺ（Ｚ／ｎＺはｎを法とする剰余類群、ｉ∈{１、２、・・・、Ｎ}は構成員の識別子）に基づき、
【００１３】
【数３】
（ｇxは楕円曲線上の点ｇのスカラー倍（ｘ倍）演算を表す、以下の乗算表記につき同様。）
として得られた各構成員のＢＢ署名検証鍵ｙiのコミットメント
【００１４】
【数４】
（ｄiはランダムな値（ｄi∈Ｚ／ｎＺ）。ｙ・ｈは楕円曲線上の点ｙと点ｈとの楕円加算を表す、以下の積算表記につき同様。）
の集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、が公開され、上記各構成員が自身のＢＢ署名検証鍵ｙiとそれに対応する秘密のＢＢ署名鍵ｘiとを保有するという条件下で用いる。
【００１５】
匿名署名生成装置は、ＯＴ署名鍵生成器と、ハッシュ関数演算器と、ＢＢ署名生成器と、四則演算器と、乱数生成器と、コミットメント生成器と、証明生成器と、ＯＴ署名生成器とから構成される。
ＯＴ署名鍵生成器は、ＯＴ署名鍵skと、それと対応するＯＴ署名検証鍵vkと、を生成して出力する。
【００１６】
ハッシュ関数演算器は、署名対象事項を特定する情報issueと署名対象のメッセージｍと上記Ｒと上記ＯＴ署名検証鍵vkとが入力され、タグＴ＝(issue‖Ｙ１‖Ｙ２‖・・・‖ＹＮ)（‖はビット結合を表す。）を生成し、ハッシュ値Ｈ（Ｔ）、Ｈ´(Ｔ)、Ｈ（Ｔ‖ｍ）、及びＨ(vk)を演算して出力する。
【００１７】
ＢＢ署名生成器は、ｇと、リングの構成員である署名者Ｉ∈｛１、２、・・、Ｎ｝のＢＢ署名鍵ｘIと、ハッシュ値Ｈ(Ｔ)、Ｈ（vk）、及びＨ´(Ｔ)と、が入力され、ＢＢ署名鍵ｘIを用いて当該Ｈ(Ｔ) 、Ｈ（vk）、及びＨ´(Ｔ)のＢＢ署名σI、σvk、及びｚをそれぞれ、
【００１８】
【数５】
により生成し出力する。
四則演算器は、ＢＢ署名σIと、ｇと、ｈと、ハッシュ値Ｈ（Ｔ‖ｍ）とが入力され、Ｑを、
【００１９】
【数６】
により演算するとともに、ハッシュ値Ｈ（Ｔ‖ｍ）とＱとから、ｉ＝Ｉ以外の全てのｉ（１≦ｉ≦ｎ）についてσｉを、σi＝ｇＨ(Ｔ,ｍ)・Ｑｉにより演算し、各演算結果を出力する。
乱数生成器は、ランダムな値η、ｄI、ｓ、ｂ、ｆ、ｒ∈Ｚ／ｎＺをそれぞれ生成して出力するとともに、
【００２０】
【数７】
について、
【００２１】
【数８】
をランダムに生成して出力する。
【００２２】
コミットメント生成器は、ｈと、ＢＢ署名検証鍵ｙIと、ＢＢ署名σI、σvk、及びｚと、値ｄI、ｓ、ｂ、及びｆとが入力され、ＢＢ署名検証鍵ｙIのコミットメントＣ、ＢＢ署名σIのコミットメントＬ、ＢＢ署名σvkのコミットメントＬvk、及びＢＢ署名ｚのコミットメントＬzを、それぞれ、
【００２３】
【数９】
により生成して出力する。
【００２４】
証明生成器は、ｇと、ｈと、ＢＢ署名鍵ｘIと、ＢＢ署名検証鍵ｙIと、ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、Ｈ(Ｔ‖ｍ）、及びＨ´(Ｔ）と、ＢＢ署名ｚと、コミットメントＬ、Ｌvk、及びＬzと、値ｓ、ｒ、η、ｆ、ｔτ、λτ、ｗτ、ｔτ´、λτ´、及びｗτ´（１≦τ≦√Ｎ）と、上記集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、上記σｉ（１≦ｉ≦ｎ、ｉ＝Ｉを含む）と、が入力され、Ｑがｇχという形をしていることの証明πＱを、
【００２５】
【数１０】
により生成し、署名者ＩのＨ(Ｔ)のＢＢ署名σＩが署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明πＣ,Ｌを、
πＣ,Ｌ＝(ｇＨ(Ｔ)・ｙＩ)ｓ・Ｌｒ
により生成し、署名者ＩのＨ（vk）のＢＢ署名σvkが署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【００２６】
【数１１】
により生成し、また、ｚがｇχという形をしていることの証明πｚを、
【００２７】
【数１２】
により生成し、Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの証明
【００２８】
【数１３】
により生成し、署名者ＩのＨ´(Ｔ)のＢＢ署名ｚが署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【００２９】
【数１４】
により生成し、ＣとしてコミットされたＢＢ署名検証鍵ｙIと同じ値がコミットされた元がＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ}の中に一つ存在することを示す証明ΠＲ,Ｃを、
【００３０】
【数１５】
の組として生成し、ＬとしてコミットされたＢＢ署名σIと同じ値がΣ＝{σ１、σ２、・・・、σＮ}の中に一つ存在することを示す証明ΠＬ,Σを、
【００３１】
【数１６】
の組として生成し、証明ΠＲ,ＣでリングＲの中に一つ存在した要素をＹＥ、証明ΠＬ,ΣでΣの中に一つ存在した要素をσＥ´としたとき、Ｅ＝Ｅ´であることを示す証明ΠＲ,Σを、
【００３２】
【数１７】
の組として生成し、生成した各証明を出力する。
【００３３】
ＯＴ署名生成器は、ＯＴ署名検証鍵vkと、ＯＴ署名鍵skと、タグＴと、メッセージｍと、コミットメントＣ、Ｌ、Ｌvk、及びＬzと、ＢＢ署名ｚと、δと、δcrsと、Ｑと、証明
【００３４】
【数１８】
とが入力され、ＯＴ署名鍵skを用いて
【００３５】
【数１９】
の署名sig0を生成し、タグ付き文書（Ｔ、ｍ）のＲに関する匿名署名
【００３６】
【数２０】
を生成し出力する。
【００３７】
匿名署名検証装置は、ＯＴ署名検証器と、ハッシュ関数演算器と、署名検証器とから構成される。
ＯＴ署名検証器は、ＯＴ署名検証鍵vkと、匿名署名
【００３８】
【数２１】
とが入力され、ＯＴ署名検証鍵vkを用いてsig0から
【００３９】
【数２２】
を復号する。
【００４０】
ハッシュ関数演算器は、タグＴと、ＯＴ署名検証鍵vkと、メッセージｍとが入力され、ハッシュ関数Ｈ(Ｔ）、Ｈ（vk）、Ｈ´(Ｔ）、及びＨ(Ｔ‖ｍ)を演算して出力する。
証明検証器は、上記ｇと、上記ｈと、上記ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、Ｈ´(Ｔ）、及びＨ(Ｔ‖ｍ)と、Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、ＯＴ署名検証器で復号された
【００４１】
【数２３】
とが入力され、全てのｉ（１≦σi≦Ｎ）についてσｉ＝ｇＨ(Ｔ,ｍ)・ＱｉによりΣ＝{σ１、σ２、・・・、σＮ}を復元し、
【００４２】
【数２４】
を検証し、更にΠＲ,Ｃに関し、
【００４３】
【数２５】
がすべて成立すること、更にΠＬ,Σに関し、
【００４４】
【数２６】
がすべて成立すること、更にΠＲ,Σに関し、
【００４５】
【数２７】
がすべて成立することをそれぞれ検証し、すべての検証が成功した場合に、sigをタグ付き文書(Ｔ、ｍ)のリングＲに関する正当な匿名署名とみなす。
【００４６】
匿名署名追跡判定装置は、同一のタグＴで文書が異なる２つのタグ付き文書（Ｔ、ｍ）及び（Ｔ、ｍ´）と、これら２つのタグ付き文書についての、各構成員のＢＢ署名検証鍵のコミットメントの集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}に係る２つの正しい匿名署名
【００４７】
【数２８】
とが入力され、各タグ付き文書について、それぞれσｉ＝ｇＨ(Ｔ,ｍ)・Ｑｉ、σｉ´＝ｇＨ(Ｔ,ｍ´)・Ｑ´ｉにより、ＢＢ署名の集合Σ＝{σ１、σ２、・・・、σＮ}、Σ´＝{σ１´、σ２´、・・・、σＮ´}を復元し、ΣとΣ´とを対照してσI＝σI´となる要素が発見された場合に署名者Ｉを出力する。
【発明の効果】
【００４８】
本発明により、ランダムオラクルモデルを用いずに安全性証明がつく追跡機能付きのリング署名方式を実現することができ、なおかつ署名の情報量をＯ（√Ｎに抑制することができる。
【図面の簡単な説明】
【００４９】
【図１】本発明の追跡機能付き匿名署名システム１の機能構成例を示す図。
【図２】本発明の追跡機能付き匿名署名システム１の処理フロー例を示す図。
【図３】Ｑ、ｍに基づき生成したσi（１≦ｉ≦Ｎ）を結んで得られる直線のイメージ図。
【図４】各証明の相関関係を示す図。
【発明を実施するための形態】
【００５０】
以下、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００５１】
〔方式の基本要件〕
本発明においては、追跡機能付きのリング署名方式における以下の基本要件を満たすように構成した。
(1)匿名性
同じ署名者が施した署名は、それが各タグにおいて１度目である限り、誰が施したかを特定できない。
(2)タグによる関連付け
同じ署名者によって同じタグに施された署名は関連付けられる。言いかえれば、あるタグに施すことができる署名の数の上限はリングの構成員数である。
(3)追跡・公開性
同じ署名者が、あるタグについて２以上の異なるメッセージに署名を施した場合、その署名者は明らかにされる。
(4)偽造困難性
ある署名者になりすまして署名を偽造することは困難である。
【００５２】
〔アルゴリズム〕
本システムで実現する追跡機能付きのリング署名方式は、準備、署名生成、署名検証、追跡判定の４つのアルゴリズムからなる。これらを追跡機能付き匿名署名システム１０として構成した例を図１に示す。追跡機能付き匿名署名システム１０は、匿名署名生成装置１００と匿名署名検証装置２００と匿名署名追跡判定装置３００とから構成される。
【００５３】
以下、各アルゴリズムについて説明する。
＜準備＞
位数ｎが大きな素数ｐ、ｑの積である巡回群Ｇと、その生成元ｇと、ｈ∈Ｇ（ｈ≠ｇ）と、zcrs∈Ｇと、位数ｎの巡回群ＧＴと、ペアリング関数ｅ：Ｇ×Ｇ→ＧＴと、ハッシュ関数Ｈ：｛０、１}*→Ｚ／ｎＺと、ハッシュ関数Ｈ´（≠Ｈ）：｛０、１}*→Ｚ／ｎＺ、を共通参照情報として公開する。ここで、ペアリング関数ｅとは、２入力１出力の関数で楕円曲線Ｅ上の２点Ｐ、Ｑについて、ｅ(ａＰ、ｂＱ)＝ｅ(Ｐ、Ｑ)ab＝ｅ(ｂＰ、ａＱ)というような双線形性を成立させる関数である。
【００５４】
更に、ランダムな値ｘi∈Ｚ／ｎＺ（Ｚ／ｎＺはｎを法とする剰余類群、ｉ∈{１、２、・・・、Ｎ}は構成員の識別子）に基づき、
【００５５】
【数２９】
（ｇxは楕円曲線上の点ｇのスカラー倍（ｘ倍）演算を表す、以下の乗算表記につき同様。）
として求めた各構成員のＢＢ署名検証鍵ｙiについて、それぞれコミットメントを、
【００５６】
【数３０】
（ｄiはランダムな値（ｄi∈Ｚ／ｎＺ）。ｙ・ｈは楕円曲線上の点ｙと点ｈとの楕円加算を表す、以下の積算表記につき同様。）
により生成し、その集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}を公開する。
また、上記各構成員は、自身のＢＢ署名検証鍵ｙiとそれに対応する秘密のＢＢ署名鍵ｘiとを予め保有する。
【００５７】
＜署名生成＞
図１に署名生成アルゴリズムの処理を担う匿名署名生成装置１００の機能構成ブロックの構成例を、図２に処理フロー例を示す。
匿名署名生成装置１００は、ＯＴ署名鍵生成器１０１と、ハッシュ関数演算器１０２と、ＢＢ署名生成器１０３と、四則演算器１０４と、乱数生成器１０５と、コミットメント生成器１０６と、証明生成器１０７と、ＯＴ署名生成器１０８とから構成される。
【００５８】
ＯＴ署名鍵生成器１０１は、ＯＴ署名鍵skとそれと対応するＯＴ署名検証鍵vkとを生成して出力する（Ｓ１）。本発明においては、上記のＢＢ署名鍵・検証鍵ｘi、ｙiと当該ＯＴ署名鍵・検証鍵sk、vkの２種類の鍵ペアを用いる。ランダムオラクルを用いずに安全性証明がつく参考文献３で開示された署名方式には、短い文書にしか署名がつけられないが、文書に対して署名が一意に決定するＢＢ１署名と、文書に対して署名が一意に確定しないが長い文書に署名がつけられるＢＢ２署名があり、ＢＢ２署名は使い捨ての署名鍵・検証鍵を生成し、ＢＢ１署名で使い捨て検証鍵に署名し、使い捨て署名鍵で長い文書に署名をする方式である。そこで本発明においては、この２つのＢＢ署名を用途によって使い分けてアルゴリズムを構成する。以下、ＢＢ１署名に係る鍵をＢＢ署名鍵・検証鍵と呼び、ＢＢ２署名に係る使い捨ての鍵をＯＴ署名鍵・検証鍵と呼ぶ。なお、ＯＴ署名鍵・検証鍵はその都度使い捨てるため、一度の使用に耐えうる安全性を有する方式であれば、いかなる公開鍵暗号方式によるものでも構わない。
【００５９】
ハッシュ関数演算器１０２には、議題や質問事項などの署名対象事項を特定する情報であるissueと、署名対象のメッセージｍと、各構成員のＢＢ署名検証鍵ｙiのコミットメントＹiの集合であるＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、ＯＴ署名検証鍵vkとが入力される。そして、タグＴ＝issue‖Ｙ１‖Ｙ２‖・・・‖ＹＮ（‖はビット結合を表す。）を生成し、ハッシュ値Ｈ（Ｔ）と、ハッシュ値Ｈ´(Ｔ)と、ハッシュ値Ｈ（Ｔ‖ｍ）と、ハッシュ値Ｈ(vk)とを演算して出力する（Ｓ２）。
【００６０】
ＢＢ署名生成器１０３は、ｇと、リングの構成員である署名者Ｉ∈｛１、２、・・、Ｎ｝のＢＢ署名鍵ｘIと、ハッシュ値Ｈ(Ｔ)と、ハッシュ値Ｈ（vk）とハッシュ値Ｈ´(Ｔ)とが入力され、Ｈ(Ｔ)、Ｈ（vk）、Ｈ´(Ｔ)のＢＢ署名σI、σvk、ｚをそれぞれ、
【００６１】
【数３１】
により生成し、生成した各署名を出力する（Ｓ３）。
四則演算器１０４は、ＢＢ署名σIとｇとハッシュ値Ｈ（Ｔ‖ｍ）とが入力され、Ｑを、
【００６２】
【数３２】
により演算して出力する（Ｓ４）。
【００６３】
ここでＱは、図３に示すような、logｇσIとＨ（Ｔ‖ｍ）とを結ぶ直線の傾きとして観念されるものである。本発明では、このＱとＨ（Ｔ‖ｍ）とに基づき署名者Ｉ以外のグループのメンバｉ（１≦ｉ≦Ｎ）のダミーの署名σiを生成、復元する（ただし復元の際には、署名者Ｉの署名は匿名状態にあるため、他と同様にＱとＨ（Ｔ‖ｍ）とに基づき復元する）。このＮ個のσiを結んだ傾きＱの直線は、あるタグＴについてメッセージｍが異なると（例えばｍ´）図３に示すように傾きがＱ´に変化するが、同じ署名者Ｉが署名している限り、２本の直線は１点（横軸が署名者Ｉの所）で交差する。そのため、検証側で復元されたタグＴについてのメッセージｍとｍ´に対する署名集合Σ＝{σ１、σ２、・・・、σＮ}とΣ´＝{σ１´、σ２´、・・・、σＮ´}とを照合することで、σＩ＝σＩ´が発見された場合には、同じ署名者Ｉが同じタグＴに対し異なる２つのメッセージに署名していると検出することができる。
【００６４】
乱数生成器１０５は、ランダムな値η、ｄI、ｓ、ｂ、ｆ、ｒ∈Ｚ／ｎＺをそれぞれ生成して出力する（Ｓ５）。なお、Ｓ５の処理はＳ１〜Ｓ４と並行して行っても構わない。
【００６５】
コミットメント生成器１０６は、ｈと、ＢＢ署名検証鍵ｙIと、ＢＢ署名σI、σvk、ｚと、ランダム値ｄI、ｓ、ｂ、ｆと、が入力され、ＢＢ署名検証鍵ｙIのコミットメントＣ、ＢＢ署名σIのコミットメントＬ、ＢＢ署名σvkのコミットメントＬvk、ＢＢ署名ｚのコミットメントＬzをそれぞれ、
【００６６】
【数３３】
により生成し出力する（Ｓ６）。このように各情報をコミットして署名生成・検証処理することにより、秘密情報の解読危険性を低減することができる。
【００６７】
証明生成器１０７は、ｇと、ｈと、ＢＢ署名鍵ｘIと、ＢＢ署名検証鍵ｙIと、ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、Ｈ(Ｔ‖ｍ）、Ｈ´(Ｔ）と、ＢＢ署名ｚと、コミットメントＬ、Ｌvk、Ｌzと、ランダム値ｓ、ｒ、η、ｆと、が入力され、以下の各証明を生成し出力する（Ｓ７）。
・Ｑがｇχという形をしていることの証明πＱ
【００６８】
【数３４】
【００６９】
・署名者ＩのＨ(Ｔ)のＢＢ署名σＩが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明πＣ,Ｌ
πＣ,Ｌ＝(ｇＨ(Ｔ)・ｙＩ)ｓ・Ｌｒ
・署名者ＩのＨ（vk）のＢＢ署名σvkが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【００７０】
【数３５】
・ｚがｇχという形をしていることの証明πｚ
【００７１】
【数３６】
・Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの証明
【００７２】
【数３７】
・署名者ＩのＨ´(Ｔ)のＢＢ署名zが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【００７３】
【数３８】
【００７４】
・ＣとしてコミットされたＢＢ署名検証鍵ｙIと同じ値がコミットされた元がＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ}の中に一つ存在することを示す証明ΠR,C
・ＬとしてコミットされたＢＢ署名σIと同じ値がΣ＝{σ１、σ２、・・・、σＮ}の中に一つ存在することを示す証明ΠL,Σ
・証明ΠR,CでリングＲの中に一つ存在した要素をＹE、証明ΠL,Σで上記Σの中に一つ存在した要素をσE´としたとき、Ｅ＝Ｅ´であることを示す証明ΠR,Σ
【００７５】
本発明においては、ハッシュ関数Ｈ´(Ｔ)についてのＢＢ署名ｚを生成し、更にこのｚに係る証明を生成して検証するが、これは次の理由による。先に説明したように、同じ署名者ＩがあるタグＴに対し２つの異なるメッセージｍ、ｍ´に署名した場合、ＱとＨ（Ｔ‖ｍ）に基づき生成したＮ個のσiを結んだ直線と、Ｑ´とＨ（Ｔ‖ｍ´）に基づき生成したＮ個のσi´を結んだ直線と、が１点（横軸が署名者Ｉの所）で交差することから、各メッセージについて生成された２つの署名集合Σ、Σ´において、σＩ＝σＩ´なる要素が存在したことをもって、重複署名がされたと判定する。しかし、悪意を持った２名の構成員が結託することで、２名がそれぞれ生成した直線をＩの所で交差させて誤判定に導くことができる可能性がある。そこで、各構成員のＢＢ署名鍵ｘIとタグＴとから、ハッシュＨとは異なる別のハッシュＨ´を用いて各構成員ごとに一意に定まるＢＢ署名ｚを生成し、このｚについても検証することで、このような結託攻撃を防御することができる。
【００７６】
また、ΠR,C、ΠL,Σ、ΠR,Σの各証明について、ここでは生成方法を特定しないが、これは非特許文献１、２などの従来技術によって生成することが可能なためである。この場合の署名の情報量は従来どおりＯ(Ｎ)となる。署名の情報量をＯ（√Ｎ）に抑制する新たなアルゴリズムについては、実施例２として後述する。
【００７７】
ＯＴ署名生成器１０８には、上記ＯＴ署名検証鍵vkと、上記ＯＴ署名鍵skと、上記タグＴと、上記メッセージｍと、上記コミットメントＣ、Ｌ、Ｌvk、Ｌzと、上記ＢＢ署名ｚと、上記δと、上記δcrsと、上記Ｑと、上記証明
【００７８】
【数３９】
とが入力される。まず、ＯＴ署名鍵skを用いて
【００７９】
【数４０】
の署名sig0を生成する。そして、タグ付き文書（Ｔ、ｍ）の上記Ｒに関する匿名署名
【００８０】
【数４１】
を生成して出力する（Ｓ８）。
【００８１】
＜署名検証＞
図１に署名検証アルゴリズムの処理を担う匿名署名検証装置２００の機能構成ブロックの構成例を、図２に処理フロー例を示す。
匿名署名検証装置２００は、ＯＴ署名検証器２０１とハッシュ関数演算器２０２と証明検証器２０３とから構成される。
ＯＴ署名検証器２０１は、ＯＴ署名検証鍵vkと匿名署名
【００８２】
【数４２】
とが入力され、ＯＴ署名検証鍵vkを用いて、sig0から
【００８３】
【数４３】
を復号する。復号できなかった場合には、不正なＯＴ署名であったと判定する（Ｓ１１）。
【００８４】
ハッシュ関数演算器２０２は、上記タグＴと、上記ＯＴ署名検証鍵vkとが入力され、ハッシュ関数Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）を演算して出力する（Ｓ１２）。
証明検証器２０３は、ｇと、ｈと、ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）と、ＯＴ署名検証器２０１で復号された
【００８５】
【数４４】
【００８６】
とが入力され、以下の各関係式の成立の確認により署名の正当性を検証する（Ｓ１３）。
・Ｑがｇχという形をしていることの確認
ｅ(Ｑ、ｈ)＝ｅ(ｇ、πＱ)
・署名者ＩのＨ(Ｔ)のＢＢ署名σＩが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの確認
ｅ(ｇＨ(Ｔ)・Ｃ、Ｌ)＝ｅ(ｇ、ｇ) ・ｅ(ｈ、πＣ，Ｌ)
・署名者ＩのＨ（vk）のＢＢ署名σvkが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの確認
【００８７】
【数４５】
【００８８】
・ｚがｇχという形をしていることの確認
ｅ(ｚ、ｈ)＝ｅ(ｇ、πＺ)
・Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの確認
δ・δcrs＝ｇ
ｅ(δ、δ・ｇ-1)＝ｅ(δcrs、δcrs・ｇ-1)＝ｅ(ｈ、πδ)
【００８９】
【数４６】
【００９０】
・署名者ＩのＨ´(Ｔ)のＢＢ署名zが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの確認
【００９１】
【数４７】
【００９２】
なお、ΠR,C、ΠL,Σ、ΠR,Σの検証については、ここでは実施方法を特定しないが、これは非特許文献１、２などの従来技術によって実施することが可能なためである。証明生成器１０７において署名の情報量をＯ（√Ｎ）に抑制するアルゴリズムに基づき証明を生成した場合には、後述する実施例２に示すアルゴリズムにより検証する。
【００９３】
以上の各証明の相関関係を図４に示す。
そして、証明検証器２０３におけるすべての検証が成功した場合に、sigをタグ付き文書（Ｔ、ｍ）のリングＲに関する正当な匿名署名とみなす。
【００９４】
＜追跡判定＞
追跡判定アルゴリズムの処理を担う匿名署名追跡判定装置３００の追跡機能付き匿名署名システム１内での位置づけを図１に、システム全体の処理フロー内での位置づけを図２に示す。
匿名署名追跡判定装置３００は、同一のタグＴで文書が異なる２つのタグ付き文書（Ｔ、ｍ）、（Ｔ、ｍ´）と、これら２つのタグ付き文書に対する各構成員のＢＢ署名検証鍵のコミットメントの集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}に関する２つの正しい匿名署名
【００９５】
【数４８】
【００９６】
とが入力され、各タグ付き文書について、それぞれσi＝ｇＨ(Ｔ,ｍ)・Ｑｉ、σi´＝ｇＨ(Ｔ,ｍ´)・Ｑ´ｉにより、ＢＢ署名の集合Σ＝{σ１、σ２、・・・、σＮ}、Σ´＝{σ１´、σ２´、・・・、σＮ´}を復元し、σI(∈Σ)＝σI´(∈Σ´)となる要素が発見された場合に、重複署名がされたと判定し署名者Ｉを出力する（Ｓ２１）。
【００９７】
以上のようなアルゴリズムにより、ランダムオラクルモデルによらずに安全性証明がつく追跡機能付きのリング署名方式を実現することができる。
【実施例２】
【００９８】
実施例２では、参考文献４で開示されたアルゴリズムを実施例１の追跡機能付きのリング署名方式に応用し、署名の情報量をＯ(Ｎ)からＯ(√Ｎ）に抑制するアルゴリズムを説明する。実施例１とは構成は共通であるが、匿名署名生成装置１００については、四則演算器１０４、乱数生成器１０５、及び証明生成器１０７、また匿名署名検証装置２００については、ハッシュ関数演算器２０２、及び証明検証器２０３につき、一部処理が追加される。そこで、ここでは追加部分についてのみ説明し、共通する部分の説明は省略する。
【００９９】
四則演算器１０４は、更に、ハッシュ値Ｈ（Ｔ‖ｍ）とＱとから、ｉ＝Ｉ以外の全てのｉ（１≦ｉ≦ｎ）について、ＢＢ署名σiを、σi＝ｇＨ(Ｔ,ｍ)・Ｑｉにより演算して出力する。
乱数生成器１０５は、更に、
【０１００】
【数４９】
について、
【０１０１】
【数５０】
【０１０２】
をランダムに生成して出力する。なお、Ｉ＝(ｕ−１)√Ｎ＋ｖは、ＢＢ署名σＩ、ＢＢ署名検証鍵のコミットメントＹＩをそれぞれ、√Ｎ×√Ｎの行列上のσｕ,ｖ、Ｙｕ,ｖにマッピングする関係式である。
【０１０３】
証明生成器１０７は、更に、ランダム値ｔτ、λτ、ｗτ、ｔτ´、λτ´、ｗτ´（１≦τ≦√Ｎ）と、集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、ＢＢ署名σi（１≦ｉ≦ｎ、ｉ＝Ｉを含む）と、がそれぞれ入力され、証明ΠＲ,Ｃ、ΠＬ,Σ、ΠＲ,Σをそれぞれ以下のように生成し出力する。
【０１０４】
なお、生成にあたっては、σｉ、Ｙｉ（１≦ｉ≦Ｎ）を、ｉ＝(ε−１)√Ｎ＋φの関係式により√Ｎ×√Ｎの行列上のσε,φ、Ｙε,φ（１≦ε、φ≦√Ｎ）にそれぞれマッピングする。
【０１０５】
【数５１】
【０１０６】
【数５２】
・証明ΠＲ,Σは、以下のπα,α´,ε、πγ,γ´,φの組からなる。
【０１０７】
【数５３】
ハッシュ関数演算器２０２は、更に上記ｍが入力され、ハッシュ関数Ｈ(Ｔ‖ｍ)を演算して出力する。
【０１０８】
証明検証器２０３は、更に上記ハッシュ関数Ｈ(Ｔ‖ｍ)と、Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}とが入力され、まず全てのｉ（１≦σi≦Ｎ）について、σｉ＝ｇＨ(Ｔ,ｍ)・ＱｉによりΣ＝{σ１、σ２、・・・、σＮ}を復元する。そして、証明ΠＲ,Ｃ、ΠＬ,Σ、ΠＲ,Σについて、以下の各関係式の成立を確認することにより署名の正当性を検証する。
●証明ΠＲ,Ｃについて
・各α（又は各γ）がｈχかｇ・ｈχのいずれかの形をしていることの確認
【０１０９】
【数５４】
・各α（又は各γ）のうち１つがｇ・ｈχの形をしていることの確認
【０１１０】
【数５５】
・その１つのα（又はγ）が、各Ｙのうちの１つに対応するものであることの確認
【０１１１】
【数５６】
・その１つのＹが、Ｃ（ｙＩのコミットメント）であることの確認
【０１１２】
【数５７】
【０１１３】
●証明ΠＬ,Σについて、
・各α（又は各γ）がｈχかｇ・ｈχのいずれかの形をしていることの確認
【０１１４】
【数５８】
・各α（又は各γ）のうち１つがｇ・ｈχの形をしていることの確認
【０１１５】
【数５９】
・その１つのα（又はγ）が、各σのうちの１つに対応するものであることの確認
【０１１６】
【数６０】
・その１つのσが、σＩであることの確認
【０１１７】
【数６１】
【０１１８】
●証明ΠＲ,Σについて、
・証明ΠＲ,ＣでリングＲの中に１つ存在した要素をＹＥ、証明ΠＬ,Σで上記Σの中に１つ存在した要素をσＥ´としたとき、Ｅ＝Ｅ´であることの確認
【０１１９】
【数６２】
【０１２０】
以上のように、Ｙi、σiをそれぞれ√Ｎ×√Ｎの行列内にマッピングし、それに基づき証明を生成することで、行又は列単位での署名の証明処理を可能とし、よって署名として必要な情報量を√Ｎに比例するＯ（√Ｎ）に抑制することができる。
【０１２１】
本発明における匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、追跡機能付き匿名署名システム、それらの方法及びプログラムは、上記の実施形態に限定されるものではなく、本発明を逸脱しない範囲で適宜変更が可能である。また、上記に説明した処理は記載の順に従った時系列において実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行してもよい。
【０１２２】
また、匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、又は追跡機能付き匿名署名システムにおける処理機能をコンピュータによって実現する場合、匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、又は追跡機能付き匿名署名システムが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより上記匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、又は追跡機能付き匿名署名システムにおける処理機能がコンピュータ上で実現される。
【０１２３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦自己の記録装置に格納する。そして、処理の実行時、このコンピュータは自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、更に、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータからこのコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって上記の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。また、この形態ではコンピュータ上で所定のプログラムを実行させることにより、匿名署名生成装置、匿名署名検証装置、匿名署名追跡判定装置、又は追跡機能付き匿名署名システムを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【特許請求の範囲】
【請求項１】
位数ｎが大きな素数ｐ、ｑの積である巡回群Ｇと、その生成元ｇと、ｈ∈Ｇ（ｈ≠ｇ）と、zcrs∈Ｇと、位数ｎの巡回群ＧＴと、ペアリング関数ｅ：Ｇ×Ｇ→ＧＴと、ハッシュ関数Ｈ：｛０、１}*→Ｚ／ｎＺと、ハッシュ関数Ｈ´（≠Ｈ）：｛０、１}*→Ｚ／ｎＺと、ランダムな値ｘi∈Ｚ／ｎＺ（Ｚ／ｎＺはｎを法とする剰余類群、ｉ∈{１、２、・・・、Ｎ}は構成員の識別子）に基づき、
【数６３】
（ｇxは楕円曲線上の点ｇのスカラー倍（ｘ倍）演算を表す、以下の乗算表記につき同様。）
として得られた各構成員のＢＢ署名検証鍵ｙiのコミットメント
【数６４】
（ｄiはランダムな値（ｄi∈Ｚ／ｎＺ）。ｙ・ｈは楕円曲線上の点ｙと点ｈとの楕円加算を表す、以下の積算表記につき同様。）
の集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、が公開され、上記各構成員が自身のＢＢ署名検証鍵ｙiとそれに対応する秘密のＢＢ署名鍵ｘiとを保有するという条件下で用いる匿名署名生成装置において、
ＯＴ署名鍵skと、それと対応するＯＴ署名検証鍵vkと、を生成して出力するＯＴ署名鍵生成器と、
署名対象事項を特定する情報issueと署名対象のメッセージｍと上記Ｒと上記ＯＴ署名検証鍵vkとが入力され、タグＴ＝(issue‖Ｙ１‖Ｙ２‖・・・‖ＹＮ)（‖はビット結合を表す。）を生成し、ハッシュ値Ｈ（Ｔ）、Ｈ´(Ｔ)、Ｈ（Ｔ‖ｍ）、及びＨ(vk)を演算して出力するハッシュ関数演算器と、
上記ｇと、リングの構成員である署名者Ｉ∈｛１、２、・・、Ｎ｝の上記ＢＢ署名鍵ｘIと、上記ハッシュ値Ｈ(Ｔ)、Ｈ（vk）、及びＨ´(Ｔ)と、が入力され、上記ＢＢ署名鍵ｘIを用いて当該Ｈ(Ｔ) 、Ｈ（vk）、及びＨ´(Ｔ)のＢＢ署名σI、σvk、及びｚをそれぞれ、
【数６５】
により生成し、生成した各署名を出力するＢＢ署名生成器と、
上記ＢＢ署名σIと、上記ｇと、上記ｈと、上記ハッシュ値Ｈ（Ｔ‖ｍ）とが入力され、Ｑを、
【数６６】
により演算して出力する四則演算器と、
ランダムな値η、ｄI、ｓ、ｂ、ｆ、ｒ∈Ｚ／ｎＺをそれぞれ生成して出力する乱数生成器と、
上記ＢＢ署名検証鍵ｙIと、上記ＢＢ署名σI、σvk、及びｚと、上記ｈと、上記値ｄI、ｓ、ｂ、及びｆと、が入力され、上記ＢＢ署名検証鍵ｙIのコミットメントＣ、上記ＢＢ署名σIのコミットメントＬ、上記ＢＢ署名σvkのコミットメントＬvk、及び上記ＢＢ署名ｚのコミットメントＬzを、それぞれ、
【数６７】
により生成して出力するコミットメント生成器と、
上記ｇと、上記ｈと、上記ＢＢ署名鍵ｘIと、上記ＢＢ署名検証鍵ｙIと、上記ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、Ｈ(Ｔ‖ｍ）、及びＨ´(Ｔ）と、上記ＢＢ署名ｚと、上記コミットメントＬ、Ｌvk、及びＬzと、上記値ｓ、ｒ、η、及びｆと、が入力され、Ｑがｇχという形をしていることの証明πＱを、
【数６８】
により生成し、当該署名者ＩのＨ(Ｔ)のＢＢ署名σＩが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明πＣ,Ｌを、
πＣ,Ｌ＝(ｇＨ(Ｔ)・ｙＩ)ｓ・Ｌｒ
により生成し、当該署名者ＩのＨ（vk）のＢＢ署名σvkが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【数６９】
により生成し、また、ｚがｇχという形をしていることの証明πｚを、
【数７０】
により生成し、Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの証明
【数７１】
により生成し、当該署名者ＩのＨ´(Ｔ)のＢＢ署名ｚが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【数７２】
により生成し、更に、上記ＣとしてコミットされたＢＢ署名検証鍵ｙIと同じ値がコミットされた元が上記Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}の中に一つ存在することを示す証明ΠＲ,Ｃを所定の演算により生成し、上記ＬとしてコミットされたＢＢ署名σIと同じ値がΣ＝{σ１、σ２、・・・、σＮ}の中に一つ存在することを示す証明ΠＬ,Σを所定の演算により生成し、上記証明ΠＲ,ＣでリングＲの中に一つ存在した要素をＹＥ、上記証明ΠＬ,Σで上記Σの中に一つ存在した要素をσＥ´としたとき、Ｅ＝Ｅ´であることを示す証明ΠＲ,Σを所定の演算により生成し、生成した各証明を出力する証明生成器と、
上記ＯＴ署名検証鍵vkと、上記ＯＴ署名鍵skと、上記タグＴと、上記メッセージｍと、上記コミットメントＣ、Ｌ、Ｌvk、及びＬzと、上記ＢＢ署名ｚと、上記δと、上記δcrsと、上記Ｑと、上記証明
【数７３】
とが入力され、上記ＯＴ署名鍵skを用いて
【数７４】
の署名sig0を生成し、タグ付き文書（Ｔ、ｍ）の上記Ｒに関する匿名署名
【数７５】
を生成し出力するＯＴ署名生成器と、
を備える匿名署名生成装置。
【請求項２】
請求項１に記載の匿名署名生成装置において、
上記四則演算器は、更に、上記ハッシュ値Ｈ（Ｔ‖ｍ）と上記Ｑとから、ｉ＝Ｉ以外の全てのｉ（１≦ｉ≦ｎ）についてσｉを、σi＝ｇＨ(Ｔ,ｍ)・Ｑｉにより演算して出力し、
上記乱数生成器は、更に、
【数７６】
について、
【数７７】
をランダムに生成して出力し、
上記証明生成器は、更に、上記値ｔτ、λτ、ｗτ、ｔτ´、λτ´、及びｗτ´（１≦τ≦√Ｎ）と、上記集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、上記σｉ（１≦ｉ≦ｎ、ｉ＝Ｉを含む）と、がそれぞれ入力され、上記証明ΠＲ,Ｃを、
【数７８】
の組として生成し、上記証明ΠＬ,Σを、
【数７９】
の組として生成し、上記証明ΠＲ,Σを、
【数８０】
の組として生成することを特徴とする匿名署名生成装置。
【請求項３】
ＯＴ署名検証鍵vkと、匿名署名
【数８１】
とが入力され、ＯＴ署名検証鍵vkを用いてsig0から
【数８２】
を復号するＯＴ署名検証器と、
上記タグＴと、上記ＯＴ署名検証鍵vkと、が入力され、ハッシュ関数Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）を演算して出力するハッシュ関数演算器と、
上記ｇと、上記ｈと、上記ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）と、上記ＯＴ署名検証器で復号された
【数８３】
とが入力され、
【数８４】
を検証し、また、ΠＲ,Ｃ、ΠＬ,Σ、ΠＲ,Σについてはそれぞれ所定の演算により検証する証明検証器と、
を備え、上記証明検証器におけるすべての検証が成功した場合に、sigをタグ付き文書(Ｔ、ｍ)のリングＲに関する正当な匿名署名とみなす匿名署名検証装置。
【請求項４】
請求項３に記載の匿名署名検証装置において、
上記ΠＲ,Ｃは、
【数８５】
であり、
上記ΠＬ,Σは、
【数８６】
であり、
上記ΠＲ,Σは、
【数８７】
であり、
上記ハッシュ関数演算器は、更に上記ｍが入力され、ハッシュ関数Ｈ(Ｔ‖ｍ)を演算して出力し、
上記証明検証器は、更に上記ハッシュ関数Ｈ(Ｔ‖ｍ)とＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ}とが入力され、全てのｉ（１≦σi≦Ｎ）についてσｉ＝ｇＨ(Ｔ,ｍ)・ＱｉによりΣ＝{σ１、σ２、・・・、σＮ}を復元し、
証明ΠＲ,Ｃについて、
【数８８】
がすべて成立すること、
証明ΠＬ,Σについて、
【数８９】
がすべて成立すること、
証明ΠＲ,Σについて、
【数９０】
がすべて成立すること、
を検証することを特徴とする匿名署名検証装置。
【請求項５】
同一のタグＴで文書が異なる２つのタグ付き文書（Ｔ、ｍ）及び（Ｔ、ｍ´）と、これら２つのタグ付き文書についての、各構成員のＢＢ署名検証鍵のコミットメントの集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}に係る２つの正しい匿名署名
【数９１】
とが入力され、各タグ付き文書について、それぞれσｉ＝ｇＨ(Ｔ,ｍ)・Ｑｉ、σｉ´＝ｇＨ(Ｔ,ｍ´)・Ｑ´ｉにより、ＢＢ署名の集合Σ＝{σ１、σ２、・・・、σＮ}、Σ´＝{σ１´、σ２´、・・・、σＮ´}を復元し、ΣとΣ´とを対照してσI＝σI´となる要素が発見された場合に署名者Ｉを出力する匿名署名追跡判定装置。
【請求項６】
請求項２に記載の匿名署名生成装置と、請求項４に記載の匿名署名検証装置と、請求項５に記載の匿名署名追跡判定装置とを備える追跡機能付き匿名署名システム。
【請求項７】
位数ｎが大きな素数ｐ、ｑの積である巡回群Ｇと、その生成元ｇと、ｈ∈Ｇ（ｈ≠ｇ）と、zcrs∈Ｇと、位数ｎの巡回群ＧＴと、ペアリング関数ｅ：Ｇ×Ｇ→ＧＴと、ハッシュ関数Ｈ：｛０、１}*→Ｚ／ｎＺと、ハッシュ関数Ｈ´（≠Ｈ）：｛０、１}*→Ｚ／ｎＺと、ランダムな値ｘi∈Ｚ／ｎＺ（Ｚ／ｎＺはｎを法とする剰余類群、ｉ∈{１、２、・・・、Ｎ}は構成員の識別子）に基づき、
【数９２】
（ｇxは楕円曲線上の点ｇのスカラー倍（ｘ倍）演算を表す、以下の乗算表記につき同様。）
として得られた各構成員のＢＢ署名検証鍵ｙiのコミットメント
【数９３】
（ｄiはランダムな値（ｄi∈Ｚ／ｎＺ）。ｙ・ｈは楕円曲線上の点ｙと点ｈとの楕円加算を表す、以下の積算表記につき同様。）
の集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、が公開され、上記各構成員が自身のＢＢ署名検証鍵ｙiとそれに対応する秘密のＢＢ署名鍵ｘiとを保有するという条件下で用いる匿名署名生成方法において、
ＯＴ署名鍵生成器が、ＯＴ署名鍵skと、それと対応するＯＴ署名検証鍵vkと、を生成するＯＴ署名鍵生成ステップと、
ハッシュ関数演算器が、署名対象事項を特定する情報issueと上記ＲとからなるタグＴ＝(issue‖Ｙ１‖Ｙ２‖・・・‖ＹＮ)（‖はビット結合を表す。）について、ハッシュ値Ｈ（Ｔ）、Ｈ´(Ｔ)、Ｈ（Ｔ‖ｍ）、及びＨ(vk)を演算するハッシュ関数演算ステップと、
ＢＢ署名生成器が、上記構成員である署名者Ｉ∈｛１、２、・・、Ｎ｝のＢＢ署名鍵ｘIを用いて、上記Ｈ(Ｔ) 、Ｈ（vk）、及びＨ´(Ｔ)のＢＢ署名σI、σvk、及びｚをそれぞれ、
【数９４】
により生成するＢＢ署名生成ステップと、
四則演算器がＱを、
【数９５】
により演算する四則演算ステップと、
乱数生成器が、ランダムな値η、ｄI、ｓ、ｂ、ｆ、ｒ∈Ｚ／ｎＺをそれぞれ生成する乱数生成ステップと、
コミットメント生成器が、上記ＢＢ署名検証鍵ｙIのコミットメントＣ、上記ＢＢ署名σIのコミットメントＬ、上記ＢＢ署名σvkのコミットメントＬvk、及び上記ＢＢ署名ｚのコミットメントＬzを、それぞれ、
【数９６】
により生成するコミットメント生成ステップと、
証明生成器が、上記署名者IのもとにloggＱが存在し、Ｑがｇχという形をしていることの証明πＱを、
【数９７】
により生成し、当該署名者ＩのＨ(Ｔ)のＢＢ署名σＩが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明πＣ,Ｌを、
πＣ,Ｌ＝(ｇＨ(Ｔ)・ｙＩ)ｓ・Ｌｒ
により生成し、当該署名者ＩのＨ（vk）のＢＢ署名σvkが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【数９８】
により生成し、また、上記署名者Iのもとにloggｚが存在し、ｚがｇχという形をしていることの証明πｚを、
【数９９】
により生成し、Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの証明
【数１００】
により生成し、当該署名者ＩのＨ´(Ｔ)のＢＢ署名ｚが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【数１０１】
により生成し、更に、上記ＣとしてコミットされたＢＢ署名検証鍵ｙIと同じ値がコミットされた元が上記Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}の中に一つ存在することを示す証明ΠＲ,Ｃを所定の演算により生成し、上記ＬとしてコミットされたＢＢ署名σIと同じ値がΣ＝{σ１、σ２、・・・、σＮ}の中に一つ存在することを示す証明ΠＬ,Σを所定の演算により生成し、上記証明ΠＲ,ＣでリングＲの中に一つ存在した要素をＹＥ、上記証明ΠＬ,Σで上記Σの中に一つ存在した要素をσＥ´としたとき、Ｅ＝Ｅ´であることを示す証明ΠＲ,Σを所定の演算により生成する証明生成ステップと、
ＯＴ署名生成器が、上記ＯＴ署名鍵skを用いて
【数１０２】
の署名sig0を生成し、タグ付き文書（Ｔ、ｍ）の上記Ｒに関する匿名署名
【数１０３】
を生成するＯＴ署名生成ステップと、
を実行する匿名署名生成方法。
【請求項８】
請求項７に記載の匿名署名生成方法において、
上記四則演算ステップにおいては、更に、上記ハッシュ値Ｈ（Ｔ‖ｍ）と上記Ｑとから、ｉ＝Ｉ以外の全てのｉ（１≦ｉ≦ｎ）についてσｉを、σi＝ｇＨ(Ｔ,ｍ)・Ｑｉにより演算し、
上記乱数生成ステップにおいては、更に、
【数１０４】
について、
【数１０５】
をランダムに生成し、
上記証明生成ステップにおいては、更に、上記証明ΠＲ,Ｃを、
【数１０６】
の組として生成し、上記証明ΠＬ,Σを、
【数１０７】
の組として生成し、上記証明ΠＲ,Σを、
【数１０８】
の組として生成することを特徴とする匿名署名生成方法。
【請求項９】
ＯＴ署名検証器が、匿名署名
【数１０９】
についてＯＴ署名検証鍵vkを用いて、sig0から
【数１１０】
を復号するＯＴ署名検証ステップと、
ハッシュ関数演算器が、ハッシュ関数Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）を演算するハッシュ関数演算ステップと、
証明検証器が、
【数１１１】
を検証し、また、ΠＲ,Ｃ、ΠＬ,Σ、ΠＲ,Σについてはそれぞれ所定の演算により検証する証明検証ステップと、
を実行し、上記証明検証ステップにおけるすべての検証が成功した場合に、sigをタグ付き文書(Ｔ、ｍ)のリングＲに関する正当な匿名署名とみなす匿名署名検証方法。
【請求項１０】
請求項９に記載の匿名署名検証方法において、
上記ΠＲ,Ｃは、
【数１１２】
であり、
上記ΠＬ,Σは、
【数１１３】
であり、
上記ΠＲ,Σは、
【数１１４】
であり、
上記ハッシュ関数演算ステップにおいては、更にハッシュ関数Ｈ(Ｔ‖ｍ)を演算し、
上記証明検証ステップにおいては、更に、全てのｉ（１≦σi≦Ｎ）について、σｉ＝ｇＨ(Ｔ,ｍ)・ＱｉによりΣ＝{σ１、σ２、・・・、σＮ}を復元し、
証明ΠＲ,Ｃについて、
【数１１５】
がすべて成立すること、
証明ΠＬ,Σについて、
【数１１６】
がすべて成立すること、
証明ΠＲ,Σについて、
【数１１７】
がすべて成立すること、
を検証することを特徴とする匿名署名検証方法。
【請求項１１】
匿名署名追跡判定装置が、同一のタグＴで文書が異なる２つのタグ付き文書（Ｔ、ｍ）及び（Ｔ、ｍ´）について、それぞれσｉ＝ｇＨ(Ｔ,ｍ)・Ｑｉ、σｉ´＝ｇＨ(Ｔ,ｍ´)・Ｑ´ｉによりＢＢ署名の集合Σ＝{σ１、σ２、・・・、σＮ}、Σ´＝{σ１´、σ２´、・・・、σＮ´}を復元し、ΣとΣ´とを対照してσI＝σI´となる要素が発見された場合に署名者Ｉを出力する匿名署名追跡判定方法。
【請求項１２】
請求項１〜６のいずれかに記載した装置又はシステムとしてコンピュータを機能させるためのプログラム。
【請求項１】
位数ｎが大きな素数ｐ、ｑの積である巡回群Ｇと、その生成元ｇと、ｈ∈Ｇ（ｈ≠ｇ）と、zcrs∈Ｇと、位数ｎの巡回群ＧＴと、ペアリング関数ｅ：Ｇ×Ｇ→ＧＴと、ハッシュ関数Ｈ：｛０、１}*→Ｚ／ｎＺと、ハッシュ関数Ｈ´（≠Ｈ）：｛０、１}*→Ｚ／ｎＺと、ランダムな値ｘi∈Ｚ／ｎＺ（Ｚ／ｎＺはｎを法とする剰余類群、ｉ∈{１、２、・・・、Ｎ}は構成員の識別子）に基づき、
【数６３】
（ｇxは楕円曲線上の点ｇのスカラー倍（ｘ倍）演算を表す、以下の乗算表記につき同様。）
として得られた各構成員のＢＢ署名検証鍵ｙiのコミットメント
【数６４】
（ｄiはランダムな値（ｄi∈Ｚ／ｎＺ）。ｙ・ｈは楕円曲線上の点ｙと点ｈとの楕円加算を表す、以下の積算表記につき同様。）
の集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、が公開され、上記各構成員が自身のＢＢ署名検証鍵ｙiとそれに対応する秘密のＢＢ署名鍵ｘiとを保有するという条件下で用いる匿名署名生成装置において、
ＯＴ署名鍵skと、それと対応するＯＴ署名検証鍵vkと、を生成して出力するＯＴ署名鍵生成器と、
署名対象事項を特定する情報issueと署名対象のメッセージｍと上記Ｒと上記ＯＴ署名検証鍵vkとが入力され、タグＴ＝(issue‖Ｙ１‖Ｙ２‖・・・‖ＹＮ)（‖はビット結合を表す。）を生成し、ハッシュ値Ｈ（Ｔ）、Ｈ´(Ｔ)、Ｈ（Ｔ‖ｍ）、及びＨ(vk)を演算して出力するハッシュ関数演算器と、
上記ｇと、リングの構成員である署名者Ｉ∈｛１、２、・・、Ｎ｝の上記ＢＢ署名鍵ｘIと、上記ハッシュ値Ｈ(Ｔ)、Ｈ（vk）、及びＨ´(Ｔ)と、が入力され、上記ＢＢ署名鍵ｘIを用いて当該Ｈ(Ｔ) 、Ｈ（vk）、及びＨ´(Ｔ)のＢＢ署名σI、σvk、及びｚをそれぞれ、
【数６５】
により生成し、生成した各署名を出力するＢＢ署名生成器と、
上記ＢＢ署名σIと、上記ｇと、上記ｈと、上記ハッシュ値Ｈ（Ｔ‖ｍ）とが入力され、Ｑを、
【数６６】
により演算して出力する四則演算器と、
ランダムな値η、ｄI、ｓ、ｂ、ｆ、ｒ∈Ｚ／ｎＺをそれぞれ生成して出力する乱数生成器と、
上記ＢＢ署名検証鍵ｙIと、上記ＢＢ署名σI、σvk、及びｚと、上記ｈと、上記値ｄI、ｓ、ｂ、及びｆと、が入力され、上記ＢＢ署名検証鍵ｙIのコミットメントＣ、上記ＢＢ署名σIのコミットメントＬ、上記ＢＢ署名σvkのコミットメントＬvk、及び上記ＢＢ署名ｚのコミットメントＬzを、それぞれ、
【数６７】
により生成して出力するコミットメント生成器と、
上記ｇと、上記ｈと、上記ＢＢ署名鍵ｘIと、上記ＢＢ署名検証鍵ｙIと、上記ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、Ｈ(Ｔ‖ｍ）、及びＨ´(Ｔ）と、上記ＢＢ署名ｚと、上記コミットメントＬ、Ｌvk、及びＬzと、上記値ｓ、ｒ、η、及びｆと、が入力され、Ｑがｇχという形をしていることの証明πＱを、
【数６８】
により生成し、当該署名者ＩのＨ(Ｔ)のＢＢ署名σＩが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明πＣ,Ｌを、
πＣ,Ｌ＝(ｇＨ(Ｔ)・ｙＩ)ｓ・Ｌｒ
により生成し、当該署名者ＩのＨ（vk）のＢＢ署名σvkが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【数６９】
により生成し、また、ｚがｇχという形をしていることの証明πｚを、
【数７０】
により生成し、Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの証明
【数７１】
により生成し、当該署名者ＩのＨ´(Ｔ)のＢＢ署名ｚが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【数７２】
により生成し、更に、上記ＣとしてコミットされたＢＢ署名検証鍵ｙIと同じ値がコミットされた元が上記Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}の中に一つ存在することを示す証明ΠＲ,Ｃを所定の演算により生成し、上記ＬとしてコミットされたＢＢ署名σIと同じ値がΣ＝{σ１、σ２、・・・、σＮ}の中に一つ存在することを示す証明ΠＬ,Σを所定の演算により生成し、上記証明ΠＲ,ＣでリングＲの中に一つ存在した要素をＹＥ、上記証明ΠＬ,Σで上記Σの中に一つ存在した要素をσＥ´としたとき、Ｅ＝Ｅ´であることを示す証明ΠＲ,Σを所定の演算により生成し、生成した各証明を出力する証明生成器と、
上記ＯＴ署名検証鍵vkと、上記ＯＴ署名鍵skと、上記タグＴと、上記メッセージｍと、上記コミットメントＣ、Ｌ、Ｌvk、及びＬzと、上記ＢＢ署名ｚと、上記δと、上記δcrsと、上記Ｑと、上記証明
【数７３】
とが入力され、上記ＯＴ署名鍵skを用いて
【数７４】
の署名sig0を生成し、タグ付き文書（Ｔ、ｍ）の上記Ｒに関する匿名署名
【数７５】
を生成し出力するＯＴ署名生成器と、
を備える匿名署名生成装置。
【請求項２】
請求項１に記載の匿名署名生成装置において、
上記四則演算器は、更に、上記ハッシュ値Ｈ（Ｔ‖ｍ）と上記Ｑとから、ｉ＝Ｉ以外の全てのｉ（１≦ｉ≦ｎ）についてσｉを、σi＝ｇＨ(Ｔ,ｍ)・Ｑｉにより演算して出力し、
上記乱数生成器は、更に、
【数７６】
について、
【数７７】
をランダムに生成して出力し、
上記証明生成器は、更に、上記値ｔτ、λτ、ｗτ、ｔτ´、λτ´、及びｗτ´（１≦τ≦√Ｎ）と、上記集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、上記σｉ（１≦ｉ≦ｎ、ｉ＝Ｉを含む）と、がそれぞれ入力され、上記証明ΠＲ,Ｃを、
【数７８】
の組として生成し、上記証明ΠＬ,Σを、
【数７９】
の組として生成し、上記証明ΠＲ,Σを、
【数８０】
の組として生成することを特徴とする匿名署名生成装置。
【請求項３】
ＯＴ署名検証鍵vkと、匿名署名
【数８１】
とが入力され、ＯＴ署名検証鍵vkを用いてsig0から
【数８２】
を復号するＯＴ署名検証器と、
上記タグＴと、上記ＯＴ署名検証鍵vkと、が入力され、ハッシュ関数Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）を演算して出力するハッシュ関数演算器と、
上記ｇと、上記ｈと、上記ハッシュ値Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）と、上記ＯＴ署名検証器で復号された
【数８３】
とが入力され、
【数８４】
を検証し、また、ΠＲ,Ｃ、ΠＬ,Σ、ΠＲ,Σについてはそれぞれ所定の演算により検証する証明検証器と、
を備え、上記証明検証器におけるすべての検証が成功した場合に、sigをタグ付き文書(Ｔ、ｍ)のリングＲに関する正当な匿名署名とみなす匿名署名検証装置。
【請求項４】
請求項３に記載の匿名署名検証装置において、
上記ΠＲ,Ｃは、
【数８５】
であり、
上記ΠＬ,Σは、
【数８６】
であり、
上記ΠＲ,Σは、
【数８７】
であり、
上記ハッシュ関数演算器は、更に上記ｍが入力され、ハッシュ関数Ｈ(Ｔ‖ｍ)を演算して出力し、
上記証明検証器は、更に上記ハッシュ関数Ｈ(Ｔ‖ｍ)とＲ＝{Ｙ１、Ｙ２、・・・、ＹＮ}とが入力され、全てのｉ（１≦σi≦Ｎ）についてσｉ＝ｇＨ(Ｔ,ｍ)・ＱｉによりΣ＝{σ１、σ２、・・・、σＮ}を復元し、
証明ΠＲ,Ｃについて、
【数８８】
がすべて成立すること、
証明ΠＬ,Σについて、
【数８９】
がすべて成立すること、
証明ΠＲ,Σについて、
【数９０】
がすべて成立すること、
を検証することを特徴とする匿名署名検証装置。
【請求項５】
同一のタグＴで文書が異なる２つのタグ付き文書（Ｔ、ｍ）及び（Ｔ、ｍ´）と、これら２つのタグ付き文書についての、各構成員のＢＢ署名検証鍵のコミットメントの集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}に係る２つの正しい匿名署名
【数９１】
とが入力され、各タグ付き文書について、それぞれσｉ＝ｇＨ(Ｔ,ｍ)・Ｑｉ、σｉ´＝ｇＨ(Ｔ,ｍ´)・Ｑ´ｉにより、ＢＢ署名の集合Σ＝{σ１、σ２、・・・、σＮ}、Σ´＝{σ１´、σ２´、・・・、σＮ´}を復元し、ΣとΣ´とを対照してσI＝σI´となる要素が発見された場合に署名者Ｉを出力する匿名署名追跡判定装置。
【請求項６】
請求項２に記載の匿名署名生成装置と、請求項４に記載の匿名署名検証装置と、請求項５に記載の匿名署名追跡判定装置とを備える追跡機能付き匿名署名システム。
【請求項７】
位数ｎが大きな素数ｐ、ｑの積である巡回群Ｇと、その生成元ｇと、ｈ∈Ｇ（ｈ≠ｇ）と、zcrs∈Ｇと、位数ｎの巡回群ＧＴと、ペアリング関数ｅ：Ｇ×Ｇ→ＧＴと、ハッシュ関数Ｈ：｛０、１}*→Ｚ／ｎＺと、ハッシュ関数Ｈ´（≠Ｈ）：｛０、１}*→Ｚ／ｎＺと、ランダムな値ｘi∈Ｚ／ｎＺ（Ｚ／ｎＺはｎを法とする剰余類群、ｉ∈{１、２、・・・、Ｎ}は構成員の識別子）に基づき、
【数９２】
（ｇxは楕円曲線上の点ｇのスカラー倍（ｘ倍）演算を表す、以下の乗算表記につき同様。）
として得られた各構成員のＢＢ署名検証鍵ｙiのコミットメント
【数９３】
（ｄiはランダムな値（ｄi∈Ｚ／ｎＺ）。ｙ・ｈは楕円曲線上の点ｙと点ｈとの楕円加算を表す、以下の積算表記につき同様。）
の集合Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}と、が公開され、上記各構成員が自身のＢＢ署名検証鍵ｙiとそれに対応する秘密のＢＢ署名鍵ｘiとを保有するという条件下で用いる匿名署名生成方法において、
ＯＴ署名鍵生成器が、ＯＴ署名鍵skと、それと対応するＯＴ署名検証鍵vkと、を生成するＯＴ署名鍵生成ステップと、
ハッシュ関数演算器が、署名対象事項を特定する情報issueと上記ＲとからなるタグＴ＝(issue‖Ｙ１‖Ｙ２‖・・・‖ＹＮ)（‖はビット結合を表す。）について、ハッシュ値Ｈ（Ｔ）、Ｈ´(Ｔ)、Ｈ（Ｔ‖ｍ）、及びＨ(vk)を演算するハッシュ関数演算ステップと、
ＢＢ署名生成器が、上記構成員である署名者Ｉ∈｛１、２、・・、Ｎ｝のＢＢ署名鍵ｘIを用いて、上記Ｈ(Ｔ) 、Ｈ（vk）、及びＨ´(Ｔ)のＢＢ署名σI、σvk、及びｚをそれぞれ、
【数９４】
により生成するＢＢ署名生成ステップと、
四則演算器がＱを、
【数９５】
により演算する四則演算ステップと、
乱数生成器が、ランダムな値η、ｄI、ｓ、ｂ、ｆ、ｒ∈Ｚ／ｎＺをそれぞれ生成する乱数生成ステップと、
コミットメント生成器が、上記ＢＢ署名検証鍵ｙIのコミットメントＣ、上記ＢＢ署名σIのコミットメントＬ、上記ＢＢ署名σvkのコミットメントＬvk、及び上記ＢＢ署名ｚのコミットメントＬzを、それぞれ、
【数９６】
により生成するコミットメント生成ステップと、
証明生成器が、上記署名者IのもとにloggＱが存在し、Ｑがｇχという形をしていることの証明πＱを、
【数９７】
により生成し、当該署名者ＩのＨ(Ｔ)のＢＢ署名σＩが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明πＣ,Ｌを、
πＣ,Ｌ＝(ｇＨ(Ｔ)・ｙＩ)ｓ・Ｌｒ
により生成し、当該署名者ＩのＨ（vk）のＢＢ署名σvkが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【数９８】
により生成し、また、上記署名者Iのもとにloggｚが存在し、ｚがｇχという形をしていることの証明πｚを、
【数９９】
により生成し、Ｌｚがｚかｚcrsのいずれかをコミットしたものであることの証明
【数１００】
により生成し、当該署名者ＩのＨ´(Ｔ)のＢＢ署名ｚが当該署名者ＩのＢＢ署名検証鍵ｙＩに対応する署名であることの証明
【数１０１】
により生成し、更に、上記ＣとしてコミットされたＢＢ署名検証鍵ｙIと同じ値がコミットされた元が上記Ｒ＝{Ｙ１、Ｙ２、・・・、ＹＮ}の中に一つ存在することを示す証明ΠＲ,Ｃを所定の演算により生成し、上記ＬとしてコミットされたＢＢ署名σIと同じ値がΣ＝{σ１、σ２、・・・、σＮ}の中に一つ存在することを示す証明ΠＬ,Σを所定の演算により生成し、上記証明ΠＲ,ＣでリングＲの中に一つ存在した要素をＹＥ、上記証明ΠＬ,Σで上記Σの中に一つ存在した要素をσＥ´としたとき、Ｅ＝Ｅ´であることを示す証明ΠＲ,Σを所定の演算により生成する証明生成ステップと、
ＯＴ署名生成器が、上記ＯＴ署名鍵skを用いて
【数１０２】
の署名sig0を生成し、タグ付き文書（Ｔ、ｍ）の上記Ｒに関する匿名署名
【数１０３】
を生成するＯＴ署名生成ステップと、
を実行する匿名署名生成方法。
【請求項８】
請求項７に記載の匿名署名生成方法において、
上記四則演算ステップにおいては、更に、上記ハッシュ値Ｈ（Ｔ‖ｍ）と上記Ｑとから、ｉ＝Ｉ以外の全てのｉ（１≦ｉ≦ｎ）についてσｉを、σi＝ｇＨ(Ｔ,ｍ)・Ｑｉにより演算し、
上記乱数生成ステップにおいては、更に、
【数１０４】
について、
【数１０５】
をランダムに生成し、
上記証明生成ステップにおいては、更に、上記証明ΠＲ,Ｃを、
【数１０６】
の組として生成し、上記証明ΠＬ,Σを、
【数１０７】
の組として生成し、上記証明ΠＲ,Σを、
【数１０８】
の組として生成することを特徴とする匿名署名生成方法。
【請求項９】
ＯＴ署名検証器が、匿名署名
【数１０９】
についてＯＴ署名検証鍵vkを用いて、sig0から
【数１１０】
を復号するＯＴ署名検証ステップと、
ハッシュ関数演算器が、ハッシュ関数Ｈ(Ｔ）、Ｈ（vk）、及びＨ´(Ｔ）を演算するハッシュ関数演算ステップと、
証明検証器が、
【数１１１】
を検証し、また、ΠＲ,Ｃ、ΠＬ,Σ、ΠＲ,Σについてはそれぞれ所定の演算により検証する証明検証ステップと、
を実行し、上記証明検証ステップにおけるすべての検証が成功した場合に、sigをタグ付き文書(Ｔ、ｍ)のリングＲに関する正当な匿名署名とみなす匿名署名検証方法。
【請求項１０】
請求項９に記載の匿名署名検証方法において、
上記ΠＲ,Ｃは、
【数１１２】
であり、
上記ΠＬ,Σは、
【数１１３】
であり、
上記ΠＲ,Σは、
【数１１４】
であり、
上記ハッシュ関数演算ステップにおいては、更にハッシュ関数Ｈ(Ｔ‖ｍ)を演算し、
上記証明検証ステップにおいては、更に、全てのｉ（１≦σi≦Ｎ）について、σｉ＝ｇＨ(Ｔ,ｍ)・ＱｉによりΣ＝{σ１、σ２、・・・、σＮ}を復元し、
証明ΠＲ,Ｃについて、
【数１１５】
がすべて成立すること、
証明ΠＬ,Σについて、
【数１１６】
がすべて成立すること、
証明ΠＲ,Σについて、
【数１１７】
がすべて成立すること、
を検証することを特徴とする匿名署名検証方法。
【請求項１１】
匿名署名追跡判定装置が、同一のタグＴで文書が異なる２つのタグ付き文書（Ｔ、ｍ）及び（Ｔ、ｍ´）について、それぞれσｉ＝ｇＨ(Ｔ,ｍ)・Ｑｉ、σｉ´＝ｇＨ(Ｔ,ｍ´)・Ｑ´ｉによりＢＢ署名の集合Σ＝{σ１、σ２、・・・、σＮ}、Σ´＝{σ１´、σ２´、・・・、σＮ´}を復元し、ΣとΣ´とを対照してσI＝σI´となる要素が発見された場合に署名者Ｉを出力する匿名署名追跡判定方法。
【請求項１２】
請求項１〜６のいずれかに記載した装置又はシステムとしてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１０−１６４９２７（Ｐ２０１０−１６４９２７Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−９３８０（Ｐ２００９−９３８０）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]