The errorlinearcomplexity spectrum of a periodic sequence is defined to be the ordered list of -errorlinear complexities of the sequence. In this paper, we present an algorithm which computes the errorlinear compl...
详细信息
The errorlinearcomplexity spectrum of a periodic sequence is defined to be the ordered list of -errorlinear complexities of the sequence. In this paper, we present an algorithm which computes the errorlinearcomplexity spectrum for binary sequences with period , where is an odd prime and is a primitive root modulo .
The linearcomplexity of sequences is an important measure to gauge the cryptographic strength of key streams used in stream ciphers. The instability of linearcomplexity caused by changing a few symbols of sequences ...
详细信息
ISBN:
(纸本)9783540859116
The linearcomplexity of sequences is an important measure to gauge 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, Niederreiter, and Su [3] studied linearcomplexity and I-errorlinearcomplexity of 2(n)-periodic binary sequences to characterize such sequences with fixed I-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-error or 3-errorlinearcomplexity L, when the Hamming weight of the binary representation of 2(n) - L is w(H)(2(n) - L) not equal 2. Using this characterization we obtain the counting function for the number of 2(n)-periodic binary sequences with fixed k-error linear complexity L for k = 2 and 3 when w(H)(2(n) - L) not equal 2.
The k-error linear complexity of a periodic sequence s over a field k and with period N is the minimum linearcomplexity that s can have after changing at most k of its terms in each period. This concept can be used a...
详细信息
ISBN:
(纸本)9781424422562
The k-error linear complexity of a periodic sequence s over a field k and with period N is the minimum linearcomplexity that s can have after changing at most k of its terms in each period. This concept can be used as a measure of cryptographic strength for sequences. We introduce a generalisation of the notion of k-error linear complexity, which we call the extension field k-error linear complexity, defined as being the k-error linear complexity of s when working in the smallest extension field of k which contains an N-th root of unity, assuming N is not divisible by the characteristic of k. The optimisation problem of finding the extension field k-error linear complexity is firstly transformed to an optimisation problem in the DFT (Discrete Fourier Transform) domain, using Blahut's theorem. We then give an approximation algorithm of polynomial complexity for the problem (O(N-2) operations in the extension field), by restricting the search space to error sequences whose DFT have period up to k. The algorithm was implemented in GAP and the results on a series of sequences are discussed.
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.
complexity measures for sequences, such as the linearcomplexity and the k-error linear complexity, play an important role in stream ciphers. This contribution studies the distribution of 1-errorlinearcomplexity of ...
详细信息
complexity measures for sequences, such as the linearcomplexity and the k-error linear complexity, play an important role in stream ciphers. This contribution studies the distribution of 1-errorlinearcomplexity of binary sequences with arbitrary prime period. For any odd prime N, the authors present all possible values of 1-errorlinearcomplexity of N-periodic binary sequences, and derive the exact formulas to count the number of N-periodic binary sequences with any given 1-errorlinearcomplexity.
In this article, we present a counterexample to Theorem 4.2 and Theorem 5.2 by kavuluru (Des Codes Cryptogr 53:75-97, 2009). We conclude that the counting functions for the number of 2 (n) -periodic binary sequences w...
详细信息
In this article, we present a counterexample to Theorem 4.2 and Theorem 5.2 by kavuluru (Des Codes Cryptogr 53:75-97, 2009). We conclude that the counting functions for the number of 2 (n) -periodic binary sequences with fixed 3-errorlinearcomplexity by kavuluru are not correct.
This paper presents some nonrandom distribution properties of two generalized cyclotomic binary sequences of length constructed by Zhang et al. (Appl Algebra Eng Commun Comput 21:93-108, 2010). Using these properties ...
详细信息
This paper presents some nonrandom distribution properties of two generalized cyclotomic binary sequences of length constructed by Zhang et al. (Appl Algebra Eng Commun Comput 21:93-108, 2010). Using these properties we further study the -errorlinearcomplexity and autocorrelation of these sequences. For some small values of , the upper bounds on the -errorlinearcomplexity are derived, which are far less than their linearcomplexity. Finally the bounds on the autocorrelation of these sequences are also presented. Our results show that there exist some drawbacks in application of these two sequences.
Modern software oriented symmetric ciphers have become a key feature in utilizing word-oriented cryptographic *** the output sequence,in the order of its generation,of a word-oriented cryptographic primitive in the sa...
详细信息
Modern software oriented symmetric ciphers have become a key feature in utilizing word-oriented cryptographic *** the output sequence,in the order of its generation,of a word-oriented cryptographic primitive in the same way as traditional bit-oriented primitives,we can expose the intrinsic weakness of these primitives,especially for word-oriented linear feedback shift registers,T-functions,and so *** new methods for using word-oriented cryptographic primitives are presented in this paper,that is,the extracted state method and cascading extracted coordinate *** a T-function as an example,we research the different cryptographic properties of the output sequences of the original method and the two proposed methods,focusing mainly on period,linearcomplexity,and k-errorlinear *** conclusions show that the proposed methods could enhance at low cost the cryptographic properties of the output *** a result,since the new methods are simple and easy to implement,they could be used to design new word-oriented cryptographic primitives.
The d-ary Sidel'nikov sequence S = s(0), s(1).. of period q - 1 for a prime power q = p(m) is a frequently analyzed sequence in the literature. Recently, it turned out that the linearcomplexity over F-p of the (d...
详细信息
The d-ary Sidel'nikov sequence S = s(0), s(1).. of period q - 1 for a prime power q = p(m) is a frequently analyzed sequence in the literature. Recently, it turned out that the linearcomplexity over F-p of the (d-ary Sidel'nikov sequence is considerably smaller than the period if the sequence element S (q - 1) /2mod (q - 1) is chosen adequately. In this paper this work is continued and tight lower bounds on the linearcomplexity over F, of the d-ary Sidel'nikov sequence are given. For certain cases exact values are provided. Finally, results on the k-error linear complexity over Fp of the d-ary Sidel'nikov sequence are presented.
暂无评论