Multi party computation communication costs cut with new secret sharing method
Big Secrets Small Shares: Revisiting Secure Multi-Party Computation
Cryptography and SecurityInformation Theory
Summary
Multi-party computation allows multiple people to jointly compute a result without revealing their private inputs. Previous methods had tradeoffs in communication cost, especially when working with complex data fields. This paper combines two earlier ideas to reduce communication needed for these computations, introducing a new 'compact sharing' method. This approach improves efficiency while maintaining strong security against certain types of passive attackers.
What this means in practice
- •For cryptographic protocol developers: Implement more communication-efficient secure computations for privacy-preserving data processing protocols using the compact sharing modification.
- •For secure cloud service engineers: Reduce bandwidth costs when deploying multi-party computation for secure outsourcing of data analysis using the combined preprocessing and compact sharing approach.
Authors
Wilton Kim, Van Long Phuoc Pham, Stanislav Kruglik, Han Mao Kiah
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.