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.

• The Paper that Keeps Showing Up

Overview of paper "Unifying Zero-Knowledge Proofs of Knowledge”, by Ueli Maurer.

Very nice explanations on the schnorr signature, and its generalisation (sigma protocols, Maurer proofs, Pedersen commitments)

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)$$

Note: here, it is important that $$h$$ be computed as a one-way of $$R$$. Otherwise, one could generate a valid signature without knowing the private key $$k$$.

Verify

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

Schnorr Proof

Schnorr proof is an interactive zero-knowledge proof, where prover has a secret $$x$$ and a public value $$X \in G$$. The proof allows the prover to demonstrate to a verifier V that she/he knows $$x$$ without revealing it.

• Prereq: P knows $$x \in \mathbb F_q$$, V knows $$X \in \mathbb G$$
• P chooses at random $$k \in \mathbb F_q$$.
• P computes $$K \gets k \cdot G$$
• P sends $$K$$ to V
• V chooses at random $$c \in \mathbb F_q$$
• V sends $$c$$ to P
• P computes $$s \gets k + c \cdot x$$
• P sends $$s$$ to V
• V verifies that $$s \cdot G = K + c \cdot X$$

It is important here that $$c$$ is sent after the commitment $$K$$, otherwise one can build a simulator that returns $$(K,s)$$ from value $$(X,c)$$, without knowing $$x$$ (first pick $$s$$ at random, then compute the corresponding $$K \gets s \cdot G - c \cdot X$$).

The scheme can be non-interactive using Fiat-Shamir transform, using a hash function H (eg. $$c \gets H(K)$$). Thanks to one-wayness, this prevents the prover to compute both $$K$$ and $$c$$.