Secret sharing consists of recovering a secret from a set of shares, each containing partial information about the secret. The Chinese remainder theorem (CRT) states that for a given system of simultaneous congruence equations, the solution is unique in some, with under some appropriate conditions on the congruences. Secret sharing can thus use the CRT to produce the shares presented in the congruence equations and the secret could be recovered by solving the system of congruences to get the unique solution, which will be the secret to recover.
See main article: Secret sharing. There are several types of secret sharing schemes. The most basic types are the so-called threshold schemes, where only the cardinality of the set of shares matters. In other words, given a secret, and shares, any set of shares is a set with the smallest cardinality from which the secret can be recovered, in the sense that any set of shares is not enough to give . This is known as a threshold access structure. We call such schemes threshold secret sharing schemes, or -out-of- scheme.
Threshold secret sharing schemes differ from one another by the method of generating the shares, starting from a certain secret. The first ones are Shamir's threshold secret sharing scheme, which is based on polynomial interpolation in order to find from a given set of shares, and George Blakley's geometric secret sharing scheme, which uses geometric methods to recover the secret . Threshold secret sharing schemes based on the CRT are due to Mignotte and Asmuth–Bloom, they use special sequences of integers along with the CRT.
Let
k\geqslant2,m1,...,mk\geqslant2
b1,...,bk\inZ
\begin{cases} x\equiv&b1 \bmod m1\\ &\vdots\\ x\equiv&bk \bmod mk\\ \end{cases}
has solutions in if and only if
bi\equivbj\bmod(mi,mj)
1\leqslanti,j\leqslantk
(mi,mj)
n=[m1,...,mk]
m1,...,mk
Since the Chinese remainder theorem provides us with a method to uniquely determine a number S modulo k-many relatively prime integers
m1,m2,...,mk
Ultimately, we choose relatively prime integers
m1<m2<...<mn
s1,s2,...,sn
si=S\bmod mi
i=1,2,...,n
This condition on can also be regarded as
n | |
\prod | |
i=n-k+2 |
mi<S<
k | |
\prod | |
i=1 |
mi.
Since is smaller than the smallest product of of the integers, it will be smaller than the product of any of them. Also, being greater than the product of the greatest integers, it will be greater than the product of any of them.
There are two secret sharing schemes that utilize essentially this idea, the Mignotte and Asmuth–Bloom schemes, which are explained below.
As said before, the Mignotte threshold secret sharing scheme uses, along with the CRT, special sequences of integers called the -Mignotte sequences which consist of integers, pairwise coprime, such that the product of the smallest of them is greater than the product of the biggest ones. This condition is crucial because the scheme is built on choosing the secret as an integer between the two products, and this condition ensures that at least shares are needed to fully recover the secret, no matter how they are chosen.
Formally, let be integers. A -Mignotte sequence is a strictly increasing sequence of positive integers
m1< … <mn
(mi,mj)=1
mn-k+2 … mn<m1 … mk
\alpha=mn-k+2 … mn
\beta=m1 … mk
\alpha
\beta
\alpha<S<\beta
s | |
i1 |
,\ldots,
s | |
ik |
\begin{cases} x\equiv&
s | |
i1 |
\bmod
m | |
i1 |
\\ &\vdots\\ x\equiv&
s | |
ik |
\bmod
m | |
ik |
\\ \end{cases}
By the Chinese remainder theorem, since
m | |
i1 |
,\ldots,
m | |
ik |
m | |
i1 |
…
m | |
ik |
This scheme also uses special sequences of integers. Let be integers. We consider a sequence of pairwise coprime positive integers
m0<...<mn
m0 ⋅ mn-k+2 … mn<m1 … mk
We then pick a random integer such that
S+\alpha ⋅ m0<m1 … mk
S+\alpha ⋅ m0
Ii=(si,mi)
I | |
i1 |
,...,I | |
ik |
\begin{cases} x\equiv&
s | |
i1 |
\bmod
m | |
i1 |
\\ &\vdots\\ x\equiv&
s | |
ik |
\bmod
m | |
ik |
\\ \end{cases}
By the Chinese remainder theorem, since
m | |
i1 |
,...,
m | |
ik |
m | |
i1 |
…
m | |
ik |
It is important to notice that the Mignotte -threshold secret-sharing scheme is not perfect in the sense that a set of less than shares contains some information about the secret. The Asmuth–Bloom scheme is perfect: is independent of the secret and
n | |
\left.\begin{array}{r} \prod | |
i=n-k+2 |
m | |||||||||||||
|
Therefore can be any integer modulo
n | |
\prod | |
i=n-k+2 |
mi.
This product of moduli is the largest of any of the choose possible products, therefore any subset of equivalences can be any integer modulo its product, and no information from is leaked.
The following is an example on the Asmuth–Bloom scheme. For practical purposes we choose small values for all parameters. We choose and . Our pairwise coprime integers being
m0=3,m1=11,m2=13,m3=17
m4=19
3 ⋅ 17 ⋅ 19<11 ⋅ 13 ⋅ 17
Say our secret is 2. Pick
\alpha=51
2+51 ⋅ 3=155
\begin{cases} x\equiv&1 \bmod 11\\ x\equiv&12 \bmod 13\\ x\equiv&2 \bmod 17\\ \end{cases}
To solve the system, let
M=11 ⋅ 13 ⋅ 17
x0=1 ⋅ e1+12 ⋅ e2+2 ⋅ e3
By Bézout's identity, since
(mi,M/mi)=1
ri.mi+si.M/mi=1
ei=si ⋅ M/mi
From the identities
1=1 ⋅ 221-20 ⋅ 11=(-5) ⋅ 187+72 ⋅ 13=5 ⋅ 143+(-42) ⋅ 17
e1=221,e2=-935,e3=715
11 ⋅ 13 ⋅ 17
S=155\equiv2\mod3