# Pseudorandom zero-sharing: how does it work?

TL;DR

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. 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$$.