PQC

National Institute for Standards  and Technology (NIST) 8105 Report on Post-Quantum Cryptography (April 2016) frames the situation nicely, noting that in recent years there has been a substantial amount of research on quantum computers – machines that exploit quantum mechanical phenomena to solve mathematical problems that are difficult or intractable for conventional computers. If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems currently in use. This would seriously compromise the confidentiality and integrity of digital communications on the Internet and elsewhere. The UK National Cyber Security Centre concurs that the security of current approaches to asymmetric cryptography, as deployed in real-world systems that usually rely on either the difficulty of factoring integers (RSA) or calculating discrete logarithms (Diffie-Hellman, Elliptic Curve) is compromised in the presence of quantum computers.

Today, there are two known algorithms that quantum computers can use for cryptanalysis: Shor’s algorithm and Grover’s algorithm.

Shor’s algorithm first. The ability to quickly factor large numbers would break both RSA and discrete log-based cryptography. The fastest algorithm for integer factorization is the general number field sieve, which runs in sub-exponential time. However, in 1994 Peter Shor developed a quantum computer algorithm for integer factorisation that runs in polynomial time, and therefore would be able to break any RSA or discrete log-based crypto-system (including those using elliptic curves). This implies that all widely used public key cryptography would be insecure if someone were to build a quantum computer.

The other algorithm is Grover's, which is able to invert functions in O(√n) time. This algorithm would reduce the security of symmetric key cryptography by a root factor, so AES-256 would only offer 128-bits of security. Since increasing the security of a hash function or AES by a factor of two is not very burdensome, Grover’s algorithm does not pose a serious threat to symmetric cryptography. Furthermore, none of the pseudorandom number generators suggested for cryptographic use would be affected by the invention of a quantum computer, other than perhaps the O(√n) factor incurred by Grover’s algorithm.

So, symmetric cryptography, and also forms of asymmetric cryptography built entirely from symmetric primitives, such as hash-based signatures, are not regarded as being vulnerable to quantum computation, as the best attacks are considered to be infeasible provided one uses large enough key (and block) sizes. In particular, when used with 256-bit keys, the AES block-cipher is currently considered to be safe from attack by any future conventional or quantum computer.

Vulnerabilities

A summary of the current situation is shown in the table below, which lists the impact of quantum computer on different cryptographic algorithms and thus highlights where vulnerabilities are.

Cryptography Use Case	Example in Common Use	Impact of Quantum Computer
Hashing	SHA2, SHA3	None
Symmetric	AES	Longer key sizes needed
Asymmetric	Factoring (RSA)	Devastating
Asymmetric	Discrete Log (DH)	Devastating

To attack asymmetric cryptography, the bad guys need to perform an active attack (which would require access to a quantum computer) to forge a signature, but may passively collect data now and then break key agreements in the future once a quantum computer becomes available. This is worth doing in order to obtain the session keys that are used to encrypt message contents (in, for example, PGP). So even if you can’t read messages now it is still worth collecting them to break them in the future. This means that transitioning current systems to use quantum-safe key agreement schemes should be considered as a higher priority than transitioning to quantum-safe digital signatures.

The timescales are obviously unknown, but bear in mind that even a small 30-qubit universal quantum computer could, theoretically, run at the equivalent of a classical computer operating at 10 teraflops (10 trillion flops, or 10¹²), according to David Deutsch, at the University of Oxford’s Centre for Quantum Computation. NIST’s current estimate is that the first cryptographically relevant quantum computer could be built by 2030 for a cost of about one billion US dollars.

Countermeasures

Broadly speaking, there are two very different approaches to protecting against the threat posed by quantum computation. One is quantum key distribution, or QKD, which exploits quantum properties of physical systems, and so requires specialised hardware. The other is post-quantum cryptography, or PQC, which, as with existing forms of asymmetric cryptography, exploits the intractability of certain mathematical problems, and so can be implemented in hardware or software.

The goal of PQC (also called quantum-resistant cryptography, QRC) is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks. Based on current understanding, the NCSC believe that for most real-world communications systems, and particularly for government systems, PQC will offer much more effective and efficient security mitigations than QKD.

NIST initiated a “traditional” multi-round process to solicit, evaluate, and standardise one or more PQC public-key algorithms. The Round 2 candidates were announced January 30, 2019. There are 17  candidate public-key encryption and key-establishment algorithms together with nine different digital signature algorithms.

These algorithms are, essentially, in three different “families” that rely on different sources of mathematical difficulty. Lattice cryptosystems are built using geometric structures known as lattices and are represented using matrices. Code-based systems use error-correcting codes, as have been used in information security for decades. Multivariate systems depend on the difficulty of solving a system of quadratic polynomial equations over a finite field. Early opinion sees lattices as the most actively studied and the most flexible. They are capable of key exchanges, digital signatures, and far more sophisticated constructions like fully homomorphic encryption which, while not widely used now, we might expect to see at the heart of future business infrastructure in response to the continuing cyberwar around us.

Therefore, it seems to me that if we are to take a first step in the space (eg, sponsoring an M.Sc, maybe at Royal Holloway, or perhaps even sponsoring a Ph.D again) then the area to focus on is quantum-safe key agreement schemes using lattices. Is it reasonable goal to  have someone build one of these to run on a quantum computer simulator that we could use in a real payment system in, say, three years?