Skip to main content
Tweeted twitter.com/StackCompSci/status/737060290983038976
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link

Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG?

Let f and g be two functions with integer range 0..m-1. They may keep state and interact with the world (for example setting a seed or reading the current time), calling them multiple times may produce different results. f and g can see each other's state, but cannot modify the other's state.

Assume at least one of f and g is a cryptographically secure pseudorandom number generator, but it is unknown which one. Is it possible to create a function h that uses f and g and behaves as a CSPRNG? h is not allowed to set or read external state directly, the only way it can modify or read state is by calling f and g and observing their results. h should work for any given f and g.

Of course, h is not allowed to use any "true" source of randomness, and ideally the construction should not involve passing randomness tests.

As a related problem, I believe that if f and g were perfectly random, then f + g (mod m) would also be perfectly random. But I think in this deterministic case, it's always possible to create a g such that it "cancels out" f in h. Not sure how to prove this.