大族布尔函数的构造及其相关性质的研究

【作者】 张敏；

【导师】 刘华宁；

【作者基本信息】 西北大学 ， 基础数学， 2015， 硕士

【摘要】 布尔函数在密码学中起着重要作用,其密码学性质的好坏直接关系到密码体制的安全性.本文从数论的角度出发,利用有限域上的多项式构造了一大族布尔函数,并讨论了其相关的密码学性质,主要取得以下结果：一、利用有限域Fq上的多项式构造大族布尔函数.设p为奇素数,Fq是阶为q=pr(r≥1)的有限域,β0,…,βr-1为Fq上的Fp基.设s=「log2p」,f(x)∈Fq[x]在Fq上无重根且0<deg(f(x))<p定义布尔函数如下：B(u11,…,u1s,…,ur1,…,urs)其中ki-1=ui1+ui2·2+…+uis·2s-1,uij∈{0,1}且1≤j≤s,1≤i≤r.本文讨论了上述布尔函数的密码学性质,包括：最大傅里叶系数、非线性度、代数次数、平均灵敏度和稀疏性.二、证明了一类伪随机二进制数列是无碰撞的且具有强雪崩效应,同时将碰撞与雪崩效应的概念延伸到了上述构造的大族布尔函数上,并研究了布尔函数的碰撞和雪崩效应.更多还原

【Abstract】 Boolean functions play an important role in the cryptography, their prop-erties directly effect the safety of the cipher system. In this paper, from the perspective of the number theory we construct a large family of Boolean func-tions by using the polynomials over finite fields, and study the cryptography properties. The following are the main results.First, a large family of Boolean functions is constructed by using the poly-nomials over Fq. Let Fq be the finite field of order q= pr with odd prime and integer r≥ 1, and letβ0,…,βr-1 be linearly independent elements of Fq over Fp. Define s=「log2p」, and write ki-1=ui1+ui2·2+…+uis· 2s-1 with Uij ∈{0,1} for 1≤ j≤ s and 1≤ i≤ r. Assume that f(x) ∈ Fq[x] has no multiple zero in Fq and 0<deg(/)< p. Define B(u11,…,u1s,…,ur1,…,urs) then we discuss the cryptography properties including the maximum Fourier co-efficient, nonlinearity, average sensitivity, sparsity, collision and avalanche effect.Second, we prove that a large family of pseudorandom binary sequence is collision free and possesses the avalanche property, extend the concepts of collision and avalanche effect to the above Boolean functions, and study their collision and avalanche effect.更多还原