Paper 2021/1398

Universally Composable Almost-Everywhere Secure Computation

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


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
Preprint. Minor revision.
Secure multi-party computationuniversal composabilityalmost-everywhere secure computationsparse graphssecure message transmission
Contact author(s)
rsp7 @ tamu edu
pouyan forghani @ tamu edu
garay @ tamu edu
2022-02-10: last of 2 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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.