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:
“The mere idea of marriage, as a strong possibility, if not always nowadays a reasonable likelihood, existing to weaken the will by distracting its straight aim in the life of practically every young girl, is the simple secret of their confessed inferiority in men’s pursuits and professions to-day.”
—William Bolitho (1890–1930)
“So close is the bond between man and woman that you can not raise one without lifting the other. The world can not move ahead without woman’s sharing in the movement, and to help give a right impetus to that movement is woman’s highest privilege.”
—Frances Ellen Watkins Harper (1825–1911)