Abstract
In 2005 Budaghyan, Carlet and Pott constructed the first APN polynomials EA-inequivalent to power functions by applying CCZ-equivalence to the Gold APN functions. It is a natural question whether it is possible to construct APN polynomials EA-inequivalent to power functions by using only EA-equivalence and inverse transformation on a power APN mapping: this would be the simplest method to construct APN polynomials EA-inequivalent to power functions. In the present paper we prove that the answer to this question is positive. By this method we construct a class of APN polynomials EA-inequivalent to power functions. On the other hand it is shown that the APN polynomials constructed by Budaghyan, Carlet and Pott cannot be obtained by the introduced method.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Beth, T., Ding, C.: On almost perfect nonlinear permutations. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 65–76. Springer, Heidelberg (1993)
Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology 4(1), 3–72 (1991)
Budaghyan, L., Carlet, C.: Classes of Quadratic APN Trinomials and Hexanomials and Related Structures. Preprint, available at http://eprint.iacr.org/2007/098
Budaghyan, L., Carlet, C., Leander, G.: Constructing new APN functions from known ones. Preprint, available at http://eprint.iacr.org/2007/063
Budaghyan, L., Carlet, C., Leander, G.: Another class of quadratic APN binomials over \(\mathbf{F}_{2^n}\): the case n divisible by 4. In: Proceedings of the Workshop on Coding and Cryptography (2007) (To appear) available at http://eprint.iacr.org/2006/428.pdf
Budaghyan, L., Carlet, C., Leander, G.: A class of quadratic APN binomials inequivalent to power functions. Submitted to IEEE Trans. Inform. Theory, available at http://eprint.iacr.org/2006/445.pdf
Budaghyan, L., Carlet, C., Felke, P., Leander, G.: An infinite class of quadratic APN functions which are not equivalent to power mappings. Proceedings of the IEEE International Symposium on Information Theory 2006, Seattle, USA (July 2006)
Budaghyan, L., Carlet, C., Pott, A.: New Classes of Almost Bent and Almost Perfect Nonlinear Functions. IEEE Trans. Inform. Theory 52(3), 1141–1152 (2006)
Budaghyan, L., Carlet, C., Pott, A.: New Constructions of Almost Bent and Almost Perfect Nonlinear Functions. In: Charpin, P., Ytrehus, Ø., (eds.) Proceedings of the Workshop on Coding and Cryptography 2005, pp. 306–315 (2005)
Canteaut, A., Charpin, P., Dobbertin, H.: A new characterization of almost bent functions. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 186–200. Springer, Heidelberg (1999)
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)
Canteaut, A., Charpin, P., Dobbertin, H.: Weight divisibility of cyclic codes, highly nonlinear functions on \(\mathbf{F}_{2^m}\), and crosscorrelation of maximum-length sequences. SIAM Journal on Discrete Mathematics 13(1), 105–138 (2000)
Carlet, C.: Vectorial (multi-output) Boolean Functions for Cryptography. In: Crama, Y., Hammer, P. (eds.) Chapter of the monography Boolean Methods and Models, Cambridge University Press, to appear soon. Preliminary version available at http://www-rocq.inria.fr/codes/Claude.Carlet/pubs.html
Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography 15(2), 125–156 (1998)
Chabaud, F., Vaudenay, S.: Links between differential and linear cryptanalysis. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 356–365. Springer, Heidelberg (1995)
Daemen, J., Rijmen, V.: AES proposal: Rijndael (1999), http://csrc.nist.gov/encryption/aes/rijndael/Rijndael.pdf
Dillon, J.F.: APN Polynomials and Related Codes. Polynomials over Finite Fields and Applications, Banff International Research Station (November 2006)
Dobbertin, H.: One-to-One Highly Nonlinear Power Functions on GF(2n). Appl. Algebra Eng. Commun. Comput. 9(2), 139–152 (1998)
Dobbertin, H.: Almost perfect nonlinear power functions over GF(2n): the Niho case. Inform. and Comput. 151, 57–72 (1999)
Dobbertin, H.: Almost perfect nonlinear power functions over GF(2n): the Welch case. IEEE Trans. Inform. Theory 45, 1271–1275 (1999)
Dobbertin, H.: Almost perfect nonlinear power functions over GF(2n): a new case for n divisible by 5. In: Jungnickel, D., Niederreiter, H. (eds.) Proceedings of Finite Fields and Applications FQ5, Augsburg, Germany, pp. 113–121. Springer, Heidelberg (2000)
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)
Gold, R.: Maximal recursive sequences with 3-valued recursive crosscorrelation functions. IEEE Trans. Inform. Theory 14, 154–156 (1968)
Hollmann, H., Xiang, Q.: A proof of the Welch and Niho conjectures on crosscorrelations of binary m-sequences. Finite Fields and Their Applications 7, 253–286 (2001)
Janwa, H., Wilson, R.: Hyperplane sections of Fermat varieties in P 3 in char. 2 and some applications to cyclic codes. In: Moreno, O., Cohen, G., Mora, T. (eds.) AAECC-10. LNCS, vol. 673, pp. 180–194. Springer, Heidelberg (1993)
Kasami, T.: The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes. Inform. and Control 18, 369–394 (1971)
Lachaud, G., Wolfmann, J.: The Weights of the Orthogonals of the Extended Quadratic Binary Goppa Codes. IEEE Trans. Inform. Theory 36, 686–692 (1990)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Nakagawa, N., Yoshiara, S.: A construction of differentially 4-uniform functions from commutative semifields of characteristic 2. In: Proceedings of WAIFI 2007, LNCS (2007)
Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)
Nyberg, K.: S-boxes and Round Functions with Controllable Linearity and Differential Uniformity. In: Preneel, B. (ed.) Fast Software Encryption. LNCS, vol. 1008, pp. 111–130. Springer, Heidelberg (1995)
Sidelnikov, V.: On mutual correlation of sequences. Soviet Math. Dokl. 12, 197–201 (1971)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Budaghyan, L. (2007). The Simplest Method for Constructing APN Polynomials EA-Inequivalent to Power Functions. In: Carlet, C., Sunar, B. (eds) Arithmetic of Finite Fields. WAIFI 2007. Lecture Notes in Computer Science, vol 4547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73074-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-73074-3_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73073-6
Online ISBN: 978-3-540-73074-3
eBook Packages: Computer ScienceComputer Science (R0)