Post Quantum Cryptography

Quantum computers will disrupt existing systems

The functioning of the internet and other communication systems relies on secure and efficient cryptographic algorithms. These algorithms allow internet entities to communicate with secrecy, and also to verify the identities of those parties with whom they are communicating. Symmetric-key algorithms such as the Advanced Encryption Standard (AES) provide secrecy by use of a shared key between the communicating parties. Public-key cryptography provides key-agreement algorithms (e.g. Diffie-Hellman) for deriving the shared key, and also verification algorithms (e.g. RSA algorithm) for authenticating the identity of each entity.

The security of RSA and Diffie-Hellman are based on computational problems such as factoring large numbers and finding discrete logs. These are exponentially difficult to solve using conventional computers and classical algorithms. Even considering Moore’s Law, it was thought that unless very significant progress was made in factoring algorithms, RSA, Diffie-Hellman and other such algorithms would be secure for the long-term future.

Shor’s algorithm, invented in 1994, changed this. It is an algorithm for factoring large numbers, but a critical part of that algorithm could only be run on quantum computers. If a sufficiently large quantum computer could be built in practice to run Shor’s algorithm, then large numbers could be factored very efficiently, and the security of RSA and related algorithms such as Diffie-Hellman would fall apart. The impact on the internet would be enormous. It is estimated that if certain problems could be solved, a quantum machine with twenty million quantum bits (qubits) could be built to break 2048-bit RSA [1]. Current experimental quantum computers contain around fifty qubits.

Due to uncertainties concerning the scaling of quantum computers, it is unknown as to when such a practical quantum computer could be built, or even if it is feasible. One milestone for measuring the progress of development is the notion of quantum supremacy, whereby a quantum computer is able in practice to solve tasks beyond the reach of conventional computers. Amidst the funding of billions of dollars for research, industry is now predicting quantum supremacy can be achieved in the next few years [2]. While this does not mean that our public key algorithms are in imminent danger of being broken, it means that industry needs to start preparation for transition to quantum-safe algorithms, immune to Shor’s and other quantum algorithms.

We note that even against the power of a quantum computer, symmetric-key algorithms remain safe. It’s estimated that the quantum computing may halve the effective length of symmetric keys, which means that algorithms like AES-256 will remain secure, without need for replacement.

Introducing quantum-safe algorithms to provide enhanced security

Huawei plans to introduce quantum-safe algorithms into its products at an early date, to ensure the long-term security of its products. Most important is to introduce secure quantum-safe algorithms for key-agreement. This is because key-agreement messages can be stored now, and retrospectively attacked when a quantum computer becomes a reality. This means that sessions conducted before the realization of a quantum computer might not have forward security if legacy key-agreement algorithms continue to be used.

Huawei is following various standardization activities for post-quantum algorithms with interest. One well-known standardization exercise is in the process of analyzing many dozens of post-quantum algorithms with the help of the global academic community. This standardization exercise is expected to finish by 2024, although the nature and number of algorithms to reach the final portfolio is difficult to predict.

We plan to introduce some of these algorithms into our products in advance of the 2024 deadline in order to prevent the key-agreement hoarding problem. This involves considering the properties of the candidate algorithms, which can be divided into six categories. Each category has special implications for both the implementation characteristics and maturity of the algorithm’s security. The categories are:

• Hash-based algorithms. This class of algorithms can only be used for signatures. One of the limitations is that each instantiation may only be used for generating a limited number of signatures. Research continues in how to optimize its usage. However, the security of hash-based algorithms is well understood.
• Multivariate algorithms, such as the oil-and-vinegar scheme. This class of algorithms can be only used for signatures. While this class of algorithms produce signatures of very small size, the security of many multivariate algorithms is not well understood.
• Lattice-based algorithms, such as the NTRU signature scheme, invented in 1996. Lattices can be used in both signatures and key exchange algorithms. The characteristics of vanilla lattices are not optimal, but introducing mathematical structure such as lattices based on rings can reduce key sizes, with a possible impact on security.
• Super-singular isogeny-based algorithms provides a key-exchange algorithm based on walks on elliptic curves. This is a category of post-quantum algorithm characterized by relatively slow speed and compact key sizes.
• Code-based algorithms can be conservative with respect to security, as typified by the McEliece encryption algorithm. With well-chosen parameters, the security of this algorithm has not been degraded since its invention in 1978. It suffers from inconvenient parameters such as a very large public key but is suitable for key exchanges for applications where the long-term keys rarely change. Other types of code-based algorithms, such as those based on low-density parity-check codes, can significantly reduce the size of the public key while providing high security.
• Miscellaneous algorithms such as the Rainbow signature algorithm, which is based on zero-knowledge proofs and lightweight block cipher components.

Transitioning from old systems to new.

A company such as Huawei has several options in how to deal with the problem of forward security of key exchange messages. It can immediately implement a promising post-quantum algorithm to replace Diffie- Hellman, but this introduces risks that the algorithm might be broken over the forthcoming years as the academic community scrutinizes the new range of quantum-safe algorithms. Alternatively, the company might choose to delay any action for several years, until the conclusion of standardization activity, in which case the problem of forward-security of key-exchange messages remains in the interim.

A third option is to implement a hybrid scheme that implements both Diffie-Hellman and a candidate quantum-safe key-exchange mechanism. This mitigates the risk significantly, since if realistic quantum computer is ultimately implemented, it cannot directly break the quantum-safe mechanism. On the other hand, if a problem with the quantum-safe mechanism is found in the interim, then the Diffie-Hellman algorithm affords some medium-term protection.

Ideally, the quantum-safe or hybrid key-exchange algorithm should drop directly into well-known protocols such as TLS or IPsec. In reality, quantum-safe algorithms are complex compared to legacy algorithms both in terms of difficulty of implementation, and in parameter characteristics (for example, large keys, or consumption of bandwidth). Careful study of the protocols and optimization of the algorithms will reduce the performance impact of using a hybrid-key exchange scheme.