New Patterson{Wiedemann type functions with 15 variables in the generalized rotation-symmetric class

Recently, it was shown that there is no Boolean function on 15 variables with nonlinearity greater than 16276 in the class of functions that are invariant under the action of GF(2 3 )GF (2 5 ) . In this study, we consider some important subsets of this class and perform an efficient enumeration of the 15-variable Patterson{Wiedemann (PW) type functions with nonlinearity greater than the bent concatenation bound 16256 in the generalized classes of both 3-RSBFs and 5-RSBFs for which the corresponding search spaces are 2 28 : 2 and 2 47 : 85 , respectively. For the case of 3-RSBFs, we nd that there are 32 functions with nonlinearity > 16256, such that 8 of them correspond to the original PW constructions, while the remaining 24 functions are new in the sense that they are not affine equivalent to the known ones. For the other case of 5-RSBFs, our results show that there are 478 functions with nonlinearity exceeding the bent concatenation bound, among which there is another set of 470 functions that are affine inequivalent to the known PW constructions.

PDF

___

[1] Matsui M. Linear cryptanalysis method for DES cipher. In: Advances in Cryptology - EUROCRYPT'93; 23{27 May 1993; Lofthus, Norway. pp. 386-397.
[2] Siegenthaler T. Decrypting a class of stream ciphers using ciphertext only. IEEE T Comput 1985; 34: 81-85.
[3] Carlet C, Khoo K, Lim CW, Loe CW. Generalized correlation analysis of vectorial Boolean functions. In: Fast Software Encryption - FSE 2007; 26{28 March 2007; Luxembourg City, Luxembourg. pp. 382-398.
[4] Meier W, Staffelbach O. Fast correlation attacks on stream ciphers. In: Advances in Cryptology - EUROCRYPT'88; 25{27 May 1988; Davos, Switzerland. pp. 301-314.
[5] Patterson NJ, Wiedemann DH. The covering radius of the (2 15 ,16) Reed-Muller code is at least 16276. IEEE T Inform Theory 1983; 29: 354-356.
[6] Kavut S, Maitra S, Yucel MD. Search for Boolean functions with excellent pro les in the rotation symmetric class. IEEE T Inform Theory 2007; 53: 1743-1751.
[7] Kavut S, Yucel MD. 9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class. Inform Comput 2008; 208: 341-350.
[8] Gangopadhyay S, Keskar PH, Maitra S. Patterson-Wiedemann construction revisited. Discrete Math 2006; 306: 1540-1556.
[9]Kavut S, Maitra S. Patterson-Wiedemann type functions on 21 variables with nonlinearity greater than bentconcatenation bound. IEEE T Inform Theory 2016; 62: 2277-2282.
[10]Kavut S, Maitra S,Ozbudak F. A super-set of Patterson-Wiedemann functionsupper bounds and possiblenonlinearities. In: International Workshop on the Arithmetic of Finite Fields - WAIFI 2016; 13{15 July 2016;Ghent, Belgium. pp. 227-242.
[11]Maitra S, Kavut S, Yucel MD. Balanced Boolean function on 13-variables having nonlinearity greater than thebent concatenation bound. In: Boolean Functions: Cryptography and Applications - BFCA 2008; 19{21 May 2008;Copenhagen, Denmark. pp. 109-118.
[12]Maitra S, Sarkar P. Modi cations of Patterson-Wiedemann functions for cryptographic applications. IEEE T InformTheory 2002; 48: 278-284.
[13]Sarkar S, Maitra S. Idempotents in the neighbourhood of Patterson-Wiedemann functions having Walsh spectrazeros. Design Code Cryptogr 2008; 49: 95-103.
[14]Zhang XM, Zheng Y. GAC { The criterion for global avalanche characteristics of cryptographic functions. J UniversComput Sci 1995; 1: 316-333.
[15]Gong G. Theory and applications of q-ary interleaved sequences. IEEE T Inform Theory 1995; 41: 400-411.
[16]Gangopadhyay S, Maitra S. Crosscorrelation spectra of Dillon and Patterson-Wiedemann type Boolean functions.IACR Cryptology ePrint Archive 2004; 2004: 14.
[17]Filiol E, Fontaine C. Highly nonlinear balanced Boolean functions with a good correlation immunity. In: Advancesin Cryptology - EUROCRYPT98; 3 May{4 June 1998; Espoo, Finland. pp. 475-488.
[18]Fontaine C. On some cosets of the First-Order Reed-Muller code with high minimum weight. IEEE T Inform Theory1999; 45: 1237-1243.