User:CryptoBm/crt

Secret sharing consists of recovering a secret S 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 $\mathbb {Z} /n\mathbb {Z}$, with $n>0$ under some appropriate conditions. 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

Main article: Secret sharing

There are several types of secret sharing schemes. The most basic types are called the threshold schemes, where only the cardinality of the set of shares matters. In other words, given a secret S, and n shares, any set of t shares is a set with the smallest cardinality from which the secret can be recovered, in the sense that any set of t-1 shares is not enough to give S. We call such schemes (t,n) threshold secret sharing schemes. Threshold secret sharing schemes differ from one another by the method of recovering the secret from the given set of shares. The first ones are Shamir's threshold secret sharing scheme, which is based on polynomial interpolation in order to find S from a given set of shares, and George Blakley's geometric secret sharing scheme, which uses geometric methods to recover the secret S. 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

Main article: Chinese Remainder Theorem

Let $k\geqslant 2$, $m_{1},...,m_{k}\geqslant 2$, and $b_{1},...,b_{k}\in \mathbb {Z}$. The system of equations

${\begin{cases}x\equiv &b_{1}\ mod\ m_{1}\\&.\\&.\\&.\\x\equiv &b_{k}\ mod\ m_{k}\\\end{cases}}$

has solutions in $\mathbb {Z}$ if and only if $b_{i}\equiv b_{j}mod(m_{i},m_{j})$ for all $1\leqslant i,j\leqslant k$, where $(m_{i},m_{j})$ denotes the greatest common divisor (GCD) of $m_{i}$ and $m_{j}$. Furthermore, under these conditions, the system has a unique solution in $\mathbb {Z} _{[m_{1},...,m_{k}]}$ where $[m_{1},...,m_{k}]$ 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 m modulo k many relatively prime integers $p_{1},p_{2},...,p_{k}$, given that $m<\prod _{i=1}^{k}p_{i}$, then, the idea is to construct a scheme that will determine the secret m given any k shares (in this case, the remainder of m modulo each of the primes), but will not reveal the secret given less than k of such shares. This is known as a threshold access structure.

Ultimately, we choose n relatively prime integers $p_{1}<p_{2}<...<p_{n}$ such that m is smaller than the product of any choice of k of these integers, but at the same time is greater than any choice of k-1 of them. Then the shares $s_{1},s_{2},...,s_{n}$ are defined by $s_{i}=m\ mod\ p_{i}$ for $i=1,2,...,n$. In this manner, thanks to the CRT, we can uniquely determine m from any set of k or more shares, but not from less than k.

This condition on m can also be regarded as $\prod _{i=n-k+2}^{n}p_{i}<m<\prod _{i=1}^{k}p_{i}$. Since it is smaller than the smallest product of k of the integers, it will be smaller than the product of k of them. Also, being greater than the product of the greatest k-1 integers, it will be greater than the product of any k-1 of them.

There are two Secret Sharing Schemes that utilize essentially this idea, Mignotte's and Asmuth-Bloom's Schemes, which are explained below.

Mignotte's Threshold Secret Sharing Scheme

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

Formally, let $n\geqslant 2$ be an integer, and k be an integer such that $2\leqslant k\leqslant n$. A (k,n)-Mignotte sequence is a sequence of positive integers $m_{1}<...<m_{n}$, with $(m_{i},m_{j})=1$ for all $1\leqslant i<j\leqslant n$, such that $m_{n-k+2}...m_{n}<m_{1}...m_{n}$. We call this range the authorized range. Now, the scheme works as follows: We intend a (k,n)-threshold secret sharing scheme. We choose the secret S as a random integer in the authorized range. We compute, for every $1\leqslant i\leqslant n$, the remainder of the Euclidean division of S by $m_{i}$ that we call $I_{i}=Smodm_{i}$, these are the shares. Now, for any k different shares $I_{i_{1}},...,I_{i_{k}}$, we consider the system of congruencies: ${\begin{cases}x\equiv &I_{i_{1}}\ mod\ m_{i_{1}}\\&.\\&.\\&.\\x\equiv &I_{i_{k}}\ mod\ m_{i_{k}}\\\end{cases}}$

By the Chinese remainder theorem, since $m_{i_{1}},...,m_{i_{k}}$ are pairwise coprime, then the system has a unique solution modulo $m_{i_{1}}...m_{i_{k}}$. By the construction of our shares, this solution is nothing but the secret S to recover.

Asmuth-Bloom's Threshold Secret Sharing Scheme

This scheme also uses special sequences of integers. Let $n\geqslant 2$ be an integer, and k be an integer such that $2\leqslant k\leqslant n$. We consider a sequence of pairwise coprime positive integers $m_{0}<...<m_{k}$ such that $m_{0}.m_{n-k+2}...m_{n}<m_{1}...m_{k}$. For this given sequence, we choose the secret S as a random integer in the set $\mathbb {Z} _{r}$. We then pick a random integer $\alpha$ such that $S+\alpha .m_{0}<m_{1}...m_{k}$. We compute the remainders of the Euclidean division of $S+\alpha .m_{0}$ by $m_{i}$, for all $1\leqslant i\leqslant n$, these are the shares $I_{i}$. Now, for any k different shares $I_{i_{1}},...,I_{i_{k}}$, we consider the system of congruences:

${\begin{cases}x\equiv &I_{i_{1}}\ mod\ m_{i_{1}}\\&.\\&.\\&.\\x\equiv &I_{i_{k}}\ mod\ m_{i_{k}}\\\end{cases}}$

By the Chinese Remainder Theorem, since $m_{i_{1}},...,m_{i_{k}}$ are pairwise coprime, then the system has a unique solution $S_{0}$ modulo $m_{i_{1}}...m_{i_{k}}$. By the construction of our shares, the secret S is the remainder of the Euclidean division of $S_{0}$ by $m_{0}$

It is important to notice that the Mignotte and Asmuth-Bloom (k,n)-threshold secret-sharing schemes are not perfect schemes, in the sense that a set of less than ‘‘k’’ shares contains some information about the secret. Nevertheless, by a suitable choice of the sequences and the parameters ($\alpha$ in the Asmuth-Bloom case), one can get a reasonable security factor. This is why the Asmuth-Bloom scheme is more secure, for it involves more random parameters.

Example

The following is an example on the Asmuth-Bloom's Scheme. For practical purposes we choose small values for all parameters. We choose k=3 and n=4. 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.17.19<11.13.17$. Say our secret S is 2. Pick $\alpha =51$, satisfying the required condition for the Asmuth-Bloom scheme. Now we compute the shares for each of the integers 11, 13, 17 and 19. They are respectively 1, 12, 2 and 3. We consider two possible sets of 3 shares, among the $4 \choose 3$ possible sets, and show that they recover the same secret S=2. Consider, for example, the following system of congruences:

${\begin{cases}x\equiv &1\ mod\ 11\\x\equiv &12\ mod\ 13\\x\equiv &2\ mod\ 17\\\end{cases}}$

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 $e_{i}$ is found as follows: By Bezout's theorem, since $(m_{i},M/m_{i})=1$, there exist positive integers $r_{i}$ and $s_{i}$, that can be found using the Euclidean algorithm, such that $r_{i}.m_{i}+s_{i}.M/m_{i}=1$. Set $e_{i}=s_{i}\cdot M_{i}/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-3\cdot 51=2$.