[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Provably "Secure" Crypto (was: IPG Algorithm Broken!)




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