CSE442T Introduction to Cryptography (Lecture 23)

Chapter 7: Composability

Zero-knowledge proofs

Let the Prover Peggy and the Verifier Victor.

Peggy wants to prove to Victor that she knows a secret $x$ without revealing anything about $x$. (e.g. $x$ such that $g^x=y\mod p$)

Zero-knowledge proofs protocol

The protocol should satisfy the following properties:

• Completeness: If Peggy knows $x$, she can always make Victor accept.
• Soundness: If a malicious Prover $P^*$ does not know $x$, then $V$ accepts with probability at most $\epsilon(n)$.
• Zero-knowledge: After the process, $V^*$ (possibly dishonest Verifier) knows no more about $x$ than he did before.

[The interaction could have been faked without $P$]

Example: Hair counting magician

“Magician” who claims they can count the number of hairs on your head.

secret info: the method of counting.

Repeat the following process for $k$ times:

1. “Magician” tells the number of hairs
2. You remove some hair $b\in \{0,1\}$ from your head.
3. “Magician” tells the number of hairs left.
4. Reject if the number of hairs is incorrect. Accept after $k$ times. (to our desired certainty)

Definition

Let $P$ and $V$ be two interactive Turing machines.

Let $x$ be the shared input, $y$ be the secret knowledge, $z$ be the existing knowledge about $y$, with $r_1,r_2,\cdots,r_k$ being the random tapes.

$V$ should output accept or reject after the interaction for $q$ times.

class P(TuringMachine):
    """
    :param x: the shared input with V
    :param y: auxiliary input (the secret knowledge)
    :param z: auxiliary input (could be existing knowledge about y)
    :param r_i: random message
    """
    def run(self, x)->str:
        """
        :return: the message to be sent to V $m_p$
        """
 
class V(TuringMachine):
    """
    The verifier will output accept or reject after the interaction for $q$ times.
 
    :param x: the shared input with P
    :param y: auxiliary input (the secret knowledge)
    :param z: auxiliary input (could be existing knowledge about y)
    :param r_i: random message
    """
    def run(self, q: int)->bool:
        """
        :param q: the number of rounds
        :return: accept or reject
        """
        for i in range(q):
            m_v = V.run(i)
            m_p = P.run(m_v)
            if m_p!=m_v:
                return False
        return True

Let the transcript be the sequence of messages exchanged between $P$ and $V$. $\text{Transcript} = (m_1^p,m_1^v,m_2^p,m_2^v,\cdots,m_q^p,m_q^v)$.

Define $(P,V)$ be the zero-knowledge proof protocol. For a language $L$, $(P,V)$ is a zero-knowledge proof for $L$ if:

Language $L$ is a set of pairs of isomorphic graphs (where two graphs are isomorphic if there exists a bijection between their vertices).

• $(P,V)$ is complete for $L$: $\forall x\in L$, $\exists$ “witness” $y$ such that $\forall z\in \{0,1\}^n$, $Pr[out_v[P(x,y)\longleftrightarrow V(x,z)]=\text{accept}]=1$.
• $(P,V)$ is sound for $L$: $\forall x\notin L$, $\forall P^*$, $Pr[out_v[P^*(x)\longleftrightarrow V(x,z)]=\text{accept}]< \epsilon(n)$.
• $(P,V)$ is zero-knowledge for $L$: $\forall V^*$, $\exists$ p.p.t. simulator $S$ such that the following distributions are indistinguishable:

If these distributions are indistinguishable, then $V^*$ learns nothing from the interaction.

Example: Graph isomorphism

Let $G_0$ and $G_1$ be two graphs.

$V$ picks a random permutation $\pi\in S_n$ and sends $G_\pi$ to $P$.

$P$ needs to determine if $G_\pi=G_0$ or $G_\pi=G_1$.

If they are isomorphic, then $\exists$ permutation $\sigma:\{1,\cdots,n\}\rightarrow \{1,\cdots,n\}$ such that $G_0=\{(i,j)\mid (i,j)\in G_1\}$.

Protocol:

Shared input $\overline{x}=(G_0,G_1)$ witness $\overline{y}=\sigma$. Repeat the following process for $n$ times, where $n$ is the number of vertices.

1. $P$ picks a random permutation $\pi\in \mathbb{P}_n$ and sends $G_\pi=\pi(G_0)$ to $V$.
2. $V$ picks a random $b\in \{0,1\}$ and sends $b$ to $P$.
3. If $b=1$, $P$ sends $\sigma=\pi^{-1}$ to $V$.
4. If $b=0$, $P$ sends $\sigma=\pi$ to $V$.
5. $V$ receives $\phi$ and checks if $b=0$ and $G_\sigma=\phi(G_0)$ or $b=1$ and $G_\sigma =\phi(G_1)$. Return accept if true.

If they are not isomorphic, $P$ rejects with probability 1.

If they are isomorphic, $P$ accepts with probability $\frac{1}{n!}$.

Proof:

• Completeness: If $G_0$ and $G_1$ are isomorphic, then $P$ can always find a permutation $\sigma$ such that $G_\sigma=G_0$ or $G_\sigma=G_1$.
• Soundness:
  • If $P^*$ knows that $V$ was going to send $b=0$, then they will pick $\Pi$ and send $G=\Pi(G_0)$ to $V$. However, if we thought they would send $0$ but they sent $1$, then $G=\Pi(G_1)$ and they would reject.
  • If $P^*$ knows that $V$ was going to send $b=1$, then they will pick $\Pi$ and send $G=\Pi(G_1)$ to $V$. However, if we thought they would send $1$ but they sent $0$, then $G=\Pi(G_0)$ and they would reject.
  • The key is that $P^*$ can only response correctly with probability at most $\frac{1}{2}$ each time.

Continue on the next lecture. (The key is that $P^*$ can only get a random permutation)