The classification of quadratic APN functions in 7 variables and combinatorial approaches to search for APN functions

Standard

The classification of quadratic APN functions in 7 variables and combinatorial approaches to search for APN functions. / Kalgin, Konstantin; Idrisova, Valeriya.

In: Cryptography and Communications, Vol. 15, No. 2, 2023, p. 239-256.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{d5634b26514c4649b9dc2c97de9646a2,

title = "The classification of quadratic APN functions in 7 variables and combinatorial approaches to search for APN functions",

abstract = "Almost perfect nonlinear functions possess optimal resistance to differential cryptanalysis and are widely studied. Most known APN functions are defined using their representation as a polynomial over a finite field and very little is known about combinatorial constructions of them on F2n. In this work we propose two approaches for obtaining quadratic APN functions on F2n. The first approach exploits a secondary construction idea, it considers how to obtain a quadratic APN function in n + 1 variables from a given quadratic APN function in n variables using special restrictions on the new terms. The second approach is searching for quadratic APN functions that have a matrix representation partially filled with the standard basis vectors in a cyclic manner. This approach allows us to find a new APN function in 7 variables. We prove that the updated list of quadratic APN functions in dimension 7 is complete up to CCZ-equivalence. Also, we observe that the quadratic parts of some APN functions have a low differential uniformity. This observation allows us to introduce a new subclass of APN functions, the so-called stacked APN functions. These are APN functions of algebraic degree d such that eliminating monomials of degrees k + 1,…, d for any k < d results in APN functions of algebraic degree k. We provide cubic examples of stacked APN functions for dimensions up to 6.",

keywords = "APN function, Boolean function, Differential uniformity, Quadratic function, S-box",

author = "Konstantin Kalgin and Valeriya Idrisova",

note = "Funding Information: We sincerely thank the anonymous reviewers for their careful reading of this manuscript and suggesting substantial improvements. We would like to cordially thank Natalia Tokareva for her valuable remarks. We are deeply thankful to Christof Beierle for pointing out some inaccuracies. We are much indebted to the reviewers of the SETA-2020 conference for their helpful reviews. We are grateful to Anastasia Gorodilova and Nikolay Kolomeec for their useful observations and fruitful discussions. The work is supported by the Mathematical Center in Akademgorodok under agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation. We are grateful to the Supercomputing Center of the Novosibirsk State University for the provided computational resources. Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

doi = "10.1007/s12095-022-00588-1",

language = "English",

volume = "15",

pages = "239--256",

journal = "Cryptography and Communications",

issn = "1936-2447",

publisher = "Springer Publishing Company",

number = "2",

}

RIS

TY - JOUR

T1 - The classification of quadratic APN functions in 7 variables and combinatorial approaches to search for APN functions

AU - Kalgin, Konstantin

AU - Idrisova, Valeriya

N1 - Funding Information: We sincerely thank the anonymous reviewers for their careful reading of this manuscript and suggesting substantial improvements. We would like to cordially thank Natalia Tokareva for her valuable remarks. We are deeply thankful to Christof Beierle for pointing out some inaccuracies. We are much indebted to the reviewers of the SETA-2020 conference for their helpful reviews. We are grateful to Anastasia Gorodilova and Nikolay Kolomeec for their useful observations and fruitful discussions. The work is supported by the Mathematical Center in Akademgorodok under agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation. We are grateful to the Supercomputing Center of the Novosibirsk State University for the provided computational resources. Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023

Y1 - 2023

N2 - Almost perfect nonlinear functions possess optimal resistance to differential cryptanalysis and are widely studied. Most known APN functions are defined using their representation as a polynomial over a finite field and very little is known about combinatorial constructions of them on F2n. In this work we propose two approaches for obtaining quadratic APN functions on F2n. The first approach exploits a secondary construction idea, it considers how to obtain a quadratic APN function in n + 1 variables from a given quadratic APN function in n variables using special restrictions on the new terms. The second approach is searching for quadratic APN functions that have a matrix representation partially filled with the standard basis vectors in a cyclic manner. This approach allows us to find a new APN function in 7 variables. We prove that the updated list of quadratic APN functions in dimension 7 is complete up to CCZ-equivalence. Also, we observe that the quadratic parts of some APN functions have a low differential uniformity. This observation allows us to introduce a new subclass of APN functions, the so-called stacked APN functions. These are APN functions of algebraic degree d such that eliminating monomials of degrees k + 1,…, d for any k < d results in APN functions of algebraic degree k. We provide cubic examples of stacked APN functions for dimensions up to 6.

AB - Almost perfect nonlinear functions possess optimal resistance to differential cryptanalysis and are widely studied. Most known APN functions are defined using their representation as a polynomial over a finite field and very little is known about combinatorial constructions of them on F2n. In this work we propose two approaches for obtaining quadratic APN functions on F2n. The first approach exploits a secondary construction idea, it considers how to obtain a quadratic APN function in n + 1 variables from a given quadratic APN function in n variables using special restrictions on the new terms. The second approach is searching for quadratic APN functions that have a matrix representation partially filled with the standard basis vectors in a cyclic manner. This approach allows us to find a new APN function in 7 variables. We prove that the updated list of quadratic APN functions in dimension 7 is complete up to CCZ-equivalence. Also, we observe that the quadratic parts of some APN functions have a low differential uniformity. This observation allows us to introduce a new subclass of APN functions, the so-called stacked APN functions. These are APN functions of algebraic degree d such that eliminating monomials of degrees k + 1,…, d for any k < d results in APN functions of algebraic degree k. We provide cubic examples of stacked APN functions for dimensions up to 6.

KW - APN function

KW - Boolean function

KW - Differential uniformity

KW - Quadratic function

KW - S-box

UR - http://www.scopus.com/inward/record.url?scp=85133161476&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/9e0c7fd2-2c7f-3783-b48e-74ad8d99f94c/

U2 - 10.1007/s12095-022-00588-1

DO - 10.1007/s12095-022-00588-1

M3 - Article

AN - SCOPUS:85133161476

VL - 15

SP - 239

EP - 256

JO - Cryptography and Communications

JF - Cryptography and Communications

SN - 1936-2447

IS - 2

ER -

ID: 36526227