Quantum Cryptography for Risk Managers or Shor, Grover, and the CryptoApocalypse
Posted by David Gamey on 23 Sep 2021.
According to some, quantum cryptography will revolutionize cryptography, kill our current ciphers, and reveal all our secrets. But if you're a risk manager, you're likely turnedoff by claims of an impending cryptoapocalypse. You want to get past the hyperbole to something you can work with. You will want to know how likely this is, how to sort out facts from spin, what kinds of resources are available, how long you've got to prepare, and what preparation and planning do you need to do. You need to understand that quantum isn't just one thing, one risk, or the only risk. Join us as we break it all down for you.
Image Credit: Copyright Intel Corporation
Before we dig in, quantum computing isn’t the only driver of cryptographic change. Regardless of the eventual impact of quantum computing, organizations will still have to manage cryptographic changes. Or put another way, even if workable scalable quantum computers never happen, organizations will need to manage cryptographic change and should be looking at building cryptographicagility programs.
Quantum Computers have tremendous potential and impact when, and if, we can get them working, overcoming technical challenges, and making them practical. In truth, we don't know when this will happen. We also don't know if we will encounter insurmountable obstacles or if there will be some new breakthrough that will make this happen sooner. However, uncertainty isn’t license for inaction. If we are going to address this pragmatically, we need to understand the playing field and start planning. There are a few things we can say:
 Quantum cryptography is actually based on several different technologies and some of them are here today. We need to understand these broadly to respond appropriately. The old way to change crypto is slow, expensive, and disruptive. We need to do better.
 We can't wait until there is a practical quantum computer able to break our ciphers to change our algorithms. We need to change them sooner. We need a plan that addresses our data retention debt. If we wait too long our old cryptograms will be broken and our secrets revealed.
 Quantum technology is not the only risk to cryptography. Nonquantum cryptanalysis is improving the methods used to attack ciphers and protocols. We need to learn from the last two decades as cryptography will continue to evolve.
 Cryptographic change happens and in order to adapt it we need to understand both what assets we are protecting and how those assets are protected with cryptography.
 We want to manage the change, not panic the change. We will need to know where, what, and when changes are needed well in advance.
Generally speaking, quantum computers are misunderstood and some of the cutting edge research is strange to say the least. Understanding something of the technology behind quantum computing is helpful to understanding its impact. However, for our purposes, we don’t want to get too far off the beaten path where quantum computing is entangled with physics and philosophy. Some of the Quantum Computing in Perspective references (below) may help. For a cryptographic perspective, Schneier makes a number of valid points but basically concludes that there is no quantum cryptography crisis and important work is being done to avoid one. Aaronson tackles explaining quantum computing, problem spaces, and enough physics and philosophy to put it all together and provide a glimpse of where this is going. There are some takeaways from all of this:
 Quantum computers are very specific beasts, they aren’t supercomputer replacements, and they aren’t general purpose or universal.
 They provide ways to implement specific algorithms. The chandelierlike computers we see in articles are often wired for specific problems. Not all machines can implement all algorithms.
 The idea of superposed states has been badly explained, the idea of trying everything at once isn’t how it works. There are some fascinating details such as quantum states cancelling each other out and the necessity to rewind, or uncompute, states in a calculation. But for now, we are content to wait for better explanations and observe the results.
 Quantum algorithms are powerful because they operate in a different problem space than classical computers. In classical computer science, there are discussions of NP complete and Polynomial problem spaces, basically how hard the problem is to solve and how it scales. Introducing quantum effects means that there’s a much larger collection of these problem spaces like BPP and BQP. In the end, quantum computing just scales better – that is, if we can actually make it work at scale.
Many organizations try to exploit marketing buzz and hype with terminology like quantum, AI, ML, blockchain, etc. to gain attention, investors, and opportunities. Additionally, the science of quantum computing is advancing steadily. Consequently, it can be difficult to cut through the noise to get to the relevant information. Below, we break down specific applications of quantum technology that impact cryptography. Hopefully this will help your risk management teams put quantum cryptography into perspective and follow the developments.
CryptographicAgility
In simplest terms, cryptographicagility is the ability to manage risk and quickly deal with cryptographic change regardless if these are due to quantum computing or more conventional advances. Risk managers concerned with the impact of quantum computing will want to ensure they have a mature cryptoagility program that monitors areas of potential change including postquantum cryptography and advancements in quantum computing.
Existing Asymmetric (i.e. Public Key) Cryptography (e.g. RSA, ECC)
The ultimate quantum cryptanalysis boogeyman is Shor's algorithm. Shor’s has the potential to crush publickey ciphers like RSA and ECC. Estimates in 2019 put a break time on 2048bit RSA at 8 hours! Of course, the really BIG IF, is building a reliable enough quantum computer. Current machines not only fall dramatically short in qubits but they also can't keep it together long enough to complete the computations. Even if IBM builds their 1000 physical qubit machine in 2023, it will be far short of the 4096 logical qubits or 2M25M physical qubits required to crack RSA2048.
Even without quantum cryptanalysis, RSA is eventually doomed. As we move to longer and longer symmetric keys, RSA keys grow exponentially in length. With AES128 commonly in use, RSA keys require 3072 bits for equivalent strength. AES256 requires a whopping 15k bit long RSA key for equivalent strength. A paper described quantum resistant RSA with insanely long keys (the same paper also suggested a central key generation authority and created a bit of a controversy in the process).
ECC keys scale linearly but the cipher is still vulnerable to Shor’s algorithm. We could see ECC as an interim algorithm.
Symmetric Key Cryptography (e.g. AES)
Quantum cryptanalysis will also have a major impact on symmetric cryptography. Grover's algorithm provides a huge advance but it's nowhere near the boogeyman that is Shor's. A practical implementation of Grover's means our AES128 is no harder to break than a 64bit key basically setting us back over 2 decades. Like Shor’s, Grover’s algorithm also requires a large number of logical qubits (2,953 for AES128) and that 2 decade reset may not happen for a decade or more. Organizations worried about the longterm viability of 128bit cryptography should get off AES128 (and TDEA) as soon as possible. Standards bodies could easily deprecate 128bit keys. AES256 will remain as solid post quantum as AES128 is today. If new 512bit ciphers are needed, they could be developed going forward.
Grover’s algorithm also impacts preimage and collision attacks on MACs and Hashes in the same way as ciphers like AES. However, there are already a number of good nonquantum reasons to reconsider many hashing usecases (See CryptoAgility).
If Grover’s is as good as it gets, we should not be worried. Of course, cryptographicagility programs will need to move to stronger symmetric algorithms and pay attention to the retention of old cryptograms derived from shorter keys.
Post Quantum or Quantum Resistant Cryptography
Cryptographers and standards bodies aren't waiting for practical large scale quantum computing to become reality. Work is proceeding to replace the PublicKey encryption and digital signature algorithms are impacted by Shor's algorithm. As noted, symmetric key encryption is not considered at risk.
 NIST has sponsored a PostQuantum Cryptography Challenge to select a standard quantum resistant algorithm. This effort has progressed to the third round with 9 PublicKey Encryption candidates and 6 Digital Signatures candidates. The field is further divided into finalists and alternatives. NIST is currently favoring structured lattice schemes. There candidate algorithms have a wide range of key sizes and equivalent key strengths have yet to be documented. Draft standards are expected between 20222024.
 Microsoft and Google have run experiments with HSM vendors.
 Cloudflare has run experimental pilots to test out different algorithms.
 The Open Quantum Safe (OQS) project provides an opensource C library for PQC cryptography and also integrates with OpenSSL.
 The PCI Security Council actively monitors developments in this area for impact on payment systems through their Encryption Task Force and other working groups. The PCI ETF can be reached for questions at ETF@PCISecurityStandards.org.
Key Distribution
Quantum key distribution (QKD) is here today. It provides a method of remotely agreeing keys that provably cannot be eavesdropped without detection. It's very interesting and serves some niche applications. But how practical is it? Where does it fit?
While the keys may be agreed securely, can they be held and used securely? A challenge to the general use of this technology is that the keys are still available to classical technologies. And if the keys are used for classical ciphers, is there any real advantage in general use cases? Most organizations aren’t going to have QKD kit any time soon.
We can also, foresee potential jurisdictional and crossborder issues arising once this technology can be made to work at really long range.
Quantum Key Generation
A recent and interesting development is the use of quantum computers for random key generation. While we haven’t seen a lot on this it’s worth noting that we already have random sources that outperform pseudorandomnumbergenerators. And as some of the challenges to using this for general applications are similar to QKD, it’s hard to see this as more than fitting a special usecase.
Marketing Buzz and Spin vs. Reliability
Cryptography is not the only application for quantum technologies and there other interesting uses. As with any new technology (e.g. artificial intelligence, machine learning, blockchain) the interest in quantum also generates it's share of spin, hype, and misleading or false claims. Fortunately, the field of quantum cryptography gets a lot of scrutiny and reliable answers are available.
Learn More
Our annotated references broken down by topic. Many of the referenced articles have been covered in our weekly [In]Security News summaries https://controlgap.com/blog?tab=insecurity

CryptographicAgility:
 CryptographicAgility (2021) https://controlgap.com/blog/CryptographicAgility

Quantum Computing in Perspective:
 Scott Aaronson Talks About What Makes Quantum Computing So Hard to Explain and Why Your Expectations are probably wrong (2021) https://www.quantamagazine.org/whyisquantumcomputingsohardtoexplain20210608/
 NSA Quantum Computing FAQ including discussion of CRQC  “Cryptographically Relevant Quantum Computers” (2021) https://media.defense.gov/2021/Aug/04/2002821837/1/1/1/Quantum_FAQs_20210804.PDF
 Quantum computers will not cause all forms of conventional encryption to become insecure (2019) https://kryptera.ca/paper/201903/
 Quantum Computing Since Democritus; Aaronson; Cambridge University Press (2013) https://www.cambridge.org/core/books/quantumcomputingsincedemocritus/197A4CD13738E10AAD787DBB78D8E92C
 Why it might be impossible to build a practical quantum computer (2021) https://www.newscientist.com/article/mg25133493200whyitmightbeimpossibletobuildapracticalquantumcomputer/
 Cryptography after the Aliens Land (2018) – a future looking essay on the cryptography and the impact of quantum technologies https://www.schneier.com/essays/archives/2018/09/cryptography_after_t.html
 Quantum Cryptography: As Awesome As It Is Pointless (2008) – an essay on why quantum computing was (and is) still a long way off https://www.schneier.com/essays/archives/2008/10/quantum_cryptography.html

Shor’s Algorithm:
 Explanation of Shor's from IBM covering quantum modular multiplication, circuits, and quantum composer tool (undated) https://quantumcomputing.ibm.com/composer/docs/iqx/guide/shorsalgorithm
 Another explanation and example from the Qiskit opensource SDK (undated) https://qiskit.org/textbook/chalgorithms/shor.html
 Shor’s algorithm is implemented using five trapped ions (2016) https://physicsworld.com/a/shorsalgorithmisimplementedusingfivetrappedions/
 How a Quantum Computer could break RSA2048 in 8 hours (2019) https://www.technologyreview.com/2019/05/30/65724/howaquantumcomputercouldbreak2048bitrsaencryptionin8hours/

Grover's Unstructured Search Algorithm:
 Explanation of Grover's from IBM covering the oracle and the amplitude amplification procedure, circuits and quantum composer (undated) https://quantumcomputing.ibm.com/composer/docs/iqx/guide/groversalgorithm
 Qiskit example (undated) https://qiskit.org/textbook/chalgorithms/grover.html
 Another explanation (undated) https://www.quantuminspire.com/kbase/groveralgorithm/

PostQuantum (Quantum Resistant) Cryptography:
 Postquantum cryptography https://en.wikipedia.org/wiki/Postquantum_cryptography
 NIST PostQuantum Cryptography (PQC) Project (20162021) https://csrc.nist.gov/projects/postquantumcryptography
 Open Quantum Safe project (20172021) https://openquantumsafe.org/
 PostQuantum Cryptography: Current state and quantum mitigation (2021) https://www.enisa.europa.eu/publications/postquantumcryptographycurrentstateandquantummitigation
 NISTIR 8309 Status Report on the Second Round of the NIST PostQuantum Cryptography Standardization Process (2020) https://doi.org/10.6028/NIST.IR.8309
 Attack BeyondBirthdayBound MACs in Quantum Setting (2020) https://eprint.iacr.org/2020/1595
 IBM demonstrates CRYSTAL a quantum resistant public key cipher and NIST candidate (also has good explanations of the limitations of quantum computing) (2019) https://www.scientificamerican.com/article/newencryptionsystemprotectsdatafromquantumcomputers/
 The results of a TLS postquantum experiment are in and the ostrich outperformed the turkey (2019) results https://blog.cloudflare.com/thetlspostquantumexperiment/ and introduction https://blog.cloudflare.com/towardspostquantumcryptographyintls/
 More on NIST’s PostQuantum Cryptography (2020) https://www.schneier.com/blog/archives/2020/09/more_on_nists_p.html
 NIST Announces 3rd Round PostQuantum Cryptography (PQC) Standardization Candidates (2020) https://content.govdelivery.com/accounts/USNIST/bulletins/296eed6 and https://www.schneier.com/blog/archives/2020/07/update_on_nists.html
 PQDH: A QuantumSafe Replacement for DiffieHellman based on SIDH (2019) https://eprint.iacr.org/2019/730
 Quantum resistant RSA (2017) – limited utility and controversial – very long keys and suggestions of using a central key generation authority. RSA is based on n=p*q, today n is 4096 bits, to make it work post quantum the primes p & q each have 4096 bits each. To use a symmetric key analogy this is a bit like split keys by using key halves vs. full length key parts. Link and discussion at https://www.schneier.com/blog/archives/2017/05/postquantum_rs.html

Quantum Key Distribution:
 Wikipedia https://en.m.wikipedia.org/wiki/Quantum_key_distribution
 Quantum Key Distribution: Is it as secure as claimed and what can it offer the enterprise? (2021) https://www.theregister.com/2021/07/06/quantum_key_distribution/
 Scientists Have Made a Quantum Key Distribution Encryptor 1,000 Times Smaller Than What Came Before (2019) http://www.sciencealert.com/scientistshavemadeaquantumchipthats1000timessmallerthanbefore
 Vulnerabilities in Quantum Key Distribution Protocols (2003) https://csrc.nist.gov/publications/detail/nistir/6977/final

Quantum Key Generation:
 AWS researcher merges the power of two quantum computers to help make cryptography keys stronger (2021) https://www.zdnet.com/article/awsresearchermergesthepoweroftwoquantumcomputerstohelpmakecryptographykeysstronger/
 And then there is this (2021) https://physicsworld.com/a/fastquantumrandomnumbergeneratorfitsonafingertip/
 Example of strong nonquantum random keys using a Geiger counter and some statistics (2017) http://poseidon2.feld.cvut.cz/conf/poster/poster2017/proceedings/Poster_2017/Section_EI/EI_040_Ruschen.pdf

Quantum Computers:
 List of Quantum processors https://en.m.wikipedia.org/wiki/List_of_quantum_processors
 Not all Qubits are equal (Physical vs. Logical) https://en.m.wikipedia.org/wiki/Physical_and_logical_qubits
 Scientists Just Simulated Quantum Technology on Classical Computing Hardware (2021) – the Quantum Approximate Optimization Algorithm (QAOA) for the MAXCUT problem https://www.sciencealert.com/quantumcircuitssimulatedonclassicalcomputerstestthelimitsoffuturetechnology, https://www.nature.com/articles/s4153402100440z, and https://en.wikipedia.org/wiki/Maximum_cut
 Google tries out error correction on its quantum processor (2021) https://arstechnica.com/science/2021/07/googletriesouterrorcorrectiononitsquantumprocessor/
 RecordBreaking Chinese Supercomputer Marks New Quantum Supremacy Milestone (2021, 66 Qubits) https://www.sciencealert.com/chinaslatest56qubitcomputermarksanotherquantummilestone
 Scientists Achieve 'Transformational' Breakthrough in Scaling Quantum Computers (2021) https://www.sciencealert.com/scientistsachievetransformationalbreakthroughinscalingupquantumcomputers and https://www.independent.co.uk/lifestyle/gadgetsandtech/quantumcomputingmicrosoftresearchqubitrecordb1797144.html
 IBM Just Committed to Having a Functioning 1,000 Qubit Quantum Computer by 2023 (2020) https://www.sciencealert.com/ibmthinksitllhavea1000qubitquantumcomputerrunningwithinthreeyears
 Chinese Scientists Claim Breakthrough in Quantum Computing Race (2020) https://www.bloomberg.com/news/articles/20201204/chinesescientistsclaimbreakthroughinquantumcomputingrace
 How Many Qubits Are Needed for Quantum Supremacy? (2020) https://spectrum.ieee.org/techtalk/computing/hardware/qubitsupremacy
 How a Quantum Physicist Invented New Code to Achieve What Many Thought Was Impossible (2020) https://scitechdaily.com/howaquantumphysicistinventednewcodetoachievewhatmanythoughtwasimpossible/
 IBM throws some Quantum shade at Google's leaked supremacy paper (2019) https://www.wired.com/story/ibmgooglesquantumleapquantumflop/
 Last month's leaked paper is out  Google AI Blog: Quantum Supremacy Using a Programmable Superconducting Processor (2019) http://ai.googleblog.com/2019/10/quantumsupremacyusingprogrammable.html
 Google may have just passed the Quantum Supremacy milestone but it isn’t a practical application (2019) https://www.wired.com/story/whygooglesquantumcomputingvictoryisahugedealandaletdown/
 Decoherence is a major problem that must be solved before quantum computers can be effective (2019) https://blogs.scientificamerican.com/observations/theproblemwithquantumcomputers/
 Qutrit's are a more powerful alternative to qubits, now researchers demonstrate new path to reliable quantum computation (2019) https://phys.org/news/201906pathreliablequantum.html. Note, ternary has been used in computers before https://enacademic.com/dic.nsf/enwiki/1425638
 Dwave can't run Shor (2017) https://arstechnica.com/science/2017/01/explainingtheupsideanddownsideofdwavesnewquantumcomputer/

Some are other “quantum technologies” not covered nor directly relevant to this article: