In our previous work we transformed the optimisation problem of finding the k-error linear complexity of a sequence into an optimisation problem in the DFT (Discrete Fourier Transform) domain, using Blahut's theor...
详细信息
ISBN:
(纸本)9783642158735
In our previous work we transformed the optimisation problem of finding the k-error linear complexity of a sequence into an optimisation problem in the DFT (Discrete Fourier Transform) domain, using Blahut's theorem. We then gave an approximation algorithm of polynomial complexity for the transformed problem by restricting the search space to error sequences whose DFT have period up to k. However, when applying the inverse transformation, the error vectors obtained are in general in an extension of the original field. In the present paper we develop our previous approximation algorithm so that now it can be constrained to only obtain errors over the original field. Essentially, we give a polynomial approximation algorithm for the computation of the k-error linear complexity of a sequence. More precisely, the algorithm will find the optimum among a restricted set of errors over the original field. While this restricted search space is still exponential, the complexity of the algorithm is polynomial, O(N-2 log N log log N).
In this paper we derive a result on the k-error linear complexity of balanced p-ary sequences of period N = p(n). Using this result, we also describe a construction of a sequence having large linearcomplexity. These ...
详细信息
In this paper we derive a result on the k-error linear complexity of balanced p-ary sequences of period N = p(n). Using this result, we also describe a construction of a sequence having large linearcomplexity. These results are of relevance in the construction of key sequences for stream ciphers.
Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences sho...
详细信息
ISBN:
(纸本)9783540772712
Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large linearcomplexity and also a large k-error linear complexity. Efficient algorithms for computing the k-error linear complexity of a sequence only exist for sequences of period equal to a power of the characteristic of the field. It is therefore useful to find a general and efficient algorithm to compute a good approximation of the k-error linear complexity. We show that the Berlekamp-Massey A Algorithm, which computes the linearcomplexity of a sequence, can be adapted to approximate the k-error linear complexity profile for a general sequence over a finite field. While the complexity of this algorithm is still exponential, it is considerably more efficient than the exhaustive search.
The Lauder-Paterson algorithm gives the profile of the k-error linear complexity for a binary sequence with period 2(n). In this paper a generalization of the Lauder-Paterson algorithm into a sequence over GF(p(m)) wi...
详细信息
ISBN:
(纸本)3540260846
The Lauder-Paterson algorithm gives the profile of the k-error linear complexity for a binary sequence with period 2(n). In this paper a generalization of the Lauder-Paterson algorithm into a sequence over GF(p(m)) with period p(n), where p is a prime and m, n are positive integers, is proposed. We discuss memory and computation complexities of proposed algorithm. Moreover numerical examples of profiles for balanced binary and ternary exponent periodic sequences, and proposed algorithm for a sequence over GF(3) with period 9(= 3(2)) are given.
Combining with the research on the linearcomplexity of explicit nonlinear generators of pseudorandom sequences, we study the stability on linearcomplexity of two classes of explicit inversive generators and two clas...
详细信息
Combining with the research on the linearcomplexity of explicit nonlinear generators of pseudorandom sequences, we study the stability on linearcomplexity of two classes of explicit inversive generators and two classes of explicit nonlinear generators. We present some lower bounds in theory on the k-error linear complexity of these explicit generatol＇s, which further improve the cryptographic properties of the corresponding number generators and provide very useful information when they are applied to cryptography.
We investigate the minimum value m(S) of k for which the k-error linear complexity is strictly less than the linearcomplexity of a given sequence S with period N = p(n) over GF(q). The upper and lower bounds on m(S) ...
详细信息
ISBN:
(纸本)9781424441969
We investigate the minimum value m(S) of k for which the k-error linear complexity is strictly less than the linearcomplexity of a given sequence S with period N = p(n) over GF(q). The upper and lower bounds on m(S) are derived to show the relationship between the linearcomplexity of a given p(n)-periodic sequence over GF(q) and the minimum value m(S). Numerical examples are given to verify, the results.
An efficient algorithm for computing the k-error linear complexity of a sequence over GF(q) with period p(n) is presented, where q is a prime and a primitive root modulo p(2). The new algorithm is a generalization of ...
详细信息
An efficient algorithm for computing the k-error linear complexity of a sequence over GF(q) with period p(n) is presented, where q is a prime and a primitive root modulo p(2). The new algorithm is a generalization of an algorithm presented by Xiao, Wei, Lam and Imamura.
The k-error linear complexity and the linearcomplexity of the keystream of a stream cipher are two important standards to scale the randomness of the key stream. For a pq^n-periodic binary sequences where p, q are tw...
详细信息
The k-error linear complexity and the linearcomplexity of the keystream of a stream cipher are two important standards to scale the randomness of the key stream. For a pq^n-periodic binary sequences where p, q are two odd primes satisfying that 2 is a primitive root module p and q^2 and gcd（p-1, q-1） = 2, we analyze the relationship between the linearcomplexity and the minimum value k for which the k-error linear complexity is strictly less than the linearcomplexity.
In this paper, a constructive approach for determining CELCS（critical errorlinearcomplexity spectrum） for the kerrorlinearcomplexity distribution of 2~n-periodic binary sequences is developed via the sieve metho...
详细信息
ISBN:
(纸本)9781510830981
In this paper, a constructive approach for determining CELCS（critical errorlinearcomplexity spectrum） for the kerrorlinearcomplexity distribution of 2~n-periodic binary sequences is developed via the sieve method and Games-Chan algorithm. Accordingly, the second descent point（critical point） distribution of the k-error linear complexity for 2~n-periodic binary sequences is characterized. As a by product, it is proved that the maximum k-error linear complexity is 2~n-(2) over all 2~n-periodic binary sequences, where 2<=k < 2 and l < n. With these results, some work by Niu et al. are proved to be incorrect.
New generalized cyclotomic sequences with length p2 and pq are considered as good *** this paper,two classes of error generalized cyclotomic sequences are constructed by changing the characteristic sets of the above *...
详细信息
New generalized cyclotomic sequences with length p2 and pq are considered as good *** this paper,two classes of error generalized cyclotomic sequences are constructed by changing the characteristic sets of the above *** show that k-error linear complexity of generalized cyclotomic sequences don't exceed p and p+q-1,which are much less than their(zero-error) linearcomplexity.
暂无评论