図面 (/)

技術 証明システム、検証装置、証明装置、証明方法、およびプログラム

出願人 日本電信電話株式会社
発明者 清島奨
出願日 2015年4月16日 (4年3ヶ月経過) 出願番号 2015-083900
公開日 2016年12月8日 (2年7ヶ月経過) 公開番号 2016-208107
状態 特許登録済
技術分野 暗号化・復号化装置及び秘密通信
主要キーワード トラップドア 任意値 ロバストネス 証明装置 多項式時間アルゴリズム 素因数 共通入力 多項式時間
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2016年12月8日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (6)

課題

一方向性関数の存在のみを仮定して安全性が証明可能な統計的コンカレントnon-malleableゼロ知識アーギュメントを実現する。

解決手段

検証装置は、統計的束縛性を満たす第1コミットメント方式に則って第1任意値コミットし、第1任意値をデコミットするための第1デコミットメント情報を、統計的束縛性を満たす第2コミットメント方式に則ってコミットし、第1任意値をコミットする処理および第1デコミットメント情報をコミットする処理が正しく行われたことのゼロ知識証明を行う。証明装置は、証明に用いられた証拠識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のNP言語に属することの証拠を用い、インスタンスがNP言語に属するか、または、検証装置によるコミットメントの何れかのデコミットメント情報を持つ、という命題を証明する。

概要

背景

コンカレントnon-malleableゼロ知識性と統計的ゼロ知識性の両者を同時に満たすゼロ知識アーギュメント(統計的コンカレントnon-malleableゼロ知識アーギュメント)についての既存研究として非特許文献1に記載されたものがある。コンカレントnon-malleableゼロ知識性は中間者攻撃を行う攻撃者に対する安全性であり、統計的ゼロ知識性は超多項式時間でも命題真偽以外の情報が漏れないことを保証する安全性である。

概要

一方向性関数の存在のみを仮定して安全性が証明可能な統計的コンカレントnon-malleableゼロ知識アーギュメントを実現する。検証装置は、統計的束縛性を満たす第1コミットメント方式に則って第1任意値コミットし、第1任意値をデコミットするための第1デコミットメント情報を、統計的束縛性を満たす第2コミットメント方式に則ってコミットし、第1任意値をコミットする処理および第1デコミットメント情報をコミットする処理が正しく行われたことのゼロ知識証明を行う。証明装置は、証明に用いられた証拠識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のNP言語に属することの証拠を用い、インスタンスがNP言語に属するか、または、検証装置によるコミットメントの何れかのデコミットメント情報を持つ、という命題を証明する。

目的

本発明の課題は、一方向性関数の存在のみを仮定して安全性が証明可能な統計的コンカレントnon-malleableゼロ知識アーギュメントを実現することである

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

統計的束縛性を満たす第1コミットメント方式に則って第1任意値コミットするための情報を出力する第1コミットメント部と、前記第1任意値をデコミットするための第1デコミットメント情報を、統計的束縛性を満たす第2コミットメント方式に則ってコミットするための情報を出力する第2コミットメント部と、前記第1コミットメント部および前記第2コミットメント部の処理が正しく行われたことのゼロ知識証明を行うための情報を出力する第1証明部と、を含む検証装置と、証明に用いられた証拠識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のNP言語に属することの証拠を用い、前記インスタンスが前記NP言語に属するか、または、前記第1コミットメント部によるコミットメントの何れかのデコミットメント情報を持つ、という命題を証明するための情報を出力する第2証明部、を有する証明装置と、を有する証明システム

請求項2

請求項1の証明システムであって、前記第1証明部は、前記第1デコミットメント情報をデコミットするための第2デコミットメント情報を証拠とし、前記第2コミットメント部でコミットされた情報は前記第1デコミットメント情報であり、かつ、前記第1デコミットメント情報は前記第1コミットメント部によるコミットメントのデコミットメント情報であることを証明するための情報を出力する、証明システム。

請求項3

請求項1または2の証明システムであって、前記証明装置は、計算量的秘匿性を満たす第3コミットメント方式に則って、第2任意値をコミットするための情報を出力する第3コミットメント部を含み、前記第1証明部は、前記第2任意値のコミットメントの後に、統計的束縛性を満たす第4コミットメント方式に則って、第3任意値をコミットするための情報を出力する第4コミットメント部を含み、前記証明装置は、前記第3任意値のコミットメントの後に、前記第2任意値をデコミットするための第3デコミットメント情報を出力するデコミットメント部を含み、前記第1証明部は、証明に用いられた証拠を識別することが困難な証明方式に則って、前記第1デコミットメント情報をデコミットするための第2デコミットメント情報を証拠として用い、前記第2コミットメント部でコミットされた情報は前記第1デコミットメント情報であり、かつ、前記第1デコミットメント情報は前記第1コミットメント部によるコミットメントのデコミットメント情報であるか、または、前記第3任意値は前記第2任意値である、という命題を証明するための情報を出力するゼロ知識証明部を含む、証明システム。

請求項4

統計的束縛性を満たす第1コミットメント方式に則って、第1任意値をコミットするための情報を出力する第1コミットメント部と、前記第1任意値をデコミットするための第1デコミットメント情報を、統計的束縛性を満たす第2コミットメント方式に則ってコミットするための情報を出力する第2コミットメント部と、前記第1コミットメント部および前記第2コミットメント部の処理が正しく行われたことのゼロ知識証明を行うための情報を出力する第1証明部と、を有する検証装置。

請求項5

統計的束縛性を満たす第1コミットメント方式に則ったコミットメントのための情報を受け付ける第1コミットメント処理部と、統計的束縛性を満たす第2コミットメント方式に則ったコミットメントのための情報を受け付ける第2コミットメント処理部と、前記第1コミットメント方式に則ったコミットメントおよび前記第2コミットメント方式に則ったコミットメントが正しく行われたことのゼロ知識証明のための情報を受け付ける検証部と、証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のNP言語に属することの証拠を用い、前記インスタンスが前記NP言語に属するか、または、前記第1コミットメント方式に則ったコミットメントの何れかのデコミットメント情報を持つ、という命題を証明するための情報を出力する証明部と、を有する証明装置。

請求項6

第1コミットメント部が、統計的束縛性を満たす第1コミットメント方式に則って第1任意値をコミットするための情報を出力するステップと、第2コミットメント部が、前記第1任意値をデコミットするための第1デコミットメント情報を、統計的束縛性を満たす第2コミットメント方式に則ってコミットするための情報を出力するステップと、第1証明部が、前記第1コミットメント部および前記第2コミットメント部の処理が正しく行われたことのゼロ知識証明を行うための情報を出力するステップと、を有する証明方法

請求項7

第1コミットメント処理部が、統計的束縛性を満たす第1コミットメント方式に則ったコミットメントのための情報を受け付けるステップと、第2コミットメント処理部が、統計的束縛性を満たす第2コミットメント方式に則ったコミットメントのための情報を受け付けるステップと、検証部が、前記第1コミットメント方式に則ったコミットメントおよび前記第2コミットメント方式に則ったコミットメントが正しく行われたことのゼロ知識証明のための情報を受け付けるステップと、証明部が、証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のNP言語に属することの証拠を用い、前記インスタンスが前記NP言語に属するか、または、前記第1コミットメント方式に則ったコミットメントの何れかのデコミットメント情報を持つ、という命題を証明するための情報を出力するステップと、を有する証明方法。

請求項8

請求項6または7の証明方法の各ステップをコンピュータに実行させるためのプログラム

技術分野

0001

本発明は、暗号分野に関し、特に対話により証明を行うゼロ知識証明およびゼロ知識アーギュメントに関する。

背景技術

0002

コンカレントnon-malleableゼロ知識性と統計的ゼロ知識性の両者を同時に満たすゼロ知識アーギュメント(統計的コンカレントnon-malleableゼロ知識アーギュメント)についての既存研究として非特許文献1に記載されたものがある。コンカレントnon-malleableゼロ知識性は中間者攻撃を行う攻撃者に対する安全性であり、統計的ゼロ知識性は超多項式時間でも命題真偽以外の情報が漏れないことを保証する安全性である。

先行技術

0003

Claudio Orlandi, Rafail Ostrovsky, Vanishree Rao, Amit Sahai, and Ivan Visconti, “Statistical concurrent non-malleable zero knowledge,” In TCC, pages 167-191, 2014.

発明が解決しようとする課題

0004

しかし、非特許文献1に記載された方式は一方向性関数から構成できない構成要素を利用しており、その安全性を一方向性関数の存在を仮定するだけでは証明できない。

0005

本発明の課題は、一方向性関数の存在のみを仮定して安全性が証明可能な統計的コンカレントnon-malleableゼロ知識アーギュメントを実現することである。

課題を解決するための手段

0006

検証装置は、統計的束縛性を満たす第1コミットメント方式に則って第1任意値コミットするための情報を出力し、当該第1任意値をデコミットするための第1デコミットメント情報を、統計的束縛性を満たす第2コミットメント方式に則ってコミットするための情報を出力し、第1任意値をコミットする処理および第1デコミットメント情報をコミットする処理が正しく行われたことのゼロ知識証明を行うための情報を出力する。証明装置は、証明に用いられた証拠識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のNP言語に属することの証拠を用い、インスタンスがNP言語に属するか、または、検証装置によるコミットメントの何れかのデコミットメント情報を持つ、という命題を証明するための情報を出力する。

発明の効果

0007

この場合、攻撃者が検証装置として証明装置と通信を行っても中間者攻撃に有益な情報を得ることができず、さらに超多項式時間の計算能力を用いても通信系列から秘密情報を得ることはできない。また、上述のようなコミットメント方式、ゼロ知識証明方式、ゼロ知識アーギュメント方式は、任意の一方向性関数から構成できる。そのため、一方向性関数の存在のみを仮定して安全性が証明可能な統計的コンカレントnon-malleableゼロ知識アーギュメントを実現できる。

図面の簡単な説明

0008

図1は実施形態の証明システム機能構成を例示したブロック図である。
図2は実施形態の証明方法を説明するためのシーケンス図である。
図3Aおよび図3Bは実施形態の方式が統計的コンカレントnon-malleableゼロ知識アーギュメントであることを説明するための概念図である。
図4は第2実施形態の検証装置の証明部および証明装置の検証部の機能構成を例示したブロック図である。
図5は第2実施形態の検証装置の証明部および証明装置の検証部の処理を説明するためのシーケンス図である。

実施例

0009

以下、本発明の実施形態を説明する。
[定義]
まず、実施形態で使用する用語を定義する。
実施形態では、証明者として機能する証明装置が検証者として機能する検証装置と通信を行うことによりゼロ知識証明を行う。ゼロ知識証明とは、証明者が「命題が真である」こと以外の知識を検証者に与えることなく、「命題が真である」ことを検証者に証明する手法である。ここで、証明者が証明する命題は「NP言語Lとインスタンス(ステートメント)xに関してx∈Lが成り立つ」ことである。この命題はNP(Non-deterministic Polynomial)に属する問題であり、その解を求める多項式時間アルゴリズムは知られていないが、多項式サイズの証拠(witness)が与えられれば、解の正しさを多項式時間で検証できる判定問題である。NP言語Lの例は「正しく生成されたRSA暗号公開鍵集合」であり、インスタンスxの例は「特定の公開鍵」である。この場合の証拠wの例は公開鍵の素因数からなる列である。証明者と検証者は共通入力としてNP言語Lとインスタンスxを持ち、更に証明者はx∈Lであることの証拠wを持つ。

0010

ゼロ知識証明の安全性は、以下の完全性健全性、およびゼロ知識性によって定義される。
完全性:x∈Lのとき、証明者と検証者とが適切なプロトコルに従うならば、証明は成功である。
健全性:x∈Lでないとき、どのような証明者も証明に失敗する。ここではプロトコルに従わない悪意を持った証明者も考慮する。
ゼロ知識性:x∈Lならば、どのような多項式時間の計算能力を持つ検証者に対しても命題が真(x∈L)であること以外の情報(例えば、証拠wに関する情報)は漏れない。ここでもプロトコルに従わない悪意を持った検証者も考慮する。

0011

ここで健全性において多項式時間の計算能力を持つ証明者のみを考慮したものをゼロ知識アーギュメントと呼ぶ。また、完全性および健全性を満たし、健全性において多項式時間の計算能力を持つ証明者のみを考慮したものをアーギュメントと呼ぶ。

0012

ゼロ知識証明およびゼロ知識アーギュメントは単独でも認証などにおいて有用であり、さらに他の暗号プロトコルの構成要素としても有用であることが知られている。ゼロ知識証明およびゼロ知識アーギュメントに関しては様々な追加的な性質や安全性が提案されている。そのうち、各実施形態に関連するのは以下に挙げるコンカレントnon-malleableゼロ知識性と統計的ゼロ知識性である。

0013

コンカレントnon-malleableゼロ知識性は中間者攻撃を行う攻撃者に対する安全性である。特に、コンカレントnon-malleableゼロ知識性は複数の証明者および検証者と同時に通信を行う攻撃者に対し、証明者との通信を利用して検証者に対して攻撃を行うことができないことを保証する。つまり、証明者と通信しながら検証者と通信を行う状況においても、攻撃者は証拠を知っている命題しか証明することができないことを保証する。コンカレントnon-malleableゼロ知識性を持つ方式には、プロトコルが同時に実行される可能性がある状況でも安全に使用できるという長所がある。例えばインターネットなどの非同期ネットワーク上では複数のゼロ知識証明を同時実行しないようにすることは困難であるためこのようなネットワーク上でゼロ知識証明(またはゼロ知識アーギュメント)を利用するためにはコンカレントnon-malleableゼロ知識性が必要となる。

0014

統計的ゼロ知識性は超多項式時間でも命題の真偽以外の情報が漏れないことを保証する安全性である。つまり、多項式時間の計算能力を持つ任意の検証者に対し、統計的ゼロ知識性は証明者−検証者間の通信系列から超多項式時間でも命題の真偽以外の情報が漏れないことを保証する。すなわち、ゼロ知識証明に対する攻撃は、(1)プロトコル実行中に行う攻撃(証明者に送る情報を悪意あるものに変更する攻撃)と、(2)プロトコル実行後に行う攻撃(通信系列から秘密情報を抜き出そうとする攻撃)の二つの段階に分けることができる。検証者(攻撃者)は、(1)の攻撃を行う際には多項式時間の計算能力を持っており、(2)の攻撃を行う際には超多項式時間の計算能力をもっていると仮定する。統計的ゼロ知識性は、このような仮定のもとで命題の真偽以外の情報が攻撃者に漏れないことを保証する。一方、通常のゼロ知識性は証明者−検証者間の通信系列から多項式時間では命題の真偽以外の情報が漏れないことのみを保証する。統計的ゼロ知識性には、プロトコル実行後に攻撃者の計算能力が劇的に増加した場合でも情報が漏れないという長所がある。つまり、通常のゼロ知識性では技術の進歩などによりプロトコル実行後に攻撃者の能力が想定よりも高くなった場合は情報が漏れる可能性があるのに対し、統計的ゼロ知識性ではこのようなことは起きない。

0015

コンカレントnon-malleableゼロ知識性と統計的ゼロ知識性の両者を同時に満たすゼロ知識アーギュメントを統計的コンカレントnon-malleableゼロ知識アーギュメントと呼ぶ。

0016

計算量的non-malleableゼロ知識性は多項式時間で中間者攻撃が行えないことを保証する安全性である。計算量的non-malleableゼロ知識性を持つゼロ知識証明プロトコルを計算量的non-malleable zero-knowledge proof of knowledgeプロトコルと呼ぶ。

0017

証拠識別困難(witness-indistinguishable)とは、証明者が命題が成り立つことを証明するために用いた証拠を検証者が識別することが困難であることである。統計的証拠識別困難とは、証明者が命題が成り立つことを証明するために用いた証拠を検証者が識別することが統計的に困難であることである。統計的証拠識別困難である場合、超多項式時間の計算能力を持つ検証者であっても証拠を識別することが困難である(証拠を識別できる確率が無視できる)。証拠識別困難な証明を証拠識別困難証明(witness-indistinguishable proof of knowledge)と呼び、拠識別困難証明のプロトコルをWIPOKと表記する。また、統計的証拠識別困難なアーギュメントを統計的証拠識別困難アーギュメント(statistical witness-indistinguishable argument of knowledge)と呼び、統計的証拠識別困難アーギュメントのプロトコルをsWIAOKと表記する。WIPOKおよびsWIAOKの例は、参考文献1(Manuel Blum, “How to prove a theorem so no one else can claim it,” In In: Proceedings of the International Congress of Mathematicians, pages 1444-1451, 1987.)に記載されたハミルトン閉路問題の証明である。以下ではWIPOKのラウンド数をRWIと表記する。

0018

コミットメント方式(ビットコミットメント方式)とは、送信者受信者との間で行われる暗号理論に基づくプロトコルであり、送信者が所望の値を秘密裏にコミットするコミットフェーズと、送信者が後にその値を公開して受信者がそれを検証するデコミットフェーズ(公開フェーズ)とを有する。コミットメント方式では、秘匿性(hiding property)および拘束性(binding property)の2つの安全性が定義される。秘匿性は、受信者がデコミットフェーズの前にコミットされた値の情報を知ることができないことを保証する。拘束性は、デコミットフェーズ時に送信者がコミットした値と異なる値を公開できないことを保証する。統計的秘匿性(statistical hiding property)は、超多項式時間の計算能力を持つ受信者でもデコミットフェーズの前にコミットされた値の情報を知ることができないことを保証する。統計的束縛性(statistical binding property)は、超多項式時間の計算能力を持つ送信者でもデコミットフェーズ時にコミットした値と異なる値を公開できないことを保証する。統計的束縛性を満たすコミットメント方式をComSBと表記し、ComSBのラウンド数をRSBと表記する。ComSBの例は、参考文献2(Moni Naor, “Bit commitment using pseudo-randomness,” J. Cryptology, 4(2):151-158, 1991.)に記載されている。統計的秘匿性を満たすコミットメント方式をComSHと表記し、ComSHのラウンド数をRSHと表記する。ComSHの例は、参考文献3(Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil P. Vadhan, “Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function,” SIAM J. Comput., 39(3):1153-1218, 2009.)に記載されている。

0019

並行抜き出し可能なコミットメント方式(concurrently extractable commitment scheme)とは、様々な値を並行にコミットしてくる攻撃者である送信者に対して多項式時間の計算能力を持つ抜き出し者が存在し、その抜き出し者がコミットされた値を抽出することが可能なコミットメント方式を意味する。並行抜き出し可能なコミットメント方式は統計的束縛性を持つ。並行抜き出し可能なコミットメント方式をCEComと表記する。CEComの例は、参考文献4(Daniele Micciancio, Shien Jin Ong, Amit Sahai, and Salil Vadhan, “Concurrent zero knowledge without complexity assumptions,” Cryptology ePrint Archive, Report 2005/286, 2005.)の「Protocol 3.2」である。例えば、この「Protocol 3.2」においてパラメータをk=ω(R log n)としたものを例示できる。ただし、ω(R log n)はR log nよりも漸近的に大きい任意の関数を表し、例えばR(log n)2である。RはRSH,RSB,RWIのうち最大のものを表す(R=max(RSH,RSB,RWI))。

0020

WIPOK、sWIAOK、ComSB、ComSH、CEComは確率的な暗号プロトコルであり、すべて任意の一方向性関数から構成できることが知られている。

0021

[第1実施形態]
次に、図面を参照して第1実施形態を説明する。
<構成>
図1に例示するように、本形態の証明システム1は検証装置11および証明装置12を有する。検証装置11は、任意値選択部110、コミットメント部111(第1コミットメント部)、コミットメント部112(第2コミットメント部)、証明部113、検証部114、および記憶部115を有する。証明装置12は、コミットメント処理部121、122、検証部123、および証明部124を有する。各装置は、例えば、通信装置、ならびに、CPU(central processing unit)等のプロセッサハードウェア・プロセッサ)およびRAM(random-access memory)・ROM(read-only memory)等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは1個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めROM等に記録されていてもよい。また、CPUのようにプログラムが読み込まれることで機能構成を実現する電子回路(circuitry)ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、1個の装置を構成する電子回路が複数のCPUを含んでいてもよい。

0022

<処理>
事前処理として、正の整数であるセキュリティパラメータn、所定のNP言語L、インスタンスx∈L、タグid∈{0,1}nが検証装置11(図1)の記憶部115および証明装置12の記憶部125に格納される。証明装置12の記憶部125には、さらにx∈Lであることの証拠wが格納される。証拠wは検証装置11に対して秘匿される秘密情報である。

0023

次に証明装置12が証拠wを用い、検証装置11にx∈Lであることを証明する処理を説明する。

0024

ステージ1:検証装置11がトラップドアにコミット>
図2に例示するように、まず、検証装置11(図1)の任意値選択部110が任意値rv∈{0,1}n(第1任意値)を選択する。例えば、任意値選択部110は乱数発生装置等を用いてランダムに任意値rvを選択してもよいし、複数個の候補から予め定められた順序で選択された値を任意値rvとしてもよい。任意値rvは記憶部115に格納される(ステップS110)。

0025

コミットメント部111は、記憶部115から任意値rvを読み込み、統計的束縛性を満たす第1コミットメント方式(例えばComSB)に則って、証明装置12のコミットメント処理部121との間で相互通信を行い、任意値rvのコミットメントを行う。このコミットメントでは、コミットメント部111が任意値rvをコミットするための情報Cを生成し、当該情報Cをコミットメント処理部121に送信(出力)する。例えば、情報Cはrvをデコミットするためのデコミットメント情報(rv,d)(第1デコミットメント情報)に対応する関数値であり、dは乱数などの任意値である。コミットメント部111はデコミットメント情報(rv,d)を記憶部115に格納する。さらにその他の通信が行われてもよい。コミットメント処理部121は情報Cを受信して(受け付けて)記憶部125に格納する(ステップS111)。

0026

コミットメント部112は、記憶部115からデコミットメント情報(rv,d)を読み込み、統計的束縛性を満たす第2コミットメント方式(例えばCECom)に則って、証明装置12のコミットメント処理部122との間で相互通信を行い、デコミットメント情報(rv,d)(すなわち「トラップドア」)のコミットメントを行う。このコミットメントでは、コミットメント部112がデコミットメント情報(rv,d)をコミットするための情報C’を生成し、当該情報C’をコミットメント処理部121に送信(出力)する。例えば、情報C’は(rv,d)をデコミットするためのデコミットメント情報((rv,d),d’)(第2デコミットメント情報)に対応する関数値であり、d’は乱数などの任意値である。コミットメント部112はデコミットメント情報((rv,d),d’)を記憶部115に格納する。さらにその他の通信が行われてもよい。コミットメント処理部122は情報C’を受信して(受け付けて)記憶部125に格納する(ステップS112)。

0027

<ステージ2:検証装置11がトラップドアの知識を証明>
次に証明部113が検証部123との間で相互通信を行い、検証部123に対し、コミットメント部111の処理(ステップS111)およびコミットメント部112の処理(ステップS112)、すなわちステージ1が正しく行われたことのゼロ知識証明を行う。このゼロ知識証明には、例えば計算量的non-malleableゼロ知識性を持つゼロ知識証明プロトコルを用いる。ゼロ知識証明の過程において、証明部113はこのゼロ知識証明を行うための情報を送信(出力)し、検証部123はこの情報を用いて検証を行う。例えば、証明部113は、記憶部115から読み込んだデコミットメント情報((rv,d),d’)を証拠とし、コミットメント部112でコミットされた情報は(rv,d)であり、かつ、(rv,d)はコミットメント部111によるコミットメントのデコミットメント情報であることを検証部123に対して証明(ゼロ知識証明)するための情報を出力する。この情報は記憶部115,125に格納されているタグidにも対応する。検証部123は、この情報および記憶部125から読み込んだid,C,C’を用いて検証を行う(ステップS113)。

0028

<ステージ3:証明装置12が「x∈Lまたはトラップドアを知っていること」を証明>
証明部124は、記憶部125からx,L,wを読み込み、証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式(例えば、sWIAOK)に則って、所定のインスタンスが所定のNP言語に属することx∈Lの証拠wを用い、「インスタンスxがNP言語Lに属するx∈Lか、または、コミットメント部111によるコミットメントの何れかのデコミットメント情報(rv’,d’)を持つ」という命題を検証部114に対して証明する。この過程で、証明部124はこの証明のための情報を送信(出力)し、検証部114はこの情報を用いて検証を行う。この命題は、x∈Lを証明するか、(rv’,d’)を持つことを証明すればよいが、証明部124は、証拠wを用いてx∈Lを証明する(ステップS124)。

0029

<統計的コンカレントnon-malleableゼロ知識アーギュメントである理由>
本形態の方式は一方向性関数から構成可能な構成要素のみを用いて構成され、一方向性関数の存在を仮定することで実現できる。このような仮定のもと、本形態の方式が統計的コンカレントnon-malleableゼロ知識アーギュメントであることを示す。

0030

図3Aおよび図3Bに例示するように、端末装置Bが検証装置として端末装置A(検証装置)と通信を行い(図3A)、その結果を利用し、証明装置として他の検証装置C(検証装置)に対して中間者攻撃を行う状況(図3B)を想定する。本形態の方式が統計的コンカレントnon-malleableゼロ知識アーギュメントであることを示すためには、端末装置Bが多項式時間の計算能力を有する場合であっても、証明装置として機能する端末装置Aとの通信を利用し、他の検証装置Cに対して中間者攻撃を行う(証拠を知らない命題を証明する)ことができないことを示す必要がある。ここで、説明の簡略化のため端末装置Bが端末装置A,Cのみと通信を行う場合を示すが、端末装置Bはその他の複数の端末装置と同様な通信を行っている。

0031

図3Aの場面では端末装置Bが検証装置11として機能する。ステップS111〜S113では、検証装置11として機能する端末装置Bが証明装置12として機能する端末装置Aに対してコミットしたり、ゼロ知識証明を行ったりする。この処理では端末装置Aの証拠などの秘密情報は用いられていない。そのため、ステップS111〜S113で端末装置Bが端末装置Aから中間者攻撃に有効な秘密情報を得ることはない。一方、ステップS124では、証明装置12として機能する端末装置Aが検証装置11として機能する端末装置Bへのゼロ知識アーギュメントを行う。このゼロ知識アーギュメントでは端末装置Aが証拠wを用いてx∈Lを証明する。この端末装置Aの挙動を端末装置Bが自らシミュレートすることができるのであれば、端末装置Aは端末装置Bに証拠wに関する情報を一切与えていないことになる。すなわち、端末装置Aが端末装置Bでシミュレート可能な通信しか行っていないのであれば、端末装置Bは自ら知り得る情報よりも多くの情報を端末装置Aから得ていないことになる。

0032

ステップS124では、「インスタンスxがNP言語Lに属するx∈Lか、または、コミットメント部111によるコミットメントの何れかのデコミットメント情報(rv’,d’)を持つ」という命題を証明すればよい。ステップS111,S112のコミットメント方式はいずれも統計的束縛性を満たし、ステップS113のゼロ知識証明の安全性から、検証装置11として機能する端末装置Bは任意値rvのコミットメントのデコミットメント情報(rv,d)を知っていることが保証される。そのため端末装置Bは、デコミットメント情報(rv,d)を証拠として用い、「インスタンスxがNP言語Lに属するx∈Lか、または、コミットメント部111によるコミットメントの何れかのデコミットメント情報(rv’,d’)を持つ」という命題を証明できる。

0033

またステップS124では、証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式が用いられる。そのため、このアーギュメント方式では、たとえ超多項式時間の計算能力を用いたとしても、証拠wを用いて「x∈Lである」ことを証明したのか、証拠(rv,d)を用いて「コミットメント部111によるコミットメントの何れかのデコミットメント情報(rv’,d’)を持つ」ことを証明したのかを識別できない。この統計的安全性により、統計的ゼロ知識性が証明できる。

0034

よって端末装置Bは、証明装置12として機能する端末装置Aが行う通信を自分自身でシミュレートできる。そのため、図3Aでの端末装置A,B間での通信は、端末装置Bが知る以上の情報を端末装置Bに与えていないことになる。したがって、端末装置Bは証明装置12として機能する端末装置Aと通信しても、図3Bの場面で検証装置11として機能する端末装置Cに対し、端末装置Bが証拠を知らない命題を証明することはできない。このことは、端末装置Bが複数の端末装置Aおよび複数の端末装置Cと同様の通信を行う場合でも同じである。以上より、本形態の方式は統計的コンカレントnon-malleableゼロ知識アーギュメントであり、一方向性関数の存在を仮定するだけで安全性を証明できる。

0035

[第2実施形態]
第2実施形態では、前述のステージ2のゼロ知識証明で用いる計算量的non-malleable zero-knowledge proof of knowledgeプロトコルの具体例を示す。以下では、第1実施形態との相違点を中心に説明し、共通部分については第1実施形態で用いた参照番号を流用して説明を簡略化する。

0036

本形態では、任意の一方向性関数から構成できる公知のmax(RSB+2,RWI)−ロバストのCCA安全コミットメント方式CCAComを追加で使用する(例えば、参考文献5「Vipul Goyal, Huijia Lin, Omkant Pandey, Rafael Pass, and Amit Sahai, “Round-effcient concurrently composable secure computation via a robust extraction lemma,” In TCC, 2015.」等参照)。ここで、CCA安全コミットメント方式はコミットメントの秘匿性を超多項式時間で破るオラクルに攻撃者がアクセスする場合でも秘匿性が成り立つコミットメント方式であり、ロバストネスはCCA安全コミットメント方式の性質の一つである。

0037

<構成>
図1に例示するように、本形態の証明システム2は検証装置21および証明装置22を有する。検証装置21は、任意値選択部110、コミットメント部111、コミットメント部112、証明部213、検証部114、および記憶部115を有する。証明装置22は、コミットメント処理部121、122、検証部223、および証明部124を有する。図4に例示するように、証明部213は、コミットメント処理部213b、コミットメント部213c(第4コミットメント部)、デコミットメント処理部213d、およびゼロ知識証明部213eを有する。検証部223は、任意値選択部223a、コミットメント部223b(第3コミットメント部)、コミットメント処理部223c、デコミットメント部223d(デコミットメント部)、および検証部223eを有する。

0038

<処理>
第1実施形態との相違点はステージ2のみであり、図2のステップS113に代えてS213を実行する。図5を用いてステップS213の処理を説明する。

0039

ステップS213では、計算量的non-malleableゼロ知識性を持つゼロ知識証明プロトコルを用い、証明部213が検証部223に対し、コミットメント部111の処理(ステップS111)およびコミットメント部112の処理(ステップS112)が正しく行われたことのゼロ知識証明を行う。すなわち、証明部213はこのプロトコルに従い、記憶部115から読み込んだデコミットメント情報((rv,d),d’)を証拠とし、コミットメント部112でコミットされた情報は(rv,d)であり、かつ、(rv,d)はコミットメント部111によるコミットメントのデコミットメント情報であることを検証部223に対してゼロ知識証明する。

0040

まず、任意値選択部223aが任意値rP∈{0,1}n(第2任意値)を選択する。例えば、任意値選択部223aは乱数発生装置等を用いてランダムに任意値rPを選択してもよいし、複数個の候補から予め定められた順序で選択された値を任意値rPとしてもよい。任意値rPはコミットメント部223bに送られる(ステップS223a)。

0041

コミットメント部223bは、統計的束縛性および計算量的秘匿性を満たす第3コミットメント方式(例えばCCACom)に則って、コミットメント処理部213bとの間で相互通信を行い、任意値rPのコミットメントを行う。このコミットメントでは、コミットメント部223bが任意値rPをコミットメントするための情報Eを生成し、当該情報Eをコミットメント処理部213bに送信(出力)する。例えば、情報EはrPをデコミットするためのデコミットメント情報(rP,e)(第3デコミットメント情報)に対応する関数値であり、eは乱数などの任意値である。コミットメント部223bはデコミットメント情報(rP,e)を記憶部125に格納する。コミットメント処理部213bは情報Eを受信して(受け付けて)記憶部115に格納する(ステップS213b)。

0042

任意値rPのコミットメントの後、コミットメント部213cが、統計的束縛性を満たす第4コミットメント方式(例えば、CECom)に則って、コミットメント処理部223cとの間で相互通信を行い、任意値kV∈{0,1}n(第3任意値)のコミットメントを行う。任意値kVは例えばkV=0nのような定数でよい。このコミットメントでは、コミットメント部213cが任意値kVをコミットするための情報Yを生成し、当該情報Yをコミットメント処理部223cに送信(出力)する。例えば、情報YはkVをデコミットするためのデコミットメント情報(kV,y)に対応する関数値であり、yは乱数などの任意値である。コミットメント部213cはデコミットメント情報(kV,y)を記憶部115に格納する。コミットメント処理部223cは情報Yを受信して(受け付けて)記憶部125に格納する(ステップS213c)。

0043

任意値kVのコミットメントの後、デコミットメント部223dは、記憶部125からデコミットメント情報(rP,e)を読み込み、rPをデコミット(オープン)する。例えば、デコミットメント部223dは、デコミットメント情報(rP,e)をデコミットメント処理部213dに送り、デコミットメント処理部213dは記憶部115から読み込んだ情報Eを用いてデコミットメント情報(rP,e)を検証する(ステップS223d)。

0044

ゼロ知識証明部213eは、証明に用いられた証拠を識別することが困難な証明方式(例えば、WIPOK)に則って、記憶部115から読み込んだデコミットメント情報((rv,d),d’)(第1デコミットメント情報をデコミットするための第2デコミットメント情報)を証拠として用い、「ステップS112でコミットメント部112(第2コミットメント部)によってコミットされた情報はデコミットメント情報(rv,d)(第1デコミットメント情報)であり、かつ、(rv,d)はコミットメント部111によるコミットメントのデコミットメント情報であるか、または、ステップS213cのコミットメントでコミットされた値kV(第3任意値)は任意値rP(第2任意値)である」という命題を検証部223eに対して証明する。この過程で、ゼロ知識証明部213eはこの証明のための情報を送信(出力)し、検証部223eはこの情報および記憶部125から読み込んだid,C,C’を用いて検証を行う。

0045

ここで、ステップS213bでは、コミットメント部223bが計算量的秘匿性を満たす第3コミットメント方式(例えばCCACom)に則って任意値rPのコミットメントを行っている。したがって、任意値rPのデコミットメント前のステップS213cにおいてコミットメント部213cがkV=rPをコミットすることはできない。また、ステップS213cでは、コミットメント部213cが統計的束縛性を満たす第4コミットメント方式(例えば、CECom)に則って任意値kVのコミットを行っている。したがって、ステップS213cで任意値kV以外の値をコミットしていたとることはできない。そのため、「ステップS112でコミットメント部112によってコミットされた情報はデコミットメント情報(rv,d)であり、かつ、(rv,d)はコミットメント部111によるコミットメントのデコミットメント情報であるか、または、ステップS213cのコミットメントでコミットされた値kVは任意値rPである」という命題が真であることが証明された場合、「ステップS112でコミットメント部112によってコミットされた情報はデコミットメント情報(rv,d)であり、かつ、(rv,d)はコミットメント部111によるコミットメントのデコミットメント情報である」という命題が真であるということが証明されたことになる。

0046

[特徴]
上述のように、各実施形態の方式は一方向性関数から構成可能な構成要素のみを用いて構成されているため、その安全性は一方向性関数の存在を仮定するだけで証明可能である。したがって、本方式は従来より弱い計算量仮定から統計的コンカレントnon-malleableゼロ知識アーギュメントを実現している。弱い計算量仮定は将来的に技術が発展した場合でも成り立つ可能性が高いため、本方式は従来方式よりも信頼度の高い安全性を持つことになる。

0047

[その他の変形例等]
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

0048

上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な(non-transitory)記録媒体である。このような記録媒体の例は、磁気記録装置光ディスク光磁気記録媒体半導体メモリ等である。

0049

このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売譲渡貸与等することによって行う。さらに、このプログラムをサーバコンピュータ記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

0050

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。

0051

上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。

0052

本発明は、例えば、電子商取引等での認証、公開鍵暗号方式等の暗号プロトコルでの公開鍵の正当性の検証などに利用できる。

0053

1,2証明システム
11,21検証装置
12,22 証明装置

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ