cr.yp.to update

New: 2005-590/brent.pdf
New: 2005-590/courtois.pdf
New: 2005-590/hong.pdf
New: 2005-590/wiener.pdf
diff -ru .old-crypto/2005-590.html cr.yp.to/2005-590.html
--- .old-crypto/2005-590.html	2005-03-29 20:11:56.000000000 -0500
+++ cr.yp.to/2005-590.html	2005-03-30 21:31:20.000000000 -0500
@@ -566,5 +566,74 @@
 <a href="2005-590/stein.ps">The parallelized Pollard kangaroo method
 in real quadratic function fields</a>,
 Section 2, through the end of 2.2.
+<h2>30 March 2005</h2>
+There is a widespread myth
+that parallelization does not improve price-performance ratio.
+Most of the cryptanalytic literature
+analyzes the time of computations on a huge <i>serial</i> computer,
+as if this said something about the time of a computation
+on a comparably priced <i>parallel</i> computer.
+In fact,
+a parallel computer can achieve price-performance ratios
+several orders of magnitude better than a serial computer.
+<p>
+Consider, for example,
+a computer multiplying two n-bit numbers.
+A <i>serial</i> computer can't possibly do this in time below n^{1+o(1)},
+and it needs n^{1+o(1)} bits of memory.
+A 2-dimensional <i>parallel</i> computer of size n^{1+o(1)}
+can do the job in time n^{1/2+o(1)}.
+The price-performance ratio drops from n^{2+o(1)} dollar-seconds
+to n^{1.5+o(1)} dollar-seconds.
+<p>
+Problems similar to n-bit multiplication
+show up all over the place in cryptanalysis.
+Focusing on serial computers makes the problems sound more difficult
+than they actually are.
+<p>
+It's particularly embarrassing when a ``record-setting'' serial computation
+is slower, more expensive, and much more complicated
+than a well-known parallel computation.
+Here are two examples:
+<ul>
+<li>The Hong-Sarkar paper
+<a href="2005-590/hong.pdf">Rediscovery of time memory tradeoffs</a>
+advertises an algorithm by Hellman that, after a huge precomputation,
+inverts a function with a 128-bit input
+using about 2^86 function evaluations
+on a serial computer with 2^93 bits of fast memory.
+<li>The Courtois paper
+<a href="2005-590/courtois.pdf">Algebraic attacks on combiners
+with memory and several outputs</a>,
+after describing a complicated algorithm
+that performs a particular 544-bit search in roughly 2^534 ``clocks''
+on a serial computer with 2^380 bits of fast memory,
+says that the algorithm is ``faster then [sic] the exhaustive search.''
+</ul>
+A <i>parallel</i> computer that simply
+searches through all 2^128 or 2^534 inputs,
+doing 2^50 function evaluations at once,
+would be vastly less expensive and would finish more quickly,
+so you'd have to be an idiot to use the serial computer.
+Parallel versions of the complicated algorithms
+are better than serial versions,
+and there are some situations where they save time,
+but they are still worse than brute-force search in both of these situations.
+<p>
+One cryptanalytic paper that doesn't make the same mistake
+is Wiener's recent paper
+<a href="2005-590/wiener.pdf">The full cost of cryptanalytic attacks</a>.
+This paper displays a shocking level of ignorance of prior work
+(its main theorem follows trivially
+from a famous theorem in a <a href="2005-590/brent.pdf">1981 paper</a>
+by Brent and Kung, for example)
+but is not bad as an introduction to parallel cryptanalysis.
+In particular,
+Section 4, on parallel discrete-logarithm computations,
+is a good explanation of why the rho method,
+a predecessor to the kangaroo method,
+is better than baby-step-giant-step.
+The Stein-Teske paper is a better introduction to the kangaroo method
+but says only a tiny bit about previous algorithms.
 </body>
 </html>