Enumeration of 9-variable rotation symmetric Boolean functions having nonlinearity > 240

Kavut S., Maitra S., Sarkar S., YÜCEL M.

7th International Conference on Cryptology in India, Calcutta, Hindistan, 11 - 13 Aralık 2006, cilt.4329, ss.266-268 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 4329
  • Basıldığı Şehir: Calcutta
  • Basıldığı Ülke: Hindistan
  • Sayfa Sayıları: ss.266-268
  • Anahtar Kelimeler: Boolean functions, covering radius, Reed-Muller code, idempotents, nonlinearity, rotational symmetry, Walsh transform, REED-MULLER CODES, COVERING RADIUS, ORPHANS, WEIGHT, COSETS, BENT
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

The existence of 9-variable Boolean functions having nonlinearity strictly greater than 240 has been shown very recently (May 2006) by Kavut, Maitra and Yucel; a few functions with nonlinearity 241 have been identified by a heuristic search in the class of Rotation Symmetric Boolean Functions (RSBFs). In this paper, using combinatorial results related to the Walsh spectra of RSBFs, we efficiently perform the exhaustive search to enumerate the 9-variable RSBFs having nonlinearity > 240 and found that there are 8 x 189 many functions with nonlinearity 241 and there is no RSBF having nonlinearity > 241. We further prove that among these functions, there are only two which are different up to the affine equivalence. This is found by utilizing the binary nonsingular circulant matrices and their variants. Finally we explain the coding theoretic significance of these functions. This is the first time orphan cosets of R(1, n) having minimum weight 241 are demonstrated for n = 9. Further they provide odd weight orphans for n = 9; earlier these were known for certain n > 11.