Pairwise-independent hashing controls fibre size

Let $U$ be a finite set with $\mathrm{\mid }U\mathrm{\mid }\ge 2$, let $R$ be a nonempty finite set, and let $\mathcal{H}$ be a nonempty finite family of maps from $U$ to $R$. Assume pairwise independence: under a uniform choice of $h\in \mathcal{H}$, for distinct $z,z^{\mathrm{\prime }}\in U$ and all $y,y^{\mathrm{\prime }}\in R$, $\mathrm{Pr}(h(z)=y,h(z^{\mathrm{\prime }})=y^{\mathrm{\prime }})=\mathrm{\mid }R{\mathrm{\mid }}^{-2}\mathrm{.}$ For $S\subseteq U$ and $y\in R$, put $N=\mathrm{\mid }\{z\in S:h(z)=y\}\mathrm{\mid }$. Then $\mathbb{E}N=\mathrm{\mid }S\mathrm{\mid }\mathrm{/}\mathrm{\mid }R\mathrm{\mid }$ and $\mathrm{Var}N\le \mathbb{E}N$. Write $\mu =\mathrm{\mid }S\mathrm{\mid }\mathrm{/}\mathrm{\mid }R\mathrm{\mid }$. The test $N>0$ has probability at most $1\mathrm{/}4$ when $\mu \le 1\mathrm{/}4$, and at least $3\mathrm{/}4$ when $\mu \ge 4$.

The corresponding public challenge announces $h$ (and the fixed target $y$), asks the prover for $z$, and accepts exactly when $z\in S$ and $h(z)=y$. Its optimal acceptance probability is $\mathrm{Pr}(N>0)$, giving the stated gap between these two promised size regimes. When elements and hashes have polynomial-length encodings, the uniform hash is sampled using polynomially many fair bits, and hash evaluation and membership in $S$ are polynomial-time decidable, this is a polynomial-time public-coin challenge: the verifier announces every sampling bit before receiving the response, then performs the stated deterministic checks.