# Hashing based on the discrete logarithm problem

At a first look, one could use the elliptic curve discrete logarithm problem to grant for the onewayness of $H(x)=x*G$ (where $G$ is the generator point of the cyclic subgroup).

Additionally, $H(x)$ is homomorphic since $H(x+y)=H(x)+H(y)$, which could prove to be a useful property for a hash function in some applications.

What are some of the disadvantages or vulnerabilities that makes such a hashing scheme not popular in practice?

• One could easily find a collision for $x$ by adding the curve order $l$ to $x$, so that $H(x)=H(x+l)$. – VincBreaker Aug 10 '18 at 21:07
• @VincBreaker yes that would be a collision unless domain of $x$ is a prime field defined by this group order. – Vadym Fedyukovych Aug 13 '18 at 12:05

## 1 Answer

A secure hash function based on the discrete log problem is $H(x\|y)=x\cdot G+y\cdot P$, where $P$ is a random point for which the discrete log is not known and "$\|$" denotes concatenation; this was shown by Damgård. This can be proven collision resistant under the discrete log assumption (if you can find a collision then this can be used to find the discrete log of $P$). Note that in order for it to be of interest, the output has to be shorter than the input. However, this is easily achieved for most curves by using point compression. Once you have this function, you can get a general collision-resistant hash function by applying the Merkle-Damgård transform.

Of course, this would be extremely inefficient, but it is a collision resistant hash function from the discrete log problem.

The paper presenting this is Collision Free Hash Functions and Public Key Signature Schemes by Ivan Damgård. It is also described in Section 8.4.2 of the Katz-Lindell textbook (second edition).

• If you haven't seen this before, the proof is super-cool. I suggest trying to work it out yourself (take a collision and see what you can do with it). – Yehuda Lindell Aug 12 '18 at 16:35