3 ms·
The difference is that ANNs make approximations. It could be manageably small and learn an approximation of the PRNG code that succeeds for a large number of ou
by cblconfederate 5y ago
The difference is that ANNs make approximations. It could be manageably small and learn an approximation of the PRNG code that succeeds for a large number of outputs, even if running a fully accurate network is impossible. I think the complexity of the PRNG recursive algorithm , when unrolled through time for large number of steps, is the relevant complexity here. The ANN is not necessarily trying to devise a new function that recovers the seed.
- _hl_ 5y agoThe proof accounts for that. You can even allow for the ANN being totally wrong on "almost all" seeds except for a non-negligible fraction, the definition of a CSPRNG allows for that. If it is wrong for all but a negligible fraction of seeds, then you haven't gained much over random guessing. So the only way that an ANN could help is if the ANN approximation is sufficiently bad that it doesn't give you any significant speedup in cracking the CSPRNG. Of course, this is assuming that practical CSPRNGs conform to the theory, but we're just debating theory here.