Disenroll Parties with Shamir Secret Share and Lagrange interpretation constantsShamir's secret sharing method generates a number of shares, of which a threshold defines the number of shares which can be used to re-build the message. With this we define a threshold value (\(t\)) and where we have \(n\) shares. For a threshold of 3, we create a polynomial which is in the form of \(f(x)=a+bx+cx^2 \pmod p\). The secret is \(a\). With three parties involved we then create shares for the split with \(f(x=1)\), \(f(x=2)\) and \(f(x=3)\), and where \(f(x=0)\) is the secret. With these shares, we use Lagrange interpretation constants to rebuild the secret value (\(f(x=0)\)). To disenroll nodes, we need to update the shares with a new polynomial. For this we add a new random polynomial (\(g(x)\)) and which creates a new polynomial share: \(f'(x)=f(x)+g(x)\). For this \(g(x)\) has a zero constant value. |
Outline
Shamir's secret sharing method generates a number of shares, of which a threshold defines the number of shares which can be used to re-build the message. With this we define a threshold value (\(t\)) and where we have \(n\) shares. For a threshold of 3, we create a polynomial which is in the form of:
\(f(x)=a+bx+cx^2 \pmod p\)
The secret is \(a\). With three parties involved we then create shares for the split with \(\varphi_1=f(x=1)\), \(\varphi_2=f(x=2)\) and \(\varphi_3=f(x=3)\), and where \(f(x=0)\) is the secret. With these shares, we use Lagrange interpretation constants to rebuild the secret value (\(f(x=0)\)). For each party (\(i\)) this is computed with:
\(\gamma_i=\prod\limits_{1 \le j \le t, i\ne j} \frac{k-j}{i-j}\)
In Python, this can be coded as:
def coef(i,n): num=1 denom=1 for x in range(1, n+1): if (x!=i): num=num*x denom=denom*(i-x) return(num/denom)
And where \(i\) is the node identifier, and \(n\) is the number parties involved. So, for \(f(x)=a+bx+cx^2 \pmod p\), if we have shares of \(\varphi_1\), \(\varphi_2\) and \(\varphi_3\), and coefficients of \(\gamma_1\), \(\gamma_2\) and \(\gamma_2\), the secret share becomes:
\(f_0=\gamma_1.\varphi_1 + \gamma_2.\varphi_2 + \gamma_3.\varphi_3 \)
For a three party share and for \(f(x)=7+19x+21x^2 \pmod {31}\), we get shares of \(\varphi_1=16\), \(\varphi_2=5\) and \(\varphi_3=5\), have Lagrange interpretation constants of \(\gamma_1=3\), \(\gamma_2=-3.0\) and \(\gamma_3=1\), we get:
Polnomial: 2 21 x + 19 x + 7 Prime: 31 Shares: f_1=16, f_2=5, f_3=5 Lagrange Interpolation constants: c_1=3.0, c_2=-3.0, c_3=1.0 Recovered secret: f_0 (secret)=7 Successful recovery
An outline is of this is:
Disenrollment
To disenroll nodes, we need to update the shares with a new polynomial. For this we add a new random polynomial (\(g(x)\)) and which creates a new polynomial share:
\(f'(x)=f(x)+g(x)\)
For this \(g(x)\) has a zero constant value.
With disenrollment, we can update each of the shares with another round. Each player generates a new polynomial which has a zero constant. In the following case, Player 1 generates:
\(g(x)=7x+3x^2 \pmod {31}\)
and where \(g(1)=10\), \(g(2)=26\) and \(g(3)=17\). Player 1 sends these new values out, and where each player will update their share values. In this case, Player 2 will get 26 and Player 3 will get 17. These add these values to their existing shares. As we can see, the secret share value will stay the same:
The updated coding using a random polynomial is:
import numpy as np import sys import random def compute(poly,p,x): d=(int(poly[2])+int(poly[1])*x+int(poly[0])*x*x) % p return (int(d)) def coef(i,n): num=1 denom=1 for x in range(1, n+1): if (x!=i): num=num*x denom=denom*(i-x) return(num/denom) p=31 a=7 b=19 c=21 if (len(sys.argv)>1): a=int(sys.argv[1]) if (len(sys.argv)>2): b=int(sys.argv[2]) if (len(sys.argv)>3): c=int(sys.argv[3]) if (len(sys.argv)>4): p=int(sys.argv[4]) A=[c,b,a] f_1=compute(A,p,1) f_2=compute(A,p,2) f_3=compute(A,p,3) print (f"Polnomial:\n{np.poly1d(A)}") print (f"Prime: {p}\n") f_0=int(( (f_1)*coef(1,3)+(f_2)*coef(2,3)+(f_3)*coef(3,3))%p) print (f"Shares: f_1={f_1}, f_2={f_2}, f_3={f_3}") print (f"Lagrange Interpolation constants:\nc_1={coef(1,3)}, c_2={coef(2,3)}, c_3={coef(3,3)}\n") print (f"Recovered secret: f_0 (secret)={f_0}") if (f_0==A[2]): print("Successful recovery") print("\n== Now refreshing shares ===") d=random.randint(0, p) e=random.randint(0, p) B=[e,d,0] g_1=compute(B,p,1) g_2=compute(B,p,2) g_3=compute(B,p,3) f_1_new = f_1+g_1 f_2_new = f_2+g_2 f_3_new = f_3+g_3 print (f"Polnomial (g):\n{np.poly1d(B)}") f_0=int(( (f_1_new)*coef(1,3)+(f_2_new)*coef(2,3)+(f_3_new)*coef(3,3))%p) print (f"New shares: f_1={f_1_new}, f_2={f_2_new}, f_3={f_3_new}") print (f"Lagrange Interpolation constants:\nc_1={coef(1,3)}, c_2={coef(2,3)}, c_3={coef(3,3)}\n") print (f"Recovered secret: f_0 (secret)={f_0}") if (f_0==A[2]): print("Successful recovery")
Coding
The coding is here: