Reports on Computer Systems Technology
The Information Technology Laboratory (ITL) at the National Institute of Standards and
Technology (NIST) promotes the U.S. economy and public welfare by providing technical
leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test
methods, reference data, proof of concept implementations, and technical analyses to advance the
development and productive use of information technology. ITL’s responsibilities include the
development of management, administrative, technical, and physical standards and guidelines for
the cost-effective security and privacy of other than national security-related information in federal
information systems.
Abstract
In recent years, there has been a substantial amount of research on quantum computers –
machines that exploit quantum mechanical phenomena to solve mathematical problems that are
difficult or intractable for conventional computers. If large-scale quantum computers are ever
built, they will be able to break many of the public-key cryptosystems currently in use. This
would seriously compromise the confidentiality and integrity of digital communications on the
Internet and elsewhere. The goal of post-quantum cryptography (also called quantum-resistant
cryptography) is to develop cryptographic systems that are secure against both quantum and
classical computers, and can interoperate with existing communications protocols and networks.
This Internal Report shares the National Institute of Standards and Technology (NIST)’s current
understanding about the status of quantum computing and post-quantum cryptography, and
outlines NIST’s initial plan to move forward in this space. The report also recognizes the
challenge of moving to new cryptographic infrastructures and therefore emphasizes the need for
agencies to focus on crypto agility.
Keywords
post-quantum cryptography; public key cryptography; quantum computing; qua
In the last three decades, public key cryptography has become an indispensable component of
our global communication digital infrastructure. These networks support a plethora of
applications that are important to our economy, our security, and our way of life, such as mobile
phones, internet commerce, social networks, and cloud computing. In such a connected world,
the ability of individuals, businesses and governments to communicate securely is of the utmost
importance.
Many of our most crucial communication protocols rely principally on three core cryptographic
functionalities: public key encryption, digital signatures, and key exchange1
. Currently, these
functionalities are primarily implemented using Diffie-Hellman key exchange, the RSA (RivestShamir-Adleman) cryptosystem, and elliptic curve cryptosystems. The security of these depends
on the difficulty of certain number theoretic problems such as Integer Factorization or the
Discrete Log Problem over various groups.
In 1994, Peter Shor of Bell Laboratories showed that quantum computers, a new technology
leveraging the physical properties of matter and energy to perform calculations, can efficiently
solve each of these problems, thereby rendering all public key cryptosystems based on such
assumptions impotent [1]. Thus a sufficiently powerful quantum computer will put many forms
of modern communication—from key exchange to encryption to digital authentication—in peril.
The discovery that quantum computers could be utilized to solve certain problems faster than
classical computers has inspired great interest in quantum computing. Is quantum complexity
fundamentally different from classical complexity? When will large-scale quantum computers be
built? Is there a way to resist both a quantum and a classical computing adversary? Researchers
are working on these questions.
In the twenty years since Shor’s discovery, the theory of quantum algorithms has developed
significantly. Quantum algorithms achieving exponential speedup have been discovered for
several problems relating to physics simulation, number theory, and topology. Nevertheless, the
list of problems admitting exponential speedup by quantum computation remains relatively
small. In contrast, more modest speedups have been developed for broad classes of problems
related to searching, collision finding, and evaluation of Boolean formulae. In particular,
Grover’s search algorithm proffers a quadratic speedup on unstructured search problems. While
such a speedup does not render cryptographic technologies obsolete, it can have the effect of
requiring larger key sizes, even in the symmetric key case. See Table 1 for a summary of the
impact of large-scale quantum computers on common cryptographic algorithms, such as RSA
and the Advanced Encryption Standard (AES). It is not known how far these quantum
advantages can be pushed, nor how wide is the gap between feasibility in the classical and
About the Creator
Enjoyed the story? Support the Creator.
Subscribe for free to receive all their stories in your feed.
Comments
There are no comments for this story
Be the first to respond and start the conversation.