On the Minimal Hardware Complexity of Pseudorandom Function Generators

摘要

A set F of Boolean functions is called a pseudorandom function generator (PRFG) if communicating with a randomly chosen secret function from F cannot be efficiently distinguished from communicating with a truly random function. We ask for the minimal hardware complexity of a PRFG. This question is motivated by design aspects of secure secret key cryptosystems. These should be efficient in hardware, but often are required to behave like PRFGs. By constructing efficient distinguishing schemes we show for a wide range of basic nonuniform complexity classes (including TC{sub}2{sup}0), that they do not contain PRFGs. On the other hand we show that the PRFG proposed by Naor and Reingold in [24] consists of TC{sub}4{sup}0-functions. The question if TC{sub}3{sup}0-functions can form PRFGs remains as an interesting open problem. We further discuss relations of our results to previous work on cryptographic limitations of learning and Natural Proofs.