Secure multi-party computation: Difference between revisions

Revision as of 16:23, 16 October 2023

Revision as of 08:41, 18 November 2023

Line 85:

Secret sharing allows one to distribute a secret among a number of parties by distributing shares to each party. Two types of secret sharing schemes are commonly used; [[Shamir's Secret Sharing|Shamir secret sharing]] and additive secret sharing. In both cases the shares are random elements of a finite field that add up to the secret in the field; intuitively, security is achieved because any non-qualifying set of shares looks randomly distributed.

Secret sharing schemes can tolerate an adversary controlling up to ''t'' parties out of ''n'' total parties, where ''t'' varies based on the scheme, the adversary can be passive or active, and different assumptions are made on the power of the adversary. The Shamir secret sharing scheme is secure against a passive adversary when <math>t < \frac{n}{2}</math> and an active adversary when <math>t < \frac{n}{3}</math> while achieving information-theoretic security, meaning that even if the adversary has unbounded computational power, they cannot learn any information about the secret underlying a share. The BGW protocol,<ref>{{Cite book|last1=Ben-Or|first1=Michael|last2=Goldwasser|first2=Shafi|last3=Wigderson|first3=Avi|datetitle=1988Proceedings of the twentieth annual ACM symposium on Theory of computing -01-01 STOC '88 |titlechapter=Completeness theorems for non-cryptographic fault-tolerant distributed computation |date=1988-01-01|publisher=ACM|pages=1–10|doi=10.1145/62212.62213|isbn=978-0897912648|s2cid=207554159}}</ref> which defines how to compute addition and multiplication on secret shares, is often used to compute functions with Shamir secret shares. Additive secret sharing schemes can tolerate the adversary controlling all but one party, that is <math>t < n</math>, while maintaining security against a passive and active adversary with unbounded computational power. Some protocols require a setup phase, which may only be secure against a computationally bounded adversary.

A number of systems have implemented various forms of MPC with secret sharing schemes. The most popular is SPDZ,<ref name="SPDZ">I. Damgård, V. Pastro, N. Smart and S. Zakarias, "Multiparty computation from somewhat homomorphic encryption," Crypto 2012, vol. Springer LNCS 7417, pp. 643-662, 2012.</ref> which implements MPC with additive secret shares and is secure against active adversaries.