Rad HAZU, Matematičke znanosti, Vol. 25 (2021), 79-105.

ON KNOWN CONSTRUCTIONS OF APN AND AB FUNCTIONS AND THEIR RELATION TO EACH OTHER

Marco Calderini, Lilya Budaghyan and Claude Carlet

Department of Informatics, University of Bergen, Bergen 5005, Norway
e-mail: marco.calderini@uib.no

Department of Informatics, University of Bergen, Bergen 5005, Norway
e-mail: lilya.budaghyan@uib.no

Department of Informatics, University of Bergen, Bergen 5005, Norway
LAGA, University of Paris 8, Saint-Denis 93526, France
e-mail: claude.carlet@gmail.com

Abstract.   This work is dedicated to APN and AB functions which are optimal against differential and linear cryptanlysis when used as Sboxes in block ciphers. They also have numerous applications in other branches of mathematics and information theory such as coding theory, sequence design, combinatorics, algebra and projective geometry. In this paper we give an overview of known constructions of APN and AB functions, in particular, those leading to infinite classes of these functions. Among them, the bivariate construction method, the idea first introduced in 2011 by the third author of the present paper, turned out to be one of the most fruitful. It has been known since 2011 that one of the families derived from the bivariate construction contains the infinite families derived by Dillon’s hexanomial method. Whether the former family is larger than the ones it contains has stayed an open problem which we solve in this paper. Further we consider the general bivariate construction from 2013 by the third author and study its relation to the recently found infinite families of bivariate APN functions.

2020 Mathematics Subject Classification.   94A60, 94A15.

Key words and phrases.   Boolean functions, almost perfect nonlinear (APN) functions, almost bent (AB) functions, cryptography.

Full text (PDF) (free access)

DOI: https://doi.org/10.21857/ygjwrcdkgy

References:

  1. N. Anbar T. Kalayci and W. Meidl, Determining the Walsh spectra of Taniguchi's and related APN-functions, Finite Fields Appl. 60 (2019), 101577, 20 pp.
    MathSciNet     CrossRef

  2. C. Beierle and G. Leander, New instances of quadratic APN functions, ArXiv preprint, 2020.

  3. T. Bending and D. Fon-Der-Flaass, Crooked functions, bent functions and distanceregular graphs, Electron. J. Comb. 5 (1998), R34.
    CrossRef

  4. T. Beth and C. Ding, On almost perfect nonlinear permutations, in: Advances in Cryptology - EUROCRYPT '93, Lecture Notes in Comput. Sci. 765 (1993), Springer-Verlag, New York, pp. 6576.
    MathSciNet     CrossRef

  5. E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. Cryptology 4 (1991), 3-72.
    MathSciNet     CrossRef

  6. A. Bluher, On xq+1 + ax + b, Finite Fields Appl. 10(3) (2004), 285-305.
    MathSciNet     CrossRef

  7. C. Bracken, E. Byrne, N. Markin and G. McGuire, New families of quadratic almost perfect nonlinear trinomials and multinomials, Finite Fields Appl. 14(3) (2008), 703-714.
    CrossRef

  8. C. Bracken, E. Byrne, N. Markin and G. McGuire, A few more quadratic APN functions, Cryptogr. Commun. 3 (2011), 43-53.
    MathSciNet     CrossRef

  9. M. Brinkmann and G. Leander, On the classification of APN functions up to dimension five, Des. Codes Cryptogr. 49 (2008), 273-288.
    MathSciNet     CrossRef

  10. K. A. Browning, J. F. Dillon, R. E. Kibler and M. T. McQuistan, APN polynomials and related Codes, Journal of Combinatorics, Information and System Science, Special Issue in honor of Prof. D.K Ray-Chaudhuri on the occasion of his 75th birthday, 34 (2009), 135-159.

  11. K. A. Browning, J. F. Dillon, M. T. McQuistan and A. J. Wolfe, An APN permutation in dimension six, in: Post-proceedings of the 9-th International Conference on Finite Fields and Their Applications, Contemporary Math. 518 (2010), pp. 33-42.
    MathSciNet     CrossRef

  12. L. Budaghyan, Construction and Analysis of Cryptographic Functions, Springer, Cham, 2015.
    MathSciNet     CrossRef

  13. L. Budaghyan, M. Calderini, C. Carlet, R. Coulter and I. Villa, Constructing APN functions through isotopic shift, IEEE Trans. Inform. Theory 66(8) (2020), 5299-5309.
    MathSciNet     CrossRef

  14. L. Budaghyan, M. Calderini, C. Carlet, R. Coulter and I. Villa, Generalized isotopic shift construction for APN functions, Des. Codes Cryptogr. 89 (2020), 19-32.
    MathSciNet     CrossRef

  15. L. Budaghyan, M. Calderini, C. Carlet, R. Coulter and I. Villa, On isotopic shift construction for planar functions, in: 2019 IEEE International Symposium on Information Theory (ISIT), 2019, pp. 2962-2966.
    CrossRef

  16. L. Budaghyan, M. Calderini, C. Carlet, D. Davidova and N. Kaleyski, A note on the Walsh spectrum of Dobbertin APN functions, in: Proceedings of SETA 2020.

  17. L. Budaghyan, M. Calderini and I. Villa, On equivalence between known families of quadratic APN functions, Finite Fields Appl. 66 (2020), 101704, 21 pp.
    MathSciNet     CrossRef

  18. L. Budaghyan, M. Calderini and I. Villa, On relations between CCZ- and EA- equivalences, Cryptogr. Commun. 12 (2020), 85-100.
    MathSciNet     CrossRef

  19. L. Budaghyan and C. Carlet, Classes of quadratic APN trinomials and hexanomials and related structures, IEEE Trans. Inform. Theory 54(5) (2008), 2354-2357.
    MathSciNet     CrossRef

  20. L. Budaghyan, C. Carlet and G. Leander, Two classes of quadratic APN binomials inequivalent to power functions, IEEE Trans. Inform. Theory 54(9) (2008), 4218-4229.
    MathSciNet     CrossRef

  21. L. Budaghyan, C. Carlet and G. Leander, Constructing new APN functions from known ones, Finite Fields Appl. 15(2) (2009), 150-159.
    MathSciNet     CrossRef

  22. L. Budaghyan, C. Carlet and G. Leander, On a construction of quadratic APN functions, in: Proceedings of IEEE Information Theory workshop ITW'09, 2009, pp. 374-378.
    CrossRef

  23. L. Budaghyan, C. Carlet and A. Pott, New classes of almost bent and almost perfect nonlinear functions, IEEE Trans. Inform. Theory 52(3) (2006), 1141-1152.
    MathSciNet     CrossRef

  24. L. Budaghyan and T. Helleseth, New commutative semifields defined by new PN multinomials, Cryptogr. Commun. 3(1) (2011), 1-16.
    MathSciNet     CrossRef

  25. L. Budaghyan, T. Helleseth and N. Kaleyski, A new family of APN quadrinomials, IEEE Trans. Inform. Theory 66(11) (2020), 7081-7087.
    MathSciNet     CrossRef

  26. M. Calderini, On the EA-classes of known APN functions in small dimensions, Cryptogr. Commun. 12 (2020), 821-840.
    MathSciNet     CrossRef

  27. M. Calderini, M. Sala and I. Villa, A note on APN permutations in even dimension, Finite Fields Appl. 46 (2017), 1-16.
    MathSciNet     CrossRef

  28. A. Canteaut, P. Charpin and H. Dobbertin, Weight divisibility of cyclic codes, highly nonlinear functions on F2m, and crosscorrelation of maximum-length sequences, SIAM J. Discrete Math. 13(1) (2000), 105-138.
    MathSciNet     CrossRef

  29. C. Carlet, Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions, Des. Codes Cryptogr. 59 (2011), 89-109.
    MathSciNet     CrossRef

  30. C. Carlet, More constructions of APN and differentially 4-uniform functions by concatenation, Sci. China Math. 56(7) (2013), 1373-1384.
    MathSciNet     CrossRef

  31. C. Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, 2021.
    CrossRef

  32. C. Carlet, P. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr. 15(2) (1998), 125-156.
    MathSciNet     CrossRef

  33. F. Chabaud and S. Vaudenay, Links between Differential and Linear Cryptanalysis, in: Advances in Cryptology - EUROCRYPT '94, Lecture Notes in Comput. Sci. 950, Springer, Berlin, 1995, pp. 356-365.
    MathSciNet     CrossRef

  34. U. Dempwolff, CCZ equivalence of power functions, Des. Codes Cryptogr. 86(3) (2018), 665-692.
    MathSciNet     CrossRef

  35. H. Dobbertin, Almost perfect nonlinear power functions over GF(2n): the Welch case, IEEE Trans. Inform. Theory 45(4) (1999), 1271-1275.
    MathSciNet     CrossRef

  36. H. Dobbertin, Almost perfect nonlinear power functions over GF(2n): the Niho case, Inform. and Comput. 151(1-2) (1999), 57-72.
    MathSciNet     CrossRef

  37. H. Dobbertin, Almost perfect nonlinear power functions over GF(2n): a new case for n divisible by 5, Proceedings of Finite Fields and Applications, Springer, Berlin, 2001, 113-121.
    MathSciNet

  38. Y. Edel, G. Kyureghyan and A. Pott, A new APN function which is not equivalent to a power function, IEEE Trans. Inform. Theory 52(2) (2006), 744-747.
    MathSciNet     CrossRef

  39. Y. Edel and A. Pott, A new almost perfect nonlinear function which is not quadratic, Adv. Math. Commun. 3(1) (2009), 59-81.
    MathSciNet     CrossRef

  40. R. Gold, Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inform. Theory 14 (1968), 154-156.
    CrossRef

  41. F. Göloglu, Gold-hybrid APN functions, Preprint, 2020.

  42. H. Janwa and R. Wilson, Hyperplane sections of Fermat varieties in P3 in char. 2 and some applications to cyclic codes, in: Proceedings of AAECC-10, Lecture Notes in Comput. Sci. 673 (1993), Springer-Verlag, Berlin, pp. 180-194.
    MathSciNet     CrossRef

  43. N. Kaleyski and K. Li, Personal communications, 2020.

  44. T. Kasami, The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes, Information and Control 18 (1971), 369-394.
    MathSciNet

  45. C. Kaspers and Y. Zhou, A lower bound on the number of inequivalent APN functions, ArXiv preprint, 2020.

  46. L. Kölsch, On CCZ-equivalence of the inverse function, IEEE Trans. Inform. Theory 67 (2021), 4856-4862.
    CrossRef

  47. G. Lachaud and J.Wolfmann, The weights of the orthogonals of the extended quadratic binary Goppa codes, IEEE Trans. Inform. Theory 36 (1990), 686-692.
    MathSciNet     CrossRef

  48. M. Matsui, Linear cryptanalysis methods for DES cipher, in: Advances in Cryptology - Eurocrypt '93, Lecture Notes in Comput. Sci. 765 (1994), pp. 386-397.
    CrossRef

  49. K. Nyberg, Differentially uniform mappings for cryptography, in: Advances in Cryptography - EUROCRYPT '93, Lecture Notes in Comput. Sci. 765 (1994), pp. 55-64.
    MathSciNet     CrossRef

  50. K. Nyberg, S-boxes and round functions with controllable linearity and differential uniformity, in: Fast Software Encryption 1994, Lecture Notes in Comput. Sci. 1008 (1995), pp. 111-130.
    CrossRef

  51. H. Taniguchi, On some quadratic APN functions, Des. Codes Cryptogr. 87 (2019), 1973-1983.
    MathSciNet     CrossRef

  52. G. Weng, Y. Tan and G. Gong, On quadratic almost perfect nonlinear functions and their related algebraic object, in: Proceedings of Workshop on Coding and Cryptography, 2013.

  53. Y. Yu, M. Wang and Y. Li, A matrix approach for constructing quadratic APN functions, Des. Codes Cryptogr. 73 (2014), 587-600.
    MathSciNet     CrossRef

  54. Y. Zhou and A. Pott, A new family of semifields with 2 parameters, Adv. Math. 234 (2013), 43-60.
    MathSciNet     CrossRef

Rad HAZU Home Page