Secure Multi-Party Computation: Promises, Protocols, and Practicalities

ECRYPT NET
Workshop on Crypto for the Cloud & Implementation
http://crypto-events.di.ens.fr/ecryptnet/
Paris Crypto Day

École Normale Supérieure
Paris
27 June 2017

1. Secure Multi-Party Computation: Promises, Protocols, and Practicalities David Evans University of Virginia (visiting Inria Paris) École Normale Supérieure Paris 27 June 2017 ECRYPT NET Workshop on Crypto for the Cloud & Implementation
2. Motivating Secure Multi-Party Computation 1982-2010 2011-2017 Yao’s Millionaire’s Problem Genetic Matchr WARNING! Reproduction not recommended processing… Genetic Dating if a < b: 0 else 1 2
5. Decentralized Certificate Authority Alice’s Cert Cafe Bob’s Trust Emporium Key Generation Protocol # ← 0, 1 ) * ← 0, 1 ) (for = # ⨁ * ) s never exists in clear 5
6. Signing a Certificate Certificate Signing Protocol # ← 0, 1 ) # ← 0, 1 ) = (tbsCert# ) if = *: sign34,4 () = # ⊕ * , = # ⊕ * never exist in clear * ← 0, 1 ) * ← 0, 1 ) * = (tbsCert* ) Alice’s Cert Cafe Bob’s Trust Emporium 6
7. Secure Two-Party Computation Can Alice and Bob compute a function on private data, without exposing anything about their data besides the result? = (, ) Alice’s Secret Input: Bob’s Secret Input: Alice’s Cert Cafe Bob’s Trust Emporium 7
8. Secure Two-Party Computation Can Alice and Bob compute a function on private data, without exposing anything about their data besides the result? = (, ) Alice’s Secret Input: Bob’s Secret Input: Alice’s Cert Cafe Bob’s Trust Emporium 8
9. FOCS 1982 FOCS 1986 Note: neither paper actually describes “Yao’s protocol” Andrew Yao 9
10. Yao’s Garbled Circuit Protocol Alice (circuit generator) Bob (circuit evaluator) Garbled Circuit Protocol secret input secret input Agree on function = (, ) = (, ) Learns nothing else about b Learns nothing else about a 10 skip?
11. Regular Logic Inputs Output a b 0 0 0 0 1 0 1 0 0 1 1 1 AND 11
12. “Obfuscated” Logic Inputs Output a b < < < < ? < ? < < ? ? ? AND @ , @ , @ are random values, chosen by generator but meaningless to evaluator. 12
13. Garbled Logic Inputs Output a b < < BC,DC (< ) < ? BC,DE (< ) ? < BE,DC (< ) ? ? BE,DE (? ) AND @ , @ , @ are random wire labels, chosen by generator 13
14. Garbled Logic Inputs Output a b ? ? BC,DC (< ) < ? BC,DE (< ) ? < BE,DC (< ) ? ? BE,DE (? ) AND Garbled Table (Garbled Gate) 14
15. Yao’s GC Protocol Alice (generator) Sends tables, her input labels (@ ) Bob (evaluator) Picks random values for <,? . <,? , <,? BC,DC (< ) BC,DE (< ) BE,DC (< ) BE,DE (? ) Evaluates circuit, decrypting one row of each garbled gate Decodes output Generates garbled tables 15
16. Yao’s GC Protocol Alice (generator) Sends tables, her input labels (@ ) Bob (evaluator) Picks random values for <,? . <,? , <,? Evaluates circuit, decrypting one row of each garbled gate Decodes output Generates garbled tables 16 BC,DC (< ) BC,DE (< ) BE,DC (< ) BE,DE (? ) How does the Bob learn his own input wire labels?
17. Primitive: Oblivious Transfer (OT) Alice (sender) Bob (receiver) Oblivious Transfer Protocol , selector Learns nothing about Rabin, 1981; Even, Goldreich, and Lempel, 1985; … 17
18. G0 G1 … G2 Chain gates to securely compute any discrete function! < < or ? < < < or ? < < ? or ? ? < ? or ? ? < < or ? < < ? or ? ? < L or ? L BC C,DC C(< <) BE C,DC C(< <) BC C,DE C(< <) BE C,DE C(? <) BC E,DC E(< ?) BE E,DC E(< ?) BC E,DE E(< ?) BE E,DE E(? ?) MC C,MC E(< L) ME C,MC E(< L) MC C,ME E(< L) ME C,ME E(? L)
19. From Theory to Practice
20. Building Computing Systems Digital Electronic Circuits Garbled Circuits Operate on known data Operate on encrypted wire labels 32-bit logical operation requires moving some electrons a few nm One-bit AND requires four encryptions Reuse is great! Reuse is not allowed! MC C,MC E(< L) ME C,MC E(< L) … 20
21. Measuring Cost (2PC) Asymptotic Communication Rounds (1) Asymptotic Complexity () Concrete Cost computation, encryptions, bandwidth $, € 21
22. 22 1 000€ 10 000€ 100 000€ 1 000 000€ 10 000 000€ 100 000 000€ 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 FairPlay (Malkhi, Nisan, Pinkas and Sella [USENIX Sec 2004]) .5M € Estimated cost of 4T gates 2PC, compute only (bandwidth free)
23. Scaling MPC Gate Execution Protocols Circuit Construction 23 MC C,MC E(< L) ME C,MC E(< L) …
24. Talk Outline Gate Execution Protocols Circuit Construction MC C,MC E(< L) ME C,MC E(< L) …
25. Ea1 ,b0 (x0 ) Ea0 ,b1 (x0 ) Ea1 ,b1 (x1 ) Ea0 ,b0 (x0 ) Simple Garbling Try all four, validation bits to determine valid output
26. Background: Point-and-Permute Enca0,,b0, (c0 ) Enca0,,b1 (c0 ) Enca0,,b0 (c0 ) Enca1,b1 (c1 ) Input wire labels (with selection bits) Output wire label Beaver, Micali and Rogaway [STOC 1990] 26 Select random bit for each wire: Set last bit of 0 to , 1 to ¬ Order table canonically: 00/01/10/11
27. Background: Garbled Row Reduction 27 Naor, Pinkas and Sumner [1999]
28. Background: Free-XOR Kolesnikov and Schneider [2008] Global generator secret
29. Background: Free-XOR Kolesnikov and Schneider [2008] Global generator secret XOR are “free”! No ciphertexts or encryption
30. Yan Huang, David Evans, and Jonathan Katz. Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? [NDSS 2012] 30 Yan Huang (UVa PhD 2012 → Indiana) Jonathan Katz (Maryland)
31. Yan Huang, David Evans, and Jonathan Katz. Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? [NDSS 2012]
32. Yan Huang, David Evans, and Jonathan Katz. Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? [NDSS 2012] swap gates (configured by generator) to do random permutation Journal of the ACM, January 1968
33. Generator Half Gate Known to generator (but secret to evaluator) 33
34. Generator Half Gate Known to generator (but secret to evaluator)
35. Swapper: “Generator Half Gate” With Garbled Row Reduction: 35 Known to generator (but secret to evaluator)
36. Two Halves Make a Whole Reducing Data Transfer in Garbled Circuits using Half Gates Samee Zahur, Mike Rosulek, and David Evans. In EuroCrypt 2015. Samee Zahur (UVa PhD 2016 → Google) + = 36 Mike Rosulek (Oregon State)
37. Evaluator Half-Gate But, we need a gate where both inputs are secret… Known to evaluator (but secret to generator)
38. Half + Half = Full Secret Gate generator half gate evaluator half gate 38 “leaked” unknown known unknown random bit selected by generator
39. Standard Gates Half Gates Generator Encryptions (H) 4 4 Evaluator Encryptions (H) 1 2 Ciphertexts Transmitted 3 2 XORs Free ✓ ✓ Bandwidth ê33% Execution Time (edit distance) ê25% Energy ê21% 39
40. Standard Gates Half Gates Generator Encryptions (H) 4 4 Evaluator Encryptions (H) 1 2 Ciphertexts Transmitted 3 2 XORs Free ✓ ✓ Bandwidth ê33% Execution Time ê25% Energy ê21% 40
41. Standard Gates Half Gates Generator Encryptions (H) 4 4 Evaluator Encryptions (H) 1 2 Ciphertexts Transmitted 3 2 XORs Free ✓ ✓ Bandwidth ê33% Execution Time ê25% Energy ê21% 41 Unless bandwidth is “free”, real cost (€) is almost all bandwidth!
42. Talk Outline Gate Execution Protocols Circuit Construction MC C,MC E(< L) ME C,MC E(< L) …
43. Fairplay 43 Malkhi, Nisan, Pinkas and Sella [USENIX Sec 2004] SFDL Program SFDL Compiler Circuit (SHDL) Garbled Tables Generator Garbled Tables Evaluator SFDL Compiler
44. Pipelined Execution Circuit-Level Application GC Framework (Evaluator) GC Framework (Generator) Circuit Structure Circuit Structure Yan Huang (UVa PhD → Indiana U.) Yan Huang, David Evans, Jonathan Katz, and Lior Malka. Faster Secure Two-Party Computation Using Garbled Circuits. USENIX Security 2011. x1 x2 y1 y2 z1 z2
45. 45 1 000€ 10 000€ 100 000€ 1 000 000€ 10 000 000€ 100 000 000€ 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 Free-XOR Pipelining, +
46. 46 1€ 10€ 100€ 1 000€ 10 000€ 100 000€ 1 000 000€ 10 000 000€ 100 000 000€ 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 Free-XOR Pipelining, + Half Gates Estimated cost of 4T gates 2PC, compute only (bandwidth free)
47. Passive Threat Model Honest-but-Curious (also called Semi-Honest) Security and correctness only guaranteed if participants follow the protocol.
48. Semi-Honest (“Honest but Curious”) Alice Bob generated circuits generator oblivious transfer Evaluates output decoding/sharing = (, ) Only provides privacy and correctness guarantees if circuit is generated honestly!
49. Standard Fix: “Cut-and-Choose” Generator (Alice) Evaluator (Bob) (1) instances of generated circuit (5) If okay, evaluate rest and select majority output (4) checks all revealed circuits (2) Challenge: choose a random subset (3) Keys for selected circuits Provides security against active attacker, but for reasonable security > 100 49
50. 50 1€ 10€ 100€ 1 000€ 10 000€ 100 000€ 1 000 000€ 10 000 000€ 100 000 000€ 1000 000 000€ 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 Semi-Honest Active Security (cut-and-choose)
51. Semi-Honest is Half-Way There Privacy Nothing is revealed other than the output (Not) Correctness The output of the protocol is (, ) Generator Evaluator As long as evaluator doesn’t send result (or complaint) back, privacy for evaluator is guaranteed. 51
52. Dual Execution Protocols Yan Huang, Jonathan Katz, David Evans. [IEEE S&P (Oakland) 2012] 52
53. Dual Execution Protocol Alice Bob first round execution (semi-honest) generator evaluator generator evaluator = (, ) Pass if = ’ and correct wire labels ’, learned output wire labels second round execution (semi-honest) ′ = (, ) z, learned output wire labels fully-secure, authenticated equality test 53
54. Security Properties Correctness: Guaranteed by authenticated, secure equality test Privacy: Leaks one (extra) bit on average adversarial circuit fails on ½ of inputs 54 Malicious generator can decrease likelihood of being caught, and increase information leaked when caught (but decreases average information leaked): at extreme, circuit fails on just one input.
55. Proving Security: Malicious A B Ideal World Adversary receives: (, ) Trusted Party in Ideal World Standard Malicious Model: can’t prove this for Dual Execution Real World A B Show equivalence Corrupted party behaves arbitrarily Secure Computation Protocol 55
56. Proof of Security: One-Bit Leakage A B Ideal World Controlled by malicious A Î ® {0, 1} is an arbitrary Boolean function selected by adversary Adversary receives: (, ) and (, ) Trusted Party in Ideal World 56
57. Intuition: 1-bit Leak Cheating detected Victim’s Possible Inputs Inputs where (? , ) = 57
58. 58 1€ 10€ 100€ 1 000€ 10 000€ 100 000€ 1 000 000€ 10 000 000€ 100 000 000€ 1000 000 000€ 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 Semi-Honest Active Security (cut-and-choose) Dual Execution
59. Talk Outline Gate Execution Protocols Circuit Construction MC C,MC E(< L) ME C,MC E(< L) …
60. Problem Size Time / Cost (semi-honest) Genomic Distance [Zahur+, iDash Genome Privacy 2015] Compare sample human SNP datasets (4.5M variations) 8 seconds (∼ $0.00) Secure Stable Matching [Doerner+. ACM CCS 2016] National Residency Match (35,000 candidates, 30,000 slots) 17 hours (∼ $15) Secure Linear Regression [Gascon+, PETS 2017] 1M elements, 200 features, 2 parties (vertically- partitioned) 40 minutes (∼ $0.50) Running between 2 EC2.c4xlarge nodes in same region (1 Gbps) 60
61. Real Costs are People 61 Problem Size Time People Cost Secure Stable Matching [Doerner, Evans, shelat. ACM CCS 2016] National Residency Match 17 hours (∼ $15) ∼$1M Secure Linear Regression [Gascon+, PETS 2017] 1M elements, 200 features, 2 parties (vertically- partitioned) 40 minutes (∼ $0.50) ∼$2M Not our real costs, assuming market wages!
62. Library-based frameworks: Circuit-level programs Full control Low-level programming Little type safety High-level Languages Little control High-level programming Strong type safety High-level programming Low-level customizability Helpful, escapable type checking Tools for Building Secure Computations 62 oblivc.org
63. Data-Oblivious Array Access 63 a[i] = x Depends on private data
64. Circuit for Array Update 64 i == 0 a[0] x a'[0] Linear Scan: need to touch every array element to hide which one is real i == 1 a[1] x a'[1] i == 2 a[2] x a'[2] i == 3 a[3] x a'[3] …
65. Traditional ORAM Client Untrusted Server [Goldreich 1987] Security property: all initialization and access sequences of the same length are indistinguishable to server. Sublinear client- side state Linear server-side encrypted state Initialize Access 65
66. RAM-SC [Gordon, Katz, Kolesnikov, Krell, Malkin, Raykova, Vahlis 2012] Alice Bob MPC Protocol Public ORAM state Public ORAM state Encrypted Results Oblivious ORAM state Initialize Access 66
67. Oblivious RAM Samee Zahur, Xiao Wang, Mariana Raykova, Adrià Gascón, Jack Doerner, David Evans, Jonathan Katz. Revisiting Square-Root ORAM. IEEE S&P 2016 (https://oblivc.org/sqoram/. 67
68. 16-byte blocks 32-byte blocks Pre-Access Cost (not counting initialization) 68
69. 16-byte blocks 32-byte blocks Whirlwind I (1951) 30 s, 2048 x 16-bit words 69
70. Z3 (1941) 70 Whirlwind I (1951) 30 s, 2048 x 16-bit words 16-byte blocks 32-byte blocks
71. Decentralized Certificate Authority MPC Signing Protocol # ← 0, 1 ) # ← 0, 1 ) = (tbsCert# ) if = *: sign34,4 () = # ⊕ * , = # ⊕ * never exist in clear * ← 0, 1 ) * ← 0, 1 ) * = (tbsCert* ) Alice’s Cert Cafe Bob’s Trust Emporium 71
72. Cost of Decentralizing Trust ECDSA Signing (secp192k1): 22 Billion gates Same Region AWS Virginia- California AWS-Azure Semi-Honest $0.33 $8.54 ∽$37 Dual Execution $0.65 $17.07 ∽$74
73. Cost of Decentralizing Trust ECDSA Signing (secp192k1): 22 Billion gates Same Region AWS Virginia- California AWS-Azure Semi-Honest $0.33 $8.54 ∽$37 Dual Execution $0.65 $17.07 ∽$74
74. Cost of Decentralizing Trust ECDSA Signing (secp192k1): 22 Billion gates Same Region AWS Virginia- California AWS-Azure Semi-Honest $0.33 $8.54 ∽$37 Dual Execution $0.65 $17.07 ∽$74
76. David Evans evans@virginia.edu www.cs.virginia.edu/evans oblivC.org 76 Bargav Jayaraman Haina Li Samee Zahur Jack Doerner