Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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)
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.
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 :)
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).$$
