research-article

Efficient Secure Three-Party Sorting with Applications to Data Analysis and Heavy Hitters

Authors:

Katsumi Takahashi,

Junichi TomidaAuthors Info & Claims

CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

Pages 125 - 138

https://doi.org/10.1145/3548606.3560691

Published: 07 November 2022 Publication History

Abstract

We present a three-party sorting protocol secure against passive and active adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as private set intersection of shared data, deduplication, and the identification of heavy hitters. The new protocol computes a stable sort. It is based on radix sort and is asymptotically better than previous secure sorting protocols. It improves on previous radix sort protocols by not having to shuffle the entire length of the items after each comparison step.

We implemented our sorting protocol with different optimizations and achieved concretely fast performance. For example, sorting one million items with 32-bit keys and 32-bit values takes less than 2 seconds with semi-honest security and about 3.5 seconds with malicious security. Finding the heavy hitters among hundreds of thousands of 256-bit values takes only a few seconds, compared to close to an hour in previous work.

References

[1]

Mark Abspoel, Anders P. K. Dalskov, Daniel Escudero, and Ariel Nof. 2021. An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings. In Applied Cryptography and Network Security - 19th International Conference, ACNS 2021, Kamakura, Japan, June 21--24, 2021, Proceedings, Part II (Lecture Notes in Computer Science), Kazue Sako and Nils Ole Tippenhauer (Eds.), Vol. 12727. Springer, 122--152. https://doi.org/10.1007/978-3-030-78375-4_6

Digital Library

[2]

Miklós Ajtai, János Komlós, and Endre Szemerédi. 1983. An O(n log n) Sorting Network. In STOC. 1--9. https://doi.org/10.1145/800061.808726

Digital Library

[3]

Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara. 2016. High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority. In CCS. 805--817. https://doi.org/10.1145/2976749.2978331

Digital Library

[4]

Toshinori Araki, Jun Furukawa, Kazuma Ohara, Benny Pinkas, Hanan Rosemarin, and Hikaru Tsuchida. 2021. Secure Graph Analysis at Scale. In CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security, 2021. ACM, 610--629.

Digital Library

[5]

Gilad Asharov, T.-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2020. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. In 3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, January 6-7, 2020. SIAM, 8--14.

[6]

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. 2020. OptORAMa: Optimal Oblivious RAM. In Advances in Cryptology - EUROCRYPT 2020 (Lecture Notes in Computer Science), Vol. 12106. Springer, 403--432.

Digital Library

[7]

Kenneth E. Batcher. 1968. Sorting Networks and Their Applications. In American Federation of Information Processing Societies: AFIPS, Vol. 32. Thomson Book Company, Washington D.C., 307--314.

[8]

Gabrielle Beck, Aarushi Goel, Abhishek Jain, and Gabriel Kaptchuk. 2021. OrderC Secure Multiparty Computation for Highly Repetitive Circuits. In Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part II (Lecture Notes in Computer Science), Anne Canteaut and François-Xavier Standaert (Eds.), Vol. 12697. Springer, 663--693.

Digital Library

[9]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing. ACM, 1--10.

Digital Library

[10]

Marina Blanton and Everaldo Aguiar. 2012. Private and Oblivious Set and Multiset Operations. In ASIACCS '12. ACM, New York, NY, USA, 40--41. https://doi.org/ 10.1145/2414456.2414479

Digital Library

[11]

Dan Bogdanov, Sven Laur, and Riivo Talviste. 2014. A practical analysis of oblivious sorting algorithms for secure multi-party computation. In Nordic Conference on Secure IT Systems. Springer, 59--74.

Digital Library

[12]

Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. 2021. Lightweight Techniques for Private Heavy Hitters. (2021), 762--776.

[13]

Koji Chida, Daniel Genkin, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Yehuda Lindell, and Ariel Nof. 2018. Fast Large-Scale Honest-Majority MPC for Malicious Adversaries. In CRYPTO 2018. 34--64. https://doi.org/10.1007/978-3-319-96878-0_2

Digital Library

[14]

Arka Rai Choudhuri, Aarushi Goel, Matthew Green, Abhishek Jain, and Gabriel Kaptchuk. 2021. Fluid MPC: Secure Multiparty Computation with Dynamic Participants. In Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part II (Lecture Notes in Computer Science), Tal Malkin and Chris Peikert (Eds.), Vol. 12826. Springer, 94--123.

[15]

Henry Corrigan-Gibbs and Dan Boneh. 2017. Prio: Private, Robust, and Scalable Computation of Aggregate Statistics. In 14th USENIX Symposium on Networked Systems Design and Implementation, NSDI. USENIX Association, 259--282.

[16]

Ronald Cramer, Ivan Damgård, and Yuval Ishai. 2005. Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. In TCC (LNCS), Joe Kilian (Ed.), Vol. 3378. Springer, 342--362.

[17]

Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and Eran Tromer. 2014. Circuits resilient to additive attacks with applications to secure computation. In Symposium on Theory of Computing, STOC 2014. ACM, 495--504.

Digital Library

[18]

Oded Goldreich. 2004. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press.

Digital Library

[19]

Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. In STOC. ACM, 218--229.

[20]

Michael T. Goodrich. 2010. Randomized Shellsort: A Simple Oblivious Sorting Algorithm. In SODA. 1262--1277.

[21]

Michael T. Goodrich. 2014. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. In Symposium on Theory of Computing, STOC 2014. ACM, 684--693.

Digital Library

[22]

Michael T. Goodrich. 2014. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. In Symposium on Theory of Computing, STOC 2014. ACM, 684--693.

Digital Library

[23]

Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. 2012. Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms. In ICISC. 202--216.

[24]

Y. Huang, D. Evans, J. Katz, and L. Malka. 2011. Faster Secure Two-Party Computation Using Garbled Circuits. In USENIX Security'11. USENIX, 539--554.

[25]

Mitsuru Ito, Akira Saito, and Takao Nishizeki. 1989. Secret sharing scheme realizing general access structure. Electronics and Communications (Part III: Fundamental Electronic Science) 72, 9 (1989), 56--64.

[26]

Kristján Valur Jónsson, Gunnar Kreitz, and Misbah Uddin. 2011. Secure Multi-Party Sorting and Applications. In ACNS. Springer.

[27]

Ryo Kikuchi, Nuttapong Attrapadung, Koki Hamada, Dai Ikarashi, Ai Ishida, Takahiro Matsuda, Yusuke Sakai, and Jacob C. N. Schuldt. 2019. Field Extension in Secret-Shared Form and Its Applications to Efficient Secure Computation. In ACISP, Vol. 11547. Springer, 343--361.

[28]

Ryo Kikuchi, Dai Ikarashi, Takahiro Matsuda, Koki Hamada, and Koji Chida. 2018. Efficient Bit-Decomposition and Modulus-Conversion Protocols with an Honest Majority. In ACISP 2018. 64--82. https://doi.org/10.1007/978-3-319-93638-3_5

Digital Library

[29]

Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and Ni Trieu. 2017. Practical Multi-party Private Set Intersection from Symmetric-Key Techniques. In CCS 2017. 1257--1272. https://doi.org/10.1145/3133956.3134065

Digital Library

[30]

Sven Laur, Jan Willemson, and Bingsheng Zhang. 2011. Round-Efficient Oblivious Database Manipulation. In ISC 2011. 262--277.

[31]

Phi Hung Le, Samuel Ranellucci, and S. Dov Gordon. 2019. Two-party Private Set Intersection with an Untrusted Third Party. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019, Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM, 2403--2420. https://doi.org/10.1145/3319535.3345661

Digital Library

[32]

Frank Thomson Leighton, Yuan Ma, and Torsten Suel. 1995. On Probabilistic Networks for Selection, Merging, and Sorting. In 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '95. ACM, 106--118.

Digital Library

[33]

Wei-Kai Lin, Elaine Shi, and Tiancheng Xie. 2019. Can We Overcome the n log n Barrier for Oblivious Sorting?. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, Timothy M. Chan (Ed.). SIAM, 2419--2438.

Digital Library

[34]

B. Pinkas, T. Schneider, G. Segev, and M. Zohner. 2015. Phasing: Private Set Intersection Using Permutation-based Hashing. In USENIX Security'15. USENIX, 515--530.

[35]

Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. 2018. Efficient Circuit-Based PSI via Cuckoo Hashing. In EUROCRYPT. 125--157.

[36]

Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (1979), 612--613.

Digital Library

Cited By

Zheng YZhu HLu RZhang SWang FShao JLi H(2025)Efficient and Privacy-Preserving Weighted Range Set Sampling in CloudIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.340881622:1(534-548)Online publication date: Jan-2025
https://doi.org/10.1109/TDSC.2024.3408816
Attrapadung NIsayama KSadakane KTozawa KLuo BLiao XXu JKirda ELie D(2024)Secure Parallel Computation with Oblivious State TransitionsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690315(3008-3022)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690315
Zhou PGuo XChen PLi TLv SLiu ZLuo BLiao XXu JKirda ELie D(2024)Shortcut: Making MPC-based Collaborative Analytics Efficient on Dynamic DatabasesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690314(854-868)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690314
Show More Cited By

Index Terms

Efficient Secure Three-Party Sorting with Applications to Data Analysis and Heavy Hitters
1. Security and privacy
  1. Cryptography

Recommendations

High-Throughput Secure Three-Party Computation with an Honest Majority
Abstract
In the setting of secure multiparty computation, a set of parties wish to carry out a joint computation of their inputs while keeping them private. In this paper, we describe new information-theoretic protocols for secure three-party computation ... $^{}$
Fast and Secure Three-party Computation: The Garbled Circuit Approach
CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for ...
Complete fairness in secure two-party computation
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

November 2022

3598 pages

ISBN:9781450394505

DOI:10.1145/3548606

General Chairs:
Heng Yin
University of California, Riverside
,
Angelos Stavrou
Virginia Tech
,
Program Chairs:
Cas Cremers
CISPA Helmholtz Center for Information Security
,
Elaine Shi
Carnegie Mellon University

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Union?s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement

Conference

CCS '22

Sponsor:

SIGSAC

CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security

November 7 - 11, 2022

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
721
Total Downloads

Downloads (Last 12 months)153
Downloads (Last 6 weeks)9

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zheng YZhu HLu RZhang SWang FShao JLi H(2025)Efficient and Privacy-Preserving Weighted Range Set Sampling in CloudIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.340881622:1(534-548)Online publication date: Jan-2025
https://doi.org/10.1109/TDSC.2024.3408816
Attrapadung NIsayama KSadakane KTozawa KLuo BLiao XXu JKirda ELie D(2024)Secure Parallel Computation with Oblivious State TransitionsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690315(3008-3022)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690315
Zhou PGuo XChen PLi TLv SLiu ZLuo BLiao XXu JKirda ELie D(2024)Shortcut: Making MPC-based Collaborative Analytics Efficient on Dynamic DatabasesProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690314(854-868)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690314
Rathee MZhang YCorrigan-Gibbs HAda Popa R(2024)Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00245(3072-3090)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00245
Kim SSon YPaek JCho SLee H(2024)A Survey of Blind Sorting Techniques: Approaches Using Fully Homomorphic Encryption2024 15th International Conference on Information and Communication Technology Convergence (ICTC)10.1109/ICTC62082.2024.10827130(480-485)Online publication date: 16-Oct-2024
https://doi.org/10.1109/ICTC62082.2024.10827130
Yu SWang HSu YNiu ZLi ZLiu JWang J(2024)Privacy-preserving recommendation system based on social relationshipsJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2024.10192336:2Online publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1016/j.jksuci.2024.101923
Ostrovsky B(2024)Privacy-Preserving DijkstraAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68400-5_3(74-110)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68400-5_3
Luo QWang YYi KWang SLi F(2023)Secure Sampling for Approximate Multi-party Query ProcessingProceedings of the ACM on Management of Data10.1145/36173391:3(1-27)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3617339
Asharov GHamada KKikuchi RNof APinkas BTomida JMeng WJensen CCremers CKirda E(2023)Secure Statistical Analysis on Multiple Datasets: Join and Group-ByProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623119(3298-3312)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623119

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten