research-article

Accelerating Secure (2+1)-Party Computation by Insecure but Efficient Building Blocks

Authors:

Keitaro Hiwatashi,

Koji NuidaAuthors Info & Claims

ASIA CCS '21: Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security

Pages 616 - 627

https://doi.org/10.1145/3433210.3453109

Published: 04 June 2021 Publication History

Abstract

Secure multi-party computation (MPC) is a cryptographic tool that enables a set of parties to compute a function jointly while keeping each input secret. Since MPC based on secret sharing (SS) achieves high throughput and works fast, many applications have been developed. However, SS-based MPC requires many communication rounds in general, and this becomes a performance bottleneck in real-world applications under high-latency networks. In this paper, we propose SS-based secure three-party computation with almost no preprocessing based on our new (small-)constant-round fundamental gates, by revisiting a framework in a few previous works where a number of parties are assisted by another party who may partially learn secret information. Instead of ordinary logical gates, our fundamental gate is an efficient Equality, for which the result leaks to the third party, and we develop novel two-round constructions of secure building-block protocols (LessThan Comparison, RightShift, Table LookUp, etc.) from the insecure Equality. To show the practicality of our protocols, we implement a secure exact edit distance protocol for two genome strings. Our experiments show that in some network setting our protocol is about 2 times faster (14 times faster taking preprocessing into consideration) than the state-of-the-art SS-based protocol (Ohata and Nuida, FC 2020).

References

[1]

Toshinori Araki, Assi Barak, Jun Furukawa, Marcel Keller, Yehuda Lindell, Kazuma Ohara, and Hikaru Tsuchida. 2018. Generalizing the SPDZ Compiler For Other Protocols. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15--19, 2018. 880--895.

Digital Library

[2]

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 Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24--28, 2016. 805--817.

Digital Library

[3]

Donald Beaver. 1991. Efficient Multiparty Protocols Using Circuit Randomization. In Advances in Cryptology - CRYPTO '91, 11th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11--15, 1991, Proceedings. 420--432.

[4]

Elette Boyle, Niv Gilboa, and Yuval Ishai. 2019. Secure Computation with Preprocessing via Function Secret Sharing. In Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1--5, 2019, Proceedings, Part I. 341--371.

[5]

Octavian Catrina and Sebastiaan de Hoogh. 2010. Improved Primitives for Secure Multiparty Integer Computation. In Security and Cryptography for Networks, 7th International Conference, SCN 2010, Amalfi, Italy, September 13--15, 2010. Proceedings. 182--199.

[6]

Harsh Chaudhari, Ashish Choudhury, Arpita Patra, and Ajith Suresh. 2019. ASTRA: High Throughput 3PC over Rings with Application to Secure Prediction. In Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop, CCSW@CCS 2019, London, UK, November 11, 2019, Radu Sion and Charalampos Papamanthou (Eds.). ACM, 81--92. https://doi.org/10.1145/3338466.3358922

Digital Library

[7]

Harsh Chaudhari, Rahul Rachuri, and Ajith Suresh. 2020. Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning. In 27th Annual Network and Distributed System Security Symposium, NDSS 2020, San Diego, California, USA, February 23--26, 2020. The Internet Society.

[8]

Ke Cheng, Yantian Hou, and Liangmin Wang. 2018. Secure Similar Sequence Query on Outsourced Genomic Data. In Proceedings of the 2018 on Asia Conference on Computer and Communications Security, AsiaCCS 2018, Incheon, Republic of Korea, June 04-08, 2018. 237--251.

Digital Library

[9]

Ivan Damgård, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, and Tomas Toft. 2006. Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4--7, 2006, Proceedings. 285--304.

Digital Library

[10]

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), Reihaneh Safavi-Naini and Ran Canetti (Eds.), Vol. 7417. Springer, 643--662. https://doi.org/10.1007/978--3--642--32009--5_38

[11]

Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, Shaza Zeitouni, and Michael Zohner. 2017. Pushing the Communication Barrier in Secure Computation using Lookup Tables. In 24th Annual Network and Distributed System Security Symposium, NDSS 2017, San Diego, California, USA, February 26 - March 1, 2017 .

[12]

Jack Doerner and Abhi Shelat. 2017. Scaling ORAM for Secure Computation. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM, 523--535. https://doi.org/10.1145/3133956.3133967

Digital Library

[13]

Oded Goldreich. 2009. Foundations of cryptography: volume 2, basic applications .Cambridge university press.

Digital Library

[14]

Seny Kamara, Payman Mohassel, Mariana Raykova, and Seyed Saeed Sadeghian. 2014. Scaling Private Set Intersection to Billion-Element Sets. In Financial Cryptography and Data Security - 18th International Conference, FC 2014, Christ Church, Barbados, March 3--7, 2014, Revised Selected Papers. 195--215.

[15]

Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2016. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24--28, 2016, Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (Eds.). ACM, 830--842. https://doi.org/10.1145/2976749.2978357

Digital Library

[16]

Payman Mohassel and Yupeng Zhang. 2017. SecureML: A System for Scalable Privacy-Preserving Machine Learning. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22--26, 2017. 19--38.

[17]

Hiraku Morita, Nuttapong Attrapadung, Tadanori Teruya, Satsuya Ohata, Koji Nuida, and Goichiro Hanaoka. 2018. Constant-Round Client-Aided Secure Comparison Protocol. In Computer Security - 23rd European Symposium on Research in Computer Security, ESORICS 2018, Barcelona, Spain, September 3--7, 2018, Proceedings, Part II. 395--415.

[18]

Satsuya Ohata and Koji Nuida. 2020. Communication-Efficient (Client-Aided) Secure Two-Party Protocols and Its Application. In Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10--14, 2020 Revised Selected Papers (Lecture Notes in Computer Science), Joseph Bonneau and Nadia Heninger (Eds.), Vol. 12059. Springer, 369--385. https://doi.org/10.1007/978--3-030--51280--4_20

[19]

Deevashwer Rathee, Thomas Schneider, and K. K. Shukla. 2019. Improved Multiplication Triple Generation over Rings via RLWE-Based AHE. In Cryptology and Network Security - 18th International Conference, CANS 2019, Fuzhou, China, October 25--27, 2019, Proceedings. 347--359.

[20]

M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schneider, and Farinaz Koushanfar. 2018. Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications. In Proceedings of the 2018 on Asia Conference on Computer and Communications Security, AsiaCCS 2018, Incheon, Republic of Korea, June 04-08, 2018, Jong Kim, Gail-Joon Ahn, Seungjoo Kim, Yongdae Kim, Javier López, and Taesoo Kim (Eds.). ACM, 707--721. https://doi.org/10.1145/3196494.3196522

Digital Library

[21]

Thomas Schneider and Oleksandr Tkachenko. 2019. EPISODE: Efficient Privacy-PreservIng Similar Sequence Queries on Outsourced Genomic DatabasEs. In Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security, AsiaCCS 2019, Auckland, New Zealand, July 09--12, 2019. 315--327.

Digital Library

[22]

Sameer Wagh, Divya Gupta, and Nishanth Chandran. 2019. SecureNN: 3-Party Secure Computation for Neural Network Training. PoPETs, Vol. 2019, 3 (2019), 26--49.

[23]

Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets (Extended Abstract). In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27--29 October 1986. 162--167.

Digital Library

[24]

Ruiyu Zhu and Yan Huang. [n.d.]. Efficient and Precise Secure Generalized Edit Distance and Beyond. IEEE Transactions on Dependable and Secure Computing, Vol. (Early Access) ( [n.,d.]). https://doi.org/10.1109/TDSC.2020.2984219

Digital Library

Cited By

Cheng KHou YWang L(2023)Secure Similar Sequence Query over Multi-source Genomic Data on CloudIEEE Transactions on Cloud Computing10.1109/TCC.2022.322890611:3(2803-2819)Online publication date: 1-Jul-2023
https://doi.org/10.1109/TCC.2022.3228906
TSUCHIDA HNISHIDE T(2022)Constant-Round Fair SS-4PC for Private Decision Tree EvaluationIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021DMP0016E105.A:9(1270-1288)Online publication date: 1-Sep-2022
https://doi.org/10.1587/transfun.2021DMP0016

Index Terms

Accelerating Secure (2+1)-Party Computation by Insecure but Efficient Building Blocks
1. Security and privacy
  1. Security services
    1. Privacy-preserving protocols

Recommendations

Bounded-concurrent secure multi-party computation with a dishonest majority
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

We show how to securely realize any multi-party functionality in a way that preserves security under an a-priori bounded number of concurrent executions, regardless of the number of corrupted parties. Previous protocols for the above task either rely on ...
Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...
Secure multi-party computation in large networks

We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a significant number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASIA CCS '21: Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security

May 2021

975 pages

ISBN:9781450382878

DOI:10.1145/3433210

General Chairs:
Jiannong Cao
The Hong Kong Polytechnic University, Hong Kong
,
Man Ho Au
The University of Hong Kong, Hong Kong
,
Program Chairs:
Zhiqiang Lin
The Ohio State University, USA
,
Moti Yung
Google and Columbia University, USA

Copyright © 2021 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

JST CREST
The Ministry of International Affairs and Communications SCOPE

Conference

ASIA CCS '21

Sponsor:

SIGSAC

ASIA CCS '21: ACM Asia Conference on Computer and Communications Security

June 7 - 11, 2021

Virtual Event, Hong Kong

Acceptance Rates

Overall Acceptance Rate 418 of 2,322 submissions, 18%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
279
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng KHou YWang L(2023)Secure Similar Sequence Query over Multi-source Genomic Data on CloudIEEE Transactions on Cloud Computing10.1109/TCC.2022.322890611:3(2803-2819)Online publication date: 1-Jul-2023
https://doi.org/10.1109/TCC.2022.3228906
TSUCHIDA HNISHIDE T(2022)Constant-Round Fair SS-4PC for Private Decision Tree EvaluationIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021DMP0016E105.A:9(1270-1288)Online publication date: 1-Sep-2022
https://doi.org/10.1587/transfun.2021DMP0016

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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents