格理論在公鑰密碼分析和計算代數(shù)中的應(yīng)用.pdf

1、格是m維實空間Rm正規(guī)排列的點陣，從數(shù)學(xué)的角度看，格是Rm上的一個離散加法子群。格基約化的思想源于18世紀Lagrange[1]、Gauss[2]等人的二次型的約化理論和19世紀末Minkowski[3]的數(shù)的幾何的研究。自從著名的LLL算法[4]在1982年被提出，到如今30年的時間里，格理論在數(shù)學(xué)、密碼學(xué)、理論計算機等領(lǐng)域都得到了廣泛的應(yīng)用和發(fā)展[5]。
　　 在數(shù)學(xué)和公鑰密碼分析方面，LLL算法及其他格基約化算法作為有效的

2、工具得到了廣泛的應(yīng)用(文獻[6]對格基約化算法進行了很好的總結(jié))。很多數(shù)學(xué)問題可以通過轉(zhuǎn)化為格基約化算法可求解的問題而得到解決。比如，有理數(shù)域上單變元多項式的分解問題[4]，變量個數(shù)固定的整數(shù)規(guī)劃問題[7]等。在公鑰密碼體制的安全性分析領(lǐng)域，格基約化算法作為有效的攻擊工具成功評估了多個密碼體制的安全性，包括背包型密碼體制的破解[8-10]，RSA公鑰加密算法的弱密鑰攻擊[11-13]，針對特殊形式的DSA[14，15]和ECDSA[16

3、]的攻擊等。此外，從理論計算機的角度看，格理論中的很多問題被證明是NP-困難的，密碼學(xué)家可以設(shè)計出基于格理論中困難問題的密碼體制，比如，基于uSVP問題的Ajtai-Dwork公鑰加密算法[17]，基于SIS問題的數(shù)字簽名算法[18]以及基于LWE問題的公鑰加密體制[19]等。在量子計算機的模型下，Shor發(fā)現(xiàn)了求解因子分解和離散對數(shù)問題的多項式時間算法[20]，目前，在量子計算機的模型下，還未找到求解NP－困難問題的有效算法。故而，基

4、于格理論中困難問題的密碼體制的分析與設(shè)計成為了備受關(guān)注的“后量子時代密碼體制”的研究熱點之一。
　　 本文針對格理論在公鑰密碼體制的安全性分析和計算代數(shù)方面的應(yīng)用做了一些研究。主要工作包括給出了隨機NTRU格中的最短向量長度的下界估計；對基于向量空間的一個同態(tài)加密體制進行了安全性分析，成功破解了設(shè)計者推薦的三組參數(shù)；對基于中國剩余定理的快速公鑰加密算法，給出了一個啟發(fā)式攻擊。此外，利用格基約化算法，給出了判定有限域Fq上單變元稀

5、疏多項式是否存在解的關(guān)于q的sub-linear的確定性算法。
　　 1、隨機NTRU格的最短向量長度的下界估計
　　 給定一個n維格L，如何尋找格L中的最短向量的問題是計算格理論中最重要的問題之一。關(guān)于最短向量長度的上界估計，可以由著名的Minkowski凸體定理得出，即，如果一個球的體積大于2ndet(L)，那么在這個球中必存在一個非零格點，從而，格中最短向量的長度小于√ndet(L)1/n。對于一個隨機格，可以通過

6、Gaussian Heuristic來“預(yù)測”這個格的最短向量的“平均”長度，即，給定一個行列式是det(L)的n維格L，Gaussian Heuristic預(yù)測在Rn上的可測集()中，包含Vol(())/det(L)個格點，其中Vol(())是可測集()的體積。取()為球心在原點的n維球，由Gaussian Heuristic可以得出，當(dāng)Vol(())≈det(L)時，可測集()中含有一個非零格向量。換句話說，最短向量的長度近似于體積

7、是det(L)的球的半徑，即√n/2eπdet(L)1/n。
　　 在本文的第一個工作中，利用Kolmogorov復(fù)雜度的理論，給出了估計一類隨機整數(shù)格的最短向量長度的下界的一般方法。作為該方法的一個重要的應(yīng)用，給出了隨機NTRU格最短向量長度的下界估計。目前，NTRU公鑰加密體制[21]是IEEE P1363.1的標準之一。密碼體制的加解密運算是在多項式環(huán)Z[X]/(XN-1)上進行的。定義S f和S g分別為單變元多項式環(huán)Z

8、[x]上的最高次數(shù)是N-1，系數(shù)很小的多項式的集合。設(shè)q是一個正整數(shù)，選取多項式f(x)∈S f和g(x)∈S8。設(shè)多項式h(x)=∑n-1i=0hixi滿足通過NTRU格中的短向量可以得到NTRU密碼體制的等價密鑰[21，22]。因此，對于NTRU格的短向量的性質(zhì)的研究對于評估NTRU密碼體制的安全性有著重要的作用。
　　 如果多項式f(x)是集合Sf上隨機選取的可逆元素，多項式g(x)隨機選取自集合Sg，我們稱NTRU格是(

9、Sf，S8)-隨機的。
　　 值得注意的是，Gaussian Heuristic對于隨機的NTRU格是不適用的。由Gaussian Heuristic可以得出，最短向量的長度約為Ω(√Nq)。但是，由多項式f(x)，g(x)的系數(shù)構(gòu)成的向量T=(f0，f1…，fN-1，g0，g1，…，gN-1)∈LNTRU。長度為O(√N)。由于多項式f和g的系數(shù)都很小，許多密碼研究人員猜測向量T是NTRU格的最短向量，但是，至今沒有給出嚴格的

10、證明。
　　 在本文的第一個工作中，給出了估計一類隨機整數(shù)格的最短向量長度下界的一般方法，作為該方法的一個重要應(yīng)用，考慮了隨機NTRU格的最短向量長度的下界估計，證明了NTRU格中最短向量的長度和私鑰(f(x)，g(x))的系數(shù)構(gòu)成的向量的長度之間的比例至少是一個與維數(shù)無關(guān)的常數(shù)。
　　 2、對ISIT2008上的同態(tài)加密算法的安全性分析
　　 在1978年，Rivest、Adleman和Dertouzos[23

11、]首次提出了同態(tài)加密的思想。此后，同態(tài)加密的思想得到了廣泛的應(yīng)用，比如，電子投票系統(tǒng)[24-26]、私密信息檢索協(xié)議[27，28]等。
　　 同態(tài)加密算法可以描述為：給定兩個消息m1，m2，滿足Dec(En(m1)()En(m2))=m1⊕m2這里⊕和()分別代表明文、密文空間的運算。通常，如果⊕代表明文空間中的模加運算，稱這個體制為加同態(tài)的加密體制，如果⊕代表乘運算，則稱為乘同態(tài)的加密體制。如果在同態(tài)加密協(xié)議中，只允許對密文進

12、行有限步的操作，稱為“受限制”同態(tài)加密體制，例如文獻[25，26，29-36]中提出的同態(tài)加密體制等。如果在同態(tài)加密協(xié)議中，允許對密文進行任意次的加法和乘法操作，則稱為“完全”同態(tài)加密體制。最近，Gentry提出了基于理想格的“完全”同態(tài)加密體制[37-39]，隨后，基于其他數(shù)學(xué)困難問題的“完全”同態(tài)加密體制被提出，比如，基于近似最大公因子問題[40，41]和基于環(huán)上的LWE問題[42，43]的同態(tài)加密體制等。
　　 本文的第二

13、個工作是對一個基于向量空間的“受限制”同態(tài)加密體制進行了等價密鑰攻擊。這個密碼體制是由Aguilar Melchor，Castagnos和Gaborit[35]在ISIT2008上提出的(為方便描述，簡稱為MCG算法)。MCG算法的安全性依賴于計算背包向量問題的困難性。根據(jù)設(shè)計者推薦的參數(shù)設(shè)置，最好的恢復(fù)明文的方法是求解一個維數(shù)至少是600的短向量問題。
　　 通過對MCG同態(tài)加密體制的密鑰生成算法的分析，首先，揭示了一個公鑰和

14、密鑰生成過程中的一個臨時私鑰之間的隱藏線性關(guān)系；然后，由部分公鑰構(gòu)造一個維數(shù)遠小于600的維數(shù)約減的格，通過求解這個新格的N個CVP實例，恢復(fù)出隱藏的噪聲矩陣；最后，通過簡單的數(shù)學(xué)操作，可以從這個噪聲矩陣恢復(fù)出一系列的等價密鑰。實驗表明，我們的攻擊對于所有的三組推薦參數(shù)都是實際有效的。
　　 3、基于中國剩余定理的快速公鑰加密算法的安全性分析
　　 在1976年，密碼學(xué)家Diffie和Hellman[44]首次提出了通過

15、基于數(shù)學(xué)難題的單向陷門函數(shù)來構(gòu)造公鑰加密算法的思想。目前，應(yīng)用最廣泛的兩大傳統(tǒng)公鑰算法包括基于整數(shù)分解問題的RSA公鑰加密算法[45]和基于有限域或者橢圓曲線上有理點群的離散對數(shù)問題的Elgamal公鑰加密體制[46]。由于這兩大算法的加解密操作均需要進行運算量較大的模指數(shù)運算，不利于在一些資源受限的設(shè)備上應(yīng)用。因此，設(shè)計安全性高、同時密鑰生成、加解密速度快的公鑰密碼體制成為重要的研究方向。基于背包問題的密碼算法是一種快速公鑰加密體制，

16、其加解密過程只需要模乘法和加法運算，不幸的是，從最初的Merkle-Hellman算法[47]到后來的Chor-Rivest密碼體制[48]都被破解了[49，50]。
　　 Wang等人[51]設(shè)計了一個基于中國剩余定理的快速加密算法，在加解密過程中，只需要幾個大整數(shù)的模乘法運算。相比于RSA、Elgamal算法，加解密速度要快很多。本文的第三個工作是對這個快速加密算法給出了一個啟發(fā)式攻擊，基本的思想是，通過構(gòu)造格，把要恢復(fù)的明

17、文轉(zhuǎn)化成尋找格的短向量或者格中距離目標向量較近的格向量的問題。由于構(gòu)造格的維數(shù)很低，調(diào)用格基約化算法即可恢復(fù)出明文。
　　 4、有限域上單變元稀疏多項式解的存在性判定
　　 本文的第四個工作考慮了格基約化理論在計算代數(shù)上的應(yīng)用，主要研究了有限域上單變元稀疏多項式解的存在性判定問題。即給定有限域Fq，以及單變元t項多項式f(x)=c0+c1xa1+c2xa2+…+ct-1xat-1.(2)判定多項式f(x)在Fq是否存在解