Simulating the view is insufficient when functionality is randomized

A simulator argument for privacy says that a party’s view of a protocol can be reproduced, in distribution, using only its input and its output as prescribed by the protocol. It is tempting to formalize this by comparing the distributions of the real and simulated views. For randomized functionalities, this is insufficient, even if the protocol produces exactly the right distribution of outputs. Not all expositions get this right (see Endnote).

Throughout, we consider perfect security against a single semi-honest party: parties follow the protocol, but may inspect everything they see. All equalities of distributions below are exact. Fix the full input vector $x$, and write $\mathbf Y$ and $\mathbf Y^*$ for the real and ideal output vectors. The view of party $i$ is its input, private random tape, and sequence of received messages:
$$
V_i=(x_i,R_i,M_{i,1},\ldots,M_{i,t}).
$$
Its outgoing messages and prescribed output can be computed from this tuple. A simulator $S_i$ for party $i$ receives only $x_i$ and $Y_i^*$, and uses independent randomness (i.e. independent of the ideal functionality) to produce
$$
\widetilde V_i=S_i(x_i,Y_i^*).
$$
The requirement is
$$
(\mathbf Y,V_i)\overset d=(\mathbf Y^*,\widetilde V_i),
$$
with one simulator for each party working for every $x$. The $Y_i^*$ supplied to the simulator is the component of the same ideal output vector appearing in this comparison.

Let’s show that it is insufficient to compare the view and the simulated view in isolation (i.e. omitting the outputs from the comparison). Consider randomized oblivious transfer. Bob supplies a choice bit $b$. The ideal functionality samples independent uniform strings
$$
K_0^*,K_1^* \in \{0,1\}^m,
$$
gives Alice $(K_0^*,K_1^*)$, and gives Bob $K_b^*$. Bob should learn nothing about the unchosen string.

Here is a completely insecure protocol: Alice samples independent uniform $K_0,K_1$, sends both to Bob, and outputs the pair. Bob outputs $K_b$. The vector of all outputs has exactly the ideal distribution. Omitting his empty random tape, Bob’s view is $(b,K_0,K_1)$. Given his ideal output $K_b^*$, a simulator can put that string in position $b$ and sample an independent uniform string $U$ for position $1-b$. The resulting view has exactly the real distribution. Alice’s view is also perfectly simulatable from her ideal output pair. So both views can be simulated, and the outputs have the right joint distribution. Yet Bob knows both strings! This demonstrates that simulating the view alone is insufficient.

The missing condition concerns the relationship between Bob’s view and Alice’s output. In the real execution, the unchosen string in Bob’s view equals Alice’s unchosen output with probability $1$. In the ideal execution, the simulator’s dummy string equals Alice’s actual unchosen output with probability $2^{-m}$. Indeed, no simulator given only $(b,K_b^*)$ can do better: $K_{1-b}^*$ remains independent and uniform.

There is, however, a useful circumstance in which explicitly adjoining the outputs is redundant. Suppose, for each fixed $x$, that the same deterministic map $G_x$ satisfies
$$
\mathbf Y=G_x(V_i),
\qquad
\mathbf Y^*=G_x(\widetilde V_i).
$$
Then equality of the view distributions implies
$$
(G_x(V_i),V_i)
\overset d=
(G_x(\widetilde V_i),\widetilde V_i),
$$
which is the required joint equality. The map may depend on the fixed inputs; the simulator need not know or evaluate it.

Endnote

There is an error on this point in Evans, Kolesnikov and Rosulek’s A Pragmatic Introduction to Secure Multi-Party Computation, §2.3.2, p. 22. After correctly including all parties’ outputs in Definition 2.2, the authors explain that this incorporates correctness, and state that it is not strictly necessary to include these values in the case of $C \ne \emptyset$ (where $C$ is the set of corrupt parties). The definition is fine; this proposed simplification is not.

On the other hand, Canetti directly addresses the same point as this blog post in Security and Composition of Multiparty Cryptographic Protocols (2000), §4.2, Remark 2, pp. 160–161, giving an example demonstrating that “secrecy and correctness cannot be separately required even for passive adversaries.” (Note that in Canetti, the adversary may output the whole view).

Leave a Reply

Your email address will not be published. Required fields are marked *