Secret Sharing Using The Chinese Remainder Theorem - Secret Sharing Using The CRT

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 ), 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, Mignotte's and Asmuth-Bloom's Schemes, which are explained below.