(57)【特許請求の範囲】
【請求項１】
統計的束縛性を満たす第１コミットメント方式に則って第１任意値をコミットするための情報を出力する第１コミットメント部と、
前記第１任意値をデコミットするための第１デコミットメント情報を、統計的束縛性を満たす第２コミットメント方式に則ってコミットするための情報を出力する第２コミットメント部と、
前記第１コミットメント部および前記第２コミットメント部の処理が正しく行われたことのゼロ知識証明を行うための情報を出力する第１証明部と、を含む検証装置と、
証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のＮＰ言語に属することの証拠を用い、前記インスタンスが前記ＮＰ言語に属するか、または、前記第１コミットメント部によるコミットメントの何れかのデコミットメント情報を持つ、という命題を証明するための情報を出力する第２証明部、を有する証明装置と、
を有する証明システム。
【請求項２】
請求項１の証明システムであって、
前記第１証明部は、前記第１デコミットメント情報をデコミットするための第２デコミットメント情報を証拠とし、前記第２コミットメント部でコミットされた情報は前記第１デコミットメント情報であり、かつ、前記第１デコミットメント情報は前記第１コミットメント部によるコミットメントのデコミットメント情報であることを証明するための情報を出力する、証明システム。
【請求項３】
請求項１または２の証明システムであって、
前記証明装置は、計算量的秘匿性を満たす第３コミットメント方式に則って、第２任意値をコミットするための情報を出力する第３コミットメント部を含み、
前記第１証明部は、前記第２任意値のコミットメントの後に、統計的束縛性を満たす第４コミットメント方式に則って、第３任意値をコミットするための情報を出力する第４コミットメント部を含み、
前記証明装置は、前記第３任意値のコミットメントの後に、前記第２任意値をデコミットするための第３デコミットメント情報を出力するデコミットメント部を含み、
前記第１証明部は、証明に用いられた証拠を識別することが困難な証明方式に則って、前記第１デコミットメント情報をデコミットするための第２デコミットメント情報を証拠として用い、前記第２コミットメント部でコミットされた情報は前記第１デコミットメント情報であり、かつ、前記第１デコミットメント情報は前記第１コミットメント部によるコミットメントのデコミットメント情報であるか、または、前記第３任意値は前記第２任意値である、という命題を証明するための情報を出力するゼロ知識証明部を含む、証明システム。
【請求項４】
統計的束縛性を満たす第１コミットメント方式に則って、第１任意値をコミットするための情報を出力する第１コミットメント部と、
前記第１任意値をデコミットするための第１デコミットメント情報を、統計的束縛性を満たす第２コミットメント方式に則ってコミットするための情報を出力する第２コミットメント部と、
前記第１コミットメント部および前記第２コミットメント部の処理が正しく行われたことのゼロ知識証明を行うための情報を出力する第１証明部と、
を有する検証装置。
【請求項５】
統計的束縛性を満たす第１コミットメント方式に則ったコミットメントのための情報を受け付ける第１コミットメント処理部と、
統計的束縛性を満たす第２コミットメント方式に則ったコミットメントのための情報を受け付ける第２コミットメント処理部と、
前記第１コミットメント方式に則ったコミットメントおよび前記第２コミットメント方式に則ったコミットメントが正しく行われたことのゼロ知識証明のための情報を受け付ける検証部と、
証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のＮＰ言語に属することの証拠を用い、前記インスタンスが前記ＮＰ言語に属するか、または、前記第１コミットメント方式に則ったコミットメントの何れかのデコミットメント情報を持つ、という命題を証明するための情報を出力する証明部と、
を有する証明装置。
【請求項６】
第１コミットメント部が、統計的束縛性を満たす第１コミットメント方式に則って第１任意値をコミットするための情報を出力するステップと、
第２コミットメント部が、前記第１任意値をデコミットするための第１デコミットメント情報を、統計的束縛性を満たす第２コミットメント方式に則ってコミットするための情報を出力するステップと、
第１証明部が、前記第１コミットメント部および前記第２コミットメント部の処理が正しく行われたことのゼロ知識証明を行うための情報を出力するステップと、
を有する証明方法。
【請求項７】
第１コミットメント処理部が、統計的束縛性を満たす第１コミットメント方式に則ったコミットメントのための情報を受け付けるステップと、
第２コミットメント処理部が、統計的束縛性を満たす第２コミットメント方式に則ったコミットメントのための情報を受け付けるステップと、
検証部が、前記第１コミットメント方式に則ったコミットメントおよび前記第２コミットメント方式に則ったコミットメントが正しく行われたことのゼロ知識証明のための情報を受け付けるステップと、
証明部が、証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のＮＰ言語に属することの証拠を用い、前記インスタンスが前記ＮＰ言語に属するか、または、前記第１コミットメント方式に則ったコミットメントの何れかのデコミットメント情報を持つ、という命題を証明するための情報を出力するステップと、
を有する証明方法。
【請求項８】
請求項６の証明方法の各ステップをコンピュータに実行させるためのプログラム。
【請求項９】
請求項７の証明方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号分野に関し、特に対話により証明を行うゼロ知識証明およびゼロ知識アーギュメントに関する。
【背景技術】
【０００２】
コンカレントnon-malleableゼロ知識性と統計的ゼロ知識性の両者を同時に満たすゼロ知識アーギュメント（統計的コンカレントnon-malleableゼロ知識アーギュメント）についての既存研究として非特許文献１に記載されたものがある。コンカレントnon-malleableゼロ知識性は中間者攻撃を行う攻撃者に対する安全性であり、統計的ゼロ知識性は超多項式時間でも命題の真偽以外の情報が漏れないことを保証する安全性である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Claudio Orlandi, Rafail Ostrovsky, Vanishree Rao, Amit Sahai, and Ivan Visconti, “Statistical concurrent non-malleable zero knowledge,” In TCC, pages 167-191, 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献１に記載された方式は一方向性関数から構成できない構成要素を利用しており、その安全性を一方向性関数の存在を仮定するだけでは証明できない。
【０００５】
本発明の課題は、一方向性関数の存在のみを仮定して安全性が証明可能な統計的コンカレントnon-malleableゼロ知識アーギュメントを実現することである。
【課題を解決するための手段】
【０００６】
検証装置は、統計的束縛性を満たす第１コミットメント方式に則って第１任意値をコミットするための情報を出力し、当該第１任意値をデコミットするための第１デコミットメント情報を、統計的束縛性を満たす第２コミットメント方式に則ってコミットするための情報を出力し、第１任意値をコミットする処理および第１デコミットメント情報をコミットする処理が正しく行われたことのゼロ知識証明を行うための情報を出力する。証明装置は、証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式に則って、所定のインスタンスが所定のＮＰ言語に属することの証拠を用い、インスタンスがＮＰ言語に属するか、または、検証装置によるコミットメントの何れかのデコミットメント情報を持つ、という命題を証明するための情報を出力する。
【発明の効果】
【０００７】
この場合、攻撃者が検証装置として証明装置と通信を行っても中間者攻撃に有益な情報を得ることができず、さらに超多項式時間の計算能力を用いても通信系列から秘密情報を得ることはできない。また、上述のようなコミットメント方式、ゼロ知識証明方式、ゼロ知識アーギュメント方式は、任意の一方向性関数から構成できる。そのため、一方向性関数の存在のみを仮定して安全性が証明可能な統計的コンカレントnon-malleableゼロ知識アーギュメントを実現できる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の証明システムの機能構成を例示したブロック図である。
【図２】図２は実施形態の証明方法を説明するためのシーケンス図である。
【図３】図３Ａおよび図３Ｂは実施形態の方式が統計的コンカレントnon-malleableゼロ知識アーギュメントであることを説明するための概念図である。
【図４】図４は第２実施形態の検証装置の証明部および証明装置の検証部の機能構成を例示したブロック図である。
【図５】図５は第２実施形態の検証装置の証明部および証明装置の検証部の処理を説明するためのシーケンス図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［定義］
まず、実施形態で使用する用語を定義する。
実施形態では、証明者として機能する証明装置が検証者として機能する検証装置と通信を行うことによりゼロ知識証明を行う。ゼロ知識証明とは、証明者が「命題が真である」こと以外の知識を検証者に与えることなく、「命題が真である」ことを検証者に証明する手法である。ここで、証明者が証明する命題は「ＮＰ言語Ｌとインスタンス（ステートメント）ｘに関してｘ∈Ｌが成り立つ」ことである。この命題はＮＰ（Non-deterministic Polynomial）に属する問題であり、その解を求める多項式時間アルゴリズムは知られていないが、多項式サイズの証拠（witness）が与えられれば、解の正しさを多項式時間で検証できる判定問題である。ＮＰ言語Ｌの例は「正しく生成されたＲＳＡ暗号の公開鍵の集合」であり、インスタンスｘの例は「特定の公開鍵」である。この場合の証拠ｗの例は公開鍵の素因数からなる列である。証明者と検証者は共通入力としてＮＰ言語Ｌとインスタンスｘを持ち、更に証明者はｘ∈Ｌであることの証拠ｗを持つ。
【００１０】
ゼロ知識証明の安全性は、以下の完全性、健全性、およびゼロ知識性によって定義される。
完全性：ｘ∈Ｌのとき、証明者と検証者とが適切なプロトコルに従うならば、証明は成功である。
健全性：ｘ∈Ｌでないとき、どのような証明者も証明に失敗する。ここではプロトコルに従わない悪意を持った証明者も考慮する。
ゼロ知識性：ｘ∈Ｌならば、どのような多項式時間の計算能力を持つ検証者に対しても命題が真（ｘ∈Ｌ）であること以外の情報（例えば、証拠ｗに関する情報）は漏れない。ここでもプロトコルに従わない悪意を持った検証者も考慮する。
【００１１】
ここで健全性において多項式時間の計算能力を持つ証明者のみを考慮したものをゼロ知識アーギュメントと呼ぶ。また、完全性および健全性を満たし、健全性において多項式時間の計算能力を持つ証明者のみを考慮したものをアーギュメントと呼ぶ。
【００１２】
ゼロ知識証明およびゼロ知識アーギュメントは単独でも認証などにおいて有用であり、さらに他の暗号プロトコルの構成要素としても有用であることが知られている。ゼロ知識証明およびゼロ知識アーギュメントに関しては様々な追加的な性質や安全性が提案されている。そのうち、各実施形態に関連するのは以下に挙げるコンカレントnon-malleableゼロ知識性と統計的ゼロ知識性である。
【００１３】
コンカレントnon-malleableゼロ知識性は中間者攻撃を行う攻撃者に対する安全性である。特に、コンカレントnon-malleableゼロ知識性は複数の証明者および検証者と同時に通信を行う攻撃者に対し、証明者との通信を利用して検証者に対して攻撃を行うことができないことを保証する。つまり、証明者と通信しながら検証者と通信を行う状況においても、攻撃者は証拠を知っている命題しか証明することができないことを保証する。コンカレントnon-malleableゼロ知識性を持つ方式には、プロトコルが同時に実行される可能性がある状況でも安全に使用できるという長所がある。例えばインターネットなどの非同期ネットワーク上では複数のゼロ知識証明を同時実行しないようにすることは困難であるためこのようなネットワーク上でゼロ知識証明（またはゼロ知識アーギュメント）を利用するためにはコンカレントnon-malleableゼロ知識性が必要となる。
【００１４】
統計的ゼロ知識性は超多項式時間でも命題の真偽以外の情報が漏れないことを保証する安全性である。つまり、多項式時間の計算能力を持つ任意の検証者に対し、統計的ゼロ知識性は証明者−検証者間の通信系列から超多項式時間でも命題の真偽以外の情報が漏れないことを保証する。すなわち、ゼロ知識証明に対する攻撃は、（１）プロトコル実行中に行う攻撃（証明者に送る情報を悪意あるものに変更する攻撃）と、（２）プロトコル実行後に行う攻撃（通信系列から秘密情報を抜き出そうとする攻撃）の二つの段階に分けることができる。検証者（攻撃者）は、（１）の攻撃を行う際には多項式時間の計算能力を持っており、（２）の攻撃を行う際には超多項式時間の計算能力をもっていると仮定する。統計的ゼロ知識性は、このような仮定のもとで命題の真偽以外の情報が攻撃者に漏れないことを保証する。一方、通常のゼロ知識性は証明者−検証者間の通信系列から多項式時間では命題の真偽以外の情報が漏れないことのみを保証する。統計的ゼロ知識性には、プロトコル実行後に攻撃者の計算能力が劇的に増加した場合でも情報が漏れないという長所がある。つまり、通常のゼロ知識性では技術の進歩などによりプロトコル実行後に攻撃者の能力が想定よりも高くなった場合は情報が漏れる可能性があるのに対し、統計的ゼロ知識性ではこのようなことは起きない。
【００１５】
コンカレントnon-malleableゼロ知識性と統計的ゼロ知識性の両者を同時に満たすゼロ知識アーギュメントを統計的コンカレントnon-malleableゼロ知識アーギュメントと呼ぶ。
【００１６】
計算量的non-malleableゼロ知識性は多項式時間で中間者攻撃が行えないことを保証する安全性である。計算量的non-malleableゼロ知識性を持つゼロ知識証明プロトコルを計算量的non-malleable zero-knowledge proof of knowledgeプロトコルと呼ぶ。
【００１７】
証拠識別困難（witness-indistinguishable）とは、証明者が命題が成り立つことを証明するために用いた証拠を検証者が識別することが困難であることである。統計的証拠識別困難とは、証明者が命題が成り立つことを証明するために用いた証拠を検証者が識別することが統計的に困難であることである。統計的証拠識別困難である場合、超多項式時間の計算能力を持つ検証者であっても証拠を識別することが困難である（証拠を識別できる確率が無視できる）。証拠識別困難な証明を証拠識別困難証明（witness-indistinguishable proof of knowledge）と呼び、拠識別困難証明のプロトコルをＷＩＰＯＫと表記する。また、統計的証拠識別困難なアーギュメントを統計的証拠識別困難アーギュメント（statistical witness-indistinguishable argument of knowledge）と呼び、統計的証拠識別困難アーギュメントのプロトコルをｓＷＩＡＯＫと表記する。ＷＩＰＯＫおよびｓＷＩＡＯＫの例は、参考文献１（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.）に記載されたハミルトン閉路問題の証明である。以下ではＷＩＰＯＫのラウンド数をＲＷＩと表記する。
【００１８】
コミットメント方式（ビットコミットメント方式）とは、送信者と受信者との間で行われる暗号理論に基づくプロトコルであり、送信者が所望の値を秘密裏にコミットするコミットフェーズと、送信者が後にその値を公開して受信者がそれを検証するデコミットフェーズ（公開フェーズ）とを有する。コミットメント方式では、秘匿性（hiding property）および拘束性（binding property）の２つの安全性が定義される。秘匿性は、受信者がデコミットフェーズの前にコミットされた値の情報を知ることができないことを保証する。拘束性は、デコミットフェーズ時に送信者がコミットした値と異なる値を公開できないことを保証する。統計的秘匿性（statistical hiding property）は、超多項式時間の計算能力を持つ受信者でもデコミットフェーズの前にコミットされた値の情報を知ることができないことを保証する。統計的束縛性（statistical binding property）は、超多項式時間の計算能力を持つ送信者でもデコミットフェーズ時にコミットした値と異なる値を公開できないことを保証する。統計的束縛性を満たすコミットメント方式をＣｏｍＳＢと表記し、ＣｏｍＳＢのラウンド数をＲＳＢと表記する。ＣｏｍＳＢの例は、参考文献２（Moni Naor, “Bit commitment using pseudo-randomness,” J. Cryptology, 4(2):151-158, 1991.）に記載されている。統計的秘匿性を満たすコミットメント方式をＣｏｍＳＨと表記し、ＣｏｍＳＨのラウンド数をＲＳＨと表記する。ＣｏｍＳＨの例は、参考文献３（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.）に記載されている。
【００１９】
並行抜き出し可能なコミットメント方式（concurrently extractable commitment scheme）とは、様々な値を並行にコミットしてくる攻撃者である送信者に対して多項式時間の計算能力を持つ抜き出し者が存在し、その抜き出し者がコミットされた値を抽出することが可能なコミットメント方式を意味する。並行抜き出し可能なコミットメント方式は統計的束縛性を持つ。並行抜き出し可能なコミットメント方式をＣＥＣｏｍと表記する。ＣＥＣｏｍの例は、参考文献４（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」においてパラメータをｋ＝ω（Ｒ ｌｏｇ ｎ）としたものを例示できる。ただし、ω（Ｒ ｌｏｇ ｎ）はＲ ｌｏｇ ｎよりも漸近的に大きい任意の関数を表し、例えばＲ（ｌｏｇ ｎ）２である。ＲはＲＳＨ，ＲＳＢ，ＲＷＩのうち最大のものを表す（Ｒ＝ｍａｘ（ＲＳＨ，ＲＳＢ，ＲＷＩ））。
【００２０】
ＷＩＰＯＫ、ｓＷＩＡＯＫ、ＣｏｍＳＢ、ＣｏｍＳＨ、ＣＥＣｏｍは確率的な暗号プロトコルであり、すべて任意の一方向性関数から構成できることが知られている。
【００２１】
［第１実施形態］
次に、図面を参照して第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の証明システム１は検証装置１１および証明装置１２を有する。検証装置１１は、任意値選択部１１０、コミットメント部１１１（第１コミットメント部）、コミットメント部１１２（第２コミットメント部）、証明部１１３、検証部１１４、および記憶部１１５を有する。証明装置１２は、コミットメント処理部１２１、１２２、検証部１２３、および証明部１２４を有する。各装置は、例えば、通信装置、ならびに、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００２２】
＜処理＞
事前処理として、正の整数であるセキュリティパラメータｎ、所定のＮＰ言語Ｌ、インスタンスｘ∈Ｌ、タグｉｄ∈｛０，１｝ｎが検証装置１１（図１）の記憶部１１５および証明装置１２の記憶部１２５に格納される。証明装置１２の記憶部１２５には、さらにｘ∈Ｌであることの証拠ｗが格納される。証拠ｗは検証装置１１に対して秘匿される秘密情報である。
【００２３】
次に証明装置１２が証拠ｗを用い、検証装置１１にｘ∈Ｌであることを証明する処理を説明する。
【００２４】
＜ステージ１：検証装置１１がトラップドアにコミット＞
図２に例示するように、まず、検証装置１１（図１）の任意値選択部１１０が任意値ｒｖ∈｛０，１｝ｎ（第１任意値）を選択する。例えば、任意値選択部１１０は乱数発生装置等を用いてランダムに任意値ｒｖを選択してもよいし、複数個の候補から予め定められた順序で選択された値を任意値ｒｖとしてもよい。任意値ｒｖは記憶部１１５に格納される（ステップＳ１１０）。
【００２５】
コミットメント部１１１は、記憶部１１５から任意値ｒｖを読み込み、統計的束縛性を満たす第１コミットメント方式（例えばＣｏｍＳＢ）に則って、証明装置１２のコミットメント処理部１２１との間で相互通信を行い、任意値ｒｖのコミットメントを行う。このコミットメントでは、コミットメント部１１１が任意値ｒｖをコミットするための情報Ｃを生成し、当該情報Ｃをコミットメント処理部１２１に送信（出力）する。例えば、情報Ｃはｒｖをデコミットするためのデコミットメント情報（ｒｖ，ｄ）（第１デコミットメント情報）に対応する関数値であり、ｄは乱数などの任意値である。コミットメント部１１１はデコミットメント情報（ｒｖ，ｄ）を記憶部１１５に格納する。さらにその他の通信が行われてもよい。コミットメント処理部１２１は情報Ｃを受信して（受け付けて）記憶部１２５に格納する（ステップＳ１１１）。
【００２６】
コミットメント部１１２は、記憶部１１５からデコミットメント情報（ｒｖ，ｄ）を読み込み、統計的束縛性を満たす第２コミットメント方式（例えばＣＥＣｏｍ）に則って、証明装置１２のコミットメント処理部１２２との間で相互通信を行い、デコミットメント情報（ｒｖ，ｄ）（すなわち「トラップドア」）のコミットメントを行う。このコミットメントでは、コミットメント部１１２がデコミットメント情報（ｒｖ，ｄ）をコミットするための情報Ｃ’を生成し、当該情報Ｃ’をコミットメント処理部１２１に送信（出力）する。例えば、情報Ｃ’は（ｒｖ，ｄ）をデコミットするためのデコミットメント情報（（ｒｖ，ｄ），ｄ’）（第２デコミットメント情報）に対応する関数値であり、ｄ’は乱数などの任意値である。コミットメント部１１２はデコミットメント情報（（ｒｖ，ｄ），ｄ’）を記憶部１１５に格納する。さらにその他の通信が行われてもよい。コミットメント処理部１２２は情報Ｃ’を受信して（受け付けて）記憶部１２５に格納する（ステップＳ１１２）。
【００２７】
＜ステージ２：検証装置１１がトラップドアの知識を証明＞
次に証明部１１３が検証部１２３との間で相互通信を行い、検証部１２３に対し、コミットメント部１１１の処理（ステップＳ１１１）およびコミットメント部１１２の処理（ステップＳ１１２）、すなわちステージ１が正しく行われたことのゼロ知識証明を行う。このゼロ知識証明には、例えば計算量的non-malleableゼロ知識性を持つゼロ知識証明プロトコルを用いる。ゼロ知識証明の過程において、証明部１１３はこのゼロ知識証明を行うための情報を送信（出力）し、検証部１２３はこの情報を用いて検証を行う。例えば、証明部１１３は、記憶部１１５から読み込んだデコミットメント情報（（ｒｖ，ｄ），ｄ’）を証拠とし、コミットメント部１１２でコミットされた情報は（ｒｖ，ｄ）であり、かつ、（ｒｖ，ｄ）はコミットメント部１１１によるコミットメントのデコミットメント情報であることを検証部１２３に対して証明（ゼロ知識証明）するための情報を出力する。この情報は記憶部１１５，１２５に格納されているタグｉｄにも対応する。検証部１２３は、この情報および記憶部１２５から読み込んだｉｄ，Ｃ，Ｃ’を用いて検証を行う（ステップＳ１１３）。
【００２８】
＜ステージ３：証明装置１２が「ｘ∈Ｌまたはトラップドアを知っていること」を証明＞
証明部１２４は、記憶部１２５からｘ，Ｌ，ｗを読み込み、証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式（例えば、ｓＷＩＡＯＫ）に則って、所定のインスタンスが所定のＮＰ言語に属することｘ∈Ｌの証拠ｗを用い、「インスタンスｘがＮＰ言語Ｌに属するｘ∈Ｌか、または、コミットメント部１１１によるコミットメントの何れかのデコミットメント情報（ｒｖ’，ｄ’）を持つ」という命題を検証部１１４に対して証明する。この過程で、証明部１２４はこの証明のための情報を送信（出力）し、検証部１１４はこの情報を用いて検証を行う。この命題は、ｘ∈Ｌを証明するか、（ｒｖ’，ｄ’）を持つことを証明すればよいが、証明部１２４は、証拠ｗを用いてｘ∈Ｌを証明する（ステップＳ１２４）。
【００２９】
＜統計的コンカレントnon-malleableゼロ知識アーギュメントである理由＞
本形態の方式は一方向性関数から構成可能な構成要素のみを用いて構成され、一方向性関数の存在を仮定することで実現できる。このような仮定のもと、本形態の方式が統計的コンカレントnon-malleableゼロ知識アーギュメントであることを示す。
【００３０】
図３Ａおよび図３Ｂに例示するように、端末装置Ｂが検証装置として端末装置Ａ（検証装置）と通信を行い（図３Ａ）、その結果を利用し、証明装置として他の検証装置Ｃ（検証装置）に対して中間者攻撃を行う状況（図３Ｂ）を想定する。本形態の方式が統計的コンカレントnon-malleableゼロ知識アーギュメントであることを示すためには、端末装置Ｂが多項式時間の計算能力を有する場合であっても、証明装置として機能する端末装置Ａとの通信を利用し、他の検証装置Ｃに対して中間者攻撃を行う（証拠を知らない命題を証明する）ことができないことを示す必要がある。ここで、説明の簡略化のため端末装置Ｂが端末装置Ａ，Ｃのみと通信を行う場合を示すが、端末装置Ｂはその他の複数の端末装置と同様な通信を行っている。
【００３１】
図３Ａの場面では端末装置Ｂが検証装置１１として機能する。ステップＳ１１１〜Ｓ１１３では、検証装置１１として機能する端末装置Ｂが証明装置１２として機能する端末装置Ａに対してコミットしたり、ゼロ知識証明を行ったりする。この処理では端末装置Ａの証拠などの秘密情報は用いられていない。そのため、ステップＳ１１１〜Ｓ１１３で端末装置Ｂが端末装置Ａから中間者攻撃に有効な秘密情報を得ることはない。一方、ステップＳ１２４では、証明装置１２として機能する端末装置Ａが検証装置１１として機能する端末装置Ｂへのゼロ知識アーギュメントを行う。このゼロ知識アーギュメントでは端末装置Ａが証拠ｗを用いてｘ∈Ｌを証明する。この端末装置Ａの挙動を端末装置Ｂが自らシミュレートすることができるのであれば、端末装置Ａは端末装置Ｂに証拠ｗに関する情報を一切与えていないことになる。すなわち、端末装置Ａが端末装置Ｂでシミュレート可能な通信しか行っていないのであれば、端末装置Ｂは自ら知り得る情報よりも多くの情報を端末装置Ａから得ていないことになる。
【００３２】
ステップＳ１２４では、「インスタンスｘがＮＰ言語Ｌに属するｘ∈Ｌか、または、コミットメント部１１１によるコミットメントの何れかのデコミットメント情報（ｒｖ’，ｄ’）を持つ」という命題を証明すればよい。ステップＳ１１１，Ｓ１１２のコミットメント方式はいずれも統計的束縛性を満たし、ステップＳ１１３のゼロ知識証明の安全性から、検証装置１１として機能する端末装置Ｂは任意値ｒｖのコミットメントのデコミットメント情報（ｒｖ，ｄ）を知っていることが保証される。そのため端末装置Ｂは、デコミットメント情報（ｒｖ，ｄ）を証拠として用い、「インスタンスｘがＮＰ言語Ｌに属するｘ∈Ｌか、または、コミットメント部１１１によるコミットメントの何れかのデコミットメント情報（ｒｖ’，ｄ’）を持つ」という命題を証明できる。
【００３３】
またステップＳ１２４では、証明に用いられた証拠を識別することが統計的に困難なアーギュメント方式が用いられる。そのため、このアーギュメント方式では、たとえ超多項式時間の計算能力を用いたとしても、証拠ｗを用いて「ｘ∈Ｌである」ことを証明したのか、証拠（ｒｖ，ｄ）を用いて「コミットメント部１１１によるコミットメントの何れかのデコミットメント情報（ｒｖ’，ｄ’）を持つ」ことを証明したのかを識別できない。この統計的安全性により、統計的ゼロ知識性が証明できる。
【００３４】
よって端末装置Ｂは、証明装置１２として機能する端末装置Ａが行う通信を自分自身でシミュレートできる。そのため、図３Ａでの端末装置Ａ，Ｂ間での通信は、端末装置Ｂが知る以上の情報を端末装置Ｂに与えていないことになる。したがって、端末装置Ｂは証明装置１２として機能する端末装置Ａと通信しても、図３Ｂの場面で検証装置１１として機能する端末装置Ｃに対し、端末装置Ｂが証拠を知らない命題を証明することはできない。このことは、端末装置Ｂが複数の端末装置Ａおよび複数の端末装置Ｃと同様の通信を行う場合でも同じである。以上より、本形態の方式は統計的コンカレントnon-malleableゼロ知識アーギュメントであり、一方向性関数の存在を仮定するだけで安全性を証明できる。
【００３５】
［第２実施形態］
第２実施形態では、前述のステージ２のゼロ知識証明で用いる計算量的non-malleable zero-knowledge proof of knowledgeプロトコルの具体例を示す。以下では、第１実施形態との相違点を中心に説明し、共通部分については第１実施形態で用いた参照番号を流用して説明を簡略化する。
【００３６】
本形態では、任意の一方向性関数から構成できる公知のｍａｘ（ＲＳＢ＋２，ＲＷＩ）−ロバストのＣＣＡ安全コミットメント方式ＣＣＡＣｏｍを追加で使用する（例えば、参考文献５「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.」等参照）。ここで、ＣＣＡ安全コミットメント方式はコミットメントの秘匿性を超多項式時間で破るオラクルに攻撃者がアクセスする場合でも秘匿性が成り立つコミットメント方式であり、ロバストネスはＣＣＡ安全コミットメント方式の性質の一つである。
【００３７】
＜構成＞
図１に例示するように、本形態の証明システム２は検証装置２１および証明装置２２を有する。検証装置２１は、任意値選択部１１０、コミットメント部１１１、コミットメント部１１２、証明部２１３、検証部１１４、および記憶部１１５を有する。証明装置２２は、コミットメント処理部１２１、１２２、検証部２２３、および証明部１２４を有する。図４に例示するように、証明部２１３は、コミットメント処理部２１３ｂ、コミットメント部２１３ｃ（第４コミットメント部）、デコミットメント処理部２１３ｄ、およびゼロ知識証明部２１３ｅを有する。検証部２２３は、任意値選択部２２３ａ、コミットメント部２２３ｂ（第３コミットメント部）、コミットメント処理部２２３ｃ、デコミットメント部２２３ｄ（デコミットメント部）、および検証部２２３ｅを有する。
【００３８】
＜処理＞
第１実施形態との相違点はステージ２のみであり、図２のステップＳ１１３に代えてＳ２１３を実行する。図５を用いてステップＳ２１３の処理を説明する。
【００３９】
ステップＳ２１３では、計算量的non-malleableゼロ知識性を持つゼロ知識証明プロトコルを用い、証明部２１３が検証部２２３に対し、コミットメント部１１１の処理（ステップＳ１１１）およびコミットメント部１１２の処理（ステップＳ１１２）が正しく行われたことのゼロ知識証明を行う。すなわち、証明部２１３はこのプロトコルに従い、記憶部１１５から読み込んだデコミットメント情報（（ｒｖ，ｄ），ｄ’）を証拠とし、コミットメント部１１２でコミットされた情報は（ｒｖ，ｄ）であり、かつ、（ｒｖ，ｄ）はコミットメント部１１１によるコミットメントのデコミットメント情報であることを検証部２２３に対してゼロ知識証明する。
【００４０】
まず、任意値選択部２２３ａが任意値ｒＰ∈｛０，１｝ｎ（第２任意値）を選択する。例えば、任意値選択部２２３ａは乱数発生装置等を用いてランダムに任意値ｒＰを選択してもよいし、複数個の候補から予め定められた順序で選択された値を任意値ｒＰとしてもよい。任意値ｒＰはコミットメント部２２３ｂに送られる（ステップＳ２２３ａ）。
【００４１】
コミットメント部２２３ｂは、統計的束縛性および計算量的秘匿性を満たす第３コミットメント方式（例えばＣＣＡＣｏｍ）に則って、コミットメント処理部２１３ｂとの間で相互通信を行い、任意値ｒＰのコミットメントを行う。このコミットメントでは、コミットメント部２２３ｂが任意値ｒＰをコミットメントするための情報Ｅを生成し、当該情報Ｅをコミットメント処理部２１３ｂに送信（出力）する。例えば、情報ＥはｒＰをデコミットするためのデコミットメント情報（ｒＰ，ｅ）（第３デコミットメント情報）に対応する関数値であり、ｅは乱数などの任意値である。コミットメント部２２３ｂはデコミットメント情報（ｒＰ，ｅ）を記憶部１２５に格納する。コミットメント処理部２１３ｂは情報Ｅを受信して（受け付けて）記憶部１１５に格納する（ステップＳ２１３ｂ）。
【００４２】
任意値ｒＰのコミットメントの後、コミットメント部２１３ｃが、統計的束縛性を満たす第４コミットメント方式（例えば、ＣＥＣｏｍ）に則って、コミットメント処理部２２３ｃとの間で相互通信を行い、任意値ｋＶ∈｛０，１｝ｎ（第３任意値）のコミットメントを行う。任意値ｋＶは例えばｋＶ＝０ｎのような定数でよい。このコミットメントでは、コミットメント部２１３ｃが任意値ｋＶをコミットするための情報Ｙを生成し、当該情報Ｙをコミットメント処理部２２３ｃに送信（出力）する。例えば、情報ＹはｋＶをデコミットするためのデコミットメント情報（ｋＶ，ｙ）に対応する関数値であり、ｙは乱数などの任意値である。コミットメント部２１３ｃはデコミットメント情報（ｋＶ，ｙ）を記憶部１１５に格納する。コミットメント処理部２２３ｃは情報Ｙを受信して（受け付けて）記憶部１２５に格納する（ステップＳ２１３ｃ）。
【００４３】
任意値ｋＶのコミットメントの後、デコミットメント部２２３ｄは、記憶部１２５からデコミットメント情報（ｒＰ，ｅ）を読み込み、ｒＰをデコミット（オープン）する。例えば、デコミットメント部２２３ｄは、デコミットメント情報（ｒＰ，ｅ）をデコミットメント処理部２１３ｄに送り、デコミットメント処理部２１３ｄは記憶部１１５から読み込んだ情報Ｅを用いてデコミットメント情報（ｒＰ，ｅ）を検証する（ステップＳ２２３ｄ）。
【００４４】
ゼロ知識証明部２１３ｅは、証明に用いられた証拠を識別することが困難な証明方式（例えば、ＷＩＰＯＫ）に則って、記憶部１１５から読み込んだデコミットメント情報（（ｒｖ，ｄ），ｄ’）（第１デコミットメント情報をデコミットするための第２デコミットメント情報）を証拠として用い、「ステップＳ１１２でコミットメント部１１２（第２コミットメント部）によってコミットされた情報はデコミットメント情報（ｒｖ，ｄ）（第１デコミットメント情報）であり、かつ、（ｒｖ，ｄ）はコミットメント部１１１によるコミットメントのデコミットメント情報であるか、または、ステップＳ２１３ｃのコミットメントでコミットされた値ｋＶ（第３任意値）は任意値ｒＰ（第２任意値）である」という命題を検証部２２３ｅに対して証明する。この過程で、ゼロ知識証明部２１３ｅはこの証明のための情報を送信（出力）し、検証部２２３ｅはこの情報および記憶部１２５から読み込んだｉｄ，Ｃ，Ｃ’を用いて検証を行う。
【００４５】
ここで、ステップＳ２１３ｂでは、コミットメント部２２３ｂが計算量的秘匿性を満たす第３コミットメント方式（例えばＣＣＡＣｏｍ）に則って任意値ｒＰのコミットメントを行っている。したがって、任意値ｒＰのデコミットメント前のステップＳ２１３ｃにおいてコミットメント部２１３ｃがｋＶ＝ｒＰをコミットすることはできない。また、ステップＳ２１３ｃでは、コミットメント部２１３ｃが統計的束縛性を満たす第４コミットメント方式（例えば、ＣＥＣｏｍ）に則って任意値ｋＶのコミットを行っている。したがって、ステップＳ２１３ｃで任意値ｋＶ以外の値をコミットしていたと偽ることはできない。そのため、「ステップＳ１１２でコミットメント部１１２によってコミットされた情報はデコミットメント情報（ｒｖ，ｄ）であり、かつ、（ｒｖ，ｄ）はコミットメント部１１１によるコミットメントのデコミットメント情報であるか、または、ステップＳ２１３ｃのコミットメントでコミットされた値ｋＶは任意値ｒＰである」という命題が真であることが証明された場合、「ステップＳ１１２でコミットメント部１１２によってコミットされた情報はデコミットメント情報（ｒｖ，ｄ）であり、かつ、（ｒｖ，ｄ）はコミットメント部１１１によるコミットメントのデコミットメント情報である」という命題が真であるということが証明されたことになる。
【００４６】
［特徴］
上述のように、各実施形態の方式は一方向性関数から構成可能な構成要素のみを用いて構成されているため、その安全性は一方向性関数の存在を仮定するだけで証明可能である。したがって、本方式は従来より弱い計算量仮定から統計的コンカレントnon-malleableゼロ知識アーギュメントを実現している。弱い計算量仮定は将来的に技術が発展した場合でも成り立つ可能性が高いため、本方式は従来方式よりも信頼度の高い安全性を持つことになる。
【００４７】
［その他の変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４８】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４９】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００５１】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【００５２】
本発明は、例えば、電子商取引等での認証、公開鍵暗号方式等の暗号プロトコルでの公開鍵の正当性の検証などに利用できる。
【符号の説明】
【００５３】
１，２  証明システム
１１，２１  検証装置
１２，２２  証明装置
【図１】
0006334453.tif 000002
【図２】
0006334453.tif 000003
【図３】
0006334453.tif 000004
【図４】
0006334453.tif 000005
【図５】
0006334453.tif 000006