PROVIDENCE, RI [Brown University] — Mathematicians often work in the dark, and that’s probably because few people, apart from other mathematicians who share the same specialty, understand what they’re doing. Even when algorithms have practical uses, like helping drivers see approaching cars that the eye can’t see, it’s the automaker (or its software developer) who gets the credit.
This is especially true of cryptographers, the unsung heroes whose algorithms protect people’s communications and data as they use the Internet – a technology known as public-key cryptography.
But sometimes pure math affects the real world. That happened this summer when the National Institute of Standards and Technologies selected four cryptographic algorithms to serve as standards for public-key security in the coming era of quantum computing, which will quickly render current cryptographic systems obsolete.
Three of the four algorithms selected are based 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-supported Falcon algorithm – and NTRU, the public-key cryptosystem on which Falcon is based – began in the mid-1990s, when quantum computing was still in the realm of science fiction. At that time, Hoffstein’s goal was to develop an algorithm that would simplify and speed up the functioning of conventional cryptographic algorithms; In 1996 he co-founded NTRU Cryptosystems Inc. with Silverman and Pipher (who is also married to Hoffstein) to bring it to market. Hoffstein said NTRU’s story was a “blood-clotting saga,” but the company ultimately thrived and found a suitable buyer in Qualcomm. Falcon, which Hoffstein developed with nine other cryptographers, and two of the three other algorithms selected by NIST build on the original NTRU framework.
From before his PhD at MIT, through all the positions he’s held at the Institute for Advanced Study, Cambridge University, the University of Rochester, and Brown, Hoffstein has been “a numbers person” through and through: “It never occurred to me no being a mathematician,” he said. “I promised myself I’d keep doing math until it wasn’t fun anymore. Unfortunately, it’s still fun!”
After being selected by NIST, Hoffstein detailed his transformation from number theorist to applied mathematician with a solution to an imminent global problem of critical importance.
Q: What is public key cryptography?
When you connect to Amazon to make a purchase, how do you know 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 a so-called digital signature; the second is solved by public key encryption. Of NIST’s standardized algorithms, one is for public-key encryption and the other three, including Falcon, are for digital signatures.
They are based on problems of pure mathematics of a very special kind. They’re hard to solve (think: time to the end of the universe) when you have one piece of information, and they’re easy to solve (takes microseconds) when you have one piece of additional secret information. The wonderful thing is that only one of the communicating parties – in this case Amazon – needs to have the secret information.
Q: What is the security challenge that quantum computing poses?
Without a powerful enough quantum computer, the encryption problem will take eons to solve. With a powerful quantum computer, the time to solve the problem is hours or less. To put it more alarmingly, if someone owned a powerful quantum computer, the entire security of the internet would collapse completely. And the National Security Agency and big companies are betting that within five years there’s a good chance a quantum computer powerful enough to crack the Internet can be built.
