Paper 2021/1398

Universally Composable Almost-Everywhere Secure Computation

Nishanth Chandran, Microsoft Research (India)
Pouyan Forghani, Texas A&M University
Juan Garay, Texas A&M University
Rafail Ostrovsky, University of California, Los Angeles
Rutvik Patel, Texas A&M University
Vassilis Zikas, Purdue University West Lafayette

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Information-Theoretic Cryptography (ITC) 2022
Secure multi-party computationuniversal composabilityalmost-everywhere secure computationsparse graphssecure message transmission
Contact author(s)
pouyan forghani @ tamu edu
garay @ tamu edu
rsp7 @ tamu edu
2023-05-19: last of 3 revisions
2021-10-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nishanth Chandran and Pouyan Forghani and Juan Garay and Rafail Ostrovsky and Rutvik Patel and Vassilis Zikas},
      title = {Universally Composable Almost-Everywhere Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1398},
      year = {2021},
      doi = {10.4230/LIPIcs.ITC.2022.14},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.