research-article

ASTRA: High Throughput 3PC over Rings with Application to Secure Prediction

Authors:

Harsh Chaudhari,

Ashish Choudhury,

Ajith SureshAuthors Info & Claims

CCSW'19: Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop

Pages 81 - 92

https://doi.org/10.1145/3338466.3358922

Published: 11 November 2019 Publication History

Abstract

The concrete efficiency of secure computation has been the focus of many recent works. In this work, we present concretely-efficient protocols for secure 3-party computation (3PC) over a ring of integers modulo 2ℓ tolerating one corruption, both with semi-honest and malicious security. Owing to the fact that computation over ring emulates computation over the real-world system architectures, secure computation over ring has gained momentum of late.

Cast in the offline-online paradigm, our constructions present the most efficient online phase in concrete terms. In the semi-honest setting, our protocol requires communication of 2 ring elements per multiplication gate during the online phase. In the malicious setting, our protocol requires communication of 4 elements per multiplication gate during the online phase, beating the state-of-the-art protocol by 5 elements. Realized with both the security notions of selective abort and fairness, the malicious protocol with fairness involves a slightly more communication than its counterpart with abort security for the output gates alone.

We apply our techniques from 3PC in the regime of secure server-aided machine-learning (ML) inference for a range of prediction functions-- linear regression, linear SVM regression, logistic regression, and linear SVM classification. Our setting considers a model-owner with trained model parameters and a client with a query, with the latter willing to learn the prediction of her query based on the model parameters of the former. The inputs and computation are outsourced to a set of three non-colluding servers. Our constructions catering to both semi-honest and malicious world, invariably perform better than the existing constructions.

References

[1]

V. A. Abril, P. Maene, N. Mertens, and N. P. Smart. 2019. Bristol Fashion MPCCircuits. https://homes.esat.kuleuven.be/~nsmart/MPC/.

[2]

T. Araki, A. Barak, J. Furukawa, T. Lichter, Y. Lindell, A. Nof, K. Ohara, A. Watz-man, and O. Weinstein. 2017. Optimized Honest-Majority MPC for Malicious Adversaries - Breaking the 1 Billion-Gate Per Second Barrier. In IEEE S&P. 843--862.

[3]

T. Araki, A. Barak, J. Furukawa, Y. Lindell, A. Nof, and K. Ohara. 2016. DEMO: High-Throughput Secure Three-Party Computation of Kerberos Ticket Generation. In ACM CCS. 1841--1843.

Digital Library

[4]

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 ACMCCS. 805--817.

[5]

C. Baum, I. Damgård, T. Toft, and R. W. Zakarias. 2016. Better Preprocessing for Secure Multiparty Computation. In ACNS. 327--345.

[6]

D. Beaver. 1991. Efficient Multiparty Protocols Using Circuit Randomization. In CRYPTO. 420--432.

[7]

D. Beaver. 1995. Precomputing Oblivious Transfer. In CRYPTO. 97--109.

[8]

Z. Beerliová-Trubíniová and M. Hirt. 2006. Efficient Multi-party Computation with Dispute Control. In TCC. 305--328.

[9]

Z. Beerliová-Trubíniová and M. Hirt. 2008. Perfectly-Secure MPC with Linear Communication Complexity. In TCC. 213--230.

[10]

M. Ben-Or, S. Goldwasser, and A. Wigderson. 1988. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In ACM STOC. 1--10.

[11]

Christopher Bishop. 2006. Pattern Recognition and Machine Learning.

[12]

D. Bogdanov, S. Laur, and J. Willemson. 2008. Sharemind: A Framework for Fast Privacy-Preserving Computations. In ESORICS. 192--206.

[13]

D. Bogdanov, R. Talviste, and J. Willemson. 2012. Deploying Secure Multi-Party Computation for Financial Data Analysis. In FC. 57--64.

[14]

M. Byali, A. Joseph, A. Patra, and D. Ravi. 2018. Fast Secure Computation for Small Population over the Internet. ACM CCS(2018), 677--694.

[15]

O. Catrina and S. de Hoogh. 2010. Secure Multiparty Linear Programming Using Fixed-Point Arithmetic. In ESORICS. 134--150.

[16]

N. Chandran, J. A. Garay, P. Mohassel, and S. Vusirikala. 2017. Efficient, Constant-Round and Actively Secure MPC: Beyond the Three-Party Case. In ACM CCS.277--294.

[17]

H. Chaudhari, A. Choudhury, A. Patra, and A. Suresh. 2019. ASTRA: High-throughput 3PC over Rings with Application to Secure Prediction. https://eprint.iacr.org/2019/429. In IACR Cryptology ePrint Archive.

[18]

K. Chida, D. Genkin, K. Hamada, D. Ikarashi, R. Kikuchi, Y. Lindell, and A. Nof. 2018. Fast Large-Scale Honest-Majority MPC for Malicious Adversaries. In CRYPTO. 34--64.

[19]

A. Choudhury and A. Patra. 2017. An Efficient Framework for Unconditionally Secure Multiparty Computation. IEEE Trans. Information Theory(2017), 428--468.

[20]

R. Cleve. 1986. Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract). In ACM STOC. 364--369.

[21]

R. Cramer, I. Damgård, D. Escudero, P. Scholl, and C. Xing. 2018. SPDZ2k: Efficient MPC mod 2k for Dishonest Majority. CRYPTO(2018), 769--798.

[22]

R. Cramer, I. Damgård, and Y. Ishai. 2005. Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. In TCC. 342--362.

[23]

Cryptography and Privacy Engineering Group at TU Darmstadt. 2017. ENCRYPTO Utils. https://github.com/encryptogroup/ENCRYPTO_utils.

[24]

M. Dahl. 2018. Private Image Analysis with MPC: Training CNNs on Sensitive Data using SPDZ. (2018).

[25]

I. Damgård, C. Orlandi, and M. Simkin. 2018. Yet Another Compiler for ActiveSecurity or: Efficient MPC Over Arbitrary Rings. CRYPTO(2018), 799--829.

[26]

I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias. 2012. Multiparty Computation from Somewhat Homomorphic Encryption. In CRYPTO. 643--662.

[27]

S. de Hoogh, B. Schoenmakers, P.Chen, and H. Akker. 2014. Practical Secure Decision Tree Learning in a Tele treatment Application. In FC. 179--194.

[28]

H. Eerikson, M. Keller, C. Orlandi, P. Pullonen, J. Puura, and M. Simkin. 2019.Use your Brain! Arithmetic 3PC For Any Modulus with Active Security. IACR Cryptology ePrint Archive(2019).

[29]

A. Esteva, B. Kuprel, R. A. Novoa, J. Ko, S. M. Swetter, H. M. Blau, and S. Thrun. 2017. Dermatologist-level classification of skin cancer with deep neural networks. Nature(2017), 115--118.

[30]

J. Furukawa, Y. Lindell, A. Nof, and O. Weinstein. 2017. High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority. In EUROCRYPT. 225--255.

[31]

A. Gascón, P. Schoppmann, B. Balle, M. Raykova, J. Doerner, S. Zahur, and D.Evans. 2016. Secure Linear Regression on Vertically Partitioned Datasets. IACR Cryptology ePrint Archive(2016).

[32]

M. Geisler. 2007. Viff: Virtual ideal functionality framework.

[33]

O. Goldreich, S. Micali, and A. Wigderson. 1987. How to Play any Mental Game orA Completeness Theorem for Protocols with Honest Majority. In STOC. 218--229.

[34]

S. D. Gordon, S. Ranellucci, and X. Wang. 2018. Secure Computation with Low Communication from Cross-Checking. In ASIA CRYPT. 59--85.

[35]

Y. Ishai, R. Kumaresan, E. Kushilevitz, and A. Paskin-Cherniavsky. 2015. Secure Computation with Minimal Interaction, Revisited. In CRYPTO. 359--378.

[36]

S. Kamara, P. Mohassel, and M. Raykova. 2011. Outsourcing Multi-Party Computation. IACR Cryptology ePrint Archive(2011).

[37]

J. Katz, V. Kolesnikov, and X. Wang. 2018. Improved Non-Interactive Zero Knowl-edge with Applications to Post-Quantum Signatures. In CCS. 525--537.

[38]

M. Keller, E. Orsini, and P. Scholl. 2016. MASCOT: Faster Malicious ArithmeticSecure Computation with Oblivious Transfer. In ACM CCS. 830--842.

Digital Library

[39]

M. Keller, V. Pastro, and D. Rotaru. 2018. Overdrive: Making SPDZ Great Again. In EUROCRYPT. 158--189.

[40]

J. Launchbury, D. Archer, T. DuBuisson, and E. Mertens. 2014. Application-Scale Secure Multiparty Computation. In ESOP. 8--26.

[41]

S. Laur, H. Lipmaa, and T. Mielikäinen. 2006. Cryptographically private supportvector machines. In ACM SIGKDD. 618--624.

[42]

Yann LeCun and Corinna Cortes. 2010. MNIST handwritten digit database. (2010). http://yann.lecun.com/exdb/mnist/

[43]

Y. Lindell and A. Nof. 2017. A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority. In ACMCCS. 259--276.

[44]

J. Liu, M. Juuti, Y. L., and N. Asokan. 2017. Oblivious Neural Network Predictionsvia MiniONN Transformations. In ACM CCS. 619--631.

[45]

E. Makri, D. Rotaru, N. P. Smart, and F. Vercauteren. 2018. EPIC: Efficient Private Image Classification (or: Learning from the Masters). CT-RSA(2018), 473--492.

[46]

P. Mohassel and P. Rindal. 2018. ABY3: A Mixed Protocol Framework for Machine Learning. In ACM CCS. 35--52.

[47]

P. Mohassel, M. Rosulek, and Y. Zhang. 2015. Fast and Secure Three-party Computation: Garbled Circuit Approach. In CCS. 591--602.

[48]

P. Mohassel and Y. Zhang. 2017. Secure ML: A System for Scalable Privacy-Preserving Machine Learning. In IEEE S&P. 19--38.

[49]

V. Nikolaenko, S. Ioannidis, U. Weinsberg, M. Joye, N. Taft, and D. Boneh. 2013. Privacy-preserving matrix factorization. In ACM CCS. 801--812.

[50]

V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft. 2013. Privacy-Preserving Ridge Regression on Hundreds of Millions of Records. In IEEE S&P. 334--348.

[51]

P. S. Nordholt and M. Veeningen. 2018. Minimising Communication in Honest-Majority MPC by Batch wise Multiplication Verification. In ACNS. 321--339.

[52]

T. Orekondy, B. Schiele, and M. Fritz. 2018. Knockoff Nets: Stealing Functionality of Black-Box Models. CoRR(2018).

[53]

N. Papernot, P. McDaniel, I. Goodfellow, S. Jha, Z. B. Celik, and A. Swami. 2017. Practical Black-Box Attacks Against Machine Learning. In ASIA CCS. 506--519.

[54]

A. Patra and D. Ravi. 2018. On the Exact Round Complexity of Secure Three-Party Computation. CRYPTO(2018), 425--458.

[55]

M. S. Riazi, C. Weinert, O. Tkachenko, E. M. Songhori, T. Schneider, and F. Koushanfar. 2018. Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications. InAsiaCCS. 707--721.

Digital Library

[56]

F. Schroff, D. Kalenichenko, and J. Philbin. 2015. FaceNet: A unified embedding for face recognition and clustering. In IEEE CVPR. 815--823.

[57]

N. P. Smart and T. Wood. 2019. Error Detection in Monotone Span Programs with Application to Communication-Efficient Multi-party Computation. InCT-RSA.210--229.

[58]

F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart. 2016. Stealing Machine Learning Models via Prediction APIs. In USENIX. 601--618.

[59]

S. Wagh, D. Gupta, and N. Chandran. 2019. Secure NN: 3-Party Secure Computation for Neural Network Training. PoPETs(2019), 26--49.

[60]

A. C. Yao. 1982. Protocols for Secure Computations. In FOCS. 160--164.

Cited By

Qin HHe DFeng QKhan MLuo MChoo K(2024)Cryptographic Primitives in Privacy-Preserving Machine Learning: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.332180336:5(1919-1934)Online publication date: May-2024
https://doi.org/10.1109/TKDE.2023.3321803
Ben-Itzhak YMöllering HPinkas BSchneider TSuresh ATkachenko OVargaftik SWeinert CYalame HYanai A(2024)ScionFL: Efficient and Robust Secure Quantized Aggregation2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00031(490-511)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00031
Brüggemann ASchick OSchneider TSuresh AYalame H(2024)Don’t Eject the Impostor: Fast Three-Party Computation With a Known Cheater2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00164(503-522)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00164
Show More Cited By

Index Terms

ASTRA: High Throughput 3PC over Rings with Application to Secure Prediction
1. Security and privacy

Recommendations

The Resiliency of MPC with Low Interaction: The Benefit of Making Errors (Extended Abstract)
Theory of Cryptography
Abstract
We study information-theoretic secure multiparty protocols that achieve full security, including guaranteed output delivery, at the presence of an active adversary that corrupts a constant fraction of the parties. It is known that 2 rounds are ...
What Security Can We Achieve Within 4 Rounds?
Abstract
Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, ...
A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority
CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

Protocols 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. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCSW'19: Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop

November 2019

209 pages

ISBN:9781450368261

DOI:10.1145/3338466

Program Chairs:
Radu Sion
Stony Brook University, USA
,
Charalampos Papamanthou
University of Maryland, College Park, USA

Copyright © 2019 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: 11 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

SERB Women Excellence Award 2017 (DSTO 1706)
Visvesvaraya PhD Scheme of Ministry of Electronics & Information Technology Government of India

Conference

CCS '19

Sponsor:

SIGSAC

CCS '19: 2019 ACM SIGSAC Conference on Computer and Communications Security

November 11, 2019

London, United Kingdom

Acceptance Rates

Overall Acceptance Rate 37 of 108 submissions, 34%

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

57
Total Citations
View Citations
485
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)8

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qin HHe DFeng QKhan MLuo MChoo K(2024)Cryptographic Primitives in Privacy-Preserving Machine Learning: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.332180336:5(1919-1934)Online publication date: May-2024
https://doi.org/10.1109/TKDE.2023.3321803
Ben-Itzhak YMöllering HPinkas BSchneider TSuresh ATkachenko OVargaftik SWeinert CYalame HYanai A(2024)ScionFL: Efficient and Robust Secure Quantized Aggregation2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00031(490-511)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00031
Brüggemann ASchick OSchneider TSuresh AYalame H(2024)Don’t Eject the Impostor: Fast Three-Party Computation With a Known Cheater2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00164(503-522)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00164
Jawalkar NGupta KBasu AChandran NGupta DSharma R(2024)Orca: FSS-based Secure Training and Inference with GPUs2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00063(597-616)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00063
Qin HHe DFeng QYang XLuo Q(2024)Outsourced and Robust Multi-party Computation with Identifying Malicious Behavior and Application to Machine LearningInformation Security Practice and Experience10.1007/978-981-97-9053-1_18(310-328)Online publication date: 25-Oct-2024
https://doi.org/10.1007/978-981-97-9053-1_18
Zbudila MPohle EAbidin APreneel B(2024)MaSTer: Maliciously Secure Truncation for Replicated Secret Sharing Without Pre-processingCryptology and Network Security10.1007/978-981-97-8013-6_3(49-73)Online publication date: 24-Sep-2024
https://dl.acm.org/doi/10.1007/978-981-97-8013-6_3
Miao PShi XWu CXu R(2024)Client-Aided Privacy-Preserving Machine LearningSecurity and Cryptography for Networks10.1007/978-3-031-71070-4_10(207-229)Online publication date: 10-Sep-2024
https://doi.org/10.1007/978-3-031-71070-4_10
Bhimrajka NChakrabarti SChoudhury AVaradarajan S(2024)Privacy-Preserving Plagiarism CheckingProgress in Cryptology – INDOCRYPT 202310.1007/978-3-031-56235-8_6(105-125)Online publication date: 29-Mar-2024
https://doi.org/10.1007/978-3-031-56235-8_6
Attrapadung NHanaoaka GHiromasa RKoseki YMatsuda TNishida YSakai YSchuldt JYasuda S(2024)Privacy-Preserving Verifiable CNNsApplied Cryptography and Network Security10.1007/978-3-031-54773-7_15(373-402)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-54773-7_15
Cook JShyani MMishra NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Creating a public repository for joining private dataProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669244(71294-71326)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669244
Show More Cited By

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.

Media

Figures

Other

Tables

View Table of Contents