DIMACS Workshop on Cryptography and Intractability

March 20 - 22, 2000
DIMACS Center, Rutgers University, Piscataway, NJ

Moni Naor, Weizmann Institute of Science, naor@wisdom.weizmann.ac.il
Joe Kilian, NEC Research Institute, joe@research.nj.nec.com
Shafi Goldwasser, MIT and Weizmann Institute of Science, shafi@theory.lcs.mit.edu
Presented under the auspices of the DIMACS Special Year on Computational Intractability and the DIMACS Special Year on Networks.

Cryptography is arguably the ultimate application of computational hardness. Almost every cryptographic task requires the existence of a one-way function, and some tasks seem to require even stronger hardness assumptions. Conversely, ideas from cryptography have been used to establish the intractability of computational tasks. The goal of the workshop is to explore this tight relationship.

The workshop will be organized around the following themes:

1) The minimal intractability assumptions required for various cryptographic tasks.

2) The feasability of basing cryptography on worst-case assumptions.

3) The proper form for an intractability assumption.

4) The relationship between cryptography and areas such as:
- Computational Learning Theory
- Proof Complexity
- Game Theory
- Combinatorial Optimization: worst-case and average-case analyses

For each of these topics there will be an introductory plenary talk, followed by more specialized talks. Less structured sessions where these issues will be discussed are also planned.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on September 3, 1999.