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

[Arnold Reinhold]

> On Jul 23, 2016, at 11:25 AM, Ron Garret <ron at flownet.com> wrote:
> 
> 
> On Jul 22, 2016, at 10:00 AM, Arnold Reinhold <agr at me.com <mailto:agr at me.com>> wrote
…
>> Given that I have just proven that searching for efficient solutions is finite, I don’t see how Turing equivalence comes into play at all. The only question is whether there are more efficient search methods and will they find anything better than brute force.
> 
> I’ve tried to explain this twice now, I’ll try one more time.
> 
> There are two distinction questions on the table:
> 
> 1.  Given a cryptographic algorithm, does an attack exist?
> 
> 2.  Can we *prove* that the answer to question 1 is “no”?
> 
> Question 2 can be interpreted in two different ways:
> 
> 2a.  Can we *in principle* prove that the answer to question 1 is “no”?
> 
> 2b.  Can we actually generate such a proof under contemporary physical, technological and economic constraints?
> 
> The answer to question 2a is obviously “yes” because, as you say, the problem is finite and we can in principle enumerate all the possibilities.  But no one in their right mind cares about this.  What matters is whether someone anyone can *actually* attack your algorithm.  I don’t care if God knows how to attack my crypto, I care if there’s a *human* who knows how to attack my crypto.

In a previous post, you suggested that one answer to 2 might be that the question is undecidable. 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.)

> 
> All else being equal I would, of course, love to have a proof that even God cannot attack my crypto.  But all else is not equal.  We live in a world with constraints, and we have to decide how to allocate limited resources.  Should we spend our effort looking for proofs, or should we spend it doing something else?
> 
> It is *that* decision which can be informed by the theory of Turing machines because proofs are Turing-complete.  And, BTW, it is *that* decision that could be informed by an answer to the question of whether not P?=NP because that answer would almost certainly contain some deep conceptual breakthrough. Because of the deep connection between this question and proof theory, it would almost certainly give us some insight into how to make the quest for a proof more fruitful, or tell us that the effort is indeed hopeless.  

> At the moment we just don’t know, and so there is no principled basis for making these decisions.  All we have are some data points with no theory.  Under those circumstances, everyone needs to choose their own risk posture.

I agree, and have said so before, that machinery developed to answer P=?NP could perhaps lead to insights on how to verify the security of cryptographic algorithms. However the central technique currently used in the study of Turing machines, the diagonal method, relies on the infinite nature of the problems. But no one can say with confidence what a yet-to-be-discovered mathematical method could or could not do. What I strongly disagree with is the widely stated belief that a proof that P=NP would, by itself, invalidate current cryptographic methods.

Arnold Reinhold

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