Paper 2021/1206

Efficient Perfectly Secure Computation with Optimal Resilience

Ittai Abraham, Gilad Asharov, and Avishay Yanai

Abstract

Secure computation enables $n$ mutually distrustful parties to compute a function over their private inputs jointly. In 1988 Ben-Or, Goldwasser, and Wigderson (BGW) demonstrated that any function can be computed with perfect security in the presence of a malicious adversary corrupting at most $t< n/3$ parties. After more than 30 years, protocols with perfect malicious security, with round complexity proportional to the circuit's depth, still require sharing a total of $O(n^2)$ values per multiplication. In contrast, only $O(n)$ values need to be shared per multiplication to achieve semi-honest security. Indeed sharing $\Omega(n)$ values for a single multiplication seems to be the natural barrier for polynomial secret sharing-based multiplication. In this paper, we close this gap by constructing a new secure computation protocol with perfect, optimal resilience and malicious security that incurs sharing of only $O(n)$ values per multiplication, thus, matching the semi-honest setting for protocols with round complexity that is proportional to the circuit depth. Our protocol requires a constant number of rounds per multiplication. Like BGW, it has an overall round complexity that is proportional only to the multiplicative depth of the circuit. Our improvement is obtained by a novel construction for {\em weak VSS for polynomials of degree-$2t$}, which incurs the same communication and round complexities as the state-of-the-art constructions for {\em VSS for polynomials of degree-$t$}. Our second contribution is a method for reducing the communication complexity for any depth-1 sub-circuit to be proportional only to the size of the input and output (rather than the size of the circuit). This implies protocols with \emph{sublinear communication complexity} (in the size of the circuit) for perfectly secure computation for important functions like matrix multiplication.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in TCC 2021
Keywords
Perfect SecuritySecure Computation
Contact author(s)
iabraham @ vmware com
Gilad Asharov @ biu ac il
yanaia @ vmware com
History
2021-10-18: revised
2021-09-17: received
See all versions
Short URL
https://ia.cr/2021/1206
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1206,
      author = {Ittai Abraham and Gilad Asharov and Avishay Yanai},
      title = {Efficient Perfectly Secure Computation with Optimal Resilience},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1206},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1206}},
      url = {https://eprint.iacr.org/2021/1206}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.