[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope

[Peter Schwabe]

lukep <lukep at tutanota.com> wrote:

Hi lukep, hi all,

> You may want to get more drinks in - there's a new eprint on IACR archive
> that's claiming a faster generation of 'a' using the 5q / 16 bit trick:
> https://eprint.iacr.org/2016/467.pdf

I know, I have been in contact with the authors and I think that we will
want to include some of their ideas in the final version of the NewHope
paper (which has been accepted at USENIX! :-)). I also told them that
they do not have to do the 4 conditional subtractions of q; apparently
that comment hasn't made it into the eprint version.

> The other change they make is to replace SHAKE by SHA-256 and AES-256 on the
> grounds that finding a backdoored 'a' would be implausible, although they no
> longer have the security reduction. Also they're not considering timing attacks.
> 
> They get a speed-up of about 1.5x on AVX2. Personally I don't really care
> about not having the security reduction for 'a' (there's still the proof in
> the newhope paper for the rest of the key exchange). 

An early version of our software was using something very similar and
similarly fast (ChaCha20) until we agreed that the right thing to use is
a XOF and pay for this with some performance penalty. As far as I know
there is only one properly specified and analyzed XOF out there at the
moment and that's SHAKE. We also considered a tree mode of SHAKE (which
is faster), but decided against it to prioritize simplicity over some
performance gain.

I would be very happy to see more research into design and analysis of
faster XOFs, and then I would totally support using them in NewHope, but
my current impression is that there's more work to be done.

> The bandwidth can be halved for n=512 vice n=1024 - this is the JarJar of
> NewHope - maybe dubious by itself but could be strong enough in hybrid with
> X25519 given that bandwidth is at a premium in Tor?

There is a reason that it's called JarJar.

Best regards,

Peter
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 811 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160520/1e6428ab/attachment.sig>