# Are CSPRNGs quantum-resistant?

It's fairly well known that Shor's algorithm kills RSA, DSA, ECDSA, DH, ... and that symmetric ciphers (AES and 3DES) and hashes (SHA-2, SHA-3) are safe as long as you double your key size / output size against a Grover search. (See slide 3 in this NIST presentation.)

My question is: nobody has mentioned random number generators either way, safe or unsafe. (As evidence, the NIST Draft Report on Post-Quantum Crypto has 0 hits for "RNG"). Is this because it's obvious to the experts, or because the research has not been done yet?

My understanding is that CSPRNGs are built on top of hashes and block ciphers, which are quantum-resistant themselves, but I would really like a definitive statement that CSPRNGs are OK, or if not, then some issues that I should be aware of / concerned about.

• A quantum algorithm may take as its inputs an input block, an output block, and an algorithm, and spit out a key. In the case of a RNG with a large hidden state, the input block is no longer available, and a more expensive algorithm is needed, possibly with work factor greater than the security level of the algorithm – Richie Frame Mar 9 '16 at 1:38

The best generic attack against a PRG (i.e. an attack that does not use any internal structure of a construction and hence works for any PRG) is exhaustive search for a seed. I think this was not done yet but it is very likely that the optimality of Grover's algorithm carries over to this setting. This would mean that for $n$ bit seeds, the best attack requires $O(2^{n/2})$ evaluations of the PRG.