4 ms·

for some reason, this reminds me of this question that occured to me. How could we design some sort of error correction/encryption algorithm which makes the inf

by bsedlm 5y ago

for some reason, this reminds me of this question that occured to me. How could we design some sort of error correction/encryption algorithm which makes the information impossible to encrypt. If we consider error correction to be the capacity for a message to resist errors, and encryption as the design of reversible error for any possible message (to add the error is to encrypt and to remove it is to decrypt). Then, how can we make an error correction scheme so good that a message encoded with it can be error corrected back into the original regardless of how the encoded message is encrypted?

drdeca 5y ago
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?
- bsedlm 5y ago
  >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" ? yes, but in such a way that the original message is recoverable even if it gets encrypted. I should have said, that I'm thinking classically and that I'm thinking about key-based encryption, i.e. no one-time pads and the key has to be smaller than the message. > 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 ? Yea, I think this may be unavodiable in any way this is done. The encoded message will be much bigger than the plain text. Which also makes it reasonable to expect this to work only against key-based cyphers. I don't undesrtand why you compare the complexity of the message and the complexity of the machines doing the cyphering (either en- or de-cryption), but regardless, thanks for the response.
  - PeterisP 5y ago
    The key issue here is that it really has to be much bigger, merely a hundred times or million times bigger is definitely not going to be sufficient. There indeed is a limitation of key-based algorithms that encrypting too many blocks with a certain structure may make them vulnerable; however, that limitation is quite large unless you're using older/smaller algorithms like DES. I couldn't remember or quickly find what the circumstances are for e.g. AES-128 but IIRC it might be something like 2^48 blocks so for your approach to work, you'd have to stretch each block of content (e.g. 16 bytes) into petabytes of encoded data before you start having a theoretical chance to decode it; and for AES-256 it would probably be that amount squared, and you simply can't encode or store 2^96 blocks of anything.
anyfoo 5y ago
Encryption does not "add", like error/noise, it translates. The signal-to-noise ratio stays the same. Another way do describe it is that error correction creates resistance against (effectively) some upper boundary of error/noise. It does that by essentially multiplying the signal so that (with a still constant error) it increases the effective SNR , as that is just signal divided by error. It cannot work if you have 100% noise and 0% signal (it's intuitive why, and 0 multiplied by x is still 0). A good encryption scheme however (pretty much any common one that isn't a toy) has the goal of making the signal look entirely random for anyone without the proper algorithm and secret to reverse. With an effectively 0 SNR to that observer, there is no signal to boost. Noise/error is random, if it wasn't it would be reversible and not need any error correction techniques that effectively reduce bandwidth. Encrypting, however, is not random at all, it is entirely deterministic, making it intentionally reversible.
jerf 5y ago
You'd need to cleverly narrow down the definition of "encrypted" you're operating under. The broad definition allows me to take your message and essentially turn it into any sequence of bits of sufficient length, and there's no way for you to then layer any further restrictions on top of that sequence because of the near-arbitrary power I have in selecting my encryption scheme. You'd need to reduce that power in some way to then create even a subset of messages that could survive the encryption. Such a result would probably be of no practical use but it could be interesting in a recreational mathematics sort of way.
- bsedlm 5y ago
  > You'd need to cleverly narrow down the definition of "encrypted" you're operating under. absolutely. I suppose I should have explained that I'm thinking of "practical key-based symmetric(?) encryption", i.e. ecryption which hinges on a key which gets "expanded" by some clever (and aribtrary) algorithm into enough bits for any message; and which (it goes without saying) can be decrypted back exactly given a key and an algorithm (the same ones or at least very similar ones if symmetric). I'm not knowledgeable enough in cryptography to easily consider the assymetric case; but I don't think symmatric-asymmetrica changes things that much.
  - jerf 5y ago
    In that case you can encrypt your message by considering it as one big number, and creating a message long enough to encrypt to that many blocks. Inefficient in this particular case, but there are length-related attacks, so it's at least not crazily out of the domain of discourse. But I had to wait for you to qualify it that way, because if someone knows this is your plan, they can compensate with an "encryption" scheme that counters the approach.
oh_sigh 5y ago
This sounds like the irresistible force paradox, in that it is only a paradox if one allows for arbitrary definitions of error correction or encryption.
a1369209993 5y ago
> can we make an error correction scheme so good that a message encoded with it can be error corrected back into the original regardless of how the encoded message is encrypted? No. Preventing this is called IND-CPA (indistiguishability under chosen plaintext attack) security and is basically table stakes for any modern symmetric encryption algorithm. In fact this is even weaker than IND-CPA, since in IND-CPA the attacker can first observe arbitrarily many other plaintexts and use the resulting information to choose two (non-yet-seen) plaintexts specific to the particular encryption algorithm and key to try to distinguish, and they don't have to be sure which is which, only to do significantly better than chance.

by bsedlm 5y ago

drdeca 5y ago

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?

bsedlm 5y ago
>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" ? yes, but in such a way that the original message is recoverable even if it gets encrypted. I should have said, that I'm thinking classically and that I'm thinking about key-based encryption, i.e. no one-time pads and the key has to be smaller than the message. > 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 ? Yea, I think this may be unavodiable in any way this is done. The encoded message will be much bigger than the plain text. Which also makes it reasonable to expect this to work only against key-based cyphers. I don't undesrtand why you compare the complexity of the message and the complexity of the machines doing the cyphering (either en- or de-cryption), but regardless, thanks for the response.
- PeterisP 5y ago
  The key issue here is that it really has to be much bigger, merely a hundred times or million times bigger is definitely not going to be sufficient. There indeed is a limitation of key-based algorithms that encrypting too many blocks with a certain structure may make them vulnerable; however, that limitation is quite large unless you're using older/smaller algorithms like DES. I couldn't remember or quickly find what the circumstances are for e.g. AES-128 but IIRC it might be something like 2^48 blocks so for your approach to work, you'd have to stretch each block of content (e.g. 16 bytes) into petabytes of encoded data before you start having a theoretical chance to decode it; and for AES-256 it would probably be that amount squared, and you simply can't encode or store 2^96 blocks of anything.

anyfoo 5y ago

Encryption does not "add", like error/noise, it translates. The signal-to-noise ratio stays the same. Another way do describe it is that error correction creates resistance against (effectively) some upper boundary of error/noise. It does that by essentially multiplying the signal so that (with a still constant error) it increases the effective SNR , as that is just signal divided by error. It cannot work if you have 100% noise and 0% signal (it's intuitive why, and 0 multiplied by x is still 0). A good encryption scheme however (pretty much any common one that isn't a toy) has the goal of making the signal look entirely random for anyone without the proper algorithm and secret to reverse. With an effectively 0 SNR to that observer, there is no signal to boost. Noise/error is random, if it wasn't it would be reversible and not need any error correction techniques that effectively reduce bandwidth. Encrypting, however, is not random at all, it is entirely deterministic, making it intentionally reversible.

jerf 5y ago

You'd need to cleverly narrow down the definition of "encrypted" you're operating under. The broad definition allows me to take your message and essentially turn it into any sequence of bits of sufficient length, and there's no way for you to then layer any further restrictions on top of that sequence because of the near-arbitrary power I have in selecting my encryption scheme. You'd need to reduce that power in some way to then create even a subset of messages that could survive the encryption. Such a result would probably be of no practical use but it could be interesting in a recreational mathematics sort of way.

bsedlm 5y ago
> You'd need to cleverly narrow down the definition of "encrypted" you're operating under. absolutely. I suppose I should have explained that I'm thinking of "practical key-based symmetric(?) encryption", i.e. ecryption which hinges on a key which gets "expanded" by some clever (and aribtrary) algorithm into enough bits for any message; and which (it goes without saying) can be decrypted back exactly given a key and an algorithm (the same ones or at least very similar ones if symmetric). I'm not knowledgeable enough in cryptography to easily consider the assymetric case; but I don't think symmatric-asymmetrica changes things that much.
- jerf 5y ago
  In that case you can encrypt your message by considering it as one big number, and creating a message long enough to encrypt to that many blocks. Inefficient in this particular case, but there are length-related attacks, so it's at least not crazily out of the domain of discourse. But I had to wait for you to qualify it that way, because if someone knows this is your plan, they can compensate with an "encryption" scheme that counters the approach.

oh_sigh 5y ago

This sounds like the irresistible force paradox, in that it is only a paradox if one allows for arbitrary definitions of error correction or encryption.

a1369209993 5y ago

> can we make an error correction scheme so good that a message encoded with it can be error corrected back into the original regardless of how the encoded message is encrypted? No. Preventing this is called IND-CPA (indistiguishability under chosen plaintext attack) security and is basically table stakes for any modern symmetric encryption algorithm. In fact this is even weaker than IND-CPA, since in IND-CPA the attacker can first observe arbitrarily many other plaintexts and use the resulting information to choose two (non-yet-seen) plaintexts specific to the particular encryption algorithm and key to try to distinguish, and they don't have to be sure which is which, only to do significantly better than chance.