New Constructions of Balanced Boolean Functions with Maximum Algebraic Immunity, High Nonlinearity and Optimal Algebraic Degree

Dheeraj Kumar  SHARMA; Rajoo  PANDEY

doi:10.48048/wjst.2020.5999

Authors

Dheeraj Kumar SHARMA Department of Electronics & Communication Engineering, National Institute of Technology Kurukshetra, 136119, India
Rajoo PANDEY Department of Electronics & Communication Engineering, National Institute of Technology Kurukshetra, 136119, India

DOI:

https://doi.org/10.48048/wjst.2020.5999

Keywords:

Boolean function, Nonlinearity, Cyclotomic coset, Algebraic degree, Algebraic immunity

Abstract

This paper consists of proposal of two new constructions of balanced Boolean function achieving a new lower bound of nonlinearity along with high algebraic degree and optimal or highest algebraic immunity. This construction has been made by using representation of Boolean function with primitive elements. Galois Field, used in this representation has been constructed by using powers of primitive element such that greatest common divisor of power and is 1. The constructed balanced variable Boolean functions achieve higher nonlinearity, algebraic degree of , and algebraic immunity of for odd , for even . The nonlinearity of Boolean function obtained in the proposed constructions is better as compared to existing Boolean functions available in the literature without adversely affecting other properties such as balancedness, algebraic degree and algebraic immunity.

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

Author Biographies

Dheeraj Kumar SHARMA, Department of Electronics & Communication Engineering, National Institute of Technology Kurukshetra, 136119, India

Assistant Professor, Electronics and Communication Engineering Department, National Institute of Technology Kurukshetra, India

Rajoo PANDEY, Department of Electronics & Communication Engineering, National Institute of Technology Kurukshetra, 136119, India

Professor, Electronics and Communication Engineering Department, National Institute of Technology Kurukshetra

References

C Carlet. Boolean Functions for Cryptography and Error Correcting Codes. Cambridge University Press, Cambridge, 2010.

C Ding, G Xiao and W Shan. The Stability Theory of Stream Ciphers. In: Lecture Notes in Computer Science, Springer, Heidelberg, 1991, p. 81-125.

W Meier and O Staffelbach. Fast Correlation Attacks on Stream Ciphers. In: Workshop on the Theory and Application of Cryptographic Techniques. Springer, Berlin, 1988, p. 301-14.

S Rønjom and T Helleseth. A new attack on the ﬁlter generator. IEEE T. Inform. Theory 2007; 53, 1752-8.

N Courtois and W Meier. Algebraic attacks on stream ciphers with linear feedback. In: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, 2003, p. 345-59.

W Meier, E Pasalic and C Carlet. Algebraic attacks and decomposition of Boolean functions. In: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, 2004, p. 474-91.

K Verma and D K Sharma. New constructions of Boolean functions using cyclotomic cosets. In: Proceedings of the 2016 International Conference on Emerging Trends in Communication Technologies (ETCT), IEEE, Dehradun, 2016, p. 1-4.

C Carlet and K Feng. An infinite class of balanced functions with optimal algebraic immunity, Good immunity to fast algebraic attacks and good nonlinearity. In: Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, 2008, p. 425-40.

LM Cheng, PD Yi and DY Song. Identification and construction of Boolean functions with maximum algebraic immunity. Sci. China Inform. Sci. 2010; 53, 1379-96.

DY Song and PD Yi. Construction of Boolean functions with maximum algebraic immunity and count of their annihilators at lowest degree. Sci. China Inform. Sci. 2010; 53, 780-7.

F Armknecht. Improving fast algebraic attacks. In: Proceedings of the International Workshop on Fast Software Encryption. Springer, Berlin, 2004, p. 65-82.

NT Courtois. Fast algebraic attacks on stream cipher with linear feedback. In: Proceedings of the Annual International Cryptology Conference. Springer, Berlin, 2003, p. 176-94.

P Rizomiliotis. On the resistance of Boolean functions against algebraic attacks using univariate polynomial representation. IEEE T. Inform. Theory 2010; 56, 4014-24.

P Hawkes and G Rose. Rewriting variables: The complexity of fast algebraic attacks on stream ciphers. In: Proceedings of the Annual International Cryptology Conference. Springer, Berlin, 2004, p. 390-406.

C Carlet, DK Dalai, KC Gupta and S Maitra. Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction. IEEE T. Inform. Theory 2006; 52, 3105-21.

D Tang, C Carlet and X Tang. Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks. IEEE T. Inform. Theory 2013; 59, 653-64.

J Du, S Fu, L Qu, C Li and S Pang. New constructions of q-variable 1-resilient rotation symmetric functions over F_p. Sci. China Inform. Sci. 2016; 59, 1-3.

X Zeng, C Carlet, J Shan and L Hu. More Boolean functions with optimal algebraic immunity and good nonlinearity and resistance to fast algebraic attacks. IEEE T. Inform. Theory. 2011; 57, 6310-20.

G Gao, Y Guo and Y Zhao. Recent result on balanced symmetric Boolean function. IEEE T. Inform. Theory 2016; 62, 5199-203.

R Lidl and H Niederreiter. Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge, 1986.

S Lin and DJ Costello. Error Control Coding. 2nd ed. Pearson Education, New Jersey, 1983.

Q Wang, J Peng, H Kan and X Xue. Construction of cryptographically significant Boolean functions using primitive polynomials. IEEE T. Inform. Theory 2010; 56, 3048-53.

M Liu, Y Zhang and D Liu. Perfect algebraic immune functions. In: Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, 2012, p. 172-89.

P Rizomiliotis. On the security of the Feng-Liao-Yang Boolean functions with optimal algebraic immunity against fast algebraic attacks. Des. Code Cryptogr. 2010; 57, 283-92.

A Braeken and B Preneel. On the algebraic immunity of symmetric Boolean functions. In: Proceedings of the International Conference on Cryptology in India. Springer, Berlin, 2005, p. 35-48.

C Carlet. A method of construction of balanced functions with optimum algebraic immunity. In: Proceedings of the International Workshop on Coding and Cryptology. Wuyishan, China. 2008, p. 25-43.

C Carlet, X Zeng, C Li and L Hu. Further properties of several classes of Boolean functions with optimum algebraic immunity. Des. Code. Cryptogr. 2009; 52, 303-38.

D K Dalai, K C Gupta and S Maitra. Cryptographically signiﬁcant Boolean functions: Construction and analysis in terms of algebraic immunity. In: Proceedings of the International Workshop on Fast Software Encryption. Springer, Berlin, 2005. p. 98-111.

D K Dalai, S Maitra and S Sarkar. Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Code Cryptogr. 2006; 40, 41-58.

N Li and W Qi. Construction and analysis of Boolean functions of 2t+1 variables with maximum algebraic immunity. In: Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, 2006, p. 84-98.

N Li, L Qu, W Qi, G Feng, C Li and D Xie. On the construction of Boolean functions with optimal algebraic immunity. IEEE T. Inform. Theory 2008; 54, 1330-4.

L Qu, K Feng, F Liu and L Wang. Constructing symmetric Boolean functions with maximum algebraic immunity. IEEE T. Inform. Theory 2009; 55, 2406-12.

Z Tu and Y Deng. A conjecture on binary string and its applications on constructing Boolean functions of optimal algebraic immunity. Des. Code Cryptogr. 2011; 60, 1-14.

X Tang, D Tang, X Zeng and L Hu. Balanced Boolean functions with (almost) optimal algebraic immunity and very high nonlinearity. Available at: https://eprint.iacr.org/2010/443.pdf, accessed December 2010.

C Carlet. On a weakness of the Tu-Deng function and its repair. Available at: https://eprint.iacr.org/2009/606.pdf, accessed December 2009.

Q Wang and T Johansson. A note on fast algebraic attacks and higher order nonlinearities. In: Proceedings of the International Conference on Information Security and Cryptology. Springer, Berlin, 2010. p. 84-98.

J Li, C Carlet, X Zeng, C Li, L Hu and J Shan. Two constructions of balanced Boolean functions with optimal algebraic immunity, high nonlinearity and good behavior against fast algebraic attacks. Des. Code Cryptogr. 2015; 76, 279-305.