Generic Case Complexity
August 13 to August 17, 2007
American Institute of Mathematics,
Palo Alto, California
and Rebecca Wright
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
Participants will be encouraged to assemble in groups to consider
questions like the following.
- 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.
There will also be introductory lectures and problem sessions.
- 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
- The relation of generic-case complexity to worst case and average
case complexity is fairly well understood. What about other complexity
Material from the workshop
A list of participants.
The workshop schedule.
A report on the workshop activities.