Idempotent and p-potent quadratic functions: distribution of nonlinearity and co-dimension

详细信息    查看全文

• 作者：Nurdagül Anbar ; Wilfried Meidl ; Alev Topuzoğlu
• 关键词：Quadratic functions ; Plateaued functions ; Bent functions ; Walsh transform ; Idempotent functions ; Rotation symmetric ; Reed ; Muller code
• 刊名：Designs, Codes and Cryptography
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：82
• 期：1-2
• 页码：265-291
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Coding and Information Theory; Data Structures, Cryptology and Information Theory; Data Encryption; Discrete Mathematics in Computer Science; Information and Communication, Circuits;
• 出版者：Springer US
• ISSN：1573-7586
• 卷排序：82

文摘

The Walsh transform \(\widehat{Q}\) of a quadratic function \(Q:{\mathbb F}_{p^n}\rightarrow {\mathbb F}_p\) satisfies \(|\widehat{Q}(b)| \in \{0,p^{\frac{n+s}{2}}\}\) for all \(b\in {\mathbb F}_{p^n}\), where \(0\le s\le n-1\) is an integer depending on Q. In this article, we study the following three classes of quadratic functions of wide interest. The class \(\mathcal {C}_1\) is defined for arbitrary n as \(\mathcal {C}_1 = \{Q(x) = \mathrm{Tr_n}(\sum _{i=1}^{\lfloor (n-1)/2\rfloor }a_ix^{2^i+1})\;:\; a_i \in {\mathbb F}_2\}\), and the larger class \(\mathcal {C}_2\) is defined for even n as \(\mathcal {C}_2 = \{Q(x) = \mathrm{Tr_n}(\sum _{i=1}^{(n/2)-1}a_ix^{2^i+1}) + \mathrm{Tr_{n/2}}(a_{n/2}x^{2^{n/2}+1}) \;:\; a_i \in {\mathbb F}_2\}\). For an odd prime p, the subclass \(\mathcal {D}\) of all p-ary quadratic functions is defined as \(\mathcal {D} = \{Q(x) = \mathrm{Tr_n}(\sum _{i=0}^{\lfloor n/2\rfloor }a_ix^{p^i+1})\;:\; a_i \in {\mathbb F}_p\}\). We determine the generating function for the distribution of the parameter s for \(\mathcal {C}_1, \mathcal {C}_2\) and \(\mathcal {D}\). As a consequence we completely describe the distribution of the nonlinearity for the rotation symmetric quadratic Boolean functions, and in the case \(p > 2\), the distribution of the co-dimension for the rotation symmetric quadratic p-ary functions, which have been attracting considerable attention recently. Our results also facilitate obtaining closed formulas for the number of such quadratic functions with prescribed s for small values of s, and hence extend earlier results on this topic. We also present the complete weight distribution of the subcodes of the second order Reed–Muller codes corresponding to \(\mathcal {C}_1\) and \(\mathcal {C}_2\) in terms of a generating function.