Trims and extensions of quadratic APN functions

被引:0
作者
Christof Beierle
Gregor Leander
Léo Perrin
机构
[1] Ruhr University Bochum,
[2] Inria,undefined
来源
Designs, Codes and Cryptography | 2022年 / 90卷
关键词
Almost perfect nonlinear; EA-equivalence; EA-invariant; Linearity; Restriction; Extension; 06E30; 94A60;
D O I
暂无
中图分类号
学科分类号
摘要
In this work, we study functions that can be obtained by restricting a vectorial Boolean function F:F2n→F2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F :\mathbb {F}_{2}^n \rightarrow \mathbb {F}_{2}^n$$\end{document} to an affine hyperplane of dimension n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document} and then projecting the output to an n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document}-dimensional space. We show that a multiset of 2·(2n-1)2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2 \cdot (2^n-1)^2$$\end{document} EA-equivalence classes of such restrictions defines an EA-invariant for vectorial Boolean functions on F2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {F}_{2}^n$$\end{document}. Further, for all of the known quadratic APN functions in dimension n<10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n < 10$$\end{document}, we determine the restrictions that are also APN. Moreover, we construct 6368 new quadratic APN functions in dimension eight up to EA-equivalence by extending a quadratic APN function in dimension seven. A special focus of this work is on quadratic APN functions with maximum linearity. In particular, we characterize a quadratic APN function F:F2n→F2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F :\mathbb {F}_{2}^n \rightarrow \mathbb {F}_{2}^n$$\end{document} with linearity of 2n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{n-1}$$\end{document} by a property of the ortho-derivative of its restriction to a linear hyperplane. Using the fact that all quadratic APN functions in dimension seven are classified, we are able to obtain a classification of all quadratic 8-bit APN functions with linearity 27\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^7$$\end{document} up to EA-equivalence.
引用
收藏
页码:1009 / 1036
页数:27
相关论文
共 40 条
  • [1] Beierle C(2021)Linearly self-equivalent APN permutations in small dimension IEEE Trans. Inf. Theory 67 4863-4875
  • [2] Brinkmann M(2022)New instances of quadratic APN functions IEEE Trans. Inf. Theory 68 670-678
  • [3] Leander G(2008)On the classification of APN functions up to dimension five Des. Codes Cryptogr. 49 273-288
  • [4] Beierle C(2020)Constructing APN functions through isotopic shifts IEEE Trans. Inf. Theory 66 5299-5309
  • [5] Leander G(2021)Generalized isotopic shift construction for APN functions Des. Codes Cryptogr. 89 19-32
  • [6] Brinkmann M(2009)Constructing new APN functions from known ones Finite Fields Their Appl. 15 150-159
  • [7] Leander G(2020)On the EA-classes of known APN functions in small dimensions Cryptogr. Commun. 12 821-840
  • [8] Budaghyan L(2018)Characterizations of the differential uniformity of vectorial functions by the Walsh transform IEEE Trans. Inf. Theory 64 6443-6453
  • [9] Calderini M(1998)Codes, bent functions and permutations suitable for DES-like cryptosystems Des. Codes Cryptogr. 15 125-156
  • [10] Carlet C(2009)A new almost perfect nonlinear function which is not quadratic Adv. Math. Commun. 3 59-81