A variation of Shamir's t-of-n Secret Sharing scheme, which allows to use any given values as secret shares

modified-secret-sharing.py

#
# A variation of Shamir's t-of-n Secret Sharing scheme,
# which allows to use any `n` values as secret shares
# at the expense of having to store `(n-t)` many public shares.
# This overcomes a drawback of the orginal scheme, 
# which requires to use the secret shares resulting from the scheme.
#
# For example, for a 3-of-5 this requires to store 2 public points.
#


# Lagrange interpolation implemented by ChatGPT.
# WARNING: Haven't checked if this is fully correct
#
def lagrange_interpolation(points, field_size, x_interpolate):
    def lagrange_basis(i, x):
        basis = 1
        for j in range(len(points)):
            if j != i:
                basis *= (x - points[j][0]) * pow(points[i][0] - points[j][0], -1, field_size)
                basis %= field_size
        return basis
    
    interpolated_value = 0
    for i in range(len(points)):
        basis = lagrange_basis(i, x_interpolate)
        interpolated_value += (basis * points[i][1]) % field_size
        interpolated_value %= field_size
        
    return interpolated_value


#
# 
# Example usage for a 3-of-5 secret sharing
#
#

field_size = 100000007  # Replace with your desired finite field size

# The 5 secret shares
points = [
    (1, 42), 
    (2, 10023), 
    (3, 109),
    (4, 1024),
    (5, 777)
]  

# Interpolate the shared secret
x_interpolate = 0  # The shared secret is f(0)
interpolated_value = lagrange_interpolation(points, field_size, x_interpolate)
print(f"The secret value at x = {x_interpolate} is: {interpolated_value}")

# Sample two more points on the polynomial 
# and share them with all 5 participants to turn this into a 3-of-5
x_interpolate = 6 
public_value1 = lagrange_interpolation(points, field_size, x_interpolate)
print(f"The public value at x = {x_interpolate} is: {public_value1}")

x_interpolate = 7  
public_value2 = lagrange_interpolation(points, field_size, x_interpolate)
print(f"The public value at x = {x_interpolate} is: {public_value2}")



# Example recovery using share_2, share_3, and share_5
#
points = [
    (2, 10023), 
    (3, 109),
    (5, 777)
]

# Append the two public points
points.append( (6, public_value1) )
points.append( (7, public_value2) )

# Interpolate the shared secret, f(0)
x_interpolate = 0  
interpolated_value = lagrange_interpolation(points, field_size, x_interpolate)
print(f"The recovered secret value at x = {x_interpolate} is: {interpolated_value}")


#
# Note that we can also use this scheme for a given secret and given shares. 
# This simply requries to sample one more public share.
#