Being indistinguishable from uniform random bytes means you can undetectably embed it within anything else that's supposed to be uniformly random.

Also, an expert human can't distinguish a single regular EC point from uniform random bytes, depending on the format. You'd still need to look at the statistics over a number of points (i.e. by writing a distinguisher).

If a single point matches the curve equation of a well-known curve then that’s pretty compelling evidence.

The point is that any random byte string can be decoded by Elligator to become a point matching the curve equation. This means that such a check is virtually useless and tells you nothing about whether there is a hidden key exchange happening or not.

not for compressed point representations (hence "depending on format")

So just X25519 then?

No, most curves support a compressed (x coord, parity/sign bit) representation. It's what you'd probably be using if Elligator didn't exist, so makes sense as the point of comparison.

https://datatracker.ietf.org/doc/draft-mattsson-tls-compact-...

Wouldn't it be a good candidate for steganography then? If I hide this string in my paragraph of innocuous text then I have some plausible deniability if Eve successfully guesses what aim doing.

The trouble with this is that whatever steganographic feature you're embedding it into would (likely) not be uniformly random by default. So although nobody could prove you were transmitting an EC point, they could reasonably assume you were transmitting some form of encrypted data, given enough samples.

I think steganography is the right idea in general, but it needs to be more clever than the classic text/image-based techniques.

Elligator is appropriate for use as a component in a steganography system, but in most cases the problem it solves isn't the hardest part of the system.

It's also useful in cases where you need to hash to a curve in a way that provably (in the ROM) doesn't have problematic structure. This comes up fairly often: OPRF, Boneh-Boyen short sigs, password-auth key exchanges like SPEKE and PAK, etc. It also was useful in SIKE, before that was broken.

Elligator is only tangentially relevant to the hashing problem. If "doesn't have a problematic structure" is understood in a weak sense, then this was already solved by Shallue and van de Woestijne almost a decade prior to the Elligator paper. And if it is understood in the stronger sense of indifferentiability, then Elligator by itself doesn't actually fit the bill, and you need something like the Brier et al. approach or SwiftEC.

The steganography stuff is the only actually novel contribution of the Elligator paper.

Perhaps it's a bit more than tangentially relevant? Yes, SW[U] predates it for hashing, and Brier et al builds indifferentiability on that. But Elligator2 is simpler and faster, and also works with Brier et al, though it only supports even-order curves. As a result, Elligator2 is specified in RFC 9380 along with SW[U], and has fairly broad implementation.

Also yes, SwiftEC is faster than Elligator2 + Brier et al, at least if Jacobi symbols are fast with your parameters/hardware. But you can do something very similar to SwiftEC with Elligator2. This is simpler than SwiftEC and probably still faster, and was published earlier (https://eprint.iacr.org/2020/1513).

You can make a random (high e) signal look non-random (low e) by adding strings of zeros and ones to it. Or you can embed it into known formats.

I was always fascinated by stuff like LSB stenography where you hide a message (or another image) in the least significant bits of an image. Not visible to the human eye, mathematically should look like thermal noise in the image at most.

Image sensor noise is not a uniform distribution (I believe it's typically modeled as a Gaussian distribution, but even that's an approximation).

Thus, it is mathematically/statistically distinguishable.

The LSB of samples from a gaussian distribution is uniformly distributed: 50/50 chance of 0/1

(Assuming you have enough bits per sample which image sensors provide IRL)

Only in theory. In practice, they're correlated with the other bits and adjacent pixels.

How correlated? I spent 2 minutes trying and failing to get chatGPT to generate code that downloads an image dataset and runs diehard on the LSBs. I'd expect the LSBs to pass the randomness test.