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

[Ron Garret]

On Jul 26, 2016, at 10:01 AM, Arnold Reinhold <agr at me.com> wrote:

> 
>> 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> 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.

And this is indeed the case.  It might not be formally undecidable in principle, but it might be actually undecidable under the physical or economic constraints of this universe.

> 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.  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.

>> 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.

You’re attacking a straw man here.  I never said that it would.

rg

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