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:
“I know what it is to have little, and I know what it is to have plenty. In any and all circumstances I have learned the secret of being well-fed and of going hungry, of having plenty and of being in need. I can do all things through him who strengthens me.”
—Bible: New Testament, Philippians 4:12-13.
Paul.
“The cup of blessing that we bless, is it not a sharing in the blood of Christ? The bread that we break, is it not a sharing in the body of Christ?”
—Bible: New Testament, 1 Corinthians 10:16.