PROVIDENCE, R.I. [Brown University] — Mathematicians often toil in obscurity, and that’s likely because few people, apart from fellow mathematicians who share the same sub-specialty, understand what they do. Even when algorithms have practical applications, like helping drivers see approaching cars that the eye can’t discern, it’s the car manufacturer (or its software developer) that gets the credit.
This is especially true of cryptographers, the unsung heroes whose algorithms keep people’s communications and data secure when they use the internet — technology known as public key cryptography.
But sometimes, pure math impacts the real world. That happened this summer when the National Institute of Standards and Technologies selected four cryptography algorithms to serve as standards for public key security in the impending era of quantum computers, which will make current encryption systems quickly obsolete.
Three of the four chosen algorithms rest on work led by a team of mathematicians at Brown: professors Jeffrey Hoffstein, Joseph Silverman and Jill Pipher (who also serves as Brown’s vice president for research).
The story of the NIST-endorsed Falcon algorithm — and NTRU, the public key cryptosystem upon which Falcon is based — began in the mid-90s, when quantum computing was still in the realm of science fiction. At the time, Hoffstein’s goal was to develop an algorithm to simplify and speed up the way conventional cryptographic algorithms worked; in 1996, he co-founded NTRU Cryptosystems Inc. with Silverman and Pipher (who is also married to Hoffstein) to take it to market. Hoffstein said the history of NTRU is a “bloodcurdling saga,” but the company was ultimately successful, finding a suitable purchaser in Qualcomm. Falcon, which Hoffstein co-designed with nine other cryptographers, and two out of the three other algorithms NIST selected, are built upon the original NTRU framework.
From before his doctoral study at MIT through each of the positions he’s held at the Institute for Advanced Study, Cambridge University, the University of Rochester and Brown, Hoffstein has been “a numbers guy,” through and through: “It never occurred to me not to be a mathematician,” he said. “I promised myself that I would continue to do math until it was no longer fun. Unfortunately, it’s still fun!”
On the heels of NIST’s selection, Hoffstein described his transformation from a number theorist to an applied mathematician with a solution to an impending global problem of critical importance.
Q: What is public key cryptography?
When you connect to Amazon to make a purchase, how do you know that you are really connected to Amazon, and not a fake website set up to look exactly like Amazon? Then, when you send your credit card information, how do you send it without fear of it being intercepted and stolen? The first question is solved by what is known as a digital signature; the second is solved by public key encryption. Of the NIST’s standardized algorithms, one is for public key encryption, and the other three, including Falcon, are for digital signatures.
At the root of these are problems of pure mathematics of a very special type. They are hard to solve (think: time until the universe ends) if you have one piece of information and they are easy to solve (takes microseconds) if you have an extra piece of secret information. The wonderful thing is that only one of the parties communicating — Amazon, in this case — needs to have the secret piece of information.
Q: What is the security challenge that quantum computers pose?
Without a sufficiently strong quantum computer, the time to solve the encryption problem is eons. With a strong quantum computer, the time to solve the problem comes down to hours or less. To put it more alarmingly, if anyone had possession of a strong quantum computer, the entire security of the internet would completely break down. And the National Security Agency and major corporations are betting that within five years there is a good chance that a quantum computer strong enough to break the internet could be built.
