Security analysis for a extended ElGamal Signature against selective unforgeability

Question

Let $H$ is a cryptography hash function and $\Pi=(\mathsf{G}, \mathsf{S}, \mathsf{V})$ is a digital signature, as follows:

$(h_1=g^x,h_2=g^y) \leftarrow \mathsf{G}(1^n)$, where $x,y$ uniformly random from $\mathbb{Z}^*_q \ .$

$(r=g^k,s=(H(m)-x \cdot r)\cdot k^{-1},z= y^{-1} \cdot k ) \leftarrow \mathsf{s}_{x,y}(m)$, where $k$ uniformly random from $\mathbb{Z}^*_q \ .$

$b:=\mathsf{V}_{h_1,h_2}(m,(r,s,z))$, where $b := \begin{cases} 1 & \text{if } (g^{H(m)} = h_1^r \cdot h_2^{z \cdot s}) \\ 0 & \text{otherwise} \end{cases}$ The above construction is similar to ElGamal signature (https://en.wikipedia.org/wiki/ElGamal_signature_scheme).

1- Where can I find proof of existential unforgeability ElGamal signature?

2- Does the above construction is a secure digital signature against existential unforgeability?

Answer 1

The hashed ElGamal signature scheme was shown to be secure by Pointcheval and Stern (see Section 3.3.); i.e., the signature scheme resists adaptive chosen message attacks assuming the discrete logarithm problem is hard. The proof of security is quite remarkable, as this was the first application of the forking lemma. Sometimes they refer to the hashed ElGamal signature scheme as the Pointcheval–Stern signature algorithm.

Note that the original ElGamal scheme (where the message is not hashed) is existentially forgeable, see Theorem 16. in the linked paper above.