What’s Happening with Post-Quantum Cryptography at NIST?



In December 2016, the U.S. Government agency NIST (National Institute of Standards and Technology) put out a call for nominations for new post-quantum cryptographic algorithms that will be studied for potential use as a new future standard.  The deadline for the submission was November 30, 2017 and they received a total of 82 different submissions with 23 being for signed signature schemes and 59 for encryption or key encapsulation mechanisms (KEM) schemes.  NIST will be studying these schemes and will hold their first standardization conference on April 12-13, 2018 to review the various proposals.  For the next 3-5 years, NIST will analyze the proposals, hold more conferences, narrow the pool for second round evaluations, and provide a draft standard for public comment after they have completed their analysis.  Key attributes that NIST will be evaluating include security, performance, and other properties including drop-in replacements, perfect forward secrecy, resistance to side channel attacks, and others.

For more details on the standardization activities at NIST, you can go to their Post Quantum Cryptography web page.  There is also a good summary presentation made in December 2017 by Dr. Dustin Moody at the Asiacrypt 2017 conference that you can find here. And if you want to see a listing of all the submissions including links to their detailed descriptions, you can find them here.

So, why is NIST doing this?  Because one potential use of quantum computing would be to break the public key cryptography codes, such as RSA, that are currently used worldwide to protect many transactions on the Internet and other computer communications networks.  This is because the public key cryptography codes are based upon factoring a large number into two prime numbers.  Performing this calculation on a classical computer for the 2048 keys that are commonly used today would take billions and billions of years. But in 1994, mathematician Peter Shor came up with a quantum algorithm that could do this quickly on a quantum computer containing perhaps 10’s or 100’s of thousands of gates.  Although quantum computers of this size do not exist today, there are projections that such computers will exist within the next 10 to 20 years.  So this puts at risk many of the cryptography algorithms that are in use today.

Note that symmetric key algorithms, such as AES, are not based upon the factorization of a large number and cannot be attacked using Shor’s algorithm.  Although a quantum computer may be able to speed up a brute force attack slightly by using Grover’s algorithm, one could simply compensate by doubling the key size.  So, for example, the difficulty of breaking an AES code with a 256 bit key on a quantum computer would be roughly as difficult as breaking one with a 128 bit key on a classical computer.  This is still extremely hard, if not impossible, for the foreseeable future.

Since public key cryptography algorithms like RSA will be threatened in the next few years, researchers are working hard to find a solution.  The nature of the solutions fall into two broad camps.  The first uses quantum mechanics to develop quantum based cryptography that leverage the entanglement and no cloning theorems to communicate messages that are provably unbreakable because of basic quantum mechanical principles.  The second is to develop new classical algorithms, called post-quantum cryptography, that are not based upon factoring a large number and could not be broken using Shor’s or any other algorithm.

Both approaches have advantages and disadvantages.  The post-quantum cryptographic approach would only require software changes and could be dropped into existing infrastructure. Researchers will be studying the algorithms for the next several years to certify that there are not any known ways of attacking these codes on either a classical or a quantum computing.  However, one would never be 100% sure that someone has developed a way to crack the code and kept it secret from the rest of us.  The approach using quantum mechanics does provide a 100% assurance that the code cannot be cracked because of fundamental quantum mechanical principles, but it is a more costly and disruptive approach because it relies on new hardware and updated communications infrastructure.

Encryption based upon quantum mechanics will most likely be used in the military/government sectors where they need absolute assurance that a code won’t be broken and where cost is less of a factor.  The Chinese government, among others, is investing significantly into this approach.  But for more standard commercial applications, like processing credit card transactions over the Internet, the post-quantum cryptography approach will likely be the preferred path.   Microsoft, Google, and many other commercial companies all have ongoing efforts investigating this approach.

Leave a Reply

Your email address will not be published. Required fields are marked *


*


This site uses Akismet to reduce spam. Learn how your comment data is processed.