Slides

Report
Succinct Functional Encryption:
d
Reusable Garbled Circuits and Beyond
Yael Kalai
Microsoft Research
Joint work with:
Shafi Goldwasser
Raluca Ada Popa
Vinod Vaikuntanathan
Nickolai Zeldovich
* Thanks to Raluca and Vinod for the slides.
MIT
MIT
U Toronto
MIT
Example: Spam Filters
Sender
Receiver
Spam filter
[]
FHE.Eval of
filter
E[spam?]
[]
FHE is not enough!
Need to decrypt computation result but
nothing else!
Desired: Functional Encryption (FE)
[Boneh-Sahai-Waters11, O’Neill11]
Allows evaluator to decrypt computation result
Client
 1 , . . , [ ]

Evaluator
compute   , … ,  
Syntax:

,  ← FE. Setup 1
 ← FE. Enc , 
Can release only one
 ← FE. KeyGen , 
function key

f  ← FE. Dec  , 


[Agrawal-GorbunovVaikuntanathan-Wee12]
Outline
• Example: Spam filters
• Problem we solve: Functional Encryption (under
LWE assumption)
• Prior work
• Main Application: Reusable Garbled Circuits
• Application 2: FHE for Turing machines
• Application 3: Publicly Verifiable and Secret
Delegation
• Our constructions
Prior Work
 Functional encryption for inner product functions
[Katz-Sahai-Waters’08, Shen-Shi-Waters’09]
 Public-index functional encryption
(also known as ABE or predicate encryption)
[Sahai-Waters’05, Goyal-Pandey-Sahai-Waters’06, Bethencourt-Sahai-Waters’07, Goyal-JainPandey-Sahai’08, Lewko-Okamoto-Sahai-Takashima-Waters’10, Waters’11, LewkoWaters’12, Waters’12, Sahai-Waters’12, Gorbunov-Vaikuntanathan-Wee’13,…]
 [Gorbunov-Vaikuntanathan-Wee’12]: Functional encryption for
general functions, where |  | grows with circuit size
(e.g. size of email encryption depends on spam filter program size)
Open question:
Is there a FE scheme for general functions
with
ciphertext size << circuit size?
succinct
Our contribution:
Succinct functional encryption
Theorem. A FE scheme with succinct ciphertexts for general
functions can be constructed from
1. FHE scheme
2. public-index functional encryption scheme
Corollary. Under the sub-exp. LWE assumption, for any depth d,
there is a FE scheme with succinct ciphertexts (whose size grows
with d) for general functions computable by circuits of depth d.
Main Application:
Reusable Garbled Circuits
Yao garbled circuits [Yao82]
–
–
–
–
–
–
–
–
Secure two-party computation [Yao86],
(Constant round) multi-party computation [BMR90],
Parallel cryptography [AIK05],
One-time programs [GKR08],
Key-dependent message (KDM) security [BHHI09, A11],
Outsourcing computation [GGP10],
Circuit-private homomorphic encryption [GHV10],
and many others
Yao Garbled Circuits
[Yao 82]
Garbled Circuit GC
Boolean Circuit C
01010010
01110110
+
Garble(C)
x
x
01010011
11111101
+
Input 
=
0
1
01010010
11100010
11010010
01010011
Garble(x)
1
0
Garbled Input 
L1,0 L2,0 L3,0 L4,0
L1,1 L2,1 L3,1 L4,1
Yao Garbled Circuits (Cont.)
 Correctness: Given GC and
, can compute C(x).
 Security (Input & Circuit privacy)
Given C(x) and 1|C|, can
simulate (GC, ).
 Efficiency:
|GC| = p(|C|) and || = p(|x|)
Garbled Circuit GC
01010010
01110110
01010010
11100010
11010010
01010011
01010011
11111101
Garbled Input 
L1,0 L2,0 L3,0 L4,0
L1,1 L2,1 L3,1 L4,1
Yao Garbled Circuits (Cont.)
Garbled Circuit GC
01010010
01110110
Theorem: [Yao86]
If one-way functions exist,
any polynomial-size circuit
family can be garbled.
01010010
11100010
11010010
01010011
01010011
11111101
Garbled Input 
L1,0 L2,0 L3,0 L4,0
L1,1 L2,1 L3,1 L4,1
Drawback: One-time
Garbled Circuit GC
01010010
01110110
insecure to release two
encodings  and ′
01010010
11100010
11010010
01010011
01010011
11111101
 = 
′ = 
L1,0 L2,0
L1,1 L2,1
L3,0 L4,0
L3,1 L4,1


No
Caninput
compute
or circuit
C(x) for
privacy
unintended
guarantees!
inputs x!
01010010
11010010
01010010
01010011
Main Application:
Reusable Garbling
Theorem:
Under the sub-exp. LWE, there is a reusable circuit
garbling scheme for poly size circuits such that:
–  =poly(,|C|)
–  =poly(, ||, ) where  is the depth of 
(: security parameter)
Application 2: FHE for Turing machines
Evaluator
[input]
Program
Client
[result]
circuit size ≥ worst-case
running time of program
Decrypt only the runtime of the instance, to
avoid worst-case!
Application 3:
Publicly-verifiable delegation with secrecy

[Gennaro-Gentry-Parno’10]: Yao + FHE
verifiable delegation

[Parno-Raikova-Vaikuntanathan’12]: public-index FE
secret publicly-verifiable delegation
succinct FE
secret privately-
non-
publicly-verifiable delegation with secrecy
Outline
LWE
public-index FE
+
FHE
+ Yao garbling
1
succinct functional encryption
2
reusable garbled
circuits
&
implication to
obfuscation
Not
today
FHE with inputspecific efficiency
Not
today
publicly-verifiable
delegation with
secrecy
Construction of FE
Public-Index Functional Encryption
(also known as ABE or predicate encryption)
 ← Enc , , 
Dec  ,  =
 ,    = 1
leaks input to
the computation
⊥ ,    = 0
Variant:  ← Enc , , 0 , 1
Dec  ,  =
0 ,    = 1
1 ,    = 0
[Borgunov-Vaikuntanathan-Wee13]: Public-index functional encryption for
any (a priori fixed) depth d circuit, based on sub-exp. LWE assumption.
Intuition
 ← FHE. Enc 
 ← 
() ← FHE. Eval(, )
Not f()!
IDEA: Start with FHE
IDEA: Use (one-time) Yao garbled for decryption
Intuition
FE.Enc of input :
1.
 ← FHE. Enc 
2. Generate garbled circuit Γ and labels 0 , 1
Output , Γ
FE.KeyGen for circuit f:
 ← 
FE.Dec( , ) should obtain ():
1.  = () ← FHE. Eval(, )
2. Obtain labels {

} for ()
3. Compute Gb. Eval Γ, 

How??
and get ()

for Dec
We need..
if FHE. Evali (, ) = 0, get label 0 , else gets 1
public predicate
keep one secret
public input
IDEA: The variant of public-index FE provides exactly this!

 ← PI. Enc , 0 , 1 )

 ← PI. KeyGen 

PI. Dec  ,  =
0 ,    = 0
1 ,    = 1
Intuition
FE.Enc of input :
1.
 ← FHE. Enc 
2. Generate garbled circuit Γ and labels 0 , 1
3. c ← PI. Enc , 0 , 1 )

for Dec
Output , Γ, ct i
FE.KeyGen for circuit f:
 ← PI. KeyGen  , where  = FHE. Evali (, ⋅)
FE.Dec( , ) should obtain ():
1.  = () ← FHE. Eval(, )
2. Obtain labels {

} for ()
3. Compute Gb. Eval Γ, 

and get ()
Outline
public-index FE
+
FHE
+ Yao garbling
succinct functional encryption
2
reusable garbled
circuits
&
implication to
obfuscation
FHE with inputspecific efficiency
publicly-verifiable
delegation with
secrecy
Intuition
Garble(C):
Γ ← . ()
Leaks C!
Garble(x):
 ← . ()
IDEA: leverage secrecy of input to hide circuit
Intuition
Garble(C):
Γ ← . (  )
Garble(x):
 ← . (, )
Intuition
Garble(C):
Γ ← . ( () )
Garble(x):
 ← . (, )
 on input  and :
- Decrypt E to obtain C
- Run ()
Correctness?
Security?
Reusability?
Summary
LWE
public-index FE
+
FHE
+ Yao garbling
1
succinct functional encryption
2
reusable garbled
circuits
&
implication to
obfuscation
Not
today
FHE with inputspecific efficiency
Not
today
publicly-verifiable
delegation with
secrecy
Thank you!
LWE
public-index FE
+
FHE
+
Yao garbling
1
succinct functional encryption
2
reusable garbled
circuits &
implication to
obfuscation
FHE with inputspecific efficiency
publicly-verifiable
delegation with secrecy

похожие документы