Can there be two hash functions without common collisions?

Question

Is there a way to prove/create (or are there known hash functions) two hash functions that never have the same collision? I mean, like provable in way that someone who took one cryptography class in university can prove.

For example, I want hash functions $A$ and $B$ such that if hash function $A$ collides on $X$ and $Y$, then $B$ will not collide on these $X$ and $Y$:

$$A(X) = A(Y) \quad \Rightarrow \quad B(X) \neq B(Y) $$

Answer 1

No, in general, there will always be a pair of inputs that will collide for both hash functions. Specifically, if the hash functions have fixed sized outputs, and both take an arbitrary input which is at least as long as the sum of their outputs, then there will be bitstrings $X$ and $Y$ with $X \neq Y$, $A(X) = A(Y)$ and $B(X) = B(Y)$

Here is a simple demonstration that such a pair must exist: let us assume that $A$ generates an output which is $n$ bits long, while $B$ generates an output which is $m$ bits long, and further assume that $n, m > 0$.

Now, consider the set of all possible bitstrings of length $n+m$, along with the empty bitstring (or, if you don't like that, pick any bitstring shorter than $n+m$). This set has size $2^{n+m}+1$. If we apply the hash function $A$ to each member of the set, there are $2^n$ possible outputs, and hence (by the pigeon-hole principle), there must be some output with at least $2^m+1$ preimages. Let us pick such an output, and call the subset when generates that output subset $W$.

Now, let us consider applying the hash function $B$ to each member of $W$; $W$ has size at least $2^m+1$, and $B$ has $2^m$ possible outputs; hence there must be two elements $X$ and $Y$ of $W$ with the output.

This pair $X$ and $Y$ is a common colliding pair for $A$ and $B$.

Answer 2

The combined output of the two hash functions must be at least as large as the input*. This follows trivially from the Pidgeonhole Principle.

The general way to construct this is using a permutation and partitioning the output into two parts that together make up the whole thing.

If you use hash-function as something that takes (almost) unlimited length inputs and produces a short constant length output, then it's impossible.

But in practice you shouldn't care. If you have a secure 256 bit hash function, collisions will never happen in practice.

---

* With size I mean the number of possible values the input/output can have

Answer 3

[Poncho's answer is correct and is probably the answer you are looking for, but I won't delete my answer as I believe there are cases where the construction has merit.]

It seems like you could construct this. Let $\oplus$ denote xor, with suitable length extension of the operands. Given any hash function $F$, define $G(x) := F(x) \oplus x$. If $x \neq y$ and $F(x) = F(y)$, then $G(x) = F(x) \oplus x = F(y) \oplus x \neq F(y) \oplus y = G(y)$.

You could use this construction to make the hash function $B$ from your given hash function $A$.