DIMACS Theoretical Computer Science Seminar

Title: Combining Cryptographic Primitives

Speaker: Joe Kilian, Rutgers University

Date: December 6, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


Cryptographic primitives can be based on a number of seemingly independent computational assumptions: the hardness of factoring, the hardness of computing discrete logarithms, etc. By choosing one particular assumption, we play cryptographic roulette, losing all our security if this assumption should fail. Wouldn't it be nice if we could make a protocol that survived as long as one of our assumptions held?

We formalize and study techniques for combining cryptographic primitives. We observe that combiners exist (and were well known) for one-way functions, and also for secret key agreement. On the other hand, we give evidence that only weaker forms of combiners exist for basic problems in secure computation. In this talk, I will try to highlight some open problems to work on and potential applications of our techniques.

Joint work with Danny Harnik, Moni Naor, Omer Reingold and Alon Rosen