Daniel J. Bernstein
University of Illinois Chicago
- Research field
- Cryptography, algorithms for secure and fast computation
Daniel J. Bernstein designs cryptographic systems and the algorithms that run them safely on real computers, where the time a computation takes can betray a secret. With Bo-Yin Yang he developed a variant of Euclid's algorithm whose sequence of operations does not depend on its input, so that a secret key cannot be read off the timing of a gcd or modular inversion, and showed that it is also faster than the earlier safe methods. The algorithm now computes the modular inverses in the library that signs Bitcoin transactions. The unit presents it right after the extended Euclidean algorithm, whose data-dependent quotients it was designed to avoid.
In the masterclass
Section 4, after the extended Euclidean algorithm and its Bézout coefficients, shows how Bernstein and Yang made the algorithm run in constant time.
The research is presented in Unit 2: Divisibility and the Euclidean Algorithm, in a research spotlight box that explains the result at the level of the unit and links it to what you have just learned.