Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise

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

Asked by user21112 (1,131 )
Dec 22, 2017 at 00:59