# A hash functin based on XOR and matrix multiplication

Imagine an $$n$$ bit to $$n$$ bit hash function defined as follows: Let $$K$$ and $$K'$$ be two random predetermined $$n\times n$$ matrices. Then the hash function $$h$$ of an $$n$$ bit number $$a$$ would be:

$$h(a)=K\cdot a\oplus K'\cdot \bar{a}$$

Note that addition in matrix multiplication is done on one bit, so it's equivalent to $$\oplus$$ operation, Now my question is that if this function is reversible.

$$h(a)=K\cdot a+K'\cdot \bar a=K\cdot a+K'\cdot(a+1^n)=\underbrace{(K+K')}_M\cdot a+\underbrace{K'\cdot 1^n}_c=M\cdot a+c$$
Also note that $$h(a)=M\cdot a$$ is an universal hash function for $$n$$-bit input and $$m$$-bit output, as $$\Pr\left[h(x)=h(y)\right]=2^{-m}$$ with the randomness being over the choice of $$M$$. Clearly in this case $$M=K+K'$$ both of which are random matrices so this clearly holds. Now note that adding $$c$$ is essentially just a permutation over the bit values which doesn't change the collision properties, so it preserves the universality.
Also note that the first observation means that given $$n+1$$ chosen input-output pairs you can fully recover a description of $$h$$ and recover all information that you could from $$Ma$$ about $$a$$ when given $$h(a)$$. The strategy to the recovery would be to request $$0^n$$ and get $$c$$ this way. Then request $$0^n$$ with the $$i$$-th bit set for all $$n$$ values of $$i$$ to learn all the columns / rows of the $$M$$ matrix.