Practical Deployment of Secure Multi-Party Computation and Cryptography Paradox

Jai Dadabhai Practical and Deployable Secure Multi-Party Computation Debayan Gupta Yale University May 11, 2016

2 The Apparent Paradox of Modern Cryptography Intuitive ideas of secrecy - Encrypted data are safe; but they appear to be unusable If people have secrets, and want to do a joint computation - They can use a trusted third party Modern cryptography - You may not have to decrypt - There may not need to be a trusted third party

3 Secure Multi-Party Computation (SMPC) Have your cake and eat it too Secret inputs; joint computation of desired output (Yao82) SMPC or Secure Function Evaluation (SFE) State of the art - 2P-SFE: Currently fast enough for many applications - SMPC: Fast enough in some cases - Fully Homomorphic Encryption: Slow, but improving

4 Talk Outline Example: Privacy-preserving Proximity PartialGC (ACM CCS'14*) - With Benjamin Mood, Kevin Butler, and Joan Feigenbaum Other work on practical, secure computation - SMPC: Overview and challenges - Frigate, SGX, Systematization Deploying SMPC Ongoing and future work *Expanded version: http://arxiv.org/abs/1506.02954

5 Talk Outline Example: Privacy-preserving Proximity PartialGC (ACM CCS'14*) - With Benjamin Mood, Kevin Butler, and Joan Feigenbaum Other work on practical, secure computation - SMPC: Overview and challenges - Frigate, SGX, Systematization Deploying SMPC Ongoing and future work *Expanded version: http://arxiv.org/abs/1506.02954

6 Privacy-Preserving Proximity 2 parties - They want to know whether they are within 1 mile of each other - Locations are private Classic 2P-SFE problem (garbled circuits, Yao82) - Every pair needs to start from scratch - Basic GC is still not efficient enough for mobile devices Could use a trusted cloud server - Location is kept private from other party but is known to server SFE 2. Location-2 1. Location-1 Bob Alice Are the locations within 1 mile of one another? Cloud Server 4. Result 3. Result

7 Proximity using PartialGC We want the advantages of a cloud server - But the privacy guarantees of SFE - Location data remain private from each other and cloud PartialGC is a garbled-circuit based, general method for fully privacy-preserving server-aided computation Cloud Server SFE SFE Bob Alice

8 Overview of PartialGC Garbled circuits Cut-and-choose for GCs secure against malicious adversaries Partial garbled circuits - Break a large garbled circuit into smaller sub-circuits - Encrypted outputs of one GC become inputs to the next - No intermediate decryption To achieve this, we need novel circuit-generation and cut-and-choose techniques

9 Garbled Circuits 2 parties Private inputs; outputs may be private or public Public function represented as a Boolean circuit The generator creates and encrypts (or garbles ) the circuit The evaluator evaluates the garbled circuit - Gate by gate - Online: Evaluation involves interaction with the generator

10 Generating a Garbled Circuit AND AND OR A B C A B C Permute 0 0 c0 0 0 E(A0.B0, c0) E(A1.B1, c3) Generator creates 4 keys, one each for A=0, A=1, B=0, and B=1 This is sent to the evaluator 0 1 c1 0 1 E(A0.B1, c1) E(A1.B0, c2) 1 0 c2 1 0 E(A1.B0, c2) E(A0.B0, c0) 1 1 c3 1 1 E(A1.B1, c3) E(A0.B1, c1)

11 Evaluating a Garbled Circuit Eval-input Received Gen-input E(A0.B0, c#) E(A#.B#, c#) E(A0.B#, c#) E(A0.B0, c#) Generator sends A0 if its input is 0 or A1, if its input is 1 E(A#.B#, c#) E(A0.B#, c#) Plug in B0 (e.g.) E(A0.B0, c#) E(A#.B#, c#) E(A0.B#, c#) E(A0.B0, c#) E(A#.B#, c#) E(A0.B#, c#) Eval-input B0 This should be B0 if the evaluator s input was 0, and B1 if it was 1 How do we do this? Oblivious Transfer E(A0.B0, c#) Value of C for one row of the table B1 E(A0.B0, c#) E(A0.B0, c#) E(A0.B0, c#) Evaluator s input

12 Cut-and-Choose How can we defend against malicious adversaries? - Many copies of the circuit - Check some circuits, evaluate the rest normally - Final result is majority output Malicious evaluator: sign output within the circuit - Does not guarantee fair release Generator sends all keys (A0,A1,B0,B1) for that circuit to the evaluator Generator creates Boolean circuit from program Generator builds many different garbled versions of this circuit Evaluator randomly selects some circuits as check All circuits are sent to the evaluator

13 Talk Outline Example: Privacy-preserving Proximity PartialGC (ACM CCS'14*) - With Benjamin Mood, Kevin Butler, and Joan Feigenbaum Other work on practical, secure computation - SMPC: Overview and challenges - Frigate, SGX, Systematization Deploying SMPC Ongoing and future work *Expanded version: http://arxiv.org/abs/1506.02954

14 Partial Garbled Circuits We need to take encrypted output from one GC - And feed it as input into another GC - Different evaluator Trivial if we have a trusted third party - Take the encrypted output from GC1, decrypt - Re-encrypt with new keys, and send as input to GC2 But we have a way to jointly compute a function without requiring a trusted third party garbled circuits! Trusted Third Party GC1 Transform GC2

15 Transformation Augment circuits with an extra layer of input gates These are 1-input gates, attached to each input bit Output from this gate is a valid input for the new circuit - Same idea as normal garbled circuits - One nonce per sub-circuit copy - More variants available in thesis Output-0 Input-0 GATE GATE Output-1 Input-1 Gets Output-X from info Input-X = hash( Output-X . nonce ) XOR Transform-X hash( ) XOR Input-X XOR hash(...) = Input-X nonce = random(), group_enc(info) Transform-0 = hash( Output-0 . nonce ) XOR Input-0 Transform-1 = hash( Output-1 . nonce ) XOR Input-1 Send to Evaluator

16 Cut-and-Choose Complications Standard cut-and-choose - Each circuit has multiple copies* - Generator knows which circuits are being checked after the first round (first evaluator) - We cannot have a different set of check circuits (this leaks information) The generator must not learn which circuits are being checked - Use oblivious transfer! GC1 GC2 Check Check Check Check Evaluate Evaluate Check Evaluate Evaluate Check

17 PartialGC Cut-and-Choose Generator offers check and evaluation keys for each sub-circuit copy - Evaluator selects one key for each via OT - Generator never learns whether a sub- circuit was checked or evaluated Use OT cut-and-choose for first round Subsequent rounds - No need to select a new set of check and evaluation circuits - Use saved (encrypted) data to pass on this information GC1 1 copy of sub-circuit Check-key OT Check Evaluate-key Check-key OT Evaluate Evaluate-key Check-key OT Check Evaluate-key

18 Performance We compare PartialGC to CMTB, which is based on the PCF (Kreuter-Shelat-Shen) system. Time taken to save and load a bit in PartialGC (using 256 copies in the cut-and-choose)

19 Solving Privacy-Preserving Proximity Question: Are we within 1 mile of each other? - Users communicate with the server in rounds - During each round, the user provides its current location, which is checked against the last reported location of the other user N users - One party s leaving does not stop the protocol Cloud Saved (encrypted) data Server Server Server Server Server Server PGC PGC PGC PGC PGC PGC Alice Bob Alice Charlie Bob Alice Alice Charlie Bob

20 Implementation

21 PartialGC is a fully general, server-aided, secure, multiparty computation mechanism We implemented privacy-preserving proximity - First SFE app fast and light enough to run on a standard phone Entry system that counts the number of people in a building - Disallows entry if there are too many people Saving credit card details across multiple purchases - One person could also pay for a group of purchases by different people Secure auctions - Only the highest/lowest values are saved per round Any iterative computation

Talk Outline Example: Privacy-preserving Proximity PartialGC (ACM CCS'14*) - With Benjamin Mood, Kevin Butler, and Joan Feigenbaum Other work on practical, secure computation - SMPC: Overview and challenges - Frigate, SGX, Systematization Deploying SMPC Ongoing and future work *Expanded version: http://arxiv.org/abs/1506.02954

23 Secure, Multiparty Computation (SMPC) . . . xn-1 x3 xn x2 x1 y = F (x1, , xn) Each i learns y No i can learn anything about xj (except what he can infer from xiand y ) Very general positive results (e.g., GMW87, BGW88) Not very widely used in practice YET!

24 Last 10 or 15 Years: Substantial Progress on Making SMPC Practical and Usable Better conceptual frameworks Development environments and tools (languages, compilers, intermediate circuit formats, run-time systems) Realistic use cases Realistic execution environments, e.g., handheld devices and cloud servers Theoretical advances and new techniques Experiments and performance analysis

Communication Pattern: Trusted-Party Computations 25

26 Communication Pattern: General SMPC Protocols

27 Communication Pattern: K-for-N Secure Outsourcing

28 Frigate Compiler Many existing development tools for secure protocols are unstable, buggy, and hard to use Frigate is a validated, extensible, and efficient compiler for SMPC - Dramatically more efficient than others (experimental comparisons with KSS, PCF, and CMBC) - Carefully tested and validated to ensure correctness - Easy to install and use; C-like language Compiles C-like programs into a Boolean-circuit representation that can be executed in a variety of SMPC run-time systems "Frigate: A Validated, Extensible, and Efficient Compiler and Interpreter for Secure Computation In Proceedings of the 2016 IEEE European Symposium on Security and Privacy (EuroS&P) 2016 (with Benjamin Mood, Henry Carter, Kevin Butler, Patrick Traynor)

29 Frigate Compile-time Speedup

30 Frigate Execution-time Speedup

31 Using Intel Software Guard Extensions for Efficient Two-Party Secure Function Evaluation We analyze the difficulties of using SGX for 2P-SFE and why na ve protocols do not work We show how to augment an SGX system to provide stronger guarantees, and we provide a protocol that enables two SGX systems to perform 2P-SFE efficiently Outsourcing and hybrid protocols Augment honest-but-curious to malicious "Using Intel Software Guard Extensions for Efficient Two-Party Secure Function Evaluation In Proceedings of the Workshop on Encrypted Computing and Applied Homomorphic Cryptography (WAHC), 2016 (with Benjamin Mood, Joan Feigenbaum, Kevin Butler, Patrick Traynor)

32 Systematization of Secure Computation We classify approximately 180 secure-computation protocols along major axes (security, efficiency, adversarial model, execution environment, etc.) By-product: annotated bibliography We develop a graphical tool ( SysSC-UI ) for exploring the secure- protocol space, comparing protocols, discovering dependencies and trade-offs among properties, etc. So far, the classification and SysSC-UI have helped newcomers get up to speed on the state of the art in secure-computation research "Systematizing Secure Computation for Research and Decision Support In Proceedings of the 9th Conference on Security and Cryptography for Networks (SCN 14), pp. 380-397, Springer, 2014 (with Jason Perry, Joan Feigenbaum, and Rebecca Wright)

33 PartialGC SMPC Systematization Frigate SGX

Ongoing and Future Work Practical reusable garbled circuits, using novel symbolic encryption, gate representation, and mini-circuits (w/ Mood, Hopkins, Carter, Feigenbaum, Butler) Improved SMPC for stable matching (w/ Terner, shelat, Feigenbaum) Implementations of Intel SGX-enabled 2P-SFE protocols (w/ Mood, Butler, Feigenbaum) Economic, legal, and social barriers to adoption - Idiosyncratic SMPC trust model (Libicki et al., 2014) - Need to comply with laws and organizational policies - Hard to displace an existing TTP

The End