# What is the significance of $\prod \limits_{i=1}^{t}m_i > p \prod \limits_{i=1}^{t-1}m_{n-i+1}$ in Asmuth–Bloom threshold SSS?

In this paper by Asmuth–Bloom on threshold SSS, the algorithm is as follows:

## Shares Distribution

To distribute $$n$$ shares of a secret $$K$$ among the set of participants $$P = \{ p_i : 1 ≤ i ≤ n\}$$, the dealer D does the following:

1. A set of integers $$\{ p, m_1 < m_2 < · · · < m_n \}$$, where $$0 ≤ K < p$$, is chosen subject to the following conditions:

$$\gcd(m_i , m_j)=1$$ where for $$i\neq j$$

$$\gcd(p , m_i)=1$$ ,for all $$i$$,

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

2. Let $$M =\prod \limits_{i=1}^{t}m_i$$.
The dealer computes $$y = K+ap$$, where $$a$$ is a positive integer generated randomly subject to the condition that $$0 ≤ y < M$$

3. The share of the $$i^{th}$$ participant,$$1 ≤ i ≤ n$$, is $$y_i = y~ mod ~m_i$$

## Secret Construction

Assume $$C$$ is a coalition of $$t$$ participants to construct the secret. Let $$M_C =\prod \limits_{i=1}^{C}m_i$$

1. Given the system $$y \equiv y_ i \mod m_ i$$ for $$i \in C$$, solve $$y$$ in $$GF(M_C )$$ uniquely using the CRT.

2. Compute the secret as $$K = y \mod p$$

According to the CRT, $$y$$ can be determined uniquely in $$GF(M_ C)$$. Since $$y \lt M \leq M_C$$, the solution is also unique in $$GF(M)$$.

Could you please explain significance of $$\prod \limits_{i=1}^{t}m_i > p \prod \limits_{i=1}^{t-1}m_{n-i+1}$$ in Asmuth–Bloom threshold SSS?

One of the required properties with a secret sharing scheme is that if you have $$t-1$$ shares (where $$t$$ is the threshold), then you can't eliminate any possible values from being the shared secret.

Now, suppose that we had $$t-1$$ shares; with the Asmuth-Bloom scheme, we would learn the most if they happened to be shares $$(y_{n-t+2})$$ through $$y_{n}$$. If you had those shares, then you could deduce the value $$y \bmod \prod \limits_{i=1}^{t-1}m_{n-i+1}$$

You also know that:

• $$0 \le y < M$$

• You really want the value $$y \bmod p$$

For you to learn nothing, we need to have all possible values of $$y \bmod \prod \limits_{i=1}^{t-1}m_{n-i+1} + pk$$ to be in the range $$[0, .., M-1]$$

This is guaranteed if $$p \cdot \prod \limits_{i=1}^{t-1}m_{n-i+1} \ge M$$, which (if we remember that $$M = \prod \limits_{i=1}^t m_i$$ is precisely the restriction they give.

BTW: what is this fascination with Asmuth-Bloom? In my opinion, Shamir Secret Sharing is a better way of solving the problem; it's simpler, a lot easier to set up, has smaller shares, and it doesn't leak any probabilistic information like Asmuth-Bloom does.

• I am a beginner of Secret Sharing Schemes(SSS), surveying SSS, not biasing any specific area. Thank you, sir, for giving your valuable suggestion. Mar 15, 2019 at 4:02