MPC (Multi-party Computation)
Definition
Given \(n\) parties, design a protocol which computes a public function \(f\) over inputs from each party such that the inputs remain private unless they would be revealed by the function anyway.
Character
- Typically, all parties will receive the same output when the calculation finishes
- MPC is typically considered when parties don’t trust either the others or a 3rd party
- An MPC protocol can be shown equivalent to a protocol uses a trusted 3rd party
There are many setups that can be used for MPC. However, in this post, we'll only take a look at Secret Sharing and its application BGW protocol.
Adversarial Models
- Honest-but-curious, Semi-Honest, Passive: Parties follow protocol, but are interested (i.e. curious) in breaking privacy of other parties. Also know as corrupt parties.
- Malicious, Byzantine, Active: Parties can deviate from the protocol e.g. lie about inputs, quit protocol early.
Secure Type
- Information theoretically secure: system cannot be broken even if adversary has unlimited computational power. Also known as Perfect security and Unconditional security.
- Computationally secure: adversary would require an unreasonably large amount of computational power to break the system.
Theoretical Limit of Adversary and Security
- Honest-but-curious adversary, Information theoretically secure: tolerate up to \(n/2\) corrupt parties
- Honest-but-curious adversary, Computationally secure: tolerate up to \(n-1\) corrupt parties
- Malicious adversary, Information theoretically secure: tolerate up to \(n/3\) adversaries
- Malicious adversary, Computationally secure: tolerate up to \(n/2\) adversaries (unfair/un-robust protocol can tolerate up to \(n-1\) adversaries)
Lagrange Interpolation
Distribution and Recombination
- A polynomial \(P(x)\) of degree \(T\) can be uniquely determined by a set of \(T + 1\) (or more) distinct points on the polynomial curve \(P(x)\).
- A polynominal \(P(x)\) of degree upto at most \(N − 1\) there exist coefficients \(r = (r_1,\cdots,r_N )\) (called the recombination vector) such that:
\[P(0)=\sum_{i=1}^Nr_iP(i)\]
Lagrange Interpolation
Given \(T\) points \((x_1,P(x_1)),\cdots,(x_n,P(x_n))\), the unique Lagrange Interpolation Polynomial of degree T is:
\[P(x)=\sum_{i=1}^{T+1}\delta_i(x)P(x_i),~\delta_i(x)=\prod_{j=1,j\neq i}^{T+1}\frac{x-x_j}{x_i-x_j}\]
We also have:
\[P(0)=\sum_{i=1}^{T+1}\delta_i(0)P(x_i)=\sum_{i=1}^{T+1}r_iP(x_i)\Rightarrow r_i=\prod_{j=1,j\neq i}^{T+1}\frac{x_j}{x_j-x_i}\]
And when \(x_i=i\):
\[r_i=\prod_{j=1,j\neq i}^{T+1}\frac{j}{j-i}\]
Secret Share
You may have already noticed that Lagrange Interpolation can be used to share(split) secret. For example, if someone have a secret \(a_0\), and he randomly choose coefficients \(a_1,\cdots,a_T\), we obtain a polynomial \(P(x)=a_0+\sum_{i=1}^Ta_ix^i\). And if he sends shares \(P(1),\cdots,P(N)\) to \(N\) parties, then the only way to recover the secret is perform recombination on at least \(T+1\) shares (from at least \(T+1\) parties).
BGW Protocol
From the definition of MPC, we need to calculate a public function \(f\). For convenience, we consider \(f:\mathcal{N^*}\rightarrow\mathcal{N}\) which is a polynomial over a finite field modulo a prime \(p\). Thus, we can only consider two gates(operations): Add(addition) and Mul(multiplication). In this post, we'll only take a look at the honest-but-curious version.
Arithmetic over a finite field rules out the possibility of 'guessing' the secret. It makes us impossible to determine the range of the secret with less than \(T+1\) shares. See wikipedia for more details.
We will look at a three-party example. Three parties are \((p_1,p_2,p_3)\) and their secrets(private values) are \((x_1,x_2,x_3)=(10,20,30)\). They want to calculate \((x_1+x_2)\times x_3\). They choose prime \(p=101\) and degree \(T=1\). We also need \(2T\leq N-1\), the reason of which is lied in the Mul gate.
Distribution
At first, each party needs to distribute it secret into \(N\) shares and send them to \(N\) parties (also include saving his own share).
- For \(p_1\), he chooses polynomial \(3x+10\), and the shares are \(13, 16, 19\).
- For \(p_2\), he chooses polynomial \(2x+20\), and the shares are \(22, 24, 26\).
- For \(p_3\), he chooses polynomial \(1x+30\), and the shares are \(31, 32, 33\).
After distribution
- \(p_1\) has shares \(13,22,31\)
- \(p_2\) has shares \(16,24,32\)
- \(p_3\) has shares \(19,26,33\)
Add Gate
Suppose we have two secrets \(a\) and \(b\) which are shared using the polynomials: \[f(x)=a+f_1x+\cdots,f_tx^T,g(x)=b+g_1x+\cdots,g_tx^T\] Each of our parties has a share \(a^{(i)}=f(i)\) and \(b^{(i)}=g(i)\). Now consider the polynomial: \[h(x)=f(x)+g(x)\] This polynomial provides a sharing of the sum \(c = a + b\), and we have \[c^{(i)}=h(i)=f(i)+g(i)=a^{(i)}+b^{(i)}\]
Let's go into the example. We want to calculate \(x_1+x_2\) first. And for each party, he needs to add the share from \(p_1\) and the share from \(p_2\).
- \(p_1\) calculates \(a^{(1)}+b^{(1)}=13+22=35\)
- \(p_2\) calculates \(a^{(2)}+b^{(2)}=16+24=40\)
- \(p_3\) calculates \(a^{(3)}+b^{(3)}=19+26=45\)
And you can see if we combine these values together by using the recombination vector, we have \([3,-3,1][35,40,45]^\top=30\), which equals to the 'true' value \(x_1+x_2=30\).
Multiplication Gate
To compute the Multiplication gate we perform the following four steps:
- Each party \(i\) locally computes \(d^{(i)}=a^{(i)}\times b^{(i)}\)
- Each party \(i\) perform distribution of \(d^{(i)}\) (party \(j\) receives the sub-share \(d_{i,j}\) from party \(i\)) by polynomial \(\delta_i(x)\) of degree \(T\)
- Each party \(j\) recombination the sub-shares as \(c^{(j)}=\sum_{i=1}^Nr_i\times d_{i,j}\)
So why does this work? Consider the first step; here we are actually computing a polynomial of degree \(2T\). Hence, we need to 'reduce' the degree of this polynomial. Thus, we produce \(\delta_i(x)\) in the second step. Consider what happens when we recombine them using the recombination vector, i.e. let: \[h(x)=\sum_{i=1}^Nr_i\delta_i(x)\] Then we have \[h(0)=\sum_{i=1}^Nr_i\delta_i(0)=\sum_{i=1}^Nr_id^{(i)}=c\] \[h(j)=\sum_{i=1}^Nr_i\delta_i(j)=\sum_{i=1}^Nr_id_{i,j}=c^{(j)}\] Thus, \(h(x)\) is a polynomial which could be used to share the value of the product and underlies the sharing produced in the final step.
Let's take a look at the example.
- \(p_1,p_2,p_3\) calculates \(d^{(1)}=35\times31=75,d^{(2)}=68,d^{(3)}=71\)
- \(p_1\) distributes \(78,81,84\), \(p_2\) distributes \(70,72,74\), \(p_3\) distributes \(72,73,74\)
- \(p_1\) has shares \(78,70,72\), \(p_2\) has shares \(81,72,73\), \(p_3\) has shares \(84,74,74\)
- \(p_1,p_2,p_3\) recombines as \(c^{(1)}=[3,-3,1][78,70,72]^\top=96,c^{(2)}=100,c^{(3)}=3\)
Recombination
Each party broadcasts its value, and performs recombination.
As the end of the example, each party obtains \(96,100,3\) and calculates the result as \([3,-3,1][96,100,3]^\top=92\), which equals to the 'true' value \((x_1+x_2)\times x_3=92\).
Reference
Smart, Nigel P. Cryptography made simple. Springer, 2016.
