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 $$c \gets H(m || R)$$
• Let $$s \gets r + c \cdot k$$
• Ouput $$\sigma \gets (c,s)$$

Note: here, it is important that $$c$$ 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^sK^{-c}$$
• Let $$c' \gets H(m || R')$$
• If $$c' = c$$, return 1, otherwise return 0.

Same, but using scalar multiplication instead of exponentiation, and returning R instead of h:

Sign

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

Verify

• Let $$c' \gets H(m || R)$$
• Let $$R' \gets s \cdot G - c' \cdot K$$
• If $$R' = R$$, 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 \mathbb 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$$.

This proofs has three properties [1]:

• completeness, this says that if the prover is honest, then the proof succeeds.
• honest verifier zero-knowledge, this says that the verifier learns nothing from $$(K,s)$$ that it knows already.

This can be proven by building a simulator that returns $$(K,s)$$ from $$(c,X)$$. As a result, this also shows that it is important that $$K$$ be committed before sending $$c$$ (otherwise one could run such simulator).

• extractabilty, this says that the prover must know $$x$$ in order to pass the proof.

This is done by running the protocol twice with the same choice $$K$$ (as if we would rewind the protocol, or using a time-machine), but different challenge $$c$$. In that case, one can extract the secret value $$x$$ from the responses $$(s,c)$$ and $$(s',c')$$. This extractibility property also mean that the prover must absolutely pick $$k$$ at random, otherwise it might expose the secret $$x$$ to extraction. This weakness is inherent to the zero-knowledge proof.