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.
Read more about this topic: Secret Sharing Using The Chinese Remainder Theorem
Famous quotes containing the words secret and/or sharing:
“Awareness of having better things to do with their lives is the secret to immunizing our children against false valueswhether presented on television or in real life. The child who finds fulfillment in music or reading or cooking or swimming or writing or drawing is not as easily convinced that he needs recognition or power or some high to feel worthwhile.”
—Polly Berrien Berends (20th century)
“The traditional American husband and father had the responsibilitiesand the privilegesof playing the role of primary provider. Sharing that role is not easy. To yield exclusive access to the role is to surrender some of the potential for fulfilling the hero fantasya fantasy that appeals to us all. The loss is far from trivial.”
—Faye J. Crosby (20th century)