exchange

blind-signatures.tex (16891B)

---

 \documentclass{article}
 \usepackage{amssymb}
 \usepackage{amsmath}
 
 \title{Blind signatures schemes for enhancing the privacy of payees}
 
 \author{Emmanuel Benoist, Christian Grothoff, Gian Demarmels, Lucien Heuzeveldt \dots}
 \begin{document}
 
 \maketitle
 
 \section{Introduction}
 
 This article compares several blind signature techniques and their
 applications in the issuing of privacy preserving payments.
 
 The blind signature presented by Chaum \cite{chaum1983blind} corresponds to the possibility for the owner of a key pair (private / public) to sign an element without knowing the precise content of this element. The main use of this type of signature is for someone (other than the person holding the key pair) to sign a token which will then be anonymised. This enables the creation of anonymous tokens that can be used to prove authorisation independently of any authentication that takes place first.
 
 
 The main purpose of blind signing is to preserve user privacy. Whereas
 the usual signature is used to certify an element. Blind signing
 enables an element to be certified without any knowledge of it. From
 the outset, this signature system has been designed to enable e-Cash \cite{chaum1990untraceable} to be used in a variety of ways. In this article, we will show how different blind signature systems can be used to enable electronic payments that protect the privacy of payers while being totally transparent with regard to the money received by merchants. This enables a payment system that is both compatible with regulations against money laundering or the financing of terrorism and at the same time protects the privacy of citizens.
 
 
 
 \subsection{Privacy in existing Payment Systems}
 \paragraph{Traditional bank payment systems}
 The traditional banking system allows two main types of payment. On the one hand, we have payments by bank transfer, debit card or cheque. In this case, the money is transferred from one bank account to another and the two banks know the two parties involved (the one sending and the one receiving the money). The system can be more complicated with an intermediary such as SWIFT, which is used to clear transactions. At least the two banks know all the information about the transaction: origin, destination, amount, date and time of the transaction.
 
 On the other hand, we have credit card payments. In this case, an intermediary (the credit card issuer) pays the merchant directly and invoices the customer at a later date. In this case, the customer's bank, if it is not the credit card issuer, only sees one global payment. In this way, the credit card issuer knows all the expenses of each of its customers: origin, destination, amount, date and time of the transaction. Income paid by credit card is also known to the merchant's bank.
 
 The case of NSA spying on financial transactions \cite{poitras2013nsa}
 shows that the data gathered in the SWIFT system or the credit card
 institutions are very attractive to the intelligence services.
 
 \paragraph{Blockchains}
 Cryptocurrencies based on blockchain use a list of transctions that is basically shared amoung all the full nodes replicating the block chain. The most successful systems are Bitcoin and Ethereum \cite{}. For those two systems, the list of the transactions for all the actors are public. Hence, there is no intrinsec privacy in both systems. One can use tumblering servers \cite{} to hide the provenance or destination of funds. But even this has been exploited by researchers \cite{}.
 
 There exist systems based on a blockchain that can provide a pretty good privacy. For instance Monero \cite{} provides a system based on ring signature, where the provenance of money is hidden in a group of transactions and can not be differenciated. Making it practically not doable to follow the flow of money in this ledger. Monero is therefore offering anonymity for the payer and the payee. This feature has made it a mean of payment for darknet transactions \cite{}.
 
 
 
 \paragraph{Cash}
 Payment in cash can hardly be scrutinized. There is no way to see who did by what at which amount if it is payed in cash. But authorities try to limit the ability to use cash for illegal purpose. They have created anti-money laundering (AML) regulations for limiting the possibility of cash to interact with the banking system.
 
 In some countries, there are limits on how much cash someone can withdraw from their bank account  \cite{}. Most countries also limit the amount that can be deposited into a bank account \cite{}. If the amount exceeds a threshold, the bank must investigate the origin of the money and verify its validity.
 
 Cash is protecting the privacy of the actors (payers and payee) and is used in illegal transactions. Therefore, connections between cash and the traditional banking systems are monitored tightly. 
 
 \subsection{GNU Taler privacy model}
 GNU Taler provides privacy to the payer and no privacy for the payee. This way, people can freely spend their money. But in the same time, there is no way to use this system for the financing of crime of tax evasion.
 
 \paragraph{Technical solutions}
 Taler has been developed with a privacy by design idea. This means that the technical solution used to mint coins is basically not authorizing to access data from the different payers.
 
 The GNU Taler system is based on the blind signature schemes. In a blind signature scheme (originally the one of Chaum, now Clause-Schnorr or XXXX) the authority signing does not know the information signed, just know that the user asking for the signature has the right to do so.
 
 In the case of the payment, a user generates a proto-coin (basically a pair of private and public keys plus a ``denomination''). A denomination is one of the types of coins available (1 cent, 2 cents, 4 cents, 8 cents, \dots). This proto-coin is blinded with a random value. Then the central authority responsible for issuing the coins (called an ``Exchange'') signs the proto-coin with the private key corresponding to the right denomination. It verifies that the user did transfer that amount of money. But since the signature was blind, the exchange has no way to know which coin it signed. Once unblinded, the coin is totally anonymous.
 
 The user can spend the coin as it wants. The merchant will send the coin to the exchange and get its money from the exchange. In this case, the exchange knows exactly to whom the money goes. It also verifies that each signed coin is just spent once. So no double spent is possible. But even though, it has no way to know which user issued that coin initially.
 
 \paragraph{Organisational solutions}
 
 Privacy of payers is given by the blind signature, but it should not be used for money laundering, financing terrorism or any illegal activities.
 
 In order to prohibit illegal activities, some organisational hurdles must be put in place. It depends on the legal framework where the exchange operates. Some exchanges may restrict the amount of money that one physical person, that is known using a Know Your Customer (KYC) procedure, may withdraw in a certain period of time. The limitation can be done for each bank account, in a way to let the bank do the KYC. Some limitations on the amount a merchant can deposit may also be done.
 
 
 \subsection{Comparison of GNU Taler and traditional payment means}
 
 \begin{table}[ht]
   \centering
   \begin{tabular}{|l|c|c|c|c|}
     \hline
     &\multicolumn{2}{c|}{Privacy}&\multicolumn{2}{c|}{Mass surveillance}\\
     &Consumer&Merchant&National&Global\\
     \hline
     Wire transfer&No&No&Yes&No\\
     Credit Cards&No&No&Yes&Yes\\
     Bitcoin and Ethereum& No &No\footnote{requires an additional step: tumblering}&complex\footnote{Surveillance of activities on bitcoin and ethereum blockchain are not possible for poor and small states.}&Yes\\
     Monero&Yes&Yes&No&No\footnote{Evidences are lacking that a big state is able to deanonymize Monero transactions}\\
     GNU Taler&Yes&No&Yes&No\\
     \hline
   \end{tabular}
   \caption{Privacy of the different payment means}
   \label{tab:privacy}
 \end{table}
 
 Table~\ref{tab:privacy} presents the features of the different payment systems regarding on one side the privacy, of customers or merchants, and on one other side, the possibility for law enforcement agency or global surveillance actors to monitor transactions.
 
 GNU Taler offers privacy where it is needed and no privacy where it is not needed. Customers have the possibility to spend their money without being seen. Global actors do not have access to any data of the different actors in the market. They can not see any transaction done by local customers or even merchants. But on the same time, GNU Taler allow local law enforcement agencies to fight the financing of criminal activities.
 
 \subsection{Structure of this paper}
 The blind signature is the cornerstone of the GNU Taler system, and there are different ways to implement it. We will present three ways to implement the blind signature.
 
 % FIXME : write the exact size of the keys for Clause Schnorr.
 In section~\ref{sec:rsa} we will present the blind signature for RSA designed by Chaum. Then in section~\ref{sec:cs} we will present the Clause-Schnorr blind signature that uses eliptic curve cryptography. The main advantage of eliptic curves cryptography is the size of keys and signatures. Whereas RSA uses 2048 or 4096 long keys, Clause-Schnorr will use XXX bit long keys. 
 
 The next big revolution in cryptography could be Quantum computers. If quantum computers were to work properly, they could break existing cryptography protocols (like RSA or Clause-Schnorr). So, even if there is not any evidence yet of a working quantum computer that would have the capabilities to break large keys, one should prepare for such an event. In section~\ref{sec:pq} we present the solution for post quantum cryptography we have designed for GNU Taler.
 
 In the last section (Section~\ref{sec:comparison}) we compare the advantages and disadvantages of each of those blind signature schemes for our purpose of blindly sign coins in the GNU Taler framework. We see how fast they run and also how much memory or how large the databases must be.
 
 \section{RSA blind signature}\label{sec:rsa}
 
 RSA blind signature scheme has been presented by Chaum \cite{chaum1983blind}. The principle is derived from RSA.
 
 In our example, a requester sends a blinded message to the signer, and the signer signs it. The requester can unblind the message and provide a valid signature for it.
 
 The signer has a pair of RSA keys RSA public key: $(n,e)$ and a RSA private key: $d$. Let $m$ be the message to be signed and $r$ be a random number called the blinding factor, such that $gcd(r,n)=1$.
 
 The requester wants to let the user sign $m$ with their private key $(n,e)$ without knowning the content of the message $m$.
 
 The requester generates another message $m'$, where $m'=m.r^e~mod n$. Then they send this message to the signer.
 
 The signer computes $s'=(m')^d~mod n$ and sends it back to the requester.
 
 The requester generates the signature $s$ our of $s'$ using $s=s'.r^{-1}~mod n$.
 
 The requester has now with $m$ and $s$ a message and its valid signature.
 
 \[  s=(m.r^e)^d.r^{-1}=m^d.r^{ed}.r-1\equiv m^d~mod n\]
 
 % The scheme is unfortunately not EUF secure, which means, that given a public key $(n,e)$, it is possible to construct a message with its valid signature.
 
 % The solution is to use a full domain hash function (FDH). A FDH is a cryptographic hash function $h()$ that transforms any message into an image having exactly the same length as the size of the RSA modulo $m$.
 
 % The hash function is simply used on m before the signature and the verification
 
 To be secure, a RSA key needs to be at least 2048 or even better 4096 bit large \cite{}. Signature is also the same size. 
 
 \section{Clause Schnorr blind signature}\label{sec:cs}
 Eliptic curves cryptography offers the possibility to have much smaller keys. It is however also possible to build a blind signature scheme based on eliptic curves.
 
 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\]
 
 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$ 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$.
 
 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}$.
 
 \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.
 
 % 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}_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}_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\]
 
 The user computes a hash of the message (concatenated with the commitment $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}\]
 
 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}
 
 
 \section{Conclusion}
 
 
 \nocite{chaum2021issue}
 
 \bibliographystyle{abbrv}
 
 \bibliography{biblio-blind-signatures}
 \end{document}