Is deniable error-correction possible? This question came up as I tried to answer an earlier question I asked: Cryptographic data structure: sparse array without membership test.  I still have not resolved that question to my satisfaction, but this question may be appreciated independently.

I want an error-correcting code that has the additional property that when encoding a string that cannot itself be feasibly distinguished from a random string, the encoding cannot be feasibly distinguished from a random string either.  So, for example, Alice could generate a random 1000 bit string, encode it using the algorithm to get a 2000 bit string, and send it over a noisy channel to Bob.  Bob could recover Alice's original 1000 bit string (even if there were many corrupted bits) but would have no way of knowing that Alice did not just send a random 2000 bit string.

I realize that "deniable" may not be the best word to use for this property since this word already has a different technical use in cryptography.  But I am not sure what to call the property.

Also, are there any tags I should be using besides "algorithm-design"?  For both my previous question and this one, I felt that there was no completely appropriate tag.
Here's an approach that corrects some errors:


Alice has a bitstring S that is indistinguishable from random that she wants Trent to know. (Perhaps it's actually a ciphertext that only Bob knows how to decrypt).
Alice generates 5 fresh new random bit-strings pM, pN, pP, pQ, and pR just as long as the original random bitstring S.
For each bit of S, Alice checks the the corresponding 5 bits of the random strings pM, pN, pP, pQ, and pR. If the majority of those 5 bits is the same as S, Alice keeps that bit the same, otherwise Alice flips all 5 bits, generating 5 modified versions of those random strings M, N, P, Q, and R.
Alice sends M, N, P, Q, and R to Trent.
For each bit of the messages M, N, P, Q, and R, Trent uses 5-modular redundancy -- the majority of the 5 bits -- to attempt to recover the string S.


Because pM, pN, pP, pQ, and pR are completely randomly generated, and S is indistinguishable from random, Trent is still unable to distinguish M, N, P, Q, and R from random bit-strings.

For any one bit-position, the 5 bits can be in any one of 32 possible patterns with equal probability.
If there is no bit error in some particular position, Trent always recovers the correct bit of S at that position.
Trent can usually correct any single-bit-flip error across a row of 5 bits.
(Given any 1 of the 5 bit positions ahead of time that will suffer a single-bit-flip error, 20 of the 32 possible patterns result in Trent recovering the correct bit of S, but the remaining 12 possible patterns would result in Trent decoding an erroneous bit).

I suspect there is a better encoding that allows Trent to always correct any single-bit-flip error.
Perhaps somehow forbidding the 12 vulnerable patterns, even though that allows statistical tests to conclude the collection of strings M, N, P, Q, and R are not completely random?