[Cryptography] State of sin (was Re: What to put in a new cryptography course)

[Ron Garret]

On Jul 27, 2016, at 9:16 AM, Ray Dillinger <bear at sonic.net> wrote:

> If an "attack" presupposes the application of brute force,
> that's not an indication that a cipher is insecure. That's a
> secure cipher functioning as intended.

You didn’t include any context so it’s hard to know exactly what you’re referring to here, but I think you’re attacking a straw man.  All of the references to brute-force in this discussion have been to brute-force searches for *algorithms*, not brute-force searches for keys.

The argument has gone like this:

Arnold: We should not be content with the lack of proofs of security.

Me: We may have no other choice unless (and here I insert my tongue slightly into my cheek) we first make progress on P?=NP

Arnold: P?=NP is irrelevant because crypto algorithms are not NP-hard

Me: P?=NP is relevant not because crypto algorithms are NP-hard (Arnold is right — they aren’t) but because finding a *proof* might be impossible without a conceptual breakthrough of a similar magnitude to answering P?=NP.

Arnold: Finding a proof cannot possibly be NP-hard either.  In fact, there is a *finite procedure* for finding a proof: simply enumerate all possible algorithms that halt in time <N where N is the cost of a brute-force attack and see if any of them break the cipher with probability greater than chance.  (N.B.: not only do you have to enumerate all algorithms, but you have to run them all against all possible keys.  But it’s all finite, so we’re in FSA-land, not Turing-land, and so everything is decidable.)

Me: That this procedure is finite is irrelevant.  This universe is also finite in both time and space (assuming our current understanding of physics and cosmology is correct).  You can do the math if you want to, but I guarantee you that finding a proof of security by brute force in this universe is completely hopeless.  Finding a proof by some other means may or may not be hopeless, we just don’t know.  The fact that we don’t know might be a result of our complacency, but it might be a consequence of the laws of physics.  We don’t know that either (that’s really the P?=NP question).  You can lather-rinse-repeat that line of reasoning to generate an infinite tower of ignorance and meta-ignorance and meta^N-ignorance.  Breaking that cycle probably requires, at the very least, a conceptual breakthrough unrivaled in the history of human intellectual endeavor.

This is not to say that people ought not to look for proofs of security.  If proofs are your thing, more power to you.  I wish you all success.  All I’m saying is that people ought not to be admonished for considering the above argument and then deciding to direct their efforts elsewhere.

rg