量子计算机有天然的并行优势，计算速度可达指数级，量子计算的典型代表是Shor算法和Grover算法^[1]。量子计算机的出现，使得电子计算机难于计算和求解的困难问题变得易于求解。这对基于数学难题的密码，构成极大威胁。例如，利用量子计算可以在较短时间内进行大整数的因子分解，可用于攻击RSA密码；利用量子计算易于求解离散对数，可对ELGamal密码和ECC密码进行攻击。美国Bell实验室提出的Grover算法和Shor算法，在量子计算机上，在多项式时间内攻破很多现有密码。尤其是Shor算法，利用量子Fourier变换具有计算加速功能这一优点，对能够规约为隐藏子群（HSP）的问题进行有效计算^[2]。量子计算机的原理是利用量子并行、相干叠加和纠缠态等量子特性进行快速计算，但在实际应用中，相干叠加和纠缠态都很脆弱，难以保持，易与外部环境相互作用，产生量子消相干。量子纠错码是克服量子消相干的有效途径之一。

一些研究者们试图从经典数学纠错码着手，利用CSS构造思想构造量子纠错码，利用量子纠错码设计新的密码体制以对抗量子计算攻击。关于抗量子密码算法，国内外学者的研究主要集中在以下5个方面^[3]：1）Merkle树签名方案，也被称为Hash函数方案；2）基于纠错码的密码方案，也被称为McEliece体制；3）基于格上困难问题的密码；4）MQ密码方案；5）研究现有安全强度高的对称密码，分析其抗量子计算能力。其中，McEliece体制是基于经典纠错码的纠错门陷设计出的密码，能较好地抗量子攻击。

关于量子编码与密码的研究报道有很多。例如，Jin^[4–6]、Xu^[7]等研究了量子纠错码，Chuang等^[8]研究了量子数字签名，Ablayev等^[9]研究了量子Hash函数，Bennett等^[10]研究了量子秘钥分配问题，Zeng^[11]研究了量子认证问题，Toyran^[12]、Okamoto^[13]、Wieschebrink^[14]等提出了量子公钥密码问题。第1个McEliece公钥体制是1978提出的^[15]，随后的多年研究表明，适当调整这种密码体制的参数后，量子计算也不能对其构成严重威胁，但这种体制的缺点是存储空间很大。1986年，Niederreiter提出了一种背包型的纠错码公钥体制，之后Li等^[16]证明了其与McEliece公钥体制的安全性等价。有关McEliece和Niederreiter公钥密码体制的具体内容详见文献[3]。2011年，曹东等^[17]利用QC-LDPC码设计二元McEliece公钥密码体制，并进行了仿真实验。

上述关于量子纠错码的研究，没有给出量子纠错码的生成算法。在设计抗量子计算攻击的公钥密码体制时，主要利用二元经典纠错码设计抗量子攻击的公钥体制。

作者先生成量子BCH码，利用量子BCH码设计量子McEliece公钥体制，且量子态包括二元和非二元情形。作者给出了3类典型的量子BCH码生成算法，第1类生成算法生成量子BCH码数目多，另外两类算法效率更高。相对于已有的一些抗量子计算加密算法，本文算法优势在于加解密时不需要经典态和量子态相互转换，提高了计算效率，同时，将量子态从二元推广到任意元。对加密算法从时间复杂性、空间复杂性、数据结构和算法模式上进行安全性分析，得到了抵抗Shor算法和Grover算法攻击的结果。利用生成的大量量子BCH码设计了抗量子计算的数字签名，给出了量子纠错码的一种应用。

1 量子BCH码的CSS构造算法

量子纠错码与经典纠错码相比在纠错方面有3点不同之处：一是，量子编码时，将单个量子比特态编成纠缠态，起冗余作用；二是，量子错误可以看成3种Pauli算子的线性组合，这3种算子对应3种量子错误，即量子比特翻转、量子相位翻转、量子比特和相位同时翻转；三是，量子纠错时，将错误对应到不同的正交Hilbert空间。下面将给出量子纠错码的定义。

1.1 量子纠错码

定义1 　一个 $q$ 元量子码 $Q$ 记为 ${\left[ {\left[ {n,k,d} \right]} \right]_q}$ ，是指Hilbert空间 ${C^{{q^n}}} = {C^q} \otimes {C^q} \otimes \cdots \otimes {C^q}$ （ $n$ 个 ${C^q}$ 的直积）的 ${q^k}$ 维子空间成为量子纠错码 $Q = {C^q} \otimes {C^q} \otimes \cdots \otimes {C^q}$ （ $k$ 个 ${C^q}$ 的直积），能够纠正至多 $t = \left\lfloor {(d - 1)/2} \right\rfloor $ 个量子错误。

一个经典线性码是有限域上线性子空间， ${C^ \bot }$ 表示Euclidean正交下码 $C$ 的对偶码， ${D^{{ \bot _H}}}$ 表示Hermitian内积下码 $D$ 的对偶码。在构造量子码时，需要用到有限域 ${F\!_q}$ 具有性质 ${C^ \bot } \subset C$ 的经典码，或有限域 ${F\!_{q^2}}$ 上具有性质 ${D^{{ \bot _H}}} \subseteq D$ 的经典码，这两类码统称 $C$ 和 $D$ 为偶包含码。关于线性码的参数关系请参考文献[18]。

1.2 量子BCH码生成算法

作者主要利用量子BCH码实现McEliece加密体制，量子纠错码的生成算法主要基于CSS构造思想^[19]。下面给出3类量子BCH码的构造方法。第1类生成算法主要指算法1和算法2，可以很全面地生成量子BCH码，由于分圆陪集选取较为复杂，所以该类算法效率不高；后两类生成算法生成的BCH码数量不多，但效率很高，其中，算法3生成的是对称的量子BCH码，算法4生成的是非对称的量子BCH码。

1.2.1 从分圆陪集角度构造量子BCH码

算法1 　分圆陪集生成有限域 ${F\!_q}$ 上的量子码

输入： $n{\text{、}}\!\!q$ 满足 $\gcd (n,q) = 1$ 。

输出：量子BCH码 $Q$ 参数 ${\left[ {\left[ {n,k,d} \right]} \right]_q}$ 。

Step1　计算分圆陪集 ${C_i}$ 。令 $m = or{d_n}(q) = \mathop {\min }\limits_{0 \le i \le n}\{ {i\left| {n\left| \right.} \right.}$ ${({q^i} - 1)},\; i > 0\}$ ，将 $i$ 按 $q$ 进制展开 $i = {i_0} + {i_1}q + \cdots + {i_{m - 2}}{q^{m - 2}} + $ $ {i_{m - 1}}{q^{m - 1}}$ ，其中， ${i_0},{i_1}, \cdots ,{i_{m - 1}} \in \left\{ {0,1, \cdots ,q - 1} \right\}$ ，存在一一对应关系 $i \leftrightarrow ({i_0},{i_1}, \cdots ,{i_{m - 1}})$ ，分圆陪集 ${C_i}$ 为 $({i_0},{i_1}, \cdots ,{i_{m - 1}})$ 全体轮换圈所对应的数 $i$ 。

Step2　任选若干个分圆陪集，计算它们的并集 $K$ ，称 $K$ 为定义集。

Step3　计算 ${K^{ - 1}} \!=\! \{ - aod n\left| {a \in K} \right.\}\!=\!\{ (n \!- \!a)od n|$ ${a \in K}\}$ 。

Step4　判断 $K \cap {K^{{\rm{ - 1}}}}\! =\! A$ ，若 $A$ 为非空集，转到Step2；若 $A$ 为空集转到Step5。

Step5　计算 $k =n- \left| K \right|$ ，设 $\delta $ 为 $K$ 中连续数的个数，输出量子码 ${\left[ {\left[ {n,n - 2k, \ge d} \right]} \right]_q}$ ，最小距离满足 $d \ge \delta + 1$ 。

算法2 　分圆陪集生成有限域 ${F\!_{q^2}}$ 上量子码

输入： $n{\text{、}}\!\!{q^2}$ 满足 $\gcd (n,q) = 1$ 。

输出：量子BCH码 $Q$ 参数 ${\left[ {\left[ {n,k,d} \right]} \right]_{{q^2}}}$ 。

Step1　计算分圆陪集 ${C_i}$ ，令 $m = or{d_n}({q^2}) = \mathop {\min }\limits_{0 \le i \le n} \{ {i\left|n\right| }$ ${({q^{2i}} - 1),i > 0}\}$ ，将 $i$ 按 ${q^2}$ 进制展开为 $ i = {i_0} + {i_1}{q^2} + \cdots +$ $ {i_{m - 2}}{q^{2(m - 2)}} + {i_{m - 1}}{q^{2(m - 1)}}$ ，其中， ${i_0},{i_1}, \cdots\!,{i_{m - 1}} \in \left\{\!{0,1, \cdots\!,{q^2} - 1} \!\right\}$ ，存在一一对应关系 $i \leftrightarrow ({i_0},{i_1}, \cdots ,{i_{m - 1}})$ ，分圆陪集 ${C_i}$ 为 $({i_0},{i_1}, \cdots ,{i_{m - 1}})$ 的全体轮换圈所对应的数。

Step2　任选若干个分圆陪集，计算其并集 $K$ ，称为定义集。

Step3　计算

${K^{ - q}} = \{ - aqod n\left| {a \in K} \right.\} =\{ (n - qa)od n\left| {a \in K} \right.\} $ 。

Step4　判断 $K \cap {K^{ - q}} = A$ ，若 $A$ 为非空集，转到Step2；若 $A$ 为空集转到Step5。

Step5　计算 $k =n- \left| K \right|$ ，设 $\delta $ 为 $K$ 中连续数的个数，则存在量子码 ${\left[ {\left[ {n,2k - n, \ge d} \right]} \right]_{q^2}}$ ，满足 $d \ge \delta + 1$ 。

证明算法正确性：算法1、算法2本质上基本是一致的，不同之处在于算法1利用CSS法构造量子BCH码时使用了有限域 ${F\!_q}$ 上的Euclidean内积；算法2使用了有限域 ${F\!_{q^2}}$ 上的Hermitian内积。下面先证明算法1中Step1计算结果能得到分圆陪集。

由定义知分圆陪集可写成 ${C_i} = \left\{ {i{q^x} } \right.od n|\left. {x \in {\textit{Z}}} \right\}$ ，若 $\forall a,b \in {C_i}$ ，则 $a = i{q^x}od n,b = i{q^y}od n$ ，不妨设 $y > x,a,b \in N = \left\{ {0,1, \cdots ,n - 1} \right\}$ ，注意到 $m = or{d_n}(q)$ ，那么， $b = a{q^{y - x}}od n$ ， $a$ 按 $q$ 进制展开有唯一表达式为 $a = {i_0} + {i_1}q + \cdots + {i_{m - 2}}{q^{m - 2}} + {i_{m - 1}}{q^{m - 1}}$ ，即存在一一对应关系 $a \leftrightarrow ({i_0},{i_1}, \cdots ,{i_{m - 1}})$ ，但 ${q^m} = 1od n$ ，所以， $aq = {i_0}q +$ $ {i_1}{q^2} + \cdots + {i_{m - 2}}{q^{m - 1}} + {i_{m - 1}}(od n)$ 存在一一对应关系 $aq \leftrightarrow ({i_{m - 1}},{i_0}, \cdots ,{i_{m - 2}})$ 。以此类推， $a{q^{y - x}}$ 与 $({i_0},{i_1}, \cdots ,{i_{m - 1}})$ 的 $\left( {y - x} \right)$ 次轮换对应，从而证明了Step1是正确的。

取生成多项式 $g(x) =\displaystyle\prod\limits_{k \in K} {(x - {\alpha ^k})} $ 构造BCH码 $C$ ，则对偶码 ${C^ \bot } \subset C \Leftrightarrow K \cap {K^{ - 1}} = \varPhi $ ^[18]，码 $C$ 的参数为 $\left[ {n,k, \ge \delta + 1} \right]$ ，利用CSS构造法很快就可求出参数为 ${\left[ {\left[ {n,2k - n, \ge d} \right]} \right]_q}$ 的量子码。证毕

举　例 　取 ${q^2} = 4$ ， $n = 5$ ， ${C_0} = \left\{ 0 \right\}$ ， ${C_1} = \left\{ {1,4} \right\},{C_2} = $ $\left\{ {2,3} \right\}$ ， $K \!=\! {C_1} \!=\! \left\{ {1,4} \right\}$ ， ${K^{ - 2}} \!=\! \left\{ { - 2 \times 1od 5, - 2 \times 4od 5} \right\} \!=$ $\left\{ {3,2} \right\}$ ，有 $K \cap {K^{ - 2}} = \varPhi $ ， $k = n-\left| K \right| =3$ ，所以， ${\left[ {\left[ {n,2k - n,}\right.}\right.} $ $\left.{\left.{\ge d} \right]} \right]_{q^2} ={\left[ {\left[ {5,2\cdot 3- 5, \ge d} \right]} \right]_{q^2}} = {\left[ {\left[ {5,1, \ge 2} \right]} \right]_{q^2}}$ 。

如果取 $K = {C_2} = \left\{ {2,3} \right\}$ ，则 ${K^{ - 2}} = \left\{ { - 2 \times 2\,od \,5,} \right.$ $\left. { - 2 \times 3\,od \,5} \right\} = \left\{ {1,4} \right\}$ ，仍有判别式 $K \cap {K^{ - 2}} = \varPhi $ ， $k =$ $ n-\left| K \right| = 3$ ，但 $K = {C_2} = \left\{ {2,3} \right\}$ 中有2个连续数2、3，则 $d \ge \delta + 1 = 3$ ，根据量子码界可知： $2d \le n - k + 2 \Rightarrow$ $ d \le 3$ ，得到 $d = 3$ ，所以存在 ${\left[ {\left[ {5,1,3} \right]} \right]_2}$ 量子码。

注意1 　根据算法1和算法2，如果定义集 $K$ 包含的数是连续的，得到的量子码被称为RS量子码；当参数 ${\left[ {\left[ {n,k,d} \right]} \right]_q}$ 满足 $2d = n - k + 2$ 时被称为MDS量子码。RS量子码和MDS量子码是两类被广泛研究的特殊量子码。

注意2 　有限域 ${F\!_q}$ 上得Euclidean内积和有限域 ${F\!_{q^2}}$ 的Hermitian内积，很多性质都是相似的，为避免啰嗦，后续只讨论有限域 ${F\!_q}$ 上Euclidean内积，对于有限域 ${F\!_{q^2}}$ ，完全有类似的生成算法可求得。

1.2.2 从特殊分圆陪集角度构造量子码

第1类构造方法中，需要搜索大量的分圆陪集，计算效率会受到影响。由文献[19]可知，如果存在 ${F\!_q}$ 上线性码 $C = {[n,k,d]_q}$ 满足 ${C^ \bot } \subseteq C$ ，则存在参数为 ${[[n,2k - n, \ge d]]_q}$ 的量子码，如果 ${C^ \bot }$ 的最小距离超过 $d$ ，则量子码的最小距离就为 $d$ ；如果存在 ${F\!_{q^2}}$ 上线性码 $D = {[n,k,d]_{{q^2}}}$ 满足 ${D^{{ \bot _H}}} \subseteq D$ ，则存在 ${[[n,2k - n, \ge d]]_{{q^2}}}$ 的量子码。下面介绍利用特殊分圆陪集构造量子纠错码。其中， $\left[xodd\right] = xod 2$ ， $\left[xeven\right] = (x - 1)od 2$ ， $\left\lceil x \right\rceil $ 为不小于 $x$ 的最小整数。

算法3 　特殊分圆陪集生成有限域 ${F\!_q}$ 上的量子码

输入： $n = {q^m} - 1$ ，取 ${\delta _{\max }} = {\rm{ }}{q^{\left\lceil {m/2} \right\rceil }} - 1 - (q - 2)\left[ {modd} \right]$ ，令 $\alpha $ 为 $n$ 次本原单位根。

输出：量子BCH码 $Q$ 参数 $[[{q^m} \!-\! 1,{q^m} \!-\! 1\! -\! 2m \left\lceil(\delta - 1)\right.\cdot $ $\left.(1 - 1/q)\right\rceil, d_Q \ge \delta ]]$ 。

Step1　设 $N = \left\{ {0,1,2, \cdots ,\left. {n - 1} \right\}} \right.$ ，任取 $\delta \le {\delta _{\max }}$ ，计算定义集 $K = {C_1} \cup {C_2} \cup \cdots \cup {C_{\delta - 1}}$ ，其中， ${C_x} = \left\{ x{q^j} \right.od n|$ $\left. {j \in {\textit{Z}}} \right\}$ 为 ${F\!_q} $ 上的分圆陪集。

Step2　选取多项式 $g(x) = \displaystyle\prod\limits_{k \in K} {(x - {\alpha ^k})} $ 和 $h(x) =$ ${\displaystyle\prod\limits_{k \in N\backslash K}}(x - {\alpha ^{ - k}})$ 作为生成多项式，生成狭义BCH码 $C$ 和 ${C^\bot } $ ，且满足 ${C^\bot } \subset C$ 。

Step3　根据 $C$ 和 ${C^ \bot } $ 利用CSS构造法构造量子BCH码 $Q$ ，最小距离 ${d_Q} \ge \delta $ 可根据需要进行设计。

算法3的证明可利用文献[20]中的定理34，这里不再赘述。类似地，还可生成 ${F\!_{q^2}}$ 上的量子码 $Q$ ，其参数为 $\left[ {\left[ {{q^{2m}} - 1, \; {q^{2m}} - 1 - 2m\left\lceil {(\delta - 1)(1 - 1/{q^2})} \right\rceil ,{d_Q} \ge \delta } \right]} \right]$ 。此时有限域 ${F\!_{q^2}}$ 的内积为Hermitian内积。算法3表明只需选取不同的 $\delta $ ，就可得到不同的定义集，生成一大批量子BCH码。

在经典BCH码中，如果生成多项式的定义集为 $K = {C_b} \cup{C_{b+1}} \cup \cdot \cdot \cdot \cup {C_{b + \delta - 2}}$ ，则最小距离 $d \ge \delta $ 。当 $n =$ $ {q^m} - 1$ 时其被称为本元BCH码，当 $b = 1$ 时被称为狭义BCH码。

1.2.3 非对称量子BCH码的构造

量子码 $Q$ 能明确其纠正比特翻转错误和相位翻转错误的能力，则被称为非对称量子码。利用CSS构造可以得到非对称量子码。设 ${C_1}$ 、 ${C_2}$ 分别是 ${F\!_q}$ 上的经典线性码，参数表达为 ${C_1} = [n,{k_1},{d_1}]$ ， ${C_2} = [n,{k_2},{d_2}]$ ，并设 ${C_1^\bot} \subseteq {C_2}$ ，从而 ${C_2^\bot} \subseteq {C_1}$ 。且参数满足不等式 ${k_1} + {k_2} - n \ge 0$ ，则存在量子码 $Q$ ，其是参数为 ${[[n,{k_1} + {k_2} - n,{{{d_{\textit{z}}}} / {{d_x}}}]]_q}$ 的非对称量子纠错码。令 $T = \left\{ {{\rm wt}({ c})|{ c} \in ({C_1}\backslash {C_2^\bot}) \cup ({C_2}\backslash {C_1^\bot})} \right\}\!{\text{，}}$ 则 ${d_x} = \min\; T\!{\text{，}}$ ${d_{\textit{z}}} = $ $\max\; T$ ，该量子码可以纠正 $\left\lfloor {({d_x} - 1)/2} \right\rfloor $ 个量子比特翻转，同时，可以纠正 $\left\lfloor {({d_{\textit{z}}} - 1)/2} \right\rfloor $ 个相位比特翻转。对于有限域 ${F\!_{{q^2}}}$ 可利用 ${D_1^{\bot _H}} \subseteq {D_2}$ 类似地构造出非对称量子码。

算法4 　有限域 ${F\!_q}$ 上的非对称量子BCH码的生成

输入： $n = {q^m} - 1$ ，取 ${\delta _{\max }} = {\rm{ }}{q^{\left\lceil {m/2} \right\rceil }} - 1 - (q - 2)\left[ {modd} \right]$ ， $n$ 次本原单位根 $\alpha $ 。

输出：量子BCH码 $Q$ 参数 $[[ {{q^m}\!-\!1,{q^m}}\!- \!1\!-\!2m\left\lceil {(\delta - 1)}\right. \cdot$ $\left.(1 - 1/q) \right\rceil ,{d_{\textit{z}}}/{d_x}]]$ 。

Step1　设 $N = \left\{ {0,1,2, \cdots ,\left. {n - 1} \right\}} \right.$ ，任取 $\delta \le {\delta _{\max }} $ 计算定义集 $K \!=\! {C_1} \cup {C_2} \cup \cdots \cup {C_{\delta - 1}}$ ，其中， ${C_x} \!=\! \left\{ {x{q^j}} \right.\,od \,n$ $|\left. {j \in {\textit{Z}}} \right\}$ 为 ${F\!_q} $ 上分圆陪集。

Step2　取多项式 $g(x) =\displaystyle\prod\limits_{k \in K} {(x - {\alpha ^k})} $ 作为生成多项式，生成狭义BCH码 ${C_1}$ 。

Step3　任取 $2\! \le \!\delta ' \!\le \!\delta $ ，计算 $K' = {C_1} \cup {C_2} \cup \cdots \cup {C_{\delta ' - 1}}$ ，由多项式 $g(x) =\displaystyle\prod\limits_{k \in K} {(x - {\alpha ^k})} $ 作为生成码 $C_2$ （也可以任意选取 ${C_1},{C_2}, \cdots ,{C_\delta }$ 中下标连续的部分分圆陪集）。

Step4　根据 ${C_1}$ 和 ${C_2}$ 利用CSS构造法可以构造量子BCH码 $Q$ 。令 $T = \left\{ {{\rm wt}(c)|c \in ({C_1}\backslash {C_2^\bot}) \cup ({C_2}\backslash {C_1^\bot})} \right\}$ ，则 ${d_x} = \min\;T\!{\text{，}}$ ${d_{\textit{z}}} = \max\;T{\text{。}}$

算法证明：从文献[20]知，Step2生成的码 $C_1$ 包含其对偶码，且维数 ${k_1} = {q^m} - 1 - m\left\lceil {(\delta - 1)(1 - 1/q)} \right\rceil $ ，而Step3生成的码 ${C_2} \supset {C_1}$ ， ${C_2}$ 的维数满足不等式 ${k_2}{\rm{ > }}{k_1}$ ，则 ${k_2}{\rm{ + }}{k_1} - n > 2{k_1} - n = {q^m} - 1 - 2m\left\lceil {(\delta - 1)(1 - 1/q)} \right\rceil > 0$ ，因此，可以得到非对称量子码。

还可以生成 ${F\!_{{{q}^2}}}$ 上的量子码 $Q$ ，其参数为 $ [[{{q^{2m}} - 1},$ ${{q^{2m}} - 1 - 2m\left\lceil {(\delta - 1)(1 - 1/{q^2})} \right\rceil ,{d_{\textit{z}}}/{d_x}}]]$ ，此时有限域 ${F\!_{{{q}^2}}}$ 的内积为Hermitian内积。利用常循环码也可以构造非对称量子纠错码，详情参见文献[21]。

2 基于量子BCH码设计量子McEliece和量子Niederreiter公钥密码体制

在解密过程中，基于量子BCH码设计的量子McEliece公钥密码体制和量子Niederreiter公钥密码体制需要使用BCH码的译码算法。主要采用BCH码的Berlekamp-Massey译码算法，简称BM译码算法。量子McEliece公钥密码体制的思想如下：

1）将量子BCH码 $Q$ ，通过隐藏得到等价的量子BCH码 $Q'$ 。

2）量子BCH码 $Q'$ 将明文消息编码成量子纠缠态。

3）加密：在已编码的量子纠缠态中，故意加入量子错误（比特翻转或相位翻转），从而得到错误污染后的量子态，即是密文。

4）解密：由 $Q'$ 的纠错功能消除量子错误，得到消息的量子态，由编码原则恢复明文。

根据第1节给出的非对称量子BCH码构造方法，经典BCH码满足 ${C_1^\bot} \subset {C_1} \subset {C_2}$ ，由CSS构造出量子码 $Q$ 。设 ${C_2}$ 的生成矩阵为 ${{ G}_2}$ ，任意选取可逆方阵 ${ U}$ 和置换矩阵 ${ P}$ ，使得 ${{ G}_2^\prime} = { U}{{ G}_2}{ P}$ ，相应地，隐藏 ${C_1^\bot} $ 、 ${C_1}$ 的生成矩阵和校验矩阵。隐藏后的生成矩阵和校验矩阵，仍记为 ${{ G}_2}$ 、 ${{ H}_2}$ 、 ${{ G}_1}$ 、 ${{ H}_1}$ 。量子码的比特翻转和相位翻转纠错能力记为 ${{{t}}_{{x}}}{\text{、}}\!\!{t_{\textit{z}}}$ 。当 ${C_1} = {C_2} = C$ 时处理方法类似。对于有限域 ${F\!_{q^2}}$ 需考虑Hermitian正交即可。设 ${F\!_q}$ 为特征为 ${{p}}$ 的有限域，则 $\forall { x} \cdot { y} \in {F\!_q^{\,n}}$ ， ${ x} \cdot { y}$ 为 Euclidean内积， ${\rm{Tr}} ({ x} \cdot { y})$ 表示内积 ${ x} \cdot { y}$ 的迹。量子态表示为 $\left| { x} \right\rangle $ ，常用的量子变换大都采用酉变换，其逆变换和原变换几乎相同。作者采用的酉变换大致为：

1）广义Hadamard门变换

$\left| { x} \right\rangle \xrightarrow{{{H^{ \otimes n}}}} \frac{1}{{\sqrt {{q^n}} }}\sum\limits_{{ y} \in F_q^n} {{{\rm e}^{\frac{{2{\text{π}} {\rm i}}}{p}{\rm{Tr}} ({ x} \cdot { y})}}} \left| { y} \right\rangle{\text{。}}$

当 ${F\!_q} = {F_2}$ 时，

$\left| { x} \right\rangle \xrightarrow{{{H^{ \otimes n}}}} \frac{1}{{\sqrt {{2^n}} }}\sum\limits_{{ y} \in F_2^n} {{{( - 1)}^{{ x} \cdot { y}}}} \left| { y} \right\rangle {\text{。}}$

2）有限域 $F_2^n$ 上的Fourier变换

$\left| { x} \right\rangle \xrightarrow{F}\frac{1}{{\sqrt {{2^n}} }}\sum\limits_{{ y}= 0}^{{2^n} - 1} {{{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{{{2^n}}}{ x} \cdot { y}}}} \left| { y} \right\rangle{\text{。}}$

3）任意函数 ${{f}}$ 的 ${U\!_f}$ 黑盒变换

$\left| { x} \right\rangle \left| { y} \right\rangle \xrightarrow{{{U\!_f}}}\left| { x} \right\rangle \left| {{ y} \oplus f({ x})} \right\rangle{\text{。}}$

2.1 密钥生成

1）给出隐藏量子码 $Q$ 及纠错能力 ${{{t}}_{{x}}}{\text{、}}\!\!{t_{\textit{z}}}$ 。

2）公钥： ${{ G}_1}{\text{、}}\!\!{{ G}_2}$ 和 ${t_{{x}}}{\text{、}}\!\!{t_{\textit{z}}}$ 。

3）私钥： ${ U}{\text{、}}\!\!{ P}$ 及相应的BM译码算法。

2.2 加密过程

1）任选明文 ${ m} \in GF({2^{{k_2}}})$ 和 ${ x} = { m}{{ G}_2}$ ，编码成量子纠缠态为：

$\left| {{ x} + {C_1}} \right\rangle = \frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {\left| {{ x} +{ y}} \right\rangle }{\text{。}}$

2）随机选择比特翻转向量和相位翻转错误 ${{ e}\!_x}{\text{、}}\!\!{{ e}_{\textit{z}}}$ ，量子Hamming重量满足：

${W_{\rm quantum}}({{ e}_x}) \le {t_x},{W_{\rm quantum}}({{ e}_{\textit{z}}}) \le {t_{\textit{z}}}{\text{。}}$

3）加密得到密文为：

$\left| {cip} \right\rangle = \frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {{{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{p}{\rm{Tr}} [({ y} +{ x}) \cdot {{ e}_{\textit{z}}}]}}} \left| {{ x} + { y} + {{ e}\!_x}} \right\rangle{\text{。}}$

2.3 解密过程

利用量子纠错码检出错误 ${{ e}\!_x}{\text{、}}\!\!{{ e}_{\textit{z}}}$ ，去掉错误得到量子态： $\left| {{ x} + {C_1}} \right\rangle = \displaystyle\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {\left| {{ x} + { y}} \right\rangle } $ ，由此恢复出明文 ${ m}$ 。为了说明量子纠错过程，有如下引理。

引　理 　设 ${F\!_q}$ 的特征为 $p$ ， $C$ 为 ${F\!_q}$ 上的线性码， ${C^ \bot }$ 为 $C$ 的对偶码， $\forall { x} \in {F\!_q^{\,n}}$ ，则 $\displaystyle\sum\limits_{{ y} \in C} {{{\rm e}^{\frac{{2{\text{π}} {\rm i}}}{p} \cdot {\rm{Tr}} ({ x} \cdot { y})}}} = \left\{ {\begin{aligned}& {|C|,\;{ x} \in {C^ \bot };}\\& {0,\;{ x} \notin {C^ \bot }}{\text{。}}\end{aligned}} \right.$

证明：线性码 $C$ 是一个加法群， ${U\!\!_p}$ 表示复数域上全体 $p$ 次单位根组成的集合。取定 ${ x} \in {F\!_q^{\,n}}$ ，定义映射：

${\chi _x}:C \to {U\!_p}$ 即 ${\chi _x}:{ y} \mapsto {{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{p} \cdot {\rm Tr}({ x} \cdot { y})}}$ ,

满足下列性质：

1） ${\chi _x}({{ y}_1} + {{ y}_2}) \!=\! {{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{p} \cdot {\rm{Tr}} ({ x} \cdot ({{ y}_1} \!+\! {{ y}_2}))}} \!=\! {{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{p}({\rm{Tr}} ({ x} \cdot {{ y}_1}) \!+\! {\rm Tr}({ x}\cdot {{ y}_2}))}}={\chi _x}({{ y}_1})\cdot$ ${\chi _x}({{ y}_2})$ ；

2） ${\chi _x}({\textbf{\textit{0}}})={{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{p}{\rm Tr}({\textbf{\textit{0}}})}} = 1$ 。

所以， ${\chi _x}$ 是码 $C$ 到 ${U\!\!_p}$ 的一个群同态，也被称为线性特征标。

当 ${ x} \notin {C^ \bot }$ 时， ${\chi _x} \ne 1$ ，那么，存在 $\bar { y} \in F\!_q^{\,n}\backslash \left\{ {\textbf{\textit{0}}} \right\}$ ， ${\chi _x}(\bar { y}) \in {U\!\!_p}$ ，满足 ${\chi _x}(\bar { y}) \ne 1, 0$ 。从而有：

$\begin{aligned}[b] & {\chi _x}(\bar { y})\sum\limits_{{ y} \in C} {{\chi _x}({ y}) = \sum\limits_{{ y} \in C} {{\chi _x}(\bar { y}){\chi _x}({ y})} }=\\ &\quad\quad \sum\limits_{{ y} \in C} {{\chi _x}({ y} + \bar { y})\underline{\underline {{ t} = { y} + \bar { y}}} }\\ & \quad\quad\sum\limits_{{ t} \in C} {{\chi _x}({ t})} = \sum\limits_{{ y} \in C} {{\chi _x}({ y})},\end{aligned}$

$({\chi _x}(\bar { y}) - 1)\displaystyle\sum\limits_{{ y} \in C} {{\chi _x}({ y}) = 0} $ ，

但 ${\chi _x}(\bar { y}) - 1 \ne 0$ ，故

$\sum\limits_{{ y} \in C} {{\chi _x}({ y}) = 0} = \sum\limits_{{ y} \in C} {{{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{p}{\rm Tr}({ x} \cdot { y})}}}{\text{。}}$

所以， $\displaystyle\sum\limits_{{ y}\in C} {{{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{p} \cdot {\rm{Tr}} ({ x} \cdot { y})}}} = \left\{ {\begin{aligned}& {|C|}, \;{{ x} \in {C^ \bot }};\\ & {0},\; {{ x} \notin {C^ \bot}}{\text{。}}\end{aligned}}\right.$

证毕

当 ${F\!_q} = {F_2}$ 时，则 $\displaystyle\sum\limits_{{ y}\in C} {{{( - 1)}^{{ x} \cdot { y}}}} = \left\{ {\begin{aligned}& {0,\;{ x} \notin {C^ \bot };}\\& {|C|,\;{ x} \in {C^ \bot }}{\text{。}}\end{aligned}} \right.$ 3类量子错误可以分别看成比特翻转和相位翻转的线性组合。设量子状态为 $\left| {{ x}+ {C_1}} \right\rangle = \displaystyle\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {\left| {{ x} +{ y}} \right\rangle } $ 。在加密过程中，选取比特翻转错误为 ${{ e}\!_x}$ ，相位翻转错误为 ${{ e}_{\textit{z}}}$ 。下面以 ${F\!_q} = {F_2}$ 为例说明解密过程。对于一般有限域，只需将 ${( - 1)^{{ x} \cdot { y}}}$ 改成 ${{\rm e}^{\frac{{2{\text{π}}{\rm i}}}{p}{\rm{Tr}} ({ x}\cdot { y})}}$ ，且使用广义Hadamard门变换，引理1的结果依然成立。于是将量子密文设为 $\displaystyle\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\displaystyle\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x}+ { y}) \cdot {{ e}_{\textit{z}}}}}} \left| {{ x} + { y} + {{ e}\!_x}} \right\rangle$ 。

纠错过程如下：

定理1 　 $\displaystyle\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x} +{ y}) \cdot {{ e}\!_x}}} |{ x} + { y} + {{ e}\!_x}}\left.\right\rangle $ 可用 ${{ H}_1}$ 纠正比特翻转。

证明：利用计算

$ \left| {{ x} + { y} + {{ e}\!_x}} \right\rangle \left| 0 \right\rangle \xrightarrow{{{U\!_f}}} \left| {{ x} + { y} + {{ e}\!_x}} \right\rangle \left| {0 + f({ x} + { y} + {{ e}\!_x})} \right\rangle {\text{。}}$

取 $f({ x} + { y} + {{ e}\!_x}) = {{ H}_1}({ x} +{ y} + {{ e}\!_x}) = {{ H}_1}{{ e}\!_x}$ ， ${{ H}_1}$ 为 ${C_1}$ 的校验矩阵，可以算出 ${{ e}\!_x}$ 。

同理，可将

$\begin{aligned}& \frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x} +{ y}) \cdot {{ e}_{\textit{z}}}}}} \left| {{ x} + { y} + {{ e}\!_x}} \right\rangle \left| 0 \right\rangle \to \\& \quad\quad\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x} + { y}) \cdot {{ e}_{\textit{z}}}}}} \left| {{ x} +{ y} + {{ e}\!_x}} \right\rangle \left| {{{ H}_1}{{ e}\!_x}} \right\rangle{\text{。}}\end{aligned}$

利用错误算子去掉 ${{ e}\!_x}$ ，得到：

$\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x} + { y}) \cdot {{ e}_{\textit{z}}}}}\left| {{ x} +{ y}} \right\rangle }{\text{。}}$

证毕

定理2 　相位翻转错误 $\displaystyle\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x} +{ y}) \cdot {{ e}_{\textit{z}}}}}\left| {{ x} + { y}} \right\rangle } $ 可以转化为比特翻转错误。

证明：应用Hadamard门作用为：

$\begin{aligned}& \frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x} + { y}) \cdot {{ e}_{\textit{z}}}}}} \left| {{ x} + { y}} \right\rangle \to \\& \quad\quad\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\frac{1}{{\sqrt {{2^n}} }}\sum\limits_{{ u} \in F_2^n} {\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x} + { y})({{ e}_{\textit{z}}} +{ v})}}} } \left| { v} \right\rangle \underline{\underline {{ u}' = { u} + {{ e}_{\textit{z}}}}} \\& \quad\quad\frac{1}{{\sqrt {\left| {{C_1}} \right|{2^n}} }}\sum\limits_{{ u}' \in F_2^n} {\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{({ x} + { y}) \cdot {{ u}'}}}} } \left| {{{ u}'} + {{ e}_{\textit{z}}}} \right\rangle =\\ & \quad\quad\frac{1}{{\sqrt {\left| {{C_1}} \right|{2^n}} }}\sum\limits_{{ u}' \in F_2^n} {(\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{{ y} \cdot {{ u}'}}}} } ){( - 1)^{{ x} \cdot {{ u}'}}}\left| {{{ u}'} + {{ e}_{\textit{z}}}} \right\rangle {\text{。}}\end{aligned}$

由引理可知，

$\begin{aligned}& \frac{1}{{\sqrt {\left| {{C_1}} \right|{2^n}} }}\sum\limits_{{ u}' \in F_2^n} {(\sum\limits_{{ y} \in {C_1}} {{{( - 1)}^{{ y} \cdot {{ u}'}}}} } ){( - 1)^{{ x} \cdot {{ u}'}}}\left| {{{ u}'} + {{ e}_{\textit{z}}}} \right\rangle =\\& \quad\quad \sqrt {\frac{{\left| {{C_1}} \right|}}{{{2^n}}}} \sum\limits_{{ u}' \in C_1^ \bot } {{{( - 1)}^{{ x} \cdot {{ u}'}}}} \left| {{{ u}'} + {{ e}_{\textit{z}}}} \right\rangle{\text{。}}\end{aligned}$

再利用 $C_1^ \bot $ 的检验矩阵 ${{ G}_1}$ 可以计算出 ${{ e}_{\textit{z}}}$ ，与定理1中类似，错误算子可以去掉 ${{ e}_{\textit{z}}}$ 。

于是得到量子态：

$\sqrt {\frac{{\left| {{C_1}} \right|}}{{{2^n}}}} \sum\limits_{{ u}' \in C_1^ \bot } {{{( - 1)}^{{ x} \cdot {{ u}'}}}} \left| {{{ u}'}} \right\rangle \underline{\underline {{ u} = { u}'}} \sqrt {\frac{{\left| {{C_1}} \right|}}{{{2^n}}}} \sum\limits_{{ u} \in C_1^ \bot } {{{( - 1)}^{{ x} \cdot { u}}}} \left| { u} \right\rangle ,$

再次应用量子Hadamard变换，上述状态变为：

$\begin{aligned}& \sqrt {\frac{{\left| {{C_1}} \right|}}{{{2^n}}}} \sum\limits_{{ u} \in C_1^ \bot } {{{( - 1)}^{{ x} \cdot { u}}}} \left| { u} \right\rangle \! \to \!\!\frac{{\sqrt {\left| {{C_1}} \right|} }}{{{2^n}}}\sum\limits_{{ v} \in F_2^n} {\sum\limits_{{ u} \in C_1^ \bot } {{{( - 1)}^{({ x} + { v}) \cdot { u}}}} \left| { v} \right\rangle }\underline{\underline {{ v}' \!\!=\! { x} \!+\! { v}}}\\& \quad\quad\frac{{\sqrt {\left| {{C_1}} \right|} }}{{{2^n}}}\sum\limits_{{ v}' \in F_2^n} {\sum\limits_{{ u} \in C_1^ \bot } {{{( - 1)}^{{ v}' \cdot { u}}}} \left| {{ v}' + { x}} \right\rangle}{\text{。}} \end{aligned}$

再根据引理可知，

$\begin{aligned}& \frac{{\sqrt {\left| {{C_1}} \right|} }}{{{2^n}}}\sum\limits_{{ v}' \in F_2^n} {\sum\limits_{{ u} \in C_1^ \bot } {{{( - 1)}^{{ v}' \cdot { u}}}} \left| {{ v}' +{ x}} \right\rangle } = \\& \quad\quad\frac{{\sqrt {\left| {{C_1}} \right|} }}{{{2^n}}}\left| {C_1^ \bot } \right|\sum\limits_{{ v}' \in {C_1}} {\left| {{ v}' + { x}} \right\rangle } = \frac{{\sqrt {\left| {{C_1}} \right|} }}{{{2^n}}}\frac{{{2^n}}}{{\left| {{C_1}} \right|}}\sum\limits_{{ v}' \in {C_1}} {\left| {{ v}' + { x}} \right\rangle }=\\ & \quad\quad \frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ v}' \in {C_1}} {\left| {{ v}' + { x}} \right\rangle } = \frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {\left| {{ x} + { y}} \right\rangle }{\text{。}}\end{aligned}$

这就是初始量子态 $\left| {{ x} + {C_1}} \right\rangle = \displaystyle\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {\left| {{ x} + { y}} \right\rangle } $ ，从而得到 ${ x}$ 可以恢复消息 ${ m}$ 。如果 ${F\!_q} \ne {F_2}$ ，将得到 $\left| { - { x}+ {C_1}} \right\rangle =\displaystyle\frac{1}{{\sqrt {\left| {{C_1}} \right|} }}\sum\limits_{{ y} \in {C_1}} {\left| { - { x} + { y}} \right\rangle } $ ，依然可以恢复消息 ${ m}$ 。

证毕

基于量子BCH码的量子Niederreiter公钥密码体制，给出如下算法：

算法5 　基于量子BCH码的量子Niederreiter公钥密码体制

1）给定量子BCH码 $Q$ ，隐藏得到等价的量子BCH码 $Q'$ 。

2）将明文消息对应到量子错误。

3）公钥：量子BCH码 $Q'$ 校验矩阵 ${{ H}^{\rm puk}}{\text{、}}\!\!\!{t_x}/{t_{\textit{z}}}$ 。

4）私钥：BM译码算法和对应伴随式译码算法，隐藏变换。

5）加密：将量子错误算子作用在一个由量子BCH码 $Q'$ 编码的纠缠态上。

6）解密：利用 $Q'$ 的纠错功，检测出量子错误，恢复得到明文消息。

此算法证明过程与量子McEliece公钥密码体制完全相似，在此省略。

3 安全性分析

文献[16]证明了经典Niederreiter公钥密码体制的安全性等价于经典McEliece公钥体制，在量子状态下，可能会有很多变化。文献[22]中引进了数据复杂性分析量子计算的安全性。下面从计算复杂度和数据复杂度的角度重点分析量子BCH码的McEliece公钥体制的安全性。

1）首先，未知其译码算法，利用接收向量直接译码，这是一个NPC问题。这说明无法从密文猜测译码算法，进而，猜测错误为 ${{ e}\!_x}{\text{、}}\!\!\!{{ e}_{\textit{z}}}$ 。且加密过程需要选择量子错误 ${{ e}\!_x}{\text{、}}\!\!\!{{ e}_{\textit{z}}}$ ，量子Hamming重量满足 $ {W_{{\rm{quantum}}}}({{ e}\!_x}) \le$ $ {t_x},{W_{{\rm{quantum}}}}({{ e}_{\textit{z}}}) \le {t_x}$ ，两类错误组合满足下列组合公式：

$\left( {\begin{aligned} n \\ {{t_x}} \end{aligned}} \right)\left( {\begin{aligned} n \\ {{t_{\textit{z}}}} \end{aligned}} \right) \ge \left( {\begin{aligned} & \quad\! n \\ & {{t_x} + {t_{\textit{z}}}} \end{aligned}} \right) = \left( {\begin{aligned}& n \\ & \,t \end{aligned}} \right),$

一般地， $t$ 比较小，所以 $\left( {\begin{aligned}& n\\& \,t\end{aligned}} \right) \approx O\left( {n!} \right)$ ， $\mathop {\lim }\limits_{n \to \infty } \displaystyle\frac{{n!}}{{{2^n}}} = \infty $ ，说明错误 ${{ e}\!_x}{\text{、}}\!\!\!{{ e}_{\textit{z}}}$ 的数据复杂度也很大。

2）在经典情形下，参数相同时，BCH码数目远没有Goppa多，作者利用的是量子BCH码，有2个优点：① 一个量子BCH码由两个具有偶包含的经典BCH组成，使得量子BCH码数目成组合增加；② 由于量子BCH码在应用前被隐藏，如果穷举出隐藏变换，需要知道可逆矩阵 ${ U}$ 和置换矩阵 ${ P}$ ， ${F\!_q}$ 上 $k$ 阶可逆矩阵数目为 $ ({q^k} - 1)({q^k} - q)({q^k} - {q^2}) \cdots ({q^k} - {q^{k - 1}})= {q^{{k^2}}}\displaystyle\prod\limits_{i = 1}^k {(1 - {q^{ - i}})} > $ ${q^{k(k - 1)}}$ 。而 $n$ 阶置换矩阵 ${ P}$ 的数目大约为 $n!$ ，还可以将置换矩阵每行为1的元素换成 ${F\!_q}$ 中的非零元素，即具有不改变码字Hamming重量的特性，这样符合条件的置换矩阵数目为 $n!{(q - 1)^n}$ 。采用CSS构造量子BCH码时，要求 ${k_1} + {k_2} > n \Rightarrow k > \displaystyle\frac{n}{2}$ ，搜索隐藏变换计算复杂度为 $O({\!(\sqrt[4]{q})^{{n^2}}}{(\!q \!-\! 1\!)^n}n!)$ ，当 $q\!\! >\!\! {2^4}$ 时， $\mathop {\lim }\limits_{n \to \infty } \displaystyle\frac{({\sqrt[4]{q})^{{n^2}}}{(q \!-\! 1)^n}n!}{2^n}= \infty $ 。

3）利用矩阵分解的方法，从量子BCH码的隐藏中得到量子码的生成矩阵，涉及到矩阵分解和矩阵乘法，是非交换群中的运算，即量子算法所不擅长的。

4）文献[17]利用数值仿真分析了量子McEliece体制有很高的计算复杂度，可以抵抗Grove量子搜索计算。文献[23]分析了McEliece体制可以抵抗量子Fourier采样攻击。

基于量子BCH码的McEliece体制存在存储空间大的弱点。除了上述安全分析外，还需考虑空间复杂度。当没有参与运算时，认为空间复杂度为 $O({\rm{1}})$ 。具体分析如下：

1）为了得到量子BCH码，需要存储线性码 ${C_1} \subset {C_2}$ ，及其对偶码 $C_1^ \bot {\text{、}}\!\!\!C_2^ \bot $ 。需要存储生成矩阵和校验矩阵，并进行相应的运算，故空间复杂度为 $O(n)$ 。

2）存储量子态 $|{ x} + {C_1} \ge \displaystyle\sum\limits_{{ y} \in {C_1}} {|{ x} + { y} \left. \right\rangle} $ ，采用 ${U\!_f}$ 及Hadamard门变换，存储空间为 $O({q^{{k_1}}})$ 。

3）存在 $C_1^ \bot {\text{、}}\!\!\!{C_2}$ 的效验矩阵 ${{ H}_1}{\text{、}}\!\!\!{{ H}_2}$ ，矩阵乘法运算存储复杂度为 $O({n^3})$ 。对 $\sqrt {\displaystyle\frac{{\left| {{C_1}} \right|}}{{{2^n}}}} \displaystyle\sum\limits_{{ u} \in C_1^ \bot } {{{( - 1)}^{{ x} \cdot { u}}}} \left| { u} \right\rangle $ 做量子Hadamard门变换，存储空间为 $O({q^{n - {k_1}}})$ 。

存储空间没有顺序，最大空间复杂度为 $O({q^{n - {k_1}}}) \!\!\approx\!\! O({q^{n/2}})\left( {{k_1}\!\!+\! {k_2}\! > \!n} \right)$ ，但 $q \!=\! {p^m} \!\!\Rightarrow\!\! O({q^{n/2}})\! \approx\! O({p^{nm/2}}),$ $\mathop {\lim }\limits_{n \to \infty } \displaystyle\frac{{{p^{nm/2}}}}{{{2^n}}} = \infty (m > 2)$ 。

4）经典BCH的译码算法中，较通用的译码算法为BM算法，需要存储大量的伴随式，伴随式个数为 $\left( {\begin{aligned} & n\\ & \,t \end{aligned}} \right) \approx n!(t \ll n)$ 空间复杂度为 $O(n!)$ 。

5）量子纠错实质上是先经典码纠错，再转换成量子态，需要很大中间转换存储空间，空间复杂度 $O({{q}^{{k_2} - {k_1}}}n!) > O(n!)$ 。

从空间复杂性分析的2）～5）知，作者提出的密码算法空间复杂性和时间复杂性都很大，进而数据复杂性也很大，具有很好的抗Shor算法和Grover算法攻击能力。

4 利用一类量子BCH构造时的偶包含码设计抗量子计算数字签名

文献[24]提出了CFS数字签名，作者在构造量子BCH码时，需要用到具有偶包含（偶码被包含在码内）特性的经典码。这种经典码可用于设计数字签名，类似CFS方案而具有抗量子攻击能力。

4.1 预备工作

设Alice选择量子BCH码 ${Q_{\rm A}}$ 由一对偶包含码 ${D^ \bot } \subset D$ 通过CSS构成，Bob选择量子BCH码 ${Q_{\rm B}}$ 是一对偶包含码 ${C^ \bot } \subset C$ 通过CSS构成的。取 ${{ G}_{\rm A}}$ 为码 $D$ 的生成矩阵， ${{ G}_{\rm B}}$ 为码 $C$ 的生成矩阵， ${{ H}_{\rm A}}$ 为 $D$ 的校验矩阵， ${{ H}_{\rm B}}$ 为 $C$ 的校验矩阵， ${\overline { G} _{\rm A}}$ 为 ${{ G}_{\rm A}}$ 的右逆 ${{ G}_{\rm A}}{\overline { G} _{\rm A}}={{ I}_K}$ 。设 ${{ P}_{\rm A}}{\text{、}}\!\!\!{{ P}_{\rm B}}$ 为置换矩阵， ${ U}$ 为任意可逆矩阵，则 ${{ G}'_{\rm A}}=$ ${ P}_{\rm A}^{ - 1} {{\overline{ G}_{\rm A}}} $ ， ${ H}{'_{\rm B}} ={ U}{{ H}_{\rm B}}{{ P}_{\rm B}}{\text{。}}$ ${{t}}$ 为码 $C$ 的最大纠错能力。

公钥： ${{ G}'_{\rm A}}$ 、 ${{ G}_{\rm B}}$ 、 ${ H}'_{\rm B}$ 、 $t$ 存入PKDB中，公开的Hash函数 ${{{h}}_1}{\text{、}}\!\!\!{h_2}$ 。

私钥：Alice的私钥 ${{ H}_{\rm A}}{\text{、}}\!\!\!{{ P}_{\rm A}}{\text{、}}\!\!\!{{ G}_{\rm A}}{\text{、}}\!\!\!{\overline { G} _{\rm A}}$ 及Bob的私钥 ${{ H}_{\rm B}}{\text{、}}\!\!\!{{ P}_{\rm B}}{\text{、}}\!\!\!{ U}$ 。

4.2 签名过程（设 ${ M}$ 为签名信息）

1）Alice随机选取一个汉明权重 ${W_{\rm H}}({ e}) \le t$ 的 $n$ 维向量 ${ e}$ ，在PKDB中查找到 ${{ H}'_{\rm B}}$ 。计算 ${ e}{({{ H}'_{\rm B}})^{\rm T}} = {{ S}_{\rm A}}$ ，相当于计算 ${ e}$ 的伴随式， ${{ S}_{\rm A}}$ 为 $(n - k)$ 维向量， ${{ H}'_{\rm B}}$ 可看成 $C$ 的对偶码 ${C^ \bot }$ 的生成矩阵。 ${{ R}_{\rm A}} = {{ S}\!_{\rm A}}{ H}{'_{\rm B}}$ 看成 ${C^ \bot }$ 中编码得到的码字。

2）Alice对 ${ M}$ 进行如下处理：

${ J} = sig({ M}) = \{ { e}+ [({h_1}({ M})\parallel {h_2}({ e})) - { e}{\overline { G} _{\rm A}}]{{ G}_{\rm A}}\} {{ P}_{\rm A}},$

Alice将 $({ M},{ J},{{ R}_{\rm A}})$ 当成签名消息发给Bob。

4.3 验证签名过程

1）Bob收到 $({ M},{ J},{{ R}_{\rm A}})$ 后，利用 ${{ R}_{\rm A}} = {{ S}_{\rm A}}{ H}{'_{\rm B}}$ 是 ${C^ \bot }$ 中码字，因为 ${C^ \bot }$ 的最小距离比 $C$ 大，由 ${C^ \bot }$ 的译码算法得到 ${{ S}_{\rm A}}$ ， ${{ S}_{\rm A}}{({{ U}^{ - 1}})^{\rm{T}} } \!\!=\!\! { e}{({ H}{'_{\rm B}})^{\rm{T}} }{({{ U}^{ - 1}})^{\rm{T}} } \!\!=\!\! { e}{({ P}_{\rm B})^{\rm{T}} }{{ H}_{\rm B}^{\rm T}}$ 且 ${{ W}_{\rm{H}} }({ e}{({{ P}_{\rm B}})^{\rm T}})\!\le$ $ t$ ，利用 $C$ 进行译码得差错向量 ${ e}{({ P}_{\rm B})^{\rm T}}$ ，Bob由私钥 ${{ P}_{\rm B}}$ 得到 ${ e}$ 。

2）Bob计算

$\begin{aligned}{{ S}_1}= & { J}{ G}{'_{\rm A}}=\{ [({h_1}({ M})\parallel {h_2}({ e}) -{ e}{\overline { G}_{\rm A}}]{{ G}_{\rm A}}\}{{ P}_{\rm A}}{ G}{'_{\rm A}}=\\& \{{ e} + [{h_1}({ M})\parallel {h_2}({ e}) - { e}{\overline { G}_{\rm A}}]{{ G}_{\rm A}}\} {{ P}_{\rm A}}{ P}_{\rm A}^{ - 1}{\overline { G}_{\rm A}}=\\& { e}{\overline { G}_{\rm A}} + [{h_1}({ M})\parallel {h_2}({ e}) - { e}{\overline { G}_{\rm A}}]{{ G}_A}{\overline { G} _A}=\\& { e}{\overline { G}_{\rm A}} + {h_1}({ M})\parallel {h_2}({ e}) - { e}{\overline { G}_{\rm A}}=\\& \quad \quad \quad {h_1}({ M})\parallel {h_2}({ e}){\text{。}}\end{aligned}$

3）Bob在1）中得到 ${ e}$ ，从签名中得到 ${ M}$ ，计算 ${{ S}\!_2} = {h_1}({ M})\parallel {h_2}({ e})$ 。

4）判断：若 ${{ S}\!_1} = {{ S}\!_2}$ ，则签名有效；否则，签名无效。

注意3 　由于篇幅过长，本签名协议的安全性分析与文献[25]类似，只不过本签名涉及的纠错码都是量子BCH码；另外，在本签名中用到两个hash函数 ${h_1}{\text{、}}\!\!\!{h_2}$ ，设 ${h_1}({ M})$ 的取值定长为 $r$ ， ${h_2}({ e})$ 取值长为 $n - r$ ， $({h_1}({ M})\parallel {h_2}({ e}))$ 正好看成一个长为 $n$ 的向量。

5 结　论

矩阵乘法运算没有交换性，不能规约到HSP问题（hidden subgroup problem）。量子Fourier 变换不擅长处理该类问题^[2]，具有良好的抗量子计算攻击。但是，量子McEliece和Niederreiter公钥密码体制也存在存储量大，效率低的弱点。作者利用量子BCH码易于编码成量子纠缠态、纠错能力可设计、译码算法多（如Peterson-Gorenstein-Zierler译码算法、Berlekamp-Massey译码算法、Su Giyama译码算法等）等优点设计了基于量子BCH码的McEliece和Niederreiter公钥密码算法，重点研究量子BCH码的量子MCEliece公钥体制。在此过程中，作者先给出了3类典型的量子BCH码生成算法，其中，算法1和算法2是第1类，算法3是第2类对称量子BCH码生成算法，算法4是第3类非对称量子BCH码生成算法。然后，利用量子BCH码设计量子McEliece公钥密码体制和量子Niederreiter公钥密码体制，并分析了安全性。本文方法完全可以推广到任意有限域上的量子BCH码的MCEliece公钥体制。

作者所提出的量子McEliece和Niederreiter公钥密码体制，在纠错过程中，仍是经典码的纠错方式，应进一步研究更方便的 $q$ 元量子码的纠错方式，结合量子力学，从物理纠错方面加以研究；需要对量子McEliece体制进行更完善的安全分析，需要借鉴已有的安全分析方法，给出更加充分的安全分析；另外，量子McEliece体制和量子Niederreiter体制的安全性证明和可应用性等方面有待进一步研究。