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?


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.

  • $\begingroup$ I am a beginner of Secret Sharing Schemes(SSS), surveying SSS, not biasing any specific area. Thank you, sir, for giving your valuable suggestion. $\endgroup$ – subbu Mar 15 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.