MPClan: protocol suite for privacy-conscious computations. (English) Zbl 1517.94120
Summary: The growing volumes of data being collected and its analysis to provide better services are creating worries about digital privacy. To address privacy concerns and give practical solutions, the literature has relied on secure multiparty computation techniques. However, recent research over rings has mostly focused on the small-party honest-majority setting of up to four parties tolerating single corruption, noting efficiency concerns. In this work, we extend the strategies to support higher resiliency in an honest-majority setting with efficiency of the online phase at the centre stage. Our semi-honest protocol improves the online communication of the protocol of I. Damgård and J. B. Nielsen [Lect. Notes Comput. Sci. 4622, 572–590 (2007; Zbl 1215.94041)] without inflating the overall communication. It also allows shutting down almost half of the parties in the online phase, thereby saving up to 50% in the system’s operational costs. Our maliciously secure protocol also enjoys similar benefits and requires only half of the parties, except for one-time verification towards the end, and provides security with fairness. To showcase the practicality of the designed protocols, we benchmark popular applications such as deep neural networks, graph neural networks, genome sequence matching, and biometric matching using prototype implementations. Our protocols, in addition to improved communication, aid in bringing up to 60–80% savings in monetary cost over prior work.
MSC:
| 94A60 | Cryptography |
| 94A62 | Authentication, digital signatures and secret sharing |
| 68P25 | Data encryption (aspects in computer science) |
| 68M12 | Network protocols |
| 68M14 | Distributed systems |
Keywords:
secure multiparty computation; honest majority; semi-honest protocol; maliciously secure protocol; ringsCitations:
Zbl 1215.94041References:
| [1] | M. Abspoel, R. Cramer, I. Damgård, D. Escudero, C. Yuan, Efficient information-theoretic secure multiparty computation over \({\mathbb{Z}}/p^k{\mathbb{Z}}\) via galois rings, in Theory of Cryptography Conference (2019) · Zbl 1455.94203 |
| [2] | M. Abspoel, A.P.K. Dalskov, D. Escudero, A. Nof, An efficient passive-to-active compiler for honest-majority MPC over rings, in ACNS (2021) · Zbl 1490.68077 |
| [3] | A. Aly, E. Orsini, D. Rotaru, N.P. Smart, T. Wood, Zaphod: efficiently combining LSSS and garbled circuits in SCALE, in ACM WAHC@CCS (2019) |
| [4] | T. Araki, A. Barak, J. Furukawa, T. Lichter, Y. Lindell, A. Nof, K. Ohara, A. Watzman, O. Weinstein, Optimized honest-majority MPC for malicious adversaries—breaking the 1 billion-gate per second barrier, in IEEE S &P (2017) |
| [5] | T. Araki, J. Furukawa, Y. Lindell, A. Nof, K. Ohara, High-throughput semi-honest secure three-party computation with an honest majority, in ACM CCS (2016) · Zbl 07707563 |
| [6] | G. Asharov, S. Halevi, Y. Lindell, T. Rabin, Privacy-preserving search of similar patients in genomic data, in PETS (2018) |
| [7] | A. Baccarini, M. Blanton, C. Yuan, Multi-party replicated secret sharing over a ring with applications to privacy-preserving machine learning, ePrint Archive (2020). https://eprint.iacr.org/2020/1577 |
| [8] | C. Baum, I. Damgård, T. Toft, R.W. Zakarias, Better preprocessing for secure multiparty computation, in ACNS (2016) · Zbl 1346.68085 |
| [9] | A. Ben-Efraim, Y. Lindell, E. Omri, Optimizing semi-honest secure multiparty computation for the internet, in CCS (2016) |
| [10] | A. Ben-Efraim, M. Nielsen, E. Omri, Turbospeedz: double your online spdz! improving SPDZ using function dependent preprocessing, in ACNS (2019) · Zbl 1458.94294 |
| [11] | A. Ben-Efraim, E. Omri, Concrete efficiency improvements for multiparty garbling with an honest majority, in LATINCRYPT (2017) · Zbl 1454.94048 |
| [12] | M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in STOC (1988) |
| [13] | M. Blanton, A. Kang, C. Yuan, Improved building blocks for secure multi-party computation based on secret sharing with honest majority, in ACNS (2020) · Zbl 07314292 |
| [14] | D. Bogdanov, S. Laur, J. Willemson, Sharemind: a framework for fast privacy-preserving computations, in ESORICS (2008) |
| [15] | D. Boneh, E. Boyle, H. Corrigan-Gibbs, N. Gilboa, Y. Ishai, Zero-knowledge proofs on secret-shared data via fully linear PCPs, in CRYPTO (2019) · Zbl 1436.94043 |
| [16] | E. Boyle, N. Gilboa, Y. Ishai, A. Nof, Practical fully secure three-party computation via sublinear distributed zero-knowledge proofs, in ACM CCS (2019) · Zbl 1511.94062 |
| [17] | E. Boyle, N. Gilboa, Y. Ishai, A. Nof, Efficient fully secure computation via distributed zero-knowledge proofs, in ASIACRYPT (2020) · Zbl 1511.94062 |
| [18] | Z. Brakerski, C. Gentry, V. Vaikuntanathan, (Leveled) Fully homomorphic encryption without bootstrapping, ACM Trans. Comput. Theory (2014) · Zbl 1347.68121 |
| [19] | L. Braun, D. Demmler, T. Schneider, O. Tkachenko, Motion—a framework for mixed-protocol multi-party computation, ACM Trans. Privacy Secur. (2022) |
| [20] | M. Byali, H. Chaudhari, A. Patra, A. Suresh, FLASH: fast and robust framework for privacy-preserving machine learning, in PETS (2020) |
| [21] | S. Carpov, K. Deforth, N. Gama, M. Georgieva, D. Jetchev, J. Katz, I. Leontiadis, M. Mohammadi, A. Sae-Tang, M. Vuille, Manticore: efficient framework for scalable secure multiparty computation protocols, ePrint Archive (2021). https://eprint.iacr.org/2021/200 · Zbl 07730739 |
| [22] | O. Catrina, S.D. Hoogh, Improved primitives for secure multiparty integer computation, in SCN (2010) · Zbl 1291.94183 |
| [23] | O. Catrina, A. Saxena, Secure computation with fixed-point numbers, in FC (2010) |
| [24] | N. Chandran, N. Dasgupta, D. Gupta, S.L.B. Obbattu, S. Sekar, A. Shah, Efficient linear multiparty PSI and extensions to circuit/quorum PSI, in ACM CCS (2021) |
| [25] | H. Chaudhari, A. Choudhury, A. Patra, A. Suresh, ASTRA: high throughput 3PC over rings with application to secure prediction, in ACM CCSW@CCS (2019) |
| [26] | H. Chaudhari, R. Rachuri, A. Suresh, Trident: efficient 4PC framework for privacy preserving machine learning, in NDSS (2020) |
| [27] | K. Chida, D. Genkin, K. Hamada, D. Ikarashi, R. Kikuchi, Y. Lindell, A. Nof, Fast large-scale honest-majority MPC for malicious adversaries, in CRYPTO (2018) · Zbl 1446.94118 |
| [28] | P. Covington, J. Adams, E. Sargin, Deep neural networks for youtube recommendations, in RecSys (2016) |
| [29] | R. Cramer, I. Damgård, D. Escudero, P. Scholl, C. Xing, SPD \({\mathbb{Z}}_{2^k} \): efficient MPC mod \(2^k\) for dishonest majority, in CRYPTO (2018) · Zbl 1436.94049 |
| [30] | R. Cramer, I. Damgård, Y. Ishai, Share conversion, pseudorandom secret-sharing and applications to secure computation, in TCC (2005) · Zbl 1079.94541 |
| [31] | Cryptography, at TU Darmstadt, P.E.G.: ENCRYPTO Utils (2017). https://github.com/encryptogroup/ENCRYPTO_utils |
| [32] | A. Dalskov, D. Escudero, M. Keller, Fantastic four: honest-majority four-party secure computation with malicious security, in USENIX Security (2021) |
| [33] | I. Damgård, D. Escudero, T.K. Frederiksen, M. Keller, P. Scholl, N. Volgushev, New primitives for actively-secure MPC over rings with applications to private machine learning, in IEEE S &P (2019) |
| [34] | I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, N.P. Smart, Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits, in ESORICS (2013) · Zbl 1406.94041 |
| [35] | I. Damgård, J.B. Nielsen, Scalable and unconditionally secure multiparty computation, in CRYPTO (2007) · Zbl 1215.94041 |
| [36] | I. Damgård, C. Orlandi, M. Simkin, Yet another compiler for active security or: efficient MPC over arbitrary rings, in CRYPTO (2018) · Zbl 1436.94050 |
| [37] | I. Damgård, V. Pastro, N.P. Smart, S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in CRYPTO (2012) · Zbl 1296.94104 |
| [38] | E. Dans, How signal cleverly exposed Facebook’s disregard for privacy, in Forbes (2021). https://www.forbes.com/sites/enriquedans/2021/05/07/how-signal-cleverly-exposed-facebooks-disregard-forprivacy |
| [39] | M. Defferrard, X. Bresson, P. Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering, in NeurIPS (2016) |
| [40] | D. Demmler, T. Schneider, M. Zohner, ABY—a framework for efficient mixed-protocol secure two-party computation, in NDSS (2015) |
| [41] | D. Dolev, H.R. Strong, Authenticated algorithms for Byzantine agreement, SIAM J. Comput. (1983) · Zbl 0524.68021 |
| [42] | C. Dwork, Differential privacy: a survey of results, in TAMC (2008) · Zbl 1139.68339 |
| [43] | Z. Erkin, M. Franz, J. Guajardo, S. Katzenbeisser, I. Lagendijk, T. Toft, Privacy-preserving face recognition, in PETS (2009) |
| [44] | D. Escudero, A. Dalskov, Honest majority MPC with abort with minimal online communication, in LATINCRYPT (2021) · Zbl 1491.94004 |
| [45] | J. Furukawa, Y. Lindell, A. Nof, O. Weinstein, High-throughput secure three-party computation for malicious adversaries and an honest majority, in EUROCRYPT (2017) · Zbl 1415.94431 |
| [46] | D. Genkin, Y. Ishai, M.M. Prabhakaran, A. Sahai, E. Tromer, Circuits resilient to additive attacks with applications to secure computation, in STOC (2014) · Zbl 1315.94073 |
| [47] | C. Gentry, A. Sahai, B. Waters, Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based, in CRYPTO (2013) · Zbl 1310.94148 |
| [48] | O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications (Cambridge University Press, 2009) · Zbl 1179.94063 |
| [49] | O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or A completeness theorem for protocols with honest majority, in STOC (1987) |
| [50] | S.D. Gordon, S. Ranellucci, X. Wang, Secure computation with low communication from cross-checking, in ASIACRYPT (2018) · Zbl 1447.94041 |
| [51] | S.D. Gordon, D. Starin, A. Yerukhimovich, The more the merrier: reducing the cost of large scale MPC, in EUROCRYPT (2021) · Zbl 07440624 |
| [52] | V. Goyal, H. Li, R. Ostrovsky, A. Polychroniadou, Y. Song, ATLAS: efficient and scalable MPC in the honest majority setting, in CRYPTO (2021) · Zbl 1486.94104 |
| [53] | V. Goyal, Y. Liu, Y. Song, Communication-efficient unconditional MPC with guaranteed output delivery, in CRYPTO (2019) · Zbl 1478.68093 |
| [54] | V. Goyal, Y. Song, Malicious security comes free in honest-majority MPC, in CRYPTO (2020) · Zbl 1504.94143 |
| [55] | G. Guido, M.I. Prete, S. Miraglia, I. De Mare, Targeting direct marketing campaigns by neural networks, J. Market. Manag. (2011) |
| [56] | W. Henecka, T. Schneider, Faster secure two-party computation with less memory, in AsiaCCS (2013) |
| [57] | M. Ito, A. Saito, T. Nishizeki, Secret sharing scheme realizing general access structure. Electron. Commun. Japan (Part III: Fundamental Electronic Science) (1989) |
| [58] | J. Katz, V. Kolesnikov, X. Wang, Improved non-interactive zero knowledge with applications to post-quantum signatures, in CCS (2018) |
| [59] | M. Keller, E. Orsini, P. Scholl, MASCOT: faster malicious arithmetic secure computation with oblivious transfer, in CCS (2016) |
| [60] | M. Keller, V. Pastro, D. Rotaru, Overdrive: making SPDZ great again, in EUROCRYPT (2018) · Zbl 1415.94446 |
| [61] | M. Keller, P. Scholl, N.P. Smart, An architecture for practical actively secure MPC with dishonest majority, in CCS (2013) |
| [62] | T.N. Kipf, M. Welling, Semi-supervised classification with graph convolutional networks, in ICLR (2017) |
| [63] | N. Koti, M. Pancholi, A. Patra, A. Suresh, SWIFT: super-fast and robust privacy-preserving machine learning, in USENIX Security (2021) |
| [64] | N. Koti, A. Patra, R. Rachuri, A. Suresh, Tetrad: actively secure 4PC for secure training and inference, in NDSS (2022) |
| [65] | A. Krizhevsky, V. Nair, G. Hinton, The CIFAR-10 dataset (2014). https://www.cs.toronto.edu/ kriz/cifar.html |
| [66] | A. Lapets, N. Volgushev, A. Bestavros, F. Jansen, M. Varia, Secure MPC for analytics as a web application, in IEEE SecDev (2016) |
| [67] | Y. LeCun, L. Bottou, Y. Bengio, P. Haffner, Gradient-based learning applied to document recognition, in Proceedings of the IEEE (1998) |
| [68] | Y. LeCun, C. Cortes, MNIST handwritten digit database (2010). http://yann.lecun.com/exdb/mnist/ |
| [69] | C. Li, B. Pang, Y. Liu, H. Sun, Z. Liu, X. Xie, T. Yang, Y. Cui, L. Zhang, Q. Zhang, Adsgnn: behavior-graph augmented relevance modeling in sponsored search, in SIGIR (2021) |
| [70] | Y. Lindell, How to simulate it—a tutorial on the simulation proof technique, in Tutorials on the Foundations of Cryptography (2017) · Zbl 1481.94111 |
| [71] | Y. Lindell, B. Pinkas, N.P. Smart, A. Yanai, Efficient constant round multi-party computation combining BMR and SPDZ, in CRYPTO (2015) · Zbl 1352.94049 |
| [72] | M. Malone, How Does Facebook Know What Ads to Show You? (Example). Vici Media (2021). https://www.vicimediainc.com/how-does-facebook-know-what-ads-to-show-you/ |
| [73] | S. Mazloom, P.H. Le, S. Ranellucci, S.D. Gordon, Secure parallel computation on national scale volumes of data, in USENIX Security (2020) |
| [74] | P. Miao, S. Patel, M. Raykova, K. Seth, M. Yung, Two-sided malicious security for private intersection-sum with cardinality, in CRYPTO (2020) · Zbl 1504.94170 |
| [75] | P. Mohassel, P. Rindal, ABY \({}^{\text{3}} \): a mixed protocol framework for machine learning, in CCS (2018) |
| [76] | P. Mohassel, M. Rosulek, Y. Zhang, Fast and secure three-party computation: the garbled circuit approach, in CCS (2015) |
| [77] | P. Mohassel, Y. Zhang, SecureML: a system for scalable privacy-preserving machine learning, in IEEE S &P (2017) |
| [78] | S. Ohata, K. Nuida, Communication-efficient (client-aided) secure two-party protocols and its application, in FC (2020) · Zbl 1459.94137 |
| [79] | K. Park, J. Lee, J. Choi, Deep neural networks for news recommendations, in CIKM (2017) |
| [80] | A. Patra, T. Schneider, A. Suresh, H. Yalame, ABY2.0: improved mixed-protocol secure two-party computation, in USENIX Security (2021) |
| [81] | A. Patra, A. Suresh, BLAZE: blazing fast privacy-preserving machine learning, in NDSS (2020) |
| [82] | R. Poddar, S. Kalra, A. Yanai, R. Deng, R.A. Popa, J.M. Hellerstein, Senate: a maliciously-secure MPC platform for collaborative analytics, in USENIX Security (2021) |
| [83] | M.S. Riazi, C. Weinert, O. Tkachenko, E.M. Songhori, T. Schneider, F. Koushanfar, Chameleon: a hybrid secure computation framework for machine learning applications, in AsiaCCS (2018) |
| [84] | P. Rogaway, T. Shrimpton, Cryptographic Hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance, in FSE (2004) · Zbl 1079.68560 |
| [85] | D. Rotaru, T. Wood, MArBled circuits: mixing arithmetic and Boolean circuits with active security, in INDOCRYPT (2019) · Zbl 1453.68082 |
| [86] | T. Schneider, O. Tkachenko, EPISODE: efficient privacy-preserving similar sequence queries on outsourced genomic databases, in AsiaCCS (2019) |
| [87] | G.C.C. Services, Google cloud platform, network costs (2008). https://cloud.google.com/vpc/network-pricing, Computation costs. https://cloud.google.com/compute/vm-instance-pricing |
| [88] | A. Shamir, How to Share a Secret Communication (ACM, 1979), pp. 612-613 · Zbl 0414.94021 |
| [89] | S. Sharma, C. Xing, Y. Liu, Privacy-preserving deep learning with SPDZ (2019) |
| [90] | L. Shen, X. Chen, J. Shi, Y. Dong, B. Fang, An efficient 3-party framework for privacy-preserving neural network inference, in ESORICS (2020) |
| [91] | K. Simonyan, A. Zisserman, Very deep convolutional networks for large-scale image recognition, in ICLR (2015) |
| [92] | J. So, B. Güler, A.S. Avestimehr, CodedPrivateML: a fast and privacy-preserving framework for distributed machine learning, IEEE J. Sel. Areas Inf. Theory (2021) |
| [93] | A. Suresh, MPCLeague: robust MPC platform for privacy-preserving machine learning, PhD Thesis (2021). https://arxiv.org/pdf/2112.13338 |
| [94] | S. Wagh, S. Tople, F. Benhamouda, E. Kushilevitz, P. Mittal, T. Rabin, FALCON: honest-majority maliciously secure framework for private deep learning, in PETS (2020) |
| [95] | R.A. Wagner, M.J. Fischer, The string-to-string correction problem, J. ACM (1974) · Zbl 0278.68032 |
| [96] | X. Wang, S. Ranellucci, J. Katz, Authenticated garbling and efficient maliciously secure two-party computation, in CCS (2017) |
| [97] | J. Yang, Z. Liu, S. Xiao, C. Li, D. Lian, S. Agrawal, A. Singh, G. Sun, X. Xie, Graphformers: Gnn-nested transformers for representation learning on textual graph, in NeurIPS (2021) |
| [98] | A.C. Yao, Protocols for secure computations (extended abstract), in FOCS (1982) |
| [99] | J. Zhu, Y. Cui, Y. Liu, H. Sun, X. Li, M. Pelger, T. Yang, L. Zhang, R. Zhang, H. Zhao, Textgnn: improving text encoder via graph neural network in sponsored search, in WWW (2021) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
