CRYPTO NEWS

About the definition of distinguishing advantage and computational indistinguishability

Given a polynomial-time adversary $A$ with binary output, the distinguishing advantage of $A$ with respect two games $G, H$ is defined as
$$
newcommand{adv}{mathbf{Adv}}
newcommand{pr}{mathbf{Pr}}
adv^textsf{dist}_{G,H}(A)=left|pr[A^G()=1]-pr[A^H()=1]right|.
$$

Where $A^G()$ denotes the adversary output when we run game $G$ with the adversary $A$.

Sometimes, people ask the ‘meaning’ of the definition, and usually the standard interpretation of the definition is something like that the binary output corresponds to the guess of $A$ about which of the two games it is in. For example, here 1 might indicate that $A$ is thinking it is in game $G$, and 0 might indicate $A$ is thinking it is in game $H$. Then, the advantage is the probability of correct guesses, penalized by subtracting the probability of wrong guesses.

But we can also write the advantage as $Delta(A^G, A^H)$, where $Delta(X,Y)$ is the statistical distance (total variation distance) between two random variables $X, Y$, because $A$ is an adversary with binary output:
$$
begin{aligned}
Delta(A^G, A^H)
&=frac{1}{2}sum_{b=0}^1left|pr[A^G()=b]-pr[A^H()=b]right|\
&=frac{1}{2}left(left|pr[A^G()=1]-pr[A^H()=1]right|right.\
&qquadleft.+left|pr[A^G()=0]-pr[A^H()=0]right|right)\
&=frac{1}{2}left(left|pr[A^G()=1]-pr[A^H()=1]right|right.\
&qquadleft.+left|(1-pr[A^G()=1])-(1-pr[A^H()=1])right|right)\
&=left|pr[A^G()=1]-pr[A^H()=1]right|.
end{aligned}
$$

And this ‘interpretation’ directly says that when the advantage is negligible, the output behavior of $A$ does not change much when the games $G$ and $H$ are switched. We might argue that distinguishing two situations means behaving differently according to the given situation. If the behavior does not (or cannot) change much between the situations for anybody, that means the two situations are indistinguishable.

But then this naturally suggests an obvious generalization: we might release the restriction that $A$ is an adversary with binary output, and instead allow arbitrary output. When we define computational indistinguishability, $A$ is a polynomial-time algorithm, so the output of $A$ can be encoded as a bitstring in ${0,1}^n$, for some polynomially large $n$. We can still define the distinguishing advantage of $A$ with respect to two games $G, H$ as $Delta(A^G, A^H)$, and we might say that $G$ and $H$ are computationally indistinguishable if for any polynomial-time adversary $A$ (with arbitrary output), the advantage is negligible.

I think this extension is at least very natural, and perhaps might be useful in some situations as well. But I’m not sure if this definition of computational indistinguishability is equivalent to the standard one. Certainly, this definition is stronger so it implies the standard one. But, would the standard definition imply the stronger one?

Essentially, an equivalence proof should show existence of a polynomial-time distinguisher $B$ with binary output such that $Delta(B^G, B^H)$ is non-negligible, from a polynomial-time adversary $A$ with arbitrary output when $Delta(A^G, A^H)$ is non-negligible.

One direction I thought about was that, when the output of $A$ is in ${0,1}^n$ for some polynomially large $n$, for each $rin{0,1}^n$, we may define $B_r$ as the algorithm which outputs $rcdot x$, the inner product modulo 2 of $r$ and $x$, when $x$ is the output of the algorithm $A$.

So my question is: when $Delta(A^G, A^H)$ is non-negligible, should there be any $r$ such that $Delta(B_r^G, B_r^H)$ is non-negligible? Or, is there any other way to establish the equivalence of the two definitions?

(The above approach essentially asks: if $X, Y$ are random variables over ${0,1}^n$, and if $Delta(rcdot X, rcdot Y)$ is negligible for any $rin{0,1}^n$, is $Delta(X,Y)$ negligible as well?)

About the definition of distinguishing advantage and computational indistinguishability

Shopping cart
There are no products in the cart!
Continue shopping
0