There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we weaken our notion of security from "impossible" to "it would take exponentially long to break" we get some other results. In How to Fool an Unbounded Adversary with a Short Key Russel and Wang show how to encrypt high entropy messages using a small symmetric key such that we can safely conclude that an adversary would have to perform an exponential number of steps to decide anything about our message. This is a problem because most of the messages I send are quite predictable. This caveat is always mentioned when I see entropic-security mentioned. It seems to me that there exists a way to encrypt messages of low entropy using this method, however.

Solution: Alice wants to send $M \in \{0, 1\}^n$ to Bob. Alice and Bob have agreed on $K_\mbox{rw} \in \{0, 1\}^{\ell + 128}$ as a key to be used in Russel ang Wang's entropically secure encryption algorithm. Alice generates a one-time pad $K \in \{0, 1\}^n$ by sampling from a uniform distribution. Alice encrypts $K$ using $K_\mbox{rw}$ and sends the results Bob. Bob now knows $K$. Alice now encrypts $M$ using $K$ and sends it to bob. Bob uses $K$ to decrypt the message and now Bob knows $M$.

$K$ would have maximal entropy and thus would meet Russel and Wang's requirement. The second message gives no information about $K$, $M$, or $K_rw$ and thus can't be used to attack the original message (At least that's how I understand it).

The only downside I can see to it is that it requires sending twice the amount of information you'd otherwise have to send but for many applications that's quite acceptable. This would seem to imply that Russel and Wang's method is far more widely applicable. You likely wouldn't use this method for video streaming but you might very well use it for sending information to your bank or you might use it for browsing the web.

The lack of mention of this a) In their paper, b) on Wikipedia and c) in a couple other papers that cite Russel and Wang that I've skimmed leaves me thinking that I've overlooked something. Is there a security issue that I've overlooked? Is this method or something equivalent/better mentioned somewhere else? Are there any other drawbacks that I'm not seeing? Even if I've done something wrong here then is something like this still possible? Specifically, can we use Russel and Wang's algorithm to encrypt low entropy messages by sending some extra information drawn from a high entropy source (as I believe my "solution" does)?


1 Answer 1


Here is the problem: if $M$ has low entropy (for example, if the attacker has side information that narrows $M$ down to just two possible messages), then conditioned on $M+K$, the key $K$ also has low entropy (there are only two possibilities for $K$). If the eavesdropper stores the first message (which was an encryption of $K$), then she can use it to figure out which of the two candidate values for $K$ is plausible (i.e. is consistent with some short key $K_{RW}$) once she sees the second message.

This problem is essentially unavoidable: taken together, the two messages form an encryption of $M$ (the fact that they were sent separately doesn't affect a passive eavesdropper who sees both). It is easy to show that, using only a short key, one cannot achieve even Russell and Wang's relaxed notion of security in a setting where $M$ has low entropy.

For a lower bound on the key length (as well as further constructions), see Dodis and Smith: https://eprint.iacr.org/2004/219 [Disclaimer: I am an author.]

  • 1
    $\begingroup$ Fantastic answer! I was worried I was misunderstanding something pretty fundamental. $\endgroup$
    – Jake
    Commented Dec 22, 2017 at 21:16

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.