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

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

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.
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.

[2]

C. Carlet, A method of construction of balanced functions with optimum algebraic immunity,, in, (2008).

[3]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in, (2010), 257.

[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.

[5]

N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback,, in, (2003), 345.

[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.

[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.

[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.

[9]

R. G. Gallager, "Information Theory and Reliable Communication,'', John Wiley and Sons Inc., (1968).

[10]

M. Liu, Y. Zhang and D. Lin, Perfect algebraic immune functions,, in, (2012), 172.

[11]

F. J. Macwilliams And N. J. Sloane, "The theory of Error-Correcting Codes,'', Amsterdam, (1977).

[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.

[13]

V. K. Wei, Generalized Hamming weights for linear codes,, IEEE Trans. Inform. Theory, 37 (1991), 1412. doi: 10.1109/18.133259.

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.

[2]

C. Carlet, A method of construction of balanced functions with optimum algebraic immunity,, in, (2008).

[3]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in, (2010), 257.

[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.

[5]

N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback,, in, (2003), 345.

[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.

[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.

[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.

[9]

R. G. Gallager, "Information Theory and Reliable Communication,'', John Wiley and Sons Inc., (1968).

[10]

M. Liu, Y. Zhang and D. Lin, Perfect algebraic immune functions,, in, (2012), 172.

[11]

F. J. Macwilliams And N. J. Sloane, "The theory of Error-Correcting Codes,'', Amsterdam, (1977).

[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.

[13]

V. K. Wei, Generalized Hamming weights for linear codes,, IEEE Trans. Inform. Theory, 37 (1991), 1412. doi: 10.1109/18.133259.

[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]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[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]

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

[14]

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

[15]

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

[16]

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

[17]

Claude Carlet, Juan Carlos Ku-Cauich, Horacio Tapia-Recillas. Bent functions on a Galois ring and systematic authentication codes. Advances in Mathematics of Communications, 2012, 6 (2) : 249-258. doi: 10.3934/amc.2012.6.249

[18]

Shingo Takeuchi. The basis property of generalized Jacobian elliptic functions. Communications on Pure & Applied Analysis, 2014, 13 (6) : 2675-2692. doi: 10.3934/cpaa.2014.13.2675

[19]

Limin Wen, Xianyi Wu, Xiaobing Zhao. The credibility premiums under generalized weighted loss functions. Journal of Industrial & Management Optimization, 2009, 5 (4) : 893-910. doi: 10.3934/jimo.2009.5.893

[20]

Mihaela Roxana Nicolai, Dan Tiba. Implicit functions and parametrizations in dimension three: Generalized solutions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (6) : 2701-2710. doi: 10.3934/dcds.2015.35.2701

2016 Impact Factor: 0.8

Metrics

  • PDF downloads (0)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]