1. bookVolume 2022 (2022): Issue 1 (January 2022)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

Polymath: Low-Latency MPC via Secure Polynomial Evaluations and Its Applications

Published Online: 20 Nov 2021
Page range: 396 - 416
Received: 31 May 2021
Accepted: 16 Sep 2021
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

While the practicality of secure multi-party computation (MPC) has been extensively analyzed and improved over the past decade, we are hitting the limits of efficiency with the traditional approaches of representing the computed functionalities as generic arithmetic or Boolean circuits. This work follows the design principle of identifying and constructing fast and provably-secure MPC protocols to evaluate useful high-level algebraic abstractions; thus, improving the efficiency of all applications relying on them. We present Polymath, a constant-round secure computation protocol suite for the secure evaluation of (multi-variate) polynomials of scalars and matrices, functionalities essential to numerous data-processing applications. Using precise natural precomputation and high-degree of parallelism prevalent in the modern computing environments, Polymath can make latency of secure polynomial evaluations of scalars and matrices independent of polynomial degree and matrix dimensions.

We implement our protocols over the HoneyBadgerMPC library and apply it to two prominent secure computation tasks: privacy-preserving evaluation of decision trees and privacy-preserving evaluation of Markov processes. For the decision tree evaluation problem, we demonstrate the feasibility of evaluating high-depth decision tree models in a general n-party setting. For the Markov process application, we demonstrate that Poly-math can compute large powers of transition matrices with better online time and less communication.


[1] Amazon ec2 instance network bandwidth. https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/ec2-instance-network-bandwidth.html. Search in Google Scholar

[2] Adi Akavia, Max Leibovich, Yehezkel S. Resheff, Roey Ron, Moni Shahar, and Margarita Vald. Privacy-preserving decision tree training and prediction against malicious server. Cryptology ePrint Archive, Report 2019/1282, 2019. https://eprint.iacr.org/2019/1282. Search in Google Scholar

[3] J. Bar-Ilan and D. Beaver. Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, PODC ’89, page 201–209, 1989.10.1145/72981.72995 Search in Google Scholar

[4] Assi Barak, Martin Hirt, Lior Koskas, and Yehuda Lindell. An end-to-end system for large scale p2p mpc-as-a-service and low-bandwidth mpc for weak participants. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 695–712, 2018.10.1145/3243734.3243801 Search in Google Scholar

[5] Donald Beaver. Efficient multiparty protocols using circuit randomization. In Annual International Cryptology Conference, pages 420–432. Springer, 1991.10.1007/3-540-46766-1_34 Search in Google Scholar

[6] Donald Beaver. Efficient multiparty protocols using circuit randomization. In Advances in Cryptology – CRYPTO’91, pages 420–432, August 11–15, 1992.10.1007/3-540-46766-1_34 Search in Google Scholar

[7] Zuzana Beerliová-Trubíniová and Martin Hirt. Perfectly-secure mpc with linear communication complexity. In Theory of Cryptography, pages 213–230, 2008.10.1007/978-3-540-78524-8_13 Search in Google Scholar

[8] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, page 1–10, New York, NY, USA, 1988. Association for Computing Machinery.10.1145/62212.62213 Search in Google Scholar

[9] Justin Brickell, Donald E Porter, Vitaly Shmatikov, and Emmett Witchel. Privacy-preserving remote diagnostics. In Proceedings of the 14th ACM conference on Computer and communications security, pages 498–507, 2007.10.1145/1315245.1315307 Search in Google Scholar

[10] Owen Brown and David Joseph. Secure digital escrow account transactions system and method, June 5 2003. US Patent App. 10/010,340. Search in Google Scholar

[11] Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, and Reto Strobl. Asynchronous verifiable secret sharing and proactive cryptosystems. In Proceedings of the 9th ACM Conference on Computer and Communications Security, pages 88–97, 2002.10.1145/586110.586124 Search in Google Scholar

[12] John Cartlidge, Nigel P. Smart, and Younes Talibi Alaoui. Mpc joins the dark side. Cryptology ePrint Archive, Report 2018/1045, 2018. https://eprint.iacr.org/2018/1045. Search in Google Scholar

[13] Octavian Catrina and Sebastiaan de Hoogh. Improved primitives for secure multiparty integer computation. In Juan A. Garay and Roberto De Prisco, editors, Security and Cryptography for Networks, pages 182–199, 2010.10.1007/978-3-642-15317-4_13 Search in Google Scholar

[14] Octavian Catrina and Amitabh Saxena. Secure computation with fixed-point numbers. In Radu Sion, editor, Financial Cryptography and Data Security, pages 35–50, 2010.10.1007/978-3-642-14577-3_6 Search in Google Scholar

[15] Richard Cleve. Limits on the security of coin flips when half the processors are faulty (extended abstract). pages 364–369, 1986.10.1145/12130.12168 Search in Google Scholar

[16] European Commission. 2018 reform of eu data protection rules. Search in Google Scholar

[17] Sandro Coretti, Juan Garay, Martin Hirt, and Vassilis Zikas. Constant-round asynchronous multi-party computation based on one-way functions. In Advances in Cryptology — ASIACRYPT 2016, page 998–1021, 2016.10.1007/978-3-662-53890-6_33 Search in Google Scholar

[18] Ronald Cramer and Ivan Damgård. Secure distributed linear algebra in a constant number of rounds. In Joe Kilian, editor, Advances in Cryptology – CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 119–136, Santa Barbara, CA, USA, August 19–23, 2001. Springer, Heidelberg, Germany.10.1007/3-540-44647-8_7 Search in Google Scholar

[19] Ronald Cramer, Ivan Damgård, and Ueli Maurer. General secure multi-party computation from any linear secret-sharing scheme. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 316–334. Springer, 2000.10.1007/3-540-45539-6_22 Search in Google Scholar

[20] Dana Dachman-Soled, Tal Malkin, Mariana Raykova, and Moti Yung. Secure efficient multiparty computing of multivariate polynomials and applications. In Javier Lopez and Gene Tsudik, editors, ACNS 11: 9th International Conference on Applied Cryptography and Network Security, volume 6715 of Lecture Notes in Computer Science, pages 130–146, Nerja, Spain, June 7–10, 2011. Springer, Heidelberg, Germany.10.1007/978-3-642-21554-4_8 Search in Google Scholar

[21] I. Damgard, V. Pastro, N.P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. Cryptology ePrint Archive, Report 2011/535, 2011. https://eprint.iacr.org/2011/535. Search in Google Scholar

[22] Ivan Damgård, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, and Tomas Toft. Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 285–304, 2006.10.1007/11681878_15 Search in Google Scholar

[23] I. Damgård, D. Escudero, T. Frederiksen, M. Keller, P. Scholl, and N. Volgushev. New primitives for actively-secure mpc over rings with applications to private machine learning. In 2019 IEEE Symposium on Security and Privacy (SP), pages 1102–1120, 2019.10.1109/SP.2019.00078 Search in Google Scholar

[24] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. Search in Google Scholar

[25] Irene Giacomelli, Somesh Jha, Ross Kleiman, David Page, and Kyonghwan Yoon. Privacy-preserving collaborative prediction using random forests. CoRR, abs/1811.08695, 2018. Search in Google Scholar

[26] Eric Goldman. An introduction to the california consumer privacy act (ccpa). Santa Clara Univ. Legal Studies Research Paper, 2020. Search in Google Scholar

[27] Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In 41st Annual Symposium on Foundations of Computer Science, pages 294–304, 01 2000. Search in Google Scholar

[28] Matthew Jones. Estimating markov transition matrices using proportions data: An application to credit risk. IMF Working Papers, 05, 01 2006.10.5089/9781451862386.001 Search in Google Scholar

[29] Marc Joye and Fariborz Salehi. Private yet efficient decision tree evaluation. In IFIP Annual Conference on Data and Applications Security and Privacy, pages 243–259. Springer, 2018.10.1007/978-3-319-95729-6_16 Search in Google Scholar

[30] Marcel Keller. MP-SPDZ: A versatile framework for multi-party computation. Cryptology ePrint Archive, Report 2020/521, 2020. https://eprint.iacr.org/2020/521.10.1145/3372297.3417872 Search in Google Scholar

[31] Benjamin Kuykendall, Hugo Krawczyk, and Tal Rabin. Cryptography for #metoo. Proceedings on Privacy Enhancing Technologies, 2019(3):409 – 429, 2019.10.2478/popets-2019-0054 Search in Google Scholar

[32] Donghang Lu, Thomas Yurek, Samarth Kulshreshtha, Rahul Govind, Aniket Kate, and Andrew Miller. Honeybadgermpc and asynchromix: Practical asynchronous mpc and its application to anonymous communication. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS ’19, page 887–903, New York, NY, USA, 2019. Association for Computing Machinery. Search in Google Scholar

[33] Jack P. K. Ma, Raymond K. H. Tai, Yongjun Zhao, and Sherman S.M. Chow. Let’s stride blindfolded in a forest: Sublinear multi-client decision trees evaluation. In ISOC Network and Distributed System Security Symposium – NDSS 2021. The Internet Society, 2021. Search in Google Scholar

[34] F. Massacci, C. N. Ngo, J. Nie, D. Venturi, and J. Williams. Futuresmex: Secure, distributed futures market exchange. In 2018 IEEE Symposium on Security and Privacy (SP), pages 335–353, 2018.10.1109/SP.2018.00028 Search in Google Scholar

[35] P. Mohassel and Y. Zhang. SecureML: a system for scalable privacy-preserving machine learning. In 2017 IEEE Symposium on Security and Privacy (SP), pages 19–38, 2017.10.1109/SP.2017.12 Search in Google Scholar

[36] Payman Mohassel and Matthew Franklin. Efficient polynomial operations in the shared-coefficients setting. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, PKC 2006: 9th International Conference on Theory and Practice of Public Key Cryptography, volume 3958 of Lecture Notes in Computer Science, pages 44–57, New York, NY, USA, April 24–26, 2006. Springer, Heidelberg, Germany. Search in Google Scholar

[37] Payman Mohassel and Peter Rindal. Aby3: A mixed protocol framework for machine learning. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, page 35–52, New York, NY, USA, 2018. Association for Computing Machinery. Search in Google Scholar

[38] Hadad Muliaman, Wimboh Santoso, Bagus Santoso, Dwityapoetra Besar, and Ita Rulina. Rating migration matrices: empirical evidence in indonesia. IFC Bulletin, 01 2009. Search in Google Scholar

[39] Takashi Nishide and Kazuo Ohta. Multiparty computation for interval, equality, and comparison without bit-decomposition protocol. In Tatsuaki Okamoto and Xiaoyun Wang, editors, Public Key Cryptography – PKC 2007, pages 343–360, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.10.1007/978-3-540-71677-8_23 Search in Google Scholar

[40] Rahul Rachuri and Ajith Suresh. Trident: Efficient 4pc framework for privacy preserving machine learning. Cryptology ePrint Archive, Report 2019/1315, 2019. https://eprint.iacr.org/2019/1315. Search in Google Scholar

[41] Adi Shamir. How to share a secret. Commun. ACM, 22(11):612–613, November 1979.10.1145/359168.359176 Search in Google Scholar

[42] Anselme Tueno, Florian Kerschbaum, and Stefan Katzenbeisser. Private evaluation of decision trees using sublinear cost. Proceedings on Privacy Enhancing Technologies, 2019(1):266–286, 2019.10.2478/popets-2019-0015 Search in Google Scholar

[43] Sameer Wagh, Divya Gupta, and Nishanth Chandran. Securenn: 3-party secure computation for neural network training. Proceedings on Privacy Enhancing Technologies, 2019(3):26 – 49, 2019. Search in Google Scholar

[44] David J. Wu, Tony Feng, Michael Naehrig, and Kristin Lauter. Privately evaluating decision trees and random forests. Proceedings on Privacy Enhancing Technologies, 2016(4), 2016.10.1515/popets-2016-0043 Search in Google Scholar

[45] Ágnes Kiss, Masoud Naderpour, Jian Liu, N. Asokan, and Thomas Schneider. Sok: Modular and efficient private decision tree evaluation. Proceedings on Privacy Enhancing Technologies, 2019(2):187 – 208, 2019. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo