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

Nir Bitansky; Ran Canetti; Omer Paneth; Alon Rosen

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 functions indistinguishability obfuscation knowledge of exponent obfuscation
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: 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}
}