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

[Arnold Reinhold]

John Tromp via e-mail has kindly called my attention to the following:

> in your recent post to the Cryptography List, you asked
> "how many bits are needed to define the smallest UTM?"
> 
> My page http://tromp.github.io/cl/cl.html <http://tromp.github.io/cl/cl.html>
> argues that it is upper bounded by 29 bytes.
> Also see http://www.ioccc.org/2012/tromp/hint.html <http://www.ioccc.org/2012/tromp/hint.html>...
> this is the smallest encoding I know of, of a universal machine
> that does all the work of parsing a description of some machine/term and
> then simulating the behaviour of that machine/term on the remainder of
> the input.

29 bytes is 232 bits, more than the key size of AES-128 and a little less than for AES-256. Of course this is not a lower bound, but it does support the notion that block ciphers with keys in that range are unlikely to contain a hidden Turing machine.

Also in my most recent post where I tried to show that a search for the most efficient algorithm to break a given block cipher is finite, I neglected to mention that the running time for each candidate algorithm can be limited to the maximum time for a brute force search, since we don’t care about algorithms which take longer.

Arnold Reinhold
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160722/f0fd891e/attachment.html>