# Oddly Shaped Pegs

An inquiry into the Nature and Causes of Stuff

## 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 $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.

March 16, 2009 at 9:36 pm

Posted in Crypto 2.0

Tagged with , , , ,

## Bringing crypto online

John Langford recently blogged about the “vetocracy” that is the dominant CS conference reviewing process. I agree that there are many problems with the process. That is good fodder for a whole sequence of posts; just not today. I did, however, seize on a point that John made along the way:

“It’s hard to imagine any research community surviving without a serious online presence. When a prospective new researcher looks around at existing research, if they don’t find serious online discussion, they’ll assume it doesn’t exist under the “not on the internet so it doesn’t exist” principle. This will starve a field of new people. […]”

So what about cryptography? There are of course millions of good and bad web resources about computer security. But there is very little about foundational “crypto” as it appears at conferences like Crypto or Eurocrypt, PKC, SFE, CHES, etc (never mind TCC, STOC or FOCS).

• Blogs: Luca Trevisan blogs actively about topics in theoretical CS, including cryptography. Luca has more crypto in his little finger than most “cryptographers” have in their whole body. Still, crypto remains a minor topic on his blog (exceptions: lecture notes, STOC ’09 picks).
• Wikipedia: this is an odd metric of “online-ness”, but nonetheless revealing: wikipedia entries for theoretical crypto are very limited (indeed, for TCS generally). I’m  experimenting this semester to see if the students in my class can help, but that will still be just a drop in the sea. For a sampling of what’s out there, see Wikipedia’s Theoretical Crypto category.
• Mailing lists, discussion fora: Nada?
• Other resources: Oded Goldreich maintains  variety of ad hoc web pages on aspects of crypto and complexity theory. Perhaps most relevant here is his selection of recent papers in TCS. Upside: it is fascinating to get Oded’s take on anything; downside: the noninteractive format makes the information flow, well, one way.

I will attempt to contribute in my copious free time, in particular, I hope, by blogging about papers at the upcoming TCC. But that’s a relatively minor contribution.

Some questions, then: What resources would help us advance TC as a field and as a scientific community? How can we get more “serious online discussion”? (What resources are out there already that aren’t listed above?)

Update (7/9/09): Since I initially wrote this post, a few more theory-of-crypto blogs have come to my attention, notably Jon Katz’s.  Helger Lipmaa maintains a list of crypto blogs (or, more accurately, blogs by cryptographers) here.