lukep lukep@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