[Cryptography] End-to-End, One-to-Many, Encryption Question

[Jerry Leichter]

On Jun 13, 2014, at 9:46 AM, Phillip Hallam-Baker <phill at hallambaker.com> wrote:
> ...It is a similar problem with public key, people thought that an np-complete problem would make a good cipher till other folk showed that heuristic approaches break them.
No one who understands the theory ever proposed NP-completeness as a certificate of good-quality cryptography.  (That doesn't mean many who don't understand the problems aren't all too happy to spout off about how a solution to some *different* problem makes for a great cryptosystem.)

The problem, of course, is that NP-hardness is a measure of the *most difficult* problems in some set.  It's not even a measure of the *average* difficulty - and even if you knew that the *average* difficulty was high, when you do cryptography, you're relying on the the difficulty of *some particular instance*, and if it turns out not to be one of the hard ones, you're dead.

Suppose it were found that one in a million AES keys is "weak" in the sense that encryption under those keys requires only 2^40 effort to break - but there was no way to tell, without expending that effort, whether a key is one of the weak ones.  In just about every area of technology, odds like that would be considered fantastically good.  But for a cryptosystem ... they would render AES unacceptable in any serious use.

The distinctions here apply much more broadly than just to cryptography, BTW.  Suppose you're concerned about the perceived service time of some Web service.  The first (and in all too many cases the only) idea many people have for improving service time is "cache stuff".  Which is great as far as it goes, but a cache by its very nature can only improve *average* service time.  Except in very specialized circumstances, it does nothing about maximum service time, and it does very little about, say, 95th percentile service time.  But if you're talking about *perceived* service time, having a good average but a big delay 1 in 20 times is very bad.
                                                        -- Jerry


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140613/4269f474/attachment.html>