**How To Construct Extractable One-Way Functions Against Uniform Adversaries**

*Nir Bitansky and Ran Canetti and Omer Paneth*

**Abstract: **A function $f$ is extractable if it is possible to algorithmically ``extract,'' from any program that outputs a value $y$ in the image of $f,$ a preimage of $y$.
When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard {\em knowledge assumption} on certain functions.

We give the first construction of extractable one-way functions assuming only standard hardness assumptions (e.g.,subexponential security of Decision Diffie-Hellman or Quadratic Residousity). 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 Aug 2013

**Contact author: **nirbitan at tau ac il

**Available format(s): **PDF | BibTeX Citation

**Note: **revision includes \thanks.

**Version: **20130802:131151 (All versions of this report)

**Short URL: **ia.cr/2013/468

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]