2026-07-25T03:04:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16492 2024-03-06T10:57:37Z ddc:004 open_access

Universally Composable Almost-Everywhere Secure Computation Chandran, Nishanth Forghani, Pouyan Garay, Juan Ostrovsky, Rafail Patel, Rutvik Zikas, Vassilis Secure multi-party computation universal composability almost-everywhere secure computation sparse graphs secure message transmission 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nishanth Chandran and Pouyan Forghani and Juan Garay and Rafail Ostrovsky and Rutvik Patel and Vassilis Zikas 2022 Is Part Of LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2022.14 urn:nbn:de:0030-drops-164929 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode