[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the differential equivalence of APN functions

  • Published:
Cryptography and Communications Aims and scope Submit manuscript

Abstract

Carlet et al. (Des. Codes Cryptogr. 15, 125–156, 1998) defined the associated Boolean function γF(a,b) in 2n variables for a given vectorial Boolean function F from \(\mathbb {F}_{2}^{n}\) to itself. It takes value 1 if a≠0 and equation F(x) + F(x + a) = b has solutions. This article defines the differentially equivalent functions as vectorial functions having equal associated Boolean functions. It is an open problem of great interest to describe the differential equivalence class for a given Almost Perfect Nonlinear (APN) function. We determined that each quadratic APN function G in n variables, n ≤ 6, that is differentially equivalent to a given quadratic APN function F, can be represented as G = F + A, where A is affine. For the APN Gold function F, we completely described all affine functions A such that F and F + A are differentially equivalent. This result implies that the class of APN Gold functions up to EA-equivalence contains the first infinite family of functions, whose differential equivalence class is non-trivial.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bending, T.D., Fon-Der-Flaass, D.: Crooked functions, bent functions, and distance regular graphs. Electron. J. Combin. 5(1), R34 (1998)

    MathSciNet  MATH  Google Scholar 

  2. Berger, T.P., Canteaut, A., Charpin, P., Laigle-Chapuy, Y.: On almost perfect nonlinear functions over \(\mathbb {F}^{n}_{2}\). IEEE Trans. Inf. Theory 52, 4160–4170 (2006)

    Article  MATH  Google Scholar 

  3. Bierbrauer, J., Kyureghyan, G.M.: Crooked binomials. Des. Codes Cryptogr. 46, 269–301 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Boura, C., Canteaut, A., Jean, J., Suder, V.: Two Notions of Differential Equivalence on Sboxes. Extended abstract of The Tenth International Workshop on Coding and Cryptography 2017 (September 18-22 Saint-Petersburg Russia) (2017)

  5. Brinkman, M., Leander, G.: On the classification of APN functions up to dimension five. In: Proc. of the International Workshop on Coding and Cryptography 2007 Dedicated to the Memory of Hans Dobbertin. Versailles, pp. 39–48 (2007)

  6. Browning, K.A., Dillon, J.F., Kibler, R.E., McQuistan, M.T.: APN polynomials and related codes. J. Comb. Inf. Syst. Sci. 34(1-4), 135–159 (2009). Special Issue in honor of Prof. D.K Ray-Chaudhuri on the occasion of his 75th birthday

    MATH  Google Scholar 

  7. Browning, K.A., Dillon, J.F., McQuistan, M.T., Wolfe, A.J.: An APN permutation in dimension six. In: Post-Proceedings of the 9-th International Conference on Finite Fields and Their Applications Fq’09, Contemporary Math. AMS, vol. 518, pp. 33–42 (2010)

  8. Budaghyan, L.: Construction and Analysis of Cryptographic Functions, vol. VIII. Springer International Publishing, p. 168 (2014)

  9. Budaghyan, L., Carlet, C.: CCZ-equivalence of single and multi output Boolean functions. In: Post-Proceedings of the 9-th International Conference on Finite Fields and Their Applications Fq’09, Contemporary Math. AMS, vol. 518, pp. 43–54 (2010)

  10. Budaghyan, L., Carlet, C., Leander, G.: Constructing new APN functions from known ones. Finite Fields Appl. 15(2), 150–159 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Budaghyan, L., Carlet, C., Pott, A.: New classes of almost bent and almost perfect nonlinear polynomials. IEEE Trans. Inform. Theory 52, 1141–1152 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  12. Carlet, C.: Open questions on nonlinearity and on APN functions. Arithmetic of finite fields. Lect. Notes Comput. Sci. 9061, 83–107 (2015)

    Article  MATH  Google Scholar 

  13. Vectorial, C.C.: Boolean functions for cryptography. Ch.9 of the monograph “Boolean Methods and Models in Mathematics, Computer Science, and Engineering”, pp. 398–472. Cambridge Univ. Press (2010)

  14. Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr. 15, 125–156 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  15. Carlet, C., Prouff, E.: On plateaued functions and their constructions. Proceedings of fast software encryption 2003. Lect. Notes Comput. Sci. 2887, 54–73 (2003)

    Article  MATH  Google Scholar 

  16. Dobbertin, H.: Almost perfect nonlinear functions over G F(2n): The Niho case. Inform. Comput. 151, 57–72 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  17. Edel, Y.: Quadratic APN functions as subspaces of alternating bilinear forms. Contact Forum Coding Theory and Cryptography III. Belgium (2009), pp. 11–24 (2011)

  18. Edel, Y., Pott, A.: A new almost perfect nonlinear function which is not quadratic. Adv. Math. Commun. 3(1), 59–81 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  19. Glukhov, M.M.: On the matrices of transitions of differences for some modular groups. Matematicheskie Voprosy Kriptografii. 4(4), 27–47 (2013). (in Russian)

    Article  Google Scholar 

  20. Glukhov, M.M.: On the approximation of discrete functions by linear functions. Matematicheskie Voprosy Kriptografii. 7(4), 29–50 (2016). (in Russian)

    Article  MathSciNet  Google Scholar 

  21. Gorodilova, A.A.: Characterization of almost perfect nonlinear functions in terms of subfunctions. Discret. Math. Appl. 26(4), 193–202 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  22. Gorodilova, A.A.: On a remarkable property of APN Gold functions. Cryptology ePrint Archive Report 2016/286 (2016)

  23. Gorodilova, A.: The linear spectrum of quadratic APN functions. Prikladnaya Diskretnaya Matematika. 4(34), 3–16 (2016). (in Russian)

    MathSciNet  Google Scholar 

  24. Hernando, F., McGuire, G.: Proof of a conjecture on the sequence of exceptional numbers, classifying cyclic codes and APN functions. J. Algebra. 343(1), 78–92 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  25. Hou, X. -D.: Affinity of permutations of \(\mathbb {F}^{n}_{2}\). Discret. Appl. Math. 154, 313–325 (2006)

    Article  Google Scholar 

  26. Idrisova, V: On an algorithm generating 2-to-1 APN functions and its applications to “the big APN problem”. Cryptogr. Commun. (2018)

  27. Kyureghyan, G.: Crooked maps in \({F_{2}^{n}}\). Finite Fields Their Appl. 13(3), 713–726 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  28. Nyberg, K.: Differentially uniform mappings for cryptography. Advances in Cryptography, EUROCRYPT’93. Lect. Notes Comput. Sci. 765, 55–64 (1994)

    Article  MATH  Google Scholar 

  29. Pott, A.: Almost perfect and planar functions. Des. Codes Cryptogr. 78, 141–195 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  30. Suder, V.: Antiderivative functions over \(F_{2^{n}}\). Des. Codes Cryptogr. 82, 435–447 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  31. Tuzhilin, M.E.: APN functions. Prikladnaya Diskretnaya Matematika. 3, 14–20 (2009). (in Russian)

    Google Scholar 

  32. Yoshiara, S.: Equivalences of quadratic APN functions. J. Algebr. Comb. 35, 461–475 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  33. Yu, Y., Wang, M., Li, Y.: A matrix approach for constructing quadratic apn functions. Cryptology ePrint Archive Report 2013/007 (2013)

  34. Yu, Y., Wang, M., Li, Y.: A matrix approach for constructing quadratic APN functions. Des. Codes Cryptogr. 73, 587–600 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author would like to thank Natalia Tokareva, Nikolay Kolomeec and Valeriya Idrisova for fruitful discussions related to this work. The author is also very grateful to the reviewers for the valuable comments and remarks.

Author information

Authors and Affiliations

  1. Sobolev Institute of Mathematics, Novosibirsk, Russia

    Anastasiya Gorodilova

  2. Novosibirsk State University, Novosibirsk, Russia

    Anastasiya Gorodilova

Authors
  1. Anastasiya Gorodilova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anastasiya Gorodilova.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The author was supported by the Russian Foundation for Basic Research (projects no. 17-41-543364, 18-07-01394), by the program of fundamental scientific researches of the SB RAS I.5.1. (project 0314-2016-0017), by the Russian Ministry of Science and Education (the 5-100 Excellence Programme and the Project no. 1.12875.2018/12.1).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gorodilova, A. On the differential equivalence of APN functions. Cryptogr. Commun. 11, 793–813 (2019). https://doi.org/10.1007/s12095-018-0329-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12095-018-0329-y

Keywords

Mathematics Subject Classification (2010)

Search

Navigation