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

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}$$

1. 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$$

2. 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?

• It is not $GF(M_C)$ but the integers modulo $M_C$ you operate over. Jan 16 '19 at 4:13

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$$).

• While the method you describe can (presumably; I haven't actually done it myself) be used to show that less than $t$ shares are not (always) sufficient to definitively and unambiguously reconstruct the secret, it doesn't prove that an attacker with less than $t$ shares cannot learn anything about the secret. For that, you'd need a slightly more complex argument. Jan 16 '19 at 15:25
• Sorry I didn't well understood the question, I edit my post right now Jan 16 '19 at 15:44
• please tell me what is cardinality you are referred here Jan 17 '19 at 15:59
• Could I suppose all the m_i's are prime numbers? Could you precise exactly and properly in which set $a$ is picked? Jan 18 '19 at 16:55
• The m_i's can be prime numbers. where a is a positive integer generated randomly subject to the condition that 0≤y<M Jan 20 '19 at 5:31