(57)【特許請求の範囲】
【請求項１】
グラフＧ０がハミルトン閉路を持つことを証明する証明装置であって、
ハミルトン閉路を持たないグラフＧ１を得る前提処理部と、
コミット対象０と前記グラフＧ０，Ｇ１と乱数ｒｉ，ｊとを含む情報に応じて得られる、前記グラフＧ１と同じサイズの零行列の各要素０へのコミットメントｃｉ，ｊを含む集合｛ｃｉ，ｊ｝を出力するコミット部と、
チャレンジｃｈの入力を受け付けるチャレンジ入力部と、
前記チャレンジｃｈが第１値である場合に、前記グラフＧ１に由来するグラフＨ（０）の隣接行列Ａ（０）の各要素ａｉ，ｊ（０）に前記コミットメントｃｉ，ｊをデコミットするためのデコミットメントｄｉ，ｊ（０）を含む集合を出力し、
前記チャレンジｃｈが前記第１値と異なる第２値である場合に、ハミルトン閉路のみを持つグラフＨ（１）の隣接行列Ａ（１）の要素のうち閉路をなす枝に対応する各要素ａｐ，ｑ（１）に前記コミットメントｃｐ，ｑ∈｛ｃｉ，ｊ｝をデコミットするためのデコミットメントｄｐ，ｑ（１）を含む集合を出力するデコミット部と、
を有する証明装置。
【請求項２】
請求項１の証明装置であって、
前記グラフＧ０がハミルトン閉路を持たない場合、前記コミット対象０への拘束性が保証され、
前記グラフＧ０がハミルトン閉路を持つ場合、０への前記コミットメントｃｉ，ｊを１へデコミットするための値を前記デコミットメントｄとすることができ、
前記グラフＧ０およびＧ１がハミルトン閉路を持つ場合、ｂ＝１への前記コミットメントｃをｂ＝０へのコミットメントとして示すことができる、証明装置。
【請求項３】
請求項１または２の証明装置であって、
０への前記コミットメントｃｉ，ｊは、前記グラフＧ０に由来するグラフＥ（０）の隣接行列Ｂ（０）の各要素ｂｉ，ｊ（０）を方式ＡＨ＿ＣｏｍでコミットしたコミットメントＣＢｉ，ｊ（０）←ＡＨ＿Ｃｏｍ（Ｇ１，ｂｉ，ｊ（０））を含む集合｛ＣＢｉ，ｊ（０）｝であり、
１への前記コミットメントｃｉ，ｊは、前記グラフＧ０と同じサイズでハミルトン閉路のみを持つグラフＥ（１）の隣接行列Ｂ（１）の各要素ｂｉ，ｊ（１）を前記方式ＡＨ＿ＣｏｍでコミットしたコミットメントＣＢｉ，ｊ（１）←ＡＨ＿Ｃｏｍ（Ｇ１，ｂｉ，ｊ（１））を含む集合｛ＣＢｉ，ｊ（１）｝であり、
前記方式ＡＨ＿Ｃｏｍでの０へのコミットメントＡＨ＿Ｃｏｍ（Ｇ１，０）は、前記グラフＧ１に由来するグラフＴ（０）の隣接行列Ｕ（０）の各要素ｕｖ，ｗ（０）へのコミットメントｃｕｖ，ｗ（０）を含む集合｛ｃｕｖ，ｗ（０）｝であり、
前記方式ＡＨ＿Ｃｏｍでの１へのコミットメントＡＨ＿Ｃｏｍ（Ｇ１，１）は、前記グラフＧ１と同じサイズでハミルトン閉路のみを持つグラフＴ（１）の隣接行列Ｕ（１）の各要素ｕｖ，ｗ（１）に対応するｃｕｖ，ｗ（１）を含む集合｛ｃｕｖ，ｗ（１）｝であり、要素ｕｖ，ｗ（１）＝１に対応するｃｕｖ，ｗ（１）は前記要素ｕｖ，ｗ（１）へのコミットメントであり、要素ｕｖ，ｗ（１）＝０に対応するｃｕｖ，ｗ（１）はランダム記号列である、証明装置。
【請求項４】
グラフＧ０がハミルトン閉路を持つことを証明する証明装置と、前記グラフＧ０がハミルトン閉路を持つことを検証する検証装置とを有し、
前記証明装置は、ハミルトン閉路を持たないグラフＧ１を得る第１前提処理部を含み、
前記検証装置は、前記グラフＧ１を得る第２前提処理部を含み、
前記証明装置は、コミット対象０と前記グラフＧ０，Ｇ１と乱数ｒｉ，ｊとを含む情報に応じて得られる、前記グラフＧ１と同じサイズの零行列の各要素０へのコミットメントｃｉ，ｊを含む集合｛ｃｉ，ｊ｝を出力するコミット部を含み、
前記検証装置は、チャレンジｃｈを出力するチャレンジ出力部を含み、
前記証明装置は、前記チャレンジｃｈの入力を受け付けるチャレンジ入力部と、
前記チャレンジｃｈが第１値である場合に、前記グラフＧ１に由来するグラフＨ（０）の隣接行列Ａ（０）の各要素ａｉ，ｊ（０）に前記コミットメントｃｉ，ｊをデコミットするためのデコミットメントｄｉ，ｊ（０）を含む集合を出力し、
前記チャレンジｃｈが前記第１値と異なる第２値である場合に、ハミルトン閉路のみを持つグラフＨ（１）の隣接行列Ａ（１）の要素のうち閉路をなす枝に対応する各要素ａｐ，ｑ（１）に前記コミットメントｃｐ，ｑ∈｛ｃｉ，ｊ｝をデコミットするためのデコミットメントｄｐ，ｑ（１）を含む集合を出力するデコミット部と、を含み、
前記検証装置は、
前記チャレンジｃｈが前記第１値である場合に、｛ｃｉ，ｊ｝，｛ｄｉ，ｊ（０）｝，｛ａｉ，ｊ（０）｝および前記グラフＧ０，Ｇ１を含む情報を用いて、前記コミットメントｃｉ，ｊが前記要素ａｉ，ｊ（０）にデコミットされたことを検証し、
前記チャレンジｃｈが前記第２値である場合に、｛ｃｐ，ｑ｝，｛ｄｐ，ｑ（１）｝および前記グラフＧ０，Ｇ１を含む情報を用いて、前記コミットメントｃｐ，ｑが１にデコミットされたことを確認し、かつ、１にデコミットされた要素に対応する枝を持つグラフがハミルトン閉路であることを検証する検証部を含む、証明システム。
【請求項５】
前提処理部とコミット部と入力部とデコミット部とを有する証明装置が、グラフＧ０がハミルトン閉路を持つことを証明する証明方法であって、
前記前提処理部が、ハミルトン閉路を持たないグラフＧ１を得、
前記コミット部が、コミット対象０と前記グラフＧ０，Ｇ１と乱数ｒｉ，ｊとを含む情報に応じて得られる、前記グラフＧ１と同じサイズの零行列の各要素０へのコミットメントｃｉ，ｊを含む集合｛ｃｉ，ｊ｝を出力し、
前記入力部が、チャレンジｃｈの入力を受け付け、
前記デコミット部が、
前記チャレンジｃｈが第１値である場合に、前記グラフＧ１に由来するグラフＨ（０）の隣接行列Ａ（０）の各要素ａｉ，ｊ（０）に前記コミットメントｃｉ，ｊをデコミットするためのデコミットメントｄｉ，ｊ（０）を含む集合を出力し、
前記チャレンジｃｈが前記第１値と異なる第２値である場合に、ハミルトン閉路のみを持つグラフＨ（１）の隣接行列Ａ（１）の要素のうち閉路をなす枝に対応する各要素ａｐ，ｑ（１）に前記コミットメントｃｐ，ｑ∈｛ｃｉ，ｊ｝をデコミットするためのデコミットメントｄｐ，ｑ（１）を含む集合を出力する証明方法。
【請求項６】
請求項１から３の何れかの証明装置としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に対話により証明を行う対話証明技術に関する。
【背景技術】
【０００２】
漏洩耐性を持つゼロ知識証明は証明者の内部状態の一部が検証者に漏れた場合でもゼロ知識性が成り立つゼロ知識証明である。漏洩耐性を持つゼロ知識証明の既存技術としては非特許文献１で提案された方式がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Omkant Pandey, “Achieving constant round leakage-resilient zero-knowledge,” In Yehuda Lindell, editor, Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings, volume 8349 of Lecture Notes in Computer Science, pages 146-166. Springer, 2014.
【非特許文献２】Andrew Chi-Chih Yao, “How to generate and exchange secrets (extended abstract),” In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 162-167. IEEE Computer Society, 1986.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、非特許文献１の方式には二者間秘密計算プロトコルであるYaoのプロトコル（例えば、非特許文献２参照）が用いられている。Yaoのプロトコルは計算量が大きく、効率面で望ましくない。
【０００５】
本発明の課題は、Yaoのプロトコルを用いずに漏洩耐性を持つゼロ知識証明を構成することである。
【課題を解決するための手段】
【０００６】
証明装置が検証装置に対し、グラフＧ０がハミルトン閉路を持つことを証明する。証明装置および検証装置はハミルトン閉路を持たないグラフＧ１を得る。証明装置は、コミット対象０とグラフＧ０，Ｇ１と乱数ｒｉ，ｊとを含む情報に応じて得られる、グラフＧ１と同じサイズの零行列の各要素０へのコミットメントｃｉ，ｊを含む集合｛ｃｉ，ｊ｝を出力する。検証装置はチャレンジｃｈを出力する。証明装置は、チャレンジｃｈの入力を受け付け、チャレンジｃｈが第１値である場合に、グラフＧ１に由来するグラフＨ（０）の隣接行列Ａ（０）の各要素ａｉ，ｊ（０）にコミットメントｃｉ，ｊをデコミットするためのデコミットメントｄｉ，ｊ（０）を含む集合を出力し、チャレンジｃｈが第１値と異なる第２値である場合に、ハミルトン閉路のみを持つグラフＨ（１）の隣接行列Ａ（１）の要素のうち閉路をなす枝に対応する各要素ａｐ，ｑ（１）にコミットメントｃｐ，ｑ∈｛ｃｉ，ｊ｝をデコミットするためのデコミットメントｄｐ，ｑ（１）を含む集合を出力する。検証装置は、チャレンジｃｈが第１値である場合に、｛ｃｉ，ｊ｝，｛ｄｉ，ｊ（０）｝，｛ａｉ，ｊ（０）｝およびグラフＧ０，Ｇ１を含む情報を用いて、コミットメントｃｉ，ｊが要素ａｉ，ｊ（０）にデコミットされたことを検証し、チャレンジｃｈが第２値である場合に、｛ｃｐ，ｑ｝，｛ｄｐ，ｑ（１）｝およびグラフＧ０，Ｇ１を含む情報を用いて、コミットメントｃｐ，ｑが１にデコミットされたことを確認し、かつ、１にデコミットされた要素に対応する枝を持つグラフがハミルトン閉路であることを検証する。
【発明の効果】
【０００７】
本発明では、Yaoのプロトコルを用いずに漏洩耐性を持つゼロ知識証明を構成できる。
【図面の簡単な説明】
【０００８】
【図１】図１は実施形態の証明システムを例示するブロック図である。
【図２】図２は実施形態の証明方法および検証方法を例示するフロー図である。
【図３】図３は実施形態の証明方法および検証方法を例示するフロー図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［定義］
まず、実施形態で使用する用語を定義する。
実施形態では、証明者として機能する証明装置が検証者として機能する検証装置と通信を行うことによりゼロ知識証明を行う。ゼロ知識証明とは、証明者が「命題が真である」こと以外の知識を検証者に与えることなく、「命題が真である」ことを検証者に証明する手法である。ここで、証明者が証明する命題は「ＮＰ言語Ｌとインスタンス（ステートメント）ｘに関してｘ∈Ｌが成り立つ」ことである。この命題はＮＰ（Non-deterministic Polynomial）に属する問題であり、その解を求める多項式時間アルゴリズムは必ずしも知られていないが、多項式サイズの証拠（witness）が与えられれば、解の正しさを多項式時間で検証できる判定問題である。ＮＰ言語Ｌの例は「正しく生成されたＲＳＡ暗号の公開鍵の集合」であり、インスタンスｘの例は「特定の公開鍵」である。この場合の証拠ｗの例は公開鍵の素因数からなる列である。証明者と検証者は共通入力としてＮＰ言語Ｌとインスタンスｘを持ち、更に証明者はｘ∈Ｌであることの証拠ｗを持つ。
【００１０】
ゼロ知識証明の安全性は、以下の健全性およびゼロ知識性によって定義される。
健全性は「ｘ∈Ｌでないとき、どのような証明者も証明に失敗する」という性質である。ここではプロトコルに従わない悪意を持った証明者も考慮する。
ゼロ知識性は「ｘ∈Ｌならば、どのような多項式時間の計算能力を持つ検証者に対しても命題が真（ｘ∈Ｌ）であること以外の情報（例えば、証拠ｗに関する情報）は漏れない」という性質である。ここでもプロトコルに従わない悪意を持った検証者も考慮する。
【００１１】
健全性において多項式時間の計算能力を持つ証明者のみを考慮したものをゼロ知識アーギュメントと呼ぶ。ゼロ知識証明およびゼロ知識アーギュメントは単独でも認証などにおいて有用であり、さらに他の暗号プロトコルの構成要素としても有用であることが知られている。
【００１２】
またゼロ知識性を表現するために、任意の検証者に対するシミュレータという概念を用いる。このシミュレータは検証者と同じ入力（ＮＰ言語Ｌとインスタンスｘ）を受け取り、証明者−検証者間の実際の通信系列と識別できない通信系列を出力する（シミュレートする）。もし、どのような検証者に対してもシミュレータが存在するならば、直感的には以下の理由から検証者が証拠に関する情報などを証明から得ていないことが保証される。
【００１３】
１．もし検証者が証明者と通信することで何らかの情報を得ているならば、その情報は証明者−検証者間の通信系列から計算できるはずである。なぜなら、検証者が証明者から得た情報は通信系列のみだからである。
２．したがって、もし検証者と同じ入力から証明者−検証者間の通信系列を出力するシミュレータが存在したら、検証者が得た情報は検証者の入力のみから計算できることになる。
３．これは検証者が得た情報は全て証明者と通信をすることなく計算することができることを意味するため、検証者の入力からは計算できない情報を検証者は得ていないことになる。
【００１４】
漏洩耐性を持つゼロ知識証明とは、証明者の内部状態（例えば、証拠、秘密入力、生成した乱数など）の一部が検証者に漏れた場合でもゼロ知識性が成り立つゼロ知識証明である。特に、検証者が任意の関数ｆを選ぶと証明者の内部状態ｓｔに関する情報ｆ（ｓｔ）が検証者に漏洩するというモデルにおいてゼロ知識性が成り立つゼロ知識証明である。それは消費電力などを物理的に観測することで内部状態に関する情報を得るサイドチャネル攻撃に対して安全性を保証するゼロ知識証明であると考えることもできる。しかし、ゼロ知識性というのは命題が真であること以外の情報（例えば、証拠ｗに関する情報）が検証者に漏れないという性質であるため、証明者の内部状態の一部である証拠ｗについての情報が検証者に漏洩するとゼロ知識性の実現は不可能となる。そこで漏洩耐性を持つゼロ知識証明の定義においてはゼロ知識性の定義を緩和する。直感的には、耐漏洩ゼロ知識性は「命題が真であることおよび漏洩した内部情報以外の情報は検証者に漏れない」ことを保証する性質である。具体的には、まずゼロ知識性の定義におけるシミュレータに追加の能力を与え、任意の関数ｆ’を選ぶとシミュレータが証拠ｗに関する部分情報ｆ’（ｗ）を得ることができるようにする。そして、検証者がＬビットの漏洩情報を受け取るならばシミュレータもＬビットの漏洩情報を受け取ることができるようにゼロ知識性の定義を変更したものを耐漏洩ゼロ知識性の定義とする。
【００１５】
任意の確率的アルゴリズムＡｌｇｏに対し、「ｙ：＝Ａｌｇｏ（ｘ；ｒ）」によって「入力ｘと乱数ｒでＡｌｇｏを計算し出力ｙを得る」という操作を表す。また「ｙ←Ａｌｇｏ（ｘ）」によって「適切な長さの乱数ｒ∈｛０，１｝*」を用いて「ｙ：＝Ａｌｇｏ（ｘ；ｒ）を計算してｙを得る」という操作を表す。「α：＝β」は「αをβにする」ことを意味する。
【００１６】
「非対話コミットメント方式」は確率的アルゴリズムの組（Ｃｏｍ，Ｄｅｃ，Ｖｅｒｉｆｙ）である。Ｃｏｍはビットｂ∈｛０，１｝を入力としてｂへのコミットメントｃ←Ｃｏｍ（ｂ）（すなわち、ｃ：＝（ｂ；ｒ））を出力する。Ｄｅｃはコミットメントｃとコミットされた値ｂとコミット時に用いた乱数ｒを入力としてデコミットメントｄ：＝Ｄｅｃ（ｂ，ｃ；ｒ）を出力する。Ｖｅｒｉｆｙはコミットメントｃとデコミットされた値ｂとデコミットメントｄを入力としてデコミットメントｄを検証する（Ｖｅｒｉｆｙ（ｂ，ｃ，ｄ）＝１ならば検証成功）。特に本形態ではコミットメントｃが擬似乱数である（つまりランダムな｜ｃ｜ビット記号列と識別できない）という性質を持つ方式を用いる。ただし、｜ｃ｜はｃのビット長を表す。「記号」は文字を含む概念である。そのような非対話コミットメント方式は一方向性置換から構築できることがよく知られている。
【００１７】
本形態では、非特許文献１の漏洩耐性を持つゼロ知識証明における前提処理である「encrypted preamble」を流用する（非特許文献１の３．３節参照）。encrypted preambleは証明者と検証者との間で行われる対話型の通信処理である。非特許文献１では、あるＮＰ言語Ｌｓｉｍが存在し、どのような証明者に対してもencrypted preambleにおける証明者−検証者間の通信系列σ（例えば、データ列）はσ∈Ｌｓｉｍを満たさないことが示されている。また、任意の検証者に対してシミュレータが存在し、その出力σ’はσ’∈Ｌｓｉｍを満たしつつ更にencrypted preambleの通信系列と識別不可能である。さらにシミュレータは同時にσ’∈Ｌｓｉｍの証拠も計算できる。ＬｓｉｍはＮＰ言語であるため、σ∈Ｌｓｉｍを満たすか否かの問題は、グラフＧがハミルトン閉路を持つグラフの集合Ｌｈａｍに属するか否かの問題（Ｇ∈Ｌｈａｍを満たすか否かの問題）であるハミルトン閉路問題に帰着可能である。
【００１８】
［原理］
まず、ある特定の性質を満たすコミットメント方式ＳｐｅｃｉａｌＣｏｍがあれば漏洩耐性を持つゼロ知識証明を構築することができることを示す。次にＳｐｅｃｉａｌＣｏｍを非対話コミットメント方式Ｃｏｍから構築することができることを示す。
【００１９】
＜ＳｐｅｃｉａｌＣｏｍを用いた漏洩耐性を持つゼロ知識証明の構成＞
≪ＳｐｅｃｉａｌＣｏｍ≫
ＳｐｅｃｉａｌＣｏｍ＝（Ｓ_Ｃｏｍ，Ｓ_Ｄｅｃ，Ｓ_Ｖｅｒｉｆｙ）を以下のような性質を満たす非対話コミットメント方式とする。
Ｓ_Ｃｏｍはビットｂ∈｛０，１｝と２つのグラフＧ０，Ｇ１を入力とし、乱数ｒを生成してｂへのコミットメントｃ←Ｓ_Ｃｏｍ（Ｇ０，Ｇ１，ｂ）（すなわち、ｃ：＝Ｓ_Ｃｏｍ（Ｇ０，Ｇ１，ｂ；ｒ））を出力する。本形態では、例えばコミットメントｃ←Ｓ_Ｃｏｍ（Ｇ０，Ｇ１，ｂ）が擬似乱数であるという性質を持つ。ただし、これは必須ではない。Ｓ_Ｄｅｃはコミットメントｃとコミットされたビットｂとコミット時に用いた乱数ｒとグラフＧ０，Ｇ１を入力とし、デコミットメントｄ：＝Ｓ_Ｄｅｃ（Ｇ０，Ｇ１，ｃ，ｂ；ｒ）を出力する。Ｓ_Ｖｅｒｉｆｙはコミットメントｃとデコミットされた値ｂとデコミットメントｄとグラフＧ０，Ｇ１を入力とし、デコミットメントｄを検証する（Ｓ_Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，ｂ，ｃ，ｄ）＝１ならば検証成功）。
【００２０】
ＳｐｅｃｉａｌＣｏｍは以下の性質を満たす。
（性質１）Ｇ０∈Ｌｈａｍでなく、かつ、Ｇ１∈Ｌｈａｍでないとき（Ｇ０およびＧ１が何れもハミルトン閉路を持たないとき）、拘束性が成り立つ。ただし、ハミルトン閉路を持つグラフの集合をＬｈａｍで表す。つまり、以下の関係が成り立つ。
{c|∃d s.t. S_Verify(G0,G1,0,c,d)=1}∩{c|∃d s.t. S_Verify(G0,G1,1,c,d)=1}=φ
ただし、「∃d s.t.α」はαを満たすようなｄが存在することを表す。φは空集合を表す。
【００２１】
（性質２）Ｇ０∈ＬｈａｍやＧ１∈Ｌｈａｍが成り立つかどうかにかかわらず、秘匿性が成り立つ。つまり、以下の関係が成り立つ。
{c|c←S_Com(G0,G1,0)}~{c|c←S_Com(G0,G1,1)}
ただし、α~βはαとβとを識別できないことを意味する。
【００２２】
（性質３）Ｇ０∈Ｌｈａｍのときは、Ｇ０∈Ｌｈａｍの証拠ｗ０を用いて０へのコミットメントを１にデコミットすることができる。つまり、あるアルゴリズムＳ＿Ｅｑｕｉｖが存在し、以下が成り立つ。
・任意の乱数rに関し、ｃ：＝Ｓ＿Ｃｏｍ（Ｇ０，Ｇ１，０；ｒ），ｄ’：＝Ｓ＿Ｅｑｕｉｖ（Ｇ０，Ｇ１，ｗ０；ｒ）とするとＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，１，ｃ，ｄ’）＝１が成り立つ。
【００２３】
（性質４）Ｇ０∈ＬｈａｍかつＧ１∈Ｌｈａｍのときは、Ｇ０∈Ｌｈａｍの証拠ｗ０とＧ１∈Ｌｈａｍの証拠ｗ１とを用い、１へのコミットメントを０のコミットメントだと「説明」することができる。つまり、あるアルゴリズムＳ＿Ａｄａｐｔが存在し、以下が成り立つ。
・任意の乱数rに関し、ｃ：＝Ｓ＿Ｃｏｍ（Ｇ０，Ｇ１，１；ｒ），ｒ’：＝Ｓ＿Ａｄａｐｔ（Ｇ０，Ｇ１，ｗ０，ｗ１；ｒ）とするとＳ＿Ｃｏｍ（Ｇ０，Ｇ１，０；ｒ’）＝ｃが成り立つ。
【００２４】
≪漏洩耐性を持つゼロ知識証明の構成≫
証明者をＰ、検証者をＶと表現する。一般性を失うことなく（ハミルトン閉路問題はＮＰ完全問題であり、一般性を失わない）、ＰはＶと共有するグラフＧ０がハミルトン閉路を持つこと（つまりＧ０∈Ｌｈａｍであること）を証明するものとする。証明者Ｐが証拠ｗ０を持つとする。
【００２５】
ステップ１：ＰとＶは非特許文献１のencrypted preambleを行う。その通信系列をσとする。また、命題σをハミルトン閉路問題に帰着して得られたグラフをＧ１とする。Ｇ１の節点数（「頂点数」「ノード数」とも呼ぶ）をｎとする。前述のようにencrypted preambleが正しく行われれば、σ∈Ｌｓｉｍを満たさず、Ｇ１∈Ｌｈａｍともならない。
【００２６】
ステップ２：ＰとＶは以下のステップ２（ａ）〜２（ｄ）の処理をパラレルにＫ回行う。ただし、Ｋは正整数（定数）であり、たとえばセキュリティパラメータである。
ステップ２（ａ）：ＰはＳｐｅｃｉａｌＣｏｍを用いてｎ×ｎの零行列にコミットする。つまり、Ｐは各ｉ∈［ｎ］，ｊ∈［ｎ］について乱数ｒｉ，ｊを選んでコミットメントｃｉ，ｊ：＝Ｓ_Ｃｏｍ（Ｇ０，Ｇ１，０；ｒｉ，ｊ）を計算し、｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］をＶに送る。なお、［ｎ］は１以上ｎ以下の整数からなる集合｛１，…，ｎ｝を表し、｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］はｃｉ，ｊ（ただし、ｉ∈［ｎ］，ｊ∈［ｎ］）を要素とした集合（例えば、ｃｉ，ｊをｉ行ｊ列の要素とした行列）を表す。また｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を｛ｃｉ，ｊ｝と省略して記載する場合もある。
【００２７】
ステップ２（ｂ）：Ｖはランダムなチャレンジｃｈ∈｛０，１｝をＰに送る。
【００２８】
ステップ２（ｃ）：ｃｈ＝０ならば、ＰはＧ１上のランダム置換πを選び、Ｈ（０）＝π（Ｇ１）の隣接行列Ａ（０）：＝Ｍ（Ｈ（０））を計算する。ただし、π（Ｇ１）はグラフＧ１の節点（「頂点」「ノード」とも呼ぶ）をπに従ってランダムに置換して得られるグラフを表し、隣接行列Ａ（０）をＡ（０）＝｛ａｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］と表記する（ただし、ａｉ，ｊ（０）∈｛０，１｝）。ＰはＧ０∈Ｌｈａｍであることを証明するためにＳｐｅｃｉａｌＣｏｍの（性質３）を利用し、Ｇ０∈Ｌｈａｍの証拠ｗ０および乱数ｒｉ，ｊを用いて｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を｛ａｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］にデコミットする。つまりＰは各ｉ∈［ｎ］，ｊ∈［ｎ］についてａｉ，ｊ（０）＝０ならばｄｉ，ｊ（０）：＝Ｓ_Ｄｅｃ（Ｇ０，Ｇ１，ｃｉ，ｊ，０；ｒｉ，ｊ）を計算し、ａｉ，ｊ（０）＝１ならばｄｉ，ｊ（０）：＝Ｓ＿Ｅｑｕｉｖ（Ｇ０，Ｇ１，ｗ０；ｒｉ，ｊ）を計算し、｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］をＶに送る。また、Ｐはランダム置換πを表す情報もＶに送る。
ｃｈ＝１ならば、Ｐはハミルトン閉路のみを持つグラフＨ（１）（節点数ｎ）のｎ×ｎの隣接行列Ａ（１）：＝Ｍ（Ｈ（１））をランダムに選択する。ただし、隣接行列Ａ（１）をＡ（１）＝｛ａｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］と表記する（ただし、ａｉ，ｊ（１）∈｛０，１｝）。さらにＰはＳｐｅｃｉａｌＣｏｍの（性質３）を利用し、証拠ｗ０および乱数ｒｉ，ｊを用い、グラフＨ（１）の閉路の部分についてｃｐ，ｑ∈｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を各要素ａｐ，ｑ（１）（ただし、ｐ∈［ｎ］，ｑ∈［ｎ］）にデコミットする。言い換えると、ＰはグラフＨ（１）の隣接行列Ａ（１）＝｛ａｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］の要素のうち、閉路をなす枝に対応する各要素ａｐ，ｑ（１）＝１にコミットメントｃｐ，ｑをデコミットする。つまり、Ｐはａｐ，ｑ（１）＝１となる各ｐ∈［ｎ］，ｑ∈［ｎ］についてｄｐ，ｑ（１）：＝Ｓ＿Ｅｑｕｉｖ（Ｇ０，Ｇ１，ｗ０；ｒｐ，ｑ）を計算し、｛ｄｐ，ｑ（１）｝ｐ∈［ｎ］，ｑ∈［ｎ］をＶに送る。
【００２９】
ステップ２（ｄ）：ｃｈ＝０のとき、ＶはＨ（０）＝π（Ｇ１）の隣接行列Ａ（０）：＝Ｍ（Ｈ（０））＝｛ａｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］を計算し、｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］が｛ａｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］にデコミットされたことを確認する。つまり、Ｖはすべてのｉ∈［ｎ］，ｊ∈［ｎ］についてＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，ａｉ，ｊ（０），ｃｉ，ｊ，ｄｉ，ｊ（０））＝１が成り立つことを確認する。これが成り立てばこの回の検証は「合格」である。
ｃｈ＝１のとき、Ｖはデコミットされた部分がハミルトン閉路となっていることを確認する。つまり、ＶはＰから受け取ったすべてのｄｐ，ｑ（１）に関してＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，１，ｃｐ，ｑ，ｄｐ，ｑ（１））＝１が成り立つことを確認し、更にコミットメントｃｐ，ｑがデコミットされた要素ａｐ，ｑ（１）が隣接行列においてハミルトン閉路を表すか（１にデコミットされた要素ａｐ，ｑ（１）に対応する枝を持つグラフがハミルトン閉路であるか）を確認する。これが成り立てばこの回の検証は「合格」である。
【００３０】
Ｋ回のすべてのステップ２（ｄ）で「合格」となれば証明は「成功」である。１回でも不合格となれば証明は「失敗」である。
【００３１】
＜安全性の証明＞
≪健全性≫
健全性については、以下の理由で成り立つ。前述のようにencrypted preambleの通信系列σは任意の証明者に対してσ∈Ｌｓｉｍを満たさない。そのため、任意の証明者に対してＧ１∈Ｌｈａｍを満たさない。ここで、Ｇ０∈Ｌｈａｍが成り立たないと仮定する（健全性の定義参照）。このとき、ＳｐｅｃｉａｌＣｏｍの（性質１）から拘束性が成り立つため、上述のステップ２（ａ）の時点でＰがコミットした行列は一意に定まる。この行列がπ（Ｇ１）の隣接行列Ａ（０）であり、なおかつ、ハミルトン閉路を含むグラフの隣接行列であることはありえない。なぜなら、Ｇ１∈Ｌｈａｍを満たさず、そのランダム置換であるπ（Ｇ１）もハミルトン閉路を含まないからである。そのため、Ｇ０∈Ｌｈａｍが成り立たないとき、上述のステップ２（ｃ）でＰが正しく答えられる確率は高々１／２である。言い換えると、Ｇ０∈Ｌｈａｍが成り立たないため（性質３）が成り立たず、Ｐがｃｈ＝０およびｃｈ＝１の両方に正しい応答を行うことはできない。ステップ２（ａ）〜２（ｄ）はＫ回繰り返されるため、全ての繰り返しにおいてＰが正しく答えられる確率は（１／２Ｋ）以下となり、Ｋが十分大きいときにはその確率は無視できる。よって健全性が成り立つ。
【００３２】
≪耐漏洩性≫
耐漏洩性については，以下の理由で成り立つ。まず、前述のようにシミュレータはencrypted preambleの通信系列σ’をシミュレートしてσ’∈Ｌｓｉｍとすることができ、その証拠も計算できる。そのため、シミュレータはＧ１’∈Ｌｈａｍとすることができ、その証拠ｗ１’も計算できる。このときシミュレータはステップ２（ａ）および２（ｃ）を以下のようにしてシミュレートできる。
【００３３】
ステップ２（ａ）：シミュレータはＧ１’上のランダム置換πを選び、Ｈ’＝π（Ｇ１’）の隣接行列Ａ’：＝Ｍ（Ｈ’）を計算する。隣接行列Ａ’をＡ’＝｛ａｉ，ｊ’｝ｉ∈［ｎ］，ｊ∈［ｎ］と表記する。このとき、シミュレータはＳｐｅｃｉａｌＣｏｍを用いてＡ’にコミットする。つまり、シミュレータは各ｉ∈［ｎ］，ｊ∈［ｎ］について乱数ｒｉ，ｊ’を選んでｃｉ，ｊ’＝Ｓ＿Ｃｏｍ（Ｇ０，Ｇ１’，ａｉ，ｊ’；ｒｉ，ｊ’）を計算し、｛ｃｉ，ｊ’｝ｉ∈［ｎ］，ｊ∈［ｎ］をＶに送る。
【００３４】
ステップ２（ｃ）：ｃｈ＝０ならば、シミュレータは｛ｃｉ，ｊ’｝ｉ∈［ｎ］，ｊ∈［ｎ］を｛ａｉ，ｊ’｝ｉ∈［ｎ］，ｊ∈［ｎ］にデコミットする。つまり、シミュレータは各ｉ∈［ｎ］，ｊ∈［ｎ］についてｄｉ，ｊ’：＝Ｓ＿Ｄｅｃ（Ｇ０，Ｇ１’，ｃｉ，ｊ’，ａｉ，ｊ’； ｒｉ，ｊ’）を計算し、｛ｄｉ，ｊ’｝ｉ∈［ｎ］，ｊ∈［ｎ］をＶに送る。また、Ｐはランダム置換πを表す情報もＶに送る。
ｃｈ＝１ならば、シミュレータはＨ’の閉路の部分についてｃｐ，ｑ’∈｛ｃｉ，ｊ’｝ｉ∈［ｎ］，ｊ∈［ｎ］をａｐ，ｑ’（ただし、ｐ∈［ｎ］，ｑ∈［ｎ］）にデコミットする。つまり、シミュレータはａｐ，ｑ’＝１となる各ｐ∈［ｎ］，ｑ∈［ｎ］についてｄｐ，ｑ’：＝Ｓ＿Ｄｅｃ（Ｇ０，Ｇ１’，ｃｐ，ｑ’，１；ｒｐ，ｑ’）を計算し、｛ｄｐ，ｑ’｝ｐ∈［ｎ］，ｑ∈［ｎ］をＶに送る。
【００３５】
ＳｐｅｃｉａｌＣｏｍの秘匿性から、このシミュレーションは実際の通信系列と確かに識別不可能である。
【００３６】
Ｐの内部状態の一部のＶへの漏洩についても以下のようにシミュレートできる。
ステップ１については非特許文献１と同様の方法で内部状態（入力と乱数）の漏洩をシミュレートできる。
【００３７】
ステップ２における証明者の内部状態は証拠ｗ０とコミットに用いた乱数ｒｉ，ｊである。そのため、Ｖが関数ｆを選んだときシミュレータは内部状態の漏洩としてｆ（ｗ０，｛ｒｉ，ｊ”｝ｉ∈［ｎ］，ｊ∈［ｎ］）をシミュレートする必要がある。ｒｉ，ｊ”＝ｒｉ，ｊである必要はなく、ｗ０と｛ｃｉ，ｊ｝が｛ｒｉ，ｊ”｝ｉ∈［ｎ］，ｊ∈［ｎ］に対応すればよい。そのために、シミュレータは、Ｇ０∈Ｌｈａｍの証拠ｗ０を入力についてＳ_Ｃｏｍ（Ｇ０，Ｇ１’，０；ｒｉ，ｊ”）＝ｃｉ，ｊ’を満たすようなｒｉ，ｊ”を出力する関数Ｆ（ｗ０）＝ｒｉ，ｊ”を計算する。前述したステップ２（ａ）のシミュレーションに示したように、シミュレータはａｉ，ｊ’＝０となる（ｉ，ｊ）についてはｒｉ，ｊ”＝ｒｉ，ｊ’を知っている。一方、シミュレータはａｉ，ｊ’＝１となる（ｉ，ｊ）についてはｒｉ，ｊ’を知っているがｒｉ，ｊ”≠ｒｉ，ｊ’ではない。しかしながら、前述のようにシミュレータはＧ１’∈Ｌｈａｍの証拠ｗ１’を計算できる。そのため、ＳｐｅｃｉａｌＣｏｍの（性質４）より、シミュレータはＧ０∈Ｌｈａｍの証拠ｗ０を入力としてａｉ，ｊ’＝１へのコミットメントをａｉ，ｊ’＝０のコミットメントだと「説明」できる。言い換えると、シミュレータはａｉ，ｊ’＝０となる（ｉ，ｊ）であっても、ｒｉ，ｊ”：＝Ｓ＿Ａｄａｐｔ（Ｇ０，Ｇ１’，ｗ０，ｗ１’； ｒｉ，ｊ’）によってＳ_Ｃｏｍ（Ｇ０，Ｇ１’，０；ｒｉ，ｊ”）＝ｃｉ，ｊ’を満たすようなｒｉ，ｊ”を計算できる。よってシミュレータはこのような関数Ｆを計算できる。よって、シミュレータはｗ０を入力としてｆ’（ｗ０，Ｆ（ｗ０））を計算する関数ｆ’を選ぶと、耐漏洩ゼロ知識性の定義からｗ０に対するｆ’（ｗ０）＝ｆ（ｗ０，｛ｒｉ，ｊ”｝ｉ∈［ｎ］，ｊ∈［ｎ］）を受け取ることができ、それをＶに送ることで証明者の内部状態の漏洩をシミュレートできる。
【００３８】
以上より、本形態の方式は漏洩耐性を持つゼロ知識証明である。
【００３９】
＜ＳｐｅｃｉａｌＣｏｍの具体例＞
ＳｐｅｃｉａｌＣｏｍの具体例を示す。この具体例では、ＳｐｅｃｉａｌＣｏｍを得るために、既存技術であるハミルトン閉路コミットメント方式Ｈ＿Ｃｏｍ（例えば、参考文献１，２参照）と、適応的ハミルトン閉路コミットメント方式ＡＨ＿Ｃｏｍ（例えば、参考文献３参照）の組み合わせを行う。Ｈ＿ＣｏｍもＡＨ＿ＣｏｍもＣｏｍから構成できるコミットメント方式である。
参考文献１：Uriel Feige and Adi Shamir, “Zero knowledge proofs of knowledge in two rounds,” In Gilles Brassard,editor, Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 526-544. Springer, 1989.
参考文献２：Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai, “Universally composable two-party and multi-party secure computation,” In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montreal, Quebec, Canada, pages 494-503. ACM, 2002.
参考文献３：Yehuda Lindell and Hila Zarosim, “Adaptive zero-knowledge proofs and adaptively secure oblivious transfer,” In Omer Reingold, editor, Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009, Proceedings, volume 5444 of Lecture Notes in Computer Science, pages 183-201, Springer, 2009.
【００４０】
以下では、最初にＨＣｏｍとＡＨＣｏｍについて簡単に説明し、次にそれらを用いたＳｐｅｃｉａｌＣｏｍの構成を例示する。
【００４１】
＜ＨＣｏｍ＞
ＨＣｏｍは確率的アルゴリズムの組（Ｈ＿Ｃｏｍ，Ｈ＿Ｄｅｃ，Ｈ＿Ｖｅｒｉｆｙ）からなる非対話コミットメント方式である。
≪Ｈ＿Ｃｏｍ≫
Ｈ＿Ｃｏｍはビットｂ∈｛０，１｝とハミルトン閉路問題のインスタンスＧを入力とし、乱数ｒを生成して以下のようにｂへのコミットメントｃ←Ｈ＿Ｃｏｍ（Ｇ，ｂ）（すなわち、ｃ：＝Ｈ＿Ｃｏｍ（Ｇ，ｂ；ｒ））を出力する。
ｂ＝０へのコミット：ＰはＧ上のランダム置換π’を選び、Ｅ（０）＝π’（Ｇ）の隣接行列Ｂ（０）：＝Ｍ（Ｅ（０））を計算し、乱数ｒｉ，ｊを選択し、Ｂ（０）＝｛ｂｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（０）∈｛０，１｝をＣｏｍでコミットして得られるｃｉ，ｊ←Ｃｏｍ（ｂｉ，ｊ（０））（すなわち、ｃｉ，ｊ：＝Ｃｏｍ（ｂｉ，ｊ（０）；ｒｉ，ｊ））からなる｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］をコミットメントｃとして出力する。
ｂ＝１へのコミット：ＰはＧと同じサイズでハミルトン閉路のみを持つグラフＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））を得、乱数ｒｉ，ｊを選択し、Ｂ（１）＝｛ｂｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（１）∈｛０，１｝をＣｏｍでコミットして得られるｃｉ，ｊ←Ｃｏｍ（ｂｉ，ｊ（１））（すなわち、ｃｉ，ｊ：＝Ｃｏｍ（ｂｉ，ｊ（１）；ｒｉ，ｊ））からなる｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］をコミットメントｃとして出力する。
【００４２】
≪Ｈ＿Ｄｅｃ≫
Ｈ＿Ｄｅｃはコミットメントｃとコミットされた値ｂとコミットメントに用いられた乱数ｒを入力とし、デコミットメントｄ：＝Ｈ＿Ｄｅｃ（Ｇ，ｂ，ｃ；ｒ）を出力する。
ｂ＝０へのデコミット：Ｐはｄｉ，ｊ（０）：＝Ｄｅｃ（ｂｉ，ｊ（０），ｃｉ，ｊ；ｒｉ，ｊ）を得、｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］をデコミットメントｄとしてπ’とともに出力する。
ｂ＝１へのデコミット：Ｐはｄｉ，ｊ（１）：＝Ｄｅｃ（ｂｉ，ｊ（１），ｃｉ，ｊ；ｒｉ，ｊ）を得、｛ｄｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］をデコミットメントｄとして出力する。さらにＰはＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））をｄとともに出力する。
【００４３】
≪Ｈ＿Ｖｅｒｉｆｙ≫
Ｈ＿Ｖｅｒｉｆｙはコミットメントｃとデコミットされた値ｂとデコミットメントｄとインスタンスＧとを入力としてデコミットメントｄを検証する。
ｂ＝０の検証：ＶはＥ（０）＝π’（Ｇ）の隣接行列Ｂ（０）：＝Ｍ（Ｅ（０））を計算し、Ｂ（０）＝｛ｂｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（０）∈｛０，１｝を得、すべてのｉ∈［ｎ］，ｊ∈［ｎ］についてＶｅｒｉｆｙ（ｂｉ，ｊ（０），ｃｉ，ｊ，ｄｉ，ｊ（０））＝１であれば検証成功とし、そうでなければ検証失敗とする。
ｂ＝１の検証：ＶはＧと同じサイズでハミルトン閉路のみを持つグラフＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））を入力とし、Ｂ（１）＝｛ｂｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（１）∈｛０，１｝を得、すべてのｉ∈［ｎ］，ｊ∈［ｎ］についてＶｅｒｉｆｙ（ｂｉ，ｊ（１），ｃｉ，ｊ，ｄｉ，ｊ（１））＝１であれば検証成功とし、そうでなければ検証失敗とする。
【００４４】
（Ｃｏｍ，Ｄｅｃ，Ｖｅｒｉｆｙ）の秘匿性からＨＣｏｍも秘匿性を満たす。Ｇがハミルトン閉路を持たないときは（つまりＧ∈Ｌｈａｍが成り立たないときは）拘束性を満たす。つまり、コミットした後に０と１の両方にオープンすることはできない。なぜなら、コミットした時点でコミットしたグラフが一意に定まり、これがＧの置換でありハミルトン閉路も含むということはありえないからである。ＨＣｏｍの特徴は、Ｇ∈ＬｈａｍのときにＰがＧ∈Ｌｈａｍの証拠ｗ（つまりＧのハミルトン閉路）を知っていると０へのコミットメントを０と１の両方にオープンすることができることである。
【００４５】
＜ＡＨＣｏｍ＞
ＡＨＣｏｍは確率的アルゴリズムの組（ＡＨ＿Ｃｏｍ，ＡＨ＿Ｄｅｃ，ＡＨ＿Ｖｅｒｉｆｙ）からなる非対話コミットメント方式である。
≪ＡＨ＿Ｃｏｍ≫
ＡＨ＿Ｃｏｍはビットｂ∈｛０，１｝とハミルトン閉路問題のインスタンスＧを入力とし、乱数ｒを生成して以下のようにｂへのコミットメントｃ←ＡＨ_Ｃｏｍ（Ｇ，ｂ）（すなわち、ｃ：＝ＡＨ＿Ｃｏｍ（Ｇ，ｂ；ｒ））を出力する。
ｂ＝０へのコミット：ＰはＧ上のランダム置換π’を選び、Ｅ（０）＝π’（Ｇ）の隣接行列Ｂ（０）：＝Ｍ（Ｅ（０））を計算し、乱数ｒｉ，ｊを選択し、Ｂ（０）＝｛ｂｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（０）をＣｏｍでコミットして得られるｃｉ，ｊ←Ｃｏｍ（ｂｉ，ｊ（０））（すなわち、ｃｉ，ｊ：＝Ｃｏｍ（ｂｉ，ｊ（０）；ｒｉ，ｊ））からなる｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］をコミットメントｃとして出力する。
ｂ＝１へのコミット：ＰはＧと同じサイズでハミルトン閉路のみを持つグラフＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））を得、乱数ｒｉ，ｊを選択し、Ｂ（１）＝｛ｂｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（１）を得る。ｂｉ，ｊ（１）＝１の場合、ＰはＣｏｍでｂｉ，ｊ（１）をコミットして得られるｃｉ，ｊ←Ｃｏｍ（ｂｉ，ｊ（１））（すなわちｃｉ，ｊ：＝Ｃｏｍ（ｂｉ，ｊ（１）；ｒｉ，ｊ））を得る。ｂｉ，ｊ（１）＝０の場合、ＰはＣｏｍで０をコミットする代わりにＣｏｍ（ｂｉ，ｊ（１））と同じ長さのランダム記号列Ｃ（ｒｉ，ｊ）をｃｉ，ｊ：＝Ｃ（ｒｉ，ｊ）として得る。Ｐは｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］をコミットメントｃとして出力する。
【００４６】
≪ＡＨ＿Ｄｅｃ≫
ＡＨ＿Ｄｅｃはコミットメントｃとコミットされた値ｂとコミットメントに用いられた乱数ｒを入力とし、デコミットメントｄ：＝ＡＨ＿Ｄｅｃ（Ｇ，ｂ，ｃ；ｒ）を出力する。
ｂ＝０へのデコミット：Ｐは、ｄｉ，ｊ（０）：＝Ｄｅｃ（ｂｉ，ｊ（０），ｃｉ，ｊ；ｒｉ，ｊ）を得、｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］をデコミットメントｄとしてπ’とともに出力する。
ｂ＝１へのデコミット：Ｐはｂｉ，ｊ（１）＝１が成り立つような（ｉ，ｊ）のみについてｄｉ，ｊ（１）：＝Ｄｅｃ（ｂｉ，ｊ（１），ｃｉ，ｊ；ｒｉ，ｊ）を得、｛ｄｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］をデコミットメントｄとして出力する。さらにＰはＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））をｄｉ，ｊ（１）とともに出力する。
【００４７】
≪ＡＨ＿Ｖｅｒｉｆｙ≫
ＡＨ＿Ｖｅｒｉｆｙはコミットメントｃとデコミットされた値ｂとデコミットメントｄとインスタンスＧとを入力としてデコミットメントｄを検証する。
ｂ＝０の検証：ＶはＥ（０）＝π’（Ｇ）の隣接行列Ｂ（０）：＝Ｍ（Ｅ（０））を計算し、Ｂ（０）＝｛ｂｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（０）∈｛０，１｝を得、すべてのｉ∈［ｎ］，ｊ∈［ｎ］についてＶｅｒｉｆｙ（ｂｉ，ｊ（０），ｃｉ，ｊ，ｄｉ，ｊ（０））＝１であれば検証成功とし、そうでなければ検証失敗とする。
ｂ＝１の検証：ＶはＧと同じサイズでハミルトン閉路のみを持つグラフＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））を入力とし、Ｂ（１）＝｛ｂｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（１）∈｛０，１｝を得る。Ｖはｂｉ，ｊ（１）＝１の場合にはＶｅｒｉｆｙ（ｂｉ，ｊ（１），ｃｉ，ｊ，ｄｉ，ｊ（１））＝１を確認し、ｂｉ，ｊ（１）＝０の場合にはｃｉ，ｊがＣｏｍ（ｂｉ，ｊ（１））と同じ長さのランダム記号列であるかを確認する。すべてのｉ∈［ｎ］，ｊ∈［ｎ］について、ｂｉ，ｊ（１）＝１の場合にＶｅｒｉｆｙ（ｂｉ，ｊ（１），ｃｉ，ｊ，ｄｉ，ｊ（１））＝１となり、ｂｉ，ｊ（１）＝０の場合にｃｉ，ｊがＣｏｍ（ｂｉ，ｊ（１））と同じ長さのランダム記号列となれば検証成功とし、そうでなければ検証失敗とする。
【００４８】
ＡＨＣｏｍもＨＣｏｍと同じ性質を満たす。さらにＡＨＣｏｍでは、Ｇ∈ＬｈａｍのときＰがＧ∈Ｌｈａｍの証拠ｗ（つまりＧのハミルトン閉路）を知っていると、０へのコミットメントｃ←ＡＨ_Ｃｏｍ（Ｇ，０）を計算した後にＡＨ＿Ｃｏｍ（Ｇ，１；ｒ’）＝ｃを満たす乱数ｒ’＝｛ｒｉ，ｊ’｝ ｉ∈［ｎ］，ｊ∈［ｎ］を計算できる。この理由を示す。ＡＨ_Ｃｏｍ（Ｇ，０）の要素ｃｉ，ｊとＡＨ＿Ｃｏｍ（Ｇ，１；ｒ）の要素ｃｉ，ｊ’との間には以下の関係を想定できる。
(1)ｃｉ，ｊがｂｉ，ｊ（０）＝１へのコミットメントであるが、ｃｉ，ｊ’がランダム記号列である。
(2)ｃｉ，ｊがｂｉ，ｊ（０）＝１へのコミットメントであり、ｃｉ，ｊ’も１へのコミットメントである。
(3)ｃｉ，ｊがｂｉ，ｊ（０）＝０へのコミットメントであり、ｃｉ，ｊ’がランダム記号列である。
(4)ｃｉ，ｊがｂｉ，ｊ（０）＝０へのコミットメントであるが、ｃｉ，ｊ’は１へのコミットメントである。
(1)の場合、ｃｉ，ｊ’はランダム記号列であり、Ｃｏｍの性質からｃｉ，ｊは長さ｜ｃｉ，ｊ｜のランダム記号列と識別できない。そのため、(1)のような（ｉ，ｊ）についてはｃｉ，ｊをそのままｒｉ，ｊ’とすればよい。
(2)のような（ｉ，ｊ）についてはｃｉ，ｊの生成に用いたｒｉ，ｊをそのままｒｉ，ｊ’とすればよい。
(3)の場合、ｃｉ，ｊ’はランダム記号列であるため、(3)のような（ｉ，ｊ）についてはｃｉ，ｊをそのままｒｉ，ｊ’とすればよい。
(4)のような（ｉ，ｊ）についてはｒｉ，ｊ’を特定できない。しかしながら、Ｇ∈Ｌｈａｍであるため、証拠ｗを用いて(4)の場合を避けるようなハミルトン閉路のみを持つグラフＥ（１）を選択することは可能である。
よって上述の性質を満たす。
【００４９】
＜ＨＣｏｍとＡＨＣｏｍを用いたＳｐｅｃｉａｌＣｏｍの構成＞
ＨＣｏｍ＝（Ｈ＿Ｃｏｍ，Ｈ＿Ｄｅｃ，Ｈ＿Ｖｅｒｉｆｙ）を構成する（Ｃｏｍ，Ｄｅｃ，Ｖｅｒｉｆｙ）を（ＡＨ＿Ｃｏｍ，ＡＨ＿Ｄｅｃ，ＡＨ＿Ｖｅｒｉｆｙ）にそれぞれ置換し、ＨＣｏｍでのＧをＧ０に置換し、ＡＨＣｏｍでのＧをＧ１に置換することでＳｐｅｃｉａｌＣｏｍ＝（Ｓ＿Ｃｏｍ，Ｓ＿Ｄｅｃ，Ｓ＿Ｖｅｒｉｆｙ）を構成できる。以下に具体的に示す。
【００５０】
≪Ｓ＿Ｃｏｍ≫
Ｓ＿Ｃｏｍはビットｂ∈｛０，１｝とハミルトン閉路問題のインスタンス（グラフ）Ｇ０，Ｇ１を入力とし、乱数ｒを生成して以下のようにｂへのコミットメントｃ←Ｓ＿Ｃｏｍ（Ｇ０，Ｇ１，ｂ）（すなわち、ｃ：＝Ｓ＿Ｃｏｍ（Ｇ０，Ｇ１，ｂ；ｒ））を出力する。
ｂ＝０へのコミット：ＰはＧ０上のランダム置換π’を選び、Ｅ（０）＝π’（Ｇ０）の隣接行列Ｂ（０）：＝Ｍ（Ｅ（０））を計算し、乱数ｒｉ，ｊを選択し、Ｂ（０）＝｛ｂｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（０）∈｛０，１｝をＡＨ＿Ｃｏｍでコミットして得られるｃｉ，ｊ←ＡＨ＿Ｃｏｍ（Ｇ１，ｂｉ，ｊ（０））（すなわち、ｃｉ，ｊ：＝ＡＨ＿Ｃｏｍ（Ｇ１，ｂｉ，ｊ（０）；ｒｉ，ｊ））からなる｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］をコミットメントｃとして出力する。
ｂ＝１へのコミット：ＰはＧ０と同じサイズでハミルトン閉路のみを持つグラフＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））を得、乱数ｒｉ，ｊを選択し、Ｂ（１）＝｛ｂｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（１）∈｛０，１｝をＡＨ＿Ｃｏｍでコミットして得られるｃｉ，ｊ←ＡＨ＿Ｃｏｍ（Ｇ１，ｂｉ，ｊ（１））（すなわち、ｃｉ，ｊ：＝ＡＨ＿Ｃｏｍ（Ｇ１，ｂｉ，ｊ（１）；ｒｉ，ｊ））からなる｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］をコミットメントｃとして出力する。
前述のように、方式ＡＨ＿Ｃｏｍでの０へのコミットメントＡＨ＿Ｃｏｍ（Ｇ１，０）は、グラフＧ１に由来するグラフＴ（０）＝π’（Ｇ１）（π’はランダム置換）の隣接行列Ｕ（０）の各要素ｕｖ，ｗ（０）へのコミットメントｃｕｖ，ｗ（０）を含む集合｛ｃｕｖ，ｗ（０）｝である。ＡＨ＿Ｃｏｍでの１へのコミットメントＡＨ＿Ｃｏｍ（Ｇ１，１）は、Ｇ１と同じサイズでハミルトン閉路のみを持つグラフＴ（１）の隣接行列Ｕ（１）の各要素ｕｖ，ｗ（１）に対応するｃｕｖ，ｗ（１）を含む集合｛ｃｕｖ，ｗ（１）｝であり、要素ｕｖ，ｗ（１）＝１に対応するｃｕｖ，ｗ（１）は要素ｕｖ，ｗ（１）へのコミットメントであり、要素ｕｖ，ｗ（１）＝０に対応するｃｕｖ，ｗ（１）はランダム記号列である。
【００５１】
≪Ｓ＿Ｄｅｃ≫
Ｓ＿Ｄｅｃはコミットメントｃとコミットされた値ｂとコミットメントに用いられた乱数ｒを入力とし、デコミットメントｄ：＝Ｓ＿Ｄｅｃ（Ｇ０，Ｇ１，ｂ，ｃ；ｒ）を出力する。
ｂ＝０へのデコミット：Ｐはｄｉ，ｊ（０）：＝ＡＨ＿Ｄｅｃ（Ｇ１，ｂｉ，ｊ（０），ｃｉ，ｊ；ｒｉ，ｊ）を得、｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］をデコミットメントｄとしてπ’とともに出力する。
ｂ＝１へのデコミット：Ｐはｄｉ，ｊ（１）：＝ＡＨ＿Ｄｅｃ（Ｇ１，ｂｉ，ｊ（１），ｃｉ，ｊ；ｒｉ，ｊ）を得、｛ｄｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］をデコミットメントｄとして出力する。さらにＰはＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））をｄとともに出力する。
【００５２】
≪Ｓ＿Ｖｅｒｉｆｙ≫
Ｓ＿Ｖｅｒｉｆｙはコミットメントｃとデコミットされた値ｂとデコミットメントｄとインスタンス（グラフ）Ｇ０，Ｇ１とを入力としてデコミットメントｄを検証する。
ｂ＝０の検証：ＶはＥ（０）＝π’（Ｇ０）の隣接行列Ｂ（０）：＝Ｍ（Ｅ（０））を計算し、Ｂ（０）＝｛ｂｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（０）∈｛０，１｝を得、すべてのｉ∈［ｎ］，ｊ∈［ｎ］についてＡＨ＿Ｖｅｒｉｆｙ（Ｇ１，ｂｉ，ｊ（０），ｃｉ，ｊ，ｄｉ，ｊ（０））＝１であれば検証成功とし、そうでなければ検証失敗とする。
ｂ＝１の検証：ＶはＧと同じサイズでハミルトン閉路のみを持つグラフＥ（１）の隣接行列Ｂ（１）：＝Ｍ（Ｅ（１））を入力とし、Ｂ（１）＝｛ｂｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ｂｉ，ｊ（１）∈｛０，１｝を得、すべてのｉ∈［ｎ］，ｊ∈［ｎ］についてＡＨ＿Ｖｅｒｉｆｙ（Ｇ１，ｂｉ，ｊ（１），ｃｉ，ｊ，ｄｉ，ｊ（１））＝１であれば検証成功とし、そうでなければ検証失敗とする。
【００５３】
このようにＨＣｏｍとＡＨＣｏｍを用いたＳｐｅｃｉａｌＣｏｍは、前述の（性質１）〜（性質４）を満たす。
【００５４】
（性質１）Ｇ０∈Ｌｈａｍでなく、かつ、Ｇ１∈Ｌｈａｍでないとき（Ｇ０およびＧ１が何れもハミルトン閉路を持たないとき）は、ＡＨＣｏｍが拘束性を満たすのでＨＣｏｍの拘束性が保存されＳｐｅｃｉａｌＣｏｍも拘束性を満たす。
【００５５】
（性質２）ＡＨＣｏｍは常に秘匿性を満たすのでＨＣｏｍの秘匿性が保存されＳｐｅｃｉａｌＣｏｍも常に秘匿性を満たす。
【００５６】
（性質３）Ｇ０∈ＬｈａｍのときはＨＣｏｍの性質から０へのコミットメントを１へデコミットすることができる。
【００５７】
（性質４）Ｇ０∈ＬｈａｍかつＧ１∈Ｌｈａｍのときは、１へのコミットメントを０のコミットメントとして以下のように説明できる。１へのコミットメントを計算する際に用いたグラフをＥ（１）とする。このとき、Ｇ０∈Ｌｈａｍの証拠ｗ０を用いるとＧ０のハミルトン閉路がＥ（１）のハミルトン閉路と重なるようにＧ０を置換するπ（１）を計算することができる。このとき、ＳｐｅｃｉａｌＣｏｍにおける０へのコミットメントが１へのコミットメントと異なる点は、Ｅ（０）＝π’（Ｇ０）では枝があるがＥ（１）では枝がない部分においてＡＨ＿Ｃｏｍで０ではなく１にコミットしていることである。ここでＧ１∈ＬｈａｍのときはＡＨ＿Ｃｏｍによる０へのコミットメントを１へのコミットメントだと説明することができるため、これによりＳｐｅｃｉａｌＣｏｍによる１へのコミットメントを０のコミットメントとして説明することができる。
【００５８】
［実施形態］
次に、図面を用いて実施形態を説明する。
＜構成＞
図１に例示するように、本形態の証明システム１は証明装置１１および検証装置１２を有する。証明装置１１は、記憶部１１１、制御部１１２、前提処理部１１３、コミット部１１４、チャレンジ入力部１１５、およびデコミット部１１６を有する。検証装置１２は、記憶部１２１、制御部１２２、前提処理部１２３、コミットメント入力部１２４、チャレンジ出力部１２５、および検証部１２６を有する。証明装置１１と検証装置１２は、ネットワーク等を通じて互いに情報の送受信が可能とされている。これらの装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００５９】
＜処理＞
図２および図３を用い、本形態における漏洩耐性を持つゼロ知識証明方法を説明する。本形態では証明装置１１が検証装置１２と共有するグラフＧ０がハミルトン閉路を持つこと（つまりＧ０∈Ｌｈａｍであること）を証明する。Ｇ０∈Ｌｈａｍであることの一例は、特定の公開鍵（グラフＧ０に対応）が正しく生成されたＲＳＡ暗号の公開鍵の集合（Ｌｈａｍに対応）に属することである。
【００６０】
前処理において、証明装置１１の記憶部１１１および検証装置１２の記憶部１２１にグラフＧ０が格納される。また、記憶部１１１にはさらにＧ０∈Ｌｈａｍであることの証拠ｗ０が格納される。証拠ｗ０の例はＧ０のハミルトン閉路を表す情報であり、例えば公開鍵の素因数からなる列である。さらにセキュリティパラメータＫが設定される。Ｋは正整数であり、例えばＫ＝６４である。
【００６１】
証明装置１１の前提処理部１１３および検証装置１２の前提処理部１２３は、非特許文献１のencrypted preambleを行ってその通信系列σを得、命題σをハミルトン閉路問題に帰着したグラフＧ１を得る。encrypted preambleが正しく行われれば、Ｇ１はハミルトン閉路を持たない。Ｇ１は記憶部１１１，１２１に送られて記憶される（ステップＳ１，Ｓ２）。
【００６２】
証明装置１１の制御部１１２はｋ＝１に設定する（ステップＳ３）。コミット部１１４は、記憶部１１１からｗ０，Ｇ０，Ｇ１を読み込み、各ｉ∈［ｎ］，ｊ∈［ｎ］について乱数ｒｉ，ｊを選択し（ステップＳ４）、コミットメントｃｉ，ｊ：＝Ｓ_Ｃｏｍ（Ｇ０，Ｇ１，０；ｒｉ，ｊ）を計算する（ステップＳ５）。コミット部１１４は、｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］および｛ｒｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を記憶部１１１に格納し、｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を検証装置１２に送信する（ステップＳ６）。すなわち、コミット部１１４は、コミット対象０とグラフＧ０，Ｇ１と乱数ｒｉ，ｊとを含む情報に応じて得られる、グラフＧ１と同じサイズ（ｎ×ｎ）の零行列の各要素０へのコミットメントｃｉ，ｊを含む集合｛ｃｉ，ｊ｝を出力する。前述のように、Ｇ１およびＧ０がハミルトン閉路を持たない場合、コミット対象０への拘束性が保証される（性質１）。グラフＧ０がハミルトン閉路を持つ場合、０へのコミットメントｃｉ，ｊを１へデコミットするための値をデコミットメントｄとすることができる（性質３）。グラフＧ０およびＧ１がハミルトン閉路を持つ場合、ｂ＝１へのコミットメントｃをｂ＝０へのコミットメントとして示すことができる（性質４）。
【００６３】
｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］は検証装置１２のコミットメント入力部１２４で受信され、記憶部１２１に格納される（ステップＳ７）。チャレンジ出力部１２５は、ランダムなチャレンジｃｈ∈｛０，１｝を選択して記憶部１２１に格納し（ステップＳ８）、さらにｃｈを証明装置１１に送信する（ステップＳ９）。
【００６４】
ｃｈは証明装置１１のチャレンジ入力部１１５で受信され（入力を受け付け）、記憶部１１１に格納される（ステップＳ１０）。デコミット部１１６は記憶部１１１からｃｈを読み込み、ｃｈ＝０であるかｃｈ＝１であるかを判定する（ステップＳ１１）。
【００６５】
ここでｃｈ＝０と判定された場合、デコミット部１１６は、記憶部１１１からＧ０，Ｇ１，ｗ０，｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］，｛ｒｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を読み込み、Ｇ１上のランダム置換πを選び（ステップＳ１２）、Ｈ（０）＝π（Ｇ１）の隣接行列Ａ（０）：＝Ｍ（Ｈ（０））を計算する（ステップＳ１３）。デコミット部１１６は、｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］をＡ（０）＝｛ａｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］にデコミットするためのデコミットメントの集合｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］を得る。つまり、デコミット部１１６は、各ｉ∈［ｎ］，ｊ∈［ｎ］についてａｉ，ｊ（０）＝０ならばｄｉ，ｊ（０）：＝Ｓ_Ｄｅｃ（Ｇ０，Ｇ１，ｃｉ，ｊ，０；ｒｉ，ｊ）を計算し、ａｉ，ｊ（０）＝１ならばｄｉ，ｊ（０）：＝Ｓ＿Ｅｑｕｉｖ（Ｇ０，Ｇ１，ｗ０；ｒｉ，ｊ）を計算し、｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］を得る。デコミット部１１６は、πおよび｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］を検証装置１２に送信する。すなわち、デコミット部１１６は、チャレンジｃｈが０（第１値）である場合に、グラフＧ１に由来するグラフＨ（０）の隣接行列Ａ（０）＝｛ａｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］の各要素ａｉ，ｊ（０）にコミットメントｃｉ，ｊをデコミットするためのデコミットメントｄｉ，ｊ（０）を含む集合を出力する（ステップＳ１４）。
【００６６】
ステップＳ１４で送信されたπおよび｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］は、検証装置１２の検証部１２６で受信される（ステップＳ１５）。検証部１２６は、記憶部１２１からＧ０，Ｇ１，｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を読み込み、Ｈ（０）＝π（Ｇ１）の隣接行列Ａ（０）：＝Ｍ（Ｈ（０））＝｛ａｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］を計算し、これらと｛ｄｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］を用い、｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］が｛ａｉ，ｊ（０）｝ｉ∈［ｎ］，ｊ∈［ｎ］にデコミットされたことを確認する。つまり、検証部１２６は、すべてのｉ∈［ｎ］，ｊ∈［ｎ］についてＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，ａｉ，ｊ（０），ｃｉ，ｊ，ｄｉ，ｊ（０））＝１が成り立つことを確認する。何れかのｉ∈［ｎ］，ｊ∈［ｎ］についてＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，ａｉ，ｊ（０），ｃｉ，ｊ，ｄｉ，ｊ（０））＝１が成り立たない場合、証明失敗として処理を終了する（ステップＳ２４）。一方、すべてのｉ∈［ｎ］，ｊ∈［ｎ］についてＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，ａｉ，ｊ（０），ｃｉ，ｊ，ｄｉ，ｊ（０））＝１が成り立つ場合、制御部１２２はｋ＝Ｋであるかを判定する（ステップＳ１７）。ここでｋ＝Ｋでなければ、制御部１２２はｋ＋１を新たなｋ（すなわちｋ：＝ｋ＋１）とし（ステップＳ２６）、処理をステップＳ４に戻す。一方、ｋ＝Ｋであれば証明成功として処理を終了する（ステップＳ２５）。
【００６７】
一方、ステップＳ１１でｃｈ＝１と判定された場合、デコミット部１１６は、ハミルトン閉路のみを持つグラフＨ（１）のｎ×ｎの隣接行列Ａ（１）：＝Ｍ（Ｈ（１））をランダムに選択する（ステップＳ１８）。ただし、隣接行列Ａ（１）をＡ（１）＝｛ａｉ，ｊ（１）｝ｉ∈［ｎ］，ｊ∈［ｎ］と表記する。さらにデコミット部１１６は、記憶部１１１からＧ０，Ｇ１，ｗ０，ｒｉ，ｊを読み込み、ＳｐｅｃｉａｌＣｏｍの（性質３）を利用し、グラフＨ（１）の閉路の部分についてｃｐ，ｑ∈｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を各要素ａｐ，ｑ（１）（ただし、ｐ∈［ｎ］，ｑ∈［ｎ］）にデコミットする。つまり、デコミット部１１６は、ａｐ，ｑ（１）＝１となる各ｐ∈［ｎ］，ｑ∈［ｎ］についてｄｐ，ｑ（１）：＝Ｓ＿Ｅｑｕｉｖ（Ｇ０，Ｇ１，ｗ０；ｒｐ，ｑ）を計算し、｛ｄｐ，ｑ（１）｝ｐ∈［ｎ］，ｑ∈［ｎ］を得る。デコミット部１１６は、｛ｐ，ｑ，ｄｐ，ｑ（１）｝ｐ∈［ｎ］，ｑ∈［ｎ］を検証装置１２に送信する。すなわち、デコミット部１１６は、チャレンジｃｈが１（第１値と異なる第２値）である場合に、ハミルトン閉路のみを持つグラフＨ（１）の隣接行列Ａ（１）の要素のうち閉路をなす枝に対応する各要素ａｐ，ｑ（１）にコミットメントｃｐ，ｑ∈｛ｃｉ，ｊ｝をデコミットするためのデコミットメントｄｐ，ｑ（１）を含む集合を出力する（ステップＳ１９）。
【００６８】
ステップＳ１９で送信された｛ｐ，ｑ，ｄｐ，ｑ（１）｝ｐ∈［ｎ］，ｑ∈［ｎ］は、検証装置１２の検証部１２６で受信される（ステップＳ２０）。検証部１２６は、記憶部１２１からＧ０，Ｇ１，｛ｃｉ，ｊ｝ｉ∈［ｎ］，ｊ∈［ｎ］を読み込み、これらと｛ｐ，ｑ，ｄｐ，ｑ（１）｝ｐ∈［ｎ］，ｑ∈［ｎ］を用い、ａｐ，ｑ（１）＝１となるすべてのｐ∈［ｎ］，ｑ∈［ｎ］についてコミットメントｃｐ，ｑが１にデコミットされたことを確認する。すなわち、検証部１２６は、ａｐ，ｑ（１）＝１となるすべてのｐ∈［ｎ］，ｑ∈［ｎ］についてＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，１，ｃｐ，ｑ，ｄｐ，ｑ（１））＝１が成り立つかを判定する（ステップＳ２１）。ここで、ａｐ，ｑ（１）＝１となる何れかのｐ∈［ｎ］，ｑ∈［ｎ］についてＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，１，ｃｐ，ｑ，ｄｐ，ｑ（１））＝１が成り立たない場合、証明失敗として処理を終了する（ステップＳ２４）。一方、ａｐ，ｑ（１）＝１となるすべてのｐ∈［ｎ］，ｑ∈［ｎ］についてＳ＿Ｖｅｒｉｆｙ（Ｇ０，Ｇ１，１，ｃｐ，ｑ，ｄｐ，ｑ（１））＝１が成り立つ場合、検証部１２６は、１にデコミットされた要素ａｐ，ｑ（１）に対応する枝を持つグラフがハミルトン閉路であるかを確認する（ステップＳ２２）。ここで、このグラフがハミルトン閉路でない場合、証明失敗として処理を終了する（ステップＳ２４）。一方、このグラフがハミルトン閉路である場合、制御部１２２はｋ＝Ｋであるかを判定する（ステップＳ２３）。ここでｋ＝Ｋでなければ、制御部１２２はｋ＋１を新たなｋ（すなわちｋ：＝ｋ＋１）とし（ステップＳ２６）、処理をステップＳ４に戻す。一方、ｋ＝Ｋであれば証明成功として処理を終了する（ステップＳ２５）。
【００６９】
＜本形態の特徴＞
本形態では、ＳｐｅｃｉａｌＣｏｍを巧みに使うことで内部情報の漏洩のシミュレーションを可能とし、Yaoの二者間秘密計算プロトコルを用いずに漏洩耐性をもつゼロ知識証明の実現が可能となった。
【００７０】
［変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、Ｇをランダム置換したものを「Ｇに由来するグラフ」とした例を説明したが、Ｇそのものを「Ｇに由来するグラフ」としてもよいし、Ｇを予め定められたように置換したものを「Ｇに由来するグラフ」としてもよい。各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。
【００７１】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７２】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００７３】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００７５】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【００７６】
本発明は、例えば、サイドチャネル攻撃を受ける可能性がある環境下における電子商取引等での認証、公開鍵暗号方式等の暗号プロトコルでの公開鍵の正当性の検証などに利用できる。
【符号の説明】
【００７７】
１  証明システム
１１  証明装置
１２  検証装置
【図１】
0006392191.tif 000002
【図２】
0006392191.tif 000003
【図３】
0006392191.tif 000004