Secure Multiparty Computation (MPC)
Currently, proof generation is supported with two different MPC protocols:
- 3-party replicated secret sharing (based on ABY31) with semi-honest security
- N-party Shamir secret sharing2 (based on DN073) with semi-honest security
Notation
With we denote that is additively secret shared amongst parties, such that and . With we denote that is binary secret shared amongst parties, such that and . With we denote that is Shamir secret shared amongst parties, such that and such that is a polynomial of degree with . Similar, for a group element in an additive Group (e.g., elliptic curve groups) we denote by its additive secret sharing amongst parties, and by its Shamir sharing, such that . Furthermore, indices of shares are taken modulo the number of parties.
3-Party Replicated Sharing
Replicated secret sharing is based on additive secret sharing, with the twist that each party has multiple additive shares. Thus, in the 3-party case a secret is shared the following way. First, the is split into three random shares such that and each party gets two shares:
Rng setup
Random values are required during many parts of MPC executions. For cheaper randomness generation, correlated random number generators are set up before protocol execution.
Random Values
In order to create random shares , random additive shares of (i.e., ), or random binary shares of (i.e., ) without interaction, Rep3 sets up a correlated random number generator during the setup phase. Each party chooses a seed and sends it to the next party . Thus, each party has two seeds and can set up an RNG's, where two party are able to create the same random numbers:
Binary To Arithmetic Conversion
For the binary to arithmetic conversion, we need correlated randomness as well. The goal is to setup RNG's, such that:
In other words, and can use RNG1 create the same field element, while all parties can sample valid shares for it. Similar, and can use RNG2 to create the same field element, while all parties can sample valid shares for it. This setup can be achieved by sampling seeds from the already set up RNG for shared random values and resharing the seeds correctly.
Supported operations
Linear Operations
Due to being based on additive secret sharing, linear operations can be performed on shares without party interaction.
- Constant addition:
- Share addition:
- Constant Multiplication:
Similar, linear operations can be computed locally in the binary domain as well.
- Constant addition:
- Share addition:
- Constant Multiplication:
Multiplications
One main advantage of replicated secret sharing is the presence of a simple multiplication protocol. First, due to having two additive shares, each party can calculate an additive share of the result without interaction. For , is a valid additive share of .
Thus, multiplications involve a local operation followed by a resharing of the result to translate the additive share to a replicated share. Resharing requires to randomize the share to not leak any information to the other party. For that reason, a fresh random share of zero is added, which can be sampled locally without party interaction (see RNG setup).
Thus, party calculates: