I suspect the two known families you "do not want to rule out" are SIDH schemes and LWE schemes with no ring structure, like Frodo. At present SIDH is too slow and LWE keys are too big, but both could improve dramatically over the next several years.

Jeff

lukep@tutanota.com transcribed 3.2K bytes:

Great to see the community making progress with post-quantum handshakes.

Hello,

Thanks! :)

But I'm wondering what's going to happen with Proposals #269 and #270. #269 seems to allow any post-quantum algorithm to be used in the hybrid with NTRUEncrypt and NewHope being specified as two options (presumably other options like SIDH or Mceliece could also be used). #270 is more specific, a hybrid of x25519 and NewHope. NewHope seems to be in the lead but do we want to rule others - so a flexible proposal like #269 might be better. #269 and #270 look as if they would not be compatible with each other so what's the process for deciding between them?

In the proposal-status document, [0] I described proposal #269 as "a generalised protocol for composing X25519 key exchanges with post-quantum ones" and proposal #270 as "a hybrid handshake based on the ntor handshake and the NewHope post-quantum key exchange. Currently needs revision to specify how this proposal depends upon prop#269."

So it's not an either-or situation for proposals #269 and #270 — they are entirely compatible and #269 is meant to provide modularity. Proposal #269 emerged because there was a lot of duplicated material in both #263 (the first NTRU handshake proposal) and #270 (the NewHope handshake proposal), and neither #263 or #270 had a security reduction. We assume that both attacks and schemes for (R-)LWE cryptosystems will improve dramatically within the next five or so years, and we would like to have the agility provided by #269 to alter the concrete instantiation should the situation change drastically, for better or for worse.

Further, just to clarify some things: proposal #269 does not "allow any post-quantum algorithm." In §2.5 of "Circuit extension handshakes for Tor: achieving forward secrecy in a quantum world" by John Schanck, William Whyte, and Zhenfei Zhang [1] it's mentioned that the post-quantum KEM portion of a hybrid, transitionally post-quantum secure handshake must provide indistinguishability under chosen-plaintext attack (IND-CPA security). There are other, additional assumptions about the pre-quantum one-way-authenticated side of the handshake, but these assumptions hold for ntor (with some very trivial modifications which do not ultimately effect the security of ntor either way).

As for the suggestion of McEliece, I've already explained why McEliece isn't suitable for use in Tor. [2]

For the repeated suggestion of SIDH, [3] I expect we'll soon see concrete details and improvements to the attacks mentioned in (and which they establish "direct validation" measures to defend against in §9 of) "Efficient algorithms for supersingular isogeny Diffie-Hellman" by Craig Costello, Patrick Longa, and Michael Naehrig. [4] E.g. if an adversary sends a supersingular curve E and linearly independent points P and Q, such that Bob calculates an isogeny ɸ: E → E' with small-degree, there could potentially be ways to utilise the kernel of the isogeny from one handshake to learn information about the shared j-invariant computed in another handshake. Side note: it's a mystery to me why the NSA and the Microsoft Research teams are jumping through hoops to validate public SIDH keys, when they could just have the requirement that the keys must be ephemeral (at the cost of some efficiency). Basically, there's a whole bunch of swinging axes, poison darts, rolling boulders, and various other death traps and doom which come into play when you take a random elliptic curve as your key, and I expect another ten years of papers which slowly work to enumerate all of them.

Also see https://eprint.iacr.org/2016/717.pdf, a comparison of attacks on NTRU. It doesn't break NTRU but it does break (some versions of) YASHE which is a FHE scheme based on NTRUEncrypt. In the conclusion it recommends transforming NTRU-like algorithms into ring-LWE like algorithms, and dismissing the former since they are known to be weaker. I still think a flexible protocol rather than all eggs in the NewHope basket is a Good Thing.

I'm not sure I follow the reasoning here. What I hear you saying is: "Some really weird schemes which use NTRU in an unsafe way are broken, ergo we should remain open to schemes other than NewHope." That still doesn't make sense to me.

Technically, that paper presents a subfield lattice attack on "overstretched" NTRU. "Overstretched" simply means that the modulus q is larger than usual, relative to the size of the secret key. To be really clear, this doesn't break normal usage of NTRU, but only breaks scheme which do really weird things with NTRU (like the fully-homomorphic encryption scheme you mentioned).

However, the Kirchner-Fouque paper does have consequences for NTRU Prime. Rather than parrot him, I'm just going to quote Chris Peikert from a discussion of this paper on another mailing list some weeks ago:

Christopher J Peikert transcribed 8.4K bytes:

Today eprint has two new papers on topics recently discussed on this list.

Kirchner and Fouque http://eprint.iacr.org/2016/717 give improved variants of subfield attacks on NTRU, and compare them to standard lattice basis-reduction attacks. (Recall that the subfield attacks work increasingly well as the parameters become more "overstretched," i.e., as the modulus q grows relative to the size of the secret key.)

One of Kirchner-Fouque's main claims (enabled by new analysis of NTRU lattices) is that standard basis-reduction attacks actually perform as well as, or even better than, the subfield attacks. A consequence is that the standard attacks apply just as well to NTRU Prime, which was designed to have no non-trivial subfields.

The authors offer many interesting conclusions:

We conclude that the shortest vector problem over module lattices seems strictly easier than the bounded distance decoding.

(NTRU is as example of the former; Ring-LWE of the latter.)

Since the practical cost of transforming a NTRU-based cryptosystem into a Ring-LWE-based cryptosystem is usually small, especially for key-exchange (e.g. [3]), we recommend to dismiss the former, in particular since it is known to be weaker (see [40, Section 4.4.4]).

(Caveat: [40, Section 4.4.4] shows that for appropriate parameters and formalizations of the problems, NTRU <= search-RLWE. The reduction is not so tight in terms of error sizes, but there are many plausible avenues for improvement.)

There is much more in the paper, and a lot to digest and verify. It should be noted that the authors have a strong track record of cryptanalysis of lattice crypto.

[0]: https://gitweb.torproject.org/torspec.git/tree/proposals/proposal-status.txt [1]: https://eprint.iacr.org/2015/287 [2]: https://lists.torproject.org/pipermail/tor-dev/2016-May/010964.html [3]: https://twitter.com/isislovecruft/status/761560658370555904 [4]: https://eprint.iacr.org/2016/413