检索结果-内蒙古大学图书馆

On the k-error linear complexity of binary sequences derived from polynomial quotients

Science China(Information Sciences) 2015年第9期58卷 83-97页

作者： CHEN ZhiXiong NIU ZhiHua WU ChenHuang School of Mathematics Putian University School of Computer Engineering and Science Shanghai University

The k-error linear complexity is an important cryptographic measure of pseudorandom sequences in stream ciphers. In this paper, we investigate the k-error linear complexity of p2-periodic binary sequences defined from the polynomial quotients modulo p, which are the generalizations of the well-studied Fermat ***, first we determine exact values of the k-error linear complexity over the finite field F2 for these binary sequences under the assumption of 2 being a primitive root modulo p2, and then we determine their k-error linear complexity over the finite field Fp. Theoretical results obtained indicate that such sequences possess‘good’ error linear complexity.

关键词： cryptography Fermat quotients polynomial quotients binary sequences linear complexity k-error linear complexity

来源：评论

学校读者我要写书评

暂无评论

On the linear complexity and k-error linear complexity over F_p of the d-ary sidel'nikov sequence

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2007年第12期53卷 4755-4761页

作者： Aly, Hassan Meidl, Wilfried Cairo Univ Fac Sci Dept Math Giza 12613 Egypt Sabanci Univ MDBF TR-34956 Istanbul Turkey

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 linear complexity 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 linear complexity 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.

关键词： k-error linear complexity linear complexity Sidel'nikov sequences stream ciphers

来源：评论

学校读者我要写书评

暂无评论

On the expected value of the linear complexity and the k-error linear complexity of periodic sequences

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2002年第11期48卷 2817-2825页

作者： Meidl, W Niederreiter, H Austrian Acad Sci Inst Discrete Math A-1010 Vienna Austria Natl Univ Singapore Dept Math Singapore 117543 Singapore

In his 1986 book, Rueppel conjectured that periodic binary sequences have expected linear complexity close to the period length N. In this paper, we determine the expected value of the linear complexity of N-periodic sequences explicitly and confirm Rueppel's conjecture for arbitrary finite fields. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity of N-periodic sequences. We present a method to establish a lower bound on the expected k-error linear complexity of N-periodic sequences based on the knowledge of the counting function V-N,V- 0 (c), i.e., the number of N-periodic sequences with given linear complexity c. For some cases, we give explicit formulas for that lower bound and we also determine N-N,N- 0 (c).

关键词： generalized discrete Fourier transform (GDFT) k-error linear complexity linear complexity periodic sequences stream ciphers

来源：评论

学校读者我要写书评

暂无评论

On the computation of the linear complexity and the k-error linear complexity of binary sequences with period a power of two

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2005年第3期51卷 1145-1150页

作者： Salagean, A Loughborough Univ Technol Dept Comp Sci Loughborough LE11 3TU Leics England

The linear Games-Chan algorithm for computing the linear complexity 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 linear complexity 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.

关键词： k-error linear complexity linear complexity repeated-root codes stream cipher

来源：评论

学校读者我要写书评

暂无评论

On the k-error linear complexity of p^m-periodic binary sequences

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2007年第6期53卷 2297-2304页

作者： Han, Yun kyoung Chung, Jin-Ho Yang, kyeongcheol POSTECH Dept Elect & Elect Engn Pohang 790784 Kyungbuk South Korea

In this correspondence, we study the statistical stability properties of p(m)-periodic binary sequences in terms of their linear complexity and k-error linear complexity, where 1) is a prime number and 2 is a primitive root modulo p(2). We show that their linear complexity 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 linear complexity 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].

关键词： cryptography k-error linear complexity linear complexity periodic sequences stream ciphers XWLI algorithm

来源：评论

学校读者我要写书评

暂无评论

Periodic sequences with maximal linear complexity and large k-error linear complexity

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 2003年第4期14卷 273-286页

作者： Meidl, W Niederreiter, H Natl Univ Singapore Temasek Labs Singapore 119260 Singapore Natl Univ Singapore Dept Math Singapore 117543 Singapore

The linear complexity and the k-error linear complexity are important concepts for the theory of stream ciphers in cryptology. keystreams that are suitable for stream ciphers must have large values of these complexity measures. We study periodic sequences over an arbitrary finite field F-q and establish conditions under which there are many periodic sequences over linear complexity N, and k-error linear complexity close to N. The existence of many such sequences thwarts attacks against the keystreams by exhaustive search.

关键词： stream cipher linear complexity k-error linear complexity periodic sequence

来源：评论

学校读者我要写书评

暂无评论

Analysis of the k-error linear complexity and error Sequence for 2pⁿ-Periodic Binary Sequence

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2018年第8期E101A卷 1197-1203页

作者： Niu, Zhihua kong, Deyu Ren, Yanli Du, Xiaoni Shanghai Univ Sch Comp Engn & Sci Shanghai 200444 Peoples R China Shanghai Univ Shanghai Inst Adv Commun & Data Sci Shanghai 200444 Peoples R China Shanghai Univ Sch Commun & Informat Engn Shanghai 200444 Peoples R China Northwest Normal Univ Coll Math & Informat Sci Lanzhou 730070 Gansu Peoples R China

The k-error linear complexity of a sequence is a fundamental concept for assessing the stability of the linear complexity. After computing the k-error linear complexity of a sequence, those bits that cause the linear complexity reduced also need to be determined. For binary sequences with period 2p(n), where p is an odd prime and 2 is a primitive root modulo p(2), we present an algorithm which computes the minimum number k such that the k-error linear complexity is not greater than a given constant c. The corresponding error sequence is also obtained.

关键词： periodic sequence linear complexity k-error linear complexity error sequence

来源：评论

学校读者我要写书评

暂无评论

New Results on Periodic Sequences With Large k-error linear complexity

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第10期55卷 4687-4694页

作者： Hu, Honggang Gong, Guang Feng, Dengguo Chinese Acad Sci Inst Software State Key Lab Informat Secur Beijing 100080 Peoples R China Univ Waterloo Dept Elect & Comp Engn Waterloo ON N2L 3G1 Canada

Niederreiter showed that there is a class of periodic sequences which possess large linear complexity and large k-error linear complexity simultaneously. This result disproved the conjecture that there exists a trade-off between the linear complexity and the k-error linear complexity of a periodic sequence by Ding et al. By considering the orders of the divisors of x(N)-1 over F-q, we obtain three main results which hold for much larger k than those of Niederreiter et al.: a) sequences with maximal linear complexity and almost maximal k-error linear complexity with general periods;b) sequences with maximal linear complexity and maximal k-error linear complexity with special periods;c) sequences with maximal linear complexity and almost maximal k-error linear complexity in the asymptotic case with composite periods. Besides, we also construct some periodic sequences with low correlation and large k-error linear complexity.

关键词： correlation cyclotomy entropy function k-error linear complexity linear complexity periodic sequence

来源：评论

学校读者我要写书评

暂无评论

An algorithm for the k-error linear complexity of sequences over GF( p^m) with period pⁿ, p a prime

引用

INFORMATION AND COMPUTATION 1999年第1-2期151卷 134-147页

作者： kaida, T Uehara, S Imamura, k Kyushu Inst Technol Dept Comp Sci & Elect Fukuoka 8208502 Japan Yatsushiro Natl Coll Technol Dept Ingn Elect & Informat Kumamoto 8668501 Japan

An algorithm is given for the k-error linear complexity of sequences over GF(p(m)) with period p(n), p a prime. The algorithm is derived by the generalized Games-Chan algorithm for the linear complexity of sequences over GF(p(m)) with period p(n) and by using the modified cost different from that used in the Stamp-Martin algorithm for sequences over GF(2) with period 2(n). A method is also given for computing an error vector which gives the k-error linear complexity. (C) 1999 Academic Press.

关键词： k-error linear complexity sequence over GF(p(m)) with period p(n) Stamp-Martin algorithm Games-Chan algorithm

来源：评论

学校读者我要写书评

暂无评论

On the k-error linear complexity of l-sequences

引用

FINITE FIELDS AND THEIR APPLICATIONS 2010年第6期16卷 420-435页

作者： Tan, Lin Qi, Wen-Feng Zhengzhou Informat Sci & Technol Inst Dept Appl Math Zhengzhou 450002 Peoples R China Chinese Acad Sci State Key Lab Informat Secur Inst Software Beijing Peoples R China

This paper studies the stability of the linear complexity of l-sequences. Let (s) under bar be an I-sequence with linear complexity attaining the maximum per((s) under bar)/2 + 1. A tight lower bound and an upper bound on minerror((s) under bar), i.e., the minimal value k for which the k-error linear complexity of (s) under bar is strictly less than its linear complexity, are given. In particular, for an I-sequence (s) under bar based on a prime number of the form 2r + 1, where r is an odd prime number with primitive root 2, it is shown that minerror((s) under bar) is very close to r, which implies that this kind of I-sequences have very stable linear complexity. (C) 2010 Published by Elsevier Inc.

关键词： Feedback with carry shift register l-Sequences linear complexity k-error linear complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：