Simulation based proofs, what am I missing?

Question

In the example given by in the top answer of Simulation based proofs: Simple examples claims that this is insecure the semi-honest, and I need assistance in where I am failing to reason why that this is true.

By definition (at least put simply to my understanding), a protocol is secure under this simulation based definition if the output views of the simulator and the adversary are computationally indistinguishable.

In the case where $x_2$ is 0, the output of the computation is always 0. And in this case, the simulator has to guess the value of $x_1$, namely it can take either value of 0 or 1. In the case that the simulator guesses $x_1$ correctly, it's obvious that these views are identical. However, what I fail to understand is in the case the simulator guesses $x_1$ wrong, how are these views distinguishable? As far as I can see, no distinguisher should be able to tell if the view of $(1,0,0)$ with the message $1$ from $P_1$ was the real/ideal interaction, or if $(0,0,0)$ with the message $0$ from $P_1$ was the real/ideal interaction.

Answer 1

Basically, what you are missing is that the real view for a given input pair must be indistinguishable from the simulated view for the same input pair.

Remember that, put simply, the requirement is that the view of each party can be simulated based only on its input and output. So, in the case of $P_2$, for each pair of input bits the simulator is given the input $y$ of $P_2$ and the output bit $x \wedge y$, where $x$ is the input bit of $P_1$, and must simulate the view $(y,x)$ of $P_2$ (input and received message). Now, consider the two cases where $y = 0$. In both those cases, the simulator has input $(0,0)$, so its output in both cases will be the same. But the real view is not the same ($x$ can be $0$ or $1$), so the simulator, no matter what it does, can't possibly simulate both views.

Concretely, consider for example the following simulator $S_2$. On input $(y,w)$ (where $w = x \wedge y$),

• if $y = 0$, chose $b \gets \{0,1\}$ randomly and output $(0,b)$;
• if $y = 1$, output $(1,w)$.

Recall also that for all input pairs $(x,y)$, we have $\mathsf{view}_2(x,y) = (y,x)$. Consider now the following distinguisher $D$. $D$ gets as input a pair of bits $(a,b)$; if $(a,b) = (0,0)$, $D$ outputs $1$, and otherwise $D$ outputs $0$. The question is, if the inputs to the parties are $(0,0)$, what does $D$ output if we give it a real vs. simulated view of $P_2$? A real view will be $(0,0)$, so $D$ will always output $1$. A simulated view will be $(0,0)$ or $(0,1)$ each with probability $1/2$, so $D$ will output $1$ with probaility only $1/2$, hence the two probability ensembles (real and simulated views) are distinguishable.