Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-27T00:55:26.909Z Has data issue: false hasContentIssue false
  • English
  • Français

On the joint 2-adic complexity of binary multisequences∗

Published online by Cambridge University Press:  06 April 2012

Lu Zhao  and
Qiao-Yan Wen
Lu Zhao
Affiliation:
State Key Laboratory of Networking and Switching Technology, P.O. Box 305, Beijing University of Posts and Telecommunications, Beijing 100876, P.R. China. [email protected]
Qiao-Yan Wen
Affiliation:
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, P.R. China
Get access

Abstract

Joint 2-adic complexity is a new important index of the cryptographic security for multisequences. In this paper, we extend the usual Fourier transform to the case of multisequences and derive an upper bound for the joint 2-adic complexity. Furthermore, for the multisequences with pn-period, we discuss the relation between sequences and their Fourier coefficients. Based on the relation, we determine a lower bound for the number of multisequences with given joint 2-adic complexity.

Keywords

Cryptographystream cipherFCSRjoint 2-adic complexityusual Fourier transform
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 46 , Issue 3 , July 2012 , pp. 401 - 412
Copyright
© EDP Sciences 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

W. Alun, Appendix A. Circulants (Extract) (2008); available at http://circulants.org/circ/
Fu, F., Niederreiter, H. and Özbudak, F., Joint linear complexity of multisequences consisting of linear recurring sequences. Cryptogr. Commun. 1 (2009) 3–29. Google Scholar
Goresky, M., Klapper, A. and Washington, L., Fourier tansform and the 2-adic span of periodic binary sequences. IEEE Trans. Inf. Theory 46 (2000) 687–691. Google Scholar
H. Gu, L. Hu and D. Feng, On the expected value of the joint 2-adic complexity of periodic binary multisequences, in Proc. of International Conference on Sequences and Their Applications, edited by G. Gong et al. (2006) 199–208.
Klapper, A. and Goresky, M., Feedback shift registers. 2-adic span, and combiners with memory. J. Cryptol. 10 (1997) 111–147. Google Scholar
Meidl, W. and Niederreiter, H., Linear complexity, k-error linear complexity, and the discrete Fourier transform. J. Complexity 18 (2002) 87–103. Google Scholar
Meidl, W. and Niederreiter, H., The expected value of the joint linear complexity of periodic multisequences. J. Complexity 19 (2003) 1–13. Google Scholar
Meidl, W., Niederreiter, H. and Venkateswarlu, A., Error linear complexity measures for multisequences. J. Complexity 23 (2007) 169–192. Google Scholar
Seo, C., Lee, S., Sung, Y., Han, K. and Kim, S., A lower bound on the linear span of an FCSR. IEEE Trans. Inf. Theory 46 (2000) 691–693. Google Scholar