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.