01 History and Basics

🪑 Session chair: Akira/Jan (Duties: Read material above-average carefully 🤓; prepare fallback discussions/questions (worst-case: just prepare some quiz questions about the material) 🙋. Prepare a few slides to guide the session through subtopics (this is not supposed to be a detailed summary of the material)

✍️ Notetaker: Jan (Duties: Take Obsidian notes during the session 📝. Moderate to get input for the wiki pages 🧠. Make people summarize / dumb down discussion results to keep things comprehensible for everyone 🧑‍⚖️.)

🎯 Goals

First, this is to kick off the reading group. We want to discuss important notions, and get everyone up to speed with the influential “roots” of ZK proofs.

We want to understand

• Basic definitions of the IP complexity class, Soundness/Proof of Knowledge, and Zero Knowledge (simulation paradigm).
• Cut-and-Choose protocols (e.g., 3-colorable, Quadratic Residue, Graph Isomorphism).
• Fiat-Shamir.

📚 Material

• Lecture (slides)

Additional (optional) material can be found on https://zk-learning.org.

📝 Notes

Session 1.1 (2023-06-01): Basic definitions

Mostly talked about Soundness/Proof of Knowledge and Zero Knowledge.

Interactive Proofs

Let $L$ be a language. An interactive proof system for $L$ is a tuple of interactive algorithms Prover $P$ and Verifier $V$, that proceed as follows.

1. $P$ and $V$ take a statement $x$ as common input.
2. For each round $i=1,\dots ,r$: $P$ sends a message $a_i$ and $V$ responds with $q_i$.
3. At the end of interaction, $V$ outputs $1$ (“accept”) or $0$ (“reject”)

Typically, $V$ has limited computational power, whereas $P$ is unbounded.

Could the number of rounds $r$ be arbitrary?

We typically assume $r$ to be a constant. Some protocols have $r\in \log (|x|)$.

Completeness

We say a proof system $(P,V)$ is complete if $V$ accepts after both $P$ and $V$ follow the protocol honestly. More formally: If $x\in L$, then $\mathrm{Pr}[(P,V)(x)=1]=1$.

Soundness

Consider a scenario where $P$ is potentially malicious, i.e., $P$ tries to convince $V$ that the statement $x$ belongs to $L$, even if $x\notin L$. Soundness guarantees that, as long as $x\notin L$ then $V$ always rejects no matter what a cheating prover does. Formally:

If $x\notin L$, then $\forall P^{\ast }$, $\mathrm{Pr}[(P^{\ast },V)(x)=1]=\mathsf{negl}(|x|)$

What does $\ast$ mean?

We often indicate an algorithm $A^{\ast }$ is adversarial.

Zero Knowledge

Now we consider a scenario where $V$ is malicious, i.e., $V$ may potentially deviate from the protocol to obtain some extra information than the fact that $x\in L$. Zero Knowledge guarantees that, no malicious $V^{\ast }$ can gain useful information while interacting with honest $P$.

Formally:

If $x\in L$, then $\forall V^{\ast }$, $\exists S$ such that ${\text{view}}_{V^{\ast }}((P,V^{\ast })(x))\approx S(x)$

where ${\text{view}}_{V^{\ast }}((P,V^{\ast })(x))$ denotes the distribution of strings that $V^{\ast }$ observes during the execution of $(P,V^{\ast })(x)$, i.e., all incoming messages to and outgoing messages from $V^{\ast }$.

What is the role of simulator $S$?

Intuitively, the existence of simulator implies that the information $V^{\ast }$ gains from a protocol execution could be efficiently computed by $V^{\ast }$ itself from $x$. This means that $V^{\ast }$ has learned “nothing new” by interacting with $P$.

If $V^{\ast }$ can simulate a protocol execution, why can't $V^{\ast }$ run a simulator to convince another verifier? Doesn't ZK condradict Soundness?

Although it sounds somewhat paradoxical, the existence of simulator doesn’t mean that one can play an honest prover. This is because a simulator may cheat by generating a transcript in the reverse order or by exploiting the knowledge of secret trapdoor.

Proof of Knowledge

In some applications, plain soundness may not be satisfactory. Say you as a user want to authenticate yourself to the web service by proving that you know secret identity information.

To this end, let us assume that $L$ is an NP language and consider the corresponding NP relation $R_L=\{(x,w):|w|\le \text{poly}(|x|)\wedge x\in L\}$, where the string $w$ is called witness. In a proof system for $R$, $P$ takes $w$ as private input, $P,V$ take $x$ as common input, and they interact, denoted by $(P(w),V)(x)$.

We say a proof system for $R_L$ is Proof of Knowledge (PoK) if the following condition is satisfied: if $V$ accepts on statement $x$, then $P^{\ast }$ must have known the corresponding witness $w$.

Formally, $\exists E$ such that $E$ is PPT and $\forall P^{\ast }$, $\forall x\in L$, $\mathrm{Pr}[b=1\wedge (x,w)\notin R_L|b\leftarrow (P^{\ast },V)(x);w\leftarrow E^{P^{\ast }}(x)]=\mathsf{negl}(|x|)$

What does $E^{P^{\ast }}$ mean?

It means that an extractor $E$ has black-box access to $P^{\ast }$. This implies that $E$ can rewind $P^{\ast }$ to its previous state.

Session 1.2 (2023-06-15): Example protocols

We will revisit the definitions and look at examples to understand the basic mechanisms and tricks better.

Session 1.3 (2023-06-22): More example protocols

For real this time: let’s go through the example protocols and understand how they work. To prepare, please read

• Zero Knowledge (in particular Zero Knowledge (Classical), but don’t get too hung up on the details)
• Proof of Knowledge (in particular Proof of Knowledge (Classical), but don’t get too hung up on the details)
• Graph Isomorphism Protocol
• Quadratic Residue Protocol
• The 3-Colorable Protocol in the Lecture (slides)

Note any comments and questions you may have and bring them to the session. If you notice typos, you can also directly fix them on https://github.com/JanBobolz/zk-wiki. If you feel like writing (even small parts of) the 3-Colorable Protocol entry, go for it! It would be appreciated 🙂.