Sep 19 2023 22:28 — 7 min read

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 GG, it is generated by an element gg and therefore the set GG will have the form g,g2,,gq1,gq=1{g, g^2,\dots, g^{q-1}, g^q=1} . Then qq is called the degree of GG and GG is called a cyclic group. To ensure the security of cryptosystems, we must work with groups of very high degree (qq is about 25122^{512}).

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

Image by Christopher Lee Image by Christopher Lee

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

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

  • Step 1: PP generates a random number rr between 11  and qq and then gives VV the element u=gru=g^r.
  • Step 2: VV chooses a random number kk between 11 and qq  and gives it to PP.
  • Step 3: PP gives VV the number tt as the remainder when dividing rkxr-kx by qq.
  • Step 4: VV checks and is convinced that PP knows xx if and only if u=ykgtu= y^kg^t.

The main idea in the proof is to require PP to give a representation of uu follows yy and gg, with the exponent of yy in that representation being kk chosen by VV. That is, PP needs to find tt so that u=ykgtu = y^kg^t. We see, if we know xx then PP already knows the representation of yy follows gg and therefore the representation of uu follows yy and gg can only be reduced to the representation of uu follows gg.

PP’s task then is extremely simple and just needs to calculate tt as the remainder when dividing rkxr-kx by qq. Without knowing xx, yy “seems” to be independent compare to gg and PP’s task would be impossible. More specifically, below we will explain why PP needs to know the secret xx to answer a random question of VV and why VV is convinced that PP knows xx but VV still knows nothing about xx:

  • PP must know xx to answer a random choice kk of VV. First of all, we see that, with the same value uu in step 1, PP only needs to give two answers t1,t2t_{1}, t_{2} for two different challenges k1,k2k_{1}, k_{2} of VV in step 2 means that PP must know xx (because then k1x+t1=k2x+t2=rk_{1}x + t_{1} = k_{2}x + t_{ 2} = r and the value xx is easily calculated). Therefore, the fact that with a random choice of kk of VV that PP gives the correct answer tt completely convinces VV that PP must know the answer on many different values ​​of kk, and therefore xx must be known.
  • Why VV doesn’t know anything about xx after the dialogue? The interesting point is that PP only needs to give an answer to a choice kk of VV. In response to a test value kk, VV receives no information about xx. The reason is that after dialogue with PP, all VV has is the set (u,t,k)(u,t,k) that satisfies the equation u=ykgtu=y^kg^t.
    However, without having to converse with PP, VV can simulate that much information by choosing k,tk,t at random and then calculating u=ykgtu=y^kg^t. The distribution of the values ​​(u,t,k)(u,t,k) is then exactly the same as if received through exchange with PP or not doesn’t provide any additional information for VV so VV doesn’t know anything more about the secret xx through dialogue with PP, even though VV is completely convinced that PP knows xx.

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 mm - 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 PP only knows kk after having chosen uu. This is easily achieved interactively, since VV only gives kk to PP after receiving uu. If PP can choose uu after knowing kk then PP can easily create a proof without knowing xx by choosing tt at random and then taking u=ykgtu=y^kg ^t. Therefore, in a non-interactive context, the key is to ensure that uu is chosen before kk. The natural idea is that the value kk should be calculated as a function of uu. This can be achieved in the signature by forcing k=H(m,u)k=H(m,u), with the function HH being a stochastic function, i.e. whatever the input the output is an unpredictable random value and from a corresponding input (in reality the HH function is hash functions like SHA3, MD5…). The fact that the value kk depends on mm also ensures that the proof is generated on the document mm but not some other document.

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

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

If the function HH is sufficiently random, we cannot choose kk before uu because giving the value kk of the function HH first and then finding uu satisfies k=H(m,u)k=H(m,u ) is as difficult as “find a needle in a haystack”. Furthermore, the fact that the value of kk depends on mm ensures that it is the signature on document mm 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.

lightsbee avatar

Hope you have a great day! I'm lightsbee — A Product Manager and also lover of Personal Knowledge Management. You can see my works, or read more about my sharing knowledge on blogs and reach about to know me better.