(57)【特許請求の範囲】
【請求項１】
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータが格納された証明装置記憶部、ならびに、前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記証明装置記憶部から前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを外部に送信し、外部からチャレンジ値cを受信すると、該チャレンジ値ｃおよび前記s＿｛j＿1｝,  …,  s＿｛j＿p｝から残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿iおよび前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを外部に送信する証明装置制御部を含む証明装置と、
前記証明装置と通信可能に接続され、複数の乱数および前記集合の元y＿1,  …,  y＿nが格納された検証装置記憶部、ならびに、前記証明装置からコミット値Commit＿1,…,Commit＿nを受信すると、前記複数の乱数から選択したcをチャレンジ値として該証明装置に送信し、前記巡回群の元s＿1,  …,  s＿nおよびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該s＿1,  …,  s＿nが前記チャレンジ値cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない検証装置制御部を含む検証装置と、
を有する証明検証システム。
【請求項２】
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、n個の元を含む巡回群のデータおよび複数の元を含む群のデータが格納された証明装置記憶部、ならびに、前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、外部からコミット値Comを受信すると、該コミット値Comを前記証明装置記憶部に格納し、該証明装置記憶部から前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記元y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、前記複数の元を含む群からランダムに元c＿2を選び、該元c＿2および該Commit＿1,  …,  Commit＿nを外部に送信し、前記コミット値Comを算出するための、前記複数の元を含む群の元c＿1を外部から受信すると、該コミット値Comが該元c＿1の正当なコミットメントであるか否かを検証し、正当でない場合、証明の続行を拒否し、正当である場合、前記c＿1と前記c＿2を乗算した値cを求め、前記s＿｛j＿1｝,  …,  s＿｛j＿p｝と該値cから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿i、および前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信する証明装置制御部を含む証明装置と、
前記証明装置と通信可能に接続され、複数の元を含む群のデータが格納された検証装置記憶部、ならびに、前記複数の元を含む群からランダムに元c＿1を選び、該元c＿1のコミット値Comを算出して前記証明装置に送信し、前記複数の元を含む群の元c＿2、およびコミット値Commit＿1,  …,  Commit＿nを前記証明装置から受信すると、前記元c＿1を該証明装置に送信し、巡回群の元s＿1,  …,  s＿n、およびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該c＿1と該c＿2を乗算した値cを求め、該s＿1,  …,  s＿nが該値cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない検証装置制御部を含む検証装置と、
を有する証明検証システム。
【請求項３】
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータが格納された証明装置記憶部、ならびに、前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記証明装置記憶部から前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記元y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、該Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、該ハッシュ値cと前記s＿｛j＿1｝,  …,  s＿｛j＿p｝とから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,  …,  nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿iおよび前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを外部に送信する証明装置制御部を含む証明装置と、
前記証明装置と通信可能に接続され、前記集合の元y＿1,  …,  y＿nが格納された検証装置記憶部、ならびに、前記巡回群の元s＿1,  …,  s＿n、コミット値Commit＿1,  …,  Commit＿n、およびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、該s＿1,  …,  s＿nが該ハッシュ値cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない検証装置制御部を含む検証装置と、
を有する証明検証システム。
【請求項４】
検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明する証明装置であって、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータが格納された記憶部と、
前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記記憶部から前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを前記検証装置に送信し、前記検証装置からチャレンジ値cを受信すると、該チャレンジ値ｃおよび前記s＿｛j＿1｝,  …,  s＿｛j＿p｝から残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿iおよび前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信する制御部と、
を有する証明装置。
【請求項５】
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証する検証装置であって、
複数の乱数および集合の元y＿1,  …,  y＿nが格納された記憶部と、
前記証明装置からコミット値Commit＿1,…,Commit＿nを受信すると、前記複数の乱数から選択したcをチャレンジ値として該証明装置に送信し、巡回群の元s＿1,  …,  s＿nおよびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該s＿1,  …,  s＿nが前記チャレンジ値cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない制御部と、
を有する検証装置。
【請求項６】
検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明する証明装置であって、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、n個の元を含む巡回群のデータおよび複数の元を含む群のデータが格納された記憶部と、
前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記検証装置からコミット値Comを受信すると、該Comを前記記憶部に格納し、該記憶部から前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記元y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、前記複数の元を含む群からランダムに元c＿2を選び、該c＿2および該Commit＿1,  …,  Commit＿nを前記検証装置に送信し、前記Comを算出するための、前記複数の元を含む群の元c＿1を該検証装置から受信すると、該コミット値Comが該c＿1の正当なコミットメントであるか否かを検証し、正当でない場合、証明の続行を拒否し、正当である場合、前記c＿1と前記c＿2を乗算したcを求め、前記s＿｛j＿1｝,  …,  s＿｛j＿p｝と該cから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿i、および前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信する制御部と、
を有する証明装置。
【請求項７】
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証する検証装置であって、
複数の元を含む群のデータおよび集合の元y＿1,  …,  y＿nが格納された記憶部と、
前記複数の元を含む群からランダムに元c＿1を選び、該元c＿1のコミット値Comを算出して前記証明装置に送信し、前記複数の元を含む群の元c＿2、およびコミット値Commit＿1,  …,  Commit＿nを前記証明装置から受信すると、前記c＿1を該証明装置に送信し、巡回群の元s＿1,  …,  s＿n、およびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該c＿1と該c＿2を乗算したcを求め、該s＿1,  …,  s＿nが該cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない制御部と、
を有する検証装置。
【請求項８】
検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明する証明装置であって、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータが格納された記憶部と、
前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記記憶部から前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記元y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、該Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、該cと前記s＿｛j＿1｝,  …,  s＿｛j＿p｝とから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,  …,  nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿iおよび前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信する制御部と、
を有する証明装置。
【請求項９】
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証する検証装置であって、
集合の元y＿1,  …,  y＿nが格納された記憶部と、
巡回群の元s＿1,  …,  s＿n、コミット値Commit＿1,  …,  Commit＿n、およびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、該s＿1,  …,  s＿nが該cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない制御部と、
を有する検証装置。
【請求項１０】
証明文を発行する証明装置と、該証明装置に通信可能に接続され、該証明文を検証する検証装置とによる証明検証方法であって、
前記証明装置が、n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータを格納し、
前記検証装置が、複数の乱数および前記集合の元y＿1,  …,  y＿nを格納し、
前記証明装置が、前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを前記検証装置に送信し、
前記検証装置が、前記証明装置からコミット値Commit＿1,…,Commit＿nを受信すると、前記複数の乱数から選択したcをチャレンジ値として該証明装置に送信し、
前記証明装置が、前記検証装置から前記チャレンジ値cを受信すると、該チャレンジ値ｃおよび前記s＿｛j＿1｝,  …,  s＿｛j＿p｝から残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿iおよび前記Challenge＿iを使ってレスポンス値Response＿iを算出し、s＿1,  …,  s＿nとResponse＿1,  …,  Response＿nを前記検証装置に送信し、
前記検証装置が、前記元s＿1,  …,  s＿nおよびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該s＿1,  …,  s＿nが前記チャレンジ値cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない、証明検証方法。
【請求項１１】
証明文を発行する証明装置と、該証明装置に通信可能に接続され、該証明文を検証する検証装置とによる証明検証方法であって、
前記証明装置が、n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、n個の元を含む巡回群のデータおよび複数の元を含む群のデータを格納し、
前記検証装置が、前記複数の元を含む群のデータを格納し、
前記検証装置が、前記複数の元を含む群からランダムに元c＿1を選び、該元c＿1のコミット値Comを算出して前記証明装置に送信し、
前記証明装置が、前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記検証装置から前記コミット値Comを受信すると、該Comを格納し、前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記元y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、前記複数の元を含む群からランダムに元c＿2を選び、該c＿2および該Commit＿1,  …,  Commit＿nを前記検証装置に送信し、
前記検証装置は、前記元c＿2および前記コミット値Commit＿1,  …,  Commit＿nを前記証明装置から受信すると、前記c＿1を該証明装置に送信し、
前記証明装置が、前記元c＿1を前記検証装置から受信すると、前記コミット値Comが該c＿1の正当なコミットメントであるか否かを検証し、正当でない場合、証明の続行を拒否し、正当である場合、前記c＿1と前記c＿2を乗算したcを求め、前記s＿｛j＿1｝,  …,  s＿｛j＿p｝と該cから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿i、および前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信し、
前記検証装置が、前記元s＿1,  …,  s＿n、および前記レスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該c＿1と該c＿2を乗算したcを求め、該s＿1,  …,  s＿nが該cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない、証明検証方法。
【請求項１２】
証明文を発行する証明装置と、該証明装置に通信可能に接続され、該証明文を検証する検証装置とによる証明検証方法であって、
前記証明装置が、n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータを格納し、
前記検証装置が、前記集合の元y＿1,  …,  y＿nを格納し、
前記証明装置が、前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して前記元y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、該Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、該cと前記s＿｛j＿1｝,  …,  s＿｛j＿p｝とから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,  …,  nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿iおよび前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信し、
前記検証装置は、前記元s＿1,  …,  s＿n、前記コミット値Commit＿1,  …,  Commit＿n、および前記レスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、該s＿1,  …,  s＿nが該cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して前記元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない、証明検証方法。
【請求項１３】
検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明するコンピュータに実行させるためのプログラムであって、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータを格納し、
前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、
v=1,  …,  pに対して前記y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、
u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを前記検証装置に送信し、
前記検証装置からチャレンジ値cを受信すると、該チャレンジ値ｃおよび前記s＿｛j＿1｝,  …,  s＿｛j＿p｝から残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、
i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、
前記y＿i、前記Commit＿iおよび前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信する処理を前記コンピュータに実行させるためのプログラム。
【請求項１４】
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証するコンピュータに実行させるためのプログラムであって、
複数の乱数および集合の元y＿1,  …,  y＿nを格納し、
前記証明装置からコミット値Commit＿1,…,Commit＿nを受信すると、前記複数の乱数から選択したcをチャレンジ値として該証明装置に送信し、
巡回群の元s＿1,  …,  s＿nおよびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該s＿1,  …,  s＿nが前記チャレンジ値cから正当な方法で生成された秘密分散であるか否かを検証し、
前記s＿1,  …,  s＿nが前記チャレンジ値cから正当な方法で生成された秘密分散であれば、i=1,  …,  nに対して前記s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない処理を前記コンピュータに実行させるためのプログラム。
【請求項１５】
検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明するコンピュータに実行させるためのプログラムであって、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、n個の元を含む巡回群のデータおよび複数の元を含む群のデータを格納し、
前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記検証装置からコミット値Comを受信すると、該Comを格納し、
前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、
v=1,  …,  pに対して前記元y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、
u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、前記複数の元を含む群からランダムに元c＿2を選び、該c＿2および該Commit＿1,  …,  Commit＿nを前記検証装置に送信し、
前記Comを算出するための、前記複数の元を含む群の元c＿1を前記検証装置から受信すると、該コミット値Comが該c＿1の正当なコミットメントであるか否かを検証し、
前記コミット値Comが前記c＿1の正当なコミットメントでない場合、証明の続行を拒否し、正当なコミットメントである場合、前記c＿1と前記c＿2を乗算したcを求め、前記s＿｛j＿1｝,  …,  s＿｛j＿p｝と該cから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿i、および前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信する処理を前記コンピュータに実行させるためのプログラム。
【請求項１６】
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証するコンピュータに実行させるためのプログラムであって、
複数の元を含む群のデータおよび集合の元y＿1,  …,  y＿nを格納し、
前記複数の元を含む群からランダムに元c＿1を選び、該元c＿1のコミット値Comを算出して前記証明装置に送信し、
前記複数の元を含む群の元c＿2、およびコミット値Commit＿1,  …,  Commit＿nを前記証明装置から受信すると、前記c＿1を該証明装置に送信し、
巡回群の元s＿1,  …,  s＿n、およびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該c＿1と該c＿2を乗算したcを求め、該s＿1,  …,  s＿nが該cから正当な方法で生成された秘密分散であるか否かを検証し、
前記s＿1,  …,  s＿nが前記cから正当な方法で生成された秘密分散であれば、i=1,  …,  nに対して前記元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない処理を前記コンピュータに実行させるためのプログラム。
【請求項１７】
検証装置と通信可能に接続され、該検証装置に対して秘密データの保持を証明するコンピュータに実行させるためのプログラムであって、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータを格納し、
前記n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、前記巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、
v=1,  …,  pに対して前記元y＿｛j＿v｝と前記Challenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、
u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、前記Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝および前記Commit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、該Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、前記cと前記s＿｛j＿1｝,  …,  s＿｛j＿p｝とから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,  …,  nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、前記y＿i、前記Commit＿iおよび前記Challenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを前記検証装置に送信する処理を前記コンピュータに実行させるためのプログラム。
【請求項１８】
証明装置と通信可能に接続され、該証明装置が発行する証明文を検証するコンピュータに実行させるためのプログラムであって、
集合の元y＿1,  …,  y＿nを格納し、
巡回群の元s＿1,  …,  s＿n、コミット値Commit＿1,  …,  Commit＿n、およびレスポンス値Response＿1,  …,  Response＿nを前記証明装置から受信すると、該Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、該s＿1,  …,  s＿nが該cから正当な方法で生成された秘密分散であるか否かを検証し、
前記s＿1,  …,  s＿nが前記cから正当な方法で生成された秘密分散であれば、i=1,  …,  nに対して前記元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文が前記y＿iの正当な証明文であるか否かを検証し、正当である場合、前記証明装置による証明を受理し、正当でない場合、該証明装置による証明を受理しない処理を前記コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の情報のうちいくつかを知っていることの証明を可能にし、また、その証明の正当性の検証を可能にするための証明検証システム、証明装置および検証装置と、証明検証方法と、その方法をコンピュータに実行させるためのプログラムとに関する。
【背景技術】
【０００２】
証明装置と呼ばれる情報処理装置が検証装置と呼ばれる他の情報処理装置に何らかの性質を満たす秘密情報を知っていることを証明するプロトコルを「知識の証明」という。検証装置は証明装置の行った証明の正当性を検証し、正当であるかそうでないかを判断する。【０００３】
知識の証明方式は様々な暗号プロトコルを作る際の部品として用いられている。直接的な応用例として認証方式や署名方式がある。認証方式も署名方式も、インターネット上で他の人に当人性を証明するために用いられる技術である。ある種の認証方式、署名方式はIPSec(Security  Architecture  for  Internet  Protocol)として実用化されており、産業上の利用価値が高い。【０００４】
文献（R.Cramer,  I.Damgaard,  and  B.Schoenmakers.，“Proofs  of  partial  knowledge  and  simplified  design  of  witness  hiding  protocols”，In  CRYPTO'94,  LNCS  2139,  Springer-Verlag,  1994,  pp.  174-187：以下では、この文献を文献１と称する）において、Cramer等は、俗に「Orの証明」と呼ばれる知識の証明方式を提案した。nを自然数とし、kをn以下の自然数とすると、この方式では、証明装置がn個の秘密のうち少なくともk個を知っていることを検証者に証明できる。【０００５】
「Orの証明」はある種の匿名性を持つ認証方式を実現するのに必要で、これも様々な暗号プロトコルに応用されている。「Orの証明」は、例えば、文献（Isamu  Teranishi,  Jun  Furukawa,  and  Kazue  Sako.，“k-Times  Anonymous  Authentication  （Extended  Abstract）”，In  ASIACRYPT  2004,  LNCS  3329,  Springer-Verlag,  2004,  pp.  308-322：以下では、この文献を文献２と称する）や文献（寺西勇，「離散対数問題にtight安全でかつ計算量が少ない署名方式」，In  Proceedings  of  the  2005  Symposium  on  Cryptography  and  Information  Security,  3E3-4,  January  2005：以下では、この文献を文献３と称する）で利用されている。文献３は電子投票、電子現金、匿名視聴といった応用を持つ方式であり、これも産業上の利用価値が高い。【０００６】
また、Cramer等は文献１で、次のような一般的な知識の証明方式も提案している。あらかじめ「アクセス構造」（Douglas  R.  Stinson，「暗号理論の基礎」，共立出版株式会社，P355-356を参照）と呼ばれるものを決めておく。この方式では、証明装置はn個の秘密のうち複数個を知っていて、しかもその複数個は前述のアクセス構造を満たすものであることを証明できる。
n個の秘密をx＿1,  …  ,x＿nとする。
Cramer等は、x＿1,  …  ,x＿nが満たす性質が同じである場合に対して知識の証明方式を提案している。
Cramer等の知識の証明方式は、x＿1の知識の証明方式、x＿2の知識の証明方式、…、x＿nの知識の証明方式を組み合わせることで、より一般の場合にも用いることができる。しかし、Cramer等の知識の証明方式を使うことができるのは、x＿1の知識の証明方式、x＿2の知識の証明方式、…、x＿nの知識の証明方式が以下の条件1,2を満たす場合のみである。
条件1.  x＿1の知識の証明方式、x＿2の知識の証明方式、…、x＿nの知識の証明方式は3-ムーブのパブリックコイン証明方式である。
条件2.  x＿iの知識の証明方式でChallengeを選ぶ空間をChallengeSpace＿iとするとき、ChallengeSpace＿1=  …=  ChallengeSpace＿nでなければならない。
なお、「3-ムーブのパブリックコイン証明方式」および「Challenge」等の言葉の説明は、後述の（定義）の章で行う。
【発明の開示】
【０００７】
Cramer等の知識の証明方式は、上述した２つの条件を満たす場合にしか使うことができない。また、Cramer等の知識の証明方式と同様な効果が得られ、かつ、必要とされる条件がより少ない方式を作る必要がある。
【０００８】
本発明の目的は、上記問題点に鑑みてなされたものであり、秘密データ保持の証明をより速く検証可能にした証明検証システム、証明装置および検証装置と、証明検証方法と、その方法をコンピュータに実行させるためのプログラムとを提供することにある。
【０００９】
上記目的を達成するための本発明の証明検証システムは、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータが格納された証明装置記憶部、ならびに、n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、証明装置記憶部から巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対してy＿｛j＿v｝とChallenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝およびCommit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを外部に送信し、外部からチャレンジ値cを受信すると、チャレンジ値ｃおよびs＿｛j＿1｝,  …,  s＿｛j＿p｝から残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、y＿i、Commit＿iおよびChallenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを外部に送信する証明装置制御部を含む証明装置と、
証明装置と通信可能に接続され、複数の乱数および集合の元y＿1,  …,  y＿nが格納された検証装置記憶部、ならびに、証明装置からコミット値Commit＿1,…,Commit＿nを受信すると、複数の乱数から選択したcをチャレンジ値として証明装置に送信し、巡回群の元s＿1,  …,  s＿nおよびレスポンス値Response＿1,  …,  Response＿nを証明装置から受信すると、s＿1,  …,  s＿nがチャレンジ値cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対してs＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文がy＿iの正当な証明文であるか否かを検証し、正当である場合、証明装置による証明を受理し、正当でない場合、証明装置による証明を受理しない検証装置制御部を含む検証装置と、
を有する構成である。
【００１０】
また、本発明の証明検証システムは、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、n個の元を含む巡回群のデータおよび複数の元を含む群のデータが格納された証明装置記憶部、ならびに、n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、外部からコミット値Comを受信すると、コミット値Comを証明装置記憶部に格納し、証明装置記憶部から巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して元y＿｛j＿v｝とChallenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝およびCommit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、複数の元を含む群からランダムに元c＿2を選び、元c＿2およびCommit＿1,  …,  Commit＿nを外部に送信し、コミット値Comを算出するための、複数の元を含む群の元c＿1を外部から受信すると、コミット値Comが元c＿1の正当なコミットメントであるか否かを検証し、正当でない場合、証明の続行を拒否し、正当である場合、c＿1とc＿2を乗算した値cを求め、s＿｛j＿1｝,  …,  s＿｛j＿p｝と値cから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,…,nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、y＿i、Commit＿i、およびChallenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを検証装置に送信する証明装置制御部を含む証明装置と、
証明装置と通信可能に接続され、複数の元を含む群のデータが格納された検証装置記憶部、ならびに、複数の元を含む群からランダムに元c＿1を選び、元c＿1のコミット値Comを算出して証明装置に送信し、複数の元を含む群の元c＿2、およびコミット値Commit＿1,  …,  Commit＿nを証明装置から受信すると、元c＿1を証明装置に送信し、巡回群の元s＿1,  …,  s＿n、およびレスポンス値Response＿1,  …,  Response＿nを証明装置から受信すると、c＿1とc＿2を乗算した値cを求め、s＿1,  …,  s＿nが値cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文がy＿iの正当な証明文であるか否かを検証し、正当である場合、証明装置による証明を受理し、正当でない場合、証明装置による証明を受理しない検証装置制御部を含む検証装置と、
を有する構成である。
【００１１】
また、本発明の証明検証システムは、
n個の秘密データのうちm個（m＜n）の秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝、集合の元y＿1,  …,  y＿n、およびn個の元を含む巡回群のデータが格納された証明装置記憶部、ならびに、n個の秘密データに対する識別子i＿1,  …,  i＿mのいずれとも異なる識別子をj＿1,  …,  j＿p（p=  n-m）とし、証明装置記憶部から巡回群の元s＿｛j＿1｝,  …,  s＿｛j＿p｝をランダムに選び、v=1,  …,  pに対して各s＿｛j＿v｝のハッシュ関数による値をチャレンジ値Challenge＿｛j＿v｝とし、v=1,  …,  pに対して元y＿｛j＿v｝とChallenge＿｛j＿v｝を入力とするゼロ知識証明のシミュレーションを行うことで、コミット値とレスポンス値の組（Commit＿｛j＿1｝,  Response＿｛j＿1｝）,  …,  （Commit＿｛j＿p｝,  Response＿｛j＿p｝）を生成し、u=1,  …,  mに対してx＿｛i＿u｝とy＿｛i＿u｝を用いてコミット値Commit＿｛i＿u｝を生成し、Commit＿｛j＿1｝,  …,  Commit＿｛j＿p｝およびCommit＿｛i＿1｝,  …,  Commit＿｛i＿m｝からなるコミット値Commit＿1,  …,  Commit＿nを求め、Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、ハッシュ値cとs＿｛j＿1｝,  …,  s＿｛j＿p｝とから残りの元s＿｛i＿1｝,  …,  s＿｛i＿m｝を生成し、i=1,  …,  nに対して各s＿iにそのハッシュ値をチャレンジ値Challenge＿iとし、y＿i、Commit＿iおよびChallenge＿iを使ってレスポンス値Response＿iを算出し、元s＿1,  …,  s＿nとレスポンス値Response＿1,  …,  Response＿nを外部に送信する証明装置制御部を含む証明装置と、
証明装置と通信可能に接続され、集合の元y＿1,  …,  y＿nが格納された検証装置記憶部、ならびに、巡回群の元s＿1,  …,  s＿n、コミット値Commit＿1,  …,  Commit＿n、およびレスポンス値Response＿1,  …,  Response＿nを証明装置から受信すると、Commit＿1,  …,  Commit＿nを含むデータのハッシュ値をｃとし、s＿1,  …,  s＿nがハッシュ値cから正当な方法で生成された秘密分散であるか否かを検証し、正当であれば、i=1,  …,  nに対して元s＿iのハッシュ値をチャレンジ値Challenge＿iとし、組（Commit＿i,  Challenge＿i,  Response＿i）による証明文がy＿iの正当な証明文であるか否かを検証し、正当である場合、証明装置による証明を受理し、正当でない場合、証明装置による証明を受理しない検証装置制御部を含む検証装置と、
を有する構成である。
【００１２】
本発明では、証明装置からコミット値が検証装置に送信され、検証装置から証明装置に送信されたチャレンジ値に対して証明装置からレスポンス値が送信され、検証装置で証明装置の証明文が検証される。このようにして、証明装置が秘密データを正規に保持しているか否かが検証可能となる。よって、証明装置がｎ個の秘密データのうちｍ個を保持していることを検証装置に証明可能となる。２つの条件が必要な従来の知識の証明方式に対し、１つの条件を満たすことで検証できる。
【図面の簡単な説明】
【００１３】
【図１】図１は実施形態１における証明検証システムの一構成例を示すブロック図である。
【図２】図２は実施形態１における証明検証システムのデータ送受信の動作手順を示すフローチャートである。
【図３】図３は実施形態１における証明装置のコミット計算手段の動作手順を示すフローチャートである。
【図４】図４は実施形態１における検証装置のチャレンジ計算手段の動作手順を示すフローチャートである。
【図５】図５は実施形態１における証明装置のレスポンス計算手段の動作手順を示すフローチャートである。
【図６】図６は実施形態１における検証装置の検証手段の動作手順を示すフローチャートである。
【図７】図７は実施形態２における証明検証システムの一構成例を示すブロック図である。
【図８】図８は実施形態２における証明検証システムのデータ送受信の動作手順を示すフローチャートである。
【図９】図９は実施形態２における証明検証システムのデータ送受信の動作手順を示すフローチャートである。
【図１０】図１０は実施形態２における検証装置のチャレンジコミット計算手段の動作手順を示すフローチャートである。
【図１１】図１１は実施形態２における証明装置のコミット計算手段の動作手順を示すフローチャートである。
【図１２】図１２は実施形態２における検証装置のチャレンジ計算手段の動作手順を示すフローチャートである。
【図１３】図１３は実施形態２における証明装置のレスポンス計算手段の動作手順を示すフローチャートである。
【図１４】図１４は実施形態２における検証装置の検証手段の動作手順を示すフローチャートである。
【図１５】図１５は実施形態３における証明検証システムの一構成例を示すブロック図である。
【図１６】図１６は実施形態３における証明検証システムのデータ送受信の動作手順を示すフローチャートである。
【図１７】図１７は実施形態３における証明装置の証明文作成手段の動作手順を示すフローチャートである。
【図１８】図１８は実施形態３における証明装置のチャレンジ計算手段の動作手順を示すフローチャートである。
【図１９】図１９は実施形態３における検証装置の検証手段の動作手順を示すフローチャートである。
【符号の説明】
【００１４】
１００    証明装置
１０１    証明装置記憶部
１０２    証明装置制御部
２００    検証装置
２０１    検証装置記憶部
２０２    検証装置制御部
【発明を実施するための最良の形態】
【００１５】
（定義）
[3-ムーブのパブリックコイン証明方式]
X,Yを集合とする。（Y,  X,  FuncCommit,  Hash,  FuncResponse,  ChallengeSpace,  Verify,  Simulator）の証明文が次の性質1,…,7を満たすとき、（Y,  X,  FuncCommit,  Hash,  FuncResponse,  Verify,  Simulator）を3-ムーブのパブリックコイン証明方式という。
1,  組FuncCommit,  Hash,  FuncResponse,  Simulator,  Verifyは関数である。
2,  ChallengeSpaceは集合である。
3,  FuncCommitはY×Xの元を入力とし、データCommitとStateを出力する。
4,  HashはChallengeSpaceに値を取るハッシュ関数である。
5,  （y,x）をY×Xの元とし、ChallengeをChallengeSpaceの元とする。FuncResponseは、y,  x,  Commit,  Challenge,  Stateが入力されると、Responseを出力する。
6,  Verifyは、y,  Commit,  Challenge,  Responseが入力されると、AcceptもしくはRejectを出力する。
7,  Simulatorは、Yの元が入力されると、組（Commit,  Challenge,  Response）を出力する。【００１６】
なお、チャレンジ値Challengeは、通信相手の装置に対して、どのような回答をするかを試すための問いかけの情報であり、一般的には乱数が知られている。コミット値Commitは、自装置が保持する秘密データに関連しているが、その秘密データが直接わからないようにして、通信相手の装置に送る情報である。レスポンス値Responseは、チャレンジ値Challengeの送信元の装置に対して返信する、チャレンジ値の問いかけに対する回答の情報である。【００１７】
[3-ムーブのパブリックコイン証明方式の例]
qを素数とし、Gを位数qの有限群とし、mを自然数とし、H=  G^mとする。
（Y,  X,  FuncCommit,  Hash,  FuncResponse,  ChallengeSpace,  Verify,  Simulator）を以下の1,…,8のように決めると、（Y,  X,  FuncCommit,  Hash,  FuncResponse,  ChallengeSpace,  Verify,  Simulator）は3-ムーブのパブリックコイン証明方式である。
1.  Y=H×Hとする。
2.  Xを位数qの巡回群（Z/qZ）とする。
3.  ChallengeSpace=（Z/qZ）とする。
4.  y=（（g＿1,  …  ,g＿m）,  （h＿1,  …  ,h＿m））をYの元とし、xをXの元とする。Y×Xの元（y,  x）が入力されると、FuncCommitは、（Z/qZ）の元rをランダムに選んで、（C＿1,  …  ,C＿n）=  （g＿1^｛r｝,  …  ,g＿m^｛r｝）を計算し、Commit=  （C＿1,  …  ,C＿n）、State=  rを出力する。
5.  HashはChallengeSpace=（Z/qZ）に値を取るハッシュ関数である。
6.  cを（Z/qZ）の元とし、Challenge=cとする。Yの元y=  （（g＿1,  …  ,g＿m）,  （h＿1,  …  ,h＿m））、Xの元x、Commit=  （C＿1,  …  ,C＿n）、Challenge=  cおよびState=  rが入力されると、FuncResponseは、ρ=  cx+  r  mod  qを計算し、Response=  ρを出力する。
7.  y=  （（g＿1,  …  ,g＿m）,（h＿1,  …  ,h＿m））、Commit=  （C＿1,  …  ,C＿n）、Challenge=  c、Response=  ρが入力されると、Verifyは、（g＿1^｛ρ｝,  …  ,g＿m^｛ρ｝）と（h＿1^｛c｝  C＿1,  …  ,h＿m^｛c｝  C＿m）を計算する。そして、（g＿1^｛ρ｝,  …  ,g＿m^｛ρ｝）=  （h＿1^｛c｝  C＿1,  …  ,h＿n^｛c｝  C＿n）が成立すれば「accept」を出力し、そうでなければ「reject」を出力する。
8.  y=（（g＿1,…,g＿m）,（h＿1,…,h＿m））が入力されると、Simulatorは、ランダムにcとρを選び、（C＿1,  …  ,C＿m）=  （g＿1^｛ρ｝  h＿1^｛-c｝,  …  ,g＿m^｛ρ｝  h＿m^｛-c｝）とし、Commit=  （C＿1,  …  ,C＿m）、Challenge=  c、Response=  ρを出力する。【００１８】
[Rに関する3-ムーブのパブリックコイン証明方式]
RをY×X上の関係式とする。3-ムーブのパブリックコイン証明方式（Y,  X,  FuncCommit,  Hash,  FuncResponse,  Verify,Simulator）が次の性質1、2を満たすとき、（Y,  X,  FuncCommit,  Hash,  FuncResponse,  Verify,Simulator）はRに関する3-ムーブのパブリックコイン証明方式であるという。
1.  R（y,x）を満たす任意の（y,x）に対し、（Commit,  State）=  FuncCommit（y,x）、Challenge=  Hash（y,Commit）、Response=  FuncResponse（y,  Commit,  Challenge,  State）とすると、Verify（y,  Commit,  Challenge,  Response）=  acceptとなる。
2.  Yの任意の元yに対し、（Commit,Challenge,Response）=Simulator（y）とすると、Verify（y,  Commit,  Challenge,  Response）=  acceptとなる。
本発明は任意の3-ムーブのパブリックコイン証明方式に対して用いることができる。しかし、実用的には何らかの関係式Rに対する3-ムーブのパブリックコイン証明方式であることが望ましい。【００１９】
[Rに関する3-ムーブのパブリックコイン証明方式の例]
（Y,  X,  FuncCommit,  Hash,  FuncResponse,  ChallengeSpace,  Verify,  Simulator）を[3-ムーブのパブリックコイン証明方式の例]と同様に決める。Xの元xとYの元y=  （（g＿1,  …  ,g＿m）,  （h＿1,  …  ,h＿m））に対し、R（y,  x）を関係式「（h＿1,  …  ,h＿m）=  （g＿1^｛x｝,  …  ,g＿m^｛x｝）」とすると、（Y,  X,  FuncCommit,  Hash,  FuncResponse,  ChallengeSpace,  Verify,  Simulator）はRに関する3-ムーブのパブリックコイン証明方式である。【００２０】
[アクセス構造]
Sを整数の有限集合とする。Sの部分集合の族Γが次の性質1を満たすとき、ΓをS上のアクセス構造であるという。
1.  Sの任意の部分集合A、Bに対しAがΓの元でかつAがBの部分集合ならBはΓの元である。
[アクセス構造の例1]
nを自然数とする。S＝｛1,…,n｝とし、Γ=｛S｝の集合とする。このときΓはS上のアクセス構造である。
[アクセス構造の例2]
nを自然数とし、kをn以下の自然数とする。S＝｛1,…,n｝とし、ΓをSの部分集合でk個以上元を持つものの集合とする。このときΓはS上のアクセス構造である。【００２１】
[秘密分散方式]
Sを有限集合とし、ΓをS上のアクセス構造とし、nをSの元の数とする。組（FuncShar,  FuncReconstruct,  SharSp,  KeySp）が次の性質1,…,5を満たすとき、（FuncShar,  FuncReconstruct,  SharSp,  KeySp）はアクセス構造Γを持つ秘密分散方式であるという。
1.  FuncSharとFuncReconstructは関数である。
2.  SharSpとKeySpは集合である。
3.  KeySpの元cが入力されると、FuncSharは、SharSpの元s＿1,  …  ,s＿nを出力する。
4.  整数とSharSpの元との組（i＿1,u＿1）,…,（i＿m,u＿m）が入力されると、FuncSharはKeySpの元を出力するか、または文字列「reject」を出力する。
5.  cをKeySpの元とする。FuncSharにcを入力したときの出力をs＿1,…,s＿nとする。A=  ｛i＿1,  …  ,i＿m｝をΓの元とする。このとき（i＿1,  s＿｛i＿1｝）,  …  ,（i＿m,  s＿｛i＿m｝）をFuncSharに入力すると、FuncSharはcを出力する。【００２２】
[秘密分散方式の例1]
n、S、Γを[アクセス構造の例１]で説明したように決める。さらに、qを自然数とする。（FuncShar,  FuncReconstruct,  SharSp,  KeySp）を次の1,…,4のように決めると、（FuncShar,  FuncReconstruct,  SharSp,  KeySp）は秘密分散方式である。
1.  SharSpを巡回群（Z/qZ）とする。
2.  KeySpを巡回群（Z/qZ）とする。
3.  KeySpの元ｃが入力されると、FuncSharは、SharSpの元s＿1,…,s＿｛n-1｝をランダムに選び、s＿n=  c-  s＿1,…,s＿｛n-1｝  mod  qを計算し、（s＿1,  …  ,s＿n）を出力する。
4.  （（1,s＿1）,…,（n,s＿n））が入力されると、FuncReconstructはs＿1+  …  +s＿nを出力する。【００２３】
[秘密分散方式の例2]
n、k、S、Γを[アクセス構造の例2]で説明したように決める。さらに、qを自然数とする。（FuncShar,  FuncReconstruct,  SharSp,  KeySp）を次の1,…,4のように決めると、（FuncShar,  FuncReconstruct,  SharSp,  KeySp）は秘密分散方式である。
1.  SharSpを巡回群（Z/qZ）とする。
2.  KeySpを巡回群（Z/qZ）とする。
3.  KeySpの元ｃが入力されると、FuncSharは、（Z/qZ）の元a＿1,…,a＿｛k-1｝をランダムに選び、多項式f（u）をf（u）=  c+  a＿1x+  a＿2x^2+  …  +a＿｛k-1｝x^｛k-1｝  mod  qと決め、s＿1=  f（1）  mod  q、  …  、s＿n=  f（n）  mod  qとし、（s＿1,  …  ,s＿n）を出力する。
4.  （（i＿1,  s＿｛i＿1｝）,  …  ,（i＿k,  s＿｛k｝））が入力されると、FuncReconstructは多項式f（u）で、f（i＿1）=  s＿｛i＿1｝  mod  q、  …  、f（i＿｛k｝）=  s＿｛i＿k｝  mod  qとなるものを選び、c=  f（0）  mod  qとし、cを出力する。【００２４】
[特別な秘密分散方式]
Sを有限集合とし、ΓをS上のアクセス構造とし、nをSの元の数とする。組（FuncShar,  FuncReconstruct,  FuncReShar,  FuncVerShar,  SharSp,  KeySp）が次の性質1,…,4を満たすとき、（FuncShar,  FuncReconstruct,  FuncVerShar,  SharSp,  KeySp）はアクセス構造Γを持つ特別な秘密分散方式であるという。
1.  （FuncShar,  FuncReconstruct,  SharSp,  KeySp）は秘密分散である。
2.  A=｛i＿1,…,i＿m｝をΓの元とする。s＿｛i＿1｝,  …  ,s＿｛i＿m｝をSharSpの元とする。そしてl=n-mとする。SからAを除いた集合をB=  ｛j＿1,  …  ,j＿l｝とする。さらに、cをKeySpの元とする。このとき、cと（i＿1,  s＿｛i＿1｝）,  …  ,（i＿m,  s＿｛i＿m｝）をFuncReSharに入力すると、FuncReSharは、Sの元とSharSpの元の組（j＿1,  s＿｛j＿1｝）,  …  ,（j＿l,  s＿｛j＿l｝）を出力するか、または「reject」を出力する。
3.  SharSpの元s＿1,  …  ,s＿nとKeySpの元cとが入力されると、FuncVerSharは文字列「accept」または文字列「reject」を出力する。
4.  cをKeySpの元とする。ｃをFuncSharに入力したときの出力をs＿1,  …  ,s＿nとする。このときVerSharSp（s＿1,…,s＿n,c）=acceptが成立する。【００２５】
[特別な秘密分散方式の例１]
n、S、Γを[アクセス構造の例１]で説明したように決める。さらに、qを自然数とする。（FuncShar,  FuncReconstruct,  SharSp,  KeySp）を[秘密分散方式の例1]で説明したように決める。
1.  A=｛i＿1,…,i＿m｝をΓの元とする。s＿｛i＿1｝,  …  ,s＿｛i＿m｝をSharSpの元とする。そしてl=n-mとする。SからAを除いた集合をB=  ｛j＿1,  …  ,j＿l｝とする。さらに、cをKeySpの元とする。cと（i＿1,  s＿｛i＿1｝）,  …  ,（i＿m,  s＿｛i＿m｝）が入力されると、FuncReSharは、s＿｛j＿1｝,  …  ,s＿｛j＿｛l-1｝｝をランダムに選び、s＿｛j＿l｝=  c-（s＿1+  …+  s＿｛j＿｛l-1｝｝+  s＿｛j＿｛j+1｝｝+  …+  s＿n）  mod  qとし、（j＿1,  s＿｛j＿1｝）,  …  ,（j＿l,  s＿｛j＿l｝）を出力する。
2.  SharSpの元s＿1,  …  ,s＿nとKeySpの元cとが入力されると、FuncVerSharは、s＿1+  …+  s＿n  mod  qを計算し、c=  s＿1+  …+  s＿n  mod  qなら「accept」を出力し、そうでないなら「reject」を出力する。【００２６】
[特別な秘密分散方式の例2]
n、k、S、Γを[アクセス構造の例2]で説明したように決める。さらに、qを自然数とする。（FuncShar,  FuncReconstruct,  SharSp,  KeySp）を[秘密分散方式の例2]で説明したように決める。（FuncReShar,  FuncVerShar）を次の1,2のように決めると、（FuncShar,  FuncReconstruct,  FuncReShar,  FuncVerShar,  SharSp,  KeySp）はアクセス構造Γを持つ特別な秘密分散方式である。
1.  A=｛i＿1,…,i＿m｝をΓの元とする。s＿｛i＿1｝,  …  ,s＿｛i＿m｝をSharSpの元とする。そしてl=n-mとする。SからAを除いた集合をB=  ｛j＿1,  …  ,j＿l｝とする。さらに、cをKeySpの元とする。cと（i＿1,  s＿｛i＿1｝）,  …  ,（i＿m,  s＿｛i＿m｝）が入力されると、FuncReSharは、多項式fでf（0）=  c  mod  q,  f（i＿1）=  s＿｛i＿1｝  mod  q,  …,  f（i＿m）=  s＿｛i＿m｝  mod  qとなるものを探す。
2.  もしそのようなfが存在しなければ、FuncReSharは「reject」を出力する。そのようなfが存在すれば、FuncReSharは、s＿｛j＿1｝=  f（j＿1）  mod  q,  …,  s＿｛j＿l｝=  f（j＿l）  mod  qを（j＿1,  s＿｛j＿1｝）,  …  ,（j＿l,  s＿｛j＿l｝）を出力する。
3.  SharSpの元s＿1,  …  ,s＿nとKeySpの元cとが入力されると、FuncVerSharは、多項式fでf（0）=  c  mod  q,  f（1）=  s＿1  mod  q,  …,  f（n）=  s＿n  mod  qとなるものを探す。そのようなfが存在すれば、FuncVerSharは「accept」を出力し、そうでなければ「reject」を出力する。【００２７】
[コミットメント方式]
（C,FuncGen,FuncCom,FuncComVer）が次の1,…,6を満たすとき、（C,  FuncGen,  FuncCom,  FuncComVer）をコミットメント方式という。
1.  Cを集合とする。
2.  FuncGen、FuncCom、FuncComVerは関数である。
3.  FuncGenはDomParを出力する。
4.  DomParとCの元cとが入力されると、FuncComはComとComStateを出力する。
5.  DomPar、Cの元c、データCom’、およびデータComState’が入力されると、FuncComVerは文字列「accept」または文字列「reject」を出力する。
6.  cをCの元とし、DomParをFuncGenの出力とする。DomParとcが入力したときのFuncComの出力をComとComStateとする。このときDomPar、c、Com、ComStateが入力されると、FuncComVerは「accept」を出力する。【００２８】
[コミットメント方式の例]
qを素数とし、Gを位数qの有限群とする。（C,  FuncGen,  FuncCom,  FuncComVer）を次のように決めると、（C,  FuncGen,  FuncCom,  FuncComVer）はコミットメント方式になる。
1.  C=  （Z/qZ）とする。
2.  FuncGenは、Gの２つの元g,  hを選び、DomPar=  （g,  h）を出力する関数である。
3.  DomPar=  （g,  h）とCの元cが入力されると、FuncComは、（Z/qZ）の元rをランダムに選び、Com=  g^c  h^rとComState=  rを出力する。
4.  DomPar=  （g,  h）とCの元cとComとComState=rが入力されると、FuncComVerは、g^c  h^rを計算し、Com=  g^c  h^rなら「accept」を出力し、そうでなければ「reject」を出力する。【００２９】
（実施形態１）
[装置構成]
本実施形態の証明検証システムの構成を説明する。
図1は本実施形態の証明検証システムの一構成例を示すブロック図である。
図1に示すように、証明検証システムは、証明を行うための証明装置100と、検証を行うための検証装置200とを有する。証明装置100および検証装置200は、通信ネットワーク（不図示）を介して通信可能に接続される。
証明装置100は、証明装置制御部102、証明装置記憶部101、および証明装置通信部（不図示）を有する。証明装置制御部102は、コミット計算手段111とレスポンス計算手段112とを有する。
検証装置200は、検証装置制御部202、検証装置記憶部201、および検証装置通信部（不図示）を有する。検証装置制御部202は、チャレンジ計算手段211と、レスポンス計算手段112とを有する。【００３０】
[装置の実装]
各装置の制御部は、通信部の制御、記憶部の制御、およびデータの演算処理を行う。制御部には、プログラムにしたがって所定の処理を実行するCPU（Central  Processing  Unit）、およびプログラムを格納するためのメモリが設けられている。コミット計算手段111、レスポンス計算手段112、チャレンジ計算手段211および検証手段212は、CPUがプログラムを実行することで、コンピュータ内に仮想的に構成される。
通信ネットワークとして、例えば、インターネットやLAN（Local  Area  Network）を用いることができる。通信ネットワークは有線および無線のいずれでもよく、また有線と無線の組み合わせでもよい。図１では、装置間における情報の流れをわかりやすくするために、各装置の通信部を図に示すことを省略している。
記憶部にはハードディスクや半導体メモリなどを用いることが可能である。【００３１】
[記号]
Gを加法群とし、HashをGに値を取るハッシュ関数とする。
i=1,…,nに対しR＿iを関係式とし、y＿iをデータとする。
i=1,…,nに対し（Y＿i,  X＿i,  FuncCommit＿i,  Hash＿i,  FuncResponse＿i,  ChallengeSpace＿i,  Verify＿i,  Simulator＿i）を3-ムーブのパブリックコイン証明方式とする。
（FuncShar,  FuncReconstruct,  FuncReShar,  FuncVerShar,  SharSp,  KeySp）を特別な秘密分散方式とする。
さらに、nを自然数とし、S=｛1,…,n｝とする。ΓをS上のアクセス構造とし、A=  ｛i＿1,  …,  i＿m｝をΓの元とする。そして、p=  n-mとする。SからAを除いた集合をB=  ｛j＿1,  …,  j＿p｝とする。
H＿iをSharSpからChallengeSpace＿iへのハッシュ関数とする。Simulator＿2をゼロ知識証明シミュレータとする。ゼロ知識証明シミュレータは、従来技術と同様であるため、ここでは詳細な説明を省略する。【００３２】
[実施形態１を使用する上での前提]
Xの元ｘ＿｛i＿1｝,…,x＿｛i＿m｝とYの元y＿1,…,y＿nが証明装置記憶部101に保存されている。このｘ＿｛i＿1｝,…,x＿｛i＿m｝は、n個の秘密データのうちのm個の秘密データに相当する。
Yの元y＿1,…,y＿nが検証装置記憶部201に保存されている。
（Y＿i,  X＿i,  FuncCommit＿i,  Hash＿i,  FuncResponse＿i,  ChallengeSpace＿i,  Verify＿i,  Simulator＿i）が関係式R＿iに関する3ムーブのパブリックコイン証明方式である場合は、R（y＿j,  x＿j）が満たされていることが望ましい。【００３３】
[データ送受信]
証明装置100と検証装置200は、以下に説明するProt1-1,  …  ,Port1-10の順でデータ送受信を行う。図２はデータ送受信の動作を示すフローチャートである。
Prot1-1.  証明装置100はコミット計算手段111を行う（ステップ１１０１）。
Prot1-2.  証明装置100は証明装置通信部を使ってコミット計算手段111の出力を検証装置200に送信装置する（ステップ１１０２）。
Prot1-3.  検証装置200は検証装置通信部を使ってコミット計算手段111の出力を受信し、受信したデータを検証装置記憶部201に書き込む（ステップ１１０３）。
Prot1-4.  検証装置200はチャレンジ計算手段211を行う（ステップ１１０４）。
Prot1-5.  検証装置200は検証装置通信部を使ってチャレンジ計算手段211の出力を証明装置100に送信する（ステップ１１０５）。
Prot1-6.  証明装置100は証明装置通信部を使ってチャレンジ計算手段211の出力を受信し、受信したデータを証明装置記憶部101に書き込む（ステップ１１０６）。
Prot1-7.  証明装置100はレスポンス計算手段112を行う（ステップ１１０７）。
Prot1-8.  証明装置100は証明装置通信部を使ってレスポンス計算手段112の出力を検証装置200に送信する（ステップ１１０８）。
Prot1-9.  検証装置200は検証装置通信部を使ってレスポンス計算手段112の出力を受信し、受信したデータを検証装置記憶部201に書き込む（ステップ１１０９）。
Prot1-10.  検証装置200は検証手段212を行う（ステップ１１１０）。【００３４】
[コミット計算手段111]
証明装置100は、以下に説明する手段Com1-1,  …  ,Com1-8を順に行う。図３はコミット計算手段111の動作手順を示すフローチャートである。
Com1-1.  秘密データｘ＿｛i＿1｝,  …  ,x＿｛i＿m｝と集合Yの元y＿1,  …  ,y＿nを証明装置記憶部101から読み込む（ステップ１２０１）。
Com1-2.  v=1,…,pに対してSharSpの元s＿｛j＿v｝をランダムに選びChallenge＿｛j＿v｝=  H＿i（s＿｛j＿v｝）とする（ステップ１２０２）。
Com1-3.  v=1,…,pに対してs＿｛j＿v｝を証明装置記憶部101に書き込む（ステップ１２０３）。
Com1-4.  v=1,…,pに対して（Commit＿｛j＿v｝,  Response＿｛j＿v｝）=  Simulator＿2  （y＿｛j＿v｝,  Challenge＿｛j＿v｝）を計算する（ステップ１２０４）。
Com1-5.  v=1,…,pに対して（Commit＿｛j＿v｝,  Challenge＿｛j＿v｝,  Response＿｛j＿v｝）を証明装置記憶部101に書き込む（ステップ１２０５）。
Com1-6.  u=1,…,mに対して（Commit＿｛i＿u｝,  State＿｛i＿u｝）=  FuncCommit＿｛i＿u｝  （x＿｛i＿u｝,  y＿｛i＿u｝）を計算する（ステップ１２０６）。
Com1-7.  u=1,…,mに対してCommit＿｛i＿u｝,  State＿｛i＿u｝を証明装置記憶部101に書き込む（ステップ１２０７）。
Com1-8.  （Commit＿1,…,Commit＿n）を出力する（ステップ１２０８）。【００３５】
[チャレンジ計算手段211]
検証装置200は、以下に説明する手段Cha1-1,…,Cha1-3を行う。図４はチャレンジ計算手段211の動作手順を示すフローチャートである。
Cha1-1.  SharSpの元cをランダムに選ぶ（ステップ１３０１）。
Cha1-2.  cを検証装置記憶部に書き込む（ステップ１３０２）。
Cha1-3.  cを出力する（ステップ１３０３）。【００３６】
[レスポンス計算手段112]
証明装置100は、以下に説明する手段Res1-1,…,Res1-7を順に行う。図５はレスポンス計算手段112の動作手順を示すフローチャートである。
Res1-1.  Commit＿1,…,Commit＿nを証明装置記憶部101から読み込む（ステップ１４０１）。
Res1-2.  cを証明装置記憶部101から読み込む（ステップ１４０２）。
Res1-3.  v=1,…,pに対してState＿｛j＿v｝を証明装置記憶部101から読み込む（ステップ１４０３）。
Res1-4.  FuncReSharにcと（j＿1,s＿｛j＿1｝）,…,（j＿p,s＿｛j＿p｝）を入力して出力（i＿1,  s＿｛i＿1｝）,  …,  （i＿m,  s＿｛i＿m｝）を得る（ステップ１４０４）。
Res1-5.  v=1,…,pに対してChallenge＿｛i＿v｝=H＿i（s＿v）とする（ステップ１４０５）。
Res1-6.  u=1,…,mに対してResponse＿｛i＿u｝=  FuncResponse＿｛i＿u｝  （y＿｛i＿u｝,  Commit＿｛i＿u｝,  Challenge＿｛i＿u｝,  State＿｛i＿u｝）とする（ステップ１４０６）。
Res1-7.  s＿1,…,s＿nとResponse＿1,…,Response＿nを出力する（ステップ１４０７）。【００３７】
[検証手段212]
検証装置200は、以下に説明する手段Ver1-1,…,Ver1-4を行う。図６は検証手段212の動作手順を示すフローチャートである。
Ver1-1.  c,s＿1,…,s＿nとResponse＿1,…,Response＿nを検証装置記憶部201から読み込む（ステップ１５０１）。
Ver1-2.  FuncVerShar（s＿1,…,s＿n,c）を計算し、FuncVerShar（s＿1,  …,  s＿n,  c）=  rejectならrejectを出力して終了する（ステップ１５０２）。
Ver1-3.  i=1,…,nに対してChallenge＿i=H＿i（s＿i）とする（ステップ１５０３）。
Ver1-4.  i=1,…,nに対し、Verify（y＿i,  Commit＿i,  Challenge＿i,  Response＿i）を計算する。i=1,  …  ,nに対し、Verify（y＿i,  Commit＿i,  Challenge＿i,  Response＿i）=  acceptならacceptを出力して終了し、そうでなければrejectを出力して終了する（ステップ１５０４）。【００３８】
本実施形態の証明検証システムでは、上述のようにして、証明装置100がｎ個の秘密データのうちｍ個を保持していることを検証装置200に証明可能となる。そのため、文献１で開示された、２つの条件を必要とする知識の証明方式について、条件１を満たせばよい。【００３９】
（実施形態２）
[装置構成]
本実施形態の証明検証システムの構成を説明する。なお、実施形態１と同様な構成についてはその詳細な説明を省略する。
図７は本実施形態の証明検証システムの一構成例を示すブロック図である。
図７に示すように、証明検証システムは、証明を行うための証明装置100と、検証を行うための検証装置200とを有する。証明装置100および検証装置200は、通信ネットワーク（不図示）を介して通信可能に接続される。【００４０】
証明装置100は、証明装置制御部102、証明装置記憶部101、および証明装置通信部（不図示）を有する。証明装置制御部102は、コミット計算手段114と、レスポンス計算手段115とを有する。
検証装置200は、検証装置制御部202、検証装置記憶部201、および検証装置通信部（不図示）を有する。検証装置制御部202は、チャレンジコミット計算手段210と、チャレンジ計算手段213と、検証手段214とを有する。【００４１】
[装置の実装]
各装置の制御部には、プログラムにしたがって所定の処理を実行するCPUと、プログラムを格納するためのメモリとが設けられている。コミット計算手段114、レスポンス計算手段115、チャレンジコミット計算手段210、チャレンジ計算手段213および検証手段214は、CPUがプログラムを実行することで、コンピュータ内に仮想的に構成される。その他の構成については、実施形態１と同様であるため、詳細な説明を省略する。【００４２】
[記号]
実施形態１と同じ記号を使う。C=  ChallengeSpとし、（C,  FuncGen,  FuncCom,  FuncComVer）をコミットメント方式とする。【００４３】
[実施形態２を使用する上での前提]
実施形態１と同じ前提を課す。加えて次の前提1,2を課す。
1.  ChallengeSpは群である。
2.  FuncGenの出力DomParを証明装置100と検証装置200が事前に共有している。【００４４】
[データ送受信]
証明装置100と検証装置200は、以下に説明するProt2-1,…,Prot2-13順でデータ送受信を行う。図８および図９は、データ送受信の動作手順を示すフローチャートである。
Prot2-1.  検証装置200はチャレンジコミット計算手段210を行う（ステップ２１０１）。
Prot2-2.検証装置200は検証装置通信部を使ってチャレンジコミット計算手段210の出力を証明装置100に送信する（ステップ２１０２）。
Prot2-3.証明装置100は証明装置通信部を使ってチャレンジコミット計算手段210の出力を受信し、受信したデータを証明装置記憶部101に書き込む（ステップ２１０３）。
Prot2-4.証明装置100はコミット計算手段114を行う（ステップ２１０４）。
Prot2-5.証明装置100は証明装置通信部を使ってコミット計算手段114の出力を検証装置200に送信装置する（ステップ２１０５）。
Prot2-6.検証装置200は検証装置通信部を使ってコミット計算手段114の出力を受信し、受信したデータを検証装置記憶部201に書き込む（ステップ２１０６）。
Prot2-7.検証装置200はチャレンジ計算手段213を行う（ステップ２１０７）。
Prot2-8.検証装置200は検証装置通信部を使ってチャレンジ計算手段213の出力を証明装置100に送信する（ステップ２１０８）。
Prot2−9.  証明装置100は証明装置通信部を使ってチャレンジ計算手段213の出力を受信し、受信したデータを証明装置記憶部101に書き込む（ステップ２１０９）。
Prot2-10.証明装置100はレスポンス計算手段115を行う（ステップ２１１０）。
Prot2-11.証明装置100は証明装置通信部を使ってレスポンス計算手段115の出力を検証装置200に送信する（ステップ２１１１）。
Prot2-12.検証装置200は検証装置通信部を使ってレスポンス計算手段115の出力を受信し、受信したデータを検証装置記憶部201に書き込む（ステップ２１１２）。
Prot2-13.検証装置200は検証手段214を行う（ステップ２１１３）。【００４５】
[チャレンジコミット計算手段210]
検証装置200は、以下に説明する手段ChaCom2-1,…,ChaCom2-5を行う。図１０はチャレンジコミット計算手段210の動作手順を示すフローチャートである。
ChaCom2-1.  DomParを検証装置記憶部201から読み込む（ステップ２２０１）。
ChaCom2-2.  ChallengeSpの元c＿1をランダムに選ぶ（ステップ２２０２）。
ChaCom2-3.  （Com,ComState）=FuncCom（DomPar,c＿1）を計算する（ステップ２２０３）。
ChaCom2-4.  c＿1、Com、ComStateを検証装置記憶部201に書き込む（ステップ２２０４）。
ChaCom2-5.  Comを出力する（ステップ２２０５）。【００４６】
[コミット計算手段114]
証明装置100は、以下に説明する手段Com2-1,…,Com2-4を行う。図１１はコミット計算手段114の動作手順を示すフローチャートである。
Com2-1.  実施形態１のCom1-1,…,Com1-7を行う（ステップ２３０１）。
Com2-2.  ChallengeSpの元c＿2をランダムに選ぶ（ステップ２３０２）。
Com2-3.  c＿2を証明装置記憶部101に書き込む（ステップ２３０３）。
Com2-4.  （c＿2,Commit＿1,…,Commit＿n）を出力する（ステップ２３０４）。【００４７】
[チャレンジ計算手段213]
検証装置200は、以下に説明する手段Cha2-1,Cha2-2を行う。図１２はチャレンジ計算手段213の動作手順を示すフローチャートである。
Cha2-1.  検証装置記憶部201からc＿1、ComStateを読み込む（ステップ２４０１）。
Cha2-2.  c＿1、ComStateを出力する（ステップ２４０２）。【００４８】
[レスポンス計算手段115]
証明装置100は、以下に説明する手段Res2-1,…,Res2-7を順に行う。図１３はレスポンス計算手段115の動作手順を示すフローチャートである。
Res2-1.  Commit＿1,…,Commit＿n,  c＿1,c＿2,DomPar,Com,ComStateを証明装置記憶部101から読み込む（ステップ２５０１）。
Res2-2.  FuncComVer（DomPar,c＿1,Com,ComState）を計算し、FuncComVer  （DomPar,  c＿1,  Com,  ComState）=  rejectならrejectを出力して終了する（ステップ２５０２）。
Res2-3.  c=c＿1c＿2を計算する（ステップ２５０３）。
Res2-4.  cを用いて実施形態１のRes1-3,…,Res1-7を行う（ステップ２５０４）。【００４９】
[検証手段214]
検証装置200は、以下に説明する手段Ver2-1,…,Ver2-5を行う。図１４は検証手段214の動作手順を示すフローチャートである。
Ver2-1.  c＿1,c＿2,s＿1,…,s＿nとResponse＿1,…,Response＿nを検証装置記憶部201から読み込む（ステップ２６０１）。
Ver2-2.  c=c＿1c＿2を計算する（ステップ２６０２）。
Ver2-3.  FuncVerShar（s＿1,…,s＿n,c）を計算し、FuncVerShar（s＿1,…,s＿n,c）=rejectならrejectを出力して終了する（ステップ２６０３）。
Ver2-4.  i=1,…,nに対してChallenge＿i=H＿i（s＿i）とする（ステップ２６０４）。
Ver2-5.  i=1,…,nに対し、Verify（y＿i,  Commit＿i,  Challenge＿i,  Response＿i）を計算する。i=1,…,nに対し、Verify（y＿i,  Commit＿i,  Challenge＿i,  Response＿i）=  acceptならacceptを出力して終了し、そうでなければrejectを出力して終了する（ステップ２６０５）。【００５０】
本実施形態では、実施形態１の効果の他に、検証装置200が証明装置100から情報を受信する前にチャレンジコミット計算手段210を実行することで、データ選択の際に証明装置100からの情報による影響が抑制され、証明装置100に格納された秘密情報の秘匿性が向上する。【００５１】
（実施形態３）
[装置構成]
本実施形態の証明検証システムの構成を説明する。なお、実施形態１と同様な構成についてはその詳細な説明を省略する。
図１５は本実施形態の証明検証システムの一構成例を示すブロック図である。
図１５に示すように、証明検証システムは、証明を行うための証明装置100と、検証を行うための検証装置200とを有する。証明装置100および検証装置200は、通信ネットワーク（不図示）を介して通信可能に接続される。【００５２】
証明装置100は、証明装置制御部102、証明装置記憶部101、および証明装置通信部（不図示）を有する。証明装置制御部102には証明文作成手段110が設けられている。証明文作成手段110は、コミット計算手段116と、チャレンジ計算手段113と、レスポンス計算手段117とを有する。
検証装置200は、検証装置制御部202、検証装置記憶部201、および検証装置通信部（不図示）を有する。検証装置制御部202は、検証手段215を有する構成である。【００５３】
[装置の実装]
各装置の制御部には、プログラムにしたがって所定の処理を実行するCPUと、プログラムを格納するためのメモリとが設けられている。コミット計算手段116、レスポンス計算手段117、チャレンジ計算手段113および検証手段215は、CPUがプログラムを実行することで、コンピュータ内に仮想的に構成される。その他の構成については、実施形態１と同様であるため、詳細な説明を省略する。【００５４】
[記号]
実施形態１と同じ記号を使う。HashChaをSharSpに値を取るハッシュ関数とする。さらに、Mをビット列とする。証明装置100と検証装置200は事前にMを共有しているとする。どのような方法でMを共有したのかは問わない。Mは予備の入力で、目的に応じてMを様々なものにセットする。Mとして空列を選んでもよい。Mにセットするものとして、例えば、次の1,…,6があり得る。
1.  （y＿1,…,y＿n）
2.  証明者のID
3.  検証者のID
4.  時刻
5.  何らかのメッセージ
6.  1,…,5の全てまたは一部を連結したもの
[実施形態３を使用する上での前提]
Xの元ｘ＿｛i＿1｝,…,x＿｛i＿m｝、Yの元y＿1,…,y＿n、およびMが証明装置記憶部101に保存されている。Yの元y＿1,  …,  y＿n、およびMが検証装置記憶部201に保存されている。【００５５】
[データ送受信]
証明装置100と検証装置200は、以下に説明するProt3-1,…,Prot3-4の順でデータ送受信を行う。図１６はデータ送受信の動作手順を示すフローチャートである。
Prot3-1.  証明装置100は証明文作成手段110を行う（ステップ３１０１）。
Prot3-2.  証明装置100は証明装置通信部を使って証明文作成手段110の出力を検証装置200に送信装置する（ステップ３１０２）。
Prot3-3.  検証装置200は検証装置通信部を使って証明文作成手段110の出力を受信し、受信したデータを検証装置記憶部201に書き込む（ステップ３１０３）。
Prot3-4.  検証装置200は検証手段215を行う（ステップ３１０４）。【００５６】
[証明文作成手段110]
証明装置100は、以下に説明する手段GenPf3-1,GenPf3-2を順に行う。図１７は証明文作成手段110の動作手順を示すフローチャートである。
GenPf3-1.  [コミット計算手段116]、[チャレンジ計算手段113]、[レスポンス計算手段117]を順に行う（ステップ３２０１）。
GenPf3-2.  Commit＿1,…,Commit＿n、s＿1,…,s＿n、Response＿1,…,Response＿nを出力する（ステップ３２０２）。
[コミット計算手段116]
証明装置100は、実施形態１のコミット計算手段111のCom1-1,…,Com1-7を行う。
[チャレンジ計算手段113]
証明装置100は以下の手段Cha3-1、Cha3-2を行う（図１８）。
Cha3-1.  Commit＿1,…,Commit＿n,Mを証明装置記憶部101から読み込む。（ステップ３３０１）
Cha3-2.  c=HashCha（Commit＿1,…,Commit＿n,M）を計算し、cを証明装置記憶部101に書き込む。（ステップ３３０２）
[レスポンス計算手段117]
証明装置100は、実施形態１のレスポンス計算手段112のRes1-1,…,Res1-6を行う。【００５７】
[検証手段215]
検証装置200は、以下に説明する手段Ver3-1,…,Ver3-5を行う。図１９は検証手段215の動作手順を示すフローチャートである。
Ver3-1.  s＿1,…,s＿n,  Commit＿1,…,Commit＿n,  M,Response＿1,…,Response＿nを検証装置記憶部201から読み込む（ステップ３４０１）。
Ver3-2.  c=HashCha（Commit＿1,…,Commit＿n,M）を計算する（ステップ３４０２）。
Ver3-3.  FuncVerShar（s＿1,…,s＿n,c）を計算し、FuncVerShar  （s＿1,  …,  s＿n,  c）=  rejectならrejectを出力して終了する（ステップ３４０３）。
Ver3-4.  i=1,…,nに対してChallenge＿i=H＿i（s＿i）とする（ステップ３４０４）。
Ver3-5.  i=1,…,nに対し、Verify（y＿i,  Commit＿i,  Challenge＿i,  Response＿i）を計算する。i=1,…,nに対し、Verify（y＿i,  Commit＿i,  Challenge＿i,  Response＿i）=  acceptならacceptを出力して終了し、そうでなければrejectを出力して終了する（ステップ３４０５）。【００５８】
本実施形態では、証明装置100におけるチャレンジ計算手段113の動作がコミット計算手段116の影響を受けないように改善したので、実施形態１の効果の他に、証明装置100の秘密情報の秘匿性が向上するとともに、証明装置100と検証装置200との通信回数を低減できる。【００５９】
なお、実施形態１から３で説明した証明検証方法を、コンピュータに実行させるためのプログラムに適用してもよい。【００６０】
また、本発明の証明検証システム、証明装置および検証装置と、証明検証方法と、その方法をコンピュータに実行させるためのプログラムについて、知識の証明方式を様々な暗号プロトコルを作る際の部品として用いることができ、認証方式や署名方式に応用できる。【００６１】
なお、本発明は上記実施形態に限定されることなく、発明の範囲内で種々の変形が可能であり、それらも本発明の範囲内に含まれることはいうまでもない。
【図１】
0004775597.tif 000002
【図２】
0004775597.tif 000003
【図３】
0004775597.tif 000004
【図４】
0004775597.tif 000005
【図５】
0004775597.tif 000006
【図６】
0004775597.tif 000007
【図７】
0004775597.tif 000008
【図８】
0004775597.tif 000009
【図９】
0004775597.tif 000010
【図１０】
0004775597.tif 000011
【図１１】
0004775597.tif 000012
【図１２】
0004775597.tif 000013
【図１３】
0004775597.tif 000014
【図１４】
0004775597.tif 000015
【図１５】
0004775597.tif 000016
【図１６】
0004775597.tif 000017
【図１７】
0004775597.tif 000018
【図１８】
0004775597.tif 000019
【図１９】
0004775597.tif 000020