布尔函数在流密码, 分组密码以及散列函数的研究中起着重要作用.为了研究布尔函数, 人们提出了许多有关布尔函数的密码学指标.
设$\mathbb{F}_{2}$是一个二元域, $\mathbb{F}_{2}^{n}$是$\mathbb{F}_{2}$上的一个$n$维线性空间, 所谓$n$元布尔函数$B(x_1, \cdots, x_n)$是指从$\mathbb{F}_{2}^{n}$到$\mathbb{F}_{2}$的一个映射.设${{\bf{x}}}=(x_1, \cdots, x_n)$, ${{\bf{a}}}=(a_1, \cdots, a_n)\in \mathbb{F}_{2}^{n}$, 则$<{\bf{a}}, {\bf{x}}>=a_1x_1+\cdots+a_nx_n$表示通常的内积.布尔函数$B(x_1, \cdots, x_n)$的最大Fourier系数$\widehat{B}({\bf{a}})$定义为
布尔函数$B(x_1, \cdots, x_n)$的非线性定义如下
每一个布尔函数都可以唯一地表示成多项式的形式, 称为布尔函数的代数正规型:
布尔函数的稀疏性${\rm{spr}}(B)$是代数正规型中非零系数单项式的个数.此外布尔函数的平均灵敏度$\sigma_{av}(B)$定义如下
其中${\bf{a}}^{(i)}$是${\bf{a}}$改变第$i$个坐标后所得的向量.
近几年来, 一些密码学研究者从数论的角度出发构造了许多具有``好''的密码学性质的布尔函数.例如, Coppersmith与Shparlinski[1]利用模$p$的二次剩余构造了如下的布尔函数.
命题1.1 设$p$为奇素数, $s=\lfloor\log_2 p\rfloor$, 其中$\lfloor x\rfloor$表示不超过$x$的最大整数.定义布尔函数为
其中$u_j\in\{0, 1\}$且$1\leq j\leq s$.则有
Lange与Winterhof[2]将上述命题进行了推广.
命题1.2 设$p$为奇素数, $\mathbb{F}_{q}$是阶为$q=p^r (r\geq1)$的有限域, $\beta_0, \cdots, \beta_{r-1}$是$\mathbb{F}_{q}$在$\mathbb{F}_{p}$上的一组基, $s=\lfloor\log_2 p\rfloor$.定义布尔函数如下
其中$k_{i-1}=u_{i1}+u_{i2}\cdot 2+\cdots+u_{is}\cdot 2^{s-1}, $ $u_{ij}\in\{0, 1\}$且$1\leq j\leq s$, $1\leq i\leq r.$则有
随后文献[3]中进一步研究了命题1.2中布尔函数的性质, 得到了以下结果.
命题1.3 设$p, r, s, B$如以上命题所定义.则有
最近几十年来, 随着数论、组合以及相关学科的发展, 伪随机子集得到了深入的研究和广泛的应用.许多论文都是关于这一领域的, 这些论文中提出了大量的思想、方法和工具. 1992年, Chung与Graham[4]发现整数环的子集具有一类令人惊奇的互相等价的性质, 并且如果一个子集满足这类性质中的任何一条, 则满足其余性质. Gowers[5]对整数环的伪随机子集进行了具体的数量分析, 利用所定义的Gowers范数, 在整数环的子集引入了新的伪随机测度, 进而给出了Szemerédi定理的新证明.
伪随机子集不仅有着深刻的理论意义, 还在网络安全、密码学等领域中具有广泛的应用.研究者发现伪随机子集可以提高密钥预分配过程的效率和安全性, 进而改善密钥管理、广播认证协议、无线传感网络的过程(参阅文献 [6]), 另外还可用于构造匿名路径以避免路径信息被窃听(参阅文献[7]与[8]).
本文将利用伪随机子集构造大族的布尔函数, 并在第2节到第4节中证明下面的结论.
定理1.1 设$p$为奇素数, $q=p^r$, $\mathbb{F}_q$为有限域, $A\subset \mathbb{F}_q$是$\mathbb{F}_q$的子集, 满足
其中$\displaystyle\sum_{\chi\neq \chi^0}$表示对$\mathbb{F}_q$的所有非平凡乘法特征求和.设$\beta_0, \cdots, \beta_{r-1}$是$\mathbb{F}_{q}$在$\mathbb{F}_{p}$上的一组基.定义$s=\lfloor\log_2 p\rfloor$, 并设$u_{ij}\in\{0, 1\}$, $1\leq j\leq s$, $1\leq i\leq r$.记$k_{i-1}=u_{i1}+u_{i2}\cdot 2+\cdots+u_{is}\cdot 2^{s-1}$, $1\leq i\leq r$.定义
则有
注 设$p$为奇素数, $q=p^r$, $\mathbb{F}_q$为有限域.定义$ A=\left\{a: a\in \mathbb{F}_q, a \hbox{是} \mathbb{F}_q \hbox{上的平方}\right\}. $不难证明
因此本文是对文献[2]与[3]的推广.
首先介绍下面的引理.
引理2.1 设$p$为奇素数, $q=p^n$, $\chi$为有限域$\mathbb{F}_q$上的$d(d>1)$阶乘法特征, $v_1, \cdots, v_n$是$\mathbb{F}_{q}$在$\mathbb{F}_{p}$上的一组基.设$f(x)\in \mathbb{F}_q[x]$不能表为$\mathbb{F}_{q}$上任何多项式的$d$次幂的常数倍, 且在它的分裂域中有$m$个不同的根.定义
其中$t_1$, $\cdots$, $t_n$是非负整数且$t_1< p$, $\cdots$, $t_n< p$.则有
证 参阅文献[9]中的定理2.
现在考虑布尔函数的最大Fourier系数.设$z\in \mathbb{F}_{q}^*$, 易证
记$k_{i-1}=u_{i1}+u_{i2}\cdot 2+\cdots+u_{is}\cdot 2^{s-1}$, 其中$u_{ij}\in\{0, 1\}$, $1\leq j\leq s$, $1\leq i\leq r$.定义
对于任意${\bf{a}}\in \mathbb{F}_{2}^{rs}$, 可得
其中$z=k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}$, $k_{i-1}=u_{i1}+u_{i2}\cdot 2+\cdots+u_{is}\cdot 2^{s-1}$, $1\leq i\leq r$, 且
令$ S({\bf{a}})=\sum_{z\in \mathcal{H}_{2^s}}\chi(z)(-1)^{<z, {\bf{a}}>}, $可得
根据文献[3]中的方法, 设$x$是一个整数且$1<x<s$, 则有
显然任意$z\in \mathcal{H}_{2^s}$都能唯一地表为$z=y+w$, 其中$y\in \mathcal{H}_{2^x}$, 且
定义
易知$\displaystyle <z, {\bf{a}}>=<y, {{\bf{b}}}>+<w, {\bf{c}}>$.由Cauchy-Schwarz不等式有
再由引理2.1可得
设实数$x_0$满足
并取$x=\lfloor x_0\rfloor+1$, 有
结合(2.1)与(2.2)式可得
注意到
因此
这就证明了(1.4)式.又由于$s=\lfloor\log_2 p\rfloor>\log_2 p-1$, 则有
从而可得(1.5)式.
设整数$a$满足$\displaystyle2^{a}>\left({\rm{spr}}(B)+1\right)^{\frac{1}{r}} \geq2^{a-1}$.令$\mathcal{M}=\left\{0, \cdots, 2^{a}-1\right\}^{r}\backslash \left\{(0, \cdots, 0)\right\}$, 对每一个$\underline{m}=(m_1, \cdots, m_r)\in\mathcal{M}$, 定义函数
其中$m_{i}=m_{i1}+\cdots+m_{ia}2^{a-1}$, $m_{ij}\in\{0, 1\}$, $1\leq j\leq a$, $1\leq i\leq r$.对于定义在$u_{11}, \cdots, u_{1(s-a)}, \cdots, u_{r1}, \cdots, u_{r(s-a)}$的所有$B_{\underline{m}}$中, 不同单项式的个数不超过$ {\rm{spr}}(B)$.注意到$|\mathcal{M}|=2^{ar}-1>{\rm{spr}}(B)$, 则可以找到非平凡的线性组合, 使得
容易证明
其中$y\in \mathcal{H}_{2^{s-a}}$, $w\in 2^{s-a}\mathcal{H}_{2^{a}}\backslash \{0\}$, 且$\underline{m}\in\mathcal{M}$与$w\in 2^{s-a}\mathcal{H}_{2^{a}}\backslash \{0\}$是一一对应的.
以及$L=\left|\mathcal{N}\right|$.则有
为方便起见, 记$\mathcal{N}=\{w_1, w_2, \cdots, w_L\}$.可得
设$\chi'$是$\mathbb{F}_q$的乘法特征群的生成元, 其阶为$q-1$.则可把$\chi_1, \cdots, \chi_L$分别写成
其中$1\leq a_1, \cdots, a_L\leq q-2$.定义
则$\chi^*$的阶为$q-1$的大于$1$的因数, $1\leq \delta_1, \cdots, \delta_L\leq q-2$, 且$(\delta_1, \cdots, \delta_L)=1$.从而
注意到$w_1, \cdots, w_L$互不相同, 且$(\delta_1, \cdots, \delta_L)=1$.则$(y+w_1)^{\delta_1}\cdots(y+w_L)^{\delta_L}$不可能表为某个多项式的$d>1$次幂.由引理2.1可得
注意到$s=\lfloor\log_2 p\rfloor>\log_2 p-1$, 有$ 2^{ar}>2^{-\frac{r}{2}}q^{\frac{1}{4}}\left(\log p+1\right)^{-\frac{r}{2}}. $从而$ {\rm{spr}}(B)\geq \left(2^{a-1}\right)^r-1>2^{-\frac{3}{2}r}q^{\frac{1}{4}} \left(\log p+1\right)^{-\frac{r}{2}}-1. $这就证明了(1.6)式.
令
并记$ B'(k)=B(u_{11}, \cdots, u_{1s}, \cdots, u_{r1}, \cdots, u_{rs}), $其中
且
根据文献[3]中的方法, 以及引理2.1可得
这就证明了(1.7)式.
利用相同的方法, 还可构造范围更大的布尔函数族, 并证明下面的结论.
定理5.1 设$p$为奇素数, $q=p^r$, $\mathbb{F}_q$为有限域, $A\subset \mathbb{F}_q$是$\mathbb{F}_q$的子集, 满足
设$\beta_0, \cdots, \beta_{r-1}$是$\mathbb{F}_{q}$在$\mathbb{F}_{p}$上的一组基.定义$s=\lfloor\log_2 p\rfloor$, 并设$u_{ij}\in\{0, 1\}$, $1\leq j\leq s$, $1\leq i\leq r$.记$k_{i-1}=u_{i1}+u_{i2}\cdot 2+\cdots+u_{is}\cdot 2^{s-1}$, $1\leq i\leq r$.定义
注 满足定理5.1中的条件的子集有很多个.例如, 设$g$是$\mathbb{F}_q^*$的生成元, 则下列子集
都满足定理5.1的要求.