0%

格（Lattice）的简介

发表于 更新于 分类于

本系列是关于格密码学的记录笔记，这一系列大部分内容我都是从资料直接摘录的，甚至可以看成是不完全的翻译版，少数内容有我自己的理解和注释。

格的优点

在之前的公钥密码学当中，几乎所有的构造都是基于 Diffie-Hellman 假设或者是 RSA 假设，然而这些基于数论的困难问题（离散对数困难问题，大整数分解困难问题）在量子计算情况下不再是困难的 [Sho97]。形式上有着几何性质的格密码学则具有抗量子性。除此之外，它还有下列优点：

  • 格因其几何性质，计算主要涉及向量（vector）和矩阵（matrix）的线性运算，因此算法简便而且可以并行化。
  • 可归约的强安全性，并且归约的形式是：worst-case to average-case reduction。这意味着只要 worst-case 问题中存在哪怕只有一个困难实例，其对应的 average-case 就是平均意义上困难的。这个性质对于格密码学的安全性来说非常重要。
  • 格的出现还为密码学中许多其他的原本只有理论的机制（如全同态加密 FHE，基于属性的加密 ABE，代码混淆 Code obfuscation 等）提供了具体构造的可能。

格的定义

格并不是一个密码学中的新概念，它只是空间中“有规律”的点集，围棋盘、合理密植的树林等形象或许可以帮助我们理解这样的概念。格的具体定义如下：

Lattice

A $n$-dimensional lattice $\mathcal{L}$ is any subset of $\mathbb{R}^n$ that is both：

  1. an additive subgroup: $0 \in \mathcal{L}$, and $-\mathbf{x}, \mathbf{x+y} \in \mathcal{L}$ for every $\mathbf{x, y} \in \mathcal{L}$; and
  2. discrete: every $\mathbf{x} \in \mathcal{L}$ has a neighborhood in $\mathbb{R}^n$ in which $\mathbf{x}$ is the only lattice point.

— by [Pei16] in p.6.

  • 一个 $n$ 维的格（lattice $\mathcal{L}$）其实是一个满足下列条件的 $\mathbb{R}^n$ 的子集：

    • 加法子群：封闭性，结合率，加法单位元，加法逆元；
    • 离散化：即一个格点的周围一定范围内没有其他格点。

  • 每一个格 $\mathcal{L}$ 通常都有一个基（basis $\mathbf{B} = \{\mathbf{b_1, \cdots, b_k}\}$），即格中每个格点（$n$ 维格中的格点其实就是 $n$ 维向量）都可以写成这些基中格点的线性组合：

  • 对于一个格 $\mathcal{L}$ 来说，有一个很重要的概念就是它的对偶格（dual lattice $\mathcal{L}$*）。对偶格是指那些与 $\mathcal{L}$ 中所有格点内积均为整数的 $n$ 维点构成的集合：

参考资料