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

[Arnold Reinhold]

> On Jul 12, 2016, at 12:05 PM, Ron Garret <ron at flownet.com> wrote:
> 
> 
> On Jul 12, 2016, at 4:37 AM, Arnold Reinhold <agr at me.com> wrote:
> 
>> 
>>> On Jul 11, 2016, at 2:23 PM, Ron Garret <ron at flownet.com> wrote:
>>> 
>>>> 
>>>> The lack of mathematical proofs for the security of cryptographic primitives is a reality with which the cryptographic community is perhaps too comfortable.
>>> 
>>> Unless someone manages to prove that P != NP we have no other choice but to make our peace with this.
>> 
>> P vs. NP has nothing to do with cryptography. Nothing. I wrote a rant on this over two decades ago (http://theworld.com/~reinhold/p=np.txt). Give me an encryption algorithm whose difficulty grows as (key size)^20 (i.e. polynomial time) and I can pick a reasonable key size that will not be crackable in the age of the universe.  And for that matter AES-256 is in P because it is solvable in constant time, it’s just a very big constant.
>> 
>> If that isn’t enough to convince you, consider this. The whole theory of NP-completeness is based on finding problems that are "NP-hard.” NP-hard just means that there exist examples of the problem into which you can embed a Turing machine and its program. The best example is Boolean-satisfiability. You can unwind any Turing machine into a giant Boolean expression in polynomial time. NP-competenss of NP-hard problems follows because for a problem, X, to be in NP there must exist a Turing machine program, testX, that can check any proposed solution of X in polynomial time.  If you can solve any NP-hard problem, Y, in polynomial time, then you can solve X in polynomial time by embedding its testX program in Y.  All very pretty and all dependent on the fact that polynomial-time is such an elastic equivalence relation: the product of two polynomials is another polynomial, but the degrees keep getting bigger and problems whose solution time is s high degree polynomial are intractable in practice.
>> 
>> Note that this theory is all about existence proofs: we find some example of the problem that can contains a Turing machine (or an arbitrary Boolean expression, which is usually much easier to show) and that problem gets the NP-hard stamp of approval. But that is no proof that all or even most examples of the problem are in any way difficult. And for cryptography we want assurance that our algorithms are strong in all cases, not just a sparse subset. 
>> 
>> We don’t know if factoring primes or finding discrete logs are NP-hard because no one has found enough structure in those problems to embed Turing machines. Suppose someone did. Then the problem would be officially NP-hard, but the newly discovered structure might nonetheless enable new attacks on practical sized problems. 
>> 
>> So the whole P vs NP theory has no bearing on cryptography.
> 
> It does have a bearing.  It is just not the straightforward one that you imply.  (That’s a very good explanation of P=NP, BTW, probably the best I’ve ever seen.)

Thank you.
 
> ...
> What you asked for is not a crypto algorithm whose complexity is X^20, what you asked for is a *proof* that there exists no algorithm that computes the same function in less than X^20.  Such a proof is a very different beastie than an algorithm.  (It’s actually even worse than that, because to prove security, proving that there is no equivalent algorithm is not enough.  You have to prove that there does not even exist a *probabilistic approximation* to the algorithm that runs in <X^20.)

That is basically what I understood I was asking for. If we could find such a proof, we could construct a crypto system that was provably strong even if it turned out that P=NP. 

> 
> In other words, you want proofs of optimality.  The question of whether such proofs are possible is much deeper than is generally appreciated.  A full discussion would be *way* beyond the scope of a mailing list post.  The point I want to make here is simply that the question of whether P=NP is germane to that discussion.  

While It is possible that new mathematical techniques developed to answer the P vs. NP question might, as a byproduct, show the way to proving some cipher algorithm is strong in the sense you mentioned, it is just as possible that some clever new approach to building strong ciphers could lead to a proof that P!=NP. Or our salvation might come from some other mathematical breakthrough. This relevance of P vs. NP to cryptography is tenuous at best.

> For a reference, see:
> 
> http://www.scottaaronson.com/papers/npcomplete.pdf

I finally made it through that paper. Thanks for the reference, it is an interesting read. I found this Aaronson quote pertinent: 
But what about the oft-repeated claim that asymptotic statements have no relevance for physical reality? This claim has never impressed me. For me, the statement “Max Clique requires exponential time” is simply shorthand for a large class of statements involving reasonable instance sizes (say 10^8) but astronomical lengths of time (say 10^80 seconds). If the complexity of the maximum clique problem turned out implausibly to be 1.000000001^n or n^10000, then so much the worse for the shorthand; the finite statements are what we actually cared about anyway. With this in mind, we can formulate the NP Hardness Assumption concretely as follows: “Given an undirected graph G with 10^8 vertices, there is no physical procedure by which you can decide in general whether G has a clique of size 10^7, with probability at least 2/3 and after at most 10^80 seconds as experienced by you.”
It seems to me that what Aaronson is asking for is not that different from what cryptographers would like to have, a proof that some cipher algorithm with key length n cannot be computed absent the key in, say, less than 2^(n/2 - epsilon) steps by any physical procedure . But we don’t need a proof that P!=NP to get there nor would the discovery that P=NP bar the existence of such a proof.

> 
> particularly the discussion in section 10.  Here is the TL;DR:
> 
>> Even many computer scientists do not seem to appreciate how different the world would be if we could solve NP-complete problems efficiently. I have heard it said, with a straight face, that a proof of P = NP would be important because it would let airlines schedule their flights better, or shipping companies pack more boxes in their trucks! One person who did understand was G ̈odel. In his celebrated 1956 letter to von Neumann (see [69]), in which he first raised the P versus NP question, G ̈odel says that a linear or quadratic-time procedure for what we now call NP-complete problems would have “consequences of the greatest magnitude.” For such an procedure “would clearly indicate that, despite the unsolvability of the Entscheidungsproblem, the mental effort of the mathematician in the case of yes-or-no questions could be completely replaced by machines.” ...
>> 

Note that Godel is asking for "a linear or quadratic-time procedure.” That is very different from being satisfied with a procedure in P. He is not endorsing the notion that P means “tractable" which so many computer science majors have been brainwashed into believing.

Arnold Reinhold

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