On Computing the Immunity of Boolean Power Functions Against Fast Algebraic Attacks

详细信息    查看全文

• 关键词：Stream cipher ; Boolean power function ; Algebraic immunity ; Fast algebraic attack
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10157
• 期：1
• 页码：304-316
• 丛书名：Information Security and Cryptology ?ICISC 2016
• ISBN：978-3-319-53177-9
• 卷排序：10157

文摘

The immunity of Boolean functions against fast algebraic attacks (FAA’s) has been considered as an important cryptographic property for Boolean functions used in stream ciphers. An n-variable Boolean power function f can be represented as a monomial trace function over finite field \(\mathbb {F}_{2^n}\), \(f(x)=Tr_1^n(\lambda x^k)\), where \(\lambda \in \mathbb {F}_{2^n}\) and k is the coset leader of cyclotomic coset \(C_k\) modulo \(2^n-1\). To determine the immunity of Boolean power functions, one may need the arithmetic in \(\mathbb {F}_{2^n}\), which is not computationally efficient compared with the operations over \(\mathbb {F}_2\). In this paper, we show that the linear (affine) invariance of the immunity of Boolean functions against FAA’s can be exploited to observe the immunity of Boolean power functions against FAA’s, i.e., the immunity of \(f(x)=Tr_1^n(\lambda x^k)\) against FAA’s is the same as that of \(r(x)=Tr_1^n(x^k)\) if f(x) can be obtained from r(x) through a linear transformation. In particular, if \(\gcd (k,2^n-1)=1\) then the immunity against FAA’s of f(x) and that of r(x) are always the same. The immunity of Boolean power functions that satisfy this condition can be computed more efficiently.