Document Open Access Logo

MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture

Authors T-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, Elaine Shi

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.75.pdf
  • Filesize: 0.83 MB
  • 52 pages

Document Identifiers

Author Details

T-H. Hubert Chan
  • The University of Hong Kong, Hong Kong
Kai-Min Chung
  • Academia Sinica, Taipei City, Taiwan
Wei-Kai Lin
  • Cornell University, Ithaca, NY, USA
Elaine Shi
  • Cornell University, Ithaca, NY, USA

Funding

  • Chan, T-H. Hubert: T-H. Hubert Chan was partially supported by the Hong Kong RGC under the grant 17200418.
  • Chung, Kai-Min: This research is partially supported by the Academia Sinica Career Development Award under Grant no. 23-17 and Ministry of Science and Technology, Taiwan, under Grant no. MOST 106-2628-E-001-002-MY3.
  • Lin, Wei-Kai: This work is supported by the DARPA Brandeis award.
  • Shi, Elaine: This work is supported in part by NSF CNS-1453634, an ONR YIP award, a Packard Fellowship, and an IARPA HECTOR grant under a subcontract from IBM.

Acknowledgements

We gratefully thank Xiaorui Sun for his patient and detailed explanations about the Massively Parallel Computation (MPC) model, for answering many of our technical questions, and for suggesting an idea to transform an MPC protocol without the s-sender-constraint to one that has.

Cite AsGet BibTex

T-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, and Elaine Shi. MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 75:1-75:52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.75

Abstract

Massively Parallel Computation (MPC) is a model of computation widely believed to best capture realistic parallel computing architectures such as large-scale MapReduce and Hadoop clusters. Motivated by the fact that many data analytics tasks performed on these platforms involve sensitive user data, we initiate the theoretical exploration of how to leverage MPC architectures to enable efficient, privacy-preserving computation over massive data. Clearly if a computation task does not lend itself to an efficient implementation on MPC even without security, then we cannot hope to compute it efficiently on MPC with security. We show, on the other hand, that any task that can be efficiently computed on MPC can also be securely computed with comparable efficiency. Specifically, we show the following results: - any MPC algorithm can be compiled to a communication-oblivious counterpart while asymptotically preserving its round and space complexity, where communication-obliviousness ensures that any network intermediary observing the communication patterns learn no information about the secret inputs; - assuming the existence of Fully Homomorphic Encryption with a suitable notion of compactness and other standard cryptographic assumptions, any MPC algorithm can be compiled to a secure counterpart that defends against an adversary who controls not only intermediate network routers but additionally up to 1/3 - η fraction of machines (for an arbitrarily small constant η) - moreover, this compilation preserves the round complexity tightly, and preserves the space complexity upto a multiplicative security parameter related blowup. As an initial exploration of this important direction, our work suggests new definitions and proposes novel protocols that blend algorithmic and cryptographic techniques.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
Keywords
  • massively parallel computation
  • secure multi-party computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Arash Afshar, Zhangxiang Hu, Payman Mohassel, and Mike Rosulek. How to Efficiently Evaluate RAM Programs with Malicious Security. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, pages 702-729, 2015. Google Scholar
  2. Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. ACM Transactions on Parallel Computing (TOPC), 4(4):17, 2018. Google Scholar
  3. Prabhanjan Ananth, Yu-Chi Chen, Kai-Min Chung, Huijia Lin, and Wei-Kai Lin. Delegating RAM Computations with Adaptive Soundness and Privacy. In Proceedings, Part II, of the 14th International Conference on Theory of Cryptography - Volume 9986, 2016. Google Scholar
  4. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 574-583, 2014. URL: https://doi.org/10.1145/2591796.2591805.
  5. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel Graph Connectivity in Log Diameter Rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 674-685, 2018. Google Scholar
  6. Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.00850.
  7. Gilad Asharov, T-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Bucket Oblivious Sort: A Simple Oblivious Sort. In SOSA, 2019. Google Scholar
  8. Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE. In Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, pages 483-501, 2012. Google Scholar
  9. Gilad Asharov and Yehuda Lindell. A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation. J. Cryptol., 30(1):58-151, January 2017. Google Scholar
  10. Sepehr Assadi. Simple Round Compression for Parallel Vertex Cover. CoRR, abs/1709.04599, 2017. Google Scholar
  11. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. arXiv preprint, 2017. URL: http://arxiv.org/abs/1711.03076.
  12. Sepehr Assadi and Sanjeev Khanna. Randomized Composable Coresets for Matching and Vertex Cover. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pages 3-12. ACM, 2017. Google Scholar
  13. Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs. CoRR, abs/1805.02974, 2018. URL: http://arxiv.org/abs/1805.02974.
  14. Saikrishna Badrinarayanan, Aayush Jain, Nathan Manohar, and Amit Sahai. Threshold Multi-Key FHE and Applications to Round-Optimal MPC. Cryptology ePrint Archive, Report 2018/580, 2018. Google Scholar
  15. Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and mapreduce. Proceedings of the VLDB Endowment, 5(5):454-465, 2012. Google Scholar
  16. Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii. Scalable k-means++. Proceedings of the VLDB Endowment, 5(7):622-633, 2012. Google Scholar
  17. MohammadHossein Bateni, Aditya Bhaskara, Silvio Lattanzi, and Vahab Mirrokni. Distributed balanced clustering via mapping coresets. In Advances in Neural Information Processing Systems, pages 2591-2599, 2014. Google Scholar
  18. D. Beaver, S. Micali, and P. Rogaway. The Round Complexity of Secure Protocols. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC '90, pages 503-513, New York, NY, USA, 1990. ACM. URL: https://doi.org/10.1145/100216.100287.
  19. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Richard M. Karp. Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching. CoRR, abs/1807.06701, 2018. Google Scholar
  20. Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G Harris. Exponentially Faster Massively Parallel Maximal Matching. arXiv preprint, 2019. URL: http://arxiv.org/abs/1901.03744.
  21. Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In ACM Conference on Computer and Communications Security (CCS), 2012. Google Scholar
  22. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, pages 1-10, 1988. Google Scholar
  23. Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. Threshold Cryptosystems from Threshold Fully Homomorphic Encryption. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I, pages 565-596, 2018. Google Scholar
  24. Elette Boyle, Kai-Min Chung, and Rafael Pass. Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, pages 742-762, 2015. Google Scholar
  25. Elette Boyle, Kai-Min Chung, and Rafael Pass. Oblivious Parallel RAM and Applications. In Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II, pages 175-204, 2016. Google Scholar
  26. Elette Boyle, Niv Gilboa, and Yuval Ishai. Breaking the Circuit Size Barrier for Secure Computation Under DDH. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, pages 509-539, 2016. Google Scholar
  27. Elette Boyle, Shafi Goldwasser, and Stefano Tessaro. Communication Locality in Secure Multi-party Computation: How to Run Sublinear Algorithms in a Distributed Setting. In Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, TCC'13, pages 356-376, Berlin, Heidelberg, 2013. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-36594-2_21.
  28. Zvika Brakerski, Shai Halevi, and Antigoni Polychroniadou. Four Round Secure Computation without Setup. In TCC, 2017. Google Scholar
  29. Sebastian Brandt, Manuela Fischer, and Jara Uitto. Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. CoRR, abs/1807.05374, 2018. Google Scholar
  30. R. Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In FOCS, 2001. Google Scholar
  31. Ran Canetti, Huijia Lin, Stefano Tessaro, and Vinod Vaikuntanathan. Obfuscation of Probabilistic Circuits and Applications. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography, pages 468-497, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. Google Scholar
  32. Hubert Chan, Kai-Min Chung, and Elaine Shi. On the Depth of Oblivious Parallel ORAM. In Asiacrypt, 2017. Google Scholar
  33. T.-H. Hubert Chan, Yue Guo, Wei-Kai Lin, and Elaine Shi. Cache-Oblivious and Data-Oblivious Sorting and Applications. In SODA, pages 2201-2220. SIAM, 2018. Google Scholar
  34. T.-H. Hubert Chan, Kartik Nayak, and Elaine Shi. Perfectly Secure Oblivious Parallel RAM. In Theory of Cryptography - 16th International Conference, TCC 2018, pages 636-668, 2018. Google Scholar
  35. T.-H. Hubert Chan and Elaine Shi. Circuit OPRAM: Unifying Statistically and Computationally Secure ORAMs and OPRAMs. In Theory of Cryptography - 15th International Conference, TCC, pages 72-107, 2017. Google Scholar
  36. Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The Complexity of (Delta+1) Coloring inCongested Clique, Massively Parallel Computation, and Centralized Local Computation. arXiv preprint, 2018. URL: http://arxiv.org/abs/1808.08419.
  37. Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, and Hong-Sheng Zhou. Cryptography for Parallel RAM from Indistinguishability Obfuscation. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 179-190, 2016. Google Scholar
  38. Kai-Min Chung and Luowen Qian. Adaptively Secure Garbling Schemes for Parallel Computations. In TCC, 2019. Google Scholar
  39. Geoffroy Couteau. A Note on the Communication Complexity of Multiparty Computation in the Correlated Randomness Model. In Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part II, pages 473-503, 2019. Google Scholar
  40. Artur Czumaj, Jakub Ła̧cki, Aleksander Ma̧dry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 471-484, 2018. URL: https://doi.org/10.1145/3188745.3188764.
  41. Rafael da Ponte Barbosa, Alina Ene, Huy L Nguyen, and Justin Ward. A New Framework for Distributed Submodular Maximization. In FOCS, pages 645-654, 2016. Google Scholar
  42. Ivan Damgård and Yuval Ishai. Constant-round Multiparty Computation Using a Black-box Pseudorandom Generator. In Proceedings of the 25th Annual International Conference on Advances in Cryptology, CRYPTO'05, pages 378-394, Berlin, Heidelberg, 2005. Springer-Verlag. Google Scholar
  43. Ivan Damgård and Yuval Ishai. Scalable Secure Multiparty Computation. In Proceedings of the 26th Annual International Conference on Advances in Cryptology, CRYPTO'06, pages 501-520, Berlin, Heidelberg, 2006. Springer-Verlag. URL: https://doi.org/10.1007/11818175_30.
  44. Ivan Damgård, Kasper Green Larsen, and Jesper Buus Nielsen. Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II, pages 61-84, 2019. Google Scholar
  45. Ivan Damgård, Jesper Buus Nielsen, Antigoni Polychroniadou, and Michael A. Raskin. On the Communication Required for Unconditionally Secure Multiplication. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, pages 459-488, 2016. Google Scholar
  46. Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using MapReduce. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 681-689. ACM, 2011. Google Scholar
  47. Alina Ene and Huy Nguyen. Random coordinate descent methods for minimizing decomposable submodular functions. In International Conference on Machine Learning, pages 787-795, 2015. Google Scholar
  48. Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy Impossibility Proofs for Distributed Consensus Problems. In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC '85, pages 59-70, New York, NY, USA, 1985. ACM. URL: https://doi.org/10.1145/323596.323602.
  49. Christopher Fletcher, Muhammad Naveed, Ling Ren, Elaine Shi, and Emil Stefanov. Bucket ORAM: Single Online Roundtrip, Constant Bandwidth Oblivious RAM. Cryptology ePrint Archive, Report 2015/1065, 2015. URL: https://eprint.iacr.org/2015/1065.
  50. Christopher W. Fletcher, Ling Ren, Albert Kwon, Marten van Dijk, Emil Stefanov, and Srinivas Devadas. RAW Path ORAM: A low-latency, low-area hardware ORAM controller with integrity verification. IACR Cryptology ePrint Archive, 2014:431, 2014. Google Scholar
  51. Christopher W. Fletcher, Ling Ren, Xiangyao Yu, Marten van Dijk, Omer Khan, and Srinivas Devadas. Suppressing the Oblivious RAM timing channel while making information leakage and program efficiency trade-offs. In HPCA, pages 213-224, 2014. Google Scholar
  52. Buddhima Gamlath, Sagar Kale, Slobodan Mitrović, and Ola Svensson. Weighted Matchings via Unweighted Augmentations. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.02760.
  53. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits. In IEEE Symposium on Foundations of Computer Science (FOCS), 2013. Google Scholar
  54. Sanjam Garg, Rafail Ostrovsky, and Akshayaram Srinivasan. Adaptive Garbled RAM from Laconic Oblivious Transfer. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III, pages 515-544, 2018. Google Scholar
  55. Craig Gentry. Fully homomorphic encryption using ideal lattices. In ACM symposium on Theory of computing (STOC), 2009. Google Scholar
  56. Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky, Mariana Raykova, and Daniel Wichs. Garbled RAM Revisited. In EUROCRYPT, pages 405-422, 2014. Google Scholar
  57. Craig Gentry, Shai Halevi, Mariana Raykova, and Daniel Wichs. Outsourcing Private RAM Computation. In FOCS, 2014. Google Scholar
  58. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013, pages 75-92, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  59. Mohsen Ghaffari. Massively Parallel Algorithms. URL: http://people.csail.mit.edu/ghaffari/MPA19/Notes/MPA.pdf.
  60. Mohsen Ghaffari, Themis Gouleakis, Slobodan Mitrovic, and Ronitt Rubinfeld. Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. CoRR, abs/1802.08237, 2018. Google Scholar
  61. Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrović. Improved Parallel Algorithms for Density-Based Network Clustering. In International Conference on Machine Learning, pages 2201-2210, 2019. Google Scholar
  62. Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster Algorithms for Edge Connectivity via Random 2-Out Contractions, 2019. URL: http://arxiv.org/abs/1909.00844.
  63. Mohsen Ghaffari and Jara Uitto. 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 2019, San Diego, California, USA, January 6-9, 2019, pages 1636-1653, 2019. Google Scholar
  64. O. Goldreich. Towards a theory of software protection and simulation by oblivious RAMs. In ACM Symposium on Theory of Computing (STOC), 1987. Google Scholar
  65. O. Goldreich, S. Micali, and A. Wigderson. How to play ANY mental game. In ACM symposium on Theory of computing (STOC), 1987. Google Scholar
  66. Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 1996. Google Scholar
  67. M. Goodrich. Communication-Efficient Parallel Sorting. SIAM Journal on Computing, 29(2):416-432, 1999. Google Scholar
  68. Michael T. Goodrich. Data-oblivious External-memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data. In Proceedings of the Twenty-third Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '11, pages 379-388, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1989493.1989555.
  69. Michael T. Goodrich and Michael Mitzenmacher. Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation. In International Colloquium on Automata, Languages and Programming (ICALP), pages 576-587, 2011. Google Scholar
  70. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, Searching, and Simulation in the MapReduce Framework. In Algorithms and Computation, pages 374-383, 2011. Google Scholar
  71. S. Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, and Yevgeniy Vahlis. Secure two-party computation in sublinear (amortized) time. In ACM Conference on Computer and Communications Security (CCS), 2012. Google Scholar
  72. S. Dov Gordon, Feng-Hao Liu, and Elaine Shi. Constant-Round MPC with Fairness and Guarantee of Output Delivery. In CRYPTO, pages 63-82, 2015. Google Scholar
  73. Vipul Goyal, Yanyi Liu, and Yifan Song. Communication-Efficient Unconditional MPC with Guaranteed Output Delivery. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II, pages 85-114, 2019. Google Scholar
  74. Jens Groth and Rafail Ostrovsky. Cryptography in the Multi-string Model. In CRYPTO, 2007. Google Scholar
  75. Yue Guo, Rafael Pass, and Elaine Shi. Synchronous, with a Chance of Partition Tolerance. In CRYPTO, 2019. Google Scholar
  76. Sungjin Im, Benjamin Moseley, and Xiaorui Sun. Efficient massively parallel methods for dynamic programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 798-811, 2017. URL: https://doi.org/10.1145/3055399.3055460.
  77. Sungjin Im, Benjamin Moseley, and Xiaorui Sun. Efficient Massively Parallel Methods for Dynamic Programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 798-811, New York, NY, USA, 2017. ACM. Google Scholar
  78. Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Founding Cryptography on Oblivious Transfer - Efficiently. In CRYPTO, 2008. Google Scholar
  79. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 938-948, 2010. URL: https://doi.org/10.1137/1.9781611973075.76.
  80. Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani. Fast Greedy Algorithms in MapReduce and Streaming. TOPC, 2(3):14:1-14:22, 2015. URL: https://doi.org/10.1145/2809814.
  81. Jakub Ła̧cki, Vahab S. Mirrokni, and Michal Wlodarczyk. Connected Components at Scale via Local Contractions. CoRR, abs/1807.10727, 2018. Google Scholar
  82. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, July 1982. Google Scholar
  83. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in MapReduce. In SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-located with FCRC 2011), pages 85-94, 2011. URL: https://doi.org/10.1145/1989493.1989505.
  84. Yehuda Lindell, Benny Pinkas, Nigel P. Smart, and Avishay Yanai. Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ. J. Cryptol., 32(3):1026-1069, July 2019. Google Scholar
  85. Chang Liu, Xiao Shaun Wang, Kartik Nayak, Yan Huang, and Elaine Shi. ObliVM: A programming framework for secure computation. In IEEE Symposium on Security and Privacy, 2015. Google Scholar
  86. Steve Lu and Rafail Ostrovsky. How to Garble RAM Programs. In EUROCRYPT, 2013. Google Scholar
  87. Steve Lu and Rafail Ostrovsky. Black-Box Parallel Garbled RAM. In Advances in Cryptology - CRYPTO 2017, pages 66-92, 2017. Google Scholar
  88. Alfonso Cevallos Manzano. Reducing the Share Size in Robust Secret Sharing. Master’s thesis, http://algant.eu/documents/theses/cevallos.pdf, 2011.
  89. Vahab S. Mirrokni and Morteza Zadimoghaddam. Randomized Composable Core-sets for Distributed Submodular Maximization. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 153-162, 2015. URL: https://doi.org/10.1145/2746539.2746624.
  90. Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative elements in massive data. In Advances in Neural Information Processing Systems, pages 2049-2057, 2013. Google Scholar
  91. Pratyay Mukherjee and Daniel Wichs. Two Round Multiparty Computation via Multi-key FHE. In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, pages 735-763, 2016. Google Scholar
  92. Kartik Nayak, Xiao Shaun Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft, and Elaine Shi. GraphSC: Parallel Secure Computation Made Easy. In IEEE S & P, 2015. Google Scholar
  93. Krzysztof Onak. Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. CoRR, abs/1807.08745, 2018. Google Scholar
  94. Merav Parter and Eylon Yogev. Distributed Algorithms Made Secure: A Graph Theoretic Approach. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1693-1710, 2019. Google Scholar
  95. Merav Parter and Eylon Yogev. Secure Distributed Computing Made (Nearly) Optimal. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 107-116, New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3293611.3331620.
  96. Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. CacheShuffle: A Family of Oblivious Shuffles. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), 2018. Google Scholar
  97. Vibhor Rastogi, Ashwin Machanavajjhala, Laukik Chitnis, and Anish Das Sarma. Finding connected components in map-reduce in logarithmic rounds. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, pages 50-61, 2013. Google Scholar
  98. Ling Ren, Xiangyao Yu, Christopher W. Fletcher, Marten van Dijk, and Srinivas Devadas. Design space exploration and optimization of path oblivious RAM in secure processors. In ISCA, pages 571-582, 2013. Google Scholar
  99. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation). In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA, USA, July 11-13, 2016, pages 1-12, 2016. URL: https://doi.org/10.1145/2935764.2935799.
  100. Elaine Shi, T.-H. Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious RAM with O((log N)³) Worst-Case Cost. In ASIACRYPT, pages 197-214, 2011. Google Scholar
  101. Emil Stefanov, Elaine Shi, and Dawn Song. Towards Practical Oblivious RAM. In Network and Distributed System Security Symposium (NDSS), 2012. Google Scholar
  102. Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path ORAM - an Extremely Simple Oblivious RAM Protocol. In ACM Conference on Computer and Communications Security (CCS), 2013. Google Scholar
  103. Leslie G. Valiant. A Bridging Model for Parallel Computation. Commun. ACM, 33(8):103-111, August 1990. Google Scholar
  104. Xiao Shaun Wang, T-H. Hubert Chan, and Elaine Shi. Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound. In CCS, 2015. Google Scholar
  105. Andrew Chi-Chih Yao. Protocols for Secure Computations (Extended Abstract). In IEEE symposium on Foundations of Computer Science (FOCS), 1982. Google Scholar
  106. Andrew Chi-Chih Yao. How to generate and exchange secrets. In IEEE Symposium on Foundations of Computer Science (FOCS), 1986. Google Scholar
  107. Grigory Yaroslavtsev and Adithya Vadapalli. Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under 𝓁_p-Distances. In Proceedings of the 35th International Conference on Machine Learning, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact