Advancements in Active Secure Multiparty Computation (MPC)

Delve into the realm of secure multiparty computation under 1-bit leakage, exploring the intersection of DP algorithms, MPC, and the utilization of leakage for enhanced performance. Discover the overhead implications of achieving active security, as well as the evolution of secure computation protocols like Yaos 2PC. Uncover state-of-the-art advancements in active 2PC, exemplified by a timeline of significant milestones and efficiency improvements across different protocols.

• Secure Computation
• Multiparty Computation
• Active Security
• MPC
• Leakage

dulcie Follow

Uploaded on Aug 09, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Active Secure MPC under 1-bit leakage Muthu Venkitasubramaniam (U Rochester) Based on joint works with Carmit Hazay, Yuval Ishai, abhi shelat

2. Active Secure MPC under 1-bit leakage Muthu Venkitasubramaniam (U Rochester) Based on joint works with Carmit Hazay, Yuval Ishai, abhi shelat

3. What we have seen so far? Many applications have DP algorithms Some have local DP solutions in the multiparty setting Centralized DP be combined with MPC generically Leaking helps improve MPC performance Protect leakage by modifying the guarantee to DP Most protocols are only passive secure This talk: Does leakage help achieve active security?

4. Secure Computation Concrete Question: Concrete Question: What is the overhead of achieving active security over passive security? Boolean: Yao-style protocols in O(1) rounds [LP11, .] Communication efficiency: Bits transmitted in OT-hybrid Computational efficiency: #BB calls to a PRG

5. Yaos 2PC OT

6. Yaos 2PC Yao

7. Yaos 2PC Yao

8. State-of-the-art Yao-style Active 2PC NISC IKOPS11, IKLOPSZ13 BMR-style LPSY15, , WRK17 Passive Yao86 Cut & choose LP11, , COT [HIV17] Rounds 1 1 Comm. # PRG calls # OT calls ? ? ? ? Theorem [HIV17]: Active Secure 2PC Theorem [HIV17]: Active Secure 2PC with constant overhead O(Passive Yao) + low-order terms.

9. Active Secure 2PC Lots of work in 1980s, 1990s on theoretical MPC 2009: Pinkas, Schneider, Smart, Williams 2PC: Malicious: 1148 seconds 2PC: SH: 7 seconds 2010: SH: 4500 ms 2011: SH: 211 ms 2013: SH: 16 ms 2015: SH: 5 ms 2017: SH: 1.4 ms 2017: Malicious: 65 ms 2017: Malicious: 37ms

10. Active Secure 2PC Lots of work in 1980s, 1990s on theoretical MPC 2009: Pinkas, Schneider, Smart, Williams 2PC: Malicious: 1148 seconds 2PC: SH: 7 seconds 2010: SH: 4500 ms 2011: SH: 211 ms 2013: SH: 16 ms 2015: SH: 5 ms 2017: SH: 1.4 ms 2017: Malicious: 65 ms 2017: Malicious: 37ms

11. Why concede to leakage? Want: Scalable MPC for big data Overhead of active over passive still exorbitant Goal: Active security with constant overhead over passive security with leakage

12. What we do? Active security at the cost of passive with leakage What we don t do but would really like to do? Show leakage is DP

13. Dual Execution [MF06] Yao

14. Dual Execution [MF06] Yao Yao

15. Dual Execution [MF06] Yao Yao

16. Dual Execution [MF06] Yao Yao EQ? Overhead 2 and leaks 1 bit Only Boolean Requires multiple rounds of interaction

17. Why concede to leakage? Want: Scalable MPC for big data Overhead of active over passive still exorbitant Goal: Active security with constant overhead over passive security with leakage

18. Why concede to leakage? Want: Scalable MPC for big data Overhead of active over passive still exorbitant Goal: Active security with constant overhead over passive security with leakage

19. Our Results - Active secure 2PC with 1-bit leakage Theorem 1[sV18]: Boolean f that is g-efficiently verifiable overhead = Yao(f)+Yao(g) Theorem 2 [sV18]: Arbitrary f that is g-efficiently verifiable overhead = GMW(f) + active-protocol(g) Theorem 3 [HIV17]: Arbitrary f overhead = (1+c) Yao(f)

20. Efficiently Verifiable Functions We say that ? is efficiently verifiable by ? if ? < ? and ? ?,?,? = 1 ? ?,? = ? Examples 1. Matrix multiplication requires O(n3), can be checked O(n2) 2. Max-flow requires O(E2V), can be checked in O(E+V) 3. LP can be checked by complementary slackness condition 4. Convex hull requires O(nlogn), checked in O(n)

21. Theorem 1 [sV18]: Boolean f

22. Theorem 1 [sV18]: Boolean f Yao Yao EQ?

23. Theorem 1 [sV18]: Boolean f Yao Yao

24. Theorem 1 [sV18]: Boolean f Yao Yao

25. Theorem 1 [sV18]: Boolean f Yao Yao Yes/No

26. Theorem 1 [sV18]: Boolean f Yao Yao Yes/No overhead = Yao(f)+Yao(g)

27. Theorem 2 [sV18]: Arbitrary f GMW

28. Theorem 2 [sV18]: Arbitrary f GMW ??? ? Yes/No overhead = GMW(f) + ???(g)

29. Theorem 2 [sV18]: Arbitrary f ???? ? ??? ? Yes/No overhead = ????(f) + ???(g) Instantiate ????with any weakly private prot. [GIPST14] Examples include GMW, BGW, CCD, DI Extends to the multiparty setting!

30. Application: Perfect Matching [Harvey06] Algebraic Algorithms for Matching and Matroid Problems Cast Harvey s algorithm as a passive protocol in matrix-multiplication hybrid A B C2 C1 C1+C2 = A+B

31. Application: Perfect Matching [Harvey06] Algebraic Algorithms for Matching and Matroid Problems Cast Harvey s algorithm as a passive protocol in matrix-multiplication hybrid

32. Application: Perfect Matching [Harvey06] Algebraic Algorithms for Matching and Matroid Problems Perfect matching in ? ?? Cast Harvey s algorithm as a passive protocol in matrix-multiplication hybrid Communication complexity is ? ?2 Checking perfect matching is ? ?2 Protocol is weakly private Amplify to active security with 1-bit leakage Observation: Realize with weakly private protocol and compose protocol and compose [Harvey06] Algebraic Algorithms for Matching and Matroid Problems Perfect matching in ? ?? Cast Harvey s algorithm as a passive protocol in matrix-multiplication hybrid Communication complexity is ? ?2 Checking perfect matching is ? ?2 Protocol is weakly private Amplify to active security with 1-bit leakage Observation: Realize with weakly private

33. Theorem 3 [HIV17]: Arbitrary f

34. Theorem 3 [HIV17]: Arbitrary f Yao

35. Theorem 3 [HIV17]: Arbitrary f Garble

36. Theorem 3 [HIV17]: Arbitrary f Idea: Authenticated Garbling [IKOPS11,WRK17a/b,HIV17,WRRK18] Garble

37. Theorem 3 [HIV17]: Arbitrary f Idea: Authenticated Garbling [IKOPS11,WRK17a/b,HIV17,WRRK18] Auth. Garble Deal with selective abort: [IKOPS11] Use certified OT [WRK17a/b,WRRK18] Use distributed garbling [HIV17] Use doubly-certified OT polylog overhead O(s) overhead O(1) overhead, uses AG codes

38. Theorem 3 [HIV17]: Arbitrary f Idea: Authenticated Garbling [IKOPS11,WRK17a/b,HIV17,WRRK18] Simple insight: Selective abort can cause 1-bit leakage Auth. Garble Deal with selective abort: [IKOPS11] Use certified OT [WRK17a/b,WRRK18] Use distributed garbling [HIV17] Use doubly-certified OT polylog overhead O(s) overhead O(1) overhead, uses AG codes

39. Theorem 3 [HIV17]: Arbitrary f Idea: Authenticated Garbling [IKOPS11,WRK17a/b,HIV17,WRRK18] Simple insight: Selective abort can cause 1-bit leakage Auth. Garble [HIV17] Design lean MAC Adds s bit auth. information with every ciphertext overhead = (1+s/k) Yao(f)

40. Certified OT [IKOPS11] Cert OT Global NP Predicate R Sender ? = ?1, Witness w Receiver 0,?1 0,?? 1, ., ??, 1 ? = ?1, ,?? [HIV17] Design concretely efficient protocol for Cert-OT Use MPC-in-the-head [IKOS07,IKOPS11] Communication overhead = parallel-OT + low order terms

41. Our Results - Active secure 2PC with 1-bit leakage Theorem 1[sV18]: Boolean f that is g-efficiently verifiable overhead = Yao(f)+Yao(g) Theorem 2 [sV18]: Arbitrary f that is g-efficiently verifiable overhead = GMW(f) + active-protocol(g) Theorem 3 [HIV17]: Arbitrary f overhead = (1+c) Yao(f)

42. Secure greedy algorithms [sV15] Iterative approach Reduce to secure comparison Leak partial result in each iteration Examples: Median [AMP10], Minimum spanning tree[BS11], job scheduling, convex full, combinatorial optimizations Communication = O(Input+Output) Active secure 2PC for medians with simple checks Can we extend to greedy algorithms?

43. Thank You