Document Open Access Logo

Oblivious Parallel Tight Compaction

Authors Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, Elaine Shi

PDF
Thumbnail PDF

File

LIPIcs.ITC.2020.11.pdf
  • Filesize: 0.64 MB
  • 23 pages

Document Identifiers

Author Details

Gilad Asharov
  • Bar-Ilan University, Ramat-Gan, Israel
Ilan Komargodski
  • NTT Research, East Palo Alto, CA, USA
Wei-Kai Lin
  • Cornell University, Ithaca, NY, USA
Enoch Peserico
  • Università degli Studi di Padova, Italy
Elaine Shi
  • Cornell University, Ithaca, NY, USA

Funding

  • Lin, Wei-Kai: Wei-Kai Lin supported by NSF CNS-1453634, an ONR YIP award, a Packard Fellowship, and a DARPA Brandeis grant.
  • Shi, Elaine: Elaine Shi supported by NSF CNS-1453634, an ONR YIP award, a Packard Fellowship, and a DARPA Brandeis grant.

Acknowledgements

Wei-Kai thanks Jyun-Jie Liao for reminding the similarity between superconcentrators and oblivious tight compaction.

Cite AsGet BibTex

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. Oblivious Parallel Tight Compaction. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITC.2020.11

Abstract

In tight compaction one is given an array of balls some of which are marked 0 and the rest are marked 1. The output of the procedure is an array that contains all of the original balls except that now the 0-balls appear before the 1-balls. In other words, tight compaction is equivalent to sorting the array according to 1-bit keys (not necessarily maintaining order within same-key balls). Tight compaction is not only an important algorithmic task by itself, but its oblivious version has also played a key role in recent constructions of oblivious RAM compilers. We present an oblivious deterministic algorithm for tight compaction such that for input arrays of n balls requires O(n) total work and O(log n) depth. Our algorithm is in the Exclusive-Read-Exclusive-Write Parallel-RAM model (i.e., EREW PRAM, the most restrictive PRAM model), and importantly we achieve asymptotical optimality in both total work and depth. To the best of our knowledge no earlier work, even when allowing randomization, can achieve optimality in both total work and depth.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
Keywords
  • Oblivious tight compaction
  • parallel oblivious RAM
  • EREW PRAM

Metrics

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

Related Versions

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1974. Google Scholar
  2. Miklós Ajtai, János Komlós, and Endre Szemerédi. An O(n log n) sorting network. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC, pages 1-9, 1983. Google Scholar
  3. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. OptORAMa: optimal oblivious RAM. In Advances in Cryptology - EUROCRYPT, 2020. Google Scholar
  4. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. Oblivious parallel tight compaction. Cryptology ePrint Archive, Report 2020/125, 2020. URL: https://eprint.iacr.org/2020/125.
  5. Hannah Bast and Torben Hagerup. Fast parallel space allocation, estimation, and integer sorting. Inf. Comput., 123(1):72-110, November 1995. Google Scholar
  6. Elette Boyle, Kai-Min Chung, and Rafael Pass. Oblivious parallel RAM and applications. In Theory of Cryptography - 13th International Conference, TCC, pages 175-204, 2016. Google Scholar
  7. Elette Boyle and Moni Naor. Is there an oblivious RAM lower bound? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS, pages 357-368, 2016. Google Scholar
  8. Hubert Chan, Kai-Min Chung, and Elaine Shi. On the depth of oblivious parallel oram. In Asiacrypt, 2017. Google Scholar
  9. 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
  10. 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
  11. Richard Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770-785, 1988. Google Scholar
  12. S. Cook, C. Dwork, and R. Reischuk. Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes. SIAM Journal on Computing, 15(1):87-97, February 1986. Google Scholar
  13. Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi. Lower bounds for external memory integer sorting via network coding. In STOC, 2019. Google Scholar
  14. Ofer Gabber and Zvi Galil. Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci., 22(3):407-420, 1981. Google Scholar
  15. Oded Goldreich. Towards a theory of software protection and simulation by oblivious rams. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC, pages 182-194, 1987. Google Scholar
  16. Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. J. ACM, 1996. Google Scholar
  17. Michael T. Goodrich and Michael Mitzenmacher. Privacy-preserving access of outsourced data via oblivious RAM simulation. In Automata, Languages and Programming - 38th International Colloquium, ICALP, pages 576-587, 2011. Google Scholar
  18. P. Hall. On Representatives of Subsets. Journal of the London Mathematical Society, s1-10(1):26-30, 1935. Google Scholar
  19. Shuji Jimbo and Akira Maruoka. Expanders obtained from affine transformations. Combinatorica, 7(4):343-355, 1987. Google Scholar
  20. Donald E. Knuth. The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., 1998. Google Scholar
  21. Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. On the (in)security of hash-based oblivious RAM and a new balancing scheme. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 143-156, 2012. Google Scholar
  22. Tom Leighton, Yuan Ma, and Torsten Suel. On probabilistic networks for selection, merging, and sorting. In Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '95, pages 106-118. ACM, 1995. Google Scholar
  23. Wei-Kai Lin, Elaine Shi, and Tiancheng Xie. Can we overcome the n log n barrier for oblivious sorting? In SODA, 2019. Google Scholar
  24. Grigorii Aleksandrovich Margulis. Explicit constructions of concentrators. Problemy Peredachi Informatsii, 9(4):71-80, 1973. Google Scholar
  25. John C. Mitchell and Joe Zimmerman. Data-oblivious data structures. In 31st International Symposium on Theoretical Aspects of Computer Science STACS, pages 554-565, 2014. Google Scholar
  26. Enoch Peserico. Deterministic oblivious distribution (and tight compaction) in linear time. CoRR, abs/1807.06719, 2018. URL: http://arxiv.org/abs/1807.06719.
  27. Nicholas Pippenger. Self-routing superconcentrators. J. Comput. Syst. Sci., 52(1):53-60, 1996. Google Scholar
  28. P. Ragde. The parallel simplicity of compaction and chaining. In Proceedings of the Seventeenth International Colloquium on Automata, Languages and Programming, pages 744-751, Berlin, Heidelberg, 1990. Springer-Verlag. Google Scholar
  29. Leslie G. Valiant. Graph-theoretic properties in computational complexity. J. Comput. Syst. Sci., 13(3):278-285, December 1976. 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