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.


1 Answer 1


First note that the following holds:

$$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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