CSE442T Introduction to Cryptography (Lecture 24)

Chapter 7: Composability

Continue on zero-knowledge proof

Let $X=(G_0,G_1)$ and $y=\sigma$ permutation. $\sigma(G_0)=G_1$.

$P$ is a random $\Pi$ permutation and $H=\Pi(G_0)$.

$P$ sends $H$ to $V$.

$V$ sends a random $b\in\{0,1\}$ to $P$.

$P$ sends $\phi=\Pi$ if $b=0$ and $\phi=\Pi\phi^{-1}$ if $b=1$.

$V$ outputs accept if $\phi(G_0)=G_1$ and reject otherwise.

Message transfer protocol

The message transfer protocol is defined as follow.

Construct a simulator $S(x,z)$ based on $V^*(x,z)$.

Pick $b'\gets\{0,1\}$.

$\Pi\gets \mathbb{P}_n$ and $H\gets \Pi(G_0)$.

If $V^*$ sends $b=b'$, we send $\Pi$/ output $V^*$‘s output

Otherwise, we start over. Go back to the beginning state. Do this until “n” successive accept.‘

Zero-knowledge definition (Cont.)

In zero-knowledge definition. We need the simulator $S$ to have expected running time polynomial in $n$.

Expected two trials for each “success”

2*n running time (one interaction)

If $G_0$ and $G_1$ are indistinguishable, $H_s=\Pi(G_{b'})$ same distribution as $H_p=\Pi(G_0)$. (random permutation of $G_1$ is a random permutation of $G_0$)