Hi Peter,

Thanks for such a nice overview of current discussions. Just want to give a quick update on the NTRU.

• NTRU is around for the longest time and has, even with high-security parameters, fairly short messages. However, existing software implementations (at least the ones in SUPERCOP) are highly vulnerable to timing attacks. Key generation (with protection to against timing attacks) is, as far as I can tell, fairly expensive.

We are working on a constant-time implementation of NTRU. We expect to release the source code this summer. However, as far as I know, timing attacks are much more powerful against encryption algorithm (that uses long-lived key for multiple times), rather than KEMs (use ephemeral keys). Our proposal treats NTRU as a KEM so I think the timing attack is not so useful.

What I'm missing in the discussion are benchmarks of NTRU and NTRUprime

(in

the context of key exchange).

Please see the attached for some benchmark results. We are working on the camera-ready version of the paper. The final version should be out soon. Also note that we are using an IND-CCA-2 secure version of NTRU. The performance can be further improved by switching to the IND-CPA secure version. IND-CPA is enough to provide channel security, provide that the ciphertext is accepted for only once for a given key. (This may open doors to some DoS attack.) As far as I can tell, the NewHope and NTRU-prime all uses CPA secure encryption algorithms.

Would it help the discussion at this point to fix NTRU parameters, produce an optimized implementation of NTRU (not production-quality code for Tor,

but

something to obtain benchmarks) and compare performance of NewHope, NTRU,

and

NTRUprime in an ephemeral key exchange? This would be a nice project for a Ph.D. student.

It would be very interesting indeed. We need to fix the parameter sets for NTRU. Currently we have 1. ntru-443 with product form, providing 128 pre-quantum/post-quantum security 2. ntru-743 with product form, providing 256 pre-quantum and >128 post-quantum security 3. ntru-887 with non-product form, providing 256 pre-quantum security And all of those parameter sets uses SHA256 rather than SHA-3 as suggested by the community.

It would be nice to have a final decision on a. shall we use non-production form b. shall we remove the IND-CCA-2 feature c. shall we use ntru-743/887 to build a sufficiently large margin just like NTRUprime

Cheers, Zhenfei

On Tue, May 24, 2016 at 6:32 PM, Peter Schwabe peter@cryptojedi.org wrote:

bancfc@openmailbox.org wrote:

Hi all,

...

Some great developments in lattice-based crypto. DJB just released a

paper

...

on NTRU Prime:

Let me just also throw in my 2 cents:

As far as I can tell, there are now 5 approaches to post-quantum key exchange that are discussed (or at least have surfaced) in this thread:

• NTRU
• NewHope
• NTRUprime
• McEliece
• SIDH

In some of the posts I got the impression that there are considerations for some sort of "algorithm agility" in the key exchange. This can mean two things:

• runtime algorithm agility, such that a client can choose what algorithm to use according to some strategy; or
• upgrading algorithm agility, which means that for each version number of a client, it is very clear which algorithm it will use, but the key exchange supports (easy) upgrading to better algorithms with increasing version numbers.

In my opinion, the second approach is extremely important, in particular because at the moment we certainly want some sort of PQ key exchange, but are quite uncertain about what approach will prove best in the long run. I'm not really sure whether anybody really suggested the first approach, but just in case, I think it's a terrible idea. If the decision of what algorithms to use is left to users, they will certainly end up making worse choices than experts; if it's left to randomness, users inevitably get the worst out of the set from time to time. I simply cannot think of any strategy that lets the user win here.

Now, out of the 5 proposals, my impression is that McEliece with binary Goppa codes has been killed as an idea for key exchange in Tor and that whenever somebody mentions it again, Isis will just shout "KEYSIZE" to make sure that it remains dead.

I can see good reasons for each of the first three (lattice-based) proposals:

• NTRU is around for the longest time and has, even with high-security parameters, fairly short messages. However, existing software implementations (at least the ones in SUPERCOP) are highly vulnerable to timing attacks. Key generation (with protection to against timing attacks) is, as far as I can tell, fairly expensive.

• NewHope is explicitely designed for ephemeral key exchange (not public-key encryption), i.e, for the operation that is required. It offers best performance and, as Isis pointed out, the paramters we propose have the largest security margin against all known attacks. Disadvantage (price to pay for the security margin): somewhat longer messages.

• NTRUprime is much less conservative than NewHope in its parameter choices against known attacks but offers "defenses" against attacks that may or may not work against NewHope and NTRU. The advertisement of those defenses is a pretty good job of the marketing department: the wording suggests that NTRUprime is, at the same bit-security level, at least as secure as NTRU or NewHope, but then has those defenses as additional safeguards. This is not quite true: NTRUprime operates in a different mathematical structure, which may in the long run prove more secure, it may also prove less secure and it could turn out that the "defenses" against hypothetical attacks turn out to be weaknesses against other attacks. Having said that, I really like the ideas of the NTRUprime paper and much more often than not have Dan and Tanja been right with their intuition for cryptographic design.

What I'm missing in the discussion are benchmarks of NTRU and NTRUprime (in the context of key exchange). For NTRUprime there is not even a proposal for ephemeral key exchange as needed in Tor; however, I assume that it's not too hard to replace NTRU operations (from the NTRU proposal) by NTRUprime operations. Also (please correct me if I'm wrong), for NTRU it's not clear what parameters to use and there is no optimized and timing-attack protected implementation. Would it help the discussion at this point to fix NTRU parameters, produce an optimized implementation of NTRU (not production-quality code for Tor, but something to obtain benchmarks) and compare performance of NewHope, NTRU, and NTRUprime in an ephemeral key exchange? This would be a nice project for a Ph.D. student.

Now, then there is SIDH: I really like SIDH, not so much for the shorter public keys (that's nice, but it's not like a difference of an order of magnitude), but because of two other reasons: 1.) It is a completely different approach and even if all non-standard lattice crypto falls, SIDH may survive. 2.) It's offering the same functionality as (EC)DH right now; both parties can compute their public keys without having received the public key of the other party. This is a great feature for protocol design and for migrating existing DH-based protocols to a post-quantum setting. However, I don't think that SIDH is ready for use at the moment. The reason is not only that it's about 300x slower than ECC, the reason is that security is really not understood at all. While probably everybody in the crypto community expects some progress in lattice attacks over the next few decades, I don't think that anybody seriously expects a polynomial-time algorithm that breaks, for example, Ring-LWE with suitably chosen paramters. A polynomial-time algorithm to break SIDH would clearly be a major breakthrough with an immediate-accept at any of the big crypto venues, but I would not want to really bet anything important (like my life in freedom) against this happening. I talked to Michael Naehrig (co-author of the Crypto paper this year implementing SIDH) two days ago and mentioned that SIDH popped up in this discussion as a possible approach for Tor. His reaction was roughly along the lines of "We say in our paper that you shouldn't use this, and very certainly not in Tor".

So, I hope that SIDH will survive in the long run, after serious cryptanalytic effort trying to break it; I hope that it will become faster by, say, a factor of 100 (that's not totally inconceivable, pairings took minutes to compute at the beginning, now we're below a millisecond) and if this happens then Tor should migrate to SIDH. Not now.

As I said, just my 2 cents.

Cheers,

Peter

---

tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev