Score:1

Problem with Shamir secret sharing degree reduction in multiplication gate

in flag

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?

ar flag
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.
Daniel avatar
ru flag
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
Score:1
ng flag

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.

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.