1
$\begingroup$

The process of Shamir secret sharing degree reduction in multiplication gate is explained in the following link

Now, based on the secret sharing that done by a degree one polynomial, we must be able to reconstruct the secret, i.e. $10$, with each of the $2$ shares out of the $3$ shares $(3, 7, 0)$. Nevertheless, the reconstructed secret using $(3, 7)$ is correctly $10$, but reconstructed secret using $(3,0)$ is 9 and using $(7, 0)$ is $1$. Why is this so? Where is the mistake?

$\endgroup$
2
  • $\begingroup$ I can't tell where you might have made a mistake, but just to check off one obvious possibility, are you using the correct $x$ coordinates for the shares? Each share in Shamir's scheme is really a pair of numbers $(x,y)$, where $x$ does not depend on the shared secret and can be public, but must be unique and (in the usual version of Shamir's scheme) non-zero, while $y$ is basically pseudorandom and must be kept secret by the shareholder to avoid leaking the share. $\endgroup$ Mar 10, 2022 at 20:35
  • $\begingroup$ You are not supposed to reconstruct the secret using two out of the three shares. Instead, you need three out of the three shares, or, in other words, you need all of the shares. This is because the resulting polynomial has degree $2$, so you need three shares $\endgroup$
    – Daniel
    Mar 10, 2022 at 20:35

1 Answer 1

1
$\begingroup$

I think you misunderstand share reconstruction. A share $(a,b,c)$ in this context is a triple of values corresponding to polynomial evaluation, namely $(\sigma(1), \sigma(2),\sigma(3))$. The problem of share reconstruction is, using

  1. any two of the above values of $\sigma(i)$, and
  2. knowledge that $\sigma(x) = \sigma(0)+ax$ is a linear-degree polynomial,

to recover $\sigma(0)$. This can easily be done. Say we have $\sigma(i) = \sigma(0) + ai$ and $\sigma(j) = \sigma(0) + aj$. We can subtract these and "solve" for $a$ to get that $a = (i-j)^{-1}(\sigma(i)-\sigma(j))$, where $a^{-1}$ is the inverse modulo 11. Then, using this value of $a$, it is simple to recover $\sigma(0)$.

Note that the computed value of $a$ is the same in all 3 cases. When $(i,j) = (1,2)$, we have that

$$a = (1-2)^{-1}(3-7) = 4$$

when $(i,j) = (1,3)$ we have that

$$a = (1-3)^{-1}(3-0) = (-2)^{-1}3 = (-6)3\equiv -18\bmod 11 \equiv 4\bmod 11.$$

Similarly, when $(i,j) = (2,3)$, we have that

$$a = (2-3)^{-1}(7-0) = -7\equiv 4\bmod 11.$$

Next, for any index $i$, we have that $\sigma(0) = \sigma(i) - ai\bmod 11 \equiv \sigma(i) - 4i\bmod 11$. It is straightforward to check that for any pair $(i, \sigma(i))$, namely for $(1, 3)$, $(2,7)$, or $(3,0)$, one obtains $10\bmod 11$ (or $-1\bmod 11$ --- these are the same value).


That all being said, I do not find the explanation of degree reduction in the linked answer to be that clear personally. I have previously explained it here. Roughly, one achieves degree reduction by combining

  1. viewing share interpolation/evaluation as a "change of basis", and
  2. reducing from a degree $2t$ polynomial to a degree $t$ polynomial via projecting onto the first $t$ coordinates (in the appropriate basis).

If you are more comfortable with linear algebra, this gives a clear "geometric" picture of what is happening. Of course, this depends on your background.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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