Secret sharing using the Chinese remainder theorem

Secret sharing consists of recovering a secret Template:Math 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 Template:Math, with Template:Math 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.

Secret sharing schemes: several types

Template:Main 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 Template:Math, and Template:Math shares, any set of Template:Math shares is a set with the smallest cardinality from which the secret can be recovered, in the sense that any set of Template:Math shares is not enough to give Template:Math. This is known as a threshold access structure. We call such schemes Template:Math threshold secret sharing schemes, or Template:Math-out-of-Template:Math 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 Template:Math from a given set of shares, and George Blakley's geometric secret sharing scheme, which uses geometric methods to recover the secret Template:Math. 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.

Chinese remainder theorem

Template:Main Let $k⩾2,m_1,...,m_k⩾2$, and $b_1,...,b_k\in 𝐙$. The system of congruences

$\{\begin{array}{cc}x\equiv & b_{1}mod{m}_1\\ & ⋮\\ x\equiv & b_{k}mod{m}_k\end{array}$

has solutions in Template:Math if and only if $b_i\equiv b_{j}mod(m_i,m_j)$ for all $1⩽i,j⩽k$, where $(m_i,m_j)$ denotes the greatest common divisor (GCD) of Template:Math and Template:Math. Furthermore, under these conditions, the system has a unique solution in Template:Math where $n=[m_1,...,m_k]$, which denotes the least common multiple (LCM) of $m_1,...,m_k$.

Secret sharing using the CRT

Since the Chinese remainder theorem provides us with a method to uniquely determine a number S modulo k-many relatively prime integers $m_1,m_2,...,m_k$, given that $S<{\prod }_{i=1}^k{m}_i$, then, the idea is to construct a scheme that will determine the secret Template:Math given any Template:Math shares (in this case, the remainder of Template:Math modulo each of the numbers Template:Math), but will not reveal the secret given less than Template:Math of such shares.

Ultimately, we choose Template:Math relatively prime integers $m_1<m_2<...<m_n$ such that Template:Math is smaller than the product of any choice of Template:Math of these integers, but at the same time is greater than any choice of Template:Math of them. Then the shares $s_1,s_2,...,s_n$ are defined by $s_i=Smod{m}_i$ for $i=1,2,...,n$. In this manner, thanks to the CRT, we can uniquely determine Template:Math from any set of Template:Math or more shares, but not from less than Template:Math. This provides the so-called threshold access structure.

This condition on Template:Math can also be regarded as

$\prod _{i=n-k+2}^n{m}_i<S<\prod _{i=1}^k{m}_i.$

Since Template:Math is smaller than the smallest product of Template:Math of the integers, it will be smaller than the product of any Template:Math of them. Also, being greater than the product of the greatest Template:Math integers, it will be greater than the product of any Template:Math of them.

There are two secret sharing schemes that utilize essentially this idea, the Mignotte and Asmuth–Bloom schemes, which are explained below.

Mignotte threshold secret sharing scheme

As said before, the Mignotte threshold secret sharing scheme uses, along with the CRT, special sequences of integers called the Template:Math-Mignotte sequences which consist of Template:Math integers, pairwise coprime, such that the product of the smallest Template:Math of them is greater than the product of the Template:Math 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 Template:Math shares are needed to fully recover the secret, no matter how they are chosen.

Formally, let Template:Math be integers. A Template:Math-Mignotte sequence is a strictly increasing sequence of positive integers $m_1<\cdots <m_n$, with $(m_i,m_j)=1$ for all Template:Math, such that $m_{n-k+2}\cdots m_n<m_1\cdots m_k$. Let $\alpha =m_{n-k+2}\cdots m_n$ and $\beta =m_1\cdots m_k$; we call the integers lying strictly between $\alpha$ and $\beta$ the authorized range. We build a Template:Math-threshold secret sharing scheme as follows: We choose the secret Template:Math as a random integer $\alpha <S<\beta$ in the authorized range. We compute, for every Template:Math, the reduction modulo Template:Math of Template:Math that we call Template:Math, these are the shares. Now, for any Template:Math different shares $s_{i_1},\dots ,s_{i_k}$, we consider the system of congruences:

$\{\begin{array}{cc}x\equiv & s_{i_1}mod{m}_{i_1}\\ & ⋮\\ x\equiv & s_{i_k}mod{m}_{i_k}\end{array}$

By the Chinese remainder theorem, since $m_{i_1},\dots ,m_{i_k}$ are pairwise coprime, the system has a unique solution modulo $m_{i_1}\cdots m_{i_k}$. By the construction of our shares, this solution is nothing but the secret Template:Math to recover.

Asmuth–Bloom threshold secret sharing scheme

This scheme also uses special sequences of integers. Let Template:Math be integers. We consider a sequence of pairwise coprime positive integers $m_0<...<m_n$ such that $m_0\cdot m_{n-k+2}\cdots m_n<m_1\cdots m_k$. For this given sequence, we choose the secret S as a random integer in the set Template:Math.

We then pick a random integer Template:Mvar such that $S+\alpha \cdot m_0<m_1\cdots m_k$. We compute the reduction modulo Template:Math of $S+\alpha \cdot m_0$, for all Template:Math, these are the shares $I_i=(s_i,m_i)$. Now, for any Template:Math different shares $I_{i_1},...,I_{i_k}$, we consider the system of congruences:

$\{\begin{array}{cc}x\equiv & s_{i_1}mod{m}_{i_1}\\ & ⋮\\ x\equiv & s_{i_k}mod{m}_{i_k}\end{array}$

By the Chinese remainder theorem, since $m_{i_1},...,m_{i_k}$ are pairwise coprime, the system has a unique solution Template:Math modulo $m_{i_1}\cdots m_{i_k}$. By the construction of our shares, the secret S is the reduction modulo Template:Math of Template:Math.

It is important to notice that the Mignotte Template:Math-threshold secret-sharing scheme is not perfect in the sense that a set of less than Template:Math shares contains some information about the secret. The Asmuth–Bloom scheme is perfect: Template:Mvar is independent of the secret Template:Mvar and

$\begin{array}{c}\prod _{i=n-k+2}^n{m}_i\\ \alpha \end{array}\}<\frac{\prod _{i=1}^k{m}_i}{m_0}$

Therefore Template:Mvar can be any integer modulo

$\prod _{i=n-k+2}^n{m}_i.$

This product of Template:Math moduli is the largest of any of the Template:Math choose Template:Math possible products, therefore any subset of Template:Math equivalences can be any integer modulo its product, and no information from Template:Mvar is leaked.

Example

The following is an example on the Asmuth–Bloom scheme. For practical purposes we choose small values for all parameters. We choose Template:Math and Template:Math. Our pairwise coprime integers being $m_0=3,m_1=11,m_2=13,m_3=17$ and $m_4=19$. They satisfy the Asmuth–Bloom required sequence because $3\cdot 17\cdot 19<11\cdot 13\cdot 17$.

Say our secret Template:Mvar is 2. Pick $\alpha =51$, satisfying the required condition for the Asmuth–Bloom scheme. Then $2+51\cdot 3=155$ and we compute the shares for each of the integers 11, 13, 17 and 19. They are respectively 1, 12, 2 and 3. We consider one possible set of 3 shares: among the 4 possible sets of 3 shares we take the set Template:Mset and show that it recovers the secret Template:Math. Consider the following system of congruences:

$\{\begin{array}{cc}x\equiv & 1mod11\\ x\equiv & 12mod13\\ x\equiv & 2mod17\end{array}$

To solve the system, let $M=11\cdot 13\cdot 17$. From a constructive algorithm for solving such a system, we know that a solution to the system is $x_0=1\cdot e_1+12\cdot e_2+2\cdot e_3$, where each Template:Math is found as follows:

By Bézout's identity, since $(m_i,M/m_i)=1$, there exist positive integers Template:Math and Template:Math, that can be found using the Extended Euclidean algorithm, such that $r_i.m_i+s_i.M/m_i=1$. Set $e_i=s_i\cdot M/m_i$.

From the identities $1=1\cdot 221-20\cdot 11=(-5)\cdot 187+72\cdot 13=5\cdot 143+(-42)\cdot 17$, we get that $e_1=221,e_2=-935,e_3=715$, and the unique solution modulo $11\cdot 13\cdot 17$ is 155. Finally, $S=155\equiv 2mod3$.

See also

• Secret sharing
• Shamir's secret sharing
• Chinese remainder theorem
• Access structure

References

• Oded Goldreich, Dana Ron and Madhu Sudan, Chinese Remaindering with Errors, IEEE Transactions on Information Theory, Vol. 46, No. 4, July 2000, pages 1330-1338.
• Mignotte M. (1983) How to Share a Secret. In: Beth T. (eds) Cryptography. EUROCRYPT 1982. Lecture Notes in Computer Science, vol 149. Springer, Berlin, Heidelberg.
• C.A. Asmuth and J. Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, IT-29(2):208-210, 1983.
• Sorin Iftene. General Secret Sharing Based on the Chinese Remainder Theorem with Applications in E-Voting. Electronic Notes in Theoretical Computer Science (ENTCS). Volume 186, (July 2007). Pages 67–84. Year of Publication: 2007. Template:ISSN.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Template:ISBN. Section 31.5: The Chinese remainder theorem, pages 873-876.
• Ronald Cramer. Basic Secret Sharing (Lectures 1-2), Class Notes. October 2008, version 1.1.

External links

• https://web.archive.org/web/20091209071915/http://www.cryptolounge.org/wiki/Ronald_Cramer