The Premise Let HA and HB be two distinct, secure cryptographic hash functions.
HA:{0,1}∗→{0,1}n HB:{0,1}∗→{0,1}m (Where n and m are the output bit lengths) We operate on two fundamental assumptions for any secure cryptographic hash function:
One-Wayness (Preimage Resistance): Given an output y, it is computationally infeasible to find any input x such that H(x)=y. Pseudo-randomness: The output of the hash function is computationally indistinguishable from a truly random function. Colllary: Pseudo-randomness implies that for two independent hash functions HA and HB, their outputs are uncorrelated. Knowing HA(x) provides no useful information about the value of HB(x).
Suppose there exists an efficient, general-purpose conversion algorithm, F, such that for any input message x:
F(HA(x))=HB(x)
Proof by Contradiction We will assume that such an efficient algorithm F exists and demonstrate that this assumption violates the core property of pseudo-randomness.
To prove a function is not pseudo-random, we construct a “distinguisher” — an algorithm that can successfully tell the function’s output apart from a truly random output.
Consider an adversary whose goal is to determine if it’s interacting with our real hash functions (HA,HB) or with two truly independent random functions (RA,RB).
World 1 (Real): The adversary can query an oracle that provides the pair (HA(x),HB(x)) for any chosen x. World 2 (Random): The adversary can query an oracle that provides the pair (RA(x),RB(x)) for any chosen x, where RA and RB are independent, truly random functions. 2. The Adversary’s Strategy
The adversary uses our hypothetical conversion function F to win this game with near-certainty.
The adversary chooses any single input message, x0. It submits x0 to a hashing oracle The oracle returns a pair of outputs, (yA,yB). The adversary then computes F(yA) and performs a simple test: Is F(yA)=yB ? 3. Analyzing the Outcome
In World 1 (Real): The returned pair is (HA(x0),HB(x0)). By the definition of our assumed function F, F(HA(x0)) is guaranteed to equal HB(x0). The test passes with probability 1.
In World 2 (Random): The returned pair is (RA(x0),RB(x0)). Since RB is a truly random function independent of RA, its output RB(x0) is a random m-bit string. The value F(RA(x0)) is some fixed output. The probability that this specific output happens to match the random output from RB is negligible: 1/2m. 4. The Contradiction
The existence of the function F allows an adversary to distinguish between the real world and the random world with probability 1.
This directly violates the pseudo-randomness assumption, which underpins the security of all cryptographic hash functions.