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 the 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?

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?

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$ 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 ∈ 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 the [this] 2 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?

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 the 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?

In this][1] 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$ 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 ∈ 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 the [this] [2] 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? [2]:https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1056651 [1]: http://pdfs.semanticscholar.org/440d/fa8ab99301d4ea3a8b19c0748575915aef15.pdf

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$ 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 ∈ 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 the [this] 2 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?