Posted by: jonkatz | August 26, 2009

## Crypto highlights

There’s an upcoming post I’m more interested in at the moment, so let me get this obligatory post out of the way. 😉

For various reasons, I missed Crypto and Eurocrypt each of the past 2 years. The truth is, sometimes I am a bit ambivalent about going to Crypto: I occasionally find the atmosphere very pressurized, with people sometimes being more interested in “selling” their results, or in “pushing” new results, than in discussing the underlying science. (An example of this is the rump session, where in some conferences people discuss open problems and ongoing research, while in crypto people market their finished results. Case in point here where, as far as I could tell, the “open problems” session contained only one piece of ongoing work.)

This year, it didn’t bother me as much — maybe I avoided those discussions, or maybe getting tenure reduced some of the pressure I had felt in the past. In fact, Crypto this year was great. It was wonderful to speak with some people I hadn’t seen in a while, as well as to meet new people, some of whom I had only previously “talked to” over email or in on-line PC meetings. I also got a chance to discuss lots of interesting technical issues.

Other thoughts and highlights:

• Is it just me, or is it really difficult to get much from a 20-minute conference talk? Some of the talks were just bad, other talks were fine but I much prefer a setting where I can ask questions in the middle of the talk — that way you don’t lose everything if you miss one slide.

I do think that we, in general, could do a better job of making our talks accessible to a wider audience. I tried to follow a cryptanalysis talk, really I did, but was lost by the second slide.

• The talks that stood out for me were:
• “How to Encipher Messages on a Small Domain: Deterministic Encryption and the Thorp Shuffle”: A really nice result, and Phil Rogaway gave a fantastic talk.
• “How Risky is the Random-Oracle Model”: Although I might quibble with some aspects of Phong’s presentation, the paper shows several attacks and raises some interesting questions.
• “Abstraction in Cryptography”, an invited talk by Maurer. Although I did not agree entirely with his claims that abstraction always makes things simpler, he did give one example that nicely illustrated his point.
• A sociologically interesting talk at the rump session, though I do not know what to make of it: “An alternative to Gentry’s fully homomorphic encryption scheme (We Do Exist!)”. The claim was that the authors had posted a paper on eprint, around the same time Gentry submitted his paper to STOC, that also described a fully homomorphic encryption scheme. As best as I can tell (this is based on a quick read and discussion with some other people), their paper does not quite show a fully homomorphic scheme but does show how to handle $t$ multiplications (and an unbounded number of additions) for any desired $t$. Anyway, what I found more interesting about this was the questions it raises about how results are accepted in the crypto community.
• Jobs seemed to be on everyone’s mind, or maybe I am overly sensitive to it because I had a student graduating this year. Fortunately, the crypto job market seemed relatively strong to me (certainly compared with the rest of TCS), with both industry and universities hiring and several postdoc positions available.

I’m already looking forward to next year!

## Responses

1. Someone told me that in the work on homomorphic encryption you mention, the ciphertext size also grows with multiplications

2. Vipul, I know of another proposal based on tensor products wherein the ciphertext size blows up with each multiplication. I don’t if that is also true of the work Jon mentions…

3. The (declared) purpose of that talk was to present an alternative to Gentry’s *for practical applications*, where a bound on the number of multiplications to be done can be established in advance

4. Jon, several of your points contain very little information for someone who was not there. For instance, can you elaborate on:
– what was Ueli’s main point, what was the nice example based on, and what aspects did you disagree with?
– what are your thoughts on the questions raised by that talk regarding how results are accepted in the crypto community?

Also, the slides you linked to explicitly say they do leveled fully homomorphic encryption (ie first fix the number of multiplications). Still, it’s true that I’ve never heard of that result, and I heard of Gentry’s result from all the sources these people quote and more… indeed raises interesting questions… (if I had a blog I’d share my thoughts on them!)

5. Jon, several of your points contain very little information for someone who was not there.

You are right, I realized this as I was writing it… 😉

I’ll discuss Maurer’s talk in a later post.

As for the fully homomorphic encryption, I think the point there is pretty obvious: your result will be more easily accepted by the community the better known you are, and it helps to give talks (as well as tell others) about your research. More generally, it reminds us once again that science is not completely “pure” but partly a social endeavor.