Pairwise-independent hashing controls fibre size

Write $N={\sum }_{z\in S}{I}_z$, where $I_z$ indicates $h(z)=y$. Since $\mathrm{\mid }U\mathrm{\mid }\ge 2$, the pairwise-independence definition Pairwise independent hash families gives uniform marginals by summing the joint distribution over a distinct input; it also gives zero covariances for distinct $z$. Thus $\mathbb{E}{I}_z=1\mathrm{/}\mathrm{\mid }R\mathrm{\mid }$.

Hence $\mathbb{E}N=\mathrm{\mid }S\mathrm{\mid }\mathrm{/}\mathrm{\mid }R\mathrm{\mid }$ and $\mathrm{Var}N={\sum }_z\mathrm{Var}{I}_z\le {\sum }_z\mathbb{E}{I}_z=\mathbb{E}N$. More exactly, $\mathrm{Var}N=\mu (1-1\mathrm{/}\mathrm{\mid }R\mathrm{\mid })\le \mu$.

Since $N$ is a nonnegative integer, ${\mathbf{1}}_{\{N>0\}}\le N$, so $\mathrm{Pr}(N>0)\le \mu \le 1\mathrm{/}4$ in the small regime. For $\mu >0$, on $N=0$ one has $(N-\mu {)}^2={\mu }^2$, hence ${\mu }^2\mathrm{Pr}(N=0)\le \mathbb{E}(N-\mu {)}^2\le \mu$. Therefore $\mathrm{Pr}(N>0)\ge 1-1\mathrm{/}\mu \ge 3\mathrm{/}4$ when $\mu \ge 4$.

If $N=0$, no prover response passes the stated checks. If $N>0$, an unrestricted prover can supply a valid preimage. Thus the optimal acceptance probability is exactly $\mathrm{Pr}(N>0)$. The checks are polynomial-time under the stated encoding and algorithmic hypotheses, and revealing every sampling bit before the response makes the protocol public-coin. This proves the quantitative challenge claim.