Milena Stankovic, Claudio Moraga, Radomir S. Stankovic

DOI Number
First page
Last page


Boolean functions expressing some particular properties often appear in engineering practice. Therefore, a lot of research efforts are put into exploring different approaches towards classification of Boolean functions with respect to various criteria that are typically selected to serve some specific needs of the intended applications. A classification is considered to be strong if there is a reasonably small number of different classes for a given number of variables n and it it desir able that classificationrules are simple. A classification with respect to Walsh spectral coefficients, introduced formerly for digital system design purposes, appears to be useful in the context of Boolean functions used in cryptography, since it is ina way compatible with characterization of cryptographically interesting functions through Walsh spectral coefficients. This classification is performed in terms of certain spectral invariant operations. We show by introducing a new spectral invariant operation in the Walsh domain, that by starting from n≤5, some classes of Boolean functions can be merged which makes the classification stronger, and from the theoretical point of view resolves a problem raised already in seventies of the last century. Further, this new spectral invariant operation can be used in constructing bent functions from bent functions represented by quadratic forms.


Boolean functions, classication, Walsh spectrum, invarant operations.

Full Text:



Braeken, A., Borisov, Y., Nikova, S., Preneel, B., ”Classification of Boolean functionsof6variablesorlesswithrespecttocryptographicproperties”, Int.Colloquium on Automata, Languages and Programming ICALP 2005, M. Yung, G.F. Italiano, C. Palamidessi (eds.), Lecture Notes in Computer Science, Vol. 3580, Springer-Verlag, 2005, 324-334.

C. Carlet, P. Sarkar, ”Spectral domain analysis of correlation immune and resilient Boolean functions”, Finite Fields Appl., Vol. 8, 2002, 120-130.

W. Golomb, ”On the classiffication of Boolean functions”, IRE Trans. Circuit Theory, Vol. CT-6, No. 5, May 1959, 176-186.

S.W. Golomb, L.D. Baumert, ”The search for Hadamard matrices”, Amer. Math. Monthly, Vol. 70, 1963, 12-17.

S.W. Golomb, G. Gong, Signal Design for Good Correlation for Wireless Communications, Cryptogtaphy and Radar, Cambridge University Press, 2005.

C.R. Edwards, ”The application of the Rademacher-Walsh transform to Boolean function classification and threshold logic synthesis”, Trans. IEEE, Vol. C-24, 1975, 48-62.

S. L. Hurst, The Logical Processing of Digital Signals, Crane, Russak & Company, Inc., New York, Edward Arnold, London, 1978.

S.L. Hurst, D.M. Miller, J.C. Muzio, Spectral Techniques for Digital Logic, Academic Press, 1985.

M. Karpovsky, R.S. Stankovic, J. Astola, Spectral Logic and Its Applications for the Design of Digital Devices, Wiley, 2008.

R. J. Lechner, ”Harmonic analysis of swiching functions” in A.Mukhopadyay, (Ed.), Recent Developments in Switching Theory, New York, Academic, 1971.

K. Miranovich, ”Spectral analysis of Boolean functions under nonuniformity of arguments”,

O. S. Rothaus, ”On bent functions”, Journal Combinatorial Theory, Vol. 20, No. A, 1976, 300-305.

T. Sasao, Switching Theory for Logic Synthesis, Kluwer Academic Publishers,1999.

P. Sarkar, ”A note on the spectral characterization of Boolean functions”, Inform Process Lett, 74, Vol. 74, 2000, 195.

M. Stankovic, C. Moraga, R.S. Stankovic, ”New spectral invariant operations for functions with disjoint products in the polynomial form”, in Proc. EUROCAST2017, 19-23, February, 2017, Las Palmas, Spain.

Y. Tarannikov, ”Spectral analysis of high order correlation immune functions”, Proc. IEEE Int. Symp. on Information Theory, June 29, 2001.

G.-Z. Xiao, J.L. Massey, ”A spectral characterization of correlation-immune combining functions”, IEEE Trans. on Inform. Theory, Vol. 34, No. 3, 1988, 569-571.


  • There are currently no refbacks.

ISSN: 0353-3670