Document Open Access Logo

Universally Composable Almost-Everywhere Secure Computation

Authors Nishanth Chandran, Pouyan Forghani, Juan Garay, Rafail Ostrovsky, Rutvik Patel, Vassilis Zikas

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITC.2022.14.pdf
  • Filesize: 0.86 MB
  • 25 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
  • Security and privacy → Information-theoretic techniques
  • Security and privacy → Formal security models
Keywords
  • Secure multi-party computation
  • universal composability
  • almost-everywhere secure computation
  • sparse graphs
  • secure message transmission

Metrics

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

Abstract

Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of which might even be corrupted. The problem becomes particularly acute in the information-theoretic setting, where the lack of trusted setups (and the cryptographic primitives they enable) makes communication over sparse networks more challenging. The work by Garay and Ostrovsky [EUROCRYPT'08] on almost-everywhere MPC (AE-MPC), introduced "best-possible security" properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation.
In this work, we provide a universally composable definition of almost-everywhere security, which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous "best-possible security" version of secure communication) in the Universal Composability (UC) framework of Canetti. Our results offer the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC. To achieve that goal, we state and prove a general composition theorem, which makes precise the level or "quality" of AE-security that is obtained when a protocol’s hybrids are replaced with almost-everywhere components.

Cite As Get BibTex

Nishanth Chandran, Pouyan Forghani, Juan Garay, Rafail Ostrovsky, Rutvik Patel, and Vassilis Zikas. Universally Composable Almost-Everywhere Secure Computation. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITC.2022.14

Author Details

Nishanth Chandran
  • Microsoft Research, Bangalore, India
Pouyan Forghani
  • Texas A&M University, College Station, TX, USA
Juan Garay
  • Texas A&M University, College Station, TX, USA
Rafail Ostrovsky
  • University of California, Los Angeles, CA, USA
Rutvik Patel
  • Texas A&M University, College Station, TX, USA
Vassilis Zikas
  • Purdue University, West Lafayette, IN, USA

Funding

  • Garay, Juan: Work partially supported by NSF grants CNS-2001082 and CNS-2055694.
  • Ostrovsky, Rafail: Supported in part by DARPA under Cooperative Agreement HR0011-20-2-0025, NSF grant CNS-2001096, US-Israel BSF grant 2015782, Cisco Research Award, Google Faculty Award, JP Morgan Faculty Award, IBM Faculty Research Award, Xerox Faculty Research Award, OKAWA Foundation Research Award, B. John Garrick Foundation Award, Teradata Research Award, Lockheed-Martin Research Award and Sunday Group. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA, the Department of Defense, 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.
  • Zikas, Vassilis: Research supported in part by NSF grants CNS-2055599 and CNS-2001096, BSF grant 2020277, and by Sunday Group.

Acknowledgements

The authors are grateful to Ran Canetti for useful discussions during preliminary stages of this work.

References

  1. Saurabh Agarwal, Ronald Cramer, and Robbert de Haan. Asymptotically optimal two-round perfectly secure message transmission. In Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, volume 4117 of Lecture Notes in Computer Science, pages 394-408. Springer, 2006. URL: https://doi.org/10.1007/11818175_24.
  2. Bar Alon, Eran Omri, and Anat Paskin-Cherniavsky. MPC with friends and foes. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part II, volume 12171 of Lecture Notes in Computer Science, pages 677-706. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-56880-1_24.
  3. Michael Backes, Birgit Pfitzmann, and Michael Waidner. A composable cryptographic library with nested operations. In Sushil Jajodia, Vijayalakshmi Atluri, and Trent Jaeger, editors, Proceedings of the 10th ACM Conference on Computer and Communications Security, CCS 2003, Washington, DC, USA, October 27-30, 2003, pages 220-230. ACM, 2003. URL: https://doi.org/10.1145/948109.948140.
  4. Christian Badertscher, Ran Canetti, Julia Hesse, Björn Tackmann, and Vassilis Zikas. Universal composition with global subroutines: Capturing global setup within plain UC. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III, volume 12552 of Lecture Notes in Computer Science, pages 1-30. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_1.
  5. Christian Badertscher, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas. Bitcoin as a transaction ledger: A composable treatment. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, volume 10401 of Lecture Notes in Computer Science, pages 324-356. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-63688-7_11.
  6. Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, and Tal Rabin. Secure computation without authentication. J. Cryptol., 24(4):720-760, 2011. URL: https://doi.org/10.1007/s00145-010-9075-9.
  7. Zuzana Beerliová-Trubíniová, Matthias Fitzi, Martin Hirt, Ueli M. Maurer, and Vassilis Zikas. MPC vs. SFE: perfect security in a unified corruption model. In Ran Canetti, editor, Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008, volume 4948 of Lecture Notes in Computer Science, pages 231-250. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-78524-8_14.
  8. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 1-10. ACM, 1988. URL: https://doi.org/10.1145/62212.62213.
  9. Elette Boyle, Ran Cohen, Deepesh Data, and Pavel Hubácek. Must the communication graph of MPC protocols be an expander? In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III, volume 10993 of Lecture Notes in Computer Science, pages 243-272. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-96878-0_9.
  10. Elette Boyle, Ran Cohen, and Aarushi Goel. Breaking the o(√n)-bit barrier: Byzantine agreement with polylog bits per party. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 319-330. ACM, 2021. URL: https://doi.org/10.1145/3465084.3467897.
  11. Jan Camenisch, Stephan Krenn, Ralf Küsters, and Daniel Rausch. iuc: Flexible universal composability made simple. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part III, volume 11923 of Lecture Notes in Computer Science, pages 191-221. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-34618-8_7.
  12. Ran Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptol., 13(1):143-202, 2000. URL: https://doi.org/10.1007/s001459910006.
  13. Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 136-145. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/SFCS.2001.959888.
  14. Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067, December 2005. Latest version at URL: https://ia.cr/2000/067.
  15. Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish. Universally composable security with global setup. In Salil P. Vadhan, editor, Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007, Proceedings, volume 4392 of Lecture Notes in Computer Science, pages 61-85. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-70936-7_4.
  16. Nishanth Chandran, Pouyan Forghani, Juan Garay, Rafail Ostrovsky, Rutvik Patel, and Vassilis Zikas. Universally composable almost-everywhere secure computation. Cryptology ePrint Archive, Report 2021/1398, 2021. URL: https://ia.cr/2021/1398.
  17. Nishanth Chandran, Juan A. Garay, and Rafail Ostrovsky. Improved fault tolerance and secure computation on sparse networks. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II, volume 6199 of Lecture Notes in Computer Science, pages 249-260. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14162-1_21.
  18. David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 11-19. ACM, 1988. URL: https://doi.org/10.1145/62212.62214.
  19. Danny Dolev. Unanimity in an unknown and unreliable environment. In 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981, pages 159-168. IEEE Computer Society, 1981. URL: https://doi.org/10.1109/SFCS.1981.53.
  20. Danny Dolev, Cynthia Dwork, Orli Waarts, and Moti Yung. Perfectly secure message transmission. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I, pages 36-45. IEEE Computer Society, 1990. URL: https://doi.org/10.1109/FSCS.1990.89522.
  21. Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal. Fault tolerance in networks of bounded degree (preliminary version). In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 370-379. ACM, 1986. URL: https://doi.org/10.1145/12130.12169.
  22. Matthias Fitzi and Juan A. Garay. Efficient player-optimal protocols for strong and differential consensus. In Elizabeth Borowsky and Sergio Rajsbaum, editors, Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, PODC 2003, Boston, Massachusetts, USA, July 13-16, 2003, pages 211-220. ACM, 2003. URL: https://doi.org/10.1145/872035.872066.
  23. Matthias Fitzi, Martin Hirt, and Ueli M. Maurer. Trading correctness for privacy in unconditional multi-party computation (extended abstract). In Hugo Krawczyk, editor, Advances in Cryptology - CRYPTO '98, 18th Annual International Cryptology Conference, Santa Barbara, California, USA, August 23-27, 1998, Proceedings, volume 1462 of Lecture Notes in Computer Science, pages 121-136. Springer, 1998. URL: https://doi.org/10.1007/BFb0055724.
  24. Juan A. Garay, Aggelos Kiayias, and Hong-Sheng Zhou. A framework for the sound specification of cryptographic tasks. In Proceedings of the 23rd IEEE Computer Security Foundations Symposium, CSF 2010, Edinburgh, United Kingdom, July 17-19, 2010, pages 277-289. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/CSF.2010.26.
  25. Juan A. Garay and Rafail Ostrovsky. Almost-everywhere secure computation. In Nigel P. Smart, editor, Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings, volume 4965 of Lecture Notes in Computer Science, pages 307-323. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-78967-3_18.
  26. Juan A. Garay and Kenneth J. Perry. A continuum of failure models for distributed computing. In Adrian Segall and Shmuel Zaks, editors, Distributed Algorithms, 6th International Workshop, WDAG '92, Haifa, Israel, November 2-4, 1992, Proceedings, volume 647 of Lecture Notes in Computer Science, pages 153-165. Springer, 1992. URL: https://doi.org/10.1007/3-540-56188-9_11.
  27. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 218-229. ACM, 1987. URL: https://doi.org/10.1145/28395.28420.
  28. Jacopo Griggio. Perfectly secure message transmission protocols with low communication overhead and their generalization. PhD thesis, Universiteit Leiden, 2012. Google Scholar
  29. Martin Hirt and Ueli M. Maurer. Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract). In James E. Burns and Hagit Attiya, editors, Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, Santa Barbara, California, USA, August 21-24, 1997, pages 25-34. ACM, 1997. URL: https://doi.org/10.1145/259380.259412.
  30. Martin Hirt and Vassilis Zikas. Adaptively secure broadcast. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 466-485. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13190-5_24.
  31. Dennis Hofheinz and Victor Shoup. GNUC: A new universal composability framework. J. Cryptol., 28(3):423-508, 2015. URL: https://doi.org/10.1007/s00145-013-9160-y.
  32. Siddhartha Jayanti, Srinivasan Raghuraman, and Nikhil Vyas. Efficient constructions for almost-everywhere secure computation. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, pages 159-183. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45724-2_6.
  33. Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas. Universally composable synchronous computation. In Amit Sahai, editor, Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 477-498. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36594-2_27.
  34. Valerie King and Jared Saia. From almost everywhere to everywhere: Byzantine agreement with õ(n^3/2) bits. In Idit Keidar, editor, Distributed Computing, 23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings, volume 5805 of Lecture Notes in Computer Science, pages 464-478. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04355-0_47.
  35. Kaoru Kurosawa and Kazuhiro Suzuki. Truly efficient 2-round perfectly secure message transmission scheme. In Nigel P. Smart, editor, Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings, volume 4965 of Lecture Notes in Computer Science, pages 324-340. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-78967-3_19.
  36. Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, 1982. URL: https://doi.org/10.1145/357172.357176.
  37. Ueli Maurer and Renato Renner. Abstract cryptography. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 1-21. Tsinghua University Press, 2011. URL: http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/14.html.
  38. Jesper Buus Nielsen. On Protocol Security in the Cryptographic Model. PhD thesis, University of Aarhus, 2003. Google Scholar
  39. Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228-234, 1980. URL: https://doi.org/10.1145/322186.322188.
  40. Hasan Md. Sayeed and Hosame Abu-Amara. Efficient perfectly secure message transmission in synchronous networks. Inf. Comput., 126(1):53-61, 1996. URL: https://doi.org/10.1006/inco.1996.0033.
  41. Gabriele Spini and Gilles Zémor. Perfectly secure message transmission in two rounds. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 286-304, 2016. URL: https://doi.org/10.1007/978-3-662-53641-4_12.
  42. K. Srinathan, Arvind Narayanan, and C. Pandu Rangan. Optimal perfectly secure message transmission. In Matthew K. Franklin, editor, Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, pages 545-561. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-28628-8_33.
  43. Eli Upfal. Tolerating linear number of faults in networks of bounded degree. In Norman C. Hutchinson, editor, Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, August 10-12, 1992, pages 83-89. ACM, 1992. URL: https://doi.org/10.1145/135419.135437.
  44. Andrew Chi-Chih Yao. Space-time tradeoff for answering range queries (extended abstract). In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 128-136. ACM, 1982. URL: https://doi.org/10.1145/800070.802185.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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