# American Institute of Mathematical Sciences

August 2018, 12(3): 505-513. doi: 10.3934/amc.2018029

## Hamming correlation of higher order

 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

Received  June 2017 Revised  March 2018 Published  July 2018

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.

Citation: Ming Su, Arne Winterhof. Hamming correlation of higher order. Advances in Mathematics of Communications, 2018, 12 (3) : 505-513. doi: 10.3934/amc.2018029
##### References:
 [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.(3), 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, IEEE Trans. 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, in Monte 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 nonlinear pseudorandom number generators, in Applied 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, in Handbook of finite fields, CRC Press, Boca Raton, FL, (2013), 324–336. [25] L. Mérai, H. Niederreiter and A. Winterhof, Expansion complexity and linear complexity of sequences 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, in Progress in 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, in Topics in Geometry, Coding Theory 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, in Selected Topics in Information and Coding Theory, Ser. Coding Theory Cryptol., 7, World Sci. Publ., Hackensack, NJ, (2010), 3–40. doi: 10.1142/9789812837172_0001.

show all references

##### References:
 [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.(3), 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, IEEE Trans. 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, in Monte 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 nonlinear pseudorandom number generators, in Applied 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, in Handbook of finite fields, CRC Press, Boca Raton, FL, (2013), 324–336. [25] L. Mérai, H. Niederreiter and A. Winterhof, Expansion complexity and linear complexity of sequences 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, in Progress in 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, in Topics in Geometry, Coding Theory 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, in Selected Topics in Information and Coding Theory, Ser. Coding Theory Cryptol., 7, World Sci. Publ., Hackensack, NJ, (2010), 3–40. doi: 10.1142/9789812837172_0001.
 [1] Aixian Zhang, Zhengchun Zhou, Keqin Feng. A lower bound on the average Hamming correlation of frequency-hopping sequence sets. Advances in Mathematics of Communications, 2015, 9 (1) : 55-62. doi: 10.3934/amc.2015.9.55 [2] Limengnan Zhou, Daiyuan Peng, Hongyu Han, Hongbin Liang, Zheng Ma. Construction of optimal low-hit-zone frequency hopping sequence sets under periodic partial Hamming correlation. Advances in Mathematics of Communications, 2018, 12 (1) : 67-79. doi: 10.3934/amc.2018004 [3] Xing Liu, Daiyuan Peng. Frequency hopping sequences with optimal aperiodic Hamming correlation by interleaving techniques. Advances in Mathematics of Communications, 2017, 11 (1) : 151-159. doi: 10.3934/amc.2017009 [4] Xing Liu, Daiyuan Peng. Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions. Advances in Mathematics of Communications, 2014, 8 (3) : 359-373. doi: 10.3934/amc.2014.8.359 [5] Jingjun Bao. New families of strictly optimal frequency hopping sequence sets. Advances in Mathematics of Communications, 2018, 12 (2) : 387-413. doi: 10.3934/amc.2018024 [6] Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015 [7] Fang Liu, Daiyuan Peng, Zhengchun Zhou, Xiaohu Tang. New constructions of optimal frequency hopping sequences with new parameters. Advances in Mathematics of Communications, 2013, 7 (1) : 91-101. doi: 10.3934/amc.2013.7.91 [8] Xianhua Niu, Daiyuan Peng, Zhengchun Zhou. New classes of optimal frequency hopping sequences with low hit zone. Advances in Mathematics of Communications, 2013, 7 (3) : 293-310. doi: 10.3934/amc.2013.7.293 [9] Samuel T. Blake, Thomas E. Hall, Andrew Z. Tirkel. Arrays over roots of unity with perfect autocorrelation and good ZCZ cross-correlation. Advances in Mathematics of Communications, 2013, 7 (3) : 231-242. doi: 10.3934/amc.2013.7.231 [10] Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475 [11] Hua Liang, Wenbing Chen, Jinquan Luo, Yuansheng Tang. A new nonbinary sequence family with low correlation and large size. Advances in Mathematics of Communications, 2017, 11 (4) : 671-691. doi: 10.3934/amc.2017049 [12] Wenbing Chen, Jinquan Luo, Yuansheng Tang, Quanquan Liu. Some new results on cross correlation of $p$-ary $m$-sequence and its decimated sequence. Advances in Mathematics of Communications, 2015, 9 (3) : 375-390. doi: 10.3934/amc.2015.9.375 [13] Lenny Fukshansky, Ahmad A. Shaar. A new family of one-coincidence sets of sequences with dispersed elements for frequency hopping cdma systems. Advances in Mathematics of Communications, 2018, 12 (1) : 181-188. doi: 10.3934/amc.2018012 [14] Zhenyu Zhang, Lijia Ge, Fanxin Zeng, Guixin Xuan. Zero correlation zone sequence set with inter-group orthogonal and inter-subgroup complementary properties. Advances in Mathematics of Communications, 2015, 9 (1) : 9-21. doi: 10.3934/amc.2015.9.9 [15] Xiaohui Liu, Jinhua Wang, Dianhua Wu. Two new classes of binary sequence pairs with three-level cross-correlation. Advances in Mathematics of Communications, 2015, 9 (1) : 117-128. doi: 10.3934/amc.2015.9.117 [16] Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409 [17] Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050 [18] Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281 [19] H. W. Broer, Renato Vitolo. Dynamical systems modeling of low-frequency variability in low-order atmospheric models. Discrete & Continuous Dynamical Systems - B, 2008, 10 (2&3, September) : 401-419. doi: 10.3934/dcdsb.2008.10.401 [20] Lassi Roininen, Markku S. Lehtinen, Sari Lasanen, Mikko Orispää, Markku Markkanen. Correlation priors. Inverse Problems & Imaging, 2011, 5 (1) : 167-184. doi: 10.3934/ipi.2011.5.167

2017 Impact Factor: 0.564

Article outline