Moni Naor on scratch-off cryptography

Theory Lunch, August 30, 2005

Minutes by David Molnar

What is the most prevalent metaphor for thinking about cryptography? If you are Moni Naor, the answer is "envelopes." A standard "layman's explanation" of encryption and bit commitment is that data is placed in special indestructible, perfectly opaque envelopes that cannot be opened without a special key.

In the physical world, however, envelopes are not indestructible. Instead, anyone can open them ("although you may need scissors"). The key quality physical envelopes have is tamper-evidence -- once opened, everyone can see that the contents have been read [1].

The key question of the talk: what can we do, cryptographically, with this weaker tamper-evidence property? Turns out the answer is "quite a bit." The results have cute ideas for applying cryptographic protocols to human beings, as well as basic foundational interest.

Our first example of the power of tamper evidence came with a "scratch-off" approach to polling on sensitive questions. We went back and forth between calling the players in the following Alice and Bob and "pollee" and "poller." I will just call them "pollee" and "poller" in these minutes.

We started by recalling a classical (1965) approach: a poller will ask a pollee to flip a coin. With probability p, the pollee will reverse his or her answer. Then no individual can be tied with 100% certainty to an answer, but the aggregate results can be verified.

"How many Bush supporters are in this room?" - Moni
"Exactly one quarter." - Christos

Here is the problem: what if the pollee ignores the coin and always answers with his or her "correct" answer? This then throws off the results.

Moni recast the polling problem in terms of two strategies for answering, strategy A and strategy B. The problem is to force the pollee to commit to one of the strategies based on the pollee's "correct answer." On the flipside, the pollee should be assured that the poller does not learn which strategy, even if the poller cheats in some way.

Enter the scratch-off cards. These are cards divided into squares. Each square has special surfacing that prevents anyone from viewing the contents of the square. The surfacing can be "scratched off," revealing the square but also revealing that someone has scratched off that piece of the card.

For the scratch-off polling protocol, the poller creates 2x2 cards where each of the 4 inputs is either a 1 or a 0. We make the restriction that each row can have at most one 1 and one 0, but otherwise generate uniformly at random. Moni then showed how a pollee can use these cards to scratch off 3 of the 4 inputs in a way that encodes his or her answer. Someone asked how the poller would know which 2 were scratched off first; Moni responded that this information was exactly what is being hidden from the poller, since the first 2 encode the "actual" answer of the pollee. He then went on to show us how this protocol committed the pollee to a specific answer. He also stated that the protocol was safe even with cheating pollers.

Umesh wanted to hear more about the proof that a cheating poller gains no information about the pollee's input. Moni replied that this wasn't illuminating and a bit tedious: basically it comes down to enumerating cases. The main result is that the probability the cheating poller is caught turns out to be independent of the pollee's input.

The scratch-off in the context of polling is a cute technique, but there are limitations. Someone asked about what happens if the voter simply acts as if his or her vote were the opposite - i.e. plays "correctly" but with the "wrong" input. Moni responded that there is a limitation to what you can do; there is no way to force someone to play with their true vote. As Christos pointed out, "you can't change human nature." Moni pointed out that this was why he assumed the pollee was being paid to complete the protocol correctly. Later, he went on to point out the issue of structuring incentives as an open problem in this area.

Another limitation, also caught by the audience, is that the pollee knows her result before returning it. Therefore, the scratch-off polling is only "weakly secret"; the pollee knows the answer before the poller does and can intentionally spoil a scratch-off form to skew the survey results. It turned out later in the talk that this was no accident, but in fact this "weak" property cannot be hacked around.

From this we went to a discussion of a zero-knowledge proof for solutions to the game Sudoku. "Has the Sudoku craze reached this part of the world yet?" "Don't tell us..." Moni explained the game and set up the problem to solve. Here, Alice has a solution to the game and wishes to convince Bob she knows a solution without revealing it. He then showed a zero-knowledge proof (ZKP) for Sudoku that makes use of scratch-off cards of the following special form: the cards have a "header" that contains a number in the clear, and then a number of squares attached to the header that are scratch-off, but for which we are promised the number is the same as the header. Furthermore, the squares can be detached from the header and separated into individual scratch-off squares. Moni then showed how a prover and verifier can use these squares to obtain a Sudoku ZKP.

Moni pointed out that the Sudoku ZKP requires some strong assumptions. In particular, the scratch-off squares must be indistinguishable even after they have been detatched and scratched-off. Moreover, we must assume that the players cannot generate scratch-off squares of their own; otherwise they could simply use bogus squares where the header number does not match the body squares. The payoff is that the resulting ZKP has perfect soundness; there is no chance a prover can cheat the verifier.

The perfect soundness, actually, seems to be the coolest thing about the Sudoku scratch-off protocol. Moni drew repeated attention to it during questions. It is interesting to note that this is at least the second time Moni Naor has used a special type of bit commitment to obtain a ZKP with nifty properties. His CRYPTO 2000 paper with Dan Boneh uses "timed commitments," which are commitments that can be forced open after enough time. They then note these can be used to place timing restrictions on the adversary in the setting of concurrent zero-knowledge, leading to concurrent zero-knowledge protocols more efficient than is possible otherwise (at least, given black-box simulation).

Robi was a little concerned about the use of a shuffle as part of the Sudoku ZKP. He pointed out that if we were to try implementing the Sudoku protocol online, the shuffle would be quite expensive. Moni pointed out that this was true, but the protocol was intended for use between two physically present players, where the shuffle step would presumably be easy.

Finally, no theory result in cryptography would be complete without a thorough examination of all the eidetic variations of a new concept. In this case, Moni outlined three different types of commitments: "weak locks," "scratch-off," and "indistinguishable envelopes." It took a few back-and-forths with the audience to flesh out the differences, but here's what I came away with:

As it turns out, the range of cryptographic protocols achievable in these models is different:

Someone asked for the definition of Oblivious Transfer. Moni made reference to a workshop in Haifa on "25 years of Oblivious Transfer," then gave a definition: Alice holds two items A and B, then Bob obtains one of the items chosen at random. Bob ends up with the item, but Alice doesn't know which it is. Killian showed that this primitive, introduced by M.O. Rabin is sufficient for obtaining secure function evaluation. Therefore, the fact that the Indistinguishable Envelopes model allows Oblivious Transfer is quite surprising. Moni can show that it is not possible given Scratch-Off or Weak Locks alone.

Moreover, we then discovered why the polling scratch-off protocol must necessarily be "weakly secure." If there were a "strongly secure" polling scratch-off protocol, then this protocol could be used to implement Oblivious Transfer in the scratch-off model. This would contradict the impossibility result. Cute!

We skipped over the slides outlining the coin flipping protocol for the Scratch-off and Weak Locks model. Someone asked if the coin flipping protocol was implementable by a human; Moni replied it was not, since it needed hardness amplification, and once we hit that territory protocols blow up beyond human capacity.

Moni then left us with this intriguing question: do zero-knowledge proofs for all of NP exist in the Weak Locks model? The "standard" ZKP for Hamiltonian Cycle, for example, fails to work because the adversary can simply force open all the Weak Locks and learn everything. Moni outlined a different proof in which the cycle is constructed "edge-by-edge." He then sketched an argument that the proof is not zero-knowledge, but not full-knowledge either in the Weak Locks model. It might be interesting to try to put an upper bound on the knowledge complexity of this protocol, but Moni had not yet done so in a quantitative way. Whether or not an alternative protocol exists that is truly zero-knowledge (or *can* exist) is an open question.

I also asked about whether the Weak Locks model would be sufficient for the collusion-free protocols of Lepinski, Micali, and shelat. This is because their paper talks about the necessity for some kind of "physical envelope" for parties to commit to randomness at the beginning of a protocol. It's not clear (to me, anyway), where that kind of "envelope" might fall in comparison to these new envelopes.

We then applauded, thanked the speaker, and headed out.


[1] Actually, not all envelopes are tamper-evident, even ones intended to be so. Recently, Bond, Murdoch, and Clulow found ways to look inside the contents of "secure" envelopes used by banks to mail PINs, debit cards, and other sensitive items. Oops.