English version:
Journal of Applied and Industrial Mathematics, 2016, 10:2, 257-263

Volume 23, No 2, 2016, P. 88-99

UDC 519.7
D. P. Pokrasenko
On the maximal component algebraic immunity of vectorial Boolean functions

The component algebraic immunity of vectorial Boolean functions is studied. We prove a theorem on the correspondence between the maximum component algebraic immunity of a function and its balancedness. Some relationship between the maximal component algebraic immunity and matrices of a special form is obtained. We construct several functions with maximal component algebraic immunity in case of few variables.
Tab. 1, bibliogr. 8.

Keywords: component algebraic immunity, vectorial Boolean function, balancedness.

DOI: 10.17377/daio.2016.23.495

Denis P. Pokrasenko 1
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: pokrasenko.d.p@gmail.com

Received 29 May 2015
Revised 8 December 2015


[1] F. Armknecht and M. Krause, Constructing single- and multi-output Boolean functions with maximal algebraic immunity, in Automata, Languages and Programming (Proc. 33rd Int. Colloq. ALP, Venice, Italy, July 10–14, 2006), Pt. II, pp. 180–191, Springer, Heidelberg, 2006 (Lect. Notes Comput. Sci., Vol. 4052).

[2] G. Ars and J.-C. Faugère, Algebraic immunities of functions over finite fields, in Boolean Functions: Cryptography and Applications (Proc. 1st Workshop BFCA, Mont Saint-Aignan, France, Mar. 7–8, 2005), pp. 21–38, Publ. Univ. Rouen Havre, Mont Saint-Aignan, 2005.

[3] C. Carlet, On the algebraic immunities and higher order nonlinearities of vectorial Boolean functions, in Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes (Proc. NATO Adv. Res. Workshop ACPTECC, Veliko Tarnovo, Bulgaria, Oct. 6–9, 2008), pp. 104–116, IOS Press, Amsterdam, 2009.

[4] N. T. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in E. Biham, ed., Advances in Cryptology — EUROCRYPT 2003 (Proc. Int. Conf. Theory Appl. Cryptogr. Tech., Warsaw, Poland, May 4–8, 2003), pp. 345–359, Springer, Heidelberg, 2003 (Lect. Notes Comput. Sci., Vol. 2656).

[5] D. K. Dalai, K. C. Gupta, and S. Maitra, Results on algebraic immunity for cryptographically significant Boolean functions, in A. Canteaut and K. Viswanathan, eds., Progress in Cryptology — INDOCRYPT 2004 (Proc. 5th Int. Conf. Cryptol. India, Chennai, India, Dec. 20–22, 2004), pp. 92–106, Springer, Heidelberg, 2005 (Lect. Notes Comput. Sci., Vol. 3348).

[6] K. Feng, Q. Liao and J. Yang, Maximal values of generalized algebraic immunity, Des. Codes Cryptogr., 50, No. 2, 243–252, 2009.

[7] R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, Reading, MA, USA, 1983.

[8] W.Meier, E. Pasalic, and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in C. Cachin and J. L. Camenisch, eds., Advances in Cryptology — EUROCRYPT 2004 (Proc. Int. Conf. Theory Appl. Cryptogr. Tech., Interlaken, Switzerland, May 2–6, 2004), pp. 474–491, Springer, Berlin, 2005 (Lect. Notes Comput. Sci., Vol. 3027).
 © Sobolev Institute of Mathematics, 2015