MPC from ChatGPT

Shamir_Secret_Sharing_Scheme.py

import random

# Returns a random prime number with n bits
def generate_prime(n):
  while True:
    p = random.getrandbits(n)
    if is_prime(p):
      return p

# Returns the result of evaluating a polynomial with coefficients
# `coefficients` at point `x` using the Horner scheme
def horner(coefficients, x):
  result = 0
  for coefficient in coefficients:
    result = result * x + coefficient
  return result

# Returns the result of evaluating a polynomial with coefficients
# `coefficients` at point `x` using the Lagrange interpolation
# method
def lagrange_interpolate(coefficients, x):
  result = 0
  for i, coefficient in enumerate(coefficients):
    numerator = coefficient
    denominator = 1
    for j, coefficient2 in enumerate(coefficients):
      if i != j:
        numerator = numerator * (x - j)
        denominator = denominator * (i - j)
    result += numerator / denominator
  return result

# Generate a random polynomial with the given degree and secret
# coefficient
def generate_polynomial(degree, secret):
  coefficients = [secret] + [random.randint(1, degree) for _ in range(degree)]
  return coefficients

# Generate a set of shares using the Shamir Secret Sharing
# scheme with the given polynomial and number of shares
def generate_shares(polynomial, shares):
  points = []
  for i in range(1, shares + 1):
    points.append((i, horner(polynomial, i)))
  return points

# Recover the secret using the given shares and prime
def recover_secret(shares, prime):
  result = 0
  for i, share in enumerate(shares):
    numerator = share[1]
    denominator = 1
    for j, share2 in enumerate(shares):
      if i != j:
        numerator = numerator * (0 - share2[0])
        denominator = denominator * (share[0] - share2[0])
    result += numerator / denominator
  return result % prime

# Tests the Shamir Secret Sharing scheme
def test_shamir():
  prime = generate_prime(10)
  secret = random.randint(1, prime - 1)
  polynomial = generate_polynomial(3, secret)
  shares = generate_shares(polynomial, 5)
  recovered = recover_secret(shares, prime)
  assert secret == recovered, f"{secret} != {recovered}"

test_shamir()