# Fast hashing into elliptic curve

Is there a fast algorithm for mapping $n$-bit numbers $s$ (for fixed $n$) into a cyclic subgroup of an elliptic curve (over a finite field) in which the Discrete Logarithm Problem is hard?

By fast, I mean it takes about as long as a point addition (and is much faster than a point scalar multiplication in the elliptic curve group, or an exponentiation operation in the finite field).

The mapping: $s \rightarrow s \cdot G$, for some generator $G$, would be too slow, and also would defeat the security of construction since the discrete logarithm with respect to $G$ would be known.

It is not necessary for the running time to be independent of the input. For instance, for elliptic curves defined by

$y^2 = x^3 + ax + b$

over the finite field $F_p$, there is the standard method of setting $x = s \bmod p$, and then computing the square root of $x^3 + ax + b$. If $p = 3 \bmod 4$, then we can compute the square root using exponentiation in the finite field. If the square root does not exist, we increment $x$ and try again. In this way we can obtain a point in the elliptic curve group, and if our cyclic subgroup has cofactor 1, then we are done. This method would be valid except that computing the square root via exponentiation takes significantly more time than a point addition.

Is there some method/choice of elliptic curve that allows a much more efficient mapping to be defined?

The speed I'm looking to beat (in order for this construction to be faster than an alternative that does not use elliptic curves) is around 100000 operations (hashes to curve points) per second on a standard single CPU core (e.g. 3.2GHz Nehalem) with a 256-bit elliptic curve. Testing with libsecp256k1, which seems to include an optimized square root implementation, I can compute only about 77000 square roots per second.

-

Over large characteristic fields, I am not aware of any "point generation method" that can be computed faster than a base field exponentiation, and I would be very surprised if such a thing existed even if you do not require constant running time. So your best bet in general is probably Icart's function (I'd pick that one over Elligator if I didn't need injectivity), which won't be fast enough for your purposes.

Over binary and ternary fields, however, it is possible to do better. For example, in the binary field case, you can use the binary Shallue–van de Woestijne encoding, which can be computed with simple base field arithmetic and half-traces, as discussed by Brier et al. in Appendix E of this paper.

Some colleagues and I have an implementation paper that should appear on the IACR ePrint archive shortly, and it computes that function to a 254-bit binary curve in well under 10,000 Haswell cycles, so your goal is easy to achieve on newer CPU architectures (I think recent AMD CPUs should be quite fast as well). Nehalem doesn't have a carry-less multiplier, however, so binary field arithmetic might be quite slow in practice on that architecture.

Incidentally, as this question falls squarely within my research interests, I'm quite curious about your concrete use case if you can say something about it.

-
$$H(u, v) = f(u) + f(v),$$
where $f$ is the Shallue-Woestijne-Ulas algorithm, and $u$ and $v$ are random $\mathbb{F}_p$ elements (perhaps obtained by $h_1(s)$ and $h_2(s)$, where $h_i$ hash bitstrings into $\mathbb{F}_p$). This construction was proven indifferentiable from a random oracle by Farashahi et al. Elligator squared adapts this approach to make the map invertible.
These more complicated point generation methods seem to be designed to ensure that the computation time is independent of the input to avoid timing related attacks, and in fact involve more computation than just computing the square root of $x^3 + ax + b$. For my purposes, the input is not secret and therefore there is no need to ensure the computation is constant time. However, even computing a single square root, in, for example, the finite field for the SECP 256k1 curve, is too expensive. –  jbms Jun 19 at 5:40