Asymmetric signatures: Difference between revisions

From miki
Jump to navigation Jump to search
 
(6 intermediate revisions by the same user not shown)
Line 4: Line 4:
* [https://cronokirby.com/posts/2022/08/the-paper-that-keeps-showing-up/ The Paper that Keeps Showing Up]
* [https://cronokirby.com/posts/2022/08/the-paper-that-keeps-showing-up/ The Paper that Keeps Showing Up]
:Overview of paper "Unifying Zero-Knowledge Proofs of Knowledge”, by Ueli Maurer.
: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)
:Very nice explanations on the schnorr signature, and its generalisation (sigma protocols, Maurer proofs, Pedersen commitments, oblivious PRFs, attribute-based credentials)


== Summary ==
== Summary ==
Line 20: Line 20:
* Input: message $$m \in \{0,1\}^*$$
* Input: message $$m \in \{0,1\}^*$$
* Choose $$r \in \Z_q$$, and compute $$R \gets G^r$$
* Choose $$r \in \Z_q$$, and compute $$R \gets G^r$$
* Let $$h \gets H(m || R)$$
* Let $$c \gets H(m || R)$$
* Let $$s \gets r + k \cdot h$$
* Let $$s \gets r + c \cdot k$$
* Ouput $$\sigma \gets (h,s)$$
* Ouput $$\sigma \gets (c,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$$.
: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
;Verify
* Let $$R' \gets G^sY^{-h}$$
* Let $$R' \gets G^sK^{-c}$$
* Let $$h' \gets H(m || R')$$
* Let $$c' \gets H(m || R')$$
* If $$h' = h$$, return 1, otherwise return 0.
* 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 ==
Schnorr proof is an interactive zero-knowledge proof, where prover has a secret $$x$$ and a public value $$X \in G$$.
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.
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$$
* Prereq: P knows $$x \in \mathbb F_q$$, V knows $$X \in \mathbb G$$
* P chooses at random $$k \in F_q$$.
* P chooses at random $$k \in \mathbb F_q$$.
* P computes $$K \gets k \cdot G$$
* P computes $$K \gets k \cdot G$$
* P sends $$K$$ to V
* P sends $$K$$ to V
* V chooses at random $$c \in F_q$$
* V chooses at random $$c \in \mathbb F_q$$
* V sends $$c$$ to P
* V sends $$c$$ to P
* P computes $$s \gets k + c \cdot x$$
* P computes $$s \gets k + c \cdot x$$
Line 48: Line 61:


The scheme can be non-interactive using [https://www.wikiwand.com/en/Fiat%E2%80%93Shamir_heuristic 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$$.
The scheme can be non-interactive using [https://www.wikiwand.com/en/Fiat%E2%80%93Shamir_heuristic 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 [https://cronokirby.com/posts/2022/08/the-paper-that-keeps-showing-up/]:
* '''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.

Latest revision as of 08:41, 31 October 2022

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.