The Goldwasser-Sipser set lower bound protocol is as follows: Let $\mathcal{H}_{m,k}$ be a pairwise independent family of hash functions from $\{0,1\}^{m} \rightarrow \{0,1\}^{k}$. Given $S \subset \{0,1\}$, we want to determine if $|S| \geq K$. We are also able to certify membership for elements of $S$. We have the prover $P$ and a verifier $V$ such that the verifier is to reject with high probability if $|S| \leq K/2$ and accept with high probability if $|S| \geq K$. Here is the procedure
1.) Let $k \in \mathbb{N}$ such that $2^{k-2} \leq K \leq 2^{k-1}$.
2.) The verifier chooses a uniformly random hash function from $\mathcal{H}_{m,k}$ and a uniformly random bit string $y \in \{0,1\}^{k}$ and sends it to the prover.
3.) The prover tries to find an $x \in S$ such that $h(x) = y$, and sends $x$ along with a certificate that $x \in S$.
4.) If the certificate is valid and $h(x) = y$ then accept the proof, else reject.
With the argument given here (page 4), the probability that the verifier $V$ accepts is $\geq \frac{3}{4}p$, where $p = \frac{K}{2^{k}}$ when $|S| = K$.
Question: I wanted to know if there is a way to obtain perfect completeness. That is, if $|S| = K$, then $P[V \text{ accepts }] = 1$. The hint given in Arora-Barak is as follows:
First note that in the
current set lowerbound protocol we can have the prover choose the
hash function. Consider the easier case of constructing a protocol to
distinguish between the case $|S| ≥ K$ and $|S| ≤ \frac{1}{c} K$ where $c > 2$ can
be even a function of $K$. If $c$ is large enough the we can allow the
prover to use several hash functions $h_{1}, . . . , h_{i}$
, and it can be proven
that if i is large enough we’ll have $\cup_{i}h_{i}(S) = \{0, 1\}^
k$
. The gap can be
increased by considering instead of S the set $S^{l}$, where $S^{l}$ is the $l$ fold cartesian product.