我想摆脱基于格的密码学，但即使是量子计算机也帮不了我

介绍

公钥加密是一种通过互联网安全发送信息的方法。它使用两个密钥：一个公钥和一个私钥。我们使用公钥来加密消息。我们可以公开分享这个密钥。私钥则被保密，只有所有者知道，他们可以使用它来解密消息。这个概念由 Diffie 和 Hellman 在 20 世纪 70 年代末在一篇具有开创性的论文中提出，与之前使用的方法相比，它具有几个优势，包括增强的安全性、安全的密钥交换、数字签名、可扩展性和更简单的密钥管理。

公钥密码学背后的工作原理是，一些复杂的数学问题（如果我们知道解决方案或某些秘密信息，可以很容易地验证，但其他情况下计算成本很高）将密钥联系起来。例如，在 RSA 密码系统中，公钥表示为 $e$，私钥表示为 $d$，它们通过表达式 $d \times e \equiv 1 \pmod{\phi(n)}$ 相关联。这意味着 $e$ 是 $d$ 模一个函数（称为Euler 总计 函数，在 $n$ 处计算）的乘法逆元，表示为 $\phi(n)$。有高效的算法来计算模逆。但是，它们需要知道 $n$ 的素因子分解，这对于大数来说非常困难，即使使用最快的超级计算机，也可能比我们的寿命还要长。

椭圆曲线密码学是另一种公钥密码学，它使用不同的数学方法。在这个系统中，秘密密钥表示为 $sk$，通过椭圆曲线的一个大的子群的生成元（表示为 $g$）与公钥（表示为 $pk$）相关联，表达式为 $pk = g^{sk}$。如果我们找到这个表达式中的指数，即离散对数问题，我们就可以从公钥中恢复秘密密钥。根据曲线及其子群的性质，这个问题可能很难解决。

然而，量子计算机的出现对这些公钥加密方案构成了一种潜在的威胁，量子计算机基于与传统计算机不同的技术，可以更快地解决特定的难题。为了解决这个问题，密码学家们一直在研究其他可以抵抗量子计算机的加密方案，称为后量子安全密码系统。NIST（美国国家标准与技术研究院）正在标准化一种或多种量子安全算法。许多这些方案都基于格上的特定问题的硬度，从而产生了基于格的密码学。

基于格的密码学能够抵抗量子计算机，还可以用于构建全同态加密方案，这在安全计算和数据隐私方面具有重要的应用。

格

在数学中，格是多维空间中点的规则排列，形成类似网格的结构。想象一张方格纸，水平线和垂直线的交叉点形成一个格。根据要解决的问题，格可以有不同的形状、大小和维度。

形式上，格可以定义为由一组基向量的线性组合生成的点集，其中系数为整数。这些基向量定义了格点的方向和间距。格可以跨越多个维度，每个维度对应于一个不同的基向量。例如，在二维空间中，一个格可以用两个基向量表示，这两个基向量定义了格点沿水平方向和垂直方向的间距。下图是由两个成 120° 角的向量所张成的六边形格。

给定一组线性独立的向量，$V = {v_1, v_2, v_3, \dots, v_m}$ 在 $R^n$ 中，由 $V$ 生成的格由以下集合给出，

$L = {a_1v_1 + a_2v_2 + \cdots + a_mv_m : a_k \in Z}$

$L$ 的维度是 $L$ 的基中的向量数。我们可以使用其他向量作为 $L$ 的基 $W = {w_1, w_2, \dots, w_m}$。基向量通过以下方式相关联

$w1 = a{11}v1 + a{12}v2 + \cdots + a{1m}v_m$

$w2 = a{21}v1 + a{22}v2 + \cdots + a{2m}v_m$

$\vdots$

$wm = a{m1}v1 + a{m2}v2 + \cdots + a{mm}v_m$

可以写成矩阵形式

$w = Av$

矩阵 $A$ 是可逆的，我们也可以将基之间的关系写成

$A^{-1}w = v$

例如，在 $R^3$ 中，我们可以使用三个垂直向量作为向量来获得一个立方格，我们可以将其表示为 $E = (1,0,0), (0,1,0), (0,0,1)$；格由整数三元组 $(x,y,z)$ 给出。我们也可以选择向量 $B = (2,1,1), (3,2,1), (1,1,1)$ 作为基。矩阵 $A$ 包含来自 $B$ 的向量作为行。

一些基比其他基更好。例如，基 $E$ 有三个长度为 1 的垂直（正交）向量。另一方面，基 $B$ 中的向量更长且不正交。我们很快就会看到，一个更好的基可以让我们轻松地解决一些格问题。

最短向量问题

格中两个重要的数学问题如下：

• 最短向量问题 (SVP)：我们想找到格中具有最短长度的非零向量 $v$，$|v|$。
• 最接近向量问题 (CVP)：给定格中的 $w$，我们想找到一个最接近 $w$ 的向量 $v$，也就是说，我们希望向量 $w - v$ 具有最小长度。

当我们有一组正交的基向量（即，每对向量都正交）时，我们可以使用勾股定理来看到

$|u|^2 = a_1^2|v_1|^2 + a_2^2|v_2|^2 + \cdots + a_m^2|v_m|^2$

其中所有 $a_k$ 都是整数。因此，最小长度的向量包含在集合 $\pm v_1, \pm v_2, \dots, \pm v_m$ 中

如果基不是正交的但仍然“好”，我们可以使用 Babai 算法来获得解决方案的“良好”近似值。如果基向量彼此接近，则此策略将失败。

带错误的环学习

带错误的学习(LWE)问题是密码学中使用的一个数学问题，用于保护通信安全和数据安全。它涉及在嘈杂的数据中找到隐藏的模式。可以把它想象成试图解决一个难题，你得到了一堆带有一些错误的方程，你需要找出变量之间正确的关系，尽管存在错误。在LWE中，方程表示为模一个大素数的数，目标是找到它们之间隐藏的线性关系，尽管存在噪声。

形式上，给定由某个线性函数 $b_k \approx s^t \cdot a$ 相关的对 $(a, b)$，目标是将这些对与均匀采样的随机点 $(x, y)$ 区分开来。每对 $(a_k, b_k)$ 包含一个随机误差 $e_k$，我们必须找到 $s$，尽管存在这些错误。

Rollup多项式环

假设我们正在处理系数在某个环上的多项式，例如整数，$Z[x]$。以下集合给出了 $n$ 次Rollup多项式

$R = Z[x]/(x^n - 1)$

这意味着我们有多项式模 $x^n - 1$，类似于我们处理整数的方式。在整数中，我们说 $15 \equiv 1 \pmod{7}$，因为它可以用 $7$ 的倍数加上一个余数来表示，即 $15 = 2 \times 7 + 1$。我们可以轻松地使用 $1$ 而不是 $15$ 并使用它进行运算。在多项式中，$x^5 + x^2 + 1 \equiv x + 2 \pmod{x^2 - 1}$，因为

$x^5 + x^2 + 1 = (x^2 - 1)(x^3 + x^2 + x + 1) + (x + 2)$

当使用 $x^n - 1$ 时的令人兴奋的属性是，只要我们发现幂 $x^n$，我们就可以用 $1$ 替换 $x^n$（对于更复杂的多项式，我们将不得不进行除法并找到余数）。这也导致了更直接的多项式乘法表达式。让我们先看一个例子，

$(x^2 + 3x + 5)(2x^2 + 2x + 7) = p(x) \pmod{(x^3 - 1)}$

标准计算将使我们应用分配律，对所有具有相同幂的项求和并减少所有大于 2 的幂：

$2x^4 + 2x^3 + 7x^2 + 6x^3 + 6x^2 + 21x + 10x^2 + 10x + 35 = p(x)$

求和,

$2x^4 + 8x^3 + 23x^2 + 31x + 35 = p(x)$

应用归约,

$p(x) = 23x^2 + 33x + 43$

一种更直接的方法是意识到项 $x^k$ 的系数 $p_k$ 由以下表达式给出：

$pk = \sum{i+j \equiv k \pmod{3}} a_i b_j$

对于 $x^2$，我们有

$p_2 = a_2b_0 + a_1b_1 + a_0b_2 = 7 + 6 + 10 = 23$

对于 $x$，我们有

$p_1 = a_1b_0 + a_0b_1 + a_2b_2 = 2 + 21 + 10 = 33$

最后,

$p_0 = a_0b_0 + a_2b_1 + a_1b_2 = 35 + 2 + 6 = 43$

一般来说，我们有

$a(x) \times b(x) = c(x)$

其中

$ck = \sum{i+j \equiv k \pmod{n}} ai b{k-i}$

如果你学习过拉普拉斯或傅里叶变换，你会发现它是 $a$ 和 $b$ 的Rollup。如果多项式的系数只能取值 $-1, 0, 1$，那么之前的计算会更快。

我们可以使用在一些有限域上定义的多项式，$Z_q$。Rollup多项式环是

$R_q = Z_q[x]/(x^n - 1)$

在 $Z_q$ 中，我们看到如果且仅当 $a$ 和 $q$ 互质时，一个元素 $a$ 才有一个乘法逆元 $b$ （使得 $a \times b \equiv 1 \pmod{q}$），即 $\gcd(a, q) = 1$（gcd 代表最大公约数）。$R_q$ 中存在一个类似的结果，指出如果且仅当 $\gcd(p(x), x^n - 1) = 1$ 时，多项式 $p(x)$ 才有一个乘法逆元 $q(x)$，$p(x)q(x) \equiv 1 \pmod{x^n - 1}$。

格和多项式环

我们可以将来自多项式环的元素映射到格的点。最简单的方法是通过系数嵌入：我们将第 $k$ 个系数，$p_k$ 视为 $Z_q^k$ 中向量的第 $k$ 个坐标。这种嵌入具有很好的属性，即添加多项式对应于格点的分量逐个相加，但是乘法没有很好的几何解释。在即将发布的文章中，我们将更详细地解释如何将 NTRU 密钥恢复简化为某个格上的最短向量问题。

NTRU

NTRU (N-th Degree Truncated polynomial Ring Units) 是一种使用三个Rollup多项式环工作的公钥加密方案，

$R = Z[x]/(x^n - 1)$

$R_q = Z_q[x]/(x^n - 1)$

$R_p = Z_p[x]/(x^n - 1)$

其中 $n$ 是一个素数且不等于 $q$。一对多项式给出了 NTRU 中的密钥，其系数只能取值 $-1, 0, 1$。这些多项式称为三元多项式，并用 $T(d_1, d_2)$ 表示它们的族。$d_1$ 是等于 1 的系数的数量，$d_2$ 是等于 $-1$ 的系数的数量（假设多项式的次数最多为 $n$，则有 $n - d_1 - d_2$ 个系数等于零）。例如，$x^3 - x^2 + 1$ 是一个三元多项式 ($d_1 = 2$, $d_2 = -1$)，而 $2x^3 + x - 3$ 不是。私钥由对 $f(x)$ 和 $g(x)$ 给出，其中

$f(x) \in T(d+1, d)$

$g(x) \in T(d, d)$

多项式 $f(x)$ 有 $d+1$ 个 1，以及 $d$ 个等于 $-1$ 的系数（如果多项式具有相同数量的 $-1$ 和 $1$，则它没有乘法逆元）。

接下来，我们分别在环 $R_q$ 和 $R_p$ 中计算 $F_q(x) = f(x)^{-1}$ 和 $F_p(x) = f(x)^{-1}$，并获得公钥作为

$h(x) = F_q(x)g(x)$

在 $R_q$ 中（如果多项式 $f(x)$ 没有逆元，我们必须选择另一个）。这是我们将用于加密消息的密钥。解密密钥由 $(f(x), F_p(x))$ 给出。

我们必须将消息编码为环 $R_p$ 中的多项式才能加密消息。因此，它们将具有范围 $-p/2, -(p-1)/2, \dots, -1, 0, 1, \dots, p/2$ 中的系数。我们抽取一些随机多项式，$r(x)$ 在 $T(d, d)$ 中，并计算密文为

$c(x) = ph(x)r(x) + m(x) \pmod{q}$

我们可以看到我们正在向明文添加一些“随机噪声”以隐藏它。

如果我们想解密，我们首先计算

$a(x) = f(x)c(x) \pmod{q}$

$b(x) = F_p(x)a(x) \pmod{p}$

如果我们正确选择参数，那么 $b(x) = m(x)$，我们可以解码以获得消息。要指定 NTRU，我们需要设置值 $(n, q, p, d)$，其中 $n$ 和 $q$ 互质且 $q > (6d+1)p$。为了理解为什么有效，我们可以更详细地查看计算：

$a(x) = f(x)c(x) \pmod{q}$

如果我们展开 $c(x)$，

$a(x) = pf(x)F_q(x)g(x)r(x) + f(x)m(x) \pmod{q}$

但是 $f(x)F_q(x) \equiv 1 \pmod{q}$，所以

$a(x) = pg(x)r(x) + f(x)m(x) \pmod{q}$

假设 $q > (6d+1)p$ 确保多项式 $a(x)$ 被精确计算并且没有环绕 $q$。

当我们应用 $F_p(x)$ 时，我们得到

$b(x) = pF_p(x)g(x)r(x) + F_p(x)f(x)m(x) \pmod{p}$

鉴于 $pF_p(x)g(x)r(x)$ 的所有系数都是 $p$ 的倍数（因子 $p$ 首先确保这一点），所以多项式模 $p$ 消失。我们剩下

$b(x) = F_p(x)f(x)m(x) \pmod{p}$

但是 $F_p(x)$ 是 $f(x)$ 在 $R_p$ 中的逆元，所以

$b(x) = m(x)$

总结

基于格的密码学是一种有希望的解决方案，可以防止量子计算机的潜在攻击。格是多维空间中点的有组织的排列，构成了基于格的密码学的基础。这些格允许构建加密方案。基于格的特定问题的难度，例如带错误的学习 (LWE) 问题和最短向量问题 (SVP)，是基于格的密码学安全性的基础。据信这些问题即使对于量子计算机来说也很难解决，这使得基于格的密码学成为后量子安全的一个引人注目的选择。在接下来的文章中，我们将更多地介绍格和加密方案的基础知识，例如 CRYSTALs Kyber。

• 原文链接： blog.lambdaclass.com/i-w...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～