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

[Ron Garret]

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

> 
>> On Jul 22, 2016, at 11:00 AM, Ron Garret <ron at flownet.com> wrote:
>> 
>> 
>> On Jul 21, 2016, at 10:22 AM, Arnold Reinhold <agr at me.com> wrote:
>> 
>>> 
>>>> On Jul 20, 2016, at 3:14 PM, Ron Garret <ron at flownet.com> wrote:
>>>> 
>>>> 
>>>> On Jul 15, 2016, at 4:58 PM, Ron Garret <ron at flownet.com> wrote:
>>>> 
>>>>> 2.  SEC(A) is true but nonetheless no proof exists.  (Godel sentences are not necessarily the only unprovable truths.)
>>>> 
>>>> It turns out that there is reason to believe that this is in fact the case.
>>>> 
>>>> http://www.scottaaronson.com/blog/?p=2725
>>>> 
>>> 
>>> Another interesting article by Scott Aaronson, thank you, but like P vs. NP it is dealing with the theory of Turing machines. While cryptographic algorithms are executed on Turing machines, there is not reason to think that they contain embedded Touring machines. Why would we allow that? And it is not likely to happen by accident. The paper has a link to a discussion of what is the smallest universal Touring machine, but I wonder if that has ever been translated into bits, i.e. how many bits are needed to define the smallest UTM? I think it is unlikely from a purely information content argument that some cleverly chosen key could turn AES-256 into a Turing machine, much less one executing a program that is impossible to decide in ZF. A similar argument might apply to Elliptic Curve groups of the size currently used. And as I pointed out previously, we like EC groups because of their lack of internal structure. Some as yet undiscovered structure that enabled them to act as Turing machines might also lead to a faster solutions of discrete logs.
>>> 
>>>>> 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
>>>> 
>>>> This is also a real possibility:
>>>> 
>>>> https://johncarlosbaez.wordpress.com/2012/10/19/insanely-long-proofs/
>>> 
>>> It is certainly possible that a proof of a lower bound for a cryptographic algorithm might be impossibly large, but it hardly follows from this paper. Peano arithmetic is a much bigger system (infinite of course) than what is needed to construct common cryptographic algorithms, which all operate in finite systems that are too small for Goedel's encoding.
>>> 
>>> Complexity theory has led to some beautiful math, but it also seems to have discouraged some practical research because it is mistakenly taken to suggest things are unsolvable even in situations when the underling assumptions for undecidability are not met.
>>> 
>>> Arnold Reinhold
>> 
>> Yes, I agree with everything you say.  But you’re still missing my point: the crypto systems we are using are not Turing-equivalent (they are finite-state machines), but the systems we use to *prove* things about them *are* Turing-equivalent.  It might be the case that the only way to prove that a crypto system is secure is to exhaustively enumerate all possible algorithms and eliminate each one as a candidate attack by actually running them on all possible keys.  This of course doesn’t even begin to touch on any “interesting” problems in complexity theory like busy-beaver numbers or Kolmogorov complexity, but it would nonetheless be intractable.  
> 
> It is not intractable.
...
> The table will be very large (to big for the known universe no doubt)

We seem to be using different definitions of the word “intractable.”  When I say “intractable” don’t mean intractable in principle, I mean intractable in practice, in *this* universe, on *this* planet, in the face of actual technological and physical limitations.  Cryptography matters, not because the math is beautiful, but because it addresses contemporary human needs and desires.

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

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.

rg