Trying to create unbreakable encryption using ancient equations
“I’m a number theorist,” said Kirsten Eisenträger. “I work in number theory and arithmetic geometry, and, at the highest level, I look for solutions to equations.”
Such a straightforward statement belies the complexity of the work she does, which soon becomes evident.
Specifically, Eisenträger studies polynomial—so-called “Diophantine”—equations, which she points and now, basically, the security of all e-commerce transactions—shopping on Amazon, online banking, everything—relies on the fact that there’s some hard number-theoretic problem underneath, based on these equations, that can’t be solved efficiently. And so I look into how hard these problems are, in particular for quantum computers.”
Even seemingly simple things, such as verifying the updates on your computer or smartphone, or accessing a network or other account with a username and password, rely on what is known as public key cryptography—a technology that is relatively difficult (or at least time-consuming) for conventional computers to crack, but would be a breeze for quantum computers of the future.
“All the systems that are currently being used would become insecure,” Eisenträger said matter-of-factly. “So I look at cryptography that would still be viable even if quantum computers are built.”
In response to a call from the National Institute of Standards and Technology (NIST) for researchers to propose such “post-quantum” cryptosystems, out have been studied for hundreds of years (dating back, in fact, to the ancient Greeks) and are the basis of some of the most advanced cryptographic security in use today on computers around the world.
“I study whether there are algorithms that determine the solvability of these equations,” she explained. “Thirty years ago, it was discovered that these equations have applications to cryptography, Eisenträger has been analyzing some recently proposed systems to see how secure they really are and, she noted, “showing in some cases that they’re actually not secure.”
The process goes something like this: one pool of researchers develops the systems, and another pool tests those systems for vulnerabilities; as soon as someone cracks a system’s security, the developers modify it and the cycle starts over again.
“For instance, there’s a cryptosystem called Soliloquy that was developed by British Intelligence,” Eisenträger said. “It was developed as a possible post-quantum system, but it turns out that one of the results that I proved and published with Sean Hallgren, Alexei Kitaev, and Fang Song actually is one of the steps that can be used to break the system, and it also breaks several other recently proposed systems. So now they’re looking at different ones.”
Ultimately, the analysts—Eisenträger included— are searching for an underlying mathematical problem that will be complex enough to stump, or at least forestall, a quantum computer’s attempts to solve it. As Eisenträger said, “We’re trying to find a unifying framework.”
Since no one, to date, has developed a working quantum computer, there can’t yet be a solution, and so the work continues; but Eisenträger, clearly, is nonetheless enthused.
“There are just so many different, creative ways to attack these problems, and different theories that have been developed while working on these problems,” she said with a grin. “It’s just very exciting.”