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:
“Mad? Is one who has solved the secret of life to be considered mad?”
—Edward T. Lowe. Frank Strayer. Dr. von Niemann (Lionel Atwill)
“We fight our way through the massed and leveled collective safe taste of the Top 40, just looking for a little something we can call our own. But when we find it and jam the radio to hear it again it isn’t just ours—it is a link to thousands of others who are sharing it with us. As a matter of a single song this might mean very little; as culture, as a way of life, you can’t beat it.”
—Greil Marcus (b. 1945)