Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions

Previous Article
Discrete logarithm like problems and linear recurring sequences
AMC Home
This Issue
Next Article
New extremal binary self-dual codes of length $68$ from $R_2$-lifts of binary self-dual codes

May 2013, 7(2): 197-217. doi: 10.3934/amc.2013.7.197

Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions

Claude Carlet ^1, and Brahim Merabet ^2,

1.	LAGA, Universities of Paris 8 and Paris 13, CNRS, France
2.	Department of Algebraic and number theory, University of Sciences and Technology, Houari Boumedienne, Algiers, Algeria, and University of Kasdi Merbah, Ouargla, Algeria

Received January 2013 Published May 2013

Abstract
Related Papers

This paper extends the work of F. Didier (IEEE Transactions on Information Theory, Vol. 52(10): 4496-4503, October 2006) on the algebraic immunity of random balanced Boolean functions, into an asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions.

Keywords: Reed-Muller codes, algebraic immunity., Boolean functions, erasure channel, vectorial functions, generalized Hamming distances.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.

Citation: Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197

References:

[1]	F. Armknecht, C. Carlet, P. Gaborit, S. Kunzli, W. Meier and O. Ruatta, Efficient computation of algebraic immunity for algebraic and fast algebraic attacks,, in, (2006), 147. Google Scholar
[2]	C. Carlet, A method of construction of balanced functions with optimum algebraic immunity,, in, (2008). Google Scholar
[3]	C. Carlet, Boolean functions for cryptography and error correcting codes,, in, (2010), 257. Google Scholar
[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, (2008), 425. Google Scholar
[5]	N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback,, in, (2003), 345. Google Scholar
[6]	D. K. Dalai, K. C. Gupta and S. Maitra, Cryptographically significant Boolean functions: Construction and analysis in terms of algebraic immunity,, in, (2005), 98. doi: 10.1007/11502760_7. Google Scholar
[7]	F. Didier, A new bound on the block error probability after decoding over the erasure channel,, IEEE Trans. Inform. Theory, 52 (2006), 4496. doi: 10.1109/TIT.2006.881719. Google Scholar
[8]	K. Feng, Q. Liao and J. Yang, Maximal values of generalized algebraic immunity,, Des. Codes Crypt., 50 (2009), 243. doi: 10.1007/s10623-008-9228-0. Google Scholar
[9]	R. G. Gallager, "Information Theory and Reliable Communication,'', John Wiley and Sons Inc., (1968). Google Scholar
[10]	M. Liu, Y. Zhang and D. Lin, Perfect algebraic immune functions,, in, (2012), 172. Google Scholar
[11]	F. J. Macwilliams And N. J. Sloane, "The theory of Error-Correcting Codes,'', Amsterdam, (1977). Google Scholar
[12]	W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions,, in, (2004), 474. doi: 10.1007/978-3-540-24676-3_28. Google Scholar
[13]	V. K. Wei, Generalized Hamming weights for linear codes,, IEEE Trans. Inform. Theory, 37 (1991), 1412. doi: 10.1109/18.133259. Google Scholar

show all references

References:

[1]	F. Armknecht, C. Carlet, P. Gaborit, S. Kunzli, W. Meier and O. Ruatta, Efficient computation of algebraic immunity for algebraic and fast algebraic attacks,, in, (2006), 147. Google Scholar
[2]	C. Carlet, A method of construction of balanced functions with optimum algebraic immunity,, in, (2008). Google Scholar
[3]	C. Carlet, Boolean functions for cryptography and error correcting codes,, in, (2010), 257. Google Scholar
[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, (2008), 425. Google Scholar
[5]	N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback,, in, (2003), 345. Google Scholar
[6]	D. K. Dalai, K. C. Gupta and S. Maitra, Cryptographically significant Boolean functions: Construction and analysis in terms of algebraic immunity,, in, (2005), 98. doi: 10.1007/11502760_7. Google Scholar
[7]	F. Didier, A new bound on the block error probability after decoding over the erasure channel,, IEEE Trans. Inform. Theory, 52 (2006), 4496. doi: 10.1109/TIT.2006.881719. Google Scholar
[8]	K. Feng, Q. Liao and J. Yang, Maximal values of generalized algebraic immunity,, Des. Codes Crypt., 50 (2009), 243. doi: 10.1007/s10623-008-9228-0. Google Scholar
[9]	R. G. Gallager, "Information Theory and Reliable Communication,'', John Wiley and Sons Inc., (1968). Google Scholar
[10]	M. Liu, Y. Zhang and D. Lin, Perfect algebraic immune functions,, in, (2012), 172. Google Scholar
[11]	F. J. Macwilliams And N. J. Sloane, "The theory of Error-Correcting Codes,'', Amsterdam, (1977). Google Scholar
[12]	W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions,, in, (2004), 474. doi: 10.1007/978-3-540-24676-3_28. Google Scholar
[13]	V. K. Wei, Generalized Hamming weights for linear codes,, IEEE Trans. Inform. Theory, 37 (1991), 1412. doi: 10.1109/18.133259. Google Scholar

[1]	Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[2]	Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031
[3]	Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[4]	Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021
[5]	Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048
[6]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[7]	Sara D. Cardell, Joan-Josep Climent. An approach to the performance of SPC product codes on the erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 11-28. doi: 10.3934/amc.2016.10.11
[8]	Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
[9]	Claude Carlet, Serge Feukoua. Three basic questions on Boolean functions. Advances in Mathematics of Communications, 2017, 11 (4) : 837-855. doi: 10.3934/amc.2017061
[10]	Carolyn Mayer, Kathryn Haymaker, Christine A. Kelley. Channel decomposition for multilevel codes over multilevel and partial erasure channels. Advances in Mathematics of Communications, 2018, 12 (1) : 151-168. doi: 10.3934/amc.2018010
[11]	Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179
[12]	David Keyes. $\mathbb F_p$-codes, theta functions and the Hamming weight MacWilliams identity. Advances in Mathematics of Communications, 2012, 6 (4) : 401-418. doi: 10.3934/amc.2012.6.401
[13]	Yang Yang, Xiaohu Tang, Guang Gong. Even periodic and odd periodic complementary sequence pairs from generalized Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 113-125. doi: 10.3934/amc.2013.7.113
[14]	Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201
[15]	Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057
[16]	Ayça Çeşmelioğlu, Wilfried Meidl. Bent and vectorial bent functions, partial difference sets, and strongly regular graphs. Advances in Mathematics of Communications, 2018, 12 (4) : 691-705. doi: 10.3934/amc.2018041
[17]	Yu Zhou. On the distribution of auto-correlation value of balanced Boolean functions. Advances in Mathematics of Communications, 2013, 7 (3) : 335-347. doi: 10.3934/amc.2013.7.335
[18]	JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003
[19]	Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006
[20]	Sihong Su. A new construction of rotation symmetric bent functions with maximal algebraic degree. Advances in Mathematics of Communications, 2019, 13 (2) : 253-265. doi: 10.3934/amc.2019017

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences