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

Ron Garret ron at flownet.com
Fri Jul 15 19:58:19 EDT 2016


On Jul 15, 2016, at 2:57 PM, Arnold Reinhold <agr at me.com> wrote:

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

Yes, all true.  I confess I was being a bit glib.  Let me try this again.

You want a proof of security.  Just trying to write down what the *claim* would look like formally is tricky, but I don’t want to get lost in those weeds.  Lets just presume that we can formulate some formal property of an algorithm A that we call SEC which conforms to what we want.  If SEC(A) is true, algorithm A is secure.

So there are four possibilities with respect to any particular algorithm A:

1.  SEC(A) is false (and hence, obviously, no proof exists)

2.  SEC(A) is true but nonetheless no proof exists.  (Godel sentences are not necessarily the only unprovable truths.)

3.  SEC(A) is true, and a proof exists, but we can’t find it because it’s too big to fit in the observable universe, or too long to enumerate before the heat death of the universe, or something else fundamental like that

4.  SEC(A) is true, a proof exists, and it is feasible for us to find it (by which I mean that writing the proof down would not violate the known laws of physics, not that it is within the mental capacity of humans to find it)

If what you care about is security then any of these situations is acceptable except #1.

So let’s go back to your original statement:

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

I took this to mean: we should work harder on finding proofs of security so that we don’t discover the hard way that we are in situation #1.

But even in situation #1 there are three possibilities

1a.  SEC(A) is false, and hence an attack exists, but it is not feasible for us to find it

1b.  SEC(A) is false, and an attack exists, and it is feasible for us to find it, but it isn’t a practical attack because the attack is still too expensive to actually carry out

1c.  SEC(A) is false, an attack exists, it is feasible to find, and it is practical

Again, if what you care about is security, then any of these situations is acceptable except 1c.

So what we are talking about here is not so much *being* secure as *knowing* we are secure (or at least knowing we are immune from a certain class of nasty surprises.  A proof won’t protect you from a monkey-wrench attack.)

There are three possible reasons we don’t have proofs:

1-3. We are not in situation 4
4a.  A proof exists, finding it would not violate the laws of physics, but finding it is infeasible given our current mental and technological limitations
4b.  A proof exists and we can find it, we just haven’t tried hard enough

Your admonition that "the cryptographic community is ... too comfortable” with the absence of proofs is only constructive in situation 4b.  We don’t know whether or not we are in situation 4b.  One way to find out is to try to find proofs.  If we succeed, then obviously we are in 4b, but if we fail (the situation we are in fact facing) then what?  Should we just keep trying, or should we perhaps re-focus our efforts to try to ascertain if perhaps we are in some situation other than 4b (like, maybe 1c)?

The quip about someone finding a proof that P!=NP was really intended to be a shorthand (or maybe a metaphor) for someone making a major breakthrough in this kind of meta-mathematical problem of ascertaining whether or not a proof of the kind you are calling for is even possible.  The point I was trying to make was simply that until and unless someone makes *that* kind of a breakthrough we may have no choice but to make our peace with having a lot of empirical evidence that SEC(A) is true, just as we have a lot of empirical evidence that P!=NP, but never knowing for sure.

rg

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


More information about the cryptography mailing list