D. J. Bernstein

Talks

Chronological order. Some statistics:


1987.06.01 10 minutes contributed lecture conference USA
Ramanujan Centenary Conference. University of Illinois at Urbana-Champaign. ``New fast algorithms for pi and e.''

1992.12 contributed lecture conference USA
West Coast Number Theory Conference. Oregon State University, Corvallis. 3x+1 results.

1992.12 contributed lecture conference USA
West Coast Number Theory Conference. Oregon State University, Corvallis. Computing Dickman's rho function.

1994.05.02 45 minutes invited lecture conference Canada
Computational Number Theory. Fields Institute, Waterloo, Ontario. ``Practical aspects of the number field sieve.'' This talk included the first public announcement of the multiple-lattice number field sieve. [nfsi paper] [mlnfs paper]

1994.10.12 invited lecture conference Germany
Algorithms and Number Theory. Schloss Dagstuhl. Preliminary report on detecting perfect powers. [powers paper]

1995.02.06 invited lecture seminar USA
Seminar, Department of Mathematics, Texas A&M University, College Station, Texas. Detecting perfect powers. [powers paper]

1995.03.01 50 minutes invited lecture colloquium USA
Department of Mathematics, Statistics, and Computer Science. University of Illinois at Chicago. Detecting perfect powers. [powers paper]

1995.04.05 50 minutes invited lecture seminar USA
Number Theory Seminar, Department of Mathematics, University of California at Berkeley. ``Detecting perfect powers.'' Abstract: ``Let n be a positive integer. Is n a perfect power? I'll describe an algorithm that answers this question in time (log n)^{1+o(1)}---i.e., about as quickly as we can read the digits of n. The time analysis requires some recent results from transcendental number theory.'' [powers paper]

1995.05 invited lecture conference Germany
Computational Number Theory. Mathematisches Forschungsinstitut, Oberwolfach. Multidigit modular multiplication with ECRT. [mmecrt paper]

1995.10.03 50 minutes invited lecture seminar USA
Seminar, Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago. Survey of topics related to number field sieve.

1995.10.17 50 minutes invited lecture seminar USA
Number Theory Seminar, Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago. Generalized Gaussian elimination.

1995.11.15 50 minutes invited lecture seminar USA
Computer Science Seminar, Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago. Universal pattern-matching automaton. [unipat paper]

1995.12.02 40 minutes invited lecture conference USA
Midwest Algebraic Number Theory Day III. University of Michigan, Ann Arbor. ``Fast ideal arithmetic via lazy localization.'' [fiall paper]

1996.05.22 20 minutes refereed lecture conference France
Algorithmic Number Theory Symposium (ANTS) II. University of Bordeaux. ``Fast ideal arithmetic via lazy localization.'' [fiall paper]

1997.03.07 30 minutes invited lecture conference USA
Mathematics of Cryptography and Security. Southwest Regional Institute in the Mathematical Sciences (SWRIMS), University of Arizona, Tucson. ``The world's fastest digital signature system.'' [sigs software] [sigs paper]

1997.03.17 50 minutes invited lecture seminar USA
Seminar, Department of Mathematics and Computer Science, Butler University. ``The world's fastest digital signature system.'' Abstract: ``A digital signature system works as follows: you create and publish a seal; you, and only you, can sign a document under that seal; anyone can verify your signature. For widely published documents it is crucial that verification be as fast as possible. The Rabin-Williams system, which is provably as secure as factorization, allows verification in less time than any other system known... until now. I will exhibit a new signature system with the same security and signing speed as Rabin-Williams but with much faster verification.'' [sigs software] [sigs paper]

1997.05.30 invited lecture conference Germany
Computational Aspects of Commutative Algebra and Algebraic Geometry. Schloss Dagstuhl. ``Composing power series over a finite ring in essentially linear time.'' Abstract written after the talk: ``Fix a finite commutative ring R. Let u and v be power series over R, with v(0)=0. I presented an algorithm that computes the first n terms of the composition u(v), given the first n terms of u and v, in n^{1+o(1)} ring operations. The algorithm is very fast in practice when char R is a product of small primes.'' [compose paper]

1997.10.25 20 minutes invited lecture conference USA
Special Session on Number Theory and Cryptography; Central Section Meeting, American Mathematical Society (AMS). University of Wisconsin at Milwaukee. ``A secure digital signature system with verification ten times faster than RSA.'' [sigs software] [sigs paper]

1997.11.19 50 minutes invited lecture seminar USA
Number Theory Seminar, Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago. ``Factoring into coprimes in essentially linear time.'' Abstract: ``It is not easy to factor integers into primes. The point of this talk is that it is easy to factor integers into coprimes. I will (1) give some examples where coprimes are an adequate substitute for primes, (2) explain the Bach-Driscoll-Shallit quadratic-time factorization method, and (3) describe my essentially-linear-time factorization method.'' [dcba paper]

1997.12.03 50 minutes invited lecture seminar USA
Number Theory Seminar, Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago. ``Improving on the Sieve of Eratosthenes,'' talk given jointly with A. O. L. Atkin. Abstract: ``This talk has two parts. The first part will explain how the Sieve of Eratosthenes, a simple method of computing the primes up to N, can be sped up to O(N) additions with roughly N^{1/2} bits of storage, or O(N/log log N) additions with roughly N bits of storage. The second part will explain a new method, relying on quadratic forms, that uses O(N/log log N) additions with roughly N^{1/2} bits of storage.'' [primegen software] [primesieves paper]

1998.02.13 50 minutes invited lecture colloquium USA
Department of Mathematics, Statistics, and Computer Science. University of Illinois at Chicago. ``Computing everything in essentially linear time'': computational one-dimensional commutative algebra.

1998.06.21 20 minutes refereed lecture conference USA
Algorithmic Number Theory Symposium (ANTS) III. Reed College, Portland, Oregon. ``Bounding smooth integers.'' [psibound software] [psi paper]

1998.09.12 invited lecture conference USA
Special Session on Number Theory; Central Section Meeting, American Mathematical Society (AMS). DePaul University, Chicago, Illinois. ``Estimating the speed of the quadratic sieve (preliminary report).''

1998.10.29 30 minutes invited lecture conference Germany
Algorithms and Number Theory. Schloss Dagstuhl. ``Ten topics in computational number theory.'' Abstract: ``1. Fast Fourier transforms. 2. Dividing power series. 3. Exponentiating power series. 4. Enumerating primes. 5. Bounding smooth integers. 6. Smooth polynomial values. 7. Square products. 8. Pomerance's conjecture. 9. Estimating transition time. 10. Estimating factorization time.'' This was a talk on estimating the speed of the quadratic sieve and the number field sieve.

1999.02.23 50 minutes invited lecture seminar USA
Mathematics in Science and Society Seminar, Department of Mathematics, University of Illinois at Urbana-Champaign. ``How to become an international arms dealer'': an introduction to cryptography.

1999.02.23 50 minutes invited lecture seminar USA
Number Theory Seminar, Department of Mathematics, University of Illinois at Urbana-Champaign. ``Fast, arbitrarily precise computation of Psi.'' Abstract: ``In this talk I will explain how to compute arbitrarily precise upper and lower bounds for Psi(x,y), the number of integers in [1,x] without prime divisors exceeding y. Along the way I will explain the state of the art in fast Fourier transforms, high-precision power series exponentiation, and enumeration of small primes.'' [psibound software] [primegen software] [djbfft software] [psi paper] [primesieves paper] [m3 paper] [fastnewton paper]

1999.06.13 20 minutes contributed lecture conference Canada
The Mathematics of Public-Key Cryptography. Fields Institute, Toronto, Ontario. ``Guaranteed message authentication faster than MD5.'' [hash127 software] [hash127 paper]

1999.07.06 invited lecture conference Germany
[PS slides] Explicit Methods in Number Theory. Mathematisches Forschungsinstitut, Oberwolfach. ``Counting rational points by brute force'': fast algorithms to find all points of low height on the Euler-Elkies surface. [sortedsums software] [sortedsums paper]

1999.10.13 10:45 40 minutes invited lecture conference China
[PS slides] Workshop on Complexity of Equation Solving and Algebra, Foundations of Computational Mathematics. City University of Hong Kong. ``Solving equations to high precision'': reducing the algebraic complexity of Newton's method. [fastnewton paper]

2000.04.08 20 minutes invited lecture conference USA
Special Session on Number Theory, Algorithms, and Cryptography; Central Section Meeting, American Mathematical Society (AMS). University of Notre Dame, Indiana. ``Faster multiplication of integers.'' Abstract: ``Zmult is new software to multiply integers of various sizes on common general-purpose computers. This talk will explain, from the perspective of a mathematician and a programmer, why Zmult is so fast.'' [Zmult software] [m3 paper]

2000.05.22 30 minutes invited lecture conference USA
Millennial Conference in Number Theory. University of Illinois at Urbana-Champaign. ``Arbitrarily precise bounds on the distribution of smooth integers.'' Abstract: ``Psibound is new software to approximate the number of integers in [1,x] that factor into integers in [1,y]. This talk will explain the mathematics behind Psibound and show some results.'' [psibound software] [psi paper]

2000.06.10 25 minutes invited lecture conference Canada
Session on Cryptography and Number Theory, Canadian Mathematical Society summer meeting, MATH 2000. McMaster University, Hamilton, Ontario. ``Sieving in cache.'' Abstract: ``Modern integer factorization algorithms do not need as much memory for sieving as is commonly believed. This talk will explain how tomorrow's factoring projects can take advantage of fast arithmetic on stupendously large integers.'' [smallfactors software] [sf paper]

2000.06.27 30 minutes invited lecture conference Russia
Session on Algebraic Algorithms and Complexity, 6th IMACS Conference on Applications of Computer Algebra (ACA). Shuvalov Palace, St. Petersburg. Preliminary title: ``How quickly can we split generic polynomials?'' Final title: ``High-precision high-degree polynomial factorization (preliminary report).'' [fastgraeffe paper]

2000.07.27 50 minutes invited lecture conference England
[PS slides] London Mathematical Society (LMS) Durham Symposium on Computational Number Theory. University of Durham. ``Rethinking the number field sieve.'' Abstract: ``How quickly can we factor 300-digit integers? This talk will review the number field sieve and explain some recent improvements.'' [smallfactors software] [psibound software] [sf paper] [dcba paper] [psi paper] [mlnfs paper]

2000.08.14 60 minutes invited lecture conference USA
[PS slides] [video at www.msri.org] Clay Mathematics Institute Introductory Workshop in Algorithmic Number Theory. Mathematical Sciences Research Institute, Berkeley, California. ``Fast multiplication.'' [multapps paper]

2000.08.15 60 minutes invited lecture conference USA
[PS slides] [video at www.msri.org] Clay Mathematics Institute Introductory Workshop in Algorithmic Number Theory. Mathematical Sciences Research Institute, Berkeley, California. ``Applications of fast multiplication.'' [multapps paper]

2000.08.18 60 minutes invited lecture conference USA
[PS slides] [video at www.msri.org] Clay Mathematics Institute Introductory Workshop in Algorithmic Number Theory. Mathematical Sciences Research Institute, Berkeley, California. ``Protecting communications against forgery'': a survey of secret-key authentication, public-key authentication, and public-key signatures. [forgery paper]

2000.09.07 50 minutes invited lecture colloquium USA
[PS slides] Department of Mathematics, University of California at Berkeley. ``Factoring into coprimes.'' Abstract: ``We do not know a fast algorithm to factor integers into primes. We do, however, know a fast algorithm to factor integers into coprimes. Coprimes suffice for many applications. This talk will describe some of those applications, explain exactly how fast the algorithm is, and present some of the techniques behind the proof.'' [dcba paper]

2000.10.06 48 minutes invited lecture seminar USA
Number Theory Seminar, Department of Mathematics, University of California at Berkeley. ``Arbitrarily precise bounds on smooth integers.'' Abstract: ``An integer is called smooth if all its prime divisors are small. Rough asymptotics for the distribution of smooth integers have been obtained by Dickman, de Bruijn, Canfield, Erdos, Pomerance, Hildebrand, Tenenbaum, et al., and used in a variety of applications. I'll present tight bounds on the distribution of smooth integers and analyze how quickly the bounds can be computed. If time permits, I'll explain the relevance of these bounds to modern integer factorization algorithms.'' [psibound software] [psi paper]

2000.10.20 60 minutes invited lecture conference USA
[PS slides] [video at www.msri.org] Number-Theoretic Cryptography. Mathematical Sciences Research Institute, Berkeley, California. ``Design and implementation of a public-key signature system.'' [sigs software] [sigs paper]

2001.03.23 50 minutes invited lecture seminar USA
Seminar, Computer Science Department, Butler University. ``The NSA sieving circuit.'' Abstract: ``Sieving is the heart of modern algorithms to find the prime factors of an integer---in particular, to break the RSA cryptosystem. This talk will give examples of sieving, explain the relevance of sieving to factorization, and describe a sieving circuit that is asymptotically much faster than previously published hardware designs at the same cost. It is possible that the circuit has already been built in secret by a major government.'' [nfscircuit paper]

2001.05.07 6 minutes contributed lecture conference Austria
[PS slides] Eurocrypt 2001. Innsbruck. ``The NSA sieving circuit.'' [nfscircuit paper]

2001.05.14 40 minutes invited lecture conference Germany
[PS slides] Algorithms and Number Theory. Schloss Dagstuhl. ``An introduction to Schimmler sorting.'' Abstract written after the talk: ``One can sort n^2 numbers on an nxn processor mesh in O(n) parallel compare-exchange steps. Schimmler's algorithm is a very simple algorithm that uses 8n-8 steps. I explained (1) odd-even transposition sorting; (2) Schimmler sorting; (3) the relevance of these results to integer factorization.'' Schimmler sorting is one good choice of sorting algorithm for the NSA sieving circuit. [nfscircuit paper]

2001.06.13 45 minutes invited lecture seminar USA
Seminar, Cambridge Research Laboratory, Compaq Computer Corporation, Cambridge, Massachusetts. ``The state of the art in RSA-type signatures.'' Abstract: ``In this talk I'll explain in detail how a modern public-key signature system works: the good, the bad, and the ugly. You are not required to know anything about cryptography in advance.'' [sigs software] [sigs paper]

2001.07.27 35 minutes invited lecture conference Germany
[PS slides] Explicit Methods in Number Theory. Mathematisches Forschungsinstitut, Oberwolfach. ``Finding polynomial values of small height.'' Unofficial title: ``The algorithm of Hastad, Vallee, Girault, Toffin, Coppersmith, Guruswami, Goldreich, Ron, Sudan, Durfee, Howgrave-Graham, and Boneh.'' The organizers offered me a 45-minute slot; in retrospect, I should have taken it. [smallheight paper]

2001.09.22 30 minutes invited lecture conference USA
[PS slides] Special Session on Cryptography and Computational and Algorithmic Number Theory; Central Section Meeting, American Mathematical Society (AMS). Ohio State University, Columbus. ``Elliptic curve cryptography: the case of NIST P-224.'' Preliminary abstract: ``In this talk I'll explain how to use a particular elliptic curve for high-speed public-key cryptography.'' Abstract: ``This is the first in a series of three talks on nistp224, an easy-to-use software library to perform compressed Diffie-Hellman key exchange on the NIST P-224 elliptic curve at record-setting speeds. In this talk, I'll explain what this means, why it is useful, and a small part of how it works: specifically, an accelerated version of Tonelli's algorithm for computing square roots. Prior exposure to cryptography is not required. In the second and third talks, at the ECC meeting in Waterloo and the MAGC meeting in Urbana, I'll explain the rest of how nistp224 works.'' [sqroot paper] [nistp224 software]

2001.10.29 60 minutes invited lecture conference Canada
[PS slides] Elliptic Curve Cryptography (ECC) 2001. University of Waterloo, Ontario. ``A software implementation of NIST P-224.'' Abstract: ``This is the second in a series of three talks on nistp224, an easy-to-use software library to perform compressed Diffie-Hellman key exchange on the NIST P-224 elliptic curve at record-setting speeds. In this talk, I'll focus on x86 processors such as the Pentium III; I'll explain in detail how nistp224 performs field multiplication and elliptic-curve multiplication. In the first talk, I explained how nistp224 computes square roots. In the third talk, at the MAGC meeting in Urbana, I'll focus on non-x86 processors such as the UltraSPARC.'' [nistp224 software]

2001.11.02 60 minutes invited lecture conference USA
[PS slides] Midwest Arithmetical Geometry in Cryptography (MAGC). University of Illinois at Urbana-Champaign. ``A complete software implementation of NIST P-224.'' Abstract: ``This is the conclusion of a series of three talks on nistp224, a fast software library to perform Diffie-Hellman key exchange on the NIST P-224 elliptic curve. In this talk, I'll focus on non-x86 processors such as the UltraSPARC; I'll explain in detail how nistp224 performs field multiplication and elliptic-curve multiplication. You do not need to have attended the first talk, in which I explained how nistp224 computes square roots, or the second talk, in which I focused on x86 processors.'' [nistp224 software]

2002.01.28 50 minutes invited lecture colloquium USA
Department of Mathematics, University of Pittsburgh. ``Is a 2048-bit factorization worth $200,000?'' Abstract: ``In this talk, I will (1) explain why cash rewards are available for anyone who finds the prime factors of certain integers; (2) present a simple example of a modern integer-factorization algorithm; (3) summarize the performance of state-of-the-art algorithms; and (4) explain how to choose good parameters in these algorithms. If time permits, I'll talk about fast Fourier transforms, generalized power series, better-than-perfect parallelization, and how easy it is to disable the Internet.''

2002.04.24 50 minutes invited lecture seminar USA
[PS slides] Mathematics and Applications Seminar, Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago. ``Finding roots of high-degree polynomials.'' Abstract: ``Consider the problem of computing the complex roots of a polynomial in one variable, given the coefficients of the polynomial. In the first half of this talk, I'll discuss algebraic algorithms that, in a fantasy world of exact arithmetic, compute sequences converging to the roots. In the second half, I'll switch to the real world of limited-precision arithmetic, and present a surprisingly fast root-finding algorithm that relies on multiplication of extremely large integers. The audience will not be assumed to have any prior knowledge of numerical analysis.''

2002.06.15 25 minutes invited lecture conference Canada
[PS slides] Symposium on Cryptography; 2002 Summer Meeting, Canadian Mathematical Society (CMS). University of Laval, Quebec. ``Speed records for cryptographic software: an update.'' Abstract: ``I'll present the latest speed records for software implementations of secret-key message authentication, public-key signature verification, and public-key secret sharing.''

2002.08.20 10 minutes invited lecture conference USA
[PS slides] Crypto 2002. Santa Barbara. ``Deterministic polynomial-time primality tests.'' [aks paper]

2002.08.20 5 minutes contributed lecture conference USA
[PS slides] Crypto 2002. Santa Barbara. ``The cost of integer factorization.'' [nfscircuit paper]

2002.10.31 50 minutes invited lecture colloquium USA
[PDF slides] Department of Mathematics, University of California at Berkeley. ``Proving primality.'' Abstract: ``I'll survey techniques for distinguishing prime numbers from composite numbers. In particular, I'll explain the August 2002 Agrawal-Kayal-Saxena theorem, which gave a remarkably simple solution to the long-standing `PRIMES in P' problem.''

2003.02.11 60 minutes invited lecture seminar USA
[PDF slides] Security Seminar, Computer Science Department, Stanford University. ``The DNS security mess.'' Abstract:
The Domain Name System publishes records such as ``www.stanford.edu has IP address 171.64.14.239.'' An attacker can easily forge these records, stealing your incoming and outgoing mail, web connections, etc.

Stopping DNS forgeries is a straightforward application of public-key cryptographic signatures. Or is it? After ten years of effort, the DNSSEC implementors are making comments like ``We're still doing basic research on what kind of data model will work for dns security ... wonder if THIS'll work? ... We're starting from scratch.''

Why is it so hard to protect DNS against forgery? Is DNS security going to remain an abject failure for another ten years? This talk is a case study of the integration of cryptography into the real world.


2003.03.18 60 minutes invited lecture seminar USA
[PDF slides] Seminar, Sun Microsystems. ``The DNS security mess.''

2003.03.23 09:30 45 minutes invited lecture conference USA
[PDF slides] Lenstra Treurfeest. ``A new proof that 83 is prime.''

2003.03.25 15:45 60 minutes invited lecture conference USA
Future directions in algorithmic number theory. American Institute of Mathematics, Palo Alto, California. ``Randomized primality proving in essentially quartic time.''

2003.03.26 11:30 30 minutes invited lecture conference USA
Future directions in algorithmic number theory. American Institute of Mathematics, Palo Alto, California. ``Rethinking the number-field sieve: an update.''

2003.04.03 14:00 50 minutes invited lecture seminar USA
[PDF slides] Algebraic Number Theory Seminar, Department of Mathematics, University of Illinois at Urbana-Champaign. ``Sharper ABC-based bounds for congruent polynomials.'' Abstract: ``Agrawal, Kayal, and Saxena recently introduced a new method of proving that an integer is prime. The speed of the Agrawal-Kayal-Saxena method depends on proven lower bounds for the size of the group generated by several elements of a finite field. I will discuss an intriguing idea introduced by Voloch for using ABC to obtain such lower bounds.''

2003.04.04 15:30 45 minutes invited lecture conference USA
[PDF slides] Special Session on Cryptography and Computational and Algorithmic Number Theory; Central Section Meeting, American Mathematical Society (AMS). Indiana University, Bloomington. ``Randomized primality proving in essentially quartic time.'' Abstract: ``In August 2002, Agrawal, Kayal, and Saxena published a new way to prove that integers are prime. A modified approach, generalizing an idea of Berrizbeitia, allows substantially shorter proofs. I'll present a typical proof of this type, that an integer satisfying certain conditions must be prime. I'll also discuss the question of whether this approach is competitive in practice with previous primality-proving methods.''

2003.04.24 08:00 75 minutes invited lecture class USA
[PDF slides] Butler University. ``Compressing RSA keys and signatures.'' Abstract:
Public-key signatures can be used to protect Internet packets against unauthorized modification. However, it is often difficult to fit a message, a key, and a signature into a single Internet packet.

Elliptic-curve cryptography is often advertised as offering much shorter keys and signatures than RSA. For example, 224-bit elliptic-curve keys with 448-bit signatures offer the same apparent security as 1536-bit RSA keys with 1536-bit signatures. On the other hand, RSA signature verification is much faster than elliptic-curve signature verification.

It turns out to be possible to compress RSA keys and signatures to a fraction of their original size. Even better compression is possible for the Rabin system, an improved version of RSA. This talk will explain the latest compression techniques.


2003.05.03 17:00 40 minutes invited lecture conference USA
Special Session on Geometry and Arithmetic over Finite Fields; Western Section Meeting, American Mathematical Society (AMS). San Francisco, California. ``Sharper ABC-based bounds for congruent polynomials.'' Abstract: ``The speed of the Agrawal-Kayal-Saxena primality-proving algorithm depends on proven lower bounds for the size of the multiplicative semigroup generated by several polynomials modulo another polynomial h. Voloch pointed out an application of the ABC theorem in this context: under mild assumptions, distinct polynomials A,B,C of degree at most 1.2 deg h - 0.2 deg rad ABC cannot all be the same modulo h. I'll present two improvements in the combinatorial part of Voloch's argument. The first improvement moves the degree bound up to 2 deg h - deg rad ABC; the second improvement generalizes to m>=3 polynomials A_1,...,A_m, with a degree bound of ((3m-5)/(3m-7)) deg h - (6/m(3m-7)) deg rad A_1...A_m.''

2003.05.10 invited lecture conference USA
Midwest Algebraic Number Theory Day. ``Sharper ABC-based bounds for congruent polynomials.''

2003.05.26 11:00 30 minutes invited lecture conference Canada
[PDF slides] Conference in Number Theory in Honour of Professor H. C. Williams. Banff Centre, Alberta. ``Doubly focused enumeration of locally square polynomial values.'' Abstract: ``It is well known that one can accelerate a broad class of sieving problems by precomputing information for various primes. It is not well known that the number of precomputed primes can be nearly doubled beyond the obvious limit. As a typical application, I'll present the results of a record-setting `pseudosquare' computation, i.e., an enumeration of locally square integers.''

2003.07.24 20 minutes contributed lecture conference Germany
Explicit Methods in Number Theory. Mathematisches Forschungsinstitut, Oberwolfach. ``Translating Chudnovsky into English.'' Asymptotically fast computation of exponential integrals.

2003.11.08 15:10 20 minutes contributed lecture conference USA
[PS slides] Mathematics of Public Key Cryptography (MPKC) 2003. University of Illinois at Chicago. ``News from the Rabin-Williams front.''

2003.11.08 16:40 20 minutes contributed lecture conference USA
[PS slides] Mathematics of Public Key Cryptography (MPKC) 2003. University of Illinois at Chicago. ``More news from the Rabin-Williams front.''

2004.04.28 11:00 50 minutes invited lecture seminar USA
[PDF slides] Special Seminar, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign. ``The DNS security mess.''

2004.05.14 09:00 30 minutes invited lecture conference USA
[PDF slides] [approximate transcript] Special Session on Coding Theory and Cryptography; Sixth International Joint Meeting, American Mathematical Society (AMS) and Sociedad Matematica Mexicana. Hyatt Regency Houston, Texas. ``How to find smooth parts of integers.'' Abstract: ``You're given a set P of primes and a sequence S of integers. Which of the integers in S are P-smooth? What is the largest P-smooth divisor of each integer? What are all the factors from P of each integer? These questions occur in many applications: computing discrete logarithms, for example, and proving primality. I previously pointed out an algorithm that answers all three questions in time b (log b)^{3+o(1)}, where b is the total number of bits in P and S. Franke, Kleinjung, Morain, and Wirth, in a recent paper on ECPP, pointed out an algorithm variant that answers only the first two questions but that typically takes time only b (log b)^{2+o(1)}. In this talk I will present an algorithm that always answers the first two questions in time b (log b)^{2+o(1)}.''

2004.06.14 09:00 60 minutes invited lecture conference USA
[PDF slides] [approximate transcript] Algorithmic Number Theory Symposium (ANTS) VI. University of Vermont, Burlington. ``Factorization myths.'' Abstract written after the talk: ``1. We want to find all relations. 2. Sieving is the ultimate test for fully factored inputs. 3. The second small-factor test is not a bottleneck. 4. ECM is the ultimate non-sieving small-factor test. 5. We must have a factor base. 6. Coppersmith's NFS variant is not practical. 7. The direct square-root method is a bottleneck. 8. We want to minimize time on a conventional computer. 9. Mesh architectures simply make everything faster. 10. MPQS beats ECM for finding huge factors.''

2004.06.24 10:20 25 minutes invited lecture conference Canada
[PDF slides] [approximate transcript] Special Session on Computational Number Theory; Canadian Number Theory Association (CNTA) VIII. University of Toronto, Ontario. ``Doubly focused enumeration in two dimensions.'' Abstract: ``Doubly focused enumeration speeds up various sieving tasks by a factor of about 1000. My original formulation of doubly focused enumeration was limited to one-dimensional problems, such as proving primality of medium-size integers. In this talk I will explain doubly focused enumeration for higher-dimensional problems, such as sieving for locally square Gaussian integers. Prior exposure to computational geometry is not required.''

2004.07.07 11:00 60 minutes invited lecture conference Australia
[PDF slides] Polynomial-Based Cryptography. University of Melbourne. ``How to find smooth parts of integers.''

2004.07.29 15:00 60 minutes invited lecture seminar Australia
[PDF slides] Computational Algebra Seminar, School of Mathematics and Statistics, University of Sydney. ``Factorization myths.''

2004.08.17 20:35 5 minutes contributed lecture conference USA
[PDF slides] Crypto 2004. Santa Barbara. ``Stop overestimating RSA bandwidth!''

2004.09.16 15:00 60 minutes invited lecture colloquium USA
[PDF slides] Colloquium aimed at graduate students, University of Illinois at Chicago. ``A state-of-the-art public-key signature system.'' Abstract: ``Hand-written signatures don't prevent forgery: they can be copied from one message to another. This talk is an introduction to cryptography, and specifically to public-key signatures, which are conjectured to prevent forgery. I'll describe a modern public-key signature system: how it works, why it was designed the way it was, and what has been proven about its security.''

2004.11.15 14:00 60 minutes invited lecture conference Canada
[PDF slides] Explicit Methods in Number Theory. Banff Centre, Alberta. ``Three algorithms related to the number-field sieve.'' Abstract: ``1. The number-field sieve tries to factor an integer n by inspecting values of the homogeneous form of a polynomial related to n. What is the size distribution of those values? I'll explain a fast algorithm to evaluate the relevant superelliptic integral. 2. How long does it take to find a polynomial of, say, degree 6, whose values are B times smaller than typical? The best method in the literature is conjectured to search about B^4.5 polynomials. I'll explain an algorithm, using four-dimensional lattice reduction, that is conjectured to search only about B^3.5 polynomials. 3. The bottleneck in the fastest known method to inspect values is computing a large integer modulo many small integers. How long does this take? I'll explain an algorithm that's 2.6+o(1) times faster than the previous record.''

2004.11.19 14:00 50 minutes invited lecture seminar Canada
[PDF slides] Discrete Math Seminar, Department of Mathematics and Statistics, University of Calgary. ``Faster factorization into coprimes.'' Abstract:
How quickly can we factor a set of positive integers into coprimes? The obvious algorithm takes cubic time. Bach, Driscoll, and Shallit achieved quadratic time in 1990. I achieved essentially linear time in 1995. The point of this talk is to announce a new algorithm that takes time just n(lg n)^{4+o(1)} where n is the number of input bits.

The bottlenecks in several common number-theoretic computations---elliptic-curve primality proving, for example, and the number-field sieve---can be viewed as highly constrained examples of factoring into coprimes. This view is traditionally ignored, because the constraints allow many special-purpose techniques that seem to handle the examples well. A surprising discovery over the last few years is that coprime factorization has surpassed the special-purpose techniques, saving time in these computations.


2005.02.15 14:00 50 minutes invited lecture seminar USA
[PDF slides] Computer Security Seminar, Department of Computer Science, University of Illinois at Chicago. ``The Poly1305-AES message-authentcation code.'' Abstract: ``Poly1305-AES is a state-of-the-art message-authentication code suitable for a wide variety of applications. I'll start by defining the Poly1305-AES function and explaining how it is used to authenticate messages. I'll then fit Poly1305-AES into a larger framework, comparing it to other functions such as HMAC-MD5 and explaining the security impact of various choices within the framework. After that I'll focus on speed: I'll review the speeds discussed in the cryptographic literature, I'll present timings for my new Poly1305-AES software, and I'll explain the techniques used to build that software.'' (I decided to spend more time on the framework; I finished the framework by the end of the talk and then skipped to the URLs.)

2005.02.21 10:05 25 minutes refereed lecture conference France
[PDF slides] [approximate transcript] Fast Software Encryption (FSE) 2005. Paris. ``The Poly1305-AES message-authentication code.'' Abstract: ``Poly1305-AES is a state-of-the-art message-authentication code suitable for a wide variety of applications. I'll discuss the security of Poly1305-AES, the speed of Poly1305-AES, and five forms of deceptive benchmarks in the cryptographic literature.''

2005.02.21 16:52 4 minutes contributed lecture conference France
[PDF slides] Fast Software Encryption (FSE) 2005. Paris. ``Have any challenges for qhasm?''

2005.02.25 09:00 60 minutes invited lecture conference France
[PDF slides] Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS). Paris. ``Building circuits for integer factorization.'' Abstract: ``I'll present my latest work on verifiable upper bounds for the money and time needed to factor 1024-bit integers. One important observation is that the switch from conventional computers to mesh computers produces even larger gains for the elliptic-curve method than for the number-field sieve.''

2005.04.26 16:00 15 minutes invited lecture panel USA
[video at uic.edu] University of Illinois at Chicago. On panel responding to 2005 Nakata Lecture by R. Michael Tanner on Universities and the Ecology of Scholarly Publication. Look, Ma: no matter where the camera is pointing, I can escape it!

2005.05.19 14:00 50 minutes invited lecture seminar Denmark
[PDF slides] Department of Mathematics, Technical University of Denmark, Copenhagen. ``High-speed elliptic-curve cryptography.'' Abstract: ``I'll explain the techniques used to set speed records for elliptic-curve Diffie-Hellman on popular CPUs. You do not need prior knowledge of computer microarchitecture.''

2005.05.23 16:10 25 minutes refereed lecture conference Denmark
[PDF slides] Eurocrypt 2005. Scandinavian Congress Center, Aarhus. ``Stronger security bounds for Wegman-Carter-Shoup authenticators.''

2005.05.26 14:15 12 minutes refereed lecture conference Denmark
[PDF slides] ECRYPT STVL Workshop on Symmetric Key Encryption (SKEW 2005). Scandinavian Congress Center, Aarhus. ``The Salsa20 stream cipher.''

2005.05.27 10:45 12 minutes refereed lecture conference Denmark
[PDF slides] ECRYPT STVL Workshop on Symmetric Key Encryption (SKEW 2005). Scandinavian Congress Center, Aarhus. ``Understanding brute force.''

2005.05.30 11:00 90 minutes invited lecture conference Poland
[PDF slides] Quo Vadis Cryptology? Advances in Cryptanalysis. Warsaw, Poland. ``The power of parallel computation.'' Abstract: ``There is a widespread myth that parallelizing a computation cannot improve its price-performance ratio. Cryptographers often wildly overstate the cost of an attack because they are restricting attention to serial computers. I will explain what is known---and what is not known---about the gains that can be achieved from massive parallelism. I will, in particular, discuss the problem of integer factorization.''

2005.06.01 09:00 40 minutes invited lecture conference Poland
[PDF slides] ENIGMA 2005. Warsaw, Poland. ``Cache-timing attacks on AES.'' Abstract: ``I recently succeeded in extracting a complete AES key from a network server on another computer. The targeted server used its key solely to encrypt data using the OpenSSL AES implementation on a Pentium III. I will explain the AES design error that led to this attack, and I will discuss the difficult problem of stopping the attack.''

2005.06.11 10:30 60 minutes invited lecture conference USA
[PDF slides] CAM 2005. University of Central Oklahoma, Edmond, Oklahoma. ``The power of parallel computation.''

2005.06.11 14:40 45 minutes invited lecture conference USA
[PDF slides] CAM 2005. University of Central Oklahoma, Edmond, Oklahoma. ``Integer factorization.''

2005.07.08 16:00 45 minutes invited lecture conference Spain
[PDF slides] Computational Number Theory Workshop; Foundations of Computational Mathematics (FoCM) 2005. Universidad de Cantabria, Santander, Spain. ``Integer factorization: a progress report.'' Abstract: ``There have been several recent improvements to the number-field sieve. I'll explain some of what's going on.'' Designated as a semi-plenary talk by the organizers.

2005.07.19 10:45 25 minutes invited lecture conference Germany
[PDF slides] Explicit Methods in Number Theory. Mathematisches Forschungsinstitut, Oberwolfach. ``Polynomial selection for the number-field sieve, part 2: polynomial merit.'' Abstract written after the talk: ``I discussed the smoothness of the values (a-bm)(a^5+f_4 a^4 b+...+f_0 b^5) that appear in the number-field sieve. In particular, I mentioned choosing pairs (a,b) to produce the smallest values; using superelliptic integrals to approximate the number of pairs (a,b); using smoothness probabilities for ideals to approximate smoothness probabilities for a-bx; using power series to approximate Dirichlet series; handling more general notions of smoothness; and, as a future possibility to explore, generalizing to (a-bm+cm^2)(...).''

2005.09.19 20:00 5 minutes contributed lecture conference Denmark
[PDF slides] Elliptic Curve Cryptography (ECC) 2005. Denmark Technical University, Copenhagen. ``Is 2^255-19 big enough?'' Abstract written after the talk: ``It is widely asserted that 128-bit AES and a strong 256-bit elliptic curve provide comparable security levels against known attacks. This assertion is false. Known attacks batch and scale much more effectively for 128-bit AES than they do for a strong 256-bit elliptic curve.''

2005.09.20 09:30 60 minutes invited lecture conference Denmark
[PDF slides] Elliptic Curve Cryptography (ECC) 2005. Denmark Technical University, Copenhagen. ``New speed records for point multiplication.''

2005.11.06 19:40 50 minutes invited lecture conference Canada
[PDF slides] Number Theory Inspired By Cryptography (NTIBC) 2005. Banff Centre, Alberta, Canada. ``Compressing RSA/Rabin keys.''

2006.02.02 14:25 20 minutes refereed lecture conference Belgium
[PDF slides] SASC 2006 - Stream Ciphers Revisited. College De Valk, Leuven, Belgium. ``Comparison of 256-bit stream ciphers.''

2006.03.11 14:30 50 minutes invited lecture conference USA
[PDF slides] Arizona Winter School 2006. University of Arizona, Tucson, Arizona. ``Integer factorization, part 1: the Q sieve.''

2006.03.12 16:00 50 minutes invited lecture conference USA
[PDF slides] Arizona Winter School 2006. University of Arizona, Tucson, Arizona. ``Integer factorization, part 2: detecting smoothness.''

2006.03.13 16:00 50 minutes invited lecture conference USA
[PDF slides] Arizona Winter School 2006. University of Arizona, Tucson, Arizona. ``Integer factorization, part 3: the number-field sieve.''

2006.03.14 10:00 50 minutes invited lecture conference USA
[PDF slides] Arizona Winter School 2006. University of Arizona, Tucson, Arizona. ``Integer factorization, part 4: polynomial selection.''

2006.04.03 17:30 6 minutes contributed lecture conference Germany
[PDF slides] SHARCS 2006. Dorint Kongress Hotel, Cologne. ``eBATS: ECRYPT Benchmarking of Asymmetric Systems.''

2006.04.09 15:30 20 minutes invited lecture conference USA
[PDF slides] Special Session on Number Theory; Central Section Meeting, American Mathematical Society. University of Notre Dame, Indiana. ``Differential addition chains.'' Abstract: ``Differential addition chains (also known as strong addition chains, Lucas chains, and Chebyshev chains) are addition chains in which every sum is already accompanied by a difference. Low-cost differential addition chains are used to efficiently exponentiate in groups where the operation a, b, a/b |-> ab is fast: in particular, to perform x-coordinate scalar multiplication P |-> mP on an elliptic curve y^2 = x^3 + Ax^2 + x. Similarly, low-cost two-dimensional differential addition chains are used to efficiently compute the function P, Q, P - Q |-> mP + nQ on an elliptic curve. I will present two new constructive upper bounds on the costs of two-dimensional differential addition chains. My new `binary' chain is very easy to compute and uses 3 additions (14 field multiplications in the elliptic-curve context) per exponent bit, with a uniform structure that helps cryptographers protect against side-channel attacks. My new `extended-gcd' chain takes more time to compute, does not have the uniform structure, and is not easy to analyze, but experiments show that it takes only about 1.77 additions (9.97 field multiplications) per exponent bit.''

2006.04.25 09:50 25 minutes refereed lecture conference USA
[PDF slides] PKC 2006. Columbia University, New York. ``Curve25519: new Diffie-Hellman speed records.''

2006.05.30 19:50 4 minutes contributed lecture conference Russia
[PDF slides] Eurocrypt 2006. Pulkovskaya Hotel, St. Petersburg. ``eBATS: ECRYPT Benchmarking of Asymmetric Systems.''

2006.06.15 16:15 105 minutes invited lecture conference Belgium
[PDF slides] Summer School on Cryptographic Hardware, Side-Channel and Fault Attacks. Louvain-la-Neuve. ``Cache-timing attacks.'' The slides aren't as thorough as usual; I was invited only a few days before the summer school, replacing Jean-Pierre Seifert, who wasn't able to attend.

2006.06.26 09:50 80 minutes invited lecture conference USA
[PDF slides] Summer School on Computational Number Theory and Applications to Cryptography. University of Wyoming, Laramie. ``The number-field sieve.'' Abstract:
The ``number-field sieve'' is today's state-of-the-art method of finding large prime factors of integers. A year ago the number-field sieve was used to factor ``RSA-200,'' a 200-digit challenge integer chosen as the product of two secret random 100-digit primes.

I'll explain what the number-field sieve computes, and why that computation can be expected to succeed. I'll start with the ``Q sieve,'' an easy special case of the number-field sieve; I'll then generalize from Q to other number fields. Along the way I'll explain how to use ``sublattices'' to improve smoothness chances.


2006.06.27 09:50 80 minutes invited lecture conference USA
[PDF slides] Summer School on Computational Number Theory and Applications to Cryptography. University of Wyoming, Laramie. ``Finding small factors of integers.'' Abstract:
The number-field sieve (like many other number-theoretic algorithms) produces a large collection of auxiliary numbers and tries to find the smooth numbers, i.e., the numbers that factor into small primes.

I'll discuss the state of the art in algorithms to find small factors of integers, combining seven critical ideas beyond trial division: ``sieving,'' ``remainder trees,'' the ``rho method,'' the ``p-1 method,'' the ``p+1 method,'' the ``elliptic-curve method,'' and ``early aborts.''


2006.06.28 09:50 80 minutes invited lecture conference USA
[PDF slides] Summer School on Computational Number Theory and Applications to Cryptography. University of Wyoming, Laramie. ``Speed of the number-field sieve.'' Abstract:
I'll discuss optimization of the number-field sieve. In particular, I'll explain fast linear algebra by the ``series-denominator method''; I'll analyze the asymptotic cost exponent of the number-field sieve; and I'll present various improvements in polynomial selection.

2006.06.29 09:50 80 minutes invited lecture conference USA
[PDF slides] Summer School on Computational Number Theory and Applications to Cryptography. University of Wyoming, Laramie. ``Proving primality in polynomial time.'' Abstract:
Agrawal, Kayal, and Saxena proved in 2002 that ``PRIMES is in P'': i.e., that there is a deterministic polynomial-time algorithm to distinguish prime numbers from composite numbers. I'll present an AKS-type algorithm, and I'll prove that an integer n is accepted by the algorithm if and only if n is prime.

2006.06.30 09:50 80 minutes invited lecture conference USA
[PDF slides] Summer School on Computational Number Theory and Applications to Cryptography. University of Wyoming, Laramie. ``Proving primality more quickly.'' Abstract:
I'll say whatever I can in the available time about the state of the art in distinguishing prime numbers from composite numbers. In particular, I'll explain ``elliptic-curve primality proving.''

2006.07.10 10:00 30 minutes invited lecture conference Australia
[PDF slides] 31st Australasian Conference on Combinatorial Mathematics and Combinatorial Computing. Voyages Resort, Alice Springs. ``Differential addition chains.''

2006.08.03 10:00 50 minutes invited lecture conference Japan
[PDF slides] 2006 Workshop on Cryptography and Related Mathematics. Chuo University, Tokyo. ``High-speed cryptographic functions.''

2006.08.14 13:30 120 minutes invited lecture (planned) conference Taiwan
Information Security Summer School (ISSS) 2006. Taipei.

2006.08.15 09:30 120 minutes invited lecture (planned) conference Taiwan
Information Security Summer School (ISSS) 2006. Taipei.