The Impossibility of Obfuscation with Auxiliary Input
This content explores the challenges and advancements in program obfuscation, private key to public key encryption, ideal obfuscation, and the evolution of obfuscation constructions. It discusses the limitations, new results, and the concept of Virtual Black-Box with a Universal Simulator.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator Nir Bitansky Ran Canetti Henry Cohn Shafi Goldwasser Yael Tauman-Kalai Omer Paneth Alon Rosen
Program Obfuscation ? y Program Obfuscation ? y Obfuscated program
Private Key to Public Key ? cipher ?????(?) Obfuscation ? cipher Public Key
Ideal Obfuscation Hides everything about the program except for its input\output behavior Point Function etc. [Canetti 97, Wee 05, Bitansky- Canetti 10, Canetti-Rothblum-Varia 10] Unobfuscatable Functions [Barak-Goldreich-Impagliazzo- Rudich-Sahai-Vadhan-Yang 01] All functions ?
Obfuscation Constructions Before 2013: No general solution. All functions All functions
Obfuscation Constructions Before 2013: No general solution. 2013: Candidate obfuscation for all circuits [Garg-Gentry-Halevi-Raykova-Sahai-Waters 13] All functions All functions
New Impossibility Result Under computational assumptions, a natural notion of ideal obfuscation cannot be achieved for a large family of cryptographic functionalities. (strengthen the impossibility of [Goldwasser-Kalai 05])
Virtual Black-Box (VBB) [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] Algorithm ? is an obfuscator for a class ? if: For every PPT adversary ? there exists a PPT simulator ? such that for every ? ? and every predicate ?(?): ? ? ? ?(?) ?(?) Inefficient!
Using Obfuscation Reduction ? ? = ? ? ?,? ?
VBB with a Universal Simulator Algorithm ? is an obfuscator for a class ? if: There exists a PPT simulator ? such that for every PPT adversary ? such that for every ? ? and every predicate ?(?): ? ? ?(?) ?(?) ?(?)
Universal Simulation Universal Simulators Black-box Simulators Barak s ZK simulator
New Impossibility Result Under computational assumptions, VBB obfuscation with a universal simulator cannot be achieved for a large family of cryptographic functionalities.
Pseudo-Entropic functions A function family ?? has super-polynomial pseudo- entropy if there exists a set of inputs ? such that for a random function ??, there exists ? with super-polynomial min-entropy: ? ? ? 1 2 3 ??(?)\Z ??(1) ??(2) ??(3)
Examples Pseudo-random functions Semantically-secure encryption (when the randomness is a PRF of the message) ? cipher ????? ? ????
New Impossibility Result Under computational assumptions, VBB obfuscation with a universal simulator is impossible for any pseudo-entropic function
Indistinguishability Obfuscation [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] ?(?2) ?(?1) ? ?2 ?1 Assumption: indistinguishability obfuscation for all circuits (A candidate construction given in [GGHRSW13])
This Work Assuming indistinguishability obfuscation, VBB obfuscation with a universal simulator is impossible for any pseudo-entropic function
This Work Worst-case VBB with a universal simulator Average-case VBB with a universal simulator Is Impossible for pseudo-entropic functions Is Impossible for pseudo-entropic functions Assuming Assuming indistinguishability obfuscation for all functions indistinguishability obfuscation for point-filter functions or equivalently, witness encryption
Worst-case VBB with a universal simulator Average-case VBB with a universal simulator [Goldwasser-Kalai 05]: Is Impossible for Filter functions Is Impossible for pseudo-entropic functions Unconditionally Assuming VBB obfuscation for point-filter functions This work: Is Impossible for pseudo-entropic functions Is Impossible for pseudo-entropic functions Assuming Assuming indistinguishability obfuscation for all functions indistinguishability obfuscation for point-filter functions
Universal Simulation and Auxiliary Input For every PPT adversary ? there exists a PPT simulator ? such that for every ? ?, every predicate ? ? and every auxiliary input ?: ? ? ? ? ? ?(?) ?(?) VBB with a universal simulator
Universal Simulation and Auxiliary Input Worst-case VBB with a universal simulator Average-case VBB with a universal simulator Average-case VBB with independent auxiliary input Worst-case VBB with dependent auxiliary input
Proof Idea What can we do with an obfuscated code that we cannot do with black-box access? [Goldwasser-Kalai 05]: Find a polynomial size circuit computing the function!
Impossibility for Worst-Case VBB Let ?? be a family of PRFs. Fix the simulator ?. Sample a random ??. Construct an adversary ? (that depends on ??) that fail ?. Let ? be the set of inputs 1,2, ,2 ? ?? ??,?? : If ? = ? ?? and ? ? = ??(?): output the secret ?, else output . ? ?\ ? ? ??(?)
Impossibility for Worst-Case VBB ?? ? ? ?\ ? ?(??) ? ? ? ??(?)
Using Indistinguishability Obfuscation ? ? ? ?\ ?\ ? ? ? ??(?) ? ? ? ? ?\ ?\ ? ? ? ? ??(?) ?
Impossibility for Average-Case VBB ? ? ?\ ? ? ? ???? ? ??(?) ?(?) ??? : If ? = ? ?? : output ? = ????(?(?)) else output .
Impossibility for Average-Case VBB ? ? ???? ? ?(?) Obfuscation should hide ??????? Use Indistinguishability Obfuscation together with puncturable pseudo-random functions
