# Does NTRU provide Perfect Forward Secrecy?

Does NTRU provide Perfect Forward Secrecy if the world would use it in an HTTPS connection?

Properly speaking, forward secrecy is a property of a protocol. The protocol is forward secret if compromise of the long term keys does not allow an attacker to decipher any past communications.

(Occasionally a distinction is made between that and perfect forward secrecy, with the latter secure when the attacker also knows e.g. all other session keys.)

You can build a key exchange protocol that provides forward secrecy from any authenticated public key encryption, including NTRU:

1. Assume the parties have exchanged long term keys.
2. A generates an ephemeral key-pair and sends the public key to B, using the long term keys for authentication.
3. B generates a session key, encrypts it for A's ephemeral keys and sends it to A.
4. A deletes the ephemeral key-pair after decrypting the session key.

However, if you mean the old draft protocol I linked in a previous answer, then, no. Unless I'm missing something, that protocol just encrypts a random secret using the long term keys. That does not provide forward secrecy.

• What is "the long term channel"? $\;$ – user991 Sep 13 '14 at 12:18
• @RickyDemer "Authenticated using the long term keys". – otus Sep 13 '14 at 12:21
• Note that there are subtleties involved in that. $\;$ – user991 Sep 13 '14 at 12:30
• @RickyDemer, sure. For example, you have to prevent replay attacks. But it's doable. – otus Sep 13 '14 at 12:45

There is a very easy way to get Perfect Forward Secrecy with the Post Quantum Security of NTRU (if you believe NTRU is secure). However it requires TWO exchanges of information.

During Exchange 1 both parties generate and exchange ephemeral NTRU keys.

During Exchange 2 both parties generate random numbers and encrypt their random numbers with the other sides ephemeral pubic key and send the resulting cipher to the other side.

Each side then decrpts the message they receive which yields the other sides random number. They add or xor the random numbers together and they have produced a shared secret key with perfect forward secrecy and quantum safety

So yes, you can get PFS with NTRU but at the cost of an additional exchange. Other Post Quantum algorithms like the Ring-LWE scheme of Peikert or the Supersingular Isogeny algorithm of Defeo can achieve quantum safety and PFS in one exchange.

Yes. I'm not sure why others are saying "no". Forward secrecy is usually done by simply creating ephemeral keys for each connection. Thus, you will simply require a different NTRU keypair for each connection.

Another, related, question is "how fast is NTRU keypair generation?" Since forward secrecy requires the frequent creation of ephemeral keys, this should be an efficient operation. According to one benchmark, some parameter sets generate about 7000 keypairs / second on a modern 4-core i5 processor. That seems plenty fast enough.

• When I played around with NTRU, I found that on the system I tested it on (which was a bit old, and hence slow) did an NTRU key generation in about 1 millisecond (parameter set EE439EP1); this doesn't strike me as "pretty slow". – poncho Dec 31 '16 at 20:37
• @poncho: You're right. I looked back at the numbers on the site I refetenced, and, on second glance, they're reasonable. I've updated my answer. – Jay Sullivan Jan 1 '17 at 1:19

No, as a plain public key algorithm it cannot provide PFS on its own. It is comparable to RSA in that both can be used to achieve PFS with the help of e.g. Diffie-Hellman Key Exchange. Running the key exchange for every session/connection leads to an ephemeral session key which can be used as a key for a symmetric algorithm like AES.

• NTRUEncrypt only ensures confidentiality of the Diffie-Hellman Key Exchange.
• NTRUSign only ensures authenticity of the Diffie-Hellman Key Exchange.
• The actual payload will be encrypted with AES or similar.
• You can use RSA to achieve forward secrecy and you can use DH creating a non forward secret protocol. Forward secrecy is a matter of protocol design and key management, not about the algorithm you use. In practice we often use DH for forward secrecy since key generation is cheap. But even for algorithms with expensive key generation, you can simply generate a new short term key every couple of seconds, which results in a high degree of forward secrecy. – CodesInChaos Sep 13 '14 at 12:53
• Yes, one can generate ephemeral NTRU keys as a replacement for (E)DH/ECDH(E), but usually the latter is used in SSL. – Artjom B. Sep 13 '14 at 13:10
• I don't see the point in using NTRU for authentication and ECDHE for confidentiality. If you want post quantum security, it's far more important to use a PQ algorithm for confidentiality than for authentication, since authentication keys expire and can be revoked. – CodesInChaos Sep 13 '14 at 13:18