From: nobody@cypherpunks.ca (John Anonymous MacDonald)
Date: Sun, 24 Nov 1996 17:35:19 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: IPG Algorith Broken!
Message-ID: <199611250124.RAA07293@abraham.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain



At 7:10 AM 11/24/1996, The Deviant wrote:
>On Sun, 24 Nov 1996, John Anonymous MacDonald wrote:
>> At 6:56 PM 11/23/1996, The Deviant wrote:
>> >On Sat, 23 Nov 1996, John Anonymous MacDonald wrote:
>> >> The good news is that you can prove a negative.  For example, it has
>> >> been proven that there is no algorithm which can tell in all cases
>> >> whether an algorithm will stop.
>> >
>> >No, he was right.  They can't prove that their system is unbreakable.
>> >They _might_ be able to prove that their system hasn't been broken, and
>> >they _might_ be able to prove that it is _unlikely_ that it will be, but
>> >they *CAN NOT* prove that it is unbreakable.  This is the nature of
>> >cryptosystems.
>> 
>> Please prove your assertion.
>> 
>> If you can't prove this, and you can't find anybody else who has, why
>> should we believe it?
>
>Prove it?  Thats like saying "prove that the sun is bright on a sunny
>day".  Its completely obvious.

In other words, you can't prove it.  Thought so.

>If somebody has a new idea on how to attack their algorithm, it might
>work.  Then the system will have been broken.  You never know when
>somebody will come up with a new idea, so the best you can truthfully
>say is "it hasn't been broken *YET*".  As I remember, this was mentioned
>in more than one respected crypto book, including "Applied Cryptography"
>(Schneier).

Page number?

Perhaps it would be helpful to hear a possible proof.  If somebody
were to show that breaking a certain cryptographic algorithm was
NP-complete, many people would find this almost as good as proof that
the algorithm is unbreakable.

Then if a clever person were to show that the NP-complete problems
were not solvable in any faster way than we presently know how, you
would have proof that a cryptographic algorithm was unbreakable.

There is no obvious reason why such a proof is not possible.

diGriz