The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS'12) instead requires the existence of an Oblivious Transfer protocol.
In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.
Category / Keywords: foundations / non-black-box simulations, resettable security, one-way functions, zero-knowledges Date: received 6 Jan 2013, last revised 5 Feb 2013 Contact author: chung at cs cornell edu Available formats: PDF | BibTeX Citation Note: Section 6.3 was added in the revision. Version: 20130205:210855 (All versions of this report) Discussion forum: Show discussion | Start new discussion