Authenticators and signatures

General

MCS 590, High-Speed Cryptography, Spring 2005

[forgery] 10pp. (PDF) (PS) (DVI) D. J. Bernstein. Protecting communications against forgery. Document ID: 9774ae5a1749a7b256cc923a7ef9d4dc. URL: http://cr.yp.to/papers.html#forgery. Date: 2004.09.06. Supersedes: (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.''

Public-key signatures

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

Zmodexp: compute modular integer powers

[meecrt] 12pp. (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.

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

Relevant talks: 1995.05, multidigit modular multiplication with ECRT.

Public-key secret sharing

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

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

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.''