More Web Proxy on the site http://driver.im/

research-article

Open access

Scalable Multiparty Garbling

Authors:

Gabrielle Beck,

Zhengzhong Jin,

Gabriel KaptchukAuthors Info & Claims

CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

Pages 2158 - 2172

https://doi.org/10.1145/3576915.3623132

Published: 21 November 2023 Publication History

Abstract

Multiparty garbling is the most popular approach for constant-round secure multiparty computation (MPC). Despite being the focus of significant research effort, instantiating prior approaches to multiparty garbling results in constant-round MPC that can not realistically accommodate large numbers of parties. In this work we present the first global-scale multiparty garbling protocol. The per-party communication complexity of our protocol decreases as the number of parties participating in the protocol increases - for the first time matching the asymptotic communication complexity of non-constant round MPC protocols. Our protocol achieves malicious security in the honest-majority setting and relies on the hardness of the Learning Party with Noise assumption.

References

[1]

Michael Alekhnovich. 2003. More on Average Case vs Approximation Complexity. In 44th FOCS. IEEE Computer Society Press, 298--307. https://doi.org/10.1109/SFCS.2003.1238204

[2]

Benny Applebaum, Jonathan Avron, and Christina Brzuska. 2015. Arithmetic Cryptography: Extended Abstract. In ITCS 2015, Tim Roughgarden (Ed.). ACM, 143--151. https://doi.org/10.1145/2688073.2688114

Digital Library

[3]

Benny Applebaum, Ivan Damgr ard, Yuval Ishai, Michael Nielsen, and Lior Zichron. 2017. Secure Arithmetic Computation with Constant Computational Overhead. In CRYPTO 2017, Part I (LNCS, Vol. 10401), Jonathan Katz and Hovav Shacham (Eds.). Springer, Heidelberg, 223--254. https://doi.org/10.1007/978-3-319-63688-7_8

[4]

Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. 2011. How to Garble Arithmetic Circuits. In 52nd FOCS, Rafail Ostrovsky (Ed.). IEEE Computer Society Press, 120--129. https://doi.org/10.1109/FOCS.2011.40

Digital Library

[5]

David Archer, Victor Arribas Abril, Steve Lu, Pieter Maene, Nele Mertens, Danilo Sijacic, and Nigel Smart. [n.,d.]. 'Bristol Fashion' MPC Circuits. https://homes.esat.kuleuven.be/ nsmart/MPC/

[6]

David Archer, Amy O'Hara, Rawane Issa, and Stephanie Straus. 2021. Sharing Sensitive Department of Education Data Across Organizational Boundaries Using Secure Multiparty Computation.

[7]

Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. 2012. Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE. In EUROCRYPT 2012 (LNCS, Vol. 7237), David Pointcheval and Thomas Johansson (Eds.). Springer, Heidelberg, 483--501. https://doi.org/10.1007/978-3-642-29011-4_29

Digital Library

[8]

Marshall Ball, Tal Malkin, and Mike Rosulek. 2016. Garbling Gadgets for Boolean and Arithmetic Circuits. In ACM CCS 2016, Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (Eds.). ACM Press, 565--577. https://doi.org/10.1145/2976749.2978410

Digital Library

[9]

Assi Barak, Martin Hirt, Lior Koskas, and Yehuda Lindell. 2018. An End-to-End System for Large Scale P2P MPC-as-a-Service and Low-Bandwidth MPC for Weak Participants. In ACM CCS 2019, David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang (Eds.). ACM Press, 695--712. https://doi.org/10.1145/3243734.3243801

Digital Library

[10]

Carsten Baum, Emmanuela Orsini, Peter Scholl, and Eduardo Soria-Vazquez. 2020. Efficient Constant-Round MPC with Identifiable Abort and Public Verifiability. In CRYPTO 2020, Part II (LNCS, Vol. 12171), Daniele Micciancio and Thomas Ristenpart (Eds.). Springer, Heidelberg, 562--592. https://doi.org/10.1007/978-3-030-56880-1_20

Digital Library

[11]

Donald Beaver, Silvio Micali, and Phillip Rogaway. 1990. The Round Complexity of Secure Protocols (Extended Abstract). In 22nd ACM STOC. ACM Press, 503--513. https://doi.org/10.1145/100216.100287

Digital Library

[12]

Gabrielle Beck, Aarushi Goel, Abhishek Jain, and Gabriel Kaptchuk. 2021. Order-C Secure Multiparty Computation for Highly Repetitive Circuits. In EUROCRYPT 2021, Part II (LNCS, Vol. 12697), Anne Canteaut and François-Xavier Standaert (Eds.). Springer, Heidelberg, 663--693. https://doi.org/10.1007/978-3-030-77886-6_23

Digital Library

[13]

Zuzana Beerliová-Trubíniová and Martin Hirt. 2008. Perfectly-Secure MPC with Linear Communication Complexity. In TCC 2008 (LNCS, Vol. 4948), Ran Canetti (Ed.). Springer, Heidelberg, 213--230. https://doi.org/10.1007/978-3-540-78524-8_13

[14]

Assaf Ben-David, Noam Nisan, and Benny Pinkas. 2008. FairplayMP: a system for secure multi-party computation. In ACM CCS 2009, Peng Ning, Paul F. Syverson, and Somesh Jha (Eds.). ACM Press, 257--266. https://doi.org/10.1145/1455770.1455804

Digital Library

[15]

Aner Ben-Efraim. 2018. On Multiparty Garbling of Arithmetic Circuits. In ASIACRYPT 2018, Part III (LNCS, Vol. 11274), Thomas Peyrin and Steven Galbraith (Eds.). Springer, Heidelberg, 3--33. https://doi.org/10.1007/978-3-030-03332-3_1

Digital Library

[16]

Aner Ben-Efraim, Kelong Cong, Eran Omri, Emmanuela Orsini, Nigel P. Smart, and Eduardo Soria-Vazquez. 2021. Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits. In EUROCRYPT 2021, Part III (LNCS, Vol. 12698), Anne Canteaut and Franccois-Xavier Standaert (Eds.). Springer, Heidelberg, 33--63. https://doi.org/10.1007/978-3-030-77883-5_2

Digital Library

[17]

Aner Ben-Efraim, Yehuda Lindell, and Eran Omri. 2016. Optimizing Semi-Honest Secure Multiparty Computation for the Internet. In ACM CCS 2016, Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (Eds.). ACM Press, 578--590. https://doi.org/10.1145/2976749.2978347

Digital Library

[18]

Aner Ben-Efraim, Yehuda Lindell, and Eran Omri. 2017. Efficient Scalable Constant-Round MPC via Garbled Circuits. In ASIACRYPT 2017, Part II (LNCS, Vol. 10625), Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer, Heidelberg, 471--498. https://doi.org/10.1007/978-3-319-70697-9_17

[19]

Aner Ben-Efraim and Eran Omri. 2019. Concrete Efficiency Improvements for Multiparty Garbling with an Honest Majority. In LATINCRYPT 2017 (LNCS, Vol. 11368), Tanja Lange and Orr Dunkelman (Eds.). Springer, Heidelberg, 289--308. https://doi.org/10.1007/978-3-030-25283-0_16

[20]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In 20th ACM STOC. ACM Press, 1--10. https://doi.org/10.1145/62212.62213

Digital Library

[21]

Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias. 2011. Semi-homomorphic Encryption and Multiparty Computation. In EUROCRYPT 2011 (LNCS, Vol. 6632), Kenneth G. Paterson (Ed.). Springer, Heidelberg, 169--188. https://doi.org/10.1007/978-3-642-20465-4_11

[22]

Dan Boneh, Kevin Lewi, Hart William Montgomery, and Ananth Raghunathan. 2013. Key Homomorphic PRFs and Their Applications. In CRYPTO 2013, Part I (LNCS, Vol. 8042), Ran Canetti and Juan A. Garay (Eds.). Springer, Heidelberg, 410--428. https://doi.org/10.1007/978-3-642-40041-4_23

[23]

R.C. Bose and D.K. Ray-Chaudhuri. 1960. On a class of error correcting binary group codes. Information and Control, Vol. 3, 1 (1960), 68--79. https://doi.org/10.1016/S0019-9958(60)90287-4

[24]

Sean Bowe, Ariel Gabizon, and Matthew D. Green. 2019. A Multi-party Protocol for Constructing the Public Parameters of the Pinocchio zk-SNARK. In FC 2018 Workshops (LNCS, Vol. 10958), Aviv Zohar, Ittay Eyal, Vanessa Teague, Jeremy Clark, Andrea Bracciali, Federico Pintore, and Massimiliano Sala (Eds.). Springer, Heidelberg, 64--77. https://doi.org/10.1007/978-3-662-58820-8_5

Digital Library

[25]

Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. 2018. Compressing Vector OLE. In ACM CCS 2019, David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang (Eds.). ACM Press, 896--912. https://doi.org/10.1145/3243734.3243868

Digital Library

[26]

Zvika Brakerski, Shai Halevi, and Antigoni Polychroniadou. 2017. Four Round Secure Computation Without Setup. In TCC 2017, Part I (LNCS, Vol. 10677), Yael Kalai and Leonid Reyzin (Eds.). Springer, Heidelberg, 645--677. https://doi.org/10.1007/978-3-319-70500-2_22

Digital Library

[27]

Ignacio Cascudo, Ronald Cramer, Chaoping Xing, and Chen Yuan. 2018. Amortized Complexity of Information-Theoretically Secure MPC Revisited. In CRYPTO 2018, Part III (LNCS, Vol. 10993), Hovav Shacham and Alexandra Boldyreva (Eds.). Springer, Heidelberg, 395--426. https://doi.org/10.1007/978-3-319-96878-0_14

Digital Library

[28]

David Chaum, Claude Crépeau, and Ivan Damgård. 1988. Multiparty Unconditionally Secure Protocols (Abstract) (Informal Contribution). In CRYPTO'87 (LNCS, Vol. 293), Carl Pomerance (Ed.). Springer, Heidelberg, 462. https://doi.org/10.1007/3-540-48184-2_43

[29]

Megan Chen, Ran Cohen, Jack Doerner, Yashvanth Kondi, Eysa Lee, Schuyler Rosefield, and abhi shelat. 2020a. Multiparty Generation of an RSA Modulus. In CRYPTO 2020, Part III (LNCS, Vol. 12172), Daniele Micciancio and Thomas Ristenpart (Eds.). Springer, Heidelberg, 64--93. https://doi.org/10.1007/978-3-030-56877-1_3

Digital Library

[30]

Megan Chen, Carmit Hazay, Yuval Ishai, Yuriy Kashnikov, Daniele Micciancio, Tarik Riviere, abhi shelat, Muthu Venkitasubramaniam, and Ruihan Wang. 2020b. Diogenes: Lightweight Scalable RSA Modulus Generation with a Dishonest Majority. Cryptology ePrint Archive, Report 2020/374. https://eprint.iacr.org/2020/374.

[31]

Koji Chida, Daniel Genkin, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Yehuda Lindell, and Ariel Nof. 2018. Fast Large-Scale Honest-Majority MPC for Malicious Adversaries. In CRYPTO 2018, Part III (LNCS, Vol. 10993), Hovav Shacham and Alexandra Boldyreva (Eds.). Springer, Heidelberg, 34--64. https://doi.org/10.1007/978-3-319-96878-0_2

Digital Library

[32]

Ivan Damgård and Yuval Ishai. 2005. Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator. In CRYPTO 2005 (LNCS, Vol. 3621), Victor Shoup (Ed.). Springer, Heidelberg, 378--394. https://doi.org/10.1007/11535218_23

Digital Library

[33]

Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. 2010. Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In EUROCRYPT 2010 (LNCS, Vol. 6110), Henri Gilbert (Ed.). Springer, Heidelberg, 445--465. https://doi.org/10.1007/978-3-642-13190-5_23

Digital Library

[34]

Ivan Damgård, Yuval Ishai, Mikkel Krøigaard, Jesper Buus Nielsen, and Adam Smith. 2008. Scalable Multiparty Computation with Nearly Optimal Work and Resilience. In CRYPTO 2008 (LNCS, Vol. 5157), David Wagner (Ed.). Springer, Heidelberg, 241--261. https://doi.org/10.1007/978-3-540-85174-5_14

Digital Library

[35]

Ivan Damgr ard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart. 2013. Practical Covertly Secure MPC for Dishonest Majority - Or: Breaking the SPDZ Limits. In ESORICS 2013 (LNCS, Vol. 8134), Jason Crampton, Sushil Jajodia, and Keith Mayes (Eds.). Springer, Heidelberg, 1--18. https://doi.org/10.1007/978-3-642-40203-6_1

[36]

Ivan Damgård and Jesper Buus Nielsen. 2007. Scalable and Unconditionally Secure Multiparty Computation. In CRYPTO 2007 (LNCS, Vol. 4622), Alfred Menezes (Ed.). Springer, Heidelberg, 572--590. https://doi.org/10.1007/978-3-540-74143-5_32

[37]

Ivan Damgr ard, Claudio Orlandi, and Mark Simkin. 2018. Yet Another Compiler for Active Security or: Efficient MPC Over Arbitrary Rings. In CRYPTO 2018, Part II (LNCS, Vol. 10992), Hovav Shacham and Alexandra Boldyreva (Eds.). Springer, Heidelberg, 799--829. https://doi.org/10.1007/978-3-319-96881-0_27

Digital Library

[38]

Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. 2012. Multiparty Computation from Somewhat Homomorphic Encryption. In CRYPTO 2012 (LNCS, Vol. 7417), Reihaneh Safavi-Naini and Ran Canetti (Eds.). Springer, Heidelberg, 643--662. https://doi.org/10.1007/978-3-642-32009-5_38

Digital Library

[39]

Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In NDSS 2015. The Internet Society.

[40]

Nico Döttling. 2015. Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification. In PKC 2015 (LNCS, Vol. 9020), Jonathan Katz (Ed.). Springer, Heidelberg, 604--626. https://doi.org/10.1007/978-3-662-46447-2_27

[41]

Nico Döttling, Satrajit Ghosh, Jesper Buus Nielsen, Tobias Nilges, and Roberto Trifiletti. 2017. TinyOLE: Efficient Actively Secure Two-Party Computation from Oblivious Linear Function Evaluation. In ACM CCS 2017, Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM Press, 2263--2276. https://doi.org/10.1145/3133956.3134024

Digital Library

[42]

Daniel Escudero, Vipul Goyal, Antigoni Polychroniadou, and Yifan Song. 2022. TurboPack: Honest Majority MPC with Constant Online Communication. In ACM CCS 2022, Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi (Eds.). ACM Press, 951--964. https://doi.org/10.1145/3548606.3560633

Digital Library

[43]

Andre Esser, Robert Kübler, and Alexander May. 2017. LPN Decoded. In CRYPTO 2017, Part II (LNCS, Vol. 10402), Jonathan Katz and Hovav Shacham (Eds.). Springer, Heidelberg, 486--514. https://doi.org/10.1007/978-3-319-63715-0_17

[44]

Matthew K. Franklin and Moti Yung. 1992. Communication Complexity of Secure Computation (Extended Abstract). In 24th ACM STOC. ACM Press, 699--710. https://doi.org/10.1145/129712.129780

Digital Library

[45]

Jun Furukawa and Yehuda Lindell. 2019. Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest. In ACM CCS 2019, Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM Press, 1557--1571. https://doi.org/10.1145/3319535.3339811

Digital Library

[46]

Sanjam Garg, Vipul Goyal, Abhishek Jain, and Amit Sahai. 2012. Concurrently Secure Computation in Constant Rounds. In EUROCRYPT 2012 (LNCS, Vol. 7237), David Pointcheval and Thomas Johansson (Eds.). Springer, Heidelberg, 99--116. https://doi.org/10.1007/978-3-642-29011-4_8

Digital Library

[47]

Daniel Genkin, Yuval Ishai, and Antigoni Polychroniadou. 2015. Efficient Multi-party Computation: From Passive to Active Security via Secure SIMD Circuits. In CRYPTO 2015, Part II (LNCS, Vol. 9216), Rosario Gennaro and Matthew J. B. Robshaw (Eds.). Springer, Heidelberg, 721--741. https://doi.org/10.1007/978-3-662-48000-7_35

Digital Library

[48]

Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and Eran Tromer. 2014. Circuits resilient to additive attacks with applications to secure computation. In 46th ACM STOC, David B. Shmoys (Ed.). ACM Press, 495--504. https://doi.org/10.1145/2591796.2591861

Digital Library

[49]

Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In 41st ACM STOC, Michael Mitzenmacher (Ed.). ACM Press, 169--178. https://doi.org/10.1145/1536414.1536440

Digital Library

[50]

Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. In 19th ACM STOC, Alfred Aho (Ed.). ACM Press, 218--229. https://doi.org/10.1145/28395.28420

Digital Library

[51]

S. Dov Gordon, Feng-Hao Liu, and Elaine Shi. 2015. Constant-Round MPC with Fairness and Guarantee of Output Delivery. In CRYPTO 2015, Part II (LNCS, Vol. 9216), Rosario Gennaro and Matthew J. B. Robshaw (Eds.). Springer, Heidelberg, 63--82. https://doi.org/10.1007/978-3-662-48000-7_4

Digital Library

[52]

S. Dov Gordon, Daniel Starin, and Arkady Yerukhimovich. 2021. The More the Merrier: Reducing the Cost of Large Scale MPC. In EUROCRYPT 2021, Part II (LNCS, Vol. 12697), Anne Canteaut and Franccois-Xavier Standaert (Eds.). Springer, Heidelberg, 694--723. https://doi.org/10.1007/978-3-030-77886-6_24

Digital Library

[53]

Vipul Goyal, Antigoni Polychroniadou, and Yifan Song. 2021. Unconditional Communication-Efficient MPC via Hall's Marriage Theorem. In CRYPTO 2021, Part II (LNCS, Vol. 12826), Tal Malkin and Chris Peikert (Eds.). Springer, Heidelberg, Virtual Event, 275--304. https://doi.org/10.1007/978-3-030-84245-1_10

Digital Library

[54]

Vipul Goyal, Antigoni Polychroniadou, and Yifan Song. 2022. Sharing Transformation and Dishonest Majority MPC with Packed Secret Sharing. In CRYPTO 2022, Part IV (LNCS, Vol. 13510), Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer, Heidelberg, 3--32. https://doi.org/10.1007/978-3-031-15985-5_1

Digital Library

[55]

Vipul Goyal and Yifan Song. 2020. Malicious Security Comes Free in Honest-Majority MPC. Cryptology ePrint Archive, Report 2020/134. https://eprint.iacr.org/2020/134.

[56]

Vipul Goyal, Yifan Song, and Chenzhi Zhu. 2020. Guaranteed Output Delivery Comes Free in Honest Majority MPC. In CRYPTO 2020, Part II (LNCS, Vol. 12171), Daniele Micciancio and Thomas Ristenpart (Eds.). Springer, Heidelberg, 618--646. https://doi.org/10.1007/978-3-030-56880-1_22

Digital Library

[57]

Marcella Hastings, Brett Hemenway, Daniel Noble, and Steve Zdancewic. 2019. SoK: General Purpose Compilers for Secure Multi-Party Computation. In 2019 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 1220--1237. https://doi.org/10.1109/SP.2019.00028

[58]

Carmit Hazay, Emmanuela Orsini, Peter Scholl, and Eduardo Soria-Vazquez. 2018a. Concretely Efficient Large-Scale MPC with Active Security (or, TinyKeys for TinyOT). In ASIACRYPT 2018, Part III (LNCS, Vol. 11274), Thomas Peyrin and Steven Galbraith (Eds.). Springer, Heidelberg, 86--117. https://doi.org/10.1007/978--3-030-03332-3_4

Digital Library

[59]

Carmit Hazay, Emmanuela Orsini, Peter Scholl, and Eduardo Soria-Vazquez. 2018b. TinyKeys: A New Approach to Efficient Multi-Party Computation. In CRYPTO 2018, Part III (LNCS, Vol. 10993), Hovav Shacham and Alexandra Boldyreva (Eds.). Springer, Heidelberg, 3--33. https://doi.org/10.1007/978-3-319-96878-0_1

Digital Library

[60]

Carmit Hazay, Peter Scholl, and Eduardo Soria-Vazquez. 2017. Low Cost Constant Round MPC Combining BMR and Oblivious Transfer. In ASIACRYPT 2017, Part I (LNCS, Vol. 10624), Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer, Heidelberg, 598--628. https://doi.org/10.1007/978-3-319-70694--8_21

[61]

Carmit Hazay, Peter Scholl, and Eduardo Soria-Vazquez. 2020. Low Cost Constant Round MPC Combining BMR and Oblivious Transfer. Journal of Cryptology, Vol. 33, 4 (Oct. 2020), 1732--1786. https://doi.org/10.1007/s00145-020-09355-y

Digital Library

[62]

Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. 2009. Secure Arithmetic Computation with No Honest Majority. In TCC 2009 (LNCS, Vol. 5444), Omer Reingold (Ed.). Springer, Heidelberg, 294--314. https://doi.org/10.1007/978-3-642-00457-5_18

Digital Library

[63]

Aayush Jain, Huijia Lin, and Amit Sahai. 2021. Indistinguishability obfuscation from well-founded assumptions. In 53rd ACM STOC, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM Press, 60--73. https://doi.org/10.1145/3406325.3451093

Digital Library

[64]

Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2016. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer. In ACM CCS 2016, Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (Eds.). ACM Press, 830--842. https://doi.org/10.1145/2976749.2978357

Digital Library

[65]

Marcel Keller, Valerio Pastro, and Dragos Rotaru. 2018. Overdrive: Making SPDZ Great Again. In EUROCRYPT 2018, Part III (LNCS, Vol. 10822), Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer, Heidelberg, 158--189. https://doi.org/10.1007/978-3-319-78372-7_6

[66]

Andrei Lapets, Frederick Jansen, Kinan Dak Albab, Rawane Issa, Lucy Qin, Mayank Varia, and Azer Bestavros. 2018. Accessible Privacy-Preserving Web-Based Data Analysis for Assessing and Addressing Economic Inequalities. In Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies (Menlo Park and San Jose, CA, USA) (COMPASS '18). Association for Computing Machinery, New York, NY, USA, Article 48, bibinfonumpages5 pages. https://doi.org/10.1145/3209811.3212701

Digital Library

[67]

Yehuda Lindell and Ariel Nof. 2017. A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority. In ACM CCS 2017, Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM Press, 259--276. https://doi.org/10.1145/3133956.3133999

Digital Library

[68]

Yehuda Lindell, Benny Pinkas, Nigel P. Smart, and Avishay Yanai. 2015. Efficient Constant Round Multi-party Computation Combining BMR and SPDZ. In CRYPTO 2015, Part II (LNCS, Vol. 9216), Rosario Gennaro and Matthew J. B. Robshaw (Eds.). Springer, Heidelberg, 319--338. https://doi.org/10.1007/978-3-662-48000-7_16

Digital Library

[69]

Yehuda Lindell, Nigel P. Smart, and Eduardo Soria-Vazquez. 2016. More Efficient Constant-Round Multi-party Computation from BMR and SHE. In TCC 2016-B, Part I (LNCS, Vol. 9985), Martin Hirt and Adam D. Smith (Eds.). Springer, Heidelberg, 554--581. https://doi.org/10.1007/978-3-662-53641-4_21

Digital Library

[70]

Hanlin Liu, Xiao Wang, Kang Yang, and Yu Yu. 2022. The Hardness of LPN over Any Integer Ring and Field for PCG Applications. Cryptology ePrint Archive, Report 2022/712. https://eprint.iacr.org/2022/712.

[71]

Eleftheria Makri and Tim Wood. 2019. Full-Threshold Actively-Secure Multiparty Arithmetic Circuit Garbling. Cryptology ePrint Archive, Report 2019/1098. https://eprint.iacr.org/2019/1099.

[72]

Dahlia Malkhi, Noam Nisan, Benny Pinkas, and Yaron Sella. 2004. Fairplay - Secure Two-Party Computation System. In USENIX Security 2004, Matt Blaze (Ed.). USENIX Association, 287--302.

Digital Library

[73]

Payman Mohassel and Peter Rindal. 2018. ABY3: A Mixed Protocol Framework for Machine Learning. Cryptology ePrint Archive, Report 2018/403. https://eprint.iacr.org/2018/403.

[74]

Pratyay Mukherjee and Daniel Wichs. 2016. Two Round Multiparty Computation via Multi-key FHE. In EUROCRYPT 2016, Part II (LNCS, Vol. 9666), Marc Fischlin and Jean-Sé bastien Coron (Eds.). Springer, Heidelberg, 735--763. https://doi.org/10.1007/978-3-662-49896-5_26

[75]

Steven Myers, Mona Sergi, and abhi shelat. 2011. Threshold Fully Homomorphic Encryption and Secure Computation. Cryptology ePrint Archive, Report 2011/454. https://eprint.iacr.org/2011/454.

[76]

Jesper Buus Nielsen, Thomas Schneider, and Roberto Trifiletti. 2017. Constant Round Maliciously Secure 2PC with Function-independent Preprocessing using LEGO. In NDSS 2017. The Internet Society.

[77]

Peter Sebastian Nordholt and Meilof Veeningen. 2018. Minimising Communication in Honest-Majority MPC by Batchwise Multiplication Verification. In ACNS 18 (LNCS, Vol. 10892), Bart Preneel and Frederik Vercauteren (Eds.). Springer, Heidelberg, 321--339. https://doi.org/10.1007/978-3-319-93387-0_17

Digital Library

[78]

Emmanuela Orsini, Nigel P. Smart, and Frederik Vercauteren. 2020. Overdrive2k: Efficient Secure MPC over ℤ_2k from Somewhat Homomorphic Encryption. In CT-RSA 2020 (LNCS, Vol. 12006), Stanislaw Jarecki (Ed.). Springer, Heidelberg, 254--283. https://doi.org/10.1007/978-3-030-40186-3_12

Digital Library

[79]

James S. Plank. 2007. Fast Galois Field Arithmetic Library in C/C. http://web.eecs.utk.edu/ jplank/plank/papers/CS-07-593/

[80]

Lucy Qin, Andrei Lapets, Frederick Jansen, Peter Flockhart, Kinan Dak Albab, Ira Globus-Harris, Shannon Roberts, and Mayank Varia. 2019. From Usability to Secure Computing and Back Again. Cryptology ePrint Archive, Report 2019/734. https://eprint.iacr.org/2019/734.

[81]

Adi Shamir. 1979. How to Share a Secret. Communications of the Association for Computing Machinery, Vol. 22, 11 (Nov. 1979), 612--613.

Digital Library

[82]

Erik Taubeneck, Martin Thomson, Ben Savage, Benjamin Case, Daniel Masny, Richa Jain, Taiki Yamaguchi, Alex Koshelev, Thurston Sandbery, Victor Miller, and Shubho Sengupta. 2023. Interoperable Private Attribution (IPA).

[83]

Ryan Wails, Aaron Johnson, Daniel Starin, Arkady Yerukhimovich, and S. Dov Gordon. 2019. Stormy: Statistics in Tor by Measuring Securely. In ACM CCS 2019, Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM Press, 615--632. https://doi.org/10.1145/3319535.3345650

Digital Library

[84]

Xiao Wang, Samuel Ranellucci, and Jonathan Katz. 2017a. Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation. In ACM CCS 2017, Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM Press, 21--37. https://doi.org/10.1145/3133956.3134053

Digital Library

[85]

Xiao Wang, Samuel Ranellucci, and Jonathan Katz. 2017b. Global-Scale Secure Multiparty Computation. In ACM CCS 2017, Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM Press, 39--56. https://doi.org/10.1145/3133956.3133979

Digital Library

[86]

Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets (Extended Abstract). In 27th FOCS. IEEE Computer Society Press, 162--167. https://doi.org/10.1109/SFCS.1986.25

Digital Library

Cited By

Jin CYin Cvan Dijk MDuan SMassacci FReiter MZhang HLuo BLiao XXu JKirda ELie D(2024)PG: Byzantine Fault-Tolerant and Privacy-Preserving Sensor Fusion with Guaranteed Output DeliveryProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670343(3272-3286)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670343
Garg RYang KKatz JWang X(2024)Scalable Mixed-Mode MPC2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00106(523-541)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00106
Goyal VLi JMisra AOstrovsky RSong YWeng C(2024)Dishonest Majority Constant-Round MPC with Linear Communication from DDHAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_6(167-199)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0938-3_6

Index Terms

Scalable Multiparty Garbling
1. Security and privacy
  1. Security services
    1. Privacy-preserving protocols

Recommendations

Low Cost Constant Round MPC Combining BMR and Oblivious Transfer
Abstract
In this work, we present two new actively secure, constant-round multi-party computation (MPC) protocols with security against all-but-one corruptions. Our protocols both start with an actively secure MPC protocol, which may have linear round ...
$_{}$
Fast Garbling of Circuits Under Standard Assumptions

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything, but the result. Over recent years, secure computation has become practical and considerable effort has been made ...
Constant-Round Multiparty Private Function Evaluation with (Quasi-)Linear Complexities
Applied Cryptography and Network Security
Abstract
Private function evaluation (PFE) is a special case of secure multiparty computation. In multiparty PFE, the party $P_{1}$ holds its private n-variable function $f$ and private input $x_{1}$ , while other parties $P_{i} (n \geq i \geq 2)$ hold their private input $x_{i}$ . All n ... $_{}_{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security

November 2023

3722 pages

ISBN:9798400700507

DOI:10.1145/3576915

General Chairs:
Weizhi Meng
Technical University of Denmark
,
Christian D. Jensen
Technical University of Denmark
,
Program Chairs:
Cas Cremers
CISPA Helmholtz Center for Information Security
,
Engin Kirda
Khoury College of Computer Sciences

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 November 2023

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CCS '23

Sponsor:

SIGSAC

CCS '23: ACM SIGSAC Conference on Computer and Communications Security

November 26 - 30, 2023

Copenhagen, Denmark

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

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

3
Total Citations
View Citations
521
Total Downloads

Downloads (Last 12 months)443
Downloads (Last 6 weeks)37

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jin CYin Cvan Dijk MDuan SMassacci FReiter MZhang HLuo BLiao XXu JKirda ELie D(2024)PG: Byzantine Fault-Tolerant and Privacy-Preserving Sensor Fusion with Guaranteed Output DeliveryProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670343(3272-3286)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670343
Garg RYang KKatz JWang X(2024)Scalable Mixed-Mode MPC2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00106(523-541)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00106
Goyal VLi JMisra AOstrovsky RSong YWeng C(2024)Dishonest Majority Constant-Round MPC with Linear Communication from DDHAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_6(167-199)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0938-3_6

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten