How can the shares of the PRZS protocol proposed in [CDI05] reconstruct the "secret" $0$?

Is the number of shares required to reconstruct $0$ equal to $2t + 1$?

Long question

The paper "Share conversion, pseudorandom secret-sharing and applications to secure computation." by Cramer, Damgård, and Ishai shows a protocol for pseudorandom zero-sharing that enables every player $P_j$ to locally compute his share $s_j$ of the polynomial $f_0$ of degree $2t$ from initially distributed keys $r_A^i$, where $t = k - 1$ in a $(k, n)$ secret sharing scheme.

$s_j$ is computed as follows: $$s_j = \sum_{A \subseteq [n] : |A| = n - t, j \in A} \sum_{i = 1}^{t} \psi_{r_A^i}(a) \cdot f_A^i(j)$$

The authors say that: "it is straightforward to verify that this results in shares consistent with polynomial $f_0$" and that: "$\mathit{deg}(f_0) \leq 2t$ and $f_0(0) = 0$".

If I've correctly understood, if we make $f_A^i(j) = 1, j \in A$ and we consider $\psi$ as an HMAC function, then every player $P_j$ simply sums the HMAC of $a$ with all the keys $r_A$ he has received from all the sets $A$ he belongs to.

How can this result in shares (polynomial $f_0$) that can reconstruct the secret 0? It still remains quite obscure to me.

Furthermore, since $\mathit{deg}(f_0) \leq 2t$, does this imply that to reconstruct $0$ we need $2t + 1$ shares at most?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.