Secure massively parallel computation for dishonest majority. (English) Zbl 07496586
Pass, Rafael (ed.) et al., Theory of cryptography. 18th international conference, TCC 2020, Durham, NC, USA, November 16–19, 2020. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12551, 379-409 (2020).
Summary: This work concerns secure protocols in the massively parallel computation (MPC) model, which is one of the most widely-accepted models for capturing the challenges of writing protocols for the types of parallel computing clusters which have become commonplace today (MapReduce, Hadoop, Spark, etc.). Recently, the work of Chan et al. (ITCS ’20) initiated this study, giving a way to compile any MPC protocol into a secure one in the common random string model, achieving the standard secure multi-party computation definition of security with up to 1/3 of the parties being corrupt.
We are interested in achieving security for much more than 1/3 corruptions. To that end, we give two compilers for MPC protocols, which assume a simple public-key infrastructure, and achieve semi-honest security for all-but-one corruptions. Our first compiler assumes hardness of the learning-with-errors (LWE) problem, and works for any MPC protocol with “short” output – that is, where the output of the protocol can fit into the storage space of one machine, for instance protocols that output a trained machine learning model. Our second compiler works for any MPC protocol (even ones with a long output, such as sorting) but assumes, in addition to LWE, indistinguishability obfuscation and a circular secure variant of threshold FHE. Both protocols allow the attacker to choose corrupted parties based on the trusted setup, an improvement over Chan et al., whose protocol requires that the CRS is chosen independently of the attacker’s choices.
For the entire collection see [Zbl 1482.94008].
We are interested in achieving security for much more than 1/3 corruptions. To that end, we give two compilers for MPC protocols, which assume a simple public-key infrastructure, and achieve semi-honest security for all-but-one corruptions. Our first compiler assumes hardness of the learning-with-errors (LWE) problem, and works for any MPC protocol with “short” output – that is, where the output of the protocol can fit into the storage space of one machine, for instance protocols that output a trained machine learning model. Our second compiler works for any MPC protocol (even ones with a long output, such as sorting) but assumes, in addition to LWE, indistinguishability obfuscation and a circular secure variant of threshold FHE. Both protocols allow the attacker to choose corrupted parties based on the trusted setup, an improvement over Chan et al., whose protocol requires that the CRS is chosen independently of the attacker’s choices.
For the entire collection see [Zbl 1482.94008].
MSC:
| 68P25 | Data encryption (aspects in computer science) |
| 68Mxx | Computer system organization |
| 94A60 | Cryptography |
References:
| [1] | Ahn, KJ; 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 |
| [2] | 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-30 (2016) · Zbl 1397.94045 |
| [3] | Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: Symposium on Theory of Computing, STOC, pp. 574-583 (2014) · Zbl 1315.05133 |
| [4] | 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-685 (2018) |
| [5] | 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-14:16 (2019) · Zbl 07561507 |
| [6] | Asharov, G.; Jain, A.; López-Alt, A.; Tromer, E.; Vaikuntanathan, V.; Wichs, D.; Pointcheval, D.; Johansson, T., Multiparty computation with low communication, computation and interaction via threshold FHE, Advances in Cryptology - EUROCRYPT 2012, 483-501, 2012, Heidelberg: Springer, Heidelberg · Zbl 1297.94042 · doi:10.1007/978-3-642-29011-4_29 |
| [7] | Assadi, S.: Simple round compression for parallel vertex cover. CoRR abs/1709.04599 (2017) |
| [8] | 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-1635 (2019) · Zbl 1431.68143 |
| [9] | 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-12 (2017) |
| [10] | 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-470 (2019) · Zbl 1542.68123 |
| [11] | 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 |
| [12] | Bahmani, B.; Kumar, R.; Vassilvitskii, S., Densest subgraph in streaming and mapreduce, Proc. VLDB Endowment, 5, 5, 454-465, 2012 · doi:10.14778/2140436.2140442 |
| [13] | Bahmani, B.; Moseley, B.; Vattani, A.; Kumar, R.; Vassilvitskii, S., Scalable k-means++, Proc. VLDB Endowment, 5, 7, 622-633, 2012 · doi:10.14778/2180912.2180915 |
| [14] | Barak, B., On the (im)possibility of obfuscating programs, J. ACM, 59, 2, 6:1-6:48, 2012 · Zbl 1281.68118 · doi:10.1145/2160158.2160159 |
| [15] | Bateni, M., Bhaskara, A., Lattanzi, S., Mirrokni, V.: Distributed balanced clustering via mapping coresets. In: Advances in Neural Information Processing Systems, pp. 2591-2599 (2014) |
| [16] | 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-490 (2019) · Zbl 1542.68125 |
| [17] | 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) |
| [18] | 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-1649 (2019) |
| [19] | 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-10 (1988) |
| [20] | Boneh, D.; Shacham, H.; Boldyreva, A., Threshold cryptosystems from threshold fully homomorphic encryption, Advances in Cryptology - CRYPTO 2018, 565-596, 2018, Cham: Springer, Cham · Zbl 1444.94047 · doi:10.1007/978-3-319-96884-1_19 |
| [21] | Boneh, D.; Waters, B.; Sako, K.; Sarkar, P., Constrained pseudorandom functions and their applications, Advances in Cryptology - ASIACRYPT 2013, 280-300, 2013, Heidelberg: Springer, Heidelberg · Zbl 1314.94057 · doi:10.1007/978-3-642-42045-0_15 |
| [22] | Boyle, E.; Chung, K-M; Pass, R.; Gennaro, R.; Robshaw, M., Large-scale secure computation: multi-party computation for (parallel) RAM programs, Advances in Cryptology - CRYPTO 2015, 742-762, 2015, Heidelberg: Springer, Heidelberg · Zbl 1352.94027 · doi:10.1007/978-3-662-48000-7_36 |
| [23] | Boyle, E.; Chung, K-M; Pass, R.; Kushilevitz, E.; Malkin, T., Oblivious parallel RAM and applications, Theory of Cryptography, 175-204, 2016, Heidelberg: Springer, Heidelberg · Zbl 1377.94039 · doi:10.1007/978-3-662-49099-0_7 |
| [24] | Boyle, E.; Goldwasser, S.; Ivan, I.; Krawczyk, H., Functional signatures and pseudorandom functions, Public-Key Cryptography - PKC 2014, 501-519, 2014, Heidelberg: Springer, Heidelberg · Zbl 1290.94145 · doi:10.1007/978-3-642-54631-0_29 |
| [25] | Brakerski, Z.; Perlman, R.; Robshaw, M.; Katz, J., Lattice-based fully dynamic multi-key FHE with short ciphertexts, Advances in Cryptology - CRYPTO 2016, 190-213, 2016, Heidelberg: Springer, Heidelberg · Zbl 1351.94029 · doi:10.1007/978-3-662-53018-4_8 |
| [26] | 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-75:52 (2020) · Zbl 07650423 |
| [27] | Chan, T-HH; Chung, K-M; Shi, E.; Takagi, T.; Peyrin, T., On the depth of oblivious parallel RAM, Advances in Cryptology - ASIACRYPT 2017, 567-597, 2017, Cham: Springer, Cham · Zbl 1420.94047 · doi:10.1007/978-3-319-70694-8_20 |
| [28] | Chan, T-HH; Nayak, K.; Shi, E.; Beimel, A.; Dziembowski, S., Perfectly secure oblivious parallel RAM, Theory of Cryptography, 636-668, 2018, Cham: Springer, Cham · Zbl 1430.94063 · doi:10.1007/978-3-030-03810-6_23 |
| [29] | Hubert Chan, T-H; Shi, E.; Kalai, Y.; Reyzin, L., Circuit OPRAM: unifying statistically and computationally secure ORAMs and OPRAMs, Theory of Cryptography, 72-107, 2017, Cham: Springer, Cham · Zbl 1416.68015 · doi:10.1007/978-3-319-70503-3_3 |
| [30] | 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-480 (2019) · Zbl 1530.68198 |
| [31] | 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-190 (2016) · Zbl 1334.94068 |
| [32] | Chung, K-M; Qian, L.; Hofheinz, D.; Rosen, A., Adaptively secure garbling schemes for parallel computations, Theory of Cryptography, 285-310, 2019, Cham: Springer, Cham · Zbl 1455.94142 · doi:10.1007/978-3-030-36033-7_11 |
| [33] | Czumaj, A., Ła̧cki, J., Ma̧dry, A., Mitrović, 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-484 (2018) · Zbl 1427.68354 |
| [34] | Dodis, Y.; Halevi, S.; Rothblum, RD; Wichs, D.; Robshaw, M.; Katz, J., Spooky encryption and its applications, Advances in Cryptology - CRYPTO 2016, 93-122, 2016, Heidelberg: Springer, Heidelberg · Zbl 1406.94045 · doi:10.1007/978-3-662-53015-3_4 |
| [35] | 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-689. ACM (2011) |
| [36] | Ene, A., Nguyen, H.: Random coordinate descent methods for minimizing decomposable submodular functions. In: International Conference on Machine Learning, pp. 787-795 (2015) |
| [37] | 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 |
| [38] | Gamlath, B., Kale, S., Mitrovic, S., Svensson, O.: Weighted matchings via unweighted augmentations. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 491-500 (2019) · Zbl 1542.68146 |
| [39] | 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-49 (2013) |
| [40] | Gentry, C.; Sahai, A.; Waters, B.; Canetti, R.; Garay, JA, Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based, Advances in Cryptology - CRYPTO 2013, 75-92, 2013, Heidelberg: Springer, Heidelberg · Zbl 1310.94148 · doi:10.1007/978-3-642-40041-4_5 |
| [41] | 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-138 (2018) · Zbl 1428.68376 |
| [42] | Ghaffari, M., Lattanzi, S., Mitrović, S.: Improved parallel algorithms for density-based network clustering. In: International Conference on Machine Learning, pp. 2201-2210 (2019) |
| [43] | 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-1653 (2019) · Zbl 1431.68133 |
| [44] | 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-479 (1984) |
| [45] | 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-229 (1987) |
| [46] | Hubáček, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: ITCS, pp. 163-172 (2015) · Zbl 1364.68201 |
| [47] | 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-811 (2017) · Zbl 1370.68316 |
| [48] | Jain, A.; Rasmussen, PMR; Sahai, A., Threshold fully homomorphic encryption, IACR Cryptol. ePrint Arch., 2017, 257, 2017 |
| [49] | 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-948 (2010) · Zbl 1288.68247 |
| [50] | Katz, J.; Ostrovsky, R.; Smith, A.; Biham, E., Round efficiency of multi-party computation with a dishonest majority, Advances in Cryptology — EUROCRYPT 2003, 578-595, 2003, Heidelberg: Springer, Heidelberg · Zbl 1038.94539 · doi:10.1007/3-540-39200-9_36 |
| [51] | 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-684 (2013) |
| [52] | Kumar, R.; Moseley, B.; Vassilvitskii, S.; Vattani, A., Fast greedy algorithms in mapreduce and streaming, TOPC, 2, 3, 14:1-14:22, 2015 · doi:10.1145/2809814 |
| [53] | Ła̧cki, J., Mirrokni, V.S., Wlodarczyk, M.: Connected components at scale via local contractions. CoRR abs/1807.10727 (2018) |
| [54] | Lattanzi, S., Moseley, B., Suri, S., Vassilvitskii, S.: Filtering: a method for solving graph problems in mapreduce. In: SPAA, pp. 85-94 (2011) |
| [55] | López-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-1234 (2012) · Zbl 1286.68114 |
| [56] | Lu, S.; Ostrovsky, R.; Katz, J.; Shacham, H., Black-box parallel garbled RAM, Advances in Cryptology - CRYPTO 2017, 66-92, 2017, Cham: Springer, Cham · Zbl 1409.94893 · doi:10.1007/978-3-319-63715-0_3 |
| [57] | Mirrokni, V.S., Zadimoghaddam, M.: Randomized composable core-sets for distributed submodular maximization. In: STOC, pp. 153-162 (2015) · Zbl 1321.68361 |
| [58] | 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-2057 (2013) |
| [59] | Mukherjee, P.; Wichs, D.; Fischlin, M.; Coron, J-S, Two round multiparty computation via multi-key FHE, Advances in Cryptology - EUROCRYPT 2016, 735-763, 2016, Heidelberg: Springer, Heidelberg · Zbl 1351.94060 · doi:10.1007/978-3-662-49896-5_26 |
| [60] | Mukherjee, P., Wichs, D.: Two round multiparty computation via multi-key FHE. In: EUROCRYPT, pp. 735-763 (2016) · Zbl 1351.94060 |
| [61] | Nayak, K., Wang, X.S., Ioannidis, S., Weinsberg, U., Taft, N., Shi, E.: GraphSC: parallel secure computation made easy. In: IEEE S & P (2015) |
| [62] | Onak, K.: Round compression for parallel graph algorithms in strongly sublinear space. CoRR abs/1807.08745 (2018) |
| [63] | 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-1710 (2019) · Zbl 1432.68559 |
| [64] | Parter, M., Yogev, E.: Secure distributed computing made (nearly) optimal, pp. 107-116. PODC’2019 (2019) · Zbl 07298662 |
| [65] | Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: Babai, L. (ed.) STOC, pp. 232-241. ACM (2004) · Zbl 1192.68077 |
| [66] | Peikert, C.; Shiehian, S.; Hirt, M.; Smith, A., Multi-key FHE from LWE, revisited, Theory of Cryptography, 217-238, 2016, Heidelberg: Springer, Heidelberg · Zbl 1397.94093 · doi:10.1007/978-3-662-53644-5_9 |
| [67] | da Ponte Barbosa, R., Ene, A., Nguyen, H.L., Ward, J.: A new framework for distributed submodular maximization. In: FOCS, pp. 645-654 (2016) |
| [68] | 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-61 (2013) |
| [69] | Regev, O., On lattices, learning with errors, random linear codes, and cryptography, J. ACM, 56, 6, 34:1-34:40, 2009 · Zbl 1325.68101 · doi:10.1145/1568318.1568324 |
| [70] | 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-12 (2016) |
| [71] | Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Symposium on Theory of Computing, STOC, pp. 475-484 (2014) · Zbl 1315.94102 |
| [72] | Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475-484. ACM (2014) · Zbl 1315.94102 |
| [73] | 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) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
