Paper 2013/468

How To Construct Extractable One-Way Functions Against Uniform Adversaries

Nir Bitansky, Ran Canetti, and Omer Paneth


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$. % under $f$. 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. 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.

Note: revision includes \thanks.

Available format(s)
Publication info
Preprint. Minor revision.
Knowledge ExtractionExtractable FunctionsZero-KnowledgeNon-Black-Box Techniques
Contact author(s)
nirbitan @ tau ac il
2014-06-02: last of 3 revisions
2013-08-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Ran Canetti and Omer Paneth},
      title = {How To Construct Extractable One-Way Functions Against Uniform Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2013/468},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.