On Virtual Grey Box Obfuscation for General Circuits

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!

similar documents