(57)【要約】    【課題】  順応性のある匿名証明書システム及び通信ネットワーク上の証明方法を提供する。    【解決手段】  匿名証明書システムにおいて、ユーザは、信用ある機関からのルート証明を得て、ルート証明に基づいて匿名証明書を生成し、検証者へ匿名証明書を有する匿名の公開鍵を送る。検証者は、匿名証明書の使用を通じて、ユーザの匿名の公開鍵が信用ある機関によって証明されていることを確認する。匿名証明書は、検証者にユーザの本当の身元を見抜くことを可能にする情報を含んでいない。匿名証明書システムにより、信用ある機関は、ユーザのルート公開鍵のために一度だけ保証する。匿名の公開鍵がそれぞれ別個の匿名証明書を含む場合、ユーザは自身によって多数の匿名の公開鍵を生成することが可能である。【選択図】    図１７
2007089171.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワーク上でデータを証明するユーザのコンピュータ装置であって、
前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、
前記コンピュータ装置が、
前記ネットワークに接続された、前記信用ある機関の装置からルート証明を受け取るためのルート証明ユニット、
前記ルート証明ユニットに接続された、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するための匿名証明書生成ユニット、
前記匿名証明書生成ユニットに接続された、前記通信ネットワークに前記匿名証明書と共に前記ユーザデータを送信するための送信ユニットを備えることを特徴とするコンピュータ装置。
【請求項２】
前記匿名証明書は、立証者が前記ユーザの本当の身元を見抜くことを可能とする如何なる情報も含まないように生成されることを特徴とする請求項１に記載のコンピュータ装置。
【請求項３】
前記ユーザのデータが、前記ユーザの公開鍵を含むことを特徴とする請求の１に記載のコンピュータ装置。
【請求項４】
前記ユーザのデータに含まれる前記公開鍵が、唯一無比の公開鍵であることを特徴とする請求項３に記載のコンピュータ装置。
【請求項５】
前記ユーザのデータを含まれる前記公開鍵が、匿名の公開鍵であり、
前記コンピュータ装置が、前記送信ユニットに接続された、前記ユーザの複数の匿名の公開鍵を生成するための匿名公開鍵生成ユニットをさらに備え、
前記複数の匿名の公開鍵が前記ユーザの秘密鍵に対応していることを特徴とする請求項３に記載のコンピュータ装置。
【請求項６】
前記匿名公開鍵生成ユニットは、前記秘密鍵及びジェネレータから複数の匿名の公開鍵を生成し、前記秘密鍵と前記ジェネレータが予め定義されたグループに属することを特徴とする請求項５に記載のコンピュータ装置。
【請求項７】
前記ルート証明が、前記信用ある機関によって前記ユーザに発行されたルート証明書であることを特徴とする請求項１に記載のコンピュータ装置。
【請求項８】
前記ルート証明が、前記ユーザのグループ秘密鍵であり、前記匿名証明書が、前記ユーザのデータのグループ署名であることを特徴とする請求項１に記載のコンピュータ装置。
【請求項９】
前記ネットワークに接続された、前記ルート証明のための要求を生成し、かつ前記信用ある機関に要求を送信するためのルート証明要求ユニットをさらに備えることを特徴とする請求項１に記載のコンピュータ装置。
【請求項１０】
前記ネットワークに接続された、前記信用ある機関あるいは前記立証者と共に知識証明を実行するための検証ユニットをさらに備えることを特徴とする請求項１に記載のコンピュータ装置。
【請求項１１】
ユーザが通信ネットワーク上でデータを証明する方法であって、
前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、
前記信用ある機関からルート証明を受信するステップと、
前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するステップと、
前記立証者側に前記匿名証明書を含む前記ユーザのデータを送信するステップとを有することを特徴とする証明方法。
【請求項１２】
前記匿名証明書は、立証者が前記ユーザの本当の身元を見抜くことを可能とする如何なる情報も含まないように生成されることを特徴とする請求項１１に記載の証明方法。
【請求項１３】
前記ユーザのデータが、前記ユーザの公開鍵を含むことを特徴とする請求の１１に記載の証明方法。
【請求項１４】
前記ユーザのデータに含まれる前記公開鍵が、唯一無比の公開鍵であることを特徴とする請求項１３に記載の証明方法。
【請求項１５】
前記ユーザのデータを含まれる前記公開鍵が、匿名の公開鍵であり、
前記ユーザの複数の匿名の公開鍵を生成するステップをさらに有し、
前記複数の匿名の公開鍵が前記ユーザの秘密鍵に対応していることを特徴とする請求項１３に記載の証明方法。
【請求項１６】
複数の匿名の公開鍵が前記秘密鍵及びジェネレータから生成され、前記秘密鍵と前記ジェネレータが予め定義されたグループに属することを特徴とする請求項１５に記載の証明方法。
【請求項１７】
前記ルート証明が、前記信用ある機関によって前記ユーザに発行されたルート証明書であることを特徴とする請求項１１に記載の証明方法。
【請求項１８】
前記ルート証明が、前記ユーザのグループ秘密鍵であり、前記匿名証明書が、前記ユーザのデータのグループ署名であることを特徴とする請求項１１に記載の証明方法。
【請求項１９】
前記ネットワークに接続された、前記ルート証明のための要求を生成し、かつ前記信用ある機関に要求を送信するためのルート証明要求ユニットをさらに備えることを特徴とする請求項１１に記載の証明方法。
【請求項２０】
前記ネットワークに接続された、前記信用ある機関あるいは前記立証者と共に知識証明を実行するための検証ユニットをさらに備えることを特徴とする請求項１１に記載の証明方法。
【請求項２１】
通信ネットワーク上で証明書を処理する処理装置であって、
前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、
前記処理装置が、
システムパラメタを計算するためのシステムパラメータ計算ユニットと、
前記システムパラメータ計算ユニットに接続された、前記ユーザ及び前記立証者側によって共有されるシステムパラメタを発行するためのパラメータ発行ユニットと、
前記ネットワークに接続された、前記ユーザからルート証明要求を受け取るためのルート証明要求受信ユニットと、
前記ルート証明要求受信ユニット及び前記システムパラメータ計算ユニットに接続された、前記ルート証明要求に応じて前記ユーザのためのルート証明を生成するためのルート証明生成ユニットとを備え、
前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする処理装置。
【請求項２２】
前記ルート証明が、前記ユーザの公開鍵に対して発行されたルート証明書であることを特徴とする請求項２１に記載の処理装置。
【請求項２３】
前記ルート証明が、前記ユーザの匿名の公開鍵に対して発行されたルート証明書であることを特徴とする請求項２１に記載の処理装置。
【請求項２４】
前記ルート証明が、前記ユーザに対して発行されたグループ秘密鍵であることを特徴とする請求項２１に記載の処理装置。
【請求項２５】
前記ルート証明生成ユニットに接続された、前記ルート証明要求について識別検査を行なうための検査ユニットをさらに備えることを特徴とする請求項２１に記載の処理装置。
【請求項２６】
前記ネットワークに接続された、前記ルート証明に基づいて前記立証者側から受信した匿名証明書の所有者の身元を調査するための調査ユニットをさらに備えることを特徴とする請求項２１に記載の処理装置。
【請求項２７】
通信ネットワーク上で証明書を処理する処理方法であって、
前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、
システムパラメタを計算するステップと、
前記ユーザ及び前記立証者側によって共有されるシステムパラメタを発行するステップと、
前記ユーザからルート証明要求を受け取るステップと、
前記ルート証明要求に応じて前記ユーザのためのルート証明を生成するステプを有し、
前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする処理方法。
【請求項２８】
前記ルート証明が、前記ユーザの公開鍵に対して発行されたルート証明書であることを特徴とする請求項２７に記載の処理方法。
【請求項２９】
前記ルート証明が、前記ユーザの匿名の公開鍵に対して発行されたルート証明書であることを特徴とする請求項２７に記載の処理方法。
【請求項３０】
前記ルート証明が、前記ユーザに対して発行されたグループ秘密鍵であることを特徴とする請求項２７に記載の処理方法。
【請求項３１】
前記ルート証明要求を受信した後、前記ルート証明要求について識別検査を実行することを特徴とする請求項２７に記載の処理方法。
【請求項３２】
前記ルート証明に基づいて前記立証者側から受信した匿名証明書の所有者の身元を調査するステプをさらに有することを特徴とする請求項２７に記載の処理方法。
【請求項３３】
通信ネットワーク上のユーザのための匿名証明書システムであって、
前記ネットワークには信用ある機関の装置を含み、
前記ネットワークに接続された、前記信用ある機関の装置からルート証明を受け取るためのルート証明ユニット、
前記ルート証明ユニットに接続された、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するための匿名証明書生成ユニット、
前記匿名証明書生成ユニットに接続された、前記通信ネットワークに前記匿名証明書と共に前記ユーザデータを送信するための送信ユニット
前記通信ネットワークに接続された、受信した匿名証明書によってユーザのデータを検査するための前記立証者側ユニットを備えることを特徴とする匿名証明書システム。
【請求項３４】
前記匿名証明書は、立証者が前記ユーザの本当の身元を見抜くことを可能とする如何なる情報も含まないように生成されることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項３５】
前記ユーザのデータが、前記ユーザの公開鍵を含むことを特徴とする請求の３３に記載の匿名証明書システム。
【請求項３６】
前記ユーザのデータに含まれる前記公開鍵が、唯一無比の公開鍵であることを特徴とする請求項３５に記載の匿名証明書システム。
【請求項３７】
前記ユーザのデータを含まれる前記公開鍵が、匿名の公開鍵であり、
前記システムが、前記送信ユニットに接続された、前記ユーザの複数の匿名の公開鍵を生成するための匿名公開鍵生成ユニットをさらに備え、
前記複数の匿名の公開鍵が前記ユーザの秘密鍵に対応していることを特徴とする請求項３５に記載の匿名証明書システム。
【請求項３８】
前記匿名公開鍵生成ユニットは、前記秘密鍵及びジェネレータから複数の匿名の公開鍵を生成し、前記秘密鍵と前記ジェネレータが予め定義されたグループに属することを特徴とする請求項３７に記載の匿名証明書システム。
【請求項３９】
前記ルート証明が、前記信用ある機関によって前記ユーザに発行されたルート証明書であることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４０】
前記ルート証明が、前記ユーザのグループ秘密鍵であり、前記匿名証明書が、前記ユーザのデータのグループ署名であることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４１】
前記立証者側ユニットが、前記匿名証明書および前記ユーザのデータについて照合を行なうための照合モジュールをさらに備えることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４２】
前記立証者側ユニットが、
前記照合モジュールに接続された、正確に検査されたデータを格納するメモリと、
前記メモリと前記照合モジュールに接続された、受信した前記ユーザのデータを前記格納したデータと比較する比較モジュールをさらに備えることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４３】
前記立証者側ユニットに接続された、前記ルート証明に基づいて前記立証者側ユニットから受信した匿名証明書の所有者の身元を調査するための調査ユニットをさらに備えることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４４】
通信ネットワーク上で匿名証明書によってユーザのデータを証明する方法であって、
前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、
前記信用ある機関から前記ユーザにルート証明を発行するステップと、
ユーザによる前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するステップと、
前記立証者側に前記匿名証明書を含む前記ユーザのデータを送信するステップを有し、
前記立証者側が、前記匿名証明書によって前記ユーザのデータを検査することを特徴とする証明方法。
【請求項４５】
前記匿名証明書は、立証者が前記ユーザの本当の身元を見抜くことを可能とする如何なる情報も含まないように生成されることを特徴とする請求項４４に記載の証明方法。
【請求項４６】
前記ユーザのデータが、前記ユーザの公開鍵を含むことを特徴とする請求の４４に記載の証明方法。
【請求項４７】
前記ユーザのデータに含まれる前記公開鍵が、唯一無比の公開鍵であることを特徴とする請求項４６に記載の証明方法。
【請求項４８】
前記ユーザのデータを含まれる前記公開鍵が、匿名の公開鍵であり、
前記ユーザの複数の匿名の公開鍵を生成するステップをさらに有し、
前記複数の匿名の公開鍵が前記ユーザの秘密鍵に対応していることを特徴とする請求項４６に記載の証明方法。
【請求項４９】
前記秘密鍵及びジェネレータから複数の匿名の公開鍵を生成し、前記秘密鍵と前記ジェネレータが予め定義されたグループに属することを特徴とする請求項４８に記載の証明方法。
【請求項５０】
前記ルート証明の発行が、前記ユーザの公開鍵に対してルート証明書を発行するステップを含むことを特徴とする請求項４４に記載の証明方法。
【請求項５１】
前記ルート証明の発行が、前記ユーザに対してグループ秘密鍵を発行するステップを含み、
少なくとも１つの匿名証明書の生成が、前記ユーザのデータのグループ署名を生成するステップを含むことを特徴とする請求項４４に記載の証明方法。
【請求項５２】
前記立証者側が、前記ユーザと知識証明を行なうことにより前記匿名証明書及び前記ユーザのデータを検査することを特徴とする請求項４４に記載の証明方法。
【請求項５３】
前記立証者側による前記匿名証明書及び前記ユーザのデータの検査が、
前記立証者側によって正確に検査されたデータを格納するステップ、
前記格納データを前記ユーザから受信したユーザのデータと比較するステップ、
前記ユーザのデータが前記記憶データのうちの１つと一致すれば、前記ユーザと前記ユーザのデータに関する知識証明を実行するステップ、
前記ユーザのデータが前記記憶データのうちの１つと一致しない場合、前記匿名証明書及び前記ユーザのデータについて照合を実行するステップとを有することを特徴とする請求項４４に記載の証明方法。
【請求項５４】
前記ルート証明に基づいて前記立証者側から受信した匿名証明書の所有者の身元を調査するステプをさらに有することを特徴とする請求項４４に記載の処理方法。
【請求項５５】
ユーザが通信ネットワーク上でデータを証明するためにコンピュータ上で実行される証明プログラムであって、
前記コンピュータに、
前記信用ある機関からルート証明を受信する処理と、
前記ルート証明に基づいて少なくとも１つの匿名証明書を生成する処理と、
前記立証者側に前記匿名証明書を含む前記ユーザのデータを送信する処理を実行させることを特徴とする証明プログラム。
【請求項５６】
前記データが匿名の公開鍵であることを特徴とする請求項５５に記載の証明プログラム。
【請求項５７】
ユーザが通信ネットワーク上でデータを証明するためにコンピュータ上で実行される証明プログラムであって、
前記コンピュータに、
システムパラメタを計算する処理と、
前記ユーザ及び前記立証者側によって共有されるシステムパラメタを発行する処理と、
前記ユーザからルート証明要求を受け取る処理と、
前記ルート証明要求に応じて前記ユーザのためのルート証明を生成する処理を実行させ、
前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする証明プログラム。
【請求項５８】
前記ルート証明が、前記ユーザの匿名の公開鍵についてのルート証明書であることを特徴とする請求項５７に記載の証明プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ通信ネットワークセキュリティに関し、特に、プライバシーを保護する通信システム及びその通信方法に関する。
【背景技術】
【０００２】
現在、公開鍵暗号方式は広く使用される。従来、多くの公開鍵の暗号化及び復号化の技術は、プライバシーの場合と同程度のセキュリティを容易に提供することが可能である。例えば、Rivestらによる米国特許4,405,829号、及びEI
Gamalらによる分離対数に基づいた公開鍵暗号方式および署名スキーム(Tahir EIGamal. A public-key cryptosystem and
a signature scheme based on discrete logarithms.  Advances in Cryptology Proceedings of CRYPTO 84, pages
10-18, 1985)に開示された技術は、当該技術分野で広く知られた技術である。上記Rivestによる特許およびEI  Gamalの技術を引用して説明する。
【０００３】
RSA方式やEI Gamalのような従来の公開鍵暗号方式によって安全に他者と通信するためには、ユーザは外部に自身の公開鍵を公開することが要求される。しかし、多くの場合、ユーザは、1つの公開鍵と秘密鍵のペア、すなわち、１つの公開鍵とそれに対応する唯一の秘密鍵とを所有するだけである。公開鍵暗号方式のこの従来の簡易な使用法は、ユーザの公開鍵をユーザの識別情報として適切に機能させるとという偶発的な結果を生じる。それは、たとえ十分に計画された他のプライバシー保護基準のみならずこの種の公開鍵暗号方式によってユーザに関するプライバシーが保護されるとしても、悪意ある者が、唯一の公開鍵についての使用パターンに基づいてユーザによって公表された情報を収集して観察することを通じて、保護されているユーザの活動を把握することが依然可能なことを意味する。
【０００４】
RSA方式及びEI  Gamalによって示されているような従来の公開鍵暗号方式の範囲内で、ユーザが、自身の単一の公開鍵によって自身のプライバシーがあばかれるかもしれないと懸念する場合、１つの可能な解決策は、いくつかの異なる公開鍵を所有し、各公開鍵を異なる通信者に用心して公開することを関係者に要請することである。
【０００５】
多くの公開鍵ペアの所有に加えて、Watersらは、ユーザが単一の秘密鍵に対応する幾つかの公開鍵を同時に所有することができるようにする唯一無比の公開鍵スキーム（仕組み）を実現するために、Ei
Gamalによる暗号化方式を用いる方法を提案している。B.R.Waters、E.W.Felten、A.Sahai、「唯一無比の公開鍵を介した受信者の秘匿化（Receiver
Anonymity via Incomparable Public keys）」、CCS'03、Washigton  DC、USA、pp.112〜121) (以下に、Waters)を参照。上記Watersに開示される技術を引用して説明する。
【０００６】
上述したように、ユーザは数個の公開鍵を所有してもよい。しかしながら、多くの場合、人物Ａが公開鍵を得る場合、誰か他の者が公開鍵を証明しなければならない。例えば、公開鍵はよく知られている証明書機関（Ｃｅｒｔｉｆｉｃａｔｅ  Ａｕｔｈｏｒｉｔｙ）（ＣＡ）で証明することが可能であるし、或いはその人物の友人Ｃによって証明することが可能である。第３の人物Ｂが公開鍵とその証明書を見る場合、ＢがＣＡを信用し、或いはＢ友人Ｃを信用するいずれの場合でも、人物はその公開鍵を信用する。
【０００７】
ユーザが数個の公開鍵を所有する時に、それらの公開鍵を証明する１つの可能な方法は、図２５に示されるように、それらの公開鍵を証明してくれるようにＣＡに依頼することである。ＣＡは全ての証明書要求を全てオンラインで処理するので、ＣＡに非常に高い能力が必要とされ、所有権とメンテナンスの点からコストが増大している。ネットワーク上のユーザがそれぞれ多数の公開鍵を所有する場合、そのようなコストがさらに増大する。
【０００８】
他の可能性は、図２６に示されるように、公開鍵の各々を証明してくれるように何人かの友人に依頼することである。しかしながら、これはユーザのプライバシー保護と相容れない。それだけでなく、公開鍵を証明してくれるように友人に依頼することは非能率的でかつ効果がないだけでなく、多くのビジネスの場面において信用されない。
【０００９】
公開鍵の検証に加えて、ＣＡを中心にした解決方法及び友人による証明方法からなる方法の上述した欠点は、数個の利用者データを証明する必要のある他の多くの状況にも存在する。
【特許文献１】米国特許第４，４０５，８２９号
【非特許文献１】EI Gamalらによる分離対数に基づいた公開鍵暗号方式および署名スキーム(Tahir EIGamal. A public-keycryptosystem and a signature scheme based on discrete logarithms.  Advances in Cryptology Proceedings ofCRYPTO 84, pages 10-18, 1985)
【非特許文献２】B.R.Waters、E.W.Felten、A.Sahai、「唯一無比の公開鍵を介した受信者の秘匿化（ReceiverAnonymity via Incomparable Public keys）」、CCS'03、Washigton  DC、USA、pp.112〜121)
【非特許文献３】応用暗号学のハンドブック（Handbook of Applied Cryptography）(http://www.cacr.math.uwaterloo.ca/hac/)
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、順応性のある匿名証明書システム及び通信ネットワーク上の証明方法を提供する。
【課題を解決するための手段】
【００１１】
本発明によれば、通信ネットワーク上でデータを証明するユーザのコンピュータ装置であって、前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、前記コンピュータ装置が、前記ネットワークに接続された、前記信用ある機関の装置からルート証明を受け取るためのルート証明ユニット、前記ルート証明ユニットに接続された、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するための匿名証明書生成ユニット、前記匿名証明書生成ユニットに接続された、前記通信ネットワークに前記匿名証明書と共に前記ユーザデータを送信するための送信ユニットを備えることを特徴とする。
【００１２】
他の本発明によれば、ユーザが通信ネットワーク上でデータを証明する方法であって、前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、前記信用ある機関からルート証明を受信するステップと、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するステップと、前記立証者側に前記匿名証明書を含む前記ユーザのデータを送信するステップとを有することを特徴とする。
【００１３】
さらに他の本発明によれば、通信ネットワーク上で証明書を処理する処理装置であって、前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、前記処理装置が、システムパラメタを計算するためのシステムパラメータ計算ユニットと、前記システムパラメータ計算ユニットに接続された、前記ユーザ及び前記立証者側によって共有されるシステムパラメタを発行するためのパラメータ発行ユニットと、前記ネットワークに接続された、前記ユーザからルート証明要求を受け取るためのルート証明要求受信ユニットと、前記ルート証明要求受信ユニット及び前記システムパラメータ計算ユニットに接続された、前記ルート証明要求に応じて前記ユーザのためのルート証明を生成するためのルート証明生成ユニットとを備え、前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする。
【００１４】
さらに他の本発明によれば、通信ネットワーク上で証明書を処理する処理方法であって、前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、システムパラメタを計算するステップと、前記ユーザ及び前記立証者側によって共有されるシステムパラメタを発行するステップと、前記ユーザからルート証明要求を受け取るステップと、前記ルート証明要求に応じて前記ユーザのためのルート証明を生成するステプを有し、前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする。
【００１５】
さらに他の本発明によれば、通信ネットワーク上のユーザのための匿名証明書システムであって、前記ネットワークには信用ある機関の装置を含み、前記ネットワークに接続された、前記信用ある機関の装置からルート証明を受け取るためのルート証明ユニット、前記ルート証明ユニットに接続された、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するための匿名証明書生成ユニット、前記匿名証明書生成ユニットに接続された、前記通信ネットワークに前記匿名証明書と共に前記ユーザデータを送信するための送信ユニット前記通信ネットワークに接続された、受信した匿名証明書によってユーザのデータを検査するための前記立証者側ユニットを備えることを特徴とする。
【００１６】
さらに他の本発明によれば、通信ネットワーク上で匿名証明書によってユーザのデータを証明する方法であって、前記ネットワークには信用ある機関の装置と少なくとも１つの認証者側の装置を含み、前記信用ある機関から前記ユーザにルート証明を発行するステップと、ユーザによる前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するステップと、前記立証者側に前記匿名証明書を含む前記ユーザのデータを送信するステップを有し、前記立証者側が、前記匿名証明書によって前記ユーザのデータを検査することを特徴とする。
【００１７】
さらに他の本発明によれば、ユーザが通信ネットワーク上でデータを証明するためにコンピュータ上で実行される証明プログラムであって、前記コンピュータに、前記信用ある機関からルート証明を受信する処理と、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成する処理と、前記立証者側に前記匿名証明書を含む前記ユーザのデータを送信する処理を実行させることを特徴とする。
【００１８】
さらに他の本発明によれば、ユーザが通信ネットワーク上でデータを証明するためにコンピュータ上で実行される証明プログラムであって、前記コンピュータに、システムパラメタを計算する処理と、前記ユーザ及び前記立証者側によって共有されるシステムパラメタを発行する処理と、前記ユーザからルート証明要求を受け取る処理と、前記ルート証明要求に応じて前記ユーザのためのルート証明を生成する処理を実行させ、前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、匿名の公開鍵が信用された主体によって証明される匿名証明書によって保証される場合、ユーザは信頼できる匿名の公開鍵を生成することが可能であることが、上述した説明から理解できる。ユーザ・プライバシ保護の機能は完全に施される。ユーザは、自身による別個の匿名の公開鍵だけでなく、自身による別個の匿名証明書を生成する。本発明による実施の形態において、ＣＡの介在は最小限である。よって、信用された主体の負荷の軽減化を実現することが可能である。さらに、匿名証明書はＣＡ或いはグループ管理者レベルで追跡可能であるので、ユーザが匿名性を乱用するのは不可能である。
【発明を実施するための最良の形態】
【００２０】
（秘匿化した公開鍵）
この出願は、この出願は、Ｋｅ  ＺＥＮＧ及びTomoyuki FUJITAによって発明された新たしい匿名の公開鍵（Ａｎｏｎｙｍｏｕｓ  Ｐｕｂｌｉｃ  Ｋｅｙ）（ＡＰＫ）方式に関するものである。ＡＰＫ方式の詳細な内容は、出願中の中国特許出願No.
200410090903.X（出願日：２００４年１１月１０日、出願人：NEC (China) Co., Ltd、発明の名称：「セキュリティ通信システムにおける秘匿化した公開鍵を生成する方法、装置及びシステム」）に記載されている。
【００２１】
まず、ＡＰＫの技術的解決方法について以下に説明する。
【００２２】
上述したように、ユーザはいくつかの公開鍵を所有することを欲する可能性がある。別個の公開鍵がそれぞれ対応する別個の秘密鍵を有する複数の公開鍵ペアを使用することによって、従来の公開鍵暗号方式では、ある程度までプライバシー問題を軽減することが可能である。しかしながら、公開鍵の数が増加するに伴って、個人のための公開鍵ペアの管理コストが増大する。
さらに、秘密鍵の数の増加に伴って、秘密鍵の紛失或いは露見といったセキュリティ上の危険性が増加する。
【００２３】
EI Gamalの暗号方式による公開鍵を構成するための種々のジェネレータを用いることによって、新しい公開鍵を生成するけれども、それは計算における最適化を困難にする。例えば、（ｇ，  ｇａ）と（ｈ，  ｈａ）がWatersの唯一無比の唯一無比の公開鍵方式（Ｉｎｃｏｍｐａｒａｂｌｅ  Ｐｕｂｌｉｃ  Ｋｅｙｓ  Ｓｃｈｅｍｅ）によって生成された異なる公開鍵であると仮定する。ここで、ｇとｈは、異なるジェネレータである。従来、EI
Gamalによる暗号化方式は、単一のジェネレータだけを使用する。従って、複数のジェネレータをオフラインで計算させることができ、かつ複数のジェネレータについて１つのテーブルだけを維持すればよいという利点が得られる。Watersによるスキームは、複数の異なるジェネレータについての数種類のテーブルの維持、及びオンラインによる計算を要求するため、計算の最適化及び管理コストの何れの点においても好ましくない。
【００２４】
発明者等は、匿名の公開鍵（Ａｎｏｎｙｍｏｕｓ  Ｐｕｂｌｉｃ  Ｋｅｙ）（ＡＰＫ）方式を見いだした。ＡＰＫ手法は、エンドユーザが一人で多数の公開鍵を生成することが可能であり、かつ１つの秘密鍵だけを保持することになっているという点で独特である。
【００２５】
ＡＰＫ方式について、図１〜図７を参照して説明する。
【００２６】
明細書全体にわたって、用語「グループ」は、他の定義が示されない限り以下のように定義される数学的な概念を指す。
【００２７】
グループ（Ｇ，  ◇）は、次の３つの公理を満たすＧにおけるブール演算◇を備えた集合Ｇから成る。
【００２８】
（１）  グループ演算は結合である。すなわち、Ｇのすべての要素ａ，ｂ，ｃについて、ａ◇（ｂ◇ｃ）＝（ａ◇ｂ）◇Ｃを満たす。
【００２９】
（２）  Ｇのすべての要素ａについてａ◇ｅ＝ｅ◇ａ＝ａを満たすＧの単位元eがある。
【００３０】
（３）  Ｇの各要素ａについて、ａ◇ａ−１＝ａ−１◇ａ＝ｅを満たすaの逆関数と呼ばれるＧの要素ａ−１が存在する。
【００３１】
例えば、追加の演算を備えた整数Zの集合は、あるグループを形成する。
【００３２】
単位元は“０”であり、整数ａの逆関数は整数ａ−１である。
【００３３】
より詳細に関しては、オンラインで利用可能な応用暗号学のハンドブック（Handbook of Applied Cryptography）を参照(http://www.cacr.math.uwaterloo.ca/hac/)。
【００３４】
本発明による通信システムは、複数の端末装置及び複数の通信チャネルを備える。
【００３５】
図１は、本発明の一実施例を示すブロック図である。
【００３６】
図１において、端末装置Ａは、複数のセッションによって端末装置ａと通信する。端末装置Ａには、端末装置ａに情報を送るための少なくとも1つの通信チャネルが存在する。
【００３７】
そのセッションは、１つあるいは複数の通信チャネルを利用する。
【００３８】
端末装置ａは、端末装置Ａに情報を送るために同じ通信チャネルを使用してもよいし、使用しなくてもよい。
【００３９】
通信チャネルを通じて、端末装置のＡは、異なる通信セッション毎に、端末装置ａに各種の公開鍵Ｅａ〜Ｅｚを通知するが、その秘密鍵ｘについては秘匿する。
【００４０】
端末装置ａは、必要に応じて端末装置Ａに対していくつかの異なる公開鍵を通知する点で、端末装置Ａと同様である。
【００４１】
図１に示されるように、異なるセッション毎に異なる公開鍵を生成することにより、端末装置ａあるいは任意の第三者が、端末装置Ａの活動パターンを推測することは事実上不可能である。
【００４２】
例えば、電子オークション環境では、異なる公開鍵が各セッション毎に生成されるため、端末装置Ａからのユーザは、自身の入札パタ−ン及び戦略が他者によって推測及び分析されるのを防ぐことができる。
【００４３】
また、図２は、本発明の他の実施例を示すブロック図である。
【００４４】
図２において、端末装置Ａは、端末装置ａから端末装置ｚの複数の端末装置と通信する。
【００４５】
端末装置Ａと各々の通信先との間で使用される通信チャネルは、同じでも、同じではなくてもよい。
【００４６】
図２の左側に示されるように、通信チャネルを通じて、端末装置Ａは、異なる公開鍵Ｅａ〜Ｅｚを他の端末装置、すなわち、端末装置ａ，端末装置ｂ，・・・端末装置ｚにそれぞれ通知する。
【００４７】
この場合、端末装置Ａと端末装置ａ〜端末装置ｚとの間に、「１対複数」の関係があるといえる。上記公開鍵の通知は様々な方法で実現することができる。
【００４８】
例えば、公開鍵と一緒に明らかにされる他の情報があってもよいし、あるいは、公開鍵が電子メールか証明書に組み込まれてもよい。
【００４９】
また、端末装置ａ〜端末装置ｚは、受信した公開鍵で暗号化される情報を端末装置Ａに送るために、端末装置ａ〜端末装置ｚの各々が端末装置Ａからの公開鍵を受け取る通信チャネルと同一の通信チャネルを使用してもよいし、使用しなくてもよい。
【００５０】
上述の場合と同様に、端末装置Ａは、自身の秘密鍵ｘを秘密にする。
【００５１】
同様に、端末装置ａ〜端末装置ｚは、必要に応じて、端末装置Ａに対していくつかの異なる公開鍵を通知する点で、端末装置Ａと同じである。
【００５２】
図２の右側に示すように、端末装置ａ〜ｚは、それぞれ自身の公開鍵Ｅａ〜Ｅｚを端末装置Ａに通知する。
【００５３】
この場合、端末装置ａ〜ｚと端末装置のＡとの間に、「複数対１」の関係があるといえる。
【００５４】
図３は、図１及び図２に示された通信システムに参加する送信側と受信側の間の好適な通信セッション例を示す。
【００５５】
図３において、送信側が受信側に公開鍵を公表しようとする度に、送信側は、既存の公開鍵のプールから１つの公開鍵を選択する（ステップＳ３２）か、もしくは新しい公開鍵を生成する（ステップＳ３３）かを決定する（ステップＳ３１）。
【００５６】
その後、送信側は受信側に対して公開鍵を送信する（ステップＳ３４）。
【００５７】
受信側は、送信すべきメッセージがある場合(ステップＳ３５)には、送信側からの公開鍵を認識して(ステップＳ３６)、メッセージを暗号化しその暗号化されたメッセージを送信側に送る(ステップＳ３７)。
【００５８】
最後に、送信側は、受信した暗号化されたメッセージを解読し(ステップＳ３８)、受信側から送信されたオリジナルのメッセージを復元する。
【００５９】
なお、受信側が暗号化されたメッセージを送信側に送信することを欲する以前に、受信側が送信側から公開鍵を予め受け取っていることも想定される。
【００６０】
既存の鍵と無関係に、送信側が常に異なる公開鍵を生成する（ステップＳ３３）ように構成されていてもよい。
【００６１】
しかしながら、当業者であれば分かるように、既存の鍵の操作はゼロから公開鍵を計算するほど集中的な計算を必要とないので、既存の公開鍵のプールを使用することは、計算のオーバヘッドを著しく軽減する。
【００６２】
送信機が自身の公開鍵を受信機へ最初に送るため、図３の送信機及び受信機が便宜的にそのように示されていることに留意すべきである。
【００６３】
一旦受信機が送信機からの公開鍵を保持すれば、その受信機が暗号化されたメッセージを受信側である送信機に送る場合、その受信機は実際には送信機となる。
【００６４】
２つの端末装置間の典型的な相互の通信セッションにおいて、上記役割は、セッションの間頻繁に逆転する。
【００６５】
ここで、図４を参照すると、本発明による公開鍵−秘密鍵のペアに基づいた通信セッションにおける送信機と受信機の好適な機能ブロック図が示されている。
【００６６】
ここで、送信機４１は、少なくとも、通信チャネルを処理する送信装置４３及び受信装置４５と、暗号文の解読を行う復号化装置４７と、公開鍵を生成する公開鍵生成装置４９とを備える。
【００６７】
受信機４２は、少なくとも、送信装置４４と、受信装置４６と、プレーンテキストのような送信される情報の暗号化を行うための暗号化装置４８とを備える。
【００６８】
送信機４１は、複数の公開鍵を受信機４２に公開してもよいし、送信機４１と受信機４２の間に複数のセッションがある場合、各セッションがそれぞれ送信機４１の異なる公開鍵を公開してもよい。
【００６９】
また、送信機４１は、受信機として動作する場合、さらに暗号化装置４８を備える。
【００７０】
同様に、受信機４２は、送信機として動作する場合、さらに復号化装置４７及び公開鍵生成装置４９を備える。
【００７１】
図４に示す暗号化装置４８及び復号化装置４７については、どちらもデータ通信と暗号化の分野においてよく知られているものである。
【００７２】
公開鍵生成装置４９について、以下に示す図５においてさらに詳細に説明する。
【００７３】
図５を参照すると、制御装置５５は、鍵を管理する処理だけでなく公開鍵を生成する処理を制御する。
【００７４】
記憶部５４は、秘密鍵、生成された公開鍵、受信した公開鍵及び制御装置５５によって要求される他のデータを格納する。
【００７５】
なお、公開鍵生成装置４９で使用される記憶部５４は、オンチップレジスタ、ＲＯＭ及びＲＡＭのような情報を格納することが可能な全ての装置によって実現することができる。
【００７６】
公開鍵生成装置４９は、受信した暗号文及び解読における中間で出力されるデータを格納するために、記憶部５４を復号化装置４７と共有することも可能である。
【００７７】
公開鍵生成装置４９の他の構成要素については後述する。
【００７８】
図５においては、「グループ」演算がグループ指数演算子５７によって処理される。
【００７９】
「グループ」演算を別のグループ演算子によって処理する公開鍵生成装置４９の他の実施例も可能である。
【００８０】
次に、本発明に従って秘匿化された公開鍵(“ＡＰＫ”)を生成する、図４及び図５に示す公開鍵生成装置４９の処理について説明する。
【００８１】
図６は、ＡＰＫ−秘密鍵ペアを生成するための典型的な処理の流れを示す。
【００８２】
まず、グループＧが、グループ選択手段５１によって選択される（ステップＳ６０）。
【００８３】
例えば、コンピュータには、様々の適切なグループを表す様々なデータを格納するメモリが備えらえている。
【００８４】
制御装置５５による管理のもと、グループ選択手段５１は、グループを示すデータの選択によって１つのグループを選択する。
【００８５】
実際の運用においては、コンピュータ上で動作可能で、そのようなサービスを提供するいくつかの関数ライブラリの製品が既に提供されている。
【００８６】
本発明を実施するアプリケーションプログラムは、いくつかの特定のパラメータと共に、上記のようなライブラリによって提供される特別の関数を呼び出すことも可能である。そして、呼び出された関数が、要求されたグループを返す。
【００８７】
本実施例において、グループＧは有限の巡回グループであり、そのグループＧの位数はｎである。また、位数ｎは正整数である。
【００８８】
有限の巡回グループＧの候補は以下のものを含むが、これらに限定されるものではない。
【００８９】
（１）有限体Ｆｑ１における楕円曲線上の点からなるグループ
【００９０】
（２）有限体Ｆｑ２の乗法グループＦｑ２、ただし、ｑ２＝ｐｍ１であり、ｍ１は正整数、Ｐは素数
【００９１】
（３）Ｚｎ１のグループ、ただし、ｎ１は合成整数
【００９２】
（４）Ｚｎ２の乗法グループ、ただし、ｎ２は素数。
【００９３】
上記の４つの典型的な種類のグループにおいて、最初のグループは、最良のセキュリティパフォーマンスを有しており、一方、後の３つのグループは、当該技術分野において一般的に用いられている。
【００９４】
グループＧの「有限の巡回」性が、グループ指数演算の結果がグループＧへマッピングされることを示している。しかし、そのマッピング方法はグループ毎に変わってもよい。さらに、それは、ジェネレータ（生成子）が存在することを示している。
【００９５】
その後、部分グループ選択手段５２は、ｍ≦ｎである位数ｍのグループＧの部分グループを選択する(ステップＳ６１)。
【００９６】
位数ｍとして素数が選択される場合、好ましいセキュリティパフォーマンスが得られる。
【００９７】
グループＧ自身が部分グループとして選択される場合があることに留意する必要がる。これは、ｍ＝ｎの場合である。
【００９８】
他の実施例として、グループＧが後に決定されるか又は選択されるという前提の場合には、部分グループの選択を省略することが可能である。それは、グループＧが数学的にグループＧ自身の部分グループであるため、グループＧ自身が部分グループとして暗黙に選択されていることを意味する。
【００９９】
すなわち、グループＧ自身が部分グループとして選択されている場合(ｍ＝ｎとなる場合)、そのような選択は見かけ上実施されない。
【０１００】
もちろん、部分グループの選択を省略する場合には、図５に示す部分グループ選択手段５２も省くことが可能である。
【０１０１】
次いで、整数選択手段５６は、秘密鍵ｘとしてｘが１＜｜ｘ｜＜ｍを満たすような整数を選択する(ステップＳ６２)。
【０１０２】
簡潔のため、ここでは、１つの秘密鍵から複数の公開鍵を生成する方法について主に説明するが、１つの端末装置が複数の秘密鍵を備えていることも考えられる。
【０１０３】
その後、ジェネレータ選択手段５３は、グループＧのジェネレータｇを選択して決定する（ステップＳ６３）。グループＧが有限の巡回グループである場合、常に少なくとも一つのジェネレータを有している。
【０１０４】
ジェネレータｇと秘密鍵ｘの選択は、互いに独立して行われることに留意する。
【０１０５】
すなわち、ステップＳ６２はステップＳ６３より前に説明されているが、それらの処理の順序は反対でもよいし、あるいは、それらの処理が並行して行われてもよい。
【０１０６】
Ｇ，ｍ，ｘ及びｇの選択の後、整数ｒが、制御装置５５の管理のもとで新しい公開鍵を生成するための、０＜｜ｒ｜＜ｍを満たす指標として選択される(ステップＳ６４)。
【０１０７】
Ｇ，ｍ，ｘ，ｇ及びｒの選択と共に、新しい公開鍵が、ｙ１＝ｇｒの演算、次に、ｙ２＝ｙ１ｘの演算によって生成される(ステップＳ６５)。
【０１０８】
その後、公開鍵（ｙ１，  ｙ２）は、暗号化のために受信機に公開される(ステップＳ６６)。
【０１０９】
もちろん、公開鍵と一緒に公開される他の情報があってもよい。
【０１１０】
ｇ，ｘ及びｒの選択は、それらの選択において連続性や依存関係が要求されない点に留意する。すなわち、そのような選択のステップＳ６２，Ｓ６３，Ｓ６４は任意の順番で、連続してあるいは同時に実行することが可能である。
【０１１１】
なお、ｇ，ｘ及びｒの選択は、任意にあるいは要求されるいくつかの基準に従ってなされてもよい。
【０１１２】
他方、前述の手順のうちのいくつかは制御装置５５によって省略され、どこか他所で実行されるかもしれない。
【０１１３】
例えば、グループＧ及び部分グループの選択手順を、信頼ある組織である第三者に割り当てることもできる。
【０１１４】
従って、グループ及び部分グループが外部的に決定されるので、制御装置５５はグループ及び部分グループを選択する手順をスキップする。
【０１１５】
さらに、１つの秘匿化された公開鍵が以前に生成されている場合、グループ、部分グループ、ジェネレータ及び秘密鍵の全てが既に選択及び決定されていることは確かである。
【０１１６】
それゆえ、新しい公開鍵を生成することになっている場合、制御装置５５は、これらの４ステップをスキップし、次のステップに直接進む。
【０１１７】
ｙ１又はｙ２が元々グループＧの範囲外にある場合、それらをグループＧへマッピングしなければならない。そのマッピング方法は、異なるグループ毎に変わってもよい。
【０１１８】
しかし、巡回グループＧは、そのようなマッピング方法があることを示している。
【０１１９】
前述の手順は、システムの単一の装置／モジュール(統合されたコンポーネントあるいは個別のコンポーネントを備えた)において、あるいはいくつかの手順を実行するシステムのそれぞれの装置に分散する方法で、それぞれ実行可能であることに留意する。
【０１２０】
（グループ、部分グループ及びジェネレータの選択の例）
【０１２１】
グループ、部分グループ及びジェネレータの選択例を、以下に示す。
【０１２２】
グループＺｐ＊が、ｐ＝１１、よって、Ｚ１１＊＝｛１，  ２，  ３，  ４，  ５，  ６，  ７，  ８，  ９，  １０｝の条件のもとで選択されたと想定する。
【０１２３】
「１１」が素数であるので、数学上、Ｚ１１＊の位数は１１−１＝１０となる。
【０１２４】
要素２は、Ｚ１１＊＝｛２ｉ
ｍｏｄ１１ ／ ｉ＝０，  １，  ・・・，  ９｝であることを容易に確認できることから、Ｚ１１＊のジェネレータである。
【０１２５】
さらに、グループが部分グループそれ自身であるので、部分グループがＺ１１＊として選択される。
【０１２６】
部分グループの別の選択例は、例えば、位数５のジェネレータ３を持つ｛１，３，４，５，９｝である。
【０１２７】
さらに、３５＝１
ｍｏｄ １１であることは容易に確認できる。
【０１２８】
さらに、当該技術分野における当業者であれば分かるように、この装置及び構成要素の全ては、多様な考察に基づきハードウェア、ソフトウェア、ファームウェアあるいはそれらの組み合わせで実現できることができる。
【０１２９】
（キー生成の最適化）
【０１３０】
主として図６に示した典型的な法の例は、本発明による秘匿化された公開鍵を生成するために利用可能な多くの方法のうちのほんの１例である。
【０１３１】
同じ目的に使用することができるだけでなく処理の最適化を達成することができるより進んだ方法がある。
【０１３２】
最適化方法を説明するために、当該技術分野においてよく知られている符号化及び復号化する手順について、図４、図５及び図７を参照して簡潔に要約する。
【０１３３】
ここで、以下の記号１で示す演算子はグループＧの可逆演算子である。
【０１３４】
【数１】
2007089171.tif 000003
【０１３５】
以下の記号２で示す演算子は、記号１で示す可逆演算子の正確な逆演算子である。
【０１３６】
【数２】
2007089171.tif 000004
【０１３７】
本発明を図７中の手順で適用する。
【０１３８】
プレーンテキストＭを暗号化するために、プレーンテキストＭがグループＧの要素として最初に表す（例えば、ＭはＡＳＣＩＩコードとして表わされる）（ステップＳ８０）。
【０１３９】
次いで、整数ｋが、１＜｜ｋ｜＜ｍを満たす指定子として選択され（ステップＳ８１）、そして、１ペアの値が以下のように計算される（ステップＳ８２）。
【０１４０】
【数３】
2007089171.tif 000005
ここで、Ｃ１とＣ２はグループＧの要素である。
【０１４１】
これらの演算処理の全ては図４に示す暗号化装置４８によって実行することができる。
【０１４２】
記号１による演算は、グループＧの乗算、除算、加算あるいは減算となる。
【０１４３】
Ｃ１又はＣ２が元々グループＧの範囲外にある場合、グループＧへそれらをマッピングしなければならない。そのマッピング方法は、各グループ毎に異なっていてもよい。
【０１４４】
この時、メッセージＭの暗号文がＣ＝（Ｃ１，  Ｃ２）として得られ（ステップＳ８３）、その暗号分が送信装置４４によって通信チャネル上に送信される（ステップＳ８３）。
【０１４５】
符号化されるグループＧの範囲外にあるメッセージＭについては、符号化前にいくつかのグループ要素に変換される。
【０１４６】
後の復号化に続いて、復元されたグループ要素はオリジナルメッセージへ戻されてもよい。
【０１４７】
その変換方法は、各グループ毎に異なっていてもよい。
【０１４８】
１例としては、メッセージをいくつかのブロック（それらの各々はグループＧの要素である）に分解し、Ｍを復元するために全てのブロックを連結する。
【０１４９】
通信チャネルの反対側で、暗号文メッセージＣが受信される（ステップＳ８４）。
【０１５０】
暗号文ＣからプレーンテキストＭを検索するために、２つの方法として、直接のべき数法かそうでないかを最初に決定する（ステップＳ８５）。
【０１５１】
べき数法の場合、ｒｂ＝Ｃ１ｘが最初に計算され（ステップＳ８６）、次に、以下の式による計算からＭが求められる（ステップＳ８７）。
【０１５２】
【数４】
2007089171.tif 000006
【０１５３】
そうでなければ、ｒａ＝Ｃ１−ｘが最初に計算され（ステップＳ８８）、次に、以下の式による計算からＭが求められる（ステップＳ８９）。
【０１５４】
【数５】
2007089171.tif 000007
【０１５５】
暗号文（Ｃ１，Ｃ２）の復号化に成功した後、復号化の実行に伴って、本発明による公開鍵生成装置４９は、（ｙ１＝Ｃ１−１，  ｙ２＝ｒａ）の書式で新しい秘匿化された公開鍵を生成するために解読中に出力される中間出力ｒａのみならず受信した暗号文を用いてもよい。
【０１５６】
同様に、公開鍵生成装置４９は、（ｙ１＝Ｃ１，  ｙ２＝ｒｂ）の書式で新しい秘匿化された公開鍵を生成するために復号化途中で出力された中間出力ｒｂのみならず受信した暗号文を用いてもよい。
【０１５７】
新しい秘匿化された公開鍵を生成する上記いずれかの方法によって、べき数演算が回避され、また計算効率が向上する。
【０１５８】
さらに、単一の秘匿化された公開鍵（ｙ１，  ｙ２）が提供される場合、公開鍵生成装置４９は、（ｙ２，ｙ２ｘ）の形式で新しい秘匿化された公開鍵を生成してもよい。
【０１５９】
この方法は、一連の公開鍵を生成するために複数回用いることが可能である。
【０１６０】
この方法では、公開鍵ｙ２の第２の部分が、次に続く公開鍵の最初の部分と同一であるので、生成された公開鍵による記憶容量の消費が非常に減少する。
【０１６１】
一連のｗ個の公開鍵について、記憶容量が（ｗ−１）／２ｗパーセントにセーブされるということは、十分に大きなｗについて約５０パーセントの節約を意味する。
【０１６２】
本発明においては、公開鍵が、ジェネレータのべき数の形式に基づいて同一のジェネレータで生成されるので、べき数法の代わりに乗法を含む一連の公開鍵を生成するためにジェネレータｇのべき数を再使用することができる。このようにして、記憶容量を節約し、計算を加速できる。
【０１６３】
また、復号化装置において、ジェネレータのべき数のただ１つのテーブルを維持する必要があるだけなので、新しい公開鍵の計算をオフラインで行うことが可能である。
【０１６４】
例えば、実施例において、暗号文メッセージＣ＝（Ｃ１，  Ｃ２）が復号化装置で受信される場合、新しい公開鍵を生成するためにＣ１を検索して用いることができる。
【０１６５】
上述したＣ１＝ｙ１ｋ＝ｇｒｋの場合、積“ｒｋ”が単なる他の整数であるので、ｇｒｋを新しい公開鍵を生成するために保存することができる。
【０１６６】
新しい公開鍵を生成するためにｇｒｋを保存することができるが、暗号化されたメッセージを送る時、もしも符号化装置がｋを明らかにしなかったならば、ｒｋの値は復号化装置には依然知られていない可能性がある点に留意すべきである。
【０１６７】
単一の秘匿化された公開鍵（ｙ１，  ｙ２）が提供される場合、公開鍵生成装置４９は、（ｙ１×ｙ１，ｙ２×ｙ２）の式から新しい秘匿化された公開鍵を生成してもよい。ここで、×はグループ乗算である。
【０１６８】
一般に、ｙ１１＝ｇｒ１，  ｙ１２＝ｇｒ２，  ・・・，  ｙ１ｊ＝ｇｒｊ
及び ｙ２１＝ｙ１１ｘ，  ｙ２２＝ｙ１２ｘ，  ・・・，  ｙ２ｊ＝ｙ１ｊｘである、複数の格納されたｇのべき数に基づいていくつかの秘匿化された公開鍵（ｙ１１，  ｙ２１），（ｙ１２，  ｙ２２），・・・，（ｙ１ｊ，  ｙ２ｊ），  ｊ≧２が提供される場合、新しい公開鍵が（ｙ１（ｊ＋１）＝ｙ１１ｙ１２・・・ｙ１ｊ，  ｙ２（ｊ＋１）＝ｙ２１ｙ２２・・・ｙ２ｊ）として計算される。
【０１６９】
ここで、上記 ｙ１１ｙ１２・・・ｙ１ｊは、ｙ１１，  ｙ１２，  ・・・、  ｙ１ｊの積であり、ｙ２１ｙ２２・・・ｙ２ｊは、ｙ２１，  ｙ２２，  ・・・、  ｙ２ｊの積である。
【０１７０】
明らかに、新しい秘匿化された公開鍵を生成するために、べき数演算は、乗算に置き換えられ、計算効率が向上する。
【０１７１】
乗法演算をオンラインで実行することができるので、このように生成された新しい公開鍵をあらかじめ計算する必要がなく、このことは直ちに記憶容量の節約を意味する。
【０１７２】
上記の最適化技術は、新しい秘匿化された公開鍵を生成するために一緒に用いてもよい。
【０１７３】
例えば、受信した上で、一連の暗号文（Ｃ１１，  Ｃ２１），（Ｃ１２，  Ｃ２２），・・・，（Ｃ１ｊ，  Ｃ２ｊ）（ただし、ｊ≧２）の復号化に成功した後、公開鍵生成装置４９は、（ｙ１＝（Ｃ１１
Ｃ１２・・・Ｃ１ｊ）， ｙ２＝（ｒｂ１ｒｂ２・・・ｒｂｊ））の式によって新しい秘匿化された公開鍵を生成するために解読中に出力される中間出力ｒｂ１，  ｒｂ２，  ・・・，  ｒｂｊのみならず受信した暗号文も用いることができる。
【０１７４】
ここで、Ｃ１１Ｃ１２・・・Ｃ１ｊはＣ１１，  Ｃ１２，  ・・・，  Ｃ１ｊの積、ｒｂ１ｒｂ２・・・ｒｂｊは、ｒｂ１，  ｒｂ２，・・・，  ｒｂｊの積である。
【０１７５】
また、ｙ２の計算で、一連の公開鍵は、（ｙ２ｗ１，  ｙ２ｗ２）として計算される。ここで，ｗ１＝ｘｗ，  ｗ２＝ｘ（ｗ＋１）
，  ｗ≧０である。
また、この計算において求められた結果(特にｇのべき数)は全て、公開鍵をさらに生成するために用いられる。
【０１７６】
さらに、暗号文メッセージＣから検索されたＣ１に基づいて、復号化装置はさらに多くの新しい公開鍵を生成することが可能である。
【０１７７】
この目的のために、Ｃ１ｘ及びＣ１−ｘを計算して保存され、次いで、２つの一連の公開鍵が生成される。
【０１７８】
一般に、多くの暗号化されたメッセージＣＣ１＝（Ｃ１１、Ｃ１２），  ＣＣ２＝（Ｃ２１、Ｃ２２），  ・・・，  ＣＣｊ＝（Ｃｊ１、Ｃｊ２）が受信された時、Ｃ１ｘの場合、一連の新しい公開鍵が、（（Ｃ１１Ｃ２１・・・Ｃｊ１）ｕ１
，  （Ｃ１１Ｃ２１・・・Ｃｊ１）ｕ２）として生成される。ここで、Ｃ１１Ｃ２１・・・Ｃｊ１は、Ｃ１１，  Ｃ２１，  ・・・，  Ｃｊ１，  （ｊ≧１，  ｕ１＝ｘｕ，  ｕ２＝ｘ（ｕ＋１），  ｕ≧０）の積である。また、Ｃ１−ｘの場合、別の一連の新しい公開鍵が、（（Ｃ１１Ｃ２１・・・Ｃｊ１）ｖ１
，  （Ｃ１１Ｃ２１・・・Ｃｊ１）ｖ２）として生成される。ここで、Ｃ１１Ｃ２１・・・Ｃｊ１は、Ｃ１１，  Ｃ２１，  ・・・，  Ｃｊ１，  （ｊ≧１，  ｖ１＝−ｘｖ，  ｖ２＝−ｘ（ｖ＋１），  ｖ≧０）の積である。
【０１７９】
さらに、この計算において求められた結果(特にｇのべき数)は全て、公開鍵をさらに生成するために用いられる。
【０１８０】
（順応性のある匿名証明書）
以下の記述で、本発明の一般的な概念を説明する。
【０１８１】
APK手法は、前述の出願中の関連出願において説明しているように、多数の秘匿化された公開キーを証明する方法に関して問題を含んでいる。そのため、多数の秘匿化された公開キーを証明することができる解決法の提案が望まれている。
【０１８２】
１．安全性。誰も証明書を偽造することができない。また、誰も証明書の保持者であることを隠すことができない。
【０１８３】
２．確実性。ユーザーのプライバシーは、いかなる証明書によっても明かされない。
【０１８４】
３．取り消し可能。ユーザーが匿名性を悪用する場合、ユーザーの本当の身元を暴露することができる。
【０１８５】
４．信頼性。証明書は、ビジネスにおいても有効である。
【０１８６】
５．分配できる。APKの分配方法のように、証明書解決法が分散させられるべきである。
【０１８７】
６．効率的。第３者機関の経済的負担がより少ない。
【０１８８】
上述したように、従来の証明方法は多くの欠点を有している。さらに、APKは分散型のプライバシー保護解決法であるので、集中型の証明解決法はAPK解決法に適していない。
【０１８９】
従って、ユーザのデータを証明するための分散型解決法は、従来より提案されている、すなわち、柔軟性のある匿名証明書(MPC)解決法である。
【０１９０】
本発明による柔軟性のある匿名証明書(MPC)解決方法は、多数の秘匿化された公開キーを証明する新規の解決方法である。全ての証明書が信頼できる実体によって生成され発行される従来の解決法と異なり、MPC解決法は、他人によってデータを証明する必要のあるユーザーが、自分自身で信頼できる実体から取得したルート証明から匿名証明書を生成する分散型解決法である。
【０１９１】
ルート証明は、ユーザーが匿名証明書を生成するために信頼できる実体によって発行された証明書でもよい。以下、そのような証明書をルート証明と称する。ルート証明は、またグループ秘密鍵でもよい。ユーザーはそのグループ秘密鍵によってグループ・メンバーの名のもとに匿名証明書を生成することが可能である。しかし、ルート証明は、それらに限定されない。ルート証明は、ユーザの信用を証明することができる任意のデータでも良いし、また、所定のアルゴリズムによって生成される匿名証明書でもよい。
【０１９２】
図８Ａは、本発明のMPC解決法の全体的な概念を示す概略ブロック図である。
【０１９３】
ユーザＵは、ネットワークを介して他のユーザと通信する、ネットワーク中のユーザである。通信セションの間、ユーザＵのデータのうちのいくつかは他のユーザ或いは仲間によって証明されることを必要とされる。例えば、ユーザＵのデータＤＡＴＡ１はユーザＶ１によって証明され、ユーザＵのデータＤＡＴＡ２はユーザＶ２によって証明され、ユーザＵのデータＤＡＴＡ３はユーザＶ３によって証明されることになっている。以下、信用を得るためにユーザＵのデータを証明することを望むユーザ或いは仲間を立証者と称する。
【０１９４】
ＤＡＴＡ１、ＤＡＴＡ２及びＤＡＴＡ３は、様々な通信セッションのためのユーザの種々の公開鍵である。１つの実例では、これらのデータは唯一の公開鍵或いはＡＰＫである。しかし、データは公開鍵に限定されない。証明されるデータは、様々な目的のためのどんなデータでもよい。
【０１９５】
データを認証するために、ユーザＵは、立証者（Ｖ１、Ｖ２、Ｖ３等）へデータを送る。ここで、データは、ＰＣ１、ＰＣ２、ＰＣ３等の証明書を有している。ＭＰＣ解決方法では、これらの全ての証明書は、信用された主体からユーザＵに発行されたルート証明から生成される。これらの証明書（ＰＣ１、ＰＣ２、ＰＣ３等）が信用された主体の介在無しでユーザＵ自身によって計算されることが重要である。立証者は、そのような添付された証明書によってユーザＵのデータを照合する。また、信用された主体によって照合された証明書はデータを保証することが可能である。立証者が信用された主体を信用するならば、立証者は、ユーザＵのデータが真正なことを信じることができる。
【０１９６】
信用ある主体は、Ｕの信用を証明することができるＣＡ、信用あるグループ、Ｕの友人あるいは他の関係者などである。
【０１９７】
本発明によるＭＰＣ解決方法において、立証者は、Ｕのデータが信用ある主体によって証明されているという証明書によって照合し確信を得ることができる。一方、その証明書は、立証者が決してユーザのデータの保持者であるユーザＵの本当の身元を明かさないようユーザによって生成される。従って、ユーザによって生成された証明書を、以下匿名証明書と称する。
【０１９８】
ユーザデータがＡＰＫである場合、ＡＰＫの各ペアと匿名の証明書が立証者（例えばＶ１）に示される。Ｖ１はＡＰＫが信用された主体によって証明されていることを検査し確信を得ることができる一方、Ｖ１は決してＡＰＫと匿名証明書のペアの保持者を明かさない。匿名の公開鍵と匿名証明書の別のペアを示す度に、ユーザがＶ１と何度も通信しても、Ｖ１は自分がユーザと話しているかどうかを知らせることはできない。
【０１９９】
図８Ｂは、本発明によるＭＰＣ解決方の一般的な検証プロセスを概略的に示すフローチャートである。
【０２００】
ステップ８１において、ユーザが信用ある主体からルート証明を取得する。例えば、ユーザは、自身の基本的なデータ（以下、ルート・データと称する）とそのデータに対するユーザの証明をＣＡに示す。ＣＡは、ユーザのルート・データとルート・データのユーザ証明の識別検査を実行する。ユーザがＣＡの識別検査にパスした後、ＣＡはユーザに対する証明書を発行する。
【０２０１】
ステップ８２において、ユーザは、ルート証明からの匿名証明書を生成する。同じルート証明から、ユーザは複数の別個の匿名証明書を生成することが可能である。
【０２０２】
ステップ８３において、ユーザは、１の匿名証明書を有するユーザのデータを立証者に送信する。
【０２０３】
ステップ８４において、立証者が匿名証明書によってユーザのデータを検査する。
データが、信用のある主体によって証明された匿名証明書によって証明されるので、立証者が信用のある主体を信じる場合、立証者は、ユーザのデータが信用できるという確信を抱くことができる。その後、立証者は前記データに基づいて安全にユーザと通信することができる。例えば、ユーザのデータが匿名の公開鍵である場合、ユーザは自身のメッセージにデジタル的に署名してもよいし、立証者はユーザ自身の匿名の公開鍵に基づいてユーザのためのメッセージを全て暗号化してもよい。しかしながら、ユーザのデータは、ユーザの匿名の公開鍵に制限されない。例えば、それはユーザの唯一無比の公開鍵でもよい。
【０２０４】
図８Ａと図８Ｂから分かるように、データが信用のある主体によって証明される匿名証明書によって保証される場合、ユーザは信頼できるデータを生成することが可能である。ユーザ・プライバシ保護の機能は完全に施される。
ユーザは、自身による別個の匿名証明書だけでなく別個の匿名の公開鍵も生成する。信用のある主体は、ユーザのルート・データのためのルート証明をただ発行するだけである。例えば、ＣＡは、ユーザ自身のルート公開鍵のために、ユーザに対してルート証明書（ＲＣ）を発行する。証明書機関（ＣＡ）の介在は最小限である。よって、ＣＡの負荷の軽減化を実現することが可能である。
【０２０５】
さらに、本発明によるＭＰＣ方式では、信用ある主体は、匿名証明書が信用ある主体で追跡可能なように、ユーザのルート証明を格納することができる、
【０２０６】
ユーザＵが不適切に振る舞う場合（例えば、ユーザがメッセージにデジタル署名した後で、それを否認するような場合）、被害者は信用ある主体にユーザＵの匿名証明書を送信することが可能である。それは、信用ある主体だけが、匿名証明書の真の保持者を解明する能力を持っているためである。
【０２０７】
具体的な例について説明する。ユーザＵは対の匿名の公開鍵および匿名証明書を生成するものとする。その後、ユーザは立証者Ｖ１と通信し、鍵と証明書を明示する。匿名証明書に基づいて、立証者Ｖ１は、匿名の公開鍵が信用ある主体によって本当に証明されていることを確認する。従って、ユーザＵが立証者Ｖ１に５０ドル支払うことに署名すると、立証者Ｖ１は、自身が著わした電子本（e-book）をユーザＵに送る。立証者Ｖ１はただ匿名の公開鍵及び匿名証明書を確認するだけなので、立証者は、買い手の本当の身元を知らない。しかしながら、ユーザＵが支払をせずに逃げるならば、立証者Ｖ１は、匿名証明書の本当の保持者を暴くことができる信用ある主体に匿名証明書を送ることが可能である。この場合、保持者Ｕは結果的にペナルティーを受けることになる。このように、ユーザはシステムの匿名性を乱用するのは不可能である。
【０２０８】
（第１の実施の形態）
以下、本発明による第１の実施の形態について図９〜図１８を参照して説明する。
【０２０９】
図９は、本発明の第1の実施の形態によるシステム構成を概略的に示すブロック図である。
【０２１０】
第１の実施の形態によれば、信用された主体は証明書機関ＣＡ(Certificate Authority CA)である。立証者によって証明されるユーザＵのデータはユーザＵの匿名の公開鍵である。
【０２１１】
もし、Ｕが個人識別検査に合格すれば、ＣＡはＵに対してルート証明書（ＲＣ）を発行する。Ｕは、自身の匿名の公開鍵のためにルート証明書から匿名証明書を生成する。その後、Ｕは、立証者Ｖ（Ｖ１、Ｖ２（Ｖ３）．．．）に対して、匿名証明書（ＰＣ１、ＰＣ２（ＰＣ３）．．．）を持つ匿名の公開鍵（ＡＰＫ１、ＡＰＫ２（ＡＰＫ３）．．．）を送信する。Ｖは、Ｕから受信した匿名証明書を証明し、予め定義した条件が満たされる場合、その証明書を受け入れる。
【０２１２】
第１の実施の形態では、Ｕは、ＣＡの介在無しにＲＣからある匿名の公開鍵のための匿名証明書を引き出すことが可能である。一方、Ｖは、同様にＣＡを含むことを必要としない匿名証明書に基づいてＵの真正なことを判断することが可能である。
【０２１３】
さらに、Ｖは、Ｕから集められたデータを格納する。また、ある状況の下で（例えば、Ｕが不法に振舞う）、Ｖは、Ｕから集めたデータをＣＡに提出することができ、また、ＣＡは、Ｕの実際の身元を明かすことができる。
【０２１４】
以下の説明においては、暗号化技術はStrong RSA (SRSA) Assumptionに基づいている。ＳＲＳＡの詳細に関しては、「N. Baric´, B. Pfitzmann, Collision-free
Accumulators and Fail-stop Signature Schemes without Trees, Advances in
Cryptology-EUROCRYPT’97, pp. 480~494, 1997; and R. Cramer, V. Shoup, Signature Schemes Based on The Strong RSA
Assumption, ACM Transactions on Information and System Security, vol. 3(3):
161~185, 2000」を参照することができる。
【０２１５】
さらに、いくつかの証明方法が本発明の実施の形態において使用される。それらは、証明者が、ある値の知識に関して立証者を納得させることを可能にする。一方、値自体に関する有用な情報は漏らされない。
【０２１６】
本発明による第１の実施の形態では、いわゆる知識証明技術が使用される（「S. Goldwasser, S. Micali, C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, 17th
ACM Symposium on Theory of Computation, pp. 291~304, 1985」を参照）。ゼロ知識（zero-knowledge）中の離散対数について知識を証明するために多くの方法が提案されている（「A. Fiat, A. Shamir, How To
Prove Yourself: Practical Solutions to Identification and Signature Problems,
Advances in Cryptology - CRYPTO’86,
pp. 186~194, 1986; D. Chaum, Demonstrating
Possession of a Discrete Logarithm without Revealing It, Advances in
Cryptology - CRYPTO’86, pp. 200~212, 1987; D. Chaum, J. H. Evertse, J. van de
Graaf, An Improved Protocol for
Demonstrating Possession of Discrete Logarithms and Some Generalizations,
Advances in Cryptology - EUROCRYPTO’87, pp. 127~141, 1987; D. Chaum, T. P.
Pedersen, Wallet Databases with Observers,
Advances in Cryptology - CRYPTO’92, pp. 89~105, 1993; and K. Sako, J. Kilian, Receipt-Free Mix-Type Voting Scheme-A
Practical Solution to the Implementation of a Voting Booth, Advances in
Cryptology - CRYPTO’98, pp. 393~403, 1998」を参照）。
【０２１７】
本発明による第１の実施の形態において、
【数６】
2007089171.tif 000008
式（１）は、共通の入力（ｇｊ，ｙｊ）について、証明者と立証者の間の知識証明を示すために使用される。ここで、ｇｊが〈ｇｊ〉，ｊ＝１，・・・，ｉを生成し、全てのｊ＝１，・・・，ｉについて、
【数７】
2007089171.tif 000009
ｙｊ＝ｇｊｘｊ
で、ａｊ＜ｘｊ＜ｂｊが成り立つようにｘｊについての知識を証明する。
ａｊ＜ｘｊ＜ｂｊを証明する手法が、「T. Okamoto, An Efficient Divisible Electronic Cash
Scheme, Advances in Cryptology - CRYPTO’95, pp. 438~451, 1995, and later on
developed in A. Chan, Y. Frankel, Y. Tsiounis, Easy Come - Easy Go Divisible Cash, Advances in Cryptology -
EUROCRYPT’98, pp. 561~575, 1998, in which it has been given the name the Range
Bounded Commitment (RBC)」に記載されている。
【０２１８】
乗法表現のための証明の場合に上述の式（１）を一般化することが可能である。
【数８】
2007089171.tif 000010
例えば、式（２）は、もし、ａ＜ｘ１＜ｂであれば、
【数９】
2007089171.tif 000011
と
【数１０】
2007089171.tif 000012
が同時に成り立つような、ｘ１とｘ２のゼロ知識証明を表す。
【０２１９】
次に、本発明の第１の実施の形態による方法の詳細を、図１０〜１６を参照して説明する。
【０２２０】
この第１の実施の形態による方法は、主として５つの工程からなる。すなわち、システムスタートアップ、RCリクエスト、MPC導出、秘匿の認証及び追跡(必要ならば)である。
【０２２１】
図１０は、本実施の形態によるシステムスタートアップ工程におけるＣＡ初期化処理の例を示すフローチャートである。
【０２２２】
ステップ１０１において、ＣＡはＳＲＳＡ係数ｎｃを生成する。係数ｎｃの因数分解は秘密に保たれる。
【０２２３】
ステップ１０２において、ＣＡは、ｐ−１がちょうどｑで割り切れるような素数ｐ及びｑを生成する。
【０２２４】
ステップ１０３において、ＣＡは、整数ｌｑ＝｜ｑ｜（すなわち、ｑの大きさ）を計算する。
【０２２５】
ステップ１０４において、ＣＡは、Ｚ＊ｐからＧＦ（ｑ）（オーダーｑの有限体）の１つのジェネレータｇを選択する。
【０２２６】
ステップ１０５において、ＣＡはＱＲ（ｎｃ）から整数ｃａ、ｃｂおよびｃｃを選択する。
【０２２７】
ステップ１０６において、ＣＡは整数ｌｃ＜ｌｑを選択する。
【０２２８】
上述の数学的な概念は、参考文献としての、A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied
Cryptography, CRC Press, 1996  に記述されている。最後に、ステップ１０７において、ＣＡは、ｎ，ｐ，ｑ，ｇ，ｌｑ，ｃａ，ｃｂ，ｃｃ及びｌｃをネットワーク（例えばインターネット）上に発行する。
【０２２９】
図１１は、本実施の形態によるシステムスタートアップ工程におけるユーザ初期化処理の例を示すフローチャートである。
【０２３０】
ＣＡによって発行されたシステムパラメタに従って、ユーザＵは、ステップ１１１においてそれ自身の秘密鍵
【０２３１】
【数１１】
2007089171.tif 000013
をランダムに選択する。
【０２３２】
ステップ１１２において、ユーザＵは、自身のルート公開鍵
【数１２】
2007089171.tif 000014
を計算する。
【０２３３】
ＲＣを得るために、Ｕは、ＣＡへ自身の身元を立証する必要があると共に、ＣＡはｙｕが公開鍵として他のいずれかのユーザによって使用されていないことを確かめなければならない。
【０２３４】
図１２は、本実施の形態によるＲＣリクエスト処理の例を示すフローチャートである。
【０２３５】
ステップ１２１において、ユーザＵが
【数１３】
2007089171.tif 000015
を計算する。
【０２３６】
ステップ１２２において、ユーザＵがＣＡにその人のルート公開鍵（ｇ，ｙｕ）およびａｕを実行依頼する。
【０２３７】
ステップ１２３において、ユーザＵおよびＣＡが以下の式により知識証明を実行する。
【数１４】
2007089171.tif 000016
【０２３８】
知識証明が成功した場合、ステップ１２４において、ＣＡは十分に大きい任意の素数
【数１５】
2007089171.tif 000017
を選択し、ｅｕが他のユーザに割り当てられていないことを確かめて、
【数１６】
2007089171.tif 000018
を計算する。
【０２３９】
ステップ１２５においては、ＣＡが、ＲＣとして（ｇ，ｙｕ）に対する（ｅｕ，ｓｕ）をユーザＵに発行する。
【０２４０】
ステップ１２６において、ＣＡは、可能な調査のために、ユーザＵの名前の元でデータベースにデマスキングｅｕを格納する。
【０２４１】
ステップ１２７において、ユーザＵが、合同式
【数１７】
2007089171.tif 000019

が成り立つことを証明する。
【０２４２】
前記ＲＣは２つの組（ｅｕ，ｓｕ）である。ここで、ｅｕは実際はＲＳＡ公開鍵で、ｓｕがｃｂ／ａｕのデジタル署名である。
しかしながら、次の段階の中で実証されるように、単一の署名の準備に際して、Ｕは、自身の全ての匿名の公開鍵のための証明書を効果的に得ることが可能である。ＲＣは、表現形式（ｇｒ，ｙｕｒ）に従って匿名の公開鍵全てに署名するデジタル署名である。
【０２４３】
図１３は、本実施の形態においてユーザＵがどのように匿名の公開鍵を生成するかを示すフローチャートである。また、図１４は、本実施の形態において匿名の公開鍵用のＲＣからユーザＵがどのように匿名証明書を得るかかを示すフローチャートである。匿名の公開鍵および匿名証明書はともにプライバシ保護及び匿名の真正なことを保証する。
【０２４４】
図１３に示すように、ステップ１３１において、ユーザＵは、｛０，１，・・・，２ｋ−１｝から整数ｒを選択し、ステップ１３２において、匿名の公開鍵（ｇｒ，ｙｕｒ）（ｍｏｄ  ｐ）を算出する。
【０２４５】
図１４に示すように、ステップ１４１において、ユーザＵは、｛０，１，・・・，ｑ−１｝から整数ｔを選択し、ステップ１４２において、
【数１８】
2007089171.tif 000020
と
【数１９】
2007089171.tif 000021
を算出する。
【０２４６】
匿名証明書は実際に２つの組
【数２０】
2007089171.tif 000022
である。
【０２４７】
いま、Ｕは、
【数２１】
2007089171.tif 000023
を有している。ここで、ｅｕ，ｘｕおよび-ｔラｅｕについての知識は次の段階において立証者に証明される。
【０２４８】
匿名の公開鍵および匿名証明書の準備の後、Ｕは立証者へそれらを提示することが可能である。
【０２４９】
図１５は、本実施の形態による匿名認証処理の例を示すフローチャートである。
【０２５０】
ステップ１５１において、ユーザＵが立証者Ｖに匿名の公開鍵（ｙ１ｒ＝ｇｒ，ｙ２ｒ＝ｙｕｒ）および匿名証明書
【数２２】
2007089171.tif 000024
を送る。
【０２５１】
ステップ１５２において、Ｖが
【数２３】
2007089171.tif 000025
を計算する。
【０２５２】
ステップ１５３において、ユーザＵおよび立証者Ｖが以下ように知識証明を実行する。
【０２５３】
【数２４】
2007089171.tif 000026
【０２５４】
ステップ１５４において、Ｖが、可能な追跡のために上記の知識証明の記録を格納する。
【０２５５】
図１２のステップ１２６においてＣＡがユーザＵの名前でデータベースにデマスキングｅｕを格納するので、ＣＡは検査能力を有する。
【０２５６】
Ｖが保証されたＣＡ  ＣＭＳとしてＵの匿名の公開鍵を受け入れて、Ｕを含めた処理を行なった後、Ｕが不適切に振る舞う場合、ＶはＣＡにＵの不適切行動を示す証拠を供給し、支援をＣＡに求めることが可能である。ＣＡは、Ｖから受け取られた証拠を明確に検査する。ＣＡの視点から、ＶがＵの本当の身元を知る十分な理由があれば、ＣＡはＵの本当の身元を確認するたねにＶに協力することが可能である。
【０２５７】
図１６は、本実施の形態による調査処理を示すフローチャートである。
【０２５８】
ステップ１６１において、ＶがＣＡに匿名証明書
【数２５】
2007089171.tif 000027
を送る。
【０２５９】
ステップ１６２においては、データベースに格納された全てのデマスキングｅｕについて、ＣＡが
【数２６】
2007089171.tif 000028
を計算し、その結果を
【数２７】
2007089171.tif 000029
と比較する。
【０２６０】
【数２８】
2007089171.tif 000030
および
【数２９】
2007089171.tif 000031
の一致は、匿名証明書
【数３０】
2007089171.tif 000032
の所有者のデマスキング値を明らかにする。このように、ＣＡは、Ｕの本当の身元を見いだして明らかにすることが可能である。
【０２６１】
次に、ユーザ側およびＣＡ側における代表的な装置について図１７と図１８を参照して説明する。
【０２６２】
図１７は、第１の実施の形態によるユーザの代表的な装置１７０を示すブロック図である。
【０２６３】
図１７に示すように、ユーザ装置１７０は、基本的に、ＣＡからＲＣを受け取るためのルート証明ユニット１７１、ＲＣに基づいて匿名証明書の生成のためにルート証明ユニット１７１に接続される匿名証明書生成ユニット１７２、匿名証明書を有するユーザのデータを送信するための匿名証明書生成ユニット１７２に接続された送信ユニット１７３を備えている。
【０２６４】
ルート証明書がネットワークを介してディジタル・リクエストによって要求される場合、ユーザ装置１７０は、さらに、ＲＣの要請を生成しＣＡに要求を送信するためのルート証明要求ユニット１７４を備えることができる。
【０２６５】
立証者によって証明されるユーザのデータは、公開鍵、唯一の公開鍵、匿名の公開鍵等であってもよい。匿名の公開鍵である場合には、ユーザ装置１７０が、匿名の公開鍵の生成のための匿名公開鍵生成ユニット１７５をさらに備えることが可能である。匿名公開鍵生成ユニット１７５の詳細については、上述したＡＰＫ手法の記述から理解することができる。匿名証明書によって証明されるユーザのデータが匿名の公開鍵でない場合、匿名公開鍵生成ユニット１７５は対応するデータ生成ユニットと置き換えることが可能である。
【０２６６】
ＲＣの発行がユーザとＣＡの間の検証プロセスを要求するか、または立証者が認証プロセスにおける知識証明を要求する場合、ユーザ装置１７０は、さらに、立証者あるいはＣＡと共に検証動作を実行するための検証ユニット１７６を備えることも可能である。
【０２６７】
上述した各ユニットは、それぞれのユニットによって使用されるデータを格納のためのメモリを備える。別の実施例では、ユーザ装置１７０は、装置の動作中に全てのユニットによって使用されるデータを格納のために記憶装置１７７を備えることも可能である。
【０２６８】
多くの場合、ユーザはさらに他のユーザの受信データを証明する必要がある。従って、ユーザ装置１７０は、添附された匿名証明書によってもう一人のユーザから受信したデータを証明するための証明ユニット１７８を備えることも可能である。
【０２６９】
ルート証明ユニット１７１、送信ユニット１７３、ルート証明要求ユニット１７４、検証ユニット１７６及び証明ユニット１７８は、ネットワークを介して他の装置と通信するために上記各ユニットと接続されるユーザ装置１７０内の通信ポート或いは通信ユニットを介してネットワークにデータを送信し、或いはネットワークからデータを受信する。
【０２７０】
本発明の第１の実施の形態による処理を実行するため、上記各ユニットは互いに接続されている。ユニットがハードウェアモジュールとして実装される場合、それらはデータバスによって互いに接続される。
【０２７１】
図１８は、第１の実施の形態による代表的なＣＡ装置１８０を示すブロック図である。
【０２７２】
図１８に示すように、ＣＡ装置１８０は、基本的に、システムパラメータを計算するためのシステムパラメータ計算ユニット１８１、ネットワークの全てのユーザによって共有されるパラメータを発行するためにシステムパラメータ計算ユニット１８１に接続されるパラメータ発行ユニット１８２、ユーザからＲＣリクエストを受信するためにネットワークに接続されるルート証明要求受信ユニット１８３、ルート証明リクエストに応じてユーザのためのＲＣを生成するために、ルート証明要求受信ユニット１８３及びシステムパラメータ計算ユニット１８１に接続されるルート証明生成ユニット１８４を備えている。
【０２７３】
ルート証明書が発行される前に、ユーザのＲＣリクエストが検査される場合、ＣＡ装置１８０は、ユーザのＲＣリクエストに応じて識別検査を行なうために、ルート証明要求受信ユニット１８３に接続された検査ユニット１８５をさらに含む。識別検査は、上述した知識証明処理を含んでいる。
【０２７４】
検査能力が要求される場合、ＣＡ装置は、ルート証明生成ユニット１８４によって生成されたルート証明書の格納されたデマスキング値を使用することにより、立証者から受信した匿名証明書の所有者の身元の調査のための、ネットワークに接続された検査ユニット１８６をさらに備えることができる。
【０２７５】
上述した各ユニットは、それぞれのユニットによって使用されるデータを格納のためのメモリを備える。別の実施例では、ＣＡ装置１８０は、装置の動作中に全てのユニットによって使用されるデータを格納のために記憶装置１８７を備えることも可能である。例えば、ルート証明生成ユニット１８４によって生成されたＲＣは、ルート証明生成ユニット１８４内部のメモリに格納するか、あるいは記憶装置１８７に格納することが可能である。
【０２７６】
本発明の第１の実施の形態による処理を実行するため、上記各ユニットは互いに接続されている。ユニットがハードウェアモジュールとして実装される場合、それらはデータバスによって互いに接続される。
【０２７７】
パラメータ発行ユニット１８２及びルート証明要求受信ユニット１８３は、ネットワークを介して他の装置と通信するために、上記各ユニットと接続されるＣＡ装置１８０内の通信ポート或いは通信ユニットを介してネットワークにデータを送信し、或いはネットワークからデータを受信する。
【０２７８】
上記説明したユーザ装置及びＣＡ装置は単なる一例である。しかしながら、装置に含まれた構成装置は、上述したユニットに限定されず、その詳細な構成は修正又は変更することが可能である。例えば、装置は、ネットワーク中の計算する装置に一般的に実装される他のユニットを含むことができる。例えば、データを入出力するためのＩ／Ｏインタフェース、ネットワークを介して他の装置に接続するための種々の通信インタフェース、各ユニットの動作を制御するためのコントローラなどである。そのようなユニットについては、この技術分野において一般的であるので図示は省略する。また、当業者によれば上述した装置にそれらのユニットを加えることは容易に考え付くことである。
【０２７９】
上記のように本発明の第１の実施の形態について説明したが、本発明は、第１の実施の形態に記述された内容に限定されない。例えば、ユーザの公開鍵については他の方法によって生成することが可能である。唯一無比の公開鍵（「B. R. Waters, E. W. Felten, A. Sahai, Receiver Anonymity via Incomparable Public Keys, CCS’03,
Washington, DC, USA, pp.112~121, 2003」を参照）は、匿名証明書によって証明されるユーザのデータとして使用することが可能である。また、匿名証明書によって保証されるユーザのデータは、公開鍵に限定されず、ユーザによって送られた任意のデータあるいはメッセージでもよい。さらに、実施の形態は、ＣＡの他の証明技術及び方法に適合させるために修正することが可能である。図１４に示されたアルゴリズムに加えて、アルゴリズムが、匿名証明書がＲＣと同様に立証可能な証明性あるいは秘密性を維持し、同時に、立証者に前記データの所有者の身元に関する情報を分からなくすることを保証する限り、他のアルゴリズムをＲＣからの匿名証明書を計算するために使用することが可能である。第１の実施の形態は、ルート公開鍵が（ｇ，ｙｕ）である場合について説明した。しかし、ルート公開鍵は匿名の公開鍵（ｇｒ，ｙｕｒ）のうちの任意の１つでもよい。
【０２８０】
（第２の実施の形態）
以下、本発明の第２の実施の形態を図１９、図２０を参照して説明する。
【０２８１】
本発明の第２の実施の形態は、公開鍵用の匿名証明書を生成するためにグループ署名方式を採用する。ここで、公開鍵は、唯一の公開鍵、匿名の公開鍵或いはユーザの他の公開鍵等であってもよい。
【０２８２】
グループ署名方式は、過去１５年の間にかなり研究されている（「D. Chaum, E. van Heyst, Group
Signatures, Advances in Cryptology - EUROCRYPTO’91, pp. 257~265, 1991; J.
Camenisch, M. Michels, A Group Signature
Scheme Based on an RSA-Variant, Advances in Cryptology - ASIACRYPT’98, pp.
160~174, 1998; and G. Ateniese, J. Camenisch, M. Joye, G. Tsudik, A Practical and Provably Secure
Coalition-Resistant Group Signature Scheme, Advances in Cryptology - CRYPTO’2000,
pp. 255~270, 2000, which are incorporated as references」を参照）。簡単に説明すると、グループをセット・アップし、グループ・メンバーの承認および取消しを扱うグループ管理者が存在する。全てのグループ・メンバーは同一のグループ公開鍵ＰＫｇを共有するが、各メンバーＵｉはそれぞれ異なる秘密鍵ＳＫｉを有している。メッセージｍが与えられると、グループ・メンバーＵｉはｓ＝ＳＩＧ（ｍ，ＰＫｇ，ＳＫｉ）としてグループを代表してメッセージに署名することが可能である。ここで、ＳＩＧ（ラ）は特有のグループ署名アルゴリズムである。メッセージｍについての署名ｓは、グループ公開鍵ＰＫｇによって照合される。すなわち、与えられたＰＫｇ，ｓ及びｍについて、もしｓ＝ＳＩＧ（ｍ，ＰＫｇ，ＳＫｉ）である場合だけ有効であることを出力する署名照合アルゴリズムＶＥＲＩＦ（ラ）（＝ＶＥＲＩＦ（ｓ，ｍ，ＰＫｇ））が存在する。しかしながら、立証者がｓの署名者Ｕｉを決定するのは非常に困難である。立証者の観点からすると、いかなるグループ・メンバーも、ｓの署名者であることについて同じ確率を有している。この特徴が「グループ署名」の名称の始まりである。
【０２８３】
いくつかのグループ署名方式は、グループ管理者がｓの署名者Ｕｉを決定することができる権限を提供する。すなわち、与えられたＰＫｇ，ｓ及びＳＫｍについて、もしｓ＝ＳＩＧ（ｍ，ＰＫｇ，ＳＫｉ）である場合だけＵｉを出力する署名照合アルゴリズムＴＲＡＣＥ（ラ）（＝ＶＥＲＩＦ（ｓ，ｍ，ＰＫｇ））が存在する。ここで、ＳＫｍはグループ管理者の秘密鍵である。
【０２８４】
図１９は、本発明の第２の実施の形態のシステム構成の概略を示すブロック図である。
【０２８５】
第２の実施の形態によれば、信用された主体はグループ管理者Ｍによって組み立てられたグループ１９０である。ユーザＵはグループのメンバーであり、自身に割り当てられたグループ秘密鍵を所有する。従来のグループ署名機構では、メッセージがグループを代表して署名される。しかしながら、本発明の第２の実施の形態では、グループ署名は公開鍵の匿名証明書を生成するために使用される。
【０２８６】
図２０は、第２の実施の形態による、匿名証明方法を示すフローチャートである。
【０２８７】
初期化段階２０１において、グループ管理者はグループを組み立てて、グループ公開鍵ＰＫｇを発行する。さらに、グループ管理者は、不適切な振る舞いのユーザを調査する際に利用される秘密鍵ＳＫｍを秘密に保持する。
【０２８８】
ステップ２０２において、グループ・メンバーＵがグループに加わり、このグループ用の自身のグループ秘密鍵ＳＫｕを取得する。
【０２８９】
ステップ２０３において、Ｕが匿名の公開鍵ａｐｋ＝（ｇｒ，ｙｕｒ）（ｍｏｄ  ｐ）を計算する。
【０２９０】
ステップ２０４において、Ｕが１つのメッセージとしてａｐｋを取得し、ｓ＝ＳＩＧ（ａｐｋ，ＰＫｇ，ＳＫｕ）として匿名の公開鍵ａｐｋにデジタル署名する。
上記のように、ｓがａｐｋについてのグループ署名であることは明らかである。
【０２９１】
ステップ２０５において、Ｕが確認用に立証者にｓとａｐｋを送る。また、立証者は、ステップ２０６において、ユーザの匿名公開鍵を証明する。
ＶＥＲＩＦ（ｓ，ａｐｋ，ＰＫｇ）が有効な応答を出力するので、ａｐｋは、匿名のグループ・メンバーによってデジタル署名されるよう立証者に受け入れられる。したがって、ｓは、匿名のグループ・メンバーが匿名の公開鍵ａｐｋを所有することを保証する。すなわち、ｓは匿名の公開鍵ａｐｋについての匿名証明書である。
【０２９２】
本発明による第２の実施の形態において、ルート証明がユーザのグループ秘密鍵であることは言うまでも無い。
【０２９３】
調査が必要な場合、ｓはグループ管理者Ｍに提示される。その結果、調査アルゴリズムＴＲＡＣＥ（ｓ，ＰＫｇ，ＳＫｍ）がＵを出力するので、グループ管理者はＵの身元を決定し明かすことが可能である。
【０２９４】
上記の例において、ユーザのデータは匿名の公開鍵である。しかしながら、ユーザのデータは、唯一の公開鍵或いはユーザの他の公開鍵のような、ユーザの他のデータであってもよい。
【０２９５】
本発明による第２の実施の形態のユーザ装置は、図１７に示した装置１７０と共通である。
第２の実施の形態においては、ルート証明ユニットはグループ管理者からユーザのグループ秘密鍵を受け取る。匿名証明書生成ユニットはグループ署名によって匿名証明書を生成する。また、送信ユニットは、ネットワークに対して匿名証明書を備えるユーザのデータを送信する。第２の実施の形態のルート証明要求ユニットは、グループメンバーシップの要求を生成し、その要求をグループ管理者に送信するために使用される。
【０２９６】
上述したように、グループ署名証明アルゴリズムを通して、立証者はユーザのデータがグループ・メンバーによって証明されると確認することが可能である。しかしながら、多くの場合、立証者は、グループ・メンバーの名のもとに署名されたデータを送るユーザがデータの真の所有者か、そのデータに署名する本当のメンバーかどうかを確認する必要がある。
【０２９７】
図２１は、ユーザが従来のグループ署名機構を有するグループに属していることを立証者へ証明する処理を示す図である。
【０２９８】
図２１に示すように、最初に、立証者は呼掛けメッセージを生成し（ステップ２１１）、証明者にそれを送る。
立証者から呼掛けメッセージを受け取ると、証明者は、自身のグループ秘密鍵を使用することにより呼掛けメッセージに署名し（ステップ２１２）、立証者へ生成されたグループ署名を送る。
その後、立証者は、グループ公開鍵と一緒に証明者から受け取られたデータについてグループ署名照合を行なう（ステップ２１３）。正確な照合は、証明者がグループ内に属することを立証者に確信させる。
【０２９９】
従来のグループ署名機構では、証明者が立証者によって生成された呼掛けメッセージに応答し、オンライン上で呼掛けメッセージ用のグループ署名を計算することに注意する必要がある。グループ署名のそのようなオンライン計算は時間を要しかつコスト高である。さらに、証明者が立証者と数回連絡をとる場合、立証者は毎回新しい呼掛けメッセージを生成し、かつ証明者は数個のグループ署名を計算しなければならない。
【０３００】
本発明による第２の実施の形態の解決方法は、匿名証明書及びユーザのデータ（つまり、ユーザ自身の公開鍵）の妥当性を認証するのにより便利であり、かつ効率的である。
【０３０１】
図２２は、本発明による第２の実施の形態の解決法によって匿名証明書及び公開鍵の妥当化を検査する処理を示す図である。
【０３０２】
図２２に示すように、証明者は、グループ署名を前もって生成するために、自身のグループ秘密鍵を使用することにより公開鍵に署名する（ステップ２２１）。
証明者が立証者と連絡をとりたい場合、証明者は、生成された匿名証明書（つまりその公開鍵に対応するグループ署名）と共に公開鍵を立証者へ送る。
証明者から公開鍵および匿名証明書を受け取ると、立証者は、ユーザのデータについて匿名証明書及びグループ公開鍵によるグループ署名照合を行なう（ステップ２２２）。正確な照合は、公開鍵がグループ・メンバーによって署名されてることを立証者に確信させる。立証者が、ユーザがその公開鍵に署名する正当なグループ・メンバーであるかどうかを知りたい場合、立証者は公開鍵に関する知識を証明してくれるように証明者に依頼することができる。ステップ２２３および２２４において、知識証明が公開鍵に対して保持される。詳細な検証処理は、図１５において示される処理と同様である。証明者が公開鍵に対応する秘密鍵についての知識を立証者に証明する場合、立証者は証明者を信頼するはずである。
【０３０３】
本発明による上述した方法では、匿名証明書が、立証者の呼掛けに応じてオンライン上で計算されるのではなく、予め計算されることが明らかである。すなわち、証明者は、証明者側の計算装置が空いた時間にグループ署名を算出することが可能である。立証者と連絡をとる前に、公開鍵だけでなく複数の匿名証明書も既に利用可能である。立証者と連絡をとる場合、証明者は匿名証明書と一緒に公開鍵を立証者へ送る必要があるだけである。立証者は、匿名証明書の有効性をチェックする。その後、証明者は、立証者に公開鍵に対応する秘密鍵についての知識だけを証明する。この証明は、グループ署名の署名より非常に効率的である。
【０３０４】
図２３は、本発明による第２の実施の形態の解決法によって匿名証明書及び公開鍵の妥当性を証明する他の処理を示す図形である。
【０３０５】
立証者が正確に検査された公開鍵を格納していると仮定する。立証者が証明者から匿名証明書と一緒に公開鍵を受け取ると（ステップ２３１）、立証者は受信した公開鍵を正確に検査され格納された公開鍵と比較する（ステップ２３２）。受信した公開鍵が格納された公開鍵のうちの１つと一致する場合、立証者は、公開鍵に関する知識証明に直接進むことが可能である（ステップ２３５）。一致した公開鍵がない場合、立証者は受信した公開鍵について公開鍵及びグループ公開鍵の匿名証明書によるグループ署名照合を行なう（ステップ２３３）。受信した匿名証明書がグループ署名照合をパスした場合、立証者は、正確に検査された公開鍵として受信した公開鍵を格納する（ステップ２３４）。次に、処理はステップ２３５に進む。グループ署名照合をパスしない場合、処理は終了する。
【０３０６】
証明者が同じ匿名証明書で立証者に複数回連絡をとることを決定した場合、立証者は最初に匿名証明書の有効性をチェックする必要がある。次のセションにおいて、立証者は、証明者から受け取った公開鍵をローカルに貯えられた公開鍵と照合する。一致するものがあれば、立証者と証明者は公開鍵に関する知識証明に直接進むことが可能である。この種の利用法はとても効率的であり、かつ匿名及び信用が全て維持されている。
【０３０７】
図２４は、本発明による第２の実施の形態の証明ユニットの例を示すブロック図である。証明ユニット２４０は、立証者の計算装置に設置されるか、あるいは図１７に示した証明ユニット１７８としてユーザ装置に設置される。
【０３０８】
証明ユニット２４０は、グループ署名及び公開鍵についての照合を行なうために照合モジュール２４５を備える。照合モジュール２４５は、グループ署名照合部２４１及び公開鍵知識照合部２４２に分割されている。証明者からのグループ署名と対になった公開鍵を受け取った時、照合モジュール２４５は、受信した公開鍵及びグループ公開鍵を使用することにより、グループ署名照合部２４１でグループ署名を照合する。証明者から受け取った公開鍵がグループ署名照合部２４１によって正確に照合された後、公開鍵知識照合部２４２はグループ署名と共に受け取った公開鍵に関する証明者について知識証明を実行する。
【０３０９】
証明ユニット２４０は、照合モジュール２４５に接続されたメモリ２４３と、照合モジュール２４５及びメモリ２４３に接続された比較モジュール２４４をさらに備える。メモリ２４３は、予め正確に検査された公開鍵を格納する。証明者から公開鍵及びグループ署名を受け取った場合、比較モジュール２４４は、受信した公開鍵をメモリ２４３に格納された公開鍵と比較し、比較の結果を照合モジュール２４５に通知する。受信した公開鍵が予め正確に検査された公開鍵のうちの１つと同じである場合、照合モジュール２４５は、グループ署名照合アルゴリズムの計算をスキップし、公開鍵知識照合部２４２によって、証明者についてグループ署名と共に受け取られた公開鍵に関する知識証明を実行する。受信した公開鍵が格納された公開鍵のうちの１つと一致しない場合、照合モジュール２４５は、グループ署名照合部２４１によって上述したようなグループ署名照合アルゴリズムの計算を実行する。
【０３１０】
本発明によれば、信用された主体がＣＡである場合、証明書と公開鍵についての照合は同様の方法で実行することが可能である。図１５を参照すると、匿名の公開鍵及び匿名証明書がユーザによって計算された後、匿名の公開鍵は、備えられた匿名証明書と共に立証者へ送られる（ステップ１５１）。その後、立証者は、匿名証明書及び匿名の公開鍵を検査するためにユーザについて知識証明を実行する（ステップ１５３）。ステップ１５３に示されるように、本発明では、匿名証明書及び匿名の公開鍵を一回の知識証明で一緒に検査することが可能である。１つの実施例では、ユーザはオフラインの方法で匿名の公開鍵、匿名証明書、及び知識証明に必要なデータを計算する。そのようなデータを受け取った後に、立証者はローカルの計算を通じて匿名証明書及び公開鍵を検査することが可能である。他の実施例では、立証者は、常時正確に検査される公開鍵を格納する。ユーザによって送信された証明書と公開鍵を検査する度に、立証者は、まずユーザの公開鍵を格納されたものと比較する。一致が得られる場合、それは公開鍵が正確に検査されるものであることを意味する。ユーザについての知識証明中に、立証者は、証明書に関する知識証明の計算をバイパスすると思われる。ユーザについての公開鍵に関する証明だけが必要である。従来の解決方法における証明書と公開鍵のオンライン照合と順次進行型の照合と比較して、本発明による上述した照合はより効率的である。
【０３１１】
信用された主体がＣＡである場合、立証者の装置中の証明ユニットはさらに照合モジュールを含む。１つの実施例によれば、証明ユニットは、例えば、図１５のステップ１５３に示されるような知識証明を実行する。他の実施例では、証明ユニットは、さらに、照合モジュールに接続されるメモリと、照合モジュール及びメモリに接続される比較モジュールを備えることが可能である。
そのメモリは、正確に検査された公開鍵を格納する。証明者から証明書と公開鍵を受け取ると、比較モジュールは、受信した公開鍵をメモリに格納された公開鍵と比較し、その比較の結果を照合モジュールに通知する。受信した公開鍵が予め正確に検査された公開鍵のうちの１つと同じである場合、照合モジュールは証明書に関する知識証明の計算をスキップし、単に証明者について公開鍵に関する知識証明を実行する。また、例えば、受信した公開鍵が格納された公開鍵のうちの１つと一致しない場合、図１５のステップ１５３に示されるように、照合モジュールは証明書と公開鍵に関する知識証明の計算を実行する。
【０３１２】
本発明による２つの場合について、証明書及びユーザのデータの照合のための方法及び装置を説明したが、本発明は上述した具体例に限定されない。当業者によれば、特定のアプリケーションやアルゴリズムに従って、照合のための方法と装置についての変形と変更を加えることが可能である。
【０３１３】
本発明によれば、匿名の公開鍵が信用された主体によって証明される匿名証明書によって保証される場合、ユーザは信頼できる匿名の公開鍵を生成することが可能であることが、上述した説明から理解できる。ユーザ・プライバシ保護の機能は完全に施される。ユーザは、自身による別個の匿名の公開鍵だけでなく、自身による別個の匿名証明書を生成する。本発明による実施の形態において、ＣＡの介在は最小限である。よって、信用された主体の負荷の軽減化を実現することが可能である。さらに、匿名証明書はＣＡ或いはグループ管理者レベルで追跡可能であるので、ユーザが匿名性を乱用するのは不可能である。
【０３１４】
本発明は、ハードウェア、ソフトウェア、ファームウェア或いはそれらの組合せによって実現することができ、システム、サブシステム、構成要素あるいはサブ構成要素において利用することができる。ソフトウェアで実現される場合、本発明の要素は本質的にプログラム、あるいは必要なタスクを実行するのに使用される命令セグメントである。プログラム又は命令セグメントは、コンピュータ読み取り可能な媒体に格納されるか、あるいは伝送ケーブル又は通信リンク上の搬送波であるたデータ信号によって送信される。「コンピュータ読み取り可能な媒体」は、情報を格納するか転送することができる任意の媒体を含む。コンピュータ読み取り可能な媒体の例としては、電子回路、半導体記憶装置、ＲＯＭ、フラッシュ・メモリ、消去可能なＲＯＭ（ＥＲＯＭ）、フロッピーディスケット、ＣＤ−ＲＯＭ、光ディスク、ハードディスク、光ファイバー媒体、無線（ＲＦ）リンクなどが含まれる。データ信号は、電子ネットワークチャネル、光ファイバ、空気、電磁気、ＲＦリンク等の伝送媒体上で伝播することが可能な任意の信号を含む。命令セグメントは、インターネット、イントラネット等のようなコンピュータネットワークを介してダウンロードすることが可能である。
【０３１５】
本発明は、その思想あるいは本質的特徴から外れない範囲で、他の特定の態様において具体化されることも可能である。例えば、システムアーキテクチャーが本発明の基本的な特徴を外れない限り、実施の形態において説明したアルゴリズムは変更することができる。また、本実施例は、全ての点において具体的な例として考慮され、限定的に考慮されるものではない。また、本発明の範囲は、実施例の記載ではなく請求の範囲によって示される。さらにクレームと同等の意味及び範囲内に含まれる全ての変形例は本発明に包含される。
【図面の簡単な説明】
【０３１６】
本発明の前述の目的及び他の目的、本発明の本質及び本発明の各特徴は、以下に述べる説明を添付図面と共に読まれることにより十分に理解されるだろう。
【図１】ＡＰＫ方法によって秘匿化する公開鍵暗号方式を用いる２つの端末装置(端末装置のうちの一方が、他方の端末装置との新しい通信セッション用の種々の公開鍵を公開する)を備えた好適なシステムを示すブロック図である。
【図２】ＡＰＫ方法によって秘匿化する公開鍵暗号方式を用いるいくつかの端末装置(ある端末装置が、異なる通信用に異なる公開鍵を有する他の端末装置と通信する)を備えた好適なシステムの例を示す図である。
【図３】図１と図２で例をあげて説明した通信システムに参加する送信機と受信機の間の好適な通信セッション例を示す図である。
【図４】ＡＰＫ方法による公開鍵−秘密鍵のペアに基づいた通信セッションにおける送信機と受信機の好適な機能ブロック図である。
【図５】ＡＰＫ方法による図４に示すＡＰＫ生成装置の好適な機能ブロック図である。
【図６】秘匿化された公開鍵を生成するＡＰＫ方法による生成フローを示すフローチャートである。
【図７】ＡＰＫ方法によるメッセージの暗号化及び復号化の好適な手続き例を示す図である。
【図８Ａ】本発明の一般的概念を概略的に示すブロック図である。
【図８Ｂ】本発明の一般的な検証プロセスを概略的に示すフローチャートである。
【図９】本発明の第１の実施の形態によるシステム構成の概要を示すブロック図である。
【図１０】第１の実施の形態によるシステムスタートアップ段階におけるＣＡ初期化プロセスの例を示すフローチャートである。
【図１１】第１の実施の形態によるシステムスタートアップ段階中にユーザ初期化プロセスの例を示すフローチャートである。
【図１２】第１の実施の形態によるＲＣ要求プロセスの例を示すフローチャートである。
【図１３】ユーザが第１の実施の形態に従ってどのように匿名の公開鍵を生成するかを示すフローチャートである。
【図１４】第１の実施の形態による匿名の公開鍵のためのルート証明書からユーザがどのように匿名証明書を取得するかを示すフローチャートである。
【図１５】第１の実施の形態による匿名の認証プロセスの例を示すフローチャートである。
【図１６】第１の実施の形態による検査プロセスを示すフローチャートである。
【図１７】第１の実施の形態によるユーザ装置の構成を示すブロック図である。
【図１８】第１の実施の形態によるＣＡ側装置の構成を示すブロック図である。
【図１９】本発明の第２の実施の形態によるシステム構成の概要を示すブロック図である。
【図２０】第２の実施の形態による匿名を証明する方法の例を示すフローチャートである。
【図２１】ユーザが従来のグループ署名機構を有するグループに属していることを立証者へ証明する処理を示す図である。
【図２２】本発明による第２の実施の形態の解決法によって匿名証明書及び公開鍵の妥当化を検査する処理を示す図である。
【図２３】本発明による第２の実施の形態の解決法によって匿名証明書及び公開鍵の妥当化を検査する他の処理を示す図である。
【図２４】本発明による第２の実施の形態の証明ユニットの例を示すブロック図である。
【図２５】証明書が証明書機関（Ｃｅｒｔｉｆｉｃａｔｅ  Ａｕｔｈｏｒｉｔｙ）によって発行される従来の証明書システムを示すブロック図である。
【図２６】証明書がユーザの友人によって発行される従来の他の証明書システムを示すブロック図である。
【符号の説明】
【０３１７】
Ａ、ａ，ｂ，・・・，ｚ１０：端末装置
Ｅ，Ｅａ，Ｅｂ，・・・，Ｅｚ：公開鍵
ｘ，ｘａ，ｘｂ，ｘｃ，・・・，ｘｚ：秘密鍵
４１：送信機
４２：受信機
４３，４４：送信装置
４５，４６：受信装置
４７：復号化装置
４８：暗号化装置
４９：公開鍵生成装置
５１：グループ選択手段
５２：部分グループ選択手段
５３：ジェネレータ選択手段
５４：記憶部
５５：制御装置
５６：整数選択手段
５７：グループ指数演算子
【図１】
2007089171.tif 000033
【図２】
2007089171.tif 000034
【図３】
2007089171.tif 000035
【図４】
2007089171.tif 000036
【図５】
2007089171.tif 000037
【図６】
2007089171.tif 000038
【図７】
2007089171.tif 000039
【図８Ａ】
2007089171.tif 000040
【図８Ｂ】
2007089171.tif 000041
【図９】
2007089171.tif 000042
【図１０】
2007089171.tif 000043
【図１１】
2007089171.tif 000044
【図１２】
2007089171.tif 000045
【図１３】
2007089171.tif 000046
【図１４】
2007089171.tif 000047
【図１５】
2007089171.tif 000048
【図１６】
2007089171.tif 000049
【図１７】
2007089171.tif 000050
【図１８】
2007089171.tif 000051
【図１９】
2007089171.tif 000052
【図２０】
2007089171.tif 000053
【図２１】
2007089171.tif 000054
【図２２】
2007089171.tif 000055
【図２３】
2007089171.tif 000056
【図２４】
2007089171.tif 000057
【図２５】
2007089171.tif 000058
【図２６】
2007089171.tif 000059
【誤訳訂正書】
【提出日】平成18年11月29日(2006.11.29)
【誤訳訂正１】
【訂正対象書類名】特許請求の範囲
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【特許請求の範囲】
【請求項１】
通信ネットワーク上でデータを証明するユーザのコンピュータ装置であって、
前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、
前記コンピュータ装置が、
前記ネットワークに接続された、前記信用機関側装置からルート証明を受け取るためのルート証明ユニット、
前記ルート証明ユニットに接続された、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するための匿名証明書生成ユニット、
前記匿名証明書生成ユニットに接続された、前記通信ネットワークに前記匿名証明書と共に前記ユーザデータを送信するための送信ユニットを備えることを特徴とするコンピュータ装置。
【請求項２】
前記匿名証明書は、立証者側が前記ユーザの本当の身元を見抜くことを可能とする如何なる情報も含まないように生成されることを特徴とする請求項１に記載のコンピュータ装置。
【請求項３】
前記ユーザのデータが、前記ユーザの公開鍵を含むことを特徴とする請求の１に記載のコンピュータ装置。
【請求項４】
前記ユーザのデータに含まれる前記公開鍵が、唯一無比の公開鍵であることを特徴とする請求項３に記載のコンピュータ装置。
【請求項５】
前記ユーザのデータを含まれる前記公開鍵が、匿名の公開鍵であり、
前記コンピュータ装置が、前記送信ユニットに接続された、前記ユーザの複数の匿名の公開鍵を生成するための匿名公開鍵生成ユニットをさらに備え、
前記複数の匿名の公開鍵が前記ユーザの秘密鍵に対応していることを特徴とする請求項３に記載のコンピュータ装置。
【請求項６】
前記匿名公開鍵生成ユニットは、前記秘密鍵及びジェネレータから複数の匿名の公開鍵を生成し、前記秘密鍵と前記ジェネレータが予め定義されたグループに属することを特徴とする請求項５に記載のコンピュータ装置。
【請求項７】
前記ルート証明が、前記信用機関側装置によって前記ユーザに発行されたルート証明書であることを特徴とする請求項１に記載のコンピュータ装置。
【請求項８】
前記ルート証明が、前記ユーザのグループ秘密鍵であり、前記匿名証明書が、前記ユーザのデータのグループ署名であることを特徴とする請求項１に記載のコンピュータ装置。
【請求項９】
前記ネットワークに接続された、前記ルート証明のための要求を生成し、かつ前記信用機関側装置に要求を送信するためのルート証明要求ユニットをさらに備えることを特徴とする請求項１に記載のコンピュータ装置。
【請求項１０】
前記ネットワークに接続された、前記信用機関側装置あるいは前記立証者側装置と共に知識証明を実行するための検証ユニットをさらに備えることを特徴とする請求項１に記載のコンピュータ装置。
【請求項１１】
ユーザが通信ネットワーク上でデータを証明する方法であって、
前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、
前記信用機関側装置からルート証明を受信するステップと、
前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するステップと、
前記立証者側装置に前記匿名証明書を含む前記ユーザのデータを送信するステップとを有することを特徴とする証明方法。
【請求項１２】
前記匿名証明書は、立証者側が前記ユーザの本当の身元を見抜くことを可能とする如何なる情報も含まないように生成されることを特徴とする請求項１１に記載の証明方法。
【請求項１３】
前記ユーザのデータが、前記ユーザの公開鍵を含むことを特徴とする請求の１１に記載の証明方法。
【請求項１４】
前記ユーザのデータに含まれる前記公開鍵が、唯一無比の公開鍵であることを特徴とする請求項１３に記載の証明方法。
【請求項１５】
前記ユーザのデータを含まれる前記公開鍵が、匿名の公開鍵であり、
前記ユーザの複数の匿名の公開鍵を生成するステップをさらに有し、
前記複数の匿名の公開鍵が前記ユーザの秘密鍵に対応していることを特徴とする請求項１３に記載の証明方法。
【請求項１６】
複数の匿名の公開鍵が前記秘密鍵及びジェネレータから生成され、前記秘密鍵と前記ジェネレータが予め定義されたグループに属することを特徴とする請求項１５に記載の証明方法。
【請求項１７】
前記ルート証明が、前記信用機関側装置によって前記ユーザに発行されたルート証明書であることを特徴とする請求項１１に記載の証明方法。
【請求項１８】
前記ルート証明が、前記ユーザのグループ秘密鍵であり、前記匿名証明書が、前記ユーザのデータのグループ署名であることを特徴とする請求項１１に記載の証明方法。
【請求項１９】
前記ネットワークに接続された、前記ルート証明のための要求を生成し、かつ前記信用機関側装置に要求を送信するためのルート証明要求ユニットをさらに備えることを特徴とする請求項１１に記載の証明方法。
【請求項２０】
前記ネットワークに接続された、前記信用機関側装置あるいは前記立証者側装置と共に知識証明を実行するための検証ユニットをさらに備えることを特徴とする請求項１１に記載の証明方法。
【請求項２１】
通信ネットワーク上で証明書を処理する処理装置であって、
前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、
前記処理装置が、
システムパラメータを計算するためのシステムパラメータ計算ユニットと、
前記システムパラメータ計算ユニットに接続された、ユーザ側装置及び前記立証者側装置によって共有されるシステムパラメ−タを発行するためのパラメータ発行ユニットと、
前記ネットワークに接続された、前記ユーザ側装置からルート証明要求を受け取るためのルート証明要求受信ユニットと、
前記ルート証明要求受信ユニット及び前記システムパラメータ計算ユニットに接続された、前記ルート証明要求に応じて前記ユーザのためのルート証明を生成するためのルート証明生成ユニットとを備え、
前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする処理装置。
【請求項２２】
前記ルート証明が、前記ユーザの公開鍵に対して発行されたルート証明書であることを特徴とする請求項２１に記載の処理装置。
【請求項２３】
前記ルート証明が、前記ユーザの匿名の公開鍵に対して発行されたルート証明書であることを特徴とする請求項２１に記載の処理装置。
【請求項２４】
前記ルート証明が、前記ユーザに対して発行されたグループ秘密鍵であることを特徴とする請求項２１に記載の処理装置。
【請求項２５】
前記ルート証明生成ユニットに接続された、前記ルート証明要求について識別検査を行なうための検査ユニットをさらに備えることを特徴とする請求項２１に記載の処理装置。
【請求項２６】
前記ネットワークに接続された、前記ルート証明に基づいて前記立証者側装置から受信した匿名証明書の所有者の身元を調査するための調査ユニットをさらに備えることを特徴とする請求項２１に記載の処理装置。
【請求項２７】
通信ネットワーク上で証明書を処理する処理方法であって、
前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、
システムパラメータを計算するステップと、
ユーザ側装置及び前記立証者側装置によって共有されるシステムパラメータを発行するステップと、
前記ユーザからルート証明要求を受け取るステップと、
前記ルート証明要求に応じて前記ユーザのためのルート証明を生成するステプを有し、
前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする処理方法。
【請求項２８】
前記ルート証明が、前記ユーザの公開鍵に対して発行されたルート証明書であることを特徴とする請求項２７に記載の処理方法。
【請求項２９】
前記ルート証明が、前記ユーザの匿名の公開鍵に対して発行されたルート証明書であることを特徴とする請求項２７に記載の処理方法。
【請求項３０】
前記ルート証明が、前記ユーザに対して発行されたグループ秘密鍵であることを特徴とする請求項２７に記載の処理方法。
【請求項３１】
前記ルート証明要求を受信した後、前記ルート証明要求について識別検査を実行することを特徴とする請求項２７に記載の処理方法。
【請求項３２】
前記ルート証明に基づいて前記立証者側装置から受信した匿名証明書の所有者の身元を調査するステプをさらに有することを特徴とする請求項２７に記載の処理方法。
【請求項３３】
通信ネットワーク上のユーザのための匿名証明書システムであって、
前記ネットワーク内に信用機関側装置を含み、
前記ネットワークに接続された、前記信用機関側装置からルート証明を受け取るためのルート証明ユニット、
前記ルート証明ユニットに接続された、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するための匿名証明書生成ユニット、
前記匿名証明書生成ユニットに接続された、前記通信ネットワークに前記匿名証明書と共に前記ユーザデータを送信するための送信ユニット
前記通信ネットワークに接続された、受信した匿名証明書によってユーザのデータを検査するための前記立証者側ユニットを備えることを特徴とする匿名証明書システム。
【請求項３４】
前記匿名証明書は、立証者が前記ユーザの本当の身元を見抜くことを可能とする如何なる情報も含まないように生成されることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項３５】
前記ユーザのデータが、前記ユーザの公開鍵を含むことを特徴とする請求の３３に記載の匿名証明書システム。
【請求項３６】
前記ユーザのデータに含まれる前記公開鍵が、唯一無比の公開鍵であることを特徴とする請求項３５に記載の匿名証明書システム。
【請求項３７】
前記ユーザのデータを含まれる前記公開鍵が、匿名の公開鍵であり、
前記システムが、前記送信ユニットに接続された、前記ユーザの複数の匿名の公開鍵を生成するための匿名公開鍵生成ユニットをさらに備え、
前記複数の匿名の公開鍵が前記ユーザの秘密鍵に対応していることを特徴とする請求項３５に記載の匿名証明書システム。
【請求項３８】
前記匿名公開鍵生成ユニットは、前記秘密鍵及びジェネレータから複数の匿名の公開鍵を生成し、前記秘密鍵と前記ジェネレータが予め定義されたグループに属することを特徴とする請求項３７に記載の匿名証明書システム。
【請求項３９】
前記ルート証明が、前記信用機関側装置によって前記ユーザに発行されたルート証明書であることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４０】
前記ルート証明が、前記ユーザのグループ秘密鍵であり、前記匿名証明書が、前記ユーザのデータのグループ署名であることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４１】
前記立証者側ユニットが、前記匿名証明書および前記ユーザのデータについて照合を行なうための照合モジュールをさらに備えることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４２】
前記立証者側ユニットが、
前記照合モジュールに接続された、正確に検査されたデータを格納するメモリと、
前記メモリと前記照合モジュールに接続された、受信した前記ユーザのデータを前記格納したデータと比較する比較モジュールをさらに備えることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４３】
前記立証者側ユニットに接続された、前記ルート証明に基づいて前記立証者側ユニットから受信した匿名証明書の所有者の身元を調査するための調査ユニットをさらに備えることを特徴とする請求項３３に記載の匿名証明書システム。
【請求項４４】
通信ネットワーク上で匿名証明書によってユーザのデータを証明する方法であって、
前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、
前記信用機関側装置からユーザ側装置にルート証明を発行するステップと、
前記ユーザ側装置による前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するステップと、
前記立証者側装置に前記匿名証明書を含む前記ユーザのデータを送信するステップを有し、
前記立証者側装置が、前記匿名証明書によって前記ユーザのデータを検査することを特徴とする証明方法。
【請求項４５】
前記匿名証明書は、立証者が前記ユーザの本当の身元を見抜くことを可能とする如何なる情報も含まないように生成されることを特徴とする請求項４４に記載の証明方法。
【請求項４６】
前記ユーザのデータが、前記ユーザの公開鍵を含むことを特徴とする請求の４４に記載の証明方法。
【請求項４７】
前記ユーザのデータに含まれる前記公開鍵が、唯一無比の公開鍵であることを特徴とする請求項４６に記載の証明方法。
【請求項４８】
前記ユーザのデータを含まれる前記公開鍵が、匿名の公開鍵であり、
前記ユーザの複数の匿名の公開鍵を生成するステップをさらに有し、
前記複数の匿名の公開鍵が前記ユーザの秘密鍵に対応していることを特徴とする請求項４６に記載の証明方法。
【請求項４９】
前記秘密鍵及びジェネレータから複数の匿名の公開鍵を生成し、前記秘密鍵と前記ジェネレータが予め定義されたグループに属することを特徴とする請求項４８に記載の証明方法。
【請求項５０】
前記ルート証明の発行が、前記ユーザの公開鍵に対してルート証明書を発行するステップを含むことを特徴とする請求項４４に記載の証明方法。
【請求項５１】
前記ルート証明の発行が、前記ユーザ側装置に対してグループ秘密鍵を発行するステップを含み、
少なくとも１つの匿名証明書の生成が、前記ユーザのデータのグループ署名を生成するステップを含むことを特徴とする請求項４４に記載の証明方法。
【請求項５２】
前記立証者側装置が、前記ユーザ側装置と知識証明を行なうことにより前記匿名証明書及び前記ユーザのデータを検査することを特徴とする請求項４４に記載の証明方法。
【請求項５３】
前記立証者側装置による前記匿名証明書及び前記ユーザのデータの検査が、
前記立証者側装置によって正確に検査されたデータを格納するステップ、
前記格納データを前記ユーザ側装置から受信したユーザのデータと比較するステップ、
前記ユーザのデータが前記記憶データのうちの１つと一致すれば、前記ユーザ側装置と共に前記ユーザのデータに関する知識証明を実行するステップ、
前記ユーザのデータが前記記憶データのうちの１つと一致しない場合、前記匿名証明書及び前記ユーザのデータについて照合を実行するステップとを有することを特徴とする請求項４４に記載の証明方法。
【請求項５４】
前記ルート証明に基づいて前記立証者側装置から受信した匿名証明書の所有者の身元を調査するステプをさらに有することを特徴とする請求項４４に記載の処理方法。
【請求項５５】
ユーザが通信ネットワーク上でデータを証明するためにコンピュータ上で実行される証明プログラムであって、
前記コンピュータに、
前記信用機関側装置からルート証明を受信する処理と、
前記ルート証明に基づいて少なくとも１つの匿名証明書を生成する処理と、
前記立証者側装置に前記匿名証明書を含む前記ユーザのデータを送信する処理を実行させることを特徴とする証明プログラム。
【請求項５６】
前記データが匿名の公開鍵であることを特徴とする請求項５５に記載の証明プログラム。
【請求項５７】
ユーザが通信ネットワーク上でデータを証明するためにコンピュータ上で実行される証明プログラムであって、
前記コンピュータに、
システムパラメータを計算する処理と、
ユーザ側装置及び前記立証者側装置によって共有されるシステムパラメータを発行する処理と、
前記ユーザ側装置からルート証明要求を受け取る処理と、
前記ルート証明要求に応じて前記ユーザのためのルート証明を生成する処理を実行させ、
前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする証明プログラム。
【請求項５８】
前記ルート証明が、前記ユーザの匿名の公開鍵についてのルート証明書であることを特徴とする請求項５７に記載の証明プログラム。
【誤訳訂正２】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ通信ネットワークセキュリティに関し、特に、プライバシーを保護する通信システム及びその通信方法に関する。
【背景技術】
【０００２】
現在、公開鍵暗号方式は広く使用される。従来、多くの公開鍵の暗号化及び復号化の技術は、プライバシーの場合と同程度のセキュリティを容易に提供することが可能である。例えば、Rivestらによる米国特許4,405,829号、及びEI
Gamalらによる分離対数に基づいた公開鍵暗号方式および署名スキーム(Tahir EIGamal. A public-key cryptosystem and
a signature scheme based on discrete logarithms.  Advances in Cryptology Proceedings of CRYPTO 84, pages
10-18, 1985)に開示された技術は、当該技術分野で広く知られた技術である。上記Rivestによる特許およびEI  Gamalの技術を引用して説明する。
【０００３】
RSA方式やEI
Gamalのような従来の公開鍵暗号方式によって安全に他者と通信するためには、ユーザは外部に自身の公開鍵を公開することが要求される。しかし、多くの場合、ユーザは、1つの公開鍵と秘密鍵のペア、すなわち、１つの公開鍵とそれに対応する唯一の秘密鍵とを所有するだけである。公開鍵暗号方式のこの従来の簡易な使用法は、ユーザの公開鍵をユーザの識別情報として適切に機能させるとという偶発的な結果を生じる。それは、たとえ十分に計画された他のプライバシー保護基準のみならずこの種の公開鍵暗号方式によってユーザに関するプライバシーが保護されるとしても、悪意ある者が、唯一の公開鍵についての使用パターンに基づいてユーザによって公表された情報を収集して観察することを通じて、保護されているユーザの活動を把握することが依然可能なことを意味する。
【０００４】
RSA方式及びEI  Gamalによって示されているような従来の公開鍵暗号方式の範囲内で、ユーザが、自身の単一の公開鍵によって自身のプライバシーがあばかれるかもしれないと懸念する場合、１つの可能な解決策は、いくつかの異なる公開鍵を所有し、各公開鍵を異なる通信者に用心して公開することを関係者に要請することである。
【０００５】
多くの公開鍵ペアの所有に加えて、Watersらは、ユーザが単一の秘密鍵に対応する幾つかの公開鍵を同時に所有することができるようにする唯一無比の公開鍵スキーム（仕組み）を実現するために、Ei
Gamalによる暗号化方式を用いる方法を提案している。B.R.Waters、E.W.Felten、A.Sahai、「唯一無比の公開鍵を介した受信者の秘匿化（Receiver
Anonymity via Incomparable Public keys）」、CCS'03、Washigton  DC、USA、pp.112〜121) (以下に、Waters)を参照。上記Watersに開示される技術を引用して説明する。
【０００６】
上述したように、ユーザは数個の公開鍵を所有してもよい。しかしながら、多くの場合、人物Ａが公開鍵を得る場合、誰か他の者が公開鍵を証明しなければならない。例えば、公開鍵はよく知られている証明書機関（Ｃｅｒｔｉｆｉｃａｔｅ  Ａｕｔｈｏｒｉｔｙ）（ＣＡ）で証明することが可能であるし、或いはその人物の友人Ｃによって証明することが可能である。第３の人物Ｂが公開鍵とその証明書を見る場合、ＢがＣＡを信用し、或いはＢ友人Ｃを信用するいずれの場合でも、人物はその公開鍵を信用する。
【０００７】
ユーザが数個の公開鍵を所有する時に、それらの公開鍵を証明する１つの可能な方法は、図２５に示されるように、それらの公開鍵を証明してくれるようにＣＡ（信用機関）に依頼することである。ＣＡは全ての証明書要求を全てオンラインで処理するので、ＣＡに非常に高い能力が必要とされ、所有権とメンテナンスの点からコストが増大している。ネットワーク上のユーザがそれぞれ多数の公開鍵を所有する場合、そのようなコストがさらに増大する。
【０００８】
他の可能性は、図２６に示されるように、公開鍵の各々を証明してくれるように何人かの友人に依頼することである。しかしながら、これはユーザのプライバシー保護と相容れない。それだけでなく、公開鍵を証明してくれるように友人に依頼することは非能率的でかつ効果がないだけでなく、多くのビジネスの場面において信用されない。
【０００９】
公開鍵の検証に加えて、ＣＡを中心にした解決方法及び友人による証明方法からなる方法の上述した欠点は、数個の利用者データを証明する必要のある他の多くの状況にも存在する。
【特許文献１】米国特許第４，４０５，８２９号
【非特許文献１】EI Gamalらによる分離対数に基づいた公開鍵暗号方式および署名スキーム(Tahir EIGamal. A public-keycryptosystem and a signature scheme based on discrete logarithms.  Advances in Cryptology Proceedings ofCRYPTO 84, pages 10-18, 1985)
【非特許文献２】B.R.Waters、E.W.Felten、A.Sahai、「唯一無比の公開鍵を介した受信者の秘匿化（ReceiverAnonymity via Incomparable Public keys）」、CCS'03、Washigton  DC、USA、pp.112〜121)
【非特許文献３】応用暗号学のハンドブック（Handbook of Applied Cryptography）(http://www.cacr.math.uwaterloo.ca/hac/)
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、順応性のある匿名証明書システム及び通信ネットワーク上の証明方法を提供する。
【課題を解決するための手段】
【００１１】
本発明によれば、通信ネットワーク上でデータを証明するユーザのコンピュータ装置であって、前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、前記コンピュータ装置が、前記ネットワークに接続された、前記信用機関側装置からルート証明を受け取るためのルート証明ユニット、前記ルート証明ユニットに接続された、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するための匿名証明書生成ユニット、前記匿名証明書生成ユニットに接続された、前記通信ネットワークに前記匿名証明書と共に前記ユーザデータを送信するための送信ユニットを備えることを特徴とする。
【００１２】
他の本発明によれば、ユーザが通信ネットワーク上でデータを証明する方法であって、前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、前記信用機関側装置からルート証明を受信するステップと、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するステップと、前記立証者側装置に前記匿名証明書を含む前記ユーザのデータを送信するステップとを有することを特徴とする。
【００１３】
さらに他の本発明によれば、通信ネットワーク上で証明書を処理する処理装置であって、前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、前記処理装置が、システムパラメータを計算するためのシステムパラメータ計算ユニットと、前記システムパラメータ計算ユニットに接続された、ユーザ側装置及び前記立証者側装置によって共有されるシステムパラメータを発行するためのパラメータ発行ユニットと、前記ネットワークに接続された、前記ユーザ側装置からルート証明要求を受け取るためのルート証明要求受信ユニットと、前記ルート証明要求受信ユニット及び前記システムパラメータ計算ユニットに接続された、前記ルート証明要求に応じて前記ユーザのためのルート証明を生成するためのルート証明生成ユニットとを備え、前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする。
【００１４】
さらに他の本発明によれば、通信ネットワーク上で証明書を処理する処理方法であって、前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、システムパラメータを計算するステップと、ユーザ側装置及び前記立証者側装置によって共有されるシステムパラメータを発行するステップと、前記ユーザ側装置からルート証明要求を受け取るステップと、前記ルート証明要求に応じて前記ユーザのためのルート証明を生成するステプを有し、前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする。
【００１５】
さらに他の本発明によれば、通信ネットワーク上のユーザのための匿名証明書システムであって、前記ネットワーク内に信用機関側装置を含み、前記ネットワークに接続された、前記信用機関側装置からルート証明を受け取るためのルート証明ユニット、前記ルート証明ユニットに接続された、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するための匿名証明書生成ユニット、前記匿名証明書生成ユニットに接続された、前記通信ネットワークに前記匿名証明書と共に前記ユーザデータを送信するための送信ユニット前記通信ネットワークに接続された、受信した匿名証明書によってユーザのデータを検査するための前記立証者側ユニットを備えることを特徴とする。
【００１６】
さらに他の本発明によれば、通信ネットワーク上で匿名証明書によってユーザのデータを証明する方法であって、前記ネットワーク内に信用機関側装置と少なくとも１つの立証者側装置を含み、前記信用機関側装置からユーザ側装置にルート証明を発行するステップと、前記ユーザ側装置による前記ルート証明に基づいて少なくとも１つの匿名証明書を生成するステップと、前記立証者側装置に前記匿名証明書を含む前記ユーザのデータを送信するステップを有し、前記立証者側装置が、前記匿名証明書によって前記ユーザのデータを検査することを特徴とする。
【００１７】
さらに他の本発明によれば、ユーザが通信ネットワーク上でデータを証明するためにコンピュータ上で実行される証明プログラムであって、前記コンピュータに、前記信用機関側装置からルート証明を受信する処理と、前記ルート証明に基づいて少なくとも１つの匿名証明書を生成する処理と、前記立証者側装置に前記匿名証明書を含む前記ユーザのデータを送信する処理を実行させることを特徴とする。
【００１８】
さらに他の本発明によれば、ユーザが通信ネットワーク上でデータを証明するためにコンピュータ上で実行される証明プログラムであって、前記コンピュータに、システムパラメータを計算する処理と、ユーザ側装置及び前記立証者側装置によって共有されるシステムパラメータを発行する処理と、前記ユーザ側装置からルート証明要求を受け取る処理と、前記ルート証明要求に応じて前記ユーザのためのルート証明を生成する処理を実行させ、前記ルート証明は複数の匿名証明書を生成する前記ユーザのために使用されることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、匿名の公開鍵が信用機関によって証明される匿名証明書によって保証される場合、ユーザは信頼できる匿名の公開鍵を生成することが可能であることが、上述した説明から理解できる。ユーザ・プライバシ保護の機能は完全に施される。ユーザは、自身による別個の匿名の公開鍵だけでなく、自身による別個の匿名証明書を生成する。本発明による実施の形態において、ＣＡの介在は最小限である。よって、信用機関の負荷の軽減化を実現することが可能である。さらに、匿名証明書はＣＡ或いはグループ管理者レベルで追跡可能であるので、ユーザが匿名性を乱用するのは不可能である。
【発明を実施するための最良の形態】
【００２０】
（秘匿化した公開鍵）
この出願は、この出願は、Ｋｅ  ＺＥＮＧ及びTomoyuki FUJITAによって発明された新たしい匿名の公開鍵（Ａｎｏｎｙｍｏｕｓ  Ｐｕｂｌｉｃ  Ｋｅｙ）（ＡＰＫ）方式に関するものである。ＡＰＫ方式の詳細な内容は、出願中の中国特許出願No.
200410090903.X（出願日：２００４年１１月１０日、出願人：NEC (China) Co., Ltd、発明の名称：「セキュリティ通信システムにおける秘匿化した公開鍵を生成する方法、装置及びシステム」）に記載されている。
【００２１】
まず、ＡＰＫの技術的解決方法について以下に説明する。
【００２２】
上述したように、ユーザはいくつかの公開鍵を所有することを欲する可能性がある。別個の公開鍵がそれぞれ対応する別個の秘密鍵を有する複数の公開鍵ペアを使用することによって、従来の公開鍵暗号方式では、ある程度までプライバシー問題を軽減することが可能である。しかしながら、公開鍵の数が増加するに伴って、個人のための公開鍵ペアの管理コストが増大する。
さらに、秘密鍵の数の増加に伴って、秘密鍵の紛失或いは露見といったセキュリティ上の危険性が増加する。
【００２３】
EI Gamalの暗号方式による公開鍵を構成するための種々のジェネレータを用いることによって、新しい公開鍵を生成するけれども、それは計算における最適化を困難にする。例えば、（ｇ，  ｇａ）と（ｈ，  ｈａ）がWatersの唯一無比の唯一無比の公開鍵方式（Ｉｎｃｏｍｐａｒａｂｌｅ  Ｐｕｂｌｉｃ  Ｋｅｙｓ  Ｓｃｈｅｍｅ）によって生成された異なる公開鍵であると仮定する。ここで、ｇとｈは、異なるジェネレータである。従来、EI
Gamalによる暗号化方式は、単一のジェネレータだけを使用する。従って、複数のジェネレータをオフラインで計算させることができ、かつ複数のジェネレータについて１つのテーブルだけを維持すればよいという利点が得られる。Watersによるスキームは、複数の異なるジェネレータについての数種類のテーブルの維持、及びオンラインによる計算を要求するため、計算の最適化及び管理コストの何れの点においても好ましくない。
【００２４】
発明者等は、匿名の公開鍵（Ａｎｏｎｙｍｏｕｓ  Ｐｕｂｌｉｃ  Ｋｅｙ）（ＡＰＫ）方式を見いだした。ＡＰＫ手法は、エンドユーザが一人で多数の公開鍵を生成することが可能であり、かつ１つの秘密鍵だけを保持することになっているという点で独特である。
【００２５】
ＡＰＫ方式について、図１〜図７を参照して説明する。
【００２６】
ＡＰＫ方式において、用語「グループ」は、他の定義が示されない限り以下のように定義される数学的な概念を指す。
【００２７】
グループ（Ｇ，  ◇）は、次の３つの公理を満たすＧにおけるブール演算◇を備えた集合Ｇから成る。
【００２８】
（１）  グループ演算は結合である。すなわち、Ｇのすべての要素ａ，ｂ，ｃについて、ａ◇（ｂ◇ｃ）＝（ａ◇ｂ）◇Ｃを満たす。
【００２９】
（２）  Ｇのすべての要素ａについてａ◇ｅ＝ｅ◇ａ＝ａを満たすＧの単位元eがある。
【００３０】
（３）  Ｇの各要素ａについて、ａ◇ａ−１＝ａ−１◇ａ＝ｅを満たすaの逆関数と呼ばれるＧの要素ａ−１が存在する。
【００３１】
例えば、追加の演算を備えた整数Zの集合は、あるグループを形成する。
【００３２】
単位元は“０”であり、整数ａの逆関数は整数ａ−１である。
【００３３】
より詳細に関しては、オンラインで利用可能な応用暗号学のハンドブック（Handbook of Applied Cryptography）を参照(http://www.cacr.math.uwaterloo.ca/hac/)。
【００３４】
ＡＰＫ方式による通信システムは、複数の端末装置及び複数の通信チャネルを備える。
【００３５】
図１は、ＡＰＫ方式による一実施例を示すブロック図である。
【００３６】
図１において、端末装置Ａは、複数のセッションによって端末装置ａと通信する。端末装置Ａには、端末装置ａに情報を送るための少なくとも1つの通信チャネルが存在する。
【００３７】
そのセッションは、１つあるいは複数の通信チャネルを利用する。
【００３８】
端末装置ａは、端末装置Ａに情報を送るために同じ通信チャネルを使用してもよいし、使用しなくてもよい。
【００３９】
通信チャネルを通じて、端末装置のＡは、異なる通信セッション毎に、端末装置ａに各種の公開鍵Ｅａ〜Ｅｚを通知するが、その秘密鍵ｘについては秘匿する。
【００４０】
端末装置ａは、必要に応じて端末装置Ａに対していくつかの異なる公開鍵を通知する点で、端末装置Ａと同様である。
【００４１】
図１に示されるように、異なるセッション毎に異なる公開鍵を生成することにより、端末装置ａあるいは任意の第三者が、端末装置Ａの活動パターンを推測することは事実上不可能である。
【００４２】
例えば、電子オークション環境では、異なる公開鍵が各セッション毎に生成されるため、端末装置Ａからのユーザは、自身の入札パタ−ン及び戦略が他者によって推測及び分析されるのを防ぐことができる。
【００４３】
また、図２は、ＡＰＫ方式の他の実施例を示すブロック図である。
【００４４】
図２において、端末装置Ａは、端末装置ａから端末装置ｚの複数の端末装置と通信する。
【００４５】
端末装置Ａと各々の通信先との間で使用される通信チャネルは、同じでも、同じではなくてもよい。
【００４６】
図２の左側に示されるように、通信チャネルを通じて、端末装置Ａは、異なる公開鍵Ｅａ〜Ｅｚを他の端末装置、すなわち、端末装置ａ，端末装置ｂ，・・・端末装置ｚにそれぞれ通知する。
【００４７】
この場合、端末装置Ａと端末装置ａ〜端末装置ｚとの間に、「１対複数」の関係があるといえる。上記公開鍵の通知は様々な方法で実現することができる。
【００４８】
例えば、公開鍵と一緒に明らかにされる他の情報があってもよいし、あるいは、公開鍵が電子メールか証明書に組み込まれてもよい。
【００４９】
また、端末装置ａ〜端末装置ｚは、受信した公開鍵で暗号化される情報を端末装置Ａに送るために、端末装置ａ〜端末装置ｚの各々が端末装置Ａからの公開鍵を受け取る通信チャネルと同一の通信チャネルを使用してもよいし、使用しなくてもよい。
【００５０】
上述の場合と同様に、端末装置Ａは、自身の秘密鍵ｘを秘密にする。
【００５１】
同様に、端末装置ａ〜端末装置ｚは、必要に応じて、端末装置Ａに対していくつかの異なる公開鍵を通知する点で、端末装置Ａと同じである。
【００５２】
図２の右側に示すように、端末装置ａ〜ｚは、それぞれ自身の公開鍵Ｅａ〜Ｅｚを端末装置Ａに通知する。
【００５３】
この場合、端末装置ａ〜ｚと端末装置のＡとの間に、「複数対１」の関係があるといえる。
【００５４】
図３は、図１及び図２に示された通信システムに参加する送信側と受信側の間の好適な通信セッション例を示す。
【００５５】
図３において、送信側が受信側に公開鍵を公表しようとする度に、送信側は、既存の公開鍵のプールから１つの公開鍵を選択する（ステップＳ３２）か、もしくは新しい公開鍵を生成する（ステップＳ３３）かを決定する（ステップＳ３１）。
【００５６】
その後、送信側は受信側に対して公開鍵を送信する（ステップＳ３４）。
【００５７】
受信側は、送信すべきメッセージがある場合(ステップＳ３５)には、送信側からの公開鍵を認識して(ステップＳ３６)、メッセージを暗号化しその暗号化されたメッセージを送信側に送る(ステップＳ３７)。
【００５８】
最後に、送信側は、受信した暗号化されたメッセージを解読し(ステップＳ３８)、受信側から送信されたオリジナルのメッセージを復元する。
【００５９】
なお、受信側が暗号化されたメッセージを送信側に送信することを欲する以前に、受信側が送信側から公開鍵を予め受け取っていることも想定される。
【００６０】
既存の鍵と無関係に、送信側が常に異なる公開鍵を生成する（ステップＳ３３）ように構成されていてもよい。
【００６１】
しかしながら、当業者であれば分かるように、既存の鍵の操作はゼロから公開鍵を計算するほど集中的な計算を必要とないので、既存の公開鍵のプールを使用することは、計算のオーバヘッドを著しく軽減する。
【００６２】
送信機が自身の公開鍵を受信機へ最初に送るため、図３の送信機及び受信機が便宜的にそのように示されていることに留意すべきである。
【００６３】
一旦受信機が送信機からの公開鍵を保持すれば、その受信機が暗号化されたメッセージを受信側である送信機に送る場合、その受信機は実際には送信機となる。
【００６４】
２つの端末装置間の典型的な相互の通信セッションにおいて、上記役割は、セッションの間頻繁に逆転する。
【００６５】
ここで、図４を参照すると、ＡＰＫ方式による公開鍵−秘密鍵のペアに基づいた通信セッションにおける送信機と受信機の好適な機能ブロック図が示されている。
【００６６】
ここで、送信機４１は、少なくとも、通信チャネルを処理する送信装置４３及び受信装置４５と、暗号文の解読を行う復号化装置４７と、ＡＰＫを生成するＡＰＫ生成装置４９とを備える。
【００６７】
受信機４２は、少なくとも、送信装置４４と、受信装置４６と、プレーンテキストのような送信される情報の暗号化を行うための暗号化装置４８とを備える。
【００６８】
送信機４１は、複数の公開鍵を受信機４２に公開してもよいし、送信機４１と受信機４２の間に複数のセッションがある場合、各セッションがそれぞれ送信機４１の異なる公開鍵を公開してもよい。
【００６９】
また、送信機４１は、受信機として動作する場合、さらに暗号化装置４８を備える。
【００７０】
同様に、受信機４２は、送信機として動作する場合、さらに復号化装置４７及びＡＰＫ生成装置４９を備える。
【００７１】
図４に示す暗号化装置４８及び復号化装置４７については、どちらもデータ通信と暗号化の分野においてよく知られているものである。
【００７２】
ＡＰＫ生成装置４９について、以下に示す図５においてさらに詳細に説明する。
【００７３】
図５を参照すると、制御装置５５は、鍵を管理する処理だけでなく公開鍵を生成する処理を制御する。
【００７４】
記憶部５４は、秘密鍵、生成された公開鍵、受信した公開鍵及び制御装置５５によって要求される他のデータを格納する。
【００７５】
なお、ＡＰＫ生成装置４９で使用される記憶部５４は、オンチップレジスタ、ＲＯＭ及びＲＡＭのような情報を格納することが可能な全ての装置によって実現することができる。
【００７６】
ＡＰＫ生成装置４９は、受信した暗号文及び解読における中間で出力されるデータを格納するために、記憶部５４を復号化装置４７と共有することも可能である。
【００７７】
公開鍵生成装置４９の他の構成要素については後述する。
【００７８】
図５においては、「グループ」演算がグループ指数演算子５７によって処理される。
【００７９】
「グループ」演算を別のグループ演算子によって処理するＡＰＫ生成装置４９の他の実施例も可能である。
【００８０】
次に、本発明に従って秘匿化された公開鍵(“ＡＰＫ”)を生成する、図４及び図５に示すＡＰＫ生成装置４９の処理について説明する。
【００８１】
図６は、ＡＰＫ−秘密鍵ペアを生成するための典型的な処理の流れを示す。
【００８２】
まず、グループＧが、グループ選択手段５１によって選択される（ステップＳ６０）。
【００８３】
例えば、コンピュータには、様々の適切なグループを表す様々なデータを格納するメモリが備えらえている。
【００８４】
制御装置５５による管理のもと、グループ選択手段５１は、グループを示すデータの選択によって１つのグループを選択する。
【００８５】
実際の運用においては、コンピュータ上で動作可能で、そのようなサービスを提供するいくつかの関数ライブラリの製品が既に提供されている。
【００８６】
ＡＰＫ方式を実施するアプリケーションプログラムは、いくつかの特定のパラメータと共に、上記のようなライブラリによって提供される特別の関数を呼び出すことも可能である。そして、呼び出された関数が、要求されたグループを返す。
【００８７】
本実施例において、グループＧは有限の巡回グループであり、そのグループＧの位数はｎである。また、位数ｎは正整数である。
【００８８】
有限の巡回グループＧの候補は以下のものを含むが、これらに限定されるものではない。
【００８９】
（１）有限体Ｆｑ１における楕円曲線上の点からなるグループ
【００９０】
（２）有限体Ｆｑ２の乗法グループＦｑ２、ただし、ｑ２＝ｐｍ１であり、ｍ１は正整数、Ｐは素数
【００９１】
（３）Ｚｎ１のグループ、ただし、ｎ１は合成整数
【００９２】
（４）Ｚｎ２の乗法グループ、ただし、ｎ２は素数。
【００９３】
上記の４つの典型的な種類のグループにおいて、最初のグループは、最良のセキュリティパフォーマンスを有しており、一方、後の３つのグループは、当該技術分野において一般的に用いられている。
【００９４】
グループＧの「有限の巡回」性が、グループ指数演算の結果がグループＧへマッピングされることを示している。しかし、そのマッピング方法はグループ毎に変わってもよい。さらに、それは、ジェネレータ（生成子）が存在することを示している。
【００９５】
その後、部分グループ選択手段５２は、ｍ≦ｎである位数ｍのグループＧの部分グループを選択する(ステップＳ６１)。
【００９６】
位数ｍとして素数が選択される場合、好ましいセキュリティパフォーマンスが得られる。
【００９７】
グループＧ自身が部分グループとして選択される場合があることに留意する必要がる。これは、ｍ＝ｎの場合である。
【００９８】
他の実施例として、グループＧが後に決定されるか又は選択されるという前提の場合には、部分グループの選択を省略することが可能である。それは、グループＧが数学的にグループＧ自身の部分グループであるため、グループＧ自身が部分グループとして暗黙に選択されていることを意味する。
【００９９】
すなわち、グループＧ自身が部分グループとして選択されている場合(ｍ＝ｎとなる場合)、そのような選択は見かけ上実施されない。
【０１００】
もちろん、部分グループの選択を省略する場合には、図５に示す部分グループ選択手段５２も省くことが可能である。
【０１０１】
次いで、整数選択手段５６は、秘密鍵ｘとしてｘが１＜｜ｘ｜＜ｍを満たすような整数を選択する(ステップＳ６２)。
【０１０２】
簡潔のため、ここでは、１つの秘密鍵から複数の公開鍵を生成する方法について主に説明するが、１つの端末装置が複数の秘密鍵を備えていることも考えられる。
【０１０３】
その後、ジェネレータ選択手段５３は、グループＧのジェネレータｇを選択して決定する（ステップＳ６３）。グループＧが有限の巡回グループである場合、常に少なくとも一つのジェネレータを有している。
【０１０４】
ジェネレータｇと秘密鍵ｘの選択は、互いに独立して行われることに留意する。
【０１０５】
すなわち、ステップＳ６２はステップＳ６３より前に説明されているが、それらの処理の順序は反対でもよいし、あるいは、それらの処理が並行して行われてもよい。
【０１０６】
Ｇ，ｍ，ｘ及びｇの選択の後、整数ｒが、制御装置５５の管理のもとで新しい公開鍵を生成するための、０＜｜ｒ｜＜ｍを満たす指標として選択される(ステップＳ６４)。
【０１０７】
Ｇ，ｍ，ｘ，ｇ及びｒの選択と共に、新しい公開鍵が、ｙ１＝ｇｒの演算、次に、ｙ２＝ｙ１ｘの演算によって生成される(ステップＳ６５)。
【０１０８】
その後、公開鍵（ｙ１，  ｙ２）は、暗号化のために受信機に公開される(ステップＳ６６)。
【０１０９】
もちろん、公開鍵と一緒に公開される他の情報があってもよい。
【０１１０】
ｇ，ｘ及びｒの選択は、それらの選択において連続性や依存関係が要求されない点に留意する。すなわち、そのような選択のステップＳ６２，Ｓ６３，Ｓ６４は任意の順番で、連続してあるいは同時に実行することが可能である。
【０１１１】
なお、ｇ，ｘ及びｒの選択は、任意にあるいは要求されるいくつかの基準に従ってなされてもよい。
【０１１２】
他方、前述の手順のうちのいくつかは制御装置５５によって省略され、どこか他所で実行されるかもしれない。
【０１１３】
例えば、グループＧ及び部分グループの選択手順を、信頼ある組織である第三者に割り当てることもできる。
【０１１４】
従って、グループ及び部分グループが外部的に決定されるので、制御装置５５はグループ及び部分グループを選択する手順をスキップする。
【０１１５】
さらに、１つの秘匿化された公開鍵が以前に生成されている場合、グループ、部分グループ、ジェネレータ及び秘密鍵の全てが既に選択及び決定されていることは確かである。
【０１１６】
それゆえ、新しい公開鍵を生成することになっている場合、制御装置５５は、これらの４ステップをスキップし、次のステップに直接進む。
【０１１７】
ｙ１又はｙ２が元々グループＧの範囲外にある場合、それらをグループＧへマッピングしなければならない。そのマッピング方法は、異なるグループ毎に変わってもよい。
【０１１８】
しかし、巡回グループＧは、そのようなマッピング方法があることを示している。
【０１１９】
前述の手順は、システムの単一の装置／モジュール(統合されたコンポーネントあるいは個別のコンポーネントを備えた)において、あるいはいくつかの手順を実行するシステムのそれぞれの装置に分散する方法で、それぞれ実行可能であることに留意する。
【０１２０】
（グループ、部分グループ及びジェネレータの選択の例）
【０１２１】
グループ、部分グループ及びジェネレータの選択例を、以下に示す。
【０１２２】
グループＺｐ＊が、ｐ＝１１、よって、Ｚ１１＊＝｛１，  ２，  ３，  ４，  ５，  ６，  ７，  ８，  ９，  １０｝の条件のもとで選択されたと想定する。
【０１２３】
「１１」が素数であるので、数学上、Ｚ１１＊の位数は１１−１＝１０となる。
【０１２４】
要素２は、Ｚ１１＊＝｛２ｉ
ｍｏｄ１１ ／ ｉ＝０，  １，  ・・・，  ９｝であることを容易に確認できることから、Ｚ１１＊のジェネレータである。
【０１２５】
さらに、グループが部分グループそれ自身であるので、部分グループがＺ１１＊として選択される。
【０１２６】
部分グループの別の選択例は、例えば、位数５のジェネレータ３を持つ｛１，３，４，５，９｝である。
【０１２７】
さらに、３５＝１
ｍｏｄ １１であることは容易に確認できる。
【０１２８】
さらに、当該技術分野における当業者であれば分かるように、この装置及び構成要素の全ては、多様な考察に基づきハードウェア、ソフトウェア、ファームウェアあるいはそれらの組み合わせで実現できることができる。
【０１２９】
（キー生成の最適化）
【０１３０】
主として図６に示した典型的な法の例は、ＡＰＫ方式による秘匿化された公開鍵を生成するために利用可能な多くの方法のうちのほんの１例である。
【０１３１】
同じ目的に使用することができるだけでなく処理の最適化を達成することができるより進んだ方法がある。
【０１３２】
最適化方法を説明するために、当該技術分野においてよく知られている符号化及び復号化する手順について、図４、図５及び図７を参照して簡潔に要約する。
【０１３３】
ここで、以下の記号１で示す演算子はグループＧの可逆演算子である。
【０１３４】
【数１】
2007089171.tif 000060
【０１３５】
以下の記号２で示す演算子は、記号１で示す可逆演算子の正確な逆演算子である。
【０１３６】
【数２】
2007089171.tif 000061
【０１３７】
ＡＰＫ方式を図７中の手順で適用する。
【０１３８】
プレーンテキストＭを暗号化するために、プレーンテキストＭがグループＧの要素として最初に表す（例えば、ＭはＡＳＣＩＩコードとして表わされる）（ステップＳ７０）。
【０１３９】
次いで、整数ｋが、１＜｜ｋ｜＜ｍを満たす指定子として選択され（ステップＳ７１）、そして、１ペアの値が以下のように計算される（ステップＳ７２）。
【０１４０】
【数３】
2007089171.tif 000062
ここで、Ｃ１とＣ２はグループＧの要素である。
【０１４１】
これらの演算処理の全ては図４に示す暗号化装置４８によって実行することができる。
【０１４２】
記号１による演算は、グループＧの乗算、除算、加算あるいは減算となる。
【０１４３】
Ｃ１又はＣ２が元々グループＧの範囲外にある場合、グループＧへそれらをマッピングしなければならない。そのマッピング方法は、各グループ毎に異なっていてもよい。
【０１４４】
この時、メッセージＭの暗号文がＣ＝（Ｃ１，  Ｃ２）として得られ（ステップＳ７３）、その暗号分が送信装置４４によって通信チャネル上に送信される（ステップＳ７３）。
【０１４５】
符号化されるグループＧの範囲外にあるメッセージＭについては、符号化前にいくつかのグループ要素に変換される。
【０１４６】
後の復号化に続いて、復元されたグループ要素はオリジナルメッセージへ戻されてもよい。
【０１４７】
その変換方法は、各グループ毎に異なっていてもよい。
【０１４８】
１例としては、メッセージをいくつかのブロック（それらの各々はグループＧの要素である）に分解し、Ｍを復元するために全てのブロックを連結する。
【０１４９】
通信チャネルの反対側で、暗号文メッセージＣが受信される（ステップＳ７４）。
【０１５０】
暗号文ＣからプレーンテキストＭを検索するために、２つの方法として、直接のべき数法かそうでないかを最初に決定する（ステップＳ７５）。
【０１５１】
べき数法の場合、ｒｂ＝Ｃ１ｘが最初に計算され（ステップＳ７６）、次に、以下の式による計算からＭが求められる（ステップＳ７７）。
【０１５２】
【数４】
2007089171.tif 000063
【０１５３】
そうでなければ、ｒａ＝Ｃ１−ｘが最初に計算され（ステップＳ７８）、次に、以下の式による計算からＭが求められる（ステップＳ７９）。
【０１５４】
【数５】
2007089171.tif 000064
【０１５５】
暗号文（Ｃ１，Ｃ２）の復号化に成功した後、復号化の実行に伴って、ＡＰＫ方式によるＡＰＫ生成装置４９は、（ｙ１＝Ｃ１−１，  ｙ２＝ｒａ）の書式で新しい秘匿化された公開鍵を生成するために解読中に出力される中間出力ｒａのみならず受信した暗号文を用いてもよい。
【０１５６】
同様に、ＡＰＫ生成装置４９は、（ｙ１＝Ｃ１，  ｙ２＝ｒｂ）の書式で新しい秘匿化された公開鍵を生成するために復号化途中で出力された中間出力ｒｂのみならず受信した暗号文を用いてもよい。
【０１５７】
新しい秘匿化された公開鍵を生成する上記いずれかの方法によって、べき数演算が回避され、また計算効率が向上する。
【０１５８】
さらに、単一の秘匿化された公開鍵（ｙ１，  ｙ２）が提供される場合、ＡＰＫ生成装置４９は、（ｙ２，ｙ２ｘ）の形式で新しい秘匿化された公開鍵を生成してもよい。
【０１５９】
この方法は、一連の公開鍵を生成するために複数回用いることが可能である。
【０１６０】
この方法では、公開鍵ｙ２の第２の部分が、次に続く公開鍵の最初の部分と同一であるので、生成された公開鍵による記憶容量の消費が非常に減少する。
【０１６１】
一連のｗ個の公開鍵について、記憶容量が（ｗ−１）／２ｗパーセントにセーブされるということは、十分に大きなｗについて約５０パーセントの節約を意味する。
【０１６２】
ＡＰＫ方式においては、公開鍵が、ジェネレータのべき数の形式に基づいて同一のジェネレータで生成されるので、べき数法の代わりに乗法を含む一連の公開鍵を生成するためにジェネレータｇのべき数を再使用することができる。このようにして、記憶容量を節約し、計算を加速できる。
【０１６３】
また、復号化装置において、ジェネレータのべき数のただ１つのテーブルを維持する必要があるだけなので、新しい公開鍵の計算をオフラインで行うことが可能である。
【０１６４】
例えば、実施例において、暗号文メッセージＣ＝（Ｃ１，  Ｃ２）が復号化装置で受信される場合、新しい公開鍵を生成するためにＣ１を検索して用いることができる。
【０１６５】
上述したＣ１＝ｙ１ｋ＝ｇｒｋの場合、積“ｒｋ”が単なる他の整数であるので、ｇｒｋを新しい公開鍵を生成するために保存することができる。
【０１６６】
新しい公開鍵を生成するためにｇｒｋを保存することができるが、暗号化されたメッセージを送る時、もしも符号化装置がｋを明らかにしなかったならば、ｒｋの値は復号化装置には依然知られていない可能性がある点に留意すべきである。
【０１６７】
単一の秘匿化された公開鍵（ｙ１，  ｙ２）が提供される場合、ＡＰＫ生成装置４９は、（ｙ１×ｙ１，ｙ２×ｙ２）の式から新しい秘匿化された公開鍵を生成してもよい。ここで、×はグループ乗算である。
【０１６８】
一般に、ｙ１１＝ｇｒ１，  ｙ１２＝ｇｒ２，  ・・・，  ｙ１ｊ＝ｇｒｊ
及び ｙ２１＝ｙ１１ｘ，  ｙ２２＝ｙ１２ｘ，  ・・・，  ｙ２ｊ＝ｙ１ｊｘである、複数の格納されたｇのべき数に基づいていくつかの秘匿化された公開鍵（ｙ１１，  ｙ２１），（ｙ１２，  ｙ２２），・・・，（ｙ１ｊ，  ｙ２ｊ），  ｊ≧２が提供される場合、新しい公開鍵が（ｙ１（ｊ＋１）＝ｙ１１ｙ１２・・・ｙ１ｊ，  ｙ２（ｊ＋１）＝ｙ２１ｙ２２・・・ｙ２ｊ）として計算される。
【０１６９】
ここで、上記 ｙ１１ｙ１２・・・ｙ１ｊは、ｙ１１，  ｙ１２，  ・・・、  ｙ１ｊの積であり、ｙ２１ｙ２２・・・ｙ２ｊは、ｙ２１，  ｙ２２，  ・・・、  ｙ２ｊの積である。
【０１７０】
明らかに、新しい秘匿化された公開鍵を生成するために、べき数演算は、乗算に置き換えられ、計算効率が向上する。
【０１７１】
乗法演算をオンラインで実行することができるので、このように生成された新しい公開鍵をあらかじめ計算する必要がなく、このことは直ちに記憶容量の節約を意味する。
【０１７２】
上記の最適化技術は、新しい秘匿化された公開鍵を生成するために一緒に用いてもよい。
【０１７３】
例えば、受信した上で、一連の暗号文（Ｃ１１，  Ｃ２１），（Ｃ１２，  Ｃ２２），・・・，（Ｃ１ｊ，  Ｃ２ｊ）（ただし、ｊ≧２）の復号化に成功した後、ＡＰＫ生成装置４９は、（ｙ１＝（Ｃ１１ Ｃ１２・・・Ｃ１ｊ），
ｙ２＝（ｒｂ１ｒｂ２・・・ｒｂｊ））の式によって新しい秘匿化された公開鍵を生成するために解読中に出力される中間出力ｒｂ１，  ｒｂ２，  ・・・，  ｒｂｊのみならず受信した暗号文も用いることができる。
【０１７４】
ここで、Ｃ１１Ｃ１２・・・Ｃ１ｊはＣ１１，  Ｃ１２，  ・・・，  Ｃ１ｊの積、ｒｂ１ｒｂ２・・・ｒｂｊは、ｒｂ１，  ｒｂ２，・・・，  ｒｂｊの積である。
【０１７５】
また、ｙ２の計算で、一連の公開鍵は、（ｙ２ｗ１，  ｙ２ｗ２）として計算される。ここで，ｗ１＝ｘｗ，  ｗ２＝ｘ（ｗ＋１）
，  ｗ≧０である。
また、この計算において求められた結果(特にｇのべき数)は全て、公開鍵をさらに生成するために用いられる。
【０１７６】
さらに、暗号文メッセージＣから検索されたＣ１に基づいて、復号化装置はさらに多くの新しい公開鍵を生成することが可能である。
【０１７７】
この目的のために、Ｃ１ｘ及びＣ１−ｘを計算して保存され、次いで、２つの一連の公開鍵が生成される。
【０１７８】
一般に、多くの暗号化されたメッセージＣＣ１＝（Ｃ１１、Ｃ１２），  ＣＣ２＝（Ｃ２１、Ｃ２２），  ・・・，  ＣＣｊ＝（Ｃｊ１、Ｃｊ２）が受信された時、Ｃ１ｘの場合、一連の新しい公開鍵が、（（Ｃ１１Ｃ２１・・・Ｃｊ１）ｕ１
，  （Ｃ１１Ｃ２１・・・Ｃｊ１）ｕ２）として生成される。ここで、Ｃ１１Ｃ２１・・・Ｃｊ１は、Ｃ１１，  Ｃ２１，  ・・・，  Ｃｊ１，  （ｊ≧１，  ｕ１＝ｘｕ，  ｕ２＝ｘ（ｕ＋１），  ｕ≧０）の積である。また、Ｃ１−ｘの場合、別の一連の新しい公開鍵が、（（Ｃ１１Ｃ２１・・・Ｃｊ１）ｖ１
，  （Ｃ１１Ｃ２１・・・Ｃｊ１）ｖ２）として生成される。ここで、Ｃ１１Ｃ２１・・・Ｃｊ１は、Ｃ１１，  Ｃ２１，  ・・・，  Ｃｊ１，  （ｊ≧１，  ｖ１＝−ｘｖ，  ｖ２＝−ｘ（ｖ＋１），  ｖ≧０）の積である。
【０１７９】
さらに、この計算において求められた結果(特にｇのべき数)は全て、公開鍵をさらに生成するために用いられる。
【０１８０】
（順応性のある匿名証明書）
以下の記述で、本発明の一般的な概念を説明する。
【０１８１】
APK手法は、前述の出願中の関連出願において説明しているように、多数の秘匿化された公開キーを証明する方法に関して問題を含んでいる。そのため、多数の秘匿化された公開キーを証明することができる解決法の提案が望まれている。
【０１８２】
１．安全性。誰も証明書を偽造することができない。また、誰も証明書の保持者であることを隠すことができない。
【０１８３】
２．確実性。ユーザのプライバシーは、いかなる証明書によっても明かされない。
【０１８４】
３．取り消し可能。ユーザが匿名性を悪用する場合、ユーザの本当の身元を暴露することができる。
【０１８５】
４．信頼性。証明書は、ビジネスにおいても有効である。
【０１８６】
５．分配できる。APKの分配方法のように、証明書解決法が分散させられるべきである。
【０１８７】
６．効率的。第３者機関の経済的負担がより少ない。
【０１８８】
上述したように、従来の証明方法は多くの欠点を有している。さらに、APKは分散型のプライバシー保護解決法であるので、集中型の証明解決法はAPK解決法に適していない。
【０１８９】
従って、ユーザのデータを証明するための分散型解決法は、従来より提案されている、すなわち、柔軟性のある匿名証明書(MPC)解決法である。
【０１９０】
本発明による柔軟性のある匿名証明書(MPC)解決方法は、多数の秘匿化された公開キーを証明する新規の解決方法である。全ての証明書が信頼できる実体によって生成され発行される従来の解決法と異なり、MPC解決法は、他人によってデータを証明する必要のあるユーザが、自分自身で信頼できる実体から取得したルート証明から匿名証明書を生成する分散型解決法である。
【０１９１】
ルート証明は、ユーザが匿名証明書を生成するために信頼できる実体によって発行された証明書でもよい。以下、そのような証明書をルート証明と称する。ルート証明は、またグループ秘密鍵でもよい。ユーザはそのグループ秘密鍵によってグループ・メンバーの名のもとに匿名証明書を生成することが可能である。しかし、ルート証明は、それらに限定されない。ルート証明は、ユーザの信用を証明することができる任意のデータでも良いし、また、所定のアルゴリズムによって生成される匿名証明書でもよい。
【０１９２】
図８Ａは、本発明のMPC解決法の全体的な概念を示す概略ブロック図である。
【０１９３】
ユーザＵは、ネットワークを介して他のユーザと通信する、ネットワーク中のユーザである。通信セションの間、ユーザＵのデータのうちのいくつかは他のユーザ或いは仲間によって証明されることを必要とされる。例えば、ユーザＵのデータＤＡＴＡ１はユーザＶ１によって証明され、ユーザＵのデータＤＡＴＡ２はユーザＶ２によって証明され、ユーザＵのデータＤＡＴＡ３はユーザＶ３によって証明されることになっている。以下、信用を得るためにユーザＵのデータを証明することを望むユーザ或いは仲間を立証者と称する。
【０１９４】
ＤＡＴＡ１、ＤＡＴＡ２及びＤＡＴＡ３は、様々な通信セッションのためのユーザの種々の公開鍵である。１つの実例では、これらのデータは唯一の公開鍵或いはＡＰＫである。しかし、データは公開鍵に限定されない。証明されるデータは、様々な目的のためのどんなデータでもよい。
【０１９５】
データを認証するために、ユーザ側装置Ｕは、立証者側装置（Ｖ１、Ｖ２、Ｖ３等）へデータを送る。ここで、データは、ＰＣ１、ＰＣ２、ＰＣ３等の証明書を有している。ＭＰＣ解決方法では、これらの全ての証明書は、信用機関側装置からユーザ側装置Ｕに発行されたルート証明から生成される。これらの証明書（ＰＣ１、ＰＣ２、ＰＣ３等）が信用機関側装置の介在無しでユーザ側装置Ｕ自身によって計算されることが重要である。立証者側装置は、そのような添付された証明書によってユーザ側装置Ｕのデータを照合する。また、信用機関によって照合された証明書はデータを保証することが可能である。立証者が信用機関を信用するならば、立証者は、ユーザ側装置Ｕのデータが真正なことを信じることができる。
【０１９６】
信用機関は、Ｕの信用を証明することができるＣＡ、信用あるグループ、Ｕの友人あるいは他の関係者などである。
【０１９７】
本発明によるＭＰＣ解決方法において、立証者は、Ｕのデータが信用機関によって証明されているという証明書によって照合し確信を得ることができる。一方、その証明書は、立証者が決してユーザのデータの保持者であるユーザＵの本当の身元を明かさないようユーザによって生成される。従って、ユーザによって生成された証明書を、以下匿名証明書と称する。
【０１９８】
ユーザデータがＡＰＫである場合、ＡＰＫの各ペアと匿名の証明書が立証者側装置（例えばＶ１）に示される。立証者側装置Ｖ１はＡＰＫが信用機関側装置によって証明されていることを検査し確信を得ることができる一方、Ｖ１は決してＡＰＫと匿名証明書のペアの保持者を明かさない。匿名の公開鍵と匿名証明書の別のペアを示す度に、ユーザがＶ１と何度も通信しても、立証者側Ｖ１は自分がユーザと通信しているかどうかを知らせることはできない。
【０１９９】
図８Ｂは、本発明によるＭＰＣ解決方の一般的な検証プロセスを概略的に示すフローチャートである。
【０２００】
ステップ８１において、ユーザ側装置が信用機関側装置からルート証明を取得する。例えば、ユーザ側装置は、自身の基本的なデータ（以下、ルート・データと称する）とそのデータに対するユーザの証明をＣＡ側装置に示す。ＣＡ側装置は、ユーザのルート・データとルート・データのユーザ証明の識別検査を実行する。ユーザがＣＡ側装置の識別検査にパスした後、ＣＡ側装置はユーザに対する証明書を発行する。
【０２０１】
ステップ８２において、ユーザ側装置は、ルート証明からの匿名証明書を生成する。同じルート証明から、ユーザ側装置は複数の別個の匿名証明書を生成することが可能である。
【０２０２】
ステップ８３において、ユーザ側装置は、１の匿名証明書を有するユーザのデータを立証者側装置に送信する。
【０２０３】
ステップ８４において、立証者側装置が匿名証明書によってユーザのデータを検査する。
データが、信用機関によって証明された匿名証明書によって証明されるので、立証者が信用機関を信じる場合、立証者は、ユーザのデータが信用できるという確信を抱くことができる。その後、立証者側装置は前記データに基づいて安全にユーザ側装置と通信することができる。例えば、ユーザのデータが匿名の公開鍵である場合、ユーザは自身のメッセージにデジタル的に署名してもよいし、立証者側装置はユーザ自身の匿名の公開鍵に基づいてユーザのためのメッセージを全て暗号化してもよい。しかしながら、ユーザのデータは、ユーザの匿名の公開鍵に制限されない。例えば、それはユーザの唯一無比の公開鍵でもよい。
【０２０４】
図８Ａと図８Ｂから分かるように、データが信用機関によって証明される匿名証明書によって保証される場合、ユーザ側装置は信頼できるデータを生成することが可能である。ユーザ・プライバシ保護の機能は完全に施される。
ユーザ側装置は、自身による別個の匿名証明書だけでなく別個の匿名の公開鍵も生成する。信用機関は、ユーザのルート・データのためのルート証明をただ発行するだけである。例えば、ＣＡは、ユーザ自身のルート公開鍵のために、ユーザ側装置に対してルート証明書（ＲＣ）を発行する。証明書機関（ＣＡ）の介在は最小限である。よって、ＣＡの負荷の軽減化を実現することが可能である。
【０２０５】
さらに、本発明によるＭＰＣ方式では、信用機関側装置は、匿名証明書が信用機関で追跡可能なように、ユーザのルート証明を格納することができる、
【０２０６】
ユーザＵが不適切に振る舞う場合（例えば、ユーザがメッセージにデジタル署名した後で、それを否認するような場合）、被害者は信用機関にユーザＵの匿名証明書を送信することが可能である。それは、信用機関だけが、匿名証明書の真の保持者を解明する能力を持っているためである。
【０２０７】
具体的な例について説明する。ユーザ側装置Ｕは対の匿名の公開鍵および匿名証明書を生成するものとする。その後、ユーザ側装置は立証者側装置Ｖ１と通信し、鍵と証明書を明示する。匿名証明書に基づいて、立証者側装置Ｖ１は、匿名の公開鍵が信用機関側装置によって本当に証明されていることを確認する。従って、ユーザＵが立証者側Ｖ１に５０ドル支払うことに署名すると、立証者側装置Ｖ１は、自身が著わした電子本（e-book）をユーザ側装置Ｕに送る。立証者側装置Ｖ１はただ匿名の公開鍵及び匿名証明書を確認するだけなので、立証者は、買い手の本当の身元を知らない。しかしながら、ユーザＵが支払をせずに逃げるならば、立証者側Ｖ１は、匿名証明書の本当の保持者を暴くことができる信用機関に匿名証明書を送ることが可能である。この場合、保持者Ｕは結果的にペナルティーを受けることになる。このように、ユーザはシステムの匿名性を乱用するのは不可能である。
【０２０８】
（第１の実施の形態）
以下、本発明による第１の実施の形態について図９〜図１８を参照して説明する。
【０２０９】
図９は、本発明の第1の実施の形態によるシステム構成を概略的に示すブロック図である。
【０２１０】
第１の実施の形態によれば、信用機関は証明書機関ＣＡ(Certificate Authority CA)である。立証者側装置によって証明されるユーザＵのデータはユーザＵの匿名の公開鍵である。
【０２１１】
もし、Ｕが個人識別検査に合格すれば、ＣＡ側装置はＵに対してルート証明書（ＲＣ）を発行する。Ｕは、自身の匿名の公開鍵のためにルート証明書から匿名証明書を生成する。その後、Ｕは、立証者側装置Ｖ（Ｖ１、Ｖ２（Ｖ３）．．．）に対して、匿名証明書（ＰＣ１、ＰＣ２（ＰＣ３）．．．）を持つ匿名の公開鍵（ＡＰＫ１、ＡＰＫ２（ＡＰＫ３）．．．）を送信する。Ｖは、Ｕから受信した匿名証明書を証明し、予め定義した条件が満たされる場合、その証明書を受け入れる。
【０２１２】
第１の実施の形態では、Ｕは、ＣＡ側装置の介在無しにＲＣからある匿名の公開鍵のための匿名証明書を引き出すことが可能である。一方、Ｖは、同様にＣＡ側装置を含むことを必要としない匿名証明書に基づいてＵの真正なことを判断することが可能である。
【０２１３】
さらに、Ｖは、Ｕから集められたデータを格納する。また、ある状況の下で（例えば、Ｕが不法に振舞う）、Ｖは、Ｕから集めたデータをＣＡ側装置に提出することができ、また、ＣＡは、Ｕの実際の身元を明かすことができる。
【０２１４】
以下の説明においては、暗号化技術はStrong RSA (SRSA) Assumptionに基づいている。ＳＲＳＡの詳細に関しては、「N.
Baric´, B. Pfitzmann, Collision-free
Accumulators and Fail-stop Signature Schemes without Trees, Advances in
Cryptology-EUROCRYPT’97, pp. 480~494, 1997; and R. Cramer, V. Shoup, Signature Schemes Based on The Strong RSA
Assumption, ACM Transactions on Information and System Security, vol. 3(3):
161~185, 2000」を参照することができる。
【０２１５】
さらに、いくつかの証明方法が本発明の実施の形態において使用される。それらは、証明者が、ある値の知識に関して立証者を納得させることを可能にする。一方、値自体に関する有用な情報は漏らされない。
【０２１６】
本発明による第１の実施の形態では、いわゆる知識証明技術が使用される（「S. Goldwasser, S. Micali, C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, 17th
ACM Symposium on Theory of Computation, pp. 291~304, 1985」を参照）。ゼロ知識（zero-knowledge）中の離散対数について知識を証明するために多くの方法が提案されている（「A. Fiat, A. Shamir, How To
Prove Yourself: Practical Solutions to Identification and Signature Problems,
Advances in Cryptology - CRYPTO’86,
pp. 186~194, 1986; D. Chaum, Demonstrating
Possession of a Discrete Logarithm without Revealing It, Advances in
Cryptology - CRYPTO’86, pp. 200~212, 1987; D. Chaum, J. H. Evertse, J. van de
Graaf, An Improved Protocol for
Demonstrating Possession of Discrete Logarithms and Some Generalizations,
Advances in Cryptology - EUROCRYPTO’87, pp. 127~141, 1987; D. Chaum, T. P.
Pedersen, Wallet Databases with Observers,
Advances in Cryptology - CRYPTO’92, pp. 89~105, 1993; and K. Sako, J. Kilian, Receipt-Free Mix-Type Voting Scheme-A
Practical Solution to the Implementation of a Voting Booth, Advances in
Cryptology - CRYPTO’98, pp. 393~403, 1998」を参照）。
【０２１７】
本発明による第１の実施の形態において、
【数６】
2007089171.tif 000065
式（１）は、共通の入力（ｇｊ，ｙｊ）について、証明者側装置と立証者側装置の間の知識証明を示すために使用される。ここで、ｇｊが〈ｇｊ〉，ｊ＝１，・・・，ｉを生成し、全てのｊ＝１，・・・，ｉについて、
【数７】
2007089171.tif 000066
で、ａｊ＜ｘｊ＜ｂｊが成り立つようにｘｊについての知識を証明する。
ａｊ＜ｘｊ＜ｂｊを証明する手法が、「T. Okamoto, An Efficient
Divisible Electronic Cash Scheme, Advances in Cryptology - CRYPTO’95, pp.
438~451, 1995, and later on developed in A. Chan, Y. Frankel, Y. Tsiounis, Easy Come - Easy Go Divisible Cash, Advances
in Cryptology - EUROCRYPT’98, pp. 561~575, 1998, in which it has been given the
name the Range Bounded Commitment (RBC)」に記載されている。
【０２１８】
乗法表現のための証明の場合に上述の式（１）を一般化することが可能である。
【数８】
2007089171.tif 000067
例えば、式（２）は、もし、ａ＜ｘ１＜ｂであれば、
【数９】
2007089171.tif 000068
と
【数１０】
2007089171.tif 000069
が同時に成り立つような、ｘ１とｘ２のゼロ知識証明を表す。
【０２１９】
次に、本発明の第１の実施の形態による方法の詳細を、図１０〜１６を参照して説明する。
【０２２０】
この第１の実施の形態による方法は、主として５つの工程からなる。すなわち、システムスタートアップ、RCリクエスト、MPC導出、秘匿の認証及び追跡(必要ならば)である。
【０２２１】
図１０は、本実施の形態によるシステムスタートアップ工程におけるＣＡ側装置の初期化処理の例を示すフローチャートである。
【０２２２】
ステップ１０１において、ＣＡ側装置はＳＲＳＡ係数ｎｃを生成する。係数ｎｃの因数分解は秘密に保たれる。
【０２２３】
ステップ１０２において、ＣＡ側装置は、ｐ−１がちょうどｑで割り切れるような素数ｐ及びｑを生成する。
【０２２４】
ステップ１０３において、ＣＡ側装置は、整数ｌｑ＝｜ｑ｜（すなわち、ｑの大きさ）を計算する。
【０２２５】
ステップ１０４において、ＣＡ側装置は、Ｚ＊ｐからＧＦ（ｑ）（オーダーｑの有限体）の１つのジェネレータｇを選択する。
【０２２６】
ステップ１０５において、ＣＡ側装置はＱＲ（ｎｃ）から整数ｃａ、ｃｂおよびｃｃを選択する。
【０２２７】
ステップ１０６において、ＣＡ側装置は整数ｌｃ＜ｌｑを選択する。
【０２２８】
上述の数学的な概念は、参考文献としての、A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied
Cryptography, CRC Press, 1996  に記述されている。最後に、ステップ１０７において、ＣＡ側装置は、ｎ，ｐ，ｑ，ｇ，ｌｑ，ｃａ，ｃｂ，ｃｃ及びｌｃをネットワーク（例えばインターネット）上に発行する。
【０２２９】
図１１は、本実施の形態によるシステムスタートアップ工程におけるユーザ側装置初期化処理の例を示すフローチャートである。
【０２３０】
ＣＡ側装置によって発行されたシステムパラメータに従って、ユーザ側装置Ｕは、ステップ１１１においてそれ自身の秘密鍵
【０２３１】
【数１１】
2007089171.tif 000070
をランダムに選択する。
【０２３２】
ステップ１１２において、ユーザ側装置Ｕは、自身のルート公開鍵
【数１２】
2007089171.tif 000071
を計算する。
【０２３３】
ＲＣを得るために、Ｕは、ＣＡ側装置へ自身の身元を立証する必要があると共に、ＣＡ側装置はｙｕが公開鍵として他のいずれかのユーザによって使用されていないことを確かめなければならない。
【０２３４】
図１２は、本実施の形態によるＲＣリクエスト処理の例を示すフローチャートである。
【０２３５】
ステップ１２１において、ユーザ側装置Ｕが
【数１３】
2007089171.tif 000072
を計算する。
【０２３６】
ステップ１２２において、ユーザ側装置ＵがＣＡ側装置にその人のルート公開鍵（ｇ，ｙｕ）およびａｕを実行依頼する。
【０２３７】
ステップ１２３において、ユーザ側装置ＵおよびＣＡ側装置が以下の式により知識証明を実行する。
【数１４】
2007089171.tif 000073
【０２３８】
知識証明が成功した場合、ステップ１２４において、ＣＡ側装置は十分に大きい任意の素数
【数１５】
2007089171.tif 000074
を選択し、ｅｕが他のユーザに割り当てられていないことを確かめて、
【数１６】
2007089171.tif 000075
を計算する。
【０２３９】
ステップ１２５においては、ＣＡ側装置が、ＲＣとして（ｇ，ｙｕ）に対する（ｅｕ，ｓｕ）をユーザ側装置Ｕに発行する。
【０２４０】
ステップ１２６において、ＣＡ側装置は、可能な調査のために、ユーザＵの名前の元でデータベースにデマスキングｅｕを格納する。
【０２４１】
ステップ１２７において、ユーザ側装置Ｕが、合同式
【数１７】
2007089171.tif 000076
が成り立つことを証明する。
【０２４２】
前記ＲＣは２つの組（ｅｕ，ｓｕ）である。ここで、ｅｕは実際はＲＳＡ公開鍵で、ｓｕがｃｂ／ａｕのデジタル署名である。
しかしながら、次の段階の中で実証されるように、単一の署名の準備に際して、Ｕは、自身の全ての匿名の公開鍵のための証明書を効果的に得ることが可能である。ＲＣは、表現形式（ｇｒ，ｙｕｒ）に従って匿名の公開鍵全てに署名するデジタル署名である。
【０２４３】
図１３は、本実施の形態においてユーザ側装置Ｕがどのように匿名の公開鍵を生成するかを示すフローチャートである。また、図１４は、本実施の形態において匿名の公開鍵用のＲＣからユーザ側装置Ｕがどのように匿名証明書を得るかかを示すフローチャートである。匿名の公開鍵および匿名証明書はともにプライバシ保護及び匿名の真正なことを保証する。
【０２４４】
図１３に示すように、ステップ１３１において、ユーザ側装置Ｕは、｛０，１，・・・，２ｋ−１｝から整数ｒを選択し、ステップ１３２において、匿名の公開鍵（ｇｒ，ｙｕｒ）（ｍｏｄ  ｐ）を算出する。
【０２４５】
図１４に示すように、ステップ１４１において、ユーザ側装置Ｕは、｛０，１，・・・，ｑ−１｝から整数ｔを選択し、ステップ１４２において、
【数１８】
2007089171.tif 000077
と
【数１９】
2007089171.tif 000078
を算出する。
【０２４６】
匿名証明書は実際に２つの組
【数２０】
2007089171.tif 000079
である。
【０２４７】
いま、Ｕは、
【数２１】
2007089171.tif 000080
を有している。ここで、ｅｕ，ｘｕおよび-ｔラｅｕについての知識は次の段階において立証者側装置に証明される。
【０２４８】
匿名の公開鍵および匿名証明書の準備の後、Ｕは立証者側装置へそれらを提示することが可能である。
【０２４９】
図１５は、本実施の形態による匿名認証処理の例を示すフローチャートである。
【０２５０】
ステップ１５１において、ユーザ側装置Ｕが立証者側装置Ｖに匿名の公開鍵（ｙ１ｒ＝ｇｒ，ｙ２ｒ＝ｙｕｒ）および匿名証明書
【数２２】
2007089171.tif 000081
を送る。
【０２５１】
ステップ１５２において、立証者側装置Ｖが
【数２３】
2007089171.tif 000082
を計算する。
【０２５２】
ステップ１５３において、ユーザ側装置Ｕおよび立証者側装置Ｖが以下ように知識証明を実行する。
【０２５３】
【数２４】
2007089171.tif 000083
【０２５４】
ステップ１５４において、Ｖが、可能な追跡のために上記の知識証明の記録を格納する。
【０２５５】
図１２のステップ１２６においてＣＡ側装置がユーザＵの名前でデータベースにデマスキングｅｕを格納するので、ＣＡ側装置は検査能力を有する。
【０２５６】
Ｖが保証されたＣＡ  ＣＭＳとしてＵの匿名の公開鍵を受け入れて、Ｕを含めた処理を行なった後、Ｕが不適切に振る舞う場合、ＶはＣＡにＵの不適切行動を示す証拠を供給し、支援をＣＡ側装置に求めることが可能である。ＣＡ側装置は、Ｖから受け取られた証拠を明確に検査する。ＣＡの視点から、ＶがＵの本当の身元を知る十分な理由があれば、ＣＡはＵの本当の身元を確認するたねにＶに協力することが可能である。
【０２５７】
図１６は、本実施の形態による調査処理を示すフローチャートである。
【０２５８】
ステップ１６１において、ＶがＣＡ側装置に匿名証明書
【数２５】
2007089171.tif 000084
を送る。
【０２５９】
ステップ１６２においては、データベースに格納された全てのデマスキングｅｕについて、ＣＡ側装置が
【数２６】
2007089171.tif 000085
を計算し、その結果を
【数２７】
2007089171.tif 000086
と比較する。
【０２６０】
【数２８】
2007089171.tif 000087
および
【数２９】
2007089171.tif 000088
の一致は、匿名証明書
【数３０】
2007089171.tif 000089
の所有者のデマスキング値を明らかにする。このように、ＣＡは、Ｕの本当の身元を見いだして明らかにすることが可能である。
【０２６１】
次に、ユーザ側およびＣＡ側における代表的な装置について図１７と図１８を参照して説明する。
【０２６２】
図１７は、第１の実施の形態によるユーザの代表的なユーザ側装置１７０を示すブロック図である。
【０２６３】
図１７に示すように、ユーザ側装置１７０は、基本的に、ＣＡ側装置からＲＣを受け取るためのルート証明ユニット１７１、ＲＣに基づいて匿名証明書の生成のためにルート証明ユニット１７１に接続される匿名証明書生成ユニット１７２、匿名証明書を有するユーザのデータを送信するための匿名証明書生成ユニット１７２に接続された送信ユニット１７３を備えている。
【０２６４】
ルート証明書がネットワークを介してディジタル・リクエストによって要求される場合、ユーザ側装置１７０は、さらに、ＲＣの要請を生成しＣＡ側装置に要求を送信するためのルート証明要求ユニット１７４を備えることができる。
【０２６５】
立証者側装置によって証明されるユーザのデータは、公開鍵、唯一の公開鍵、匿名の公開鍵等であってもよい。匿名の公開鍵である場合には、ユーザ側装置１７０が、匿名の公開鍵の生成のための匿名公開鍵生成ユニット１７５をさらに備えることが可能である。匿名公開鍵生成ユニット１７５の詳細については、上述したＡＰＫ手法の記述から理解することができる。匿名証明書によって証明されるユーザのデータが匿名の公開鍵でない場合、匿名公開鍵生成ユニット１７５は対応するデータ生成ユニットと置き換えることが可能である。
【０２６６】
ＲＣの発行がユーザとＣＡ側装置の間の検証プロセスを要求するか、または立証者側装置が認証プロセスにおける知識証明を要求する場合、ユーザ側装置１７０は、さらに、立証者側装置あるいはＣＡ側装置と共に証明動作を実行するための証明ユニット１７６を備えることも可能である。
【０２６７】
上述した各ユニットは、それぞれのユニットによって使用されるデータを格納のためのメモリを備える。別の実施例では、ユーザ側装置１７０は、装置の動作中に全てのユニットによって使用されるデータを格納のために記憶装置１７７を備えることも可能である。
【０２６８】
多くの場合、ユーザはさらに他のユーザの受信データを照合する必要がある。従って、ユーザ側装置１７０は、添附された匿名証明書によってもう一人のユーザから受信したデータを検証するための検証ユニット１７８を備えることも可能である。
【０２６９】
ルート証明ユニット１７１、送信ユニット１７３、ルート証明要求ユニット１７４、証明ユニット１７６及び検証ユニット１７８は、ネットワークを介して他の装置と通信するために上記各ユニットと接続されるユーザ側装置１７０内の通信ポート或いは通信ユニットを介してネットワークにデータを送信し、或いはネットワークからデータを受信する。
【０２７０】
本発明の第１の実施の形態による処理を実行するため、上記各ユニットは互いに接続されている。ユニットがハードウェアモジュールとして実装される場合、それらはデータバスによって互いに接続される。
【０２７１】
図１８は、第１の実施の形態による代表的なＣＡ装置１８０を示すブロック図である。
【０２７２】
図１８に示すように、ＣＡ装置１８０は、基本的に、システムパラメータを計算するためのシステムパラメータ計算ユニット１８１、ネットワークの全てのユーザによって共有されるパラメータを発行するためにシステムパラメータ計算ユニット１８１に接続されるパラメータ発行ユニット１８２、ユーザ側装置からＲＣリクエストを受信するためにネットワークに接続されるルート証明要求受信ユニット１８３、ルート証明リクエストに応じてユーザのためのＲＣを生成するために、ルート証明要求受信ユニット１８３及びシステムパラメータ計算ユニット１８１に接続されるルート証明生成ユニット１８４を備えている。
【０２７３】
ルート証明書が発行される前に、ユーザのＲＣリクエストが検査される場合、ＣＡ装置１８０は、ユーザのＲＣリクエストに応じて識別検査を行なうために、ルート証明要求受信ユニット１８３に接続された検査ユニット１８５をさらに含む。識別検査は、上述した知識証明処理を含んでいる。
【０２７４】
検査能力が要求される場合、ＣＡ装置は、ルート証明生成ユニット１８４によって生成されたルート証明書の格納されたデマスキング値を使用することにより、立証者側装置から受信した匿名証明書の所有者の身元の調査のための、ネットワークに接続された調査ユニット１８６をさらに備えることができる。
【０２７５】
上述した各ユニットは、それぞれのユニットによって使用されるデータを格納のためのメモリを備える。別の実施例では、ＣＡ装置１８０は、装置の動作中に全てのユニットによって使用されるデータを格納のために記憶装置１８７を備えることも可能である。例えば、ルート証明生成ユニット１８４によって生成されたＲＣは、ルート証明生成ユニット１８４内部のメモリに格納するか、あるいは記憶装置１８７に格納することが可能である。
【０２７６】
本発明の第１の実施の形態による処理を実行するため、上記各ユニットは互いに接続されている。ユニットがハードウェアモジュールとして実装される場合、それらはデータバスによって互いに接続される。
【０２７７】
パラメータ発行ユニット１８２及びルート証明要求受信ユニット１８３は、ネットワークを介して他の装置と通信するために、上記各ユニットと接続されるＣＡ装置１８０内の通信ポート或いは通信ユニットを介してネットワークにデータを送信し、或いはネットワークからデータを受信する。
【０２７８】
上記説明したユーザ側装置及びＣＡ装置は単なる一例である。しかしながら、装置に含まれた構成装置は、上述したユニットに限定されず、その詳細な構成は修正又は変更することが可能である。例えば、装置は、ネットワーク中の計算する装置に一般的に実装される他のユニットを含むことができる。例えば、データを入出力するためのＩ／Ｏインタフェース、ネットワークを介して他の装置に接続するための種々の通信インタフェース、各ユニットの動作を制御するためのコントローラなどである。そのようなユニットについては、この技術分野において一般的であるので図示は省略する。また、当業者によれば上述した装置にそれらのユニットを加えることは容易に考え付くことである。
【０２７９】
上記のように本発明の第１の実施の形態について説明したが、本発明は、第１の実施の形態に記述された内容に限定されない。例えば、ユーザの公開鍵については他の方法によって生成することが可能である。唯一無比の公開鍵（「B. R. Waters, E. W. Felten, A. Sahai, Receiver Anonymity via Incomparable Public Keys, CCS’03, Washington,
DC, USA, pp.112~121, 2003」を参照）は、匿名証明書によって証明されるユーザのデータとして使用することが可能である。また、匿名証明書によって保証されるユーザのデータは、公開鍵に限定されず、ユーザによって送られた任意のデータあるいはメッセージでもよい。さらに、実施の形態は、ＣＡの他の証明技術及び方法に適合させるために修正することが可能である。図１４に示されたアルゴリズムに加えて、アルゴリズムが、匿名証明書がＲＣと同様に立証可能な証明性あるいは秘密性を維持し、同時に、立証者に前記データの所有者の身元に関する情報を分からなくすることを保証する限り、他のアルゴリズムをＲＣからの匿名証明書を計算するために使用することが可能である。第１の実施の形態は、ルート公開鍵が（ｇ，ｙｕ）である場合について説明した。しかし、ルート公開鍵は匿名の公開鍵（ｇｒ，ｙｕｒ）のうちの任意の１つでもよい。
【０２８０】
（第２の実施の形態）
以下、本発明の第２の実施の形態を図１９、図２０を参照して説明する。
【０２８１】
本発明の第２の実施の形態は、公開鍵用の匿名証明書を生成するためにグループ署名方式を採用する。ここで、公開鍵は、唯一の公開鍵、匿名の公開鍵或いはユーザの他の公開鍵等であってもよい。
【０２８２】
グループ署名方式は、過去１５年の間にかなり研究されている（「D. Chaum, E. van Heyst, Group
Signatures, Advances in Cryptology - EUROCRYPTO’91, pp. 257~265, 1991; J.
Camenisch, M. Michels, A Group Signature
Scheme Based on an RSA-Variant, Advances in Cryptology - ASIACRYPT’98, pp.
160~174, 1998; and G. Ateniese, J. Camenisch, M. Joye, G. Tsudik, A Practical and Provably Secure
Coalition-Resistant Group Signature Scheme, Advances in Cryptology -
CRYPTO’2000, pp. 255~270, 2000, which are incorporated as references」を参照）。簡単に説明すると、グループをセット・アップし、グループ・メンバーの承認および取消しを扱うグループ管理者が存在する。全てのグループ・メンバーは同一のグループ公開鍵ＰＫｇを共有するが、各メンバーＵｉはそれぞれ異なる秘密鍵ＳＫｉを有している。メッセージｍが与えられると、グループ・メンバーＵｉはｓ＝ＳＩＧ（ｍ，ＰＫｇ，ＳＫｉ）としてグループを代表してメッセージに署名することが可能である。ここで、ＳＩＧ（ラ）は特有のグループ署名アルゴリズムである。メッセージｍについての署名ｓは、グループ公開鍵ＰＫｇによって照合される。すなわち、与えられたＰＫｇ，ｓ及びｍについて、もしｓ＝ＳＩＧ（ｍ，ＰＫｇ，ＳＫｉ）である場合だけ有効であることを出力する署名照合アルゴリズムＶＥＲＩＦ（ラ）（＝ＶＥＲＩＦ（ｓ，ｍ，ＰＫｇ））が存在する。しかしながら、立証者側装置がｓの署名者Ｕｉを決定するのは非常に困難である。立証者の観点からすると、いかなるグループ・メンバーも、ｓの署名者であることについて同じ確率を有している。この特徴が「グループ署名」の名称の始まりである。
【０２８３】
いくつかのグループ署名方式は、グループ管理者がｓの署名者Ｕｉを決定することができる権限を提供する。すなわち、与えられたＰＫｇ，ｓ及びＳＫｍについて、もしｓ＝ＳＩＧ（ｍ，ＰＫｇ，ＳＫｉ）である場合だけＵｉを出力する署名照合アルゴリズムＴＲＡＣＥ（ラ）（＝ＶＥＲＩＦ（ｓ，ｍ，ＰＫｇ））が存在する。ここで、ＳＫｍはグループ管理者の秘密鍵である。
【０２８４】
図１９は、本発明の第２の実施の形態のシステム構成の概略を示すブロック図である。
【０２８５】
第２の実施の形態によれば、信用機関はグループ管理者Ｍによって組み立てられたグループ１９０である。ユーザＵはグループのメンバーであり、自身に割り当てられたグループ秘密鍵を所有する。従来のグループ署名機構では、メッセージがグループを代表して署名される。しかしながら、本発明の第２の実施の形態では、グループ署名は公開鍵の匿名証明書を生成するために使用される。
【０２８６】
図２０は、第２の実施の形態による、匿名証明方法を示すフローチャートである。
【０２８７】
初期化のステップ２０１において、グループ管理者側装置はグループを組み立てて、グループ公開鍵ＰＫｇを発行する。さらに、グループ管理者側装置は、不適切な振る舞いのユーザを調査する際に利用される秘密鍵ＳＫｍを秘密に保持する。
【０２８８】
ステップ２０２において、グループ・メンバーＵがグループに加わり、このグループ用の自身のグループ秘密鍵ＳＫｕを取得する。
【０２８９】
ステップ２０３において、Ｕが匿名の公開鍵ａｐｋ＝（ｇｒ，ｙｕｒ）（ｍｏｄ  ｐ）を計算する。
【０２９０】
ステップ２０４において、Ｕが１つのメッセージとしてａｐｋを取得し、ｓ＝ＳＩＧ（ａｐｋ，ＰＫｇ，ＳＫｕ）として匿名の公開鍵ａｐｋにデジタル署名する。
上記のように、ｓがａｐｋについてのグループ署名であることは明らかである。
【０２９１】
ステップ２０５において、Ｕが確認用に立証者側装置にｓとａｐｋを送る。また、立証者側装置は、ステップ２０６において、ユーザの匿名公開鍵を証明する。
ＶＥＲＩＦ（ｓ，ａｐｋ，ＰＫｇ）が有効な応答を出力するので、ａｐｋは、匿名のグループ・メンバーによってデジタル署名されるよう立証者側装置に受け入れられる。したがって、ｓは、匿名のグループ・メンバーが匿名の公開鍵ａｐｋを所有することを保証する。すなわち、ｓは匿名の公開鍵ａｐｋについての匿名証明書である。
【０２９２】
本発明による第２の実施の形態において、ルート証明がユーザのグループ秘密鍵であることは言うまでも無い。
【０２９３】
調査が必要な場合、ｓはグループ管理者側装置Ｍに提示される。その結果、調査アルゴリズムＴＲＡＣＥ（ｓ，ＰＫｇ，ＳＫｍ）がＵを出力するので、グループ管理者側装置はＵの身元を決定し明かすことが可能である。
【０２９４】
上記の例において、ユーザのデータは匿名の公開鍵である。しかしながら、ユーザのデータは、唯一の公開鍵或いはユーザの他の公開鍵のような、ユーザの他のデータであってもよい。
【０２９５】
本発明による第２の実施の形態のユーザ側装置は、図１７に示した装置１７０と共通である。
第２の実施の形態においては、ルート証明ユニットはグループ管理者側装置からユーザのグループ秘密鍵を受け取る。匿名証明書生成ユニットはグループ署名によって匿名証明書を生成する。また、送信ユニットは、ネットワークに対して匿名証明書を備えるユーザのデータを送信する。第２の実施の形態のルート証明要求ユニットは、グループメンバーシップの要求を生成し、その要求をグループ管理者側装置に送信するために使用される。
【０２９６】
上述したように、グループ署名証明アルゴリズムを通して、立証者側装置はユーザのデータがグループ・メンバーによって照合されると確認することが可能である。しかしながら、多くの場合、立証者側装置は、グループ・メンバーの名のもとに署名されたデータを送るユーザがデータの真の所有者か、そのデータに署名する本当のメンバーかどうかを確認する必要がある。
【０２９７】
図２１は、ユーザが従来のグループ署名機構を有するグループに属していることを立証者側装置へ証明する処理を示す図である。
【０２９８】
図２１に示すように、最初に、立証者側装置は呼掛けメッセージを生成し（ステップ２１１）、証明者側装置にそれを送る。
立証者側装置から呼掛けメッセージを受け取ると、証明者側装置は、自身のグループ秘密鍵を使用することにより呼掛けメッセージに署名し（ステップ２１２）、立証者側装置へ生成されたグループ署名を送る。
その後、立証者側装置は、グループ公開鍵と一緒に証明者側装置から受け取られたデータについてグループ署名照合を行なう（ステップ２１３）。正確な照合は、証明者がグループ内に属することを立証者に確信させる。
【０２９９】
従来のグループ署名機構では、証明者側装置が立証者側装置によって生成された呼掛けメッセージに応答し、オンライン上で呼掛けメッセージ用のグループ署名を計算することに注意する必要がある。グループ署名のそのようなオンライン計算は時間を要しかつコスト高である。さらに、証明者側装置が立証者側装置と数回連絡をとる場合、立証者側装置は毎回新しい呼掛けメッセージを生成し、かつ証明者側装置は数個のグループ署名を計算しなければならない。
【０３００】
本発明による第２の実施の形態の解決方法は、匿名証明書及びユーザのデータ（つまり、ユーザ自身の公開鍵）の妥当性を認証するのにより便利であり、かつ効率的である。
【０３０１】
図２２は、本発明による第２の実施の形態の解決法によって匿名証明書及び公開鍵の妥当化を検査する処理を示す図である。
【０３０２】
図２２に示すように、証明者側装置は、グループ署名を前もって生成するために、自身のグループ秘密鍵を使用することにより公開鍵に署名する（ステップ２２１）。
証明者側装置が立証者側装置と連絡をとる場合、証明者側装置は、生成された匿名証明書（つまりその公開鍵に対応するグループ署名）と共に公開鍵を立証者側装置へ送る。
証明者側装置から公開鍵および匿名証明書を受け取ると、立証者側装置は、ユーザのデータについて匿名証明書及びグループ公開鍵によるグループ署名照合を行なう（ステップ２２２）。正確な照合は、公開鍵がグループ・メンバーによって署名されてることを立証者に確信させる。立証者が、ユーザがその公開鍵に署名する正当なグループ・メンバーであるかどうかを知りたい場合、立証者は公開鍵に関する知識を証明してくれるように証明者側装置に依頼することができる。ステップ２２３および２２４において、知識証明が公開鍵に対して保持される。詳細な検証処理は、図１５において示される処理と同様である。証明者側装置が公開鍵に対応する秘密鍵についての知識を立証者側装置に証明する場合、立証者は証明者側を信頼するはずである。
【０３０３】
本発明による上述した方法では、匿名証明書が、立証者側装置の呼掛けに応じてオンライン上で計算されるのではなく、予め計算されることが明らかである。すなわち、証明者は、証明者側の計算装置が空いた時間にグループ署名を算出することが可能である。立証者側装置と連絡をとる前に、公開鍵だけでなく複数の匿名証明書も既に利用可能である。立証者側装置と連絡をとる場合、証明者側装置は匿名証明書と一緒に公開鍵を立証者側装置へ送る必要があるだけである。立証者側装置は、匿名証明書の有効性をチェックする。その後、証明者側装置は、立証者側装置に公開鍵に対応する秘密鍵についての知識だけを証明する。この証明は、グループ署名の署名より非常に効率的である。
【０３０４】
図２３は、本発明による第２の実施の形態の解決法によって匿名証明書及び公開鍵の妥当性を証明する他の処理を示す図形である。
【０３０５】
立証者側装置が正確に検査された公開鍵を格納していると仮定する。立証者側装置が証明者側装置から匿名証明書と一緒に公開鍵を受け取ると（ステップ２３１）、立証者側装置は受信した公開鍵を正確に検査され格納された公開鍵と比較する（ステップ２３２）。受信した公開鍵が格納された公開鍵のうちの１つと一致する場合、立証者側装置は、公開鍵に関する知識証明に直接進むことが可能である（ステップ２３５）。一致した公開鍵がない場合、立証者側装置は受信した公開鍵について公開鍵及びグループ公開鍵の匿名証明書によるグループ署名照合を行なう（ステップ２３３）。受信した匿名証明書がグループ署名照合をパスした場合、立証者側装置は、正確に検査された公開鍵として受信した公開鍵を格納する（ステップ２３４）。次に、処理はステップ２３５に進む。グループ署名照合をパスしない場合、処理は終了する。
【０３０６】
証明者側装置が同じ匿名証明書で立証者側装置に複数回連絡をとる場合、立証者側装置は最初に匿名証明書の有効性をチェックする必要がある。次のセションにおいて、立証者側装置は、証明者側装置から受け取った公開鍵をローカルに貯えられた公開鍵と照合する。一致するものがあれば、立証者側装置と証明者側装置は公開鍵に関する知識証明に直接進むことが可能である。この種の利用法はとても効率的であり、かつ匿名及び信用が全て維持されている。
【０３０７】
図２４は、本発明による第２の実施の形態の証明ユニットの例を示すブロック図である。証明ユニット２４０は、立証者側の計算装置に設置されるか、あるいは図１７に示した検証ユニット１７８としてユーザ側装置に設置される。
【０３０８】
証明ユニット２４０は、グループ署名及び公開鍵についての照合を行なうために照合モジュール２４５を備える。照合モジュール２４５は、グループ署名照合部２４１及び公開鍵知識照合部２４２に分割されている。証明者側装置からのグループ署名と対になった公開鍵を受け取った時、照合モジュール２４５は、受信した公開鍵及びグループ公開鍵を使用することにより、グループ署名照合部２４１でグループ署名を照合する。証明者側装置から受け取った公開鍵がグループ署名照合部２４１によって正確に照合された後、公開鍵知識照合部２４２はグループ署名と共に受け取った公開鍵に関する証明者について知識証明を実行する。
【０３０９】
証明ユニット２４０は、照合モジュール２４５に接続されたメモリ２４３と、照合モジュール２４５及びメモリ２４３に接続された比較モジュール２４４をさらに備える。メモリ２４３は、予め正確に検査された公開鍵を格納する。証明者側装置から公開鍵及びグループ署名を受け取った場合、比較モジュール２４４は、受信した公開鍵をメモリ２４３に格納された公開鍵と比較し、比較の結果を照合モジュール２４５に通知する。受信した公開鍵が予め正確に検査された公開鍵のうちの１つと同じである場合、照合モジュール２４５は、グループ署名照合アルゴリズムの計算をスキップし、公開鍵知識照合部２４２によって、証明者についてグループ署名と共に受け取られた公開鍵に関する知識証明を実行する。受信した公開鍵が格納された公開鍵のうちの１つと一致しない場合、照合モジュール２４５は、グループ署名照合部２４１によって上述したようなグループ署名照合アルゴリズムの計算を実行する。
【０３１０】
本発明によれば、信用機関がＣＡである場合、証明書と公開鍵についての照合は同様の方法で実行することが可能である。図１５を参照すると、匿名の公開鍵及び匿名証明書がユーザ側装置によって計算された後、匿名の公開鍵は、備えられた匿名証明書と共に立証者側装置へ送られる（ステップ１５１）。その後、立証者側装置は、匿名証明書及び匿名の公開鍵を検査するためにユーザについて知識証明を実行する（ステップ１５３）。ステップ１５３に示されるように、本発明では、匿名証明書及び匿名の公開鍵を一回の知識証明で一緒に検査することが可能である。１つの実施例では、ユーザ側装置はオフラインの方法で匿名の公開鍵、匿名証明書、及び知識証明に必要なデータを計算する。そのようなデータを受け取った後に、立証者側装置はローカルの計算を通じて匿名証明書及び公開鍵を検査することが可能である。他の実施例では、立証者側装置は、常時正確に検査される公開鍵を格納する。ユーザ側装置によって送信された証明書と公開鍵を検査する度に、立証者側装置は、まずユーザの公開鍵を格納されたものと比較する。一致が得られる場合、それは公開鍵が正確に検査されるものであることを意味する。ユーザについての知識証明中に、立証者側装置は、証明書に関する知識証明の計算をバイパスすると思われる。ユーザについての公開鍵に関する証明だけが必要である。従来の解決方法における証明書と公開鍵のオンライン照合と順次進行型の照合と比較して、本発明による上述した照合はより効率的である。
【０３１１】
信用機関がＣＡである場合、立証者側装置中の証明ユニットはさらに照合モジュールを含む。１つの実施例によれば、証明ユニットは、例えば、図１５のステップ１５３に示されるような知識証明を実行する。他の実施例では、証明ユニットは、さらに、照合モジュールに接続されるメモリと、照合モジュール及びメモリに接続される比較モジュールを備えることが可能である。
そのメモリは、正確に検査された公開鍵を格納する。証明者側装置から証明書と公開鍵を受け取ると、比較モジュールは、受信した公開鍵をメモリに格納された公開鍵と比較し、その比較の結果を照合モジュールに通知する。受信した公開鍵が予め正確に検査された公開鍵のうちの１つと同じである場合、照合モジュールは証明書に関する知識証明の計算をスキップし、単に証明者について公開鍵に関する知識証明を実行する。また、例えば、受信した公開鍵が格納された公開鍵のうちの１つと一致しない場合、図１５のステップ１５３に示されるように、照合モジュールは証明書と公開鍵に関する知識証明の計算を実行する。
【０３１２】
本発明による２つの場合について、証明書及びユーザのデータの照合のための方法及び装置を説明したが、本発明は上述した具体例に限定されない。当業者によれば、特定のアプリケーションやアルゴリズムに従って、照合のための方法と装置についての変形と変更を加えることが可能である。
【０３１３】
本発明によれば、匿名の公開鍵が信用機関によって証明される匿名証明書によって保証される場合、ユーザは信頼できる匿名の公開鍵を生成することが可能であることが、上述した説明から理解できる。ユーザ・プライバシ保護の機能は完全に施される。ユーザは、自身による別個の匿名の公開鍵だけでなく、自身による別個の匿名証明書を生成する。本発明による実施の形態において、ＣＡの介在は最小限である。よって、信用機関の負荷の軽減化を実現することが可能である。さらに、匿名証明書はＣＡ或いはグループ管理者レベルで追跡可能であるので、ユーザが匿名性を乱用するのは不可能である。
【０３１４】
本発明は、ハードウェア、ソフトウェア、ファームウェア或いはそれらの組合せによって実現することができ、システム、サブシステム、構成要素あるいはサブ構成要素において利用することができる。ソフトウェアで実現される場合、本発明の要素は本質的にプログラム、あるいは必要なタスクを実行するのに使用される命令セグメントである。プログラム又は命令セグメントは、コンピュータ読み取り可能な媒体に格納されるか、あるいは伝送ケーブル又は通信リンク上の搬送波であるたデータ信号によって送信される。「コンピュータ読み取り可能な媒体」は、情報を格納するか転送することができる任意の媒体を含む。コンピュータ読み取り可能な媒体の例としては、電子回路、半導体記憶装置、ＲＯＭ、フラッシュ・メモリ、消去可能なＲＯＭ（ＥＲＯＭ）、フロッピー（登録商標）ディスケット、ＣＤ−ＲＯＭ、光ディスク、ハードディスク、光ファイバー媒体、無線（ＲＦ）リンクなどが含まれる。データ信号は、電子ネットワークチャネル、光ファイバ、空気、電磁気、ＲＦリンク等の伝送媒体上で伝播することが可能な任意の信号を含む。命令セグメントは、インターネット、イントラネット等のようなコンピュータネットワークを介してダウンロードすることが可能である。
【０３１５】
本発明は、その思想あるいは本質的特徴から外れない範囲で、他の特定の態様において具体化されることも可能である。例えば、システムアーキテクチャーが本発明の基本的な特徴を外れない限り、実施の形態において説明したアルゴリズムは変更することができる。また、本実施例は、全ての点において具体的な例として考慮され、限定的に考慮されるものではない。また、本発明の範囲は、実施例の記載ではなく請求の範囲によって示される。さらにクレームと同等の意味及び範囲内に含まれる全ての変形例は本発明に包含される。
【図面の簡単な説明】
【０３１６】
本発明の前述の目的及び他の目的、本発明の本質及び本発明の各特徴は、以下に述べる説明を添付図面と共に読まれることにより十分に理解されるだろう。
【図１】ＡＰＫ方法によって秘匿化する公開鍵暗号方式を用いる２つの端末装置(端末装置のうちの一方が、他方の端末装置との新しい通信セッション用の種々の公開鍵を公開する)を備えた好適なシステムを示すブロック図である。
【図２】ＡＰＫ方法によって秘匿化する公開鍵暗号方式を用いるいくつかの端末装置(ある端末装置が、異なる通信用に異なる公開鍵を有する他の端末装置と通信する)を備えた好適なシステムの例を示す図である。
【図３】図１と図２で例をあげて説明した通信システムに参加する送信機と受信機の間の好適な通信セッション例を示す図である。
【図４】ＡＰＫ方法による公開鍵−秘密鍵のペアに基づいた通信セッションにおける送信機と受信機の好適な機能ブロック図である。
【図５】ＡＰＫ方法による図４に示すＡＰＫ生成装置の好適な機能ブロック図である。
【図６】秘匿化された公開鍵を生成するＡＰＫ方法による生成フローを示すフローチャートである。
【図７】ＡＰＫ方法によるメッセージの暗号化及び復号化の好適な手続き例を示す図である。
【図８Ａ】本発明の一般的概念を概略的に示すブロック図である。
【図８Ｂ】本発明の一般的な検証プロセスを概略的に示すフローチャートである。
【図９】本発明の第１の実施の形態によるシステム構成の概要を示すブロック図である。
【図１０】第１の実施の形態によるシステムスタートアップ段階におけるＣＡ装置初期化プロセスの例を示すフローチャートである。
【図１１】第１の実施の形態によるシステムスタートアップ段階中にユーザ側装置初期化プロセスの例を示すフローチャートである。
【図１２】第１の実施の形態によるＲＣ要求プロセスの例を示すフローチャートである。
【図１３】ユーザ側装置が第１の実施の形態に従ってどのように匿名の公開鍵を生成するかを示すフローチャートである。
【図１４】第１の実施の形態による匿名の公開鍵のためのルート証明書からユーザ側装置がどのように匿名証明書を取得するかを示すフローチャートである。
【図１５】第１の実施の形態による匿名の認証プロセスの例を示すフローチャートである。
【図１６】第１の実施の形態による検査プロセスを示すフローチャートである。
【図１７】第１の実施の形態によるユーザ側装置の構成を示すブロック図である。
【図１８】第１の実施の形態によるＣＡ側装置の構成を示すブロック図である。
【図１９】本発明の第２の実施の形態によるシステム構成の概要を示すブロック図である。
【図２０】第２の実施の形態による匿名を証明する方法の例を示すフローチャートである。
【図２１】ユーザが従来のグループ署名機構を有するグループに属していることを立証者側装置へ証明する処理を示す図である。
【図２２】本発明による第２の実施の形態の解決法によって匿名証明書及び公開鍵の妥当化を検査する処理を示す図である。
【図２３】本発明による第２の実施の形態の解決法によって匿名証明書及び公開鍵の妥当化を検査する他の処理を示す図である。
【図２４】本発明による第２の実施の形態の証明ユニットの例を示すブロック図である。
【図２５】証明書が証明書機関（Ｃｅｒｔｉｆｉｃａｔｅ  Ａｕｔｈｏｒｉｔｙ）によって発行される従来の証明書システムを示すブロック図である。
【図２６】証明書がユーザの友人によって発行される従来の他の証明書システムを示すブロック図である。
【符号の説明】
【０３１７】
Ａ、ａ，ｂ，・・・，ｚ１０：端末装置
Ｅ，Ｅａ，Ｅｂ，・・・，Ｅｚ：公開鍵
ｘ，ｘａ，ｘｂ，ｘｃ，・・・，ｘｚ：秘密鍵
４１：送信機
４２：受信機
４３，４４：送信装置
４５，４６：受信装置
４７：復号化装置
４８：暗号化装置
４９：公開鍵生成装置
５１：グループ選択手段
５２：部分グループ選択手段
５３：ジェネレータ選択手段
５４：記憶部
５５：制御装置
５６：整数選択手段
５７：グループ指数演算子
１７０：ユーザ側装置
１７１：ルート証明ユニット
１７２：匿名証明書生成ユニット
１７３：送信ユニット
１７４：ルート証明要求ユニット
１７５：匿名公開鍵生成ユニット
１７６：証明ユニット
１７７：記憶装置
１７８：検証ユニット
１８０：ＣＡ側装置（信用機関側装置）
１８１：システムパラメータ計算ユニット
１８２：パラメータ発行ユニット
１８３：ルート証明要求受信ユニット
１８４：ルート証明生成ユニット
１８５：検査ユニット
１８６：調査ユニット
１９０：グループ
２４０：証明ユニット
２４１：グループ署名照合部
２４２：公開鍵知識照合部
２４３：メモリ
２４４：比較モジュール
【誤訳訂正３】
【訂正対象書類名】図面
【訂正対象項目名】全図
【訂正方法】変更
【訂正の内容】
【図１】
2007089171.tif 000090
【図２】
2007089171.tif 000091
【図３】
2007089171.tif 000092
【図４】
2007089171.tif 000093
【図５】
2007089171.tif 000094
【図６】
2007089171.tif 000095
【図７】
2007089171.tif 000096
【図８Ａ】
2007089171.tif 000097
【図８Ｂ】
2007089171.tif 000098
【図９】
2007089171.tif 000099
【図１０】
2007089171.tif 000100
【図１１】
2007089171.tif 000101
【図１２】
2007089171.tif 000102
【図１３】
2007089171.tif 000103
【図１４】
2007089171.tif 000104
【図１５】
2007089171.tif 000105
【図１６】
2007089171.tif 000106
【図１７】
2007089171.tif 000107
【図１８】
2007089171.tif 000108
【図１９】
2007089171.tif 000109
【図２０】
2007089171.tif 000110
【図２１】
2007089171.tif 000111
【図２２】
2007089171.tif 000112
【図２３】
2007089171.tif 000113
【図２４】
2007089171.tif 000114
【図２５】
2007089171.tif 000115
【図２６】
2007089171.tif 000116
【外国語明細書】
2007089171000001.pdf