patternMinor
Two-way Hash Functions
Viewed 0 times
functionstwowayhash
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#69422, answer score: 7
Revisions (0)
No revisions yet.