(57)【要約】【課題】匿名化可能署名の匿名性を向上させる。【解決手段】安全パラメタを入力として、エージェント秘密鍵ｗとシステムパラメタρとを生成するセットアップ手段と、前記システムパラメタρを入力として、署名者の秘密鍵ｘと公開鍵ｙとを生成する鍵生成手段と、前記秘密鍵ｘと、署名が付与される対象のメッセージｍとを入力として、前記メッセージｍに対する署名ｒを生成する署名生成手段と、前記署名者の識別子ｉと、前記エージェント秘密鍵ｗと、前記署名ｒと、前記署名者が属するグループを示すリングＬと、前記リングＬに属する署名者の公開鍵ｙのリストｙＬと、前記メッセージｍとを入力として、前記署名ｒを匿名化したリング署名σを生成する匿名化手段と、前記リングＬと、前記リストｙＬと、前記メッセージｍと、前記リング署名σとを入力として、前記メッセージｍの検証結果ｂを出力する検証手段と、を有することを特徴とする。【選択図】図１
2019213092.tif 000002
【特許請求の範囲】
【請求項１】
安全パラメタを入力として、エージェント秘密鍵ｗとシステムパラメタρとを生成するセットアップ手段と、
前記システムパラメタρを入力として、署名者の秘密鍵ｘと公開鍵ｙとを生成する鍵生成手段と、
前記秘密鍵ｘと、署名が付与される対象のメッセージｍとを入力として、前記メッセージｍに対する署名ｒを生成する署名生成手段と、
前記署名者の識別子ｉと、前記エージェント秘密鍵ｗと、前記署名ｒと、前記署名者が属するグループを示すリングＬと、前記リングＬに属する署名者の公開鍵ｙのリストｙＬと、前記メッセージｍとを入力として、前記署名ｒを匿名化したリング署名σを生成する匿名化手段と、
前記リングＬと、前記リストｙＬと、前記メッセージｍと、前記リング署名σとを入力として、前記メッセージｍの検証結果ｂを出力する検証手段と、
を有することを特徴とする匿名署名システム。
【請求項２】
前記セットアップ手段は、
Ｔｒａｐｄｏｏｒ  ＤＤＨ群の離散対数から一様ランダムに選択した要素を前記エージェント秘密鍵ｗとし、
前記匿名化手段は、
前記エージェント秘密鍵ｗを用いた知識証明を生成することで、前記リング署名σを生成する、
ことを特徴とする請求項１に記載の匿名署名システム。
【請求項３】
前記匿名化手段は、
前記エージェント秘密鍵ｗを用いて前記Ｔｒａｐｄｏｏｒ  ＤＤＨ群に定義されたペアリングを計算した結果と、前記署名ｒを用いて前記ペアリングを計算した結果とが一致する場合に、前記知識証明を生成する、
ことを特徴とする請求項２に記載の匿名署名システム。
【請求項４】
メッセージｍに対する署名ｒの匿名化を行う匿名署名生成装置とネットワークを介して接続される署名生成装置であって、
前記匿名署名生成装置で生成されたシステムパラメタρを入力として、署名者の秘密鍵ｘと公開鍵ｙとを生成する鍵生成手段と、
前記秘密鍵ｘと、前記メッセージｍとを入力として、前記メッセージｍに対する署名ｒを生成する署名生成手段と、
前記メッセージｍと前記署名ｒとを前記匿名署名生成装置に送信する送信手段と、
を有することを特徴とする署名生成装置。
【請求項５】
メッセージｍに対する署名ｒを生成する署名生成装置とネットワークを介して接続される匿名署名生成装置であって、
安全パラメタを入力として、エージェント秘密鍵ｗとシステムパラメタρとを生成するセットアップ手段と、
前記署名生成装置で生成された署名ｒと、前記署名ｒに対応するメッセージｍと、前記署名ｒの署名者の識別子ｉと、前記エージェント秘密鍵ｗと、前記署名者が属するグループを示すリングＬと、前記リングＬに属する署名者の公開鍵ｙのリストｙＬとを入力として、前記署名ｒを匿名化したリング署名σを生成する匿名化手段と、
を有することを特徴とする匿名署名生成装置。
【請求項６】
メッセージｍに対する署名ｒを匿名化したリング署名σを生成する匿名署名生成装置とネットワークを介して接続される署名生成装置であって、
前記署名ｒを署名した署名者が属するグループを示すリングＬと、前記リングＬに属する署名者の公開鍵ｙのリストｙＬと、前記メッセージｍと、前記リング署名σとを入力として、前記メッセージｍの検証結果ｂを出力する検証手段、
を有することを特徴とする検証装置。
【請求項７】
安全パラメタを入力として、エージェント秘密鍵ｗとシステムパラメタρとを生成するセットアップ手順と、
前記システムパラメタρを入力として、署名者の秘密鍵ｘと公開鍵ｙとを生成する鍵生成手順と、
前記秘密鍵ｘと、署名が付与される対象のメッセージｍとを入力として、前記メッセージｍに対する署名ｒを生成する署名生成手順と、
前記署名者の識別子ｉと、前記エージェント秘密鍵ｗと、前記署名ｒと、前記署名者が属するグループを示すリングＬと、前記リングＬに属する署名者の公開鍵ｙのリストｙＬと、前記メッセージｍとを入力として、前記署名ｒを匿名化したリング署名σを生成する匿名化手順と、
前記リングＬと、前記リストｙＬと、前記メッセージｍと、前記リング署名σとを入力として、前記メッセージｍの検証結果ｂを出力する検証手順と、
をコンピュータが実行することを特徴とする匿名署名方法。
【請求項８】
コンピュータを、請求項４に記載の署名生成装置における各手段、請求項５に記載の匿名署名生成装置における各手段又は請求項６に記載の検証装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、匿名署名システム、署名生成装置、匿名署名生成装置、検証装置、匿名署名方法及びプログラムに関する。
【背景技術】
【０００２】
署名者の匿名性を守りつつ電子署名を行う方法として匿名署名が知られている（例えば特許文献１）。このような匿名署名の１つとして、リング署名が知られている。リング署名では、署名がグループのメンバにより作成されたことを第三者が検証することができるが、グループのどのメンバにより署名が作成されたかは特定することができず、また、グループ管理者も存在しない。
【０００３】
また、リング署名の拡張として、匿名化可能署名（Anonymizable Signature）が知られている（例えば非特許文献１）。匿名化可能署名では、署名されたメッセージを持つ者は誰でも後からその署名を匿名署名に変換することができる。このため、或るグループ（リング）に属する署名者は、自身の秘密鍵を用いて署名したメッセージを或るエージェント（例えば、署名を預かって、管理する第三者）に渡しておけば、当該署名の匿名化に関与する必要がない。言い換えれば、エージェントのみで当該署名を匿名化することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４８７５４４８号公報
【非特許文献】
【０００５】
【非特許文献１】F. Hoshino, T. Kobayashi, and K. Suzuki, "Anonymizable signature and its construction from pairings,", Pairing-Based Cryptography - Pairing 2010 - 4th International Conference, Yamanaka Hot Spring, Japan, December 2010. Proceedings, ed. M. Joye, A. Miyaji, and A. Otsuka, Lecture Notes in Computer Science, vol.6487, pp.62-77, Springer, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来の匿名化可能署名では、署名者がエージェントに渡す署名は通常の署名であり、例えば、漏洩によって攻撃者がこの署名を入手した場合、当該攻撃者は、エージェント同様に、署名者がこの署名を行ったことを確認できてしまう。
【０００７】
本発明は、上記の点に鑑みてなされたもので、匿名化可能署名の匿名性を向上させることを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明の実施の形態は、安全パラメタを入力として、エージェント秘密鍵ｗとシステムパラメタρとを生成するセットアップ手段と、前記システムパラメタρを入力として、署名者の秘密鍵ｘと公開鍵ｙとを生成する鍵生成手段と、前記秘密鍵ｘと、署名が付与される対象のメッセージｍとを入力として、前記メッセージｍに対する署名ｒを生成する署名生成手段と、前記署名者の識別子ｉと、前記エージェント秘密鍵ｗと、前記署名ｒと、前記署名者が属するグループを示すリングＬと、前記リングＬに属する署名者の公開鍵ｙのリストｙＬと、前記メッセージｍとを入力として、前記署名ｒを匿名化したリング署名σを生成する匿名化手段と、前記リングＬと、前記リストｙＬと、前記メッセージｍと、前記リング署名σとを入力として、前記メッセージｍの検証結果ｂを出力する検証手段と、を有することを特徴とする。
【発明の効果】
【０００９】
匿名化可能署名の匿名性を向上させることができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態における匿名署名システムの全体構成の一例を示す図である。
【図２】本発明の実施の形態におけるセットアップ処理の一例を示すフローチャートである。
【図３】本発明の実施の形態における鍵生成処理の一例を示すフローチャートである。
【図４】本発明の実施の形態における署名処理の一例を示すフローチャートである。
【図５】本発明の実施の形態における匿名化処理の一例を示すフローチャートである。
【図６】本発明の実施の形態における検証処理の一例を示すフローチャートである。
【図７】本発明の実施の形態における署名生成装置、匿名署名生成装置及び署名検証装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について説明する。以降では、匿名化可能署名が漏洩した場合であっても、当該匿名化可能署名を誰が行ったのかを確認することが困難な匿名署名システム１（すなわち、匿名化可能署名の匿名性を向上させた匿名署名システム１）について説明する。
【００１２】
＜表記＞
本発明の実施の形態では、以下の表記を導入する。
【００１３】
・集合Ｘから一様ランダムに選択された要素をｘとすることを、
【００１４】
【数１】
2019213092.tif 000003
と表記する。これを以降では、「ｘ←＄Ｘ」又は「Ｘ→＄ｘ」とも表す。
【００１５】
・確率的多項式時間アルゴリズムＡｌｇ（）の出力をｘとすることを、
【００１６】
【数２】
2019213092.tif 000004
と表記する。これを以降では、「ｘ←＄Ａｌｇ（）」又は「Ａｌｇ（）→＄ｘ」とも表す。
【００１７】
・ｙをｘで定義する又はｙにｘを代入することを、ｙ←ｘ又はｘ→ｙと表す。ただし、「→」又は「←」は文脈によっては写像（又は関数）を表す。「→」又は「←」が写像を表す場合は、写像（又は関数）であることを明記する。
【００１８】
＜従来の匿名化可能署名の概略＞
ここで、非特許文献１に記載されている匿名化可能署名（従来の匿名化可能署名）の概略について説明する。ｋ∈Ｎ（Ｎは自然数全体の集合）を安全パラメタとし、Ｍ＝｛０，１，・・・｝を署名者集合とする。署名者集合の部分集合Ｌ⊂Ｍはリングと呼ばれる。また、署名者の識別子（例えば、署名者ＩＤ等）をｉとして、識別子ｉの署名者の秘密鍵をｘｉ，公開鍵をｙｉとする。ただし、署名者の識別子ｉを考えない場合は、単に、秘密鍵をｘ、公開鍵をｙと表す。
【００１９】
更に、以降では、簡単のため、リングＬに対して、ａＬ＝（ａｉ）ｉ∈Ｌと定義する。すなわち、例えば、Ｌ＝｛Ｌ０，Ｌ１，・・・｝である場合、ａＬ＝（ａＬ０，ａＬ１，・・・）である。
【００２０】
このとき、従来の匿名化可能署名方式Σは、次の構文を満たす４つの確率的多項式時間アルゴリズム（ＫｅｙＧｅｎ，Ｓｉｇｎ，Ａｎｏｎｙｍｉｚｅ，Ｖｅｒｉｆｙ）により構成される。
【００２１】
・鍵生成アルゴリズムＫｅｙＧｅｎ（１ｋ）→＄（ｘ，ｙ）：安全パラメタ１ｋを入力として、秘密鍵ｘと公開鍵ｙとを出力とする確率的多項式時間アルゴリズム。
【００２２】
・署名アルゴリズムＳｉｇｎ（ｘ，ｍ）→＄ｒ：秘密鍵ｘとメッセージｍとを入力として、署名ｒを出力とする確率的多項式時間アルゴリズム。なお、メッセージｍは、署名ｒが付与される対象である。
【００２３】
・匿名化アルゴリズムＡｎｏｎｙｍｉｚｅ（ｉ，ｒ，Ｌ，ｙＬ，ｍ）→＄σ又は⊥：署名者の識別子ｉと、リングＬ⊂Ｍと、リングＬに属する署名者の公開鍵のリストｙＬと、メッセージｍとを入力として、リング署名σ又は拒絶⊥を出力とする確率的多項式時間アルゴリズム。リング署名σは匿名署名σとも称される。なお、公開鍵のリストｙＬは、ｙＬ＝（ｙｋ）ｋ∈Ｌである。
【００２４】
・検証アルゴリズムＶｅｒｉｆｙ（Ｌ，ｙＬ，ｍ，σ）→＄０又は１：リングＬと、リングＬに属する署名者の公開鍵のリストｙＬと、メッセージｍと、リング署名σとを入力として、単一ビットｂ∈｛０，１｝を出力する確率的多項式時間アルゴリズム。なお、例えば、ｂ＝０が検証失敗を表し、ｂ＝１が検証成功を表す。
【００２５】
・構文：任意の多項式長のメッセージｍ∈｛０，１｝＊と、任意の多項式長のリングＬ⊂Ｍと、任意の署名者の識別子ｉ∈Ｌとに対して、確率
【００２６】
【数３】
2019213092.tif 000005
がｋに関して無視可能である。
【００２７】
上述したように、署名者の匿名性を担保するため、署名ｒは、署名者とエージェントとの間で秘密にしなければならない。すなわち、仮に、漏洩によって攻撃者が署名ｒを入手した場合、当該攻撃者は、エージェント同様に、署名者がこの署名ｒを行ったことを確認できてしまう。このため、エージェントは、署名者から託された署名を秘密として安全に管理する必要がある。通常、エージェントは、多くの署名者から多くの署名を託される場合が多く、託された署名の数に比例して安全に管理すべき秘密の量も大きくなる。ここで、エージェントとは、例えば、署名を預かって、管理する第三者のことである。
【００２８】
なお、上記の従来の匿名化可能署名に関する具体的な構成については、上記の非特許文献１を参照されたい。非特許文献１には、ペアリングを用いた具体的な構成が記載されている。
【００２９】
＜エージェント指定匿名化可能署名＞
本発明の実施の形態では、事前に署名者が指定したエージェントのみが匿名化及び検証することが可能な匿名化可能署名（この匿名化可能署名を「エージェント指定匿名化署名」と表す。）を説明する。
【００３０】
エージェント指定匿名化可能署名方式Σは、次の構文を満たす５つの確率的多項式時間アルゴリズム（Ｓｅｔｕｐ，ＫｅｙＧｅｎ，Ｓｉｇｎ，Ａｎｏｎｙｍｉｚｅ，Ｖｅｒｉｆｙ）により構成される。
【００３１】
・エージェント鍵生成アルゴリズムＳｅｔｕｐ（１ｋ）→＄（ｗ，ρ）：安全パラメタ１ｋを入力として、エージェント秘密鍵ｗとシステムパラメタρとを出力とする確率的多項式時間アルゴリズム。なお、システムパラメタρは、エージェント指定匿名化署名方式Σに参加している参加者（署名者）が知っている共通参照情報であり、エージェント毎に生成及び公開される。また、エージェント秘密鍵ｗは、エージェントが署名ｒの匿名化に用いる秘密情報である。
【００３２】
・鍵生成アルゴリズムＫｅｙＧｅｎ（ρ）→＄（ｘ，ｙ）：システムパラメタρを入力として、秘密鍵ｘと公開鍵ｙとを出力とする確率的多項式時間アルゴリズム。すなわち、鍵生成アルゴリズムＫｅｙＧｅｎ（ρ）は、１以上のエージェントのうち、署名者が指定したエージェントにより公開されているシステムパラメタρを入力として、秘密鍵ｘと公開鍵ｙとを出力する。
【００３３】
・署名アルゴリズムＳｉｇｎ（ｘ，ｍ）→＄ｒ：秘密鍵ｘとメッセージｍとを入力として、署名ｒを出力とする確率的多項式時間アルゴリズム。
【００３４】
・匿名化アルゴリズムＡｎｏｎｙｍｉｚｅ（ｉ，ｗ，ｒ，Ｌ，ｙＬ，ｍ）→＄σ又は⊥：署名者の識別子ｉと、当該署名者の署名ｒと、リングＬ⊂Ｍと、リングＬに属する署名者の公開鍵のリストｙＬと、当該署名ｒに対応するメッセージｍと、エージェント秘密鍵ｗとを入力として、リング署名σ又は拒絶⊥を出力とする確率的多項式時間アルゴリズム。なお、リング署名σは匿名署名とも称される。
【００３５】
・検証アルゴリズムＶｅｒｉｆｙ（Ｌ，ｙＬ，ｍ，σ）→＄０又は１：リングＬと、リングＬに属する署名者の公開鍵のリストｙＬと、メッセージｍと、リング署名σとを入力として、単一ビットｂ∈｛０，１｝を出力する確率的多項式時間アルゴリズム。なお、例えば、ｂ＝０である場合はメッセージｍが正当でないことを表し、ｂ＝１である場合はメッセージｍが正当であることを表す。
【００３６】
・構文：任意の多項式長のメッセージｍ∈｛０，１｝＊と、任意の多項式長のリングＬ⊂Ｍと、任意の署名者の識別子ｉ∈Ｌとに対して、確率
【００３７】
【数４】
2019213092.tif 000006
がｋに関して無視可能である。
【００３８】
上記のエージェント指定匿名化可能署名では、仮に署名ｒが攻撃者に漏洩したとしても、エージェント秘密鍵ｗが漏洩していなければ、署名ｒがどの秘密鍵ｘｉによって作成された署名であるのかが計算量的に識別困難となる。すなわち、エージェント指定匿名化可能署名では、署名ｒの匿名化にエージェント秘密鍵ｗが必要であるため、署名者が指定したエージェントでのみ匿名化及び検証が可能となる。したがって、エージェント指定匿名化可能署名では、エージェント秘密鍵ｗが漏洩しなければ、署名ｒの匿名性が担保される。
【００３９】
上記のエージェント指定匿名化可能署名方式Σを実現するために、以降では、いくつかの概念について説明する。
【００４０】
＜Ｔｒａｐｄｏｏｒ  ＤＤＨ＞
例えば以下の参考文献１にはペアリングを拡張した特殊なＴｒａｐｄｏｏｒ  ＤＤＨ群の具体的構成が記載されている。
【００４１】
［参考文献１］
F. Hoshino, "A Variant of Diffie-Hellman Problem and How to Prove Independency." SCIS 2014 The 31st Symposium on Cryptography and Information Security Kagoshima, Japan, Jan. 21 - 24, 2014.
上記のエージェント指定匿名化署名の具体的構成を与えるために、このＴｒａｐｄｏｏｒ  ＤＤＨ群を用いる。Ｔｒａｐｄｏｏｒ  ＤＤＨ群の概略は以下の通りである。
【００４２】
・ｐを十分大きい素数とする。
【００４３】
・Ｅを有限体Ｆｐ上の超特異楕円曲線とし、位数が十分大きい素数ｑで割り切れるものとする。なお、Ｆｐ＝Ｚ／ｐＺ（Ｚは整数環）である。
【００４４】
・αをＥ（Ｆｐ）［ｑ］の生成元とする。
【００４５】
このとき、Ｇ：＝ＧＬ（ｎ，〈α〉）⊆〈α〉ｎ×ｎ，Ｒ：＝ＧＬ（ｎ，Ｆｑ）⊆Ｆｑｎ×ｎとする。これにより、Ｇは成分毎の楕円加算を群演算とするアーベル群であり、このアーベル群をＴｒａｐｄｏｏｒ  ＤＤＨ群と見做すことができる。また、Ｒは非可換環であり、Ｇに関する離散対数と見做すことができる。更に、後述するように、Ｇ上で自然なペアリング写像を定義することができる。
【００４６】
＜離散対数＞
巡回群を〈α〉，位数をｑ（ただし、ｑは素数）とする。このとき、
【００４７】
【数５】
2019213092.tif 000007
とした場合に、
【００４８】
【数６】
2019213092.tif 000008
に対して、
【００４９】
【数７】
2019213092.tif 000009
を離散対数と呼ぶ。このとき、ｈをαｒとも表す。また、ｒがｎ×ｎの単位行列である場合は、αｒをＩｎと表す。なお、上述したように、Ｇ＝ＧＬ（ｎ，〈α〉）は離散対数が正則な〈α〉ｎ×ｎの部分群であり、成分毎の楕円加算を群演算とするアーベル群である。
【００５０】
一例として、ｎ＝２の場合に、以下のｇ，ｈ∈Ｇの演算を示す。
【００５１】
【数８】
2019213092.tif 000010
加法表記した場合は以下となる。
【００５２】
【数９】
2019213092.tif 000011
また、乗法表記した場合は以下となる。
【００５３】
【数１０】
2019213092.tif 000012
＜右冪乗・左冪乗＞
ｇ，ｇ１，ｇ２∈Ｇとして、これらｇ，ｇ１，ｇ２の各成分の指数部分により構成される行列をそれぞれｘ，ｘ１，ｘ２∈Ｒとした場合、以下の関係を満たすように左冪乗と右冪乗とが定義されているものとする。
【００５４】
【数１１】
2019213092.tif 000013
このとき、右冪乗・左冪乗に関してＲが非可換環である場合、［Ｇ，Ｒ］には右冪乗・左冪乗を計算するための以下の確率的多項式時間アルゴリズムが存在する。
【００５５】
・Ｇ，Ｒに関する非退化双準同型写像ｒｐｏｗ：Ｇ×Ｒ→Ｇ
・Ｇ，Ｒに関する非退化双準同型写像ｌｐｏｗ：Ｒ×Ｇ→Ｇ
なお、ｒｐｏｗは右冪乗を、ｌｐｏｗは左冪乗を計算するための写像である。ｒｐｏｗ及びｌｐｏｗはいずれも結合律を満たす。
【００５６】
一例として、ｎ＝２の場合に、以下のｘ，ｙ∈Ｒの演算を示す。この演算は離散対数上の行列乗算（ｘ（αｙ）＝αｘｙ，（αｙ）ｘ＝αｙｘ）と考える。
【００５７】
【数１２】
2019213092.tif 000014
このとき、ｘｇ，ｇｘを乗法表記した場合は以下となる。また、ｘＩｎ，Ｉｎｘについても以下に示す。
【００５８】
【数１３】
2019213092.tif 000015
なお、エージェント指定匿名化可能署名とは直接は関係ないが、上述したように、ｘ，ｙ∈Ｒ、ｇ∈Ｇに対してｘ（ｇｙ）＝（ｘｇ）ｙが成立するため、このことから鍵交換を実現することもできる。
【００５９】
＜ペアリング＞
Ｇ上で以下の自然なペアリング写像を定義することができる。
【００６０】
【数１４】
2019213092.tif 000016
このペアリング写像は離散対数上の行列乗算（ｅ（αｘ，αｙ）＝ξｘｙ）と考える。
【００６１】
一例として、ｎ＝２の場合に、ｇ，ｈ∈Ｇを以下とする。
【００６２】
【数１５】
2019213092.tif 000017
このとき、ペアリング写像ｅ（ｇ，ｈ）は以下で定義できる。
【００６３】
【数１６】
2019213092.tif 000018
＜匿名署名システム１の全体構成＞
以降では、上記のエージェント指定匿名化可能署名方式Σを実現する匿名署名システム１について、図１を参照しながら説明する。図１は、本発明の実施の形態における匿名署名システム１の全体構成の一例を示す図である。
【００６４】
図１に示すように、本発明の実施の形態における匿名署名システム１には、複数の署名生成装置１０と、１以上の匿名署名生成装置２０と、１以上の署名検証装置３０とが含まれる。また、署名生成装置１０と、匿名署名生成装置２０と、署名検証装置３０とは、例えばインターネット等の通信ネットワーク４０を介して通信可能に接続されている。
【００６５】
署名生成装置１０は、署名者が利用するコンピュータ又はコンピュータシステムであり、秘密鍵ｘ及び公開鍵ｙの生成と、署名ｒの生成（作成）とを行う。署名生成装置１０は、鍵生成部１１０と、署名生成部１２０とを有する。
【００６６】
鍵生成部１１０は、エージェント指定匿名化可能署名方式Σの鍵生成アルゴリズムＫｅｙＧｅｎ（ρ）を実行する。すなわち、鍵生成部１１０は、署名者が指定したエージェントが公開しているシステムパラメタρを入力として、秘密鍵ｘと公開鍵ｙとを出力する。出力された秘密鍵ｘは、例えば、署名生成装置１０の補助記憶装置等に記憶される。一方で、出力された公開鍵ｙは任意の方法で公開される。
【００６７】
署名生成部１２０は、エージェント指定匿名化可能署名方式Σの署名アルゴリズムＳｉｇｎ（ｘ，ｍ）を実行する。すなわち、署名生成部１２０は、秘密鍵ｘとメッセージｍとを入力として、署名ｒを出力する。出力された署名ｒは、メッセージｍと共に、上記で署名者が指定したエージェントの匿名署名生成装置２０に送信される。
【００６８】
なお、鍵生成部１１０及び署名生成部１２０は、例えば、署名生成装置１０にインストールされた１以上のプログラムがプロセッサ等に実行させる処理により実現される。
【００６９】
匿名署名生成装置２０は、エージェントが利用するコンピュータ又はコンピュータシステムであり、エージェント鍵ｗの生成と、署名ｒの匿名化とを行う。匿名署名生成装置２０は、セットアップ部２１０と、匿名化部２２０とを有する。
【００７０】
セットアップ部２１０は、エージェント鍵生成アルゴリズムＳｅｔｕｐ（１ｋ）を実行する。すなわち、セットアップ部２１０は、安全パラメタ１ｋを入力として、エージェント秘密鍵ｗとシステムパラメタρとを出力する。出力されたエージェント秘密鍵ｗは、例えば、匿名署名生成装置２０の補助記憶装置等に記憶される。一方で、出力されたシステムパラメタρは任意の方法で公開される。
【００７１】
匿名化部２２０は、匿名化アルゴリズムＡｎｏｎｙｍｉｚｅ（ｉ，ｒ，Ｌ，ｙＬ，ｍ，ｗ）を実行する。すなわち、匿名化部２２０は、署名者の識別子ｉと、当該署名者の署名ｒと、リングＬと、リングＬに属する署名者の公開鍵のリストｙＬと、当該署名ｒに対応するメッセージｍと、エージェント秘密鍵ｗとを入力として、リング署名σ又は拒絶⊥を出力する。
【００７２】
なお、セットアップ部２１０及び匿名化部２２０は、例えば、匿名署名生成装置２０にインストールされた１以上のプログラムがプロセッサ等に実行させる処理により実現される。
【００７３】
署名検証装置３０は、エージェントやエージェントとは異なる第三者が利用するコンピュータ又はコンピュータシステムであり、リング署名σの検証を行う。署名検証装置３０は、検証部３１０を有する。
【００７４】
検証部３１０は、検証アルゴリズムＶｅｒｉｆｙ（Ｌ，ｙＬ，ｍ，σ）を実行する。すなわち、検証部３１０は、リングＬと、リングＬに属する署名者の公開鍵のリストｙＬと、メッセージｍと、リング署名σとを入力として、単一ビットｂ∈｛０，１｝を出力する。
【００７５】
なお、検証部３１０は、署名検証装置３０にインストールされた１以上のプログラムがプロセッサ等に実行させる処理により実現される。
【００７６】
以上により、本発明の実施の形態における匿名署名システム１は、エージェント指定匿名化可能署名方式Σを実現することができる。このエージェント指定匿名化可能署名方式Σは、上記の数４に示した構文を満たすものとする。
【００７７】
なお、図１に示す匿名署名システム１の構成は一例であって、他の構成であっても良い。例えば、匿名署名生成装置２０と署名検証装置３０とが一体で構成されていても良い。
【００７８】
＜匿名署名システム１の処理の詳細＞
Ｇを上記のＴｒａｐｄｏｏｒ  ＤＤＨ群、ＲをＧに関する離散対数とし、ＧＴ＝ＧＬ（ｎ，〈ｅ（α，α）〉）とする。また、ｅ：Ｇ×Ｇ→ＧＴを上記のＴｒａｐｄｏｏｒ  ＤＤＨ群のペアリング写像とし、写像Ｈ：｛０，１｝＊→Ｇ及び写像Ｈ´：｛０，１｝＊→Ｒを互いに独立なランダムオラクルとする。更に、システムパラメタρをρ＝（Ｒ，Ｇ，ＧＴ，ｅ，ｇ，Ｈ，Ｈ´）とする。
【００７９】
（セットアップ処理）
まず、セットアップ部２１０が実行するセットアップ処理について、図２を参照しながら説明する。図２は、本発明の実施の形態におけるセットアップ処理の一例を示すフローチャートである。
【００８０】
ステップＳ１０１：まず、セットアップ部２１０は、安全パラメタ１ｋを入力する。
【００８１】
ステップＳ１０２：次に、セットアップ部２１０は、ｗ←＄Ｒとしてエージェント秘密鍵ｗを生成する。すなわち、セットアップ部２１０は、Ｒから一様ランダムに選択された要素をエージェント秘密鍵ｗとする。
【００８２】
ステップＳ１０３：次に、セットアップ部２１０は、ｇ←Ｉｎｗとした後、ρ←（Ｒ，Ｇ，ＧＴ，ｅ，ｇ，Ｈ，Ｈ´）としてシステムパラメタρを生成する。すなわち、セットアップ部２１０は、（Ｒ，Ｇ，ＧＴ，ｅ，ｇ，Ｈ，Ｈ´）をシステムパラメタρとする。
【００８３】
ステップＳ１０４：最後に、セットアップ部２１０は、エージェント秘密鍵ｗとシステムパラメタρとを出力する。
【００８４】
これにより、エージェント秘密鍵ｗとシステムパラメタρとが生成される。なお、エージェント秘密鍵ｗは、例えば、匿名署名生成装置２０の補助記憶装置等に記憶される。一方で、システムパラメタρは、署名者に公開される。
【００８５】
（鍵生成処理）
次に、鍵生成部１１０が実行する鍵生成処理について、図３を参照しながら説明する。図３は、本発明の実施の形態における鍵生成処理の一例を示すフローチャートである。なお、図３に示す鍵生成処理では、リングＬに属する或る署名者の署名生成装置１０が秘密鍵ｘと公開鍵ｙとを生成する場合について説明する。
【００８６】
ステップＳ２０１：まず、鍵生成部１１０は、システムパラメタρを入力する。このとき、鍵生成部１１０は、署名者が指定したエージェントが公開しているシステムパラメタρを入力する。
【００８７】
ステップＳ２０２：次に、鍵生成部１１０は、（Ｒ，Ｇ，ＧＴ，ｅ，ｇ，Ｈ，Ｈ´）←ρとシステムパラメタρをパースする。すなわち、鍵生成部１１０は、システムパラメタρを（Ｒ，Ｇ，ＧＴ，ｅ，ｇ，Ｈ，Ｈ´）とする。
【００８８】
ステップＳ２０３：次に、鍵生成部１１０は、ｘ←＄Ｒとした後、ｙ←ｘｇとして秘密鍵ｘと公開鍵ｙとを生成する。
【００８９】
ステップＳ２０４：最後に、鍵生成部１１０は、秘密鍵ｘと公開鍵ｙとを出力する。
【００９０】
これにより、リングＬに属する或る署名者の秘密鍵ｘと公開鍵ｙとが生成される。なお、秘密鍵ｘは、例えば、署名生成装置１０の補助記憶装置等に記憶される。一方で、公開鍵ｙは、エージェントに公開される。
【００９１】
（署名処理）
次に、署名生成部１２０が実行する署名処理について、図４を参照しながら説明する。図４は、本発明の実施の形態における署名処理の一例を示すフローチャートである。なお、図４に示す署名処理では、リングＬに属する或る署名者の署名生成装置１０が署名を生成（作成）する場合について説明する。
【００９２】
ステップＳ３０１：まず、署名生成部１２０は、秘密鍵ｘとメッセージｍとを入力する。
【００９３】
ステップＳ３０２：次に、署名生成部１２０は、ｒ←ｘＨ（ρ，ｍ）として署名ｒを生成する。なお、このρは、上記のステップＳ２０１で署名者が指定したエージェントが公開しているシステムパラメタρである。
【００９４】
ステップＳ３０３：最後に、署名生成部１２０は、署名ｒを出力する。
【００９５】
これにより、署名ｒが生成される。署名ｒは、メッセージｍと共に、上記のステップＳ２０１で署名者が指定したエージェントの匿名署名生成装置２０に送信される。
【００９６】
（匿名化処理）
次に、匿名化部２２０が実行する匿名化処理について、図５を参照しながら説明する。図５は、本発明の実施の形態における匿名化処理の一例を示すフローチャートである。図５に示す匿名化処理では、識別子ｉの署名者の署名ｒを匿名化する場合について説明する。
【００９７】
ステップＳ４０１：まず、匿名化部２２０は、署名者の識別子ｉと、当該署名者の署名ｒと、リングＬと、リングＬに属する署名者の公開鍵リストｙＬと、当該署名ｒに対応するメッセージｍと、エージェント秘密鍵ｗとを入力する。
【００９８】
ステップＳ４０２：次に、匿名化部２２０は、ｈ←Ｈ（ρ，ｍ）としてランダムオラクルＨの出力値ｈを生成する。なお、システムパラメタρは自身が生成したもの用いる。
【００９９】
ステップＳ４０３：次に、匿名化部２２０は、以下の等式が成立するか否かを判定する。
【０１００】
【数１７】
2019213092.tif 000019
ステップＳ４０４：上記の数１７に示す等式が成立しない場合、匿名化部２２０は、拒絶⊥を出力する。この場合は、署名ｒを匿名化することはできない。
【０１０１】
ステップＳ４０５：上記の数１７に示す等式が成立する場合、匿名化部２２０は、
【０１０２】
【数１８】
2019213092.tif 000020
のゼロ知識証明を以下のステップＳ４０５−１〜ステップＳ４０５−３により生成する。
【０１０３】
ステップＳ４０５−１：匿名化部２２０は、
【０１０４】
【数１９】
2019213092.tif 000021
とする。
【０１０５】
ステップＳ４０５−２：匿名化部２２０は、任意のｊ∈Ｌ＼｛ｉ｝に対して、
【０１０６】
【数２０】
2019213092.tif 000022
とする。以上により、Ｔ１，Ｌ＝（Ｔ１，ｋ）ｋ∈Ｌと、Ｔ２，Ｌ＝（Ｔ２，ｋ）ｋ∈Ｌとが得られる。
【０１０７】
ステップＳ４０５−３：匿名化部２２０は、
【０１０８】
【数２１】
2019213092.tif 000023
とする。以上により、ｚ１，Ｌ＝（ｚ１，ｋ）ｋ∈Ｌと、ｚ２，Ｌ＝（ｚ２，ｋ）ｋ∈Ｌと、ｃＬ＝（ｃｋ）ｋ∈Ｌとが得られる。
【０１０９】
ステップＳ４０６：次に、匿名化部２２０は、σ←（Ｕ，ｃＬ，ｚ１，Ｌ，ｚ２，Ｌ）としてリング署名σを生成する。
【０１１０】
ステップＳ４０７：最後に、匿名化部２２０は、リング署名σを出力する。これにより、リング署名σが生成される。
【０１１１】
以上のように、エージェント指定匿名化可能署名方式Σでは、署名ｒの匿名化にエージェント秘密鍵ｗを用いる。このため、署名者が指定したエージェントのみが署名ｒの匿名を行うことができる。したがって、エージェント指定匿名化可能署名方式Σでは、仮に署名ｒが漏洩した場合であっても、エージェント秘密鍵ｗが漏洩しなければ、署名ｒの匿名性を担保することができる。
【０１１２】
（検証処理）
次に、検証部３１０が実行する検証処理について、図６を参照しながら説明する。図６は、本発明の実施の形態における検証処理の一例を示すフローチャートである。
【０１１３】
ステップＳ５０１：まず、検証部３１０は、リングＬと、リングＬに属する署名者の公開鍵リストｙＬと、メッセージｍと、リング署名σとを入力する。
【０１１４】
ステップＳ５０２：次に、検証部３１０は、（Ｕ，ｃＬ，ｚ１，Ｌ，ｚ２，Ｌ）←σとリング署名σをパースする。すなわち、検証部３１０は、リング署名σを（Ｕ，ｃＬ，ｚ１，Ｌ，ｚ２，Ｌ）とする。
【０１１５】
ステップＳ５０３：次に、検証部３１０は、ｈ←Ｈ（ρ，ｍ）としてランダムオラクルＨの出力値ｈを生成する。なお、システムパラメタρはエージェントが生成したものを用いる。
【０１１６】
ステップＳ５０４：次に、検証部３１０は、任意のｊ∈Ｌに対して、
【０１１７】
【数２２】
2019213092.tif 000024
としてＴ１，ｊ及びＴ２，ｊを生成する。
【０１１８】
ステップＳ５０５：次に、検証部３１０は、以下の等式が成立するか否かを判定する。
【０１１９】
【数２３】
2019213092.tif 000025
であるか否かを判定する。
【０１２０】
ステップＳ５０６：上記の数２３に示す等式が成立する場合、検証部３１０は、検証結果として１を出力する。この場合、メッセージｍが正当であることを表す。
【０１２１】
ステップＳ５０７：上記の数２３に示す等式が成立しない場合、検証部３１０は、検証結果として０を出力する。この場合、メッセージｍが正当でないことを表す。
【０１２２】
＜ハードウェア構成＞
最後に、本発明の実施の形態における署名生成装置１０、匿名署名生成装置２０及び署名検証装置３０のハードウェア構成について、図７を参照しながら説明する。図７は、本発明の実施の形態における署名生成装置１０、匿名署名生成装置２０及び署名検証装置３０のハードウェア構成の一例を示す図である。なお、署名生成装置１０、匿名署名生成装置２０及び署名検証装置３０は略同様のハードウェア構成で実現可能であるため、以降では、主に、署名生成装置１０のハードウェア構成について説明する。
【０１２３】
図７に示すように、本発明の実施の形態における署名生成装置１０は、入力装置４０１と、表示装置４０２と、ＲＡＭ（Random Access Memory）４０３と、ＲＯＭ（Read Only Memory）４０４と、プロセッサ４０５と、外部Ｉ／Ｆ４０６と、通信Ｉ／Ｆ４０７と、補助記憶装置４０８とを有する。これら各ハードウェアは、それぞれがバス４０９を介して通信可能に接続されている。
【０１２４】
入力装置４０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置４０２は、例えばディスプレイ等であり、ユーザに対して処理結果等を表示するのに用いられる。なお、署名生成装置１０、匿名署名生成装置２０及び署名検証装置３０は、入力装置４０１及び表示装置４０２のうちの少なくとも一方を有していなくても良い。
【０１２５】
ＲＡＭ４０３は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ４０４は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。プロセッサ４０５は、例えばＣＰＵ（Central Processing Unit）等であり、ＲＯＭ４０４や補助記憶装置４０８等からプログラムやデータをＲＡＭ４０３上に読み出して処理を実行する演算装置である。
【０１２６】
外部Ｉ／Ｆ４０６は、外部装置とのインタフェースである。外部装置には、記録媒体４０６ａ等がある、記録媒体４０６ａとしては、例えば、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等が挙げられる。
【０１２７】
通信Ｉ／Ｆ４０７は、署名生成装置１０を通信ネットワーク４０に接続するためのインタフェースである。署名生成装置１０は、通信Ｉ／Ｆ４０７を介して、他の装置との間でデータ通信を行うことができる。匿名署名生成装置２０及び署名検証装置３０についても同様である。
【０１２８】
補助記憶装置４０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等の不揮発性の記憶装置である。補助記憶装置４０８には、各種データやプログラム（例えば、鍵生成部１１０及び署名生成部１２０を実現する１以上のプログラム）等が記憶されている。なお、匿名署名生成装置２０の補助記憶装置４０８には、例えば、セットアップ部２１０及び匿名化部２２０を実現する１以上のプログラム等が記憶されている。同様に、署名検証装置３０の補助記憶装置４０８には、例えば、検証部３１０を実現する１以上のプログラム等が記憶されている。
【０１２９】
本発明の実施の形態における署名生成装置１０、匿名署名生成装置２０及び署名検証装置３０は、図７に示すハードウェア構成を有することにより、上述した各種処理を実現することができる。なお、図７では、署名生成装置１０、匿名署名生成装置２０及び署名検証装置３０が１台の装置（コンピュータ）で実現されている場合について説明したが、これに限られず、署名生成装置１０、匿名署名生成装置２０及び署名検証装置３０のうちの少なくとも１つが複数台の装置（コンピュータ）で実現されていても良い。
【０１３０】
本発明は、具体的に開示された上記の各実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更、組み合わせ等が可能である。
【符号の説明】
【０１３１】
１        匿名署名システム
１０      署名生成装置
２０      匿名署名生成装置
３０      署名検証装置
４０      通信ネットワーク
１１０    鍵生成部
１２０    署名生成部
２１０    セットアップ部
２２０    匿名化部
３１０    検証部
【図１】
2019213092.tif 000026
【図２】
2019213092.tif 000027
【図３】
2019213092.tif 000028
【図４】
2019213092.tif 000029
【図５】
2019213092.tif 000030
【図６】
2019213092.tif 000031
【図７】
2019213092.tif 000032