cr.yp.to update

 2005-501.html      |  202 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 ecdh.html          |    4 -
 ecdh/reports.html  |    3 
 streamciphers.html |   18 +++-
 4 files changed, 220 insertions(+), 7 deletions(-)
New: cr.yp.to/2005-501
diff -ru .old-crypto/2005-501.html cr.yp.to/2005-501.html
--- .old-crypto/2005-501.html	2005-09-13 02:56:48.000000000 -0400
+++ cr.yp.to/2005-501.html	2005-09-25 15:09:24.000000000 -0400
@@ -264,5 +264,220 @@
 If you're interested in achieving multiplication depth Theta(lg n)
 rather than Theta((lg n)^2),
 look up ``Wallace trees.''
+<h2>25 September 2005</h2>
+There are several ways to view the fast Fourier transform (FFT).
+I presented it as a method of multiplying polynomials:
+specifically, an algorithm
+to multiply two polynomials with complex coefficients mod x^n-1,
+where n is a power of 2.
+<p>
+The FFT is an ``algebraic algorithm'':
+it produces the output coefficients
+using complex additions, complex subtractions, and complex multiplications
+starting from the input coefficients and various constants.
+I took ``algebraic complexity'' as my cost measure;
+this is the total number of additions, subtractions, and multiplications.
+This cost measure avoids the question
+of how complex numbers are represented inside a computer,
+and the question of how much time is used by a complex operation.
+<p>
+The FFT is given two size-n polynomials u,v
+and produces the size-n polynomial w = uv mod x^n-1.
+In more detail, the FFT has two inputs:
+a sequence (u[0],u[1],u[2],...,u[n-1]) of n complex numbers
+representing the polynomial u = u[0] + u[1]x + u[2]x^2 + ... + u[n-1]x^{n-1},
+and a sequence (v[0],v[1],v[2],...,v[n-1]) of n complex numbers
+representing the polynomial v = v[0] + v[1]x + v[2]x^2 + ... + v[n-1]x^{n-1}.
+The FFT has one output:
+a sequence (w[0],w[1],w[2],...,w[n-1]) of n complex numbers
+representing
+the unique polynomial w = w[0] + w[1]x + w[2]x^2 + ... + w[n-1]x^{n-1}
+of degree below n
+such that w-uv is a multiple of x^n-1.
+<p>
+The FFT output can be described without polynomials
+as the ``cyclic convolution'' of the inputs:
+<ul>
+<li>the first output w[0] is u[0]v[0]+u[1]v[n-1]+u[2]v[n-2]+...+u[n-1]v[1];
+<li>the second output w[1] is u[0]v[1]+u[1]v[0]+u[2]v[n-1]+...+u[n-1]v[2];
+<li>the third output w[2] is u[0]v[2]+u[1]v[1]+u[2]v[0]+...+u[n-1]v[3];
+<li>...
+<li>the last output w[n-1]
+is u[0]v[n-1]+u[1]v[n-2]+u[2]v[n-3]+...+u[n-1]v[0].
+</ul>
+<p>
+For example, for n=2,
+the inputs are two complex vectors (u[0],u[1]) and (v[0],v[1])
+representing the linear polynomials u = u[0]+u[1]x and v = v[0]+v[1]x.
+The output is the complex vector
+(w[0],w[1])=(u[0]v[0]+u[1]v[1],u[0]v[1]+u[1]v[0])
+representing the linear polynomial
+w = w[0]+w[1]x = (u[0]v[0]+u[1]v[1])+(u[0]v[1]+u[1]v[0])x
+= uv - u[1]v[1](x^2-1).
+<p>
+As a larger example, for n=4,
+the inputs are two complex vectors (u[0],u[1],u[2],u[3])
+and (v[0],v[1],v[2],v[3])
+representing the polynomials
+u = u[0]+u[1]x+u[2]x^2+u[3]x^3
+and v = v[0]+v[1]x+v[2]x^2+v[3]x^3.
+The product uv is
+(u[0]v[0])
++ (u[0]v[1]+u[1]v[0])x
++ (u[0]v[2]+u[1]v[1]+u[2]v[0])x^2
++ (u[0]v[3]+u[1]v[2]+u[2]v[1]+u[3]v[0])x^3
++ (u[1]v[3]+u[2]v[2]+u[3]v[1])x^4
++ (u[2]v[3]+u[3]v[2])x^5
++ (u[3]v[3])x^6,
+so uv mod x^4-1 is
+uv - 
+((u[1]v[3]+u[2]v[2]+u[3]v[1])
++ (u[2]v[3]+u[3]v[2])x
++ (u[3]v[3])x^2)(x^4-1)
+= (u[0]v[0]+u[1]v[3]+u[2]v[2]+u[3]v[1])
++ (u[0]v[1]+u[1]v[0]+u[2]v[3]+u[3]v[2])x
++ (u[0]v[2]+u[1]v[1]+u[2]v[0]+u[3]v[3])x^2
++ (u[0]v[3]+u[1]v[2]+u[2]v[1]+u[3]v[0])x^3.
+The output is the vector
+(u[0]v[0]+u[1]v[3]+u[2]v[2]+u[3]v[1],u[0]v[1]+u[1]v[0]+u[2]v[3]+u[3]v[2],u[0]v[2]+u[1]v[1]+u[2]v[0]+u[3]v[3],u[0]v[3]+u[1]v[2]+u[2]v[1]+u[3]v[0]).
+<p>
+The idea of the FFT, in a nutshell,
+is to compute uv mod x^n-1 
+from uv mod x^(n/2)-1 and uv mod x^(n/2)+1,
+each of which is computed recursively.
+In more detail:
+<ol>
+<li>If n=1: Compute u[0]v[0] and stop.
+<li>Compute u mod x^(n/2)-1.
+<li>Compute v mod x^(n/2)-1.
+<li>Recursively multiply mod x^(n/2)-1,
+obtaining (u mod x^(n/2)-1)(v mod x^(n/2)-1) mod x^(n/2)-1
+= uv mod x^(n/2)-1.
+<li>Compute u mod x^(n/2)+1.
+<li>Compute v mod x^(n/2)+1.
+<li>Recursively multiply mod x^(n/2)+1,
+obtaining (u mod x^(n/2)+1)(v mod x^(n/2)+1) mod x^(n/2)+1
+= uv mod x^(n/2)+1.
+<li>Compute
+((uv mod x^(n/2)-1)+(uv mod x^(n/2)+1))/2
++ x^(n/2)((uv mod x^(n/2)-1)-(uv mod x^(n/2)+1))/2,
+which is exactly uv mod x^n-1.
+</ol>
+There's a gap in this recursion:
+how does one multiply mod x^(n/2)+1?
+One solution is to generalize the FFT
+to x^n-c^2 for any nonzero complex number c:
+<ol>
+<li>If n=1: Compute u[0]v[0] and stop.
+<li>Compute u mod x^(n/2)-c.
+This polynomial is represented by the vector
+(u[0]+u[n/2]c,u[1]+u[n/2+1]c,...u[n/2-1]+u[n-1]c);
+computing this vector takes n/2 multiplications by c
+and n/2 additions.
+<li>Compute v mod x^(n/2)-c.
+<li>Recursively multiply mod x^(n/2)-c,
+obtaining uv mod x^(n/2)-c.
+<li>Compute u mod x^(n/2)+c.
+This polynomial is represented by the vector
+(u[0]-u[n/2]c,u[1]-u[n/2+1]c,...u[n/2-1]-u[n-1]c);
+computing this vector takes n/2 subtractions,
+reusing the previous products u[n/2]c etc.
+<li>Compute v mod x^(n/2)+c.
+<li>Recursively multiply mod x^(n/2)+c,
+obtaining uv mod x^(n/2)+c.
+<li>Compute
+((uv mod x^(n/2)-c)+(uv mod x^(n/2)+c))/2
++ x^(n/2)((uv mod x^(n/2)-c)-(uv mod x^(n/2)+c))/2c,
+which is exactly uv mod x^n-c^2.
+This takes n/2 additions, n/2 subtractions,
+n/2 divisions by 2,
+and n/2 divisions by 2c.
+</ol>
+<p>
+The FFT has algebraic complexity 5n lg n + n:
+<ul>
+<li>(3/2)n lg n additions;
+<li>(3/2)n lg n subtractions;
+<li>n lg n multiplications by constants
+(many of which are 1 and thus can be eliminated);
+<li>n lg n divisions by nonzero constants
+(half of which are divisions by 2, i.e., multiplications by 1/2,
+which can be combined with subsequent multiplications); and
+<li>n multiplications at the bottom of the recursion.
+</ul>
+For comparison,
+the obvious algorithm has algebraic complexity 2n^2-n:
+specifically, n^2 multiplications and n^2-n additions.
+<p>
+Homework due 28 September 2005
+is to analyze in more detail the n lg n multiplications by constants.
+How many of the n lg n constants are primitive 4th roots of 1, namely i or -i?
+How many of the n lg n constants are primitive 8th roots of 1,
+namely sqrt(i), -sqrt(i), sqrt(-i), or -sqrt(-i)?
+(For example,
+there are 4 multiplications by primitive 8th roots of 1 if n=8,
+and 12 multiplications by primitive 8th roots of 1 if n=16;
+of course, your answer should cover all values of n.)
+Same question for 16th, 32nd, etc.
+<p>
+I also described another solution to the problem
+of handling x^(n/2)+1 recursively:
+namely,
+to ``twist'' the multiplication mod x^(n/2)+1
+into a multiplication mod x^(n/2)-1.
+A careful combination of these two solutions
+produces the ``split-radix FFT,''
+which is about 20% faster than the original solutions,
+and which held the speed records for decades;
+see, e.g., Section 2 of my paper
+<a href="lineartime/multapps-20041007.pdf">``Fast multiplication
+and its applications.''</a>
+Last year, Van Buskirk introduced what I call the ``tangent FFT,''
+which is about 5% faster than the split-radix FFT;
+see the paper
+<a href="2005-501/johnson.pdf">``A modified split-radix FFT
+with reduced arithmetic complexity''</a>
+by Johnson and Frigo.
+<p>
+I then explained one way to use the FFT for integer multiplication.
+The problem is
+to multiply the integers u[0] + 2u[1] + 4u[2] + ...
+and v[0] + 2v[1] + 4v[2] + ...,
+given bits u[0],v[0],u[1],v[1],...;
+the basic idea is to
+multiply the polynomials
+u[0] + u[1]x + u[2]x^2 + ...
+and v[0] + v[1]x + v[2]x^2 + ...
+using the FFT.
+There are three complications in making this work:
+<ul>
+<li>The FFT computes uv mod x^n-1.
+What we actually want is the polynomial product uv.
+Solution (easy):
+choose n as a power of 2 known to be larger than the degree of uv;
+then uv mod x^n-1 is exactly uv.
+<li>The polynomial product has O(lg n) bits in each coefficient;
+what we actually want is 1 bit in each coefficient.
+In other words, we still have to do carries.
+Solution (fairly easy):
+split the polynomial coefficients into O(lg n) integers,
+each having O(n) bits;
+add those integers.
+<li>The cost measure is different.
+The FFT uses n^(1+o(1)) additions, subtractions, and multiplications;
+what we actually want is n^(1+o(1)) low-level machine instructions.
+Solution (natural but difficult):
+choose a floating-point precision, let's say 3 lg n bits;
+represent each real number
+inside the computer as a nearby floating-point number;
+prove, by careful numerical analysis,
+that the floating-point FFT output is within 0.25 of
+the integers u[0]v[0], u[0]v[1]+u[1]v[0], etc.,
+allowing those integers to be computed;
+and observe that an n^(o(1))-bit floating-point approximation
+to a complex operation
+uses n^(o(1)) machine instructions.
+</ul>
+Next time I'll explain better solutions to the third complication.
 </body>
 </html>
diff -ru .old-crypto/ecdh/reports.html cr.yp.to/ecdh/reports.html
--- .old-crypto/ecdh/reports.html	2005-09-20 10:32:38.000000000 -0400
+++ cr.yp.to/ecdh/reports.html	2005-09-24 01:00:55.000000000 -0400
@@ -65,6 +65,7 @@
 <tr><td>yes</td><td><a href="speed-20050915-silverton.txt">832457</a></td><td>Pentium III (686)</td><td>2^255-19</td><td>Curve25519</td><td>255</td><td>2^125 additions</td><td>2005 Bernstein</td></tr>
 <tr><td>no</td><td>835530</td><td>Pentium II (652)</td><td>2^224-2^96+1</td><td>NIST P-224</td><td>224</td><td>2^112 additions</td><td>2001 Bernstein</td></tr>
 <tr><td>no</td><td>837000</td><td>Pentium III</td><td>2^163</td><td>NIST B-163</td><td>326</td><td>2^77 additions</td><td>2003 Fong Hankerson Lopez Menezes</td></tr>
+<tr><td>no</td><td>838000</td><td>Athlon</td><td>near 2^160</td><td></td><td>320</td><td>2^80 additions</td><td>2004 Avanzi</td></tr>
 <tr><td>no</td><td>943244</td><td>Pentium 4 (f05)</td><td>2^224-2^96+1</td><td>NIST P-224</td><td>224</td><td>2^112 additions</td><td>2001 Bernstein</td></tr>
 <tr><td>yes</td><td><a href="speed-20050915-frobenius.txt">957904</a></td><td>Pentium 4 (f12)</td><td>2^255-19</td><td>Curve25519</td><td>255</td><td>2^125 additions</td><td>2005 Bernstein</td></tr>
 <tr><td>no</td><td>985097</td><td>Pentium (525)</td><td>2^224-2^96+1</td><td>NIST P-224</td><td>448</td><td>2^112 additions</td><td>2001 Bernstein</td></tr>
@@ -76,10 +77,12 @@
 <tr><td>no</td><td>1200000</td><td>Pentium II</td><td>2^233</td><td>NIST K-233</td><td>466</td><td>2^112 additions</td><td>1999 Lopez Dahab</td></tr>
 <tr><td>no</td><td>1355344</td><td>PowerPC 7410</td><td>2^224-2^96+1</td><td>NIST P-224</td><td>224</td><td>2^112 additions</td><td>2001 Bernstein</td></tr>
 <tr><td>no</td><td>1200000</td><td>UltraSPARC</td><td>2^163</td><td></td><td>326</td><td>2^77 additions</td><td>1998 Certicom</td></tr>
+<tr><td>no</td><td>1395000</td><td>Athlon</td><td>near 2^192</td><td></td><td>384</td><td>2^96 additions</td><td>2004 Avanzi</td></tr>
 <tr><td>no</td><td>1720000</td><td>Pentium III</td><td>2^233</td><td>NIST B-233</td><td>466</td><td>2^112 additions</td><td>2003 Fong Hankerson Lopez Menezes</td></tr>
 <tr><td>no</td><td>1800000</td><td>Pentium</td><td>2^224-2^96+1</td><td>NIST P-224</td><td>448</td><td>2^112 additions</td><td>2000 Brown Hankerson Hernandez Menezes</td></tr>
 <tr><td>no</td><td>2300000</td><td>UltraSPARC</td><td>2^160-2933</td><td></td><td>320</td><td>2^80 additions</td><td>1998 Cohen Miyaji Ono</td></tr>
 <tr><td>no</td><td>2700000</td><td>Pentium 4</td><td>2^224-2^96+1</td><td>NIST P-224</td><td>448</td><td>2^112 additions</td><td>2000 Brown Hankerson Hernandez Menezes</td></tr>
+<tr><td>no</td><td>3048000</td><td>Athlon</td><td>near 2^256</td><td></td><td>512</td><td>2^128 additions</td><td>2004 Avanzi</td></tr>
 <tr><td>no</td><td>3100000</td><td>Pentium</td><td>(2^31-1)^6</td><td></td><td>372</td><td>2^91 additions</td><td>1999 Bailey Paar</td></tr>
 <tr><td>no</td><td>3600000</td><td>UltraSPARC</td><td>2^192-3345</td><td></td><td>384</td><td>2^96 additions</td><td>1998 Cohen Miyaji Ono</td></tr>
 <tr><td>no</td><td>4100000</td><td>UltraSPARC</td><td>2^163</td><td></td><td>326</td><td>2^77 additions</td><td>1999 Lopez Dahab</td></tr>
diff -ru .old-crypto/ecdh.html cr.yp.to/ecdh.html
--- .old-crypto/ecdh.html	2005-09-20 06:38:40.000000000 -0400
+++ cr.yp.to/ecdh.html	2005-09-24 07:08:23.000000000 -0400
@@ -142,9 +142,9 @@
 -1,
 and infinity.
 <h2><a name="papers">Where can I learn more about Curve25519?</a></h2>
-I've given a talk on Curve25519 at ECC 2005:
+I gave a talk on Curve25519 at ECC 2005:
 <a href="talks.html#2005.09.20">2005.09.20</a>.
-I've also given a short talk discussing the 255-bit security level:
+I also gave a short talk discussing the 255-bit security level:
 <a href="talks.html#2005.09.19">2005.09.19</a>.
 </body>
 </html>
diff -ru .old-crypto/streamciphers.html cr.yp.to/streamciphers.html
--- .old-crypto/streamciphers.html	2005-09-13 15:57:58.000000000 -0400
+++ cr.yp.to/streamciphers.html	2005-09-24 02:25:49.000000000 -0400
@@ -6,8 +6,15 @@
 <a href="djb.html">D. J. Bernstein</a>
 <br><a href="hash.html">Hash functions and ciphers</a>
 <h1>Notes on the ECRYPT Stream Cipher project (eSTREAM)</h1>
+<a href="#intro">Introduction</a>
+<br><a href="#table">Table of submissions</a>
+<br><a href="#vsaes">Advantages over AES</a>
+<br><a href="#authspeed">Notes on authentication speed</a>
+<br><a href="#patents">Notes on patented submissions</a>
+<hr>
 <a href="streamciphers/20050614-abbreviations.txt">Abbreviating the stream-cipher discussions</a>
 <hr>
+<h2><a name="intro">Introduction</a></h2>
 ECRYPT
 (<a href="http://www.ecrypt.eu.org">www.ecrypt.eu.org</a>),
 a consortium of European research organizations,
@@ -25,6 +32,7 @@
 <li><a href="http://www.ecrypt.eu.org/stream/phorum">www.ecrypt.eu.org/stream/phorum</a>, a public discussion area;
 <li><a href="http://www.ecrypt.eu.org/stream/call">www.ecrypt.eu.org/stream/call</a>, the original call for submissions.
 </ul>
+<h2><a name="table">Table of submissions</a></h2>
 Here's my own list of the submissions:
 <table border>
 <tr><th>Name</th><th>Key size</th><th>Authors; policy</th><th>Documents</th></tr>
@@ -73,7 +81,7 @@
 <tr><td>YAMB</td><td>32 bytes</td><td>Anatoly N. Lebedev, Alexander Ivanov, Sergey Starodubtzev, Alexey Kolchkov</td><td><a href="streamciphers/yamb/yamb.c">C</a> <a href="streamciphers/yamb/desc.pdf">paper</a></td></tr>
 <tr><td>ZK-Crypt</td><td></td><td>Carmi Gressel, Ran Granot, Gabi Vago; <b>patented</b></td><td></td></tr>
 </table>
-<p>
+<h2><a name="vsaes">Advantages over AES</a></h2>
 Why is it reasonable to believe that a new design process
 will produce better results than the AES design process?
 Here are two reasons:
@@ -95,7 +103,7 @@
 constant-time high-speed AES software for modern CPUs.
 </ul>
 A new cipher can avoid these structural errors.
-<h2>Notes on authentication speed</h2>
+<h2><a name="authspeed">Notes on authentication speed</a></h2>
 Most stream ciphers are purely for encryption.
 Applications need authentication,
 so these stream ciphers need to be combined with authentication mechanisms,
@@ -135,7 +143,7 @@
 and the underlying pure-encryption stream cipher
 should be evaluated on its own merits.
 Phelix, on the other hand, can't be separated in this way.
-<h2>Notes on patented submissions</h2>
+<h2><a name="patents">Notes on patented submissions</a></h2>
 DECIM, Frogbit, Fubuki, Rabbit, VEST, and ZK-Crypt
 are patented.
 <p>
@@ -542,8 +550,8 @@
 by secret-index table lookups,
 creating timing-attack problems.
 <p>
-Khazaei writes: ``... a distinguishing attack
-with data, time and memory complexities of O(2^32) could be applied.''
+Khazaei and Kiaei write: ``we ... mount a distinguishing attack
+on both versions of ABC with data, time and memory complexities of O(2^32).''
 <b>No response yet from the authors.</b>
 <h2>Notes on DECIM version 1 (patented) (withdrawn)</h2>
 10-byte key.