Posted by: jonkatz | September 17, 2009

Polycrypto project?

You may have heard about the successful polymath project, and a second one now ongoing. Luca recently wrote about this as well.

What would make a good “polycrypto” project? (I.e., a crypto-related research question that people could successfully work on in a distributed fashion.) I thought about it a bit, but nothing struck me. Some musings, though:

  • It would have to be a problem that’s neither too easy nor too hard; that is sufficiently compelling to sufficiently many people; and where even partial progress would be interesting.
  • What kinds of problems are best suited to having large numbers of people contribute in relatively small increments on a wiki? I guess it would be problems that require expertise in different areas; that have no clear path to a solution; and where the solution is likely to be comprised of many small steps rather than one key breakthrough. But I’m really guessing here.
  • Is crypto deep enough to have problems difficult enough for such a project? Let me explain what I mean. In mathematics, people are generally experts in their own (sub)-sub-area and are less up-to-date on material outside their own expertise; moreover, some of the deepest math problems seem to require techniques from one or more areas. On the other hand (and generalizing a bit), people in crypto are usually familiar with several areas, and there are not many problems that “straddle” two or more areas.
  • Maybe it’s just my perception, but I feel like the general attitude in crypto is less receptive to sharing problems/ideas/credit than in math. Thus, people might be unwilling to propose their “favorite problem” for a polycrypto project, and people may be unwilling to contribute to a paper if their name will not appear on it. (For what it’s worth, I would rather have the names of everyone who contributed to the solution appear on the published paper, rather than have the paper published under a pseudonym [as was done for the polymath project].)

We can test the last statement now: please post if you have any ideas about a good candidate problem!



  1. Wow, no comments? That really does confirm your last statement.

  2. Sad.

  3. I’m willing to bet that people just can’t think of a suitable problem. Jon is right that the problems don’t seem “deep” enough in that they require experts in many different areas or subareas, and thus they seem unlikely to benefit from a “polycrypto” attack. A way to test this would be to ask readers to comment (perhaps anonymously) on whether they can’t think of a suitable problem, or they can but aren’t willing to share.

  4. Here goes my attempt at a problem. The problem is about building cryptographic primitives from assumptions based on learning parity with noise (LPN).

    Here is the cryptographic landscape in the LPN world: we can build a whole bunch of primitives based on LPN, namely one-way functions (and all you can get from it), key exchange protocols, OT and public-key encryption (and maybe even trapdoor functions). One thing that is conspicuously absent from the list is collision-resistant hash functions (CRHF). That is my question: construct a CRHF from (some variant of) LPN.

    A note: In the closely related learning with errors (LWE) world which is, roughly speaking, the same as LPN except over a large field rather than GF(2), we can in fact construct CRHFs.

    Does this problem satisfy any/all of Jon’s criteria? I think it satisfies at least the division of expertise criterion in a weak sense; the problem will benefit from general crypto expertise as well as lattice expertise (are they “sufficiently different” areas of expertise? I don’t know).

    The problem is probably not “too easy”. I have made some (ultimately unsuccessful) takes at it (along with others). On the other hand, perhaps it is well-known (and thus, “too hard”)?

  5. Anon, can you give the reference for construction of CRHF based on LWE?

  6. Anon above: the CRHF goes back to Ajtai’s work on lattice-based crypto. See for example Micciancio and Regev’s FOCS 2004 paper for the (simple) construction.

    Actually collision resistance is based only on the SIS (“small integer solution”) problem, which is basically a homogeneous version of subset-sum over Zq^n. SIS is at least as hard as LWE (for appropriate parameters).

    I’d expect a similar relationship to hold between SIS over Z_2^n and LPN, which would give a CRHF. One complication is that the LPN problem would need a smallish bias, say 1/sqrt(n) or less (this may not “count,” depending on whom you ask). I guess another issue is that the Hamming weight of the hash input must be small enough so that the accumulated biased error terms remain biased. Probably anon has done the calculations and they don’t work out favorably :).

  7. I don’t think that our field is old enough to have very good polycrypto problems. Math is thousands of years old; modern crypto is 35, tops!

  8. Chris – don’t forget al-Kindi. 🙂

    But in general, polymath4 could be seen as a polycrypto project, a good one in the sense that the question is relevant for us but it is tackled by mathematicians too. (Well, it is actually not tackled by any cryptographers – except I’ve seen a contribution by Avi W.)

Leave a Reply

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

You are commenting using your 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: