Scalable Multiparty Computation from~Non-linear Secret Sharing
Technical Overview
- Existing information theoretic MPC protocols use secret sharing to evaluate gates of the circuit.
- The methodology is secret share the inputs of the gate, perform operations to obtain the secret shares of the output of the gate.
- So the share size adds a multiplicative factor in the computational complexity of the circuit evaluation.
- Let us define the download rate as the ratio between the secret size and the total share size. Here total share size is the size of all the shares needed to reconstruct the secret.
- (DID NOT UNDERSTAND) So if we want to do better than \(C\cdot p_0\), we need to ensure that the download rate is \(O(1)\).
- Now, linear secret sharing by definition considers schemes where the secret and the share come from the same field \(F_{p_0}\).
- So the download rate is \(\le |F_{p_0}|/|t\cdot F_{p_0}| = 1/n\).
- You can use share packing to make it amortized constant download rate.
- There is a problem with the amortization. One packed sharing contains \(O(t)\) shares. You need to apply the same operation on all of the packed shares simultaneously. E.g., if you add two packed shares, the output will have added all the packed shares. What if you wanted some of them to be inputs to an addition gate while the others as inputs to a different gate, say multiplication?
- People have tried to make the best of this by showing that this is like doing SIMD operations and thus using compiler optimizations. But the problem remains open for general circuits.
Notes
Informal theorems summarizing their results (from their paper):
Honest majority Semi-honest
For any constant $\delta\in (0,1/2)$, any prime field $F_p$ such that $\log{p}=\Omega(n^2\log{n})$, and any arithmetic circuit $C$ over $F$, there is an unconditional secure MPC protocol realizing $C$ among $n$ parties against $t=(1/2-\delta)\cdot n$ semi-honest corruptions. This protocol is perfectly correct and $\mathsf{poly}(|C|/|F|)$-statistically secure. Moreover, the total communication and computation (measured at bit-level) of the protocol is $O(|C|\cdot\log{|F|})$.
Dishonest-majority semi-honest
For any constant $\delta\in (0,1/2)$, any prime field $F_p$ such that $\log{p}=\Omega(n^2\log{n})$, and any arithmetic circuit $C$ over $F$, in the correlated randomness model, there is an unconditional secure MPC protocol realizing $C$ among $n$ parties against $t=(1-\delta)\cdot n$ semi-honest corruptions. This protocol is perfectly correct and $\mathsf{poly}(|C|/|F|)$-statistically secure. Moreover, the total communication and computation (measured at bit-level) of the protocol is $O(|C|\cdot\log{|F|})$.