(1057, 31)-Aralıklı Dizilerden Üretilen Boole Fonksiyonlar

1983 yılında keşfedildikten itibaren günümüzde halen bilinen en yüksek doğrusal olmama değerine (16276) sahip olan 15-değişkenli Patterson-Wiedemann (PW) fonksiyonlarının, özel bir yapıda bulunan (151, 217)-aralıklı dizilerden üretilen döngüsel simetrik Boole fonksiyonları (DSBF’ler) olarak yorumlanabildiği bilinmektedir. İlgili literatürde, aynı doğrusal olmama değerine ulaşan başka bir inşa/arama yöntemi bilinmemekle birlikte, tam arama veya sezgisel arama yöntemleri ile (151, 217)- ve (217, 151)-aralıklı dizilerden, bükük-bağlaşım sınırını (16256) aşan doğrusal olmama değerine sahip genelleştirilmiş DSBF’lerin elde edilebildiği gösterilmiştir. Ancak, bahsedilen yöntemlerle ulaşılan en iyi doğrusal olmama değeri 16268’i aşamamıştır. Bu çalışmamızda, bildiğimiz kadarıyla ilk defa (1057, 31)-aralıklı dizilerden üretilen DSBF’ler araştırılmış ve sezgisel arama yöntemi ile 16272 doğrusal olmama değerine ulaşılmıştır.

Anahtar Kelimeler:

Aralıklı dizi, bükük-bağlaşım sınırı, döngüsel simetrik Boole fonksiyonu (DSBF), doğrusal olmama

Boolean Functions Generated from (1057, 31)-Interleaved Sequences

It is known that Patterson-Wiedemann (PW) functions with 15-variables, which still have the highest known nonlinearity value (16276) since their discovery in 1983, can be interpreted as rotation-symmetric Boolean functions (RSBFs) produced from (151, 217)-interleaved sequences which are in the form of a special structure. In the related literature, though no other search/construction method achieving the same nonlinearity value is known, it has been shown that generalized RSBFs with nonlinearity exceeding the bent-concatenation bound (16256) can be obtained from (151, 217)- and (217, 151)-interleaved sequences by using exhaustive or heuristic search methods. However, the best nonlinearity value reached by these methods could not exceed 16268. In this study, RSBFs produced from (1057, 31)-interleaved sequences are investigated for the first time to the best of our knowledge, and the nonlinearity value of 16272 is attained by a heuristic search method.

Keywords:

Bent-concatenation bound, interleaved sequence, nonlinearity, rotation-symmetric Boolean function (RSBF),

PDF

___

Ding, C., Xiao, G., Shan, W. The stability theory of stream ciphers, Springer, Berlin, 1991.
Matsui, M. Linear cryptanalysis method for DES cipher, Springer, Berlin, 1994, EUROCRYPT 1993, LNCS, vol. 765, pp. 386-397.
X.-D. Hou. On the norm and covering radius of the first order Reed-Muller codes, IEEE Trans. Inf. Theory, 1997, 43(3), pp. 1025-1027.
Patterson, N. J., Wiedemann, D. H. The covering radius of the (215, 16) Reed-Muller code is at least 16276, IEEE Trans. Inf. Theory, 1983, 29(3), pp. 354-356.
Kavut, S., Yücel, M. D. 9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class, Inf. Comput., 2010, 208(4), pp. 341-350.
Gangopadhyay, S., Keskar, P. H., Maitra, S. Patterson-Wiedemann construction revisited, Discret. Math., 2006, 306(14), pp. 1540-1556.
Kavut, S. New Patterson-Wiedemann type functions with 15 variables in the generalized rotation-symmetric class, Turk. J. Electr. Eng. Comp. Sci., 2017, 25(6), pp. 4901-4906.
Kavut, S. A Modified Patterson-Wiedemann Construction Having Nonlinearity Greater Than Bent Concatenation Bound, Rostock, Germany, 2022, WCC 2022.
Kavut, S., Maitra, S. Patterson-Wiedemann type functions on 21 variables with nonlinearity greater than bent concatenation bound, IEEE Trans. Inf. Theory, 2016, 62(4), pp. 2277-2282.
Zhang, W.G. High-meets-low: construction of strictly almost optimal resilient Boolean functions via fragmentary Walsh spectra, IEEE Trans. Inf. Theory, 2019, 65(9), pp. 5856-5864.
Sarkar, S., Maitra, S. Idempotents in the neighbourhood of Patterson-Wiedemann functions having Walsh spectra zeros, Des. Codes Cryptogr., 2008, 49, pp. 95-103.
Kavut, S. Improved cryptographic properties of Boolean functions obtained from the neighbourhood of Patterson-Wiedemann functions. Cryptogr. Commun., 2023, 15, pp. 433-442.
Stănică, P., Maitra, S. Rotation symmetric Boolean functions − Count and cryptographic properties, Discret. Appl. Math., 2008, 156(10), pp. 1567-1580.
Pieprzyk, J., Qu, C. X. Fast hashing and rotation-symmetric functions, J. Universal Comput. Sci. 1999, 5(1) pp. 20-31.
Filiol, E., Fontaine, C. Highly nonlinear balanced Boolean functions with a good correlation immunity, Springer, Berlin, 1998, EUROCRYPT 1998, LNCS, vol. 1403, pp. 475-488.
Fontaine, C. On some cosets of the first-order Reed-Muller code with high minimum weight, IEEE Trans. Inf. Theory, 1999, 45(4), pp. 1237-1243.
Courtois, N. T., Meier, W. Algebraic attacks on stream ciphers with linear feedback, Springer, Berlin, 2003, EUROCRYPT 2003, LNCS, vol. 2656, pp. 345-359.
Kavut, S. Bazı alt uzaylarda kriptografik açıdan eniyilenmiş büyük S-kutuları, EMO Bilimsel Dergi, 2022, 12(1), pp. 43-51.
Kavut, S., Yücel, M. D. Güçlü kriptografik özelliklere sahip Boole işlevleri tasarımında yeni bir algoritma, Ankara, Türkiye, 2005, 1.Ulusal Kriptoloji Sempozyumu, Bildiriler Kitabı, pp. 95-105.
Kavut, S. Maitra, S., Yücel, M. D. Search for Boolean functions with excellent profiles in the rotation symmetric class, IEEE Trans. Inf. Theory, 2007, 53(5), pp. 1743-1751.
Clark, J. A., Jacob, J. L. Two-stage optimisation in the design of Boolean functions, Springer, Berlin, 2000, ACISP 2000, LNCS, vol. 1841, pp. 242-254.
Kavut, S. Truth tables and system of inequalities for (1057, 31)-interleaved sequences, GitHub, URL: https://github.com/Selcuk-kripto/1057_31 (Erişim tarihi: 20.11.2022).
Kavut, S. Correction to the paper: Patterson-Wiedemann construction revisited, Discret. Appl. Math., 2016, 202, pp. 185-187.
Dalai, D. K., Gupta, K. C., Maitra, S. Results on algebraic immunity for cryptographically significant Boolean functions, Springer, Berlin, 2004, INDOCRYPT 2004, LNCS, vol. 3348, pp. 92-106.