Secret sharing using the Chinese remainder theorem

Last updated • 7 min readFrom Wikipedia, The Free Encyclopedia

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 Z/nZ, with n > 0 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.

Contents

Secret sharing schemes: several types

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 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. This is known as a threshold access structure. We call such schemes (t, n) threshold secret sharing schemes, or t-out-of-n 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 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

Let , and . The system of congruences

has solutions in Z if and only if for all , where denotes the greatest common divisor (GCD) of mi and mj. Furthermore, under these conditions, the system has a unique solution in Z/nZ where , which denotes the least common multiple (LCM) of .

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 , given that , 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 mi), but will not reveal the secret given less than k of such shares.

Ultimately, we choose n relatively prime integers 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 are defined by for . 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 threshold access structure.

This condition on S can also be regarded as

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 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, 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 (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 fully recover the secret, no matter how they are chosen.

Formally, let 2 ≤ kn be integers. A (k, n)-Mignotte sequence is a strictly increasing sequence of positive integers , with for all 1 ≤ i < jn, such that . Let and ; we call the integers lying strictly between and the authorized range. We build a (k, n)-threshold secret sharing scheme as follows: We choose the secret S as a random integer in the authorized range. We compute, for every 1 ≤ in, the reduction modulo mi of S that we call si, these are the shares. Now, for any k different shares , we consider the system of congruences:

By the Chinese remainder theorem, since are pairwise coprime, the system has a unique solution modulo . By the construction of our shares, this solution is nothing but the secret S to recover.

Asmuth–Bloom threshold secret sharing scheme

This scheme also uses special sequences of integers. Let 2 ≤ kn be integers. We consider a sequence of pairwise coprime positive integers such that . For this given sequence, we choose the secret S as a random integer in the set Z/m0Z.

We then pick a random integer α such that . We compute the reduction modulo mi of , for all 1 ≤ in, these are the shares . Now, for any k different shares , we consider the system of congruences:

By the Chinese remainder theorem, since are pairwise coprime, the system has a unique solution S0 modulo . By the construction of our shares, the secret S is the reduction modulo m0 of S0.

It is important to notice that the Mignotte (k, n)-threshold secret-sharing 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 S and

Therefore α can be any integer modulo

This product of k − 1 moduli is the largest of any of the n choose k − 1 possible products, therefore any subset of k − 1 equivalences can be any integer modulo its product, and no information from S 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 k = 3 and n = 4. Our pairwise coprime integers being and . They satisfy the Asmuth–Bloom required sequence because .

Say our secret S is 2. Pick , satisfying the required condition for the Asmuth–Bloom scheme. Then 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:

To solve the system, let . From a constructive algorithm for solving such a system, we know that a solution to the system is , where each ei is found as follows:

By Bézout's identity, since , there exist positive integers ri and si, that can be found using the Extended Euclidean algorithm, such that . Set .

From the identities , we get that , and the unique solution modulo is 155. Finally, .

See also

Related Research Articles

<span class="mw-page-title-main">Chinese remainder theorem</span> Theorem for solving simultaneous congruences

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

<span class="mw-page-title-main">Modular arithmetic</span> Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

<span class="mw-page-title-main">Quadratic reciprocity</span> Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

In number theory, Euler's theorem states that, if n and a are coprime positive integers, and is Euler's totient function, then a raised to the power is congruent to 1 modulo n; that is

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

In modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gka. Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is, the factorial satisfies

The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery.

<span class="mw-page-title-main">Carmichael function</span> Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael functionλ(n) of a positive integer n is the smallest positive integer m such that

<span class="mw-page-title-main">Ramanujan tau function</span>

The Ramanujan tau function, studied by Ramanujan (1916), is the function defined by the following identity:

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number p, then this root can be lifted to a unique root modulo any higher power of p. More generally, if a polynomial factors modulo p into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of p.

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.

In mathematics, a Kloosterman sum is a particular kind of exponential sum. They are named for the Dutch mathematician Hendrik Kloosterman, who introduced them in 1926 when he adapted the Hardy–Littlewood circle method to tackle a problem involving positive definite diagonal quadratic forms in four as opposed to five or more variables, which he had dealt with in his dissertation in 1924.

The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r2n, where p is a prime: that is, to find a square root of n modulo p.

In cryptography, the Rabin signature algorithm is a method of digital signature originally proposed by Michael O. Rabin in 1978.

Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x3 ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x3p is solvable if and only if x3q is solvable.

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as

Shamir's secret sharing (SSS) is an efficient secret sharing algorithm for distributing private information among a group so that the secret cannot be revealed unless a quorum of the group acts together to pool their knowledge. To achieve this, the secret is mathematically divided into parts from which the secret can be reassembled only when a sufficient number of shares are combined. SSS has the property of information-theoretic security, meaning that even if an attacker steals some shares, it is impossible for the attacker to reconstruct the secret unless they have stolen the quorum number of shares.

References