由于量子计算对经典公钥密码体制的威胁，基于格等困难问题的后量子公钥体制和基于量子物理特性的公钥体制受到广泛关注.量子公钥加密方案简单归为2类：明文为未知状态的量子比特，或者明文为经典比特.基于量子物理特性构造公钥密码体制的思想由Gottesman和Chuang^[1]于2001年首次提出. 2005年，Gottesman^[2]提出一个对量子态的公钥加密方案.同年，Kawachi等^[3]基于全翻转置换下量子态的不可区分性(QSCD_ff, computational distinguishability of two quantum states generated via fully flipped permutations)问题提出首个对经典比特的加密方案，随后，他们将上述比特方案推广到一个基于全翻转循环置换下量子态的不可区分性(QSCD_cyc, computational distinguishability of two quantum states generated via cyclic permutations)问题的多比特加密方案^[4]，其中公钥的长度随加密的明文长度呈线性增长. 2008年，Nikolopoulos^[5]基于单量子比特旋转操作提出一个高效的方案，一年后，Nikolopoulos等^[6]提出该方案的前向搜索攻击(FSA, forward search attack)，并以牺牲效率为代价提出一个改进方案. 2012年，Seyfarth等^[7]对改进方案给出一个新的攻击分析，但是攻击效果并不如前向搜索攻击. 2014年，Zheng等^[8]也提出一个改进方案，该方案有解密错误，但是其效率较文献[6]中的方案有所提高.同年，Wu等^[9]提出一个基于量子搜索算法的多比特公钥加密方案(事实上，该消息的每个比特的加密都是相互独立). 2015年，Luo等^[10]基于量子完善加密提出一个量子比特方案；2018年，Wu等^[11]基于Bell态也提出一个比特加密方案.目前的量子公钥加密方案多是单比特的量子公钥加密，只有Kawachi等^[4]将QSCD_ff问题进行推广，构造了一个多比特的加密方案.笔者首先基于Nikolopoulos^[5]在2008年提出的单比特旋转陷门函数给出一个多比特的量子公钥加密方案，从已知的惟公钥攻击、惟密文攻击(前向搜索攻击)和选择密文攻击等方面对其进行安全性评估；然后，从公钥使用量、密文扩展方面与Kawachi等^[4]提出的多比特方案的效率进行对比分析，可以看出，在公钥长度方面具有明显优势.此外，笔者提出的构造方式有望推广到其他单比特的方案，向多比特方案扩展.

1 Nikolopoulos^[5]的单比特公钥加密方案

首先回顾一下Nikolopoulos在2008年提出的基于旋转变换的单比特加密方案.令{|0_z〉, |1_z〉}是Hilbert空间的一组正交基.一个在x－z平面上的量子比特可记为|φ(θ)〉=cos$\frac{\theta }{2} $|0_z〉+sin$ \frac{\theta }{2}$|1_z〉, θ∈[0, 2π).

定义一个绕轴y旋转的酉变换R_θ(s)=e^－isθγ/2，其中γ=i(|1_z〉〈0_z|－|0_z〉〈1_z|), s为整数，θ取值同上.显然，该酉变换满足交换律，即R_θ1(s₁)R_θ2(s₂)=R_θ2(s₂)R_θ1(s₁).

1.1 密钥生成

1) 生成一个安全参数n，令θ_n=$ \frac{\mathtt{π }}{{{2}^{n}}}$；

2) 选择一个n bit长的随机整数s；

3) 制备一个量子比特|0_z〉，并对该量子比特作酉变换R_θn(s)，则其状态变为

$ | \varphi ( s \theta _ { n } ) \rangle = \operatorname { cos } \frac { s \theta _ { n } } { 2 } | 0 _ { z } \rangle + \operatorname { sin } \frac { s \theta _ { n } } { 2 } | 1 _ { z } \rangle $

(1)

4) 重复步骤1)和2)(至多重复制备N_c次).

Alice的公钥是量子比特|φ(sθ_n)〉(最多N_c份)；她的私钥是(n, s).

1.2 加密过程

对于一个明文比特p∈{0, 1}，计算密文状态|c〉=R_π(p)|φ(sθ_n)〉.

1.3 解密过程

对于收到的量子比特|c〉，首先计算|p〉=R_θn(－s)|c〉，然后对其测量，则可以1的概率恢复明文p.

Nikolopoulos^[5]提出基于Swap Test电路的前向安全搜索攻击，利用公钥的副本和密文量子态比较，从而以3/4的正确概率得到明文. 2009年，Nikolopoulos^[6]又提出一种Symmetric Test电路，将攻击成功的概率提高到q=(N－1)/N，N为攻击者可以获得的公钥副本个数.为此，他们提出一个改进方案.然而，为了使攻击者的优势ε可忽略，加密1 bit明文，密文扩展为O(N|lbε+1|)量子比特.上面描述的是Nikolopoulos在2008年提出的基础加解密方案.为了方便下面多比特加密方案的描述，上述加密过程简记为$\mathbb{E} $(|φ(sθ_n)〉, p)，解密过程简记为$\mathbb{D} $(s, n，|c〉).

2 多比特公钥加密方案

方案同样分为密钥生成、加密和解密3个部分.长消息被切割成固定长度的分块分别进行加密.下面的方案中每块明文加密时可以使用一个公钥副本(N_d=m+l+n′)，现实应用中也可以规定每个明文块加密使用某个公钥比特的N_d个副本.

2.1 密钥生成

1) 生成一个安全参数n，令θ_n= $ \frac{\mathtt{π }}{{{2}^{n}}}$；

2) 选择一个随机数向量S=(s₁, s₂, …, s_Nd)，其中每个分量s_j(1≤j≤N_d)都是两两独立的n bit长的随机整数；

3) 制备N_d个量子比特|0_z〉^⊗N_d，并对第j个量子比特实施酉操作R_θn(s_j)，则其状态变化为

$ | \varphi ( s _ { j } \theta _ { n } ) \rangle = \operatorname { cos } \frac { s _ { j } \theta _ { n } } { 2 } | 0 _ { z } \rangle + \operatorname { sin } \frac { s _ { j } \theta _ { n } } { 2 } | 1 _ { z } \rangle $

(2)

4) 重复步骤2)和3)(至多重复制备N_c次).

Alice的每份公钥是N_d个量子比特串|φ_S(θ_n)〉= ⊗_j=1^N_d|φ(s_jθ_n)〉，共制备N_c份；其私钥为(n, S).

令H、G和W分别是输出为m+l、n′和l bit的Hash函数.

2.2 加密过程

将明文切割成m bit长的块分别进行加密，当不足m bit时，填充到m bit(填充一个结束位1和足够多的0)；每个明文块M分别执行下述步骤进行加密：

1) 选择一个n′比特的随机数r；

2) 计算α=W(M‖r)；

3) 计算2个中间值t₁=H(r)⊕(M‖α)和t₂=G(t₁)⊕r；

4) 使用第1节中的加密算法逐比特加密比特串T=t₁‖t₂得到密文量子比特串；

$ \left| C \right\rangle =\otimes _{j=1}^{m+n'+l}\left| {{c}_{j}} \right\rangle =\otimes _{j=1}^{m+n'+l}\left| \mathbb{E}\left( \varphi \left( {{s}_{j}}{{\theta }_{n}} \right), {{T}_{j}} \right) \right\rangle $

(3)

2.3 解密过程

1) 使用第1节中的解密算法从密文量子态|C〉=⊗_j=1^m+n′+l|c_j〉中逐一恢复出中间比特串T′=T′₁T′₂… T′_m+n′+l，其中T′_j=$\mathbb{D}\ $(s_j, n, |c_j〉)，j=1, 2, …, m+n′+l；

2) 将T′分成两份，T′的前m+l bit记为t′₁，后n′ bit记为t′₂；

3) 顺序计算r′=G(t′₁)⊕t′₂和T″=H(r′)⊕t′₁;

4) 取T″的前m bit记为M′，后l bit记为α′；

5) 计算W(M′‖r′)并与α′比较，若相等，则输出M′；否则程序终止.

当所有的密文块顺利执行完上述解密操作后，解密程序停止.

3 安全性分析 3.1 私钥安全性

Alice的每份公钥是N_d长的量子比特串|φ_S(θ_n)〉=⊗_j=1^N_d|φ(s_jθ_n)〉, 共制备N_c份；其私钥是(n, S).简单来说，lbn表示每个量子公钥比特包含的信息比特数(经典).根据Holevo定理^[12]可知，每份公钥长度N_d和公钥的总份数N_c满足下列条件：

$ \text{lb}\left( {{n}_{1}}-{{n}_{2}} \right)+{{N}_{d}}\left( \frac{{{n}_{1}}+{{n}_{2}}}{2} \right)\ge {{N}_{d}}{{N}_{c}} $

(4)

其中n∈[n₁, n₂]，n₁、n₂为大整数.则攻击者Eve不可能从他获取的N(N≤N_c)份公钥副本中得到Alice的私钥信息.

3.2 前向搜索攻击

假设攻击者可以在信道上截获密文，并进行前向搜索攻击.下面以密文仅为1块为例，分情况讨论攻击者成功的概率.

情况1   假设攻击者可以利用Symmetric Test电路，在解密过程的第1步完全正确地恢复T′的所有比特，那么攻击者可完全正确恢复明文块M.已知Symmetric Test电路正确恢复每个经典比特的概率为q，那么此时攻击成功的概率为Pr₁=q^m+n′+l.

由文献[6]可知，对于1-N比较问题，当2个粒子不相等时仍然输出0的概率(错误概率)为$ \frac{1+N{{\lambda }^{2}}}{N+1}$，其中N为攻击者可以获得的公钥副本份数，λ为被比较的2个量子态的内积模(此时λ=0)；而当2个粒子相等时，λ=1，Symmetric Test电路以1的概率输出0(正确概率)，所以

$ \begin{align} & q\text{= Pr}\left[ \text{output = 0 }\!\!|\!\!\text{ equal} \right]\text{ }\!\!\cdot\!\!\text{ Pr}\left[ \text{equal} \right]\text{ +} \\ & \text{Pr}\left[ \text{output = 1 }\!\!|\!\!\text{ unequal} \right]\text{ }\!\!\cdot\!\!\text{ Pr}\left[ \text{unequal} \right]\text{ =} \\ & 1\cdot \frac{1}{2}+\left( 1-\frac{1}{N+1} \right)\cdot \frac{1}{2}=\frac{2N+1}{2\left( N+1 \right)} \\ \end{align} $

(5)

情况2  假设攻击者利用Symmetric Test电路，在解密过程的第1步恢复出的T′有错误，那么攻击者成功的概率为Pr₂= $ \frac{1}{{{2}^{m}}}\left( 1-{{q}^{m+n'+l}} \right)$.

假设攻击者利用Symmetric Test电路恢复出的t′₁有a bit正确(条件成立的概率为q^a(1－q)^m+l－a，t′₂有b bit正确(条件成立的概率为q^b(1－q)^n′－b)，那么攻击者可以在步骤2)~5)恢复正确明文块的概率为1/2^m，换句话说，将H和G看作是随机函数，那么，攻击者使用错误的t′₁(或者t′₂)计算出的T″=H(G(t′₁)⊕ t′₂)⊕t′₁的前m个比特正确的概率为1/2^m.因此,

$ \begin{array}{l} \begin{array}{*{20}{l}} { \text{Pr}_2 = [\sum\limits_{a = 1}^{m + l - 1} {{q^a}} {{(1 - q)}^{m + l - a}}\sum\limits_{b = 0}^{{n^\prime }} {{q^b}} {{(1 - q)}^{{n^\prime } - b}} \cdot \frac{1}{{{2^m}}}] + }\\ {[{q^{m + l}}\sum\limits_{b = 0}^{{n^\prime } - 1} {{q^b}} {{(1 - q)}^{{n^\prime } - b}} \cdot \frac{1}{{{2^m}}}] = } \end{array}\\ \begin{array}{*{20}{l}} {\frac{1}{{{2^m}}}[\sum\limits_{a = 0}^{m + l} {{q^a}} {{(1 - q)}^{m + l - a}}\sum\limits_{b = 0}^{{n^\prime }} {{q^b}} {{(1 - q)}^{{n^\prime } - b}}}\\ {{q^{m + l}}{q^{{n^\prime }}}] = \frac{1}{{{2^m}}}(1 - {q^{m + {n^\prime } + l}})} \end{array} \end{array} $

(6)

由上述2种情况可知，攻击者成功恢复1块明文的概率为

$ \text{Pr} = \text{Pr}{ _1} + \text{Pr}{ _2} = \frac{1}{{{2^m}}} + {q^{m + l + {n^\prime }}} - \frac{1}{{{2^m}}}{q^{m + l + n^\prime}} $

(7)

特别地，当明文长度为1 bit时，该方案中攻击者的优势为

$ \begin{array}{*{20}{c}} {A = \text{Pr} - \frac{1}{2} = }\\ {(\frac{1}{2} + {q^{1 + l + {n^\prime }}} - \frac{1}{2}{q^{1 + l + {n^\prime }}}) - \frac{1}{2} = \frac{{{q^{1 + l + {n^\prime }}}}}{2}} \end{array} $

(8)

与Nikolopoulos等^[6]提出的方案类似，若要上述优势可忽略，即${A = \frac{{{q^{1 + l + {n^\prime }}}}}{2} < \varepsilon } $，那么$l + n' \ge \left| {\frac{{1 + {\rm{lb}}\varepsilon }}{{{\rm{lb}}q}}} \right| $.

在式(5)中，当N较大，即攻击者获得较多公钥副本，若要使攻击者优势可忽略，则l+n′非常大，意味着加密1 bit明文时，密文扩展非常大.假设N_d≤N_c，那么加密1块消息可以使用公钥φ(s_jθ_n)的N_d个副本，若[N_c/N_d]=N+1较小，则密文扩展较低.

3.3 选择密文攻击

在上述前向搜索攻击中，假设攻击者只能截获到密文，事实上，对于攻击者还可能对截获到的密文C^*进行伪装C，将伪装后的密文发送给解密预示请求解密，然后根据解密预示返回的明文M(伪装的密文C所对应的明文)，计算获取截获到密文C^*所对应明文M^*，称之为选择密文攻击.

对于文献[5-6]中提出的方案，攻击者只需要对截获到密文的每个量子状态进行旋转操作R_π(u_j), u_j∈{0, 1}，若共有奇数个u_j取值为1，则令M^*的值与解密预示返回值M相反；否则令M^*的值等于解密预示返回值M.

然而，上述多比特方案中，攻击者很难成功实施选择密文攻击，因为有如下2种情况.

情况1  如果攻击者修改了密文C^*(此处的修改特指对密文量子态执行R_θ(u_j)操作，其中u_j=1, 1≤j≤m+l+n′, 0 < θ < π.首先在解密预示进行第1步操作时，若某个u_j=1，将以平均1/2的概率使得T第j bit翻转.

首先，以T第j bit由0翻转为1为例，则表示在该比特测量前状态由|0_z〉被攻击者篡改成了cos $\frac{\theta }{2} $|0_z〉+sin $ \frac{\theta }{2}$|1_z〉，此时进行测量得到|1_z〉的概率为sin²(θ/2)，因为0 < θ < π，故平均概率为$ \frac{1}{\mathtt{π} }\int_0^\mathtt{π} {{{\sin }^2}} \left( {\theta /2} \right){\rm{d}}\theta = 1/2$.

其次，经过第2)~4)步解密操作后，恢复出的M、r和α满足W(M‖r)与α相等的概率为1/2^l.如果l足够大，则第5)步解密预示以很大的概率检测出密文被篡改，那么解密预示直接停止，攻击者无法拿到M.

另一方面，即使篡改没有被检测到，攻击者很难获得T(未知)经过H、G的扩散和混淆作用后生成的M与目标明文M^*的关系，故攻击者无法从解密预示返回的明文M获得目标明文M^*的信息，只能随机猜测M^*.

情况2  如果攻击者修改了密文C^*(此处的修改特指R_π(u_j)操作，其中u_j=1, 1≤j≤m+l+n′)，那么，解密预示执行完解密第1)步解密操作后，比特串T第j bit以1的概率发生翻转.同理，经过第2)至4)步解密操作后，恢复出的M、r、α满足W(M‖ r)与α相等的概率为1/2^l.如果l足够大，则第5)步解密预示以很大的概率检测出密文被篡改，那么解密预示直接停止，攻击者无法拿到M.同样，即使篡改没有被检测到，T(未知)经过H、G的扩散和混淆作用后生成的M与目标明文M^*的关系攻击者很难获得，故攻击者无法从解密预示返回的明文M获得目标明文M^*的信息，只能随机猜测M^*.

综上所述，攻击者试图通过上述选择密文攻击恢复明文的复杂度小于直接猜测M^*的概率.

注意，上述分析中没有考虑下列情况：如果攻击者修改了密文C^*(此处的修改特指对密文量子态执行R_θ(u_j)操作(u_j=1, 1≤j≤m+l+n′, 0 < θ < π)，则在解密预示进行第1步操作时，若某个u_j=1，将以平均1/2的概率使得T第j bit保持不变，此时，攻击者将获得和目标明文M^*完全一致的返回明文M.因为在经典密码中，若攻击者发送给解密预示的请求密文C与攻击者的目标密文C^*相同，则通过日志和审计系统容易发现.然而在量子攻击中，对量子比特状态的变化不容易监测，所以，在攻击模型中，应该将上述条件修改为攻击者解密预示返回的明文M与攻击者的目标明文M^*不同.

4 效率分析

Kawachi等^[4]提出的多比特方案中，明文为lbm经典比特，每份公钥长为m个量子态，每个量子态为O(nlbn)量子比特(n为安全参数)，私钥为O(nlbn!)量子比特，密文为nlbn量子比特.

Hayashi等^[13]证明若攻击者获得公钥的界为N=O(nlbn/(mlbm))，则该多比特方案具有信息论不可区分性.

第2节提出多比特量子公钥加密方案中，明文分块长度为m经典比特，每份公钥长为N_d个量子比特(至多生成N_d份，N≤N_c)，私钥为lbn+nN_d经典比特(n为安全参数)，密文为m+n′+l量子比特.

设攻击者利用前向搜索攻击，成功恢复明文的概率为$\Pr = \frac{1}{{{2^m}}} + {q^{m + l + {n^\prime }}} - \frac{1}{{{2^m}}} + {q^{m + l + {n^\prime }}} $，若要其概率近似于随机猜测目标明文的M^*的概率1/2^m，那么，q^m+n′+l(1－1/2^m) < q^m+n′+l < ε, ε为一个可忽略的数，q=(2N+1)/2(N+1) (N为攻击者可以获得的公钥拷贝份数).密文长度满足下列条件$m + n' + l \ge \frac{{\ln \varepsilon }}{{\ln q}} > \frac{{\left| {\ln \varepsilon } \right|}}{{\ln \left( {2N + 2} \right)}} $, 进一步约为$m + n' + l \ge \frac{{\ln \varepsilon }}{{\ln q}} > \frac{n}{{\ln \left( {2N + 2} \right)}} $, 因为n为安全参数，故而$ \varepsilon \le \frac{1}{{{2^n}}}$.

显然，同样的明文分块长度下，Kawachi等^[4]方案中的公钥随安全参数n增长而使指数增长，而新方案呈线性增长趋势；但是Kawachi等^[4]的方案中密文扩展是安全参数的多项式函数，由于新方案前向搜索攻击，密文扩展亦随安全参数n增长而线性增长.

5 结束语

提出了一种新的多比特(明文为经典比特串)量子公钥加密方案，并使用目前已知的攻击方法对其进行了安全分析，结果表明，在安全参数足够大的情况下新方案是安全的.直观上看，笔者提出的构造方法同样适用于将其他比特方案^{[3, 8-11]}扩展为多比特方案，也就是加密的第4)步替换为使用其他逐步特加密算法依次加密T=t₁‖t₂.此外在保障安全的前提下是否可以进一步简化加解密过程，或者如何在特殊应用，如图像信息加密^[14-16]场景下优化方案效率，是下一步需要探讨的问题.