×

Crooked maps in \(\mathbb F_{2^n}\). (English) Zbl 1170.94009

Almost perfect nonlinear (APN) maps provide the best resistance against the differential cryptanalysis. A special class of APN maps are called \(crooked\). Crooked maps can be used to construct many interesting combinatorial objects – codes, graphs, schemes, etc. The only known crooked maps are polynomials with exponents of binary weight 2. In this paper, the authors study the question whether other crooked maps exist. Using combinatorics in the cyclic group of order \(n\), the authors show that in a class of maps including power maps only the ones with exponents of binary weight 2 can be crooked.

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bending, T. D.; Fon-Der-Flaass, D., Crooked functions, bent functions, and distance regular graphs, Electron. J. Combin., 5, 1, R34 (1998) · Zbl 0903.05053
[2] T. Berger, A. Canteaut, P. Charpin, Y. Laigle-Chapuy, On almost perfect nonlinear mappings over \(F_2^n\); T. Berger, A. Canteaut, P. Charpin, Y. Laigle-Chapuy, On almost perfect nonlinear mappings over \(F_2^n\) · Zbl 1184.94224
[3] J. Bierbrauer, G. Kyureghyan, Crooked binomials, manuscript, 2005; J. Bierbrauer, G. Kyureghyan, Crooked binomials, manuscript, 2005
[4] Canteaut, A.; Charpin, P., Decomposing bent functions, IEEE Trans. Inform. Theory, 49, 8, 2004-2019 (2003) · Zbl 1184.94230
[5] Canteaut, A.; Charpin, P.; Dobbertin, H., Binary \(m\)-sequences with three-valued crosscorrelation: A proof of Welch’s conjecture, IEEE Trans. Inform. Theory, 46, 1, 4-8 (2000) · Zbl 1003.94519
[6] Carlet, C.; Charpin, P.; Zinoviev, V., Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15, 2, 125-156 (1998) · Zbl 0938.94011
[7] Chabaud, F.; Vaudenay, S., Links between differential and linear cryptanalysis, (Proc. Advances in Cryptology - EUROCRYPT ’94. Proc. Advances in Cryptology - EUROCRYPT ’94, Lecture Notes in Comput. Sci., vol. 950 (1995), Springer: Springer Berlin), 356-365 · Zbl 0879.94023
[8] Dobbertin, H., Almost perfect nonlinear power functions on \(GF(2^n)\): The Niho case, Inform. and Comput., 151, 1-2, 57-72 (1999) · Zbl 1072.94513
[9] Dobbertin, H., Almost perfect nonlinear power functions on \(GF(2^n)\): The Welch case, IEEE Trans. Inform. Theory, 45, 4, 1271-1275 (1999) · Zbl 0957.94021
[10] Dobbertin, H., Almost perfect nonlinear power functions on \(GF(2^n)\): A new case for \(n\) divisible by 5, (Proc. Finite Fields and Applications \(F_q 5 (2001)\), Springer: Springer Berlin), 113-121 · Zbl 1010.94550
[11] Edel, Y.; Kyureghyan, G.; Pott, A., A new APN function which is not equivalent to a power mapping, IEEE Trans. Inform. Theory, 52, 2, 744-747 (2006) · Zbl 1246.11185
[12] Gold, R., Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inform. Theory, 14, 154-156 (1968) · Zbl 0228.62040
[13] D. Hertel, A. Pott, A characterization of a class of maximum nonlinear functions, 2004, submitted for publication; D. Hertel, A. Pott, A characterization of a class of maximum nonlinear functions, 2004, submitted for publication · Zbl 1179.05020
[14] Hollmann, H. D.L.; Xiang, Q., A proof of the Welch and Niho conjectures on cross-correlations of binary \(m\)-sequences, Finite Fields Appl., 7, 2, 253-286 (2001) · Zbl 1027.94006
[15] Kasami, T., The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes, Inform. Control, 18, 369-394 (1971) · Zbl 0217.58802
[16] Klapper, A., Cross-correlations of geometric sequences in characteristic two, Des. Codes Cryptogr., 3, 4, 347-377 (1993) · Zbl 0780.94006
[17] G. Kyureghyan, The only crooked power functions are \(2^k + 2^l\); G. Kyureghyan, The only crooked power functions are \(2^k + 2^l\) · Zbl 1180.94055
[18] Langevin, Ph.; Véron, P., On the non-linearity of power function, Des. Codes Cryptogr., 37, 1, 31-43 (2005) · Zbl 1136.06300
[19] N.G. Leander, Normality of bent functions. Monomial- and binomial-bent functions, PhD thesis, Ruhr Univ. Bochum, Fakultät für Mathematik, Bochum, 2004; N.G. Leander, Normality of bent functions. Monomial- and binomial-bent functions, PhD thesis, Ruhr Univ. Bochum, Fakultät für Mathematik, Bochum, 2004 · Zbl 1310.94159
[20] Lidl, R.; Niederreiter, H., Finite Fields, Encyclopedia Math. Appl., vol. 20 (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge
[21] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1977), North-Holland: North-Holland Amsterdam · Zbl 0369.94008
[22] Nyberg, K., Differentially uniform mappings for cryptography, (Advances in Cryptology - EUROCRYPT ’93. Advances in Cryptology - EUROCRYPT ’93, Lecture Notes in Comput. Sci., vol. 765 (1994), Springer: Springer Berlin), 55-64 · Zbl 0951.94510
[23] van Dam, E. R.; Fon-Der-Flaass, D., Uniformly packed codes and more distance regular graphs from crooked functions, J. Algebraic Combin., 12, 2, 115-121 (2000) · Zbl 0966.05084
[24] van Dam, E. R.; Fon-Der-Flaass, D., Codes, graphs, and schemes from nonlinear functions, European J. Combin., 24, 1, 85-98 (2003) · Zbl 1015.05093
[25] Wolfmann, J., Codes projectifs à deux ou trois poids associés aux hyperquadriques d’une géométrie finie, Discrete Math., 13, 2, 185-211 (1975) · Zbl 0336.05018
[26] Zheng, Y.; Zhang, X.-M., Plateaued functions, (ICICS ’99. ICICS ’99, Lecture Notes in Comput. Sci., vol. 1726 (1999), Springer: Springer Berlin), 284-300 · 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.