Generating Hard Problems of Cellular Automata
This work introduces new cryptographic hardness assumptions based on cellular automata, potentially benefiting cryptography researchers, but it is incremental as it builds on existing reduction techniques without broad SOTA impact.
The authors tackled the problem of generating hard problems in cellular automata for cryptographic applications, proposing two problems (DDP and SDDP) and showing reductions from discrete logarithm and short integer solution problems, with a proof-of-work protocol designed as an example.
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 $τ$ between $s$ and $t$. [SDDP$^δ_{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 $δ$ 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$^δ_{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$^δ_{k,n}$.