Virtual Presentation - ET - Remote Access - Zoom
GILAD ASHAROV , Postdoctoral Researcher
Power in Weakness: Efficient Perfectly Secure Multiplication with Optimal Resilience and Constant Time
Secure computation enables n mutually distrustful parties to compute a function over their private inputs jointly. A fundamental result in the area is that of Ben-Or, Goldwasser, and Wigderson (BGW) in 1988, showing that any function can be computed with perfect security in the presence of a malicious adversarial entity controlling at most t < n/3 parties.
A crucial part in the construction of BGW is a protocol for multiplying two shared values. Despite 30 years of research, the protocol requires sharing a total of O(n2) values per multiplication. In contrast, the semi-honest protocol of BGW and comparable protocols in the computational settings that are based on secret sharing require the sharing of O(n) values for a single multiplication. In this paper close this gap, leading to a more efficient construction while maintaining a round complexity that is constant per multiplication. Our result is obtained by exploring the limits of verifiable secret sharing and constructing a protocol for weak verifiable secret sharing of a polynomial of degree-2t with the same communication complexity and round complexity as strong verifiable secret sharing of a polynomial of degree-t.
Besides efficiency improvements, our protocol overall simplifies the BGW construction, which has also pedagogical significance due to its centrality. In addition, we show how our new approach improves the efficiency of depth-1 computations, e.g., matrix multiplications.
Joint work with: Ittai Abraham and Avishay Yahai.
Zoom Participation. See announcement.
For More Information: