Thales Blog

Quantum Resistance – An Addition, Not A Replacement

February 27, 2017

In order to protect our data in the medium term the algorithms and protocols used must be resistant to developments in Quantum Computing that could result in many conventional public key algorithms becoming breakable – that is, reversible from the public key.

As new algorithms and mechanisms are proposed how should they be safely included in systems without ultimately undermining security because of their immaturity?

Several areas of mathematics are being considered as possibly resistant to quantum computer attacks. These fundamental mathematical ideas are then used to create algorithms and protocols for performing particular functions, such as key agreement or signing.

The development of new cryptography relieves heavily upon review, analysis and attempts to break the algorithms or underlying mathematics. This takes time. From the time a mathematical idea or algorithm is proposed it may be several years before sufficient analysis has been performed to have confidence that the algorithm or mechanism is suitable.

Where a mechanism is devised that performs a similar task to an existing mechanism, the strategy may be to replace the classical algorithm with the new quantum resistant algorithm. Because of the ‘new-ness’ of the quantum resistant mechanism there is a real risk that some defects are found and improvements made in the coming years. The defects may not necessarily be related to quantum computing, but can be exploited now. This would mean moving from the current mechanism to the new quantum resistant algorithm would make the security position worse.

To counteract this problem of immaturity while making best efforts to be quantum resistant, the deployment of, relatively, immature quantum resistance algorithms should be done while continuing to use the best mechanisms currently known. This means, for example, in the case of key exchange, a classical Diffie-Hellman algorithm should be used in conjunction with the new quantum resistant exchange and the shared secrets that each produce combined to create the resulting shared key.

Similarly, quantum resistant signature algorithms can be used in conjunction with classical signature algorithms. Therefore an object being signed should have two signatures related to the object, one from a classical signing mechanism and the other from the new quantum resistant algorithm.

In protocols (for example IKEv2) and data formats (for example certificates) the fact that a public key, or a signature is for multiple algorithms can be hidden within the data fields. Therefore the new algorithm identifiers should not refer to a single new mechanism (for example, the quantum resistant algorithm X), but to the combination (for example, X25519 and the quantum resistant algorithm X).

Because of the many classical algorithms currently used this could lead to a proliferation of combinations of algorithms. Therefore, careful consideration and effort should be made to minimize the number of classical algorithms proposed in combination with new quantum resistant algorithms –preferably there would be only be one for each mechanism.

To end, I’ll leave you with this question: Do you believe we can get to a positon wherein all new quantum resistant key agreement algorithms are used in combination with X25519 algorithm, and all quantum resistant signing algorithms are used in combination with Ed25519?