🔢 mathematics

Notes on the LVP and CVP in $p$ -adic Fields

本文利用 $p$ -adic 范数的非阿基米德性质，提出了一种基于极大序和 $p$ -根结构的多项式时间算法，用于在 $p$ -adic 域中高效计算格的正交基并解决最长向量问题（LVP）和最近向量问题（CVP）。

原作者： Chi Zhang, Mingqian Yao

发布于 2026-04-13

📖 1 分钟阅读🧠 深度阅读

原作者： Chi Zhang, Mingqian Yao

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲的是数学家如何在一个特殊的数学世界里“破解”两个著名的难题，并顺便给未来的密码锁提出了一些警告。

为了让你更容易理解，我们可以把这篇论文的内容想象成在一个充满魔法的“非欧几里得”迷宫里找路。

1. 背景：两个著名的“寻宝游戏”

在普通的数学世界（欧几里得空间，就像我们生活的现实世界）里，有两个很难的谜题：

最短向量问题 (SVP)：在一个由无数个点组成的网（晶格）里，找到离原点最近的那个点。
最近向量问题 (CVP)：给你一个目标点，让你在这个网里找到离它最近的一个点。

这两个问题很难，所以现代密码学（比如保护你银行账号的加密技术）经常利用它们的“难解性”来制造安全锁。

但是，这篇论文把目光投向了** $p$ -进数（ $p$ -adic fields）**的世界。这是一个非常奇特的数学宇宙，那里的距离规则和我们不一样：

普通世界：三角形两边之和大于第三边。
$p$ -进数世界：遵循“非阿基米德”规则。想象一下，如果你走两步，每一步的长度不同，那么总长度完全取决于你走得最远的那一步，而不是两步加起来。这就像你坐电梯上楼，如果你坐电梯到了 100 楼，再走楼梯下到 99 楼，你的高度还是由 100 楼决定的，而不是 100+1。

在这个世界里，原来的“最短向量”问题变成了**“最长向量问题 (LVP)"（因为规则变了，我们要找的是“最大”的那个），以及“最近向量问题 (CVP)"**。

2. 核心发现：一把万能钥匙

以前的研究者认为，在这个奇特的 $p$ -进数世界里，找“最长向量”和“最近向量”很难，就像在迷宫里乱撞。

但这篇论文的作者（张驰和姚明谦）发现了一个巨大的漏洞：
在这个世界里，所有的迷宫其实都有一个**“正交基”（Orthogonal Basis）**。

打个比方：
想象你在一个复杂的迷宫里，原本的路径是歪歪扭扭、互相纠缠的（就像一团乱麻）。

以前的方法：你需要在这团乱麻里一点点摸索，计算量巨大，非常慢。
作者的方法：他们发现，只要找到一把特殊的“钥匙”（正交基），就能把这团乱麻瞬间拉直，变成几条互不干扰的平行线。
- 一旦路被拉直了，找“最长”或“最近”的点就变得像在直尺上读数一样简单，几秒钟就能算出来。

3. 他们是怎么做到的？（三步走战略）

作者提出了一套多项式时间算法（意思是：输入的数据越大，计算时间虽然变长，但只是按“平方”或“立方”增长，而不是按“指数”爆炸，所以非常快）。

他们的步骤就像是一个**“炼金术士”的配方**：

寻找“最大环”（Maximal Order）：
他们利用数学工具（像 Round 2 和 Round 4 算法），在 $p$ -进数这个复杂的代数结构里，找到了一个最完美的“核心结构”。这就像在混乱的矿石中提炼出了最纯净的金块。
提取“魔法种子”（Uniformizer）和“余数世界”（Residue Field）：
在这个核心结构里，他们找到了一个特殊的元素（叫 $\pi$ ，均匀化子），它就像是一个**“尺子”**，可以衡量所有东西的大小。同时，他们把这个世界简化成一个简单的“余数世界”（就像把复杂的十进制简化为只有 0-9 的个位数世界）。
组装“正交基”：
利用那个“尺子”和“余数世界”的基，他们像搭积木一样，迅速搭建出了那把**“万能钥匙”（正交基）**。

一旦有了这把钥匙，LVP（找最长）和 CVP（找最近）这两个曾经被认为很难的问题，瞬间就变成了小学算术题。

4. 这对密码学意味着什么？（警报拉响）

这是论文最震撼的部分：

现状：之前有人（Deng 等人）尝试用 $p$ -进数晶格来设计新的公钥加密系统和数字签名，认为它们很安全，因为没人能快速解决 LVP 和 CVP。
后果：这篇论文证明了，只要你知道这个 $p$ -进数场是怎么定义的（比如给了一个最小多项式），攻击者就能用作者发明的这套“快速算法”瞬间破解这些系统。
比喻：这就像有人造了一把号称“无法被打开”的保险箱，声称只有天才才能找到钥匙。但这篇论文的作者直接造出了一台自动开锁机，只要给你保险箱的图纸，机器就能在几秒钟内把锁打开。

5. 未来的方向：如何修补？

既然旧的锁被破解了，怎么办？
作者在最后提出了一些建议：

不要直接给图纸：在密码系统中，不要直接把 $p$ -进数场的完整定义（最小多项式）告诉用户。
只给“黑盒”：只告诉用户一个“预言机”（Oracle），比如“你输入一个数，我告诉你它的大小”，但不告诉用户这个大小是怎么算出来的，也不泄露那把“正交基”钥匙。
新的谜题：如果只给黑盒，目前还没有人知道怎么在多项式时间内找到那把钥匙。这可能成为未来后量子密码学（抵抗量子计算机攻击的密码）的新方向。

总结

这篇论文就像是一个数学侦探故事：

侦探发现了一个看似坚不可摧的数学迷宫（ $p$ -进数晶格）。
侦探发现迷宫里其实藏着一条隐藏的直线通道（正交基）。
侦探发明了一套快速导航仪（多项式时间算法），能瞬间找到这条通道。
结果：所有基于这个迷宫设计的“安全锁”都被证明是不安全的。
建议：未来的锁必须设计得更狡猾，不能让人看到迷宫的图纸，只能让人在迷宫里瞎转，这样才安全。

这对密码学界是一个重要的提醒：在数学的 $p$ -进数世界里，有些我们以为的“困难”，其实只是因为我们还没找到那把正确的钥匙。

论文技术总结： $p$ -进域中长向量问题 (LVP) 与最近向量问题 (CVP) 的注记

论文标题：Notes on the LVP and CVP in p-adic Fields
作者：Chi Zhang, Mingqian Yao
机构：中国科学院数学与系统科学研究院，中国科学院大学

1. 研究背景与问题定义

1.1 背景

$p$ -进域（ $p$ -adic fields）上的计算几何问题已成为代数数论与理论密码学的交叉热点。传统的格密码学基于欧几里得空间中的最短向量问题（SVP）和最近向量问题（CVP）。在 $p$ -进向量空间中，由于范数满足非阿基米德性质（ $|v+w|_p \le \max\{|v|_p, |w|_p\}$ ），几何结构发生了质变，衍生出了长向量问题 (Longest Vector Problem, LVP) 和 最近向量问题 (Closest Vector Problem, CVP)。

1.2 问题定义

LVP (长向量问题)：给定一个 $p$ -进格 $L$ ，寻找格中长度第二大的向量（即 $\lambda_2$ ，其中 $\lambda_1$ 为最大长度）。
CVP (最近向量问题)：给定格 $L$ 和目标向量 $t$ ，寻找格中距离 $t$ 最近的向量。

1.3 现有挑战

早期的方案（如 Deng et al. [3, 5]）利用 $p$ -进格构建公钥加密和签名方案，并声称其安全性基于 LVP/CVP 的困难性。
然而，Zhang [12] 指出在特定条件（完全分歧域）下，LVP 存在确定性多项式时间算法，从而破坏了部分方案的安全性。
后续研究（Zhang et al. [13]）试图通过构造大剩余次数（large residue degree）的域来规避攻击，但忽略了在给定极小多项式的情况下，计算最大序（Maximal Order）本身存在多项式时间算法（如 Round 2/4 算法），且 $p$ -进格天然存在正交基 (Orthogonal Basis)，而正交基的存在使得 LVP 和 CVP 可在多项式时间内求解。

2. 核心方法论

本文提出了一套完整的确定性多项式时间算法框架，用于在给定极小多项式的 $p$ -进域 $K$ 中求解 LVP 和 CVP。主要步骤如下：

2.1 计算最大序 (Maximal Order)

利用 $p$ -进域的结构，从初始序 $O = \mathbb{Z}_p[\theta]$ 开始，通过迭代扩大来构造最大序 $\mathcal{O}_K$ ：

计算 $p$ -根 (p-radical)：定义 $I_p = \{x \in O \mid \exists m, x^m \in pO\}$ 。利用 Frobenius 同态的幂次（ $x \mapsto x^{p^j}$ ）在商环 $R = O/pO $中计算$ I_p$ 的核。
扩大序：根据定理 3.3，构造 $O' = \{x \in K \mid xI_p \subset I_p\}$ 。若 $O' \neq O$ ，则用 $O'$ 替换 $O$ 并重复，直到收敛到最大序 $\mathcal{O}_K$ 。

2.2 构造正交基 (Orthogonal Basis)

一旦获得最大序 $\mathcal{O}_K$ ，即可构造域 $K$ 的正交基：

寻找一致化元 (Uniformizer)：在 $p$ -根 $I_p$ 的基中寻找具有最大 $p$ -进绝对值的元素 $\pi$ ，即为一致化元。
构造剩余域基：计算剩余域 $k = \mathcal{O}_K/\pi\mathcal{O}_K$ 在 $\mathbb{F}_p$ 上的基 $s_1, \dots, s_f$ （其中 $f$ 为剩余次数）。
生成正交基：利用定理 4.3，集合 $\{s_i \pi^j \mid 1 \le i \le f, 0 \le j \le e-1\}$ （其中 $e$ 为分歧指数，$n=ef $）构成了$ K $在$ \mathbb{Q}_p$ 上的正交基。

2.3 求解 LVP 和 CVP

在获得正交基后，利用算法 1 和算法 2 高效求解：

LVP 算法：利用正交基的性质，通过贪心策略重排格基向量，直接定位长度第二大的向量。
CVP 算法：利用正交基将目标向量投影到各正交分量上，通过简单的系数截断（取整）找到最近格点。
复杂度：上述所有步骤（最大序计算、正交基构造、LVP/CVP 求解）的时间复杂度均为输入规模 $n$ （域次数）和 $\log p$ 的多项式。

3. 主要贡献

算法创新：
- 首次将 $p$ -进 Gram-Schmidt 正交化与剩余域计算相结合，设计了求解 $p$ -进格 LVP 和 CVP 的高效求解器。
- 证明了在给定极小多项式的条件下，LVP 和 CVP 是多项式时间可解的（确定性算法）。
理论突破：
- 揭示了 $p$ -进格天然具备正交基结构，且该结构可通过最大序和一致化元高效构造。
- 给出了 $\mathbb{Q}_p$ 上向量空间范数的完整刻画（定理 7.1）：任何范数均可由一组正实数和可逆矩阵确定，且若矩阵已知，正交基可被轻易提取，导致安全性失效。
实例验证：
- 在 $K = \mathbb{Q}_2(\sqrt[3]{5})$ （通过多项式 $X^3 - 3X^2 + 3X - 5$ 定义）上进行了具体计算，演示了从最大序计算到正交基生成，再到求解 LVP/CVP 的全过程。

4. 研究结果与结论

安全性结论：基于 $p$ -进格的公钥加密和签名方案（如 Deng et al. [5] 提出的方案）在完全指定域（即已知极小多项式）的情况下是不安全的。本文提出的通用攻击算法能够以多项式时间破解这些方案，无论其剩余次数大小如何。
攻击机制：攻击者无需破解困难问题，只需利用代数算法（Round 2/4 等）计算最大序，进而构造正交基，即可将 LVP/CVP 转化为简单的线性代数问题。
未来方向：
- 现有的方案若仅通过增大剩余次数修补，仍无法抵御此攻击。
- 未来的安全方案可能需要改变设定：不再直接给出域的极小多项式，而是将 $p$ -进绝对值作为预言机 (Oracle) 提供。
- 关键挑战在于：设计一种可计算的范数，使其不泄露正交基信息，或者证明在仅给定范数预言机时，寻找正交基（或定理 7.1 中的参数）是困难的。

5. 意义与影响

密码学影响：该研究对基于 $p$ -进格的抗量子密码方案构成了严重威胁，表明当前基于该假设的方案缺乏形式化的安全证明，且存在根本性的结构漏洞。
数学贡献：统一了代数技巧（最大序、 $p$ -根）与计算效率，深化了对 $p$ -进格几何结构的理解，为后续研究 $p$ -进域上的困难问题提供了新的视角和基准。

总结：本文证明了在标准设定下（给定极小多项式）， $p$ -进域上的 LVP 和 CVP 并非困难问题，而是存在高效的多项式时间算法。这一发现直接否定了基于此假设的现有公钥密码体制的安全性，并指出了未来构建安全方案必须避免泄露正交基结构或改变问题定义的方向。