On Sun, 6 Oct 2002, Adam Shostack wrote: > Has anyone done any research into how much better new cryptosystems > with proofs of security do, as opposed to their unproven cousins? It > seems that having a proof of security doesn't actually improve the > odds that a system will survive attacks. But thats my intuition, not > a proven fact. ;) > > Has anyone read a stack of papers and done some statistics?
Cool idea... If you're going to do this study, you might want to first split off block ciphers into their own separate category. My understanding is that the proofs of security you see there are more along the lines of "we prove we don't fall victim to differential cryptanalysis." In contrast, with public-key crypto the proofs are of the typically of form "if you can break the scheme, then you can factor/break DH/break DDH/something else." The empirical 'benefit' of both kinds of proofs is certainly of interest, but I think it'd be way too confusing to treat them together. Not that I think you were making that suggestion, of course. I merely want to point out that the term "proof of security" covers a bunch of different things with different characteristics. For a while, the "proof of security success story" I would have cited was OAEP vs. PKCS #1 v1.5 . The water there seems a little more murky now than it did in 1998. I personally think that a case can be made that OAEP is "better" than PKCS #1 v1.5, and we can observe that OAEP has a proof of security in the random oracle model, while PKCS #1 v1.5 has no proof. (Before everyone jumps in pointing to Shoup's paper, I know about that - that's why I wrote the water is more murky). Making that case takes more time than I have for this e-mail. -David
