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

Arnold Reinhold agr at me.com
Thu Jul 21 13:22:32 EDT 2016


> 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




More information about the cryptography mailing list