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.
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.
E N D
Presentation Transcript
Active Secure MPC under 1-bit leakage Muthu Venkitasubramaniam (U Rochester) Based on joint works with Carmit Hazay, Yuval Ishai, abhi shelat
Active Secure MPC under 1-bit leakage Muthu Venkitasubramaniam (U Rochester) Based on joint works with Carmit Hazay, Yuval Ishai, abhi shelat
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?
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
Yaos 2PC OT
Yaos 2PC Yao
Yaos 2PC Yao
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.
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
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
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
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
Dual Execution [MF06] Yao Yao
Dual Execution [MF06] Yao Yao
Dual Execution [MF06] Yao Yao EQ? Overhead 2 and leaks 1 bit Only Boolean Requires multiple rounds of interaction
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
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
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)
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)
Theorem 1 [sV18]: Boolean f Yao Yao EQ?
Theorem 1 [sV18]: Boolean f Yao Yao
Theorem 1 [sV18]: Boolean f Yao Yao
Theorem 1 [sV18]: Boolean f Yao Yao Yes/No
Theorem 1 [sV18]: Boolean f Yao Yao Yes/No overhead = Yao(f)+Yao(g)
Theorem 2 [sV18]: Arbitrary f GMW ??? ? Yes/No overhead = GMW(f) + ???(g)
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!
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
Application: Perfect Matching [Harvey06] Algebraic Algorithms for Matching and Matroid Problems Cast Harvey s algorithm as a passive protocol in matrix-multiplication hybrid
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
Theorem 3 [HIV17]: Arbitrary f Idea: Authenticated Garbling [IKOPS11,WRK17a/b,HIV17,WRRK18] Garble
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
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
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)
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
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)
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?
