Provably "Secure" Crypto (was: IPG Algorithm Broken!)
John Anonymous MacDonald
nobody at cypherpunks.ca
Tue Nov 26 09:44:57 PST 1996
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
More information about the cypherpunks-legacy
mailing list