Section 11.7 Other applications
Subsection 11.7.1 Secret sharing
Suppose that a company with a particular trade secret has three employees with clearance to know details of this secret process. 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β3β.Algorithm 11.7.1. Secret Sharing.
Suppose the trade secret is digitally represented as a large number
Choose some prime
-
Choose three numbers
which are:mutually coprime and coprime to
i.e. and-
AND such that
Let
-
Now choose some
at random. Then the keys are as follows:-
We have a modified secret
-
Person
gets the key
-
Proof.
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\text{.}\) That may not seem like a lot; that just gives us things to within multiples of \(m_im_j\text{.}\)
But by our choice of \(M=m_1m_2>pm_3\text{,}\) we know that \(M/p>m_3\) (and hence \(M/p>m_i\) as well). So
And certainly if \(K_0<M\text{,}\) then \(K_0<m_im_j\text{,}\) 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\text{!}\)
Finally, note that just one person doesn't have enough information to get \(K\text{,}\) since that just tells that
so that
for all \(\ell\) modulo \(m_i\text{.}\)
Example 11.7.2.
Suppose your secret was
xxxxxxxxxx
K=5
p=13
m1,m2,m3=17,19,16
We'll check quickly that
xxxxxxxxxx
m1*m2>p*m3
So
xxxxxxxxxx
M=m1*m2
t=12
print(M)
print(M/p > t)
So
xxxxxxxxxx
K_0=K+t*p
print(K_0)
This gives keys
xxxxxxxxxx
k1,k2,k3 = mod(K_0,m1),mod(K_0,m2),mod(K_0,m3)
print(k1, k2, k3)
The three keys are now
Now let's actually reconstruct the secret
xxxxxxxxxx
# First line: turn modular integers back into integers
k1, k2, k3 = ZZ(k1), ZZ(k2), ZZ(k3)
print(CRT(k1,k2,m1,m2))
print(CRT(k1,k3,m1,m3))
print(CRT(k2,k3,m2,m3))
Now we subtract
xxxxxxxxxx
161-t*p
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.
xxxxxxxxxx
print([k1+i*m1 for i in [0..10]])
print([k2+i*m2 for i in [0..10]])
print([k3+i*m3 for i in [0..10]])
As you can see, without all the information it would not be so clear which is the correct