On 02/03/2016 12:12 PM, Jeff Burdges wrote:
I donno that you'll ever beat that 1kb key size with a post-quantum system. There is a lattice based signature scheme and an isogeny based scheme that'll both beat SPHINCS on signature sizes, but I think not so much on key size.
I just wanted to resurrect this old thread to point out that supersingular isogeny key exchange (SIDH) is the isogeny scheme that you're referring to. Using a clever compression algorithm, SIDH only needs to exchange 3072 bits (384 bytes) at a 128-bit quantum security level. This beats SPHINCS by a mile and unlike NTRUEncrypt, fits nicely into Tor's current cell size. I don't know about key sizes, though. If I recall correctly, SIDH's paper also references the "A quantum-safe circuit-extension handshake for Tor" paper that lead to this proposal.
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.