1
$\begingroup$

I am trying to understand how Asmuth-Bloom's secret sharing is perfect. My "proof" so far (in a 3 out of 4 scheme):

$y=s + a * m_0 \bmod m_1 * m_2 * m_3$

Having $k-1$ shares, it will yield a valid solution for the CRT, but not a unique one. 2 shares yield $x = y' \bmod m_1 * m_2$
Therefore, we know that $y = y' + z * m_1 * m_2$ and also that $y = [0;m_1*m_2*m_3]$
But since we do not know the exact range of $y$, since $m_3$ is missing, we can not just simply guess $z$ and therefore guess $y$.
However, I see a sequence of following primes used a lot, so when we know $m_1$ and $m_2$ we could just assume $m_3$ is the next prime and guess values for $z$ and therefore $y$ right?

Example with numbers:
$m_0 = 43,\space m_1=131, \space m_2=137, \space m_3 = 139, \space m_4=149, \space s=42, \space a = 476$
$y = 42 + 476 * 43$
$y = 20510 \bmod 2494633$

$s_1 = (74, 131), \space s_2 = (97, 137), \space s_3 = (77, 139), \space s_4 = (97, 149)$

CRT with two shares:

$x \equiv 74 \bmod 131$
$x \equiv 97 \bmod 137$
$x \equiv 2563 \bmod 17947$

So now we could start guessing

$y_0 = 2563 + 0*17947$
$y_1 = 2563 + 1*17947$
$y_2 = 2563 + 2*17947$
$y_n = 2563 + n*17947$
and, with the knowledge (or assumption) that $m_3$ is the next prime after $137$, a max value of $y_{138} = 2563 + 138 * 17947$
since $2563 + 139 * 17947$ exceeds $m_1*m_2*m_3$

So we have $138$ values to guess the secret from.
$s_n = y_n \bmod 43$


From my conclusion, this would not be a perfect scheme, but everyone states it is. So where am i wrong?

$\endgroup$
0
$\begingroup$

Okay, so i was finally able to figure out a solution for this. The scheme does indeed yield 138 valid results to guess the secret from. However, since they already know the secret lies in $\mathbb{Z}_{m_0}$ there are only (in the example above) 42 possible secrets anyways. Since $a$ is uniformly distributed, the scheme does indeed leak some probabilistic information about the secret when you apply $\bmod 43$ to all 138 possible values, as seen in:enter image description here

So for example, an attacker could determine that 2,3 or 4 are more likely than for example 0 or 1. However, there is no information leaked about the secret itself.

$\endgroup$
  • $\begingroup$ Actually, as you noted, some probabilistic information about the secret is leaked, hence Asmuth-Bloom can't really be described as "perfect" (in the same sense that, say, Shamir is) $\endgroup$ – poncho Jan 22 at 16:13

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.