Report

Ran Canetti, Huijia (Rachel) Lin, Omer Paneth Zero-Knowledge Proofs • Completeness • Soundness ∈ ℒ? Zero-Knowledge Proofs • Completeness • Soundness • Zero-knowledge ∈ℒ ∗ Zero-Knowledge [Goldwasser-Micali-Rackoff 85] • ∗ learn nothing except " ∈ ℒ" • ∗ knows how to generate a proof • There is a Simulator that efficiently extracts a proof from ∗ Two Types of Zero-Knowledge proofs Public-Coin Protocols 1 ← 1 2 ← 2 Concurrent Composition 1 2 1 2 3 3 4 4 ∗ State of the Art Constant-round public-coin zero-knowledge [Barak 01] Concurrent zero-knowledge [Richardson-Kilian 99] [Kilian-Petrank 01] [Prabhakaran-Rosen-Sahai 02] Question Is there a public-coin concurrent zero-knowledge protocol? Yes! (well, almost) Technical Motivation Combine state of the art simulation techniques Applications to concurrent 2PC [Goyal 13] What are the existing simulation techniques? The Simulator Simulator proof transcript ∗ How does the simulator ∗ extract a proof from ? The FLS Paradigm [Feige-Lapidot-Shamir 90] Set a trapdoor statement such that only knows a trapdoor witness Witness Indistinguishable proof for ∈ ℒ or for a trapdoor statement The FLS Paradigm Simulator ∗ proof transcript trapdoor witness How does the simulator extract a trapdoor witness? Rewinding 1 Question-answer slot 4 Rewinding 1 ′ ′ + ′ = Trapdoor witness 4 ∗ Other Techniques • Public-coin protocols [Goldreich-Krawczyk 96] • Concurrent composition [Dwork-Naor-Sahai 98] Public-Coin Protocols 0 ′ Goldreich-Krawczyk 96: ′ ∗ No black-box simulator and ′ are independent Public-Coin Protocols The solution: Non-black-box simulation [Barak 01] Concurrent Composition 1 1 4 4 ∗ Concurrent Composition 1 ′ 1 1 ′ ′ 4 ′ 4 ′ ′ ∗ Concurrent Composition 1 ′ 1 1 ′ ′ ′′ ′′′ ′ ′′ ′′′ 4 4 ′ ′ ∗ Concurrent Composition The solution: Rewinding with many slots [Richardson-Kilian 99] [Kilian-Petrank 01] [Prabhakaran-Rosen-Sahai 02] Current Techniques rewinding stand-alone private-coin zero-knowledge rewinding with many slots concurrent zero-knowledge [RK,KP,PRS] non-black-box simulation public-coin zero-knowledge [Barak 01] This work public-coin concurrent zero-knowledge Barak’s Protocol (sketch) = COM(Π) Witness indistinguishable proof for ∈ ℒ or trapdoor statement Trapdoor statement: the program Π predicts the randomness before it was sent Barak’s Protocol = COM(Π) Witness indistinguishable proof for ∈ ℒ or Π c → Trapdoor statement: ∃Π: = COM Π ∧ Π → Barak’s Protocol Soundness: ∗ can not commit to Π that predicts Zero-knowledge: Π = ∗ = COM(Π) = COM( ∗ ) Witness indistinguishable proof ∗ Proof that () → for ∈ ℒ or Π c → ∗ Concurrent Barak = COM( ∗ ) ∗ Proof Proof that ∗ () → Concurrent Barak = COM( ∗ ⋅, , "Proof" ) Proof ∗ (, , "Proof") → ∗ Folklore Approach [Deng-Goyal-Sahai 09] [Pass-Rosen-Tseng 11] [Goyal-Jain-Ostrovsky-Richelson-Visconti 13] Folklore Approach = COM( ∗ ⋅, , "Proof" ) Proof ∗ Folklore Approach = COM(′) ′ Proof Proof that ′() → ∗ Simulation Running Time = COM(′) = COM(′) ′ Proof that ′() → Proof that ′() → ∗ ′ Simulation Running Time ′ ′ ′ ≥ 2 ′ ′ Proof that ′ () → Proof that ′() → ′ Simulation Running Time ′ ≥ 2 ′ ′ ≥ 2 ′ ≥ 4 ′ … ′ Proof that ′ () → Proof that ′() → Proof that ′() → ′ ′ Recursive Rewinding 1 2 ′ 2 1 1 ′ 2 2 ′ 2 ′′ 2 ′′′ 3 3 ′ 3 ′′ 3 ′′′ 4 4 ′ 3 3 ′ ∗ The Problem Simulate Prove a ≥2⋅ a proof statement Roadmap add slots stand-alone private-coin zero-knowledge non-black-box simulation public-coin zero-knowledge [Barak 01] concurrent zero-knowledge [RK,KP,PRS] simulation runtime is exponential concurrent compassion public-coin concurrent zero-knowledge Concurrent Zero-Knowledge 1 1 Slot 1 2 2 6 Slot Concurrent Zero-Knowledge 1 1 1 ′ 1 1 ′ 2 1 + 1 ′ 2 6 ∗ Concurrent Zero-Knowledge 1 1 1 2 2 ′ 2 2 ′ 2 + 2 ′ 6 ∗ Concurrent Zero-Knowledge ∗ Concurrent Zero-Knowledge ∗ Concurrent Zero-Knowledge ∗ The KP-PRS Strategy The KP-PRS Strategy The Protocol 1 = COM(Π) 1 … Slot Slot = COM(Π) WI proof for ∈ ℒ or ∃i, Π: = COM Π ∧ Π → Simulation Black-box world - Rewinding Non-black-box world – Proving Simulation = COM(′) KP-PRS Block ′ Round complexity 1+ log for > 0 Proof that ′ ( ) → ∗ A Caveat Simulation constructs many long proof Solved by using memory delegation Need all session to use one hash function The Global Hash Model ℎ ← ℋ collision-resistant hash function The Global Hash Model Breaking soundness Explicit uniform reduction Finding collisions The Global Hash Model Uniform Hash Function Protocol in the plain model against uniform adversaries The Global Hash Model SHA-256 Protocol in the plain model from human ignorance [Rogaway 06] GHM vs. CRS Common reference string model Global hash model Simulated with a trapdoor Simulation for every ℎ Public-coin concurrent zero-knowledge NIZK Black-box impossibility [Pass-Tseng-Wikström] What is next? • [Goyal 13]: Public-coin concurrent zero-knowledge with poly() rounds without a global hash • Open question: Public-coin concurrent zero-knowledge with O(log ) rounds without a global hash • Open question: Concurrent zero-knowledge with o(log ) rounds [slide: Mira Blenekiy]