Gr_bner基求解算法的研究及其密碼函數(shù)上的應用.pdf

1、代數(shù)攻擊是近年來提出的一種密碼分析方法，已被應用于流密碼、多變量公鑰密碼、橢圓曲線公鑰密碼和McEliece公鑰密碼等的分析中。其核心思想就是把對密碼算法的安全性分析轉(zhuǎn)化/規(guī)約為一個多元高次方程組的求解問題。一般而言，這個問題是困難的，一類重要的求解算法是通過求解方程組所對應的多變量多項式組的Gr(o)bner基來實現(xiàn)的。因此，Gr(o)bner基求解算法的效率直接決定了代數(shù)攻擊的有效性、密碼算法的安全性。不僅如此，Gr(o)bner基

2、的求解算法已廣泛應用于編碼理論、物理、生物等其它自然科學領域，所以研究設計高效的Gr(o)bner基求解算法是一個十分重要的課題。該文對Gr(o)bner求解算法及其在密碼函數(shù)上的應用進行了深入的研究與分析，概括為以下五個部分。
　　1、首次證明了F5算法的終止性問題。F5算法是求解Gr(o)bner基的最快算法之一，其在ISSAC02會議上被提出之后不久便在Crypto03會議上首次被用于攻破了隱藏域方程(HFE)的80比特挑戰(zhàn)

3、。然而，任意多項式系統(tǒng)中的F5算法的有限步終止問題在本文之前仍然是一個公開問題。本文根據(jù)F5的結構特點，構造了一個通用的F5GEN算法，而F5算法只是我們這一通用算法的一個具體實例。通過證明F5GEN算法的有限步內(nèi)終止，作為這一結論的一個推論便證明了F5算法的有限步內(nèi)終止。
　　2、給出一個求解Gr(o)bner基的實用算法。從Gao-Volny-Wang(GVW)框架出發(fā)，出于對實際應用的考慮，給出一個實例算法，提出算法層次的優(yōu)

4、化設計方法。同時，還給出一個高效的約化準則。通過實驗，該文比較了算法可用的各項準則及策略。結果表明，矩陣型GVW實例在準則和策略的選取上是最優(yōu)的。同時，矩陣型GVW在某些多項式系統(tǒng)（如，Cyclic系列和Katsura系列多項式系統(tǒng)）下比Buchberger型GVW要快約2～6倍。
　　3、給出齊次F5算法有限步終止的簡單證明。提出了一個通用的算法框架，利用重寫基的性質(zhì)證明該框架能在有限步內(nèi)正確終止。隨后，對F5算法的約化操作進行

5、合理的化簡，并且對于齊次F5算法，證明了其復雜的選擇策略等價于按模序選擇。因此，齊次F5算法就能看成該框架的一個特例，從而得到了齊次F5算法有限步內(nèi)終止的一個更簡潔的證明。
　　4、首次證明了非齊次F5的正確終止性。通過比較GVW-Huang-Stroomer(GVWHS)算法和F5算法，發(fā)現(xiàn)GVWHS算法在求解某些系統(tǒng)時要比F5算法快一個指數(shù)級。首先提出了更通用的算法框架，該框架能夠同時模擬GVWHS和F5算法。證明了這一通用算

6、法框架必在有限步內(nèi)終止，因而，一類算法（包括齊次和非齊F5算法）也在有限步內(nèi)終止。GVWHS和F5過去被認為兩個不同的算法。而我們的工作表明，GVWHS和F5只是在一個框架內(nèi)應用了不同的模序、選擇序以及重寫序作為插件的兩個算法，因此，只需通過研究我們的這一通用框架就可以得到GVWHS和F5兩個算法的更清晰、簡潔的結果。實驗表明，對于Random-n和HFE-(12，n)系列多項式系統(tǒng)，GVWHS似乎比幾種F5算法的實現(xiàn)要快一個指數(shù)級。<