Re: Provably "Secure" Crypto

["Dana W. Albrecht" <dwa@corsair.com>]

The Deviant <deviant@pooh-corner.com> writes: 
> On Mon, 25 Nov 1996, Dana W. Albrecht wrote:
> > Rigorous proofs of the non-existence of an algorithm are not new.  
> > Neither are rigorous proofs that any algorithm which can solve a given 
> > problem requires a minimal running time.  Or, in an even stronger sense, 
> 
> Hrmmm... I seem to see a problem (namely Moore's first law) in assigning
> anything a "minimal running time".  Perhaps "minimal instruction count"
> would be more suited to your example.  Because if you're talking about
> time, it essentially boils down to "the longer something takes the less
> time it takes".
> 
> > that a particular known algorithm for a given problem is indeed a 
> > (provably) optimal algorithm for that problem.
> 
> Never happen.  It just won't.  As a rule, there's _always_ a faster way.

This is just simply not true.  In fact, since you seem to have gracefully
failed to quote the section of my prior post which demonstrates otherwise,
let me re-iterate it:

> > For a (non-cryptographic) example of a proof of the first sort --- that 
> > is, that "there exists no algorithm" --- consider the famous "Halting 
> > Problem" for Turing machines.  (I believe someone else has also 
> > mentioned this.)  There are many proofs such as this one, often related, 
> > though the Halting Problem itself is perhaps the most famous example.
> > 
> > For an (again, non-cryptographic) example of a proof of the second sort 
> > --- that is, that "any algorithm that solves a given problem requires a 
> > minimal running time" --- consider the proof that the "minimal" number 
> > of key comparisons in the worst case required to sort a random list of 
> > elements for which only an ordering relationship is known is O(nlog(n)).  
> > See Knuth, Volume 3, section 5.3.  For a simpler example, a standard 
> > "binary" search which requires O(log(n)) comparisons to find a given 
> > element in the worst case is provably the optimal algorithm for this 
> > task.

Which part of this have you failed to understand?  Look in section 5.3.1
of Volume 3 of "The Art of Computer Programming" by Knuth.  You will find
there a rigorous proof that the "information theoretic lower bound" of
an algorithm which sorts by comparison of keys is O(nlg(n)).

Alternatively, refer to section 6.2.1 of the same book where it is
demonstrated that a binary search by comparison of keys on a sorted list
where no other information is available is an "optimum" algorithm.

If you wish to discuss this further, then you're going to have to directly
address what's widely known and beautifully articulated in Knuth.

> > Turning once again to cryptography, there is presumably an "optimal" 
> > algorithm for factoring a "general" number in the "worst" case.  Of 
> 
> Ok, now I have to pose a question: If cryptographers actually beleive
> this, why continue to search for a faster one.

That's easy.  That an "optimum" factorization algorithm exists does not
mean it is _known_.  Similarly, while one might demonstrate a mathematical
lower bound on the worst-case running times of all possible (known and
unknown) factorization algorithms, this does not mean that an actual
algorithm which runs in this time is known, nor does it even mean that
an actual algorithm which runs in this time even exists.

If you want a completely useless (but easy to prove) lower bound on the
number of operations a factorization algorithm must necessarily have,
I submit to you a trivial one:  1.  Proof of this is left to the reader. :)
Proofs of more interesting lower bounds left to experienced mathematicians.

> > Turning once again to cryptography, there is presumably an "optimal" 
> > algorithm for factoring a "general" number in the "worst" case.  Of 
> > course, known algorithms for factorization seem to regularly improve and 
> > no one has even suggested that any current algorithm is (provably) the 
> > "optimal" algorithm.  Worse case bounds on running time for currently 
> > known algorithms can certainly be produced, but no one currently knows 
> > if these are the best algorithms.
> 
> Again I say, there's _always_ a faster way.

No, there's not.  While no proofs of useful lower bounds on factorization
algorithms are presently known, this does NOT mean that they do not exist.
That such proofs exist for other, simpler algorithms (see above) just
simply refutes this statement.

> > Obviously, discussion on this topic is unrelated to such security 
> > problems as implementation mistakes, fault analysis, outright theft of 
> > keys, etc.  I hope that I've been careful to explain what I mean by 
> > "provably secure" and that it's not interpreted to include these types 
> > of attacks.
> 
> Yes, I must commend you on your amazing tact in asking this incredebly
> irrevelant question.

You're welcome to think it's irrelevant.  I, for one, am glad that people
like Matt Blaze took the trouble to do some work in this area.  I'm also
grateful that this has been pointed out to me in response to my previous
post.  (Thanks to "Mark M." <markm@voicenet.com>)

Dana W. Albrecht
dwa@corsair.com