James Randi owes me a million dollars.
http://www.crypto.com/blog/psychic_cryptanalysis/
James Randi owes me a million dollars
How I discovered my psychic powers at the library
I've long been an admirer of the James Randi Educational Foundation
(JREF), tireless advocates for critical thinking, skepticism, and the
scientific method. They offer a one million dollar prize to the first
person who can provide convincing, testable proof of supernatural
powers. The foundation recently set up a "remote viewing" challenge in
which the purported psychic is asked to describe the contents of a
special sealed box held at the JREF office in Fort Lauderdale, Florida.
Those who know me may be surprised to read this, but I'm pleased to
announce that Jutta Degener and I have successfully visualized the
contents of Randi's challenge box. We accomplished this from over a
thousand miles away and entirely through mental concentration and the
application of our unique talents (or, I should say, gifts), and without
any physical access or inside information. We can now reveal to the
world the item in the box: a small mirrored flat circular wheel or disk,
such as a DVD or CD. Randi, if you're reading this, a money order or
certified check will be fine.
As you ponder the cosmic ramifications of the awesome, terrible powers
that we apparently possess (we'll use them only for good, I promise),
let me explain a bit more about the remote viewing challenge and how we
accomplished this unprecedented paranormal feat.
Threat models for public challenges such as this one are mutually
adversarial. Here, Randi and his foundation want to protect themselves
from cheating scammers who might seek to learn the contents of the box
through non-supernatural, earthly means. Would-be psychics, on the other
hand, want to be assured that the game is fair. In particular, the
foundation should not be able to deny the prize to a genuinely
successful remote viewer by switching the box's contents after the fact.
Cryptographers might recognize this as a textbook setup for bit
commitment protocols, in which a systematically encoded text (called a
"commitment string" in the technical jargon) is published in a way that
does not reveal its underlying content. Later, the original text and
other parameters that produced the commitment string are revealed to
allow anyone to learn the original text and to verify that no cheating
occurred (that is, that the published commitment string really could
only have been produced from the underlying text).
In typical bit commitment protocols, the commitment string is the output
of a randomized one-way function. Most cryptographic commitment
protocols have the nice property that they work even when neither party
trusts the other and without third party help.
Randi apparently also saw this as a bit commitment problem, and last
week published this encoded description of his box's secret contents:
0679
4388
66/27
5 -14
After staring at this commitment string for a little while, we suspected
(or, if you prefer, we had a divine inspiration) that the first 10
digits might represent the ISBN number of a published book. Sure enough,
a bit of Internet research quickly revealed ISBN number 0-679-43886-6 to
be the 1995 edition of the Random House Webster's College Dictionary.
Once we tracked down a library with a copy (it's a bit scarcer than you
might think), we checked page 275 ("/27 5"). If you're following along
with a copy at home, you'll see that the 14th entry from the bottom
("-14") is the definition for compact disc, which is, as Randi has
confirmed, what was in the box.
So, unfortunately (for Randi, that is -- remember, money order or
certified check, please), the commitment function used here turned out
to be reversible. There's also another problem. Because the exact
procedure for performing the encoding was not fully specified as part of
the challenge, the commitment string is also subject to collisions. With
a little creativity, anyone can use the published string to "prove" that
the box contains almost anything. For example, if we interpret the "14"
a little differently, we might use the 1st column, 4th entry of the same
page to assert that the box contains a copy of the Communist Manifesto.
Randi, for his part, could exploit this ambiguity to disavow a valid
psychic claim, should one happen to come along.
It's tempting as a cryptographer to suggest that all this could be fixed
simply by using a better cryptographic commitment scheme, such as one
based on a widely-scrutinized pseudo-random function. But in fact,
digital bit commitment really isn't a good fit here. It won't help us to
find an unambiguous cryptographically strong collision-free one-way
function unless we can also explain -- even to people who believe they
possess magical powers -- what that would prove. Remember that the
underlying purpose of the JREF challenge is educational, aiming to
produce persuasive evidence that refutes (or confirms) supernatural
claims. Bit commitment protocols are, as we've just seen, hard to get
right; good ones depend on subtle interactions of esoteric mathematical
functions. It can be very difficult to convince even an expert in the
field that a proposed protocol is secure and fair. I'm not aware of any
such protocol that's easily understandable to a non-specialist. Arcane
complexity is a regrettably common feature in cryptographic functions.
Intuitively accessible secure cryptography would help solve problems
well beyond exposing crackpot psychics. Perhaps the most important and
obvious is electronic voting. For several years now (long before the
present debate on the subject), there have been cryptographic election
systems proposed that provide a remarkable range of provable security
properties, including anonymity, publicly verifiable outcomes, the
inability to sell votes, and so on. And yet election officials and the
vendors of electronic voting machines have almost universally ignored
them. Why? Largely because these protocols are practically
incomprehensible without (or even with) specialized expertise. The first
requirement for a democratic election is that voters understand and have
confidence in the outcome. The crypto-based voting systems proposed thus
far by and large fail this test from the start. Voting, like psychic
debunking, is first and last a human scale security problem.
I can imagine ways to construct remote viewing challenges that could be
understood without a PhD in cryptanalysis, but they don't involve
cryptography or computers and they have other disadvantages that might
render them impractical for Randi's purposes. One might, for example,
display a sealed challenge box in a prominent public place, to be opened
in a widely-advertised ceremony at some specified time in the future. As
an accomplished magician, Randi (he's the Amazing Randi, after all)
doubtlessly envisions simple ways that such a challenge could be
undetectably rigged or subverted. That intimate familiarity with the
human-scale side of cheating no doubt explains his attraction to
cryptographic alternatives, which at least resist sleight-of-hand. I
wish our community had more to offer him right now. I suppose I'll
graciously decline his million dollars. This time.
The fine work of the James Randi Educational Foundation deserves your
attention and support. Check them out at www.randi.org.
www.crypto.com/blog ? mab@crypto.com
