TCC, Day 1

(Presenting partial, i.e. biased and incomplete, coverage of the conference talks, lunch discussions, and ideas “in the air” at TCC 2009)

Attending TCC is always a pleasure: the community is friendly, and the topic is narrow enough that I can usually understand all the talks at the conference. I don’t have time to write about all the day’s talks, but here are some of my notes…

The morning session talks focused on “fairness” in secure function evaluation (SFE). Roughly, a distributed SFE protocol is fair if either all honest players get the correct output, or none of them get the correct output. In 1986, Cleve showed that no two-party coin-flipping protocol that resists malicious behaviour from either party can be fair: it is always possible for either Alice or Bob to cheat and bias the result of the coin-flip somewhat.

Recently, Gordon, Hazay, Katz and Lindell showed that, nevertheless, several functions (such as the greater-than function) can be computed fairly by two mutually untrusting parties. This work was the backdrop for the first two papers of the morning:

• Tal Moran gave a great talk explaining a coin flipping protocol that matches Cleve’s lower bound on the bias that some cheating party can impose on the coin’s value. The r-round version of the new Moran-Naor-Segev protocol has bias whereas the previous best achievable bias was

  This result is surprising because (a) the protocol is very simple, and (b) Cleve and Impagliazzo had previously shown a lower bound of in a restricted model. Because of (b), Tal  (and others) had initially assumed that the real optimal bias was This is a nice example of a long-standing problem where the common wisdom was pointing in the wrong direction, yet whose solution was simple. The tool kit for the solution came, in part, from the GHKL paper on perfectly fair protocols for functionalities that are very different from coin-flipping, which brings us to talk 2…

• … in which Dov Gordon (of GHKL) discussed the difficulties of extending the GHKL two-party fair protocols to larger number of parties.  The results are still very partial, but it seems that fairness, even with 3 parties, is much mroe complicated than fairness with two parties. The interesting part here is the failure of the folklore that “anything” you can do with 2-parties, one of whom may be cheating, can be done with n parties, n-1 of whom may be cheating.

Another nice aspect of the recent fairness papers is the influence that (I think) the work on fair protocols for rational players has had on fair protocols for the traditional cryptographic model of malicious players. Although some of the connections are obvious (everybody seems to like the “commit to shares of the secret and reveal gradually” approach), my feeling is that there is a more subtle connection to be discovered…

There were of course many other great talks in the day. A particular highlight was Chris Peikert’s invited talk on lattice-based crypto. Chris does a remarkable job of pairing down the notation and definitions necessary to explain the basic results in the area. No doubt there are more good things to come out of this area.

Another highlight (for me!) was Shabsi Walfish’s talk on our joint work on deniability in the face of “online” attacks… which I will demurely refrain from plugging excessively here.

Advertisement