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. AlonY. KohayakawaC. MauduitC. 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. ChenA. 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. DuC. 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-HaraY. 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. LiuD. PengZ. 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éraiH. 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. ParkH. SongD. 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. AlonY. KohayakawaC. MauduitC. 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. ChenA. 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. DuC. 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-HaraY. 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. LiuD. PengZ. 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éraiH. 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. ParkH. SongD. 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]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271

[2]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[3]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020050

[4]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240

[5]

Harrison Bray. Ergodicity of Bowen–Margulis measure for the Benoist 3-manifolds. Journal of Modern Dynamics, 2020, 16: 305-329. doi: 10.3934/jmd.2020011

[6]

Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217

[7]

Giulia Luise, Giuseppe Savaré. Contraction and regularizing properties of heat flows in metric measure spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 273-297. doi: 10.3934/dcdss.2020327

[8]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267

[9]

Russell Ricks. The unique measure of maximal entropy for a compact rank one locally CAT(0) space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 507-523. doi: 10.3934/dcds.2020266

[10]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[11]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377

[12]

Jiahao Qiu, Jianjie Zhao. Maximal factors of order $ d $ of dynamical cubespaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278

[13]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[14]

Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247

[15]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[16]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

[17]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[18]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[19]

Jun Zhou. Lifespan of solutions to a fourth order parabolic PDE involving the Hessian modeling epitaxial growth. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5581-5590. doi: 10.3934/cpaa.2020252

[20]

Xuefeng Zhang, Yingbo Zhang. Fault-tolerant control against actuator failures for uncertain singular fractional order systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 1-12. doi: 10.3934/naco.2020011

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (159)
  • HTML views (171)
  • Cited by (0)

Other articles
by authors

[Back to Top]