1
$\begingroup$

In Shamir's secret sharing scheme, Dealer performs the following steps

  1. Choose a prime number $q$ such that $q > n$

  2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

  3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

  1. Compute shares $s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$ and sends secretly to participants

  2. At least threshold number of participants can reconstruct secret by using Lagranges interpolation formula

My doubt is:

Instead of step 4 mentioned above, if we write without $\mod q$ as shown below then what will happen?

  1. Compute shares $s_i = g(id_i) , i=1,2, \cdots,n$.

Is there any advantage to use $\mod q$ over naive method (without using modulo)? If yes, is it security or computational complexity or any other?

$\endgroup$
4
$\begingroup$

Is there any advantage to use $\bmod q$ over naïve method (without using modulo)? If yes, is it security or computational complexity or any other?

Yes; doing things $\bmod q$ does have the practical advantage that the shares are bounded length; computing the shares in $\mathbb{Z}$ can potentially have us send rather long values (as the values there don't have an upper bound).

However there are also security concerns:

  • Revealing the shares in $\mathbb{Z}$ leaks information; for example, suppose someone knows the share $(x, y)$ for $x=2$ that corresponds to a secret $z$. That is, he is given a value $y = a_n2^n + a_{n-1} 2^{n-1} + ... + a_12^1 + z$. Now, the nonconstant terms are all even; hence if they see that $y$ is odd, that means that $z$ must also be odd; that is, we just leaked the lsbit. Extending this observation shows that a share $(x, y)$ reveals the value of $z \bmod x$. A similar observation shows that two shares $(x_0, y_0)$, $(x_1, y_1)$ also reveals $z \bmod x_0 - x_1$. This is in contrast to the standard Shamir Secret Sharing, which has no such leakage.

  • Shamir assumes that the secret coefficients $a_n, a_{n-1}, ..., a_1$ are chosen uniformly. However, it turns out to be impossible to select uniformly randomly from a set of size $\aleph_0$ (which the set of integers is), that is, any selection method must necessarily be biased. And, depending on what the distribution is, this bias will also leak further information.

BTW: Shamir Secret Sharing isn't necessarily done modulo a large prime; it can be implemented over any finite field. In practice, we often use even characteristic fields, such as $GF(2^8)$ or $GF(2^{128})$; the security is the same, but it has the practical advantage of everything fitting in an integral number of bytes.

$\endgroup$
1
  • 2
    $\begingroup$ It's also worth mentioning that Shamir sharing doesn't work mod $q$ when $q$ is composite. In that case, reconstructing the secret via the Lagrange interpolation formula will fail (Lagrange requires division at some point and division doesn't always work modulo a composite). And indeed, not every set of $d$ points will have a degree $<d$ polynomial hitting them; and some sets of $d$ points will have more than one polynomial hitting them. $\endgroup$
    – Mikero
    Jul 23 at 21:49

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.