$1M NSF Award Supports Reimagining Cryptography in a Post-Quantum World

In 1994, mathematician Peter Shor developed an algorithm showing how then-hypothetical quantum computers could factor numbers exponentially faster than standard machines. This promise of exotic computational power launched the age of quantum computing. It also set the clock ticking on existing public-key cryptography that provides safeguards for online banking, medical records, national secrets and more based on the infeasibility of factoring massive numbers.

Today, with Google, IBM and College Park-based startup IonQ racing to introduce the world’s first general-purpose quantum computer, University of Maryland researchers—backed by $1 million in funding from the National Science Foundation—are developing a framework for cryptographic systems that can weather increasingly powerful quantum computers. They are also focused on fundamentally changing the way that cryptography is taught, developed and practiced.

“The aim of our work is to help build the foundational theory of cryptography in a post-quantum future,” said Jonathan Katz, a professor of computer science and principal investigator of the award. “We know that many aspects of classical cryptography will look very different in a world where everyone, both honest parties and attackers, have access to quantum computers.”

Assisting Katz on the NSF award are Dana Dachman-Soled, an associate professor of electrical and computer engineering, and Gorjan Alagic, an associate research scientist in the University of Maryland Institute for Advanced Computer Studies (UMIACS), where Dachman-Soled also holds an appointment.

The researchers will explore constructions of cryptosystems that can be proven secure against quantum computers. Initially they will focus on the private-key setting. Two kinds of cryptography are currently in use: public-key and private-key. The former is ideal for negotiating a connection over the internet but slow for sending data. The latter is very fast but needs a preexisting, already-negotiated connection. In practice, both types get used often.

It is known that quantum computers would pose a dangerous threat to current public-key cryptosystems, Alagic said, but security of private-key systems against quantum computers is less well understood. One strategy is to establish mathematical theorems that say things like, “breaking this private-key cryptosystem would take a quantum computer that's this powerful.”

Alagic and the other researchers are working closely with the National Institute of Standards and Technology in this area, as the federal agency is ultimately tasked with establishing the benchmarks for any post-quantum security regulations or protocols.

A key element of the NSF grant is to explore new options in education, Katz said. While cryptography in a post-quantum future will require people to think differently about the challenge of securing critical information, it will also require new knowledge on quantum-based security features that are not currently possible.

Educational initiatives are already underway, with the UMD faculty helping organize a summer school on quantum and post-quantum cryptography at the University of California, Los Angeles last year. The weeklong event brought together physicists and computer scientists and included introductory talks on cryptography and quantum computing, invited talks on post-quantum assumptions and proof techniques, and poster and mentoring sessions.

Dachman-Soled said that although she believes existing public-key cryptosystems will remain in use for the near future, she is incorporating a module on post-quantum cryptography in the undergraduate course she teaches at UMD.

She is also working with a team of Gemstone Honors Program students to extend the functionality of a toolkit she developed to analyze the security of post-quantum cryptosystems when “side-information” is available. Examples include a system’s timing, power consumption and electromagnetic leaks, which can be used as a sort of “hint” in attacks to break the cryptosystem, Dachman-Soled explained.

To get younger students interested in quantum cryptography, Alagic recently visited an elementary school and a middle school in Montgomery County, Md., as part of each school’s career-day programming.

“The kids were great,” he said. “The elementary school students enjoyed it so much they actually sent me thank-you notes encrypted with the Caesar cipher I taught them.”