Why are theoretical hash constructions based on the hardness of the discrete logarithm problem not really used in practice?

Question

In an old 2010 Q&A at StackOverflow, Pornin states:

… a good hash function "should not" allow a property such as surjectivity to be actually proven.

This makes sense to me when looking at, for example, the SHA-2 function family.

Yet, in an answer to Has any crypto hash function been proven to be surjective?, Lindell provides an answer with a nice example of a hash function that allows such proof.

Since the widely known, theoretical construction based on the discrete log problem combined with a Merkle-Damgård transform seems pretty solid at first glimpse, it begs for the question why alike hash constructions don't tend to be practically used more often. The surjectivity (and according collision resistance) proof seems to be a plus when comparing it to the somewhat non-provability (more of an assumption) of the surjectivity of SHA et al.

Is this merely based on the fact that discrete log functionalities tend to be computationally expensive and harder to implement on specific hardware (compared to constructions like SHA-2)?

Or are there other implications (maybe related to cryptographic security or specific attack vectors) which could explain why such theoretical hash constructions based on the hardness of the discrete logarithm problem don't tend to be practically used and preferred (due to the more clear proof)?

Answer 1

I would say it is largely due to

the fact that discrete log functionalities tend to be computationally expensive and harder to implement on specific hardware (compared to constructions like SHA-2)

In many (perhaps most) use cases, hash functions are not primarily used for their cryptographic security properties, but for efficient and comfortable data management, e.g. in databases. So complexity of running the algorithm should be minimal.

In addition, good hash functions do provide strong security and have several advantages over applications of finite group schemes (where the discrete logarithm applies). In particular, they provide extremely little algebraic structure, meaning there is not much to attack in the first place. This is also the reason why many consider hash functions to be quantum computer resistant, while it is already known that Shor's algorithm can solve the DLP efficiently.

In short, I do not know of any advantage that a DLP-based hash function would bring about, while there certainly would be some shortcomings by comparison.

Answer 2

As pointed out by @indiscreteLogarithm, the hash function based on discrete log is just way to slow to be used in practice. However, I very much do NOT agree with the statement that there would not be advantages to the scheme. The DLP scheme has a rigorous proof of security relative to the discrete log problem which means that breaking it requires breaking the discrete log problem. Thus, breaking such a hash function would make the SHA1 break seem insignificant. If you are worried about quantum attacks, then there also hash functions based on the learning with errors problem (and other lattice problems), that are also provably secure. These hash functions based on lattices are also quite efficient.

Anyway, bottom line, the "only" disadvantage is the fact that they are not efficient. However, this disadvantage is so significant that it means they are not really usable in practice.