Pseudorandom functions in TC0 and cryptographic limitations to proving lower bounds
This paper investigates which complexity classes inside NC can contain pseudorandom function generators (PRFGs). Under the Decisional Diffie-Hellman assumption (a common cryptographic assumption) TC40 contains PRFGs. No lower complexity classes with this property are currently known. On the other hand, we use effective lower bound arguments to show that some complexity classes cannot contain PRFGs. This provides evidence for the following conjecture: Any effective lower bound argument for a complexity class can be turned into an efficient distinguishing algorithm which proves that this class cannot contain PRFGs.
pseudorandomness tc0 lower bounds function generators