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.
$\begingroup$
$\endgroup$
9
-
2$\begingroup$ I just have to ask — Why don't existing, well-vetted hash algorithms satisfy your needs? $\endgroup$– e-sushiCommented May 5, 2017 at 10:37
-
$\begingroup$ Uhm, hash the representation? $\endgroup$– SEJPMCommented May 5, 2017 at 12:56
-
$\begingroup$ @SEJPM can you define "representation"? $\endgroup$– richardCommented May 6, 2017 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 ♦Commented May 6, 2017 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 ♦Commented May 6, 2017 at 15:47
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
4
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).
answered May 6, 2017 at 15:45
-
$\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 ♦Commented May 6, 2017 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$– ponchoCommented May 6, 2017 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 ♦Commented May 6, 2017 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$– ponchoCommented May 6, 2017 at 16:23