Oddly Shaped Pegs

An inquiry into the Nature and Causes of Stuff

TCC, Day 1

with 5 comments

(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 O(1/r), whereas the previous best achievable bias was O(1/\sqrt{r}).

    This result is surprising because (a) the protocol is very simple, and (b) Cleve and Impagliazzo had previously shown a lower bound of \Omega(1/\sqrt{r}) in a restricted model. Because of (b), Tal  (and others) had initially assumed that the real optimal bias was O(1/\sqrt{r}). 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.

Advertisements

Written by adamdsmith

March 16, 2009 at 9:36 pm

Posted in Crypto 2.0

Tagged with , , , ,

5 Responses

Subscribe to comments with RSS.

  1. I believe you should say Moran-Naor-Segev rather than Moran-Naor there.

    Sam

    March 17, 2009 at 2:07 am

    • Fixed, thanks (and sorry, Gil)!

      adamdsmith

      March 17, 2009 at 10:49 am

  2. Are we going to see more posts after the FOCS deadline?

    Omkant

    Anonymous

    April 2, 2009 at 10:53 am

    • Adam: please write something 🙂

      vipul

      May 7, 2009 at 10:30 am

  3. I like the fact that the conventional wisdom was wrong on the coin bound.

    rjlipton

    July 9, 2009 at 2:00 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: