[發明專利]一種VHE實現方法

在審

• 申請號: 201710175292.6
• 申請日: 2017-03-22
• 公開（公告）號: CN106961328A
• 公開（公告）日: 2017-07-18
• 發明（設計）人: 楊浩淼;金保隆;黃云帆;何偉超;冉鵬;姚銘軒;汪小芬
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L9/08
• 分類號: H04L9/08;H04L9/30
• 代理公司: 成都弘毅天承知識產權代理有限公司51230
• 代理人: 王正楠

技術領域

本發明涉及整數向量同態計算領域，尤其涉及一種基于矩陣的公鑰加密算法的分析與攻擊的實現方法。

背景技術

VHE(Vector Homomorphic Encryption)，是一個針對整數向量的同態加密方法，以下簡稱VHE方法。VHE方案支持整數向量的同態加法、線性變換、向量內積等運算。其處理整數向量的同態計算效率較高，在數據挖掘、云計算方面有較好的應用前景。

VHE方法在加密過程中所使用的技術被稱為Key-Switching，VHE方法的安全性基于如下數學關系：Sc＝wx+e，其中，S：私鑰矩陣，c：密文向量，w：公共參數，x：明文向量，e：噪聲向量；Key-Switching的具體步驟為：

(1)將明文進行比特化處理；比特化過程如下:對于明文向量，要將向量的每個維表示為長度為l(此處l為小寫L，l代表比特化參數)的0-1比特向量，所有0-1向量比特組成比特化的明文向量，如x＝(3,2)，l＝3，那么x^*＝(1，1，0，0，1，0)，矩陣的比特化，取S中的每個元素s_i，將其擴展為s_i，2s_i，4s_i，然后所有的擴展向量組成S^*。

(2)指定新的私鑰S＝[I，T]，其中，I代表單位矩陣，T代表隨機矩陣；

(3)構造公鑰矩陣其中，A是一個隨機矩陣(此處的隨機矩陣A和步驟(2)中的隨機矩陣T的用處和維度均不相同，T在計算私鑰矩陣S和公鑰矩陣M上半部分時用到，而A在計算公鑰矩陣上下兩部分時用到)，E是隨機生成的噪聲矩陣，I^*是進行了比特化擴展的單位矩陣；

(4)計算密文c＝Mx。

相應的解密過程為：

上述步驟中，在已知某次單向加密的公鑰與密文的情況下，可以通過如下方法對本次加密進行破解：

上述過程中將公鑰構造為將私鑰構造為S＝[I，T]，觀察公鑰結構，不難從其中得到如下內容M_m＝[TA-E]，如果知道算法使用的比特化參數就可以直接計算出M矩陣上半部分所占行數，然后就可以從該矩陣中得到[TA-E]的結構。如果不知道比特化參數，由于M上半部分的列數是其行數的整數(這個整數即是比特化參數)倍，所以可以從M的列數的因子中選擇一個作為M上半部分的行數，然后對M進行分解。根據A盡可能多的構造矩陣M_m中向量的線性組合，并將其作為矩陣T中向量線性組合的近似值。考慮到解密操作即可由上述分析中得到的T中向量線性組合的近似值來模擬解密過程:

根據Mmin，A可以得到T中向量的若干線性組合，再考慮解密過程：

從上述步驟中我們可以看出，以T中向量線性組合的近似值及密文盡可能多的模擬解密過程，即可得到若干組明文的近似值，再考慮到M中引入的噪聲和w的關系，可以推斷出該近似值與真實值十分接近。

對于一個公鑰加密方法而言，私鑰是不允許公開的，也不允許方法中的公開部分瀉露私鑰、明文的相關信息，而通過上述的分析方法可以破解其單向加密，也就是說現有的VHE方法未能有效地隱藏公鑰和私鑰的關系，因此，該實現方法是不安全的。

發明內容

本發明的目的在于：解決現有VHE實現方法因未能有效隱藏公鑰和私鑰的關系，而導致的安全問題，本發明提供一種VHE實現方法。

本發明的具體方案如下：

一種VHE實現方法，包含以下步驟：

步驟一：根據要加密的明文向量構造如下矩陣其中x代表明文向量，表示n維整數向量集合，I表示單位矩陣，表示a行b列的矩陣集合，T，A表示隨機生成的整數矩陣，w表示加密算法中選取的一個大整數,S′和M′都是計算的中間產物，目的是利用這兩個矩陣計算S和M。

步驟二：生成一可逆矩陣及其逆矩陣P_s，P_m表示有理數矩陣，表示a行b列的有理數矩陣集合。

步驟三：根據步驟一和步驟二得到的S′、M′、P_s、P_m的值計算私鑰S和公鑰M，其中，S＝S′P_s，M＝P_mM′。

步驟四：根據步驟三中得到的公鑰M進行加密操作，計算密文向量c＝Mx+e，其中，e表示噪聲向量。