We give the first construction of extractable one-way functions assuming only standard hardness assumptions (e.g. the subexponential Learning with Errors Assumption). Our functions are extractable against adversaries with bounded polynomial advice and unbounded polynomial running time. We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions.
The construction uses ideas from [Barak, FOCS01] and [Barak, Lindell, and Vadhan, FOCS03], and rely on the recent breakthrough construction of privately verifiable $\P$-delegation schemes [Kalai, Raz, and Rothblum]. The extraction procedure uses the program evaluating $f$ in a non-black-box way, which we show to be necessary.Category / Keywords: foundations / Knowledge Extraction, Extractable Functions, Zero-Knowledge, Non-Black-Box Techniques Date: received 29 Jul 2013, last revised 2 Jun 2014 Contact author: nirbitan at tau ac il Available format(s): PDF | BibTeX Citation Note: revision includes \thanks. Version: 20140602:221446 (All versions of this report) Discussion forum: Show discussion | Start new discussion