Efficient Perfectly Secure Computation with Optimal Resilience

Autor:	Gilad Asharov, Ittai Abraham, Avishay Yanai
Rok vydání:	2021
Předmět:	Discrete mathematics Polynomial Computer science Round complexity Secure multi-party computation Multiplication Function (mathematics) Adversary Resilience (network) Secret sharing
Zdroj:	Theory of Cryptography ISBN: 9783030904524 TCC (2)
Popis:	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 \(\varOmega (n)\) values for a single multiplication seems to be the natural barrier for polynomial secret sharing-based multiplication.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::8bdbbae705eac2b5c4250f02baf4c0ea https://doi.org/10.1007/978-3-030-90453-1_3 Zobrazit plný text záznamu