Report

Nir Bitansky and Omer Paneth The Result Assuming OT there exist a resettably-sound ZK protocol (Previous constructions of resettably-sound ZK relied on CRHF) Zero-Knowledge Proofs Zero Knowledge Soundness ∈ ℒ? Zero-Knowledge Proofs Soundness ∉ℒ ∗ Zero-Knowledge Proofs Zero Knowledge ∈ℒ ∗ Intuition: ∗ “knows” how to generate a proof itself! ∗ We can efficiently extract a proof from ∗ The Simulator Accepting transcript: ∗ Simulator The Simulator ∗ ≈ ∗ Simulator Black-Box Simulator ∗ Black Box Simulator Non-Black-Box Simulator ∗ Non Black Box Simulator Black-Box vs. Non-Black-Box Can Non-Black-Box Simulation really achieve more than Black-Box Simulation? Black-Box vs. Non-Black-Box Constant-round public-coin ZK (for NP, with negligible soundness error) Not considering 3-round ZK from KEA [Hada-Tanaka 98, Bellare-Palacio 04] CRHF + PCP Argument Black Box Simulator [Goldreich-Krawczyk 90] Non Black Box Simulator [Barak 01] Black-Box vs. Non-Black-Box Black Box Simulator Non Black Box Simulator Constant-round public-coin ZK GK90,B01 Resettably-sound ZK BGGL01 Constant-round bounded-concurrent ZK and MPC B01,PR03 Constant-round ZK with strict polynomial-time simulation\knowledge extraction BL02 Simultaneously resettable ZK and MPC DGS09,GM11 Constant-round covert MPC GJ10 Constant-round public-coin parallel ZK PRT11 Simultaneously resettable WI proof of knowledge COSV12 Non-Black-Box Simulation BGGL01,B01,PR03,BL02,DGS9,GS09, GM11,GJ10,PRT11,COSV12… Barak Barak 01 01 Non-Black-Box Simulation BGGL01,B01,PR03,BL02,DGS9,GS09, GM11,GJ10,PRT11,COSV12… Barak 01 CRHF + PCP Barak’s ZK Protocol The FLS paradigm: [Feige-Lapidot-Shamir 99] Generation protocol for trapdoor Witness indistinguishable proof that ∈ ℒ or “knows” Barak’s ZK Protocol The FLS paradigm: [Feige-Lapidot-Shamir 99] A proof generated using a witness for ∈ ℒ and a proof generated using the trapdoor are protocol indistinguishable Generation for trapdoor Witness indistinguishable proof that ∈ ℒ or “knows” Barak’s ZK Protocol Q: Can we have a trapdoor generation protocol where is public-coin? A: Not using black-box simulation. Barak’s ZK Protocol Q: Can we have a trapdoor generation protocol where is public-coin? A: (Barak 01) Yes! Trapdoor is the entire code of ∗ Problem of “Long” Trapdoor (Or: problem of “short” messages) Witness indistinguishable proof that ∈ ℒ or “knows” = ∗ ∗ is an arbitrary polynomial Barak’s ZK Protocol Fixing the problem: 1. Use a Universal Argument – a succinct witness indistinguishable proof based on PCPs [kilian 92, Barak-Goldreich 08] 2. Use a collision-resistant hash function to give a shrinking commitment to trapdoor. Non-Black-Box Simulation BGGL01,B01,PR03,BL02,DGS9,GS09, GM11,GJ10,PRT11,COSV12… Barak 01 CRHF + UA\PCP Are Barak’s techniques inherent in non-black-box simulation? No! Can its applications be achieved without collision-resistant hashing and universal arguments? Yes! Resettable Protocols Resettable Protocols Resettable Protocols Resettable ZK [Canetti-Goldreich-Goldwasser-Micali 00] ∈ℒ ∗ Resettably-Sound ZK [Micali-Reyzin 01, Barak-Goldreich-Goldwasser-Lindell 01] ∉ℒ ∗ Resettably-Sound ZK [Barak-Goldreich-Goldwasser-Lindell01, Goldreich-Krawczyk 90] Black Box Simulator Resettably-Sound ZK Black Box Simulator ∗ ∗ Black Box Simulator Resettably-Sound ZK [Barak-Goldreich-Goldwasser-Lindell 01] Non Black Box Simulator Using CRHF and UA The Result Assuming only OT there exist a constant-round resettably-sound ZK protocol that does not make use of UA. The Technique A new non-black-box simulation technique from the Impossibility of Obfuscation Program Obfuscation is an obfuscation of a function family : Πk () ≈ Πk Obfuscation and ZK If we can obfuscate ∗ : ∗ ∗ ( ) Non Black Box Simulator Black Box Simulator Resettably-Sound ZK Obfuscation and ZK Assuming OWFs, there exist a family of functions that can not be obfuscated. [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] Resettably-Sound ZK “Easy” Impossibility of obfuscation Obfuscation and ZK Assuming OWFs, there exist a family of functions that can not be obfuscated. [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] Resettably-Sound ZK “Hard” Impossibility of obfuscation + OT Unobfuscatable functions 1. ∀, ← : 2. ∃, ∀ ≡ : The Protocol = () =0 ← Secure function evaluation of () () where = () Witness Indistinguishable proof that ∈ ℒ or “knows” Proof Idea - Resettable Soundness = () ∗ () SFE of () ← ∗ Proof Idea – Zero Knowledge Non Black Box Simulator ∗ ≡ Proof Idea – Zero Knowledge ≡ = () () SFE of () ∗ Non Black Box Simulator ∗ ≡ Proof Idea – Zero Knowledge ≡ = () ⊥ ⊥ SFE of () = ⊥ ∗ w.p. w.p. 1 − Proof Idea – Zero Knowledge ≡ ′ ≡ \ ⊥ ′ ≡ \ ⊥ ∗ ⊥ () … 1 ∗ ′ ≡ \ ⊥ ∗ ⊥ () Proof Idea – Zero Knowledge Non Black Box Simulator = () =0 () ∗ ← SFE of () ≡ Witness Indistinguishable proof that ∈ ℒ or “knows” ∗ The SFE Protocol = () ∗ () SFE of () ∗ How Howto to instantiate instantiate this box? box? this = () () SFE of () ∗ ≡ The SFE Protocol Semi-honest SFE of () ZK proof of knowledge ZK proof of knowledge () The SFE Protocol Semi-honest SFE of () ZK proof of knowledge ZK proof of knowledge () The SFE Protocol Semi-honest SFE of () Resettably-sound ZK POK Based on resettably-sound ZK [BGGL01,GS09] Resettable ZK POK () The SFE Protocol = () ∗ () SFE of () ∗ ∉ℒ ∈ℒ = () () SFE of () ∗ ≡ Instance-dependent SFE ∈ℒ ∉ℒ SFE of () ZK POK Resettable POK Resettable ZK + Strongly unobfuscatable functions Instance-dependent SFE 1 3 ∈ℒ POK ∉ℒ Resettable ZK WI Instance-dependent SFE Com() 1 3 ∈ℒ POK ∉ℒ Resettable ZK Instance-dependent SFE Com () 1 3 ∈ℒ POK ∉ℒ Resettable ZK Simulation Running Time Non Black Box Simulator ∗ ≡ Simulation Running Time ≡ ′ ≡ \ ⊥ ′ ≡ \ ⊥ ∗ ⊥ ′ ≡ \ ⊥ ∗ () () poly() = … 1 ∗ ⊥ Proof Idea – Zero Knowledge Non Black Box Simulator = () =0 () ∗ ← SFE of () ≡ Witness Indistinguishable proof that ∈ ℒ or “knows” ∗ Simulation Running Time Non Black Box Simulator ∗ ≡ w.p. || = poly() w.p. 1 − poly =⋅ + 1 − ⋅ poly = poly Simulation Running Time Non Black Box Simulator ∗ ≡ () = ( 2 ) poly =⋅ 2 1 + 1 − ⋅ poly > Simulation Running Time = () =0 ← () SFE of () Witness Indistinguishable proof that ∈ ℒ or “knows” Simulation Running Time = () =0 () ← SFE of () =0 () SFE of () Witness Indistinguishable proof that ∈ ℒ or “knows” Simulation Running Time Non Black Box Simulator ∗ ≡ poly = poly =⋅ 2 + 1 − ⋅ poly = poly Comparison to [Barak 01] # rounds Assumptions Uses Trapdoor PCP\UA Length PublicCoin Barak 01 O(1) CRHF Yes Long Yes This work O(1) OT No Short No One More Application Simultaneously resettable ZK ∉ℒ ∗ ∈ℒ ∗ [BGGL 01]: Can a protocol be resettable ZK and resettably-sound simultaneously? Simultaneously resettable ZK ∉ℒ ∗ ∈ℒ [Deng-Goyal-Sahai 09]: Yes! ∗ Simultaneously resettable ZK Resettably-sound ZK Non-black-box simulation Long trapdoor Short trapdoor Black-box simulation Bounded concurrent ZK Concurrent ZK Resettable ZK Simultaneously resettable ZK Resettably-sound ZK Non-black-box simulation Short trapdoor Black-box simulation Concurrent ZK Resettable ZK Simultaneously resettable ZK = () =0 × () ← SFE of () 12] [Cho-Ostrovsky-Scafuro-Visconti Simultaneously Resettable Witness Indistinguishable proof that ∈ ℒ or “knows” ?