On the algebraic degree stability of Boolean functions when restricted to affine spaces
We study the n-variable Boolean functions which keep their algebraic degree unchanged when they are restricted to any (affine) hyperplane, or more generally to any affine space of a given co-dimension k. For cryptographic applications it is of interest to determine functions f which have a relatively high degree and also maintain this degree when restricted to affine spaces of co-dimension k for k ranging from 1 to as high a value as possible. This highest value will be called the restriction degree stability of f, denoted by deg stab(f). We give several necessary and/or sufficient conditions for f to maintain its degree on spaces of co-dimension k. The value of deg stab(f) is determined for functions which are direct sums of monomial as well as for functions of degrees r ∈ {1, 2, n − 2, n − 1, n}; we also determine the symmetric functions which maintain their degree on any hyperplane. Finally, using our previous results and some computer assistance, we determine the behaviour of all the functions in 8 variables, therefore determining the optimal ones (i.e. with highest value of deg stab(f)) for each degree.
Funding
Boolean functions with optimal stability of their cryptographic indicators under restriction of the inputs
Engineering and Physical Sciences Research Council
Find out more...History
School
- Science
Department
- Computer Science
Published in
Designs, Codes and CryptographySource
13th International Workshop of Coding and CryptographyPublisher
SpringerVersion
- AM (Accepted Manuscript)
Publisher statement
This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/xxxxx. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-termsPublication date
2024-07-10ISSN
0925-1022eISSN
1573-7586Publisher version
Language
- en