A Note on the Optimal Immunity of Boolean Functions Against Fast Algebraic Attacks
The immunity of Boolean functions against fast algebraic attacks is an important cryptographic property. When deciding the optimal immunity of an n-variable Boolean function against fast algebraic attacks, one may need to compute the ranks of a series of
- PDF / 222,885 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 208 Views
Guangdong College of Industry and Commerce, Guangzhou 510510, China 2 School of Information Management, Sun Yat-sen University, Guangzhou 510006, China [email protected]
Abstract. The immunity of Boolean functions against fast algebraic attacks is an important cryptographic property. When deciding the optimal immunity of an n-variable Boolean function against fast algebraic attacks, need ncompute the ranks of a series of matrices of e to one may n × size n i=d+1 i i=0 i over binary field F2 for each positive integer e less than n2 and corresponding d. In this paper, for an n-variable balanced Boolean function, exploiting the combinatorial properties of the binomial coefficients, when n is odd, we show that the optimal immunity is only determined by the ranks of those matrices such that ei=0 ni is even. When n is even but not the power of 2, we show that the optimal immunity matrices nof those n such that e+1 e n is only determined by theranks e i=0 i is even or such that both i=0 i and i=0 i are odd. Keywords: Boolean function immunity
1
·
Fast algebraic attack
·
Algebraic
Introduction
Boolean functions play a vital role in coding theory and in symmetric cryptography [8]. Various criteria related to cryptographically desirable Boolean functions have been proposed. Boolean functions used in stream ciphers, especially in the filer and combination generators of stream ciphers based on linear feedback shift registers, should have large algebraic immunity, in order to help resist algebraic attacks [3,6,14]. Moreover, Boolean functions should also have the resistance against a variant of the algebraic attack, called the fast algebraic attack (FAA) [1,5,7]. To a certain degree the algebraic immunity can be covered by the immunity of Boolean functions against fast algebraic attacks (FAA’s). Algebraic immunity, as well as This work is supported by National Natural Science Foundations of China (Grant No. 61309028, Grant No. 61472457, Grant No. 61502113), Science and Technology Planning Project of Guangdong Province, China (Grant No. 2014A010103017), and Natural Science Foundation of Guangdong Province, China (Grant No. 2016A030313298). c Springer Nature Singapore Pte Ltd. 2017 D. Giri et al. (Eds.): ICMC 2017, CCIS 655, pp. 57–67, 2017. DOI: 10.1007/978-981-10-4642-1 6
58
J. Shen and Y. Du
the immunity against FAA’s, has been considered as a important cryptographic property for Boolean functions used in stream ciphers [10,11,15,16,19]. Studies show that a good immunity for an n-variable function f against FAA’s is that deg(f g) > d for any nonzero n-variable Boolean function g of algebraic degree at most e, where 1 ≤ e < n2 and d is as large as possible but less than n − e, such as d = n − e − 1, d = n − e − 2 or d = n − e − 3 [2,10,13,15]. In particular, if deg(f g) ≥ n−e for any nonzero n-variable Boolean function g of degree at most e and any positive integer e < n/2, then we say that Boolean function f has the optimal immunity against fast algebraic attacks. When consider
Data Loading...
