U.S. announces first quantum-proof encryption recommendation

In the race between quantum computing and quantum-proof encryption, encryption crossed a major checkpoint on Tuesday — a win for the security of consumer and other data.

In 2016, the National Institute of Standards and Technology asked computer scientists to help it in its search for an encryption algorithm that can secure data against attacks using quantum computers. This week, the institute announced it would recommend a single mechanism for that purpose: Kyber.

Kyber is an open-source system for securely establishing a shared secret between parties to encode messages. In this way, it is like RSA, which is the most popular encryption scheme in use today and sits at the heart of many data encryption schemes. Unlike RSA, scientists have not discovered any algorithm that can crack Kyber.

Some major tech vendors already support Kyber to an extent, including Amazon as part of its Amazon Web Services offering. Cloudflare also supports Kyber in a cryptography library it built and maintains, and earlier this year released its plan for migrating to post-quantum cryptography.

Although none of these companies have announced they use Kyber to protect customer data, their early support signals that technology providers, like the government, are looking to Kyber as a (and perhaps the) post-quantum encryption algorithm of choice.

“Today’s announcement is an important milestone in securing our sensitive data against the possibility of future cyberattacks from quantum computers,” said Gina M. Raimondo, the secretary of commerce, in the announcement. “Thanks to NIST’s expertise and commitment to cutting-edge technology, we are able to take the necessary steps to secure electronic information so U.S. businesses can continue innovating while maintaining the trust and confidence of their customers.”

A team of 10 computer scientists from across Europe and North America built Kyber, which is based on an award-winning paper published in 2009 by Israeli-American computer scientist Oded Regev. After first submitting Kyber to NIST in 2017, the team has provided two major revisions that improve the overall security and efficiency of the tool.

Kyber exploits a field of mathematics called lattice problems. By contrast, RSA exploits a field of mathematics called the factoring problem. Phones, laptops, desktops, servers and other computers made en masse cannot solve the factoring problem, making RSA safe in most situations, but quantum computers will one day be able to crack the encryption.

Mathematicians have known since 1994 how a quantum computer could solve the factoring problem and therefore break RSA. The problem has been engineering a computer that can actually do so.

“While in the past it was less clear that large quantum computers are a physical possibility, many scientists now believe it to be merely a significant engineering challenge,” reads NIST’s webpage on post-quantum encryption.

Quantum computers have uses beyond the nefarious. They are not merely or even primarily made to break the encryption algorithms companies and governments use today.

Cyber security

The peril — and promise — of quantum computing

The technology does not yet exist, but in the not-too-distant future it could fundamentally transform how many organizations do business.

By John Heltman

January 3

Banks can look forward to faster artificial intelligence and financial modeling using quantum computers — as soon as a practicable quantum computer is available for them to use. In part for these reasons, banks including Wells Fargo and Goldman Sachs have taken steps into the quantum world.

The exact date commercial quantum computers will become capable of solving these problems is uncertain. Companies such as Google, IBM, Intel and Microsoft have poured billions into developing this new era of computing, and while quantum computers today can solve a small number of problems faster than classical computers, they do not threaten to break encryption or promise to develop new drugs for at least a few more years.

In 2020, the Global Risk Institute, a research organization formed by the Canadian government and the country’s largest financial institutions, surveyed 44 experts in quantum computing about the likelihood of “a significant quantum threat” to contemporary encryption algorithms. A majority of the surveyed experts assigned a less-than-1% likelihood of that threat arising by 2025.

Most assigned a likelihood of less than 5% that the threat would arise by 2030. However, their risk estimates for 2035 grew to around 50% likelihood, then to greater than 70% by 2040.

According to NIST, the fact that the inevitable quantum threat has not yet arrived makes today the perfect time to transition cybersystems from pre-quantum cryptography to post-quantum.

“This transition needs to take place well before any large-scale quantum computers are built, so that any information that is later compromised by quantum cryptanalysis is no longer sensitive when that compromise occurs,” reads NIST’s 2016 call for post-quantum encryption proposals. “Therefore, it is desirable to plan for this transition early.”