Let's say we have a message m of small size. I am looking for a system $S$ so that $S(m)$ is arbitrarily large, we can easily compute the inverse $I(S(m)) = m$, and any modification to $S(m)$ makes it impossible to recover any part of the initial message $m$.

Let's say my initial message is $m$ = "Hello world!" (12 characters long), and I want $S(m) = c$ to be larger (let's say, 1000 characters long, so 8000 bits). Let's say that $c'$ is the same as $c$, but with at least one error (one bit changed). I know $I(c) = m$. I want $I(c') \neq m$, so that it is impossible to obtain $m$ from $I(c')$.

Initially, I thought I could do this with some kind of symmetric private key encryption, with padding on the message and the "private" key public (anyone should be able to get $m$ from $c$; but no one should be able to get $m$ from $c'$). I tried AES in CBC mode, with padding to increase the original message's length, but it didn't do what I wanted. Introducing an error in $c$ would see this error propagate to the latter blocks, but not the preceding blocks, and so the original message $m$ was often still legible.

Is there a system that could achieve the specific behavior that I'm looking for?

Thanks in advance!

  • $\begingroup$ Are you looking for a keyed transform (that is, without the "key", one cannot compute $I(c)$, even with the correct $c$), or will an unkeyed transform suffice? $\endgroup$ – poncho Jul 8 '20 at 14:07
  • $\begingroup$ ... and if you're looking for a keyed transform, do you want a key for only one direction or both? $\endgroup$ – SEJPM Jul 8 '20 at 14:08
  • 1
    $\begingroup$ What you're asking for should be impossible. If a single bit is changed, I can try to reconstruct the original c by flipping each bit and trying to decode. As long as the message is recognizable this will always lead to the correct message and is quite efficient. $\endgroup$ – Maeher Jul 8 '20 at 14:35
  • $\begingroup$ @poncho For if I need a keyed transform, the answer is no. Anyone should be able to decipher an unmodified message. Using a preexisting keyed transform wouldn't be an issue though, as I could then just keep the key public. $\endgroup$ – MATHIEU SERAPHIM Jul 8 '20 at 14:40
  • $\begingroup$ So, what you're looking for is known as an "All-or-nothing" transform, see en.wikipedia.org/wiki/All-or-nothing_transform $\endgroup$ – poncho Jul 8 '20 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.