@inproceedings{chandran2022universally,
author = {Chandran, Nishanth and Forghani, Pouyan and Garay, Juan and Patel, Rutvik and Ostrovsky, Rafail and Zikas, Vassilis},
title = {Universally Composable Almost-Everywhere Secure Computation},
booktitle = {Information Theoretic Cryptography Conference (ITC 2022)},
year = {2022},
month = {May},
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.},
url = {http://approjects.co.za/?big=en-us/research/publication/universally-composable-almost-everywhere-secure-computation/},
}