Is it possible to make encryption immune to brute force attacks?

Encryption is the art of turning a message into what appears to be nonsense which can be turned back into the message if you know the right secret “‍key‍”. For example, “‍Fpqqwnuynrs‍” is a cypher of “‍Compression‍” with the key “‍to decrypt, subtract a digit of pi from each letter‍”: F – 3 = C, p – 1 = o, q – 4 = m, etc.

Most encryption schemes are built with the assumption that everyone will know how you encrypted something, they just won’t know a single small fact, most often a password. This assumption means that there is always room for what is called a “‍brute-force attack‍”: to decrypt something you get a lot of fast computers to try every possible password until you find one that gives back a message that makes sense.

Brute force attacks rely on redundancy: most decrpytions are patently nonsense because they lack the redundancy that we add to everything to make it robust to miscommunication. Thus, I can easily tell if I successfully decrypted a message or not.

Now, suppose instead we had an encryption scheme where every candidate key resulted in a sensible-looking message. In that case, brute force attacks would become almost meaningless. If someone tried to brute-force decrypt your bank account information from an encrypted online purchase they’d end up with a few billion valid-looking account numbers and names, only one of which was actually your account, instead of a few billion blurbs of nonsense text just one of which looked anything like an account number and name.

Such a brute-force-proof encryption scheme is closely related to perfect compression. If I compress away all of the context, all of the things I could use to sanity-check a message, then I’m left with a space where there is no such thing as nonsense. If I can identify every conceivable message in a particular context and number each one then all I need to communicate is a simple number and any decryption, creating a number, will look reasonable.

Since compression depends closely on context, there are no general-purpose perfect compression schemes and thus no general-purpose brute-force-proof encryption schemes either. But in theory, for any given domain, such an encryption scheme does exists.