10 Secret sharing
In this section, we look at yet another cryptographic primitive, with a different functionality than encryption or signatures. We will learn about:
Secret sharing.
Polynomial interpolation and the Shamir secret sharing scheme.
Threshold decryption in the ElGamal encryption scheme.
10.1 Secret sharing
Sometimes, we want to ensure that some action requires more than one party to execute. One dramatic example, often depicted in popular media, is the two-man concept for the launch of nuclear weapons.40 The idea is that, to launch a nuclear missile, two operators must insert their respective keys in locks that are physically distant. This prevents a single operator from launching the missiles. The important observation here is that a single key is useless by itself, yet is it is absolutely necessary to proceed with the launch. In a sense, each of the keys is actually part of the key that controls the launch.
In this section, we will look at the cryptographic version of that. Let us assume that we want to make some information \(\mathsf{m}\) difficult to access unless \(n\) different parties collaborate, and let us denote the parties by the numbers \(1\) to \(n\). We call \(\mathsf{m}\) the secret. Each party \(i\) will hold some information \(s_i\) called a share. The shares work in a way such that, by themselves, they are useless. However, if the parties reveal the shares to each other, then anyone with all the shares will be able to recover the secret.
Moreover, we generalize this definition to admit situations in which not all shares are necessary to recover the secret. For example, we might want a situation in which we have \(5\) parties, and any \(3\) shares are enough to recover the secret, but any \(2\) shares reveal nothing about the secret. We will call this a \(3\)-out-of-\(5\) secret sharing scheme. We present a more formal definition below.
Definition 10.1 Let \(t,n\in\mathbb{N}\). Av\(t\)-out-of-\(n\) secret sharing scheme is a pair of algorithms \[(\mathsf{Share},\mathsf{Reconstruct}).\]
The \(\mathsf{Share}\) algorithm takes the secret \(\mathsf{m}\) and produces the set of shares \(\{s_1,\dots,s_n\}\). This algorithm might be randomized.
The \(\mathsf{Reconstruct}\) algorithm takes as input a subset of the shares, and outputs a message. For the scheme to work correctly, we want that \(\mathsf{Reconstruct}\) outputs \(\mathsf{m}\) whenever it is fed with a subset of \(\{s_1,\dots,s_n\}\) of size at least \(t\).
According to this definition, the example at the beginning of the section would be a \(2\)-out-of-\(2\) secret sharing scheme. In general, \(t\)-out-of-\(n\) secret sharing schemes are called threshold secret sharing schemes, since we need to reach a threshold \(t\) of shares for the secret to be recoverable. More complex access structures, like subsets of shares of variable sizes, are possible, but we will not cover these in the course.
Another aspect of secret sharing that we will not look at, but is worth mentioning, is the fact that whoever runs the \(\mathsf{Share}\) algorithm knows the secret and all the shares, so this requires, in principle, that every other party trusts a sole party to generate the shares.
Informally, we will say that a \(t\)-out-of-\(n\) secret sharing scheme is secure if any set of less than \(t\) shares reveals absolutely no information about the secret. Consider, for example, the following candidate for a \(2\)-out-of-\(2\) secret sharing scheme:
\(\mathsf{Share}\): given \(\mathsf{m}\in\{0,1\}^\lambda\), split \(\mathsf{m}\) in two halves and set each share as one of these halves.
\(\mathsf{Reconstruct}\): given two shares, concatenate them to recover the secret.
It is clear that this will not be secure, because knowing one share gives away half of the bits of the secret.
A \(2\)-out-of-\(2\) scheme that does work uses something that we used at the very beginning of the course: the one-time pad.
\(\mathsf{Share}\): given \(\mathsf{m}\in\{0,1\}^\lambda\), choose a uniformly random \(s_1\in\{0,1\}^\lambda\) and set \(s_2=s_1\oplus\mathsf{m}\).
\(\mathsf{Reconstruct}\): given two shares \(s_1\) and \(s_2\), output \(s_1\oplus s_2\).
Clearly, this works because \[s_1\oplus s_2 = s_1\oplus(s_1\oplus\mathsf{m})=\mathsf{m},\] since \(s_1\oplus s_1 = 0\). The security relies on the perfect secrecy of the one-time pad: given one of the shares without the other, the message could be anything in \(\{0,1\}^\lambda\).
10.2 The Shamir secret sharing scheme
We introduce a \(t\)-out-of-\(n\) secret sharing scheme due to Shamir, who you might remember as the S in the RSA cryptosystem.41 The scheme relies on the idea of polynomial interpolation, which is explained in Appendix C.
We know that a polynomial of degree \(t-1\) is uniquely determined by \(t\) pairs of point and image through the polynomial. Shamir’s idea is to encode the secret \(\mathsf{m}\) into the polynomial, and give one evaluation to each party, so that any \(t\) parties can put together their shares and recover the polynomial by interpolation. We describe the scheme more precisely below.
\(\mathsf{Share}\): on input a security parameter \(\lambda\), choose a prime number \(p\) of bitlength \(\lambda\). Choose uniformly random coefficients \(a_1,\dots,a_{t-1}\in\mathbb{Z}_p\), and define the following polynomial of degree \(t-1\): \[f(X)=\mathsf{m}+\sum_{i=1}^{t-1}a_iX^i.\] For \(i=1,\dots,n\), set the share corresponding to user \(i\) as \[s_i=(i,f(i)\bmod{p}).\]
\(\mathsf{Reconstruct}\): given \(t\) different shares, compute the Lagrange interpolation polynomial \(f(X)\) corresponding to them (with operations modulo \(p\)), and output \(f(0)\).
The scheme works because all the shares come from the same polynomial of degree \(t-1\), and thus all interpolations from \(t\) shares yield the same polynomial \(p(X)\), which is necessarily the one used to create the shares in the first place. Given that polynomial, it is clear that \(f(0)=\mathsf{m}\).
The security comes from the fact that any \(t-1\) shares reveal nothing about the evaluation at \(0\). To see this, assume that we have \(t-1\) shares \((x_i,y_i)\), for \(i=1,\dots,t-1\). Then, for any possible \(\mathsf{m}\), there is a unique polynomial \(f_\mathsf{m}(X)\) of degree \(t-1\) such that \[f_\mathsf{m}(0)=\mathsf{m},\qquad \text{and} \qquad f(x_i)=y_i \quad \text{ for all }i=1,\dots,t-1.\] That is, with only \(t-1\) shares, the secret \(\mathsf{m}\) could still be anything!
Proposition 10.1 The Shamir secret sharing scheme is a secure threshold secret sharing scheme.
We also note that an explicit formula for the secret \(\mathsf{m}=p(0)\) in terms of the interpolation points can be deduced directly from the interpolation polynomial formula. Indeed, since \[f(X)=\sum_{i=0}^ty_i\ell_i(X),\qquad \text{where} \qquad \ell_i(X)=\prod_{j\neq i}\frac{X-j}{i-j},\] we have that \[\mathsf{m}=f(0)=\sum_{i=0}^ty_i\prod_{j\neq i}\frac{-j}{i-j}.\] Thus, we actually do not need to interpolate the whole polynomial, as we only require the evaluation at \(0\).
10.3 Threshold decryption in the ElGamal encryption scheme
In a normal public-key encryption scheme, the secret key, which is used for decryption, is stored in a single place. This creates a single point of failure, as if this place becomes compromised, then the attacker will be able to decrypt any messages in the past encrypted with the corresponding public key.
One way to prevent this is to use secret sharing to split the secret key, and give the shares to different parties. A certain number of parties will be required to decrypt. This is known as threshold decryption. The crucial point is that they do not reconstruct the key, so no single party knows the whole key at any point in the process. Instead, the decryption is achieved by a combination of partial decryptions, in which each party uses their share to partially decrypt, and then these partial decryptions are combined to recover the original message.
Below, we show how to combine the ElGamal encryption scheme with the Shamir secret sharing scheme to achieve \(t\)-out-of-\(n\) threshold decryption.
\(\mathsf{KeyGen}\): first we run the usual ElGamal key generation. On input a security parameter \(\lambda\), choose a cyclic group \(\mathbb{G}\) of prime order \(p\), and a generator \(g\) of \(\mathbb{G}\). We will write \(\mathbb{G}\) with multiplicative notation. Sample a uniformly random \(x\in\mathbb{Z}_p\), and set \(h=g^x\). Set the public key \[\mathsf{pk}=(\mathbb{G}, g, h),\] and the secret key \[\mathsf{sk}=x.\] Then, we use Shamir secret sharing to split the secret key \(\mathsf{sk}\), producing \(n\) shares \(\mathsf{sk}_i=(i,y_i)\), for \(i=1,\dots,n\). Output \((\mathsf{pk},\mathsf{sk}_1,\dots,\mathsf{sk}_n)\).
\(\mathsf{Enc}\): given a message \(\mathsf{m}\in\mathbb{Z}_p\), with \(\mathsf{m}\) small, and the receiver’s public key \((\mathbb{G}, g, h)\), choose a uniformly random \(r\in\mathbb{Z}_p\) and output the ciphertext \[\mathsf{c}=(\mathsf{c}_1,\mathsf{c}_2)=(g^r,g^mh^r).\]
\(\mathsf{Dec}\): each party \(i\), given a ciphertext \(\mathsf{c}=(\mathsf{c}_1,\mathsf{c}_2)\) and their secret key share \(\mathsf{sk}_i=(i,y_i)\), computes the partial decryption \(\mathsf{c}_1^{y_i}\), and sends it to one agreed party that will take care of reconstructing the message. This designated party, once \(t\) partial decryptions have arrived, computes \[\alpha=\prod_{i=1}^t\left(\mathsf{c}_1^{y_i}\right)^{w_i},\qquad \text{where} \qquad w_i=\ell_i(0)=\prod_{j\neq i}\frac{-j}{i-j}.\] Finally, the message is recovered by computing \[\log_g\frac{\mathsf{c}_2}{\alpha}.\]
To see that this works, we just need to ensure that \(\alpha=\mathsf{c}_1^x\) since, if that is the case, then decryption is just as in the usual ElGamal encryption scheme. Equivalently, we need to prove that \[x=\sum_{i=1}^ty_iw_i.\] The expression on the right is exactly the one given at the end of Section 10.2, which tells us that indeed this formula recovers the secret \(x\).
Note that each party kept their share \(y_i\) during the process, never revealing it. The only information being sent is \(\mathsf{c}_1^{y_i}\), but we expect \(y_i\) to be hard to recover from here, due to the hardness of the discrete logarithm problem.
Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612-613.↩︎