On 5/25/12 8:35 AM, Robert J. Hansen wrote: > Dan Boneh showed breaking RSA without factoring anything was > probably possible, but it was a nonconstructive demonstration -- we have > no idea where to begin.
Just realized the phrase "nonconstructive" may need to be explained. The best way to do it is with a story. Imagine that you and Dan Boneh [1] are in a dark room. Neither you nor he have any idea what's in here with you, or if in fact there's anything in here at all. You're completely ... in the dark, if you'll forgive the pun. You begin to muse about wouldn't it be nice if there was a way to find out exactly what else was in the room with you. Dan listens politely, then says: "Well, figuring out what's in the room with us is a big question. Maybe we should start smaller: let's find out if there's *anything* in the room with us." You scoff at this. "How are we going to do that? If we find out *what's* in the room with us, that will tell us *if* anything's in the room with us. How do you propose to figure out *if* anything's in the room with us but not *what* that is?" Now, a little-known fact about academics in computer science is that we are all heavily-armed [2]. This is something you probably wished you had thought about before you foolishly volunteered to be in this metaphor, because now Dan Boneh is quick-drawing a Glock 18 with the sort of grace and precision usually reserved for samurai movies. As he fills the room with hot lead at nine hundred rounds per minute, somewhere in the world Quentin Tarantino stops what he's doing and a single tear of pride rolls down his cheek, although he is not quite sure why. Having fallen over in all the excitement, you quickly pull yourself to your feet and scream out, "WHAT WAS THAT?" Somehow, your voice sounds very tinny and far away. Dan casually removes his earplugs and explains: "Judging from the reverberations, we know there are walls. We just don't know where. Judging from the sounds of fragile things breaking, we know there were fragile things -- but we don't know what shape they're in now. And judging from the noise of a sucking chest wound, it's a fair bet there is some other living creature in the room with us." You take all this in for a moment and exclaim, "Are you telling me you just /shot another human being?!/" "No," Dan observes. "It /could/ have been a werewolf. True, werewolves are usually immune to conventional weapons, but I have no way of knowing whether I was using silver bullets just there. I /may/ have shot a human being. But I'm not ruling out the werewolf hypothesis yet, either." At this point you look skywards and scream, "GET ME OUT OF THIS METAPHOR! I get it already! A nonconstructive proof doesn't tell us anything about /what/ or /why/ or /how/, it just says that something /is/! GET ME OUT OF HERE, I don't want to spend the rest of this metaphor in a dark room with a raving psychotic!" Dan helpfully points out as he's reloading that werewolves suffer from lycanthropy, not psychosis. As for you, you flee the metaphor for the safety of a more literal world. [1] In reality, Dan Boneh is a very nice guy, quite reasonable, and nothing at all like I'm portraying him here. [2] http://www.ccs.neu.edu/home/shivers/autoweapons.html _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users