# 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. Google Scholar [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. Google Scholar [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. Google Scholar [4] L. Chen and G. Gong, Communication Systems Security, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2012.Google Scholar [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. Google Scholar [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. Google Scholar [7] Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discrete Math., 28 (2014), 1-7. doi: 10.1137/130907951. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [19] D. Jungnickel, Finite Fields, Structure and Arithmetics, B. I.-Wissenschaftsverlag, Mannheim, 1993. Google Scholar [20] A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties, IEEE Trans. Inform. Theory, 20 (1974), 90-94. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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.Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [30] A. Sárközy, On finite pseudorandom binary sequences and their applications in cryptography, Tatra Mt. Math. Publ., 37 (2007), 123-136. Google Scholar [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. Google Scholar [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. Google Scholar

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. Google Scholar [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. Google Scholar [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. Google Scholar [4] L. Chen and G. Gong, Communication Systems Security, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2012.Google Scholar [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. Google Scholar [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. Google Scholar [7] Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discrete Math., 28 (2014), 1-7. doi: 10.1137/130907951. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [19] D. Jungnickel, Finite Fields, Structure and Arithmetics, B. I.-Wissenschaftsverlag, Mannheim, 1993. Google Scholar [20] A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties, IEEE Trans. Inform. Theory, 20 (1974), 90-94. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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.Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [30] A. Sárközy, On finite pseudorandom binary sequences and their applications in cryptography, Tatra Mt. Math. Publ., 37 (2007), 123-136. Google Scholar [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. Google Scholar [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. Google Scholar
 [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] Shanding Xu, Xiwang Cao, Jiafu Mi, Chunming Tang. More cyclotomic constructions of optimal frequency-hopping sequences. Advances in Mathematics of Communications, 2019, 13 (3) : 373-391. doi: 10.3934/amc.2019024 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [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] 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

2018 Impact Factor: 0.879