從 Shor 演算法到格密碼學

02-03

本文主要參考 Umesh Vazirani 在 Simons Institute 的 talk: Quantum and Post-Quantum Cryptography, 說的是關於從一類非交換隱含子群問題到格密碼(LWE)的簡短歷史, 稍微補充了一些細節.

讓我們把目光聚集到 1994 年. 一年前, Daniel Simon 往 FOCS 上投了篇關於量子演算法的論文[1], 儘管文章被拒了, 作為那年 Program Committee 成員的 Peter Shor 卻對此印象深刻: 自己動手把 Factoring 規約到了 Period-Finding 上, 然後有效地解決了後者. 次年, 兩人的論文雙雙出現在 FOCS 上, Shor 提出了素數分解和離散對數問題的多項式時間量子演算法[2] ( $mathsf{Factoring} in mathsf{BQP}$ ), 而眾所周知前者是 RSA 的困難假設. 簡單地說, 公鑰密碼學所做的事情就是在為難對手的同時 (困難假設) 方便自己人, 量子計算機提供了一種讓困難假設變得不再"困難"的可能性.

大家試圖理解 Shor 演算法為什麼具有如此威力, 於是在此基礎上抽象出了隱含子群問題 (Hidden Subgroup Problem):

考慮有限交換群 $G$ 和他的子群 $H$ . 給定計算 $f: Grightarrow S$ 的黑盒函數, 其中 $f$ 是 $H$ 的陪集(coset)上的常數. 如何確定隱含子群 $H$ ?

回到 Shor 演算法, 這裡的 $G=mathbb{Z}_n=mathbb{Z}/nmathbb{Z}$ , 要找的隱含子群 $H$ 就是 $n$ 的素因子 $p$ 對應的 $pmathbb{Z}_n={0,p,2p,cdots,n-p}$ , 即周期尋找問題(Period Finding). 一般地來說, 解決一類隱含子群問題的過程包括:

隨機取一個陪集, 製備它其中所有元素對應的態的疊加態, 即 $|psirangle = |gHrangle = frac{1}{sqrt{|H|}}sum_{hin H}|ghrangle$ .
對其應用量子 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,0rangle 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 在同年證明了[3]在這種情形下的查詢複雜度 (Quantum Query Complexity) 只能做到 $Omega(2^{n/3})$ . 看起來量子計算機的能力並沒有遠遠出乎大家的意料.

故事講到了這裡, 怎麼設計能夠抵抗量子攻擊的經典密碼系統, 即抗量子密碼學成了我們不得不面對的問題. 前文關於 Shor 演算法的故事只說了一半, 同一時期 Alexei Kitaev 也在做類似的嘗試, 不過他研究的是圖同構問題 (Graph Isomorphism), 因而最終與榮譽失之交臂. 備受關注的非交換隱含子群問題往往有兩種:

對稱群 $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 演算法[4].

Sean Hallgren 等人在 2006 年提供了關於非交換隱含子群問題 (特別是圖同構問題) 的困難性(Hardness) 的強有力的證據[5]: 考慮陪集 $H_{g_1}, H_{g_2}. cdots, H_{g_k}$ 且 $k < poly(n)$ , 那麼我們需要指數多次測量來得到足夠的信息. 於是對於"足夠非交換"的群, 如 $S_n, GL_n$ , 足夠的非交換性意味著指數規模的不可約表示. Umesh Vazirani 和其中兩位作者再次基礎上提出了基於 $S_n$ 上的隱含子群問題的單向函數 (One-Way Function) 構造[6].

花開兩朵, 各表一枝. 讓我們繞開 Kitaev 悲傷的故事, 回到二面體群 $D_n$ 的隱含子群問題. Ph.D 期間成果寥寥的 Oded Regev, 在畢業一年後的 STOC 2002 提出了量子演算法和格問題之間的驚人聯繫[7]:

二面體群的隱含子群問題的經典構造與子集和問題 (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,urangle$ 均為整數 $}$

其中對偶格 $L^*$ 是格 $L$ 作用量子 Fourier 變換後的結果.

為了求解最短格矢量問題, 下面我們給格上增加高斯權, 即第一步到第二步:

$sum_{xin L}|xranglesum_y e^{-y^2/w}|yranglelongrightarrow sum_{xin L} |xrangle sum_{y} e^{-y^2/w}|x+yrangle longrightarrow sum_{x in L} |0rangle sum_y e^{-y^2/w} |x+yrangle.$

但是第二步違反了量子不可克隆定理 (Quantum No-cloning Theorem), 我們必須抹掉 $x$ 把它變成真空態 $|0rangle$ . 具體做法則是找到一個滿足 $z=x+y$ 的 $x$ , 從而得到上式第三步.

而這並不是故事的全部, 在 STOC 2005, Regev 在此基礎上進一步提出了 LWE (Learning with Errors) [8]. 考慮 $mathbb{Z}_p$ 上的線性方程組, $p$ 為素數且 $n^2 < p <2n^2$ :

$m$ 個 noisy equations:

$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$

誤差 $e_i=langle a_i,srangle - b_i$ 符合平均值為 $0$ 且標準差為 $n^{3/2}$ 的高斯分布.

在此基礎上, Regev 證明了近似 LWE 和近似格上的最短向量 (SVP) 在 $n^{3/2}$ 內一樣困難. 上面的 LWE 刻畫了平均情形, 而下面的定理則證明了最差情形.

於是, 脫胎於二面體群的隱含子群問題的 LWE, 後來成為了一類格密碼學所依賴的困難假設. 而 Regev 則拿到了 Wolf Foundation 於同年頒發的第一屆 Krill Prize (可以類比北美的 Sloan Research Fellowships).

作為後話的故事有兩個:

一是在 STOC 2014, Kirsten Eisentr?ger, Sean Hallgren, Alexei Kitaev 和 Fang Song (宋方老師最近剛來了知乎) 把隱含子群的定義拓展到連續群上, 並提出了 $mathbb{R}^n$ 上的隱含子群問題的量子演算法[9]. Campbell-Groves-Shepard 在此基礎上提出了攻擊 Soliloquy 公鑰密碼系統的方法[10].
二是去年11月下旬, Regev 在 Tel Aviv Univ. 時期的學生 Lior Eldar 和 Peter Shor 放出的重磅炸彈, 提出新的量子演算法給出了攻擊 LWE 的潛在可能性[11]. 儘管三天後, 由於論文所依賴的假設之一 (據悉由 Regev 指出) 有誤撤稿, 但是事實上仍然存在著 MAGA (make the algorithm great again) 的可能性.

Reference

[1] Simon D R. On the power of quantum computation[J]. SIAM journal on computing, 1997, 26(5): 1474-1483.

[2] Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring[C]//Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on. IEEE, 1994: 124-134.

[3] Bennett C H, Bernstein E, Brassard G, et al. Strengths and weaknesses of quantum computing[J]. SIAM journal on Computing, 1997, 26(5): 1510-1523.

[4] Kuperberg G. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[J]. SIAM Journal on Computing, 2005, 35(1): 170-188.

[5] Hallgren S, Moore C, R?tteler M, et al. Limitations of quantum coset states for graph isomorphism[J]. Journal of the ACM (JACM), 2010, 57(6): 34.

[6] Moore C, Russell A, Vazirani U. A classical one-way function to confound quantum adversaries[J]. arXiv preprint quant-ph/0701115, 2007.

[7] Regev O. Quantum computation and lattice problems[J]. SIAM Journal on Computing, 2004, 33(3): 738-760.

[8] Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM (JACM), 2009, 56(6): 34.

[9] Eisentr?ger K, Hallgren S, Kitaev A, et al. A quantum algorithm for computing the unit group of an arbitrary degree number field[C]//Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, 2014: 293-302.

[10] Campbell P, Groves M, Shepherd D. Soliloquy: A cautionary tale[C]//ETSI 2nd Quantum-Safe Crypto Workshop. 2014: 1-9.

[11] Eldar L, Shor P W. An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem[J]. arXiv preprint arXiv:1611.06999, 2016.

[12] 關於圖同構問題的博客: Reading List: Graph Isomorphism