[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope

[Jeff Burdges]

Just a a couple questions :

Is SIDH costing 100 times the CPU such a big deal, assuming it's running
on another thread?  Can it be abused for DOS attacks for example?  Is
that CPU time needed for symmetric crypto?  etc.  If so, is it worth
restricting to your guard node? 

Is New Hope's 3+ times the bandwidth a big deal?  I suppose circuit
building does not occupy much bandwidth, so no.  


On Thu, 2016-05-12 at 12:33 +0000, Yawning Angel wrote:
> We pre-build circuits, but the telescoping extension process and
> opportunistic data both mean that circuits see "traffic"
> near-immediately in most cases (everyone but the exit will see the
> traffic of handshaking to further hops, the exit sees opportunistic
> data in some cases).

Ok.  I suppose that leaks a node's position in the circuit regardless,
but perhaps that's not a concern.  And I donno anything about
opportunistic data.  


> I don't think SIDH is really something to worry about now anyway...

If you like, I could ask Luca de Feo if he imagines it getting much
faster, but I suspect his answer would be only a smallish factor, like
another doubling or so. 

Assuming we stick to schemes with truly hybrid anonymity, then I suspect
the anonymity cost of early adoption is that later parameter tweaks leak
info about a user's tor version.  We can always ask the MS SIDH folk,
Luca, etc. what parameters could be tweaked in SIDH to get some idea. 

Jeff

p.s.  If taken outside Tor's context, I would disagree with your
statement on SIDH : 

I donno NTRU well enough to comment on even how different the underlying
reconciliation is from New Hope, but there might be an argument that
most advances big enough to actually break New Hope would break NTRU and
NTRU' too, so maybe one Ring-LWE scheme suffices.  SIDH is an entirely
different beast though. 

I've warm fuzzy feelings about the "evaluate on two points trick" used
by Luca de Feo, et al., and by this SIDH, to fix previous attempts.  It
could always go down in mathematical flames, but it makes the scheme
obnoxiously rigid, leaving jack for homomorphic properties, and could
prove remarkably robust as a trapdoor. 

By comparison, there are going to be more papers on Ring-LWE because
academic cryptographers will enjoy playing with it's homomorphic
properties.  Yet, one could imagine the link between Ring-LWE and
dihedral HSP becoming more dangerous "looking", not necessarily
producing a viable quantum attack, but maybe prompting deeper
disagreements about parameter choices. 

In other words, I'd expect our future trust in Ring-LWE and SIDH to
evolve in different ways.  And counting papers will not be informative. 

Imho, almost anyone protecting user-to-user communications should hybrid
ECDH, Ring-LWE, and SIDH all together, as users have CPU cycles to burn.
Tor is user-to-volunteer-server though, so the economics are different. 


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160516/caef1b91/attachment.sig>