Pseudorandom Bit Generators from Enhanced Cellular Automata
Jason Spencer
Elementary and programmable cellular automata are known to produce statistically sound pseudorandom generators, but have never been shown to provide hardness that is required for cryptographic applications. Yet their simplicity and inherent parallelism are desirable qualities when designing today’s fast, cheap cryptographic primitives. In this paper, we present a new 3-neighbor cellular automata construct using cells which can be modeled as finite-state transducers having a simple state transition diagram. We show that for this construct, computing the cell values at time t — k when given cell values at time t is NP-Complete. We then use this as a primitive on which to build the Chasm family of pseudorandom generators. We provide test results from the NIST test suite to show that Chasm generators are statistically sound and argue they may be provably hard to invert in the average case as well as the worse case.
Keywords: Pseudorandom generators, cellular automata, cryptographic primitive, NP-Hardness, forward security