In this correspondence, we study the statistical stability properties of p(m)-periodic binary sequences in terms of their linearcomplexity and k-error linear complexity, where 1) is a prime number and 2 is a primitiv...
详细信息
In this correspondence, we study the statistical stability properties of p(m)-periodic binary sequences in terms of their linearcomplexity and k-error linear complexity, where 1) is a prime number and 2 is a primitive root modulo p(2). We show that their linearcomplexity and k-error linear complexity take a value only from some specific ranges. We then present the minimum value k for which the k-error linear complexity is strictly less than the linearcomplexity in a new viewpoint different from the approach by Meidl. We also derive the distribution of p(m)-periodic binary sequences with specific k-error linear complexity. Finally, we get an explicit formula for the expectation value of the k-error linear complexity and give its lower and upper bounds, when k <= [p/2].
Recently the first author presented exact formulas for the number of 2(n)-periodic binary sequences with given 1-errorlinearcomplexity, and an exact formula for the expected 1-errorlinearcomplexity and upper and l...
详细信息
Recently the first author presented exact formulas for the number of 2(n)-periodic binary sequences with given 1-errorlinearcomplexity, and an exact formula for the expected 1-errorlinearcomplexity and upper and lower bounds for the expected k-error linear complexity, k >= 2, of a random 2(n)-periodic binary sequence. A crucial role for the analysis played the Chan-Games algorithm. We use a more sophisticated generalization of the Chan-Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-errorlinearcomplexity for p(n)-periodic sequences over F-p,p prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p(n)-periodic sequences over F-p.
We first optimize the structure of the Wei-Xiao-Chen algorithm for the linearcomplexity of sequences over GF(q) with period N = 2p(n), where p and q are odd primes, and q is a primitive root (mod p(2)). Then the unio...
详细信息
ISBN:
(纸本)9781424410736
We first optimize the structure of the Wei-Xiao-Chen algorithm for the linearcomplexity of sequences over GF(q) with period N = 2p(n), where p and q are odd primes, and q is a primitive root (mod p(2)). Then the union cost is used, so that an efficient algorithm for computing the k-error linear complexity of a sequence with period 2p(n) over GF(q) is derived, where p and q are odd primes, and q is a primitive root of modulo p2. We also give a validity proof of the proposed algorithm. Finally, a numerical example is presented to illustrate the algorithm.
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.
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.
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.
The linearcomplexity of sequences is an important measure of the cryptographic strength of key streams used in stream ciphers. The instability of linearcomplexity caused by changing a few symbols of sequences can be...
详细信息
The linearcomplexity of sequences is an important measure of the cryptographic strength of key streams used in stream ciphers. The instability of linearcomplexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu et al. (SETA, pp. 88-103, 2006) studied the linearcomplexity and the 1-errorlinearcomplexity of 2 (n) -periodic binary sequences to characterize such sequences with fixed 1-errorlinearcomplexity. In this paper we study the linearcomplexity and the k-error linear complexity of 2 (n) -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 (n) -periodic binary sequences with fixed 2- or 3-errorlinearcomplexity. Using this characterization we obtain the counting function for the number of 2 (n) -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.
The linear Games-Chan algorithm for computing the linearcomplexity c(s) of a binary sequence s of period l = 2(n) requires the knowledge of the full sequence, while the quadratic Berlekamp-Massey algorithm requires k...
详细信息
The linear Games-Chan algorithm for computing the linearcomplexity c(s) of a binary sequence s of period l = 2(n) requires the knowledge of the full sequence, while the quadratic Berlekamp-Massey algorithm requires knowledge of only 2c(s) terms. We show that we can modify the Games-Chan algorithm so that it computes the complexity in linear time knowing only 2c(s) terms. The algorithms of Stamp-Martin and Lauder-Paterson can also be modified, without loss of efficiency, to compute analogs of the k-error linear complexity for finite binary sequences viewed as initial segments of infinite sequences with period a power of two. We also develop an algorithm which, given a constant c and an infinite binary sequence s with period l = 2(n), computes the minimum number k of errors (and an associated error sequence) needed over a period of s for bringing the linearcomplexity of s below c. The algorithm has a time and space bit complexity of O(l). We apply our algorithm to decoding and encoding binary repeated-root cyclic codes of length l in linear, O(t), time and space. A previous decoding algorithm proposed by Lauder and Paterson has O(l(logl)(2)) complexity.
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.
linearcomplexity and k-error linear complexity of the stream cipher are two important standards to scale the randomicity of keystreams. For the 2n -periodicperiodic binary sequence with linearcomplexity 2n 1and k = ...
详细信息
linearcomplexity and k-error linear complexity of the stream cipher are two important standards to scale the randomicity of keystreams. For the 2n -periodicperiodic binary sequence with linearcomplexity 2n 1and k = 2,3,the number of sequences with given k-error linear complexity and the expected k-error linear complexity are provided. Moreover,the proportion of the sequences whose k-error linear complexity is bigger than the expected value is analyzed.
暂无评论