-
信息的保密一般是通过对信息进行加密来实现的,而按照Kerckhoffs原则,一个密码体制的安全应该基于密钥的保密而不是对算法本身的保密.正因为如此,密钥分配成为密码学中非常重要的研究课题.基于公钥算法的密钥分配方案的安全性大多是基于求解困难性并没有得到证明的数学难题上的,如Diffie-Hellman方案就是基于离散对数问题是难解的假设上的.随着算法的改进和硬件的升级,特别是量子计算机的诞生,这些困难问题很可能变得容易[1-2].而量子密钥分配方案的安全性则由量子力学原理所保证,因此其安全性不受算法和硬件的影响.目前最著名的量子密钥分配方案(也是史上第一个量子密钥分配方案)是1984年由Bennett和Brassard发明的BB84[3]. BB84在进行密钥分配过程中要用到两个信道:一个量子信道和一个可认证公开信道.通信的双方Alice和Bob通过量子信道在他们之间传输量子信息,为建立一个共享的对称密钥做准备. Alice和Bob利用公共信道对通过量子信道得到的信息进行处理,以便能得到共享的对称密钥,然后在公共信道上传输用共享对称密钥加密的数据.可认证公开信道是假设任何人都能监听此信道,但不能改变其中的信息. BB84密钥分配过程由下面的3个步骤构成:
1) 产生原始密钥(raw key generation):通信的双方通过量子信道产生两个等长的比特串;
2) 信息调和(information reconciliation):通信的双方通过可认证公开信道交换信息,对两个等长、但不一定相同的比特串进行纠(滤)错,使之变成相同的比特串;
3) 保密增强(privacy amplification):通信的双方通过可认证公开信道交换信息,消除在进行前面两个步骤的过程中第三方可能获得的信息,以提高比特串的保密性.
量子密钥分配的一个重要特征是能探测到窃听者的存在,而要取得这一特征,在通过量子信道产生原始密钥时双方基串的选择要有一定的随机性,但这又会影响整个方案的效率.本文给出一个基串的生成方法,在保证随机性的同时,又可以提高效率.
全文HTML
-
先介绍一些概念和结论.由于篇幅所限,只介绍与本文密切相关的.若想了解更多,请参考文献[4-5]的相关章节.在量子信息论里与经典信息论中比特(bit)对应的是量子比特(qubit).比特只有两个状态:0和1,而量子比特的状态可以用2维Hilbert空间
$\mathscr{H}$ 中的单位矢量表示.设|0〉,|1〉是$\mathscr{H}$ 的一组标准正交基,记则|+〉,|-〉也是
$\mathscr{H}$ 的一组标准正交基,这两组基分别称为Z基和X基.对于状态α=a|0〉+b|1〉,当在Z基下测量(measure in basis Z)时,只能得到|0〉或|1〉,其中得到|0〉的概率为a2,得到|1〉的概率为b2.特别地,在Z基下测量|0〉(|1〉),则得到的一定是|0〉(|1〉);在Z基下测量|+〉或|-〉,则得到|0〉或|1〉的概率均是
$\frac{1}{2}$ .同样的,对于状态β=c|+〉+d|-〉,当在X基下测量时,则只能得到|+〉或|-〉,其中得到|+〉的概率为c2,得到|-〉的概率为d2.特别地,在X基下测量|+〉(|-〉),则得到的一定是|+〉(|-〉);在X基下测量|0〉或|1〉,则得到|+〉或|-〉的概率均是$\frac{1}{2}$ .下面总假设n,m是正整数.用(a1,…,al)l表示长度为l的串(string),在不引起混淆的情况下简记为(a1,…,al).
定义1 设l是正整数,ai=(ai1,…,aim)是长度为m的比特串,1≤i≤l.数
称为a1,…,al的相关系数,记为Correlation(a1,…,al).对于β∈{0,1},数
称为a1,…,al的β相关系数,记为Correlation(a1,…,al)β.显然有
设a=(a1,…,am)和b=(b1,…,bm)是两个比特串.显然
此数称为a与b的错码率.
下面介绍BB84协议[4].
1) Alice随机地选择N=(4+δ)n个比特做成一个数据比特串a=(a1,a2,…,aN).
2) Alice再随机选择一个有N个比特的比特串b=(b1,b2,…,bN).对于1≤i≤N,如果bi=0,那么Alice把ai编码为{|0〉,|1〉};否则编码为{|+〉,|-〉}.也就是把a编码为具有N个量子比特的一个块:
其中|ψ00〉=|0〉,|ψ10〉=|1〉,|ψ01〉=|+〉,|ψ11〉=|-〉.
3) Alice通过量子信道把|ψ〉发送给Bob.
4) Bob随机地选择一个比特串b′=(b′1,b′2,…,b′N).对通过量子信道接收到的第i个量子比特,若b′i=0,则在Z下测量,否则在X下测量. Bob将测量的结果按照
的编码规则逐个、顺序地转化成一个数据比特串a′=(a′1,a′2,…,a′N).
5) 在公开信道上Alice公布b,Bob公布b′.
6) Alice和Bob分别保留a和a′中位置对应于b-b′中分量为0的位置的比特,即当bi-b′i=0时,Alice保留ai,Bob保留a′i;否则Alice删除ai,Bob删除a′i.这样Alice和Bob将分别得到一个长度约为2n的比特串a和a′. a和a′称为筛后比特串.
7) Alice和Bob协商在2n个位置中随机地选择n个位置,然后通过公开信道公布各自这n个位置上的比特值.
8) 若双方这n个位置上对应比特串之间的错码率e超过可接受的限度emax,则终止协议.
9) Alice和Bob在各自剩下的约n个比特(构成的两个比特串称为原始密钥)上通过公开信道进行信息调和与保密增强以获得m个比特的共享密钥.
由于比特串b和b′分别确定Alice的编码基和Bob的测量基,所以也将这两个比特串称为基串.
量子密钥分配与传统密钥分配的一个重要区别是前者能探测到窃听者的存在. BB84能取得这一特性的关键是在步骤2) 和步骤4) 中Alice和Bob分别独立随机地选择基串b和b′.在无窃听、无噪音的情况下,在步骤8) 的比较中,对应比特值不同的个数为0,也就是说两个被比较的串的相关系数为1.如果有窃听,因为Alice和Bob是独立地选择b和b′,Eve选择的基只有
$\frac{1}{2}$ 的概率与Alice和Bob的选择相同.在不相同的情况下,Bob接收的量子比特将有$\frac{1}{2}$ 的概率与Alice发送的量子比特不同,因此当Eve以λ的概率窃听每一个量子比特时,通过步骤8) 的比较,Alice与Bob对应比特值不同的出现概率将可能达到$\frac{\lambda }{4}$ .如果λ较大时,就有可能在步骤8) 被检测出.注意,在步骤8) 中双方各自参与对比的n个比特中,两个对应比特之间,Alice发送所选择的基与Bob测量所选择的基是一致的,既可能是Z基,也可能是X基.在对比中,双方没有把n个比特按基分成两个串分别比较,而是组成一个串来比较.称这种不区分基的对比检验为统一对比检验.
为了说明方便,我们从操作的角度将上面BB84协议的步骤2) 和步骤4) 做一些形式上的变化,为此要用到(伪)随机数生成器,本文考虑的(伪)随机数生成器产生的都是区间[0, 1]上的实数,且具有均匀分布.下文中产生一个数是指调用随机数生成器一次让其输出一个数.
定义2 设p=(p1,…,pm)是一实数串,其中0<pi<1(i=1,…,m),称为概率串.给定p,可按下面方法产生一个比特串r=(r1,…,rm):对整数i(1≤i≤m),随机产生一个实数xi,0≤xi≤1,令
ri称为依照pi产生,而r称为依照p产生.
由于x1,…,xm是随机产生的,所以依照p产生的比特串不是唯一的.不难证明下面这个定理.
定理1 若a和b都是依据p=(p,p,…,p)m产生的,其中0<p≤12,则Correlation(a,b)的期望值为1-2p(1-p).
由定理1不难看出,BB84协议中步骤2) 和步骤4) 中的b和b′都是依据p=
${\left( {\frac{1}{2},\frac{1}{2}, \cdots ,\frac{1}{2}} \right)_N}$ 产生的.前面已经说明,由于Alice和Bob是各自独立地依据p=${\left( {\frac{1}{2},\frac{1}{2}, \cdots ,\frac{1}{2}} \right)_N}$ 分别产生基串b和基串b′,因而通过步骤8) 可以检测出窃听;但也正是因为双方独立地依据p=${\left( {\frac{1}{2},\frac{1}{2}, \cdots ,\frac{1}{2}} \right)_N}$ 生各自的基串,所以Bob接收到的数据比特串与Alice的数据比特串的相关系数在没有窃听的情况下只有$\frac{1}{2}$ ,因此在量子信道,BB84的效率$\left( {\frac{筛后比特串的长度}{N} \approx 0.5} \right)$ 只有约50%.为了提高BB84的效率,文献[6]给出了一个方法,该方法产生b和b′时所依据的概率串为p=(p,p,…,p)N,其中0<p≤
$\frac{1}{2}$ .此时,b和b′中分量为0的比例约为1-p,分量为1的比例约为p.这就是说Alice在步骤2) 选择Z基编码,Bob在步骤4) 选择Z基测量的比例约为1-p,而双方选择X基的比例约为p.由定理1,当p→0时,Correlation(b,b′)的期望值趋向于1,从而Correlation(a,a′)的期望值也趋向于1,因此量子信道的效率趋向于100%.此时在步骤8) 若采用统一对比检验,很可能无法检测出某些窃听.文献[6]给出了一个窃听的方案,此方案是一个中间攻击方案(man in the middle attack).对每个Alice发送给Bob的qubit,Eve按下面的策略操作:
1) 以概率pZ选择Z基测量,然后将测量结果重发给Bob;
2) 以概率pX选择X基测量,然后将测量结果重发给Bob;
3) 以概率1-pZ-pX什么都不做.
用eZ表示Alice和Bob都选择Z基时的错码率,用eX表示Alice和Bob都选择X基时的错码率.由于在这两种情况下,Alice和Bob选择的基都相同,所以出错只能是由Eve选择了不同的基测量导致的,故
若采用统一对比检验,Alice和bob只能发现平均错码率:
若Eve只选择Z基测量,即pZ=1,pX=0,则有
当p→0时,e→0,因此采用统一对比检验,Alice和bob将无法检测出Eve的窃听.
这种攻击能够成功是利用了Alice和Bob偏向于选择Z基,在窃听时也偏向于选择Z基窃听,因此Alice和Bob在Z基中的对应比特的错码率小于其在X基中的对应比特的错码率.由于统一对比检验得出的是两种错码率的平均值,尽管一个错码率可能很高,但由于另一个错码率较低,拉低了平均值,故而统一对比检测无法测出Eve的窃听.
为抵抗这种攻击,文献[6]还给出了一个较统一对比检验细化的方法:在步骤7),Alice和Bob协商在2n个位置中分别随机地选择m1个双方选择Z基的位置和m2个双方选择X基的位置,这里m1≈
$\frac{n}{2}$ ≈m2,然后通过公开信道公布各自这m1+m2个位置上的比特值.在步骤8) 将各自m1个采用Z基的比特组成一个子串,采用X基的组成另一个子串,然后分别计算这两个子串与对方对应子串的错码率eZ和eX.在步骤8),只有当eZ,eX<emax时,才进行步骤9).称这种对比检验为分类对比检验.文献[6]中,步骤9) 选择的n个比特值都来自发送和接收都选择Z基的比特值(因为选择Z基的比特数在p<${\frac{1}{2}}$ 时要多于选择X基的比特数).文献[6]证明了在BB84中依据p=(p,p,…,p)N来产生b和b′,然后用分类对比检验来替换统一对比检验,这样改进后的方案是安全的.为方便起见,称改进后的方案为LCA-BB84方案.
LCA-BB84方案虽然能提高BB84产生原始比特的效率,但这个效率更多体现在量子信道上. BB84之所以要在步骤7) 从2n个比特中选取n个来进行对比检验,是为了使得到的检验结果具有较高的精确度,即能够使检验得到的错码率尽可能接近双方剩余的n个比特串的实际错码率.从统计学的角度来说,参与检验的比特数越大,得到的结果的精确度也就越高.文献[6]的作者也认为如果要求Eve攻破系统的概率是剩余比特长度n的指数函数的倒数(因为量子密钥分配要达到的安全等级是无条件安全,所以这个攻破系统的概率要求是合理的),那选择参与检测的比特数与n同级是必须的.
为了在步骤7) 有2n个比特,BB84通过量子信道要发送约4n=N个qubit.若LCA-BB84方案在取p=
${\frac{1}{3}}$ 时针对两个基的错码率也要达到和BB84相同的精确度,也就是对应于每个基的比特串的长度都是n,加上剩余的n个比特,则至少要在步骤6) 得到3n个比特,因此通过量子信道发送的qubit至少要$\frac{{3n}}{{1 - 2p\left( {1 - p} \right)}} = \frac{{27n}}{5}$ 个,大于BB84的4n.如果只要求总的参与比较的比特数是n,即m1=m2=$\frac{n}{2}$ .由于m2≤Np2,因此通过量子信道发送的qubit至少要$\frac{{{m_2}}}{{{p^2}}} = \frac{{9n}}{2}$ =4.5n,也大于BB84的4n.从另一个角度来看,若要求发送qubit的总数不超过4n,即要保证N≤4n,则m2≤Np2≤4np2,故p≥$\sqrt {\frac{1}{8}} > \frac{1}{3}$ .从上面的分析看出,文献[6]声称的LCA-BB84的效率高于BB84,主要体现在量子信道上.从总体来看,LCA-BB84效率的提高是有限的.在不增加传送的qubit的总数的情况下,产生基串时依据的概率串p=(p,p,…,p)N中的p>
$\frac{1}{3}$ ,故由定理1知其效率小于$\frac{5}{9}$ ,并不能无限接近100%.注意,这里还没有考虑LCA-BB84方案在步骤9) 进行信息调和时的比特串全部来自Z基的比特.导致LCA-BB84方案在量子信道效率高,但经过检错后效率回落的原因是:要提高量子信道的效率,就要减少概率串p=(p,p,…,p)N中p的值.而p值的减少,就导致步骤6) 中剩余的比特里X基的比特较少.要保证有足够数量的X基比特来进行错码率对比,要么加大qubit的发送量,要么p的值不能太小.本文给出一种方案,在方案中Alice和Bob都采用一种特殊的方法来产生基串,然后利用分类对比检验,可以使效率达到
$\frac{2}{3}$ .这个方案的效率不仅优于BB84方案,也优于LCA-BB84方案.
-
在BB84方案中的概率串为(
$\frac{1}{2}$ ,…,$\frac{1}{2}$ )N;而在LCA-BB84方案中,概率串为(p,…,p)N,其中0<p≤$\frac{1}{2}$ .一个自然的考虑是将概率串换成(p1,…,pN)后会有什么结果.为此先证明下面的定理.定理2 设概率串p=(p1,…,pm)的各项都是相互独立随机产生的.若a和b都是依据p产生的,则当m→∞时,Correlation(a,b)的期望值为
$\frac{2}{3}$ .证 考察a和b在位置i的对应元素ai和bi.容易看出ai=bi当且仅当ai=1=bi或ai=0=bi.但
所以
因此Correlation(a,b)的期望值为
从这个定理可以看出,若概率串的各项都是独立随机产生的,则双方依据此概率串产生的基串的相关系数就为
$\frac{2}{3}$ ,因此相应的量子信道的效率就是$\frac{2}{3}$ ,高于BB84.下面给出我们的方案.首先假设Alice和Bob共享一个概率串p=(p1,…,pN),其各项是互相独立随机产生的.
1) Alice随机地选择N=(3+δ)n个比特做成一个数据比特串a=(a1,a2,…,aN).
2) Alice依据p产生基串b=(b1,b2,…,bN).对于1≤i≤N,如果bi=0,那么Alice把ai编码为{|0〉,|1〉};否则编码为{|+〉,|-〉}.也就是把a编码为具有N个量子比特的一个块:
其中|ψ00〉=|0〉,|ψ10〉=|1〉,|ψ01〉=|+〉,|ψ11〉=|-〉.
3) Alice通过量子信道把|ψ〉发送给Bob.
4) Bob依据p产生基串b′=(b′1,b′2,…,b′N).对通过量子信道接收到的第i个量子比特,若b′i=0,则在Z下测量,否则在X下测量. Bob将测量的结果按照
的编码规则逐个、顺序地转化成一个数据比特串a′=(a′1,a′2,…,a′N).
5) 在公开信道上Alice公布b,Bob公布b′.
6) Alice和Bob分别保留a和a′中位置对应于b-b′中分量为0的位置的比特,即当bi-b′i=0时,Alice保留ai,Bob保留a′i;否则Alice删除ai,Bob删除a′i.这样Alice和Bob将分别得到一个长度约为2n的比特串a和a′. a和a′称为筛后比特串.
7) Alice和Bob协商在2n个位置中随机地选择n个位置,然后通过公开信道公布各自这n个位置上的比特值.
8) 双方分别计算n个位置中使用Z基和X基的比特构成的两个串与对方对应串的错码率eZ和eX.若eZ>emax或eX>emax,则终止协议.
9) Alice和Bob在各自剩下的约n个比特上通过公开信道进行信息调和和保密增强以获得m个比特的共享密钥.
在上述方案中,基串的每一项取1或取0的概率都要根据概率串中相应的项来调整,且这种调整具有一定的随机性,因此将这个方案命名为PARK(probabilistic adaptive random key generation).
在PARK方案中,由于概率串的第i项是pi,所以双方基串的第i项为1和0的概率分别为pi和1-pi.由大数定律可知基串中1和0出现频率的期望值分别为
和
也就说当基串长度足够长时,基串中1和0出现的频率基本相同.
由定理2知,在PARK的步骤6),a和a′的长度约为
因此整体来看,要产生长度为n的原始密钥,BB84需发送约4n个qubit,而PARK只需发送约3n个.若只考虑量子信道,PARK的效率是
$\frac{2}{3}$ ,比BB84高约17%≈$\frac{1}{6}$ =$\frac{2}{3}$ -$\frac{1}{2}$ .对LCA-BB84,如果要求发送的qubit数不超过(4+δ)n,那么产生基串时所依据的概率串p=(p,p,…,p)N中的p值必须大于
$\frac{1}{3}$ .由于1-2p(1-p)作为p的函数在区间($\frac{1}{3}$ ,$\frac{1}{2}$ ]上是严格单调递减的,故LCA-BB84此时在量子信道上的效率不会超过1-2p(1-p)<$\frac{5}{9}$ <$\frac{2}{3}$ .在发送qubit的总数为(3+δ)n的情况下,即便按$\frac{5}{9}$ 来算,筛后比特串的长度的期望值也只能是3n×$\frac{5}{9}$ <2n.去掉n个参与对比检验的比特,原始密钥的长度就不足n了.因此不论是从量子信道看还是从整体来看,PARK也都优于LCA-BB84.
-
在对BB84的安全性证明中,文献[7]给出的证明方法可能是最简单的.文献[7]实际上给出了一个基于量子纠缠纯化协议(EPP)的量子密钥分配协议,并证明其是安全的,然后证明这个协议的安全蕴含BB84的安全.文献[6]给出了分类对比检验中的两个错码率eX和eZ与EPP中的两个错误率—比特翻转差错(bit-flip error)ebit-flip和相位差错(phase error)ephase之间的一个转换关系:
其中q和1-q分别为最后的密钥中对应于Z基和X基的比特所占的比例.可以看出,适当选择emax,只要
其中δe是一个小的正整数,就能保证
成立.因此文献[7]的论证可移植来证明LCA-BB84的安全性[6]. PARK与LCA-BB84最主要的区别是在基串的产生上,故PARK的安全性可类似地证明.在LCA-BB84中,q=1,所以ebit-flip=eZ,ephase=eX;而在PARK中,可以取q=
$\frac{1}{2}$ ,这时ebit-flip=ephase=$\frac{{{e_Z} + {e_X}}}{2}$ .在PARK中,Alice和Bob要事先共享一个概率串p. p可以由双方共同协商产生,也可用
作为种子,通过一个安全的伪随机数生成器产生.这里authenstr是Alice和Bob用作身份认证的信息,而nonceA和nonceB分别是由Alice和Bob即时随机产生的数.在这种情况下,因为authenstr只有Alice和Bob才有,所以p也只有Alice和Bob才能产生.这时PARK还具有身份认证的作用:因为Alice和Bob能产生p,所以在步骤6) 基串的比较中Correlation(b,b′)≈
$\frac{2}{3}$ ;如果有一方是假冒的,那么Correlation(b,b′)≈$\frac{1}{2}$ ,因此可被另一方发现.
-
提高量子密钥分配的效率对量子密码的实际应用和普及有着积极的作用.在LCA-BB84方案中,双方通过加大选择一个基的概率,减少选择另一个基的概率,使得量子信道的效率得到了提高.但这也导致得到的数据中对应两个基的两类数据中有一类要少于另一类.为了保证检测数据有足够的精确度,两类数据的数目都要足够多,才能保证有足够多的数据被抽样来进行检验.因此要么加大qubit的传送数目,要么减少选择两种基的概率之差.这样一来,LCA-BB84方案的总体效率就受到制约.在PARK方案中,由于两种基的选择总体上是平均的,因此得到的两类数据比例也是平均的,总体效率不受检测的影响.另外,适当调整PARK中概率串的生成方式,就可使PARK具有身份认证的功能