Filter by topic and date
Internet Security vs. Quantum Computing
22 Apr 2015
One of the great scientific challenges of our time is the construction of a practical quantum computer.
Such a machine would use the counterintuitive principles of quantum physics, and it 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, designing new types of drugs, and of course, breaking most of the cryptographic systems that are in use today. Fortunately, no one has yet built a practical quantum computer, though many countries and companies are striving do just that. For example, the U.S. government has spent more than $80M USD on a project with that aim. 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 quantum computing will become a reality. When that happens, we will be living in a post-quantum world.
Without actually having a quantum computer in hand, we are using theories to make educated guesses about the capabilities of these yet-to-be-realized machines. It is widely believed that the public key cryptography that is in widespread use today will easily be broken by a quantum computer. It is also believed that the symmetric encryption algorithms and hash functions will remain largely secure, perhaps requiring the larger key sizes that are already widely implemented.
Can we begin the work to replace the algorithms that we depend on today, including RSA, DSA, ECDSA, DH, and ECDH? The research community is hard at work identifying algorithms that will be secure against the threat of quantum computing. Significant progress has been made, and some public algorithms are believed to be secure. When this work is ready, the IETF will need to adapt protocols to make use of the new algorithms.
The U.S. National Institute for Standards and Technology (NIST) recently organized a Workshop on Cybersecurity in a Post-Quantum World. It brought together people from the research community, government, and industry from all around the world to start the work on the development and standardization of cryptography that will still be secure in a post-quantum future. NIST deserves a round of applause for this well-planned event, and the presentations and discussions showed that good work has been done, but more is needed.
We 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 issues associated with those algorithms, such as large public keys. These algorithms have very large keys, and practical techniques are needed to handle them.
In our view, the first post-quantum secure algorithm to be standardized will be hash-based signatures. The security of hash-based signatures is well established. A well-engineered proposal for this type of signature was recently made to the IRTF Crypto Forum Research Group by Andreas Hülsing. If you are familiar with the original hash-based signatures proposed by Ralph Merkle in the late 1970s [1][2], you know that their main disadvantage is their long key generation time. The new proposal, called Extended Hash-Based Signatures or XMSS [3], uses multiple trees, in a hierarchical way, to solve that problem.
Other work has been brought to the IRTF and the IETF on hash-based signatures, including [4] and [5].
References:
[1] http://www.merkle.com/papers/Thesis1979.pdf
[2] http://en.wikipedia.org/wiki/Merkle_signature_scheme