【隐私计算】 秘密共享方案

Shamir 秘密共享方案

Shamir’s Secret Sharing Scheme is based on Lagrange Interception.

Now suppose there are $n$ people, and $t$ is the threshold for secret recovery

Construct a polynimal at first, the form like:

$$ P(x) = a_{t-1}x^{t-1} + a_{t-2}x^{t-2} + \cdots + a_2x^2 + a_1x + a_0 $$

Setting $a_0$ as the secret. Each person is allocated a secret share represented as $(i, a_{i}x^{i})$.

For the secret recovery, we need to construct a Lagrange Interception to compute the coefficients $a_0$(secret). The Lagrange Interpolation method is as follows

$$L(x) = \sum_{j=0}^{n} y_j \prod_{\substack{i=0 \ i \neq j}}^{n} \frac{x - x_i}{x_j - x_i}$$

In the above formula, by setting $x = 0$, the value of $a_0$ can be calculated.

Python code for implementing the Shamir Secret Sharing Scheme:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# Shamir
import random
from math import ceil
from decimal import Decimal
 
# a large size, make sures that the shares can not to be brute-forced
FIELD_SIZE = 10**5

def compute_coefficients(t, secret):
    coeff = [random.randrange(0, FIELD_SIZE) for _ in range(t-1)]
    coeff.append(secret) # secret is in the last
    return coeff

def compute_polynomial(x, coefficients):
    polynomial = 0
    for index, values in enumerate(coefficients[::-1]): # we need to reverse in here because the secret(a0) is in the last
        polynomial += x ** index * values
    return polynomial

def generate_shares(n, t, secret):
    coefficients = compute_coefficients(t,secret)
    shares = []
    for i in range(1, n+1):
        x = random.randrange(0,FIELD_SIZE)
        shares.append((x, compute_polynomial(x,coefficients)))
    return shares

def reconstruct_secret(shares):
    sums = 0
    for i, share_i in enumerate(shares):
        xi, yi = share_i
        # use decimal to make sure that we can get an accurate integer
        prod = Decimal(1)
        for j, share_j in enumerate(shares):
            xj, _ = share_j
            if i!=j:
                prod *= Decimal(Decimal(xj)/(xj-xi)) # lagrange interception
                
        prod *= yi
        sums += prod
    return int(round(Decimal(sums),0)) # get the integer secret

# Driver code
if __name__ == '__main__':
 
    # n peoples, and the threshold is t
    t, n = 3, 5
    secret = 114514
    print(f'Original Secret: {secret}')
 
    # Generate the shares
    shares = generate_shares(n, t, secret)
    print(f'Shares: {", ".join(str(share) for share in shares)}')
 
    # Reconstruct the secret
    # Picking t shares randomly for
    pool = random.sample(shares, t)
    print(f'Reconstructed secret: {reconstruct_secret(pool)}')

Reference: https://www.geeksforgeeks.org/implementing-shamirs-secret-sharing-scheme-in-python/

基于中国剩余定理的秘密共享方案

CRT(Chinese Remainder Theory) can be used to solve the Secret Sharing. My seudocode is as follow:

python code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 基于中国剩余定理的秘密共享方案
import sympy as sp
import random
import math
from libnum import solve_crt,generate_prime

def generate_primes(n, S):
    """
    生成 n 个根据 S 调整大小的随机质数
    """
    lower_bound = 10  # 下限
    upper_bound = int(math.sqrt(S))  # 上限
    primes = []
    for _ in range(n):
        primes.append(sp.randprime(lower_bound, upper_bound))
    return primes

def check_conditions(numbers, t, S):
    """
    检查条件是否满足
    """
    numbers.sort()
    product_smallest_t = math.prod(numbers[:t])
    product_largest_t_minus_1 = math.prod(numbers[-(t-1):])
    return product_smallest_t > S and product_largest_t_minus_1 < S

def find_numbers(n, t, S):
    """
    找到满足条件的 n 个互质随机数
    """
    while True:
        numbers = generate_primes(n, S)
        if check_conditions(numbers, t, S):
            return numbers

def generate_shares(s, k, n):
    """
    Implements the Asmuth and Bloom's CRT-based secret sharing algorithm.
    """
    primes = find_numbers(n,k,s)
    shares = [s % mi for mi in primes]
    
    return shares, primes

def select_random_k_elements(shares_zip, k):
    random_selection = random.sample(shares_zip, k)
    selected_shares, selected_moduli = zip(*random_selection)
    return list(selected_shares), list(selected_moduli)


# Example usage:
secret = 1145141919  # The secret to be shared
k = 3                # Minimum number of shares needed to reconstruct the secret
n = 5                # Total number of shares to be distributed

# Generate the shares
shares, moduli = generate_shares(secret, k, n)
shares_zip = list(zip(shares, moduli))
print("Shares:", shares_zip)

# Reconstruct the secret
shares_pool, moduli_pool = select_random_k_elements(shares_zip, k)
res = solve_crt(shares_pool,moduli_pool)
print("Secret:", res)

Brickell Secret Sharing

The Brickell Secret Sharing Scheme is based on multi-dimensional vectors, allowing for the specification of designated groups for secret recovery.

Steps:

Sharing Generation:

  1. Assuming the secret = $S$, $n$ = 4, the vector dimension is $d$ = 3.
  2. Define the reconstruct rules ${(v1,v2,v3),(v1,v5)}$, means that person(1~3) and person(1 and 5) can recover the secret.
  3. Generate v1 to v5, ensuring that any group of vectors can linearly construct $(1,0,0)$
  4. Generate d-1 random numbers ${a_1,a_2…,a_{d-1}}$. In here, generate $a_1 = S, a_2 = 55$, $a_3 = 28$
  5. Compute the sharing, $S_i = a * v_i$, and the sharing is $(S_i, i)$

Secret Reconstruction

  1. Collect the sharing, ensuring that the sharing groups follow the rules ${(v1,v2,v3),(v1,v5)}$, assuming the $S_1 = 55, S_2 = 10, S_3 = 17$
  2. use the sharing group to linearly construct $(1,0,0)$, $c_1v_1+c_2v_2+c_3v_3 = (1,0,0)$, get the coefficients $c_1=-1, c_2=1, c_3=1$
  3. Recover the $S$, $S = c_1S_1+c_2S_2+c_3S_3$

总结

Secret sharing schemes are widely used in privacy computing. Here is a summary of their advantages and disadvantages.

Advantages

  1. It allows for the addition of new shareholders without changing the existing shareholders’ secret shares, demonstrating excellent scalability.
  2. Based on the original shared secret key, the secret shares can be invalidated by altering other terms without changing the constant term.

Disadvantages

  1. It relies on the credibility of the secret distributor. If the distributor is dishonest and distributes a fake share to a participant, it can cause confusion during the sharing process.
  2. Some participants may submit invalid secret shares, preventing the correct secret from being recovered. A secure point-to-point channel needs to be established between the secret distributor and the participants.