On the impossibility of entropy reversal, and its application to zero-knowledge proofs

Shachar Lovett and Jiapeng Zhang

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.

Available format(s)
Publication info
Keywords
statistical zero-knowledge proofentropy reversalblack-box reduction
Contact author(s)
slovett @ cs ucsd edu
jpeng zhang @ gmail com
History
Short URL
https://ia.cr/2017/922

CC BY

BibTeX

@misc{cryptoeprint:2017/922,
author = {Shachar Lovett and Jiapeng Zhang},
title = {On the impossibility of entropy reversal, and its application to zero-knowledge proofs},
howpublished = {Cryptology ePrint Archive, Paper 2017/922},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/922}},
url = {https://eprint.iacr.org/2017/922}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.