Hello list,

We had a very constructive discussion on this proposal last Thursday.
I have updated the feature request based on the feedback from the discussion.
We also like to thank Roger for grammar fixes on the proposal.

Major tech updates are:
1. Use SHA3 and SHAKE instead of HMAC_SHA3

2. In previous proposal, when server sends back the message, it sends a ciphertext
C = ENCRYPT( P | B, QSPK), and its one-time ECC public key Y = e^y;
where P is the secret that server chose, B is servers long term public key.

In this new version, we also include servers short term public key in the plaintext, i.e.,
C = ENCRYPT( P | B | Y, QSPK)
and Y is no longer send to the client separately. The client will need to decrypt
C first and retrieve Y from the message. Y is not revealed to any one other than the
client.

This is proposed by Nick. It was also suggested to us by Aniket Kate. We thank Nick
and Aniket for the suggestion. This modification will save 32 bytes of traffic as Y is no
longer transmitted. Also since Y is now encrypted it will be a little harder for the attacker
to attack the 25519 keys.

3. Choosing algorithms and parameters for the protocol.
We have identified NTRUEncrypt and R-LWE as two candidates for this protocol.
We have agreed to use NTRUEncrypt for now, in the meantime, keep the option open
for "newesthope" version of R-LWE type key exchange when it becomes available. Also,
for NTRUEncrypt we will be using parameters sets with SHA3, to align with Tor specs.
I have modified the feature request to reflect this change.

Also in the discussion we were talking about the possibility of using non-product form
polynomial version of NTRUEncrypt, as this version will become patent free by Aug 2017,
while the patent for product form will last for another 4 years. The main concern is that
Debian will not allow patented software in the package.  However, through our discussion,
it turns out that we may be able to include this proposal in the next one of two release of
Tor. From this point of view, both patent (basic NTRU patent, till 2017 and product form
patent, till 2021) are going to be an issue if Debian does not agree with SI's patent statement.
So does it make sense to keep the product form polynomials as they enables roughly 3
times faster operations on both client side and server side?


Thanks for your time, and please let us know if you have any further comments/suggestions.

Best regards,
Zhenfei