2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ For H1, there is an on-going RFC draft: github.com/chris-wood/draft-sullivan-cfrg-hash-to-curve $\endgroup$ – cygnusv Jul 19 '18 at 20:58
  • $\begingroup$ For $H_1$, is it needed that $M$ does not reveal $m$ such that $m\,P=H_1(M)$ where $P$ is a public point? Without this requirement, construction of $H_1$ is pretty easy as $H_1(M)=(H(M)\bmod n)P$ for some generic hash $H$ much wider than the group order $n$, and $P$ a public generator. BTW, I can't tell if there is consensus about if said property is part of the default definition of a hash. $\endgroup$ – fgrieu Jul 20 '18 at 16:11
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thank you for your response. I have a small question : when computing the values in the Icart's function should I use modulo arithmetic and thus use a cubic root modulo p and the modular multiplicative inverse for the $u^6/27$ for example ? Or should I just round the values I obtain ? Because otherwise x and y are not integers. $\endgroup$ – user1241025 Jul 22 '18 at 13:10
  • 1
    $\begingroup$ All operations in Icart's function are mod p. If you're curious I have implemented this method in : github.com/jadeblaquiere/fspke/blob/master/src/icarthash.c $\endgroup$ – jadb Jul 22 '18 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.