126 lines
5.2 KiB
Markdown
126 lines
5.2 KiB
Markdown
# 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.
|
|
|
|
```python
|
|
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:
|
|
|
|
$$
|
|
\{\text{Transcript}[P(x,y)\leftrightarrow V^*(x,z)\mid x\in L,y\leftarrow \{0,1\}^n]\}\quad\text{and}\quad\{S(x,z)\mid x\notin L\}.
|
|
$$
|
|
|
|
*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)
|