This issue Previous Article Next Article

Article Contents

2018, Volume 12, Issue 3: 505-513. Doi:10.3934/amc.2018029

This issue Previous ArticleArchitecture-aware coding for distributed storage: Repairable block failure resilient codesNext ArticleA note on some algebraic trapdoors for block ciphers

Hamming correlation of higher order

Ming Su^1, , and
Arne Winterhof^2,

1.
Department of Computer Science, Nankai University, Tianjin, China
2.
Johann Radon Institute for Computational and Applied Mathematics, Altenberger Straße 69, A-4040 Linz, Austria

* Corresponding author: Ming Su
* Corresponding author: Ming Su

Received: June 2017

Revised: March 2018

Published: July 2018

Abstract/ Introduction Full Text(HTML)Related Papers Cited by

Abstract

Abstract
We introduce a new measure of pseudorandomness, the (periodic) Hamming correlation of order $\ell$ which generalizes the Hamming autocorrelation ($\ell = 2$). We analyze the relation between the Hamming correlation of order $\ell$ and the periodic analog of the correlation measure of order $\ell$ introduced by Mauduit and Sárközy. Roughly speaking, the correlation measure of order $\ell$ is a finer measure than the Hamming correlation of order $\ell$. However, the latter can be much faster calculated and still detects some undesirable linear structures. We analyze examples of sequences with optimal Hamming correlation and show that they have large Hamming correlation of order $\ell$ for some very small $\ell>2$. Thus they have some undesirable linear structures, in particular in view of cryptographic applications such as secure communications.
- Pseudorandomness,
- Hamming autocorrelation,
- frequency hopping sequence,
- correlation measure of order $\ell$,
- cryptography.
Mathematics Subject Classification:94A55, 11K45, 11T71, 94A05, 94A60.
Citation:
\begin{equation} \\ \end{equation}

[1]	N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira and V. Rödl, Measures of pseudorandomness for finite sequences: Typical values,Lond. Math. Soc.,95 (2007), 778-812. doi: 10.1112/plms/pdm027.
[2]	G. Bérczi, On finite pseudorandom sequences of $k$ symbols,Period. Math. Hungar.,47 (2003), 29-44. doi: 10.1023/B:MAHU.0000010809.50836.79.
[3]	N. Brandstätter and A. Winterhof, Linear complexity profile of binary sequences with small correlation measure,Period. Math. Hungar.,52 (2006), 1-8. doi: 10.1007/s10998-006-0008-1.
[4]	L. Chen and G. Gong,Communication Systems Security, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2012.
[5]	Z. Chen, A. Ostafe and A. Winterhof, Structure of pseudorandom numbers derived from Fermat quotients,Lecture Notes in Comput. Sci.,6087 (2010), 73-85. doi: 10.1007/978-3-642-13797-6_6.
[6]	Z. Chen and A. Winterhof, Linear complexity profile of $m$-ary pseudorandom sequences with small correlation measure,Indag. Mathem.,20 (2009), 631-640. doi: 10.1016/S0019-3577(09)80030-X.
[7]	Z. Chen and A. Winterhof, Interpolation of Fermat quotients,SIAM J. Discrete Math.,28 (2014), 1-7. doi: 10.1137/130907951.
[8]	W. Chu and C. J. Colbourn, Optimal frequency-hopping sequences via cyclotomy,IEEETrans. Inform. Theory,51 (2005), 1139-1141. doi: 10.1109/TIT.2004.842708.
[9]	J. H. Chung and K. Yang, Optimal frequency-hopping sequences with new parameters,IEEE Trans. Inform. Theory,56 (2010), 1685-1693. doi: 10.1109/TIT.2010.2040888.
[10]	G. Dorfer and A. Winterhof, Lattice structure and linear complexity profile of nonlinear pseudorandom number generators,Appl. Algebra Engrg. Comm. Comput.,13 (2003), 499-508. doi: 10.1007/s00200-003-0116-6.
[11]	G. Dorfer and A. Winterhof, A. Lattice structure of nonlinear pseudorandom number generators in parts of the period, inMonte Carlo and Quasi-Monte Carlo Methods 2002, Springer, Berlin, (2004), 199–211.
[12]	X. Du, C. Wu and W. Wei, An extension of binary threshold sequences from Fermat quotients,Adv. Math. Commun.,10 (2016), 743-752. doi: 10.3934/amc.2016038.
[13]	R. Ernvall and T. Metsänkylä, On the $p$-divisibility of Fermat quotients,Math. Comp.,66 (1997), 1353-1365. doi: 10.1090/S0025-5718-97-00843-0.
[14]	R. Fuji-Hara, Y. Miao and M. Mishima, Optimal frequency hopping sequences: A combinatorial approach,IEEE Trans. Inform. Theory,50 (2004), 2408-2420. doi: 10.1109/TIT.2004.834783.
[15]	D. Gómez-Pérez and J. Gutierrez, On the linear complexity and lattice test of nonlinearpseudorandom number generators, inApplied Algebra and Number Theory, Cambridge Univ. Press, Cambridge, (2014), 91–101.
[16]	D. Gómez and A. Winterhof, Multiplicative character sums of Fermat quotients and pseudorandom sequences,Period. Math. Hungar.,64 (2012), 161-168. doi: 10.1007/s10998-012-3747-1.
[17]	Y. K. Han and K. Yang, On the Sidelnikov sequences as frequency-hopping sequences,IEEE Trans. Inform. Theory,55 (2009), 4279-4285. doi: 10.1109/TIT.2009.2025569.
[18]	G. Harman and I. E. Shparlinski, Products of small integers in residue classes and additive properties of Fermat quotients,Int. Math. Res. Not., (2016), 1424-1446. doi: 10.1093/imrn/rnv182.
[19]	D. Jungnickel,Finite Fields, Structure and Arithmetics, B. I.-Wissenschaftsverlag, Mannheim, 1993.
[20]	A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties,IEEE Trans. Inform. Theory,20 (1974), 90-94.
[21]	F. Liu, D. Peng, Z. Zhou and X. Tang, New constructions of optimal frequency hopping sequences with new parameters,Adv. Math. Commun.,7 (2013), 91-101. doi: 10.3934/amc.2013.7.91.
[22]	C. Mauduit and A. Sárközy, On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol,Acta Arith.,82 (1997), 365-377. doi: 10.4064/aa-82-4-365-377.
[23]	C. Mauduit and A. Sárközy, On finite pseudorandom sequences of $k$ symbols,Indag. Math. (N.S.),13 (2002), 89-101. doi: 10.1016/S0019-3577(02)90008-X.
[24]	W. Meidl and A. Winterhof, Linear complexity of sequences and multisequences, inHandbookof finite fields, CRC Press, Boca Raton, FL, (2013), 324–336.
[25]	L. Mérai, H. Niederreiter and A. Winterhof, Expansion complexity and linear complexity ofsequences over finite fields,Cryptogr. Commun.,9 (2017), 501-509. doi: 10.1007/s12095-016-0189-2.
[26]	H. Niederreiter, Linear complexity and related complexity measures for sequences, inProgressin Cryptology-INDOCRYPT 2003, Lecture Notes in Comput. Sci., 2904, Springer, Berlin, (2003), 1–17.doi: 10.1007/978-3-540-24582-7_1.
[27]	A. Ostafe and I. E. Shparlinski, Pseudorandomness and dynamics of Fermat quotients,SIAM J. Discrete Math.,25 (2011), 50-71. doi: 10.1137/100798466.
[28]	K. Park, H. Song, D. S. Kim and S. W. Golomb, Optimal families of perfect polyphase sequences from the array structure of Fermat-Quotient sequences,IEEE Trans. Inform. Theory,62 (2016), 1076-1086. doi: 10.1109/TIT.2015.2511780.
[29]	G. I. Pirsic and A. Winterhof, On discrete Fourier transform, ambiguity, and Hamming-autocorrelation of pseudorandom sequences,Des. Codes Cryptography,73 (2014), 319-328. doi: 10.1007/s10623-013-9916-2.
[30]	A. Sárközy, On finite pseudorandom binary sequences and their applications in cryptography,Tatra Mt. Math. Publ.,37 (2007), 123-136.
[31]	A. Topuzoǧlu and A. Winterhof, Pseudorandom sequences, inTopics in Geometry, CodingTheory and Cryptography, Algebr. Appl., 6, Springer, Dordrecht, (2007), 135–166.doi: 10.1007/1-4020-5334-4_4.
[32]	A. Winterhof, Linear complexity and related complexity measures, inSelected Topics in Information and Coding Theory, Ser. Coding Theory Cryptol., 7, World Sci. Publ., Hackensack, NJ, (2010), 3–40.doi: 10.1142/9789812837172_0001.