Oded Goldreich has written an essay in response to two essays on “provable security” by Koblitz and Menezes. Oded says that “Although it feels ridiculous to answer [the claims of Koblitz and Menezes], we undertake to do so in this essay. In particular, we point out some of the fundamental philosophical flaws that underly the said article and some of its misconceptions regarding theoretical research in Cryptography in the last quarter of a century.“
Neil Koblitz spoke here at IPAM in October on the somewhat related matter of how to interpret results in the Random Oracle model and in the Generic Group model. There is an audio file of his talk.
18 comments
Comments feed for this article
December 5, 2006 at 8:43 am
Anonymous
Welcome to Bizzaro World. First of all, do people know how to write coherent introductions these days? Try reading the Koblitz-Menezes article and figuring out what the hell they are trying to say… no, first you will have to read through long descriptions of cryptosystems and signature schemes, followed by… what seem like at most vague and poorly stated complaints.
While Oded’s response is hilarious (e.g. he is careful to defend post-modernism while lamenting its application to cryptography), maybe his response should have just been Whaaaaa? (and then the sound of a hand slapping a forehead)
I think that the point Koblitz and Menezes get most wrong is one that lots of practioners also fail to get, relating to the science of desigining a system/algorithm based on the fact that eventually you will try to prove your approach correct. Sure, a lot of time this introduces unreasonable (pratical) inefficiencies into an algorithm. The point is that it can also produce approaches that transcend basic human intuition.
December 5, 2006 at 7:24 pm
Anonymous
I don’t think Oded understood the point of Koblitz-Menezes. They are not arguing that we should stop proving correctness, as Oded seems to imply, but rather that we keep in mind that any given cryptosystem lives in the real world and security is thus more than hwo difficult it is to invert a single application of an encryption function.
In hindsight, there is not even much revolutionary in this. PKC is useful because of this very observation, i.e. distribution of the key can be as big a problem as encryption itself.
December 5, 2006 at 8:09 pm
Anonymous
Does anyone else find his view of “science” odd? I would think most people would think of science as developing theories that can that fit the evidence and make falsiable predictions that can be tested in the real world. His view seems to be entirely removed from the real world. If two different assumptions seem to be completely equivalent in practice (to algorithm designers), even though we can’t prove it, shouldn’t that count for something?
December 5, 2006 at 11:54 pm
Anonymous
“Does anyone else find his view of “science” odd?” — yes, I’d agree to that. He seems to use “science” as a synonym for “mathematics”.
December 6, 2006 at 12:57 am
Anonymous
Well, he also references Bacon’s Novum Organum as justification for “rigorous analysis” in cryptography, by which he apparently means theorem/proof analysis. To my knowledge, that work essentially describes how to conduct empirical scientific experiments to gain knowledge, and does not support the claim that the former kind of analysis is the only acceptable methodology e.g. for cryptography, and that its results should be blindly adhered to as truth about the world especially when they contradict plain common sense, as K&M claim they do (not saying whether the latter is true or not, just that it doesn’t address this).
December 6, 2006 at 4:55 am
Anonymous
but rather that we keep in mind that any given cryptosystem lives in the real world and security is thus more than how difficult it is to invert a single application of an encryption function
But this viewpoint is by no means new; seem Bellare or Boneh, etc. These are people who care about real-world cryptography, but simultaneously acknowledge and participate in the essential role of rigorous analysis.
December 6, 2006 at 4:56 am
Anonymous
Does anyone else find his view of “science” odd? I would think most people would think of science as developing theories that can that fit the evidence and make falsiable predictions that can be tested in the real world. His view seems to be entirely removed from the real world.
Haven’t you ever heard of string theory?
December 6, 2006 at 4:42 pm
Anonymous
Dear Luca,
I guess I shouyld thank you for calling attention to my essay,
but I fear that I’ll regret it…
I already see 8 comments, begging for answer, but I really cannot afford to take part in this media.
Still, let me make a few points:
1) I don’t care too much of what K&M meant to say, I care of the way their text is (or may be) understood. I’s be happier if any of the opinions that I attribute to their text and crticize is actually not held by K&M or anybody else for that matter.
2) I think that high-level texts and especially texts of a philosphical nature (mine included) should be read in a flexible way; the point should not be to argue with the exact text but rather to study it and/or to nderstand what it means. I found some cmments very lacking in that respect.
3) I do not defend post-modernism. I actually oppose it (as can be read between the lines of my essay). I just think that post-modernism in general is better than the meaning I read into K&M text.
Oded
December 6, 2006 at 4:44 pm
Oded Goldreich
Sorry for all typos on the previous one. I guess I also hit a wrong bottom in getting it be posted as anonymous. I guess I just proved that I’m not fit for this media…
December 6, 2006 at 4:52 pm
Oded Goldreich
I was told that I had typos also in my last comment… I meant to say that I hit the wrong button
(not “the wrong bottom”), and I hope nobody will read Freudian slips or anything else into my typos…
December 7, 2006 at 3:12 am
Anonymous
I would like to compliment Oded on his essay (I only know what it is responding to via the essay itself, but that is not what I am concerned with). However, I feel that they way he employs “Unscientific” is similar to the way that others have used “Unamerican”.
I can also see why some see the essay as supporting postmodernism. In the end, Science is simply a methodology. As this essay exhibits, the methodology cannot support itself (the argument here to support “Science” is not a scientific argument by the author’s admission). The question becomes, “what does support the methodology”. The answer seems to be “truth” or “intuition” depending on where we were in the argument. The answer of “truth” (which I think is likely Oded’s answer) is often refused by postmodernists. Then you are left with intuition, which, is very close to saying, “faith” (however faith usually has a component of revelation).
Conclusion: Postmodernists are Unamerican!
December 7, 2006 at 4:30 pm
Yehuda Lindell
I am actually quite amazed at some of the comments written here. Science, and this goes for ANY science, is categorized by rigorous methodology. This is true of mathematics and of empirical science – the difference is in the methodology and not in the fact that it is rigorous. Koblitz and Menezes’ main argument is that intuition should come first. This is completely unscientific and could not be said in any scientific community. Needless to say, if Koblitz and Menezes were proposing an empirical methodology for security, this would be a completely different story. However, the fact that “many people in the field feel something” is not a methodology at all. If it were, many folklore medicines could be approved by the FDA because there are thousands of people that swear by them. Intuition taking precedence over theory would also have had interesting ramifications for relativity (it definitely should not be accepted because it’s completely anti-intuitive). So, if you want to trust your intuition go ahead. But don’t try to call it science…
December 7, 2006 at 5:45 pm
Oded Goldreich
Oh, this is unresistable.
Having a “supporter” as commentator Nr 12, forces me to violate my silence vow:
1) As I point out in the ssay, I differentiate between intuition applied to simple and basic things vs intuition applied to things we don’t understrand at all.
2) Indeed, if one insists and wants to get to the first cause of all, then one cannot speak at all.
And while being here, I do want to state that what I and others take from Bacon is the basic rigorous attitude not a specific methodlogy that may be adequate in one discipline but not in another. One of my main points was the experiments make no sense in Cryptography. How do you experiment with an adversary (without incurring massive harm)?
December 8, 2006 at 6:48 am
Anonymous
It is difficult for me to
believe that Oded wanted to
post his first response
as an anonymous person
considering that his message
begins by saying “I guess I
should thank you for calling
attention to MY essay”.
If it was posted openly
purely due to inability to
hit the wrong button, then
the message will not be like
this.
December 8, 2006 at 7:04 am
Anonymous
It appears to me that
Oded seems to have double standards
based on his first response.
In point 1, he says “I don’t
care what K & M meant to said
and I just care of the way their
text is (or may be) understood”.
In point 2, he says “High level
texts (mine included) should be read in a flexible way. One should not argue with the exact text and should study and understand the
intent of the author”.
So it appears that while he
will deal with other’s writings
with their exact text, he wants
his own writings to be read
by others by somehow magically getting into his head.
December 8, 2006 at 7:23 am
Anonymous
Oded,
Of course I don’t mean to violate #1. You very clearly laid out #1. However, in the previous sentence, when I say “you very clearly laid out #1”, what am I really asserting. By what methodology did you convince me? It is not the methodology of science. We agree on that. So then by what? #2 goes too far to say that nothing can be asserted (I am not here saying it is wrong, but rather that it cannot substantiate by assertion). So then there is some methodology outside of science but within which we can make and argue assertions. And that is marvelous!
Anonymous #12
December 21, 2006 at 4:19 pm
Anonymous
Beside advocating rigor in cryptography, perhaps, Goldreich should learn to have the same standard of rigor in writing, more precisely “typing”.
In his essay, Goldreich said the “random oracle paradigm” has become a fetish and so we should banish it somehow. I get the feeling that Koblitz and Menezes think “provably security” (I don’t know what terminology I should use) has already became an even bigger fetish as many researchers focus so much on rigorous inference between security of a construction and the underlying computational problem assumption(which is not bad). But many of them forget to check whether the assumption makes any sense. Many of such constructions work only with unrealistic parameters for implementation or are not secure at all.
Listen to the Koblitz’s talk or read their second draft. To get rid of the fetish random oracle, Boneh and Boyen created a “short signature” with a longer signature by replacing the common assumption with a less common one. The gain is their proof does not need the random oracle. The loss is their scheme cannot be “instantiated” securely with any choice of parameters although they already evaluate the hardness of the new computational assumption in the generic group model. Similar to this, Bellare showed a hybrid encryption construction provably secure in the random oracle but cannot be “instantiated” securely when the random oracle is replaced with any real hash function.
I think what Koblitz and Menezes complained is many people prefer to replace a fetish by a bigger fetish in order to write a paper with title like “XXX without Random Oracle”.
Many of the original constructions in the random oracle model cannot be decided secure or not. The uninstantiation of random oracle has not been shown in all of them. On the contrary, many schemes without random oracle make use of the SDH assumption. The uninstantiation of realistic parameters for them can be shown. I believe Kobitz and Menezes just wanted to make the community to aware of this unhealthy reliance on the unreadable theorems in many crypto papers.
Good “science” is not just all about rigorous methodology. Verification of assumption in real world is also important. Both are required to make “science” whole. Could any single theory alone in physics make a scientist a Noble prize winner without any experiments done to show a phenomenon that is predicted “solely” by the theroy? When claiming cryptography rigorous science, we may have dishonoured those scientist. If cryptography can be treated as like any of the physical science, so can economics, right?
It appears that Goldreich defended the rigorous methodology in cryptography but dwarfed the importance of the verification of assumptions and implementation parameters, at which Koblitz and Menezes casted a moan. His philosophy seems to be “use good assumption like one way functions”. Does it imply that we should banish public key encryption?
April 14, 2007 at 8:44 pm
Anonymous
I find Menezes and Koblitz’s article quite interesting and an enjoyable read. I was not very impressed by Oded’s comparison to ROM as a fetish.
Something is better than nothing.. and that something is provided by ROM. All serious crypto people know that ROM is just theory.. However, it still does give a reasonable model for proving security.