Asymmetric signatures
Jump to navigation
Jump to search
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)
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$$, V knows $$X$$
- P chooses at random $$k \in F_q$$.
- P computes $$K \gets k \cdot G$$
- P sends $$K$$ to V
- V chooses at random $$c \in 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 \get 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$$.