### On Virtual Grey Box Obfuscation for General Circuits

```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)
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.
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)
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:
[Pass-Seth-Telang 13]
2. Multilinear subgroup elimination assumption
[Gentry-Lewko-Sahai-Waters 14]
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
IO
[Pass-Seth-Telang 13]
Semantically secure*
VGB for  1
Semantically secure*
VGB for  1
Results
Semantically secure
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
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
Semantically secure*
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
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

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