[cryptography] integer automata networks for PRNG
eugen at leitl.org
Fri Sep 6 06:19:13 EDT 2013
Assuming you want to build a family of large-state PRNGs by
using random high-dimensional (N>>3) automaton networks
(>>10^3 nodes or more) where each node state is computed by a
logical function (e.g. XOR) of the node and its neighborhood --
1) is there prior work on that?
2) which methods would one use to prove/engineer their
resistance to reverse engineering state and topology (which
can change at each round, by e.g. treating the array of pointers
as automaton state itself) from just observing a small window
on its state? It seems there's a continuum between one-time
pad and sufficiently large-state PRNGs.
I can think of using light cones for low-dimensional, regular
analoga to show state propagation across volume, but high-dimensional
networks pretty much guarantee that information about local state will
spread wide even with a few iterations.
Obviously, by using a lot of state and randomizing the topology
at each round would make ASICfication prohibitively expensive.
Obviously, for software implementations this is bandwidth-limited
(and guarantees worst-case for memory streaming), and could be
accelerated by using a massively parallel system with embedded
memory and a suitable n-torus signalling mesh.
Thanks for any pointers and/or comments.
More information about the cryptography