On the Impossibility of Entropy Reversal, and Its Application to Zero-Knowledge Proofs
Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is th
- PDF / 364,559 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 164 Views
Abstract. Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is that in NISZK only very limited communication is allowed between the verifier and the prover. It is an open problem whether these two classes are in fact equal. In this paper, we rule out efficient black box reductions between SZK and NISZK. We achieve this by studying algorithms which can reverse the entropy of a function. The problem of estimating the entropy of a circuit is complete for NISZK. Hence, reversing the entropy of a function is equivalent to a black box reduction of NISZK to its complement, which is known to be equivalent to a black box reduction of SZK to NISZK [Goldreich et al. CRYPTO 1999]. We show that any such black box algorithm incurs an exponential loss of parameters, and hence cannot be implemented efficiently.
Keywords: Entropy reversal Black-box reductions
1
·
Statistical zero-knowledge proofs
·
Introduction
The notion of Zero-Knowledge Proof Systems was introduced in the seminal paper of Goldwasser et al. [11]. Informally, an interactive proof system is a protocol that involves a computational unbounded prover P and a polynomial time verifier V . The prover attempts to convince the verifier that an assertion is a YES instance x of some promise problem. A promise problem Π consists of two disjoint sets ΠY and ΠN , e.g., yes instances and no instances. A zero-knowledge proof system for the problem Π requires the following three conditions: – Completeness: If x ∈ ΠY , then Pr[(P, V )(x) accepts] ≥ 2/3. – Soundness: If x ∈ ΠN , then for every adversary P ∗ , Pr[(P ∗ , V )(x) accepts] ≤ 1/3. S. Lovett and J. Zhang—Research supported by NSF CAREER award 1350481. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 31–55, 2017. https://doi.org/10.1007/978-3-319-70500-2_2
32
S. Lovett and J. Zhang
– Zero-knowledge: There is a polynomial time simulator S such that S(x) and (P, V )(x) are “indistinguishable”, for every x ∈ ΠY . Different zero knowledge proof systems differ in the allowed communication protocol, and in the notion of indistinguishability applied to the simulator. In this paper, we restrict our attention to statistical proof systems (SZK and NISZK), where the corresponding notion is that of statistical indistinguishability. Statistical zero knowledge (SZK). The complexity class SZK consists of the problems that have a statistical zero-knowledge proof, where any efficient interactive communication is allowed between the verifier and the prover. Surprisingly, there are complete problems for SZK which have nothing to do with interaction. This was first discovered by Sahai and Vadhan [17]. A distribution D over {0, 1}m is said to be efficiently sampleable if there exists a polynomial size boolean circuit C : {0, 1}n → {0, 1}m , such that the distribution D can be ob
Data Loading...
