DIMACS Workshop on Complexity and Cryptography: Status of Impagliazzo's Worlds

June 3 - 5, 2009
Princeton University

Boaz Barak, Princeton University, boaz at CS.Princeton.edu
Salil Vadhan, Harvard University, salil at eecs.harvard.edu
Presented under the auspices of the Special Focus on Hardness of Approximation and the Special Focus on Communication Security and Information Privacy.

Cryptography is a science that has become crucial to many private, commercial, and government activities. But these activities depend on the security of the utilized cryptographic schemes for encryption, authentication, etc., which in turn are based on the presumed intractability of certain computational tasks describing an adversary's computation. Unfortunately, at the moment we do not know how to prove that the adversary's tasks are truly intractable.

Minimizing the reliance of cryptographic schemes on unproven assumptions is a fundamental goal of cryptography. One reason is that basing schemes on false assumptions could have devastating consequences for security when the schemes are in practical use. Another reason is that by studying the relations between assumptions and the minimal assumptions needed for certain tasks, we gain deep insights into what makes cryptographic schemes secure, and how we can improve upon them.

The workshop will aim at advancing the state of the art in this field. It will feature talks that discuss the progress made to date and as well as identifying important remaining open problems.

An important facet of cryptographic schemes is the assumptions on which they are based. One important theoretical direction in this area is the goal of basing more cryptographic schemes the most general assumptions possible, e.g., solely on the existence of one-way functions. The workshop will discuss recent results that do so for the case of statistical zero knowledge arguments and statistically hiding commitment schemes. We will also highlight tasks for which the current best constructions need stronger assumptions.

It is often desirable to base cryptographic schemes on worst-case hardness assumptions, as we currently have a better understanding of worst-case hardness than average-case or every-case hardness. However, this can be problematic in general, as it does not necessarily yield the necessary hardness needed to defeat an adversary. The workshop will discuss progress in using worst-case assumptions on certain problems, such as problems over lattices, and the open questions in this area.

Another direction the workshop will address is the limitations of current cryptographic techniques. In this area, we will seek to better understand the limitations of our techniques as well as to seek ways to bypass these limitations. For example, many techniques used in cryptography are of the black-box type, which are known not to be strong enough to solve some of the above questions. We will discuss some of the recently discovered non-black-box techniques and highlight open questions on whether they can be applied in other settings. We will also discuss some results that show that resolving some questions cannot be done with certain types of techniques and open questions about these whether these results can be extended to cover all known techniques.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on October 9, 2008.