Asymmetric signatures
References
- A nice overview of the three main schemes, ElGamal, Schnorr and DSA.
- 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.