0
$\begingroup$

I have a 256 bit string (indistinguishable from random) which I wish to encode into a greater length string using an error correction code.

The result must also be indistinguishable from random. It should not be possible to detect the presence of error correction from the result.

Is it possible? And if so, how?

PS: Related: https://crypto.stackexchange.com/questions/80890/error-correcting-codes-that-are-indistinguishable-from-random

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Please define the threat model and what is known to the sender, the recipient, and the adversary. For instance, can the sender and recipient choose a random code that they both know but the adversary does not? $\endgroup$
    – D.W. ♦
    May 24, 2020 at 5:46
  • 1
    $\begingroup$ (It would, of course, be possible to first use error correction coding followed by encryption, and after flawless transmission/storage & decryption, errors could be detected/corrected: better clarify the role using an error correction code is to play.) $\endgroup$
    – greybeard
    May 24, 2020 at 7:26
  • $\begingroup$ @D.W. The program that chooses and encodes the string is public, an adversary can examine it and trivially forge his own messages. He must not however be able to confirm that an intercepted message was made by it. $\endgroup$
    – Jack Fleming
    May 24, 2020 at 13:35
  • $\begingroup$ @greybeard This is in fact how the message is handled (a stream cipher whitens it hiding any error correction) but the ephemeral public key cannot be encrypted - the program is public. So error correction must be used on it raw and its presence has to be hidden. $\endgroup$
    – Jack Fleming
    May 24, 2020 at 13:37
  • $\begingroup$ What kind of corruptions must the ECC handle? $\endgroup$
    – Dmitri Urbanowicz
    Jul 24, 2020 at 7:05

3 Answers 3

Reset to default
1
$\begingroup$

One natural approach is to apply the error-correcting code, then encrypt the codeword with a stream cipher (e.g., AES-CTR mode). The recipient can decrypt (this will not increase the number of bits with an error), then decode the code to correct any errors. Anyone who does not know the symmetric key will be unable to distinguish the transmitted ciphertext from a random string.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is not an option. Anyone intercepting the message would be expected to know the encryption key because the program that does it is public. The linked question explains this. $\endgroup$
    – Jack Fleming
    May 24, 2020 at 17:14
  • 4
    $\begingroup$ @JackFleming, please edit your question to state the requirements and threat model more clearly. Tell us what solutions you've already considered and rejected and why, so we don't waste our time suggesting obvious solutions. I asked once for a clear statement of the threat model and didn't understand your response, so I took a guess at what you might be asking; apparently I guessed wrong. I don't think I'll try that again. I encourage you to make your question self-contained, and don't just leave comments -- edit your question. $\endgroup$
    – D.W. ♦
    May 24, 2020 at 17:23
1
$\begingroup$

Encrypting an error-correcting code does not, in general, result in an error-correcting code. So that approach is probably a non-starter.

On top of what everyone else has said, I don't see how error correcting codes can be indistinguishable from randomness for most reasonable definitions of "indistinguishable". The whole point, after all, is that encoded messages are not equally likely; uncorrupted messages are more likely than corrupted ones.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Not more or less likely, but corrupted codes are corrupted and uncorrupted ones are not. $\endgroup$
    – gnasher729
    Nov 21, 2020 at 10:35
1
$\begingroup$

What you are asking for: You want transformations T and T’, such that X = T(S) is undistinguishable from random, T’(X) = S, and if X’ = X with few random bit errors, then T’(X’) = S as well.

But strings with errors can be distinguished: If A has no errors, then adding some random bit changes leaves T’(A) unchanged. If A already contains errors, then fewer random bit changes are needed to change T’(A).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.