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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.