1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's not very clear... Aparently you want some invertible function that maps a string $s$ (length $n$) to a pair $[s_1,s_2]$ (lengths $n_1,n_2$, with $n_1 < n$) so that $s_1$ is statistically "uniform" - and I presume you want $n_1$ is fixed, independent of $n$. Is that so? $\endgroup$ – leonbloy Jul 23 '11 at 18:08
  • $\begingroup$ Yes. n1 need to have a fixed relationship to n. Such as n1=n-2; $\endgroup$ – Galaxy Jul 23 '11 at 18:14
  • $\begingroup$ Two examples - probably dumb, they surely they wont fit your need, but you'd tell us why, your problem is not well posed. 1) take $s_1$ as a (say) MD5 hash of $s$, trim it (or pad with noise) to $n_1$ bits; append the full original string ($s_2 = s$). 2) compress the string (huffman, zip, etc) and split it into two parts (first of length $n_1$). $\endgroup$ – leonbloy Jul 23 '11 at 18:24
  • $\begingroup$ I just add 0<m<n to make is more clearly. Compress doesnot meet m<n. $\endgroup$ – Galaxy Jul 23 '11 at 18:29
  • $\begingroup$ reversible? If $x > m$ then it can't be reversible by Pigeonhole principle. $\endgroup$ – Willie Wong Jul 23 '11 at 19:22
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Seems good. Random is privided by H(s1) and, might be kept after XOR. I am not so sure about this point. However, this is a good starting point. $\endgroup$ – Galaxy Jul 23 '11 at 18:43
  • $\begingroup$ If XOR is not good enough, you could replace it with some other parametrized, invertible bijection $E_K$ to get $f(s) = E_{H(s_1)}(s_0)\;||\;s_1$. To invert $f$, replace $E_K$ with its inverse $E_K^{-1}$. In particular, a block cipher with the key $K$ will do for $E_K$, although that might be considered overkill. $\endgroup$ – Ilmari Karonen Jul 23 '11 at 19:53

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.