Secret Sharing by Example

1. The Scenario

You are haphazardly appointed as the group in charge of authorizing the launch of your country’s nuclear weapons. No idea how you got appointed, maybe you were just unlucky 🤷‍♂️.

Knowing that you are tasked with managing the launch code, you’ve decided that the only way to ensure no one abuses this code is to share the code in such a way that you and your friends must come together to reveal the secret code.

xkcd's what-if 47

2. A Failed Attempt

Let's suppose our hypothetical launch code is \( 857392 \) for simplicity's sake.

You might want to give each of your five friends each a concatenated digit and number.

• You get \( 81 \)
• Albert gets \( 52 \)
• Bernard gets \( 73 \)
• Cheryl gets \( 34 \)
• Denise gets \( 95 \)
• Edward gets \( 26 \)

To recover the secret, you’ll need to spell out the launch code in order of increasing numbers. Simple enough.

There's a catch, Bernard isn't too careful and ends up having his secret share (\( 73 \)) stolen. The thief is now in the fortunate position of having to guess fewer numbers in order to brute force the secret code. If it takes \( 10^6 \) tries to brute force a six-digit number, it'll take \( \frac{1}{10} \) the number of tries, hence \( 10^5 \), to brute force a five-digit number. This is not ideal.

3. A Somewhat Successful Attempt

Let’s do something different to mitigate the risk of having an exposed secret share.

You’ll give each of your friends a random six-digit number.

• Albert gets \( 397467 \)
• Bernard gets \( 645723 \)
• Cheryl gets \( 593239 \)
• Denise gets \( 305724 \)
• Edward gets \( 789942 \)

By adding each number to the original secret code, and using modulus 10 in case of a “carry over”, we can generate a random secret.

\[ \begin{array}{c c c c} &8&5&7&3&9&2&\text{Original Secret}\\ &3&9&7&4&6&7&\text{Albert's Secret}\\ &6&4&5&7&2&3&\text{Bernard's Secret}\\ &5&9&3&2&3&9&\text{Cheryl's Secret}\\ &3&0&5&7&2&4&\text{Denise's Secret}\\ +&7&8&9&9&4&2&\text{Edward's Secret}\\ \hline &2&5&6&2&6&7&\text{Random Secret}\\ \end{array} \]

You'll then keep the random secret \( 256267 \) to yourself.

To recover the secret you’ll need to perform the “reverse” of what you did to generate the random secret.

Note that we can subtract your friend’s secrets from the random secret in any order due to addition’s commutative properties.

\[ \begin{array}{c c c c} &2&5&6&2&6&7&\text{Random Secret}\\ -&3&9&7&4&6&7&\text{Albert's Secret}\\ -&6&4&5&7&2&3&\text{Bernard's Secret}\\ -&5&9&3&2&3&9&\text{Cheryl's Secret}\\ -&3&0&5&7&2&4&\text{Denise's Secret}\\ -&7&8&9&9&4&2&\text{Edward's Secret}\\ \hline &8&5&7&3&9&2&\text{Original Secret}\\ \end{array} \]

When we compare this method (known as a one-time pad or OTP) of generating secret shares to our first attempt. We can see that in the case that a secret share is exposed, an attacker is still required to brute force all \( 10^6 \) combinations since a random secret share doesn't narrow down the brute force search area in any meaningful way.

However, there’s another catch. Edward is also not very careful about his secret share and ends up losing it! Without Edward’s secret share, recovering the secret code is just as hard as brute-forcing it. Somehow, this doesn’t seem ideal.

4. A Clever Geometric Example

Now let’s address the problems with our previous methods. Rather than representing shares as single numbers, let’s represent shares as points on a graph.

For simplicity, let's assume that the secret is \( 4 \).

The 2 Shares Case

Let's find an arbitrary line that results in a y-intercept of \( 4 \).

\[ y = -x+4 \]

Taking any two points where \( x \neq 0 \), gives us the ability to recover the line hence finding the y-intercept.

We could for example create shares in the following configuration:

• You get \( (1, 3) \)
• Albert gets \( (2, 2) \)
• Bernard gets \( (3, 1) \)
• Cheryl gets \( (4, 0) \)
• Denise gets \( (5, -1) \)
• Edward gets \( (6, -2) \)

You will note that this type of secret sharing scheme has two significant advantages over our previous methods.

• Knowing a share doesn’t improve your chances of knowing the original secret (the y-intercept can still be any arbitrary number).
• Shares can be lost and the original secret can still be recovered.

However, you'll note that allowing two shares to recover the original secret might not be considered secure. Remember, Bernard's share was leaked to the public and Edward's share was lost. If someone happened to find Edward's share, they could recover the original secret. We'll need to think of a way to secure the original secret through \( +3 \) shares.

The 3 Shares Case

Instead of using a line, what if we use a quadratic?

Let’s consider the following quadratic function:

\[ y = x^2-4x+4 \]

We could for example create shares in the following configuration:

• You get \( (1, 1) \)
• Albert gets \( (2, 0) \)
• Bernard gets \( (3, 1) \)
• Cheryl gets \( (4, 4) \)
• Denise gets \( (5, 9) \)
• Edward gets \( (6, 16) \)

Using any three shares, the y-intercept of the quadratic can be recovered.

5. Introducing Shamir’s Secret Sharing

The beauty of this secret sharing scheme is that you can extend the cases by introducing higher and higher order polynomials.

The 2 shares case is known as a \( (2, n) \) scheme and the 3 shares case is known as a \( (3, n) \) scheme.

6. A Full Shamir’s Secret Sharing Implementation in JavaScript

We’ve talked about how previous secret sharing schemes have specific disadvantages, and we’ve also talked about the basis of how Shamir’s Secret Sharing works. But what does an actual implementation of Shamir’s Secret Sharing look like?

Note that actual implementation of Shamir’s Secret Sharing use polynomials over a finite field and are not representable on a 2D plane. For the mathematical formulation of scheme, here is a good overview.

The following code is ported from Wikipedia’s Shamir’s Secret Sharing Python Implementation.

Note that this implementation is not to be used in production! I am not responsible for any liabilities caused by following 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
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

/**
 * The following JavaScript implementation of Shamir's Secret Sharing is
 * released into the Public Domain under the terms of CC0 and OWFa:
 * https://creativecommons.org/publicdomain/zero/1.0/
 * http://www.openwebfoundation.org/legal/the-owf-1-0-agreements/owfa-1-0
 */

/**
 * The 12th Mersenne prime.
 * This is comparable to a security level of 128-bits.
 */
const PRIME = 2n ** 127n - 1n;

/**
 * Generates BigInts between low (inclusive) and high (exclusive)
 * https://devimalplanet.com/how-to-generate-random-number-in-range-javascript
 */
const generateRandomBigInt = (lowBigInt, highBigInt) => {
    if (lowBigInt >= highBigInt) {
        throw "lowBigInt must be smaller than highBigInt.";
    }

    const difference = highBigInt - lowBigInt;
    const differenceLength = difference.toString().length;
    let multiplier = "";
    while (multiplier.length < differenceLength) {
        multiplier += Math.random()
            .toString()
            .split(".")[1];
    }
    multiplier = multiplier.slice(0, differenceLength);
    const divisor = "1" + "0".repeat(differenceLength);

    const randomDifference = (difference * BigInt(multiplier)) / BigInt(divisor);

    return lowBigInt + randomDifference;
};

/**
 * BigInt floor divide
 * Note: This is needed because BigInt divides are truncated instead of floored.
 */
const bigIntfloorDivide = (a, b) => {
    if (b === 0n) {
        throw "Divide by zero.";
    }
    if (a === 0n) {
        return 0n;
    }

    if ((a > 0n && b > 0n) || (a < 0n && b < 0n)) {
        return a / b;
    }

    const quotient = a / b;
    const remainder = a % b;

    if (remainder === 0n) {
        return quotient;
    }

    return quotient - 1n;
};

/**
 * Evaluates polynomial (coefficient tuple) at x, used to generate a
 * shamir pool in makeRandomShares below.
 */
const evalAt = (poly, x, prime) => {
    let accum = 0n;

    for (let i = poly.length - 1; i >= 0; i--) {
        accum *= x;
        accum += poly[i];
        accum %= prime;
    }

    return accum;
};

/**
 * Generates a random shamir pool for a given secret, returns share points.
 */
const makeRandomShares = (secret, minimum, shares, prime = PRIME) => {
    if (minimum > shares) {
        throw "Pool secret would be irrecoverable.";
    }

    const poly = [BigInt(secret)].concat(
        [...Array(minimum - 1).keys()].map(
            _ => generateRandomBigInt(0n, PRIME - 1n)
        )
    );

    return [...Array(shares).keys()].map(
        i => [BigInt(i + 1), evalAt(poly, BigInt(i + 1), prime)]
    );
};

/**
 * Division in integers modulus p means finding the inverse of the
 * denominator modulo p and then multiplying the numerator by this
 * inverse (Note: inverse of A is B such that A*B % p == 1) this can
 * be computed via extended Euclidean algorithm
 * http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation
 */
const extendedGCD = (a, b) => {
    let x = 0n;
    let lastX = 1n;
    let y = 1n;
    let lastY = 0n;

    while (b !== 0n) {
        const quot = bigIntfloorDivide(a, b);
        [a, b] = [b, (a + b) % b];
        [x, lastX] = [lastX - quot * x, x];
        [y, lastY] = [lastY - quot * y, y];
    }

    return [lastX, lastY];
};

/**
 * Compute num / den modulo prime p
 * To explain what this means, the return value will be such that
 * the following is true: den * divMod(num, den, p) % p == num
 */
const divMod = (num, den, p) => {
    const inv = extendedGCD(den, p)[0];
    return num * inv;
};

/**
 * Find the y-value for the given x, given n (x, y) points;
 * k points will define a polynomial of up to kth order.
 */
const lagrangeInterpolate = (x, xs, ys, p) => {
    const k = xs.length;

    const PI = vals => {
        let accum = 1n;
        for (const val of vals) {
            accum *= val;
        }
        return accum;
    };

    const nums = [];
    const dens = [];
    for (let i = 0; i < k; i++) {
        const others = xs.slice();
        const cur = BigInt(others.splice(i, 1));
        nums.push(PI(others.map(o => x - o)));
        dens.push(PI(others.map(o => cur - o)));
    }

    const den = PI(dens);
    const num = [...Array(k).keys()]
        .map(i => divMod(nums[i] * den * ys[i] % p, dens[i], p))
        .reduce((total, el) => total + el, 0n);

    let secret = divMod(num, den, p);
    if (secret > 0n) {
        return secret % p;
    }

    // Sometimes the secret is a huge negative number.
    // We need to multiples of p to ensure that our result is
    // positive when we take modulus p.
    return (secret + ((-1n * secret / p + 1n) * p)) % p;
};

/**
 * Recover the secret from share points
 * (x, y points on the polynomial).
 */
const recoverSecret = (shares, prime = PRIME) => {
    if (shares.length < 2) {
        throw "Need at least 2 shares";
    }

    const xs = [];
    const ys = [];
    for (const share of shares) {
        xs.push(share[0]);
        ys.push(share[1]);
    }

    return lagrangeInterpolate(0n, xs, ys, prime);
};

/**
 * Generate shares.
 */
const secret = 857392;
const shares = makeRandomShares(secret, 4, 6);
console.log("Shares:");
console.log(shares);

/**
 * Recover the secret with the first two shares missing.
 */
shares.splice(0, 2);
console.log("Recovered Secret:");
console.log(recoverSecret(shares));

7. Now What?

Whew! We are done! 🎉

I hope this gave you a somewhat brief introduction to the world of secret sharing schemes.

We haven’t covered all the secret sharing schemes out there! However, Shamir’s is widely considered one of the best secret sharing schemes. Here are a few alternative secret sharing schemes:

• Blakley’s Secret Sharing (arxiv.org)
• Secret sharing using the Chinese remainder theorem (wikipedia.org)

With the rise of the Internet, secret sharing schemes are becoming increasingly prevalent and are used in all sorts of applications such as blockchain and cloud computing.

If you find any issues with this article, please let me know at [email protected].

8. Credits

This article is made possible by the following great resources and JS libraries:

• Art of the Problem’s Secret Sharing Explained Visually
• Wikipedia’s Shamir’s Secret Sharing article
• MathJax for math notation
• Mauricio Poppe’s Function Plot for graph plots