The future of cybersecurity hinges on creating harder problems

The cybersecurity that protects sensitive online data relies heavily upon how hard it would be to solve a type of really, really hard math problem. 

The bad news: Quantum computers are really, really good at solving the types of problems currently used. The good news: Cryptographers and coding theorists around the world are hunting for new problems that are hard for both contemporary and quantum computers to solve.

In an invited review article in the March-April edition of American Scientist, Gretchen Matthews, mathematics professor and director of the Commonwealth Cyber Initiative in Southwest Virginia, talks about new hard problems that can support cryptography for today’s computing devices but could also withstand an attack from an adversary equipped with a quantum computer. 

Built on the idiosyncrasies of physics at and below the level of the atom, quantum computers are designed completely differently than today’s machines. When fully developed, the emerging technology promises to extend our technological strides into leaps with tools to simulate molecules and drug discovery, solve complex traffic and network flow problems, and predict and mitigate climate crises. On the flipside, however, they will also provide the key to dismantle most digital security. 

Although the National Institute of Standards and Technology is laying the groundwork for the rollout of advanced cryptosystems, modern society might be in for a bumpy transition. 

“There will be a time when large-scale, reliable quantum computing is a reality, but potentially only accessible to some well-resourced groups,” Matthews said. “Unless we act expeditiously, it would be the ultimate unlevel playing field for security.”

Code-based cryptography based on coding theory, Matthews’ area of expertise, is one of the few mathematical techniques that enables the construction of quantum-safe cryptosystems — resilient to both today’s computers and quantum computers of the future. 

It works by introducing errors or distortion in a way that keeps information secret from unauthorized users. An authorized user can decode a message, but the code and encrypted data remain unintelligible to an eavesdropper.

Mathematicians have been exploring these “error-correcting codes”  since the late 1940s, and coding theory provided a foundation for technology such as CDs, DVDs, and even 5G.

“Coding theory is thankfully already in our arsenal, though it is being applied in novel and unexpected ways to build quantum-safe cryptosystems,” Matthews said.

Along with other researchers at Virginia Tech and elsewhere, Matthews is investigating ways to speed up and condense the codes without creating security vulnerabilities.

“It’s a difficult-to-achieve tightrope walk, evidenced by the long list of codes tried and broken,” Matthews said. “But this process moves the field forward and leads to new, potentially more secure cryptosystems.”

Other hard problems remain, beyond those that support the security of the cryptosystems, such as: What does implementation look like? Who should convert to these new quantum-safe cryptosystems? What system is best for a particular application? 

Researchers are drawing from and iterating on a long history of hard problems to protect our data in the here and now — and into a quantum future.

Related stories

Commonwealth Cyber Initiative researchers hone cryptographic algorithms to stand against powerful quantum threat

Saddling up cryptosystems for a quantum showdown