Research On Cryptographic Properties Of Functions And Periodic Sequences Over Finite Fields:Perfect Nonlinear And Linear Complexity

Cryptography and information security are important research fields in communication. In the private key cipher code system, we need to use the functions over finite fields or periodic sequences as keys to encrypt the plaintext into the ciphertext, so as to achieve the purpose of the secrecy. The functions and sequences should have good cryptographic properties to resist various cipher code attacks that have been invented. Let Fq be the q-ary finite field, where q=pm, p is a prime and m>1. The function f:Fq�'Fqn with perfect nonlinear can be used as key to resist differential attack. Q-ary periodic sequence with large complexity can be used as keys in the stream cipher system to resist the attack of the Berlekamp-Massey algorithm. In practical application, the k-error linear complexity is the more important property of the cryptography, it is also a difficult and important research field in the current cryptography. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of the multisequences has been investigated. This paper studies the cryptographic properties of functions and periodic sequences over finite fields: perfect nonlinear and linear complexity. The main results are as follows:1、We solve two conjectures presented by Kyureghyan and Ozbudak in2012about a class of functions fn,a{x)=x{Trn{x)-α/2x) over Fqn, where∈Fqn and Trn(x) is a trace function from Fqn to Fq by using Exponential sum over the finite field. We prove that there is no function fn,α (x) when n≥4in terms of the estimation of Kloosterman sum and the trace mapping over the finite field. The method is also applicable for the results given by Kyureghyan and Ozbudak about n≥5, thus we also give a more simplified proof for the results about n≥5. We also prove that there is no function f3,α(x) with perfect nonlinear on Fq3when α∈Fq\{0,2,3,4,6}.2、We generalize the distribution functions for the linear complexity of the sequences with prime period length to the case of special composite number period length. Combining the discrete Fourier transform with the cyclotomic cosets theory, we determine the distribution functions for the linear complexity of the sequences with period N=2nl(l≥1) over Fq, where n and the characteristic of Fq are odd primes, gcd(n,q)=1and q is a primitive root modulo2n’. 3, We extend the optimal shift of binary sequene with period2"-1to the case of the sequence with period q"-1over Fq by using the sequential divisions method and the inverse discrete Fourier transform. Two algorithms are presented to determine the optimal shfit and the minimum linear complexity of the sequences that differs from a given sequence over Fq with period q"-1by one digit, one of which also describes how the linear complexity changes with the error position and the error bit.4、We generalize the approximation algorithm for the extension field k-error linear complexity of single sequences to the case of the multisequence in terms of the generalized discrete Fourier transform. We first give the notion of the extension field k-error Fq-linear complexity for the multisequence with period N over the finite fieldwith characteristic p, where gcd(N,p)=1, then we give an approximation algorithm for computing the k-error Fq-linear complexity of the periodic multisequence by using the generalized discrete Fourier transform.5、We extend the optimal shift of the binary sequence with period2n-1to the case of multisequences by using the inverse discrete Fourier transform. An algorithm is given to describe how the joint linear complexity of the binary multisequence with odd period N changes with respect to the error term, we also determine the1-error joint linear complexity and the optimal shift.