Enhancing Privacy Preserving for Crowdsourced Monitoring A Game Theoretic Analysis Based Approach

1.   引言

纠错码理论在密码学中的应用与研究已经有了很长的历史。1978 年Berlekamp等人^[1]证明了一般线性码的译码问题是NP完全问题，受到这一事实而启发出的第1个基于纠错码的McEliece公钥加密方案^[2]，开启了纠错码理论在密码学中的应用前景。基于纠错码理论构造的公钥体制，其理论基础是译码问题的困难性，即仅在已知生成矩阵的情况下，在码空间中寻找与给定接收向量Hamming距离最短的码字。纠错码可以被用于构造公钥加密和签名算法、设计对称方案等，在现代密码学中发挥着重要的作用。

列表译码是纠错码理论中一类特殊的译码算法，它可以输出与接收向量在给定Hamming距离内的全部合法码字，并且它的纠错能力超过了传统的唯一译码(unique decoding)算法。对列表译码的研究最早可以追溯到上世纪50年代的Elias^[3]，但当时只是提出了列表译码的概念，并没有给出可行的算法。目前，比较经典的算法有对Hadamard码的列表译码算法^[4]、对Reed-Solomon(RS)码的译码算法^[5]、对代数几何码的译码算法^[6,7]、对Reed-Muller(RM)码的译码算法^[8]等。Sudan^[9]在2000年曾给出过一个关于列表译码的综述，但该综述仅着眼于列表译码在计算复杂性理论中的应用。

列表译码在密码学领域也有着广泛的应用。Goldreich和Levin^[4]通过Hadamard码的列表译码算法，提出了对任意单向函数构造硬核谓词的方法，引出了硬核谓词与列表译码间的微妙联系，启发了大量的工作^[10-18]，列表译码成为了硬核谓词研究中的重要技术之一。列表译码比传统纠错算法更强大的能力，在提高叛徒追踪方案的效率^[19-25]、降低传统基于纠错码的密码方案的参数规模和密钥长度^[26]等方面都发挥了独特的作用。另一方面，列表译码算法和某些特殊问题之间的关联，使其在密码学中得到了更加广泛的应用。如RS码的列表译码问题，本质上就是通过某些点和对应函数值来恢复赋值多项式，因此又被称为多项式重建(Polynomial Reconstruction, PR)问题，基于该问题及相关子问题，可以设计许多有趣的密码方案和协议^[27-30]。而有限域上离散对数问题的求解^[31,32]，也和RS码的列表译码有着深刻的联系。

近几年，列表译码技术在密码学中得到了进一步的应用。在设计能够抵抗量子计算攻击和主动敌手攻击的安全通信协议时，RS码由于具有高效列表译码算法，可以提高信道传输能力和纠错能力，被用来对传递的消息进行编码^[33]。代数几何码作为RS在高亏格曲线上的推广，也有着有效的列表译码算法，受到用列表译码求解有限域上离散对数问题的研究思路的启发，椭圆码的列表译码被用来对椭圆曲线上离散对数进行求解^[34]。在后量子密码的方案设计中，列表译码不仅被用来减小密钥规模，还被用来保护码族的结构，为代数几何码在密码中的应用创造了可能^[35-37]。列表译码技术的强大功能，正在成为密码学飞速发展的助推剂。探究列表译码技术在密码学中的新应用，具有重要的理论意义和实用价值。

本文将对列表译码在密码中的应用进行较为细致的综述。首先将以硬核谓词、叛徒追踪、构造公钥方案、求解离散对数问题和缩短密钥尺寸为例，介绍列表译码在密码学中的早期应用。然后重点介绍列表译码近些年来在密码学中的新应用，如在构造安全通信协议、求解椭圆曲线上离散对数问题、设计新的基于代数几何码的密码方案等方面。

文章组织如下：第2节介绍线性纠错码和代数几何码的基本定义与性质。第3节介绍现有的列表译码算法，主要是RS码和代数几何码的列表译码算法。第4节和第5节分别介绍列表译码技术在密码学中的早期应用和新应用。最后，第6节对全文进行总结，并对未来的发展趋势进行探讨。

2.   纠错码与代数几何码

定义在有限域${\mathbb{F}_q}$上码长为$n$，维数为$k$的$[n,k]$线性码${\cal{C}}$是$n$维线性空间$\mathbb{F}_q^n$的一个$k$维子空间，${\cal{C}}$中的向量称为码字(codeword)。${\cal{C}}$的生成矩阵G是满秩的$k \times n$矩阵，G的行向量构成了${\cal{C}}$的一组基，因此一个线性码的生成矩阵不是唯一的，各个生成矩阵之间可以通过初等行变换相互转化。形式化地，码${\cal{C}}$的定义是${\cal{C}} = \{ {{xG}}|{{x}} \in \mathbb{F}_q^k\}$。给定一个码字${{c}} = ({c_1},{c_2}, ··· ,{c_n}) \in {\cal{C}} \subseteq \mathbb{F}_q^n$，它的汉明重量(Hamming weight)是指码字中非零分量的个数，即${\rm{\rm{wt}}}({{c}}) =$${}_{}|\{ i|{c_i} \ne 0,1 \le i \le n\}$。两个码字${{{c}}_1}$和${{{c}}_2}$之间的汉明距离$d({{{c}}_1},{{{c}}_2})$，是指两个码字中不同分量的个数，而线性码${\cal{C}}$的最小距离$d({\cal{C}})$是${\cal{C}}$中任意两个码字之间汉明距离的最小值。由纠错码的线性性质，有$d({\cal{C}})$就是${\cal{C}}$中所有非零码字重量的最小值，即$d({\cal{C}}) = \min$$\{ {\rm{wt}}({{c}})|{{c}} \in {\cal{C}}\backslash 0\}$。如果$[n,k]$码的最小距离是$d$，那么${\cal{C}}$就是一个$[n,k,d]$线性码。

代数几何码作为RS码的一般推广，由Goppa^[38]在1977年首先提出，并由Janwa和Moreno^[39]在1996年引入密码学。代数几何码是一类定义在代数曲线上的线性码。设${\cal{X}}$是有限域${\mathbb{F}_q}$上的一条不可约曲线，亏格为$g$，记${\cal{X}}$上的函数域为${\mathbb{F}_q}({\cal{X}})$。曲线上的除子$D$是曲线${\cal{X}}$上的点的形式和，即$D = \displaystyle\sum\nolimits_P {{n_P}P}$，其中${n_P} \in \mathbb{Z}\backslash \{ 0\}$仅在有限个点成立。这些系数非零的点组成的集合被称为除子$D$的支座，记作${\rm{supp}}(D)$。除子$D$的次数是${n_P}$的和，即$\deg (D) =$$\displaystyle\sum\nolimits_P {{n_P}}$。对任意$P \in {\cal{X}}$和$f \in {\mathbb{F}_q}({\cal{X}})\backslash \{ 0\}$，定义$f$在点$P$的赋值${v_P}$是从${\mathbb{F}_q}({\cal{X}})$到$\mathbb{Z} \cup \{ \infty \}$的映射。如果 ${v_P}(f) = m > 0$，则称$P$是m重零点；如果${v_P}(f) =$$m < 0$，则称$P$是$- m$重极点。任意函数$f \in {\mathbb{F}_q}({\cal{X}})\backslash \{ 0\}$可以与主除子相对应。$f$的主除子的定义为${\rm{div}}(f) = \displaystyle\sum\nolimits_P {{v_P}(f)P} {{v_P}(f)P}$，主除子的次数总是0。设$G = \displaystyle\sum\nolimits_P {{n_P} }$是曲线${\cal{X}}$上任一个$\alpha$次除子。用${\cal{L}}(G)$表示所有非负有理函数构成的集合，即${\cal{L}}(G) = \{ f|{\rm{div}}(f) + G \succ {\rm{0}}\} \cup \{ 0\}$。由Riemann-Roch定理，${\cal{L}}(G)$是${\mathbb{F}_q}$上维数有限的向量空间，它的维数为${\rm{dim}}({\cal{L}}(G)) = \alpha - g + 1$，其中g是曲线${\cal{X}}$的亏格。给定一条不可约曲线${\cal{X}}$和${\cal{X}}$上的函数域${\mathbb{F}_q}({\cal{X}})$，设${P_1},{P_2}, ··· ,{P_n}$是${\cal{X}}$上互不相同的有理点。由这$n$个点定义除子$D = {P_1} + {P_2} + ··· + {P_n}$。设$G$是${\cal{X}}$上任意满足$\{ {P_1},{P_2}, ··· ,{P_n}\} \cap {\rm{supp}}(G) =\varnothing$的除子，则代数几何码${\cal{C}}(D,G)$由映射${\rm{ev}}:{\cal{L}}(G) \to \mathbb{F}_q^n$定义，其中${\rm{ev}}(f) = (f({P_1}),f({P_2}), ··· ,f({P_n}))$。因此，${\cal{C}}(D,G) =$${\rm{image}}({\rm{ev}})$。如果$G = \displaystyle\sum\nolimits_P {{n_P}P}$是一个$\alpha$次除子，那么${\cal{C}}(D,G)$就是${\mathbb{F}_q}$上的一个$[n,k = \alpha + g - 1,d]$码，且有$d \le n - k + 1$。更多代数几何码的性质可以参阅文献[40]。

3.   列表译码技术

码字在信道上传送的过程中可能出现错误。如果${{c}}$是一个码字，而${{r}} = {{c}} + {{e}}$是接收到的向量，称${{r}}$为接收向量(或受损码字)，${{e}}$为错误向量，$\{ i|{e_i} \ne 0\}$为错误位置，${\rm{wt}}({{e}})$为错误重量。如果${\rm{wt}}({{e}}) < d/2$，那么在码字空间里可以找到与该接收向量对应的唯一码字${{c}}'$，且一定有${{c}} = {{c}}'$。这种译码方式叫做唯一译码。但研究者们很早就注意到，从接收向量恢复码字并不是只有唯一译码能完成的。上世纪50年代，Elias^[3]首先提出了列表译码的概念，在列表译码中，输出结果不再是某个特定的码字，而是到接收向量的距离在给定范围内的全部码字的列表。显然，列表译码可以纠正重量更大的错误，有着比唯一译码更强的纠错能力。第1个具体的列表译码算法是由Goldreich和Levin等人^[4]在1989年提出的关于Hadamard码的一种随机译码算法，针对二元域上的Hadamard码，可以在${\rm{poly}}\left(\lg n,\dfrac{1}{\gamma }\right)$的时间内，给出到接收向量的距离在$\left(\dfrac{1}{2} - \gamma \right)n$的所有码字。目前在实际中应用较多的代数几何码及其列表译码，将在下面做出详细介绍。

1996年，Sudan^[5]给出了RS码的列表译码算法，该算法可以纠正接收向量中重量不超过$n - \sqrt {2nk}$的错误。随后，Shokrollahi和Wasserman^[41]将这一算法进行了推广，从而可以对任意代数几何码进行译码，但可以纠正的错误上界仍然是$n - \sqrt {2nk}$。1999年，Guruswami和Sudan^[6,7]对之前的算法进行了优化，将RS码和代数几何码可以纠正的错误上界提高到了$n - \sqrt {nk}$，即该算法可以有效地输出一个表单，该表单包含所有以接收向量为中心，半径不超过$t = n - \sqrt {nk}$的码字。进一步地，列表译码算法${\rm{ListDecode}}({\cal{C}},{{r}},t)$以一个$[n,k]$线性码${\cal{C}}$，一个接收向量${{r}}$和参数$t \le n - \sqrt {nk}$为输入，输出一个码字表单，该表单里的码字到r的汉明距离不超过t。表1给出该算法的一个简短描述，更多信息请参考文献[6,7]。

表  1  Guruswami-Sudan列表译码算法${\rm{ListDecode}}({\cal{C}},{{r}},t)$

输入：有限域${\mathbb{F}_q}$，曲线${\cal{X}}$，除子$G = \alpha Q$和$D$，接受向量${{r} } = ({r_1},{r_2}, ··· ,{r_n})$ 以及错误重量上界$t$。
初始化：
(1) 设置表单${\Omega _r}: = \varnothing$；
(2) 由$n,k,t$计算译码参数$l$，要求$l > \alpha$；一般地，设 　　 $r = 1 + \dfrac{{(2g + \alpha )n - 2gt + \sqrt {{{((2g + \alpha )n - 2gt)}^2} - 4({g^2} - 1)({{(n - t)}^2} - \alpha n)} }}{{2{{(n - t)}^2} - \alpha n}}$, $l = r(n - t) - 1$；
(3) 固定${\cal{L}}(lQ)$的一组极基$\{ {\phi _{ {j_1} } }:1 \le {j_1} \le l - g + 1\}$，使得Q最多为${\phi _{{j_1}}}$的${j_1} + g - 1$次极点；
(4) 对任意${P_i}$, $1 \le i \le n$，找${\cal{L}}(lQ)$的一组零基$\{ {\psi _{ {j_3} } }:1 \le {j_3} \le l - g + 1\}$，使得${P_i}$为${\psi _{{j_3},{P_i}}}$重数(至少)为${j_3} - 1$的零点；
(5) 计算集合$\{ {a_{ {P_i},{j_1},{j_3} } } \in {\mathbb{F}_q}:1 \le i \le n,1 \le {j_1},{j_3} \le l - g + 1\}$，使得对任意i和${j_1}$，都有${\phi _{{j_1}}} = {\Sigma _{{j_3}}}{a_{{P_i},{j_1},{j_3}}}{\psi _{{j_3},{P_i}}}$。
插值： 　　 令$s = \dfrac{{l - g}}{\alpha }$，找非零多项式$H \in {\cal{L}}(lQ)[T]$，它具有以下形式：$H[T] = \displaystyle\sum\limits_{ {j_2} = 0}^s {\displaystyle\sum\limits_{ {j_1} = 1}^{l - g + 1 - \alpha {j_2} } { {h_{ {j_1},{j_2} } }{\phi _{ {j_1} } }{T^{ {j_2} } } } }$；
其中，系数${h_{{j_1},{j_2}}} \in {\mathbb{F}_q}$满足：至少有一个${h_{{j_1},{j_2}}}$是非零的，且对任意$i \in [n]$，和满足${j_3} + {j_4} \le r$的${j_3} \ge 1,{j_4} \ge 0$，有 　　 $h_{{j_3},{j_4}}^{(i)} = \displaystyle\sum\limits_{{j_2} = {j_4}}^s {\displaystyle\sum\limits_{{j_1} = 1}^{l - g + 1 - \alpha {j_2}} {\left( \begin{array}{l} {j_2} \\ {j_4} \\ \end{array} \right)r_i^{{j_2} - {j_4}} \cdot {h_{{j_1},{j_2}}}{\alpha _{{x_i},{j_1},{j_3}}} = 0} }$
求根：
找到$H[T]$的所有根$h \in {\cal{L}}(\alpha Q) \subseteq {\cal{L}}(lQ)$。对每一个$h$，检查是否对至少$n - t$个$i \in \{ 1,2, ··· ,n\}$有$h({P_i}) = {r_i}$，即$d({{r} },{{c} }) \le t$。如果成 　　 立，将$h$加入${\Omega _r}$。
输出：码字列表${\Omega _r}$。

下载: 导出CSV 

| 显示表格

目前为止，列表译码是对代数几何码最有效的译码算法之一。文献[6,7]中给出的插值和求根算法实现效率比较低，后续有大量的工作给出了更有效的算法，如文献[42,43]等。Muralidhara 等人^[44]给出了纠错能力超过$n - \sqrt {nk}$的RS码的列表译码算法，他们证明了对任何常数$\rm c$，以$n - \sqrt {nk} +{\rm c}$为半径的汉明球中，有至多${\cal{O}}\left({n^{2{\rm c}\sqrt \alpha /{{(1 - \sqrt \alpha )}^2} + {\rm c} + 2}}\right)$个合法码字。Guruswami和Xing在文献[45]中利用蒙特卡洛算法，给出了对任意固定$\epsilon > 0$，可以在${\cal O}(1/\epsilon )$时间内，纠正$(1 - R - \epsilon )$比例的错误的列表译码算法，其中$R = k/n$，该算法不仅适用于RS码，也适用于秩度量的Gabidulin码，是第一个可以纠正超过$d/2$个秩错误的列表译码算法。

4.   列表译码在密码学中的早期应用

列表译码在密码中早期的应用起源于单向函数硬核谓词的构造，之后在叛徒追踪、构造基于多项式重构的密码体制，及减少基于纠错码的密钥尺寸等方面均有所应用。

4.1   硬核谓词

函数$f$的硬核谓词是一个布尔函数$h$，它代表着与函数$f$原像相关的信息中，最不容易被求逆的某一比特。故而当$f$被普遍认为是单向函数后，$h$的像便展现出优秀的伪随机性。这使得它在伪随机数生成器、伪随机函数等密码学理论中具有重要作用。1982年Blum和Micali^[10]首次发现硬核谓词的存在后，探讨这一有趣现象的工作陆续出现。Goldreich和Levin^[4]发现对任意单向函数$f(x)$，容易构造新的单向函数$g(x,r)$及其硬核谓词$h(x,r)$。证明思路是将硬核谓词转换成Hadamard码的码字集合，将与待求逆的单向函数值$g(x,r)$相关的硬核谓词值$h(x,r)$转成受损码字，再通过寻找与受损码字距离最为接近的一批码字来对$g(x,r)$求逆。这种对任意单向函数构造硬核谓词的方式，本质上是一个对Hadamard码的多项式时间列表译码算法。

2003年，Akavia 等人^[11]中给出了一套对于任意抽象群上单向函数的硬核谓词的构造和证明方法，首次明确地展示了列表译码技术在硬核谓词研究中的作用。该方法中的关键一步是寻找任意函数的坐标所对应的傅里叶基，可保证整个规约算法能在多项式时间执行。王明强等人^[12]在此基础上提出了基于列表译码方法在查询访问模型下含错学习问题的求解算法，其结果也可以理解为建立了一类单向函数的困难比特。2009年，Morillo等人^[13]扩展了Akavia的工作，证明了对于定义在$N$阶循环群上可以乘法访问的任意函数而言，其所有的比特都是安全的。之后，谢小荣等人^[14]证明了$ax + b\;{\rm{mod}} p$的任意比特位是$p$阶循环群上积性码可接近的单向函数的硬核谓词。Duc等人^[15]在2012年用列表译码技术证明了有限域${\mathbb{F}_q}$上椭圆曲线的单向函数，其输入的任意一比特都是硬核的。同年，Fazio等人^[16]给出进一步成果，他们在有限域${\mathbb{F}_{{p^2}}}$上定义了一个Diffie-Hellman(DH)问题的变体，并利用列表译码技术证明了秘密DH值的其中一个坐标的任意比特位是无法预测的。2016年，Wang等人^[17]在文献[16]的基础上，进一步给出了如下结论：在${\mathbb{F}_{{p^2}}}$上的计算性DH问题的秘密值的所有单独的比特位都是硬核的，而对于在${\mathbb{F}_{{p^t}}}$上的计算DH问题而言，几乎所有的单独比特位都是硬核的。2006年，Kawachi等人^[18]提出了对于任意量子单向函数的3个量子硬核函数。通过提出主要技术为对经典纠错码的量子列表解码方法，他们证明了伪随机数生成器的的量子硬核特性，给出了一个简单但强大的标准用以将多项式时间可计算码转化为量子单向函数的量子硬核谓词。

4.2   叛徒追踪

叛徒追踪方案考虑的是数字资源通过网络广播的手段发送给各个订阅者的场景。在付费电视和网络等应用中，服务提供者以公钥将资源加密，并给予订阅者内置私钥的硬件或软件实现的解码器用于解密，从而仅有付费用户能够获得服务。然而，合法的订阅者可以通过复制解码器或提取解码器中的私钥，制作更多的解码器分发给未被授权的用户。“叛徒”就是指进行上述行为的授权用户。叛徒追踪方案希望通过提升授权用户进行叛徒行为的代价来减少或阻止这种行为的发生。具体来讲，如果多个用户合谋生成非授权的解码器，那么至少其中一个合谋者会被检测出来。由于合谋者均不希望自己成为被追踪的一个，上述特性已经对于非授权行为造成可观的警示。早期的叛徒追踪策略通过分发不同的私钥组合给授权用户，在定位其身份的同时给予其解密的能力，然而这种策略仅能概率性地追踪叛徒。

为了给出确定性的追踪策略，Boneh等人^[19]首次尝试使用了代数方法来设计方案。该叛徒追踪方案的追踪性与安全分别基于离散对数问题(Discrete Logarithm Problems, DLP)和判定性DH问题，并且需要借助一种线性空间追踪码。如果由这种码产生的$2k$个密钥是线性无关的，那么叛徒们在生成新的私钥时，任何$k$个密钥的凸组合是可以被唯一追踪的(尽管不一定高效)，其中$k$是叛徒个数上界。作者进一步指出，如果使用RS码，并以适当的方式从其中产生私钥，那么利用RS码的列表译码算法，可以实现更有效的追踪。Fernandez等人^[20]提出了以代数几何码及其列表译码算法找出所有非诚实用户的方法。随后的一系列工作，如文献[21-23]等，均体现出列表译码技术在以纠错码为基础的叛徒追踪策略中有诸多潜在的用途。2001年，Silverberg等人^[24,25]利用列表译码技术构造了一个叛徒追踪方案，该方案可以高效地列举出所有可能的叛徒。

4.3   构造密码协议

RS码的列表译码问题又被称为PR问题，即给定参数$k,t$和$n$个点$({x_i},{y_i})$，求全部次数不超过$k$的多项式$P(x)$，使得在至少对$t$个$i$的值有${y_i} = P({x_i})$。Naor和Pinkas在文献[46]中利用PR问题构造了多种实用的加密应用，但当时并没有对方案的安全性进行严格的证明。Kiayias和Yung^[28]研究了PR问题的困难性，证明了PR及其相关子问题，指标PR(Index-PR)问题在密码学意义上具有很强的鲁棒性，非常值得在密码学中被进一步研究和应用。他们提出了判定版本的PR问题，并证明了该判定问题中部分信息的提取是困难的，即在新的点上预测某些可计算函数的值是困难的；此外，PR实例是伪随机的，它们与随机点集不可区分。这些结果表明PR问题在密码学意义上是非常健壮的，适合在密码构造中使用。多样本多项式重建问题(Multisample -PR, MPR)作为PR问题的自然推广，在文献[27]中被第1次提出，并在文献[47]中得到了进一步的研究。MPR问题具有与PR问题相似的鲁棒性。Kiayias和Yung^[28]对相应的指标MPR问题做了研究。基于MPR问题的困难性，他们在文献[30]中给出了两种类型的多项式表示的安全游戏模型，并在此基础上设计了一系列密码协议。他们设计的私有信息检索协议能保证检索结果正确，且仅有对数级的复杂度。此外，他们还给出了列表交集预测、不经意协商等多种具体协议，这些协议可以被用于安全计算、结算托管等，从而在电子商务中发挥作用。

利用PR和MPR问题还可以设计对称加密方案，产生的流(块)密码体制具有许多良好的性质^[30]，如语义安全、纠错解密(error-correcting decryption)、超短密钥、在有限域上具有乘法有解的全同态性等。而在公钥体制方面，Augot和Finiasz^[48]利用PR问题构造了一种公钥加密方案，该方案的公钥是一个困难PR问题实例，而私钥是对应的错误位置。加密时，由公钥和随机数作标量乘的结果与明文相加，再添加额外错误扰动，得到密文；解密时，先由私钥去除部分错误，再由译码算法去除剩余的错误。该方案与McEliece方案相比有着更小的密钥尺寸，但方案的部分参数被Coron^[49]攻破，Kiayias和Yung^[29]进一步证明了利用列表译码技术可以构造对该方案的通用攻击。

4.4   ${{\mathbb{F}}_q}$上DLP求解

Justesen和Hoholdt^[50]指出，对于任意整数$g < n$，存在至少一个半径为$n - g$的汉明球，包含了至少$(_g^n)/{q^{g - k}}$个码字。但是当$g$的值从$k$逐渐提高到$n$时，$(_g^n)/{q^{g - k}}$会下降到低于1的值，此时$g$的值是小于$\sqrt {nk}$的。即如果用$\hat g(n,k,q)$表示使得$(_g^n)/{q^{g - k}}$小于1的最小整数，$\hat g(n,k,q)$和$\sqrt {nk}$之间存在一个间隙。那么，当错误重量为$n - \hat g(n,k,q)$时，列表译码究竟有多困难呢？Cheng和Wan在文献[31]中对此问题进行了研究，并发现该问题和有限域上的DLP有着密切的联系。

DLP是数论中的经典困难问题之一，目前已知的最优算法仍然是亚指数级的计算复杂度，因此在密码学中被广泛应用于构造密码方案。DLP的一个实例$({\mathbb{Z}_p}^*,g,y)$是，给定乘法群${\mathbb{Z}_p}^*$和其中一个生成元$g$，对 ${\mathbb{Z}_p}^*$中的元素$y$，求整数$a$, $0 \le a \le p - 1$，使得${g^a} = y$。如何提高DLP的求解效率、是否存在一些特殊参数使得相应的DLP是容易的，都是密码学中的研究热点。

Cheng和Wan在文献[31]通过建立到接收向量的距离为$n - g$的码字和${\mathbb{F}_q}$上$g$次多项式环的一一映射，证明了如果列表译码可以纠正$n - \hat g(n,k,q)$个错误，那么有限域${\mathbb{F}_{{q^{\overset{\lower0.2em\hbox{$\smash{\scriptscriptstyle\frown}$}}{g} (n,k,q) - k}}}}$上的DLP是容易的。另外，若$h$和$g$分别是对任意$\epsilon > 0$满足$q \ge \max$$({g^2},{(h - 1)^{2 + \epsilon }})$和$g \ge (4/\epsilon + 2)(h + 1)$的正整数，求解${\mathbb{F}_{{q^h}}}$上的以$b(\alpha )$为基的$t(\alpha )$的离散对数时，通过构造赋值点集为$\{ (a, - f(a)/h(a) - {a^{g - h}})|a \in {\mathbb{F}_q}\}$的RS码，并以类似于指数演算法的方式，重复运行错误界为$q - g$的列表译码来收集方程，再分解因式，最终能以$1 - {1}/{{2n}}$的概率求得DLP的解。

同年，Cheng还在文献[32]中提出了一种算法，在满足一些特定条件的情况下，利用RS码的列表译码技术，可以在关于$\lg ({q^n})$的多项式时间内，对给定的有限域${\mathbb{F}_{{q^n}}}$上的$g$和${g^e}$，找到离散对数$e$从而给出了${\mathbb{F}_{{q^n}}}$上有界数字和形式的DLP更有效的求解算法。Cheng给出的算法^[38]以指数演算法为基础，是一种随机算法，适用于对有限域${\mathbb{F}_q}$的Kummer扩张${\mathbb{F}_{{q^n}}}$上的DLP的求解。该算法以有限域${\mathbb{F}_{{q^n}}} = {\mathbb{F}_q}[x]/({x^n} - a)$及其生成元$g$和求解目标$y = {g^e}$为输入，希望输出求解结果$e$。算法对参数的要求是：(1) $n|q - 1$; (2) $0 \le e \le {q^n}$且${S_q}(e) \le n$; (3) $g = \alpha + b$，其中${\mathbb{F}_q}(\alpha ) = {\mathbb{F}_{{q^n}}}$, $b \in {\mathbb{F}_q}^*$且${\alpha ^n} \in {\mathbb{F}_q}$。算法的核心思想是将$y$表示为$f(\alpha )$的形式，其中$f \in {\mathbb{F}_q}[x]$且$\deg (f) \le n$，并将该多项式分解为$f(x) = {(x + b)^{{e_1}}}{({h^2}x + b)^{{e_2}}} ··· {({h^{n - 1}}x + b)^{{e_{n - 1}}}}$的形式，其中分解得到的幂次指数就是$e$的$q$元分解表示的系数，即$e = {e_0} + {e_1}q + ··· + {e_{n - 1}}{q^{n - 1}}$。这一步骤几乎与RS码的列表译码算法相同，因此利用Guruswami-Sudan的列表译码算法，就可以对DLP求解算法进行有效的实现。

4.5   减小公钥尺寸

目前公认的抗量子密码主要是基于格、基于纠错码、基于多变量和基于哈希的方案。美国国家标准技术局 NIST已经于2018年开始对抗量子密码方案的征集，在他们收到的69个草案中有20个是利用纠错码设计的，而进入第2轮筛选的26个方案中有7个是基于纠错码的，基于纠错码的密码体制在量子计算时代的地位可见一斑。McEliece方案^[2]是经典的基于纠错码的公钥加密方案，其安全性依赖于线性码的一般译码问题和Goppa码的区分问题，被认为是可以抵抗量子计算攻击的公钥加密方案。McEliece方案加解密算法都非常高效，但过大的公钥规模限制了其实用性，因此许多工作围绕着缩减McEliece体制的密钥尺寸进行。目前，比较主流的减小密钥长度的方法有使用准循环(Quasi-Cyclic, QC)码、准并矢(Quasi-Dyadic, QD)码，或转用基于秩度量(rank metric)的编码等。这些方法都使用了具有特殊结构的码族，在某些参数或码族选择不合适的情况下，可能会导致攻击。

Barbier和Barreto在文献[26]中提出，将传统基于编码的密码体制中调用的译码算法，从唯一译码变为列表译码，从而在加密时可以引入重量超过最小距离$d$的一半的错误向量。上述改变将增加一般译码问题的难度，可以选用长度和维数更小的码。进一步地，上述改变不会给使用的原始码增加额外的结构特点，或减小原始码的空间，从而不会带来新的安全隐患。与此同时，对所有基于编码的密码方案的通用攻击，信息集译码攻击，有着和错误重量密切相关的算法复杂度^[51]，随着错误重量的增加，ISD的算法复杂度是呈亚指数级增加的。因此，和使用唯一译码的方案相比，采用列表译码技术能够用更小的参数来抵抗同样级别的ISD攻击，从而达到减小密钥存储空间的效果。他们指出，使用二元Goppa码的列表译码来改进标准McEliece加密方案，可以减少4%的密钥存储空间，如果将Goppa码换成QD码，可以减少21%的密钥存储空间。虽然他们提出的使用QD码的方案并不能完全避免文献[52]提出的攻击，但使用列表译码来减小参数规模进而减小密钥尺寸的思想，为提高McEliece方案的实用性提供了思路。

5.   列表译码在密码学中的新应用

5.1   安全通信

物联网的不断普及和量子计算的飞速发展，对当今网络物理世界的长期信息安全保障提出了巨大的挑战。当前通讯网络的极端连通性意味着对数据的保护必须是端到端的，并且保护必须要落实在网络的所有层，而量子计算的发展前景还要求算法和协议在量子计算时代仍然保持安全。能否在物理层假设上构建端到端的安全通信成为了一个值得关注的问题。

Wang等人在文献[33]中，提出了一种能够抵抗敌手的包括窃听、在被窃听的部分码字上添加噪声扰动等攻击行为的交互协议。该协议建立在Wyner第2类窃听模型^[53]下，即通信双方所用的信道，被拥有无限计算能力的敌手监听，且敌手可以选择查看并修改固定比例的通信内容，而通信仍然达到信息论安全，是一种特殊的对抗窃听信道(AWTP channel)。该协议可以分为两步：首先通过密钥协议(Key Agreement Protocol)步骤在通信双方之间建立共享密钥，该密钥被用来计算消息的MAC，从而接收方可以判断敌手是否对信道上的消息进行了篡改。在第2步中，双方将进行多个回合的前向传输和重复请求，确保接收方可以得到正确的消息，而敌手得不到任何有用的信息。在重复请求中，接收者会要求重传一些前一轮中的符号。在协议中，信道上传送的所有消息都使用RS码编码，直到接收方得到了足够译码的正确分量。在前向信道编码时，首先对消息用特定长度的随机数进行填充，再添加删余错误，从而保障对敌手不能从对码字的观察中获得额外的信息。而在后向信道中，同样采用RS码进行编码来保障消息的可靠性。该方案选用RS码作为主要编码方法的主要原因，就是它有着高效的列表译码算法，从而能够纠正包括噪声和删余的更多错误，有更强大的容错能力，从而可以提高通信效率。可否利用具有更好的代数性质并且能够列表译码的其他纠错码，构造更有效或性能更好的此类协议是这个方向值得深入探讨的内容。

此外，随着5G技术的发展和推广，极化码的列表译码技术引起了国内外的关注^[54-56]。目前，已经有将极化码应用于设计密码方案的研究^[57,58]，但这些的方案的安全性均受到了挑战^[59]。如何将极化码及其列表译码应用于密码方案的设计和安全通信协议的设计，为5G通信的安全护航，也是很有意义的研究方向。

5.2   椭圆曲线上离散对数问题的求解

上世纪80年代，基于椭圆曲线的密码体制(ECC)开始发展。由于在椭圆曲线上实现的公钥加密、数字签名、密钥交换等密码原语，在和传统方案达到相同安全级别的要求下，所需要的密钥更小，实现速度更快，已经在过去的几十年中被广泛的使用到各种应用和程序之中。而ECC安全性的关键，就在于椭圆曲线上离散对数问题(ECDLP)的困难性。ECDLP问题的一个实例$({\mathbb{F}_q},\mathcal{E}({\mathbb{F}_q}),p,Q,P)$是：定义在有限域${\mathbb{F}_q}$上的椭圆曲线$\mathcal{E}({\mathbb{F}_q})$, $P \in \mathcal{E}({\mathbb{F}_q})$为其上的一个$p$阶点，$\left\langle P \right\rangle$为以点$P$为生成点构成的$p$阶子群，对$Q \in \left\langle P \right\rangle$，求$0 \le s < p$使得$Q = sP$。目前为止，除了一些特殊的曲线，ECDLP求解算法的计算复杂度仍然是${{O}}(\sqrt p )$。

Goppa在1977年提出了代数几何码的概念^[38]，而定义在椭圆曲线上的代数几何码就是椭圆码。对于$[n,k]$椭圆码来说，它的最小距离一定是$n - k$或$n - k + 1$，这取决于是否存在$\{ {P_{{i_1}}},{P_{{i_2}}}, ··· ,{P_{{i_k}}}\} \subseteq$$\{ {P_1},{P_2}, ··· ,{P_n}\}$使得${P_{{i_1}}} + {P_{{i_2}}} + ··· + {P_{{i_k}}} - G$是一个主除子。而文献[60]和文献[61]先后关注到，曲线$\mathcal{E}$上的ECDLP的解和定义在$\mathcal{E}$的椭圆码的最小距离有着密切的关联，这就为求解ECDLP问题提供了新的思路。通过寻找椭圆码的最小重量码字，就有可能解决相应的ECDLP。虽然椭圆码的最小距离问题在文献[61]中被证明了是NP困难问题(从而寻找最小重量码字也是NP困难问题)，但理论上还是有可能构造出比穷搜索更有效率的算法。

Zhang和Liu在文献[34]中提出了一种解决ECDLP问题的新方法。对于任何ECDLP，首先构造一个对应的椭圆码，然后利用列表译码技术来寻找最小重量码字，再通过这个码字解决ECDLP问题。具体来说，对一个ECDLP问题的实例$({\mathbb{F}_q},\mathcal{E}({\mathbb{F}_q}),p,Q,P)$，假设$P$的阶是素数$p$。令$\theta \!=\! \left\lceil {{{\log }_2}p} \right\rceil$, $n = 2\theta$, $k = \left\lfloor {(\theta + 1)/2} \right\rfloor$。定义${P_i} = {2^{i - 1}}P$，选取${\mathbb{Z}_p}$上的随机数${r_2},{r_3}, ··· ,{r_{n - \theta }}$，定义${P_{\theta + j}} = {r_j}Q$，其中$j = 1,2, ··· ,n - \theta$。由除子$G = k{\cal{O}}$和$D = \displaystyle\sum\nolimits_{i = 1}^n {{P_i}}$ 构造椭圆码${\cal{C}}(G,D)$。调用列表译码算法，直到对一个接收向量译出两个码字，就找到了${\cal{C}}(G,D)$的最小重量码字${{c}} = ({c_1},{c_2}, ··· ,{c_n})$，设其中的非零分量为${c_{{i_1}}},{c_{{i_2}}}, ··· ,{c_{{i_k}}}$。假设${i_{j - 1}} \le \theta$且${i_j} > \theta$，则计算$s' \equiv - {\left(\displaystyle\sum\nolimits_{k = j}^\theta {{r_{{i_k} - \theta }}} \right)^{ - 1}}\displaystyle\sum\nolimits_{k = 1}^{j - 1} {{2^{{i_k} - 1}}} \;{\rm{mod}} p$，若验证有$Q = s'P$，则找到了相应ECDLP的解。

可以发现，对ECDLP的求解和有限域上DLP的求解，其实有很大的不同。对DLP的求解^[31,32]主要基于对有限域结构的观察，只适用于某些特殊的有限域，对素域上的DLP问题是无法求解的。而Zhang等人的结果，是一种求解ECDLP的通用解法，不受有限域类型和大小限制。虽然目前文献[34]中算法的成功概率并不是很高，却是第1个通过列表译码技术解决ECDLP的算法，具有深刻的理论意义。

5.3   设计新的基于代数几何码的公钥加密方案

随着量子计算的快速发展，目前使用的基于整数分解、离散对数等数学问题困难性假设构造的公钥方案的安全性受到了极大的挑战。基于编码技术的密码方案作为能够抵抗量子攻击的方案，引起了研究者的关注。基于编码的密码方案主要有3种形式，分别是以一般译码问题为困难假设的McEliece体制、以校验子译码问题为困难假设的Niederreiter体制，和以LWE问题为困难性假设的密码体制。其中，一般译码问题和校验子译码问题已经被证明是等价的，并且都是NP完全的^[1]。而椭圆码的最小距离判定问题和最大似然译码问题也是NP困难的^[61]。

代数几何码的概念在1996年被Janwa和Moreno引入密码学领域^[39]。代数几何码一方面将存储码的方式从生成矩阵转化为曲线上的除子和有理点集，减小了传统的McEliece方案的密钥尺寸；另一方面能够提供更多的参数选择空间，从而使得方案的应用更加灵活。然而其结构过于特殊，遭到了大量的攻击。1992年，Sidelnikov和Shestakov^[62]攻破了使用亏格为0的代数几何码，也就是 RS码的Niederreiter方案；Minder等人^[63,64]结合ISD对亏格小于等于2的曲线上定义的代数几何码进行了攻击；Couvreur 等人^[65]证明了对高亏格曲线上定义的代数几何码，存在多项式时间的攻击算法，随后在文献[66]中，他们又结合ECP译码技术^[67,68]对任意亏格的代数几何码给出了多项式时间的攻击。至此，代数几何码几乎已经被认为不适用于构造密码体制了。

2016年，Marquez-Corbella等人^[35]提出利用RS码构造广义$(U|U + V)$码，进而设计公钥加密方案的思路。使用广义$(U|U + V)$码可以有效隐藏RS码的结构信息，从而可以抵抗针对RS码的结构攻击，进而利用RS码的特殊结构来减小私钥尺寸；而RS码具有有效的列表译码算法，和$(U|U + V)$码的译码算法相结合，可以进一步提高译码算法的纠错能力，减小公钥尺寸。

Zhang等人^[36]构造了一种能抵抗已知攻击的基于椭圆码的方案ECC²，该方案使用了列表译码技术，从而可以纠正超过码字最小距离1/2的错误，这正是抵抗针对代数几何码的已知攻击的关键。该方案的第1个版本^[36]中，所采用的McEliece方案的变种并不能达到IND-CPA安全，已经在新的版本^[37]中进行了更正，即将加在消息上的随机向量由第1部分密文中被编码的向量，变成了错误中的非零位组成的新向量。为了抵抗文献[63]针对椭圆码的结构攻击，利用文献[61]中证明椭圆码最小距离问题是NP完全问题的思路，通过将一个背包问题实例转化成椭圆码，构造出赋值点远少于曲线上有理点的椭圆码，从而难以找到这样的椭圆码上的最小重量码字，这就打破了文献[63]中攻击方法的假设前提。而针对ECP攻击，利用ECP存在当且仅当错误重量不超过码的最小距离1/2的结论，添加超过限制重量的错误，从而ECP译码方法失效，无法直接攻击。同时保证从接收向量中寻找额外错误的位置也是不可行的，即先剔除超过码的最小距离1/2的错误，再使用ECP译码也是不可行的。在解码时，通过列表译码技术，直接纠正接收向量中的全部错误，译得码字，再进行解密步骤。该方案的安全性在标准模型下归结到椭圆码的校验子译码问题上。在此基础上，能否考虑利用其他代数几何码来构造安全实用的，抵抗量子攻击的密码体制，是非常值得研究的问题。

6.   结束语

列表译码自诞生起，便成为了纠错码译码研究方面的一个关注点。尽管通讯领域非常需要其强大的抗噪声能力，但广义上，列表译码的功能与研究意义绝不仅限于此。从当前的情形看，列表译码的思想与底蕴深厚的纠错码理论还为其它学科中一些繁琐的现象提供了自然、严谨、相对简单的描述或解释方法。熟悉Goldreich-Levin硬核谓词的读者应当能更加容易地体会这一观点。随着纠错码与密码学的融合，前者成为了后量子密码体制中一个独具特色的计算困难性提供源。可以说，当前的纠错码理论已可以系统化地为密码学家诠释出基于纠错码的候选单向陷门函数的原理与结构。这种看似平凡的诠释却在计算复杂性的观点下证实了基于纠错码的密码体制的存在性。然而，存在性与实用性往往还存在着较大的间隙。为了缩小这个间隙，众多理论或技术上的屏障成为了亟待解决的问题。鉴于译码算法与求逆前述单向陷门函数的紧密联系，与列表译码相关的内容无疑将成为攻克这些屏障的道路上，最值得研究的课题之一。

首先来看列表译码算法本身。无论是从编码学还是密码学的角度，更少的计算资源、更强的纠错能力和更广的码族覆盖面必定是其最终追求的目标。因此，从提高运行效率与纠错能力的角度提高和改进现有算法，或是针对码族的特征结构完成其列表译码从无到有的转变均是十分有意义的研发工作。具体来看，当前使用的列表译码主要还是Guruswami-Sudan算法。如果尝试将其应用于代数几何码，那么需要寻找对应除子空间中的一组零基和一组极基。一般而言，极基容易得到，但零基并非如此。目前数学界普遍认为，对于由任意一条代数曲线上任意除子生成的Riemann-Roch空间而言，构造其一组零基是一个非常困难的计算问题；仅在某些特殊曲线上，有效的零基构造方法是已知的。既然密码方案中使用的代数几何码只能在素域上的低亏格曲线上构造，一个自然的想法便是如何针对这类特殊的曲线，改进已知的零基构造算法，使之能够服务于密码中的代数几何码，进而使列表译码成为可能。另一方面，还可以探究如何充分地运用循环码和准循环码等编码的特殊结构，用以提高其现有列表译码算法的效率。这些问题的解决将为列表译码在密码学中的应用前景提供可观的促进作用。

然后来看与列表译码相关的密码方案与协议。毋庸置疑，列表译码技术本身的提升对上层的方案与协议有正面的影响，但针对特定方案的具体特点，给出适宜的修改策略亦是对其进行优化和改进的思路。细化来看，既然当前常用的PR，也即RS码的列表译码问题，能够被用于多种密码方案和协议设计，而且多元多项式重建与列表译码存在着微妙的联系，一个直观的设想为是否能利用多元多项式重建问题以及与PR相关的设计思路，提出功能相同但性能更为优越的方案。与此同时，目前存在多个利用列表译码技术减小密钥存储空间或者保护码的特殊结构的方案，可见以列表译码为基于纠错码的方案进行减负提速的研究很可能是大有文章可做的。遗憾的是，在使用列表译码强大纠错能力的同时，付出的代价是更长的计算时间。故而为了使得上述方案更为贴近实际使用，往往还需要在密钥存储空间与解密效率或密钥安全性等方面做出权衡。除此之外，基于编码的签名等技术需要相应的校验子译码算法，而利用编码构造基于身份的加密系统时，更是需要一类对任意向量都能进行校验子译码的码族。这些问题使得寻找合适的码族与相应的列表译码算法变得有意义起来。

接下来考虑以列表译码求解DLP等问题的密码分析类研究。DLP是一个跟循环群有关的跨度相对很广的计算问题。由此，研究思路呈现两个方面：一是尝试能否将一些目前不太常用的有限域上的DLP，进行放宽限制条件的处理，然后将现有的方法扩展到其上；二是对这些不常用类型的有限域结构进行观察和分析，随后利用列表译码技术设计新的DLP求解方法。与此同时，对ECDLP问题的攻击算法的改进中，很可能会遇到缺乏合适的纠错码及其列表译码算法的情况。由于不同参数下的纠错码体现出来的纠错性能不同，于是能否在设计列表译码时借助这些现象来提速最小重量码字的寻找算法，从而提速ECDLP计算，是一个有潜力的研究课题。另外，如果能够提高Guruswami-Sudan的列表译码界，那么其很显然有助于ECDLP攻击的效率提升，但这已被认为是编码界的疑难问题。可见，在椭圆码，或者利用 ECDLP实例构造的椭圆码，甚至是具有某些特殊性质的椭圆码上，寻找相对于传统办法而言具有更高译码界和更有效的列表译码算法将是一个值得重点研究的问题。

最后，改进与提高现有的理论与方案只是为了列表译码在密码学领域深度的扩充，想要赢得更宽更广的发展，我们必须重视其在密码学新应用中的作用，尤其是全同态加密、混淆等近十年取得突飞猛进的领域。一个显而易见的难点是，尽管纠错码与格存在诸多的相似点，但上述这几种功能异常优秀的密码应用最初却是在一类特殊格，也即理想格上构造的。理想格在结构上更近似于循环码或者准循环码，拥有节省存储，具有环特性等一般格不具备的优点。因此，该方向的攻坚问题大概率集中在了寻找具有特殊结构的纠错码及其列表译码算法上，其中列表译码的作用主要体现在于解密算法与安全证明中。

随着研究的深入，密码学中的新问题和新研究方向会不断出现。鉴于效率的提高，列表译码理论与技术的实用性将不断增强，进而延伸到密码学的各分支中，为新密码方案与协议的设计以及疑难问题的解决提供更为夯实的工具与基础。