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

Abstract:

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