A Sequence Synthesis Algorithm with Error Tolerance

doi:10.3969/j.issn.1000-3428.2014.02.028

Abstract

Abstract: The Synthesis of Linear Shift Register(LSR) with error tolerance is an important problem in the analysis of stream cipher. This paper constructs a homogenous key equation which is described by homogenous ideal of . It shows that the Homogenous key module equation can be used to solve the synthesis problem of the LSR sequence. By means of a fast computation of Gr?bner basis of homogenous polynomial ideal with two variables, the paper finds an efficient algorithm to solve the Homogenous key module equation. It gives a theorem to show the error tolerance of the algorithm. Results show that the success rate of the algorithm has a linear relationship with the complexity of the sequence, for a sequence with length of 1 000 and complexity of 65, the success rate of the algorithm is up to 86.6% at an error code rate of 10–3.

Key words: sequence synthesis, key equation, Berlekamp-Massey algorithm, Gr?bner basis, error tolerance performance

摘要： 线性递归序列的容错综合问题在流密码分析领域具有重要的理论分析与应用价值。利用伽罗华域上2个变元多项式的齐次理想刻画齐次关键方程的解空间，通过齐次关键方程解决线性递归序列综合问题不但具有可行性，而且具有某些容错性质。为此，根据二元多项式齐次理想Gr?bner基算法，提出一种求解齐次关键方程的快速算法，并给出一个定理来论述算法实现序列综合的充分条件。通过实验仿真对该算法在不同的序列复杂度和误码率下的容错性能进行分析，结果表明，该算法的成功率与序列复杂度呈线性关系，在误码率为10–3的情况下，对于序列复杂度为65、序列长度为1 000的序列，成功率可达86.6%以上。

关键词: 序列综合, 关键方程, Berlekamp-Massey算法, Gr?bner基, 容错性能

CLC Number:

TP309

GUO Tao, LU Pei-zhong. A Sequence Synthesis Algorithm with Error Tolerance[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2014.02.028.

郭涛，陆佩忠. 一种具有容错性的序列综合算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2014.02.028.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2014.02.028

http://www.ecice06.com/EN/Y2014/V40/I2/128

References

参考文献 [1] Berlekamp E R. Algebraic Coding Theory[M]. New York, USA: McGraw-Hill, 1968. [2] Massey J L. Shift-register Synthesis and BCH Decoding[J]. IEEE Trans. on Information Theory, 1969, 15(1): 122-127. [3] Mills W H. Continued Fractions and Linear Recurrences[J]. Mathematics of Computation, 1975, 129(29): 173-180. [4] Sugiyama Y. A Method for Solving Key Equation for Dec- oding Goppa Codes[J]. Information and Control, 1975, 27(1): 87-99. [5] Buchberger B, Bases G: An Algorithm Method in Polynomial Ideal Theory[M]. [S. 1.]: Reidel Publishing Company, 1985: 184-232. [6] Sakata S. Two-dimensional Shift Register Synthesis and Gr?bner Bases for Polynomial Ideal over an Integer Residue Ring[J]. Discrete Applied Mathematics, 1991, 33(1): 191-203. [7] 陆佩忠, 周锦君, 宋国文. 序列综合问题的新方法及其应用[M]. 北京: 科学出版社, 1992. [8] Lu Peizhong. Synthesis of Sequences and Efficient Decoding for a Class of Algebraic Geometry Codes[J]. Acta Electronic Sinica, 1993, 21(1): 1-10. [9] 陆佩忠, 刘木兰. UFD上线性递归序列特征理想的Gr?bner基[J]. 中国科学A辑, 1998, 28(6): 508-519. [10] Lu Peizhong. Synthesis of Multisequences and Their Applic- ations[J]. Journal of Electronics, 1993, 15(5): 46-73. [11] Zou Yan, Lu Peizhong. A New Generalization of Key Equation[J]. Chinese Journal of Computers, 2006, 29(5): 712- 718. [12] Schmidt G, Sidorenko V R. Multi-sequence Linear Hift-register Synthesis: The Varying Length Case[C]//Proc. of IEEE International Symposium on Information Theory. [S. 1.]: IEEE Press, 2006: 1738-1742. [13] Schmidt G, Sidorenko V R. Syndrome Decoding of Reed- solomon Codes Beyond Half the Minimum Distance Based on Shift-register Synthesis[J]. IEEE Trans. on Information Theory, 2010, 56(1): 5245-5252. [14] Lin Tsung-Ching, Truong Trieu-Kien, et al. A Future Simplification of Procedure for Decoding Nonsystematic Reed-solomon Codes Using the Berlekamp-massey Algorithm[J]. IEEE Trans. on Communications, 2011, 59(1): 1555-1562. 编辑索书志

[1]	DING Xiaohui, CAO Suzhen, WANG Caifen. Smart Contract-Assisted Dynamically Searchable Encryption Scheme with Forward and Backward Security [J]. Computer Engineering, 2022, 48(7): 141-150.
[2]	JIN Haibo, ZHAO Xinyue. High-Reliability Intrusion Detection Algorithm Under Conformal Prediction Framework [J]. Computer Engineering, 2022, 48(7): 130-140.
[3]	ZHANG Chao, PENG Changgen, DING Hongfa, XU Dequan. Searchable Encryption Scheme Based on China State Cryptography Standard SM9 [J]. Computer Engineering, 2022, 48(7): 159-167.
[4]	YE Qing, ZHAO Nannan, ZHAO Zongqu, QIN Panke, YAN Xixi, TANG Yongli. Efficient Fully Dynamic Group Signature Scheme from Lattice [J]. Computer Engineering, 2021, 47(2): 160-167,175.
[5]	JI Lusheng, ZHANG Guiling, YANG Jiarun. Off-Chain Personal Data Protection Scheme Based on Blockchain [J]. Computer Engineering, 2021, 47(2): 176-181,187.
[6]	ZHANG Jing, HE Zheng, GE Binghui, TANG Yongli, YE Qing. An Efficient Protocol for Millionaires' Problem and Its Application [J]. Computer Engineering, 2021, 47(2): 168-175.
[7]	YOU Wenzhu, GE Haibo. Efficient Algorithm for Multi-Scalar Multiplication of Elliptic Curves Using Multi-Base Number System [J]. Computer Engineering, 2021, 47(2): 182-187.
[8]	FU Zixi, XU Yang, WU Zhaodi, XU Dandan, XIE Xiaoyao. SVM-KNN Network Intrusion Detection Method Based on Incremental Learning [J]. Computer Engineering, 2020, 46(4): 115-122.
[9]	LIU Xueyan, HE Xiaomei, LU Tingting, LUO Yukun. Certificateless Public Audit Scheme for Shared Data [J]. Computer Engineering, 2020, 46(4): 143-150.
[10]	ZENG Yaqin, ZHANG Linlin, ZHANG Ruonan, YANG Bo. Malware Family Classification Model Based on MobileNet [J]. Computer Engineering, 2020, 46(4): 162-168.
[11]	ZHANG Rui, CHEN Hongwei. Intrusion Detection Based on Feature Optimization and SVPSO for Industrial Control System [J]. Computer Engineering, 2020, 46(4): 19-25.
[12]	LI Zhi, SONG Lipeng. Research on Internal Threat Detection Based on User Window Behavior [J]. Computer Engineering, 2020, 46(4): 135-142,150.
[13]	SHI Zhicai, WANG Yihan, ZHANG Xiaomei, CHEN Jiwei, CHEN Shanshan. An RFID Grouping-proof Protocol with Privacy Protection and Forward Security [J]. Computer Engineering, 2020, 46(1): 108-113.
[14]	ZHAO Nan, ZHANG Guoan, GU Xiaohui. Certificateless Aggregate Signature Scheme for Privacy Protection in VANET [J]. Computer Engineering, 2020, 46(1): 114-120,128.
[15]	LI Yuanhang, CHEN Xianlai, LIU Li, AN Ying, LI Zhongmin. Random Forest Algorithm for Differential Privacy Protection [J]. Computer Engineering, 2020, 46(1): 93-101.

Please choose a citation manager

Content to export