Shamir’s secret sharing scheme

The essential idea of Adi Shamir’s threshold scheme is that 2 points are sufficient to define a line, 3 points are sufficient to define a parabola, 4 points to define a cubic curve and so forth. That is, it takes \(k\) points to define a polynomial of degree \(k-1\).

Suppose we want to use a \(( k , n )\) , threshold scheme to share our secret \(S_{size}\), without loss of generality assumed to be an element in a finite field \(\mathbb{Z}_p\) of size \(P\) where

\[0 < k ≤ n < P; S < P; P \in \mathbb{P}\]

Choose at random \(k-1\) positive integers \(a_1,\cdots, a_{k-1}\) with\(a_i < P\), and let \(a_0=S\). Build the polynomial

\[f(x)=a_0+a_1x+a_2x^2+\cdots+a_{k-1}x^{k-1}\]

Let us construct any \(n\) points out of it, for instance set \(i=1,\cdots, n\) to retrive \((i, f(i))\).

Every participant is given a point (a non-zero integer input to the polynomial, and the corresponding integer output) along with the prime which defines the finite field to use. Given any subset of \(k\) of these pairs, we can find the coefficients of the polynomial using interpolation. The secret is the constant term \(a_0\)

SSSS

[1]:


from klefki.const import SECP256K1_P as P
from klefki.types.algebra.meta import field
from operator import add

import random

N = 0xFFFFF
random_f = lambda: CF(random.randint(1, N) % CF.P)


[2]:

from operator import mul

[3]:

from functools import reduce
from operator import add

(k, n) = (66, 99)
CF = field(P)
S = random_f()
P = CF.P

[4]:

assert 0 < k <= n < P

[5]:

a = [random_f() for _ in range(k-1)]

[6]:

f = lambda x: S + reduce(
    add, [CF(a[i]) * CF((x ** i)) for i in range(1, k - 1 )])

[7]:

rand = lambda: CF(random.randint(1, CF.P))

x = [CF(rand()) for _ in range(k)]
assert len(x) == k

[8]:

ret = lambda x: reduce(add, [f(x[j]) * reduce(mul,
    [x[m] / (x[m]-x[j])for m in range(k-1) if m != j]) for j in range(k-1)])

[9]:

ret([CF(rand()) for _ in range(k+20)]) == ret([CF(rand()) for _ in range(k)]) == S

[9]:

True
\[P = \sum_{j=0}^{k-1}f(x_j)\prod_{i=0;i\neq j}^{k-1}\frac{{x_i}}{{x_i}-{x_j}}\]

Feldman-VSS

In cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later reconstruct. (In standard secret sharing, the dealer is assumed to be honest.) The concept of verifiable secret sharing (VSS) was first introduced in 1985 by Benny Chor, Shafi Goldwasser, Silvio Micali and Baruch Awerbuch.

In a VSS protocol a distinguished player who wants to share the secret is referred to as the dealer. The protocol consists of two phases: a sharing phase and a reconstruction phase.

A commonly used example of a simple VSS scheme is the protocol by Paul Feldman, which is based on Shamir’s secret sharing scheme combined with any homomorphic encryption scheme. This scheme is, at best, secure for computationally bounded adversaries only.

First, a cyclic group \(G\) of prime order \(p\), along with a generator \(g\) of \(G\), is chosen publicly as a system parameter.

The group \(G\) must be chosen such that computing discrete logarithms is hard in this group.

[10]:

from klefki.types.algebra.concrete import FiniteFieldCyclicSecp256k1 as CF
from klefki.types.algebra.concrete import EllipticCurveCyclicSubgroupSecp256k1 as ECC

G = ECC.G

To make these shares verifiable, the dealer distributes commitments to the coefficients of \(P\).

If \(P(x) = s + a_1x + ... + a_tx^t\), then the commitments that must be given are:

\[\begin{split}c_0 = g^s\\ c_1 = g^{a_1}\\ \vdots\\ c_t=g^{a_t}\end{split}\]

Once these are given, any party can verify their share. For instance, to verify that \(v = P(i) \mod q\), party \(i\) can check that

\[{\displaystyle g^{v}=c_{0}c_{1}^{i}c_{2}^{i^{2}}\cdots c_{t}^{i^{t}}=\prod _{j=0}^{t}c_{j}^{i^{j}}=\prod _{j=0}^{t}g^{a_{j}i^{j}}=g^{\sum _{j=0}^{t}a_{j}i^{j}}=g^{P(i)}}.\]
[11]:

from klefki.crypto.ssss import SSSS
from klefki.types.algebra.utils import randfield
from klefki.types.algebra.meta import field
from klefki.numbers.primes import generate_prime
from functools import reduce
from operator import mul
import random


[12]:

k = 3
n = k * 3
secret = randfield(CF)
poly_params = [randfield(CF) for _ in range(k - 1)]
poly_proofs = [G**p for p in ([secret] + poly_params)]
s = SSSS(CF, secret, k, n, poly_params=poly_params)

[13]:

shares = [s.join() for _ in range(k)]

[14]:

def verify(x, y):
    return G ** y == reduce(mul, [poly_proofs[i] ** (x ** i) for i in range(k)])

[15]:

assert all([verify(*s) for s in shares])

Homomorphic property

  1. If we add/multiply a constant to all secret shares (y-values) then this constant will be add/multiplyied to the secret to get new secret

[16]:

from klefki.crypto.ssss import SSSS
from klefki.const import SECP256K1_P as P
from klefki.types.algebra.utils import randfield
from klefki.types.algebra.meta import field
import random


F = field(P)
k = random.randint(1, 100)
n = k * 3
secret = randfield(F)
s = SSSS(F, secret, k, n)

[17]:

shares = [s.join() for _ in range(k+1)]

[18]:

mul_s = [[s[0], s[1] * 3] for s in shares]

[19]:

assert SSSS.decrypt(mul_s) == secret * 3

[20]:

add_s = [[s[0], s[1] + 3] for s in shares]

[21]:

assert SSSS.decrypt(add_s) == secret + 3

  1. Suppose we have two secrets \(s\) and \(t\). Their corresponding shares are \(f(1),\cdots,f(n)\) for poly \(f(x)\) and \(g(1),\cdots,g(n)\) for poly g(x). Now we define \(j^{th}\) share as \(f(j)+g(i)\),\((j \in [1\cdots n])\). New secret will be \(s+t\) for the new function \(h(x)=f(x)+g(x)\) since \(h(0)=f(0)+g(0)\)

[22]:

F = field(P)

[23]:

x, y = randfield(F), randfield(F)

[24]:

ss_x = SSSS(F, x, k, n)
ss_y = SSSS(F, y, k, n)

[25]:

shares_x = [ss_x.join(i) for i in range(1, k+2)]
shares_y = [ss_y.join(i) for i in range(1, k+2)]

[26]:

comb_s = [[s[0][0], s[0][1] + s[1][1]] for s in zip(shares_x, shares_y)]

[27]:

assert SSSS.decrypt(comb_s) == x + y

Implementation

SSSS

[28]:

from klefki.crypto.ssss import SSSS
from klefki.const import SECP256K1_P as P
from klefki.types.algebra.utils import randfield
from klefki.types.algebra.meta import field
import random


[29]:

k = random.randint(1, 100)
n = k * 3
secret = randfield(F)
s = SSSS(field(P), secret, k, n)

assert s.decrypt([s.join() for _ in range(k - 1)]) != secret
assert s.decrypt([s.join() for _ in range(k+1)]) == secret
assert s.decrypt([s.join() for _ in range(k + 1)]) == secret

Feldman-VSS

[30]:

from klefki.crypto.vss import VSS


[31]:

G = ECC.G
k = random.randint(1, 100)
n = k * 3
secret = randfield(CF)
s = VSS(G, CF, secret, k, n)
assert s.decrypt([s.join() for _ in range(k - 1)]) != secret
assert s.decrypt([s.join() for _ in range(k+1)]) == secret
assert s.decrypt([s.join() for _ in range(k + 1)]) == secret


[32]:

assert s.verify(*s.join())