Asymmetric signatures

References

• On the Security of the Schnorr Signature Scheme and DSA against Related-Key Attacks

A nice overview of the three main schemes, ElGamal, Schnorr and DSA.

Summary

These are the main asymmetric signature schemes:

• ElGamal
• Schnorr
• DSA

Schnorr signature

Key generation

• Private key: choose $$k \in \Z_q$$,
• Public key: $$K \gets G^k$$.

Sign

• Input: message $$m \in \{0,1\}^*$$
• Choose $$r \in \Z_q$$, and compute $$R \gets G^r$$
• Let $$h \gets H(m || R)$$
• Let $$s \gets r + k \cdot h$$
• Ouput $$\sigma \gets (h,s)$$

Verify

• Let $$R' \gets G^sY^{-h}$$
• Let $$h' \gets H(m || R')$$
• If $$h' = h$$, return 1, otherwise return 0.