Welcome to the resource topic for 2021/836
Title:
Towards a Unified Approach to Black-Box Constructions of Zero-Knowledge Proofs
Authors: Xiao Liang, Omkant Pandey
Abstract:General-purpose zero-knowledge 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 black-box 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 black-box access to the function. Rosulek (Crypto’12) shows that non-trivial proofs for even simple statements, such as membership in the range of a one-way function, require non-black-box access. We propose an alternative approach to bypass Rosulek’s impossibility result. Instead of asking for a ZK proof directly for the given one-way function f, we seek to construct a \textit{new} one-way function F given only black-box access to f, \textit{and} an associated ZK protocol for proving non-trivial statements, such as range membership, over its output. We say that F, along with its proof system, is a \textit{proof-based} one-way function. We similarly define proof-based versions of other primitives, specifically pseudo-random generators and collision-resistant hash functions. We show how to construct proof-based 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 proof-based pseudo-random generators cannot be constructed from ordinary ones in a black-box manner, thus establishing that some restrictions over the input are necessary. - We next present black-box 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 Goldreich-Levin 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 general-purpose ZK proofs for relations that require black-box access to the primitives above may be possible in the future without violating their black-box nature by instantiating them using proof-based primitives instead of ordinary ones.
ePrint: https://eprint.iacr.org/2021/836
Talk: https://www.youtube.com/watch?v=vpm-tkjQGrU
Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/422/slides.pptx
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 .