Quantum Resistance – Algorithm Flexibility Practicalities

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. One of the uses of public key cryptography is Key Agreement (also known as Key Exchange), which typically uses the Diffie-Hellman mechanism, and its Elliptic Curve equivalents.

Replacement mechanisms have been proposed for Diffie-Hellman, notably New Hope, as an example. But how similar is it - and how easy will future algorithm developments fit into existing applications?

In a Diffie-Hellman exchange (using the tradition of Alice and Bob as the two parties involved in the exchange) Alice creates a private and public key, and delivers her public key. Bob creates a private and public key, and delivers his public key.Both Alice and Bob can now calculate a shared key using their own private key and the other person’s public key.

In New Hope (and related protocols) Alice creates a random public parameter to create her private key and delivers this parameter with her public key. Bob requires this to create a related private, public key and a shared key. He then delivers his public key and a derived value that is used by Alice (together with her private key) to create the common shared key.

It is similar to Diffie-Hellman in that both parties send one ‘public’ message to the other, and with this they can both agree on a shared value. Therefore, this is a good choice as far as messaging is concerned when replacing Diffie-Hellman in a protocol.

The important difference between the two is that the Diffie-Hellman exchange is symmetrical, in that both parties perform the same operations to arrive at the shared key. In New Hope the two parties perform different operations to arrive at the shared key and they are performed in sequence - there is inherently only one creator of the public parameter, and messages that exchange public keys contain additional data that are different in each direction. Therefore, this algorithm works where there is an Initiator and Responder type sequence (as there is in IKEv2 for example), but any truly symmetrical protocol would need additional changes to support this.

When it comes to implementing this as a set of replacement functions in an algorithm suite or protocol library it also becomes clear that the drop-in replacement as an algorithm probably does not work because of this asymmetrical behaviour. The basic interface of Diffie-Hellman is:

• Create_Private_Key(size),
• Create_Public_Key_from_Private_key(private_key)
• Create_Shared_Secret(own_private_key, peer_public_key)

But for New Hope, and others, the generalised interface should be:

• Create_Initiator_Private_Key(size),
• Create_Initiator_Public_Key_from_Private_key(private_key)
• Create_Responders_Private_key(peers_public_key)
• Create_Responders_Public_Key_from_Private_key(private_key)
• Create_Responders_Shared_Secret(own_private_key, peer_public_key)
• Create_Initiators_Shared_Secret(own_private_key, peer_public_key)

As the development of Quantum Resistant algorithms continues and cryptographic analysis and understanding progresses, the specific mechanisms and algorithms are likely to evolve. In preparing for this cryptographic algorithm suites will need to be replaceable or upgradable as a matter of course.

With this in mind, I’ll end with something for you to ponder: what range of algorithm possibilities do we need to allow for, and what interfaces do we need to make the algorithms easily replaceable in the future?