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.
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 an encoded description of his box's secret contents:
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 also easily understandable to a non-specialist. Arcane complexity is a regrettably common feature in modern cryptography.
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 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 probably explains his attraction to cryptographic alternatives, which at least have the virtue, whatever their other limitations, of resisting physical sleight-of-hand. Sadly, however, I don't think our community has very much 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.