## fixed-point hash

posted on 19 Nov 2019

Suppose these requirements are given for a cryptographic hash function:

``````1) x != y  ->  hash(x) != hash(y)  (with high probability)
2) hash(x) != hash(y)  ->  x != y  (with high probability)
3) It is intractable to discover x given only hash(x)
``````

None of them prohibit the existince of a fixed point:

``````Not a rule:  hash(x) != x
``````

If `hash(x) == x` for some `x`, then you discover `x` when you’re given `hash(x)`, so it doesn’t violate property #3.

If you were to simply pick an `x` and redefine `hash(x) == x`, as long as `hash(x)` doesn’t have known preimages, the fixed hash continues to satisfy all of the properties.

(In fact, you can set the output of any input value to any output value that doesn’t have a known preimage).

### `fixhash` function

`fixhash` takes a hash function and a point, and replaces the hash function’s value at that point.

``````fixhash(hash,fixin,fixout) = H
where
H(fixin) = fixout
| H(x) = hash(x)
``````

Again, the key to using `fixhash` is to ensure `fixout` has no known preimage. Since you have one choice before a preimage is known for your fixed hash, to keep it simple you could choose `fixout == fixin`.

### `H0` function or nullable hash

The `H0(x)` function is defined with respect to a given hash function as:

``````H0 = fixhash(hash, 0, 0)
``````

In other words,

``````H0(0) = 0
H0(x) = hash(x)
``````

Everyone already knows `hash(0)`, it’s a canonical test case for `hash`. No usage of the primitive can depend on the preimage of `hash(0)` being impossible to discover, because it is known: `0`. Likewise knowing that the preimage of constant `H0(0)` is `0` could not somehow break a protocol that depended on the cryptographic properties of `hash`. That protocol would be insecure to begin with.

And yet, nobody knows `unhash(0)`. The probability of ever encountering a collision remains negligible!

### forecast

• Writing hash-linked data structures with `H0`
• `H1`, `L1`, `H2`, `L2`, … : Nullifying a region of the hash domain
• Hash-domain kernel: DHT lookup as trap mechanism