The Aura of Interactive Proofs

In his essay The Work of Art in the Age of Mechanical Reproduction, Walter Benjamin introduces the idea that original artwork has an aura — some ineffable something that the work’s creator imbues into the work, but which is lost in reproductions made by mechanical means. There is something unique about an original work. Let us imagine that Walter is able to read the aura of work of art, or sense its absence. Thus, he has the seemingly magical ability to tell original art from mechanical forgery.

Andy Warhol is skeptical of Walter’s claims. Andy doesn’t believe in the aura. And even if the aura does exist, he sincerely doubts that Walter is able to detect its presence. In an attempt to unmask Walter for the fraud he undoubtedly he is, Andy hatches a cunning plan to catch Walter in a lie. By hand, he paints an original painting, then using the most advanced technology available, makes a perfect replica of the original. Although the replica looks exactly like the original to the layman (and even Andy himself), according to Walter, there is something missing in the replica.

Andy’s original plan was to present Walter with the two seemingly identical paintings and simply ask which is the original. He soon realized, however, that this approach would be entirely unsatisfactory for his peace of mind. If Walter picked the true original, Andy still couldn’t be entirely convinced of Walter’s powers: maybe Walter just guessed and happened to guess correctly! How can Andy change his strategy in order to (1) be more likely to catch Walter in his lie (if in fact is he lying) and (2) be more convinced to Walter’s supernatural abilities if indeed he is telling the truth?

Andy’s next idea is to repeat his test of Walter. He plans to present Walter with the two pictures and ask which is the original, then ask Walter to leave the room. When Andy is alone with the two pictures, he will decide to either swap the two pictures, or leave them alone, then ask Walter which is the original work. Andy and Walter will repeat this procedure until either Walter slips up and Andy catches him in a lie, or until Andy is convinced that Walter can actually sense the aura of the original painting.

Although Andy is reasonably happy with his plan, he is still a little bit worried. While he doesn’t believe Walter can sense the aura of a picture, he knows that Walter is quite brilliant and knows Andy well. So perhaps Walter could predict whether or not Andy will switch the pictures each time Andy tests Walter. Or perhaps, Walter can tell from Andy’s reactions which is the original painting. Either way, it might still be possible for Walter to cheat.

So Andy comes up with a scheme that he thinks is certain to work. First, he asks his assistant to pack the two pictures for travel and not tell Andy which picture was in which package. This way when Andy arrives at Walters with the two pictures, not even Andy will know which is the original painting. Therefore, he won’t give away which picture is the original with his body language or anything else. Second, when he chooses to swap the pictures, instead of choosing arbitrarily, he will flip a coin and make the choice randomly. After the first showing of the pictures, he will not ask Walter which painting is which. Instead, he will simply ask Walter if the two pictures were swapped. Andy will only be convinced of Walter’s clairvoyance if he is able to correctly tell whether or not the pictures were swapped in, say, 20 consecutive tests.

This procedure is a very clever way for Walter to convince Andy that he can sense the aura of an artwork. In fact, the procedure satisfies the following two criteria:

Completeness If Walter can sense the aura of the original artwork, then he will be able to convince Andy of his power by correctly determining whether or not the pictures were swapped 20 times in a row.

Soundness If Walter cannot actually sense the aura of the original art, then he is incredibly unlikely to be able to guess whether or not the pictures were swapped 20 times in a row. In fact, since the choice of swapping is made at random, the probability that he can correctly guess whether or not the pictures were swapped 20 times in a row is \(\frac{1}{2^{20}}\), which is on the order of one in a million!

A protocol described above is known as interactive proof in computer science. The notion of an interactive proof was introduced by Goldwasser, Micali, and Rackoff in 1985 in their paper, The Knowledge Complexity of Interactive Proof-Systems. Interactive proofs has proven to be a fundamental concept in computational complexity theory and has found many applications in cryptography. The protocol described above has another feature that is of particular interest to cryptographers: zero knowledge.

Zero knowledge At the beginning of the protocol, when Andy initially shows Walter the pictures, Andy does not know which is the original and which is the reproduction. At the end of the protocol, he still doesn’t know which picture is which, since Walter only told Andy whether or not the pictures were swapped, and not which is the original. Thus, Walter is able to convince Andy of his clairvoyance without revealing any additional information, such as which is the original painting.

Will Rosenbaum

Tel Aviv

comments powered by Disqus