Prerequisites for Zero-Knowledge Proof
Preface
I started my research on ZKP last month. There were many unfamiliar math concepts for me, such as group, order, elliptic curve, etc. After struggling for several days and with the help of my professor, I understood them gradually. Now I want to construct my knowledge base in this field. My best bet is to rephrase these contents like executing rubber duck debugging. This is why I decided to write a series of articles to help me review the ideas. This page is aiming at introducing jargon/concepts and explaining them with concrete examples (try my best). For some complicated concepts, I’ll illuminate the topics with more pages.
Part 1
Field
A field is a set, whose elements are able to execute basic number operations with each other, denoted by an upper character (\(\mathbb F\)).
e.g.
- \(\mathbb R\) (real numbers)
- \(\mathbb Q\) (rational numbers)
Most cryptographic theorems reply on finite fields, especially with prime numbers. The reason is that the modulo operation over prime numbers features some useful properties. I’ll introduce these features and how they work later.
Group
A group is a set and a binary operation * that allows any two elements to produce a third element, which also belongs to the same set, denoted by \((\mathbb G, *)\).
e.g.
- \((\mathbb Q, +)\), \(\mathbb Q\) under \(+\) operation is a group.
A group has the following properties:
- Closure: \(\forall a,b\in\mathbb G, a*b\in\mathbb G\). I.e., the definition of a group.
- Associativity: \(\forall a,b,c\in\mathbb G, (a*b)*c=a*(b*c)\). E.g., For addition, \((a+b)+c=a+(b+c)\).
- Identify: There exists a unique element \(e\in\mathbb G\), s.t. \(\forall a\in\mathbb G,e*a=a*e=a\). E.g., \(1\) is the identity of multiplication, \(0\) is the identity of addition.
- Inverse: \(\forall a\in\mathbb G\), there exists a unique element \(b\in\mathbb G\), s.t. \(a*b=b*a=e\). Such element is called the inverse of \(a\) and commonly denoted by \(a^{-1}\).
In applied cryptography, a group over modular multiplicative with prime numbers is frequently used. This is because \(1\) is the identity element in the multiplication group, and finding the inverse of an element is equivalent to solving \(ax\equiv 1\pmod{p}\), which is the goal of the Extended Euclidean algorithm. The benefits for computers to implement cryptographic algorithms through modular multiplicative are boosting the computation process and reducing memory usage. Recall RSA, the public key \(e\) is the inverse of the private key \(d\) modulo \(\phi(N)\).
Subgroup
A subgroup is a non-empty subset of a group, denoted by \((\mathbb S, *)<(\mathbb G, *)\).
e.g.
- \((\mathbb Z, +)<(\mathbb Q, +)\), integers \(\mathbb Z\) is a subgroup of rational numbers \(\mathbb Q\) under \(+\).
Note:
- A subgroup has all the properties of a group.
- A group is a subgroup of itself.
- The set containing the single identity element is also a subgroup, called a trivial subgroup.
Order
The order of a group is the number of elements in that group, denoted by \(|\mathbb G|\).
e.g.
- The order of \((\mathbb Z_n, +)\) is \(n\).
The order of an element is the order of the subgroup generated by this element.
e.g.
- For \((\mathbb Z_5, +)\), the order of \(2\) is 2.
As for the group over multiplication, the order of an element \(a\) is the smallest positive integer \(m\) s.t. \(a^m=e\pmod{n}\), called multiplicative order.
e.g.
- The order of \(8\) in \(\mathbb Z_{23}^*\) is 11.
Generator
A generator is a number that can generate all the elements of the group by repeatedly applying one or more operation(s) on themselves.
e.g.
- \(1\) is a generator of the positive number group under \(+\).
- \(2\) is a generator of the positive even number group excluding \(0\) under \(+\).
Safe Prime
A safe prime is a prime number \(p\), s.t. \(p=2q+1\) where q is also prime.
e.g.
- \(5\) is a safe prime (\(5=2\times2+1\)).
- \(7\) is a safe prime (\(7=2\times3+1\)).
Safe prime features many useful properties in terms of finding the above concepts. Let’s draw the modular exponentiation table of \(\mathbb Z_7^*\):
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 4 | 1 | 2 | 4 | 1 |
| 3 | 3 | 2 | 6 | 4 | 5 | 1 |
| 4 | 4 | 2 | 1 | 4 | 2 | 1 |
| 5 | 5 | 4 | 6 | 2 | 3 | 1 |
| 6 | 6 | 1 | 6 | 1 | 6 | 1 |
It’s easy to find that the possible orders exist in \(\{1, 2, 3, 6\}\) for all elements excluding \(1\). Recall the definition of safe prime, the orders are corresponding to \(\{1, 2, {{p-1}\over 2}, p-1\}\). This situation never happens if we choose a non-safe prime.
Another interesting finding is all the single element having order \({p-1}\over 2\) is also a generator of the subgroup they combine (like the chart below).
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 2 | 4 | 1 |
| 4 | 4 | 2 | 1 |
We can get the same subgroup if the group is under multiplication rather than exponentiation. (Safe prime is intriguing!)
With the help of the above findings, we can produce a subgroup \(\mathbb G_q\) having the following properties:
- The size of \(\mathbb G_q\) is \(q\).
- The order of all elements is \(q\) (except \(1\)).
- This indicates \(g^q\pmod{p}=1\rightarrow g^n\pmod{p}=g^{n\pmod{q}}\pmod{p}\).
- Finding the inverse of any element is efficient: \(g^{-1}\pmod{p}=g^{q-1}\pmod p\).
Part 2
Diffie-Hellman Key Exchange
Diffie-Hellman key exchange allows multiple parties to exchange cryptographic keys over a public channel.
Assume \(A\) and \(B\) want to exchange their key and make an agreement on the session key, i.e., \(A: g^x\), \(B: g^y\), and the session key will be \(g^{xy}\). They can achieve their goal through the following steps:
- \(A\) -> \(B\): \(g^x\)
- \(B\) -> \(A\): \(g^y\)
- \(A\) and \(B\) can compute the session key respectively: \((g^x)^y\), \((g^y)^x\)
The security of DH holds because it’s infeasible to compute \(g^{xy}\) when given \(g^x\) and \(g^y\). This is called Computational Diffie-Hellman (CDH). Another related assumption is Decisional Diffie-Hellman (DDH): determine whether \(z\) is equal to \(g^{xy}\) given \(g^x,g^y,z\). These two assumptions are based on the hardness of the Discrete Logarithm Problem (DLP): find \(x\) where \(g^x=n\) when given \(g, n\), considered as computational hardness assumption.
Proof of Knowledge
Assume there’re a prover \(P\) and a verifier \(V\), s.t. \(P\) wants to convice \(V\) that \(P\) knows something. If \(P\) succeeds in proving the knowledge without revealing the secrect itself (\(V\) also cannot extract the secrect through the proof that \(P\) sends), we call this zero-knowledge proof.
e.g.
- A simple example of proof of knowledge is \(P\) has the private key corresponding to the public key, then \(P\) can convince \(V\) by signing a message to let \(V\) accept the proof.
Practically, we mathematically design the proof system, e.g., \(P\) proves s/he knows a polynomial by giving the root of the polynomial, which holds due to Schwartz-Zippel Lemma.
Schwartz–Zippel Lemma
Assume a non-zero polynomial \(f(x_1,x_2,\dots,x_n)\) has total degree \(d\), and there’s a finite field \(S\). If we choose \(r_1,r_2,\dots,r_n\) randomly and independently from \(S\), then the probability that \(f(r_1,r_2,\dots,r_n)=0\) is \(\leq{d\over{|S|}}\).
e.g.
- Let \(S=\mathbb F_5, \{0,1,2,3,4\}\). Let \(f(x)=x-1\). Following the lemma, the probability that \(f(r)\) is equal to zero is \(\leq{1\over 5}\). We can list all the possible values: \(1\). The probability is \(={1\over 5}\).
- Let \(S=\mathbb F_5, \{0,1,2,3,4\}\). Let \(f(x,y)=x(x+y)\). Following the lemma, the probability that (f(r,s)\) is equal to zero is \(\leq{2\over 5}\). We can list all the possible values: \((0,1),(0,2),(0,3),(0,4),(1,4),(2,3),(3,2),(4,1)\). The probability is \(8\over 25\), which is \(\lt{2\over 5}\).
In fact, this is the main idea of how the interactive proof system achieves soundness: if the statement is false, the probability of the prover can convince the verifier is negligible. Normally the field used in the system is much bigger than \(d\), resulting in the soundness error being close to zero.
Sigma Protocols
A \(\Sigma-protocol\) features a way to prove a knowledge without disclosing the secret ifself. It follows 3 steps: commitment, challenge, and response. First, the prover sends a commitment of a random value to the verifier. Then the verifier generates another random value as the challenge and sends it to the prover. Finally, the prover generates a response with combining the random value in step 1, the challenge sent by the verifier, and the witness (the value being used to prove the knowledge), and sends the response to the verifier. After some computation, the verifier will accept or reject the proof.
e.g.
- Schonrr Protocol
- \(P\) wants to prove that s/he knows a value \(x\), s.t. \(h=g^x\). Given \(h\) and \(g\), it’s infeasible to obtain \(x\) due to DLP. In order to achieve zero knowledge, \(P\) generates a random value \(r\in\mathbb Z_p\) and produces a value \(a\), s.t. \(a=g^r\pmod{p}\). Then \(P\) sends \(a\) to \(V\).
- \(V\) generates a challenge value \(e\in\mathbb Z_p\) and sends it to \(P\).
- \(P\) creates a response \(\sigma\), s.t. \(\sigma\leftarrow ex+r\), and sends the response to \(V\).
- Now \(V\) can verify the proof by checking the equality of \(g^\sigma\) and \(h^ea\).
Fiat-Shamir Heuristic
Fiat-Shamir is a heuristic method to make \(\Sigma\)-protocols non-interactive. The main idea is using some hash function running over a random oracle to generate \(a\), and computing \(e\leftarrow RO(x,a)\) as the challenge. Thus the protocol can proceed: \(P\) sends \(a\), \(e\), and \(\sigma\) to \(V\).