Generic Case Complexity

August 13 to August 17, 2007

at the

American Institute of Mathematics, Palo Alto, California

organized by

Robert Gilman, Alexei Miasnikov, Vladimir Shpilrain, and Rebecca Wright

Original Announcement

This workshop will be devoted to exploring the potential contribution of generic-case complexity to cryptography. Generic-case complexity is a new complexity measure which seems to be useful for assessing the algorithmic security of public key cryptosystems. The intended intended participants include cryptographers, mathematicians, and students.

The main topics for the workshop are

  1. Introduction to generic-case complexity
  2. Relation of generic-case complexity to other complexity measures;
  3. Application of generic-case complexity and generic properties of mathematical structures to the cryptanalysis of public key systems;
  4. The generic structure of hard problems.
Participants will be encouraged to assemble in groups to consider questions like the following. There will also be introductory lectures and problem sessions.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.