Organizer: Vukašin Karadžić, TU Darmstadt, Cryptography and Network Security Group

Abstract

The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper/talk

Russell Impagliazzo: “A personal view of average-case complexity” available at https://ieeexplore.ieee.org/document/514853

with the following abstract:

“The structural theory of average-case complexity, introduced by Levin (1986), gives a formal setting for discussing the types of inputs for which a problem is difficult. This is vital to understanding both when a seemingly difficult (e.g. NP-complete) problem is actually easy on almost all instances, and to determining which problems might be suitable for applications requiring hard problems, such as cryptography.

The paper attempts to summarize the state of knowledge in this area, including some ”folklore“ results that have not explicitly appeared in print. We also try to standardize and unify definitions. Finally, we indicate what we feel are interesting research directions. We hope that the paper motivates more research in this area and provide an introduction to the area for people new to it.”

Meeting link

For participation a meeting link is required. If you want to participate in the virtual format, please contact the organizer (see above).

More information

CROSSING Wiki