1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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()) $\endgroup$ – Saksham Jain Oct 7 '18 at 19:30
  • $\begingroup$ What is nth key? are trying to implement a hash table? So the nth key is one of the $2^32$ key set? $\endgroup$ – kelalaka Oct 7 '18 at 20:39
  • $\begingroup$ 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. $\endgroup$ – Saksham Jain Oct 8 '18 at 16:28
  • $\begingroup$ @SakshamJain my problem, I don't see a chain here. Could you explicitly show the chain. $\endgroup$ – kelalaka Oct 8 '18 at 19:00
  • $\begingroup$ 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 $\endgroup$ – Saksham Jain Oct 8 '18 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.