Article Contents
Article Contents

Nearly optimal codebooks from generalized Boolean bent functions over $\mathbb{Z}_{4}$

• * Corresponding author: Lisha Wang

This work was supported by the National Natural Science Foundation of China (Nos. 61702166, 61761166010) and Science Research Project of Hubei Provincial Department of Education (No. B2020150)

• In this paper, based on the theory of $\mathbb{Z}_{4}$-valued quadratic forms we propose several classes of generalized Boolean bent functions over $\mathbb{Z}_{4}$, and new families of codebooks are constructed from these functions. The codebooks constructed in this paper are nearly optimal with respect to the Welch bound, and their parameters are new. Furthermore, some Boolean bent functions are also derived.

Mathematics Subject Classification: Primary: 11T71; Secondary: 11T23.

 Citation:

• Table 1.  The parameters of codebooks nearly achieving the Welch bound

 Parameters $(N, K)$ Constraints $I_{max}$ Ref. $\big(p^n, K=\frac{p-1}{2p}(p^n+p^{n/2})+1\big)$ $p$ is an odd prime $\frac{(p+1)p^{n/2}}{2pK}$ [13] $\big(q^2, \frac{(q-1)^2}{2}\big)$ $q$ is a power of an odd prime $\frac{q+1}{(q-1)^2}$ [36] $\big(q(q+4), \frac{(q+3)(q+1)}{2}\big)$ $q$ is a prime power $\frac{1}{q+1}$ [16] $(q, \frac{q-1}{2})$ $q$ is a prime power $\frac{\sqrt{q}+1}{q-1}$ [16] $(p^n-1, \frac{p^n-1}{2})$ $p$ is an odd prime $\frac{\sqrt{p^n}+1}{p^n-1}$ [35] $(q^l+q^{l-1}-1, q^{l-1})$ $l>2$ $\frac{1}{\sqrt{q^{l-1}}}$ [39] $\big((q-1)^k+q^{k-1}, q^{k-1}\big)$ $k>2, q\geq4$ $\frac{\sqrt{q^{k+1}}}{(q-1)^{k}+(-1)^{k+1}}$ [11] $\big((q-1)^k+K, K\big)$ $k>2, K=\frac{(q-1)^{k}+(-1)^{k+1}}{q}$ $\frac{\sqrt{q^{k-1}}}{K}$ [11] $\big((q^s-1)^n+K, K\big)$ $s>1, n>1$ and $\frac{\sqrt{q^{sn+1}}}{(q^s-1)^{n}+(-1)^{n+1}}$ [20] $K=\frac{(q^s-1)^{n}+(-1)^{n+1}}{q}$ $\big((q^s-1)^n+q^{sn-1}, q^{sn-1}\big)$ $s>1, n>1$ $\frac{\sqrt{q^{sn+1}}}{(q^s-1)^{n}+(-1)^{n+1}}$ [20] $\big(q-1, \frac{q(r-1)}{2r}\big)$ $r=p^t, q=r^s, p \nmid s$ $\frac{\sqrt{r}}{\sqrt{q}(\sqrt{r}-1) K}$ [31] $\big(q^2, \frac{q(q+1)(r-1)}{2r}\big)$ $r=p^t, q=r^s$ $\frac{(r+1)q}{2rK}$ [31] $(q^3, q^2)$, $(q^3+q^2, q^2)$ $q$ is a prime power $\frac{1}{q}$ [19] $\big((q-1)q^2, (q-1)q\big)$, $q$ is a prime power $\frac{1}{q-1}$ [19] $\big((q^2-1)q, (q-1)q\big)$ $\big(q^3-q^2-q+1, (q-1)^2\big)$, $q$ is a prime power $\frac{q}{(q-1)^2}$ [19] $\big(q^3-2q+1, (q-1)^2\big)$, $\big((q-1)^2q, (q-1)^2\big)$, $\big((q-1)q^2, (q-1)^2\big)$ $\big((q-1)^2q, (q-1)(q-2)\big)$, $q$ is a prime power $\frac{q}{(q-1)(q-2)}$ [19] $\big(q^3-q^2-2q+2, (q-1)(q-2)\big)$ $\big((q-1)^3, (q-2)^2\big)$, $q$ is a prime power $\frac{q}{(q-2)^2}$ [19] $\big(q^3-2q^2-q+3, (q-2)^2\big)$ $(2^{\frac{n}{r}+n}+2^n, 2^n)$ $1 •  [1] E. H. Brown, Generalizations of the Kervaire invariant, Annals. Math., 95 (1972), 368-383. doi: 10.2307/1970804. [2] X. Cao, W. Chou and X. Zhang, More constructions of near optimal codebooks associated with binary sequences, Adv. Math. Commun., 11 (2017), 187-202. doi: 10.3934/amc.2017012. [3] C. Carlet and S. Mesnager, Four decades of research on bent functions, Des. Codes Cryptogr., 78 (2016), 5-50. doi: 10.1007/s10623-015-0145-8. [4] P. Charpin, E. Pasalic and C. Tavernier, On bent and semi-bent quadratic Boolean functions, IEEE Trans. Inf. Theory, 51 (2005), 4286-4298. doi: 10.1109/TIT.2005.858929. [5] C. Ding, Complex codebooks from combinatorial designs, IEEE Trans. Inf. Theory, 52 (2006), 4229-4235. doi: 10.1109/TIT.2006.880058. [6] C. Ding and T. Feng, A generic construction of complex codebooks meeting the Welch bound, IEEE Trans. Inf. Theory, 53 (2007), 4245-4250. doi: 10.1109/TIT.2007.907343. [7] C. Ding and T. Feng, Codebooks from almost difference sets, Des. Codes Cryptogr., 46 (2008), 113-126. doi: 10.1007/s10623-007-9140-z. [8] C. Ding and J. Yin, Signal sets from functions with optimimum nonlinearity, IEEE Trans. Communications, 55 (2007), 936-940. doi: 10.1109/TCOMM.2007.894113. [9] A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane and P. Sole, The${\mathbb Z}_4$-linearity of Kerdock, Preparata, Goethals, and related codes, IEEE Trans. Inf. Theory, 40 (1994), 301-319. doi: 10.1109/18.312154. [10] Z. Heng, Nearly optimal codebooks based on generalized Jacobi sums, Dis. Appli. Math., 250 (2018), 227-240. doi: 10.1016/j.dam.2018.05.017. [11] Z. Heng, C. Ding and Q. Yue, New constructions of asymptotically optimal codebooks with multiplicative characters, IEEE Trans. Inf. Theory, 63 (2017), 6179-6187. doi: 10.1109/TIT.2017.2693204. [12] Z. Heng and Q. Yue, Optimal codebooks achieving the Levenshtein bound from generalized bent functions over$\mathbb{Z}_4$, Cryptogr. Commun., 9 (2017), 41-53. doi: 10.1007/s12095-016-0194-5. [13] S. Hong, H. Park, T. Helleseth and Y. Kim, Near-optimal partial Hadamard codebook construction using binary sequences obtained from quadratic residue mapping, IEEE Trans. Inf. Theory, 60 (2014), 3698-3705. doi: 10.1109/TIT.2014.2314298. [14] H. Hu and J. Wu, New constructions of codebooks nearly meeting the Welch bound with equality, IEEE Trans. Inf. Theory, 60 (2014), 1348-1355. doi: 10.1109/TIT.2013.2292745. [15] V. I. Levenshtein, Bounds for packing of metric spaces and some of their applications, Probl. Cybern., 40 (1983), 43-110. [16] C. Li, Q. Yue and Y. Huang, Two families of nearly optimal codebooks, Des. Codes Cryptogr., 75 (2015), 43-57. doi: 10.1007/s10623-013-9891-7. [17] N. Li, X. Tang and T. Helleseth, New constructions of quadratic bent functions in polynomial form, IEEE Trans. Inf. Theory, 60 (2014), 5760-5767. doi: 10.1109/TIT.2014.2339861. [18] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, England, 1997. [19] W. Lu, X. Wu, X. Cao and M. Chen, Six constructions of asymptotically optimal codebooks via the character sums, Des. Codes Cryptogr., 88 (2020), 1139-1158. doi: 10.1007/s10623-020-00735-w. [20] G. Luo and X. Cao, Two constructions of asymptotically optimal codebooks via the hyper Eisenstein sum, IEEE Trans. Inf. Theory, 64 (2018), 6498-6505. doi: 10.1109/TIT.2017.2777492. [21] G. Luo and X. Cao, New constructions of codebooks asymptotically achieving the Welch bound, 2018 IEEE International Symposium on Information Theory, (2018), 2346–2350. [22] S. Mesnager, Bent Functions: Fundamentals and Results, Springer-Verlag, 2016. doi: 10.1007/978-3-319-32595-8. [23] Y. Qi, S. Mesnager, C. Tang, Codebooks from generalized bent$\mathbb{Z}_{4}$-valued quadratic forms, Discret. Math., 343 (2020), 111736. doi: 10.1016/j.disc.2019.111736. [24] L. Qian, X. Cao, W. Lu and X. Wu, New constructions of asymptotically optimal codebooks via character sums over a local ring, preprint, arXiv: 1906.05523. [25] O. S. Rothaus, On "bent" functions, J. Combin. Theory Ser. A, 20 (1976), 300-305. doi: 10.1016/0097-3165(76)90024-8. [26] D. V. Sarwate, Meeting the Welch bound with equality, Sequences and Their Applications, Springer London, 1999, 79–102. [27] K. Schmidt,${\mathbb Z}_4$-valued quadratic forms and quaternary sequence families, IEEE Trans. Inf. Theory, 55 (2009), 5803-5810. doi: 10.1109/TIT.2009.2032818. [28] P. Sol$\acute{e}\$ and N. Tokareva, Connections between quaternary and binary bent functions, 2009. Available from: https://eprint.iacr.org/2009/544.pdf. [29] P. Tan, Z. Zhou and D. Zhang, A construction of codebooks nearly achieving the Levenshtein bound, IEEE Signal Process. Lett., 23 (2016), 1306-1309.  doi: 10.1109/LSP.2016.2595106. [30] L. Welch, Lower bounds on the maximum cross correlation of signal, IEEE Trans. Inf. Theory, 20 (1974), 397-399.  doi: 10.1109/TIT.1974.1055219. [31] X. Wu, W. Lu and X. Cao, Two constructions of asymptotically optimal codebooks via the trace functions, Cryptogr. Commun., 12 (2020), 1195-1211.  doi: 10.1007/s12095-020-00448-w. [32] P. Xia, S. Zhou and G. B. Giannakis, Achieving the Welch bound with difference sets, IEEE Trans. Inf. Theory, 51 (2005), 1900-1907.  doi: 10.1109/TIT.2005.846411. [33] C. Xiang, C. Ding and S. Mesnager, Optimal codebooks from binary codes meeting the Levenshtein bound, IEEE Trans. Inf. Theory, 61 (2015), 6526-6535.  doi: 10.1109/TIT.2015.2487451. [34] W. Yin, C. Xiang and F. Fu, A further construction of asymptotically optimal codebooks with multiplicative characters, Appl. Algebra Eng. Commun. Comput., 30 (2019), 453-469.  doi: 10.1007/s00200-019-00387-x. [35] N. Y. Yu, A construction of codebooks associated with binary sequences, IEEE Trans. Inf. Theory, 58 (2012), 5522-5533.  doi: 10.1109/TIT.2012.2196021. [36] A. Zhang and K. Feng, Two classes of codebooks nearly meeting the Welch bound, IEEE Trans. Inf. Theory, 58 (2012), 2507-2511.  doi: 10.1109/TIT.2011.2176531. [37] A. Zhang and K. Feng, Construction of cyclotomic codebooks nearly meeting the Welch bound, Des. Codes Cryptogr., 63 (2012), 209-224.  doi: 10.1007/s10623-011-9549-2. [38] Z. Zhou, C. Ding and N. Li, New families of codebooks achieving the Levenshtein bound, IEEE Trans. Inf. Theory, 60 (2014), 7382-7387.  doi: 10.1109/TIT.2014.2353052. [39] Z. Zhou and X. Tang, New nearly optimal codebooks from relative difference sets, Adv. Math. Commun., 5 (2011), 521-527.  doi: 10.3934/amc.2011.5.521.

Tables(1)