[tech] the theory lunch and zero knowledge proofs

every wednesday at noon the theory group gives a theory lunch, where faculty and students from computer science and other departments get together, eat lunch, talk about life and what they're working on, and listen to one speaker give an informal talk on some problem they are working on.

today we had indian food. and quite good indian food! the saag paneer was first-rate, and there was a really good fish curry. i've never thought of fish curry as particular indian, but this fish curry was excellent.

anyway, the talk given today was about cryptographic protocols and zero-knowledge proofs. info about the speaker, Moni Naor.

i honestly don't know a lot about cryptography or these protocols, but i learned quite a bit nonetheless. the first protocol was motivated by polling (see the paper for more detail here). imagine that alice wants to take an exit poll after a vote. however, many voters don't like to reveal how they voted. but suppose alice does this. let's call the two candidates D and R. alice makes a scratch card with 4 entries like so:

DR
RD

initially all these letters are covered, and the position of each D and R in a row is randomly chosen. so another potential card is:

RD
DR

or

DR
DR

but NOT:
DD
RR

namely, each row must contain the two different candidates.

Alice hands this scratch card to Bob, who just voted. Now Bob must follow these instructions: he randomly chooses to reveal 1 entry from each row. So suppose this is what bob does:

Initial Card:
o o
o o

Bob scratches:
D o
o R

Bob gets one more scratch. Bob's vote is indicated by the single revealed entry in the row that still contains one hidden entry. So in this situation, suppose Bob is a D man. Since he knows that the row with only one revealed entry will be the row that indicates his vote, he scratches the second line:

D o
D R

and hands his scratch card back to Alice. Alice tallies Bob's vote as D.

Ok so now here's the trick: suppose Bob's initial scratches reveal this:

R o
R o

In this case, whether Bob wanted it or not, when he hands his scratch card back to Alice, he'll vote will be tallied as an R vote.

Now notice this: in 3/4 of Bob's scratchings, he'll be able to indicate the candidate he truly voted for. This is because if he scratches out a D and an R first, then he can choose D. If he first scratches out R and R, then he must choose R. But if he scratches out D and D, then he is forced to choose D, his real vote. So 75% of the time, Alice will get the correct vote, and in ALL CASES, Alice will NOT KNOW Bob's true vote (she could guess 75% of the time correctly, but in an individual case she really has no idea).