(57)【特許請求の範囲】
【請求項１】
検証装置と通信可能に接続される証明装置であって、
予め定められた第一の関係を満たす共通入力および証拠とランダムテープとに基づいて、第一の関係に関する特別正直検証者零知識対話証明の証明のコミットメントを生成する第一証明コミットメント生成装置と通信可能に接続され、
第一の関係に関する共通入力および証拠とランダムテープと挑戦値とに基づいて、第一の関係に関する特別正直検証者零知識対話証明の応答を生成する第一応答生成装置と通信可能に接続され、
第二の関係に関する共通入力と証明コミットメントと挑戦値と応答とに基づいて、第二の関係に関する特別正直検証者零知識対話証明の受理を表す信号または不受理を表す信号を出力する第二対話証明検証装置と通信可能に接続され、
第二の関係に関する共通入力と挑戦値とランダムテープとに基づいて、第二の関係に関する証明コミットメントおよび応答を生成する模擬装置と通信可能に接続され、
ハッシュ関数の計算を行うハッシュ関数の計算装置と通信可能に接続され、
予め定められた第一の関係を満たす共通入力および証拠が入力される共通入力等受信手段と、
第一のランダムテープおよび第二のランダムテープが入力されるランダムテープ入力手段と、
前記検証装置から、第二の関係に関する共通入力および当該共通入力に対応する証拠の知識の非対話証明を受信する非対話証明受信手段と、
前記非対話証明を用いて、前記ハッシュ関数の計算装置および前記第二対話証明検証装置と通信した結果により、前記非対話証明を受理するか否かを判定する非対話証明受理不受理判定手段と、
第一のランダムテープ、第二のランダムテープ、第一の関係を満たす共通入力と証拠、および前記非対話証明に含まれる共通入力を用いて、前記模擬装置、前記第一証明コミットメント生成装置、前記ハッシュ関数の計算装置、および第一応答生成装置と通信することにより、第一の関係に関する共通入力に対する証拠の知識あるいは、第二の関係に関する共通入力に対する証拠の知識のいずれかの知識があることの知識の非対話証明を生成する証拠知識非対話証明生成手段と、
前記証拠知識非対話証明生成手段が生成した知識の非対話証明を前記検証装置に送信する非対話証明送信手段とを備えた
ことを特徴とする証明装置。
【請求項２】
非対話証明受信手段は、
検証装置から、第二の関係に関する共通入力と証明コミットメントと応答とを含む非対話証明を受信し、
非対話証明受理不受理判定手段は、
前記非対話証明に含まれる第二の関係に関する共通入力および証明コミットメントをハッシュ関数の計算装置に送信し、前記第二の関係に関する共通入力および証明コミットメントに応じた挑戦値となるハッシュ値を計算させ、
前記挑戦値と、前記非対話証明に含まれる第二の関係に関する共通入力、証明コミットメント、および応答とを、第二対話証明検証装置に送信し、第二対話証明検証装置が出力力する信号により、前記非対話証明を受理するか否かを判定し、
証拠知識非対話証明生成手段は、
第二のランダムテープにより第二の関係に関する挑戦値を生成し、
前記第二の関係に関する共通入力、前記第二の関係に関する挑戦値、および第二のランダムテープを模擬装置に送信し、第二の関係に関する証明コミットメントおよび応答を生成させ、
第一の関係を満たす共通入力および証拠と、第一のランダムテープとを第一証明コミットメント生成装置に送信し、第一の関係に関する証明コミットメントを生成させ、
第一の関係に関する共通入力および証明コミットメントと、第二の関係に関する共通入力と、模擬装置に生成させた第二の関係に関する証明コミットメントとを前記ハッシュ関数の計算装置に送信し、第一の関係に関する共通入力および証明コミットメントと第二の関係に関する共通入力および証明コミットメントとに応じたハッシュ値を計算させ、
当該ハッシュ値と前記第二の関係に関する挑戦値とに基づいて第一の関係に関する挑戦値を決定し、
第一の関係を満たす共通入力および証拠と、第一のランダムテープと、前記第一の関係に関する挑戦値とを第一応答生成装置に送信し、第一の関係に関する応答を生成させ、
第一の関係に関する証明コミットメント、挑戦値、および応答と、第二の関係に関する挑戦値と、模擬装置に生成させた第二の関係に関する証明コミットメントおよび応答とを知識の非対話証明とする
請求項１に記載の証明装置。
【請求項３】
請求項１または請求項２に記載の証明装置と通信可能に接続される検証装置であって、
第一の関係に関する共通入力と証明コミットメントと挑戦値と応答とに基づいて、第一の関係に関する特別正直検証者零知識対話証明の受理を表す信号または不受理を表す信号を出力する第一対話証明検証装置と通信可能に接続され、
第二の関係に関する共通入力と証明コミットメントと挑戦値と応答とに基づいて、第二の関係に関する特別正直検証者零知識対話証明の受理を表す信号または不受理を表す信号を出力する第二対話証明検証装置と通信可能に接続され、
第二の関係に関する共通入力および証拠とランダムテープとに基づいて、第二の関係に関する特別正直検証者零知識対話証明の証明のコミットメントを生成する第二証明コミットメント生成装置と通信可能に接続され、
第二の関係に関する共通入力および証拠とランダムテープと挑戦値とに基づいて、第二の関係に関する特別正直検証者零知識対話証明の応答を生成する第二応答生成装置と通信可能に接続され、
ハッシュ関数の計算を行うハッシュ関数の計算装置と通信可能に接続され、
第一の関係に関する共通入力が入力される共通入力入力手段と、
第三のランダムテープとしてランダムテープRVおよびランダムテープR'V が入力されるランダムテープ入力手段と、
第二の関係を満たす共通入力および証拠を、第三のランダムテープのうちのランダムテープR'V から生成する共通入力等生成手段と、
前記共通入力等生成手段に生成された第二の関係を満たす共通入力および証拠と、第三のランダムテープのうちのランダムテープRVとを用いて、前記第二証明コミットメント生成装置、前記第二応答生成装置、および前記ハッシュ関数の計算装置と通信することにより、前記共通入力との間で第二の関係を満たすような証拠の知識の非対話証明を生成する証拠知識非対話証明生成手段と、
前記証拠知識非対話証明生成手段によって生成された知識の非対話証明を証明装置に送信する非対話証明送信手段と、
証明装置から、第一の関係に関する共通入力に対する証拠の知識あるいは、第二の関係に関する共通入力に対する証拠の知識のいずれかの知識があることの知識の非対話証明を受信する非対話証明受信手段と、
第二の関係に関する共通入力と、共通入力入力手段に入力された第一の関係に関する共通入力と、非対話証明受信手段が受信した非対話証明とを用いて、前記第一対話証明検証装置、前記第二対話証明検証装置、および前記ハッシュ関数の計算装置と通信を行うことによって、非対話証明受信手段が受信した非対話証明を受理するか否かの判定を行い、その判定結果を出力する判定手段とを備えた
ことを特徴とする検証装置。
【請求項４】
証拠知識非対話証明生成手段は、
第二の関係を満たす共通入力および証拠と、第三のランダムテープのうちのランダムテープRVとを第二証明コミットメント生成装置に送信し、第二の関係に関する証明コミットメントを生成させ、
第二の関係に関する共通入力と前記第二の関係に関する証明コミットメントをハッシュ関数の計算装置に送信し、前記共通入力および前記証明コミットメントに応じた挑戦値となるハッシュ値を計算させ、
第二の関係を満たす共通入力および証拠と、前記ランダムテープRVと、前記挑戦値とを、第二応答生成装置に送信し、第二の関係に関する応答を生成させ、
第二の関係に関する共通入力、証明コミットメント、および応答を、知識の非対話証明とし、
非対話証明受信手段は、
証明装置から、第一の関係に関する証明コミットメント、挑戦値、および応答と、第二の関係に関する証明コミットメント、挑戦値、および応答とを含む非対話証明を受信し、
判定手段は、
共通入力入力手段に入力された第一の関係に関する共通入力と、非対話証明に含まれる第一の関係に関する証明コミットメント、挑戦値、および応答とを、第一対話証明検証装置に送信し、第一対話証明検証装置が出力する信号を受信し、
第二の関係に関する共通入力と、非対話証明に含まれる第二の関係に関する証明コミットメント、挑戦値、および応答とを、第二対話証明検証装置に送信し、第二対話証明検証装置が出力する信号を受信し、
第一の関係に関する共通入力および証明コミットメントと第二の関係に関する共通入力および証明コミットメントとをハッシュ関数の計算装置に送信して、第一の関係に関する共通入力および証明コミットメントと第二の関係に関する共通入力および証明コミットメントとに応じたハッシュ値を計算させ、当該ハッシュ値と非対話証明に含まれる第一の関係に関する挑戦値および第二の関係に関する挑戦値との間に所定の関係が成立しているか否かを判定し、
その判定の結果と、第一対話証明検証装置および第二対話証明検証装置から受信した信号とに基づいて、非対話証明を受理するか否かを判定する
請求項３に記載の検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、否認可能零知識対話証明に適用される証明装置及び検証装置に関する。
【背景技術】
【０００２】
従来のランダムオラクルモデルにおける否認可能零知識対話証明の技術について、例えば、非特許文献１に記載されている。以下、非特許文献１に記載された技術（従来技術１と記すことにする。）について説明する。
【０００３】
図４は、非特許文献１に記載される構成を示す説明図である。なお、本出願における図面において、合流する矢印は、矢印の元の情報が全て集まって矢印の先へ送られることを意味し、分岐する矢印は、矢印の元の情報全てまたは一部がそれぞれの矢印の先へ送られることを意味する。
【０００４】
また、従来技術１が証明する言語は、ＮＰ完全であるグラフの三彩色問題である。ここで、言語とはデータの集合を意味し、「言語が三彩色問題である」とは、データの集合が、三彩色問題の集合であることを意味する。また、あるｄがある言語（例えば三色彩問題）に属することを証明するとは、ｄが三色彩問題の集合に属することを証明することである。従来技術１で、本言語を否認可能零知識で証明できるということは、従来技術１でＮＰに属する全ての言語が否認可能零知識で証明できることを意味する。
【０００５】
図４に示す証明装置１０３と検証装置１０４には、有方向グラフGn=(VG,EG)が共通入力１０１として入力される。ここで、VGはグラフの頂点の集合であり、EGは辺の集合であり、 両者によりグラフG が表現される。また、頂点の数（|VG|と記す。）は、|VG|=nとする。
【０００６】
また、証明装置１０３には各頂点の色 C=(c1,c2,...,cn)が証拠１０２として入力される。各i ∈{1,...,n} はci∈ {1,2,3}で、三色の色を表し、 頂点の塗り分けを表現する。C は、 全ての辺に関して、この辺で連結された二つの頂点が異る色となる様な塗り分けとする。
【０００７】
証明装置１０３は、検証装置１０４にG に関する上記の証拠C が存在することを否認可能零知識対話証明する。「対話証明する」とは、もし上記性質を持つC がG に対して存在しなければ、いかなる偽の証明装置を用いても、この偽の証明装置と検証装置（本例では検証装置１０４）が互いの通信及び各装置における計算を行なった後、検証装置（本例では検証装置１０４）が最終的に証明を受理することを表す信号を出力せず、証明装置（本例では証明装置１０３）と検証装置（本例では検証装置１０４）に上記G とC が入力されれば、検証装置（本例では検証装置１０４）は証明を受理することを表す信号を出力することを意味する。
【０００８】
また、否認可能零知識であるとは次のことを言う。いかなるデータが入力された、多項式時間しか動作しないいかなる偽の検証装置が証明装置（本例では証明装置１０３）と通信を行なっても、その偽の検証装置の出力は次の性質（性質Ａと記す。）を満すことをいう。ただし、偽の検証装置は同じG と C が与えられた複数の証明装置と同時並行的に通信を行なうことが可能であるとする。ここで、上記の性質Ａとは、偽の検証装置と通信可能な、多項式時間しか動作しないある模擬装置が存在して、この装置に上記偽の検証装置への入力が与えられたならば、この模擬装置が証明装置（本例では証明装置１０３）と通信が不可能であっても、上記偽の検証装置の出力とその分布が識別不可能なデータを出力することができることである。性質Ａの具体例を示す。例えば、任意の偽の検証装置が、証明装置（本例では証明装置１０３）と通信をした後、何らかのデータを出力したとする。このデータをａと呼ぶことにする。一方、模擬装置は、偽の検証装置と通信を行い（このとき、証明装置として振る舞う）、その後、何らかのデータを出力する。このデータをｂと呼ぶことにする。模擬装置は、どのような偽の検証装置を持ってきても、その出力データａの分布と識別不可能な分布を持つデータｂを出力できる（性質Ａ）。
【０００９】
なお、「データａの分布とデータｂの分布とが識別不可能である」とは、以下のような意味である。あるデータの分布Ａとデータの分布Ｂが与えられたとする。また、データａは、分布Ａから一様無作為に選ばれたデータであり、データｂは、分布Ｂから一様無作為に選ばれたデータであるとする。どのような識別装置Ｄ（０か１を出力する装置であるものとする。）を持ってきても、識別装置Ｄにａを入力した時における識別装置Ｄが１を出力する確率と、識別装置Ｄにｂを入力した時における識別装置Ｄが１を出力する確率とが等しければ、データａの分布とデータｂの分布とが識別不可能であるという。なお、確率は、分布Ａ，Ｂからａとｂとを何度も選びなおして求める。
【００１０】
以下、図４に示す証明装置１０３および検証装置１０４の動作について説明する。以下の説明では、離散対数問題を使った例を示すが、一般の(確率的)一方向性関数でも可能である。Gqを位数q の離散対数問題が難しい乗法群とし、g をその生成子とする。t を安全変数とする。t の値は、１６０以上であれば十分である。Hash(・)はハッシュ関数で、その出力の大きさはt ビットとする。
【００１１】
ステップ１：検証装置１０４は無作為にx ∈ Z/qZを選び、y=gxを計算する。
【００１２】
ステップ２：検証装置１０４は、i = 1,...,t に関してx'[i]∈ Z/qZを選び、y'[i] = gx'[i] とする。
【００１３】
ステップ３：検証装置１０４は、i = 1,...,t に関して、乱数 r[1,i] ∈ {0,1}n と、乱数 r[2,i] ∈ {0,1}n を選ぶ。検証装置１０４は、i = 1,...,t に関して、ハッシュ値 c[1,i] = Hash(x'[i],r[1,i]) と、ハッシュ値 c[2,i] = Hash(x'[i]+x,r[2,i]) と、をハッシュ関数を生成する装置１０５と何度も通信して生成する。
【００１４】
ステップ４：検証装置１０４は、t ビットのハッシュ値c を次の様に計算する。
【００１５】
h=Hash({g,y,y'[i],c[1,i],c[2,i]}i=1,...,t) 
【００１６】
検証装置１０４は、i=1,...,t に関して、h のi 番目のビットが０ならば、t[1,i] = x'[i]、t[2,i] = r[1,i] とする。また、h のi 番目のビットが１ならば、t[1,i] = x'[i]+x、t[2,i] = r[2,i]) とする。
【００１７】
ステップ５：検証装置１０４は、証明装置１０３に{g,y,y'[i],c[1,i],c[2,i],t[1,i],t[2,i]}i=1,...,t)を送付する。
【００１８】
ステップ６：証明装置１０３は、h'=Hash({g,y,y'[i],c[1,i],c[2,i]}i=1,...,t) を計算する。証明装置１０３は、ハッシュ関数を計算する装置１０７と通信することで、i=1,...,t に関して、h'のi 番目のビットが０ならば、c[1,i] = Hash(t[1,i],t[2,i])であることと、gt[1,i] = y'[i] であることを確認し、h'のi 番目のビットが１ならば、c[2,i] = Hash(t[1,i],t[2,i])であることと、gt[2,i] = y・y'[i] であることを確認する。
【００１９】
ステップ７：証明装置１０３は、y = gxなるx を知っているか、あるいはG に対してC を知っていることの、ハッシュ関数１０７を用いた非対話的零知識証明を生成する。ただし、どちらを知っているかは識別できない様に証明する。また、ステップ７における非対話的零知識証明は、例えば、非特許文献３に記載された方法により生成する。
【００２０】
ステップ８：証明装置１０３は、ステップ７で生成した非対話的零知識証明を検証装置１０４に送付する。
【００２１】
ステップ９：検証装置１０４は、証明装置１０３から送られてきた非対話的零知識証明を検証し、正当であれば受理を、不当であれば不受理を表す信号を検証結果１０９として出力する。
【００２２】
ハッシュ関数がランダムなデータを返す関数だと仮定すれば、ステップ１−５は検証装置１０４の、検証装置１０４がx を知っていることの非対話的零知識証明である。これは次の様にして分かる。
【００２３】
証明装置１０３から送られるデータは、h'=Hash({g,y,y'[i],c[1,i],c[2,i]}i=1,...,t) に対し、以下のようになっていればよい。
【００２４】
すなわち、i=1,...,t に関して、h'のi 番目のビットが０ならば、c[1,i] = Hash(t[1,i],t[2,i])であり、gt[1,i] = y'[i] であり、h'のi 番目のビットが１ならば、c[2,i] = Hash(t[1,i],t[2,i])であり、gt[2,i] = y・y'[i] であればよい。
【００２５】
このようなデータは、あらかじめh'の値が決まっていれば簡単に生成可能である。ハッシュ関数がランダムな値を返す関数だと仮定すれば、このような仮定が可能である為、x を知らなくとも上記データは生成可能である。このため、このデータから証明装置１０３がいかなる知識を得ることもない。
【００２６】
上記の証明が、証明装置１０３と検証装置１０４とにおける対話証明となっていることは次の事から分かる。ステップ７において証明装置１０３は検証装置１０４に対し、G に対して（１）C を知っている、すなわちG に対してC が存在する、あるいは （２）x を知っている、のいずれかであることを証明している。ところが、ステップ５で受け取るデータから証明装置１０３は何ら知識を得ることができないため、Gq の離散対数を求めることができず、z を知ることができない。よって、上記の（１）を証明する必要がある。
【００２７】
また、上記の動作において、証明装置１０３と検証装置１０４とにおける対話は否認可能零知識となっていることは次の事から分かる。ランダムオラクルモデルでは検証装置１０４が、ハッシュ値 c[1,i] = Hash(x'[i],r[1,i])と、ハッシュ値 c[2,i] = Hash(x'[i]+x,r[2,i])とを計算する時には、それぞれ(x'[i],r[1,i])と(x'[i]+x,r[2,i])とをランダムオラクルに送らなければならない。模擬装置がこのような値を途中で傍受すると、(x'[i]+x) - x'[i] = x のように、容易にx を求めることができる。このx を知る模擬装置は、ステップ７において上記（２）の「x を知っていること」を証明することができる。これは上記（１） の「C を知っていること」の証明と識別できないため、証明装置１０３の生成するデータと識別ができないデータを生成することが可能である。 
【００２８】
上記の動作で、証明装置１０３と検証装置１０４とにおける否認可能零知識対話証明は２ラウンドである。すなわち、検証装置１０４から証明装置１０３への通信が一回、証明装置１０３から検証装置１０４への通信が一回、合わせて二回の通信しか必要としない。
【００２９】
また、従来の特別正直検証者零知識対話証明の技術については、例えば、非特許文献２に記載されている。なお、「特別正直検証者」とは、検証者（検証装置）が証明者（証明装置）に送るデータが乱数であるという意味である。また、特別正直検証者零知識対話証明では、最初に証明装置から検証装置に送られるメッセージaRと、次に検証装置から証明装置に送られるメッセージeRと、最後に証明装置から検証装置に送られるメッセージzRとを用いる。「証明コミットメント」とは、上記の最初に検証装置に送られるメッセージaRのことである。また、「挑戦値」とは、次に検証装置から証明装置に送られるメッセージeRのことである。「応答」とは、最後に証明装置から検証装置に送られるメッセージzRのことである。
【００３０】
以下、非特許文献２に記載された技術（従来技術２と記すことにする。）について説明する。図５および図６は、非特許文献２に記載される構成を示す説明図である。また、以下の説明において、関係をR 、共通入力（図５および図６では共通入力２０７）をX 、証拠（図６では証拠２０８）をW の記号で表す。共通入力X と証拠W が関係R を満たすことを(X,W) ∈ Rと記す。
【００３１】
図５に示す証明コミットメント生成装置２０１は、関数ARにより証明コミットメントを生成する装置である。応答生成装置２０２は、関数ZRにより応答を生成する関数である。検証装置２０３は、関数VRにより検証結果を出力する装置である。図６に示す模擬装置２０４は、関数SRの演算を行う装置である。証拠抽出装置２０５は、関数ERにより証拠を抽出する装置である。関数AR、関数ZR、関数VR、関数SR、関数ERについては、後述する。
【００３２】
関係R に関する３ラウンド特別正直検証者零知識対話証明をSHVZKIP(R)と記す。これは、証明コミットメントを生成する関数AR、応答を生成する関数ZR、検証の為の関数VR、模擬の為の関数SR、証拠抽出の関数ERを用い、以下のような性質を満すものである。以下の説明で、RP，RSは、ランダムテープである。
【００３３】
[性質1]
挑戦値eR（図における挑戦値２１２）を乱数２０６とする。また、証明コミットメントaR（図における証明コミットメント２０９）と応答zR（図における応答２１０）が以下の式によって表されるとする。
【００３４】
aR = AR(X,W,RP)
zR = ZR(X,W,RP,eR)
【００３５】
このとき、VR = VR(X,aP,eR,zR)=1 が成り立つ。ここでVRの出力を検証結果２１１と呼ぶ。
【００３６】
[性質2]
証明コミットメントaR（図における証明コミットメント２１３）、第一挑戦値eRと第二挑戦値e'R （図では、第一挑戦値および第二挑戦値の組２１４として示している。）、第一応答zRと第二応答z'R （図では、第一応答および第二応答の組２１５として示している。）が以下の式を満たしているとする。
【００３７】
VR(X,aR,eR,zR)=1 
VR(X,aR,e'R,z'R)=1 
eR ≠ e'R
【００３８】
このとき、W'= ER(aR,eR,zR,e'R,z'R) なる証拠W'（図における証拠２１６） は、(X,W')∈ Rとなる。
【００３９】
[性質3]
挑戦値eR（図における挑戦値２１２）を乱数とする。また、証明コミットメントaR（図における証明コミットメント２０９）と応答zR（図における応答２１０）が以下の式によって表されるとする。ただし、RPはランダムテープ２０６である。
【００４０】
aR = AR(X,W,RP)
zR = ZR(X,W,RP,eR)
【００４１】
一方、挑戦値e'R （図における挑戦値２１６）を乱数とする。また、証明コミットメントa'R（図における証明コミットメント２１７）と応答z'R（図における応答２１８）が以下のように導出されるとする。ただし、RSはランダムテープ２１９である。
【００４２】
(a'R,z'R) = SR(X,e'R,RS)
【００４３】
このとき、ランダムテープRP（図におけるランダムテープ２０６）をランダムに振ったときの (aR,eR,zR) の分布と、ランダムテープRS（図におけるランダムテープ２１９）をランダムに振ったときの (a'R,e'R,z'R) の分布とを識別することが難しい。
【００４４】
SHVZKIP(R)を用いて対話証明を行なった場合、検証装置の選ぶeRがランダムでなければならないという制約があるが、一般に検証装置がその様なeRを選ぶ保証はないため、この対話証明は零知識とはならない。
【００４５】
しかし、多くのR に関する効率的なSHVZKIP(R)が知られているため、このSHVZKIP(R)を利用して、効率の悪化を抑えながら零知識対話証明を構成することには応用上意義がある。
【００４６】
以下に、SHVZKIP(R)の例をあげる。X はGqの二つの元(y,g) とし、W をZ/qZの元x とし、y=gxなる関係を満すとき、(X,W) ∈ Rとする。
【００４７】
関数ARは、例えば、以下のような関数である。入力は、X,W 、及びランダムテープRPである。そして、RPからランダムな x' ∈ Z/qZ を生成し、aR = y' =gx' として、aRを出力する。
【００４８】
関数ZRは、例えば、以下のような関数である。入力は、X,W、ランダムテープRP、及び eR=cである。そして、 zR = r = xc + x' mod q を計算し、zRを出力する。
【００４９】
関数VRは、例えば、以下のような関数である。入力は、X,aR,eR,zRである。そして、gr = yc y'が成立するならば１を出力し、成立しないならば０を出力する。
【００５０】
関数ERは、例えば、以下のような関数である。入力は、aR,eR=c,zR=r, e'R=c',z'R=r'である。そして、 W = x =(r-r')/(c'-c) mod q を計算し、W を出力する。
【００５１】
関数SRは、例えば、以下のような関数である。入力は、X,eR=c,及びランダムテープRSである。そして、RSからランダムな zR=r ∈ Z/qZ を生成し、aR = y' = gry-c を生成する。そして、(aR,zR) を出力する。
【００５２】
[非対話的知識の証明]
次に、非対話的知識の証明について説明する。上記の従来技術２では、証明装置と検証装置が対話(互いに通信)することで、証明者が検証者に、ある事例がある言語に属する事を証明した。一方、証明者が、検証者にデータを一回送るだけで、ある事例がある言語に属する事を証明する方法がある。これを非対話的証明と言う。特に、ある事例がある言語に属することを多項式時間で検証し得る証拠を保持していることを証明する場合は、非対話的知識の証明と言う。
【００５３】
非特許文献３に記された方法に従うと、特別正直検証者零知識対話証明を用いて、X に対して、(X,W) ∈ RなるR の知識があることの非対話的知識の証明の一例（PR）を次の様に構成できる。
【００５４】
PR = (aR,zR) 
【００５５】
ただし、RPはランダムテープである。また、以下の関係が成り立っているものとする。
aR = AR(X,W,RP) ,
eR = Hash(X,aR) ,
aR = AR(X,W,RP,eR).
【先行技術文献】
【非特許文献】
【００５６】
【非特許文献１】“Rafael Pass”，“ On Deniability in the Common Reference String and Random Oracle Model”，“CRYPTO 2003”，2003年，p.316-337,p316-337
【非特許文献２】“Oded Goldreich”，“Foundations of Cryptography --- Basic Tools”，“Cambridge University Press”，2001年，p.206-207
【非特許文献３】“Amos Fiat Adi Shamir”，“How to Prove Yourself: Practical Solutions to Identification and Signature Problems”，“CRYPTO 1986”，1986年，p.186-194
【発明の概要】
【発明が解決しようとする課題】
【００５７】
しかし、上記の従来技術１は、以下に示す問題を有している。
【００５８】
従来技術１では、ステップ３において、十分に大きなt に関して、t 個のコミットメント{c[1,i] と c[2.i]}i=1,...,t を生成する必要がある。この理由は次の通りである。模擬装置は、二つのコミットメント c[1,i] = Hash(x'[i],r[1,i])と c[2,i] = Hash(x'[i]+x,r[2,i])の両方の、コミットされた値x'[i] とx'[i]+x を必要とする。すなわち両方のコミットメントが正しく作られない限り、模擬装置はうまく働かない。ところが、実際の検証装置の動作では、各i に関して、片方しかコミットされた値を公開しない。それゆえ、公開しない方の値を不正に生成しておいても、証明装置に発覚しないおそれがある。このようなおそれがあるため、十分に多くのi に関して(t 個) コミットメントを生成することにより、検証装置が全てのi に関して証明装置を騙せる確率を十分に小さく(1/2t) している。
【００５９】
上記理由により、従来の技術は検証装置に数多くのコミットメント生成を要求し、ステップ６において証明装置に数多くの計算を要求する。このことにより、計算時間、両者の通信量が共に大きくなるという欠点を持っている。
【００６０】
従来技術１で説明したステップ１−５は離散対数の知識の非対話零知識証明であるが、次の離散対数の知識の非対話零知識証明と比べることで、その計算量と通信量の差がよく分かる。 
【００６１】
y=gxとする。証明装置にg,y,x が入力され、検証者（検証装置）にg,y が入力される。
【００６２】
ステップ１：証明装置は、 x' ∈ Z/qZ を選び、y'=gx'を生成する。
【００６３】
ステップ２：証明装置は、c = Hash(g,y,y')を計算する。
【００６４】
ステップ３：証明装置は、t = c x +x' mod q を計算する。
【００６５】
ステップ４：証明装置は、(t,c) を検証装置に送付する。
【００６６】
ステップ５：検証装置は、c = Hash(g,y,gty-c) が成り立つことを確認する。
【００６７】
ここで示した非対話零知識証明における通信量と計算量は、どちらも従来の技術で利用されているものの、1/t 倍程であり、大変効率的である。
【００６８】
しかし、ここで示した方式を、既に説明した従来の方式に単純に適用することはできない。なぜなら、疑似装置が、ハッシュへの入力(g,y,y')をたとえ取り出せることができても、x を求めることができないからである。
【００６９】
一方、従来技術２には、従来技術２の説明の最後に挙げたように、効率的な方法が多くのR に対して数多くあるが、零知識性を持たない。特に、否認可能零知識性を持つことはない。
【００７０】
本発明は、上記問題点に鑑みてなされたものであって、特別正直検証者零知識対話証明の方法が与えられたときに、これを利用して、通信量と計算量共に少ない否認可能零知識対話証明を行えるようにすることを目的とする。
【課題を解決するための手段】
【００７１】
本発明による証明装置は、検証装置と通信可能に接続される証明装置であって、
予め定められた第一の関係を満たす共通入力および証拠とランダムテープとに基づいて、第一の関係に関する特別正直検証者零知識対話証明の証明のコミットメントを生成する第一証明コミットメント生成装置と通信可能に接続され、第一の関係に関する共通入力および証拠とランダムテープと挑戦値とに基づいて、第一の関係に関する特別正直検証者零知識対話証明の応答を生成する第一応答生成装置と通信可能に接続され、第二の関係に関する共通入力と証明コミットメントと挑戦値と応答とに基づいて、第二の関係に関する特別正直検証者零知識対話証明の受理を表す信号または不受理を表す信号を出力する第二対話証明検証装置と通信可能に接続され、第二の関係に関する共通入力と挑戦値とランダムテープとに基づいて、第二の関係に関する証明コミットメントおよび応答を生成する模擬装置と通信可能に接続され、ハッシュ関数の計算を行うハッシュ関数の計算装置と通信可能に接続され、予め定められた第一の関係を満たす共通入力および証拠が入力される共通入力等受信手段と、第一のランダムテープおよび第二のランダムテープが入力されるランダムテープ入力手段と、検証装置から、第二の関係に関する共通入力および当該共通入力に対応する証拠の知識の非対話証明を受信する非対話証明受信手段と、非対話証明を用いて、ハッシュ関数の計算装置および第二対話証明検証装置と通信した結果により、非対話証明を受理するか否かを判定する非対話証明受理不受理判定手段と、第一のランダムテープ、第二のランダムテープ、第一の関係を満たす共通入力と証拠、および非対話証明に含まれる共通入力を用いて、模擬装置、第一証明コミットメント生成装置、ハッシュ関数の計算装置、および第一応答生成装置と通信することにより、第一の関係に関する共通入力に対する証拠の知識あるいは、第二の関係に関する共通入力に対する証拠の知識のいずれかの知識があることの知識の非対話証明を生成する証拠知識非対話証明生成手段と、証拠知識非対話証明生成手段が生成した知識の非対話証明を検証装置に送信する非対話証明送信手段とを備えたことを特徴とする。
【００７２】
非対話証明受信手段が、検証装置から、第二の関係に関する共通入力と証明コミットメントと応答とを含む非対話証明を受信し、非対話証明受理不受理判定手段が、非対話証明に含まれる第二の関係に関する共通入力および証明コミットメントをハッシュ関数の計算装置に送信し、第二の関係に関する共通入力および証明コミットメントに応じた挑戦値となるハッシュ値を計算させ、挑戦値と、非対話証明に含まれる第二の関係に関する共通入力、証明コミットメント、および応答とを、第二対話証明検証装置に送信し、第二対話証明検証装置が出力力する信号により、非対話証明を受理するか否かを判定し、証拠知識非対話証明生成手段が、第二のランダムテープにより第二の関係に関する挑戦値を生成し、第二の関係に関する共通入力、第二の関係に関する挑戦値、および第二のランダムテープを模擬装置に送信し、第二の関係に関する証明コミットメントおよび応答を生成させ、第一の関係を満たす共通入力および証拠と、第一のランダムテープとを第一証明コミットメント生成装置に送信し、第一の関係に関する証明コミットメントを生成させ、第一の関係に関する共通入力および証明コミットメントと、第二の関係に関する共通入力と、模擬装置に生成させた第二の関係に関する証明コミットメントとをハッシュ関数の計算装置に送信し、第一の関係に関する共通入力および証明コミットメントと第二の関係に関する共通入力および証明コミットメントとに応じたハッシュ値を計算させ、当該ハッシュ値と第二の関係に関する挑戦値とに基づいて第一の関係に関する挑戦値を決定し、第一の関係を満たす共通入力および証拠と、第一のランダムテープと、第一の関係に関する挑戦値とを第一応答生成装置に送信し、第一の関係に関する応答を生成させ、第一の関係に関する証明コミットメント、挑戦値、および応答と、第二の関係に関する挑戦値と、模擬装置に生成させた第二の関係に関する証明コミットメントおよび応答とを知識の非対話証明とする構成であってもよい。
【００７３】
本発明による検証装置は、上記の証明装置と通信可能に接続される検証装置であって、第一の関係に関する共通入力と証明コミットメントと挑戦値と応答とに基づいて、第一の関係に関する特別正直検証者零知識対話証明の受理を表す信号または不受理を表す信号を出力する第一対話証明検証装置と通信可能に接続され、第二の関係に関する共通入力と証明コミットメントと挑戦値と応答とに基づいて、第二の関係に関する特別正直検証者零知識対話証明の受理を表す信号または不受理を表す信号を出力する第二対話証明検証装置と通信可能に接続され、第二の関係に関する共通入力および証拠とランダムテープとに基づいて、第二の関係に関する特別正直検証者零知識対話証明の証明のコミットメントを生成する第二証明コミットメント生成装置と通信可能に接続され、第二の関係に関する共通入力および証拠とランダムテープと挑戦値とに基づいて、第二の関係に関する特別正直検証者零知識対話証明の応答を生成する第二応答生成装置と通信可能に接続され、ハッシュ関数の計算を行うハッシュ関数の計算装置と通信可能に接続され、第一の関係に関する共通入力が入力される共通入力入力手段と、第三のランダムテープとしてランダムテープRVおよびランダムテープR'V が入力されるランダムテープ入力手段と、第二の関係を満たす共通入力および証拠を、第三のランダムテープのうちのランダムテープR'V から生成する共通入力等生成手段と、共通入力等生成手段に生成された第二の関係を満たす共通入力および証拠と、第三のランダムテープのうちのランダムテープRVとを用いて、第二証明コミットメント生成装置、第二応答生成装置、およびハッシュ関数の計算装置と通信することにより、共通入力との間で第二の関係を満たすような証拠の知識の非対話証明を生成する証拠知識非対話証明生成手段と、証拠知識非対話証明生成手段によって生成された知識の非対話証明を証明装置に送信する非対話証明送信手段と、証明装置から、第一の関係に関する共通入力に対する証拠の知識あるいは、第二の関係に関する共通入力に対する証拠の知識のいずれかの知識があることの知識の非対話証明を受信する非対話証明受信手段と、第二の関係に関する共通入力と、共通入力入力手段に入力された第一の関係に関する共通入力と、非対話証明受信手段が受信した非対話証明とを用いて、第一対話証明検証装置、第二対話証明検証装置、およびハッシュ関数の計算装置と通信を行うことによって、非対話証明受信手段が受信した非対話証明を受理するか否かの判定を行い、その判定結果を出力する判定手段とを備えたことを特徴とする。
【００７４】
証拠知識非対話証明生成手段が、第二の関係を満たす共通入力および証拠と、第三のランダムテープのうちのランダムテープRVとを第二証明コミットメント生成装置に送信し、第二の関係に関する証明コミットメントを生成させ、第二の関係に関する共通入力と第二の関係に関する証明コミットメントをハッシュ関数の計算装置に送信し、共通入力および証明コミットメントに応じた挑戦値となるハッシュ値を計算させ、第二の関係を満たす共通入力および証拠と、ランダムテープRVと、挑戦値とを、第二応答生成装置に送信し、第二の関係に関する応答を生成させ、第二の関係に関する共通入力、証明コミットメント、および応答を、知識の非対話証明とし、非対話証明受信手段が、証明装置から、第一の関係に関する証明コミットメント、挑戦値、および応答と、第二の関係に関する証明コミットメント、挑戦値、および応答とを含む非対話証明を受信し、判定手段が、共通入力入力手段に入力された第一の関係に関する共通入力と、非対話証明に含まれる第一の関係に関する証明コミットメント、挑戦値、および応答とを、第一対話証明検証装置に送信し、第一対話証明検証装置が出力する信号を受信し、第二の関係に関する共通入力と、非対話証明に含まれる第二の関係に関する証明コミットメント、挑戦値、および応答とを、第二対話証明検証装置に送信し、第二対話証明検証装置が出力する信号を受信し、第一の関係に関する共通入力および証明コミットメントと第二の関係に関する共通入力および証明コミットメントとをハッシュ関数の計算装置に送信して、第一の関係に関する共通入力および証明コミットメントと第二の関係に関する共通入力および証明コミットメントとに応じたハッシュ値を計算させ、当該ハッシュ値と非対話証明に含まれる第一の関係に関する挑戦値および第二の関係に関する挑戦値との間に所定の関係が成立しているか否かを判定し、その判定の結果と、第一対話証明検証装置および第二対話証明検証装置から受信した信号とに基づいて、非対話証明を受理するか否かを判定する構成であってもよい。
【発明の効果】
【００７５】
本発明によれば、通信量と計算量共に少ない否認可能零知識対話証明を実現することができる。
【図面の簡単な説明】
【００７６】
【図１】本発明の第１の実施の形態の証明装置および検証装置を示す説明図である。
【図２】本発明の第２の実施の形態の証明装置および検証装置を示す説明図である。
【図３】本発明の実施例を示す説明図である。
【図４】非特許文献１に記載される構成を示す説明図である。
【図５】非特許文献２に記載される構成を示す説明図である。
【図６】非特許文献２に記載される構成を示す説明図である。
【発明を実施するための形態】
【００７７】
以下、本発明の実施の形態を図面を参照して説明する。
【００７８】
以下の説明では、挑戦値のコミットメントに言及するが、この「コミットメント」と、既に説明した「証明コミットメント」とは異なるものである。そこで、まず、「コミットメント」について説明する。「Ｕ（例えば、挑戦値）のコミットメント」とは、以下の性質を有するデータである。すなわち、「Ｕのコミットメントのみが与えられても、Ｕに関する情報が何も得られず、Ｕのコミットメントを生成したものは、後にこれがＵのコミットメントであることを証明することができる。」という性質を有し、そして、「いかなるＵ’≠Ｕに関してもＵ’のコミットメントであることを証明できない。」という性質を有するデータである。以下の説明で言及する「挑戦値のコミットメント」も、この性質を有する。
【００７９】
実施の形態１．
図１は、本発明の第１の実施の形態の証明装置および検証装置を示す説明図である。証明装置３０１および検証装置３０２は、互いに通信可能となるように接続されている。証明装置３０１には、(X,W) ∈ Rなる共通入力X 、証拠W 、および第一のランダムテープRPが入力される。この関係R は、予め定められた関係である。本実施の形態では、便宜的に、関係R のことを第一の関係と呼ぶことにする。
【００８０】
なお、共通入力は、証明装置および検証装置に共通に入力されるデータである。ただし、後述する第２の実施の形態では、検証装置が共通入力となるデータ（第２の実施の形態におけるX'）を生成し、証明装置に送信する場合も示す。このように、検証装置が生成し、証明装置に送信するデータも共通入力となる。
【００８１】
証明装置３０１は、第一の関係に関する挑戦値のコミットメント検証装置３２４（以下、挑戦値のコミットメント検証装置３２４と記す。）と、対話的な、第一の関係に関する知識の証明生成装置３３０（以下、証明生成装置３３０と記す。）とを備える。
【００８２】
検証装置３１２は、第一の関係に関する挑戦値のコミットメント生成装置３１２（以下、挑戦値のコミットメント生成装置３１２と記す。）と、対話的な、第一の関係に関する知識の証明検証装置３４０（以下、証明検証装置３４０と記す。）とを備える。
【００８３】
挑戦値のコミットメント検証装置３２４は、ハッシュ関数の計算装置３１０と通信可能に接続される。また、証明生成装置３３０は、第一の関係R に関する特別正直検証者零知識対話証明の証明コミットメント生成装置３０３（以下、証明コミットメント生成装置３０３と記す。）と通信可能に接続される。また、証明生成装置３３０は、第一の関係R に関する特別正直検証者零知識対話証明の応答生成３０４（以下、応答生成装置３０４と記す。）と通信可能に接続される。
【００８４】
挑戦値のコミットメント生成装置３１２は、ハッシュ関数の計算装置３１１と通信可能に接続される。証明検証装置３４０は、第一の関係R に関する特別正直検証者零知識対話証明の検証装置３０５（以下、対話証明検証装置３０５と記す。）と通信可能に接続される。
【００８５】
証明コミットメント生成装置３０３は、関数（関数ARとする。）に従って、証明生成装置３３０からの入力に応じた証明コミットメントを生成し、証明生成装置３３０に出力する。なお、本実施の形態における関数ARの具体的な計算例は、例えば、従来技術２で示した関数ARと同様である。
【００８６】
応答生成装置３０４は、関数（関数ZRとする。）に従って、証明生成装置３３０からの入力に応じた応答を生成し、証明生成装置３３０に出力する。なお、本実施の形態における関数ZRの具体的な計算例は、例えば、従来技術２で示した関数ZRと同様である。
【００８７】
対話証明検証装置３０５は、関数（関数VRとする。）に従って、証明検証装置３４０からの入力に応じた検証結果を生成し、証明検証装置３４０に出力する。なお、本実施の形態における関数VRの具体的な計算例は、例えば、従来技術２で示した関数VRと同様である。なお、検証結果が１であれば、証明の受理を表し、検証結果が０であれば、証明の不受理を表すものとする。
【００８８】
挑戦値のコミットメント検証装置３２４には、挑戦値のコミットメント生成装置３１２から、挑戦値のコミットメント（c とする。）が入力される。挑戦値のコミットメント検証装置３２４は、証明検証装置３４０が証明生成装置３３０に対して出力する挑戦値および乱数を用いたハッシュ関数の計算結果が、挑戦値のコミットメントc と一致するか否かを判定する。
【００８９】
証明生成装置３３０には、前述の共通入力X 、証拠W 、および第一のランダムテープRPが入力される。また、証明生成装置３３０は、証明コミットメント生成装置３０３に生成させた証明コミットメントを、証明検証装置３４０に出力する。その後、証明生成装置３３０には、証明検証装置３４０から、挑戦値および乱数が入力される。挑戦値および乱数を用いたハッシュ関数の計算結果が、挑戦値のコミットメントc と一致していた場合には、証明生成装置３３０は、応答生成装置３０４に生成させた応答を証明検証装置３４０に出力する。
【００９０】
挑戦値のコミットメント生成装置３１２には、共通入力X 、および第二のランダムテープRVが入力される。そして、挑戦値のコミットメント生成装置３１２は、挑戦値、乱数を生成し、ハッシュ関数の計算装置３１１に挑戦値のコミットメントc を生成させる。挑戦値のコミットメント生成装置３１２は、挑戦値のコミットメントc を挑戦値のコミットメント検証装置３２４に出力する。
【００９１】
証明検証装置３４０には、証明生成装置３３０から証明コミットメントが入力される。その後、証明検証装置３４０は、挑戦値および乱数を証明生成装置３３０を出力する。そして、証明生成装置３３０から応答が入力される。証明検証装置３４０は、応答を受けると、対話証明検証装置３０５に検証結果を生成させ、その検証結果３２２を出力する。
【００９２】
なお、図１では、符号３０６を用いて共通入力X を示している。また、符号３０７を用いて証拠W を示している。また、符号３０８を用いて第一のランダムテープRPを示している。また、符号３０９を用いて第二のランダムテープRVを示している。
【００９３】
次に、証明装置３０１と検証装置３０２とによる関係R の否認可能零知識対話証明の動作について説明する。
【００９４】
まず、証明装置３０１の証明生成装置３３０に、(X,W) ∈ Rなる共通入力X 、証拠W 、および第一のランダムテープRPが入力される。
【００９５】
続いて、検証装置３０２が備える挑戦値のコミットメント生成装置３１２に、共通入力X 、および第二のランダムテープRVが入力される。
【００９６】
次に、挑戦値のコミットメント生成装置３１２は、以下のようにして、第一の関係R に関する挑戦値のコミットメントを、ハッシュ関数の計算装置３１１に生成させる。挑戦値のコミットメント生成装置３１２は、第二のランダムテープRVを用いて、挑戦値eRを選ぶ。また、挑戦値のコミットメント生成装置３１２は、第二のランダムテープRVを用いて、乱数r を選ぶ。この乱数r は、挑戦値のコミットメントの証拠となっている。挑戦値のコミットメント生成装置３１２は、挑戦値eRおよび乱数r をハッシュ関数の計算装置３１１に送信する。ハッシュ関数の計算装置３１１は、c = Hash(eR,r)として、挑戦値のコミットメントc を計算し、挑戦値のコミットメントc を挑戦値のコミットメント生成装置３１２に送信する。このときの通信を、図１では、通信３１３として示している。
【００９７】
挑戦値のコミットメント生成装置３１２は、ハッシュ関数の計算装置３１１から受信した挑戦値のコミットメントc を、挑戦値のコミットメント検証装置３２４に送信する（図１に示す通信３１４）。なお、挑戦値のコミットメント検証装置３２４は、挑戦値のコミットメント生成装置３１２から挑戦値のコミットメントc が送信されてくるのを待ち、挑戦値のコミットメント生成装置３１２から挑戦値のコミットメントc を受信する。
【００９８】
挑戦値のコミットメント検証装置３２４が挑戦値のコミットメントc を受信すると、証明生成装置３３０は、共通入力X 、証拠W 、および第一のランダムテープRPを、証明コミットメント生成装置３０３に送信する。証明コミットメント生成装置３０３は、関数ARによって、aR =AR(x,w,RP)として、証明コミットメントaRを生成する。そして、証明コミットメント生成装置３０３は、証明コミットメントaRを証明生成装置３３０に送信する。このときの通信を、図１では、通信３１５として示している。
【００９９】
証明生成装置３３０は、証明コミットメント生成装置３０３から受信した証明コミットメントaRを証明検証装置３４０に送信する（図１に示す通信３１６）。証明生成装置３３０は、証明コミットメントaRを送信した後、証明検証装置３４０から、挑戦値のコミットメントc によりコミットされた挑戦値およびそのコミットメントの証拠（乱数r ）が送信されてくるのを待つ。
【０１００】
証明検証装置３４０は、証明コミットメントaRを受信した後、挑戦値eRおよび乱数r を証明生成装置３３０に送信する（図１に示す通信３１７）。証明検証装置３４０は、挑戦値eRおよび乱数r を送信した後、証明生成装置３３０から応答が送信されてくるのを待つ。
【０１０１】
証明生成装置３３０が挑戦値eRおよび乱数r を受信すると、挑戦値のコミットメント検証装置３２４は、ハッシュ関数の計算装置３１０と通信を行い（図１に示す通信３１９）、挑戦値eRおよび乱数をr を用いたハッシュ関数の計算結果が、挑戦値のコミットメントc と一致するか否かを判定する。すなわち、ハッシュ関数の計算装置３１０に、Hash(eR,r)を計算させ、その計算結果が、既に受信している挑戦値のコミットメントc と一致するか否かを判定する。換言すると、既に受信している挑戦値のコミットメントc が挑戦値eRのコミットメントであるか否かを、乱数r を用いて検証する。
【０１０２】
c = Hash(eR,r)が成立していないならば、挑戦値のコミットメント検証装置３２４は、証明装置３０１の停止命令を証明生成装置３３０に出力する（図１に示す出力３２５）。停止命令が出力された場合、証明装置３０１は動作を停止する。なお、c = Hash(eR,r)が成立しているならば、停止命令を出力しない。
【０１０３】
停止命令が出力されなかった場合、証明生成装置３３０は、共通入力X 、証拠W 、挑戦値eR、および第一のランダムテープRPを、応答生成装置３０４に送信する。応答生成装置３０４は、関数ZRによって、zR =ZR(x,w,eR,RP) として、応答zRを生成する。そして、応答生成装置３０４は、応答zRを証明生成装置３３０に送信する。このときの通信を、図１では、通信３２０として示している。
【０１０４】
証明生成装置３３０は、応答生成装置３０４から受信した応答zRを証明検証装置３４０に送信する（図１に示す通信３１８）。
【０１０５】
証明検証装置３４０は、応答zRを受信すると、共通入力X 、証明コミットメントaR、挑戦値eR、および応答zRを、対話証明検証装置３０５に送信する。なお、証明検証装置３４０は、挑戦値のコミットメント生成装置３１２から挑戦値eRを受信すればよい（図１に示す通信３２６）。対話証明検証装置３０５は、関数VRによって、VR(X,aR,eR,zR)の計算結果を導出する。この計算結果は、例えば、１か０かのいずれかとなり、証明の受理あるいは不受理を表す。対話証明検証装置３０５は、証明の受理あるいは不受理を表す信号を証明検証装置３４０に送信する。このときの通信を、図１では、通信３２１として示している。
【０１０６】
証明検証装置３４０は、受信した信号（証明の受理あるいは不受理を表す信号）を、検証結果３２２として出力する。
【０１０７】
第１の実施の形態によれば、検証装置３０２から証明装置３０１への送信は、挑戦値のコミットメントc の送信（図１に示す通信３１４）、および、そのコミットメントが挑戦値のコミットメントであることを示すデータの送信（図１に示す通信３１７）のみである。よって、通信量が少なくて済み、方式を簡易化し、通信を効率化することができる。
【０１０８】
第１の実施の形態において、証明装置が備える共通入力等入力手段、ランダムテープ入力手段、証明コミットメント生成制御手段、挑戦値等受信手段、および応答生成制御手段は、証明装置３０１の証明生成装置３３０によって実現される。また、証明装置が備える挑戦値コミットメント受信手段、挑戦値コミットメント検証手段は、証明装置３０１の挑戦値のコミットメント検証装置３２４によって実現される。
【０１０９】
そして、検証装置が備える共通入力入力手段、ランダムテープ入力手段、挑戦値生成手段、乱数生成手段、挑戦値コミットメント生成制御手段は、検証装置３０２の挑戦値のコミットメント生成装置３１２によって実現される。また、検証装置が備える証明コミットメント受信手段、応答受信手段、検証結果出力手段は、検証装置３０３の証明検証装置３４０によって実現される。
【０１１０】
実施の形態２．
以下の説明では、ビット毎の排他的論理和を符号∨によって表すものとする。
【０１１１】
図２は、本発明の第２の実施の形態の証明装置および検証装置を示す説明図である。証明装置４０１および検証装置４０２は、互いに通信可能となるように接続されている。証明装置４０１には、(X,W) ∈ Rなる共通入力X、証拠W、第一のランダムテープRP、第二のランダムテープR'Pが入力される。この関係R は、予め定められた関係であり、以下、第一の関係と呼ぶ。なお、第一の関係R とは別の第二の関係をR'とする。
【０１１２】
証明装置４０１は、第二の関係に関する非対話的知識の証明検証装置４２３（以下、第二関係証明検証装置４２３と記す。）と、非対話的な、第一の関係を満たす証拠、あるいは第二の関係を満たす証拠のいずれかの証拠の知識の証明生成装置４２５（以下、証明生成装置４２５と記す。）とを備える。
【０１１３】
検証装置４０２は、第二の関係に関する非対話的知識の証明生成装置４１７（以下、第二関係証明生成装置４１７と記す。）と、非対話的な、第一の関係を満たす知識、あるいは第二の関係を満たす知識のいずれかの知識の証明検証装置４３４（以下、証明検証装置４３４と記す。）とを備える。
【０１１４】
第二関係証明検証装置４２３は、ハッシュ関数の計算装置４１０と通信可能に接続される。また、第二関係証明検証装置４２３は、第二の関係R'に関する特別正直検証者零知識対話証明の検証装置４０８（以下、第二対話証明検証装置４０８と記す。）とも通信可能に接続されている。
【０１１５】
証明生成装置４２５は、ハッシュ関数の計算装置４１０と通信可能に接続される。また、証明生成装置４２５は、第一の関係R に関する特別正直検証者零知識対話証明の証明コミットメント生成装置４０３（以下、第一証明コミットメント生成装置４０３と記す。）と通信可能に接続される。また、証明生成装置４２５は、第一の関係R に関する特別正直検証者零知識対話証明の応答生成装置４０４（以下、第一応答生成装置４０４と記す。）と通信可能に接続される。さらに、証明生成装置４２５は、第二の関係R'に関する特別正直検証者零知識対話証明の模擬装置４０９（以下、第二関係模擬装置４０９と記す。）と通信可能に接続される。
【０１１６】
第二関係証明生成装置４１７は、ハッシュ関数の計算装置４１１と通信可能に接続される。また、第二関係証明生成装置４１７は、第二の関係R' に関する特別正直検証者零知識対話証明の証明コミットメント生成装置４０６（以下、第二証明コミットメント生成装置４０６）と通信可能に接続される。さらに、第二関係証明生成装置４１７は、第二の関係R'に関する特別正直検証者零知識対話証明の応答生成装置４０７（以下、第二応答生成装置４０７）と通信可能に接続される。
【０１１７】
証明検証装置４３４は、ハッシュ関数の計算装置４１１と通信可能に接続される。また、証明検証装置４３４は、第一の関係R に関する特別正直検証者零知識対話証明の検証装置４０５（以下、第一対話証明検証装置４０５と記す。）と通信可能に接続される。さらに、証明検証装置４３４は、第二対話証明検証装置４０８と通信可能に接続される。
【０１１８】
第一証明コミットメント生成装置４０３は、関数（関数ARとする。）に従って、証明生成装置４２５からの入力に応じた証明コミットメントを生成し、証明生成装置４２５に出力する。なお、本実施の形態における関数ARの具体的な計算例は、例えば、従来技術２で示した関数ARと同様である。
【０１１９】
第一応答生成装置４０４は、関数（関数ZRとする。）に従って、証明生成装置４２５からの入力に応じた応答を生成し、証明生成装置４２５に出力する。なお、本実施の形態における関数ZRの具体的な計算例は、例えば、従来技術２で示した関数ZRと同様である。
【０１２０】
第一対話証明検証装置４０５は、関数（関数VRとする。）に従って、証明検証装置４３４からの入力に応じた検証結果（証明の受理あるいは不受理を表す信号）を生成し、証明検証装置４３４に出力する。なお、本実施の形態における関数VRの具体的な計算例は、例えば、従来技術２で示した関数VRと同様である。なお、検証結果が１であれば、証明の受理を表し、検証結果が０であれば、証明の不受理を表すものとする。
【０１２１】
第二証明コミットメント生成装置４０６は、関数（関数AR’ とする。）に従って、第二関係証明生成装置４１７からの入力に応じた証明コミットメント（aR'とする。）を生成し、第二関係証明生成装置４１７に出力する。関数AR’ は、共通入力、証拠、ランダムテープを入力とし、証明コミットメントを出力する関数である。ここでは、関数AR’ が関数ARとは異なる計算を行う関数であるものとして説明するが、第一の関係R と第二の関係R’とが同じ関係であるならば、関数AR’ が関数ARと同様の計算を行う関数であってもよい。
【０１２２】
第二応答生成装置４０７は、関数（関数ZR’ とする。）に従って、第二関係証明生成装置４１７からの入力に応じた応答を生成し、第二関係証明生成装置４１７に出力する。関数ZR’ は、共通入力、証拠、挑戦値、およびランダムテープを入力とし、応答（zR'とする。）を出力する関数である。ここでは、関数ZR’ が関数ZRとは異なる計算を行う関数であるものとして説明するが、第一の関係R と第二の関係R’とが同じ関係であるならば、関数ZR’ が関数ZRと同様の計算を行う関数であってもよい。
【０１２３】
第二対話証明検証装置４０８は、関数（関数VR’ とする。）に従って、第二関係証明検証装置４２３や証明検証装置４３４からの入力に応じた検証結果（証明の受理あるいは不受理を表す信号）を生成し、第二関係証明検証装置４２３や証明検証装置４３４にその検証結果を出力する。関数VR’ は、証明コミットメント、応答、共通入力、挑戦値を入力とし、検証結果を出力する関数である。ここでは、関数VR’ が関数VRとは異なる計算を行う関数であるものとして説明するが、第一の関係R と第二の関係R’とが同じ関係であるならば、関数VR’ が関数VRと同様の計算を行う関数であってもよい。なお、検証結果が１であれば、証明の受理を表し、検証結果が０であれば、証明の不受理を表すものとする。
【０１２４】
第二関係模擬装置４０９は、関数（関数SR’ とする。）に従って、証明生成装置４２５からの入力に応じた証明コミットメントおよび応答を出力する。関数SR’ は、共通入力、挑戦値、およびランダムテープを入力とし、証明コミットメントおよび応答を出力する関数である。本実施の形態における関数SR’ の具体的な計算例は、例えば、従来技術２で示した関数SRと同様である。
【０１２５】
第二関係証明生成装置４１７には、共通入力X と第三のランダムテープが入力される。なお、第三のランダムテープとしては、RVおよびR'V が入力される。また、第二関係証明生成装置４１７は、第二の関係R'に関する非対話的知識の証明（PR' とする。）を第二関係証明検証装置４２３に出力する。
【０１２６】
第二関係証明検証装置４２３は、第二の関係R'に関する非対話的知識の証明PR' を用いて、所定の関係式が成立しているか否かを判定する。
【０１２７】
証明生成装置４２５には、前述の共通入力X、証拠W、第一のランダムテープRP、第二のランダムテープR'Pが入力される。そして、非対話的な、第一の関係を満たす証拠、あるいは第二の関係を満たす証拠のいずれかの証拠の知識の証明（PR∨R'とする。）を生成し、その証明を証明検証装置４３４に出力する。
【０１２８】
証明検証装置４３４は、第一対話証明検証装置４０５および第二対話証明検証装置４０８との通信結果に基づいて、証明PR∨R'の受理または不受理を表す信号を検証結果４３５として出力する。
【０１２９】
なお、図２では、符号４１２を用いて共通入力X を示している。また、符号４１３を用いて証拠W を示している。また、符号４１４を用いて第一のランダムテープRPを示している。また、符号４１５を用いて第二のランダムテープR'P を示している。また、符号４１６を用いて第三のランダムテープRVおよびR'V を示している。
【０１３０】
次に、証明装置４０１と検証装置４０２とによる関係R の否認可能零知識対話証明の動作について説明する。
【０１３１】
まず、証明装置４０１の証明生成装置４２５に、(X,W) ∈ Rなる共通入力X 、証拠W 、第一のランダムテープRP、および第二のランダムテープR'Pが入力される。
【０１３２】
続いて、検証装置４０２の第二関係証明生成装置４１７に、共通入力X 及び第三のランダムテープRVおよびR'V が入力される。
【０１３３】
次に、第二関係証明生成装置４１７は、以下のようにして、第二の関係R'に関する非対話的知識の証明PR' を生成する。
【０１３４】
第二関係証明生成装置４１７は、一様無作為に、(X',W') ∈ R' なるX',W' （第二の関係R'に関する共通入力および証拠）を、第三のランダムテープのうちのR'V を用いて生成する。
【０１３５】
次に、第二関係証明生成装置４１７は、共通入力X'、証拠W'、第三のランダムテープのうちのRVを第二証明コミットメント生成装置４０６に送信する。第二証明コミットメント生成装置４０６は、関数AR’ によって、aR'=AR'(X',W', RV)として、証明コミットメントaR' を生成する。そして、第二証明コミットメント生成装置４０６は、証明コミットメントaR' を第二関係証明生成装置４１７に送信する。このときの通信を、図２では、通信４１８として示している。
【０１３６】
次に、第二関係証明生成装置４１７は、共通入力X'、証明コミットメントaR' をハッシュ関数の計算装置４１１に送信する。ハッシュ関数の計算装置４１１は、eR' =Hash(X',aR') としてハッシュ値を計算する。ハッシュ関数の計算装置４１１は、ハッシュ値eR' を第二関係証明生成装置４１７に送信する。このときの通信を、図２では、通信４１９として示している。
【０１３７】
次に、第二関係証明生成装置４１７は、共通入力X'、証拠W'、ハッシュ値eR' 、および第三のランダムテープのうちのRVを第二応答生成装置４０７に送信する。ここでは、ハッシュ値eR' を挑戦値として送信する。第二応答生成装置４０７は、関数ZR’ によって、zR' =ZR'(X',W',eR', RV)として、応答zR'を生成する。第二応答生成装置４０７は、応答zR'を第二関係証明生成装置４１７に送信する。このときの通信を、図２では、通信４２０として示している。
【０１３８】
第二関係証明生成装置４１７は、第二の関係R'に関する非対話的知識の証明PR'を(X',aR',zR') とする。第二関係証明生成装置４１７は、以上のようにして生成した証明PR'=(X',aR',zR')を、第二関係証明検証装置４２３に送信する（図２に示す通信４２１）。
【０１３９】
なお、第二関係証明検証装置４２３は、証明PR'（第二の関係R’に関する共通入力X'とその共通入力X'に対応する証拠W'の知識の非対話証明）が送信されてくるのを待ち、上記の通信４２１で、第二関係証明生成装置４１７をから証明PR'=(X',aR',zR')を受信する。
【０１４０】
証明装置４０１の第二関係証明検証装置４２３は、以下のようにして、第二の関係R' に関する非対話的知識の証明 PR'を検証する。
【０１４１】
第二関係証明検証装置４２３は、共通入力X'、証明コミットメントaR' をハッシュ関数の計算装置４１０に送信する。ハッシュ関数の計算装置４１０は、eR' = Hash(X',aR')  としてハッシュ値を計算する。ハッシュ関数の計算装置４１０は、ハッシュ値eR'を第二関係証明検証装置４２３に送信する。このときの通信を、図２では、通信４２２として示している。
【０１４２】
第二関係証明検証装置４２３は、共通入力X'、証明コミットメントaR' 、ハッシュ値eR'、応答zR'を第二対話証明検証装置４０８に送信する。ここでは、ハッシュ値eR' を挑戦値として送信する。第二対話証明検証装置４０８は、関数VR’ によって、VR'(X',aR',eR',zR')の計算結果を導出し、その計算結果を第二関係証明検証装置４２３に送信する。このときの通信を、図２では、通信４２４として示している。
【０１４３】
第二関係証明検証装置４２３は、VR'(X',aR',eR',zR')=1が成り立つか否かを判定する。成り立っていないならば、証明装置４０１を停止する。また、成り立っているならば、証明装置４０１は、次に示す動作を行う。すなわち、VR'(X',aR',eR',zR')=1が成立していれば、証明 PR'を受理とし、成立していなければ証明 PR'を不受理とする。
【０１４４】
証明装置４０１の証明生成装置４２５は、以下のようにして、第一の関係R を満す証拠あるいは第二の関 係R' を満す証拠の、いずれかの証拠に関する知識の非対話的知識の証明PR∨R'を生成する。
【０１４５】
証明生成装置４２５は、第二のランダムテープR'Pを用いて乱数e'R'を生成し、これを第二の関係R'に関する挑戦値とする。
【０１４６】
次に、証明生成装置４２５は、共通入力X'、挑戦値e'R'、および第二のランダムテープR'Pを第二関係模擬装置４０９に送信して、第二関係模擬装置４０９に第二の関係R'に関する証明コミットメントa'R'と応答z'R'を生成させる。第二関係模擬装置４０９は、関数SR’ によって、(a'R',z'R') =SR'(X',e'R',R'P)を導出し、証明コミットメントa'R'と応答z'R'を証明生成装置４２５に送信する。このときの通信を、図２では、通信４２６として示している。
【０１４７】
次に、証明生成装置４２５は、共通入力X 、証拠W 、および第一のランダムテープRPを第一証明コミットメント生成装置４０３に送信する。第一証明コミットメント生成装置４０３は、関数ARによって、aR=AR(X,W,RP)として、証明コミットメントaRを生成し、証明生成装置４２５に送信する。このときの通信を、図２では、通信４２７として示している。
【０１４８】
次に、証明生成装置４２５は、第一の関係R に関する共通入力X 、証明コミットメントaR、第二の関係R'に関する共通入力X'、証明コミットメントa'R'を、ハッシュ関数の計算装置４１０に送信する。ハッシュ関数の計算装置４１０は、e = Hash(X,aR,X',a'R')としてハッシュ値e を計算し、そのハッシュ値を証明生成装置４２５に送信する。このときの通信を、図２では、通信４２８として示している。
【０１４９】
次に、証明生成装置４２５は、eR= e ∨ e'R'として、挑戦値eRを計算する。証明生成装置４２５は、共通入力X 、証拠W 、挑戦値eR、および第一のランダムテープRPを第一応答生成装置４０４に送信し、応答zRを生成させる。第一応答生成装置４０４は、関数ZRによって、zR=ZR(X,W,eR,RP)として、応答zRを生成し、応答zRを証明生成装置４２５に送信する。このときの通信を、図２では、通信４２９として示している。
【０１５０】
証明生成装置４２５は、第一の関係R を満す証拠あるいは第二の関係R'を満す証拠の、いずれかの証拠に関する知識の非対話的知識の証明 PR∨R' を(aR,eR,zR, a'R',e'R',z'R') とする。証明生成装置４２５は、以上のようにして生成した証明PR∨R'= (aR,eR,zR, a'R',e'R',z'R')を、検証装置４０２の証明検証装置４３４に送信する（図２に示す通信４２９）。
【０１５１】
証明検証装置４３４は、共通入力X （検証装置４０２に入力された共通入力X）、証明コミットメントaR、共通入力X'、および証明コミットメントa'R'をハッシュ関数の計算装置４１１に送信し、ハッシュ値を計算させる。ハッシュ関数の計算装置４１１は、Hash(X,aR,X',a'R')の計算結果を導出し、その計算結果（ハッシュ値）を証明検証装置４３４に送信する。このときの通信を、図２では、通信４３０として示している。そして、証明検証装置４３４は、Hash(X,aR,X',a'R')の計算結果が、eR∨e'R'と等しくなっているか否かを判定する。
【０１５２】
次に、証明検証装置４３４は、共通入力X 、証明コミットメントaR、挑戦値eR、応答zRを第一対話証明検証装置４０５に送信する。第一対話証明検証装置４０５は、関数VRによって、VR(X,aR,eR,zR)の計算結果を導出し、その計算結果を証明検証装置４３４に送信する。このときの通信を、図２では、通信４３２として示している。証明検証装置４３４は、VR(X,aR,eR,zR)=1が成立しているか否かを判定する。
【０１５３】
次に、証明検証装置４３４は、共通入力X'、証明コミットメントa'R'、挑戦値e'R'、応答z'R'を第二対話証明検証装置４０８に送信する。第二対話証明検証装置４０８は、関数VR’ によって、VR'(X',a'R',e'R',z'R')の計算結果を導出し、その計算結果を証明検証装置４３４に送信する。このときの通信を、図２では、通信４３１として示している。証明検証装置４３４は、VR'(X',a'R',e'R',z'R')=1が成立しているか否かを判定する。
【０１５４】
証明検証装置４３４は、上記の各判定が全て成立している場合、すなわち、Hash(X,aR,X',a'R')=eR∨e'R'、VR(X,aR,eR,zR)=1、およびVR'(X',a'R',e'R',z'R')=1が全て成立している場合、“１”を検証結果４３５として出力する。その他の場合、証明検証装置４３４は、“０”を検証結果４３５として出力する。上記の“１”は、証明 PR∨R' を受理することを表す。また、上記の“０”は、証明 PR∨R' を受理しないことを表す。
【０１５５】
第２の実施の形態によれば、検証装置４０２から証明装置４０１に送信する通信量が少なくて済み、通信量や計算量を抑えることができる。例えば、図４に示す従来技術１では、検証装置から証明装置に2t個のc[1,i]、c[2,i]を送信している。それに対し、第２の実施の形態では、検証装置４０２は、証明装置４０１に対して証明PR’を送信しているのみである。このように、本発明によれば、通信量や計算量を抑えることができる。
【０１５６】
第２の実施の形態において、証明装置が備える非対話証明受信手段、非対話証明受理不受理判定手段は、証明装置４０２の第二関係証明検証装置４２３によって実現される。また、証明装置が備える共通入力等受信手段、ランダムテープ入力手段、証拠知識非対話証明生成手段、非対話証明送信手段は、証明装置４０２の証明生成装置４２５によって実現される。
【０１５７】
そして、検証装置が備える共通入力入力手段、ランダムテープ入力手段、共通入力等生成手段、証拠知識非対話証明生成手段、非対話証明送信手段は、検証装置４０２の第二関係証明生成装置４１７によって実現される。また、検証装置が備える非対話証明受信手段、判定手段は、検証装置４０２の証明検証装置４３４によって実現される。
【０１５８】
本発明によれば、特別正直検証者零知識対話証明が存在すれば否認可能零知識対話証明を行なうことが可能であり、特にその計算量と通信量に関する効率を従来技術１と比較して著しく高めることができる。
【０１５９】
また、本発明によれば、証明装置が、検証装置と通信を行った事実を、いかなる検証装置も証明することができないため、効率的な否認不可署名、否認可能証明、レシートフリー電子投票を実現することができる。
【０１６０】
また、上記の各実施の形態において、証明装置、検証装置を、それぞれプログラムに従って動作するコンピュータによって実現してもよい。
【０１６１】
なお、上記の各実施の形態では、証明を受理する場合を“１”で表し、受理しない場合を“０”で表すようにしているが、逆であってもよい。
【実施例１】
【０１６２】
以下、第２の実施の形態の実施例について説明する。図３は、本発明の第２の形態の実施例を示す説明図である。本実施例では、第一の関係R と第二の関係R'として両方とも同じ離散対数の関係を用いる場合を例にして説明する。そして、本実施例の実現は、否認可能認証となっている。ここでは、証明装置が検証装置による認証を受ける。
【０１６３】
図３に示す証明装置５０１は、第２の実施の形態における証明装置４０１に相当し、図３に検証装置５０２は、第２の実施の形態における検証装置４０２に相当する。
【０１６４】
証明装置５０１は、第二の関係に関する非対話的知識の証明検証装置５２３（以下、第二関係証明検証装置５２３と記す。）と、非対話的な、第一の関係を満たす証拠、あるいは第二の関係を満たす証拠のいずれかの証拠の知識の証明生成装置５２５（以下、証明生成装置５２５と記す。）とを備える。これらは、それぞれ、第二の実施の形態における証明検証装置４２３、証明生成装置４２５に相当する。
【０１６５】
検証装置５０２は、第二の関係に関する非対話的知識の証明生成装置５１７（以下、第二関係証明生成装置５１７と記す。）と、非対話的な、第一の関係を満たす知識、あるいは第二の関係を満たす知識のいずれかの知識の証明検証装置５３４（以下、証明検証装置５３４と記す。）とを備える。これらは、それぞれ、第二の実施の形態における第二関係証明生成装置４１７、証明検証装置４３４に相当する。
【０１６６】
また、図３に示すハッシュ関数の計算装置５１０，５１１は、それぞれ第２の実施の形態におけるハッシュ関数の計算装置４１０，４１１に相当する。
【０１６７】
また、図３では、符号５１２を用いて共通入力X を示している。また、符号５１３を用いて証拠W を示している。また、符号５１４を用いて第一のランダムテープRPを示している。また、符号５１５を用いて第二のランダムテープR'P を示している。また、符号５１６を用いて第三のランダムテープRVおよびR'V を示している。
【０１６８】
本実施例では、第一の関係R と第二の関係R'として両方とも同じ離散対数の関係を用いる。従って、第２の実施の形態における第一証明コミットメント生成装置４０３および第二証明コミットメント生成装置４０６を、同一の装置で実現している。この装置は、図３に示す離散対数の関係に関する特別正直検証者零知識対話証明の証明コミットメント生成装置５０３（以下、証明コミットメント生成装置５０３と記す。）である。証明コミットメント生成装置５０３は、関数ARによって、証明コミットメントを生成する。
【０１６９】
同様に、本実施例では、第２の実施の形態における第一応答生成装置４０４および第二応答生成装置４０７を、同一の装置で実現している。この装置は、図３に示す離散対数の関係に関する特別正直検証者零知識対話証明の応答生成装置５０４（以下、応答生成装置５０４と記す。）である。応答生成装置５０４は、関数ZRによって、応答を生成する。
【０１７０】
同様に、本実施例では、第２の実施の形態における第一対話証明検証装置４０５および第二対話証明検証装置４０８を、同一の装置で実現している。この装置は、図３に示す離散対数の関係に関する特別正直検証者零知識対話証明の検証装置５０５（以下、対話証明検証装置５０５と記す。）である。対話証明検証装置５０５は、関数VRによって、検証結果を導出する。
【０１７１】
また、図３に示す離散対数の関係に関する特別正直検証者零知識対話証明の模擬装置５０９（以下、模擬装置５０９と記す。）は、第二の実施の形態における第二関係模擬装置４０９に相当する。模擬装置５０９は、関数SR’ を用いて、証明コミットメントおよび応答を生成する。
【０１７２】
以下に本実施例における関数AR、関数ZR、関数VR、関数SR’ について説明する。なお、本実施例では用いないが、補足として、従来技術２における関数ERについても併せて説明する。
【０１７３】
［関数AR］
入力は、X,W 、及びランダムテープRPである。そして、RPからランダムな x' ∈ Z/qZ を生成し、aR = y' =gx' として、aRを出力する。
【０１７４】
［関数ZR］
入力は、X,W、ランダムテープRP、及び eR=cである。そして、 zR = r = xc + x' mod q を計算し、zRを出力する。
【０１７５】
［関数VR］
入力は、X,aR,eR,zRである。そして、gr = yc y'が成立するならば１を出力し、成立しないならば０を出力する。
【０１７６】
［関数SR’ ］
入力は、X,eR=c,及びランダムテープRSである。そして、RSからランダムな zR=r ∈ Z/qZ を生成し、aR = y' = gry-c を生成する。そして、(aR,zR) を出力する。
【０１７７】
［関数ER］
入力は、aR,eR=c,zR=r, e'R=c',z'R=r'である。そして、 W = x =(r-r')/(c'-c) mod q を計算し、W を出力する。
【０１７８】
なお、上記の関数の説明で、入力となるランダムテープをRS等と表したが、これは入力となるランダムテープを便宜的に表したものに過ぎない。
【０１７９】
次に、本実施例における証明装置と検証装置とによる否認可能認証の動作について説明する。
【０１８０】
まず、証明装置５０１の証明生成装置５２５に、(X,W) ∈ Rなる共通入力X 、証拠W 、第一のランダムテープRP、および第二のランダムテープR'Pが入力される。
【０１８１】
続いて、検証装置５０２の第二関係証明生成装置５１７に、共通入力X 及び第三のランダムテープRVおよびR'V が入力される。
【０１８２】
次に、第二関係証明生成装置５１７は、以下のようにして、離散対数の関係に関する非対話的知識の証明PRを生成する。
【０１８３】
第二関係証明生成装置５１７は、一様無作為に、(X',W') ∈R' なるX',W' を、第三のランダムテープのうちのR'V を用いて生成する。
【０１８４】
次に、第二関係証明生成装置５１７は、共通入力X'、証拠W'、第三のランダムテープのうちのRVを証明コミットメント生成装置５０３に送信する。証明コミットメント生成装置５０３は、関数ARによって、αR= AR(X',W', RV)として、証明コミットメントαR を生成する。そして、証明コミットメント生成装置５０３は、証明コミットメントαR を第二関係証明生成装置５１７に送信する。このときの通信を、図３では、通信５１８として示している。
【０１８５】
次に、第二関係証明生成装置５１７は、共通入力X'、証明コミットメントαR をハッシュ関数の計算装置５１１に送信する。ハッシュ関数の計算装置５１１は、εR=Hash(X', αR)としてハッシュ値を計算する。ハッシュ関数の計算装置５１１は、ハッシュ値εR を第二関係証明生成装置５１７に送信する。このときの通信を、図３では、通信５１９として示している。
【０１８６】
次に、第二関係証明生成装置５１７は、共通入力X'、証拠W'、ハッシュ値εR 、および第三のランダムテープのうちのRVを応答生成装置５０４に送信する。ここでは、ハッシュ値εR を挑戦値として送信する。応答生成装置５０４は、関数ZRによって、ζR =ZR(X',W',εR, RV)として、応答ζR を生成する。応答生成装置５０４は、応答ζR を第二関係証明生成装置５１７に送信する。このときの通信を、図３では、通信５２０として示している。
【０１８７】
第二関係証明生成装置５１７は、離散対数の関係に関する非対話的知識の証明PRを(X',εR,ζR)とする。第二関係証明生成装置５１７は、以上のようにして生成した証明 PR=(X',εR,ζR)を、第二関係証明検証装置５２３に送信する（図３に示す通信５２１）。
【０１８８】
なお、第二関係証明検証装置５２３は、証明PRが送信されてくるのを待ち、上記の通信５２１で、第二関係証明生成装置５１７から証明 PR=(X',εR,ζR)を受信する。
【０１８９】
証明装置５０１の第二関係証明検証装置５２３は、以下のようにして、離散対数の関係に関する非対話的知識の証明PRを検証する。
【０１９０】
第二関係証明検証装置５２３は、共通入力X'、証明コミットメントαR をハッシュ関数の計算装置５１０に送信する。ハッシュ関数の計算装置５１０は、ε'R = Hash(X', αR)としてハッシュ値を計算する。ハッシュ関数の計算装置５１０は、ハッシュ値ε'Rを第二関係証明検証装置５２３に送信する。このときの通信を、図３では、通信５２２として示している。
【０１９１】
第二関係証明検証装置５２３は、共通入力X'、証明コミットメントαR 、ハッシュ値ε'R、応答ζR を対話証明検証装置５０５に送信する。ここでは、ハッシュ値ε'Rを挑戦値として送信する。対話証明検証装置５０５は、関数VRによって、VR(X',αR,ε'R, ζR)の計算結果を導出し、その計算結果を第二関係証明検証装置５２３に送信する。このときの通信を、図３では、通信５２４として示している。
【０１９２】
第二関係証明検証装置５２３は、VR(X',αR,ε'R, ζR)=1が成り立つか否かを判定する。成り立っていないならば、証明装置５０１を停止する。また、成り立っているならば、証明装置５０１は、次に示す動作を行う。すなわち、VR(X',αR,ε'R, ζR)=1が成立していれば、証明PRを受理とし、成立していなければ証明PRを不受理とする。
【０１９３】
証明装置５０１の証明生成装置５２５は、以下のようにして、X に関して離散対数の関係を満す証拠あるいはX'に関して離散対数の関係を満す証拠の、いずれかの証拠に関する知識の非対話的知識の証明 PR(X)∨R(X') を生成する。
【０１９４】
証明生成装置５２５は、第二のランダムテープR'P を用いて乱数e'Rを生成し、これを挑戦値とする。
【０１９５】
次に、証明生成装置５２５は、共通入力X'、挑戦値e'R、および第二のランダムテープR'Pを模擬装置５０９に送信して、模擬装置５０９に証明コミットメントa'Rと応答z'Rを生成させる。模擬装置５０９は、関数SR’ によって、(a'R,z'R) =SR'(X',e'R,R'P)を導出し、証明コミットメントa'Rと応答z'Rを証明生成装置５２５に送信する。このときの通信を、図３では、通信５２６として示している。
【０１９６】
次に、証明生成装置５２５は、共通入力X 、証拠W 、および第一のランダムテープRPを証明コミットメント生成装置５０３に送信する。証明コミットメント生成装置５０３は、関数ARによって、aR=AR(X,W,RP)として、証明コミットメントaRを生成し、証明生成装置５２５に送信する。このときの通信を、図３では、通信５２７として示している。
【０１９７】
次に、証明生成装置５２５は、共通入力X 、証明コミットメントaR、共通入力X'、証明コミットメントa'Rを、ハッシュ関数の計算装置５１０に送信する。ハッシュ関数の計算装置５１０は、e = Hash(X,aR,X',a'R) としてハッシュ値e を計算し、そのハッシュ値を証明生成装置５２５に送信する。このときの通信を、図３では、通信５２８として示している。
【０１９８】
次に、証明生成装置５２５は、eR= e ∨ e'Rとして、挑戦値eRを計算する。証明生成装置５２５は、共通入力X 、証拠W 、挑戦値eR、および第一のランダムテープRPを応答生成装置５０４に送信し、応答zRを生成させる。応答生成装置５０４は、関数ZRによって、zR=ZR(X,W,eR,RP)として、応答zRを生成し、応答zRを証明生成装置５２５に送信する。このときの通信を、図３では、通信５２９として示している。
【０１９９】
証明生成装置５２５は、X に関する離散対数の関係を満す証拠あるいはX' に関する離散対数の関係を満す証拠の、いずれかの証拠に関する知識の非対話的知識の証明 PR(X)∨R(X') を(aR,eR,zR, a'R,e'R,z'R)とする。証明生成装置５２５は、以上のようにして生成した証明 PR(X)∨R(X') =(aR,eR,zR, a'R,e'R,z'R)を、検証装置５０２の証明検証装置５３４に送信する（図３に示す通信５２９）。
【０２００】
証明検証装置５３４は、共通入力X 、証明コミットメントaR、共通入力X'、および証明コミットメントa'Rをハッシュ関数の計算装置５１１に送信し、ハッシュ値を計算させる。ハッシュ関数の計算装置５１１は、Hash(X,aR,X',a'R) の計算結果を導出し、その計算結果（ハッシュ値）を証明検証装置５３４に送信する。このときの通信を、図３では、通信５３０として示している。そして、証明検証装置５３４は、Hash(X,aR,X',a'R) の計算結果が、eR∨e'Rと等しくなっているか否かを判定する。
【０２０１】
次に、証明検証装置５３４は、共通入力X 、証明コミットメントaR、挑戦値eR、応答zRを対話証明検証装置５０５に送信する。対話証明検証装置５０５は、関数VRによって、VR(X,aR,eR,zR)の計算結果を導出し、その計算結果を証明検証装置５３４に送信する。このときの通信を、図３では、通信５３２として示している。証明検証装置５３４は、VR(X,aR,eR,zR)=1が成立しているか否かを判定する。
【０２０２】
次に、証明検証装置５３４は、共通入力X'、証明コミットメントa'R、挑戦値e'R、応答z'Rを対話証明検証装置５０５に送信する。対話証明検証装置５０５は、関数VRによって、VR(X',a'R,e'R,z'R)の計算結果を導出し、その計算結果を証明検証装置５３４に送信する。このときの通信を、図３では、通信５３１として示している。証明検証装置５３４は、VR(X',a'R,e'R,z'R)=1が成立しているかを判定する。
【０２０３】
証明検証装置５３４は、上記の各判定が全て成立している場合、すなわち、Hash(X,aR,X',a'R) =eR∨e'R、VR(X,aR,eR,zR)=1、およびVR(X',a'R,e'R,z'R)=1が全て成立している場合、“１”を検証結果５３５として出力する。その他の場合、証明検証装置５３４は、“０”をを検証結果５３５として出力する。上記の“１”は、証明 PR(X)∨R(X')を受理することを表す。また、上記の“０”は、証明 PR(X)∨R(X')を受理しないことを表す。
【産業上の利用可能性】
【０２０４】
本発明は、例えば、否認不可署名の否認プロトコル、 否認不可署名の確認プロトコル、否認可能認証等に使われる否認可能零知識対話証明に適用可能である。
【０２０５】
また、本発明は、スマートカード等の計算力の小さなハードウェアによる否認可能認証にも適用可能である。スマートカード等を用いて従来の方法で否認可能証明のようなプライバシー保護性が高い認証を行なう場合、スマートカード等の計算力の低さにより、膨大な時間がかかってしまっていた。本発明を適用することにより、一般に使われているプライバシー保護性が低い認証の高々２倍程度の計算量で、プライバシー保護性が高い認証を実現できる。
【０２０６】
また、サーバ等が多くのプライバシー保護性が高い認証を行なう場合にも、本発明を用いることができる。一般に、サーバ等が多量の認証を行なう場合、個々の認証に必要な時間と通信量が大して多くなくとも、多量の認証を行なうと、全体としてそれらの量は膨大となる。本発明を用いれば、プライバシー保護性が高い認証を行っても、サーバの計算量と通信量を小さく抑えることができる。
【０２０７】
また、プライバシー保護性が高い零知識証明を行なう場合にも、本発明を用いることができる。認証、電子投票、否認 不可署名、検証者指定署名等、高いプライバシー保護性が満されると都合のよいアプリケーションが多くある。また、これらのアプリケーションに対応する特別正直検証者零知識対話証明が数多く提案されている。これらの特別正直検証者零知識対話証明に本発明を適用すれば、高いプライバシー保護性が満される電子投票、否認不可署名、検証者指定署名等が容易に実現できる。
【符号の説明】
【０２０８】
３０１  証明装置
３０２  検証装置
３０３  証明コミットメント生成装置
３０４  応答生成装置
３０５  対話証明検証装置
３１０，３１１  ハッシュ関数の計算装置
３１２  挑戦値のコミットメント生成装置
３２４  挑戦値のコミットメント検証装置
３３０  証明生成装置
３４０  証明検証装置
【図１】
0005321696.tif 000002
【図２】
0005321696.tif 000003
【図３】
0005321696.tif 000004
【図４】
0005321696.tif 000005
【図５】
0005321696.tif 000006
【図６】
0005321696.tif 000007