What is post-quantum cryptography

What is post-quantum cryptography

Quantum computing has become an imminent reality. Although the road to universal fault-tolerant devices still requires overcoming fundamental obstacles to achieve inherent stability, the roadmap to success is becoming clearer by the day, even shrinking as we progress.

But what does this mean for cybersecurity? Simply that killer quantum apps like Shor and Grover algorithms will soon be implementable on a quantum computer. We are not talking about proof-of-concepts, but implementations that will create risks for asymmetric key encryption protocols currently in use and to decentralized systems, such as blockchain technology.

While quantum communications, a field that has tremendous potential to attain unprecedented security levels, has yet to be fully mature and operational, a new mitigation solution has started to see the light: post-quantum cryptography, also known as PQC. PQC’s concept is to make use of encryption algorithms that are proven to be too complex to break for both classical and quantum computers.

Why is PQC important?

The importance of PQC comes from the relatively quick and practically feasible transition. Although challenging, it does not require a complete change of the infrastructure, and several of the algorithms previously unretained for asymmetric cryptography can be chosen from.

Asymmetric encryption is the most at risk, with RSA and ECC known to be broken through Shor’s factoring algorithm. A quantum computer respectively requires around 4,100 and 1,600 logical qubits to fully execute Shor’s algorithm to break RSA and ECC cryptography2, which is the challenge of finding the private key from the public key.

The NIST recommendations

In 2016, the National Institute for Standards and Technology (NIST) launched a competition to replace the vulnerable RSA and ECC protocols. Public Key Encryption protocols and Digital Signature Algorithms have seen a list of suitable replacements, with a big part of them shifting the focus from prime numbers factorization to lattice based mathematical problems.

In July 2022, NIST announced CRYSTALS-KYBERS algorithm as the winner for public key encryption and listed CRYSTALS-DILITHIUM, FALCON and SPHINCS+ as winners for the digital signature scheme. It is therefore recommended to switch to these encryption protocols to ensure that no quantum computer can decrypt one’s data. It is preferable to operate as soon as possible since store now – decrypt later scenarios can be harmful even years later, if data remains relevant like personally identifiable information.

Cybersecurity Strategy

Current encryption protocols suffer from two major weaknesses. First, they are based on mathematical complexity which is a conjecture. We compare the computational complexity of a problem through the most efficient algorithms that we know to solve it. This can induce into errors if a more efficient algorithm is discovered. Second, key management systems generate keys pseudo-randomly since classical computers cannot generate true random numbers.

Pseudo-randomness can be addressed as of today by making use of quantum random number generators, inherently random due to the nature of quantum physics. Today’s quantum devices are perfectly capable of achieving this.

Mathematical complexity must be assessed against currently existing quantum algorithms and with NIST recommendations, it is best to start mitigating to one of the retained protocols right away.

What comes after PQC?

Despite how important PQC is, one must remember that it remains a transition towards quantum cryptography and the quantum internet. Relying on computational complexity only as a security layer in the long run, can lead to catastrophic scenarios once mature quantum computers are deployed. Ever since the discovery of Shor and Grover’s algorithms, we have had the luxury of time since even to this day, we cannot implement a full version of them, therefore we are not immediately risking our current cryptography schemes.

However, in a scenario where one PQC protocol becomes breakable in a mature quantum era, it will be a matter of minutes or even seconds if a major hack is executed, leading to tons of encrypted data becoming revealed in broad daylight. This is why a constant assessment of PQC protocols needs to be done, and new protocols might see the light before a final mitigation to quantum communications takes place, the latter being subject to resolving the distance limitation.

In looking to the future, high hopes are built around the quantum internet, especially once quantum repeaters become mature and widely available. Under the condition that two communicating nodes will be entangled first, we will attain unprecedented security levels and through quantum teleportation, obtain instantaneous quantum state exchange.



The Impact of Quantum Computing on Present Cryptography (https://dx.doi.org/10.14569/IJACSA.2018.090354)

Disclaimer: Mr. Ghalbouni is an Applied Quantum Researcher at Point72, L.P.  The information, views, and opinions expressed herein are solely his own and do not necessarily represent the views of Point72.  Point72 is not responsible for, and did not verify for accuracy, any of the information contained herein.”

Leave a Reply