3
$\begingroup$

I was learning Asmuth-Bloom's threshold secret sharing scheme. I was working out an example as given in this Wikipedia article. As per the example, the secret, d is 2, the number of shares, n is 4 and threshold, k is 3. The list of relatively prime integers, m is [3,11,13,17,19] and it follows the criteria $m_1.m_2.m_3 > m_0.m_3.m_4$. As per the example, the shares are generated as $1$ $mod$ $11$, $12$ $mod$ $13$, $2$ $mod$ $17$ and $3$ $mod$ $19$. The example then regenerates the secret using the shares $1$ $mod$ $11$, $12$ $mod$ $13$, $2$ $mod$ $17$.

However, when I tried to reconstruct the secret using two shares ($1$ $mod$ $11$ and $3$ $mod$ $19$) I could regenerate the secret, which is against the threshold property.

I tried for multiple examples and this was true for all cases.

Can somebody explain if I am wrong somewhere or if there is a limitation in the threshold scheme?

$\endgroup$
5
$\begingroup$

I don't believe that, in the example you gave, you can reconstruct the secret using two shares.

$d + \alpha m_0$ is in the range $[0, 2431)$; using the two shares $1 \bmod 11$ and $3 \bmod 19$, you can determine that it is one of $155, 364, 573, 782, 991, 1200, 1409, 1618, 1827, 2036, 2245$, however you have no further information about which it might be. Since these include values consistent with all possible values of $d$ (which must be between 0 and $m_0-1$), we can conclude that the attacker cannot determine the value of $d$, or even eliminate any potential value of $d$.

On the other hand, if the attacker knows the probability distribution $\alpha$ was chosen from, he can obtain some probabilistic information about $d$. In the case in question, we see that there are four possible values of $\alpha$ that is consistent with $d=1$ and $d=2$, while there are only three possible values that is consistent with $d=0$. If the attacker knows that $\alpha$ was chosen uniformly, he may conclude that while $d=0$ is possible, it is somewhat less probable to be the shared secret than either of the other two.

In contrast, Shamir's Secret Sharing doesn't leak any such probabilistic information for any number of shares less than the threshold.

$\endgroup$
  • $\begingroup$ Thanks a lot @poncho. I did not take care of the fact that the value $155$ mod $209$ is within $[0,2431)$. Thanks again for clearing my doubt. $\endgroup$ – vishnuvp Mar 16 '16 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.