Universally Composable Almost-Everywhere Secure Computation

doi:10.1007/s00145-025-09565-2

Universally Composable Almost-Everywhere Secure Computation

2026-01-15

0

PRE

AI

DOI：10.1007/s00145-025-09565-2

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Secure multi-party computation

Universal composability

Almost-everywhere secure computation

Sparse graphs

Secure message transmission

Universally Composable Almost-Everywhere Secure Computation

Abstract

Journal

Organization