commit 5f26104c6f2da4e4c978a2d6e5384da32f8eb169
parent 4cbde3dca6623ea2d1cd331c7929c36995e73a87
Author: Emmanuel Benoist <emmanuel.benoist@bfh.ch>
Date: Mon, 7 Jul 2025 17:55:35 +0200
First version for the Clause Schnorr scheme
Diffstat:
1 file changed, 59 insertions(+), 13 deletions(-)
diff --git a/doc/cs/article/blind-signatures.tex b/doc/cs/article/blind-signatures.tex
@@ -1,9 +1,10 @@
\documentclass{article}
\usepackage{amssymb}
+\usepackage{amsmath}
\title{Blind signatures schemes for enhancing the privacy of payees}
-\author{Emmanuel Benoist, Christian Grothoff, \dots}
+\author{Emmanuel Benoist, Christian Grothoff, Gian Demarmels, Lucien Heuzeveldt \dots}
\begin{document}
\maketitle
@@ -133,52 +134,97 @@ Eliptic curves cryptography offers the possibility to have much smaller keys. It
Eliptic curve cryptography bases on the multiplication of a point on the curve G (a generator of the curve with prime order $n$) by a scalar (the private key $q$ ). The result is the public key $Q$.
-\[Q = q.G\]
+\[Q := q.G\]
+
+The eliptic curve algorithms presentation is based on \cite{desmarmelsHeuzeveldt} which was based on \cite{cryptoeprint:2019:877}.
\paragraph{Signature with eliptic curve cryptography}
In eliptic curves one can use signature with the Eliptic Curve Digital Signature Algorithm (ECDSA).
To sign a message $m$, this scheme uses a cryptographic hash function $h()$ (for instance SHA-256).
-The signer first needs to hash the message $m$, $e=h(m)$. Then the signer picks a random nonce $a$ and computes the corresponding point on the curve $A=aG=(x_1,y_1)$. The signer computes $r=x_1~mod~n$ (if $r=0$, their pick another nonce $a$).Then one can compute the value $s=a^{-1}(e+qr)~mod~n$.
+The signer first needs to hash the message $m$, $e:=h(m)$. Then the signer picks a random nonce $a$ and computes the corresponding point on the curve $A:=aG$ where $A=(x_1,y_1)$. The signer computes $r:=x_1~mod~n$ (if $r=0$, their pick another nonce $a$).Then one can compute the value $s:=a^{-1}(e+qr)\mod{n}$.
The signature is $(r,s)$.
\subparagraph{Verification}
-The verifyer of the signature first computes the hash of the message $e=h(m)$. Then $w=s^{-1}$ which is the inverse of the signature $s$.
+The verifyer of the signature first computes the hash of the message $e:=h(m)$. Then $w:=s^{-1}$ which is the inverse of the signature $s$.
-Then, the verifyer computes $u_1=ew~mod~n$ and $u_2=rw~mod~n$. They can generate a point in the curve based on the generator $G$ and the public key of the signer $Q$: $R'=u_1G+u_2Q=(x_1',y_1')$.
+Then, the verifyer computes $u_1:=ew\mod{n}$ and $u_2:=rw\mod{n}$. They can generate a point in the curve based on the generator $G$ and the public key of the signer $Q$: $R'=u_1G+u_2Q=(x_1',y_1')$.
-The signature is valid if and only if $r\equiv x_1' mod n$.
+The signature is valid if and only if $r\equiv x_1'\mod{n}$.
\paragraph{Blind signature}
% Fixme Blind signatures Citation
We first present the Blind Schnorr Signature Scheme which is considered broken. We present the fix in the next paragraph.
-We use for this scheme, the same key pair for signing $(q,Q)$ where $Q = q.G$.
+% FIXME definir p comme le prime du groupe
+
+We use for this scheme, the same key pair for signing $(x,P)$ where $P := x.G$.
-Before receiving the message, the signer generates a first random number $r$ (out of $\mathbb{Z}_n$) that will be a private key. The signer generates out of it the corresponding public key $R=rG$. The point $R$ is sent to the user.
+Before receiving the message, the signer generates a first random number $r$ (out of $\mathbb{Z}_p$) that will be a session private key. The signer generates out of it the corresponding public key $R=rG$. The point $R$ is sent to the user.
-The user choses then two random values $\alpha$ and $\beta$ (also out of $\mathbb{Z}_n$). They generate a blinded nonce based on $\alpha$, $\beta$ and the two public keys sent by the signer $R$ and $Q$.
+The user choses then two random values $\alpha$ and $\beta$ (also out of $\mathbb{Z}_p$). They generate a blinded nonce based on $\alpha$, $\beta$ and the two public keys sent by the signer $R$ and $Q$.
-\[R' = R + \alpha G+ \beta Q\]
+\[R' := R + \alpha G+ \beta Q\]
The user computes a hash of the message (concatenated with the commitment $R'$).
-\[ e = h(m\Vert R') \]
+\[ e := h(m\Vert R') \]
+
+This hash is then blinded $e':= e+\beta \mod{p}$. And $e'$ is sent to the signer.
+
+The signer signes the challenge $e'$ with its private key $x$.
+
+\[s':=r + x e'\mod{p}\]
+
+The user can then unblind this signature to get a valid signature for the original message.
+
+User computes $s$ out of $s'$.
+
+\[ s:=s'+\alpha\mod{p}\]
-This hash is then blinded $e'= e+\beta ~mod~n$. And $e'$ is signed to the signer.
+The signature of the message is $(e,s)$.
+\subparagraph{Verification of the signature}
+Anyone knowing $(e,s)$ and the public key $P$ can compute.
+\[R' := sG - eP\]
+
+and can check if $e$ is equal to $h(m\Vert R')$.
+
+This all works because:
+
+\[R'= sG -eP \\
+ R'= sG - exG\\
+ R' = (s - ex)G\\
+ R' = (s' -s' +s -ex)G\\
+ R' = (r+e'x -s' +s -ex)G ~~\text{because } s'=r+e'x\\
+ R' = rG +(s-s')G +(e'-e)xG\\
+ R' = R + \alpha G -\beta X ~~\text{because} \alpha=s-s' \text{ and } \beta=e'-e\\
+ R'=R+\alpha G + \beta P\]
+
+Unfortunately, this scheme is not safe against the ROS problem and need to be extended. This scheme was proven in \cite{cryptoeprint:2019:877} that solving the ROS problem breaks the unforgeability property of blind Schnorr signatures by finding $l+1$ valid signatures out of $l$ signing operations.
\paragraph{Clause-Schnorr signature scheme}
In this paragraph, we present the Clause-Schnorr improved signature scheme presented in \cite{cryptoeprint:2019:877}.
-
+The Clause Blind Schnorr Signature Scheme is a modification of the Blind Schnorr Signature Scheme for which the ROS problem is harder to solve.
+The Clause Blind Schnorr Signature Scheme does this by choosing two random values $r_0, r_1$ and calculating $R_0 := r_0G; R_1 := r_1G$.
+The user generates the blinding factors twice $\alpha_0, \alpha_1, \beta_0, \beta_1 \leftarrow random \in \mathbb{Z}_p$.
+
+The user then calculates the challenges as before $c_0' := H(R_0',m); c_0 := c_0' + \beta_0 \mod p$ and $c_1' := H(R_1',m); c_1 := c_1' + \beta_1 \mod p$.
+
+After the signer receives the two challenges $c_0$ and $c_1$, the signer randomly chooses $b \leftarrow random \{0, 1\}$ and calculates only $s_b$ as in $s := r_b+c_bx \mod p$.
+The User receives $s, b$ and can unblind the signature to receive his signature $\sigma := \langle R'_b, s'_b \rangle$.
+The verification algorithm remains the same for Clause Blind Schnorr Signature Scheme.
+
\section{Post-Quantum solution for blind signature}\label{sec:pq}
+\section{Design of the application depending on the signature scheme}
+
\section{Comparisons of the different models}\label{sec:comparison}
