U.S. National Security Agency Issues Update on Quantum-Resistant Encryption

quantum computer stock image
(Image credit: Shutterstock)

The U.S. National Security Agency (NSA) has issued a FAQ (PDF) titled "Quantum Computing and Post-Quantum Cryptography FAQs" where the agency explores the potential implications for national security following the likely arrival of a "brave new world" beyond the classical computing sphere. As the race for quantum computing accelerates, with a myriad of players attempting to achieve quantum supremacy through various, exotic scientific investigation routes, the NSA document explores the potential security concerns arising from the prospective creation of a “Cryptographically Relevant Quantum Computer” (CRQC).

A CRQC is the advent of a quantum-based supercomputer that is powerful enough to break current, classical-computing-designed encryption schemes. While these schemes (think AES-256, more common on the consumer side, or RSA 3072-bit or larger for asymmetrical encryption algorithms) are virtually impossible to crack with current or even future supercomputers, a quantum computer doesn't play by the same rules due to the nature of the beast and the superposition states available to its computing unit, the qubit.

With the race for quantum computing featuring major private and state players, it's not just the expected $26 billion value of the quantum computing sphere by 2030 that worries security experts - but the possibility of quantum systems falling into the hands of rogue entities. We need only look to the history of hacks in the blockchain sphere to see that where there is an economic incentive, there are hacks - and data is expected to become the number one economic source in a (perhaps not so) distant future.

Naturally, an entity such as the NSA, which ensures the safety of the U.S.'s technological infrastructure, has to not only deal with present threats, but also future ones - as one might imagine, it takes an inordinate amount of time for entities as grand as an entire country's critical government systems to be updated.

According to the NSA, "New cryptography can take 20 years or more to be fully deployed to all National Security Systems (NSS)". And as the agency writes in its document, "(...) a CRQC would be capable of undermining the widely deployed public key algorithms used for asymmetric key exchanges and digital signatures. National Security Systems (NSS) — systems that carry classified or otherwise sensitive military or intelligence information — use public key cryptography as a critical component to protect the confidentiality, integrity, and authenticity of national security information. Without effective mitigation, the impact of adversarial use of a quantum computer could be devastating to NSS and our nation, especially in cases where such information needs to be protected for many decades."

The agency's interest in quantum computing is such, even, that as a part of the document trove leaked by Edward Snowden, it was revealed that the agency invested $79.7 million in a research program titled “Penetrating Hard Targets” - which aimed to explore whether a quantum computer for actually breaking traditional encryption protocols was feasible to pursue at the time.

This is especially important considering that an algorithm that can be employed by a quantum computer to break traditional encryption schemes already exists in the form of Schor's algorithm, first demonstrated in 1994 - before humanity's control over the qubit was all but a distant dream. The only thing standing in the way of the Schor algorithm's implementation at a quantum level is that it requires a much larger amount of qubits than is currently feasible - orders of magnitude higher than today's most advanced quantum computing designs, that max out at around "only" one hundred qubits

It is only a matter of time, however, before such systems exist. The answer lies in the creation and deployment of so-called post-quantum cryptography - encryption schemes designed to give pause to or even completely thwart future CRQCs. These already exist. However, their deployment at a time where the cryptographic security threat of quantum computing still lays beyond the horizon, implementing post-quantum cryptography would present issues in terms of infrastructure interoperability - different systems from different agencies and branches sharing confidential information between themselves and understanding what they're transmitting between each other.

In its documentation, NSA puts the choice on exactly what post-quantum cryptography will be implemented by the U.S. national infrastructure on the feet of the National Institute of Standards and Technologies (NIST), which is "in the process of standardizing quantum-resistant public key in their Post-Quantum Standardization Effort, which started in 2016. This multi-year effort is analyzing a large variety of confidentiality and authentication algorithms for inclusion in future standards," the NSA writes.

But contrary to what some would have you think, the NSA knows that it's a matter of time before quantum computing turns the security world on its proverbial head. There's no stopping the march of progress; as the agency writes, "The intention is to (...) remove quantum-vulnerable algorithms and replace them with a subset of the quantum-resistant algorithms selected by NIST at the end of the third round of the NIST post-quantum effort."

Quantum is coming; Post-quantum security must come before it.

Francisco Pires
Freelance News Writer

Francisco Pires is a freelance news writer for Tom's Hardware with a soft side for quantum computing.

  • R_1
    "The agency's interest in quantum computing is such, even, that as a part of the document trove leaked by Edward Snowden, it was revealed that the agency invested $79.7 million in a research program titled “Penetrating Hard Targets” - which aimed to explore whether a quantum computer " it ends there abruptly. end of paragraph 4. delete comment after correction thanks
    Reply
  • GenericUser
    Shouldn't the title be "...Quantum-Resistant Encryption" instead of Crypto-Resistant Encryption? Or am I missing something? Crypto resistant makes it sound like the encryption is resistant to itself or something.
    Reply
  • Sippincider
    What happens when something that's been quantum-encrypted with infinite combinations, gets attacked by a quantum-decrypter that runs all the combinations at once?

    The Universe folds onto itself with a divide-by-zero error?
    Reply
  • husker
    Sippincider said:
    What happens when something that's been quantum-encrypted with infinite combinations, gets attacked by a quantum-decrypter that runs all the combinations at once?

    The Universe folds onto itself with a divide-by-zero error?

    Doing my best Neil Degrasse Tyson impersonation, I would say: Actually, some infinities are larger than other infinities. So the system (the encryption or the attacker) that uses the largest infinity will win out in the end. How can one infinity be larger than another, you ask? One common explanation is this: The list of whole numbers (1, 2, 3, ...) is infinite. But the number of real numbers between any 2 whole numbers is also infinite. So the list of all real numbers between all whole numbers contains an infinity of infinities, and therefore is larger than the first infinity.
    Reply