Plateaued函数的构造方法研究

孙天锋; 胡斌; 杨阳

doi:10.11999/JEIT170965

摘要: Plateaued函数在密码学及编码等领域有着极其重要的应用，该文提出一种Plateaued函数的直接构造方法，研究了由该方法构造的Plateaued函数的密码学性质，证明了现有的直接构造方法可归约到本构造方法。

关键词:

Abstract: Plateaued functions play a significant role in cryptography, coding theory and so on. In this paper, a new primary construction of plateaued function is given. Some cryptographic properties of the constructed plateaued functions are studied. It is shown that the existing primary constructions of plateaued function can be reduced to the proposed construction.

Key words:

1. 引言

众所周知，密码函数是序列密码和分组密码中一个重要的密码变换环节，在密码系统的设计中起着举足轻重的作用。为了能够有效抵抗各种密码攻击，密码函数应当具有良好的密码学性质。不同的密码系统侧重的密码学性质不同，但非线性度和弹性阶是两个必须要考虑的性质。Maitra和Sarkar在文献[1]中指出，非线性度和弹性阶相互制约。只有Plateaued函数^[2]能达到两者最好的折中。Plateaued函数是包含Bent函数^[3]和部分Bent函数^[4]的更大的函数类，可具有高非线性度、一定的弹性阶、良好的传播特性，而且可以不具有非零的线性结构，是一类密码学性质优良的函数类。因此，对Plateaued函数构造方法的研究成为一个十分必要的研究课题。

密码函数的构造方法主要分两类：直接构造方法和二次构造方法。关于Plateaued函数直接构造方法的研究成果较少，大多由Bent函数的构造方法推广得来，其中Bent函数两种主要的直接构造方法为文献[5]和文献[6]。之后文献[7]扩展了文献[6]中的构造方法，提出了一种关于Plateaued函数的新的直接构造方法。对于Plateaued函数的其他直接构造方法，可参考文献[8–10]。函数的二次构造方法对于改良函数某些特定的密码学性质具有极其重要的意义，文献[11]推广了间接和(indirect sum)的概念，提出了一种Plateaued函数的二次构造方法；文献[12]通过级联两个Bent函数，给出了一种具有高非线性度且无线性结构的Plateaued函数的构造方法；文献[13]通过固定Bent函数某个变元的值，将一个Bent函数分解为两个Plateaued函数，并利用函数的间接和，给出了一种Plateaued函数二次构造方法。对于Plateaued函数的其他二次构造方法，可参考文献[14–16]。

本文主要对Plateaued函数的直接构造方法进行研究，并分析其相关密码学性质。

2. 预备知识

本文用 ${F_2}$ 表示二元域， $F_2^n$ 表示 ${F_2}$ 上的 $n$ 维向量空间。 $n$ 元布尔函数为 $F_2^n$ 到 ${F_2}$ 的映射，用 ${{B}_n}$ 表示所有 $n$ 元布尔函数构成的集合。实数上的加法运算记为 $+$ 和 ${\Sigma _i}$ ，二元域上的加法运算记为 $\oplus$ 和 ${ \oplus _i}$ 。任意 $f \in {{ B}_n}$ 均可由其代数标准型唯一表示，即

$f({{x}}) = f({x_1}, {x_2},·\!·\!· ,{x_n}) = \mathop \oplus \limits_{{{u}} \in F_2^n} {\lambda _{{u}}}\left(\prod\limits_{i = 1}^n {x_i^{{u_i}}} \right)$

其中， ${\lambda _{{u}}} \in {F_2}$ 。函数 $f({{x}})$ 的代数次数记为 $\deg (f)$ ，且

$\deg (f) = \mathop {\max }\limits_{{u} \in F_2^n} \{ wt({{u}}):{\lambda _{{u}}} \ne 0\}$

其中， $wt({{u}})$ 为向量 ${{u}}$ 的汉明重量。当 $\deg (f) = 1$ 时，称 $f({{x}})$ 为仿射函数，用 ${{A}_n}$ 表示 $n$ 元仿射函数构成的集合，特别地，当 ${\lambda _0} = 0$ 时，称 $f(x)$ 为线性函数，用 ${L_n}$ 表示 $n$ 元仿射函数构成的集合。

函数 $f \in {{B}_n}$ 在 ${ω}\in F_2^n$ 点的Walsh谱为

${W_f}({{ω}} ) = \sum\limits_{{{x}} \in F_2^n} {{{( - 1)}^{f({{x}}) \oplus {{ω}} \cdot {{x}}}}}$

其中， ${{ω}} \cdot {{x}}$ 为二者的点积。 $f({{x}})$ 的Walsh谱满足能量守恒定理，即

$\sum\limits_{{ω} \in F_2^n} {{W_f}{{({{ω}} )}^2}} = {2^{2n}}$

$f({{x}})$ 的非线性度 ${N_f}$ 与其Walsh谱之间满足关系：

${N_f} = {2^{n - 1}} - \frac{1}{2}\mathop {\max }\limits_{{ω} \in F_2^n} |{W_f}({{ω}} )|$

由能量守恒定理可知， ${N_f} \le {2^{n - 1}} - {2^{n/2 - 1}}$ ，称非线性度为 ${2^{n - 1}} - {2^{n/2 - 1}}$ 的 $n$ 元布尔函数为Bent函数，显然， $n$ 必为偶数。

定义1^[2] 设 $f \in {{B}_n}$ ，如果存在一个偶数 $r$ ，使得

$\# \left\{ {{{ω}} \in F_2^n:{W_f}({{ω}} ) \ne 0} \right\} = {2^r}$

且对任意的 ${{ω}} \in F_2^n$ ， ${W_f}({{ω}} ) = 0$ 或 $\pm {2^{n - {r}/{2}}}$ ，则称 $f({{x}})$ 为 $r$ 阶Plateaued函数。

设 $f \in {{B}_n}$ ，则 $f({{x}})$ 为 $m$ 阶弹性函数的充要条件为对任意的 ${{ω}} \in F_2^n$ ， $0 \le wt({{ω}} ) \le m$ ，有 ${W_f}({{ω}} ) = 0$ 。

定义2^[17] 设 $f \in {{B}_n}$ 为2次函数，则其双线性函数定义为

${B_f}({{x}},{{y}}) = f({{0}}) \oplus f({{x}}) \oplus f({{y}}) \oplus f({{x}} \oplus {{y}})$

其根空间 ${\rm{rad}}(f)$ 定义为

${\rm{rad}}(f) = \{ {{x}} \in F_2^n:\forall {{y}} \in F_2^n,{B_f}({{x}},{{y}}) = 0\}$

下面引理1给出了2次函数Walsh谱与其根空间之间的关系。

引理1^[17]2次函数 $f \in {{B}_n}$ 的Walsh谱分布由其根空间 ${\rm rad}(f)$ 的维数 $t$ 唯一确定，如表1所示。

表 1 谱值与根空间维数的关系

${W_f}({{ω}} )$	${{ω}}$ 的个数
0	${2^n} - {2^{n - t}}$
${2^{(n + t)/2}}$	${2^{n - t - 1}} + {( - 1)^{f(0)}}{2^{(n - t - 2)/2}}$
$- {2^{(n + t)/2}}$	${2^{n - t - 1}} - {( - 1)^{f(0)}}{2^{(n - t - 2)/2}}$

下载: 导出CSV

| 显示表格

下面介绍几类关于Plateaued函数的函数结构。

定义3^[7] 设 $n = r + s$ , $r$ 和 $s$ 为任意正整数， $\phi$ 为 $F_2^s$ 到 $F_2^r$ 的一个映射， $g$ 为 $F_2^s$ 上的布尔函数，则Maiorana-McFarland型函数定义为

${f_{{\rm{MM}}}}({{x}},{{y}}) = {{x}} \cdot \phi ({{y}}) \oplus g({{y}})$

(1)

其中， ${{x}} \in F_2^r,{{y}} \in F_2^s$ 。简记该函数结构为MM型。

下面引理2给出其构成Plateaued函数的充分条件。

引理2^[7] 令 ${f_{{\rm{MM}}}} \in {{B}_n}$ 为MM型函数，则

(1)若映射 $\phi$ 为单射，则 ${f_{{\rm{MM}}}}({{x}},{{y}})$ 为 $2s$ 阶Plateaued函数；

(2)若映射 $\phi$ 为2对1映射，则 ${f_{{\rm{MM}}}}({{x}},{{y}})$ 为 $2s - 2$ 阶Plateaued函数。

文献[10]中利用级联函数真值表的方法，给出了一种Plateaued函数的直接构造方法，该方法描述如下：

令 $t$ 和 $k$ 为正整数且 $k < {2^t} < {2^k}$ , $E \subseteq F_2^k$ ， $\# E = {2^t}$ 且 $F_2^k$ 上任意非零线性函数限制在 $E$ 上不为常数。对任意的 ${{{e}}_i} \in E$ ，令 ${\gamma _i}$ 为线性函数 ${{x}} \cdot {{{e}}_i}$ 的真值表，则以 ${\gamma _0}{\gamma _1} ·\!·\!· {\gamma _{{2^t} - 1}}$ 为真值表的函数 $f \in {{B}_{k + t}}$ 为 $2t$ 阶Plateaued函数。

该构造方法已被证明属于MM型函数结构^[9]，即本质为仿射函数的级联，而仿射函数是一类性质较弱的函数，为了弥补该缺点，下面介绍两种级联2次函数的函数结构。

定义4^[8] 令 $n$ 和 $r$ 为任意正整数，且 $r \!<\! n$ , $t \!=\!\! \left\lfloor {r/2} \right\rfloor$ , $s \!=\! n - r$ 。令 $\psi$ 为 $F_2^s$ 到 $F_2^t$ 的一个映射， ${\psi _1},{\psi _2}, ·\!·\!·, {\psi _t}$ 为其坐标函数，令 $\phi$ 为 $F_2^s$ 到 $F_2^r$ 的一个映射， ${\phi _1},{\phi _2}, ·\!·\!· ,{\phi _r}$ 为其坐标函数， $g$ 为 $F_2^s$ 上的布尔函数，定义

${f_{{\rm{MD}}}}({{x}},{{y}}) = \oplus _{i = 1}^t{x_{2i - 1}}{x_{2i}}{\psi _i}({{y}}) \oplus{x} \cdot \phi ({{y}}) \oplus g({{y}})$

(2)

其中， ${{x}} \in F_2^r,{{y}} \in F_2^s$ 。简记该函数结构为MD型。显然，当 $\psi$ 为零映射时，MM型函数与MD型函数相同。

引理3^[8] 令 ${f_{{\rm{MD}}}} \in {{ B}_n}$ 为MD型函数，对任意的 ${{a}} \in F_2^r$ ，定义集合

${E_{{a}}} = \!\left\{\!\! {\begin{aligned}& \{ {{y}} \in F_2^s:\forall i \le t,{\psi _i}({{y}}) = {a_{2i - 1}}\\& \Rightarrow {\phi _{2i - 1}}({{y}}) = {a_{2i - 1}},{\phi _{2i}}({{y}}) = {a_{2i}}\} ,\\& \quad\quad r {{为偶数}}\\& \{ {{y}} \in F_2^s:\forall i \le t,{\psi _i}({{y}}) = {a_{2i - 1}} \\& \Rightarrow {\phi _{2i - 1}}({{y}}) \!=\! {a_{2i - 1}},{\phi _{2i}}({{y}}) \!=\! {a_{2i}};{\phi _r} ({{y}}) \!s=\! {a_r}\} ,\\& \quad\quad r {{为奇数}}\end{aligned}} \right.$

若对任意的 ${{y}} \in F_2^s$ ， $\psi ({{y}})$ 的汉明重量为 ${r_0}$ ，则

(1)若对任意的 ${{a}} \in F_2^r$ , $\# {E_{{a}}} = 0$ 或 $1$ ，则 ${f_{{\rm{MD}}}}(x,y)$ 为 $2(s + {r_0})$ 阶Plateaued函数；

(2)若对任意的 ${{a}} \in F_2^r$ , $\# {E_{{a}}} = 0$ 或 $2$ ，则 ${f_{{\rm{MD}}}}(x,y)$ 为 $\ 2(s + {r_0} - 1)$ 阶Plateaued函数。

定义5^[9] 设 $n = r + s$ , $r$ 和 $s$ 为任意正整数， ${\phi _1},{\phi _2},{\phi _3}$ 是 $F_2^s$ 到 $F_2^r$ 的3个映射， $g$ 为 $F_2^s$ 上的布尔函数，定义

$\begin{align}{f_{\rm{Q}}}({{x}},{{y}}) =& ({{x}} \cdot {\phi _1}({{y}}))({{x}} \cdot {\phi _2}({{y}})) \\& \oplus {{x}} \cdot {\phi _3}({{y}}) \oplus g({{y}})\end{align}$

(3)

其中， ${{x}} \in F_2^r,{{y}} \in F_2^s$ 。简记该函数结构为Q型。以下引理给出了Q型函数构成Plateaued函数的充分条件。

引理4^[9] 令 ${f_{\rm{Q}}}({{x}},{{y}}) \in {{B}_n}$ 为Q型函数，且对任意的 ${{y}} \in F_2^s$ ，向量 ${\phi _1}({{y}})$ 和 ${\phi _2}({{y}})$ 线性无关。若当 ${{y}}$ 遍历 $F_2^s$ 时， ${\phi _3}({{y}}) + < {\phi _1}({{y}}),{\phi _2}({{y}}) >$ 中的元素两两不相等，则函数 ${f_{\rm{Q}}}({{x}},{{y}})$ 为 $2s + 2$ 阶Plateaued函数。

引理5^[9]令 ${f_{\rm{Q}}}({{x}},{{y}}) \in {{B}_n}$ 为Q型函数，且对任意的 ${{y}} \in F_2^s$ ， ${\phi _2}({{y}}) \ne 0$ 。定义以下两个集合：

$\begin{align} {F_{{a}}}\!^\prime =& \{ {{y}} \in F_2^s:{\phi _1}({{y}}){{与}}{\phi _2}({{y}}){{线性无关；}} \\&{{a}} \in {\phi _3}({{y}}) + < {\phi _1}({{y}}),{\phi _2}({{y}}) > \} \end{align}$

$\begin{align} {F_{{a}}}\!'' = &\{ {{y}} \in F_2^s:{\phi _1}({{y}}){{与}}{\phi _2}({{y}}){{线性相关；}}\\&{{a}} = {\phi _3}({{y}}) + {\phi _1}({{y}})\} \end{align}$

若对任意的 ${{a}} \in F_2^r$ ， $\# {F_{{a}}}^\prime + 2\# {F_{{a}}}'' = 0$ 或2，则函数 ${f_{\rm{Q}}}({{x}},{{y}})$ 是 $2s$ 阶Plateaued函数。

3. 新型Plateaued函数结构

MM型函数采用级联仿射函数的方式，MD型和Q型函数采用级联特定形式的2次函数的方式，这3类函数结构的Walsh谱均易于计算。本节给出一种级联一般形式2次函数的函数结构，其谱值也易于计算。

令 ${{A}} = {({a_{ij}})_{nn}},{{B}} = {({b_{ij}})_{nn}},{{C}} = {({c_{ij}})_{nn}}, ·\!·\!·$ 表示矩阵， ${\varOmega _t}$ 为所有 $t$ 阶上三角矩阵构成的集合。对任意的2次函数 $f \in {{ B}_n}$ 且 $f({{0}}) = 0$ ，其代数标准型为

$f({{x}}) = \mathop \oplus \limits_{i = 1}^n {\alpha _i}{x_i} \oplus \mathop \oplus \limits_{1 \le i < j \le n} {\alpha _{i,j}}{x_i}{x_j}$

也可将其表示为

$f({{x}}) = ({x_1},{x_2}, ·\!·\!· ,{x_n}){{A}}{({x_1},{x_2}, ·\!·\!· ,{x_n})^{\rm{T}}}$

(4)

其中， ${{A}} \in {\varOmega _n}$ , ${a_{ii}} = {\alpha _i}$ , ${a_{ij}} = {\alpha _{i,j}}$ 。

通过级联式(4)中的2次函数，给出下面的函数结构，记为TF型函数结构。

定义6　设 $n = r + s$ , $r$ 和 $s$ 为任意正整数，则TF型函数定义为

${f_{\zeta ,g}}({{x}},{{y}}) = {{x}}\zeta ({{y}}){{{x}}^{\rm{T}}} \oplus g({{y}})$

(5)

其中， ${{x}} \in F_2^r,{{y}} \in F_2^s$ ， $\zeta$ 为 $F_2^s$ 到集合 ${\varOmega _r}$ 的一个映射， $g$ 为 $F_2^s$ 上的布尔函数。

下面给出TF型函数的谱值计算定理。

定理1 令 ${f_{\zeta ,g}} \in {{B}_n}$ 为TF型函数，对任意的 ${{x}} \!\in\! F_2^r,{{y}} \!\in\! F_2^s$ ，令 $\zeta ({{y}}) \!=\! {A_{{y}}} \in {\varOmega _r}$ , ${h_{{y}}}({{x}}) \!=\! {{x}}{{{A}}_{{y}}}{{{x}}^{\rm{T}}}$ ，则对任意的 $({{a}},{{b}}) \in F_2^r \times F_2^s$ ，有

${W_{{f_{\zeta ,g}}}}({{a}},{{b}}) = \sum\limits_{{{y}} \in F_2^s} {{\xi _{{a},\zeta }}({{y}}){2^{(2r - R({{{A}}_{{y}}} \oplus {{A}}_{{y}}^{\rm{T}}))/2}}{{( - 1)}^{g({{y}}) \oplus {{b}} \cdot {{y}}}}}$

其中， $R({{A}} \oplus {{{A}}^{\rm{T}}})$ 表示矩阵 ${{A}} \oplus {{{A}}^{\rm{T}}}$ 的秩， ${\xi _{{{a}},\zeta }}$ 为 $F_2^s$ 到 $\{ 0,1, - 1\}$ 的一个映射：

${\xi _{{{a}},\zeta }}({{y}}) = \left\{ {\begin{aligned}& {0,\quad\quad{W_{{h_y}}}({{a}}) = 0} \\ & {1,\quad\quad{W_{{h_y}}}({{a}}) > 0} \\ & { - 1, \quad{W_{{h_y}}}({{a}}) < 0} \end{aligned}} \right.$

证明由定义2，函数 ${h_{{y}}}({{x}})$ 的双线性函数为

$\begin{align} {B_{{h_y}}}({{x}},z) =& {h_y}({{0}}) \oplus {h_{{y}}}({{x}}) \oplus {h_{{y}}}({z}) \oplus {h_{{y}}}({x} \oplus {z}) \\ = &\!0 \!\oplus\! {{x}}{{{A}}_{{y}}}{{{x}}^{\rm{T}}} \!\oplus\! {z}{{{A}}_{{y}}}{{z}^{\rm{T}}} \!\oplus\! ({{x}} \!\oplus\! {z}){{{A}}_{{y}}}{({x} \!\oplus\! {z})^{\rm{T}}} \\ =& {{x}}({{{A}}_{{y}}} \oplus {{A}}_{{y}}^{\rm{T}}){{z}^{\rm{T}}} \\ \end{align}$

其根空间为

$\begin{align} {\rm{rad}}({h_{{y}}}) = &\{ {{x}} \in F_2^r:\forall {z} \in F_2^r,{B_{{h_{{y}}}}}({{x}},{z}) = 0\} \\= &\{ {{x}} \in F_2^r:\forall {z} \in F_2^r,{{x}}({{{A}}_{{y}}} \oplus {{A}}_{{y}}^{\rm{T}}){{z}^{\rm{T}}} = 0\} \\ = &\{ {{x}} \in F_2^r:{{x}}({{{A}}_{{y}}} \oplus {A}_y^{\rm{T}}) = {0}\} \\ \end{align}$

故 ${\rm{rad}}({h_{{y}}})$ 的维数为 $r - R({{A}} \oplus {{{A}}^{\rm{T}}})$ 。

由引理1及映射 ${\xi _{{a},\zeta }}$ 的定义，对任意的 $({{a}},{{b}}) \in$ $F_2^r \times F_2^s$ ，有

$\begin{align} {W_{{f_{\zeta ,g}}}}({{a}},{{b}}) &= \sum\limits_{{{x}} \in F_2^r,{{y}} \in F_2^s} {{{( - 1)}^{{f_{\zeta ,g}}({{x}},{{y}}) \oplus {{a}} \cdot {{x}} \oplus {{b}} \cdot {{y}}}}} \\ &= \sum\limits_{{{y}} \in F_2^s} {{{( - 1)}^{g({{y}}) \oplus {{b}} \cdot {{y}}}}} \sum\limits_{x \in F_2^r} {{{( - 1)}^{{{x}}\zeta ({{y}}){{{x}}^{\rm{T}}} \oplus {{a}} \cdot {{x}}}}} \\ &=\!\! \sum\limits_{{{y}} \in F_2^s} \!\!{{\xi _{{{a}},\zeta }}({{y}}){2^{(r + (r - R({{{A}}_{{y}}} \oplus {{A}}_{{y}}^{\rm{T}})))/2}}\!{{( -\! 1)}^{g({{y}}) \oplus {{b}} \cdot {{y}}}}} \\& = \sum\limits_{{{y}} \in F_2^s} {{\xi _{{{a}},\zeta }}({{y}}){2^{(2r - R({{{A}}_{{y}}} \oplus {{A}}_{{y}}^{\rm{T}}))/2}}{{( - 1)}^{g({{y}}) \oplus {{b}} \cdot {{y}}}}} \end{align}$

证毕

由此给出Plateaued函数的构造定理。

定理2 令 ${f_{\zeta ,g}} \in {{B}_n}$ 为TF型函数，假定对任意的 ${{y}} \in F_2^s$ ， $R({{{A}}_{{y}}} \oplus {{A}}_{{y}}^{\rm{T}})$ 保持不变，记为 ${t_0}$ 。定义集合

${F_{{a}}} = \{ {{y}} \in F_2^s:{\xi _{{{a}},\zeta }}({{y}}) \ne 0\} ,\ {{a}} \in F_2^r$

则

(1) 若对任意的 ${{a}} \in F_2^r$ ， $\# {F_{{a}}} = 0$ 或1，则函数 ${f_{\zeta ,g}}({{x}},{{y}})$ 是 $2s + {t_0}$ 阶Plateaued函数；

(2) 若对任意的 ${{a}} \in F_2^r$ ， $\# {F_{{a}}} = 0$ 或2，则函数 ${f_{\zeta ,g}}({{x}},{{y}})$ 是 $2s + {t_0} - 2$ 阶Plateaued函数。

证明由于对任意的 ${{y}} \in F_2^s$ ， $R({{{A}}_{{y}}} \oplus {{A}}_{{y}}^{\rm{T}})$ 保持不变，则由定理1可知，对任意的 $({{a}},{{b}}) \in F_2^r \times F_2^s$ ，有

$\begin{align} {W_{{f_{\zeta ,g}}}}({{a}},{{b}}) = &\sum\limits_{{{y}} \in F_2^s} {{\xi _{{{a}},\zeta }}({{y}}){2^{(2r - R({{{A}}_{{y}}} \oplus {A}_y^{\rm{T}}))/2}}{{( - 1)}^{g({{y}}) \oplus {{b}} \cdot {{y}}}}} \\ =& {2^{r - {t_0}/2}}\sum\limits_{{{y}} \in F_2^s} {{\xi _{{{a}},\zeta }}({{y}}){{( - 1)}^{g({{y}}) \oplus {{b}} \cdot {{y}}}}} \\ \end{align}$

若对任意的 ${{a}} \in F_2^r$ ， $\# {F_{{a}}} = 0$ 或1，则 ${W_{{f_{\zeta ,g}}}}({{a}},{{b}})$ 为0或 $\pm {( - 1)^{g({{y}}) \oplus {{b}} \cdot {{y}}}}{2^{r - {t_0}/2}} = \pm {2^{r - {t_0}/2}}$ ，即 ${f_{\zeta ,g}}({{x}},{{y}})$ 是 $2s + {t_0}$ 阶Plateaued函数。

同理可证条件(2)。证毕

注1 由定理1及定理2可知，当对任意的 ${{a}} \in F_2^r$ ， $\# {F_{{a}}} = 0$ 或1成立时，有

$\begin{align}& \sum\limits_{{{a}} \in F_2^r,{{y}} \in F_2^s} {W_{{h_{{y}}}}^2({{a}}) \le {2^{3r - {t_0}}}} \\& \sum\limits_{{{a}} \in F_2^r,{{b}} \in F_2^s} {W_f^2({{a}},{{b}}) \le {2^{3r + s - {t_0}}}} \end{align}$

由能量守恒定理可知，

${2^{s + 2r}} \le {2^{3r - {t_0}}},\ {2^{2s + 2r}} \le {2^{3r + s - {t_0}}}$

由此可知， $s \le r - {t_0}$ 。同理可得，当对任意的 ${{a}} \in F_2^r$ ， $\# {F_{{a}}} = 0$ 或2成立时，有 $s \le r - {t_0} + 2$ 。

以下记满足条件(1)的函数为 ${\rm{T}}{{\rm{F}}_{\rm{1}}}$ 型Plateaued函数，满足条件(2)的函数为 ${\rm{T}}{{\rm{F}}_2}$ 型Plateaued函数。

由非线性度和谱值之间的关系可知， ${\rm{T}}{{\rm{F}}_{\rm{1}}}$ 型Plateaued函数的非线性度为 ${2^{n - 1}} - {2^{(2r - {t_0})/2 - 1}}$ ； ${\rm{T}}{{\rm{F}}_2}$ 型Plateaued函数的非线性度为 ${2^{n - 1}} - {2^{(2r - {t_0})/2}}$ 。

由于TF型Plateaued函数本质为级联一般形式的2次函数，故其代数次数 $\le s + 2$ 。

下面两个定理分别研究了 ${\rm{T}}{{\rm{F}}_{\rm{1}}}$ 型和 ${\rm{T}}{{\rm{F}}_2}$ 型Plateaued函数的弹性阶。

定理3 令 ${f_{\zeta ,g}} \in {{B}_n}$ 为 ${\rm{T}}{{\rm{F}}_{\rm{1}}}$ 型Plateaued函数，集合

$D = \{ {{a}} \in F_2^r: {{存在}}{{y}} \in F_2^s {{使得}}{\xi _{a,\zeta }}({{y}}) \ne 0\}$

整数 $k$ 为集合 $D$ 中元素汉明重量的最小值，则函数 ${f_{\zeta ,g}}$ 的弹性阶为 $k - 1$ 且

$k \le \max \left\{ t \in N:\sum\limits_{i = 0}^t {\left( {\begin{array}{*{20}{c}} r \\ i \end{array}} \right)} \le {2^r} - \# D \right\} + 1$

证明由 ${f_{\zeta ,g}} \in {{B}_n}$ 为 ${\rm{T}}{{\rm{F}}_{\rm{1}}}$ 型Plateaued函数，故对任意的 ${{a}} \in F_2^r$ ， $\# {F_{{a}}} = 0$ 或1。由集合 $D$ 的定义可知，函数 ${f_{\zeta ,g}}$ 的弹性阶 $\le k - 1$ 。由定理1和定理2，对任意的 $({{a}},{{b}}) \in F_2^r \times F_2^s$ ， ${W_{{f_{\zeta ,g}}}}({{a}},{{b}}) = \pm {2^{r - {t_0}/2}}$ 当且仅当 ${{a}} \in D$ 。若 $wt({{a}},{{b}}) \le k - 1$ ，则 $wt({{a}}) \le k - 1$ ，从而 ${{a}} \notin D$ ，故 ${W_{{f_{\zeta ,g}}}}({{a}},{{b}}) = 0$ ，从而函数 ${f_{\zeta ,g}}$ 的弹性阶 $\ \ge k - 1$ 。

因此，函数 ${f_{\zeta ,g}}$ 的弹性阶为 $k - 1$ 。

由集合 $D$ 和整数 $k$ 的定义，汉明重量 $\le k - 1$ 的向量在集合 ${D^c}$ 中，故有

$\sum\limits_{i = 0}^{k - 1} {\left( {\begin{array}{*{20}{c}} r \\ i \end{array}} \right)} \le {2^r} - \# D$

由此得到

$k \le \max \{ t \in N:\sum\limits_{i = 0}^t {\left( {\begin{array}{*{20}{c}} r \\ i \end{array}} \right)} \le {2^r} - \# D\} + 1$

证毕

定理4 令 ${f_{\zeta ,g}} \in {{B}_n}$ 为 ${\rm{T}}{{\rm{F}}_2}$ 型Plateaued函数，集合 $D$ 和整数 $k$ 如定理3中定义，则函数 ${f_{\zeta ,g}}$ 的弹性阶为 $k$ 或 $k - 1$ 且

$k \le \max \left\{ t \in N:\sum\limits_{i = 0}^t {\left( {\begin{array}{*{20}{c}} r \\ i \end{array}} \right)} \le {2^r} - \# D\right\} + 1$

证明由定理1和定理2可知，对任意的 $({{a}},{{b}}) \in F_2^r \times F_2^s$ ， ${W_{{f_{\zeta ,g}}}}({{a}},{{b}}) = \pm {2^{r + 1 - {t_0}/2}}$ 当且仅当 ${{a}} \in D$ 。若 $wt({{a}},{{b}}) \le k - 1$ ，则 $wt({{a}}) \le k - 1$ ，从而 ${{a}} \notin D$ ，故 ${W_{{f_{\zeta ,g}}}}({{a}},{{b}}) = 0$ 。由此可知，函数 ${f_{\zeta ,g}}$ 的弹性阶 $\ge k - 1$ 。

取 ${{a}} \in D$ 且 $wt({{a}}) = k$ ，令 ${{{y}}_1},{{{y}}_2} \in F_2^s$ 且 ${\xi _{{{a}},\zeta }}({{{y}}_1})$ $\ne 0$ , ${ {ξ}_{{a},\zeta }}({{{y}}_2}) \ne 0$ 。由定理1，对任意的 ${{b}} \in F_2^s$ ，限制在 $\{ {a}\} \times F_2^s$ 上的谱值为以下二者之一：

$\begin{align} \frac{1}{{{2^{r - {t_0}/2}}}}{W_{{f_{\zeta ,g}}}}({{a}},{{b}}) =& \pm [{( - 1)^{g({{{y}}_1}) \oplus {{b}} \cdot {{{y}}_1}}}\! - {( - 1)^{g({{{y}}_2}) \oplus {{b}} \cdot {{y}_2}}}] \\ =& \pm 2[{{b}} \cdot ({{{y}}_1} \!\oplus\! {{{y}}_2}) \!\oplus\! g({{{y}}_1}) \!\oplus\! g({{{y}}_2})] \\ \frac{1}{{{2^{r - {t_0}/2}}}}{W_{{f_{\zeta ,g}}}}({{a}},{{b}}) =& \pm [{( - 1)^{g({{{y}}_1}) \oplus {{b}} \cdot {{{y}}_1}}} + {( - 1)^{g({{{y}}_2}) \oplus {{b}} \cdot {{{y}}_2}}}]\\ = \pm 2 & [{{b}} \cdot ({{{y}}_1} \!\oplus\! {{y}_2}) \!\oplus\! g({{{y}}_1}) \oplus g({{{y}}_2}) \!\oplus\! 1] \end{align}$

当向量 ${{y}_1} \ne {{y}_2}$ 时，线性函数 ${b} \cdot ({{{y}}_1} \oplus {{{y}}_2})$ 在集合 $\{ {{b}} \in F_2^s:wt({{b}}) \le 1\}$ 上的取值不为常值，从而总存在 ${{b}} \in F_2^s$ ， $wt({{b}}) \le 1$ ，使得 ${W_{{f_{\zeta ,g}}}}({{a}},{{b}}) \ne 0$ ，从而函数 ${f_{\zeta ,g}}$ 的弹性阶 $< k + 1$ 。

因此，函数 ${f_{\zeta ,g}}$ 的弹性阶为 $k$ 或 $k - 1$ 。整数 $k$ 界的证明与定理3相同，这里不再赘述。证毕

4. 各类函数结构之间的包含关系

第2节已经说明文献[10]中的函数类可归约到MM型函数，而MM型函数又可归约到MD型函数。本节证明MD型Plateaued函数和Q型Plateaued函数都可归约到TF型Plateaued函数。

首先，给出MD型Plateaued函数的归约证明。定义集合

$\begin{align}\varOmega _r^{{\rm{MD}}} =& \{ {{A}} \in {\varOmega _r}:{a_{(2i - 1)(2i)}},{a_{jj}} \in {F_2}, \\ &1 \le i \le t,1 \le j \le r;{{其余}}{a_{ij}} = 0\} \end{align}$

其中， $t = \left\lfloor {r/2} \right\rfloor$ ，令 ${\zeta _{{\rm{MD}}}}$ 为 $F_2^s$ 到 $\varOmega _r^{{\rm{MD}}}$ 的映射，则函数 ${f_{{\zeta _{{\rm{MD}}}},g}}({{x}},{{y}}) = {{x}}{\zeta _{{\rm{MD}}}}({{y}}){{{x}}^{\rm{T}}} \oplus g({y})$ 即为MD型函数。

定理5 令函数 ${f_{{\rm{MD}}}} \in {{ B}_n}$ 为MD型函数。若对任意的 ${{y}} \in F_2^s$ ， $\psi ({{y}})$ 的汉明重量为常数 ${r_0}$ ，则对任意的 ${{A}} \in \varOmega _r^{{\rm{MD}}}$ ， $R({{A}} \oplus {{{A}}^{\rm{T}}}) = 2{r_0}$ 。

证明由于仿射函数的双线性函数恒为零函数，这里只考虑映射 $\psi$ 。

若对任意的 ${{y}} \in F_2^s$ ， $\psi ({{y}})$ 的汉明重量为 ${r_0}$ ，则向量 $({\psi _1}({{y}}),{\psi _2}({{y}}), ·\!·\!·, {\psi _t}({{y}}))$ 中1的个数为 ${r_0}$ ，即集合 $\{ {a_{12}},{a_{34}}, \cdots ,{a_{(2t - 1)(2t)}}\}$ 中1的个数为 ${r_0}$ 。

当 ${r_0}$ 为偶数时，矩阵 ${{A}} \oplus {{{A}}^{\rm{T}}}$ 为

其中， ${a_{12}} = {a_{21}}, ·\!·\!· ,{a_{(r - 1)(r)}} = {a_{(r)(r - 1)}}$ 。显然，此时有 $R({{A}} \oplus {{{A}}^{\rm{T}}}) = 2{r_0}$ 。同理可证 ${r_0}$ 为奇数时的情况。证毕

定理6 MD型Plateaued函数可归约到TF型Plateaued函数。

证明对任意的 $({{a}},{{b}}) \in F_2^r \times F_2^s$ ，函数 ${f_{{\rm{MD}}}}$ 在该点的Walsh谱为

${W_{{f_{{\rm{MD}}}}}}({{a}},{{b}}) \\=\sum\limits_{{{y}} \in F_2^s} {\sum\limits_{{{x}} \in F_2^r} {{{( - 1)}^{ \oplus _{i = 1}^t{{{x}}_{2i - 1}}{{{x}}_{2i}}{\psi _i}({{y}}) \oplus {{x}} \cdot \phi ({{y}}) \oplus {{a}} \cdot {{x}}}}{{( - 1)}^{g({{y}}) \oplus {{b}} \cdot {{y}}}}} }$

若对任意的 ${{a}} \in F_2^r$ ，有 $\# {E_{{a}}} = 0$ 或1，则由定理5可知，至多存在一个 ${{y}} \in F_2^s$ 使得

$\biggr|\sum\limits_{{{x}} \in F_2^r} {{{( - 1)}^{ \oplus _{i = 1}^t{x_{2i - 1}}{{{x}}_{2i}}{\psi _i}({{y}}) \oplus {{x}} \cdot \phi ({{y}}) \oplus {{a}} \cdot {{x}}}}} \biggr| = {2^{r - {r_0}}}$

由映射 ${\zeta _{{\rm{MD}}}}$ 和集合 ${F_{{a}}}$ 的定义可知， $\# {F_{{a}}} = 0$ 或1。

同理可证若对任意的 ${{a}} \in F_2^r$ ， $\# {E_{{a}}} = 0$ 或2，则 $\# {F_{{a}}} = 0$ 或2。证毕

下面给出Q型Plateaued函数的归约证明。由于式(3)中的函数 $({{x}} \cdot {\phi _1}({{y}}))({{x}} \cdot {\phi _2}({{y}})) \oplus {{x}} \cdot {\phi _3}({{y}})$ 的秩为0或2^[9]，定义集合

$\varOmega _r^{\rm{Q}} = \{ {{A}} \in {\varOmega _r}:R({{A}} \oplus {{{A}}^{\rm{T}}}) = 0 {{或}}2\}$

令 ${\zeta _{\rm{Q}}}$ 为 $F_2^s$ 到 $\varOmega _r^{\rm{Q}}$ 的一个映射，则函数 ${f_{{\zeta _{\rm{Q}}},g}}({{x}},{{y}}) =$ ${x}{\zeta _{\rm{Q}}}({{y}}){{x}^{\rm{T}}} \oplus g({{y}})$ 即为Q型函数。

定理7 Q型Plateaued函数可归约到TF型Plateaued函数。

证明令集合

$E = \{ {{y}} \in F_2^s:{\phi _1}({{y}}){{和}}{\phi _2}({{y}})\} {{线性无关}}\}$

若 $E = F_2^s$ ，则对任意的 ${{A}} \!\in\! \varOmega _r^{\rm{Q}}$ , $R({{A}} \!\oplus\! {{{A}}^{\rm{T}}}) \!=\! 2$ ；若 $E$ 为空集，则对任意的 ${{A}} \in \varOmega _r^{\rm{Q}}$ ，有 $R({{A}} \oplus {{{A}}^{\rm{T}}}) = 0$ 。

对任意的 $({{a}},{{b}}) \in F_2^r \times F_2^s$ ，函数 ${f_{\rm{Q}}}$ 在该点的Walsh谱为

$\!\begin{array}{l}{W_{{f_{\rm{Q}}}}}({{a}},{{b}})\\ =\!\!\sum\limits_{{{y}} \in F_2^s} {\sum\limits_{{{x}} \in F_2^r} {{{( - 1)}^{({{x}} \cdot {\phi _1}({{y}}))({{x}} \cdot {\phi _2}({{y}})) \oplus {{x}} \cdot {\phi _3}({{y}}) \oplus {{a}} \cdot {{x}}}}} {{( - 1)}^{g({{y}}) \oplus {{b}} \cdot {{y}}}}} \end{array}$

若对任意的 ${{y}} \in F_2^s$ ， ${\phi _3}({{y}}) + < {\phi _1}({{y}}),{\phi _2}({{y}}) >$ 中元素两两不相等，则对任意的 ${{a}} \in F_2^r$ ，至多存在一个 ${{y}} \in F_2^s$ 使得

$\biggr|\sum\limits_{{{x}} \in F_2^r} {{{( - 1)}^{({{x}} \cdot {\phi _1}({{y}}))({{x}} \cdot {\phi _2}({{y}})) \oplus {{x}} \cdot {\phi _3}({{y}}) \oplus {{a}} \cdot {{x}}}}} \biggr| = {2^{r - 1}}$

由映射 ${\zeta _{\rm{Q}}}$ 和集合 ${F_{{a}}}$ 的定义可知， $\# {F_{{a}}} = 0$ 或1。

令集合 ${F'\!\!_{{a}}}$ 和 ${F''\!\!\!_{{a}}}$ 如引理5中定义，若 $\# {F'\!\!_{{a}}} +$ $2\# {F''\!\!\!_{{a}}} = 0$ 或2，则

$\left\{ {\begin{array}{*{20}{c}}{\# {{F'}\!\!_{{a}}} = 0 {{或}}2}\\\!\!\!\!\!\!\!\!\! {\# {{F''}\!\!\!_{{a}}} = 0}\end{array}} \right.\;\; {{或}}\;\; \left\{ {\begin{array}{*{20}{c}}\!\!\!\!\!\!\!\!\! {\# {{F'}\!\!_{{a}}} = 0}\\{\# {{F''}\!\!\!_{{a}}} = 0 {{或}}1}\end{array}} \right.$

当 $\# {F'\!\!_{{a}}} = 0$ 或2， $\# {F''\!\!\!_{{a}}} = 0$ 时，对任意的 ${{A}} \in \varOmega _r^{\rm{Q}}$ , $R({{A}} \oplus {{{A}}^{\rm{T}}}) = 2$ ，且对任意的 ${{a}} \in F_2^r$ ，存在0或2个 ${{y}} \in F_2^s$ 使得

$\biggr|\sum\limits_{{{x}} \in F_2^r} {{{( - 1)}^{({{x}} \cdot {\phi _1}({{y}}))({{x}} \cdot {\phi _2}({{y}})) \oplus {{x}} \cdot {\phi _3}({{y}}) \oplus {{a}} \cdot {{x}}}}}\biggr| = {2^{r - 1}}$

由映射 ${\zeta _{\rm{Q}}}$ 和集合 ${F_{{a}}}$ 的定义可知， $\# {F_{{a}}} = 0$ 或2。同理可证当 $\# {F_{{a}}}^\prime = 0$ , $\# {F''\!\!\!_{{a}}} = 0$ 或1时， $\# {F_{{a}}} = 0$ 或1。证毕

注2 TF型函数的函数量为 $N({\rm TF}) = {({2^{({r^2} + r)/2}})^{{2^s}}}$ $\times{2^{{2^s}}} = {2^{[({r^2} + r)/2 + 1]{2^s}}}$ ；MD型函数的函数量为 $N({\rm{MD}}) = {({2^{{2^s}}})^t} \times {({2^r})^{{2^s}}} \times {2^{{2^s}}} = {2^{(t + r + 1){2^s}}}$ ；Q型函数的函数量为 $N({\rm Q}) = {[{({2^r})^{{2^s}}}]^3} \times {2^{{2^s}}} = {2^{(3r + 1){2^s}}}$ 。可见， $N({\rm TF}) \ge N({\rm GMM})$ 且当 $r \ge 6$ 时， $N({\rm TF}) >$ $N({\rm Q})$ 。

下面给出一类不为MD型或Q型的TF型Plateaued函数。

例1 令 $n = 13$ , $s = 4$ , $r = 9$ ，矩阵 ${{{A}}_1} \in {\varOmega _4}$ , ${{{A}}_2} \in {\varOmega _5}$ 为

$\begin{aligned}& {{{A}}_1} = \left[ {\begin{array}{*{20}{c}} 0&0&1&0 \\ 0&0&1&1 \\ 0&0&0&0 \\ 0&0&0&0 \end{array}} \right]\\& {{{A}}_2} = \left[ {\begin{array}{*{20}{l}} {{a_{55}}}&0&0&0&0 \\ 0&{{a_{66}}}&0&0&0 \\ 0&0&{{a_{77}}}&0&0 \\ 0&0&0&{{a_{88}}}&0 \\ 0&0&0&0&{{a_{99}}} \end{array}} \right]\end{aligned}$

其中， ${a_{55}},{a_{66}},{a_{77}},{a_{88}},{a_{99}} \in {F_2}$ ，矩阵 ${{A}} \in {\varOmega _9}$ 为

${{A}} = \left[ {\begin{array}{*{20}{c}} {{{{A}}_1}}&{{{{A}}_3}} \\ {{{{A}}_4}}&{{{{A}}_2}} \end{array}} \right]$

其中， ${{{A}}_3}$ 和 ${{{A}}_4}$ 为全0矩阵，记由满足上述条件的矩阵 ${{A}}$ 构成的集合为 $\varOmega _9^0$ 。

此时，对任意的 ${{A}} \in \varOmega _9^0$ , $R({{A}} \oplus {{{A}}^{\rm{T}}}) = 4$ 。由于 $\# \varOmega _9^0 = 32 > 16$ ，可定义 $F_2^4$ 到 $\varOmega _9^0$ 的单射，可以验证该单射满足定理2中的条件(1)，即函数 ${f_{\zeta ,g}}$ 为13元12阶Plateaued函数。

显然，对任意的 ${{A}} \in \varOmega _9^0$ ，有 ${{A}} \notin \varOmega _9^{{\rm{MD}}}$ 且 ${{A}} \!\notin\! \varOmega _9^{\rm{Q}}$ 。

5. 结束语

本文提出了一类新型函数结构，即TF型函数，给出了TF型函数构成Plateaued函数的充分条件，分析了该类Plateaued函数的代数次数、非线性度和弹性阶，指出了TF型Plateaued函数是包含MM型、MD型和Q型Plateaued函数的更为一般的函数类。与现有直接构造方法相比，TF型Plateaued函数形式更为一般，需要满足的条件也更为宽泛，此外，TF型函数的函数量更大，能够构造大量与现有函数类不同的Plateaued函数。

表 1 谱值与根空间维数的关系

${W_f}({{ω}} )$	${{ω}}$ 的个数
0	${2^n} - {2^{n - t}}$
${2^{(n + t)/2}}$	${2^{n - t - 1}} + {( - 1)^{f(0)}}{2^{(n - t - 2)/2}}$
$- {2^{(n + t)/2}}$	${2^{n - t - 1}} - {( - 1)^{f(0)}}{2^{(n - t - 2)/2}}$

下载: 导出CSV

SARKAR P and MAITRA S. Nonlinearity bounds and constructions of resilient Boolean functions[C]. International Cryptology Conference, California, USA, 2000: 515–532. doi: 10.1007/3-540-44598-6_32.

ZHENG Y L and ZHANG X M. On plateaued functions[J]. IEEE Transactions on Information Theory, 2001, 47(3): 1215–1223 doi: 10.1109/18.915690

Rothaus O S. On bent functions[J]. Journal of Combinatorial Theory, 1976, 20(3): 300–305 doi: 10.1016/0097-3165(76)90024-8

CARLET C. Partially bent functions[J]. Designs, Codes and Cryptography, 1993, 3(2): 135–145 doi: 10.1007/BF01388412

DILLON J F. Elementary Hadamard difference sets[D]. [Ph.D. dissertation], University of Maryland, 1974. doi: 10.13016/M2MS3K194.

MCFARLAND R L. A family of difference sets in noncyclic groups[J]. Journal of Combinatorial Theory, 1973, 15(1): 1–10 doi: 10.1016/0097-3165(73)90031-9

CAMION P, CARLET C, CHARPIN P, et al. On Correlation immune functions[C]. International Cryptology Conference, California, USA, 1991: 68–100. doi: 10.1007/3-540-46766-1_6.

CARLET C. A larger Class of Cryptographic Boolean functions via a study of the Marorana-McFarland Construction[C]. International Cryptology Conference, California, USA, 2002: 68–100. doi: 10.1007/3-540-45708-9_35.

CARLET C and PROUFF E. On plateaued functions and their construction[C]. Fast Software Encryption, Lund, Sweden, 2003: 54–73. doi: 10.1007/978-3-540-39887-5_6.

ZHENG Y L and ZHANG X M. Plateaued functions[C]. International Conference on Information and Communications Security, Berlin, Heidelberg, 1999: 284–300. doi: 10.1007/978-3-540-47942-0_24.

ZHANG F R, CARLET C, HU Y P, et al. Secondary constructions of highly nonlinear Boolean functions and disjoint spectra plateaued functions[J]. Information Sciences, 2014, 283: 94–106 doi: 10.1016/j.ins.2014.06.024

CUSICK T W. Highly nonlinear plateaued functions[J]. IET Information Security, 2017, 11(2): 78–81 doi: 10.1049/iet-ifs.2016.0131

ZHANG F R, CARLET C, HU Y P, et al. New secondary constructions of bent functions[J]. Applicable Algebra in Engineering, Communication and Computing, 2016, 27(5): 413–434 doi: 10.1007/s00200-016-0287-6

HYUN J Y, LEE J, and LEE Y. Explicit criteria for construction of plateaued functions[J]. IEEE Transactions on Information Theory, 2016, 62(12): 7555–7565 doi: 10.1109/TIT.2016.2582217

MESNAGER S, TANG C M, and QI Y F. Generalized plateaued functions and admissible (plateaued) functions[J]. IEEE Transactions on Information Theory, 2017, 63(10): 6139–6148 doi: 10.1109/TIT.2017.2715804

OLMEZ O. Plateaued functions and one-half difference sets[J]. Designs, Codes and Cryptography, 2015, 76(3): 537–549 doi: 10.1007/s10623-014-9975-z

CANTEAUT A, CHARPIN P, and KYUREGHYAN G M. A new class of monomial bent functions[J]. Finite Fields and Their Applications, 2008, 14(1): 221–241 doi: 10.1016/j.ffa.2007.02.004

期刊类型引用(1)

1.

王维琼，许豪杰，崔萌，谢琼. 优良布尔函数的混合禁忌搜索算法. 通信学报. 2022(05): 133-143 .

百度学术

其他类型引用(1)

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板