Cybersecurity for the quantum era: OIST professor among team behind new international standard for post-quantum cryptography

Cryptography, the science of securing information, is one of the fields most affected by emerging quantum technologies. The main cryptographic mechanisms used to protect our digital infrastructure will become ineffective against adversaries in possession of large-scale quantum computers. This emerging threat has accelerated efforts to develop and deploy new “post-quantum” cryptographic algorithms.

Now, Classic McEliece, a post-quantum cryptographic algorithm developed by an international team that includes Professor Carlos Cid, from the Applied Cryptography Unit at the Okinawa Institute of Science and Technology (OIST), has been selected as a new international standard by the International Organization for Standardization (ISO) for high-security cryptography to keep user data safe against future quantum-computing threats.

In the 1990s, the two most prominent public-key cryptographic algorithms, Diffie–Hellman (DH) and RSA, were shown to be breakable by future quantum computers due to the development of a powerful quantum algorithm by Peter Shor. These types of cryptographic algorithms rely on the assumption that finding prime factors of extremely large numbers and computing discrete logarithms are computationally infeasible. However, Shor’s algorithm showed how these tasks can be solved exponentially faster than classical algorithms.

“The expected development of large-scale, fault-tolerant quantum computers capable of running Shor’s algorithm will undermine the security of today’s most widely used public-key cryptographic mechanisms,” says Prof. Cid. 

On the other hand, McEliece's system, based on an encryption system published by Robert J. McEliece in 1978 and one of the earliest public-key encryption algorithms ever proposed, relies on different mathematical principles, using error-correcting codes rather than exponentiation (repeated multiplication).

Prof. Cid continues, “Classic McEliece is a code-based cryptographic scheme that relies on different mathematical assumptions for its security. The original McEliece cryptosystem, on which it is based, has been thoroughly studied and analysed for almost five decades, and its classical and quantum security is very well understood. As a result, Classic McEliece is widely regarded as one of the most conservative post-quantum cryptographic designs.”    

Compared to other more recently developed post-quantum cryptosystems, Classic McEliece offers not just a longer and stronger track record of security but also lower total costs. Classic McEliece allows the costs of large public keys to be spread across many small ciphertexts, while other options have larger ciphertexts.

"The fact that the ciphertexts are so small turns out to be connected to one of the security features that McEliece already figured out in 1978," says Daniel J. Bernstein, Professor at University of Illinois Chicago, and also a member of the Classic McEliece team. "Pursuing security isn't always a performance problem."

Although quantum computers capable of breaking today’s cryptography — known as Cryptographically Relevant Quantum Computers (CRQCs) — may still be several years away, a worldwide effort to upgrade the current cryptographic infrastructure is ongoing. Japan, alongside other countries, has introduced targets to migrate to “post-quantum” cryptographic algorithms by 2035.  Prof. Cid said, “Classic McEliece has already been integrated into several real-world applications. We expect that ISO standardisation will accelerate its adoption by providing a formal endorsement of Classic McEliece as a secure and trusted cryptographic mechanism for protecting communications in the quantum era.”

ISO's new standard is an amendment to an existing encryption standard called ISO/IEC 18033-2, which dates back to 2006. The original standard did not include cryptographic algorithms that could provide protection against quantum computers.