WAIFI 2014: Arithmetic of Finite Fields pp 83-107

# Open Questions on Nonlinearity and on APN Functions

• Claude Carlet
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 9061)

## Abstract

In a first part of the paper, we recall some known open questions on the nonlinearity of Boolean and vectorial functions and on the APN-ness of vectorial functions. All of them have been extensively searched and seem quite difficult. We also indicate related less well-known open questions. In the second part of the paper, we introduce four new open problems (leading to several related sub-problems) and the results which lead to them. Addressing these problems may be less difficult since they have not been much worked on.

## Keywords

Cryptography Boolean function Nonlinearity Almost Perfect Nonlinear Almost Bent

## Notes

### Acknowledgement

We wish to thank Lilya Budaghyan, Faruk Gologlu and Sihem Mesnager for useful information.

## References

1. 1.
Browning, K., Dillon, J., McQuistan, M.: APN polynomials and related codes. Special volume of Journal of Combinatorics, Information and System Sciences, honoring the 75-th birthday of Prof. D.K.Ray-Chaudhuri 34, 135–159 (2009)Google Scholar
2. 2.
Browning, K., Dillon, J., McQuistan, M., Wolfe, A.: An APN permutation in dimension six. Contemp. Math. 58, 33–42 (2010)
3. 3.
Budaghyan, L., Carlet, C., Helleseth, T.: On bent functions associated to AB functions. In: Proceedings of IEEE Information Theory Workshop (2011)Google Scholar
4. 4.
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)
5. 5.
Carlet, C.: Generalized partial spreads. IEEE Trans. Inform. Theory 41(5), 1482–1487 (1995)
6. 6.
Carlet, C., Feng, K.: An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 425–440. Springer, Heidelberg (2008)
7. 7.
Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 257–397. Cambridge University Press, Cambridge (2010)
8. 8.
Carlet, C.: Vectorial Boolean Functions for Cryptography, Idem, pp. 398–469 (2010)Google Scholar
9. 9.
Carlet, C.: Relating three nonlinearity parameters of vectorial functions and building APN functions from bent. Des. Codes Crypt. 59(1), 89–109 (2011)
10. 10.
Carlet, C.: Open problems on binary bent functions. In: Proceedings of the Conference Open Problems in Mathematical and Computational Sciences, September 18–20, 2013, in Istanbul, Turkey, pp. 203–241. Springer (2014)Google Scholar
11. 11.
Carlet. C.: A survey on nonlinear boolean functions with optimal algebraic immunity suitable for stream ciphers. In: Proceedings of the SMF-VMS Conference, Hué, Vietnam, 20–24 August 2012. (Special issue of the Vietnam Journal of Mathematics, Volume 41, Issue 4, Page 527–541, 2013)Google Scholar
12. 12.
Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Crypt. 15(2), 125–156 (1998)
13. 13.
Carlet, C., Guillot, P.: A new representation of boolean functions. In: Fossorier, M.P.C., Imai, H., Lin, S., Poli, A. (eds.) AAECC 1999. LNCS, vol. 1719, pp. 94–103. Springer, Heidelberg (1999)
14. 14.
Carlet, C., Guillot, P.: Bent, resilient functions and the numerical normal form. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 56, 87–96 (2001)
15. 15.
Carlet, C., Klapper, A.: Upper bounds on the numbers of resilient functions and of bent functions. This paper was meant to appear in an issue of Lecture Notes in Computer Sciences dedicated to Philippe Delsarte, Editor Jean-Jacques Quisquater. But this issue finally never appeared. A shorter version has appeared in the Proceedings of the 23rd Symposium on Information Theory in the Benelux, Louvain-La-Neuve, Belgium (2002)Google Scholar
16. 16.
Carlet, C., Tang, D.: Enhanced Boolean functions suitable for the filter model of pseudo-random generator. Designs, Codes and Cryptography (to appear)Google Scholar
17. 17.
Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)
18. 18.
Chepyzhov, V., Smeets, B.J.M.: On a fast correlation attack on certain stream ciphers. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 176–185. Springer, Heidelberg (1991)
19. 19.
Dillon, J.: A survey of bent functions. NSA Tech. J., 191–215 (1972). Special IssueGoogle Scholar
20. 20.
Dillon, J.F.: Elementary Hadamard Difference sets. Ph. D. Thesis, Univ. of Maryland (1974)Google Scholar
21. 21.
Dobbertin, H.: Another proof of Kasami’s Theorem. Des. Codes Crypt. 17, 177–180 (1999)
22. 22.
Dobbertin, H.: Kasami power functions, permutation polynomials and cyclic difference sets. In: Proceedings of the NATO-A.S.I. Workshop “Difference sets, sequences and their correlation properties”, Bad Windsheim, Kluwer Verlag, pp. 133–158 (1998)Google Scholar
23. 23.
Dillon, J.F., Dobbertin, H.: New cyclic difference sets with Singer parameters. Finite Fields Appl. 10, 342–389 (2004)
24. 24.
Edel, Y., Pott, A.: A new almost perfect nonlinear function which is not quadratic. Adv. Math. Commun. 3(1), 59–81 (2009)
25. 25.
Gologlu, F.: Projective polynomials and their applications in cryptography. In: International Workshop on Boolean Functions and Their Applications, Bergen, September 2014. http://www.people.uib.no/lbu061/gologlu.pdf
26. 26.
Guillot, P.: Completed GPS covers all bent functions. J. Comb. Theory Ser. A 93, 242–260 (2001)
27. 27.
Ding, C., Shan, W., Xiao, G. (eds.): The Stability Theory of Stream Ciphers. LNCS, vol. 561. Springer, Heidelberg (1991)
28. 28.
Helleseth, T.: Kholosha, Alexander: $$x^{2^{l}+1}+x+a$$ and related affine polynomials over $$GF(2^k)$$. Crypt. Commun. 2(1), 85–109 (2010)
29. 29.
Langevin, P., Leander, G.: Counting all bent functions in dimension eight 99270589265934370305785861242880. Des. Codes Crypt. 59(1–3), 193–205 (2011)
30. 30.
Liu, M., Lin, D., Pei, D.: Fast algebraic attacks and decomposition of symmetric boolean functions. IEEE Trans. Inform. Theory 57, 4817–4821 (2011). A preliminary version of this paper was presented in ArXiv: 0910.4632v1 [cs.CR]. http://arxiv.org/abs/0910.4632
31. 31.
Massey, J.L.: Shift-register analysis and BCH decoding. IEEE Trans. Inf. Theory 15, 122–127 (1969)
32. 32.
Nyberg, K.: Perfect nonlinear S-boxes. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 378–386. Springer, Heidelberg (1991)
33. 33.
Piret, G., Roche, T., Carlet, C.: PICARO – a block cipher allowing efficient higher-order side-channel resistance. In: Bao, F., Samarati, P., Zhou, J. (eds.) ACNS 2012. LNCS, vol. 7341, pp. 311–328. Springer, Heidelberg (2012)
34. 34.
Rønjom, S., Helleseth, T.: A new attack on the filter generator. IEEE Trans. Inf. Theory 53(5), 1752–1758 (2007)
35. 35.
Rothaus, O.S.: On “bent” functions. J. Comb. Theory 20A, 300–305 (1976)
36. 36.
Tang, D., Carlet, C., Tang, X.: Highly nonlinear boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks. IEEE Tran. Inf. Theory 59(1), 653–664 (2013)
37. 37.
Tokareva, N.: On the number of bent functions from iterative constructions: lower bounds and hypotheses. Adv. Math. Commun. (AMC) 5, 609–621 (2011)
38. 38.
Wu, B.: $${\cal PS}$$ bent functions constructed from finite pre-quasifield spreads. http://arxiv.org/abs/1308.3355
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8238762021064758, "perplexity": 11927.30194957121}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-43/segments/1570986661296.12/warc/CC-MAIN-20191016014439-20191016041939-00058.warc.gz"}