Why is a number of shares that is greater than a threshold required to construct a secret?

Question

In this paper of Asmuth–Bloom 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 \text{ where for } i\neq j$$ $$\gcd(p , m_i)=1,\text{ 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 ∈ 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 < M ≤ M_C$ , the solution is also unique in $GF(M)$.

In this original paper the author given to recover $K$ , it clearly suffices to find y. If $y_{1},y_{2}.......y_{t}$ are known, then by the Chinese remainder theorem modulo $M_C =\prod \limits_{i=1}^{C}m_i$ . As $M ≤ M_C$ this uniquely determines $y$ and thus $K$ . On the other hand, if only $t-1$ shares were known, essentially no information about the secret can be recovered

---

How to prove formally that the number of participants lesser than threshold number $t$ cannot get secret?

Answer 1

To show that the adversary could not retrieve the secret, you can show that two different secrets will implies the same shares, and then an adversary that has access to these shares could not retrieve the secret.

To show that the adversary has no bit of information about the secret when he has $t'$ strictly less than $t$ shares, you can show that if you take two different $K_1$ and $K_2$, and compute the cardinality of $a$'s (for $k_1$ and for $K_2$) such that you obtain the $t'$ shares. Because they are the same, and because $a$ is uniformly picked at random, you deduce the perfect secrecy. First I'm claiming that $a$ is chosen unifromly at random in $\{0, \dots, M-1 \}$ (I can give you more details, if you aren't not convinced. Let $\left(y_1, \dots, y_{n-1}\right)$ a vector of shares.\newline We call $\psi$ the isomorphism given by the chinese remainder theorem from $\mathbb{Z}_{m_1} \times \dots \times \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}$ to $\mathbb{Z}_{Mp}$, and $\phi$ the invert isomorphism.

$$Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}, \phi \left(K_1 + a*p\right) = \left(y_1, \dots, y_{n-1}, z, z'\right)\}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}, \phi \left(K_1\right) + \phi\left(a\right)*\phi\left(p\right) = \left(y_1, \dots, y_{n-1}, z, z'\right) \}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists \left(z, z'\right) \in \mathbb{Z}_{m_n} \times \mathbb{Z}_{p}, \phi\left(a\right)*\phi\left(p\right) = \left(y_1 - \left(K_1 \mod m_{1} \right), \dots, y_{n-1} - \left(K_1 \mod m_{n-1}\right), z - \left(K_1 \mod m_{n}\right), z' - \left(K_1 \mod p\right) \right) \}$$

Because $p \mod p = 0$, we deduce, that necessarily $z' = K_1 \mod p$ (and such $z'$ exists).

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists z \in \mathbb{Z}_{m_n}, \phi\left(a\right) = \left(\frac{y_1 - \left(K_1 \mod m_{1} \right)}{p \mod m_{n-1}}, \dots, \frac{y_{n-1} - \left(K_1 \mod m_{n-1}\right)}{p \mod m_{n-1}}, \frac{\left(z - \left(K_1 \mod m_{n}\right)\right)}{p \mod m_n}, 0\right) \}$$

$$ = Card \{a \in \{0, \dots, M-1 \} / \exists z \in \mathbb{Z}_{m_n}, a = \psi\left(\frac{y_1 - \left(K_1 \mod m_{1} \right)}{p \mod m_{n-1}}, \dots, \frac{y_{n-1} - \left(K_1 \mod m_{n-1}\right)}{p \mod m_{n-1}}, \frac{\left(z - \left(K_1 \mod m_{n}\right)\right)}{p \mod m_n}, 0\right) \}$$.

This cardinal doesn't depend of $K_1$ (it's equal to $m_n$).