(57)【要約】【課題】署名者の匿名性を考慮した電子署名技術において、署名者を特定することなく、二つの署名が同一署名者によって生成されたか否かを判断できる方法を提供する。【解決手段】同一性検証装置は、署名者Ｐｉの識別子Ｃｉ，Ｃｉ′を暗号化し、暗号文Ｅ（Ｃｉ），Ｅ（Ｃｉ′）を開示装置に送信する。開示装置は、準同型暗号関数θ′（Ｅ（Ｃｉ），Σ），θ（Ｅ（Ｃｉ′），Σ′）を計算し、乱数ｓｉ，ｓｉ′を選んで、Ｙｉ＝θ′（Ｅ（Ｃｉ），Σ）ｓi，Ｙｉ′＝θ′（Ｅ（Ｃｉ′））ｓi′を計算し、適当に並び替えたｍ個の組（Ｙｉ，Ｙｉ′）を同一性検証装置に送信する。同一性検証装置は、ｍ個の組（Ｙｉ，Ｙｉ′）を復号し、その復号結果に（１，１）が含まれていると、Σ，Σ′を同一の署名者と判定する。【選択図】図１
2006262256.tif 000002
【特許請求の範囲】
【請求項１】
Ｃｉ，Ｃｉ′（ｉ＝１，…，ｍ）をある有限群Ｇの要素で表現された署名者Ｐｉの識別子とし、Σ，Σ′をそれぞれある署名者によって生成された、ある有限群Ｈｄの要素で表現された署名情報とし（ｄはＨの次元を表す）、θを以下に示す署名者特定のための関数とし、
【数１】
2006262256.tif 000019
ここで¬ｌは１以外のＧの要素を表し、θは開示装置のみ計算出来る関数とし、更にＥを開示装置が以下の関係を満たす関数θ′を計算出来る、
【数２】
2006262256.tif 000020
Ｇからある有限群Ｇ′（以降、記述の都合上Ｇ，Ｇ′内の演算として乗法が定義されているものとする）に写す準同型暗号関数としたとき、
同一性検証装置は開示装置との以下の手順によりΣ，Σ′が同一の署名者によって生成された署名かどうか判定する、
１．同一性検証装置はＣｉ，Ｃｉ′（ｉ＝１，…，ｍ），Σ，Σ′を入力し、自身が復号出来るような暗号化をＣｉ，Ｃｉ′に対して行い（当該暗号文をそれぞれＥ（Ｃｉ），Ｅ（Ｃｉ′）とする）、それらを開示装置に送信する。
２．開示装置はＥ（Ｃｉ），Ｅ（Ｃｉ′）（ｉ＝１，…，ｍ），Σ，Σ′を入力とし、以下を行う。
（ａ）θ′（Ｅ（Ｃｉ），Σ），θ′（Ｅ（Ｃｉ′），Σ′）を計算する。
（ｂ）乱数ｓｉ，ｓｉ′を選び、
【数３】
2006262256.tif 000021
を計算し、当該ｍ個の組（Ｙｉ，Ｙｉ′）を適当な順番に並び替えて、同一性検証装置に送信する。
３．同一性検証装置は当該ｍ個の組（Ｙｉ，Ｙｉ′）を復号し、その復号結果に（１，１）が含まれている場合は同一の署名者と判定する。
ことを特徴とする署名生成者同一性検証方法。
【請求項２】
Ｃｉ，Ｃｉ′（ｉ＝１，…，ｍ）をある有限群Ｇの要素で表現された署名者Ｐｉの識別子とし、Σ，Σ′をそれぞれある署名者によって生成された、ある有限群Ｈｄの要素で表現された署名情報とし（ｄはＨの次元を表す）、θを以下に示す署名者特定のための関数とし、
【数４】
2006262256.tif 000022
ここで¬ｌは１以外のＧの要素を表し、θは開示装置のみ計算出来る関数とし、更にＥを開示装置が以下の関係を満たす関数θ′を計算出来る、Ｇからある有限群Ｇ′（以降、記述の都合上Ｇ，Ｇ′内の演算として乗法が定義されているものとする）に写す準同型暗号関数としたとき、
【数５】
2006262256.tif 000023
同一性検証装置（ｊ）（ｊ＝１，…，Ｋ）は開示装置との以下の手順によりΣ，Σ′が同一の署名者によって生成された署名かどうか判定する、
１．同一性検証装置（ｊ）（ｊ＝１，…，Ｋ）は協力して、Ｃｉ，Ｃｉ′（ｉ＝１，…，ｍ）を入力として、当該同一性検証装置（ｊ）（ｊ＝１，…，Ｋ）が協力してはじめて復号出来るような暗号化をＣｉ，Ｃｉ′に対して行う（それぞれＸi，0＝Ｅ（Ｃｉ），Ｘi，0′＝Ｅ（Ｃｉ′）とする）。
２．ｊ＝１，…，Ｋについて、同一性検証装置２００（ｊ）は順番に以下を行う。
（ａ）ｍ個の暗号文の組（Ｘi，j−1，Ｘi，j−1′）を入力する。
（ｂ）Ｘi，j−1，Ｘi，j−1′をそれぞれ再暗号化し（結果をそれぞれＸi，j，Ｘi，j′とする）、当該ｍ個の組（Ｘi，j，Ｘi，j′）を適当な順番に並び替えて出力する。
３．開示装置はｍ個の暗号文の組（Ｘi，K，Ｘi，K′）、及びΣ，Σ′を入力とし、Ｚi，0＝θ′（Ｘi，K，Σ），Ｚi，0′＝θ′（Ｘi，K′，Σ′）を計算し、出力する。
４．ｊ＝１，…，Ｋについて、同一性検証装置（ｊ）は順番に以下を行う。
（ａ）ｍ個の暗号文の組（Ｚi，j−1，Ｚi，j−1′）を入力する。
（ｂ）乱数ｓi，j，ｓi，j′を選び、
【数６】
2006262256.tif 000024
を計算し、出力する。
５．同一性検証装置（ｊ）（ｊ＝１，…，Ｋ）は協力して、（Ｚi，K，Ｚi，K′）を復号し、その復号結果に（１，１）が含まれている場合は同一の署名者と判定する。
ことを特徴とする署名生成者同一性検証方法。
【請求項３】
請求項１または２記載の署名生成者同一性検証方法において、秘密分散技術により一定数以上の開示装置が協力しない限りθ′を計算出来ないようにする、
ことを特徴とする署名生成者同一性検証方法。
【請求項４】
請求項１〜３のいずれか１項に記載の署名生成者同一性検証方法の何れかにおいて、ゼロ知識証明技術により開示装置及び同一性検証装置は自身の処理正当性を他装置に証明する、
ことを特徴とする署名生成者同一性検証方法。
【請求項５】
ネットワークで結ばれた同一性検証装置及び開示装置を具備し、請求項１〜４のいずれか１項に記載の署名生成者同一性検証方法を実施することを特徴とする署名生成者同一性検証システム。
【請求項６】
請求項１〜４のいずれか１項に記載の署名生成者同一性検証方法をコンピュータに実施させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティの技術分野に閑し、特に時号技術を応用し、署名者の匿名性を考慮した幾つかの電子署名技術に対して、一定数以上の管理者が協力した場合に限り、署名者を特定することなく、二つの署名が同一署名者によって生成されたか否かを判断するための技術に関する。
【背景技術】
【０００２】
署名者の匿名性を考慮した電子署名技術として、グループ署名（例えば非特許文献１）やリング署名（例えば非特許文献２）といった技術が知られている。グループ署名やリング署名は、基本的に任意の二つの署名が同一署名者によって生成されたか否かを判断できないことが特徴の一つである。一方、グループ署名やリング署名を実現する方式の中には、管理者だけは署名者の匿名性を失効出来るように設計されているものもあり、特に当該管理者の失効権限を複数の管理者に分散可能とし、複数の管理者が協力しない限りは署名者の匿名性が保証されるような方法も知られている（例えば非特許文献３）。
【０００３】
【非特許文献１】Ｄ．Ｃhaum  and  Ｅ．Ｖ．Ｈeyst，“Ｇroup  signatures，”ＥＵＲＯＣＲＹＰＴ  ’91，ＬＮＣＳ  547，pp．257−265，Ｓpringer−Ｖerlag，1991．
【非特許文献２】Ｒ．Ｒivest，Ａ．Ｓhamir，and  Ｙ．Ｔauman，“Ｈow  to  leak  a  secret，”ＡＳＩＡＣＲＹＰＴ  ’01，ＬＮＣＳ  2248，pp．552−565，Ｓpringer−Ｖerlag，2001．
【非特許文献３】菊池，多田，中西，“リング署名における署名者の証明と匿名性破棄プロトコル”，情報処理学会論文誌，Ｖol．45，Ｎo.８，pp．1881−1886，Ａug．2004．
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ある権限（秘密鍵）を持った管理者だけは署名者の匿名性を失効出来るような電子署名技術においては、匿名性を失効するための条件を出来るだけ明確化する事が、サービスの運用上非常に重要といえる。その理由は、あるサービスにおいて、匿名性が失効される条件が曖昧であると、利用者は、いつ自身の匿名性が失効されるか分からないという不安感から、当該電子署名を利用し辛くなる事が予想されるためである。
【０００５】
一方、二つの署名が同一署名者によって生成されたか否かを判断出来ないような性質は、匿名性を一層高める事になるため、利用者のプライバシの観点からすれば好ましいといえるが、当該性質を悪用し、別人を装って大量の不正な署名を生成する攻撃が懸念される。例えば、あるサービス業者は、当該電子署名を付与した文書のみを有効な文書とみなすものとしたとき、当該電子署名を付与した、匿名のいたずら文書がサービス業者に送られてきた場合、一つ二つのいたずら文書であれば許容出来たとしても、大量のいたずら文書が送られてくるとサービスが阻害されてしまうかも知れない。しかし当該電子署名の性質により、大量のいたずら文書が同一人物による確信的犯行であるかどうか判断出来ない。この点は解決されるべき課題といえよう。
【０００６】
本発明が解決しようとする課題は、任意の二つの署名が同一署名者によって生成されたか否かを判断出来ないような、署名者の匿名性を考慮した電子署名に対して、一定数以上の管理者が協力した場合に限り、署名者を特定する事無く、二つの署名が同一署名者によって生成されたか否かを判断出来る技術を提供する事である。
【課題を解決するための手段】
【０００７】
本発明で使用するハードウェアはサーバイメージの同一性検証装置及び開示装置である。ここで、本発明の署名生成者同一性検証方法として、同一性検証装置を一つとする場合を第１の方法、複数構成とする場合を第２の方法と称すことにする。
【０００８】
［第１の方法］
Ｃｉ，Ｃｉ′（ｉ＝１，…，ｍ）をある有限群Ｇの要素で表現された署名者Ｐｉの識別子とし、Σ，Σ′をそれぞれある署名者によって生成された、ある有限群Ｈｄの要素で表現された署名情報とし（ｄはＨの次元を表す）、θを以下に示す署名者特定のための関数とし、
【０００９】
【数１】
2006262256.tif 000003
ここで¬ｌは１以外のＧの要素を表し、θは開示装置のみ計算出来る関数とし、更にＥを開示装置が以下の関係を満たす関数θ′を計算出来る、
【００１０】
【数２】
2006262256.tif 000004
Ｇからある有限群Ｇ′（以降、記述の都合上Ｇ，Ｇ′内の演算として乗法が定義されているものとする）に写す準同型暗号関数としたとき、
同一性検証装置は開示装置との以下の手順によりΣ，Σ′が同一の署名者によって生成された署名かどうか判定する。
【００１１】
１．同一性検証装置はＣｉ，Ｃｉ′（ｉ＝１，…，ｍ），Σ，Σ′を入力し、自身が復号出来るような暗号化をＣｉ，Ｃｉ′に対して行い（当該暗号文をそれぞれＥ（Ｃｉ），Ｅ（Ｃｉ′）とする）、それらを開示装置に送信する。
２．開示装置はＥ（Ｃｉ），Ｅ（Ｃｉ′）（ｉ＝１，…，ｍ），Σ，Σ′を入力後、以下の処理を行う。
（ａ）θ′（Ｅ（Ｃｉ），Σ），θ′（Ｅ（Ｃｉ′），Σ′）を計算する。
（ｂ）乱数ｓｉ，ｓｉ′を選び、
【００１２】
【数３】
2006262256.tif 000005
を計算し、当該ｍ個の組（Ｙｉ，Ｙｉ′）を適当な順番に並び替えて、同一性検証装置に送信する。
３．同一性検証装置は当該ｍ個の組（Ｙｉ，Ｙｉ′）を復号し、その復号結果に（１，１）が含まれている場合は同一の署名者と判定する。
【００１３】
［第２の方法］
Ｃｉ，Ｃｉ′（ｉ＝１，…，ｍ）をある有限群Ｇの要素で表現された署名者Ｐｉの識別子とし、Σ，Σ′をそれぞれある署名者によって生成された、ある有限群Ｈｄの要素で表現された署名情報とし（ｄはＨの次元を表す）、θを以下に示す署名者特定のための関数とし、
【００１４】
【数４】
2006262256.tif 000006
ここで¬ｌは１以外のＧの要素を表し、θは開示装置のみ計算出来る関数とし、更にＥを開示装置が以下の関係を満たす関数θ′を計算出来る、Ｇからある有限群Ｇ′（以降、記述の都合上Ｇ，Ｇ′内の演算として乗法が定義されているものとする）に写す準同型暗号関数としたとき、
【００１５】
【数５】
2006262256.tif 000007
同一性検証装置（ｊ）（ｊ＝１，…，Ｋ）は開示装置との以下の手順によりΣ，Σ′が同一の署名者によって生成された署名かどうか判定する。
【００１６】
１．同一性検証装置（ｊ）（ｊ＝１，…，Ｋ）は協力して、Ｃｉ，Ｃｉ′（ｉ＝１，…，ｍ）を入力として、当該同一性検証装置（ｊ）（ｊ＝１，…，Ｋ）が協力してはじめて復号出来るような暗号化をＣｉ，Ｃｉ′に対して行う（それぞれＸi，0＝Ｅ（Ｃｉ），Ｘi，0′＝Ｅ（Ｃｉ′）とする）。
２．ｊ＝１，…，Ｋについて、同一性検証装置２００（ｊ）は順番に以下を行う。
（ａ）ｍ個の暗号文の組（Ｘi，j−1，Ｘi，j−1′）を入力する。
（ｂ）Ｘi，j−1，Ｘi，j−1′をそれぞれ再暗号化し（結果をそれぞれＸi，j，Ｘi，j′とする）、当該ｍ個の組（Ｘi，j，Ｘi，j′）を適当な順番に並び替えて出力する。
３．開示装置はｍ個の暗号文の組（Ｘi，K，Ｘi，K′）、及びΣ，Σ′を入力とし、Ｚi，0＝θ′（Ｘi，K，Σ），Ｚi，0′＝θ′（Ｘi，K′，Σ′）を計算し、出力する。
４．ｊ＝１，…，Ｋについて、同一性検証装置（ｊ）は順番に以下を行う。
（ａ）ｍ個の暗号文の組（Ｚi，j−1，Ｚi，j−1′）を入力する。
（ｂ）乱数ｓi，j，ｓi，j′を選び、
【００１７】
【数６】
2006262256.tif 000008
を計算し、出力する。
５．同一性検証装置（ｊ）（ｊ＝１，…，Ｋ）は協力して、（Ｚi，K，Ｚi，K′）を復号し、その復号結果に（１，１）が含まれている場合は同一の署名者と判定する。
【発明の効果】
【００１８】
本発明の署名生成者同一性検証方法によれば、任意の二つの署名が同一署名者によって生成されたか否かを判断出来ないような、署名者の匿名性を考慮した電子署名を用いたサービスに対して、例えば、大量のいたずら文書を送信した確信犯がいる疑いがあるときに限り、二つの署名が同一署名者によって生成されたか否かを判断出来る技術を適用し、それによって当該確信犯が存在する事が明らかになったときに限り、次に署名者の匿名性を失効する技術を適用し、当該確信犯を特定する、といった運用が可能になる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施の形態について図面を用いて詳細に説明する。
【００２０】
［第１の実施の形態］
これは、本発明の第１の方法を適用するものである。本実施の形態におけるシステム構成は、図１に示すように、開示装置１００及び一つの同一性検証装置２００からなる。開示装置１００及び同一性検証装置２００はネットワーク３００を介して接続されている。ここでは、非特許文献４で提案された署名方式について、第１の方法に基づき、開示装置１００及び同一性検証装置２００の手続きにより署名生成者の同一性を検証する一例を示す。
［非特許文献４］Ｇ．Ａteniese，Ｊ．Ｃamenisch，Ｍ．Ｊoye，and  Ｇ．Ｔsudik，“Ａ  practical  and  provably  secure  coalition-resistant  group  signature  scheme，”ＣＲＹＰＴＯ  2000，ＬＮＣＳ  1880，pp．255−270，Ｓpringer−Ｖerlag，2000．
【００２１】
先ず非特許文献４で提案された電子署名方式について、本実施の形態の説明に必要な箇所を抜粋して説明する。
【００２２】
ε（＞１），ｋ，ｌｐをセキュリティパラメータとし、λ１，λ２，γ１，γ２を以下の関係を満たす自然数とし、
λ１＞ε(λ２＋ｋ)＋２，λ２＞４ｌｐ，γ１＞ε(γ２＋ｋ)＋２，γ２＞λ１＋２
Ｈを｛０，１｝＊から［ｌ，ｑ］に写す一方向性ハッシュ関数とし、
【００２３】
【数７】
2006262256.tif 000009
とする。そして、Ｘ＝（ε，ｋ，ｌｐ，λ１，λ２，γ１，γ２）とする。なお［ａ，ｂ］でａ以上ｂ以下の整数の集合を表すものとする。
【００２４】
管理者Ｍは以下を行う。
【００２５】
【数８】
2006262256.tif 000010
次にユーザＰｉはグループメンバとなるために管理者Ｍと以下の手続きを行う。
【００２６】
【数９】
2006262256.tif 000011
Ｐｉによる署名生成は以下となる。
【００２７】
【数１０】
2006262256.tif 000012
そして最終的に、管理者ＭはＺを入力として、Ａ＝Ｔ１／Ｔ２ｘを計算し、Ａ＝Ａｉとなるようなｉを求め、そのｉに対応するグループメンバＰｉを署名者と判定する。
【００２８】
次に、本発明の第１の方法を［非特許文献４］で提案されている方式に適用した例を説明する。ここで上記管理者Ｍは、以降、開示装置１００に置き換えて話を進める。図２に本実施の形態の処理フローを示す。
【００２９】
同一性検証装置２００は開示装置１００との以下の手順により［非特許文献３］における署名情報Ｔ２，Ｔ２′が同一の署名者によって生成された署名かどうか判定する（ここでダッシュ（′）が付いた記号は、ダッシュが付いていない記号に対応する。即ち、Ｚ＝（ｃ，ｓ１，ｓ２，ｓ３，ｓ４，Ｔ１，Ｔ２，Ｔ３，msg），Ｚ′＝（ｃ′，ｓ１′，ｓ２′，ｓ３′，ｓ４′，Ｔ１′，Ｔ２′，Ｔ３′，msg′）はそれぞれある二つのメッセージｍｓｇ，ｍｓｇ′の署名情報を意味する）。
【００３０】
１．同一性検証装置２００はＡｉ／Ｔ１，Ａｉ′／Ｔ１′（ｉ＝１，…，ｍ），Ｔ２，Ｔ２′を入力し（ステップ１）、自身が復号出来るような、群ＱＲ（Ｎ）上で定義されるＥlＧamal暗号を用いてＡｉ／Ｔ１，Ａｉ′／Ｔ１′を暗号化し（ステップ２）、暗号文Ｅ（Ａｉ／Ｔ１），Ｅ（Ａｉ′／Ｔ１′）を開示装置１００に送信する（ステップ３）。
２．開示装置１００はＥ（Ａｉ／Ｔ１），Ｅ（Ａｉ′／Ｔ１′）（ｉ＝１，…，ｍ），Ｔ２，Ｔ２′を入力後（ステップ４）、乱数ｓｉ，ｓｉ′を選び（ステップ５）、
【００３１】
【数１１】
2006262256.tif 000013
を計算し（ステップ６）、ｍ個の組（Ｙｉ，Ｙｉ′）を適当な順番に並び替えて（ステップ７）、同一性検証装置２００に送信する（ステップ８）。
３．同一性検証装置２００は当該ｍ個の組（Ｙｉ，Ｙｉ′）を復号し（ステップ９）、その復号結果に（１，１）が含まれている場合は同一の署名者と判定する（ステップ１０）。
【００３２】
上記手続きでは、ＥlＧamal暗号の準同型性により、
【００３３】
【数１２】
2006262256.tif 000014
が成り立つ。従って、Ａｉ＝Ｔ１／Ｔ２ｘかつＡｉ′＝Ｔ１′／Ｔ２′ｘが成り立つｉが存在する、即ち、Ｔ２，Ｔ２′同一署名者が生成した場合は、（Ｙｉ，Ｙｉ′）（ｉ＝１，…，ｍ）の復号結果には（１，１）が存在し、そうでない場合は（１，１）が存在する確率は十分小さい事が期待出来る。また、（Ｙｉ，Ｙｉ′）（ｉ＝１，…，ｍ）は実際には開示装置１００により適当な順番に入れ替わっており、更にＹｉ，Ｙｉ′は１でないときはｓｉ，ｓｉ′によってＱＲ（Ｎ）の１以外のランダムな値に変換される事が期待出来るため、（Ｙｉ，Ｙｉ′）及びそれら復号結果からＴ２，Ｔ２′の署名生成者を特定するための有意な情報を同一性検証装置２００が得る事は困難である事が期待出来る。一方、開示装置１００は同一性検証装置２００のみが復号出来るような暗号文、及び署名者の識別情報を含まない値Ｔ２，Ｔ２′を受け取るだけであるため、ＥlＧamal暗号の秘匿性に基づいて開示装置１００が署名生成者を特定するための有意な情報を同一性検証装置２００が得る事は困難である。
【００３４】
［第２の実施の形態］
これは本発明の第２の方法を適用するものである。本実施の形態におけるシステム構成は、図３に示すように、開示装置１００及び複数の同一性検証装置２００（ｊ）（ｊ＝１，…，Ｋ）からなる。開示装置１００及び複数の同一性検証装置２００（ｊ）はネットワーク３００を介して接続されている。ここでは、［非特許文献３］で提案された署名方式について、第２の方法に基づき署名生成者の同一性を検証し、ゼロ知識証明技術により、開示装置１００及び同一性検証装置２００（ｊ）（ｊ＝１，…，Ｋ）自身の処理正当性を他装置に証明する一例を示す。
【００３５】
先ず［非特許文献３］で提案された電子署名方式について、本実施の形態の説明に必要な箇所を抜粋して説明する。
【００３６】
システムパラメータ、およびグループメンバＰｉの公開鍵は以下となる。
システムパラメータ
（ｐ，ｑ）：ｑ｜ｐ−１を満たす大きな素数の組
Ｈ：｛０，１｝＊→［１，ｑ］への一方向性ハッシュ関数
Ｇｑ：ｑ個の要素を持つＺｐｘの部分群
ｇ：Ｇｐの生成元
グループメンバＰｉの公開鍵    ｙｉ＝ｇｘｉ（ｘｉは［１，ｑ］からランダムに選んだ値）。
その他、管理者は、［１，ｑ］からランダムにｔを選んだ後、ｈ＝ｇｔを計算、公開する。
【００３７】
＜Ｐｉによる署名生成＞
Ｐｉによる署名生成は以下となる。
１．［ｌ，ｑ］からランダムにαを選んだ後、
【００３８】
【数１３】
2006262256.tif 000015
を計算する。ここでｍｓｇは署名対象メッセージとし、ｉ＝ｍならばｉ＋１→１。
２．ｌ＝ｉ＋１，…，ｍ，１，…，ｉ−１について、［１，ｑ］からランダムにｓｌを選んだ後、Ｔｌ＝ｇｓｌｙｌｃｌ，ｃｌ＋１＝Ｈ（msg‖Ｔｌ）を計算する。ここでｌ＝ｍならばｌ＋１→１。
３．（α＝）logｇＴａ＝logｈＵ（modｑ）となるＴａ（１≦α≦ｍ）が存在することを証明するために、ゼロ知識非対話証明技術を用いて、証明に必要な情報Ｖを作成する。
４．ｓｉ＝α−ｘｉｃｉ（modｑ）を計算し、（ｃ１，ｓ１，…，ｓｍ，Ｕ，Ｖ）をｍｓｇの署名とする。
【００３９】
＜署名者開示＞
署名者を特定するための開示処理は以下となる。
１．（ｃ１，ｓ１，…，ｓｍ，Ｕ，Ｖ）を入力として、Ｔｌ＝ｇｓｌｙｌｃｌ（ｌ＝１，…，ｍ）計算する。
２．Ｕｌ＝Ｔｌｔを計算し、Ｕ＝Ｕａを満たすａ（１≦ａ≦ｍ）を求め、ｍｓｇの署名者Ｐａを特定する。
【００４０】
次に、本発明第２の方法を［非特許文献３］で提案されている方式に適用した例を説明する。ここで上記管理者Ｍは、以降、開示装置１００に置き換えて話を進める。図４及び図５に本実施の形態の処理フローを示す。
【００４１】
同一性検証装置２００（ｊ）（ｊ＝１，…，Ｋ）は開示装置１００との以下の手順により［非特許文献３］における署名情報Ｕ，Ｕが同一の署名者によって生成された署名かどうか判定する（ここでダッシュ（′）が付いた記号は、ダッシュが付いていない記号に対応する。即ち、（ｃ１，ｓ１，…，ｓｍ，Ｕ，Ｖ）、（ｃ１′，ｓ１′，…，ｓｍ′，Ｕ′，Ｖ′）はそれぞれある二つのメッセージｍｓｇ、ｍｓｇ′の署名情報を意味する）。
【００４２】
１．同一性検証装置２００（ｊ）（ｊ＝１，…，Ｋ）は協力して、Ｔｉ，Ｔｉ′（ｉ＝１，…，ｍ）を入力として（ステップ１１）、該同一性検証装置２００（ｊ）（ｊ＝１，…，Ｋ）のうち一定数以上が協力してはじめて復号出来る“閾値ＥlＧamal暗号”（［非特許文献５］）を用いてＴｉ，Ｔｉ′を暗号化する（当該暗号文をそれぞれＸi，0＝Ｅ（Ｔｉ），Ｘi，0′＝Ｅ（Ｔｉ′とする）（ステップ１２）。
２．ｊ＝１，…，Ｋについて、同一性検証装置２００（ｊ）は順番に以下を行う。
（ａ）ｍ個の暗号文の組（Ｘi，j-1，Ｘ′i，j-1）を入力する（ステップ１３）。
（ｂ）Ｘi，j-1，Ｘ′i，j-1をそれぞれ再暗号化し（結果をそれぞれＸi，j，Ｘ′i，jとする）（ステップ１４）、当該ｍ個の組（Ｘi，j-1，Ｘ′i，j-1）を適当な順番に並び替えて（ステップ１５）出力する（ステップ１６）。なおその際、当該順番を並び替えた出力の処理正当性を例えば［非特許文献６］の非対話ゼロ知識証明技術を用いて証明する（ステップ１７）。非対話ゼロ知識証明方法とは、要するに、Ｐを底にしたｘｉＰの離散対数、およびＡ″としたｘｉＡ″の離散対数が等しい（すなわち、ともにｘｉとなる）ことを非対話で証明する方法である。
３．開示装置１００はｍ個の暗号文の組（Ｘi，Ｋ，Ｘ′i，Ｋ），及びＵ，Ｕ′を入力とし（ステップ１８）、Ｚi，0＝Ｘｔi，Ｋ／Ｕ，Ｚi，0′＝Ｘｔi，Ｋ′／Ｕ′を計算（ステップ１９）、出力する（ステップ２０）。なおＺi，0，Ｚi，0′を計算する過程でそれぞれＸｔi，Ｋ，Ｘｔi，Ｋ′を計算する必要があるが、この計算結果の処理正当性を例えば［非特許文献７］の非対話ゼロ知識証明技術を用いて証明する（ステップ２１）。
４．ｊ＝１，…，Ｋについて、同一性検証装置２００（ｊ）は順番に以下を行う。
（ａ）ｍ個の暗号文の組（Ｚi，j-1，Ｚi，j-1′）を入力する（ステップ２２）。
（ｂ）［１，ｑ］からランダムにｓi，j，ｓi，j′を選び（ステップ２３）、
【００４３】
【数１４】
2006262256.tif 000016
を計算し（ステップ２４）、出力する（ステップ２５）。なおその際、当該計算結果の処理正当性を例えば［非特許文献７］の非対話ゼロ知識証明技術を用いて証明する（ステップ２６）。
５．同一性検証装置２００（ｊ）（ｊ＝１，…，Ｋ）は協力して、（Ｚi，K，Ｚi，K′）を復号し（ステップ２７）、当該復号結果の処理正当性を例えば［非特許文献７］の非対話ゼロ知識証明技術を用いて証明し（ステップ２８）、復号結果に（１，１）が含まれている場合は同一の署名者と判定する（ステップ２９）。
【００４４】
［非特許文献５］Ｙ．Ｄesmedt  and  Ｙ．Ｆrankel，“Ｔhreshold  cryptosystems，”ＣＲＹＰＴＯ  ’89，ＬＮＣＳ435，ｐｐ．307-315，Ｓpringer−Ｖerlag，1990.
［非特許文献６］Ｊ．Ｇroth，“Ａ  verifiable  secret  shuffle  of  homomorphic  encryptions，”ＰＫＣ  ’03，ＬＮＣＳ2567，ｐｐ．145−160，Ｓpringer−Ｖerlag，2003．
［非特許文献７］Ｄ．Ｌ．Ｃhaum  and  Ｔ．Ｐ．Ｐedersen，“Ｗallet  databases  with  observers,”ＣＲＹＰＴＯ  ’92，ＬＮＣＳ740，ｐｐ.89−105，Ｓpringer-Verlag,1993．
【００４５】
上記手続きでは、ＥlＧamal暗号の持つ準同型性により、
【００４６】
【数１５】
2006262256.tif 000017
が成り立つ。
【００４７】
【数１６】
2006262256.tif 000018
従って、Ｕｉ＝ＵかつＵｉ′＝Ｕ′が成り立つｉが存在する、即ちＵ，Ｕ′を同一署名者が生成した場合は、（Ｚi，K，Ｚi，K′）（ｉ＝１，…，ｍ）の復号結果には（１，１）が存在し、そうでない場合は（１，１）が存在する確率は十分小さい事が期待出来る。また、（Ｚi，K，Ｚi，K′）（ｉ＝１，…，ｍ）は実際には同一性検証装置２００（ｊ）（ｊ＝１，…，Ｋ）により適当な順番に入れ替わっており、更にＺi，K，Ｚi，K′は１でないときはｓi，jβ（ｊ＝１，…，Ｋ）によってＧｑの１以外のランダムな値に変換されるため、（Ｚi，K，Ｚi，K′）及びそれら復号結果からＵ，Ｕ′の署名生成者を特定するための有意な情報を得る事は困難である事が期待出来る。
【００４８】
なお、図１や図３で示したシステムにおける各装置の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２や図４、図５で示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００４９】
【図１】本発明の第１の実施の形態のシステム構成例を示す図。
【図２】第１の実施の形態の処理フロー図。
【図３】本発明の第２の実施の形態のシステム構成例を示す図。
【図４】第２の実施の形態の処理フロー図。
【図５】図４の続きの処理フロー図。
【符号の説明】
【００５０】
１００  開示装置
２００  同一性検証装置
３００  ネットワーク
【図１】
2006262256.tif 000025
【図２】
2006262256.tif 000026
【図３】
2006262256.tif 000027
【図４】
2006262256.tif 000028
【図５】
2006262256.tif 000029