Garbled Circuits: A Tutorial Benny Applebaum Tel Aviv University Cryptography Boot Camp Simons Institute, 2015 Plan Definitions and Properties Feasibility Results Recent Efficiency Improvements Skip practical advances Applications ? Garbled Circuit Powerful Cryptographic Tool with many Applications Constant-round secure computation [Yao82,BMR90,...] Private Simultaneous Messages protocols [FKN94,] Computing on encrypted data [RAD78,SYY99,] Parallel cryptography [AIK05,] One-time programs [GKR08,] KDM-secure encryption [BHHI10,...]

Verifiable computation [GGP10,] Functional encryption [SS10,] Bootstrapping obfuscators [App13] Yao, 80s Garbled Circuit Encoding/Encryption of a function What is a Garbled Circuit? [Yao82] [FKN94] [IK00-02] [AIK04] [BHR12] Yao, 80s Secure 2-party computation protocol Private Simultaneous Messages protocols Randomizing Polynomials representation Randomized Encoding of functions Garbling Scheme

Randomized Encoding of Functions [IK00, AIK04] Input X f Output Y Decoder Random g Simulator Encoding(Y) Input X g(X;R) is a Randomized Encoding of f(X). Correctness: (X,R), Decoder(g(X;R))=f(X) Privacy: X

Sim(f(X)) (g(X;R)) flavors: perfect, statistical, computational (Silly) Example I Input X f Y Decoder Random Input X f Simulator Y (Less Silly) Example II X, e, N RSA

Xe (mod N) Decoder Random X, e, N RSA Simulator Xe +R*N Usefulness Input X f Output Y Complex Decoder Random Input X

g Simulator Encoding(Y) Simple Hope: g can be simpler than f (meaning of simpler determined by application) g can be used as a substitute for f Example: Non-Interactive Delegation x g(x;r) f(x) Example: Non-Interactive Delegation Compare to FHE

x x f(x) x Useful Properties Composition: Enc(Enc(f)) is an encoding of f. Concatenation: (Enc(f1), Enc(f2)) is an encoding of f=(f1,f2). Substitution: Enc(f) h encodes f h Z X R h X Z

h f Enc(f) Useful Properties Composition: Enc(Enc(f)) is an encoding of f. Concatenation: (Enc(f1), Enc(f2)) is an encoding of f=(f1,f2). Substitution: Enc(f) h encodes f h X Y e R h Xe

Y h f Enc(f) Y mod N Y+RN Encoding a Function Family (public) circuit C Garbled circuit C Offline Random Garbled

Input X Input X Online Enc(C)(X;R) reveals C(x) and nothing else C is independent of X Typically, X is independent of C Encoding a Function Family (public) circuit C Garbled circuit C Offline Random Garbled Input X

Input X Online Enc(C)(X;R) reveals C(x) and nothing else C is independent of X Typically, X is independent of C Notions of simplicity: Affinity (public) circuit C Garbled circuit C Offline Random Input X Garbled Input X

The mapping XX is affine in X Variant: low degree in the randomness as well Online Notions of simplicity: Decomposability (public) C C Offline Random Input X X1 Xn

Online Xi depends only on Xi Variant: low locality in the randomness as well Decomposable Affine REs (DARE) (public) C C Offline x1 a1 + b1 xn an + bn Online Random Input X Feasibility Results

The [AIK11] framework Goal I: perfect DARE for formulas (public) C C Offline x1 a1 + b1 xn an + bn Online Random Input X Keys may be long DARE for Simple Functions x1+x2 Encoded by x1+r | x2-r

rRF x1x2 Encoded by x1+r1 | x2+r2 | ?r2x1+r1r2+r1x2 Enc by x1+r1 | x2+r2 | r2x1+r1r2+r3 | r1x2-r3 x1 * 1 r2 + r1 r1r2+r3 x2 * 1 r1

+ r2 -r3 DARE for Simple Functions x1x2+x3 Affinization Gadget Encoded by x1 * 1 r2 + r1 r1r2+r3

x2 * 1 r1 + r2 r4 x3 * -1 + -r3-r4 Encoding the Circuit Layer-by-Layer y1 y2 y3 y4 C1

Cd x3

x2 y2 y3 y4 Trivial encoding for output level Ci-1 x1 y1

x4 Encoding the Circuit Layer-by-Layer DARE for C1 Ci-1 C1 Ci-1 y1i-1 y2i-1 y3i-1

y4i-1 x + x x y1i y2i y3i y4i Ci+1 y1i-1 a1 +b

1 Offline Garbling the Circuit Layer-by-Layer Substitution C1

Ci-1 y1i-1 y2i-1 y3i-1 y4i-1 x + x x y1i

y2i y3i y4i Ci+1 y1iy2i a1 +b 1 Offline

Garbling the Circuit Layer-by-Layer Affinization C1 Ci-1 y1i-1 y2i-1 y3i-1

y4i-1 x + x x y1i y2i y3i y4i Ci+1 y1i c1 +d

1 y2i c2 Offline +d 2 Perfect DARE for Formulas

Key-length = exp(circuit-depth) Perfect DARE for NC1 circuits [IK00-02] New proof of [IK02] Works for arithmetic NC1 circuits over finite fields Open: Perfect DARE for Circuits ? Coming-up: Computational DARE for circuits Main idea: Key-shrinking Gadget ! Garbling General Circuits AGC for C1 Ci-1 C1 Ci-1

y1i-1 y2i-1 y3i-1 y4i-1 x + x x y1i y2i y3i y4i

Ci+1 y1i-1 a1 +b 1 Offline Garbling the Circuit Layer-by-Layer Substitution

C1 Ci-1 y1i-1 y2i-1 y3i-1 y4i-1 x +

x x y1i y2i y3i y4i Ci+1 y1iy2i a1 +b 1 Offline

Garbling the Circuit Layer-by-Layer Affinization C1

Ci-1 y1i-1 y2i-1 y3i-1 y4i-1 x + x x y1i y2i y3i y4i

Ci+1 y1i c1 +d 1 y2i c2 Offline +d 2

Garbling the Circuit Layer-by-Layer Key shrinking C1 Ci-1 y1i-1 y2i-1

y3i-1 y4i-1 x + x x y1i y2i y3i y4i Ci+1 y1i a1

+b 1 y2i a2 Offline +b 2

Key-Shrinking Gadget yc+ d decoder simulator ya+b W Encode long affine func by short affine func + offline part a,b,W can depend on c,d and randomness Implementing Key-Shrinking (Boolean case) yc+ d decoder simulator ya+b

If y=0 encoding should release d If y=1 encoding should release c+d W Implementing Key-Shrinking (Boolean case) Eb(d) yc+ d decoder simulator ya+b If y=0 encoding should release d If y=1 encoding should release c+d Ea+b(c+d) Corollary: DARE for Boolean Circuits (public)

Boolean Circuit C Garbled circuit C Offline x1 a1 + b1 xn an + bn Online Random Input X DARE for Boolean Circuits from OWFs [Yao 80s] Online efficient: complexity n* independent of |C| Computational privacy New view of Yaos construction Corollary: DARE for Boolean Circuits (public) Boolean Circuit C

Garbled circuit C Offline x1 a1 + b1 xn an + bn Online Random Input X DARE for Boolean Circuits from OWFs [Yao 80s] Low-degree + low locality from Log-space OWFs DARE for RAM from OWFs [AIK05] [LO13, GHL+14, GLOS14,GLO15] Q: DARE for Arithmetic Circuits? Arithmetic Circuit C

Garbled circuit C Offline x1 a1 + b1 xn an + bn Online Random XFn Gates perform addition or multiplication Operations over a large domain (e.g., field F) Motivated by efficiency & arithmetic feasibility Need Arithmetic Key-Shrinking Implementing Key-Shrinking (Arithmetic case)

Eb(d) yc+ d decoder simulator ya+b Ea+b(c+d) E2a+b(2c+d) E3a+b(3c+d) Implementing Key-Shrinking (Arithmetic case) Eb(d) yc+ d decoder simulator

ya+b Ea(c) Essentially need: encryption with homomorphism s.t y*Ea(c)+Eb(d) = Ey*a+b(y*c+d) Approximately achieved over the integers using LWE DARE for Circuits over Integers Garbled circuit C Arithmetic Circuit C Random XFn x1 a1 + b1 xn an + bn [AIK11] DARE for Arithmetic Circuits from LWE Online efficient, works over exp-large integers, Decoder is Boolean Q: DARE for Circuits over general finite field? [AAB15] Impossible if Decoder is also arithmetic circuit

Summary (so far) C Garbled circuit C Offline x1 a1 + b1 xn an + bn Online Random Input X General approach for garbled circuits Alternative to Yaos garbled tables approach Independent of the domain size New modular, simplified proof for Boolean case Efficiency Improvements Efficiency Improvements

(public) Boolean circuit C Garbled circuit C Offline Random Input X Garbled Input X Online Q1: Shorten onlineReveal part C(x) X? and nothing else Q2: Reuse offline part C ? Q3: Optimize offline efficiency ? Improving Online Rate

Online x Encr x Online rate = |x|/|x| Yaos construction: rate = Q: What is the best achievable rate? Improving Online Rate Online x Encr x Thm [AIKW13]: Assuming DDH, LWE, or RSA, there is a Affine RE with online rate=1.

More precisely: |x|=|x|+ Quasi-linear online computational complexity Decomposability is impossible Improving Online Rate Online x Encr x Thm [AIKW13]: Assuming DDH, LWE, or RSA, there is a Affine RE with online rate=1. Outline: Key-Homomorphism Set Encryption Thm Gadget: Set Encryption Alice Bob

Mn M4 M3 M2 M1 EncK Cnn C4 M subset T{1,,n} 1 0 0 1 0 Key length = Independent of the number of plaintexts KT C3

C22 C1 M Gadget Compressing Keys Simulator C(x) Garbled circuit C Boolean circuit C Yao Input x Garbled circuit C Gadget s Subset KT Decoder

Implementing the Gadget Tool: symmetric encryption with homomorphism for keys/messages EK1(M1)+EK2(M2)=EK1+K2(M1+M2) Can be implemented under DDH Variants under LWE, RSA From Homomorphism to Set Encryption Alice C1 C2 M1 C1 Mn MM M2 M1 4 2 M3 Ci=Enc(Ki,Mi)

M3 1 0 C2 M3 C4 KT 1 C1+C3 M1 C3 M4 0 C 3 C4 We get Online Rate = 1

C C Offline X Online Random X |X|=n+ Online Rate < 1 ? C C Offline Random

X X |X|

|X|

Online |X|

Online part grows with n,m, and circuit-depth Succinct Functional Encryption Boolean circuit C Garbled circuit C Offline Random Input X Garbled Input X Online Reusable Randomized Encoding Thm. [Goldwasser-Kalai-Popa-Vaikuntanathan-Zeldovich13] Reusable RE under sub-exp LWE Outline: Homomorphism Attribute Encryption Thm

Gadget: Attribute Encryption [SW05, GPSW06] Reusable RE for the function: (T,s) AE(T,s)= (T,) if predicate P(T) holds else Alice Bob Reusable Offline(P) Reusable Offline(P) T

s T s if P(T) holds FHE+ Attribute Enc Reusable-GC FHE+ Attribute Enc Reusable-GC Idea: Garble F(x) by Conditional F(x) FHE-decryption FHE(F(x)) FHE(x) Decrypt If CT=FHE(F(x)) FHE+ Attribute Enc Reusable-GC Reusable

Offline(F) FHE-decryption circuit One-time Garbled Circuit Yao One-time Garbled circuit Gadget Reveal Ki,b if EvalF(T)i=b FHE(x) FHE(x) T=FHE(x) FHE+ Attribute Enc Reusable-GC Dec(FHE(F(x)))= F(x) Reusable

Offline(F) FHE-decryption circuit One-time Garbled Circuit Yao One-time Garbled circuit Gadget Reveal Ki,b if FHE(F(x))i=b FHE(x) FHE(x) T=FHE(x) Decoder Implementing Attribute Encryption [GorbunovVaikuntanathanWee13]

Tool: Public-Key Encryption with Re-Keying For every public-keys A,B,C, key TA,B C TA,B C: EA(S), EB(S) EC(S) Can be implemented under LWE Implementing Attribute Encryption [GorbunovVaikuntanathanWee13] Reveal s iff output(T)=1 1 0 0 Public input T Secret input s 0

1 0 1 s Implementing Attribute Encryption [GorbunovVaikuntanathanWee13] Reveal s iff output(T)=1 s 1 0 0 Public input T Secret input s 0

1 0 1 Succinct RE [GKPVZ13b,GHRW14b,BGLPT15,KLW15,CHJV15] Complexity so far [Yao]: Time(Enc(C)) Time(C) [GKPVZ13]: AmortizeTime(Enc(C)) independent of Time(C) poly(input, output, , depth(C)) Q: Time(Enc(C)) independent of Time(C)? Assume that C has short description (Turing Machine). C C Random X X

Succinct RE Thm. [BGLPT15,CHJV15] Succinct RE under iO+OWFs Time(Enc(C))=poly(input, output, , space(C)) Previously, [GKPVZ13b] under stronger assumption Follow-up [KLW15] eliminates dependency in space Allows to transform iO for circuits to iO for TMs Turing Machine C C Random Input X Garbled Input X Proof Idea (over-simplified) [BGLPT15] View Turing Machine as a uniform circuit Y CT

Ci i Program P C1

X Proof Idea (over-simplified) [BGLPT15] Encode the circuit via Yaos construction Fact 1: encoding is local Y CT Enc(C1) X

Rand Enc(Ci)

Rand C1 Rand X Enc(CT) Ci i

Program P Rand Proof Idea (over-simplified) [BGLPT15] Encode the circuit via Yaos construction Fact 1: encoding is local Enc(CT) Rand X

Enc(C1) X Enc(Ci) i Rand

Program P Proof Idea (over-simplified) [BGLPT15] Encode the circuit via Yaos construction Fact 1: encoding is local Enc(CT) Rand X Enc(C1)

X Enc(Ci) i PRFK Program P K

Proof Idea (over-simplified) [BGLPT15] Security: Yaos Simulation is local Puncturing Encoding Program P K Program Obf(P) i X

Rand X Take Home Message Better Homomorphism Better encodings Rerandomizable GCs [GHV10] Free XOR gates [App13] ABE for Arithmetic circuit [BNS13] Simultaneous Compression of online/offline [GGHV13] Summary Construction Efficiency Assumption DARE for formulas

Poly(C) NONE DARE for circuits/RAM Online efficient OWFs DARE for circuits NC0 OWFs in LOGSPACE Affine-RE for circuits Online succinct DDH,LWE, RSA

DARE for Arithmetic Circuit Online efficient LWE Reusable DARE for circuits Amortize-Time =poly(n,m,,depth) Sub-exp. hard LWE DARE for TMs Time=poly(n,m,) iO+OWFs Relaxing Assumptions ? Proving necessity? Stronger notions of security?

Robust grass Fragile orchid Applications The Archetypical Story Bob Adversary REs? Functionality Alice Encoding the Functionality Bob

Adversary Examples: Secure Computation Delegation Program Checking Functionality Verifiable Computation Bootstrapping Obfuscation Alice Encoding the Honest Parties Bob Adversary Examples: Parallel Crypto ECC with fast decoder Functionality

Alice Encoding the Adversary Bob Adversary Examples: Key-Dependent Message Amplification [BHHI10, App11] Functionality Alice F-KDM Security sk pk C=E (pk, f(sk)) m

fF D(sk,C) F-KDM Adversary From G-KDM to F-KDM sk pk C=E (pk, m) m D(sk,C) G encodes F if: g(x;r) encodes f(x), gr(x) is in G for every fixed r Assume E is G-KDM secure sk C=E(pk,m)= E (pk, Sim(m)) pk

m D(sk,C) G encodes f if: g(x;r) encodes f(x), gr(x) is in G for every fixed r Assume E is G-KDM secure sk C=E(pk,m)= E (pk, Sim(m)) pk m m'=D(sk,C) m=Decode(m) G encodes f if: g(x;r) encodes f(x), gr(x) is in G for every fixed r Security

E(pk,f(sk)) = E(pk, Sim(f(sk))) f-KDM for E pk E(pk, g(sk,r)) E(pk, gr(sk)) pk G-KDM for E Corollary: projections KDM fixed poly-size circuits Open Question Adaptive security: Online Input depends on offline part RO, complexity leveraging, UCE [BHR12, BHK13] Online part>output length [AIKW13] Standard model with online complexity <|C| ? (public) Boolean circuit C

Input X Garbled circuit C Garbled Input X Offline Online Thank You!