D. J. Bernstein

Authenticators and signatures


MCS 590, High-Speed Cryptography, Spring 2005

[forgery] 15pp. (PDF) D. J. Bernstein. Protecting communications against forgery. Document ID: 9774ae5a1749a7b256cc923a7ef9d4dc. URL: http://cr.yp.to/papers.html#forgery. Date: 2008.05.01. Supersedes: (PDF) 2007.07.20. (PDF) (PS) (DVI) 2004.09.06. (PDF) (PS) (DVI) 2003.09.22. (PDF) (PS) (DVI) 2001.07.31.

Relevant talks: 2000.08.18 (slides and video available), ``Protecting communications against forgery.'' 2002.06.15 (slides available), ``Speed records for cryptographic software: an update.''

Exponentiation and scalar multiplication

See also newelliptic, joint work with Tanja Lange; and (off-site) the Explicit-Formulas Database, joint work with Tanja Lange.

[efd] 19pp. (PDF) D. J. Bernstein, Tanja Lange. Analysis and optimization of elliptic-curve single-scalar multiplication. URL: http://cr.yp.to/papers.html#efd. Document ID: 8ac889630fe4d44913b92cc5914aa01b. Date: 2007.12.04.

[doublebase] 16pp. (PDF) D. J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. Optimizing double-base elliptic-curve single-scalar multiplication. URL: http://cr.yp.to/papers.html#doublebase. Document ID: d721c86c47e3b56834ded945c814b5e0. Date: 2007.10.28.

[meecrt] 12pp. (PDF, AMS version) (PDF) (PS) (DVI) D. J. Bernstein, Jonathan P. Sorenson. Modular exponentiation via the explicit Chinese remainder theorem. URL: http://cr.yp.to/papers.html#meecrt. Supersedes: (PDF) (PS) (DVI) 2003.08.15. Also supersedes: (PDF) (PS) (DVI) D. J. Bernstein. Multidigit modular multiplication with the Explicit Chinese Remainder Theorem. Chapter 4, Ph.D. thesis, University of California at Berkeley, May 1995.

Relevant talks: 1995.05, multidigit modular multiplication with ECRT.

[pippenger] 21pp, draft. (PDF) (PS) (DVI) D. J. Bernstein. Pippenger's exponentiation algorithm. URL: http://cr.yp.to/papers.html#pippenger.

Public-key signatures

A state-of-the-art public-key signature system

Zmodexp: compute modular integer powers

Public-key secret sharing

A state-of-the-art Diffie-Hellman function: the Curve25519 function, the curve25519 paper, etc.

The future of Diffie-Hellman functions

nistp224: share secret keys using the NIST P-224 elliptic curve (superseded by Curve25519)

[sqroot] 10pp, draft. (PDF) (PS) (DVI) D. J. Bernstein. Faster square roots in annoying finite fields. URL: http://cr.yp.to/papers.html#sqroot.

Secret-key authentication

[pema] 14pp. (PDF) D. J. Bernstein Polynomial evaluation and message authentication. Document ID: b1ef3f2d385a926123e1517392e20f8c. URL: http://cr.yp.to/papers.html#pema. Date: 2007.10.22.

A state-of-the-art message-authentication code: the Poly1305-AES function, the poly1305 paper, the securitywcs paper, the cachetiming paper, etc.

hash127: compute a secure secret-key authenticator (superseded by Poly1305-AES)

[hash127] 21pp. (PDF) (PS) (DVI) D. J. Bernstein. Floating-point arithmetic and message authentication. Document ID: dabadd3095644704c5cbe9690ea3738e. URL: http://cr.yp.to/papers.html#hash127. Date: 2004.09.18. Supersedes: (PDF) (PS) (DVI) 2000.03.21. [hash127-abs] (PDF) (PS) (DVI) Guaranteed message authentication faster than MD5 (abstract), 1999.04.04.

[stretch] 8pp. (PDF) (PS) (DVI) D. J. Bernstein. How to stretch random functions: the security of protected counter sums. Journal of Cryptology 12 (1999), 185-192. URL: http://cr.yp.to/papers.html#stretch.

[easycbc] 6pp. (PDF) (PS) (DVI) D. J. Bernstein. A short proof of the unpredictability of cipher block chaining. Document ID: 24120a1f8b92722b5e15fbb6a86521a0. URL: http://cr.yp.to/papers.html#easycbc. Date: 2005.01.09. I also have some unpublished work (dating back to 1999) pinning down the security of CBC somewhat more precisely, but those details have no hope of being applied to systems other than CBC; in contrast, the proof strategy in the easycbc paper is very widely applicable.

Relevant talks: 1999.06.13, ``Guaranteed message authentication faster than MD5.''