Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3658644.3690359acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
research-article
Open access

Secure Sorting and Selection via Function Secret Sharing

Published: 09 December 2024 Publication History

Abstract

We revisit the problem of concretely efficient secure computation of sorting and selection (e.g., maximum, median, or top-k) on secret-shared data, focusing on the case of security against a single semi-honest party. Previous solutions either have a high communication overhead or many rounds of interaction, even when allowing input-independent preprocessing.
We propose a suite of 2-party and 3-party offline-online protocols that exploit the efficient aggregation feature of function secret sharing to minimize the online communication and rounds. In particular, most of our protocols are optimal in terms of both online communication and online rounds up to small constant factors.
We compare the performance of our protocols with prior works for different input parameters (number of items, bit length of items, batch size) and system parameters (CPU cores, network) and obtain up to 14x improvement in online run time for sorting and selection under some settings.

References

[1]
Amit Agarwal, Elette Boyle, Niv Gilboa, Yuval Ishai, Mahimna Kelkar, and Yiping Ma. 2024. Compressing Unit-Vector Correlations via Sparse Pseudorandom Generators. In CRYPTO. Springer, 346--383.
[2]
Miklós Ajtai, János Komlós, and Endre Szemerédi. 1983. An O(n log n) Sorting Network. In STOC. ACM, 1--9.
[3]
Noga Alon and Yossi Azar. 1988. Sorting, approximate sorting, and searching in rounds. SIAM Journal on Discrete Mathematics, Vol. 1, 3 (1988), 269--280.
[4]
Noga Alon, Yossi Azar, and Uzi Vishkin. 1986. Tight complexity bounds for parallel comparison sorting. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). IEEE, 502--510.
[5]
Toshinori Araki, Jun Furukawa, Kazuma Ohara, Benny Pinkas, Hanan Rosemarin, and Hikaru Tsuchida. 2021. Secure graph analysis at scale. In CCS. 610--629.
[6]
Joshua J. Arulanandham, Cristian S Calude, and Michael Dinneen. 2002. Bead--sort: A natural sorting algorithm. Technical Report. Department of Computer Science, The University of Auckland, New Zealand.
[7]
Gilad Asharov, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Ariel Nof, Benny Pinkas, Katsumi Takahashi, and Junichi Tomida. 2022. Efficient secure three-party sorting with applications to data analysis and heavy hitters. In CCS. 125--138.
[8]
Kenneth E Batcher. 1968. Sorting networks and their applications. In Proceedings of the April 30--May 2, 1968, spring joint computer conference. 307--314.
[9]
Donald Beaver, Joan Feigenbaum, Joe Kilian, and Phillip Rogaway. 1997. Locally Random Reductions: Improvements and Applications. J. Cryptology, Vol. 10 (1997), 17--36. https://doi.org/10.1007/s001459900017
[10]
Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias. 2011. Semi-homomorphic Encryption and Multiparty Computation. In EUROCRYPT. Springer, 169--188.
[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.
[12]
Béla Bollobás and Graham Brightwell. 1990. Parallel selection with high probability. SIAM Journal on Discrete Mathematics, Vol. 3, 1 (1990), 21--31.
[13]
Béla Bollobás and Moshe Rosenfeld. 1981. Sorting in one round. Israel Journal of Mathematics, Vol. 38 (1981), 154--160.
[14]
Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, and Mayank Rathee. 2021. Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation. In EUROCRYPT. 871--900.
[15]
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. 2019. Efficient pseudorandom correlation generators: Silent OT extension and more. In CRYPTO. Springer, 489--518.
[16]
Elette Boyle, Niv Gilboa, and Yuval Ishai. 2015. Function secret sharing. In EUROCRYPT. Springer, 337--367.
[17]
Elette Boyle, Niv Gilboa, and Yuval Ishai. 2016. Function secret sharing: Improvements and extensions. In CCS. 1292--1303.
[18]
Mark Braverman, Jieming Mao, and S Matthew Weinberg. 2016. Parallel algorithms for select and partition with noisy comparisons. In STOC. 851--862.
[19]
Paul Bunn, Eyal Kushilevitz, and Rafail Ostrovsky. 2022. CNF-FSS and its applications. In Public-Key Cryptography--PKC 2022: 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8--11, 2022, Proceedings, Part I. Springer, 283--314.
[20]
Ran Canetti. 2000. Security and Composition of Multiparty Cryptographic Protocols. J. Cryptol., Vol. 13, 1 (2000), 143--202.
[21]
Melissa Chase, Esha Ghosh, and Oxana Poburinnaya. 2020. Secret-shared shuffle. In ASIACRYPT. Springer, 342--372.
[22]
Ivan Damgård, Jesper Buus Nielsen, Michael Nielsen, and Samuel Ranellucci. 2017. The TinyTable Protocol for 2-Party Secure Computation, or: Gate-Scrambling Revisited. In EUROCRYPT. 167--187.
[23]
Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. 2012. Multiparty Computation from Somewhat Homomorphic Encryption. In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19--23, 2012. Proceedings (Lecture Notes in Computer Science, Vol. 7417), Reihaneh Safavi-Naini and Ran Canetti (Eds.). Springer, 643--662. https://doi.org/10.1007/978--3--642--32009--5_38
[24]
Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, and Daniel Wichs. 2016. Spooky Encryption and Its Applications. In CRYPTO. Springer, 93--122.
[25]
Jack Doerner and Abhi Shelat. 2017. Scaling ORAM for secure computation. In CCS. 523--535.
[26]
Chun Guo, Jonathan Katz, Xiao Wang, and Yu Yu. 2020. Efficient and Secure Multiparty Computation from Fixed-Key Block Ciphers. In IEEE SP. 825--841.
[27]
Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. 2013. Practically efficient multi-party sorting protocols from comparison sort algorithms. In ICISC. Springer, 202--216.
[28]
Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Claudio Orlandi, and Anat Paskin-Cherniavsky. 2013. On the Power of Correlated Randomness in Secure Computation. In TCC. 600--620.
[29]
Vladimir Kolesnikov, Ahmad-Reza Sadeghi, and Thomas Schneider. 2009. Improved garbled circuit building blocks and applications to auctions and computing minima. In CANS. Springer, 1--20.
[30]
A Pranav Shriram, Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal, and Somya Sangal. 2023. Ruffle: Rapid 3-party shuffle protocols. Proceedings on Privacy Enhancing Technologies, Vol. 3 (2023), 24--42.
[31]
Thomas Schneider and Michael Zohner. 2013. GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In FC. Springer, 275--292.
[32]
Leslie G Valiant. 1975. Parallelism in comparison problems. SIAM J. Comput., Vol. 4, 3 (1975), 348--355.
[33]
Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets. In FOCS. 162--167.
[34]
Bingsheng Zhang. 2011. Generic constant-round oblivious sorting algorithm for MPC. In International Conference on Provable Security. Springer, 240--256.

Index Terms

  1. Secure Sorting and Selection via Function Secret Sharing

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    CCS '24: Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security
    December 2024
    5188 pages
    ISBN:9798400706363
    DOI:10.1145/3658644
    This work is licensed under a Creative Commons Attribution International 4.0 License.

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 09 December 2024

    Check for updates

    Author Tags

    1. function secret sharing.
    2. secure multiparty computation
    3. secure selection
    4. secure sorting

    Qualifiers

    • Research-article

    Funding Sources

    • ERC
    • AFOSR
    • ERC grant NTSC
    • MOST
    • BSF grant
    • ISF
    • Microsoft Research PhD Fellowship
    • ISF grant
    • ISF-NSFC grant

    Conference

    CCS '24
    Sponsor:

    Acceptance Rates

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

    Upcoming Conference

    CCS '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 23
      Total Downloads
    • Downloads (Last 12 months)23
    • Downloads (Last 6 weeks)23
    Reflects downloads up to 11 Dec 2024

    Other Metrics

    Citations

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media