Re: it ought to be impossible to recover the original information.
It is also very hard indeed to recover the image of James Brown out of 64 byte.
You just need a specialized compression algorithm. I have one that can reconstruct an image of James Brown from a single bit.
Here's the pseudocode for the expander:
if first bit is 0
return hard-coded James Brown image
else
remove initial bit and pass remaining data to gzip
Extending this to support an image of Barry White is left as an exercise for the reader.