# New Advances in Garbling Circuits

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!

## Recently Viewed Presentations

• Context Clues: You be the Detective "Time Is Now" Context Clues - What Are They? Context clues are bits of information from the text that, when combined with prior knowledge, allow you to decide the meaning of unknown words in...
• WHMIS and HHPS Safety. Key Question. Physical and Chemical Properties ... Paints. Lubricants. Question: How do we know when a product is safe to use? Answer: Product Safety Symbols! Household Product Symbols. Workplace (Industrial) Product Symbols. HHPS Symbols. HHPS symbols...
• The work of the committee led to the writing of an ASA Member Initiative grant proposal (in 2014) in order to fund a face-to-face meeting to work on a new report. The committee has been working consistently on updating the...
• Other exchanges: AMEX, regional exchanges The Over-the-counter market (OTC) OTC has no central, physical location; linked by a mass telecommunication network. A part of the OTC market is made up of stocks traded on NASDAQ. On the secondary market, investors...
• Tim Hay, NASPO ValuePoint Cooperative Development Coordinator . [email protected] (503) 428-5705 * NASPO ValuePoint Point of Contact for these Master Agreements. QUESTIONS. California Contract Administrator. ... MuĂ±oz, [email protected] ...
• Times New Roman Arial Monotype Sorts colorbxb.ppt Spin-Offs Reasons for Spin-Offs Reasons for Spin-Offs (KS): Reduction of information asymmetry. Krishnaswami-Subramaniam (1999) (KS) Reasons for Spin-Offs (KS): Reduction of information asymmetry.
• Preparation for XRD - Crushing sediments into powder Precise grain size analysis results - Ternary Grain Size Chart Includes all sediment samples. SEDIMENT PROPERTIES - LOI & Grain Size Results CURRENT CONDITIONS - Water Measurements Wet & dry sediment bulk...
• Wouldn't it be wonderful if Christ really did come and his children really were ready for him? Wouldn't it be terrific if evil was finally conquered, once and for all, and the Savior of the world came down in the...