[Cryptography] Are zero knowledge authentication systems safe?

[Jerry Leichter]

> Let us assume that we have a provably secure zero knowledge system. Is
> it actually more secure in practice than other techniques?...
> 
> Am I just missing the point or is this particular zero knowledge proof
> rather brittle in practice?
Koblitz and Menezes have been writing about issues with "proofs of difficulty" for close to a decade.  One overview is http://www.ams.org/notices/201003/rtx100300357p.pdf.  Over all, they make several points:

1.  The proofs that are out there, even if true, often don't prove what they claim;
2.  The trend in these proofs is in an unfortunate direction, based on reductions to problems more or less made up for the purpose and which there is actually almost no reason to accept at face value any claim of difficulty;
3.  One can find examples where algorithms were almost certainly made *weaker* in order to enable a "proof of security".

They haven't specifically addressed the issue you raise - brittleness - though it's implicit in much of what they write.  My own take on this is that traditional mathematical techniques and results are *inherently* brittle.  Why?  Because the mathematician's goal is the most general possible theorem - the one that requires the bare minimum of constraints to be true.  But that means the instant you remove any of the remaining constraints - the theorem becomes false!  (Compare the reported NSA definition of a trusted party:  Someone who can break your security.)

It's not that there hasn't been work that attempts to develop some kind of theory of robustness.  The whole field of concrete complexity - some of the pioneering work here was done by Bellare and Rogoway - at least started of as a way to develop such a theory.  (I haven't kept up with the literature and don't know where it is these days.)  But it's the direction relatively few have followed:  After a great deal of careful, complex analysis, you get fairly boring-sounding results.  Meanwhile, the guys making the assumptions come up with all kinds of sexy new algorithms and protocols....

                                                        -- Jerry