Digital Signature Standard

Definition §

A generic G-DSA signature algorithm is defined as follows:

• The public parameters include a cyclic group $G$ of prime order $q$ generated by an element $g$, a hash function $H:\{0,1{\}}^{\ast }\to {\mathbb{Z}}_q$ defined from arbitrary strings into ${\mathbb{Z}}_q$ and another hash function $H^{\prime }:G\to {\mathbb{Z}}_q$ defined from $G$ to ${\mathbb{Z}}_q$.
• Key-Gen: On input the security parameter $\lambda$,
  • outputs a private key $x$ chosen uniformly at random in ${\mathbb{Z}}_q$, and
  • a public key $y=g^x$ computed in $G$.
• Signature: On input an arbitrary message $M$,
  • compute $m=H(M)\in {\mathbb{Z}}_q$
  • choose $k{\in }_R{\mathbb{Z}}_q$
  • compute $R=g^{k^{-1}}$ in $G$ and $r=H^{\prime }(R)\in {\mathbb{Z}}_q$
  • compute $s=k(m+xr)\mathrm{mod}q$
  • output $\sigma =(r,s)$
• Verification: On input $M$, $\sigma$ and $y$,
  • check that $r,s\in {\mathbb{Z}}_q$
  • compute $R^{\prime }=g^{m{s}^{-1}\mathrm{mod}q}{y}^{r{s}^{-1}\mathrm{mod}q}$ in $G$.
  • accept (outupt 1) iff $H^{\prime }(R^{\prime })=r$.

The traditional DSA algorithm is obtained by:

• choosing large primes $p,q$ such that $q|(p-1)$ and setting $G$ to be the subgroup ${\mathbb{Z}}_p^{\ast }$ of order $q$
• in this case the multiplication operation in $G$ is multiplication modulo $p$.
• the function $H^{\prime }$ is defined as $H^{\prime }(R)=R\mathrm{mod}q$.

The EC-DSA algorithm is obtained by:

• choosing $G$ as a group of points on an elliptic curve of cardinality $q$.
• in this case the multiplication operation in $G$ is the group operation over the curve.
• the function $H^{\prime }$ is defined as $H^{\prime }(R)=R_x\mathrm{mod}q$ where $R_x$ is the $x$-coordinate of the point $R$.

Threshold DSA §

The main technical issue in constructing threshold DSA signatures is dealing with the fact that both the secret key $x$ and the nonce $k$ have to remain secret. This means that in a threshold scheme, they must be shared in some way among the servers.

Resources §

• Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin wallet security