*Original article by Phan Duong Hieu.*

…

From the relatively abstract principles ZKP, we will consider a specific proof and from there explicitly build an digital signature scheme. All we need is a finite set with multiplication so that from a element we can calculate all the other elements. To be more specific, we are working on a finite set $G$, it is generated by an element $g$ and therefore the set $G$ will have the form ${g, g^2,\dots, g^{q-1}, g^q=1}$ . Then $q$ is called the degree of $G$ and $G$ is called a *cyclic* group. To ensure the security of cryptosystems, we must work with groups of very high degree ($q$ is about $2^{512}$).

Then the following problem is considered very difficult to solve for current computers: Let $g$ and $y$ be a random element in $G$, the requirement is to find $x$ that satisfies $y=g^ x$. If we try from $x=1$ to $q$, we will find the answer, but this test will take billions of years (when $q$ is as large as $2^{512}$).

*Image by Christopher Lee*

I can easily generate an element $y$ by randomly choosing a secret $x$ and calculating $y=g^x$. Then if $y$ is made public, only I will know $x$, and you will not know $x$ because finding $x$ is solving the discrete logarithm problem. How can I prove to you that I know the secret that $x$ corresponds to $y$? The simplest way is for me to give $x$ to you to check whether $y$ is equal to $g^x$ or not. This method completely convinces you that I know the secret, but the price to pay is that I lose $x$ secret. I don’t want you to know $x$ but you’re still convinced by me that I know $x$. Proving that I know $x$ but after proving that you still do not know anything about $x$, that is a ZKP.

Proving knowledge of $x$ without revealing $x$ is quite simple. **The prover** (called $P$) gives $g, y$ and claims to know $x$ such that $y=g^x$. The goal is that **the verifier** (called $V$), holding $(g, y)$, needs to be convinced that $P$ knows $x$ but $V$ himself will still not know anything about $x$ after being convinced. The proof process is as follows:

Step 1: $P$ generates a random number $r$ between $1$ and $q$ and then gives $V$ the element $u=g^r$.Step 2: $V$ chooses a random number $k$ between $1$ and $q$ and gives it to $P$.Step 3: $P$ gives $V$ the number $t$ as the remainder when dividing $r-kx$ by $q$.Step 4: $V$ checks and is convinced that $P$ knows $x$ if and only if $u= y^kg^t$.

The main idea in the proof is to require $P$ to give a representation of $u$ follows $y$ and $g$, with the exponent of $y$ in that representation being $k$ chosen by $V$. That is, $P$ needs to find $t$ so that $u = y^kg^t$. We see, if we know $x$ then $P$ already knows the representation of $y$ follows $g$ and therefore the representation of $u$ follows $y$ and $g$ can only be reduced to the representation of $u$ follows $g$.

$P$’s task then is extremely simple and just needs to calculate $t$ as the remainder when dividing $r-kx$ by $q$. Without knowing $x$, $y$ *“seems”* to be independent compare to $g$ and $P$’s task would be impossible. More specifically, below we will explain why $P$ needs to know the secret $x$ to answer a random question of $V$ and why $V$ is convinced that $P$ knows $x$ but $V$ still knows nothing about $x$:

- $P$ must know $x$ to answer a random choice $k$ of $V$. First of all, we see that, with the same value $u$ in
step 1, $P$ only needs to give two answers $t_{1}, t_{2}$ for two different challenges $k_{1}, k_{2}$ of $V$ instep 2means that $P$ must know $x$ (because then $k_{1}x + t_{1} = k_{2}x + t_{ 2} = r$ and the value $x$ is easily calculated). Therefore, the fact that with a random choice of $k$ of $V$ that $P$ gives the correct answer $t$ completely convinces $V$ that $P$ must know the answer on many different values of $k$, and therefore $x$ must be known.- Why $V$ doesn’t know anything about $x$ after the dialogue? The interesting point is that $P$ only needs to give an answer to a choice $k$ of $V$. In response to a test value $k$, $V$ receives no information about $x$. The reason is that after dialogue with $P$, all $V$ has is the set $(u,t,k)$ that satisfies the equation $u=y^kg^t$.

However, without having to converse with $P$, $V$ can simulate that much information by choosing $k,t$ at random and then calculating $u=y^kg^t$. The distribution of the values $(u,t,k)$ is then exactly the same as if received through exchange with $P$ or not doesn’t provide any additional information for $V$ so $V$ doesn’t know anything more about the secret $x$ through dialogue with $P$, even though $V$ is completely convinced that $P$ knows $x$.

So we end up with a ZKP. From there we can build an digital signature scheme.

The purpose of an digital signature scheme is how we can sign a document - represented as a numeric value $m$ - so that no one can fake our signature, but everyone can check it. That signature is mine. The problem seems a bit similar to a ZKP but the basic difference is that digital signatures do not go through interactive Q&A, while ZKP necessarily goes through interaction.

Looking back at the ZKP above, the key point is that $P$ only knows $k$ after having chosen $u$. This is easily achieved interactively, since $V$ only gives $k$ to $P$ after receiving $u$. If $P$ can choose $u$ after knowing $k$ then $P$ can easily create a proof without knowing $x$ by choosing $t$ at random and then taking $u=y^kg ^t$. Therefore, in a non-interactive context, the key is to ensure that $u$ is chosen before $k$. The natural idea is that the value $k$ should be calculated as a function of $u$. This can be achieved in the signature by forcing $k=H(m,u)$, with the function $H$ being a stochastic function, i.e. whatever the input the output is an unpredictable random value and from a corresponding input (in reality the $H$ function is hash functions like SHA3, MD5…). The fact that the value $k$ depends on $m$ also ensures that the proof is generated on the document $m$ but not some other document.

Taking the original interaction proof above and replacing the dialogue between $P$ and $V$ with the work of the signer, we have the following digital signature scheme, proposed by **Schnorr**:

Step 1: The signer chooses the private key $x$ and publishes the public key $y=g^x$. The purpose is to send a document $m$ and need to sign on it. The signer generates a random number $r$ between 1 and $q$ and then calculates $u=g^r$.Step 2: The signer calculates $k=H(u,m)$.Step 3: The signer calculates $t$ as the remainder when dividing $r-kx$ by $q$ and places the signature on document $m$ as $(u,t)$.Step 4: On the document $m$ and the signature $(u,t)$, the checker calculates $k=H(m,u)$ and checks whether $u$ is equal to $y^kg^t$ or not. If equal, accept the signature on document $m$, otherwise reject.

If the function $H$ is sufficiently random, we cannot choose $k$ before $u$ because giving the value $k$ of the function $H$ first and then finding $u$ satisfies $k=H(m,u )$ is as difficult as *“find a needle in a haystack”*. Furthermore, the fact that the value of $k$ depends on $m$ ensures that it is the signature on document $m$ and not on some other document.

In cryptography, the **Schnorr** digital signature we considered above is the basis for many digital signature standards used in practice (including the digital signature standard *DSA - Digital signature algorithm*).

Going from the vague (proving interaction without revealing knowledge - ZKP) to then applying it to do something specific (digital signature) is really interesting! What is too obvious may only have finite value, what is mysterious may have unlimited potential value.