Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

 Citation:

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