Paper 2025/1007
Scalable Multiparty Computation from Non-linear Secret Sharing
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 {\em large fields} with total computation $\mathcal{O}(|C|\log|F|)$, where $|C|$ and $|F|$ denote the circuit and field size, respectively. Prior work could either achieve similar complexity only in {\em 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 {\em non-linear} secret sharing.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in CRYPTO 2024
- DOI
- 10.1007/978-3-031-68397-8_12
- Keywords
- Secure multiparty computationChinese remainder-based secret sharingScalable MPC
- Contact author(s)
-
sanjamg @ berkeley edu
abhishek @ cs jhu edu
pratyay85 @ gmail com
mingyuan @ berkeley edu - History
- 2025-06-02: approved
- 2025-05-31: received
- See all versions
- Short URL
- https://ia.cr/2025/1007
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1007,
author = {Sanjam Garg and Abhishek Jain and Pratyay Mukherjee and Mingyuan Wang},
title = {Scalable Multiparty Computation from Non-linear Secret Sharing},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1007},
year = {2025},
doi = {10.1007/978-3-031-68397-8_12},
url = {https://eprint.iacr.org/2025/1007}
}
