Draft of nine new FAQ questions

[Robert J. Hansen]

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