Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
20 lines (10 sloc) 2.7 KB

Shamir’s Secret Sharing Scheme [SSSS]

Shamir’s Secret Sharing [1] is an algorithm used to divide a given master secret MS into n parts, such that m parts are required in order to compute the original master secret. If only m-1 parts are available, no information about the master secret is revealed. If the m-of-n threshold scheme is n = 2m-1 then we can still recover MS even if n/2 = m-1 of the n pieces are destroyed. However, an adversary cannot reconstruct MS even when he has compromised n/2 = m-1 parts.

SSSS is based on polynomial interpolation: given m points in the 2-dimensional plane (x_1, y_1) … (x_m, y_m) there is only one function q(x) of degree m-1 such that q(x_i) = y_i for all i. In order to protect against the attacker acquiring information about MS with every additional D_i, we use finite field arithmetic with a field of size p ∊ P: p > MS, p > n. Prime number p must be close enough to the desired security level, because a too large p leads to long cypher text, but a too small p leads to compromised security.

Preparation

After specifying MS, m and n, we generate m-1 random numbers a_1, … a_[m-1] and build a polynomial with the secret as a_0. The polynomial is thus q(x) = a_0 + a_1*x + a_2*x^2 + … + a_[m-1]*x^[m-1].

Then we construct n points D_[x-1] = (x, q(x) mod p) from the polynomial and each party gets a different point [both x and q(x)], the MS is q(0).

Reconstruction

To reconstruct MS, any m of n will be enough to compute the entire polynomial q(x) with the Lagrange interpolation formula [2].

Simulated shared ownership

SSSS can distribute the knowledge of a secret across several different sub-secret, where each of the holders has full knowledge of his individual part. However, the dealer first generates a master secret, which he has full knowledge off. Thus the dealer has full access and property rights in the funds locked up by the master secret. The sub-secret holders thus have a simulated shared ownership, however, they rely on the good will of the dealer to not spend the funds on his own accord. The use case for SSSS is thus more to backup a private key among semi-trusted peers, but where the dealer and owner of the bitcoin has always full control himself. This is a vitally important differentiation compared to some secure key and signature aggregation [3], which generates non-simulated shared ownership.


1. Adi Shamir. How to Share a Secret. Communications of the ACM, Volume 22, November 1979.
2. Hazewinkel, Michiel. Lagrange interpolation formula. Encyclopedia of Mathematics, Springer Science+Business Media B.V. 1994
3. Refer to chapter on Schnorr MuSig
You can’t perform that action at this time.