Are there any post-quantum, forward-secure, hybrid, optionally authenticated key exchange protocols? Specifically, I am looking for one that can be deployed in a hybrid with X25519 + EdDSA.

  • $\begingroup$ IIRC the supersingular isogeny based stuff is a drop-in replacement for DH. $\endgroup$
    – SEJPM
    Jun 24 '18 at 18:28
  • $\begingroup$ @SEJPM They are — sort of. They are slow, for instance. $\endgroup$
    – Demi
    Jun 24 '18 at 22:01

Key exchange and authentication are typically done by separate algorithms. However, there are post-quantum key exchange algorithms that also provide forward secrecy. For example:

  • SIDH - Supersingular Isogeny Diffie-Hellman is very similar to regular DH. The main difference is that the security is related to the problem of finding the isogeny mapping between two supersingular elliptic curves with the same number of points.1

  • NewHope - This algorithm is based off of ring-learning-with-errors (R-LWE). The security relies on the approximate shortest vector problem (α-SVP). This is the idea that finding a vector shorter than α times the shortest vector is difficult, even for quantum computers.

Both of these algorithms can be combined with traditional key exchange to form a hybrid that is secure against both quantum computers and cryptanalysis of the relatively newer post-quantum algorithms. Google for example has experimented with their CECPQ1 key exchange algorithm, which combines NewHope and x25519. The Tor Project is also working on a hybrid algorithm using the same primitives, though implemented differently (using NTor rather than TLS).

Neither of these schemes provide post-quantum cryptographic signatures. The reason for this is simply that a signature does not need to provide security for nearly as long as key exchange. Key exchange must be secure against an adversary who can store the handshake and encrypted message and decrypt it at a later time when technology is sufficiently advanced. Signatures on the other hand only require that they cannot be broken right now. If your adversary is an attacker who is storing encrypted connections to break in the future, there is no need to switch to PQ signature schemes. It's only if your adversary is an active attacker with a quantum computer at this very moment that you need to worry about more secure authentication.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.