Bit Guessing Game

The bit guessing game models two players, namely Alice and Bob, where Alice has a secret vector $\vec x \in \{0, 1 \}^n$ which Bob tries to learn. Bob is only allowed to ask Alice the value of

for bit vector $\vec c \in \{0, 1\}^n$ he comes up with. Under this setting, it is trivial for Bob to learn each bit of $x$: he needs to just query Alice for $\vec e_i \cdot \vec x$, where $\vec e_i$ is the indicator vector with its $i$-th dimension equal to 1 and other dimensions equal to 0.

One way for Alice to prevent information leakage is to add some bounded noise $Z$ to the query result and returns

For example, $Z$ could be a bounded random variable. Is is still a chance for Bob to learn the vector $\vec x$?

Theorem 1. If Bob is allowed to query $r(\vec c)$ for all $\vec c \in \{0, 1\}^n$, and suppose that $Z$ is bounded by some real number $R$, then Bob can have an estimation $\vec y$ such that

Remark: In this case Bob queries for $2^n$ vectors. This result implies that is Bob is able to ask exponential number of questions, then it is hard to prevent information leakage. E.g., suppose $R = n / 400$, which is a relatively large number when $n$ is large, the theorem says that Bob can recover $99\%$ of bits in $\vec x$.

Proof: We say a vector $\vec y$ is consistent with a query result $r(\vec c)$ if

The strategy of Bob is to choose any $\vec y$ that is consistent with all $\vec c \in \{0, 1\}^n$. Such $\vec y$ exits, a special of which is given by $\vec y = \vec x$. It remains to prove that such an $\vec y$ satisfies the constraint.

Consider the special case of $\vec c = \vec x$,

By triangle inequality, it holds

Observe that $\vec x \cdot \vec x \ge \vec x \cdot \vec y$, which implies

Hence, $\vec y$ and $\vec x$ differ by at most $2R$ bits, on the non-zero dimensions of $\vec x$.

Let $\bar x$ be the bit-wise complement of $\vec x$. By similar arguments, we get

and $\vec x$ and $\vec y$ differ by at most $2R$ bits, on the zero dimensions of $\vec x$. It concludes that $|\vec x - \vec y | \le 4R$.

$\blacksquare$

What if Bob asks $O(n)$ questions? The following theorem states that if $Z$ is bounded by $O(\sqrt n)$, then Bob is able to have a good estimation of $\vec x$.

Theorem 2. If Bob is able to ask $\frac{n \log 2 + \ln n}{\log \frac{3}{2} - \log \lambda }$ queries, and $Z$ is bounded by $\alpha \sqrt n$, then Bob can obtains an estimation $\vec y$, such that

Proof: As before, a vector $\vec y$ is said to be consistent with a query result $r(\vec c)$ if

It suffices to find a sequence of vectors $\vec c_1, \vec c_2, ..., \vec c_k$ ($k$ is a value to be determined), such that

1. $k = O(n)$,
2. For any $\vec y$ with $|\vec x - \vec y| > (3e \frac{\alpha}{\lambda } )^2 \cdot n$, there exists at least one $\vec c_i$, such that $\vec y$ is not consistent with $r(\vec c_i)$, with high probability.

If Bob can find a sequence of query vectors with the specified properties, he can rule out any $\vec y$ such that $|\vec x - \vec y| > (3e \frac{\alpha}{\lambda } )^2 \cdot n$. Note that not every vector in $\{0, 1\}^n$ will be ruled out. At least $\vec x$ will remain. Bob can output any $\vec y$ that is not ruled out as his guess of $\vec x$.

It turns out that fining $\vec c_i$'s is simple: each $\vec c_i$ is sampled independently and uniformly at random from $\{0, 1\}^n$. It remains to prove that any $\vec y$ with $|\vec x - \vec y| > (3e \frac{\alpha}{\lambda } )^2 \cdot n$ will be ruled out with high probability.

For a fix $i$, consider the probability of

Lower bounding this probability is equivalent to upper bounding the probability

Lemma. For a value $l \in \mathbb{N}$,

We leave the proof of the lemma at the end of our discussion. It following by union bound that

Conditioning on that $|\vec x - \vec y| > (3e \frac{\alpha}{\lambda } )^2 \cdot n$, this probability is at most

The probability that this holds simultaneously for all $\vec c_i$ is therefore $(\frac{2\lambda }{3})^k$. Applying union bound over all $\vec y$ such that $|\vec x - \vec y| > (3e\alpha)^2 \cdot n$, we have an upper bound of failure probability

If we take $k = \frac{n \log 2 + \ln n}{\log \frac{3}{2} - \log \lambda }$, this probability becomes $\frac{1}{n}$.

Proof of the lemma: Without lose of generality, suppose that $l \ge 0$. Observe that $\vec x - \vec y$ is a vector in $\{-1, 0, 1 \}^n$. Denote $v = |\vec x - \vec y|$ be the number of non-zero dimensions in $\vec x - \vec y$. Further, let $v_+$ ($v_-$) be the number of positive (negative) dimensions in $\vec x - \vec y$. Hence, $v = v_+ + v_-$. As $\vec c_i$ is sampled uniformly from $\{0, 1\}^n$, we have

By Stirling's approximation,

Assuming that $\lfloor v / 2\rfloor \ge 1$, we get

$\square$

The idea behind Theorem 2 is more obvious if we study the scenario where $\vec x \in \{-1, 1\}^n$. For any estimation $\vec y \in \{-1, 1\}^n$, if $\vec c$ is sampled uniformly at random from $\{-1, 1\}^n$, then

If $|\vec x - \vec y| = O(\alpha^2 n)$, by anti-concentration property, the probability

equals to some constant. Equivalently, $\Pr[ |\vec c (\vec x - \vec y) | < \alpha \sqrt n]$ is some constant. By sampling $\vec c$ repeatedly, the probability that $|\vec c (\vec x - \vec y) | < \alpha \sqrt n$ holds for all sampled $\vec c$ decreases exponentially. That is why we can rule out any $\vec y$ such that $|\vec x - \vec y| = O(\alpha^2 n)$ with high probability.

Reference

[1] C. Dwork and A. Roth, “The Algorithmic Foundations of Differential Privacy,” Foundations and Trends in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2013