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

[Dana W. Albrecht]

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 at corsair.com

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


Eric Murray <ericm at lne.com> writes:
> Don Wood <wichita at 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 at 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