{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T05:03:21Z","timestamp":1764133401508,"version":"3.40.3"},"publisher-location":"Cham","reference-count":73,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030643775"},{"type":"electronic","value":"9783030643782"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-64378-2_14","type":"book-chapter","created":{"date-parts":[[2020,12,12]],"date-time":"2020-12-12T15:02:46Z","timestamp":1607785366000},"page":"379-409","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Secure Massively Parallel Computation for Dishonest Majority"],"prefix":"10.1007","author":[{"given":"Rex","family":"Fernando","sequence":"first","affiliation":[]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[]},{"given":"Yanyi","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,12,9]]},"reference":[{"issue":"4","key":"14_CR1","first-page":"17","volume":"4","author":"KJ Ahn","year":"2018","unstructured":"Ahn, K.J., Guha, S.: Access to data and number of iterations: dual primal algorithms for maximum matching under resource constraints. ACM Trans. Parallel Comput. (TOPC) 4(4), 17 (2018)","journal-title":"ACM Trans. Parallel Comput. (TOPC)"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Ananth, P., Chen, Y., Chung, K., Lin, H., Lin, W.: Delegating RAM computations with adaptive soundness and privacy. In: Theory of Cryptography - 14th International Conference, TCC, pp. 3\u201330 (2016)","DOI":"10.1007\/978-3-662-53644-5_1"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: Symposium on Theory of Computing, STOC, pp. 574\u2013583 (2014)","DOI":"10.1145\/2591796.2591805"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Andoni, A., Song, Z., Stein, C., Wang, Z., Zhong, P.: Parallel graph connectivity in log diameter rounds. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 674\u2013685 (2018)","DOI":"10.1109\/FOCS.2018.00070"},{"key":"14_CR5","unstructured":"Andoni, A., Stein, C., Zhong, P.: Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In: 46th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 14:1\u201314:16 (2019)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-29011-4_29","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"G Asharov","year":"2012","unstructured":"Asharov, G., Jain, A., L\u00f3pez-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483\u2013501. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_29"},{"key":"14_CR7","unstructured":"Assadi, S.: Simple round compression for parallel vertex cover. CoRR abs\/1709.04599 (2017)"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Assadi, S., Bateni, M., Bernstein, A., Mirrokni, V.S., Stein, C.: Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1616\u20131635 (2019)","DOI":"10.1137\/1.9781611975482.98"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S.: Randomized composable coresets for matching and vertex cover. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pp. 3\u201312 (2017)","DOI":"10.1145\/3087556.3087581"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Assadi, S., Sun, X., Weinstein, O.: Massively parallel algorithms for finding well-connected components in sparse graphs. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 461\u2013470 (2019)","DOI":"10.1145\/3293611.3331596"},{"key":"14_CR11","first-page":"580","volume":"2018","author":"S Badrinarayanan","year":"2018","unstructured":"Badrinarayanan, S., Jain, A., Manohar, N., Sahai, A.: Threshold multi-key FHE and applications to round-optimal MPC. IACR Cryptol. ePrint Arch. 2018, 580 (2018)","journal-title":"IACR Cryptol. ePrint Arch."},{"issue":"5","key":"14_CR12","doi-asserted-by":"publisher","first-page":"454","DOI":"10.14778\/2140436.2140442","volume":"5","author":"B Bahmani","year":"2012","unstructured":"Bahmani, B., Kumar, R., Vassilvitskii, S.: Densest subgraph in streaming and mapreduce. Proc. VLDB Endowment 5(5), 454\u2013465 (2012)","journal-title":"Proc. VLDB Endowment"},{"issue":"7","key":"14_CR13","doi-asserted-by":"publisher","first-page":"622","DOI":"10.14778\/2180912.2180915","volume":"5","author":"B Bahmani","year":"2012","unstructured":"Bahmani, B., Moseley, B., Vattani, A., Kumar, R., Vassilvitskii, S.: Scalable k-means++. Proc. VLDB Endowment 5(7), 622\u2013633 (2012)","journal-title":"Proc. VLDB Endowment"},{"issue":"2","key":"14_CR14","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/2160158.2160159","volume":"59","author":"B Barak","year":"2012","unstructured":"Barak, B., et al.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6:1\u20136:48 (2012)","journal-title":"J. ACM"},{"key":"14_CR15","unstructured":"Bateni, M., Bhaskara, A., Lattanzi, S., Mirrokni, V.: Distributed balanced clustering via mapping coresets. In: Advances in Neural Information Processing Systems, pp. 2591\u20132599 (2014)"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., et al.: Massively parallel computation of matching and MIS in sparse graphs. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 481\u2013490 (2019)","DOI":"10.1145\/3293611.3331609"},{"key":"14_CR17","unstructured":"Behnezhad, S., Derakhshan, M., Hajiaghayi, M., Karp, R.M.: Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. CoRR abs\/1807.06701 (2018)"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Hajiaghayi, M., Harris, D.G.: Exponentially faster massively parallel maximal matching. In: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1637\u20131649 (2019)","DOI":"10.1109\/FOCS.2019.00096"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"14_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-319-96884-1_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"D Boneh","year":"2018","unstructured":"Boneh, D., et al.: Threshold cryptosystems from threshold fully homomorphic encryption. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 565\u2013596. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_19"},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-642-42045-0_15","volume-title":"Advances in Cryptology - ASIACRYPT 2013","author":"D Boneh","year":"2013","unstructured":"Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 280\u2013300. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-42045-0_15"},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/978-3-662-48000-7_36","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"E Boyle","year":"2015","unstructured":"Boyle, E., Chung, K.-M., Pass, R.: Large-scale secure computation: multi-party computation for (parallel) RAM programs. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 742\u2013762. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_36"},{"key":"14_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-662-49099-0_7","volume-title":"Theory of Cryptography","author":"E Boyle","year":"2016","unstructured":"Boyle, E., Chung, K.-M., Pass, R.: Oblivious parallel RAM and applications. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 175\u2013204. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_7"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-642-54631-0_29","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"E Boyle","year":"2014","unstructured":"Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501\u2013519. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54631-0_29"},{"key":"14_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-662-53018-4_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"Z Brakerski","year":"2016","unstructured":"Brakerski, Z., Perlman, R.: Lattice-based fully dynamic multi-key FHE with short ciphertexts. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 190\u2013213. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53018-4_8"},{"key":"14_CR26","unstructured":"Chan, T.H., Chung, K., Lin, W., Shi, E.: MPC for MPC: secure computation on a massively parallel computing architecture. In: 11th Innovations in Theoretical Computer Science Conference, ITCS, pp. 75:1\u201375:52 (2020)"},{"key":"14_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/978-3-319-70694-8_20","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2017","author":"T-HH Chan","year":"2017","unstructured":"Chan, T.-H.H., Chung, K.-M., Shi, E.: On the depth of oblivious parallel RAM. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 567\u2013597. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70694-8_20"},{"key":"14_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1007\/978-3-030-03810-6_23","volume-title":"Theory of Cryptography","author":"T-HH Chan","year":"2018","unstructured":"Chan, T.-H.H., Nayak, K., Shi, E.: Perfectly secure oblivious parallel RAM. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11240, pp. 636\u2013668. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03810-6_23"},{"key":"14_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/978-3-319-70503-3_3","volume-title":"Theory of Cryptography","author":"T-H Hubert Chan","year":"2017","unstructured":"Hubert Chan, T.-H., Shi, E.: Circuit OPRAM: unifying statistically and computationally secure ORAMs and OPRAMs. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 72\u2013107. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_3"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Chang, Y., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Y.: The complexity of ($$\\Delta $$+1) coloring in congested clique, massively parallel computation, and centralized local computation. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 471\u2013480 (2019)","DOI":"10.1145\/3293611.3331607"},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chow, S.S.M., Chung, K., Lai, R.W.F., Lin, W., Zhou, H.: Cryptography for parallel RAM from indistinguishability obfuscation. In: ACM Conference on Innovations in Theoretical Computer Science, ITCS, pp. 179\u2013190 (2016)","DOI":"10.1145\/2840728.2840769"},{"key":"14_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-030-36033-7_11","volume-title":"Theory of Cryptography","author":"K-M Chung","year":"2019","unstructured":"Chung, K.-M., Qian, L.: Adaptively secure garbling schemes for parallel computations. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11892, pp. 285\u2013310. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36033-7_11"},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"Czumaj, A., \u0141a\u0327cki, J., Ma\u0327dry, A., Mitrovi\u0107, S., Onak, K., Sankowski, P.: Round compression for parallel matching algorithms. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 471\u2013484 (2018)","DOI":"10.1145\/3188745.3188764"},{"key":"14_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-662-53015-3_4","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"Y Dodis","year":"2016","unstructured":"Dodis, Y., Halevi, S., Rothblum, R.D., Wichs, D.: Spooky encryption and its applications. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 93\u2013122. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53015-3_4"},{"key":"14_CR35","doi-asserted-by":"crossref","unstructured":"Ene, A., Im, S., Moseley, B.: Fast clustering using mapreduce. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 681\u2013689. ACM (2011)","DOI":"10.1145\/2020408.2020515"},{"key":"14_CR36","unstructured":"Ene, A., Nguyen, H.: Random coordinate descent methods for minimizing decomposable submodular functions. In: International Conference on Machine Learning, pp. 787\u2013795 (2015)"},{"key":"14_CR37","doi-asserted-by":"crossref","unstructured":"Fernando, R., Komargodski, I., Liu, Y., Shi, E.: Secure massively parallel computation for dishonest majority. IACR Cryptol. ePrint Arch. 2017. https:\/\/eprint.iacr.org\/2020\/1157","DOI":"10.1007\/978-3-030-64378-2_14"},{"key":"14_CR38","doi-asserted-by":"crossref","unstructured":"Gamlath, B., Kale, S., Mitrovic, S., Svensson, O.: Weighted matchings via unweighted augmentations. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 491\u2013500 (2019)","DOI":"10.1145\/3293611.3331603"},{"key":"14_CR39","doi-asserted-by":"crossref","unstructured":"Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 40\u201349 (2013)","DOI":"10.1109\/FOCS.2013.13"},{"key":"14_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"C Gentry","year":"2013","unstructured":"Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75\u201392. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_5"},{"key":"14_CR41","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Gouleakis, T., Konrad, C., Mitrovic, S., Rubinfeld, R.: Improved massively parallel computation algorithms for mis, matching, and vertex cover. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 129\u2013138 (2018)","DOI":"10.1145\/3212734.3212743"},{"key":"14_CR42","unstructured":"Ghaffari, M., Lattanzi, S., Mitrovi\u0107, S.: Improved parallel algorithms for density-based network clustering. In: International Conference on Machine Learning, pp. 2201\u20132210 (2019)"},{"key":"14_CR43","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Uitto, J.: Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1636\u20131653 (2019)","DOI":"10.1137\/1.9781611975482.99"},{"key":"14_CR44","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: 25th Annual Symposium on Foundations of Computer Science, FOCS, pp. 464\u2013479 (1984)"},{"key":"14_CR45","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"key":"14_CR46","doi-asserted-by":"crossref","unstructured":"Hub\u00e1\u010dek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: ITCS, pp. 163\u2013172 (2015)","DOI":"10.1145\/2688073.2688105"},{"key":"14_CR47","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B., Sun, X.: Efficient massively parallel methods for dynamic programming. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 798\u2013811 (2017)","DOI":"10.1145\/3055399.3055460"},{"key":"14_CR48","first-page":"257","volume":"2017","author":"A Jain","year":"2017","unstructured":"Jain, A., Rasmussen, P.M.R., Sahai, A.: Threshold fully homomorphic encryption. IACR Cryptol. ePrint Arch. 2017, 257 (2017)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"14_CR49","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 938\u2013948 (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"14_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/3-540-39200-9_36","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2003","author":"J Katz","year":"2003","unstructured":"Katz, J., Ostrovsky, R., Smith, A.: Round efficiency of multi-party computation with a dishonest majority. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 578\u2013595. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-39200-9_36"},{"key":"14_CR51","doi-asserted-by":"crossref","unstructured":"Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS, pp. 669\u2013684 (2013)","DOI":"10.1145\/2508859.2516668"},{"issue":"3","key":"14_CR52","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/2809814","volume":"2","author":"R Kumar","year":"2015","unstructured":"Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in mapreduce and streaming. TOPC 2(3), 14:1\u201314:22 (2015)","journal-title":"TOPC"},{"key":"14_CR53","unstructured":"\u0141a\u0327cki, J., Mirrokni, V.S., Wlodarczyk, M.: Connected components at scale via local contractions. CoRR abs\/1807.10727 (2018)"},{"key":"14_CR54","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Moseley, B., Suri, S., Vassilvitskii, S.: Filtering: a method for solving graph problems in mapreduce. In: SPAA, pp. 85\u201394 (2011)","DOI":"10.1145\/1989493.1989505"},{"key":"14_CR55","doi-asserted-by":"crossref","unstructured":"L\u00f3pez-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, pp. 1219\u20131234 (2012)","DOI":"10.1145\/2213977.2214086"},{"key":"14_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-319-63715-0_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"S Lu","year":"2017","unstructured":"Lu, S., Ostrovsky, R.: Black-box parallel garbled RAM. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 66\u201392. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_3"},{"key":"14_CR57","doi-asserted-by":"crossref","unstructured":"Mirrokni, V.S., Zadimoghaddam, M.: Randomized composable core-sets for distributed submodular maximization. In: STOC, pp. 153\u2013162 (2015)","DOI":"10.1145\/2746539.2746624"},{"key":"14_CR58","unstructured":"Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular maximization: Identifying representative elements in massive data. In: Advances in Neural Information Processing Systems, pp. 2049\u20132057 (2013)"},{"key":"14_CR59","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/978-3-662-49896-5_26","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"P Mukherjee","year":"2016","unstructured":"Mukherjee, P., Wichs, D.: Two round multiparty computation via multi-key FHE. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 735\u2013763. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_26"},{"key":"14_CR60","doi-asserted-by":"crossref","unstructured":"Mukherjee, P., Wichs, D.: Two round multiparty computation via multi-key FHE. In: EUROCRYPT, pp. 735\u2013763 (2016)","DOI":"10.1007\/978-3-662-49896-5_26"},{"key":"14_CR61","doi-asserted-by":"crossref","unstructured":"Nayak, K., Wang, X.S., Ioannidis, S., Weinsberg, U., Taft, N., Shi, E.: GraphSC: parallel secure computation made easy. In: IEEE S & P (2015)","DOI":"10.1109\/SP.2015.30"},{"key":"14_CR62","unstructured":"Onak, K.: Round compression for parallel graph algorithms in strongly sublinear space. CoRR abs\/1807.08745 (2018)"},{"key":"14_CR63","doi-asserted-by":"crossref","unstructured":"Parter, M., Yogev, E.: Distributed algorithms made secure: a graph theoretic approach. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1693\u20131710 (2019)","DOI":"10.1137\/1.9781611975482.102"},{"key":"14_CR64","doi-asserted-by":"crossref","unstructured":"Parter, M., Yogev, E.: Secure distributed computing made (nearly) optimal, pp. 107\u2013116. PODC\u20192019 (2019)","DOI":"10.1145\/3293611.3331620"},{"key":"14_CR65","doi-asserted-by":"crossref","unstructured":"Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Babai, L. (ed.) STOC, pp. 232\u2013241. ACM (2004)","DOI":"10.1145\/1007352.1007393"},{"key":"14_CR66","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-662-53644-5_9","volume-title":"Theory of Cryptography","author":"C Peikert","year":"2016","unstructured":"Peikert, C., Shiehian, S.: Multi-key FHE from LWE, revisited. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 217\u2013238. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_9"},{"key":"14_CR67","doi-asserted-by":"crossref","unstructured":"da Ponte Barbosa, R., Ene, A., Nguyen, H.L., Ward, J.: A new framework for distributed submodular maximization. In: FOCS, pp. 645\u2013654 (2016)","DOI":"10.1109\/FOCS.2016.74"},{"key":"14_CR68","doi-asserted-by":"crossref","unstructured":"Rastogi, V., Machanavajjhala, A., Chitnis, L., Sarma, A.D.: Finding connected components in map-reduce in logarithmic rounds. In: 29th IEEE International Conference on Data Engineering, ICDE, pp. 50\u201361 (2013)","DOI":"10.1109\/ICDE.2013.6544813"},{"issue":"6","key":"14_CR69","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1\u201334:40 (2009)","journal-title":"J. ACM"},{"key":"14_CR70","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Vassilvitskii, S., Wang, J.R.: Shuffles and circuits: (on lower bounds for modern parallel computation). In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pp. 1\u201312 (2016)","DOI":"10.1145\/2935764.2935799"},{"key":"14_CR71","doi-asserted-by":"crossref","unstructured":"Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Symposium on Theory of Computing, STOC, pp. 475\u2013484 (2014)","DOI":"10.1145\/2591796.2591825"},{"key":"14_CR72","doi-asserted-by":"crossref","unstructured":"Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475\u2013484. ACM (2014)","DOI":"10.1145\/2591796.2591825"},{"key":"14_CR73","unstructured":"Yaroslavtsev, G., Vadapalli, A.: Massively parallel algorithms and hardness for single-linkage clustering under $$\\ell _p$$-distances. In: Proceedings of the 35th International Conference on Machine Learning (2018)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-64378-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T01:04:55Z","timestamp":1702343095000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-64378-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030643775","9783030643782"],"references-count":73,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-64378-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"9 December 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 November 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 November 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"websubrev","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"167","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"71","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"17","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic this event was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}