TransWikia.com

Undetectable error correcting codes

Computer Science Asked by Jack Fleming on December 21, 2021

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

3 Answers

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).

Answered by gnasher729 on December 21, 2021

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.

Answered by Pseudonym on December 21, 2021

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.

Answered by D.W. on December 21, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP