Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?

by Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz.

Oded's comments

The main result is a proof of the stadard assumption regarding the infeasibility of decoding random linear codes implies a one-way function that can be effected by a single step of a cellular automaton. This result weakens the connection between graph expansion and cryptographic hardness in NC0, or at least indicate that the required expansion may be much weaker than suspected. It also contradicts the feeling that cryptographic hardness should go hand in hand with inapproximability, or again indicates that such connection should be better qualified.

The original abstract

A cellular automaton (CA) is a discrete dynamical system in which cells are placed on a grid and the state of each cell is updated via a *spatially local* deterministic rule that depends only on the few cells within its close neighborhood. This model is commonly used to describe real world systems in nature and society. CAs are known to be capable of a highly complex behavior including the ability to generate computational intractability and computational unpredictability. However, it is not clear how fast these phenomena evolve and how common they are with respect to all possible initial configurations. Previous results suggest that computational intractability and unpredictability can evolve fast from some exceptional initial configurations, or alternatively, can evolve from almost all initial configurations after sufficiently long time. Our main results show that, under widely accepted conjectures, computational intractability and unpredictability can evolve after a single computation step from almost all initial configurations. This is done by constructing cryptographic primitives which are computed by a single step of a CA. These results support the view that computational forms of complexity can emerge from simple spatially local interactions in a very common and immediate way.

Back to list of Oded's choices.