(57)【特許請求の範囲】
【請求項１】
ｐを素数、ｘ，ｙ∈Ｚｐ＊をマスタ秘密鍵、Ｇ，ＧＴを位数ｐの群、ｇ３∈Ｇとｇ１＝ｇ３１／ｘとｇ２＝ｇ３１／ｙをマスタ公開鍵、ａ，ｂ∈Ｚｐ＊をユーザ秘密鍵、ｇ１ａ，ｇ２ｂをユーザ公開鍵、ｅ：Ｇ×Ｇ→ＧＴをペアリング関数として、
ｇ∈Ｇ、上記マスタ公開鍵のｇ３、上記ユーザ秘密鍵ａ，ｂ及びｕ，ｖ∈Ｚｐ＊を用いて、タグであるｇｕ，ｇｖ及び（ｇ３ａ＋ｂ）ｕ／ｖを計算するタグ生成部と、上記マスタ公開鍵のｇ３及び上記ユーザ秘密鍵ａ，ｂを用いて、第一トークンｔｋｎ１＝ｇ３ａ＋ｂを計算する第一トークン計算部とを含むユーザ装置と、
上記マスタ秘密鍵ｘ，ｙ及びユーザ公開鍵ｇ１ａ，ｇ２ｂを用いて、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙを計算する第二トークン計算部を含む管理者装置と、
上記第一トークンｔｋｎ１又は第二トークンｔｋｎ２と上記タグｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖとを用いて、ｅ（ｔｋｎ１，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）又はｅ（ｔｋｎ２，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であるか計算するリンク計算部を含む検証者装置と、を含む、
タグシステム。
【請求項２】
請求項１に記載のタグシステムにおいて、
上記管理者装置は、上記マスタ秘密鍵ｍｔｓｋを生成するマスタ秘密鍵生成部と、上記マスタ秘密鍵ｍｔｓｋを用いて上記マスタ公開鍵ｐｔｐｋを生成するマスタ公開鍵生成部とを更に含む、
タグシステム。
【請求項３】
請求項１又は２に記載のタグシステムにおいて、
上記管理者装置は、上記ユーザ秘密鍵ａ，ｂを生成するユーザ秘密鍵生成部と、上記ユーザ秘密鍵ａ，ｂを用いて上記ユーザ公開鍵ｇ１ａ，ｇ２ｂを生成するユーザ公開鍵生成部とを更に含む、
タグシステム。
【請求項４】
ｐを素数、ｘ，ｙ∈Ｚｐ＊をマスタ秘密鍵、Ｇ，ＧＴを位数ｐの群、ｇ３∈Ｇとｇ１＝ｇ３１／ｘとｇ２＝ｇ３１／ｙをマスタ公開鍵、ａ，ｂ∈Ｚｐ＊をユーザ秘密鍵、ｇ１ａ，ｇ２ｂをユーザ公開鍵、ｅ：Ｇ×Ｇ→ＧＴをペアリング関数として、
ユーザ装置が、ｇ∈Ｇ、上記マスタ公開鍵のｇ３、上記ユーザ秘密鍵ａ，ｂ及びｕ，ｖ∈Ｚｐ＊を用いて、タグであるｇｕ，ｇｖ及び（ｇ３ａ＋ｂ）ｕ／ｖを計算するタグ生成ステップと、
ユーザ装置が、上記マスタ公開鍵のｇ３及び上記ユーザ秘密鍵ａ，ｂを用いて、第一トークンｔｋｎ１＝ｇ３ａ＋ｂを計算する第一トークン計算ステップと、
管理者装置が、上記マスタ秘密鍵ｘ，ｙ及びユーザ公開鍵ｇ１ａ，ｇ２ｂを用いて、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙを計算する第二トークン計算ステップと、
検証者装置が、上記第一トークンｔｋｎ１又は第二トークンｔｋｎ２と上記タグｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖとを用いて、ｅ（ｔｋｎ１，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）又はｅ（ｔｋｎ２，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であるか計算するリンク計算ステップと、を含む、
タグシステムの方法。
【請求項５】
ｐを素数、ｘ，ｙ∈Ｚｐ＊をマスタ秘密鍵、Ｇを位数ｐの群、ｇ３∈Ｇとｇ１＝ｇ３１／ｘとｇ２＝ｇ３１／ｙをマスタ公開鍵、ａ，ｂ∈Ｚｐ＊をユーザ秘密鍵として、
ｇ∈Ｇ、上記マスタ公開鍵のｇ３、上記ユーザ秘密鍵ａ，ｂ及びｕ，ｖ∈Ｚｐ＊を用いて、タグであるｇｕ，ｇｖ及び（ｇ３ａ＋ｂ）ｕ／ｖを計算するタグ生成部と、
上記マスタ公開鍵のｇ３及び上記ユーザ秘密鍵ａ，ｂを用いて、第一トークンｔｋｎ１＝ｇ３ａ＋ｂを計算する第一トークン計算部と、
を含むユーザ装置。
【請求項６】
ｐを素数、ｘ，ｙ∈Ｚｐ＊をマスタ秘密鍵、Ｇを位数ｐの群、ａ，ｂ∈Ｚｐ＊をユーザ秘密鍵、ｇ１ａ，ｇ２ｂをユーザ公開鍵として、
上記マスタ秘密鍵ｘ，ｙ及びユーザ公開鍵ｇ１ａ，ｇ２ｂを用いて、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙを計算する第二トークン計算部を含む、
管理者装置。
【請求項７】
ｐを素数、ｘ，ｙ∈Ｚｐ＊をマスタ秘密鍵、Ｇ，ＧＴを位数ｐの群、ｇ３∈Ｇとｇ１＝ｇ３１／ｘとｇ２＝ｇ３１／ｙをマスタ公開鍵、ａ，ｂ∈Ｚｐ＊をユーザ秘密鍵、ｇ１ａ，ｇ２ｂをユーザ公開鍵、ｅ：Ｇ×Ｇ→ＧＴ、ｇ∈Ｇ、ｕ，ｖ∈Ｚｐ＊として、
第一トークンｔｋｎ１＝ｇ３ａ＋ｂ又は第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙと、タグｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖとを用いて、ｅ（ｔｋｎ１，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）又はｅ（ｔｋｎ２，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であるか計算するリンク計算部を含む、
検証者装置。
【請求項８】
請求項５から７の何れかの装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、電気通信システムに関し、特に匿名性を持つタグに関する。
【背景技術】
【０００２】
非特許文献１に記載されたいわゆるｔｒａｃｅａｂｌｅ  ｓｉｇｎａｔｕｒｅでは、ユーザによるサービスの利用を停止するために、ユーザがサービスの利用権限があるかどうかを検証する検証者に対して、管理者はユーザの秘密鍵から計算したユーザ固有の秘密情報を提供している（例えば、非特許文献１参照。）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】B.Libert and M.Yung. “Efficient traceable signatures in the standard model.”, In Paring 2009, volume 5672 of LNCS, pages 187-205. Springer-Verlag, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、ｔｒａｃｅａｂｌｅ  ｓｉｇｎａｔｕｒｅでは、ユーザの秘密情報に対応するユーザの公開鍵を特定することにより、そのユーザを特定することができる。すなわち、例えば、検証者は受け取ったユーザの秘密情報に基づいてサービスの利用が停止されたユーザを特定することができてしまう。この点において、ｔｒａｃｅａｂｌｅ  ｓｉｇｎａｔｕｒｅは、匿名性が高くない。
【０００５】
この発明の目的は、より匿名性の高いタグシステム、方法、ユーザ装置、管理者装置、検証者装置及びこれらのプログラムを提供することである。
【課題を解決するための手段】
【０００６】
この発明の１つの態様であるタグシステムは、ｐを素数、ｘ，ｙ∈Ｚｐ＊をマスタ秘密鍵、Ｇ，ＧＴを位数ｐの群、ｇ３∈Ｇとｇ１＝ｇ３１／ｘとｇ２＝ｇ３１／ｙをマスタ公開鍵、ａ，ｂ∈Ｚｐ＊をユーザ秘密鍵、ｇ１ａ，ｇ２ｂをユーザ公開鍵、ｅ：Ｇ×Ｇ→ＧＴをペアリング関数として、管理者装置と、ユーザ装置と、検証者装置とを備える。ユーザ装置は、ｇ∈Ｇ、マスタ公開鍵のｇ３、ユーザ秘密鍵ａ，ｂ及びｕ，ｖ∈Ｚｐ＊を用いて、タグであるｇｕ，ｇｖ及び（ｇ３ａ＋ｂ）ｕ／ｖを計算するタグ生成部と、マスタ公開鍵のｇ３及びユーザ秘密鍵ａ，ｂを用いて、第一トークンｔｋｎ１＝ｇ３ａ＋ｂを計算する第一トークン計算部とを含む。管理者装置は、マスタ秘密鍵ｘ，ｙ及びユーザ公開鍵ｇ１ａ，ｇ２ｂを用いて、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙを計算する第二トークン計算部を含む。検証者装置は、第一トークンｔｋｎ１又は第二トークンｔｋｎ２とタグｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖとを用いて、ｅ（ｔｋｎ１，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）又はｅ（ｔｋｎ２，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であるか計算するリンク計算部を含む。
【発明の効果】
【０００７】
検証者装置は、第一トークンｔｋｎ１及び第二トークンｔｋｎ２に対応するタグを特定することはできるが、第一トークンｔｋｎ１及び第二トークンｔｋｎ２に対応するユーザ公開鍵を特定することはできない。この点において、従来よりも匿名性が高くなる。
【０００８】
例えば、第一トークンｔｋｎ１及び第二トークンｔｋｎ２を受け取った検証者装置は、第一トークンｔｋｎ１及び第二トークンｔｋｎ２に対応するタグを持つユーザのサービスの利用を停止することはできるが、そのユーザが誰であるかを特定することはできない。
【図面の簡単な説明】
【０００９】
【図１】タグシステムの例を説明するためのブロック図。
【図２】管理者装置の例を説明するためのブロック図。
【図３】ユーザ装置の例を説明するためのブロック図。
【図４】検証者装置の例を説明するためのブロック図。
【図５】タグシステムの方法の例を説明するための流れ図。
【発明を実施するための形態】
【００１０】
以下、図面を参照してこの発明の一実施形態を説明する。
【００１１】
タグシステムは、図１に示すように、管理者装置１、ユーザ装置２、検証者装置３を例えば備える。
【００１２】
管理者装置１は、図２に示すように、記憶部１０、マスタ秘密鍵生成部１１、マスタ公開鍵生成部１２、ユーザ秘密鍵生成部１３、ユーザ公開鍵生成部１４及び第二トークン生成部１５を例えば備える。
【００１３】
管理者装置１のマスタ秘密鍵生成部１１は、マスタ秘密鍵ｍｔｓｋであるｘ，ｙ∈Ｚｐ＊を選択する（ステップＳ１１、図５）。ｘ，ｙは例えばランダムに選択される。このように、マスタ秘密鍵ｍｔｓｋは、ｘとｙの組（ｘ，ｙ）である。生成されたマスタ秘密鍵ｍｔｓｋ＝（ｘ，ｙ）は、マスタ公開鍵生成部１２及び第二トークン生成部１５に送信される。マスタ秘密鍵ｍｔｓｋ＝（ｘ，ｙ）は、秘密に保たれ、ユーザ装置２及び検証者装置３には公開されない。
【００１４】
ここで、ｐを所定の定数として、Ｚｐは、０以上ｐ未満の整数の集合である。Ｚｐ＊は、Ｚｐかつｐと互いに素な整数の集合である。
【００１５】
マスタ公開鍵生成部１２は、マスタ秘密鍵ｍｔｓｋ＝（ｘ，ｙ）を用いて、マスタ公開鍵ｍｔｐｋであるｇ１＝ｇ３ｘ，ｇ２＝ｇ３ｙ，ｇ３∈Ｇを生成する（ステップＳ１２）。このように、マスタ公開鍵ｍｔｐｋは、ｇ１とｇ２とｇ３の組（ｇ１，ｇ２，ｇ３）である。マスタ公開鍵生成部１２は、まずｇ３を群Ｇの中から選択する。そして、選択されたｇ３を用いて、ｇ３ｘを計算してその計算結果をｇ１とし、ｇ３ｙを計算してその計算結果をｇ２とする。生成されたマスタ公開鍵ｍｔｐｋ＝（ｇ１，ｇ２，ｇ３）は、ユーザ装置２及び検証者装置３に公開される。
【００１６】
ここで、Ｇ，ＧＴは位数ｐの群であり、これらの群Ｇ，ＧＴには、いわゆるペアリング関数ｅ：Ｇ×Ｇ→ＧＴが定義可能であるとする。
【００１７】
ユーザ秘密鍵生成部１３は、ユーザ秘密鍵ｕｔｓｋであるａ，ｂ∈Ｚｐ＊を選択する（ステップＳ１３）。ａ，ｂは例えばランダムに選択される。このように、ユーザ秘密鍵ｕｔｓｋは、ａとｂの組（ａ，ｂ）である。生成されたユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）は、ユーザ公開鍵生成部１４及びユーザ装置２に送信される。
【００１８】
ユーザ公開鍵生成部１４は、ユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）と、マスタ公開鍵ｍｔｐｋ＝（ｇ１，ｇ２，ｇ３）の中のｇ１及びｇ２とを用いて、ユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）を計算する（ステップＳ１４）。計算されたユーザ公開鍵は、第二トークン生成部１５及びユーザ装置２に送信される。
【００１９】
ユーザ装置２が複数ある場合には、複数のユーザ装置毎にユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）及びユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）が生成される。
【００２０】
ユーザ装置２は、図３に示すように、記憶部２０、乱数生成部２１、タグ生成部２２及び第一トークン生成部２３を例えば備える。
【００２１】
乱数生成部２１は、ｕ，ｖ∈Ｚｐ＊を選択する。ｕ，ｖは例えばランダムに選択される（ステップＳ２１）。選択されたｕ，ｖは、タグ生成部２２に送信される。
【００２２】
タグ生成部２２は、ｇ∈Ｇ、マスタ公開鍵ｍｔｐｋ＝（ｇ１，ｇ２，ｇ３）のｇ３、ユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）及びｕ，ｖを用いて、タグであるｇｕ，ｇｖ及び（ｇ３ａ＋ｂ）ｕ／ｖを計算する（ステップＳ２２）。このようにタグは、ｇｕとｇｖと（ｇ３ａ＋ｂ）ｕ／ｖの組（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）である。計算されたタグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）は、検証者装置３に送信される。
【００２３】
タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）は、ユーザ装置２に対応する情報である。例えば、あるサービスを利用するためのチケットや、電子署名として用いられる。同一のユーザから複数のタグが生成されてもよい。
【００２４】
タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）がユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）とリンクするかどうかを、ユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有していない者が判定することは難しい。すなわち、タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）が、ユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）に対応するユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有する者によって、生成されたかどうかを、ユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有していない者が判定することは難しい。それは、いわゆるＤＬＩＮ（Ｄｅｃｉｓｉｏｎ  Ｌｉｎｅｒ）問題の困難性に基づく。
【００２５】
検証者装置３は、図４に示すように、記憶部３０、リンク計算部３１を例えば含む。
【００２６】
検証者装置３は、タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）を有するユーザに対して、例えばサービスの利用の許可をしてもよいかの判断を行う。その際、検証者装置３は、タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）がユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有する者によって生成されたかどうかを確認するために、第一トークンｔｋｎ１をユーザ装置２に要求してもよい。この場合、検証者装置３は、第一トークンｔｋｎ１に基づいて、タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）がユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有する者によって生成されたと判定できた場合には、サービスの利用を許可する。
【００２７】
ユーザ装置２の第一トークン生成部２３は、マスタ公開鍵ｍｔｐｋ＝（ｇ１，ｇ２，ｇ３）の中のｇ３及びユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を用いて、第一トークンｔｋｎ１＝ｇ３ａ＋ｂを計算する。計算された第一トークンｔｋｎ１＝ｇ３ａ＋ｂは、検証者装置３に送信される。
【００２８】
検証者装置３のリンク計算部３１は、第一トークンｔｋｎ１＝ｇ３ａ＋ｂ及びタグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）を用いて、ｅ（ｔｋｎ１，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であるか計算する（ステップＳ３１）。ｅ（ｔｋｎ１，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であれば、タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）は第一トークンｔｋｎ１＝ｇ３ａ＋ｂとリンクしている、すなわち、タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）及び第一トークンｔｋｎ１＝ｇ３ａ＋ｂがユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有する者によって生成されたと判定することができる。
【００２９】
第一トークンｔｋｎ１＝ｇ３ａ＋ｂがユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）とリンクするかどうかを、ユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有していない者が判定することは難しい。すなわち、第一トークンｔｋｎ１＝ｇ３ａ＋ｂが、ユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）に対応するユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有する者によって、生成されたかどうかを、ユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有していない者が判定することは難しい。それは、いわゆるＤＬＩＮ（Ｄｅｃｉｓｉｏｎ  Ｌｉｎｅｒ）問題の困難性に基づく。
【００３０】
したがって、第一トークンｔｋｎ１＝ｇ３ａ＋ｂを受け取った検証者装置３は、タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）及び第一トークンｔｋｎ１が何れかのユーザ秘密鍵（ａ，ｂ）に基づいて生成されたということを知ることができるが、そのユーザ秘密鍵（ａ，ｂ）がどのユーザのものなのかを知ることはできない。
【００３１】
なお、管理者装置１が、あるタグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）を無効にしたい場合がある。この場合は、管理者装置１の第二トークン生成部１５は、マスタ秘密鍵ｍｔｓｋ＝（ｘ，ｙ）、及び、ユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）を用いて、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙを計算する（ステップＳ１６）。計算された第二トークンｔｋｎ２は、検証者装置３に送信される。ｇ１＝ｇ３１／ｘ及びｇ２＝ｇ３１／ｙであることを考慮すると、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙ＝ｇ３ａｇ３ｂ＝ｇ３ａ＋ｂであるため、第二トークンｔｋｎ２の値はｇ３ａ＋ｂとなる。
【００３２】
検証者装置３のリンク計算部３１は、第二トークンｔｋｎ２及びタグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）を用いて、ｅ（ｔｋｎ２，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であるか計算する（ステップＳ３２）。ｅ（ｔｋｎ２，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であれば、タグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）は第二トークンｔｋｎ２とリンクしており、第二トークンｔｋｎ２がマスタ秘密鍵ｍｔｓｋ＝（ｘ，ｙ）を有する者によって生成されたと判定することができる。この場合、検証者装置３は、ｅ（ｔｋｎ２，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）の関係を満たすタグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）を有する者にサービスの利用を認めない。
【００３３】
このように、マスタ秘密鍵ｍｔｓｋ＝（ｘ，ｙ）を有する管理者装置１は、任意のユーザに対応するタグを無効にすることができる。
【００３４】
第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙ＝ｇ３ａ＋ｂがユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）とリンクするかどうかを、ユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有していない者が判定することは難しい。すなわち、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙ＝ｇ３ａ＋ｂがどのユーザ公開鍵ｕｔｐｋ＝（ｇ１ａ，ｇ２ｂ）に対応するものであるのかを、ユーザ秘密鍵ｕｔｓｋ＝（ａ，ｂ）を有していない者が判定することは難しい。それは、いわゆるＤＬＩＮ（Ｄｅｃｉｓｉｏｎ  Ｌｉｎｅｒ）問題の困難性に基づく。
【００３５】
したがって、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙ＝ｇ３ａ＋ｂを受け取った検証者装置３は、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙ＝ｇ３ａ＋ｂに対応するタグ（ｇｕ，ｇｖ，（ｇ３ａ＋ｂ）ｕ／ｖ）を特定することができるが、第二トークンｔｋｎ２＝（ｇ１ａ）ｘ（ｇ２ｂ）ｙ＝ｇ３ａ＋ｂに対応するユーザ、すなわち無効にされたユーザを特定することはできない。
【００３６】
なお、上記の実施形態では、ユーザ装置２は、第一トークンｔｋｎ１＝ｇ３ａ＋ｂを検証者装置３に送信したが、第一トークンｔｋｎ１＝ｇ３ａ＋ｂについてゼロ知識証明をすることにより、ユーザ装置２が第一トークンｔｋｎ１＝ｇ３ａ＋ｂを検証者装置３に送信せずに、検証者装置３のリンク計算部３１がｅ（ｔｋｎ１，ｇｕ）＝ｅ（（ｇ３ａ＋ｂ）ｕ／ｖ，ｇｖ）であるか判定をしてもよい。同一のユーザに複数のタグがある場合に、第一トークンｔｋｎ１＝ｇ３ａ＋ｂを検証者装置３に渡してしまうと、検証者装置３は、第一トークンｔｋｎ１＝ｇ３ａ＋ｂに対応するタグを判定することにより、同一のユーザの複数のタグを知ることができてしまう。しかし、このように、第一トークンｔｋｎ１＝ｇ３ａ＋ｂについてゼロ知識証明をすることにより、検証者装置３により、同一のユーザの複数のタグが知られることがなくなる。
【００３７】
なお、上記の実施形態では、管理者装置１、ユーザ装置２及び検証者装置３の各部間でデータは直接送受信されていたが、データは記憶部１０，２０，３０を介してやり取りされてもよい。
【００３８】
管理者装置１をコンピュータによって実現する場合、管理者装置１の各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、管理者装置１の各部の処理機能がコンピュータ上で実現される。同様に、ユーザ装置２をコンピュータによって実現する場合、ユーザ装置２の各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、ユーザ装置２の各部の処理機能がコンピュータ上で実現される。同様に、検証者装置３をコンピュータによって実現する場合、検証者装置３の各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、検証者装置３の各部の処理機能がコンピュータ上で実現される。
【００３９】
これらのプログラムのそれぞれは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４０】
この発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４１】
また、上記の実施形態及び変形例を互いに組み合わせてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００４２】
１      管理者装置
１１    マスタ秘密鍵生成部
１２    マスタ公開鍵生成部
１３    ユーザ秘密鍵生成部
１４    ユーザ公開鍵生成部
１５    第二トークン生成部
２      ユーザ装置
２１    乱数生成部
２２    タグ生成部
２３    第一トークン生成部
３      検証者装置
３１    リンク計算部
【図１】
0005449123.tif 000002
【図２】
0005449123.tif 000003
【図３】
0005449123.tif 000004
【図４】
0005449123.tif 000005
【図５】
0005449123.tif 000006