Exploring the mathematical elegance of ElGamal and Schnorr cryptographic signatures
The ElGamal digital signature scheme, proposed by Taher ElGamal in 1985, is based on the discrete logarithm problem. It provides both authentication and non-repudiation, ensuring that a signature can only be created by the holder of the private key.
The Schnorr signature scheme, invented by Claus Schnorr, is known for its simplicity and efficiency. It's based on the discrete logarithm problem and produces shorter signatures than ElGamal while maintaining the same level of security.
| Aspect | ElGamal | Schnorr |
|---|---|---|
| Signature Size | 2 Ă |q| bits | |q| + |hash| bits |
| Verification Efficiency | 2 exponentiations | 1 exponentiation + 1 multiplication |
| Security Model | Standard model | Random oracle model |
| Batch Verification | Possible but complex | Naturally supported |
| Implementation Complexity | Moderate | Simple |
| Year Introduced | 1985 | 1991 |