Asmuth-Bloom's threshold secret sharing scheme

Question

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?

Answer 1

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.