Cryptology ePrint Archive: Report 2021/1398

Universally Composable Almost-Everywhere Secure Computation

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

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 whom might even be corrupted. 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—we call such parties “doomed.”

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 result offers the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC.

Category / Keywords: cryptographic protocols / Secure multi-party computation, universal composability, almost-everywhere secure computation, sparse graphs, secure message transmission

Date: received 16 Oct 2021, last revised 18 Oct 2021

Contact author: rsp7 at tamu edu, pouyan forghani at tamu edu, garay at tamu edu

Available format(s): PDF | BibTeX Citation

Version: 20211018:151553 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]