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.
The error linear complexity spectrum constitutes a well-known cryptographic criterion for sequences, indicating how the linear complexity of the sequence decreases as the number of bits allowed to be modified per peri...
详细信息
The error linear complexity spectrum constitutes a well-known cryptographic criterion for sequences, indicating how the linear complexity of the sequence decreases as the number of bits allowed to be modified per period increases. In this paper, via defining an association between 2(n)-periodic binary sequences and Boolean functions on n variables, it is shown that the error linear complexity spectrum also provides useful cryptographic information for the corresponding Boolean function f - namely, it yields an upper bound on the minimum Hamming distance between f and the set of functions depending on fewer number of variables. Therefore, the prominent lauder-paterson algorithm for computing the error linear complexity spectrum of a sequence may also be used for efficiently determining approximations of a Boolean function that depend on fewer number of variables. Moreover, it is also shown that, through this approach, low-degree approximations of a Boolean function can be also obtained in an efficient way.
暂无评论