  We propose two hard problems in cellular automata. In particular the problems
are:
  [DDP$^M_{n,p}$] Given two \emph{randomly} chosen configurations $t$ and $s$
of a cellular automata of length $n$, find the number of transitions $\tau$
between $s$ and $t$.
  [SDDP$^\delta_{k,n}$] Given two \emph{randomly} chosen configurations $s$ of
a cellular automata of length $n$ and $x$ of length $k<n$, find the
configuration $t$ such that $k$ number of cells of $t$ is fixed to $x$ and $t$
is reachable from $s$ within $\delta$ transitions.
  We show that the discrete logarithm problem over the finite field reduces to
DDP$^M_{n,p}$ and the short integer solution problem over lattices reduces to
SDDP$^\delta_{k,n}$. The advantage of using such problems as the hardness
assumptions in cryptographic protocols is that proving the security of the
protocols requires only the reduction from these problems to the designed
protocols. We design one such protocol namely a proof-of-work out of
SDDP$^\delta_{k,n}$.
