Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions

Haitner Iftach; Shaltiel Ronen

Paper 2004/335

Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions

Haitner Iftach and Shaltiel Ronen

Abstract

A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any additional information but the validity of the claim. Naor et al., Journal of Cryptology 1998, showed how to implement such a protocol using any one-way permutation. We achieve such a protocol using any approximable-preimage-size one-way function. These are one-way functions with the additional feature that there is a feasible way to approximate the number of preimages of a given output. A special case is regular one-way functions where each output has the same number of preimages. Our result is achieved by showing that a variant of the computationally-binding bit-commitment protocol of Naor et al. can be implemented using a any one-way functions with ``sufficiently dense'' output distribution. We construct such functions from approximable-preimage-size one-way functions using ``hashing techniques'' inspired by Hastad et al., SIAM Journal on Computing 1998.

Metadata

Available format(s): PS
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): iftach haitner @ weizmann ac il
History: 2004-12-02: received
Short URL: https://ia.cr/2004/335
License: CC BY

BibTeX

@misc{cryptoeprint:2004/335,
      author = {Haitner Iftach and Shaltiel Ronen},
      title = {Statistical Zero-Knowledge Arguments for {NP} Using Approximable-Preimage-Size One-Way Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/335},
      year = {2004},
      url = {https://eprint.iacr.org/2004/335}
}