Paper 2024/245

Linear-Communication Asynchronous Complete Secret Sharing with Optimal Resilience

Xiaoyu Ji, Tsinghua University
Junru Li, ShanghaiTech University
Yifan Song, Tsinghua University, Shanghai Qi Zhi Institute
Abstract

Secure multiparty computation (MPC) allows a set of $n$ parties to jointly compute a function on their private inputs. In this work, we focus on the information-theoretic MPC in the \emph{asynchronous network} setting with optimal resilience ($t<n/3$). The best-known result in this setting is achieved by Choudhury and Patra [J. Cryptol '23], which requires $O(n^4\kappa)$ bits per multiplication gate, where $\kappa$ is the size of a field element. An asynchronous complete secret sharing (ACSS) protocol allows a dealer to share a batch of Shamir sharings such that all parties eventually receive their shares. ACSS is an important building block in AMPC. The best-known result of ACSS is due to Choudhury and Patra [J. Cryptol '23], which requires $O(n^3\kappa)$ bits per sharing. On the other hand, in the synchronous setting, it is known that distributing Shamir sharings can be achieved with $O(n\kappa)$ bits per sharing. There is a gap of $n^2$ in the communication between the synchronous setting and the asynchronous setting. Our work closes this gap by presenting the first ACSS protocol that achieves $O(n\kappa)$ bits per sharing. When combined with the compiler from ACSS to AMPC by Choudhury and Patra [IEEE Trans. Inf. Theory '17], we obtain an AMPC with $O(n^2\kappa)$ bits per multiplication gate, improving the previously best-known result by a factor of $n^2$. Moreover, with a concurrent work that improves the compiler by Choudhury and Patra by a factor of $n$, we obtain the first AMPC with $O(n\kappa)$ bits per multiplication gate.

Note: Adding Solution for ACSS over Smaller Fields

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2024
Contact author(s)
jixy23 @ mails tsinghua edu cn
lijr2 @ shanghaitech edu cn
yfsong @ mail tsinghua edu cn
History
2024-07-09: last of 2 revisions
2024-02-15: received
See all versions
Short URL
https://ia.cr/2024/245
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/245,
      author = {Xiaoyu Ji and Junru Li and Yifan Song},
      title = {Linear-Communication Asynchronous Complete Secret Sharing with Optimal Resilience},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/245},
      year = {2024},
      url = {https://eprint.iacr.org/2024/245}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.