Score:1

What does the syntax Pr[D = 1] mean?

fr flag

I'm looking at this PDF to understand the hybrid argument: http://www.cs.columbia.edu/~tal/4261/F14/hybrid.pdf

The first few lines go as follows:

Suppose you have two oracles, or input distributions, $O_0,O_1$, and you want to prove that they're in-distinguishable, i.e. for every probabilistic, polynomial-time (PPT) distinguisher, D, the following must hold: $$ |Pr[D^{O_1} = 1] - Pr[D^{O_0} = 1]| = negl. $$

I'm trying to understand what $Pr[D^{O_1} = 1]$ means. Is it the probability the distinguisher is correct?

Score:2
sa flag

$Pr[D^{O_i} = 1]$ is the probability that the distinguisher outputs 1 given the actual oracle is $O_i.$

us flag
I don't think it's right to say that "distinguisher outputs 1" means "distinguisher is correct". I think that "correct" distinguisher output changes when the oracle changes, but we are comparing the probability of "output 1" in the presence of two different oracles.
Foobar avatar
fr flag
@Mikero, so if I understand correctly if the distinguisher outputs 1 it thinks the oracle is O1, and if it outputs 0 it thinks the oracle is O0. And the claim is: the distinguisher should be equally likely to output 1 regardless of whether the actual oracle is O1 or O1
Score:1
es flag

$\newcommand{\pr}{\mathbf{Pr}}$ Another possible intuitive interpretation would be: this means that the behavior of $D$ does not change perceptively. Suppose $D$ outputs 0 or 1. Then, the output behavior of $D$ can be summarized by the probability distribution of $D$'s output, and this can be written as a vector $(\pr[D=0], \pr[D=1])$.

Consider the L1 distance between the distribution vectors with respect to the oracles $O_0, O_1$: $$|\pr[D^{O_1}=0]-\pr[D^{O_0}=0]|+|\pr[D^{O_1}=1]-\pr[D^{O_0}=1]|.$$

Since $\pr[D^{O_1}=0]=1-\pr[D^{O_1}=1]$ and $\pr[D^{O_0}=0]=1-\pr[D^{O_0}=1]$, plugging these into the L1 distance, we get $$2|\pr[D^{O_1}=1]-\pr[D^{O_0}=1]|.$$

So, the given condition is that the output probability distribution doesn't change much, when one swaps $O_0$ and $O_1$.

This makes sense: to be able to distinguish two situations means to be able to act differently according to the given situation. If someone's behavior never changes (and cannot change) even if you switch one from the other, it means he/she doesn't recognize the switch.

What if $D$ outputs not only a bit but something more? Say, $D$ could output a number. Even in that case, if $D$ behaves differently when the oracle is switched, some aspect of the output must change. For example, say, the MSB of the output of $D$ could change. In that case, we may define another distinguisher $D'$ which runs $D$, and then only outputs the MSB of $D$'s output. So, if there's no such $D'$, then there's no such $D$. So more or less without loss of generality, we may consider only distinguishers with binary output when defining indistinguishability.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.