On Annihilators in Fewer Variables： Basic Theory and Applications  

作　　者：JIAO Lin WANG Mingsheng LI Yongqiang LIU Meicheng 

机构地区：[1]Institute of Software, Chinese Academy of Sciences, Beijing 100190, China [2]Graduate University of Chinese Academy of Sciences, Beijing 100049, China [3]State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

出　　处：《Chinese Journal of Electronics》2013年第3期489-494,共6页电子学报（英文版）

基　　金：This work is supported by the National Natural Science Foundation of China （No.60970134, No.11171323）, the IIE＇s Cryptography Research Project （No.Y2Z0011102）, and the Strategic Priority Research Program of the Chinese Academy of Sciences （No.XDA06010701）.

摘　　要：Algebraic attacks on stream ciphers exploit annihilators of low degree. From another point of view, we concentrate on annihilators in fewer variables in this paper. This work consists of two parts. Firstly, the concept of singular annihilators is proposed and the basic theory is established. Secondly we present two applications of singular annihilators. We propose a variant of the Filter states guessing attack （FSGA） introduced by Pasalic （2009）. Our attack outperforms the FSGA in many cases. Moreover, we put forward a probabilistic algorithm, which can screen out a large number of Boolean functions with annihilators of low degree at a lower cost for the resistance against algebraic attacks.

关 键 词：ANNIHILATOR Algebraic attack Boolean function Stream cipher Filter states guessing attack （FSGA）. 

分 类 号：O241.82[理学—计算数学] TP317[理学—数学]