I'm reading this paper, which on page 3(Section IV.C) presents a Jointly Random Verifiable Secret Sharing Scheme for Elliptic curves. The algorithm makes sense to me save for this part:

"Each $P_{i\neq j}$ verifies that his share is consistent with other shares i.e. $a_0^{(i)}G = \sum_{j \in B}b_j f_i(j)G$"

Just to explain the terms for those that haven't read the whole paper:$E$ is an elliptic curve, the base point is $G \in E(Z_p)$ of order $r$.

Player $P_i$ shares secret $a_0^{(i)}$ via $f_i(x)$, a random polynomial of degree $t$. $P_i$ then sends other players their share, i.e. sends $f_i(j)$ to player $P_j \hspace{3pt}\forall j \in \{1,\cdots,n\}$. $P_i$ also broadcasts $f_i(j)G \hspace{3pt}\forall j \in \{1,\cdots,n\}$.

So, can someone please explain to me why this equation holds:$$a_0^{(i)}G = \sum_{j \in B}b_j f_i(j)G$$

The authors do not seem to define $B$ or $b_i$. However, later in the same paper,in a related context, they define $b_i = \prod\limits_{j \in B, j \neq i}\frac{j}{(j-i)}$. I'm not sure if that definition applies here too.


1 Answer 1


The values

$b_i = \prod\limits_{j \in B, j \neq i}\frac{j}{(j-i)}$

are the evaluations of the so called Lagrange basis polynomials at point $0$. These terms are often also called Lagrange coefficients and can be computed by any participant and $B$ is the index set of the participants.

The formula

$a_0^{(i)}G = \sum_{j \in B}b_j f_i(j)G$

is just a Lagrange polynomial interpolation, i.e., a weighted sum of the lagrange coefficients. That's just Shamir's secret sharing in the "exponent" (not literally, because we have an additive group here, but the reconstructed value $a_0^{(i)}=f_i(0)$ is hidden due to the DL assumption).

This means reconstruction of the secret (the share $a_0^{(i)}$ of party $i$) without revealing the secret value itself (since the value $a_0^{(i)}$ is not revealed from $a_0^{(i)}G$ as this would require solving the discrete log problem in the used group and the values $f_i(j)G$ also do not reveal the values $f_i(j)$.

Basically, the verifiable secret sharing is achieved by letting every party $i$ revealing "shares" of their share value $a_0^{(i)}$ (hidden due to the DL assumption). Consequently, the participants can verify whether their shares $a_0^{(i)}$ are consistent without revealing their share values (what verifiable secret sharing is about).

Hope that helps.


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.