Communication-Efficient Multi-Party Computation for RMS Programs
Authors
Thomas Attema, Aron van Baarsen, Stefan van den Berg, Pedro Capitão, Vincent Dunning, Lisa Kohl
Abstract
Despite much progress, general-purpose secure multi-party computation (MPC) with active security may still be prohibitively expensive in settings with large input datasets. This particularly applies to the secure evaluation of graph algorithms, where each party holds a subset of a large graph. Recently, Araki et al. (ACM CCS '21) showed that dedicated solutions may provide significantly better efficiency if the input graph is sparse. In particular, they provide an efficient protocol for the secure evaluation of “message passing” algorithms, such as the PageRank algorithm. Their protocol's computation and communication complexity are both $\tilde{O}(M\cdot B)$ instead of the $O(M^2)$ complexity achieved by general-purpose MPC protocols, where $M$ denotes the number of nodes and $B$ the (average) number of incoming edges per node. On the downside, their approach achieves only a relatively weak security notion; $1$-out-of-$3$ malicious security with selective abort.
In this work, we show that PageRank can instead be captured efficiently as a restricted multiplication straight-line (RMS) program, and present a new actively secure MPC protocol tailored to handle RMS programs. In particular, we show that the local knowledge of the participants can be leveraged towards the first maliciously-secure protocol with communication complexity linear in $M$, independently of the sparsity of the graph. We present two variants of our protocol. In our communication-optimized protocol, going from semi-honest to malicious security only introduces a small communication overhead, but results in quadratic computation complexity $O(M^2)$. In our balanced protocol, we still achieve a linear communication complexity $O(M)$, although with worse constants, but a significantly better computational complexity scaling with $O(M\cdot B)$. Additionally, our protocols achieve security with identifiable abort and can tolerate up to $n-1$ corruptions.
References
[AC20]
Thomas Attema and Ronald Cramer. Compressed $\varSigma$-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics. In CRYPTO (3), volume 12172 of Lecture Notes in Computer Science, pages 513–543. 2020. Springer. DOI: 10.1007/978-3-030-56877-1_18
[ACC+22]
Thomas Attema, Ignacio Cascudo, Ronald Cramer, Ivan Damgård, and Daniel Escudero. Vector Commitments over Rings and Compressed $\varSigma$-Protocols. In TCC (1), volume 13747 of Lecture Notes in Computer Science, pages 173–202. 2022. Springer. DOI: 10.1007/978-3-031-22318-1_7
[ACK21]
Thomas Attema, Ronald Cramer, and Lisa Kohl. A Compressed $\varSigma$-Protocol Theory for Lattices. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II, volume 12826 of LNCS, pages 549–579, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84245-1_19
[AFO+21]
Toshinori Araki, Jun Furukawa, Kazuma Ohara, Benny Pinkas, Hanan Rosemarin, and Hikaru Tsuchida. Secure Graph Analysis at Scale. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 610–629, New York, NY, USA. 2021. Association for Computing Machinery. DOI: 10.1145/3460120.3484560
[Att23]
Thomas Attema. Compressed $\varSigma$-Protocol Theory. PhD thesis, Leiden University, 2023.
[BBB+18]
Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Gregory Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. In IEEE Symposium on Security and Privacy, pages 315–334. 2018. IEEE Computer Society. DOI: 10.1109/SP.2018.00020
[BCC+16]
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In EUROCRYPT (2), volume 9666 of Lecture Notes in Computer Science, pages 327–357. 2016. Springer. DOI: 10.1007/978-3-662-49896-5_12
[BCG+17]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, and Michele Orrù. Homomorphic Secret Sharing: Optimizations and Applications. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 2105–2122. 2017. ACM Press. DOI: 10.1145/3133956.3134107
[BCS16]
Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive Oracle Proofs. In TCC (B2), volume 9986 of Lecture Notes in Computer Science, pages 31–60. 2016. DOI: 10.1007/978-3-662-53644-5_2
[BDO23]
Lennart Braun, Ivan Damgård, and Claudio Orlandi. Secure Multiparty Computation from Threshold Encryption Based on Class Groups. In CRYPTO (1), volume 14081 of Lecture Notes in Computer Science, pages 613–645. 2023. Springer. DOI: 10.1007/978-3-031-38557-5_20
[BDOZ11]
Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias. Semi-homomorphic Encryption and Multiparty Computation. In EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 169–188. 2011. Springer. DOI: 10.1007/978-3-642-20465-4_11
[BGI16]
Elette Boyle, Niv Gilboa, and Yuval Ishai. Breaking the Circuit Size Barrier for Secure Computation Under DDH. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, pages 509–539. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-53018-4_19
[BGW88]
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In 20th ACM STOC, pages 1–10. May 1988. ACM Press. DOI: 10.1145/62212.62213
[BKS19]
Elette Boyle, Lisa Kohl, and Peter Scholl. Homomorphic Secret Sharing from Lattices Without FHE. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 3–33. May 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-17656-3_1
[BP98]
Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Comput. Networks, 30(1-7):107–117, 1998. DOI: 10.1016/S0169-7552(98)00110-X
[CCD88]
David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty Unconditionally Secure Protocols (Extended Abstract). In 20th ACM STOC, pages 11–19. May 1988. ACM Press. DOI: 10.1145/62212.62214
[CCL+20]
Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker. Bandwidth-Efficient Threshold EC-DSA. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020, Part II, volume 12111 of LNCS, pages 266–296. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45388-6_10
[CDN01]
Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen. Multiparty Computation from Threshold Homomorphic Encryption. In EUROCRYPT, volume 2045 of Lecture Notes in Computer Science, pages 280–299. 2001. Springer. DOI: 10.1007/3-540-44987-6_18
[CGS97]
Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. A Secure and Optimally Efficient Multi-Authority Election Scheme. In Walter Fumy, editor, EUROCRYPT'97, volume 1233 of LNCS, pages 103–118. May 1997. Springer, Heidelberg. DOI: 10.1007/3-540-69053-0_9
[CL15]
Guilhem Castagnos and Fabien Laguillaumie. Linearly Homomorphic Encryption from $\mathsf{DDH}$. In Kaisa Nyberg, editor, CT-RSA 2015, volume 9048 of LNCS, pages 487–505. April 2015. Springer, Heidelberg. DOI: 10.1007/978-3-319-16715-2_26
[CLT18]
Guilhem Castagnos, Fabien Laguillaumie, and Ida Tucker. Practical Fully Secure Unrestricted Inner Product Functional Encryption Modulo p. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 733–764. December 2018. Springer, Heidelberg. DOI: 10.1007/978-3-030-03329-3_25
[COS+22]
Ilaria Chillotti, Emmanuela Orsini, Peter Scholl, Nigel P. Smart, and Barry Van Leeuwen. Scooby: Improved Multi-party Homomorphic Secret Sharing Based on FHE. In SCN, volume 13409 of Lecture Notes in Computer Science, pages 540–563. 2022. Springer. DOI: 10.1007/978-3-031-14791-3_24
[CSA21]
Daniele Cozzo, Nigel P. Smart, and Younes Talibi Alaoui. Secure Fast Evaluation of Iterative Methods: With an Application to Secure PageRank. In Kenneth G. Paterson, editor, CT-RSA 2021, volume 12704 of LNCS, pages 1–25. May 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-75539-3_1
[DH76]
Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, 1976. DOI: 10.1109/TIT.1976.1055638
[DHRW16]
Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, and Daniel Wichs. Spooky Encryption and Its Applications. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 93–122. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-53015-3_4
[DJ00]
Ivan B. Damgård and Mads J. Jurik. Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes. Jan. 2000.
[DJ01]
Ivan Damgård and Mads Jurik. A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System. In Public Key Cryptography, volume 1992 of Lecture Notes in Computer Science, pages 119–136. 2001. Springer. DOI: 10.1007/3-540-44586-2_9
[dPLS19]
Raël del Pino, Vadim Lyubashevsky, and Gregor Seiler. Short Discrete Log Proofs for FHE and Ring-LWE Ciphertexts. In Public Key Cryptography (1), volume 11442 of Lecture Notes in Computer Science, pages 344–373. 2019. Springer. DOI: 10.1007/978-3-030-17253-4_12
[DPSZ12]
Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty Computation from Somewhat Homomorphic Encryption. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 643–662. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_38
[ElG85]
Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469-472, 1985. DOI: 10.1109/TIT.1985.1057074
[FGJS17]
Nelly Fazio, Rosario Gennaro, Tahereh Jafarikhah, and William E. Skeith. Homomorphic Secret Sharing from Paillier Encryption. In Tatsuaki Okamoto, Yong Yu, Man Ho Au, and Yannan Li, editors, Provable Security, pages 381–399, Cham. 2017. Springer International Publishing. DOI: 10.1007/978-3-319-68637-0_23
[FPS00]
Pierre-Alain Fouque, Guillaume Poupard, and Jacques Stern. Sharing Decryption in the Context of Voting or Lotteries. In Financial Cryptography, volume 1962 of Lecture Notes in Computer Science, pages 90–104. 2000. Springer. DOI: 10.1007/3-540-45472-1_7
[GMW87]
Oded Goldreich, Silvio Micali, and Avi Wigderson. How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. In Alfred Aho, editor, 19th ACM STOC, pages 218–229. May 1987. ACM Press. DOI: 10.1145/28395.28420
[OSY21]
Claudio Orlandi, Peter Scholl, and Sophia Yakoubov. The Rise of Paillier: Homomorphic Secret Sharing and Public-Key Silent OT. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part I, volume 12696 of LNCS, pages 678–708. October 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-77870-5_24
[Pai99]
Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In EUROCRYPT, volume 1592 of Lecture Notes in Computer Science, pages 223–238. 1999. Springer. DOI: 10.1007/3-540-48910-X_16
[Ped91a]
Torben P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 129–140. 1991. Springer. DOI: 10.1007/3-540-46766-1_9
[Ped91b]
Torben P. Pedersen. A Threshold Cryptosystem without a Trusted Party (Extended Abstract) (Rump Session). In Donald W. Davies, editor, EUROCRYPT'91, volume 547 of LNCS, pages 522–526. April 1991. Springer, Heidelberg. DOI: 10.1007/3-540-46416-6_47
[RB89]
Tal Rabin and Michael Ben-Or. Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). In 21st ACM STOC, pages 73–85. May 1989. ACM Press. DOI: 10.1145/73007.73014
[RS21]
Lawrence Roy and Jaspal Singh. Large Message Homomorphic Secret Sharing from DCR and Applications. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part III, volume 12827 of LNCS, pages 687–717, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84252-9_23
[SvHA+19]
Alex Sangers, Maran van Heesch, Thomas Attema, Thijs Veugen, Mark Wiggerman, Jan Veldsink, Oscar Bloemen, and Daniël Worm. Secure Multiparty PageRank Algorithm for Collaborative Fraud Detection. In Financial Cryptography, volume 11598 of Lecture Notes in Computer Science, pages 605–623. 2019. Springer. DOI: 10.1007/978-3-030-32101-7_35
[vEDvdB+24]
Marie Beth van Egmond, Vincent Dunning, Stefan van den Berg, Thomas Rooijakkers, Alex Sangers, Ton Poppe, and Jan Veldsink. Privacy-preserving Anti-Money Laundering using Secure Multi-Party Computation. Cryptology ePrint Archive, Paper 2024/065. 2024.
[Yao86]
Andrew Chi-Chih Yao. How to Generate and Exchange Secrets (Extended Abstract). In 27th FOCS, pages 162–167. October 1986. IEEE Computer Society Press. DOI: 10.1109/SFCS.1986.25
History
Submitted: 2024-04-08
Accepted: 2024-06-03
Published: 2024-07-08
Accepted: 2024-06-03
Published: 2024-07-08
How to cite
Thomas Attema, Aron van Baarsen, Stefan van den Berg, Pedro Capitão, Vincent Dunning, and Lisa Kohl, Communication-Efficient Multi-Party Computation for RMS Programs. IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/ab0lmp-3y.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.