1
$\begingroup$

Can I create a secure hash function $h: E(\mathbb{F}_p) \rightarrow \mathbb{Z}_q$ (for some $q$) where $E(\mathbb{F}_p)$ is an elliptic curve on the finite field of $p$ elements? By secure hash function I mean: one way, strongly collision free.

$\endgroup$
  • 2
    $\begingroup$ I just have to ask — Why don't existing, well-vetted hash algorithms satisfy your needs? $\endgroup$ – e-sushi May 5 '17 at 10:37
  • $\begingroup$ Uhm, hash the representation? $\endgroup$ – SEJPM May 5 '17 at 12:56
  • $\begingroup$ @SEJPM can you define "representation"? $\endgroup$ – richard May 6 '17 at 10:44
  • 1
    $\begingroup$ @SEJPM You may have to perform mod $q$ afterwards. Furthermore, the result will not be perfectly distributed. The question is, does it have to be? It's certainly one way and strongly collision free. Oh, and you can simply use a compressed or uncompressed point representation, there doesn't seem to be a particular need to encode in ASN.1 - although equally viable. $\endgroup$ – Maarten Bodewes May 6 '17 at 10:57
  • 1
    $\begingroup$ Hash functions take bits and bytes, so you need to map it to bits / bytes. In general an EC point consists of at least two numbers so it is a bit tricky to convert those into one number. Bits/bytes is easy though. $\endgroup$ – Maarten Bodewes May 6 '17 at 15:47
1
$\begingroup$

With the current requirements, it seems like any member of $H(C(P)) \bmod q$ should work.

Where:

  • $H$ is the set of secure hash functions, e.g. SHA-512;
  • $C$ is the set of canonical encoding schemes of the points, e.g. a compressed point representation (02+X or 03+X depending if Y is odd or not);
  • $P$ a the set of possible points on the curve;
  • $q$ is the order of the curve (already specified).

This is certainly one way and collision free, as long as the used curve and hash function outputs are large enough. But note that it is not well distributed over $\mathbb{Z}_q$ (especially if the hash is shorter than $q$ of course, when viewed as an unsigned number).

$\endgroup$
  • $\begingroup$ I suppose that X is within [0,Q) and that a compressed point means that Y is either 02 or 03 (which can be represented by a single bit). So with that in mind you could use the answer of this question to use FPE to create a well distributed point I guess. But I'm not all that sure that it is OK distribution-wise. $\endgroup$ – Maarten Bodewes May 6 '17 at 15:50
  • 2
    $\begingroup$ If you need a uniform distribution, then replace the $H$ with an XOF (e.g. SHAKE), have the XOF generate a stream of bits, and use one of a number of techniques to convert that stream of bits into a $\mathbb{Z}_q$ value $\endgroup$ – poncho May 6 '17 at 16:05
  • $\begingroup$ Interesting idea. I presume you can use the same techniques as generating a random number in a range to create the value. $\endgroup$ – Maarten Bodewes May 6 '17 at 16:16
  • $\begingroup$ True; typically, we don't care enough about a precisely uniform value to go to that effort, but we could... $\endgroup$ – poncho May 6 '17 at 16:23

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.