Subsection11.7.1Secret sharing
Suppose that three people work at a company with some trade secret, all of whom have clearance to know about the secret's details. However, the company wants to avoid one of the three being bought off by a competitor and revealing it in an act of corporate espionage.
The company needs to devise a system where, in order to actually gain access to the details of the trade secret, one needs two of the people involved. In a movie, you would have an impressive safe with three locks; each person would have a separate key to one of the locks, and the safe would be constructed so that any two of the keys would open it.
But real cryptography is not the movies! For one thing, the data is probably electronic, so it's really something we need to do digitally. Cryptography provides the perfect way to deal with these issues. What we will do is indeed give each person a key – a digital encryption key, of course. (The exposition is based on the one in the book I first learned it from, [C.1.4], which does this in full generality.)
Algorithm11.7.1Secret Sharing
Suppose the trade secret is digitally represented as a large number \(K\). Here are steps to create three different keys; access to any two of these will allow access to \(K\).
Choose some prime \(p>K\).
-
Choose three numbers \(m_1<m_2<m_3\) which are:
mutually coprime and coprime to \(p\), i.e. \(\gcd(m_i,m_j)=1\) and \(\gcd(m_i,p)=1\).
AND such that \begin{equation*}m_1 m_2>pm_3\end{equation*}
Let \(M=m_1 m_2\).
-
Now choose some \(t<M/p\) at random. Then the keys are as follows:
What good do these do us? Well, the Chinese Remainder Theorem allows us to reconstruct \(K_0\) modulo \(m_im_j\) with any two keys \(k_i\) and \(k_j\). That may not seem like a lot; that just gives us things to within multiples of \(m_im_j\).
But by our choice of \(M=m_1m_2>pm_3\), we know that \(M/p>m_3\) (and hence \(M/p>m_i\) as well). So \begin{equation*}K_0=K+tp<p+tp=(t+1)p\leq (M/p)p=M\end{equation*} And certainly if \(K_0<M\), then \(K_0<m_im_j\), since \(M\) is the smallest such product. So the Chinese Remainder Theorem allows us to reconstruct \(K_0\) uniquely, and then \(K=K_0-tp\)!
Finally, note that just one person doesn't have enough information to get \(K\), since that just tells that \begin{equation*}K_0\equiv k_i\text{ (mod }m_i)\; ,\end{equation*} so that \begin{equation*}K_0=k_i+\ell m_i\end{equation*} for all \(\ell\) modulo \(m_i\).
Obviously, we'll want to see this in action.
Example11.7.2
This is a slight modification of [C.1.4, Example 7.8]. Suppose your secret was \(K=4\). Let's pick \(p=7\), and numbers \(11,13,16\).
We'll check quickly that \(m_1m_2>pm_3\):
So \(M=11\cdot 13=143\), and we can pick \(t=15\) more or less randomly as being less than \(M/p=143/7=20\frac{3}{7}\).
So \(K_0=K+tp=4+15\cdot 7=109\):
This gives keys \(k_i\), which are \(K_0\) modulo \(m_i\):
Note that in our example, we can check all the conditions in the proof by hand, but with industrial-size numbers that would not be possible.
Now let's actually reconstruct the secret \(K\) in these cases. First, let's see that any two people do have enough information.
Great!
One might suspect that a lone person, without one of the other secret sharers, might be able to just ‘guess’ which of the various solutions was right in this very small example, but it's actually not clear which is the correct \(K_0\). If you get only one chance, you might not want to try to be lucky!
As a note, we should point out that this secret sharing method doesn't just protect against someone defecting. It also provides protection against one of the three becoming incapacitated somehow. If all three were necessary to unlock the secret, the company is an illness or death or resignation away from its secret being irretrievably lost without a system of this type.
Finally, it is not terribly hard to extend this to a system that works with spreading a secret known to \(n\) in such a way that \(k\) of the \(n\) sharers are needed to access the secret. (Again, see [C.1.4].)
