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

[Arnold Reinhold]

> 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. We know that there exists one highly efficient, if impractical, Touring machine for breaking a block cipher given a known plaintext-ciphertext pair. Equip the Touring machine with a table of all plaintext ciphertext pairs for each key (a codebook) sorted by plaintext-ciphertext string. Then do a binary lookup in the table for the known plaintext-ciphertext pair to recover the key. The table will be very large (to big for the known universe no doubt) but finite. Binary search time would be on the order block-size times key-length, which is short enough to be considered an efficient break. 

Let G be the size of this table-lookup Turing machine including its precomputed table. Then we can as you suggest "exhaustively enumerate all possible algorithms and eliminate each one as a candidate attack by actually running them on all possible keys” and record the most efficient, but stop when the length of the candidate programs exceeds G. Stopping then is justified since the table look up approach is good enough. So our algorithm-searching Touring machine is guaranteed to halt. 

If you like we can stop the search at a smaller program length, maybe the number of atoms in the Solar system, or a maybe one exabyte, so we only get solutions of practical size (there will be plenty of still-too-large partial table solutions found before we get to length G).  Note that this search is guaranteed to find at least one solution since the brute-force attack of trying all keys is sure to be found.


> The question of whether or not it is the case that this is the only way to prove this result *is* a question of Turing-equivalence because it is a question about proof systems, not a question about crypto algorithms.

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.

Arnold Reinhold