Adi Shamir’s Threshold Scheme

June 17, 2011

[ Today’s exercise was written by guest author Graham Enos, a PhD student in the Applied Mathematics program at UNC Charlotte, with solution in Python rather than Scheme. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested. ]

In his 1979 paper “How to Share A Secret,” Adi Shamir (the S in RSA) proposed a cryptographic scheme that allows n people to share a secret number S in such a way that it takes at least k of them pooling their resources to reconstruct S. This (k, n) threshold scheme uses modular arithmetic and polynomials to give each of the n participants ¹/_k of the needed information. For our discussion, we’ll use a mix of Shamir’s notation and that found in chapter 12 of the book Handbook of Applied Cryptography by Menezes, van Oorschot, and Vanstone.

In his paper, Shamir describes how this scheme can be used to allow groups of k people to retrieve the secret number S even if the other n−k pieces of information have been lost or destroyed. For another use case, suppose S is a 2048-bit private RSA key that’s been used to encrypt a message. Once k participants get together and pool their information, they can find S and decode the message. However, at least k of them must cooperate to retrieve S; no smaller number of participants will do. Note that S and n can be arbitrarily large integers with k ≤ n. For instance, S could be the ASCII value of some secret letter, or a word encoded by taking letters as digits in base 36. Now for the details.

Given a secret value S, the number of participants n, the threshold number k, and some prime number p > max(S, n), we first construct in secret a polynomial y = q(x) of degree k−1 (modulo our prime p) with constant term S by picking independent random integers between 1 and p−1, inclusive, for the coefficients. Next we choose n unique random integers x between 1 and p−1, inclusive, and evaluate the polynomial at those n points. Each of the n participants is given an (x, y) pair.

To reconstruct S from k pairs (x, y), we use Lagrange Interpolation. In general this technique can rebuild the entire polynomial y = q(x), but since S = q(0), we only need to find q(0):

$S = \sum_{i = 1}^k \left[ y_i \prod_{1 \le j \le k, j \ne i} x_j (x_j - x_i)^{-1} \right] \mod p$

Note: the exponent −1 signifies taking the multiplicative inverse mod p, that is, the integer z such that z · (x_j – x_i) ≡ 1 (mod p).

As an example, suppose p = 23, S = 17, and our polynomial y = q(x) is 17 + 4x + 13x². Since this polynomial has degree two, we need at least three points to reconstruct this polynomial. Suppose furthermore that to three of our n recipients we gave the points (14, 22), (2, 8), and (21, 5). Lagrange Interpolation could be used to recreate the whole polynomial, but we’re only interested in the constant term $S = \sum_{i = 1}^3 \left[ y_i \prod_{1 \le j \le k, j \ne i} x_j (x_j - x_i)^{-1} \right] \pmod{23}$ :

S = [22 · 2(2−14)⁻¹ · 21(21−14)⁻¹] + [8 · 14(14−2)⁻¹ · 21(21−2)⁻¹] + [5 · 14(14−21)⁻¹ · 2(2−21)⁻¹] (mod 23)

= [22 · 2 · 11⁻¹ · 21 · 7⁻¹] + [8 · 14 · 12⁻¹ · 21 · 19⁻¹] + [5 · 14 · 16⁻¹ · 21 · 4⁻¹] (mod 23)

= [22 · 2 · 21 · 21 · 10] + [8 · 14 · 2 · 23 · 17] + [5 · 14 · 13 · 21 · 6] (mod 23)

= 194040 + 87584 + 114660 (mod 23)

= 396284 (mod 23)

= 17

The beauty of this scheme is twofold. First, it is rather simple and elegant; the majority of the actual code used to implement the scheme takes less than 15 lines in Python. Second, it has information theoretic security. That is, the security of the scheme relies entirely upon the fact that at least k points are needed to reconstruct a degree k−1 polynomial; nothing less than k points will do. This means its security is based on something being impossible, as opposed to something being believed to be difficult, but not yet proven to be so (e.g. factoring the product of two large primes). This scheme also enjoys other useful properties; see the above references for more.

Your task is to write functions that perform both portions of Shamir’s (k, n) threshold scheme. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Posted by programmingpraxis

Filed in Exercises

6 Comments »

6 Responses to “Adi Shamir’s Threshold Scheme”

Graham said
June 18, 2011 at 7:22 PM
I also wrote a version in Common Lisp, since I’m trying to learn a new language. If there are any CL gurus in the audience, I’d appreciate any feedback!
Graham said
June 23, 2011 at 6:59 PM
For good measure, here it is in C and Haskell.

razvan said

July 5, 2011 at 5:18 PM

Here’s my solution in C:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#define max(m, n) ((m) > (n) ? (m) : (n))

typedef struct pair 
{
    int x;
    long y;
} pair;

long ipow(int x, int n)
{
    if(n == 0) return 1;
    if(n % 2 == 0) return ipow(x * x, n / 2);
    return x * ipow(x, n - 1);
}

void euclid(int a, int b, int *d, int *x, int *y)
{
    if (b == 0) 
    {
        *d = a;
        *x = 1;
        *y = 0;
    }
    else {
        int x0, y0;
        euclid(b, a % b, d, &x0, &y0);
        *x = y0;
        *y = x0 - (a / b) * y0;
    }
}


long eval(int* P, int x, int n)
{
    assert(P != NULL);
    assert(n >= 0);
    int res = 0;
    int i;
    for(i=0; i<=n; i++)
        res += P[i] * ipow(x, i);
    return res;
}

pair* encrypt(int S, int n, int k, int p)
{
    assert(k <= n);
    assert(p > max(S, n));
    int* P = malloc(k * sizeof(int));
    if(P == NULL)
        exit(1);
    int i;
    P[0] = S;
    for(i=1; i<=k-1; i++)
        P[i] = rand() % p;
    pair* out = malloc(n * sizeof(pair));
    if(out == NULL)
        exit(1);
    for(i=0; i<n; i++)
    {
        out[i].x = rand() % p;
        int unique = 0;
        while(!unique)
        {
            unique = 1;
            int j;
            for(j=0; j<i; j++)
                if(out[j].x == out[i].x)
                {
                    unique = 0;
                    out[i].x = rand() % p;
                    break;
                }
        }
        out[i].y = eval(P, out[i].x, k-1) % p;
    }
    return out;
}

int decrypt(pair* pairs, int k, int p)
{
    assert(p > k);
    assert(pairs != NULL);
    int S = 0;
    int i, j;
    for(i=0; i<k; i++)
    {
        int prod = pairs[i].y;
        for(j=0; j<k; j++)
        {
            if(j == i) continue;
            prod*= pairs[j].x;
            int d, x, y;
            euclid(p, (pairs[j].x - pairs[i].x + p) % p, &d, &x, &y);
            prod *= (y + p) % p;
            prod %= p;
        }
        S += prod;
    }
    S %= p;
    return S;
}

int main(int argc, char **argv)
{
    srand(time(NULL));
    int S = 17, n = 3, k = 2, p = 23;
    pair* pairs = encrypt(S, n, k, p);
    int i;
    for(i=0; i<n; i++)
        printf("(%d, %ld)\n", pairs[i].x, pairs[i].y);
    printf("\nS = %d", decrypt(pairs, n, p));
    free(pairs);
    return 0;
}

razvan said
July 5, 2011 at 5:25 PM
Err, that should rather be
```
printf("\nS = %d", decrypt(pairs, k + 1, p));
```
Graham Enos said
October 25, 2011 at 5:56 PM
I changed github accounts, so the gists I linked to above are dead (apologies). Here are new ones:
Common Lisp
Haskell
C, version 1
C, version 2 (improved with a little help from Razvan’s solution).
Sayantan Sur said
September 3, 2017 at 9:09 PM
= [22 · 2 · 11−1 · 21 · 7−1] + [8 · 14 · 12−1 · 21(mark) · 19−1] + [5 · 14 · 16−1 · 21 · 4−1] (mod 23)

= [22 · 2 · 21 · 21 · 10] + [8 · 14 · 2 · 23(mark) · 17] + [5 · 14 · 13 · 21 · 6] (mod 23)

these lines has been copied from the solution example given above.
see the mark written portion in both the lines. how did 21 got transformed to 23?
please explain

Programming Praxis