a new efficient algorithm for computing all low degree annihilators of     sparse polynomials with a high number of variables

	a new efficient algorithm for computing all low degree annihilators of sparse polynomials with a high number of variables
	Xu Lin ; Lin Dongdai ; Li Xin
	2010
会议名称	6th International Conference on Information Security Practice and Experience
会议日期	MAY 12-13,
会议地点	Seoul, SOUTH KOREA
关键词	algebraic attack annihilator algebraic immunity boolean polynomial computational algebra
页码	123-137
英文摘要	Algebraic attacks have proved to be an effective threat to block and stream cipher systems. In the realm of algebraic attacks, there is one major concern that, for a given Boolean polynomial f, if f or f 1 has low degree annihilators. Existing methods for computing all annihilators within degree d of f in n variables, such as Gauss elimination and interpolation, have a complexity based on the parameter k(n,d) = Sigma(d)(i=0) ((n)(i)), which increases dramatically with n. As a result, these methods are impractical when dealing with sparse polynomials with a large n, which widely appear in modern cipher systems. In this paper, we present a new tool for computing annihilators, the characters w.r.t. a Boolean polynomial. We prove that the existence of annihilators of f and f 1 7-esp. relies on the zero characters and the critical characters zu.r.t. f. Then we present a new algorithm for computing annihilators whose complexity relies on lef,d, the number of zero or critical characters within degree d w.r.t.f. Since 16,d << k(n,d) when f is sparse, this algorithm is very efficient for sparse polynomials with a large n. In our experiments, all low degree annihilators of a random balanced sparse polynomial in 256 variables can be found in a few minutes.
会议主办者	Korea Internet & Security Agcy, Elect & Telecommun Res Inst, Korea Inst Informat Security & Cryptography, Korea Commun Commiss
会议录	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
会议录出版者	INFORMATION SECURITY PRACTICE AND EXPERIENCE, PROCEEDINGS
会议录出版地	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
ISSN号	0302-9743
ISBN号	978-3-642-12826-4
内容类型	会议论文
源URL	[http://124.16.136.157/handle/311060/8616]
专题	软件研究所_信息安全国家重点实验室_会议论文
推荐引用方式 GB/T 7714	Xu Lin,Lin Dongdai,Li Xin. a new efficient algorithm for computing all low degree annihilators of sparse polynomials with a high number of variables[C]. 见:6th International Conference on Information Security Practice and Experience. Seoul, SOUTH KOREA. MAY 12-13,.