Cryptology ePrint Archive: Report 2021/836

Towards a Unified Approach to Black-Box Constructions of Zero-Knowledge Proofs

Xiao Liang and 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.

Category / Keywords: cryptographic protocols / Zero-Knowledge, Black-Box, Separation

Original Publication (with major differences): IACR-CRYPTO-2021

Date: received 18 Jun 2021

Contact author: liang1 at cs stonybrook edu, omkant at cs stonybrook edu

Available format(s): PDF | BibTeX Citation

Note: The full version of the conference version.

Version: 20210621:075657 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]