Disenrollment of Parties in Secret Shares

Disenrollment of Parties in Secret Shares

Within a secret share infrastructure, we have a number of parties, and which receive secret shares. When we bring back these shares, we can rebuild a secret value (such as encryption key). But, what happens when you need to disenroll parties from the secret share? For this, we need to redeal the shares, without revealing the original share. So, let’s look at a basic disenrollment scheme.

Lagrange interpretation constants

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² (mod 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)). For each party this is computed with:

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 of parties involved. So, for f(x)=a+bx+cx² (mod p), if we have shares of φ_1, φ_2 and φ_3, and coefficients of γ_1, γ_2 and γ_2, the secret share becomes:

The following is some sample code:

import numpy as np
import sys


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

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)}")


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 Interpoltion 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")

For a three party share and for f(x)=7+19x+21x² (mod 31) , we get shares of φ_1=16, φ_2=5 and φ_3=5, have Lagrange interpretation constants of γ_1=3, γ_2=−3.0 and γ_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

Here are some examples:

• f(x)=7+19x+21x² (mod31) Try
• f(x)=21+19x+21x² (mod31) Try
• f(x)=500+499x+78x² (mod997) Try
• f(x)=9999+7654x+501x² (mod 65537) Try

Disenroll parties

To disenroll parties, 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, such as g=7x+3x². 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² (mod 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 code with 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

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")

Here are examples, with updates using g(x):

• f(x)=7+19x+21x² (mod 31) Try
• f(x)=21+19x+21x² (mod 31) Try
• f(x)=500+499x+78x² (mod 997) Try
• f(x)=9999+7654x+501x² (mod 65537) Try

Conclusions

The great thing about the disenrollment scheme is that we can reset the share values, without revealing the original secret.