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