Challenges in Constant-Round Public-Coin Zero-Knowledge Proofs

The paper discusses the implausibility of constant-round public-coin zero-knowledge proofs, exploring the limitations and complexities in achieving them. It delves into the fundamental problem of whether such proofs exist, the challenges in soundness error reduction, and the difficulties in parallel repetition. Additionally, it highlights the breakthrough by Barak in constructing a constant-round public-coin zero-knowledge argument. The content emphasizes the barriers, impossibility results, and non-black-box strategies in this area of cryptography research.

• Zero-Knowledge Proofs
• Constant Round
• Public-Coin
• Impossibility Results
• Cryptography

nstai Follow

Uploaded on Sep 13, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs Yi Deng IIE,Chinese Academy of Sciences (Beijing) Joint work with Juan Garay, San Ling, Huaxiong Wang and Moti Yung On the Implausibility of Constant-Round Public-Coin ZK Proofs 1

2. The problem: Do constant-round public-coin ZK proofs exist? Public-coin constructions are broadly applicable and versatile Deep connection to other fundamental problems, such as the Fiat-Shamir Heuristic On the Implausibility of Constant-Round Public-Coin ZK Proofs 2

3. Earlier public-coin protocols 3-round public-coin ZK proofs for NP [Blum 86,GMW86] Zero knowledge (By rewinding) Common input: x a P V e {0,1} Soundness Large soundness error: cheating prob. = 1/2 z What we want: Constant-round public-coin ZK proofs with negligible soundness error On the Implausibility of Constant-Round Public-Coin ZK Proofs 3

4. Parallel repetition doesnt help much x Reduces soundness error exponentially Preserves round complexity P V a e {0,1} z But: Not known to be zero knowledge parallelizing (BB simulator does not exist!) Pass et al. [PTW 10] Parallel repetion for public-coin protocol does not preserve BB ZK in general P V a1, a2, , an e1, e2, , en ei {0,1} z1,z2, ,zn On the Implausibility of Constant-Round Public-Coin ZK Proofs 4

5. Impossibility result for black-box simulation [GK96] w.r.t. both proof and argument Soundness only holds against PPT prover Surprisingly, Barak broke the above black-box barrier, constructing constant-round public-coin ZK argument for NP On the Implausibility of Constant-Round Public-Coin ZK Proofs 5

6. Baraks non-black-box ZK argument Barak s argument In the simulation, S computes Z=Com(h(V*),s) (using the code of V*) x L h V P Z = Com(h( ),s) r Prove (WIUA): x L OR there exists s.t. Z = Com(h( )) and (z) outputs r in time nlogn On the Implausibility of Constant-Round Public-Coin ZK Proofs 6

7. Striking properties of Baraks simulator x L h V* Straight-line i.e., no rewinding S(V*) Z = Com(h(V*),s) r Uses the code of V* without understanding it! Prove (WIUA): x L OR there exists s.t. Z = Com(h( )) and (z) outputs r in time nlogn On the Implausibility of Constant-Round Public-Coin ZK Proofs 7

8. Probably not Is it a proof system? Two facts Barak s protocol 1. There are too many pre-images for a single hash value x L 2. There infinitely many different codes 1, 2, that compute the same function (z) = r h V P* Z = Com(h(0n)) r Prove (WIUA): x L OR there exists s.t. Z = Com( ) and (z) outputs r in time nlogn P* may be able to find a code such that (z) = r and Z = Com(h(0n)) = Com(h( )) On the Implausibility of Constant-Round Public-Coin ZK Proofs 8

9. Would known NBB techniques help? Earlier negative evidence (for arbitrary reduction) [BLV03]: entropy-preserving hash functions exist No constant-round public-coin ZK proofs But such hash functions cannot be based on standard assumptions via BB reduction [BDGJKLW13] We give new negative evidence for universal simulation case. On the Implausibility of Constant-Round Public-Coin ZK Proofs 9

10. Universal simulators ZK property requires the mere existence of a simulator: For every V*, there exists a simulator S But we often prove ZK property by . Constructing a single universal simulator S for every V* Almost all simulators are universal: BB simulator Barak s NBB simulator On the Implausibility of Constant-Round Public-Coin ZK Proofs 10

11. Our main result We will deal with honest public-coin verifier (functionalities) Canonical ZK proof: It is sufficient to feed S with only partial code of V* in simulation Given a random tape r = [r1, r2, , rm], ri: randomness for step i, The honest verifier V(r)= [V1(r1), V2(r2), , Vm(rm)]: the step i function: Vi(hist, ri) = ri All known ZK protocols are canonical For a common type of constant-round public-coin proof system, if it has a universal simulator S But we consider Arbitrary code of the honest verifier functionality V* = [V*1, V*2, , V*m] each V*iis functionally equivalent (FE) to some Vi(ri): FE V*i(hist) Vi: V*i(hist)=Vi(hist, ri) = ri Then S can be used to distinguish some non-trivial functionality of the (possibly obfuscated) code of V* On the Implausibility of Constant-Round Public-Coin ZK Proofs 11

12. Our main result (3) For a common type constant-round public-coin proof system, if it has a universal simulator S This is in sharp contrast with all known public-coin protocols! Known straight-line S: it generates the prefix (r1, p1,, rk-1, pk-1) before executing V*k. There exist a code V [V1, V2, , Vk-1] a set of verifier step k (V1k, ,Vtk) a code V*k random one of (V1k, ,Vtk) Distinguish functionality of V*k. without executing V*k? r1 S(x,V , V*k) V1 ... This shows that constructing constant-round public-coin ZK proof (if exists) requires paradigm shifting simulation technique! p1 V rk-1 Vk-1 pk-1 ? V*k S must encode some functionality property of V*k in the session prefix before the verifier s k-th step! s.t. there is an alg U, U (r1, p1,, rk-1, pk-1)=j and V*k Vik On the Implausibility of Constant-Round Public-Coin ZK Proofs 12

13. Proof sketch (step 1): Lemma 1 (an improvement of Babai-Moran derandomization [BM88]) There exist p random tapes (r1,r2, rp) s.t. any false x ri1 Vi=V(ri) P*(r1,r2, rp) p1 P* knows the set of random tapes from which V will choose rim pm accept <1-1/p ri=[ri1, ri2, , rim] Let m be the round number and q the length of a prover msg Babai-Moran [BM88]: p=qm Improved: p=(q/log n)m On the Implausibility of Constant-Round Public-Coin ZK Proofs 13

14. Proof sketch (step 2): Lemma 2 There exists a false statement x and p random tapes (r1,r2, rp) of the verifier such that a false x a false x ri1 ri1 P*(r1,r2, rp) Vi=V(ri) S(V*) V* Vi=V(ri) p1 p1 & rim rim pm pm accept < 1-1/p accept w/ prob. 1 ri=[ri1, ri2, , rim] On the Implausibility of Constant-Round Public-Coin ZK Proofs 14

15. Proof sketch (last step): Now we group the p verifiers V1, Vp(Vi=V(ri)) as follows: If two verifiers Viand Vjshare the same first k-1 next-message- steps [V1, ,Vk-1] (i.e., they share the same randomness up to the (k-1)-st step), we put them in the same group V1 Each represents a next-msg-function (determined by the randomness used for this step) V2 VK-1 On the Implausibility of Constant-Round Public-Coin ZK Proofs 15

16. Proof sketch (last step): Now we group the p verifiers V1, Vp(Vi=V(ri)) as follows: If two verifiers Viand Vjshare the same first k-1 next-message- steps [V1, ,Vk-1] (i.e., they share the same randomness up to the (k-1)-st step), we put them in the same group V1 Each represents a next-msg-function (determined by the randomness used for this step) V2 VK-1 Each path represents a verifier A tree represents a group of verifiers Vm Vm+1 Vn On the Implausibility of Constant-Round Public-Coin ZK Proofs 16

17. Proof sketch (last step): We now have (a polynomial number of) trees V1 V2 VK-1 Vn Vp V1 V2 Vm-1Vm On the Implausibility of Constant-Round Public-Coin ZK Proofs 17

18. Proof sketch (last step): We then prove that there is a tree sharing the same [V1, ,Vk-1], but have t different k-th steps, V1k, ,Vtk, and a code V [V1, ,Vk-1] V1 V2 V VK-1 V1K V2K VtK Vn Vp V1 V2 Vi-1Vm On the Implausibility of Constant-Round Public-Coin ZK Proofs 18

19. Proof sketch (last step): We then prove that there is a tree sharing the same [V1, ,Vk-1], but have t different k-th steps, V1k, ,Vtk, and a code V [V1, ,Vk-1] such that for any code V*k Vik S(V ,V*k) will generate a prefix (r1, ,p (k-1)) Based on this prefix (r1, ,p (k-1)) : r1 p1 (By lemma 2 and canonical property) If V*k Vik, an all-powerful prover will make a random verifier in the subtree Ti(rooted at Vik) accept with prob. 1 r2 V S(V ,V*k) p(k-2) rk-1 pk-1 Vik (By Babai-Moran) There exists at least one bad subtree Tj (rooted at Vjk) such that an all-powerful prover will make a random verifier in this tree accept with prob. < 1-1/t V1k Vik Vtk Thus, based on the prefix (r1, ,p (k-1)), we can construct an algorithm U(r1, ,p (k-1)) that finds the bad subtree Tj(i.e., find the root Vik V*k) by exhaustive search Vm Vn This completes the proof Ti Tj (bad) On the Implausibility of Constant-Round Public-Coin ZK Proofs (good) 19

20. Summary Showed connection between existence of constant- round public-coin ZK proofs and a seemingly unrelated program functionality distinguishing problem Typical goal in reverse-engineering attempts with static analysis Thus, new evidence against existence of constant- round public-coin ZK proofs, as it would imply 1. A positive result in above distinguishing problem, commonly believed to be notoriously hard, or 2. A major paradigm shift in simulation strategies, beyond the only known technique applicable to argument systemsThanks! On the Implausibility of Constant-Round Public-Coin ZK Proofs 20