Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries Yehuda Lindell Bar-Ilan University Efficient Secure Two-Party Computation Using Symmetric Cut-and-Choose Yan Huang, Jonathan Katz, David Evans University of Maryland, University of Virginia Secure Two-Party Computation • Two parties with private inputs x and y • Compute a joint function of their inputs while preserving – Privacy – Correctness – Independence of inputs 2 Adversaries and Security • Semi-honest: follow protocol description but attempt to learn more than allowed – Highly efficient, but weak guarantee • Malicious: run any arbitrary attack strategy – Much more expensive • Covert: behave maliciously and may succeed, but will be caught with a guaranteed probability 3 Yao’s Protocol (Semi-Honest) Bob Alice Input: x Input: y Garbled (encrypted) circuit Compute f(x,y) (learn nothing else) Security for Malicious • Alice may not construct the circuit correctly • Solution – cut-and-choose 5 The Cut-and-choose Paradigm 6 The Cut-and-choose Paradigm 7 The Cut-and-choose Paradigm Final output Majority 8 The Cost • How many circuits are needed to make sure that the majority are correct? – With s circuits, probability of cheating is 2-0.311s [LP11] or 2-0.32s [sS11] – For error 2-40, need approximately 125 circuits – For error 2-80, need approximately 250 circuits • This is a very heavy price! 9 These Two Works • Aim: reduce the number of garbled circuits needed 1. Lindell: s circuits + some small additional overhead for 2-s error 2. Huang-Katz-Evans: s circuits per party in parallel for 2-s error • Cut-and-choose opens up many other problems (input consistency etc.); we focus on the main issue of number of circuits 10 Lindell’s Solution – The Main Idea • Why majority? – A malicious Alice can make most circuits correct and a few not – The incorrect circuits can compute the function if Bob’s input meets some condition; otherwise compute garbage – Bob aborts if it gets different outputs: • If Bob aborts, Alice knows that Bob’s input does not meet the condition • If Bob does not abort, Alice knows that Bob’s input meets the condition 11 Lindell’s Solution – The Main Idea • Make cheating possible only if all checked circuits are correct and all evaluated circuits are incorrect – This yields error 2-s for s circuits • How? – Alice and Bob run a small secure computation in addition – If Bob received two different outputs in two different circuits, it learns Alice’s input – In this case, Bob computes f(x,y) itself – Alice doesn’t know which case happened 12 Lindell’s Solution – The Main Idea • The secure computation – Yao’s circuit for malicious (e.g., LP11) – Number of non-XOR gates is only the number of bits in Alice’s input (very small circuit) • Input consistency and other issues are dealt with as in other works – These other parameters are not optimized in the paper – This will be discusses in the next talk; their solutions can be applied here 13 Lindell’s Solution – More Details • The garbled values on the output wires are secret (this has been used for secure delegation) • If Bob learns two garbled values on a single output wire (in different circuits), then Alice must have been cheating – This is a proof that Alice cheated • The secure computation checks if Bob has two such values and outputs Alice’s input x to Bob if yes • This circuit can be made very small, and Alice can be forced to use the same input 14 Huang-Katz-Evans Solution • Observation – One of the two parties is honest, all circuits generated by him is correct • Approach – Let each party generate half of the circuits – Suffices to ensure at least one good evaluation circuit is generated by the adversary 15 16 A party uses consistent inputs in both roles Securely combine both parties’ results to obtain the final output 17 Input Consistency – The Goal Generator s s sends wi w10 w20 w30 w40 w11 w12 w13 w14 Evaluator / OT Receiver ì q = gk ï 0 [Naor and Pinkas, SODA2001] k ¬ , sends qs q, í k ïî q1 = C / g The discrete log of C is unknown. 18 Input Consistency – The Idea Generator s w10 = g a1 w20 = g a2 w30 = g a3 w40 = g a4 w11 = C / g r1 w12 = C / g r2 w13 = C / g r3 w14 = C / g r4 Evaluator / OT Receiver ì q = gk ï 0 k ¬ q, í , sends qs k ïî q1 = C / g 19 Final output Goal: Derive the final output from both parties’ circuit evaluation results z 20 Output Revelation Verifiable Secret Sharing w10 w20 w30 w40 w50 w60 w70 w80 w11 w12 w13 w14 w15 w16 w17 w18 Generator picks a pair of secrets (s0, s1)randomly (w10 ,w20 ,w30 ,w40 ,w50 ,w60 ,w70 ,w80 ) = VSS.Share(s0 ,8,5) (w11,w12 ,w13 ,w14 ,w15 ,w16 ,w17 ,w18 ) = VSS.Share(s1,8,5) 2 with threshold: + 1 = 5. 21 Output Revelation circuit check w10 w20 w30 w40 w50 w60 w70 w80 w11 w12 w13 w14 w15 w16 w17 w18 Verify(s0 ,w ),Verify(s0 ,w ),Verify(s0 ,w ),Verify(s0 ,w ) 0 1 0 3 0 4 0 7 Verify(s1,w ), Verify(s1,w ),Verify(s1,w ),Verify(s1,w ) 1 1 1 3 1 4 1 7 sharing threshold: 5. 22 Output Revelation circuit evaluation w10 w20 w30 w40 w50 w60 w70 w80 w11 w12 w13 w14 w15 w16 w17 w18 s0 = VSS.Recover(w ,w ,w ,w ,w ,w ,w ,w ) 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 s1 = VSS.Recover(w ,w ,w ,w ,w ,w ,w ,w ) 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 sharing threshold: 5. 23 Output Revelation secure equality test Output 0 (s0, s’0) (s0, s’0) Output 1 (s0,s1) (s1, s’1) (s1, s’1) (s’0,s’1) One and only one of the 2 tests can succeed. 24 Conclusions Actively secure two party computation can be done with reduced number of circuits via either punishing the cheater or symmetric cut-and-choose.