The impossibility of obfuscation with auxiliary input or a universal simulator

DOI10.1007/978-3-662-44381-1_5MaRDI QIDQ2874531zbMATH OpenOpenAlexFDO

Authors Nir Bitansky, Ran Canetti, Henry Cohn, Yael Tauman Kalai, Omer Paneth, Alon Rosen, Shafi Goldwasser

Publication date 7 August 2014

Published in Advances in Cryptology – CRYPTO 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0348

Mathematics Subject Classification ID

Cryptography (94A60)

Abstract: In this paper we show that the existence of general indistinguishability obfuscators conjectured in a few recent works implies, somewhat counterintuitively, strong impossibility results for virtual black box obfuscation. In particular, we show that indistinguishability obfuscation for all circuits implies: * The impossibility of average-case virtual black box obfuscation with auxiliary input for any circuit family with super-polynomial pseudo-entropy. Such circuit families include all pseudo-random function families, and all families of encryption algorithms and randomized digital signatures that generate their required coin flips pseudo-randomly. Impossibility holds even when the auxiliary input depends only on the public circuit family, and not the specific circuit in the family being obfuscated. * The impossibility of average-case virtual black box obfuscation with a universal simulator (with or without any auxiliary input) for any circuit family with super-polynomial pseudo-entropy. These bounds significantly strengthen the impossibility results of Goldwasser and Kalai (STOC 2005).

Recommendations

• Impossibility of quantum virtual black-box obfuscation of classical circuits
• scientific article; zbMATH DE number 1842483
• On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input
• On the (im)possibility of obfuscating programs
• On best-possible obfuscation

Cited in

(26)

• On the complexity of simulating auxiliary input
• On virtual grey box obfuscation for general circuits
• On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input
• New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries
• Impossibility of quantum virtual black-box obfuscation of classical circuits
• Obfuscated fuzzy Hamming distance and conjunctions from subset product problems
• On constructing one-way permutations from indistinguishability obfuscation
• On the Impossibility of Virtual Black-Box Obfuscation in Idealized Models
• Indistinguishability obfuscation: from approximate to exact
• On the correlation intractability of obfuscated pseudorandom functions
• Perfect structure on the edge of chaos. Trapdoor permutations from indistinguishability obfuscation
• On constructing one-way permutations from indistinguishability obfuscation
• Contention in cryptoland: obfuscation, leakage and UCE
• A unified approach to idealized model separations via indistinguishability obfuscation
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Limits on the power of indistinguishability obfuscation and functional encryption
• Pseudorandom functions: three decades later
• Patchable indistinguishability obfuscation: \(i\mathcal {O}\) for evolving software
• On the impossibility of approximate obfuscation and applications to resettable cryptography
• Obfuscation for evasive functions
• Structure-preserving compilers from new notions of obfuscations
• Quantum depth in the random oracle model
• On the need for large quantum depth
• Pseudorandom obfuscation and applications
• Powerful primitives in the bounded quantum storage model
• Lower bounds on the overhead of indistinguishability obfuscation

This page was built for publication: The impossibility of obfuscation with auxiliary input or a universal simulator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874531)