ElGamal signature without calculating the inverse

Question

I stumbled upon this question in some textbook.

Propose a variant of ElGamal signature scheme such that there is no need to calculate the inverse $k^{-1}$ as it is usually done using the EEA.

Recalling what ElGamal signature is about: we fix a prime number $p$ and a generator $\alpha$ of $Z_p^*$. User $A$ then chooses a number $a \in \{0, \ldots, p-1\}$ as its private key and sets $ \beta = \alpha^a \pmod{p}$ as its public key. To sign a message $x$, $A$ chooses a random $k \in Z_{p-1}^*$. The signed message is then $(\gamma, \delta)$ where $$\gamma \equiv \alpha^k \pmod{p} \quad{} \hbox{and} \quad{} \delta \equiv (x-a\gamma)k^{-1} \pmod{(p-1)}$$

To verify the validity of the signature, $B$ verifies that $$ \beta^\gamma \gamma^\delta \equiv \alpha^x \pmod{p}$$

I have no idea how to solve this problem without breaking the security of the system. Browsing the internet, I've found some papers related to this problem, but the proposed solutions seemed too complicated for a question posed at the undergrad level. Does anyone know a clever solution?

Answer 1

Try switching $\alpha$ and $\gamma$ during the verify.

Fix a prime number $p$ and a generator $\alpha$ of $Z_p^*$. User $A$ then chooses a number $a \in \{0, \ldots, p-1\}$ as its private key and sets $ \beta = \alpha^a \pmod{p}$ as its public key. To sign a message $x$, $A$ chooses a random $k \in Z_{p-1}^*$. The signed message is then $(\gamma, \delta)$ where $$\gamma \equiv \alpha^k \pmod{p} \quad{} \hbox{and} \quad{} \delta \equiv kx-a\gamma \pmod{(p-1)}$$

To verify the validity of the signature, $B$ verifies that $$ \beta^\gamma \alpha^\delta \equiv \gamma^x \pmod{p}$$

Correctness: $$\beta^\gamma \alpha^d = \alpha^{a\gamma+d} \text{ but } \gamma^x = \alpha^{kx} \text{ and } d = kx-a\gamma$$

Security: Seems a little iffy to move the known exponent onto an unknown generator, but forging a signature ($\delta$) for a given $\gamma$ still seems like a discrete log problem with base $\alpha$. I don't know if there is a better way to choose $\gamma$ to make forging signatures easier though.

The definition of $\delta$ does not use $k$ (beyond $\gamma$) to mask the secret key $a$. I think just using $\gamma$ is a bad idea, so I think this system is insecure, but I forget the attack.

Answer 2

Schnorr signatures and KCDSA are two ElGamal variants that don't need an inverse for computing a signature.