A Mathematical Problem for Security Analysis of Hash Functions and Pseudorandom Generators
Source: Cornell University
In this paper, the authors specify a class of mathematical problems, which they refer to as "Function Density Problems" (FDPs), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure PseudoRandom Generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Their argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. They also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints.