CNS - 36 - Verifiable Secret Sharing

The dealer generates a random polynomial \(p(x)\) with degree \(t-1\) and with \(P(0) = s\)

\[p(x) = s + a_1x + a_2x^2 + \ldots + a_{t-2}x^{t-2} + a_{t-1}x^{t-1}\]

where \(a_i\) are random terms in the suitable modular range. Once having done that, we distribute one share to each of the \(n\) parties

\[(x_i, y_i) = y_i = p(x_i)\]

The additional step done by the dealer Feldman scheme is the following one: for each coefficient of the polynomial as well as for the secret the following values are computed and broadcasted in public

\[\begin{split} c_0 &= g^{s} \mod p \\ c_1 &= g^{a_1} \mod p\\ &\,\,\, \vdots \\ c_{t-1} &= g^{a_{t-1}} \mod p \end{split}\]

Notice that, at least in principle, the broadcasting of these values does not reveal anything about the coefficient values, because as long as the value of the prime \(p\) is sufficiently large, than the DLOG problem is computationally unfeasible. These values are called commitments, because they allow you to understand whether or not the coefficient of the polynomial were actually used.

Consider now then the party \(i\) receives the share \((x_i, y_i)\).

When \(i\) reveals his share, the other parties can check if the value revealed by the party \(i\) is correct by computing the following value (working \(\mod p\))

\[\begin{split} & \;\;\; c_0 \cdot c_1^{x_i} \cdot c_2^{x_i^2} \cdot c_3^{x_i^3} \cdot \ldots \cdot c_{t-1}^{x_i^{t-1}} = \\ &= (g^s) \cdot (g^{a_1})^{x_i} \cdot (g^{a_2})^{x_i^2} \cdot (g^{a_3})^{x_i^3} \cdot \ldots \cdot (g^{a_{t-1}})^{x_i^{t-1}} = \\ &= g^{s + a_1x_i + a_2x_i^2 + a_3x_i^3 + \ldots + a_{t-1}x_i^{t-1}} = \\ &= g^{p(x_i)} \\ \end{split}\]

Notice that in the polynomial we have re-constructed the value of the polynomial at the point \(x_i\) without actually knowing the value. Indeed, we can perform this computation even before the \(i\) -th pary decides to reveal his share. When the \(i\) party finally reveals his share \((x_i, y_i)\), I can just check if the value previously computed matches with the \(y_i\) given, that is, if

\[g^{y_i} = g^{p(x_i)} \mod p\]

We can have various different commitments. For each one of them we have to understand how much they are hiding and how much they are binding. For example.

• Feldman commitment: Given by the following transformation

  \[x \to g^x \mod p\]

  this commitment is only computationally hiding, because given \(c = g^x \mod p\) it is computationally bounded to get back \(x\), and thus with enough computationally power you can actually break it.

  In terms of binding instead this scheme is perfectly binding, because the sender cannot find any other \(x'\) such that \(g^{x'} = c\) where \(x'\) is larger than the group order. This result doesn't depend on computationally power.

  ---

• Hash commitment: Given by the following transformation, where \(H(\cdot)\) is an hash function.

  \[x \to H(x)\]

  This commitment is computationally hiding, since with sufficient power you can get back the original value \(x\).

  This commitment is also computationally binding, because with sufficient power you can find a new value \(x'\) such that it creates a collsion, that is such that \(H(x') = H(x)\).

  Thus an hash function is a bad commitment value.

Observation 1: It is actually impossible to have a commitment scheme that is both perfectly hiding and perfectly binding.

Observation 2: When a scheme such as \(g^x \mod p\) is computationally hiding you need to look at two things:

1. That \(p\) is large enough.

2. That \(x\) is large enough in the same order of \(p\).

In this scheme the dealer does the following:

• Generates two random polynomials: where \(s\) is the secret and \(r\) is the random value generated for computing the commitment.

  \[\begin{split} f(x) &= s + a_1x + a_2x^2 + \ldots + a_{t-2}x^{t-2} + a_{t-1}x^{t-1} \\ f'(x) &= r + b_1x + b_2x^2 + \ldots + b_{t-2}x^{t-2} + b_{t-1}x^{t-1} \\ \end{split}\]

• Distributes the shares: Each party \(i\) then receives a double share \((x_i, y_i, z_i)\)

  \[\begin{split} y_i &= f(x_i) = s + a_1x_i + a_2x_i^2 + \ldots + a_{t-1} x_i^{t-1} \\ z_i &= f'(x_i) = r + b_1x_i + b_2x_i^2 + \ldots + b_{t-1} x_i^{t-1} \\ \end{split}\]

• Publish the commitments: Finally, you publish all the commitments

  \[\begin{split} c_0 &= g^s \cdot h^r \\ c_0 &= g^{a_1} \cdot h^{b_1} \\ &\,\,\,\vdots \\ c_{t-1} &= g^{a_{t-1}} \cdot h^{b_{t-1}} \\ \end{split}\]

Notice that all these commits are perfectly hiding.

When party \(i\) receives shares \((x_i, y_i, z_i)\) it can be verifies \(\mod p\) that

\[ c_0 \cdot c_1^{x_i} \cdot c_2^{x_i^2} \cdot \ldots \cdot c_{t-1}^{x_i^{t-1}} = \ldots = g^{y_i} \cdot h^{z_i}\]