On the joint 2-adic complexity of binary multisequences
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 3, pp. 401-412.

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.

DOI : https://doi.org/10.1051/ita/2012011
Classification : 11T71,  14G50,  94A60
Mots clés : cryptography, stream cipher, FCSR, joint 2-adic complexity, usual Fourier transform
@article{ITA_2012__46_3_401_0,
author = {Zhao, Lu and Wen, Qiao-Yan},
title = {On the joint 2-adic complexity of binary multisequences},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {401--412},
publisher = {EDP-Sciences},
volume = {46},
number = {3},
year = {2012},
doi = {10.1051/ita/2012011},
zbl = {1277.94010},
mrnumber = {2981676},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2012011/}
}
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
DA  - 2012///
SP  - 401
EP  - 412
VL  - 46
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2012011/
UR  - https://zbmath.org/?q=an%3A1277.94010
UR  - https://www.ams.org/mathscinet-getitem?mr=2981676
UR  - https://doi.org/10.1051/ita/2012011
DO  - 10.1051/ita/2012011
LA  - en
ID  - ITA_2012__46_3_401_0
ER  - 
Zhao, Lu; Wen, Qiao-Yan. On the joint 2-adic complexity of binary multisequences. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 3, pp. 401-412. doi : 10.1051/ita/2012011. http://www.numdam.org/articles/10.1051/ita/2012011/

[1] W. Alun, Appendix A. Circulants (Extract) (2008); available at http://circulants.org/circ/

[2] F. Fu, H. Niederreiter and F. Özbudak, Joint linear complexity of multisequences consisting of linear recurring sequences. Cryptogr. Commun. 1 (2009) 3-29. | MR 2511294 | Zbl 1178.94176

[3] M. Goresky, A. Klapper and L. Washington, Fourier tansform and the 2-adic span of periodic binary sequences. IEEE Trans. Inf. Theory 46 (2000) 687-691. | MR 1748998 | Zbl 0996.94029

[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. | MR 2444666 | Zbl 1152.94388

[5] A. Klapper and M. Goresky, Feedback shift registers. 2-adic span, and combiners with memory. J. Cryptol. 10 (1997) 111-147. | MR 1447843 | Zbl 0874.94029

[6] W. Meidl and H. Niederreiter, Linear complexity, k-error linear complexity, and the discrete Fourier transform. J. Complexity 18 (2002) 87-103. | MR 1895078 | Zbl 1004.68066

[7] W. Meidl and H. Niederreiter, The expected value of the joint linear complexity of periodic multisequences. J. Complexity 19 (2003) 1-13. | MR 1951323 | Zbl 1026.68067

[8] W. Meidl, H. Niederreiter and A. Venkateswarlu, Error linear complexity measures for multisequences. J. Complexity 23 (2007) 169-192. | MR 2314755 | Zbl 1128.94007

[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. Theory 46 (2000) 691-693. | MR 1748999 | Zbl 0996.94031

Cité par Sources :