# Generating a XOR Hash function for a given group of numbers to maximise collisions

Given $$x$$, a vector of $$m$$ distinct bit vectors of bit length $$N$$, I want to use an XOR-hash $$h$$ such that all $$x_i$$ collide to the same value.

I define an XOR hash $$h$$ which takes bit vector $$q$$ as input and performs an AND operation on each bit of $$q$$ with a bit vector $$k_i$$ of bit length $$S$$.

$$h(q) = (k_1.q_1)\oplus(k_2.q_2)\oplus...\oplus(k_N.q_N)$$

The "AND" dot operation $$a.b$$ takes bit vector $$a$$ and boolean/bit $$b$$ and returns ($$a$$ if $$b$$ else 0).

Here $$k$$ is a vector of bit vectors, and my goal is to find $$k$$ such that for some constant bit vector $$y$$ of bit length $$S$$, $$h(x_i) = y$$ for all $$i$$.

Section 4.3 in this paper describes this hash function. http://www.mathcs.emory.edu/~whalen/Hash/Hash_Articles/IEEE/Efficient%20hardware%20hashing%20functions%20for%20high%20performance%20computers.pdf

It is my understanding that when you try to XOR-hash a bit vector of size $$N$$ to a bit vector of size $$S$$, there will be $$2^{N-S}$$ collisions. I want to choose $$k$$ so that all $$m$$ bit vectors in $$x$$ hash to the same value $$y$$.

For example, take $$N=15$$, and $$m=200$$.

I am trying to round $$m$$ to the next power of 2. In this case, I would like to round 200 to 256 and then have $$2^{N-S}=256=2^8$$, so that $$N-S=8$$ and thus $$S=7$$.

In other words, I can now XOR-hash from a $$N=15$$-bit space to a $$S=7$$-bit space with all the $$m=200$$ inputs colliding to the same output. I understand that there are an additional 56 numbers which are not accounted for. We choose any bit vector of size 15 which is not in $$x$$.

How do I go about finding $$k$$ deterministically (or closed-loop fashion) to make all the hashes collide?

• Not exactly a clear question. What is $N(15)$? do you mean the number of bit o each $m$ us 15? then you should use $N=15$. Dou you hash $m_i$ with a cryptographic hash function then x-or the output? $$\bigoplus_{m=1}^{200} hash(m_i)$$ – kelalaka Jul 5 '20 at 7:55
• @kelalaka . Thanks for the advice. I have corrected the post accordingly. I am trying to generate a hash function which outputs the same value for all the m values. In other words $hash(m_0)$ = $hash(m_1)$ =$hash(m_{200})$ – Acinonyx Jul 5 '20 at 11:38
• If the hash is a Cryptographic hash than it is an impossible task. However, once you find a collision, a multi-collision is much easier. – kelalaka Jul 5 '20 at 11:54
• Explain what you mean by "using an XOR hash". XOR is not a hash algorithm. You can use XOR as one of operations when calculating hash. But describe what else are you doing to calculate hash. – mentallurg Jul 5 '20 at 12:01
• @mentallurg I have added more detail to the question. I think this is call XOR AND or maybe it is called AND XOR. Cannot remember the full name. – Acinonyx Jul 5 '20 at 14:02