# Looking for a way to enlarge a message so that any modification to the “enlarged” message makes recovering the original message impossible

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!

• 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? – poncho Jul 8 '20 at 14:07
• ... and if you're looking for a keyed transform, do you want a key for only one direction or both? – SEJPM Jul 8 '20 at 14:08
• 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. – Maeher Jul 8 '20 at 14:35
• @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. – MATHIEU SERAPHIM Jul 8 '20 at 14:40
• So, what you're looking for is known as an "All-or-nothing" transform, see en.wikipedia.org/wiki/All-or-nothing_transform – poncho Jul 8 '20 at 14:47