Skip to main content
added 233 characters in body
Source Link
Ariel
  • 13.6k
  • 1
  • 21
  • 39

$$ \Pr[A(x)=1]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr[A(x)=1 | \text{A requested bits $i_1,...,i_j$}]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr\left[A\left(x_{i_1,i_2,...,i_j}\right)=1\right]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}] $$

Here you already see that if $A$ is non adaptive this becomes immediate, as only one summand is non zero, and $A(x_{i_1},...,x_{i_j})$ has the same distribution as $A(U_j)$. If one considers randomized $A$ then change this argument to claim that the bits requested do not depend on the input, and thus the probability of requesting a certain set of indices does not depend on the distribution of the input. For the adaptive case, try the following. Denote by $a_i$ the index of the $i'th$ bit requested by $A$.

$$ \Pr[\text{A requested bits $i_1,...,i_j$}]=\Pr\left[\bigwedge\limits_{l=1}^j a_l=i_l\right]=\Pr\left[a_j=i_j \Bigg| \bigwedge\limits_{l=1}^{j-1}a_l=i_l\right]\cdot \Pr\left[a_{j-1}=i_{j-1} \Bigg| \bigwedge\limits_{l=1}^{j-2}a_l=i_l\right]\cdot...\cdot\Pr\left[a_2=i_2 |a_1=i_1\right]\cdot\Pr[a_1=i_1]. $$

Note that in each term the probability is both over the internal randomness of $A$ and the randomness of the input $x$ (which is implicit in the above). You can now prove by induction that in each multiplier, you can switch $x$ with a uniformly distributed string. More formally, for all $1\le l\le j$, the random variable $a_l$ conditioned on $a_1,...,a_{l-1}$ has the same distribution as $a_l$ when $x$ is uniformly random. Finally, plug this back to the above sum, and now every occurence of the input $x$ was switched by a uniformly distributed string.

$$ \Pr[A(x)=1]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr[A(x)=1 | \text{A requested bits $i_1,...,i_j$}]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr\left[A\left(x_{i_1,i_2,...,i_j}\right)=1\right]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}] $$

Here you already see that if $A$ is non adaptive this becomes immediate, as only one summand is non zero, and $A(x_{i_1},...,x_{i_j})$ has the same distribution as $A(U_j)$. For the adaptive case, try the following. Denote by $a_i$ the index of the $i'th$ bit requested by $A$.

$$ \Pr[\text{A requested bits $i_1,...,i_j$}]=\Pr\left[\bigwedge\limits_{l=1}^j a_l=i_l\right]=\Pr\left[a_j=i_j \Bigg| \bigwedge\limits_{l=1}^{j-1}a_l=i_l\right]\cdot \Pr\left[a_{j-1}=i_{j-1} \Bigg| \bigwedge\limits_{l=1}^{j-2}a_l=i_l\right]\cdot...\cdot\Pr\left[a_2=i_2 |a_1=i_1\right]\cdot\Pr[a_1=i_1]. $$

Note that in each term the probability is both over the internal randomness of $A$ and the randomness of the input $x$ (which is implicit in the above). You can now prove by induction that in each multiplier, you can switch $x$ with a uniformly distributed string. More formally, for all $1\le l\le j$, the random variable $a_l$ conditioned on $a_1,...,a_{l-1}$ has the same distribution as $a_l$ when $x$ is uniformly random. Finally, plug this back to the above sum, and now every occurence of the input $x$ was switched by a uniformly distributed string.

$$ \Pr[A(x)=1]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr[A(x)=1 | \text{A requested bits $i_1,...,i_j$}]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr\left[A\left(x_{i_1,i_2,...,i_j}\right)=1\right]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}] $$

Here you already see that if $A$ is non adaptive this becomes immediate, as only one summand is non zero, and $A(x_{i_1},...,x_{i_j})$ has the same distribution as $A(U_j)$. If one considers randomized $A$ then change this argument to claim that the bits requested do not depend on the input, and thus the probability of requesting a certain set of indices does not depend on the distribution of the input. For the adaptive case, try the following. Denote by $a_i$ the index of the $i'th$ bit requested by $A$.

$$ \Pr[\text{A requested bits $i_1,...,i_j$}]=\Pr\left[\bigwedge\limits_{l=1}^j a_l=i_l\right]=\Pr\left[a_j=i_j \Bigg| \bigwedge\limits_{l=1}^{j-1}a_l=i_l\right]\cdot \Pr\left[a_{j-1}=i_{j-1} \Bigg| \bigwedge\limits_{l=1}^{j-2}a_l=i_l\right]\cdot...\cdot\Pr\left[a_2=i_2 |a_1=i_1\right]\cdot\Pr[a_1=i_1]. $$

Note that in each term the probability is both over the internal randomness of $A$ and the randomness of the input $x$ (which is implicit in the above). You can now prove by induction that in each multiplier, you can switch $x$ with a uniformly distributed string. More formally, for all $1\le l\le j$, the random variable $a_l$ conditioned on $a_1,...,a_{l-1}$ has the same distribution as $a_l$ when $x$ is uniformly random. Finally, plug this back to the above sum, and now every occurence of the input $x$ was switched by a uniformly distributed string.

Source Link
Ariel
  • 13.6k
  • 1
  • 21
  • 39

$$ \Pr[A(x)=1]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr[A(x)=1 | \text{A requested bits $i_1,...,i_j$}]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr\left[A\left(x_{i_1,i_2,...,i_j}\right)=1\right]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}] $$

Here you already see that if $A$ is non adaptive this becomes immediate, as only one summand is non zero, and $A(x_{i_1},...,x_{i_j})$ has the same distribution as $A(U_j)$. For the adaptive case, try the following. Denote by $a_i$ the index of the $i'th$ bit requested by $A$.

$$ \Pr[\text{A requested bits $i_1,...,i_j$}]=\Pr\left[\bigwedge\limits_{l=1}^j a_l=i_l\right]=\Pr\left[a_j=i_j \Bigg| \bigwedge\limits_{l=1}^{j-1}a_l=i_l\right]\cdot \Pr\left[a_{j-1}=i_{j-1} \Bigg| \bigwedge\limits_{l=1}^{j-2}a_l=i_l\right]\cdot...\cdot\Pr\left[a_2=i_2 |a_1=i_1\right]\cdot\Pr[a_1=i_1]. $$

Note that in each term the probability is both over the internal randomness of $A$ and the randomness of the input $x$ (which is implicit in the above). You can now prove by induction that in each multiplier, you can switch $x$ with a uniformly distributed string. More formally, for all $1\le l\le j$, the random variable $a_l$ conditioned on $a_1,...,a_{l-1}$ has the same distribution as $a_l$ when $x$ is uniformly random. Finally, plug this back to the above sum, and now every occurence of the input $x$ was switched by a uniformly distributed string.