ElGamal signature without calculating the inverse

Question

Last time I asked a question of this type on math.se it was redirected here, so I hope this one is also appropriatete for crypto.se.

I stumbled uppon 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 net, I've found some papers related to this problem, but the proposed solution seemed too complicated for a question posed at the undergrad level.

Anyone happens to see 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.