Yawning Angel transcribed 4.3K bytes:
On Fri, 22 Apr 2016 14:58:45 +0200 Jeff Burdges burdges@gnunet.org wrote:
On Fri, 2016-04-22 at 11:10 +0000, Yawning Angel wrote:
On Fri, 22 Apr 2016 11:41:30 +0200 Jeff Burdges burdges@gnunet.org wrote:
There is some chance SIDH might wind up being preferable for key exchanges with long term key material.
Maybe. Some people have hinted at an improved version of SPHINCS256 being in the works as well.
Ain't clear how that'd work.
There are homomorphic MAC like constructions, like accumulators, which might let you reuse your Merkle tree. I though these usually needed assumptions that Shor's algorithm nukes, like one is f(x,y) = x^7 + 3 y^7 mod N with N=pq secret, for example.
I suppose Nyberg's accumulator scheme is post-quantum, but I though it's huge too. I'm not completely sure if just an accumulator helps anyways.
I didn't get details unfortunately.
It's not my paper, so I probably shouldn't give too much away, but…
Essentially, there are two different optimisations being discussed: one which allows faster signature times via batching, which can optionally also be used to decrease the size of the signatures (although assuming you're sending several signatures in succession to the same party). That optimisation is maybe useful for something like PQ Bitcoin; probably not so much for Tor.
The second optimisation is applying the ideas from XMSS-T [0] to SPHINCS. The authors say that the size of the public keys will be 64 bytes. My napkin calculation says, given that our current network bandwidth capacity is ~175 Gbit/s, and ~75 Gbit/s is utilised with 1 Gbit/s used for dirfetches, adding 64 bytes to each microdesc increases the dirfetch bandwidth overhead by about 33%.
Hence, the latter may be a feasible method for extending our post-quantum security to the authentication, however this _doesn't_ mean we should stall on making the KEX post-quantum forward secure. As Yawning pointed earlier in this thread, "there is a database in Utah storing all the handshakes and we should've been working against that ten years ago", and also:
My current assumption is that by the time we need to seriously start thinking about auth and need to design/deploy a new construct around that as part of our threat model, both signatures and key exchange algorithms will be more fleshed out, but in the immediate future, going by what's available and practical pushes me towards NTRUEncrypt/Ring-LWE.
On that note, I've been working on a Tor proposal for a Ring-LWE + X25519 hybrid KEX. It'll be ready for design review soon.
[0]: https://joostrijneveld.nl/papers/multitarget_xmss/
Best Regards,