International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Constructions for Almost-everywhere Secure Computation

Authors:
Siddhartha Jayanti , MIT
Srinivasan Raghuraman , MIT
Nikhil Vyas , MIT
Download:
DOI: 10.1007/978-3-030-45724-2_6 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: 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.
Video from EUROCRYPT 2020
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
}