Two-way Hash Functions

Question

While I'm aware most (good) hash functions are one-way (or at least mostly so), I'm wondering if there's any construct (not necessarily called a hash function) which behaves in many ways like a hash function, but can be easily reversed.

For example, a function $f$ takes an arbitrary string $x$ and maps it to $y$, where $|y| = c$ for some constant $c$ (i.e. $y$ is always the same length), and collisions are infrequent, so in general, $f(x) = y$.

In this case, I'm wondering if it's possible to construct a function $f$ matching the criteria above, but where $f^{-1}(y) = x$ is as easily calculable as $f(x) = y$, in a computational complexity sense.

In the case of collisions, where $\forall x \in S$,  $f(x) = y$,  $f^{-1}(y)$ might give you either the entire set $S$, some subset of $S$, or even a single element from $S$

In the case that this is not theoretically possible, possibly due to the fact that $f$ allows strings of arbitrary lengths and $|y| = c$, so infinite collisions must occur(?), then what if we only allow $|x| < C$, such that the number of possible collisions are finite?

Obviously, you wouldn't use this kind of function for anything security related, but it might be useful for something like reverse image searching?

Answer 1

Yes, this is possible. Here are two examples of such a function.

One function is $f(x)=x$. This has no collisions, and the function is easy to invert.

Here is another function: define $f(x) = x$ if $x$ is 256 bits long, otherwise $f(x) = \operatorname{SHA256}(x)$. Then it is very hard to find collisions for $f$ (since SHA256 is collision-resistant). At the same time, given $y$, it is easy to find an $x$ such that $f(x)=y$, so we might be willing to say that $f^{-1}(y)$ is easily computable. To put it another way, given $y=f(x)$ where we are told $y$ but not told $x$, it is easy to find $x'$ such that $f(x')=y$. The catch is that $x'$ might be different from the original $x$.

Answer 2

In addition to everything that others have said: any cipher is an invertible "hash" function. And there are standard ways to construct them; one common way of turning a one-way function into an invertible function is to use a Feistel network.

They're quite useful in practice. See, for example, this question from a few years ago.

Answer 3

A function can only have an inverse if the range is at least as large as the domain. One important property of hash functions is that they map their input to a much smaller output. Therefore every output has many different inputs mapped to it.

While you could in principle invert simple hash functions (in the sense of finding all possible preimages efficiently, where efficiency is measured per preimage generated), there will be a great many of them – infinitely many, in case the function accepts arbitrarily long inputs – so this won't be too useful.

Answer 4

You can create any such mapping function if you don't have any constraints. Your input range can be large, but your data might be sparse, so you can have a mapping that converts the input into a domain with a smaller range, and it is quite possible that it doesn't have collisions (especially in image domain).

For image domain, for example, most of the histogram processing techniques (i.e. gamma correction) can be considered as reversible mapping functions of pixel values.

It all boils down to your mapping function being one-to-one, so that it is reversible.