6
$\begingroup$

I need to make use of a secret sharing scheme and I don't really know how to decide which one to use, Shamir's or Asmuth-Bloom (using CRT).

The complexity for recovering the secret seems to be linear in both cases and both schemes are perfectly secure.

Can anyone give arguments why we should opt for one over the other?

$\endgroup$
  • $\begingroup$ It looks to me that properly choosing the parameters correctly and efficiently during the dealer phase in Asmuth-Bloom can be tricky. $\endgroup$ – Artjom B. Apr 7 '16 at 9:21
6
$\begingroup$

There is one theoretical difference between Shamir's scheme and Asmuth and Bloom's scheme.

Shamir can be done in an informationally secure manner; specifically, if the nonconstant polynomial coefficients were chosen in a random manner (that is, from a uniform probability distribution that's uncorrelated to anything else the attacker can see), then someone with a number of shares that's less than the threshold gains no information about the shared secret. This is because, for any potential value of the shared secret, there is the same number of possible secret coefficients that is consistent with that secret value - if we assume that those coefficients were chosen uniformly, the attacker has no criteria to say that one set of coefficients is any more likely that the other.

In contrast, Asmuth and Bloom's scheme does leak some probabilistitic information. Now, any particular value of the shared secret is possible; however different values of the shared secret have different numbers of possible secret value $\alpha$. Assuming that the attacker knows the probability distribution that $\alpha$ was drawn from, he can then assign different probabilities to the values of the shared secret, should he choose to.

As Asmuth and Bloom's scheme does leak some probabilistic information, while Shamir's does not, well, that seems like a good reason to prefer Shamir's (especially since, as Louis says, Shamir's is actually easier from a practical standpoint)

$\endgroup$
5
$\begingroup$

I too had to go through this decision some time back and did a comparative study of both schemes. Shamir's scheme is used for the majority of works in the area of threshold secret sharing. This is because of the foremost reason of the number of primes required in both the schemes. Asmuth-Bloom's scheme require $n+1$ ($n$ being the number of shares) prime numbers greater than the secret and following a special sequence, as mentioned in Louis's answer. This makes the scheme n times slower than Shamir's.

We can list down these factors to show why Shamir's is better than Asmuth-Bloom's scheme.

  • Asmuth-Bloom's scheme requires $n$ more primes than Shamir's
  • Asmuth-Bloom's scheme is not ideal as the length of shares are n times longer than the secret while share size of Shamir's scheme is at most the length of the secret.
  • Probability distribution of the random parameter used in Asmuth-Bloom's can help to gain information about the secret
  • Choosing the random parameter and primes can be tricky. A naive implementation can run into an infinite loop finding these numbers.
$\endgroup$
3
$\begingroup$

Shamir's scheme is the most widely used scheme in such things as multi-party computation, threshold cryptography and oblivious transfer. Honestly I don't really know of any real everyday use of secret sharing based on CRT.

As Artjom said Asmuth and Bloom's scheme takes some time to setup. The dealer must choose pairwise relatively prime integers $m_0 < m_1 < m_2 < . . . < m_n$ where $m_0 > d$ such that:

$\prod^{t}_{i=1}m_i>m_0 \prod^{t-1}_{i=1}m_{n-1+1}$

Whilst this doesn't seem like much it takes far more time/computations than the dealer phase of Shamir's scheme where the dealer simply chooses the coefficients of the polynomial at random.

Finally if we look at the reconstruction phases of both Shamir's scheme simply uses Lagrange interpolation whilst Asmuth and Bloom's scheme requires the solving of simultaneous congruences.

As can be seen Shamir's scheme is far simpler and more elegant! Hope this helps :)

$\endgroup$
2
$\begingroup$

Technical details were fully dicussed in the previous answers. But from mathematical point of view both schemes are almost identical. The reason is that Lagrange interpolation polynomial is a solution polynomial CRT-system $$f(x)\equiv a_i\bmod (x-x_i)\qquad(1\le i\le n,\deg f<n).$$

$\endgroup$

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.