Paper 2014/402

On the Existence of Extractable One-Way Functions

Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen

Abstract

A function f is extractable if it is possible to algorithmically ``extract,'' from any adversarial 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 *knowledge assumption* on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliary-input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. STOC 2014
DOI
10.1145/2591796.2591859
Contact author(s)
nirbitan @ tau ac il
History
2014-06-02: revised
2014-06-02: received
See all versions
Short URL
https://ia.cr/2014/402
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/402,
      author = {Nir Bitansky and Ran Canetti and Omer Paneth and Alon Rosen},
      title = {On the Existence of Extractable One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/402},
      year = {2014},
      doi = {10.1145/2591796.2591859},
      note = {\url{https://eprint.iacr.org/2014/402}},
      url = {https://eprint.iacr.org/2014/402}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.