p256: Add implementation of Elligator Squared.

[codahale]

This is in big need of more scrutiny, documenting, and refactoring, but I wanted to push early and allow for input.

Elligator Squared is obviously not a standard anything, nor is the simplified Shallue-van de Woestijne-Ulas encoding, so I’m pretty open to this being a bad fit for inclusion in this crate. This is well into “science project” territory and really not something I’d responsibly recommend to anyone.

Buuut it’s neat and I’ve got a hobby project which might could use it and it seems like a decent focal point for conversations about what an EC API looks like which would allow me to ~commit these sorts of crimes~ implement this sort of functionality without having to maintain my own fork. At a minimum, that’d probably be access to FieldElement, curve constants, and point construction.

Ostensibly this could also be implemented for k256, but it’d need a similar degree of specialization.

Absolutely no hurry on this, BTW.

[tarcieri]

This looks interesting. I can hopefully review some more this weekend.

[tarcieri]

Having recently seen this issue: https://github.com/dalek-cryptography/curve25519-dalek/issues/389

...I'm curious if perhaps we should just have a cargo feature that exposes the FieldElement API. It can remain hidden from rustdoc.

There's already an expose-field feature in k256. We could add a similar one to p256, and then it seems like this could be implemented at a library level.

It could potentially even be generic over curves, similar to the SSWU implementation in the elliptic-curve crate:

https://docs.rs/elliptic-curve/0.11.12/elliptic_curve/hash2curve/trait.OsswuMap.html

We've been trying to avoid exposing FieldElement as doing so is a huge footgun, but I'm seeing enough legitimate use cases it might make sense to reconsider, feature gating it and keeping it hidden but available for the modicum of protocols which do need legitimate access.

Alternatively a generic implementation of Elligator Squared could potentially be added to elliptic-curve in a similar manner to hash2curve.

cc @str4d

[codahale]

Having recently seen this issue: dalek-cryptography/curve25519-dalek#389

...I'm curious if perhaps we should just have a cargo feature that exposes the FieldElement API. It can remain hidden from rustdoc.

I think that’s a good start, but it’s worth noting that this implementation also requires the ability to convert raw coordinates to points and back, plus access to (or duplication of) curve constants.

We've been trying to avoid exposing FieldElement as doing so is a huge footgun, but I'm seeing enough legitimate use cases it might make sense to reconsider, feature gating it and keeping it hidden but available for the modicum of protocols which do need legitimate access.

I feel you on the footgun aspect. The feature could export the hazmat types from a specific hazmat submodule?

Alternatively a generic implementation of Elligator Squared could potentially be added to elliptic-curve in a similar manner to hash2curve.

I was curious if a generic approach would work here, but there’s a few wrinkles to the way the algorithm works which makes me wonder how much structure could be shared for implementations across curves. The sampling algorithm is generic, and embedding a field element in a point is generic w.r.t. curves, but the inverse function is kind of gnarly. I guess if you extracted out the d constant (the maximum number of preimages for the inverse embedding) and fixed the potential modulo bias in the sampling algorithm it’d fly.

[kayabaNerve]

For my uses, I'd be willing to consent to a lack of semver guarantees and feature flagging, if that provides another developer's perspective. That said, I only need it in dalek for Monero's hash to curve so I don't really count as a user who can give feedback over here :p

[tarcieri]

@codahale FYI, with the primeorder::PrimeCurveParams trait you should be able to implement this out-of-tree.

Impl here: https://docs.rs/p256/0.13.2/p256/struct.NistP256.html#impl-PrimeCurveParams-for-NistP256

[codahale]

Indeed, I can! https://github.com/codahale/elligator-squared

Mashing field elements into and from bytes isn’t delightful, but it’s functional for now.

Thanks for the update!