Would a non-deterministic (read: randomized) compression algorithm be crypto-safe? Would a compression algorithm that randomly shifts stuff around every iteration be TLS/crypto-safe?

This randomization would prevent the same byte sequence from appearing twice in a row, thus making it harder to figure out the key and stuff. Altho I don't have any crypto knowledge...

Note that it would only apply to the compression step. The decompression step would always produce the same output when given the same input.
... a compression algorithm that randomly shifts stuff around ...


This is a contradiction in terms, surely? The extent to which any block of data can be compressed is directly related to the entropy of this data. The more predictable the data is, the lower its entropy and the more compressible it becomes.

If you apply random transformations to your data, you are increasing its entropy and making it less compressible. This defeats the purpose of your compression algorithm. Ultimately, you will end up with data that is indistinguishable from random noise, making it completely incompressible.