2
$\begingroup$

Is there any hash function which takes the co-ordinates of an elliptic curve $E_p(a,b)$ as input and gives an integer value i.e.

$h(.) : \{(x,y) \in E_p(a,b)\} \rightarrow \mathbb{Z}$

$\endgroup$
  • 1
    $\begingroup$ What about $H(x + p\cdot y)$ where $H$ is your favorite hash function? $\endgroup$ – user94293 May 30 '16 at 16:59
  • 1
    $\begingroup$ If this is for a practical application you'd usually just hash (and expand) the x-coordinate of the curve point. $\endgroup$ – SEJPM May 30 '16 at 18:41
  • 2
    $\begingroup$ Choose an encoding for curve points and hash the encoded point. Then interpret the hash as integer. $\endgroup$ – CodesInChaos May 30 '16 at 20:22
  • $\begingroup$ @CodesInChaos will that yield a unique value ? I guess that will depend on the encoding algorithm. If the encoded result is unique then hashed output will be unique. Isn't it ? $\endgroup$ – Sandy May 31 '16 at 3:49
  • 1
    $\begingroup$ @Sandy: The encoding $(x,y) \mapsto x + py$ (in $\mathbb{Z}$) is unique for each point $(x,y)$ on an elliptic curve defined modulo $p$. Alternatively, you can also encode points as $(x,y)\mapsto x + 2^k y$ for some $k$ such that $2^k > p$. $\endgroup$ – user94293 Jun 2 '16 at 13:48
1
$\begingroup$

Let $k$ denote the bit-size of $p$. Let also a hash function $H \colon \{0,1\}^{2k} \to \{0,1\}^\ell$. We define the hash value of a point $P = (x,y)$ on an elliptic curve over $\mathbb{F}_p$ as $$h \colon E_p(a,b) \to \mathbb{Z}, (x,y) \mapsto H(x + 2^k y)$$

One-wayness follows from hash function $H$ (for example SHA-3).

Note. There is a slight abuse of notation above, integer $x+2^ky$ should be seen as a binary string when applying hash function $H$; and the output (namely, $H(x + 2^k y)$) should be regarded as an integer. This is done by the canonical representation: a $t$-bit integer $a \in \mathbb{Z}$ can uniquely be represented as $a = \sum_{i=0}^{t-1} a_i 2^i$ with $a_i \in \{0,1\}$, which in turn can be seen as the $t$-bit binary string $a_{t-1}a_{t-2}\ldots a_0$, and conversely.

$\endgroup$
  • $\begingroup$ Using only the $x$-coordinate does not guarantee collision resistance: both $P=(x,y)$ and $-P=(x,-y)$ would hash to the same value. Both the $x$ and $y$ coordinates should be used. $\endgroup$ – user94293 Aug 3 '16 at 15:32
0
$\begingroup$

Let $E$ be the elliptic curve defined over $F_p$. If $\#E=p$ then $E$ is called anomalous elliptic curve. In this curve we can solve discrete logarithm problem in polynomial time. Let $P$ be the base point of this curve. Now we can easily construct hash function as bellow:

$$H(Q=k\cdot P)=k.$$

$\endgroup$

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.