从 Shor 算法到格密码学

本文主要参考 Umesh Vazirani 在 Simons Institute 的 talk: Quantum and Post-Quantum Cryptography , 说的是关于从一类非交换隐含子群问题到格密码(LWE)的简短历史, 稍微补充了一些细节. 值得一提的是, Oded Regev 关于使用 Learning with Errors (LWE) 作为困难假设的 Lattice-based cryptography 的工作^[1], 荣膺 2018 年 Gödel Prize.

从 Shor 算法讲起

Shor 算法和交换隐含子群问题

让我们把目光聚集到 1994 年. 一年前, Daniel Simon 往 FOCS 上投了篇关于量子算法的论文^[2], 尽管文章被拒了, 作为那年 Program Committee 成员的 Peter Shor 却对此印象深刻: 自己动手把 Factoring 规约到了 Period-Finding 上, 然后用量子 Fourier 变换有效地解决了后者. 次年, 两人的论文双双出现在 FOCS 上, Shor 提出了素数分解和离散对数问题的多项式时间量子算法^[3] ( $\mathsf{Factoring} \in \mathsf{BQP}$ ), 而众所周知前者是 RSA 的困难假设, 这应该是第一个量子计算机的令人关注的潜在应用. 简单地说, 公钥密码学所做的事情就是在为难对手的同时 (困难假设) 方便自己人, 量子计算机提供了一种让困难假设变得不再"困难"的可能性. Peter Shor 凭借 Shor 算法获得了 1999 年的 Gödel Prize, 这是理论计算机科学的最高奖项 (论文奖) 之一.

大家试图理解 Shor 算法为什么具有如此威力, 于是在此基础上抽象出了隐含子群问题 (Hidden Subgroup Problem):

考虑有限交换群 $G$ 和他的子群 $H$ . 给定计算 $f: G\rightarrow S$ 的黑盒函数, 其中 $f$ 是 $H$ 的陪集(coset)上的常数. 如何确定隐含子群 $H$?

回到 Shor 算法, 这里的 $G=\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$, 要找的隐含子群 $H$ 就是 $n$ 的素因子 $p$ 对应的 $p\mathbb{Z}_n=\{0,p,2p,\cdots,n-p\}$ , 即周期寻找问题(Period Finding). 一般地来说, 解决一类隐含子群问题的过程包括:

1. 随机取一个陪集, 制备它其中所有元素对应的态的叠加态, 即 $|\psi\rangle = |gH\rangle = \frac{1}{\sqrt{|H|}}\sum_{h\in H}|gh\rangle$.
2. 对其应用量子 Fourier 变换, 并测量得到信息, 即均匀随机地得到 $H^{\perp}$ 中的元素. 量子 Fourier 变换的性质之一, 就是可以从子群 $H$ 得到 $H^{\perp}$ .

如果把陪集的态表示作为透镜一边的相的话, 那么量子 Fourier 变换就像一个透镜, 另一端得到的是我们需要的答案. 这样的量子并行能力十分惊人, 我们不禁要问, 是否存在类似高效的算法来解决足够困难的问题 (比如诸如 3-SAT 的一系列 $\mathsf{NP}$-complete 问题)?

3-SAT 问题描述的是一个布尔函数的可满足性, 考虑 $f(x_1,\cdots,x_n)=c_1 \wedge c_2 \wedge \cdots \wedge c_m$. 如果存在量子算法 (即允许任意酉变换) 做到下面的变换 $\psi = \sum_{x} \frac{1}{2^{n/2}}|x,0\rangle \longrightarrow \psi = \sum_x \frac{1}{2^{n/2}}|x,f(x)\rangle$. 那么我们只需要设计一种测量方式, 它能够 (在多项式时间内) 破坏所有不满足结果为真的赋值, 我们就能够用量子计算机解决 $\mathsf{NP}$-complete 问题 (即 $\mathsf{NP} \subseteq \mathsf{BQP}$ ). 不幸的是, Vazirani 师徒和 Charles Bennett 和 Gilles Brassard 在同年证明了^[4]在这种情形下的查询复杂度 (Quantum Query Complexity) 只能做到 $\Omega(2^{n/3})$ . 看起来量子计算机的能力并没有远远出乎大家的意料.

无果而终的非交换情形

故事讲到了这里, 怎么设计能够抵抗量子攻击的经典密码系统, 即抗量子密码学成了我们不得不面对的问题. 前文关于 Shor 算法的故事只说了一半, 同一时期 Alexei Kitaev 也在做类似的尝试, 不过他研究的是图同构问题 (Graph Isomorphism)^[5], 因而最终与荣誉失之交臂. 备受关注的非交换隐含子群问题往往有两种:

• 对称群 $S_n$ : 给定两个图的邻接矩阵 $A_1$, $A_2$ , 如果同构的话则有 $A_2 = P A_1 P^{-1}$ , $P \in S_n$ 为置换矩阵. 我们可以把图同构规约到此种情形.
• 二面体群 $D_N = \mathbb{Z}_N \rtimes \mathbb{Z}_2$ , 想象一个能在平面上旋转和翻转的正 $N$ 边形.

而关于寻找非交换隐含子群问题多项式时间算法的尝试至今仍然以失败告终, 最好的结果不过是 Greg Kuperberg 关于 $D_N$ 的亚指数时间 (sub-exponential time) 算法^[6].
Sean Hallgren 等人在 2006 年提供了关于非交换隐含子群问题 (特别是图同构问题) 的困难性(Hardness) 的强有力的证据^[7]: 考虑陪集 $H_{g_1}, H_{g_2}. \cdots, H_{g_k}$ 且 $k < poly(n)$ , 那么我们需要指数多次测量来得到足够的信息. 于是对于"足够非交换"的群, 如 $S_n$, $GL_n$, 足够的非交换性 意味着 指数规模的不可约表示. Umesh Vazirani 和其中两位作者再次基础上提出了基于 $S_n$ 上的隐含子群问题的单向函数 (One-Way Function) 构造^[8], 单向函数是现代密码学最重要的原语 (Primitive) 之一.

从非交换隐含子群问题到格密码学

Oded Regev 和最短格矢量 (SVP) 问题

花开两朵, 各表一枝. 让我们绕开 Kitaev 悲伤的故事, 回到二面体群 $D_n$ 的隐含子群问题. 一年前刚从 Tel Aviv University 毕业的 Oded Regev, 在 STOC 2002 提出了量子算法和格问题之间的惊人联系^[9]:

• 二面体群的隐含子群问题的经典构造与子集和问题 (Subset-Sum) 相关, 而后者是 $\mathsf{NP}$-complete 的.
• 唯一最短格问题 (Unique Shortest Lattice Problem) 可以规约到二面体群的隐含子群问题上.

这意味着一种寻找最短格矢量 (Shortest Lattice Vector Problem, SVP) 的量子算法. 考虑下述定义:

• 格 (Lattice) $L = \{ u_1, \cdots, u_n$ 的整数线性组合 $\}$
• 对偶格 (Dual lattice) $L^*=\{v:$ 对于 $L$ 上的所有 $u$, 两者内积 $\langle v,u\rangle$ 均为整数 $\}$
  其中对偶格 L^* 是格 L 作用量子 Fourier 变换后的结果.

为了求解最短格矢量问题, 下面我们给格上增加高斯权, 即第一步到第二步:

$\sum_{x\in L}|x\rangle\sum_y e^{-y^2/w}|y\rangle\longrightarrow \sum_{x\in L} |x\rangle \sum_{y} e^{-y^2/w}|x+y\rangle \longrightarrow \sum_{x \in L} |0\rangle \sum_y e^{-y^2/w} |x+y\rangle.$

但是第二步违反了量子不可克隆定理 (Quantum No-cloning Theorem), 我们必须抹掉 $x$ 把它变成真空态 $|0\rangle$ . 具体做法则是找到一个满足 $z=x+y$ 的 $x$ , 从而得到上式第三步.

Learning with Errors 和平均情形困难假设

而这并不是故事的全部, 在 STOC 2005, Regev 在此基础上进一步提出了 LWE (Learning with Errors) ^[1:1]. 考虑 $\mathbb{Z}_p$ 上的线性方程组, $p$ 为素数且 $n^2 < p <2n^2$ :

• m 个 noisy equations:

$\begin{aligned} a_{11}s_1+a_{12}s_2+\cdots+a_{1n}s_n &\approx b_1\\ a_{21}s_1+a_{22}s_2+\cdots+a_{2n}s_n &\approx b_2\\ &\vdots\\ a_{m1}s_1+a_{m2}s_2+\cdots+a_{mn}s_n &\approx b_m\\ \end{aligned}$

误差 $e_i=\langle a_i,s\rangle - b_i$ 符合平均值为 $0$ 且标准差为 $n^{3/2}$ 的高斯分布.
在此基础上, Regev 证明了 近似 LWE 和近似格上的最短向量 (SVP) 在 $n^{3/2}$ 内一样困难. 上面的 LWE 刻画了平均情形困难性(average-case hardness), 而下面的定理则证明了最差情形 (worst-case).

于是, 脱胎于二面体群的隐含子群问题的 LWE, 后来成为了一类格密码学所依赖的困难假设. 而 Regev 则拿到了 Wolf Foundation 于同年颁发的第一届 Krill Prize (可以类比北美的 Sloan Research Fellowships), 每年只有自然科学和工程领域的十数位以色列高校的助理教授 (Lecturer 或 Senior Lecturer) 能够获此殊荣.

后话

从 Shor 算法^[3:1]收到的空前关注, 以及同时期 Kitaev 对于图同构问题^[5:1]的失败尝试; 再到量子计算机对非交换隐含子群问题的无能为力[^hallgen], 以及 Regev 在其基础上提出的应对量子计算机威胁的格密码^[1:2]. 作为后量子密码 (Post-Quantum Cryptography) 的主要竞争者, 关于格密码和隐含子群问题自然也有后续的故事.

Oded Regev 和 Gödel Prize (2018)

时隔近二十年, Gödel Prize 再次颁发给量子计算相关的工作, 这次的得主是任职于 NYU Courant Institute 的 Oded Regev, 获奖工作是参考文献中的 ^[1:3], 关于使用 LWE 作为困难假设的 Lattice-based Cryptography. Gödel Prize 每年颁发一次, 是理论计算机科学领域的顶尖论文奖, 获奖工作必须发表在最近 14 年内的同行评议期刊上. 该奖项以 Kurt Gödel 命名, 是因为 Gödel 在 1956 年与 John von Neumann 的通信中第一次提及了 \math{sfP}-v.s.-$\mathsf{NP}$ 问题, 即询问是否有特定的 $\mathsf{NP}$-complete 问题能够被线性时间或平方时间求解.

EATCS 和 ACM SIGACT 对 Regev 的工作评价如下:

Regev’s work has ushered in a revolution in cryptography, in both theory and practice. On the theoretical side, LWE has served as a simple and yet amazingly versatile foundation for nearly every kind of cryptographic object imaginable—along with many that were unimaginable until recently, and which still have no known constructions without LWE. Toward the practical end, LWE and its direct descendants are at the heart of several efficient real-world cryptosystems.

连续群上的隐含子群问题 (2014)

在 STOC 2014, Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev 和 Fang Song (宋方老师最近刚来了知乎) 把隐含子群的定义拓展到连续群上, 并提出了 \mathbb{R}^n 上的隐含子群问题的量子算法^[10]. 这一工作也是量子信息理论领域顶级会议 QIP 2015 的 Plenary Talk. 此后, Campbell-Groves-Shepard 在此基础上提出了攻击 Soliloquy 公钥密码系统的方法^[11].

攻击 LWE 的失败尝试 (2016)

2016 年 11 月下旬, Regev 在 Tel Aviv University 时期的学生 Lior Eldar 和 Peter Shor 放出的重磅炸弹, 提出新的量子算法给出了攻击 LWE 的潜在可能性^[12]. Eldar 时为 MIT Center for Theoretical Physics 的博后, 其代表工作为 No Low-Error Trivial State (NLETS) 定理, 即量子 PCP 猜想的推论的弱化情形. 一时 Twitter 上有人惊呼, “Peter Shor 要彻底终结公钥密码系统”. 不过三天后, 由于论文所依赖的假设之一 (据悉由 Regev 指出) 有误撤稿, 这大概也是为什么很多研究者依然对格密码充满信心的原因吧.

参考文献