格的Voronoi胞腔的紧凑表示

### 格的Voronoi胞腔的紧凑表示 #### 1. 引言 在算法数论几何、密码学和整数规划领域，最短向量问题（SVP）和最近向量问题（CVP）是两个被广泛研究的重要问题。给定一个格 $\Lambda$，SVP 是要找到 $\Lambda$ 中的一个最短非零向量；对于目标向量 $t \in R^n$，CVP 则是要找到一个格向量 $z^*$，使得在所有 $z \in \Lambda$ 中，欧几里得长度 $\|t - z\|$ 最小。 在算法发展历程中，80 年代 Kannan 提出了能在比特复杂度 $n^{O(n)}$ 和多项式空间内解决 SVP 和 CVP 的算法。到了 2001 年，Ajtai、Kumar 和 Sivakumar 给出了一个求解 SVP 的随机算法，时间复杂度为 $2^{O(n)}$，但该算法除了具有随机性外，还需要指数级的空间。2010 年，Micciancio 和 Voulgaris 得到了一个确定性的 $2^{O(n)}$ 算法来解决这两个问题，其算法基于计算格的 Voronoi 胞腔 $V_{\Lambda}$，不过在最坏（和一般）情况下，由于 Voronoi 胞腔是一个最多有 $2(2n - 1)$ 个面的多面体，该算法存储 Voronoi 胞腔需要指数级的空间。 因此，是否存在一种只需要多项式空间的算法成为了一个重要的开放问题。本文的主要目标就是提出一种 Voronoi 胞腔的紧凑表示方法，并研究其在单指数时间和多项式空间内解决 CVP 的优势。 我们定义，如果格 $\Lambda$ 的每个 Voronoi 相关向量（即面向量）都可以用基向量 $B$ 表示，且系数的绝对值有界为 $c$，则称基 $B$ 是 $c$-紧凑的。用 $c(\Lambda)$ 表示使得 $\Lambda$ 存在 $c$-紧凑基的最小 $c$ 值。有了 $c$-紧凑基，我们就能在时间 $(2c + 1)^{O(n)} poly(n)$ 和多项式空间内解决 CVP。 关键问题在于，对于任意格，$c(\Lambda)$ 能有多小呢？如果 $c(\Lambda)$ 是常数，那么上述算法在渐近意义上与 Micciancio - Voulgaris 算法具有相同的运行时间，但只使用多项式空间。 以下是一些已知的结果： - 对于 $n$ 维格，总是存在 $c$-紧凑基，其中 $c$ 由 $n^2$ 界定。 - 存在一些格，不存在 $c$ 随维度亚线性增长的 $c$-紧凑基。 - 每个具有 zonotopal Voronoi 胞腔的格都有一个 1 - 紧凑基。 #### 2. $c$-紧凑基的概念 给定格 $\Lambda \subseteq R^n$，其 Voronoi 胞腔定义为 $V_{\Lambda} = \{x \in R^n : \|x\| \leq \|x - z\| \text{ 对于所有 } z \in \Lambda\}$，它是所有到原点的距离至少和到 $\Lambda$ 中其他任何格点的距离一样近的点的集合。Voronoi 胞腔是一个中心对称的多面体，其外部描述为 $V_{\Lambda} = \{x \in R^n : 2 x^T z \leq \|z\|^2 \text{ 对于所有 } z \in \Lambda\}$。 一个向量 $v \in \Lambda$ 若对应的不等式 $2 x^T v \leq \|v\|^2$ 定义了 $V_{\Lambda}$ 的一个支撑超平面，则称其为弱 Voronoi 相关向量；若它还能定义一个面，则称其为（严格）Voronoi 相关向量。设 $F_{\Lambda}$ 和 $C_{\Lambda}$ 分别是 $\Lambda$ 的严格和弱 Voronoi 相关向量的集合。 中心定义如下： - **定义 1**：格 $\Lambda$ 的基 $B$ 称为 $c$-紧凑的，如果 $F_{\Lambda} \subseteq \{Bz : z \in Z^n, \|z\|_{\infty} \leq c\}$。此外，$\Lambda$ 的紧凑性常数定义为 $c(\Lambda) = \min\{c \geq 0 : \Lambda \text{ 拥有一个 } c \text{-紧凑基}\}$。 在详细研究紧凑性常数之前，我们给出一些等价定义，这些定义既可以作为辅助工具，也有助于更好地理解底层概念。 设 $\Lambda^* = \{y \in R^n : y^T z \in Z \text{ 对于所有 } z \in \Lambda\}$ 是 $\Lambda$ 的对偶格，$K^* = \{x \in R^n : x^T y \leq 1 \text{ 对于所有 } y \in K\}$ 是包含原点在其内部的紧凑凸集 $K \subseteq R^n$ 的极体。 - **引理 1**：设 $B = \{b_1, \ldots, b_n\}$ 是格 $\Lambda \subseteq R^n$ 的基。以下条件等价： - (i) $B$ 是 $c$-紧凑的。 - (ii) $c \cdot conv(F_{\Lambda})^*$ 包含 $\Lambda^*$ 的对偶基 $B^{-T}$。 - (iii) 记 $B^{-T} = \{b_1^*, \ldots, b_n^*\}$，则 $F_{\Lambda} \subseteq \{x \in \Lambda : |x^T b_i^*| \leq c, \forall 1 \leq i \leq n\}$。 - (iv) $F_{\Lambda} \subseteq c P_B$，其中 $P_B = \sum_{i = 1}^{n}[-b_i, b_i]$。 这些等价定义的证明如下： - (i) $\Leftrightarrow$ (ii)：根据定义，$B$ 是 $c$-紧凑的当且仅当 $F_{\Lambda} \subseteq \{Bz : z \in Z^n, \|z\|_{\infty} \leq c\}$，这意味着 $Q = conv(F_{\Lambda}) \subseteq B[-c, c]^n$。取极体后，这等价于 $B^{-T} \frac{1}{c}C_n^* \subseteq Q^*$，其中 $C_n^* = conv\{\pm e_1, \ldots, \pm e_n\}$ 是标准交叉多面体。由于 $B^{-T}$ 的列构成了对偶格 $\Lambda^*$ 的基，证明完成。 - (i) $\Leftrightarrow$ (iii)：$B = \{b_1, \ldots, b_n\}$ 是 $c$-紧凑的当且仅当任何 Voronoi 相关向量 $v \in F_{\Lambda}$ 的表示 $v = \sum_{i = 1}^{n} \alpha_i b_i$ 满足 $|\alpha_i| \leq c$，对于所有 $1 \leq i \leq n$。根据对偶基的定义，$\alpha_i = v^T b_i^*$，从而证明了该结论。 - (i) $\Leftrightarrow$ (iv)：根据定义，$F_{\Lambda} \subseteq c P_B$ 当且仅当对于每个 $v \in F_{\Lambda}$，存在系数 $\alpha_1, \ldots, \alpha_n \in R$ 使得 $v = \sum_{i = 1}^{n} \alpha_i b_i$ 且 $|\alpha_i| \leq c$。这些系数是唯一的，并且由于 $B$ 是 $\Lambda$ 的基，它们是整数，即 $\alpha_i \in Z$。因此，我们开始的包含关系等价于说 $B$ 是 $c$-紧凑的。 引理 1 的 (iv) 部分表明，紧凑性常数 $c(\Lambda)$ 是使得 $F_{\Lambda} \subseteq c P_B$ 对于 $\Lambda$ 的某个基 $B$ 成立的最小 $c$。在这个定义中，该概念已经由 Engel、Michel 和 Senechal 引入，同时还有一个变体 $\chi(\Lambda)$，其中用更大的弱 Voronoi 相关向量集 $C_{\Lambda}$ 代替了 $F_{\Lambda}$。受晶体学应用的启发，一个反复出现的问题是给出这些格不变量 $c(\Lambda)$ 和 $\chi(\Lambda)$ 的良好上界。S