現代暗号史_ゼロ知識

現代暗号史_ゼロ知識

現代暗号史

  • 分類
    • 分布の識別不可能性
      • Perfect, Statistical, Computationally
    • 証明者の能力
      • Unlimited or Poly-time
    • 検証者の能力
    • 多重性
      • Sequential, Parallel, Concurrent
    • シミュレータの能力
      • Black-Box or Non-Black-Box, さらにはSimulate出来ないもの(UC), Resetable (こっちだったかな?)
    • ラウンド数
      • Constant, Log, Poly etc.

歴史

  • 1982, Goldwasser, Mical, Rackoff. "The Knowledge Complexity of Interactive Proof Systems"
    • ゼロ知識証明の概念の初出.
    • FOCS '83, STOC '84, FOCS '84とrejectされたらしい……最終的にSTOC '85でaccept.
  • 1987, Goldreich, Micali, Wigderson. "How to Play any Mental Game - A Completeness Theorem for Protocols with Honest Majority"
    • commitmentを利用して全てのNPについてゼロ知識証明を構成.
    • KatzだったかKilianがArgumentヴァージョンを作っていたような.
  • 1987, Fiat, Shamir. "How to Prove Yourself: Practical Solution to Identification and Signature Problems" (Crypto '86)
    • Honest Verifierゼロ知識を3 roundで実行.
    • Verifierの質問はpublic coinなので, Random Oracleで代用して1回にする話(だった筈)
  • 1999, Feige, Lapidot, Shamir. "Multiple Non-Interactive Zero-Knowledge Proofs Under General Assumptions" (1999か?)
    • ゼロ知識証明の応用例の紹介(Goldreich曰く)
  • 1990, Feige, Shamir.
    • witness indistinguishabilityの定式化.

Zero-Knowledgeの定義

  • GMR版 (Sequentialで落ちるのでよろしくない)
  • Expected-time simulation (Goldreich曰く, よくないらしい)
  • UC simulation
    • rewindingなし
    • Compositionについて閉じているが, 2者間だとCRSなり何なりの仮定が必要.
  • Black-box simulation
    • rewindingあり (入力テープと乱数テープは制御するが, 中は知らない)
  • Non-black-box simulation
    • rewindingどころか検証者のプログラムを読める
    • 2001 Barak "How to Go Beyond the Black-Box Simulation Barrier"
  • Auxiliary-input simulation
    • V*ごとにシミュレータが存在する

GMR版の定義とUC版の定義だとどっちが強い?

GO94ではCl(BB-Sim) ⊆ Cl(AI-Sim) ⊆ Cl(GMR)が示されている. Cl(BB-Sim) ⊆ Cl(NBB-Sim)は自明か?


大雑把な分類

Zero-Knowledgeを何回もする場合.

sequential Zero-Knowledge

  • 1990. O. Goldreich, H. Krawczyk. "On the Composition of Zero-Knowledge Proof Systems" (ICALP 1990, J. of Computing 1996)
    • auxialiy-input zero-knowledgeなら連続的に行っても大丈夫という話. 最初のGMRの定義だと落ちる. (P-evasive ensemble)
    • 1989. O. Goldreichh, H. Krawczyk. "Sparse Pseudorandom Distributions" (CRYPTO 1989, Random Structures and Algorithms, Volume 3, 1992) の結果を使っている.
  • 1994. O. Goldreich, Y. Oren. "Definitions and Properties of Zero-Knowledge Proof Systems" (J. of Crypt. 1994(7):pp. 1-32)

paralell Zero-Knowledge

  • 1990. Goldreich, Krawczyk. "On the Composition of Zero-Knowledge Proof Systems" (ICALP 1990, J. of Computing 1996)
  • 2002. Goldreich "Concurrent Zero-Knowledge With Timing, Revisited"
    • 一般には言えない. auxialy-input ZK, black-box simulation ZKでも落ちる. 昔の論文だとparalellとconcurrentをそこまで区別していない.

concurrent Zero-Knowledge

  • 1998. Dwork, Naor, Sahai "Concurrent Zero-Knowledge"
  • 1999. Richardson, Kilian "On the Concurrent Composition of Zero-Knowledge Proofs"
  • 2001. Kilian, Petrank "Concurrent and Resettable Zero-Knowledge in Poly-logarithmic Rounds"
  • 2001. Barak "How to Go Beyond the Black-Box Simulation Barrier"
  • 2001. Canetti, Kilian, Petrank, Rosen "Black-Box Cuncurrent Zero-Knowledge Requires Ω(log n) Rounds"

resetable Zero-Knowledge (rZK)

  • 忘れた.
  • Canetti-Goldreich-Goldwasser-MIcaliのResettable Zero Knowledge (STOC00).
  • Proverの乱数を固定して, VerifierがProverをResetする.
  • 派生として Barak-Goldreich-Goldwasser-Lindell の Resettably-Sound Zero Knowledge and Its Applications (FOCS01)がある. VerifierがResetされても健全性が保たれるようなZK. rZKの構成などに利用できる.
  • rZKでBPK (Bare Public Key)モデルを導入したことにより健全性に one-time, sequential, concurrent, resettableという4つのsoundnessが定義されることになった.

最近の話?

R. Pass and A. Rosen "New and Improved Constructions of Non-Malleable Cryptographic Protocols" (STOC 2005)のイントロから拾ったNon-Malleableに注目した流れ.

Man-in-the-Middleされた場合にもゼロ知識って出来るの? という話.

ちなみにこの論文, Commitmentを作ってからZKPを作るでは無く, 逆の発想でZKPを作ってからCommitmentを作るらしい.

  • 1998 Di Crescenzo, Ishai, Ostrovski "Non-Interactive and Non-Malleable Commitment"
    • CRS仮定をおいてnon-malleable (wrt. opening) commitmentを作る
  • 1999 Sahai "Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security"
    • CRS仮定をおいてnon-interactive non-malleable Zero-knowledge protocolを作る
  • 2000 Fischlin, Fischlin "Efficient Non-Malleable Commitment Schemes"
    • CRS仮定をおいてnon-malleable (wrt. opening) commitmentを作る
  • 2001 Di Crescenzo, Katz, Ostrovski, Smith "Efficient and Non-Interactive Non-Malleable Commitment"
    • CRS仮定をおいてnon-malleable commitmentを作る
  • 2001 De Santis, Di Crescenzo, Ostrovski, Persiano, Sahai "Robust Non-Interactive Zero Knowledge"
    • CRS仮定をおいてnon-interactive non-malleable Zero-knowledge protocolを作る
  • 2003 Damgard, Groth "Non-Interactive and Reusable Non-Malleable Commitment Schemes"
    • CRS仮定をおいてnon-malleable commitmentを作る
  • 2002 Barak "Constant-Round Coin-Tossing or Realizing the Shared Random String Model" (FOCS 2002)
    • CRSを2者間で実現するにはどうするか. Man-in-the-Middleアタックは仮定無しだと防げないので, どうにかして折り合いをつける話.

で、こういうことが出来るからCRS仮定は怪しいとか言われるのか?

言語のクラスに関する話(←タイトル不適切かも)

以下 Computational Zero Knowledge Interactive Proof を CZKIP のように略す.

{\cal BPP}\subset{\cal PZKIP}\subseteq{\cal SZKIP}\subset{\cal CZKIP}={\cal IP}

最後の等号は One-Way Function の存在を仮定して成立する. 最初と三番目の厳密な包含関係は広く信じられている仮定(多項式時間階層が第二層までつぶれるようなことはない)の下で成立する. 二つ目の関係は open problem である.

Perfect Zero Knowledge Interactive Proof

random self-reducibility という性質を持つ言語に対して存在する.

Tompa and Woll (STOC 89だっけ?) で解析されている.

NP問題に入るかどうかわからないグラフ非同型問題がPZKIPを持つことが知られている.

Statistical Zero Knowledge Interactive Proof

Fortnow (1989?) によりNP完全問題がSZKPをもつと多項式時間階層が第二層までつぶれることが示されているので, NP完全問題に対してSZKPは存在しそうも無い. (よってPZKPも)

岡本先生による以下の結果.

  • Honet Verifier SZKP (HVSZKP) = SZKP
  • Public-coin SZKP = Private-coin SZKP
  • SZKP with Black-Box simulators = SZKP with non-Black-Box simulator
  • SZKP = co-SZKP
  • unbounded round SZKP = bounded round SZKP

Computational Zero Knowledge Interactive Proof

OWFを仮定するとIPに属する任意の言語に対して存在する.

またVadhanによる以下の結果が知られている.

  • Honet Verifier CZKP (HVCZKP) = CZKP
  • Public-coin CZKP = Private-coin CZKP
  • CZKP with Black-Box simulators = CZKP with non-Black-Box simulator

問題のクラスに関する結果であり round complexity に関する話ではないことに注意.

Perfect Zero Knowledge Argument

One-Way Permutationの存在を仮定すると任意のNP命題に対して存在する.

Statistical Zero Knowledge Argument

OWFの存在を仮定して任意のNP命題に対して存在する.

Computational Zero Knowledge Argument

なんぞありましたかね.

Non-Interactive Perfect Zero Knowledge Interactive Proof

Non-Interactive Statistical Zero Knowledge Interactive Proof

Non-Interactive Computatinal Zero Knowledge Interactive Proof

Non-Interactive Perfect Zero Knowledge Argument

Non-Interactive Statistical Zero Knowledge Argument

Non-Interactive Computatinal Zero Knowledge Argument

Round Complexity に関する話

  • 3-round public-coin Black-Box Zero KnowledgeはBPPに含まれる.
  • 2-round CZKはBPPに含まれる. [Goldreich and Oren]
  • 3-round Black-Box CZKはBPPに含まれる. [Goldreich and Krawczyk]
  • NP言語に対してConstant round public-coin Zero Knowledge Proofは存在しそうに無い,というconjectureがある.
  • 4-round Black-Box CZKはcoMAに含まれる [Katz 2007]
    • ePrintで発見. 正しいかどうかは不明.
    • 結果, 多項式階層が潰れないならばNP完全な言語は4-round Black-Box CZK証明を持たない.
  • Black-Box Concurrent ZKは \tilde{\Omega}(n) round 必要.
Note
GNIはcoNPに含まれる. また, 4-round SZKIPを持つ. [Goldwasser, Micali, Rivest 1988]

Non-Interactive Zero Knowledge

Shared Random Strings を仮定して存在する.

参考資料