About the definition of distinguishing advantage and computational indistinguishability

Question

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}^1\left|\pr[A^G()=b]-\pr[A^H()=b]\right|\\ &=\frac{1}{2}\left(\left|\pr[A^G()=1]-\pr[A^H()=1]\right|\right.\\ &\qquad\left.+\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.\\ &\qquad\left.+\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 $r\in\{0,1\}^n$, we may define $B_r$ as the algorithm which outputs $r\cdot 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(r\cdot X, r\cdot Y)$ is negligible for any $r\in\{0,1\}^n$, is $\Delta(X,Y)$ negligible as well?)

---

@Mikero commented that allowing outputs of polynomially many bits would make this definition equal to the statistical indistinguishability, since the adversary may just output its entire view.

But, could this definition be salvaged somehow? For example, what would happen if we restrict to adversaries with outputs of logarithmic length?

Answer 1

A few things to mention

1. For certain situations, the restriction to binary-output adversaries is (known to be) without loss of generality. The data-processing inequality gives that $\Delta(f(X), f(Y)) \leq \Delta(X, Y)$ for any random variables $X, Y$, and there exists $f$ such that this is tight.

2. More generally, a (unified) definition of advantage for adversaries that output $k$ bits (for $k\in [1,n]$) is given here. The most interesting cases are $k = 1$ (where one wants it to scale with $\Delta(\cdot, \cdot)$ --- interestingly though, the scaling identified is quadratic $\Delta(\cdot,\cdot)^2$, rather than linear), and $k = n$, say in secret key recovery games, where the adversary outputs a full $n$ bit secret, and one wants the advantage to be the success probability in recovering the secret.

3. The idea of "reducing" an adversary with $n$-bit outputs to an adversary with $1$-bit outputs is investigated here. This only examines $k$-bit outputs for $k\in\{1,n\}$ though, so does not handle $\log(n)$ bit outputs (as the comments discuss).

When investigating this, there are a number of "standard" paradoxes one likely wants to ensure are resolved by whatever definition one settles on. Both papers discuss them though, so I defer to them.