Communication-Efficient Multi-Party Computation for RMS Programs

Thomas Attema; Aron van Baarsen; Stefan van den Berg; Pedro Capitão; Vincent Dunning; Lisa Kohl

doi:10.62056/ab0lmp-3y

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

Thomas Attema

TNO, Applied Cryptography and Quantum Algorithms, The Hague, The Netherlands
CWI, Cryptology Group, Amsterdam, The Netherlands
thomas dot attema at tno dot nl

Aron van Baarsen

CWI, Cryptology Group, Amsterdam, The Netherlands
Leiden University, Mathematical Institute, Leiden, The Netherlands
aronvanbaarsen at gmail dot com

Stefan van den Berg

TNO, Applied Cryptography and Quantum Algorithms, The Hague, The Netherlands
stefan dot vandenberg at tno dot nl

Pedro Capitão

CWI, Cryptology Group, Amsterdam, The Netherlands
Leiden University, Mathematical Institute, Leiden, The Netherlands
pedro dot capitao at cwi dot nl

Vincent Dunning

TNO, Applied Cryptography and Quantum Algorithms, The Hague, The Netherlands
vincent dot dunning at tno dot nl

Lisa Kohl

CWI, Cryptology Group, Amsterdam, The Netherlands
lisa dot kohl at cwi dot nl

Keywords: Multi-Party Computation Active Security RMS Programs Zero Knowledge Proofs

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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[Att23]

Thomas Attema. Compressed $\varSigma$-Protocol Theory. PhD thesis, Leiden University, 2023.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[DJ00]

Ivan B. Damgård and Mads J. Jurik. Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes. Jan. 2000.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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.

Google Scholar ePrint

[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

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ab0lmp-3y

History

Submitted: 2024-04-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.

@article{CiC-1-2-10,
    author = "Attema, Thomas and van Baarsen, Aron and van den Berg, Stefan and Capitão, Pedro and Dunning, Vincent and Kohl, Lisa",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Communication-Efficient Multi-Party Computation for {RMS} Programs",
    volume = "1",
    number = "2",
    date = "2024-07-08",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/ab0lmp-3y"
}

TY - JOUR
AU - Attema, Thomas
AU - van Baarsen, Aron
AU - van den Berg, Stefan
AU - Capitão, Pedro
AU - Dunning, Vincent
AU - Kohl, Lisa
PY  - 2024
TI  - Communication-Efficient Multi-Party Computation for RMS Programs
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 2
DO  - 10.62056/ab0lmp-3y
UR  - https://doi.org/10.62056/ab0lmp-3y
AB  - <p>        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.</p><p>                 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. </p>
ER  -

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.