×

Quasi-perfect linear codes from planar and APN functions. (English) Zbl 1358.94098

Summary: Let \(p\) be a prime and \(m\) be a positive integer with \(m \geq 3\). Let \(f\) be a mapping from \(\mathbb {F}_{p^{m}}\) to itself and \(\mathcal {C}_{f}\) be the linear code of length \(p^{m}- 1\), whose parity-check matrix has its \(j\)-th column \(\left[\begin{matrix} \pi ^{j}\\ f(\pi ^{j})\end{matrix}\right]\), where \(\pi\) is a primitive element in \(\mathbb {F}_{p^{m}}\) and \(j = 0, 1,\cdots, p^{m}- 2\). In the case of \(p = 2\), it is proved that \(\mathcal {C}_{f}\) has covering radius 3 when \(f(x)\) is a quadratic APN function. This gives a number of binary quasi-perfect codes with minimum distance 5. In the case that \(p\) is an odd prime, we show that for all known planar functions \(f(x)\), the covering radius of \(\mathcal {C}_{f}\) is equal to 2 if \(m\) is odd and 3 if \(m\) is even. Consequently, several classes of \(p\)-ary quasi-perfect codes are derived.

MSC:

94B15 Cyclic codes
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94B75 Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bierbrauer, J.: New semifields, PN and APN functions. Des. Codes Crypt. 54 (3), 189-200 (2010) · Zbl 1269.12006 · doi:10.1007/s10623-009-9318-7
[2] Bierbrauer, J.: Commutative semifields from projection mappings. Des. Codes Crypt. 61(2), 187-196 (2011) · Zbl 1241.12004 · doi:10.1007/s10623-010-9447-z
[3] Bracken, C., Byrne, E., Markin, N., McGuire, G.: An infinite family of quadratic quadrinomial APN functions. arXiv:0707.1223 (2007) · Zbl 1195.94048
[4] Bracken, C., Byrne, E., Markin, N., McGuire, G.: New families of quadratic almost perfect nonlinear trinomials and multinomials. Finite Fields and Their Applications 14(3), 703-714 (2008) · Zbl 1153.11058 · doi:10.1016/j.ffa.2007.11.002
[5] Budaghyan, L., Carlet, C.: Classes of quadratic APN trinomials and hexanomials and related structures. IEEE Trans. Inf. Theory 54(5), 2354-2357 (2008) · Zbl 1177.94134 · doi:10.1109/TIT.2008.920246
[6] Budaghyan, L., Carlet, C., Leander, G.: Two classes of quadratic APN binomials inequivalent to power functions. IEEE Trans. Inf. Theory 54(9), 4218-4229 (2008) · Zbl 1177.94135 · doi:10.1109/TIT.2008.928275
[7] Budaghyan, L., Carlet, C., Leander, G.: Constructing new APN functions from known ones. Finite Fields and Their Applications 15(2), 150-159 (2009) · Zbl 1184.94228 · doi:10.1016/j.ffa.2008.10.001
[8] Canteaut, A., Charpin, P., Dobbertin, H.: Binary m-sequences with three-valued crosscorrelation: a proof of Welch’s conjecture. IEEE Trans. Inf. Theory 46(1), 4-8 (2000) · Zbl 1003.94519 · doi:10.1109/18.817504
[9] Carlet, C.: Vectorial Boolean Functions for Cryptography. In: Crama, Y., Hammer, P.L (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press (2010) · Zbl 1209.94036
[10] Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Crypt. 15(2), 125-156 (1998) · Zbl 0938.94011 · doi:10.1023/A:1008344232130
[11] Carlet, C., Ding, C.: Highly nonlinear mappings. J. Complex. 20, 205-244 (2004) · Zbl 1053.94011 · doi:10.1016/j.jco.2003.08.008
[12] Carlet, C., Ding, C., Yuan, J.: Linear codes from perfect nonlinear mappings and their secret sharing schemes. IEEE Trans. Inf. Theory 51(6), 2089-2102 (2005) · Zbl 1192.94114 · doi:10.1109/TIT.2005.847722
[13] Chabaud, F.; Vaudenay, S.; Santis, A. (ed.), Links between differential and linear cryptanalysis (1995), Berlin Heidelberg · Zbl 0879.94023
[14] Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. North-Holland Mathematical Library. Elsevier Science (1997) · Zbl 0874.94001
[15] Coulter, R., Matthews, R.: Planar functions and planes of Lenz-Barlotti class II. Des. Codes Crypt. 10(2), 167-184 (1997) · Zbl 0872.51007 · doi:10.1023/A:1008292303803
[16] Danev, D., Dodunekov, S.: A family of ternary quasi-perfect BCH codes. Des. Codes Crypt. 49(1-3), 265-271 (2008) · Zbl 1178.94235 · doi:10.1007/s10623-008-9193-7
[17] Danev, D., Dodunekov, S., Radkova, D.: A family of constacyclic ternary quasi-perfect codes with covering radius 3. Des. Codes Crypt. 59(1-3), 111-118 (2011) · Zbl 1211.94045 · doi:10.1007/s10623-010-9470-0
[18] Dobbertin, H.: Almost perfect nonlinear power functions on GF(2n): the Niho case. Inf. Comput. 151(1), 57-72 (1999) · Zbl 1072.94513 · doi:10.1006/inco.1998.2764
[19] Dobbertin, H.: Almost perfect nonlinear power functions on GF(2n): the Welch case. IEEE Trans. Inf. Theory 45(4), 1271-1275 (1999) · Zbl 0957.94021 · doi:10.1109/18.761283
[20] Dobbertin, H.; Jungnickel, D. (ed.); Niederreiter, H. (ed.), Almost perfect nonlinear power functions on GF(2n): a new case for n divisible by 5, 113-121 (2001), Berlin Heidelberg · Zbl 1010.94550 · doi:10.1007/978-3-642-56755-1_11
[21] Dodunekov, S.: The optimal double-error correcting codes of Zetterberg and Dumer-Zinovev are quasiperfect. C. R. Acad. Bulg. Sci. 38(9), 1121-1123 (1985) · Zbl 0576.94019
[22] Dodunekov, S.: Some quasi-perfect double error correcting codes. Probl. Control Inform. Theory 15(5), 367-375 (1986) · Zbl 0627.94020
[23] Dumer, I., Zinoviev, V.: Some new maximal codes over GF(4). Probl. Peredachi Inf. 14(3), 24-34 (1978) · Zbl 0396.94011
[24] Edel, Y., Kyureghyan, G., Pott, A.: A new APN function which is not equivalent to a power mapping. IEEE Trans. Inf. Theory 52(2), 744-747 (2006) · Zbl 1246.11185 · doi:10.1109/TIT.2005.862128
[25] Edel, Y., Pott, A.: A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications 3(1), 59-81 (2009) · Zbl 1231.11140 · doi:10.3934/amc.2009.3.59
[26] Etzion, T., Mounits, B.: Quasi-perfect codes with small distance. IEEE Trans. Inf. Theory 51(11), 3938-3946 (2005) · Zbl 1298.94149 · doi:10.1109/TIT.2005.856944
[27] Feng, K., Luo, J.: Value distributions of exponential sums from perfect nonlinear functions and their applications. IEEE Trans. Inf. Theory 53(9), 3035-3041 (2007) · Zbl 1318.11160 · doi:10.1109/TIT.2007.903153
[28] Gallager, R.G.: Information Theory and Reliable Communication (1968) · Zbl 0198.52201
[29] Gashkov, I., Sidel’nikov, V.: Linear ternary quasiperfect codes that correct double errors. Probl. Peredachi Inf. 22(4), 43-48 (1986) · Zbl 0619.94015
[30] Gevorkijan, D.N., Avetisjan, A.M., Tigranjan, G.A.: On the construction of codes correcting two errors in Hammings metrix over Galois field. Vichislitel’naja Tehnika 3, 19-21 (1975)
[31] Gold, R.: Maximal recursive sequences with three-valued recursive cross-correlation functions. IEEE Trans. Inf. Theory 14(1), 154-156 (1968) · Zbl 0228.62040 · doi:10.1109/TIT.1968.1054106
[32] Goppa, V.D.: A new class of linear error-correcting codes. Probl. Peredach. Inform. 6(3), 24-30 (1970) · Zbl 0292.94011
[33] Hollmann, H., Xiang, Q.: A proof of the Welch and Niho conjectures on cross-correlations of binary m-sequences. Finite Fields and Their Applications 7(2), 253-286 (2001) · Zbl 1027.94006 · doi:10.1006/ffta.2000.0281
[34] Kasami, T.: The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes. Inf. Control. 18(4), 369-394 (1971) · Zbl 0217.58802 · doi:10.1016/S0019-9958(71)90473-6
[35] Leducq, E.: Functions which are PN on infinitely many extensions of Fp,p \(\mathbb{F}_p,\,p\) odd. Des. Codes Crypt. 75(2), 281-299 (2015) · Zbl 1331.11114
[36] Moreno, O., Castro, F.: Divisibility properties for covering radius of certain cyclic codes. IEEE Trans. Inf. Theory 49(12), 3299-3303 (2003) · Zbl 1301.94171 · doi:10.1109/TIT.2003.820033
[37] Nyberg, K.; Helleseth, T. (ed.), Differentially uniform mappings for cryptography, 55-64 (1994), Berlin Heidelberg · Zbl 0951.94510
[38] Tietäväinen, A.: On the nonexistence of perfect codes over finite fields. SIAM J. Appl. Math. 24(1), 88-96 (1973) · Zbl 0233.94004 · doi:10.1137/0124010
[39] Weng, G., Zeng, X.: Further results on planar DO functions and commutative semifields. Des. Codes Crypt. 63(3), 413-423 (2012) · Zbl 1272.12021 · doi:10.1007/s10623-011-9564-3
[40] Yuan, J., Carlet, C., Ding, C.: The weight distribution of a class of linear codes from perfect nonlinear functions. IEEE Trans. Inf. Theory 52(2), 712-717 (2006) · Zbl 1192.94128 · doi:10.1109/TIT.2005.862125
[41] Zieve, M.: Planar functions and perfect nonlinear monomials over finit fields. Des. Codes Crypt. 75(1), 71-80 (2015) · Zbl 1314.51003
[42] Zinoviev, V., Leontiev, V.: The nonexistence of perfect codes over Galois fields. Probl. Control Inform. Theory 2(2) (1973)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.