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, oblivious PRFs, attribute-based credentials)

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.