Generic Case Complexity
August 13 to August 17, 2007
at the
American Institute of Mathematics,
San Jose, 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
- Introduction to generic-case complexity
- Relation of generic-case complexity to other complexity measures;
- Application of generic-case complexity and generic properties of
mathematical structures to the cryptanalysis of public key systems;
- The generic structure of hard problems.
Participants will be encouraged to assemble in groups to consider
questions like the following.
- Generic methods have proved useful in cryptanalysis of braid group
cryptosystems. To what extent do they apply to other systems?
- Several hard problems e.g., the halting problem for Turing machines
with semi-infinite tape, are generically easy. How general is this
phenomenon? Find some decision problems which are not generically
easy.
- The relation of generic-case complexity to worst case and average
case complexity is fairly well understood. What about other complexity
measures?
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.
Papers arising from the workshop: