Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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