4 ms·
The underlying assumption of all of modern cryptography is that one-way functions exist (implying P != NP), and further that the algorithms we use in practice a
by _hl_ 5y ago
The underlying assumption of all of modern cryptography is that one-way functions exist (implying P != NP), and further that the algorithms we use in practice are actually instances of these theoretically hard problems. So there provably always exists an algorithm that breaks any given PRNG, it will just always take you very long to compute and/or a lot of queries to the PRNG. ANNs are nothing special in that regard, they are just algorithms and have the same theoretical lower bound on their runtime.
So yes, an absurdly large ANN will break any PRNG, but so will other absurdly long-running algorithms, some of which are quite trivial: Just try every possible seed until you get the same sequence as what you observe, repeat until only one candidate seed is left.
EDIT: To add to this, you seem to be referring to the universal approximation theorems for ANNs. These theorems state that for any function (subject to some conditions not relevant here) and any arbitrary approximation ratio, there exists a finite ANN that approximates the function to within the desired approximation ratio. It says nothing about whether it's possible to train such an ANN, merely that it exists. Which in this case is a fairly trivial results, you could feasibly create a look-up table of PRNG sequences to seeds and encode that as an enormous ANN. But finding/training this ANN is prohibitively expensive.
- cblconfederate 5y agoI'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
- _hl_ 5y agoThe 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.
- cblconfederate 5y agoThe 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.