The list of papers accepted to STOC 2010 is out. Several interesting crypto and related papers, though many of them are (to the best of my knowledge) not yet on-line.

An interesting observation: I noticed at least one paper got accepted that was rejected at least twice before from “weaker” conferences. (To the best of my knowledge, the content of the paper has not changed. Of course, I could be wrong.) Rather than speculate which PC made the “right” decision and which made the “wrong” decision, or re-hash the arguments about anonymous vs. non-anonymous submissions, let’s just chalk this up as more evidence of the high degree of variability in conference acceptance decisions.

That digital signature schemes can be constructed based on the (minimal) assumption that one-way functions exist is surely one of the major successes of theoretical cryptography. Reviewing this result recently as part of a survey I am writing, it struck me how complicated the construction is. At a high level, the construction proceeds like this:

1. Start with a one-time signature scheme whose message length is twice as long as its public-key length. These are not easy to construct, and appear to require a universal one-way hash function (which can be constructed from any one-way function).
2. Use in a binary tree to obtain a (many-time) signature scheme $\Pi$.
3. Step 2 actually gives a scheme that is stateful. One can obtain a stateless scheme by applying an idea due to Goldreich that relies on pseudorandom functions (which can be constructed from any one-way function).

Step 2 is fairly easy, and is described in my book. Given a universal one-way hash function (UOWHF), step 1 is not trivial (the issue is that the hash function may have an extremely long key) but it’s not too hard either. Given a pseudorandom function (PRF), step 3 is standard.

The problem is that if we want a complete proof that one-way functions imply signature schemes, we must also prove the existence of UOWHFs and PRFs based on one-way functions. These proofs are themselves quite involved (though there has been some work simplifying them in the past few years). So a complete proof that one-way functions imply signature schemes would run to something like 100 pages. (If I’ve missed something please let me know.)

And let’s not forget about efficiency. Step 2, above, is inefficient by the standards of practical crypto, but not terribly inefficient by the standards of theoretical crypto: scheme could be implemented fairly easily, and (for practical parameters) would “only” be a factor of 100 or so slower than . But building an actual UOWHF or a PRF from a one-way function seems out of the question.

Do things get better, in terms of complexity, if we are willing to make (slightly) stronger assumptions? Unless we are willing to rely on the random oracle model, the answer is: not much. Assuming (trapdoor) one-way permutations allows for simpler constructions of UOWHFs and PRFs, but still all 3 steps sketched above are necessary. Assuming collision-resistant hash functions gives UOWHFs trivially, but doesn’t help with constructing PRFs and doesn’t allow us to eliminate any of the above steps.

Is this inherent? There has been some work proving lower bounds on the efficiency of one-time signature schemes, but to my knowledge no results showing any inherent efficiency “gap” between many-time signatures and one-time signatures. But an even more interesting question (to me) is whether the complexity of the construction can be improved (even at the expense of reduced efficiency). Is the reliance on a PRF to get a stateless scheme really necessary? Are universal one-way hash functions really needed in order to apply the tree-based construction of step 2? Or, for that matter, might there be a totally different approach that doesn’t rely on trees at all? Some hope for this — though I admit it is not much — is that the construction of a one-time signature scheme (or even a -time signature scheme) from one-way functions is simple and self-contained. Why should it be so much more difficult to handle an unbounded number of signatures than it is to handle an arbitrary, but bounded, number of signatures?

A few months ago I bought a Kindle DX, but after the initial excitement I find I have barely used it. Partly this is because I still have a preference for paper — in particular, I find myself flipping around a lot when reading papers and the Kindle, at least, did not handle this well. But I also quickly became disappointed with the Kindle itself. My dream was to load a library of research papers (and monographs, etc.) onto the device, and then have ready access to them whenever I needed to look something up. But, amazingly, the Kindle has no support for directories meaning that if you load too many papers you have to navigate through screen after screen to get to the one you want. (A few months ago, Amazon announced a plan to eventually support directories but I haven’t heard anything since.) In addition to this, I just didn’t find the Kindle very convenient to use: the delay when “turning pages” was noticeable, and I found the buttons clunky. (I’m not the only one.) Finally, the contrast for pdfs is lower (thus harder to read) than the contrast for native Kindle content. In particular, I found it hard to read in the dim light on an airplane — one of the exact times I would want to use it.

I expect, with time, all these issues will be fixed. Perhaps they have been fixed already — can anyone recommend an e-book reader specifically to be used for reading research papers in pdf?

Aaron Sterling’s recent post about ICS noted how well-funded theoretical computer science appears to be in China*, and contrasted the “malaise” toward theory in the US to the high regard in which theory seems to be held in China. (Being at an institution that, as a whole, does not seem to value theory certainly makes me sympathize with Aaron’s remarks. Having said that, I especially enjoyed the third comment on his post. [Go ahead and read it, I'll wait.] Not that I entirely agree with it — I just found it amusing.)

That post and the ensuing discussion raise the larger question: what is the “right” level of funding for theoretical computer science research? More broadly, how would one go about determining how much money “should” be allocated to any of the different sub-areas of CS? Yes, theory is important. But surely other areas of CS are important, too? (Maybe one or two areas are even more important?) We are used to grabbing as much money as we can for theory — both because theory has been historically underfunded (and under-appreciated?) and also because that’s the way the game is played by all academics — but consider this question: say you were in charge of allocating NSF’s budget for computer science research. How would you determine the “right” allocation? Of course, the question only becomes more complicated when you consider the allocation of funds across all the sciences.

I don’t have any immediate answers to these questions. I just find it interesting that, with all the (past) focus on increasing funding for theory (e.g., theorymatters.org, which hasn’t been active in a while), these questions haven’t been discussed. It’s easy to say “theory should be given more funding”, but harder to answer the question “in what areas should funding decrease in order for that to happen?”.

(*As an aside, I suspect that the total level of theory funding in the US is orders of magnitude more than the total level of theory funding in China. Tsinghua University has a high concentration of top-notch theorists, but how many theorists are there in all of China compared with all of the US?)

(Part 1 of what may be a series…)

I am loath to criticize federal grants too much, since they fund a good chunk of my salary…and yet…

In booking upcoming travel to Europe, I noticed a great fare of $600 available (this is for midweek travel, no weekend stopover, booked on relatively short notice). Unfortunately, that fare was on a non-US carrier — so due to the Fly American Act I will instead take a less convenient flight costing 3 times as much. A fine example of your* tax dollars at work!

The silly Fly America Act affects me every time I travel: always by forcing me to take a less preferable airline (US carriers seem to be the least comfortable, and offer the fewest amenities to the traveler), and usually by making me fly at less convenient times. But the price difference this time is truly egregious.

(*If you pay taxes to the US, that is.)

Decentralized Mechanism Design, Distributed Computing, and Cryptography Workshop

Just forwarding this along (though I will be speaking at this workshop also):

Organizers: Ittai Abraham (Microsoft), Dino Gerardi (Yale), and Joe Halpern (Cornell).

The Institute for Advanced Study is sponsoring a workshop on Decentralized Mechanism Design, Distributed Computing, and Cryptography, which will focus on issues at the boundaries of these three areas. We hope to bring together researchers in computer science and game theory who have been working on related topics, largely unaware of each others’ efforts, for over 20 years.

The workshop will be held on Thursday June 3 and Friday June 4, 2010, at the Nassau Inn, Princeton. We plan to have a relatively light schedule of speakers, allowing plenty of time for interaction between participants.

If you are interested in attending the workshop, please send an email to dcc.workshop {at} gmail(.)com, preferably before January, 25, 2010. Although registration is free, the number of attendees will be limited; we want to keep the workshop small to allow lots of interaction. We will respond to emails by January 31, 2010.

By now, there been lots of discussion in the blogosphere ridiculing the fact that video feeds from US UAVs (unmanned aerial vehicles) are unencrypted. (See here, here, and here.)

Bruce Schneier has another take on the issue, arguing that the military made the right choice not to encrypt. Schneier makes two points: (1) encryption is not the problem; key management is; (2) it’s not much of a concern whether the enemy can eavesdrop on the video feed. The second point seems right to me — it is no secret what areas the UAVs are monitoring, so it doesn’t really matter whether others can see the video. As for the first point, I agree to an extent: just to illustrate the point, consider that although it may be cheap to add encryption to the UAV, doing so would require providing decryption capability to everyone in the field looking at the feed; I have no idea how expensive or difficult that would be. On the other hand, the first point also reflects some of the endemic problems the military has in dealing with crypto in general.

More reading here.

A sensible discussion regarding whether “simple” algorithms should appear at SODA has been derailed in the comments by people arguing whether computer scientists have destroyed mathematics by using the notation “” to refer to the integer in that is congruent to modulo .

Although I find the opinions expressed in the comments extreme, and see nothing wrong with using in the sense above as long as it is clear to the reader, I have to say that I myself sometimes find the notation confusing. When Yehuda and I wrote our textbook, we noticed this and decided to write to refer to reduction of modulo , as opposed to for the “standard” mathematical notion of equality modulo . (As a personal preference, I don’t like using \pmod to write though I can understand others who choose to use it.) For that matter, we also distinguished between an assignment operator “” and the equality predicate “”. That way, the expressions “” and “” and “” can all be distinguished from each other.

While it’s ok to be pedantic and obsessive in one’s own writing (as I am), it seems wrong to require it of others especially if there is no danger of misinterpretation.

In case you haven’t noticed, I’ve added a twitter feed to this blog.

I’ve never been a big fan of twitter as a social networking tool. (Believe me, the last thing people need to know is what I’m doing every half hour.) I’ve had an account for a while — I wanted to reserve the name (and I still couldn’t get jkatz) — but my first tweet was today. It seems to provide a useful way to link to relevant articles without having to write a whole blog post.

On the other hand, so far I find it kind of “dry” since no one can post comments about the stuff I’m linking to — i.e., there is no two-way communication. What do the readers think? (Feel free to also use this space to comment on any of the tweets I’ve posted so far.)

In recent news, Microsoft New England has apparently hired Boaz Barak. (Though I could not find any announcement by Microsoft, or any indication on Boaz’s webpage.) This comes on top of Microsoft’s recent hires of Madhu Sudan and Omer Reingold (in Silicon Valley). One could argue that were MSR New England an academic department, it would rank among the top 3 in theoretical computer science. (Of course, one could also argue that were MSR New England an academic department many of the people would leave and the productivity of those who remain would be cut by half…)

I have to admit to feeling a bit jealous, as MSR New England is one place I would love to go… (and yes, I’ve “applied”).

I don’t want to re-hash the debates about academia vs. industry. (Anyway, it is not a fair comparison in any of these cases since Boaz, Madhu, and Omer are getting the benefits of industry without having to give up the benefits of tenure.) I’m more interested in the question of what Microsoft expects to get out of these hires? Or, more bluntly, how does Microsoft expect any of these hires to impact its bottom line? I am not asking about the value of TCS research in general, which I think is clear. I am asking, in particular, about hiring people who are about as far from practice as possible. I don’t think comparisons to “the old Bell labs” work here: the fundamental physics work done at Bell labs seems, to me, much closer to yielding practical benefits than fundamental work on complexity theory. I also don’t buy the arguments about these hires being public relations coups: how many people, outside of the attendees of STOC/FOCS, would recognize these people’s names? And for how many people will this affect their decision of whether to apply to Microsoft for a job, or buy Microsoft products?

But maybe I’m missing something. Any thoughts?