Hacker News Reader

Comment by Y_Y | Hacker News Reader

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.

View on HN

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

Reply on news.ycombinator.com