Efficient Multiparty Computation for Matrix Rings against Malicious Adversaries
Explore the development of efficient multiparty computation protocols for non-commutative rings, specifically focusing on matrix rings, in the dishonest majority setting to combat malicious adversaries. This study, presented at ASIACRYPT 2024, delves into the significance of utilizing matrix rings in preserving privacy in machine learning and their applications in various domains such as computer graphics and aerospace. Discover the importance of matrix rings in enhancing secure computations and their representation through matrices.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Dishonest Majority Multiparty Computation over Matrix Rings Hongqing Liu, Chaoping Xing, Chen Yuan, Taoxu Zou Shanghai Jiao Tong University Dec 10th,ASIACRYPT 2024
Multiparty Computation Ring Honest majority DN07,ATLAS, Dishonest Majority BDOZ,SPDZ MiniMAC, SPDZ2k,EXY22 Large field Binary field Integer ring 2? Non-commutative ring CCXY18,GS21, ACD+19,CRX21, ES21 Question: Can we design an efficient MPC protocol for some non-commutative rings in the dishonest majority setting against a malicious adversary? Answer: Yes for matrix rings ? ?(?)!
Why Matrix Rings? Matrix rings: privacy preserving machine learning Quaternion rings: computer graphics, aerospace
Why Matrix Rings? Matrix rings: privacy preserving machine learning Quaternion rings: computer graphics, aerospace Can be represented in the form of matrices! ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + ?? + ?? + ??
Recap: SPDZ protocol [DPSZ12] SPDZ: authenticated sharing = additive sharing + MAC ?1 ?? ? = ?1 + + ?? secret ? = ?1 + + ?? global key ? = ( ? , ? , ?? ) MAC ? ? = ?1? + + ??(?) Local computation Multiplication ( ? , ? , ? ) ? = ? ? Preprocessing Addition ? + ? = ( ?] + [? , ? ,[??] + [??]) open ? ? ? ,? ? [ ? ] Scalar Mult Online ?? = (? ? , ? ,?[??]) compute z = ? + ? ? + ? ? + ? ?
SPDZ protocol + matrix rings [CKR+21] MAC key secret ? = ( ? , ? , ?? ) ? ?? ? Local computation Multiplication Preprocessing ( ? , ? , ? ) ? = ?? Addition ? + ? = ( ?] + [? , ? ,[??] + [??]) open ? Left linearity ? ? ,? ? [ ? ] ?? = (? ? , ? ,?[??]) Online compute Z = ? + ? ? + ? ? + ?? Right linearity ?? = ( ? ?, ? , ?? ?)
Our authenticated sharing Share size: ??? ??+ ? Reduce around 50%! MAC secret key ? ? ?? ? = ( ? , ? , ?? ) Local computation Multiplication Preprocessing ( ? , ? , ? ) ? = ?? Addition ? + ? = ( ?] + [? , ? ,[??] + [??]) open ? ? ? ,? ? ? Left linearity ?? = (? ? ,[?],?[??]) Online compute ? = ? + ? ? + ?? + ?? Right linearity How to compute?
Our multiplication protocol Question: How to achieve the right linearity for our authenticated sharing scheme? Answer: Make of use the transpose of matrices! double sharing Preprocessing ( ? , ??, ? , ? , ? , ?? ) ? = ?? Multiplication sextuple = Beaver triple + double sharing open D ? ? ,? ? ? Drawback: Additional round Online open ? ???? ?? compute ? = ? + ? ? + ? + ??+ ?? Solution: Function-dependent preprocessing
Vector Oblivious Linear Evaluation ? ??,? ? Expand ? ? VOLE ? ? Bob Alice ?,? ??s.t. ? + ? = ? ? ?-party VOLE = ?2invocations of 2-party VOLE Application: VOLE could be used to generate the MAC shares.
Random VOLE [BCGI18] Expand: ? ?? ? = Expand(?) ? Expand ? ?,? ? ? ? RVOLE ? ? Alice Bob ?,? ??s.t. ? + ? = ? ? From VOLE to RVOLE: Communication cost sublinear in the vector length ? Fundamental primitives of RVOLE: Base VOLE + OT VOPE Subfield VOLE NEW!
Subfield VOLE [BCG+19] Expand: ? ??1 ? = Expand(?) ? Expand Expand ? ?,? ??2 ? ? SVOLE Alice Bob ? ? :??1 ??2 ?1 ?2(?) ? ??,?= ?? ?? ?,? ?1 ?2(?) s.t. ? + ? = ? ? From RVOLE to SVOLE: Reuse the seed to reduce the number of OT instances
Vector Oblivious Product Evaluation Expand: ? ??1 Expand : ? ??2 ? = Expand(?) ? = Expand (? ) ? ? Expand Expand Expand ? ?,? ? ? ? VOPE Alice Bob ? ? :??1 ??2 ?1 ?2(?) ? ??,?= ?? ?? ?,? ?1 ?2(?) s.t. ? + ? = ? ? From SVOLE to VOPE: Transform base VOLE instances into random VOLE instances
Random Matrix Multiplication ? ??1 ?2(?) ? ??1 ?2(?) ? ??1 ?3(?) ? = ?? ? ??1 ?2(?) ? ??1 ?2(?) ? ??1 ?3(?) ? ?1,? [?3] ??,? ??,?= ?? ?? ?? ?? inner product
Random Matrix Multiplication via VOPE ? ??1 ?2(?) ? ??1 ?2(?) ? ??1 ?3(?) ?2 ? = ?? = ?? ?? ?? ?=1 outer product ?? ) Expand : ? ??3 Expand: ? ??1 ??= Expand (?? ?i= Expand(??) ?? ?? Expand Expand Expand ??,?? ?1 ?3(?) s.t. ?? ?,s? ? ?? ?? ??+ ??= ?? ?? VOPE Alice Bob ?? ??
Performance: Online Phase Theoretic analysis Protocol SPDZ SPDZ + matrix This work (FI*) This work (FD*) * FI / FD: Function-Independent / Dependent Preprocessing Communication 4?3? 1 log? 4?2? 1 log? 6?2? 1 log? 4?2? 1 log? Share size 2?2log? 2?2log? # multiplication 6?3 5?3+ ?2 3?3+ 3?2 3?3+ 3?2 ? ? + 1 log? ? ? + 1 log? Reduce 40% computation! Experiment result SPDZ 1.3 sec 9.5 sec 77.9 sec 633 sec SPDZ + matrix 96 ms 559 ms 5.0 sec 42.5 sec This work 52 ms 329 ms 3.2 sec 30.9 sec ? 128 256 512 1024 1.38x-1.85x speedup!
Performance: Preprocessing Phase Theoretic analysis of communication Random VOLE 83.5 MB 362 MB 1453 MB 6000 MB Subfield VOLE 34.8 MB 138 MB 518 MB 2004 MB This work 19.0 MB 60 MB 198 MB 739 MB HE [CKR+21] 12.5 MB 50 MB 199 MB 797 MB ? 128 256 512 1024 Experiment result: benchmark Random VOLE 3.6 sec 13.9 sec 56.4 sec 4.1 min Subfield VOLE 2.9 sec 10.1 sec 38.2 sec 2.5 min This work 4.1 sec 8.2 sec 16.8 sec 36.0 sec HE [CKR+21] 5.9 sec 25.5 sec 2.3 min 14.5 min ? 128 256 512 1024 1.44x- 24.17x speedup!
Summary This work DPSZ12 CKR+21 online share size computation ??% ??% communication ?/? HE CKR+21 preprocessing VOPE This work RVOLE [BCGI18] SVOLE [BCG+19] VOLE base VOLE OT
References [DPSZ12] Ivan Damgard, Valerio Pastro, Nigel Smart, and Sarah Zakarias: Multiparty computation from somewhat homomorphic encryption. In: CRYPTO 2012. [BGIN18] Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai: Compressing vector OLE. In: ACM CCS 2018. [BCG+19] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl: Efficient pseudorandom correlation generators: Silent OT extension and more. In: CRYPTO 2019. [CKR+21] Hao Chen, Miran Kim, Ilya Razenshteyn, Dragos Rotaru, Yongsoo Song, and Sameer Wagh: Maliciously secure matrix multiplication with applications to private deep learning. In: ASIACRYPT 2020.
Thank you! See our full version at ia.cr/2023/1912. If you have any questions, please contact me via liu.hong.qing@sjtu.edu.cn
