From: nobody@cypherpunks.ca (John Anonymous MacDonald)
Date: Tue, 26 Nov 1996 09:44:57 -0800 (PST)
To: cypherpunks@toad.com
Subject: Provably "Secure" Crypto (was: IPG Algorithm Broken!)
Message-ID: <199611261727.JAA14042@abraham.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain



At 12:28 PM 11/25/1996, Dana W. Albrecht wrote:
>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.

What is the longest running provably optimal algorithm?  Would it be
possible to construct a crypto system from it?

A relatively weak crypto system which is provably no weaker than it
appeared would have its uses.

>Comments, anyone?

Congratulations on your excellent post.

diGriz