摘要
近期的研究工作关注于与密码学应用相关的格同构问题（Lattice Isomorphism Problem, LIP）的复杂性。本文研究自对偶格 $\mathcal{L} \subset \mathbb{R}^n$ 上的 LIP，这类格在许多应用中自然出现。我们的主要成果包括一个时间复杂度为 $2^{n/2 + o(n)}$ 的随机算法和一个 $\mathsf{coNP}$ 协议，适用于广泛类别的自对偶格。这些结果扩展了最近关于 ZLIP 的研究，ZLIP 是判断一个格是否同构于 $\mathbb{Z}^n$ 的问题。
具体而言，前者的结果扩展了 Bennett, Ganju, Peetathawachai 和 Stephens-Davidowitz（Eurocrypt, 2023）以及 Ducas（Des. Codes Cryptogr., 2024）对 ZLIP 的 $2^{n/2 + o(n)}$ 时间算法的研究。后者的结果则扩展了 Hunkenschröder（Math. Prog. Series A, 2024）关于 $\mathrm{ZLIP} \in \mathsf{coNP}$ 的结果。
我们的结果利用了自对偶格的两个关键结构性质：
- 每个自对偶格 $\mathcal{L}$ 同构于某个自对偶格 $\mathcal{L}_0 \oplus \mathbb{Z}^r$，其中 $\lambda_1(\mathcal{L}_0)^2 \geq 2$；
- 每个自对偶格 $\mathcal{L}$ 存在特征向量，即存在向量 $\mathbf{w} \in \mathcal{L}$，使得对每个 $\mathbf{v} \in \mathcal{L}$，都有 $\langle\mathbf{v}, \mathbf{w}\rangle \equiv \langle\mathbf{v}, \mathbf{v}\rangle \pmod{2}$。
我们的方法借鉴了 Elkies 和 Gaulter 对具有长最短特征向量的格的研究，并在假设 Elkies（Math. Res. Lett., 1995）相关问题的正答案的情况下可以进一步加强。此外，我们还研究了自对偶编码的置换码等价性（Permutation Code Equivalence, PCE），发现类似的结构性质使得对某些自对偶码的 PCE 存在多项式时间算法。这为具有大外壳的自然编码类提供了简单的 PCE 解决方案。
博主点评： 本文在自对偶格和编码的同构问题上取得了重要进展，尤其是通过引入新的算法和理论框架，推动了密码学应用中的格理论研究。对于未来的研究，如何进一步优化算法和拓展其应用范围，将是一个值得关注的方向。