# ElGamal signature without calculating the inverse

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?

-
I'm assuming that the new scheme just needs to look secure, not actually be any good. Presumably if one could remove an expensive modular inverse without security consequences, it would have already been done. – Jack Schmidt Sep 5 '11 at 22:23
@Jack: not necessarily. You can implement inversion with modular exponentiation ($1/x = x^{p-2} \mod q$); this is not the fastest way, but it is fast enough for ECDSA or ElGamal: you already have such code around, and that operation has very small cost compared to the other modular exponentiation that you must already compute. However, this is relevant for ECC-based variants, where modular inversion requires extra code; this prompted the South-Korean government to sponsor EKDSA, a variant which replaces inversion with a well-placed XOR. – Thomas Pornin Sep 6 '11 at 6:41

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.

-
Nice scheme! For the curious: You are right, it is not secure. Let $(\gamma,\delta)$ be a valid signature on the message $x$. Then $(\gamma^2,\gamma \delta)$ will be a valid signature on the message $\gamma x/2$. (This works as long as either $\gamma$ or $x$ is even.) Therefore, the scheme is not secure against existential forgery. Your answer still seems like a good response to the textbook question, though. – D.W. Feb 28 '14 at 20:44

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

-