5
$\begingroup$

Consider a probability distribution $D$ over $n$ bit strings. Consider a next bit predictor $A$ as follows. \begin{equation} \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}. \end{equation} Here, $X_i$ indicates the $i^{\text{th}}$ bit of $X$. Consider that this predictor exists. Intuitively, if I understand correctly, this means that there should be a "gap" between the bit $X_k$ and the bit $\overline{X_k}$ (complement of $X_k$); otherwise the algorithm $A$ should not exist. In other words, I think that the existence of an algorithm $A$ implies \begin{equation} \underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \geq \frac{1}{\text{poly}(n)}, \end{equation} or something similar to this, with respect to the statistical property of the $k^{\text{th}}$ bit. I couldn't prove this mathematically.

Is my intuition correct and can it be made mathematically rigorous?


I tried proving my intuition, but I am still stuck. Here is my attempt.

We can show that the fact that $A$ exists and acts as \begin{equation} \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}. \end{equation} implies \begin{equation} \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}] \geq \frac{1}{\text{poly}(n)}. \end{equation}

Now, I am trying to show \begin{equation} \underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \\ \geq \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}]. \end{equation}

In other words, the proof reduces to proving \begin{equation} \underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \\ = \max_{A}\left( \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}]\right). \end{equation}

If I start with the contrapositive of the statement, I end up in the same place. I think I am missing something subtle. In spirit, the statement our proof reduces to is similar to a very similar-looking result relating total variation distance between two distributions with distinguishability bias of the best algorithm (like this answer). But also, it is not quite the same: as we only have one distribution now, not two, and retracing the same steps does not work.

$\endgroup$
5
  • $\begingroup$ You are essentially correct, if I am not misunderstanding you. However, the reverse is not true, at least not shown to be true. While existence of such a predictor requires there be significant gap in probability in the $k$th bit given $k-1$ bits, such a gap has not been shown to be a sufficient condition for th predictor $A$ to exist. $\endgroup$ – Manish Adhikari Feb 21 at 7:23
  • $\begingroup$ I couldn't mathematically show that the existence of such a predictor requires a gap in the probability of the $k$th bit given $k-1$ bits. Might you elaborate on the math in a separate answer? $\endgroup$ – BlackHat18 Feb 21 at 8:08
  • 1
    $\begingroup$ crypto.stackexchange.com/questions/73108/… has some answers, its about how to show that statistical closeness implies computational indistinguishability. You can use this for reference $\endgroup$ – Manish Adhikari Feb 22 at 7:21
  • $\begingroup$ Interesting question! Something I don't quite understand: are the $X_i$ i.i.d $\sim D$ or or is $X_1^n \sim D$ and the question is about the relation between $X_1^k$ and $X^{k+1}$ ? $\endgroup$ – Marc Ilunga Feb 24 at 8:32
  • $\begingroup$ It is the latter. $\endgroup$ – BlackHat18 Feb 24 at 10:06
4
$\begingroup$

[SEE UPDATE BELOW] This is a very interesting question. Basically what it means is that if there exists a next-bit predictor, then there is a canonical distinguisher $D$ that outputs the $k$th bit and does nothing else. This is a good distinguisher since the $k$th bit equals 1 with probability that is polynomially bounded away from a random bit. I find this intuitively appealing and was first surprised. However, it does make sense.

As a sanity check, let's see what would happen if on the extreme: $$ Pr_{X\sim D}[X_k=1 \mid X_1X_2\ldots X_{k-1}] = Pr_{X\sim D}[X_k=0 \mid X_1X_2\ldots X_{k-1}]. $$ This would mean that $X_k$ is actually independent of $X_1,\ldots,X_{k-1}$ and is a random bit. In such a case, it is clear that $A$ could only predict the next bit with probability $\frac12$. As a result, I think that this could be proven in the contrapositive.

I won't do all of this here; there is good value in you working it out. In order to get the direction, I propose that you look at the proof of equivalence of next-bit unpredictability and pseudo randomness. One place to see this is Section 7.3.2 of this chapter on Pseudorandomness by Salil Vadhan.

Let me know if it doesn't work out from here.

==================================

I'm leaving the above for the didactic value, but I'm no longer sure that this is correct. The problem is the conditioning. In particular, once we condition on $X_1,\ldots,X_{k-1}$, then we are completely changing the probability space. (General recommendation - it's really easy to get conditioning wrong so stay away if you can. This was a recommendation given to me by my advisor. You can't always avoid it, but you need to be really careful.) In more detail, it could be that for \emph{many} given $X_1,\ldots,X_{k-1}$, the $k$th bit $X_k$ is polynomially biased away from $1/2$. The problem is that you don't know how to recognize the prefixes where this holds. Of course, this means that it can't happen with high probability (or a non-uniform distinguisher could hold some prefixes as advice). I think part of the confusion is what it even means to sample a full $X$ and then condition on $X_1,\ldots,X_{k-1}$. I think what you mean is that: for every $X_1,\ldots,X_{k-1}$, the probability of $X_k=1$ when the sample of $X$ has the given prefix of $X_1,\ldots,X_{k-1}$ is bounded away from $1/2$. I don't think this would be correct. If you mean something else, then it's worth thinking about.

I guess the important question is what you are trying to show and why, or possibly it's just understanding (which is good within itself).

$\endgroup$
6
  • $\begingroup$ Do we need absolute value here? $\endgroup$ – kelalaka Feb 21 at 13:46
  • $\begingroup$ Absolutely. But that's not an issue and doesn't make things any harder. $\endgroup$ – Yehuda Lindell Feb 21 at 14:29
  • $\begingroup$ Am I missing something here? A probability can't be negative and we have equality there, not a minus. $\endgroup$ – kelalaka Feb 21 at 14:36
  • 1
    $\begingroup$ @kelaka Sorry, my bad. No absolute value is needed in my answer with equality. Absolute value is needed when doing the actual analysis where the gap is assumed to be negligible (or non-negligible if doing the contrapositive). $\endgroup$ – Yehuda Lindell Feb 22 at 14:14
  • $\begingroup$ Thanks for the links! I tried doing it but I think I am still stuck and missing something subtle. I showed my steps by editing the original question. $\endgroup$ – BlackHat18 Feb 23 at 15:30
1
$\begingroup$

I think there is the use of intuition in the proof (Similar proof to statistical closeness implies computational indistinguishability). It uses the fact that a best case scenario for the adversary (even computationally unbounded ones) would be if it could efficiently and deterministically calculate the probability $Pr[X_k|X_1,X_2..X_{k-1}]$. The distinguisher then outputs $1$ if $p_{1}>p_{0}$, $0$ otherwise. You can now use basic probability calculation to show that the distinguisher still gets it correct with the probability only negligibly better than random guess if $|p_1 - p_0|$ is negligible. Another strategy would be more probabilistic, output 1 with probability equal to $p_{1}$ but since this is independent of whether $X_{k}$ is $0$ or $1$, advantage is still equal to one above.

Unfortunately, I don't have any mathematical proof that this is best an adversary can do but it is the fact that these probabilities are the best any computationally unbounded adversary can theoretically calculate given only $X_1,X_2..X_{k-1}$.

$\endgroup$
1
+50
$\begingroup$

I am not sure this is correct but I'll give it a try... More specifically instead of relating the conditional probabilities, I will rather try and bound conditional entropies i.e $H(X_k | X_1^{k-1})$. I don't know yet if the bound on probabilities directly follows from this but I will try and argue it informally.

Notation $X_k^n = (X_k, X_{k+1},\ldots,X_n)$. For simplicity we write $X^n = X_1^n$.

Problem statement: We are given $X^n \sim \text{ } D$. We are also given an adversary $\mathcal A$ that produces a guess $\tilde X_{k} = \mathcal A(X^{k-1})$ and $P[\tilde X_k = X_k] \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}$. We want to show that:

\begin{equation} \underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \geq \frac{1}{\text{poly}(n)}, \end{equation}

Attempt 1: We use Fano's inequality


Fano's inequality: Let $U$ and $\tilde U$ be random variables taking values in the set $\mathcal U$. We think of $\tilde U$ as a guess about $U$. Let the error probability defined as $P_e = Pr[U \neq \tilde U]$, then we have $$ H_b(Pe) + Pe \log(|\mathcal U| - 1) \geq H(U|\tilde U)$$ Where $H_b(p)$ is the binary entropy of a Bernoulli RV with $P(1) = p$

We apply this to $X_k$ and $\tilde X_k$: First the probability of error $P_e^{\mathcal A} = \frac{1}{2} - \frac{1}{\text{poly}(n)}$. We then obtain $ H(X_k | X_{k-1}) \leq H(X_k |\tilde X_k) \leq H_b(P_e^{\mathcal A}) = H_b(\frac{1}{2} - \frac{1}{\text{poly}(n)})$. The first inequality from $\tilde X_k = \mathcal A(X^{k-1})$.

Now if we assume towards contraction that \begin{equation} \underset{X \sim D}{\text{Pr}}[X_k~|~X_1,X_2,\ldots,X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1,X_2,\ldots,X_{k-1}] \approx \text{negl}(n), \end{equation}

Then (very informal): $H(X_k | X^{k-1})$ is the average of entropies of almost uniform Bernouilli distributions therefore $H(X_k | X_{k-1}) \leq H(X_k |\tilde X_k) \leq H_b(P_e^{\mathcal A}) = H_b(\frac{1}{2} - \frac{1}{\text{poly}(n)})$ would not hold.

$\endgroup$
5
  • $\begingroup$ How do I see see that $H(X_k | X^{k-1})$ is the average of entropies of almost uniform Bernoulli distributions? $\endgroup$ – BlackHat18 Feb 27 at 4:38
  • $\begingroup$ I believe that it follows from assuming that there is no "gap" between $X_k$ and $\bar X_k$ when conditioned on $X_{k-1}$. This could be restated as $P_{X_k | X_{k-1}} \sim$ Beroulli$(\frac{1}{2} + \text{negl}(n))$. Which is almost uniform. $\endgroup$ – Marc Ilunga Feb 27 at 10:02
  • $\begingroup$ I don't believe that you can use bounds on entropy. In the computational setting, the real entropy can be zero, and the statistical gap between indistinguishable distributions can be huge. You can use pseudoentropy, but I don't know if analogs of these bounds hold in that case. $\endgroup$ – Yehuda Lindell Feb 28 at 11:02
  • $\begingroup$ @YehudaLindell, would you mind developing a bit on the entropy issues in the computational setting? As stated at the beginning of my answer I also had doubts about the answer... On the other hand, however, it seems like we are making statements about probabilities only and for Fano's inequality, there's normally no restriction on the adversary computing power. But yeah I would definitely be interested in identifying flaws here $\endgroup$ – Marc Ilunga Mar 1 at 11:05
  • $\begingroup$ At a very high level, a distribution X has pseudoentropy $k$ if there exists a distribution Y that has entropy $k$ such that $X$ and $Y$ are indistinguishable. Pseudoentropy was introduced in the famous HILL paper (PRGs from any OWF). The best place to learn about it is this tutorial by Haitner and Vadhan: cs.tau.ac.il/~iftachh/papers/ManyEntInOWF/… $\endgroup$ – Yehuda Lindell Mar 1 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.