Yawning Angel <yawning@...> writes:
On Sat, 2 Apr 2016 18:48:24 -0400 Jesse V <kernelcorn@...> 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