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