American Institute of Mathematical Sciences

Advanced
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

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]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[2]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117
[3]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[4]

Ville Salo, Ilkka Törmä. Recoding Lie algebraic subshifts. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 1005-1021. doi: 10.3934/dcds.2020307
[5]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[6]

Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167
[7]

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345
[8]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346
[9]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171
[10]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319
[11]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363
[12]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445
[13]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences