[tor-dev] Quantum-safe Hybrid handshake for Tor

[lukep]

Yawning Angel <yawning at ...> writes:

> 
> On Sat, 2 Apr 2016 18:48:24 -0400
> Jesse V <kernelcorn at ...> wrote:
> > Again, I have very little understanding of post-quantum crypto and I'm
> > just starting to understand ECC, but after looking over
> > https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exchange and
> > skimming the SIDH paper, I'm rather impressed. SIDH doesn't seem to be
> > patented, it's reasonably fast, it uses the smallest bandwidth, and it
> > offers perfect forward secrecy. It seems to me that SIDH actually has
> > more potential for making it into Tor than any other post-quantum
> > cryptosystem.
> 
> Your definition of "reasonably fast" doesn't match mine.  The number
> for SIDH (key exchange, when the thread was going off on a tangent
> about signatures) is ~200ms.
> 
> A portable newhope (Ring-LWE) implementation[0] on my laptop can do one
> side of the exchange in ~190 usec.  Saving a few cells is not a good
> reason to use a key exchange mechanism that is 1000x slower
> (NTRUEncrypt is also fast enough to be competitive).
> 
> nb: Numbers are rough, and I don't have SIDH code to benchmark.
> newhope in particular vectorizes really well and the AVX2 code is even
> faster.
> 

Beware that the definition of newhope has changed! The authors have
published a new version of this paper and some of the numbers are different.
The parameter for the binomial distribution has changed from 12 to 16, the
probability of failure has changed from 2^-110 to 2^-64, the core hardness
of the attack has increased from 186 to 206 bits on a quantum computer, and
the timings have increased slightly too.

I'm not sure that the newhope algorithm has settled down yet. There's also a
new paper on IACR called "How (not) to instantiate ring-LWE" which has some
ideas on how to choose the error distribution - this might mean that newhope
has to change again??


-- lukep