6
$\begingroup$

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.

|improve this question
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Richie Frame Mar 9 '16 at 1:38
4
$\begingroup$

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.

For PRGs build from hash functions and block ciphers this should be the case also for specific, non-generic attacks (assuming the used hash / BC is post-quantum). Of course, if you use a number theory based PRG like Blum-Blum-Shub Shor's algorithm kicks in.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This absolutely feels like the right answer to me (possibly except for the fact that the size of the internal state could affect the number of evaluations required). But yeah, without a formal paper with proof on the subject it's hard to be 100% - I could well imagine that cryptographers would ignore the problem as it seems a self answering question. (Dual-ECB DRBG would also be in trouble I imagine, but that algorithm is very likely insecure without quantum crypto). $\endgroup$ – Maarten Bodewes♦ Mar 9 '16 at 10:47
  • 2
    $\begingroup$ @MaartenBodewes: what mephisto is suggesting is to use Grover's algorithm to attack a PRG by viewing it as a black box that takes a seed as an input , and generates some output (and Grover's matching criteria is when we see the output we're interested in). As such, the size of the internal state doesn't change how many evaluations that Grover's would take. $\endgroup$ – poncho Mar 9 '16 at 15:31
  • $\begingroup$ Right. For the generic security the inner state size does not matter. Nevertheless, I guess it will matter as soon as you start looking at the internals. I mean, finding the internal state would also work to distinguish so that should probably also be twice the targeted security level... $\endgroup$ – mephisto Mar 10 '16 at 7:29

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.