Mathematics has a long tradition of using counter-examples as a way of illuminating structure in theory. Especially in more abstract areas like topology, canonical counterexamples provide a quick way of teasing out fine structure in sets of axioms and assumptions.
A brief foray through Amazon.com revealed catalogues of well known counter examples in topology, analysis, and graph theory. On the web, there are pages on counterexamples in functional analysis, Clifford algebras, and mathematical programming.
What would be good candidate areas for a list of counter-examples in theory ? Complexity theory springs to mind: simple constructions (diagonalization, what have you) that break certain claims.
In combinatorial geometry, one might be able to come up with a list of useful structures. Personally, I find the projective plane to be a useful example to demonstrate the limits of combinatorial arguments when reasoning about geometric objects.
Cryptography. The entire early history of the field is a litany of counterexamples -- for example, knapsack cryptosystems were conjectured to be secure because they were "based on" NP-hard problems. In practice, the notion of "based on" wasn't particularly formal, and eventually we found out they weren't all that hard to break. Andrew Odlyzko's "The Rise and Fall of Knapsack Cryptosystems" is pretty good, although slightly dated (the Chor-Rivest scheme was broken in 1998).
ReplyDeletehttp://citeseer.ist.psu.edu/odlyzko90rise.html
I suspect this history helped motivate the more recent interest in hardness of lattice problems. For example, the Ajtai-Dwork cryptosystem actually has a randomized reduction from the underlying problem to breaking the cryptosystem, and the underlying family of lattices has a worst-case to average case reduction. (Although later we found out that for "practical" parameters it doesn't seem to be hard enough.)
In general, broken cryptosystems serve as counterexamples that push the development of theory in cryptography. They force us to reconsider our assumptions and look for more rigorous foundations.
There's a second strain of counterexamples in cryptography, as well. These counterexamples might be closer to the spirit of the mathematical ones you mention. This strain looks at definitions of security in cryptography and comes up with cryptosystems that meet the definition but don't have some property we might "intuitively" expect a "secure" cryptosystem to have.
For example, the standard definition of security for public-key encryption is indistinguishability of encryptions. If I give you a string X, and promise you it is either the encryption of a "1" bit or of a "0" bit, you shouldn't be able to tell which (with non-negligible probability). You can further augment this definition with a chosen-ciphertext oracle and show the stronger definition implies non-malleability. You can also show it implies semantic security, which says the adversary "learns nothing" about the plaintext given the ciphertext. It looks like a perfect definition.
Does it hide which public key was used to encrypt? We want this for applications to anonymous messaging; if the encryption reveals the recipient, things become a lot harder. In fact it doesn't, and you can come up with a silly counterexample that leaks the recipient's identity with 100% certainty on every message.
Another example here would be the random oracle model counterexamples of Canetti, Goldreich, and Halevi. They show there are signature schemes which are secure in the random oracle model, but not secure at all for *any* instantiation of the random oracle. I'm still trying to wrap my head around that one.
Forgot to sign last comment. -David Molnar
ReplyDeleteThanks. this is a good example !
ReplyDelete