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

Claude Carlet; Brahim Merabet

doi:10.3934/amc.2013.7.197

Article Contents

2013, Volume 7, Issue 2: 197-217. Doi: 10.3934/amc.2013.7.197

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

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
2.
Department of Algebraic and number theory, University of Sciences and Technology, Houari Boumedienne, Algiers, Algeria, and University of Kasdi Merbah, Ouargla

Received: December 31, 2012

Published: April 2013

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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 "Advances in Cryptology-EUROCRYPT 2006,'' Springer-Verlag, (2006), 147-164.
[2]	C. Carlet, A method of construction of balanced functions with optimum algebraic immunity, in "Proceedings of the International Workshop on Coding and Cryptography,'' World Scientific Publishing Co., 2008.
[3]	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. Hammer), Cambridge Univ. Press, (2010), 257-397.
[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 "Advances in Cryptology-ASIACRYPT 2008,'' Springer-Verlag, (2008), 425-440.
[5]	N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in "Proceedings of Eurocrypt 2003,'' Springer, (2003), 345-359; An extended version is available at http://www.cryptosystem.net/stream/
[6]	D. K. Dalai, K. C. Gupta and S. Maitra, Cryptographically significant Boolean functions: Construction and analysis in terms of algebraic immunity, in "Fast Software Encryption 2005,'' Springer, (2005), 98-111.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-4503.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-252.doi: 10.1007/s10623-008-9228-0.
[9]	R. G. Gallager, "Information Theory and Reliable Communication,'' John Wiley and Sons Inc., New York, 1968.
[10]	M. Liu, Y. Zhang and D. Lin, Perfect algebraic immune functions, in "Advances in Cryptology,'' Springer, (2012), 172-189.
[11]	F. J. Macwilliams And N. J. Sloane, "The theory of Error-Correcting Codes,'' Amsterdam, North Holland, 1977.
[12]	W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in "Advances in Cryptology EUROCRYPT 2004,'' Springer-Verlag, (2004), 474-491.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-1418.doi: 10.1109/18.133259.