Secret sharing using the Chinese remainder theorem

Secret sharing consists of recovering a secret S from a set of shares, each containing partial information about the secret. The (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. 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.

1 Secret sharing schemes: several types
2 Chinese remainder theorem
3 Secret sharing using the CRT
4 Source
5 See Also on BitcoinWiki

Secret sharing schemes: several types

There are several types of schemes. The most basic types are the so-called schemes, where only the 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 from which the secret can be recovered, in the sense that any set of t-1 shares is not enough to give S. This is known as a . We call such schemes (t,n) schemes, or t-out-of-n scheme.

schemes differ from one another by the method of generating the shares, starting from a certain secret. The first ones are , which is based on in order to find S from a given set of shares, and ‘s geometric secret sharing scheme, which uses geometric methods to recover the secret S. 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

Let $k geqslant 2, m_1,...,m_k geqslant 2$ , and $b_1,...,b_k in mathbf{Z}$ . The system of congruences

begin{cases} x equiv & b_1 bmod m_1 & vdots x equiv & b_k bmod m_k end{cases}

has solutions in if and only if $b_i equiv b_j bmod (m_i,m_j)$ for all $1 leqslant i,j leqslant k$ , where $(m_i,m_j)$ denotes the (GCD) of and . Furthermore, under these conditions, the system has a unique solution in where $n = [m_1,...,m_k]$ , which denotes the (LCM) of $m_1,...,m_k$ .

Secret sharing using the CRT

Since the provides us with a method to uniquely determine a number S modulo k-many 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 S given any k shares (in this case, the remainder of S modulo each of the numbers ), but will not reveal the secret given less than k of such shares.

Ultimately, we choose n integers $m_1< m_2< ...< m_n$ such that S 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 = S bmod m_i$ for $i=1, 2, ..., n$ . In this manner, thanks to the CRT, we can uniquely determine S from any set of k or more shares, but not from less than k. This provides the so-called .

This condition on S can also be regarded as

prod_{i=n-k+2}^n m_i < S < prod_{i=1}^k m_i.

Since S is smaller than the smallest product of k of the integers, it will be smaller than the product of any k 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 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, Mignotte’s scheme uses, along with the CRT, special sequences of integers called the (k,n)-Mignotte sequences which consist of n integers, , such that the product of the smallest k 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 k shares are needed to fully recover the secret, no matter how they are chosen.

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

begin{cases} x equiv & s_{i_1} bmod m_{i_1} & vdots x equiv & s_{i_k} bmod m_{i_k} end{cases}

By the , since $m_{i_1}, ldots, m_{i_k}$ are , 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 S to recover.

Asmuth-Bloom’s threshold secret sharing scheme

This scheme also uses special sequences of integers. Let be integers. We consider a sequence of positive integers $m_0 < ... < m_n$ 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 .

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

$begin{cases} x equiv & s_{i_1} bmod m_{i_1} & vdots x equiv & s_{i_k} bmod m_{i_k} end{cases}$

By the , since $m_{i_1}, ... , m_{i_k}$ are , the system has a unique solution modulo $m_{i_1}...m_{i_k}$ . By the construction of our shares, the secret S is the reduction modulo of .

It is important to notice that the Mignotte (k,n)- scheme is not perfect in the sense that a set of less than k shares contains some information about the secret. The Asmuth-Bloom scheme is perfect: is independent of the secret and

$left.begin{array}{r} prod_{i=n-k+2}^n m_i alpha end{array}right}<frac{prod_{i=1}^k m_i}{m_0}$

Therefore can be any integer modulo

prod_{i=n-k+2}^n m_i.

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

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 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 $3cdot17cdot19 < 11cdot13cdot17$ .

Say our secret is 2. Pick $alpha = 51$ , satisfying the required condition for the Asmuth-Bloom scheme. Then $2+51cdot 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 {1,12,2} and show that it recovers the secret S=2. Consider the following system of congruences:

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 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 + 12cdot e_2 + 2cdot e_3$ , where each is found as follows:

By , since $(m_i,M/m_i) = 1$ , there exist positive integers and , that can be found using the , such that $r_i.m_i+s_i.M/m_i = 1$ . Set $e_i=s_icdot M/m_i$ .

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