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?

Question

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?

Answer 1

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.