Skip to main content
5 of 16
added 13 characters in body
Natwar
  • 441
  • 2
  • 8

Why threshold number number of shares is required to construct secret?

In this paper of Asmuth–Bloom 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:

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

$\gcd(m_i , m_j)=1$ where for $i!=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}$

$M =\prod \limits_{i=1}^{t}m_i$

Dealer computes

 y = K+ap
 where a is a positive integer generated randomly subject to the condition that 0 ≤ y < M

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$ $y \equiv y_ i \mod m_ i $

for $i ∈ C$, solve y in $GF(M_C )$ uniquely using the CRT. 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)$.

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

Natwar
  • 441
  • 2
  • 8