{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T00:59:17Z","timestamp":1784595557168,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union?s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement","award":["891234"],"award-info":[{"award-number":["891234"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,11,7]]},"DOI":"10.1145\/3548606.3560691","type":"proceedings-article","created":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T11:41:28Z","timestamp":1667821288000},"page":"125-138","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":42,"title":["Efficient Secure Three-Party Sorting with Applications to Data Analysis and Heavy Hitters"],"prefix":"10.1145","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Koki","family":"Hamada","sequence":"additional","affiliation":[{"name":"NTT Corporation, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dai","family":"Ikarashi","sequence":"additional","affiliation":[{"name":"NTT Corporation, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryo","family":"Kikuchi","sequence":"additional","affiliation":[{"name":"NTT Corporation, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ariel","family":"Nof","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Pinkas","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katsumi","family":"Takahashi","sequence":"additional","affiliation":[{"name":"NTT Corporation, Ramat Gan, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Junichi","family":"Tomida","sequence":"additional","affiliation":[{"name":"NTT Corporation, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,7]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"ACNS 2021, Kamakura, Japan, June 21--24, 2021, Proceedings, Part II (Lecture Notes in Computer Science), Kazue Sako and Nils Ole Tippenhauer (Eds.)","volume":"12727","author":"Abspoel Mark","year":"2021","unstructured":"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 10.1007\/978-3-030-78375-4_6 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"},{"key":"#cr-split#-e_1_3_2_1_2_1.1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai J\u00e1nos Koml\u00f3s and Endre Szemer\u00e9di. 1983. An O(n log n) Sorting Network. In STOC. 1--9. https:\/\/doi.org\/10.1145\/800061.808726 10.1145\/800061.808726","DOI":"10.1145\/800061.808726"},{"key":"#cr-split#-e_1_3_2_1_2_1.2","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai J\u00e1nos Koml\u00f3s and Endre Szemer\u00e9di. 1983. An O(n log n) Sorting Network. In STOC. 1--9. https:\/\/doi.org\/10.1145\/800061.808726","DOI":"10.1145\/800061.808726"},{"key":"#cr-split#-e_1_3_2_1_3_1.1","doi-asserted-by":"crossref","unstructured":"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 10.1145\/2976749.2978331","DOI":"10.1145\/2976749.2978331"},{"key":"#cr-split#-e_1_3_2_1_3_1.2","doi-asserted-by":"crossref","unstructured":"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","DOI":"10.1145\/2976749.2978331"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484560"},{"key":"e_1_3_2_1_5_1","volume-title":"Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. In 3rd Symposium on Simplicity in Algorithms, SOSA 2020","author":"Asharov Gilad","year":"2020","unstructured":"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. 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."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_14"},{"key":"e_1_3_2_1_7_1","volume-title":"Sorting Networks and Their Applications","author":"Batcher Kenneth E.","unstructured":"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. 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."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77886-6_23"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_3_2_1_10_1","volume-title":"Private and Oblivious Set and Multiset Operations. In ASIACCS '12","author":"Blanton Marina","year":"2012","unstructured":"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 10.1145\/2414456.2414479 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"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11599-3_4"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Dan Boneh Elette Boyle Henry Corrigan-Gibbs Niv Gilboa and Yuval Ishai. 2021. Lightweight Techniques for Private Heavy Hitters. (2021) 762--776.  Dan Boneh Elette Boyle Henry Corrigan-Gibbs Niv Gilboa and Yuval Ishai. 2021. Lightweight Techniques for Private Heavy Hitters. (2021) 762--776.","DOI":"10.1109\/SP40001.2021.00048"},{"key":"e_1_3_2_1_13_1","volume-title":"Fast Large-Scale Honest-Majority MPC for Malicious Adversaries. In CRYPTO","author":"Chida Koji","year":"2018","unstructured":"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 10.1007\/978-3-319-96878-0_2 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"},{"key":"e_1_3_2_1_14_1","volume-title":"CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part II (Lecture Notes in Computer Science), Tal Malkin and Chris Peikert (Eds.)","volume":"12826","author":"Choudhuri Arka Rai","year":"2021","unstructured":"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. 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."},{"key":"e_1_3_2_1_15_1","volume-title":"14th USENIX Symposium on Networked Systems Design and Implementation, NSDI. USENIX Association, 259--282","author":"Corrigan-Gibbs Henry","year":"2017","unstructured":"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 . 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."},{"key":"e_1_3_2_1_16_1","volume-title":"TCC (LNCS)","author":"Cramer Ronald","unstructured":"Ronald Cramer , Ivan Damg\u00e5rd , 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. Ronald Cramer, Ivan Damg\u00e5rd, 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."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591861"},{"key":"e_1_3_2_1_18_1","volume-title":"The Foundations of Cryptography -","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2004. The Foundations of Cryptography - Volume 2 , Basic Applications. Cambridge University Press . Oded Goldreich. 2004. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1145\/28395.28420"},{"key":"e_1_3_2_1_20_1","volume-title":"Randomized Shellsort: A Simple Oblivious Sorting Algorithm. In SODA. 1262--1277.","author":"Goodrich Michael T.","year":"2010","unstructured":"Michael T. Goodrich . 2010 . Randomized Shellsort: A Simple Oblivious Sorting Algorithm. In SODA. 1262--1277. Michael T. Goodrich. 2010. Randomized Shellsort: A Simple Oblivious Sorting Algorithm. In SODA. 1262--1277."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591830"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591830"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1007\/978-3-642-37682-5_15"},{"key":"e_1_3_2_1_24_1","unstructured":"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.  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."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1002\/ecjc.4430720906","article-title":"Secret sharing scheme realizing general access structure","volume":"72","author":"Ito Mitsuru","year":"1989","unstructured":"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 . 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.","journal-title":"Electronics and Communications (Part III: Fundamental Electronic Science)"},{"key":"e_1_3_2_1_26_1","volume-title":"Secure Multi-Party Sorting and Applications","author":"J\u00f3nsson Kristj\u00e1n Valur","unstructured":"Kristj\u00e1n Valur J\u00f3nsson , Gunnar Kreitz , and Misbah Uddin . 2011. Secure Multi-Party Sorting and Applications . In ACNS. Springer . Kristj\u00e1n Valur J\u00f3nsson, Gunnar Kreitz, and Misbah Uddin. 2011. Secure Multi-Party Sorting and Applications. In ACNS. Springer."},{"key":"e_1_3_2_1_27_1","volume-title":"Schuldt","author":"Kikuchi Ryo","year":"2019","unstructured":"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. 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."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93638-3_5"},{"key":"e_1_3_2_1_29_1","volume-title":"CCS","author":"Kolesnikov Vladimir","year":"2017","unstructured":"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 10.1145\/3133956.3134065 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"},{"key":"e_1_3_2_1_30_1","volume-title":"Round-Efficient Oblivious Database Manipulation. In ISC","author":"Laur Sven","year":"2011","unstructured":"Sven Laur , Jan Willemson , and Bingsheng Zhang . 2011 . Round-Efficient Oblivious Database Manipulation. In ISC 2011. 262--277. Sven Laur, Jan Willemson, and Bingsheng Zhang. 2011. Round-Efficient Oblivious Database Manipulation. In ISC 2011. 262--277."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3345661"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/215399.215429"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310583"},{"key":"e_1_3_2_1_34_1","volume-title":"Phasing: Private Set Intersection Using Permutation-based Hashing. In USENIX Security'15. USENIX, 515--530.","author":"Pinkas B.","year":"2015","unstructured":"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. 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."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Benny Pinkas Thomas Schneider Christian Weinert and Udi Wieder. 2018. Efficient Circuit-Based PSI via Cuckoo Hashing. In EUROCRYPT. 125--157.  Benny Pinkas Thomas Schneider Christian Weinert and Udi Wieder. 2018. Efficient Circuit-Based PSI via Cuckoo Hashing. In EUROCRYPT. 125--157.","DOI":"10.1007\/978-3-319-78372-7_5"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"}],"event":{"name":"CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security","location":"Los Angeles CA USA","acronym":"CCS '22","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3548606.3560691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3548606.3560691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:59Z","timestamp":1750182539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3548606.3560691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,7]]},"references-count":38,"alternative-id":["10.1145\/3548606.3560691","10.1145\/3548606"],"URL":"https:\/\/doi.org\/10.1145\/3548606.3560691","relation":{},"subject":[],"published":{"date-parts":[[2022,11,7]]},"assertion":[{"value":"2022-11-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}