Slides

Report
Boaz Barak
Sanjam Garg
Yael Tauman Kalai
Omer Paneth
Amit Sahai
Program Obfuscation

 ()
cipher
Obfuscation

Public Key
cipher
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  ∈ :

()

()
≈

VBB Impossibility
[Barak-Goldreich-Impagliazzo-Rudich-Sahai-Vadhan-Yang 01]
There exists contrived “unobfuscatable” programs.
Code of a program
equivalent to 

Secret

()
Execute
 
on itself
Secret

First Candidate Obfuscation
[Garg-Gentry-Halevi-Raykova-Sahai-Waters 13]
What is the security of the candidate?
Assumption:
The [GGHRSW13] obfuscator is an
Indistingushability Obfuscator.
Indistinguishability Obfuscation ():
Noevery
known
except
[BGIRSVY01].
For
pairattacks
of equivalent
circuits
1 ≡ 2 :
 1 ≈ (2 )
This Work
A variant of the [GGHRSW13]
obfuscator is VBB for all circuits
in a generic model
(underlying algebra is idealized)
Multilinear Maps
[Boneh-Silverberg 03, Garg-Gentry-Halevi 13]
Encoding 

of  ∈  under a set  ⊆  .
1.

1,2,5
± 
1,2,5
2.

1,2,5
± 
3,4
3.  
1,…,
= ±
= ⋅
1,2,5
1,2,3,4,5
= 1 iff  = 0
Idealy: any other operation is hard.
The Generic MM Model


1 , 2 , E3 , E4 , E5

()
6 , 7 , E8 , E9 , E10
()
()
Add
Multiply
ZT
Our Result
Virtual Black-Box obfuscation in
the generic MM model:
1
1. For NC .
2. For P/Poly assuming LWE.
Avoiding VBB Impossibility
In the Generic MM Model
Code of a program
equivalent to 

Secret
Add
Mul
ZT
()
Execute
 
on itself
Secret
Interpretation
Secure obfuscation against “algebraic attacks”.
Warning:
Non-algebraic attacks do exist [BGIRSVY01].
Interpretation II
+
This Work:
VBB with Generic
Multilinear Maps
Multi-Message
Semantically-Secure
Multilinear Maps
[Pass-Seth-Telang 13]
 for P/Poly
(assuming LWE)
Virtual gray-box
obfuscation for NC1
[Pass-Seth-Telang 13]
[Bitansky-Canetti-Kalai-P 14].
Previous Works
[GGHRSW13]
[Canetti-Vaikuntanathan13]
 in the Generic
Colored Matrix Model
VBB from Black-Box
Pseudo-Free Groups
[Brakerski-Rothblum13]
 in the Generic
MM Model
This Work
[Brakerski-Rothblum13]
Assuming BSH
VBB in the Generic
MM Model
The Construction
1. Construction for NC1 via branching programs
2. Bootstrap to P/Poly assuming LWE
(leveled-FHE with decryption in NC1 )
Branching Programs
Program:
10
20
30
40
50
60
70
80
90
0
10
0
11
0
12
11
21
31
41
51
61
71
81
91
1
10
1
11
1
12
Input:
1
2
3
4
BP Evaluation
Program:
10
20
30
40
50
60
70
80
90
0
10
0
11
0
12
11
21
31
41
51
61
71
81
91
1
10
1
11
1
12
or
⊥
Input:
0
1
1
0
Output: ⊤
Obfuscating BP
1. Randomizing
2. Encoding
[Kilian 88]
Step 1: Randomizing
Program:
10
20
30
40
50
60
70
80
90
0
10
0
11
0
12
11
21
31
41
51
61
71
81
91
1
10
1
11
1
12
or
⊥
Input:
1
2
3
4
Output: ⊤
Step 1: Randomizing
Program:
10
20
30
40
50
60
70
80
90
0
10
0
11
0
12
11
21
31
41
51
61
71
81
91
1
10
1
11
1
12
or
⊥
Input:
0
1
1
0
Output: ⊤
Step 2: Encoding
Program:
10
20
30
40
50
60
70
80
90
0
10
0
11
0
12
11
21
31
41
51
61
71
81
91
1
10
1
11
1
12
{1}
{2}
{3}
{4}
{5}
{6}
{7}
{8}
{9}
{10} {11} {12}
Obfuscation includes the encodings:


∀ level , bit  , ⊤
12
⊤
{1, … , 12}
Proof of Security
40
10
21
50
31
80
61
71
1
10
1
11
…
+
0
12
90
60
20
11
31
+ ⋅
?
⊤
41
=0
51
0
10
71
81
91
1
11
1
12
Simulation Outline
Test every monomial separately:
40
10
21
50
61
31
By querying 
80
0
1
71
1
0
12
90
1
10
0
1
11
Problems
1. Inconsistent monomials:
40
10
21
31
80
51
61
0
12
90
71
2. Too many monomials:
0
1
10 + 11 ⋅ 20 + 21 ⋅ … ⋅ 12
+ 12
1
10
1
11
Changing the Sets
{1}
{2}
{3}
{4}
{5}
{6}
{7}
{8}
{9}
{10} {11} {12}
10
20
30
40
50
60
70
80
90
0
10
0
11
0
12
11
21
31
41
51
61
71
81
91
1
10
1
11
1
12
{1}
{2}
{3}
{4}
{5}
{6}
{7}
{8}
{9}
{10} {11} {12}
⊤
{1, … , 12}
Changing the Sets
1
1′
2
2′
3
3′
4
4′
5
5′
6
6′
7
7′
8
8′
9
9′
10
20
30
40
50
60
70
80
90
0
10
0
11
0
12
11
21
31
41
51
61
71
81
91
1
10
1
11
1
12
1
1′
2
2′
3
3′
4
4′
5
5′
6
6′
7
7′
8
8′
9
9′
10
10′
10
10′
11
11′
11
11′
12
12′
12
12′
⊤
1, … , 12
1′, … , 12′
Changing the Sets
1
1′
5
5′
9
9′
10
50
90
11
51
91
1
1′
5
5′
9
9′
Straddling Set System
1,5,9
1′, 5′, 9′
1
1′
5
5′
9
9′
10
50
90
11
51
91
1
5′
5
9′
9
1′
=
9
1
5
∪ ′ ∪ ′
9
1′
5
0-matrices
=
1
9
5
∪
∪
5′
1′
9′
1-matrices
Straddling Set System
1
1′
5
5′
9
9′
10
50
90
11
51
91
1
5′
5
9′
9
1′
Straddling Set System
1
1′
2
2′
3
3′
4
4′
5
5′
6
6′
7
7′
8
8′
9
9′
10
10′
11
11′
12
12′
1
5′
2
6′
3
7′
4
8′
5
9′
6
10′
7
11′
8
12′
9
1′
10
2′
11
3′
12
4′
Too Many Monomials
0
1
10 50 90 + 11 51 91 ⋅ … ⋅ 40 80 12
+ 41 81 12
+
⋅ …⋅
+
Pairing Level Together
From Two Levels to One
10
10′
8
8′
0
90 10
90
0
10
1
90 10
91
1
10
0
91 10
10
2′
8
12′
1
91 10
10,8
10′ , 8′
10,8
10′ , 12′
10,8
2′ , 8′
10,8
2′ , 12′
From Two Levels to One
Dual-Input BP
Input:
1
2
3
4
Too Many Monomials
+
Thank You!


similar documents