[curves] SIDH

[Trevor Perrin]

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.

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).

- 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).

Reasonable-sized keys (< 1KB). Performance seems a couple orders of
magnitude above a well-optimized 25519, but that's not horrible for
some cases. And perhaps there's room for more optimization?


Trevor

[Tony Arcieri]

Saw that paper as well. Previously I would've said SIDH looks great
(comparatively small key sizes, support for D-H-style key exchange as
opposed to key transport) aside from its performance, so it's great to see
progress on the performance front.

Some interesting performance comparisons of a Peikert KEX scheme (Ring-LWE
key exchange scheme, a.k.a. "NewHope") vs the SIDH improvements:

https://twitter.com/durumcrustulum/status/725805655408431104

[lvh]

Hi,


This does look like a great set of developments and I don’t mean to diminish the paper in any way, but I think we’re still an incredible amount of research away from having this be something you can realistically use in production environments (granted; you don’t have to care much until you actually care about PQ crypto). In particular, the inability to verify that your DH mixed inputs aren’t malicious is a serious problem. That’s not a complaint about SIDH specifically; another recent IACR paper suggests that this is a decent description of the overall state of PQ[1].

[1]: https://eprint.iacr.org/2016/415


lvh

Post by Trevor Perrin
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.
- 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).
- 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).
Reasonable-sized keys (< 1KB). Performance seems a couple orders of
magnitude above a well-optimized 25519, but that's not horrible for
some cases. And perhaps there's room for more optimization?
Trevor
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves

[Tony Arcieri]

Post by lvh
I think we’re still an incredible amount of research away from having this
be something you can realistically use in production environments (granted;
you don’t have to care much until you actually care about PQ crypto). In
particular, the inability to verify that your DH mixed inputs aren’t
malicious is a serious problem.

What's nice about SIDH is it's amenable to easily running side by side with
e.g. Curve25519 (and putting both shared secrets into a KDF or something
like that). You can rely on Curve25519 for security today, and maybe just
maybe SIDH will continue to provide confidentiality in a hypothetical
post-quantum world.

[Jeff Burdges]

Post by Trevor Perrin
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.

Post by Trevor Perrin
- 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.

Post by Trevor Perrin
- 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