Paper 2012/523

The Curious Case of Non-Interactive Commitments

Mohammad Mahmoody and Rafael Pass

Abstract

It is well-known that one-way permutations (and even one-to-one one-way functions) imply the existence of non-interactive commitments. Furthermore the construction is black-box (i.e., the underlying one-way function is used as an oracle to implement the commitment scheme, and an adversary attacking the commitment scheme is used as an oracle in the proof of security). We rule out the possibility of black-box constructions of non interactive commitments from general (possibly not one-to-one) one-way functions. As far as we know, this is the first result showing a natural cryptographic task that can be achieved in a black-box way from one-way permutations but not from one-way functions. We next extend our black-box separation to constructions of non-interactive commitments from a stronger notion of one-way functions, which we refer to as \emph{hitting} one-way functions. Perhaps surprisingly, Barak, Ong, and Vadhan (Siam JoC '07) showed that there does exist a non-black-box construction of non-interactive commitments from hitting one-way functions. As far as we know, this is the first result to establish a ``separation'' between the power of black-box and non-black-box use of a primitive to implement a natural cryptographic task. We finally show that unless the complexity class NP has program checkers, the above separations extend also to non-interactive instance-based commitments, and 3-message public-coin honest-verifier zero-knowledge protocols with O(log n)-bit verifier messages. The well-known classical zero-knowledge proof for NP fall into this category.

Note: It is a more polished version.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Crypto 2012
Keywords
Non-Black-Box ConstructionsBlack-Box SeparationsOne-Way FunctionsNon-Interactive CommitmentsZero-Knowledge ProofsProgram Checkers.
Contact author(s)
mahmoody @ gmail com
rafael @ cs cornell edu
History
2012-09-10: revised
2012-09-06: received
See all versions
Short URL
https://ia.cr/2012/523
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/523,
      author = {Mohammad Mahmoody and Rafael Pass},
      title = {The Curious Case of Non-Interactive Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2012/523},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/523}},
      url = {https://eprint.iacr.org/2012/523}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.