Secure Statistical Analysis on Multiple Datasets: Join and Group-By
Authors: 
Gilad Asharov, 
Koki Hamada, Ryo Kikuchi, Ariel Nof, Benny Pinkas, Junichi TomidaAuthors Info & Claims
Pages 3298 - 3312
Abstract
We implement a secure platform for statistical analysis over multiple organizations and multiple datasets. We provide a suite of protocols for different variants of JOIN and GROUP-BY operations. JOIN allows combining data from multiple datasets based on a common column. GROUP-BY allows aggregating rows that have the same values in a column or a set of columns, and then apply some aggregation summary on the rows (such as sum, count, median, etc.). Both operations are fundamental tools for relational databases. One example use case of our platform is in data marketing in which an analyst would join purchase histories and membership information, and then obtain statistics, such as "Which products were bought by people earning this much per annum?"
Both JOIN and GROUP-BY involve many variants, and we design protocols for several common procedures. In particular, we propose a novel group-by-median protocol that has not been known so far. Our protocols rely on sorting protocols, and work in the honest majority setting and against malicious adversaries. To the best of our knowledge, this is the first implementation of JOIN and GROUP-BY protocols secure against a malicious adversary.
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 ACNS 2021 (Lecture Notes in Computer Science, Vol. 12727), Kazue Sako and Nils Ole Tippenhauer (Eds.). Springer, 122--152. https://doi.org/10.1007/978-3-030-78375-4_6
[2]
Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. 2015. Ciphers for MPC and FHE. In EUROCRYPT 2015, Elisabeth Oswald and Marc Fischlin (Eds.), Vol. 9056. Springer, 430--454. https://doi.org/10.1007/978-3-662-46800-5_17
[3]
Mohammad Anagreh, Peeter Laud, and Eero Vainikko. 2021. Parallel Privacy-Preserving Shortest Path Algorithms. Cryptogr., Vol. 5, 4 (2021), 27. https://doi.org/10.3390/cryptography5040027
[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, Virtual Event, Republic of Korea, November 15 - 19, 2021, Yongdae Kim, Jong Kim, Giovanni Vigna, and Elaine Shi (Eds.). ACM, 610--629. https://doi.org/10.1145/3460120.3484560
[5]
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 2022, Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (Eds.). ACM, 125--138. https://doi.org/10.1145/3548606.3560691
[6]
Nuttapong Attrapadung, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Takahiro Matsuda, Ibuki Mishina, Hiraku Morita, and Jacob C. N. Schuldt. 2022a. Adam in Private: Secure and Fast Training of Deep Neural Networks with Adaptive Moment Estimation. Proc. Priv. Enhancing Technol., Vol. 2022, 4 (2022), 746--767.
[7]
Nuttapong Attrapadung, Hiraku Morita, Kazuma Ohara, Jacob C. N. Schuldt, Tadanori Teruya, and Kazunari Tozawa. 2022b. Secure Parallel Computation on Privately Partitioned Data and Applications. In CCS 2022, Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (Eds.). ACM, 151--164. https://doi.org/10.1145/3548606.3560695
[8]
Saikrishna Badrinarayanan, Sourav Das, Gayathri Garimella, Srinivasan Raghuraman, and Peter Rindal. 2022. Secret-Shared Joins with Multiplicity from Aggregation Trees. In ACM SIGSAC Conference on Computer and Communications Security (CCS).
[9]
Marina Blanton and Everaldo Aguiar. 2012. Private and oblivious set and multiset operations. In ASIACCS '12. 40--41.
[10]
Guy E. Blelloch. 1989. Scans as Primitive Parallel Operations. IEEE Trans. Computers, Vol. 38, 11 (1989), 1526--1538.
[11]
Guy E. Blelloch. 1990. Prefix sums and their applications. https://www.cs.cmu.edu/ guyb/papers/Ble93.pdf
[12]
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 (Lecture Notes in Computer Science, Vol. 10993), Hovav Shacham and Alexandra Boldyreva (Eds.). Springer, 34--64. https://doi.org/10.1007/978-3-319-96878-0_2
[13]
R. Cramer, I. Damgård, and Y. Ishai. 2005. Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. In TCC (LNCS, Vol. 3378). Springer, 342--362.
[14]
Reza Curtmola, Juan A. Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Searchable symmetric encryption: improved definitions and efficient constructions. In Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati (Eds.). ACM, 79--88.
[15]
Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. 2004. Efficient Private Matching and Set Intersection. In Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings (Lecture Notes in Computer Science, Vol. 3027), Christian Cachin and Jan Camenisch (Eds.). Springer, 1--19.
[16]
O. Goldreich. 2004. Foundations of Cryptography.
[17]
Koki Hamada, Dai Ikarashi, Ryo Kikuchi, and Koji Chida. 2023. Efficient decision tree training with new data structure for secure multi-party computation. Proc. Priv. Enhancing Technol., Vol. 2023, 1 (2023), 343--364. https://doi.org/10.56553/popets-2023-0021
[18]
Mitsuru Ito, Akira Saito, and Takao Nishizeki. 1989. Secret sharing scheme realizing general access structure. Electronics and Communications (Part III: Fundamental Electronic Science), Vol. 72, 9 (1989), 56--64.
[19]
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 2019 (Lecture Notes in Computer Science, Vol. 11547), Julian Jang-Jaccard and Fuchun Guo (Eds.). Springer, 343--361. https://doi.org/10.1007/978-3-030-21548-4_19
[20]
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.
[21]
Sven Laur, Riivo Talviste, and Jan Willemson. 2013. From Oblivious AES to Efficient and Secure Database Join in the Multiparty Setting. In ACNS 2013 (Lecture Notes in Computer Science, Vol. 7954), Michael J. Jacobson Jr., Michael E. Locasto, Payman Mohassel, and Reihaneh Safavi-Naini (Eds.). Springer, 84--101. https://doi.org/10.1007/978-3-642-38980-1_6
[22]
Fukang Liu, Takanori Isobe, and Willi Meier. 2021. Cryptanalysis of Full LowMC and LowMC-M with Algebraic Techniques. In CRYPTO 2021 (Lecture Notes in Computer Science, Vol. 12827), Tal Malkin and Chris Peikert (Eds.). Springer, 368--401. https://doi.org/10.1007/978-3-030-84252-9_13
[23]
Payman Mohassel, Peter Rindal, and Mike Rosulek. 2020. Fast Database Joins and PSI for Secret Shared Data. In ACM SIGSAC Conference on Computer and Communications Security (CCS).
[24]
Kartik Nayak, Xiao Shaun Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft, and Elaine Shi. 2015. GraphSC: Parallel Secure Computation Made Easy. In SP 2015. IEEE Computer Society, 377--394. https://doi.org/10.1109/SP.2015.30
[25]
Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. 2015. Phasing: Private Set Intersection Using Permutation-based Hashing. In 24th USENIX Security Symposium, USENIX Security 15, Washington, D.C., USA, August 12-14, 2015, Jaeyeon Jung and Thorsten Holz (Eds.). USENIX Association, 515--530.
[26]
A. Shamir. 1980. On the Power of Commutativity in Cryptography. In ICALP.
[27]
Dawn Xiaodong Song, David A. Wagner, and Adrian Perrig. 2000. Practical Techniques for Searches on Encrypted Data. In 2000 IEEE Symposium on Security and Privacy, Berkeley, California, USA, May 14-17, 2000. IEEE Computer Society, 44--55.
[28]
T. Araki, J. Furukawa, Y. Lindell, A. Nof, and K. Ohara. 2016. High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority. In ACM CCS. ACM, 805--817. io
Index Terms
- Secure Statistical Analysis on Multiple Datasets: Join and Group-By
Recommendations
High-Throughput Secure Three-Party Computation with an Honest Majority
AbstractIn 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 Large-Scale Honest-Majority MPC for Malicious Adversaries
AbstractProtocols for secure multiparty computation enable a set of parties to compute a function of their inputs without revealing anything but the output. The security properties of the protocol must be preserved in the presence of adversarial behavior. ...
On the Power of an Honest Majority in Three-Party Computation Without Broadcast
AbstractFully secure multiparty computation (MPC) allows a set of parties to compute some function of their inputs, while guaranteeing correctness, privacy, fairness, and output delivery. Understanding the necessary and sufficient assumptions that allow ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
3722 pages
ISBN:9798400700507
DOI:10.1145/3576915
- General Chairs:
- Weizhi Meng,
- Christian D. Jensen,
- Program Chairs:
- Cas Cremers,
- Engin Kirda
Copyright © 2023 Owner/Author.
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: 21 November 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- European Union?s Horizon 2020
- Israel Science Foundation
Conference
CCS '23
Sponsor:
CCS '23: ACM SIGSAC Conference on Computer and Communications Security
November 26 - 30, 2023
Copenhagen, Denmark
Acceptance Rates
Overall Acceptance Rate 1,261 of 6,999 submissions, 18%
Upcoming Conference
CCS '24
- Sponsor:
- sigsac
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 485Total Downloads
- Downloads (Last 12 months)485
- Downloads (Last 6 weeks)54
Reflects downloads up to 14 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in