Paper cuts multi-party computation communication with compact secret sharing
Original title: Big Secrets Small Shares: Revisiting Secure Multi-Party Computation
Combining CRYPTO 2007 preprocessing with a modified ramp scheme yields constant amortized gate-evaluation communication under stated conditions.
The paper combines Damgård and Nielsen’s preprocessing approach with ideas from Cramer, Damgård, and de Haan’s ramp secret sharing to reduce communication in multi-phase MPC. A modification called compact sharing masks polynomial coefficients that could leak during degree reduction. The protocol claims perfect security against static semi-honest adversaries, with 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 has constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.
- The work revisits preprocessing from CRYPTO 2007 and ramp sharing from EUROCRYPT 2007.
- Compact sharing is designed to hide coefficients during degree reduction.
- Security is perfect against static semi-honest adversaries, not malicious ones.
- Input and output communication is excluded from the constant-overhead claim.
From the original article
1 min read at arxiv.orgAt 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.
By Wilton Kim · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.