On the joint 2-adic complexity of binary multisequences

Lu Zhao; Qiao-Yan Wen

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

  • Volume: 46, Issue: 3, page 401-412
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Zhao, Lu, and Wen, Qiao-Yan. "On the joint 2-adic complexity of binary multisequences." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.3 (2012): 401-412. <http://eudml.org/doc/273002>.

@article{Zhao2012,
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.},
author = {Zhao, Lu, Wen, Qiao-Yan},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {cryptography; stream cipher; FCSR; joint 2-adic complexity; usual Fourier transform; Fourier transform},
language = {eng},
number = {3},
pages = {401-412},
publisher = {EDP-Sciences},
title = {On the joint 2-adic complexity of binary multisequences},
url = {http://eudml.org/doc/273002},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Zhao, Lu
AU - Wen, Qiao-Yan
TI - On the joint 2-adic complexity of binary multisequences
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2012
PB - EDP-Sciences
VL - 46
IS - 3
SP - 401
EP - 412
AB - 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.
LA - eng
KW - cryptography; stream cipher; FCSR; joint 2-adic complexity; usual Fourier transform; Fourier transform
UR - http://eudml.org/doc/273002
ER -

References

top
  1. [1] W. Alun, Appendix A.Circulants (Extract) (2008); available at http://circulants.org/circ/ 
  2. [2] F. Fu, H. Niederreiter and F. Özbudak, Joint linear complexity of multisequences consisting of linear recurring sequences. Cryptogr. Commun.1 (2009) 3–29. Zbl1178.94176MR2511294
  3. [3] M. Goresky, A. Klapper and L. Washington, Fourier tansform and the 2-adic span of periodic binary sequences. IEEE Trans. Inf. Theory46 (2000) 687–691. Zbl0996.94029MR1748998
  4. [4] 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. Zbl1152.94388MR2444666
  5. [5] A. Klapper and M. Goresky, Feedback shift registers. 2-adic span, and combiners with memory. J. Cryptol. 10 (1997) 111–147. Zbl0874.94029MR1447843
  6. [6] W. Meidl and H. Niederreiter, Linear complexity, k-error linear complexity, and the discrete Fourier transform. J. Complexity18 (2002) 87–103. Zbl1004.68066MR1895078
  7. [7] W. Meidl and H. Niederreiter, The expected value of the joint linear complexity of periodic multisequences. J. Complexity19 (2003) 1–13. Zbl1026.68067MR1951323
  8. [8] W. Meidl, H. Niederreiter and A. Venkateswarlu, Error linear complexity measures for multisequences. J. Complexity23 (2007) 169–192. Zbl1128.94007MR2314755
  9. [9] C. Seo, S. Lee, Y. Sung, K. Han and S. Kim, A lower bound on the linear span of an FCSR. IEEE Trans. Inf. Theory46 (2000) 691–693. Zbl0996.94031MR1748999

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.