Cryptology ePrint Archive: Report 2013/641

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

Nir Bitansky and Ran Canetti and 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].

Category / Keywords: foundations / extractable functions, indistinguishability obfuscation, knowledge of exponent, obfuscation

Date: received 5 Oct 2013, last revised 2 Jun 2014

Contact author: nirbitan at tau ac il

Available format(s): PDF | BibTeX Citation

Version: 20140602:222234 (All versions of this report)

Short URL: ia.cr/2013/641

Discussion forum: Show discussion | Start new discussion