Counting Boolean functions with specified values in their Walsh spectrum

Uyan E., Calik C., DOĞANAKSOY A.

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, cilt.259, ss.522-528, 2014 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 259
  • Basım Tarihi: 2014
  • Doi Numarası: 10.1016/j.cam.2013.06.035
  • Dergi Adı: JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.522-528
  • Anahtar Kelimeler: Boolean functions, Walsh spectrum, Counting
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

The problem of counting Boolean functions with specified number s of Walsh coefficients omega in their Walsh spectrum is discussed in this paper. Strategies to solve this problem shall help solving many more problems related to desired cryptographic features of Boolean functions such as nonlinearity, resiliency, algebraic immunity, etc. In an attempt to study this problem, we present a new framework of solutions. We give results for vertical bar omega vertical bar >= 2(n-1) and for all s, in line with a previous work of Wu (1998) [12]. We also provide various results such as existence and construction for some s when omega = 0, multiplicities for all omega and naive bounds on s for omega > 2(n/2). (C) 2013 Elsevier B.V. All rights reserved.