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

Question

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.

Answer 1

No. There's no way to create such an $h$.

Here's an informal sketch of the proof. Suppose $f$ is a CSPRNG. Then for all $h$, there exists a $g$ such that $h(f,g)$ outputs only even numbers. In particular, $g$ reads the state of $f$, deduces what $f$'s next output will be, and outputs something that will cause $h$ to output an even number (if necessary, by generating multiple candidate outputs and testing each one to see which will provoke $h$ to output an even number).

[This is the main idea of a proof. To get a full formal proof, you'd also have to consider the case where $h$ ignores its second input or mostly ignores its second input. However, it's pretty easy to see that such a $h$ can't possibly be any good, either.]

---

That's the theory. What about practice? In the real world, if you're not sure whether $f$ or $g$ are any good, don't let them read the internal state of anything else. Don't ever let something that might be malicious read the internal state of security-critical parts of your system.

---

If you know that $f$ and $g$ are independent (as random variables), and you know that at least one of $f,g$ is a secure CSPRNG, then $f+g \bmod m$ is indeed good (it's a secure CSPRNG). However, the critical requirement here is that they be independent. If one can read the internal state of the other, then they're not independent.