有限域上代數方程算法問題研究2013年度報告

胡磊

摘要：本年度圍繞關鍵科學問題“有限域上代數方程求解”，結合密碼學理論，在求解算法研究及其密碼應用方面取得了以下三方面的進展：（1）在有限域上方程系統求解算法方面，提出了一個二元域上帶噪方程系統的求解算法；給出了一種從代數方程到CNF轉換的高效算法。（2）在利用代數方程求解算法進行密碼分析方面，推進了分組密碼KATAN、PRINCE等的分析；在多變量密碼的分析方面，利用線性化方法分析了MFE改進方案、擴展的多變量公鑰密碼方案、兩層非線性Piece in hand增強方案，用多項式向量的不確定插值方法改進了對SFLASH密碼體制的攻擊；利用線性化方法或格基約化算法分析了一些基于格及背包問題的密碼算法；在代數攻擊中自動推理方法的研究方面，利用解方程組的思想，提出了基于字的分組密碼算法的不可能差分路徑自動化搜索的算法，擴展了Mouha等人基于混合整數線性規劃的方法，給出了一種自動化評估比特級分組密碼抵抗相關密鑰差分攻擊安全性的方法；（3）在利用代數方法設計對稱密碼組件方面，給出了一系列基于線性反饋移位寄存器實現的低代價最優擴散層的構造；否證了C.Carlet于1998年提出的“任何一個AB函數都EA等價于一個置換”的猜想。除以上三方面之外，針對ALE認證加密算法泄露消息沒有受到密鑰保護的特點，提出了一種新的偽造攻擊方法——泄露狀態偽造攻擊。

關鍵詞：代數方程；算法問題；密碼應用

A general report on the study of the project “Algorithmic problems of algebraic equations over finite fields” in 2013

Abstract：This year， our research group， focusing on the key scientific problem of solving algebraic equations over finite fields and its applications in the cryptography， has made the following progress： （1） For solving algebraic equations over finite fields， we proposed an algorithm which can solve systems of polynomial equations with noise over GF（2）， and an efficient method for converting a system of algebraic equations into its conjunction normal form； （2） For the application of algebraic equation solving techniques in the cryptanalysis， we improved the cryptanalysis of block ciphers KATAN， PRINCE， etc.； Also， by employing the linearization technique， we attacked some multivariate public-key cryptosystems such as an improved MFE scheme， the Extended Multivariate Public Key Cryptosystem and a strengthened two-layer Piece in Hand scheme. Moreover， we obtained a more efficient attack on SFLASH with the method of projective interpolation of polynomial vectors and cryptanalyzed some lattice and knapsack based public key schemes using linearization and lattice reduction methods. In addition， by extending Mouha et als methods， we proposed an algorithm for automatic impossible differential path search and automatic security evaluation for bit-oriented ciphers with respect to related-key differential attack. （3） For the application of algebraic methods in designing secure components of block ciphers， we presented a series of low cost diffusion layers which can be implemented using linear shift registers. Whats more， we showed the conjecture proposed by C. Carlet in 1998， stating that every AB function is EA equivalent to a permutation， is not correct. Besides， we proposed a new attack method on the ALE authenticated encryption scheme， the leaked state forgery attack， by exploiting its leaked messages which are not protected by the secret key.

Keywords：algebraic equation；algorithmic problem；general report

閱讀全文鏈接（需實名注冊）：http：//www.nstrs.cn/xiangxiBG.aspx？id=48073&flag=1