数学杂志  2018, Vol. 38 Issue (1): 167-176   PDF    
扩展功能
加入收藏夹
复制引文信息
加入引用管理器
Email Alert
RSS
本文作者相关文章
刘华宁
陈晓林
基于伪随机子集生成的Boolean函数
刘华宁, 陈晓林    
西北大学数学学院, 陕西 西安 710127
摘要:本文基于有限域中的伪随机子集,构造了大族Boolean函数并研究了其性质.利用有限域中特征和估计的方法,分析了Boolean函数的非线性,平均灵敏度与稀疏性,给出了估计式.推广并改进了相关领域的已有结果.
关键词Boolean函数    最大Fourier系数    非线性    平均灵敏度    稀疏性    
LARGE FAMILY OF BOOLEAN FUNCTIONS CONSTRUCTED BY USING PSEUDORANDOM SUBSETS
LIU Hua-ning, CHEN Xiao-lin    
School of Mathematics, Northwest University, Xi'an 710127, China
Abstract: In this paper, we study the cryptography properties of large families of Boolean functions constructed by the pseudorandom subsets in finite fields. Using bounds on character sums over finite fields, we obtain lower bounds on the nonlinearity, average sensitivity and sparsity, which generalizes the previous results.
Key words: Boolean function     maximum Fourier coefficient     nonlinearity     average sensitivity     sparsity    
1 引言

布尔函数在流密码, 分组密码以及散列函数的研究中起着重要作用.为了研究布尔函数, 人们提出了许多有关布尔函数的密码学指标.

$\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}})$定义为

$ \widehat{B}({\bf{a}})=\sum\limits_{{\bf{x}}\in \mathbb{F}_{2}^{n}}(-1)^{B({\bf{x}})+<{\bf{a}}, {\bf{x}}>}. $

布尔函数$B(x_1, \cdots, x_n)$的非线性定义如下

$ nl(B)=2^{n-1}-\frac{1}{2}\max\limits_{{\bf{a}}\in \mathbb{F}_{2}^{n}}\left|\widehat{B}({\bf{a}})\right|. $

每一个布尔函数都可以唯一地表示成多项式的形式, 称为布尔函数的代数正规型:

$ B(x_1, \cdots, x_n)=\sum\limits_{I\subseteq\{1, 2, \cdots, n\}}a_{I}\prod\limits_{i\in I}x_i, \qquad a_{I}\in\mathbb{F}_{2}. $

布尔函数的稀疏性${\rm{spr}}(B)$是代数正规型中非零系数单项式的个数.此外布尔函数的平均灵敏度$\sigma_{av}(B)$定义如下

$ \sigma_{av}(B)=2^{-n}\sum\limits_{{\bf{a}}\in \mathbb{F}_{2}^{n}}\sum\limits_{i=1}^{n}\left|B({\bf{a}})-B({\bf{a}}^{(i)})\right|, $

其中${\bf{a}}^{(i)}$${\bf{a}}$改变第$i$个坐标后所得的向量.

近几年来, 一些密码学研究者从数论的角度出发构造了许多具有``好''的密码学性质的布尔函数.例如, Coppersmith与Shparlinski[1]利用模$p$的二次剩余构造了如下的布尔函数.

命题1.1 设$p$为奇素数, $s=\lfloor\log_2 p\rfloor$, 其中$\lfloor x\rfloor$表示不超过$x$的最大整数.定义布尔函数为

$ \begin{eqnarray} B(u_1, \cdots, u_s)=\left\{\begin{array}{ll} 0,&\hbox{如果 } u_1+u_2\cdot 2+\cdots+u_s\cdot 2^{s-1} \hbox{是} \mathbb{F}_p \hbox{上的二次剩余}, \\ 1,&\hbox{如果 } u_1+u_2\cdot 2+\cdots+u_s\cdot 2^{s-1} \hbox{ 是} \mathbb{F}_p \hbox{上的二次非剩余}, \end{array}\right. \end{eqnarray} $ (1.1)

其中$u_j\in\{0, 1\}$$1\leq j\leq s$.则有

$ \begin{eqnarray*} &&{\rm{spr}}(B)\geq 2^{-\frac{3}{2}}p^{\frac{1}{4}}(\log_2 p)^{-\frac{1}{2}}-1, &&\sigma_{av}(B)\geq 0.5s+o(s). \end{eqnarray*} $

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$.定义布尔函数如下

$ \begin{eqnarray} &&\;\;\;\;B(u_{11}, \cdots, u_{1s}, \cdots, u_{r1}, \cdots, u_{rs})\nonumber\\ &&=\left\{\begin{array}{ll} 0,&\hbox{如果 } k_0\beta_0+\cdots+k_{r-1}\beta_{r-1} \hbox{是} \mathbb{F}_q \hbox{上的平方}, \\ 1,&\hbox{如果 } k_0\beta_0+\cdots+k_{r-1}\beta_{r-1} \hbox{是 } \mathbb{F}_q \hbox{上的非平方}, \end{array}\right. \end{eqnarray} $ (1.2)

其中$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.$则有

$ {\rm{spr}}(B)\geq \left(2^{-\frac{3}{2}}\left(3^{\frac{1}{r}}+r\right)^{-\frac{1}{2}}p^{\frac{1}{4}}\right)^r-1. $

随后文献[3]中进一步研究了命题1.2中布尔函数的性质, 得到了以下结果.

命题1.3 设$p, r, s, B$如以上命题所定义.则有

$ \begin{eqnarray*} &&\max\limits_{{\bf{a}}\in \mathbb{F}_{2}^{rs}}\left|\widehat{B}({\bf{a}})\right|\leq 2^{\frac{2r+3}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}+1, \\ &&\sigma_{av}(B)\geq 0.5rs+o(rs). \end{eqnarray*} $

最近几十年来, 随着数论、组合以及相关学科的发展, 伪随机子集得到了深入的研究和广泛的应用.许多论文都是关于这一领域的, 这些论文中提出了大量的思想、方法和工具. 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$的子集, 满足

$ 0\not\in A, \qquad |A|=\frac{q-1}{2}, \quad\hbox{与}\quad \sum\limits_{\chi\neq \chi^0}\left|\sum\limits_{b\in A}\chi(b)\right|=\frac{q-1}{2}, $

其中$\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$.定义

$ \begin{eqnarray} &&\;\;\;\;B(u_{11}, \cdots, u_{1s}, \cdots, u_{r1}, \cdots, u_{rs})\nonumber\\ &&=\left\{\begin{array}{ll} 0,&\hbox{如果 } k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}\in A, \\ 1,&\hbox{如果 } k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}\not\in A. \end{array}\right. \end{eqnarray} $ (1.3)

则有

$ \max\limits_{{\bf{a}}\in \mathbb{F}_{2}^{rs}}\left|\widehat{B}({\bf{a}})\right| \leq 2^{\frac{2r+3}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}-\frac{1}{2^{\frac{8r+3}{4}}}q^{\frac{5}{8}}\left(\log p+1\right)^{\frac{3r}{4}}, $ (1.4)
$ nl(B)\geq \frac{q}{2^{r+1}}-2^{\frac{2r-1}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}+\frac{1}{2^{\frac{8r+7}{4}}}q^{\frac{5}{8}}\left(\log p+1\right)^{\frac{3r}{4}}, $ (1.5)
$ {\rm{spr}}(B)\geq 2^{-\frac{3}{2}r}q^{\frac{1}{4}} \left(\log p+1\right)^{-\frac{r}{2}}-1, $ (1.6)
$ \sigma_{av}(B)\geq 0.5rs+o(rs). $ (1.7)

  设$p$为奇素数, $q=p^r$, $\mathbb{F}_q$为有限域.定义$ A=\left\{a: a\in \mathbb{F}_q, a \hbox{是} \mathbb{F}_q \hbox{上的平方}\right\}. $不难证明

$ 0\not\in A, \qquad |A|=\frac{q-1}{2}, \quad\hbox{与}\quad \sum\limits_{\chi\neq \chi^0}\left|\sum\limits_{b\in A}\chi(b)\right|=\frac{q-1}{2}. $

因此本文是对文献[2]与[3]的推广.

2 最大Fourier系数与非线性

首先介绍下面的引理.

引理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$个不同的根.定义

$ B=\left\{\sum\limits_{i=1}^nj_iv_i: 0\leq j_i\leq t_i, i=1, 2, \cdots, n\right\}, $

其中$t_1$, $\cdots$, $t_n$是非负整数且$t_1< p$, $\cdots$, $t_n< p$.则有

$ \left|\sum\limits_{z\in B}\chi\left(f(z)\right)\right|<mq^{\frac{1}{2}}\left(1+\log p\right)^n. $

 参阅文献[9]中的定理2.

现在考虑布尔函数的最大Fourier系数.设$z\in \mathbb{F}_{q}^*$, 易证

$ \begin{eqnarray*} \frac{2}{q-1}\sum\limits_{b\in A}\sum\limits_{\chi}\chi(z)\chi\left(b^{-1}\right)-1 =\left\{\begin{array}{ll} 1,&\hbox{当} z\in A, \\ -1,&\hbox{当} z\not\in A. \end{array} \right. \end{eqnarray*} $

$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$.定义

$ \mathcal{H}_{2^s}=\left\{k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}: 0\leq k_{i-1}\leq 2^{s}-1, i=1, \cdots, r\right\}. $

对于任意${\bf{a}}\in \mathbb{F}_{2}^{rs}$, 可得

$ \begin{eqnarray*} \widehat{B}({\bf{a}})&=&\sum\limits_{{\bf{x}}\in \mathbb{F}_{2}^{rs}}(-1)^{B({\bf{x}})+<{\bf{a}}, {\bf{x}}>} =\sum\limits_{z\in \mathcal{H}_{2^s}^*}\left(\frac{2}{q-1}\sum\limits_{b\in A}\sum\limits_{\chi}\chi(z)\chi\left(b^{-1}\right)-1\right)\cdot (-1)^{<z, {\bf{a}}>}-1 \\ &=&\sum\limits_{z\in \mathcal{H}_{2^s}^*}\left(\frac{2}{q-1}\sum\limits_{b\in A}\sum\limits_{\chi\neq\chi^0}\chi(z)\chi\left(b^{-1}\right)\right)\cdot (-1)^{<z, {\bf{a}}>}-1\\ &=&\frac{2}{q-1}\sum\limits_{\chi\neq\chi^0}\left(\sum\limits_{b\in A}\chi\left(b^{-1}\right)\right)\sum\limits_{z\in \mathcal{H}_{2^s}^*}\chi(z)(-1)^{<z, {\bf{a}}>}-1, \end{eqnarray*} $

其中$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$, 且

$ <z, {\bf{a}}>=\left<\left(u_{11}, \cdots, u_{1s}, \cdots, u_{r1}, \cdots, u_{rs}\right), {\bf{a}}\right>. $

$ S({\bf{a}})=\sum_{z\in \mathcal{H}_{2^s}}\chi(z)(-1)^{<z, {\bf{a}}>}, $可得

$ \begin{eqnarray} \left|\widehat{B}({\bf{a}})\right|&\leq&\frac{2}{q-1}\sum\limits_{\chi\neq\chi^0}\left|\sum\limits_{b\in A}\chi\left(b^{-1}\right)\right|\cdot \left|S({\bf{a}})\right|+1. \end{eqnarray} $ (2.1)

根据文献[3]中的方法, 设$x$是一个整数且$1<x<s$, 则有

$ \begin{eqnarray*} k_{i-1}&=&u_{i1}+u_{i2}\cdot 2+\cdots+u_{is}\cdot 2^{s-1}\\ &=&u_{i1}+u_{i2}\cdot 2+\cdots+u_{ix}\cdot 2^{x-1}\\ &&+u_{i(x+1)}\cdot 2^x+u_{i(x+2)}\cdot 2^{x+1}+\cdots+u_{is}\cdot 2^{s-1}\\ &=&u_{i1}+u_{i2}\cdot 2+\cdots+u_{ix}\cdot 2^{x-1}\\ &&+2^{x}\left(u_{i(x+1)}+u_{i(x+2)}\cdot 2+\cdots+u_{is}\cdot 2^{s-x-1}\right). \end{eqnarray*} $

显然任意$z\in \mathcal{H}_{2^s}$都能唯一地表为$z=y+w$, 其中$y\in \mathcal{H}_{2^x}$, 且

$ \begin{eqnarray*} w\in 2^x\mathcal{H}_{2^{s-x}}&=&\left\{2^{x}\left(k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}\right): 0\leq k_{i-1}\leq 2^{s-x}-1, i=1, \cdots, r\right\}. \end{eqnarray*} $

定义

$ \begin{eqnarray*} {\bf{a}}&=&\left(a_{11}, \cdots, a_{1s}, \cdots, a_{r1}, \cdots, a_{rs}\right), \\ {\bf{b}}&=&\left(a_{11}, \cdots, a_{1x}, \cdots, a_{r1}, \cdots, a_{rx}\right), \\ {\bf{c}}&=&\left(a_{1(x+1)}, \cdots, a_{1s}, \cdots, a_{r(x+1)}, \cdots, a_{rs}\right). \end{eqnarray*} $

易知$\displaystyle <z, {\bf{a}}>=<y, {{\bf{b}}}>+<w, {\bf{c}}>$.由Cauchy-Schwarz不等式有

$ \begin{eqnarray*} &&\left|S({\bf{a}})\right|^2=\left|\sum\limits_{y\in \mathcal{H}_{2^x}}\sum\limits_{w\in 2^x\mathcal{H}_{2^{s-x}}}\chi(y+w)(-1)^{<y, {\bf{b}}>+<w, {\bf{c}}>}\right|^2\\ &&\leq\left(\sum\limits_{y\in \mathcal{H}_{2^x}}\left|\sum\limits_{w\in 2^x\mathcal{H}_{2^{s-x}}}\chi(y+w)(-1)^{<w, {\bf{c}}>}\right|\right)^2\\ &&\leq2^{rx}\sum\limits_{y\in \mathcal{H}_{2^x}}\left|\sum\limits_{w\in 2^x\mathcal{H}_{2^{s-x}}}\chi(y+w)(-1)^{<w, {\bf{c}}>}\right|^2\\ &&=2^{rx}\sum\limits_{y\in \mathcal{H}_{2^x}}\sum\limits_{w_1\in 2^x\mathcal{H}_{2^{s-x}}}\sum\limits_{w_2\in 2^x\mathcal{H}_{2^{s-x}}}\chi\left((y+w_1)(y+w_2)\right)\cdot(-1)^{<w_1, {\bf{c}}>+<w_2, {\bf{c}}>}\\ &&\leq2^{rx}\sum\limits_{w_1\in 2^x\mathcal{H}_{2^{s-x}}}\sum\limits_{w_2\in 2^x\mathcal{H}_{2^{s-x}}}\left|\sum\limits_{y\in \mathcal{H}_{2^x}}\chi\left((y+w_1)(y+w_2)\right)\right|\\ &&\leq2^{rx+rs}+2^{rx}\mathop{\sum\limits_{w_1\in 2^x\mathcal{H}_{2^{s-x}}}\sum\limits_{w_2\in 2^x\mathcal{H}_{2^{s-x}}}}_{w_1\neq w_2}\left|\sum\limits_{y\in \mathcal{H}_{2^x}}\chi\left((y+w_1)(y+w_2)\right)\right|. \end{eqnarray*} $

再由引理2.1可得

$ \begin{eqnarray*} \left|S(\mathbf{a})\right|^2&<&2^{rx+rs}+2^{rx}\cdot 2^{r(s-x)}\left(2^{r(s-x)}-1\right)\cdot 2q^{\frac{1}{2}}\left(1+\log p\right)^r\\ &=&2^{rx+rs}+2^{2rs-rx}\cdot 2q^{\frac{1}{2}}\left(1+\log p\right)^r-2^{rs}\cdot 2q^{\frac{1}{2}}\left(1+\log p\right)^r. \end{eqnarray*} $

设实数$x_0$满足

$ 2^{rx_0+rs}= 2^{2rs-rx_0}\cdot 2q^{\frac{1}{2}}\left(1+\log p\right)^r\quad\hbox{即}\quad 2^{rx_0}=2^{\frac{rs}{2}}2^{\frac{1}{2}}q^{\frac{1}{4}}\left(1+\log p\right)^{\frac{r}{2}}, $

并取$x=\lfloor x_0\rfloor+1$, 有

$ \begin{eqnarray} \left|S(\mathbf{a})\right|^2&<&2\cdot 2^{rx+rs}-2^{rs}\cdot 2q^{\frac{1}{2}}\left(1+\log p\right)^r<2\cdot 2^{r(x_0+1)+rs}-2^{rs}\cdot 2q^{\frac{1}{2}}\left(1+\log p\right)^r\nonumber\\ &=&2^{r+\frac{3}{2}}2^{\frac{3rs}{2}}q^{\frac{1}{4}}\left(1+\log p\right)^{\frac{r}{2}}-2^{rs+1}q^{\frac{1}{2}}\left(1+\log p\right)^r\nonumber\\ &\leq& 2^{r+\frac{3}{2}}q^{\frac{7}{4}}\left(1+\log p\right)^{\frac{r}{2}}-\frac{1}{2^{r-1}}q^{\frac{3}{2}}\left(1+\log p\right)^r. \end{eqnarray} $ (2.2)

结合(2.1)与(2.2)式可得

$ \begin{eqnarray*} \left|\widehat{B}({\bf{a}})\right|&\leq& \sqrt{2^{r+\frac{3}{2}}q^{\frac{7}{4}}\left(1+\log p\right)^{\frac{r}{2}}-\frac{1}{2^{r-1}}q^{\frac{3}{2}}\left(1+\log p\right)^r}+1. \end{eqnarray*} $

注意到

$ \begin{eqnarray*} && \;\;\;2^{\frac{2r+3}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}-\sqrt{2^{\frac{2r+3}{2}}q^{\frac{7}{4}}\left(\log p+1\right)^{\frac{r}{2}}-\frac{1}{2^{r-1}}q^{\frac{3}{2}}\left(1+\log p\right)^r}-1\\ &&\geq \frac{1}{2^{\frac{8r+3}{4}}}q^{\frac{5}{8}}\left(\log p+1\right)^{\frac{3r}{4}}, \end{eqnarray*} $

因此

$ \begin{eqnarray*} \left|\widehat{B}({\bf{a}})\right|&\leq& \sqrt{2^{r+\frac{3}{2}}q^{\frac{7}{4}}\left(1+\log p\right)^{\frac{r}{2}}-\frac{1}{2^{r-1}}q^{\frac{3}{2}}\left(1+\log p\right)^r}+1\\ &\leq&2^{\frac{2r+3}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}-\frac{1}{2^{\frac{8r+3}{4}}}q^{\frac{5}{8}}\left(\log p+1\right)^{\frac{3r}{4}}. \end{eqnarray*} $

这就证明了(1.4)式.又由于$s=\lfloor\log_2 p\rfloor>\log_2 p-1$, 则有

$ \begin{eqnarray*} nl(B)&=&2^{rs-1}-\frac{1}{2}\max\limits_{{\bf{a}}\in \mathbb{F}_{2}^{rs}}\left|\widehat{B}({\bf{a}})\right|\\ &>&2^{r\log_2 p-r-1}-2^{\frac{2r-1}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}+\frac{1}{2^{\frac{8r+7}{4}}}q^{\frac{5}{8}}\left(\log p+1\right)^{\frac{3r}{4}} \\ &=&\frac{q}{2^{r+1}}-2^{\frac{2r-1}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}+\frac{1}{2^{\frac{8r+7}{4}}}q^{\frac{5}{8}}\left(\log p+1\right)^{\frac{3r}{4}}. \end{eqnarray*} $

从而可得(1.5)式.

3 稀疏性

设整数$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}$, 定义函数

$ \begin{eqnarray*} &&\;\;\;B_{\underline{m}}(u_{11}, \cdots, u_{1(s-a)}, \cdots, u_{r1}, \cdots, u_{r(s-a)}) \\ &&=B(u_{11}, \cdots, u_{1(s-a)}, m_{11}, \cdots, m_{1a}, \cdots, u_{r1}, \cdots, u_{r(s-a)}, m_{r1}, \cdots, m_{ra}), \end{eqnarray*} $

其中$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)$, 则可以找到非平凡的线性组合, 使得

$ \sum\limits_{\underline{m}\in\mathcal{M}}c_{\underline{m}}B_{\underline{m}} (u_{11}, \cdots, u_{1(s-a)}, \cdots, u_{r1}, \cdots, u_{r(s-a)})=0, \qquad c_{\underline{m}}\in\mathbb{F}_2. $

定义

$ \begin{eqnarray*} &&\mathcal{H}_{2^{s-a}}=\left\{k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}: 0\leq k_{i-1}\leq 2^{s-a}-1, i=1, \cdots, r\right\}, \\ &&2^{s-a}\mathcal{H}_{2^{a}}=\left\{2^{s-a}\left(k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}\right): 0\leq k_{i-1}\leq 2^{a}-1, i=1, \cdots, r\right\}. \end{eqnarray*} $

容易证明

$ \begin{eqnarray*} &&\;\;\;\;\;c_{\underline{m}}B_{\underline{m}} (u_{11}, \cdots, u_{1(s-a)}, \cdots, u_{r1}, \cdots, u_{r(s-a)})\\ &&=c_{\underline{m}}B(u_{11}, \cdots, u_{1(s-a)}, m_{11}, \cdots, m_{1a}, \cdots, u_{r1}, \cdots, u_{r(s-a)}, m_{r1}, \cdots, m_{ra})\\ &&=c_wB\left(y+w\right), \end{eqnarray*} $

其中$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\}$是一一对应的.

定义

$ \mathcal{N}=\left\{w\in 2^{s-a}\mathcal{H}_{2^{a}}\backslash \{0\}: \hbox{与$w$ 对应的$\underline{m}$ 满足s $c_{\underline{m}}=1$}\right\}, $

以及$L=\left|\mathcal{N}\right|$.则有

$ \begin{eqnarray*} 2^{(s-a)r}&=&\sum\limits_{u_{11}=0}^{1}\cdots\sum\limits_{u_{1(s-a)}=0}^{1}\cdots\sum\limits_{u_{r1}=0}^{1}\cdots\sum\limits_{u_{r(s-a)}=0}^{1}1\\ &=&\sum\limits_{u_{11}=0}^{1}\cdots\sum\limits_{u_{1(s-a)}=0}^{1}\cdots\sum\limits_{u_{r1}=0}^{1}\cdots\sum\limits_{u_{r(s-a)}=0}^{1} (-1)^{\sum\limits_{\underline{m}\in\mathcal{M}}c_{\underline{m}}B_{\underline{m}} (u_{11}, \cdots, u_{1(s-a)}, \cdots, u_{r1}, \cdots, u_{r(s-a)})}\\ &=&\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}(-1)^{\sum\limits_{w\in \mathcal{N}}B(y+w)}=\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\prod\limits_{w\in \mathcal{N}}(-1)^{B(y+w)}\\ &=&\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\prod\limits_{w\in \mathcal{N}}\left(\frac{2}{q-1}\sum\limits_{b\in A}\sum\limits_{\chi}\chi(y+w)\chi\left(b^{-1}\right)-1\right)\\ &=&\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\prod\limits_{w\in \mathcal{N}}\left(\frac{2}{q-1}\sum\limits_{b\in A}\sum\limits_{\chi\neq\chi^0}\chi\left(b^{-1}\right)\chi(y+w)\right). \end{eqnarray*} $

为方便起见, 记$\mathcal{N}=\{w_1, w_2, \cdots, w_L\}$.可得

$ \begin{eqnarray*} 2^{(s-a)r}&=&\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\left(\frac{2}{q-1}\sum\limits_{b_1\in A}\sum\limits_{\chi_1\neq\chi^0}\chi_1\left(b_1^{-1}\right)\chi_1(y+w_1)\right)\\ &&\qquad\times\cdots\times\left(\frac{2}{q-1}\sum\limits_{b_L\in A}\sum\limits_{\chi_L\neq\chi^0}\chi_L\left(b_L^{-1}\right)\chi_L(y+w_L)\right)\\ &=&\frac{2^L}{(q-1)^L}\sum\limits_{\chi_1\neq\chi^0}\sum\limits_{b_1\in A}\chi_1\left(b_1^{-1}\right)\cdots\sum\limits_{\chi_L\neq\chi^0}\sum\limits_{b_L\in A}\chi_L\left(b_L^{-1}\right)\\ &&\qquad\times\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\chi_1(y+w_1)\cdots\chi_L(y+w_L). \end{eqnarray*} $

$\chi'$$\mathbb{F}_q$的乘法特征群的生成元, 其阶为$q-1$.则可把$\chi_1, \cdots, \chi_L$分别写成

$ \chi_1=(\chi')^{a_1}, \cdots, \chi_L=(\chi')^{a_L}, $

其中$1\leq a_1, \cdots, a_L\leq q-2$.定义

$ \chi^*=\left(\chi'\right)^{(a_1, \cdots, a_L)}, \quad \delta_1=\frac{a_1}{(a_1, \cdots, a_L)}, \quad \cdots, \quad\delta_L=\frac{a_L}{(a_1, \cdots, a_L)}, $

$\chi^*$的阶为$q-1$的大于$1$的因数, $1\leq \delta_1, \cdots, \delta_L\leq q-2$, 且$(\delta_1, \cdots, \delta_L)=1$.从而

$ \sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\chi_1(y+w_1)\cdots\chi_L(y+w_L) =\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\chi^*\left((y+w_1)^{\delta_1}\cdots(y+w_L)^{\delta_L}\right). $

注意到$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可得

$ \begin{eqnarray*} \left|\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\chi_1(y+w_1)\cdots\chi_L(y+w_L)\right| &=&\left|\sum\limits_{y\in \mathcal{H}_{2^{s-a}}}\chi^*\left((y+w_1)^{\delta_1}\cdots(y+w_L)^{\delta_L}\right)\right|\\ &<&Lq^{\frac{1}{2}}\left(\log p+1\right)^r. \end{eqnarray*} $

因此

$ 2^{(s-a)r}<Lq^{\frac{1}{2}}\left(\log p+1\right)^r\leq \left(2^{ar}-1\right)q^{\frac{1}{2}}\left(\log p+1\right)^r. $

注意到$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)式.

4 平均灵敏度

$ M=\lfloor s^{\frac{1}{2}}\rfloor, \quad H=2M+1, \quad J=\lfloor s-s^{\frac{1}{2}}\rfloor, \quad K=2^{s}-H2^{J}, $

并记$ B'(k)=B(u_{11}, \cdots, u_{1s}, \cdots, u_{r1}, \cdots, u_{rs}), $其中

$ k=k_0+k_1p+\cdots+k_{r-1}p^{r-1}, \quad 0\leq k_{i-1}\leq p-1, \quad 1\leq i\leq r, $

$ k_{i-1}=u_{i1}+u_{i2}\cdot2+\cdots+u_{is}\cdot2^{s-1}, \quad u_{ij}\in\{0, 1\}, \quad 1\leq j\leq s, \quad 1\leq i\leq r. $

定义

$ \begin{eqnarray*} \mathcal{H}'_{K}=\left\{k_0+k_1p+\cdots+k_{r-1}p^{r-1}: 0\leq k_{i-1}\leq K-1, i=1, \cdots, r\right\}. \end{eqnarray*} $

根据文献[3]中的方法, 以及引理2.1可得

$ \begin{eqnarray*} \sigma_{av}(B)&=&2^{-rs}\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{s}\mathop {\sum\limits_{k\in\mathcal{H}'_{2^{s}}}}_{B'(k)\neq B'(k^{(ij)})}1 \geq2^{-rs}\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{J}\mathop {\sum\limits_{k\in\mathcal{H}'_{2^{s}}}}_{B'(k)\neq B'(k^{(ij)})}1\\ &=&2^{-rs}M^{-1}\left(\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{J} \sum\limits_{h=1}^{M}\left|\mathop{\sum\limits_{k\in\mathcal{H}'_{K}}} _{B'(k+h2^{j}p^{i-1})\neq B'((k+h2^{j}p^{i-1})^{(ij)})}1 -\mathop{\sum\limits_{k\in\mathcal{H}'_{2^{s}}}}_{B'(k) \neq B'(k^{(ij)})}1\right|\right.\\ &&\left.\qquad+\sum\limits_{i=1}^{r}\sum\limits_{j=1}^{J}\sum\limits_{k\in\mathcal{H}'_{K}} \mathop{\sum\limits_{h=1}^{M}}_{B'(k+h2^{j}p^{i-1})\neq B'((k+h2^{j}p^{i-1})^{(ij)})}1\right)\\ &\geq&2^{-rs}M^{-1}(o(rJM2^{rs})+0.5JK^{r}rM+o(JK^{r}rM))\\ &\geq&0.5rs+o(rs). \end{eqnarray*} $

这就证明了(1.7)式.

5 进一步的讨论

利用相同的方法, 还可构造范围更大的布尔函数族, 并证明下面的结论.

定理5.1 设$p$为奇素数, $q=p^r$, $\mathbb{F}_q$为有限域, $A\subset \mathbb{F}_q$$\mathbb{F}_q$的子集, 满足

$ 0\not\in A, \qquad |A|=\frac{q-1}{2}, \quad\hbox{与}\quad \sum\limits_{\chi\neq \chi^0}\left|\sum\limits_{b\in A}\chi(b)\right|\leq c(q-1). $

$\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$.定义

$ \begin{eqnarray*} &&\;\;\;\;B(u_{11}, \cdots, u_{1s}, \cdots, u_{r1}, \cdots, u_{rs})\\ &&=\left\{\begin{array}{ll} 0,&\hbox{如果 } k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}\in A, \\ 1,&\hbox{如果 } k_0\beta_0+\cdots+k_{r-1}\beta_{r-1}\not\in A. \end{array}\right. \end{eqnarray*} $

则有

$ \max\limits_{{\bf{a}}\in \mathbb{F}_{2}^{rs}}\left|\widehat{B}({\bf{a}})\right| \leq 2c\left(2^{\frac{2r+3}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}-\frac{1}{2^{\frac{8r+3}{4}}}q^{\frac{5}{8}}\left(\log p+1\right)^{\frac{3r}{4}}\right), $ (5.1)
$ nl(B)\geq \frac{q}{2^{r+1}}-c\left(2^{\frac{2r+3}{4}}q^{\frac{7}{8}}\left(\log p+1\right)^{\frac{r}{4}}-\frac{1}{2^{\frac{8r+3}{4}}}q^{\frac{5}{8}}\left(\log p+1\right)^{\frac{3r}{4}}\right), $ (5.2)
$ {\rm{spr}}(B)\gg \frac{\log q}{2^r}, $ (5.3)
$ \sigma_{av}(B)\geq 0.5rs+o(rs). $ (5.4)

  满足定理5.1中的条件的子集有很多个.例如, 设$g$$\mathbb{F}_q^*$的生成元, 则下列子集

$ \begin{eqnarray*} A_1&=&\left\{g^n: 1\leq n\leq q-1, n\equiv 0 (\bmod2)\right\}, \\ A_2&=&\left\{g^n: 1\leq n\leq q-1, n\equiv 1 (\bmod2)\right\}, \\ A_3&=&\left\{g^n: 1\leq n\leq q-1, n\equiv 1, 2 (\bmod4)\right\}, \quad \hbox{当}q\equiv 1(\bmod4), \\ A_4&=&\left\{g^n: 1\leq n\leq q-1, n\equiv 1, 3, 7, 8 (\bmod\ 8)\right\}, \quad \hbox{当}q\equiv 1(\bmod8) \end{eqnarray*} $

都满足定理5.1的要求.

参考文献
[1] Coppersmith D, Shparlinski I E. On polynominal approximation of the discrete logarithm and the Diffie-Hellman mapping[J]. J. Cryp., 2000, 13(3): 339–360. DOI:10.1007/s001450010002
[2] Lange T, Winterhof A. Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions[J]. Acta Arith., 2002, 101(3): 223–229. DOI:10.4064/aa101-3-3
[3] Lange T, Winterhof A. Interpolation of the discrete logarithm in $mathbb{F}$q by Boolean functions and by polynomials in several variables modulo a divisor of q-1[J]. Disc. Appl. Math., 2003, 128(1): 193–206. DOI:10.1016/S0166-218X(02)00445-6
[4] Chung F R K, Graham R L. Quasi-random subsets of $mathbb{Z}$n[J]. J. Combin. The. Ser. A, 1992, 61(1): 64–86.
[5] Gowers W T. A new proof of Szemerédi's theorem[J]. Geom. Funct. Anal., 2001, 11(3): 465–588. DOI:10.1007/s00039-001-0332-9
[6] 苏忠, 林闯, 任丰原. 无线传感器网络中基于散列链的随机密钥预分发方案[J]. 计算机学报, 2009, 32(1): 30–41.
[7] 夏永波. Bent序列的构造及其相关值分布[J]. 数学杂志, 2010, 30(4): 663–670.
[8] Xu L, Chen S, Huang X, Mu Y. Pseudonym and bloom filter based secure and anonymouse DSR protocol in wireless ad hoc network[J]. Int. J. Comput. Netw. Commun. Secur., 2010, 5(1): 35–44.
[9] Winterhof A. Some estimates for character sums and applications[J]. Des. Codes Cryptogr., 2001, 22(2): 123–131. DOI:10.1023/A:1008300619004