FOR THE INVENTION OF CRYPTOGRAPHY BASED ON ELLIPTICAL CURVES

A physical signature on a contract gives a modest yet legally binding guarantee that the signee approved the agreement. Such signatures have long played an important role in society but they have several disadvantages: they are easy to forge, they do not assure that the document was not altered after signing and they are cumbersome to apply to many documents. A natural question is whether digital technology can overcome these deficiencies, i.e., can digital signatures ensure authenticity and information integrity in an efficient manner. Efficiency is especially important for today’s internet web browsers that collectively relay billions of clicks each day. For example, customers shopping online want to know that the web pages they see are authentic, and banks want to know that the transactions they are completing are authorized by legitimate parties.

Digital signatures are based on a branch of mathematics that had otherwise found limited application: number theory. For example, a classic number-theoretic problem is the seemingly strange question: are there any positive integer solutions to aⁿ+bⁿ=cⁿ for any integer n greater than two? The answer to this question is, in fact, Fermat’s Last Theorem from 1637 whose proof 358 years later involved elliptic curves.

Number theory became important for data security in 1976 with Diffie and Hellman’s invention of public-key cryptography. These two researchers suggested a new secret-key exchange algorithm that can provide digital signatures and whose security relies on the difficulty of performing discrete logarithms over a set called the “multiplicative group of a finite field” (the reader unfamiliar with the meaning of a “multiplicative group” can simply think of multiplying positive integers modulo a prime number such as 127). However, one important weakness of this group is that there are competing algorithms that can invert logarithms more easily than by brute-force search. This weakness means, e.g., that digital signatures require large keys with over 3000 bits for a reasonable level of security. The substantial key length translates into slow processing, costly storage, and high energy consumption.

The winners of the 2020 Eduard Rhein Technology Award are Neal Koblitz and Victor Miller for the invention of elliptic-curve cryptography. Their core idea from 1985 was to replace the “multiplicative group of a finite field” with the “group of points on an elliptic curve over a finite field”. This idea will sound obscure to most readers, but it is practically important because problems such as computing discrete logarithms seem to be significantly more difficult in the second group than the first. This in turn means that elliptic-curve cryptography requires only 283-bit keys to achieve the same level of security as the 3000-bit keys of earlier methods. Furthermore, the ten-fold reduction in key length lets cryptographic devices operate with higher speed, smaller memory, and lower energy requirements.

In 2013, the U.S. National Institute of Standards and Technology (NIST) recommended elliptic curve cryptography for key exchange through an algorithm called Elliptic Curve Diffie Hellman (ECDH), and for digital signatures through an algorithm called the Elliptic Curve Digital Signature Algorithm (ECDSA). Furthermore, the U.S. National Security Agency allowed using these algorithms to protect information classified up to top secret with 384-bit keys. Today, elliptic curves are used by applications such as Bitcoin, Transport Layer Security (TLS) based web browsing, and many others.

Neal Koblitz received a Bachelor of Arts from Harvard University in 1969 and a Ph.D. from Princeton University in 1974. He has been with the University of Washington since 1979. Shortly before inventing elliptic curve cryptography, in 1984 he published the textbook “Introduction to Elliptic Curves and Modular Forms” with, in his words, down-to-earth examples that aim to make the material readable and interesting. He has received several recognitions for his work, including an RSA Excellence in Mathematics Award in 2009 together with Victor Miller.

Victor Miller was born in Brooklyn, New York, and he learned about elliptic curves as a freshman in college in 1964 when these objects were, in his words, an interesting but arcane piece of mathematics. He studied mathematics at Columbia University and Harvard from 1964-75. He joined the University of Massachusetts in 1973, IBM in Yorktown Heights in 1978, and the Center for Communications Research (CCR) of the Institute for Defense Analyses in Princeton, New Jersey, in 1993.

Through their invention of elliptic curve cryptography, Neal Koblitz and Victor Miller have had a lasting impact on digital technology that is sure to grow over time. Their application of fundamental mathematics to a problem of great engineering and social relevance has made possible a secure and efficient communication over the internet.

(The polynomial equation in the title represents the Koblitz curve K-283 as described in Section D.1.3 of NIST’s publication FIPS PUB 186-4 from July 2013.)