Paper 2013/641

Indistinguishability Obfuscation vs. Auxiliary-Input Extractable Functions: One Must Fall

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

Abstract

We show that if there exist indistinguishability obfuscators for all circuits then there do not exist auxiliary-input extractable one-way functions. In particular, the knowledge of exponent assumption with respect to adversaries with auxiliary input is false in any group where computing discrete logarithms is intractable. The proof uses the “punctured programs” technique of [Sahai-Waters 2013].

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
extractable functionsindistinguishability obfuscationknowledge of exponentobfuscation
Contact author(s)
nirbitan @ tau ac il
History
2014-06-02: revised
2013-10-10: received
See all versions
Short URL
https://ia.cr/2013/641
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/641,
      author = {Nir Bitansky and Ran Canetti and Omer Paneth and Alon Rosen},
      title = {Indistinguishability Obfuscation vs. Auxiliary-Input Extractable Functions: One Must Fall},
      howpublished = {Cryptology ePrint Archive, Paper 2013/641},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/641}},
      url = {https://eprint.iacr.org/2013/641}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.