Any scenario for using ElGamal-SIGNATURE over RSA?

Question

On a homework assignment, we're asked to give an example in which scenario one would use an ElGamal-Signature over an RSA-Signature. I found this question, but the answer also only describes why RSA is superior. I searched a while now, but I don't really find any reason why one would use a Schoolbook-ElGamal (not DSA or elliptic curves) instead of RSA.

Does anyone have an additional idea?

Answer 1

ElGamal signature works as follows. Define a large prime $p = 2qs + 1$ where $q$ is a prime. Let $g$ be an element of order $q$ and a hash function $H\colon \{0,1\}^* \to \mathbb{Z}_q$. The public key is $y = g^x \bmod p$ and the private key is $x \in \mathbb{Z}_q$. The signature of a message $m$ is given by a pair $(r,s)$ where $$r=g^k \bmod p\quad\text{and}\quad s = k^{-1}(H(m) - xr) \bmod q$$ for a random integer $k \in \mathbb{Z}_q$. The validity of a signature $(r,s)$ on message $m$ is checked by verifying that $r^sy^r \equiv g^{H(m)} \pmod p$.

It is worth to see that the two expensive operations in the signature generation, namely computing $g^k \bmod p$ and $k^{-1} \bmod q$, are independent of the message to be signed. They can therefore be precomputed. ElGamal signatures can be preferred when signing should be done very fast, like for example to authenticate a car at a toll bridge. In this mode (called off-line/on-line),

1. [off-line phase] several coupons $(r_i, t_i)$, with $r_i = g^{k_i} \bmod p$ and $t_i = k_i^{-1} \bmod q$, for random integers $k_i \in \mathbb{Z}_q$ are pre-computed;
2. [on-line phase] when a message $m$ has to be signed, the signer takes a fresh coupon $(r_i, t_i)$ and computes the signature as $r = r_i$ and $s = t_i(H(m) - xr_i) \bmod q$.

Notes.

1. A coupon can only be used once. Each signature needs a fresh coupon.

2. In the on-line phase, the cost of an ElGamal signature is only a couple of multiplications modulo $q$ (which is much faster than a full modular exponentiation in the case of RSA).