# Given a boolen hash function (based on XOR), find the $n^{th}$ key for a specific hash.

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.

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.

• Can you explain your implementation? I don't need a popcount() algorithm, it is provided by the hardware as an instruction. But what I do need it to find out the nth key with a specific hash (In O(1)). What you are telling me is how to find the hash of a single key. FYI, for finding a hash of a single key I am doing exactly what you are doing (Except I use hardware provided popcount()) – Saksham Jain Oct 7 '18 at 19:30
• What is nth key? are trying to implement a hash table? So the nth key is one of the $2^32$ key set? – kelalaka Oct 7 '18 at 20:39
• Nth key is the nth key, starting from 0, that has same hash for a given hash. For example, for hash fucntion hash = h(key), if this is the key to hash mapping (key, hash) -> (0, 1), (1, 7), (2, 6), (3, 1) ... then for hash = 1, the 1st key is '0' and 2nd key is '3' and so on. – Saksham Jain Oct 8 '18 at 16:28
• @SakshamJain my problem, I don't see a chain here. Could you explicitly show the chain. – kelalaka Oct 8 '18 at 19:00
• If we look at the given example: /* 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  Here the 3rd Key for hash 1 is 0x5 – Saksham Jain Oct 8 '18 at 20:36