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?


1 Answer 1


To your question:

  1. About the HMAC example, maybe the hypothesis that $f^i_A(j)$ is not feasible. Because $f_A(x)$ servers as a role somelike base polynomial while $\psi$ servers as a random scalors of these base polynomials.

$f_A(x)$ is constructed in this way: first, we know $t$ roots of $f_A(x)$, then we assign $f_A(0)=1$. Therefore, $f_A(x)$ is a $t$ degree polynomial whose constant term is 1. Besides, other points like $(j, f_A(j))$ are computed by interpolating. We cannot simply treat $f_A(j)$ as 1.

  1. About reconstructing secret 0. Now that we know the secret is 0, why we need to concern about how to reconstruct the secret. I think maybe the real secret, things we want to hide from is coefficients of non-constant terms in $f_A(x)$, because we usually use PRZS protocol to randomize an existing polynomial whose constant term is a secret.

BTW, there is a simpler version of PRZS:

\begin{equation*} f(X) = \sum_{A\subset X\text{, }|A|=n-t}\sum_{j=1}^t \psi_{r_A}(a, j) \cdot X^j \cdot f_A(X) \end{equation*}

Three observations here:

  1. $f_A(X)$ is a polynomial whose degree is at most $t$ with random constant term.

  2. $X^t \cdot f_A(X)$ is a polynomial whose degree is at most $2t$.

  3. $f(X)$ is divisible by $X$ which means its constant term is 0. Beacause $X^1 \cdot f_A(X)$ contributes $f(X)$'s lowest degree.

Therefore, we come to the conclusion that $f(X)$ is a polynomial that $deg(f) \leq 2t$, and $f(0) = 0$.


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.