Mignotte's scheme

From CryptoWiki
Jump to: navigation, search

Chinese remainder theorem provides us with a method to uniquely determine a number x modulo t-many relatively prime integers Mg p1 pt.png given that

Mg syst.png (1)

A (t,n)-Mignotte sequence is a strictly increasing sequence of positive prime integers Mg p1 less pn.png, such that Mg nr 1.png. We build a (t,n)-threshold secret sharing scheme as follows: We choose the secret x as a random integer in the range Mg nr 2.png. We compute a share for every participant i: Mg share.png.

Now, for any t different shares, we consider the system of congruences:

By the Chinese remainder theorem, since Mg p1 pt.png are pairwise coprime, the system (1) has a unique solution. By the construction of our shares, this solution is nothing but the secret x to recover. [Mi83]

Go to the main page