{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:04:55Z","timestamp":1753895095871,"version":"3.41.2"},"reference-count":42,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,4,8]],"date-time":"2024-04-08T00:00:00Z","timestamp":1712534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,6,3]]},"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 \u201cmessage passing\u201d algorithms, such as the PageRank algorithm. Their protocol's computation and communication complexity are both \n \n \n \n O<\/mml:mi>\n <\/mml:mrow>\n ~<\/mml:mo>\n <\/mml:mover>\n (<\/mml:mo>\n M<\/mml:mi>\n \u00b7<\/mml:mi>\n B<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math> instead of the \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n M<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math> complexity achieved by general-purpose MPC protocols, where \n \n M<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> denotes the number of nodes and \n \n B<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> the (average) number of incoming edges per node. On the downside, their approach achieves only a relatively weak security notion; \n \n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>-out-of-\n \n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math> malicious security with selective abort.<\/jats:p>\n 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 \n \n M<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>, 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\u00a0\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n M<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>. In our balanced protocol, we still achieve a linear communication complexity\u00a0\n \n O<\/mml:mi>\n (<\/mml:mo>\n M<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>, although with worse constants, but a significantly better computational complexity scaling with\u00a0\n \n O<\/mml:mi>\n (<\/mml:mo>\n M<\/mml:mi>\n \u00b7<\/mml:mi>\n B<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>. Additionally, our protocols achieve security with identifiable abort and can tolerate up to \n \n n<\/mml:mi>\n \u2212<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math> corruptions. <\/jats:p>","DOI":"10.62056\/ab0lmp-3y","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T15:52:04Z","timestamp":1720453924000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Communication-Efficient Multi-Party Computation for RMS Programs"],"prefix":"10.62056","author":[{"given":"Thomas","family":"Attema","sequence":"first","affiliation":[{"name":"TNO, Applied Cryptography and Quantum Algorithms","place":["The Hague, The Netherlands"]},{"name":"CWI, Cryptology Group","place":["Amsterdam, The Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aron","family":"van Baarsen","sequence":"additional","affiliation":[{"name":"CWI, Cryptology Group","place":["Amsterdam, The Netherlands"]},{"name":"Leiden University, Mathematical Institute","place":["Leiden, The Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"van den Berg","sequence":"additional","affiliation":[{"name":"TNO, Applied Cryptography and Quantum Algorithms","place":["The Hague, The Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pedro","family":"Capit\u00e3o","sequence":"additional","affiliation":[{"name":"CWI, Cryptology Group","place":["Amsterdam, The Netherlands"]},{"name":"Leiden University, Mathematical Institute","place":["Leiden, The Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Dunning","sequence":"additional","affiliation":[{"name":"TNO, Applied Cryptography and Quantum Algorithms","place":["The Hague, The Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lisa","family":"Kohl","sequence":"additional","affiliation":[{"name":"CWI, Cryptology Group","place":["Amsterdam, The Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"ref1:FOCS:Yao86","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1109\/SFCS.1986.25","article-title":"How to Generate and Exchange Secrets (Extended Abstract)","volume-title":"27th FOCS","author":"Andrew Chi-Chih Yao","year":"1986"},{"key":"ref2:STOC:GolMicWig87","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1145\/28395.28420","article-title":"How to Play any Mental Game or A Completeness Theorem for\n Protocols with Honest Majority","volume-title":"19th ACM STOC","author":"Oded Goldreich","year":"1987"},{"key":"ref3:STOC:BenGolWig88","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/62212.62213","article-title":"Completeness Theorems for Non-Cryptographic Fault-Tolerant\n Distributed Computation (Extended Abstract)","volume-title":"20th ACM STOC","author":"Michael Ben-Or","year":"1988"},{"key":"ref4:STOC:ChaCreDam88","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/62212.62214","article-title":"Multiparty Unconditionally Secure Protocols (Extended\n Abstract)","volume-title":"20th ACM STOC","author":"David Chaum","year":"1988"},{"key":"ref5:STOC:RabBen89","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/73007.73014","article-title":"Verifiable Secret Sharing and Multiparty Protocols with\n Honest Majority (Extended Abstract)","volume-title":"21st ACM STOC","author":"Tal Rabin","year":"1989"},{"key":"ref6:C:BoyGilIsh16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/978-3-662-53018-4_19","article-title":"Breaking the Circuit Size Barrier for Secure Computation\n Under DDH","volume-title":"CRYPTO\u00a02016, Part\u00a0I","volume":"9814","author":"Elette Boyle","year":"2016"},{"key":"ref7:AFOPRT21","series-title":"CCS '21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1145\/3460120.3484560","article-title":"Secure Graph Analysis at Scale","volume-title":"Proceedings of the 2021 ACM SIGSAC Conference on Computer\n and Communications Security","author":"Toshinori Araki","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450384544"},{"key":"ref8:DBLP:conf\/fc\/SangersHAVWVBW19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-030-32101-7_35","article-title":"Secure Multiparty PageRank Algorithm for Collaborative Fraud\n Detection","volume-title":"Financial Cryptography","volume":"11598","author":"Alex Sangers","year":"2019"},{"key":"ref9:RSA:CozSmaAla21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-75539-3_1","article-title":"Secure Fast Evaluation of Iterative Methods: With an\n Application to Secure PageRank","volume-title":"CT-RSA\u00a02021","volume":"12704","author":"Daniele Cozzo","year":"2021"},{"article-title":"Privacy-preserving Anti-Money Laundering using Secure\n Multi-Party Computation","year":"2024","author":"Marie Beth van Egmond","key":"ref10:EDBe"},{"key":"ref11:DBLP:conf\/eurocrypt\/BendlinDOZ11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-20465-4_11","article-title":"Semi-homomorphic Encryption and Multiparty Computation","volume-title":"EUROCRYPT","volume":"6632","author":"Rikke Bendlin","year":"2011"},{"key":"ref12:DBLP:conf\/crypto\/DamgardPSZ12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-642-32009-5_38","article-title":"Multiparty Computation from Somewhat Homomorphic\n Encryption","volume-title":"CRYPTO","volume":"7417","author":"Ivan Damg\u00e5rd","year":"2012"},{"key":"ref13:CDN01","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/3-540-44987-6_18","article-title":"Multiparty Computation from Threshold Homomorphic\n Encryption","volume-title":"EUROCRYPT","volume":"2045","author":"Ronald Cramer","year":"2001"},{"key":"ref14:DBLP:conf\/eurocrypt\/BootleCCGP16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-662-49896-5_12","article-title":"Efficient Zero-Knowledge Arguments for Arithmetic Circuits\n in the Discrete Log Setting","volume-title":"EUROCRYPT (2)","volume":"9666","author":"Jonathan Bootle","year":"2016"},{"key":"ref15:DBLP:conf\/sp\/BunzBBPWM18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1109\/SP.2018.00020","article-title":"Bulletproofs: Short Proofs for Confidential Transactions and\n More","volume-title":"IEEE Symposium on Security and Privacy","author":"Benedikt B\u00fcnz","year":"2018"},{"key":"ref16:DBLP:conf\/tcc\/Ben-SassonCS16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-662-53644-5_2","article-title":"Interactive Oracle Proofs","volume-title":"TCC (B2)","volume":"9986","author":"Eli Ben-Sasson","year":"2016"},{"key":"ref17:AC20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-030-56877-1_18","article-title":"Compressed $\\varSigma$-Protocol Theory and Practical\n Application to Plug & Play Secure Algorithmics","volume-title":"CRYPTO (3)","volume":"12172","author":"Thomas Attema","year":"2020"},{"key":"ref18:ACC+22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-031-22318-1_7","article-title":"Vector Commitments over Rings and Compressed\n $\\varSigma$-Protocols","volume-title":"TCC (1)","volume":"13747","author":"Thomas Attema","year":"2022"},{"article-title":"Compressed $\\varSigma$-Protocol Theory","year":"2023","author":"Thomas Attema","key":"ref19:Att23"},{"key":"ref20:C:DHRW16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-662-53015-3_4","article-title":"Spooky Encryption and Its Applications","volume-title":"CRYPTO\u00a02016, Part\u00a0III","volume":"9816","author":"Yevgeniy Dodis","year":"2016"},{"key":"ref21:CCS:BCGIO17","doi-asserted-by":"publisher","first-page":"2105","DOI":"10.1145\/3133956.3134107","article-title":"Homomorphic Secret Sharing: Optimizations and Applications","volume-title":"ACM CCS 2017","author":"Elette Boyle","year":"2017"},{"key":"ref22:FGJS17","isbn-type":"print","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/978-3-319-68637-0_23","article-title":"Homomorphic Secret Sharing from Paillier Encryption","volume-title":"Provable Security","author":"Nelly Fazio","year":"2017","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319686370"},{"key":"ref23:EC:OrlSchYak21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1007\/978-3-030-77870-5_24","article-title":"The Rise of Paillier: Homomorphic Secret Sharing and\n Public-Key Silent OT","volume-title":"EUROCRYPT\u00a02021, Part\u00a0I","volume":"12696","author":"Claudio Orlandi","year":"2021"},{"key":"ref24:C:RoySin21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/978-3-030-84252-9_23","article-title":"Large Message Homomorphic Secret Sharing from DCR and\n Applications","volume-title":"CRYPTO\u00a02021, Part\u00a0III","volume":"12827","author":"Lawrence Roy","year":"2021"},{"key":"ref25:EC:BoyKohSch19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-17656-3_1","article-title":"Homomorphic Secret Sharing from Lattices Without FHE","volume-title":"EUROCRYPT\u00a02019, Part\u00a0II","volume":"11477","author":"Elette Boyle","year":"2019"},{"key":"ref26:chillotti2022scooby","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1007\/978-3-031-14791-3_24","article-title":"Scooby: Improved Multi-party Homomorphic Secret Sharing\n Based on FHE","volume-title":"SCN","volume":"13409","author":"Ilaria Chillotti","year":"2022"},{"key":"ref27:BP98","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","article-title":"The Anatomy of a Large-Scale Hypertextual Web Search\n Engine","volume":"30","author":"Sergey Brin","year":"1998","journal-title":"Comput. Networks"},{"key":"ref28:Pai99","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","article-title":"Public-Key Cryptosystems Based on Composite Degree\n Residuosity Classes","volume-title":"EUROCRYPT","volume":"1592","author":"Pascal Paillier","year":"1999"},{"key":"ref29:DJ00","doi-asserted-by":"publisher","DOI":"10.7146\/brics.v7i5.20133","article-title":"Efficient Protocols based on Probabilistic Encryption using\n Composite Degree Residue Classes","volume":"7","author":"Ivan B. Damg\u00e5rd","year":"2000","journal-title":"BRICS Report Series"},{"key":"ref30:FPS00","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/3-540-45472-1_7","article-title":"Sharing Decryption in the Context of Voting or Lotteries","volume-title":"Financial Cryptography","volume":"1962","author":"Pierre-Alain Fouque","year":"2000"},{"key":"ref31:DJ01","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-44586-2_9","article-title":"A Generalisation, a Simplification and Some Applications of\n Paillier's Probabilistic Public-Key System","volume-title":"Public Key Cryptography","volume":"1992","author":"Ivan Damg\u00e5rd","year":"2001"},{"key":"ref32:ElGamal","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","article-title":"A public key cryptosystem and a signature scheme based on\n discrete logarithms","volume":"31","author":"Taher ElGamal","year":"1985","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref33:EC:CraGenSch97","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/3-540-69053-0_9","article-title":"A Secure and Optimally Efficient Multi-Authority Election\n Scheme","volume-title":"EUROCRYPT'97","volume":"1233","author":"Ronald Cramer","year":"1997"},{"key":"ref34:DH76","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"Whitfield Diffie","year":"1976","journal-title":"IEEE Transactions on Information Theory"},{"key":"ref35:EC:Pedersen91b","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1007\/3-540-46416-6_47","article-title":"A Threshold Cryptosystem without a Trusted Party (Extended\n Abstract) (Rump Session)","volume-title":"EUROCRYPT'91","volume":"547","author":"Torben P. Pedersen","year":"1991"},{"key":"ref36:Ped91","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/3-540-46766-1_9","article-title":"Non-Interactive and Information-Theoretic Secure Verifiable\n Secret Sharing","volume-title":"CRYPTO","volume":"576","author":"Torben P. Pedersen","year":"1991"},{"key":"ref37:AC:CasLagTuc18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/978-3-030-03329-3_25","article-title":"Practical Fully Secure Unrestricted Inner Product Functional\n Encryption Modulo p","volume-title":"ASIACRYPT\u00a02018, Part\u00a0II","volume":"11273","author":"Guilhem Castagnos","year":"2018"},{"key":"ref38:RSA:CasLag15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-319-16715-2_26","article-title":"Linearly Homomorphic Encryption from $\\mathsf{DDH}$","volume-title":"CT-RSA\u00a02015","volume":"9048","author":"Guilhem Castagnos","year":"2015"},{"key":"ref39:BDO23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/978-3-031-38557-5_20","article-title":"Secure Multiparty Computation from Threshold Encryption\n Based on Class Groups","volume-title":"CRYPTO (1)","volume":"14081","author":"Lennart Braun","year":"2023"},{"key":"ref40:PKC:CCLST20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-030-45388-6_10","article-title":"Bandwidth-Efficient Threshold EC-DSA","volume-title":"PKC\u00a02020, Part\u00a0II","volume":"12111","author":"Guilhem Castagnos","year":"2020"},{"key":"ref41:C:AttCraKoh21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/978-3-030-84245-1_19","article-title":"A Compressed $\\varSigma$-Protocol Theory for Lattices","volume-title":"CRYPTO\u00a02021, Part\u00a0II","volume":"12826","author":"Thomas Attema","year":"2021"},{"key":"ref42:PLS19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-030-17253-4_12","article-title":"Short Discrete Log Proofs for FHE and Ring-LWE\n Ciphertexts","volume-title":"Public Key Cryptography (1)","volume":"11442","author":"Ra\u00ebl del Pino","year":"2019"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:26:54Z","timestamp":1733866014000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/2\/10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":42,"URL":"https:\/\/doi.org\/10.62056\/ab0lmp-3y","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-04-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-2-29"}}