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

[Arnold Reinhold]

> On Jul 26, 2016, at 2:09 PM, Ron Garret <ron at flownet.com> wrote:
> 
> 
> On Jul 26, 2016, at 10:01 AM, Arnold Reinhold <agr at me.com <mailto:agr at me.com>> wrote:
...
> 
>> I attempted to show that for a fixed size block cipher there exists a finite (tho entirely impractical) algorithm for finding all possible attacks and that therefore the the question is not undecidable. I’m glad you now agree that this is obvious. (I believe my argument can be extended to discrete log public key systems by replacing the code book with a table of logarithms as a finite upper bound for the size of Turing machines to search.)
> 
> Yes, obviously all finite problems are decidable in principle.  Why do you think that’s relevant?  Formal decidability is not the issue here.  

You were the one who suggested that the security of cryptographic algorithms might be undecidable in the formal sense, pointing us to Aaronson's blog with an example of a formally undecidable Turing machine with just a few thousand states.  

> The issue is whether or not it is worth spending scarce resources looking for proofs.  Just because a question is formally decidable doesn’t mean it’s worth pursuing the answer.  The question of whether or not the Goldabch conjecture is true for all even integers less than Graham’s number is formally decidable, but it would be the very definition of foolishness to pursue the answer in the straightforward way.

The fate of nations has depended on the security of cryptography in the past and maybe depends on it even more so today. We currently spend scarce resources on far less practical questions than finding cryptographic systems that are provably secure.

>> 
>>  ... What I strongly disagree with is the widely stated belief that a proof that P=NP would, by itself, invalidate current cryptographic methods.
> 
> You’re attacking a straw man here.  I never said that it would.
> 

I never said you did. I said it was a "widely stated belief.” Here are quotes from the Clay Mathematics Institute’s Official Description of the P Versus NP Problem http://www.claymath.org/sites/default/files/pvsnp.pdf by Stephen Cook:

"The security of the Internet, including most financial transactions, depends on complexity-theoretic assumptions such as the difficulty of integer factoring or of breaking DES (the Data Encryption Standard). If P = NP, these assumptions are all false.” ... "Even if P != NP it may still happen that every NP problem is susceptible to a polynomial-time algorithm that works on “most” inputs. This could render cryptography impossible…”

Cook, who with Leonid Levin, was the first to state the P vs NP problem, and the Clay Mathematics Institute are hardly straw men.

Arnold Reinhold

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