{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T05:44:15Z","timestamp":1781329455970,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T00:00:00Z","timestamp":1636675200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,11,12]]},"DOI":"10.1145\/3460120.3484560","type":"proceedings-article","created":{"date-parts":[[2021,11,13]],"date-time":"2021-11-13T12:05:34Z","timestamp":1636805134000},"page":"610-629","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":54,"title":["Secure Graph Analysis at Scale"],"prefix":"10.1145","author":[{"given":"Toshinori","family":"Araki","sequence":"first","affiliation":[{"name":"NEC Corporation, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Furukawa","sequence":"additional","affiliation":[{"name":"NEC Corporation, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kazuma","family":"Ohara","sequence":"additional","affiliation":[{"name":"AIST, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Pinkas","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hanan","family":"Rosemarin","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hikaru","family":"Tsuchida","sequence":"additional","affiliation":[{"name":"NEC Corporation, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,11,13]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1","article-title":"An O(n log n) sorting network","author":"Ajtai M.","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di, An O(n log n) sorting network,\" in STOC, 1983, pp. 1--9.","journal-title":"STOC"},{"key":"e_1_3_2_1_2_1","volume-title":"SP","author":"Araki T.","year":"2017","unstructured":"T. Araki, A. Barak, J. Furukawa, T. Lichter, Y. Lindell, A. Nof, K. Ohara, and A. Watzman, ?Optimized honest-majority mpc for malicious adversaries - breaking the 1 billion-gate per second barrier,\" in IEEE Symposium on Security and Privacy, SP, 2017."},{"key":"e_1_3_2_1_3_1","first-page":"843","volume-title":"?Optimized honest-majority MPC for malicious adversaries - breaking the 1 billion-gate per second barrier,\" in 2017 IEEE Symposium on Security and Privacy","author":"Araki T.","year":"2017","unstructured":"T. Araki, A. Barak, J. Furukawa, T. Lichter, Y. Lindell, A. Nof, K. Ohara, A. Watzman, and O. Weinstein, ?Optimized honest-majority MPC for malicious adversaries - breaking the 1 billion-gate per second barrier,\" in 2017 IEEE Symposium on Security and Privacy, 2017, pp. 843--862."},{"key":"e_1_3_2_1_4_1","first-page":"805","article-title":"High-throughput semi-honest secure three-party computation with an honest majority","author":"Araki T.","year":"2016","unstructured":"T. Araki, J. Furukawa, Y. Lindell, A. Nof, and K. Ohara, \"High-throughput semi-honest secure three-party computation with an honest majority,\" in ACM Conference on Computer and Communications Security CCS, 2016, pp. 805--817.","journal-title":"ACM Conference on Computer and Communications Security CCS"},{"key":"e_1_3_2_1_5_1","first-page":"695","volume-title":"CCS","author":"Barak A.","year":"2018","unstructured":"A. Barak, M. Hirt, L. Koskas, and Y. Lindell, \"An end-to-end system for large scale P2P mpc-as-a-service and low-bandwidth MPC for weak participants,\" in ACM Conference on Computer and Communications Security, CCS, 2018, pp. 695--712."},{"key":"e_1_3_2_1_6_1","first-page":"1","article-title":"Completeness theorems for noncryptographic fault-tolerant distributed computation (extended abstract)","author":"Ben-Or M.","year":"1988","unstructured":"M. Ben-Or, S. Goldwasser, and A. Wigderson, \"Completeness theorems for noncryptographic fault-tolerant distributed computation (extended abstract),\" in STOC, 1988, pp. 1--10.","journal-title":"STOC"},{"key":"e_1_3_2_1_7_1","first-page":"308","volume-title":"ACM","author":"Blelloch G. E.","year":"2012","unstructured":"G. E. Blelloch, J. T. Fineman, and J. Shun, \"Greedy sequential maximal independent set and matching are parallel on average,\" in SPAA. ACM, 2012, pp. 308--317."},{"key":"e_1_3_2_1_8_1","first-page":"869","volume-title":"CCS","author":"Boyle E.","year":"2019","unstructured":"E. Boyle, N. Gilboa, Y. Ishai, and A. Nof, \"Practical fully secure three-party computation via sublinear distributed zero-knowledge proofs,\" in ACM Conference on Computer and Communications Security, CCS, 2019, pp. 869--886."},{"key":"e_1_3_2_1_9_1","first-page":"1573","volume-title":"CCS","author":"Byali M.","year":"2019","unstructured":"M. Byali, C. Hazay, A. Patra, and S. Singla, \"Fast actively secure five-party computation with security beyond abort,\" in ACM Conference on Computer and Communications Security, CCS, 2019, pp. 1573--1590."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_3_2_1_11_1","first-page":"35","volume-title":"Secure computation with fixed-point numbers,\" in International Conference on Financial Cryptography and Data Security","author":"Catrina O.","year":"2010","unstructured":"O. Catrina and A. Saxena, \"Secure computation with fixed-point numbers,\" in International Conference on Financial Cryptography and Data Security. Springer, 2010, pp. 35--50."},{"key":"e_1_3_2_1_12_1","first-page":"11","article-title":"Multiparty unconditionally secure protocols (extended abstract)","author":"Chaum D.","year":"1988","unstructured":"D. Chaum, C. Cr\u00e9peau, and I. Damg\u00e5rd, \"Multiparty unconditionally secure protocols (extended abstract),\" in STOC, 1988, pp. 11--19.","journal-title":"STOC"},{"key":"e_1_3_2_1_13_1","first-page":"34","article-title":"Fast large-scale honest-majority MPC for malicious adversaries","volume":"2018","author":"Chida K.","year":"2018","unstructured":"K. Chida, D. Genkin, K. Hamada, D. Ikarashi, R. Kikuchi, Y. Lindell, and A. Nof, \"Fast large-scale honest-majority MPC for malicious adversaries,\" in CRYPTO 2018, 2018, pp. 34--64.","journal-title":"CRYPTO"},{"key":"e_1_3_2_1_14_1","unstructured":"K. Chida K. Hamada D. Ikarashi R. Kikuchi N. Kiribuchi and B. Pinkas \"An efficient secure three-party sorting protocol with an honest majority \" Cryptology ePrint Archive Report 2019\/695 2019 https:\/\/eprint.iacr.org\/2019\/695."},{"key":"e_1_3_2_1_15_1","first-page":"30","article-title":"Adaptively secure MPC with sublinear communication complexity","author":"Cohen R.","year":"2019","unstructured":"R. Cohen, abhi shelat, and D. Wichs, \"Adaptively secure MPC with sublinear communication complexity,\" in CRYPTO, 2019, pp. 30--60.","journal-title":"CRYPTO"},{"key":"e_1_3_2_1_16_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, 3rd ed. The MIT Press, 2009.","edition":"3"},{"key":"e_1_3_2_1_17_1","first-page":"1102","article-title":"New primitives for actively-secure MPC over rings with applications to private machine learning,\" in IEEE Symposium on Security and Privacy","author":"Damg\u00e5rd I.","year":"2019","unstructured":"I. Damg\u00e5rd, D. Escudero, T. K. Frederiksen, M. Keller, P. Scholl, and N. Volgushev, \"New primitives for actively-secure MPC over rings with applications to private machine learning,\" in IEEE Symposium on Security and Privacy, SP, 2019, pp. 1102--1120.","journal-title":"SP"},{"key":"e_1_3_2_1_18_1","first-page":"2152","volume-title":"Tight analysis of parallel randomized greedy MIS,\" in SODA","author":"Fischer M.","year":"2018","unstructured":"M. Fischer and A. Noever, \"Tight analysis of parallel randomized greedy MIS,\" in SODA. SIAM, 2018, pp. 2152--2160."},{"key":"e_1_3_2_1_19_1","first-page":"1557","article-title":"Two-thirds honest-majority MPC for malicious adversaries at almost the cost of semi-honest","author":"Furukawa J.","year":"2019","unstructured":"J. Furukawa and Y. Lindell, \"Two-thirds honest-majority MPC for malicious adversaries at almost the cost of semi-honest,\" in ACM Conference on Computer and Communications Security CCS, 2019, pp. 1557--1571.","journal-title":"ACM Conference on Computer and Communications Security CCS"},{"key":"e_1_3_2_1_20_1","first-page":"225","article-title":"High-throughput secure three-party computation for malicious adversaries and an honest majority","volume":"2017","author":"Furukawa J.","year":"2017","unstructured":"J. Furukawa, Y. Lindell, A. Nof, and O. Weinstein, \"High-throughput secure three-party computation for malicious adversaries and an honest majority,\" in EUROCRYPT 2017, 2017, pp. 225--255.","journal-title":"EUROCRYPT"},{"key":"e_1_3_2_1_21_1","first-page":"218","article-title":"How to play any mental game or A completeness theorem for protocols with honest majority","author":"Goldreich O.","year":"1987","unstructured":"O. Goldreich, S. Micali, and A. Wigderson, \"How to play any mental game or A completeness theorem for protocols with honest majority,\" in STOC, 1987, pp. 218--229.","journal-title":"STOC"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049701"},{"key":"e_1_3_2_1_23_1","first-page":"684","article-title":"Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in o(n log n) time,\" in STOC, D. B. Shmoys","author":"Goodrich M. T.","year":"2014","unstructured":"--, \"Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in o(n log n) time,\" in STOC, D. B. Shmoys, Ed., 2014, pp. 684--693.","journal-title":"Ed."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03332-3_3"},{"key":"e_1_3_2_1_25_1","first-page":"85","article-title":"Communication-efficient unconditional MPC with guaranteed output delivery","author":"Goyal V.","year":"2019","unstructured":"V. Goyal, Y. Liu, and Y. Song, \"Communication-efficient unconditional MPC with guaranteed output delivery,\" in CRYPTO 2019, pp. 85--114.","journal-title":"CRYPTO"},{"key":"e_1_3_2_1_26_1","first-page":"202","volume-title":"Practically efficient multi-party sorting protocols from comparison sort algorithms,\" in ICISC, ser. LNCS","author":"Hamada K.","year":"2012","unstructured":"K. Hamada, R. Kikuchi, D. Ikarashi, K. Chida, and K. Takahashi, \"Practically efficient multi-party sorting protocols from comparison sort algorithms,\" in ICISC, ser. LNCS, vol. 7839. Springer, 2012, pp. 202--216."},{"key":"e_1_3_2_1_27_1","first-page":"97","article-title":"Covert security with public verifiability: Faster, leaner, and simpler","volume":"2019","author":"Hong C.","year":"2019","unstructured":"C. Hong, J. Katz, V. Kolesnikov,W. Lu, and X.Wang, \"Covert security with public verifiability: Faster, leaner, and simpler,\" in EUROCRYPT 2019, 2019, pp. 97--121.","journal-title":"EUROCRYPT"},{"key":"e_1_3_2_1_28_1","volume-title":"A design and an implementation of super-high-speed multi-party sorting:the day when multi-party computation reached scripting languages,\" in Computer Security Symposium","author":"Ikarashi D.","year":"2017","unstructured":"D. Ikarashi, K. Hamada, R. Kikuchi, and K. Chida, \"A design and an implementation of super-high-speed multi-party sorting:the day when multi-party computation reached scripting languages,\" in Computer Security Symposium 2017."},{"key":"e_1_3_2_1_29_1","first-page":"830","article-title":"MASCOT: faster malicious arithmetic secure computation with oblivious transfer","author":"Keller M.","year":"2016","unstructured":"M. Keller, E. Orsini, and P. Scholl, \"MASCOT: faster malicious arithmetic secure computation with oblivious transfer,\" in ACM Conference on Computer and Communications Security, 2016, pp. 830--842.","journal-title":"ACM Conference on Computer and Communications Security"},{"key":"e_1_3_2_1_30_1","first-page":"549","volume-title":"Eds.","author":"Keller M.","year":"2013","unstructured":"M. Keller, P. Scholl, and N. P. Smart, \"An architecture for practical actively secure MPC with dishonest majority,\" in ACM Conference on Computer and Communications Security, CCS, A. Sadeghi, V. D. Gligor, and M. Yung, Eds., 2013, pp. 549--560."},{"key":"e_1_3_2_1_31_1","volume-title":"The art of computer programming","author":"Knuth D. E.","year":"1998","unstructured":"D. E. Knuth, The art of computer programming, , Volume III, 2nd Edition. Addison-Wesley, 1998.","edition":"2"},{"key":"e_1_3_2_1_32_1","first-page":"495","volume-title":"Dishonest majority multi-party computation for binary circuits,\" in CRYPTO","author":"Larraia E.","year":"2014","unstructured":"E. Larraia, E. Orsini, and N. P. Smart, \"Dishonest majority multi-party computation for binary circuits,\" in CRYPTO 2014, J. A. Garay and R. Gennaro, Eds., pp. 495--512."},{"key":"e_1_3_2_1_33_1","first-page":"262","article-title":"Round-efficient oblivious database manipulation","author":"Laur S.","year":"2011","unstructured":"S. Laur, J. Willemson, and B. Zhang, \"Round-efficient oblivious database manipulation,\" in ISC, 2011, pp. 262--277.","journal-title":"ISC"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_6"},{"key":"e_1_3_2_1_35_1","first-page":"259","volume-title":"CCS","author":"Lindell Y.","year":"2017","unstructured":"Y. Lindell and A. Nof, \"A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority,\" in ACM Conference on Computer and Communications Security, CCS, 2017, pp. 259--276."},{"key":"e_1_3_2_1_36_1","first-page":"359","article-title":"Oblivm: A programming framework for secure computation,\" in 2015 IEEE Symposium on Security and Privacy","author":"Liu C.","year":"2015","unstructured":"C. Liu, X. S. Wang, K. Nayak, Y. Huang, and E. Shi, \"Oblivm: A programming framework for secure computation,\" in 2015 IEEE Symposium on Security and Privacy, SP, 2015, pp. 359--376.","journal-title":"SP"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_3_2_1_38_1","first-page":"1","volume-title":"ACM","author":"Luby M.","year":"1985","unstructured":"M. Luby, \"A simple parallel algorithm for the maximal independent set problem,\" in STOC. ACM, 1985, pp. 1--10."},{"key":"e_1_3_2_1_39_1","first-page":"135","article-title":"Pregel: a system for large-scale graph processing","author":"Malewicz G.","year":"2010","unstructured":"G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski, \"Pregel: a system for large-scale graph processing,\" in ACM SIGMOD, 2010, pp. 135--146.","journal-title":"ACM SIGMOD"},{"key":"e_1_3_2_1_40_1","first-page":"490","volume-title":"ACM","author":"Mazloom S.","year":"2018","unstructured":"S. Mazloom and S. D. Gordon, \"Secure computation with differentially private access patterns,\" in ACM Conference on Computer and Communications Security. ACM, 2018, pp. 490--507."},{"key":"e_1_3_2_1_41_1","first-page":"2487","volume-title":"Secure parallel computation on national scale volumes of data,\" in USENIX Security Symposium","author":"Mazloom S.","year":"2020","unstructured":"S. Mazloom, P. H. Le, S. Ranellucci, and S. D. Gordon, \"Secure parallel computation on national scale volumes of data,\" in USENIX Security Symposium. USENIX Association, 2020, pp. 2487--2504."},{"key":"e_1_3_2_1_42_1","first-page":"35","volume-title":"CCS","author":"Mohassel P.","year":"2018","unstructured":"P. Mohassel and P. Rindal, \"Aby3: A mixed protocol framework for machine learning,\" in ACM Conference on Computer and Communications Security, CCS, 2018, pp. 35--52."},{"key":"e_1_3_2_1_43_1","volume-title":"Loopy belief propagation for approximate inference: An empirical study,\" arXiv preprint arXiv:1301.6725","author":"Murphy K.","year":"2013","unstructured":"K. Murphy, Y.Weiss, and M. I. Jordan, \"Loopy belief propagation for approximate inference: An empirical study,\" arXiv preprint arXiv:1301.6725, 2013."},{"key":"e_1_3_2_1_44_1","first-page":"377","article-title":"Graphsc: Parallel secure computation made easy,\" in 2015 IEEE Symposium on Security and Privacy","author":"Nayak K.","year":"2015","unstructured":"K. Nayak, X. S. Wang, S. Ioannidis, U. Weinsberg, N. Taft, and E. Shi, \"Graphsc: Parallel secure computation made easy,\" in 2015 IEEE Symposium on Security and Privacy, SP, 2015, pp. 377--394.","journal-title":"SP"},{"key":"e_1_3_2_1_45_1","first-page":"801","volume-title":"ACM","author":"Nikolaenko V.","year":"2013","unstructured":"V. Nikolaenko, S. Ioannidis, U.Weinsberg, M. Joye, N. Taft, and D. Boneh, \"Privacypreserving matrix factorization,\" in ACM CCS. ACM, 2013, pp. 801--812."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"M. Paterson \"Progress in selection \" in Algorithm Theory - SWAT 1996 pp. 368--379.","DOI":"10.1007\/3-540-61422-2_146"},{"key":"e_1_3_2_1_47_1","first-page":"73","article-title":"Verifiable secret sharing and multiparty protocols with honest majority","author":"Rabin T.","year":"1989","unstructured":"T. Rabin and M. Ben-Or, \"Verifiable secret sharing and multiparty protocols with honest majority,\" in STOC, 1989, pp. 73--85.","journal-title":"STOC"},{"issue":"2","key":"e_1_3_2_1_48_1","first-page":"3","article-title":"The ubiquity of large graphs and surprising challenges of graph processing: extended survey","volume":"29","author":"Sahu S.","year":"2020","unstructured":"S. Sahu, A. Mhedhbi, S. Salihoglu, J. Lin, and M. T. \u00d6zsu, \"The ubiquity of large graphs and surprising challenges of graph processing: extended survey,\" VLDB J., vol. 29, no. 2--3, pp. 595--618, 2020.","journal-title":"VLDB J."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32101-7_35"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39884-1_23"},{"key":"e_1_3_2_1_51_1","first-page":"162","article-title":"How to generate and exchange secrets (extended abstract)","author":"Yao A. C.","year":"1986","unstructured":"A. C. Yao, \"How to generate and exchange secrets (extended abstract),\" in FOCS, 1986, pp. 162--167.","journal-title":"FOCS"},{"key":"e_1_3_2_1_52_1","first-page":"236","volume-title":"Understanding belief propagation and its generalizations,\" Exploring artificial intelligence in the new millennium","author":"Yedidia J. S.","year":"2003","unstructured":"J. S. Yedidia, W. T. Freeman, and Y. Weiss, \"Understanding belief propagation and its generalizations,\" Exploring artificial intelligence in the new millennium, vol. 8, pp. 236--239, 2003."},{"key":"e_1_3_2_1_53_1","first-page":"240","volume-title":"ser. Lecture Notes in Computer Science","author":"Zhang B.","year":"2011","unstructured":"B. Zhang, \"Generic constant-round oblivious sorting algorithm for MPC,\" in ProvSec, ser. Lecture Notes in Computer Science, vol. 6980. Springer, 2011, pp. 240--256."}],"event":{"name":"CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security","location":"Virtual Event Republic of Korea","acronym":"CCS '21","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460120.3484560","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460120.3484560","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T20:54:25Z","timestamp":1763499265000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460120.3484560"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,12]]},"references-count":53,"alternative-id":["10.1145\/3460120.3484560","10.1145\/3460120"],"URL":"https:\/\/doi.org\/10.1145\/3460120.3484560","relation":{},"subject":[],"published":{"date-parts":[[2021,11,12]]},"assertion":[{"value":"2021-11-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}