A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any setup assumption, so it is actually an "NP proof system."
A noninteractive bit commitment scheme based on any one-way function.
The specific NW-type generator we need is a hitting set generator fooling nondeterministic circuits. It is known how to construct such a generator if ETIME = DTIME(2^O(n)) has a function of nondeterministic circuit complexity 2^\Omega(n) (Miltersen and Vinodchandran, FOCS `99).
Our witness-indistinguishable proofs are obtained by using the NW-type generator to derandomize the ZAPs of Dwork and Naor (FOCS `00). To our knowledge, this is the first construction of an NP proof system achieving a secrecy property.
Our commitment scheme is obtained by derandomizing the interactive commitment scheme of Naor (J. Cryptology, 1991). Previous constructions of noninteractive commitment schemes were only known under incomparable assumptions.Category / Keywords: foundations / Publication Info: An extended abstract of this paper appeared in CRYPTO 2003. Date: received 9 Oct 2005 Contact author: shienjin at eecs harvard edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20051010:092516 (All versions of this report) Discussion forum: Show discussion | Start new discussion