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

[Ron Garret]

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

The reason P?=NP matters is not because we want crypto algorithms that are in NP.  The reason that it matters is that what you asked for is not an *algorithm* but a *proof*:

> The lack of mathematical *proofs* for the security of cryptographic primitives is a reality with which the cryptographic community is perhaps too comfortable

(Emphasis added)

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

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.  For a reference, see:

http://www.scottaaronson.com/papers/npcomplete.pdf

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.”
> 
> But it would indicate even more. If such a procedure existed, then we could quickly find the smallest Boolean circuits that output (say) a table of historical stock market data, or the human genome, or the complete works of Shakespeare. It seems entirely conceivable that, by analyzing these circuits, we could make an easy fortune on Wall Street, or retrace evolution, or even generate Shakespeare’s 38th play. For broadly speaking, that which we can compress we can understand, and that which we can understand we can predict. Indeed, in a recent book [12], Eric Baum argues that much of what we call ‘insight’ or ‘intelligence’ simply means finding succinct representations for our sense data. On his view, the human mind is largely a bundle of hacks and heuristics for this succinct-representation problem, cobbled together over a billion years of evolution. So if we could solve the general case—if knowing something was tantamount to knowing the shortest efficient description of it—then we would be almost like gods. The NP Hardness Assumption is the belief that such power will be forever beyond our reach.


rg