Welcome to the resource topic for 2012/711
Title:
Unprovable Security of 2-Message Zero Knowledge
Authors: Kai-Min Chung, Edward Lui, Mohammad Mahmoody, Rafael Pass
Abstract:Goldreich and Oren (JoC’94) show that only languages in BPP have 2-message zero-knowledge arguments. In this paper we consider weaker, super-polynomial simulation (SPS), notions of zero-knowledge. We present barriers to using black-box reductions for demonstrating soundness of 2-message protocols with efficient prover strategies satisfying SPS zero-knowledge. More precisely, if poly(T(n))-hard one-way functions exist for a super-polynomial T(n), the following holds about 2-message efficient prover arguments over statements of length n. 1. Black-box reductions cannot prove soundness of 2-message T(n)-simulatable arguments based on any polynomial-time intractability assumption, unless the assumption can be broken in polynomial time. This complements known 2-message quasi-polynomial-time simulatable arguments using a quasi-polynomial-time reduction (Pass’03), and 2-message exponential-time simulatable proofs using a polynomial-time reduction (Dwork-Naor’00, Pass’03). 2. Back-box reductions cannot prove soundness of 2-message strong T(n)-simulatable arguments, even if the reduction and the challenger both can run in poly(T(n))-time, unless the assumption can be broken in poly(T(n)) time. Strong T(\cdot)-simulatability means that the output of the simulator is indistinguishable also for poly(T(\cdot))-size circuits, with a negl(T(\cdot)) indistinguishability gap. This complements known 3-message strong quasi-polynomial-time simulatable proofs (Blum’86, Canetti et~al’~00), or 2-message quasi-polynomial-time simulatable arguments (Khurana-Sahai’17, Kalai-Khurana-Sahai’18) satisfying a relaxed notion of strong simulation where the distinguisher’s size can be large, but the distinguishing gap is negligible in n.
ePrint: https://eprint.iacr.org/2012/711
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .