Document Open Access Logo

Secure Merge with O(n log log n) Secure Operations

Authors Brett Hemenway Falk , Rafail Ostrovsky

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.7.pdf
  • Filesize: 0.93 MB
  • 29 pages

Document Identifiers

Author Details

Brett Hemenway Falk
  • University of Pennsylvania, Philadelphia, PA, USA
Rafail Ostrovsky
  • University of California, Los Angeles, CA, USA

Funding

Work done while consulting at Stealth Software Inc.

Cite AsGet BibTex

Brett Hemenway Falk and Rafail Ostrovsky. Secure Merge with O(n log log n) Secure Operations. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 7:1-7:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.7

Abstract

Data-oblivious algorithms are a key component of many secure computation protocols. In this work, we show that advances in secure multiparty shuffling algorithms can be used to increase the efficiency of several key cryptographic tools. The key observation is that many secure computation protocols rely heavily on secure shuffles. The best data-oblivious shuffling algorithms require O(n log n), operations, but in the two-party or multiparty setting, secure shuffling can be achieved with only O(n) communication. Leveraging the efficiency of secure multiparty shuffling, we give novel, information-theoretic algorithms that improve the efficiency of securely sorting sparse lists, secure stable compaction, and securely merging two sorted lists. Securely sorting private lists is a key component of many larger secure computation protocols. The best data-oblivious sorting algorithms for sorting a list of n elements require O(n log n) comparisons. Using black-box access to a linear-communication secure shuffle, we give a secure algorithm for sorting a list of length n with t ≪ n nonzero elements with communication O(t log² n + n), which beats the best oblivious algorithms when the number of nonzero elements, t, satisfies t < n/log² n. Secure compaction is the problem of removing dummy elements from a list, and is essentially equivalent to sorting on 1-bit keys. The best oblivious compaction algorithms run in O(n)-time, but they are unstable, i.e., the order of the remaining elements is not preserved. Using black-box access to a linear-communication secure shuffle, we give an information-theoretic stable compaction algorithm with only O(n) communication. Our main result is a novel secure merge protocol. The best previous algorithms for securely merging two sorted lists into a sorted whole required O(n log n) secure operations. Using black-box access to an O(n)-communication secure shuffle, we give the first multi-party secure merge algorithm that requires only O(n log log n) communication. Our algorithm takes as input n secret-shared values, and outputs a secret-sharing of the sorted list. All our algorithms are generic, i.e., they can be implemented using generic secure computations techniques and make black-box access to a secure shuffle. Our techniques extend naturally to the multiparty situation (with a constant number of parties) as well as to handle malicious adversaries without changing the asymptotic efficiency. These algorithm have applications to securely computing database joins and order statistics on private data as well as multiparty Oblivious RAM protocols.

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
Keywords
  • Secure computation
  • Data-oblivious algorithms
  • Sorting
  • Merging
  • Shuffling
  • Compaction

Metrics

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

Related Versions

References

  1. Gagan Aggarwal, Nina Mishra, and Benny Pinkas. Secure computation of the median (and other elements of specified ranks). Journal of cryptology, 23(3):373-401, 2010. Google Scholar
  2. M. Ajtai, J. Komlós, and E. Szemerédi. Sorting in c log(n) steps. Combinatorica, 3:1-19, 1983. Google Scholar
  3. S.W. Al-Haj Baddar and K.E. Batcher. The AKS sorting network. In Designing sorting networks. Springer, 2011. URL: https://doi.org/10.1007/978-1-4614-1851-1_11.
  4. Nikolaos Alexopoulos, Aggelos Kiayias, Riivo Talviste, and Thomas Zacharias. MCMix: Anonymous messaging via secure multiparty computation. In 26th USENIX Security Symposium USENIX Security 17), pages 1217-1234, 2017. Google Scholar
  5. Kazuyuki Amano and Akira Maruoka. On optimal merging networks. In International Symposium on Mathematical Foundations of Computer Science, pages 152-161. Springer, 2003. Google Scholar
  6. Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, and Elaine Shi. OptORAMa: Optimal oblivious RAM. In EUROCRYPT, 2020. Google Scholar
  7. Yonatan Aumann and Yehuda Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. In Theory of Cryptography Conference, pages 137-156. Springer, 2007. Google Scholar
  8. Sherenaz W Al-Haj Baddar and Kenneth E Batcher. The 0/1-principle. In Designing Sorting Networks, pages 19-25. Springer, 2011. Google Scholar
  9. Kenneth E. Batcher. Sorting networks and their applications. In Proceedings of the April 30-May 2, 1968, spring joint computer conference, pages 307-314. ACM, 1968. Google Scholar
  10. Johes Bater, Gregory Elliott, Craig Eggen, Satyender Goel, Abel Kho, and Jennie Rogers. SMCQL: secure querying for federated databases. Proceedings of the VLDB Endowment, 10(6):673-684, 2017. Google Scholar
  11. Stephanie Bayer and Jens Groth. Efficient zero-knowledge argument for correctness of a shuffle. In EUROCRYPT, pages 263-280. Springer, 2012. Google Scholar
  12. Bruno Beauquier and Eric Darrot. On arbitrary waksman networks and their vulnerability. Technical Report 3788, INRIA, 1999. Google Scholar
  13. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In STOC, pages 1-10, New York, NY, USA, 1988. ACM. URL: https://doi.org/10.1145/62212.62213.
  14. Dan Bogdanov, Sven Laur, and Riivo Talviste. A practical analysis of oblivious sorting algorithms for secure multi-party computation. In Nordic Conference on Secure IT Systems, pages 59-74. Springer, 2014. Google Scholar
  15. Ran Canetti and Rafail Ostrovsky. Secure computation with honest-looking parties (extended abstract) what if nobody is truly honest? In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 255-264, 1999. Google Scholar
  16. T-H Hubert Chan, Jonathan Katz, Kartik Nayak, Antigoni Polychroniadou, and Elaine Shi. More is less: Perfectly secure oblivious algorithms in the multi-server setting. In ASIACRYPT, pages 158-188. Springer, 2018. Google Scholar
  17. Koji Chida, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Naoto Kiribuchi, and Benny Pinkas. An efficient secure three-party sorting protocol with an honest majority. IACR ePrint 2019/695, 2019. Google Scholar
  18. David B. Cousins, Gerard Ryan, Yuriy Polyakov, and Kurt Rohloff. PALISADE. https://gitlab.com/palisade, 2019. Google Scholar
  19. Daniel Demmler, Thomas Schneider, and Michael Zohner. ABY-a framework for efficient mixed-protocol secure two-party computation. In NDSS, 2015. Google Scholar
  20. Sam Dittmer and Rafail Ostrovsky. Oblivious tight compaction in O(n) time with smaller constant. In SCN, 2020. Google Scholar
  21. Kris Vestergaard Ebbesen. On the practicality of data-oblivious sorting. Master’s thesis, Aarhus university, 2015. Google Scholar
  22. Craig Gentry, Shai Halevi, Charanjit Jutla, and Mariana Raykova. Private database access with HE-over-ORAM architecture. In International Conference on Applied Cryptography and Network Security, pages 172-191. Springer, 2015. Google Scholar
  23. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game. In STOC, pages 218-229, 1987. Google Scholar
  24. Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM), 43(3):431-473, 1996. Google Scholar
  25. Michael T Goodrich. Randomized shellsort: A simple oblivious sorting algorithm. In SODA, pages 1262-1277. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  26. Michael T Goodrich. Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data. In SPAA, pages 379-388. ACM, 2011. Google Scholar
  27. Michael T Goodrich. Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in o(n log~n) time. In STOC, pages 684-693. ACM, 2014. Google Scholar
  28. Vipul Goyal, Rafail Ostrovsky, and Yifan Song. ATLAS: Efficient and scalable MPC in the honest majority setting. Manuscript, 2021. Google Scholar
  29. Jens Groth. A verifiable secret shuffle of homomorphic encryptions. Journal of Cryptology, 23(4):546-579, 2010. Google Scholar
  30. Koki Hamada, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. Oblivious radix sort: An efficient sorting algorithm for practical secure multi-party computation. IACR Cryptology ePrint Archive, 2014:121, 2014. Google Scholar
  31. Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. Practically efficient multi-party sorting protocols from comparison sort algorithms. In ICISC, pages 202-216. Springer, 2012. Google Scholar
  32. Yan Huang, David Evans, and Jonathan Katz. Private set intersection: Are garbled circuits better than custom protocols? In NDSS, 2012. Google Scholar
  33. Peeter Laud and Alisa Pankova. Privacy-preserving record linkage in large databases using secure multiparty computation. BMC medical genomics, 11(4):84, 2018. Google Scholar
  34. Sven Laur, Jan Willemson, and Bingsheng Zhang. Round-efficient oblivious database manipulation. In ISC, pages 262-277. Springer, 2011. Google Scholar
  35. Tom Leighton, Yuan Ma, and Torsten Suel. On probabilistic networks for selection, merging, and sorting. Theory of Computing Systems, 30(6):559-582, 1997. Google Scholar
  36. Wei-Kai Lin, Elaine Shi, and Tiancheng Xie. Can we overcome the n log~n barrier for oblivious sorting? In SODA, pages 2419-2438. Society for Industrial and Applied Mathematics, 2019. Google Scholar
  37. John C Mitchell and Joe Zimmerman. Data-oblivious data structures. In STACS. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  38. Rafail Ostrovsky. Efficient computation on oblivious RAMs. In STOC, pages 514-523, 1990. Google Scholar
  39. Michael S Paterson. Improved sorting networks with O(log~N) depth. Algorithmica, 5(1-4):75-92, 1990. Google Scholar
  40. Joel Seiferas. Sorting networks of logarithmic depth, further simplified. Algorithmica, 53(3):374-384, 2009. Google Scholar
  41. Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612-613, 1979. Google Scholar
  42. Nigel P Smart and Younes Talibi Alaoui. Distributing any elliptic curve based protocol. In IMACC, pages 342-366. Springer, 2019. Google Scholar
  43. Nikolaj Volgushev, Malte Schwarzkopf, Ben Getchell, Mayank Varia, Andrei Lapets, and Azer Bestavros. Conclave: secure multi-party computation on big data. In EuroSys, page 3. ACM, 2019. Google Scholar
  44. Abraham Waksman. A permutation network. Journal of the ACM (JACM), 15(1):159-163, 1968. Google Scholar
  45. Xiao Wang, Alex J Malozemoff, and Jonathan Katz. EMP-toolkit: Efficient multiparty computation toolkit. https://github.com/emp-toolkit/emp-sh2pc, 2016. Google Scholar
  46. Xiao Wang, Samuel Ranellucci, and Jonathan Katz. Global-scale secure multiparty computation. In CCS, pages 39-56. ACM, 2017. Google Scholar
  47. Andrew Yao. Protocols for Secure Computations (Extended Abstract). In FOCS, pages 160-164, 1982. Google Scholar
  48. Andrew Yao. How to Generate and Exchange Secrets. In FOCS, pages 162-167, 1986. Google Scholar
  49. Samee Zahur and David Evans. Obliv-c: A language for extensible data-oblivious computation. IACR Cryptology ePrint Archive 2015/1153, 2015. 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