Report

On Virtual Grey-Box Obfuscation for General Circuits Nir Bitansky Ran Canetti Yael Tauman-Kalai Omer Paneth Program Obfuscation Program y Obfuscation y Obfuscated program Private Key to Public Key () cipher Obfuscation cipher Public Key Virtual Black-Box (VBB) [Hada 00, 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 (): () Pr (()) = () = Pr = ± Impossibility Results for VBB Impossible for some functions. [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] Impossible for all pseudo-entropic functions w.r.t auxiliary input (assuming IO). [Goldwasser-Kalai 05, Bitansky-Canetti-Cohn-Goldwasser-Kalai-P-Rosen 14] Indistinguishability Obfuscation (IO) [Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01] 1 (1 ) ≡ 2 ≈ (2 ) History 2000-2013: No general solution. Obfuscation for simple functions: [C97,W05,CD08,CRV10,BC10,BR13] 2013: Candidate obfuscation for all circuits [Garg-Gentry-Halevi-Raykova-Sahai-Waters 13] What is the security of the candidate obfuscator? Assumption: the [GGHRSW13] obfuscator is IO Many recent applications: [Garg-Gentry-Halevi-Raykova-Sahai-Waters 13, Sahai-Waters 13, Hohenberger-Sahai-Waters 13, Garg-Gentry-Halevi-Raykova 13, Bitansky-Canetti-P-Rosen 13, Boneh-Zhandry 13, Brzuska-FarshimMittelbach 14, Bitansky-P 14, Ramchen-Waters 14] Better assumption: 1. Semantically-secure graded encodings [Pass-Seth-Telang 13] 2. Multilinear subgroup elimination assumption [Gentry-Lewko-Sahai-Waters 14] What about other applications? Example: point function Can we get more then IO? Today: virtual grey-box Simulation Definition for IO [Bitansky-Canetti 10] 1 ≡ 2 ⇒ (1 ) ≈ (2 ) Weak VBB: () ≈ Computationally unbounded Virtual black-box: Simulator is bounded [Bitansky-Canetti 10] Virtual grey-box (VGB): Simulator is semi-bounded unbounded computation Indistinguishability: Simulator is unbounded polynomial number of oracle queries Virtual black-box: Simulator is bounded meaningful Pseudo-random functions [Bitansky-Canetti 10] Virtual grey-box (VGB): Simulator is semi-bounded Not meaningful meaningful Point functions Indistinguishability: Simulator is unbounded Not meaningful Assume the [GGHRSW13] obfuscation is VGB. Or better yet, prove it! Results Semantically secure graded encoding IO [Pass-Seth-Telang 13] Semantically secure* graded encoding VGB for 1 Semantically secure* graded encoding VGB for 1 Results Semantically secure graded encoding Semantically secure* mutlilinear jigsaw puzzles Semantically secure* mutlilinear jigsaw puzzles IO [Pass-Seth-Telang 13] VGB for 1 VGB for all circuits Results Semantically secure graded encoding Semantically secure* mutlilinear jigsaw puzzles Semantically secure* mutlilinear jigsaw puzzles Semantically secure mutlilinear jigsaw puzzles IO [Pass-Seth-Telang 13] VGB for 1 VGB VBB for new families New Feasibility Results For VBB Existing VBB results: • Point functions [Canetti 97, Wee 05] • Constant-size set functions [Bitansky-Canetti 10] • Constant-dimension hyperplanes [Canetti-Rothblum-Varia 10] New results: • Fuzzy point functions (Hamming balls) • Constant-dimension linear subspaces • Conjunctions (worst-case) Unified proof for all existing VBB results. Results Semantically secure graded encoding Semantically secure* graded encoding Semantically secure* mutlilinear jigsaw puzzles Semantically secure mutlilinear jigsaw puzzles IO [Pass-Seth-Telang 13] VGB for 1 VGB VBB for new families Indistinguishability Simulation IND-secure encryption SIM-secure encryption Witness indistinguishable proofs Zero-knowledge proofs IND-secure functional encryption SIM-secure functional encryption Indistinguishability obfuscation Obf. w. Unbounded simulation ? VGB obfuscation [Goldwasser-Micali 82] [Feige-Lapidot-Shamir 99] [De Caro-Iovino-Jain-O'Neill-P-Persiano 13] [Bitansky-Canetti 10] This work Strong indistinguishability obfuscation Virtual grey-box obfuscation Indistinguishability Obfuscation For every pair of circuits 1 , 2 : ∀: 1 = 2 () 1 ≈ 2 Strong Indistinguishability Obfuscation For every pair of distributions on circuits 1 , 2 : ∀: Pr 1 = 2 ≥ 1 − negl 1 ≈ 2 VGB from Semantic Security Semantically-secure graded encoding* Strong IO for 1 Virtual grey-box obfuscation for 1 The Equivalence. Strong indistinguishability obfuscation Virtual grey-box obfuscation Strong IO ⇐ VGB Let 1 , 2 be distributions on circuits such that: ∀: Pr 1 = 2 ≥ 1 − negl For every distinguisher : 2 1 1 ≈ ≈ ≈ 2 The Equivalence. Strong indistinguishability obfuscation Virtual grey-box obfuscation Strong IO ⇒ VGB: The Challenge 1 if Point Function: () = 0 if ( ) = ≠ 1 0 if = if ≠ 1 0 if = if ≠ High-Level Simulation Strategy High-Level Simulation Strategy High-Level Simulation Strategy High-Level Simulation Strategy High-Level Simulation Strategy High-Level Simulation Strategy Extract a information about C from the adversary First Step: Concentrated Functions A family of boolean functions is concentrated around a function if for every input : Pr = ← ≥ 1 − negl( ) Starting Point The simulator queries on a “splitting” input The simulator queries on a “splitting” input The simulator queries on a “splitting” input The simulator queries on a “splitting” input The Concentrated Family There is no splitting input to query Warm Up: Point Functions [Canetti 97] Let be a strong IO for point functions. For an adversary let be the set of points such that: Pr = 1 − Pr =1 ≥ How to simulate an obfuscation of ? If ∉ simulation is trivial. if ∈ the simulator can learn with a small number of oracle queries. (( )) (()) if if ∈ ∉ For an adversary let be a set of functions such that: Pr = 1 − Pr = 1 ≥ Claim: = poly( 1 , ). Proof: By the definition of we have that: ← ≉ . However, if is super polynomial: ∀: Pr ← = ≥ 1 − negl Main Step: General Concentrated Functions Let be a strong IO for . For an adversary let be the set of functions ∈ s.t: Pr = 1 − Pr =1 ≥ The set may be large! To simulate an obfuscation of ∈ D: 1. If ∉ simulation is trivial. 2. if ∈ then simulator can learn a “separating” input s.t. ≠ () in a small number of oracle queries. 3. Set 2 = ∈ | ≠ () . Note: 2 ≪ . 4. Repeat. 2 ≠ 2 2 ≠ 2 2 2 3 ≠ 2 2 2 3 2 ≠ 2 2 3 3 3 ≠ 2 2 When ∈ , how to learn a separating input s.t. ≠ () in a small number of oracle queries? Claim: There exists a set of separating inputs such that: 1 1. = poly( , ). 2. For every ∈ , there exists ∈ Z such that ≠ () Proof: By the definition of we have that: ← ≉ . Find an input that is separating for a noticeable fraction of the functions in . Such exists since otherwise: ∀: Pr = ← ≥ 1 − negl Add to , set = ∖ | ≠ , and repeat. Two sources of inefficiency 1. Learning the function: – Finding splitting inputs to concentrate 2. Learning the adversary: – Finding the bad set – Finding the set of separating inputs Summary • VGB is more meaningful than IO and probably more achievable than VBB. • Strong IO ⇔ VGB. • More applications of VGB. • The quest for the “right” definition is not over. Thanks!