Document Open Access Logo

Asymmetric Multi-Party Computation

Authors Vipul Goyal, Chen-Da Liu-Zhang , Rafail Ostrovsky

PDF
Thumbnail PDF

File

LIPIcs.ITC.2023.6.pdf
  • Filesize: 0.81 MB
  • 25 pages

Document Identifiers

Author Details

Vipul Goyal
  • NTT Research, Sunnyvale, CA, USA
  • Carnegie Mellon University, Pittsburgh, PA, USA
Chen-Da Liu-Zhang
  • NTT Research, Sunnyvale, CA, USA
Rafail Ostrovsky
  • University of California at Los Angeles, CA, USA

Funding

  • Ostrovsky, Rafail: The author was supported in part by DARPA under Cooperative Agreement HR0011-20-2-0025, the Algorand Centers of Excellence programme managed by Algorand Foundation, NSF grants CNS-2246355, CCF-2220450 and CNS-2001096, US-Israel BSF grant 2015782, Amazon Faculty Award, Cisco Research Award and Sunday Group. Any views, opinions, findings, conclusions or recommendations contained herein are those of the author(s) and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA, the Department of Defense, the Algorand Foundation, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes not withstanding any copyright annotation therein.

Cite As Get BibTex

Vipul Goyal, Chen-Da Liu-Zhang, and Rafail Ostrovsky. Asymmetric Multi-Party Computation. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITC.2023.6

Abstract

Current protocols for Multi-Party Computation (MPC) consider the setting where all parties have access to similar resources. For example, all parties have access to channels bounded by the same worst-case delay upper bound Δ, and all channels have the same cost of communication. As a consequence, the overall protocol performance (resp. the communication cost) may be heavily affected by the slowest (resp. the most expensive) channel, even when most channels are fast (resp. cheap). Given the state of affairs, we initiate a systematic study of asymmetric MPC. In asymmetric MPC, the parties are divided into two categories: fast and slow parties, depending on whether they have access to high-end or low-end resources. 
We investigate two different models. In the first, we consider asymmetric communication delays: Fast parties are connected via channels with small delay δ among themselves, while channels connected to (at least) one slow party have a large delay Δ ≫ δ. In the second model, we consider asymmetric communication costs: Fast parties benefit from channels with cheap communication, while channels connected to a slow party have an expensive communication. We provide a wide range of positive and negative results exploring the trade-offs between the achievable number of tolerated corruptions t and slow parties s, versus the round complexity and communication cost in each of the models. Among others, we achieve the following results. In the model with asymmetric communication delays, focusing on the information-theoretic (i-t) setting:
 
- An i-t asymmetric MPC protocol with security with abort as long as t+s < n and t < n/2, in a constant number of slow rounds. 
- We show that achieving an i-t asymmetric MPC protocol for t+s = n and with number of slow rounds independent of the circuit size implies an i-t synchronous MPC protocol with round complexity independent of the circuit size, which is a major problem in the field of round-complexity of MPC. 
- We identify a new primitive, asymmetric broadcast, that allows to consistently distribute a value among the fast parties, and at a later time the same value to slow parties. We completely characterize the feasibility of asymmetric broadcast by showing that it is possible if and only if 2t + s < n. 
- An i-t asymmetric MPC protocol with guaranteed output delivery as long as t+s < n and t < n/2, in a number of slow rounds independent of the circuit size.
In the model with asymmetric communication cost, we achieve an asymmetric MPC protocol for security with abort for t+s < n and t < n/2, based on one-way functions (OWF). The protocol communicates a number of bits over expensive channels that is independent of the circuit size. We conjecture that assuming OWF is needed and further provide a partial result in this direction.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
Keywords
  • multiparty computation
  • asymmetric
  • delays
  • communication

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty computation with low communication, computation and interaction via threshold FHE. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 483-501. Springer, Heidelberg, April 2012. URL: https://doi.org/10.1007/978-3-642-29011-4_29.
  2. Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer extensions with security for malicious adversaries. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 673-701. Springer, Heidelberg, April 2015. URL: https://doi.org/10.1007/978-3-662-46800-5_26.
  3. Saikrishna Badrinarayanan, Aayush Jain, Nathan Manohar, and Amit Sahai. Secure MPC: Laziness leads to GOD. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 120-150. Springer, Heidelberg, December 2020. URL: https://doi.org/10.1007/978-3-030-64840-4_5.
  4. Donald Beaver. Correlated pseudorandomness and the complexity of private computations. In 28th ACM STOC, pages 479-488. ACM Press, May 1996. URL: https://doi.org/10.1145/237814.237996.
  5. Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols (extended abstract). In 22nd ACM STOC, pages 503-513. ACM Press, May 1990. URL: https://doi.org/10.1145/100216.100287.
  6. Zuzana Beerliová-Trubíniová and Martin Hirt. Perfectly-secure MPC with linear communication complexity. In Ran Canetti, editor, TCC 2008, volume 4948 of LNCS, pages 213-230. Springer, Heidelberg, March 2008. URL: https://doi.org/10.1007/978-3-540-78524-8_13.
  7. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In 20th ACM STOC, pages 1-10. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62213.
  8. Fabrice Benhamouda and Huijia Lin. k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 500-532. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_17.
  9. Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part I, volume 12550 of LNCS, pages 353-380. Springer, Heidelberg, November 2020. URL: https://doi.org/10.1007/978-3-030-64375-1_13.
  10. Gabriel Bracha. An o (log n) expected rounds randomized byzantine generals protocol. Journal of the ACM (JACM), 34(4):910-920, 1987. Google Scholar
  11. David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In 20th ACM STOC, pages 11-19. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62214.
  12. Arka Rai Choudhuri, Aarushi Goel, Matthew Green, Abhishek Jain, and Gabriel Kaptchuk. Fluid MPC: Secure multiparty computation with dynamic participants. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II, volume 12826 of LNCS, pages 94-123, Virtual Event, August 2021. Springer, Heidelberg. URL: https://doi.org/10.1007/978-3-030-84245-1_4.
  13. Ran Cohen, Sandro Coretti, Juan A. Garay, and Vassilis Zikas. Probabilistic termination and composability of cryptographic protocols. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 240-269. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53015-3_9.
  14. Ronald Cramer, Ivan Damgård, Stefan Dziembowski, Martin Hirt, and Tal Rabin. Efficient multiparty computations secure against an adaptive adversary. In Jacques Stern, editor, EUROCRYPT'99, volume 1592 of LNCS, pages 311-326. Springer, Heidelberg, May 1999. URL: https://doi.org/10.1007/3-540-48910-X_22.
  15. Claude Crépeau, Jeroen van de Graaf, and Alain Tapp. Committed oblivious transfer and private multi-party computation. In Don Coppersmith, editor, CRYPTO'95, volume 963 of LNCS, pages 110-123. Springer, Heidelberg, August 1995. URL: https://doi.org/10.1007/3-540-44750-4_9.
  16. Ivan Damgård and Jesper Buus Nielsen. Scalable and unconditionally secure multiparty computation. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 572-590. Springer, Heidelberg, August 2007. URL: https://doi.org/10.1007/978-3-540-74143-5_32.
  17. Ivan Damgård, Daniel Escudero, and Antigoni Polychroniadou. Phoenix: Secure computation in an unstable network with dropouts and comebacks. Cryptology ePrint Archive, Report 2021/1376, 2021. URL: https://ia.cr/2021/1376.
  18. Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983. Google Scholar
  19. Paul Feldman and Silvio Micali. Optimal algorithms for byzantine agreement. In 20th ACM STOC, pages 148-161. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62225.
  20. Sanjam Garg and Akshayaram Srinivasan. Two-round multiparty secure computation from minimal assumptions. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 468-499. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_16.
  21. Daniel Genkin, Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and Eran Tromer. Circuits resilient to additive attacks with applications to secure computation. In David B. Shmoys, editor, 46th ACM STOC, pages 495-504. ACM Press, May / June 2014. URL: https://doi.org/10.1145/2591796.2591861.
  22. Rosario Gennaro, Michael O. Rabin, and Tal Rabin. Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In Brian A. Coan and Yehuda Afek, editors, 17th ACM PODC, pages 101-111. ACM, June / July 1998. URL: https://doi.org/10.1145/277697.277716.
  23. Craig Gentry, Shai Halevi, Hugo Krawczyk, Bernardo Magri, Jesper Buus Nielsen, Tal Rabin, and Sophia Yakoubov. YOSO: You only speak once - secure MPC with stateless ephemeral roles. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II, volume 12826 of LNCS, pages 64-93, Virtual Event, August 2021. Springer, Heidelberg. URL: https://doi.org/10.1007/978-3-030-84245-1_3.
  24. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218-229. ACM Press, May 1987. URL: https://doi.org/10.1145/28395.28420.
  25. Oded Goldreich and Avi Wigderson. Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Structures & Algorithms, 11(4):315-343, 1997. Google Scholar
  26. S. Dov Gordon, Feng-Hao Liu, and Elaine Shi. Constant-round MPC with fairness and guarantee of output delivery. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 63-82. Springer, Heidelberg, August 2015. URL: https://doi.org/10.1007/978-3-662-48000-7_4.
  27. Vipul Goyal, Yanyi Liu, and Yifan Song. Communication-efficient unconditional MPC with guaranteed output delivery. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 85-114. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_4.
  28. Vipul Goyal, Yifan Song, and Chenzhi Zhu. Guaranteed output delivery comes free in honest majority MPC. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 618-646. Springer, Heidelberg, August 2020. URL: https://doi.org/10.1007/978-3-030-56880-1_22.
  29. Yue Guo, Rafael Pass, and Elaine Shi. Synchronous, with a chance of partition tolerance. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 499-529. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26948-7_18.
  30. Danny Harnik, Yuval Ishai, and Eyal Kushilevitz. How many oblivious transfers are needed for secure multiparty computation? In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 284-302. Springer, Heidelberg, August 2007. URL: https://doi.org/10.1007/978-3-540-74143-5_16.
  31. Danny Harnik, Joe Kilian, Moni Naor, Omer Reingold, and Alon Rosen. On robust combiners for oblivious transfer and other primitives. In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 96-113. Springer, Heidelberg, May 2005. URL: https://doi.org/10.1007/11426639_6.
  32. Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 145-161. Springer, Heidelberg, August 2003. URL: https://doi.org/10.1007/978-3-540-45146-4_9.
  33. Jonathan Katz and Chiu-Yuen Koo. On expected constant-round protocols for byzantine agreement. In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 445-462. Springer, Heidelberg, August 2006. URL: https://doi.org/10.1007/11818175_27.
  34. Jonathan Katz and Rafail Ostrovsky. Round-optimal secure two-party computation. In Matthew Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 335-354. Springer, Heidelberg, August 2004. URL: https://doi.org/10.1007/978-3-540-28628-8_21.
  35. Jonathan Katz, Rafail Ostrovsky, and Adam Smith. Round efficiency of multi-party computation with a dishonest majority. In Eli Biham, editor, EUROCRYPT 2003, volume 2656 of LNCS, pages 578-595. Springer, Heidelberg, May 2003. URL: https://doi.org/10.1007/3-540-39200-9_36.
  36. Joe Kilian. Founding cryptography on oblivious transfer. In 20th ACM STOC, pages 20-31. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62215.
  37. Yehuda Lindell. Parallel coin-tossing and constant-round secure two-party computation. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 171-189. Springer, Heidelberg, August 2001. URL: https://doi.org/10.1007/3-540-44647-8_10.
  38. Yehuda Lindell and Hila Zarosim. On the feasibility of extending oblivious transfer. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 519-538. Springer, Heidelberg, March 2013. URL: https://doi.org/10.1007/978-3-642-36594-2_29.
  39. Chen-Da Liu-Zhang, Julian Loss, Ueli Maurer, Tal Moran, and Daniel Tschudi. MPC with synchronous security and asynchronous responsiveness. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 92-119. Springer, Heidelberg, December 2020. URL: https://doi.org/10.1007/978-3-030-64840-4_4.
  40. Pratyay Mukherjee and Daniel Wichs. Two round multiparty computation via multi-key FHE. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 735-763. Springer, Heidelberg, May 2016. URL: https://doi.org/10.1007/978-3-662-49896-5_26.
  41. Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. A new approach to practical active-secure two-party computation. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 681-700. Springer, Heidelberg, August 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_40.
  42. Rafael Pass and Alon Rosen. Bounded-concurrent secure two-party computation in a constant number of rounds. In 44th FOCS, pages 404-415. IEEE Computer Society Press, October 2003. URL: https://doi.org/10.1109/SFCS.2003.1238214.
  43. Rafael Pass and Elaine Shi. Thunderella: Blockchains with optimistic instant confirmation. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 3-33. Springer, Heidelberg, April / May 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_1.
  44. Birgit Pfitzmann and Michael Waidner. Unconditional byzantine agreement for any number of faulty processors. In Annual Symposium on Theoretical Aspects of Computer Science, pages 337-350. Springer, 1992. Google Scholar
  45. Michael O. Rabin. How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, Report 2005/187, 2005. URL: https://eprint.iacr.org/2005/187.
  46. Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In 21st ACM STOC, pages 73-85. ACM Press, May 1989. URL: https://doi.org/10.1145/73007.73014.
  47. Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 3-13. IEEE, 2000. Google Scholar
  48. Adi Shamir. How to share a secret. Communications of the Association for Computing Machinery, 22(11):612-613, November 1979. Google Scholar
  49. Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In 27th FOCS, pages 162-167. IEEE Computer Society Press, October 1986. URL: https://doi.org/10.1109/SFCS.1986.25.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact