Information theory — the discipline that gave us digital communication and data compression — also put cryptography on a secure mathematical foundation. Unfortunately, as a group of researchers at MIT and the National University of Ireland (NUI) at Maynooth, demonstrated in a paper presented at the recent International Symposium on Information Theory, that assumption is false.
“We thought we’d establish that the basic premise that everyone was using was fair and reasonable,” says Ken Duffy, one of the researchers at NUI. “And it turns out that it’s not.” On both papers, Duffy is joined by his student Mark Christiansen; Muriel Médard, a professor of electrical engineering at MIT; and her student Flávio du Pin Calmon.
The problem, Médard explains, is that information-theoretic analyses of secure systems have generally used the wrong notion of entropy. But in cryptography, the real concern isn’t with the average case but with the worst case. A codebreaker needs only one reliable correlation between the encrypted and unencrypted versions of a file in order to begin to deduce further correlations. In the years since Shannon’s paper, information theorists have developed other notions of entropy, some of which give greater weight to improbable outcomes. Those, it turns out, offer a more accurate picture of the problem of codebreaking.
Read more here…