# What key exchange protocols give Forward-Secrecy resisting future progress?

I (wrongly) understood what I've been told as meaning DHE in TLS, PFS in IPSec do not provide Forward-Secrecy; and I'm told that common forward-secure key exchange protocols are restricted to establishment of an Asymmetric key, or are otherwise vulnerable when the security of some security assumption of an asymmetric cryptosystem collapses.

I ask which (preferably well-studied) key exchange protocols (if any, which I have now come to doubt) provide the following enhanced form of Forward Secrecy, for exchange of a wide ephemeral symmetric key, by mean of some asymmetric private/public key pairs; in the sense of insuring that an intercept made at a date when the assumption(s) of hardness underlying the asymmetric protocol(s) used holds, can't help recovering the ephemeral symmetric key established, even after said assumption(s) of hardness no longer holds.

Note: I now realize that collapse of assumption of hardness of all asymmetric cryptosystems is a stronger assumption than compromise of the long term private asymmetric keys, which is the standard assumption in forward-secrecy.

• DHE in TLS does provide forward secrecy if properly used (no session cache etc). – ithisa Mar 5 '14 at 20:28
• @user54609: no, it doesn't, or rather, it doesn't in the specific scenario that fgrieu is talking about: what if someone later obtains the ability to solve the asymmetric problem (which is, in this case, the DH problem). This question came up during a discussion of "what happens if the adversary gets a Quantum computer; can they go back and decrypt old transcripts of encrypted traffic" – poncho Mar 5 '14 at 20:33
• @fgrieu if your key exchange protocol relies on a hardness assumption that can be broken at some point in time, then it does not make any difference if it has provided (perfect) forward secrecy or not at the point of time when the hardness assumption was still valid, since the forward secrecy itself does not contribute anything. Having access to the transcripts of the key exchange will let you recover the respective secret if the hardness assumption is no longer valid. – DrLecter Mar 5 '14 at 20:45
• @DrLecter: perhaps with a more rigorous proof, your comment seems to be a very spot-on answer. I need to ponder it. – fgrieu Mar 5 '14 at 21:06

To make key exchange protocols (providing perfect forward-secrecy) robust against quantum computers they need to rely on assumptions that are not susceptible to quantum attacks (post-quantum crypto) like hash based, lattice based or multivariate-quadratic-equations based.

Clearly, quantum key distribution is a candidate for key exchange with all the associated problems.

pqcrypto.org provides a quite updated reference to post-quantum research. It looks like the key exchange issue and in particular perfect forward-secrecy has not really seen much research so far.

At least the paper Smooth projective hashing and password-based authenticated key exchange from lattices provides a construction of an password-based authenticated key exchange for the post-quantum world.

Subsequently, I comment on the below cited part of the question and I only speak of protocols where we use hardness assumptions which do not longer hold in the advent of a quantum computer below.

...insuring that an intercept made at a date when the assumption of hardness underlying the asymmetric protocol holds, can't help recovering the ephemeral symmetric key established even after said assumption of hardness no longer holds.

We speak here of key-exchange/key-agreement protocols which allow to parties to compute a common secret over some public channel where this common ephemeral secret may then be used to compute some common symmetric session key.

Perfect forward-secrecy in the key-exchange context typically means that both parties have some long term-key and on every session they run some key-agreement to compute a common session key, but the compromise of long-term keys does not compromise the secrecy of any past sessions.

In order to compute a session key there happens a key-agreement protocol (typically, the long term-keys will be used to sign the respective ephemeral information of the key-agreement sent by the respective party), where the ephemeral information exchanged to compute the common key do not deterministically depend on the long-term keys if perfect forward secrecy is provided. Anyways, there always simply happens a key-agreement irrespective of the perfect forward-secrecy feature or not.

So if the security of the key-agreement is based on some hardness assumptions $P_1,\ldots,P_n$, it does not make a difference if you consider key-agreement protocols that provide perfect forward-secrecy or not. If the $P_i$'s do no longer hold, e.g., if we have a fancy quantum computer, then the transcript of any key-agreement will allow you to recover the respective session key.

Perfect forward-secrecy is concerned with compromise of the long-term secrets (such as private keys for static DH keys), but not with breaking the hardness assumptions when given the transcript of a key-agreement (clearly, because the key-agreement only makes sense if the hardness assumption holds).

• There may be more than one hardness assumption in a key agreement protocol. If, say, ephemeral DH keys are exchanged encrypted by a preliminary symmetric key communicated via RSA, then the session transcript remains secure as long as DH remains hard as well as if DH is cracked but RSA remains hard, the RSA private key remains unknown to the attacker and the preliminary symmetric key was sufficiently random. – Brock Hansen Mar 5 '14 at 22:01
• @Brock Hansen: the reworded question covers just the valid point that you made. – fgrieu Mar 5 '14 at 22:04
• @BrockHansen yes you are right. actually I assumed that all involved hardness assumptions do no longer hold. I made an edit to cover this. But clearly, you may find a key-agreement protocol that combines primitives based on different assumptions in a clever way such that if not all are broken you still have security. – DrLecter Mar 5 '14 at 22:08
• @DrLecter : when we consider the forward security, is it more meaningful to consider it combined with time ? In other words, for a certain session key, I just want to keep it safe for a couple of years. Then, at the end of this time, I don't care whether the information protested by the session key is exposed or not. – T.B Mar 6 '14 at 1:30
• @DrLecter : $\:$ Should "future" be replaced with "past"? $\;\;\;\;$ – user991 Mar 6 '14 at 3:23

The paper Quantum Key Distribution in the Classical Authenticated Key Exchange Framework
gives a key exchange protocol for which the property you describe holds.

The paper On Everlasting Security in the Hybrid Bounded Storage Model