Mar 17 2019

Post-Quantum Cryptography in a Pre-Quantum World

The Quantum Computer is becoming a reality sooner than we thought – possibly in less than five years. Nation State-sponsored research from the US, China, France, and the UK are leading innovators. Major corporations such as IBM, Microsoft, Google, Rigetti, and Alibaba are releasing cloud-based access to quantum computers with coding languages being developed. Organizations such as NASA, Lockheed Martin, Royal Bank of Scotland Group are developing practice applications for the implications of the exponential computing advantages that Quantum Computers can deliver for particular tasks such as AI, Molecular Modeling, Financial Modeling, and Logistics just to name a few. Many experts say this “Post Quantum World” will be a reality much sooner than expected.

There is a ‘dual-edged sword’ effect of quantum computers in relation to cryptography. On one side, quantum computers could render current encryption algorithms obsolete; breaking our current AES 256 bit standard in about 20 seconds. This would create chaos. On the other side of the blade, there is quantum key distribution (QKD). A method by which quantum computers can be used to create a method of unbreakable key distribution impervious to man in the middle attacks. Two popular QKD protocols are BB84 [1] an E91 [2]. This is for the key distribution – not the encryption itself – which would be transmitted over a secure channel with a provably secure one-time pad quantum generated random key.

Today’s cryptography is based on complex mathematical problems such as elliptic curves, factorization, and discrete logarithms – all of which will not withstand a practical quantum computer using currently developed algorithms such as Shor’s Algorithm [3]. Post Quantum Cryptography (PQC) will need to make it reasonably impenetrable by quantum computing.

Three major families of quantum resistant algorithms are leading the way in many forms. Lattice cryptosystems are built using geometric structures known as lattices and represented using matrix arrays. Code-based systems using error-correcting codes and multivariate systems based on solving a system of quadratic polynomial equations over a finite field are also being developed as these would all make it reasonably difficult to crack. “Reasonably” difficult is our current standard – meaning, you can crack today’s encryption method using a brute force method; however, it would take all the computing power globally dedicated to this single task, and the number of years needed to exhaust the 256-bit key space would be about 3×10 to the 51st power. That doesn’t sound too “reasonable” to me.

The National Institute of Standards and Technology (NIST) [4] has initiated a process to standardize one or more quantum-resistant public-key algorithms and are, at the time of this posting, in the Round 2 Candidates selection process. It will be soon time to “Adapt and change”.

[1] – BB84 Protocol – Charles H Bennett and Gilles Brassard (1984)

[2] – E91: Protocol: Artur Ekert (1991)

[3] – Shor’s Algorithm: Peter Shor (1984)

[4] – https://csrc.nist.gov/Projects/Post-Quantum-Cryptography

Photo by Lars Plougmann

BACK TO BLOGS