Paper 2021/836
Towards a Unified Approach to BlackBox Constructions of ZeroKnowledge Proofs
Xiao Liang and Omkant Pandey
Abstract
Generalpurpose zeroknowledge proofs for all \textsf{NP} languages greatly simplify secure protocol design. However, they inherently require the code of the underlying relation. If the relation contains blackbox calls to a cryptographic function, the code of that function must be known to use the ZK proof, even if both the relation and the proof require only blackbox access to the function. Rosulek (Crypto'12) shows that nontrivial proofs for even simple statements, such as membership in the range of a oneway function, require nonblackbox access. We propose an alternative approach to bypass Rosulek's impossibility result. Instead of asking for a ZK proof directly for the given oneway function $f$, we seek to construct a \textit{new} oneway function $F$ given only blackbox access to $f$, \textit{and} an associated ZK protocol for proving nontrivial statements, such as range membership, over its output. We say that $F$, along with its proof system, is a \textit{proofbased} oneway function. We similarly define proofbased versions of other primitives, specifically pseudorandom generators and collisionresistant hash functions. We show how to construct proofbased versions of each of the primitives mentioned above from their ordinary counterparts under mild but necessary restrictions over the input. More specifically,  We first show that if the prover entirely chooses the input, then proofbased pseudorandom generators cannot be constructed from ordinary ones in a blackbox manner, thus establishing that some restrictions over the input are necessary.  We next present blackbox constructions handling inputs of the form $(x,r)$ where $r$ is chosen uniformly by the verifier. This is similar to the restrictions in the widely used GoldreichLevin theorem. The associated ZK proofs support range membership over the output as well as arbitrary predicates over prefixes of the input. Our results open up the possibility that generalpurpose ZK proofs for relations that require blackbox access to the primitives above may be possible in the future without violating their blackbox nature by instantiating them using proofbased primitives instead of ordinary ones.
Note: The full version of the conference version.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2021
 Keywords
 ZeroKnowledgeBlackBoxSeparation
 Contact author(s)

liang1 @ cs stonybrook edu
omkant @ cs stonybrook edu  History
 20210621: received
 Short URL
 https://ia.cr/2021/836
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/836, author = {Xiao Liang and Omkant Pandey}, title = {Towards a Unified Approach to BlackBox Constructions of ZeroKnowledge Proofs}, howpublished = {Cryptology ePrint Archive, Paper 2021/836}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/836}}, url = {https://eprint.iacr.org/2021/836} }