[curves] SIDH

[Jeff Burdges]

On Fri, 2016-04-29 at 11:20 -0700, Trevor Perrin wrote:
> This looks interesting:
> 
> https://eprint.iacr.org/2016/413.pdf
> https://research.microsoft.com/en-us/projects/sidh/
> 
> 
> As I understand it, it's an elliptic curve approach to post-quantum security.

One should mention that an SIDH key can only pair with another SIDH key
whose kernel lives in the other torsion.  

It's no problem if you only have users talking with servers.  There are
however situations where you must tweak protocols, or even advertise two
keys.  Your might for example define the fingerprint to be a two leaf
Merkle tree H(H(MyPub2) || H(MyPub3)). 

In a 2-step ratchet, each party would just stick with one prime, which
sounds better than say being stuck with the same polynomial a if your
ratchet using Ring-LWE. 

Akaik, all the existing signature algorithms built from SIDH need 3 or 4
types of torsion, which blows up the curve size.

> Some advertised benefits:
> 
>  - Gives a DH function and apparently allows reuse of DH keypairs
> (e.g. ephemeral-static DH, static-static DH), so allows protocols
> similar to current ECDH (though the public-key validation to make this
> safe roughly doubles the cost of the DH).

Only computational cost though, not bandwidth. 

It's worth reading section 9 even if you skip other parts.  It gives
insight into the sort of validation weaknesses that arose previously. 

>  - There's a hybrid mode where a more traditional ECDH is integrated
> (though I'm not sure whether this is significantly better than just
> performing a 25519 or something alongside the SIDH, and hashing the
> results).

It's described in section 8 as only being about code size.  They propose
an ordinary curve secure for ECDH but defined over the same field as
their SIDH curves, thus dropping one field implementation.  It's a huge
curve that provides 384 bits of security though.  They never say if this
code size savings should improve cache hits significantly or if they're
thinking about embedded devices.  

Jeff



-------------- 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://moderncrypto.org/mail-archive/curves/attachments/20160430/5ac4abf5/attachment.sig>