Linear Secret-Sharing Schemes​
​by José Manuel Rodríguez Caballero
Abstract. We implement the Shamir's secret sharing scheme and its generalization, the Linear Secret Sharing Scheme (LSSS).
Update. November 25, 2020

Preliminaries

We will use the package about finite fields. The finite field having p elements will be denoted GF[p]. All the entries of the matrices will be in GF[p].
In[]:=
Needs["FiniteFields`"]

Shamir's Secret Sharing

Let p be a prime number, s be an element of the Galois field having p elements, and two integers k and n. SecretSharing[p, s, k, n] returns n pairs of elements of GF[p], which are the shares in a (k, n) Shamir's Secret Sharing scheme, where k is the minimum number of shares needed to recover the secret s.
In[]:=
SecretShare[p_Integer,s_,k_Integer,n_Integer]:=Block[{x},​​Function[P,{#,Function[t,If[t===0,GF[p][{0}],t]][P/.xGF[p][{#}]]}&/@Range[n]​​][s+Sum[GF[p][{RandomInteger[{0,p-1}]}]*x^i,{i,1,k-1}]]​​]
If L = SecretSharing[p, s, k, n], then SecretReconstruction[p, L] = s.
In[]:=
SecretReconstruction[p_Integer,L_List]:=Block[{x},​​InterpolatingPolynomial[L,x,Modulusp]/.xGF[p][{0}]​​]
ShamirCounterExample[p, L, k] generates the counterexamples of Shamir's scheme, where L = SecretSharing[p, s, k, n].
In[]:=
ShamirCounterExample[p_Integer,L_List,k_Integer]:=Function[s,​​Select[L[[#]]&/@Subsets[Range[Length[L]],{k}],Not[SecretReconstruction[p,#]===s]&]​​][SecretReconstruction[p,L]]
ShamirQ[p, L, k] returns True iff it is enough to have k shares to recover the same secret as L itself.
In[]:=
ShamirQ[p_Integer,L_List,k_Integer]:=ShamirCounterExample[p,L,k]=={}

Examples

Consider the prime modulus p = 19319 and the secret s = 11.
In[]:=
L=SecretShare[19319,GF[19319][{11}],3,5];​​L//TableForm
Out[]//TableForm=
1
{12758}
19319
2
{13673}
19319
3
{2756}
19319
4
{18645}
19319
5
{3383}
19319
We recover the secret using 3 shares.
In[]:=
SecretReconstruction[19319,L[[1;;3]]]
Out[]=
{11}
19319
We check that using 2 shares we do not recover the secret.
In[]:=
SecretReconstruction[19319,L[[1;;2]]]
Out[]=
{11843}
19319
We verify that L is a (3,5) Shamir's scheme.
In[]:=
ShamirQ[19319,L,3]
Out[]=
True
We verify that L is not a (2,5) Shamir's scheme.
In[]:=
ShamirQ[19319,L,2]
Out[]=
False
In[]:=
ClearAll[L]

Linear secret sharing scheme

We introduce Linear Secret Sharing Scheme (LSSS), which generalizes Shamir's scheme.
Vandermonde[p, k, L] generates the k-columns Vandermonde matrix associated to the list L.
In[]:=
Vandermonde[p_,k_,L_]:=Transpose[Table[GF[p][{#^i}]&/@L,{i,0,k-1}]]
Let w be a vector and v be a number. RandomVec[p, w, v] = a, for some random a satisfying w . a (inner product) = v.
In[]:=
RandomVec[p_,w_,v_]:=If[w=={},​​{},(*w=={}*)​​Function[{t,s},(*w==Insert[t,s,-1]*)​​If[t=={},​​{v*s^(-1)},(*t=={}*)​​Join[RandomVec[p,t,v-#*s],{#}]&[GF[p][{RandomInteger[{0,p-1}]}]](*t!={}*)​​]​​][Take[w,{1,-2}],Last[w]]​​]
Let n be the number of shares. Let k be the minimum number of shares needed to be together to know the secret. Let m be the number of parties. Let M be a n×k-matrix, w a k-dimensional vector, χ:Range[n] ⟶ Range[m] a map (represented as an array). For any number v, LSSS[M,w, v] is the result of the application of the (M, w) linear secret sharing scheme (LSSS) to v. We assume that First[w] is not divisible by p.
In[]:=
LSSS[p_,M_,w_,χ_,v_]:=Function[a,​​Function[s,​​{χ[[#]],s[[#]]}&/@Range[Length[s]]​​][M.a]​​][RandomVec[p,w,v]]
Reconstruction of the secret using LSSS. The list A is the set of parties combining their shares.
In[]:=
LSSSReconstruction[p_,M_,w_,χ_,L_,A_]:=Function[R,​​w.Inverse[M[[R]][[Range[Length[w]]]]].Last/@(L[[R]][[Range[Length[w]]]])​​][Select[Range[Length[χ]],MemberQ[A,χ[[#]]]&]]

Example 1: Shamir's secret sharing scheme as a particular case

We will use the Vandermonde matrix
In[]:=
M=Vandermonde[19319,3,Range[5]];​​M//MatrixForm
Out[]//MatrixForm=
{1}
19319
{1}
19319
{1}
19319
{1}
19319
{2}
19319
{4}
19319
{1}
19319
{3}
19319
{9}
19319
{1}
19319
{4}
19319
{16}
19319
{1}
19319
{5}
19319
{25}
19319
and the vector
In[]:=
w={GF[19319][{1}],GF[19319][{0}],GF[19319][{0}]};​​w//MatrixForm
Out[]//MatrixForm=
{1}
19319
{0}
19319
{0}
19319
in order to emulate the Shamir secret sharing scheme as a particular case of LSSS. We use the partition
In[]:=
χ=Range[5]
Out[]=
{1,2,3,4,5}
We Assigns the shares to the parties as a list of pairs, where the first component is the parties and the second component is the share assigned to this party.
We encode the secret 37 with respect to the prime 19319, using the setup (M, w, χ).
In[]:=
L=LSSS[19319,M,w,χ,GF[19319][{37}]];​​L//TableForm
Out[]//TableForm=
1
{15310}
19319
2
{174}
19319
3
{12586}
19319
4
{13908}
19319
5
{4140}
19319
We reconstruct the secret form the parties 1, 3 and 4.
In[]:=
SecretReconstruction[19319,L[[{1,3,4}]]]
Out[]=
{37}
19319
We check that L satisfies the (3, 5) Shamir secret sharing scheme.
In[]:=
ShamirQ[19319,L,3]
Out[]=
True
We check LSSSReconstruction.
In[]:=
LSSSReconstruction[19319,M,w,χ,L,Range[5]]//MatrixForm
Out[]//MatrixForm=
{37}
19319

Example 2: Additive secret sharing

For additive secret sharing we will use the identity matrix
the vector
and the partition
We encode the secret 88 with respect to the prime 19319, using the setup (M, w, χ).
We check that the sum of the shares is equal to the secret.
We check LSSSReconstruction.

Example 3: Replicated secret sharing

For (2,3)-additive secret sharing we will use the identity matrix
the vector
and the partition
We encode the secret 1729 with respect to the prime 19319, using the setup (M, w, χ).
We reconstruct the secret by adding two shares from one part and one share from another part.

References

[Beimel2011] Beimel, Amos. "Secret-sharing schemes: a survey." International Conference on Coding and Cryptology. Springer, Berlin, Heidelberg, 2011.
[Shamir1979] Shamir, Adi. "How to share a secret." Communications of the ACM 22.11 (1979): 612-613.