# What is the reason for Shamir scheme to use modulo prime?

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?

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.

• 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. Jul 23 at 21:49