Decomposing bent functions

被引:90
作者
Canteaut, A [1 ]
Charpin, P [1 ]
机构
[1] INRIA, Project CODES, F-78153 Le Chesnay, France
关键词
bent functions; Boolean functions; derivatives of Boolean functions; Reed-Muller codes; restrictions of Boolean functions;
D O I
10.1109/TIT.2003.814476
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In a recent paper [1], it is shown that the restrictions of bent functions to subspaces of codimension 1 and 2 are highly nonlinear. Here, we present an extensive study of the restrictions of bent functions to affine subspaces. We propose several methods which are mainly based on properties of the derivatives and of the dual of a given bent function. We solve an open problem due to Hou [2]. We especially describe the connection, for a bent function, between the Fourier spectra of its restrictions and the decompositions of its dual. Most notably, we show that the Fourier spectra of the restrictions of a bent function to the subspaces of codimension 2 can be explicitly derived from the Hamming weights of the second derivatives of the dual function. The last part of the paper is devoted to some infinite classes of bent functions which cannot be decomposed into four bent functions.
引用
收藏
页码:2004 / 2019
页数:16
相关论文
共 25 条
[1]  
[Anonymous], 1995, LNCS
[2]  
Bending T. D., 1998, ELECTRON J COMB, V5, pR34, DOI [10.37236/1372, DOI 10.37236/1372]
[3]   On cryptographic properties of the cosets of R(1, m) [J].
Canteaut, A ;
Carlet, C ;
Charpin, P ;
Fontaine, C .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2001, 47 (04) :1494-1513
[4]  
Canteaut A, 2000, LECT NOTES COMPUT SC, V1807, P507
[5]   Weight divisibility of cyclic codes, highly nonlinear functions on F2m, and crosscorrelation of maximum-length sequences [J].
Canteaut, A ;
Charpin, P ;
Dobbertin, H .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (01) :105-138
[6]  
CANTEAUT A, 2003, P WORKSH COD CRYPT W, P91
[7]  
CANTEAUT U, 1997, P SEL AR CRYPT SAC 9, P172
[8]  
Carlet C., 1993, Designs, Codes and Cryptography, V3, P135, DOI 10.1007/BF01388412
[9]   Codes, Bent Functions and Permutations Suitable for DES-like Cryptosystems [J].
Carlet C. ;
Charpin P. ;
Zinoviev V. .
Designs, Codes and Cryptography, 1998, 15 (2) :125-156
[10]  
Carlet C., 1994, LECTURE NOTES COMPUT, V765, P77, DOI DOI 10.1007/3-540-48285-7_8