Some classical random oracle reference

2 files changed, 74 insertions, 90 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/trash b/doc/paper/trash
deleted file mode 100644
index ced86833a..000000000
--- a/doc/paper/trash
+++ /dev/null
@@ -1,90 +0,0 @@
-
-
-
-\begin{proposition}
-If there are no refresh operations, then any adversary who links
-coins can recognize blinding factors.
-\end{proposition}
-
-\begin{proof}
-In effect, coin withdrawal transcripts consist of numbers $b m^d \mod n$
-
-The blinding factor is created with a full domain hash 
-\end{proof}
-
-
-We say a blind signature 
-linkable if some probabilistic polynomial 
-time (PPT) adversary has a non-negligible advantage indentifying
-the 
-
-
-, given some withdrawal and refresh
-transcripts
-
- 
-
-
-
-We say a coin $C_0$ is {\em linkable} to the withdrawal or refresh
-operation in which it was created if some probabilistic polynomial 
-time (PPT) adversary has a non-negligible advantage in guessing
-which of $\{ C_0, C_1 \}$ were created in that operation,
- where $C_1$ is an unrelated third coin.
-
-% TODO: Compare this definition with some from the literature
-% TODO: Should this definition be broadened?
-
-.. reference literate about withdrawal ..
-
-\begin{proposition}
-In the random oracle model, 
-if a coin created by refresh is linkable to the refresh operation
-that created it, then some PPT adversary has a non-negligible
-advantage in determining the shared secret of an eliptic curve 
-Diffie-Hellman key exchange on curve25519.
-\end{proposition}
-
-% Intuitively this follows from \cite{Rudich88}[Theorem 4.1], but
-% we provide slightly more formality.
-
-\begin{proof}
-Assume a PPT adversary $A$ has a non-negligible advantage in solving
-the linking problem.
-
-We have two curve points $C = c G$ and $T = t G$ for which
-we wish to compute the shared secret $c t G$.
-
-We make $C$ into a coin by singing it with a denomination key
-invented for this purpose.  We let $T^{(1)}$ denote $T$ and
-invent $\kappa-1$ linking keys $T^{(2)},\ldots,T^{(\kappa)}$.
-
-We shall extract the shared secret by constructing an algorithm
-that runs the refresh protocol and then runs $A$ using the natural
-simulation of a random oracle, namely answering new queries with
-random bits, yet recording the answers in a database so as to
-provide idendical answers to identical queries.
-
-We may take $\gamma=1$ by restarting the exchange with a clean
-database.  As a result, the exchange never checks the commitment
-covering $T^{(1)}$, but this alone does not suffice to discount
-the any information contained in the commitment.  
-
-Instead, we observe that our commitments consist of random oracle
-queries distinct from anything else in the protocol, so they contain
-no information of use to $A$, and can safely be omitted.
-
-We do not know $c t G$ so our simulation cannot run the KDF to
-derive the new coin that $A$ can link.  
-
-
-... random oracle ..
-\end{proof}
-
-In principle, one might worry if coins created in the same withdrawal
-or refresh opeartion might be linkable to one another without being
-linkable to the operation, but addressing this concern would take us
-somewhat far afield and require similar methods.
-
-
-