4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I was hoping for a more rigorous proof, but I think I need to more clearly define the model of computation first. $\endgroup$ – quantumtremor May 30 '16 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.