A note on some algebraic trapdoors for block ciphers
Architecture-aware coding for distributed storage: Repairable block failure resilient codes
August 2018, 12(3): 505-513. doi: 10.3934/amc.2018029
Hamming correlation of higher order
Ming Su 1,, and Arne Winterhof 2,
Department of Computer Science, Nankai University, Tianjin, China
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
Full Text(HTML)
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.
Keywords: Pseudorandomness, Hamming autocorrelation, frequency hopping sequence, correlation measure of order $\ell$, cryptography.
Mathematics Subject Classification: 94A55, 11K45, 11T71, 94A05, 94A60.
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
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
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
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
L. Chen and G. Gong, Communication Systems Security, Chapman & Hall/CRC Cryptography and Network Security, CRC Press, Boca Raton, FL, 2012. Google Scholar
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
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
Z. Chen and A. Winterhof, Interpolation of Fermat quotients, SIAM J. Discrete Math., 28 (2014), 1-7. doi: 10.1137/130907951. Google Scholar
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
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
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
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
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
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
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
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
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
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
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
D. Jungnickel, Finite Fields, Structure and Arithmetics, B. I.-Wissenschaftsverlag, Mannheim, 1993. Google Scholar
A. Lempel and H. Greenberger, Families of sequences with optimal Hamming correlation properties, IEEE Trans. Inform. Theory, 20 (1974), 90-94. Google Scholar
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
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
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
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
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
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
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
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
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
A. Sárközy, On finite pseudorandom binary sequences and their applications in cryptography, Tatra Mt. Math. Publ., 37 (2007), 123-136. Google Scholar
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
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
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
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
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
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
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
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
Hongyu Han, Sheng Zhang. New classes of strictly optimal low hit zone frequency hopping sequence sets. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020031
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
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
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
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
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
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
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
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
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
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
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
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
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
HTML views (127)
Ming Su Arne Winterhof