Skip to main content
Fix delimiter orientation.
Source Link
Squeamish Ossifrage
  • 49.9k
  • 3
  • 123
  • 232

A probabilistic distinguisher is still a deterministic function of its input and random coins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins (importantly: independent of $X$/$Y$).

But:

\begin{align} \Delta\Big( (X,R), (Y,R) \Big) &= \frac12 \sum_{\alpha,r} \Big| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \Pr[R=r] \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \underbrace{\sum_r \Pr[R=r]}_{=1} \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \\ &= \Delta(X,Y) \end{align}\begin{align} \Delta\Bigl( (X,R), (Y,R) \Bigr) &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Bigr| \\ &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Bigr| \\ &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \Pr[R=r] \\ &= \frac12 \sum_{\alpha} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \;\underbrace{\sum_r \Pr[R=r]}_{=1} \\ &= \frac12 \sum_{\alpha} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \\ &= \Delta(X,Y) \end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.

A probabilistic distinguisher is still a deterministic function of its input and random coins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins (importantly: independent of $X$/$Y$).

But:

\begin{align} \Delta\Big( (X,R), (Y,R) \Big) &= \frac12 \sum_{\alpha,r} \Big| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \Pr[R=r] \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \underbrace{\sum_r \Pr[R=r]}_{=1} \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \\ &= \Delta(X,Y) \end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.

A probabilistic distinguisher is still a deterministic function of its input and random coins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins (importantly: independent of $X$/$Y$).

But:

\begin{align} \Delta\Bigl( (X,R), (Y,R) \Bigr) &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Bigr| \\ &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Bigr| \\ &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \Pr[R=r] \\ &= \frac12 \sum_{\alpha} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \;\underbrace{\sum_r \Pr[R=r]}_{=1} \\ &= \frac12 \sum_{\alpha} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \\ &= \Delta(X,Y) \end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.

added 39 characters in body
Source Link
Mikero
  • 15.4k
  • 2
  • 37
  • 60

A probabilistic distinguisher is still a deterministic function of its input and random tapecoins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins (importantly: independent of $X$/$Y$).

But:

\begin{align} \Delta\Big( (X,R), (Y,R) \Big) &= \frac12 \sum_{\alpha,r} \Big| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \Pr[R=r] \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \underbrace{\sum_r \Pr[R=r]}_{=1} \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \\ &= \Delta(X,Y) \end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.

A probabilistic distinguisher is still a deterministic function of its input and random tape. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins.

But:

\begin{align} \Delta\Big( (X,R), (Y,R) \Big) &= \frac12 \sum_{\alpha,r} \Big| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \Pr[R=r] \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \underbrace{\sum_r \Pr[R=r]}_{=1} \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \\ &= \Delta(X,Y) \end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.

A probabilistic distinguisher is still a deterministic function of its input and random coins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins (importantly: independent of $X$/$Y$).

But:

\begin{align} \Delta\Big( (X,R), (Y,R) \Big) &= \frac12 \sum_{\alpha,r} \Big| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \Pr[R=r] \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \underbrace{\sum_r \Pr[R=r]}_{=1} \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \\ &= \Delta(X,Y) \end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.

Source Link
Mikero
  • 15.4k
  • 2
  • 37
  • 60

A probabilistic distinguisher is still a deterministic function of its input and random tape. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins.

But:

\begin{align} \Delta\Big( (X,R), (Y,R) \Big) &= \frac12 \sum_{\alpha,r} \Big| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Big| \\ &= \frac12 \sum_{\alpha,r} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \Pr[R=r] \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \underbrace{\sum_r \Pr[R=r]}_{=1} \\ &= \frac12 \sum_{\alpha} \Big| \Pr[X=\alpha] - \Pr[Y=\alpha]\Big| \\ &= \Delta(X,Y) \end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.