Evan LernerPenn Researchers Receive $1.1 Million NSF Grant to Protect Internet Security
University of Pennsylvania researchers Nadia Heninger, Ted Chinburg, Brett Hemenway and Zach Scherr are trying to break the internet. But only so they can protect it.
The team of computer scientists and mathematicians received a four-year, $1.1 million grant from the Secure and Trustworthy Cyberspace program of the National Science Foundation to use mathematics to better understand modern cryptography systems. Such systems allow for the transmission of secure communications over insecure wireless channels. Specifically, the researchers are focusing on a type of public key encryption called RSA.
A little more than a year into the project, they have published their first paper and are working on next steps to further combine their expertise in arithmetic geometry and cryptography. By linking these subjects in a novel way, they hope to develop tools applicable to a broad range of cryptographic systems.
The collaboration came about serendipitously. In 2014, Heninger, the Magerman Term Assistant Professor in the computer and information science department in the School of Engineering and Applied Science, gave a talk to the math department in the School of Arts & Sciences, where Chinburg is a professor and Scherr, who is now at Bucknell University, was one of several Hans Rademacher Instructors of Mathematics.
“She was doing something in a subject I knew about, namely capacity theory,” Chinburg said. “I realized that capacity theory could tell whether or not you could really improve,” an important aspect of what’s come to be called Coppersmith’s method.
In Coppersmith’s method, if have two 500-digit numbers, a computer can easily multiply them and return a product, but how about doing the reverse? If you know that a huge number came from two factors but you don’t know either one, how would you determine those factors? Don Coppersmith, a cryptographer and mathematician, discovered in the 1990s that, if you knew half the digits of the bigger of the two numbers, you could eventually discover both numbers precisely.
“This was a very important result and it was a surprise to many people,” Chinburg said. The Penn team wanted to go a step further. “Suppose you knew fewer of the digits of that larger number? Could you still determine a rapid algorithm to find the factors? Coppersmith had been inventing a part of capacity theory without realizing this.”
Capacity theory, an aspect of number theory, derives from the study of how electric charges disperse on different types of objects. Repelling electrical charges move to minimize their total potential energy. In the past century, scientists discovered that the physics of this process could help predict whether various problems in number theory could be solved.
To do this requires building a physical model of the number theoretic problem. If the electrical charges in that model can’t move around in a way that enables them to reach a small enough total energy, the original number theory problem cannot be solved.
In its first paper, the Penn group used this method to put sharp bounds on how far science could improve the technique Coppersmith used to prove this theorem. The researchers learned that making a substantial improvement in Coppersmith’s final result would really require a different technique.
So how does this relate to the internet? There are many different ways to attack the internet’s security; the Penn researchers decided to tackle RSA encryption.
“Cryptographers have spent several decades thinking about how you might be able to break the security of RSA encryption in various scenarios,” Heninger said. “But we didn’t have any assurances that the approaches cryptographers were taking were optimal, the best that you could do.”
That’s where the math comes in. Much like the notion of trying to solve which two factors make up a massive number, RSA encryption requires two encoded “keys” composed of many digits. One is public, the other private. Heninger uses the example of a bank to explain. A bank publishes its public key which users employ to send messages about private personal financial information. The bank then uses its private key to decrypt those messages.
“Nobody else can decrypt the message unless they have the bank’s private key,” Heninger said. “And they can’t compute the private key from the public key. That’s the foundation of security on the internet.”
To this point, the Penn collaboration has meshed well, figuring out how to skirt the barriers of translating back and forth between what are essentially two different languages of math and computer science.
“Cryptographers are incredibly clever,” Chinburg said. “They find methodology that theoreticians never would have dreamed of. On the other hand, arithmetic geometers have invented some methods new to the cryptography community. I’m very excited that our group has the opportunity to combine the two subjects.”
It could result in a safer, more secure internet.
Originally published by Michele Berger at news.upenn.edu.