有限域上代数方程算法问题研究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