Reading the Crypto Classics: Goldreich, Goldwasser, Micali: “How to construct random functions”

26.02.2020 10:00-11:00

Speaker: Patrick Harasser, Cryptoplexity Group | Location: Hochschulstraße 10 (S2|02), Piloty Building, Room A102, Darmstadt

Organizer: Christian Janson

This talk is the fifth 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

Goldreich, Goldwasser, Micali: “How to construct random functions” (Journal of the ACM 1986) (DOI: 10.1145/6490.6503)

with the following abstract:

„A constructive theory of randomness for functions, based on computational complexity, is developed, and a pseudorandom function generator is presented. This generator is a deterministic polynomial-time algorithm that transforms pairs (g, r), where g is any one-way function and r is a random k-bit string, to polynomial-time computable functions ƒ_r: {1, … , 2^k} → {1, … , 2^k}. These ƒ_r's cannot be distinguished from random functions by any probabilistic polynomial-time algorithm that asks and receives the value of a function at arguments of its choice. The result has applications in cryptography, random constructions, and complexity theory.“

Further information