Cybersecurity in the Post-Quantum Era

One of the great scientific challenges of our time is the construction of a practical quantum computer. Operating using the counterintuitive principles of quantum physics, such a device could rapidly explore an vast number of possible states. It could perform computational tasks that are far beyond our current capabilities, such as modeling molecules and designing new types of drugs—and breaking most of the cryptographic systems that are currently in use. Fortunately, no one has yet built a practical quantum computer, though many countries and companies are striving do just that. It has been claimed that the U.S. National Security Agency has a secret US$80M project with that aim, for example. Quantum computing is still an unproven technology, and it may not be practical for decades, but since it poses an existential threat to cryptography, we need to start preparing now for the possibility that one day the news will announce a breakthrough in quantum computing, and we will be living in a post-quantum world.

The U.S. National Institute for Standards and Technology (NIST) recently organized a Workshop on Cybersecurity in a Post-Quantum World to bring together people from the research community, government, and industry, and to work toward the development and standardization of cryptography that will still be secure in a post-quantum future. While it is believed that the public key cryptography that is currently in widespread use—RSA, DH, ECDH, ECDSA—will easily be broken by a quantum computer, there are other public algorithms that are believed to be secure. There is important work to be done here: identifying algorithms that will be secure against the threat of quantum computing, establishing the detailed parameter choices and techniques needed for their secure use, and developing standards that can ensure that we can trust cryptography even after a breakthrough is announced. NIST deserves kudos for this well-planned event, and to my mind, the presentations and discussions showed that while good work has been done, more is needed.

At the workshop, I had the pleasure of giving an invited talk on Living with post-quantum cryptography and participating in the panel on Shoring up the Infrastructure: A strategy for Standardizing Hash Signatures organized by Burt Kaliski of Verisign. In my talk, I argued in favor of a pragmatic systems engineering approach, in which we embrace algorithms that are the most mature and well-reviewed, and thus are the most deserving of our confidence, and that we then use systems engineering to mitigate the performance issues associated with those algorithms, such as large public keys. Those algorithms might have very large keys, but security is our paramount goal, and there are plenty of practical techniques that we can apply to make living with large keys practical. Probably the first post-quantum secure algorithm to be standardized will be hash-based signatures because their security is well established. A well-engineered proposal for this type of signature was recently made to the IRTF Crypto Forum Research Group, and Andreas Hülsing gave a good overview at the workshop. If you are familiar with the original Merkle signatures, you will know that their main disadvantage is their long key generation time. The new proposal uses multiple trees, in a hierarchical way, to solve that problem.

Cisco’s own Scott Fluhrer, technical leader for cryptography, and Chris Shenefiel, program manager for advanced security research, also attended the workshop. In addition to this current interest, Cisco has provided funding for a number of research projects into quantum-secure cryptography over the years, including

• Biasi, Barreto, Misoczki, Ruggiero, Scaling efficient code-based cryptosystems for embedded platforms, 2012
• Bernstein, Lange, Peters, Smaller decoding exponents: ball-collision decoding, CRYPTO 2011
• Bernstein, Lange, Peters, Wild McEliece Incognito, PQC 2011
• Bernstein, Grover vs. McEliece, PQC 2010
• Burleson, Paar, Heyse, Alternative Public-Key Algorithms for High-Performance Network Security, 2011

More information on Cisco Research is available online.

Share