[cryptography] integer automata networks for PRNG

Eugen Leitl 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 mailing list