(57)【要約】【課題】署名の対象となるメッセージ空間のサイズに関し制約を受けることなく、情報量的安全性を保障し得る電子署名の構造を提供する。【解決手段】上記課題は、各ユーザＵｉに対応させてそれぞれ異なるように生成された乱数ｒｉと、（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の上記乱数ｒｉに対応する集合Ｆｒｉ＝｛ｌｉ１，・・・，ｌｉ｜Ｆｒｉ｜｝とメッセージ情報ｍとの認証子生成・検証アルゴリズムによる演算の値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）との組α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を有する電子署名の構造にて達成される。【選択図】　　　　図２
2004104172.tif 000002
【特許請求の範囲】
【請求項１】
所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成されたメッセージ情報ｍに対して付加されるべき電子署名の構造において、
上記各ユーザＵｉに対応させてそれぞれ異なるように生成された乱数ｒｉと、
（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の上記乱数ｒｉに対応する集合Ｆｒｉ＝｛ｌｉ１，・・・，ｌｉ｜Ｆｒｉ｜｝とメッセージ情報ｍとの認証子生成・検証アルゴリズムによる演算の値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）との組α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を有する電子署名の構造。
【請求項２】
所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された署名付き情報が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う署名付き情報検証方法において、
所定のセンタにおいて実行される、
上記各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉを生成するステップと、
上記生成した乱数ｒｉの何れかを選択するステップと、
上記各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉ´を生成するステップと、
上記生成した乱数ｒｉ´の何れかを選択するステップと、
（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝を生成するステップと、
上記選択した乱数ｒｉと、上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の上記選択した乱数ｒｉに対応する集合Ｆｒｉ＝｛ｌｉ１，・・・，ｌｉ｜Ｆｒｉ｜｝とをユーザＵｉに発行するステップと、
上記生成した乱数ｒｉと上記生成した乱数ｒｉ´との対応関係を表すマッピング情報π１を生成するステップと、
上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の集合Ｌと上記マッピング情報π１とを検証者に発行するステップと、
を有し、
上記各ユーザＵｉの端末において実行される、
上記所定のセンタにおいて発行された乱数ｒｉと集合Ｆｒｉとを取得するステップと、
上記取得した集合Ｆｒｉとメッセージ情報ｍとを用い、認証子生成・検証アルゴリズムにより値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）を演算するステップと、
上記取得した乱数ｒｉと上記値α´ｉｊとの組である電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を発行するステップと、
上記メッセージ情報ｍと上記発行した電子署名αとを上記検証者に送るステップと、
を有し、
上記検証者の端末において実行される、
上記所定のセンタにおいて発行された集合Ｌと上記マッピング情報π１とを取得するステップと、
上記ユーザＵｉの端末から送られた上記メッセージ情報ｍと上記電子署名αとを取得するステップと、
上記取得した集合Ｌと上記取得した電子署名α内の乱数ｒｉとを用いて上記集合Ｆｒｉを演算するステップと、
上記メッセージ情報ｍと上記集合Ｆｒｉを用い、全てのｊに対して認証子生成・検証アルゴリズムにより値ｆ（ｍ，ｌｉｊ）を演算するステップと、
上記値ｆ（ｍ，ｌｉｊ）が上記電子署名α内のα´ｉｊ＝ｆ（ｍ，ｌｉｊ）に一致するか否かを判定するステップと、
を有し、その判定結果を上記メッセージ情報ｍと上記電子署名αからなる署名付き情報が上記所定のグループに属するいずれかのユーザにおいて生成されたものであることの検証結果とする署名付き情報検証方法。
【請求項３】
請求項２に記載の署名付き情報検証方法において、
上記所定のセンタにおいて実行される、
上記生成した乱数ｒｉ´と上記ユーザＵｉとの対応関係を表すマッピング情報π２を生成するステップと、
上記生成したマッピング情報π２を所定の機関に発行するステップと、
を有し、
上記検証者の端末において実行される、
上記マッピング情報π１に基づいて、上記電子署名αに含まれる乱数ｒｉに対応する乱数ｒｉ´を特定し、当該特定した乱数ｒｉ´を上記所定の機関に発行するステップを有し、
上記所定の機関において実行される、
上記所定のセンタにおいて発行されたマッピング情報π２を取得するステップと、
上記検証者の端末において発行された乱数ｒｉ´を取得するステップと、
上記取得したマッピング情報π２と、上記取得した乱数ｒｉ´とに基づいて、当該乱数ｒｉ´に対応するユーザＵｉを特定するステップと、
を有する署名付き情報検証方法。
【請求項４】
所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された署名付き情報が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う署名付き情報検証システムにおいて、
所定のセンタは、
上記各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉを生成する手段と、
上記生成された乱数ｒｉの何れかを選択する手段と、
上記各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉ´を生成する手段と、
上記生成された乱数ｒｉ´の何れかを選択する手段と、
（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝を生成する手段と、
上記選択された乱数ｒｉと、上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の上記選択された乱数ｒｉに対応する集合Ｆｒｉ＝｛ｌｉ１，・・・，ｌｉ｜Ｆｒｉ｜｝とをユーザＵｉに発行する手段と、
上記された乱数ｒｉと上記生成した乱数ｒｉ´との対応関係を表すマッピング情報π１を生成する手段と、
上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の集合Ｌと上記マッピング情報π１とを検証者に発行する手段と、
を有し、
上記各ユーザＵｉの端末は、
上記所定のセンタにおいて発行された乱数ｒｉと集合Ｆｒｉとを取得する手段と、
上記取得された集合Ｆｒｉとメッセージ情報ｍとを用い、認証子生成・検証アルゴリズムにより値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）を演算する手段と、
上記取得された乱数ｒｉと上記値α´ｉｊとの組である電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を発行する手段と、
上記メッセージ情報ｍと上記発行された電子署名αとを上記検証者に送る手段と、
を有し、
上記検証者の端末は、
上記所定のセンタにおいて発行された集合Ｌと上記マッピング情報π１とを取得する手段と、
上記ユーザＵｉの端末から送られた上記メッセージ情報ｍと上記電子署名αとを取得する手段と、
上記取得された集合Ｌと上記取得された電子署名α内の乱数ｒｉとを用いて上記集合Ｆｒｉを演算する手段と、
上記メッセージ情報ｍと上記集合Ｆｒｉを用い、全てのｊに対して認証子生成・検証アルゴリズムにより値ｆ（ｍ，ｌｉｊ）を演算する手段と、
上記値ｆ（ｍ，ｌｉｊ）が上記電子署名α内のα´ｉｊ＝ｆ（ｍ，ｌｉｊ）に一致するか否かを判定する手段と、
を有し、その判定結果を上記メッセージ情報ｍと上記電子署名αからなる署名付き情報が上記所定のグループに属するいずれかのユーザにおいて生成されたものであることの検証結果とする署名付き情報検証システム。
【請求項５】
請求項４に記載の署名付き情報検証システムにおいて、
上記所定のセンタは、
上記生成された乱数ｒｉ´と上記ユーザＵｉとの対応関係を表すマッピング情報π２を生成する手段と、
上記生成されたマッピング情報π２を所定の機関に発行する手段と、
を有し、
上記検証者の端末は、
上記マッピング情報π１に基づいて、上記電子署名αに含まれる乱数ｒｉに対応する乱数ｒｉ´を特定し、当該特定した乱数ｒｉ´を上記所定の機関に発行する手段を有し、
上記所定の機関は、
上記所定のセンタにおいて発行されたマッピング情報π２を取得する手段と、
上記検証者の端末において発行された乱数ｒｉ´を取得する手段と、
上記取得されたマッピング情報π２と、上記取得された乱数ｒｉ´とに基づいて、当該乱数ｒｉ´に対応するユーザＵｉを特定する手段と、
を有する署名付き情報検証システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、電子投票や電子アンケート等において用いることのできる電子署名の構造に係り、詳しくは、所定のグループに所属する複数のユーザのそれぞれの端末において生成されたメッセージ情報ｍに対して付加されるべき電子署名の構造に関する。
【０００２】
また、本発明は、所定のグループに属する複数のユーザのそれぞれの端末において生成された署名付き情報が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う署名付き情報検証方法及びシステムに関する。
【０００３】
【従来の技術】
例えば、あるグループに所属するユーザを対象とした電子投票や電子アンケートなどを行うシステムでは、確実にそのグループに所属するユーザの投票や回答であることが保障されることや、投票や回答したユーザが特定できないこと、いわゆる、匿名性が確保されることが要求される場合がある。
【０００４】
このようなシステムでは、例えば、あるグループに所属する複数のユーザに対して共通の秘密情報を付与しておき、各ユーザはその共通の秘密情報を用いた署名付きの投票や回答を行う。そして、各ユーザの匿名性を確保した状態で、その投票や回答がそのグループに所属する正規のユーザからなされたものであることを確認することができる。
【０００５】
しかし、上述のようなシステムでは、各ユーザに対して共通の秘密情報が付与されるために、ユーザがそのグループを脱退するなど、ユーザがその秘密情報を使用する必要がなくなった状況が発生する毎に、その秘密情報を無効にしなければならない。また、グループに所属する全てのユーザに対して共通の秘密情報を付与することから、十分な安全性を確保することが比較的難しい。このような問題を解決するため、近年、グループ署名という技術が提案されている。
【０００６】
グループ署名の場合、素因数分解や離散対数問題の計算が計算量的に不可能であるということを前提とした安全性確保（計算量的に安全）の手法がとられている。即ち、現在考えられるどのような高性能のコンピュータでも、現実的な時間内で秘密情報等の解読ができないことを保障している。
【０００７】
しかし、現在、計算量的に安全であることが保障し得ていても、今後、コンピュータの性能向上などにより、その安全性を十分保障し得るものとはならない。
【０００８】
このような問題を解決するため、特願２００１−３４７９９８においては、長期的な安全性の確保に主眼をおいた、いわゆる、計算量的な安全の仮定をおかない手法が提案されている。
【０００９】
【発明が解決しようとする課題】
しかしながら、この特願２００１−３４７９９８では、有限体上の多項式を用いた手法となっており、署名の対象となるメッセージ空間の大きさがユーザの総数以上でなければならないという制約が存在する。このような制約はできるだけ少ないことが望ましい。
【００１０】
そこで、本発明の第１の課題は、署名の対象となるメッセージ空間のサイズに関し制約を受けることなく、情報量的安全性を保障し得る電子署名の構造を提供することである。
【００１１】
また、本発明の第２の課題は、メッセージ情報にそのような電子署名がなされて生成される署名付き情報の検証方法及びシステムを提供することである。
【００１２】
【課題を解決するための手段】
上記第１の課題を解決するため、本発明は請求項１に記載されるように、所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成されたメッセージ情報ｍに対して付加されるべき電子署名の構造において、上記各ユーザＵｉに対応させてそれぞれ異なるように生成された乱数ｒｉと、（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の上記乱数ｒｉに対応する集合Ｆｒｉ＝｛ｌｉ１，・・・，ｌｉ｜Ｆｒｉ｜｝とメッセージ情報ｍとの認証子生成・検証アルゴリズムによる演算の値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）との組α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を有する。
【００１３】
このような電子署名の構造では、電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝、メッセージ情報ｍ及び乱数ｒｉが悪意の第三者に取得されたとしても、全てのｊ（ｊ＝１，・・・，｜Ｆｒｉ｜）に対して生成された値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）の組み合わせは無数に存在するため、電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を構成する値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）を特定することができない。従って、悪意の第三者が所定のグループに所属するユーザに成りすますことはできない。また、（ｎ，ｔ，ｋ）−ＣｏｖｅｒＦｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝の採用により、署名の対象となるメッセージ空間の大きさがユーザの総数以上でなければならないという制約が存在しない。
【００１４】
ここで、（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝とは、元の数がｔであるような集合Ｌに対し、集合Ｆｉ（ｉ＝１，・・・，ｎ）のそれぞれは部分集合であり、且つ、｛ｉ＝１，２，・・・，ｎ｝の中から選ばれた任意の｛ｉ０，ｉ２，・・・，ｉｋ｝に対して、集合ＦｉｏがＦｉ１からＦｉｋの和集合の部分集合にはならないものをいう。なお、ＣｏｖｅｒＦｒｅｅ　Ｆａｍｉｌｙについては、「Ｐ．Ｅｒｄｏｓ，　Ｐ．Ｆｒａｎｋｉ　ａｎｄ　Ｚ．Ｆｕｒｅｄｉ著，「ａｍｉｌｉｅｓ　ｏｆ　ｆｉｎｉｔｅ　ｓｅｔｓ　ｉｎ　ｗｈｉｃｈ　ｎｏ　ｓｅｔｓ　ｉｓ　ｃｏｖｅｒｅｄ　ｂｙ　ｔｈｅ　ｕｎｉｏｎ　ｏｆ　ｔｗｏｏｔｈｅｒｓ」Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｂｉｎ．　Ｔｈｅｏｒｙ　Ｓｅｒ．　Ａ　３３．　ｐ．１５８−１６６，　１９８２」に詳細が記述されている。
【００１５】
また、上記第２の課題を解決するため、本発明は請求項２に記載されるように、所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された署名付き情報が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う署名付き情報検証方法において、所定のセンタにおいて実行される、上記各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉを生成するステップと、上記生成した乱数ｒｉの何れかを選択するステップと、上記各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉ´を生成するステップと、上記生成した乱数ｒｉ´の何れかを選択するステップと、（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝を生成するステップと、上記選択した乱数ｒｉと、上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の上記選択した乱数ｒｉに対応する集合Ｆｒｉ＝｛ｌｉ１，・・・，ｌｉ｜Ｆｒｉ｜｝とをユーザＵｉに発行するステップと、上記生成した乱数ｒｉと上記生成した乱数ｒｉ´との対応関係を表すマッピング情報π１を生成するステップと、上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の集合Ｌと上記マッピング情報π１とを検証者に発行するステップとを有し、上記各ユーザＵｉの端末において実行される、上記所定のセンタにおいて発行された乱数ｒｉと集合Ｆｒｉとを取得するステップと、上記取得した集合Ｆｒｉとメッセージ情報ｍとを用い、認証子生成・検証アルゴリズムにより値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）を演算するステップと、上記取得した乱数ｒｉと上記値α´ｉｊとの組である電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を発行するステップと、上記メッセージ情報ｍと上記発行した電子署名αとを上記検証者に送るステップとを有し、上記検証者の端末において実行される、上記所定のセンタにおいて発行された集合Ｌと上記マッピング情報π１とを取得するステップと、上記ユーザＵｉの端末から送られた上記メッセージ情報ｍと上記電子署名αとを取得するステップと、上記取得した集合Ｌと上記取得した電子署名α内の乱数ｒｉとを用いて上記集合Ｆｒｉを演算するステップと、上記メッセージ情報ｍと上記集合Ｆｒｉを用い、全てのｊに対して認証子生成・検証アルゴリズムにより値ｆ（ｍ，ｌｉｊ）を演算するステップと、上記値ｆ（ｍ，ｌｉｊ）が上記電子署名α内のα´ｉｊ＝ｆ（ｍ，ｌｉｊ）に一致するか否かを判定するステップとを有し、その判定結果を上記メッセージ情報ｍと上記電子署名αからなる署名付き情報が上記所定のグループに属するいずれかのユーザにおいて生成されたものであることの検証結果とする。
【００１６】
このような署名付き情報検証方法では、検証者は、センタから発行された上記集合Ｌ、及び、上記乱数ｒｉと上記乱数ｒｉ´との対応関係を表すマッピング情報π１と、ユーザＵｉにおいて生成されたメッセージ情報ｍ、及び、電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝とを用いて、全てのｊ（ｊ＝１，・・・，｜Ｆｒｉ｜）に対して認証子生成・検証アルゴリズムにより値ｆ（ｍ，ｌｉｊ）を生成し、その生成された値ｆ（ｍ，ｌｉｊ）と電子署名α内のα´ｉｊ＝ｆ（ｍ，ｌｉｊ）とが一致するか否かを判定することにより、メッセージ情報ｍと電子署名αからなる署名付き情報が所定のグループに属するいずれかのユーザにおいて生成されたものであることの検証を行う。
【００１７】
ユーザに対して、メッセージ情報ｍの生成否認を許さないという観点から、本発明は請求項３に記載されるように、上記署名付き情報検証方法において、上記所定のセンタにおいて実行される、上記生成した乱数ｒｉ´と上記ユーザＵｉとの対応関係を表すマッピング情報π２を生成するステップと、上記生成したマッピング情報π２を所定の機関に発行するステップとを有し、上記検証者の端末において実行される、上記マッピング情報π１に基づいて、上記電子署名αに含まれる乱数ｒｉに対応する乱数ｒｉ´を特定し、当該特定した乱数ｒｉ´を上記所定の機関に発行するステップを有し、上記所定の機関において実行される、上記所定のセンタにおいて発行されたマッピング情報π２を取得するステップと、上記検証者の端末において発行された乱数ｒｉ´を取得するステップと、上記取得したマッピング情報π２と、上記取得した乱数ｒｉ´とに基づいて、当該乱数ｒｉ´に対応するユーザＵｉを特定するステップとを有する。
【００１８】
上述の署名付き情報検証方法では、検証者が有する情報だけでは、署名付き情報を生成したのは所定のグループに所属する何れかのユーザであることは検証できるものの、ユーザの匿名性が確保されているため、具体的にその生成したユーザを特定することができない。そこで、センタは、予めユーザの乱数ｒｉとユーザＵｉとの対応関係を表すマッピング情報π２を所定の機関に発行する。これにより、検証者が乱数ｒｉ´を当該所定の機関に提供することにより、その署名付き情報を生成したユーザＵｉを特定することができる。即ち、その署名付き情報を生成したユーザＵｉを検証者と所定の機関が協力し合うことによって特定することができる。このように特定されたユーザＵｉは、その署名付き情報を生成したことを否認することができなくなる。
【００１９】
請求項２に記載された発明と同様の観点から、本発明は請求項４に記載されるように、所定のグループに属する複数のユーザのそれぞれＵｉ（ｉ＝１，・・・，ｎ）の端末において生成された署名付き情報が当該所定のグループに所属する何れかのユーザにて生成されたものであることの検証を行う署名付き情報検証システムにおいて、所定のセンタは、上記各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉを生成する手段と、上記生成された乱数ｒｉの何れかを選択する手段と、上記各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉ´を生成する手段と、上記生成された乱数ｒｉ´の何れかを選択する手段と、（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝を生成する手段と、上記選択された乱数ｒｉと、上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の上記選択された乱数ｒｉに対応する集合Ｆｒｉ＝｛ｌｉ１，・・・，ｌｉ｜Ｆｒｉ｜｝とをユーザＵｉに発行する手段と、上記された乱数ｒｉと上記生成した乱数ｒｉ´との対応関係を表すマッピング情報π１を生成する手段と、上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の集合Ｌと上記マッピング情報π１とを検証者に発行する手段とを有し、上記各ユーザＵｉの端末は、上記所定のセンタにおいて発行された乱数ｒｉと集合Ｆｒｉとを取得する手段と、上記取得された集合Ｆｒｉとメッセージ情報ｍとを用い、認証子生成・検証アルゴリズムにより値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）を演算する手段と、上記取得された乱数ｒｉと上記値α´ｉｊとの組である電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を発行する手段と、上記メッセージ情報ｍと上記発行された電子署名αとを上記検証者に送る手段とを有し、上記検証者の端末は、上記所定のセンタにおいて発行された集合Ｌと上記マッピング情報π１とを取得する手段と、上記ユーザＵｉの端末から送られた上記メッセージ情報ｍと上記電子署名αとを取得する手段と、上記取得された集合Ｌと上記取得された電子署名α内の乱数ｒｉとを用いて上記集合Ｆｒｉを演算する手段と、上記メッセージ情報ｍと上記集合Ｆｒｉを用い、全てのｊに対して認証子生成・検証アルゴリズムにより値ｆ（ｍ，ｌｉｊ）を演算する手段と、上記値ｆ（ｍ，ｌｉｊ）が上記電子署名α内のα´ｉｊ＝ｆ（ｍ，ｌｉｊ）に一致するか否かを判定する手段とを有し、その判定結果を上記メッセージ情報ｍと上記電子署名αからなる署名付き情報が上記所定のグループに属するいずれかのユーザにおいて生成されたものであることの検証結果とする。
【００２０】
請求項３に記載された発明と同様の観点から、本発明は請求項５に記載されるように、上記署名付き情報検証システムにおいて、上記所定のセンタは、上記生成された乱数ｒｉ´と上記ユーザＵｉとの対応関係を表すマッピング情報π２を生成する手段と、上記生成されたマッピング情報π２を所定の機関に発行する手段とを有し、上記検証者の端末は、上記マッピング情報π１に基づいて、上記電子署名αに含まれる乱数ｒｉに対応する乱数ｒｉ´を特定し、当該特定した乱数ｒｉ´を上記所定の機関に発行する手段を有し、上記所定の機関は、上記所定のセンタにおいて発行されたマッピング情報π２を取得する手段と、上記検証者の端末において発行された乱数ｒｉ´を取得する手段と、上記取得されたマッピング情報π２と、上記取得された乱数ｒｉ´とに基づいて、当該乱数ｒｉ´に対応するユーザＵｉを特定する手段とを有する。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態を図面に基づいて説明する。
【００２２】
本発明の実施の一形態に係る署名付き情報検証方法が適用されるシステムは、例えば、図１に示すように構成される。
【００２３】
図１において、所定のグループに所属するユーザＵｉ（ｉ＝１，・・・，ｎ）が使用すべきユーザ端末１０１〜１０ｎ、検証者Ｖ（Ｖｅｒｉｆｉｅｒ）にて管理される検証者端末２０及び信頼できる第三者（Ｔｒｕｓｔｅｄ　Ａｕｔｈｏｒｉｔｙ）が管理するセンタ１００（コンピュータ）が所定のネットワークＮＷに接続されている。また、上記所定のグループ内またはそのグループ以外のユーザで、例えば、電子投票や電子アンケートの回答を回収する者にて管理されるユーザ端末１０ｊ及び所定の機関となるエスクローエージェント（Ｅｓｃｒｏｗ　Ａｇｅｎｔ）２００（コンピュータ）がネットワークＮＷに接続されている。
【００２４】
上記のようなシステムにおいて、例えば、上記所定のグループに所属する複数のユーザＵｉが電子投票を行う場合、図２及び図３に示す手順に従って処理が行われる。
【００２５】
図２においてセンタ１００は、（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝をランダムに生成する（Ｓ１）。更にセンタ１００は、各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉ（ｉ＝１，・・・，ｎ）を生成して何れかを選択するとともに、同様に、各ユーザＵｉに対応させてそれぞれ異なる乱数ｒｉ´（ｉ＝１，・・・，ｎ）を生成して何れかを選択する（Ｓ２）。
【００２６】
次にセンタ１００は、選択した乱数ｒｉと、生成した（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の上記選択した乱数ｒｉに対応する集合Ｆｒｉ＝｛ｌｉ１，・・・，ｌｉ｜Ｆｒｉ｜｝からなる情報｛ｒｉ，Ｆｒｉ｝をユーザＵｉに送付する（Ｓ３）。
【００２７】
次にセンタ１００は、上記のように生成した乱数ｒｉと乱数ｒｉ´との対応関係を表すマッピング情報π１を生成し（Ｓ４）、上記（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝内の集合Ｌと上記マッピング情報π１からなる情報｛Ｌ，π１｝を検証者端末２０にＮＷを介して送付する（Ｓ５）。
【００２８】
その後、センタ１００は、上記のように生成した乱数ｒｉ´とユーザＵｉとの対応関係を表すマッピング情報π２を生成し（Ｓ６）、当該マッピング情報π２をエスクローエージェント２００にＮＷを介して送付する（Ｓ７）。
【００２９】
ユーザ端末１０ｉは、上記のようにセンタ１００から送付される｛ｒｉ，Ｆｒｉ｝を受領する（Ｓ８）。更にユーザＵｉが投票内容に関するメッセージをユーザ端末１０ｉに入力すると、当該ユーザ端末１０ｉは、そのメッセージをメッセージ情報ｍに変換し、そのメッセージ情報ｍと、上記受領した値Ｆｒｉとを用いて、認証子生成・検証アルゴリズムにより値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）を生成する。更にユーザ端末１０ｉは、受領した乱数ｒｉと上記値α´ｉｊとの組である電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を生成し、その電子署名αをメッセージ情報ｍに付加した署名付き情報｛ｍ，ｒｉ，α｝を生成する（Ｓ９）。
【００３０】
次にユーザ端末１０ｉは、ネットワークＮＷを介して上記のように生成した署名付き情報｛ｍ，ｒｉ，α｝を投票の回収を行うユーザが管理するユーザ端末１０ｊに送付する（Ｓ１０）。このように署名付き情報が送信されると、ユーザ端末１０ｉでの投票に関する処理が終了する。
【００３１】
ユーザ端末１０ｊは、ユーザＵｉのユーザ端末１０ｉから上記署名付き情報｛ｍ，ｒｉ，α｝を受領すると（Ｓ１１）、その署名付き情報｛ｍ，ｒｉ，α｝の検証を行う必要があるか否かを判定する（Ｓ１２）。この判定基準は任意に定めることができる。
【００３２】
上記受領した署名付き情報｛ｍ，ｒｉ，α｝の検証を行う必要がないと判定された場合（Ｓ１２でＮＯ）、その署名付き情報｛ｍ，ｒｉ，α｝に含まれるメッセージ情報ｍが投票内容として、ユーザ端末１０ｊに蓄積される。一方、上記受領した署名付き情報｛ｍ，ｒｉ，α｝の検証を行う必要がないと判定された場合（Ｓ１２でＮＯ）、ユーザ端末１０ｊは、検証の依頼とともに、上記ユーザ端末１０ｉから受領した署名付き情報｛ｍ，ｒｉ，α｝を検証者端末２０へ送付する（Ｓ１３）。
【００３３】
検証者端末２０は、センタ１００から情報｛Ｌ，π１｝を受領すると（Ｓ１５）、それを記憶装置に格納する（Ｓ１６）。更に検証者端末２０は、ユーザ端末１０ｊから検証の依頼とともに、署名付き情報｛ｍ，ｒｉ，α｝を受領すると（Ｓ１７）、その署名付き情報｛ｍ，ｒｉ，α｝内の電子署名αに含まれる値ｓ１＝｛α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を抽出する。更に検証者端末２０は、上記のようにセンタ１００から発行され、記憶装置に格納した情報｛Ｌ，π１｝と乱数ｒｉからＦｒｉを生成し、その署名付き情報｛ｍ，ｒｉ，α｝に含まれるメッセージ情報ｍを用いて、ｓ２＝｛ｆ（ｍ，ｌｉ１），・・・，ｆ（ｍ，ｌｉ｜Ｆｒｉ｜）｝を演算する（Ｓ１８）。
【００３４】
検証者端末２０は、上記のようにして得られた２つの値ｓ１とｓ２とが一致するか否かを判定する（Ｓ１９）。検証者端末２０は、乱数ｒｉ´とユーザＵｉとの対応関係を表すマッピング情報π２を保持していないので、上記２つの値ｓ１とｓ２とが一致する場合、上記署名付き情報｛ｍ，ｒｉ，α｝を生成したユーザを特定することはできないものの、上記グループに所属する正規のユーザの何れかが生成したものと判断することができる。
【００３５】
一方、上記署名付き情報｛ｍ，ｒｉ，α｝のうち、メッセージ情報ｍ、乱数ｒｉ及び電子署名αの少なくとも１つが改ざんされた場合、上記値ｓ１とｓ２は一致しなくなる。このため、当該値ｓ１とｓ２が一致しない場合、上記署名付き情報｛ｍ，ｒｉ，α｝は、何らかの改ざんがなされたものと判断することができる。
【００３６】
従って、上記値ｓ１とｓ２が一致すると判定された場合（Ｓ１９でＹＥＳ）、検証者端末２０は、当該署名付き情報｛ｍ，ｒｉ，α｝は正当であるとの検証結果を生成し（Ｓ２０）、その検証結果を検証の依頼元となるユーザ端末１０ｊに送信する（Ｓ２１）。一方、上記値ｓ１とｓ２が一致しないと判定された場合（Ｓ１９でＮＯ）、検証者端末２０は、当該署名付き情報｛ｍ，ｒｉ，α｝は不当であるとの検証結果を生成し（Ｓ２２）、その検証結果を検証の依頼元となるユーザ端末１０ｊに送信する（Ｓ２３）。
【００３７】
上記のようにして検証の依頼を行った（Ｓ１３）ユーザ端末１０ｊは、ネットワークＮＷを介して上記検証結果を受信する（Ｓ１４）。上記署名付き情報｛ｍ，ｒｉ，α｝が正当であるとの検証結果を受信した場合、ユーザ端末１０ｊは、その署名付き情報｛ｍ，ｒｉ，α｝に含まれるメッセージ情報ｍにて表される投票内容を有効票として処理する。一方、上記署名付き情報｛ｍ，ｒｉ，α｝が不当であるとの検証結果を受信した場合、ユーザ端末１０ｊは、その署名付き情報｛ｍ，ｒｉ，α｝に含まれるメッセージ情報ｍにて表される投票内容を無効票として処理する。
【００３８】
検証者端末２０は、上記署名付き情報｛ｍ，ｒｉ，α｝が正当であるとの検証結果を得た場合（Ｓ１９でＹＥＳ）、その検証結果をユーザ端末１０ｊに送信した後に（Ｓ２１）、図３に示すＳ２４において、その署名付き情報｛ｍ，ｒｉ，α｝を生成したユーザを特定すべきか否かを判定する。その判定基準は、任意に定めることができる。
【００３９】
上記署名付き情報｛ｍ，ｒｉ，α｝を生成したユーザを特定すべきと判定されると（Ｓ２４でＹＥＳ）、検証者端末２０は、マッピング情報π１に基づいて、署名付き情報｛ｍ，ｒｉ，α｝に含まれる乱数ｒｉに対応する乱数ｒｉ´を特定し、当該乱数ｒｉ´をネットワークＮＷを介してエスクローエージェント２００へ送付する（Ｓ２５）。
【００４０】
上述したように、乱数ｒｉ´とそれに対応したユーザＵｉ（ｉ＝１，・・・，ｎ）との対応関係を表すマッピング情報π２をセンタ１００から受領した（図２に示すＳ２７）エスクローエージェント２００は、図３に示すＳ２８において、検証者端末２０から送付される乱数ｒｉ´を受領する。
【００４１】
更にエスクローエージェント２００は、上記乱数ｒｉ´とユーザＵｉ（ｉ＝１，・・・，ｎ）との対応関係を表すマッピング情報π２から、検証者端末２０から受領した乱数ｒｉ´に対応するユーザＵｉを検索する（Ｓ２９）。その検索の結果、乱数ｒｉ´に対応するユーザＵｉが得られると、エスクローエージェント２００は、そのユーザを特定する識別子Ｕｉを検証者端末２０へ送付する（Ｓ３０）。検証者端末２０は、エスクローエージェント２００からユーザを特定する識別子Ｕｉを受領する（Ｓ２６）。
【００４２】
このように、署名付き情報｛ｍ，ｒｉ，α｝を生成したユーザＵｉの通知を受けた検証者端末２０は、その署名付き情報｛ｍ，ｒｉ，α｝に含まれるメッセージ情報ｍとその生成者となるユーザＵｉとの関係を管理する。これにより、何らかの理由によりメッセージ情報ｍを生成したユーザを特定する必要が生じた場合に、検証者端末２０にて管理されるメッセージ情報ｍとその生成者となるユーザとの関係を利用することが可能となる。従って、ユーザは、自らメッセージ情報ｍを生成したことの否認ができなくなる。
【００４３】
上述したようなシステムによれば、検証者は、署名付き情報｛ｍ，ｒｉ，α｝を生成した者がグループに所属するユーザの何れかであることを検証することができる。また、上記のように署名付き情報｛ｍ，ｒｉ，α｝がユーザ端末１０ｉからユーザ端末１０ｊに送付される際に、悪意の第三者によって不正に取得され、メッセージ情報ｍ、乱数ｒｉ、電子署名αの少なくとも何れかが改ざんされた場合、検証者は、その改ざんを検出することが可能となる。即ち、いかなる計算能力のコンピュータを用いても、正当な署名付き情報｛ｍ，ｒｉ，α｝をその正当性を保持しつつ改ざんすることはできない。
【００４４】
更に、悪意の第三者が上記メッセージ情報ｍ、乱数ｒｉ、電子署名αを不正に取得しても、電子署名α＝｛ｒｉ，α´ｉ１，・・・，α´ｉ｜Ｆｒｉ｜｝を定めるそれぞれの値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）（ｊ＝１，・・・，｜Ｆｒｉ｜）は無数に存在するので、いかなる計算能力のコンピュータを用いても、その各値α´ｉｊ＝ｆ（ｍ，ｌｉｊ）を特定することができず、不正者が正規ユーザに成りすますことはできない。
【００４５】
また、上記署名付き情報｛ｍ，ｒｉ，α｝に含まれる情報からだけでは、どのような計算能力を有するコンピュータを用いても、その署名付き情報｛ｍ，ｒｉ，α｝を生成したユーザを特定することができない。また、検証者端末２０においても、単独では、その署名付き情報｛ｍ，ｒｉ，α｝を生成したユーザを特定することができない。
【００４６】
一方で、検証者端末２０とエスクローエージェント２００とが協働する場合に限って、署名付き情報｛ｍ，ｒｉ，α｝を生成したユーザを特定することができる。このため、グループに所属するいかなる正規ユーザも生成者が不明であるような署名付き情報｛ｍ，ｒｉ，α｝を生成することができない。
【００４７】
更に、電子署名αの生成に際し、（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝を採用することにより、署名の対象となるメッセージ空間のサイズに関する制約をなくすことができる。
【発明の効果】
以上、説明したように、請求項１記載の本願発明によれば、署名付き情報に含まれる複数の情報のいずれかでも改ざんすれば、その改ざんを検出することができ、また、他人が知り得る情報から電子署名αの構造の要素α´ｉｊ＝ｆ（ｍ，ｌｉｊ）を論理的に再現することはできない。従って、いかなる性能のコンピュータを用いても不正を行うことができないという、いわゆる情報量的安全性を保障しうるグループ署名の構造を実現することができる。また、電子署名αの生成に際し、（ｎ，ｔ，ｋ）−Ｃｏｖｅｒ　Ｆｒｅｅ　Ｆａｍｉｌｙ｛Ｌ，Ｆ１，…，Ｆｎ｝を採用することにより、署名の対象となるメッセージ空間のサイズに関する制約をなくすことができる。
【００４８】
また、請求項２乃至５記載の発明によれば、メッセージ情報に上記のような電子署名（グループ署名）が付加されることにより生成された署名付き情報の検証方法及びシステムを実現することができる。
【図面の簡単な説明】
【図１】本発明の実施の一形態に係る署名付き情報検証方法が適用されるシステムの構成例を示す図である。
【図２】図１に示すシステムでの処理の流れの第１の例を示すシーケンス図である。
【図３】図２に示す処理の流れに続く処理の流れを示すシーケンス図である。
【符号の説明】
１０ｉ、１０ｊ、１０１〜１０ｎ　ユーザ端末
２０　検証者端末
１００　センタ
２００　エスクローエージェント
【図１】
2004104172.tif 000003
【図２】
2004104172.tif 000004
【図３】
2004104172.tif 000005