10
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ From my limited understanding error correction is $m | e$ where $e$ is some extra data used to correct up to a portion of $m$. Assuming $m$ is encrypted, and thus indistinguishable from a random string, what benefit is to be gained from making $e$ also indistinguishable? Unless the scheme is studied for its own merit. $\endgroup$
    – rath
    Commented Sep 26, 2014 at 19:33
  • $\begingroup$ "cannot feasibly be distinguished from a random string cannot feasibly be distinguished from a random string"? $\endgroup$
    – user991
    Commented Sep 26, 2014 at 19:46
  • $\begingroup$ @rath It is not required that the message itself be an initial segment of the code, though some codes have that property. If you want a motivation, see my previous question. That question came from thinking about a practical problem. $\endgroup$
    – gmr
    Commented Sep 26, 2014 at 20:19
  • $\begingroup$ @Ricky If x looks random and y is the encoding of x then y looks random too. Hopefully the Alice/Bob example makes it clearer? $\endgroup$
    – gmr
    Commented Sep 26, 2014 at 20:20
  • $\begingroup$ @RickyDemer: you're parsing it wrong: "the encoding of a string (that cannot be distinguished from random) cannot be distinguished from random". He's asking if the encoding can be made indistiguishable (and the answer is easy if Alice and Bob share a secret) $\endgroup$
    – poncho
    Commented Sep 26, 2014 at 20:20

4 Answers 4

Reset to default
4
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, this does show that some error correction is possible. But arguably the hallmark of error-correcting codes is that for some transmission rate you can encode stuff with an arbitrarily low error rate, and I don't see any way to generalize your method to get that. $\endgroup$
    – gmr
    Commented Sep 28, 2014 at 5:54
  • $\begingroup$ @gmr, you could always apply it recursively, though the data size grows fast. $\endgroup$
    – otus
    Commented Sep 28, 2014 at 8:07
2
$\begingroup$

Take a look at the Fujisaki-Okamoto CCA2-Security conversion. This is what you need.

In short, this is a conversion that makes the ciphertext of the McEliece encryption scheme (which is based on error correction codes) to be indistinguishable from random.

Improve this answer
$\endgroup$
13
  • $\begingroup$ I looked up this conversion on the web. As far as I can discern, it is a general method for takes (1) a public key cryptosystem that is secure against chosen plaintext attacks but not necessarily chosen ciphertext attacks and (2) a symmetric key cryptosystem that is secure against chosen ciphertext attacks and gives you (3) a public key cryptosystem secure against chosen ciphertext attacks. I don't see the connection between this and my question. The question does not involve encryption at all. $\endgroup$
    – gmr
    Commented Sep 29, 2014 at 5:24
  • $\begingroup$ @gmr, I know your question has nothing to do with encryption scheme. The point is that this conversion makes a ciphertext indistinguishable from random. Now recall that the ciphertext of McEliece scheme is the encoding of the plaintext (with some errors), exactly as you described in your problem. In short, you just have to adapt the concept of McEliece+FujisakiOkamotoConversion to your context. Another good example of CCA2 secure conversion is the one proposed by Kobara-Imai. Take a look at this last one. It is completely focused on the McEliece scheme. (Y) $\endgroup$
    – mczraf
    Commented Sep 29, 2014 at 6:00
  • $\begingroup$ This idea looks really interesting, and I upvoted your answer, but I have not yet found time to really study the technologies the answer uses and convince myself that it works. Nonetheless, I will ask a question. Maybe this is obvious, but if Bob gets what is effectively a ciphertext, how can he unencode it without a key? Or if the key is made public, doesn't that break the indistinguishability from randomness property? $\endgroup$
    – gmr
    Commented Sep 30, 2014 at 0:08
  • $\begingroup$ Let's start from the beginning. The McEliece PK Enc. Scheme works as follows. Both priv. and pub. keys are descriptions of a single linear-code. The private description is a 'privileged' description which ables efficient error-correction. The public one just enables encoding (i.e. it can't correct errors). The idea of McEliece was to encode the plaintext and purposely add some errors. In other words, the 'challenge'of this cryptosystem is the ability of efficient correcting errors. But this scheme, as described above, has a problem. See below. $\endgroup$
    – mczraf
    Commented Sep 30, 2014 at 1:29
  • 1
    $\begingroup$ OK, it seems like we have had a gigantic misunderstanding. As I said in my first response to you, my question does not involve encryption at all. Not in any way. Just error-correction. Anyway, thanks for your time and sorry it was such a waste. $\endgroup$
    – gmr
    Commented Oct 2, 2014 at 7:16
1
$\begingroup$

In general, an error correcting code $C$ is simply a collection of codewords of a given length $n$ that meet some desired minimum (Hamming) distance properties. Any tell-tale structure that is present is not intrinsic to the error-correcting properties, it's there in order to ease encoding and decoding and to allow you to prove that the desired properties exist.

Since $C$ can be arbitrarily chosen, there is no way to tell if a single word is a member. If Trent sees a large number of messages (and let's assume he sees them before the noisy channel), he can see if the there is anything unusual about their distribution - that their minimum pairwise distance is larger than expected for that number of messages. The larger the minimum distance between codewords, the more quickly he can conclude (with statistical certainty) that such a scheme is in use.

This can be fixed by changing codes for each message based upon some pre-arranged scheme. Note that for any code $C$ the code $C_k = \{ c + k | c \in C \}$ is an error correcting code with the same power for any $k$. You can probably use a construct analogous to CBC mode to make this secure.

Part of your question seems to propose that Trent knows $C$ but only sees the data after it has passed over the noisy channel. His ability to detect if the error correcting code was used will depend on the channel. At one extreme, if it never corrupts data, he'll always be able to tell whether the sent message is in $C$. In general, this is going to depend on the balance of $d$, the error correcting ability of the code, and the noise properties of the channel. Alice will want $d$ large enough to correct expected errors, but the larger it is the more distinguishing power Trent has.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, @bmm6o. On "Since $C$ can be arbitrarily chosen, there is no way to tell if a single word is a member", are you thinking that the attacker Trent would not know what code is in use but the intended recipient Bob would? Because that is not the setup. No one other than the sender Alice knows anything anyone else doesn't. On "he can see if there is anything unusual about their distribution", the question was about a single message, but even if we allow multiple messages, it isn't clear to me that this gives up information, so long as the number of messages is not astronomical, $\endgroup$
    – gmr
    Commented Oct 2, 2014 at 3:19
  • $\begingroup$ especially if the code need not be optimal. On "At one extreme, if it never corrupts data, he'll always be able to tell whether the sent message is in $C$", I think there is an ambiguity in the idea of "knowing $C$". $C$ will be far too large to know by having a list of list members. Also, a separate point is that it just isn't true that you need to know what code is in use to be able to recover encoded words; approximate knowledge of the code can suffice with high probability. $\endgroup$
    – gmr
    Commented Oct 2, 2014 at 3:31
  • $\begingroup$ Given a set of words $W$ and the noise profile of the channel it's easy to calculate the probability that some received message $w'$ was originally broadcast as a word in $W$. That seems too simple, but I don't see any other way to interpret your question if nothing is secret and there's only 1 message sent. $\endgroup$
    – bmm6o
    Commented Oct 2, 2014 at 20:41
  • $\begingroup$ Let me say a number of independent things, some of which you may already know and/or may not matter to the argument you are making. The sender (Alice) can have secrets. The probability is only determined given a distribution over what was sent. It is not required that the sender always encode the same word in the same way. The calculation you describe will not necessarily be feasible. The last comment I wrote to @otus may clarify things. $\endgroup$
    – gmr
    Commented Oct 3, 2014 at 0:42
0
$\begingroup$

I'm assuming your deniability/indistinguishability definition requires a random piece of data and a error correcting piece of data to look the same to a decoder, because that seems like a requirement in the application you linked. In that case any error-correcting code that can fix all one bit errors is necessarily distinguishable from random data. Sketch of proof:

Suppose you have an indistinguishable ECC capable of correcting all one bit errors. Encode some message using it. That code and all the codes that differ from it by one bit must produce the same message when decoded. However, the same cannot be true for all the modified messages, or else the ECC is capable of correcting all two bit errors. Apply induction to show that it means it must correct n-bit errors, which is impossible in general. A random piece of data has a chance of being one of those "corrupted codes", so it can be distinguished by seeing if all the one bit changes get fixed or not.

A scheme such as that detailed in David Cary's answer is probably the best you can do.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The issue is whether you can partition the $n$ bit strings into a large number of classes in such a way that few strings have small Hamming distance from a string in a different class. Maybe there is a simple combinatorial argument that this is impossible, but I can't see it. If you don't know the answer, maybe I should just ask on Math Stack Exchange. I'm basically 100% sure that the answer is known and the proof is simple. $\endgroup$
    – gmr
    Commented Oct 2, 2014 at 15:48
  • $\begingroup$ @gmr, yes, perhaps you should ask on math.se. Intuitively it seems clear that the proportion of non-correctable strings it not negligible. $\endgroup$
    – otus
    Commented Oct 3, 2014 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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