International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Scalable Multiparty Computation from Non-linear Secret Sharing

Authors:
Sanjam Garg , UC Berkeley
Abhishek Jain , Johns Hopkins University
Pratyay Mukherjee , Supra Research
Mingyuan Wang , UC Berkeley
Download:
DOI: 10.1007/978-3-031-68397-8_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: A long line of work has investigated the design of scalable secure multiparty computation (MPC) protocols with computational and communication complexity independent of the number of parties (beyond any dependence on the circuit size). We present the first unconditionally-secure MPC protocols for arithmetic circuits over *large fields* with total computation $\bigO{|C|\log|F|}$, where $|C|$ and $F|$ denote the circuit and field size, respectively. Prior work could either achieve similar complexity only in *communication*, or required highly structured circuits, or expensive circuit transformations. To obtain our results, we depart from the prior approach of share packing in linear secret-sharing schemes; instead, we use an ``unpacking'' approach via *non-linear* secret sharing.
BibTeX
@inproceedings{crypto-2024-34203,
  title={Scalable Multiparty Computation from Non-linear Secret Sharing},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68397-8_12},
  author={Sanjam Garg and Abhishek Jain and Pratyay Mukherjee and Mingyuan Wang},
  year=2024
}