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.