Hacker News Reader

Comment by cblconfederate | Hacker News Reader

I'm not sure if there is any guarantee on the size of the network required. Problems like vision or language were also very complex and nonlinear but anns were able to handle them. It is analytically difficult to find an inverse function but the ANNs are not trying to do that, merely approximating the source code of the PRNG as piecewise-nonlinear functions. So i wouldn't think the former problem (inverse) is informative about the difficulty of the ANN training. At least i dont know if there's theoretical work on designing ANN-hard cryptographic functions

View on HN

The argument is fairly straightforward: Let n be the number of seed bits of the CSPRNG. Assume there exists an ANN that approximates the CSPRNG so that the number of possibly wrong output bits is at most polylogarithmic in n (otherwise you haven't really gained much insight from the ANN). Assume further that the ANN is sufficiently small so that a forward pass through the ANN takes at most polynomial time in n. Then you can create a polynomial-time algorithm that (i) runs the ANN on the observed CSPRNG samples/by querying the oracle, and then (ii) brute-forces the possible error bits in polynomial time, thereby recovering the full seed. But this is a contradiction with the assumption that the CSPRNG is secure, i.e. that it admits no polynomial-time adversary, q.e.d.

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.

The 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.

Reply on news.ycombinator.com