New extremal binary self-dual codes of length $68$ from $R_2$-lifts of binary self-dual codes
AMC Home
Discrete logarithm like problems and linear recurring sequences
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,
LAGA, Universities of Paris 8 and Paris 13, CNRS, France
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
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. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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/ Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
R. G. Gallager, "Information Theory and Reliable Communication,'' John Wiley and Sons Inc., New York, 1968. Google Scholar
M. Liu, Y. Zhang and D. Lin, Perfect algebraic immune functions, in "Advances in Cryptology,'' Springer, (2012), 172-189. Google Scholar
F. J. Macwilliams And N. J. Sloane, "The theory of Error-Correcting Codes,'' Amsterdam, North Holland, 1977. Google Scholar
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. Google Scholar
V. K. Wei, Generalized Hamming weights for linear codes, IEEE Trans. Inform. Theory, 37 (1991), 1412-1418. doi: 10.1109/18.133259. Google Scholar
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
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
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
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
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
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
SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010
Deng Tang. A note on the fast algebraic immunity and its consequences on modified majority functions. Advances in Mathematics of Communications, 2020, 14 (1) : 111-125. doi: 10.3934/amc.2020009
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
Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
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
Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069
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
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
Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021031
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
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
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
Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020121
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
Claude Carlet Brahim Merabet