×

Recent results and problems on constructions of linear codes from cryptographic functions. (English) Zbl 1469.94135

Summary: Linear codes have a wide range of applications in the data storage systems, communication systems, consumer electronics products since their algebraic structure can be analyzed and they are easy to implement in hardware. How to construct linear codes with excellent properties to meet the demands of practical systems becomes a research topic, and it is an efficient way to construct linear codes from cryptographic functions. In this paper, we will introduce some methods to construct linear codes by using cryptographic functions over finite fields and present some recent results and problems in this area.

MSC:

94B05 Linear codes (general theory)
94D10 Boolean functions
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beth, T.; Ding, C., On almost perfect nonlinear permutation, EUROCRYPT’93, Springer-Verlag, LNCS, 765, 65-76 (1994) · Zbl 0951.94524
[2] Budaghyan, L.: Construction and analysis of cryptographic functions, Springer Verlag (2015) · Zbl 1367.94001
[3] Budaghyan, L.; Helleseth, T., New perfect nonlinear multinomials over \(\mathbb{F}_{p^{2k}}\) Fp2k for any odd prime p, Springer-Verlag, LNCS, 5203, 403-414 (2008) · Zbl 1177.94137
[4] Calderbank, AR; Goethals, JM, Three-weight codes and association schemes, Philips J. Res., 39, 4-5, 143-152 (1984) · Zbl 0546.94016
[5] Calderbank, AR; Kantor, WM, The geometry of two-weight codes, Bull. London Math. Soc., 18, 97-122 (1986) · Zbl 0582.94019
[6] Canteaut, A.; Charpin, P.; Dobbertin, H., Weight divisibility of cyclic codes, highly nonlinear functions on \(\mathbb{F}_{2^m}\) F2m, and crosscorrelation of maximum-length sequences, SIAM, J. Discrete Math., 13, 1, 105-138 (2000) · Zbl 1010.94013
[7] Canteaut, A.; Charpin, P.; Dobbertin, H., Binary m-squences with three-valued crosscorrelation: a proof of Welch’s conjecture, IEEE Trans. Inf. Theory, 46, 1, 4-8 (2000) · Zbl 1003.94519
[8] Carlet, C.; Charpin, P.; Zinoviev, V., Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15, 125-156 (1998) · Zbl 0938.94011
[9] Carlet, C.: Boolean Functions for Cryptography and Error Correcting Codes, Chapter of the monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering. In: Crama, Y, Hammer, P (eds.) , pp 257-397. Cambridge University Press (2010) · Zbl 1209.94035
[10] Carlet, C.: Vectorial Boolean Functions for Cryptography, Chapter of the monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Crama, Y., Hammer, P., (eds) pp. 398-469. Cambridge: University Press (2010) · Zbl 1209.94036
[11] Carlet, C., Boolean and vectorial plateaued functions, and APN functions, IEEE Trans. Inf. Theory, 61, 11, 6272-6289 (2015) · Zbl 1359.94931
[12] Carlet, C.: Boolean Functions for Cryptography and Coding Theory. To appear in Cambridge University Press · Zbl 1512.94001
[13] 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
[14] Çeşmelioǧlu, A.; McGuire, G.; Meidl, W., A construction of weakly and non-weakly regular bent functions, J. Combin. Theory Ser. A, 119, 2, 420-429 (2012) · Zbl 1258.94034
[15] Chen, Y.; Li, N.; Zeng, X., A class of binary cyclic codes with generalized Niho exponents, Finite Fields Appl., 43, 123-140 (2017) · Zbl 1351.94084
[16] Coulter, R., Henderson, M., Hu, L., Kosick, P., Xiang, Q., Zeng, X.: Planar polynomials and commutative semifields two dimensional over their middle nucleus and four dimensional over their nucleus, Online at http://www.math.udel.edu/ coulter/papers/d24.pdf
[17] Coulter, R.; Matthews, RW, Planar and planes of Lenz-Barlotti class II, Des. Codes Cryptogr., 10, 2, 167-184 (1997) · Zbl 0872.51007
[18] Dembowski, P.; Ostrom, TG, Planes of order n with collineation groups of order n2, Math. Z., 103, 3, 239-258 (1968) · Zbl 0163.42402
[19] Ding, C., Cyclic codes from the two-Prime sequences, IEEE Trans. Inf. Theory, 58, 6, 3881-3891 (2012) · Zbl 1365.94552
[20] Ding, C.: Cyclic codes from Dickson polynomials. https://arxiv.org/pdf/1206.4370.pdf
[21] Ding, C., Cyclic codes from cyclotomic sequences of order four, Finite Fields Appl., 23, 8-34 (2013) · Zbl 1305.94109
[22] Ding, C., Cyclic codes from some monomials and trinomials, SIAM J. Discret. Math., 27, 4, 1977-1994 (2013) · Zbl 1306.94114
[23] Ding, C., Linear codes from some 2-designs, IEEE Trans. Inf. Theory, 61, 6, 3265-3275 (2015) · Zbl 1359.94685
[24] Ding, C., A construction of binary linear codes from Boolean functions, Discrete Math., 339, 9, 2288-2323 (2016) · Zbl 1408.94979
[25] Ding, C., A sequence construction of cyclic codes over finite fields, Cryptogr, Commun., 10, 2, 319-341 (2018) · Zbl 1412.94242
[26] Ding, C.; Helleseth, T., Optimal ternary cyclic codes from monomials, IEEE Trans. Inf. Theory, 59, 9, 5898-5904 (2013) · Zbl 1364.94652
[27] Ding, C.; Li, C.; Li, N.; Zhou, Z., Three-weight cyclic codes and their weight distributions, Discrete Math., 339, 2, 415-427 (2016) · Zbl 1356.94094
[28] Ding, C.; Niederreiter, H., Cyclotomic linear codes of order 3, IEEE Trans. Inf. Theory, 53, 6, 2274-2277 (2007) · Zbl 1323.94156
[29] Ding, C.; Wang, X., A coding theory construction of new systematic authentication codes, Theor. Comput. Sci., 330, 1, 81-99 (2005) · Zbl 1078.68030
[30] Ding, C.; Yang, Y.; Tang, X., Optimal sets of frequency hopping sequences from linear cyclic codes, IEEE Trans. Inf. Theory, 56, 7, 3605-3612 (2010) · Zbl 1366.94636
[31] Ding, C.; Yuan, J., A family of skew Hadamard difference sets, J. Comb. Theory, Ser. A, 113, 7, 1526-1535 (2006) · Zbl 1106.05016
[32] Ding, C.; Zhou, Z., Binary cyclic codes from explicit polynomials over GF(2m), Discrete Math., 321, 76-89 (2014) · Zbl 1339.94088
[33] Ding, K.; Ding, C., A class of two-weight and three-weight codes and their applications in secret sharing, IEEE Trans. Inf. Theory, 61, 11, 5835-5842 (2015) · Zbl 1359.94687
[34] Dobbertin, H.: Almost perfect nonlinear power functions over GF(2^n): a new case for n divisible by 5, Springer-Verlag, pp 113-121 (2000) · Zbl 1010.94550
[35] Du, X.; Wan, Y., Linear codes from quadratic forms, Appl. Algebra Eng. Commun. Comput., 28, 6, 535-547 (2017) · Zbl 1394.94948
[36] 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
[37] Gold, R., Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inf. Theory, 14, 1, 154-156 (1968) · Zbl 0228.62040
[38] Göloǧlu, F.; Krasnayová, D., Proofs of several conjectures on linear codes from Boolean functions, Discrete Math., 342, 2, 572-583 (2019) · Zbl 1417.94101
[39] Han, D.; Yan, H., On an open problem about a class of optimal ternary cyclic codes, Finite Fields Appl., 59, 335-343 (2019) · Zbl 1421.94102
[40] Helleseth, T.; Kholosha, A., Monomial and quadratic bent functions over the finite fields of odd characteristic, IEEE Trans. Inf. Theory, 52, 5, 2018-2032 (2006) · Zbl 1177.94149
[41] Helleseth, T.; Kholosha, A., New binomial bent functions over the finite fields of odd characteristic, IEEE Trans. Inf. Theory, 56, 9, 4646-4652 (2010) · Zbl 1366.94774
[42] Heng, Z.; Yue, Q., Two classes of two-weight linear codes, Finite Fields Appl., 38, 72-92 (2016) · Zbl 1338.94100
[43] Heng, Z.; Yue, Q., A construction of q-ary linear codes with two weights, Finite Fields Appl., 48, 20-42 (2017) · Zbl 1398.94216
[44] Heng, Z.; Yue, Q., Evaluation of the Hamming weights of a class of linear codes based on Gauss sums, Des, Codes Cryptogr., 83, 2, 307-326 (2017) · Zbl 1381.94118
[45] Heng, Z.; Yue, Q.; Li, C., Three classes of linear codes with two or three weights, Discrete Math., 339, 2832-2847 (2016) · Zbl 1372.94455
[46] Hollmann, H.; Xiang, Q., A proof of the Welch and Niho conjectures on crosscorrelations of binary m-squences, Finite Fields Appl., 7, 2, 253-286 (2001) · Zbl 1027.94006
[47] Hu, Z.; Li, N.; Zeng, X., New linear codes with few weights derived from Kloosterman sums, Finite Fields Appl., 62, 101608 (2020) · Zbl 1452.94115
[48] Huffman, W., Pless, V.: Fundamentals of error-correcting codes Cambridge University Press (1997) · Zbl 1099.94030
[49] Jian, G.; Lin, Z.; Feng, R., Two-weight and three-weight linear codes based on Weil sums, Finite Fields Appl., 57, 92-107 (2019) · Zbl 1448.94264
[50] 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
[51] Katz, DJ, Weil sums of binomials, three-level cross-correlation, and a conjecture of Helleseth, J. Comb. Theory, Ser. A, 119, 8, 1644-1659 (2012) · Zbl 1263.11111
[52] Kløve, T., Codes for Error Detection (2007), Singapore: World Scientific, Singapore · Zbl 1131.94002
[53] Kumar, PV; Scholtz, RA; Welch, LR, Generalized bent functions and their properties, J. Comb. Theory(A), 40, 1, 90-107 (1985) · Zbl 0585.94016
[54] Li, C.; Yue, Q.; Fu, F., A construction of several classes of two-weight and three-weight linear codes, Appl. Algebra Eng. Commun. Comput., 28, 1, 11-30 (2017) · Zbl 1384.94126
[55] Li, C.; Bae, S.; Yang, S., Some two-weight and three-weight linear codes, Math. of Comm., 13, 1, 195-211 (2019) · Zbl 1415.94482
[56] Li, C.; Li, N.; Helleseth, T.; Ding, C., The weight distributions of several classes of cyclic codes from APN monomials, IEEE Trans. Inf. Theory, 60, 8, 4710-4721 (2014) · Zbl 1360.94402
[57] Li, F.; Yan, Y.; Wang, Q.; Yan, T., Several classes of binary linear codes and their weight enumerators, Appl. Algebra Eng. Commun. Comput., 30, 2, 93-106 (2019) · Zbl 1412.94232
[58] Li, N.; Li, C.; Helleseth, T.; Ding, C.; Tang, X., Optimal ternary cyclic codes with minimum distance four and five, Finite Fields Appl., 30, 100-120 (2014) · Zbl 1354.94067
[59] Li, N.; Zeng, X., A survey on the applications of Niho exponents, Cryptogr, Commun., 11, 3, 509-548 (2019) · Zbl 1412.12001
[60] Li, N., Zhou, Z., Helleseth, T.: On a conjecture about a class of optimal ternary cyclic codes, IWSDA, pp 62-65 (2015)
[61] Li, S.; Hu, S.; Feng, T.; Ge, G., The weight distribution of a class of cyclic codes related to Hermitian forms graphs, IEEE Trans. Inf. Theory, 59, 5, 3064-3067 (2013) · Zbl 1364.94656
[62] Luo, G.; Cao, X.; Xu, S.; Mi, J., Binary linear codes with two or three weights from niho exponents, Cryptogr, Commun., 10, 2, 301-318 (2018) · Zbl 1412.94234
[63] MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, North-Holland, New York (1977) · Zbl 0369.94008
[64] Meidl, W., Generalized Rothaus construction and non-weakly regular bent functions, J. Combin. Theory Ser. A, 141, 78-89 (2016) · Zbl 1360.11139
[65] Mesnager, S., Linear codes with few weights from weakly regular bent functions based on a generic construction, Cryptogr, Commun., 9, 1, 71-84 (2017) · Zbl 1351.94079
[66] Mesnager, S.; Özbudak, F.; Sinak, A., Linear codes from weakly regular plateaued functions and their secret sharing schemes, Des. Codes Cryptogr., 87, 2-3, 463-480 (2019) · Zbl 1421.94098
[67] Niho, Y.: Multi-valued cross-correlation functions between two maimal linear recursive sequences Doctorial Dissertation (1972)
[68] Nyberg, K., Perfect nonlinear S-boxes, EUROCRYPT’91, Springer-Verlag, LNCS, 547, 378-386 (1991) · Zbl 0766.94012
[69] Nyberg, K., Differentially uniform mappings for cryptography, EUROCRYPT’93, Springer-Verlag, LNCS, 765, 55-64 (1994) · Zbl 0951.94510
[70] Pott, A., Almost perfect and planar functions, Des. Codes Cryptogr., 78, 1, 141-195 (2016) · Zbl 1351.51004
[71] Rothaus, OS, On “bent” functions, J. Combin. Theory Ser. A, 20, 3, 300-305 (1976) · Zbl 0336.12012
[72] Tang, C.; Li, N.; Qi, Y.; Zhou, Z.; Helleseth, T., Linear codes with two or three weights from weakly regualr bent functions, IEEE Trans. Inf. Theory, 62, 3, 1166-1176 (2016) · Zbl 1359.94738
[73] Tang, C.; Qi, Y.; Xu, M., A note on cyclic codes from APN functions, Appl. Algebra Eng. Commun. Comput., 25, 1-2, 21-37 (2014) · Zbl 1342.94123
[74] Tang, D.; Carlet, C.; Zhou, Z., Binary linear codes from vectorial boolean functions and their weight distribution, Discrete Math., 340, 12, 3055-3072 (2017) · Zbl 1403.94113
[75] Tangaraj, A.; McLaughlin, SW, Quantum codes from cyclic codes over GF(4m), IEEE Trans. Inf. Theory, 47, 3, 1176-1178 (2001) · Zbl 1020.94032
[76] Wang, Q., Li, F., Lin, D.: A class of linear codes with three weights. CoRR abs/1512.03866 (2015)
[77] Wang, X.; Zheng, D.; Liu, H., Several classes of linear codes and their weight distributions, Appl. Algebra Eng. Commun. Comput., 30, 1, 75-92 (2019) · Zbl 1453.94148
[78] Wolfmann, J.: Bent functions and coding theory. Difference Sets, Sequences and their Correlation Properties, A. Pott, P. V. Kumar, T. Helleseth and D. Jungnickel, eds.,pp. 393-417. Amsterdam: Kluwer (1999) · Zbl 0972.94023
[79] Wu, Y., Li, N., Zeng, X.: Linear codes from perfect nonlinear functions over finite fields, under reveiw
[80] Wu, Y., Li, N., Zeng, X.: Linear codes with few weights from cyclotomic classes and weakly regular bent functions, under reveiw · Zbl 1448.94277
[81] Xia, Y.; Li, C., Three-weight ternary linear codes from a family of power functions, Finite Fields Appl., 46, 17-37 (2017) · Zbl 1431.94190
[82] Xiang, C.: It is indeed a fundamental construction of all linear codes, Online available at https://arxiv.org/pdf/1610.06355.pdf
[83] Xiang, C.; Feng, K.; Tang, C., A Construction of linear codes over \(\mathbb{F}_{2^t}\) F2t from Boolean functions, IEEE Trans. Inf. Theory, 63, 1, 169-176 (2017) · Zbl 1359.94743
[84] Xiong, M.; Li, N., Optimal cyclic codes with generalized Niho-type zeros and the weight distribution, IEEE Trans. Inf. Theory, 61, 9, 4914-4922 (2015) · Zbl 1359.94774
[85] Xiong, M.; Li, N.; Zhou, Z.; Ding, C., Weight distribution of cyclic codes with arbitrary number of generalized Niho type zeroes, Des Codes Cryptogr., 78, 3, 713-730 (2016) · Zbl 1333.94066
[86] Xu, Y.; Carlet, C.; Mesnager, S.; Wu, C., Classification of bent monomials, constructions of bent multinomials and upper bounds on the nonlinearity of vectorial functions, IEEE Trans. Inf. Theory, 64, 1, 367-383 (2018) · Zbl 1390.94955
[87] Yang, S.; Yao, Z., Complete weight enumerators of a family of three-weight linear codes, Des Codes Cryptogr., 82, 3, 663-674 (2017) · Zbl 1370.94578
[88] Yang, S.; Yao, Z., Complete weight enumerators of a class of linear codes, Discrete Math., 340, 4, 729-739 (2017) · Zbl 1393.94937
[89] Yuan, J.; Carlet, C.; Ding, C., The weight distributions of a class of linear codes from perfect nonlinear functions, IEEE Trans. Inf. Thoery, 52, 2, 712-716 (2006) · Zbl 1192.94128
[90] Yuan, J.; Ding, C., Secret sharing schemes from three classes of linear codes, IEEE Trans. Inf. Theory, 52, 1, 206-212 (2006) · Zbl 1283.94105
[91] Zha, Z.; Kyureghyan, GM; Wang, X., Perfect nonlinear binomials and their semifields, Finite Fields Appl., 15, 2, 125-133 (2009) · Zbl 1194.12003
[92] Zeng, X.; Hu, L.; Jiang, W.; Yue, Q.; Cao, X., The weight distribution of a class of p-ary cyclic codes, Finite Fields Appl, 16, 1, 56-73 (2010) · Zbl 1206.94110
[93] Zeng, X., Li, N., Hu, L.: A class of nonbinary codes and sequence families, SETA, pp 81-94 (2008) · Zbl 1206.94108
[94] Zeng, X.; Liu, J.; Hu, L., Generalized Kasami sequences: the large set, IEEE Trans. Inf. Theory, 53, 7, 2587-2598 (2007) · Zbl 1192.94086
[95] Zeng, X.; Shan, J.; Hu, L., A triple-error-correcting cyclic code from the Gold and Kasami-Welch APN power functions, Finite Fields Appl., 18, 1, 70-92 (2012) · Zbl 1246.94053
[96] Zhou, Z.; Li, N.; Fan, C.; Helleseth, T., Linear codes with two or three weights from quadratic bent functions, Des Codes Cryptogr., 81, 2, 283-295 (2016) · Zbl 1405.94116
[97] Zhou, Z.; Zhang, A.; Ding, C.; Xiong, M., The weight enumerator of three families of cyclic codes, IEEE Trans. Inf. Theory, 59, 9, 6002-6009 (2013) · Zbl 1364.94667
[98] Zheng, Y.; Zhang, X., Plateaued functions, Proceedings of ICICS’99, LNCS, 1726, 284-300 (1999) · Zbl 0982.94038
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.