Big Secrets Small Shares: Revisiting Secure Multi-Party Computation
Abstract
At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.
Related
- On the use of G-computation in small randomized controlled trials with many covariates
- A Planar Switching Neuron Shares Logarithmic First-Spike Latency with Its Three-Dimensional Parent But Not Its Onset Mechanism
- Constructions of Secure Convertible Codes
- Progressive-Resolution Secure Aggregation for Federated Learning
- Secure Domination in Odd-order Sierpinski Graphs
BibTeX
@misc{kim2026secrets,
title = {{Big Secrets Small Shares: Revisiting Secure Multi-Party Computation}},
author = {Wilton Kim and Van Long Phuoc Pham and Stanislav Kruglik and Han Mao Kiah},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27609},
eprint = {2610.27609},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27609},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Big Secrets Small Shares: Revisiting Secure Multi-Party Computation
AU - Wilton Kim
AU - Van Long Phuoc Pham
AU - Stanislav Kruglik
AU - Han Mao Kiah
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27609
UR - https://arxiv.org/abs/2610.27609
AB - At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.
ER -