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

[isis]

Yawning Angel transcribed 4.3K bytes:
> On Fri, 22 Apr 2016 14:58:45 +0200 Jeff Burdges <burdges at 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 at 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,
-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160426/e59d65ca/attachment.sig>