Right way to hash elliptic curve points into finite field

Question

I would like to know how I can implement several hash functions :

$H_1:\{0,1\}^* \rightarrow P $ with $P \in E(\mathbb{F}_q)$

and

$H_2:P \rightarrow \mathbb{Z_q}^*$

And others where the input data changes (for example $h:(P,\{0,1\}^* )\rightarrow \mathbb{Z_q}^*$)
With an elliptic curve of the form $y² = x³+ax+b$ over $\mathbb{F}_q $ where $q$ is a prime number, what is the correct way to construct those functions in my code ?

I planned to use some NIST or SECG recommended elliptic curves so I didn't generate all the elliptic curve points, thus for $H_1$ I can't just simply hash with an existing function and map the result to a point in a list (So I can't use this response ?) .
For the hash functions which take a point should I just hash the coordinates with a function like SHA-2 or another and apply a modulo on the output ?

I don't really know if my ideas are the right ways to go, I just want to implement these functions properly from a cryptographic standpoint, something that works without need to be perfectly optimized.

Thank you in advance

Answer 1

For $H_1$ it depends on a bit on what characteristics you require of your hash function. There is a thorough analysis from Brier et. al (https://eprint.iacr.org/2009/340.pdf). Here's the basics:

Method 1: One way to hash from $\{0,1\}^*$ to $E(F_p)$ is to first hash to $Z_p$ and then multiply by the generator. Universal Hash Functions as first described by Carter and Wegman (https://en.wikipedia.org/wiki/Universal_hashing) provide a simple mechanism to obtain an indistinguishable distribution. Given $q \geqslant p$ and random values $a,b \in q$ this can be constructed as:

$$H_{CW_1}(x) = ((a_1x + b_1) \text{ mod } q) \text{ mod } p$$

$$H_u(x) = H_{CW_1}(x)*G$$

$H_u$ hashes from ${\{0,1\}}^*$ to $E(F_p)$. Because $H_{CW}$ is uniform (i.e. the probability of a collision is $1/p$) in $Z_p$ it follows that $H_u$ is uniform in $E(F_p)$. This could be sufficient for some uses, however it should be noted that $H_{CW}$ is the discrete logarithm of $H_u$. If your use of a hash function depends on security of the ECDLP for the result then this is not sufficient.

Method 2: The second method, assuming a short Weierstrass represenation with $p \equiv 2 \text{ mod } 3$ is to use Icart's function to map directly to $x,y$ coordinates which are parametrically constrained to be on the curve $E(F_p)$. Icart's function $f(u) = (x,y) : u \in F_p$ is defined by:

$$v = (3a -u^4)/6u$$ $$x = (v^2 - b - u^6/27)^{1/3} + {u^2}/3$$ $$y = ux + v$$

Extending this to map $\{0,1\}^* \rightarrow E(F_p)$ is as simple as:

$$H_{CW_2}(x) = ((a_2x + b_2) \text{ mod } q) \text{ mod } p$$

$$H_I(x) = f(H_{CW_2}(x))$$

$H_I$ hashes from ${\{0,1\}}^*$ to $E(F_p)$. The derivation $(x,y)$ using Icart's function provides no gain on finding the discrete logarithm of $f(u)$, so it could be sufficient for some applications, however $f$ only maps to a distinct subset (about 5/8) of the points of $E(F_p)$, so it is not sufficient for appilcations which require a uniform/indistinguishable mapping.

(Note: there are alternate implementations to Icart's function explained in Brier et. al. which can be used for other curve equation forms and for $p \neq 2 \text{ mod } 3$)

Method 3: If you want something which is uniform and ECDLP-secure then you can simply combine the above two methods:

$$H_{us}(x) = H_u(x) + H_I(x)$$

---

For $H_2$ you likely want to securely hash the full string representation of the point (as doing something like using the x coordinate would have a trivial hash collision of $-P$) to $\{0,1\}$ and then reduce that to $F_p$. Something like:

$$H_{CW_3}(x) = ((a_3x + b_3) \text{ mod } q) \text{ mod } p$$

$$H_{Z_p}(P) = H_{CW_3}(SHA256(P_x | P_y))$$

Which will produce a secure, uniform result in $Z_p$