Elliptic Curve Verifiable Secret Sharing

Question

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.

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.