diff options
Diffstat (limited to 'doc/paper')
| -rw-r--r-- | doc/paper/taler.tex | 478 |
1 files changed, 243 insertions, 235 deletions
diff --git a/doc/paper/taler.tex b/doc/paper/taler.tex index 6787fcd71..4a4f741a3 100644 --- a/doc/paper/taler.tex +++ b/doc/paper/taler.tex @@ -1167,6 +1167,236 @@ certification process. \section{Correctness} +\subsection{Taxability arguments} + +We assume the exchange operates honestly when discussing taxability. +We feel this assumption is warranted mostly because a Taler exchange +requires licenses to operate as a financial institution, which it +risks loosing if it knowingly facilitates tax evasion. +We also expect an auditor monitors the exchange similarly to how +government regulators monitor financial institutions. +In fact, our auditor software component gives the auditor read access +to the exchange's database, and carries out test operations anonymously, +which expands its power over conventional auditors. + +\begin{proposition} +Assuming the exchange operates the refresh protocol honestly, +a customer operating the refresh protocol dishonestly expects to +loose $1 - {1 \over \kappa}$ of the value of their coins. +\end{proposition} + +\begin{proof} +An honest exchange keeps any funds being refreshed if the reveal +phase is never carried out, does not match the commitment, or shows +an incorrect commitment. As a result, a customer dishonestly +refreshing a coin looses their money if they have more than one +dishonest commitment. If they make exactly one dishonest +commitment, they have a $1 \over \kappa$ chance of their +dishonest commitment being selected for the refresh. +\end{proof} + +We say a coin $C$ is {\em controlled} by a user if the user's wallet knows +its secret scalar $c_s$, the signature $S$ of the appropriate denomination +key on its public key $C_s$, and the residual value of the coin. + +We assume the wallet cannot loose knowledge of a particular coin's +key material, and the wallet can query the exchange to learn the +residual value of the coin, so a wallet cannot loose control of +a coin. A wallet may loose the monetary value associated with a coin +if another wallet spends it however. + +We say a user Alice {\em owns} a coin $C$ if only Alice's wallets can +gain control of $C$ using standard interactions with the exchange. +In other words, ownership means exclusive control not just in the +present, but in the future even if another user interacts with the +exchange. + +\begin{theorem} +Let $C$ denote a coin controlled by users Alice and Bob. +Suppose Bob creates a coin $C'$ from $C$ following the refresh protocol. +Assuming the exchange and Bob operated the refresh protocol correctly, +and that the exchange continues to operate the linking protocol +(\S\ref{subsec:linking}) correctly, +then Alice can gain control of $C'$ using the linking protocol. +\end{theorem} + +\begin{proof} +Alice may run the linking protocol to obtain all transfer keys $T^i$, +bindings $B^i$ associated to $C$, and those coins denominations, +including the $T'$ for $C'$. + +We assumed both the exchange and Bob operated the refresh protocol +correctly, so now $c_s T'$ is the seed from which $C'$ was generated. +Alice rederives both $c_s$ and the blinding factor to unblind the +denomination key signature on $C'$. Alice finally asks the exchange +for the residual value on $C'$ and runs the linking protocol to +determine if it was refreshed too. +\end{proof} + +\begin{corollary} + Abusing the refresh protocol to transfer ownership has an + expected loss of $1 - \frac{1}{\kappa}$ of the transaction value. +\end{corollary} + + +\subsection{Privacy arguments} + +The {\em linking problem} for blind signature is, +if given coin creation transcripts and possibly fewer +coin deposit transcripts for coins from the creation transcripts, +then produce a corresponding creation and deposit transcript. + +We say an adversary {\em links} coins if it has a non-negligible +advantage in solving the linking problem, when given the private +keys of the exchange. + +In Taler, there are two forms of coin creation transcripts, +withdrawal and refresh. + +\begin{lemma} +If there are no refresh operations, any adversary with an +advantage in linking coins is polynomially equivalent to an +adversary with the same advantage in recognizing blinding factors. +\end{lemma} + +\begin{proof} +Let $n$ denote the RSA modulus of the denomination key. +Also let $d$ and $e$ denote the private and public exponents, respectively. +In effect, coin withdrawal transcripts consist of numbers +$b m^d \mod n$ where $m$ is the FDH of the coin's public key +and $b$ is the blinding factor, while coin deposits transcripts +consist of only $m^d \mod n$. + +Of course, if the adversary can link coins then they can compute +the blinding factors as $b m^d / m^d \mod n$. Conversely, if the +adversary can recognize blinding factors then they link coins after +first computing $b_{i,j} = b_i m_i^d / m_j^d \mod n$ for all $i,j$. +\end{proof} + +We now know the following because Taler uses SHA512 adopted to be + a FDH to be the blinding factor. + +\begin{corollary} +Assuming no refresh operation, +any adversary with an advantage for linking Taler coins gives +rise to an adversary with an advantage for recognizing SHA512 output. +\end{corollary} + +We will now consider the impact of the refresh operation. For the +sake of the argument, we will first consider an earlier +encryption-based version of the protocol in which refresh operated +consisted of $\kappa$ normal coin withdrawals where the commitment +consisted of the blinding factors and private keys of the fresh coins +encrypted using the secret $t^{(i)} C_s$ where $C_s = c_s G$ of the +dirty coin $C$ being refreshed and $T^{(i)} = t^{(i)} G$ is the +transfer key.\footnote{We abandoned that version as it required + slightly more storage space and the additional encryption + primitive.} + +\begin{proposition} +Assuming the encryption used is semantically (IND-CPA) secure, and +that the independence of $c_s$, $t$, and the new coins' key materials, +then any probabilistic polynomial time (PPT) adversary with an +advantage for linking Taler coins gives rise to an adversary with + an advantage for recognizing SHA512 output. +\end{proposition} + +In fact, the exchange can launch an chosen cphertext attack against +the customer by providing different ciphertexts. Yet, the resulting +plaintext is implicitly authenticated becuase after decryption +the customer unblinds and checks the signature by the denomination +key. + +If this check does not check out, then the wallet must abandon +this coin and report the exchange's fraudulent activity. + +% TODO: Is independence here too strong? + +We may now remove the encrpytion by appealing to the random oracle +model~\cite{BR-RandomOracles}. + +\begin{lemma}[\cite{??}] +Consider a protocol that commits to random data by encrypting it +using a secret derived from a Diffe-Hellman key exchange. +In the random oracle model, we may replace this encryption with +a hash function which derives the random data by applying hash +functions to the same secret. +\end{lemma} +% TODO: IND-CPA again? Anything else? + +\begin{proof} +We work with the usual instantiation of the random oracle model as +returning a random string and placing it into a database for future +queries. + +We take the random number generator that drives one random oracle $R$ +to be the random number generator used to produce the random data +that we encrypt in the old encryption based version of Taler. +Now our random oracle scheme with $R$ gives the same result as our +scheme that encrypts random data, so the encryption becomes +superfluous and may be omitted. +\end{proof} + +We may now conclude that Taler remains unlinkable even with the refresh protocol. + +\begin{theorem} +In the random oracle model, any PPT adversary with an advantage +in linking Taler coins has an advantage in breaking elliptic curve +Diffie-Hellman key exchange on Curve25519. +\end{theorem} + +We do not distinguish between information known by the exchange and +information known by the merchant in the above. As a result, this +proves that out linking protocol \S\ref{subsec:linking} does not +degrade privacy. We note that the exchange could lie in the linking +protocol about the transfer public key to generate coins that it can +link (at a financial loss to the exchange that it would have to square +with its auditor). However, in the normal course of payments the link +protocol is never used. + +\subsection{Exculpability arguments} + +\begin{lemma} +The exchange can detect and prove double-spending. +\end{lemma} + +\begin{proof} +\end{proof} + +\begin{lemma} +Merchants and customers can verify double-spending proofs. +\end{lemma} + +\begin{proof} +\end{proof} + + +\begin{lemma} +Customers can either obtain proof-of-payment or their money back. +\end{lemma} + +\begin{proof} +\end{proof} + +\begin{lemma} +If a customer paid for a contract, they can prove it. +\end{lemma} + +\begin{proof} +\end{proof} + +\begin{lemma} +The merchant can issue refunds, and only to the original customer. +\end{lemma} + +\begin{proof} +\end{proof} + + + +\begin{theorem} + The protocol prevents double-spending and provides exculpability. +\end{theorem} @@ -1184,32 +1414,32 @@ certification process. \caption{Outgoing traffic from the exchange, in bytes per 5 minutes.} \label{fig:out} \end{figure} - \begin{subfigure}{0.45\columnwidth} + \begin{figure}[b!] \includegraphics[width=\columnwidth]{db_read.png} \caption{DB read operations per second.} \label{fig:read} - \end{subfigure} - \begin{subfigure}{0.45\columnwidth} + \end{figure} + \begin{figure}[b!] \includegraphics[width=\columnwidth]{db_write.png} \caption{DB write operations per second.} \label{fig:write} - \end{subfigure} - \begin{subfigure}{0.45\columnwidth} + \end{figure} + \begin{figure}[b!] \includegraphics[width=\columnwidth]{cpu_balance.png} \caption{CPU credit balance. Hitting a balance of 0 shows the CPU is the limiting factor.} \label{fig:cpu} - \end{subfigure}\hfill - \begin{subfigure}{0.45\columnwidth} + \end{figure} + \begin{figure}[b!] \includegraphics[width=\columnwidth]{cpu_usage.png} \caption{CPU utilization. The t2.micro instance is allowed to use 10\% of one CPU.} \label{fig:usage} - \end{subfigure} - \caption{Selected EC2 performance monitors for the experiment in the EC2 - (after several hours, once the system was ``warm'').} - \label{fig:ec2} -\end{figure} + \end{figure} +% \caption{Selected EC2 performance monitors for the experiment in the EC2 +% (after several hours, once the system was ``warm'').} +% \label{fig:ec2} +%\end{figure} We ran the Taler exchange v0.0.2 on an Amazon EC2 t2.micro instance (10\% of a Xeon E5-2676 at 2.4 GHz) based on Ubuntu 14.04.4 LTS, using @@ -1359,7 +1589,7 @@ We thank people (anonymized). \newpage \bibliographystyle{ACM-Reference-Format} -\bibliography{taler} +\bibliography{taler,rfc,ro} %\end{document} @@ -1451,228 +1681,6 @@ data being persisted are represented in between $\langle\rangle$. \item[$\overline{C^{(i)}_p}$]{Public coin keys computed from $\overline{c_s^{(i)}}$ by the verifier} \end{description} -\newpage -\section{Taxability arguments} - -We assume the exchange operates honestly when discussing taxability. -We feel this assumption is warranted mostly because a Taler exchange -requires licenses to operate as a financial institution, which it -risks loosing if it knowingly facilitates tax evasion. -We also expect an auditor monitors the exchange similarly to how -government regulators monitor financial institutions. -In fact, our auditor software component gives the auditor read access -to the exchange's database, and carries out test operations anonymously, -which expands its power over conventional auditors. - -\begin{proposition} -Assuming the exchange operates the refresh protocol honestly, -a customer operating the refresh protocol dishonestly expects to -loose $1 - {1 \over \kappa}$ of the value of their coins. -\end{proposition} - -\begin{proof} -An honest exchange keeps any funds being refreshed if the reveal -phase is never carried out, does not match the commitment, or shows -an incorrect commitment. As a result, a customer dishonestly -refreshing a coin looses their money if they have more than one -dishonest commitment. If they make exactly one dishonest -commitment, they have a $1 \over \kappa$ chance of their -dishonest commitment being selected for the refresh. -\end{proof} - -We say a coin $C$ is {\em controlled} by a user if the user's wallet knows -its secret scalar $c_s$, the signature $S$ of the appropriate denomination -key on its public key $C_s$, and the residual value of the coin. - -We assume the wallet cannot loose knowledge of a particular coin's -key material, and the wallet can query the exchange to learn the -residual value of the coin, so a wallet cannot loose control of -a coin. A wallet may loose the monetary value associated with a coin -if another wallet spends it however. - -We say a user Alice {\em owns} a coin $C$ if only Alice's wallets can -gain control of $C$ using standard interactions with the exchange. -In other words, ownership means exclusive control not just in the -present, but in the future even if another user interacts with the -exchange. - -\begin{theorem} -Let $C$ denote a coin controlled by users Alice and Bob. -Suppose Bob creates a coin $C'$ from $C$ following the refresh protocol. -Assuming the exchange and Bob operated the refresh protocol correctly, -and that the exchange continues to operate the linking protocol -(\S\ref{subsec:linking}) correctly, -then Alice can gain control of $C'$ using the linking protocol. -\end{theorem} - -\begin{proof} -Alice may run the linking protocol to obtain all transfer keys $T^i$, -bindings $B^i$ associated to $C$, and those coins denominations, -including the $T'$ for $C'$. - -We assumed both the exchange and Bob operated the refresh protocol -correctly, so now $c_s T'$ is the seed from which $C'$ was generated. -Alice rederives both $c_s$ and the blinding factor to unblind the -denomination key signature on $C'$. Alice finally asks the exchange -for the residual value on $C'$ and runs the linking protocol to -determine if it was refreshed too. -\end{proof} - -\begin{corollary} - Abusing the refresh protocol to transfer ownership has an - expected loss of $1 - \frac{1}{\kappa}$ of the transaction value. -\end{corollary} - - -\section{Privacy arguments} - -The {\em linking problem} for blind signature is, -if given coin creation transcripts and possibly fewer -coin deposit transcripts for coins from the creation transcripts, -then produce a corresponding creation and deposit transcript. - -We say a probabilistic polynomial time (PPT) adversary -{\em links} coins if it has a non-negligible advantage in -solving the linking problem, when given the private keys -of the exchange. - -In Taler, there are two forms of coin creation transcripts, -withdrawal and refresh. - -\begin{lemma} -If there are no refresh operations, any adversary with an -advantage in linking coins is polynomially equivalent to an -advantage with the same advantage in recognizing blinding factors. -\end{lemma} - -\begin{proof} -Let $n$ denote the RSA modulus of the denomination key. -Also let $d$ and $e$ denote the private and public exponents, respectively. -In effect, coin withdrawal transcripts consist of numbers -$b m^d \mod n$ where $m$ is the FDH of the coin's public key -and $b$ is the blinding factor, while coin deposits transcripts -consist of only $m^d \mod n$. - -Of course, if the adversary can link coins then they can compute -the blinding factors as $b m^d / m^d \mod n$. Conversely, if the -adversary can recognize blinding factors then they link coins after -first computing $b_{i,j} = b_i m_i^d / m_j^d \mod n$ for all $i,j$. -\end{proof} - -We now know the following because Taler uses SHA512 adopted to be - a FDH to be the blinding factor. - -\begin{corollary} -Assuming no refresh operation, -any PPT adversary with an advantage for linking Taler coins gives -rise to an adversary with an advantage for recognizing SHA512 output. -\end{corollary} - -We will now consider the impact of the refresh operation. For the -sake of the argument, we will first consider an earlier -encryption-based version of the protocol in which refresh operated -consisted of $\kappa$ normal coin withdrawals where the commitment -consisted of the blinding factors and private keys of the fresh coins -encrypted using the secret $t^{(i)} C_s$ where $C_s = c_s G$ of the -dirty coin $C$ being refreshed and $T^{(i)} = t^{(i)} G$ is the -transfer key.\footnote{We abandoned that version as it required - slightly more storage space and the additional encryption - primitive.} - -\begin{proposition} -Assuming the encryption used is ??? secure, and that - the independence of $c_s$, $t$, and the new coins' key materials, then -any PPT adversary with an advantage for linking Taler coins gives -rise to an adversary with an advantage for recognizing SHA512 output. -\end{proposition} - -% TODO: Is independence here too strong? - -We may now remove the encrpytion by appealing to the random oracle -model~\cite{BR-RandomOracles}. - -\begin{lemma}[\cite{??}] -Consider a protocol that commits to random data by encrypting it -using a secret derived from a Diffe-Hellman key exchange. -In the random oracle model, we may replace this encryption with -a hash function which derives the random data by applying hash -functions to the same secret. -\end{lemma} - -\begin{proof} -We work with the usual instantiation of the random oracle model as -returning a random string and placing it into a database for future -queries. - -We take the random number generator that drives this random oracle -to be the random number generator used to produce the random data -that we encrypt in the old encryption based version of Taler. -Now our random oracle scheme gives the same result as our scheme -that encrypts random data, so the encryption becomes superfluous -and may be omitted. -\end{proof} - -We may now conclude that Taler remains unlinkable even with the refresh protocol. - -\begin{theorem} -In the random oracle model, any PPT adversary with an advantage -in linking Taler coins has an advantage in breaking elliptic curve -Diffie-Hellman key exchange on Curve25519. -\end{theorem} - -We do not distinguish between information known by the exchange and -information known by the merchant in the above. As a result, this -proves that out linking protocol \S\ref{subsec:linking} does not -degrade privacy. We note that the exchange could lie in the linking -protocol about the transfer public key to generate coins that it can -link (at a financial loss to the exchange that it would have to square -with its auditor). However, in the normal course of payments the link -protocol is never used. - -\section{Exculpability arguments} - -\begin{lemma} -The exchange can detect and prove double-spending. -\end{lemma} - -\begin{proof} -\end{proof} - -\begin{lemma} -Merchants and customers can verify double-spending proofs. -\end{lemma} - -\begin{proof} -\end{proof} - - -\begin{lemma} -Customers can either obtain proof-of-payment or their money back. -\end{lemma} - -\begin{proof} -\end{proof} - -\begin{lemma} -If a customer paid for a contract, they can prove it. -\end{lemma} - -\begin{proof} -\end{proof} - -\begin{lemma} -The merchant can issue refunds, and only to the original customer. -\end{lemma} - -\begin{proof} -\end{proof} - - - -\begin{theorem} - The protocol prevents double-spending and provides exculpability. -\end{theorem} - \end{document} |