Hash multiset to point on elliptic curve where $A = 0$

Question

I want to hash a multiset to a point on the elliptic curve $y^2 = x^3 + 3$ over a finite field of some 254-bit prime order, where $P = 3 \pmod 4$. Moreover, I want this hash to be incremental, in that the hash of the union of the multisets should be the same as the elliptic curve group sum of the hashes of each multiset.

The basic strategy for achieving this is to hash elements of a multiset using some hash function into the elliptic curve group, and then compose the multiset hash using group operations.

There is an elliptic curve multiset hash in the literature, but it relies on a deterministic Shallue-Woestijne encoding of field elements into EC group elements. In general, there are a number of deterministic encodings of field elements for elliptic curves which are "safe" assuming the hash function used for the elements of the multiset is a random oracle, but they all either apply to curves over fields with characteristic $2$ or $3$, or require the curve equation $y^2 = x^3 + ax + b$ to have $a \neq 0$ (I was looking at this paper).

I'm also can't just take a generator $g$ in the EC and produce $\operatorname{hash}(elem) \cdot g$ as the hash of {elem}, as a generalized birthday problem may be employed to find collisions between multisets (assume the inputs to the hash are public).

My question is how safe against multiset collisions is hashing {elem} by just setting $x = \operatorname{hash}(elem)$, and incrementing $x$ until $x^3 + 3$ is a square? SW encoding was used in the paper for ECMH mentioned earlier, but if timing/determinism isn't an issue, can this simpler approach be used instead? This approach is called MapToGroup in this paper.

I also found a multiset hash similar to what is described in the post here, with $b = 7$ and some $256$-bit prime field.

Answer 1

The short answer: MapToGroup can be used securely in this context. It reaches at least half the points on the curve (and much more if another bit from the hash input is used to determine the parity of y). Moreover, this encoding is "well-distributed" enough to act as an ideal hashing function, assuming the input is from a random oracle. Maitin-Shepard writes:

I believe the try-and-increment encoding is fine from a security perspective, you just lose a few extra bits of security due to the larger bound on the size of the preimage of the encoding function.

The encoding in the ECMH paper caps the preimage size of points to three, and though I don't know of a bound for MapToGroup (which involves finding the longest sequence of non-residues in the base field), it doesn't seem to be a practical security concern.

Moreover, since about half the elements in the field mentioned earlier will be quadratic residues (see Counting Squares in $\mathbb{Z}_n$ by Stangl), an implementation of MapToGroup can expect about two trials on average to find a point. The average preimage size of points is less than two.

However, Aranha pointed out that an article Indifferentiable Hashing to Barreto–Naehrig Curves exists which describes a deterministic encoding precisely to the curve being described in the question, and which is "secure" in this context.

The downside is that although the running time may be fixed, the implementation requires more computation on average than MapToGroup when using a BN curve. Moreover, there could be a side-channel leak from computing quadratic characteristics, which can vary in running time according to the input. This may be mitigated by "blinding" the computation of characteristics using inputs from a source of randomness, but is definitely an important implementation detail if the ECMH is being used on any private information.

Probably a good bet would be to go with the setup in the paper if there is support for binary curves, and otherwise consider whether any private information is being hashed.