$\Theta(2^k \lg n)$ queries are necessary and sufficient.
Algorithm
Define $I = \{i_1,\dots,i_k\}$. Our goal is to recover $I$. Given $x$, define $Z(x) = \{i : x_i = 0\}$. For each $x$ where $f(x)=0$, we learn that $Z(x) \subseteq I$. This suggests the following algorithm:
- Set $J := \{1,2,\dots,n\}$.
- For each $x$ in the input such that $f(x)=0$, set $J := J \cap Z(x)$.
- Output $J$.
Analysis: It's guaranteed that this algorithm will output a set $J$ satisfying $I \subseteq J$. Can we ensure that $I=J$? Well, if we have $c \lg n$ values of $x$ where $f(x)=0$, then for any fixed $j \notin I$, $\Pr[j \in J] \le 1/2^{c \lg n} = 1/(2^c n)$; then by a union bound, $\Pr[J \ne I] \le 1/2^c$. So, the probability that this produces the wrong output can be made exponentially small in $c$, as long as we have $c \lg n$ values of $x$ where $f(x)=0$.
Moreover, given $m$ pairs, we expect $m/2^k$ of them to have $f(x)=0$. So, if we have $c \cdot 2^k \lg n$ pairs, we expect $c \lg n$ where $f(x)=0$. Therefore, $O(2^k \lg n)$ pairs suffice to ensure that this algorithm will give the correct answer (except with negligible probability of failure).
Lower bound
This is the best we can do. We can extend the information-theoretic lower bound in the question.
Let's start by showing that $\Omega(2^k)$ pairs are needed. For a random $x$, we have $\Pr[f(x)=0] = 1/2^k$. Therefore, we obviously need $\Omega(2^k)$ pairs to have a good chance of observing at least one pair where $f(x)=0$. With $o(2^k)$ pairs, there's an overwhelming probability that all pairs satisfy $f(x)=1$, in which case we have learned nothing about $f$. So, $\Omega(2^k)$ pairs are needed.
We can improve this lower bound a bit. Call $x$ good if it satisfies $f(x)=0$. Suppose we have to examine $p$ pairs before we see the first good value of $x$. Once we see our first good value of $x$, how many bits of information have we learned about $f$? Only $\lg p$ bits (because one of those $p$ pairs yields 0 and all the rest are 1; there are $p$ ways to select one of them to be 0). It takes about $2^k$ pairs to see the first good value of $x$. So, after observing $2^k$ pairs, we expect to learn about $k$ bits of information about $f$. In general, each good value of $x$ gives us about $k$ bits of information about $f$, and we need to see about $2^k$ pairs per good value obtained. Now as described in the question, we need $\Omega(k \lg n)$ bits to specify $f$ uniquely. Therefore, we need $\Omega(\lg n)$ good values of $x$, so we need $\Omega(2^k \lg n)$ pairs in total.
This gives a lower bound that matches the performance of the algorithm above, to within a constant factor. Therefore, the algorithm above is asymptotically optimal.
