Making Cryptosystems More Secure in the Presence of Quantum Computers

Quantum computing is increasingly seen as a way to solve unique mathematical problems that currently require substantial time and resources for conventional computers—from large-scale pharmaceutical testing, to complex financial modeling, to better predicting extreme weather events.

Another area where quantum computers will excel—if, and when, they become feasible—is the ability to break many of the public-key cryptosystems currently in use, a scenario that would seriously compromise the confidentiality and integrity of many of today’s digital communications.

Dana Dachman-Soled (in photo), an assistant professor of electrical and computer engineering, is currently leading an effort to analyze the security of certain “post-quantum” cryptosystems—cryptographic systems that will remain secure in the presence of a quantum computer.

The project, supported by the National Institute of Standards and Technology (NIST), includes Léo Ducas, a researcher at Centrum Wiskunde & Informatica in the Netherlands; Mélissa Rossi, a doctoral student at the École Normale Supérieure in Paris, France; and Huijing Gong, a sixth-year doctoral student in computer science at the University of Maryland.

Dachman-Soled says that one of the foremost avenues for efficient, post-quantum cryptosystems is to construct cryptosystems from “lattice problems,” a type of mathematical problem that is believed to be hard even for quantum computers.

In a recent paper, "LWE with Side Information: Attacks and Concrete Security Estimation," the researchers presented their concepts for breaking lattice-based cryptosystems, also referred to as cryptanalysis of lattice-based schemes.

Dachman-Soled says it’s important to research the best algorithms for breaking cryptosystems in order to inform the setting of concrete parameters for standardized cryptosystems. These parameters must be set so that the security of the resulting cryptosystems cannot be compromised, even by hackers with very large amounts of computational resources.

The NIST-supported team has developed a publicly available toolkit that provides estimates for the concrete security of lattice-based cryptosystems when side-channel information is incorporated. Examples of side-channel information include timing information, power consumption, and electromagnetic leaks from the computer system. This information can be used as a sort of “hint” in an attack to break the cryptosystem.

Specifically, the toolkit provides scripts to automatically analyze the performance of so-called “lattice reduction algorithms” when side-information is available.

“We envision this toolkit will be valuable for comparing the concrete security of various schemes that are candidates for standardization,” says Dachman-Soled. “It will also be useful for analyzing the security degradation of such schemes when exposed to side-channel attacks. Finally, it provides a unified framework for these types of analyses that will simplify future work.”

The team’s paper has been accepted to the 40th Annual International Cryptology Conference (Crypto 2020), which is organized by the International Association for Cryptologic Research. The event is scheduled to take place online August 17–21.

***
Note: Dana Dachman-Soled was recently promoted to associate professor, effective July 1. In addition to her tenure appointment, she has an appointment in the University of Maryland Institute for Advanced Computer Studies and is a core faculty member in the Maryland Cybersecurity Center.

—Story by Melissa Brachfeld