Linear Communication in Secure Multiparty Computation for Efficient and Fast Processing

The research focuses on achieving perfectly secure multiparty computation (MPC) with linear communication and constant expected time. It explores efficient approaches using a broadcast-hybrid model and P2P communication, aiming to balance speed and efficiency in MPC. The study highlights the importance of optimal resilience and gate-depth considerations in achieving secure computation.

• Secure Multiparty Computation
• Linear Communication
• Efficient Processing
• Perfect Security
• MPC

emer_2 Follow

Uploaded on Sep 20, 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. Detect, Pack and Batch: Perfectly-Secure MPC with Linear Communication and Constant Expected Time Ittai Abraham VMWare Research Gilad Asharov Bar-Ilan University Shravani Patil IISc Bangalore Arpita Patra IISc Bangalore

2. Secure Multiparty Computation Perfect Security ? <? 3 Unbounded adversary Zero error probability ?1 ?4 ?2 ?3 - ? parties ?1, ,??some corrupted by a centralized adversary - ?? has private input ?? - Goal: jointly compute a common ?-input function ?(?1,?2,..??) correctly (correctness), without leaking anything beyond (privacy). 1

3. MPC in the broadcast-hybrid model Efficient but Slow Fast but Inefficient [GLS19] [AAY21] ? ? ?3 ? ? ? P2P Communication Broadcast ?( ? ?3) ?(?) ?(? + ?) ?(?) Rounds [GLS19] Vipul Goyal, Yanyi Liu, and Yifan Song. "Communication-efficient unconditional MPC with guaranteed output delivery." CRYPTO, 2019. [AAY21] Ittai Abraham, Gilad Asharov, and Avishay Yanai. "Efficient perfectly secure computation with optimal resilience." TCC, 2021. 2

4. MPC in the broadcast-hybrid model Goal: Can we get the best of both the approaches? Efficient but Slow Fast but Inefficient [GLS19] [AAY21] ? ? ?3 ? ? ? P2P Communication Broadcast ?( ? ?3) ?(?) ?(? + ?) ?(?) Rounds 3

5. MPC in the broadcast-hybrid model Efficient but Slow Fast but Inefficient Efficient and Fast [GLS19] [AAY21] This Work ? ? ?3 ? ? ? ? ? ? P2P Communication Broadcast ?( ? ?3) ?(?3) ?(?) ?(? + ?) ?(?) ?(?) Rounds 4

6. MPC in the P2P model Efficient but Slow Fast but Inefficient Efficient and Fast [GLS19] [AAY21] This Work ? ? ? + ?4 ? ? ? + ?3 ? ? ?5 Communication ?(?) rounds Rounds ?(?2+ ?) ? ? ? + ?5 ?(? + ?) ? ? ? + ?4 ?(? + ?) ? ? ?4 Communication ?(? 1 ) rounds Rounds (Expected) ?(?) ?(?) ?(? + ?) 5

7. Our Main Result: Linear Communication MPC MPC with perfect security and optimal resilience (? < ?/3) ? ?? + ??2+ ?4 P2P communication for a circuit with ? gates and depth ?. ? ?? + ??2+ ?4 P2P ? ?3 broadcast [AAPP22] Expected ? ? rounds [AAPP22] Ittai Abraham, Gilad Asharov, Shravani Patil, and Arpita Patra. "Asymptotically Free Broadcast in Constant Expected Time via Packed VSS." TCC, 2022. 6

8. High Level Approach: MPC Beaver Triple Generation ?1 ?2 ?? 1 ?? ? ? complexity protocol for each building block VSS VSS VSS VSS VTS VTS VTS VTS Triple Extraction Beaver Multiplication [CP16] Ashish Choudhury, and Arpita Patra. "An efficient framework for unconditionally secure multiparty computation." IEEE Transactions on Information Theory, 2016. 7

9. High Level Approach: MPC Beaver Triple Generation ?1 ?2 ?? 1 ?? VSS VSS VSS VSS VTS VTS VTS VTS Triple Extraction Beaver Multiplication [CP16] Ashish Choudhury, and Arpita Patra. "An efficient framework for unconditionally secure multiparty computation." IEEE Transactions on Information Theory, 2016. [DN07] Ivan Damg rd, and Jesper Buus Nielsen. "Scalable and unconditionally secure multiparty computation." CRYPTO, 2007. 8

10. Key Design Principles Pack (P) Many secrets in one instance. The broadcast cost of many instances. Batch (B) Corrupt parties and neutralise their power to obstruct. Detect (D) 9

11. Verifiable Secret Sharing (VSS) Extends the concept of secret sharing to settings with malicious corruptions. Two phase protocol (Sh,Rec). Input: Dealer ? holds a secret ? Output: Each party ?? holds a secret ?? at the end of Rec. Hiding: If ? is honest, view of ? independent of ? at the end of Sh. Binding: Joint view of honest parties at the end of Sh defines ? . Validity: Honest parties output ? at the end of Rec. If ? is honest, then ? = ?. 10

12. Main Result: VSS Verifiable secret sharing with perfect security and optimal resilience (? < ?/3) ? ?? + ?4 communication complexity for sharing ? secrets Expected ? 1 rounds ? ? overhead per secret for ? ?3 Matches semi-honest secret sharing! 11

13. Comparison with the existing work Number of secrets Communication [AAPP22] This Work ? ?2 ? ?2 P2P P: ?(?2) ?(?2) Broadcast ?(?) ?(?4) P+D: ?(?4) Total Instead of (2?,?)-bivariate, choose a (3?/2,?)-bivariate Balance the broadcast communication ?(?) per party allows batching! [AAPP22] Ittai Abraham, Gilad Asharov, Shravani Patil, and Arpita Patra. "Asymptotically Free Broadcast in Constant Expected Time via Packed VSS." TCC, 2022. 12

14. Comparison with the existing work Number of secrets Communication [AAPP22] This Work ? ?2 ? ?2 P2P P: ?(?2) ?(?2) Broadcast ?(?) ?(?4) P+D: ?(?4) Total ?(??2) ?(??2) P2P P+D+B: ?(??2) ?(?2) ? ? ? Broadcast ? = ?(??) ?(?? + ?4) ?(??2+ ?4) Total Instead of (2?,?)-bivariate, choose a (3?/2,?)-bivariate Balance the broadcast communication ?(?) per party allows batching! [AAPP22] Ittai Abraham, Gilad Asharov, Shravani Patil, and Arpita Patra. "Asymptotically Free Broadcast in Constant Expected Time via Packed VSS." TCC, 2022. 13

15. High Level Approach: MPC Beaver Triple Generation ?1 ?2 ?? 1 ?? VSS VSS VSS VSS VTS VTS VTS VTS Triple Extraction Beaver Multiplication [CP16] Ashish Choudhury, and Arpita Patra. "An efficient framework for unconditionally secure multiparty computation." IEEE Transactions on Information Theory, 2016. [DN07] Ivan Damg rd, and Jesper Buus Nielsen. "Scalable and unconditionally secure multiparty computation." CRYPTO, 2007. 14

16. Detectable Secret Sharing (DSS) New notion of secret sharing with malicious corruptions. Two phase protocol (Sh,Rec). Input: Dealer ? holds a secret ? Output: Each party ?? holds a secret ?? at the end of Rec. Hiding: If ? is honest, view of ? independent of ? at the end of Sh. Binding: Joint view of honest parties at the end of Sh defines ? . Validity: Honest parties output ? at the end of Rec. If ? is honest, then ? = ?. 15

17. Detectable Secret Sharing (DSS) New notion of secret sharing with malicious corruptions. Two phase protocol (Sh,Rec). Input: Dealer ? holds a secret ? Output: Each party ?? holds a secret ?? at the end of Rec. Hiding: If ? is honest, view of ? independent of ? at the end of Sh. Binding: Joint view of honest parties at the end of Sh defines ? . Validity: One of the following conditions holds: Rec succeeds: Honest parties output ? at the end of Rec. If ? is honest, then ? = ?. Rec fails: Honest dealer identifies ?(?) corrupt parties. VSS 16

18. Main Result: DSS Detectable secret sharing with perfect security and optimal resilience (? < ?/3) ? ? + ?4 communication complexity for sharing ? secrets Expected ? 1 rounds ? 1 overhead per secret for ? ?4 Matches packed semi-honest secret sharing! 17

19. VSS v/s DSS Number of secrets Number of instances P2P Broadcast Total VSS DSS ?(?4) ? ?2 ? ?2 ? ?2 1 ? ? Pack ?(?) secrets along both the ? and ? dimensions of the bivariate! P+D: P*+D: 18 18

20. VSS v/s DSS Number of secrets Number of instances P2P Broadcast Total VSS DSS ?(?4) ? ?2 ? ?2 ? ?2 1 ? ? ?(??2) ?(?2) ?(??2+ ?4) ? ??2 ? ?(??) P+D+B: P*+D+B: P+D: P*+D: 19 19

21. Summary: Key Design Principles Many secrets in one instance. Pack The broadcast cost of many instances. Batch Corrupt parties and neutralise their power to obstruct. Detect 20

22. Summary: Our Contributions Beaver Triple Generation ?1 ?2 ?? 1 ?? ?(?) VSS VSS VSS VSS Improvement ?(?3) VTS VTS VTS VTS Triple Extraction Beaver Multiplication [AAPP22] Ittai Abraham, Gilad Asharov, Shravani Patil, and Arpita Patra. "Asymptotically Free Broadcast in Constant Expected Time via Packed VSS." TCC, 2022. [CP16] Choudhury, Ashish, and Arpita Patra. "An efficient framework for unconditionally secure multiparty computation." IEEE Transactions on Information Theory, 2016. 21

23. Thank You! https://eprint.iacr.org/2023/557.pdf