论文标题
产生细胞自动机的硬问题
Generating Hard Problems of Cellular Automata
论文作者
论文摘要
我们提出了细胞自动机中的两个严重问题。特别是： [ddp $^m_ {n，p} $]给定两个\ emph {随机}选择的配置$ t $和$ s的长度$ n $的蜂窝自动机的$ s $，找到$ s $ s $和$ t $之间的过渡$τ$。 [SDDP $^δ_{k，n} $]给定了两个蜂窝自动机的$ n $和$ x $ length $ k <n $的蜂窝自动机的$ s $ s $ s $ k <n $，找到$ t $ $ t $的单元$ x $ to $ x $ nestry $ t $ n Inspectual $ n $ k < 我们表明，有限字段上的离散对数问题减少为ddp $^m_ {n，p} $，而晶格上的简短整数解决方案问题则减少为sddp $^δ__{k，n} $。使用加密协议中的硬度假设之类的问题的优点在于，证明协议的安全性仅需要从这些问题减少到设计的协议。我们设计一个这样的协议，即从sddp $^δ_{k，n} $中的工作证明。
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}$.
