Secure Two-Party Computation Techniques Explained

On the Security of the Free-XOR Technique Ranjit Kumaresan Joint work with Seung Geol Choi, Jonathan Katz, and Hong-Sheng Zhou (UMD)

Research in Secure Two-party Computation (2PC) Generic protocols [Yao86, GMW87] Tailored protocols for specific applications [FNP04,HL08,KO97, ] Fairplay [MNPS04]: Implemented generic protocols Hope for practicality

Research in Secure Two-party Computation (2PC) Active research improving concrete efficiency of generic protocols Garbled circuit approach [PSSW09,HEKM11,KM11,LP07,LP11, ] GMW approach [NNOB11, CHKMR12,...] Moving secure computation from theory to practice

Talk Outline Background on Yao GC & the Free-XOR technique [KS08] Description in the random oracle (RO) model Replacing RO with correlation robust hash functions? Sufficient assumptions on the hash function Why correlation robust hash functions are not enough New notion: Circular correlation robust hash functions Security of the Free-XOR technique Conclusions

Yao Garbled Circuit (GC) [Yao86] Generic secure computation protocol Constant round solution Mostly symmetric-key operations Popular choice for efficient 2PC

Yao Garbled Circuit u v XOR u v w u v AND u v v u v u Credit: V. Kolesnikov

Yao Garbled Circuit y0 H(w0,x0,g ) y0 H(w0,x1,g ) y1 H(w1,x0,g ) y1 H(w1,x1,g ) y0 g,g : gate indices H: hash function y1 XOR x0 w0 x1 w1 H(u0,v0,g) w0 H(u0,v1,g) w0 H(u1,v0,g) w0 H(u1,v1,g) w1 AND u0 v0 u1 v1

GC Based Semi-Honest 2PC [Yao86] GC . Alice input keys Bob keys input bits OT Bob input keys Evaluate GC using received input keys GC .

Efficiency Improvements to Yao GC Garbled row reduction [NPS99,PSSW09] Just 3 entries per garbled table Point-and-permute [MNPS04] Decrypt only one entry Free-XOR technique [KS08] No garbled table for XOR gates

Free-XOR Technique [KS08] Idea: XOR gates evaluated for free No cryptographic operations or communication (like [Kol05,GMW87]) GC based 2PC in the semi-honest setting Gains in practice? 40% improvement for typical circuits 300% improvement for universal circuits Impact All recent implementations use Free-XOR technique [PSSW09, SS11, ] Efforts to minimize #non-XOR gates in circuit [KS08, KSS09, PSSW09]

Free-XOR Technique [KS08] y0 H(w0,x0,g ) y0 H(w0,x1,g ) y1 H(w1,x0,g ) y1 H(w1,x1,g ) y0 y1 XOR x0 w0 x1 w1 H(u0,v0,g) w0 H(u0,v1,g) w0 H(u1,v0,g) w0 H(u1,v1,g) w1 AND u0 v0 u1 v1

Free-XOR Technique [KS08] y0 = w0 x0 H(w0,x0,g ) y0 H(w0,x1,g ) y1 H(w1,x0,g ) y1 H(w1,x1,g ) y0 y1 = y0 R R : hidden global parameter XOR x0 w0 w1 = w0 R x1 = x0 R H(u0,v0,g) w0 H(u0,v1,g) w0 H(u1,v0,g) w0 H(u1,v1,g) w1 AND u0 v0 v1 = v0 R u1 = u0 R

Free-XOR Technique [KS08] y H(w0,x0,g ) y0 H(w0,x1,g ) y1 H(w1,x0,g ) y1 H(w1,x1,g ) y0 Set y = w x R : hidden global parameter XOR x w Use H(u,v,g) to recover w H(u0,v0,g) w0 H(u0,v1,g) w0 H(u1,v0,g) w0 H(u1,v1,g) w1 AND u v

Proof in the RO Model [KS08] Corrupt Alice: Trivial Corrupt Bob: Sim creates a fake garbled circuit whose output is always correct Intuitively, security reduces to proving R is completely hidden Indistinguishability proved by induction on topological ordering of gates Real table Simulated table By induction, known input keys: u, v Only w is recovered Except with negl. prob., all other values are hidden H(u,v,g) w H(u,v R,g) w H(u R,v,g) w H(u R,v R,g) (w R) H(u,v,g) w random1 random2 random3

Proof in the Standard Model? RO is not programmed Can RO be replaced by a suitable hash function? [KS08]: a variant of correlation robust hash functions (CorRHF) works Repeated wherever Free-XOR is used [PSSW09,SS11,AHI11,NO09, ] Our contributions Natural variant of CorRHF is NOT sufficient Specify variant of CorRHF that is sufficient

Proof in the Standard Model? Natural variant of CorRHF is NOT sufficient Main issue is circularity [BK03,BRS03, HK07, ] H(u R,v R,g) (w R) CorRHF does not capture circularity H(u,v,g) w H(u,v R,g) w H(u R,v,g) w H(u R,v R,g) (w R) Specify variant of CorRHF that is sufficient Circular Correlation Robust Hash Functions Captures circularity Security proof for the Free-XOR technique

Why is this important? Implementors happy with RO In theory, RO methodology is inherently flawed [CGH04] Want precise formulation of concrete properties required by RO Natural variant of CorRHF used in other contexts [AHI11,NO09] CorRHF is sufficient for Free-XOR technique claimed in several works [PSSW09,SS11, AHI11, ] Assumptions required for Free-XOR tech. in Yao GC? Free-XOR in [GMW87, Kol05] with no other assumptions

Correlation Robust Hash Functions [IKNP03] Proposed by [IKNP03] for removing RO in OT extension Definition: (CorRHF) H is CorRHF if for randomly chosen u1, , up, the following two distributions are comp. indistinguishable (u1, , up, H(u1 R), , H(up R)) where R is chosen uniformly (u1, , up, w1, , wp) where each wi is chosen uniformly (Arithmetic variant) realized under PDH assumption [AHI11] [KS08]: Variant can replace RO in Free-XOR Use of hidden off-set in both [KS08] and [IKNP03]

Natural Variant of CorRHF Definition: (weak 2-CorRHF) H is weakly 2-CorRHF if for given u1, , up, v1, , vp, the following two distributions are comp. indistinguishable . H(u1 R,v1,1), H(u1,v1 R,1), H(u1 R,v1 R,1) . . . ` H(up R,vp,p), H(up,vp R,p), H(up R,vp R,p) where R is chosen uniformly (w1, , w3p) where each wi is chosen uniformly

Our Working Definition of 2-CorRHF Oracle based CorR(u,v,g): output H(u,v R,g), H(u R,v,g), H(u R,v R,g) Rand(u,v,g): if input was queried before then output answer given previously, else output a uniformly chosen string Definition: (2-CorRHF) H is 2-CorRHF if every non-uniform PPT adversary A with oracle access to O (either CorR or Rand) cannot tell whether O is CorR or Rand except with negligible advantage Stronger than previous definition Oracle queries can be adaptive

2-CorRHF and Free-XOR technique Real table Simulated table H(u,v,g) w H(u,v R,g) w H(u R,v,g) w H(u R,v R,g) (w R) H(u,v,g) w random1 random2 random3 Reduction adversary B for 2-CorRHF Given O (either CorR or Rand) How to create garbled table? Choose random u,v,w Query O(u,v,g) to get h1, h2, h3 First 3 entries can be set How to obtain fourth entry using h3? Unclear how to complete reduction Reduction Table H(u,v,g) w h1 w h2 w ?

Counterexample Rule out fully black-box reduction using two oracles H and Break H is 2-CorRHF even if A has oracle access to H and Break Free-XOR technique is insecure when A has access to H and Break Break(u,v,g,z1,z2,z3) Output r when z1 = H(u,v r,g) z2 = H(u r,v,g) z3 = H(u r,v r,g) r Else output nothing H(u,v,g) Random function

H is 2-CorRHF against AH, Break O = Rand: uniform, independent of A s view O = CorR: uniform, independent of A s view unless A queries O(u,v,g) & O(u ,v ,g) with u u = R or v v = R, or H(u ,v ,g) with u u = R or v v = R, or Break(u,v,g,z1,z2,z3) with z3 H(u R,v R,g) = R Happens with negligible prob. Break(u,v,g,z1,z2,z3) Output r when z1 = H(u,v r,g) z2 = H(u r,v,g) z3 = H(u r,v r,g) r Else output nothing H(u,v,g) Random function

Insecurity of Free-XOR Tech.: AH, Break Attack: A acting as Bob recovers R Recover w from gate g using H(u,v,g) z1 = c1 w z2 = c2 w z3 = c3 w Query Break(u,v,g,z1,z2,z3) to get R AND gate g H(u,v,g) w H(u,v R,g) w H(u R,v,g) w H(u R,v R,g) (w R) c1 c2 c3 Break(u,v,g,z1,z2,z3) Output r when z1 = H(u,v r,g) z2 = H(u r,v,g) z3 = H(u r,v r,g) r Else output nothing H(u,v,g) Random function

Capturing Circularity: Circular 2-CorRHF Recall indistinguishable oracles in 2-CorRHF CorR(u,v,g): output H(u,v R,g), H(u R,v,g), H(u R,v R,g) Rand(u,v,g): if input was queried before then output answer given previously, else output uniformly chosen bR = 0 when b=0 bR = R when b=1 Oracles for Circular 2-CorRHF CircR(u,v,g,b1,b2,b3): output H(u b1R, v b2R, g) b3R Rand(u,v,g,b1,b2,b3): same as before

Capturing Circularity: Circular 2-CorRHF Recall indistinguishable oracles in 2-CorRHF CorR(u,v,g): output H(u,v R,g), H(u R,v,g), H(u R,v R,g) Rand(u,v,g): if input was queried before then output answer given previously, else output uniformly chosen Allowing b3 = 1 captures circularity Oracles for Circular 2-CorRHF CircR(u,v,g,b1,b2,b3): output H(u b1R, v b2R, g) b3R Rand(u,v,g,b1,b2,b3): same as before

Circular 2-CorRHF Oracles for Circular 2-CorRHF CircR(u,v,g,b1,b2,b3): output H(u b1R, v b2R, g) b3R Rand(u,v,g,b1,b2,b3): same as before Indistinguishability conditioned on restricted queries to CircR No queries of the form (u,v,g,0,0,b3) No queries on both (u,v,g,b1,b2,0) and (u,v,g,b1,b2,1) Definition: (Circular 2-CorRHF) H is circular 2-CorRHF if every non-uniform PPT adversary A making legal queries to oracle O cannot tell whether O is CircR or Rand except with negligible advantage

Proof of Security for the Free-XOR Tech. Corrupt Alice: Trivial Corrupt Bob: Sim creates a fake garbled circuit . . . y = w x Choose random key for all wires except output wires of XOR gates XOR chosen keys for input wires to get key for output wire of XOR gate Populate unknown values in non- XOR gate table with random values Set output garbled table to give correct output z XOR Simulated table w x H(u,v,g) w random1 random2 random3 AND u v

Reduction to Circular 2-CorRHF Reduction adversary B for Circular 2-CorRHF B given access to O (either CircR or Rand) & real inputs for both parties . . . y = w x Choose random key for all wires except output wires of XOR gates XOR chosen keys for input wires to get key for output wire of XOR gate Populate unknown values in non- XOR gate table using O Set output garbled table to give correct output z XOR Reduction Table w x H(u,v,g) w O(u,v,g,0,1,0) w O(u,v,g,1,0,0) w O(u,v,g,1,1,1) w AND u v

Circular 2-CorRHF & Free-XOR technique Real table Simulated table H(u,v,g) w H(u,v R,g) w H(u R,v,g) w H(u R,v R,g) (w R) H(u,v,g) w random1 random2 random3 Reduction Table H(u,v,g) w O(u,v,g,0,1,0) w O(u,v,g,1,0,0) w O(u,v,g,1,1,1) w O = CircR O = Rand Recall CircR(u,v,g,b1,b2,b3): output H(u b1R, v b2R, g) b3R

Conclusions & Open Questions Free-XOR technique extremely influential Used in all Yao GC implementations Secure in the random oracle model Natural variant of 2-CorRHF is not sufficient Circularity Stronger notion of 2-CorRHF: Circular 2-CorRHF Security proof for the Free-XOR technique Free gate evaluation under OWF? Realize Circular 2-CorRHF from standard crypto assumptions?

Thank You!