### DIMACS Workshop on Cryptography and Intractability

#### March 20 - 22, 2000

DIMACS Center, Rutgers University, Piscataway, NJ

**Organizers:**
** 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.