Fast algebraic immunity of Boolean functions

Sihem Mesnager; Gérard Cohen

doi:10.3934/amc.2017031

Article Contents

2017, Volume 11, Issue 2: 373-377. Doi: 10.3934/amc.2017031

This issue Previous Article A multi-dimensional block-circulant perfect array construction Next Article On parameters of subfield subcodes of extended norm-trace codes

Fast algebraic immunity of Boolean functions

Sihem Mesnager^1, and
Gérard Cohen^2,

1.
Department of Mathematics, University of Paris Ⅷ and Paris ⅩⅢ and Télécom ParisTech, LAGA, UMR 7539, CNRS, Sorbonne Paris Cité
2.
Télécom ParisTech, department INFRES/MIC2, CNRS, UMR 5441

Received: February 2016

Revised: March 2016

Published: September 2017

Abstract Full Text(HTML) Related Papers Cited by

Abstract

Since 1970, Boolean functions have been the focus of a lot of attention in cryptography. An important topic in symmetric ciphers concerns the cryptographic properties of Boolean functions and constructions of Boolean functions with good cryptographic properties, that is, good resistance to known attacks. An important progress in cryptanalysis areas made in 2003 was the introduction by Courtois and Meier of algebraic attacks and fast algebraic attacks which are very powerful analysis concepts and can be applied to almost all cryptographic algorithms. To study the resistance against algebraic attacks, the notion of algebraic immunity has been introduced. In this paper, we use a parameter introduced by Liu and al., called fast algebraic immunity, as a tool to measure the resistance of a cryptosystem (involving Boolean functions) to fast algebraic attacks. We prove an upper bound on the fast algebraic immunity. Using our upper bound, we establish the weakness of trace inverse functions against fast algebraic attacks confirming a recent result of Feng and Gong.

Keywords:

Mathematics Subject Classification: 12K10, 94A60.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

	C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering (eds. Y. Crama and P. L. Hammer), Cambridge Univ. Press, 2010,257-397. doi: 10.1017/CBO9780511780448.
	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 Adv. Crypt. -ASIACRYPT 2008, Springer, 2008,425-440. doi: 10.1007/978-3-540-89255-7_26.
	C. Carlet and D. Tang , Enhanced Boolean functions suitable for the filter model of pseudo-random generator, Des. Codes Crypt., 76 (2015) , 571-587. doi: 10.1007/s10623-014-9978-9.
	N. Courtois, Fast algebraic attacks on stream ciphers with linear feedback, Advances in Cryptology-CRYPTO 2003, Springer, 2003,177-194. doi: 10.1007/978-3-540-45146-4_11.
	N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology, Springer, 2002,346-359. doi: 10.1007/3-540-39200-9_21.
	Y. Du, F. Zhang and M. Liu, On the resistance of Boolean functions against fast algebraic attacks, in ICISC 2011, Springer, 2012,261-274. doi: 10.1007/978-3-642-31912-9_18.
	X. Feng and G. Gong, On algebraic immunity of trace inverse functions over finite fields with characteristic two, Cryptology ePrint Archive: Report 2013/585.
	M. Liu , D. Lin and D. Pei , Fast algebraic attacks and decomposition of symmetric Boolean functions, IEEE Trans. Inf. Theory, 57 (2011) , 4817-4821. doi: 10.1109/TIT.2011.2145690.
	W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in Eurocrypt 2004, Springer, 2004,474-491. doi: 10.1007/978-3-540-24676-3_28.
	Y. Nawaz, G. Gong and K. C. Gupta, Upper bounds on algebraic immunity of Boolean power functions, in 13th Int. Workshop Fast Softw. Encrypt., Springer, 2006,375-389.
	K. Nyberg, Differentially uniform mappings for cryptography, in Eurocrypt 1993, Springer, 1994, 55-64. doi: 10.1007/3-540-48285-7_6.
	E. Pasalic, Almost fully optimized infinite classes of Boolean functions resistant to (fast) algebraic cryptanalysis, in ICISC 2008, Springer, 2008,399-414. doi: 10.1007/978-3-642-00730-9_25.
	C. Shannon , Communication theory of secrecy systems, Bell Syst. Techn. J., 28 (1949) , 656-715. doi: 10.1002/j.1538-7305.1949.tb00928.x.