Digital signatures are crpytographic schemes that provide message authentication (the receiver can verify the origin of the message), integrity (the receiver can verify that the message has not been modified since it was signed) and non-repudiation (the sender cannot falsely claim that they have not signed the message).

In this short note, we discuss arithmetic circuit constraints that ensures that a witness, a set of inputs and outputs, correctly computes (or are related to each other through) the Digital Signature Algorithm (DSA) and its more advanced version that uses elliptic curves. Both algorithms are based on groups of known order and the discrete logarithm (DL) security assumptions.

A signature scheme has three parts, the setup algorithm which involves private and public key generation, the signature algorithm itself, and a verification algorithm for checking if a signature is authentic.

The verification algorithm is the only part of the scheme that is public and is typically the only part that is of importance for circuit constraints. For example, the verification algorithm for DSA appears in smart contracts executed in the Ethereum Virtual Machine. The veracity of the inputs and outputs of this verification algorithm can be shown by encoding a set of contraints into a circuit used to prove a larger set of computations with a ZK-SNARK.

We will introduce the two algorithms, DSA and Elliptic-curve DSA in turn and briefly discuss the circuit constraints associated with each.

---

Digital Signature Algorithm (DSA)

Setup Algorithm: The setup algorithm generates a private key known only to the sender (or signee) and a corresponding public key. Since the setup algorithm is privately computed and not really relevant to the verification process, it is possible to skip this section, which only provides background information on why DSA works.

The algorithm goes as follows. Security parameters

$(p,q)$ are chosen and publically shared.

$p$ is a prime of size

$>1024$ bits and

$q$ is a prime of size

$>160$ bits chosen in such a way that

$p-1=cq$ for a particular

$c>0$. The reason for this contraint is as follows.

The signatures created by DSA will be utilizing a cyclic subgroup

$G⩽\mathbb{Z}/p{\mathbb{Z}}^{\times }$ of prime order

$q$ with a generator

$g$. Now the question of interest is how to find such a generator.

$\mathbb{Z}/p{\mathbb{Z}}^{\times }$ is the multiplicative group (with non-prime order

$p-1$) of the prime field

${\mathbb{F}}_p$, which will act as the base field. Any subgroups of this multiplicative group have orders that can divide

$p-1$ due to Lagrange's theorem and are cyclic (all subgroups of a cyclic group are cyclic).

We need

$g^q=1\text{ mod }p$. Since

$q$ is prime and have no divisors except

$1$ and itself, a

$g$ that satisfies this equation would be a generator of a subgroup of order

$q$ or would be the identity element

$1$. We can generate such a

$g$ by considering a random element

$h\sim \text{Unif}(\{2,...,q-2\})$ in

${\mathbb{F}}_p$. Then, we can consider the candidate

$\tilde{g}=h^c\text{ mod }p$, as

${\tilde{g}}^q=h^{cq}=h^{p-1}=1\text{ mod }p$ for any

$h$, due to Fermat's little theorem. Therefore,

$\tilde{g}$ is either

$1$ or a generator of the cyclic subgroup

$G$ and we can find other candidates if we end up with

$\tilde{g}=1$.

$(p,q,g)$ are determined through this process. Once these are determined, we can operate within

$G$ by raising the generator to

$i\in [0,1,2,...,q-1]$ to obtain the sequence

$[1,g,g^2,...,g^{q-1}]$, which is the

$\mathbb{Z}/q{\mathbb{Z}}^{+}$ isomorphism. Note that the group operation within the subgroup

$G$ is

$g^i\text{ mod }p$ and not

$g^i\text{ mod }q$.

Based on all this setup, the sender choses a private key

$k_{\text{pr}}\in \{2,...,q-1\}$ to keep hidden and computes a corresponding public key from the subgroup

$G$,

$k_{\text{pub}}=g^{k_{\text{pr}}}\mathrm{mod}p$, which gets published along with the generator

$g$. In addition to these, a cryptographic hash function

$H$ is chosen and published.

Overall, the setup algorithm executed by the sender publishes

$(p,q,k_{\text{pub}},g,H)$ and keeps hidden

$k_{\text{pr}}$.

---

Signature Algorithm: Similar to the setup algorithm, the signature algorithm itself is not publically computed and therefore is not typically a subject of circuit constraints. The section can be skipped, as it only explains how the signatures are created by the sender.

DSA is a stochastic signature scheme and therefore, each time a signature is generated for a particular fixed message

$m$, the signature is different. This requires a source of randomness,

$\pi \sim \text{Unif}(\{1,...,q-1\})$.

Then, a one-time random key

$r$ is created by trying a number of

$\pi$ until

$r\ne 0$ (few tries are needed) which are related through the following equation.

$$\begin{array}{r}r=\tilde{r}\text{ mod }q=(g^{\pi }\text{ mod }p)\text{ mod }q\end{array}$$ Note that

$\tilde{r}=g^{\pi }\text{ mod }p$ is an element of

$G$. The exponentiation in this computation is the most computationally expensive part of the signing operation, but it may be computed before the message is known, which is an advantage of the scheme. We also need to calculate

${\pi }^{-1}={\pi }^{q-2}\text{ mod }q$, using the Extended Euclidean algorithm (EEA), which is the second most expensive operation.

In order to generate the signature for a given message

$m$, which can be of variable length, we first hash it to a fixed-size digest,

$H(m)$. This digest, along with the randomness variables

${\pi }^{-1}$,

$r$ and the public key

$k_{\text{pr}}$, is then used to compute the following,

$$\begin{array}{r}\sigma =({\pi }^{-1}(H(m)+r{k}_{\text{pr}}))\text{ mod }q.\end{array}$$Then, the triplet

$(m,r,\sigma )$ is published as the signed message. Note that the message-sender pair

$(m,k_{\text{pub}})$ is now interlocked to the signature pair

$(r,\sigma )$ through this signed message.

---

Verification Algorithm: The verification algorithm is the only publically computed part of the scheme and is of great interest to proof systems. In this section, we will give a description and then discuss the circuit constraints in the next section.

Given a signed message

$(m,r,\sigma )$ and the public variables

$(p,q,g,k_{\text{pub}})$, verification process is centered around checking a relation between these variables that is efficiently computable. As a preliminary, the algorithm first checks

$0<r$,

$\sigma <q$, and then computes

${\sigma }^{-1}={\sigma }^{q-2}\text{ mod }q$ (usually using EEA for efficiency).

Based on how

$\sigma$ is computed in the signature algorithm, we can obtain the following candidate relation that could be useful for verification,

$$\begin{array}{rl}\sigma & =({\pi }^{-1}(H(m)+r{k}_{\text{pr}}))\text{ mod }q\\ \pi \sigma & =(H(m)+r{k}_{\text{pr}})\text{ mod }q\\ \pi & =(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})\text{ mod }q.\end{array}$$However, the verification algorithm does not know the private key

$k_{\text{pr}}$ to be able to check this relationship. On the other hand, the subgroup encrypted version of this relationship,

$$\begin{array}{rl}{g}^{\pi }\text{ mod }p& =g^{(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})\text{ mod }q}\text{ mod }p\end{array}$$ is much more useful, as it replaces the private key

$k_{\text{pr}}$ with the public key

$k_{\text{pub}}$ if the correct set of simplification steps take place (note that

$\text{ mod }q$ can be removed, as the subgroup is known to have an order

$q$):

$$\begin{array}{rl}{g}^{\pi }\text{ mod }p=g^{(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})\text{ mod }q}\text{ mod }p& =g^{(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})}\text{ mod }p\\ & =g^{H(m){\sigma }^{-1}}{g}^{r{k}_{\text{pr}}{\sigma }^{-1}}\text{ mod }p\\ \tilde{r}& =g^{H(m){\sigma }^{-1}}{k}_{\text{pub}}^{r{\sigma }^{-1}}\text{ mod }p.\end{array}$$This could further be improved to,

$$\begin{array}{rl}r& =\tilde{r}\text{ mod }q=(g^{H(m){\sigma }^{-1}}{k}_{\text{pub}}^{r{\sigma }^{-1}}\text{ mod }p)\text{ mod }q.\end{array}$$Based on the above,

$(m,r,{\sigma }^{-1},k_{\text{pub}})$ are interlocked into this relationship through the generator

$g$, the hash function

$H$ and the

$(p,q)$ pair, which is checked by the verification algorithm to confirm that the signature

$(r,\sigma )$ matches the message-sender pair

$(m,k_{\text{pub}})$.

---

Circuit constraints: Finally, we discuss the circuit constraints that replicate the verification algorithm in proving that the signature in a signed message

$(r,\sigma )$ matches the message-sender pair

$(m,k_{\text{pub}})$.

As it is the case in most arithmetic circuits, this is accomplished by breaking down the verification check equation into a set of simpler arithmetic equations with the use of auxiliary advice variables, provided as inputs to the circuit, that need to match intermediate computations.

These advice variables are, the output of the hash function

$H_m$, the inverse of

$\sigma$ variable (modulo

$q$)

${\sigma }_{\text{inv}}$, quotients for modulo operations

${\kappa }_{\text{inv}},{\kappa }_{\text{p}},{\kappa }_{\text{q}}$, and various intermediate computations

$\alpha ,\beta ,\gamma ,\theta$.

Given a witness, inputs + advice variables,

$$\begin{array}{c}p,q,k_{\text{pub}},g\text{[public variables]}\\ m,r,\sigma \text{[signed message]}\\ H_m,{\sigma }_{\text{inv}},{\kappa }_{\text{inv}},{\kappa }_{\text{p}},{\kappa }_{\text{q}},\alpha ,\beta ,\gamma ,\theta \text{[advice variables]}\end{array}$$ the following set of circuit constraints can be used to verify the authenticity of a signed message,

$$\begin{array}{rl}{H}_m& =H(m)\text{[Using circuit constraints specific to hash function]}\\ \sigma \cdot {\sigma }_{\text{inv}}& =1+{\kappa }_{\text{inv}}q\\ \alpha & =H_m{\sigma }_{\text{inv}}\\ \beta & =r{\sigma }_{\text{inv}}\\ \gamma & =g^{\alpha }\text{[By decomposing it into }{\log }_2\alpha \text{ intermediate constraints]}\\ \theta & =k_{\text{pub}}^{\beta }\text{[By decomposing it into }{\log }_2\beta \text{ intermediate constraints]}\\ r& =\gamma \theta +{\kappa }_{p}p+{\kappa }_{q}q\end{array}$$ Exponentiations are handled by decomposing the constraint into many smaller constraints that build upon, e.g.

$g_2=g\cdot g$ and

$g_4=g_2\cdot g_2$ and so on until some

$\gamma =g_{\alpha /2}\cdot g_{\alpha /2}$ is reached, similar to the square multiply algorithm used in efficient group exponentiation. There are logarithmic number (in the exponent) of such constraints needed.

In general, doing all this efficiently requires decomposing single constraints with large integers in them, into multiple constraints with smaller integers, as the integers inputted to these constraints can be huge due to security requirements of DSA. This is a topic we explore in another note focused on efficient large number arithmetic circuits.

---

Elliptic Curve DSA (ECDSA)

Setup Algorithm: Elliptic Curve DSA is identical to DSA, except that it changes the subgroup used. It replaces the prime order

$q$ subgroup of the multiplicative group of the field

${\mathbb{F}}_p$ with an elliptic curve

$G$ constructed on

${\mathbb{F}}_p\times {\mathbb{F}}_p$. Much of the three algorithms remain the same. Security parameters are again

$(p,q)$ and

$q$ is the order of the elliptic curve and the generator of the curve is

$g$.

In the same manner as DSA, the private key is chosen from

$k_{\text{pr}}\in \{2,...,q-1\}$ and the public key is computed using the curve group operation according to

$k_{\text{pub}}=g^{k_{\text{pr}}}$. We will use the multiplicative notation for the elliptic curve to match the earlier discussion of DSA, even though an additive notation is more common for elliptic curves.

---

Signature Algorithm: The source of randomness,

$\pi \sim \text{Unif}(\{1,...,q-1\})$, is the same as DSA. However,

$\tilde{r}\in G$ is now a curve point calculated as

$\tilde{r}=g^{\pi }$.

In DSA, the one-time random key

$r$ was a digest of

$\tilde{r}$ with some bits of information lost through a smaller modulo operation, when

$\tilde{r}$ was in a larger field of order

$p>>q$. Similarly,

$r$ in ECDSA is calculated as a digest from the curve point

$\tilde{r}$ by taking its

$x$ coordinate

${\tilde{r}}_x$ and then passing it through modulo

$q$,

$$\begin{array}{r}r={\tilde{r}}_x\text{ mod }q=(g^{\pi }{)}_x\text{ mod }q\end{array}$$

Again, the group operations (exponentiation) in this computation is the most computationally expensive part of the signing operation, but it may be computed before the message is known.

$\pi$ needs to be randomly chosen such that

$r\ne 1$, the identity element of the elliptic curve at infinity.

The inverse

${\pi }^{-1}$ and the signature

$\sigma$ are computed exactly in the same way as DSA,

$$\begin{array}{r}\sigma =({\pi }^{-1}(H(m)+r{k}_{\text{pr}}))\text{ mod }q.\end{array}$$ The signed message

$(m,r,\sigma )$ is then published.

---

Verification Algorithm: Once again, as a preliminary, the algorithm checks that

$0<r,\sigma <q$, and then computes

${\sigma }^{-1}={\sigma }^{q-2}\text{ mod }q$ (usually using EEA for efficiency).

It is still the case that

$\pi =(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})\text{ mod }q$. Again, the verifier does not know the private key

$k_{\text{pr}}$ to be able to check this. Similarly, since

$g$ is the generator of

$G$ with order

$q$, the group encrypted version of this relationship

$g^{\pi }=g^{(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})\text{ mod }q}$ is the same as

$g^{(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})}$, and is much more useful, as it replaces the private key

$k_{\text{pr}}$ with the public key

$k_{\text{pub}}$ if the correct set of simplification steps take place.

$$\begin{array}{rl}\tilde{r}=g^{\pi }=g^{(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})\text{ mod }q}& =g^{(H(m){\sigma }^{-1}+r{k}_{\text{pr}}{\sigma }^{-1})}\\ & =g^{H(m){\sigma }^{-1}}{g}^{r{k}_{\text{pr}}{\sigma }^{-1}}\\ \tilde{r}& =g^{H(m){\sigma }^{-1}}{k}_{\text{pub}}^{r{\sigma }^{-1}}\end{array}$$This could further be improved to,

$$\begin{array}{rl}r& ={\tilde{r}}_x\text{ mod }q=(g^{H(m){\sigma }^{-1}}{k}_{\text{pub}}^{r{\sigma }^{-1}}{)}_x\text{ mod }q.\end{array}$$which interlocks

$(m,r,{\sigma }^{-1},k_{\text{pub}})$ to each other. Verifying this relationship is enough to verify that the signature

$(r,\sigma )$ matches the message/sender pair

$(m,k_{\text{pub}})$, which can be done efficiently.

As we can see in all of these three algorithm, ECDSA is almost exactly the same as DSA except that the subgroup used is changed from a modulo group to an elliptic curve (digest operation to compute the one-time key

$r$ also has a slight change).

---

Circuit constraints: Again, we discuss the circuit constraints that replicate the verification algorithm in proving that the signature in a signed message

$(r,\sigma )$ matches the message-sender pair

$(m,k_{\text{pub}})$.

The advice variables are, the output of the hash function

$H_m$, the inverse of

$\sigma$ variable (modulo

$q$)

${\sigma }_{\text{inv}}$, quotients for modulo operations

${\kappa }_{\text{inv}},{\kappa }_{\text{q}}$, the coordinates

${\tilde{r}}_x,{\tilde{r}}_y$ and various intermediate computations

$\alpha ,\beta ,\gamma ,\theta$.

Given a witness, inputs + advice variables,

$$\begin{array}{c}p,q,k_{\text{pub}},g\text{[public variables]}\\ m,r,\sigma \text{[signed message]}\\ H_m,{\sigma }_{\text{inv}},{\kappa }_{\text{inv}},{\kappa }_{\text{q}},{\tilde{r}}_x,{\tilde{r}}_y,\alpha ,\beta ,\gamma ,\theta \text{[advice variables]}\end{array}$$ the following set of circuit constraints can be used to verify the authenticity of a signed message,

$$\begin{array}{rl}{H}_m& =H(m)\text{[Using circuit constraints specific to hash function]}\\ \sigma \cdot {\sigma }_{\text{inv}}& =1+{\kappa }_{\text{inv}}q\\ \alpha & =H_m{\sigma }_{\text{inv}}\\ \beta & =r{\sigma }_{\text{inv}}\\ \gamma & =g^{\alpha }\text{[By decomposing it into }{\log }_2\alpha \text{ intermediate constraints]}\\ \theta & =k_{\text{pub}}^{\beta }\text{[By decomposing it into }{\log }_2\beta \text{ intermediate constraints]}\\ ({\tilde{r}}_x,{\tilde{r}}_x)& =\gamma \theta \\ r& ={\tilde{r}}_x+{\kappa }_{q}q\end{array}$$ Now, multiplications in the constraints with

$\alpha ,\beta ,\gamma ,\theta$ and

$\gamma \theta$ are no longer integer constraints but elliptic curve constraints, which will have to be expanded to the specific integer computations involved in the group operation of the curve.

Aside from that, the only difference between these constraints and those of DSA is the addition of

$({\tilde{r}}_x,{\tilde{r}}_x)$ as advice variables that represent the coordinates of the elliptic curve point corresponding to

$\tilde{r}$ and the removal of the quotients related to modulo

$p$.