Organizer: Christian Janson
This talk is the second one in the seminar series “Reading the Crypto Classics” for the winter term 2019/2020. 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
Micali: “CS Proofs (Extended Abstract)” (FOCS 1994)
DOI: 10.1109/SFCS.1994.365746 with the following abstract:
“This paper puts forward a computationally-based notion of proof and explores its implications to computation at large. In particular, given a random oracle or a suitable cryptographic assumption, we show that every computation possesses a short certificate vouching its correctness, and that, under a cryptographic assumption, any program for a NP-complete problem is checkable in polynomial time. In addition, our work provides the beginnings of a theory of computational complexity that is based on ”individual inputs“ rather than languages.”