Elligator2 inverse mapping

[SnowyCoder]

Hello, I've been developing a Proof of Concept protocol indistinguishable from random data, as described in Noise - Handshake Indistinguishability. To make this a hash-to-point, inverse elligator2 mapping is required.

I've seen that a pull-request implementing it is already open #357 but there is no discussion regarding if it should be merged or closed. Is there any plan regarding its merging, or do you plan to never merge it to avoid code complexity?

Workarounds:

• Using #389 to provide an extension crate, (curve25519-dalek-elligator?) that provides the same features but using an external crate (to avoid code complexity issues)

Additional Pointers:

• If you plan to merge #357 I would suggest adding a tweak/mask field as in the Monocypher implementation and add tests with known implementations (from Monocypher or elligator.org
• There is another independent Rust implementation (with test vectors and tweak field) that I found, but it is completely separate from curve25519-dalek, and thus it hinders compatibility with other crates: https://github.com/codahale/qdsa

If you need a hand I'm open to helping, but I'm just an interested Computer Science student with little background in the math behind cryptography.

[jrose-signal]

For further comparison, Signal has an Elligator variant used for Ristretto points rather than the whole curve. We've thought about trying to upstream it in the past but haven't really gotten around to it because it's a clunky API—either it exposes the limitation that you can't encode a full 256 bits in a RistrettoPoint (or a MontgomeryPoint, for that matter), or it has to be wrapped in something like the "lizard" method in that file, where you use a good chunk of the point-space as a hash.

(I am still not a cryptographer myself.)

[jrose-signal]

I'll bump this issue from Signal's perspective: would the crate maintainers be interested in a pair of raw Elligator mapping APIs

• one from [u8; 32] to RistrettoPoint
• one from RistrettoPoint to eight candidates of [u8; 32]

? Even given that the latter can only produce 253 bits of value.

[rozbb]

I apologize, yes we have been meaning to merge hash-to-curve functionality for a while (e.g., https://github.com/dalek-cryptography/curve25519-dalek/pull/377). The main blocker has been the ability to review the code and check that it 1) is readable, 2) does what it says, 3) has proper tests, and 4) the tests come from the right place. I hope to get around to this in the next month, if that's a reasonable timeline. Some of it would be easier if the PRs were rebased, but I don't wanna be a bother if I'm not prepared to review anything yet.

One question: can you explain the relationship between hash-to-curve and inverse mapping? If we merge hash-to-curve, would people still want access to the inverse mapping?

[jrose-signal]

(We actually use the inverse mapping, i.e. encoding information in a RistrettoPoint and decoding it again later, in our private group system. And it is specifically RistrettoPoints we care about, because those are the subgroup points we can do sigma protocol proofs on. *still not a cryptographer, but learning* So hash-to-curve may help the original poster but not us.)

[SnowyCoder]

I'm sorry, I'm quite new to the field and I was under the impression that hash-to-curve and inverse mapping were the same thing (since curve-to-hash is the forward mapping?). I don't have much experience with low-level cryptography