## CryptoDB

### Paper: Efficient Constructions for Almost-everywhere Secure Computation

Authors: Siddhartha Jayanti , MIT Srinivasan Raghuraman , MIT Nikhil Vyas , MIT DOI: 10.1007/978-3-030-45724-2_6 (login may be required) Search ePrint Search Google EUROCRYPT 2020 We study the problem of {\em almost-everywhere reliable message transmission}; a key component in designing efficient and secure MPC protocols for sparsely connected networks. The goal is to design low-degree networks which allow a large fraction of honest nodes to communicate reliably even while linearly many nodes can experience byzantine corruption and deviate arbitrarily from the assigned protocol.\\ \noindent In this paper, we achieve a $\log$-degree network with a polylogarithmic work complexity protocol, thereby improving over the state-of-the-art result of Chandran {\em et al.} (ICALP 2010) who required a polylogarithmic-degree network and had a linear work complexity. In addition, we also achieve: \begin{itemize} \item A work efficient version of Dwork et. al.'s (STOC 1986) butterfly network. \item An improvement upon the state of the art protocol of Ben-or and Ron (Information Processing Letters 1996) in the randomized corruption model---both in work-efficiency and in resilience.
##### BibTeX
@inproceedings{eurocrypt-2020-30254,
title={Efficient Constructions for Almost-everywhere Secure Computation},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={MPC;almost-everywhere;byzantine fault-tolerance},
volume={12105},
doi={10.1007/978-3-030-45724-2_6},
author={Siddhartha Jayanti and Srinivasan Raghuraman and Nikhil Vyas},
year=2020
}