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

Our friend Don Woods seems to have inadvertently sparked what could be a 
useful and serious discussion regarding "provably secure cryptography."

Not to be confused with the usual "unbreakable" snake oil we see peddled 
so often, I refer to systems for which rigorous mathematical proof that 
"there are no shortcuts" exists.  To my knowledge, no such systems, with 
the exception of a real one-time pad, exist today.  However, I also 
under the impression that ongoing research on this topic continues.  For 
example, consider the work being done on "Lattice" cryptosystems (see 
http://jya.com/lattice.htm).

"diGriz" is right.  Nothing precludes the existence of a cryptographic 
algorithm for which a rigorous mathematical proof of "security" exists
--- where "security" means a provable lower bound on the time required 
for recovery of the key.  Indeed, it seems that finding such an 
algorithm --- or providing the necessary rigorous proof for a current 
algorithm --- is a laudable goal of academic cryptographic research.

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, 
that a particular known algorithm for a given problem is indeed a 
(provably) optimal algorithm for that problem.

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.

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.

However, just as one can say, "How do you know that tomorrow some 
brilliant mathematician will not produce a polynomial time factorization 
algorithm?" one can also say, "How do you know that tomorrow some 
brilliant mathematician will not provide a rigorous proof that all 
factorization algorithms --- in the worse case --- require some 
specified minimal running time?"

While the current state of mathematical knowledge suggests that this is 
not likely to happen anytime soon for the factorization problem, it is 
encouraging to see work in areas where more rigorous proofs of security 
are within closer reach.  Again, I refer to work on Lattice problems.  
If the types of rigorous proof regarding "what can't be done" that are 
known for the Halting Problem, sorting, and searching are available for 
cryptographic problems, then this is indeed a major (and laudable) 
advance in cryptography.

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.

I'm interested in the current state of research (if any) on this topic.  
Other than what John Young sent to the list some time ago about Lattice 
stuff --- which is certainly far from prime time --- I've not seen 
anything else.  I also haven't devoted a lot of time to looking.

Relevant pieces of the earlier thread are included below.

Comments, anyone?

Dana W. Albrecht
dwa@corsair.com

----------------------------------------------------------------------------


Eric Murray <ericm@lne.com> writes:
> Don Wood <wichita@cyberstation.net> writes:
> > Do not belive it, it will never happen. It is impossible,  and we can
> > prove it to your satisfaction.
> 
> No, you can't.  It's impossible to prove an algorithim unbreakable.
> You can only say that it hasn't been broken yet, but you can't
> predict the advances in cryptoanalysis.
> 
> If, in two or three years, no one's broken it then maybe it'll seem
> like a reasonably-secure algorithim.  Of course when someone does break
> it you'll just say "oh, that wasn't the real algorithim" like you did
> last time.

[ Snip ]

> You can't prove a negative.  The best IPG could say is that
> it can't be broken with current technology.
> Next week someone might come up with a new way
> to break ciphers that renders the IPG algorithim breakable.
> 
> You point could have been that the same problem exists
> for proofs- that next week someone could come up
> with a way to prove, for all time, that an algorithim
> really IS unbreakable.  So, to cover that posibility
> I should have said "it's currently impossible to
> prove an algorithim unbreakable". :-)

----------------------------------------------------------------------------

"diGriz" anonymously writes: 
> 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.

[ Snip ] 

> The best they can say is what they did say: they have a proof that
> their system is unbreakable.  What you question, quite reasonably,
> is whether they have such a proof.

[ Snip ]
 
> Or, more accurately, nobody credible has seen such a proof.  But, a
> clever person might invent one.

----------------------------------------------------------------------------

The Deviant <deviant@pooh-corner.com> writes: 
> 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.
> 
> > >The best IPG could say is that
> > >it can't be broken with current technology.
> > >Next week someone might come up with a new way
> > >to break ciphers that renders the IPG algorithim breakable.
> > 
> > The best they can say is what they did say: they have a proof that
> > their system is unbreakable.  What you question, quite reasonably,
> > is whether they have such a proof.
> 
> It is impossible to prove such a thing.  It's like saying you have proof
> that you have the last car of a certain model ever to be built.  Anybody
> could come along and build another, and then you don't have the last one.
> 
> > 
> > >You point could have been that the same problem exists
> > >for proofs- that next week someone could come up
> > >with a way to prove, for all time, that an algorithim
> > >really IS unbreakable.  So, to cover that posibility
> > >I should have said "it's currently impossible to
> > >prove an algorithim unbreakable". :-)
> > 
> > Or, more accurately, nobody credible has seen such a proof.  But, a
> > clever person might invent one.
> 
> There *IS NO SUCH PROOF*.  Just like you can't prove that god created the
> universe, or that Oswald shot Kennedy, and so on and so forth.  It can't
> be proven.  It never has been proven, and it never will be proven.  People
> have new ideas, new algorithms are invented.  Someday, somebody will crack
> _all_ the cryptosystems that have now been invented.

[ Snip ]

> diGriz anonymous writes:
> > At 6:56 PM 11/23/1996, The Deviant wrote:
> > >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.  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).

----------------------------------------------------------------------------

"diGriz" Anonymously responds:
> 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

-----BEGIN PGP SIGNED MESSAGE-----

On Mon, 25 Nov 1996, Dana W. Albrecht wrote:

> I'm interested in the current state of research (if any) on this topic.  
> Other than what John Young sent to the list some time ago about Lattice 
> stuff --- which is certainly far from prime time --- I've not seen 
> anything else.  I also haven't devoted a lot of time to looking.
> 
> Relevant pieces of the earlier thread are included below.
> 
> Comments, anyone?

Matt Blaze did some work on NP-complete Feistel ciphers.  I don't know much
about the details.  The paper is at ftp.research.att.com/dist/mab/turtle.ps

Mark
- -- 
finger -l for PGP key
PGP encrypted mail prefered.
0xf9b22ba5 now revoked

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQEVAwUBMppkIizIPc7jvyFpAQFzYQf7BM9AZR0I7FWEbnvtmBZPYiW4xUARRpTL
eqoeDuA474PMenN/iEYUTRilxfdvUycBgBXLav8RaE+ZYLUuqu3G5uixsM0iwT+5
3nma1/xtNwv9F420nacWDzzSFatg77/SnbsaJ6/EFROHgy8EAz/cie5cZEtCkPJe
s6BFEe32deHHCqlzFamoCE+8UOtyOtGeBtyX4prC/+RfUI0UMU6PXiD1LicvA5C7
cEE7/K4qb8ku7+3qcp1LE47iN0Icuy8xK9N3oX6B00XxwzYX7kqmV4wDRbE0DxcP
O7cmrE395Y+J2w4VenDMw65XLI6Cp1INK2Ev+3/c4Nf+FNaQ/I8jRw==
=xvkT
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----

On Mon, 25 Nov 1996, Dana W. Albrecht wrote:

> Our friend Don Woods seems to have inadvertently sparked what could be a 
> useful and serious discussion regarding "provably secure cryptography."
> 
> Not to be confused with the usual "unbreakable" snake oil we see peddled 
> so often, I refer to systems for which rigorous mathematical proof that 
> "there are no shortcuts" exists.  To my knowledge, no such systems, with 
> the exception of a real one-time pad, exist today.  However, I also 

As I have argued many times, that is correct.  OTP, with real random
numbers, and no-reusage, etc, etc, is the only "perfect" cryptosystem, and
even it has its problems (like key exchange, for instance).

> 
> 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.

> 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.

> 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.

> 
> However, just as one can say, "How do you know that tomorrow some 
> brilliant mathematician will not produce a polynomial time factorization 
> algorithm?" one can also say, "How do you know that tomorrow some 
> brilliant mathematician will not provide a rigorous proof that all 
> factorization algorithms --- in the worse case --- require some 
> specified minimal running time?"

Again I say, it just won't happen.  It can't, and I can't prove that for
the same reasons that it can't happen.

> 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.

> Comments, anyone?
> 
> Dana W. Albrecht
> dwa@corsair.com
> 

 --Deviant
   PGP KeyID = E820F015 Fingerprint = 3D6AAB628E3DFAA9 F7D35736ABC56D39

Unix is the worst operating system; except for all others.
                -- Berry Kercheval


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQEVAwUBMppmkTCdEh3oIPAVAQF50wf+J2Gz8P7stqKD4sesCHmWWYNZX1vf2zU0
nBQhkDABuE2fjJnNpUijc13Vls5K6owkL4LeWEHW2mvwCU1tqseRJSUm8m8ckEh1
M/CBu7lJplFj2QYcK+vFvg1+dOpuZycvhROKb0VO6zbB3PTLi9Cc4iJpwIhqDyDG
zCurg4Ccc1cW7I7lTSfeSlRVVqF5FfCTP0GmqS1lcr+NWSPdHIqgZRGHq5n2+nUU
y16ksaIKJMGJ8bzCFb8Q02ii7JUJF3JyYbgsGRWQMHxN+W0mx2E3Crh3+q4ieK/R
ehGnKh4ZjOPY4RRDLQJfuLTvBBccdoKvSimyKHRoybZYIjTra9jYHQ==
=9qjq
-----END PGP SIGNATURE-----

On Tue, 26 Nov 1996 03:39:35 +0000 (GMT), The Deviant wrote:

   On Mon, 25 Nov 1996, Dana W. Albrecht wrote:

   > so often, I refer to systems for which rigorous mathematical proof that 
   > "there are no shortcuts" exists.  To my knowledge, no such systems, with 
   > the exception of a real one-time pad, exist today.  However, I also 

   As I have argued many times, that is correct.  OTP, with real random
   numbers, and no-reusage, etc, etc, is the only "perfect" cryptosystem, and
   even it has its problems (like key exchange, for instance).

The only one known at this time, not necessarily the only one
possible.  Are you aware of some proof that no other cryptosystem can
be secure (in the way Dana talks about)?

   > 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

There's a Moore's second law?

   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".

"Minimal running time" doesn't really mean time in hours.  Obviously
hardware gets faster all the time.  It means complexity -- O(n^2)
takes more time than O(log(n)), regardless of how fast your hardware
is.  In other words, if takes f(x) time units, but the units are
arbitrary.

"Minimal instruction count" is pretty meaningless (change the
instruction set to arrive at any figure you like).

   > 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.

But there _are_ such proofs ("reductio ad absurdum".  Assume this is
_not_ the best algorithm.  Then there is some better algorithm.
Figure out some properties this better algorithm must have.  Something
like "1 == 2" comes up, therefore there is no such better algorithm.)

Of course you can do it (whatever "it" is) faster with faster
hardware, or maybe better implementation.  And there are sometimes
special-case shortcuts...(a OTP has innumerable "weak keys" -- all
'0's being the most obvious -- of course it's _possible_ that your
random pad just happens to transform your real message into valid
English text, but I doubt this argument would save you from the firing
squad :-) The chance of generating an all-'0' pad ((1/n)^x, n=range of
values in pad, x=number of blocks (characters) in message) is a lot
better than the chance of getting some unrelated-but-meaningful text
as output (I don't even know where start on that one -- it's the
"monkeys in the British Museum" scenario))

   > 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.

Because no-one's found the optimal solution yet (or at least not
proved that it is optimal).

   > "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.

But you're arguing "faster" in terms of clock time (which is obviously
true, but not necessarily useful).  Something that takes O(n^2) time
can be done in arbitrarily short clock time (given fast enough
hardware), but is still slower than something that takes O(log(n))
time.  If you make n big enough, the O(n^2) calculation may not be
worth doing, while the O(log(n)) calculation is still fairly fast (in
reality, of course, you'd prefer something that takes much longer than
n^2).

-- 
Paul Foley <mycroft@actrix.gen.nz>       ---         PGPmail preferred

	   PGP key ID 0x1CA3386D available from keyservers
    fingerprint = 4A 76 83 D8 99 BC ED 33  C5 02 81 C9 BF 7A 91 E8
----------------------------------------------------------------------
Christ:
	A man who was born at least 5,000 years ahead of his time.

At 6:41 am -0500 11/26/96, Paul Foley wrote:
>There's a Moore's second law?

"When the fabs cost $10 billion to build, all bets are off." ;-)

That's expected to happen in 10 years or so. Fab prices have been going up
by an order of magnitude every N years since the beginning of
semiconductors. Forbes did an article on this earlier this year, I think.

Cheers,
Bob Hettinga

-----------------
Robert Hettinga (rah@shipwright.com)
e$, 44 Farquhar Street, Boston, MA 02131 USA
"The cost of anything is the foregone alternative" -- Walter Johnson
The e$ Home Page: http://www.vmeng.com/rah/

At 10:30 PM -0500 11/25/96, Mark M. wrote:

>Matt Blaze did some work on NP-complete Feistel ciphers.  I don't know much
>about the details.  The paper is at ftp.research.att.com/dist/mab/turtle.ps

Matt described some of his (preliminary) results at an evening crypto
session at the Hackers Conference. The motivation was that secret key
ciphers, with the exception of one time pads, tend to be based on crufty,
ad hoc mechanisms, without any kind of provable security (again, with the
exception of true one time pads, which are of course known to be
information-theoretically secure).

It didn't seem to me that Matt had completed his work, and I don't believe
that any usable cipher has resulted (usable in the sense of being a
distibuted, ready to deploy cipher). He mentioned speeds comparable to DES.

Several people in this thread have commented on how nice it would be to
have a cipher provably as "good" as NP-complete problems are "hard"
(loosely speaking).

A noble goal. This was actually a motivation for the Founding Fathers of
Modern Cryptography, of course. Merkle, for example, believed that certain
"puzzle problems" could be used, with the security engendered by
NP-complete problems. The knapsack problem, generally, for example. It
turned out of course that the specifics of the proposed knapsack problem
implementations were not really fully equivalent to the general knapsack
problem, and were in fact breakable.

This is worth bearing in mind. Even if a problem is NP-complete, a
cryptosystem based on it may (and historically, _will_) often fail to be as
strong.

--Tim May


Just say "No" to "Big Brother Inside"
We got computers, we're tapping phone lines, I know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^1398269     | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."

"Dana W. Albrecht" <dwa@corsair.com> writes:
> Our friend Don Woods seems to have inadvertently sparked what could be a
> useful and serious discussion regarding "provably secure cryptography."

Sure beats Timmy May's idiotic rants... Don Woods knows much more about
crypto than Timmy May, Paul Bradley, and all other "cypherpunks" combined.

---

Dr.Dimitri Vulis KOTM
Brighton Beach Boardwalk BBS, Forest Hills, N.Y.: +1-718-261-2013, 14.4Kbps

On Mon, 25 Nov 1996, Dana W. Albrecht wrote:

> 
> 
> Our friend Don Woods seems to have inadvertently sparked what could be a 
> useful and serious discussion regarding "provably secure cryptography."



Not only that But I have proven that the IPG system is perfect, see the
proof at:

           http://www.netprivacy.com 

> 
And you can prove it to yourself, it is patently self evident iwhen you
examine the algorithm and uinderstand what it does.Need I say more.
Find out yourself.

Your friend,

Don Wood

> Not to be confused with the usual "unbreakable" snake oil we see peddled 
> so often, I refer to systems for which rigorous mathematical proof that 
> "there are no shortcuts" exists.  To my knowledge, no such systems, with 
> the exception of a real one-time pad, exist today.  However, I also 
> under the impression that ongoing research on this topic continues.  For 
> example, consider the work being done on "Lattice" cryptosystems (see 
> http://jya.com/lattice.htm).
> 
> "diGriz" is right.  Nothing precludes the existence of a cryptographic 
> algorithm for which a rigorous mathematical proof of "security" exists
> --- where "security" means a provable lower bound on the time required 
> for recovery of the key.  Indeed, it seems that finding such an 
> algorithm --- or providing the necessary rigorous proof for a current 
> algorithm --- is a laudable goal of academic cryptographic research.
> 
> 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, 
> that a particular known algorithm for a given problem is indeed a 
> (provably) optimal algorithm for that problem.
> 
> 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.
> 
> 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.
> 
> However, just as one can say, "How do you know that tomorrow some 
> brilliant mathematician will not produce a polynomial time factorization 
> algorithm?" one can also say, "How do you know that tomorrow some 
> brilliant mathematician will not provide a rigorous proof that all 
> factorization algorithms --- in the worse case --- require some 
> specified minimal running time?"
> 
> While the current state of mathematical knowledge suggests that this is 
> not likely to happen anytime soon for the factorization problem, it is 
> encouraging to see work in areas where more rigorous proofs of security 
> are within closer reach.  Again, I refer to work on Lattice problems.  
> If the types of rigorous proof regarding "what can't be done" that are 
> known for the Halting Problem, sorting, and searching are available for 
> cryptographic problems, then this is indeed a major (and laudable) 
> advance in cryptography.
> 
> 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.
> 
> I'm interested in the current state of research (if any) on this topic.  
> Other than what John Young sent to the list some time ago about Lattice 
> stuff --- which is certainly far from prime time --- I've not seen 
> anything else.  I also haven't devoted a lot of time to looking.
> 
> Relevant pieces of the earlier thread are included below.
> 
> Comments, anyone?
> 
> Dana W. Albrecht
> dwa@corsair.com
> 
> ----------------------------------------------------------------------------
> 
> 
> Eric Murray <ericm@lne.com> writes:
> > Don Wood <wichita@cyberstation.net> writes:
> > > Do not belive it, it will never happen. It is impossible,  and we can
> > > prove it to your satisfaction.
> > 
> > No, you can't.  It's impossible to prove an algorithim unbreakable.
> > You can only say that it hasn't been broken yet, but you can't
> > predict the advances in cryptoanalysis.
> > 
> > If, in two or three years, no one's broken it then maybe it'll seem
> > like a reasonably-secure algorithim.  Of course when someone does break
> > it you'll just say "oh, that wasn't the real algorithim" like you did
> > last time.
> 
> [ Snip ]
> 
> > You can't prove a negative.  The best IPG could say is that
> > it can't be broken with current technology.
> > Next week someone might come up with a new way
> > to break ciphers that renders the IPG algorithim breakable.
> > 
> > You point could have been that the same problem exists
> > for proofs- that next week someone could come up
> > with a way to prove, for all time, that an algorithim
> > really IS unbreakable.  So, to cover that posibility
> > I should have said "it's currently impossible to
> > prove an algorithim unbreakable". :-)
> 
> ----------------------------------------------------------------------------
> 
> "diGriz" anonymously writes: 
> > 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.
> 
> [ Snip ] 
> 
> > The best they can say is what they did say: they have a proof that
> > their system is unbreakable.  What you question, quite reasonably,
> > is whether they have such a proof.
> 
> [ Snip ]
>  
> > Or, more accurately, nobody credible has seen such a proof.  But, a
> > clever person might invent one.
> 
> ----------------------------------------------------------------------------
> 
> The Deviant <deviant@pooh-corner.com> writes: 
> > 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.
> > 
> > > >The best IPG could say is that
> > > >it can't be broken with current technology.
> > > >Next week someone might come up with a new way
> > > >to break ciphers that renders the IPG algorithim breakable.
> > > 
> > > The best they can say is what they did say: they have a proof that
> > > their system is unbreakable.  What you question, quite reasonably,
> > > is whether they have such a proof.
> > 
> > It is impossible to prove such a thing.  It's like saying you have proof
> > that you have the last car of a certain model ever to be built.  Anybody
> > could come along and build another, and then you don't have the last one.
> > 
> > > 
> > > >You point could have been that the same problem exists
> > > >for proofs- that next week someone could come up
> > > >with a way to prove, for all time, that an algorithim
> > > >really IS unbreakable.  So, to cover that posibility
> > > >I should have said "it's currently impossible to
> > > >prove an algorithim unbreakable". :-)
> > > 
> > > Or, more accurately, nobody credible has seen such a proof.  But, a
> > > clever person might invent one.
> > 
> > There *IS NO SUCH PROOF*.  Just like you can't prove that god created the
> > universe, or that Oswald shot Kennedy, and so on and so forth.  It can't
> > be proven.  It never has been proven, and it never will be proven.  People
> > have new ideas, new algorithms are invented.  Someday, somebody will crack
> > _all_ the cryptosystems that have now been invented.
> 
> [ Snip ]
> 
> > diGriz anonymous writes:
> > > At 6:56 PM 11/23/1996, The Deviant wrote:
> > > >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.  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).
> 
> ----------------------------------------------------------------------------
> 
> "diGriz" Anonymously responds:
> > 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
> 



With Kindest regards,

Don Wood