Special Issue – CryptographyNo Access

LOWER BOUNDS ON THE SECOND ORDER NONLINEARITY OF BOOLEAN FUNCTIONS

Department of Mathematics, Xidian University, Post Box 95, Xi'an, Shannxi, 710071, China

Key Laboratory of Computer Networks and Information Security, Ministry of Education, Xidian University, Xi'an, Shannxi, 710071, China

Search for more papers by this author

, and

JUNTAO GAO

Key Laboratory of Computer Networks and Information Security, Ministry of Education, Xidian University, Xi'an, Shannxi, 710071, China

State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China

Search for more papers by this author

https://doi.org/10.1142/S012905411100874XCited by:7 (Source: Crossref)

Abstract

It is a difficult task to compute the r-th order nonlinearity of a given function with algebraic degree strictly greater than r > 1. Though lower bounds on the second order nonlinearity are known only for a few particular functions, the majority of which are cubic. We investigate lower bounds on the second order nonlinearity of cubic Boolean functions , where , d_l = 2^il + 2^jl + 1, m, i_l and j_l are positive integers, n > i_l > j_l. Furthermore, for a class of Boolean functions we deduce a tighter lower bound on the second order nonlinearity of the functions, where , d_l = 2^i_lγ + 2^j_lγ + 1, i_l > j_l and γ ≠ 1 is a positive integer such that gcd(n,γ) = 1.

Lower bounds on the second order nonlinearity of cubic monomial Boolean functions, represented by f_μ(x) = Tr(μx^{2ⁱ+2^j+1}), , i and j are positive integers such that i > j, were obtained by Gode and Gangopadhvay in 2009. In this paper, we first extend the results of Gode and Gangopadhvay from monomial Boolean functions to Boolean functions with more trace terms. We further generalize and improve the results to a wider range of n. Our bounds are better than those of Gode and Gangopadhvay for monomial functions f_μ(x). Especially, our lower bounds on the second order nonlinearity of some Boolean functions F(x) are better than the existing ones.

Keywords:

References

C. Brackenet al., Determining the Nonlinearity of a New Family of APN Functions, Proc. AAECC, Lecture Notes in Computer Science 4851 (Springer, Bangalore, India, 2007) pp. 72–79. Google Scholar
A. Canteaut, P. Charpin and G. M. Kyureghyan, Finite Fields and Their Applications 14, 221 (2008). Crossref, Web of Science, Google Scholar
C. Carlet, On the higher order nonlinearities of algebraic immune functions, Advances in Cryptology C CRYPTO 2006, LNCS 4117 (Springer-Verlag, 2006) pp. 584–601. Google Scholar
C. Carletet al., IEEE Trans. Information Theory 52(7), 3105 (2006), DOI: 10.1109/TIT.2006.876253. Crossref, Web of Science, Google Scholar
C. Carlet, IEEE Trans. Information Theory 54(3), 1262 (2008), DOI: 10.1109/TIT.2007.915704. Crossref, Web of Science, Google Scholar
G. Cohen et al. (eds.) , Covering Codes ( North-Holland , Amsterdam, The Netherlands , 1977 ) . Google Scholar
I. Dumer, G. Kabatiansky and C. Tavernier, List decoding of second order Reed-Muller codes up to the Johnson bound with almost linear complexity, Proc. IEEE Int. Symp. Information Theory In ISIT 2006 pp. 38–142. Google Scholar
R. Fourquet and C. Tavernier, List decoding of second order Reed-Muller codes and its covering radius implications, WCC 2007 pp. 147–156. Google Scholar
S. Gangopadhyay, S. Sarkar and R. Telang, Information Sciences 180(2), 266 (2010), DOI: 10.1016/j.ins.2009.09.006. Crossref, Web of Science, Google Scholar
R. Gode, S. Gangopadhyay, On second order nonlinearities of cubic monomial Boolean functions , http://eprint.iacr.org/2009/502.pdf . Google Scholar
R. Gode, S. Gangopadhyay, On lower bounds of second-order nonlinearities of cubic bent functions constructed by concatenation Gold functions , http://eprint.iacr.org/2010/258.pdf . Google Scholar
M. Hell, T. Johansson and W. Meier, International Journal of Wireless and Mobile Computing 2(1), 86 (2007), DOI: 10.1504/IJWMC.2007.013798. Crossref, Web of Science, Google Scholar
M. Hellet al., A Stream Cipher Proposal: Grain-128, Proc. IEEE Int. Symp. Information Theory In ISIT 2006 pp. 1614–1618. Google Scholar
G. Kabatiansky and C. Tavernier , List decoding of second order Reed-Muller codes , 8th International Symposium of Communication theory and Applications . Google Scholar
R. Lidl and H. Niederreiter (eds.) , Finite fields ( Combridge Univ. Press , Cambridge, U.K , 1983 ) . Google Scholar
V. S. Pless and W. C. Huffman (eds.) , Handbook of coding theory ( Elsevier , Amsterdam , 1998 ) . Google Scholar
W. G. Solomn and G. Guang (eds.), Signal Design for Good Correlation for Wireless Communication, Cryptography, and Radar (Cambridge Univ. Press, Cambridge, New York, 2005) pp. 42–45. Google Scholar
G. Sun and C. Wu, Information Sciences 179(3), 267 (2009), DOI: 10.1016/j.ins.2009.01.040. Crossref, Web of Science, Google Scholar