On Propagation Criteria of Some Classes of Boolean Functions

Gleb Isaev


The denition of the propagation criterion of Boolean functions was introduced by Bart Preneel and co-authors. This concept represent a set of vectors, for which the corresponding derivatives of a Boolean function are balanced.  It characterizes the statistical properties of a family of Boolean function  derivatives that play an important role in the cryptosystem analysis and  synthesis. For some classes of Boolean functions, the propagation criterion  determines their extreme properties. For example, the propagation criterion of bent functions determines their maximum nonlinearity. However, the main disadvantage of bent functions is the lack of balancedness, which means that  such functions do not have a uniform output distribution. The construction of  balanced Boolean functions having a high nonlinearity and a large number of  vectors satisfying the propagation criterion is still an open problem in  cryptography. In this paper we obtain exact values and estimates of the number  of vectors satisfying the propagation criterion of Boolean functions from well- known cryptographic classes, such as plateaued functions, Maiorana-McFarland  functions, quadratic functions, algebraic degenerate functions and multiane  functions. We also show that the number of vectors satisfying the propagation  criterion is an invariant for the extension of the general affine group of the first  degree. 

Full Text:

PDF (Russian)


O.A. Logachev, A.A. Salnikov., S.V. Smyshlyaev, V.V. Yashchenko. Boolean Functions in Coding Theory and Cryptography Moscow, URSS, 2015, 583 p. [in Russian].

V.V. Yashchenko. On Propagation Criterion of Boolean Functions and Bent-Functions Probl. Peredachi Inf., Volume 33, Issue 1, 7586 pp., 1997 [in Russian].

I.A. Pankratova. Boolean Functions in Cryptography¿ Tomsk. Gos. Univ., Tomsk, 88 p., 2014 [in Russian].

B. Preneel. Analysis and Design of Cryptographic Hash Functions PhD thesis, Katholiek Universiteit Leuven 242-245 pp., 2003.

B. Preneel, W. Van Leekwijck, L. Van Linden, R. Govaerts, J. Vandewalle. Propagation characteristics of Boolean functions¿ Advances in Cryptology EUROCRYPT'90, Lecture Notes in Computer Science, V. 437, Springer-Verlag, Berlin, Heidelberg, New-York, 155165 pp., 1990.

A. Canteaut, C. Carlet, P. Charpin, C. Fontaine. ropagation Characteristics and Correlation-Immunity of Highly Nonlinear Boolean Functions Lecture Notes in Computer Science, 1807, 16 p., 2000.

J. Seberry, X.M. Zhang, Y. Zheng. Nonlinearity and Propagation Characteristics of Balanced Boolean Functions¿ Crypto'93 Advances in Cryptography, 773, Lecture Notes in Computer Science, SpringerVerlag, Berlin, 29 p., 1994.

Y. Zheng, X.M. Zhang. On Relationships among Avalanche, Nonlinearity, and Correlation Immunity Advances in Cryptology ASIACRYPT 2000, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 13 p., 1976 (2000).

O.S. Rothaus. On Bent Functions Journal of Combinatorial Theory (A), V. 20, No. 3, 300-305 pp., 1976.

R.J. McEliece. Weight congruences for p-ary cyclic codes Discrete Mathematics, V. 3, 177-192 pp., 1972.

F.J. MacWilliams, N.J.A. Sloane. The Theory of Error-Correcting Codes¿ Amsterdam, New York, Oxford: North-Holland Publishing Company, 1977.

A.F. Webster, S.E. Tavares. On the design of S-boxes Crypto'85 Advances in Cryptology, 219, Lecture Notes in Computer Science, Springer-Verlag, 523534 pp., 1985.

R.L. McFarland. A Family of Dierence Sets in Noncyclic Groups¿ Journal of Combinatorial Theory (A), V. 15, No. 1, 1-10 pp., 1973. 24


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162