A boolen hash function is given that takes a hexadecimal key as input and returns the hash for that key (hash can be only 0 or 1). The hash function is based on XORing bits of the key.
For example, an sample hash function in C would be written like this
/* This hash function calculates hash based on XORing bits 0,1,3,4 of the key */
bool hash_function(uint64_t key) {
bool bit0 = (key >> 0) & 0x1;
bool bit1 = (key >> 1) & 0x1;
bool bit3 = (key >> 3) & 0x1;
bool bit4 = (key >> 4) & 0x1;
return bit0 ^ bit1 ^ bit4 ^ bit5;
}
Given this hash function, following is the key-hash pair:
key hash
0x0 0
0x1 1
0x2 1
0x3 0
0x4 0
0x5 1
0x6 1
0x7 0
0x8 1
....
So given this hash function, can you find the $n^{th}$ key that has a hash 0 in $O(1)$ (i.e. constant time) with the first key starting at 0x0?
For example, for n = 2, key = 0x3, for n = 4, key = 0x7 ...
The hash function given above is a toy example. The actual hash function that I have is XORing bits 0,1,6,7,10,13,14,15,16,18 of the key (i.e. the real hash function is more complicated).
I need solution to this problem for my project really badly. I need to be able to find the $n^{th}$ key in as few mathematical operations as possible as my code is very performance sensitive.
If O(1) is not possible, what is the next best possible solution? I currently can only think of doing brute force, with finding hash for all keys from 0x0 to 2n - 1.
Thanks in advance.
Let $y = hash\_function(x)$, for some $x$ in the input space.
$hash\_function$ returns a bit form at least $2^{18}$ space, 18-bit, or
$$hash\_function: 2^{18} \rightarrow \{0,1\}$$
There are $\approx 2^{17}$ values mapping 1 and $\approx 2^{17}$ mapping 0, if we assume that your hash is uniformly random.
To find the pre-image is impossible. Once you find a value $x' = hash\_function(y)$, you cannot determine $x = x'$ or $x \neq x'$.
second preimage has $\approx 2^{17}$ solutions. Finding one is very easy, take a random value and test it, if not take another randomly. The problem is the values are not going to help you.