Score:3

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

in flag

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?

Score:4
my flag

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.

us flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.