MIMO格密码的设计与实现

刘年生

集美大学 计算机工程学院，福建 厦门 361021

1 引言

MIMO（Multiple Input Multiple Output）技术最早是由G.Marconi于1908年提出的，用于抑制信道衰落[1]。在过去的50年，经过Cox、Foschini和Andersen等著名学者创造了一系列新的MIMO实现方法，在不增加带宽的情况下，MIMO成倍地提高通信系统的容量和频谱利用率。MIMO从早期单用户模式逐步发展到大规模、3D模式，成为下一代无线通信的关键技术之一[2]，应用广泛。

由于MIMO无线传输的内在特性（如传输的广播性、叠加性和共享性等），现有的安全机制缺陷[3]，加之攻击者的计算能力越来越强[4]。因而，MIMO通信安全问题备受关注，开始从物理层来解决这一问题[5]。根据大规模MIMO的固有特性，提出一种基于格和OAEP+的密码方案，以提高MIMO通信的安全性。

2 安全模型

Shannon在1949年提出了保密通信模型[6]，如图1所示。在图1中 Alice和Bob是一对合法通信用户，Eve是窃听者。当Alice发送消息M给Bob时，先在密钥K的参与下，将明文M加密成密文X，然后将密文X通过公共信道发送给合法接收者Bob。Bob将收到的密文X在密钥K的参与下恢复出明文M。与此同时，窃听者Eve从公共信道上也收到密文X，但在不知道密钥K的情况下恢复明文至少在计算上是困难的。Shannon加密系统比较适合对称密码体制。

图1 Shannon保密通信模型

在Shannon保密通信模型基础上，Wyner提出了窃听信道模型[7]，如图2所示。合法通信者Alice和Bob之间的信道为主信道，是无噪声的，而Eve和Alice（或Bob）之间的信道为次信道（即：窃听信道），是有噪声的；将K比特长的数据MK编码成N(N>K)比特长的数据XN通过二级制对称信道（BSC）发送时，可推导出如下关系式：

公式（1）中，Δ为数据不确定性度，H为条件信息熵，φ为XN的一个子集，子集元素个数为μ(μ

图2 Wyner窃听信道模型

3 格密码

在量子计算机时代，原有的许多密码算法如RSA和Diffie-Hellman等不再具有可接受的应用安全性，一般推测认为，只有基于NPC（Nondeterministic Polynomial Complete）或NP-Hard问题的密码算法才具有抗量子计算机攻击的能力。因此，格密码近年来备受关注[9]。格是Rm中一类具有周期性结构离散点的集合。严格地说，格是m维欧式空间Rm的n(n≥m)个线性无关向量组A1,A2,…,An的所有整系数线性组合，即：

向量组 A1,A2,…,An称为格L(A)的一组基，Zn为n维复数集，m称为格的维数，n称为格的秩，当n=m时称为满秩。在格理论研究中，存在一系列困难问题[10]，主要有最短向量问题（Shortest Vector Problem，SVP）、最近向量问题（Closest Vector Problem，CVP）、小整数解问题（Small Integer Solution Problem，SIS）和误差学习（Learning With Errors Problem，LWE）等。在不同近似参数γ和不同范数Lp(1≤p≤∞)下，对SVP和CVP问题的计算难度结论是不同的，如表1所示。

表1SVP和CVP计算难度

在表1中，Boas在1981年证明了L∞范数下的精确SVP计算难度是NP-hard的[11]，精确CVP计算难度是NP-C的，并猜测在L2范数下精确SVP计算难度同样是NP-hard的。2007年，Peikert证明了近似参数为O n，范数为Lp(p≥2)下n维格的CVP和SVP都是CoNP的。一些与SVP密切相关的格问题，如GapSVP（Decision Shortest Vector Problem）、aSVP（approximation SVP）、SIVP（Shortest Independent Vector Problem）、BDD（Bounded Distance Decoding）等等，都可以归约为不同制约条件下的SVP问题。同样，对一些与CVP密切相关的格问题，存在类似的归约。

LWE和SIS在格问题的最坏情况到一般情况的归约中扮演着重要的角色，这种归约能保证格问题在一般情况下拥有与最坏情况类似的复杂度，在常规的理论求解和分析中，最坏情况的问题困难程度结果比较容易获得。

4 MIMO格密码原理

在Wyner窃听模型下，主信道和窃听信道都采用MIMO方式，不失一般性，假设n×h的MIMO是n根发射天线，h根接收天线，则MIMO接收信号矢量y表示为：

其中，x∈Rn为需要传输的信号矢量，A∈Rn×h为信道增益矩阵，信道增益矩阵的元素值分布为零均值、标准偏差为k/的高斯分布，记为Ψk，e∈Rh为信道噪声，分布为零均值、标准偏差为α/的高斯分布Ψα。对于实数型信道系数的MIMO而言，传输星座图χ可以定义为[0,M)的整数集合。

若用矢量ai表示发射端到第i根接收天线的信道增益，x为来自χn的传输信号矢量，ei为发射端到第i根接收天线的噪声矢量，则第i根接收天线接收的信号为：

若MIMO信道的最小噪声和星座大小满足如下条件，就可以将MIMO解码问题与解标准格问题关联起来，在物理层构建起MIMO格密码，提高信息传送的安全水平[19]。

最小噪声：

星座大小：

其中参数p>0，它是由用户或系统来选择的，是信噪比（SNR）要求与星座大小的折中。

为了把消息x传送给Bob，Alice将对其进行线性预测编码[20]，对信道增益矩阵A进行奇异分解得到A=UΣVH，其中，U 是n×n阶酉矩阵，Σ是n×h对角矩阵，VH是h×h阶酉矩阵V 的共轭转置。将x=Vx发送给Bob。Bob收到Alice发来的消息后，计算 y =UHy=Σx+e，由于Σ是A的对角矩阵，表示A的奇异值的；所以Bob能在关于n的线性复杂度内估算出x。同时，注意到U是酉矩阵，因此，

同时，窃听者Eve通过窃听信道收到Vx后，其计算表示为：

应注意到V是关于A的右奇异向量，跟B无关，为一酉矩阵；同时，高斯随机矩阵具有正交不变性[21]；所以BV跟B属于同一分布。Eve通过公式（7）恢复出x的困难性等可以归约为解标准格问题（如GapSVP、SIVP和BDD等）的困难性[19]，并通过LWE归约机制，保证在一般情况下MIMO解码难度，具有在最坏情况下同样的解码难度，计算复杂度为O()2n，因此，当n足够大时，窃听者Eve即使具备量子计算机的计算能力，也难以恢复出x。

5 MIMO格密码的实现与分析

MIMO格密码在理论上被证明是可能的，其实现方案就成为研究者所关注的热点。根据Shoup所提的OAEP+算法[22]，设计出一种大规模MIMO格密码实现方案，方案如下：

不妨设K=nlbM是每个MIMO信道所传输的比特数，Alice想把消息m传送给Bob，消息m长度为η=K-2n比特。若Alice和Bob都能访问三个随机预言函数：G:{0,1}n→{0,1}η，H′:{0,1}n+η→{0,1}n，H:{0,1}n+η→{0,1}n。Alice从{0,1}n+η随机均匀选取r，按图3所示的加密公式计算 s∈{0,1}n+η，t∈{0,1}n和 x∈{0,1}K，然后将X与Bob信道的右奇异向量相乘，即：x=Vx，发送给Bob。Bob收到 x消息后，计算 y =UHx，恢复出 X ，按图3所示的解密公式计算，恢复明文消息m，并根据c=H′(r||m)是否成立，验证所收到的Alice消息，如果c=H′(r||m)不成立，则拒绝接受所收到的Alice消息，否则就接受所收到的Alice消息。

图3 MIMO格密码加解密计算流程

在MIMO格密码方案实现时，上述三个随机预言函数G、H和H′一般采用安全散列函数，如SHA-2类（SHA-256、SHA-512等），它们具有高度的雪崩效应和抗碰撞攻击能力。为此，在如下参数设置条件下，α=1，p=0.03，k=0.04，三个随机预言函数G、H和H′就采用SHA-256，用Matlab（2014a版）对该MIMO格密码方案进行了仿真实现，仿真结果证明该方案是可行的。因为方案中采用了安全散列函数，必须保证Alice和Bob之间能正确解码，其误码率低至某一可接受的水平，而Eve不能正确解码。这种安全的解码方式与MIMO信道的可计算保密容量密切相关。根据格基归约算法[23]，在参数α=1，p=1条件下MIMO每条信道的可计算保密容量（Computational Secrecy Capacity）如图4所示，随着发射天线数目的增加，MIMO每条信道的可计算保密容量呈线性增长。线性判定系数R2=0.999 8，接近于1，证明这两者之间具有较强的线性拟合关系。

图4 MIMO发射天线数目与每条信道可计算保密容量的关系

尽管发射天线数目的增加既有助于提高抗量子计算攻击，又有助于提高信道保密容量。但是，如果发射天线数目太高，会增加工程实现的困难和成本，在安全性、可实现性和经济性博弈中，合理选取一个发射天线数目。

所提密码方案是基于大规模MIMO的解码复杂性，将大规模MIMO的解码复杂性归约为解标准格问题（如GapSVP、SIVP和BDD等），即使在最坏情况下，它的解码复杂度至少为O(2n)。因此，本方案的计算复杂度随MIMO发射天线n呈指数关系增大，当n足够大时，所提方案具有抗量子计算攻击的能力。其次，在本方案设计中采用了OAEP+算法，而OAEP+算法被证明是具有抗自适应选择性密文攻击的能力[22]，本方案自然继承这一特性，具有抗自适应选择性密文攻击的能力；而自适应选择性密文分析是目前已知的最强的密码分析方式，如果一个密码系统能够抵抗自适应选择性密文攻击，那就可以认为它能够抵抗其他常见攻击，包括唯密文攻击、已知明文攻击、选择性明文攻击和非适应性选择密文攻击等。第三，本方案在进行加密通信时双方不需要预先共享密钥，从而简化了密钥管理。

6 结束语

在Wyner窃听信道模型下，利用较强的高斯随机噪声对MIMO信道的影响，使得MIMO信道呈现出复杂的时空动态变化特性，从而将窃听者对大规模MIMO的解码复杂性问题归约为解标准格问题，并利用大规模MIMO信道增益矩阵的奇异分解特性和OAEP+算法原理，构建出一种MIMO格密码实现方案，并在Matlab开源平台中进行了原型验证，结果证明所提方案是可行的，加密通信双方不需要预共享密钥。仿真计算结果还显示在格基归约算法下MIMO信道保密容量与发射天线的数目呈较强线性关系，MIMO发射天线数目越多，信道保密容量相应增大。

[1]Andersen J B.History of communications/radio wave propagation from marconi to MIMO[J].IEEE Communications Magazine，2017，55（2）：6-10.

[2]Larsson E G，Edfors O，Tufvesson F，et al.Massive MIMO for next generation wireless systems[J].IEEE Communications Magazine，2014，52（2）：186-195.

[3]Wallace J W，Sharma R K.Automatic secret keys from reciprocalMIMO wirelesschannels：Measurementand analysis[J].IEEE Transactions on Information Forensics and Security，2010，5（3）：381-392.

[4]Kapetanovic D，Zheng G，Rusek F.Physical layer security for massive MIMO：An overview on passive eavesdropping and active attacks[J].IEEE Communications Magazine，2015，53（6）：21-27.

[5]Poor H V，Schaefer R F.Wireless physical layer security[J].Proceedings of the National Academy of Sciences Current Issue，2017，114（1）：19-26.

[6]Shannon C E.Communication theory of secrecy systems[J].Bell System Technical Journal，2014，28（4）：656-715.

[7]Wyner A D.The wire-tap channel[J].Bell System Technical Journal，1975，54（8）：1355-1387.

[8]Ozarow L H，Wyner A D.Wire-tap channel II[J].Bell System Technical Journal，1984，63（10）：2135-2157.

[9] 王小云，刘明洁.格密码学研究[J].密码学报，2014，1（1）：13-27.

[10]王旭阳，胡爱群.格困难问题的复杂度分析[J].密码学报，2015，2（1）：1-16.

[11]Boas P E.Another NP-complete partition problem and the complexity of computing short vectors in a lattice，Technical Report 81-04[R].Mathematische Instituut，University of Amsterdam，1981.

[12]Ajtai M O.The shortest vector problem in L2 is NP-hard for randomized reductions（extended abstract）[C]//Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing，Dallas，Texas，USA，1998：10-19.

[13]Micciancio D.Inapproximability of the shortest vector problem：Toward a deterministic reduction[J].Theory of Computing，2012，8（1）：487-512.

[14]Khot S.Hardness of approximating the shortest vector problem in lattices[C]//45th Symposium on Foundations of Computer Science（FOCS 2004），Rome，Italy，2004：126-135.

[15]Haviv I，Regev O.Tensor-based hardness of the shortest vector problem to within almost polynomial factors[C]//Proceedings of the 39th Annual ACM Symposium on Theory of Computing，San Diego，California，USA，2007：469-477.

[16]Peikert C.Limits on the hardness of lattice problems in Lp norms[J].Computational Complexity，2008，17（2）：300-351.

[17]Arora S，Babai L，Stern J，et al.The hardness of approximate optima in lattices，codes，and systems of linear equations[C]//34th Annual Symposium on Foundations of Computer Science，1993：724-733.

[18]Dinur I，Kindler G，Raz R，et al.Approximating CVP to within almost-Polynomial factors is NP-hard[J].Combinatorica，2003，23（2）：205-243.

[19]Dean T R，Goldsmith A J.Physical-layer cryptography through massive MIMO[J].IEEE Transactions on Information Theory，2017，63（8）：5419-5436.

[20]Goldsmith A J.Wireless communications[M].Cambridge，MA，USA：Cambridge University Press，2004.

[21]Edelman A，Rao N.Random matrix theory[J].Acta Numerica，2005，14：233-297.

[22]Shoup V.OAEP reconsidered[C]//Proceedings of 21st Annual International Cryptology Conference，Santa Barbara，California，USA，2001：239-259.

[23]Micciancio D，Walter M.Practical predictable lattice basis reduction[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques，Vienna，Austria，2016：820-849.