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

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

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

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 writes:

...

Don Wood 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 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