The Swift-Boating of Modern Cryptography
The September issue of the Notices of the AMS is out, and it contains an article by Neal Koblitz on modern cryptography, exposing themes he wrote about in previous articles.
Before I get to Koblitz's thesis I should describe the context, as I see it.
Cryptography underwent two major revolutions in the 1970s and 1980s.
The notion of public key cryptography, invented by Diffie and Hellman (and earlier, but only in classified documents that didn't enter the public domain for decades, by Ellis, Cocks, and Williamson) and made possible by Rivest, Shamir and Adleman, allowed parties that had never met in advance to share a secret key to communicate over an unsafe channel. Without this technology, buying and selling things online would be extremely inconvenient and companies like amazon and ebay would probably not exist.
The other revolution, started by the 1982 series of papers by Blum, Goldwasser, Micali and Yao, was the discovery that one could provide formal definitions of security for cryptographic problems, and that such definitions were achievable under complexity assumptions, albeit, initially, via slow constructions.
Indeed, the importance of the new definitions cannot be overstated, and, possibly for lack of accessible expositions, it has not been completely digested by all the security community. I remember, not too long ago, reading a paper on electronic elections, listing seven or more requirements that an election protocol should satisfy, and it was clear that the list was unwieldy, redundant, and, most importantly, incomplete. The modern definitional approach is instead to begin with a description of an ideal setting (where every person votes in a secret ballot, then all ballots are counted and the total tally is the only information that anybody gets) and then require that a protocol be such that anything an adversary can do in the protocol to alter the outcome or gain information, can also be done in the ideal setting. In particular, whatever outcome or information an attacker cannot gain in the ideal setting, it cannot be gained in the protocol either.
Some constructions developed by theoreticians and coming with a formal analysis are too inefficient to be used, but their development often leads to the discovery of general design principles such that, for example, public key encryption algorithms must be randomized, and should be designed so that it is not possible to construct a valid ciphertext in any other way than applying the encryption algorithm to a known message.
Indeed modern cryptography is the area of computer science where the distance between theory and practice is the least: one finds theoreticians who spend most of their time on impractical constructions designed to be "plausibility results" but who also sit on standards bodies and help create and assess widely used systems, whereas one is less likely to see the algorist preoccupied with $O(log n)$ approximation algorithms also working on commercial optimization packages. The important difference is that optimization algorithms can be validated in practice in a way that is impossible for cryptographic protocols, where one cannot anticipate what attacks will be used, and hence one should strive for security against all possible attacks which is possible, within an attack model, only via a formal analysis and reductions.
Koblitz points out that sometimes proofs contain mistakes, and that there can be attacks not covered by standard models. His reaction, however, is not that the community should be very careful about formal correctness, and explore (as is being done) new models that take into account timing attacks and other "grey box" accesses to the computations of the parties. Rather, he suggests doing away with proofs, and relying more on intuition. This is discussed in the second part of the paper (the first part is devoted to encryption schemes and factoring algorithms via elliptic curves, the "good" interaction between math and cryptography), through such rhetorical devices as non sequiturs, personal attacks, and petulance. The CRYPTO community's typesetting abilities are not spared, nor is Oded Goldreich's spelling.
It would seem hard to defend the idea that one is more likely to make a correct statement if the statement has no proof compared to having a proof, or that one can be secure against a wider class of attacks by relying on intuition rather than defining a class of attacks and establishing the security guarantee. It would be like having a draft-dodger compete in an election against a war hero, and having the latter be on the defensive about his military service, but sometimes strange things do happen.
(For the Italian readers, a better reference would be from Nanni Moretti's Aprile: "Di qualcosa, D'Alema rispondi. Non ti far mettere in mezzo sulla giustizia proprio da Berlusconi! D'Alema, dì una cosa di sinistra, dì una cosa anche non di sinistra, di civiltà!")
Update 9/1/07: you can now read letters to the editors by Oded Goldreich, Boaz Barak, and Jon Katz, and there are more online comments [here] and [here]
Update 9/5/07: Hugo Krawczyk has also written a letter to the editors of the Notices. The interested reader can compare what Koblitz said about Hugo's work on HMQV to the actual HMQV paper.
Before I get to Koblitz's thesis I should describe the context, as I see it.
Cryptography underwent two major revolutions in the 1970s and 1980s.
The notion of public key cryptography, invented by Diffie and Hellman (and earlier, but only in classified documents that didn't enter the public domain for decades, by Ellis, Cocks, and Williamson) and made possible by Rivest, Shamir and Adleman, allowed parties that had never met in advance to share a secret key to communicate over an unsafe channel. Without this technology, buying and selling things online would be extremely inconvenient and companies like amazon and ebay would probably not exist.
The other revolution, started by the 1982 series of papers by Blum, Goldwasser, Micali and Yao, was the discovery that one could provide formal definitions of security for cryptographic problems, and that such definitions were achievable under complexity assumptions, albeit, initially, via slow constructions.
Indeed, the importance of the new definitions cannot be overstated, and, possibly for lack of accessible expositions, it has not been completely digested by all the security community. I remember, not too long ago, reading a paper on electronic elections, listing seven or more requirements that an election protocol should satisfy, and it was clear that the list was unwieldy, redundant, and, most importantly, incomplete. The modern definitional approach is instead to begin with a description of an ideal setting (where every person votes in a secret ballot, then all ballots are counted and the total tally is the only information that anybody gets) and then require that a protocol be such that anything an adversary can do in the protocol to alter the outcome or gain information, can also be done in the ideal setting. In particular, whatever outcome or information an attacker cannot gain in the ideal setting, it cannot be gained in the protocol either.
Some constructions developed by theoreticians and coming with a formal analysis are too inefficient to be used, but their development often leads to the discovery of general design principles such that, for example, public key encryption algorithms must be randomized, and should be designed so that it is not possible to construct a valid ciphertext in any other way than applying the encryption algorithm to a known message.
Indeed modern cryptography is the area of computer science where the distance between theory and practice is the least: one finds theoreticians who spend most of their time on impractical constructions designed to be "plausibility results" but who also sit on standards bodies and help create and assess widely used systems, whereas one is less likely to see the algorist preoccupied with $O(log n)$ approximation algorithms also working on commercial optimization packages. The important difference is that optimization algorithms can be validated in practice in a way that is impossible for cryptographic protocols, where one cannot anticipate what attacks will be used, and hence one should strive for security against all possible attacks which is possible, within an attack model, only via a formal analysis and reductions.
Koblitz points out that sometimes proofs contain mistakes, and that there can be attacks not covered by standard models. His reaction, however, is not that the community should be very careful about formal correctness, and explore (as is being done) new models that take into account timing attacks and other "grey box" accesses to the computations of the parties. Rather, he suggests doing away with proofs, and relying more on intuition. This is discussed in the second part of the paper (the first part is devoted to encryption schemes and factoring algorithms via elliptic curves, the "good" interaction between math and cryptography), through such rhetorical devices as non sequiturs, personal attacks, and petulance. The CRYPTO community's typesetting abilities are not spared, nor is Oded Goldreich's spelling.
It would seem hard to defend the idea that one is more likely to make a correct statement if the statement has no proof compared to having a proof, or that one can be secure against a wider class of attacks by relying on intuition rather than defining a class of attacks and establishing the security guarantee. It would be like having a draft-dodger compete in an election against a war hero, and having the latter be on the defensive about his military service, but sometimes strange things do happen.
(For the Italian readers, a better reference would be from Nanni Moretti's Aprile: "Di qualcosa, D'Alema rispondi. Non ti far mettere in mezzo sulla giustizia proprio da Berlusconi! D'Alema, dì una cosa di sinistra, dì una cosa anche non di sinistra, di civiltà!")
Update 9/1/07: you can now read letters to the editors by Oded Goldreich, Boaz Barak, and Jon Katz, and there are more online comments [here] and [here]
Update 9/5/07: Hugo Krawczyk has also written a letter to the editors of the Notices. The interested reader can compare what Koblitz said about Hugo's work on HMQV to the actual HMQV paper.
posted by Luca at 10:44 AM
62 comments
