Education logo

Quantum computing

computing

By Falfala DusanePublished 2 years ago • 3 min read
Quantum computing
Photo by Sergey Zolkin on Unsplash

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

student

About the Creator

Enjoyed the story? Support the Creator.

Subscribe for free to receive all their stories in your feed.

Subscribe For Free

Reader insights

Comments

There are no comments for this story

Be the first to respond and start the conversation.

Sign in to comment
    Written by Falfala Dusane