Organizer: Christian Janson, TU Darmstadt, Cryptoplexity Group
This talk is the fourth one in the seminar series „Reading the Crypto Classics“ for the very special winter term 2020/2021. 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
Naor, Reingold: „Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions“ (FOCS 1995); DOI: https://doi.org/10.1006/jcss.1998.1618
with the following abstract:
„A pseudo-random function is a fundamental cryptographic primitive that is essential for encryption, identification, and authentication. We present a new cryptographic primitive called pseudo-random synthesizer and show how to use it in order to get a parallel construction of a pseudo-random function. We show several NC1 implementations of synthesizers based on concrete intractability assumptions as factoring and the Diffie–Hellman assumption. This yields the first parallel pseudo-random functions (based on standard intractability assumptions) and the only alternative to the original construction of Goldreich, Goldwasser, and Micali. In addition, we show parallel constructions of synthesizers based on other primitives such as weak pseudo-random functions or trapdoor one-way permutations. The security of all our constructions is similar to the security of the underlying assumptions. The connection with problems in computational learning theory is discussed.“