Consider the construction of "A Pseudorandom Generator from any One-way Function" [HILL99] in Hastad et al.

One way to proof pseudorandomness of this construction is by contradiction. That is, an assumed PRG distinguisher is transformed into a OWF inverter (usually through an intermediate notion called pseudoentropy generator). There is both a uniform and a non-uniform version, considering uniform resp. non-uniform distinguishers/inverters. However, in all proofs of the uniform version that I have seen the PRG distinguisher and the OWF inverter are randomized.

Is it (im-)possible to convert a deterministic (uniform) PRG distinguisher into a deterministic (uniform) OWF inverter?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.