I want to prove that the DSA signature scheme is EUF-CMA secure in the random oracle model, if the discrete logarithm problem is hard. I know it can be proved by the following two parts:

  1. Discrete logarithm problem is hard $\Rightarrow$ DSA identification scheme is UI-PA security
  2. DSA identification scheme is UI-PA security + $H,F$ are random oracle $\Rightarrow$ DSA signature scheme is EUF-CMA secure

For clarity, the DSA identification protocol and signature algorithm I consider is as follows (use the Fiat-Samir transform to convert the identification protocol into a signature scheme):

DSA identification protocol


  • Prover uniformly selects $r\leftarrow \mathbb{Z}_p$, let $R:=g^r\in G$, and gives $R$ to Verifier.
  • Verifier uniformly selects $(e,d)\leftarrow \mathbb{Z}_p^2$, and gives $(e,d)$ to Prover.
  • Prover computes $z:=r^{-1}\cdot(e+d\cdot s)\in\mathbb{Z}_p$, and gives $z$ to Verifier
  • Verifier checks whether $R=(g^e\cdot h^d)^{z^{-1}}$. If yes, the verification passes.

DSA signature scheme

Two hash functions: $H:\{0,1\}^*\to \mathbb{Z}_p,F:G\to \mathbb{Z}_p$

  • Key generation algorithm: $(PK=(G,p,g,h=g^s),SK=s)\leftarrow \mathsf{Gen}(1^\lambda)$
  • Signature algorithm: $\sigma\leftarrow\mathsf{Sign}(SK,M)$, message $M\in\{0,1\}^*$
    • Prover uniformly selects $r\leftarrow \mathbb{Z}_p$, let $R:=g^r\in G$
    • Computes $e:=H(M)\in\mathbb{Z}_p$
    • Computes $d:=F(R)\in\mathbb{Z}_p$
    • Computes $z:=r^{-1}\cdot(e+d\cdot s)\in\mathbb{Z}_p$
    • Outputs $\sigma:=(d,z)$
  • Verification algorithm: $0/1\leftarrow \mathsf{Vfy}(PK,M,\sigma=(d,z))$
    • Verifier computers $e:=H(M)\in\mathbb{Z}_p$
    • Computes $R:=(g^e\cdot h^d)^{z^{-1}}\in\mathbb{Z}_p$
    • Checks whether $d=F(R)$. If yes, outputs 1; otherwise, outputs 0

I've solved the first part, but I don't know how to prove the second part. I found a relevant proof about the Schnorr signature scheme in in Theorem 12.10 on page 454 of INTRODUCTION TO MODERN CRYPTOGRAPHY. But unlike the Schnorr signature scheme, the DSA signature scheme uses two hash functions (i.e. $H,F$), which confuses me.

Detailed proofs or ideas are welcome and appreciated :)

  • $\begingroup$ Question is clear now! Your $p$ is noted $q$ in DSA or $n$ in ECDSA. In these your $F$ is a reduction modulo your $p$ of some integer (near) representative of an element of your $G$. So you are studying some theoretical model/variant of DSA/ECDSA. There is literature linked in this question, and this ref. $\endgroup$
    – fgrieu
    Apr 21, 2023 at 6:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.