Is there some reversible mapping that as uniform as a hash?

Question

I am looking for a mapping to encode a n-bits information into n-x+m bits.

• The (n-x) bits need to be as uniform as posible, and I can accept a small mount of data to achieve this (such as a nxn matrix).
• The m bits are free to be in any distribution.

n,x,m are fixed. 0<m<n, x>=0.

In fact, I want a hash function that encode some of the string into the hash value so that I can save some space from keeping the whole string.

I read that any invertible matrix can form a bijection linear transformation, but it is not a uniform one.

And, since it is to be used as "hash", space and time are importent too.

Answer 1

Hmm... If I understand you correctly, here's something that might work:

Let $H$ be a hash function taking an arbitrary string as input and producing an $n$-bit string as output. Given an input string $s$, let $s_0$ denote the first $n$ bits of $s$ and $s_1$ the rest (i.e. $s = s_0\;||\;s_1$, where $s_0$ is $n$ bits long and $||$ denotes concatenation). Then define $$f(s) = (s_0 \oplus H(s_1))\;||\;s_1,$$ where $\oplus$ means bitwise XOR. It's easy to see that $f$ is its own inverse, i.e.$f(f(s)) = s$, so that the input string $s$ can be recovered from $f(s)$ just by running it through $f$ again.