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

Ron Garret ron at flownet.com
Wed Jul 27 14:00:50 EDT 2016


On Jul 27, 2016, at 10:30 AM, Ray Dillinger <bear at sonic.net> wrote:

> 
> 
> On 07/27/2016 10:13 AM, Ron Garret wrote:
>> 
>> You didn’t include any context so it’s hard to know exactly what
>> you’re referring to here, but I think you’re attacking a straw man.
>> All of the references to brute-force in this discussion have been to
>> brute-force searches for *algorithms*, not brute-force searches for
>> keys.
>> 
> 
> In general, I refer to the fact that enumerating all
> possible proofs is the same method for finding whether
> a cipher is secure, as enumerating all possible keys
> is a method for finding an encryption key.  (an
> encryption key, after all, is a particular bit
> string which we can prove has some property with
> respect to another bit string).
> 
> One could in theory base a secure cipher on the
> problem of finding mathematical proofs that the
> equations governing particular problems are secure,
> just as we normally do with ciphers which are proofs
> that particular numbers have particular properties
> relative to the boolean equations that comprise
> the cipher algorithm.

Sorry, I’m not following this.  A proof and an algorithm are not the same thing.  I don’t see how a cipher algorithm is a “proof that particular numbers have particular properties relative to the boolean equations that comprise the cipher algorithm.”  Can you please explain that?

> But how would you prove that such a hypothetical
> cipher were secure?  Oh, wait (Wait forever, in
> fact).  Didn't we say that the Halting problem was
> one we wouldn't necessarily need to address?

No, you don’t have to wait forever.  You don’t need to run an algorithm forever to know that it’s not an attack.  You can stop once it has run as long as a brute-force attack.  It really is a finite problem.  The halting problem really does not come into play.  It really is just about the fact that the cost is larger (by a huge margin!) than the computational power of our universe.

rg



More information about the cryptography mailing list