diff options
Diffstat (limited to 'doc')
-rw-r--r-- | doc/paper/ro.bib | 74 | ||||
-rw-r--r-- | doc/paper/taler.tex | 85 |
2 files changed, 138 insertions, 21 deletions
diff --git a/doc/paper/ro.bib b/doc/paper/ro.bib new file mode 100644 index 000000000..d85b2e891 --- /dev/null +++ b/doc/paper/ro.bib @@ -0,0 +1,74 @@ + + + + +@inproceedings{BR-RandomOracles, + dblp = {DBLP:conf/ccs/BellareR93}, + author = {Mihir Bellare and + Phillip Rogaway}, + title = {Random Oracles are Practical: {A} Paradigm for Designing Efficient + Protocols}, + booktitle = {{CCS} '93, Proceedings of the 1st {ACM} Conference on Computer and + Communications Security, Fairfax, Virginia, USA, November 3-5, 1993.}, + pages = {62--73}, + year = {1993}, + crossref = {DBLP:conf/ccs/1993}, + url = {http://doi.acm.org/10.1145/168588.168596}, + doi = {10.1145/168588.168596}, + timestamp = {Fri, 23 Dec 2011 14:54:25 +0100}, + biburl = {http://dblp.uni-trier.de/rec/bib/conf/ccs/BellareR93}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@proceedings{DBLP:conf/ccs/1993, + editor = {Dorothy E. Denning and + Raymond Pyle and + Ravi Ganesan and + Ravi S. Sandhu and + Victoria Ashby}, + title = {{CCS} '93, Proceedings of the 1st {ACM} Conference on Computer and + Communications Security, Fairfax, Virginia, USA, November 3-5, 1993}, + publisher = {{ACM}}, + year = {1993}, + url = {http://dl.acm.org/citation.cfm?id=168588}, + isbn = {0-89791-629-8}, + timestamp = {Fri, 09 Dec 2011 14:34:06 +0100}, + biburl = {http://dblp.uni-trier.de/rec/bib/conf/ccs/1993}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + + + + +@inproceedings{Rudich88, + dblp = {DBLP:conf/crypto/ImpagliazzoR88}, + author = {Russell Impagliazzo and + Steven Rudich}, + title = {Limits on the Provable Consequences of One-way Permutations}, + booktitle = {Advances in Cryptology - {CRYPTO} '88, 8th Annual International Cryptology + Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings}, + pages = {8--26}, + year = {1988}, + crossref = {DBLP:conf/crypto/1988}, + url = {http://dx.doi.org/10.1007/0-387-34799-2_2}, + doi = {10.1007/0-387-34799-2_2}, + timestamp = {Fri, 18 Sep 2009 08:51:10 +0200}, + biburl = {http://dblp.uni-trier.de/rec/bib/conf/crypto/ImpagliazzoR88}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@proceedings{DBLP:conf/crypto/1988, + editor = {Shafi Goldwasser}, + title = {Advances in Cryptology - {CRYPTO} '88, 8th Annual International Cryptology + Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings}, + series = {Lecture Notes in Computer Science}, + volume = {403}, + publisher = {Springer}, + year = {1990}, + isbn = {3-540-97196-3}, + timestamp = {Thu, 07 Feb 2002 09:41:39 +0100}, + biburl = {http://dblp.uni-trier.de/rec/bib/conf/crypto/1988}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + + diff --git a/doc/paper/taler.tex b/doc/paper/taler.tex index 4ef76ca63..70378d4f2 100644 --- a/doc/paper/taler.tex +++ b/doc/paper/taler.tex @@ -1377,8 +1377,8 @@ data being persisted are represented in between $\langle\rangle$. \section{Taxability arguments} We assume the exchange operates honestly when discussing taxability. -We feel this assumption is warratned mostly because a Taler exchange -requires liscenses to operate as a financial institution, which it +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. @@ -1389,15 +1389,15 @@ 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 thei coins. +loose $1 - {1 \over \kappa}$ of the value of their coins. \end{proposition} \begin{proof} -An honest esxchange keeps any funds being refreshed if the reveal +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 -dishonet commitment. They have a $1 \over \kappa$ chance of their +dishonest commitment. They have a $1 \over \kappa$ chance of their dishonest commitment being selected for the refresh. \end{proof} @@ -1428,7 +1428,7 @@ then Alice can gain control of $C'$ using the linking protocol. \begin{proof} Alice may run the linking protocol to obtain all transfer keys $T^i$, -blindings $B^i$ associated to $C$, and those coins denominations, +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 @@ -1444,30 +1444,73 @@ At a result, there is no way for a user to loose control over a coin, \section{Privacy arguments} -We consider two coins $C_1$ and $C_2$ created by the same withdrawal -or refresh operation. We say they are {\em linkable} if -some probabilistic polynomial time adversary has a non-negligible -advantage in guessing which two of $\{ C_0, C_1, C_2 \}$ were -created together, where $C_0$ is an unrelated third coin. +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. -% TODO: Compare this definition with some from the literature +We say a probabilistic polynomial time (PPT) adversary $A$ +{\em links} coins if it has a non-negligible advantage in +solving the linking problem, when given the private keys +of the exchange. -.. reference literate about withdrawal .. +In Taler, there are two forms of coin creation transcripts, +withdrawal and refresh. -\begin{proposition} -If two coins created by refresh are linkable, then some -probabilistic polynomial time adversary has a non-negligible -advantage in determining that their seeds ... -... -\end{proposition} +\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} -... random oracle .. +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 \mon 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 used 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} + +There was an earlier encryption-based version of the Taler protocol +in which refresh operated consisted of $\kappa$ normal coin withdrawals +encrypted using the secret $t^{(i)} C$ where $C = c G$ is the coin being +refreshed and $T^{(i)} = t^{(i)} G$ is the transfer key. + +\begin{proposition} +Assuming the encryption used is ??? secure, and that + the independence of $c$, $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} + +We now apply \cite[??]{??} to deduce : + +\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. -\end{document} |