{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T09:10:57Z","timestamp":1746781857177},"reference-count":45,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"1","license":[{"start":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T00:00:00Z","timestamp":1637366400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p><jats:p>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<jats:italic>n<\/jats:italic>-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.<\/jats:p>","DOI":"10.2478\/popets-2022-0020","type":"journal-article","created":{"date-parts":[[2021,11,21]],"date-time":"2021-11-21T02:44:19Z","timestamp":1637462659000},"page":"396-416","source":"Crossref","is-referenced-by-count":5,"title":["Polymath: Low-Latency MPC via Secure Polynomial Evaluations and Its Applications"],"prefix":"10.56553","volume":"2022","author":[{"given":"Donghang","family":"Lu","sequence":"first","affiliation":[{"name":"Purdue University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Albert","family":"Yu","sequence":"additional","affiliation":[{"name":"Purdue University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aniket","family":"Kate","sequence":"additional","affiliation":[{"name":"Purdue University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hemanta","family":"Maji","sequence":"additional","affiliation":[{"name":"Purdue University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"35752","published-online":{"date-parts":[[2021,11,20]]},"reference":[{"key":"2022062314360137076_j_popets-2022-0020_ref_001","unstructured":"[1] Amazon ec2 instance network bandwidth. https:\/\/docs.aws.amazon.com\/AWSEC2\/latest\/UserGuide\/ec2-instance-network-bandwidth.html."},{"key":"2022062314360137076_j_popets-2022-0020_ref_002","unstructured":"[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."},{"key":"2022062314360137076_j_popets-2022-0020_ref_003","doi-asserted-by":"crossref","unstructured":"[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 \u201989, page 201\u2013209, 1989.10.1145\/72981.72995","DOI":"10.1145\/72981.72995"},{"key":"2022062314360137076_j_popets-2022-0020_ref_004","doi-asserted-by":"crossref","unstructured":"[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\u2013712, 2018.10.1145\/3243734.3243801","DOI":"10.1145\/3243734.3243801"},{"key":"2022062314360137076_j_popets-2022-0020_ref_005","doi-asserted-by":"crossref","unstructured":"[5] Donald Beaver. Efficient multiparty protocols using circuit randomization. In Annual International Cryptology Conference, pages 420\u2013432. Springer, 1991.10.1007\/3-540-46766-1_34","DOI":"10.1007\/3-540-46766-1_34"},{"key":"2022062314360137076_j_popets-2022-0020_ref_006","doi-asserted-by":"crossref","unstructured":"[6] Donald Beaver. Efficient multiparty protocols using circuit randomization. In Advances in Cryptology \u2013 CRYPTO\u201991, pages 420\u2013432, August 11\u201315, 1992.10.1007\/3-540-46766-1_34","DOI":"10.1007\/3-540-46766-1_34"},{"key":"2022062314360137076_j_popets-2022-0020_ref_007","doi-asserted-by":"crossref","unstructured":"[7] Zuzana Beerliov\u00e1-Trub\u00edniov\u00e1 and Martin Hirt. Perfectly-secure mpc with linear communication complexity. In Theory of Cryptography, pages 213\u2013230, 2008.10.1007\/978-3-540-78524-8_13","DOI":"10.1007\/978-3-540-78524-8_13"},{"key":"2022062314360137076_j_popets-2022-0020_ref_008","doi-asserted-by":"crossref","unstructured":"[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 \u201988, page 1\u201310, New York, NY, USA, 1988. Association for Computing Machinery.10.1145\/62212.62213","DOI":"10.1145\/62212.62213"},{"key":"2022062314360137076_j_popets-2022-0020_ref_009","doi-asserted-by":"crossref","unstructured":"[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\u2013507, 2007.10.1145\/1315245.1315307","DOI":"10.1145\/1315245.1315307"},{"key":"2022062314360137076_j_popets-2022-0020_ref_010","unstructured":"[10] Owen Brown and David Joseph. Secure digital escrow account transactions system and method, June 5 2003. US Patent App. 10\/010,340."},{"key":"2022062314360137076_j_popets-2022-0020_ref_011","doi-asserted-by":"crossref","unstructured":"[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\u201397, 2002.10.1145\/586110.586124","DOI":"10.1145\/586110.586124"},{"key":"2022062314360137076_j_popets-2022-0020_ref_012","unstructured":"[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."},{"key":"2022062314360137076_j_popets-2022-0020_ref_013","doi-asserted-by":"crossref","unstructured":"[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\u2013199, 2010.10.1007\/978-3-642-15317-4_13","DOI":"10.1007\/978-3-642-15317-4_13"},{"key":"2022062314360137076_j_popets-2022-0020_ref_014","doi-asserted-by":"crossref","unstructured":"[14] Octavian Catrina and Amitabh Saxena. Secure computation with fixed-point numbers. In Radu Sion, editor, Financial Cryptography and Data Security, pages 35\u201350, 2010.10.1007\/978-3-642-14577-3_6","DOI":"10.1007\/978-3-642-14577-3_6"},{"key":"2022062314360137076_j_popets-2022-0020_ref_015","doi-asserted-by":"crossref","unstructured":"[15] Richard Cleve. Limits on the security of coin flips when half the processors are faulty (extended abstract). pages 364\u2013369, 1986.10.1145\/12130.12168","DOI":"10.1145\/12130.12168"},{"key":"2022062314360137076_j_popets-2022-0020_ref_016","unstructured":"[16] European Commission. 2018 reform of eu data protection rules."},{"key":"2022062314360137076_j_popets-2022-0020_ref_017","doi-asserted-by":"crossref","unstructured":"[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 \u2014 ASIACRYPT 2016, page 998\u20131021, 2016.10.1007\/978-3-662-53890-6_33","DOI":"10.1007\/978-3-662-53890-6_33"},{"key":"2022062314360137076_j_popets-2022-0020_ref_018","doi-asserted-by":"crossref","unstructured":"[18] Ronald Cramer and Ivan Damg\u00e5rd. Secure distributed linear algebra in a constant number of rounds. In Joe Kilian, editor, Advances in Cryptology \u2013 CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 119\u2013136, Santa Barbara, CA, USA, August 19\u201323, 2001. Springer, Heidelberg, Germany.10.1007\/3-540-44647-8_7","DOI":"10.1007\/3-540-44647-8_7"},{"key":"2022062314360137076_j_popets-2022-0020_ref_019","doi-asserted-by":"crossref","unstructured":"[19] Ronald Cramer, Ivan Damg\u00e5rd, 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\u2013334. Springer, 2000.10.1007\/3-540-45539-6_22","DOI":"10.1007\/3-540-45539-6_22"},{"key":"2022062314360137076_j_popets-2022-0020_ref_020","doi-asserted-by":"crossref","unstructured":"[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\u2013146, Nerja, Spain, June 7\u201310, 2011. Springer, Heidelberg, Germany.10.1007\/978-3-642-21554-4_8","DOI":"10.1007\/978-3-642-21554-4_8"},{"key":"2022062314360137076_j_popets-2022-0020_ref_021","unstructured":"[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."},{"key":"2022062314360137076_j_popets-2022-0020_ref_022","doi-asserted-by":"crossref","unstructured":"[22] Ivan Damg\u00e5rd, 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\u2013304, 2006.10.1007\/11681878_15","DOI":"10.1007\/11681878_15"},{"key":"2022062314360137076_j_popets-2022-0020_ref_023","doi-asserted-by":"crossref","unstructured":"[23] I. Damg\u00e5rd, 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\u20131120, 2019.10.1109\/SP.2019.00078","DOI":"10.1109\/SP.2019.00078"},{"key":"2022062314360137076_j_popets-2022-0020_ref_024","unstructured":"[24] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017."},{"key":"2022062314360137076_j_popets-2022-0020_ref_025","unstructured":"[25] Irene Giacomelli, Somesh Jha, Ross Kleiman, David Page, and Kyonghwan Yoon. Privacy-preserving collaborative prediction using random forests. CoRR, abs\/1811.08695, 2018."},{"key":"2022062314360137076_j_popets-2022-0020_ref_026","doi-asserted-by":"crossref","unstructured":"[26] Eric Goldman. An introduction to the california consumer privacy act (ccpa). Santa Clara Univ. Legal Studies Research Paper, 2020.","DOI":"10.4337\/9781788119924.00025"},{"key":"2022062314360137076_j_popets-2022-0020_ref_027","doi-asserted-by":"crossref","unstructured":"[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\u2013304, 01 2000.","DOI":"10.1109\/SFCS.2000.892118"},{"key":"2022062314360137076_j_popets-2022-0020_ref_028","doi-asserted-by":"crossref","unstructured":"[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","DOI":"10.5089\/9781451862386.001"},{"key":"2022062314360137076_j_popets-2022-0020_ref_029","doi-asserted-by":"crossref","unstructured":"[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\u2013259. Springer, 2018.10.1007\/978-3-319-95729-6_16","DOI":"10.1007\/978-3-319-95729-6_16"},{"key":"2022062314360137076_j_popets-2022-0020_ref_030","doi-asserted-by":"crossref","unstructured":"[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","DOI":"10.1145\/3372297.3417872"},{"key":"2022062314360137076_j_popets-2022-0020_ref_031","doi-asserted-by":"crossref","unstructured":"[31] Benjamin Kuykendall, Hugo Krawczyk, and Tal Rabin. Cryptography for #metoo. Proceedings on Privacy Enhancing Technologies, 2019(3):409 \u2013 429, 2019.10.2478\/popets-2019-0054","DOI":"10.2478\/popets-2019-0054"},{"key":"2022062314360137076_j_popets-2022-0020_ref_032","unstructured":"[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 \u201919, page 887\u2013903, New York, NY, USA, 2019. Association for Computing Machinery."},{"key":"2022062314360137076_j_popets-2022-0020_ref_033","unstructured":"[33] Jack P. K. Ma, Raymond K. H. Tai, Yongjun Zhao, and Sherman S.M. Chow. Let\u2019s stride blindfolded in a forest: Sublinear multi-client decision trees evaluation. In ISOC Network and Distributed System Security Symposium \u2013 NDSS 2021. The Internet Society, 2021."},{"key":"2022062314360137076_j_popets-2022-0020_ref_034","doi-asserted-by":"crossref","unstructured":"[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\u2013353, 2018.10.1109\/SP.2018.00028","DOI":"10.1109\/SP.2018.00028"},{"key":"2022062314360137076_j_popets-2022-0020_ref_035","doi-asserted-by":"crossref","unstructured":"[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\u201338, 2017.10.1109\/SP.2017.12","DOI":"10.1109\/SP.2017.12"},{"key":"2022062314360137076_j_popets-2022-0020_ref_036","unstructured":"[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\u201357, New York, NY, USA, April 24\u201326, 2006. Springer, Heidelberg, Germany."},{"key":"2022062314360137076_j_popets-2022-0020_ref_037","unstructured":"[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\u201352, New York, NY, USA, 2018. Association for Computing Machinery."},{"key":"2022062314360137076_j_popets-2022-0020_ref_038","unstructured":"[38] Hadad Muliaman, Wimboh Santoso, Bagus Santoso, Dwityapoetra Besar, and Ita Rulina. Rating migration matrices: empirical evidence in indonesia. IFC Bulletin, 01 2009."},{"key":"2022062314360137076_j_popets-2022-0020_ref_039","doi-asserted-by":"crossref","unstructured":"[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 \u2013 PKC 2007, pages 343\u2013360, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.10.1007\/978-3-540-71677-8_23","DOI":"10.1007\/978-3-540-71677-8_23"},{"key":"2022062314360137076_j_popets-2022-0020_ref_040","unstructured":"[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."},{"key":"2022062314360137076_j_popets-2022-0020_ref_041","doi-asserted-by":"crossref","unstructured":"[41] Adi Shamir. How to share a secret. Commun. ACM, 22(11):612\u2013613, November 1979.10.1145\/359168.359176","DOI":"10.1145\/359168.359176"},{"key":"2022062314360137076_j_popets-2022-0020_ref_042","doi-asserted-by":"crossref","unstructured":"[42] Anselme Tueno, Florian Kerschbaum, and Stefan Katzenbeisser. Private evaluation of decision trees using sublinear cost. Proceedings on Privacy Enhancing Technologies, 2019(1):266\u2013286, 2019.10.2478\/popets-2019-0015","DOI":"10.2478\/popets-2019-0015"},{"key":"2022062314360137076_j_popets-2022-0020_ref_043","doi-asserted-by":"crossref","unstructured":"[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 \u2013 49, 2019.","DOI":"10.2478\/popets-2019-0035"},{"key":"2022062314360137076_j_popets-2022-0020_ref_044","doi-asserted-by":"crossref","unstructured":"[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","DOI":"10.1515\/popets-2016-0043"},{"key":"2022062314360137076_j_popets-2022-0020_ref_045","doi-asserted-by":"crossref","unstructured":"[45] \u00c1gnes 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 \u2013 208, 2019.","DOI":"10.2478\/popets-2019-0026"}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2022-0020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T19:16:08Z","timestamp":1726168568000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2022\/popets-2022-0020.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,20]]},"references-count":45,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,11,20]]},"published-print":{"date-parts":[[2022,1,1]]}},"alternative-id":["10.2478\/popets-2022-0020"],"URL":"https:\/\/doi.org\/10.2478\/popets-2022-0020","relation":{},"ISSN":["2299-0984"],"issn-type":[{"type":"electronic","value":"2299-0984"}],"subject":[],"published":{"date-parts":[[2021,11,20]]}}}