$1M NSF award supports reimagining cryptography in a post-quantum world

A new $1M NSF award is examining "Cryptography in a Post-Quantum Future." The PI for the award is Jonathan Katz (CS/UMIACS).

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 ISR-affiliated Associate Professor Dana Dachman-Soled (ECE/UMIACS) 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.” --- Story by Melissa Brachfeld of Maryland Today

Abstract

Quantum computers appear imminent. Indeed, after decades of theoretical work demonstrating the power of quantum computation, followed by steady experimental progress in academia, several large companies and startups are now investing significant resources in building quantum computers. It has long been understood that the advent of quantum computers would render currently deployed public-key cryptosystems insecure. NIST's post-quantum standardization effort will address this, but is only the tip of the iceberg. Cryptography in a post-quantum future does not merely involve swapping out one set of hard problems for another, but instead requires a paradigm shift in the way we think about attackers and approach the challenge of securing information.

This project brings together researchers with complementary expertise in classical (including post-quantum) cryptography and quantum cryptography to develop new foundational theories needed for quantum-secure cryptography and, equally importantly, to train the next generation of students to "natively" view cryptography from a quantum perspective. Some of the problems to be addressed include (1) security of symmetric-key primitives against quantum attackers; (2) investigating the power of the quantum random-oracle model; and (3) seeking to overcome existing impossibility results by exploring (3a) cryptosystems in which honest parties use quantum computation (but classical communication) and (3b) classical constructions proven secure via quantum reductions.

Published July 15, 2022