PDF《数学杂志》

Vol.

28 (

2018 ) No.

1 数学杂志J. of Math. (PRC) 基于伪随机子集生成的 Boolean 函数 刘华宁, 陈晓林 (西北大学数学学院, 陕西 西安 710127) 摘要: 本文基于有限域中的伪随机子集, 构造了大族 Boolean 函数并研究了其性质. 利用有限 域中特征和估计的方法, 分析了 Boolean 函数的非线性, 平均灵敏度与稀疏性, 给出了估计式. 推广并 改进了相关领域的已有结果. 关键词: Boolean 函数;

最大 Fourier 系数;

非线性;

平均灵敏度;

稀疏性 MR(2010) 主题分类号: 94C10;

94A60;

11T71;

11T24 中图分类号: TN918.1;

O156.4 文献标识码: A 文章编号: 0255-7797(2018)01-0167-10

1 引言 Boolean 函数在流密码, 分组密码以及散列函数的研究中起着重要作用. 为了研究 Boolean 函数, 人们提出了许多有关 Boolean 函数的密码学指标. 设F2 是一个二元域, Fn

2 是F2 上的一个 n 维线性空间, 所谓 n 元Boolean 函数 B(x1,xn) 是指从 Fn

2 到F2 的一个映射. 设x=(x1,xn), a = (a1,an) ∈ Fn

2 , 则a, x = a1x1 anxn 表示通常的内积. Boolean 函数 B(x1,xn) 的最大 Fourier 系数B(a) 定义为 B(a) = x∈Fn

2 (?1)B(x)+ a,x . Boolean 函数 B(x1,xn) 的非线性定义如下 nl(B) = 2n?1 ?

1 2 max a∈Fn

2 B(a) . 每一个 Boolean 函数都可以唯一地表示成多项式的形式, 称为 Boolean 函数的代数正规 型B(x1,xn) = I?{1,2,・・・ ,n} aI i∈I xi, aI ∈ F2. Boolean 函数的稀疏性 spr(B) 是代数正规型中非零系数单项式的个数. 此外 Boolean 函数 的平均灵敏度 σav(B) 定义如下 σav(B) = 2?n a∈Fn

2 n i=1 B(a) ? B(a(i) ) , ? 收稿日期: 2016-05-13 接收日期: 2016-10-27 基金项目: 国家自然科学基金资助 (11571277);

陕西省青年科技新星项目资助 (2014KJXX-61);

陕西省 自然科学基金资助 (2014JM1007);

陕西省工业科技攻关项目资助 (2016GY-080;

2016GY-077). 作者简介: 刘华宁 (1979C), 男, 湖南永州, 教授, 主要研究方向: 数论及其应用.

168 数学杂志Vol.

38 其中 a(i) 是a改变第 i 个坐标后所得的向量. 近几年来, 一些密码学研究者从数论的角度出发构造了许多具有 好 的密码学性质 的Boolean 函数. 例如, Coppersmith 与Shparlinski [1] 利用模 p 的二次剩余构造了如下的 Boolean 函数. 命题 1.1 设p为奇素数, s = log2 p , 其中 x 表示不超过 x 的最大整数. 定义 Boolean 函数为 B(u1,us) = 0, 如果 u1 + u2 ・

2 us ・ 2s?1 是Fp 上的二次剩余, 1, 如果 u1 + u2 ・

2 us ・ 2s?1 是Fp 上的二次非剩余, (1.1) 其中 uj ∈ {0, 1} 且1≤j≤s. 则有 spr(B) ≥ 2?

3 2 p

1 4 (log2 p)?

1 2 ? 1, σav(B) ≥ 0.5s + o(s). Lange 与Winterhof [2] 将上述命题进行了推广. 命题 1.2 设p为奇素数, Fq 是阶为 q = pr (r ≥ 1) 的有限域, β0,βr?1 是Fq 在Fp 上的一组基, s = log2 p . 定义 Boolean 函数如下 B(u11,u1s,ur1,urs) = 0, 如果k0β0 kr?1βr?1 是Fq 上的平方, 1, 如果k0β0 kr?1βr?1 是Fq 上的非平方, (1.2) 其中 ki?1 = ui1 + ui2 ・

2 uis ・ 2s?1 , uij ∈ {0, 1} 且1≤j≤s,

1 ≤ i ≤ r. 则有 spr(B) ≥ 2?

3 2

3 1 r + r ?

1 2 p

1 4 r ? 1. 随后文献 [3] 进一步研究了命题 1.2 中Boolean 函数的性质, 得到了以下结果. 命题 1.3 设p, r, s, B 如以上命题所定义. 则有 max a∈Frs

2 B(a) ≤

2 2r+3

4 q

7 8 (log p + 1) r

4 + 1, σav(B) ≥ 0.5rs + o(rs). 最近几十年来, 随着数论、 组合以及相关学科的发展, 伪随机子集得到了深入的研究和广 泛的应用. 许多论文都是关于这一领域的, 这些论文中提出了大量的思想、 方法和工具.