Algorithm to serve as cryptography standard for quantum computing era

Mathematicians often work in the dark, and this is probably because few people, apart from other mathematicians who share the same specialty, understand what they are 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 prior to his PhD at MIT through all positions he has held at the Institute for Advanced Study, Cambridge University, University of Rochester and Brown, Hoffstein has been “a numbers person” through and through: “It never crossed my mind “I made a promise to myself that I would do 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.

Q: They developed the NTRU solution in the early to mid 90’s, well before anyone thought about the cryptography requirements of potential quantum computers. What were you thinking at the time?

I found the three main approaches to public key cryptography very clunky and unaesthetic. To give just one example, the most popular method, RSA, is to take numbers many hundreds of digits long, then raise them to hundreds of digits, divide by another number hundreds of digits long , and finally take the rest. This calculation is easy to do on a computer, but not very practical if you have a small, light processor like a 1996 cell phone. RSA is also very slow – okay, milliseconds, but that still counts as slow.

Our dream was to find a method for public-key cryptography that is orders of magnitude faster than RSA and runs on low-power devices. And we did it! People who implemented it could run it at speeds 200 to 300 times faster than RSA. I didn’t do this alone – I thought about the problem obsessively for a year and a half, but it didn’t materialize into a solution until I joined Joe Silverman and Jill Pipher, my Brown colleagues and the co-founders of NTRU.

Q: What does NTRU stand for?

We never said – people just assumed we meant something technical and used their imagination! But it stands for Number Theorists R Us. This irritated Jill as she is a harmonic analyst, not a number theorist, but she eventually forgave me.

Q: You described that your startup NTRU Cryptosystems had about five “near-death” experiences. What were some of the challenges you faced?

The gatekeepers in the field are mostly cryptographers who work for companies and in IT departments. Getting a new algorithm to be taken seriously is incredibly difficult, and it’s especially difficult when you’re not in the crypto club. In our case, we sounded the alarm bells for two reasons. For one, we were outsiders and added additional structures from algebraic number theory to the grids to make things more efficient.

If you do this, there is a serious risk that you may have accidentally introduced vulnerabilities. Yes, it’s wonderful to make something more efficient. But did you lose an important piece of security in the process? It is entirely understandable that people were deeply suspicious of this additional structure that introduced the ability to multiply and add. It took 10 years of intense scrutiny for people to start accepting that weaknesses weren’t added.

Q: This wasn’t just an academic exercise. NTRU was a company that needed to work with investors and potential customers. Early on, NTRU was unfairly attacked in an article written by some well-known names in cryptography (who later admitted their mistake). How did NTRU survive this?

It turned out that her paper was largely ignored, but our paper was so interesting that everyone looked into it. They tried to attack and destroy it, and it attracted tremendous attention. Every single surface you can imagine has been besieged by battering rams. The crypto community has been so resilient to mathematicians encroaching on their turf. If we hadn’t been known Brown mathematicians, we wouldn’t have survived the controversy. In the end, that attention probably helped us.

Q: Were there any advantages of being a mathematician – outsiders of this world?

What I’m most proud of isn’t necessarily the fact that each algorithm made the bottom four of the NIST picks, even though each and every one of the three lattice-based algorithms uses our ring structure (the multiplication function). They all use the math we introduced because after more than 25 years of testing, not a single weakness has emerged from adding this structure. This mathematics, derived from algebraic number theory, was not previously part of cryptography. It’s part of my other livelihood and I find it particularly appealing that we’ve been able to put into practice this totally abstract theoretical thing that doesn’t seem to have any use. As a result, today’s generation of cryptographers must know all algebraic theory, which is kind of fun.

Q: What is it like being married to another mathematician?

It’s the nicest thing in the whole world to be married to someone who understands what it’s like to be a mathematician. In math, 99.9% of the time you spend hours, weeks, months, and years thinking about something that gets nowhere. So often you think you have a fantastic idea and it’s going nowhere. It’s wonderful to be married to someone who understands that feeling, even if we don’t always understand the details of what the other person is working on.

Q: Can you tell when you’re deep in thought?

Yes, and she probably is too.