Welcome to the resource topic for 2021/1206
Title:
Efficient Perfectly Secure Computation with Optimal Resilience
Authors: Ittai Abraham, Gilad Asharov, 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.
ePrint: https://eprint.iacr.org/2021/1206
Talk: https://www.youtube.com/watch?v=hlOVTevX8JM
Slides: https://iacr.org/submit/files/slides/2021/tcc/tcc2021/196/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .