(57)【要約】【課題】  簡易な構成により、ｃ−限定並行性を満たすセッション制御を実現する。【解決手段】  セッション管理装置Ｍは、セッションの累積並行度の上限値と、現在実行中のセッション毎の累積並行度とを各記憶部１，２に記憶し、開始要求メッセージを受信した場合に、この上限値と各セッション毎の累積並行度とに基づいて、新たなセッションの開始を許可する簡易な構成である。従って、非常に複雑な制御や大きなリソースを必要とせず、簡易な構成により、ｃ−限定並行性を満たすセッション制御を実現できる。【選択図】  図１
2006041836.tif 000002
【特許請求の範囲】
【請求項１】
証明者装置の持つ秘密情報について該証明者装置と複数の検証者装置との間で複数並行して行われるゼロ知識対話証明プロトコルのセッションを管理するゼロ知識対話証明プロトコル管理装置であって、
１つのセッションの開始から終了までの間に自セッションを含めて並行実行されるセッションの数が累積されてなる累積並行度に関し、前記累積並行度の上限値を記憶する上限値記憶手段と、
現在実行中のセッションを個別に示すセッションＩＤ毎に、当該セッションの累積並行度を記憶する累積並行度記憶手段と、
前記ゼロ知識対話証明プロトコルの開始を要求する開始要求メッセージを前記証明者装置又はいずれかの検証者装置から受信する受信手段と、
前記開始要求メッセージを受信した場合に、前記上限値記憶手段内の上限値及び前記累積並行度記憶手段内のセッションＩＤ毎の累積並行度に基づいて前記開始を許可するか否かを判定する判定手段と
を備えたことを特徴とするゼロ知識対話証明プロトコル管理装置。
【請求項２】
請求項１に記載のゼロ知識対話証明プロトコル管理装置において、
前記判定手段は、前記累積並行度記憶手段内の全ての累積並行度が前記上限値記憶手段内の上限値を下回るとき、前記開始を許可する旨を判定することを特徴とするゼロ知識対話証明プロトコル管理装置。
【請求項３】
請求項２に記載のゼロ知識対話証明プロトコル管理装置において、
前記判定により開始が許可されたとき、前記累積並行度記憶手段内の全ての累積並行度を１増加させる手段と、
前記判定により開始が許可されたとき、前記累積並行度記憶手段内のセッションＩＤの個数に１を加えて許可セッションの累積並行度を得る手段と、
得られた累積並行度を許可セッションのセッションＩＤに関連付けて前記累積並行度記憶手段に書込む手段と
を更に備えたことを特徴とするゼロ知識対話証明プロトコル管理装置。
【請求項４】
請求項１に記載のゼロ知識対話証明プロトコル管理装置において、
前記判定手段は、前記累積並行度記憶手段内のいずれかの累積並行度が前記上限値記憶手段内の上限値に達しているとき、前記開始を許可しない旨を判定することを特徴とするゼロ知識対話証明プロトコル管理装置。
【請求項５】
請求項１乃至請求項４のいずれか１項に記載のゼロ知識対話証明プロトコル管理装置において、
前記ゼロ知識対話証明プロトコルの終了を通知する終了通知メッセージを前記証明者装置又は前記検証者装置から受信する手段と、
前記終了通知メッセージを受信した場合に、前記累積並行度記憶手段内の該当するセッションＩＤ及び累積並行度を削除する手段と
を更に備えたことを特徴とするゼロ知識対話証明プロトコル管理装置。
【請求項６】
証明者装置の持つ秘密情報について該証明者装置と複数の検証者装置との間で複数並行して行われるゼロ知識対話証明プロトコルのセッションを管理するゼロ知識対話証明プロトコル管理装置によるゼロ知識対話証明プロトコル管理方法であって、
１つのセッションの開始から終了までの間に自セッションを含めて並行実行されるセッションの数が累積されてなる累積並行度に関し、前記累積並行度の上限値を記憶する上限値記憶工程と、
現在実行中のセッションを個別に示すセッションＩＤ毎に、当該セッションの累積並行度を記憶する累積並行度記憶工程と、
前記ゼロ知識対話証明プロトコルの開始を要求する開始要求メッセージを前記証明者装置又はいずれかの検証者装置から受信する工程と、
前記開始要求メッセージを受信した場合に、前記上限値記憶工程により記憶された上限値及び前記累積並行度記憶工程により記憶されたセッションＩＤ毎の累積並行度に基づいて前記開始を許可するか否かを判定する判定工程と
を備えたことを特徴とするゼロ知識対話証明プロトコル管理方法。
【請求項７】
証明者装置の持つ秘密情報について該証明者装置と複数の検証者装置との間で複数並行して行われるゼロ知識対話証明プロトコルのセッションを管理するゼロ知識対話証明プロトコル管理装置に用いられるプログラムであって、
前記ゼロ知識対話証明プロトコル管理装置のコンピュータに、
１つのセッションの開始から終了までの間に自セッションを含めて並行実行されるセッションの数が累積されてなる累積並行度に関し、前記累積並行度の上限値をメモリに記憶する手段、
現在実行中のセッションを個別に示すセッションＩＤ毎に、当該セッションの累積並行度をメモリに記憶する手段、
前記ゼロ知識対話証明プロトコルの開始を要求する開始要求メッセージを前記証明者装置又はいずれかの検証者装置から受信する手段、
前記開始要求メッセージを受信した場合に、前記メモリ内の上限値及び前記メモリ内の各セッション毎の累積並行度に基づいて前記開始を許可するか否かを判定する判定手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ゼロ知識対話証明プロトコルを管理するゼロ知識対話証明プロトコル管理装置、方法及びプログラムに関する。
【背景技術】
【０００２】
秘密情報ｗを知っていることを秘密情報ｗを明かさずに証明する技術として、ゼロ知識対話証明(Zero-Knowledge Interactive Proof)プロトコルが知られている。
【０００３】
ゼロ知識対話証明では、証明者Ｐと検証者Ｖとの間で一定のやり取り（対話）を行って秘密情報ｗを知っていることを証明・検査するラウンドを、複数ラウンド繰り返す。これは、１回のラウンドでは、証明者Ｐが秘密情報ｗを知らなくても検査を合格させる試み（なりすまし）がある確率で成功することによる。すなわち、ゼロ知識対話証明では、十分証明されたとみなされる回数以上のラウンドを実施することにより、なりすましの成功を阻止している。
【０００４】
ところで、証明者Ｐが同一の秘密情報ｗに関し、ゼロ知識対話証明プロトコルを複数の検証者Ｖ１〜Ｖｎと並行に実行する場合がある。このように、プロトコルが並行して複数個実行されるゼロ知識対話証明を並行ゼロ知識対話証明(concurrent zero-knowledge interactive proof)という。なお、（同一の秘密情報についての）複数プロトコルの並行実行は並行合成とも呼ばれる。個々の実行はセッション(session)と呼ばれる。
【０００５】
このような並行ゼロ知識対話証明は、単独の検証者Ｖとの間の実行を前提とするラウンド数だけではゼロ知識性が破れる（すなわち、秘密情報が漏れる）ことがあることが知られている。
【０００６】
そこで、並行ゼロ知識対話証明の安全性確保の観点から、セッションから見た並行度を限定する方式が考えられている。例えば、あるセッションｓの開始から終了までの間に、検証者Ｖがプリアンブル（preamble：証明完了前の一定のやり取り）においてコミットメントの開示を行うセッションｓ’の個数を、セッションｓから見た並行度ということにする。
【０００７】
全てのセッションに対して、そのセッションから見た並行度がｃ以下であるとき、このプロトコルは、ｃ−限定並行(c-bounded concurrent)であるという。このようなｃ−限定並行のゼロ知識対話証明プロトコルは安全性が証明されている（例えば非特許文献１〜３参照）。
【０００８】
かかるｃ−限定並行ゼロ知識対話証明プロトコルの特長は、プロトコルのラウンド数の上限が決定されており、かつ、非限定並行の場合と比較してラウンド数を抑制可能なため、プロトコルの処理コスト、特に、通信回数を削減可能な点にある。
【非特許文献１】村谷博文.ゼロ知識証明の並行合成に関する考察. 2004年暗号と情報セキュリティシンポジウム, 3C5-5, pp. 1309 - 1314, 2004.
【非特許文献２】Yehuda Lindell. Bounded-Concurrent Secure Two-Party Computation Without Setup Assumptions. STOC 2003, pp. 683 - 692, 2003.
【非特許文献３】Yehuda Lindell. Protocols for Bounded-Concurrent Secure Two-Party Computation Without Setup Assumptions. Cryptology ePrint Archive Report 2003/100 http://eprint.iacr.org .
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、以上のようなｃ−限定並行ゼロ知識対話証明は、プロトコルのｃ−限定並行性を保証するためのセッション制御の方法が知られていない。ｃ−限定並行の定義が、同時に継続されているセッション数というような素朴な概念よりも制約が厳しいため、実現の際には、非常に複雑な制御や大きなリソースを必要とすると考えられる。
【００１０】
本発明は上記実情を考慮してなされたもので、簡易な構成により、ｃ−限定並行性を満たすセッション制御を実現し得るゼロ知識対話証明プロトコル管理装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
第１の発明は、証明者装置の持つ秘密情報について該証明者装置と複数の検証者装置との間で複数並行して行われるゼロ知識対話証明プロトコルのセッションを管理するゼロ知識対話証明プロトコル管理装置であって、１つのセッションの開始から終了までの間に自セッションを含めて並行実行されるセッションの数が累積されてなる累積並行度に関し、前記累積並行度の上限値を記憶する上限値記憶手段と、現在実行中のセッションを個別に示すセッションＩＤ毎に、当該セッションの累積並行度を記憶する累積並行度記憶手段と、前記ゼロ知識対話証明プロトコルの開始を要求する開始要求メッセージを受信する手段と、前記開始要求メッセージを受信した場合に、前記上限値記憶手段内の上限値及び前記累積並行度記憶手段内のセッションＩＤ毎の累積並行度に基づいて前記開始を許可するか否かを判定する判定手段とを備えたことを特徴とするゼロ知識対話証明プロトコル管理装置である。
【００１２】
（作用）
第１の発明は、セッションの累積並行度の上限値と、現在実行中のセッション毎の累積並行度とを記憶手段に記憶し、開始要求メッセージを受信した場合に、この上限値と各セッション毎の累積並行度とに基づいて、新たなセッションの開始を許可する構成である。
【００１３】
ここで、必要なリソースは、累積並行度の上限値と、現在実行中のセッション毎の累積並行度とを記憶する記憶手段が主であり、これは比較的小さいリソースで実現可能である。また、必要な制御は、上限値と各セッション毎の累積並行度とを比較し、累積並行度が上限値を超えない場合に開始を許可する内容であり、しかも、セッションの累積並行度はセッションの開始要求と終了のタイミングにのみ管理すれば良く、全てのメッセージ授受のたびに管理する必要はない。これは非常に複雑とは言えない。
【００１４】
このように第１の発明は、従来の考えとは異なり、非常に複雑な制御や大きなリソースを必要としない。よって、第１の発明は、簡易な構成により、ｃ−限定並行性を満たすセッション制御を実現できる。
【発明の効果】
【００１５】
以上説明したように本発明によれば、簡易な構成により、ｃ−限定並行性を満たすセッション制御を実現できる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の一実施形態について図面を参照しながら説明するが、その前に実施形態で用いられるｃ−限定並行ゼロ知識証明について説明する。
【００１７】
（定義１：ｃ−限定並行性［非特許文献２，３］）
ｃ−限定並行性（C-bounded concurrency）とは、敵のスケジュールが以下を満たすことをいう：各セッションの実行に対して、その開始から終了までの間に、自らを含めて高々ｃ個の異なるセッションがメッセージを送信できる。
【００１８】
（十分なラウンド数）
（定理１［非特許文献３参照］）
セッション数ｎに対する任意の関数κ（ｎ）＝ω（ｎ０）に対して、ＲＫＺＫ（ｃκ（ｎ））は、∀Ｌ∈ＮＰに対するｃ−限定並行ゼロ知識証明系である。そのシミュレータ（チューリング機械）は、厳密に多項式時間で実行される。
【００１９】
ここで、ＲＫＺＫ（ｃκ（ｎ））は、ラウンド数ｃκ（ｎ）のリチャードソン−キリアン（Richardson - Kilian）・プロトコルを意味している（R. Richardson and Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. EURO-CRIPT’99, 415-431, 1999.）。ラウンド数はプロトコルの長さに相当し、例えばプレアンブルのメッセージ数が適用可能となっている。
【００２０】
例えばラウンド数ｍのＲＫＺＫ（ｍ）は、検証者Ｖ及び証明者Ｐに関し、以下のように定義可能である。
【００２１】
１．Ｖ→Ｐ：ｖ１，ｖ２，…，ｖｍをコミットする。  
２．Ｐ→Ｖ：ｐ１をコミットする。  
…  
３．Ｖ→Ｐ：ｖｉを開示する。  
４．Ｐ→Ｖ：ｐi+1をコミットする。  
…  
５．Ｖ→Ｐ：ｖｍを開示する。
【００２２】
６．Ｐ→Ｖ：（∃ｉ  ｖｉ＝ｐｉ）∨Ｔのゼロ知識証明を行なう。  
Ｔは証明される文。ステップ１〜５をプレアンプル、ステップ６を本体という。
【００２３】
一方、∀Ｌ∈ＮＰは、非決定性多項式時間チューリング機械により認識できる言語のクラスＮＰに属する任意の言語Ｌを意味している。
【００２４】
（ラウンド数の下界）
ｃ−限定並行ゼロ知識証明のラウンド数ｍの下界は知られていない。どのようなプロトコルによっても下界ｍ＞ｃが課されてしまう確率性多項式限定機能の存在が示されたが（非特許文献２参照）、ゼロ知識証明はその例に該当していない。
【００２５】
（十分なラウンド数の改良）
定理１では、ラウンド数ｍが並行性ｃに線形なため、ｃが大きくなるにつれ、ｍも速く大きくなり、ｃ−限定性導入のメリットが小さい。以下では改良を行なう。
【００２６】
（定理２：ｃ−限定並行ゼロ知識証明の十分なラウンド数）
ｎ＝ｋＯ(1)とする。ｍ−２log２(ｃｍ)＝ω(log２ｋ)ならば、ＲＫＺＫ（ｍ）は∀Ｌ∈ＮＰに対するｃ−限定並行ゼロ知識証明系である。そのシミュレータは厳密に多項式時間で実行される。
【００２７】
なお、ｋはセキュリティパラメータであり、ラウンド数ｍの各ラウンドにおけるコミット値ｖ１〜ｖｍの大きさである（｜ｖ1｜＝・・・＝｜ｖm｜）。
【００２８】
定理２の証明は、プラブハカラン−サハイ（Prabhakaran-Sahai）の証明（M. Prabhakaran and A. Sahai. On the Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity. ECCC 2002, 2002.）に対し、修正を加えて得られる。
【００２９】
セッション数ｎは、セキュリティパラメータｋの多項式とする。ゼロ知識証明を破る可能性のある敵Ｖ*は、証明者Ｐとの間で複数セッションを並行実行する任意の確率性多項式時間チューリング機械とする。シミュレータＳは、Ｖ*をオラクルとする確率性（平均／厳密）多項式時間チューリング機械とする。
【００３０】
シミュレータＳは、敵Ｖ*を巻き戻すことにより、プレアンブルの証拠ｖiを得て、ｐｉ＝ｖｉをコミットする。多項式時間内に、全てのセッションに対して、少なくとも１つのｉ∈｛１，２，…，ｍ｝に対してこれを行なうことができればブラックボックスシミュレーションが成功する。なお、ブラックボックスとは、証明者Ｐのビュー（Ｐの入力とセッションの対話記録（transcript）とＶ*のランダムテープの内容）とＳV*の出力が識別不可能であることをいう。
【００３１】
シミュレータＳによる巻き戻しスケジュールを記述するため、以下の定義を与える：
（定義２：プロトコル木）
敵Ｖ*によるコミット値の開示をシミュレータＳが受取るＮ＝（ｍ＋１）ｎ個の時点をプロトコル点（protocol point）と呼ぶ。Ｎはちょうど２のべきであるとする。図５にＮ＝８の例を示すように、プロトコル点を葉とする完全にバランスした２分木をプロトコル木といい、Τで表す。敵Ｖ*は、プロトコル木Τの深さ優先探索の順序でプロトコル点でメッセージを送信する。
【００３２】
（定義３：シミュレーション木）
プロトコル木Τに対して、図６にＮ＝８の例を示すように、根と葉以外の節点を重複させて得られる木をシミュレーション木（simulation tree）といい、Τ＾で表す。節をシミュレーション点（simulation point）といい、全部でＮ2／２個ある。
【００３３】
さて、シミュレータＳによる巻戻しは、シミュレーション木Τ＾を深さ優先の順序で葉以外の節点で行われる。コミット値ｖｉに続いてｖi+1が正しく開示されると、シミュレータＳはｖｉの直後に敵Ｖ*を巻き戻し、ｐi+1＝ｖi+1をコミットする。シミュレータＳが少なくとも１つのｉに対してこの処理に成功してセッションは解決された（solved）と言われる。
【００３４】
シミュレータＳの変形Ｓ*とＳ+とを図７に示す処理の違いを持つものとして考える。変形Ｓ*とＳ+は、各セッションの証明される文Ｔに関する証拠を持つ。
【００３５】
シミュレータＳがアボート（中止）する確率と、変形Ｓ*がアボートする確率との差は、各セッションのＴの証明のゼロ知識性により、セキュリティパラメータｋに関して無視できる。また、変形Ｓ*がアボートする確率と、変形Ｓ+がアボートする確率との差は、証明者Ｐのコミットメントの完全結合性により、セキュリティパラメータｋに関して無視できる。よって、次の補題１が成立する。
【００３６】
（補題１：Prabhakaran-Sahai、前掲論文）
シミュレータＳがアボートする確率と、変形Ｓ+がアボートする確率との差は、セキュリティパラメータｋに関して無視できる。
【００３７】
以下、シミュレータＳの代わりに、その変形Ｓ+を用いて解析する。敵Ｖ*がシミュレーション点の対（start, stop）に対して成功するとは、一方のシミュレーション点（start）で開始し、他方のシミュレーション点（stop）で終了するセッションが証明の本体に達したとき、シミュレータの変形Ｓ+がそのセッションを解決できていないことをいう。対の総数Ｏ（Ｎ２）は、セキュリティパラメータｋの多項式なので、各対に対して敵が成功する確率がｋに関して無視できることが証明できれば、敵が全ての対を用いても成功する確率は無視できる。
【００３８】
（定義４：森）
シミュレーション点startとstopに対応するプロトコル点をそれぞれproto-startとproto-stopとする。プロトコル木において、その子孫の節点が全てプロトコル間隔（proto-start, proto-stop）の内部に入る節点の集合を、プロトコル間隔（proto-start, proto-stop）によって決定されるプロトコル森（protocol forest）といい、Ｆで表す。同様に、シミュレーション木において、シミュレーション森（simulation forest）を定義し、Ｆ＾で表す。
【００３９】
あるセッションのプレアンブル内で検証者のコミットメントのｍ個のメッセージに対応するプロトコル点をそのセッションのスケジュール点（schedule point）という。
【００４０】
（定義５：良い森）
少なくとも２つのスケジュール点をプロトコル森Ｆ内にもつＦの部分グラフを良い森（good forest）といい、Ｇで表す。
【００４１】
良い森Ｇ内の葉ａに対して、そのピボット（pivot）ＸａをＧ内の直前の葉との共通の先祖で最も近くにあるものとする。もしそれが存在しなければ、良い森Ｇ内で葉ａを含む木の根とする。ｔａを葉ａからピボットＸａへの距離とする。
【００４２】
（補題２：Prabhakaran-Sahai、前掲論文）
良い森Ｇ内の辺の個数は、少なくともΣa ｔa＝ｍ−Ｏ(h)個ある。ここで、ｈはプロトコル木Τの高さである。また、葉ａの和は、良い森Ｇ内の全ての葉についてとる。
【００４３】
敵が行なえるスケジューリングにｃ−限定並行の制限を課すことで、どのセッションも、そのセッションに属する全てのプロトコル点がプロトコル木Τ中において、高さｈ’は次式の部分木に含まれる。
【数１】
2006041836.tif 000003
【００４４】
よって、補題２は、以下のように修正される。
【００４５】
（補題３）
良い森Ｇ内の辺の個数Σa ｔaは、少なくとも次式で表される。  
【数２】
2006041836.tif 000004
【００４６】
（定理３）
ｍ−２log２(cm)＝ω(log2 ｋ)ならば、シミュレーション点の対（start, stop）に対して、敵が成功する確率は、セキュリティパラメータｋに関して無視できる。
【００４７】
定理３の証明。シミュレーション対（start, stop）に対して、敵が成功する確率Ｐｒは、次式で表される。
【数３】
2006041836.tif 000005
【００４８】
補題３より、ｍ−２log２(cm)＝ω(log2 ｋ)ならば、敵が成功する確率は（１／２）ω(log2ｋ)で無視できる。                                                □
定理３より敵がＯ(Ｎ２)通り全ての（start, stop）を用いても成功確率は無視でき、定理２が得られる。                                                      □
（系１）
セッション数ｎ＝ｋｏ(1)とする。並行度ｃが正（ｃ＞０）の定数のとき、ラウンド数ｍ＝κ（ｋ）＋２log２ｃとすると、κ（ｋ）＝ω（log2 ｋ）ならば、ＲＫＺＫ（ｍ）は、∀Ｌ∈ＮＰに対するｃ−限定並行ゼロ知識証明系である。そのシミュレータは厳密に多項式時間で実行される。
【００４９】
系１の証明。定理２より、ｍ＝κ（ｋ）＋２log２ｃとおくと、
κ（ｋ）−２log２（κ（ｋ）＋２log２ｃ）＝ω（log２ ｋ）
□
続いて、以上のようなｃ−限定並行ゼロ知識証明に関し、プロトコルのｃ−限定並行性を保証するための実施形態について説明する。  
（実施形態）
図１は本発明の一実施形態に係るゼロ知識対話証明プロトコル管理装置が適用されたゼロ知識対話証明システムの構成を示す模式図である。このシステムは、プロトコル管理装置Ｍ、証明者装置Ｐ及びｎ台の検証者装置Ｖ１〜Ｖｎを備えている。なお、各装置Ｍ，Ｐ，Ｖ１〜Ｖｎは、いずれもハードウェア及び／又はソフトウェアにて実現可能なものであり、ソフトウェアにより実現される場合にはその動作を示すプログラムが予め記憶媒体又はネットワークから各装置Ｍ，Ｐ，Ｖ１〜Ｖｎのコンピュータにインストールされる。
【００５０】
ここで、プロトコル管理装置Ｍは、上限値記憶部１、並行度記憶部２、要求受信部３、許否判定部４及び許否送信部５を備えている。
【００５１】
ここで、上限値記憶部１は、１つのセッションの開始から終了までの間に自セッションを含めて並行実行されるセッションの数が累積されてなる累積並行度に関し、累積並行度の上限値ｃが記憶されるメモリであり、許否判定部４から読出可能となっている。ここで、上限値ｃは、ｃ−限定並行性を保証するための値であり、予め設定される。
【００５２】
並行度記憶部２は、図２に示す如き、並行セッション表ＣＳＴ（Concurrent Session Table）を記憶するメモリであり、セッション実行（プロトコル実行）の前後のチェックイン／チェックアウト処理として許否判定部４から読出／書込可能となっている。
【００５３】
チェックイン処理は、セッションの実行前に、並行セッション表ＣＳＴを参照してそのセッションの開始を許すか否かを許否判定部４が判定し、許可されたときにそのセッションのエントリ（セッションＩＤと累積並行度の行）を並行セッション表ＣＳＴに書込む処理であり、他のエントリの累積並行度の更新も含んでいる。チェックアウト処理は、セッションの終了後、許否判定部４が並行セッション表ＣＳＴからそのエントリを削除する処理である。本実施形態では、このようなセッション制御のモデルをチェックイン・チェックアウトモデルと呼んでいる。
【００５４】
並行セッション表ＣＳＴは、チェックイン・チェックアウトモデルに従ってｃ−限定並行性を保証する観点から、現在実行中のセッションを個別に示すセッションＩＤ毎に、当該セッションの累積並行度が記憶されるリストとなっており、リストの行数（現在のセッションＩＤの個数）が現在の並行度を示している。
【００５５】
ここで、現在の並行度及び累積並行度について図３に示す例を用いて説明する。  
現在の並行度は、現在実行中のセッションの個数を意味し、換言すると、現在同時に継続しているセッションの個数を意味しており、例えば各セッションｓ１，ｓ２，…，ｓ４の開始・終了に応じて増減する値となっている。
【００５６】
累積並行度は、ｃ−限定並行性の定義に基づく並行度であり、あるセッションの開始から終了までの間に自セッションを含めて並行実行されるセッションの個数を意味し、例えばセッションｓ１のように、他のセッションｓ２，ｓ３，ｓ４の開始に応じて増加するが、他のセッションｓ２，ｓ３が終了しても変化しない値（累積値）となっている。
【００５７】
なお、累積並行度が累積値であり、現在の並行度が増減値であることから、累積並行度は、現在の並行度と同じか又は大きい値となる。このため、上限値ｃを越えないように管理する並行度は、現在の並行度よりも累積並行度とした方が安全であると考えられる。ｃ−限定並行性は、累積並行度が上限値ｃを越えないことで保証される。
【００５８】
一方、図１に戻り、要求受信部３は、ゼロ知識対話証明プロトコルの開始を要求する開始要求メッセージを受信し、受信内容を許否判定部４に送出する機能と、ゼロ知識対話証明プロトコルの終了を通知する終了通知メッセージを受信し、受信内容を許否判定部４に送出する機能とをもっている。
【００５９】
許否判定部４は、要求受信部３が開始要求メッセージを受信した場合に、上限値記憶部１内の上限値ｃと、並行度記憶部２内の並行セッション表ＣＳＴにおけるセッションＩＤ毎の累積並行度とに基づいて開始を許可するか否かを判定する機能と、判定結果を許否送信部５に送出する機能をもっている。
【００６０】
許否判定部４は、並行度記憶部２内の並行セッション表ＣＳＴにおける全ての累積並行度が上限値記憶部１内の上限値ｃを下回るとき、開始を許可する旨を判定する機能と、判定により開始を許可したとき、並行セッション表ＣＳＴの全ての累積並行度を１増加させる機能と、判定により開始を許可したとき、並行セッション表ＣＳＴ内のセッションＩＤの個数（エントリ数）に１を加えて許可セッションの累積並行度を得る機能と、得られた累積並行度を許可セッションのセッションＩＤに関連付けて並行セッション表ＣＳＴに書込む機能とをもっている。
【００６１】
許否判定部４は、並行度記憶部２内の並行セッション表ＣＳＴにおけるいずれかの累積並行度が上限値記憶部１内の上限値ｃに達しているとき、開始を許可しない旨を判定する機能をもっている。
【００６２】
許否判定部４は、要求受信部３が終了通知メッセージを受信した場合に、並行度記憶部２内の並行セッション表ＣＳＴにおける該当するエントリ（セッションＩＤ及び累積並行度）を削除する機能とをもっている。
【００６３】
許否送信部５は、許否判定部４による判定結果を開始要求元に送信する機能をもっている。
【００６４】
証明者装置Ｐは、秘密情報を保持する機能と、秘密情報に基づいて各検証者装置Ｖ１〜Ｖｎとの間で複数並行してゼロ知識対話証明プロトコルを実行する機能と、プロトコル実行前に検証者装置Ｖ１〜Ｖｎから受けたセッション開始要求メッセージをプロトコル管理装置Ｍに送信する機能と、プロトコル実行後にプロトコル管理装置Ｍにセッション終了通知メッセージを送信する機能とをもっている。
【００６５】
検証者装置Ｖ１〜Ｖｎは、証明者装置Ｐとの間で複数並行してゼロ知識対話証明プロトコルを実行する機能と、プロトコル実行前に証明者装置Ｐにセッション開始要求メッセージを送信する機能とをもっている。
【００６６】
次に、以上のように構成されたゼロ知識対話証明システムの動作を図４のフローチャートを用いて説明する。ここでは、検証者装置Ｖ１〜Ｖｎのうち、検証者装置Ｖｊを例に挙げて述べる。
【００６７】
いま、証明者装置Ｐは検証者装置Ｖｊに対して証明前を示す状態Ａにあり、検証者装置Ｖｊは検証前を示す状態Ｃにあり、プロトコル管理装置Ｍはプロトコル管理中を示す状態Ｅにあるとする。
【００６８】
この状態で証明者装置Ｐは、セッション開始要求の受信を待機する（ＳＴ１）。
【００６９】
検証者装置Ｖｊは、ゼロ知識対話証明を開始する前に、セッション開始要求メッセージを証明者装置Ｐに送信する（ＳＴ２）。セッション開始要求メッセージは、ゼロ知識対話証明プロトコルにおける、検証者装置Ｖｊから証明者装置Ｐへの最初のメッセージを要求と見なしてもよいし、それとは別に、要求用のメッセージとしてもよい。
【００７０】
証明者装置Ｐは、検証者装置Ｖｊからセッション開始要求メッセージを受信すると（ＳＴ３）、このセッション開始要求メッセージをプロトコル管理装置Ｍに送信する。
【００７１】
プロトコル管理装置Ｍにおいては、管理タイミングの到来の待機中に（ＳＴ４）、要求受信部３が受信したメッセージに関し、許否判定部４が受信メッセージがセッション開始要求か否かを判定する（ＳＴ５）。セッション開始要求でない場合（ＳＴ５；ＮＯ）にはセッション終了なので、ステップＳＴ１７に進む。
【００７２】
ここではセッション開始要求であるので（ＳＴ５；ＹＥＳ）、許否判定部４はセッション開始要求に基づいて、並行度記憶部２内の並行セッション表ＣＳＴを読出し（ＳＴ６）、新たに開始要求があったセッションを開始した場合にｃ−限定並行性が破れるセッションが存在しない旨を確認する。
【００７３】
具体的には許否判定部４は、上限値記憶部１内の上限値ｃと、並行セッション表ＣＳＴにおけるセッションＩＤ毎の累積並行度ｃ０，ｃ１，…とに基づいて、累積並行度ｃ０，ｃ１，…が上限値ｃに達しているセッションが存在するか否かに応じて開始を許可するか否かを判定する（ＳＴ７）。
【００７４】
例えば並行セッション表ＣＳＴ内のいずれかの累積並行度ｃｉが上限値ｃに達しているとき（ｃｉ＝ｃ）、拒否判定部４は開始を許可しない旨を判定し（ＳＴ７；ＹＥＳ）、拒否送信部５は要求の拒否を通知する要求拒否メッセージを要求元の証明者装置Ｐに送信する（ＳＴ８）。しかる後、プロトコル管理装置Ｍは状態Ｅに戻って他のセッションの管理を継続する。
【００７５】
証明者装置Ｐは、要求拒否メッセージを受信して検証者装置Ｖｊに転送し（ＳＴ９）、状態Ａに戻る。あるいは、拒否メッセージを返す代わりに、新たなセッションを開始できる状態になるまで、受取った開始要求を保留しておいてもよい。
【００７６】
一方、ステップＳＴ７の判定の結果、並行セッション表ＣＳＴにおける全ての累積並行度ｃ０，ｃ１，…が上限値ｃを下回るとき（ｃ０＜ｃ、ｃ１＜ｃ，…）、開始を許可する旨を判定する（ＳＴ７；ＮＯ）。許否判定部４は、判定により開始を許可したとき、並行セッション表ＣＳＴを更新する（ＳＴ１０）。
【００７７】
この更新は、並行セッション表ＣＳＴ内の全ての累積並行度ｃ０，ｃ１，…を１増加させる処理と、並行セッション表ＣＳＴ内のセッションＩＤ ｓ０，ｓ１，…の個数（エントリ数：現在の並行度）に１を加えて許可セッション（新規セッション）の累積並行度ｃｊを得る処理と、得られた累積並行度ｃｊを許可セッションのセッションＩＤ ｓｊに関連付けて並行セッション表ＣＳＴに書込む処理とを含んでいる。
【００７８】
並行セッション表ＣＳＴの更新完了後、許否判定部４は、開始を許可する旨の判定結果を許否送信部５に送出する。許否送信部５は、この判定結果に基いて、開始要求の受理を通知する受理メッセージを開始要求元の証明者装置Ｐに送信する(ＳＴ１１）。しかる後、プロトコル管理装置Ｍは状態Ｅに戻って他のセッションの管理を継続する。
【００７９】
証明者装置Ｐは、受理メッセージを受信して検証者装置Ｖｊに転送する（ＳＴ１２）。
【００８０】
検証者装置Ｖｊは、ステップＳＴ９の要求拒否メッセージ又はステップＳＴ１２の受理メッセージを受信すると（ＳＴ１３）、この受信したメッセージにより、開始要求が受理されたか否かを判定する（ＳＴ１４）。開始要求が拒否された場合（ＳＴ１４；ＮＯ）、検証者装置Ｖｊは、開始要求を再度送信するか又は処理を終了する。なお、再要求を行うか否か、どのようなタイミングで再要求を行うかは、任意に設計可能である。
【００８１】
一方、ステップＳＴ１４の判定の結果、開始要求が拒否された場合（ＳＴ１４；ＮＯ）、検証者装置Ｖｊは証明者装置Ｐとの間でメッセージの送受信を行い、検証者装置Ｖｊ及び証明者装置Ｐは、ゼロ知識証明プロトコルのセッションを実行する（ＳＴ１５〜ＳＴ１６）。
【００８２】
セッションが終了すると、検証者装置Ｖｊは検証後を示す状態Ｄに移る。証明者装置Ｐは、ゼロ知識証明プロトコルの終了を通知する終了通知メッセージをプロトコル管理装置Ｍに送信し、検証者装置Ｖｊに対しての証明後を示す状態Ｂに移る。なお、セッションの終了は、ゼロ知識対話証明プロトコルにおける証明者装置Ｐから検証者装置Ｖｊへの最後のメッセージの送信をもって終了とみなしても良いし、終了を通知するメッセージを一方から他方へ送信しても良い。
【００８３】
一方、プロトコル管理装置Ｍにおいては、要求受信部３が終了通知メッセージを受信すると、前述したステップＳＴ４，ＳＴ５（；ＮＯ）を介して許否判定部４が並行度記憶部２内の並行セッション表ＣＳＴから、該当するセッションのエントリを削除し（ＳＴ１７）、状態Ｅに戻って他のセッションの管理を継続する。
【００８４】
上述したように本実施形態によれば、セッションの累積並行度の上限値ｃと、現在実行中のセッションｓ０，ｓ１，…毎の累積並行度ｃ０，ｃ１，…とを各記憶部１，２に記憶し、開始要求メッセージを受信した場合に、この上限値ｃと各セッション毎の累積並行度ｃ０，ｃ１，…とに基づいて、新たなセッションｓｊの開始を許可する構成である。
【００８５】
ここで、必要なリソースは、累積並行度の上限値ｃと、現在実行中のセッション毎の累積並行度とを記憶する記憶部１，２が主であり、これは比較的小さいリソースで実現可能である。また、必要な制御は、上限値ｃと各セッション毎の累積並行度とを比較し、累積並行度が上限値ｃを超えない場合に開始を許可する内容であり、これは非常に複雑とは言えない。このように本実施形態は、従来の考えとは異なり、非常に複雑な制御や大きなリソースを必要としない。よって、本実施形態は、簡易な構成により、ｃ−限定並行性を満たすセッション制御を実現できる。
【００８６】
補足すると、本実施形態は、チェックイン・チェックアウトモデルによってセッション制御を行い、ｃ−限定並行性を保証している。ここで、ｃ−限定並行性を保つには、必ずしもチェックイン・チェックアウトモデルに従ったセッション制御である必要はない。
【００８７】
しかしながら、本実施形態は、チェックイン・チェックアウトモデルにより、並行セッション表ＣＳＴへのアクセス時期をセッションの開始時と終了時だけとし、セッション実行中の個々のメッセージに関してはＣＳＴにアクセスしない構成として、簡素にセッション制御を実行している。
【００８８】
なお、本実施形態は、プロトコル管理装置Ｍが証明者装置Ｐから開始要求メッセージを受信する場合について説明したが、これに限らず、検証者装置Ｖｊから開始要求メッセージを受信する構成としても、本発明を同様に実施して同様の効果を得ることができる。
【００８９】
同様に、本実施形態は、プロトコル管理装置Ｍが証明者装置Ｐから終了通知メッセージを受信する場合について説明したが、これに限らず、検証者装置Ｖｊから終了通知メッセージを受信する構成としても、本発明を同様に実施して同様の効果を得ることができる。
【００９０】
また、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【００９１】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【００９２】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【００９３】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【００９４】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【００９５】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【００９６】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【００９７】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００９８】
【図１】本発明の一実施形態に係るゼロ知識対話証明プロトコル管理装置が適用されたゼロ知識対話証明システムの構成を示す模式図である。
【図２】同実施形態における並行セッション表ＣＳＴ及びチェックイン・チェックアウトモデルを説明するための模式図である。
【図３】同実施形態における現在の並行度及び累積並行度を説明するための模式図である。
【図４】同実施形態における動作を説明するためのフローチャートである。
【図５】同実施形態の前提となるｃ−限定並行ゼロ知識証明におけるプロトコル木を説明するための模式図である。
【図６】同実施形態の前提となるｃ−限定並行ゼロ知識証明におけるシミュレーション木を説明するための模式図である。
【図７】同実施形態の前提となるｃ−限定並行ゼロ知識証明におけるシミュレータの処理の違いを表す図である。
【符号の説明】
【００９９】
１…上限値記憶部、２…並行度記憶部、３…要求受信部、４…許否判定部、５…許否送信部、Ｍ…プロトコル管理装置、Ｐ…証明者装置、Ｖ１〜Ｖｎ…検証者装置。
【図１】
2006041836.tif 000006
【図２】
2006041836.tif 000007
【図３】
2006041836.tif 000008
【図４】
2006041836.tif 000009
【図５】
2006041836.tif 000010
【図６】
2006041836.tif 000011
【図７】
2006041836.tif 000012