How to Share a Secret

In this crypto bite, we'll look at a classic: Shamir's Threshold Scheme, or How to Share a Secret. A \((t, n)\) threshold scheme is a construction which divides some secret \(k_0\) (typically a key), into a set of \(n\) shares \(\{k_1, k_2, \dots, k_n\}\), such that \(k_0\) can be reconstructed, if and only if at least \(t \le n\) shares of that set are provided. Furthermore, complete knowledge of strictly fewer than \(t\) shares reveals absolutely nothing about \(k_0\).[1]

Shamir's threshold scheme is very useful in real world applications, as we'll see below.

In the context of Secure Multiparty Computation (MPC), Shamir's threshold scheme can be used to trivially MPC-compute additions and (with a little bit of additional efforts) multiplications.

The Problem

Suppose that an entity has a very important secret \(k_0\) to protect. It could be the master key that starts World War III (and no, it's a lot more complicated than CPE1704TKS). Perhaps it is the key that a central bank uses to create new digital currency out of thin air. Maybe it is the key used to sign data on the RFID chips of all passports within a country. Or, more down to earth, it could simply be the signing key of a major certificate authority (CA).

In any case, it is neither desirable nor acceptable, that this super important secret key gets compromized: a Global Thermonuclear War can hardly be undone, the central bank losing control of the major digital currency of a country would wreck the economy, passports can't easily be revoked and replaced en masse in a timely manner, and a CA losing control of its signing key is immediatly out of business. In other words, the cost of a compromized secret is prohibitively high.

So what will these entities do? Before Adi Shamir came up with his famous threshold scheme, they would give access to this key to a supremely trusted employee, typically at the very top of their management. Unfortunately, key holders are people too: they can die, quit the company, or be coerced to hand out their key(s). So \(k_0\) can get lost entirely, or some non-authorized bad guys may get access to it.

There must be a better solution. Do you remember those bank vaults where customers could deposit all kinds of things they deem valuable like jewelry, paperwork, etc? To open a compartment, a bank employee inserts her key in one slit. Then, the customer inserts his own key in the other slit. Only then will the compartment open, and the customer could access its contents. The very same principle has been used my missileers and submarine crews during the Cold War to activate ICBMs and SLBMs. The basic idea was to split the master key into few key shares and give each key holder one share. Only when all key holders cooperated in bringing their key shares to the table, could the master key be accessed.

Implementing this system was already possible before Shamir's scheme. In fact, there's a trivial solution to this: simply put as many locks on a system as you need shares. Only when all keys are available, can the system be unlocked / activated / whatever. Unfortunately, this simple scheme has one very serious problem: if only one key share gets lost, the main secret key is lost or at least remains unaccessible forever.

We clearly need a better solution.

Lagrange Interpolation to the Rescue

Shamir uses a basic mathematical property of polynomials to split a key into many shares.

Lets give ourselves a set of \(n+1\) distinct points \(\{(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\}\) with the additional property that all \(x_i\) are pairwise distinct, i.e. \(\forall i,j \colon x_i \ne x_j\).

Recall than any polynomial \(p(x) = \sum_{i=0}^n a_i x^i\) of degree \(n\) is completely defined given \(n+1\) distinct points on the polynomial's graph: \(\{ (x_0, p(x_0)), (x_1, p(x_1)), \dots, (x_n, p(x_n))\}\), where all \(x_i\) are pairwise distinct. Indeed, one and only one straight line goes though two distinct points, only one parabola goes through 3 distinct points, and so on... Exercise: prove this property in the general case.

Given any \(n+1\) distinct points (i.e. with distinct x-coordinates) \(\{(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\}\), we can thus reconstruct the polynomial \(p(x) = \sum_{i=0}^n a_i x^i\) of degree \(n\) whose graph contains all these points, i.e. for which the following propery holds:

\[ \forall i \in \{0, 1, \dots, n\} \colon p(x_i) = y_i \]

To get the coefficients \(\{a_0, a_1, \dots, a_n\}\), we make use of the Lagrange Interpolation Formula[3]:

\[ p(x) = \sum_{i=0}^n y_i \ell_i(x) \]

where \(\ell_i(x)\) is defined as the following product:

\[ \ell_i(x) = \prod_{\substack{0 \le j \le n \\ j \ne i}} \frac{x - x_j}{x_i - x_j} = \frac{x - x_0}{x_i - x_0} \cdots \frac{x - x_{i-1}}{x_i - x_{i-1}} \frac{x - x_{i+1}}{x_i - x_{i+1}} \cdots \frac{x - x_n}{x_i - x_n} \]

Either manually or with the help of a computer algebra system (CAS), we could easily compute the coefficients of \(p(x)\) from this long expression.

Shamir's (t, n) Threshold Scheme

What is a (t, n) threshold scheme?

We start with a definition[2, Definition 12.69, p525]:

Definition: A \((t, n)\) threshold scheme \((t \le n)\) is a method by which a trusted party computes \(n\) secret key shares \(k_i, 1 \le i \le n\) from an initial secret key \(k_0\), and securely distributes \(k_i\) to the party \(P_i\), such that the following is true:

  1. any \(t\) or more parties who pool their key shares may easily recover \(k_0\)
  2. any \(t-1\) or fewer parties who pool their key shares may not recover \(k_0\).

Shamir's idea

Shamir uses a random polynomial \(p(x)\) of degree \(t - 1\) and Lagrange interpolation to achieve this goal. Initially, only the trusted party which owns \(k_0\) randomly generates and knows (the coefficients of) this polynomial.

The idea consists of placing the secret key \(k_0\) on the polynomial at an \(x\) coordinate that is known by all parties. All the \(n\) key shares \(k_n\) will be placed on the polynomial at some other \(x\) coordinates in such a way, that party \(P_i\) knows "its" \(x\) coordinate. It doesn't hurt to use public \(x\) coordinates known by all parties. We stress again that the polynomial ifself remains unknown to the untrusted key holders at this point in time.

Because of the property that \(t\) points are enough to reconstruct any polynomial of degree \(t - 1\), all \(t\) colluding parties \(P_{m_1}, P_{m_2}, \dots, P_{m_t}\) need to do it to stuff their \(t\) \(x\) coordinates into the Lagrange interpolation formula to reconstruct \(\ell_{m_i}(x)\). With the help of their key shares \(k_{m_i} = p(k_{m_i}) = y_{m_i}\), they can then use the Lagrange interpolation formula to reconstruct the polynomial \(p(x)\). Finally, all they have to do is to evaluate that polynomial at the well-known \(x\) coordinate of the secret key to get \(k_0\).

Without loss of generality, Shamir put the secret key \(k_0\) at \(x\) coordinate zero, i.e:

\[ p(0) = a_0 = k_0 \]

and the remaining key shares at \(x\) coordinates \(1, 2, \dots, n\) respectively:

\[ \forall i \in \{1, 2, \dots, n\} \colon k_i = p(i) \]

The Algorithm

Let's now summarize Shamir's \((t, n)\) Threshold Scheme [2, Algorithm 12.71, p526]:

Algorithm: (Shamir's (t,n) threshold scheme)

  • Input: A trusted party T wants to share a secret \(k_0\) among \(n\) parties \(P_1, P_2, \dots, P_n\), such that any group of \(t \le n\) parties can pool their key shares to recover \(k_0\).
  • Distribution Phase, executed by the trusted party T:
    • Chose a prime \(p \gt \operatorname{max}(k_0, n)\) and define \(a_0 = k_0\).
    • Chose \(t - 1\) random, independent coefficients \(a_1, a_2, \dots, a_{t-1}\) each one uniformly sampled from the set \(\{0, \dots, p-1\}\), with \(a_{t-1} \ne 0\). The coefficients \(a_{t-1}, \dots, a_1, a_0\) define a random polynomial \(f\) of degree \(t - 1\) over \(\mathbb{Z}_p\): \(f(x) = \sum_{j=q}^{t-1} a_j x^j\). Note that all computations are performed modulo \(p\).
    • For each \(i \in \{1, 2, \dots, n\}\) compute: \(k_i = f(i) \pmod{p}\).
    • For each \(i \in \{1, 2, \dots, n\}\) securely transfer the share \(k_i\) to party \(P_i\).
  • Pooling of Shares, executed by a group of \(t\) or more parties:
    • All parties precompute the coefficients \(c_i = \prod_{\substack{1 \le j \le t \\ j \ne i}} \frac{-x_j}{x_i - x_j}\) for all \(i \in \{1, \dots, t\}\).
    • Each party \(P_i\) computes independently \(k_0 = \sum_{j=1}^t c_j k_i\) with its key share \(k_i\).

Properties of Shamir's (t, n) Threshold Scheme

The following list of properties is from [2]. Comments are mine.

  • perfect. Given knowledge of any \(t - 1\) or fewer shares, all values of \(k_0 \in \{0, 1, \dots, p-1\}\) remain equally probable. In other words, strictly less than \(t\) shares leak absolutely nothing about the shared secret \(k_0\). This is a very useful property to have, since up to \(t - 1\) parties can get compromized (e.g. people carrying those share being abducted), yet still, the secret \(k_0\) stays uncompromized.
  • ideal. The size of one share is the size of the secret. Or, in other words \(\forall i \in \{1, 2, \dots, n\} \colon |k_i| = |k_0|\). This is very useful, because an adversary can't distinguish between a secret \(k_0\) and a share \(k_i\) merely by looking at the key lengths. Exercise: can an adversary distinguish between \(k_0\) and \(k_i\) by other means? Hint: \(k_0\) is uniformly distributed, but are the shares also uniformly distributed?
  • extensible to new parties. New shares for new parties may be computed and distributed without affecting shares of existing parties. In other words, with fixed \(t\) and a random polynomial \(p(x)\) of degree \(t-1\), one can increase \(n\). This useful property of Lagrange interpolation can be applied in practice: new people join organizations all the time. If the number of already distributed shares is high, adding new parties fortunatly doesn't require updating the shares of exiting parties. Unfortunatly, individual shares can't be revoked, without revoking \(k_0\) as well. This is one drawback to keep in mind in the real world: as soon as \(t\) fired disgruntled empolyees pool their shares, they will reconstruct \(k_0\).
  • varying levels of control possible. Providing a single party with multiple shares bestows more control upon that party. Say, \(t = 6\) in the normal setup. But two users are particularly trusted to access \(k_0\) if they work together. This is an exception from the rule-of-six at that organization. Handing out three shares to each of those two users allow them to collectively provide the required minimum number of shares.
  • no unproven assumptions. The security of this scheme doesn't depend on unproven assumptions (e.g. about the difficulty of number-theoretic problems like factoring, discrete logarithm problems etc.). Exercise: does it mean that Shamir's Threshold Scheme is post-quantum secure?

Implementing Shamir's Threshold Scheme

Implementing Shamir's Threshold Scheme is straightforward. Use Horner's method to evaluate polynomials. The most important thing to remember is that all computations occur with modular arithmetic. In particular, to perform divisions \(\frac{a}{b} = a b^{-1}\), one needs to compute \(b\)'s modular inverse \(b^{-1}\). This can be done using the extended euclidean algorithm (EEA). See this from Introduction to Cryptography, Lecure 11 starting at 23:18, if you need a refresher (the part about modular inverting starts at 1:04:50):

The second point is that secrets \(k_0, k_1, \dots, k_n\) are usually big integers, e.g. 128 bits, 256 bits, so we can't use built-in data types like unsigned int on 64 bit machines. Sure, on some specific platforms like Intel and AMD, one can make use of larger registers like %xmm, i.e. SSE instructions to compute on such keys, but that is unportable. The classical way is to make use of a bignum multiprecision library like e.g. GNU's gmp[4]. One possible implementation with gmp is B. Poettering's ssss[5] (source code on github.com).

One big drawback of general bignum multiprecision libraries like gmp is that, due to their generality, they store numbers on the heap, and make use of handcrafted assembler code to speed up calculations. A modern C++ bignum library would rather delegate this task to the compiler, possibly even using template metaprogramming to precompute as much as possible already at compile time, dramatically reducing runtime overhead. One such modern library is ctbignum[6] by Niek J. Bouman, based on current research[7]. It is a cryptographic bignum library specialized for data sizes that are typical for keys (a few hundred bits). Much importantly, the authors are painstakingly making sure that computations run in constant time (using ct_verif[8], a verification tool), which is crucial in cryptography to thwart side-channel timing attacks.

Exercise: implement Shamir's threshold scheme in C++ using ctbignum.

The Bigger Picture

Shamir's threshold scheme as shown in this crypto bite is a very general and useful method of secret sharing. But we didn't introduce it here for its own sake, despite its beauty. Since we're in the Secure Multiparty Computation (MPC) mini-series, we're going to show in the next crypto bite how to leverage this scheme to compute arbitrary functions consisting of additions and multiplications (or, if you prefer, of circuits built out of adders and multipliers) the MPC way. We'll see that on one hand, computing additions in MPC using Shamir's threshold scheme is trivially easy. Multiplications, on the other hand, are somewhat more involved, but we'll see how to overcome that difficulty too.

While threshold schemes are useful in implementing MPC, they are not as general as we would like them to be. Research in MPC converged towards implementing MPC on general functions, or, general circuits. This is where Yao's garbled circuits, and Yao's protocol come into play. Essentially, they are a compiler that convert the circuit of a general function into a garbled circuit, where the internal wires are carrying encrypted 0s and 1s. Recent advances in Secure Multiparty Computation research have tremendously improved the efficiency of these generic methods, so that they are in fact even faster than the more specialized threshold methods. But they require the use of a very powerful and fundamental crypto primitive called oblivious transfer (OT).

Sources

Since this crypto bite is part of the mini-series inspired primarily by Tal Rabin's lecture at the Technion's 2014 Computer Engineering Summer School on Secure Party Computation, here's the part where Tal explained Shamir's Threshold Scheme (starting at 34:00 up to 40:00):

Fancying an alternative easy introduction? There we go:

Literature