One-Way Functions: The Unsolved Mathematical Mystery of Encryption

Monday - October 23 2023, 08:05 UTC - 1 year ago

Computer scientists, mathematicians, and cryptographers have been on a quest to find new encryption algorithms that can withstand attacks from both classical and quantum computers. No one has yet found a type of problem that is provably hard for classical or quantum computers to solve, and if true one-way functions don't exist, cryptographers may still be in danger of attack from unknown hackers. Rafael Pass and Leslie Valiant are working on mathematical models to establish one-way functions but to date nothing has been developed.

When we check email, log in to our bank accounts, or exchange messages on Signal, our passwords and credentials are protected through encryption, a locking scheme that uses secrets to disguise our data. It works like a cyber padlock: with the right key someone can unlock the data. Without it, they’ll have to resort to laborious brute-force methods, the digital equivalent of hacksaws and blowtorches.

Our trust in online security is rooted in mathematics. Encryption schemes are built on families of math problems called one-way functions—calculations that are easy to carry out in one direction but almost impossible to solve efficiently from the other, even with a powerful computer. They’re sort of a computational equivalent of those road spikes found at the exits of airport car rental agencies. Drive in one direction and you barely notice. Hit reverse and you won’t get far (and will need new tires).

There’s a problem, however. Although mathematicians suspect true one-way functions exist, they have yet to prove it. They haven’t proved that the thorny problems we do use are impossible, or even extremely impractical, to solve. Instead, it could just be that we haven’t yet found the appropriate mathematical means to take the problems apart. This conundrum haunts all encryption. Our data is secured by the fact that no one knows how to crack the schemes that protect it—at least not yet.

Computer scientists, mathematicians, and cryptographers are on a quest to find new encryption algorithms that can withstand attacks not only from today’s conventional computers but also from tomorrow’s quantum machines. What they want is a big, sticky math problem—something that’s robust enough to withstand attacks from classical and quantum computers but can still be easily implemented in cyberspace.

Unfortunately, no one has yet found a single type of problem that is provably hard for computers—classical or quantum—to solve. (In the world of cryptography, "hard" describes a problem whose solution requires an unreasonable number of steps or amount of computing power.) If one-way functions don’t exist, then cryptographers’ whack-a-mole process of finding flaws and developing ever stronger schemes to block clever hackers will persist indefinitely.

"The question of whether one-way functions exist is really the most important problem," says Rafael Pass, a theoretical computer scientist at Tel Aviv University in Israel. It’s a conundrum that dates to the 1970s and the dawn of a research area now known as computational complexity theory. Over five decades, theorists and cryptographers have been looking for ways to establish whether such functions do exist. Perhaps the problems we hope or suspect are one-way are just easier, breakable ones in disguise.

Pass is exploring how one-way functions are connected to a raft of other open problems, a promising line of research that has drawn other theorists into the quest. At the same time, people focused on the practical side of cryptography are plowing ahead, hunting for new schemes that are—if not provably hard—seemingly strong enough to hold up against quantum computers.

For the last seven yeas, Pass and Leslie Valiant, a computer scientist at Harvard University, have been developing a mathematical model of computational complexity theory that could serve as the missing link to one-way functions. It proposes that certain mathematical problems embedded in networks of multiple switches be used as the preventive tar pits to stop tomorrow’s unknown attackers.