At least with classical information, I'm this is impossible. Classical information can be described with a sequence of bits. If you have a long enough shared r

At least with classical information, I'm this is impossible. Classical information can be described with a sequence of bits. If you have a long enough shared random sequence of bits, you can always use that as a one-time-pad, and encrypt it that way. For quantum information, I'm fairly sure that a quantum variation of the one-time-pad still works (where the pad consists of entangled pairs of qubits (the two parties each hold one qubit of each pair) instead of just shared random bits), and so it is, I think, also impossible. (And even if it was possible-but-only-for-quantum-information, I think the no-cloning theorem would still render it pointless, as the only thing preventing it from being encrypted would accomplish, would be allowing someone to successfully intercept a message that was being sent, instead of just causing the message to be lost) _____ Maybe the idea you are really looking for isn't "prevent it from being encrypted", but instead, "make any 'simple' reversible transformation of it, have parts that hint at a way to decode it / leave it still decodeable by some algorithm" ? where, I guess "simple" means something along the lines of, where the transformation can be described with much less information than the message to be sent? This, might(?) be possible? Ok, suppose the transformation is done by a deterministic finite state transducer, and specifically one which is invertible. (i.e. one T s.t. there exists a transducer S s.t. their composition gives the identity relationship over strings on the alphabet) . Then, uh, I guess you could like, take many copies of the message but transformed by different such transducers, and concatenate them together, except, accounting for the possibility of influence from the previous copies on the current copy. (accounting for this possibility by considering, given a transducer T and a string s1, constructing a transducer T' s.t. for any s2 and s3, ((s1 s2 [T] s3) iff (s2 [T'] s3)), or... something like that.) I think if the size of the possible adversary transducers you are dealing with is small compared to the messages you are sending, or rather, if you are allowed to encode your messages in ways that make them really gargantuan and much larger than could ever be practical, then, I think this could be done ? edit: On the other hand, if you don't restrict the adversary to small(relative to your message) reversible finite state transducers, but instead, say, turing machines which have their complexity (either kolmogorov complexity or levin complexity or something) much smaller than that of the message you want to send, and where these compute an transformation with a computable inverse which is provably an inverse, uh, well, that makes the problem harder, but, well, I guess if one can enumerate through all such turing machines (of which there will be finitely many, due to the bound on the complexity), and find the inverse of each, and apply each to the output of the machine, uh, well, one of these will produce the right output of course, but how can one go about determining which one it is? If you have an oracle for complexity... Ok, maybe it would be better to abstract more. The adversary, Chuck, has a large and fairly general, but finite, set of invertible maps from strings to strings, and they will choose one map h from this set. Alice and Bob also know this set, but not which map they chose. Alice and Bob need to agree on a pair of functions f, g from strings to strings, with the goal that the composition f ; h ; g is the identity function. If Alice and Bob have no restrictions on what functions they can use, then, I think there is a solution. The set of strings can be put in one to one correspondence with the natural numbers. What Alice and Bob need to do is find an infinite set of strings such that no two pairs of (transformation potentially chosen by Chuck, potential input to the transformation) produces the same output. For any input, there are only finitely many outputs that these transformations could give. Furthermore, because each of the transformations are invertible, for each of the outputs, each of the transformations produces that output for at most one input, and therefore there are only finitely many inputs such that some map in the set produces that output. So, for each input, there are only finitely many other inputs with which it could be confused. So, a sequence of these strings can be constructed as follows: start with the 0th possible string (under the chosen mapping). This will be used to encode 0. Then, repeat the following: If one has encodings for all natural numbers up to n, take the first string which cannot be confused with any of the strings one has already chosen to encode a number. This will be the encoding for n+1 . This works. (to decode, just find the only codeword which could be transformed into that by one of the maps) Perhaps this could be extended to allow Chuck to have a potentially infinite set of maps, but under the restriction that there is an order on these maps and which maps he is allowed to use is only the ones before a certain point in this order depending on the size of the input he is sent? Or, alternatively, some limitation how how quickly the maps can increase the size (or complexity?) of the string?