(57)【要約】  属性を取り扱い、なおかつ属性を公開情報にしないようにでき、効率がよく、データベースを必要としない情報通信システム等を提供できるようにしなければならない。  仮名とタグの生成手段はユーザ装置の秘密鍵のコミットメントを含むタグと仮名を出力し、所属証明書生成手段はタグと仮名に対する署名文を所属証明書として出力し、所属証明書所有証明手段は署名文をユーザ装置が検証者装置に送信し、タグが秘密鍵のコミットメントの証明をユーザ装置が検証者装置にし、所属証明書所有検証手段は署名文を検証者装置が検証し、タグが秘密鍵のコミットメントの証明を検証者装置が検証する。
2009066557.tif 000002
【特許請求の範囲】
【請求項１】
オーガニゼーション装置とユーザ装置と検証者装置からなる情報通信システムで、
ユーザ装置には自身の秘密鍵があり、
仮名とタグを生成する手段と、
仮名とタグが前記オーガニゼーション装置から発行された事を証明する所属証明書を生成する手段と、
所属証明書の所有を証明する手段と、
所属証明書の所有を検証する手段と、
をもつものであって、
仮名とタグを生成する前記手段では前記ユーザ装置の秘密鍵のコミットメントを含むタグと仮名を出力し、
所属証明書を生成する前記手段では前記タグと前記仮名に対する署名文を所属証明書として出力し、
所属証明書の所有を証明する前記手段では前記署名文をユーザ装置が前記検証者装置に送信し、
前記タグが前記秘密鍵のコミットメントである事を前記ユーザ装置が前記検証者装置に証明し、
所属証明書の所有を検証する前記手段では前記署名文を前記検証者装置が検証し、
さらに前記タグが前記秘密鍵のコミットメントである事の証明を前記検証者装置が検証する事を特徴とする情報通信システム。
【請求項２】
さらにユーザ装置が２つ以上のオーガニゼーション装置から仮名とタグを発行してもらった際にそれら２つのタグが同じユーザ装置のものである事を示す為のタグ関連性証明の手段と、
前記タグ関連性証明を検証する手段とを持ち、
前記タグ関連性証明では２つのタグが同じ秘密鍵を用いて生成されている事を前記ユーザ装置が証明し、
前記タグ関連性検証では２つのタグが同じ秘密鍵を用いて生成されている事の証明を前記検証者装置が検証する事を特徴とする請求項１に記載の情報通信システム。
【請求項３】
仮名とタグを生成する前記手段ではさらに前記タグが秘密鍵のコミットメントを含むものである事を前記ユーザ装置が前記オーガニゼーション装置に証明し、
さらに前記タグが秘密鍵のコミットメントを含むものである事の証明を前記オーガニゼーション装置が検証する事を特徴とする請求項１または２に記載の情報通信システム。
【請求項４】
前記秘密鍵xのコミットメントCが、公開情報KとＬとを使い、ランダムに選んだRでＣ＝K^xL^Rにより作成される事を特徴とする請求項１から３のいずれか１項に記載の情報通信システム。
【請求項５】
さらに属性を証明する手段と属性の証明を検証する手段とを持ち、
仮名とタグを生成する前記手段では前記ユーザ装置がさらに仮名に関する属性のコミットメントを作成し、
さらに前記秘密鍵のコミットメントと前記属性のコミットメントを含むものをタグとし、
属性を証明する前記手段では前記署名文を前記ユーザ装置が前記検証者装置に送信し、
前記タグが秘密鍵のコミットメントである事を前記ユーザ装置が前記検証者装置に証明し、
属性の証明を検証する前記手段では前記署名文を前記検証者装置が検証し、
さらに前記タグが秘密鍵のコミットメントである事の証明を前記検証者装置が検証する事を特徴とする請求項１または２に記載の情報通信システム。
【請求項６】
仮名とタグを生成する前記手段ではさらに前記タグが秘密鍵のコミットメント及び属性のコミットメントを含むものである事を前記ユーザ装置が前記オーガニゼーション装置に証明し、
さらに前記タグが秘密鍵のコミットメント及び属性のコミットメントを含むものである事の証明を前記オーガニゼーション装置が検証する事を特徴とする請求項５記載の情報通信システム。
【請求項７】
前記秘密鍵xのコミットメントCが、公開情報KとＬとを使い、ランダムに選んだRでＣ＝K^xL^Rにより作成され、
前記属性のi番目のものW_iのコミットメントC_iが、公開情報K_iとＬ_iとを使い、ランダムに選んだR_iでＣ＝K^[W_i]L^[R_i]により作成される事を特徴とする請求項５または６に記載の情報通信システム。
【請求項８】
請求項１から７のいずれか１項に記載された情報通信システムのオーガニゼーション装置。
【請求項９】
請求項１から７のいずれか１項に記載された情報通信システムのユーザ装置。
【請求項１０】
オーガニゼーション装置とユーザ装置と検証者装置からなる情報通信システムで、
ユーザ装置には自身の秘密鍵があり、
仮名とタグを生成する手段と、
仮名が前記オーガニゼーション装置から発行された事を証明する所属証明書を生成する手段と、
所属証明書の所有を証明する手段と、
所属証明書の所有を検証する手段と、
をもつものであって、
仮名とタグを生成する前記手段では何からのビット列を仮名にし、
さらに前記ユーザ装置が自身の秘密鍵のコミットメントを含むものをタグとし、
所属証明書を生成する前記手段では前記タグに対する源署名文を汎用指定検証者署名方式の源署名生成手段に従って作成し、
さらに前記源署名文を所属証明書として出力し、
所属証明書の所有を証明する前記手段では前記源署名文を見せずに前記源署名文の知識を証明し、
所属証明書の所有を検証する前記手段では前記源署名文を見せずに前記源署名文の知識を検証する事を特徴とする情報通信システム。
【請求項１１】
所属証明書の所有を証明する前記手段では前記源署名文から前記汎用指定検証者署名方式の指定検証者署名生成手段に従って指定検証者署名を生成し、
さらに前記指定検証者署名を検証者装置に送信し、
さらに前記タグが秘密鍵のコミットメントであることを前記ユーザ装置が検証者装置に証明し、
所属証明書の所有を検証する前記手段では前記指定検証者署名文を前記検証者装置が検証し、
さらに前記タグが秘密鍵のコミットメントである事の証明を検証する事を特徴とする請求項１０に記載の情報通信システム。
【請求項１２】
さらにユーザ装置が２つ以上のオーガニゼーション装置から仮名とタグを発行してもらった際にそれら２つのタグが同じユーザ装置のものである事を示す為のタグ関連性証明の手段を持ち、
さらにタグ関連性証明を検証する手段を持ち、
タグ関連性証明の手段では前記タグ関連性証明では２つのタグが同じ秘密鍵を用いて生成されている事をユーザ装置が検証者装置に証明し、
タグ関連性証明を検証する手段では前記タグ関連性証明では２つのタグが同じ秘密鍵を用いて生成されている事の証明を検証者装置が検証する事を特徴とする請求項１０または１１に記載の情報通信システム。
【請求項１３】
仮名とタグを生成する前記手段ではさらに前記タグが秘密鍵のコミットメントを含むものである事を前記ユーザ装置が前記オーガニゼーション装置に証明し、
さらに前記タグが秘密鍵のコミットメントを含むものである事の証明を前記オーガニゼーション装置が検証する事を特徴とする請求項１０から１２のいずれか１項に記載の情報通信システム。
【請求項１４】
前記秘密鍵xの前記コミットメントCが、公開情報KとＬとを使い、ランダムに選んだRでＣ＝K^xL^Rにより作成される事を特徴とする請求項１０から１３のいずれか１項に記載の情報通信システム。
【請求項１５】
さらに属性を証明する手段と属性の証明を検証する手段とを持ち、
仮名を生成する前記手段では前記ユーザ装置がさらに仮名に関する属性のコミットメントを作成し、
さらに前記秘密鍵のコミットメントと前記属性のコミットメントを含むものをタグとし、
属性を証明する前記手段では前記証明文を前記ユーザ装置が前記検証者装置に送信し、
さらに前記属性に対するタグに含まれるコミットメントが属性のコミットメントを含むものである事を前記ユーザ装置が前記検証者装置に証明し、
属性の証明を検証する前記手段では前記署名文を前記検証者装置が検証し、
さらに前記属性に対するタグに含まれるコミットメントが属性のコミットメントを含むものである事の証明を前記検証者装置が検証する事を特徴とする請求項１０から１２のいずれか１項に記載の情報通信システム。
【請求項１６】
仮名とタグを生成する前記手段ではさらに前記タグが秘密鍵のコミットメント及び属性のコミットメントを含むものである事を前記ユーザ装置が前記オーガニゼーション装置に証明し、
さらに前記タグが秘密鍵のコミットメント及び属性のコミットメントを含むものである事の証明を前記オーガニゼーション装置が検証する事を特徴とする請求項１５記載の情報通信システム。
【請求項１７】
前記属性のi番目のものW_iのコミットメントC_iが、公開情報K_iとＬ_iとを使い、ランダムに選んだR_iでＣ＝K^[W_i]L^[R_i]により作成され、
前記秘密鍵xの前記コミットメントCが、公開情報KとＬとを使い、ランダムに選んだRでＣ＝K^xL^Rにより作成される事を特徴とする請求項１５または１６に記載の情報通信システム。
【請求項１８】
請求項１０から１７のいずれか１項に記載の情報通信システムのオーガニゼーション装置。
【請求項１９】
請求項１０から１７のいずれか１項に記載の情報通信システムのユーザ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、効率的なアノニマス・クレデンシャル技術に関するものである。
【背景技術】
【０００２】
[アノニマス・クレデンシャル]
アノニマス・クレデンシャル方式は仮名で認証を受ける技術である。
様々なバージョンがあるが、ここでは非特許文献１のものを図１に従って紹介する。【０００３】
非特許文献１のアノニマス・クレデンシャル方式にはオーガニゼーション、ユーザ、検証者、データベース公開者の４種類のエンティティがいる。オーガニゼーションはユーザのグループを運営している。【０００４】
ユーザ、オーガニゼーション、検証者、およびデータベース管理者は計算機（例えばパーソナル・コンピュータ）を持っているものとする。【０００５】
オーガニゼーション、ユーザ、検証者、およびデータベース管理者が所有している計算機をそれぞれオーガニゼーション装置１、ユーザ装置２、検証者装置３、データベース管理者装置４という。【０００６】
オーガニゼーション装置１は演算部１７、記憶部１８、および通信部１９を持つ。同様にユーザ装置２は演算部２７、記憶部２８、および通信部２９を持つ。同様に検証者装置３は演算部３７、記憶部３８、および通信部３９を持つ。【０００７】
またデータベース管理者装置は通信部４９とデータベース４１０を持つ。これらの装置の演算部、記憶部、通信部はそれぞれ例えばＣＰＵ、ハードディスク、およびインターネット用のポートが使えるが、どのようなものを用いてもよい。装置同士はなんらかの通信回線を経由して通信できる。通信回線としては例えばインターネットがあるが、どのようなものを用いてもよい。【０００８】
また、各オーガニゼーション装置１は自身の公開鍵を公開する何らかの方法があるとする。例えばＰＫＩの仕組みを用いる事で、オーガニゼーション装置１は公開鍵を公開できる。【０００９】
アノニマス・クレデンシャルでは仮名(pseudonym)、タグ(Validation Tag)、所属証明書(Credential)というデータを扱う。仮名はユーザがグループに加入する際ユーザに割り振られるものである。【００１０】
所属証明書は、仮名を持ったユーザが確かにそのグループに属している事を証明する証明書である。【００１１】
アノニマス・クレデンシャル System は以下のプロシージャを持つ。
１．オーガニゼーション鍵生成１１
２．ユーザ秘密鍵生成２１
３．仮名生成（１２と２２）
４．所属証明書生成（１３と２３）
５．所属証明書所有証明２４と所属証明書所有検証３４
６．タグ関連性証明２６とタグ関連性検証３６【００１２】
非特許文献１では、１．３．４．５．６．をそれぞれ「System Parameter and Key Generation」、「Generation of Pseudonym」、「Generation of a Credential」、「Showing a Single Credential」、「Showing Credential with Respect to a Pseudonym」と呼んでいる。【００１３】
オーガニゼーション鍵生成１１はオーガニゼーション装置の公開鍵と秘密鍵を生成するアルゴリズムで、各オーガニゼーションがグループを解説する際に実行する。【００１４】
仮名生成（１２と２２）はユーザのいずれかのグループに新しく所属する際に行うプロトコルで、グループを管理するオーガニゼーションとユーザとの間で行われる。プロトコルが正常に終了すると、ユーザのこのグループにおける仮名とタグが生成される。【００１５】
安全性の観点から言えば仮名生成の際の通信は盗聴できないようにしたほうがよい。例えば通信内容を暗号化する事で盗聴を防ぐ事ができる。【００１６】
所属証明書生成（１３と２３）は、ユーザのタグの正当性を証明する証明文である所属証明書を生成するプロトコルであり、ユーザとオーガニゼーションの間で行われる。【００１７】
所属証明書所有証明２４はユーザがグループに所属している事を検証者に証明する手順で、所属証明書所有検証３４は検証者がその証明を検証する手順である。【００１８】
タグ関連性証明２６はユーザが２つのグループに属している際、双方のグループで使っているタグが同一人物のものである事を検証者に証明する手順で、タグ関連性検証３６は検証者がその証明を検証する手順である。【００１９】
データベース公開者はユーザのデータベースを公開している。ユーザが仮名生成（１２と２２）を行うたびにデータベース管理者はユーザの仮名とタグとのペアをデータベースに追加する。またデータベース管理者はユーザが所属証明書生成（１３と２３）をするたびに、所属証明書の情報を追加する。【００２０】
（準備）
[汎用指定検証者署名方式]
汎用指定検証者署名方式(Universal Designated-Verifier Signature Scheme)は非特許文献２で提案された方式である。
また汎用指定検証者署名方式には、公開情報生成、署名者鍵生成、検証者鍵生成、源署名生成、検証、指定検証者署名生成、検証者指定検証の７つのアルゴリズムがある。【００２１】
公開情報生成はセキュリティ・パラメータλを入力として受け取り、公開情報paramを出力する。
署名鍵生成は公開情報paramを入力として受け取り、署名者の公開鍵spkと署名者の秘密鍵sskを出力する。
検証者鍵生成は公開情報paramを入力として受け取り、検証者の公開鍵vpkと検証者の秘密鍵vskを出力する。
源署名生成は公開情報paramと署名者の秘密鍵sskとメッセージMとを入力として受け取り、源署名文Sを出力する。
検証は公開情報paramと署名者の公開鍵spkとメッセージMと源署名文Sとを入力として受け取り、「受理」もしくは「拒否」を出力する。【００２２】
指定検証者署名生成は公開情報paramと署名者の公開鍵spkと検証者の公開鍵vpkとメッセージとM署名文Sとを入力として受け取り、指定検証者署名文σを出力する。
検証者指定検証は公開情報paramと署名者の公開鍵spkと検証者の公開鍵vpkとメッセージMと指定検証者署名文σとを入力として受け取り、「受理」もしくは「拒否」を出力する。【００２３】
非特許文献２では、以下のような汎用指定検証者署名方式が提案されている。
群G_1、G_2、G_Tをλビットの位数を持ち、ペアリング<・、・> : G_1×G_2→G_Tと写像ψ:G_2→G_1を持つものとする。
qをG_1の位数（＝G_2の位数＝G_Tの位数）し、HをG_2に値を取るハッシュ関数とする。
公開情報生成はG_1の元g_1をランダムに選び、g_2=ψ(g_1)とし、param=(g_1、g_2)を出力する。【００２４】
署名鍵生成はparam=(g_1、g_2)を入力として受け取り、Z_qの元sskをランダムに選び、spk=g_1^[ssk]を計算し、spk、sskをそれぞれ公開鍵、秘密鍵として出力する。
検証者鍵生成はparam=(g_1、g_2)を入力として受け取り、Z_qの元vskをランダムに選び、vpk=g_1^[vsk]を計算し、vpk、vskをそれぞれ公開鍵、秘密鍵として出力する。
源署名生成は署名者の秘密鍵sskとメッセージMとを入力として受け取り、S=H(M)^[ssk]を計算し、Sを源署名文として出力する。
検証は署名者の公開鍵spkとメッセージMと源署名文σとを入力として受け取り、<g_1、S>=<spk、H(M)>なら「受理」を、そうでなければ「拒否」を出力する。【００２５】
指定検証者署名生成は署名者の公開鍵spkと検証者の公開鍵vpkとメッセージと署名文Sとを入力として受け取り、σ=<vpk、S>を出力する。
検証者指定検証は署名者の公開鍵spkと検証者の公開鍵vpkとメッセージと指定検証者署名文σとを入力として受け取りσ=<spk^[vsk]、H(M)>なら「受理」をそうでなければ「拒否」を出力する。【００２６】
ここで、証明書発行装置において、公開鍵記憶手段は、対象ユーザの公開鍵を記憶し、秘密鍵記憶手段は、上記公開鍵に対応した秘密鍵を記憶し、属性情報公開手段は、対象ユーザの属性情報に対応した属性識別子を公開し、ユーザ値生成手段は、対象ユーザの固有の値を生成し、証明書発行手段は、上記秘密鍵、上記対象ユーザの固有の値及び上記属性識別子に基づいた秘密情報を含む証明書を、対象ユーザへ発行することで、複数のユーザ間で属性情報を公平に公開できるように構成して、それぞれのユーザが安心して通信することができる技術が提案されている（例えば、特許文献１参照）。
【特許文献１】特開２００１−２０９３１３号公報
【非特許文献１】Jan Camenisch、 Anna Lysyanskaya。 An Efficient System for N    on-transferable アノニマス・クレデンシャルs with Optional Anonymity Revocati    on. EUROCRYPT 2001. pp. 93-118.
【非特許文献２】Ron Steinfeld、 Laurence Bull、 Huaxiong Wang、 Josef Pieprz    yk: Universal Designated-Verifier Signatures. ASIACRYPT 2003. pp. 523-542
【発明の開示】
【発明が解決しようとする課題】
【００２７】
しかしながら、上述の関連技術では、年齢、性別、嗜好といったユーザの属性を公開情報にしないように取り扱う事ができるようにする事が課題である。【００２８】
非特許文献１の方式でも仮名の自由記述部に属性を書き込めば属性を取り扱う事ができるが、自由記述部の情報は公開情報なので、属性の秘密を保つ事ができない。また非特許文献１の方式の効率の悪さを改善する事も課題である。【００２９】
また非特許文献１の方式はオーガニゼーション、ユーザ、および検証者以外にデータベースを別個に作らねばならない。【００３０】
本発明は、以上のような課題を解決するためになされたもので、属性を取り扱い、なおかつ属性を公開情報にしないようにでき、効率がよく、データベースを必要としない情報通信システム、オーガニゼーション装置およびユーザ装置を提供することを目的とする。
【課題を解決するための手段】
【００３１】
かかる目的を達成するために、本発明は、以下の特徴を有することとする。【００３２】
本発明の第１の情報通信システムは、オーガニゼーション装置とユーザ装置と検証者装置からなる情報通信システムで、
ユーザ装置には自身の秘密鍵があり、
仮名とタグを生成する手段と、
仮名とタグが前記オーガニゼーション装置から発行された事を証明する所属証明書を生成する手段と、
所属証明書の所有を証明する手段と、
所属証明書の所有を検証する手段と、
をもつものであって、
仮名とタグを生成する前記手段では前記ユーザ装置の秘密鍵のコミットメントをふくむタグと仮名を出力し、
所属証明書を生成する前記手段では前記タグと前記仮名に対する署名文を所属証明書として出力し、
所属証明書の所有を証明する前記手段では前記署名文をユーザ装置が前記検証者装置に送信し、
前記タグが前記秘密鍵のコミットメントである事を前記ユーザ装置が前記検証者装置に証明し、
所属証明書の所有を検証する前記手段では前記署名文を前記検証者装置が検証し、
さらに前記タグが前記秘密鍵のコミットメントである事の証明を前記検証者装置が検証する事を特徴とする。【００３３】
また、本発明の第２の情報通信システムは、オーガニゼーション装置とユーザ装置と検証者装置からなる情報通信システムで、
ユーザ装置には自身の秘密鍵があり、
仮名とタグを生成する手段と、
仮名が前記オーガニゼーション装置から発行された事を証明する所属証明書を生成する手段と、
所属証明書の所有を証明する手段と、
所属証明書の所有を検証する手段と、
をもつものであって、
仮名とタグを生成する前記手段では何からのビット列を仮名にし、
さらに前記ユーザ装置が自身の秘密鍵のコミットメントを含むものをタグとし、
所属証明書を生成する前記手段では前記タグに対する源署名文を汎用指定検証者署名方式の源署名生成手段に従って作成し、
さらに前記源署名文を所属証明書として出力し、
所属証明書の所有を証明する前記手段では前記源署名文を見せずに前記源署名文の知識を証明し、
所属証明書の所有を検証する前記手段では前記源署名文を見せずに前記源署名文の知識を検証する事を特徴とする。
【発明の効果】
【００３４】
本発明によれば、属性を取り扱い、なおかつ属性を公開情報にしないようにでき、効率がよく、データベースを必要としない情報通信システム、オーガニゼーション装置およびユーザ装置を提供することができる。
【発明を実施するための最良の形態】
【００３５】
[装置構成とプロシージャ] 
本発明の装置構成は非特許文献１のそれに似ているがデータベース管理者が存在しない。
本発明にはユーザ、オーガニゼーション、検証者の３種類のエンティティが参加する。
ユーザ、オーガニゼーション、および検証者は計算機（例えばパーソナル・コンピュータ）を持っているものとする。【００３６】
本発明は、例えば、図２に示すような情報通信システムに適用される。この情報通信システムは、上記図２に示すように、ユーザ装置２と、オーガニゼーション装置１と、検証者装置３とから構成されている。
ユーザ、オーガニゼーションが所有している計算機をそれぞれユーザ装置２、オーガニゼーション装置１、検証者装置３という。これらの装置は演算部、記憶部、および通信部を持っている。演算部、記憶部、通信部はそれぞれ例えばＣＰＵ、ハードディスク、およびインターネット用のポートが使えるが、どのようなものを用いてもよい。【００３７】
装置同士はなんらかの通信回線を経由して通信できる。通信回線としては例えばインターネットがあるが、どのようなものを用いてもよい。【００３８】
また、各オーガニゼーション装置１が自身の公開鍵を公開する何らかの方法があるとする。例えばＰＫＩの仕組みを用いる事で、オーガニゼーション装置１は公開鍵を公開できる。【００３９】
本発明のプロシージャは非特許文献１のそれに似ているが、新たに属性証明２５と属性検証３５というプロシージャが加わる。
本発明には以下のプロシージャがある。
１．オーガニゼーション鍵生成１１
２．ユーザ秘密鍵生成２１
３．仮名生成（１２と２２）
４．所属証明書生成（１３と２３）
５．所属証明書所有証明２４と所属証明書所有検証３４
６．属性証明２５と属性検証３５
７．タグ関連性証明２６とタグ関連性検証３６
属性証明２５と属性検証３５以外のプロシージャの役割は非特許文献１のそれと同じである。【００４０】
（第一の実施の形態）
Σ=(Gen、Sig、Ver)を署名方式とする。
ここでGenはΣの鍵生成アルゴリズム、Sigは署名アルゴリズム、Verは検証アルゴリズム。さらにGを素数位数の巡回群でG上の離散対数問題が困難なものとし、qをGの位数とする。さらにHをハッシュ関数とし、λをセキュリティ・パラメータとする。【００４１】
＜オーガニゼーション鍵生成１１＞
オーガニゼーション装置１であるOは以下のようにしてオーガニゼーション鍵生成１１を行う。
１．λを記憶部から読み込む。
２．Gen(λ)を実行し、Genの出力として署名用の公開鍵spkと署名用の秘密鍵sskを得る。
３．自然数mを選び、Gの元K_[O0]、L_[O0]、…、K_[Om]、L_[Om]をランダムに選ぶ。
４．(spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])を公開鍵とし、sskを秘密鍵とする。
５．公開鍵(spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])と秘密鍵sskとを記憶部に書き込む。
６．公開鍵(spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])を公開する。【００４２】
＜ユーザ秘密鍵生成２１＞
ユーザ装置２であるUは以下のようにしてユーザ秘密鍵生成２１を行う。
１．Gの元x_Uをランダムに選ぶ。
２．x_Uを記憶部に書き込む。【００４３】
＜仮名生成（１２と２２）＞
W_[N1]、…、W_[Nm]をユーザの属性とする。
ユーザ装置２であるUとオーガニゼーション Oは以下のようにして仮名生成（１２と２２）を行う。
１．OはメッセージN_2を選び、通信回線を使ってUに送る。
２．UはメッセージN_1をえらび、仮名NをN=N_1||N_2とする。
３．UはGの元R_[N0]、…、R_[Nm]をランダムに選ぶ。
４．UはQ_[N0]=K_[O0]^[x_U]L_[O0]^[R_[N0]]を計算し、Q_[N0]の正当性を証明する。そしてＯはその証明を検証する。
５．UはQ_[N1]=K_[O1]^[H(W_1)]L_[O1]^[R_[N1]]、…、
Q_[Nm]=K_[Om]^[H(W_m)]L_[Om]^[R_[Nm]]を計算する。
６．Uは(Q_[N0]、 Q_[N1]、…、 Q_[Nm])を通信回線を使ってOに送り、Q_[N0]、 Q_[N1]、…、 Q_[Nm]の正当性を証明する。 そしてＯはその証明を検証する。
７．Uは仮名Nとタグ(Q_[N0]、 Q_[N1]、…、 Q_[Nm])、W_[N1]、…、W_[Nm]、R_[N0]、…、R_[Nm])を記憶部に保管する。【００４４】
Uはどのような方法でx_U、R_[N0]の知識を証明してもよいが、例えば以下の方法で証明できる。
１．ＯはZ_qの元c、rをランダムに選んでC=K_[O0]^[c] L_[O0]^rを計算し、CをUに送信する。
２．UはZ_qの元x'、R'をランダムに選んでQ'=K_[O0]^[x']L_[O0]^[R']を計算し、Q'をＯに送信する。
３．Ｏはc、rをUに送信する。
４．UはC=K_[O0]^[c] L_[O0]^rが成立するかどうかを確認する。 もしC=K_[O0]^[c] L_[O0]^rがしなければUは証明を終了する。
５．Uはρ_x=cx_U+x' mod q、ρ_R=cR_[N0]+R' mod qを計算し、ρ_x、ρ_RをＯに送信する。
６．ＯはQ_[N0]^cQ'=K_[O0]^[ρ_x]L_[O0]^[ρ_R]が成立するかどうかを確認し、もし成立すれば証明を受理し、そうでなければ棄却する。【００４５】
Uはどのような方法でR_[Ni]の知識を証明してもよいが、例えば以下の方法で証明できる。
１．ＯはZ_qの元c、rをランダムに選んでC=K_[Oi]^[c] L_[Oi]^rを計算し、CをUに送信する。
２．UはZ_qの元R'をランダムに選んでQ'= L_[Oi]^[R']を計算し、Q'をＯに送信する。
３．Ｏはc、rをUに送信する。
４．UはC=K_[Oi]^[c] L_[Oi]^rが成立するかどうかを確認する。もしC=K_[Oi]^[c] L_[Oi]^rがしなければUは証明を終了する。
５．Uはρ_R=cR_[Ni]+R' mod qを計算し、ρ_RをＯに送信する。
６．Ｏは(Q_[Ni]/K_[Oi]^[H(W_i)])^cQ'= L_[Oi]^[ρ_R]が成立するかどうかを確認し、もし成立すれば証明を受理し、そうでなければ棄却する。【００４６】
＜所属証明書生成（１３と２３）＞
ユーザ装置２であるUとオーガニゼーション Oは以下のようにして所属証明書生成（１３と２３）を行う。
１．Uは記憶部から(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を読み込み、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を通信回線を使ってOに送る。
２．Oはsskを記憶部から読み込み、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])に対する署名S_N=Sig_[ssk](N、Q_[N0]、Q_[N1]、…、 Q_[Nm])を計算し、S_NをUに送信する。
３．UはVer_[spk]((N、Q_[N0]、Q_[N1]、…、 Q_[Nm])、S_N)を実行し、Ver_[spk]がが受理を出力したらS_Nを所属証明書として記憶部に書き込む。 そうでなければ所属証明書生成（１３と２３）は失敗に終わる。【００４７】
＜所属証明書所有証明２４と所属証明書所有検証３４＞
Nを、オーガニゼーション Oが管理するグループにおけるユーザ装置２であるUの仮名とする。
UがNに対する所属証明書の所有を検証者装置３であるVに証明するには、以下のようにする。
１．Uはオーガニゼーション Oの公開鍵K_[O0]、L_[O0]と(N、Q_[N0]、 x_U、R_[N0]、S_N)を記憶部から読み込む。
２．Vはオーガニゼーション Oの公開鍵spk、K_[O0]、L_[O0]、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を記憶部から読み込む。
３．UはNとS_Nを通信回線を使ってVに送信する。
４．VはVer_[spk]((N、Q_[N0]、Q_[N1]、…、 Q_[Nm])、S_N)を実行し、Verが拒否を出力したらVはUの証明を拒否する。
５．UはQ_[N0]=K_[O0]^[x_U]L_[O0]^[R_[N0]]を満たすx_U、R_[N0]の知識をVに証明し、Vはその証明を検証する。【００４８】
Uはどのような方法でx_U、R_[N0]の知識を証明してもよいが、例えば仮名生成（１２と２２）の所で説明した方法で証明できる。【００４９】
＜属性証明２５と属性検証３５＞
Nを、オーガニゼーション Oが管理するグループにおけるユーザ装置２であるUの仮名とする。
UがNに対するi番目の属性W_iを検証者装置３であるVに証明するには以下のようにする。
１．UはK_[Oi]、L_[Oi]、W_i、R_[Ni]を記憶部から読み込む。
２．VはK_[Oi]、L_[Oi]、W_iを記憶部から読み込む。
３．UはVにQ_[Ni]/K_[Oi]^[H(W_i)]= L_[Oi]^[R_[Ni]]を満たすR_[Ni]の知識を証明し、Ｖはその証明を検証する。【００５０】
Uはどのような方法でR_[Ni]の知識を証明してもよいが、例えば仮名生成（１２と２２）の所で説明した方法で証明できる。【００５１】
＜タグ関連性証明２６とタグ関連性検証３６＞
O_1、O_2をオーガニゼーション装置１とする。 O_1とO_2は同じオーガニゼーションでもよい。【００５２】
(spk、 K_[O_10]、L_[O_10]、…、K_[O_1m]、L_[O_1m])、(spk、K_[O_20]、L_[O_20]、…、K_[O_2m]、L_[O_2m])をそれぞれO_1、O_2の公開鍵とする。
さらにユーザ装置２であるUがO_1の管理するグループにおける仮名N_1とN_1に対するタグ(Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m]、W_[N_11]、…、W_[N_1m]、R_[N_10]、…、R_[N_1m]、S_M[N_1])と仮名N_2とN_2に対するタグ(Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m]、W_[N_21]、…、W_[N_2m]、R_[N_20]、…、R_[N_2m]、S_[N_2])を記憶部に保管していたとする。【００５３】
Uが別の検証者装置３であるVに対して所属証明書関連性証明を行うには、以下のようにする。
１．UはK_[O_10]、L_[O_10]、x_U、(N_1、Q_[N_10]、R_[N_10]、S_[N_1])、(N_2、Q_[N_20]、 R_[N_20]、S_[N_2])を記憶部から読み込む。
２．Vはspk、K_[O_10]、L_[O_10]、 (N_1、 Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m])、(N_2、 Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m])を記憶部から読み込む。
３．UはS_[N_1]、S_[N_2]を通信装置を使ってVに送信する。
４．VはVer_[spk]((N_1、Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m])、S_[N_1])、Ver_[spk]((N_12 Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m])、S_[N_2])の少なくとも一方が拒否なら、Uの証明を拒否する。
５．UはQ_[N_10]=K_[O_10]^[x_U] L_[O_10]^[R_[N_10]]とQ_[N_20]=K_[O_10]^[x_U] L_[O_20]^[R_[N_20]]を満たす(x_U、 R_[N_10]、 R_[N_20])の知識をVに証明し、Ｖはその証明を検証する。【００５４】
Uはどのような方法で(x_U、R_[N_10]、 R_[N_20])の知識を証明してもよいが、例えば以下の方法で証明できる。
１．VはZ_qの元c、rをランダムに選び、C=K_[O0]^cL_[O0]^rを計算する。
２．UはZ_qの元x'、R'_1、R'_2をランダムに選び、Q'_1=K_[O_10]^[x'] L_[O_10]^[R'_1]とQ'_2=K_[O_20]^[x'] L_[O_20]^[R'_2]を計算し、Q'_1とQ'_2をVに送信する。
３．Vはc、rをUに送信する。
４．UはC=K_[O0]^cL_[O0]^rが成立するかどうかを確認する。 もしC=K_[O0]^cL_[O0]^rが成立しなけれUは証明を終了する。
５．Uはρ_x=cx_U+x'、ρ_[R_1]=cR_[N_10]+R'_1、ρ_[R_2]=cR_[N_20]+R'_2を計算し、ρ_x、ρ_[R_1]、ρ_[R_2]をVに送信する。
６．VはQ_[N_10]^cQ'_1=K_[O_10]^[ρ_x] L_[O_10]^[R'_1]と
Q_[N_20]^cQ'_2=K_[O_20]^[ρ_x] L_[O_20]^[R'_2]が成立すれば証明を受理し、そうでなければ棄却する。【００５５】
（第二の実施の形態）
以下のように仮名生成（１２と２２）を行う。 他は第一の実施の形態と同じである。【００５６】
＜仮名生成（１２と２２）＞
W_[N1]、…、W_[Nm]をユーザの属性とする。
ユーザ装置２であるUとオーガニゼーション装置１であるOは以下のようにして仮名生成（１２と２２）を行う。
１．OはメッセージN_2を選び、通信回線を使ってUに送る。
２．UはメッセージN_1をえらび、仮名NをN=N_1||N_2とする。
３．UはGの元R_[N0]、…、R_[Nm]をランダムに選ぶ。
４．UはQ_[N0]=K_[O0]^[x_U]L_[O0]^[R_[N0]]を計算し、Q_[N0]の正当性を証明する。そしてＯはその証明を検証する。
５．UはQ_[N1]=K_[O1]^[H(W_1)]L_[O1]^[R_[N1]]、…、Q_[Nm]=K_[Om]^[H(W_m)]L_[Om]^[R_[Nm]]を計算する。
６．Uは(W_[N1]、…、W_[Nm]、R_[N0]、…、R_[Nm]、Q_[N0])を通信回線を使ってOに送る。
７．OはQ_[N1]=K_[O1]^[H(W_1)]L_[O1]^[R_[N1]]、…、 Q_[Nm]=K_[Om]^[H(W_m)]L_[Om]^[R_[Nm]]を計算する。
８．Uは仮名Nとタグ(Q_[N0]、 Q_[N1]、…、 Q_[Nm])、W_[N1]、…、W_[Nm]、R_[N0]、…、R_[Nm]を記憶部に保管する。【００５７】
Uはどのような方法でx_U、R_[N0]の知識を証明してもよいが、例えば第一の実施の形態で説明した方法で証明できる。【００５８】
（第三の実施の形態）
第一、第二の実施の形態では、ユーザ装置２であるUは仮名生成（１２と２２）を行うたびにR_[Ni]を選び直している。【００５９】
しかし目的によっては、複数の仮名生成（１２と２２）で同じR_[Ni]を使用してもよい。
属性もW_[Ni]とR_[Ni]が２回の仮名生成（１２と２２）で同じなら、１回目の仮名生成（１２と２２）で作成されたQ_[N_1i]と２回目の仮名生成（１２と２２）で作成されたQ_[N_2i]は同一のものになる。よってこの場合タグ関連性証明２６とタグ関連性検証３６を以下のように行う事ができる。【００６０】
＜タグ関連性証明２６とタグ関連性検証３６＞
ステップ１．〜４．は第一の実施の形態のタグ関連性証明２６とタグ関連性検証３６と同じ。
５．は以下のように行う。
５．VはQ_[N_1i]=Q_[N_2i]なら証明を受理し、そうでなければ棄却する。【００６１】
（第四の実施の形態）
Σ=(GenParam、SGen、VGen、Sig、Ver、DSig、DVer)を検証者指定検証方式とする。
ここでGenParam、SGen、VGen、Sig、Ver、DSig、DVerはそれぞれ公開情報生成、署名者鍵生成、検証者鍵生成、源署名生成、検証、指定検証者署名生成のアルゴリズムがある。さらにGを素数位数の巡回群でG上の離散対数問題が困難なものとし、qをGの位数とする。さらにHをハッシュ関数とし、λをセキュリティ・パラメータとする。【００６２】
＜オーガニゼーション鍵生成１１＞
オーガニゼーション装置１であるOは以下のようにしてオーガニゼーション鍵生成１１を行う。
１．λを記憶部から読み込む。
２．GenParam(λ)を実行し、GenParamの出力paramを得る。 さらにSGenを行い、公開鍵spkと秘密鍵sskを得る。
３．自然数mを選び、Gの元K_[O0]、L_[O0]、…、K_[Om]、L_[Om]をランダムに選ぶ。
４．(param、spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])を公開鍵とし、sskを秘密鍵とする。
５．公開鍵(param、spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])と秘密鍵sskとを記憶部に書き込む。
６．公開鍵(param、spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])を公開する。【００６３】
＜ユーザ秘密鍵生成２１＞
ユーザ装置２であるUは第一の実施の形態と同じ方法で仮名生成（１２と２２）を行う。
すなわち、以下のようにしてユーザ秘密鍵生成２１を行う。
１．Gの元x_Uをランダムに選ぶ。
２．x_Uを記憶部に書き込む。【００６４】
＜仮名生成（１２と２２）＞
W_[N1]、…、W_[Nm]をユーザの属性とする。
ユーザ装置２であるUとオーガニゼーション Oは第一の実施の形態と同じ方法で仮名生成（１２と２２）を行う。【００６５】
＜所属証明書生成（１３と２３）＞
ユーザ装置２であるUとオーガニゼーション Oは以下のようにして所属証明書生成（１３と２３）を行う。
１．Uは記憶部から(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を読み込み、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を通信回線を使ってOに送る。
２．Oはparamとsskを記憶部から読み込み、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])に対する源署名S_N=Sig_[param、ssk](N、Q_[N0]、Q_[N1]、…、 Q_[Nm])を計算し、S_NをUに送信する。
３．Uはparamとspkを記憶部から読み込み、Ver_[param、spk]((N、Q_[N0]、Q_[N1]、…、 Q_[Nm])、S_N)を実行し、Ver_[param、spk]が受理を出力S_Nを所属証明書として記憶部に書き込む。 そうでなければ所属証明書生成（１３と２３）は失敗に終わる。【００６６】
＜所属証明書所有証明２４と所属証明書所有検証３４＞
Nを、オーガニゼーション Oが管理するグループにおけるユーザ装置２であるUの仮名とする。
UがNに対する所属証明書の所有を検証者装置３であるVに証明するには、以下のようにする。
１．Uは公開情報param、オーガニゼーション Oの公開鍵K_[O0]、L_[O0]と(N、Q_[N0]、 x_U、R_[N0]、S_N)を記憶部から読み込む。
２．Vはオーガニゼーション Oの公開鍵spk、K_[O0]、L_[O0]、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を記憶部から読み込む。
３．VはVGen(λ)を行い、VGenの出力として公開鍵vpk、vskを得、vpkをUに送信し、vpkの正当性をUに証明する。 Ｖはその証明を検証する。
４．UはDSig_[param、spk、vpk](N、S_N)を実行し、DSigの出力σ_Nを得、Nとσ_Nを通信回線を使ってVに送信する。
５．VはDVer_[param、spk、vpk]((N、Q_[N0]、Q_[N1]、…、 Q_[Nm])、σ_N)を実行し、DVerが拒否を出力したらVはUの証明を拒否する。
６．UはQ_[N0]=K_[O0]^[x_U]L_[O0]^[R_[N0]]を満たすx_U、R_[N0]の知識をVに証明する。Ｖはその証明を検証する。【００６７】
Uはどのような方法でx_U、R_[N0]の知識を証明してもよいが、例えば第一の実施の形態の仮名生成（１２と２２）の所で説明した方法で証明できる。【００６８】
＜属性証明２５と属性検証３５＞
Nを、オーガニゼーション Oが管理するグループにおけるユーザ装置２であるUの仮名とする。
UがNに対するi番目の属性W_iを検証者装置３であるVに証明するには第一の実施の形態と同じようにする。【００６９】
＜タグ関連性証明２６とタグ関連性検証３６＞
O_1、O_2をオーガニゼーション装置１とする。 O_1とO_2は同じオーガニゼーションでもよい。【００７０】
(spk、 K_[O_10]、L_[O_10]、…、K_[O_1m]、L_[O_1m])、(spk、K_[O_20]、L_[O_20]、…、K_[O_2m]、L_[O_2m])をそれぞれO_1、O_2の公開鍵とする。
さらにユーザ装置２であるUがO_1の管理するグループにおける仮名N_1とN_1に関するタグ(Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m]、W_[N_11]、…、W_[N_1m]、R_[N_10]、…、R_[N_1m]、σ[N_1])と仮名N_2とN_2に関するタグ(Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m]、W_[N_21]、…、W_[N_2m]、R_[N_20]、…、R_[N_2m]、σ[N_2])を記憶部に保管していたとする。【００７１】
Uが検証者装置３であるVに対して所属証明書関連性証明を行うには、以下のようにする。
１．UはK_[O_10]、L_[O_10]、x_U、(N_1、Q_[N_10]、R_[N_10]、σ[N_1])、(N_2、Q_[N_20]、 R_[N_20]、σ[N_2])を記憶部から読み込む。
２．Vはparam、spk、K_[O_10]、L_[O_10]、 (N_1、 Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m])、(N_2、 Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m])を記憶部から読み込む。
３．Uはσ[N_1]、σ[N_2]を通信装置を使ってVに送信する。
４．VはVer_[param、spk]((N_1、Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m])、σ[N_1])、Ver_[param、spk]((N_12 Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m])、σ[N_2])の少なくとも一方が拒否なら、Uの証明を拒否する。
５．UはQ_[N_10]=K_[O_10]^[x_U] L_[O_10]^[R_[N_10]]とQ_[N_20]=K_[O_10]^[x_U] L_[O_20]^[R_[N_20]]を満たす(x_U、 R_[N_10]、 R_[N_20])の知識をVに証明する。 Ｖはその証明を検証する。【００７２】
Uはどのような方法で(x_U、R_[N_10]、 R_[N_20])の知識を証明してもよいが、例えば第一の実施の形態で説明した方法で証明できる。【００７３】
（第五の実施の形態）
第二の実施の形態と同じ方法で仮名生成（１２と２２）を行う。他は第四の実施の形態と同じである。【００７４】
（第六の実施の形態）
第三の実施の形態と同じ方法で仮名生成（１２と２２）を行う。他は第四の実施の形態と同じである。【００７５】
（第七の実施の形態）
第四の実施の形態でVは所属証明書所有証明（２４と３４）を行うたびにvpk、vskを生成していたが、用途によっては全ての所属証明書所有証明（２４と３４）で同じvpk、vskを使ってもよい。【００７６】
（実施例１）
第二の実施の形態の検証者指定検証方式Σ=(GenParam、SGen、VGen、Sig、Ver、DSig、DVer)として非特許文献２の方式を使ったものを説明する。
群G_1、G_2、G_Tをλビットの位数を持ち、ペアリング<・、・> : G_1×G_2→G_Tと写像ψ:G_2→G_1を持つものとする。
qをG_1の位数（＝G_2の位数＝G_Tの位数）し、HをG_2に値を取るハッシュ関数とする。G=G_1とする。【００７７】
＜オーガニゼーション鍵生成１１＞
オーガニゼーション装置１であるOは以下のようにしてオーガニゼーション鍵生成１１を行う。
１．λを記憶部から読み込む。
２．G_1の元g_1をランダムに選び、g_2=ψ(g_1)とし、param=(g_1、g_2)とし、Z_qの元sskをランダムに選び、spk=g_1^[ssk]を計算する。
３．自然数mを選び、Gの元K_[O0]、L_[O0]、…、K_[Om]、L_[Om]をランダムに選ぶ。
４．(param、spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])を公開鍵とし、sskを秘密鍵とする。
５．公開鍵(param、spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])と秘密鍵sskとを記憶部に書き込む。
６．公開鍵(param、spk、 K_[O0]、L_[O0]、…、K_[Om]、L_[Om])を公開する。【００７８】
＜ユーザ秘密鍵生成２１＞
ユーザ装置２であるUは第一の実施の形態と同じ方法で仮名生成（１２と２２）を行う。
すなわち、以下のようにしてユーザ秘密鍵生成２１を行う。
１．G_1の元x_Uをランダムに選ぶ。
２．x_Uを記憶部に書き込む。【００７９】
＜仮名生成（１２と２２）＞
W_[N1]、…、W_[Nm]をユーザの属性とする。
ユーザ装置２であるUとオーガニゼーション装置１であるOは第一の実施の形態と同じ方法で仮名生成（１２と２２）を行う。【００８０】
＜所属証明書生成（１３と２３）＞
ユーザ装置２であるUとオーガニゼーション装置１であるOは以下のようにして所属証明書生成（１３と２３）を行う。
１．Uは記憶部から(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を読み込み、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を通信回線を使ってOに送る。
２．Oはparamとsskを記憶部から読み込み、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])に対する源署名S_N=H(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])^[ssk]を計算し、S_NをUに送信する。
３．Uはparamとspkを記憶部から読み込み、<g_1、S_N>=<spk、H((N、Q_[N0]、Q_[N1]、…、 Q_[Nm])、S_N)>ならS_Nを所属証明書として記憶部に書き込む。 そうでなければ所属証明書生成（１３と２３）は失敗に終わる。【００８１】
＜所属証明書所有証明２４と所属証明書所有検証３４＞
Nを、オーガニゼーション Oが管理するグループにおけるユーザ装置２であるUの仮名とする。
UがNに対する所属証明書の所有を検証者装置３であるVに証明するには、以下のようにする。
１．Uは公開情報param、オーガニゼーション Oの公開鍵K_[O0]、L_[O0]と(N、Q_[N0]、 x_U、R_[N0]、S_N)を記憶部から読み込む。
２．Vはオーガニゼーション Oの公開鍵spk、K_[O0]、L_[O0]、(N、Q_[N0]、 Q_[N1]、…、 Q_[Nm])を記憶部から読み込む。
３．VはZ_qの元vskをランダムに選び、vpk=g_1^[vsk]とし、vpkをUに送信し、vpkの正当性をUに証明する。 Ｖはその証明を検証する。
４．σ_N=<vpk、S_N>とし、Nとσ_Nを通信回線を使ってVに送信する。
５．σ_N=<spk^[vsk]、H(N、Q_[N0]、Q_[N1]、…、 Q_[Nm])>が成立していなければ、VはUの証明を拒否する。
６．UはQ_[N0]=K_[O0]^[x_U]L_[O0]^[R_[N0]]を満たすx_U、R_[N0]の知識をVに証明する。Ｖはその証明を検証する。【００８２】
Uはどのような方法でx_U、R_[N0]の知識を証明してもよいが、例えば第一の実施の形態の仮名生成（１２と２２）の所で説明した方法で証明できる。【００８３】
＜属性証明２５と属性検証３５＞
Nを、オーガニゼーション Oが管理するグループにおけるユーザ装置２であるUの仮名とする。
UがNに対するi番目の属性W_iを検証者装置３であるVに証明するには第一の実施の形態と同じようにする。【００８４】
＜タグ関連性証明２６とタグ関連性検証３６＞
O_1、O_2をオーガニゼーション装置１とする。 O_1とO_2は同じオーガニゼーションでもよい。【００８５】
(spk、 K_[O_10]、L_[O_10]、…、K_[O_1m]、L_[O_1m])、(spk、K_[O_20]、L_[O_20]、…、K_[O_2m]、L_[O_2m])をそれぞれO_1、O_2の公開鍵とする。
さらにユーザ装置２であるUがO_1の管理するグループにおける仮名N_1とN_1に関するタグ(Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m]、W_[N_11]、…、W_[N_1m]、R_[N_10]、…、R_[N_1m]、σ_[N_1])と仮名N_2とN_2に関するタグ(Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m]、W_[N_21]、…、W_[N_2m]、R_[N_20]、…、R_[N_2m]、σ_[N_2])を記憶部に保管していたとする。【００８６】
Uが検証者装置３であるVに対して所属証明書関連性証明を行うには、以下のようにする。
１．UはK_[O_10]、L_[O_10]、x_U、(N_1、Q_[N_10]、R_[N_10]、σ_[N_1])、(N_2、Q_[N_20]、 R_[N_20]、σ_[N_2])を記憶部から読み込む。
２．Vはparam、spk、K_[O_10]、L_[O_10]、 (N_1、 Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m])、(N_2、 Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m])を記憶部から読み込む。
３．Uはσ_[N_1]、σ_[N_2]を通信装置を使ってVに送信する。
４．σ_[N_1]=<spk^[vsk]、H((N_1、Q_[N_10]、 Q_[N_11]、…、 Q_[N_1m]))>、σ_[N_2]=<spk^[vsk]、H((N_2、Q_[N_20]、 Q_[N_21]、…、 Q_[N_2m]))>の少なくとも一方が成立しないなら、VはUの証明を拒否する。
５．UはQ_[N_10]=K_[O_10]^[x_U] L_[O_10]^[R_[N_10]]とQ_[N_20]=K_[O_10]^[x_U] L_[O_20]^[R_[N_20]]を満たす(x_U、 R_[N_10]、 R_[N_20])の知識をVに証明する。 Ｖは証明を検証する。【００８７】
Uはどのような方法で(x_U、R_[N_10]、 R_[N_20])の知識を証明してもよいが、例えば第一の実施の形態で説明した方法で証明できる。【００８８】
（実施例２）
本発明は電子的な免許証に応用できる。これらの応用では、ＣＡという特殊なオーガニゼーションがおり、ＣＡは各ユーザの当人性を確認する役割を担う。【００８９】
ユーザがアノニマス・クレデンシャルのシステムを使うには、まずＣＡにアクセスする。ＣＡはユーザの当人性を確認した後、ユーザと仮名生成１２と所属証明書生成１３を行い、ユーザに仮名とタグと所属証明書を発行する。【００９０】
免許証への応用では免許発行センターがオーガニゼーションになる。
免許を取得する際、ユーザは本名を明かさずに、変わりにＣＡが発行した仮名を提示する。
さらにユーザは免許発行センターに対して所属証明書所有証明２４を行う。
ユーザは免許発行センターから免許を取得する許可を得る。【００９１】
免許を取得する許可をユーザに与えたら、免許発行センターはユーザと仮名生成１２と所属証明書生成１３を行う事で新たな仮名PとタグTと所属証明書pfを発行する。
所属証明書は免許証に相当するもので、仮名がPであるユーザが免許を持っている事を証明する。【００９２】
ユーザは免許証の提示を求められるたびに所属証明書所有証明２４を行う。
同様にして本発明を会員証へも応用できる。
会員証への応用では会員クラブの主催者がオーガニゼーションになる。
この応用では、所属証明書は免許証ではなく会員証に相当する。
よってユーザはクラブを利用するたびに所属証明書所有証明２４を行う事でクラブの会員である事を証明できる。これ以外の詳細は免許証の場合と同様である。【００９３】
ユーザは必要に応じて属性証明２５を行う事でユーザは自分の属性を証明できる。例えば２０才以上の人物しか利用できないサービスを利用する場合は、ユーザは年齢という属性を証明する事で、このサービスを利用できる。
ユーザは複数の仮名で複数の免許証・会員証を持っている。ユーザはタグ関連性証明２６を行う事でそれらの免許証・会員証が実は同一人物のものである事を証明できる。【００９４】
なお、上述する各実施の形態は、本発明の好適な実施の形態であり、本発明の要旨を逸脱しない範囲内において種々変更実施が可能である。例えば、第一〜第七の実施の形態の各装置の機能を実現するソフトウェアのプログラムコードを記憶した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータが記憶媒体に格納されたプログラムコードを読みだして実行してもよい。さらに、そのプログラムは、コンピュータ読み取り可能な記録媒体であるＣＤ−ＲＯＭまたは光磁気ディスクなどを介して、または伝送媒体であるインターネット、電話回線などを介して伝送波により他のコンピュータシステムに伝送されてもよい。【００９５】
なお、この出願は、２００７年１１月２１日に出願した、日本特許出願番号２００７−３０１４６６号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００９６】
本発明は、例えば、ユーザ装置と、オーガニゼーション装置と、検証者装置とから構成される情報通信システムに適用可能である。
【図面の簡単な説明】
【００９７】
【図１】非特許文献１のブロック図である。
【図２】本発明の実施の形態に係るブロック図である。
【符号の説明】
【００９８】
１    オーガニゼーション装置
２    ユーザ装置バ
３    検証者装置
１７、２７、３７    演算部
１８、２８、３８    記憶部
１９、２９、３９    通信部
【図１】
2009066557.tif 000003
【図２】
2009066557.tif 000004
【手続補正書】
【提出日】平成21年3月16日(2009.3.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
オーガニゼーション装置とユーザ装置と検証者装置からなる情報通信システムで、
前記ユーザ装置には自身の秘密鍵があり、
前記オーガニゼーション装置と前記ユーザ装置には仮名とタグを生成する手段があり、
前記ユーザ装置には前記仮名と前記タグが前記オーガニゼーション装置から発行された事を証明する所属証明書を生成する手段があり、
前記ユーザ装置には所属証明書の所有を証明する手段があり、
前記検証装置には所属証明書の所有を検証する手段があるものであって、
仮名とタグを生成する前記手段は前記ユーザ装置の秘密鍵のコミットメントをふくむタグと仮名を前記ユーザ装置に出力し、
所属証明書を生成する前記手段は前記タグと前記仮名に対する署名文を所属証明書として前記ユーザ装置に出力し、
所属証明書の所有を証明する前記手段では前記署名文をユーザ装置が前記検証者装置に送信し、
前記タグが前記秘密鍵のコミットメントである事を前記ユーザ装置が前記検証者装置に証明し、
所属証明書の所有を検証する前記手段では前記署名文を前記検証者装置が検証し、
さらに前記タグが前記秘密鍵のコミットメントである事の証明を前記検証者装置が検証する事を特徴とする情報通信システム。
【請求項２】
さらにユーザ装置が２つ以上のオーガニゼーション装置から仮名とタグを発行してもらった際にそれら２つのタグが同じユーザ装置のものである事を示す為のタグ関連性証明の手段を前記ユーザ装置が持ち、
前記タグ関連性証明を検証する手段を前記検証者装置持ち、
前記タグ関連性証明では２つのタグが同じ秘密鍵を用いて生成されている事を前記ユーザ装置が証明し、
前記タグ関連性検証では２つのタグが同じ秘密鍵を用いて生成されている事の証明を前記検証者装置が検証する事を特徴とする請求項１に記載の情報通信システム。
【請求項３】
仮名とタグを生成する前記手段ではさらに前記タグが秘密鍵のコミットメントを含むものである事を前記ユーザ装置が前記オーガニゼーション装置に証明し、
さらに前記タグが秘密鍵のコミットメントを含むものである事の証明を前記オーガニゼーション装置が検証する事を特徴とする請求項１または２に記載の情報通信システム。
【請求項４】
前記秘密鍵ｘのコミットメントＣが、公開情報ＫとＬとを使い、ランダムに選んだＲでＣ＝Ｋ＾ｘＬ＾Ｒにより作成される事を特徴とする請求項１から３のいずれか１項に記載の情報通信システム。
【請求項５】
さらに属性を証明する手段を前記ユーザ装置が持ち、属性の証明を検証する手段を前記検証装置が持ち、
仮名とタグを生成する前記手段では前記ユーザ装置がさらに仮名に関する属性のコミットメントを作成し、
さらに前記秘密鍵のコミットメントと前記属性のコミットメントを含むものをタグとし、
属性を証明する前記手段では前記署名文を前記ユーザ装置が前記検証者装置に送信し、
前記タグが秘密鍵のコミットメントである事を前記ユーザ装置が前記検証者装置に証明し、
属性の証明を検証する前記手段では前記署名文を前記検証者装置が検証し、
さらに前記タグが秘密鍵のコミットメントである事の証明を前記検証者装置が検証する事を特徴とする請求項１または２に記載の情報通信システム。
【請求項６】
仮名とタグを生成する前記手段ではさらに前記タグが秘密鍵のコミットメント及び属性のコミットメントを含むものである事を前記ユーザ装置が前記オーガニゼーション装置に証明し、
さらに前記タグが秘密鍵のコミットメント及び属性のコミットメントを含むものである事の証明を前記オーガニゼーション装置が検証する事を特徴とする請求項５記載の情報通信システム。
【請求項７】
前記秘密鍵ｘのコミットメントＣが、公開情報ＫとＬとを使い、ランダムに選んだＲでＣ＝Ｋ＾ｘＬ＾Ｒにより作成され、
前記属性のｉ番目のものＷ＿ｉのコミットメントＣ＿ｉが、公開情報Ｋ＿ｉとＬ＿ｉとを使い、ランダムに選んだＲ＿ｉでＣ＝Ｋ＾［Ｗ＿ｉ］Ｌ＾［Ｒ＿ｉ］により作成される事を特徴とする請求項５または６に記載の情報通信システム。
【請求項８】
請求項１から７のいずれか１項に記載された情報通信システムのオーガニゼーション装置。
【請求項９】
請求項１から７のいずれか１項に記載された情報通信システムのユーザ装置。
【請求項１０】
オーガニゼーション装置とユーザ装置と検証者装置からなる情報通信システムで、
前記ユーザ装置には自身の秘密鍵があり、
前記オーガニゼーション装置と前記ユーザ装置には仮名とタグを生成する手段があり、
前記ユーザ装置と前記オーガニゼーション装置には仮名が前記オーガニゼーション装置から発行された事を証明する所属証明書を生成する手段があり、
前記ユーザ装置には所属証明書の所有を証明する手段があり、
前記変賞装置には所属証明書の所有を検証する手段があるものであって、
仮名とタグを生成する前記手段では何からのビット列を仮名にし、
さらに前記ユーザ装置が自身の秘密鍵のコミットメントを含むものをタグとし、
所属証明書を生成する前記手段では前記タグに対する源署名文を汎用指定検証者署名方式の源署名生成手段に従って作成し、
さらに前記源署名文を所属証明書として前記ユーザ装置に出力し、
所属証明書の所有を証明する前記手段では前記源署名文を見せずに前記源署名文の知識を前記ユーザ装置が証明し、
所属証明書の所有を検証する前記手段では前記源署名文を見せずに前記源署名文の知識を前記検証装置が検証する事を特徴とする情報通信システム。
【請求項１１】
所属証明書の所有を証明する前記手段では前記源署名文から前記汎用指定検証者署名方式の指定検証者署名生成手段に従って指定検証者署名を生成し、
さらに前記指定検証者署名を検証者装置に送信し、
さらに前記タグが秘密鍵のコミットメントであることを前記ユーザ装置が検証者装置に証明し、
所属証明書の所有を検証する前記手段では前記指定検証者署名文を前記検証者装置が検証し、
さらに前記タグが秘密鍵のコミットメントである事の証明を検証する事を特徴とする請求項１０に記載の情報通信システム。
【請求項１２】
さらにユーザ装置が２つ以上のオーガニゼーション装置から仮名とタグを発行してもらった際にそれら２つのタグが同じユーザ装置のものである事を示す為のタグ関連性証明の手段を前記ユーザ装置が持ち、
さらにタグ関連性証明を検証する手段を前記検証装置が持ち、
タグ関連性証明の手段では前記タグ関連性証明では２つのタグが同じ秘密鍵を用いて生成されている事をユーザ装置が検証者装置に証明し、
タグ関連性証明を検証する手段では前記タグ関連性証明では２つのタグが同じ秘密鍵を用いて生成されている事の証明を検証者装置が検証する事を特徴とする請求項１０または１１に記載の情報通信システム。
【請求項１３】
仮名とタグを生成する前記手段ではさらに前記タグが秘密鍵のコミットメントを含むものである事を前記ユーザ装置が前記オーガニゼーション装置に証明し、
さらに前記タグが秘密鍵のコミットメントを含むものである事の証明を前記オーガニゼーション装置が検証する事を特徴とする請求項１０から１２のいずれか１項に記載の情報通信システム。
【請求項１４】
前記秘密鍵ｘの前記コミットメントＣが、公開情報ＫとＬとを使い、ランダムに選んだＲでＣ＝Ｋ＾ｘＬ＾Ｒにより作成される事を特徴とする請求項１０から１３のいずれか１項に記載の情報通信システム。
【請求項１５】
さらに属性を証明する手段を前記ユーザ装置が持ち、属性の証明を検証する手段を前記検証装置が持ち、
仮名を生成する前記手段では前記ユーザ装置がさらに仮名に関する属性のコミットメントを作成し、
さらに前記秘密鍵のコミットメントと前記属性のコミットメントを含むものをタグとし、
属性を証明する前記手段では前記証明文を前記ユーザ装置が前記検証者装置に送信し、さらに前記属性に対するタグに含まれるコミットメントが属性のコミットメントを含むものである事を前記ユーザ装置が前記検証者装置に証明し、
属性の証明を検証する前記手段では前記署名文を前記検証者装置が検証し、
さらに前記属性に対するタグに含まれるコミットメントが属性のコミットメントを含むものである事の証明を前記検証者装置が検証する事を特徴とする請求項１０から１２のいずれか１項に記載の情報通信システム。
【請求項１６】
仮名とタグを生成する前記手段ではさらに前記タグが秘密鍵のコミットメント及び属性のコミットメントを含むものである事を前記ユーザ装置が前記オーガニゼーション装置に証明し、
さらに前記タグが秘密鍵のコミットメント及び属性のコミットメントを含むものである事の証明を前記オーガニゼーション装置が検証する事を特徴とする請求項１５記載の情報通信システム。
【請求項１７】
前記属性のｉ番目のものＷ＿ｉのコミットメントＣ＿ｉが、公開情報Ｋ＿ｉとＬ＿ｉとを使い、ランダムに選んだＲ＿ｉでＣ＝Ｋ＾［Ｗ＿ｉ］Ｌ＾［Ｒ＿ｉ］により作成され、
前記秘密鍵ｘの前記コミットメントＣが、公開情報ＫとＬとを使い、ランダムに選んだＲでＣ＝Ｋ＾ｘＬ＾Ｒにより作成される事を特徴とする請求項１５または１６に記載の情報通信システム。
【請求項１８】
請求項１０から１７のいずれか１項に記載の情報通信システムのオーガニゼーション装置。
【請求項１９】
請求項１０から１７のいずれか１項に記載の情報通信システムのユーザ装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
非特許文献１：Ｊａｎ  Ｃａｍｅｎｉｓｃｈ、Ａｎｎａ  Ｌｙｓｙａｎｓｋａｙａ。Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｓｙｓｔｅｍ  ｆｏｒ  Ｎｏｎ−ｔｒａｎｓｆｅｒａｂｌｅ  アノニマス・クレデンシャル  ｓ  ｗｉｔｈ  Ｏｐｔｉｏｎａｌ  Ａｎｏｎｙｍｉｔｙ  Ｒｅｖｏｃａｔｉｏｎ．ＥＵＲＯＣＲＹＰＴ  ２００１．ｐｐ．９３−１１８．
非特許文献２：Ｒｏｎ  Ｓｔｅｉｎｆｅｌｄ、Ｌａｕｒｅｎｃｅ  Ｂｕｌｌ、Ｈｕａｘｉｏｎｇ  Ｗａｎｇ、Ｊｏｓｅｆ  Ｐｉｅｐｒｚ  ｙｋ：Ｕｎｉｖｅｒｓａｌ  Ｄｅｓｉｇｎａｔｅｄ−Ｖｅｒｉｆｉｅｒ  Ｓｉｇｎａｔｕｒｅｓ．ＡＳＩＡＣＲＹＰＴ  ２００３．ｐｐ．５２３−５４２
発明の開示
発明が解決しようとする課題
［００２７］
しかしながら、上述の関連技術では、年齢、性別、嗜好といったユーザの属性を公開情報にしないように取り扱う事ができるようにする事が課題である。
［００２８］
非特許文献１の方式でも仮名の自由記述部に属性を書き込めば属性を取り扱う事ができるが、自由記述部の情報は公開情報なので、属性の秘密を保つ事ができない。
また非特許文献１の方式の効率の悪さを改善する事も課題である。
［００２９］
また非特許文献１の方式はオーガニゼーション、ユーザ、および検証者以外にデータベースを別個に作らねばならない。
［００３０］
本発明は、以上のような課題を解決するためになされたもので、属性を取り扱い、なおかつ属性を公開情報にしないようにでき、効率がよく、データベースを必要としない情報通信システム、オーガニゼーション装置およびユーザ装置を提供することを目的とする。
課題を解決するための手段
［００３１］
かかる目的を達成するために、本発明は、以下の特徴を有することとする。
［００３２］
本発明の第１の情報通信システムは、オーガニゼーション装置とユーザ装置と検証者装置からなる情報通信システムで、
前記ユーザ装置には自身の秘密鍵があり、
前記オーガニゼーション装置と前記ユーザ装置には仮名とタグを生成する手段があり、
前記ユーザ装置には前記仮名と前記タグが前記オーガニゼーション装置から発行された事を証明する所属証明書を生成する手段があり、
前記ユーザ装置には所属証明書の所有を証明する手段があり、
前記検証装置には所属証明書の所有を検証する手段があるものであって、
仮名とタグを生成する前記手段は前記ユーザ装置の秘密鍵のコミットメントをふくむ
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
タグと仮名を前記ユーザ装置に出力し、
所属証明書を生成する前記手段は前記タグと前記仮名に対する署名文を所属証明書として前記ユーザ装置に出力し、
所属証明書の所有を証明する前記手段では前記署名文をユーザ装置が前記検証者装置に送信し、
前記タグが前記秘密鍵のコミットメントである事を前記ユーザ装置が前記検証者装置に証明し、
所属証明書の所有を検証する前記手段では前記署名文を前記検証者装置が検証し、
さらに前記タグが前記秘密鍵のコミットメントである事の証明を前記検証者装置が検証する事を特徴とする。
［００３３］
また、本発明の第２の情報通信システムは、オーガニゼーション装置とユーザ装置と検証者装置からなる情報通信システムで、
前記ユーザ装置には自身の秘密鍵があり、
前記オーガニゼーション装置と前記ユーザ装置には仮名とタグを生成する手段があり、
前記ユーザ装置と前記オーガニゼーション装置には仮名が前記オーガニゼーション装置から発行された事を証明する所属証明書を生成する手段があり、
前記ユーザ装置には所属証明書の所有を証明する手段があり、
前記変賞装置には所属証明書の所有を検証する手段があるものであって、
仮名とタグを生成する前記手段では何からのビット列を仮名にし、
さらに前記ユーザ装置が自身の秘密鍵のコミットメントを含むものをタグとし、
所属証明書を生成する前記手段では前記タグに対する源署名文を汎用指定検証者署名方式の源署名生成手段に従って作成し、
さらに前記源署名文を所属証明書として前記ユーザ装置に出力し、
所属証明書の所有を証明する前記手段では前記源署名文を見せずに前記源署名文の知識を前記ユーザ装置が証明し、
所属証明書の所有を検証する前記手段では前記源署名文を見せずに前記源署名文の知識を前記検証装置が検証する事を特徴とする。
発明の効果
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
［００３４］
本発明によれば、属性を取り扱い、なおかつ属性を公開情報にしないようにでき、効率がよく、データベースを必要としない情報通信システム、オーガニゼーション装置およびユーザ装置を提供することができる。
発明を実施するための最良の形態
［００３５］
［装置構成とプロシージャ］
本発明の装置構成は非特許文献１のそれに似ているがデータベース管理者が存在しない。
本発明にはユーザ、オーガニゼーション、検証者の３種類のエンティティが参加する。
ユーザ、オーガニゼーション、および検証者は計算機（例えばパーソナル・コンピュータ）を持っているものとする。
［００３６］
本発明は、例えば、図２に示すような情報通信システムに適用される。この情報通信システムは、上記図２に示すように、ユーザ装置２と、オーガニゼーション装置１と、検証者装置３とから構成されている。
ユーザ、オーガニゼーションが所有している計算機をそれぞれユーザ装置２、オーガニゼーション装置１、検証者装置３という。これらの装置は演算部、記憶部、および通信部を持っている。演算部、記憶部、通信部はそれぞれ例えばＣＰＵ、ハードディスク、およびインターネット用のポートが使えるが、どのようなものを用いてもよい。
［００３７］
装置同士はなんらかの通信回線を経由して通信できる。通信回線としては例えばインターネットがあるが、どのようなものを用いてもよい。
［００３８］
また、各オーガニゼーション装置１が自身の公開鍵を公開する何らかの方法があるとする。例えばＰＫＩの仕組みを用いる事で、オーガニゼーション装置１は公開鍵を公開できる。
［００３９］
本発明のプロシージャは非特許文献１のそれに似ているが、新たに属性証明２５と
【国際調査報告】
2009066557.tif 000005
2009066557.tif 000006
2009066557.tif 000007