(57)【要約】【課題】証明者と検証者が同一である状況において、複数の識別子についての認証を効率良く行うための技術を提供する。【解決手段】識別子Ｙｉ（ｉ＝１，…，ｄ）と、その識別子Ｙｉを検証可能な認証情報ＸｉについてのＮＰ関係Ｒがｐ−加法的であるとし、そのＮＰ関係Ｒについての対話証明方法をπとし、ｅｉ（以下、ｅｉをｅｉとも表記する。）を証明者装置が事前に予測することが困難なｉごとに定まる１からｐまでの第一の乱数とし、対話証明バッチ実行システムが、識別子として代表識別子ΠｉＹｉｅｉ又は代表識別子ΣｉｅｉＹｉを用い、認証情報としてその代表識別子に対応する代表認証情報を用いて、上記対話証明方法πを行う。【選択図】図１
2008172686.tif 000002
【特許請求の範囲】
【請求項１】
識別子Ｙｉ（ｉ＝１，…，ｄ）と、その識別子Ｙｉを検証可能な認証情報ＸｉについてのＮＰ関係Ｒがｐ−加法的であるとし、そのＮＰ関係Ｒについての対話証明方法をπとし、ｅｉ（以下、ｅｉをｅｉとも表記する。）を証明者装置が事前に予測することが困難なｉごとに定まる１からｐまでの第一の乱数とし、
対話証明バッチ実行システムが、識別子として代表識別子ΠｉＹｉｅｉ又は代表識別子ΣｉｅｉＹｉを用い、認証情報としてその代表識別子に対応する代表認証情報を用いて、上記対話証明方法πを行う対話証明バッチ実行方法。
【請求項２】
請求項１に記載の対話証明バッチ実行方法において、
証明者装置が、第二の乱数を生成して、その第二の乱数と共通パラメータとを少なくとも用いて生成した第一送信情報を検証者装置に送信する第一送信情報送信ステップと、
検証者装置が、第三の乱数を生成して、証明者装置に送信する第三乱数送信ステップと、
証明者装置が、代表認証情報ΠｉＸｉｅｉ又は代表認証情報ΣｉｅｉＸｉと、上記第二の乱数と、上記第三の乱数と、を少なくとも用いて生成した第二送信情報を検証者装置に送信する第二送信情報送信ステップと、
検証者装置が、上記第一送信情報が、代表識別子ΠｉＹｉｅｉ又は代表識別子ΣｉｅｉＹｉと、上記第二送信情報と、共通パラメータとを少なくとも用いて生成した値と同じであるかを検証し、その検証に成功した場合には、上記複数の識別情報のすべてについて検証が成功したと判断する検証ステップと、
を有することを特徴とする対話証明バッチ実行方法。
【請求項３】
請求項１又は請求項２に記載の対話証明バッチ実行方法において、さらに、
検証者装置が、上記第一の乱数ｅｉを生成して、証明者装置に送信するステップを含むことを特徴とする対話証明バッチ実行方法。
【請求項４】
請求項１から請求項３の何れかに記載の対話証明バッチ実行方法において、
上記識別子としてΠｉＹｉ（ｅｉ  ｍｏｄ  ｐ）又はΣｉ（ｅｉ  ｍｏｄ  ｐ）Ｙｉを用いることを特徴とする対話証明バッチ実行方法。
【請求項５】
請求項２から請求項４の何れかに記載の対話証明バッチ実行方法において、
上記認証情報としてΠｉＸｉ（ｅｉ  ｍｏｄ  ｐ）又はΣｉ（ｅｉ  ｍｏｄ  ｐ）Ｘｉを用いることを特徴とする
【請求項６】
請求項１から請求項５の何れかに記載の対話証明バッチ実行方法において、
上記乱数ｅｉは、ｅｉ−１であることを特徴とする対話証明バッチ実行方法。
【請求項７】
識別子Ｙｉ（ｉ＝１，…，ｄ）と、その識別子Ｙｉを検証可能な認証情報ＸｉについてのＮＰ関係Ｒがｐ−加法的であるとし、そのＮＰ関係Ｒについての対話証明方法をπとし、ｅｉ（以下、ｅｉをｅｉとも表記する。）を証明者装置が事前に予測することが困難なｉごとに定まる１からｐまでの第一の乱数とし、
識別子として代表識別子ΠｉＹｉｅｉ又は代表識別子ΣｉｅｉＹｉを用い、認証情報としてその代表識別子に対応する代表認証情報を用いて、上記対話証明方法πについての対話証明方法を行う対話証明バッチ実行システム。
【請求項８】
ｅｉ（以下、ｅｉをｅｉとも表記する。）を証明者装置が事前に予測することが困難なｉごとに定まる１からｐまでの第一の乱数とし、
乱数発生手段が、第二の乱数を生成する乱数発生ステップと、
第一送信情報生成手段が、上記第二の乱数と共通パラメータとを少なくとも用いて生成した第一送信情報を検証者装置に送信する第一送信情報送信ステップと、
第二送信情報生成手段が、代表認証情報ΠｉＸｉｅｉ又は代表認証情報ΣｉｅｉＸｉと、上記第二の乱数と、検証者装置が生成した第三の乱数と、を少なくとも用いて生成した第二送信情報を検証者装置に送信する第二送信情報送信ステップと、
を有する証明者装置。
【請求項９】
ｅｉ（以下、ｅｉをｅｉとも表記する。）を証明者装置が事前に予測することが困難なｉごとに定まる１からｐまでの第一の乱数とし、
乱数検証者装置が、第三の乱数を生成して、証明者装置に送信する第三乱数送信ステップと、
検証手段が、証明者装置が生成した第一送信情報が、代表識別子ΠｉＹｉｅｉ又は代表識別子ΣｉｅｉＹｉと、証明者装置が生成した第二送信情報と、共通パラメータとを少なくとも用いて生成した値と同じであるかを検証し、その検証に成功した場合には、上記複数の識別情報のすべてについて検証が成功したと判断する検証ステップと、
を有する検証者装置。
【請求項１０】
請求項８に記載の証明者装置としてコンピュータを機能させるための証明者装置プログラム。
【請求項１１】
請求項９に記載の検証者装置としてコンピュータを機能させるための検証者装置プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
証明者（装置）がある知識を有していることを対話によって検証者（装置）に証明する対話証明方法に関し、特に、複数の知識を有していることを効率良く証明するための対話証明バッチ実行方法、そのシステム、証明者装置、検証者装置、それらのプログラムに関する。
【背景技術】
【０００２】
まず、ＧｕｉｌｌｏｕとＱｕｉｓｑｕａｔｅｒによる対話証明方法を示す。νは公開された共通パラメータであり、素数である。効率のために、νは小さな値で、ハミングウェイトが小さいことが望ましい。Ｎは、素因数分解が困難な自然数であり、認証情報発行者によって選ばれる。認証情報発行者は、Ｎの素因数分解を知っているが、秘密に保つとする。
【０００３】
Ｙ∈（Ｚ／ＮＺ）＊を識別子とする。認証情報発行者は、Ｎの素因数に関する情報を用いて、Ｙ＝Ｘ−ν  ｍｏｄ  ＮとなるＸを計算する。Ｘは、識別子Ｙに対応する認証情報である。認証情報Ｘを保持する証明者が、検証者に対して、識別子Ｙに関する認証を行うためには、すなわち、認証情報Ｘを有していることを証明するためには、次のプロトコルに従って計算する。
【０００４】
１．証明者は、乱数ｒ∈｛１，…，Ｎ−１｝を選び、第一送信情報Ｔ＝ｒνｍｏｄ  Ｎを計算し、この第一送信情報Ｔを検証者に送信する。
２．検証者は、乱数ｃ∈｛１，…，ν−１｝を選び、この乱数ｃを証明者に送信する。
３．証明者は、第二送信情報Ｄ
Ｄ＝ｒＸｃ  ｍｏｄ  Ｎ…（１）
を計算し、この第二送信情報Ｄを検証者に送信する。
４．検証者は、
Ｔ＝ＤνＹｃ  ｍｏｄ  Ｎ…（２）
であることを検証する。検証に成功すれば、検証者は認証を受け入れる。
このＧｕｉｌｌｏｕとＱｕｉｓｑｕａｔｅｒによる対話証明方法は、完全ゼロ知識証明であることが知られている（例えば、非特許文献１参照。）。
【０００５】
次に、ＢｏｎｅｈとＦｒａｎｋｌｉｎによる対話証明方法を示す。Ｅ［ｐ］、Ｆを位数ｐの有限可換群とし、ｅｐ：Ｅ［ｐ］×Ｅ［ｐ］→Ｆを双線形写像とする。例えば、Ｅ［ｐ］をある楕円曲線のｐ−捩れ点の集合、Ｆを有限体の単元がなす群（部分群でも良い。）、ｅｐをＷｅｉｌペアリングとすることができる。
【０００６】
認証情報発行者は、自然数ｕを秘密に選び、Ｇ∈Ｅ［ｐ］を選び、Ｈ＝ｕＧを計算する。Ｇ，Ｈを共通パラメータとして公開する。識別子Ｙ∈Ｅ［ｐ］に対して、認証情報Ｘを保持する証明者が、検証者に対して、識別子Ｙに関する認証を行うためには、すなわち、認証情報Ｘを有していることを証明するためには、次のプロトコルに従って計算する。
【０００７】
１．証明者は、乱数ｋ∈｛１，…，ｐ−１｝を選び、第一送信情報ｒ
ｒ＝ｅｐ（Ｙ，Ｇ）ｋ  …（３）
を計算し、この第一送信情報ｒを検証者に送信する。
２．検証者は、乱数ｃ∈｛１，…，ｐ−１｝を選び、この乱数ｃを証明者に送信する。
３．証明者は、第二送信情報Ｓ
Ｓ＝ｃＸ＋ｋＹ  …（４）
を計算し、この第二送信情報Ｓを検証者に送信する。
４．検証者は、
ｒ＝ｅｐ（Ｓ，Ｇ）ｅｐ（Ｙ，Ｈ）−ｃ  …（５）
であることを検証する。検証に成功すれば、検証者は認証を受け入れる。
このＢｏｎｅｈとＦｒａｎｋｌｉｎによる対話証明方法は、完全ゼロ知識証明であることが知られている（例えば、非特許文献２参照。）。
【非特許文献１】L.Guillou and J.Quisquater,“A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory”，Advances in Cryptology-EUROCRYPT’88, Springer-Verlag, 1988.，pp.123-128
【非特許文献２】D.Boneh and M.Franklin,“Identity based encryption from the Weil pairing”，Advances in Cryptology-CRYPTO 2001, LNCS2139, Springer-Verlag, 2001.，pp.213-229
【発明の開示】
【発明が解決しようとする課題】
【０００８】
複数の識別子について認証を行う場合、背景技術に記載された方法では、識別子の数だけ、上記背景技術に記載した対話証明方法を繰り返し行う必要がある。このため、認証に用いる識別子の数が増大した場合に、認証の効率が低下するという問題がある。
【０００９】
本発明は、複数の識別子について認証を行う場合に、効率良く認証を行う対話証明バッチ実行方法、そのシステム、証明者装置、検証者装置、それらのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
識別子Ｙｉ（ｉ＝１，…，ｄ）と、その識別子Ｙｉを検証可能な認証情報ＸｉについてのＮＰ関係Ｒがｐ−加法的であるとし、そのＮＰ関係Ｒについての対話証明方法をπとし、ｅｉ（以下、ｅｉをｅｉとも表記する。）をｉごとに定まる１からｐまでの乱数とし、
対話証明バッチ実行システムが、識別子として代表識別子Πｉｙｉｅｉ又は代表識別子Σｉｅｉｙｉを用い、認証情報としてその代表識別子に対応する代表認証情報を用いて、上記対話証明方法πを行う。
【発明の効果】
【００１１】
複数の識別子を代表する代表識別子と、複数の認証情報を代表する代表認証情報とを用いて対話証明のバッチ実行を行うことにより、上記複数の識別子について同時に認証することができる。このため、計算量、通信量ともに抑制され認証の効率が向上する。
【発明を実施するための最良の形態】
【００１２】
［理論的背景］
まず、ｐ−加法的ＮＰ関係の概念について説明をする。ＲをＮＰ関係とし、言語ＬＲを、
ＬＲ＝｛Ｙ∈｛０，１｝＊｜（Ｙ，Ｘ）∈Ｒ  for some   Ｘ∈｛０，１｝｝とする。また、ウィットネス（認証情報）の集合を
Ｗ（Ｙ）＝｛Ｘ∈｛０，１｝＊｜（Ｙ，Ｘ）∈Ｒ｝，Ｗ＝∪ＹＷ（Ｙ）
と書くことにする。ＬＲが、アーベル群の構造を持ち、群の演算はすべて多項式時間で実行可能であるとする。以下、この群を乗法的に記述する。さらに、Ｘ１∈Ｗ（Ｙ１）とＸ２∈Ｗ（Ｙ２）を入力として、Ｙ１Ｙ２に対応した認証情報Ｘ∈Ｗ（Ｙ１Ｙ２）を出力する多項式時間アルゴリズムが存在するとする。このとき、Ｒを加法的と呼ぶ。さらに、ある自然数ｐ（望ましくは、素数）について、任意のＹ∈ＲについてＹｐ＝１となるとき、ＮＰ関係Ｒをｐ−加法的と呼ぶ。
【００１３】
例えば、背景技術に記載した、ＧｕｉｌｌｏｕとＱｕｉｓｑｕａｔｅｒによる対話証明方法と、ＢｏｎｅｈとＦｒａｎｋｌｉｎによる対話証明方法とはいずれもｐ−加法的ＮＰ関係Ｒについての対話証明方法である。
【００１４】
なぜなら、ＧｕｉｌｌｏｕとＱｕｉｓｑｕａｔｅｒによる対話証明方法においては、Ｒ＝｛（Ｙ，Ｘ）｜Ｙ＝Ｘ−ν  ｍｏｄ  Ｎ｝であり、識別子Ｙ１と認証情報Ｘ１、識別子Ｙ２と認証情報Ｘ２が与えられた場合には、Ｙ１＝Ｘ１−ν  ｍｏｄ  ＮとＹ２＝Ｘ２−ν  ｍｏｄ  Ｎとから、Ｙ１Ｙ２に対応する認証情報を、（Ｘ１Ｘ２）―νと計算することができる。また、ＢｏｎｅｈとＦｒａｎｋｌｉｎによる対話証明方法においては、Ｒ＝｛（Ｙ，Ｘ）｜Ｘ＝ｕＹ  ｍｏｄ  ｐ｝であり、群を加法的に記述すると、識別子Ｙ１と認証情報Ｘ１、識別子Ｙ２と認証情報Ｘ２が与えられた場合には、Ｘ１＝ｕＹ１  ｍｏｄ  ｐとＸ２＝ｕＹ２  ｍｏｄ  ｐとから、Ｙ１＋Ｙ２に対応する認証情報を、ｕ（Ｘ１＋Ｘ２）と計算することができるためである。
【００１５】
ここで、識別子Ｙｉ（ｉ＝１，…，ｄ）と、その識別子Ｙｉを検証可能な認証情報ＸｉについてのＮＰ関係Ｒがｐ−加法的であるとし、そのＮＰ関係Ｒについての対話証明方法をπとする。また、ｉごとに定まる乱数ｅｉ（ｅｉとも表記する。）を、ｅｉ∈｛０，…，ｐ−１｝とする。このとき、代表識別子Πｉｙｉｅｉ又は代表識別子Σｉｅｉｙｉを識別子として用い、選択された代表識別子に対応する代表認証情報を認証情報として用いて、上記対話証明方法πを行うことにより、すべての識別子Ｙｉについての認証を同時に行うことができる。ここで、代表認証情報は、上記ｐ―加法的ＮＰ関係Ｒの定義により多項式時間で容易に計算することができる。この代表識別子と代表認証情報とを用いて上記対話証明方法πを実行する対話証明方法をπｄとする。
【００１６】
上記代表識別子を用いて対話証明方法πを行うことにより、各識別子について認証を行うことができるのは、次の定理１、定理２が成立するためである。以下、定理１、定理２とそれらの証明について説明をする。
＜定理１＞対話証明方法πが、（完全、統計量的、計算量的）ゼロ知識証明である場合には、対話証明方法πｄも（完全、統計量的、計算量的）ゼロ知識証明となる。
＜定理２＞対話証明方法πが知識健全である場合には、対話証明方法πｄも知識健全である。
【００１７】
≪証明≫定理１が成立するのは、対話証明方法πｄは、対話証明方法πの入力として代表識別子と代表認証情報を用いたものであるためである。
以下、定理２について証明をする。Ｐ＊（以下、Ｐ＊とも表記する。）をπｄの必ずしも正常系とは限らない証明者とする。Ｐ＊の証明が、検証者Ｖに受理される確率をｐ（Ｙ１，Ｙ２，…，Ｙｄ）＝Ｐｒｏｂ［（Ｐ＊，Ｖ）∈Ａｃｃ］とする。ここで、（Ｐ＊，Ｖ）は、証明者Ｐ＊と検証者Ｖとの間の対話である。
【００１８】
ｅ∈Ｚ／ｐＺについて、πｄにおけるＶと同様のアルゴリズムで、ｅをランダムに選ぶ代わりに常にｅを送信するものを考える。それを、Ｖｅと書くことにする。
Ｋｐをπにおける知識抽出機とする。Ｋの動作時間の期待値は、高々ｋｃ／（ｐ（Ｙ１，Ｙ２，…，Ｙｄ）−ε（ｋ））である。ここで、εは無視できる関数であり、πの知識誤りである。
【００１９】
次のＰ＊−オラクル機械を考える。
１．ｉ←１
２．ｅ←｛０，…，ｐ−１｝をランダムに選ぶ。πをＰ＊とＶｅとの間で実行する。もし証明が受理されなければ、ステップ２に戻る。
３．もしｅ∈｛ｅ１，ｅ２，…，ｅｉ−１｝ならば、ステップ２に戻る。
４．ＫＰ＊を実行し、動作時間が、４ｋｃ／（ｐ（Ｙ１，Ｙ２，…，Ｙｄ）−ε（ｋ））に達した場合は実行を中断する。もし、ＫＰ＊があるＸで、（ΠｊＹｊ＾（ｅｊ−１  ｍｏｄ  ｐ），Ｘ）∈Ｒとなるものを出力すれば、次のステップに進む。そうでなければ、ステップ２に戻る。
５．ｅｉ←ｅ，Ｘｉ←Ｘ，Ｙｉ’＝ΠｊＹｊＨ（ｅ，ｊ）と置き、ｉ←ｉ＋１とする。ここで、Ｈ：｛０，１，…，ｐ−１｝×Ｎ→｛０，１，…，ｐ−１｝はハッシュ関数である。もし、ｉ≦ｄならば、ステップ２に戻る。
６．有限体Ｆｐに値を持つ、ｄ×ｄ行列Ｅを次のように構成する。Ｅｉ，ｊ＝Ｈ（ｅｉ，ｊ）。もし、ｄｅｔ（Ｅ）＝０ならば、ステップ１に戻る。そうでなければ、Ｅの逆行列−１を計算し、ｉ＝１，２，…，ｄについて、Ｘｉ’で（ΠｊＹｊ’（Ｅ−１）ｉ，ｊ，Ｘｉ’）∈Ｒとなるものを計算する。（Ｘ１’，Ｘ２’，…，Ｘｄ’）を出力する。
【００２０】
Ε＝｛ｅ｜Ｐｒ［（Ｐ＊，Ｖｅ）∈Ａｃｃ］＞ｐ（Ｙ１，Ｙ２，…，Ｙｄ）／２｝とおく。すると、数え上げの議論によって、Ｐｒ［ｅ←Ｒ｛０，１，…，ｐ−１｝，（Ｐ＊，Ｖｅ）∈Ａｃｃ：ｅ∈Ｅ］＞１／２であることがわかる。したがって、ステップ２において、ｅをＥから選択する確率は、１／２よりも大きい。もし、ｅ∈Ｅならば、Ｋｐ＊は、Ｘで、ｇＸ＝ΠｊＹｊＨ（ｃ，ｊ）なるものを、４ｋｃ／（ｐ（Ｙ１，Ｙ２，…，Ｙｄ）−ε（ｋ））時間以内に、少なくとも１／２の確率で出力する。
【００２１】
有限体Ｆｐに値を持つｄ次正方行列は、ｐ＾（ｄ２）個存在する。そのうち、非退化行列は、ｐｄ（ｄ−１）／２Πｉ＝１ｄ（ｐｉ−１）個である。したがって、ステップ６において、ｄｅｔ（Ｅ）≠０となる確率は、ｆ（ｐ，ｄ）＝（１−ｐ−１）（１−ｐ−２）…（１−ｐ−ｄ）である。この確率は無視できなくて、ある定数ｃ２（Ｃ２とも表記する。）が存在して、１／ｆ（ｐ，ｄ）＜ｋｃ２となることがわかる。ΠｊＹｊ’（Ｅ−１）ｉ，ｊ＝Ｙｉであることは明らかなので、よって、上記アルゴリズムがπｄの知識を出力するまでの時間の期待値は、４ｄ（４ｋｃ＋ｃ２＋１）／（ｐ（Ｙ１，Ｙ２，…，Ｙｄ）−ε’（ｋ））以下である。ここで、ε’は無視できる関数である（証明終わり）。
【００２２】
以下、ｐ−加法的ＮＰ関係Ｒについての対話証明方法として、ＧｕｉｌｌｏｕとＱｕｉｓｑｕａｔｅｒによる対話証明方法と、ＢｏｎｅｈとＦｒａｎｋｌｉｎによる対話証明方法をそれぞれ例に挙げて、本発明による対話証明バッチ実行方法、システム、証明者装置、検証者装置、それらのプログラムについて説明をする。
なお、以下の実施形態は、あるひとつの乱数ｅを用いて、ｉごとの乱数ｅｉをｅｉ＝ｅｉ−１と定めた場合の実施形態である。
【００２３】
［第一実施形態］
第一実施形態による対話証明バッチ実行システム５００の機能構成を図１に、その処理フローを図５に例示する。
対話証明バッチ実行システム５００は、認証情報発行者装置１、証明者装置２、検証者装置３を有する。認証情報発行者装置１は、対話証明を行うのに必要な識別子Ｙや認証情報Ｘ等のデータを生成して予め配布しておく。証明者装置２、検証者装置３は、認証情報Ｘを用いて識別子Ｙの対話証明を行う。
【００２４】
図２に、認証情報発行者装置１の機能構成を示す。認証情報発行者装置１は、例えば、素数生成部１１、識別子生成部１２、共通パラメータ生成部１３、認証情報生成部１４、通信部１５を有する。
証明者装置２（図１参照）は、例えば、乱数発生部２１、第一送信情報生成部２２、通信部２３、第二送信情報生成部２４、記憶部２５を有する。記憶部２５は、証明者装置２の各部とデータの読み書きが可能なように接続されている。
検証者装置３は、例えば、乱数発生部３１、通信部３２、検証部３３、記憶部３４を有する。
【００２５】
＜ステップＳ０＞
認証情報発行者装置１（図２参照）の素数生成部１１は、素因数分解が困難な自然数Ｎを生成する。認証情報発行者装置は、自然数Ｎの素因数分解に関する情報を知っているが秘密に保っている。自然数Ｎは、識別子生成部１２と認証情報生成部１４と通信部１５に出力される。
【００２６】
識別子生成部１２は、自然数Ｎを用いて、識別子Ｙｉ∈（Ｚ／ＮＺ）＊を、ｉ＝１，…，ｄについてそれぞれ生成する。各識別子Ｙｉには、例えば、証明者の住所、氏名、電話番号、性別、年齢等が対応付けられている。識別子Ｙｉは、認証情報生成部１４と通信部１５に出力される。
【００２７】
共通パラメータ生成部１３は、公開される共通パラメータνを生成する。共通パラメータνは素数である。共通パラメータνは、小さい値で、ハミングウェイトが小さいことが望ましい。共通パラメータνは、認証情報生成部１４と通信部１５に出力される。
認証情報生成部１４は、自然数Ｎの素因数分解に関する情報を用いて、Ｙｉ＝Ｘｉ−ν  ｍｏｄ  Ｎとなる、認証情報Ｘｉを計算する。Ｘｉは、識別子Ｙｉに対応した認証情報である。
【００２８】
通信部１５は、識別子Ｙｉと認証情報Ｘｉと共通パラメータνと自然数Ｎを証明者装置２に、識別子Ｙｉと共通パラメータνと自然数Ｎを検証者装置３に予めそれぞれ送信しておく。識別子Ｙｉと認証情報Ｘｉと共通パラメータνと自然数Ｎは、証明者装置２の記憶部２５に格納される。識別子Ｙｉと共通パラメータνと自然数Ｎは、検証者装置３の記憶部に予めそれぞれ送信しておく
＜ステップＳ１＞
証明者装置２（図３参照）の乱数発生部２１は、乱数ｒ∈｛１，…，Ｎ−１｝を生成して、第一送信情報生成部２２に出力する。
第一送信情報生成部２２は、乱数ｒと記憶部２５から読み出した共通パラメータνを用いて、Ｔ＝ｒν  ｍｏｄ  Ｎを計算して、第一送信情報Ｔを生成して、通信部２３に出力する。
通信部２３は、第一送信情報Ｔを、検証者装置３に送信する。第一送信情報Ｔは、検証者装置３の記憶部３４に格納される。
【００２９】
＜ステップＳ２＞
検証者装置３の乱数発生部３１は、乱数ｃ∈｛０，…，ν−１｝と、乱数ｅ∈｛０，…，ν−１｝を生成して、通信部３２に送信する。
通信部３２は、乱数ｃと乱数ｅを、証明者装置２に送信する。乱数ｃと乱数ｅは、証明者装置２の記憶部２５に格納される。
【００３０】
＜ステップＳ３＞
第二送信情報生成部２４は、乱数発生部２１が生成した乱数ｒと、記憶部２５から読み出した認証情報Ｘｉと乱数ｃと乱数ｅと共通パラメータνとを用いて、
Ｄ＝ｒ（ΠｉＸｉ＾（ｃｅｉ−１  ｍｏｄ  ν））  ｍｏｄ  Ｎ  …（６）
を計算して、第二送信情報Ｄを生成して、通信部２３に出力する。
通信部２３は、第二送信情報Ｄを、検証者装置３に送信する。
【００３１】
ここで、上記式（６）は、背景技術における式（１）の認証情報Ｘに、代表認証情報ΠｉＸｉ＾（ｅｉ−１）を代入したものに等しい。すなわち、式（１）の認証情報Ｘに、代表認証情報ΠｉＸｉ＾（ｅｉ−１）を代入すると、
Ｄ＝ｒＸｃ  ｍｏｄ  Ｎ  …（１）
＝ｒ（ΠｉＸｉ＾（ｅｉ−１））ｃ  ｍｏｄ  Ｎ
＝ｒ（ΠｉＸｉ＾（ｃｅｉ−１））  ｍｏｄ  Ｎ
＝ｒ（ΠｉＸｉ＾（ｃｅｉ−１  ｍｏｄ  ν））  ｍｏｄ  Ｎ  …（６）
となる。
【００３２】
＜ステップＳ４＞
検証者装置３の検証部３３は、通信部３２から受信した第二送信情報Ｄと、記憶部３４から読み出した第一送信情報Ｔと共通パラメータνと識別子Ｙｉと乱数ｃと乱数ｅを用いて、
Ｔ＝Ｄν（ΠｉＹｉ＾（ｃｅｉ−１  ｍｏｄ  ν））  ｍｏｄ  Ｎ  …（７）
が成立するかどうかを検証する。検証に成功すれば、検証者装置３はすべての識別子Ｙｉについての認証を受け入れる。
【００３３】
ここで、上記式（７）は、背景技術における式（２）の識別子Ｙに、代表識別子ΠｉＹｉ＾（ｅｉ−１）を代入したものに等しい。すなわち、式（２）の識別子Ｙに、代表識別子ΠｉＹｉ＾（ｅｉ−１）を代入すると、
Ｔ＝ＤνＹｃ  ｍｏｄ  Ｎ  …（２）
＝Ｄν（ΠｉＹｉ＾（ｅｉ−１））ｃ  ｍｏｄ  Ｎ  
＝Ｄν（ΠｉＹｉ＾（ｃｅｉ−１））  ｍｏｄ  Ｎ
＝Ｄν（ΠｉＹｉ＾（ｃｅｉ−１  ｍｏｄ  ν））  ｍｏｄ  Ｎ  …（７）
となる。
【００３４】
［第二実施形態］
図４に第二実施形態による対話証明バッチ実行システム５０１の機能構成を、図６にその処理フローを示す。
対話証明バッチ実行システム５０１は、例えば、認証情報発行者装置４、証明者装置５、検証者装置６を有する。認証情報発行者装置４は、対話証明を行うのに必要な識別子Ｙｉや認証情報Ｘｉ等のデータを生成して予め配布しておく。証明者装置５、検証者装置６は、認証情報Ｘｉを用いて識別子Ｙｉの対話証明を行う。
【００３５】
図３に、認証情報発行者装置４の機能構成を例示する。認証情報発行者装置４は、自然数選択部４１、第一共通パラメータ生成部４２、第二共通パラメータ生成部４３、識別子生成部４４、認証情報生成部４５、通信部４６を有する。
証明者装置５は、例えば、乱数発生部５１、第一送信情報生成部５２、通信部５３、第二送信情報生成部５４、記憶部５５を有する。記憶部５５と、証明者装置５の各部とは、データの読み書きができるように接続されている。
検証者装置６は、例えば、乱数発生部６１、通信部６２、検証部６３、記憶部６４を有する。記憶部６４と、検証者装置６の各部は、データの読み書きができるように接続されている。
【００３６】
＜ステップＳ１０＞
以下、Ｅ［ｐ］とＦを位数ｐの有限可換群とし、ｅｐ：Ｅ［ｐ］×Ｅ［ｐ］→Ｆを双線形写像とする。例えば、Ｅ［ｐ］をある捩れ点の集合、Ｆを有限体の単元がなす群（部分群でも良い。）、ｅｐをＷｅｉｌペアリングとすることができる。
認証情報発行者装置４の自然数選択部４１は、自然数ｕを秘密に選択して、認証情報生成部４５と、第二共通パラメータ生成部４３に出力する。
【００３７】
第一共通パラメータ生成部４２は、第一共通パラメータＧ∈Ｅ［ｐ］を選択して、第二共通パラメータ生成部４３と通信部４６に出力する。
第二共通パラメータ生成部４３は、自然数選択部４１が選択したｕと、第一共通パラメータ生成部４２が生成した第一共通パラメータＧを用いて、第二共通パラメータＨ＝ｕＧを計算して、通信部４６に出力する。
【００３８】
識別子生成部４４は、ｉ（ｉ＝１，…，ｄ）ごとに、識別子Ｙｉ∈Ｅ［ｐ］を選択して、認証情報生成部４５と通信部４６に出力する。各識別子Ｙｉには、例えば、証明者の住所、氏名、電話番号、性別、年齢等が対応付けられている。
認証情報生成部４５は、自然数ｕと識別子Ｙｉを用いて、認証情報Ｘｉ＝ｕＹｉを生成して、通信部４６に出力する。Ｘｉは、識別子Ｙｉに対応する認証情報である。
【００３９】
通信部４６は、識別子Ｙｉと認証情報Ｘｉと第一共通パラメータＧと第二共通パラメータＨと自然数ｐを証明者装置５に、識別子Ｙｉと第一共通パラメータＧと第二共通パラメータＨと自然数ｐを検証者装置６に、それぞれ予め送信しておく。識別子Ｙｉと認証情報Ｘｉと第一共通パラメータＧと第二共通パラメータＨと自然数ｐは証明者装置５の記憶部５５に格納され、識別子Ｙｉと第一共通パラメータＧと第二共通パラメータＨと自然数ｐは証明者装置５の記憶部６４に格納される。
【００４０】
＜ステップＳ１１＞
検証者装置６（図４参照）の乱数発生部６１は、乱数ｅ∈｛０，…，ｐ−１｝を選択して、通信部６２と検証部６３に出力する。
通信部６２は、乱数ｅを証明者装置５に出力する。乱数ｅは、証明者装置の記憶部５５に格納される。
【００４１】
＜ステップＳ１２＞
証明者装置５の乱数発生部５１は、乱数ｋ∈｛０，…，ｐ−１｝を選択して、第一送信情報生成部５２と第二送信情報生成部５４に出力する。
第一送信情報生成部５２は、乱数ｋと、記憶部５５から読み出した識別子Ｙｉと共通パラメータＧとを用いて、
ｒ＝Πｉ（ｅｐ（Ｙｉ，Ｇ）＾（ｋｅｉ−１  ｍｏｄ  ｐ））  …（８）
を計算して、第一送信情報ｒを通信部５３に出力する。
【００４２】
ここで、上記式（８）は、背景技術による式（３）の識別子Ｙに、代表識別子Σｉｅｉ−１Ｙｉを代入したものである。すなわち、上記式（３）の識別子Ｙに、代表識別子Σｉｅｉ−１Ｙｉを代入すると、ｅｐは双線形写像であるため、
ｒ＝ｅｐ（Ｙ，Ｇ）ｋ  …（３）
＝ｅｐ（Σｉｅｉ−１Ｙｉ，Ｇ）ｋ 
＝Πｉ（ｅｐ（Ｙｉ，Ｇ）＾（ｋｅｉ−１））  
＝Πｉ（ｅｐ（Ｙｉ，Ｇ）＾（ｋｅｉ−１  ｍｏｄ  ｐ））  …（８）
となる。
通信部５３は、第一送信情報ｒを、検証者装置６に送信する。第一送信情報ｒは、検証者装置６の記憶部６４に格納される。
【００４３】
＜ステップＳ１３＞
検証者装置の乱数発生部６１は、乱数ｃ∈｛０，…，ｐ−１｝を選択して、通信部６２と検証部６３に出力する。
通信部６２は、乱数ｃを証明者装置５に出力する。乱数ｃは、証明者装置５の記憶部５５に格納される。
【００４４】
＜ステップＳ１４＞
証明者装置５の第二送信情報生成部５４は、乱数発生部５１が生成した乱数ｋと、記憶部５５から読み出した乱数ｅと乱数ｃと認証情報Ｘｉと識別子Ｙｉとを用いて、
Ｓ＝Σｉ（ｅｉ−１  ｍｏｄ  ｐ）（ｃＸｉ+ｋＹｉ）  …（９）
を計算して、第二送信情報Ｓを生成して通信部５３に出力する。
【００４５】
ここで、上記式（９）は、背景技術における式（４）の認証情報Ｘと識別子Ｙに、代表認証情報Σｉｅｉ−１Ｘｉと代表識別子Σｉｅｉ−１Ｙｉを代入したものである。すなわち、上記式（４）の認証情報Ｘと識別子Ｙに、代表認証情報Σｉｅｉ−１Ｘｉと代表識別子Σｉｅｉ−１Ｙｉを代入すると、
Ｓ＝ｃＸ＋ｋＹ  …（４）
＝ｃΣｉｅｉ−１Ｘｉ＋ｋΣｉｅｉ−１Ｙｉ 
＝Σｉｅｉ−１（ｃＸｉ+ｋＹｉ）  
＝Σｉ（ｅｉ−１  ｍｏｄ  ｐ）（ｃＸｉ+ｋＹｉ）  …（９）
となる。
通信部５３は、第二送信情報Ｓを検証者装置６に送信する。第二送信情報Ｓは、検証者装置６の記憶部６４に格納される。
【００４６】
＜ステップＳ１５＞
検証者装置６の検証部６３は、乱数発生部６１が選択した乱数ｅと乱数ｃと、記憶部６４から読み出した第一送信情報ｒと第二送信情報Ｓと第一共通パラメータＧと識別子Ｙｉと第二共通パラメータＨとを用いて、
ｒ＝ｅｐ（Ｓ，Ｇ）ｅｐ（Σｉ（ｅｉ−１  ｍｏｄ  ｐ）Ｙｉ，Ｈ）−ｃ  …（１０）
が成立するかどうかを検証する。検証に成功すれば、検証者装置６はすべての識別子Ｙｉについての認証を受け入れる。
ここで、上記式（１０）は、背景技術の式（５）の識別子Ｙとして、代表識別情報Σｉｅｉ−１Ｙｉを代入したものである。
【００４７】
［変形例等］
上記実施形態においては、計算量を削減するために、式（６）、式（７）において、ｅｉ−１について、共通パラメータνを法として計算している。また、式（８）、式（９）、式（１０）において、ｅｉ−１について、ｐを法として計算している。しかし、合同式の計算を行わなくてもよい。すなわち、式（６）〜式（１０）に代えてそれぞれ式（６’）、式（７’）を計算してもよい。
Ｄ＝ｒ（ΠｉＸｉ＾（ｃｅｉ−１）  ｍｏｄ  Ｎ  …（６’）
Ｔ＝Ｄν（ΠｉＹｉ＾（ｃｅｉ−１）  ｍｏｄ  Ｎ  …（７’）
ｒ＝Πｉ（ｅｐ（Ｙｉ，Ｇ）＾（ｋｅｉ−１））  …（８’）
Ｓ＝Σｉｅｉ−１（ｃＸｉ+ｋＹｉ）  …（９’）
ｒ＝ｅｐ（Ｓ，Ｇ）ｅｐ（Σｉｅｉ−１Ｙｉ，Ｈ）−ｃ  …（１０’）
【００４８】
検証者装置３、６の乱数発生部３１、６１が乱数ｅを生成する代わりに、乱数ｅを検証者装置３、６と証明者装置２、４で共有する時点で、検証者装置３、６と証明者装置２、４との間で共有されている情報のうち証明者装置２、４にとって事前予測が困難な情報からハッシュ関数によって生成してもよい。例えば、検証者装置３の乱数発生部３１と、証明者装置２の乱数発生部２６とが、｛０，…，ν−１｝の値をランダムに出力する時刻のハッシュ関数Ｈａｓｈ１（ｔ）を用いて、同じ時刻ｔに基づく乱数ｅ＝Ｈａｓｈ１（ｔ）を生成してもよい。また、検証者装置３の乱数発生部３１と、証明者装置２の乱数発生部２６とが、｛０，…，ν−１｝の値をランダムに出力する乱数ｃのハッシュ関数Ｈａｓｈ２（ｃ）を用いて、ｅ＝Ｈａｓｈ２（ｃ）を計算することにより、乱数ｅを生成してもよい。検証者装置６、証明者装置４についても同様である。
【００４９】
上記実施形態においては、ある乱数ｅをひとつだけ生成して、その乱数ｅからｉごとの乱数ｅｉとして、ｅｉ−１を用いている。しかし、ｅｉ−１の代わりに、任意のｉごとの乱数ｅｉを用いてよい。例えば、検証者装置３の乱数発生部３１が、ｉごとの乱数ｅｉ∈｛０，…，ν−１｝を、すべてのｉについてそれぞれ生成する。そして、証明者装置２の各部と検証者装置３の各部とが、乱数ｅｉ−１に代えて、このｉごとの乱数ｅｉを用いて、上記処理を行ってもよい。検証者装置６、証明者装置４についても同様である。
【００５０】
また、例えば、｛０，…，ν−１｝の値をランダムに出力するハッシュ関数Ｈａｓｈ３（・）を用いて、上記何れかの方法によって生成した乱数と、ｅｉ＝Ｈａｓｈ３（ｅ‖ｉ）とによって、ｉごとの乱数ｅｉを求め、証明者装置２の各部と検証者装置３の各部とが、乱数ｅｉ−１に代えて、このｉごとの乱数ｅｉを用いて、上記処理を行ってもよい。証明者装置４と検証者装置においては、｛０，…，ｐ−１｝の値をランダムに出力するハッシュ関数Ｈａｓｈ４（・）を用いて、同様のことを行う。
【００５１】
上記第一実施形態においては、第一送信情報Ｔは、検証者装置が生成する乱数ｅを必要としないため、通信の効率性の観点から、ステップＳ２（図５参照）において、検証者装置３が乱数ｅと乱数ｃの両方を生成して証明者装置２に送信している。しかし、例えば、図５に破線で示すように、ステップＳ１の前に、ステップＳ５を設けて、検証者装置３が乱数ｅを生成して証明者装置２に送信してもよい。この場合には、ステップＳ２の代わりに、図５に破線で示すステップＳ６において、検証者装置３は乱数ｃのみを生成して証明者装置２に送信する。
【００５２】
上記対話証明バッチ実行システム５００、５０１の証明者装置２、５、検証者装置３、６の処理機能をコンピュータによって実現することができる。この場合、証明者装置２、５、検証者装置３、６の処理の内容はプログラムによって記述される。そして、このプログラムを、コンピュータで実行することにより、証明者装置２、５、検証者装置３、６の処理機能がコンピュータ上で実現される。
【００５３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ＤＶＤ−ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｒｅｃｏｒｄａｂｌｅ）／ＲＷ（ＲｅＷｒｉｔａｂｌｅ）等を、光磁気記録媒体として、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｃ）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Ｅｌｅｃｔｒｏｎｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ａｎｄ  Ｐｒｏｇｒａｍｍａｂｌｅ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）等を用いることができる。
【００５４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、証明者装置２、５、検証者装置３、６を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００５７】
以上の各実施形態の他、本発明である対話証明バッチ実行方法、そのシステム、証明者装置、検証者装置、それらのプログラムは上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【図面の簡単な説明】
【００５８】
【図１】対話証明バッチ実行システム５００の機能構成を例示する図。
【図２】認証情報発行者装置１の機能構成を例示する図。
【図３】認証情報発行者装置４の機能構成を例示する図。
【図４】対話証明バッチ実行システム５０１の機能構成を例示する図。
【図５】対話証明バッチ実行システム５００の処理フローを例示する図。
【図６】対話証明バッチ実行システム５００の処理フローを例示する図。
【符号の説明】
【００５９】
１     認証情報発行者装置              ３３   検証部
２     証明者装置                      ３４   記憶部
３     検証者装置                      ４１   自然数選択部
４     認証情報発行者装置              ４２   第一共通パラメータ生成部
５     証明者装置                      ４３   第二共通パラメータ生成部    
６     検証者装置                      ４４   識別子生成部
１１   素数生成部                      ４５   認証情報生成部
１２   識別子生成部                    ４６   通信部
１３   共通パラメータ生成部            ５１   乱数発生部
１４   認証情報生成部                  ５２   第一送信情報生成部
１５   通信部                          ５３   通信部
２１   乱数発生部                      ５４   第二送信情報生成部
２２   第一送信情報生成部              ５５   記憶部
２３   通信部                          ６１   乱数発生部
２４   第二送信情報生成部              ６２   通信部
２５   記憶部                          ６３   検証部
２６   乱数発生部                      ６４   記憶部              
３１   乱数発生部                      ５００ 対話証明バッチ実行システム
３２   通信部                          ５０１ 対話証明バッチ実行システム
【図１】
2008172686.tif 000003
【図２】
2008172686.tif 000004
【図３】
2008172686.tif 000005
【図４】
2008172686.tif 000006
【図５】
2008172686.tif 000007
【図６】
2008172686.tif 000008