In July, the National Institute of Standards and Technologies selected four cryptography algorithms as national standards for public key security in order to prepare for an era of quantum computers, which uses quantum physics for more powerful computing and will compromise the security of current algorithms. Three of the four selected algorithms are based on technology developed by NTRU Cryptosystems, Inc., which was founded by a team of University researchers in 1996.
A cryptography algorithm is “nothing more or less than any method by which two people can exchange messages and secrets,” said Jeff Hoffstein, founder of NTRU Cryptosystems, Inc. and professor and chair of mathematics.
These algorithms serve two main functions: data scrambling and data authentication, according to William Whyte, senior director of technical standards at Qualcomm, which acquired NTRU Cryptosystems, Inc.
Cryptography algorithms contain keys, which can encrypt or decrypt data. There are two different types of cryptography used in data scrambling: symmetric, where both the sender and receiver have the same key, and asymmetric, where the sender has access to a public encryption key and the receiver has a private decryption key, Whyte added. While symmetric cryptography algorithms are fast, they present an authentication problem where the sender and receiver can pretend to be the other, allowing for identification fraud, he said.
Asymmetric cryptography algorithms, also called public key cryptography algorithms, solve this problem. The public key algorithm “gives you the ability to have actually secure identities online” by requiring both a public key for encryption and a private one for decryption, such that “only one person needs to know a secret in order for two people to communicate,” Hoffstein said.
When an individual sends a message using their private key, this creates a digital signature that the receiver can check using that individual’s public key. This allows for data authentication — if “the signature is valid, that means it was created by the private key and that means I’m the only person that could have created it,” Whyte said.
This allows “two people to communicate securely and privately,” John Schanck, an architect of several of the NIST finalists, said. “It’s what we use every day when you go online to talk to your bank or browse the web privately.”
Historically, public key cryptography has been considered to be secure because calculating the decryption key from the encryption key would “take eons until the sun burns out to solve it if you just use normal computers,” Hoffstein said.
But the researchers say that this security will be compromised in the new age of quantum computers. This calls for new public key encryption algorithms to protect data.
“I'm pretty confident that the (quantum computing) machines are coming, that they're going to be built soon, and when they are, the main effect is that they break all the public key cryptography that we're using today,” Schanck said.
“If a sufficiently strong quantum computer existed that could solve the problem in a very short time, the entire security that the Internet is based on would vanish in a moment,” Hoffstein added. Thus, “NIST began a competition where people from all over the world submitted algorithms to this contest, … and the entire world of cryptographers set to work trying to attack these problems.”
The FALCON algorithm, developed by Hoffstein’s NTRU Cryptosystems, Inc. was selected by NIST as one of the 2022 national cryptography standards due to its new method of computation that is not as susceptible to quantum computer attack. Two other selected algorithms are also based on NTRU technology, Hoffstein said.
Hoffstein’s interest in cryptography began after attending a lecture on the topic that presented on three old cryptosystems. He left the lecture wondering, “Why is it that these three methods of doing public key cryptography are so incredibly clunky?” he said. All three methods involved “such a tremendous amount of computational nonsense” and were “all based on very very simple mathematical ideas.”
Thus, he decided to replace the modular arithmetic that these systems used with calculations on an elliptic curve, which simplified the algorithmic computations. “I thought it would be really nice to have something that was so simple that it did not involve big processors like computers,” Hoffstein said, “something that could be done on a cell phone.”
After finding a rough solution, he took this idea to Joseph Silverman ’77 and Jill Pipher, both professors of mathematics, and asked them to collaborate with him to turn the concept into a “polished, working cryptosystem,” he said. “I would have gotten nowhere without them.”
After months of work, the team developed the NTRU cryptosystem in 1996. Since then, nobody has found an attack on NTRU that would compromise security, which is why NIST decided to accept algorithms based on the NTRU method, Hoffstein said.
NTRU’s success highlights the importance of curiosity-driven research, Hoffman added.
“The U.S. government has directed less and less money towards curiosity-driven research, and this strikes a blow on the value of curiosity-driven research,” Hoffstein said. But “there are innumerable mathematical examples of fantastic things that have come out of curiosity-driven research, and to have added to the list, that's really the most satisfying thing.”
