ZKP in Digital signature algorithm

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$ in step 2 means 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.